/*

 * Copyright (c) 1999, 2016, Oracle and/or its affiliates. All rights reserved.

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

 *

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

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

 * published by the Free Software Foundation.

 *

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

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

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

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

 * accompanied this code).

 *

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

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

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

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 *

 */

#ifndef SHARE_VM_C1_C1_INSTRUCTION_HPP

#define SHARE_VM_C1_C1_INSTRUCTION_HPP

#include "c1/c1_Compilation.hpp"

#include "c1/c1_LIR.hpp"

#include "c1/c1_ValueType.hpp"

#include "ci/ciField.hpp"

// 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   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   TypeCast;

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         UnsafeGetAndSetObject;

class   ProfileCall;

class   ProfileReturnType;

class   ProfileInvoke;

class   RuntimeCall;

class   MemBar;

class   RangeCheckPredicate;

#ifdef ASSERT

class   Assert;

#endif

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

typedef Instruction* Value;

typedef GrowableArray<Value> Values;

typedef GrowableArray<ValueStack*> ValueStackStack;

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

class BlockClosure: public CompilationResourceObj {

 public:

  virtual void block_do(BlockBegin* block)       = 0;

};

// A simple closure class for visiting the values of an Instruction

class ValueVisitor: public StackObj {

 public:

  virtual void visit(Value* v) = 0;

};

// Some array and list classes

typedef GrowableArray<BlockBegin*> BlockBeginArray;

class BlockList: public GrowableArray<BlockBegin*> {

 public:

  BlockList(): GrowableArray<BlockBegin*>() {}

  BlockList(const int size): GrowableArray<BlockBegin*>(size) {}

  BlockList(const int size, BlockBegin* init): GrowableArray<BlockBegin*>(size, size, init) {}

  void iterate_forward(BlockClosure* closure);

  void iterate_backward(BlockClosure* closure);

  void blocks_do(void f(BlockBegin*));

  void values_do(ValueVisitor* f);

  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:

  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_TypeCast       (TypeCast*        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_UnsafeGetAndSetObject(UnsafeGetAndSetObject* x) = 0;

  virtual void do_ProfileCall    (ProfileCall*     x) = 0;

  virtual void do_ProfileReturnType (ProfileReturnType*  x) = 0;

  virtual void do_ProfileInvoke  (ProfileInvoke*   x) = 0;

  virtual void do_RuntimeCall    (RuntimeCall*     x) = 0;

  virtual void do_MemBar         (MemBar*          x) = 0;

  virtual void do_RangeCheckPredicate(RangeCheckPredicate* x) = 0;

#ifdef ASSERT

  virtual void do_Assert         (Assert*          x) = 0;

#endif

};

// Hashing support

//

// 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:

  int          _id;                              // the unique instruction id

#ifndef PRODUCT

  int          _printable_bci;                   // the bci of the instruction for printing

#endif

  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

  ValueStack*  _state_before;                    // Copy of state with input operands still on stack (or NULL)

  ValueStack*  _exception_state;                 // Copy of state for exception handling

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

  friend class UseCountComputer;

  friend class BlockBegin;

  void update_exception_state(ValueStack* state);

 protected:

  BlockBegin*  _block;                           // Block that contains this instruction

  void set_type(ValueType* type) {

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

    _type = type;

  }

  // Helper class to keep track of which arguments need a null check

  class ArgsNonNullState {

  private:

    int _nonnull_state; // mask identifying which args are nonnull

  public:

    ArgsNonNullState()

      : _nonnull_state(AllBits) {}

    // Does argument number i needs a null check?

    bool arg_needs_null_check(int i) const {

      // No data is kept for arguments starting at position 33 so

      // conservatively assume that they need a null check.

      if (i >= 0 && i < (int)sizeof(_nonnull_state) * BitsPerByte) {

        return is_set_nth_bit(_nonnull_state, i);

      }

      return true;

    }

    // Set whether argument number i needs a null check or not

    void set_arg_needs_null_check(int i, bool check) {

      if (i >= 0 && i < (int)sizeof(_nonnull_state) * BitsPerByte) {

        if (check) {

          _nonnull_state |= nth_bit(i);

        } else {

          _nonnull_state &= ~(nth_bit(i));

        }

      }

    }

  };

