src/share/vm/c1/c1_Instruction.hpp
Print this page
rev 4136 : 7153771: array bound check elimination for c1
Summary: when possible optimize out array bound checks, inserting predicates when needed.
Reviewed-by:
*** 108,117 ****
--- 108,119 ----
class UnsafePrefetchWrite;
class ProfileCall;
class ProfileInvoke;
class RuntimeCall;
class MemBar;
+ class RangeCheckPredicate;
+ class Assert;
// A Value is a reference to the instruction creating the value
typedef Instruction* Value;
define_array(ValueArray, Value)
define_stack(Values, ValueArray)
*** 208,217 ****
--- 210,223 ----
virtual void do_UnsafePrefetchWrite(UnsafePrefetchWrite* x) = 0;
virtual void do_ProfileCall (ProfileCall* x) = 0;
virtual void do_ProfileInvoke (ProfileInvoke* x) = 0;
virtual void do_RuntimeCall (RuntimeCall* x) = 0;
virtual void do_MemBar (MemBar* x) = 0;
+ virtual void do_RangeCheckPredicate(RangeCheckPredicate* x) = 0;
+ #ifdef ASSERT
+ virtual void do_Assert (Assert* x) = 0;
+ #endif
};
// Hashing support
//
*** 304,315 ****
friend class UseCountComputer;
friend class BlockBegin;
void update_exception_state(ValueStack* state);
! //protected:
! public:
void set_type(ValueType* type) {
assert(type != NULL, "type must exist");
_type = type;
}
--- 310,322 ----
friend class UseCountComputer;
friend class BlockBegin;
void update_exception_state(ValueStack* state);
! protected:
! BlockBegin* _block; // Block that contains this instruction
!
void set_type(ValueType* type) {
assert(type != NULL, "type must exist");
_type = type;
}
*** 340,359 ****
UnorderedIsTrueFlag,
NeedsPatchingFlag,
ThrowIncompatibleClassChangeErrorFlag,
ProfileMDOFlag,
IsLinkedInBlockFlag,
InstructionLastFlag
};
public:
bool check_flag(InstructionFlag id) const { return (_flags & (1 << id)) != 0; }
void set_flag(InstructionFlag id, bool f) { _flags = f ? (_flags | (1 << id)) : (_flags & ~(1 << id)); };
// 'globally' used condition values
enum Condition {
! eql, neq, lss, leq, gtr, geq
};
// Instructions may be pinned for many reasons and under certain conditions
// with enough knowledge it's possible to safely unpin them.
enum PinReason {
--- 347,369 ----
UnorderedIsTrueFlag,
NeedsPatchingFlag,
ThrowIncompatibleClassChangeErrorFlag,
ProfileMDOFlag,
IsLinkedInBlockFlag,
+ NeedsRangeCheckFlag,
+ InWorkListFlag,
+ DeoptimizeOnException,
InstructionLastFlag
};
public:
bool check_flag(InstructionFlag id) const { return (_flags & (1 << id)) != 0; }
void set_flag(InstructionFlag id, bool f) { _flags = f ? (_flags | (1 << id)) : (_flags & ~(1 << id)); };
// 'globally' used condition values
enum Condition {
! eql, neq, lss, leq, gtr, geq, aeq, beq
};
// Instructions may be pinned for many reasons and under certain conditions
// with enough knowledge it's possible to safely unpin them.
enum PinReason {
*** 379,388 ****
--- 389,399 ----
, _printable_bci(-99)
#endif
, _pin_state(0)
, _type(type)
, _next(NULL)
+ , _block(NULL)
, _subst(NULL)
, _flags(0)
, _operand(LIR_OprFact::illegalOpr)
, _state_before(state_before)
, _exception_handlers(NULL)
*** 397,411 ****
#ifndef PRODUCT
bool has_printable_bci() const { return _printable_bci != -99; }
int printable_bci() const { assert(has_printable_bci(), "_printable_bci should have been set"); return _printable_bci; }
void set_printable_bci(int bci) { _printable_bci = bci; }
#endif
int use_count() const { return _use_count; }
int pin_state() const { return _pin_state; }
bool is_pinned() const { return _pin_state != 0 || PinAllInstructions; }
ValueType* type() const { return _type; }
! Instruction* prev(BlockBegin* block); // use carefully, expensive operation
Instruction* next() const { return _next; }
bool has_subst() const { return _subst != NULL; }
Instruction* subst() { return _subst == NULL ? this : _subst->subst(); }
LIR_Opr operand() const { return _operand; }
--- 408,424 ----
#ifndef PRODUCT
bool has_printable_bci() const { return _printable_bci != -99; }
int printable_bci() const { assert(has_printable_bci(), "_printable_bci should have been set"); return _printable_bci; }
void set_printable_bci(int bci) { _printable_bci = bci; }
#endif
+ int dominator_depth();
int use_count() const { return _use_count; }
int pin_state() const { return _pin_state; }
bool is_pinned() const { return _pin_state != 0 || PinAllInstructions; }
ValueType* type() const { return _type; }
! BlockBegin *block() const { return _block; }
! Instruction* prev(); // use carefully, expensive operation
Instruction* next() const { return _next; }
bool has_subst() const { return _subst != NULL; }
Instruction* subst() { return _subst == NULL ? this : _subst->subst(); }
LIR_Opr operand() const { return _operand; }
*** 430,439 ****
--- 443,455 ----
assert(next->has_printable_bci(), "_printable_bci should have been set");
assert(next != NULL, "must not be NULL");
assert(as_BlockEnd() == NULL, "BlockEnd instructions must have no next");
assert(next->can_be_linked(), "shouldn't link these instructions into list");
+ BlockBegin *block = this->block();
+ next->_block = block;
+
next->set_flag(Instruction::IsLinkedInBlockFlag, true);
_next = next;
return next;
}
*** 442,459 ****
--- 458,499 ----
next->set_printable_bci(bci);
#endif
return set_next(next);
}
+ // when blocks are merged
+ void fixup_block_pointers() {
+ Instruction *cur = next()->next(); // next()'s block is set in set_next
+ while (cur && cur->_block != block()) {
+ cur->_block = block();
+ cur = cur->next();
+ }
+ }
+
+ Instruction *insert_after(Instruction *i) {
+ Instruction* n = _next;
+ set_next(i);
+ i->set_next(n);
+ return _next;
+ }
+
+ Instruction *insert_after_same_bci(Instruction *i) {
+ #ifndef PRODUCT
+ i->set_printable_bci(printable_bci());
+ #endif
+ return insert_after(i);
+ }
+
void set_subst(Instruction* subst) {
assert(subst == NULL ||
type()->base() == subst->type()->base() ||
subst->type()->base() == illegalType, "type can't change");
_subst = subst;
}
void set_exception_handlers(XHandlers *xhandlers) { _exception_handlers = xhandlers; }
void set_exception_state(ValueStack* s) { check_state(s); _exception_state = s; }
+ void set_state_before(ValueStack* s) { check_state(s); _state_before = s; }
// machine-specifics
void set_operand(LIR_Opr operand) { assert(operand != LIR_OprFact::illegalOpr, "operand must exist"); _operand = operand; }
void clear_operand() { _operand = LIR_OprFact::illegalOpr; }
*** 507,516 ****
--- 547,561 ----
virtual Base* as_Base() { return NULL; }
virtual RoundFP* as_RoundFP() { return NULL; }
virtual ExceptionObject* as_ExceptionObject() { return NULL; }
virtual UnsafeOp* as_UnsafeOp() { return NULL; }
virtual ProfileInvoke* as_ProfileInvoke() { return NULL; }
+ virtual RangeCheckPredicate* as_RangeCheckPredicate() { return NULL; }
+
+ #ifndef PRODUCT
+ virtual Assert* as_Assert() { return NULL; }
+ #endif
virtual void visit(InstructionVisitor* v) = 0;
virtual bool can_trap() const { return false; }
*** 568,588 ****
// the value of a local variable at the beginning of a join block.
// A Phi consists of n operands, one for every incoming branch.
LEAF(Phi, Instruction)
private:
- BlockBegin* _block; // the block to which the phi function belongs
int _pf_flags; // the flags of the phi function
int _index; // to value on operand stack (index < 0) or to local
public:
// creation
Phi(ValueType* type, BlockBegin* b, int index)
: Instruction(type->base())
, _pf_flags(0)
- , _block(b)
, _index(index)
{
NOT_PRODUCT(set_printable_bci(Value(b)->printable_bci()));
if (type->is_illegal()) {
make_illegal();
}
}
--- 613,632 ----
// the value of a local variable at the beginning of a join block.
// A Phi consists of n operands, one for every incoming branch.
LEAF(Phi, Instruction)
private:
int _pf_flags; // the flags of the phi function
int _index; // to value on operand stack (index < 0) or to local
public:
// creation
Phi(ValueType* type, BlockBegin* b, int index)
: Instruction(type->base())
, _pf_flags(0)
, _index(index)
{
+ _block = b;
NOT_PRODUCT(set_printable_bci(Value(b)->printable_bci()));
if (type->is_illegal()) {
make_illegal();
}
}
*** 601,612 ****
int stack_index() const { assert(is_on_stack(), ""); return -(_index+1); }
Value operand_at(int i) const;
int operand_count() const;
- BlockBegin* block() const { return _block; }
-
void set(Flag f) { _pf_flags |= f; }
void clear(Flag f) { _pf_flags &= ~f; }
bool is_set(Flag f) const { return (_pf_flags & f) != 0; }
// Invalidates phis corresponding to merges of locals of two different types
--- 645,654 ----
*** 668,677 ****
--- 710,720 ----
assert(type->is_constant(), "must be a constant");
// since it's patching it needs to be pinned
pin();
}
+ // generic
virtual bool can_trap() const { return state_before() != NULL; }
virtual void input_values_do(ValueVisitor* f) { /* no values */ }
virtual intx hash() const;
virtual bool is_equal(Value v) const;
*** 850,867 ****
--- 893,912 ----
: AccessArray(as_ValueType(elt_type), array, state_before)
, _index(index)
, _length(length)
, _elt_type(elt_type)
{
+ set_flag(Instruction::NeedsRangeCheckFlag, true);
ASSERT_VALUES
}
// accessors
Value index() const { return _index; }
Value length() const { return _length; }
BasicType elt_type() const { return _elt_type; }
+ void clear_length() { _length = NULL; }
// perform elimination of range checks involving constants
bool compute_needs_range_check();
// generic
virtual void input_values_do(ValueVisitor* f) { AccessArray::input_values_do(f); f->visit(&_index); if (_length != NULL) f->visit(&_length); }
*** 1522,1531 ****
--- 1567,1577 ----
private:
int _block_id; // the unique block id
int _bci; // start-bci of block
int _depth_first_number; // number of this block in a depth-first ordering
int _linear_scan_number; // number of this block in linear-scan ordering
+ int _dominator_depth;
int _loop_depth; // the loop nesting level of this block
int _loop_index; // number of the innermost loop of this block
int _flags; // the flags associated with this block
// fields used by BlockListBuilder
*** 1533,1542 ****
--- 1579,1589 ----
BitMap _stores_to_locals; // bit is set when a local variable is stored in the block
// SSA specific fields: (factor out later)
BlockList _successors; // the successors of this block
BlockList _predecessors; // the predecessors of this block
+ BlockList _dominates; // list of blocks that are dominated by this block
BlockBegin* _dominator; // the dominator of this block
// SSA specific ends
BlockEnd* _end; // the last instruction of this block
BlockList _exception_handlers; // the exception handlers potentially invoked by this block
ValueStackStack* _exception_states; // only for xhandler entries: states of all instructions that have an edge to this xhandler
*** 1581,1594 ****
--- 1628,1643 ----
, _bci(bci)
, _depth_first_number(-1)
, _linear_scan_number(-1)
, _loop_depth(0)
, _flags(0)
+ , _dominator_depth(-1)
, _dominator(NULL)
, _end(NULL)
, _predecessors(2)
, _successors(2)
+ , _dominates(2)
, _exception_handlers(1)
, _exception_states(NULL)
, _exception_handler_pco(-1)
, _lir(NULL)
, _loop_index(-1)
*** 1601,1621 ****
--- 1650,1673 ----
, _first_lir_instruction_id(-1)
, _last_lir_instruction_id(-1)
, _total_preds(0)
, _stores_to_locals()
{
+ _block = this;
#ifndef PRODUCT
set_printable_bci(bci);
#endif
}
// accessors
int block_id() const { return _block_id; }
int bci() const { return _bci; }
BlockList* successors() { return &_successors; }
+ BlockList* dominates() { return &_dominates; }
BlockBegin* dominator() const { return _dominator; }
int loop_depth() const { return _loop_depth; }
+ int dominator_depth() const { return _dominator_depth; }
int depth_first_number() const { return _depth_first_number; }
int linear_scan_number() const { return _linear_scan_number; }
BlockEnd* end() const { return _end; }
Label* label() { return &_label; }
LIR_List* lir() const { return _lir; }
*** 1632,1641 ****
--- 1684,1694 ----
BitMap& stores_to_locals() { return _stores_to_locals; }
// manipulation
void set_dominator(BlockBegin* dom) { _dominator = dom; }
void set_loop_depth(int d) { _loop_depth = d; }
+ void set_dominator_depth(int d) { _dominator_depth = d; }
void set_depth_first_number(int dfn) { _depth_first_number = dfn; }
void set_linear_scan_number(int lsn) { _linear_scan_number = lsn; }
void set_end(BlockEnd* end);
void clear_end();
void disconnect_from_graph();
*** 1693,1703 ****
is_on_work_list_flag = 1 << 5,
was_visited_flag = 1 << 6,
parser_loop_header_flag = 1 << 7, // set by parser to identify blocks where phi functions can not be created on demand
critical_edge_split_flag = 1 << 8, // set for all blocks that are introduced when critical edges are split
linear_scan_loop_header_flag = 1 << 9, // set during loop-detection for LinearScan
! linear_scan_loop_end_flag = 1 << 10 // set during loop-detection for LinearScan
};
void set(Flag f) { _flags |= f; }
void clear(Flag f) { _flags &= ~f; }
bool is_set(Flag f) const { return (_flags & f) != 0; }
--- 1746,1757 ----
is_on_work_list_flag = 1 << 5,
was_visited_flag = 1 << 6,
parser_loop_header_flag = 1 << 7, // set by parser to identify blocks where phi functions can not be created on demand
critical_edge_split_flag = 1 << 8, // set for all blocks that are introduced when critical edges are split
linear_scan_loop_header_flag = 1 << 9, // set during loop-detection for LinearScan
! linear_scan_loop_end_flag = 1 << 10, // set during loop-detection for LinearScan
! donot_eliminate_range_checks = 1 << 11 // Should be try to eliminate range checks in this block
};
void set(Flag f) { _flags |= f; }
void clear(Flag f) { _flags &= ~f; }
bool is_set(Flag f) const { return (_flags & f) != 0; }
*** 1726,1736 ****
};
BASE(BlockEnd, StateSplit)
private:
- BlockBegin* _begin;
BlockList* _sux;
protected:
BlockList* sux() const { return _sux; }
--- 1780,1789 ----
*** 1744,1762 ****
public:
// creation
BlockEnd(ValueType* type, ValueStack* state_before, bool is_safepoint)
: StateSplit(type, state_before)
- , _begin(NULL)
, _sux(NULL)
{
set_flag(IsSafepointFlag, is_safepoint);
}
// accessors
bool is_safepoint() const { return check_flag(IsSafepointFlag); }
! BlockBegin* begin() const { return _begin; }
// manipulation
void set_begin(BlockBegin* begin);
// successors
--- 1797,1815 ----
public:
// creation
BlockEnd(ValueType* type, ValueStack* state_before, bool is_safepoint)
: StateSplit(type, state_before)
, _sux(NULL)
{
set_flag(IsSafepointFlag, is_safepoint);
}
// accessors
bool is_safepoint() const { return check_flag(IsSafepointFlag); }
! // For compatibility with old code, for new code use block()
! BlockBegin* begin() const { return _block; }
// manipulation
void set_begin(BlockBegin* begin);
// successors
*** 1809,1818 ****
--- 1862,1941 ----
void set_profiled_method(ciMethod* method) { _profiled_method = method; }
void set_profiled_bci(int bci) { _profiled_bci = bci; }
void set_direction(Direction d) { _direction = d; }
};
+ #ifndef PRODUCT
+
+ LEAF(Assert, Instruction)
+ private:
+ Value _x;
+ Condition _cond;
+ Value _y;
+ char *_message;
+
+ public:
+ // creation
+ // unordered_is_true is valid for float/double compares only
+ Assert(Value x, Condition cond, bool unordered_is_true, Value y);
+
+ // accessors
+ Value x() const { return _x; }
+ Condition cond() const { return _cond; }
+ bool unordered_is_true() const { return check_flag(UnorderedIsTrueFlag); }
+ Value y() const { return _y; }
+ const char *message() const { return _message; }
+
+ // generic
+ virtual void input_values_do(ValueVisitor* f) { f->visit(&_x); f->visit(&_y); }
+ };
+
+ #endif
+
+ LEAF(RangeCheckPredicate, StateSplit)
+ private:
+ Value _x;
+ Condition _cond;
+ Value _y;
+
+ void check_state();
+
+ public:
+ // creation
+ // unordered_is_true is valid for float/double compares only
+ RangeCheckPredicate(Value x, Condition cond, bool unordered_is_true, Value y, ValueStack* state) : StateSplit(illegalType)
+ , _x(x)
+ , _cond(cond)
+ , _y(y)
+ {
+ ASSERT_VALUES
+ set_flag(UnorderedIsTrueFlag, unordered_is_true);
+ assert(x->type()->tag() == y->type()->tag(), "types must match");
+ this->set_state(state);
+ check_state();
+ }
+
+ // Always deoptimize
+ RangeCheckPredicate(ValueStack* state) : StateSplit(illegalType)
+ {
+ this->set_state(state);
+ _x = _y = NULL;
+ check_state();
+ }
+
+ // accessors
+ Value x() const { return _x; }
+ Condition cond() const { return _cond; }
+ bool unordered_is_true() const { return check_flag(UnorderedIsTrueFlag); }
+ Value y() const { return _y; }
+
+ void always_fail() { _x = _y = NULL; }
+
+ // generic
+ virtual void input_values_do(ValueVisitor* f) { StateSplit::input_values_do(f); f->visit(&_x); f->visit(&_y); }
+ HASHING3(RangeCheckPredicate, true, x()->subst(), y()->subst(), cond())
+ };
LEAF(If, BlockEnd)
private:
Value _x;
Condition _cond;