/*

 * Copyright 1999-2006 Sun Microsystems, Inc.  All Rights Reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 *

 */

// Predefined classes

class ciField;

class ValueStack;

class InstructionPrinter;

class IRScope;

class LIR_OprDesc;

typedef LIR_OprDesc* LIR_Opr;

// Instruction class hierarchy

//

// All leaf classes in the class hierarchy are concrete classes

// (i.e., are instantiated). All other classes are abstract and

// serve factoring.

class Instruction;

class   HiWord;

class   Phi;

class   Local;

class   Constant;

class   AccessField;

class     LoadField;

class     StoreField;

class   AccessArray;

class     ArrayLength;

class     AccessIndexed;

class       LoadIndexed;

class       StoreIndexed;

class   NegateOp;

class   Op2;

class     ArithmeticOp;

class     ShiftOp;

class     LogicOp;

class     CompareOp;

class     IfOp;

class   Convert;

class   NullCheck;

class   OsrEntry;

class   ExceptionObject;

class   StateSplit;

class     Invoke;

class     NewInstance;

class     NewArray;

class       NewTypeArray;

class       NewObjectArray;

class       NewMultiArray;

class     TypeCheck;

class       CheckCast;

class       InstanceOf;

class     AccessMonitor;

class       MonitorEnter;

class       MonitorExit;

class     Intrinsic;

class     BlockBegin;

class     BlockEnd;

class       Goto;

class       If;

class       IfInstanceOf;

class       Switch;

class         TableSwitch;

class         LookupSwitch;

class       Return;

class       Throw;

class       Base;

class   RoundFP;

class   UnsafeOp;

class     UnsafeRawOp;

class       UnsafeGetRaw;

class       UnsafePutRaw;

class     UnsafeObjectOp;

class       UnsafeGetObject;

class       UnsafePutObject;

class       UnsafePrefetch;

class         UnsafePrefetchRead;

class         UnsafePrefetchWrite;

class   ProfileCall;

class   ProfileCounter;

// A Value is a reference to the instruction creating the value

typedef Instruction* Value;

define_array(ValueArray, Value)

define_stack(Values, ValueArray)

define_array(ValueStackArray, ValueStack*)

define_stack(ValueStackStack, ValueStackArray)

// BlockClosure is the base class for block traversal/iteration.

class BlockClosure: public CompilationResourceObj {

 public:

  virtual void block_do(BlockBegin* block)       = 0;

};

// Some array and list classes

define_array(BlockBeginArray, BlockBegin*)

define_stack(_BlockList, BlockBeginArray)

class BlockList: public _BlockList {

 public:

  BlockList(): _BlockList() {}

  BlockList(const int size): _BlockList(size) {}

  BlockList(const int size, BlockBegin* init): _BlockList(size, init) {}

  void iterate_forward(BlockClosure* closure);

  void iterate_backward(BlockClosure* closure);

  void blocks_do(void f(BlockBegin*));

  void values_do(void f(Value*));

  void print(bool cfg_only = false, bool live_only = false) PRODUCT_RETURN;

};

// InstructionVisitors provide type-based dispatch for instructions.

// For each concrete Instruction class X, a virtual function do_X is

// provided. Functionality that needs to be implemented for all classes

// (e.g., printing, code generation) is factored out into a specialised

// visitor instead of added to the Instruction classes itself.

class InstructionVisitor: public StackObj {

 public:

          void do_HiWord         (HiWord*          x) { ShouldNotReachHere(); }

  virtual void do_Phi            (Phi*             x) = 0;

  virtual void do_Local          (Local*           x) = 0;

  virtual void do_Constant       (Constant*        x) = 0;

  virtual void do_LoadField      (LoadField*       x) = 0;

  virtual void do_StoreField     (StoreField*      x) = 0;

  virtual void do_ArrayLength    (ArrayLength*     x) = 0;

  virtual void do_LoadIndexed    (LoadIndexed*     x) = 0;

  virtual void do_StoreIndexed   (StoreIndexed*    x) = 0;

  virtual void do_NegateOp       (NegateOp*        x) = 0;

  virtual void do_ArithmeticOp   (ArithmeticOp*    x) = 0;

  virtual void do_ShiftOp        (ShiftOp*         x) = 0;

