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