CSE2410 Fall 2014 Bounce

// Copyright 2012 the V8 project authors. All rights reserved.

// Redistribution and use in source and binary forms, with or without

// modification, are permitted provided that the following conditions are

// met:

//

//     * Redistributions of source code must retain the above copyright

//       notice, this list of conditions and the following disclaimer.

//     * Redistributions in binary form must reproduce the above

//       copyright notice, this list of conditions and the following

//       disclaimer in the documentation and/or other materials provided

//       with the distribution.

//     * Neither the name of Google Inc. nor the names of its

//       contributors may be used to endorse or promote products derived

//       from this software without specific prior written permission.

//

// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#ifndef V8_HYDROGEN_INSTRUCTIONS_H_

#define V8_HYDROGEN_INSTRUCTIONS_H_

#include "v8.h"

#include "allocation.h"

#include "code-stubs.h"

#include "data-flow.h"

#include "deoptimizer.h"

#include "small-pointer-list.h"

#include "string-stream.h"

#include "unique.h"

#include "v8conversions.h"

#include "v8utils.h"

#include "zone.h"

namespace v8 {

namespace internal {

// Forward declarations.

class HBasicBlock;

class HEnvironment;

class HInferRepresentationPhase;

class HInstruction;

class HLoopInformation;

class HStoreNamedField;

class HValue;

class LInstruction;

class LChunkBuilder;

#define HYDROGEN_ABSTRACT_INSTRUCTION_LIST(V)  \

  V(ArithmeticBinaryOperation)                 \

  V(BinaryOperation)                           \

  V(BitwiseBinaryOperation)                    \

  V(ControlInstruction)                        \

  V(Instruction)                               \

#define HYDROGEN_CONCRETE_INSTRUCTION_LIST(V)  \

  V(AbnormalExit)                              \

  V(AccessArgumentsAt)                         \

  V(Add)                                       \

  V(Allocate)                                  \

  V(ApplyArguments)                            \

  V(ArgumentsElements)                         \

  V(ArgumentsLength)                           \

  V(ArgumentsObject)                           \

  V(Bitwise)                                   \

  V(BlockEntry)                                \

  V(BoundsCheck)                               \

  V(BoundsCheckBaseIndexInformation)           \

  V(Branch)                                    \

  V(CallConstantFunction)                      \

  V(CallFunction)                              \

  V(CallGlobal)                                \

  V(CallKeyed)                                 \

  V(CallKnownGlobal)                           \

  V(CallNamed)                                 \

  V(CallNew)                                   \

  V(CallNewArray)                              \

  V(CallRuntime)                               \

  V(CallStub)                                  \

  V(CapturedObject)                            \

  V(Change)                                    \

  V(CheckHeapObject)                           \

  V(CheckInstanceType)                         \

  V(CheckMaps)                                 \

  V(CheckMapValue)                             \

  V(CheckSmi)                                  \

  V(CheckValue)                                \

  V(ClampToUint8)                              \

  V(ClassOfTestAndBranch)                      \

  V(CompareNumericAndBranch)                   \

  V(CompareHoleAndBranch)                      \

  V(CompareGeneric)                            \

  V(CompareObjectEqAndBranch)                  \

  V(CompareMap)                                \

  V(Constant)                                  \

  V(Context)                                   \

  V(DateField)                                 \

  V(DebugBreak)                                \

  V(DeclareGlobals)                            \

  V(Deoptimize)                                \

  V(Div)                                       \

  V(DummyUse)                                  \

  V(ElementsKind)                              \

  V(EnterInlined)                              \

  V(EnvironmentMarker)                         \

  V(ForceRepresentation)                       \

  V(ForInCacheArray)                           \

  V(ForInPrepareMap)                           \

  V(FunctionLiteral)                           \

  V(GetCachedArrayIndex)                       \

  V(GlobalObject)                              \

  V(GlobalReceiver)                            \

  V(Goto)                                      \

  V(HasCachedArrayIndexAndBranch)              \

  V(HasInstanceTypeAndBranch)                  \

  V(InnerAllocatedObject)                      \

  V(InstanceOf)                                \

  V(InstanceOfKnownGlobal)                     \

  V(InvokeFunction)                            \

  V(IsConstructCallAndBranch)                  \

  V(IsObjectAndBranch)                         \

  V(IsStringAndBranch)                         \

  V(IsSmiAndBranch)                            \

  V(IsUndetectableAndBranch)                   \

  V(LeaveInlined)                              \

  V(LoadContextSlot)                           \

  V(LoadExternalArrayPointer)                  \

  V(LoadFieldByIndex)                          \

  V(LoadFunctionPrototype)                     \

  V(LoadGlobalCell)                            \

  V(LoadGlobalGeneric)                         \

  V(LoadKeyed)                                 \

  V(LoadKeyedGeneric)                          \

  V(LoadNamedField)                            \

  V(LoadNamedGeneric)                          \

  V(LoadRoot)                                  \

  V(MapEnumLength)                             \

  V(MathFloorOfDiv)                            \

  V(MathMinMax)                                \

  V(Mod)                                       \

  V(Mul)                                       \

  V(OsrEntry)                                  \

  V(OuterContext)                              \

  V(Parameter)                                 \

  V(Power)                                     \

  V(PushArgument)                              \

  V(Random)                                    \

  V(RegExpLiteral)                             \

  V(Return)                                    \

  V(Ror)                                       \

  V(Sar)                                       \

  V(SeqStringSetChar)                          \

  V(Shl)                                       \

  V(Shr)                                       \

  V(Simulate)                                  \

  V(StackCheck)                                \

  V(StoreCodeEntry)                            \

  V(StoreContextSlot)                          \

  V(StoreGlobalCell)                           \

  V(StoreGlobalGeneric)                        \

  V(StoreKeyed)                                \

  V(StoreKeyedGeneric)                         \

  V(StoreNamedField)                           \

  V(StoreNamedGeneric)                         \