  virtual void do_LogicOp        (LogicOp*         x) = 0;

  virtual void do_CompareOp      (CompareOp*       x) = 0;

  virtual void do_IfOp           (IfOp*            x) = 0;

  virtual void do_Convert        (Convert*         x) = 0;

  virtual void do_NullCheck      (NullCheck*       x) = 0;

  virtual void do_Invoke         (Invoke*          x) = 0;

  virtual void do_NewInstance    (NewInstance*     x) = 0;

  virtual void do_NewTypeArray   (NewTypeArray*    x) = 0;

  virtual void do_NewObjectArray (NewObjectArray*  x) = 0;

  virtual void do_NewMultiArray  (NewMultiArray*   x) = 0;

  virtual void do_CheckCast      (CheckCast*       x) = 0;

  virtual void do_InstanceOf     (InstanceOf*      x) = 0;

  virtual void do_MonitorEnter   (MonitorEnter*    x) = 0;

  virtual void do_MonitorExit    (MonitorExit*     x) = 0;

  virtual void do_Intrinsic      (Intrinsic*       x) = 0;

  virtual void do_BlockBegin     (BlockBegin*      x) = 0;

  virtual void do_Goto           (Goto*            x) = 0;

  virtual void do_If             (If*              x) = 0;

  virtual void do_IfInstanceOf   (IfInstanceOf*    x) = 0;

  virtual void do_TableSwitch    (TableSwitch*     x) = 0;

  virtual void do_LookupSwitch   (LookupSwitch*    x) = 0;

  virtual void do_Return         (Return*          x) = 0;

  virtual void do_Throw          (Throw*           x) = 0;

  virtual void do_Base           (Base*            x) = 0;

  virtual void do_OsrEntry       (OsrEntry*        x) = 0;

  virtual void do_ExceptionObject(ExceptionObject* x) = 0;

  virtual void do_RoundFP        (RoundFP*         x) = 0;

  virtual void do_UnsafeGetRaw   (UnsafeGetRaw*    x) = 0;

  virtual void do_UnsafePutRaw   (UnsafePutRaw*    x) = 0;

  virtual void do_UnsafeGetObject(UnsafeGetObject* x) = 0;

  virtual void do_UnsafePutObject(UnsafePutObject* x) = 0;

  virtual void do_UnsafePrefetchRead (UnsafePrefetchRead*  x) = 0;

  virtual void do_UnsafePrefetchWrite(UnsafePrefetchWrite* x) = 0;

  virtual void do_ProfileCall    (ProfileCall*     x) = 0;

  virtual void do_ProfileCounter (ProfileCounter*  x) = 0;

};

// Hashing support

//

// Note: This hash functions affect the performance

//       of ValueMap - make changes carefully!

#define HASH1(x1            )                    ((intx)(x1))

#define HASH2(x1, x2        )                    ((HASH1(x1        ) << 7) ^ HASH1(x2))

#define HASH3(x1, x2, x3    )                    ((HASH2(x1, x2    ) << 7) ^ HASH1(x3))

#define HASH4(x1, x2, x3, x4)                    ((HASH3(x1, x2, x3) << 7) ^ HASH1(x4))

// The following macros are used to implement instruction-specific hashing.

// By default, each instruction implements hash() and is_equal(Value), used

// for value numbering/common subexpression elimination. The default imple-

// mentation disables value numbering. Each instruction which can be value-

// numbered, should define corresponding hash() and is_equal(Value) functions

// via the macros below. The f arguments specify all the values/op codes, etc.

// that need to be identical for two instructions to be identical.

//

// Note: The default implementation of hash() returns 0 in order to indicate

//       that the instruction should not be considered for value numbering.

//       The currently used hash functions do not guarantee that never a 0

//       is produced. While this is still correct, it may be a performance

//       bug (no value numbering for that node). However, this situation is

//       so unlikely, that we are not going to handle it specially.

#define HASHING1(class_name, enabled, f1)             \

  virtual intx hash() const {                         \

    return (enabled) ? HASH2(name(), f1) : 0;         \

  }                                                   \

  virtual bool is_equal(Value v) const {              \

    if (!(enabled)  ) return false;                   \

    class_name* _v = v->as_##class_name();            \

    if (_v == NULL  ) return false;                   \

    if (f1 != _v->f1) return false;                   \

    return true;                                      \

  }                                                   \

