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:


  93 class         LookupSwitch;
  94 class       Return;
  95 class       Throw;
  96 class       Base;
  97 class   RoundFP;
  98 class   UnsafeOp;
  99 class     UnsafeRawOp;
 100 class       UnsafeGetRaw;
 101 class       UnsafePutRaw;
 102 class     UnsafeObjectOp;
 103 class       UnsafeGetObject;
 104 class       UnsafePutObject;
 105 class         UnsafeGetAndSetObject;
 106 class       UnsafePrefetch;
 107 class         UnsafePrefetchRead;
 108 class         UnsafePrefetchWrite;
 109 class   ProfileCall;
 110 class   ProfileInvoke;
 111 class   RuntimeCall;
 112 class   MemBar;


 113 
 114 // A Value is a reference to the instruction creating the value
 115 typedef Instruction* Value;
 116 define_array(ValueArray, Value)
 117 define_stack(Values, ValueArray)
 118 
 119 define_array(ValueStackArray, ValueStack*)
 120 define_stack(ValueStackStack, ValueStackArray)
 121 
 122 // BlockClosure is the base class for block traversal/iteration.
 123 
 124 class BlockClosure: public CompilationResourceObj {
 125  public:
 126   virtual void block_do(BlockBegin* block)       = 0;
 127 };
 128 
 129 
 130 // A simple closure class for visiting the values of an Instruction
 131 class ValueVisitor: public StackObj {
 132  public:


 193   virtual void do_IfInstanceOf   (IfInstanceOf*    x) = 0;
 194   virtual void do_TableSwitch    (TableSwitch*     x) = 0;
 195   virtual void do_LookupSwitch   (LookupSwitch*    x) = 0;
 196   virtual void do_Return         (Return*          x) = 0;
 197   virtual void do_Throw          (Throw*           x) = 0;
 198   virtual void do_Base           (Base*            x) = 0;
 199   virtual void do_OsrEntry       (OsrEntry*        x) = 0;
 200   virtual void do_ExceptionObject(ExceptionObject* x) = 0;
 201   virtual void do_RoundFP        (RoundFP*         x) = 0;
 202   virtual void do_UnsafeGetRaw   (UnsafeGetRaw*    x) = 0;
 203   virtual void do_UnsafePutRaw   (UnsafePutRaw*    x) = 0;
 204   virtual void do_UnsafeGetObject(UnsafeGetObject* x) = 0;
 205   virtual void do_UnsafePutObject(UnsafePutObject* x) = 0;
 206   virtual void do_UnsafeGetAndSetObject(UnsafeGetAndSetObject* x) = 0;
 207   virtual void do_UnsafePrefetchRead (UnsafePrefetchRead*  x) = 0;
 208   virtual void do_UnsafePrefetchWrite(UnsafePrefetchWrite* x) = 0;
 209   virtual void do_ProfileCall    (ProfileCall*     x) = 0;
 210   virtual void do_ProfileInvoke  (ProfileInvoke*   x) = 0;
 211   virtual void do_RuntimeCall    (RuntimeCall*     x) = 0;
 212   virtual void do_MemBar         (MemBar*          x) = 0;




 213 };
 214 
 215 
 216 // Hashing support
 217 //
 218 // Note: This hash functions affect the performance
 219 //       of ValueMap - make changes carefully!
 220 
 221 #define HASH1(x1            )                    ((intx)(x1))
 222 #define HASH2(x1, x2        )                    ((HASH1(x1        ) << 7) ^ HASH1(x2))
 223 #define HASH3(x1, x2, x3    )                    ((HASH2(x1, x2    ) << 7) ^ HASH1(x3))
 224 #define HASH4(x1, x2, x3, x4)                    ((HASH3(x1, x2, x3) << 7) ^ HASH1(x4))
 225 
 226 
 227 // The following macros are used to implement instruction-specific hashing.
 228 // By default, each instruction implements hash() and is_equal(Value), used
 229 // for value numbering/common subexpression elimination. The default imple-
 230 // mentation disables value numbering. Each instruction which can be value-
 231 // numbered, should define corresponding hash() and is_equal(Value) functions
 232 // via the macros below. The f arguments specify all the values/op codes, etc.


 289 #ifndef PRODUCT
 290   int          _printable_bci;                   // the bci of the instruction for printing
 291 #endif
 292   int          _use_count;                       // the number of instructions refering to this value (w/o prev/next); only roots can have use count = 0 or > 1
 293   int          _pin_state;                       // set of PinReason describing the reason for pinning
 294   ValueType*   _type;                            // the instruction value type
 295   Instruction* _next;                            // the next instruction if any (NULL for BlockEnd instructions)
 296   Instruction* _subst;                           // the substitution instruction if any
 297   LIR_Opr      _operand;                         // LIR specific information
 298   unsigned int _flags;                           // Flag bits
 299 
 300   ValueStack*  _state_before;                    // Copy of state with input operands still on stack (or NULL)
 301   ValueStack*  _exception_state;                 // Copy of state for exception handling
 302   XHandlers*   _exception_handlers;              // Flat list of exception handlers covering this instruction
 303 
 304   friend class UseCountComputer;
 305   friend class BlockBegin;
 306 
 307   void update_exception_state(ValueStack* state);
 308 
 309  //protected:
 310  public:

 311   void set_type(ValueType* type) {
 312     assert(type != NULL, "type must exist");
 313     _type = type;
 314   }
 315 
 316  public:
 317   void* operator new(size_t size) {
 318     Compilation* c = Compilation::current();
 319     void* res = c->arena()->Amalloc(size);
 320     ((Instruction*)res)->_id = c->get_next_id();
 321     return res;
 322   }
 323 
 324   static const int no_bci = -99;
 325 
 326   enum InstructionFlag {
 327     NeedsNullCheckFlag = 0,
 328     CanTrapFlag,
 329     DirectCompareFlag,
 330     IsEliminatedFlag,
 331     IsSafepointFlag,
 332     IsStaticFlag,
 333     IsStrictfpFlag,
 334     NeedsStoreCheckFlag,
 335     NeedsWriteBarrierFlag,
 336     PreservesStateFlag,
 337     TargetIsFinalFlag,
 338     TargetIsLoadedFlag,
 339     TargetIsStrictfpFlag,
 340     UnorderedIsTrueFlag,
 341     NeedsPatchingFlag,
 342     ThrowIncompatibleClassChangeErrorFlag,
 343     ProfileMDOFlag,
 344     IsLinkedInBlockFlag,



 345     InstructionLastFlag
 346   };
 347 
 348  public:
 349   bool check_flag(InstructionFlag id) const      { return (_flags & (1 << id)) != 0;    }
 350   void set_flag(InstructionFlag id, bool f)      { _flags = f ? (_flags | (1 << id)) : (_flags & ~(1 << id)); };
 351 
 352   // 'globally' used condition values
 353   enum Condition {
 354     eql, neq, lss, leq, gtr, geq
 355   };
 356 
 357   // Instructions may be pinned for many reasons and under certain conditions
 358   // with enough knowledge it's possible to safely unpin them.
 359   enum PinReason {
 360       PinUnknown           = 1 << 0
 361     , PinExplicitNullCheck = 1 << 3
 362     , PinStackForStateSplit= 1 << 12
 363     , PinStateSplitConstructor= 1 << 13
 364     , PinGlobalValueNumbering= 1 << 14
 365   };
 366 
 367   static Condition mirror(Condition cond);
 368   static Condition negate(Condition cond);
 369 
 370   // initialization
 371   static int number_of_instructions() {
 372     return Compilation::current()->number_of_instructions();
 373   }
 374 
 375   // creation
 376   Instruction(ValueType* type, ValueStack* state_before = NULL, bool type_is_constant = false)
 377   : _use_count(0)
 378 #ifndef PRODUCT
 379   , _printable_bci(-99)
 380 #endif
 381   , _pin_state(0)
 382   , _type(type)
 383   , _next(NULL)

 384   , _subst(NULL)
 385   , _flags(0)
 386   , _operand(LIR_OprFact::illegalOpr)
 387   , _state_before(state_before)
 388   , _exception_handlers(NULL)
 389   {
 390     check_state(state_before);
 391     assert(type != NULL && (!type->is_constant() || type_is_constant), "type must exist");
 392     update_exception_state(_state_before);
 393   }
 394 
 395   // accessors
 396   int id() const                                 { return _id; }
 397 #ifndef PRODUCT
 398   bool has_printable_bci() const                 { return _printable_bci != -99; }
 399   int printable_bci() const                      { assert(has_printable_bci(), "_printable_bci should have been set"); return _printable_bci; }
 400   void set_printable_bci(int bci)                { _printable_bci = bci; }
 401 #endif

 402   int use_count() const                          { return _use_count; }
 403   int pin_state() const                          { return _pin_state; }
 404   bool is_pinned() const                         { return _pin_state != 0 || PinAllInstructions; }
 405   ValueType* type() const                        { return _type; }
 406   Instruction* prev(BlockBegin* block);          // use carefully, expensive operation

 407   Instruction* next() const                      { return _next; }
 408   bool has_subst() const                         { return _subst != NULL; }
 409   Instruction* subst()                           { return _subst == NULL ? this : _subst->subst(); }
 410   LIR_Opr operand() const                        { return _operand; }
 411 
 412   void set_needs_null_check(bool f)              { set_flag(NeedsNullCheckFlag, f); }
 413   bool needs_null_check() const                  { return check_flag(NeedsNullCheckFlag); }
 414   bool is_linked() const                         { return check_flag(IsLinkedInBlockFlag); }
 415   bool can_be_linked()                           { return as_Local() == NULL && as_Phi() == NULL; }
 416 
 417   bool has_uses() const                          { return use_count() > 0; }
 418   ValueStack* state_before() const               { return _state_before; }
 419   ValueStack* exception_state() const            { return _exception_state; }
 420   virtual bool needs_exception_state() const     { return true; }
 421   XHandlers* exception_handlers() const          { return _exception_handlers; }
 422 
 423   // manipulation
 424   void pin(PinReason reason)                     { _pin_state |= reason; }
 425   void pin()                                     { _pin_state |= PinUnknown; }
 426   // DANGEROUS: only used by EliminateStores
 427   void unpin(PinReason reason)                   { assert((reason & PinUnknown) == 0, "can't unpin unknown state"); _pin_state &= ~reason; }
 428 
 429   Instruction* set_next(Instruction* next) {
 430     assert(next->has_printable_bci(), "_printable_bci should have been set");
 431     assert(next != NULL, "must not be NULL");
 432     assert(as_BlockEnd() == NULL, "BlockEnd instructions must have no next");
 433     assert(next->can_be_linked(), "shouldn't link these instructions into list");
 434 



 435     next->set_flag(Instruction::IsLinkedInBlockFlag, true);
 436     _next = next;
 437     return next;
 438   }
 439 
 440   Instruction* set_next(Instruction* next, int bci) {
 441 #ifndef PRODUCT
 442     next->set_printable_bci(bci);
 443 #endif
 444     return set_next(next);
 445   }
 446 























 447   void set_subst(Instruction* subst)             {
 448     assert(subst == NULL ||
 449            type()->base() == subst->type()->base() ||
 450            subst->type()->base() == illegalType, "type can't change");
 451     _subst = subst;
 452   }
 453   void set_exception_handlers(XHandlers *xhandlers) { _exception_handlers = xhandlers; }
 454   void set_exception_state(ValueStack* s)        { check_state(s); _exception_state = s; }

 455 
 456   // machine-specifics
 457   void set_operand(LIR_Opr operand)              { assert(operand != LIR_OprFact::illegalOpr, "operand must exist"); _operand = operand; }
 458   void clear_operand()                           { _operand = LIR_OprFact::illegalOpr; }
 459 
 460   // generic
 461   virtual Instruction*      as_Instruction()     { return this; } // to satisfy HASHING1 macro
 462   virtual Phi*              as_Phi()             { return NULL; }
 463   virtual Local*            as_Local()           { return NULL; }
 464   virtual Constant*         as_Constant()        { return NULL; }
 465   virtual AccessField*      as_AccessField()     { return NULL; }
 466   virtual LoadField*        as_LoadField()       { return NULL; }
 467   virtual StoreField*       as_StoreField()      { return NULL; }
 468   virtual AccessArray*      as_AccessArray()     { return NULL; }
 469   virtual ArrayLength*      as_ArrayLength()     { return NULL; }
 470   virtual AccessIndexed*    as_AccessIndexed()   { return NULL; }
 471   virtual LoadIndexed*      as_LoadIndexed()     { return NULL; }
 472   virtual StoreIndexed*     as_StoreIndexed()    { return NULL; }
 473   virtual NegateOp*         as_NegateOp()        { return NULL; }
 474   virtual Op2*              as_Op2()             { return NULL; }


 492   virtual InstanceOf*       as_InstanceOf()      { return NULL; }
 493   virtual TypeCast*         as_TypeCast()        { return NULL; }
 494   virtual AccessMonitor*    as_AccessMonitor()   { return NULL; }
 495   virtual MonitorEnter*     as_MonitorEnter()    { return NULL; }
 496   virtual MonitorExit*      as_MonitorExit()     { return NULL; }
 497   virtual Intrinsic*        as_Intrinsic()       { return NULL; }
 498   virtual BlockBegin*       as_BlockBegin()      { return NULL; }
 499   virtual BlockEnd*         as_BlockEnd()        { return NULL; }
 500   virtual Goto*             as_Goto()            { return NULL; }
 501   virtual If*               as_If()              { return NULL; }
 502   virtual IfInstanceOf*     as_IfInstanceOf()    { return NULL; }
 503   virtual TableSwitch*      as_TableSwitch()     { return NULL; }
 504   virtual LookupSwitch*     as_LookupSwitch()    { return NULL; }
 505   virtual Return*           as_Return()          { return NULL; }
 506   virtual Throw*            as_Throw()           { return NULL; }
 507   virtual Base*             as_Base()            { return NULL; }
 508   virtual RoundFP*          as_RoundFP()         { return NULL; }
 509   virtual ExceptionObject*  as_ExceptionObject() { return NULL; }
 510   virtual UnsafeOp*         as_UnsafeOp()        { return NULL; }
 511   virtual ProfileInvoke*    as_ProfileInvoke()   { return NULL; }





 512 
 513   virtual void visit(InstructionVisitor* v)      = 0;
 514 
 515   virtual bool can_trap() const                  { return false; }
 516 
 517   virtual void input_values_do(ValueVisitor* f)   = 0;
 518   virtual void state_values_do(ValueVisitor* f);
 519   virtual void other_values_do(ValueVisitor* f)   { /* usually no other - override on demand */ }
 520           void       values_do(ValueVisitor* f)   { input_values_do(f); state_values_do(f); other_values_do(f); }
 521 
 522   virtual ciType* exact_type() const             { return NULL; }
 523   virtual ciType* declared_type() const          { return NULL; }
 524 
 525   // hashing
 526   virtual const char* name() const               = 0;
 527   HASHING1(Instruction, false, id())             // hashing disabled by default
 528 
 529   // debugging
 530   static void check_state(ValueStack* state)     PRODUCT_RETURN;
 531   void print()                                   PRODUCT_RETURN;


 553 
 554 // Debugging support
 555 
 556 
 557 #ifdef ASSERT
 558 class AssertValues: public ValueVisitor {
 559   void visit(Value* x)             { assert((*x) != NULL, "value must exist"); }
 560 };
 561   #define ASSERT_VALUES                          { AssertValues assert_value; values_do(&assert_value); }
 562 #else
 563   #define ASSERT_VALUES
 564 #endif // ASSERT
 565 
 566 
 567 // A Phi is a phi function in the sense of SSA form. It stands for
 568 // the value of a local variable at the beginning of a join block.
 569 // A Phi consists of n operands, one for every incoming branch.
 570 
 571 LEAF(Phi, Instruction)
 572  private:
 573   BlockBegin* _block;    // the block to which the phi function belongs
 574   int         _pf_flags; // the flags of the phi function
 575   int         _index;    // to value on operand stack (index < 0) or to local
 576  public:
 577   // creation
 578   Phi(ValueType* type, BlockBegin* b, int index)
 579   : Instruction(type->base())
 580   , _pf_flags(0)
 581   , _block(b)
 582   , _index(index)
 583   {

 584     NOT_PRODUCT(set_printable_bci(Value(b)->printable_bci()));
 585     if (type->is_illegal()) {
 586       make_illegal();
 587     }
 588   }
 589 
 590   // flags
 591   enum Flag {
 592     no_flag         = 0,
 593     visited         = 1 << 0,
 594     cannot_simplify = 1 << 1
 595   };
 596 
 597   // accessors
 598   bool  is_local() const          { return _index >= 0; }
 599   bool  is_on_stack() const       { return !is_local(); }
 600   int   local_index() const       { assert(is_local(), ""); return _index; }
 601   int   stack_index() const       { assert(is_on_stack(), ""); return -(_index+1); }
 602 
 603   Value operand_at(int i) const;
 604   int   operand_count() const;
 605 
 606   BlockBegin* block() const       { return _block; }
 607 
 608   void   set(Flag f)              { _pf_flags |=  f; }
 609   void   clear(Flag f)            { _pf_flags &= ~f; }
 610   bool   is_set(Flag f) const     { return (_pf_flags & f) != 0; }
 611 
 612   // Invalidates phis corresponding to merges of locals of two different types
 613   // (these should never be referenced, otherwise the bytecodes are illegal)
 614   void   make_illegal() {
 615     set(cannot_simplify);
 616     set_type(illegalType);
 617   }
 618 
 619   bool is_illegal() const {
 620     return type()->is_illegal();
 621   }
 622 
 623   // generic
 624   virtual void input_values_do(ValueVisitor* f) {
 625   }
 626 };
 627 


 653 
 654 
 655 LEAF(Constant, Instruction)
 656  public:
 657   // creation
 658   Constant(ValueType* type):
 659       Instruction(type, NULL, /*type_is_constant*/ true)
 660   {
 661     assert(type->is_constant(), "must be a constant");
 662   }
 663 
 664   Constant(ValueType* type, ValueStack* state_before):
 665     Instruction(type, state_before, /*type_is_constant*/ true)
 666   {
 667     assert(state_before != NULL, "only used for constants which need patching");
 668     assert(type->is_constant(), "must be a constant");
 669     // since it's patching it needs to be pinned
 670     pin();
 671   }
 672 

 673   virtual bool can_trap() const                  { return state_before() != NULL; }
 674   virtual void input_values_do(ValueVisitor* f)   { /* no values */ }
 675 
 676   virtual intx hash() const;
 677   virtual bool is_equal(Value v) const;
 678 
 679   virtual ciType* exact_type() const;
 680 
 681   enum CompareResult { not_comparable = -1, cond_false, cond_true };
 682 
 683   virtual CompareResult compare(Instruction::Condition condition, Value right) const;
 684   BlockBegin* compare(Instruction::Condition cond, Value right,
 685                       BlockBegin* true_sux, BlockBegin* false_sux) const {
 686     switch (compare(cond, right)) {
 687     case not_comparable:
 688       return NULL;
 689     case cond_false:
 690       return false_sux;
 691     case cond_true:
 692       return true_sux;


 835 
 836   // generic
 837   HASHING1(ArrayLength, true, array()->subst())
 838 };
 839 
 840 
 841 BASE(AccessIndexed, AccessArray)
 842  private:
 843   Value     _index;
 844   Value     _length;
 845   BasicType _elt_type;
 846 
 847  public:
 848   // creation
 849   AccessIndexed(Value array, Value index, Value length, BasicType elt_type, ValueStack* state_before)
 850   : AccessArray(as_ValueType(elt_type), array, state_before)
 851   , _index(index)
 852   , _length(length)
 853   , _elt_type(elt_type)
 854   {

 855     ASSERT_VALUES
 856   }
 857 
 858   // accessors
 859   Value index() const                            { return _index; }
 860   Value length() const                           { return _length; }
 861   BasicType elt_type() const                     { return _elt_type; }
 862 

 863   // perform elimination of range checks involving constants
 864   bool compute_needs_range_check();
 865 
 866   // generic
 867   virtual void input_values_do(ValueVisitor* f)   { AccessArray::input_values_do(f); f->visit(&_index); if (_length != NULL) f->visit(&_length); }
 868 };
 869 
 870 
 871 LEAF(LoadIndexed, AccessIndexed)
 872  private:
 873   NullCheck*  _explicit_null_check;              // For explicit null check elimination
 874 
 875  public:
 876   // creation
 877   LoadIndexed(Value array, Value index, Value length, BasicType elt_type, ValueStack* state_before)
 878   : AccessIndexed(array, index, length, elt_type, state_before)
 879   , _explicit_null_check(NULL) {}
 880 
 881   // accessors
 882   NullCheck* explicit_null_check() const         { return _explicit_null_check; }