  V(StringAdd)                                 \

  V(StringCharCodeAt)                          \

  V(StringCharFromCode)                        \

  V(StringCompareAndBranch)                    \

  V(Sub)                                       \

  V(ThisFunction)                              \

  V(Throw)                                     \

  V(ToFastProperties)                          \

  V(TransitionElementsKind)                    \

  V(TrapAllocationMemento)                     \

  V(Typeof)                                    \

  V(TypeofIsAndBranch)                         \

  V(UnaryMathOperation)                        \

  V(UnknownOSRValue)                           \

  V(UseConst)                                  \

  V(ValueOf)                                   \

  V(WrapReceiver)

#define GVN_TRACKED_FLAG_LIST(V)               \

  V(Maps)                                      \

  V(NewSpacePromotion)

#define GVN_UNTRACKED_FLAG_LIST(V)             \

  V(ArrayElements)                             \

  V(ArrayLengths)                              \

  V(StringLengths)                             \

  V(BackingStoreFields)                        \

  V(Calls)                                     \

  V(ContextSlots)                              \

  V(DoubleArrayElements)                       \

  V(DoubleFields)                              \

  V(ElementsKind)                              \

  V(ElementsPointer)                           \

  V(GlobalVars)                                \

  V(InobjectFields)                            \

  V(OsrEntries)                                \

  V(ExternalMemory)

#define DECLARE_ABSTRACT_INSTRUCTION(type)                              \

  virtual bool Is##type() const V8_FINAL V8_OVERRIDE { return true; }   \

  static H##type* cast(HValue* value) {                                 \

    ASSERT(value->Is##type());                                          \

    return reinterpret_cast<H##type*>(value);                           \

  }

#define DECLARE_CONCRETE_INSTRUCTION(type)              \

  virtual LInstruction* CompileToLithium(               \

     LChunkBuilder* builder) V8_FINAL V8_OVERRIDE;      \

  static H##type* cast(HValue* value) {                 \

    ASSERT(value->Is##type());                          \

    return reinterpret_cast<H##type*>(value);           \

  }                                                     \

  virtual Opcode opcode() const V8_FINAL V8_OVERRIDE {  \

    return HValue::k##type;                             \

  }

class Range V8_FINAL : public ZoneObject {

 public:

  Range()

      : lower_(kMinInt),

        upper_(kMaxInt),

        next_(NULL),

        can_be_minus_zero_(false) { }

  Range(int32_t lower, int32_t upper)

      : lower_(lower),

        upper_(upper),

        next_(NULL),

        can_be_minus_zero_(false) { }

  int32_t upper() const { return upper_; }

  int32_t lower() const { return lower_; }

  Range* next() const { return next_; }

  Range* CopyClearLower(Zone* zone) const {

    return new(zone) Range(kMinInt, upper_);

  }

  Range* CopyClearUpper(Zone* zone) const {

    return new(zone) Range(lower_, kMaxInt);

  }

  Range* Copy(Zone* zone) const {

    Range* result = new(zone) Range(lower_, upper_);

    result->set_can_be_minus_zero(CanBeMinusZero());

    return result;

  }

  int32_t Mask() const;

  void set_can_be_minus_zero(bool b) { can_be_minus_zero_ = b; }

  bool CanBeMinusZero() const { return CanBeZero() && can_be_minus_zero_; }

  bool CanBeZero() const { return upper_ >= 0 && lower_ <= 0; }

  bool CanBeNegative() const { return lower_ < 0; }

  bool CanBePositive() const { return upper_ > 0; }

  bool Includes(int value) const { return lower_ <= value && upper_ >= value; }

  bool IsMostGeneric() const {

    return lower_ == kMinInt && upper_ == kMaxInt && CanBeMinusZero();

  }

  bool IsInSmiRange() const {

    return lower_ >= Smi::kMinValue && upper_ <= Smi::kMaxValue;

  }

  void ClampToSmi() {

    lower_ = Max(lower_, Smi::kMinValue);

    upper_ = Min(upper_, Smi::kMaxValue);

  }

  void KeepOrder();

#ifdef DEBUG

  void Verify() const;

#endif

  void StackUpon(Range* other) {

    Intersect(other);

    next_ = other;

  }

  void Intersect(Range* other);

  void Union(Range* other);

  void CombinedMax(Range* other);

  void CombinedMin(Range* other);

  void AddConstant(int32_t value);

  void Sar(int32_t value);

  void Shl(int32_t value);

  bool AddAndCheckOverflow(const Representation& r, Range* other);

  bool SubAndCheckOverflow(const Representation& r, Range* other);

  bool MulAndCheckOverflow(const Representation& r, Range* other);

 private:

  int32_t lower_;

  int32_t upper_;

  Range* next_;

  bool can_be_minus_zero_;

};

class HType V8_FINAL {

 public:

  static HType None() { return HType(kNone); }

  static HType Tagged() { return HType(kTagged); }

  static HType TaggedPrimitive() { return HType(kTaggedPrimitive); }

  static HType TaggedNumber() { return HType(kTaggedNumber); }

  static HType Smi() { return HType(kSmi); }

  static HType HeapNumber() { return HType(kHeapNumber); }

  static HType String() { return HType(kString); }

  static HType Boolean() { return HType(kBoolean); }

  static HType NonPrimitive() { return HType(kNonPrimitive); }

  static HType JSArray() { return HType(kJSArray); }

  static HType JSObject() { return HType(kJSObject); }

  // Return the weakest (least precise) common type.

  HType Combine(HType other) {

    return HType(static_cast<Type>(type_ & other.type_));

  }

  bool Equals(const HType& other) const {

    return type_ == other.type_;

  }

  bool IsSubtypeOf(const HType& other) {

    return Combine(other).Equals(other);

  }

  bool IsTaggedPrimitive() const {

    return ((type_ & kTaggedPrimitive) == kTaggedPrimitive);

  }