#define HASHING2(class_name, enabled, f1, f2)         \

  virtual intx hash() const {                         \

    return (enabled) ? HASH3(name(), f1, f2) : 0;     \

  }                                                   \

  virtual bool is_equal(Value v) const {              \

    if (!(enabled)  ) return false;                   \

    class_name* _v = v->as_##class_name();            \

    if (_v == NULL  ) return false;                   \

    if (f1 != _v->f1) return false;                   \

    if (f2 != _v->f2) return false;                   \

    return true;                                      \

  }                                                   \

#define HASHING3(class_name, enabled, f1, f2, f3)     \

  virtual intx hash() const {                          \

    return (enabled) ? HASH4(name(), f1, f2, f3) : 0; \

  }                                                   \

  virtual bool is_equal(Value v) const {              \

    if (!(enabled)  ) return false;                   \

    class_name* _v = v->as_##class_name();            \

    if (_v == NULL  ) return false;                   \

    if (f1 != _v->f1) return false;                   \

    if (f2 != _v->f2) return false;                   \

    if (f3 != _v->f3) return false;                   \

    return true;                                      \

  }                                                   \

// The mother of all instructions...

class Instruction: public CompilationResourceObj {

 private:

  static int   _next_id;                         // the node counter

  int          _id;                              // the unique instruction id

  int          _bci;                             // the instruction bci

  int          _use_count;                       // the number of instructions refering to this value (w/o prev/next); only roots can have use count = 0 or > 1

  int          _pin_state;                       // set of PinReason describing the reason for pinning

  ValueType*   _type;                            // the instruction value type

  Instruction* _next;                            // the next instruction if any (NULL for BlockEnd instructions)

  Instruction* _subst;                           // the substitution instruction if any

  LIR_Opr      _operand;                         // LIR specific information

  unsigned int _flags;                           // Flag bits

  XHandlers*   _exception_handlers;              // Flat list of exception handlers covering this instruction

#ifdef ASSERT

  HiWord*      _hi_word;

#endif

  friend class UseCountComputer;

 protected:

  void set_bci(int bci)                          { assert(bci == SynchronizationEntryBCI || bci >= 0, "illegal bci"); _bci = bci; }

  void set_type(ValueType* type) {

    assert(type != NULL, "type must exist");

    _type = type;

  }

 public:

  enum InstructionFlag {

    NeedsNullCheckFlag = 0,

    CanTrapFlag,

    DirectCompareFlag,

    IsEliminatedFlag,

    IsInitializedFlag,

    IsLoadedFlag,

    IsSafepointFlag,

    IsStaticFlag,

    IsStrictfpFlag,

    NeedsStoreCheckFlag,

    NeedsWriteBarrierFlag,

    PreservesStateFlag,

    TargetIsFinalFlag,

    TargetIsLoadedFlag,

    TargetIsStrictfpFlag,

    UnorderedIsTrueFlag,

    NeedsPatchingFlag,

    ThrowIncompatibleClassChangeErrorFlag,

    ProfileMDOFlag,

    InstructionLastFlag

  };

 public:

  bool check_flag(InstructionFlag id) const      { return (_flags & (1 << id)) != 0;    }

  void set_flag(InstructionFlag id, bool f)      { _flags = f ? (_flags | (1 << id)) : (_flags & ~(1 << id)); };

  // 'globally' used condition values

  enum Condition {

    eql, neq, lss, leq, gtr, geq

  };

  // Instructions may be pinned for many reasons and under certain conditions

  // with enough knowledge it's possible to safely unpin them.

  enum PinReason {

      PinUnknown           = 1 << 0

    , PinExplicitNullCheck = 1 << 3

    , PinStackForStateSplit= 1 << 12

    , PinStateSplitConstructor= 1 << 13

    , PinGlobalValueNumbering= 1 << 14

  };

  static Condition mirror(Condition cond);

  static Condition negate(Condition cond);

  // initialization

  static void initialize()                       { _next_id = 0; }

  static int number_of_instructions()            { return _next_id; }

  // creation

  Instruction(ValueType* type, bool type_is_constant = false, bool create_hi = true)

  : _id(_next_id++)

  , _bci(-99)

  , _use_count(0)

