|
1 /* |
|
2 * Copyright 1998-2006 Sun Microsystems, Inc. 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
|
20 * CA 95054 USA or visit www.sun.com if you need additional information or |
|
21 * have any questions. |
|
22 * |
|
23 */ |
|
24 |
|
25 // The MethodLiveness class performs a simple liveness analysis on a method |
|
26 // in order to decide which locals are live (that is, will be used again) at |
|
27 // a particular bytecode index (bci). |
|
28 // |
|
29 // The algorithm goes: |
|
30 // |
|
31 // 1. Break the method into a set of basic blocks. For each basic block we |
|
32 // also keep track of its set of predecessors through normal control flow |
|
33 // and predecessors through exceptional control flow. |
|
34 // |
|
35 // 2. For each basic block, compute two sets, gen (the set of values used before |
|
36 // they are defined) and kill (the set of values defined before they are used) |
|
37 // in the basic block. A basic block "needs" the locals in its gen set to |
|
38 // perform its computation. A basic block "provides" values for the locals in |
|
39 // its kill set, allowing a need from a successor to be ignored. |
|
40 // |
|
41 // 3. Liveness information (the set of locals which are needed) is pushed backwards through |
|
42 // the program, from blocks to their predecessors. We compute and store liveness |
|
43 // information for the normal/exceptional exit paths for each basic block. When |
|
44 // this process reaches a fixed point, we are done. |
|
45 // |
|
46 // 4. When we are asked about the liveness at a particular bci with a basic block, we |
|
47 // compute gen/kill sets which represent execution from that bci to the exit of |
|
48 // its blocks. We then compose this range gen/kill information with the normal |
|
49 // and exceptional exit information for the block to produce liveness information |
|
50 // at that bci. |
|
51 // |
|
52 // The algorithm is approximate in many respects. Notably: |
|
53 // |
|
54 // 1. We do not do the analysis necessary to match jsr's with the appropriate ret. |
|
55 // Instead we make the conservative assumption that any ret can return to any |
|
56 // jsr return site. |
|
57 // 2. Instead of computing the effects of exceptions at every instruction, we |
|
58 // summarize the effects of all exceptional continuations from the block as |
|
59 // a single set (_exception_exit), losing some information but simplifying the |
|
60 // analysis. |
|
61 |
|
62 |
|
63 # include "incls/_precompiled.incl" |
|
64 # include "incls/_methodLiveness.cpp.incl" |
|
65 |
|
66 //-------------------------------------------------------------------------- |
|
67 // The BitCounter class is used for counting the number of bits set in |
|
68 // some BitMap. It is only used when collecting liveness statistics. |
|
69 |
|
70 #ifndef PRODUCT |
|
71 |
|
72 class BitCounter: public BitMapClosure { |
|
73 private: |
|
74 int _count; |
|
75 public: |
|
76 BitCounter() : _count(0) {} |
|
77 |
|
78 // Callback when bit in map is set |
|
79 virtual void do_bit(size_t offset) { |
|
80 _count++; |
|
81 } |
|
82 |
|
83 int count() { |
|
84 return _count; |
|
85 } |
|
86 }; |
|
87 |
|
88 |
|
89 //-------------------------------------------------------------------------- |
|
90 |
|
91 |
|
92 // Counts |
|
93 long MethodLiveness::_total_bytes = 0; |
|
94 int MethodLiveness::_total_methods = 0; |
|
95 |
|
96 long MethodLiveness::_total_blocks = 0; |
|
97 int MethodLiveness::_max_method_blocks = 0; |
|
98 |
|
99 long MethodLiveness::_total_edges = 0; |
|
100 int MethodLiveness::_max_block_edges = 0; |
|
101 |
|
102 long MethodLiveness::_total_exc_edges = 0; |
|
103 int MethodLiveness::_max_block_exc_edges = 0; |
|
104 |
|
105 long MethodLiveness::_total_method_locals = 0; |
|
106 int MethodLiveness::_max_method_locals = 0; |
|
107 |
|
108 long MethodLiveness::_total_locals_queried = 0; |
|
109 long MethodLiveness::_total_live_locals_queried = 0; |
|
110 |
|
111 long MethodLiveness::_total_visits = 0; |
|
112 |
|
113 #endif |
|
114 |
|
115 // Timers |
|
116 elapsedTimer MethodLiveness::_time_build_graph; |
|
117 elapsedTimer MethodLiveness::_time_gen_kill; |
|
118 elapsedTimer MethodLiveness::_time_flow; |
|
119 elapsedTimer MethodLiveness::_time_query; |
|
120 elapsedTimer MethodLiveness::_time_total; |
|
121 |
|
122 MethodLiveness::MethodLiveness(Arena* arena, ciMethod* method) |
|
123 #ifdef COMPILER1 |
|
124 : _bci_block_start((uintptr_t*)arena->Amalloc((method->code_size() >> LogBitsPerByte) + 1), method->code_size()) |
|
125 #endif |
|
126 { |
|
127 _arena = arena; |
|
128 _method = method; |
|
129 _bit_map_size_bits = method->max_locals(); |
|
130 _bit_map_size_words = (_bit_map_size_bits / sizeof(unsigned int)) + 1; |
|
131 |
|
132 #ifdef COMPILER1 |
|
133 _bci_block_start.clear(); |
|
134 #endif |
|
135 } |
|
136 |
|
137 void MethodLiveness::compute_liveness() { |
|
138 #ifndef PRODUCT |
|
139 if (TraceLivenessGen) { |
|
140 tty->print_cr("################################################################"); |
|
141 tty->print("# Computing liveness information for "); |
|
142 method()->print_short_name(); |
|
143 } |
|
144 |
|
145 if (TimeLivenessAnalysis) _time_total.start(); |
|
146 #endif |
|
147 |
|
148 { |
|
149 TraceTime buildGraph(NULL, &_time_build_graph, TimeLivenessAnalysis); |
|
150 init_basic_blocks(); |
|
151 } |
|
152 { |
|
153 TraceTime genKill(NULL, &_time_gen_kill, TimeLivenessAnalysis); |
|
154 init_gen_kill(); |
|
155 } |
|
156 { |
|
157 TraceTime flow(NULL, &_time_flow, TimeLivenessAnalysis); |
|
158 propagate_liveness(); |
|
159 } |
|
160 |
|
161 #ifndef PRODUCT |
|
162 if (TimeLivenessAnalysis) _time_total.stop(); |
|
163 |
|
164 if (TimeLivenessAnalysis) { |
|
165 // Collect statistics |
|
166 _total_bytes += method()->code_size(); |
|
167 _total_methods++; |
|
168 |
|
169 int num_blocks = _block_count; |
|
170 _total_blocks += num_blocks; |
|
171 _max_method_blocks = MAX2(num_blocks,_max_method_blocks); |
|
172 |
|
173 for (int i=0; i<num_blocks; i++) { |
|
174 BasicBlock *block = _block_list[i]; |
|
175 |
|
176 int numEdges = block->_normal_predecessors->length(); |
|
177 int numExcEdges = block->_exception_predecessors->length(); |
|
178 |
|
179 _total_edges += numEdges; |
|
180 _total_exc_edges += numExcEdges; |
|
181 _max_block_edges = MAX2(numEdges,_max_block_edges); |
|
182 _max_block_exc_edges = MAX2(numExcEdges,_max_block_exc_edges); |
|
183 } |
|
184 |
|
185 int numLocals = _bit_map_size_bits; |
|
186 _total_method_locals += numLocals; |
|
187 _max_method_locals = MAX2(numLocals,_max_method_locals); |
|
188 } |
|
189 #endif |
|
190 } |
|
191 |
|
192 |
|
193 void MethodLiveness::init_basic_blocks() { |
|
194 bool bailout = false; |
|
195 |
|
196 int method_len = method()->code_size(); |
|
197 ciMethodBlocks *mblocks = method()->get_method_blocks(); |
|
198 |
|
199 // Create an array to store the bci->BasicBlock mapping. |
|
200 _block_map = new (arena()) GrowableArray<BasicBlock*>(arena(), method_len, method_len, NULL); |
|
201 |
|
202 _block_count = mblocks->num_blocks(); |
|
203 _block_list = (BasicBlock **) arena()->Amalloc(sizeof(BasicBlock *) * _block_count); |
|
204 |
|
205 // Used for patching up jsr/ret control flow. |
|
206 GrowableArray<BasicBlock*>* jsr_exit_list = new GrowableArray<BasicBlock*>(5); |
|
207 GrowableArray<BasicBlock*>* ret_list = new GrowableArray<BasicBlock*>(5); |
|
208 |
|
209 // generate our block list from ciMethodBlocks |
|
210 for (int blk = 0; blk < _block_count; blk++) { |
|
211 ciBlock *cib = mblocks->block(blk); |
|
212 int start_bci = cib->start_bci(); |
|
213 _block_list[blk] = new (arena()) BasicBlock(this, start_bci, cib->limit_bci()); |
|
214 _block_map->at_put(start_bci, _block_list[blk]); |
|
215 #ifdef COMPILER1 |
|
216 // mark all bcis where a new basic block starts |
|
217 _bci_block_start.set_bit(start_bci); |
|
218 #endif // COMPILER1 |
|
219 } |
|
220 // fill in the predecessors of blocks |
|
221 ciBytecodeStream bytes(method()); |
|
222 |
|
223 for (int blk = 0; blk < _block_count; blk++) { |
|
224 BasicBlock *current_block = _block_list[blk]; |
|
225 int bci = mblocks->block(blk)->control_bci(); |
|
226 |
|
227 if (bci == ciBlock::fall_through_bci) { |
|
228 int limit = current_block->limit_bci(); |
|
229 if (limit < method_len) { |
|
230 BasicBlock *next = _block_map->at(limit); |
|
231 assert( next != NULL, "must be a block immediately following this one."); |
|
232 next->add_normal_predecessor(current_block); |
|
233 } |
|
234 continue; |
|
235 } |
|
236 bytes.reset_to_bci(bci); |
|
237 Bytecodes::Code code = bytes.next(); |
|
238 BasicBlock *dest; |
|
239 |
|
240 // Now we need to interpret the instruction's effect |
|
241 // on control flow. |
|
242 assert (current_block != NULL, "we must have a current block"); |
|
243 switch (code) { |
|
244 case Bytecodes::_ifeq: |
|
245 case Bytecodes::_ifne: |
|
246 case Bytecodes::_iflt: |
|
247 case Bytecodes::_ifge: |
|
248 case Bytecodes::_ifgt: |
|
249 case Bytecodes::_ifle: |
|
250 case Bytecodes::_if_icmpeq: |
|
251 case Bytecodes::_if_icmpne: |
|
252 case Bytecodes::_if_icmplt: |
|
253 case Bytecodes::_if_icmpge: |
|
254 case Bytecodes::_if_icmpgt: |
|
255 case Bytecodes::_if_icmple: |
|
256 case Bytecodes::_if_acmpeq: |
|
257 case Bytecodes::_if_acmpne: |
|
258 case Bytecodes::_ifnull: |
|
259 case Bytecodes::_ifnonnull: |
|
260 // Two way branch. Set predecessors at each destination. |
|
261 dest = _block_map->at(bytes.next_bci()); |
|
262 assert(dest != NULL, "must be a block immediately following this one."); |
|
263 dest->add_normal_predecessor(current_block); |
|
264 |
|
265 dest = _block_map->at(bytes.get_dest()); |
|
266 assert(dest != NULL, "branch desination must start a block."); |
|
267 dest->add_normal_predecessor(current_block); |
|
268 break; |
|
269 case Bytecodes::_goto: |
|
270 dest = _block_map->at(bytes.get_dest()); |
|
271 assert(dest != NULL, "branch desination must start a block."); |
|
272 dest->add_normal_predecessor(current_block); |
|
273 break; |
|
274 case Bytecodes::_goto_w: |
|
275 dest = _block_map->at(bytes.get_far_dest()); |
|
276 assert(dest != NULL, "branch desination must start a block."); |
|
277 dest->add_normal_predecessor(current_block); |
|
278 break; |
|
279 case Bytecodes::_tableswitch: |
|
280 { |
|
281 Bytecode_tableswitch *tableswitch = |
|
282 Bytecode_tableswitch_at(bytes.cur_bcp()); |
|
283 |
|
284 int len = tableswitch->length(); |
|
285 |
|
286 dest = _block_map->at(bci + tableswitch->default_offset()); |
|
287 assert(dest != NULL, "branch desination must start a block."); |
|
288 dest->add_normal_predecessor(current_block); |
|
289 while (--len >= 0) { |
|
290 dest = _block_map->at(bci + tableswitch->dest_offset_at(len)); |
|
291 assert(dest != NULL, "branch desination must start a block."); |
|
292 dest->add_normal_predecessor(current_block); |
|
293 } |
|
294 break; |
|
295 } |
|
296 |
|
297 case Bytecodes::_lookupswitch: |
|
298 { |
|
299 Bytecode_lookupswitch *lookupswitch = |
|
300 Bytecode_lookupswitch_at(bytes.cur_bcp()); |
|
301 |
|
302 int npairs = lookupswitch->number_of_pairs(); |
|
303 |
|
304 dest = _block_map->at(bci + lookupswitch->default_offset()); |
|
305 assert(dest != NULL, "branch desination must start a block."); |
|
306 dest->add_normal_predecessor(current_block); |
|
307 while(--npairs >= 0) { |
|
308 LookupswitchPair *pair = lookupswitch->pair_at(npairs); |
|
309 dest = _block_map->at( bci + pair->offset()); |
|
310 assert(dest != NULL, "branch desination must start a block."); |
|
311 dest->add_normal_predecessor(current_block); |
|
312 } |
|
313 break; |
|
314 } |
|
315 |
|
316 case Bytecodes::_jsr: |
|
317 { |
|
318 assert(bytes.is_wide()==false, "sanity check"); |
|
319 dest = _block_map->at(bytes.get_dest()); |
|
320 assert(dest != NULL, "branch desination must start a block."); |
|
321 dest->add_normal_predecessor(current_block); |
|
322 BasicBlock *jsrExit = _block_map->at(current_block->limit_bci()); |
|
323 assert(jsrExit != NULL, "jsr return bci must start a block."); |
|
324 jsr_exit_list->append(jsrExit); |
|
325 break; |
|
326 } |
|
327 case Bytecodes::_jsr_w: |
|
328 { |
|
329 dest = _block_map->at(bytes.get_far_dest()); |
|
330 assert(dest != NULL, "branch desination must start a block."); |
|
331 dest->add_normal_predecessor(current_block); |
|
332 BasicBlock *jsrExit = _block_map->at(current_block->limit_bci()); |
|
333 assert(jsrExit != NULL, "jsr return bci must start a block."); |
|
334 jsr_exit_list->append(jsrExit); |
|
335 break; |
|
336 } |
|
337 |
|
338 case Bytecodes::_wide: |
|
339 assert(false, "wide opcodes should not be seen here"); |
|
340 break; |
|
341 case Bytecodes::_athrow: |
|
342 case Bytecodes::_ireturn: |
|
343 case Bytecodes::_lreturn: |
|
344 case Bytecodes::_freturn: |
|
345 case Bytecodes::_dreturn: |
|
346 case Bytecodes::_areturn: |
|
347 case Bytecodes::_return: |
|
348 // These opcodes are not the normal predecessors of any other opcodes. |
|
349 break; |
|
350 case Bytecodes::_ret: |
|
351 // We will patch up jsr/rets in a subsequent pass. |
|
352 ret_list->append(current_block); |
|
353 break; |
|
354 case Bytecodes::_breakpoint: |
|
355 // Bail out of there are breakpoints in here. |
|
356 bailout = true; |
|
357 break; |
|
358 default: |
|
359 // Do nothing. |
|
360 break; |
|
361 } |
|
362 } |
|
363 // Patch up the jsr/ret's. We conservatively assume that any ret |
|
364 // can return to any jsr site. |
|
365 int ret_list_len = ret_list->length(); |
|
366 int jsr_exit_list_len = jsr_exit_list->length(); |
|
367 if (ret_list_len > 0 && jsr_exit_list_len > 0) { |
|
368 for (int i = jsr_exit_list_len - 1; i >= 0; i--) { |
|
369 BasicBlock *jsrExit = jsr_exit_list->at(i); |
|
370 for (int i = ret_list_len - 1; i >= 0; i--) { |
|
371 jsrExit->add_normal_predecessor(ret_list->at(i)); |
|
372 } |
|
373 } |
|
374 } |
|
375 |
|
376 // Compute exception edges. |
|
377 for (int b=_block_count-1; b >= 0; b--) { |
|
378 BasicBlock *block = _block_list[b]; |
|
379 int block_start = block->start_bci(); |
|
380 int block_limit = block->limit_bci(); |
|
381 ciExceptionHandlerStream handlers(method()); |
|
382 for (; !handlers.is_done(); handlers.next()) { |
|
383 ciExceptionHandler* handler = handlers.handler(); |
|
384 int start = handler->start(); |
|
385 int limit = handler->limit(); |
|
386 int handler_bci = handler->handler_bci(); |
|
387 |
|
388 int intersect_start = MAX2(block_start, start); |
|
389 int intersect_limit = MIN2(block_limit, limit); |
|
390 if (intersect_start < intersect_limit) { |
|
391 // The catch range has a nonempty intersection with this |
|
392 // basic block. That means this basic block can be an |
|
393 // exceptional predecessor. |
|
394 _block_map->at(handler_bci)->add_exception_predecessor(block); |
|
395 |
|
396 if (handler->is_catch_all()) { |
|
397 // This is a catch-all block. |
|
398 if (intersect_start == block_start && intersect_limit == block_limit) { |
|
399 // The basic block is entirely contained in this catch-all block. |
|
400 // Skip the rest of the exception handlers -- they can never be |
|
401 // reached in execution. |
|
402 break; |
|
403 } |
|
404 } |
|
405 } |
|
406 } |
|
407 } |
|
408 } |
|
409 |
|
410 void MethodLiveness::init_gen_kill() { |
|
411 for (int i=_block_count-1; i >= 0; i--) { |
|
412 _block_list[i]->compute_gen_kill(method()); |
|
413 } |
|
414 } |
|
415 |
|
416 void MethodLiveness::propagate_liveness() { |
|
417 int num_blocks = _block_count; |
|
418 BasicBlock *block; |
|
419 |
|
420 // We start our work list off with all blocks in it. |
|
421 // Alternately, we could start off the work list with the list of all |
|
422 // blocks which could exit the method directly, along with one block |
|
423 // from any infinite loop. If this matters, it can be changed. It |
|
424 // may not be clear from looking at the code, but the order of the |
|
425 // workList will be the opposite of the creation order of the basic |
|
426 // blocks, which should be decent for quick convergence (with the |
|
427 // possible exception of exception handlers, which are all created |
|
428 // early). |
|
429 _work_list = NULL; |
|
430 for (int i = 0; i < num_blocks; i++) { |
|
431 block = _block_list[i]; |
|
432 block->set_next(_work_list); |
|
433 block->set_on_work_list(true); |
|
434 _work_list = block; |
|
435 } |
|
436 |
|
437 |
|
438 while ((block = work_list_get()) != NULL) { |
|
439 block->propagate(this); |
|
440 NOT_PRODUCT(_total_visits++;) |
|
441 } |
|
442 } |
|
443 |
|
444 void MethodLiveness::work_list_add(BasicBlock *block) { |
|
445 if (!block->on_work_list()) { |
|
446 block->set_next(_work_list); |
|
447 block->set_on_work_list(true); |
|
448 _work_list = block; |
|
449 } |
|
450 } |
|
451 |
|
452 MethodLiveness::BasicBlock *MethodLiveness::work_list_get() { |
|
453 BasicBlock *block = _work_list; |
|
454 if (block != NULL) { |
|
455 block->set_on_work_list(false); |
|
456 _work_list = block->next(); |
|
457 } |
|
458 return block; |
|
459 } |
|
460 |
|
461 |
|
462 MethodLivenessResult MethodLiveness::get_liveness_at(int entry_bci) { |
|
463 int bci = entry_bci; |
|
464 bool is_entry = false; |
|
465 if (entry_bci == InvocationEntryBci) { |
|
466 is_entry = true; |
|
467 bci = 0; |
|
468 } |
|
469 |
|
470 MethodLivenessResult answer(NULL,0); |
|
471 |
|
472 if (_block_count > 0) { |
|
473 if (TimeLivenessAnalysis) _time_total.start(); |
|
474 if (TimeLivenessAnalysis) _time_query.start(); |
|
475 |
|
476 assert( 0 <= bci && bci < method()->code_size(), "bci out of range" ); |
|
477 BasicBlock *block = _block_map->at(bci); |
|
478 // We may not be at the block start, so search backwards to find the block |
|
479 // containing bci. |
|
480 int t = bci; |
|
481 while (block == NULL && t > 0) { |
|
482 block = _block_map->at(--t); |
|
483 } |
|
484 assert( block != NULL, "invalid bytecode index; must be instruction index" ); |
|
485 assert(bci >= block->start_bci() && bci < block->limit_bci(), "block must contain bci."); |
|
486 |
|
487 answer = block->get_liveness_at(method(), bci); |
|
488 |
|
489 if (is_entry && method()->is_synchronized() && !method()->is_static()) { |
|
490 // Synchronized methods use the receiver once on entry. |
|
491 answer.at_put(0, true); |
|
492 } |
|
493 |
|
494 #ifndef PRODUCT |
|
495 if (TraceLivenessQuery) { |
|
496 tty->print("Liveness query of "); |
|
497 method()->print_short_name(); |
|
498 tty->print(" @ %d : result is ", bci); |
|
499 answer.print_on(tty); |
|
500 } |
|
501 |
|
502 if (TimeLivenessAnalysis) _time_query.stop(); |
|
503 if (TimeLivenessAnalysis) _time_total.stop(); |
|
504 #endif |
|
505 } |
|
506 |
|
507 #ifndef PRODUCT |
|
508 if (TimeLivenessAnalysis) { |
|
509 // Collect statistics. |
|
510 _total_locals_queried += _bit_map_size_bits; |
|
511 BitCounter counter; |
|
512 answer.iterate(&counter); |
|
513 _total_live_locals_queried += counter.count(); |
|
514 } |
|
515 #endif |
|
516 |
|
517 return answer; |
|
518 } |
|
519 |
|
520 |
|
521 #ifndef PRODUCT |
|
522 |
|
523 void MethodLiveness::print_times() { |
|
524 tty->print_cr ("Accumulated liveness analysis times/statistics:"); |
|
525 tty->print_cr ("-----------------------------------------------"); |
|
526 tty->print_cr (" Total : %3.3f sec.", _time_total.seconds()); |
|
527 tty->print_cr (" Build graph : %3.3f sec. (%2.2f%%)", _time_build_graph.seconds(), |
|
528 _time_build_graph.seconds() * 100 / _time_total.seconds()); |
|
529 tty->print_cr (" Gen / Kill : %3.3f sec. (%2.2f%%)", _time_gen_kill.seconds(), |
|
530 _time_gen_kill.seconds() * 100 / _time_total.seconds()); |
|
531 tty->print_cr (" Dataflow : %3.3f sec. (%2.2f%%)", _time_flow.seconds(), |
|
532 _time_flow.seconds() * 100 / _time_total.seconds()); |
|
533 tty->print_cr (" Query : %3.3f sec. (%2.2f%%)", _time_query.seconds(), |
|
534 _time_query.seconds() * 100 / _time_total.seconds()); |
|
535 tty->print_cr (" #bytes : %8d (%3.0f bytes per sec)", |
|
536 _total_bytes, |
|
537 _total_bytes / _time_total.seconds()); |
|
538 tty->print_cr (" #methods : %8d (%3.0f methods per sec)", |
|
539 _total_methods, |
|
540 _total_methods / _time_total.seconds()); |
|
541 tty->print_cr (" avg locals : %3.3f max locals : %3d", |
|
542 (float)_total_method_locals / _total_methods, |
|
543 _max_method_locals); |
|
544 tty->print_cr (" avg blocks : %3.3f max blocks : %3d", |
|
545 (float)_total_blocks / _total_methods, |
|
546 _max_method_blocks); |
|
547 tty->print_cr (" avg bytes : %3.3f", |
|
548 (float)_total_bytes / _total_methods); |
|
549 tty->print_cr (" #blocks : %8d", |
|
550 _total_blocks); |
|
551 tty->print_cr (" avg normal predecessors : %3.3f max normal predecessors : %3d", |
|
552 (float)_total_edges / _total_blocks, |
|
553 _max_block_edges); |
|
554 tty->print_cr (" avg exception predecessors : %3.3f max exception predecessors : %3d", |
|
555 (float)_total_exc_edges / _total_blocks, |
|
556 _max_block_exc_edges); |
|
557 tty->print_cr (" avg visits : %3.3f", |
|
558 (float)_total_visits / _total_blocks); |
|
559 tty->print_cr (" #locals queried : %8d #live : %8d %%live : %2.2f%%", |
|
560 _total_locals_queried, |
|
561 _total_live_locals_queried, |
|
562 100.0 * _total_live_locals_queried / _total_locals_queried); |
|
563 } |
|
564 |
|
565 #endif |
|
566 |
|
567 |
|
568 MethodLiveness::BasicBlock::BasicBlock(MethodLiveness *analyzer, int start, int limit) : |
|
569 _gen((uintptr_t*)analyzer->arena()->Amalloc(BytesPerWord * analyzer->bit_map_size_words()), |
|
570 analyzer->bit_map_size_bits()), |
|
571 _kill((uintptr_t*)analyzer->arena()->Amalloc(BytesPerWord * analyzer->bit_map_size_words()), |
|
572 analyzer->bit_map_size_bits()), |
|
573 _entry((uintptr_t*)analyzer->arena()->Amalloc(BytesPerWord * analyzer->bit_map_size_words()), |
|
574 analyzer->bit_map_size_bits()), |
|
575 _normal_exit((uintptr_t*)analyzer->arena()->Amalloc(BytesPerWord * analyzer->bit_map_size_words()), |
|
576 analyzer->bit_map_size_bits()), |
|
577 _exception_exit((uintptr_t*)analyzer->arena()->Amalloc(BytesPerWord * analyzer->bit_map_size_words()), |
|
578 analyzer->bit_map_size_bits()), |
|
579 _last_bci(-1) { |
|
580 _analyzer = analyzer; |
|
581 _start_bci = start; |
|
582 _limit_bci = limit; |
|
583 _normal_predecessors = |
|
584 new (analyzer->arena()) GrowableArray<MethodLiveness::BasicBlock*>(analyzer->arena(), 5, 0, NULL); |
|
585 _exception_predecessors = |
|
586 new (analyzer->arena()) GrowableArray<MethodLiveness::BasicBlock*>(analyzer->arena(), 5, 0, NULL); |
|
587 _normal_exit.clear(); |
|
588 _exception_exit.clear(); |
|
589 _entry.clear(); |
|
590 |
|
591 // this initialization is not strictly necessary. |
|
592 // _gen and _kill are cleared at the beginning of compute_gen_kill_range() |
|
593 _gen.clear(); |
|
594 _kill.clear(); |
|
595 } |
|
596 |
|
597 |
|
598 |
|
599 MethodLiveness::BasicBlock *MethodLiveness::BasicBlock::split(int split_bci) { |
|
600 int start = _start_bci; |
|
601 int limit = _limit_bci; |
|
602 |
|
603 if (TraceLivenessGen) { |
|
604 tty->print_cr(" ** Splitting block (%d,%d) at %d", start, limit, split_bci); |
|
605 } |
|
606 |
|
607 GrowableArray<BasicBlock*>* save_predecessors = _normal_predecessors; |
|
608 |
|
609 assert (start < split_bci && split_bci < limit, "improper split"); |
|
610 |
|
611 // Make a new block to cover the first half of the range. |
|
612 BasicBlock *first_half = new (_analyzer->arena()) BasicBlock(_analyzer, start, split_bci); |
|
613 |
|
614 // Assign correct values to the second half (this) |
|
615 _normal_predecessors = first_half->_normal_predecessors; |
|
616 _start_bci = split_bci; |
|
617 add_normal_predecessor(first_half); |
|
618 |
|
619 // Assign correct predecessors to the new first half |
|
620 first_half->_normal_predecessors = save_predecessors; |
|
621 |
|
622 return first_half; |
|
623 } |
|
624 |
|
625 void MethodLiveness::BasicBlock::compute_gen_kill(ciMethod* method) { |
|
626 ciBytecodeStream bytes(method); |
|
627 bytes.reset_to_bci(start_bci()); |
|
628 bytes.set_max_bci(limit_bci()); |
|
629 compute_gen_kill_range(&bytes); |
|
630 |
|
631 } |
|
632 |
|
633 void MethodLiveness::BasicBlock::compute_gen_kill_range(ciBytecodeStream *bytes) { |
|
634 _gen.clear(); |
|
635 _kill.clear(); |
|
636 |
|
637 while (bytes->next() != ciBytecodeStream::EOBC()) { |
|
638 compute_gen_kill_single(bytes); |
|
639 } |
|
640 } |
|
641 |
|
642 void MethodLiveness::BasicBlock::compute_gen_kill_single(ciBytecodeStream *instruction) { |
|
643 int localNum; |
|
644 |
|
645 // We prohibit _gen and _kill from having locals in common. If we |
|
646 // know that one is definitely going to be applied before the other, |
|
647 // we could save some computation time by relaxing this prohibition. |
|
648 |
|
649 switch (instruction->cur_bc()) { |
|
650 case Bytecodes::_nop: |
|
651 case Bytecodes::_goto: |
|
652 case Bytecodes::_goto_w: |
|
653 case Bytecodes::_aconst_null: |
|
654 case Bytecodes::_new: |
|
655 case Bytecodes::_iconst_m1: |
|
656 case Bytecodes::_iconst_0: |
|
657 case Bytecodes::_iconst_1: |
|
658 case Bytecodes::_iconst_2: |
|
659 case Bytecodes::_iconst_3: |
|
660 case Bytecodes::_iconst_4: |
|
661 case Bytecodes::_iconst_5: |
|
662 case Bytecodes::_fconst_0: |
|
663 case Bytecodes::_fconst_1: |
|
664 case Bytecodes::_fconst_2: |
|
665 case Bytecodes::_bipush: |
|
666 case Bytecodes::_sipush: |
|
667 case Bytecodes::_lconst_0: |
|
668 case Bytecodes::_lconst_1: |
|
669 case Bytecodes::_dconst_0: |
|
670 case Bytecodes::_dconst_1: |
|
671 case Bytecodes::_ldc2_w: |
|
672 case Bytecodes::_ldc: |
|
673 case Bytecodes::_ldc_w: |
|
674 case Bytecodes::_iaload: |
|
675 case Bytecodes::_faload: |
|
676 case Bytecodes::_baload: |
|
677 case Bytecodes::_caload: |
|
678 case Bytecodes::_saload: |
|
679 case Bytecodes::_laload: |
|
680 case Bytecodes::_daload: |
|
681 case Bytecodes::_aaload: |
|
682 case Bytecodes::_iastore: |
|
683 case Bytecodes::_fastore: |
|
684 case Bytecodes::_bastore: |
|
685 case Bytecodes::_castore: |
|
686 case Bytecodes::_sastore: |
|
687 case Bytecodes::_lastore: |
|
688 case Bytecodes::_dastore: |
|
689 case Bytecodes::_aastore: |
|
690 case Bytecodes::_pop: |
|
691 case Bytecodes::_pop2: |
|
692 case Bytecodes::_dup: |
|
693 case Bytecodes::_dup_x1: |
|
694 case Bytecodes::_dup_x2: |
|
695 case Bytecodes::_dup2: |
|
696 case Bytecodes::_dup2_x1: |
|
697 case Bytecodes::_dup2_x2: |
|
698 case Bytecodes::_swap: |
|
699 case Bytecodes::_iadd: |
|
700 case Bytecodes::_fadd: |
|
701 case Bytecodes::_isub: |
|
702 case Bytecodes::_fsub: |
|
703 case Bytecodes::_imul: |
|
704 case Bytecodes::_fmul: |
|
705 case Bytecodes::_idiv: |
|
706 case Bytecodes::_fdiv: |
|
707 case Bytecodes::_irem: |
|
708 case Bytecodes::_frem: |
|
709 case Bytecodes::_ishl: |
|
710 case Bytecodes::_ishr: |
|
711 case Bytecodes::_iushr: |
|
712 case Bytecodes::_iand: |
|
713 case Bytecodes::_ior: |
|
714 case Bytecodes::_ixor: |
|
715 case Bytecodes::_l2f: |
|
716 case Bytecodes::_l2i: |
|
717 case Bytecodes::_d2f: |
|
718 case Bytecodes::_d2i: |
|
719 case Bytecodes::_fcmpl: |
|
720 case Bytecodes::_fcmpg: |
|
721 case Bytecodes::_ladd: |
|
722 case Bytecodes::_dadd: |
|
723 case Bytecodes::_lsub: |
|
724 case Bytecodes::_dsub: |
|
725 case Bytecodes::_lmul: |
|
726 case Bytecodes::_dmul: |
|
727 case Bytecodes::_ldiv: |
|
728 case Bytecodes::_ddiv: |
|
729 case Bytecodes::_lrem: |
|
730 case Bytecodes::_drem: |
|
731 case Bytecodes::_land: |
|
732 case Bytecodes::_lor: |
|
733 case Bytecodes::_lxor: |
|
734 case Bytecodes::_ineg: |
|
735 case Bytecodes::_fneg: |
|
736 case Bytecodes::_i2f: |
|
737 case Bytecodes::_f2i: |
|
738 case Bytecodes::_i2c: |
|
739 case Bytecodes::_i2s: |
|
740 case Bytecodes::_i2b: |
|
741 case Bytecodes::_lneg: |
|
742 case Bytecodes::_dneg: |
|
743 case Bytecodes::_l2d: |
|
744 case Bytecodes::_d2l: |
|
745 case Bytecodes::_lshl: |
|
746 case Bytecodes::_lshr: |
|
747 case Bytecodes::_lushr: |
|
748 case Bytecodes::_i2l: |
|
749 case Bytecodes::_i2d: |
|
750 case Bytecodes::_f2l: |
|
751 case Bytecodes::_f2d: |
|
752 case Bytecodes::_lcmp: |
|
753 case Bytecodes::_dcmpl: |
|
754 case Bytecodes::_dcmpg: |
|
755 case Bytecodes::_ifeq: |
|
756 case Bytecodes::_ifne: |
|
757 case Bytecodes::_iflt: |
|
758 case Bytecodes::_ifge: |
|
759 case Bytecodes::_ifgt: |
|
760 case Bytecodes::_ifle: |
|
761 case Bytecodes::_tableswitch: |
|
762 case Bytecodes::_ireturn: |
|
763 case Bytecodes::_freturn: |
|
764 case Bytecodes::_if_icmpeq: |
|
765 case Bytecodes::_if_icmpne: |
|
766 case Bytecodes::_if_icmplt: |
|
767 case Bytecodes::_if_icmpge: |
|
768 case Bytecodes::_if_icmpgt: |
|
769 case Bytecodes::_if_icmple: |
|
770 case Bytecodes::_lreturn: |
|
771 case Bytecodes::_dreturn: |
|
772 case Bytecodes::_if_acmpeq: |
|
773 case Bytecodes::_if_acmpne: |
|
774 case Bytecodes::_jsr: |
|
775 case Bytecodes::_jsr_w: |
|
776 case Bytecodes::_getstatic: |
|
777 case Bytecodes::_putstatic: |
|
778 case Bytecodes::_getfield: |
|
779 case Bytecodes::_putfield: |
|
780 case Bytecodes::_invokevirtual: |
|
781 case Bytecodes::_invokespecial: |
|
782 case Bytecodes::_invokestatic: |
|
783 case Bytecodes::_invokeinterface: |
|
784 case Bytecodes::_newarray: |
|
785 case Bytecodes::_anewarray: |
|
786 case Bytecodes::_checkcast: |
|
787 case Bytecodes::_arraylength: |
|
788 case Bytecodes::_instanceof: |
|
789 case Bytecodes::_athrow: |
|
790 case Bytecodes::_areturn: |
|
791 case Bytecodes::_monitorenter: |
|
792 case Bytecodes::_monitorexit: |
|
793 case Bytecodes::_ifnull: |
|
794 case Bytecodes::_ifnonnull: |
|
795 case Bytecodes::_multianewarray: |
|
796 case Bytecodes::_lookupswitch: |
|
797 // These bytecodes have no effect on the method's locals. |
|
798 break; |
|
799 |
|
800 case Bytecodes::_return: |
|
801 if (instruction->method()->intrinsic_id() == vmIntrinsics::_Object_init) { |
|
802 // return from Object.init implicitly registers a finalizer |
|
803 // for the receiver if needed, so keep it alive. |
|
804 load_one(0); |
|
805 } |
|
806 break; |
|
807 |
|
808 |
|
809 case Bytecodes::_lload: |
|
810 case Bytecodes::_dload: |
|
811 load_two(instruction->get_index()); |
|
812 break; |
|
813 |
|
814 case Bytecodes::_lload_0: |
|
815 case Bytecodes::_dload_0: |
|
816 load_two(0); |
|
817 break; |
|
818 |
|
819 case Bytecodes::_lload_1: |
|
820 case Bytecodes::_dload_1: |
|
821 load_two(1); |
|
822 break; |
|
823 |
|
824 case Bytecodes::_lload_2: |
|
825 case Bytecodes::_dload_2: |
|
826 load_two(2); |
|
827 break; |
|
828 |
|
829 case Bytecodes::_lload_3: |
|
830 case Bytecodes::_dload_3: |
|
831 load_two(3); |
|
832 break; |
|
833 |
|
834 case Bytecodes::_iload: |
|
835 case Bytecodes::_iinc: |
|
836 case Bytecodes::_fload: |
|
837 case Bytecodes::_aload: |
|
838 case Bytecodes::_ret: |
|
839 load_one(instruction->get_index()); |
|
840 break; |
|
841 |
|
842 case Bytecodes::_iload_0: |
|
843 case Bytecodes::_fload_0: |
|
844 case Bytecodes::_aload_0: |
|
845 load_one(0); |
|
846 break; |
|
847 |
|
848 case Bytecodes::_iload_1: |
|
849 case Bytecodes::_fload_1: |
|
850 case Bytecodes::_aload_1: |
|
851 load_one(1); |
|
852 break; |
|
853 |
|
854 case Bytecodes::_iload_2: |
|
855 case Bytecodes::_fload_2: |
|
856 case Bytecodes::_aload_2: |
|
857 load_one(2); |
|
858 break; |
|
859 |
|
860 case Bytecodes::_iload_3: |
|
861 case Bytecodes::_fload_3: |
|
862 case Bytecodes::_aload_3: |
|
863 load_one(3); |
|
864 break; |
|
865 |
|
866 case Bytecodes::_lstore: |
|
867 case Bytecodes::_dstore: |
|
868 store_two(localNum = instruction->get_index()); |
|
869 break; |
|
870 |
|
871 case Bytecodes::_lstore_0: |
|
872 case Bytecodes::_dstore_0: |
|
873 store_two(0); |
|
874 break; |
|
875 |
|
876 case Bytecodes::_lstore_1: |
|
877 case Bytecodes::_dstore_1: |
|
878 store_two(1); |
|
879 break; |
|
880 |
|
881 case Bytecodes::_lstore_2: |
|
882 case Bytecodes::_dstore_2: |
|
883 store_two(2); |
|
884 break; |
|
885 |
|
886 case Bytecodes::_lstore_3: |
|
887 case Bytecodes::_dstore_3: |
|
888 store_two(3); |
|
889 break; |
|
890 |
|
891 case Bytecodes::_istore: |
|
892 case Bytecodes::_fstore: |
|
893 case Bytecodes::_astore: |
|
894 store_one(instruction->get_index()); |
|
895 break; |
|
896 |
|
897 case Bytecodes::_istore_0: |
|
898 case Bytecodes::_fstore_0: |
|
899 case Bytecodes::_astore_0: |
|
900 store_one(0); |
|
901 break; |
|
902 |
|
903 case Bytecodes::_istore_1: |
|
904 case Bytecodes::_fstore_1: |
|
905 case Bytecodes::_astore_1: |
|
906 store_one(1); |
|
907 break; |
|
908 |
|
909 case Bytecodes::_istore_2: |
|
910 case Bytecodes::_fstore_2: |
|
911 case Bytecodes::_astore_2: |
|
912 store_one(2); |
|
913 break; |
|
914 |
|
915 case Bytecodes::_istore_3: |
|
916 case Bytecodes::_fstore_3: |
|
917 case Bytecodes::_astore_3: |
|
918 store_one(3); |
|
919 break; |
|
920 |
|
921 case Bytecodes::_wide: |
|
922 fatal("Iterator should skip this bytecode"); |
|
923 break; |
|
924 |
|
925 default: |
|
926 tty->print("unexpected opcode: %d\n", instruction->cur_bc()); |
|
927 ShouldNotReachHere(); |
|
928 break; |
|
929 } |
|
930 } |
|
931 |
|
932 void MethodLiveness::BasicBlock::load_two(int local) { |
|
933 load_one(local); |
|
934 load_one(local+1); |
|
935 } |
|
936 |
|
937 void MethodLiveness::BasicBlock::load_one(int local) { |
|
938 if (!_kill.at(local)) { |
|
939 _gen.at_put(local, true); |
|
940 } |
|
941 } |
|
942 |
|
943 void MethodLiveness::BasicBlock::store_two(int local) { |
|
944 store_one(local); |
|
945 store_one(local+1); |
|
946 } |
|
947 |
|
948 void MethodLiveness::BasicBlock::store_one(int local) { |
|
949 if (!_gen.at(local)) { |
|
950 _kill.at_put(local, true); |
|
951 } |
|
952 } |
|
953 |
|
954 void MethodLiveness::BasicBlock::propagate(MethodLiveness *ml) { |
|
955 // These set operations could be combined for efficiency if the |
|
956 // performance of this analysis becomes an issue. |
|
957 _entry.set_union(_normal_exit); |
|
958 _entry.set_difference(_kill); |
|
959 _entry.set_union(_gen); |
|
960 |
|
961 // Note that we merge information from our exceptional successors |
|
962 // just once, rather than at individual bytecodes. |
|
963 _entry.set_union(_exception_exit); |
|
964 |
|
965 if (TraceLivenessGen) { |
|
966 tty->print_cr(" ** Visiting block at %d **", start_bci()); |
|
967 print_on(tty); |
|
968 } |
|
969 |
|
970 int i; |
|
971 for (i=_normal_predecessors->length()-1; i>=0; i--) { |
|
972 BasicBlock *block = _normal_predecessors->at(i); |
|
973 if (block->merge_normal(_entry)) { |
|
974 ml->work_list_add(block); |
|
975 } |
|
976 } |
|
977 for (i=_exception_predecessors->length()-1; i>=0; i--) { |
|
978 BasicBlock *block = _exception_predecessors->at(i); |
|
979 if (block->merge_exception(_entry)) { |
|
980 ml->work_list_add(block); |
|
981 } |
|
982 } |
|
983 } |
|
984 |
|
985 bool MethodLiveness::BasicBlock::merge_normal(BitMap other) { |
|
986 return _normal_exit.set_union_with_result(other); |
|
987 } |
|
988 |
|
989 bool MethodLiveness::BasicBlock::merge_exception(BitMap other) { |
|
990 return _exception_exit.set_union_with_result(other); |
|
991 } |
|
992 |
|
993 MethodLivenessResult MethodLiveness::BasicBlock::get_liveness_at(ciMethod* method, int bci) { |
|
994 MethodLivenessResult answer(NEW_RESOURCE_ARRAY(uintptr_t, _analyzer->bit_map_size_words()), |
|
995 _analyzer->bit_map_size_bits()); |
|
996 answer.set_is_valid(); |
|
997 |
|
998 #ifndef ASSERT |
|
999 if (bci == start_bci()) { |
|
1000 answer.set_from(_entry); |
|
1001 return answer; |
|
1002 } |
|
1003 #endif |
|
1004 |
|
1005 #ifdef ASSERT |
|
1006 ResourceMark rm; |
|
1007 BitMap g(_gen.size()); g.set_from(_gen); |
|
1008 BitMap k(_kill.size()); k.set_from(_kill); |
|
1009 #endif |
|
1010 if (_last_bci != bci || trueInDebug) { |
|
1011 ciBytecodeStream bytes(method); |
|
1012 bytes.reset_to_bci(bci); |
|
1013 bytes.set_max_bci(limit_bci()); |
|
1014 compute_gen_kill_range(&bytes); |
|
1015 assert(_last_bci != bci || |
|
1016 (g.is_same(_gen) && k.is_same(_kill)), "cached computation is incorrect"); |
|
1017 _last_bci = bci; |
|
1018 } |
|
1019 |
|
1020 answer.clear(); |
|
1021 answer.set_union(_normal_exit); |
|
1022 answer.set_difference(_kill); |
|
1023 answer.set_union(_gen); |
|
1024 answer.set_union(_exception_exit); |
|
1025 |
|
1026 #ifdef ASSERT |
|
1027 if (bci == start_bci()) { |
|
1028 assert(answer.is_same(_entry), "optimized answer must be accurate"); |
|
1029 } |
|
1030 #endif |
|
1031 |
|
1032 return answer; |
|
1033 } |
|
1034 |
|
1035 #ifndef PRODUCT |
|
1036 |
|
1037 void MethodLiveness::BasicBlock::print_on(outputStream *os) const { |
|
1038 os->print_cr("==================================================================="); |
|
1039 os->print_cr(" Block start: %4d, limit: %4d", _start_bci, _limit_bci); |
|
1040 os->print (" Normal predecessors (%2d) @", _normal_predecessors->length()); |
|
1041 int i; |
|
1042 for (i=0; i < _normal_predecessors->length(); i++) { |
|
1043 os->print(" %4d", _normal_predecessors->at(i)->start_bci()); |
|
1044 } |
|
1045 os->cr(); |
|
1046 os->print (" Exceptional predecessors (%2d) @", _exception_predecessors->length()); |
|
1047 for (i=0; i < _exception_predecessors->length(); i++) { |
|
1048 os->print(" %4d", _exception_predecessors->at(i)->start_bci()); |
|
1049 } |
|
1050 os->cr(); |
|
1051 os->print (" Normal Exit : "); |
|
1052 _normal_exit.print_on(os); |
|
1053 os->print (" Gen : "); |
|
1054 _gen.print_on(os); |
|
1055 os->print (" Kill : "); |
|
1056 _kill.print_on(os); |
|
1057 os->print (" Exception Exit: "); |
|
1058 _exception_exit.print_on(os); |
|
1059 os->print (" Entry : "); |
|
1060 _entry.print_on(os); |
|
1061 } |
|
1062 |
|
1063 #endif // PRODUCT |