  bool IsTaggedNumber() const {

    return ((type_ & kTaggedNumber) == kTaggedNumber);

  }

  bool IsSmi() const {

    return ((type_ & kSmi) == kSmi);

  }

  bool IsHeapNumber() const {

    return ((type_ & kHeapNumber) == kHeapNumber);

  }

  bool IsString() const {

    return ((type_ & kString) == kString);

  }

  bool IsNonString() const {

    return IsTaggedPrimitive() || IsSmi() || IsHeapNumber() ||

        IsBoolean() || IsJSArray();

  }

  bool IsBoolean() const {

    return ((type_ & kBoolean) == kBoolean);

  }

  bool IsNonPrimitive() const {

    return ((type_ & kNonPrimitive) == kNonPrimitive);

  }

  bool IsJSArray() const {

    return ((type_ & kJSArray) == kJSArray);

  }

  bool IsJSObject() const {

    return ((type_ & kJSObject) == kJSObject);

  }

  bool IsHeapObject() const {

    return IsHeapNumber() || IsString() || IsBoolean() || IsNonPrimitive();

  }

  bool ToStringOrToNumberCanBeObserved(Representation representation) {

    switch (type_) {

      case kTaggedPrimitive:  // fallthru

      case kTaggedNumber:     // fallthru

      case kSmi:              // fallthru

      case kHeapNumber:       // fallthru

      case kString:           // fallthru

      case kBoolean:

        return false;

      case kJSArray:          // fallthru

      case kJSObject:

        return true;

      case kTagged:

        break;

    }

    return !representation.IsSmiOrInteger32() && !representation.IsDouble();

  }

  static HType TypeFromValue(Handle<Object> value);

  const char* ToString();

 private:

  enum Type {

    kNone = 0x0,             // 0000 0000 0000 0000

    kTagged = 0x1,           // 0000 0000 0000 0001

    kTaggedPrimitive = 0x5,  // 0000 0000 0000 0101

    kTaggedNumber = 0xd,     // 0000 0000 0000 1101

    kSmi = 0x1d,             // 0000 0000 0001 1101

    kHeapNumber = 0x2d,      // 0000 0000 0010 1101

    kString = 0x45,          // 0000 0000 0100 0101

    kBoolean = 0x85,         // 0000 0000 1000 0101

    kNonPrimitive = 0x101,   // 0000 0001 0000 0001

    kJSObject = 0x301,       // 0000 0011 0000 0001

    kJSArray = 0x701         // 0000 0111 0000 0001

  };

  // Make sure type fits in int16.

  STATIC_ASSERT(kJSArray < (1 << (2 * kBitsPerByte)));

  explicit HType(Type t) : type_(t) { }

  int16_t type_;

};

class HUseListNode: public ZoneObject {

 public:

  HUseListNode(HValue* value, int index, HUseListNode* tail)

      : tail_(tail), value_(value), index_(index) {

  }

  HUseListNode* tail();

  HValue* value() const { return value_; }

  int index() const { return index_; }

  void set_tail(HUseListNode* list) { tail_ = list; }

#ifdef DEBUG

  void Zap() {

    tail_ = reinterpret_cast<HUseListNode*>(1);

    value_ = NULL;

    index_ = -1;

  }

#endif

 private:

  HUseListNode* tail_;

  HValue* value_;

  int index_;

};

// We reuse use list nodes behind the scenes as uses are added and deleted.

// This class is the safe way to iterate uses while deleting them.

class HUseIterator V8_FINAL BASE_EMBEDDED {

 public:

  bool Done() { return current_ == NULL; }

  void Advance();

  HValue* value() {

    ASSERT(!Done());

    return value_;

  }

  int index() {

    ASSERT(!Done());

    return index_;

  }

 private:

  explicit HUseIterator(HUseListNode* head);

  HUseListNode* current_;

  HUseListNode* next_;

  HValue* value_;

  int index_;

  friend class HValue;

};

// There must be one corresponding kDepends flag for every kChanges flag and

// the order of the kChanges flags must be exactly the same as of the kDepends

// flags. All tracked flags should appear before untracked ones.

enum GVNFlag {

  // Declare global value numbering flags.

#define DECLARE_FLAG(type) kChanges##type, kDependsOn##type,

  GVN_TRACKED_FLAG_LIST(DECLARE_FLAG)

  GVN_UNTRACKED_FLAG_LIST(DECLARE_FLAG)

#undef DECLARE_FLAG

  kAfterLastFlag,

  kLastFlag = kAfterLastFlag - 1,

#define COUNT_FLAG(type) + 1

  kNumberOfTrackedSideEffects = 0 GVN_TRACKED_FLAG_LIST(COUNT_FLAG)

#undef COUNT_FLAG

};

class DecompositionResult V8_FINAL BASE_EMBEDDED {

 public:

  DecompositionResult() : base_(NULL), offset_(0), scale_(0) {}

  HValue* base() { return base_; }

  int offset() { return offset_; }

  int scale() { return scale_; }

  bool Apply(HValue* other_base, int other_offset, int other_scale = 0) {

    if (base_ == NULL) {

      base_ = other_base;

      offset_ = other_offset;

      scale_ = other_scale;

      return true;

    } else {

      if (scale_ == 0) {

        base_ = other_base;

        offset_ += other_offset;

        scale_ = other_scale;

        return true;

      } else {

        return false;

      }

    }

  }

  void SwapValues(HValue** other_base, int* other_offset, int* other_scale) {

    swap(&base_, other_base);

    swap(&offset_, other_offset);

    swap(&scale_, other_scale);

  }

 private:

  template <class T> void swap(T* a, T* b) {

    T c(*a);

    *a = *b;

    *b = c;

  }

  HValue* base_;

  int offset_;

  int scale_;

};

typedef EnumSet<GVNFlag> GVNFlagSet;

class HValue : public ZoneObject {

 public:

  static const int kNoNumber = -1;

