1 /*
2 * Copyright (c) 1998, 2019, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #ifndef SHARE_COMPILER_METHODLIVENESS_HPP
26 #define SHARE_COMPILER_METHODLIVENESS_HPP
27
28 #include "utilities/bitMap.hpp"
29 #include "utilities/growableArray.hpp"
30
31 class ciMethod;
32
33 class MethodLivenessResult : public ResourceBitMap {
34 private:
35 bool _is_valid;
36
37 public:
38 MethodLivenessResult()
39 : ResourceBitMap()
40 , _is_valid(false)
41 {}
42
43 MethodLivenessResult(idx_t size_in_bits)
44 : ResourceBitMap(size_in_bits)
45 , _is_valid(false)
46 {}
47
48 void set_is_valid() { _is_valid = true; }
49 bool is_valid() const { return _is_valid; }
50
51 #ifdef ASSERT
52 bool at(idx_t index) const {
53 assert(is_valid(), "reading invalid");
54 return ResourceBitMap::at(index);
55 }
56 #endif
57 };
58
59 class MethodLiveness : public ArenaObj {
60 public:
61 // The BasicBlock class is used to represent a basic block in the
62 // liveness analysis.
63 class BasicBlock : public ArenaObj {
64 private:
65 // This class is only used by the MethodLiveness class.
66 friend class MethodLiveness;
67
68 // The analyzer which created this basic block.
69 MethodLiveness* _analyzer;
70
71 // The range of this basic block is [start_bci,limit_bci)
72 int _start_bci;
73 int _limit_bci;
74
75 // The liveness at the start of the block;
76 ArenaBitMap _entry;
77
78 // The summarized liveness effects of our direct successors reached
79 // by normal control flow
80 ArenaBitMap _normal_exit;
81
82 // The summarized liveness effects of our direct successors reached
83 // by exceptional control flow
84 ArenaBitMap _exception_exit;
85
86 // These members hold the results of the last call to
87 // compute_gen_kill_range(). _gen is the set of locals
88 // used before they are defined in the range. _kill is the
89 // set of locals defined before they are used.
90 ArenaBitMap _gen;
91 ArenaBitMap _kill;
92 int _last_bci;
93
94 // A list of all blocks which could come directly before this one
95 // in normal (non-exceptional) control flow. We propagate liveness
96 // information to these blocks.
97 GrowableArray<BasicBlock*>* _normal_predecessors;
98
99 // A list of all blocks which could come directly before this one
100 // in exceptional control flow.
101 GrowableArray<BasicBlock*>* _exception_predecessors;
102
103 // The following fields are used to manage a work list used in the
104 // dataflow.
105 BasicBlock *_next;
106 bool _on_work_list;
107
108 // Our successors call this method to merge liveness information into
109 // our _normal_exit member.
110 bool merge_normal(const BitMap& other);
111
112 // Our successors call this method to merge liveness information into
113 // our _exception_exit member.
114 bool merge_exception(const BitMap& other);
115
116 // This helper routine is used to help compute the gen/kill pair for
117 // the block. It is also used to answer queries.
118 void compute_gen_kill_range(ciBytecodeStream *bytes);
119
120 // Compute the gen/kill effect of a single instruction.
121 void compute_gen_kill_single(ciBytecodeStream *instruction);
122
123 // Helpers for compute_gen_kill_single.
124 void load_one(int local);
125 void load_two(int local);
126 void store_one(int local);
127 void store_two(int local);
128
129 BasicBlock(MethodLiveness *analyzer, int start, int limit);
130
131 // -- Accessors
132
133 int start_bci() const { return _start_bci; }
134
135 int limit_bci() const { return _limit_bci; }
136 void set_limit_bci(int limit) { _limit_bci = limit; }
137
138 BasicBlock *next() const { return _next; }
139 void set_next(BasicBlock *next) { _next = next; }
140
141 bool on_work_list() const { return _on_work_list; }
142 void set_on_work_list(bool val) { _on_work_list = val; }
143
144 // -- Flow graph construction.
145
146 // Add a basic block to our list of normal predecessors.
147 void add_normal_predecessor(BasicBlock *pred) {
148 _normal_predecessors->append_if_missing(pred);
149 }
150
151 // Add a basic block to our list of exceptional predecessors
152 void add_exception_predecessor(BasicBlock *pred) {
153 _exception_predecessors->append_if_missing(pred);
154 }
155
156 // Split the basic block at splitBci. This basic block
157 // becomes the second half. The first half is newly created.
158 BasicBlock *split(int splitBci);
159
160 // -- Dataflow.
161
162 void compute_gen_kill(ciMethod* method);
163
164 // Propagate changes from this basic block
165 void propagate(MethodLiveness *ml);
166
167 // -- Query.
168
169 MethodLivenessResult get_liveness_at(ciMethod* method, int bci);
170
171 // -- Debugging.
172
173 void print_on(outputStream *os) const PRODUCT_RETURN;
174
175 }; // End of MethodLiveness::BasicBlock
176
177 private:
178 // The method we are analyzing.
179 ciMethod* _method;
180 ciMethod* method() const { return _method; }
181
182 // The arena for storing structures...
183 Arena* _arena;
184 Arena* arena() const { return _arena; }
185
186 // We cache the length of the method.
187 int _code_size;
188
189 // The size of a BitMap.
190 int _bit_map_size_bits;
191
192 // A list of all BasicBlocks.
193 BasicBlock **_block_list;
194
195 // number of blocks
196 int _block_count;
197
198 // Keeps track of bci->block mapping. One entry for each bci. Only block starts are
199 // recorded.
200 GrowableArray<BasicBlock*>* _block_map;
201
202 // Our work list.
203 BasicBlock *_work_list;
204
205 #ifdef COMPILER1
206 // bcis where blocks start are marked
207 ArenaBitMap _bci_block_start;
208 #endif // COMPILER1
209
210 // -- Graph construction & Analysis
211
212 // Compute ranges and predecessors for basic blocks.
213 void init_basic_blocks();
214
215 // Compute gen/kill information for all basic blocks.
216 void init_gen_kill();
217
218 // Perform the dataflow.
219 void propagate_liveness();
220
221 // The class MethodLiveness::BasicBlock needs special access to some
222 // of our members.
223 friend class MethodLiveness::BasicBlock;
224
225 // And accessors.
226 int bit_map_size_bits() const { return _bit_map_size_bits; }
227
228 // Work list manipulation routines. Called internally by BasicBlock.
229 BasicBlock *work_list_get();
230 void work_list_add(BasicBlock *block);
231
232 public:
233 // Create a liveness analyzer for a method
234 MethodLiveness(Arena* arena, ciMethod* method);
235
236 // Compute liveness information for the method
237 void compute_liveness();
238
239 // Find out which locals are live at a specific bci.
240 MethodLivenessResult get_liveness_at(int bci);
241
242 #ifdef COMPILER1
243 const BitMap& get_bci_block_start() const { return _bci_block_start; }
244 #endif // COMPILER1
245
246 };
247
248 #endif // SHARE_COMPILER_METHODLIVENESS_HPP