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