  enum Flag {

    kFlexibleRepresentation,

    kCannotBeTagged,

    // Participate in Global Value Numbering, i.e. elimination of

    // unnecessary recomputations. If an instruction sets this flag, it must

    // implement DataEquals(), which will be used to determine if other

    // occurrences of the instruction are indeed the same.

    kUseGVN,

    // Track instructions that are dominating side effects. If an instruction

    // sets this flag, it must implement HandleSideEffectDominator() and should

    // indicate which side effects to track by setting GVN flags.

    kTrackSideEffectDominators,

    kCanOverflow,

    kBailoutOnMinusZero,

    kCanBeDivByZero,

    kAllowUndefinedAsNaN,

    kIsArguments,

    kTruncatingToInt32,

    kAllUsesTruncatingToInt32,

    kTruncatingToSmi,

    kAllUsesTruncatingToSmi,

    // Set after an instruction is killed.

    kIsDead,

    // Instructions that are allowed to produce full range unsigned integer

    // values are marked with kUint32 flag. If arithmetic shift or a load from

    // EXTERNAL_UNSIGNED_INT_ELEMENTS array is not marked with this flag

    // it will deoptimize if result does not fit into signed integer range.

    // HGraph::ComputeSafeUint32Operations is responsible for setting this

    // flag.

    kUint32,

    kHasNoObservableSideEffects,

    // Indicates the instruction is live during dead code elimination.

    kIsLive,

    // HEnvironmentMarkers are deleted before dead code

    // elimination takes place, so they can repurpose the kIsLive flag:

    kEndsLiveRange = kIsLive,

    // TODO(everyone): Don't forget to update this!

    kLastFlag = kIsLive

  };

  STATIC_ASSERT(kLastFlag < kBitsPerInt);

  static const int kChangesToDependsFlagsLeftShift = 1;

  static GVNFlag ChangesFlagFromInt(int x) {

    return static_cast<GVNFlag>(x * 2);

  }

  static GVNFlag DependsOnFlagFromInt(int x) {

    return static_cast<GVNFlag>(x * 2 + 1);

  }

  static GVNFlagSet ConvertChangesToDependsFlags(GVNFlagSet flags) {

    return GVNFlagSet(flags.ToIntegral() << kChangesToDependsFlagsLeftShift);

  }

  static HValue* cast(HValue* value) { return value; }

  enum Opcode {

    // Declare a unique enum value for each hydrogen instruction.

  #define DECLARE_OPCODE(type) k##type,

    HYDROGEN_CONCRETE_INSTRUCTION_LIST(DECLARE_OPCODE)

    kPhi

  #undef DECLARE_OPCODE

  };

  virtual Opcode opcode() const = 0;

  // Declare a non-virtual predicates for each concrete HInstruction or HValue.

  #define DECLARE_PREDICATE(type) \

    bool Is##type() const { return opcode() == k##type; }

    HYDROGEN_CONCRETE_INSTRUCTION_LIST(DECLARE_PREDICATE)

  #undef DECLARE_PREDICATE

    bool IsPhi() const { return opcode() == kPhi; }

  // Declare virtual predicates for abstract HInstruction or HValue

  #define DECLARE_PREDICATE(type) \

    virtual bool Is##type() const { return false; }

    HYDROGEN_ABSTRACT_INSTRUCTION_LIST(DECLARE_PREDICATE)

  #undef DECLARE_PREDICATE

  HValue(HType type = HType::Tagged())

      : block_(NULL),

        id_(kNoNumber),

        type_(type),

        use_list_(NULL),

        range_(NULL),

        flags_(0) {}

  virtual ~HValue() {}

  virtual int position() const { return RelocInfo::kNoPosition; }

  HBasicBlock* block() const { return block_; }

  void SetBlock(HBasicBlock* block);

  int LoopWeight() const;

  // Note: Never call this method for an unlinked value.

  Isolate* isolate() const;

  int id() const { return id_; }

  void set_id(int id) { id_ = id; }

  HUseIterator uses() const { return HUseIterator(use_list_); }

  virtual bool EmitAtUses() { return false; }

  Representation representation() const { return representation_; }

  void ChangeRepresentation(Representation r) {

    ASSERT(CheckFlag(kFlexibleRepresentation));

    ASSERT(!CheckFlag(kCannotBeTagged) || !r.IsTagged());

    RepresentationChanged(r);

    representation_ = r;

    if (r.IsTagged()) {

      // Tagged is the bottom of the lattice, don't go any further.

      ClearFlag(kFlexibleRepresentation);

    }

  }

  virtual void AssumeRepresentation(Representation r);

  virtual Representation KnownOptimalRepresentation() {

    Representation r = representation();

    if (r.IsTagged()) {

      HType t = type();

      if (t.IsSmi()) return Representation::Smi();

      if (t.IsHeapNumber()) return Representation::Double();

      if (t.IsHeapObject()) return r;

      return Representation::None();

    }

    return r;

  }

  HType type() const { return type_; }

  void set_type(HType new_type) {

    ASSERT(new_type.IsSubtypeOf(type_));

    type_ = new_type;

  }

  bool IsHeapObject() {

    return representation_.IsHeapObject() || type_.IsHeapObject();

  }

  // An operation needs to override this function iff:

  //   1) it can produce an int32 output.

  //   2) the true value of its output can potentially be minus zero.

  // The implementation must set a flag so that it bails out in the case where

  // it would otherwise output what should be a minus zero as an int32 zero.

  // If the operation also exists in a form that takes int32 and outputs int32

  // then the operation should return its input value so that we can propagate

  // back.  There are three operations that need to propagate back to more than

  // one input.  They are phi and binary div and mul.  They always return NULL

  // and expect the caller to take care of things.

  virtual HValue* EnsureAndPropagateNotMinusZero(BitVector* visited) {

    visited->Add(id());

    return NULL;

  }

  // There are HInstructions that do not really change a value, they