1507     }
1508   }
1509 
1510   // generic
1511   virtual bool can_trap() const                  { return check_flag(CanTrapFlag); }
1512   virtual void input_values_do(ValueVisitor* f) {
1513     StateSplit::input_values_do(f);
1514     for (int i = 0; i < _args->length(); i++) f->visit(_args->adr_at(i));
1515   }
1516 };
1517 
1518 
1519 class LIR_List;
1520 
1521 LEAF(BlockBegin, StateSplit)
1522  private:
1523   int        _block_id;                          // the unique block id
1524   int        _bci;                               // start-bci of block
1525   int        _depth_first_number;                // number of this block in a depth-first ordering
1526   int        _linear_scan_number;                // number of this block in linear-scan ordering

1527   int        _loop_depth;                        // the loop nesting level of this block
1528   int        _loop_index;                        // number of the innermost loop of this block
1529   int        _flags;                             // the flags associated with this block
1530 
1531   // fields used by BlockListBuilder
1532   int        _total_preds;                       // number of predecessors found by BlockListBuilder
1533   BitMap     _stores_to_locals;                  // bit is set when a local variable is stored in the block
1534 
1535   // SSA specific fields: (factor out later)
1536   BlockList   _successors;                       // the successors of this block
1537   BlockList   _predecessors;                     // the predecessors of this block

