1 /*
2 * Copyright (c) 1998, 2006, 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 class ciMethod;
26
27 class MethodLivenessResult : public BitMap {
28 private:
29 bool _is_valid;
30
31 public:
32 MethodLivenessResult(BitMap::bm_word_t* map, idx_t size_in_bits)
33 : BitMap(map, size_in_bits)
34 , _is_valid(false)
35 {}
36
37 MethodLivenessResult(idx_t size_in_bits)
38 : BitMap(size_in_bits)
39 , _is_valid(false)
40 {}
41
42 void set_is_valid() { _is_valid = true; }
43 bool is_valid() { return _is_valid; }
44 };
45
46 class MethodLiveness : public ResourceObj {
47 public:
48 // The BasicBlock class is used to represent a basic block in the
49 // liveness analysis.
50 class BasicBlock : public ResourceObj {
51 private:
52 // This class is only used by the MethodLiveness class.
53 friend class MethodLiveness;
54
55 // The analyzer which created this basic block.
56 MethodLiveness* _analyzer;
57
58 // The range of this basic block is [start_bci,limit_bci)
59 int _start_bci;
60 int _limit_bci;
61
62 // The liveness at the start of the block;
63 BitMap _entry;
64
65 // The summarized liveness effects of our direct successors reached
66 // by normal control flow
67 BitMap _normal_exit;
68
69 // The summarized liveness effects of our direct successors reached
70 // by exceptional control flow
71 BitMap _exception_exit;
72
73 // These members hold the results of the last call to
74 // compute_gen_kill_range(). _gen is the set of locals
75 // used before they are defined in the range. _kill is the
76 // set of locals defined before they are used.
77 BitMap _gen;
78 BitMap _kill;
79 int _last_bci;
80
81 // A list of all blocks which could come directly before this one
82 // in normal (non-exceptional) control flow. We propagate liveness
83 // information to these blocks.
84 GrowableArray<BasicBlock*>* _normal_predecessors;
85
86 // A list of all blocks which could come directly before this one
87 // in exceptional control flow.
88 GrowableArray<BasicBlock*>* _exception_predecessors;
89
90 // The following fields are used to manage a work list used in the
91 // dataflow.
92 BasicBlock *_next;
93 bool _on_work_list;
94
95 // Our successors call this method to merge liveness information into
96 // our _normal_exit member.
97 bool merge_normal(BitMap other);
98
99 // Our successors call this method to merge liveness information into
100 // our _exception_exit member.
101 bool merge_exception(BitMap other);
102
103 // This helper routine is used to help compute the gen/kill pair for
104 // the block. It is also used to answer queries.
105 void compute_gen_kill_range(ciBytecodeStream *bytes);
106
107 // Compute the gen/kill effect of a single instruction.
108 void compute_gen_kill_single(ciBytecodeStream *instruction);
109
110 // Helpers for compute_gen_kill_single.
111 void load_one(int local);
112 void load_two(int local);
113 void store_one(int local);
114 void store_two(int local);
115
116 BasicBlock(MethodLiveness *analyzer, int start, int limit);
117
118 // -- Accessors
119
120 int start_bci() const { return _start_bci; }
121
122 int limit_bci() const { return _limit_bci; }
123 void set_limit_bci(int limit) { _limit_bci = limit; }
124
125 BasicBlock *next() const { return _next; }
126 void set_next(BasicBlock *next) { _next = next; }
127
128 bool on_work_list() const { return _on_work_list; }
129 void set_on_work_list(bool val) { _on_work_list = val; }
130
131 // -- Flow graph construction.
132
133 // Add a basic block to our list of normal predecessors.
134 void add_normal_predecessor(BasicBlock *pred) {
135 _normal_predecessors->append_if_missing(pred);
136 }
137
138 // Add a basic block to our list of exceptional predecessors
139 void add_exception_predecessor(BasicBlock *pred) {
140 _exception_predecessors->append_if_missing(pred);
141 }
142
143 // Split the basic block at splitBci. This basic block
144 // becomes the second half. The first half is newly created.
145 BasicBlock *split(int splitBci);
146
147 // -- Dataflow.
148
149 void compute_gen_kill(ciMethod* method);
150
151 // Propagate changes from this basic block
152 void propagate(MethodLiveness *ml);
153
154 // -- Query.
155
156 MethodLivenessResult get_liveness_at(ciMethod* method, int bci);
157
158 // -- Debugging.
159
160 void print_on(outputStream *os) const PRODUCT_RETURN;
161
162 }; // End of MethodLiveness::BasicBlock
163
164 private:
165 // The method we are analyzing.
166 ciMethod* _method;
167 ciMethod* method() const { return _method; }
168
169 // The arena for storing structures...
170 Arena* _arena;
171 Arena* arena() const { return _arena; }
172
173 // We cache the length of the method.
174 int _code_size;
175
176 // The size of a BitMap.
177 int _bit_map_size_bits;
178 int _bit_map_size_words;
179
180 // A list of all BasicBlocks.
181 BasicBlock **_block_list;
182
183 // number of blocks
184 int _block_count;
185
186 // Keeps track of bci->block mapping. One entry for each bci. Only block starts are
187 // recorded.
188 GrowableArray<BasicBlock*>* _block_map;
189
190 // Our work list.
191 BasicBlock *_work_list;
192
193 #ifdef COMPILER1
194 // bcis where blocks start are marked
195 BitMap _bci_block_start;
196 #endif // COMPILER1
197
198 // -- Graph construction & Analysis
199
200 // Compute ranges and predecessors for basic blocks.
201 void init_basic_blocks();
202
203 // Compute gen/kill information for all basic blocks.
204 void init_gen_kill();
205
206 // Perform the dataflow.
207 void propagate_liveness();
208
209 // The class MethodLiveness::BasicBlock needs special access to some
210 // of our members.
211 friend class MethodLiveness::BasicBlock;
212
213 // And accessors.
214 int bit_map_size_bits() const { return _bit_map_size_bits; }
215 int bit_map_size_words() const { return _bit_map_size_words; }
216
217 // Work list manipulation routines. Called internally by BasicBlock.
218 BasicBlock *work_list_get();
219 void work_list_add(BasicBlock *block);
220
221 // -- Timing and Statistics.
222
223
224 // Timers
225 static elapsedTimer _time_build_graph;
226 static elapsedTimer _time_gen_kill;
227 static elapsedTimer _time_flow;
228 static elapsedTimer _time_query;
229 static elapsedTimer _time_total;
230
231 #ifndef PRODUCT
232
233 // Counts
234 static long _total_bytes;
235 static int _total_methods;
236
237 static long _total_blocks;
238 static int _max_method_blocks;
239
240 static long _total_edges;
241 static int _max_block_edges;
242
243 static long _total_exc_edges;
244 static int _max_block_exc_edges;
245
246 static long _total_method_locals;
247 static int _max_method_locals;
248
249 static long _total_locals_queried;
250 static long _total_live_locals_queried;
251
252 static long _total_visits;
253
254 #endif
255
256 public:
257 // Create a liveness analyzer for a method
258 MethodLiveness(Arena* arena, ciMethod* method);
259
260 // Compute liveness information for the method
261 void compute_liveness();
262
263 // Find out which locals are live at a specific bci.
264 MethodLivenessResult get_liveness_at(int bci);
265
266 #ifdef COMPILER1
267 const BitMap get_bci_block_start() const { return _bci_block_start; }
268 #endif // COMPILER1
269
270 static void print_times() PRODUCT_RETURN;
271 };