  // only add pieces of information to it (like bounds checks, map checks,

  // smi checks...).

  // We call these instructions "informative definitions", or "iDef".

  // One of the iDef operands is special because it is the value that is

  // "transferred" to the output, we call it the "redefined operand".

  // If an HValue is an iDef it must override RedefinedOperandIndex() so that

  // it does not return kNoRedefinedOperand;

  static const int kNoRedefinedOperand = -1;

  virtual int RedefinedOperandIndex() { return kNoRedefinedOperand; }

  bool IsInformativeDefinition() {

    return RedefinedOperandIndex() != kNoRedefinedOperand;

  }

  HValue* RedefinedOperand() {

    int index = RedefinedOperandIndex();

    return index == kNoRedefinedOperand ? NULL : OperandAt(index);

  }

  bool CanReplaceWithDummyUses();

  virtual int argument_delta() const { return 0; }

  // A purely informative definition is an idef that will not emit code and

  // should therefore be removed from the graph in the RestoreActualValues

  // phase (so that live ranges will be shorter).

  virtual bool IsPurelyInformativeDefinition() { return false; }

  // This method must always return the original HValue SSA definition,

  // regardless of any chain of iDefs of this value.

  HValue* ActualValue() {

    HValue* value = this;

    int index;

    while ((index = value->RedefinedOperandIndex()) != kNoRedefinedOperand) {

      value = value->OperandAt(index);

    }

    return value;

  }

  bool IsInteger32Constant();

  int32_t GetInteger32Constant();

  bool EqualsInteger32Constant(int32_t value);

  bool IsDefinedAfter(HBasicBlock* other) const;

  // Operands.

  virtual int OperandCount() = 0;

  virtual HValue* OperandAt(int index) const = 0;

  void SetOperandAt(int index, HValue* value);

  void DeleteAndReplaceWith(HValue* other);

  void ReplaceAllUsesWith(HValue* other);

  bool HasNoUses() const { return use_list_ == NULL; }

  bool HasMultipleUses() const {

    return use_list_ != NULL && use_list_->tail() != NULL;

  }

  int UseCount() const;

  // Mark this HValue as dead and to be removed from other HValues' use lists.

  void Kill();

  int flags() const { return flags_; }

  void SetFlag(Flag f) { flags_ |= (1 << f); }

  void ClearFlag(Flag f) { flags_ &= ~(1 << f); }

  bool CheckFlag(Flag f) const { return (flags_ & (1 << f)) != 0; }

  void CopyFlag(Flag f, HValue* other) {

    if (other->CheckFlag(f)) SetFlag(f);

  }

  // Returns true if the flag specified is set for all uses, false otherwise.

  bool CheckUsesForFlag(Flag f) const;

  // Same as before and the first one without the flag is returned in value.

  bool CheckUsesForFlag(Flag f, HValue** value) const;

  // Returns true if the flag specified is set for all uses, and this set

  // of uses is non-empty.

  bool HasAtLeastOneUseWithFlagAndNoneWithout(Flag f) const;

  GVNFlagSet gvn_flags() const { return gvn_flags_; }

  void SetGVNFlag(GVNFlag f) { gvn_flags_.Add(f); }

  void ClearGVNFlag(GVNFlag f) { gvn_flags_.Remove(f); }

  bool CheckGVNFlag(GVNFlag f) const { return gvn_flags_.Contains(f); }

  void SetAllSideEffects() { gvn_flags_.Add(AllSideEffectsFlagSet()); }

  void ClearAllSideEffects() {

    gvn_flags_.Remove(AllSideEffectsFlagSet());

  }

  bool HasSideEffects() const {

    return gvn_flags_.ContainsAnyOf(AllSideEffectsFlagSet());

  }

  bool HasObservableSideEffects() const {

    return !CheckFlag(kHasNoObservableSideEffects) &&

        gvn_flags_.ContainsAnyOf(AllObservableSideEffectsFlagSet());

  }

  GVNFlagSet DependsOnFlags() const {

    GVNFlagSet result = gvn_flags_;

    result.Intersect(AllDependsOnFlagSet());

    return result;

  }

  GVNFlagSet SideEffectFlags() const {

    GVNFlagSet result = gvn_flags_;

    result.Intersect(AllSideEffectsFlagSet());

    return result;

  }

  GVNFlagSet ChangesFlags() const {

    GVNFlagSet result = gvn_flags_;

    result.Intersect(AllChangesFlagSet());

    return result;

  }

  GVNFlagSet ObservableChangesFlags() const {

    GVNFlagSet result = gvn_flags_;

    result.Intersect(AllChangesFlagSet());

    result.Intersect(AllObservableSideEffectsFlagSet());

    return result;

  }

  Range* range() const { return range_; }

  // TODO(svenpanne) We should really use the null object pattern here.

  bool HasRange() const { return range_ != NULL; }

  bool CanBeNegative() const { return !HasRange() || range()->CanBeNegative(); }

  bool CanBeZero() const { return !HasRange() || range()->CanBeZero(); }

  bool RangeCanInclude(int value) const {

    return !HasRange() || range()->Includes(value);

  }

  void AddNewRange(Range* r, Zone* zone);

  void RemoveLastAddedRange();

  void ComputeInitialRange(Zone* zone);

  // Escape analysis helpers.

  virtual bool HasEscapingOperandAt(int index) { return true; }

  virtual bool HasOutOfBoundsAccess(int size) { return false; }

  // Representation helpers.

  virtual Representation observed_input_representation(int index) {

    return Representation::None();

  }

  virtual Representation RequiredInputRepresentation(int index) = 0;

  virtual void InferRepresentation(HInferRepresentationPhase* h_infer);

  // This gives the instruction an opportunity to replace itself with an

  // instruction that does the same in some better way.  To replace an

  // instruction with a new one, first add the new instruction to the graph,

  // then return it.  Return NULL to have the instruction deleted.

  virtual HValue* Canonicalize() { return this; }