1538   BlockBegin* _dominator;                        // the dominator of this block
1539   // SSA specific ends
1540   BlockEnd*  _end;                               // the last instruction of this block
1541   BlockList  _exception_handlers;                // the exception handlers potentially invoked by this block
1542   ValueStackStack* _exception_states;            // only for xhandler entries: states of all instructions that have an edge to this xhandler
1543   int        _exception_handler_pco;             // if this block is the start of an exception handler,
1544                                                  // this records the PC offset in the assembly code of the
1545                                                  // first instruction in this block
1546   Label      _label;                             // the label associated with this block
1547   LIR_List*  _lir;                               // the low level intermediate representation for this block
1548 
1549   BitMap      _live_in;                          // set of live LIR_Opr registers at entry to this block
1550   BitMap      _live_out;                         // set of live LIR_Opr registers at exit from this block
1551   BitMap      _live_gen;                         // set of registers used before any redefinition in this block
1552   BitMap      _live_kill;                        // set of registers defined in this block
1553 
1554   BitMap      _fpu_register_usage;
1555   intArray*   _fpu_stack_state;                  // For x86 FPU code generation with UseLinearScan
1556   int         _first_lir_instruction_id;         // ID of first LIR instruction in this block
1557   int         _last_lir_instruction_id;          // ID of last LIR instruction in this block


1566     Compilation* c = Compilation::current();
1567     void* res = c->arena()->Amalloc(size);
1568     ((BlockBegin*)res)->_id = c->get_next_id();
1569     ((BlockBegin*)res)->_block_id = c->get_next_block_id();
1570     return res;
1571   }
1572 
1573   // initialization/counting
1574   static int  number_of_blocks() {
1575     return Compilation::current()->number_of_blocks();
1576   }
1577 
1578   // creation
1579   BlockBegin(int bci)
1580   : StateSplit(illegalType)
1581   , _bci(bci)
1582   , _depth_first_number(-1)
1583   , _linear_scan_number(-1)
1584   , _loop_depth(0)
1585   , _flags(0)

1586   , _dominator(NULL)
1587   , _end(NULL)
1588   , _predecessors(2)
1589   , _successors(2)

1590   , _exception_handlers(1)
1591   , _exception_states(NULL)
1592   , _exception_handler_pco(-1)
1593   , _lir(NULL)
1594   , _loop_index(-1)
1595   , _live_in()
1596   , _live_out()
1597   , _live_gen()
1598   , _live_kill()
1599   , _fpu_register_usage()
1600   , _fpu_stack_state(NULL)
1601   , _first_lir_instruction_id(-1)
1602   , _last_lir_instruction_id(-1)
1603   , _total_preds(0)
1604   , _stores_to_locals()
1605   {

1606 #ifndef PRODUCT
1607     set_printable_bci(bci);
1608 #endif
1609   }
1610 
1611   // accessors
1612   int block_id() const                           { return _block_id; }
1613   int bci() const                                { return _bci; }
1614   BlockList* successors()                        { return &_successors; }

1615   BlockBegin* dominator() const                  { return _dominator; }
1616   int loop_depth() const                         { return _loop_depth; }

1617   int depth_first_number() const                 { return _depth_first_number; }
1618   int linear_scan_number() const                 { return _linear_scan_number; }
1619   BlockEnd* end() const                          { return _end; }
1620   Label* label()                                 { return &_label; }
1621   LIR_List* lir() const                          { return _lir; }
1622   int exception_handler_pco() const              { return _exception_handler_pco; }
1623   BitMap& live_in()                              { return _live_in;        }
1624   BitMap& live_out()                             { return _live_out;       }
1625   BitMap& live_gen()                             { return _live_gen;       }
1626   BitMap& live_kill()                            { return _live_kill;      }
1627   BitMap& fpu_register_usage()                   { return _fpu_register_usage; }
1628   intArray* fpu_stack_state() const              { return _fpu_stack_state;    }
1629   int first_lir_instruction_id() const           { return _first_lir_instruction_id; }
1630   int last_lir_instruction_id() const            { return _last_lir_instruction_id; }
1631   int total_preds() const                        { return _total_preds; }
1632   BitMap& stores_to_locals()                     { return _stores_to_locals; }
1633 
1634   // manipulation
1635   void set_dominator(BlockBegin* dom)            { _dominator = dom; }
1636   void set_loop_depth(int d)                     { _loop_depth = d; }

1637   void set_depth_first_number(int dfn)           { _depth_first_number = dfn; }
1638   void set_linear_scan_number(int lsn)           { _linear_scan_number = lsn; }
1639   void set_end(BlockEnd* end);
1640   void clear_end();
1641   void disconnect_from_graph();
1642   static void disconnect_edge(BlockBegin* from, BlockBegin* to);
1643   BlockBegin* insert_block_between(BlockBegin* sux);
1644   void substitute_sux(BlockBegin* old_sux, BlockBegin* new_sux);
1645   void set_lir(LIR_List* lir)                    { _lir = lir; }
1646   void set_exception_handler_pco(int pco)        { _exception_handler_pco = pco; }
1647   void set_live_in       (BitMap map)            { _live_in = map;        }
1648   void set_live_out      (BitMap map)            { _live_out = map;       }
1649   void set_live_gen      (BitMap map)            { _live_gen = map;       }
1650   void set_live_kill     (BitMap map)            { _live_kill = map;      }
1651   void set_fpu_register_usage(BitMap map)        { _fpu_register_usage = map; }
1652   void set_fpu_stack_state(intArray* state)      { _fpu_stack_state = state;  }
1653   void set_first_lir_instruction_id(int id)      { _first_lir_instruction_id = id;  }
1654   void set_last_lir_instruction_id(int id)       { _last_lir_instruction_id = id;  }
1655   void increment_total_preds(int n = 1)          { _total_preds += n; }
1656   void init_stores_to_locals(int locals_count)   { _stores_to_locals = BitMap(locals_count); _stores_to_locals.clear(); }


