src/v8/src/hydrogen-instructions.h

   1 // Copyright 2012 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #ifndef V8_HYDROGEN_INSTRUCTIONS_H_
   6 #define V8_HYDROGEN_INSTRUCTIONS_H_
   7
   8 #include "src/v8.h"
   9
  10 #include "src/allocation.h"
  11 #include "src/code-stubs.h"
  12 #include "src/conversions.h"
  13 #include "src/data-flow.h"
  14 #include "src/deoptimizer.h"
  15 #include "src/feedback-slots.h"
  16 #include "src/hydrogen-types.h"
  17 #include "src/small-pointer-list.h"
  18 #include "src/unique.h"
  19 #include "src/utils.h"
  20 #include "src/zone.h"
  21
  22 namespace v8 {
  23 namespace internal {
  24
  25 // Forward declarations.
  26 struct ChangesOf;
  27 class HBasicBlock;
  28 class HDiv;
  29 class HEnvironment;
  30 class HInferRepresentationPhase;
  31 class HInstruction;
  32 class HLoopInformation;
  33 class HStoreNamedField;
  34 class HValue;
  35 class LInstruction;
  36 class LChunkBuilder;
  37 class OStream;
  38
  39 #define HYDROGEN_ABSTRACT_INSTRUCTION_LIST(V)  \
  40   V(ArithmeticBinaryOperation)                 \
  41   V(BinaryOperation)                           \
  42   V(BitwiseBinaryOperation)                    \
  43   V(ControlInstruction)                        \
  44   V(Instruction)                               \
  45
  46
  47 #define HYDROGEN_CONCRETE_INSTRUCTION_LIST(V)  \
  48   V(AbnormalExit)                              \
  49   V(AccessArgumentsAt)                         \
  50   V(Add)                                       \
  51   V(AllocateBlockContext)                      \
  52   V(Allocate)                                  \
  53   V(ApplyArguments)                            \
  54   V(ArgumentsElements)                         \
  55   V(ArgumentsLength)                           \
  56   V(ArgumentsObject)                           \
  57   V(Bitwise)                                   \
  58   V(BlockEntry)                                \
  59   V(BoundsCheck)                               \
  60   V(BoundsCheckBaseIndexInformation)           \
  61   V(Branch)                                    \
  62   V(CallWithDescriptor)                        \
  63   V(CallJSFunction)                            \
  64   V(CallFunction)                              \
  65   V(CallNew)                                   \
  66   V(CallNewArray)                              \
  67   V(CallRuntime)                               \
  68   V(CallStub)                                  \
  69   V(CapturedObject)                            \
  70   V(Change)                                    \
  71   V(CheckHeapObject)                           \
  72   V(CheckInstanceType)                         \
  73   V(CheckMaps)                                 \
  74   V(CheckMapValue)                             \
  75   V(CheckSmi)                                  \
  76   V(CheckValue)                                \
  77   V(ClampToUint8)                              \
  78   V(ClassOfTestAndBranch)                      \
  79   V(CompareNumericAndBranch)                   \
  80   V(CompareHoleAndBranch)                      \
  81   V(CompareGeneric)                            \
  82   V(CompareMinusZeroAndBranch)                 \
  83   V(CompareObjectEqAndBranch)                  \
  84   V(CompareMap)                                \
  85   V(Constant)                                  \
  86   V(ConstructDouble)                           \
  87   V(Context)                                   \
  88   V(DateField)                                 \
  89   V(DebugBreak)                                \
  90   V(DeclareGlobals)                            \
  91   V(Deoptimize)                                \
  92   V(Div)                                       \
  93   V(DoubleBits)                                \
  94   V(DummyUse)                                  \
  95   V(EnterInlined)                              \
  96   V(EnvironmentMarker)                         \
  97   V(ForceRepresentation)                       \
  98   V(ForInCacheArray)                           \
  99   V(ForInPrepareMap)                           \
 100   V(FunctionLiteral)                           \
 101   V(GetCachedArrayIndex)                       \
 102   V(Goto)                                      \
 103   V(HasCachedArrayIndexAndBranch)              \
 104   V(HasInstanceTypeAndBranch)                  \
 105   V(InnerAllocatedObject)                      \
 106   V(InstanceOf)                                \
 107   V(InstanceOfKnownGlobal)                     \
 108   V(InvokeFunction)                            \
 109   V(IsConstructCallAndBranch)                  \
 110   V(IsObjectAndBranch)                         \
 111   V(IsStringAndBranch)                         \
 112   V(IsSmiAndBranch)                            \
 113   V(IsUndetectableAndBranch)                   \
 114   V(LeaveInlined)                              \
 115   V(LoadContextSlot)                           \
 116   V(LoadFieldByIndex)                          \
 117   V(LoadFunctionPrototype)                     \
 118   V(LoadGlobalCell)                            \
 119   V(LoadGlobalGeneric)                         \
 120   V(LoadKeyed)                                 \
 121   V(LoadKeyedGeneric)                          \
 122   V(LoadNamedField)                            \
 123   V(LoadNamedGeneric)                          \
 124   V(LoadRoot)                                  \
 125   V(MapEnumLength)                             \
 126   V(MathFloorOfDiv)                            \
 127   V(MathMinMax)                                \
 128   V(Mod)                                       \
 129   V(Mul)                                       \
 130   V(OsrEntry)                                  \
 131   V(Parameter)                                 \
 132   V(Power)                                     \
 133   V(PushArguments)                             \
 134   V(RegExpLiteral)                             \
 135   V(Return)                                    \
 136   V(Ror)                                       \
 137   V(Sar)                                       \
 138   V(SeqStringGetChar)                          \
 139   V(SeqStringSetChar)                          \
 140   V(Shl)                                       \
 141   V(Shr)                                       \
 142   V(Simulate)                                  \
 143   V(StackCheck)                                \
 144   V(StoreCodeEntry)                            \
 145   V(StoreContextSlot)                          \
 146   V(StoreFrameContext)                         \
 147   V(StoreGlobalCell)                           \
 148   V(StoreKeyed)                                \
 149   V(StoreKeyedGeneric)                         \
 150   V(StoreNamedField)                           \
 151   V(StoreNamedGeneric)                         \
 152   V(StringAdd)                                 \
 153   V(StringCharCodeAt)                          \
 154   V(StringCharFromCode)                        \
 155   V(StringCompareAndBranch)                    \
 156   V(Sub)                                       \
 157   V(ThisFunction)                              \
 158   V(ToFastProperties)                          \
 159   V(TransitionElementsKind)                    \
 160   V(TrapAllocationMemento)                     \
 161   V(Typeof)                                    \
 162   V(TypeofIsAndBranch)                         \
 163   V(UnaryMathOperation)                        \
 164   V(UnknownOSRValue)                           \
 165   V(UseConst)                                  \
 166   V(WrapReceiver)
 167
 168 #define GVN_TRACKED_FLAG_LIST(V)               \
 169   V(NewSpacePromotion)
 170
 171 #define GVN_UNTRACKED_FLAG_LIST(V)             \
 172   V(ArrayElements)                             \
 173   V(ArrayLengths)                              \
 174   V(StringLengths)                             \
 175   V(BackingStoreFields)                        \
 176   V(Calls)                                     \
 177   V(ContextSlots)                              \
 178   V(DoubleArrayElements)                       \
 179   V(DoubleFields)                              \
 180   V(ElementsKind)                              \
 181   V(ElementsPointer)                           \
 182   V(GlobalVars)                                \
 183   V(InobjectFields)                            \
 184   V(Maps)                                      \
 185   V(OsrEntries)                                \
 186   V(ExternalMemory)                            \
 187   V(StringChars)                               \
 188   V(TypedArrayElements)
 189
 190
 191 #define DECLARE_ABSTRACT_INSTRUCTION(type)                              \
 192   virtual bool Is##type() const V8_FINAL V8_OVERRIDE { return true; }   \
 193   static H##type* cast(HValue* value) {                                 \
 194     DCHECK(value->Is##type());                                          \
 195     return reinterpret_cast<H##type*>(value);                           \
 196   }
 197
 198
 199 #define DECLARE_CONCRETE_INSTRUCTION(type)              \
 200   virtual LInstruction* CompileToLithium(               \
 201      LChunkBuilder* builder) V8_FINAL V8_OVERRIDE;      \
 202   static H##type* cast(HValue* value) {                 \
 203     DCHECK(value->Is##type());                          \
 204     return reinterpret_cast<H##type*>(value);           \
 205   }                                                     \
 206   virtual Opcode opcode() const V8_FINAL V8_OVERRIDE {  \
 207     return HValue::k##type;                             \
 208   }
 209
 210
 211 enum PropertyAccessType { LOAD, STORE };
 212
 213
 214 class Range V8_FINAL : public ZoneObject {
 215  public:
 216   Range()
 217       : lower_(kMinInt),
 218         upper_(kMaxInt),
 219         next_(NULL),
 220         can_be_minus_zero_(false) { }
 221
 222   Range(int32_t lower, int32_t upper)
 223       : lower_(lower),
 224         upper_(upper),
 225         next_(NULL),
 226         can_be_minus_zero_(false) { }
 227
 228   int32_t upper() const { return upper_; }
 229   int32_t lower() const { return lower_; }
 230   Range* next() const { return next_; }
 231   Range* CopyClearLower(Zone* zone) const {
 232     return new(zone) Range(kMinInt, upper_);
 233   }
 234   Range* CopyClearUpper(Zone* zone) const {
 235     return new(zone) Range(lower_, kMaxInt);
 236   }
 237   Range* Copy(Zone* zone) const {
 238     Range* result = new(zone) Range(lower_, upper_);
 239     result->set_can_be_minus_zero(CanBeMinusZero());
 240     return result;
 241   }
 242   int32_t Mask() const;
 243   void set_can_be_minus_zero(bool b) { can_be_minus_zero_ = b; }
 244   bool CanBeMinusZero() const { return CanBeZero() && can_be_minus_zero_; }
 245   bool CanBeZero() const { return upper_ >= 0 && lower_ <= 0; }
 246   bool CanBeNegative() const { return lower_ < 0; }
 247   bool CanBePositive() const { return upper_ > 0; }
 248   bool Includes(int value) const { return lower_ <= value && upper_ >= value; }
 249   bool IsMostGeneric() const {
 250     return lower_ == kMinInt && upper_ == kMaxInt && CanBeMinusZero();
 251   }
 252   bool IsInSmiRange() const {
 253     return lower_ >= Smi::kMinValue && upper_ <= Smi::kMaxValue;
 254   }
 255   void ClampToSmi() {
 256     lower_ = Max(lower_, Smi::kMinValue);
 257     upper_ = Min(upper_, Smi::kMaxValue);
 258   }
 259   void KeepOrder();
 260 #ifdef DEBUG
 261   void Verify() const;
 262 #endif
 263
 264   void StackUpon(Range* other) {
 265     Intersect(other);
 266     next_ = other;
 267   }
 268
 269   void Intersect(Range* other);
 270   void Union(Range* other);
 271   void CombinedMax(Range* other);
 272   void CombinedMin(Range* other);
 273
 274   void AddConstant(int32_t value);
 275   void Sar(int32_t value);
 276   void Shl(int32_t value);
 277   bool AddAndCheckOverflow(const Representation& r, Range* other);
 278   bool SubAndCheckOverflow(const Representation& r, Range* other);
 279   bool MulAndCheckOverflow(const Representation& r, Range* other);
 280
 281  private:
 282   int32_t lower_;
 283   int32_t upper_;
 284   Range* next_;
 285   bool can_be_minus_zero_;
 286 };
 287
 288
 289 class HUseListNode: public ZoneObject {
 290  public:
 291   HUseListNode(HValue* value, int index, HUseListNode* tail)
 292       : tail_(tail), value_(value), index_(index) {
 293   }
 294
 295   HUseListNode* tail();
 296   HValue* value() const { return value_; }
 297   int index() const { return index_; }
 298
 299   void set_tail(HUseListNode* list) { tail_ = list; }
 300
 301 #ifdef DEBUG
 302   void Zap() {
 303     tail_ = reinterpret_cast<HUseListNode*>(1);
 304     value_ = NULL;
 305     index_ = -1;
 306   }
 307 #endif
 308
 309  private:
 310   HUseListNode* tail_;
 311   HValue* value_;
 312   int index_;
 313 };
 314
 315
 316 // We reuse use list nodes behind the scenes as uses are added and deleted.
 317 // This class is the safe way to iterate uses while deleting them.
 318 class HUseIterator V8_FINAL BASE_EMBEDDED {
 319  public:
 320   bool Done() { return current_ == NULL; }
 321   void Advance();
 322
 323   HValue* value() {
 324     DCHECK(!Done());
 325     return value_;
 326   }
 327
 328   int index() {
 329     DCHECK(!Done());
 330     return index_;
 331   }
 332
 333  private:
 334   explicit HUseIterator(HUseListNode* head);
 335
 336   HUseListNode* current_;
 337   HUseListNode* next_;
 338   HValue* value_;
 339   int index_;
 340
 341   friend class HValue;
 342 };
 343
 344
 345 // All tracked flags should appear before untracked ones.
 346 enum GVNFlag {
 347   // Declare global value numbering flags.
 348 #define DECLARE_FLAG(Type) k##Type,
 349   GVN_TRACKED_FLAG_LIST(DECLARE_FLAG)
 350   GVN_UNTRACKED_FLAG_LIST(DECLARE_FLAG)
 351 #undef DECLARE_FLAG
 352 #define COUNT_FLAG(Type) + 1
 353   kNumberOfTrackedSideEffects = 0 GVN_TRACKED_FLAG_LIST(COUNT_FLAG),
 354   kNumberOfUntrackedSideEffects = 0 GVN_UNTRACKED_FLAG_LIST(COUNT_FLAG),
 355 #undef COUNT_FLAG
 356   kNumberOfFlags = kNumberOfTrackedSideEffects + kNumberOfUntrackedSideEffects
 357 };
 358
 359
 360 static inline GVNFlag GVNFlagFromInt(int i) {
 361   DCHECK(i >= 0);
 362   DCHECK(i < kNumberOfFlags);
 363   return static_cast<GVNFlag>(i);
 364 }
 365
 366
 367 class DecompositionResult V8_FINAL BASE_EMBEDDED {
 368  public:
 369   DecompositionResult() : base_(NULL), offset_(0), scale_(0) {}
 370
 371   HValue* base() { return base_; }
 372   int offset() { return offset_; }
 373   int scale() { return scale_; }
 374
 375   bool Apply(HValue* other_base, int other_offset, int other_scale = 0) {
 376     if (base_ == NULL) {
 377       base_ = other_base;
 378       offset_ = other_offset;
 379       scale_ = other_scale;
 380       return true;
 381     } else {
 382       if (scale_ == 0) {
 383         base_ = other_base;
 384         offset_ += other_offset;
 385         scale_ = other_scale;
 386         return true;
 387       } else {
 388         return false;
 389       }
 390     }
 391   }
 392
 393   void SwapValues(HValue** other_base, int* other_offset, int* other_scale) {
 394     swap(&base_, other_base);
 395     swap(&offset_, other_offset);
 396     swap(&scale_, other_scale);
 397   }
 398
 399  private:
 400   template <class T> void swap(T* a, T* b) {
 401     T c(*a);
 402     *a = *b;
 403     *b = c;
 404   }
 405
 406   HValue* base_;
 407   int offset_;
 408   int scale_;
 409 };
 410
 411
 412 typedef EnumSet<GVNFlag, int32_t> GVNFlagSet;
 413
 414
 415 // This class encapsulates encoding and decoding of sources positions from
 416 // which hydrogen values originated.
 417 // When FLAG_track_hydrogen_positions is set this object encodes the
 418 // identifier of the inlining and absolute offset from the start of the
 419 // inlined function.
 420 // When the flag is not set we simply track absolute offset from the
 421 // script start.
 422 class HSourcePosition {
 423  public:
 424   HSourcePosition(const HSourcePosition& other) : value_(other.value_) { }
 425
 426   static HSourcePosition Unknown() {
 427     return HSourcePosition(RelocInfo::kNoPosition);
 428   }
 429
 430   bool IsUnknown() const { return value_ == RelocInfo::kNoPosition; }
 431
 432   int position() const { return PositionField::decode(value_); }
 433   void set_position(int position) {
 434     if (FLAG_hydrogen_track_positions) {
 435       value_ = static_cast<int>(PositionField::update(value_, position));
 436     } else {
 437       value_ = position;
 438     }
 439   }
 440
 441   int inlining_id() const { return InliningIdField::decode(value_); }
 442   void set_inlining_id(int inlining_id) {
 443     if (FLAG_hydrogen_track_positions) {
 444       value_ = static_cast<int>(InliningIdField::update(value_, inlining_id));
 445     }
 446   }
 447
 448   int raw() const { return value_; }
 449
 450  private:
 451   typedef BitField<int, 0, 9> InliningIdField;
 452
 453   // Offset from the start of the inlined function.
 454   typedef BitField<int, 9, 23> PositionField;
 455
 456   // On HPositionInfo can use this constructor.
 457   explicit HSourcePosition(int value) : value_(value) { }
 458
 459   friend class HPositionInfo;
 460
 461   // If FLAG_hydrogen_track_positions is set contains bitfields InliningIdField
 462   // and PositionField.
 463   // Otherwise contains absolute offset from the script start.
 464   int value_;
 465 };
 466
 467
 468 OStream& operator<<(OStream& os, const HSourcePosition& p);
 469
 470
 471 class HValue : public ZoneObject {
 472  public:
 473   static const int kNoNumber = -1;
 474
 475   enum Flag {
 476     kFlexibleRepresentation,
 477     kCannotBeTagged,
 478     // Participate in Global Value Numbering, i.e. elimination of
 479     // unnecessary recomputations. If an instruction sets this flag, it must
 480     // implement DataEquals(), which will be used to determine if other
 481     // occurrences of the instruction are indeed the same.
 482     kUseGVN,
 483     // Track instructions that are dominating side effects. If an instruction
 484     // sets this flag, it must implement HandleSideEffectDominator() and should
 485     // indicate which side effects to track by setting GVN flags.
 486     kTrackSideEffectDominators,
 487     kCanOverflow,
 488     kBailoutOnMinusZero,
 489     kCanBeDivByZero,
 490     kLeftCanBeMinInt,
 491     kLeftCanBeNegative,
 492     kLeftCanBePositive,
 493     kAllowUndefinedAsNaN,
 494     kIsArguments,
 495     kTruncatingToInt32,
 496     kAllUsesTruncatingToInt32,
 497     kTruncatingToSmi,
 498     kAllUsesTruncatingToSmi,
 499     // Set after an instruction is killed.
 500     kIsDead,
 501     // Instructions that are allowed to produce full range unsigned integer
 502     // values are marked with kUint32 flag. If arithmetic shift or a load from
 503     // EXTERNAL_UINT32_ELEMENTS array is not marked with this flag
 504     // it will deoptimize if result does not fit into signed integer range.
 505     // HGraph::ComputeSafeUint32Operations is responsible for setting this
 506     // flag.
 507     kUint32,
 508     kHasNoObservableSideEffects,
 509     // Indicates an instruction shouldn't be replaced by optimization, this flag
 510     // is useful to set in cases where recomputing a value is cheaper than
 511     // extending the value's live range and spilling it.
 512     kCantBeReplaced,
 513     // Indicates the instruction is live during dead code elimination.
 514     kIsLive,
 515
 516     // HEnvironmentMarkers are deleted before dead code
 517     // elimination takes place, so they can repurpose the kIsLive flag:
 518     kEndsLiveRange = kIsLive,
 519
 520     // TODO(everyone): Don't forget to update this!
 521     kLastFlag = kIsLive
 522   };
 523
 524   STATIC_ASSERT(kLastFlag < kBitsPerInt);
 525
 526   static HValue* cast(HValue* value) { return value; }
 527
 528   enum Opcode {
 529     // Declare a unique enum value for each hydrogen instruction.
 530   #define DECLARE_OPCODE(type) k##type,
 531     HYDROGEN_CONCRETE_INSTRUCTION_LIST(DECLARE_OPCODE)
 532     kPhi
 533   #undef DECLARE_OPCODE
 534   };
 535   virtual Opcode opcode() const = 0;
 536
 537   // Declare a non-virtual predicates for each concrete HInstruction or HValue.
 538   #define DECLARE_PREDICATE(type) \
 539     bool Is##type() const { return opcode() == k##type; }
 540     HYDROGEN_CONCRETE_INSTRUCTION_LIST(DECLARE_PREDICATE)
 541   #undef DECLARE_PREDICATE
 542     bool IsPhi() const { return opcode() == kPhi; }
 543
 544   // Declare virtual predicates for abstract HInstruction or HValue
 545   #define DECLARE_PREDICATE(type) \
 546     virtual bool Is##type() const { return false; }
 547     HYDROGEN_ABSTRACT_INSTRUCTION_LIST(DECLARE_PREDICATE)
 548   #undef DECLARE_PREDICATE
 549
 550   bool IsBitwiseBinaryShift() {
 551     return IsShl() || IsShr() || IsSar();
 552   }
 553
 554   explicit HValue(HType type = HType::Tagged())
 555       : block_(NULL),
 556         id_(kNoNumber),
 557         type_(type),
 558         use_list_(NULL),
 559         range_(NULL),
 560 #ifdef DEBUG
 561         range_poisoned_(false),
 562 #endif
 563         flags_(0) {}
 564   virtual ~HValue() {}
 565
 566   virtual HSourcePosition position() const {
 567     return HSourcePosition::Unknown();
 568   }
 569   virtual HSourcePosition operand_position(int index) const {
 570     return position();
 571   }
 572
 573   HBasicBlock* block() const { return block_; }
 574   void SetBlock(HBasicBlock* block);
 575
 576   // Note: Never call this method for an unlinked value.
 577   Isolate* isolate() const;
 578
 579   int id() const { return id_; }
 580   void set_id(int id) { id_ = id; }
 581
 582   HUseIterator uses() const { return HUseIterator(use_list_); }
 583
 584   virtual bool EmitAtUses() { return false; }
 585
 586   Representation representation() const { return representation_; }
 587   void ChangeRepresentation(Representation r) {
 588     DCHECK(CheckFlag(kFlexibleRepresentation));
 589     DCHECK(!CheckFlag(kCannotBeTagged) || !r.IsTagged());
 590     RepresentationChanged(r);
 591     representation_ = r;
 592     if (r.IsTagged()) {
 593       // Tagged is the bottom of the lattice, don't go any further.
 594       ClearFlag(kFlexibleRepresentation);
 595     }
 596   }
 597   virtual void AssumeRepresentation(Representation r);
 598
 599   virtual Representation KnownOptimalRepresentation() {
 600     Representation r = representation();
 601     if (r.IsTagged()) {
 602       HType t = type();
 603       if (t.IsSmi()) return Representation::Smi();
 604       if (t.IsHeapNumber()) return Representation::Double();
 605       if (t.IsHeapObject()) return r;
 606       return Representation::None();
 607     }
 608     return r;
 609   }
 610
 611   HType type() const { return type_; }
 612   void set_type(HType new_type) {
 613     DCHECK(new_type.IsSubtypeOf(type_));
 614     type_ = new_type;
 615   }
 616
 617   // There are HInstructions that do not really change a value, they
 618   // only add pieces of information to it (like bounds checks, map checks,
 619   // smi checks...).
 620   // We call these instructions "informative definitions", or "iDef".
 621   // One of the iDef operands is special because it is the value that is
 622   // "transferred" to the output, we call it the "redefined operand".
 623   // If an HValue is an iDef it must override RedefinedOperandIndex() so that
 624   // it does not return kNoRedefinedOperand;
 625   static const int kNoRedefinedOperand = -1;
 626   virtual int RedefinedOperandIndex() { return kNoRedefinedOperand; }
 627   bool IsInformativeDefinition() {
 628     return RedefinedOperandIndex() != kNoRedefinedOperand;
 629   }
 630   HValue* RedefinedOperand() {
 631     int index = RedefinedOperandIndex();
 632     return index == kNoRedefinedOperand ? NULL : OperandAt(index);
 633   }
 634
 635   bool CanReplaceWithDummyUses();
 636
 637   virtual int argument_delta() const { return 0; }
 638
 639   // A purely informative definition is an idef that will not emit code and
 640   // should therefore be removed from the graph in the RestoreActualValues
 641   // phase (so that live ranges will be shorter).
 642   virtual bool IsPurelyInformativeDefinition() { return false; }
 643
 644   // This method must always return the original HValue SSA definition,
 645   // regardless of any chain of iDefs of this value.
 646   HValue* ActualValue() {
 647     HValue* value = this;
 648     int index;
 649     while ((index = value->RedefinedOperandIndex()) != kNoRedefinedOperand) {
 650       value = value->OperandAt(index);
 651     }
 652     return value;
 653   }
 654
 655   bool IsInteger32Constant();
 656   int32_t GetInteger32Constant();
 657   bool EqualsInteger32Constant(int32_t value);
 658
 659   bool IsDefinedAfter(HBasicBlock* other) const;
 660
 661   // Operands.
 662   virtual int OperandCount() const = 0;
 663   virtual HValue* OperandAt(int index) const = 0;
 664   void SetOperandAt(int index, HValue* value);
 665
 666   void DeleteAndReplaceWith(HValue* other);
 667   void ReplaceAllUsesWith(HValue* other);
 668   bool HasNoUses() const { return use_list_ == NULL; }
 669   bool HasOneUse() const {
 670     return use_list_ != NULL && use_list_->tail() == NULL;
 671   }
 672   bool HasMultipleUses() const {
 673     return use_list_ != NULL && use_list_->tail() != NULL;
 674   }
 675   int UseCount() const;
 676
 677   // Mark this HValue as dead and to be removed from other HValues' use lists.
 678   void Kill();
 679
 680   int flags() const { return flags_; }
 681   void SetFlag(Flag f) { flags_ |= (1 << f); }
 682   void ClearFlag(Flag f) { flags_ &= ~(1 << f); }
 683   bool CheckFlag(Flag f) const { return (flags_ & (1 << f)) != 0; }
 684   void CopyFlag(Flag f, HValue* other) {
 685     if (other->CheckFlag(f)) SetFlag(f);
 686   }
 687
 688   // Returns true if the flag specified is set for all uses, false otherwise.
 689   bool CheckUsesForFlag(Flag f) const;
 690   // Same as before and the first one without the flag is returned in value.
 691   bool CheckUsesForFlag(Flag f, HValue** value) const;
 692   // Returns true if the flag specified is set for all uses, and this set
 693   // of uses is non-empty.
 694   bool HasAtLeastOneUseWithFlagAndNoneWithout(Flag f) const;
 695
 696   GVNFlagSet ChangesFlags() const { return changes_flags_; }
 697   GVNFlagSet DependsOnFlags() const { return depends_on_flags_; }
 698   void SetChangesFlag(GVNFlag f) { changes_flags_.Add(f); }
 699   void SetDependsOnFlag(GVNFlag f) { depends_on_flags_.Add(f); }
 700   void ClearChangesFlag(GVNFlag f) { changes_flags_.Remove(f); }
 701   void ClearDependsOnFlag(GVNFlag f) { depends_on_flags_.Remove(f); }
 702   bool CheckChangesFlag(GVNFlag f) const {
 703     return changes_flags_.Contains(f);
 704   }
 705   bool CheckDependsOnFlag(GVNFlag f) const {
 706     return depends_on_flags_.Contains(f);
 707   }
 708   void SetAllSideEffects() { changes_flags_.Add(AllSideEffectsFlagSet()); }
 709   void ClearAllSideEffects() {
 710     changes_flags_.Remove(AllSideEffectsFlagSet());
 711   }
 712   bool HasSideEffects() const {
 713     return changes_flags_.ContainsAnyOf(AllSideEffectsFlagSet());
 714   }
 715   bool HasObservableSideEffects() const {
 716     return !CheckFlag(kHasNoObservableSideEffects) &&
 717         changes_flags_.ContainsAnyOf(AllObservableSideEffectsFlagSet());
 718   }
 719
 720   GVNFlagSet SideEffectFlags() const {
 721     GVNFlagSet result = ChangesFlags();
 722     result.Intersect(AllSideEffectsFlagSet());
 723     return result;
 724   }
 725
 726   GVNFlagSet ObservableChangesFlags() const {
 727     GVNFlagSet result = ChangesFlags();
 728     result.Intersect(AllObservableSideEffectsFlagSet());
 729     return result;
 730   }
 731
 732   Range* range() const {
 733     DCHECK(!range_poisoned_);
 734     return range_;
 735   }
 736   bool HasRange() const {
 737     DCHECK(!range_poisoned_);
 738     return range_ != NULL;
 739   }
 740 #ifdef DEBUG
 741   void PoisonRange() { range_poisoned_ = true; }
 742 #endif
 743   void AddNewRange(Range* r, Zone* zone);
 744   void RemoveLastAddedRange();
 745   void ComputeInitialRange(Zone* zone);
 746
 747   // Escape analysis helpers.
 748   virtual bool HasEscapingOperandAt(int index) { return true; }
 749   virtual bool HasOutOfBoundsAccess(int size) { return false; }
 750
 751   // Representation helpers.
 752   virtual Representation observed_input_representation(int index) {
 753     return Representation::None();
 754   }
 755   virtual Representation RequiredInputRepresentation(int index) = 0;
 756   virtual void InferRepresentation(HInferRepresentationPhase* h_infer);
 757
 758   // This gives the instruction an opportunity to replace itself with an
 759   // instruction that does the same in some better way.  To replace an
 760   // instruction with a new one, first add the new instruction to the graph,
 761   // then return it.  Return NULL to have the instruction deleted.
 762   virtual HValue* Canonicalize() { return this; }
 763
 764   bool Equals(HValue* other);
 765   virtual intptr_t Hashcode();
 766
 767   // Compute unique ids upfront that is safe wrt GC and concurrent compilation.
 768   virtual void FinalizeUniqueness() { }
 769
 770   // Printing support.
 771   virtual OStream& PrintTo(OStream& os) const = 0;  // NOLINT
 772
 773   const char* Mnemonic() const;
 774
 775   // Type information helpers.
 776   bool HasMonomorphicJSObjectType();
 777
 778   // TODO(mstarzinger): For now instructions can override this function to
 779   // specify statically known types, once HType can convey more information
 780   // it should be based on the HType.
 781   virtual Handle<Map> GetMonomorphicJSObjectMap() { return Handle<Map>(); }
 782
 783   // Updated the inferred type of this instruction and returns true if
 784   // it has changed.
 785   bool UpdateInferredType();
 786
 787   virtual HType CalculateInferredType();
 788
 789   // This function must be overridden for instructions which have the
 790   // kTrackSideEffectDominators flag set, to track instructions that are
 791   // dominating side effects.
 792   // It returns true if it removed an instruction which had side effects.
 793   virtual bool HandleSideEffectDominator(GVNFlag side_effect,
 794                                          HValue* dominator) {
 795     UNREACHABLE();
 796     return false;
 797   }
 798
 799   // Check if this instruction has some reason that prevents elimination.
 800   bool CannotBeEliminated() const {
 801     return HasObservableSideEffects() || !IsDeletable();
 802   }
 803
 804 #ifdef DEBUG
 805   virtual void Verify() = 0;
 806 #endif
 807
 808   virtual bool TryDecompose(DecompositionResult* decomposition) {
 809     if (RedefinedOperand() != NULL) {
 810       return RedefinedOperand()->TryDecompose(decomposition);
 811     } else {
 812       return false;
 813     }
 814   }
 815
 816   // Returns true conservatively if the program might be able to observe a
 817   // ToString() operation on this value.
 818   bool ToStringCanBeObserved() const {
 819     return ToStringOrToNumberCanBeObserved();
 820   }
 821
 822   // Returns true conservatively if the program might be able to observe a
 823   // ToNumber() operation on this value.
 824   bool ToNumberCanBeObserved() const {
 825     return ToStringOrToNumberCanBeObserved();
 826   }
 827
 828   MinusZeroMode GetMinusZeroMode() {
 829     return CheckFlag(kBailoutOnMinusZero)
 830         ? FAIL_ON_MINUS_ZERO : TREAT_MINUS_ZERO_AS_ZERO;
 831   }
 832
 833  protected:
 834   // This function must be overridden for instructions with flag kUseGVN, to
 835   // compare the non-Operand parts of the instruction.
 836   virtual bool DataEquals(HValue* other) {
 837     UNREACHABLE();
 838     return false;
 839   }
 840
 841   bool ToStringOrToNumberCanBeObserved() const {
 842     if (type().IsTaggedPrimitive()) return false;
 843     if (type().IsJSObject()) return true;
 844     return !representation().IsSmiOrInteger32() && !representation().IsDouble();
 845   }
 846
 847   virtual Representation RepresentationFromInputs() {
 848     return representation();
 849   }
 850   virtual Representation RepresentationFromUses();
 851   Representation RepresentationFromUseRequirements();
 852   bool HasNonSmiUse();
 853   virtual void UpdateRepresentation(Representation new_rep,
 854                                     HInferRepresentationPhase* h_infer,
 855                                     const char* reason);
 856   void AddDependantsToWorklist(HInferRepresentationPhase* h_infer);
 857
 858   virtual void RepresentationChanged(Representation to) { }
 859
 860   virtual Range* InferRange(Zone* zone);
 861   virtual void DeleteFromGraph() = 0;
 862   virtual void InternalSetOperandAt(int index, HValue* value) = 0;
 863   void clear_block() {
 864     DCHECK(block_ != NULL);
 865     block_ = NULL;
 866   }
 867
 868   void set_representation(Representation r) {
 869     DCHECK(representation_.IsNone() && !r.IsNone());
 870     representation_ = r;
 871   }
 872
 873   static GVNFlagSet AllFlagSet() {
 874     GVNFlagSet result;
 875 #define ADD_FLAG(Type) result.Add(k##Type);
 876   GVN_TRACKED_FLAG_LIST(ADD_FLAG)
 877   GVN_UNTRACKED_FLAG_LIST(ADD_FLAG)
 878 #undef ADD_FLAG
 879     return result;
 880   }
 881
 882   // A flag mask to mark an instruction as having arbitrary side effects.
 883   static GVNFlagSet AllSideEffectsFlagSet() {
 884     GVNFlagSet result = AllFlagSet();
 885     result.Remove(kOsrEntries);
 886     return result;
 887   }
 888   friend OStream& operator<<(OStream& os, const ChangesOf& v);
 889
 890   // A flag mask of all side effects that can make observable changes in
 891   // an executing program (i.e. are not safe to repeat, move or remove);
 892   static GVNFlagSet AllObservableSideEffectsFlagSet() {
 893     GVNFlagSet result = AllFlagSet();
 894     result.Remove(kNewSpacePromotion);
 895     result.Remove(kElementsKind);
 896     result.Remove(kElementsPointer);
 897     result.Remove(kMaps);
 898     return result;
 899   }
 900
 901   // Remove the matching use from the use list if present.  Returns the
 902   // removed list node or NULL.
 903   HUseListNode* RemoveUse(HValue* value, int index);
 904
 905   void RegisterUse(int index, HValue* new_value);
 906
 907   HBasicBlock* block_;
 908
 909   // The id of this instruction in the hydrogen graph, assigned when first
 910   // added to the graph. Reflects creation order.
 911   int id_;
 912
 913   Representation representation_;
 914   HType type_;
 915   HUseListNode* use_list_;
 916   Range* range_;
 917 #ifdef DEBUG
 918   bool range_poisoned_;
 919 #endif
 920   int flags_;
 921   GVNFlagSet changes_flags_;
 922   GVNFlagSet depends_on_flags_;
 923
 924  private:
 925   virtual bool IsDeletable() const { return false; }
 926
 927   DISALLOW_COPY_AND_ASSIGN(HValue);
 928 };
 929
 930 // Support for printing various aspects of an HValue.
 931 struct NameOf {
 932   explicit NameOf(const HValue* const v) : value(v) {}
 933   const HValue* value;
 934 };
 935
 936
 937 struct TypeOf {
 938   explicit TypeOf(const HValue* const v) : value(v) {}
 939   const HValue* value;
 940 };
 941
 942
 943 struct ChangesOf {
 944   explicit ChangesOf(const HValue* const v) : value(v) {}
 945   const HValue* value;
 946 };
 947
 948
 949 OStream& operator<<(OStream& os, const HValue& v);
 950 OStream& operator<<(OStream& os, const NameOf& v);
 951 OStream& operator<<(OStream& os, const TypeOf& v);
 952 OStream& operator<<(OStream& os, const ChangesOf& v);
 953
 954
 955 #define DECLARE_INSTRUCTION_FACTORY_P0(I)                                      \
 956   static I* New(Zone* zone, HValue* context) {                                 \
 957     return new(zone) I();                                                      \
 958 }
 959
 960 #define DECLARE_INSTRUCTION_FACTORY_P1(I, P1)                                  \
 961   static I* New(Zone* zone, HValue* context, P1 p1) {                          \
 962     return new(zone) I(p1);                                                    \
 963   }
 964
 965 #define DECLARE_INSTRUCTION_FACTORY_P2(I, P1, P2)                              \
 966   static I* New(Zone* zone, HValue* context, P1 p1, P2 p2) {                   \
 967     return new(zone) I(p1, p2);                                                \
 968   }
 969
 970 #define DECLARE_INSTRUCTION_FACTORY_P3(I, P1, P2, P3)                          \
 971   static I* New(Zone* zone, HValue* context, P1 p1, P2 p2, P3 p3) {            \
 972     return new(zone) I(p1, p2, p3);                                            \
 973   }
 974
 975 #define DECLARE_INSTRUCTION_FACTORY_P4(I, P1, P2, P3, P4)                      \
 976   static I* New(Zone* zone,                                                    \
 977                 HValue* context,                                               \
 978                 P1 p1,                                                         \
 979                 P2 p2,                                                         \
 980                 P3 p3,                                                         \
 981                 P4 p4) {                                                       \
 982     return new(zone) I(p1, p2, p3, p4);                                        \
 983   }
 984
 985 #define DECLARE_INSTRUCTION_FACTORY_P5(I, P1, P2, P3, P4, P5)                  \
 986   static I* New(Zone* zone,                                                    \
 987                 HValue* context,                                               \
 988                 P1 p1,                                                         \
 989                 P2 p2,                                                         \
 990                 P3 p3,                                                         \
 991                 P4 p4,                                                         \
 992                 P5 p5) {                                                       \
 993     return new(zone) I(p1, p2, p3, p4, p5);                                    \
 994   }
 995
 996 #define DECLARE_INSTRUCTION_FACTORY_P6(I, P1, P2, P3, P4, P5, P6)              \
 997   static I* New(Zone* zone,                                                    \
 998                 HValue* context,                                               \
 999                 P1 p1,                                                         \
1000                 P2 p2,                                                         \
1001                 P3 p3,                                                         \
1002                 P4 p4,                                                         \
1003                 P5 p5,                                                         \
1004                 P6 p6) {                                                       \
1005     return new(zone) I(p1, p2, p3, p4, p5, p6);                                \
1006   }
1007
1008 #define DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P0(I)                         \
1009   static I* New(Zone* zone, HValue* context) {                                 \
1010     return new(zone) I(context);                                               \
1011   }
1012
1013 #define DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P1(I, P1)                     \
1014   static I* New(Zone* zone, HValue* context, P1 p1) {                          \
1015     return new(zone) I(context, p1);                                           \
1016   }
1017
1018 #define DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P2(I, P1, P2)                 \
1019   static I* New(Zone* zone, HValue* context, P1 p1, P2 p2) {                   \
1020     return new(zone) I(context, p1, p2);                                       \
1021   }
1022
1023 #define DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P3(I, P1, P2, P3)             \
1024   static I* New(Zone* zone, HValue* context, P1 p1, P2 p2, P3 p3) {            \
1025     return new(zone) I(context, p1, p2, p3);                                   \
1026   }
1027
1028 #define DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P4(I, P1, P2, P3, P4)         \
1029   static I* New(Zone* zone,                                                    \
1030                 HValue* context,                                               \
1031                 P1 p1,                                                         \
1032                 P2 p2,                                                         \
1033                 P3 p3,                                                         \
1034                 P4 p4) {                                                       \
1035     return new(zone) I(context, p1, p2, p3, p4);                               \
1036   }
1037
1038 #define DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P5(I, P1, P2, P3, P4, P5)     \
1039   static I* New(Zone* zone,                                                    \
1040                 HValue* context,                                               \
1041                 P1 p1,                                                         \
1042                 P2 p2,                                                         \
1043                 P3 p3,                                                         \
1044                 P4 p4,                                                         \
1045                 P5 p5) {                                                       \
1046     return new(zone) I(context, p1, p2, p3, p4, p5);                           \
1047   }
1048
1049
1050 // A helper class to represent per-operand position information attached to
1051 // the HInstruction in the compact form. Uses tagging to distinguish between
1052 // case when only instruction's position is available and case when operands'
1053 // positions are also available.
1054 // In the first case it contains intruction's position as a tagged value.
1055 // In the second case it points to an array which contains instruction's
1056 // position and operands' positions.
1057 class HPositionInfo {
1058  public:
1059   explicit HPositionInfo(int pos) : data_(TagPosition(pos)) { }
1060
1061   HSourcePosition position() const {
1062     if (has_operand_positions()) {
1063       return operand_positions()[kInstructionPosIndex];
1064     }
1065     return HSourcePosition(static_cast<int>(UntagPosition(data_)));
1066   }
1067
1068   void set_position(HSourcePosition pos) {
1069     if (has_operand_positions()) {
1070       operand_positions()[kInstructionPosIndex] = pos;
1071     } else {
1072       data_ = TagPosition(pos.raw());
1073     }
1074   }
1075
1076   void ensure_storage_for_operand_positions(Zone* zone, int operand_count) {
1077     if (has_operand_positions()) {
1078       return;
1079     }
1080
1081     const int length = kFirstOperandPosIndex + operand_count;
1082     HSourcePosition* positions =
1083         zone->NewArray<HSourcePosition>(length);
1084     for (int i = 0; i < length; i++) {
1085       positions[i] = HSourcePosition::Unknown();
1086     }
1087
1088     const HSourcePosition pos = position();
1089     data_ = reinterpret_cast<intptr_t>(positions);
1090     set_position(pos);
1091
1092     DCHECK(has_operand_positions());
1093   }
1094
1095   HSourcePosition operand_position(int idx) const {
1096     if (!has_operand_positions()) {
1097       return position();
1098     }
1099     return *operand_position_slot(idx);
1100   }
1101
1102   void set_operand_position(int idx, HSourcePosition pos) {
1103     *operand_position_slot(idx) = pos;
1104   }
1105
1106  private:
1107   static const intptr_t kInstructionPosIndex = 0;
1108   static const intptr_t kFirstOperandPosIndex = 1;
1109
1110   HSourcePosition* operand_position_slot(int idx) const {
1111     DCHECK(has_operand_positions());
1112     return &(operand_positions()[kFirstOperandPosIndex + idx]);
1113   }
1114
1115   bool has_operand_positions() const {
1116     return !IsTaggedPosition(data_);
1117   }
1118
1119   HSourcePosition* operand_positions() const {
1120     DCHECK(has_operand_positions());
1121     return reinterpret_cast<HSourcePosition*>(data_);
1122   }
1123
1124   static const intptr_t kPositionTag = 1;
1125   static const intptr_t kPositionShift = 1;
1126   static bool IsTaggedPosition(intptr_t val) {
1127     return (val & kPositionTag) != 0;
1128   }
1129   static intptr_t UntagPosition(intptr_t val) {
1130     DCHECK(IsTaggedPosition(val));
1131     return val >> kPositionShift;
1132   }
1133   static intptr_t TagPosition(intptr_t val) {
1134     const intptr_t result = (val << kPositionShift) | kPositionTag;
1135     DCHECK(UntagPosition(result) == val);
1136     return result;
1137   }
1138
1139   intptr_t data_;
1140 };
1141
1142
1143 class HInstruction : public HValue {
1144  public:
1145   HInstruction* next() const { return next_; }
1146   HInstruction* previous() const { return previous_; }
1147
1148   virtual OStream& PrintTo(OStream& os) const V8_OVERRIDE;  // NOLINT
1149   virtual OStream& PrintDataTo(OStream& os) const;          // NOLINT
1150
1151   bool IsLinked() const { return block() != NULL; }
1152   void Unlink();
1153
1154   void InsertBefore(HInstruction* next);
1155
1156   template<class T> T* Prepend(T* instr) {
1157     instr->InsertBefore(this);
1158     return instr;
1159   }
1160
1161   void InsertAfter(HInstruction* previous);
1162
1163   template<class T> T* Append(T* instr) {
1164     instr->InsertAfter(this);
1165     return instr;
1166   }
1167
1168   // The position is a write-once variable.
1169   virtual HSourcePosition position() const V8_OVERRIDE {
1170     return HSourcePosition(position_.position());
1171   }
1172   bool has_position() const {
1173     return !position().IsUnknown();
1174   }
1175   void set_position(HSourcePosition position) {
1176     DCHECK(!has_position());
1177     DCHECK(!position.IsUnknown());
1178     position_.set_position(position);
1179   }
1180
1181   virtual HSourcePosition operand_position(int index) const V8_OVERRIDE {
1182     const HSourcePosition pos = position_.operand_position(index);
1183     return pos.IsUnknown() ? position() : pos;
1184   }
1185   void set_operand_position(Zone* zone, int index, HSourcePosition pos) {
1186     DCHECK(0 <= index && index < OperandCount());
1187     position_.ensure_storage_for_operand_positions(zone, OperandCount());
1188     position_.set_operand_position(index, pos);
1189   }
1190
1191   bool Dominates(HInstruction* other);
1192   bool CanTruncateToSmi() const { return CheckFlag(kTruncatingToSmi); }
1193   bool CanTruncateToInt32() const { return CheckFlag(kTruncatingToInt32); }
1194
1195   virtual LInstruction* CompileToLithium(LChunkBuilder* builder) = 0;
1196
1197 #ifdef DEBUG
1198   virtual void Verify() V8_OVERRIDE;
1199 #endif
1200
1201   bool CanDeoptimize();
1202
1203   virtual bool HasStackCheck() { return false; }
1204
1205   DECLARE_ABSTRACT_INSTRUCTION(Instruction)
1206
1207  protected:
1208   explicit HInstruction(HType type = HType::Tagged())
1209       : HValue(type),
1210         next_(NULL),
1211         previous_(NULL),
1212         position_(RelocInfo::kNoPosition) {
1213     SetDependsOnFlag(kOsrEntries);
1214   }
1215
1216   virtual void DeleteFromGraph() V8_OVERRIDE { Unlink(); }
1217
1218  private:
1219   void InitializeAsFirst(HBasicBlock* block) {
1220     DCHECK(!IsLinked());
1221     SetBlock(block);
1222   }
1223
1224   HInstruction* next_;
1225   HInstruction* previous_;
1226   HPositionInfo position_;
1227
1228   friend class HBasicBlock;
1229 };
1230
1231
1232 template<int V>
1233 class HTemplateInstruction : public HInstruction {
1234  public:
1235   virtual int OperandCount() const V8_FINAL V8_OVERRIDE { return V; }
1236   virtual HValue* OperandAt(int i) const V8_FINAL V8_OVERRIDE {
1237     return inputs_[i];
1238   }
1239
1240  protected:
1241   explicit HTemplateInstruction(HType type = HType::Tagged())
1242       : HInstruction(type) {}
1243
1244   virtual void InternalSetOperandAt(int i, HValue* value) V8_FINAL V8_OVERRIDE {
1245     inputs_[i] = value;
1246   }
1247
1248  private:
1249   EmbeddedContainer<HValue*, V> inputs_;
1250 };
1251
1252
1253 class HControlInstruction : public HInstruction {
1254  public:
1255   virtual HBasicBlock* SuccessorAt(int i) const = 0;
1256   virtual int SuccessorCount() const = 0;
1257   virtual void SetSuccessorAt(int i, HBasicBlock* block) = 0;
1258
1259   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
1260
1261   virtual bool KnownSuccessorBlock(HBasicBlock** block) {
1262     *block = NULL;
1263     return false;
1264   }
1265
1266   HBasicBlock* FirstSuccessor() {
1267     return SuccessorCount() > 0 ? SuccessorAt(0) : NULL;
1268   }
1269   HBasicBlock* SecondSuccessor() {
1270     return SuccessorCount() > 1 ? SuccessorAt(1) : NULL;
1271   }
1272
1273   void Not() {
1274     HBasicBlock* swap = SuccessorAt(0);
1275     SetSuccessorAt(0, SuccessorAt(1));
1276     SetSuccessorAt(1, swap);
1277   }
1278
1279   DECLARE_ABSTRACT_INSTRUCTION(ControlInstruction)
1280 };
1281
1282
1283 class HSuccessorIterator V8_FINAL BASE_EMBEDDED {
1284  public:
1285   explicit HSuccessorIterator(const HControlInstruction* instr)
1286       : instr_(instr), current_(0) {}
1287
1288   bool Done() { return current_ >= instr_->SuccessorCount(); }
1289   HBasicBlock* Current() { return instr_->SuccessorAt(current_); }
1290   void Advance() { current_++; }
1291
1292  private:
1293   const HControlInstruction* instr_;
1294   int current_;
1295 };
1296
1297
1298 template<int S, int V>
1299 class HTemplateControlInstruction : public HControlInstruction {
1300  public:
1301   int SuccessorCount() const V8_OVERRIDE { return S; }
1302   HBasicBlock* SuccessorAt(int i) const V8_OVERRIDE { return successors_[i]; }
1303   void SetSuccessorAt(int i, HBasicBlock* block) V8_OVERRIDE {
1304     successors_[i] = block;
1305   }
1306
1307   int OperandCount() const V8_OVERRIDE { return V; }
1308   HValue* OperandAt(int i) const V8_OVERRIDE { return inputs_[i]; }
1309
1310
1311  protected:
1312   void InternalSetOperandAt(int i, HValue* value) V8_OVERRIDE {
1313     inputs_[i] = value;
1314   }
1315
1316  private:
1317   EmbeddedContainer<HBasicBlock*, S> successors_;
1318   EmbeddedContainer<HValue*, V> inputs_;
1319 };
1320
1321
1322 class HBlockEntry V8_FINAL : public HTemplateInstruction<0> {
1323  public:
1324   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
1325     return Representation::None();
1326   }
1327
1328   DECLARE_CONCRETE_INSTRUCTION(BlockEntry)
1329 };
1330
1331
1332 class HDummyUse V8_FINAL : public HTemplateInstruction<1> {
1333  public:
1334   explicit HDummyUse(HValue* value)
1335       : HTemplateInstruction<1>(HType::Smi()) {
1336     SetOperandAt(0, value);
1337     // Pretend to be a Smi so that the HChange instructions inserted
1338     // before any use generate as little code as possible.
1339     set_representation(Representation::Tagged());
1340   }
1341
1342   HValue* value() const { return OperandAt(0); }
1343
1344   virtual bool HasEscapingOperandAt(int index) V8_OVERRIDE { return false; }
1345   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
1346     return Representation::None();
1347   }
1348
1349   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
1350
1351   DECLARE_CONCRETE_INSTRUCTION(DummyUse);
1352 };
1353
1354
1355 // Inserts an int3/stop break instruction for debugging purposes.
1356 class HDebugBreak V8_FINAL : public HTemplateInstruction<0> {
1357  public:
1358   DECLARE_INSTRUCTION_FACTORY_P0(HDebugBreak);
1359
1360   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
1361     return Representation::None();
1362   }
1363
1364   DECLARE_CONCRETE_INSTRUCTION(DebugBreak)
1365 };
1366
1367
1368 class HGoto V8_FINAL : public HTemplateControlInstruction<1, 0> {
1369  public:
1370   explicit HGoto(HBasicBlock* target) {
1371     SetSuccessorAt(0, target);
1372   }
1373
1374   virtual bool KnownSuccessorBlock(HBasicBlock** block) V8_OVERRIDE {
1375     *block = FirstSuccessor();
1376     return true;
1377   }
1378
1379   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
1380     return Representation::None();
1381   }
1382
1383   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
1384
1385   DECLARE_CONCRETE_INSTRUCTION(Goto)
1386 };
1387
1388
1389 class HDeoptimize V8_FINAL : public HTemplateControlInstruction<1, 0> {
1390  public:
1391   static HDeoptimize* New(Zone* zone,
1392                           HValue* context,
1393                           const char* reason,
1394                           Deoptimizer::BailoutType type,
1395                           HBasicBlock* unreachable_continuation) {
1396     return new(zone) HDeoptimize(reason, type, unreachable_continuation);
1397   }
1398
1399   virtual bool KnownSuccessorBlock(HBasicBlock** block) V8_OVERRIDE {
1400     *block = NULL;
1401     return true;
1402   }
1403
1404   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
1405     return Representation::None();
1406   }
1407
1408   const char* reason() const { return reason_; }
1409   Deoptimizer::BailoutType type() { return type_; }
1410
1411   DECLARE_CONCRETE_INSTRUCTION(Deoptimize)
1412
1413  private:
1414   explicit HDeoptimize(const char* reason,
1415                        Deoptimizer::BailoutType type,
1416                        HBasicBlock* unreachable_continuation)
1417       : reason_(reason), type_(type) {
1418     SetSuccessorAt(0, unreachable_continuation);
1419   }
1420
1421   const char* reason_;
1422   Deoptimizer::BailoutType type_;
1423 };
1424
1425
1426 class HUnaryControlInstruction : public HTemplateControlInstruction<2, 1> {
1427  public:
1428   HUnaryControlInstruction(HValue* value,
1429                            HBasicBlock* true_target,
1430                            HBasicBlock* false_target) {
1431     SetOperandAt(0, value);
1432     SetSuccessorAt(0, true_target);
1433     SetSuccessorAt(1, false_target);
1434   }
1435
1436   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
1437
1438   HValue* value() const { return OperandAt(0); }
1439 };
1440
1441
1442 class HBranch V8_FINAL : public HUnaryControlInstruction {
1443  public:
1444   DECLARE_INSTRUCTION_FACTORY_P1(HBranch, HValue*);
1445   DECLARE_INSTRUCTION_FACTORY_P2(HBranch, HValue*,
1446                                  ToBooleanStub::Types);
1447   DECLARE_INSTRUCTION_FACTORY_P4(HBranch, HValue*,
1448                                  ToBooleanStub::Types,
1449                                  HBasicBlock*, HBasicBlock*);
1450
1451   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
1452     return Representation::None();
1453   }
1454   virtual Representation observed_input_representation(int index) V8_OVERRIDE;
1455
1456   virtual bool KnownSuccessorBlock(HBasicBlock** block) V8_OVERRIDE;
1457
1458   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
1459
1460   ToBooleanStub::Types expected_input_types() const {
1461     return expected_input_types_;
1462   }
1463
1464   DECLARE_CONCRETE_INSTRUCTION(Branch)
1465
1466  private:
1467   HBranch(HValue* value,
1468           ToBooleanStub::Types expected_input_types = ToBooleanStub::Types(),
1469           HBasicBlock* true_target = NULL,
1470           HBasicBlock* false_target = NULL)
1471       : HUnaryControlInstruction(value, true_target, false_target),
1472         expected_input_types_(expected_input_types) {
1473     SetFlag(kAllowUndefinedAsNaN);
1474   }
1475
1476   ToBooleanStub::Types expected_input_types_;
1477 };
1478
1479
1480 class HCompareMap V8_FINAL : public HUnaryControlInstruction {
1481  public:
1482   DECLARE_INSTRUCTION_FACTORY_P2(HCompareMap, HValue*, Handle<Map>);
1483   DECLARE_INSTRUCTION_FACTORY_P4(HCompareMap, HValue*, Handle<Map>,
1484                                  HBasicBlock*, HBasicBlock*);
1485
1486   virtual bool KnownSuccessorBlock(HBasicBlock** block) V8_OVERRIDE {
1487     if (known_successor_index() != kNoKnownSuccessorIndex) {
1488       *block = SuccessorAt(known_successor_index());
1489       return true;
1490     }
1491     *block = NULL;
1492     return false;
1493   }
1494
1495   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
1496
1497   static const int kNoKnownSuccessorIndex = -1;
1498   int known_successor_index() const { return known_successor_index_; }
1499   void set_known_successor_index(int known_successor_index) {
1500     known_successor_index_ = known_successor_index;
1501   }
1502
1503   Unique<Map> map() const { return map_; }
1504   bool map_is_stable() const { return map_is_stable_; }
1505
1506   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
1507     return Representation::Tagged();
1508   }
1509
1510   DECLARE_CONCRETE_INSTRUCTION(CompareMap)
1511
1512  protected:
1513   virtual int RedefinedOperandIndex() { return 0; }
1514
1515  private:
1516   HCompareMap(HValue* value,
1517               Handle<Map> map,
1518               HBasicBlock* true_target = NULL,
1519               HBasicBlock* false_target = NULL)
1520       : HUnaryControlInstruction(value, true_target, false_target),
1521         known_successor_index_(kNoKnownSuccessorIndex),
1522         map_is_stable_(map->is_stable()),
1523         map_(Unique<Map>::CreateImmovable(map)) {
1524     set_representation(Representation::Tagged());
1525   }
1526
1527   int known_successor_index_ : 31;
1528   bool map_is_stable_ : 1;
1529   Unique<Map> map_;
1530 };
1531
1532
1533 class HContext V8_FINAL : public HTemplateInstruction<0> {
1534  public:
1535   static HContext* New(Zone* zone) {
1536     return new(zone) HContext();
1537   }
1538
1539   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
1540     return Representation::None();
1541   }
1542
1543   DECLARE_CONCRETE_INSTRUCTION(Context)
1544
1545  protected:
1546   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
1547
1548  private:
1549   HContext() {
1550     set_representation(Representation::Tagged());
1551     SetFlag(kUseGVN);
1552   }
1553
1554   virtual bool IsDeletable() const V8_OVERRIDE { return true; }
1555 };
1556
1557
1558 class HReturn V8_FINAL : public HTemplateControlInstruction<0, 3> {
1559  public:
1560   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P2(HReturn, HValue*, HValue*);
1561   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P1(HReturn, HValue*);
1562
1563   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
1564     // TODO(titzer): require an Int32 input for faster returns.
1565     if (index == 2) return Representation::Smi();
1566     return Representation::Tagged();
1567   }
1568
1569   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
1570
1571   HValue* value() const { return OperandAt(0); }
1572   HValue* context() const { return OperandAt(1); }
1573   HValue* parameter_count() const { return OperandAt(2); }
1574
1575   DECLARE_CONCRETE_INSTRUCTION(Return)
1576
1577  private:
1578   HReturn(HValue* context, HValue* value, HValue* parameter_count = 0) {
1579     SetOperandAt(0, value);
1580     SetOperandAt(1, context);
1581     SetOperandAt(2, parameter_count);
1582   }
1583 };
1584
1585
1586 class HAbnormalExit V8_FINAL : public HTemplateControlInstruction<0, 0> {
1587  public:
1588   DECLARE_INSTRUCTION_FACTORY_P0(HAbnormalExit);
1589
1590   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
1591     return Representation::None();
1592   }
1593
1594   DECLARE_CONCRETE_INSTRUCTION(AbnormalExit)
1595  private:
1596   HAbnormalExit() {}
1597 };
1598
1599
1600 class HUnaryOperation : public HTemplateInstruction<1> {
1601  public:
1602   explicit HUnaryOperation(HValue* value, HType type = HType::Tagged())
1603       : HTemplateInstruction<1>(type) {
1604     SetOperandAt(0, value);
1605   }
1606
1607   static HUnaryOperation* cast(HValue* value) {
1608     return reinterpret_cast<HUnaryOperation*>(value);
1609   }
1610
1611   HValue* value() const { return OperandAt(0); }
1612   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
1613 };
1614
1615
1616 class HUseConst V8_FINAL : public HUnaryOperation {
1617  public:
1618   DECLARE_INSTRUCTION_FACTORY_P1(HUseConst, HValue*);
1619
1620   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
1621     return Representation::None();
1622   }
1623
1624   DECLARE_CONCRETE_INSTRUCTION(UseConst)
1625
1626  private:
1627     explicit HUseConst(HValue* old_value) : HUnaryOperation(old_value) { }
1628 };
1629
1630
1631 class HForceRepresentation V8_FINAL : public HTemplateInstruction<1> {
1632  public:
1633   static HInstruction* New(Zone* zone, HValue* context, HValue* value,
1634                            Representation required_representation);
1635
1636   HValue* value() const { return OperandAt(0); }
1637
1638   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
1639     return representation();  // Same as the output representation.
1640   }
1641
1642   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
1643
1644   DECLARE_CONCRETE_INSTRUCTION(ForceRepresentation)
1645
1646  private:
1647   HForceRepresentation(HValue* value, Representation required_representation) {
1648     SetOperandAt(0, value);
1649     set_representation(required_representation);
1650   }
1651 };
1652
1653
1654 class HChange V8_FINAL : public HUnaryOperation {
1655  public:
1656   HChange(HValue* value,
1657           Representation to,
1658           bool is_truncating_to_smi,
1659           bool is_truncating_to_int32)
1660       : HUnaryOperation(value) {
1661     DCHECK(!value->representation().IsNone());
1662     DCHECK(!to.IsNone());
1663     DCHECK(!value->representation().Equals(to));
1664     set_representation(to);
1665     SetFlag(kUseGVN);
1666     SetFlag(kCanOverflow);
1667     if (is_truncating_to_smi && to.IsSmi()) {
1668       SetFlag(kTruncatingToSmi);
1669       SetFlag(kTruncatingToInt32);
1670     }
1671     if (is_truncating_to_int32) SetFlag(kTruncatingToInt32);
1672     if (value->representation().IsSmi() || value->type().IsSmi()) {
1673       set_type(HType::Smi());
1674     } else {
1675       set_type(HType::TaggedNumber());
1676       if (to.IsTagged()) SetChangesFlag(kNewSpacePromotion);
1677     }
1678   }
1679
1680   bool can_convert_undefined_to_nan() {
1681     return CheckUsesForFlag(kAllowUndefinedAsNaN);
1682   }
1683
1684   virtual HType CalculateInferredType() V8_OVERRIDE;
1685   virtual HValue* Canonicalize() V8_OVERRIDE;
1686
1687   Representation from() const { return value()->representation(); }
1688   Representation to() const { return representation(); }
1689   bool deoptimize_on_minus_zero() const {
1690     return CheckFlag(kBailoutOnMinusZero);
1691   }
1692   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
1693     return from();
1694   }
1695
1696   virtual Range* InferRange(Zone* zone) V8_OVERRIDE;
1697
1698   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
1699
1700   DECLARE_CONCRETE_INSTRUCTION(Change)
1701
1702  protected:
1703   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
1704
1705  private:
1706   virtual bool IsDeletable() const V8_OVERRIDE {
1707     return !from().IsTagged() || value()->type().IsSmi();
1708   }
1709 };
1710
1711
1712 class HClampToUint8 V8_FINAL : public HUnaryOperation {
1713  public:
1714   DECLARE_INSTRUCTION_FACTORY_P1(HClampToUint8, HValue*);
1715
1716   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
1717     return Representation::None();
1718   }
1719
1720   DECLARE_CONCRETE_INSTRUCTION(ClampToUint8)
1721
1722  protected:
1723   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
1724
1725  private:
1726   explicit HClampToUint8(HValue* value)
1727       : HUnaryOperation(value) {
1728     set_representation(Representation::Integer32());
1729     SetFlag(kAllowUndefinedAsNaN);
1730     SetFlag(kUseGVN);
1731   }
1732
1733   virtual bool IsDeletable() const V8_OVERRIDE { return true; }
1734 };
1735
1736
1737 class HDoubleBits V8_FINAL : public HUnaryOperation {
1738  public:
1739   enum Bits { HIGH, LOW };
1740   DECLARE_INSTRUCTION_FACTORY_P2(HDoubleBits, HValue*, Bits);
1741
1742   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
1743     return Representation::Double();
1744   }
1745
1746   DECLARE_CONCRETE_INSTRUCTION(DoubleBits)
1747
1748   Bits bits() { return bits_; }
1749
1750  protected:
1751   virtual bool DataEquals(HValue* other) V8_OVERRIDE {
1752     return other->IsDoubleBits() && HDoubleBits::cast(other)->bits() == bits();
1753   }
1754
1755  private:
1756   HDoubleBits(HValue* value, Bits bits)
1757       : HUnaryOperation(value), bits_(bits) {
1758     set_representation(Representation::Integer32());
1759     SetFlag(kUseGVN);
1760   }
1761
1762   virtual bool IsDeletable() const V8_OVERRIDE { return true; }
1763
1764   Bits bits_;
1765 };
1766
1767
1768 class HConstructDouble V8_FINAL : public HTemplateInstruction<2> {
1769  public:
1770   DECLARE_INSTRUCTION_FACTORY_P2(HConstructDouble, HValue*, HValue*);
1771
1772   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
1773     return Representation::Integer32();
1774   }
1775
1776   DECLARE_CONCRETE_INSTRUCTION(ConstructDouble)
1777
1778   HValue* hi() { return OperandAt(0); }
1779   HValue* lo() { return OperandAt(1); }
1780
1781  protected:
1782   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
1783
1784  private:
1785   explicit HConstructDouble(HValue* hi, HValue* lo) {
1786     set_representation(Representation::Double());
1787     SetFlag(kUseGVN);
1788     SetOperandAt(0, hi);
1789     SetOperandAt(1, lo);
1790   }
1791
1792   virtual bool IsDeletable() const V8_OVERRIDE { return true; }
1793 };
1794
1795
1796 enum RemovableSimulate {
1797   REMOVABLE_SIMULATE,
1798   FIXED_SIMULATE
1799 };
1800
1801
1802 class HSimulate V8_FINAL : public HInstruction {
1803  public:
1804   HSimulate(BailoutId ast_id,
1805             int pop_count,
1806             Zone* zone,
1807             RemovableSimulate removable)
1808       : ast_id_(ast_id),
1809         pop_count_(pop_count),
1810         values_(2, zone),
1811         assigned_indexes_(2, zone),
1812         zone_(zone),
1813         removable_(removable),
1814         done_with_replay_(false) {}
1815   ~HSimulate() {}
1816
1817   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
1818
1819   bool HasAstId() const { return !ast_id_.IsNone(); }
1820   BailoutId ast_id() const { return ast_id_; }
1821   void set_ast_id(BailoutId id) {
1822     DCHECK(!HasAstId());
1823     ast_id_ = id;
1824   }
1825
1826   int pop_count() const { return pop_count_; }
1827   const ZoneList<HValue*>* values() const { return &values_; }
1828   int GetAssignedIndexAt(int index) const {
1829     DCHECK(HasAssignedIndexAt(index));
1830     return assigned_indexes_[index];
1831   }
1832   bool HasAssignedIndexAt(int index) const {
1833     return assigned_indexes_[index] != kNoIndex;
1834   }
1835   void AddAssignedValue(int index, HValue* value) {
1836     AddValue(index, value);
1837   }
1838   void AddPushedValue(HValue* value) {
1839     AddValue(kNoIndex, value);
1840   }
1841   int ToOperandIndex(int environment_index) {
1842     for (int i = 0; i < assigned_indexes_.length(); ++i) {
1843       if (assigned_indexes_[i] == environment_index) return i;
1844     }
1845     return -1;
1846   }
1847   virtual int OperandCount() const V8_OVERRIDE { return values_.length(); }
1848   virtual HValue* OperandAt(int index) const V8_OVERRIDE {
1849     return values_[index];
1850   }
1851
1852   virtual bool HasEscapingOperandAt(int index) V8_OVERRIDE { return false; }
1853   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
1854     return Representation::None();
1855   }
1856
1857   void MergeWith(ZoneList<HSimulate*>* list);
1858   bool is_candidate_for_removal() { return removable_ == REMOVABLE_SIMULATE; }
1859
1860   // Replay effects of this instruction on the given environment.
1861   void ReplayEnvironment(HEnvironment* env);
1862
1863   DECLARE_CONCRETE_INSTRUCTION(Simulate)
1864
1865 #ifdef DEBUG
1866   virtual void Verify() V8_OVERRIDE;
1867   void set_closure(Handle<JSFunction> closure) { closure_ = closure; }
1868   Handle<JSFunction> closure() const { return closure_; }
1869 #endif
1870
1871  protected:
1872   virtual void InternalSetOperandAt(int index, HValue* value) V8_OVERRIDE {
1873     values_[index] = value;
1874   }
1875
1876  private:
1877   static const int kNoIndex = -1;
1878   void AddValue(int index, HValue* value) {
1879     assigned_indexes_.Add(index, zone_);
1880     // Resize the list of pushed values.
1881     values_.Add(NULL, zone_);
1882     // Set the operand through the base method in HValue to make sure that the
1883     // use lists are correctly updated.
1884     SetOperandAt(values_.length() - 1, value);
1885   }
1886   bool HasValueForIndex(int index) {
1887     for (int i = 0; i < assigned_indexes_.length(); ++i) {
1888       if (assigned_indexes_[i] == index) return true;
1889     }
1890     return false;
1891   }
1892   BailoutId ast_id_;
1893   int pop_count_;
1894   ZoneList<HValue*> values_;
1895   ZoneList<int> assigned_indexes_;
1896   Zone* zone_;
1897   RemovableSimulate removable_ : 2;
1898   bool done_with_replay_ : 1;
1899
1900 #ifdef DEBUG
1901   Handle<JSFunction> closure_;
1902 #endif
1903 };
1904
1905
1906 class HEnvironmentMarker V8_FINAL : public HTemplateInstruction<1> {
1907  public:
1908   enum Kind { BIND, LOOKUP };
1909
1910   DECLARE_INSTRUCTION_FACTORY_P2(HEnvironmentMarker, Kind, int);
1911
1912   Kind kind() const { return kind_; }
1913   int index() const { return index_; }
1914   HSimulate* next_simulate() { return next_simulate_; }
1915   void set_next_simulate(HSimulate* simulate) {
1916     next_simulate_ = simulate;
1917   }
1918
1919   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
1920     return Representation::None();
1921   }
1922
1923   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
1924
1925 #ifdef DEBUG
1926   void set_closure(Handle<JSFunction> closure) {
1927     DCHECK(closure_.is_null());
1928     DCHECK(!closure.is_null());
1929     closure_ = closure;
1930   }
1931   Handle<JSFunction> closure() const { return closure_; }
1932 #endif
1933
1934   DECLARE_CONCRETE_INSTRUCTION(EnvironmentMarker);
1935
1936  private:
1937   HEnvironmentMarker(Kind kind, int index)
1938       : kind_(kind), index_(index), next_simulate_(NULL) { }
1939
1940   Kind kind_;
1941   int index_;
1942   HSimulate* next_simulate_;
1943
1944 #ifdef DEBUG
1945   Handle<JSFunction> closure_;
1946 #endif
1947 };
1948
1949
1950 class HStackCheck V8_FINAL : public HTemplateInstruction<1> {
1951  public:
1952   enum Type {
1953     kFunctionEntry,
1954     kBackwardsBranch
1955   };
1956
1957   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P1(HStackCheck, Type);
1958
1959   HValue* context() { return OperandAt(0); }
1960
1961   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
1962     return Representation::Tagged();
1963   }
1964
1965   void Eliminate() {
1966     // The stack check eliminator might try to eliminate the same stack
1967     // check instruction multiple times.
1968     if (IsLinked()) {
1969       DeleteAndReplaceWith(NULL);
1970     }
1971   }
1972
1973   bool is_function_entry() { return type_ == kFunctionEntry; }
1974   bool is_backwards_branch() { return type_ == kBackwardsBranch; }
1975
1976   DECLARE_CONCRETE_INSTRUCTION(StackCheck)
1977
1978  private:
1979   HStackCheck(HValue* context, Type type) : type_(type) {
1980     SetOperandAt(0, context);
1981     SetChangesFlag(kNewSpacePromotion);
1982   }
1983
1984   Type type_;
1985 };
1986
1987
1988 enum InliningKind {
1989   NORMAL_RETURN,          // Drop the function from the environment on return.
1990   CONSTRUCT_CALL_RETURN,  // Either use allocated receiver or return value.
1991   GETTER_CALL_RETURN,     // Returning from a getter, need to restore context.
1992   SETTER_CALL_RETURN      // Use the RHS of the assignment as the return value.
1993 };
1994
1995
1996 class HArgumentsObject;
1997
1998
1999 class HEnterInlined V8_FINAL : public HTemplateInstruction<0> {
2000  public:
2001   static HEnterInlined* New(Zone* zone,
2002                             HValue* context,
2003                             BailoutId return_id,
2004                             Handle<JSFunction> closure,
2005                             int arguments_count,
2006                             FunctionLiteral* function,
2007                             InliningKind inlining_kind,
2008                             Variable* arguments_var,
2009                             HArgumentsObject* arguments_object) {
2010     return new(zone) HEnterInlined(return_id, closure, arguments_count,
2011                                    function, inlining_kind, arguments_var,
2012                                    arguments_object, zone);
2013   }
2014
2015   void RegisterReturnTarget(HBasicBlock* return_target, Zone* zone);
2016   ZoneList<HBasicBlock*>* return_targets() { return &return_targets_; }
2017
2018   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
2019
2020   Handle<JSFunction> closure() const { return closure_; }
2021   int arguments_count() const { return arguments_count_; }
2022   bool arguments_pushed() const { return arguments_pushed_; }
2023   void set_arguments_pushed() { arguments_pushed_ = true; }
2024   FunctionLiteral* function() const { return function_; }
2025   InliningKind inlining_kind() const { return inlining_kind_; }
2026   BailoutId ReturnId() const { return return_id_; }
2027
2028   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
2029     return Representation::None();
2030   }
2031
2032   Variable* arguments_var() { return arguments_var_; }
2033   HArgumentsObject* arguments_object() { return arguments_object_; }
2034
2035   DECLARE_CONCRETE_INSTRUCTION(EnterInlined)
2036
2037  private:
2038   HEnterInlined(BailoutId return_id,
2039                 Handle<JSFunction> closure,
2040                 int arguments_count,
2041                 FunctionLiteral* function,
2042                 InliningKind inlining_kind,
2043                 Variable* arguments_var,
2044                 HArgumentsObject* arguments_object,
2045                 Zone* zone)
2046       : return_id_(return_id),
2047         closure_(closure),
2048         arguments_count_(arguments_count),
2049         arguments_pushed_(false),
2050         function_(function),
2051         inlining_kind_(inlining_kind),
2052         arguments_var_(arguments_var),
2053         arguments_object_(arguments_object),
2054         return_targets_(2, zone) {
2055   }
2056
2057   BailoutId return_id_;
2058   Handle<JSFunction> closure_;
2059   int arguments_count_;
2060   bool arguments_pushed_;
2061   FunctionLiteral* function_;
2062   InliningKind inlining_kind_;
2063   Variable* arguments_var_;
2064   HArgumentsObject* arguments_object_;
2065   ZoneList<HBasicBlock*> return_targets_;
2066 };
2067
2068
2069 class HLeaveInlined V8_FINAL : public HTemplateInstruction<0> {
2070  public:
2071   HLeaveInlined(HEnterInlined* entry,
2072                 int drop_count)
2073       : entry_(entry),
2074         drop_count_(drop_count) { }
2075
2076   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
2077     return Representation::None();
2078   }
2079
2080   virtual int argument_delta() const V8_OVERRIDE {
2081     return entry_->arguments_pushed() ? -drop_count_ : 0;
2082   }
2083
2084   DECLARE_CONCRETE_INSTRUCTION(LeaveInlined)
2085
2086  private:
2087   HEnterInlined* entry_;
2088   int drop_count_;
2089 };
2090
2091
2092 class HPushArguments V8_FINAL : public HInstruction {
2093  public:
2094   static HPushArguments* New(Zone* zone, HValue* context) {
2095     return new(zone) HPushArguments(zone);
2096   }
2097   static HPushArguments* New(Zone* zone, HValue* context, HValue* arg1) {
2098     HPushArguments* instr = new(zone) HPushArguments(zone);
2099     instr->AddInput(arg1);
2100     return instr;
2101   }
2102   static HPushArguments* New(Zone* zone, HValue* context, HValue* arg1,
2103                              HValue* arg2) {
2104     HPushArguments* instr = new(zone) HPushArguments(zone);
2105     instr->AddInput(arg1);
2106     instr->AddInput(arg2);
2107     return instr;
2108   }
2109   static HPushArguments* New(Zone* zone, HValue* context, HValue* arg1,
2110                              HValue* arg2, HValue* arg3) {
2111     HPushArguments* instr = new(zone) HPushArguments(zone);
2112     instr->AddInput(arg1);
2113     instr->AddInput(arg2);
2114     instr->AddInput(arg3);
2115     return instr;
2116   }
2117   static HPushArguments* New(Zone* zone, HValue* context, HValue* arg1,
2118                              HValue* arg2, HValue* arg3, HValue* arg4) {
2119     HPushArguments* instr = new(zone) HPushArguments(zone);
2120     instr->AddInput(arg1);
2121     instr->AddInput(arg2);
2122     instr->AddInput(arg3);
2123     instr->AddInput(arg4);
2124     return instr;
2125   }
2126
2127   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
2128     return Representation::Tagged();
2129   }
2130
2131   virtual int argument_delta() const V8_OVERRIDE { return inputs_.length(); }
2132   HValue* argument(int i) { return OperandAt(i); }
2133
2134   virtual int OperandCount() const V8_FINAL V8_OVERRIDE {
2135     return inputs_.length();
2136   }
2137   virtual HValue* OperandAt(int i) const V8_FINAL V8_OVERRIDE {
2138     return inputs_[i];
2139   }
2140
2141   void AddInput(HValue* value);
2142
2143   DECLARE_CONCRETE_INSTRUCTION(PushArguments)
2144
2145  protected:
2146   virtual void InternalSetOperandAt(int i, HValue* value) V8_FINAL V8_OVERRIDE {
2147     inputs_[i] = value;
2148   }
2149
2150  private:
2151   explicit HPushArguments(Zone* zone)
2152       : HInstruction(HType::Tagged()), inputs_(4, zone) {
2153     set_representation(Representation::Tagged());
2154   }
2155
2156   ZoneList<HValue*> inputs_;
2157 };
2158
2159
2160 class HThisFunction V8_FINAL : public HTemplateInstruction<0> {
2161  public:
2162   DECLARE_INSTRUCTION_FACTORY_P0(HThisFunction);
2163
2164   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
2165     return Representation::None();
2166   }
2167
2168   DECLARE_CONCRETE_INSTRUCTION(ThisFunction)
2169
2170  protected:
2171   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
2172
2173  private:
2174   HThisFunction() {
2175     set_representation(Representation::Tagged());
2176     SetFlag(kUseGVN);
2177   }
2178
2179   virtual bool IsDeletable() const V8_OVERRIDE { return true; }
2180 };
2181
2182
2183 class HDeclareGlobals V8_FINAL : public HUnaryOperation {
2184  public:
2185   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P2(HDeclareGlobals,
2186                                               Handle<FixedArray>,
2187                                               int);
2188
2189   HValue* context() { return OperandAt(0); }
2190   Handle<FixedArray> pairs() const { return pairs_; }
2191   int flags() const { return flags_; }
2192
2193   DECLARE_CONCRETE_INSTRUCTION(DeclareGlobals)
2194
2195   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
2196     return Representation::Tagged();
2197   }
2198
2199  private:
2200   HDeclareGlobals(HValue* context,
2201                   Handle<FixedArray> pairs,
2202                   int flags)
2203       : HUnaryOperation(context),
2204         pairs_(pairs),
2205         flags_(flags) {
2206     set_representation(Representation::Tagged());
2207     SetAllSideEffects();
2208   }
2209
2210   Handle<FixedArray> pairs_;
2211   int flags_;
2212 };
2213
2214
2215 template <int V>
2216 class HCall : public HTemplateInstruction<V> {
2217  public:
2218   // The argument count includes the receiver.
2219   explicit HCall<V>(int argument_count) : argument_count_(argument_count) {
2220     this->set_representation(Representation::Tagged());
2221     this->SetAllSideEffects();
2222   }
2223
2224   virtual HType CalculateInferredType() V8_FINAL V8_OVERRIDE {
2225     return HType::Tagged();
2226   }
2227
2228   virtual int argument_count() const {
2229     return argument_count_;
2230   }
2231
2232   virtual int argument_delta() const V8_OVERRIDE {
2233     return -argument_count();
2234   }
2235
2236  private:
2237   int argument_count_;
2238 };
2239
2240
2241 class HUnaryCall : public HCall<1> {
2242  public:
2243   HUnaryCall(HValue* value, int argument_count)
2244       : HCall<1>(argument_count) {
2245     SetOperandAt(0, value);
2246   }
2247
2248   virtual Representation RequiredInputRepresentation(
2249       int index) V8_FINAL V8_OVERRIDE {
2250     return Representation::Tagged();
2251   }
2252
2253   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
2254
2255   HValue* value() const { return OperandAt(0); }
2256 };
2257
2258
2259 class HBinaryCall : public HCall<2> {
2260  public:
2261   HBinaryCall(HValue* first, HValue* second, int argument_count)
2262       : HCall<2>(argument_count) {
2263     SetOperandAt(0, first);
2264     SetOperandAt(1, second);
2265   }
2266
2267   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
2268
2269   virtual Representation RequiredInputRepresentation(
2270       int index) V8_FINAL V8_OVERRIDE {
2271     return Representation::Tagged();
2272   }
2273
2274   HValue* first() const { return OperandAt(0); }
2275   HValue* second() const { return OperandAt(1); }
2276 };
2277
2278
2279 class HCallJSFunction V8_FINAL : public HCall<1> {
2280  public:
2281   static HCallJSFunction* New(Zone* zone,
2282                               HValue* context,
2283                               HValue* function,
2284                               int argument_count,
2285                               bool pass_argument_count);
2286
2287   HValue* function() const { return OperandAt(0); }
2288
2289   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
2290
2291   virtual Representation RequiredInputRepresentation(
2292       int index) V8_FINAL V8_OVERRIDE {
2293     DCHECK(index == 0);
2294     return Representation::Tagged();
2295   }
2296
2297   bool pass_argument_count() const { return pass_argument_count_; }
2298
2299   virtual bool HasStackCheck() V8_FINAL V8_OVERRIDE {
2300     return has_stack_check_;
2301   }
2302
2303   DECLARE_CONCRETE_INSTRUCTION(CallJSFunction)
2304
2305  private:
2306   // The argument count includes the receiver.
2307   HCallJSFunction(HValue* function,
2308                   int argument_count,
2309                   bool pass_argument_count,
2310                   bool has_stack_check)
2311       : HCall<1>(argument_count),
2312         pass_argument_count_(pass_argument_count),
2313         has_stack_check_(has_stack_check) {
2314       SetOperandAt(0, function);
2315   }
2316
2317   bool pass_argument_count_;
2318   bool has_stack_check_;
2319 };
2320
2321
2322 class HCallWithDescriptor V8_FINAL : public HInstruction {
2323  public:
2324   static HCallWithDescriptor* New(Zone* zone, HValue* context,
2325       HValue* target,
2326       int argument_count,
2327       const InterfaceDescriptor* descriptor,
2328       const Vector<HValue*>& operands) {
2329     DCHECK(operands.length() == descriptor->GetEnvironmentLength());
2330     HCallWithDescriptor* res =
2331         new(zone) HCallWithDescriptor(target, argument_count,
2332                                       descriptor, operands, zone);
2333     return res;
2334   }
2335
2336   virtual int OperandCount() const V8_FINAL V8_OVERRIDE {
2337     return values_.length();
2338   }
2339   virtual HValue* OperandAt(int index) const V8_FINAL V8_OVERRIDE {
2340     return values_[index];
2341   }
2342
2343   virtual Representation RequiredInputRepresentation(
2344       int index) V8_FINAL V8_OVERRIDE {
2345     if (index == 0) {
2346       return Representation::Tagged();
2347     } else {
2348       int par_index = index - 1;
2349       DCHECK(par_index < descriptor_->GetEnvironmentLength());
2350       return descriptor_->GetParameterRepresentation(par_index);
2351     }
2352   }
2353
2354   DECLARE_CONCRETE_INSTRUCTION(CallWithDescriptor)
2355
2356   virtual HType CalculateInferredType() V8_FINAL V8_OVERRIDE {
2357     return HType::Tagged();
2358   }
2359
2360   virtual int argument_count() const {
2361     return argument_count_;
2362   }
2363
2364   virtual int argument_delta() const V8_OVERRIDE {
2365     return -argument_count_;
2366   }
2367
2368   const InterfaceDescriptor* descriptor() const {
2369     return descriptor_;
2370   }
2371
2372   HValue* target() {
2373     return OperandAt(0);
2374   }
2375
2376   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
2377
2378  private:
2379   // The argument count includes the receiver.
2380   HCallWithDescriptor(HValue* target,
2381                       int argument_count,
2382                       const InterfaceDescriptor* descriptor,
2383                       const Vector<HValue*>& operands,
2384                       Zone* zone)
2385     : descriptor_(descriptor),
2386       values_(descriptor->GetEnvironmentLength() + 1, zone) {
2387     argument_count_ = argument_count;
2388     AddOperand(target, zone);
2389     for (int i = 0; i < operands.length(); i++) {
2390       AddOperand(operands[i], zone);
2391     }
2392     this->set_representation(Representation::Tagged());
2393     this->SetAllSideEffects();
2394   }
2395
2396   void AddOperand(HValue* v, Zone* zone) {
2397     values_.Add(NULL, zone);
2398     SetOperandAt(values_.length() - 1, v);
2399   }
2400
2401   void InternalSetOperandAt(int index,
2402                             HValue* value) V8_FINAL V8_OVERRIDE {
2403     values_[index] = value;
2404   }
2405
2406   const InterfaceDescriptor* descriptor_;
2407   ZoneList<HValue*> values_;
2408   int argument_count_;
2409 };
2410
2411
2412 class HInvokeFunction V8_FINAL : public HBinaryCall {
2413  public:
2414   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P2(HInvokeFunction, HValue*, int);
2415
2416   HInvokeFunction(HValue* context,
2417                   HValue* function,
2418                   Handle<JSFunction> known_function,
2419                   int argument_count)
2420       : HBinaryCall(context, function, argument_count),
2421         known_function_(known_function) {
2422     formal_parameter_count_ = known_function.is_null()
2423         ? 0 : known_function->shared()->formal_parameter_count();
2424     has_stack_check_ = !known_function.is_null() &&
2425         (known_function->code()->kind() == Code::FUNCTION ||
2426          known_function->code()->kind() == Code::OPTIMIZED_FUNCTION);
2427   }
2428
2429   static HInvokeFunction* New(Zone* zone,
2430                               HValue* context,
2431                               HValue* function,
2432                               Handle<JSFunction> known_function,
2433                               int argument_count) {
2434     return new(zone) HInvokeFunction(context, function,
2435                                      known_function, argument_count);
2436   }
2437
2438   HValue* context() { return first(); }
2439   HValue* function() { return second(); }
2440   Handle<JSFunction> known_function() { return known_function_; }
2441   int formal_parameter_count() const { return formal_parameter_count_; }
2442
2443   virtual bool HasStackCheck() V8_FINAL V8_OVERRIDE {
2444     return has_stack_check_;
2445   }
2446
2447   DECLARE_CONCRETE_INSTRUCTION(InvokeFunction)
2448
2449  private:
2450   HInvokeFunction(HValue* context, HValue* function, int argument_count)
2451       : HBinaryCall(context, function, argument_count),
2452         has_stack_check_(false) {
2453   }
2454
2455   Handle<JSFunction> known_function_;
2456   int formal_parameter_count_;
2457   bool has_stack_check_;
2458 };
2459
2460
2461 class HCallFunction V8_FINAL : public HBinaryCall {
2462  public:
2463   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P2(HCallFunction, HValue*, int);
2464   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P3(
2465       HCallFunction, HValue*, int, CallFunctionFlags);
2466
2467   HValue* context() { return first(); }
2468   HValue* function() { return second(); }
2469   CallFunctionFlags function_flags() const { return function_flags_; }
2470
2471   DECLARE_CONCRETE_INSTRUCTION(CallFunction)
2472
2473   virtual int argument_delta() const V8_OVERRIDE { return -argument_count(); }
2474
2475  private:
2476   HCallFunction(HValue* context,
2477                 HValue* function,
2478                 int argument_count,
2479                 CallFunctionFlags flags = NO_CALL_FUNCTION_FLAGS)
2480       : HBinaryCall(context, function, argument_count), function_flags_(flags) {
2481   }
2482   CallFunctionFlags function_flags_;
2483 };
2484
2485
2486 class HCallNew V8_FINAL : public HBinaryCall {
2487  public:
2488   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P2(HCallNew, HValue*, int);
2489
2490   HValue* context() { return first(); }
2491   HValue* constructor() { return second(); }
2492
2493   DECLARE_CONCRETE_INSTRUCTION(CallNew)
2494
2495  private:
2496   HCallNew(HValue* context, HValue* constructor, int argument_count)
2497       : HBinaryCall(context, constructor, argument_count) {}
2498 };
2499
2500
2501 class HCallNewArray V8_FINAL : public HBinaryCall {
2502  public:
2503   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P3(HCallNewArray,
2504                                               HValue*,
2505                                               int,
2506                                               ElementsKind);
2507
2508   HValue* context() { return first(); }
2509   HValue* constructor() { return second(); }
2510
2511   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
2512
2513   ElementsKind elements_kind() const { return elements_kind_; }
2514
2515   DECLARE_CONCRETE_INSTRUCTION(CallNewArray)
2516
2517  private:
2518   HCallNewArray(HValue* context, HValue* constructor, int argument_count,
2519                 ElementsKind elements_kind)
2520       : HBinaryCall(context, constructor, argument_count),
2521         elements_kind_(elements_kind) {}
2522
2523   ElementsKind elements_kind_;
2524 };
2525
2526
2527 class HCallRuntime V8_FINAL : public HCall<1> {
2528  public:
2529   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P3(HCallRuntime,
2530                                               Handle<String>,
2531                                               const Runtime::Function*,
2532                                               int);
2533
2534   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
2535
2536   HValue* context() { return OperandAt(0); }
2537   const Runtime::Function* function() const { return c_function_; }
2538   Handle<String> name() const { return name_; }
2539   SaveFPRegsMode save_doubles() const { return save_doubles_; }
2540   void set_save_doubles(SaveFPRegsMode save_doubles) {
2541     save_doubles_ = save_doubles;
2542   }
2543
2544   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
2545     return Representation::Tagged();
2546   }
2547
2548   DECLARE_CONCRETE_INSTRUCTION(CallRuntime)
2549
2550  private:
2551   HCallRuntime(HValue* context,
2552                Handle<String> name,
2553                const Runtime::Function* c_function,
2554                int argument_count)
2555       : HCall<1>(argument_count), c_function_(c_function), name_(name),
2556         save_doubles_(kDontSaveFPRegs) {
2557     SetOperandAt(0, context);
2558   }
2559
2560   const Runtime::Function* c_function_;
2561   Handle<String> name_;
2562   SaveFPRegsMode save_doubles_;
2563 };
2564
2565
2566 class HMapEnumLength V8_FINAL : public HUnaryOperation {
2567  public:
2568   DECLARE_INSTRUCTION_FACTORY_P1(HMapEnumLength, HValue*);
2569
2570   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
2571     return Representation::Tagged();
2572   }
2573
2574   DECLARE_CONCRETE_INSTRUCTION(MapEnumLength)
2575
2576  protected:
2577   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
2578
2579  private:
2580   explicit HMapEnumLength(HValue* value)
2581       : HUnaryOperation(value, HType::Smi()) {
2582     set_representation(Representation::Smi());
2583     SetFlag(kUseGVN);
2584     SetDependsOnFlag(kMaps);
2585   }
2586
2587   virtual bool IsDeletable() const V8_OVERRIDE { return true; }
2588 };
2589
2590
2591 class HUnaryMathOperation V8_FINAL : public HTemplateInstruction<2> {
2592  public:
2593   static HInstruction* New(Zone* zone,
2594                            HValue* context,
2595                            HValue* value,
2596                            BuiltinFunctionId op);
2597
2598   HValue* context() const { return OperandAt(0); }
2599   HValue* value() const { return OperandAt(1); }
2600
2601   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
2602
2603   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
2604     if (index == 0) {
2605       return Representation::Tagged();
2606     } else {
2607       switch (op_) {
2608         case kMathFloor:
2609         case kMathRound:
2610         case kMathFround:
2611         case kMathSqrt:
2612         case kMathPowHalf:
2613         case kMathLog:
2614         case kMathExp:
2615           return Representation::Double();
2616         case kMathAbs:
2617           return representation();
2618         case kMathClz32:
2619           return Representation::Integer32();
2620         default:
2621           UNREACHABLE();
2622           return Representation::None();
2623       }
2624     }
2625   }
2626
2627   virtual Range* InferRange(Zone* zone) V8_OVERRIDE;
2628
2629   virtual HValue* Canonicalize() V8_OVERRIDE;
2630   virtual Representation RepresentationFromUses() V8_OVERRIDE;
2631   virtual Representation RepresentationFromInputs() V8_OVERRIDE;
2632
2633   BuiltinFunctionId op() const { return op_; }
2634   const char* OpName() const;
2635
2636   DECLARE_CONCRETE_INSTRUCTION(UnaryMathOperation)
2637
2638  protected:
2639   virtual bool DataEquals(HValue* other) V8_OVERRIDE {
2640     HUnaryMathOperation* b = HUnaryMathOperation::cast(other);
2641     return op_ == b->op();
2642   }
2643
2644  private:
2645   // Indicates if we support a double (and int32) output for Math.floor and
2646   // Math.round.
2647   bool SupportsFlexibleFloorAndRound() const {
2648 #ifdef V8_TARGET_ARCH_ARM64
2649     return true;
2650 #else
2651     return false;
2652 #endif
2653   }
2654   HUnaryMathOperation(HValue* context, HValue* value, BuiltinFunctionId op)
2655       : HTemplateInstruction<2>(HType::TaggedNumber()), op_(op) {
2656     SetOperandAt(0, context);
2657     SetOperandAt(1, value);
2658     switch (op) {
2659       case kMathFloor:
2660       case kMathRound:
2661         if (SupportsFlexibleFloorAndRound()) {
2662           SetFlag(kFlexibleRepresentation);
2663         } else {
2664           set_representation(Representation::Integer32());
2665         }
2666         break;
2667       case kMathClz32:
2668         set_representation(Representation::Integer32());
2669         break;
2670       case kMathAbs:
2671         // Not setting representation here: it is None intentionally.
2672         SetFlag(kFlexibleRepresentation);
2673         // TODO(svenpanne) This flag is actually only needed if representation()
2674         // is tagged, and not when it is an unboxed double or unboxed integer.
2675         SetChangesFlag(kNewSpacePromotion);
2676         break;
2677       case kMathFround:
2678       case kMathLog:
2679       case kMathExp:
2680       case kMathSqrt:
2681       case kMathPowHalf:
2682         set_representation(Representation::Double());
2683         break;
2684       default:
2685         UNREACHABLE();
2686     }
2687     SetFlag(kUseGVN);
2688     SetFlag(kAllowUndefinedAsNaN);
2689   }
2690
2691   virtual bool IsDeletable() const V8_OVERRIDE { return true; }
2692
2693   HValue* SimplifiedDividendForMathFloorOfDiv(HDiv* hdiv);
2694   HValue* SimplifiedDivisorForMathFloorOfDiv(HDiv* hdiv);
2695
2696   BuiltinFunctionId op_;
2697 };
2698
2699
2700 class HLoadRoot V8_FINAL : public HTemplateInstruction<0> {
2701  public:
2702   DECLARE_INSTRUCTION_FACTORY_P1(HLoadRoot, Heap::RootListIndex);
2703   DECLARE_INSTRUCTION_FACTORY_P2(HLoadRoot, Heap::RootListIndex, HType);
2704
2705   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
2706     return Representation::None();
2707   }
2708
2709   Heap::RootListIndex index() const { return index_; }
2710
2711   DECLARE_CONCRETE_INSTRUCTION(LoadRoot)
2712
2713  protected:
2714   virtual bool DataEquals(HValue* other) V8_OVERRIDE {
2715     HLoadRoot* b = HLoadRoot::cast(other);
2716     return index_ == b->index_;
2717   }
2718
2719  private:
2720   explicit HLoadRoot(Heap::RootListIndex index, HType type = HType::Tagged())
2721       : HTemplateInstruction<0>(type), index_(index) {
2722     SetFlag(kUseGVN);
2723     // TODO(bmeurer): We'll need kDependsOnRoots once we add the
2724     // corresponding HStoreRoot instruction.
2725     SetDependsOnFlag(kCalls);
2726   }
2727
2728   virtual bool IsDeletable() const V8_OVERRIDE { return true; }
2729
2730   const Heap::RootListIndex index_;
2731 };
2732
2733
2734 class HCheckMaps V8_FINAL : public HTemplateInstruction<2> {
2735  public:
2736   static HCheckMaps* New(Zone* zone, HValue* context, HValue* value,
2737                          Handle<Map> map, HValue* typecheck = NULL) {
2738     return new(zone) HCheckMaps(value, new(zone) UniqueSet<Map>(
2739             Unique<Map>::CreateImmovable(map), zone), typecheck);
2740   }
2741   static HCheckMaps* New(Zone* zone, HValue* context,
2742                          HValue* value, SmallMapList* map_list,
2743                          HValue* typecheck = NULL) {
2744     UniqueSet<Map>* maps = new(zone) UniqueSet<Map>(map_list->length(), zone);
2745     for (int i = 0; i < map_list->length(); ++i) {
2746       maps->Add(Unique<Map>::CreateImmovable(map_list->at(i)), zone);
2747     }
2748     return new(zone) HCheckMaps(value, maps, typecheck);
2749   }
2750
2751   bool IsStabilityCheck() const { return is_stability_check_; }
2752   void MarkAsStabilityCheck() {
2753     maps_are_stable_ = true;
2754     has_migration_target_ = false;
2755     is_stability_check_ = true;
2756     ClearChangesFlag(kNewSpacePromotion);
2757     ClearDependsOnFlag(kElementsKind);
2758     ClearDependsOnFlag(kMaps);
2759   }
2760
2761   virtual bool HasEscapingOperandAt(int index) V8_OVERRIDE { return false; }
2762   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
2763     return Representation::Tagged();
2764   }
2765
2766   virtual HType CalculateInferredType() V8_OVERRIDE {
2767     if (value()->type().IsHeapObject()) return value()->type();
2768     return HType::HeapObject();
2769   }
2770
2771   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
2772
2773   HValue* value() const { return OperandAt(0); }
2774   HValue* typecheck() const { return OperandAt(1); }
2775
2776   const UniqueSet<Map>* maps() const { return maps_; }
2777   void set_maps(const UniqueSet<Map>* maps) { maps_ = maps; }
2778
2779   bool maps_are_stable() const { return maps_are_stable_; }
2780
2781   bool HasMigrationTarget() const { return has_migration_target_; }
2782
2783   virtual HValue* Canonicalize() V8_OVERRIDE;
2784
2785   static HCheckMaps* CreateAndInsertAfter(Zone* zone,
2786                                           HValue* value,
2787                                           Unique<Map> map,
2788                                           bool map_is_stable,
2789                                           HInstruction* instr) {
2790     return instr->Append(new(zone) HCheckMaps(
2791             value, new(zone) UniqueSet<Map>(map, zone), map_is_stable));
2792   }
2793
2794   static HCheckMaps* CreateAndInsertBefore(Zone* zone,
2795                                            HValue* value,
2796                                            const UniqueSet<Map>* maps,
2797                                            bool maps_are_stable,
2798                                            HInstruction* instr) {
2799     return instr->Prepend(new(zone) HCheckMaps(value, maps, maps_are_stable));
2800   }
2801
2802   DECLARE_CONCRETE_INSTRUCTION(CheckMaps)
2803
2804  protected:
2805   virtual bool DataEquals(HValue* other) V8_OVERRIDE {
2806     return this->maps()->Equals(HCheckMaps::cast(other)->maps());
2807   }
2808
2809   virtual int RedefinedOperandIndex() { return 0; }
2810
2811  private:
2812   HCheckMaps(HValue* value, const UniqueSet<Map>* maps, bool maps_are_stable)
2813       : HTemplateInstruction<2>(HType::HeapObject()), maps_(maps),
2814         has_migration_target_(false), is_stability_check_(false),
2815         maps_are_stable_(maps_are_stable) {
2816     DCHECK_NE(0, maps->size());
2817     SetOperandAt(0, value);
2818     // Use the object value for the dependency.
2819     SetOperandAt(1, value);
2820     set_representation(Representation::Tagged());
2821     SetFlag(kUseGVN);
2822     SetDependsOnFlag(kMaps);
2823     SetDependsOnFlag(kElementsKind);
2824   }
2825
2826   HCheckMaps(HValue* value, const UniqueSet<Map>* maps, HValue* typecheck)
2827       : HTemplateInstruction<2>(HType::HeapObject()), maps_(maps),
2828         has_migration_target_(false), is_stability_check_(false),
2829         maps_are_stable_(true) {
2830     DCHECK_NE(0, maps->size());
2831     SetOperandAt(0, value);
2832     // Use the object value for the dependency if NULL is passed.
2833     SetOperandAt(1, typecheck ? typecheck : value);
2834     set_representation(Representation::Tagged());
2835     SetFlag(kUseGVN);
2836     SetDependsOnFlag(kMaps);
2837     SetDependsOnFlag(kElementsKind);
2838     for (int i = 0; i < maps->size(); ++i) {
2839       Handle<Map> map = maps->at(i).handle();
2840       if (map->is_migration_target()) has_migration_target_ = true;
2841       if (!map->is_stable()) maps_are_stable_ = false;
2842     }
2843     if (has_migration_target_) SetChangesFlag(kNewSpacePromotion);
2844   }
2845
2846   const UniqueSet<Map>* maps_;
2847   bool has_migration_target_ : 1;
2848   bool is_stability_check_ : 1;
2849   bool maps_are_stable_ : 1;
2850 };
2851
2852
2853 class HCheckValue V8_FINAL : public HUnaryOperation {
2854  public:
2855   static HCheckValue* New(Zone* zone, HValue* context,
2856                           HValue* value, Handle<JSFunction> func) {
2857     bool in_new_space = zone->isolate()->heap()->InNewSpace(*func);
2858     // NOTE: We create an uninitialized Unique and initialize it later.
2859     // This is because a JSFunction can move due to GC during graph creation.
2860     // TODO(titzer): This is a migration crutch. Replace with some kind of
2861     // Uniqueness scope later.
2862     Unique<JSFunction> target = Unique<JSFunction>::CreateUninitialized(func);
2863     HCheckValue* check = new(zone) HCheckValue(value, target, in_new_space);
2864     return check;
2865   }
2866   static HCheckValue* New(Zone* zone, HValue* context,
2867                           HValue* value, Unique<HeapObject> target,
2868                           bool object_in_new_space) {
2869     return new(zone) HCheckValue(value, target, object_in_new_space);
2870   }
2871
2872   virtual void FinalizeUniqueness() V8_OVERRIDE {
2873     object_ = Unique<HeapObject>(object_.handle());
2874   }
2875
2876   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
2877     return Representation::Tagged();
2878   }
2879   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
2880
2881   virtual HValue* Canonicalize() V8_OVERRIDE;
2882
2883 #ifdef DEBUG
2884   virtual void Verify() V8_OVERRIDE;
2885 #endif
2886
2887   Unique<HeapObject> object() const { return object_; }
2888   bool object_in_new_space() const { return object_in_new_space_; }
2889
2890   DECLARE_CONCRETE_INSTRUCTION(CheckValue)
2891
2892  protected:
2893   virtual bool DataEquals(HValue* other) V8_OVERRIDE {
2894     HCheckValue* b = HCheckValue::cast(other);
2895     return object_ == b->object_;
2896   }
2897
2898  private:
2899   HCheckValue(HValue* value, Unique<HeapObject> object,
2900                bool object_in_new_space)
2901       : HUnaryOperation(value, value->type()),
2902         object_(object),
2903         object_in_new_space_(object_in_new_space) {
2904     set_representation(Representation::Tagged());
2905     SetFlag(kUseGVN);
2906   }
2907
2908   Unique<HeapObject> object_;
2909   bool object_in_new_space_;
2910 };
2911
2912
2913 class HCheckInstanceType V8_FINAL : public HUnaryOperation {
2914  public:
2915   enum Check {
2916     IS_SPEC_OBJECT,
2917     IS_JS_ARRAY,
2918     IS_STRING,
2919     IS_INTERNALIZED_STRING,
2920     LAST_INTERVAL_CHECK = IS_JS_ARRAY
2921   };
2922
2923   DECLARE_INSTRUCTION_FACTORY_P2(HCheckInstanceType, HValue*, Check);
2924
2925   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
2926
2927   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
2928     return Representation::Tagged();
2929   }
2930
2931   virtual HType CalculateInferredType() V8_OVERRIDE {
2932     switch (check_) {
2933       case IS_SPEC_OBJECT: return HType::JSObject();
2934       case IS_JS_ARRAY: return HType::JSArray();
2935       case IS_STRING: return HType::String();
2936       case IS_INTERNALIZED_STRING: return HType::String();
2937     }
2938     UNREACHABLE();
2939     return HType::Tagged();
2940   }
2941
2942   virtual HValue* Canonicalize() V8_OVERRIDE;
2943
2944   bool is_interval_check() const { return check_ <= LAST_INTERVAL_CHECK; }
2945   void GetCheckInterval(InstanceType* first, InstanceType* last);
2946   void GetCheckMaskAndTag(uint8_t* mask, uint8_t* tag);
2947
2948   Check check() const { return check_; }
2949
2950   DECLARE_CONCRETE_INSTRUCTION(CheckInstanceType)
2951
2952  protected:
2953   // TODO(ager): It could be nice to allow the ommision of instance
2954   // type checks if we have already performed an instance type check
2955   // with a larger range.
2956   virtual bool DataEquals(HValue* other) V8_OVERRIDE {
2957     HCheckInstanceType* b = HCheckInstanceType::cast(other);
2958     return check_ == b->check_;
2959   }
2960
2961   virtual int RedefinedOperandIndex() { return 0; }
2962
2963  private:
2964   const char* GetCheckName() const;
2965
2966   HCheckInstanceType(HValue* value, Check check)
2967       : HUnaryOperation(value, HType::HeapObject()), check_(check) {
2968     set_representation(Representation::Tagged());
2969     SetFlag(kUseGVN);
2970   }
2971
2972   const Check check_;
2973 };
2974
2975
2976 class HCheckSmi V8_FINAL : public HUnaryOperation {
2977  public:
2978   DECLARE_INSTRUCTION_FACTORY_P1(HCheckSmi, HValue*);
2979
2980   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
2981     return Representation::Tagged();
2982   }
2983
2984   virtual HValue* Canonicalize() V8_OVERRIDE {
2985     HType value_type = value()->type();
2986     if (value_type.IsSmi()) {
2987       return NULL;
2988     }
2989     return this;
2990   }
2991
2992   DECLARE_CONCRETE_INSTRUCTION(CheckSmi)
2993
2994  protected:
2995   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
2996
2997  private:
2998   explicit HCheckSmi(HValue* value) : HUnaryOperation(value, HType::Smi()) {
2999     set_representation(Representation::Smi());
3000     SetFlag(kUseGVN);
3001   }
3002 };
3003
3004
3005 class HCheckHeapObject V8_FINAL : public HUnaryOperation {
3006  public:
3007   DECLARE_INSTRUCTION_FACTORY_P1(HCheckHeapObject, HValue*);
3008
3009   virtual bool HasEscapingOperandAt(int index) V8_OVERRIDE { return false; }
3010   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
3011     return Representation::Tagged();
3012   }
3013
3014   virtual HType CalculateInferredType() V8_OVERRIDE {
3015     if (value()->type().IsHeapObject()) return value()->type();
3016     return HType::HeapObject();
3017   }
3018
3019 #ifdef DEBUG
3020   virtual void Verify() V8_OVERRIDE;
3021 #endif
3022
3023   virtual HValue* Canonicalize() V8_OVERRIDE {
3024     return value()->type().IsHeapObject() ? NULL : this;
3025   }
3026
3027   DECLARE_CONCRETE_INSTRUCTION(CheckHeapObject)
3028
3029  protected:
3030   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
3031
3032  private:
3033   explicit HCheckHeapObject(HValue* value) : HUnaryOperation(value) {
3034     set_representation(Representation::Tagged());
3035     SetFlag(kUseGVN);
3036   }
3037 };
3038
3039
3040 class InductionVariableData;
3041
3042
3043 struct InductionVariableLimitUpdate {
3044   InductionVariableData* updated_variable;
3045   HValue* limit;
3046   bool limit_is_upper;
3047   bool limit_is_included;
3048
3049   InductionVariableLimitUpdate()
3050       : updated_variable(NULL), limit(NULL),
3051         limit_is_upper(false), limit_is_included(false) {}
3052 };
3053
3054
3055 class HBoundsCheck;
3056 class HPhi;
3057 class HConstant;
3058 class HBitwise;
3059
3060
3061 class InductionVariableData V8_FINAL : public ZoneObject {
3062  public:
3063   class InductionVariableCheck : public ZoneObject {
3064    public:
3065     HBoundsCheck* check() { return check_; }
3066     InductionVariableCheck* next() { return next_; }
3067     bool HasUpperLimit() { return upper_limit_ >= 0; }
3068     int32_t upper_limit() {
3069       DCHECK(HasUpperLimit());
3070       return upper_limit_;
3071     }
3072     void set_upper_limit(int32_t upper_limit) {
3073       upper_limit_ = upper_limit;
3074     }
3075
3076     bool processed() { return processed_; }
3077     void set_processed() { processed_ = true; }
3078
3079     InductionVariableCheck(HBoundsCheck* check,
3080                            InductionVariableCheck* next,
3081                            int32_t upper_limit = kNoLimit)
3082         : check_(check), next_(next), upper_limit_(upper_limit),
3083           processed_(false) {}
3084
3085    private:
3086     HBoundsCheck* check_;
3087     InductionVariableCheck* next_;
3088     int32_t upper_limit_;
3089     bool processed_;
3090   };
3091
3092   class ChecksRelatedToLength : public ZoneObject {
3093    public:
3094     HValue* length() { return length_; }
3095     ChecksRelatedToLength* next() { return next_; }
3096     InductionVariableCheck* checks() { return checks_; }
3097
3098     void AddCheck(HBoundsCheck* check, int32_t upper_limit = kNoLimit);
3099     void CloseCurrentBlock();
3100
3101     ChecksRelatedToLength(HValue* length, ChecksRelatedToLength* next)
3102       : length_(length), next_(next), checks_(NULL),
3103         first_check_in_block_(NULL),
3104         added_index_(NULL),
3105         added_constant_(NULL),
3106         current_and_mask_in_block_(0),
3107         current_or_mask_in_block_(0) {}
3108
3109    private:
3110     void UseNewIndexInCurrentBlock(Token::Value token,
3111                                    int32_t mask,
3112                                    HValue* index_base,
3113                                    HValue* context);
3114
3115     HBoundsCheck* first_check_in_block() { return first_check_in_block_; }
3116     HBitwise* added_index() { return added_index_; }
3117     void set_added_index(HBitwise* index) { added_index_ = index; }
3118     HConstant* added_constant() { return added_constant_; }
3119     void set_added_constant(HConstant* constant) { added_constant_ = constant; }
3120     int32_t current_and_mask_in_block() { return current_and_mask_in_block_; }
3121     int32_t current_or_mask_in_block() { return current_or_mask_in_block_; }
3122     int32_t current_upper_limit() { return current_upper_limit_; }
3123
3124     HValue* length_;
3125     ChecksRelatedToLength* next_;
3126     InductionVariableCheck* checks_;
3127
3128     HBoundsCheck* first_check_in_block_;
3129     HBitwise* added_index_;
3130     HConstant* added_constant_;
3131     int32_t current_and_mask_in_block_;
3132     int32_t current_or_mask_in_block_;
3133     int32_t current_upper_limit_;
3134   };
3135
3136   struct LimitFromPredecessorBlock {
3137     InductionVariableData* variable;
3138     Token::Value token;
3139     HValue* limit;
3140     HBasicBlock* other_target;
3141
3142     bool LimitIsValid() { return token != Token::ILLEGAL; }
3143
3144     bool LimitIsIncluded() {
3145       return Token::IsEqualityOp(token) ||
3146           token == Token::GTE || token == Token::LTE;
3147     }
3148     bool LimitIsUpper() {
3149       return token == Token::LTE || token == Token::LT || token == Token::NE;
3150     }
3151
3152     LimitFromPredecessorBlock()
3153         : variable(NULL),
3154           token(Token::ILLEGAL),
3155           limit(NULL),
3156           other_target(NULL) {}
3157   };
3158
3159   static const int32_t kNoLimit = -1;
3160
3161   static InductionVariableData* ExaminePhi(HPhi* phi);
3162   static void ComputeLimitFromPredecessorBlock(
3163       HBasicBlock* block,
3164       LimitFromPredecessorBlock* result);
3165   static bool ComputeInductionVariableLimit(
3166       HBasicBlock* block,
3167       InductionVariableLimitUpdate* additional_limit);
3168
3169   struct BitwiseDecompositionResult {
3170     HValue* base;
3171     int32_t and_mask;
3172     int32_t or_mask;
3173     HValue* context;
3174
3175     BitwiseDecompositionResult()
3176         : base(NULL), and_mask(0), or_mask(0), context(NULL) {}
3177   };
3178   static void DecomposeBitwise(HValue* value,
3179                                BitwiseDecompositionResult* result);
3180
3181   void AddCheck(HBoundsCheck* check, int32_t upper_limit = kNoLimit);
3182
3183   bool CheckIfBranchIsLoopGuard(Token::Value token,
3184                                 HBasicBlock* current_branch,
3185                                 HBasicBlock* other_branch);
3186
3187   void UpdateAdditionalLimit(InductionVariableLimitUpdate* update);
3188
3189   HPhi* phi() { return phi_; }
3190   HValue* base() { return base_; }
3191   int32_t increment() { return increment_; }
3192   HValue* limit() { return limit_; }
3193   bool limit_included() { return limit_included_; }
3194   HBasicBlock* limit_validity() { return limit_validity_; }
3195   HBasicBlock* induction_exit_block() { return induction_exit_block_; }
3196   HBasicBlock* induction_exit_target() { return induction_exit_target_; }
3197   ChecksRelatedToLength* checks() { return checks_; }
3198   HValue* additional_upper_limit() { return additional_upper_limit_; }
3199   bool additional_upper_limit_is_included() {
3200     return additional_upper_limit_is_included_;
3201   }
3202   HValue* additional_lower_limit() { return additional_lower_limit_; }
3203   bool additional_lower_limit_is_included() {
3204     return additional_lower_limit_is_included_;
3205   }
3206
3207   bool LowerLimitIsNonNegativeConstant() {
3208     if (base()->IsInteger32Constant() && base()->GetInteger32Constant() >= 0) {
3209       return true;
3210     }
3211     if (additional_lower_limit() != NULL &&
3212         additional_lower_limit()->IsInteger32Constant() &&
3213         additional_lower_limit()->GetInteger32Constant() >= 0) {
3214       // Ignoring the corner case of !additional_lower_limit_is_included()
3215       // is safe, handling it adds unneeded complexity.
3216       return true;
3217     }
3218     return false;
3219   }
3220
3221   int32_t ComputeUpperLimit(int32_t and_mask, int32_t or_mask);
3222
3223  private:
3224   template <class T> void swap(T* a, T* b) {
3225     T c(*a);
3226     *a = *b;
3227     *b = c;
3228   }
3229
3230   InductionVariableData(HPhi* phi, HValue* base, int32_t increment)
3231       : phi_(phi), base_(IgnoreOsrValue(base)), increment_(increment),
3232         limit_(NULL), limit_included_(false), limit_validity_(NULL),
3233         induction_exit_block_(NULL), induction_exit_target_(NULL),
3234         checks_(NULL),
3235         additional_upper_limit_(NULL),
3236         additional_upper_limit_is_included_(false),
3237         additional_lower_limit_(NULL),
3238         additional_lower_limit_is_included_(false) {}
3239
3240   static int32_t ComputeIncrement(HPhi* phi, HValue* phi_operand);
3241
3242   static HValue* IgnoreOsrValue(HValue* v);
3243   static InductionVariableData* GetInductionVariableData(HValue* v);
3244
3245   HPhi* phi_;
3246   HValue* base_;
3247   int32_t increment_;
3248   HValue* limit_;
3249   bool limit_included_;
3250   HBasicBlock* limit_validity_;
3251   HBasicBlock* induction_exit_block_;
3252   HBasicBlock* induction_exit_target_;
3253   ChecksRelatedToLength* checks_;
3254   HValue* additional_upper_limit_;
3255   bool additional_upper_limit_is_included_;
3256   HValue* additional_lower_limit_;
3257   bool additional_lower_limit_is_included_;
3258 };
3259
3260
3261 class HPhi V8_FINAL : public HValue {
3262  public:
3263   HPhi(int merged_index, Zone* zone)
3264       : inputs_(2, zone),
3265         merged_index_(merged_index),
3266         phi_id_(-1),
3267         induction_variable_data_(NULL) {
3268     for (int i = 0; i < Representation::kNumRepresentations; i++) {
3269       non_phi_uses_[i] = 0;
3270       indirect_uses_[i] = 0;
3271     }
3272     DCHECK(merged_index >= 0 || merged_index == kInvalidMergedIndex);
3273     SetFlag(kFlexibleRepresentation);
3274     SetFlag(kAllowUndefinedAsNaN);
3275   }
3276
3277   virtual Representation RepresentationFromInputs() V8_OVERRIDE;
3278
3279   virtual Range* InferRange(Zone* zone) V8_OVERRIDE;
3280   virtual void InferRepresentation(
3281       HInferRepresentationPhase* h_infer) V8_OVERRIDE;
3282   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
3283     return representation();
3284   }
3285   virtual Representation KnownOptimalRepresentation() V8_OVERRIDE {
3286     return representation();
3287   }
3288   virtual HType CalculateInferredType() V8_OVERRIDE;
3289   virtual int OperandCount() const V8_OVERRIDE { return inputs_.length(); }
3290   virtual HValue* OperandAt(int index) const V8_OVERRIDE {
3291     return inputs_[index];
3292   }
3293   HValue* GetRedundantReplacement();
3294   void AddInput(HValue* value);
3295   bool HasRealUses();
3296
3297   bool IsReceiver() const { return merged_index_ == 0; }
3298   bool HasMergedIndex() const { return merged_index_ != kInvalidMergedIndex; }
3299
3300   virtual HSourcePosition position() const V8_OVERRIDE;
3301
3302   int merged_index() const { return merged_index_; }
3303
3304   InductionVariableData* induction_variable_data() {
3305     return induction_variable_data_;
3306   }
3307   bool IsInductionVariable() {
3308     return induction_variable_data_ != NULL;
3309   }
3310   bool IsLimitedInductionVariable() {
3311     return IsInductionVariable() &&
3312         induction_variable_data_->limit() != NULL;
3313   }
3314   void DetectInductionVariable() {
3315     DCHECK(induction_variable_data_ == NULL);
3316     induction_variable_data_ = InductionVariableData::ExaminePhi(this);
3317   }
3318
3319   virtual OStream& PrintTo(OStream& os) const V8_OVERRIDE;  // NOLINT
3320
3321 #ifdef DEBUG
3322   virtual void Verify() V8_OVERRIDE;
3323 #endif
3324
3325   void InitRealUses(int id);
3326   void AddNonPhiUsesFrom(HPhi* other);
3327   void AddIndirectUsesTo(int* use_count);
3328
3329   int tagged_non_phi_uses() const {
3330     return non_phi_uses_[Representation::kTagged];
3331   }
3332   int smi_non_phi_uses() const {
3333     return non_phi_uses_[Representation::kSmi];
3334   }
3335   int int32_non_phi_uses() const {
3336     return non_phi_uses_[Representation::kInteger32];
3337   }
3338   int double_non_phi_uses() const {
3339     return non_phi_uses_[Representation::kDouble];
3340   }
3341   int tagged_indirect_uses() const {
3342     return indirect_uses_[Representation::kTagged];
3343   }
3344   int smi_indirect_uses() const {
3345     return indirect_uses_[Representation::kSmi];
3346   }
3347   int int32_indirect_uses() const {
3348     return indirect_uses_[Representation::kInteger32];
3349   }
3350   int double_indirect_uses() const {
3351     return indirect_uses_[Representation::kDouble];
3352   }
3353   int phi_id() { return phi_id_; }
3354
3355   static HPhi* cast(HValue* value) {
3356     DCHECK(value->IsPhi());
3357     return reinterpret_cast<HPhi*>(value);
3358   }
3359   virtual Opcode opcode() const V8_OVERRIDE { return HValue::kPhi; }
3360
3361   void SimplifyConstantInputs();
3362
3363   // Marker value representing an invalid merge index.
3364   static const int kInvalidMergedIndex = -1;
3365
3366  protected:
3367   virtual void DeleteFromGraph() V8_OVERRIDE;
3368   virtual void InternalSetOperandAt(int index, HValue* value) V8_OVERRIDE {
3369     inputs_[index] = value;
3370   }
3371
3372  private:
3373   ZoneList<HValue*> inputs_;
3374   int merged_index_;
3375
3376   int non_phi_uses_[Representation::kNumRepresentations];
3377   int indirect_uses_[Representation::kNumRepresentations];
3378   int phi_id_;
3379   InductionVariableData* induction_variable_data_;
3380
3381   // TODO(titzer): we can't eliminate the receiver for generating backtraces
3382   virtual bool IsDeletable() const V8_OVERRIDE { return !IsReceiver(); }
3383 };
3384
3385
3386 // Common base class for HArgumentsObject and HCapturedObject.
3387 class HDematerializedObject : public HInstruction {
3388  public:
3389   HDematerializedObject(int count, Zone* zone) : values_(count, zone) {}
3390
3391   virtual int OperandCount() const V8_FINAL V8_OVERRIDE {
3392     return values_.length();
3393   }
3394   virtual HValue* OperandAt(int index) const V8_FINAL V8_OVERRIDE {
3395     return values_[index];
3396   }
3397
3398   virtual bool HasEscapingOperandAt(int index) V8_FINAL V8_OVERRIDE {
3399     return false;
3400   }
3401   virtual Representation RequiredInputRepresentation(
3402       int index) V8_FINAL V8_OVERRIDE {
3403     return Representation::None();
3404   }
3405
3406  protected:
3407   virtual void InternalSetOperandAt(int index,
3408                                     HValue* value) V8_FINAL V8_OVERRIDE {
3409     values_[index] = value;
3410   }
3411
3412   // List of values tracked by this marker.
3413   ZoneList<HValue*> values_;
3414 };
3415
3416
3417 class HArgumentsObject V8_FINAL : public HDematerializedObject {
3418  public:
3419   static HArgumentsObject* New(Zone* zone, HValue* context, int count) {
3420     return new(zone) HArgumentsObject(count, zone);
3421   }
3422
3423   // The values contain a list of all elements in the arguments object
3424   // including the receiver object, which is skipped when materializing.
3425   const ZoneList<HValue*>* arguments_values() const { return &values_; }
3426   int arguments_count() const { return values_.length(); }
3427
3428   void AddArgument(HValue* argument, Zone* zone) {
3429     values_.Add(NULL, zone);  // Resize list.
3430     SetOperandAt(values_.length() - 1, argument);
3431   }
3432
3433   DECLARE_CONCRETE_INSTRUCTION(ArgumentsObject)
3434
3435  private:
3436   HArgumentsObject(int count, Zone* zone)
3437       : HDematerializedObject(count, zone) {
3438     set_representation(Representation::Tagged());
3439     SetFlag(kIsArguments);
3440   }
3441 };
3442
3443
3444 class HCapturedObject V8_FINAL : public HDematerializedObject {
3445  public:
3446   HCapturedObject(int length, int id, Zone* zone)
3447       : HDematerializedObject(length, zone), capture_id_(id) {
3448     set_representation(Representation::Tagged());
3449     values_.AddBlock(NULL, length, zone);  // Resize list.
3450   }
3451
3452   // The values contain a list of all in-object properties inside the
3453   // captured object and is index by field index. Properties in the
3454   // properties or elements backing store are not tracked here.
3455   const ZoneList<HValue*>* values() const { return &values_; }
3456   int length() const { return values_.length(); }
3457   int capture_id() const { return capture_id_; }
3458
3459   // Shortcut for the map value of this captured object.
3460   HValue* map_value() const { return values()->first(); }
3461
3462   void ReuseSideEffectsFromStore(HInstruction* store) {
3463     DCHECK(store->HasObservableSideEffects());
3464     DCHECK(store->IsStoreNamedField());
3465     changes_flags_.Add(store->ChangesFlags());
3466   }
3467
3468   // Replay effects of this instruction on the given environment.
3469   void ReplayEnvironment(HEnvironment* env);
3470
3471   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
3472
3473   DECLARE_CONCRETE_INSTRUCTION(CapturedObject)
3474
3475  private:
3476   int capture_id_;
3477
3478   // Note that we cannot DCE captured objects as they are used to replay
3479   // the environment. This method is here as an explicit reminder.
3480   // TODO(mstarzinger): Turn HSimulates into full snapshots maybe?
3481   virtual bool IsDeletable() const V8_FINAL V8_OVERRIDE { return false; }
3482 };
3483
3484
3485 class HConstant V8_FINAL : public HTemplateInstruction<0> {
3486  public:
3487   DECLARE_INSTRUCTION_FACTORY_P1(HConstant, int32_t);
3488   DECLARE_INSTRUCTION_FACTORY_P2(HConstant, int32_t, Representation);
3489   DECLARE_INSTRUCTION_FACTORY_P1(HConstant, double);
3490   DECLARE_INSTRUCTION_FACTORY_P1(HConstant, Handle<Object>);
3491   DECLARE_INSTRUCTION_FACTORY_P1(HConstant, ExternalReference);
3492
3493   static HConstant* CreateAndInsertAfter(Zone* zone,
3494                                          HValue* context,
3495                                          int32_t value,
3496                                          Representation representation,
3497                                          HInstruction* instruction) {
3498     return instruction->Append(HConstant::New(
3499         zone, context, value, representation));
3500   }
3501
3502   static HConstant* CreateAndInsertBefore(Zone* zone,
3503                                           HValue* context,
3504                                           int32_t value,
3505                                           Representation representation,
3506                                           HInstruction* instruction) {
3507     return instruction->Prepend(HConstant::New(
3508         zone, context, value, representation));
3509   }
3510
3511   static HConstant* CreateAndInsertBefore(Zone* zone,
3512                                           Unique<Map> map,
3513                                           bool map_is_stable,
3514                                           HInstruction* instruction) {
3515     return instruction->Prepend(new(zone) HConstant(
3516         map, Unique<Map>(Handle<Map>::null()), map_is_stable,
3517         Representation::Tagged(), HType::HeapObject(), true,
3518         false, false, MAP_TYPE));
3519   }
3520
3521   static HConstant* CreateAndInsertAfter(Zone* zone,
3522                                          Unique<Map> map,
3523                                          bool map_is_stable,
3524                                          HInstruction* instruction) {
3525     return instruction->Append(new(zone) HConstant(
3526             map, Unique<Map>(Handle<Map>::null()), map_is_stable,
3527             Representation::Tagged(), HType::HeapObject(), true,
3528             false, false, MAP_TYPE));
3529   }
3530
3531   Handle<Object> handle(Isolate* isolate) {
3532     if (object_.handle().is_null()) {
3533       // Default arguments to is_not_in_new_space depend on this heap number
3534       // to be tenured so that it's guaranteed not to be located in new space.
3535       object_ = Unique<Object>::CreateUninitialized(
3536           isolate->factory()->NewNumber(double_value_, TENURED));
3537     }
3538     AllowDeferredHandleDereference smi_check;
3539     DCHECK(has_int32_value_ || !object_.handle()->IsSmi());
3540     return object_.handle();
3541   }
3542
3543   bool IsSpecialDouble() const {
3544     return has_double_value_ &&
3545         (BitCast<int64_t>(double_value_) == BitCast<int64_t>(-0.0) ||
3546          FixedDoubleArray::is_the_hole_nan(double_value_) ||
3547          std::isnan(double_value_));
3548   }
3549
3550   bool NotInNewSpace() const {
3551     return is_not_in_new_space_;
3552   }
3553
3554   bool ImmortalImmovable() const;
3555
3556   bool IsCell() const {
3557     return instance_type_ == CELL_TYPE || instance_type_ == PROPERTY_CELL_TYPE;
3558   }
3559
3560   bool IsMap() const {
3561     return instance_type_ == MAP_TYPE;
3562   }
3563
3564   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
3565     return Representation::None();
3566   }
3567
3568   virtual Representation KnownOptimalRepresentation() V8_OVERRIDE {
3569     if (HasSmiValue() && SmiValuesAre31Bits()) return Representation::Smi();
3570     if (HasInteger32Value()) return Representation::Integer32();
3571     if (HasNumberValue()) return Representation::Double();
3572     if (HasExternalReferenceValue()) return Representation::External();
3573     return Representation::Tagged();
3574   }
3575
3576   virtual bool EmitAtUses() V8_OVERRIDE;
3577   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
3578   HConstant* CopyToRepresentation(Representation r, Zone* zone) const;
3579   Maybe<HConstant*> CopyToTruncatedInt32(Zone* zone);
3580   Maybe<HConstant*> CopyToTruncatedNumber(Zone* zone);
3581   bool HasInteger32Value() const { return has_int32_value_; }
3582   int32_t Integer32Value() const {
3583     DCHECK(HasInteger32Value());
3584     return int32_value_;
3585   }
3586   bool HasSmiValue() const { return has_smi_value_; }
3587   bool HasDoubleValue() const { return has_double_value_; }
3588   double DoubleValue() const {
3589     DCHECK(HasDoubleValue());
3590     return double_value_;
3591   }
3592   bool IsTheHole() const {
3593     if (HasDoubleValue() && FixedDoubleArray::is_the_hole_nan(double_value_)) {
3594       return true;
3595     }
3596     return object_.IsKnownGlobal(isolate()->heap()->the_hole_value());
3597   }
3598   bool HasNumberValue() const { return has_double_value_; }
3599   int32_t NumberValueAsInteger32() const {
3600     DCHECK(HasNumberValue());
3601     // Irrespective of whether a numeric HConstant can be safely
3602     // represented as an int32, we store the (in some cases lossy)
3603     // representation of the number in int32_value_.
3604     return int32_value_;
3605   }
3606   bool HasStringValue() const {
3607     if (has_double_value_ || has_int32_value_) return false;
3608     DCHECK(!object_.handle().is_null());
3609     return instance_type_ < FIRST_NONSTRING_TYPE;
3610   }
3611   Handle<String> StringValue() const {
3612     DCHECK(HasStringValue());
3613     return Handle<String>::cast(object_.handle());
3614   }
3615   bool HasInternalizedStringValue() const {
3616     return HasStringValue() && StringShape(instance_type_).IsInternalized();
3617   }
3618
3619   bool HasExternalReferenceValue() const {
3620     return has_external_reference_value_;
3621   }
3622   ExternalReference ExternalReferenceValue() const {
3623     return external_reference_value_;
3624   }
3625
3626   bool HasBooleanValue() const { return type_.IsBoolean(); }
3627   bool BooleanValue() const { return boolean_value_; }
3628   bool IsUndetectable() const { return is_undetectable_; }
3629   InstanceType GetInstanceType() const { return instance_type_; }
3630
3631   bool HasMapValue() const { return instance_type_ == MAP_TYPE; }
3632   Unique<Map> MapValue() const {
3633     DCHECK(HasMapValue());
3634     return Unique<Map>::cast(GetUnique());
3635   }
3636   bool HasStableMapValue() const {
3637     DCHECK(HasMapValue() || !has_stable_map_value_);
3638     return has_stable_map_value_;
3639   }
3640
3641   bool HasObjectMap() const { return !object_map_.IsNull(); }
3642   Unique<Map> ObjectMap() const {
3643     DCHECK(HasObjectMap());
3644     return object_map_;
3645   }
3646
3647   virtual intptr_t Hashcode() V8_OVERRIDE {
3648     if (has_int32_value_) {
3649       return static_cast<intptr_t>(int32_value_);
3650     } else if (has_double_value_) {
3651       return static_cast<intptr_t>(BitCast<int64_t>(double_value_));
3652     } else if (has_external_reference_value_) {
3653       return reinterpret_cast<intptr_t>(external_reference_value_.address());
3654     } else {
3655       DCHECK(!object_.handle().is_null());
3656       return object_.Hashcode();
3657     }
3658   }
3659
3660   virtual void FinalizeUniqueness() V8_OVERRIDE {
3661     if (!has_double_value_ && !has_external_reference_value_) {
3662       DCHECK(!object_.handle().is_null());
3663       object_ = Unique<Object>(object_.handle());
3664     }
3665   }
3666
3667   Unique<Object> GetUnique() const {
3668     return object_;
3669   }
3670
3671   bool EqualsUnique(Unique<Object> other) const {
3672     return object_.IsInitialized() && object_ == other;
3673   }
3674
3675   virtual bool DataEquals(HValue* other) V8_OVERRIDE {
3676     HConstant* other_constant = HConstant::cast(other);
3677     if (has_int32_value_) {
3678       return other_constant->has_int32_value_ &&
3679           int32_value_ == other_constant->int32_value_;
3680     } else if (has_double_value_) {
3681       return other_constant->has_double_value_ &&
3682           BitCast<int64_t>(double_value_) ==
3683           BitCast<int64_t>(other_constant->double_value_);
3684     } else if (has_external_reference_value_) {
3685       return other_constant->has_external_reference_value_ &&
3686           external_reference_value_ ==
3687           other_constant->external_reference_value_;
3688     } else {
3689       if (other_constant->has_int32_value_ ||
3690           other_constant->has_double_value_ ||
3691           other_constant->has_external_reference_value_) {
3692         return false;
3693       }
3694       DCHECK(!object_.handle().is_null());
3695       return other_constant->object_ == object_;
3696     }
3697   }
3698
3699 #ifdef DEBUG
3700   virtual void Verify() V8_OVERRIDE { }
3701 #endif
3702
3703   DECLARE_CONCRETE_INSTRUCTION(Constant)
3704
3705  protected:
3706   virtual Range* InferRange(Zone* zone) V8_OVERRIDE;
3707
3708  private:
3709   friend class HGraph;
3710   explicit HConstant(Handle<Object> handle,
3711                      Representation r = Representation::None());
3712   HConstant(int32_t value,
3713             Representation r = Representation::None(),
3714             bool is_not_in_new_space = true,
3715             Unique<Object> optional = Unique<Object>(Handle<Object>::null()));
3716   HConstant(double value,
3717             Representation r = Representation::None(),
3718             bool is_not_in_new_space = true,
3719             Unique<Object> optional = Unique<Object>(Handle<Object>::null()));
3720   HConstant(Unique<Object> object,
3721             Unique<Map> object_map,
3722             bool has_stable_map_value,
3723             Representation r,
3724             HType type,
3725             bool is_not_in_new_space,
3726             bool boolean_value,
3727             bool is_undetectable,
3728             InstanceType instance_type);
3729
3730   explicit HConstant(ExternalReference reference);
3731
3732   void Initialize(Representation r);
3733
3734   virtual bool IsDeletable() const V8_OVERRIDE { return true; }
3735
3736   // If this is a numerical constant, object_ either points to the
3737   // HeapObject the constant originated from or is null.  If the
3738   // constant is non-numeric, object_ always points to a valid
3739   // constant HeapObject.
3740   Unique<Object> object_;
3741
3742   // If object_ is a heap object, this points to the stable map of the object.
3743   Unique<Map> object_map_;
3744
3745   // If object_ is a map, this indicates whether the map is stable.
3746   bool has_stable_map_value_ : 1;
3747
3748   // We store the HConstant in the most specific form safely possible.
3749   // The two flags, has_int32_value_ and has_double_value_ tell us if
3750   // int32_value_ and double_value_ hold valid, safe representations
3751   // of the constant.  has_int32_value_ implies has_double_value_ but
3752   // not the converse.
3753   bool has_smi_value_ : 1;
3754   bool has_int32_value_ : 1;
3755   bool has_double_value_ : 1;
3756   bool has_external_reference_value_ : 1;
3757   bool is_not_in_new_space_ : 1;
3758   bool boolean_value_ : 1;
3759   bool is_undetectable_: 1;
3760   int32_t int32_value_;
3761   double double_value_;
3762   ExternalReference external_reference_value_;
3763
3764   static const InstanceType kUnknownInstanceType = FILLER_TYPE;
3765   InstanceType instance_type_;
3766 };
3767
3768
3769 class HBinaryOperation : public HTemplateInstruction<3> {
3770  public:
3771   HBinaryOperation(HValue* context, HValue* left, HValue* right,
3772                    HType type = HType::Tagged())
3773       : HTemplateInstruction<3>(type),
3774         observed_output_representation_(Representation::None()) {
3775     DCHECK(left != NULL && right != NULL);
3776     SetOperandAt(0, context);
3777     SetOperandAt(1, left);
3778     SetOperandAt(2, right);
3779     observed_input_representation_[0] = Representation::None();
3780     observed_input_representation_[1] = Representation::None();
3781   }
3782
3783   HValue* context() const { return OperandAt(0); }
3784   HValue* left() const { return OperandAt(1); }
3785   HValue* right() const { return OperandAt(2); }
3786
3787   // True if switching left and right operands likely generates better code.
3788   bool AreOperandsBetterSwitched() {
3789     if (!IsCommutative()) return false;
3790
3791     // Constant operands are better off on the right, they can be inlined in
3792     // many situations on most platforms.
3793     if (left()->IsConstant()) return true;
3794     if (right()->IsConstant()) return false;
3795
3796     // Otherwise, if there is only one use of the right operand, it would be
3797     // better off on the left for platforms that only have 2-arg arithmetic
3798     // ops (e.g ia32, x64) that clobber the left operand.
3799     return right()->HasOneUse();
3800   }
3801
3802   HValue* BetterLeftOperand() {
3803     return AreOperandsBetterSwitched() ? right() : left();
3804   }
3805
3806   HValue* BetterRightOperand() {
3807     return AreOperandsBetterSwitched() ? left() : right();
3808   }
3809
3810   void set_observed_input_representation(int index, Representation rep) {
3811     DCHECK(index >= 1 && index <= 2);
3812     observed_input_representation_[index - 1] = rep;
3813   }
3814
3815   virtual void initialize_output_representation(Representation observed) {
3816     observed_output_representation_ = observed;
3817   }
3818
3819   virtual Representation observed_input_representation(int index) V8_OVERRIDE {
3820     if (index == 0) return Representation::Tagged();
3821     return observed_input_representation_[index - 1];
3822   }
3823
3824   virtual void UpdateRepresentation(Representation new_rep,
3825                                     HInferRepresentationPhase* h_infer,
3826                                     const char* reason) V8_OVERRIDE {
3827     Representation rep = !FLAG_smi_binop && new_rep.IsSmi()
3828         ? Representation::Integer32() : new_rep;
3829     HValue::UpdateRepresentation(rep, h_infer, reason);
3830   }
3831
3832   virtual void InferRepresentation(
3833       HInferRepresentationPhase* h_infer) V8_OVERRIDE;
3834   virtual Representation RepresentationFromInputs() V8_OVERRIDE;
3835   Representation RepresentationFromOutput();
3836   virtual void AssumeRepresentation(Representation r) V8_OVERRIDE;
3837
3838   virtual bool IsCommutative() const { return false; }
3839
3840   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
3841
3842   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
3843     if (index == 0) return Representation::Tagged();
3844     return representation();
3845   }
3846
3847   void SetOperandPositions(Zone* zone,
3848                            HSourcePosition left_pos,
3849                            HSourcePosition right_pos) {
3850     set_operand_position(zone, 1, left_pos);
3851     set_operand_position(zone, 2, right_pos);
3852   }
3853
3854   bool RightIsPowerOf2() {
3855     if (!right()->IsInteger32Constant()) return false;
3856     int32_t value = right()->GetInteger32Constant();
3857     return IsPowerOf2(value) || IsPowerOf2(-value);
3858   }
3859
3860   DECLARE_ABSTRACT_INSTRUCTION(BinaryOperation)
3861
3862  private:
3863   bool IgnoreObservedOutputRepresentation(Representation current_rep);
3864
3865   Representation observed_input_representation_[2];
3866   Representation observed_output_representation_;
3867 };
3868
3869
3870 class HWrapReceiver V8_FINAL : public HTemplateInstruction<2> {
3871  public:
3872   DECLARE_INSTRUCTION_FACTORY_P2(HWrapReceiver, HValue*, HValue*);
3873
3874   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
3875
3876   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
3877     return Representation::Tagged();
3878   }
3879
3880   HValue* receiver() const { return OperandAt(0); }
3881   HValue* function() const { return OperandAt(1); }
3882
3883   virtual HValue* Canonicalize() V8_OVERRIDE;
3884
3885   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
3886   bool known_function() const { return known_function_; }
3887
3888   DECLARE_CONCRETE_INSTRUCTION(WrapReceiver)
3889
3890  private:
3891   HWrapReceiver(HValue* receiver, HValue* function) {
3892     known_function_ = function->IsConstant() &&
3893         HConstant::cast(function)->handle(function->isolate())->IsJSFunction();
3894     set_representation(Representation::Tagged());
3895     SetOperandAt(0, receiver);
3896     SetOperandAt(1, function);
3897     SetFlag(kUseGVN);
3898   }
3899
3900   bool known_function_;
3901 };
3902
3903
3904 class HApplyArguments V8_FINAL : public HTemplateInstruction<4> {
3905  public:
3906   DECLARE_INSTRUCTION_FACTORY_P4(HApplyArguments, HValue*, HValue*, HValue*,
3907                                  HValue*);
3908
3909   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
3910     // The length is untagged, all other inputs are tagged.
3911     return (index == 2)
3912         ? Representation::Integer32()
3913         : Representation::Tagged();
3914   }
3915
3916   HValue* function() { return OperandAt(0); }
3917   HValue* receiver() { return OperandAt(1); }
3918   HValue* length() { return OperandAt(2); }
3919   HValue* elements() { return OperandAt(3); }
3920
3921   DECLARE_CONCRETE_INSTRUCTION(ApplyArguments)
3922
3923  private:
3924   HApplyArguments(HValue* function,
3925                   HValue* receiver,
3926                   HValue* length,
3927                   HValue* elements) {
3928     set_representation(Representation::Tagged());
3929     SetOperandAt(0, function);
3930     SetOperandAt(1, receiver);
3931     SetOperandAt(2, length);
3932     SetOperandAt(3, elements);
3933     SetAllSideEffects();
3934   }
3935 };
3936
3937
3938 class HArgumentsElements V8_FINAL : public HTemplateInstruction<0> {
3939  public:
3940   DECLARE_INSTRUCTION_FACTORY_P1(HArgumentsElements, bool);
3941
3942   DECLARE_CONCRETE_INSTRUCTION(ArgumentsElements)
3943
3944   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
3945     return Representation::None();
3946   }
3947
3948   bool from_inlined() const { return from_inlined_; }
3949
3950  protected:
3951   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
3952
3953  private:
3954   explicit HArgumentsElements(bool from_inlined) : from_inlined_(from_inlined) {
3955     // The value produced by this instruction is a pointer into the stack
3956     // that looks as if it was a smi because of alignment.
3957     set_representation(Representation::Tagged());
3958     SetFlag(kUseGVN);
3959   }
3960
3961   virtual bool IsDeletable() const V8_OVERRIDE { return true; }
3962
3963   bool from_inlined_;
3964 };
3965
3966
3967 class HArgumentsLength V8_FINAL : public HUnaryOperation {
3968  public:
3969   DECLARE_INSTRUCTION_FACTORY_P1(HArgumentsLength, HValue*);
3970
3971   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
3972     return Representation::Tagged();
3973   }
3974
3975   DECLARE_CONCRETE_INSTRUCTION(ArgumentsLength)
3976
3977  protected:
3978   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
3979
3980  private:
3981   explicit HArgumentsLength(HValue* value) : HUnaryOperation(value) {
3982     set_representation(Representation::Integer32());
3983     SetFlag(kUseGVN);
3984   }
3985
3986   virtual bool IsDeletable() const V8_OVERRIDE { return true; }
3987 };
3988
3989
3990 class HAccessArgumentsAt V8_FINAL : public HTemplateInstruction<3> {
3991  public:
3992   DECLARE_INSTRUCTION_FACTORY_P3(HAccessArgumentsAt, HValue*, HValue*, HValue*);
3993
3994   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
3995
3996   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
3997     // The arguments elements is considered tagged.
3998     return index == 0
3999         ? Representation::Tagged()
4000         : Representation::Integer32();
4001   }
4002
4003   HValue* arguments() const { return OperandAt(0); }
4004   HValue* length() const { return OperandAt(1); }
4005   HValue* index() const { return OperandAt(2); }
4006
4007   DECLARE_CONCRETE_INSTRUCTION(AccessArgumentsAt)
4008
4009  private:
4010   HAccessArgumentsAt(HValue* arguments, HValue* length, HValue* index) {
4011     set_representation(Representation::Tagged());
4012     SetFlag(kUseGVN);
4013     SetOperandAt(0, arguments);
4014     SetOperandAt(1, length);
4015     SetOperandAt(2, index);
4016   }
4017
4018   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
4019 };
4020
4021
4022 class HBoundsCheckBaseIndexInformation;
4023
4024
4025 class HBoundsCheck V8_FINAL : public HTemplateInstruction<2> {
4026  public:
4027   DECLARE_INSTRUCTION_FACTORY_P2(HBoundsCheck, HValue*, HValue*);
4028
4029   bool skip_check() const { return skip_check_; }
4030   void set_skip_check() { skip_check_ = true; }
4031
4032   HValue* base() const { return base_; }
4033   int offset() const { return offset_; }
4034   int scale() const { return scale_; }
4035
4036   void ApplyIndexChange();
4037   bool DetectCompoundIndex() {
4038     DCHECK(base() == NULL);
4039
4040     DecompositionResult decomposition;
4041     if (index()->TryDecompose(&decomposition)) {
4042       base_ = decomposition.base();
4043       offset_ = decomposition.offset();
4044       scale_ = decomposition.scale();
4045       return true;
4046     } else {
4047       base_ = index();
4048       offset_ = 0;
4049       scale_ = 0;
4050       return false;
4051     }
4052   }
4053
4054   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
4055     return representation();
4056   }
4057
4058   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
4059   virtual void InferRepresentation(
4060       HInferRepresentationPhase* h_infer) V8_OVERRIDE;
4061
4062   HValue* index() const { return OperandAt(0); }
4063   HValue* length() const { return OperandAt(1); }
4064   bool allow_equality() const { return allow_equality_; }
4065   void set_allow_equality(bool v) { allow_equality_ = v; }
4066
4067   virtual int RedefinedOperandIndex() V8_OVERRIDE { return 0; }
4068   virtual bool IsPurelyInformativeDefinition() V8_OVERRIDE {
4069     return skip_check();
4070   }
4071
4072   DECLARE_CONCRETE_INSTRUCTION(BoundsCheck)
4073
4074  protected:
4075   friend class HBoundsCheckBaseIndexInformation;
4076
4077   virtual Range* InferRange(Zone* zone) V8_OVERRIDE;
4078
4079   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
4080   bool skip_check_;
4081   HValue* base_;
4082   int offset_;
4083   int scale_;
4084   bool allow_equality_;
4085
4086  private:
4087   // Normally HBoundsCheck should be created using the
4088   // HGraphBuilder::AddBoundsCheck() helper.
4089   // However when building stubs, where we know that the arguments are Int32,
4090   // it makes sense to invoke this constructor directly.
4091   HBoundsCheck(HValue* index, HValue* length)
4092     : skip_check_(false),
4093       base_(NULL), offset_(0), scale_(0),
4094       allow_equality_(false) {
4095     SetOperandAt(0, index);
4096     SetOperandAt(1, length);
4097     SetFlag(kFlexibleRepresentation);
4098     SetFlag(kUseGVN);
4099   }
4100
4101   virtual bool IsDeletable() const V8_OVERRIDE {
4102     return skip_check() && !FLAG_debug_code;
4103   }
4104 };
4105
4106
4107 class HBoundsCheckBaseIndexInformation V8_FINAL
4108     : public HTemplateInstruction<2> {
4109  public:
4110   explicit HBoundsCheckBaseIndexInformation(HBoundsCheck* check) {
4111     DecompositionResult decomposition;
4112     if (check->index()->TryDecompose(&decomposition)) {
4113       SetOperandAt(0, decomposition.base());
4114       SetOperandAt(1, check);
4115     } else {
4116       UNREACHABLE();
4117     }
4118   }
4119
4120   HValue* base_index() const { return OperandAt(0); }
4121   HBoundsCheck* bounds_check() { return HBoundsCheck::cast(OperandAt(1)); }
4122
4123   DECLARE_CONCRETE_INSTRUCTION(BoundsCheckBaseIndexInformation)
4124
4125   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
4126     return representation();
4127   }
4128
4129   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
4130
4131   virtual int RedefinedOperandIndex() V8_OVERRIDE { return 0; }
4132   virtual bool IsPurelyInformativeDefinition() V8_OVERRIDE { return true; }
4133 };
4134
4135
4136 class HBitwiseBinaryOperation : public HBinaryOperation {
4137  public:
4138   HBitwiseBinaryOperation(HValue* context, HValue* left, HValue* right,
4139                           HType type = HType::TaggedNumber())
4140       : HBinaryOperation(context, left, right, type) {
4141     SetFlag(kFlexibleRepresentation);
4142     SetFlag(kTruncatingToInt32);
4143     SetFlag(kAllowUndefinedAsNaN);
4144     SetAllSideEffects();
4145   }
4146
4147   virtual void RepresentationChanged(Representation to) V8_OVERRIDE {
4148     if (to.IsTagged() &&
4149         (left()->ToNumberCanBeObserved() || right()->ToNumberCanBeObserved())) {
4150       SetAllSideEffects();
4151       ClearFlag(kUseGVN);
4152     } else {
4153       ClearAllSideEffects();
4154       SetFlag(kUseGVN);
4155     }
4156     if (to.IsTagged()) SetChangesFlag(kNewSpacePromotion);
4157   }
4158
4159   virtual void UpdateRepresentation(Representation new_rep,
4160                                     HInferRepresentationPhase* h_infer,
4161                                     const char* reason) V8_OVERRIDE {
4162     // We only generate either int32 or generic tagged bitwise operations.
4163     if (new_rep.IsDouble()) new_rep = Representation::Integer32();
4164     HBinaryOperation::UpdateRepresentation(new_rep, h_infer, reason);
4165   }
4166
4167   virtual Representation observed_input_representation(int index) V8_OVERRIDE {
4168     Representation r = HBinaryOperation::observed_input_representation(index);
4169     if (r.IsDouble()) return Representation::Integer32();
4170     return r;
4171   }
4172
4173   virtual void initialize_output_representation(Representation observed) {
4174     if (observed.IsDouble()) observed = Representation::Integer32();
4175     HBinaryOperation::initialize_output_representation(observed);
4176   }
4177
4178   DECLARE_ABSTRACT_INSTRUCTION(BitwiseBinaryOperation)
4179
4180  private:
4181   virtual bool IsDeletable() const V8_OVERRIDE { return true; }
4182 };
4183
4184
4185 class HMathFloorOfDiv V8_FINAL : public HBinaryOperation {
4186  public:
4187   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P2(HMathFloorOfDiv,
4188                                               HValue*,
4189                                               HValue*);
4190
4191   DECLARE_CONCRETE_INSTRUCTION(MathFloorOfDiv)
4192
4193  protected:
4194   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
4195
4196  private:
4197   HMathFloorOfDiv(HValue* context, HValue* left, HValue* right)
4198       : HBinaryOperation(context, left, right) {
4199     set_representation(Representation::Integer32());
4200     SetFlag(kUseGVN);
4201     SetFlag(kCanOverflow);
4202     SetFlag(kCanBeDivByZero);
4203     SetFlag(kLeftCanBeMinInt);
4204     SetFlag(kLeftCanBeNegative);
4205     SetFlag(kLeftCanBePositive);
4206     SetFlag(kAllowUndefinedAsNaN);
4207   }
4208
4209   virtual Range* InferRange(Zone* zone) V8_OVERRIDE;
4210
4211   virtual bool IsDeletable() const V8_OVERRIDE { return true; }
4212 };
4213
4214
4215 class HArithmeticBinaryOperation : public HBinaryOperation {
4216  public:
4217   HArithmeticBinaryOperation(HValue* context, HValue* left, HValue* right)
4218       : HBinaryOperation(context, left, right, HType::TaggedNumber()) {
4219     SetAllSideEffects();
4220     SetFlag(kFlexibleRepresentation);
4221     SetFlag(kAllowUndefinedAsNaN);
4222   }
4223
4224   virtual void RepresentationChanged(Representation to) V8_OVERRIDE {
4225     if (to.IsTagged() &&
4226         (left()->ToNumberCanBeObserved() || right()->ToNumberCanBeObserved())) {
4227       SetAllSideEffects();
4228       ClearFlag(kUseGVN);
4229     } else {
4230       ClearAllSideEffects();
4231       SetFlag(kUseGVN);
4232     }
4233     if (to.IsTagged()) SetChangesFlag(kNewSpacePromotion);
4234   }
4235
4236   DECLARE_ABSTRACT_INSTRUCTION(ArithmeticBinaryOperation)
4237
4238  private:
4239   virtual bool IsDeletable() const V8_OVERRIDE { return true; }
4240 };
4241
4242
4243 class HCompareGeneric V8_FINAL : public HBinaryOperation {
4244  public:
4245   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P3(HCompareGeneric, HValue*,
4246                                               HValue*, Token::Value);
4247
4248   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
4249     return index == 0
4250         ? Representation::Tagged()
4251         : representation();
4252   }
4253
4254   Token::Value token() const { return token_; }
4255   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
4256
4257   DECLARE_CONCRETE_INSTRUCTION(CompareGeneric)
4258
4259  private:
4260   HCompareGeneric(HValue* context,
4261                   HValue* left,
4262                   HValue* right,
4263                   Token::Value token)
4264       : HBinaryOperation(context, left, right, HType::Boolean()),
4265         token_(token) {
4266     DCHECK(Token::IsCompareOp(token));
4267     set_representation(Representation::Tagged());
4268     SetAllSideEffects();
4269   }
4270
4271   Token::Value token_;
4272 };
4273
4274
4275 class HCompareNumericAndBranch : public HTemplateControlInstruction<2, 2> {
4276  public:
4277   DECLARE_INSTRUCTION_FACTORY_P3(HCompareNumericAndBranch,
4278                                  HValue*, HValue*, Token::Value);
4279   DECLARE_INSTRUCTION_FACTORY_P5(HCompareNumericAndBranch,
4280                                  HValue*, HValue*, Token::Value,
4281                                  HBasicBlock*, HBasicBlock*);
4282
4283   HValue* left() const { return OperandAt(0); }
4284   HValue* right() const { return OperandAt(1); }
4285   Token::Value token() const { return token_; }
4286
4287   void set_observed_input_representation(Representation left,
4288                                          Representation right) {
4289       observed_input_representation_[0] = left;
4290       observed_input_representation_[1] = right;
4291   }
4292
4293   virtual void InferRepresentation(
4294       HInferRepresentationPhase* h_infer) V8_OVERRIDE;
4295
4296   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
4297     return representation();
4298   }
4299   virtual Representation observed_input_representation(int index) V8_OVERRIDE {
4300     return observed_input_representation_[index];
4301   }
4302
4303   virtual bool KnownSuccessorBlock(HBasicBlock** block) V8_OVERRIDE;
4304
4305   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
4306
4307   void SetOperandPositions(Zone* zone,
4308                            HSourcePosition left_pos,
4309                            HSourcePosition right_pos) {
4310     set_operand_position(zone, 0, left_pos);
4311     set_operand_position(zone, 1, right_pos);
4312   }
4313
4314   DECLARE_CONCRETE_INSTRUCTION(CompareNumericAndBranch)
4315
4316  private:
4317   HCompareNumericAndBranch(HValue* left,
4318                            HValue* right,
4319                            Token::Value token,
4320                            HBasicBlock* true_target = NULL,
4321                            HBasicBlock* false_target = NULL)
4322       : token_(token) {
4323     SetFlag(kFlexibleRepresentation);
4324     DCHECK(Token::IsCompareOp(token));
4325     SetOperandAt(0, left);
4326     SetOperandAt(1, right);
4327     SetSuccessorAt(0, true_target);
4328     SetSuccessorAt(1, false_target);
4329   }
4330
4331   Representation observed_input_representation_[2];
4332   Token::Value token_;
4333 };
4334
4335
4336 class HCompareHoleAndBranch V8_FINAL : public HUnaryControlInstruction {
4337  public:
4338   DECLARE_INSTRUCTION_FACTORY_P1(HCompareHoleAndBranch, HValue*);
4339   DECLARE_INSTRUCTION_FACTORY_P3(HCompareHoleAndBranch, HValue*,
4340                                  HBasicBlock*, HBasicBlock*);
4341
4342   virtual void InferRepresentation(
4343       HInferRepresentationPhase* h_infer) V8_OVERRIDE;
4344
4345   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
4346     return representation();
4347   }
4348
4349   DECLARE_CONCRETE_INSTRUCTION(CompareHoleAndBranch)
4350
4351  private:
4352   HCompareHoleAndBranch(HValue* value,
4353                         HBasicBlock* true_target = NULL,
4354                         HBasicBlock* false_target = NULL)
4355       : HUnaryControlInstruction(value, true_target, false_target) {
4356     SetFlag(kFlexibleRepresentation);
4357     SetFlag(kAllowUndefinedAsNaN);
4358   }
4359 };
4360
4361
4362 class HCompareMinusZeroAndBranch V8_FINAL : public HUnaryControlInstruction {
4363  public:
4364   DECLARE_INSTRUCTION_FACTORY_P1(HCompareMinusZeroAndBranch, HValue*);
4365
4366   virtual void InferRepresentation(
4367       HInferRepresentationPhase* h_infer) V8_OVERRIDE;
4368
4369   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
4370     return representation();
4371   }
4372
4373   virtual bool KnownSuccessorBlock(HBasicBlock** block) V8_OVERRIDE;
4374
4375   DECLARE_CONCRETE_INSTRUCTION(CompareMinusZeroAndBranch)
4376
4377  private:
4378   explicit HCompareMinusZeroAndBranch(HValue* value)
4379       : HUnaryControlInstruction(value, NULL, NULL) {
4380   }
4381 };
4382
4383
4384 class HCompareObjectEqAndBranch : public HTemplateControlInstruction<2, 2> {
4385  public:
4386   DECLARE_INSTRUCTION_FACTORY_P2(HCompareObjectEqAndBranch, HValue*, HValue*);
4387   DECLARE_INSTRUCTION_FACTORY_P4(HCompareObjectEqAndBranch, HValue*, HValue*,
4388                                  HBasicBlock*, HBasicBlock*);
4389
4390   virtual bool KnownSuccessorBlock(HBasicBlock** block) V8_OVERRIDE;
4391
4392   static const int kNoKnownSuccessorIndex = -1;
4393   int known_successor_index() const { return known_successor_index_; }
4394   void set_known_successor_index(int known_successor_index) {
4395     known_successor_index_ = known_successor_index;
4396   }
4397
4398   HValue* left() const { return OperandAt(0); }
4399   HValue* right() const { return OperandAt(1); }
4400
4401   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
4402
4403   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
4404     return Representation::Tagged();
4405   }
4406
4407   virtual Representation observed_input_representation(int index) V8_OVERRIDE {
4408     return Representation::Tagged();
4409   }
4410
4411   DECLARE_CONCRETE_INSTRUCTION(CompareObjectEqAndBranch)
4412
4413  private:
4414   HCompareObjectEqAndBranch(HValue* left,
4415                             HValue* right,
4416                             HBasicBlock* true_target = NULL,
4417                             HBasicBlock* false_target = NULL)
4418       : known_successor_index_(kNoKnownSuccessorIndex) {
4419     SetOperandAt(0, left);
4420     SetOperandAt(1, right);
4421     SetSuccessorAt(0, true_target);
4422     SetSuccessorAt(1, false_target);
4423   }
4424
4425   int known_successor_index_;
4426 };
4427
4428
4429 class HIsObjectAndBranch V8_FINAL : public HUnaryControlInstruction {
4430  public:
4431   DECLARE_INSTRUCTION_FACTORY_P1(HIsObjectAndBranch, HValue*);
4432   DECLARE_INSTRUCTION_FACTORY_P3(HIsObjectAndBranch, HValue*,
4433                                  HBasicBlock*, HBasicBlock*);
4434
4435   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
4436     return Representation::Tagged();
4437   }
4438
4439   virtual bool KnownSuccessorBlock(HBasicBlock** block) V8_OVERRIDE;
4440
4441   DECLARE_CONCRETE_INSTRUCTION(IsObjectAndBranch)
4442
4443  private:
4444   HIsObjectAndBranch(HValue* value,
4445                      HBasicBlock* true_target = NULL,
4446                      HBasicBlock* false_target = NULL)
4447     : HUnaryControlInstruction(value, true_target, false_target) {}
4448 };
4449
4450
4451 class HIsStringAndBranch V8_FINAL : public HUnaryControlInstruction {
4452  public:
4453   DECLARE_INSTRUCTION_FACTORY_P1(HIsStringAndBranch, HValue*);
4454   DECLARE_INSTRUCTION_FACTORY_P3(HIsStringAndBranch, HValue*,
4455                                  HBasicBlock*, HBasicBlock*);
4456
4457   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
4458     return Representation::Tagged();
4459   }
4460
4461   virtual bool KnownSuccessorBlock(HBasicBlock** block) V8_OVERRIDE;
4462
4463   static const int kNoKnownSuccessorIndex = -1;
4464   int known_successor_index() const { return known_successor_index_; }
4465   void set_known_successor_index(int known_successor_index) {
4466     known_successor_index_ = known_successor_index;
4467   }
4468
4469   DECLARE_CONCRETE_INSTRUCTION(IsStringAndBranch)
4470
4471  protected:
4472   virtual int RedefinedOperandIndex() { return 0; }
4473
4474  private:
4475   HIsStringAndBranch(HValue* value,
4476                      HBasicBlock* true_target = NULL,
4477                      HBasicBlock* false_target = NULL)
4478     : HUnaryControlInstruction(value, true_target, false_target),
4479       known_successor_index_(kNoKnownSuccessorIndex) { }
4480
4481   int known_successor_index_;
4482 };
4483
4484
4485 class HIsSmiAndBranch V8_FINAL : public HUnaryControlInstruction {
4486  public:
4487   DECLARE_INSTRUCTION_FACTORY_P1(HIsSmiAndBranch, HValue*);
4488   DECLARE_INSTRUCTION_FACTORY_P3(HIsSmiAndBranch, HValue*,
4489                                  HBasicBlock*, HBasicBlock*);
4490
4491   DECLARE_CONCRETE_INSTRUCTION(IsSmiAndBranch)
4492
4493   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
4494     return Representation::Tagged();
4495   }
4496
4497  protected:
4498   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
4499   virtual int RedefinedOperandIndex() { return 0; }
4500
4501  private:
4502   HIsSmiAndBranch(HValue* value,
4503                   HBasicBlock* true_target = NULL,
4504                   HBasicBlock* false_target = NULL)
4505       : HUnaryControlInstruction(value, true_target, false_target) {
4506     set_representation(Representation::Tagged());
4507   }
4508 };
4509
4510
4511 class HIsUndetectableAndBranch V8_FINAL : public HUnaryControlInstruction {
4512  public:
4513   DECLARE_INSTRUCTION_FACTORY_P1(HIsUndetectableAndBranch, HValue*);
4514   DECLARE_INSTRUCTION_FACTORY_P3(HIsUndetectableAndBranch, HValue*,
4515                                  HBasicBlock*, HBasicBlock*);
4516
4517   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
4518     return Representation::Tagged();
4519   }
4520
4521   virtual bool KnownSuccessorBlock(HBasicBlock** block) V8_OVERRIDE;
4522
4523   DECLARE_CONCRETE_INSTRUCTION(IsUndetectableAndBranch)
4524
4525  private:
4526   HIsUndetectableAndBranch(HValue* value,
4527                            HBasicBlock* true_target = NULL,
4528                            HBasicBlock* false_target = NULL)
4529       : HUnaryControlInstruction(value, true_target, false_target) {}
4530 };
4531
4532
4533 class HStringCompareAndBranch : public HTemplateControlInstruction<2, 3> {
4534  public:
4535   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P3(HStringCompareAndBranch,
4536                                               HValue*,
4537                                               HValue*,
4538                                               Token::Value);
4539
4540   HValue* context() { return OperandAt(0); }
4541   HValue* left() { return OperandAt(1); }
4542   HValue* right() { return OperandAt(2); }
4543   Token::Value token() const { return token_; }
4544
4545   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
4546
4547   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
4548     return Representation::Tagged();
4549   }
4550
4551   Representation GetInputRepresentation() const {
4552     return Representation::Tagged();
4553   }
4554
4555   DECLARE_CONCRETE_INSTRUCTION(StringCompareAndBranch)
4556
4557  private:
4558   HStringCompareAndBranch(HValue* context,
4559                           HValue* left,
4560                           HValue* right,
4561                           Token::Value token)
4562       : token_(token) {
4563     DCHECK(Token::IsCompareOp(token));
4564     SetOperandAt(0, context);
4565     SetOperandAt(1, left);
4566     SetOperandAt(2, right);
4567     set_representation(Representation::Tagged());
4568     SetChangesFlag(kNewSpacePromotion);
4569   }
4570
4571   Token::Value token_;
4572 };
4573
4574
4575 class HIsConstructCallAndBranch : public HTemplateControlInstruction<2, 0> {
4576  public:
4577   DECLARE_INSTRUCTION_FACTORY_P0(HIsConstructCallAndBranch);
4578
4579   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
4580     return Representation::None();
4581   }
4582
4583   DECLARE_CONCRETE_INSTRUCTION(IsConstructCallAndBranch)
4584  private:
4585   HIsConstructCallAndBranch() {}
4586 };
4587
4588
4589 class HHasInstanceTypeAndBranch V8_FINAL : public HUnaryControlInstruction {
4590  public:
4591   DECLARE_INSTRUCTION_FACTORY_P2(
4592       HHasInstanceTypeAndBranch, HValue*, InstanceType);
4593   DECLARE_INSTRUCTION_FACTORY_P3(
4594       HHasInstanceTypeAndBranch, HValue*, InstanceType, InstanceType);
4595
4596   InstanceType from() { return from_; }
4597   InstanceType to() { return to_; }
4598
4599   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
4600
4601   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
4602     return Representation::Tagged();
4603   }
4604
4605   virtual bool KnownSuccessorBlock(HBasicBlock** block) V8_OVERRIDE;
4606
4607   DECLARE_CONCRETE_INSTRUCTION(HasInstanceTypeAndBranch)
4608
4609  private:
4610   HHasInstanceTypeAndBranch(HValue* value, InstanceType type)
4611       : HUnaryControlInstruction(value, NULL, NULL), from_(type), to_(type) { }
4612   HHasInstanceTypeAndBranch(HValue* value, InstanceType from, InstanceType to)
4613       : HUnaryControlInstruction(value, NULL, NULL), from_(from), to_(to) {
4614     DCHECK(to == LAST_TYPE);  // Others not implemented yet in backend.
4615   }
4616
4617   InstanceType from_;
4618   InstanceType to_;  // Inclusive range, not all combinations work.
4619 };
4620
4621
4622 class HHasCachedArrayIndexAndBranch V8_FINAL : public HUnaryControlInstruction {
4623  public:
4624   DECLARE_INSTRUCTION_FACTORY_P1(HHasCachedArrayIndexAndBranch, HValue*);
4625
4626   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
4627     return Representation::Tagged();
4628   }
4629
4630   DECLARE_CONCRETE_INSTRUCTION(HasCachedArrayIndexAndBranch)
4631  private:
4632   explicit HHasCachedArrayIndexAndBranch(HValue* value)
4633       : HUnaryControlInstruction(value, NULL, NULL) { }
4634 };
4635
4636
4637 class HGetCachedArrayIndex V8_FINAL : public HUnaryOperation {
4638  public:
4639   DECLARE_INSTRUCTION_FACTORY_P1(HGetCachedArrayIndex, HValue*);
4640
4641   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
4642     return Representation::Tagged();
4643   }
4644
4645   DECLARE_CONCRETE_INSTRUCTION(GetCachedArrayIndex)
4646
4647  protected:
4648   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
4649
4650  private:
4651   explicit HGetCachedArrayIndex(HValue* value) : HUnaryOperation(value) {
4652     set_representation(Representation::Tagged());
4653     SetFlag(kUseGVN);
4654   }
4655
4656   virtual bool IsDeletable() const V8_OVERRIDE { return true; }
4657 };
4658
4659
4660 class HClassOfTestAndBranch V8_FINAL : public HUnaryControlInstruction {
4661  public:
4662   DECLARE_INSTRUCTION_FACTORY_P2(HClassOfTestAndBranch, HValue*,
4663                                  Handle<String>);
4664
4665   DECLARE_CONCRETE_INSTRUCTION(ClassOfTestAndBranch)
4666
4667   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
4668     return Representation::Tagged();
4669   }
4670
4671   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
4672
4673   Handle<String> class_name() const { return class_name_; }
4674
4675  private:
4676   HClassOfTestAndBranch(HValue* value, Handle<String> class_name)
4677       : HUnaryControlInstruction(value, NULL, NULL),
4678         class_name_(class_name) { }
4679
4680   Handle<String> class_name_;
4681 };
4682
4683
4684 class HTypeofIsAndBranch V8_FINAL : public HUnaryControlInstruction {
4685  public:
4686   DECLARE_INSTRUCTION_FACTORY_P2(HTypeofIsAndBranch, HValue*, Handle<String>);
4687
4688   Handle<String> type_literal() const { return type_literal_.handle(); }
4689   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
4690
4691   DECLARE_CONCRETE_INSTRUCTION(TypeofIsAndBranch)
4692
4693   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
4694     return Representation::None();
4695   }
4696
4697   virtual bool KnownSuccessorBlock(HBasicBlock** block) V8_OVERRIDE;
4698
4699   virtual void FinalizeUniqueness() V8_OVERRIDE {
4700     type_literal_ = Unique<String>(type_literal_.handle());
4701   }
4702
4703  private:
4704   HTypeofIsAndBranch(HValue* value, Handle<String> type_literal)
4705       : HUnaryControlInstruction(value, NULL, NULL),
4706         type_literal_(Unique<String>::CreateUninitialized(type_literal)) { }
4707
4708   Unique<String> type_literal_;
4709 };
4710
4711
4712 class HInstanceOf V8_FINAL : public HBinaryOperation {
4713  public:
4714   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P2(HInstanceOf, HValue*, HValue*);
4715
4716   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
4717     return Representation::Tagged();
4718   }
4719
4720   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
4721
4722   DECLARE_CONCRETE_INSTRUCTION(InstanceOf)
4723
4724  private:
4725   HInstanceOf(HValue* context, HValue* left, HValue* right)
4726       : HBinaryOperation(context, left, right, HType::Boolean()) {
4727     set_representation(Representation::Tagged());
4728     SetAllSideEffects();
4729   }
4730 };
4731
4732
4733 class HInstanceOfKnownGlobal V8_FINAL : public HTemplateInstruction<2> {
4734  public:
4735   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P2(HInstanceOfKnownGlobal,
4736                                               HValue*,
4737                                               Handle<JSFunction>);
4738
4739   HValue* context() { return OperandAt(0); }
4740   HValue* left() { return OperandAt(1); }
4741   Handle<JSFunction> function() { return function_; }
4742
4743   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
4744     return Representation::Tagged();
4745   }
4746
4747   DECLARE_CONCRETE_INSTRUCTION(InstanceOfKnownGlobal)
4748
4749  private:
4750   HInstanceOfKnownGlobal(HValue* context,
4751                          HValue* left,
4752                          Handle<JSFunction> right)
4753       : HTemplateInstruction<2>(HType::Boolean()), function_(right) {
4754     SetOperandAt(0, context);
4755     SetOperandAt(1, left);
4756     set_representation(Representation::Tagged());
4757     SetAllSideEffects();
4758   }
4759
4760   Handle<JSFunction> function_;
4761 };
4762
4763
4764 class HPower V8_FINAL : public HTemplateInstruction<2> {
4765  public:
4766   static HInstruction* New(Zone* zone,
4767                            HValue* context,
4768                            HValue* left,
4769                            HValue* right);
4770
4771   HValue* left() { return OperandAt(0); }
4772   HValue* right() const { return OperandAt(1); }
4773
4774   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
4775     return index == 0
4776       ? Representation::Double()
4777       : Representation::None();
4778   }
4779   virtual Representation observed_input_representation(int index) V8_OVERRIDE {
4780     return RequiredInputRepresentation(index);
4781   }
4782
4783   DECLARE_CONCRETE_INSTRUCTION(Power)
4784
4785  protected:
4786   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
4787
4788  private:
4789   HPower(HValue* left, HValue* right) {
4790     SetOperandAt(0, left);
4791     SetOperandAt(1, right);
4792     set_representation(Representation::Double());
4793     SetFlag(kUseGVN);
4794     SetChangesFlag(kNewSpacePromotion);
4795   }
4796
4797   virtual bool IsDeletable() const V8_OVERRIDE {
4798     return !right()->representation().IsTagged();
4799   }
4800 };
4801
4802
4803 class HAdd V8_FINAL : public HArithmeticBinaryOperation {
4804  public:
4805   static HInstruction* New(Zone* zone,
4806                            HValue* context,
4807                            HValue* left,
4808                            HValue* right);
4809
4810   // Add is only commutative if two integer values are added and not if two
4811   // tagged values are added (because it might be a String concatenation).
4812   // We also do not commute (pointer + offset).
4813   virtual bool IsCommutative() const V8_OVERRIDE {
4814     return !representation().IsTagged() && !representation().IsExternal();
4815   }
4816
4817   virtual HValue* Canonicalize() V8_OVERRIDE;
4818
4819   virtual bool TryDecompose(DecompositionResult* decomposition) V8_OVERRIDE {
4820     if (left()->IsInteger32Constant()) {
4821       decomposition->Apply(right(), left()->GetInteger32Constant());
4822       return true;
4823     } else if (right()->IsInteger32Constant()) {
4824       decomposition->Apply(left(), right()->GetInteger32Constant());
4825       return true;
4826     } else {
4827       return false;
4828     }
4829   }
4830
4831   virtual void RepresentationChanged(Representation to) V8_OVERRIDE {
4832     if (to.IsTagged() &&
4833         (left()->ToNumberCanBeObserved() || right()->ToNumberCanBeObserved() ||
4834          left()->ToStringCanBeObserved() || right()->ToStringCanBeObserved())) {
4835       SetAllSideEffects();
4836       ClearFlag(kUseGVN);
4837     } else {
4838       ClearAllSideEffects();
4839       SetFlag(kUseGVN);
4840     }
4841     if (to.IsTagged()) {
4842       SetChangesFlag(kNewSpacePromotion);
4843       ClearFlag(kAllowUndefinedAsNaN);
4844     }
4845   }
4846
4847   virtual Representation RepresentationFromInputs() V8_OVERRIDE;
4848
4849   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE;
4850
4851   DECLARE_CONCRETE_INSTRUCTION(Add)
4852
4853  protected:
4854   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
4855
4856   virtual Range* InferRange(Zone* zone) V8_OVERRIDE;
4857
4858  private:
4859   HAdd(HValue* context, HValue* left, HValue* right)
4860       : HArithmeticBinaryOperation(context, left, right) {
4861     SetFlag(kCanOverflow);
4862   }
4863 };
4864
4865
4866 class HSub V8_FINAL : public HArithmeticBinaryOperation {
4867  public:
4868   static HInstruction* New(Zone* zone,
4869                            HValue* context,
4870                            HValue* left,
4871                            HValue* right);
4872
4873   virtual HValue* Canonicalize() V8_OVERRIDE;
4874
4875   virtual bool TryDecompose(DecompositionResult* decomposition) V8_OVERRIDE {
4876     if (right()->IsInteger32Constant()) {
4877       decomposition->Apply(left(), -right()->GetInteger32Constant());
4878       return true;
4879     } else {
4880       return false;
4881     }
4882   }
4883
4884   DECLARE_CONCRETE_INSTRUCTION(Sub)
4885
4886  protected:
4887   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
4888
4889   virtual Range* InferRange(Zone* zone) V8_OVERRIDE;
4890
4891  private:
4892   HSub(HValue* context, HValue* left, HValue* right)
4893       : HArithmeticBinaryOperation(context, left, right) {
4894     SetFlag(kCanOverflow);
4895   }
4896 };
4897
4898
4899 class HMul V8_FINAL : public HArithmeticBinaryOperation {
4900  public:
4901   static HInstruction* New(Zone* zone,
4902                            HValue* context,
4903                            HValue* left,
4904                            HValue* right);
4905
4906   static HInstruction* NewImul(Zone* zone,
4907                          HValue* context,
4908                          HValue* left,
4909                          HValue* right) {
4910     HInstruction* instr = HMul::New(zone, context, left, right);
4911     if (!instr->IsMul()) return instr;
4912     HMul* mul = HMul::cast(instr);
4913     // TODO(mstarzinger): Prevent bailout on minus zero for imul.
4914     mul->AssumeRepresentation(Representation::Integer32());
4915     mul->ClearFlag(HValue::kCanOverflow);
4916     return mul;
4917   }
4918
4919   virtual HValue* Canonicalize() V8_OVERRIDE;
4920
4921   // Only commutative if it is certain that not two objects are multiplicated.
4922   virtual bool IsCommutative() const V8_OVERRIDE {
4923     return !representation().IsTagged();
4924   }
4925
4926   virtual void UpdateRepresentation(Representation new_rep,
4927                                     HInferRepresentationPhase* h_infer,
4928                                     const char* reason) V8_OVERRIDE {
4929     HArithmeticBinaryOperation::UpdateRepresentation(new_rep, h_infer, reason);
4930   }
4931
4932   bool MulMinusOne();
4933
4934   DECLARE_CONCRETE_INSTRUCTION(Mul)
4935
4936  protected:
4937   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
4938
4939   virtual Range* InferRange(Zone* zone) V8_OVERRIDE;
4940
4941  private:
4942   HMul(HValue* context, HValue* left, HValue* right)
4943       : HArithmeticBinaryOperation(context, left, right) {
4944     SetFlag(kCanOverflow);
4945   }
4946 };
4947
4948
4949 class HMod V8_FINAL : public HArithmeticBinaryOperation {
4950  public:
4951   static HInstruction* New(Zone* zone,
4952                            HValue* context,
4953                            HValue* left,
4954                            HValue* right);
4955
4956   virtual HValue* Canonicalize() V8_OVERRIDE;
4957
4958   virtual void UpdateRepresentation(Representation new_rep,
4959                                     HInferRepresentationPhase* h_infer,
4960                                     const char* reason) V8_OVERRIDE {
4961     if (new_rep.IsSmi()) new_rep = Representation::Integer32();
4962     HArithmeticBinaryOperation::UpdateRepresentation(new_rep, h_infer, reason);
4963   }
4964
4965   DECLARE_CONCRETE_INSTRUCTION(Mod)
4966
4967  protected:
4968   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
4969
4970   virtual Range* InferRange(Zone* zone) V8_OVERRIDE;
4971
4972  private:
4973   HMod(HValue* context,
4974        HValue* left,
4975        HValue* right) : HArithmeticBinaryOperation(context, left, right) {
4976     SetFlag(kCanBeDivByZero);
4977     SetFlag(kCanOverflow);
4978     SetFlag(kLeftCanBeNegative);
4979   }
4980 };
4981
4982
4983 class HDiv V8_FINAL : public HArithmeticBinaryOperation {
4984  public:
4985   static HInstruction* New(Zone* zone,
4986                            HValue* context,
4987                            HValue* left,
4988                            HValue* right);
4989
4990   virtual HValue* Canonicalize() V8_OVERRIDE;
4991
4992   virtual void UpdateRepresentation(Representation new_rep,
4993                                     HInferRepresentationPhase* h_infer,
4994                                     const char* reason) V8_OVERRIDE {
4995     if (new_rep.IsSmi()) new_rep = Representation::Integer32();
4996     HArithmeticBinaryOperation::UpdateRepresentation(new_rep, h_infer, reason);
4997   }
4998
4999   DECLARE_CONCRETE_INSTRUCTION(Div)
5000
5001  protected:
5002   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
5003
5004   virtual Range* InferRange(Zone* zone) V8_OVERRIDE;
5005
5006  private:
5007   HDiv(HValue* context, HValue* left, HValue* right)
5008       : HArithmeticBinaryOperation(context, left, right) {
5009     SetFlag(kCanBeDivByZero);
5010     SetFlag(kCanOverflow);
5011   }
5012 };
5013
5014
5015 class HMathMinMax V8_FINAL : public HArithmeticBinaryOperation {
5016  public:
5017   enum Operation { kMathMin, kMathMax };
5018
5019   static HInstruction* New(Zone* zone,
5020                            HValue* context,
5021                            HValue* left,
5022                            HValue* right,
5023                            Operation op);
5024
5025   virtual Representation observed_input_representation(int index) V8_OVERRIDE {
5026     return RequiredInputRepresentation(index);
5027   }
5028
5029   virtual void InferRepresentation(
5030       HInferRepresentationPhase* h_infer) V8_OVERRIDE;
5031
5032   virtual Representation RepresentationFromInputs() V8_OVERRIDE {
5033     Representation left_rep = left()->representation();
5034     Representation right_rep = right()->representation();
5035     Representation result = Representation::Smi();
5036     result = result.generalize(left_rep);
5037     result = result.generalize(right_rep);
5038     if (result.IsTagged()) return Representation::Double();
5039     return result;
5040   }
5041
5042   virtual bool IsCommutative() const V8_OVERRIDE { return true; }
5043
5044   Operation operation() { return operation_; }
5045
5046   DECLARE_CONCRETE_INSTRUCTION(MathMinMax)
5047
5048  protected:
5049   virtual bool DataEquals(HValue* other) V8_OVERRIDE {
5050     return other->IsMathMinMax() &&
5051         HMathMinMax::cast(other)->operation_ == operation_;
5052   }
5053
5054   virtual Range* InferRange(Zone* zone) V8_OVERRIDE;
5055
5056  private:
5057   HMathMinMax(HValue* context, HValue* left, HValue* right, Operation op)
5058       : HArithmeticBinaryOperation(context, left, right),
5059         operation_(op) { }
5060
5061   Operation operation_;
5062 };
5063
5064
5065 class HBitwise V8_FINAL : public HBitwiseBinaryOperation {
5066  public:
5067   static HInstruction* New(Zone* zone,
5068                            HValue* context,
5069                            Token::Value op,
5070                            HValue* left,
5071                            HValue* right);
5072
5073   Token::Value op() const { return op_; }
5074
5075   virtual bool IsCommutative() const V8_OVERRIDE { return true; }
5076
5077   virtual HValue* Canonicalize() V8_OVERRIDE;
5078
5079   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
5080
5081   DECLARE_CONCRETE_INSTRUCTION(Bitwise)
5082
5083  protected:
5084   virtual bool DataEquals(HValue* other) V8_OVERRIDE {
5085     return op() == HBitwise::cast(other)->op();
5086   }
5087
5088   virtual Range* InferRange(Zone* zone) V8_OVERRIDE;
5089
5090  private:
5091   HBitwise(HValue* context,
5092            Token::Value op,
5093            HValue* left,
5094            HValue* right)
5095       : HBitwiseBinaryOperation(context, left, right),
5096         op_(op) {
5097     DCHECK(op == Token::BIT_AND || op == Token::BIT_OR || op == Token::BIT_XOR);
5098     // BIT_AND with a smi-range positive value will always unset the
5099     // entire sign-extension of the smi-sign.
5100     if (op == Token::BIT_AND &&
5101         ((left->IsConstant() &&
5102           left->representation().IsSmi() &&
5103           HConstant::cast(left)->Integer32Value() >= 0) ||
5104          (right->IsConstant() &&
5105           right->representation().IsSmi() &&
5106           HConstant::cast(right)->Integer32Value() >= 0))) {
5107       SetFlag(kTruncatingToSmi);
5108       SetFlag(kTruncatingToInt32);
5109     // BIT_OR with a smi-range negative value will always set the entire
5110     // sign-extension of the smi-sign.
5111     } else if (op == Token::BIT_OR &&
5112         ((left->IsConstant() &&
5113           left->representation().IsSmi() &&
5114           HConstant::cast(left)->Integer32Value() < 0) ||
5115          (right->IsConstant() &&
5116           right->representation().IsSmi() &&
5117           HConstant::cast(right)->Integer32Value() < 0))) {
5118       SetFlag(kTruncatingToSmi);
5119       SetFlag(kTruncatingToInt32);
5120     }
5121   }
5122
5123   Token::Value op_;
5124 };
5125
5126
5127 class HShl V8_FINAL : public HBitwiseBinaryOperation {
5128  public:
5129   static HInstruction* New(Zone* zone,
5130                            HValue* context,
5131                            HValue* left,
5132                            HValue* right);
5133
5134   virtual Range* InferRange(Zone* zone) V8_OVERRIDE;
5135
5136   virtual void UpdateRepresentation(Representation new_rep,
5137                                     HInferRepresentationPhase* h_infer,
5138                                     const char* reason) V8_OVERRIDE {
5139     if (new_rep.IsSmi() &&
5140         !(right()->IsInteger32Constant() &&
5141           right()->GetInteger32Constant() >= 0)) {
5142       new_rep = Representation::Integer32();
5143     }
5144     HBitwiseBinaryOperation::UpdateRepresentation(new_rep, h_infer, reason);
5145   }
5146
5147   DECLARE_CONCRETE_INSTRUCTION(Shl)
5148
5149  protected:
5150   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
5151
5152  private:
5153   HShl(HValue* context, HValue* left, HValue* right)
5154       : HBitwiseBinaryOperation(context, left, right) { }
5155 };
5156
5157
5158 class HShr V8_FINAL : public HBitwiseBinaryOperation {
5159  public:
5160   static HInstruction* New(Zone* zone,
5161                            HValue* context,
5162                            HValue* left,
5163                            HValue* right);
5164
5165   virtual bool TryDecompose(DecompositionResult* decomposition) V8_OVERRIDE {
5166     if (right()->IsInteger32Constant()) {
5167       if (decomposition->Apply(left(), 0, right()->GetInteger32Constant())) {
5168         // This is intended to look for HAdd and HSub, to handle compounds
5169         // like ((base + offset) >> scale) with one single decomposition.
5170         left()->TryDecompose(decomposition);
5171         return true;
5172       }
5173     }
5174     return false;
5175   }
5176
5177   virtual Range* InferRange(Zone* zone) V8_OVERRIDE;
5178
5179   virtual void UpdateRepresentation(Representation new_rep,
5180                                     HInferRepresentationPhase* h_infer,
5181                                     const char* reason) V8_OVERRIDE {
5182     if (new_rep.IsSmi()) new_rep = Representation::Integer32();
5183     HBitwiseBinaryOperation::UpdateRepresentation(new_rep, h_infer, reason);
5184   }
5185
5186   DECLARE_CONCRETE_INSTRUCTION(Shr)
5187
5188  protected:
5189   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
5190
5191  private:
5192   HShr(HValue* context, HValue* left, HValue* right)
5193       : HBitwiseBinaryOperation(context, left, right) { }
5194 };
5195
5196
5197 class HSar V8_FINAL : public HBitwiseBinaryOperation {
5198  public:
5199   static HInstruction* New(Zone* zone,
5200                            HValue* context,
5201                            HValue* left,
5202                            HValue* right);
5203
5204   virtual bool TryDecompose(DecompositionResult* decomposition) V8_OVERRIDE {
5205     if (right()->IsInteger32Constant()) {
5206       if (decomposition->Apply(left(), 0, right()->GetInteger32Constant())) {
5207         // This is intended to look for HAdd and HSub, to handle compounds
5208         // like ((base + offset) >> scale) with one single decomposition.
5209         left()->TryDecompose(decomposition);
5210         return true;
5211       }
5212     }
5213     return false;
5214   }
5215
5216   virtual Range* InferRange(Zone* zone) V8_OVERRIDE;
5217
5218   virtual void UpdateRepresentation(Representation new_rep,
5219                                     HInferRepresentationPhase* h_infer,
5220                                     const char* reason) V8_OVERRIDE {
5221     if (new_rep.IsSmi()) new_rep = Representation::Integer32();
5222     HBitwiseBinaryOperation::UpdateRepresentation(new_rep, h_infer, reason);
5223   }
5224
5225   DECLARE_CONCRETE_INSTRUCTION(Sar)
5226
5227  protected:
5228   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
5229
5230  private:
5231   HSar(HValue* context, HValue* left, HValue* right)
5232       : HBitwiseBinaryOperation(context, left, right) { }
5233 };
5234
5235
5236 class HRor V8_FINAL : public HBitwiseBinaryOperation {
5237  public:
5238   static HInstruction* New(Zone* zone,
5239                            HValue* context,
5240                            HValue* left,
5241                            HValue* right) {
5242     return new(zone) HRor(context, left, right);
5243   }
5244
5245   virtual void UpdateRepresentation(Representation new_rep,
5246                                     HInferRepresentationPhase* h_infer,
5247                                     const char* reason) V8_OVERRIDE {
5248     if (new_rep.IsSmi()) new_rep = Representation::Integer32();
5249     HBitwiseBinaryOperation::UpdateRepresentation(new_rep, h_infer, reason);
5250   }
5251
5252   DECLARE_CONCRETE_INSTRUCTION(Ror)
5253
5254  protected:
5255   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
5256
5257  private:
5258   HRor(HValue* context, HValue* left, HValue* right)
5259        : HBitwiseBinaryOperation(context, left, right) {
5260     ChangeRepresentation(Representation::Integer32());
5261   }
5262 };
5263
5264
5265 class HOsrEntry V8_FINAL : public HTemplateInstruction<0> {
5266  public:
5267   DECLARE_INSTRUCTION_FACTORY_P1(HOsrEntry, BailoutId);
5268
5269   BailoutId ast_id() const { return ast_id_; }
5270
5271   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
5272     return Representation::None();
5273   }
5274
5275   DECLARE_CONCRETE_INSTRUCTION(OsrEntry)
5276
5277  private:
5278   explicit HOsrEntry(BailoutId ast_id) : ast_id_(ast_id) {
5279     SetChangesFlag(kOsrEntries);
5280     SetChangesFlag(kNewSpacePromotion);
5281   }
5282
5283   BailoutId ast_id_;
5284 };
5285
5286
5287 class HParameter V8_FINAL : public HTemplateInstruction<0> {
5288  public:
5289   enum ParameterKind {
5290     STACK_PARAMETER,
5291     REGISTER_PARAMETER
5292   };
5293
5294   DECLARE_INSTRUCTION_FACTORY_P1(HParameter, unsigned);
5295   DECLARE_INSTRUCTION_FACTORY_P2(HParameter, unsigned, ParameterKind);
5296   DECLARE_INSTRUCTION_FACTORY_P3(HParameter, unsigned, ParameterKind,
5297                                  Representation);
5298
5299   unsigned index() const { return index_; }
5300   ParameterKind kind() const { return kind_; }
5301
5302   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
5303
5304   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
5305     return Representation::None();
5306   }
5307
5308   DECLARE_CONCRETE_INSTRUCTION(Parameter)
5309
5310  private:
5311   explicit HParameter(unsigned index,
5312                       ParameterKind kind = STACK_PARAMETER)
5313       : index_(index),
5314         kind_(kind) {
5315     set_representation(Representation::Tagged());
5316   }
5317
5318   explicit HParameter(unsigned index,
5319                       ParameterKind kind,
5320                       Representation r)
5321       : index_(index),
5322         kind_(kind) {
5323     set_representation(r);
5324   }
5325
5326   unsigned index_;
5327   ParameterKind kind_;
5328 };
5329
5330
5331 class HCallStub V8_FINAL : public HUnaryCall {
5332  public:
5333   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P2(HCallStub, CodeStub::Major, int);
5334   CodeStub::Major major_key() { return major_key_; }
5335
5336   HValue* context() { return value(); }
5337
5338   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
5339
5340   DECLARE_CONCRETE_INSTRUCTION(CallStub)
5341
5342  private:
5343   HCallStub(HValue* context, CodeStub::Major major_key, int argument_count)
5344       : HUnaryCall(context, argument_count),
5345         major_key_(major_key) {
5346   }
5347
5348   CodeStub::Major major_key_;
5349 };
5350
5351
5352 class HUnknownOSRValue V8_FINAL : public HTemplateInstruction<0> {
5353  public:
5354   DECLARE_INSTRUCTION_FACTORY_P2(HUnknownOSRValue, HEnvironment*, int);
5355
5356   virtual OStream& PrintDataTo(OStream& os) const;  // NOLINT
5357
5358   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
5359     return Representation::None();
5360   }
5361
5362   void set_incoming_value(HPhi* value) { incoming_value_ = value; }
5363   HPhi* incoming_value() { return incoming_value_; }
5364   HEnvironment *environment() { return environment_; }
5365   int index() { return index_; }
5366
5367   virtual Representation KnownOptimalRepresentation() V8_OVERRIDE {
5368     if (incoming_value_ == NULL) return Representation::None();
5369     return incoming_value_->KnownOptimalRepresentation();
5370   }
5371
5372   DECLARE_CONCRETE_INSTRUCTION(UnknownOSRValue)
5373
5374  private:
5375   HUnknownOSRValue(HEnvironment* environment, int index)
5376       : environment_(environment),
5377         index_(index),
5378         incoming_value_(NULL) {
5379     set_representation(Representation::Tagged());
5380   }
5381
5382   HEnvironment* environment_;
5383   int index_;
5384   HPhi* incoming_value_;
5385 };
5386
5387
5388 class HLoadGlobalCell V8_FINAL : public HTemplateInstruction<0> {
5389  public:
5390   DECLARE_INSTRUCTION_FACTORY_P2(HLoadGlobalCell, Handle<Cell>,
5391                                  PropertyDetails);
5392
5393   Unique<Cell> cell() const { return cell_; }
5394   bool RequiresHoleCheck() const;
5395
5396   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
5397
5398   virtual intptr_t Hashcode() V8_OVERRIDE {
5399     return cell_.Hashcode();
5400   }
5401
5402   virtual void FinalizeUniqueness() V8_OVERRIDE {
5403     cell_ = Unique<Cell>(cell_.handle());
5404   }
5405
5406   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
5407     return Representation::None();
5408   }
5409
5410   DECLARE_CONCRETE_INSTRUCTION(LoadGlobalCell)
5411
5412  protected:
5413   virtual bool DataEquals(HValue* other) V8_OVERRIDE {
5414     return cell_ == HLoadGlobalCell::cast(other)->cell_;
5415   }
5416
5417  private:
5418   HLoadGlobalCell(Handle<Cell> cell, PropertyDetails details)
5419     : cell_(Unique<Cell>::CreateUninitialized(cell)), details_(details) {
5420     set_representation(Representation::Tagged());
5421     SetFlag(kUseGVN);
5422     SetDependsOnFlag(kGlobalVars);
5423   }
5424
5425   virtual bool IsDeletable() const V8_OVERRIDE { return !RequiresHoleCheck(); }
5426
5427   Unique<Cell> cell_;
5428   PropertyDetails details_;
5429 };
5430
5431
5432 class HLoadGlobalGeneric V8_FINAL : public HTemplateInstruction<2> {
5433  public:
5434   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P3(HLoadGlobalGeneric, HValue*,
5435                                               Handle<String>, bool);
5436
5437   HValue* context() { return OperandAt(0); }
5438   HValue* global_object() { return OperandAt(1); }
5439   Handle<String> name() const { return name_; }
5440   bool for_typeof() const { return for_typeof_; }
5441   int slot() const {
5442     DCHECK(FLAG_vector_ics &&
5443            slot_ != FeedbackSlotInterface::kInvalidFeedbackSlot);
5444     return slot_;
5445   }
5446   Handle<FixedArray> feedback_vector() const { return feedback_vector_; }
5447   void SetVectorAndSlot(Handle<FixedArray> vector, int slot) {
5448     DCHECK(FLAG_vector_ics);
5449     feedback_vector_ = vector;
5450     slot_ = slot;
5451   }
5452
5453   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
5454
5455   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
5456     return Representation::Tagged();
5457   }
5458
5459   DECLARE_CONCRETE_INSTRUCTION(LoadGlobalGeneric)
5460
5461  private:
5462   HLoadGlobalGeneric(HValue* context, HValue* global_object,
5463                      Handle<String> name, bool for_typeof)
5464       : name_(name), for_typeof_(for_typeof),
5465         slot_(FeedbackSlotInterface::kInvalidFeedbackSlot) {
5466     SetOperandAt(0, context);
5467     SetOperandAt(1, global_object);
5468     set_representation(Representation::Tagged());
5469     SetAllSideEffects();
5470   }
5471
5472   Handle<String> name_;
5473   bool for_typeof_;
5474   Handle<FixedArray> feedback_vector_;
5475   int slot_;
5476 };
5477
5478
5479 class HAllocate V8_FINAL : public HTemplateInstruction<2> {
5480  public:
5481   static bool CompatibleInstanceTypes(InstanceType type1,
5482                                       InstanceType type2) {
5483     return ComputeFlags(TENURED, type1) == ComputeFlags(TENURED, type2) &&
5484         ComputeFlags(NOT_TENURED, type1) == ComputeFlags(NOT_TENURED, type2);
5485   }
5486
5487   static HAllocate* New(Zone* zone,
5488                         HValue* context,
5489                         HValue* size,
5490                         HType type,
5491                         PretenureFlag pretenure_flag,
5492                         InstanceType instance_type,
5493                         Handle<AllocationSite> allocation_site =
5494                             Handle<AllocationSite>::null()) {
5495     return new(zone) HAllocate(context, size, type, pretenure_flag,
5496         instance_type, allocation_site);
5497   }
5498
5499   // Maximum instance size for which allocations will be inlined.
5500   static const int kMaxInlineSize = 64 * kPointerSize;
5501
5502   HValue* context() const { return OperandAt(0); }
5503   HValue* size() const { return OperandAt(1); }
5504
5505   bool has_size_upper_bound() { return size_upper_bound_ != NULL; }
5506   HConstant* size_upper_bound() { return size_upper_bound_; }
5507   void set_size_upper_bound(HConstant* value) {
5508     DCHECK(size_upper_bound_ == NULL);
5509     size_upper_bound_ = value;
5510   }
5511
5512   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
5513     if (index == 0) {
5514       return Representation::Tagged();
5515     } else {
5516       return Representation::Integer32();
5517     }
5518   }
5519
5520   virtual Handle<Map> GetMonomorphicJSObjectMap() {
5521     return known_initial_map_;
5522   }
5523
5524   void set_known_initial_map(Handle<Map> known_initial_map) {
5525     known_initial_map_ = known_initial_map;
5526   }
5527
5528   bool IsNewSpaceAllocation() const {
5529     return (flags_ & ALLOCATE_IN_NEW_SPACE) != 0;
5530   }
5531
5532   bool IsOldDataSpaceAllocation() const {
5533     return (flags_ & ALLOCATE_IN_OLD_DATA_SPACE) != 0;
5534   }
5535
5536   bool IsOldPointerSpaceAllocation() const {
5537     return (flags_ & ALLOCATE_IN_OLD_POINTER_SPACE) != 0;
5538   }
5539
5540   bool MustAllocateDoubleAligned() const {
5541     return (flags_ & ALLOCATE_DOUBLE_ALIGNED) != 0;
5542   }
5543
5544   bool MustPrefillWithFiller() const {
5545     return (flags_ & PREFILL_WITH_FILLER) != 0;
5546   }
5547
5548   void MakePrefillWithFiller() {
5549     flags_ = static_cast<HAllocate::Flags>(flags_ | PREFILL_WITH_FILLER);
5550   }
5551
5552   bool MustClearNextMapWord() const {
5553     return (flags_ & CLEAR_NEXT_MAP_WORD) != 0;
5554   }
5555
5556   void MakeDoubleAligned() {
5557     flags_ = static_cast<HAllocate::Flags>(flags_ | ALLOCATE_DOUBLE_ALIGNED);
5558   }
5559
5560   virtual bool HandleSideEffectDominator(GVNFlag side_effect,
5561                                          HValue* dominator) V8_OVERRIDE;
5562
5563   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
5564
5565   DECLARE_CONCRETE_INSTRUCTION(Allocate)
5566
5567  private:
5568   enum Flags {
5569     ALLOCATE_IN_NEW_SPACE = 1 << 0,
5570     ALLOCATE_IN_OLD_DATA_SPACE = 1 << 1,
5571     ALLOCATE_IN_OLD_POINTER_SPACE = 1 << 2,
5572     ALLOCATE_DOUBLE_ALIGNED = 1 << 3,
5573     PREFILL_WITH_FILLER = 1 << 4,
5574     CLEAR_NEXT_MAP_WORD = 1 << 5
5575   };
5576
5577   HAllocate(HValue* context,
5578             HValue* size,
5579             HType type,
5580             PretenureFlag pretenure_flag,
5581             InstanceType instance_type,
5582             Handle<AllocationSite> allocation_site =
5583                 Handle<AllocationSite>::null())
5584       : HTemplateInstruction<2>(type),
5585         flags_(ComputeFlags(pretenure_flag, instance_type)),
5586         dominating_allocate_(NULL),
5587         filler_free_space_size_(NULL),
5588         size_upper_bound_(NULL) {
5589     SetOperandAt(0, context);
5590     UpdateSize(size);
5591     set_representation(Representation::Tagged());
5592     SetFlag(kTrackSideEffectDominators);
5593     SetChangesFlag(kNewSpacePromotion);
5594     SetDependsOnFlag(kNewSpacePromotion);
5595
5596     if (FLAG_trace_pretenuring) {
5597       PrintF("HAllocate with AllocationSite %p %s\n",
5598              allocation_site.is_null()
5599                  ? static_cast<void*>(NULL)
5600                  : static_cast<void*>(*allocation_site),
5601              pretenure_flag == TENURED ? "tenured" : "not tenured");
5602     }
5603   }
5604
5605   static Flags ComputeFlags(PretenureFlag pretenure_flag,
5606                             InstanceType instance_type) {
5607     Flags flags = pretenure_flag == TENURED
5608         ? (Heap::TargetSpaceId(instance_type) == OLD_POINTER_SPACE
5609             ? ALLOCATE_IN_OLD_POINTER_SPACE : ALLOCATE_IN_OLD_DATA_SPACE)
5610         : ALLOCATE_IN_NEW_SPACE;
5611     if (instance_type == FIXED_DOUBLE_ARRAY_TYPE) {
5612       flags = static_cast<Flags>(flags | ALLOCATE_DOUBLE_ALIGNED);
5613     }
5614     // We have to fill the allocated object with one word fillers if we do
5615     // not use allocation folding since some allocations may depend on each
5616     // other, i.e., have a pointer to each other. A GC in between these
5617     // allocations may leave such objects behind in a not completely initialized
5618     // state.
5619     if (!FLAG_use_gvn || !FLAG_use_allocation_folding) {
5620       flags = static_cast<Flags>(flags | PREFILL_WITH_FILLER);
5621     }
5622     if (pretenure_flag == NOT_TENURED &&
5623         AllocationSite::CanTrack(instance_type)) {
5624       flags = static_cast<Flags>(flags | CLEAR_NEXT_MAP_WORD);
5625     }
5626     return flags;
5627   }
5628
5629   void UpdateClearNextMapWord(bool clear_next_map_word) {
5630     flags_ = static_cast<Flags>(clear_next_map_word
5631                                 ? flags_ | CLEAR_NEXT_MAP_WORD
5632                                 : flags_ & ~CLEAR_NEXT_MAP_WORD);
5633   }
5634
5635   void UpdateSize(HValue* size) {
5636     SetOperandAt(1, size);
5637     if (size->IsInteger32Constant()) {
5638       size_upper_bound_ = HConstant::cast(size);
5639     } else {
5640       size_upper_bound_ = NULL;
5641     }
5642   }
5643
5644   HAllocate* GetFoldableDominator(HAllocate* dominator);
5645
5646   void UpdateFreeSpaceFiller(int32_t filler_size);
5647
5648   void CreateFreeSpaceFiller(int32_t filler_size);
5649
5650   bool IsFoldable(HAllocate* allocate) {
5651     return (IsNewSpaceAllocation() && allocate->IsNewSpaceAllocation()) ||
5652         (IsOldDataSpaceAllocation() && allocate->IsOldDataSpaceAllocation()) ||
5653         (IsOldPointerSpaceAllocation() &&
5654             allocate->IsOldPointerSpaceAllocation());
5655   }
5656
5657   void ClearNextMapWord(int offset);
5658
5659   Flags flags_;
5660   Handle<Map> known_initial_map_;
5661   HAllocate* dominating_allocate_;
5662   HStoreNamedField* filler_free_space_size_;
5663   HConstant* size_upper_bound_;
5664 };
5665
5666
5667 class HStoreCodeEntry V8_FINAL: public HTemplateInstruction<2> {
5668  public:
5669   static HStoreCodeEntry* New(Zone* zone,
5670                               HValue* context,
5671                               HValue* function,
5672                               HValue* code) {
5673     return new(zone) HStoreCodeEntry(function, code);
5674   }
5675
5676   virtual Representation RequiredInputRepresentation(int index) {
5677     return Representation::Tagged();
5678   }
5679
5680   HValue* function() { return OperandAt(0); }
5681   HValue* code_object() { return OperandAt(1); }
5682
5683   DECLARE_CONCRETE_INSTRUCTION(StoreCodeEntry)
5684
5685  private:
5686   HStoreCodeEntry(HValue* function, HValue* code) {
5687     SetOperandAt(0, function);
5688     SetOperandAt(1, code);
5689   }
5690 };
5691
5692
5693 class HInnerAllocatedObject V8_FINAL : public HTemplateInstruction<2> {
5694  public:
5695   static HInnerAllocatedObject* New(Zone* zone,
5696                                     HValue* context,
5697                                     HValue* value,
5698                                     HValue* offset,
5699                                     HType type) {
5700     return new(zone) HInnerAllocatedObject(value, offset, type);
5701   }
5702
5703   HValue* base_object() const { return OperandAt(0); }
5704   HValue* offset() const { return OperandAt(1); }
5705
5706   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
5707     return index == 0 ? Representation::Tagged() : Representation::Integer32();
5708   }
5709
5710   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
5711
5712   DECLARE_CONCRETE_INSTRUCTION(InnerAllocatedObject)
5713
5714  private:
5715   HInnerAllocatedObject(HValue* value,
5716                         HValue* offset,
5717                         HType type) : HTemplateInstruction<2>(type) {
5718     DCHECK(value->IsAllocate());
5719     DCHECK(type.IsHeapObject());
5720     SetOperandAt(0, value);
5721     SetOperandAt(1, offset);
5722     set_representation(Representation::Tagged());
5723   }
5724 };
5725
5726
5727 inline bool StoringValueNeedsWriteBarrier(HValue* value) {
5728   return !value->type().IsSmi()
5729       && !value->type().IsNull()
5730       && !value->type().IsBoolean()
5731       && !value->type().IsUndefined()
5732       && !(value->IsConstant() && HConstant::cast(value)->ImmortalImmovable());
5733 }
5734
5735
5736 inline bool ReceiverObjectNeedsWriteBarrier(HValue* object,
5737                                             HValue* value,
5738                                             HValue* dominator) {
5739   while (object->IsInnerAllocatedObject()) {
5740     object = HInnerAllocatedObject::cast(object)->base_object();
5741   }
5742   if (object->IsConstant() && HConstant::cast(object)->IsCell()) {
5743     return false;
5744   }
5745   if (object->IsConstant() &&
5746       HConstant::cast(object)->HasExternalReferenceValue()) {
5747     // Stores to external references require no write barriers
5748     return false;
5749   }
5750   // We definitely need a write barrier unless the object is the allocation
5751   // dominator.
5752   if (object == dominator && object->IsAllocate()) {
5753     // Stores to new space allocations require no write barriers.
5754     if (HAllocate::cast(object)->IsNewSpaceAllocation()) {
5755       return false;
5756     }
5757     // Stores to old space allocations require no write barriers if the value is
5758     // a constant provably not in new space.
5759     if (value->IsConstant() && HConstant::cast(value)->NotInNewSpace()) {
5760       return false;
5761     }
5762     // Stores to old space allocations require no write barriers if the value is
5763     // an old space allocation.
5764     while (value->IsInnerAllocatedObject()) {
5765       value = HInnerAllocatedObject::cast(value)->base_object();
5766     }
5767     if (value->IsAllocate() &&
5768         !HAllocate::cast(value)->IsNewSpaceAllocation()) {
5769       return false;
5770     }
5771   }
5772   return true;
5773 }
5774
5775
5776 inline PointersToHereCheck PointersToHereCheckForObject(HValue* object,
5777                                                         HValue* dominator) {
5778   while (object->IsInnerAllocatedObject()) {
5779     object = HInnerAllocatedObject::cast(object)->base_object();
5780   }
5781   if (object == dominator &&
5782       object->IsAllocate() &&
5783       HAllocate::cast(object)->IsNewSpaceAllocation()) {
5784     return kPointersToHereAreAlwaysInteresting;
5785   }
5786   return kPointersToHereMaybeInteresting;
5787 }
5788
5789
5790 class HStoreGlobalCell V8_FINAL : public HUnaryOperation {
5791  public:
5792   DECLARE_INSTRUCTION_FACTORY_P3(HStoreGlobalCell, HValue*,
5793                                  Handle<PropertyCell>, PropertyDetails);
5794
5795   Unique<PropertyCell> cell() const { return cell_; }
5796   bool RequiresHoleCheck() {
5797     return !details_.IsDontDelete() || details_.IsReadOnly();
5798   }
5799   bool NeedsWriteBarrier() {
5800     return StoringValueNeedsWriteBarrier(value());
5801   }
5802
5803   virtual void FinalizeUniqueness() V8_OVERRIDE {
5804     cell_ = Unique<PropertyCell>(cell_.handle());
5805   }
5806
5807   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
5808     return Representation::Tagged();
5809   }
5810   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
5811
5812   DECLARE_CONCRETE_INSTRUCTION(StoreGlobalCell)
5813
5814  private:
5815   HStoreGlobalCell(HValue* value,
5816                    Handle<PropertyCell> cell,
5817                    PropertyDetails details)
5818       : HUnaryOperation(value),
5819         cell_(Unique<PropertyCell>::CreateUninitialized(cell)),
5820         details_(details) {
5821     SetChangesFlag(kGlobalVars);
5822   }
5823
5824   Unique<PropertyCell> cell_;
5825   PropertyDetails details_;
5826 };
5827
5828
5829 class HLoadContextSlot V8_FINAL : public HUnaryOperation {
5830  public:
5831   enum Mode {
5832     // Perform a normal load of the context slot without checking its value.
5833     kNoCheck,
5834     // Load and check the value of the context slot. Deoptimize if it's the
5835     // hole value. This is used for checking for loading of uninitialized
5836     // harmony bindings where we deoptimize into full-codegen generated code
5837     // which will subsequently throw a reference error.
5838     kCheckDeoptimize,
5839     // Load and check the value of the context slot. Return undefined if it's
5840     // the hole value. This is used for non-harmony const assignments
5841     kCheckReturnUndefined
5842   };
5843
5844   HLoadContextSlot(HValue* context, int slot_index, Mode mode)
5845       : HUnaryOperation(context), slot_index_(slot_index), mode_(mode) {
5846     set_representation(Representation::Tagged());
5847     SetFlag(kUseGVN);
5848     SetDependsOnFlag(kContextSlots);
5849   }
5850
5851   int slot_index() const { return slot_index_; }
5852   Mode mode() const { return mode_; }
5853
5854   bool DeoptimizesOnHole() {
5855     return mode_ == kCheckDeoptimize;
5856   }
5857
5858   bool RequiresHoleCheck() const {
5859     return mode_ != kNoCheck;
5860   }
5861
5862   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
5863     return Representation::Tagged();
5864   }
5865
5866   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
5867
5868   DECLARE_CONCRETE_INSTRUCTION(LoadContextSlot)
5869
5870  protected:
5871   virtual bool DataEquals(HValue* other) V8_OVERRIDE {
5872     HLoadContextSlot* b = HLoadContextSlot::cast(other);
5873     return (slot_index() == b->slot_index());
5874   }
5875
5876  private:
5877   virtual bool IsDeletable() const V8_OVERRIDE { return !RequiresHoleCheck(); }
5878
5879   int slot_index_;
5880   Mode mode_;
5881 };
5882
5883
5884 class HStoreContextSlot V8_FINAL : public HTemplateInstruction<2> {
5885  public:
5886   enum Mode {
5887     // Perform a normal store to the context slot without checking its previous
5888     // value.
5889     kNoCheck,
5890     // Check the previous value of the context slot and deoptimize if it's the
5891     // hole value. This is used for checking for assignments to uninitialized
5892     // harmony bindings where we deoptimize into full-codegen generated code
5893     // which will subsequently throw a reference error.
5894     kCheckDeoptimize,
5895     // Check the previous value and ignore assignment if it isn't a hole value
5896     kCheckIgnoreAssignment
5897   };
5898
5899   DECLARE_INSTRUCTION_FACTORY_P4(HStoreContextSlot, HValue*, int,
5900                                  Mode, HValue*);
5901
5902   HValue* context() const { return OperandAt(0); }
5903   HValue* value() const { return OperandAt(1); }
5904   int slot_index() const { return slot_index_; }
5905   Mode mode() const { return mode_; }
5906
5907   bool NeedsWriteBarrier() {
5908     return StoringValueNeedsWriteBarrier(value());
5909   }
5910
5911   bool DeoptimizesOnHole() {
5912     return mode_ == kCheckDeoptimize;
5913   }
5914
5915   bool RequiresHoleCheck() {
5916     return mode_ != kNoCheck;
5917   }
5918
5919   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
5920     return Representation::Tagged();
5921   }
5922
5923   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
5924
5925   DECLARE_CONCRETE_INSTRUCTION(StoreContextSlot)
5926
5927  private:
5928   HStoreContextSlot(HValue* context, int slot_index, Mode mode, HValue* value)
5929       : slot_index_(slot_index), mode_(mode) {
5930     SetOperandAt(0, context);
5931     SetOperandAt(1, value);
5932     SetChangesFlag(kContextSlots);
5933   }
5934
5935   int slot_index_;
5936   Mode mode_;
5937 };
5938
5939
5940 // Represents an access to a portion of an object, such as the map pointer,
5941 // array elements pointer, etc, but not accesses to array elements themselves.
5942 class HObjectAccess V8_FINAL {
5943  public:
5944   inline bool IsInobject() const {
5945     return portion() != kBackingStore && portion() != kExternalMemory;
5946   }
5947
5948   inline bool IsExternalMemory() const {
5949     return portion() == kExternalMemory;
5950   }
5951
5952   inline bool IsStringLength() const {
5953     return portion() == kStringLengths;
5954   }
5955
5956   inline bool IsMap() const {
5957     return portion() == kMaps;
5958   }
5959
5960   inline int offset() const {
5961     return OffsetField::decode(value_);
5962   }
5963
5964   inline Representation representation() const {
5965     return Representation::FromKind(RepresentationField::decode(value_));
5966   }
5967
5968   inline Handle<String> name() const {
5969     return name_;
5970   }
5971
5972   inline bool immutable() const {
5973     return ImmutableField::decode(value_);
5974   }
5975
5976   // Returns true if access is being made to an in-object property that
5977   // was already added to the object.
5978   inline bool existing_inobject_property() const {
5979     return ExistingInobjectPropertyField::decode(value_);
5980   }
5981
5982   inline HObjectAccess WithRepresentation(Representation representation) {
5983     return HObjectAccess(portion(), offset(), representation, name(),
5984                          immutable(), existing_inobject_property());
5985   }
5986
5987   static HObjectAccess ForHeapNumberValue() {
5988     return HObjectAccess(
5989         kDouble, HeapNumber::kValueOffset, Representation::Double());
5990   }
5991
5992   static HObjectAccess ForHeapNumberValueLowestBits() {
5993     return HObjectAccess(kDouble,
5994                          HeapNumber::kValueOffset,
5995                          Representation::Integer32());
5996   }
5997
5998   static HObjectAccess ForHeapNumberValueHighestBits() {
5999     return HObjectAccess(kDouble,
6000                          HeapNumber::kValueOffset + kIntSize,
6001                          Representation::Integer32());
6002   }
6003
6004   static HObjectAccess ForElementsPointer() {
6005     return HObjectAccess(kElementsPointer, JSObject::kElementsOffset);
6006   }
6007
6008   static HObjectAccess ForLiteralsPointer() {
6009     return HObjectAccess(kInobject, JSFunction::kLiteralsOffset);
6010   }
6011
6012   static HObjectAccess ForNextFunctionLinkPointer() {
6013     return HObjectAccess(kInobject, JSFunction::kNextFunctionLinkOffset);
6014   }
6015
6016   static HObjectAccess ForArrayLength(ElementsKind elements_kind) {
6017     return HObjectAccess(
6018         kArrayLengths,
6019         JSArray::kLengthOffset,
6020         IsFastElementsKind(elements_kind)
6021             ? Representation::Smi() : Representation::Tagged());
6022   }
6023
6024   static HObjectAccess ForAllocationSiteOffset(int offset);
6025
6026   static HObjectAccess ForAllocationSiteList() {
6027     return HObjectAccess(kExternalMemory, 0, Representation::Tagged(),
6028                          Handle<String>::null(), false, false);
6029   }
6030
6031   static HObjectAccess ForFixedArrayLength() {
6032     return HObjectAccess(
6033         kArrayLengths,
6034         FixedArray::kLengthOffset,
6035         Representation::Smi());
6036   }
6037
6038   static HObjectAccess ForStringHashField() {
6039     return HObjectAccess(kInobject,
6040                          String::kHashFieldOffset,
6041                          Representation::Integer32());
6042   }
6043
6044   static HObjectAccess ForStringLength() {
6045     STATIC_ASSERT(String::kMaxLength <= Smi::kMaxValue);
6046     return HObjectAccess(
6047         kStringLengths,
6048         String::kLengthOffset,
6049         Representation::Smi());
6050   }
6051
6052   static HObjectAccess ForConsStringFirst() {
6053     return HObjectAccess(kInobject, ConsString::kFirstOffset);
6054   }
6055
6056   static HObjectAccess ForConsStringSecond() {
6057     return HObjectAccess(kInobject, ConsString::kSecondOffset);
6058   }
6059
6060   static HObjectAccess ForPropertiesPointer() {
6061     return HObjectAccess(kInobject, JSObject::kPropertiesOffset);
6062   }
6063
6064   static HObjectAccess ForPrototypeOrInitialMap() {
6065     return HObjectAccess(kInobject, JSFunction::kPrototypeOrInitialMapOffset);
6066   }
6067
6068   static HObjectAccess ForSharedFunctionInfoPointer() {
6069     return HObjectAccess(kInobject, JSFunction::kSharedFunctionInfoOffset);
6070   }
6071
6072   static HObjectAccess ForCodeEntryPointer() {
6073     return HObjectAccess(kInobject, JSFunction::kCodeEntryOffset);
6074   }
6075
6076   static HObjectAccess ForCodeOffset() {
6077     return HObjectAccess(kInobject, SharedFunctionInfo::kCodeOffset);
6078   }
6079
6080   static HObjectAccess ForOptimizedCodeMap() {
6081     return HObjectAccess(kInobject,
6082                          SharedFunctionInfo::kOptimizedCodeMapOffset);
6083   }
6084
6085   static HObjectAccess ForFunctionContextPointer() {
6086     return HObjectAccess(kInobject, JSFunction::kContextOffset);
6087   }
6088
6089   static HObjectAccess ForMap() {
6090     return HObjectAccess(kMaps, JSObject::kMapOffset);
6091   }
6092
6093   static HObjectAccess ForMapAsInteger32() {
6094     return HObjectAccess(kMaps, JSObject::kMapOffset,
6095                          Representation::Integer32());
6096   }
6097
6098   static HObjectAccess ForMapInObjectProperties() {
6099     return HObjectAccess(kInobject,
6100                          Map::kInObjectPropertiesOffset,
6101                          Representation::UInteger8());
6102   }
6103
6104   static HObjectAccess ForMapInstanceType() {
6105     return HObjectAccess(kInobject,
6106                          Map::kInstanceTypeOffset,
6107                          Representation::UInteger8());
6108   }
6109
6110   static HObjectAccess ForMapInstanceSize() {
6111     return HObjectAccess(kInobject,
6112                          Map::kInstanceSizeOffset,
6113                          Representation::UInteger8());
6114   }
6115
6116   static HObjectAccess ForMapBitField() {
6117     return HObjectAccess(kInobject,
6118                          Map::kBitFieldOffset,
6119                          Representation::UInteger8());
6120   }
6121
6122   static HObjectAccess ForMapBitField2() {
6123     return HObjectAccess(kInobject,
6124                          Map::kBitField2Offset,
6125                          Representation::UInteger8());
6126   }
6127
6128   static HObjectAccess ForNameHashField() {
6129     return HObjectAccess(kInobject,
6130                          Name::kHashFieldOffset,
6131                          Representation::Integer32());
6132   }
6133
6134   static HObjectAccess ForMapInstanceTypeAndBitField() {
6135     STATIC_ASSERT((Map::kInstanceTypeAndBitFieldOffset & 1) == 0);
6136     // Ensure the two fields share one 16-bit word, endian-independent.
6137     STATIC_ASSERT((Map::kBitFieldOffset & ~1) ==
6138                   (Map::kInstanceTypeOffset & ~1));
6139     return HObjectAccess(kInobject,
6140                          Map::kInstanceTypeAndBitFieldOffset,
6141                          Representation::UInteger16());
6142   }
6143
6144   static HObjectAccess ForPropertyCellValue() {
6145     return HObjectAccess(kInobject, PropertyCell::kValueOffset);
6146   }
6147
6148   static HObjectAccess ForCellValue() {
6149     return HObjectAccess(kInobject, Cell::kValueOffset);
6150   }
6151
6152   static HObjectAccess ForAllocationMementoSite() {
6153     return HObjectAccess(kInobject, AllocationMemento::kAllocationSiteOffset);
6154   }
6155
6156   static HObjectAccess ForCounter() {
6157     return HObjectAccess(kExternalMemory, 0, Representation::Integer32(),
6158                          Handle<String>::null(), false, false);
6159   }
6160
6161   static HObjectAccess ForExternalUInteger8() {
6162     return HObjectAccess(kExternalMemory, 0, Representation::UInteger8(),
6163                          Handle<String>::null(), false, false);
6164   }
6165
6166   // Create an access to an offset in a fixed array header.
6167   static HObjectAccess ForFixedArrayHeader(int offset);
6168
6169   // Create an access to an in-object property in a JSObject.
6170   // This kind of access must be used when the object |map| is known and
6171   // in-object properties are being accessed. Accesses of the in-object
6172   // properties can have different semantics depending on whether corresponding
6173   // property was added to the map or not.
6174   static HObjectAccess ForMapAndOffset(Handle<Map> map, int offset,
6175       Representation representation = Representation::Tagged());
6176
6177   // Create an access to an in-object property in a JSObject.
6178   // This kind of access can be used for accessing object header fields or
6179   // in-object properties if the map of the object is not known.
6180   static HObjectAccess ForObservableJSObjectOffset(int offset,
6181       Representation representation = Representation::Tagged()) {
6182     return ForMapAndOffset(Handle<Map>::null(), offset, representation);
6183   }
6184
6185   // Create an access to an in-object property in a JSArray.
6186   static HObjectAccess ForJSArrayOffset(int offset);
6187
6188   static HObjectAccess ForContextSlot(int index);
6189
6190   // Create an access to the backing store of an object.
6191   static HObjectAccess ForBackingStoreOffset(int offset,
6192       Representation representation = Representation::Tagged());
6193
6194   // Create an access to a resolved field (in-object or backing store).
6195   static HObjectAccess ForField(Handle<Map> map,
6196       LookupResult *lookup, Handle<String> name = Handle<String>::null());
6197
6198   // Create an access for the payload of a Cell or JSGlobalPropertyCell.
6199   static HObjectAccess ForCellPayload(Isolate* isolate);
6200
6201   static HObjectAccess ForJSTypedArrayLength() {
6202     return HObjectAccess::ForObservableJSObjectOffset(
6203         JSTypedArray::kLengthOffset);
6204   }
6205
6206   static HObjectAccess ForJSArrayBufferBackingStore() {
6207     return HObjectAccess::ForObservableJSObjectOffset(
6208         JSArrayBuffer::kBackingStoreOffset, Representation::External());
6209   }
6210
6211   static HObjectAccess ForJSArrayBufferByteLength() {
6212     return HObjectAccess::ForObservableJSObjectOffset(
6213         JSArrayBuffer::kByteLengthOffset, Representation::Tagged());
6214   }
6215
6216   static HObjectAccess ForExternalArrayExternalPointer() {
6217     return HObjectAccess::ForObservableJSObjectOffset(
6218         ExternalArray::kExternalPointerOffset, Representation::External());
6219   }
6220
6221   static HObjectAccess ForJSArrayBufferViewWeakNext() {
6222     return HObjectAccess::ForObservableJSObjectOffset(
6223         JSArrayBufferView::kWeakNextOffset);
6224   }
6225
6226   static HObjectAccess ForJSArrayBufferWeakFirstView() {
6227     return HObjectAccess::ForObservableJSObjectOffset(
6228         JSArrayBuffer::kWeakFirstViewOffset);
6229   }
6230
6231   static HObjectAccess ForJSArrayBufferViewBuffer() {
6232     return HObjectAccess::ForObservableJSObjectOffset(
6233         JSArrayBufferView::kBufferOffset);
6234   }
6235
6236   static HObjectAccess ForJSArrayBufferViewByteOffset() {
6237     return HObjectAccess::ForObservableJSObjectOffset(
6238         JSArrayBufferView::kByteOffsetOffset);
6239   }
6240
6241   static HObjectAccess ForJSArrayBufferViewByteLength() {
6242     return HObjectAccess::ForObservableJSObjectOffset(
6243         JSArrayBufferView::kByteLengthOffset);
6244   }
6245
6246   static HObjectAccess ForGlobalObjectNativeContext() {
6247     return HObjectAccess(kInobject, GlobalObject::kNativeContextOffset);
6248   }
6249
6250   inline bool Equals(HObjectAccess that) const {
6251     return value_ == that.value_;  // portion and offset must match
6252   }
6253
6254  protected:
6255   void SetGVNFlags(HValue *instr, PropertyAccessType access_type);
6256
6257  private:
6258   // internal use only; different parts of an object or array
6259   enum Portion {
6260     kMaps,             // map of an object
6261     kArrayLengths,     // the length of an array
6262     kStringLengths,    // the length of a string
6263     kElementsPointer,  // elements pointer
6264     kBackingStore,     // some field in the backing store
6265     kDouble,           // some double field
6266     kInobject,         // some other in-object field
6267     kExternalMemory    // some field in external memory
6268   };
6269
6270   HObjectAccess() : value_(0) {}
6271
6272   HObjectAccess(Portion portion, int offset,
6273                 Representation representation = Representation::Tagged(),
6274                 Handle<String> name = Handle<String>::null(),
6275                 bool immutable = false,
6276                 bool existing_inobject_property = true)
6277     : value_(PortionField::encode(portion) |
6278              RepresentationField::encode(representation.kind()) |
6279              ImmutableField::encode(immutable ? 1 : 0) |
6280              ExistingInobjectPropertyField::encode(
6281                  existing_inobject_property ? 1 : 0) |
6282              OffsetField::encode(offset)),
6283       name_(name) {
6284     // assert that the fields decode correctly
6285     DCHECK(this->offset() == offset);
6286     DCHECK(this->portion() == portion);
6287     DCHECK(this->immutable() == immutable);
6288     DCHECK(this->existing_inobject_property() == existing_inobject_property);
6289     DCHECK(RepresentationField::decode(value_) == representation.kind());
6290     DCHECK(!this->existing_inobject_property() || IsInobject());
6291   }
6292
6293   class PortionField : public BitField<Portion, 0, 3> {};
6294   class RepresentationField : public BitField<Representation::Kind, 3, 4> {};
6295   class ImmutableField : public BitField<bool, 7, 1> {};
6296   class ExistingInobjectPropertyField : public BitField<bool, 8, 1> {};
6297   class OffsetField : public BitField<int, 9, 23> {};
6298
6299   uint32_t value_;  // encodes portion, representation, immutable, and offset
6300   Handle<String> name_;
6301
6302   friend class HLoadNamedField;
6303   friend class HStoreNamedField;
6304   friend class SideEffectsTracker;
6305   friend OStream& operator<<(OStream& os, const HObjectAccess& access);
6306
6307   inline Portion portion() const {
6308     return PortionField::decode(value_);
6309   }
6310 };
6311
6312
6313 OStream& operator<<(OStream& os, const HObjectAccess& access);
6314
6315
6316 class HLoadNamedField V8_FINAL : public HTemplateInstruction<2> {
6317  public:
6318   DECLARE_INSTRUCTION_FACTORY_P3(HLoadNamedField, HValue*,
6319                                  HValue*, HObjectAccess);
6320   DECLARE_INSTRUCTION_FACTORY_P5(HLoadNamedField, HValue*, HValue*,
6321                                  HObjectAccess, const UniqueSet<Map>*, HType);
6322
6323   HValue* object() const { return OperandAt(0); }
6324   HValue* dependency() const {
6325     DCHECK(HasDependency());
6326     return OperandAt(1);
6327   }
6328   bool HasDependency() const { return OperandAt(0) != OperandAt(1); }
6329   HObjectAccess access() const { return access_; }
6330   Representation field_representation() const {
6331       return access_.representation();
6332   }
6333
6334   const UniqueSet<Map>* maps() const { return maps_; }
6335
6336   virtual bool HasEscapingOperandAt(int index) V8_OVERRIDE { return false; }
6337   virtual bool HasOutOfBoundsAccess(int size) V8_OVERRIDE {
6338     return !access().IsInobject() || access().offset() >= size;
6339   }
6340   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
6341     if (index == 0 && access().IsExternalMemory()) {
6342       // object must be external in case of external memory access
6343       return Representation::External();
6344     }
6345     return Representation::Tagged();
6346   }
6347   virtual Range* InferRange(Zone* zone) V8_OVERRIDE;
6348   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
6349
6350   bool CanBeReplacedWith(HValue* other) const {
6351     if (!CheckFlag(HValue::kCantBeReplaced)) return false;
6352     if (!type().Equals(other->type())) return false;
6353     if (!representation().Equals(other->representation())) return false;
6354     if (!other->IsLoadNamedField()) return true;
6355     HLoadNamedField* that = HLoadNamedField::cast(other);
6356     if (this->maps_ == that->maps_) return true;
6357     if (this->maps_ == NULL || that->maps_ == NULL) return false;
6358     return this->maps_->IsSubset(that->maps_);
6359   }
6360
6361   DECLARE_CONCRETE_INSTRUCTION(LoadNamedField)
6362
6363  protected:
6364   virtual bool DataEquals(HValue* other) V8_OVERRIDE {
6365     HLoadNamedField* that = HLoadNamedField::cast(other);
6366     if (!this->access_.Equals(that->access_)) return false;
6367     if (this->maps_ == that->maps_) return true;
6368     return (this->maps_ != NULL &&
6369             that->maps_ != NULL &&
6370             this->maps_->Equals(that->maps_));
6371   }
6372
6373  private:
6374   HLoadNamedField(HValue* object,
6375                   HValue* dependency,
6376                   HObjectAccess access)
6377       : access_(access), maps_(NULL) {
6378     DCHECK_NOT_NULL(object);
6379     SetOperandAt(0, object);
6380     SetOperandAt(1, dependency ? dependency : object);
6381
6382     Representation representation = access.representation();
6383     if (representation.IsInteger8() ||
6384         representation.IsUInteger8() ||
6385         representation.IsInteger16() ||
6386         representation.IsUInteger16()) {
6387       set_representation(Representation::Integer32());
6388     } else if (representation.IsSmi()) {
6389       set_type(HType::Smi());
6390       if (SmiValuesAre32Bits()) {
6391         set_representation(Representation::Integer32());
6392       } else {
6393         set_representation(representation);
6394       }
6395     } else if (representation.IsDouble() ||
6396                representation.IsExternal() ||
6397                representation.IsInteger32()) {
6398       set_representation(representation);
6399     } else if (representation.IsHeapObject()) {
6400       set_type(HType::HeapObject());
6401       set_representation(Representation::Tagged());
6402     } else {
6403       set_representation(Representation::Tagged());
6404     }
6405     access.SetGVNFlags(this, LOAD);
6406   }
6407
6408   HLoadNamedField(HValue* object,
6409                   HValue* dependency,
6410                   HObjectAccess access,
6411                   const UniqueSet<Map>* maps,
6412                   HType type)
6413       : HTemplateInstruction<2>(type), access_(access), maps_(maps) {
6414     DCHECK_NOT_NULL(maps);
6415     DCHECK_NE(0, maps->size());
6416
6417     DCHECK_NOT_NULL(object);
6418     SetOperandAt(0, object);
6419     SetOperandAt(1, dependency ? dependency : object);
6420
6421     DCHECK(access.representation().IsHeapObject());
6422     DCHECK(type.IsHeapObject());
6423     set_representation(Representation::Tagged());
6424
6425     access.SetGVNFlags(this, LOAD);
6426   }
6427
6428   virtual bool IsDeletable() const V8_OVERRIDE { return true; }
6429
6430   HObjectAccess access_;
6431   const UniqueSet<Map>* maps_;
6432 };
6433
6434
6435 class HLoadNamedGeneric V8_FINAL : public HTemplateInstruction<2> {
6436  public:
6437   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P2(HLoadNamedGeneric, HValue*,
6438                                               Handle<Object>);
6439
6440   HValue* context() const { return OperandAt(0); }
6441   HValue* object() const { return OperandAt(1); }
6442   Handle<Object> name() const { return name_; }
6443
6444   int slot() const {
6445     DCHECK(FLAG_vector_ics &&
6446            slot_ != FeedbackSlotInterface::kInvalidFeedbackSlot);
6447     return slot_;
6448   }
6449   Handle<FixedArray> feedback_vector() const { return feedback_vector_; }
6450   void SetVectorAndSlot(Handle<FixedArray> vector, int slot) {
6451     DCHECK(FLAG_vector_ics);
6452     feedback_vector_ = vector;
6453     slot_ = slot;
6454   }
6455
6456   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
6457     return Representation::Tagged();
6458   }
6459
6460   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
6461
6462   DECLARE_CONCRETE_INSTRUCTION(LoadNamedGeneric)
6463
6464  private:
6465   HLoadNamedGeneric(HValue* context, HValue* object, Handle<Object> name)
6466       : name_(name),
6467         slot_(FeedbackSlotInterface::kInvalidFeedbackSlot) {
6468     SetOperandAt(0, context);
6469     SetOperandAt(1, object);
6470     set_representation(Representation::Tagged());
6471     SetAllSideEffects();
6472   }
6473
6474   Handle<Object> name_;
6475   Handle<FixedArray> feedback_vector_;
6476   int slot_;
6477 };
6478
6479
6480 class HLoadFunctionPrototype V8_FINAL : public HUnaryOperation {
6481  public:
6482   DECLARE_INSTRUCTION_FACTORY_P1(HLoadFunctionPrototype, HValue*);
6483
6484   HValue* function() { return OperandAt(0); }
6485
6486   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
6487     return Representation::Tagged();
6488   }
6489
6490   DECLARE_CONCRETE_INSTRUCTION(LoadFunctionPrototype)
6491
6492  protected:
6493   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
6494
6495  private:
6496   explicit HLoadFunctionPrototype(HValue* function)
6497       : HUnaryOperation(function) {
6498     set_representation(Representation::Tagged());
6499     SetFlag(kUseGVN);
6500     SetDependsOnFlag(kCalls);
6501   }
6502 };
6503
6504 class ArrayInstructionInterface {
6505  public:
6506   virtual HValue* GetKey() = 0;
6507   virtual void SetKey(HValue* key) = 0;
6508   virtual ElementsKind elements_kind() const = 0;
6509   // TryIncreaseBaseOffset returns false if overflow would result.
6510   virtual bool TryIncreaseBaseOffset(uint32_t increase_by_value) = 0;
6511   virtual bool IsDehoisted() const = 0;
6512   virtual void SetDehoisted(bool is_dehoisted) = 0;
6513   virtual ~ArrayInstructionInterface() { }
6514
6515   static Representation KeyedAccessIndexRequirement(Representation r) {
6516     return r.IsInteger32() || SmiValuesAre32Bits()
6517         ? Representation::Integer32() : Representation::Smi();
6518   }
6519 };
6520
6521
6522 static const int kDefaultKeyedHeaderOffsetSentinel = -1;
6523
6524 enum LoadKeyedHoleMode {
6525   NEVER_RETURN_HOLE,
6526   ALLOW_RETURN_HOLE
6527 };
6528
6529
6530 class HLoadKeyed V8_FINAL
6531     : public HTemplateInstruction<3>, public ArrayInstructionInterface {
6532  public:
6533   DECLARE_INSTRUCTION_FACTORY_P4(HLoadKeyed, HValue*, HValue*, HValue*,
6534                                  ElementsKind);
6535   DECLARE_INSTRUCTION_FACTORY_P5(HLoadKeyed, HValue*, HValue*, HValue*,
6536                                  ElementsKind, LoadKeyedHoleMode);
6537   DECLARE_INSTRUCTION_FACTORY_P6(HLoadKeyed, HValue*, HValue*, HValue*,
6538                                  ElementsKind, LoadKeyedHoleMode, int);
6539
6540   bool is_external() const {
6541     return IsExternalArrayElementsKind(elements_kind());
6542   }
6543   bool is_fixed_typed_array() const {
6544     return IsFixedTypedArrayElementsKind(elements_kind());
6545   }
6546   bool is_typed_elements() const {
6547     return is_external() || is_fixed_typed_array();
6548   }
6549   HValue* elements() const { return OperandAt(0); }
6550   HValue* key() const { return OperandAt(1); }
6551   HValue* dependency() const {
6552     DCHECK(HasDependency());
6553     return OperandAt(2);
6554   }
6555   bool HasDependency() const { return OperandAt(0) != OperandAt(2); }
6556   uint32_t base_offset() const { return BaseOffsetField::decode(bit_field_); }
6557   bool TryIncreaseBaseOffset(uint32_t increase_by_value);
6558   HValue* GetKey() { return key(); }
6559   void SetKey(HValue* key) { SetOperandAt(1, key); }
6560   bool IsDehoisted() const { return IsDehoistedField::decode(bit_field_); }
6561   void SetDehoisted(bool is_dehoisted) {
6562     bit_field_ = IsDehoistedField::update(bit_field_, is_dehoisted);
6563   }
6564   virtual ElementsKind elements_kind() const V8_OVERRIDE {
6565     return ElementsKindField::decode(bit_field_);
6566   }
6567   LoadKeyedHoleMode hole_mode() const {
6568     return HoleModeField::decode(bit_field_);
6569   }
6570
6571   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
6572     // kind_fast:                 tagged[int32] (none)
6573     // kind_double:               tagged[int32] (none)
6574     // kind_fixed_typed_array:    tagged[int32] (none)
6575     // kind_external:             external[int32] (none)
6576     if (index == 0) {
6577       return is_external() ? Representation::External()
6578           : Representation::Tagged();
6579     }
6580     if (index == 1) {
6581       return ArrayInstructionInterface::KeyedAccessIndexRequirement(
6582           OperandAt(1)->representation());
6583     }
6584     return Representation::None();
6585   }
6586
6587   virtual Representation observed_input_representation(int index) V8_OVERRIDE {
6588     return RequiredInputRepresentation(index);
6589   }
6590
6591   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
6592
6593   bool UsesMustHandleHole() const;
6594   bool AllUsesCanTreatHoleAsNaN() const;
6595   bool RequiresHoleCheck() const;
6596
6597   virtual Range* InferRange(Zone* zone) V8_OVERRIDE;
6598
6599   DECLARE_CONCRETE_INSTRUCTION(LoadKeyed)
6600
6601  protected:
6602   virtual bool DataEquals(HValue* other) V8_OVERRIDE {
6603     if (!other->IsLoadKeyed()) return false;
6604     HLoadKeyed* other_load = HLoadKeyed::cast(other);
6605
6606     if (IsDehoisted() && base_offset() != other_load->base_offset())
6607       return false;
6608     return elements_kind() == other_load->elements_kind();
6609   }
6610
6611  private:
6612   HLoadKeyed(HValue* obj,
6613              HValue* key,
6614              HValue* dependency,
6615              ElementsKind elements_kind,
6616              LoadKeyedHoleMode mode = NEVER_RETURN_HOLE,
6617              int offset = kDefaultKeyedHeaderOffsetSentinel)
6618       : bit_field_(0) {
6619     offset = offset == kDefaultKeyedHeaderOffsetSentinel
6620         ? GetDefaultHeaderSizeForElementsKind(elements_kind)
6621         : offset;
6622     bit_field_ = ElementsKindField::encode(elements_kind) |
6623         HoleModeField::encode(mode) |
6624         BaseOffsetField::encode(offset);
6625
6626     SetOperandAt(0, obj);
6627     SetOperandAt(1, key);
6628     SetOperandAt(2, dependency != NULL ? dependency : obj);
6629
6630     if (!is_typed_elements()) {
6631       // I can detect the case between storing double (holey and fast) and
6632       // smi/object by looking at elements_kind_.
6633       DCHECK(IsFastSmiOrObjectElementsKind(elements_kind) ||
6634              IsFastDoubleElementsKind(elements_kind));
6635
6636       if (IsFastSmiOrObjectElementsKind(elements_kind)) {
6637         if (IsFastSmiElementsKind(elements_kind) &&
6638             (!IsHoleyElementsKind(elements_kind) ||
6639              mode == NEVER_RETURN_HOLE)) {
6640           set_type(HType::Smi());
6641           if (SmiValuesAre32Bits() && !RequiresHoleCheck()) {
6642             set_representation(Representation::Integer32());
6643           } else {
6644             set_representation(Representation::Smi());
6645           }
6646         } else {
6647           set_representation(Representation::Tagged());
6648         }
6649
6650         SetDependsOnFlag(kArrayElements);
6651       } else {
6652         set_representation(Representation::Double());
6653         SetDependsOnFlag(kDoubleArrayElements);
6654       }
6655     } else {
6656       if (elements_kind == EXTERNAL_FLOAT32_ELEMENTS ||
6657           elements_kind == EXTERNAL_FLOAT64_ELEMENTS ||
6658           elements_kind == FLOAT32_ELEMENTS ||
6659           elements_kind == FLOAT64_ELEMENTS) {
6660         set_representation(Representation::Double());
6661       } else {
6662         set_representation(Representation::Integer32());
6663       }
6664
6665       if (is_external()) {
6666         SetDependsOnFlag(kExternalMemory);
6667       } else if (is_fixed_typed_array()) {
6668         SetDependsOnFlag(kTypedArrayElements);
6669       } else {
6670         UNREACHABLE();
6671       }
6672       // Native code could change the specialized array.
6673       SetDependsOnFlag(kCalls);
6674     }
6675
6676     SetFlag(kUseGVN);
6677   }
6678
6679   virtual bool IsDeletable() const V8_OVERRIDE {
6680     return !RequiresHoleCheck();
6681   }
6682
6683   // Establish some checks around our packed fields
6684   enum LoadKeyedBits {
6685     kBitsForElementsKind = 5,
6686     kBitsForHoleMode = 1,
6687     kBitsForBaseOffset = 25,
6688     kBitsForIsDehoisted = 1,
6689
6690     kStartElementsKind = 0,
6691     kStartHoleMode = kStartElementsKind + kBitsForElementsKind,
6692     kStartBaseOffset = kStartHoleMode + kBitsForHoleMode,
6693     kStartIsDehoisted = kStartBaseOffset + kBitsForBaseOffset
6694   };
6695
6696   STATIC_ASSERT((kBitsForElementsKind + kBitsForBaseOffset +
6697                  kBitsForIsDehoisted) <= sizeof(uint32_t)*8);
6698   STATIC_ASSERT(kElementsKindCount <= (1 << kBitsForElementsKind));
6699   class ElementsKindField:
6700     public BitField<ElementsKind, kStartElementsKind, kBitsForElementsKind>
6701     {};  // NOLINT
6702   class HoleModeField:
6703     public BitField<LoadKeyedHoleMode, kStartHoleMode, kBitsForHoleMode>
6704     {};  // NOLINT
6705   class BaseOffsetField:
6706     public BitField<uint32_t, kStartBaseOffset, kBitsForBaseOffset>
6707     {};  // NOLINT
6708   class IsDehoistedField:
6709     public BitField<bool, kStartIsDehoisted, kBitsForIsDehoisted>
6710     {};  // NOLINT
6711   uint32_t bit_field_;
6712 };
6713
6714
6715 class HLoadKeyedGeneric V8_FINAL : public HTemplateInstruction<3> {
6716  public:
6717   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P2(HLoadKeyedGeneric, HValue*,
6718                                               HValue*);
6719   HValue* object() const { return OperandAt(0); }
6720   HValue* key() const { return OperandAt(1); }
6721   HValue* context() const { return OperandAt(2); }
6722   int slot() const {
6723     DCHECK(FLAG_vector_ics &&
6724            slot_ != FeedbackSlotInterface::kInvalidFeedbackSlot);
6725     return slot_;
6726   }
6727   Handle<FixedArray> feedback_vector() const { return feedback_vector_; }
6728   void SetVectorAndSlot(Handle<FixedArray> vector, int slot) {
6729     DCHECK(FLAG_vector_ics);
6730     feedback_vector_ = vector;
6731     slot_ = slot;
6732   }
6733
6734   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
6735
6736   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
6737     // tagged[tagged]
6738     return Representation::Tagged();
6739   }
6740
6741   virtual HValue* Canonicalize() V8_OVERRIDE;
6742
6743   DECLARE_CONCRETE_INSTRUCTION(LoadKeyedGeneric)
6744
6745  private:
6746   HLoadKeyedGeneric(HValue* context, HValue* obj, HValue* key)
6747       : slot_(FeedbackSlotInterface::kInvalidFeedbackSlot) {
6748     set_representation(Representation::Tagged());
6749     SetOperandAt(0, obj);
6750     SetOperandAt(1, key);
6751     SetOperandAt(2, context);
6752     SetAllSideEffects();
6753   }
6754
6755   Handle<FixedArray> feedback_vector_;
6756   int slot_;
6757 };
6758
6759
6760 // Indicates whether the store is a store to an entry that was previously
6761 // initialized or not.
6762 enum StoreFieldOrKeyedMode {
6763   // The entry could be either previously initialized or not.
6764   INITIALIZING_STORE,
6765   // At the time of this store it is guaranteed that the entry is already
6766   // initialized.
6767   STORE_TO_INITIALIZED_ENTRY
6768 };
6769
6770
6771 class HStoreNamedField V8_FINAL : public HTemplateInstruction<3> {
6772  public:
6773   DECLARE_INSTRUCTION_FACTORY_P3(HStoreNamedField, HValue*,
6774                                  HObjectAccess, HValue*);
6775   DECLARE_INSTRUCTION_FACTORY_P4(HStoreNamedField, HValue*,
6776                                  HObjectAccess, HValue*, StoreFieldOrKeyedMode);
6777
6778   DECLARE_CONCRETE_INSTRUCTION(StoreNamedField)
6779
6780   virtual bool HasEscapingOperandAt(int index) V8_OVERRIDE {
6781     return index == 1;
6782   }
6783   virtual bool HasOutOfBoundsAccess(int size) V8_OVERRIDE {
6784     return !access().IsInobject() || access().offset() >= size;
6785   }
6786   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
6787     if (index == 0 && access().IsExternalMemory()) {
6788       // object must be external in case of external memory access
6789       return Representation::External();
6790     } else if (index == 1) {
6791       if (field_representation().IsInteger8() ||
6792           field_representation().IsUInteger8() ||
6793           field_representation().IsInteger16() ||
6794           field_representation().IsUInteger16() ||
6795           field_representation().IsInteger32()) {
6796         return Representation::Integer32();
6797       } else if (field_representation().IsDouble()) {
6798         return field_representation();
6799       } else if (field_representation().IsSmi()) {
6800         if (SmiValuesAre32Bits() && store_mode_ == STORE_TO_INITIALIZED_ENTRY) {
6801           return Representation::Integer32();
6802         }
6803         return field_representation();
6804       } else if (field_representation().IsExternal()) {
6805         return Representation::External();
6806       }
6807     }
6808     return Representation::Tagged();
6809   }
6810   virtual bool HandleSideEffectDominator(GVNFlag side_effect,
6811                                          HValue* dominator) V8_OVERRIDE {
6812     DCHECK(side_effect == kNewSpacePromotion);
6813     if (!FLAG_use_write_barrier_elimination) return false;
6814     dominator_ = dominator;
6815     return false;
6816   }
6817   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
6818
6819   HValue* object() const { return OperandAt(0); }
6820   HValue* value() const { return OperandAt(1); }
6821   HValue* transition() const { return OperandAt(2); }
6822
6823   HObjectAccess access() const { return access_; }
6824   HValue* dominator() const { return dominator_; }
6825   bool has_transition() const { return has_transition_; }
6826   StoreFieldOrKeyedMode store_mode() const { return store_mode_; }
6827
6828   Handle<Map> transition_map() const {
6829     if (has_transition()) {
6830       return Handle<Map>::cast(
6831           HConstant::cast(transition())->handle(Isolate::Current()));
6832     } else {
6833       return Handle<Map>();
6834     }
6835   }
6836
6837   void SetTransition(HConstant* transition) {
6838     DCHECK(!has_transition());  // Only set once.
6839     SetOperandAt(2, transition);
6840     has_transition_ = true;
6841     SetChangesFlag(kMaps);
6842   }
6843
6844   bool NeedsWriteBarrier() const {
6845     DCHECK(!field_representation().IsDouble() || !has_transition());
6846     if (field_representation().IsDouble()) return false;
6847     if (field_representation().IsSmi()) return false;
6848     if (field_representation().IsInteger32()) return false;
6849     if (field_representation().IsExternal()) return false;
6850     return StoringValueNeedsWriteBarrier(value()) &&
6851         ReceiverObjectNeedsWriteBarrier(object(), value(), dominator());
6852   }
6853
6854   bool NeedsWriteBarrierForMap() {
6855     return ReceiverObjectNeedsWriteBarrier(object(), transition(),
6856                                            dominator());
6857   }
6858
6859   SmiCheck SmiCheckForWriteBarrier() const {
6860     if (field_representation().IsHeapObject()) return OMIT_SMI_CHECK;
6861     if (value()->type().IsHeapObject()) return OMIT_SMI_CHECK;
6862     return INLINE_SMI_CHECK;
6863   }
6864
6865   PointersToHereCheck PointersToHereCheckForValue() const {
6866     return PointersToHereCheckForObject(value(), dominator());
6867   }
6868
6869   Representation field_representation() const {
6870     return access_.representation();
6871   }
6872
6873   void UpdateValue(HValue* value) {
6874     SetOperandAt(1, value);
6875   }
6876
6877   bool CanBeReplacedWith(HStoreNamedField* that) const {
6878     if (!this->access().Equals(that->access())) return false;
6879     if (SmiValuesAre32Bits() &&
6880         this->field_representation().IsSmi() &&
6881         this->store_mode() == INITIALIZING_STORE &&
6882         that->store_mode() == STORE_TO_INITIALIZED_ENTRY) {
6883       // We cannot replace an initializing store to a smi field with a store to
6884       // an initialized entry on 64-bit architectures (with 32-bit smis).
6885       return false;
6886     }
6887     return true;
6888   }
6889
6890  private:
6891   HStoreNamedField(HValue* obj,
6892                    HObjectAccess access,
6893                    HValue* val,
6894                    StoreFieldOrKeyedMode store_mode = INITIALIZING_STORE)
6895       : access_(access),
6896         dominator_(NULL),
6897         has_transition_(false),
6898         store_mode_(store_mode) {
6899     // Stores to a non existing in-object property are allowed only to the
6900     // newly allocated objects (via HAllocate or HInnerAllocatedObject).
6901     DCHECK(!access.IsInobject() || access.existing_inobject_property() ||
6902            obj->IsAllocate() || obj->IsInnerAllocatedObject());
6903     SetOperandAt(0, obj);
6904     SetOperandAt(1, val);
6905     SetOperandAt(2, obj);
6906     access.SetGVNFlags(this, STORE);
6907   }
6908
6909   HObjectAccess access_;
6910   HValue* dominator_;
6911   bool has_transition_ : 1;
6912   StoreFieldOrKeyedMode store_mode_ : 1;
6913 };
6914
6915
6916 class HStoreNamedGeneric V8_FINAL : public HTemplateInstruction<3> {
6917  public:
6918   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P4(HStoreNamedGeneric, HValue*,
6919                                               Handle<String>, HValue*,
6920                                               StrictMode);
6921   HValue* object() const { return OperandAt(0); }
6922   HValue* value() const { return OperandAt(1); }
6923   HValue* context() const { return OperandAt(2); }
6924   Handle<String> name() const { return name_; }
6925   StrictMode strict_mode() const { return strict_mode_; }
6926
6927   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
6928
6929   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
6930     return Representation::Tagged();
6931   }
6932
6933   DECLARE_CONCRETE_INSTRUCTION(StoreNamedGeneric)
6934
6935  private:
6936   HStoreNamedGeneric(HValue* context,
6937                      HValue* object,
6938                      Handle<String> name,
6939                      HValue* value,
6940                      StrictMode strict_mode)
6941       : name_(name),
6942         strict_mode_(strict_mode) {
6943     SetOperandAt(0, object);
6944     SetOperandAt(1, value);
6945     SetOperandAt(2, context);
6946     SetAllSideEffects();
6947   }
6948
6949   Handle<String> name_;
6950   StrictMode strict_mode_;
6951 };
6952
6953
6954 class HStoreKeyed V8_FINAL
6955     : public HTemplateInstruction<3>, public ArrayInstructionInterface {
6956  public:
6957   DECLARE_INSTRUCTION_FACTORY_P4(HStoreKeyed, HValue*, HValue*, HValue*,
6958                                  ElementsKind);
6959   DECLARE_INSTRUCTION_FACTORY_P5(HStoreKeyed, HValue*, HValue*, HValue*,
6960                                  ElementsKind, StoreFieldOrKeyedMode);
6961   DECLARE_INSTRUCTION_FACTORY_P6(HStoreKeyed, HValue*, HValue*, HValue*,
6962                                  ElementsKind, StoreFieldOrKeyedMode, int);
6963
6964   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
6965     // kind_fast:               tagged[int32] = tagged
6966     // kind_double:             tagged[int32] = double
6967     // kind_smi   :             tagged[int32] = smi
6968     // kind_fixed_typed_array:  tagged[int32] = (double | int32)
6969     // kind_external:           external[int32] = (double | int32)
6970     if (index == 0) {
6971       return is_external() ? Representation::External()
6972                            : Representation::Tagged();
6973     } else if (index == 1) {
6974       return ArrayInstructionInterface::KeyedAccessIndexRequirement(
6975           OperandAt(1)->representation());
6976     }
6977
6978     DCHECK_EQ(index, 2);
6979     return RequiredValueRepresentation(elements_kind_, store_mode_);
6980   }
6981
6982   static Representation RequiredValueRepresentation(
6983       ElementsKind kind, StoreFieldOrKeyedMode mode) {
6984     if (IsDoubleOrFloatElementsKind(kind)) {
6985       return Representation::Double();
6986     }
6987
6988     if (kind == FAST_SMI_ELEMENTS && SmiValuesAre32Bits() &&
6989         mode == STORE_TO_INITIALIZED_ENTRY) {
6990       return Representation::Integer32();
6991     }
6992
6993     if (IsFastSmiElementsKind(kind)) {
6994       return Representation::Smi();
6995     }
6996
6997     return IsExternalArrayElementsKind(kind) ||
6998                    IsFixedTypedArrayElementsKind(kind)
6999                ? Representation::Integer32()
7000                : Representation::Tagged();
7001   }
7002
7003   bool is_external() const {
7004     return IsExternalArrayElementsKind(elements_kind());
7005   }
7006
7007   bool is_fixed_typed_array() const {
7008     return IsFixedTypedArrayElementsKind(elements_kind());
7009   }
7010
7011   bool is_typed_elements() const {
7012     return is_external() || is_fixed_typed_array();
7013   }
7014
7015   virtual Representation observed_input_representation(int index) V8_OVERRIDE {
7016     if (index < 2) return RequiredInputRepresentation(index);
7017     if (IsUninitialized()) {
7018       return Representation::None();
7019     }
7020     Representation r = RequiredValueRepresentation(elements_kind_, store_mode_);
7021     // For fast object elements kinds, don't assume anything.
7022     if (r.IsTagged()) return Representation::None();
7023     return r;
7024   }
7025
7026   HValue* elements() const { return OperandAt(0); }
7027   HValue* key() const { return OperandAt(1); }
7028   HValue* value() const { return OperandAt(2); }
7029   bool value_is_smi() const {
7030     return IsFastSmiElementsKind(elements_kind_);
7031   }
7032   StoreFieldOrKeyedMode store_mode() const { return store_mode_; }
7033   ElementsKind elements_kind() const { return elements_kind_; }
7034   uint32_t base_offset() const { return base_offset_; }
7035   bool TryIncreaseBaseOffset(uint32_t increase_by_value);
7036   HValue* GetKey() { return key(); }
7037   void SetKey(HValue* key) { SetOperandAt(1, key); }
7038   bool IsDehoisted() const { return is_dehoisted_; }
7039   void SetDehoisted(bool is_dehoisted) { is_dehoisted_ = is_dehoisted; }
7040   bool IsUninitialized() { return is_uninitialized_; }
7041   void SetUninitialized(bool is_uninitialized) {
7042     is_uninitialized_ = is_uninitialized;
7043   }
7044
7045   bool IsConstantHoleStore() {
7046     return value()->IsConstant() && HConstant::cast(value())->IsTheHole();
7047   }
7048
7049   virtual bool HandleSideEffectDominator(GVNFlag side_effect,
7050                                          HValue* dominator) V8_OVERRIDE {
7051     DCHECK(side_effect == kNewSpacePromotion);
7052     dominator_ = dominator;
7053     return false;
7054   }
7055
7056   HValue* dominator() const { return dominator_; }
7057
7058   bool NeedsWriteBarrier() {
7059     if (value_is_smi()) {
7060       return false;
7061     } else {
7062       return StoringValueNeedsWriteBarrier(value()) &&
7063           ReceiverObjectNeedsWriteBarrier(elements(), value(), dominator());
7064     }
7065   }
7066
7067   PointersToHereCheck PointersToHereCheckForValue() const {
7068     return PointersToHereCheckForObject(value(), dominator());
7069   }
7070
7071   bool NeedsCanonicalization();
7072
7073   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
7074
7075   DECLARE_CONCRETE_INSTRUCTION(StoreKeyed)
7076
7077  private:
7078   HStoreKeyed(HValue* obj, HValue* key, HValue* val,
7079               ElementsKind elements_kind,
7080               StoreFieldOrKeyedMode store_mode = INITIALIZING_STORE,
7081               int offset = kDefaultKeyedHeaderOffsetSentinel)
7082       : elements_kind_(elements_kind),
7083       base_offset_(offset == kDefaultKeyedHeaderOffsetSentinel
7084           ? GetDefaultHeaderSizeForElementsKind(elements_kind)
7085           : offset),
7086       is_dehoisted_(false),
7087       is_uninitialized_(false),
7088       store_mode_(store_mode),
7089       dominator_(NULL) {
7090     SetOperandAt(0, obj);
7091     SetOperandAt(1, key);
7092     SetOperandAt(2, val);
7093
7094     if (IsFastObjectElementsKind(elements_kind)) {
7095       SetFlag(kTrackSideEffectDominators);
7096       SetDependsOnFlag(kNewSpacePromotion);
7097     }
7098     if (is_external()) {
7099       SetChangesFlag(kExternalMemory);
7100       SetFlag(kAllowUndefinedAsNaN);
7101     } else if (IsFastDoubleElementsKind(elements_kind)) {
7102       SetChangesFlag(kDoubleArrayElements);
7103     } else if (IsFastSmiElementsKind(elements_kind)) {
7104       SetChangesFlag(kArrayElements);
7105     } else if (is_fixed_typed_array()) {
7106       SetChangesFlag(kTypedArrayElements);
7107       SetFlag(kAllowUndefinedAsNaN);
7108     } else {
7109       SetChangesFlag(kArrayElements);
7110     }
7111
7112     // EXTERNAL_{UNSIGNED_,}{BYTE,SHORT,INT}_ELEMENTS are truncating.
7113     if ((elements_kind >= EXTERNAL_INT8_ELEMENTS &&
7114         elements_kind <= EXTERNAL_UINT32_ELEMENTS) ||
7115         (elements_kind >= UINT8_ELEMENTS &&
7116         elements_kind <= INT32_ELEMENTS)) {
7117       SetFlag(kTruncatingToInt32);
7118     }
7119   }
7120
7121   ElementsKind elements_kind_;
7122   uint32_t base_offset_;
7123   bool is_dehoisted_ : 1;
7124   bool is_uninitialized_ : 1;
7125   StoreFieldOrKeyedMode store_mode_: 1;
7126   HValue* dominator_;
7127 };
7128
7129
7130 class HStoreKeyedGeneric V8_FINAL : public HTemplateInstruction<4> {
7131  public:
7132   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P4(HStoreKeyedGeneric, HValue*,
7133                                               HValue*, HValue*, StrictMode);
7134
7135   HValue* object() const { return OperandAt(0); }
7136   HValue* key() const { return OperandAt(1); }
7137   HValue* value() const { return OperandAt(2); }
7138   HValue* context() const { return OperandAt(3); }
7139   StrictMode strict_mode() const { return strict_mode_; }
7140
7141   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
7142     // tagged[tagged] = tagged
7143     return Representation::Tagged();
7144   }
7145
7146   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
7147
7148   DECLARE_CONCRETE_INSTRUCTION(StoreKeyedGeneric)
7149
7150  private:
7151   HStoreKeyedGeneric(HValue* context,
7152                      HValue* object,
7153                      HValue* key,
7154                      HValue* value,
7155                      StrictMode strict_mode)
7156       : strict_mode_(strict_mode) {
7157     SetOperandAt(0, object);
7158     SetOperandAt(1, key);
7159     SetOperandAt(2, value);
7160     SetOperandAt(3, context);
7161     SetAllSideEffects();
7162   }
7163
7164   StrictMode strict_mode_;
7165 };
7166
7167
7168 class HTransitionElementsKind V8_FINAL : public HTemplateInstruction<2> {
7169  public:
7170   inline static HTransitionElementsKind* New(Zone* zone,
7171                                              HValue* context,
7172                                              HValue* object,
7173                                              Handle<Map> original_map,
7174                                              Handle<Map> transitioned_map) {
7175     return new(zone) HTransitionElementsKind(context, object,
7176                                              original_map, transitioned_map);
7177   }
7178
7179   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
7180     return Representation::Tagged();
7181   }
7182
7183   HValue* object() const { return OperandAt(0); }
7184   HValue* context() const { return OperandAt(1); }
7185   Unique<Map> original_map() const { return original_map_; }
7186   Unique<Map> transitioned_map() const { return transitioned_map_; }
7187   ElementsKind from_kind() const { return from_kind_; }
7188   ElementsKind to_kind() const { return to_kind_; }
7189
7190   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
7191
7192   DECLARE_CONCRETE_INSTRUCTION(TransitionElementsKind)
7193
7194  protected:
7195   virtual bool DataEquals(HValue* other) V8_OVERRIDE {
7196     HTransitionElementsKind* instr = HTransitionElementsKind::cast(other);
7197     return original_map_ == instr->original_map_ &&
7198            transitioned_map_ == instr->transitioned_map_;
7199   }
7200
7201   virtual int RedefinedOperandIndex() { return 0; }
7202
7203  private:
7204   HTransitionElementsKind(HValue* context,
7205                           HValue* object,
7206                           Handle<Map> original_map,
7207                           Handle<Map> transitioned_map)
7208       : original_map_(Unique<Map>(original_map)),
7209         transitioned_map_(Unique<Map>(transitioned_map)),
7210         from_kind_(original_map->elements_kind()),
7211         to_kind_(transitioned_map->elements_kind()) {
7212     SetOperandAt(0, object);
7213     SetOperandAt(1, context);
7214     SetFlag(kUseGVN);
7215     SetChangesFlag(kElementsKind);
7216     if (!IsSimpleMapChangeTransition(from_kind_, to_kind_)) {
7217       SetChangesFlag(kElementsPointer);
7218       SetChangesFlag(kNewSpacePromotion);
7219     }
7220     set_representation(Representation::Tagged());
7221   }
7222
7223   Unique<Map> original_map_;
7224   Unique<Map> transitioned_map_;
7225   ElementsKind from_kind_;
7226   ElementsKind to_kind_;
7227 };
7228
7229
7230 class HStringAdd V8_FINAL : public HBinaryOperation {
7231  public:
7232   static HInstruction* New(Zone* zone,
7233                            HValue* context,
7234                            HValue* left,
7235                            HValue* right,
7236                            PretenureFlag pretenure_flag = NOT_TENURED,
7237                            StringAddFlags flags = STRING_ADD_CHECK_BOTH,
7238                            Handle<AllocationSite> allocation_site =
7239                                Handle<AllocationSite>::null());
7240
7241   StringAddFlags flags() const { return flags_; }
7242   PretenureFlag pretenure_flag() const { return pretenure_flag_; }
7243
7244   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
7245     return Representation::Tagged();
7246   }
7247
7248   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
7249
7250   DECLARE_CONCRETE_INSTRUCTION(StringAdd)
7251
7252  protected:
7253   virtual bool DataEquals(HValue* other) V8_OVERRIDE {
7254     return flags_ == HStringAdd::cast(other)->flags_ &&
7255         pretenure_flag_ == HStringAdd::cast(other)->pretenure_flag_;
7256   }
7257
7258  private:
7259   HStringAdd(HValue* context,
7260              HValue* left,
7261              HValue* right,
7262              PretenureFlag pretenure_flag,
7263              StringAddFlags flags,
7264              Handle<AllocationSite> allocation_site)
7265       : HBinaryOperation(context, left, right, HType::String()),
7266         flags_(flags), pretenure_flag_(pretenure_flag) {
7267     set_representation(Representation::Tagged());
7268     SetFlag(kUseGVN);
7269     SetDependsOnFlag(kMaps);
7270     SetChangesFlag(kNewSpacePromotion);
7271     if (FLAG_trace_pretenuring) {
7272       PrintF("HStringAdd with AllocationSite %p %s\n",
7273              allocation_site.is_null()
7274                  ? static_cast<void*>(NULL)
7275                  : static_cast<void*>(*allocation_site),
7276              pretenure_flag == TENURED ? "tenured" : "not tenured");
7277     }
7278   }
7279
7280   // No side-effects except possible allocation:
7281   virtual bool IsDeletable() const V8_OVERRIDE { return true; }
7282
7283   const StringAddFlags flags_;
7284   const PretenureFlag pretenure_flag_;
7285 };
7286
7287
7288 class HStringCharCodeAt V8_FINAL : public HTemplateInstruction<3> {
7289  public:
7290   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P2(HStringCharCodeAt,
7291                                               HValue*,
7292                                               HValue*);
7293
7294   virtual Representation RequiredInputRepresentation(int index) {
7295     // The index is supposed to be Integer32.
7296     return index == 2
7297         ? Representation::Integer32()
7298         : Representation::Tagged();
7299   }
7300
7301   HValue* context() const { return OperandAt(0); }
7302   HValue* string() const { return OperandAt(1); }
7303   HValue* index() const { return OperandAt(2); }
7304
7305   DECLARE_CONCRETE_INSTRUCTION(StringCharCodeAt)
7306
7307  protected:
7308   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
7309
7310   virtual Range* InferRange(Zone* zone) V8_OVERRIDE {
7311     return new(zone) Range(0, String::kMaxUtf16CodeUnit);
7312   }
7313
7314  private:
7315   HStringCharCodeAt(HValue* context, HValue* string, HValue* index) {
7316     SetOperandAt(0, context);
7317     SetOperandAt(1, string);
7318     SetOperandAt(2, index);
7319     set_representation(Representation::Integer32());
7320     SetFlag(kUseGVN);
7321     SetDependsOnFlag(kMaps);
7322     SetDependsOnFlag(kStringChars);
7323     SetChangesFlag(kNewSpacePromotion);
7324   }
7325
7326   // No side effects: runtime function assumes string + number inputs.
7327   virtual bool IsDeletable() const V8_OVERRIDE { return true; }
7328 };
7329
7330
7331 class HStringCharFromCode V8_FINAL : public HTemplateInstruction<2> {
7332  public:
7333   static HInstruction* New(Zone* zone,
7334                            HValue* context,
7335                            HValue* char_code);
7336
7337   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
7338     return index == 0
7339         ? Representation::Tagged()
7340         : Representation::Integer32();
7341   }
7342
7343   HValue* context() const { return OperandAt(0); }
7344   HValue* value() const { return OperandAt(1); }
7345
7346   virtual bool DataEquals(HValue* other) V8_OVERRIDE { return true; }
7347
7348   DECLARE_CONCRETE_INSTRUCTION(StringCharFromCode)
7349
7350  private:
7351   HStringCharFromCode(HValue* context, HValue* char_code)
7352       : HTemplateInstruction<2>(HType::String()) {
7353     SetOperandAt(0, context);
7354     SetOperandAt(1, char_code);
7355     set_representation(Representation::Tagged());
7356     SetFlag(kUseGVN);
7357     SetChangesFlag(kNewSpacePromotion);
7358   }
7359
7360   virtual bool IsDeletable() const V8_OVERRIDE {
7361     return !value()->ToNumberCanBeObserved();
7362   }
7363 };
7364
7365
7366 template <int V>
7367 class HMaterializedLiteral : public HTemplateInstruction<V> {
7368  public:
7369   HMaterializedLiteral<V>(int index, int depth, AllocationSiteMode mode)
7370       : literal_index_(index), depth_(depth), allocation_site_mode_(mode) {
7371     this->set_representation(Representation::Tagged());
7372   }
7373
7374   HMaterializedLiteral<V>(int index, int depth)
7375       : literal_index_(index), depth_(depth),
7376         allocation_site_mode_(DONT_TRACK_ALLOCATION_SITE) {
7377     this->set_representation(Representation::Tagged());
7378   }
7379
7380   int literal_index() const { return literal_index_; }
7381   int depth() const { return depth_; }
7382   AllocationSiteMode allocation_site_mode() const {
7383     return allocation_site_mode_;
7384   }
7385
7386  private:
7387   virtual bool IsDeletable() const V8_FINAL V8_OVERRIDE { return true; }
7388
7389   int literal_index_;
7390   int depth_;
7391   AllocationSiteMode allocation_site_mode_;
7392 };
7393
7394
7395 class HRegExpLiteral V8_FINAL : public HMaterializedLiteral<1> {
7396  public:
7397   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P4(HRegExpLiteral,
7398                                               Handle<FixedArray>,
7399                                               Handle<String>,
7400                                               Handle<String>,
7401                                               int);
7402
7403   HValue* context() { return OperandAt(0); }
7404   Handle<FixedArray> literals() { return literals_; }
7405   Handle<String> pattern() { return pattern_; }
7406   Handle<String> flags() { return flags_; }
7407
7408   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
7409     return Representation::Tagged();
7410   }
7411
7412   DECLARE_CONCRETE_INSTRUCTION(RegExpLiteral)
7413
7414  private:
7415   HRegExpLiteral(HValue* context,
7416                  Handle<FixedArray> literals,
7417                  Handle<String> pattern,
7418                  Handle<String> flags,
7419                  int literal_index)
7420       : HMaterializedLiteral<1>(literal_index, 0),
7421         literals_(literals),
7422         pattern_(pattern),
7423         flags_(flags) {
7424     SetOperandAt(0, context);
7425     SetAllSideEffects();
7426     set_type(HType::JSObject());
7427   }
7428
7429   Handle<FixedArray> literals_;
7430   Handle<String> pattern_;
7431   Handle<String> flags_;
7432 };
7433
7434
7435 class HFunctionLiteral V8_FINAL : public HTemplateInstruction<1> {
7436  public:
7437   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P2(HFunctionLiteral,
7438                                               Handle<SharedFunctionInfo>,
7439                                               bool);
7440   HValue* context() { return OperandAt(0); }
7441
7442   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
7443     return Representation::Tagged();
7444   }
7445
7446   DECLARE_CONCRETE_INSTRUCTION(FunctionLiteral)
7447
7448   Handle<SharedFunctionInfo> shared_info() const { return shared_info_; }
7449   bool pretenure() const { return pretenure_; }
7450   bool has_no_literals() const { return has_no_literals_; }
7451   bool is_generator() const { return is_generator_; }
7452   StrictMode strict_mode() const { return strict_mode_; }
7453
7454  private:
7455   HFunctionLiteral(HValue* context,
7456                    Handle<SharedFunctionInfo> shared,
7457                    bool pretenure)
7458       : HTemplateInstruction<1>(HType::JSObject()),
7459         shared_info_(shared),
7460         pretenure_(pretenure),
7461         has_no_literals_(shared->num_literals() == 0),
7462         is_generator_(shared->is_generator()),
7463         strict_mode_(shared->strict_mode()) {
7464     SetOperandAt(0, context);
7465     set_representation(Representation::Tagged());
7466     SetChangesFlag(kNewSpacePromotion);
7467   }
7468
7469   virtual bool IsDeletable() const V8_OVERRIDE { return true; }
7470
7471   Handle<SharedFunctionInfo> shared_info_;
7472   bool pretenure_ : 1;
7473   bool has_no_literals_ : 1;
7474   bool is_generator_ : 1;
7475   StrictMode strict_mode_;
7476 };
7477
7478
7479 class HTypeof V8_FINAL : public HTemplateInstruction<2> {
7480  public:
7481   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P1(HTypeof, HValue*);
7482
7483   HValue* context() const { return OperandAt(0); }
7484   HValue* value() const { return OperandAt(1); }
7485
7486   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
7487
7488   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
7489     return Representation::Tagged();
7490   }
7491
7492   DECLARE_CONCRETE_INSTRUCTION(Typeof)
7493
7494  private:
7495   explicit HTypeof(HValue* context, HValue* value) {
7496     SetOperandAt(0, context);
7497     SetOperandAt(1, value);
7498     set_representation(Representation::Tagged());
7499   }
7500
7501   virtual bool IsDeletable() const V8_OVERRIDE { return true; }
7502 };
7503
7504
7505 class HTrapAllocationMemento V8_FINAL : public HTemplateInstruction<1> {
7506  public:
7507   DECLARE_INSTRUCTION_FACTORY_P1(HTrapAllocationMemento, HValue*);
7508
7509   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
7510     return Representation::Tagged();
7511   }
7512
7513   HValue* object() { return OperandAt(0); }
7514
7515   DECLARE_CONCRETE_INSTRUCTION(TrapAllocationMemento)
7516
7517  private:
7518   explicit HTrapAllocationMemento(HValue* obj) {
7519     SetOperandAt(0, obj);
7520   }
7521 };
7522
7523
7524 class HToFastProperties V8_FINAL : public HUnaryOperation {
7525  public:
7526   DECLARE_INSTRUCTION_FACTORY_P1(HToFastProperties, HValue*);
7527
7528   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
7529     return Representation::Tagged();
7530   }
7531
7532   DECLARE_CONCRETE_INSTRUCTION(ToFastProperties)
7533
7534  private:
7535   explicit HToFastProperties(HValue* value) : HUnaryOperation(value) {
7536     set_representation(Representation::Tagged());
7537     SetChangesFlag(kNewSpacePromotion);
7538
7539     // This instruction is not marked as kChangesMaps, but does
7540     // change the map of the input operand. Use it only when creating
7541     // object literals via a runtime call.
7542     DCHECK(value->IsCallRuntime());
7543 #ifdef DEBUG
7544     const Runtime::Function* function = HCallRuntime::cast(value)->function();
7545     DCHECK(function->function_id == Runtime::kCreateObjectLiteral);
7546 #endif
7547   }
7548
7549   virtual bool IsDeletable() const V8_OVERRIDE { return true; }
7550 };
7551
7552
7553 class HDateField V8_FINAL : public HUnaryOperation {
7554  public:
7555   DECLARE_INSTRUCTION_FACTORY_P2(HDateField, HValue*, Smi*);
7556
7557   Smi* index() const { return index_; }
7558
7559   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
7560     return Representation::Tagged();
7561   }
7562
7563   DECLARE_CONCRETE_INSTRUCTION(DateField)
7564
7565  private:
7566   HDateField(HValue* date, Smi* index)
7567       : HUnaryOperation(date), index_(index) {
7568     set_representation(Representation::Tagged());
7569   }
7570
7571   Smi* index_;
7572 };
7573
7574
7575 class HSeqStringGetChar V8_FINAL : public HTemplateInstruction<2> {
7576  public:
7577   static HInstruction* New(Zone* zone,
7578                            HValue* context,
7579                            String::Encoding encoding,
7580                            HValue* string,
7581                            HValue* index);
7582
7583   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
7584     return (index == 0) ? Representation::Tagged()
7585                         : Representation::Integer32();
7586   }
7587
7588   String::Encoding encoding() const { return encoding_; }
7589   HValue* string() const { return OperandAt(0); }
7590   HValue* index() const { return OperandAt(1); }
7591
7592   DECLARE_CONCRETE_INSTRUCTION(SeqStringGetChar)
7593
7594  protected:
7595   virtual bool DataEquals(HValue* other) V8_OVERRIDE {
7596     return encoding() == HSeqStringGetChar::cast(other)->encoding();
7597   }
7598
7599   virtual Range* InferRange(Zone* zone) V8_OVERRIDE {
7600     if (encoding() == String::ONE_BYTE_ENCODING) {
7601       return new(zone) Range(0, String::kMaxOneByteCharCode);
7602     } else {
7603       DCHECK_EQ(String::TWO_BYTE_ENCODING, encoding());
7604       return  new(zone) Range(0, String::kMaxUtf16CodeUnit);
7605     }
7606   }
7607
7608  private:
7609   HSeqStringGetChar(String::Encoding encoding,
7610                     HValue* string,
7611                     HValue* index) : encoding_(encoding) {
7612     SetOperandAt(0, string);
7613     SetOperandAt(1, index);
7614     set_representation(Representation::Integer32());
7615     SetFlag(kUseGVN);
7616     SetDependsOnFlag(kStringChars);
7617   }
7618
7619   virtual bool IsDeletable() const V8_OVERRIDE { return true; }
7620
7621   String::Encoding encoding_;
7622 };
7623
7624
7625 class HSeqStringSetChar V8_FINAL : public HTemplateInstruction<4> {
7626  public:
7627   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P4(
7628       HSeqStringSetChar, String::Encoding,
7629       HValue*, HValue*, HValue*);
7630
7631   String::Encoding encoding() { return encoding_; }
7632   HValue* context() { return OperandAt(0); }
7633   HValue* string() { return OperandAt(1); }
7634   HValue* index() { return OperandAt(2); }
7635   HValue* value() { return OperandAt(3); }
7636
7637   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
7638     return (index <= 1) ? Representation::Tagged()
7639                         : Representation::Integer32();
7640   }
7641
7642   DECLARE_CONCRETE_INSTRUCTION(SeqStringSetChar)
7643
7644  private:
7645   HSeqStringSetChar(HValue* context,
7646                     String::Encoding encoding,
7647                     HValue* string,
7648                     HValue* index,
7649                     HValue* value) : encoding_(encoding) {
7650     SetOperandAt(0, context);
7651     SetOperandAt(1, string);
7652     SetOperandAt(2, index);
7653     SetOperandAt(3, value);
7654     set_representation(Representation::Tagged());
7655     SetChangesFlag(kStringChars);
7656   }
7657
7658   String::Encoding encoding_;
7659 };
7660
7661
7662 class HCheckMapValue V8_FINAL : public HTemplateInstruction<2> {
7663  public:
7664   DECLARE_INSTRUCTION_FACTORY_P2(HCheckMapValue, HValue*, HValue*);
7665
7666   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
7667     return Representation::Tagged();
7668   }
7669
7670   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
7671
7672   virtual HType CalculateInferredType() V8_OVERRIDE {
7673     if (value()->type().IsHeapObject()) return value()->type();
7674     return HType::HeapObject();
7675   }
7676
7677   HValue* value() const { return OperandAt(0); }
7678   HValue* map() const { return OperandAt(1); }
7679
7680   virtual HValue* Canonicalize() V8_OVERRIDE;
7681
7682   DECLARE_CONCRETE_INSTRUCTION(CheckMapValue)
7683
7684  protected:
7685   virtual int RedefinedOperandIndex() { return 0; }
7686
7687   virtual bool DataEquals(HValue* other) V8_OVERRIDE {
7688     return true;
7689   }
7690
7691  private:
7692   HCheckMapValue(HValue* value, HValue* map)
7693       : HTemplateInstruction<2>(HType::HeapObject()) {
7694     SetOperandAt(0, value);
7695     SetOperandAt(1, map);
7696     set_representation(Representation::Tagged());
7697     SetFlag(kUseGVN);
7698     SetDependsOnFlag(kMaps);
7699     SetDependsOnFlag(kElementsKind);
7700   }
7701 };
7702
7703
7704 class HForInPrepareMap V8_FINAL : public HTemplateInstruction<2> {
7705  public:
7706   DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P1(HForInPrepareMap, HValue*);
7707
7708   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
7709     return Representation::Tagged();
7710   }
7711
7712   HValue* context() const { return OperandAt(0); }
7713   HValue* enumerable() const { return OperandAt(1); }
7714
7715   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
7716
7717   virtual HType CalculateInferredType() V8_OVERRIDE {
7718     return HType::Tagged();
7719   }
7720
7721   DECLARE_CONCRETE_INSTRUCTION(ForInPrepareMap);
7722
7723  private:
7724   HForInPrepareMap(HValue* context,
7725                    HValue* object) {
7726     SetOperandAt(0, context);
7727     SetOperandAt(1, object);
7728     set_representation(Representation::Tagged());
7729     SetAllSideEffects();
7730   }
7731 };
7732
7733
7734 class HForInCacheArray V8_FINAL : public HTemplateInstruction<2> {
7735  public:
7736   DECLARE_INSTRUCTION_FACTORY_P3(HForInCacheArray, HValue*, HValue*, int);
7737
7738   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
7739     return Representation::Tagged();
7740   }
7741
7742   HValue* enumerable() const { return OperandAt(0); }
7743   HValue* map() const { return OperandAt(1); }
7744   int idx() const { return idx_; }
7745
7746   HForInCacheArray* index_cache() {
7747     return index_cache_;
7748   }
7749
7750   void set_index_cache(HForInCacheArray* index_cache) {
7751     index_cache_ = index_cache;
7752   }
7753
7754   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
7755
7756   virtual HType CalculateInferredType() V8_OVERRIDE {
7757     return HType::Tagged();
7758   }
7759
7760   DECLARE_CONCRETE_INSTRUCTION(ForInCacheArray);
7761
7762  private:
7763   HForInCacheArray(HValue* enumerable,
7764                    HValue* keys,
7765                    int idx) : idx_(idx) {
7766     SetOperandAt(0, enumerable);
7767     SetOperandAt(1, keys);
7768     set_representation(Representation::Tagged());
7769   }
7770
7771   int idx_;
7772   HForInCacheArray* index_cache_;
7773 };
7774
7775
7776 class HLoadFieldByIndex V8_FINAL : public HTemplateInstruction<2> {
7777  public:
7778   DECLARE_INSTRUCTION_FACTORY_P2(HLoadFieldByIndex, HValue*, HValue*);
7779
7780   HLoadFieldByIndex(HValue* object,
7781                     HValue* index) {
7782     SetOperandAt(0, object);
7783     SetOperandAt(1, index);
7784     SetChangesFlag(kNewSpacePromotion);
7785     set_representation(Representation::Tagged());
7786   }
7787
7788   virtual Representation RequiredInputRepresentation(int index) V8_OVERRIDE {
7789     if (index == 1) {
7790       return Representation::Smi();
7791     } else {
7792       return Representation::Tagged();
7793     }
7794   }
7795
7796   HValue* object() const { return OperandAt(0); }
7797   HValue* index() const { return OperandAt(1); }
7798
7799   virtual OStream& PrintDataTo(OStream& os) const V8_OVERRIDE;  // NOLINT
7800
7801   virtual HType CalculateInferredType() V8_OVERRIDE {
7802     return HType::Tagged();
7803   }
7804
7805   DECLARE_CONCRETE_INSTRUCTION(LoadFieldByIndex);
7806
7807  private:
7808   virtual bool IsDeletable() const V8_OVERRIDE { return true; }
7809 };
7810
7811
7812 class HStoreFrameContext: public HUnaryOperation {
7813  public:
7814   DECLARE_INSTRUCTION_FACTORY_P1(HStoreFrameContext, HValue*);
7815
7816   HValue* context() { return OperandAt(0); }
7817
7818   virtual Representation RequiredInputRepresentation(int index) {
7819     return Representation::Tagged();
7820   }
7821
7822   DECLARE_CONCRETE_INSTRUCTION(StoreFrameContext)
7823  private:
7824   explicit HStoreFrameContext(HValue* context)
7825       : HUnaryOperation(context) {
7826     set_representation(Representation::Tagged());
7827     SetChangesFlag(kContextSlots);
7828   }
7829 };
7830
7831
7832 class HAllocateBlockContext: public HTemplateInstruction<2> {
7833  public:
7834   DECLARE_INSTRUCTION_FACTORY_P3(HAllocateBlockContext, HValue*,
7835                                  HValue*, Handle<ScopeInfo>);
7836   HValue* context() const { return OperandAt(0); }
7837   HValue* function() const { return OperandAt(1); }
7838   Handle<ScopeInfo> scope_info() const { return scope_info_; }
7839
7840   virtual Representation RequiredInputRepresentation(int index) {
7841     return Representation::Tagged();
7842   }
7843
7844   virtual OStream& PrintDataTo(OStream& os) const;  // NOLINT
7845
7846   DECLARE_CONCRETE_INSTRUCTION(AllocateBlockContext)
7847
7848  private:
7849   HAllocateBlockContext(HValue* context,
7850                         HValue* function,
7851                         Handle<ScopeInfo> scope_info)
7852       : scope_info_(scope_info) {
7853     SetOperandAt(0, context);
7854     SetOperandAt(1, function);
7855     set_representation(Representation::Tagged());
7856   }
7857
7858   Handle<ScopeInfo> scope_info_;
7859 };
7860
7861
7862
7863 #undef DECLARE_INSTRUCTION
7864 #undef DECLARE_CONCRETE_INSTRUCTION
7865
7866 } }  // namespace v8::internal
7867
7868 #endif  // V8_HYDROGEN_INSTRUCTIONS_H_