  bool Equals(HValue* other);

  virtual intptr_t Hashcode();

  // Compute unique ids upfront that is safe wrt GC and concurrent compilation.

  virtual void FinalizeUniqueness() { }

  // Printing support.

  virtual void PrintTo(StringStream* stream) = 0;

  void PrintNameTo(StringStream* stream);

  void PrintTypeTo(StringStream* stream);

  void PrintRangeTo(StringStream* stream);

  void PrintChangesTo(StringStream* stream);

  const char* Mnemonic() const;

  // Type information helpers.

  bool HasMonomorphicJSObjectType();

  // TODO(mstarzinger): For now instructions can override this function to

  // specify statically known types, once HType can convey more information

  // it should be based on the HType.

  virtual Handle<Map> GetMonomorphicJSObjectMap() { return Handle<Map>(); }

  // Updated the inferred type of this instruction and returns true if

  // it has changed.

  bool UpdateInferredType();

  virtual HType CalculateInferredType();

  // This function must be overridden for instructions which have the

  // kTrackSideEffectDominators flag set, to track instructions that are

  // dominating side effects.

  virtual void HandleSideEffectDominator(GVNFlag side_effect,

                                         HValue* dominator) {

    UNREACHABLE();

  }

  // Check if this instruction has some reason that prevents elimination.

  bool CannotBeEliminated() const {

    return HasObservableSideEffects() || !IsDeletable();

  }

#ifdef DEBUG

  virtual void Verify() = 0;

#endif

  virtual bool TryDecompose(DecompositionResult* decomposition) {

    if (RedefinedOperand() != NULL) {

      return RedefinedOperand()->TryDecompose(decomposition);

    } else {

      return false;

    }

  }

  // Returns true conservatively if the program might be able to observe a

  // ToString() operation on this value.

  bool ToStringCanBeObserved() const {

    return type().ToStringOrToNumberCanBeObserved(representation());

  }

  // Returns true conservatively if the program might be able to observe a

  // ToNumber() operation on this value.

  bool ToNumberCanBeObserved() const {

    return type().ToStringOrToNumberCanBeObserved(representation());

  }

  MinusZeroMode GetMinusZeroMode() {

    return CheckFlag(kBailoutOnMinusZero)

        ? FAIL_ON_MINUS_ZERO : TREAT_MINUS_ZERO_AS_ZERO;

  }

 protected:

  // This function must be overridden for instructions with flag kUseGVN, to

  // compare the non-Operand parts of the instruction.

  virtual bool DataEquals(HValue* other) {

    UNREACHABLE();

    return false;

  }

  virtual Representation RepresentationFromInputs() {

    return representation();

  }

  Representation RepresentationFromUses();

  Representation RepresentationFromUseRequirements();

  bool HasNonSmiUse();

  virtual void UpdateRepresentation(Representation new_rep,

                                    HInferRepresentationPhase* h_infer,

                                    const char* reason);

  void AddDependantsToWorklist(HInferRepresentationPhase* h_infer);

  virtual void RepresentationChanged(Representation to) { }

  virtual Range* InferRange(Zone* zone);

  virtual void DeleteFromGraph() = 0;

  virtual void InternalSetOperandAt(int index, HValue* value) = 0;

  void clear_block() {

    ASSERT(block_ != NULL);

    block_ = NULL;

  }

  void set_representation(Representation r) {

    ASSERT(representation_.IsNone() && !r.IsNone());

    representation_ = r;

  }

  static GVNFlagSet AllDependsOnFlagSet() {

    GVNFlagSet result;

    // Create changes mask.

#define ADD_FLAG(type) result.Add(kDependsOn##type);

  GVN_TRACKED_FLAG_LIST(ADD_FLAG)

  GVN_UNTRACKED_FLAG_LIST(ADD_FLAG)

#undef ADD_FLAG

    return result;

  }

  static GVNFlagSet AllChangesFlagSet() {

    GVNFlagSet result;

    // Create changes mask.

#define ADD_FLAG(type) result.Add(kChanges##type);

  GVN_TRACKED_FLAG_LIST(ADD_FLAG)

  GVN_UNTRACKED_FLAG_LIST(ADD_FLAG)

#undef ADD_FLAG

    return result;

  }

  // A flag mask to mark an instruction as having arbitrary side effects.

  static GVNFlagSet AllSideEffectsFlagSet() {

    GVNFlagSet result = AllChangesFlagSet();

    result.Remove(kChangesOsrEntries);

    return result;

  }

  // A flag mask of all side effects that can make observable changes in

  // an executing program (i.e. are not safe to repeat, move or remove);

  static GVNFlagSet AllObservableSideEffectsFlagSet() {

    GVNFlagSet result = AllChangesFlagSet();

    result.Remove(kChangesNewSpacePromotion);

    result.Remove(kChangesElementsKind);

    result.Remove(kChangesElementsPointer);

    result.Remove(kChangesMaps);

    return result;

  }

  // Remove the matching use from the use list if present.  Returns the

  // removed list node or NULL.

  HUseListNode* RemoveUse(HValue* value, int index);

  void RegisterUse(int index, HValue* new_value);

  HBasicBlock* block_;

  // The id of this instruction in the hydrogen graph, assigned when first

  // added to the graph. Reflects creation order.

  int id_;

  Representation representation_;

  HType type_;

  HUseListNode* use_list_;

  Range* range_;

  int flags_;

  GVNFlagSet gvn_flags_;

 private:

  virtual bool IsDeletable() const { return false; }

  DISALLOW_COPY_AND_ASSIGN(HValue);

};

#define DECLARE_INSTRUCTION_FACTORY_P0(I)                                      \

  static I* New(Zone* zone, HValue* context) {                                 \

    return new(zone) I();                                                      \

}

#define DECLARE_INSTRUCTION_FACTORY_P1(I, P1)                                  \

