1 /*
   2  * Copyright (c) 1999, 2021, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #ifndef SHARE_C1_C1_INSTRUCTION_HPP
  26 #define SHARE_C1_C1_INSTRUCTION_HPP
  27 
  28 #include "c1/c1_Compilation.hpp"
  29 #include "c1/c1_LIR.hpp"
  30 #include "c1/c1_ValueType.hpp"
  31 #include "ci/ciField.hpp"
  32 
  33 // Predefined classes
  34 class ciField;
  35 class ValueStack;
  36 class InstructionPrinter;
  37 class IRScope;
  38 class LIR_OprDesc;
  39 typedef LIR_OprDesc* LIR_Opr;
  40 
  41 
  42 // Instruction class hierarchy
  43 //
  44 // All leaf classes in the class hierarchy are concrete classes
  45 // (i.e., are instantiated). All other classes are abstract and
  46 // serve factoring.
  47 
  48 class Instruction;
  49 class   Phi;
  50 class   Local;
  51 class   Constant;
  52 class   AccessField;
  53 class     LoadField;
  54 class     StoreField;
  55 class   AccessArray;
  56 class     ArrayLength;
  57 class     AccessIndexed;
  58 class       LoadIndexed;
  59 class       StoreIndexed;
  60 class   NegateOp;
  61 class   Op2;
  62 class     ArithmeticOp;
  63 class     ShiftOp;
  64 class     LogicOp;
  65 class     CompareOp;
  66 class     IfOp;
  67 class   Convert;
  68 class   NullCheck;
  69 class   TypeCast;
  70 class   OsrEntry;
  71 class   ExceptionObject;
  72 class   StateSplit;
  73 class     Invoke;
  74 class     NewInstance;
  75 class     NewArray;
  76 class       NewTypeArray;
  77 class       NewObjectArray;
  78 class       NewMultiArray;
  79 class     TypeCheck;
  80 class       CheckCast;
  81 class       InstanceOf;
  82 class     AccessMonitor;
  83 class       MonitorEnter;
  84 class       MonitorExit;
  85 class     Intrinsic;
  86 class     BlockBegin;
  87 class     BlockEnd;
  88 class       Goto;
  89 class       If;
  90 class       Switch;
  91 class         TableSwitch;
  92 class         LookupSwitch;
  93 class       Return;
  94 class       Throw;
  95 class       Base;
  96 class   RoundFP;
  97 class   UnsafeOp;
  98 class     UnsafeGet;
  99 class     UnsafePut;
 100 class     UnsafeGetAndSet;
 101 class   ProfileCall;
 102 class   ProfileReturnType;
 103 class   ProfileInvoke;
 104 class   RuntimeCall;
 105 class   MemBar;
 106 class   RangeCheckPredicate;
 107 #ifdef ASSERT
 108 class   Assert;
 109 #endif
 110 
 111 // A Value is a reference to the instruction creating the value
 112 typedef Instruction* Value;
 113 typedef GrowableArray<Value> Values;
 114 typedef GrowableArray<ValueStack*> ValueStackStack;
 115 
 116 // BlockClosure is the base class for block traversal/iteration.
 117 
 118 class BlockClosure: public CompilationResourceObj {
 119  public:
 120   virtual void block_do(BlockBegin* block)       = 0;
 121 };
 122 
 123 
 124 // A simple closure class for visiting the values of an Instruction
 125 class ValueVisitor: public StackObj {
 126  public:
 127   virtual void visit(Value* v) = 0;
 128 };
 129 
 130 
 131 // Some array and list classes
 132 typedef GrowableArray<BlockBegin*> BlockBeginArray;
 133 
 134 class BlockList: public GrowableArray<BlockBegin*> {
 135  public:
 136   BlockList(): GrowableArray<BlockBegin*>() {}
 137   BlockList(const int size): GrowableArray<BlockBegin*>(size) {}
 138   BlockList(const int size, BlockBegin* init): GrowableArray<BlockBegin*>(size, size, init) {}
 139 
 140   void iterate_forward(BlockClosure* closure);
 141   void iterate_backward(BlockClosure* closure);
 142   void blocks_do(void f(BlockBegin*));
 143   void values_do(ValueVisitor* f);
 144   void print(bool cfg_only = false, bool live_only = false) PRODUCT_RETURN;
 145 };
 146 
 147 
 148 // InstructionVisitors provide type-based dispatch for instructions.
 149 // For each concrete Instruction class X, a virtual function do_X is
 150 // provided. Functionality that needs to be implemented for all classes
 151 // (e.g., printing, code generation) is factored out into a specialised
 152 // visitor instead of added to the Instruction classes itself.
 153 
 154 class InstructionVisitor: public StackObj {
 155  public:
 156   virtual void do_Phi            (Phi*             x) = 0;
 157   virtual void do_Local          (Local*           x) = 0;
 158   virtual void do_Constant       (Constant*        x) = 0;
 159   virtual void do_LoadField      (LoadField*       x) = 0;
 160   virtual void do_StoreField     (StoreField*      x) = 0;
 161   virtual void do_ArrayLength    (ArrayLength*     x) = 0;
 162   virtual void do_LoadIndexed    (LoadIndexed*     x) = 0;
 163   virtual void do_StoreIndexed   (StoreIndexed*    x) = 0;
 164   virtual void do_NegateOp       (NegateOp*        x) = 0;
 165   virtual void do_ArithmeticOp   (ArithmeticOp*    x) = 0;
 166   virtual void do_ShiftOp        (ShiftOp*         x) = 0;
 167   virtual void do_LogicOp        (LogicOp*         x) = 0;
 168   virtual void do_CompareOp      (CompareOp*       x) = 0;
 169   virtual void do_IfOp           (IfOp*            x) = 0;
 170   virtual void do_Convert        (Convert*         x) = 0;
 171   virtual void do_NullCheck      (NullCheck*       x) = 0;
 172   virtual void do_TypeCast       (TypeCast*        x) = 0;
 173   virtual void do_Invoke         (Invoke*          x) = 0;
 174   virtual void do_NewInstance    (NewInstance*     x) = 0;
 175   virtual void do_NewTypeArray   (NewTypeArray*    x) = 0;
 176   virtual void do_NewObjectArray (NewObjectArray*  x) = 0;
 177   virtual void do_NewMultiArray  (NewMultiArray*   x) = 0;
 178   virtual void do_CheckCast      (CheckCast*       x) = 0;
 179   virtual void do_InstanceOf     (InstanceOf*      x) = 0;
 180   virtual void do_MonitorEnter   (MonitorEnter*    x) = 0;
 181   virtual void do_MonitorExit    (MonitorExit*     x) = 0;
 182   virtual void do_Intrinsic      (Intrinsic*       x) = 0;
 183   virtual void do_BlockBegin     (BlockBegin*      x) = 0;
 184   virtual void do_Goto           (Goto*            x) = 0;
 185   virtual void do_If             (If*              x) = 0;
 186   virtual void do_TableSwitch    (TableSwitch*     x) = 0;
 187   virtual void do_LookupSwitch   (LookupSwitch*    x) = 0;
 188   virtual void do_Return         (Return*          x) = 0;
 189   virtual void do_Throw          (Throw*           x) = 0;
 190   virtual void do_Base           (Base*            x) = 0;
 191   virtual void do_OsrEntry       (OsrEntry*        x) = 0;
 192   virtual void do_ExceptionObject(ExceptionObject* x) = 0;
 193   virtual void do_RoundFP        (RoundFP*         x) = 0;
 194   virtual void do_UnsafeGet      (UnsafeGet*       x) = 0;
 195   virtual void do_UnsafePut      (UnsafePut*       x) = 0;
 196   virtual void do_UnsafeGetAndSet(UnsafeGetAndSet* x) = 0;
 197   virtual void do_ProfileCall    (ProfileCall*     x) = 0;
 198   virtual void do_ProfileReturnType (ProfileReturnType*  x) = 0;
 199   virtual void do_ProfileInvoke  (ProfileInvoke*   x) = 0;
 200   virtual void do_RuntimeCall    (RuntimeCall*     x) = 0;
 201   virtual void do_MemBar         (MemBar*          x) = 0;
 202   virtual void do_RangeCheckPredicate(RangeCheckPredicate* x) = 0;
 203 #ifdef ASSERT
 204   virtual void do_Assert         (Assert*          x) = 0;
 205 #endif
 206 };
 207 
 208 
 209 // Hashing support
 210 //
 211 // Note: This hash functions affect the performance
 212 //       of ValueMap - make changes carefully!
 213 
 214 #define HASH1(x1            )                    ((intx)(x1))
 215 #define HASH2(x1, x2        )                    ((HASH1(x1        ) << 7) ^ HASH1(x2))
 216 #define HASH3(x1, x2, x3    )                    ((HASH2(x1, x2    ) << 7) ^ HASH1(x3))
 217 #define HASH4(x1, x2, x3, x4)                    ((HASH3(x1, x2, x3) << 7) ^ HASH1(x4))
 218 
 219 
 220 // The following macros are used to implement instruction-specific hashing.
 221 // By default, each instruction implements hash() and is_equal(Value), used
 222 // for value numbering/common subexpression elimination. The default imple-
 223 // mentation disables value numbering. Each instruction which can be value-
 224 // numbered, should define corresponding hash() and is_equal(Value) functions
 225 // via the macros below. The f arguments specify all the values/op codes, etc.
 226 // that need to be identical for two instructions to be identical.
 227 //
 228 // Note: The default implementation of hash() returns 0 in order to indicate
 229 //       that the instruction should not be considered for value numbering.
 230 //       The currently used hash functions do not guarantee that never a 0
 231 //       is produced. While this is still correct, it may be a performance
 232 //       bug (no value numbering for that node). However, this situation is
 233 //       so unlikely, that we are not going to handle it specially.
 234 
 235 #define HASHING1(class_name, enabled, f1)             \
 236   virtual intx hash() const {                         \
 237     return (enabled) ? HASH2(name(), f1) : 0;         \
 238   }                                                   \
 239   virtual bool is_equal(Value v) const {              \
 240     if (!(enabled)  ) return false;                   \
 241     class_name* _v = v->as_##class_name();            \
 242     if (_v == NULL  ) return false;                   \
 243     if (f1 != _v->f1) return false;                   \
 244     return true;                                      \
 245   }                                                   \
 246 
 247 
 248 #define HASHING2(class_name, enabled, f1, f2)         \
 249   virtual intx hash() const {                         \
 250     return (enabled) ? HASH3(name(), f1, f2) : 0;     \
 251   }                                                   \
 252   virtual bool is_equal(Value v) const {              \
 253     if (!(enabled)  ) return false;                   \
 254     class_name* _v = v->as_##class_name();            \
 255     if (_v == NULL  ) return false;                   \
 256     if (f1 != _v->f1) return false;                   \
 257     if (f2 != _v->f2) return false;                   \
 258     return true;                                      \
 259   }                                                   \
 260 
 261 
 262 #define HASHING3(class_name, enabled, f1, f2, f3)     \
 263   virtual intx hash() const {                         \
 264     return (enabled) ? HASH4(name(), f1, f2, f3) : 0; \
 265   }                                                   \
 266   virtual bool is_equal(Value v) const {              \
 267     if (!(enabled)  ) return false;                   \
 268     class_name* _v = v->as_##class_name();            \
 269     if (_v == NULL  ) return false;                   \
 270     if (f1 != _v->f1) return false;                   \
 271     if (f2 != _v->f2) return false;                   \
 272     if (f3 != _v->f3) return false;                   \
 273     return true;                                      \
 274   }                                                   \
 275 
 276 
 277 // The mother of all instructions...
 278 
 279 class Instruction: public CompilationResourceObj {
 280  private:
 281   int          _id;                              // the unique instruction id
 282 #ifndef PRODUCT
 283   int          _printable_bci;                   // the bci of the instruction for printing
 284 #endif
 285   int          _use_count;                       // the number of instructions refering to this value (w/o prev/next); only roots can have use count = 0 or > 1
 286   int          _pin_state;                       // set of PinReason describing the reason for pinning
 287   ValueType*   _type;                            // the instruction value type
 288   Instruction* _next;                            // the next instruction if any (NULL for BlockEnd instructions)
 289   Instruction* _subst;                           // the substitution instruction if any
 290   LIR_Opr      _operand;                         // LIR specific information
 291   unsigned int _flags;                           // Flag bits
 292 
 293   ValueStack*  _state_before;                    // Copy of state with input operands still on stack (or NULL)
 294   ValueStack*  _exception_state;                 // Copy of state for exception handling
 295   XHandlers*   _exception_handlers;              // Flat list of exception handlers covering this instruction
 296 
 297   friend class UseCountComputer;
 298 
 299   void update_exception_state(ValueStack* state);
 300 
 301  protected:
 302   BlockBegin*  _block;                           // Block that contains this instruction
 303 
 304   void set_type(ValueType* type) {
 305     assert(type != NULL, "type must exist");
 306     _type = type;
 307   }
 308 
 309   // Helper class to keep track of which arguments need a null check
 310   class ArgsNonNullState {
 311   private:
 312     int _nonnull_state; // mask identifying which args are nonnull
 313   public:
 314     ArgsNonNullState()
 315       : _nonnull_state(AllBits) {}
 316 
 317     // Does argument number i needs a null check?
 318     bool arg_needs_null_check(int i) const {
 319       // No data is kept for arguments starting at position 33 so
 320       // conservatively assume that they need a null check.
 321       if (i >= 0 && i < (int)sizeof(_nonnull_state) * BitsPerByte) {
 322         return is_set_nth_bit(_nonnull_state, i);
 323       }
 324       return true;
 325     }
 326 
 327     // Set whether argument number i needs a null check or not
 328     void set_arg_needs_null_check(int i, bool check) {
 329       if (i >= 0 && i < (int)sizeof(_nonnull_state) * BitsPerByte) {
 330         if (check) {
 331           _nonnull_state |= nth_bit(i);
 332         } else {
 333           _nonnull_state &= ~(nth_bit(i));
 334         }
 335       }
 336     }
 337   };
 338 
 339  public:
 340   void* operator new(size_t size) throw() {
 341     Compilation* c = Compilation::current();
 342     void* res = c->arena()->Amalloc(size);
 343     return res;
 344   }
 345 
 346   static const int no_bci = -99;
 347 
 348   enum InstructionFlag {
 349     NeedsNullCheckFlag = 0,
 350     CanTrapFlag,
 351     DirectCompareFlag,
 352     IsEliminatedFlag,
 353     IsSafepointFlag,
 354     IsStaticFlag,
 355     NeedsStoreCheckFlag,
 356     NeedsWriteBarrierFlag,
 357     PreservesStateFlag,
 358     TargetIsFinalFlag,
 359     TargetIsLoadedFlag,
 360     UnorderedIsTrueFlag,
 361     NeedsPatchingFlag,
 362     ThrowIncompatibleClassChangeErrorFlag,
 363     InvokeSpecialReceiverCheckFlag,
 364     ProfileMDOFlag,
 365     IsLinkedInBlockFlag,
 366     NeedsRangeCheckFlag,
 367     InWorkListFlag,
 368     DeoptimizeOnException,
 369     InstructionLastFlag
 370   };
 371 
 372  public:
 373   bool check_flag(InstructionFlag id) const      { return (_flags & (1 << id)) != 0;    }
 374   void set_flag(InstructionFlag id, bool f)      { _flags = f ? (_flags | (1 << id)) : (_flags & ~(1 << id)); };
 375 
 376   // 'globally' used condition values
 377   enum Condition {
 378     eql, neq, lss, leq, gtr, geq, aeq, beq
 379   };
 380 
 381   // Instructions may be pinned for many reasons and under certain conditions
 382   // with enough knowledge it's possible to safely unpin them.
 383   enum PinReason {
 384       PinUnknown           = 1 << 0
 385     , PinExplicitNullCheck = 1 << 3
 386     , PinStackForStateSplit= 1 << 12
 387     , PinStateSplitConstructor= 1 << 13
 388     , PinGlobalValueNumbering= 1 << 14
 389   };
 390 
 391   static Condition mirror(Condition cond);
 392   static Condition negate(Condition cond);
 393 
 394   // initialization
 395   static int number_of_instructions() {
 396     return Compilation::current()->number_of_instructions();
 397   }
 398 
 399   // creation
 400   Instruction(ValueType* type, ValueStack* state_before = NULL, bool type_is_constant = false)
 401   : _id(Compilation::current()->get_next_id()),
 402 #ifndef PRODUCT
 403   _printable_bci(-99),
 404 #endif
 405     _use_count(0)
 406   , _pin_state(0)
 407   , _type(type)
 408   , _next(NULL)
 409   , _subst(NULL)
 410   , _operand(LIR_OprFact::illegalOpr)
 411   , _flags(0)
 412   , _state_before(state_before)
 413   , _exception_handlers(NULL)
 414   , _block(NULL)
 415   {
 416     check_state(state_before);
 417     assert(type != NULL && (!type->is_constant() || type_is_constant), "type must exist");
 418     update_exception_state(_state_before);
 419   }
 420 
 421   // accessors
 422   int id() const                                 { return _id; }
 423 #ifndef PRODUCT
 424   bool has_printable_bci() const                 { return _printable_bci != -99; }
 425   int printable_bci() const                      { assert(has_printable_bci(), "_printable_bci should have been set"); return _printable_bci; }
 426   void set_printable_bci(int bci)                { _printable_bci = bci; }
 427 #endif
 428   int dominator_depth();
 429   int use_count() const                          { return _use_count; }
 430   int pin_state() const                          { return _pin_state; }
 431   bool is_pinned() const                         { return _pin_state != 0 || PinAllInstructions; }
 432   ValueType* type() const                        { return _type; }
 433   BlockBegin *block() const                      { return _block; }
 434   Instruction* prev();                           // use carefully, expensive operation
 435   Instruction* next() const                      { return _next; }
 436   bool has_subst() const                         { return _subst != NULL; }
 437   Instruction* subst()                           { return _subst == NULL ? this : _subst->subst(); }
 438   LIR_Opr operand() const                        { return _operand; }
 439 
 440   void set_needs_null_check(bool f)              { set_flag(NeedsNullCheckFlag, f); }
 441   bool needs_null_check() const                  { return check_flag(NeedsNullCheckFlag); }
 442   bool is_linked() const                         { return check_flag(IsLinkedInBlockFlag); }
 443   bool can_be_linked()                           { return as_Local() == NULL && as_Phi() == NULL; }
 444 
 445   bool is_null_obj()                             { return as_Constant() != NULL && type()->as_ObjectType()->constant_value()->is_null_object(); }
 446 
 447   bool has_uses() const                          { return use_count() > 0; }
 448   ValueStack* state_before() const               { return _state_before; }
 449   ValueStack* exception_state() const            { return _exception_state; }
 450   virtual bool needs_exception_state() const     { return true; }
 451   XHandlers* exception_handlers() const          { return _exception_handlers; }
 452 
 453   // manipulation
 454   void pin(PinReason reason)                     { _pin_state |= reason; }
 455   void pin()                                     { _pin_state |= PinUnknown; }
 456   // DANGEROUS: only used by EliminateStores
 457   void unpin(PinReason reason)                   { assert((reason & PinUnknown) == 0, "can't unpin unknown state"); _pin_state &= ~reason; }
 458 
 459   Instruction* set_next(Instruction* next) {
 460     assert(next->has_printable_bci(), "_printable_bci should have been set");
 461     assert(next != NULL, "must not be NULL");
 462     assert(as_BlockEnd() == NULL, "BlockEnd instructions must have no next");
 463     assert(next->can_be_linked(), "shouldn't link these instructions into list");
 464 
 465     BlockBegin *block = this->block();
 466     next->_block = block;
 467 
 468     next->set_flag(Instruction::IsLinkedInBlockFlag, true);
 469     _next = next;
 470     return next;
 471   }
 472 
 473   Instruction* set_next(Instruction* next, int bci) {
 474 #ifndef PRODUCT
 475     next->set_printable_bci(bci);
 476 #endif
 477     return set_next(next);
 478   }
 479 
 480   // when blocks are merged
 481   void fixup_block_pointers() {
 482     Instruction *cur = next()->next(); // next()'s block is set in set_next
 483     while (cur && cur->_block != block()) {
 484       cur->_block = block();
 485       cur = cur->next();
 486     }
 487   }
 488 
 489   Instruction *insert_after(Instruction *i) {
 490     Instruction* n = _next;
 491     set_next(i);
 492     i->set_next(n);
 493     return _next;
 494   }
 495 
 496   Instruction *insert_after_same_bci(Instruction *i) {
 497 #ifndef PRODUCT
 498     i->set_printable_bci(printable_bci());
 499 #endif
 500     return insert_after(i);
 501   }
 502 
 503   void set_subst(Instruction* subst)             {
 504     assert(subst == NULL ||
 505            type()->base() == subst->type()->base() ||
 506            subst->type()->base() == illegalType, "type can't change");
 507     _subst = subst;
 508   }
 509   void set_exception_handlers(XHandlers *xhandlers) { _exception_handlers = xhandlers; }
 510   void set_exception_state(ValueStack* s)        { check_state(s); _exception_state = s; }
 511   void set_state_before(ValueStack* s)           { check_state(s); _state_before = s; }
 512 
 513   // machine-specifics
 514   void set_operand(LIR_Opr operand)              { assert(operand != LIR_OprFact::illegalOpr, "operand must exist"); _operand = operand; }
 515   void clear_operand()                           { _operand = LIR_OprFact::illegalOpr; }
 516 
 517   // generic
 518   virtual Instruction*      as_Instruction()     { return this; } // to satisfy HASHING1 macro
 519   virtual Phi*              as_Phi()             { return NULL; }
 520   virtual Local*            as_Local()           { return NULL; }
 521   virtual Constant*         as_Constant()        { return NULL; }
 522   virtual AccessField*      as_AccessField()     { return NULL; }
 523   virtual LoadField*        as_LoadField()       { return NULL; }
 524   virtual StoreField*       as_StoreField()      { return NULL; }
 525   virtual AccessArray*      as_AccessArray()     { return NULL; }
 526   virtual ArrayLength*      as_ArrayLength()     { return NULL; }
 527   virtual AccessIndexed*    as_AccessIndexed()   { return NULL; }
 528   virtual LoadIndexed*      as_LoadIndexed()     { return NULL; }
 529   virtual StoreIndexed*     as_StoreIndexed()    { return NULL; }
 530   virtual NegateOp*         as_NegateOp()        { return NULL; }
 531   virtual Op2*              as_Op2()             { return NULL; }
 532   virtual ArithmeticOp*     as_ArithmeticOp()    { return NULL; }
 533   virtual ShiftOp*          as_ShiftOp()         { return NULL; }
 534   virtual LogicOp*          as_LogicOp()         { return NULL; }
 535   virtual CompareOp*        as_CompareOp()       { return NULL; }
 536   virtual IfOp*             as_IfOp()            { return NULL; }
 537   virtual Convert*          as_Convert()         { return NULL; }
 538   virtual NullCheck*        as_NullCheck()       { return NULL; }
 539   virtual OsrEntry*         as_OsrEntry()        { return NULL; }
 540   virtual StateSplit*       as_StateSplit()      { return NULL; }
 541   virtual Invoke*           as_Invoke()          { return NULL; }
 542   virtual NewInstance*      as_NewInstance()     { return NULL; }
 543   virtual NewArray*         as_NewArray()        { return NULL; }
 544   virtual NewTypeArray*     as_NewTypeArray()    { return NULL; }
 545   virtual NewObjectArray*   as_NewObjectArray()  { return NULL; }
 546   virtual NewMultiArray*    as_NewMultiArray()   { return NULL; }
 547   virtual TypeCheck*        as_TypeCheck()       { return NULL; }
 548   virtual CheckCast*        as_CheckCast()       { return NULL; }
 549   virtual InstanceOf*       as_InstanceOf()      { return NULL; }
 550   virtual TypeCast*         as_TypeCast()        { return NULL; }
 551   virtual AccessMonitor*    as_AccessMonitor()   { return NULL; }
 552   virtual MonitorEnter*     as_MonitorEnter()    { return NULL; }
 553   virtual MonitorExit*      as_MonitorExit()     { return NULL; }
 554   virtual Intrinsic*        as_Intrinsic()       { return NULL; }
 555   virtual BlockBegin*       as_BlockBegin()      { return NULL; }
 556   virtual BlockEnd*         as_BlockEnd()        { return NULL; }
 557   virtual Goto*             as_Goto()            { return NULL; }
 558   virtual If*               as_If()              { return NULL; }
 559   virtual TableSwitch*      as_TableSwitch()     { return NULL; }
 560   virtual LookupSwitch*     as_LookupSwitch()    { return NULL; }
 561   virtual Return*           as_Return()          { return NULL; }
 562   virtual Throw*            as_Throw()           { return NULL; }
 563   virtual Base*             as_Base()            { return NULL; }
 564   virtual RoundFP*          as_RoundFP()         { return NULL; }
 565   virtual ExceptionObject*  as_ExceptionObject() { return NULL; }
 566   virtual UnsafeOp*         as_UnsafeOp()        { return NULL; }
 567   virtual ProfileInvoke*    as_ProfileInvoke()   { return NULL; }
 568   virtual RangeCheckPredicate* as_RangeCheckPredicate() { return NULL; }
 569 
 570 #ifdef ASSERT
 571   virtual Assert*           as_Assert()          { return NULL; }
 572 #endif
 573 
 574   virtual void visit(InstructionVisitor* v)      = 0;
 575 
 576   virtual bool can_trap() const                  { return false; }
 577 
 578   virtual void input_values_do(ValueVisitor* f)   = 0;
 579   virtual void state_values_do(ValueVisitor* f);
 580   virtual void other_values_do(ValueVisitor* f)   { /* usually no other - override on demand */ }
 581           void       values_do(ValueVisitor* f)   { input_values_do(f); state_values_do(f); other_values_do(f); }
 582 
 583   virtual ciType* exact_type() const;
 584   virtual ciType* declared_type() const          { return NULL; }
 585 
 586   // hashing
 587   virtual const char* name() const               = 0;
 588   HASHING1(Instruction, false, id())             // hashing disabled by default
 589 
 590   // debugging
 591   static void check_state(ValueStack* state)     PRODUCT_RETURN;
 592   void print()                                   PRODUCT_RETURN;
 593   void print_line()                              PRODUCT_RETURN;
 594   void print(InstructionPrinter& ip)             PRODUCT_RETURN;
 595 };
 596 
 597 
 598 // The following macros are used to define base (i.e., non-leaf)
 599 // and leaf instruction classes. They define class-name related
 600 // generic functionality in one place.
 601 
 602 #define BASE(class_name, super_class_name)       \
 603   class class_name: public super_class_name {    \
 604    public:                                       \
 605     virtual class_name* as_##class_name()        { return this; }              \
 606 
 607 
 608 #define LEAF(class_name, super_class_name)       \
 609   BASE(class_name, super_class_name)             \
 610    public:                                       \
 611     virtual const char* name() const             { return #class_name; }       \
 612     virtual void visit(InstructionVisitor* v)    { v->do_##class_name(this); } \
 613 
 614 
 615 // Debugging support
 616 
 617 
 618 #ifdef ASSERT
 619 class AssertValues: public ValueVisitor {
 620   void visit(Value* x)             { assert((*x) != NULL, "value must exist"); }
 621 };
 622   #define ASSERT_VALUES                          { AssertValues assert_value; values_do(&assert_value); }
 623 #else
 624   #define ASSERT_VALUES
 625 #endif // ASSERT
 626 
 627 
 628 // A Phi is a phi function in the sense of SSA form. It stands for
 629 // the value of a local variable at the beginning of a join block.
 630 // A Phi consists of n operands, one for every incoming branch.
 631 
 632 LEAF(Phi, Instruction)
 633  private:
 634   int         _pf_flags; // the flags of the phi function
 635   int         _index;    // to value on operand stack (index < 0) or to local
 636  public:
 637   // creation
 638   Phi(ValueType* type, BlockBegin* b, int index)
 639   : Instruction(type->base())
 640   , _pf_flags(0)
 641   , _index(index)
 642   {
 643     _block = b;
 644     NOT_PRODUCT(set_printable_bci(Value(b)->printable_bci()));
 645     if (type->is_illegal()) {
 646       make_illegal();
 647     }
 648   }
 649 
 650   // flags
 651   enum Flag {
 652     no_flag         = 0,
 653     visited         = 1 << 0,
 654     cannot_simplify = 1 << 1
 655   };
 656 
 657   // accessors
 658   bool  is_local() const          { return _index >= 0; }
 659   bool  is_on_stack() const       { return !is_local(); }
 660   int   local_index() const       { assert(is_local(), ""); return _index; }
 661   int   stack_index() const       { assert(is_on_stack(), ""); return -(_index+1); }
 662 
 663   Value operand_at(int i) const;
 664   int   operand_count() const;
 665 
 666   void   set(Flag f)              { _pf_flags |=  f; }
 667   void   clear(Flag f)            { _pf_flags &= ~f; }
 668   bool   is_set(Flag f) const     { return (_pf_flags & f) != 0; }
 669 
 670   // Invalidates phis corresponding to merges of locals of two different types
 671   // (these should never be referenced, otherwise the bytecodes are illegal)
 672   void   make_illegal() {
 673     set(cannot_simplify);
 674     set_type(illegalType);
 675   }
 676 
 677   bool is_illegal() const {
 678     return type()->is_illegal();
 679   }
 680 
 681   // generic
 682   virtual void input_values_do(ValueVisitor* f) {
 683   }
 684 };
 685 
 686 
 687 // A local is a placeholder for an incoming argument to a function call.
 688 LEAF(Local, Instruction)
 689  private:
 690   int      _java_index;                          // the local index within the method to which the local belongs
 691   bool     _is_receiver;                         // if local variable holds the receiver: "this" for non-static methods
 692   ciType*  _declared_type;
 693  public:
 694   // creation
 695   Local(ciType* declared, ValueType* type, int index, bool receiver)
 696     : Instruction(type)
 697     , _java_index(index)
 698     , _is_receiver(receiver)
 699     , _declared_type(declared)
 700   {
 701     NOT_PRODUCT(set_printable_bci(-1));
 702   }
 703 
 704   // accessors
 705   int java_index() const                         { return _java_index; }
 706   bool is_receiver() const                       { return _is_receiver; }
 707 
 708   virtual ciType* declared_type() const          { return _declared_type; }
 709 
 710   // generic
 711   virtual void input_values_do(ValueVisitor* f)   { /* no values */ }
 712 };
 713 
 714 
 715 LEAF(Constant, Instruction)
 716  public:
 717   // creation
 718   Constant(ValueType* type):
 719       Instruction(type, NULL, /*type_is_constant*/ true)
 720   {
 721     assert(type->is_constant(), "must be a constant");
 722   }
 723 
 724   Constant(ValueType* type, ValueStack* state_before):
 725     Instruction(type, state_before, /*type_is_constant*/ true)
 726   {
 727     assert(state_before != NULL, "only used for constants which need patching");
 728     assert(type->is_constant(), "must be a constant");
 729     // since it's patching it needs to be pinned
 730     pin();
 731   }
 732 
 733   // generic
 734   virtual bool can_trap() const                  { return state_before() != NULL; }
 735   virtual void input_values_do(ValueVisitor* f)   { /* no values */ }
 736 
 737   virtual intx hash() const;
 738   virtual bool is_equal(Value v) const;
 739 
 740   virtual ciType* exact_type() const;
 741 
 742   enum CompareResult { not_comparable = -1, cond_false, cond_true };
 743 
 744   virtual CompareResult compare(Instruction::Condition condition, Value right) const;
 745   BlockBegin* compare(Instruction::Condition cond, Value right,
 746                       BlockBegin* true_sux, BlockBegin* false_sux) const {
 747     switch (compare(cond, right)) {
 748     case not_comparable:
 749       return NULL;
 750     case cond_false:
 751       return false_sux;
 752     case cond_true:
 753       return true_sux;
 754     default:
 755       ShouldNotReachHere();
 756       return NULL;
 757     }
 758   }
 759 };
 760 
 761 
 762 BASE(AccessField, Instruction)
 763  private:
 764   Value       _obj;
 765   int         _offset;
 766   ciField*    _field;
 767   NullCheck*  _explicit_null_check;              // For explicit null check elimination
 768 
 769  public:
 770   // creation
 771   AccessField(Value obj, int offset, ciField* field, bool is_static,
 772               ValueStack* state_before, bool needs_patching)
 773   : Instruction(as_ValueType(field->type()->basic_type()), state_before)
 774   , _obj(obj)
 775   , _offset(offset)
 776   , _field(field)
 777   , _explicit_null_check(NULL)
 778   {
 779     set_needs_null_check(!is_static);
 780     set_flag(IsStaticFlag, is_static);
 781     set_flag(NeedsPatchingFlag, needs_patching);
 782     ASSERT_VALUES
 783     // pin of all instructions with memory access
 784     pin();
 785   }
 786 
 787   // accessors
 788   Value obj() const                              { return _obj; }
 789   int offset() const                             { return _offset; }
 790   ciField* field() const                         { return _field; }
 791   BasicType field_type() const                   { return _field->type()->basic_type(); }
 792   bool is_static() const                         { return check_flag(IsStaticFlag); }
 793   NullCheck* explicit_null_check() const         { return _explicit_null_check; }
 794   bool needs_patching() const                    { return check_flag(NeedsPatchingFlag); }
 795 
 796   // Unresolved getstatic and putstatic can cause initialization.
 797   // Technically it occurs at the Constant that materializes the base
 798   // of the static fields but it's simpler to model it here.
 799   bool is_init_point() const                     { return is_static() && (needs_patching() || !_field->holder()->is_initialized()); }
 800 
 801   // manipulation
 802 
 803   // Under certain circumstances, if a previous NullCheck instruction
 804   // proved the target object non-null, we can eliminate the explicit
 805   // null check and do an implicit one, simply specifying the debug
 806   // information from the NullCheck. This field should only be consulted
 807   // if needs_null_check() is true.
 808   void set_explicit_null_check(NullCheck* check) { _explicit_null_check = check; }
 809 
 810   // generic
 811   virtual bool can_trap() const                  { return needs_null_check() || needs_patching(); }
 812   virtual void input_values_do(ValueVisitor* f)   { f->visit(&_obj); }
 813 };
 814 
 815 
 816 LEAF(LoadField, AccessField)
 817  public:
 818   // creation
 819   LoadField(Value obj, int offset, ciField* field, bool is_static,
 820             ValueStack* state_before, bool needs_patching)
 821   : AccessField(obj, offset, field, is_static, state_before, needs_patching)
 822   {}
 823 
 824   ciType* declared_type() const;
 825 
 826   // generic; cannot be eliminated if needs patching or if volatile.
 827   HASHING3(LoadField, !needs_patching() && !field()->is_volatile(), obj()->subst(), offset(), declared_type())
 828 };
 829 
 830 
 831 LEAF(StoreField, AccessField)
 832  private:
 833   Value _value;
 834 
 835  public:
 836   // creation
 837   StoreField(Value obj, int offset, ciField* field, Value value, bool is_static,
 838              ValueStack* state_before, bool needs_patching)
 839   : AccessField(obj, offset, field, is_static, state_before, needs_patching)
 840   , _value(value)
 841   {
 842     set_flag(NeedsWriteBarrierFlag, as_ValueType(field_type())->is_object());
 843     ASSERT_VALUES
 844     pin();
 845   }
 846 
 847   // accessors
 848   Value value() const                            { return _value; }
 849   bool needs_write_barrier() const               { return check_flag(NeedsWriteBarrierFlag); }
 850 
 851   // generic
 852   virtual void input_values_do(ValueVisitor* f)   { AccessField::input_values_do(f); f->visit(&_value); }
 853 };
 854 
 855 
 856 BASE(AccessArray, Instruction)
 857  private:
 858   Value       _array;
 859 
 860  public:
 861   // creation
 862   AccessArray(ValueType* type, Value array, ValueStack* state_before)
 863   : Instruction(type, state_before)
 864   , _array(array)
 865   {
 866     set_needs_null_check(true);
 867     ASSERT_VALUES
 868     pin(); // instruction with side effect (null exception or range check throwing)
 869   }
 870 
 871   Value array() const                            { return _array; }
 872 
 873   // generic
 874   virtual bool can_trap() const                  { return needs_null_check(); }
 875   virtual void input_values_do(ValueVisitor* f)   { f->visit(&_array); }
 876 };
 877 
 878 
 879 LEAF(ArrayLength, AccessArray)
 880  private:
 881   NullCheck*  _explicit_null_check;              // For explicit null check elimination
 882 
 883  public:
 884   // creation
 885   ArrayLength(Value array, ValueStack* state_before)
 886   : AccessArray(intType, array, state_before)
 887   , _explicit_null_check(NULL) {}
 888 
 889   // accessors
 890   NullCheck* explicit_null_check() const         { return _explicit_null_check; }
 891 
 892   // setters
 893   // See LoadField::set_explicit_null_check for documentation
 894   void set_explicit_null_check(NullCheck* check) { _explicit_null_check = check; }
 895 
 896   // generic
 897   HASHING1(ArrayLength, true, array()->subst())
 898 };
 899 
 900 
 901 BASE(AccessIndexed, AccessArray)
 902  private:
 903   Value     _index;
 904   Value     _length;
 905   BasicType _elt_type;
 906   bool      _mismatched;
 907 
 908  public:
 909   // creation
 910   AccessIndexed(Value array, Value index, Value length, BasicType elt_type, ValueStack* state_before, bool mismatched)
 911   : AccessArray(as_ValueType(elt_type), array, state_before)
 912   , _index(index)
 913   , _length(length)
 914   , _elt_type(elt_type)
 915   , _mismatched(mismatched)
 916   {
 917     set_flag(Instruction::NeedsRangeCheckFlag, true);
 918     ASSERT_VALUES
 919   }
 920 
 921   // accessors
 922   Value index() const                            { return _index; }
 923   Value length() const                           { return _length; }
 924   BasicType elt_type() const                     { return _elt_type; }
 925   bool mismatched() const                        { return _mismatched; }
 926 
 927   void clear_length()                            { _length = NULL; }
 928   // perform elimination of range checks involving constants
 929   bool compute_needs_range_check();
 930 
 931   // generic
 932   virtual void input_values_do(ValueVisitor* f)   { AccessArray::input_values_do(f); f->visit(&_index); if (_length != NULL) f->visit(&_length); }
 933 };
 934 
 935 
 936 LEAF(LoadIndexed, AccessIndexed)
 937  private:
 938   NullCheck*  _explicit_null_check;              // For explicit null check elimination
 939 
 940  public:
 941   // creation
 942   LoadIndexed(Value array, Value index, Value length, BasicType elt_type, ValueStack* state_before, bool mismatched = false)
 943   : AccessIndexed(array, index, length, elt_type, state_before, mismatched)
 944   , _explicit_null_check(NULL) {}
 945 
 946   // accessors
 947   NullCheck* explicit_null_check() const         { return _explicit_null_check; }
 948 
 949   // setters
 950   // See LoadField::set_explicit_null_check for documentation
 951   void set_explicit_null_check(NullCheck* check) { _explicit_null_check = check; }
 952 
 953   ciType* exact_type() const;
 954   ciType* declared_type() const;
 955 
 956   // generic;
 957   HASHING3(LoadIndexed, true, type()->tag(), array()->subst(), index()->subst())
 958 };
 959 
 960 
 961 LEAF(StoreIndexed, AccessIndexed)
 962  private:
 963   Value       _value;
 964 
 965   ciMethod* _profiled_method;
 966   int       _profiled_bci;
 967   bool      _check_boolean;
 968 
 969  public:
 970   // creation
 971   StoreIndexed(Value array, Value index, Value length, BasicType elt_type, Value value, ValueStack* state_before,
 972                bool check_boolean, bool mismatched = false)
 973   : AccessIndexed(array, index, length, elt_type, state_before, mismatched)
 974   , _value(value), _profiled_method(NULL), _profiled_bci(0), _check_boolean(check_boolean)
 975   {
 976     set_flag(NeedsWriteBarrierFlag, (as_ValueType(elt_type)->is_object()));
 977     set_flag(NeedsStoreCheckFlag, (as_ValueType(elt_type)->is_object()));
 978     ASSERT_VALUES
 979     pin();
 980   }
 981 
 982   // accessors
 983   Value value() const                            { return _value; }
 984   bool needs_write_barrier() const               { return check_flag(NeedsWriteBarrierFlag); }
 985   bool needs_store_check() const                 { return check_flag(NeedsStoreCheckFlag); }
 986   bool check_boolean() const                     { return _check_boolean; }
 987   // Helpers for MethodData* profiling
 988   void set_should_profile(bool value)                { set_flag(ProfileMDOFlag, value); }
 989   void set_profiled_method(ciMethod* method)         { _profiled_method = method;   }
 990   void set_profiled_bci(int bci)                     { _profiled_bci = bci;         }
 991   bool      should_profile() const                   { return check_flag(ProfileMDOFlag); }
 992   ciMethod* profiled_method() const                  { return _profiled_method;     }
 993   int       profiled_bci() const                     { return _profiled_bci;        }
 994   // generic
 995   virtual void input_values_do(ValueVisitor* f)   { AccessIndexed::input_values_do(f); f->visit(&_value); }
 996 };
 997 
 998 
 999 LEAF(NegateOp, Instruction)