  , _pin_state(0)

  , _type(type)

  , _next(NULL)

  , _subst(NULL)

  , _flags(0)

  , _operand(LIR_OprFact::illegalOpr)

  , _exception_handlers(NULL)

#ifdef ASSERT

  , _hi_word(NULL)

#endif

  {

    assert(type != NULL && (!type->is_constant() || type_is_constant), "type must exist");

#ifdef ASSERT

    if (create_hi && type->is_double_word()) {

      create_hi_word();

    }

#endif

  }

  // accessors

  int id() const                                 { return _id; }

  int bci() const                                { return _bci; }

  int use_count() const                          { return _use_count; }

  int pin_state() const                          { return _pin_state; }

  bool is_pinned() const                         { return _pin_state != 0 || PinAllInstructions; }

  ValueType* type() const                        { return _type; }

  Instruction* prev(BlockBegin* block);          // use carefully, expensive operation

  Instruction* next() const                      { return _next; }

  bool has_subst() const                         { return _subst != NULL; }

  Instruction* subst()                           { return _subst == NULL ? this : _subst->subst(); }

  LIR_Opr operand() const                        { return _operand; }

  void set_needs_null_check(bool f)              { set_flag(NeedsNullCheckFlag, f); }

  bool needs_null_check() const                  { return check_flag(NeedsNullCheckFlag); }

  bool has_uses() const                          { return use_count() > 0; }

  bool is_root() const                           { return is_pinned() || use_count() > 1; }

  XHandlers* exception_handlers() const          { return _exception_handlers; }

  // manipulation

  void pin(PinReason reason)                     { _pin_state |= reason; }

  void pin()                                     { _pin_state |= PinUnknown; }

  // DANGEROUS: only used by EliminateStores

  void unpin(PinReason reason)                   { assert((reason & PinUnknown) == 0, "can't unpin unknown state"); _pin_state &= ~reason; }

  virtual void set_lock_stack(ValueStack* l)     { /* do nothing*/ }

  virtual ValueStack* lock_stack() const         { return NULL; }

  Instruction* set_next(Instruction* next, int bci) {

    if (next != NULL) {

      assert(as_BlockEnd() == NULL, "BlockEnd instructions must have no next");

      assert(next->as_Phi() == NULL && next->as_Local() == NULL, "shouldn't link these instructions into list");

      next->set_bci(bci);

    }

    _next = next;

    return next;

  }

  void set_subst(Instruction* subst)             {

    assert(subst == NULL ||

           type()->base() == subst->type()->base() ||

           subst->type()->base() == illegalType, "type can't change");

    _subst = subst;

  }

  void set_exception_handlers(XHandlers *xhandlers) { _exception_handlers = xhandlers; }

#ifdef ASSERT

  // HiWord is used for debugging and is allocated early to avoid

  // allocation at inconvenient points

  HiWord* hi_word() { return _hi_word; }

  void create_hi_word();

#endif

  // machine-specifics

  void set_operand(LIR_Opr operand)              { assert(operand != LIR_OprFact::illegalOpr, "operand must exist"); _operand = operand; }

  void clear_operand()                           { _operand = LIR_OprFact::illegalOpr; }

  // generic

  virtual Instruction*      as_Instruction()     { return this; } // to satisfy HASHING1 macro

  virtual HiWord*           as_HiWord()          { return NULL; }

  virtual Phi*           as_Phi()          { return NULL; }

  virtual Local*            as_Local()           { return NULL; }

  virtual Constant*         as_Constant()        { return NULL; }

  virtual AccessField*      as_AccessField()     { return NULL; }

  virtual LoadField*        as_LoadField()       { return NULL; }

  virtual StoreField*       as_StoreField()      { return NULL; }

  virtual AccessArray*      as_AccessArray()     { return NULL; }

  virtual ArrayLength*      as_ArrayLength()     { return NULL; }

  virtual AccessIndexed*    as_AccessIndexed()   { return NULL; }

  virtual LoadIndexed*      as_LoadIndexed()     { return NULL; }

  virtual StoreIndexed*     as_StoreIndexed()    { return NULL; }

  virtual NegateOp*         as_NegateOp()        { return NULL; }

  virtual Op2*              as_Op2()             { return NULL; }