  static I* New(Zone* zone, HValue* context, P1 p1) {                          \

    return new(zone) I(p1);                                                    \

  }

#define DECLARE_INSTRUCTION_FACTORY_P2(I, P1, P2)                              \

  static I* New(Zone* zone, HValue* context, P1 p1, P2 p2) {                   \

    return new(zone) I(p1, p2);                                                \

  }

#define DECLARE_INSTRUCTION_FACTORY_P3(I, P1, P2, P3)                          \

  static I* New(Zone* zone, HValue* context, P1 p1, P2 p2, P3 p3) {            \

    return new(zone) I(p1, p2, p3);                                            \

  }

#define DECLARE_INSTRUCTION_FACTORY_P4(I, P1, P2, P3, P4)                      \

  static I* New(Zone* zone,                                                    \

                HValue* context,                                               \

                P1 p1,                                                         \

                P2 p2,                                                         \

                P3 p3,                                                         \

                P4 p4) {                                                       \

    return new(zone) I(p1, p2, p3, p4);                                        \

  }

#define DECLARE_INSTRUCTION_FACTORY_P5(I, P1, P2, P3, P4, P5)                  \

  static I* New(Zone* zone,                                                    \

                HValue* context,                                               \

                P1 p1,                                                         \

                P2 p2,                                                         \

                P3 p3,                                                         \

                P4 p4,                                                         \

                P5 p5) {                                                       \

    return new(zone) I(p1, p2, p3, p4, p5);                                    \

  }

#define DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P0(I)                         \

  static I* New(Zone* zone, HValue* context) {                                 \

    return new(zone) I(context);                                               \

  }

#define DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P1(I, P1)                     \

  static I* New(Zone* zone, HValue* context, P1 p1) {                          \

    return new(zone) I(context, p1);                                           \

  }

#define DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P2(I, P1, P2)                 \

  static I* New(Zone* zone, HValue* context, P1 p1, P2 p2) {                   \

    return new(zone) I(context, p1, p2);                                       \

  }

#define DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P3(I, P1, P2, P3)             \

  static I* New(Zone* zone, HValue* context, P1 p1, P2 p2, P3 p3) {            \

    return new(zone) I(context, p1, p2, p3);                                   \

  }

#define DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P4(I, P1, P2, P3, P4)         \

  static I* New(Zone* zone,                                                    \

                HValue* context,                                               \

                P1 p1,                                                         \

                P2 p2,                                                         \

                P3 p3,                                                         \

                P4 p4) {                                                       \

    return new(zone) I(context, p1, p2, p3, p4);                               \

  }

#define DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P5(I, P1, P2, P3, P4, P5)     \

  static I* New(Zone* zone,                                                    \

                HValue* context,                                               \

                P1 p1,                                                         \

                P2 p2,                                                         \

                P3 p3,                                                         \

                P4 p4,                                                         \

                P5 p5) {                                                       \

    return new(zone) I(context, p1, p2, p3, p4, p5);                           \

  }

class HInstruction : public HValue {

 public:

  HInstruction* next() const { return next_; }

  HInstruction* previous() const { return previous_; }

  virtual void PrintTo(StringStream* stream) V8_OVERRIDE;

  virtual void PrintDataTo(StringStream* stream);

  bool IsLinked() const { return block() != NULL; }

  void Unlink();

  void InsertBefore(HInstruction* next);

  void InsertAfter(HInstruction* previous);

  // The position is a write-once variable.

  virtual int position() const V8_OVERRIDE { return position_; }

  bool has_position() const { return position_ != RelocInfo::kNoPosition; }

  void set_position(int position) {

    ASSERT(!has_position());

    ASSERT(position != RelocInfo::kNoPosition);

    position_ = position;

  }

  bool CanTruncateToInt32() const { return CheckFlag(kTruncatingToInt32); }

  virtual LInstruction* CompileToLithium(LChunkBuilder* builder) = 0;

#ifdef DEBUG

  virtual void Verify() V8_OVERRIDE;

#endif

  virtual bool IsCall() { return false; }

  DECLARE_ABSTRACT_INSTRUCTION(Instruction)

 protected:

  HInstruction(HType type = HType::Tagged())

      : HValue(type),

        next_(NULL),

        previous_(NULL),

        position_(RelocInfo::kNoPosition) {

    SetGVNFlag(kDependsOnOsrEntries);

  }

  virtual void DeleteFromGraph() V8_OVERRIDE { Unlink(); }

 private:

  void InitializeAsFirst(HBasicBlock* block) {

    ASSERT(!IsLinked());

    SetBlock(block);

  }

  void PrintMnemonicTo(StringStream* stream);

  HInstruction* next_;

  HInstruction* previous_;

  int position_;

  friend class HBasicBlock;

};

template<int V>

class HTemplateInstruction : public HInstruction {

 public:

  virtual int OperandCount() V8_FINAL V8_OVERRIDE { return V; }

  virtual HValue* OperandAt(int i) const V8_FINAL V8_OVERRIDE {

    return inputs_[i];

  }

 protected:

  HTemplateInstruction(HType type = HType::Tagged()) : HInstruction(type) {}

  virtual void InternalSetOperandAt(int i, HValue* value) V8_FINAL V8_OVERRIDE {

    inputs_[i] = value;

  }

 private:

  EmbeddedContainer<HValue*, V> inputs_;

};

class HControlInstruction : public HInstruction {

 public:

  virtual HBasicBlock* SuccessorAt(int i) = 0;

  virtual int SuccessorCount() = 0;

  virtual void SetSuccessorAt(int i, HBasicBlock* block) = 0;

  virtual void PrintDataTo(StringStream* stream) V8_OVERRIDE;

  virtual bool KnownSuccessorBlock(HBasicBlock** block) {

    *block = NULL;

    return false;

  }

  HBasicBlock* FirstSuccessor() {

    return SuccessorCount() > 0 ? SuccessorAt(0) : NULL;

  }

