/*
* Copyright (c) 1998, 2010, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* 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.
*
*/
#ifndef SHARE_VM_COMPILER_METHODLIVENESS_HPP
#define SHARE_VM_COMPILER_METHODLIVENESS_HPP
#include "utilities/bitMap.hpp"
#include "utilities/growableArray.hpp"
class ciMethod;
class MethodLivenessResult : public BitMap {
private:
bool _is_valid;
public:
MethodLivenessResult(BitMap::bm_word_t* map, idx_t size_in_bits)
: BitMap(map, size_in_bits)
, _is_valid(false)
{}
MethodLivenessResult(idx_t size_in_bits)
: BitMap(size_in_bits)
, _is_valid(false)
{}
void set_is_valid() { _is_valid = true; }
bool is_valid() { return _is_valid; }
};
class MethodLiveness : public ResourceObj {
public:
// The BasicBlock class is used to represent a basic block in the
// liveness analysis.
class BasicBlock : public ResourceObj {
private:
// This class is only used by the MethodLiveness class.
friend class MethodLiveness;
// The analyzer which created this basic block.
MethodLiveness* _analyzer;
// The range of this basic block is [start_bci,limit_bci)
int _start_bci;
int _limit_bci;
// The liveness at the start of the block;
BitMap _entry;
// The summarized liveness effects of our direct successors reached
// by normal control flow
BitMap _normal_exit;
// The summarized liveness effects of our direct successors reached
// by exceptional control flow
BitMap _exception_exit;
// These members hold the results of the last call to
// compute_gen_kill_range(). _gen is the set of locals
// used before they are defined in the range. _kill is the
// set of locals defined before they are used.
BitMap _gen;
BitMap _kill;
int _last_bci;
// A list of all blocks which could come directly before this one
// in normal (non-exceptional) control flow. We propagate liveness
// information to these blocks.
GrowableArray<BasicBlock*>* _normal_predecessors;
// A list of all blocks which could come directly before this one
// in exceptional control flow.
GrowableArray<BasicBlock*>* _exception_predecessors;
// The following fields are used to manage a work list used in the
// dataflow.
BasicBlock *_next;
bool _on_work_list;
// Our successors call this method to merge liveness information into
// our _normal_exit member.
bool merge_normal(BitMap other);
// Our successors call this method to merge liveness information into
// our _exception_exit member.
bool merge_exception(BitMap other);
// This helper routine is used to help compute the gen/kill pair for
// the block. It is also used to answer queries.
void compute_gen_kill_range(ciBytecodeStream *bytes);
// Compute the gen/kill effect of a single instruction.
void compute_gen_kill_single(ciBytecodeStream *instruction);
// Helpers for compute_gen_kill_single.
void load_one(int local);
void load_two(int local);
void store_one(int local);
void store_two(int local);
BasicBlock(MethodLiveness *analyzer, int start, int limit);
// -- Accessors
int start_bci() const { return _start_bci; }
int limit_bci() const { return _limit_bci; }
void set_limit_bci(int limit) { _limit_bci = limit; }
BasicBlock *next() const { return _next; }
void set_next(BasicBlock *next) { _next = next; }
bool on_work_list() const { return _on_work_list; }
void set_on_work_list(bool val) { _on_work_list = val; }
// -- Flow graph construction.
// Add a basic block to our list of normal predecessors.
void add_normal_predecessor(BasicBlock *pred) {
_normal_predecessors->append_if_missing(pred);
}
// Add a basic block to our list of exceptional predecessors
void add_exception_predecessor(BasicBlock *pred) {
_exception_predecessors->append_if_missing(pred);
}
// Split the basic block at splitBci. This basic block
// becomes the second half. The first half is newly created.
BasicBlock *split(int splitBci);
// -- Dataflow.
void compute_gen_kill(ciMethod* method);
// Propagate changes from this basic block
void propagate(MethodLiveness *ml);
// -- Query.
MethodLivenessResult get_liveness_at(ciMethod* method, int bci);
// -- Debugging.
void print_on(outputStream *os) const PRODUCT_RETURN;
}; // End of MethodLiveness::BasicBlock
private:
// The method we are analyzing.
ciMethod* _method;
ciMethod* method() const { return _method; }
// The arena for storing structures...
Arena* _arena;
Arena* arena() const { return _arena; }
// We cache the length of the method.
int _code_size;
// The size of a BitMap.
int _bit_map_size_bits;
int _bit_map_size_words;
// A list of all BasicBlocks.
BasicBlock **_block_list;
// number of blocks
int _block_count;
// Keeps track of bci->block mapping. One entry for each bci. Only block starts are
// recorded.
GrowableArray<BasicBlock*>* _block_map;
// Our work list.
BasicBlock *_work_list;
#ifdef COMPILER1
// bcis where blocks start are marked
BitMap _bci_block_start;
#endif // COMPILER1
// -- Graph construction & Analysis
// Compute ranges and predecessors for basic blocks.
void init_basic_blocks();
// Compute gen/kill information for all basic blocks.
void init_gen_kill();
// Perform the dataflow.
void propagate_liveness();
// The class MethodLiveness::BasicBlock needs special access to some
// of our members.
friend class MethodLiveness::BasicBlock;
// And accessors.
int bit_map_size_bits() const { return _bit_map_size_bits; }
int bit_map_size_words() const { return _bit_map_size_words; }
// Work list manipulation routines. Called internally by BasicBlock.
BasicBlock *work_list_get();
void work_list_add(BasicBlock *block);
// -- Timing and Statistics.
// Timers
static elapsedTimer _time_build_graph;
static elapsedTimer _time_gen_kill;
static elapsedTimer _time_flow;
static elapsedTimer _time_query;
static elapsedTimer _time_total;
#ifndef PRODUCT
// Counts
static long _total_bytes;
static int _total_methods;
static long _total_blocks;
static int _max_method_blocks;
static long _total_edges;
static int _max_block_edges;
static long _total_exc_edges;
static int _max_block_exc_edges;
static long _total_method_locals;
static int _max_method_locals;
static long _total_locals_queried;
static long _total_live_locals_queried;
static long _total_visits;
#endif
public:
// Create a liveness analyzer for a method
MethodLiveness(Arena* arena, ciMethod* method);
// Compute liveness information for the method
void compute_liveness();
// Find out which locals are live at a specific bci.
MethodLivenessResult get_liveness_at(int bci);
#ifdef COMPILER1
const BitMap get_bci_block_start() const { return _bci_block_start; }
#endif // COMPILER1
static void print_times() PRODUCT_RETURN;
};
#endif // SHARE_VM_COMPILER_METHODLIVENESS_HPP