  virtual ArithmeticOp*     as_ArithmeticOp()    { return NULL; }

  virtual ShiftOp*          as_ShiftOp()         { return NULL; }

  virtual LogicOp*          as_LogicOp()         { return NULL; }

  virtual CompareOp*        as_CompareOp()       { return NULL; }

  virtual IfOp*             as_IfOp()            { return NULL; }

  virtual Convert*          as_Convert()         { return NULL; }

  virtual NullCheck*        as_NullCheck()       { return NULL; }

  virtual OsrEntry*         as_OsrEntry()        { return NULL; }

  virtual StateSplit*       as_StateSplit()      { return NULL; }

  virtual Invoke*           as_Invoke()          { return NULL; }

  virtual NewInstance*      as_NewInstance()     { return NULL; }

  virtual NewArray*         as_NewArray()        { return NULL; }

  virtual NewTypeArray*     as_NewTypeArray()    { return NULL; }

  virtual NewObjectArray*   as_NewObjectArray()  { return NULL; }

  virtual NewMultiArray*    as_NewMultiArray()   { return NULL; }

  virtual TypeCheck*        as_TypeCheck()       { return NULL; }

  virtual CheckCast*        as_CheckCast()       { return NULL; }

  virtual InstanceOf*       as_InstanceOf()      { return NULL; }

  virtual AccessMonitor*    as_AccessMonitor()   { return NULL; }

  virtual MonitorEnter*     as_MonitorEnter()    { return NULL; }

  virtual MonitorExit*      as_MonitorExit()     { return NULL; }

  virtual Intrinsic*        as_Intrinsic()       { return NULL; }

  virtual BlockBegin*       as_BlockBegin()      { return NULL; }

  virtual BlockEnd*         as_BlockEnd()        { return NULL; }

  virtual Goto*             as_Goto()            { return NULL; }

  virtual If*               as_If()              { return NULL; }

  virtual IfInstanceOf*     as_IfInstanceOf()    { return NULL; }

  virtual TableSwitch*      as_TableSwitch()     { return NULL; }

  virtual LookupSwitch*     as_LookupSwitch()    { return NULL; }

  virtual Return*           as_Return()          { return NULL; }

  virtual Throw*            as_Throw()           { return NULL; }

  virtual Base*             as_Base()            { return NULL; }

  virtual RoundFP*          as_RoundFP()         { return NULL; }

  virtual ExceptionObject*  as_ExceptionObject() { return NULL; }

  virtual UnsafeOp*         as_UnsafeOp()        { return NULL; }

  virtual void visit(InstructionVisitor* v)      = 0;

  virtual bool can_trap() const                  { return false; }

  virtual void input_values_do(void f(Value*))   = 0;

  virtual void state_values_do(void f(Value*))   { /* usually no state - override on demand */ }

  virtual void other_values_do(void f(Value*))   { /* usually no other - override on demand */ }

          void       values_do(void f(Value*))   { input_values_do(f); state_values_do(f); other_values_do(f); }

  virtual ciType* exact_type() const             { return NULL; }

  virtual ciType* declared_type() const          { return NULL; }

  // hashing

  virtual const char* name() const               = 0;

  HASHING1(Instruction, false, id())             // hashing disabled by default

  // debugging

  void print()                                   PRODUCT_RETURN;

  void print_line()                              PRODUCT_RETURN;

  void print(InstructionPrinter& ip)             PRODUCT_RETURN;

};

// The following macros are used to define base (i.e., non-leaf)

// and leaf instruction classes. They define class-name related

// generic functionality in one place.

#define BASE(class_name, super_class_name)       \

  class class_name: public super_class_name {    \

   public:                                       \

    virtual class_name* as_##class_name()        { return this; }              \

#define LEAF(class_name, super_class_name)       \

  BASE(class_name, super_class_name)             \

   public:                                       \

    virtual const char* name() const             { return #class_name; }       \

    virtual void visit(InstructionVisitor* v)    { v->do_##class_name(this); } \

// Debugging support

#ifdef ASSERT

  static void assert_value(Value* x)             { assert((*x) != NULL, "value must exist"); }

  #define ASSERT_VALUES                          values_do(assert_value);

#else

  #define ASSERT_VALUES

#endif // ASSERT

// A HiWord occupies the 'high word' of a 2-word