  HBasicBlock* SecondSuccessor() {

    return SuccessorCount() > 1 ? SuccessorAt(1) : NULL;

  }

  void Not() {

    HBasicBlock* swap = SuccessorAt(0);

    SetSuccessorAt(0, SuccessorAt(1));

    SetSuccessorAt(1, swap);

  }

  DECLARE_ABSTRACT_INSTRUCTION(ControlInstruction)

};

class HSuccessorIterator V8_FINAL BASE_EMBEDDED {

 public:

  explicit HSuccessorIterator(HControlInstruction* instr)

      : instr_(instr), current_(0) { }

  bool Done() { return current_ >= instr_->SuccessorCount(); }

  HBasicBlock* Current() { return instr_->SuccessorAt(current_); }

  void Advance() { current_++; }

 private:

  HControlInstruction* instr_;

  int current_;

};

template<int S, int V>

class HTemplateControlInstruction : public HControlInstruction {

 public:

  int SuccessorCount() V8_OVERRIDE { return S; }

  HBasicBlock* SuccessorAt(int i) V8_OVERRIDE { return successors_[i]; }

  void SetSuccessorAt(int i, HBasicBlock* block) V8_OVERRIDE {

    successors_[i] = block;

  }

  int OperandCount() V8_OVERRIDE { return V; }

  HValue* OperandAt(int i) const V8_OVERRIDE { return inputs_[i]; }

 protected:

  void InternalSetOperandAt(int i, HValue* value) V8_OVERRIDE {

    inputs_[i] = value;

  }

 private:

  EmbeddedContainer<HBasicBlock*, S> successors_;

  EmbeddedContainer<HValue*, V> inputs_;

};

class HBlockEntry V8_FINAL : public HTemplateInstruction<0> {

 public:

  virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {

    return Representation::None();

  }

  DECLARE_CONCRETE_INSTRUCTION(BlockEntry)

};

class HDummyUse V8_FINAL : public HTemplateInstruction<1> {

 public:

  explicit HDummyUse(HValue* value)

      : HTemplateInstruction<1>(HType::Smi()) {

    SetOperandAt(0, value);

    // Pretend to be a Smi so that the HChange instructions inserted

    // before any use generate as little code as possible.

    set_representation(Representation::Tagged());

  }

  HValue* value() { return OperandAt(0); }

  virtual bool HasEscapingOperandAt(int index) V8_OVERRIDE { return false; }

  virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {

    return Representation::None();

  }

  virtual void PrintDataTo(StringStream* stream) V8_OVERRIDE;

  DECLARE_CONCRETE_INSTRUCTION(DummyUse);

};

// Inserts an int3/stop break instruction for debugging purposes.

class HDebugBreak V8_FINAL : public HTemplateInstruction<0> {

 public:

  DECLARE_INSTRUCTION_FACTORY_P0(HDebugBreak);

  virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {

    return Representation::None();

  }

  DECLARE_CONCRETE_INSTRUCTION(DebugBreak)

};

class HGoto V8_FINAL : public HTemplateControlInstruction<1, 0> {

 public:

  explicit HGoto(HBasicBlock* target) {

    SetSuccessorAt(0, target);

  }

  virtual bool KnownSuccessorBlock(HBasicBlock** block) V8_OVERRIDE {

    *block = FirstSuccessor();

    return true;

  }

  virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {

    return Representation::None();

  }

  virtual void PrintDataTo(StringStream* stream) V8_OVERRIDE;

  DECLARE_CONCRETE_INSTRUCTION(Goto)

};

class HDeoptimize V8_FINAL : public HTemplateControlInstruction<1, 0> {

 public:

  static HInstruction* New(Zone* zone,

                           HValue* context,

                           const char* reason,

                           Deoptimizer::BailoutType type,

                           HBasicBlock* unreachable_continuation) {

    return new(zone) HDeoptimize(reason, type, unreachable_continuation);

  }

  virtual bool KnownSuccessorBlock(HBasicBlock** block) V8_OVERRIDE {

    *block = NULL;

    return true;

  }

  virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {

    return Representation::None();

  }

  const char* reason() const { return reason_; }

  Deoptimizer::BailoutType type() { return type_; }

  DECLARE_CONCRETE_INSTRUCTION(Deoptimize)

 private:

  explicit HDeoptimize(const char* reason,

                       Deoptimizer::BailoutType type,

                       HBasicBlock* unreachable_continuation)

      : reason_(reason), type_(type) {

    SetSuccessorAt(0, unreachable_continuation);

  }

  const char* reason_;

  Deoptimizer::BailoutType type_;

};

class HUnaryControlInstruction : public HTemplateControlInstruction<2, 1> {

 public:

  HUnaryControlInstruction(HValue* value,

                           HBasicBlock* true_target,

                           HBasicBlock* false_target) {

    SetOperandAt(0, value);

    SetSuccessorAt(0, true_target);

    SetSuccessorAt(1, false_target);

  }

  virtual void PrintDataTo(StringStream* stream) V8_OVERRIDE;

  HValue* value() { return OperandAt(0); }

};

class HBranch V8_FINAL : public HUnaryControlInstruction {

 public:

  DECLARE_INSTRUCTION_FACTORY_P1(HBranch, HValue*);

  DECLARE_INSTRUCTION_FACTORY_P2(HBranch, HValue*,

                                 ToBooleanStub::Types);

  DECLARE_INSTRUCTION_FACTORY_P4(HBranch, HValue*,

                                 ToBooleanStub::Types,

                                 HBasicBlock*, HBasicBlock*);

  virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {

    return Representation::None();

  }

  virtual Representation observed_input_representation(int index) V8_OVERRIDE;

  virtual bool KnownSuccessorBlock(HBasicBlock** block) V8_OVERRIDE;

  ToBooleanStub::Types expected_input_types() const {

    return expected_input_types_;

  }

  DECLARE_CONCRETE_INSTRUCTION(Branch)