1678   BlockBegin* exception_handler_at(int i) const  { return _exception_handlers.at(i); }
1679 
1680   // states of the instructions that have an edge to this exception handler
1681   int number_of_exception_states()               { assert(is_set(exception_entry_flag), "only for xhandlers"); return _exception_states == NULL ? 0 : _exception_states->length(); }
1682   ValueStack* exception_state_at(int idx) const  { assert(is_set(exception_entry_flag), "only for xhandlers"); return _exception_states->at(idx); }
1683   int add_exception_state(ValueStack* state);
1684 
1685   // flags
1686   enum Flag {
1687     no_flag                       = 0,
1688     std_entry_flag                = 1 << 0,
1689     osr_entry_flag                = 1 << 1,
1690     exception_entry_flag          = 1 << 2,
1691     subroutine_entry_flag         = 1 << 3,
1692     backward_branch_target_flag   = 1 << 4,
1693     is_on_work_list_flag          = 1 << 5,
1694     was_visited_flag              = 1 << 6,
1695     parser_loop_header_flag       = 1 << 7,  // set by parser to identify blocks where phi functions can not be created on demand
1696     critical_edge_split_flag      = 1 << 8, // set for all blocks that are introduced when critical edges are split
1697     linear_scan_loop_header_flag  = 1 << 9, // set during loop-detection for LinearScan
1698     linear_scan_loop_end_flag     = 1 << 10  // set during loop-detection for LinearScan

1699   };
1700 
1701   void set(Flag f)                               { _flags |= f; }
1702   void clear(Flag f)                             { _flags &= ~f; }
1703   bool is_set(Flag f) const                      { return (_flags & f) != 0; }
1704   bool is_entry_block() const {
1705     const int entry_mask = std_entry_flag | osr_entry_flag | exception_entry_flag;
1706     return (_flags & entry_mask) != 0;
1707   }
1708 
1709   // iteration
1710   void iterate_preorder   (BlockClosure* closure);
1711   void iterate_postorder  (BlockClosure* closure);
1712 
1713   void block_values_do(ValueVisitor* f);
1714 
1715   // loops
1716   void set_loop_index(int ix)                    { _loop_index = ix;        }
1717   int  loop_index() const                        { return _loop_index;      }
1718 
1719   // merging
1720   bool try_merge(ValueStack* state);             // try to merge states at block begin
1721   void merge(ValueStack* state)                  { bool b = try_merge(state); assert(b, "merge failed"); }
1722 
1723   // debugging
1724   void print_block()                             PRODUCT_RETURN;
1725   void print_block(InstructionPrinter& ip, bool live_only = false) PRODUCT_RETURN;
1726 };
1727 
1728 
1729 BASE(BlockEnd, StateSplit)
1730  private:
1731   BlockBegin* _begin;
1732   BlockList*  _sux;
1733 
1734  protected:
1735   BlockList* sux() const                         { return _sux; }
1736 
1737   void set_sux(BlockList* sux) {
1738 #ifdef ASSERT
1739     assert(sux != NULL, "sux must exist");
1740     for (int i = sux->length() - 1; i >= 0; i--) assert(sux->at(i) != NULL, "sux must exist");
1741 #endif
1742     _sux = sux;
1743   }
1744 
1745  public:
1746   // creation
1747   BlockEnd(ValueType* type, ValueStack* state_before, bool is_safepoint)
1748   : StateSplit(type, state_before)
1749   , _begin(NULL)
1750   , _sux(NULL)
1751   {
1752     set_flag(IsSafepointFlag, is_safepoint);
1753   }
1754 
1755   // accessors
1756   bool is_safepoint() const                      { return check_flag(IsSafepointFlag); }
1757   BlockBegin* begin() const                      { return _begin; }

1758 
1759   // manipulation
1760   void set_begin(BlockBegin* begin);
1761 
1762   // successors
1763   int number_of_sux() const                      { return _sux != NULL ? _sux->length() : 0; }
1764   BlockBegin* sux_at(int i) const                { return _sux->at(i); }
1765   BlockBegin* default_sux() const                { return sux_at(number_of_sux() - 1); }
1766   BlockBegin** addr_sux_at(int i) const          { return _sux->adr_at(i); }
1767   int sux_index(BlockBegin* sux) const           { return _sux->find(sux); }
1768   void substitute_sux(BlockBegin* old_sux, BlockBegin* new_sux);
1769 };
1770 
1771 
1772 LEAF(Goto, BlockEnd)
1773  public:
1774   enum Direction {
1775     none,            // Just a regular goto
1776     taken, not_taken // Goto produced from If
1777   };


1794   Goto(BlockBegin* sux, bool is_safepoint) : BlockEnd(illegalType, NULL, is_safepoint)
1795                                            , _direction(none)
1796                                            , _profiled_method(NULL)
1797                                            , _profiled_bci(0) {
1798     BlockList* s = new BlockList(1);
1799     s->append(sux);
1800     set_sux(s);
1801   }
1802 
1803   bool should_profile() const                    { return check_flag(ProfileMDOFlag); }
1804   ciMethod* profiled_method() const              { return _profiled_method; } // set only for profiled branches
1805   int profiled_bci() const                       { return _profiled_bci; }
1806   Direction direction() const                    { return _direction; }
1807 
1808   void set_should_profile(bool value)            { set_flag(ProfileMDOFlag, value); }
1809   void set_profiled_method(ciMethod* method)     { _profiled_method = method; }
1810   void set_profiled_bci(int bci)                 { _profiled_bci = bci; }
1811   void set_direction(Direction d)                { _direction = d; }
1812 };
1813 






































































