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