/*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*
*/
#include "precompiled.hpp"
#include "ci/ciMethod.hpp"
#include "ci/ciMethodBlocks.hpp"
#include "ci/ciStreams.hpp"
#include "compiler/methodLiveness.hpp"
#include "interpreter/bytecode.hpp"
#include "interpreter/bytecodes.hpp"
#include "memory/allocation.inline.hpp"
#include "utilities/bitMap.inline.hpp"
// The MethodLiveness class performs a simple liveness analysis on a method
// in order to decide which locals are live (that is, will be used again) at
// a particular bytecode index (bci).
//
// The algorithm goes:
//
// 1. Break the method into a set of basic blocks. For each basic block we
// also keep track of its set of predecessors through normal control flow
// and predecessors through exceptional control flow.
//
// 2. For each basic block, compute two sets, gen (the set of values used before
// they are defined) and kill (the set of values defined before they are used)
// in the basic block. A basic block "needs" the locals in its gen set to
// perform its computation. A basic block "provides" values for the locals in
// its kill set, allowing a need from a successor to be ignored.
//
// 3. Liveness information (the set of locals which are needed) is pushed backwards through
// the program, from blocks to their predecessors. We compute and store liveness
// information for the normal/exceptional exit paths for each basic block. When
// this process reaches a fixed point, we are done.
//
// 4. When we are asked about the liveness at a particular bci with a basic block, we
// and exceptional exit information for the block to produce liveness information
// at that bci.
//
// The algorithm is approximate in many respects. Notably:
//
// 1. We do not do the analysis necessary to match jsr's with the appropriate ret.
// Instead we make the conservative assumption that any ret can return to any
// jsr return site.
// 2. Instead of computing the effects of exceptions at every instruction, we
// summarize the effects of all exceptional continuations from the block as
// a single set (_exception_exit), losing some information but simplifying the
// analysis.
//--------------------------------------------------------------------------
// The BitCounter class is used for counting the number of bits set in
// some BitMap. It is only used when collecting liveness statistics.
#ifndef PRODUCT
private:
int _count;
public:
// Callback when bit in map is set
_count++;
return true;
}
int count() {
return _count;
}
};
//--------------------------------------------------------------------------
// Counts
#endif
// Timers
#ifdef COMPILER1
: _bci_block_start((uintptr_t*)arena->Amalloc((method->code_size() >> LogBitsPerByte) + 1), method->code_size())
#endif
{
#ifdef COMPILER1
#endif
}
#ifndef PRODUCT
if (TraceLivenessGen) {
method()->print_short_name();
}
#endif
{
}
{
}
{
}
#ifndef PRODUCT
if (TimeLivenessAnalysis) {
// Collect statistics
for (int i=0; i<num_blocks; i++) {
_total_edges += numEdges;
}
}
#endif
}
bool bailout = false;
// Create an array to store the bci->BasicBlock mapping.
// generate our block list from ciMethodBlocks
#ifdef COMPILER1
// mark all bcis where a new basic block starts
#endif // COMPILER1
}
// fill in the predecessors of blocks
if (limit < method_len) {
}
continue;
}
// Now we need to interpret the instruction's effect
// on control flow.
switch (code) {
case Bytecodes::_if_icmpeq:
case Bytecodes::_if_icmpne:
case Bytecodes::_if_icmplt:
case Bytecodes::_if_icmpge:
case Bytecodes::_if_icmpgt:
case Bytecodes::_if_icmple:
case Bytecodes::_if_acmpeq:
case Bytecodes::_if_acmpne:
case Bytecodes::_ifnonnull:
// Two way branch. Set predecessors at each destination.
break;
break;
break;
case Bytecodes::_tableswitch:
{
while (--len >= 0) {
}
break;
}
case Bytecodes::_lookupswitch:
{
while(--npairs >= 0) {
}
break;
}
{
break;
}
{
break;
}
assert(false, "wide opcodes should not be seen here");
break;
// These opcodes are not the normal predecessors of any other opcodes.
break;
break;
case Bytecodes::_breakpoint:
// Bail out of there are breakpoints in here.
bailout = true;
break;
default:
// Do nothing.
break;
}
}
// can return to any jsr site.
if (ret_list_len > 0 && jsr_exit_list_len > 0) {
for (int i = jsr_exit_list_len - 1; i >= 0; i--) {
for (int i = ret_list_len - 1; i >= 0; i--) {
}
}
}
// Compute exception edges.
for (int b=_block_count-1; b >= 0; b--) {
if (intersect_start < intersect_limit) {
// The catch range has a nonempty intersection with this
// basic block. That means this basic block can be an
// exceptional predecessor.
if (handler->is_catch_all()) {
// 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
// reached in execution.
break;
}
}
}
}
}
}
for (int i=_block_count-1; i >= 0; i--) {
}
}
// 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
// early).
_work_list = NULL;
for (int i = 0; i < num_blocks; i++) {
block = _block_list[i];
block->set_on_work_list(true);
_work_list = block;
}
}
}
if (!block->on_work_list()) {
block->set_on_work_list(true);
_work_list = block;
}
}
block->set_on_work_list(false);
}
return block;
}
bool is_entry = false;
if (entry_bci == InvocationEntryBci) {
is_entry = true;
bci = 0;
}
if (_block_count > 0) {
// We may not be at the block start, so search backwards to find the block
// containing bci.
int t = bci;
}
// Synchronized methods use the receiver once on entry.
}
#ifndef PRODUCT
if (TraceLivenessQuery) {
method()->print_short_name();
}
#endif
}
#ifndef PRODUCT
if (TimeLivenessAnalysis) {
// Collect statistics.
}
#endif
return answer;
}
#ifndef PRODUCT
(float)_total_method_locals / _total_methods,
(float)_total_blocks / _total_methods,
(float)_total_bytes / _total_methods);
(float)_total_edges / _total_blocks,
(float)_total_exc_edges / _total_blocks,
(float)_total_visits / _total_blocks);
}
#endif
_exception_exit((uintptr_t*)analyzer->arena()->Amalloc(BytesPerWord * analyzer->bit_map_size_words()),
_last_bci(-1) {
_start_bci = start;
_limit_bci = limit;
// this initialization is not strictly necessary.
// _gen and _kill are cleared at the beginning of compute_gen_kill_range()
}
if (TraceLivenessGen) {
}
// 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
return first_half;
}
}
}
}
int localNum;
// 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.
switch (instruction->cur_bc()) {
case Bytecodes::_aconst_null:
case Bytecodes::_iconst_m1:
case Bytecodes::_tableswitch:
case Bytecodes::_if_icmpeq:
case Bytecodes::_if_icmpne:
case Bytecodes::_if_icmplt:
case Bytecodes::_if_icmpge:
case Bytecodes::_if_icmpgt:
case Bytecodes::_if_icmple:
case Bytecodes::_if_acmpeq:
case Bytecodes::_if_acmpne:
case Bytecodes::_getstatic:
case Bytecodes::_putstatic:
case Bytecodes::_invokevirtual:
case Bytecodes::_invokespecial:
case Bytecodes::_invokestatic:
case Bytecodes::_invokeinterface:
case Bytecodes::_invokedynamic:
case Bytecodes::_anewarray:
case Bytecodes::_checkcast:
case Bytecodes::_arraylength:
case Bytecodes::_instanceof:
case Bytecodes::_monitorenter:
case Bytecodes::_monitorexit:
case Bytecodes::_ifnonnull:
case Bytecodes::_multianewarray:
case Bytecodes::_lookupswitch:
// These bytecodes have no effect on the method's locals.
break;
// return from Object.init implicitly registers a finalizer
// for the receiver if needed, so keep it alive.
load_one(0);
}
break;
break;
load_two(0);
break;
load_two(1);
break;
load_two(2);
break;
load_two(3);
break;
break;
load_one(0);
break;
load_one(1);
break;
load_one(2);
break;
load_one(3);
break;
break;
store_two(0);
break;
store_two(1);
break;
store_two(2);
break;
store_two(3);
break;
break;
store_one(0);
break;
store_one(1);
break;
store_one(2);
break;
store_one(3);
break;
fatal("Iterator should skip this bytecode");
break;
default:
break;
}
}
}
}
}
}
}
}
// 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.
if (TraceLivenessGen) {
}
int i;
}
}
}
}
}
}
}
#ifndef ASSERT
return answer;
}
#endif
#ifdef ASSERT
#endif
}
#ifdef ASSERT
}
#endif
return answer;
}
#ifndef PRODUCT
int i;
for (i=0; i < _normal_predecessors->length(); i++) {
}
for (i=0; i < _exception_predecessors->length(); i++) {
}
}
#endif // PRODUCT