1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/compiler/methodLiveness.cpp Wed Apr 27 01:25:04 2016 +0800
1.3 @@ -0,0 +1,1072 @@
1.4 +/*
1.5 + * Copyright (c) 1998, 2014, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.23 + * or visit www.oracle.com if you need additional information or have any
1.24 + * questions.
1.25 + *
1.26 + */
1.27 +
1.28 +#include "precompiled.hpp"
1.29 +#include "ci/ciMethod.hpp"
1.30 +#include "ci/ciMethodBlocks.hpp"
1.31 +#include "ci/ciStreams.hpp"
1.32 +#include "compiler/methodLiveness.hpp"
1.33 +#include "interpreter/bytecode.hpp"
1.34 +#include "interpreter/bytecodes.hpp"
1.35 +#include "memory/allocation.inline.hpp"
1.36 +#include "utilities/bitMap.inline.hpp"
1.37 +
1.38 +PRAGMA_FORMAT_MUTE_WARNINGS_FOR_GCC
1.39 +
1.40 +// The MethodLiveness class performs a simple liveness analysis on a method
1.41 +// in order to decide which locals are live (that is, will be used again) at
1.42 +// a particular bytecode index (bci).
1.43 +//
1.44 +// The algorithm goes:
1.45 +//
1.46 +// 1. Break the method into a set of basic blocks. For each basic block we
1.47 +// also keep track of its set of predecessors through normal control flow
1.48 +// and predecessors through exceptional control flow.
1.49 +//
1.50 +// 2. For each basic block, compute two sets, gen (the set of values used before
1.51 +// they are defined) and kill (the set of values defined before they are used)
1.52 +// in the basic block. A basic block "needs" the locals in its gen set to
1.53 +// perform its computation. A basic block "provides" values for the locals in
1.54 +// its kill set, allowing a need from a successor to be ignored.
1.55 +//
1.56 +// 3. Liveness information (the set of locals which are needed) is pushed backwards through
1.57 +// the program, from blocks to their predecessors. We compute and store liveness
1.58 +// information for the normal/exceptional exit paths for each basic block. When
1.59 +// this process reaches a fixed point, we are done.
1.60 +//
1.61 +// 4. When we are asked about the liveness at a particular bci with a basic block, we
1.62 +// compute gen/kill sets which represent execution from that bci to the exit of
1.63 +// its blocks. We then compose this range gen/kill information with the normal
1.64 +// and exceptional exit information for the block to produce liveness information
1.65 +// at that bci.
1.66 +//
1.67 +// The algorithm is approximate in many respects. Notably:
1.68 +//
1.69 +// 1. We do not do the analysis necessary to match jsr's with the appropriate ret.
1.70 +// Instead we make the conservative assumption that any ret can return to any
1.71 +// jsr return site.
1.72 +// 2. Instead of computing the effects of exceptions at every instruction, we
1.73 +// summarize the effects of all exceptional continuations from the block as
1.74 +// a single set (_exception_exit), losing some information but simplifying the
1.75 +// analysis.
1.76 +
1.77 +
1.78 +//--------------------------------------------------------------------------
1.79 +// The BitCounter class is used for counting the number of bits set in
1.80 +// some BitMap. It is only used when collecting liveness statistics.
1.81 +
1.82 +#ifndef PRODUCT
1.83 +
1.84 +class BitCounter: public BitMapClosure {
1.85 + private:
1.86 + int _count;
1.87 + public:
1.88 + BitCounter() : _count(0) {}
1.89 +
1.90 + // Callback when bit in map is set
1.91 + virtual bool do_bit(size_t offset) {
1.92 + _count++;
1.93 + return true;
1.94 + }
1.95 +
1.96 + int count() {
1.97 + return _count;
1.98 + }
1.99 +};
1.100 +
1.101 +
1.102 +//--------------------------------------------------------------------------
1.103 +
1.104 +
1.105 +// Counts
1.106 +long MethodLiveness::_total_bytes = 0;
1.107 +int MethodLiveness::_total_methods = 0;
1.108 +
1.109 +long MethodLiveness::_total_blocks = 0;
1.110 +int MethodLiveness::_max_method_blocks = 0;
1.111 +
1.112 +long MethodLiveness::_total_edges = 0;
1.113 +int MethodLiveness::_max_block_edges = 0;
1.114 +
1.115 +long MethodLiveness::_total_exc_edges = 0;
1.116 +int MethodLiveness::_max_block_exc_edges = 0;
1.117 +
1.118 +long MethodLiveness::_total_method_locals = 0;
1.119 +int MethodLiveness::_max_method_locals = 0;
1.120 +
1.121 +long MethodLiveness::_total_locals_queried = 0;
1.122 +long MethodLiveness::_total_live_locals_queried = 0;
1.123 +
1.124 +long MethodLiveness::_total_visits = 0;
1.125 +
1.126 +#endif
1.127 +
1.128 +// Timers
1.129 +elapsedTimer MethodLiveness::_time_build_graph;
1.130 +elapsedTimer MethodLiveness::_time_gen_kill;
1.131 +elapsedTimer MethodLiveness::_time_flow;
1.132 +elapsedTimer MethodLiveness::_time_query;
1.133 +elapsedTimer MethodLiveness::_time_total;
1.134 +
1.135 +MethodLiveness::MethodLiveness(Arena* arena, ciMethod* method)
1.136 +#ifdef COMPILER1
1.137 + : _bci_block_start((uintptr_t*)arena->Amalloc((method->code_size() >> LogBitsPerByte) + 1), method->code_size())
1.138 +#endif
1.139 +{
1.140 + _arena = arena;
1.141 + _method = method;
1.142 + _bit_map_size_bits = method->max_locals();
1.143 + _bit_map_size_words = (_bit_map_size_bits / sizeof(unsigned int)) + 1;
1.144 +
1.145 +#ifdef COMPILER1
1.146 + _bci_block_start.clear();
1.147 +#endif
1.148 +}
1.149 +
1.150 +void MethodLiveness::compute_liveness() {
1.151 +#ifndef PRODUCT
1.152 + if (TraceLivenessGen) {
1.153 + tty->print_cr("################################################################");
1.154 + tty->print("# Computing liveness information for ");
1.155 + method()->print_short_name();
1.156 + }
1.157 +
1.158 + if (TimeLivenessAnalysis) _time_total.start();
1.159 +#endif
1.160 +
1.161 + {
1.162 + TraceTime buildGraph(NULL, &_time_build_graph, TimeLivenessAnalysis);
1.163 + init_basic_blocks();
1.164 + }
1.165 + {
1.166 + TraceTime genKill(NULL, &_time_gen_kill, TimeLivenessAnalysis);
1.167 + init_gen_kill();
1.168 + }
1.169 + {
1.170 + TraceTime flow(NULL, &_time_flow, TimeLivenessAnalysis);
1.171 + propagate_liveness();
1.172 + }
1.173 +
1.174 +#ifndef PRODUCT
1.175 + if (TimeLivenessAnalysis) _time_total.stop();
1.176 +
1.177 + if (TimeLivenessAnalysis) {
1.178 + // Collect statistics
1.179 + _total_bytes += method()->code_size();
1.180 + _total_methods++;
1.181 +
1.182 + int num_blocks = _block_count;
1.183 + _total_blocks += num_blocks;
1.184 + _max_method_blocks = MAX2(num_blocks,_max_method_blocks);
1.185 +
1.186 + for (int i=0; i<num_blocks; i++) {
1.187 + BasicBlock *block = _block_list[i];
1.188 +
1.189 + int numEdges = block->_normal_predecessors->length();
1.190 + int numExcEdges = block->_exception_predecessors->length();
1.191 +
1.192 + _total_edges += numEdges;
1.193 + _total_exc_edges += numExcEdges;
1.194 + _max_block_edges = MAX2(numEdges,_max_block_edges);
1.195 + _max_block_exc_edges = MAX2(numExcEdges,_max_block_exc_edges);
1.196 + }
1.197 +
1.198 + int numLocals = _bit_map_size_bits;
1.199 + _total_method_locals += numLocals;
1.200 + _max_method_locals = MAX2(numLocals,_max_method_locals);
1.201 + }
1.202 +#endif
1.203 +}
1.204 +
1.205 +
1.206 +void MethodLiveness::init_basic_blocks() {
1.207 + bool bailout = false;
1.208 +
1.209 + int method_len = method()->code_size();
1.210 + ciMethodBlocks *mblocks = method()->get_method_blocks();
1.211 +
1.212 + // Create an array to store the bci->BasicBlock mapping.
1.213 + _block_map = new (arena()) GrowableArray<BasicBlock*>(arena(), method_len, method_len, NULL);
1.214 +
1.215 + _block_count = mblocks->num_blocks();
1.216 + _block_list = (BasicBlock **) arena()->Amalloc(sizeof(BasicBlock *) * _block_count);
1.217 +
1.218 + // Used for patching up jsr/ret control flow.
1.219 + GrowableArray<BasicBlock*>* jsr_exit_list = new GrowableArray<BasicBlock*>(5);
1.220 + GrowableArray<BasicBlock*>* ret_list = new GrowableArray<BasicBlock*>(5);
1.221 +
1.222 + // generate our block list from ciMethodBlocks
1.223 + for (int blk = 0; blk < _block_count; blk++) {
1.224 + ciBlock *cib = mblocks->block(blk);
1.225 + int start_bci = cib->start_bci();
1.226 + _block_list[blk] = new (arena()) BasicBlock(this, start_bci, cib->limit_bci());
1.227 + _block_map->at_put(start_bci, _block_list[blk]);
1.228 +#ifdef COMPILER1
1.229 + // mark all bcis where a new basic block starts
1.230 + _bci_block_start.set_bit(start_bci);
1.231 +#endif // COMPILER1
1.232 + }
1.233 + // fill in the predecessors of blocks
1.234 + ciBytecodeStream bytes(method());
1.235 +
1.236 + for (int blk = 0; blk < _block_count; blk++) {
1.237 + BasicBlock *current_block = _block_list[blk];
1.238 + int bci = mblocks->block(blk)->control_bci();
1.239 +
1.240 + if (bci == ciBlock::fall_through_bci) {
1.241 + int limit = current_block->limit_bci();
1.242 + if (limit < method_len) {
1.243 + BasicBlock *next = _block_map->at(limit);
1.244 + assert( next != NULL, "must be a block immediately following this one.");
1.245 + next->add_normal_predecessor(current_block);
1.246 + }
1.247 + continue;
1.248 + }
1.249 + bytes.reset_to_bci(bci);
1.250 + Bytecodes::Code code = bytes.next();
1.251 + BasicBlock *dest;
1.252 +
1.253 + // Now we need to interpret the instruction's effect
1.254 + // on control flow.
1.255 + assert (current_block != NULL, "we must have a current block");
1.256 + switch (code) {
1.257 + case Bytecodes::_ifeq:
1.258 + case Bytecodes::_ifne:
1.259 + case Bytecodes::_iflt:
1.260 + case Bytecodes::_ifge:
1.261 + case Bytecodes::_ifgt:
1.262 + case Bytecodes::_ifle:
1.263 + case Bytecodes::_if_icmpeq:
1.264 + case Bytecodes::_if_icmpne:
1.265 + case Bytecodes::_if_icmplt:
1.266 + case Bytecodes::_if_icmpge:
1.267 + case Bytecodes::_if_icmpgt:
1.268 + case Bytecodes::_if_icmple:
1.269 + case Bytecodes::_if_acmpeq:
1.270 + case Bytecodes::_if_acmpne:
1.271 + case Bytecodes::_ifnull:
1.272 + case Bytecodes::_ifnonnull:
1.273 + // Two way branch. Set predecessors at each destination.
1.274 + dest = _block_map->at(bytes.next_bci());
1.275 + assert(dest != NULL, "must be a block immediately following this one.");
1.276 + dest->add_normal_predecessor(current_block);
1.277 +
1.278 + dest = _block_map->at(bytes.get_dest());
1.279 + assert(dest != NULL, "branch desination must start a block.");
1.280 + dest->add_normal_predecessor(current_block);
1.281 + break;
1.282 + case Bytecodes::_goto:
1.283 + dest = _block_map->at(bytes.get_dest());
1.284 + assert(dest != NULL, "branch desination must start a block.");
1.285 + dest->add_normal_predecessor(current_block);
1.286 + break;
1.287 + case Bytecodes::_goto_w:
1.288 + dest = _block_map->at(bytes.get_far_dest());
1.289 + assert(dest != NULL, "branch desination must start a block.");
1.290 + dest->add_normal_predecessor(current_block);
1.291 + break;
1.292 + case Bytecodes::_tableswitch:
1.293 + {
1.294 + Bytecode_tableswitch tableswitch(&bytes);
1.295 +
1.296 + int len = tableswitch.length();
1.297 +
1.298 + dest = _block_map->at(bci + tableswitch.default_offset());
1.299 + assert(dest != NULL, "branch desination must start a block.");
1.300 + dest->add_normal_predecessor(current_block);
1.301 + while (--len >= 0) {
1.302 + dest = _block_map->at(bci + tableswitch.dest_offset_at(len));
1.303 + assert(dest != NULL, "branch desination must start a block.");
1.304 + dest->add_normal_predecessor(current_block);
1.305 + }
1.306 + break;
1.307 + }
1.308 +
1.309 + case Bytecodes::_lookupswitch:
1.310 + {
1.311 + Bytecode_lookupswitch lookupswitch(&bytes);
1.312 +
1.313 + int npairs = lookupswitch.number_of_pairs();
1.314 +
1.315 + dest = _block_map->at(bci + lookupswitch.default_offset());
1.316 + assert(dest != NULL, "branch desination must start a block.");
1.317 + dest->add_normal_predecessor(current_block);
1.318 + while(--npairs >= 0) {
1.319 + LookupswitchPair pair = lookupswitch.pair_at(npairs);
1.320 + dest = _block_map->at( bci + pair.offset());
1.321 + assert(dest != NULL, "branch desination must start a block.");
1.322 + dest->add_normal_predecessor(current_block);
1.323 + }
1.324 + break;
1.325 + }
1.326 +
1.327 + case Bytecodes::_jsr:
1.328 + {
1.329 + assert(bytes.is_wide()==false, "sanity check");
1.330 + dest = _block_map->at(bytes.get_dest());
1.331 + assert(dest != NULL, "branch desination must start a block.");
1.332 + dest->add_normal_predecessor(current_block);
1.333 + BasicBlock *jsrExit = _block_map->at(current_block->limit_bci());
1.334 + assert(jsrExit != NULL, "jsr return bci must start a block.");
1.335 + jsr_exit_list->append(jsrExit);
1.336 + break;
1.337 + }
1.338 + case Bytecodes::_jsr_w:
1.339 + {
1.340 + dest = _block_map->at(bytes.get_far_dest());
1.341 + assert(dest != NULL, "branch desination must start a block.");
1.342 + dest->add_normal_predecessor(current_block);
1.343 + BasicBlock *jsrExit = _block_map->at(current_block->limit_bci());
1.344 + assert(jsrExit != NULL, "jsr return bci must start a block.");
1.345 + jsr_exit_list->append(jsrExit);
1.346 + break;
1.347 + }
1.348 +
1.349 + case Bytecodes::_wide:
1.350 + assert(false, "wide opcodes should not be seen here");
1.351 + break;
1.352 + case Bytecodes::_athrow:
1.353 + case Bytecodes::_ireturn:
1.354 + case Bytecodes::_lreturn:
1.355 + case Bytecodes::_freturn:
1.356 + case Bytecodes::_dreturn:
1.357 + case Bytecodes::_areturn:
1.358 + case Bytecodes::_return:
1.359 + // These opcodes are not the normal predecessors of any other opcodes.
1.360 + break;
1.361 + case Bytecodes::_ret:
1.362 + // We will patch up jsr/rets in a subsequent pass.
1.363 + ret_list->append(current_block);
1.364 + break;
1.365 + case Bytecodes::_breakpoint:
1.366 + // Bail out of there are breakpoints in here.
1.367 + bailout = true;
1.368 + break;
1.369 + default:
1.370 + // Do nothing.
1.371 + break;
1.372 + }
1.373 + }
1.374 + // Patch up the jsr/ret's. We conservatively assume that any ret
1.375 + // can return to any jsr site.
1.376 + int ret_list_len = ret_list->length();
1.377 + int jsr_exit_list_len = jsr_exit_list->length();
1.378 + if (ret_list_len > 0 && jsr_exit_list_len > 0) {
1.379 + for (int i = jsr_exit_list_len - 1; i >= 0; i--) {
1.380 + BasicBlock *jsrExit = jsr_exit_list->at(i);
1.381 + for (int i = ret_list_len - 1; i >= 0; i--) {
1.382 + jsrExit->add_normal_predecessor(ret_list->at(i));
1.383 + }
1.384 + }
1.385 + }
1.386 +
1.387 + // Compute exception edges.
1.388 + for (int b=_block_count-1; b >= 0; b--) {
1.389 + BasicBlock *block = _block_list[b];
1.390 + int block_start = block->start_bci();
1.391 + int block_limit = block->limit_bci();
1.392 + ciExceptionHandlerStream handlers(method());
1.393 + for (; !handlers.is_done(); handlers.next()) {
1.394 + ciExceptionHandler* handler = handlers.handler();
1.395 + int start = handler->start();
1.396 + int limit = handler->limit();
1.397 + int handler_bci = handler->handler_bci();
1.398 +
1.399 + int intersect_start = MAX2(block_start, start);
1.400 + int intersect_limit = MIN2(block_limit, limit);
1.401 + if (intersect_start < intersect_limit) {
1.402 + // The catch range has a nonempty intersection with this
1.403 + // basic block. That means this basic block can be an
1.404 + // exceptional predecessor.
1.405 + _block_map->at(handler_bci)->add_exception_predecessor(block);
1.406 +
1.407 + if (handler->is_catch_all()) {
1.408 + // This is a catch-all block.
1.409 + if (intersect_start == block_start && intersect_limit == block_limit) {
1.410 + // The basic block is entirely contained in this catch-all block.
1.411 + // Skip the rest of the exception handlers -- they can never be
1.412 + // reached in execution.
1.413 + break;
1.414 + }
1.415 + }
1.416 + }
1.417 + }
1.418 + }
1.419 +}
1.420 +
1.421 +void MethodLiveness::init_gen_kill() {
1.422 + for (int i=_block_count-1; i >= 0; i--) {
1.423 + _block_list[i]->compute_gen_kill(method());
1.424 + }
1.425 +}
1.426 +
1.427 +void MethodLiveness::propagate_liveness() {
1.428 + int num_blocks = _block_count;
1.429 + BasicBlock *block;
1.430 +
1.431 + // We start our work list off with all blocks in it.
1.432 + // Alternately, we could start off the work list with the list of all
1.433 + // blocks which could exit the method directly, along with one block
1.434 + // from any infinite loop. If this matters, it can be changed. It
1.435 + // may not be clear from looking at the code, but the order of the
1.436 + // workList will be the opposite of the creation order of the basic
1.437 + // blocks, which should be decent for quick convergence (with the
1.438 + // possible exception of exception handlers, which are all created
1.439 + // early).
1.440 + _work_list = NULL;
1.441 + for (int i = 0; i < num_blocks; i++) {
1.442 + block = _block_list[i];
1.443 + block->set_next(_work_list);
1.444 + block->set_on_work_list(true);
1.445 + _work_list = block;
1.446 + }
1.447 +
1.448 +
1.449 + while ((block = work_list_get()) != NULL) {
1.450 + block->propagate(this);
1.451 + NOT_PRODUCT(_total_visits++;)
1.452 + }
1.453 +}
1.454 +
1.455 +void MethodLiveness::work_list_add(BasicBlock *block) {
1.456 + if (!block->on_work_list()) {
1.457 + block->set_next(_work_list);
1.458 + block->set_on_work_list(true);
1.459 + _work_list = block;
1.460 + }
1.461 +}
1.462 +
1.463 +MethodLiveness::BasicBlock *MethodLiveness::work_list_get() {
1.464 + BasicBlock *block = _work_list;
1.465 + if (block != NULL) {
1.466 + block->set_on_work_list(false);
1.467 + _work_list = block->next();
1.468 + }
1.469 + return block;
1.470 +}
1.471 +
1.472 +
1.473 +MethodLivenessResult MethodLiveness::get_liveness_at(int entry_bci) {
1.474 + int bci = entry_bci;
1.475 + bool is_entry = false;
1.476 + if (entry_bci == InvocationEntryBci) {
1.477 + is_entry = true;
1.478 + bci = 0;
1.479 + }
1.480 +
1.481 + MethodLivenessResult answer((uintptr_t*)NULL,0);
1.482 +
1.483 + if (_block_count > 0) {
1.484 + if (TimeLivenessAnalysis) _time_total.start();
1.485 + if (TimeLivenessAnalysis) _time_query.start();
1.486 +
1.487 + assert( 0 <= bci && bci < method()->code_size(), "bci out of range" );
1.488 + BasicBlock *block = _block_map->at(bci);
1.489 + // We may not be at the block start, so search backwards to find the block
1.490 + // containing bci.
1.491 + int t = bci;
1.492 + while (block == NULL && t > 0) {
1.493 + block = _block_map->at(--t);
1.494 + }
1.495 + assert( block != NULL, "invalid bytecode index; must be instruction index" );
1.496 + assert(bci >= block->start_bci() && bci < block->limit_bci(), "block must contain bci.");
1.497 +
1.498 + answer = block->get_liveness_at(method(), bci);
1.499 +
1.500 + if (is_entry && method()->is_synchronized() && !method()->is_static()) {
1.501 + // Synchronized methods use the receiver once on entry.
1.502 + answer.at_put(0, true);
1.503 + }
1.504 +
1.505 +#ifndef PRODUCT
1.506 + if (TraceLivenessQuery) {
1.507 + tty->print("Liveness query of ");
1.508 + method()->print_short_name();
1.509 + tty->print(" @ %d : result is ", bci);
1.510 + answer.print_on(tty);
1.511 + }
1.512 +
1.513 + if (TimeLivenessAnalysis) _time_query.stop();
1.514 + if (TimeLivenessAnalysis) _time_total.stop();
1.515 +#endif
1.516 + }
1.517 +
1.518 +#ifndef PRODUCT
1.519 + if (TimeLivenessAnalysis) {
1.520 + // Collect statistics.
1.521 + _total_locals_queried += _bit_map_size_bits;
1.522 + BitCounter counter;
1.523 + answer.iterate(&counter);
1.524 + _total_live_locals_queried += counter.count();
1.525 + }
1.526 +#endif
1.527 +
1.528 + return answer;
1.529 +}
1.530 +
1.531 +
1.532 +#ifndef PRODUCT
1.533 +
1.534 +void MethodLiveness::print_times() {
1.535 + tty->print_cr ("Accumulated liveness analysis times/statistics:");
1.536 + tty->print_cr ("-----------------------------------------------");
1.537 + tty->print_cr (" Total : %3.3f sec.", _time_total.seconds());
1.538 + tty->print_cr (" Build graph : %3.3f sec. (%2.2f%%)", _time_build_graph.seconds(),
1.539 + _time_build_graph.seconds() * 100 / _time_total.seconds());
1.540 + tty->print_cr (" Gen / Kill : %3.3f sec. (%2.2f%%)", _time_gen_kill.seconds(),
1.541 + _time_gen_kill.seconds() * 100 / _time_total.seconds());
1.542 + tty->print_cr (" Dataflow : %3.3f sec. (%2.2f%%)", _time_flow.seconds(),
1.543 + _time_flow.seconds() * 100 / _time_total.seconds());
1.544 + tty->print_cr (" Query : %3.3f sec. (%2.2f%%)", _time_query.seconds(),
1.545 + _time_query.seconds() * 100 / _time_total.seconds());
1.546 + tty->print_cr (" #bytes : %8d (%3.0f bytes per sec)",
1.547 + _total_bytes,
1.548 + _total_bytes / _time_total.seconds());
1.549 + tty->print_cr (" #methods : %8d (%3.0f methods per sec)",
1.550 + _total_methods,
1.551 + _total_methods / _time_total.seconds());
1.552 + tty->print_cr (" avg locals : %3.3f max locals : %3d",
1.553 + (float)_total_method_locals / _total_methods,
1.554 + _max_method_locals);
1.555 + tty->print_cr (" avg blocks : %3.3f max blocks : %3d",
1.556 + (float)_total_blocks / _total_methods,
1.557 + _max_method_blocks);
1.558 + tty->print_cr (" avg bytes : %3.3f",
1.559 + (float)_total_bytes / _total_methods);
1.560 + tty->print_cr (" #blocks : %8d",
1.561 + _total_blocks);
1.562 + tty->print_cr (" avg normal predecessors : %3.3f max normal predecessors : %3d",
1.563 + (float)_total_edges / _total_blocks,
1.564 + _max_block_edges);
1.565 + tty->print_cr (" avg exception predecessors : %3.3f max exception predecessors : %3d",
1.566 + (float)_total_exc_edges / _total_blocks,
1.567 + _max_block_exc_edges);
1.568 + tty->print_cr (" avg visits : %3.3f",
1.569 + (float)_total_visits / _total_blocks);
1.570 + tty->print_cr (" #locals queried : %8d #live : %8d %%live : %2.2f%%",
1.571 + _total_locals_queried,
1.572 + _total_live_locals_queried,
1.573 + 100.0 * _total_live_locals_queried / _total_locals_queried);
1.574 +}
1.575 +
1.576 +#endif
1.577 +
1.578 +
1.579 +MethodLiveness::BasicBlock::BasicBlock(MethodLiveness *analyzer, int start, int limit) :
1.580 + _gen((uintptr_t*)analyzer->arena()->Amalloc(BytesPerWord * analyzer->bit_map_size_words()),
1.581 + analyzer->bit_map_size_bits()),
1.582 + _kill((uintptr_t*)analyzer->arena()->Amalloc(BytesPerWord * analyzer->bit_map_size_words()),
1.583 + analyzer->bit_map_size_bits()),
1.584 + _entry((uintptr_t*)analyzer->arena()->Amalloc(BytesPerWord * analyzer->bit_map_size_words()),
1.585 + analyzer->bit_map_size_bits()),
1.586 + _normal_exit((uintptr_t*)analyzer->arena()->Amalloc(BytesPerWord * analyzer->bit_map_size_words()),
1.587 + analyzer->bit_map_size_bits()),
1.588 + _exception_exit((uintptr_t*)analyzer->arena()->Amalloc(BytesPerWord * analyzer->bit_map_size_words()),
1.589 + analyzer->bit_map_size_bits()),
1.590 + _last_bci(-1) {
1.591 + _analyzer = analyzer;
1.592 + _start_bci = start;
1.593 + _limit_bci = limit;
1.594 + _normal_predecessors =
1.595 + new (analyzer->arena()) GrowableArray<MethodLiveness::BasicBlock*>(analyzer->arena(), 5, 0, NULL);
1.596 + _exception_predecessors =
1.597 + new (analyzer->arena()) GrowableArray<MethodLiveness::BasicBlock*>(analyzer->arena(), 5, 0, NULL);
1.598 + _normal_exit.clear();
1.599 + _exception_exit.clear();
1.600 + _entry.clear();
1.601 +
1.602 + // this initialization is not strictly necessary.
1.603 + // _gen and _kill are cleared at the beginning of compute_gen_kill_range()
1.604 + _gen.clear();
1.605 + _kill.clear();
1.606 +}
1.607 +
1.608 +
1.609 +
1.610 +MethodLiveness::BasicBlock *MethodLiveness::BasicBlock::split(int split_bci) {
1.611 + int start = _start_bci;
1.612 + int limit = _limit_bci;
1.613 +
1.614 + if (TraceLivenessGen) {
1.615 + tty->print_cr(" ** Splitting block (%d,%d) at %d", start, limit, split_bci);
1.616 + }
1.617 +
1.618 + GrowableArray<BasicBlock*>* save_predecessors = _normal_predecessors;
1.619 +
1.620 + assert (start < split_bci && split_bci < limit, "improper split");
1.621 +
1.622 + // Make a new block to cover the first half of the range.
1.623 + BasicBlock *first_half = new (_analyzer->arena()) BasicBlock(_analyzer, start, split_bci);
1.624 +
1.625 + // Assign correct values to the second half (this)
1.626 + _normal_predecessors = first_half->_normal_predecessors;
1.627 + _start_bci = split_bci;
1.628 + add_normal_predecessor(first_half);
1.629 +
1.630 + // Assign correct predecessors to the new first half
1.631 + first_half->_normal_predecessors = save_predecessors;
1.632 +
1.633 + return first_half;
1.634 +}
1.635 +
1.636 +void MethodLiveness::BasicBlock::compute_gen_kill(ciMethod* method) {
1.637 + ciBytecodeStream bytes(method);
1.638 + bytes.reset_to_bci(start_bci());
1.639 + bytes.set_max_bci(limit_bci());
1.640 + compute_gen_kill_range(&bytes);
1.641 +
1.642 +}
1.643 +
1.644 +void MethodLiveness::BasicBlock::compute_gen_kill_range(ciBytecodeStream *bytes) {
1.645 + _gen.clear();
1.646 + _kill.clear();
1.647 +
1.648 + while (bytes->next() != ciBytecodeStream::EOBC()) {
1.649 + compute_gen_kill_single(bytes);
1.650 + }
1.651 +}
1.652 +
1.653 +void MethodLiveness::BasicBlock::compute_gen_kill_single(ciBytecodeStream *instruction) {
1.654 + int localNum;
1.655 +
1.656 + // We prohibit _gen and _kill from having locals in common. If we
1.657 + // know that one is definitely going to be applied before the other,
1.658 + // we could save some computation time by relaxing this prohibition.
1.659 +
1.660 + switch (instruction->cur_bc()) {
1.661 + case Bytecodes::_nop:
1.662 + case Bytecodes::_goto:
1.663 + case Bytecodes::_goto_w:
1.664 + case Bytecodes::_aconst_null:
1.665 + case Bytecodes::_new:
1.666 + case Bytecodes::_iconst_m1:
1.667 + case Bytecodes::_iconst_0:
1.668 + case Bytecodes::_iconst_1:
1.669 + case Bytecodes::_iconst_2:
1.670 + case Bytecodes::_iconst_3:
1.671 + case Bytecodes::_iconst_4:
1.672 + case Bytecodes::_iconst_5:
1.673 + case Bytecodes::_fconst_0:
1.674 + case Bytecodes::_fconst_1:
1.675 + case Bytecodes::_fconst_2:
1.676 + case Bytecodes::_bipush:
1.677 + case Bytecodes::_sipush:
1.678 + case Bytecodes::_lconst_0:
1.679 + case Bytecodes::_lconst_1:
1.680 + case Bytecodes::_dconst_0:
1.681 + case Bytecodes::_dconst_1:
1.682 + case Bytecodes::_ldc2_w:
1.683 + case Bytecodes::_ldc:
1.684 + case Bytecodes::_ldc_w:
1.685 + case Bytecodes::_iaload:
1.686 + case Bytecodes::_faload:
1.687 + case Bytecodes::_baload:
1.688 + case Bytecodes::_caload:
1.689 + case Bytecodes::_saload:
1.690 + case Bytecodes::_laload:
1.691 + case Bytecodes::_daload:
1.692 + case Bytecodes::_aaload:
1.693 + case Bytecodes::_iastore:
1.694 + case Bytecodes::_fastore:
1.695 + case Bytecodes::_bastore:
1.696 + case Bytecodes::_castore:
1.697 + case Bytecodes::_sastore:
1.698 + case Bytecodes::_lastore:
1.699 + case Bytecodes::_dastore:
1.700 + case Bytecodes::_aastore:
1.701 + case Bytecodes::_pop:
1.702 + case Bytecodes::_pop2:
1.703 + case Bytecodes::_dup:
1.704 + case Bytecodes::_dup_x1:
1.705 + case Bytecodes::_dup_x2:
1.706 + case Bytecodes::_dup2:
1.707 + case Bytecodes::_dup2_x1:
1.708 + case Bytecodes::_dup2_x2:
1.709 + case Bytecodes::_swap:
1.710 + case Bytecodes::_iadd:
1.711 + case Bytecodes::_fadd:
1.712 + case Bytecodes::_isub:
1.713 + case Bytecodes::_fsub:
1.714 + case Bytecodes::_imul:
1.715 + case Bytecodes::_fmul:
1.716 + case Bytecodes::_idiv:
1.717 + case Bytecodes::_fdiv:
1.718 + case Bytecodes::_irem:
1.719 + case Bytecodes::_frem:
1.720 + case Bytecodes::_ishl:
1.721 + case Bytecodes::_ishr:
1.722 + case Bytecodes::_iushr:
1.723 + case Bytecodes::_iand:
1.724 + case Bytecodes::_ior:
1.725 + case Bytecodes::_ixor:
1.726 + case Bytecodes::_l2f:
1.727 + case Bytecodes::_l2i:
1.728 + case Bytecodes::_d2f:
1.729 + case Bytecodes::_d2i:
1.730 + case Bytecodes::_fcmpl:
1.731 + case Bytecodes::_fcmpg:
1.732 + case Bytecodes::_ladd:
1.733 + case Bytecodes::_dadd:
1.734 + case Bytecodes::_lsub:
1.735 + case Bytecodes::_dsub:
1.736 + case Bytecodes::_lmul:
1.737 + case Bytecodes::_dmul:
1.738 + case Bytecodes::_ldiv:
1.739 + case Bytecodes::_ddiv:
1.740 + case Bytecodes::_lrem:
1.741 + case Bytecodes::_drem:
1.742 + case Bytecodes::_land:
1.743 + case Bytecodes::_lor:
1.744 + case Bytecodes::_lxor:
1.745 + case Bytecodes::_ineg:
1.746 + case Bytecodes::_fneg:
1.747 + case Bytecodes::_i2f:
1.748 + case Bytecodes::_f2i:
1.749 + case Bytecodes::_i2c:
1.750 + case Bytecodes::_i2s:
1.751 + case Bytecodes::_i2b:
1.752 + case Bytecodes::_lneg:
1.753 + case Bytecodes::_dneg:
1.754 + case Bytecodes::_l2d:
1.755 + case Bytecodes::_d2l:
1.756 + case Bytecodes::_lshl:
1.757 + case Bytecodes::_lshr:
1.758 + case Bytecodes::_lushr:
1.759 + case Bytecodes::_i2l:
1.760 + case Bytecodes::_i2d:
1.761 + case Bytecodes::_f2l:
1.762 + case Bytecodes::_f2d:
1.763 + case Bytecodes::_lcmp:
1.764 + case Bytecodes::_dcmpl:
1.765 + case Bytecodes::_dcmpg:
1.766 + case Bytecodes::_ifeq:
1.767 + case Bytecodes::_ifne:
1.768 + case Bytecodes::_iflt:
1.769 + case Bytecodes::_ifge:
1.770 + case Bytecodes::_ifgt:
1.771 + case Bytecodes::_ifle:
1.772 + case Bytecodes::_tableswitch:
1.773 + case Bytecodes::_ireturn:
1.774 + case Bytecodes::_freturn:
1.775 + case Bytecodes::_if_icmpeq:
1.776 + case Bytecodes::_if_icmpne:
1.777 + case Bytecodes::_if_icmplt:
1.778 + case Bytecodes::_if_icmpge:
1.779 + case Bytecodes::_if_icmpgt:
1.780 + case Bytecodes::_if_icmple:
1.781 + case Bytecodes::_lreturn:
1.782 + case Bytecodes::_dreturn:
1.783 + case Bytecodes::_if_acmpeq:
1.784 + case Bytecodes::_if_acmpne:
1.785 + case Bytecodes::_jsr:
1.786 + case Bytecodes::_jsr_w:
1.787 + case Bytecodes::_getstatic:
1.788 + case Bytecodes::_putstatic:
1.789 + case Bytecodes::_getfield:
1.790 + case Bytecodes::_putfield:
1.791 + case Bytecodes::_invokevirtual:
1.792 + case Bytecodes::_invokespecial:
1.793 + case Bytecodes::_invokestatic:
1.794 + case Bytecodes::_invokeinterface:
1.795 + case Bytecodes::_invokedynamic:
1.796 + case Bytecodes::_newarray:
1.797 + case Bytecodes::_anewarray:
1.798 + case Bytecodes::_checkcast:
1.799 + case Bytecodes::_arraylength:
1.800 + case Bytecodes::_instanceof:
1.801 + case Bytecodes::_athrow:
1.802 + case Bytecodes::_areturn:
1.803 + case Bytecodes::_monitorenter:
1.804 + case Bytecodes::_monitorexit:
1.805 + case Bytecodes::_ifnull:
1.806 + case Bytecodes::_ifnonnull:
1.807 + case Bytecodes::_multianewarray:
1.808 + case Bytecodes::_lookupswitch:
1.809 + // These bytecodes have no effect on the method's locals.
1.810 + break;
1.811 +
1.812 + case Bytecodes::_return:
1.813 + if (instruction->method()->intrinsic_id() == vmIntrinsics::_Object_init) {
1.814 + // return from Object.init implicitly registers a finalizer
1.815 + // for the receiver if needed, so keep it alive.
1.816 + load_one(0);
1.817 + }
1.818 + break;
1.819 +
1.820 +
1.821 + case Bytecodes::_lload:
1.822 + case Bytecodes::_dload:
1.823 + load_two(instruction->get_index());
1.824 + break;
1.825 +
1.826 + case Bytecodes::_lload_0:
1.827 + case Bytecodes::_dload_0:
1.828 + load_two(0);
1.829 + break;
1.830 +
1.831 + case Bytecodes::_lload_1:
1.832 + case Bytecodes::_dload_1:
1.833 + load_two(1);
1.834 + break;
1.835 +
1.836 + case Bytecodes::_lload_2:
1.837 + case Bytecodes::_dload_2:
1.838 + load_two(2);
1.839 + break;
1.840 +
1.841 + case Bytecodes::_lload_3:
1.842 + case Bytecodes::_dload_3:
1.843 + load_two(3);
1.844 + break;
1.845 +
1.846 + case Bytecodes::_iload:
1.847 + case Bytecodes::_iinc:
1.848 + case Bytecodes::_fload:
1.849 + case Bytecodes::_aload:
1.850 + case Bytecodes::_ret:
1.851 + load_one(instruction->get_index());
1.852 + break;
1.853 +
1.854 + case Bytecodes::_iload_0:
1.855 + case Bytecodes::_fload_0:
1.856 + case Bytecodes::_aload_0:
1.857 + load_one(0);
1.858 + break;
1.859 +
1.860 + case Bytecodes::_iload_1:
1.861 + case Bytecodes::_fload_1:
1.862 + case Bytecodes::_aload_1:
1.863 + load_one(1);
1.864 + break;
1.865 +
1.866 + case Bytecodes::_iload_2:
1.867 + case Bytecodes::_fload_2:
1.868 + case Bytecodes::_aload_2:
1.869 + load_one(2);
1.870 + break;
1.871 +
1.872 + case Bytecodes::_iload_3:
1.873 + case Bytecodes::_fload_3:
1.874 + case Bytecodes::_aload_3:
1.875 + load_one(3);
1.876 + break;
1.877 +
1.878 + case Bytecodes::_lstore:
1.879 + case Bytecodes::_dstore:
1.880 + store_two(localNum = instruction->get_index());
1.881 + break;
1.882 +
1.883 + case Bytecodes::_lstore_0:
1.884 + case Bytecodes::_dstore_0:
1.885 + store_two(0);
1.886 + break;
1.887 +
1.888 + case Bytecodes::_lstore_1:
1.889 + case Bytecodes::_dstore_1:
1.890 + store_two(1);
1.891 + break;
1.892 +
1.893 + case Bytecodes::_lstore_2:
1.894 + case Bytecodes::_dstore_2:
1.895 + store_two(2);
1.896 + break;
1.897 +
1.898 + case Bytecodes::_lstore_3:
1.899 + case Bytecodes::_dstore_3:
1.900 + store_two(3);
1.901 + break;
1.902 +
1.903 + case Bytecodes::_istore:
1.904 + case Bytecodes::_fstore:
1.905 + case Bytecodes::_astore:
1.906 + store_one(instruction->get_index());
1.907 + break;
1.908 +
1.909 + case Bytecodes::_istore_0:
1.910 + case Bytecodes::_fstore_0:
1.911 + case Bytecodes::_astore_0:
1.912 + store_one(0);
1.913 + break;
1.914 +
1.915 + case Bytecodes::_istore_1:
1.916 + case Bytecodes::_fstore_1:
1.917 + case Bytecodes::_astore_1:
1.918 + store_one(1);
1.919 + break;
1.920 +
1.921 + case Bytecodes::_istore_2:
1.922 + case Bytecodes::_fstore_2:
1.923 + case Bytecodes::_astore_2:
1.924 + store_one(2);
1.925 + break;
1.926 +
1.927 + case Bytecodes::_istore_3:
1.928 + case Bytecodes::_fstore_3:
1.929 + case Bytecodes::_astore_3:
1.930 + store_one(3);
1.931 + break;
1.932 +
1.933 + case Bytecodes::_wide:
1.934 + fatal("Iterator should skip this bytecode");
1.935 + break;
1.936 +
1.937 + default:
1.938 + tty->print("unexpected opcode: %d\n", instruction->cur_bc());
1.939 + ShouldNotReachHere();
1.940 + break;
1.941 + }
1.942 +}
1.943 +
1.944 +void MethodLiveness::BasicBlock::load_two(int local) {
1.945 + load_one(local);
1.946 + load_one(local+1);
1.947 +}
1.948 +
1.949 +void MethodLiveness::BasicBlock::load_one(int local) {
1.950 + if (!_kill.at(local)) {
1.951 + _gen.at_put(local, true);
1.952 + }
1.953 +}
1.954 +
1.955 +void MethodLiveness::BasicBlock::store_two(int local) {
1.956 + store_one(local);
1.957 + store_one(local+1);
1.958 +}
1.959 +
1.960 +void MethodLiveness::BasicBlock::store_one(int local) {
1.961 + if (!_gen.at(local)) {
1.962 + _kill.at_put(local, true);
1.963 + }
1.964 +}
1.965 +
1.966 +void MethodLiveness::BasicBlock::propagate(MethodLiveness *ml) {
1.967 + // These set operations could be combined for efficiency if the
1.968 + // performance of this analysis becomes an issue.
1.969 + _entry.set_union(_normal_exit);
1.970 + _entry.set_difference(_kill);
1.971 + _entry.set_union(_gen);
1.972 +
1.973 + // Note that we merge information from our exceptional successors
1.974 + // just once, rather than at individual bytecodes.
1.975 + _entry.set_union(_exception_exit);
1.976 +
1.977 + if (TraceLivenessGen) {
1.978 + tty->print_cr(" ** Visiting block at %d **", start_bci());
1.979 + print_on(tty);
1.980 + }
1.981 +
1.982 + int i;
1.983 + for (i=_normal_predecessors->length()-1; i>=0; i--) {
1.984 + BasicBlock *block = _normal_predecessors->at(i);
1.985 + if (block->merge_normal(_entry)) {
1.986 + ml->work_list_add(block);
1.987 + }
1.988 + }
1.989 + for (i=_exception_predecessors->length()-1; i>=0; i--) {
1.990 + BasicBlock *block = _exception_predecessors->at(i);
1.991 + if (block->merge_exception(_entry)) {
1.992 + ml->work_list_add(block);
1.993 + }
1.994 + }
1.995 +}
1.996 +
1.997 +bool MethodLiveness::BasicBlock::merge_normal(BitMap other) {
1.998 + return _normal_exit.set_union_with_result(other);
1.999 +}
1.1000 +
1.1001 +bool MethodLiveness::BasicBlock::merge_exception(BitMap other) {
1.1002 + return _exception_exit.set_union_with_result(other);
1.1003 +}
1.1004 +
1.1005 +MethodLivenessResult MethodLiveness::BasicBlock::get_liveness_at(ciMethod* method, int bci) {
1.1006 + MethodLivenessResult answer(NEW_RESOURCE_ARRAY(uintptr_t, _analyzer->bit_map_size_words()),
1.1007 + _analyzer->bit_map_size_bits());
1.1008 + answer.set_is_valid();
1.1009 +
1.1010 +#ifndef ASSERT
1.1011 + if (bci == start_bci()) {
1.1012 + answer.set_from(_entry);
1.1013 + return answer;
1.1014 + }
1.1015 +#endif
1.1016 +
1.1017 +#ifdef ASSERT
1.1018 + ResourceMark rm;
1.1019 + BitMap g(_gen.size()); g.set_from(_gen);
1.1020 + BitMap k(_kill.size()); k.set_from(_kill);
1.1021 +#endif
1.1022 + if (_last_bci != bci || trueInDebug) {
1.1023 + ciBytecodeStream bytes(method);
1.1024 + bytes.reset_to_bci(bci);
1.1025 + bytes.set_max_bci(limit_bci());
1.1026 + compute_gen_kill_range(&bytes);
1.1027 + assert(_last_bci != bci ||
1.1028 + (g.is_same(_gen) && k.is_same(_kill)), "cached computation is incorrect");
1.1029 + _last_bci = bci;
1.1030 + }
1.1031 +
1.1032 + answer.clear();
1.1033 + answer.set_union(_normal_exit);
1.1034 + answer.set_difference(_kill);
1.1035 + answer.set_union(_gen);
1.1036 + answer.set_union(_exception_exit);
1.1037 +
1.1038 +#ifdef ASSERT
1.1039 + if (bci == start_bci()) {
1.1040 + assert(answer.is_same(_entry), "optimized answer must be accurate");
1.1041 + }
1.1042 +#endif
1.1043 +
1.1044 + return answer;
1.1045 +}
1.1046 +
1.1047 +#ifndef PRODUCT
1.1048 +
1.1049 +void MethodLiveness::BasicBlock::print_on(outputStream *os) const {
1.1050 + os->print_cr("===================================================================");
1.1051 + os->print_cr(" Block start: %4d, limit: %4d", _start_bci, _limit_bci);
1.1052 + os->print (" Normal predecessors (%2d) @", _normal_predecessors->length());
1.1053 + int i;
1.1054 + for (i=0; i < _normal_predecessors->length(); i++) {
1.1055 + os->print(" %4d", _normal_predecessors->at(i)->start_bci());
1.1056 + }
1.1057 + os->cr();
1.1058 + os->print (" Exceptional predecessors (%2d) @", _exception_predecessors->length());
1.1059 + for (i=0; i < _exception_predecessors->length(); i++) {
1.1060 + os->print(" %4d", _exception_predecessors->at(i)->start_bci());
1.1061 + }
1.1062 + os->cr();
1.1063 + os->print (" Normal Exit : ");
1.1064 + _normal_exit.print_on(os);
1.1065 + os->print (" Gen : ");
1.1066 + _gen.print_on(os);
1.1067 + os->print (" Kill : ");
1.1068 + _kill.print_on(os);
1.1069 + os->print (" Exception Exit: ");
1.1070 + _exception_exit.print_on(os);
1.1071 + os->print (" Entry : ");
1.1072 + _entry.print_on(os);
1.1073 +}
1.1074 +
1.1075 +#endif // PRODUCT