 public:

  void* operator new(size_t size) throw() {

    Compilation* c = Compilation::current();

    void* res = c->arena()->Amalloc(size);

    ((Instruction*)res)->_id = c->get_next_id();

    return res;

  }

  static const int no_bci = -99;

  enum InstructionFlag {

    NeedsNullCheckFlag = 0,

    CanTrapFlag,

    DirectCompareFlag,

    IsEliminatedFlag,

    IsSafepointFlag,

    IsStaticFlag,

    IsStrictfpFlag,

    NeedsStoreCheckFlag,

    NeedsWriteBarrierFlag,

    PreservesStateFlag,

    TargetIsFinalFlag,

    TargetIsLoadedFlag,

    TargetIsStrictfpFlag,

    UnorderedIsTrueFlag,

    NeedsPatchingFlag,

    ThrowIncompatibleClassChangeErrorFlag,

    ProfileMDOFlag,

    IsLinkedInBlockFlag,

    NeedsRangeCheckFlag,

    InWorkListFlag,

    DeoptimizeOnException,

    InstructionLastFlag

  };

 public:

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

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

  // 'globally' used condition values

  enum Condition {

    eql, neq, lss, leq, gtr, geq, aeq, beq

  };

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

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

  enum PinReason {

      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 int number_of_instructions() {

    return Compilation::current()->number_of_instructions();

  }

  // creation

  Instruction(ValueType* type, ValueStack* state_before = NULL, bool type_is_constant = false)

  : _use_count(0)

#ifndef PRODUCT

  , _printable_bci(-99)

#endif

  , _pin_state(0)

  , _type(type)

  , _next(NULL)

  , _block(NULL)

  , _subst(NULL)

  , _flags(0)

  , _operand(LIR_OprFact::illegalOpr)

  , _state_before(state_before)

  , _exception_handlers(NULL)

  {

    check_state(state_before);

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

    update_exception_state(_state_before);

  }

  // accessors

  int id() const                                 { return _id; }

#ifndef PRODUCT

  bool has_printable_bci() const                 { return _printable_bci != -99; }

  int printable_bci() const                      { assert(has_printable_bci(), "_printable_bci should have been set"); return _printable_bci; }

  void set_printable_bci(int bci)                { _printable_bci = bci; }

#endif

  int dominator_depth();

  int use_count() const                          { return _use_count; }

  int pin_state() const                          { return _pin_state; }

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

  ValueType* type() const                        { return _type; }

  BlockBegin *block() const                      { return _block; }

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

  Instruction* next() const                      { return _next; }

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

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

  LIR_Opr operand() const                        { return _operand; }

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

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

  bool is_linked() const                         { return check_flag(IsLinkedInBlockFlag); }

  bool can_be_linked()                           { return as_Local() == NULL && as_Phi() == NULL; }

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

  ValueStack* state_before() const               { return _state_before; }

  ValueStack* exception_state() const            { return _exception_state; }

  virtual bool needs_exception_state() const     { return true; }

  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; }

  Instruction* set_next(Instruction* next) {

    assert(next->has_printable_bci(), "_printable_bci should have been set");

    assert(next != NULL, "must not be NULL");

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

    assert(next->can_be_linked(), "shouldn't link these instructions into list");

    BlockBegin *block = this->block();

    next->_block = block;

    next->set_flag(Instruction::IsLinkedInBlockFlag, true);

    _next = next;

    return next;

  }

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

#ifndef PRODUCT

    next->set_printable_bci(bci);

#endif

    return set_next(next);

  }

  // when blocks are merged

  void fixup_block_pointers() {

    Instruction *cur = next()->next(); // next()'s block is set in set_next

    while (cur && cur->_block != block()) {

      cur->_block = block();

      cur = cur->next();

    }

  }

  Instruction *insert_after(Instruction *i) {

    Instruction* n = _next;

    set_next(i);

    i->set_next(n);

    return _next;

  }

  Instruction *insert_after_same_bci(Instruction *i) {

#ifndef PRODUCT

    i->set_printable_bci(printable_bci());

#endif

    return insert_after(i);

  }

  void set_subst(Instruction* subst)             {