1814 
1815 LEAF(If, BlockEnd)
1816  private:
1817   Value       _x;
1818   Condition   _cond;
1819   Value       _y;
1820   ciMethod*   _profiled_method;
1821   int         _profiled_bci; // Canonicalizer may alter bci of If node
1822   bool        _swapped;      // Is the order reversed with respect to the original If in the
1823                              // bytecode stream?
1824  public:
1825   // creation
1826   // unordered_is_true is valid for float/double compares only
1827   If(Value x, Condition cond, bool unordered_is_true, Value y, BlockBegin* tsux, BlockBegin* fsux, ValueStack* state_before, bool is_safepoint)
1828     : BlockEnd(illegalType, state_before, is_safepoint)
1829   , _x(x)
1830   , _cond(cond)
1831   , _y(y)
1832   , _profiled_method(NULL)
1833   , _profiled_bci(0)




  93 class         LookupSwitch;
  94 class       Return;
  95 class       Throw;
  96 class       Base;
  97 class   RoundFP;
  98 class   UnsafeOp;
  99 class     UnsafeRawOp;
 100 class       UnsafeGetRaw;
 101 class       UnsafePutRaw;
 102 class     UnsafeObjectOp;
 103 class       UnsafeGetObject;
 104 class       UnsafePutObject;
 105 class         UnsafeGetAndSetObject;
 106 class       UnsafePrefetch;
 107 class         UnsafePrefetchRead;
 108 class         UnsafePrefetchWrite;
 109 class   ProfileCall;
 110 class   ProfileInvoke;
 111 class   RuntimeCall;
 112 class   MemBar;
 113 class   RangeCheckPredicate;
 114 class   Assert;
 115 
 116 // A Value is a reference to the instruction creating the value
 117 typedef Instruction* Value;
 118 define_array(ValueArray, Value)
 119 define_stack(Values, ValueArray)
 120 
 121 define_array(ValueStackArray, ValueStack*)
 122 define_stack(ValueStackStack, ValueStackArray)
 123 
 124 // BlockClosure is the base class for block traversal/iteration.
 125 
 126 class BlockClosure: public CompilationResourceObj {
 127  public:
 128   virtual void block_do(BlockBegin* block)       = 0;
 129 };
 130 
 131 
 132 // A simple closure class for visiting the values of an Instruction
 133 class ValueVisitor: public StackObj {
 134  public:


 195   virtual void do_IfInstanceOf   (IfInstanceOf*    x) = 0;
 196   virtual void do_TableSwitch    (TableSwitch*     x) = 0;
 197   virtual void do_LookupSwitch   (LookupSwitch*    x) = 0;
 198   virtual void do_Return         (Return*          x) = 0;
 199   virtual void do_Throw          (Throw*           x) = 0;
 200   virtual void do_Base           (Base*            x) = 0;
 201   virtual void do_OsrEntry       (OsrEntry*        x) = 0;
 202   virtual void do_ExceptionObject(ExceptionObject* x) = 0;
 203   virtual void do_RoundFP        (RoundFP*         x) = 0;
 204   virtual void do_UnsafeGetRaw   (UnsafeGetRaw*    x) = 0;
 205   virtual void do_UnsafePutRaw   (UnsafePutRaw*    x) = 0;
 206   virtual void do_UnsafeGetObject(UnsafeGetObject* x) = 0;
 207   virtual void do_UnsafePutObject(UnsafePutObject* x) = 0;
 208   virtual void do_UnsafeGetAndSetObject(UnsafeGetAndSetObject* x) = 0;
 209   virtual void do_UnsafePrefetchRead (UnsafePrefetchRead*  x) = 0;
 210   virtual void do_UnsafePrefetchWrite(UnsafePrefetchWrite* x) = 0;
 211   virtual void do_ProfileCall    (ProfileCall*     x) = 0;
 212   virtual void do_ProfileInvoke  (ProfileInvoke*   x) = 0;
 213   virtual void do_RuntimeCall    (RuntimeCall*     x) = 0;
 214   virtual void do_MemBar         (MemBar*          x) = 0;
 215   virtual void do_RangeCheckPredicate(RangeCheckPredicate* x) = 0;
 216 #ifdef ASSERT
 217   virtual void do_Assert         (Assert*          x) = 0;
 218 #endif
 219 };
 220 
 221 
 222 // Hashing support
 223 //
 224 // Note: This hash functions affect the performance
 225 //       of ValueMap - make changes carefully!
 226 
 227 #define HASH1(x1            )                    ((intx)(x1))
 228 #define HASH2(x1, x2        )                    ((HASH1(x1        ) << 7) ^ HASH1(x2))
 229 #define HASH3(x1, x2, x3    )                    ((HASH2(x1, x2    ) << 7) ^ HASH1(x3))
 230 #define HASH4(x1, x2, x3, x4)                    ((HASH3(x1, x2, x3) << 7) ^ HASH1(x4))
 231 
 232 
 233 // The following macros are used to implement instruction-specific hashing.
 234 // By default, each instruction implements hash() and is_equal(Value), used
 235 // for value numbering/common subexpression elimination. The default imple-
 236 // mentation disables value numbering. Each instruction which can be value-
 237 // numbered, should define corresponding hash() and is_equal(Value) functions
 238 // via the macros below. The f arguments specify all the values/op codes, etc.


 295 #ifndef PRODUCT
 296   int          _printable_bci;                   // the bci of the instruction for printing
 297 #endif
 298   int          _use_count;                       // the number of instructions refering to this value (w/o prev/next); only roots can have use count = 0 or > 1
 299   int          _pin_state;                       // set of PinReason describing the reason for pinning
 300   ValueType*   _type;                            // the instruction value type
 301   Instruction* _next;                            // the next instruction if any (NULL for BlockEnd instructions)
 302   Instruction* _subst;                           // the substitution instruction if any
 303   LIR_Opr      _operand;                         // LIR specific information
 304   unsigned int _flags;                           // Flag bits
 305 
 306   ValueStack*  _state_before;                    // Copy of state with input operands still on stack (or NULL)
 307   ValueStack*  _exception_state;                 // Copy of state for exception handling
 308   XHandlers*   _exception_handlers;              // Flat list of exception handlers covering this instruction
 309 
 310   friend class UseCountComputer;
 311   friend class BlockBegin;
 312 
 313   void update_exception_state(ValueStack* state);
 314 
 315  protected:
 316   BlockBegin*  _block;                           // Block that contains this instruction
 317 
 318   void set_type(ValueType* type) {
 319     assert(type != NULL, "type must exist");
 320     _type = type;
 321   }
 322 
 323  public:
 324   void* operator new(size_t size) {
 325     Compilation* c = Compilation::current();
 326     void* res = c->arena()->Amalloc(size);
 327     ((Instruction*)res)->_id = c->get_next_id();
 328     return res;
 329   }
 330 
 331   static const int no_bci = -99;
 332 
 333   enum InstructionFlag {
 334     NeedsNullCheckFlag = 0,
 335     CanTrapFlag,
 336     DirectCompareFlag,
 337     IsEliminatedFlag,
 338     IsSafepointFlag,
 339     IsStaticFlag,
 340     IsStrictfpFlag,
 341     NeedsStoreCheckFlag,
 342     NeedsWriteBarrierFlag,
 343     PreservesStateFlag,
 344     TargetIsFinalFlag,
 345     TargetIsLoadedFlag,
 346     TargetIsStrictfpFlag,
 347     UnorderedIsTrueFlag,
 348     NeedsPatchingFlag,
 349     ThrowIncompatibleClassChangeErrorFlag,
 350     ProfileMDOFlag,
 351     IsLinkedInBlockFlag,
 352     NeedsRangeCheckFlag,
 353     InWorkListFlag,
 354     DeoptimizeOnException,
 355     InstructionLastFlag
 356   };
 357 
 358  public:
 359   bool check_flag(InstructionFlag id) const      { return (_flags & (1 << id)) != 0;    }
 360   void set_flag(InstructionFlag id, bool f)      { _flags = f ? (_flags | (1 << id)) : (_flags & ~(1 << id)); };
 361 
 362   // 'globally' used condition values
 363   enum Condition {
 364     eql, neq, lss, leq, gtr, geq, aeq, beq
 365   };
 366 
 367   // Instructions may be pinned for many reasons and under certain conditions
 368   // with enough knowledge it's possible to safely unpin them.
 369   enum PinReason {
 370       PinUnknown           = 1 << 0
 371     , PinExplicitNullCheck = 1 << 3
 372     , PinStackForStateSplit= 1 << 12
 373     , PinStateSplitConstructor= 1 << 13
 374     , PinGlobalValueNumbering= 1 << 14
 375   };
 376 
 377   static Condition mirror(Condition cond);
 378   static Condition negate(Condition cond);
 379 
 380   // initialization
 381   static int number_of_instructions() {
 382     return Compilation::current()->number_of_instructions();
 383   }
 384 
 385   // creation
 386   Instruction(ValueType* type, ValueStack* state_before = NULL, bool type_is_constant = false)
 387   : _use_count(0)
 388 #ifndef PRODUCT
 389   , _printable_bci(-99)
 390 #endif
 391   , _pin_state(0)
 392   , _type(type)
 393   , _next(NULL)
 394   , _block(NULL)
 395   , _subst(NULL)
 396   , _flags(0)
 397   , _operand(LIR_OprFact::illegalOpr)
 398   , _state_before(state_before)
 399   , _exception_handlers(NULL)
 400   {
 401     check_state(state_before);
 402     assert(type != NULL && (!type->is_constant() || type_is_constant), "type must exist");
 403     update_exception_state(_state_before);
 404   }
 405 
 406   // accessors
 407   int id() const                                 { return _id; }
 408 #ifndef PRODUCT
 409   bool has_printable_bci() const                 { return _printable_bci != -99; }
 410   int printable_bci() const                      { assert(has_printable_bci(), "_printable_bci should have been set"); return _printable_bci; }
 411   void set_printable_bci(int bci)                { _printable_bci = bci; }
 412 #endif
 413   int dominator_depth();
 414   int use_count() const                          { return _use_count; }
 415   int pin_state() const                          { return _pin_state; }
 416   bool is_pinned() const                         { return _pin_state != 0 || PinAllInstructions; }
 417   ValueType* type() const                        { return _type; }
 418   BlockBegin *block() const                      { return _block; }
 419   Instruction* prev();                           // use carefully, expensive operation
 420   Instruction* next() const                      { return _next; }
 421   bool has_subst() const                         { return _subst != NULL; }
 422   Instruction* subst()                           { return _subst == NULL ? this : _subst->subst(); }
 423   LIR_Opr operand() const                        { return _operand; }
 424 
 425   void set_needs_null_check(bool f)              { set_flag(NeedsNullCheckFlag, f); }
 426   bool needs_null_check() const                  { return check_flag(NeedsNullCheckFlag); }
 427   bool is_linked() const                         { return check_flag(IsLinkedInBlockFlag); }
 428   bool can_be_linked()                           { return as_Local() == NULL && as_Phi() == NULL; }
 429 
 430   bool has_uses() const                          { return use_count() > 0; }
 431   ValueStack* state_before() const               { return _state_before; }
 432   ValueStack* exception_state() const            { return _exception_state; }
 433   virtual bool needs_exception_state() const     { return true; }
 434   XHandlers* exception_handlers() const          { return _exception_handlers; }
 435 
 436   // manipulation
 437   void pin(PinReason reason)                     { _pin_state |= reason; }
 438   void pin()                                     { _pin_state |= PinUnknown; }
 439   // DANGEROUS: only used by EliminateStores
 440   void unpin(PinReason reason)                   { assert((reason & PinUnknown) == 0, "can't unpin unknown state"); _pin_state &= ~reason; }
 441 
 442   Instruction* set_next(Instruction* next) {
 443     assert(next->has_printable_bci(), "_printable_bci should have been set");
 444     assert(next != NULL, "must not be NULL");
 445     assert(as_BlockEnd() == NULL, "BlockEnd instructions must have no next");
 446     assert(next->can_be_linked(), "shouldn't link these instructions into list");
 447 
 448     BlockBegin *block = this->block();
 449     next->_block = block;
 450 
 451     next->set_flag(Instruction::IsLinkedInBlockFlag, true);
 452     _next = next;
 453     return next;
 454   }
 455 
 456   Instruction* set_next(Instruction* next, int bci) {
 457 #ifndef PRODUCT
 458     next->set_printable_bci(bci);
 459 #endif
 460     return set_next(next);
 461   }
 462 
 463   // when blocks are merged
 464   void fixup_block_pointers() {
 465     Instruction *cur = next()->next(); // next()'s block is set in set_next
 466     while (cur && cur->_block != block()) {
 467       cur->_block = block();
 468       cur = cur->next();
 469     }
 470   }
 471   
 472   Instruction *insert_after(Instruction *i) {
 473     Instruction* n = _next;
 474     set_next(i);
 475     i->set_next(n);
 476     return _next;
 477   }
 478 
 479   Instruction *insert_after_same_bci(Instruction *i) {
 480 #ifndef PRODUCT
 481     i->set_printable_bci(printable_bci());
 482 #endif
 483     return insert_after(i);
 484   }
 485 
 486   void set_subst(Instruction* subst)             {
 487     assert(subst == NULL ||
 488            type()->base() == subst->type()->base() ||
 489            subst->type()->base() == illegalType, "type can't change");
 490     _subst = subst;
 491   }
 492   void set_exception_handlers(XHandlers *xhandlers) { _exception_handlers = xhandlers; }
 493   void set_exception_state(ValueStack* s)        { check_state(s); _exception_state = s; }
 494   void set_state_before(ValueStack* s)           { check_state(s); _state_before = s; }
 495 
 496   // machine-specifics
 497   void set_operand(LIR_Opr operand)              { assert(operand != LIR_OprFact::illegalOpr, "operand must exist"); _operand = operand; }
 498   void clear_operand()                           { _operand = LIR_OprFact::illegalOpr; }
 499 
 500   // generic
 501   virtual Instruction*      as_Instruction()     { return this; } // to satisfy HASHING1 macro
 502   virtual Phi*              as_Phi()             { return NULL; }
 503   virtual Local*            as_Local()           { return NULL; }
 504   virtual Constant*         as_Constant()        { return NULL; }
 505   virtual AccessField*      as_AccessField()     { return NULL; }
 506   virtual LoadField*        as_LoadField()       { return NULL; }
 507   virtual StoreField*       as_StoreField()      { return NULL; }
 508   virtual AccessArray*      as_AccessArray()     { return NULL; }
 509   virtual ArrayLength*      as_ArrayLength()     { return NULL; }
 510   virtual AccessIndexed*    as_AccessIndexed()   { return NULL; }
 511   virtual LoadIndexed*      as_LoadIndexed()     { return NULL; }
 512   virtual StoreIndexed*     as_StoreIndexed()    { return NULL; }
 513   virtual NegateOp*         as_NegateOp()        { return NULL; }
 514   virtual Op2*              as_Op2()             { return NULL; }


 532   virtual InstanceOf*       as_InstanceOf()      { return NULL; }
 533   virtual TypeCast*         as_TypeCast()        { return NULL; }
 534   virtual AccessMonitor*    as_AccessMonitor()   { return NULL; }
 535   virtual MonitorEnter*     as_MonitorEnter()    { return NULL; }
 536   virtual MonitorExit*      as_MonitorExit()     { return NULL; }
 537   virtual Intrinsic*        as_Intrinsic()       { return NULL; }
 538   virtual BlockBegin*       as_BlockBegin()      { return NULL; }
 539   virtual BlockEnd*         as_BlockEnd()        { return NULL; }
 540   virtual Goto*             as_Goto()            { return NULL; }
 541   virtual If*               as_If()              { return NULL; }
 542   virtual IfInstanceOf*     as_IfInstanceOf()    { return NULL; }
 543   virtual TableSwitch*      as_TableSwitch()     { return NULL; }
 544   virtual LookupSwitch*     as_LookupSwitch()    { return NULL; }
 545   virtual Return*           as_Return()          { return NULL; }
 546   virtual Throw*            as_Throw()           { return NULL; }
 547   virtual Base*             as_Base()            { return NULL; }
 548   virtual RoundFP*          as_RoundFP()         { return NULL; }
 549   virtual ExceptionObject*  as_ExceptionObject() { return NULL; }
 550   virtual UnsafeOp*         as_UnsafeOp()        { return NULL; }
 551   virtual ProfileInvoke*    as_ProfileInvoke()   { return NULL; }
 552   virtual RangeCheckPredicate* as_RangeCheckPredicate() { return NULL; }
 553 
 554 #ifndef PRODUCT
 555   virtual Assert*           as_Assert()          { return NULL; }
 556 #endif
 557 
 558   virtual void visit(InstructionVisitor* v)      = 0;
 559 
 560   virtual bool can_trap() const                  { return false; }
 561 
 562   virtual void input_values_do(ValueVisitor* f)   = 0;
 563   virtual void state_values_do(ValueVisitor* f);
 564   virtual void other_values_do(ValueVisitor* f)   { /* usually no other - override on demand */ }
 565           void       values_do(ValueVisitor* f)   { input_values_do(f); state_values_do(f); other_values_do(f); }
 566 
 567   virtual ciType* exact_type() const             { return NULL; }
 568   virtual ciType* declared_type() const          { return NULL; }
 569 
 570   // hashing
 571   virtual const char* name() const               = 0;
 572   HASHING1(Instruction, false, id())             // hashing disabled by default
 573 
 574   // debugging
 575   static void check_state(ValueStack* state)     PRODUCT_RETURN;
 576   void print()                                   PRODUCT_RETURN;


 598 
 599 // Debugging support
 600 
 601 
 602 #ifdef ASSERT
 603 class AssertValues: public ValueVisitor {
 604   void visit(Value* x)             { assert((*x) != NULL, "value must exist"); }
 605 };
 606   #define ASSERT_VALUES                          { AssertValues assert_value; values_do(&assert_value); }
 607 #else
 608   #define ASSERT_VALUES
 609 #endif // ASSERT
 610 
 611 
 612 // A Phi is a phi function in the sense of SSA form. It stands for
 613 // the value of a local variable at the beginning of a join block.
 614 // A Phi consists of n operands, one for every incoming branch.
 615 
 616 LEAF(Phi, Instruction)
 617  private:

 618   int         _pf_flags; // the flags of the phi function
 619   int         _index;    // to value on operand stack (index < 0) or to local
 620  public:
 621   // creation
 622   Phi(ValueType* type, BlockBegin* b, int index)
 623   : Instruction(type->base())
 624   , _pf_flags(0)

 625   , _index(index)
 626   {
 627     _block = b;
 628     NOT_PRODUCT(set_printable_bci(Value(b)->printable_bci()));
 629     if (type->is_illegal()) {
 630       make_illegal();
 631     }
 632   }
 633 
 634   // flags
 635   enum Flag {
 636     no_flag         = 0,
 637     visited         = 1 << 0,
 638     cannot_simplify = 1 << 1
 639   };
 640 
 641   // accessors
 642   bool  is_local() const          { return _index >= 0; }
 643   bool  is_on_stack() const       { return !is_local(); }
 644   int   local_index() const       { assert(is_local(), ""); return _index; }
 645   int   stack_index() const       { assert(is_on_stack(), ""); return -(_index+1); }
 646 
 647   Value operand_at(int i) const;
 648   int   operand_count() const;
 649 


 650   void   set(Flag f)              { _pf_flags |=  f; }
 651   void   clear(Flag f)            { _pf_flags &= ~f; }
 652   bool   is_set(Flag f) const     { return (_pf_flags & f) != 0; }
 653 
 654   // Invalidates phis corresponding to merges of locals of two different types
 655   // (these should never be referenced, otherwise the bytecodes are illegal)
 656   void   make_illegal() {
 657     set(cannot_simplify);
 658     set_type(illegalType);
 659   }
 660 
 661   bool is_illegal() const {
 662     return type()->is_illegal();
 663   }
 664 
 665   // generic
 666   virtual void input_values_do(ValueVisitor* f) {
 667   }
 668 };
 669 


 695 
 696 
 697 LEAF(Constant, Instruction)
 698  public:
 699   // creation
 700   Constant(ValueType* type):
 701       Instruction(type, NULL, /*type_is_constant*/ true)
 702   {
 703     assert(type->is_constant(), "must be a constant");
 704   }
 705 
 706   Constant(ValueType* type, ValueStack* state_before):
 707     Instruction(type, state_before, /*type_is_constant*/ true)
 708   {
 709     assert(state_before != NULL, "only used for constants which need patching");
 710     assert(type->is_constant(), "must be a constant");
 711     // since it's patching it needs to be pinned
 712     pin();
 713   }
 714 
 715   // generic
 716   virtual bool can_trap() const                  { return state_before() != NULL; }
 717   virtual void input_values_do(ValueVisitor* f)   { /* no values */ }
 718 
 719   virtual intx hash() const;
 720   virtual bool is_equal(Value v) const;
 721 
 722   virtual ciType* exact_type() const;
 723 
 724   enum CompareResult { not_comparable = -1, cond_false, cond_true };
 725 
 726   virtual CompareResult compare(Instruction::Condition condition, Value right) const;
 727   BlockBegin* compare(Instruction::Condition cond, Value right,
 728                       BlockBegin* true_sux, BlockBegin* false_sux) const {
 729     switch (compare(cond, right)) {
 730     case not_comparable:
 731       return NULL;
 732     case cond_false:
 733       return false_sux;
 734     case cond_true:
 735       return true_sux;


 878 
 879   // generic
 880   HASHING1(ArrayLength, true, array()->subst())
 881 };
 882 
 883 
 884 BASE(AccessIndexed, AccessArray)
 885  private:
 886   Value     _index;
 887   Value     _length;
 888   BasicType _elt_type;
 889 
 890  public:
 891   // creation
 892   AccessIndexed(Value array, Value index, Value length, BasicType elt_type, ValueStack* state_before)
 893   : AccessArray(as_ValueType(elt_type), array, state_before)
 894   , _index(index)
 895   , _length(length)
 896   , _elt_type(elt_type)
 897   {
 898     set_flag(Instruction::NeedsRangeCheckFlag, true);
 899     ASSERT_VALUES
 900   }
 901 
 902   // accessors
 903   Value index() const                            { return _index; }
 904   Value length() const                           { return _length; }
 905   BasicType elt_type() const                     { return _elt_type; }
 906 
 907   void clear_length()                            { _length = NULL; }
 908   // perform elimination of range checks involving constants
 909   bool compute_needs_range_check();
 910 
 911   // generic
 912   virtual void input_values_do(ValueVisitor* f)   { AccessArray::input_values_do(f); f->visit(&_index); if (_length != NULL) f->visit(&_length); }
 913 };
 914 
 915 
 916 LEAF(LoadIndexed, AccessIndexed)
 917  private:
 918   NullCheck*  _explicit_null_check;              // For explicit null check elimination
 919 
 920  public:
 921   // creation
 922   LoadIndexed(Value array, Value index, Value length, BasicType elt_type, ValueStack* state_before)
 923   : AccessIndexed(array, index, length, elt_type, state_before)
 924   , _explicit_null_check(NULL) {}
 925 
 926   // accessors
 927   NullCheck* explicit_null_check() const         { return _explicit_null_check; }


