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