1000  private:
1001   Value _x;
1002 
1003  public:
1004   // creation
1005   NegateOp(Value x) : Instruction(x->type()->base()), _x(x) {
1006     ASSERT_VALUES
1007   }
1008 
1009   // accessors
1010   Value x() const                                { return _x; }
1011 
1012   // generic
1013   virtual void input_values_do(ValueVisitor* f)   { f->visit(&_x); }
1014 };
1015 
1016 
1017 BASE(Op2, Instruction)
1018  private:
1019   Bytecodes::Code _op;
1020   Value           _x;
1021   Value           _y;
1022 
1023  public:
1024   // creation
1025   Op2(ValueType* type, Bytecodes::Code op, Value x, Value y, ValueStack* state_before = NULL)
1026   : Instruction(type, state_before)
1027   , _op(op)
1028   , _x(x)
1029   , _y(y)
1030   {
1031     ASSERT_VALUES
1032   }
1033 
1034   // accessors
1035   Bytecodes::Code op() const                     { return _op; }
1036   Value x() const                                { return _x; }
1037   Value y() const                                { return _y; }
1038 
1039   // manipulators
1040   void swap_operands() {
1041     assert(is_commutative(), "operation must be commutative");
1042     Value t = _x; _x = _y; _y = t;
1043   }
1044 
1045   // generic
1046   virtual bool is_commutative() const            { return false; }
1047   virtual void input_values_do(ValueVisitor* f)   { f->visit(&_x); f->visit(&_y); }
1048 };
1049 
1050 
1051 LEAF(ArithmeticOp, Op2)
1052  public:
1053   // creation
1054   ArithmeticOp(Bytecodes::Code op, Value x, Value y, ValueStack* state_before)
1055   : Op2(x->type()->meet(y->type()), op, x, y, state_before)
1056   {
1057     if (can_trap()) pin();
1058   }
1059 
1060   // generic
1061   virtual bool is_commutative() const;
1062   virtual bool can_trap() const;
1063   HASHING3(Op2, true, op(), x()->subst(), y()->subst())
1064 };
1065 
1066 
1067 LEAF(ShiftOp, Op2)
1068  public:
1069   // creation
1070   ShiftOp(Bytecodes::Code op, Value x, Value s) : Op2(x->type()->base(), op, x, s) {}
1071 
1072   // generic
1073   HASHING3(Op2, true, op(), x()->subst(), y()->subst())
1074 };
1075 
1076 
1077 LEAF(LogicOp, Op2)
1078  public:
1079   // creation
1080   LogicOp(Bytecodes::Code op, Value x, Value y) : Op2(x->type()->meet(y->type()), op, x, y) {}
1081 
1082   // generic
1083   virtual bool is_commutative() const;
1084   HASHING3(Op2, true, op(), x()->subst(), y()->subst())
1085 };
1086 
1087 
1088 LEAF(CompareOp, Op2)
1089  public:
1090   // creation
1091   CompareOp(Bytecodes::Code op, Value x, Value y, ValueStack* state_before)
1092   : Op2(intType, op, x, y, state_before)
1093   {}
1094 
1095   // generic
1096   HASHING3(Op2, true, op(), x()->subst(), y()->subst())
1097 };
1098 
1099 
1100 LEAF(IfOp, Op2)
1101  private:
1102   Value _tval;
1103   Value _fval;
1104 
1105  public:
1106   // creation
1107   IfOp(Value x, Condition cond, Value y, Value tval, Value fval)
1108   : Op2(tval->type()->meet(fval->type()), (Bytecodes::Code)cond, x, y)
1109   , _tval(tval)
1110   , _fval(fval)
1111   {
1112     ASSERT_VALUES
1113     assert(tval->type()->tag() == fval->type()->tag(), "types must match");
1114   }
1115 
1116   // accessors
1117   virtual bool is_commutative() const;
1118   Bytecodes::Code op() const                     { ShouldNotCallThis(); return Bytecodes::_illegal; }
1119   Condition cond() const                         { return (Condition)Op2::op(); }
1120   Value tval() const                             { return _tval; }
1121   Value fval() const                             { return _fval; }
1122 
1123   // generic
1124   virtual void input_values_do(ValueVisitor* f)   { Op2::input_values_do(f); f->visit(&_tval); f->visit(&_fval); }
1125 };
1126 
1127 
1128 LEAF(Convert, Instruction)
1129  private:
1130   Bytecodes::Code _op;
1131   Value           _value;
1132 
1133  public:
1134   // creation
1135   Convert(Bytecodes::Code op, Value value, ValueType* to_type) : Instruction(to_type), _op(op), _value(value) {
1136     ASSERT_VALUES
1137   }
1138 
1139   // accessors
1140   Bytecodes::Code op() const                     { return _op; }
1141   Value value() const                            { return _value; }
1142 
1143   // generic
1144   virtual void input_values_do(ValueVisitor* f)   { f->visit(&_value); }
1145   HASHING2(Convert, true, op(), value()->subst())
1146 };
1147 
1148 
1149 LEAF(NullCheck, Instruction)
1150  private:
1151   Value       _obj;
1152 
1153  public:
1154   // creation
1155   NullCheck(Value obj, ValueStack* state_before)
1156   : Instruction(obj->type()->base(), state_before)
1157   , _obj(obj)
1158   {
1159     ASSERT_VALUES
1160     set_can_trap(true);
1161     assert(_obj->type()->is_object(), "null check must be applied to objects only");
1162     pin(Instruction::PinExplicitNullCheck);
1163   }
1164 
1165   // accessors
1166   Value obj() const                              { return _obj; }
1167 
1168   // setters
1169   void set_can_trap(bool can_trap)               { set_flag(CanTrapFlag, can_trap); }
1170 
1171   // generic
1172   virtual bool can_trap() const                  { return check_flag(CanTrapFlag); /* null-check elimination sets to false */ }
1173   virtual void input_values_do(ValueVisitor* f)   { f->visit(&_obj); }
1174   HASHING1(NullCheck, true, obj()->subst())
1175 };
1176 
1177 
1178 // This node is supposed to cast the type of another node to a more precise
1179 // declared type.
1180 LEAF(TypeCast, Instruction)
1181  private:
1182   ciType* _declared_type;
1183   Value   _obj;
1184 
1185  public:
1186   // The type of this node is the same type as the object type (and it might be constant).
1187   TypeCast(ciType* type, Value obj, ValueStack* state_before)
1188   : Instruction(obj->type(), state_before, obj->type()->is_constant()),
1189     _declared_type(type),
1190     _obj(obj) {}
1191 
1192   // accessors
1193   ciType* declared_type() const                  { return _declared_type; }
1194   Value   obj() const                            { return _obj; }
1195 
1196   // generic
1197   virtual void input_values_do(ValueVisitor* f)  { f->visit(&_obj); }
1198 };
1199 
1200 
1201 BASE(StateSplit, Instruction)
1202  private:
1203   ValueStack* _state;
1204 
1205  protected:
1206   static void substitute(BlockList& list, BlockBegin* old_block, BlockBegin* new_block);
1207 
1208  public:
1209   // creation
1210   StateSplit(ValueType* type, ValueStack* state_before = NULL)
1211   : Instruction(type, state_before)
1212   , _state(NULL)
1213   {
1214     pin(PinStateSplitConstructor);
1215   }
1216 
1217   // accessors
1218   ValueStack* state() const                      { return _state; }
1219   IRScope* scope() const;                        // the state's scope
1220 
1221   // manipulation
1222   void set_state(ValueStack* state)              { assert(_state == NULL, "overwriting existing state"); check_state(state); _state = state; }
1223 
1224   // generic
1225   virtual void input_values_do(ValueVisitor* f)   { /* no values */ }
1226   virtual void state_values_do(ValueVisitor* f);
1227 };
1228 
1229 
1230 LEAF(Invoke, StateSplit)
1231  private:
1232   Bytecodes::Code _code;
1233   Value           _recv;
1234   Values*         _args;
1235   BasicTypeList*  _signature;
1236   ciMethod*       _target;
1237 
1238  public:
1239   // creation
1240   Invoke(Bytecodes::Code code, ValueType* result_type, Value recv, Values* args,
1241          ciMethod* target, ValueStack* state_before);
1242 
1243   // accessors
1244   Bytecodes::Code code() const                   { return _code; }
1245   Value receiver() const                         { return _recv; }
1246   bool has_receiver() const                      { return receiver() != NULL; }
1247   int number_of_arguments() const                { return _args->length(); }
1248   Value argument_at(int i) const                 { return _args->at(i); }
1249   BasicTypeList* signature() const               { return _signature; }
1250   ciMethod* target() const                       { return _target; }
1251 
1252   ciType* declared_type() const;
1253 
1254   // Returns false if target is not loaded
1255   bool target_is_final() const                   { return check_flag(TargetIsFinalFlag); }
1256   bool target_is_loaded() const                  { return check_flag(TargetIsLoadedFlag); }
1257 
1258   // JSR 292 support
1259   bool is_invokedynamic() const                  { return code() == Bytecodes::_invokedynamic; }
1260   bool is_method_handle_intrinsic() const        { return target()->is_method_handle_intrinsic(); }
1261 
1262   virtual bool needs_exception_state() const     { return false; }
1263 
1264   // generic
1265   virtual bool can_trap() const                  { return true; }
1266   virtual void input_values_do(ValueVisitor* f) {
1267     StateSplit::input_values_do(f);
1268     if (has_receiver()) f->visit(&_recv);
1269     for (int i = 0; i < _args->length(); i++) f->visit(_args->adr_at(i));
1270   }
1271   virtual void state_values_do(ValueVisitor *f);
1272 };
1273 
1274 
1275 LEAF(NewInstance, StateSplit)
1276  private:
1277   ciInstanceKlass* _klass;
1278   bool _is_unresolved;
1279 
1280  public:
1281   // creation
1282   NewInstance(ciInstanceKlass* klass, ValueStack* state_before, bool is_unresolved)
1283   : StateSplit(instanceType, state_before)
1284   , _klass(klass), _is_unresolved(is_unresolved)
1285   {}
1286 
1287   // accessors
1288   ciInstanceKlass* klass() const                 { return _klass; }
1289   bool is_unresolved() const                     { return _is_unresolved; }
1290 
1291   virtual bool needs_exception_state() const     { return false; }
1292 
1293   // generic
1294   virtual bool can_trap() const                  { return true; }
1295   ciType* exact_type() const;
1296   ciType* declared_type() const;
1297 };
1298 
1299 
1300 BASE(NewArray, StateSplit)
1301  private:
1302   Value       _length;
1303 
1304  public:
1305   // creation
1306   NewArray(Value length, ValueStack* state_before)
1307   : StateSplit(objectType, state_before)
1308   , _length(length)
1309   {
1310     // Do not ASSERT_VALUES since length is NULL for NewMultiArray
1311   }
1312 
1313   // accessors
1314   Value length() const                           { return _length; }
1315 
1316   virtual bool needs_exception_state() const     { return false; }
1317 
1318   ciType* exact_type() const                     { return NULL; }
1319   ciType* declared_type() const;
1320 
1321   // generic
1322   virtual bool can_trap() const                  { return true; }
1323   virtual void input_values_do(ValueVisitor* f)   { StateSplit::input_values_do(f); f->visit(&_length); }
1324 };
1325 
1326 
1327 LEAF(NewTypeArray, NewArray)
1328  private:
1329   BasicType _elt_type;
1330 
1331  public:
1332   // creation
1333   NewTypeArray(Value length, BasicType elt_type, ValueStack* state_before)
1334   : NewArray(length, state_before)
1335   , _elt_type(elt_type)
1336   {}
1337 
1338   // accessors
1339   BasicType elt_type() const                     { return _elt_type; }
1340   ciType* exact_type() const;
1341 };
1342 
1343 
1344 LEAF(NewObjectArray, NewArray)
1345  private:
1346   ciKlass* _klass;
1347 
1348  public:
1349   // creation
1350   NewObjectArray(ciKlass* klass, Value length, ValueStack* state_before) : NewArray(length, state_before), _klass(klass) {}
1351 
1352   // accessors
1353   ciKlass* klass() const                         { return _klass; }
1354   ciType* exact_type() const;
1355 };
1356 
1357 
1358 LEAF(NewMultiArray, NewArray)
1359  private:
1360   ciKlass* _klass;
1361   Values*  _dims;
1362 
1363  public:
1364   // creation
1365   NewMultiArray(ciKlass* klass, Values* dims, ValueStack* state_before) : NewArray(NULL, state_before), _klass(klass), _dims(dims) {
1366     ASSERT_VALUES
1367   }
1368 
1369   // accessors
1370   ciKlass* klass() const                         { return _klass; }
1371   Values* dims() const                           { return _dims; }
1372   int rank() const                               { return dims()->length(); }
1373 
1374   // generic
1375   virtual void input_values_do(ValueVisitor* f) {
1376     // NOTE: we do not call NewArray::input_values_do since "length"
1377     // is meaningless for a multi-dimensional array; passing the
1378     // zeroth element down to NewArray as its length is a bad idea
1379     // since there will be a copy in the "dims" array which doesn't
1380     // get updated, and the value must not be traversed twice. Was bug
1381     // - kbr 4/10/2001
1382     StateSplit::input_values_do(f);
1383     for (int i = 0; i < _dims->length(); i++) f->visit(_dims->adr_at(i));
1384   }
1385 };
1386 
1387 
1388 BASE(TypeCheck, StateSplit)
1389  private:
1390   ciKlass*    _klass;
1391   Value       _obj;
1392 
1393   ciMethod* _profiled_method;
1394   int       _profiled_bci;
1395 
1396  public:
1397   // creation
1398   TypeCheck(ciKlass* klass, Value obj, ValueType* type, ValueStack* state_before)
1399   : StateSplit(type, state_before), _klass(klass), _obj(obj),
1400     _profiled_method(NULL), _profiled_bci(0) {
1401     ASSERT_VALUES
1402     set_direct_compare(false);
1403   }
1404 
1405   // accessors
1406   ciKlass* klass() const                         { return _klass; }
1407   Value obj() const                              { return _obj; }
1408   bool is_loaded() const                         { return klass() != NULL; }
1409   bool direct_compare() const                    { return check_flag(DirectCompareFlag); }
1410 
1411   // manipulation
1412   void set_direct_compare(bool flag)             { set_flag(DirectCompareFlag, flag); }
1413 
1414   // generic
1415   virtual bool can_trap() const                  { return true; }
1416   virtual void input_values_do(ValueVisitor* f)   { StateSplit::input_values_do(f); f->visit(&_obj); }
1417 
1418   // Helpers for MethodData* profiling
1419   void set_should_profile(bool value)                { set_flag(ProfileMDOFlag, value); }
1420   void set_profiled_method(ciMethod* method)         { _profiled_method = method;   }
1421   void set_profiled_bci(int bci)                     { _profiled_bci = bci;         }
1422   bool      should_profile() const                   { return check_flag(ProfileMDOFlag); }
1423   ciMethod* profiled_method() const                  { return _profiled_method;     }
1424   int       profiled_bci() const                     { return _profiled_bci;        }
1425 };
1426 
1427 
1428 LEAF(CheckCast, TypeCheck)
1429  public:
1430   // creation
1431   CheckCast(ciKlass* klass, Value obj, ValueStack* state_before)
1432   : TypeCheck(klass, obj, objectType, state_before) {}
1433 
1434   void set_incompatible_class_change_check() {
1435     set_flag(ThrowIncompatibleClassChangeErrorFlag, true);
1436   }
1437   bool is_incompatible_class_change_check() const {
1438     return check_flag(ThrowIncompatibleClassChangeErrorFlag);
1439   }
1440   void set_invokespecial_receiver_check() {
1441     set_flag(InvokeSpecialReceiverCheckFlag, true);
1442   }
1443   bool is_invokespecial_receiver_check() const {
1444     return check_flag(InvokeSpecialReceiverCheckFlag);
1445   }
1446 
1447   virtual bool needs_exception_state() const {
1448     return !is_invokespecial_receiver_check();
1449   }
1450 
1451   ciType* declared_type() const;
1452 };
1453 
1454 
1455 LEAF(InstanceOf, TypeCheck)
1456  public:
1457   // creation
1458   InstanceOf(ciKlass* klass, Value obj, ValueStack* state_before) : TypeCheck(klass, obj, intType, state_before) {}
1459 
1460   virtual bool needs_exception_state() const     { return false; }
1461 };
1462 
1463 
1464 BASE(AccessMonitor, StateSplit)
1465  private:
1466   Value       _obj;
1467   int         _monitor_no;
1468 
1469  public:
1470   // creation
1471   AccessMonitor(Value obj, int monitor_no, ValueStack* state_before = NULL)
1472   : StateSplit(illegalType, state_before)
1473   , _obj(obj)
1474   , _monitor_no(monitor_no)
1475   {
1476     set_needs_null_check(true);
1477     ASSERT_VALUES
1478   }
1479 
1480   // accessors
1481   Value obj() const                              { return _obj; }
1482   int monitor_no() const                         { return _monitor_no; }
1483 
1484   // generic
1485   virtual void input_values_do(ValueVisitor* f)   { StateSplit::input_values_do(f); f->visit(&_obj); }
1486 };
1487 
1488 
1489 LEAF(MonitorEnter, AccessMonitor)
1490  public:
1491   // creation
1492   MonitorEnter(Value obj, int monitor_no, ValueStack* state_before)
1493   : AccessMonitor(obj, monitor_no, state_before)
1494   {
1495     ASSERT_VALUES
1496   }
1497 
1498   // generic
1499   virtual bool can_trap() const                  { return true; }
1500 };
1501 
1502 
1503 LEAF(MonitorExit, AccessMonitor)
1504  public:
1505   // creation
1506   MonitorExit(Value obj, int monitor_no)
1507   : AccessMonitor(obj, monitor_no, NULL)
1508   {
1509     ASSERT_VALUES
1510   }
1511 };
1512 
1513 
1514 LEAF(Intrinsic, StateSplit)
1515  private:
1516   vmIntrinsics::ID _id;
1517   Values*          _args;
1518   Value            _recv;
1519   ArgsNonNullState _nonnull_state;
1520 
1521  public:
1522   // preserves_state can be set to true for Intrinsics
1523   // which are guaranteed to preserve register state across any slow
1524   // cases; setting it to true does not mean that the Intrinsic can
1525   // not trap, only that if we continue execution in the same basic
1526   // block after the Intrinsic, all of the registers are intact. This
1527   // allows load elimination and common expression elimination to be
1528   // performed across the Intrinsic.  The default value is false.
1529   Intrinsic(ValueType* type,
1530             vmIntrinsics::ID id,
1531             Values* args,
1532             bool has_receiver,
1533             ValueStack* state_before,
1534             bool preserves_state,
1535             bool cantrap = true)
1536   : StateSplit(type, state_before)
1537   , _id(id)
1538   , _args(args)
1539   , _recv(NULL)
1540   {
1541     assert(args != NULL, "args must exist");
1542     ASSERT_VALUES
1543     set_flag(PreservesStateFlag, preserves_state);
1544     set_flag(CanTrapFlag,        cantrap);
1545     if (has_receiver) {
1546       _recv = argument_at(0);
1547     }
1548     set_needs_null_check(has_receiver);
1549 
1550     // some intrinsics can't trap, so don't force them to be pinned
1551     if (!can_trap() && !vmIntrinsics::should_be_pinned(_id)) {
1552       unpin(PinStateSplitConstructor);
1553     }
1554   }
1555 
1556   // accessors
1557   vmIntrinsics::ID id() const                    { return _id; }
1558   int number_of_arguments() const                { return _args->length(); }
1559   Value argument_at(int i) const                 { return _args->at(i); }
1560 
1561   bool has_receiver() const                      { return (_recv != NULL); }
1562   Value receiver() const                         { assert(has_receiver(), "must have receiver"); return _recv; }
1563   bool preserves_state() const                   { return check_flag(PreservesStateFlag); }
1564 
1565   bool arg_needs_null_check(int i) const {
1566     return _nonnull_state.arg_needs_null_check(i);
1567   }
1568 
1569   void set_arg_needs_null_check(int i, bool check) {
1570     _nonnull_state.set_arg_needs_null_check(i, check);
1571   }
1572 
1573   // generic
1574   virtual bool can_trap() const                  { return check_flag(CanTrapFlag); }
1575   virtual void input_values_do(ValueVisitor* f) {
1576     StateSplit::input_values_do(f);
1577     for (int i = 0; i < _args->length(); i++) f->visit(_args->adr_at(i));
1578   }
1579 };
1580 
1581 
1582 class LIR_List;
1583 
1584 LEAF(BlockBegin, StateSplit)
1585  private:
1586   int        _block_id;                          // the unique block id
1587   int        _bci;                               // start-bci of block
1588   int        _depth_first_number;                // number of this block in a depth-first ordering
1589   int        _linear_scan_number;                // number of this block in linear-scan ordering
1590   int        _dominator_depth;
1591   int        _loop_depth;                        // the loop nesting level of this block
1592   int        _loop_index;                        // number of the innermost loop of this block
1593   int        _flags;                             // the flags associated with this block
1594 
1595   // fields used by BlockListBuilder
1596   int            _total_preds;                   // number of predecessors found by BlockListBuilder
1597   ResourceBitMap _stores_to_locals;              // bit is set when a local variable is stored in the block
1598 
1599   // SSA specific fields: (factor out later)
1600   BlockList   _successors;                       // the successors of this block
1601   BlockList   _predecessors;                     // the predecessors of this block
1602   BlockList   _dominates;                        // list of blocks that are dominated by this block
1603   BlockBegin* _dominator;                        // the dominator of this block
1604   // SSA specific ends
1605   BlockEnd*  _end;                               // the last instruction of this block
1606   BlockList  _exception_handlers;                // the exception handlers potentially invoked by this block
1607   ValueStackStack* _exception_states;            // only for xhandler entries: states of all instructions that have an edge to this xhandler
1608   int        _exception_handler_pco;             // if this block is the start of an exception handler,
1609                                                  // this records the PC offset in the assembly code of the
1610                                                  // first instruction in this block
1611   Label      _label;                             // the label associated with this block
1612   LIR_List*  _lir;                               // the low level intermediate representation for this block
1613 
1614   ResourceBitMap _live_in;                       // set of live LIR_Opr registers at entry to this block
1615   ResourceBitMap _live_out;                      // set of live LIR_Opr registers at exit from this block
1616   ResourceBitMap _live_gen;                      // set of registers used before any redefinition in this block
1617   ResourceBitMap _live_kill;                     // set of registers defined in this block
1618 
1619   ResourceBitMap _fpu_register_usage;
1620   intArray*      _fpu_stack_state;               // For x86 FPU code generation with UseLinearScan
1621   int            _first_lir_instruction_id;      // ID of first LIR instruction in this block
1622   int            _last_lir_instruction_id;       // ID of last LIR instruction in this block
1623 
1624   void iterate_preorder (boolArray& mark, BlockClosure* closure);
1625   void iterate_postorder(boolArray& mark, BlockClosure* closure);
1626 
1627   friend class SuxAndWeightAdjuster;
1628 
1629  public:
1630    void* operator new(size_t size) throw() {
1631     Compilation* c = Compilation::current();
1632     void* res = c->arena()->Amalloc(size);
1633     return res;
1634   }
1635 
1636   // initialization/counting
1637   static int  number_of_blocks() {
1638     return Compilation::current()->number_of_blocks();
1639   }
1640 
1641   // creation
1642   BlockBegin(int bci)
1643   : StateSplit(illegalType)
1644   , _block_id(Compilation::current()->get_next_block_id())
1645   , _bci(bci)
1646   , _depth_first_number(-1)
1647   , _linear_scan_number(-1)
1648   , _dominator_depth(-1)
1649   , _loop_depth(0)
1650   , _loop_index(-1)
1651   , _flags(0)
1652   , _total_preds(0)
1653   , _stores_to_locals()
1654   , _successors(2)
1655   , _predecessors(2)
1656   , _dominates(2)
1657   , _dominator(NULL)
1658   , _end(NULL)
1659   , _exception_handlers(1)
1660   , _exception_states(NULL)
1661   , _exception_handler_pco(-1)
1662   , _lir(NULL)
1663   , _live_in()
1664   , _live_out()
1665   , _live_gen()
1666   , _live_kill()
1667   , _fpu_register_usage()
1668   , _fpu_stack_state(NULL)
1669   , _first_lir_instruction_id(-1)
1670   , _last_lir_instruction_id(-1)
1671   {
1672     _block = this;
1673 #ifndef PRODUCT
1674     set_printable_bci(bci);
1675 #endif
1676   }
1677 
1678   // accessors
1679   int block_id() const                           { return _block_id; }
1680   int bci() const                                { return _bci; }
1681   BlockList* successors()                        { return &_successors; }
1682   BlockList* dominates()                         { return &_dominates; }
1683   BlockBegin* dominator() const                  { return _dominator; }
1684   int loop_depth() const                         { return _loop_depth; }
1685   int dominator_depth() const                    { return _dominator_depth; }
1686   int depth_first_number() const                 { return _depth_first_number; }
1687   int linear_scan_number() const                 { return _linear_scan_number; }
1688   BlockEnd* end() const                          { return _end; }
1689   Label* label()                                 { return &_label; }
1690   LIR_List* lir() const                          { return _lir; }
1691   int exception_handler_pco() const              { return _exception_handler_pco; }
1692   ResourceBitMap& live_in()                      { return _live_in;        }
1693   ResourceBitMap& live_out()                     { return _live_out;       }
1694   ResourceBitMap& live_gen()                     { return _live_gen;       }
1695   ResourceBitMap& live_kill()                    { return _live_kill;      }
1696   ResourceBitMap& fpu_register_usage()           { return _fpu_register_usage; }
1697   intArray* fpu_stack_state() const              { return _fpu_stack_state;    }
1698   int first_lir_instruction_id() const           { return _first_lir_instruction_id; }
1699   int last_lir_instruction_id() const            { return _last_lir_instruction_id; }
1700   int total_preds() const                        { return _total_preds; }
1701   BitMap& stores_to_locals()                     { return _stores_to_locals; }
1702 
1703   // manipulation
1704   void set_dominator(BlockBegin* dom)            { _dominator = dom; }
1705   void set_loop_depth(int d)                     { _loop_depth = d; }
1706   void set_dominator_depth(int d)                { _dominator_depth = d; }
1707   void set_depth_first_number(int dfn)           { _depth_first_number = dfn; }
1708   void set_linear_scan_number(int lsn)           { _linear_scan_number = lsn; }
1709   void set_end(BlockEnd* end);
1710   void clear_end();
1711   void disconnect_from_graph();
1712   static void disconnect_edge(BlockBegin* from, BlockBegin* to);
1713   BlockBegin* insert_block_between(BlockBegin* sux);
1714   void substitute_sux(BlockBegin* old_sux, BlockBegin* new_sux);
1715   void set_lir(LIR_List* lir)                    { _lir = lir; }
1716   void set_exception_handler_pco(int pco)        { _exception_handler_pco = pco; }
1717   void set_live_in  (const ResourceBitMap& map)  { _live_in = map;   }
1718   void set_live_out (const ResourceBitMap& map)  { _live_out = map;  }
1719   void set_live_gen (const ResourceBitMap& map)  { _live_gen = map;  }
1720   void set_live_kill(const ResourceBitMap& map)  { _live_kill = map; }
1721   void set_fpu_register_usage(const ResourceBitMap& map) { _fpu_register_usage = map; }
1722   void set_fpu_stack_state(intArray* state)      { _fpu_stack_state = state;  }
1723   void set_first_lir_instruction_id(int id)      { _first_lir_instruction_id = id;  }
1724   void set_last_lir_instruction_id(int id)       { _last_lir_instruction_id = id;  }
1725   void increment_total_preds(int n = 1)          { _total_preds += n; }
1726   void init_stores_to_locals(int locals_count)   { _stores_to_locals.initialize(locals_count); }
1727 
1728   // generic
1729   virtual void state_values_do(ValueVisitor* f);
1730 
1731   // successors and predecessors
1732   int number_of_sux() const;
1733   BlockBegin* sux_at(int i) const;
1734   void add_successor(BlockBegin* sux);
1735   void remove_successor(BlockBegin* pred);
1736   bool is_successor(BlockBegin* sux) const       { return _successors.contains(sux); }
1737 
1738   void add_predecessor(BlockBegin* pred);
1739   void remove_predecessor(BlockBegin* pred);
1740   bool is_predecessor(BlockBegin* pred) const    { return _predecessors.contains(pred); }
1741   int number_of_preds() const                    { return _predecessors.length(); }
1742   BlockBegin* pred_at(int i) const               { return _predecessors.at(i); }
1743 
1744   // exception handlers potentially invoked by this block
1745   void add_exception_handler(BlockBegin* b);
1746   bool is_exception_handler(BlockBegin* b) const { return _exception_handlers.contains(b); }
1747   int  number_of_exception_handlers() const      { return _exception_handlers.length(); }
1748   BlockBegin* exception_handler_at(int i) const  { return _exception_handlers.at(i); }
1749 
1750   // states of the instructions that have an edge to this exception handler
1751   int number_of_exception_states()               { assert(is_set(exception_entry_flag), "only for xhandlers"); return _exception_states == NULL ? 0 : _exception_states->length(); }
1752   ValueStack* exception_state_at(int idx) const  { assert(is_set(exception_entry_flag), "only for xhandlers"); return _exception_states->at(idx); }
1753   int add_exception_state(ValueStack* state);
1754 
1755   // flags
1756   enum Flag {
1757     no_flag                       = 0,
1758     std_entry_flag                = 1 << 0,
1759     osr_entry_flag                = 1 << 1,
1760     exception_entry_flag          = 1 << 2,
1761     subroutine_entry_flag         = 1 << 3,
1762     backward_branch_target_flag   = 1 << 4,
1763     is_on_work_list_flag          = 1 << 5,
1764     was_visited_flag              = 1 << 6,
1765     parser_loop_header_flag       = 1 << 7,  // set by parser to identify blocks where phi functions can not be created on demand
1766     critical_edge_split_flag      = 1 << 8, // set for all blocks that are introduced when critical edges are split
1767     linear_scan_loop_header_flag  = 1 << 9, // set during loop-detection for LinearScan
1768     linear_scan_loop_end_flag     = 1 << 10, // set during loop-detection for LinearScan
1769     donot_eliminate_range_checks  = 1 << 11  // Should be try to eliminate range checks in this block
1770   };
1771 
1772   void set(Flag f)                               { _flags |= f; }
1773   void clear(Flag f)                             { _flags &= ~f; }
1774   bool is_set(Flag f) const                      { return (_flags & f) != 0; }
1775   bool is_entry_block() const {
1776     const int entry_mask = std_entry_flag | osr_entry_flag | exception_entry_flag;
1777     return (_flags & entry_mask) != 0;
1778   }
1779 
1780   // iteration
1781   void iterate_preorder   (BlockClosure* closure);
1782   void iterate_postorder  (BlockClosure* closure);
1783 
1784   void block_values_do(ValueVisitor* f);
1785 
1786   // loops
1787   void set_loop_index(int ix)                    { _loop_index = ix;        }
1788   int  loop_index() const                        { return _loop_index;      }
1789 
1790   // merging
1791   bool try_merge(ValueStack* state);             // try to merge states at block begin
1792   void merge(ValueStack* state)                  { bool b = try_merge(state); assert(b, "merge failed"); }
1793 
1794   // debugging
1795   void print_block()                             PRODUCT_RETURN;
1796   void print_block(InstructionPrinter& ip, bool live_only = false) PRODUCT_RETURN;
1797 };
1798 
1799 
1800 BASE(BlockEnd, StateSplit)
1801  private:
1802   BlockList*  _sux;
1803 
1804  protected:
1805   BlockList* sux() const                         { return _sux; }
1806 
1807   void set_sux(BlockList* sux) {
1808 #ifdef ASSERT
1809     assert(sux != NULL, "sux must exist");
1810     for (int i = sux->length() - 1; i >= 0; i--) assert(sux->at(i) != NULL, "sux must exist");
1811 #endif
1812     _sux = sux;
1813   }
1814 
1815  public:
1816   // creation
1817   BlockEnd(ValueType* type, ValueStack* state_before, bool is_safepoint)
1818   : StateSplit(type, state_before)
1819   , _sux(NULL)
1820   {
1821     set_flag(IsSafepointFlag, is_safepoint);
1822   }
1823 
1824   // accessors
1825   bool is_safepoint() const                      { return check_flag(IsSafepointFlag); }
1826   // For compatibility with old code, for new code use block()
1827   BlockBegin* begin() const                      { return _block; }
1828 
1829   // manipulation
1830   void set_begin(BlockBegin* begin);
1831 
1832   // successors
1833   int number_of_sux() const                      { return _sux != NULL ? _sux->length() : 0; }
1834   BlockBegin* sux_at(int i) const                { return _sux->at(i); }
1835   BlockBegin* default_sux() const                { return sux_at(number_of_sux() - 1); }
1836   BlockBegin** addr_sux_at(int i) const          { return _sux->adr_at(i); }
1837   int sux_index(BlockBegin* sux) const           { return _sux->find(sux); }
1838   void substitute_sux(BlockBegin* old_sux, BlockBegin* new_sux);
1839 };
1840 
1841 
1842 LEAF(Goto, BlockEnd)
1843  public:
1844   enum Direction {
1845     none,            // Just a regular goto
1846     taken, not_taken // Goto produced from If
1847   };
1848  private:
1849   ciMethod*   _profiled_method;
1850   int         _profiled_bci;
1851   Direction   _direction;
1852  public:
1853   // creation
1854   Goto(BlockBegin* sux, ValueStack* state_before, bool is_safepoint = false)
1855     : BlockEnd(illegalType, state_before, is_safepoint)
1856     , _profiled_method(NULL)
1857     , _profiled_bci(0)
1858     , _direction(none) {
1859     BlockList* s = new BlockList(1);
1860     s->append(sux);
1861     set_sux(s);
1862   }
1863 
1864   Goto(BlockBegin* sux, bool is_safepoint) : BlockEnd(illegalType, NULL, is_safepoint)
1865                                            , _profiled_method(NULL)
1866                                            , _profiled_bci(0)
1867                                            , _direction(none) {
1868     BlockList* s = new BlockList(1);
1869     s->append(sux);
1870     set_sux(s);
1871   }
1872 
1873   bool should_profile() const                    { return check_flag(ProfileMDOFlag); }
1874   ciMethod* profiled_method() const              { return _profiled_method; } // set only for profiled branches
1875   int profiled_bci() const                       { return _profiled_bci; }
1876   Direction direction() const                    { return _direction; }
1877 
1878   void set_should_profile(bool value)            { set_flag(ProfileMDOFlag, value); }
1879   void set_profiled_method(ciMethod* method)     { _profiled_method = method; }
1880   void set_profiled_bci(int bci)                 { _profiled_bci = bci; }
1881   void set_direction(Direction d)                { _direction = d; }
1882 };
1883 
1884 #ifdef ASSERT
1885 LEAF(Assert, Instruction)
1886   private:
1887   Value       _x;
1888   Condition   _cond;
1889   Value       _y;
1890   char        *_message;
1891 
1892  public:
1893   // creation
1894   // unordered_is_true is valid for float/double compares only
1895    Assert(Value x, Condition cond, bool unordered_is_true, Value y);
1896 
1897   // accessors
1898   Value x() const                                { return _x; }
1899   Condition cond() const                         { return _cond; }
1900   bool unordered_is_true() const                 { return check_flag(UnorderedIsTrueFlag); }
1901   Value y() const                                { return _y; }
1902   const char *message() const                    { return _message; }
1903 
1904   // generic
1905   virtual void input_values_do(ValueVisitor* f)  { f->visit(&_x); f->visit(&_y); }
1906 };
1907 #endif
1908 
1909 LEAF(RangeCheckPredicate, StateSplit)
1910  private:
1911   Value       _x;
1912   Condition   _cond;
1913   Value       _y;
1914 
1915   void check_state();
1916 
1917  public:
1918   // creation
1919   // unordered_is_true is valid for float/double compares only
1920    RangeCheckPredicate(Value x, Condition cond, bool unordered_is_true, Value y, ValueStack* state) : StateSplit(illegalType)
1921   , _x(x)
1922   , _cond(cond)
1923   , _y(y)
1924   {
1925     ASSERT_VALUES
1926     set_flag(UnorderedIsTrueFlag, unordered_is_true);
1927     assert(x->type()->tag() == y->type()->tag(), "types must match");
1928     this->set_state(state);
1929     check_state();
1930   }
1931 
1932   // Always deoptimize
1933   RangeCheckPredicate(ValueStack* state) : StateSplit(illegalType)
1934   {
1935     this->set_state(state);
1936     _x = _y = NULL;
1937     check_state();
1938   }
1939 
1940   // accessors
1941   Value x() const                                { return _x; }
1942   Condition cond() const                         { return _cond; }
1943   bool unordered_is_true() const                 { return check_flag(UnorderedIsTrueFlag); }
1944   Value y() const                                { return _y; }
1945 
1946   void always_fail()                             { _x = _y = NULL; }
1947 
1948   // generic
1949   virtual void input_values_do(ValueVisitor* f)  { StateSplit::input_values_do(f); f->visit(&_x); f->visit(&_y); }
1950   HASHING3(RangeCheckPredicate, true, x()->subst(), y()->subst(), cond())
1951 };
1952 
1953 LEAF(If, BlockEnd)
1954  private:
1955   Value       _x;
1956   Condition   _cond;
1957   Value       _y;
1958   ciMethod*   _profiled_method;
1959   int         _profiled_bci; // Canonicalizer may alter bci of If node
1960   bool        _swapped;      // Is the order reversed with respect to the original If in the
1961                              // bytecode stream?
1962  public:
1963   // creation
1964   // unordered_is_true is valid for float/double compares only
1965   If(Value x, Condition cond, bool unordered_is_true, Value y, BlockBegin* tsux, BlockBegin* fsux, ValueStack* state_before, bool is_safepoint)
1966     : BlockEnd(illegalType, state_before, is_safepoint)
1967   , _x(x)
1968   , _cond(cond)
1969   , _y(y)
1970   , _profiled_method(NULL)
1971   , _profiled_bci(0)
1972   , _swapped(false)
1973   {
1974     ASSERT_VALUES
1975     set_flag(UnorderedIsTrueFlag, unordered_is_true);
1976     assert(x->type()->tag() == y->type()->tag(), "types must match");
1977     BlockList* s = new BlockList(2);
1978     s->append(tsux);
1979     s->append(fsux);
1980     set_sux(s);
1981   }
1982 
1983   // accessors
1984   Value x() const                                { return _x; }
1985   Condition cond() const                         { return _cond; }
1986   bool unordered_is_true() const                 { return check_flag(UnorderedIsTrueFlag); }
1987   Value y() const                                { return _y; }
1988   BlockBegin* sux_for(bool is_true) const        { return sux_at(is_true ? 0 : 1); }
1989   BlockBegin* tsux() const                       { return sux_for(true); }
1990   BlockBegin* fsux() const                       { return sux_for(false); }
1991   BlockBegin* usux() const                       { return sux_for(unordered_is_true()); }
1992   bool should_profile() const                    { return check_flag(ProfileMDOFlag); }
1993   ciMethod* profiled_method() const              { return _profiled_method; } // set only for profiled branches
1994   int profiled_bci() const                       { return _profiled_bci; }    // set for profiled branches and tiered
1995   bool is_swapped() const                        { return _swapped; }
1996 
1997   // manipulation
1998   void swap_operands() {
1999     Value t = _x; _x = _y; _y = t;
2000     _cond = mirror(_cond);
2001   }
2002 
2003   void swap_sux() {
2004     assert(number_of_sux() == 2, "wrong number of successors");
2005     BlockList* s = sux();
2006     BlockBegin* t = s->at(0); s->at_put(0, s->at(1)); s->at_put(1, t);
2007     _cond = negate(_cond);
2008     set_flag(UnorderedIsTrueFlag, !check_flag(UnorderedIsTrueFlag));
2009   }
2010 
2011   void set_should_profile(bool value)             { set_flag(ProfileMDOFlag, value); }
2012   void set_profiled_method(ciMethod* method)      { _profiled_method = method; }
2013   void set_profiled_bci(int bci)                  { _profiled_bci = bci;       }
2014   void set_swapped(bool value)                    { _swapped = value;         }
2015   // generic
2016   virtual void input_values_do(ValueVisitor* f)   { BlockEnd::input_values_do(f); f->visit(&_x); f->visit(&_y); }
2017 };
2018 
2019 
2020 BASE(Switch, BlockEnd)
2021  private:
2022   Value       _tag;
2023 
2024  public:
2025   // creation
2026   Switch(Value tag, BlockList* sux, ValueStack* state_before, bool is_safepoint)
2027   : BlockEnd(illegalType, state_before, is_safepoint)
2028   , _tag(tag) {
2029     ASSERT_VALUES
2030     set_sux(sux);
2031   }
2032 
2033   // accessors
2034   Value tag() const                              { return _tag; }
2035   int length() const                             { return number_of_sux() - 1; }
2036 
2037   virtual bool needs_exception_state() const     { return false; }
2038 
2039   // generic
2040   virtual void input_values_do(ValueVisitor* f)   { BlockEnd::input_values_do(f); f->visit(&_tag); }
2041 };
2042 
2043 
2044 LEAF(TableSwitch, Switch)
2045  private:
2046   int _lo_key;
2047 
2048  public:
2049   // creation
2050   TableSwitch(Value tag, BlockList* sux, int lo_key, ValueStack* state_before, bool is_safepoint)
2051     : Switch(tag, sux, state_before, is_safepoint)
2052   , _lo_key(lo_key) { assert(_lo_key <= hi_key(), "integer overflow"); }
2053 
2054   // accessors
2055   int lo_key() const                             { return _lo_key; }
2056   int hi_key() const                             { return _lo_key + (length() - 1); }
2057 };
2058 
2059 
2060 LEAF(LookupSwitch, Switch)
2061  private:
2062   intArray* _keys;
2063 
2064  public:
2065   // creation
2066   LookupSwitch(Value tag, BlockList* sux, intArray* keys, ValueStack* state_before, bool is_safepoint)
2067   : Switch(tag, sux, state_before, is_safepoint)
2068   , _keys(keys) {
2069     assert(keys != NULL, "keys must exist");
2070     assert(keys->length() == length(), "sux & keys have incompatible lengths");
2071   }
2072 
2073   // accessors
2074   int key_at(int i) const                        { return _keys->at(i); }
2075 };
2076 
2077 
2078 LEAF(Return, BlockEnd)
2079  private:
2080   Value _result;
2081 
2082  public:
2083   // creation
2084   Return(Value result) :
2085     BlockEnd(result == NULL ? voidType : result->type()->base(), NULL, true),
2086     _result(result) {}
2087 
2088   // accessors
2089   Value result() const                           { return _result; }
2090   bool has_result() const                        { return result() != NULL; }
2091 
2092   // generic
2093   virtual void input_values_do(ValueVisitor* f) {
2094     BlockEnd::input_values_do(f);
2095     if (has_result()) f->visit(&_result);
2096   }
2097 };
2098 
2099 
2100 LEAF(Throw, BlockEnd)
2101  private:
2102   Value _exception;
2103 
2104  public:
2105   // creation
2106   Throw(Value exception, ValueStack* state_before) : BlockEnd(illegalType, state_before, true), _exception(exception) {
2107     ASSERT_VALUES
2108   }
2109 
2110   // accessors
2111   Value exception() const                        { return _exception; }
2112 
2113   // generic
2114   virtual bool can_trap() const                  { return true; }
2115   virtual void input_values_do(ValueVisitor* f)   { BlockEnd::input_values_do(f); f->visit(&_exception); }
2116 };
2117 
2118 
2119 LEAF(Base, BlockEnd)
2120  public:
2121   // creation
2122   Base(BlockBegin* std_entry, BlockBegin* osr_entry) : BlockEnd(illegalType, NULL, false) {
2123     assert(std_entry->is_set(BlockBegin::std_entry_flag), "std entry must be flagged");
2124     assert(osr_entry == NULL || osr_entry->is_set(BlockBegin::osr_entry_flag), "osr entry must be flagged");
2125     BlockList* s = new BlockList(2);
2126     if (osr_entry != NULL) s->append(osr_entry);
2127     s->append(std_entry); // must be default sux!
2128     set_sux(s);
2129   }
2130 
2131   // accessors
2132   BlockBegin* std_entry() const                  { return default_sux(); }
2133   BlockBegin* osr_entry() const                  { return number_of_sux() < 2 ? NULL : sux_at(0); }
2134 };
2135 
2136 
2137 LEAF(OsrEntry, Instruction)
2138  public:
2139   // creation
2140 #ifdef _LP64
2141   OsrEntry() : Instruction(longType) { pin(); }
2142 #else
2143   OsrEntry() : Instruction(intType)  { pin(); }
2144 #endif
2145 
2146   // generic
2147   virtual void input_values_do(ValueVisitor* f)   { }
2148 };
2149 
2150 
2151 // Models the incoming exception at a catch site
2152 LEAF(ExceptionObject, Instruction)
2153  public:
2154   // creation
2155   ExceptionObject() : Instruction(objectType) {
2156     pin();
2157   }
2158 
2159   // generic
2160   virtual void input_values_do(ValueVisitor* f)   { }
2161 };
2162 
2163 
2164 // Models needed rounding for floating-point values on Intel.
2165 // Currently only used to represent rounding of double-precision
2166 // values stored into local variables, but could be used to model
2167 // intermediate rounding of single-precision values as well.
2168 LEAF(RoundFP, Instruction)
2169  private:
2170   Value _input;             // floating-point value to be rounded
2171 
2172  public:
2173   RoundFP(Value input)
2174   : Instruction(input->type()) // Note: should not be used for constants
2175   , _input(input)
2176   {
2177     ASSERT_VALUES
2178   }
2179 
2180   // accessors
2181   Value input() const                            { return _input; }
2182 
2183   // generic
2184   virtual void input_values_do(ValueVisitor* f)   { f->visit(&_input); }
2185 };
2186 
2187 
2188 BASE(UnsafeOp, Instruction)
2189  private:
2190   Value _object;                                 // Object to be fetched from or mutated
2191   Value _offset;                                 // Offset within object
2192   bool  _is_volatile;                            // true if volatile - dl/JSR166
2193   BasicType _basic_type;                         // ValueType can not express byte-sized integers
2194 
2195  protected:
2196   // creation
2197   UnsafeOp(BasicType basic_type, Value object, Value offset, bool is_put, bool is_volatile)
2198     : Instruction(is_put ? voidType : as_ValueType(basic_type)),
2199     _object(object), _offset(offset), _is_volatile(is_volatile), _basic_type(basic_type)
2200   {
2201     //Note:  Unsafe ops are not not guaranteed to throw NPE.
2202     // Convservatively, Unsafe operations must be pinned though we could be
2203     // looser about this if we wanted to..
2204     pin();
2205   }
2206 
2207  public:
2208   // accessors
2209   BasicType basic_type()                         { return _basic_type; }
2210   Value object()                                 { return _object; }
2211   Value offset()                                 { return _offset; }
2212   bool  is_volatile()                            { return _is_volatile; }
2213 
2214   // generic
2215   virtual void input_values_do(ValueVisitor* f)   { f->visit(&_object);
2216                                                     f->visit(&_offset); }
2217 };
2218 
2219 LEAF(UnsafeGet, UnsafeOp)
2220  private:
2221   bool _is_raw;
2222  public:
2223   UnsafeGet(BasicType basic_type, Value object, Value offset, bool is_volatile)
2224   : UnsafeOp(basic_type, object, offset, false, is_volatile)
2225   {
2226     ASSERT_VALUES
2227     _is_raw = false;
2228   }
2229   UnsafeGet(BasicType basic_type, Value object, Value offset, bool is_volatile, bool is_raw)
2230   : UnsafeOp(basic_type, object, offset, false, is_volatile), _is_raw(is_raw)
2231   {
2232     ASSERT_VALUES
2233   }
2234 
2235   // accessors
2236   bool is_raw()                             { return _is_raw; }
2237 };
2238 
2239 
2240 LEAF(UnsafePut, UnsafeOp)
2241  private:
2242   Value _value;                                  // Value to be stored
2243  public:
2244   UnsafePut(BasicType basic_type, Value object, Value offset, Value value, bool is_volatile)
2245   : UnsafeOp(basic_type, object, offset, true, is_volatile)
2246     , _value(value)
2247   {
2248     ASSERT_VALUES
2249   }
2250 
2251   // accessors
2252   Value value()                                  { return _value; }
2253 
2254   // generic
2255   virtual void input_values_do(ValueVisitor* f)   { UnsafeOp::input_values_do(f);
2256                                                    f->visit(&_value); }
2257 };
2258 
2259 LEAF(UnsafeGetAndSet, UnsafeOp)
2260  private:
2261   Value _value;                                  // Value to be stored
2262   bool  _is_add;
2263  public:
2264   UnsafeGetAndSet(BasicType basic_type, Value object, Value offset, Value value, bool is_add)
2265   : UnsafeOp(basic_type, object, offset, false, false)
2266     , _value(value)
2267     , _is_add(is_add)
2268   {
2269     ASSERT_VALUES
2270   }
2271 
2272   // accessors
2273   bool is_add() const                            { return _is_add; }
2274   Value value()                                  { return _value; }
2275 
2276   // generic
2277   virtual void input_values_do(ValueVisitor* f)   { UnsafeOp::input_values_do(f);
2278                                                    f->visit(&_value); }
2279 };
2280 
2281 LEAF(ProfileCall, Instruction)
2282  private:
2283   ciMethod*        _method;
2284   int              _bci_of_invoke;
2285   ciMethod*        _callee;         // the method that is called at the given bci
2286   Value            _recv;
2287   ciKlass*         _known_holder;
2288   Values*          _obj_args;       // arguments for type profiling
2289   ArgsNonNullState _nonnull_state;  // Do we know whether some arguments are never null?
2290   bool             _inlined;        // Are we profiling a call that is inlined
2291 
2292  public:
2293   ProfileCall(ciMethod* method, int bci, ciMethod* callee, Value recv, ciKlass* known_holder, Values* obj_args, bool inlined)
2294     : Instruction(voidType)
2295     , _method(method)
2296     , _bci_of_invoke(bci)
2297     , _callee(callee)
2298     , _recv(recv)
2299     , _known_holder(known_holder)
2300     , _obj_args(obj_args)
2301     , _inlined(inlined)
2302   {
2303     // The ProfileCall has side-effects and must occur precisely where located
2304     pin();
2305   }
2306 
2307   ciMethod* method()             const { return _method; }
2308   int bci_of_invoke()            const { return _bci_of_invoke; }
2309   ciMethod* callee()             const { return _callee; }
2310   Value recv()                   const { return _recv; }
2311   ciKlass* known_holder()        const { return _known_holder; }
2312   int nb_profiled_args()         const { return _obj_args == NULL ? 0 : _obj_args->length(); }
2313   Value profiled_arg_at(int i)   const { return _obj_args->at(i); }
2314   bool arg_needs_null_check(int i) const {
2315     return _nonnull_state.arg_needs_null_check(i);
2316   }
2317   bool inlined()                 const { return _inlined; }
2318 
2319   void set_arg_needs_null_check(int i, bool check) {
2320     _nonnull_state.set_arg_needs_null_check(i, check);
2321   }
2322 
2323   virtual void input_values_do(ValueVisitor* f)   {
2324     if (_recv != NULL) {
2325       f->visit(&_recv);
2326     }
2327     for (int i = 0; i < nb_profiled_args(); i++) {
2328       f->visit(_obj_args->adr_at(i));
2329     }
2330   }
2331 };
2332 
2333 LEAF(ProfileReturnType, Instruction)
2334  private:
2335   ciMethod*        _method;
2336   ciMethod*        _callee;
2337   int              _bci_of_invoke;
2338   Value            _ret;
2339 
2340  public:
2341   ProfileReturnType(ciMethod* method, int bci, ciMethod* callee, Value ret)
2342     : Instruction(voidType)
2343     , _method(method)
2344     , _callee(callee)
2345     , _bci_of_invoke(bci)
2346     , _ret(ret)
2347   {
2348     set_needs_null_check(true);
2349     // The ProfileType has side-effects and must occur precisely where located
2350     pin();
2351   }
2352 
2353   ciMethod* method()             const { return _method; }
2354   ciMethod* callee()             const { return _callee; }
2355   int bci_of_invoke()            const { return _bci_of_invoke; }
2356   Value ret()                    const { return _ret; }
2357 
2358   virtual void input_values_do(ValueVisitor* f)   {
2359     if (_ret != NULL) {
2360       f->visit(&_ret);
2361     }
2362   }
2363 };
2364 
2365 // Call some C runtime function that doesn't safepoint,
2366 // optionally passing the current thread as the first argument.
2367 LEAF(RuntimeCall, Instruction)
2368  private:
2369   const char* _entry_name;
2370   address     _entry;
2371   Values*     _args;
2372   bool        _pass_thread;  // Pass the JavaThread* as an implicit first argument
2373 
2374  public:
2375   RuntimeCall(ValueType* type, const char* entry_name, address entry, Values* args, bool pass_thread = true)
2376     : Instruction(type)
2377     , _entry_name(entry_name)
2378     , _entry(entry)
2379     , _args(args)
2380     , _pass_thread(pass_thread) {
2381     ASSERT_VALUES
2382     pin();
2383   }
2384 
2385   const char* entry_name() const  { return _entry_name; }
2386   address entry() const           { return _entry; }
2387   int number_of_arguments() const { return _args->length(); }
2388   Value argument_at(int i) const  { return _args->at(i); }
2389   bool pass_thread() const        { return _pass_thread; }
2390 
2391   virtual void input_values_do(ValueVisitor* f)   {
2392     for (int i = 0; i < _args->length(); i++) f->visit(_args->adr_at(i));
2393   }
2394 };
2395 
2396 // Use to trip invocation counter of an inlined method
2397 
2398 LEAF(ProfileInvoke, Instruction)
2399  private:
2400   ciMethod*   _inlinee;
2401   ValueStack* _state;
2402 
2403  public:
2404   ProfileInvoke(ciMethod* inlinee,  ValueStack* state)
2405     : Instruction(voidType)
2406     , _inlinee(inlinee)
2407     , _state(state)
2408   {
2409     // The ProfileInvoke has side-effects and must occur precisely where located QQQ???
2410     pin();
2411   }
2412 
2413   ciMethod* inlinee()      { return _inlinee; }
2414   ValueStack* state()      { return _state; }
2415   virtual void input_values_do(ValueVisitor*)   {}
2416   virtual void state_values_do(ValueVisitor*);
2417 };
2418 
2419 LEAF(MemBar, Instruction)
2420  private:
2421   LIR_Code _code;
2422 
2423  public:
2424   MemBar(LIR_Code code)
2425     : Instruction(voidType)
2426     , _code(code)
2427   {
2428     pin();
2429   }
2430 
2431   LIR_Code code()           { return _code; }
2432 
2433   virtual void input_values_do(ValueVisitor*)   {}
2434 };
2435 
2436 class BlockPair: public CompilationResourceObj {
2437  private:
2438   BlockBegin* _from;
2439   BlockBegin* _to;
2440  public:
2441   BlockPair(BlockBegin* from, BlockBegin* to): _from(from), _to(to) {}
2442   BlockBegin* from() const { return _from; }
2443   BlockBegin* to() const   { return _to;   }
2444   bool is_same(BlockBegin* from, BlockBegin* to) const { return  _from == from && _to == to; }
2445   bool is_same(BlockPair* p) const { return  _from == p->from() && _to == p->to(); }
2446   void set_to(BlockBegin* b)   { _to = b; }
2447   void set_from(BlockBegin* b) { _from = b; }
2448 };
2449 
2450 typedef GrowableArray<BlockPair*> BlockPairList;
2451 
2452 inline int         BlockBegin::number_of_sux() const            { assert(_end == NULL || _end->number_of_sux() == _successors.length(), "mismatch"); return _successors.length(); }
2453 inline BlockBegin* BlockBegin::sux_at(int i) const              { assert(_end == NULL || _end->sux_at(i) == _successors.at(i), "mismatch");          return _successors.at(i); }
2454 inline void        BlockBegin::add_successor(BlockBegin* sux)   { assert(_end == NULL, "Would create mismatch with successors of BlockEnd");         _successors.append(sux); }
2455 
2456 #undef ASSERT_VALUES
2457 
2458 #endif // SHARE_C1_C1_INSTRUCTION_HPP