1552     }
1553   }
1554 
1555   // generic
1556   virtual bool can_trap() const                  { return check_flag(CanTrapFlag); }
1557   virtual void input_values_do(ValueVisitor* f) {
1558     StateSplit::input_values_do(f);
1559     for (int i = 0; i < _args->length(); i++) f->visit(_args->adr_at(i));
1560   }
1561 };
1562 
1563 
1564 class LIR_List;
1565 
1566 LEAF(BlockBegin, StateSplit)
1567  private:
1568   int        _block_id;                          // the unique block id
1569   int        _bci;                               // start-bci of block
1570   int        _depth_first_number;                // number of this block in a depth-first ordering
1571   int        _linear_scan_number;                // number of this block in linear-scan ordering
1572   int        _dominator_depth;
1573   int        _loop_depth;                        // the loop nesting level of this block
1574   int        _loop_index;                        // number of the innermost loop of this block
1575   int        _flags;                             // the flags associated with this block
1576 
1577   // fields used by BlockListBuilder
1578   int        _total_preds;                       // number of predecessors found by BlockListBuilder
1579   BitMap     _stores_to_locals;                  // bit is set when a local variable is stored in the block
1580 
1581   // SSA specific fields: (factor out later)
1582   BlockList   _successors;                       // the successors of this block
1583   BlockList   _predecessors;                     // the predecessors of this block
1584   BlockList   _dominates;                        // list of blocks that are dominated by this block
1585   BlockBegin* _dominator;                        // the dominator of this block
1586   // SSA specific ends
1587   BlockEnd*  _end;                               // the last instruction of this block
1588   BlockList  _exception_handlers;                // the exception handlers potentially invoked by this block
1589   ValueStackStack* _exception_states;            // only for xhandler entries: states of all instructions that have an edge to this xhandler
1590   int        _exception_handler_pco;             // if this block is the start of an exception handler,
1591                                                  // this records the PC offset in the assembly code of the
1592                                                  // first instruction in this block
1593   Label      _label;                             // the label associated with this block
1594   LIR_List*  _lir;                               // the low level intermediate representation for this block
1595 
1596   BitMap      _live_in;                          // set of live LIR_Opr registers at entry to this block
1597   BitMap      _live_out;                         // set of live LIR_Opr registers at exit from this block
1598   BitMap      _live_gen;                         // set of registers used before any redefinition in this block
1599   BitMap      _live_kill;                        // set of registers defined in this block
1600 
1601   BitMap      _fpu_register_usage;
1602   intArray*   _fpu_stack_state;                  // For x86 FPU code generation with UseLinearScan
1603   int         _first_lir_instruction_id;         // ID of first LIR instruction in this block
1604   int         _last_lir_instruction_id;          // ID of last LIR instruction in this block


