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