methodLiveness.cpp revision 2027
6338N/A * Copyright (c) 1998, 2011, Oracle and/or its affiliates. All rights reserved. 6338N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 6338N/A * This code is free software; you can redistribute it and/or modify it 6338N/A * under the terms of the GNU General Public License version 2 only, as 6338N/A * published by the Free Software Foundation. 6338N/A * This code is distributed in the hope that it will be useful, but WITHOUT 6338N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 6338N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 6338N/A * version 2 for more details (a copy is included in the LICENSE file that 6338N/A * You should have received a copy of the GNU General Public License version 6338N/A * 2 along with this work; if not, write to the Free Software Foundation, 6338N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 6338N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 6338N/A// The MethodLiveness class performs a simple liveness analysis on a method 6338N/A// in order to decide which locals are live (that is, will be used again) at 6338N/A// a particular bytecode index (bci). 6338N/A// 1. Break the method into a set of basic blocks. For each basic block we 6338N/A// also keep track of its set of predecessors through normal control flow 6338N/A// and predecessors through exceptional control flow. 6338N/A// 2. For each basic block, compute two sets, gen (the set of values used before 6338N/A// they are defined) and kill (the set of values defined before they are used) 6338N/A// in the basic block. A basic block "needs" the locals in its gen set to 6338N/A// perform its computation. A basic block "provides" values for the locals in 6338N/A// its kill set, allowing a need from a successor to be ignored. 6338N/A// 3. Liveness information (the set of locals which are needed) is pushed backwards through 6338N/A// the program, from blocks to their predecessors. We compute and store liveness 6338N/A// this process reaches a fixed point, we are done. 6338N/A// 4. When we are asked about the liveness at a particular bci with a basic block, we 6338N/A// compute gen/kill sets which represent execution from that bci to the exit of 6338N/A// its blocks. We then compose this range gen/kill information with the normal 6338N/A// and exceptional exit information for the block to produce liveness information 6338N/A// The algorithm is approximate in many respects. Notably: 6338N/A// 1. We do not do the analysis necessary to match jsr's with the appropriate ret. 6338N/A// Instead we make the conservative assumption that any ret can return to any 6338N/A// 2. Instead of computing the effects of exceptions at every instruction, we 6338N/A// summarize the effects of all exceptional continuations from the block as 6338N/A// a single set (_exception_exit), losing some information but simplifying the 6338N/A//-------------------------------------------------------------------------- 6338N/A// The BitCounter class is used for counting the number of bits set in 6338N/A// some BitMap. It is only used when collecting liveness statistics. 6338N/A // Callback when bit in map is set 6338N/A//-------------------------------------------------------------------------- 6338N/A tty->
print_cr(
"################################################################");
6338N/A // Create an array to store the bci->BasicBlock mapping. 6338N/A // generate our block list from ciMethodBlocks 6338N/A // mark all bcis where a new basic block starts 6338N/A // fill in the predecessors of blocks 6338N/A // Now we need to interpret the instruction's effect 6338N/A // Two way branch. Set predecessors at each destination. assert(
false,
"wide opcodes should not be seen here");
// These opcodes are not the normal predecessors of any other opcodes. // We will patch up jsr/rets in a subsequent pass. // Bail out of there are breakpoints in here. // Patch up the jsr/ret's. We conservatively assume that any ret // can return to any jsr site. // Compute exception edges. // The catch range has a nonempty intersection with this // basic block. That means this basic block can be an // exceptional predecessor. // This is a catch-all block. // The basic block is entirely contained in this catch-all block. // Skip the rest of the exception handlers -- they can never be // We start our work list off with all blocks in it. // Alternately, we could start off the work list with the list of all // blocks which could exit the method directly, along with one block // from any infinite loop. If this matters, it can be changed. It // may not be clear from looking at the code, but the order of the // workList will be the opposite of the creation order of the basic // blocks, which should be decent for quick convergence (with the // possible exception of exception handlers, which are all created // We may not be at the block start, so search backwards to find the block assert(
block !=
NULL,
"invalid bytecode index; must be instruction index" );
// Synchronized methods use the receiver once on entry. tty->
print_cr (
"-----------------------------------------------");
tty->
print_cr (
" #methods : %8d (%3.0f methods per sec)",
tty->
print_cr (
" avg normal predecessors : %3.3f max normal predecessors : %3d",
tty->
print_cr (
" avg exception predecessors : %3.3f max exception predecessors : %3d",
tty->
print_cr (
" #locals queried : %8d #live : %8d %%live : %2.2f%%",
// this initialization is not strictly necessary. // _gen and _kill are cleared at the beginning of compute_gen_kill_range() // Make a new block to cover the first half of the range. // Assign correct values to the second half (this) // Assign correct predecessors to the new first half // We prohibit _gen and _kill from having locals in common. If we // know that one is definitely going to be applied before the other, // we could save some computation time by relaxing this prohibition. // These bytecodes have no effect on the method's locals. // return from Object.init implicitly registers a finalizer // for the receiver if needed, so keep it alive. fatal(
"Iterator should skip this bytecode");
// These set operations could be combined for efficiency if the // performance of this analysis becomes an issue. // Note that we merge information from our exceptional successors // just once, rather than at individual bytecodes. os->
print_cr(
"===================================================================");