1613     Compilation* c = Compilation::current();
1614     void* res = c->arena()->Amalloc(size);
1615     ((BlockBegin*)res)->_id = c->get_next_id();
1616     ((BlockBegin*)res)->_block_id = c->get_next_block_id();
1617     return res;
1618   }
1619 
1620   // initialization/counting
1621   static int  number_of_blocks() {
1622     return Compilation::current()->number_of_blocks();
1623   }
1624 
1625   // creation
1626   BlockBegin(int bci)
1627   : StateSplit(illegalType)
1628   , _bci(bci)
1629   , _depth_first_number(-1)
1630   , _linear_scan_number(-1)
1631   , _loop_depth(0)
1632   , _flags(0)
1633   , _dominator_depth(-1)
1634   , _dominator(NULL)
1635   , _end(NULL)
1636   , _predecessors(2)
1637   , _successors(2)
1638   , _dominates(2)
1639   , _exception_handlers(1)
1640   , _exception_states(NULL)
1641   , _exception_handler_pco(-1)
1642   , _lir(NULL)
1643   , _loop_index(-1)
1644   , _live_in()
1645   , _live_out()
1646   , _live_gen()
1647   , _live_kill()
1648   , _fpu_register_usage()
1649   , _fpu_stack_state(NULL)
1650   , _first_lir_instruction_id(-1)
1651   , _last_lir_instruction_id(-1)
1652   , _total_preds(0)
1653   , _stores_to_locals()
1654   {
1655     _block = this;
1656 #ifndef PRODUCT
1657     set_printable_bci(bci);
1658 #endif
1659   }
1660 
1661   // accessors
1662   int block_id() const                           { return _block_id; }
1663   int bci() const                                { return _bci; }
1664   BlockList* successors()                        { return &_successors; }
1665   BlockList* dominates()                         { return &_dominates; }
1666   BlockBegin* dominator() const                  { return _dominator; }
1667   int loop_depth() const                         { return _loop_depth; }
1668   int dominator_depth() const                    { return _dominator_depth; }
1669   int depth_first_number() const                 { return _depth_first_number; }
1670   int linear_scan_number() const                 { return _linear_scan_number; }
1671   BlockEnd* end() const                          { return _end; }
1672   Label* label()                                 { return &_label; }
1673   LIR_List* lir() const                          { return _lir; }
1674   int exception_handler_pco() const              { return _exception_handler_pco; }
1675   BitMap& live_in()                              { return _live_in;        }
1676   BitMap& live_out()                             { return _live_out;       }
1677   BitMap& live_gen()                             { return _live_gen;       }
1678   BitMap& live_kill()                            { return _live_kill;      }
1679   BitMap& fpu_register_usage()                   { return _fpu_register_usage; }
1680   intArray* fpu_stack_state() const              { return _fpu_stack_state;    }
1681   int first_lir_instruction_id() const           { return _first_lir_instruction_id; }
1682   int last_lir_instruction_id() const            { return _last_lir_instruction_id; }
1683   int total_preds() const                        { return _total_preds; }
1684   BitMap& stores_to_locals()                     { return _stores_to_locals; }
1685 
1686   // manipulation
1687   void set_dominator(BlockBegin* dom)            { _dominator = dom; }
1688   void set_loop_depth(int d)                     { _loop_depth = d; }
1689   void set_dominator_depth(int d)                { _dominator_depth = d; }
1690   void set_depth_first_number(int dfn)           { _depth_first_number = dfn; }
1691   void set_linear_scan_number(int lsn)           { _linear_scan_number = lsn; }
1692   void set_end(BlockEnd* end);
1693   void clear_end();
1694   void disconnect_from_graph();
1695   static void disconnect_edge(BlockBegin* from, BlockBegin* to);
1696   BlockBegin* insert_block_between(BlockBegin* sux);
1697   void substitute_sux(BlockBegin* old_sux, BlockBegin* new_sux);
1698   void set_lir(LIR_List* lir)                    { _lir = lir; }
1699   void set_exception_handler_pco(int pco)        { _exception_handler_pco = pco; }
1700   void set_live_in       (BitMap map)            { _live_in = map;        }
1701   void set_live_out      (BitMap map)            { _live_out = map;       }
1702   void set_live_gen      (BitMap map)            { _live_gen = map;       }
1703   void set_live_kill     (BitMap map)            { _live_kill = map;      }
1704   void set_fpu_register_usage(BitMap map)        { _fpu_register_usage = map; }
1705   void set_fpu_stack_state(intArray* state)      { _fpu_stack_state = state;  }
1706   void set_first_lir_instruction_id(int id)      { _first_lir_instruction_id = id;  }
1707   void set_last_lir_instruction_id(int id)       { _last_lir_instruction_id = id;  }
1708   void increment_total_preds(int n = 1)          { _total_preds += n; }
1709   void init_stores_to_locals(int locals_count)   { _stores_to_locals = BitMap(locals_count); _stores_to_locals.clear(); }


1731   BlockBegin* exception_handler_at(int i) const  { return _exception_handlers.at(i); }
1732 
1733   // states of the instructions that have an edge to this exception handler
1734   int number_of_exception_states()               { assert(is_set(exception_entry_flag), "only for xhandlers"); return _exception_states == NULL ? 0 : _exception_states->length(); }
1735   ValueStack* exception_state_at(int idx) const  { assert(is_set(exception_entry_flag), "only for xhandlers"); return _exception_states->at(idx); }
1736   int add_exception_state(ValueStack* state);
1737 
1738   // flags
1739   enum Flag {
1740     no_flag                       = 0,
1741     std_entry_flag                = 1 << 0,
1742     osr_entry_flag                = 1 << 1,
1743     exception_entry_flag          = 1 << 2,
1744     subroutine_entry_flag         = 1 << 3,
1745     backward_branch_target_flag   = 1 << 4,
1746     is_on_work_list_flag          = 1 << 5,
1747     was_visited_flag              = 1 << 6,
1748     parser_loop_header_flag       = 1 << 7,  // set by parser to identify blocks where phi functions can not be created on demand
1749     critical_edge_split_flag      = 1 << 8, // set for all blocks that are introduced when critical edges are split
1750     linear_scan_loop_header_flag  = 1 << 9, // set during loop-detection for LinearScan
1751     linear_scan_loop_end_flag     = 1 << 10, // set during loop-detection for LinearScan
1752     donot_eliminate_range_checks  = 1 << 11  // Should be try to eliminate range checks in this block
1753   };
1754 
1755   void set(Flag f)                               { _flags |= f; }
1756   void clear(Flag f)                             { _flags &= ~f; }
1757   bool is_set(Flag f) const                      { return (_flags & f) != 0; }
1758   bool is_entry_block() const {
1759     const int entry_mask = std_entry_flag | osr_entry_flag | exception_entry_flag;
1760     return (_flags & entry_mask) != 0;
1761   }
1762 
1763   // iteration
1764   void iterate_preorder   (BlockClosure* closure);
1765   void iterate_postorder  (BlockClosure* closure);
1766 
1767   void block_values_do(ValueVisitor* f);
1768 
1769   // loops
1770   void set_loop_index(int ix)                    { _loop_index = ix;        }
1771   int  loop_index() const                        { return _loop_index;      }
1772 
1773   // merging
1774   bool try_merge(ValueStack* state);             // try to merge states at block begin
1775   void merge(ValueStack* state)                  { bool b = try_merge(state); assert(b, "merge failed"); }
1776 
1777   // debugging
1778   void print_block()                             PRODUCT_RETURN;
1779   void print_block(InstructionPrinter& ip, bool live_only = false) PRODUCT_RETURN;
1780 };
1781 
1782 
1783 BASE(BlockEnd, StateSplit)
1784  private:

1785   BlockList*  _sux;
1786 
1787  protected:
1788   BlockList* sux() const                         { return _sux; }
1789 
1790   void set_sux(BlockList* sux) {
1791 #ifdef ASSERT
1792     assert(sux != NULL, "sux must exist");
1793     for (int i = sux->length() - 1; i >= 0; i--) assert(sux->at(i) != NULL, "sux must exist");
1794 #endif
1795     _sux = sux;
1796   }
1797 
1798  public:
1799   // creation
1800   BlockEnd(ValueType* type, ValueStack* state_before, bool is_safepoint)
1801   : StateSplit(type, state_before)

1802   , _sux(NULL)
1803   {
1804     set_flag(IsSafepointFlag, is_safepoint);
1805   }
1806 
1807   // accessors
1808   bool is_safepoint() const                      { return check_flag(IsSafepointFlag); }
1809   // For compatibility with old code, for new code use block()
1810   BlockBegin* begin() const                      { return _block; }
1811 
1812   // manipulation
1813   void set_begin(BlockBegin* begin);
1814 
1815   // successors
1816   int number_of_sux() const                      { return _sux != NULL ? _sux->length() : 0; }
1817   BlockBegin* sux_at(int i) const                { return _sux->at(i); }
1818   BlockBegin* default_sux() const                { return sux_at(number_of_sux() - 1); }
1819   BlockBegin** addr_sux_at(int i) const          { return _sux->adr_at(i); }
1820   int sux_index(BlockBegin* sux) const           { return _sux->find(sux); }
1821   void substitute_sux(BlockBegin* old_sux, BlockBegin* new_sux);
1822 };
1823 
1824 
1825 LEAF(Goto, BlockEnd)
1826  public:
1827   enum Direction {
1828     none,            // Just a regular goto
1829     taken, not_taken // Goto produced from If
1830   };


1847   Goto(BlockBegin* sux, bool is_safepoint) : BlockEnd(illegalType, NULL, is_safepoint)
1848                                            , _direction(none)
1849                                            , _profiled_method(NULL)
1850                                            , _profiled_bci(0) {
1851     BlockList* s = new BlockList(1);
1852     s->append(sux);
1853     set_sux(s);
1854   }
1855 
1856   bool should_profile() const                    { return check_flag(ProfileMDOFlag); }
1857   ciMethod* profiled_method() const              { return _profiled_method; } // set only for profiled branches
1858   int profiled_bci() const                       { return _profiled_bci; }
1859   Direction direction() const                    { return _direction; }
1860 
1861   void set_should_profile(bool value)            { set_flag(ProfileMDOFlag, value); }
1862   void set_profiled_method(ciMethod* method)     { _profiled_method = method; }
1863   void set_profiled_bci(int bci)                 { _profiled_bci = bci; }
1864   void set_direction(Direction d)                { _direction = d; }
1865 };
1866 
1867 #ifndef PRODUCT
1868 
1869 LEAF(Assert, Instruction)
1870   private:
1871   Value       _x;
1872   Condition   _cond;
1873   Value       _y;
1874   char        *_message;
1875 
1876  public:
1877   // creation
1878   // unordered_is_true is valid for float/double compares only
1879    Assert(Value x, Condition cond, bool unordered_is_true, Value y);
1880 
1881   // accessors
1882   Value x() const                                { return _x; }
1883   Condition cond() const                         { return _cond; }
1884   bool unordered_is_true() const                 { return check_flag(UnorderedIsTrueFlag); }
1885   Value y() const                                { return _y; }
1886   const char *message() const                    { return _message; }
1887 
1888   // generic
1889   virtual void input_values_do(ValueVisitor* f)  { f->visit(&_x); f->visit(&_y); }
1890 };
1891 
1892 #endif
1893 
1894 LEAF(RangeCheckPredicate, StateSplit)
1895  private:
1896   Value       _x;
1897   Condition   _cond;
1898   Value       _y;
1899 
1900   void check_state();
1901 
1902  public:
1903   // creation
1904   // unordered_is_true is valid for float/double compares only
1905    RangeCheckPredicate(Value x, Condition cond, bool unordered_is_true, Value y, ValueStack* state) : StateSplit(illegalType)
1906   , _x(x)
1907   , _cond(cond)
1908   , _y(y)
1909   {
1910     ASSERT_VALUES
1911     set_flag(UnorderedIsTrueFlag, unordered_is_true);
1912     assert(x->type()->tag() == y->type()->tag(), "types must match");
1913     this->set_state(state);
1914     check_state();
1915   }
1916 
1917   // Always deoptimize
1918   RangeCheckPredicate(ValueStack* state) : StateSplit(illegalType)
1919   {
1920     this->set_state(state);
1921     _x = _y = NULL;
1922     check_state();
1923   }
1924 
1925   // accessors
1926   Value x() const                                { return _x; }
1927   Condition cond() const                         { return _cond; }
1928   bool unordered_is_true() const                 { return check_flag(UnorderedIsTrueFlag); }
1929   Value y() const                                { return _y; }
1930 
1931   void always_fail()                             { _x = _y = NULL; }
1932 
1933   // generic
1934   virtual void input_values_do(ValueVisitor* f)  { StateSplit::input_values_do(f); f->visit(&_x); f->visit(&_y); }
1935   HASHING3(RangeCheckPredicate, true, x()->subst(), y()->subst(), cond())
1936 };
1937 
1938 LEAF(If, BlockEnd)
1939  private:
1940   Value       _x;
1941   Condition   _cond;
1942   Value       _y;
1943   ciMethod*   _profiled_method;
1944   int         _profiled_bci; // Canonicalizer may alter bci of If node
1945   bool        _swapped;      // Is the order reversed with respect to the original If in the
1946                              // bytecode stream?
1947  public:
1948   // creation
1949   // unordered_is_true is valid for float/double compares only
1950   If(Value x, Condition cond, bool unordered_is_true, Value y, BlockBegin* tsux, BlockBegin* fsux, ValueStack* state_before, bool is_safepoint)
1951     : BlockEnd(illegalType, state_before, is_safepoint)
1952   , _x(x)
1953   , _cond(cond)
1954   , _y(y)
1955   , _profiled_method(NULL)
1956   , _profiled_bci(0)