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/base/bits.h"
12#include "src/code-stubs.h"
13#include "src/conversions.h"
14#include "src/data-flow.h"
15#include "src/deoptimizer.h"
16#include "src/feedback-slots.h"
17#include "src/hydrogen-types.h"
18#include "src/small-pointer-list.h"
19#include "src/unique.h"
20#include "src/utils.h"
21#include "src/zone.h"
22
23namespace v8 {
24namespace internal {
25
26// Forward declarations.
27struct ChangesOf;
28class HBasicBlock;
29class HDiv;
30class HEnvironment;
31class HInferRepresentationPhase;
32class HInstruction;
33class HLoopInformation;
34class HStoreNamedField;
35class HValue;
36class LInstruction;
37class LChunkBuilder;
38class OStream;
39
40#define HYDROGEN_ABSTRACT_INSTRUCTION_LIST(V) \
41  V(ArithmeticBinaryOperation)                \
42  V(BinaryOperation)                          \
43  V(BitwiseBinaryOperation)                   \
44  V(ControlInstruction)                       \
45  V(Instruction)
46
47
48#define HYDROGEN_CONCRETE_INSTRUCTION_LIST(V) \
49  V(AbnormalExit)                             \
50  V(AccessArgumentsAt)                        \
51  V(Add)                                      \
52  V(AllocateBlockContext)                     \
53  V(Allocate)                                 \
54  V(ApplyArguments)                           \
55  V(ArgumentsElements)                        \
56  V(ArgumentsLength)                          \
57  V(ArgumentsObject)                          \
58  V(Bitwise)                                  \
59  V(BlockEntry)                               \
60  V(BoundsCheck)                              \
61  V(BoundsCheckBaseIndexInformation)          \
62  V(Branch)                                   \
63  V(CallWithDescriptor)                       \
64  V(CallJSFunction)                           \
65  V(CallFunction)                             \
66  V(CallNew)                                  \
67  V(CallNewArray)                             \
68  V(CallRuntime)                              \
69  V(CallStub)                                 \
70  V(CapturedObject)                           \
71  V(Change)                                   \
72  V(CheckHeapObject)                          \
73  V(CheckInstanceType)                        \
74  V(CheckMaps)                                \
75  V(CheckMapValue)                            \
76  V(CheckSmi)                                 \
77  V(CheckValue)                               \
78  V(ClampToUint8)                             \
79  V(ClassOfTestAndBranch)                     \
80  V(CompareNumericAndBranch)                  \
81  V(CompareHoleAndBranch)                     \
82  V(CompareGeneric)                           \
83  V(CompareMinusZeroAndBranch)                \
84  V(CompareObjectEqAndBranch)                 \
85  V(CompareMap)                               \
86  V(Constant)                                 \
87  V(ConstructDouble)                          \
88  V(Context)                                  \
89  V(DateField)                                \
90  V(DebugBreak)                               \
91  V(DeclareGlobals)                           \
92  V(Deoptimize)                               \
93  V(Div)                                      \
94  V(DoubleBits)                               \
95  V(DummyUse)                                 \
96  V(EnterInlined)                             \
97  V(EnvironmentMarker)                        \
98  V(ForceRepresentation)                      \
99  V(ForInCacheArray)                          \
100  V(ForInPrepareMap)                          \
101  V(FunctionLiteral)                          \
102  V(GetCachedArrayIndex)                      \
103  V(Goto)                                     \
104  V(HasCachedArrayIndexAndBranch)             \
105  V(HasInstanceTypeAndBranch)                 \
106  V(InnerAllocatedObject)                     \
107  V(InstanceOf)                               \
108  V(InstanceOfKnownGlobal)                    \
109  V(InvokeFunction)                           \
110  V(IsConstructCallAndBranch)                 \
111  V(IsObjectAndBranch)                        \
112  V(IsStringAndBranch)                        \
113  V(IsSmiAndBranch)                           \
114  V(IsUndetectableAndBranch)                  \
115  V(LeaveInlined)                             \
116  V(LoadContextSlot)                          \
117  V(LoadFieldByIndex)                         \
118  V(LoadFunctionPrototype)                    \
119  V(LoadGlobalCell)                           \
120  V(LoadGlobalGeneric)                        \
121  V(LoadKeyed)                                \
122  V(LoadKeyedGeneric)                         \
123  V(LoadNamedField)                           \
124  V(LoadNamedGeneric)                         \
125  V(LoadRoot)                                 \
126  V(MapEnumLength)                            \
127  V(MathFloorOfDiv)                           \
128  V(MathMinMax)                               \
129  V(Mod)                                      \
130  V(Mul)                                      \
131  V(OsrEntry)                                 \
132  V(Parameter)                                \
133  V(Power)                                    \
134  V(PushArguments)                            \
135  V(RegExpLiteral)                            \
136  V(Return)                                   \
137  V(Ror)                                      \
138  V(Sar)                                      \
139  V(SeqStringGetChar)                         \
140  V(SeqStringSetChar)                         \
141  V(Shl)                                      \
142  V(Shr)                                      \
143  V(Simulate)                                 \
144  V(StackCheck)                               \
145  V(StoreCodeEntry)                           \
146  V(StoreContextSlot)                         \
147  V(StoreFrameContext)                        \
148  V(StoreGlobalCell)                          \
149  V(StoreKeyed)                               \
150  V(StoreKeyedGeneric)                        \
151  V(StoreNamedField)                          \
152  V(StoreNamedGeneric)                        \
153  V(StringAdd)                                \
154  V(StringCharCodeAt)                         \
155  V(StringCharFromCode)                       \
156  V(StringCompareAndBranch)                   \
157  V(Sub)                                      \
158  V(TailCallThroughMegamorphicCache)          \
159  V(ThisFunction)                             \
160  V(ToFastProperties)                         \
161  V(TransitionElementsKind)                   \
162  V(TrapAllocationMemento)                    \
163  V(Typeof)                                   \
164  V(TypeofIsAndBranch)                        \
165  V(UnaryMathOperation)                       \
166  V(UnknownOSRValue)                          \
167  V(UseConst)                                 \
168  V(WrapReceiver)
169
170#define GVN_TRACKED_FLAG_LIST(V)               \
171  V(NewSpacePromotion)
172
173#define GVN_UNTRACKED_FLAG_LIST(V)             \
174  V(ArrayElements)                             \
175  V(ArrayLengths)                              \
176  V(StringLengths)                             \
177  V(BackingStoreFields)                        \
178  V(Calls)                                     \
179  V(ContextSlots)                              \
180  V(DoubleArrayElements)                       \
181  V(DoubleFields)                              \
182  V(ElementsKind)                              \
183  V(ElementsPointer)                           \
184  V(GlobalVars)                                \
185  V(InobjectFields)                            \
186  V(Maps)                                      \
187  V(OsrEntries)                                \
188  V(ExternalMemory)                            \
189  V(StringChars)                               \
190  V(TypedArrayElements)
191
192
193#define DECLARE_ABSTRACT_INSTRUCTION(type)                              \
194  virtual bool Is##type() const FINAL OVERRIDE { return true; }   \
195  static H##type* cast(HValue* value) {                                 \
196    DCHECK(value->Is##type());                                          \
197    return reinterpret_cast<H##type*>(value);                           \
198  }
199
200
201#define DECLARE_CONCRETE_INSTRUCTION(type)              \
202  virtual LInstruction* CompileToLithium(               \
203     LChunkBuilder* builder) FINAL OVERRIDE;      \
204  static H##type* cast(HValue* value) {                 \
205    DCHECK(value->Is##type());                          \
206    return reinterpret_cast<H##type*>(value);           \
207  }                                                     \
208  virtual Opcode opcode() const FINAL OVERRIDE {  \
209    return HValue::k##type;                             \
210  }
211
212
213enum PropertyAccessType { LOAD, STORE };
214
215
216class Range FINAL : public ZoneObject {
217 public:
218  Range()
219      : lower_(kMinInt),
220        upper_(kMaxInt),
221        next_(NULL),
222        can_be_minus_zero_(false) { }
223
224  Range(int32_t lower, int32_t upper)
225      : lower_(lower),
226        upper_(upper),
227        next_(NULL),
228        can_be_minus_zero_(false) { }
229
230  int32_t upper() const { return upper_; }
231  int32_t lower() const { return lower_; }
232  Range* next() const { return next_; }
233  Range* CopyClearLower(Zone* zone) const {
234    return new(zone) Range(kMinInt, upper_);
235  }
236  Range* CopyClearUpper(Zone* zone) const {
237    return new(zone) Range(lower_, kMaxInt);
238  }
239  Range* Copy(Zone* zone) const {
240    Range* result = new(zone) Range(lower_, upper_);
241    result->set_can_be_minus_zero(CanBeMinusZero());
242    return result;
243  }
244  int32_t Mask() const;
245  void set_can_be_minus_zero(bool b) { can_be_minus_zero_ = b; }
246  bool CanBeMinusZero() const { return CanBeZero() && can_be_minus_zero_; }
247  bool CanBeZero() const { return upper_ >= 0 && lower_ <= 0; }
248  bool CanBeNegative() const { return lower_ < 0; }
249  bool CanBePositive() const { return upper_ > 0; }
250  bool Includes(int value) const { return lower_ <= value && upper_ >= value; }
251  bool IsMostGeneric() const {
252    return lower_ == kMinInt && upper_ == kMaxInt && CanBeMinusZero();
253  }
254  bool IsInSmiRange() const {
255    return lower_ >= Smi::kMinValue && upper_ <= Smi::kMaxValue;
256  }
257  void ClampToSmi() {
258    lower_ = Max(lower_, Smi::kMinValue);
259    upper_ = Min(upper_, Smi::kMaxValue);
260  }
261  void KeepOrder();
262#ifdef DEBUG
263  void Verify() const;
264#endif
265
266  void StackUpon(Range* other) {
267    Intersect(other);
268    next_ = other;
269  }
270
271  void Intersect(Range* other);
272  void Union(Range* other);
273  void CombinedMax(Range* other);
274  void CombinedMin(Range* other);
275
276  void AddConstant(int32_t value);
277  void Sar(int32_t value);
278  void Shl(int32_t value);
279  bool AddAndCheckOverflow(const Representation& r, Range* other);
280  bool SubAndCheckOverflow(const Representation& r, Range* other);
281  bool MulAndCheckOverflow(const Representation& r, Range* other);
282
283 private:
284  int32_t lower_;
285  int32_t upper_;
286  Range* next_;
287  bool can_be_minus_zero_;
288};
289
290
291class HUseListNode: public ZoneObject {
292 public:
293  HUseListNode(HValue* value, int index, HUseListNode* tail)
294      : tail_(tail), value_(value), index_(index) {
295  }
296
297  HUseListNode* tail();
298  HValue* value() const { return value_; }
299  int index() const { return index_; }
300
301  void set_tail(HUseListNode* list) { tail_ = list; }
302
303#ifdef DEBUG
304  void Zap() {
305    tail_ = reinterpret_cast<HUseListNode*>(1);
306    value_ = NULL;
307    index_ = -1;
308  }
309#endif
310
311 private:
312  HUseListNode* tail_;
313  HValue* value_;
314  int index_;
315};
316
317
318// We reuse use list nodes behind the scenes as uses are added and deleted.
319// This class is the safe way to iterate uses while deleting them.
320class HUseIterator FINAL BASE_EMBEDDED {
321 public:
322  bool Done() { return current_ == NULL; }
323  void Advance();
324
325  HValue* value() {
326    DCHECK(!Done());
327    return value_;
328  }
329
330  int index() {
331    DCHECK(!Done());
332    return index_;
333  }
334
335 private:
336  explicit HUseIterator(HUseListNode* head);
337
338  HUseListNode* current_;
339  HUseListNode* next_;
340  HValue* value_;
341  int index_;
342
343  friend class HValue;
344};
345
346
347// All tracked flags should appear before untracked ones.
348enum GVNFlag {
349  // Declare global value numbering flags.
350#define DECLARE_FLAG(Type) k##Type,
351  GVN_TRACKED_FLAG_LIST(DECLARE_FLAG)
352  GVN_UNTRACKED_FLAG_LIST(DECLARE_FLAG)
353#undef DECLARE_FLAG
354#define COUNT_FLAG(Type) + 1
355  kNumberOfTrackedSideEffects = 0 GVN_TRACKED_FLAG_LIST(COUNT_FLAG),
356  kNumberOfUntrackedSideEffects = 0 GVN_UNTRACKED_FLAG_LIST(COUNT_FLAG),
357#undef COUNT_FLAG
358  kNumberOfFlags = kNumberOfTrackedSideEffects + kNumberOfUntrackedSideEffects
359};
360
361
362static inline GVNFlag GVNFlagFromInt(int i) {
363  DCHECK(i >= 0);
364  DCHECK(i < kNumberOfFlags);
365  return static_cast<GVNFlag>(i);
366}
367
368
369class DecompositionResult FINAL BASE_EMBEDDED {
370 public:
371  DecompositionResult() : base_(NULL), offset_(0), scale_(0) {}
372
373  HValue* base() { return base_; }
374  int offset() { return offset_; }
375  int scale() { return scale_; }
376
377  bool Apply(HValue* other_base, int other_offset, int other_scale = 0) {
378    if (base_ == NULL) {
379      base_ = other_base;
380      offset_ = other_offset;
381      scale_ = other_scale;
382      return true;
383    } else {
384      if (scale_ == 0) {
385        base_ = other_base;
386        offset_ += other_offset;
387        scale_ = other_scale;
388        return true;
389      } else {
390        return false;
391      }
392    }
393  }
394
395  void SwapValues(HValue** other_base, int* other_offset, int* other_scale) {
396    swap(&base_, other_base);
397    swap(&offset_, other_offset);
398    swap(&scale_, other_scale);
399  }
400
401 private:
402  template <class T> void swap(T* a, T* b) {
403    T c(*a);
404    *a = *b;
405    *b = c;
406  }
407
408  HValue* base_;
409  int offset_;
410  int scale_;
411};
412
413
414typedef EnumSet<GVNFlag, int32_t> GVNFlagSet;
415
416
417// This class encapsulates encoding and decoding of sources positions from
418// which hydrogen values originated.
419// When FLAG_track_hydrogen_positions is set this object encodes the
420// identifier of the inlining and absolute offset from the start of the
421// inlined function.
422// When the flag is not set we simply track absolute offset from the
423// script start.
424class HSourcePosition {
425 public:
426  HSourcePosition(const HSourcePosition& other) : value_(other.value_) { }
427
428  static HSourcePosition Unknown() {
429    return HSourcePosition(RelocInfo::kNoPosition);
430  }
431
432  bool IsUnknown() const { return value_ == RelocInfo::kNoPosition; }
433
434  int position() const { return PositionField::decode(value_); }
435  void set_position(int position) {
436    if (FLAG_hydrogen_track_positions) {
437      value_ = static_cast<int>(PositionField::update(value_, position));
438    } else {
439      value_ = position;
440    }
441  }
442
443  int inlining_id() const { return InliningIdField::decode(value_); }
444  void set_inlining_id(int inlining_id) {
445    if (FLAG_hydrogen_track_positions) {
446      value_ = static_cast<int>(InliningIdField::update(value_, inlining_id));
447    }
448  }
449
450  int raw() const { return value_; }
451
452 private:
453  typedef BitField<int, 0, 9> InliningIdField;
454
455  // Offset from the start of the inlined function.
456  typedef BitField<int, 9, 23> PositionField;
457
458  explicit HSourcePosition(int value) : value_(value) { }
459
460  friend class HPositionInfo;
461  friend class LCodeGenBase;
462
463  // If FLAG_hydrogen_track_positions is set contains bitfields InliningIdField
464  // and PositionField.
465  // Otherwise contains absolute offset from the script start.
466  int value_;
467};
468
469
470OStream& operator<<(OStream& os, const HSourcePosition& p);
471
472
473class HValue : public ZoneObject {
474 public:
475  static const int kNoNumber = -1;
476
477  enum Flag {
478    kFlexibleRepresentation,
479    kCannotBeTagged,
480    // Participate in Global Value Numbering, i.e. elimination of
481    // unnecessary recomputations. If an instruction sets this flag, it must
482    // implement DataEquals(), which will be used to determine if other
483    // occurrences of the instruction are indeed the same.
484    kUseGVN,
485    // Track instructions that are dominating side effects. If an instruction
486    // sets this flag, it must implement HandleSideEffectDominator() and should
487    // indicate which side effects to track by setting GVN flags.
488    kTrackSideEffectDominators,
489    kCanOverflow,
490    kBailoutOnMinusZero,
491    kCanBeDivByZero,
492    kLeftCanBeMinInt,
493    kLeftCanBeNegative,
494    kLeftCanBePositive,
495    kAllowUndefinedAsNaN,
496    kIsArguments,
497    kTruncatingToInt32,
498    kAllUsesTruncatingToInt32,
499    kTruncatingToSmi,
500    kAllUsesTruncatingToSmi,
501    // Set after an instruction is killed.
502    kIsDead,
503    // Instructions that are allowed to produce full range unsigned integer
504    // values are marked with kUint32 flag. If arithmetic shift or a load from
505    // EXTERNAL_UINT32_ELEMENTS array is not marked with this flag
506    // it will deoptimize if result does not fit into signed integer range.
507    // HGraph::ComputeSafeUint32Operations is responsible for setting this
508    // flag.
509    kUint32,
510    kHasNoObservableSideEffects,
511    // Indicates an instruction shouldn't be replaced by optimization, this flag
512    // is useful to set in cases where recomputing a value is cheaper than
513    // extending the value's live range and spilling it.
514    kCantBeReplaced,
515    // Indicates the instruction is live during dead code elimination.
516    kIsLive,
517
518    // HEnvironmentMarkers are deleted before dead code
519    // elimination takes place, so they can repurpose the kIsLive flag:
520    kEndsLiveRange = kIsLive,
521
522    // TODO(everyone): Don't forget to update this!
523    kLastFlag = kIsLive
524  };
525
526  STATIC_ASSERT(kLastFlag < kBitsPerInt);
527
528  static HValue* cast(HValue* value) { return value; }
529
530  enum Opcode {
531    // Declare a unique enum value for each hydrogen instruction.
532  #define DECLARE_OPCODE(type) k##type,
533    HYDROGEN_CONCRETE_INSTRUCTION_LIST(DECLARE_OPCODE)
534    kPhi
535  #undef DECLARE_OPCODE
536  };
537  virtual Opcode opcode() const = 0;
538
539  // Declare a non-virtual predicates for each concrete HInstruction or HValue.
540  #define DECLARE_PREDICATE(type) \
541    bool Is##type() const { return opcode() == k##type; }
542    HYDROGEN_CONCRETE_INSTRUCTION_LIST(DECLARE_PREDICATE)
543  #undef DECLARE_PREDICATE
544    bool IsPhi() const { return opcode() == kPhi; }
545
546  // Declare virtual predicates for abstract HInstruction or HValue
547  #define DECLARE_PREDICATE(type) \
548    virtual bool Is##type() const { return false; }
549    HYDROGEN_ABSTRACT_INSTRUCTION_LIST(DECLARE_PREDICATE)
550  #undef DECLARE_PREDICATE
551
552  bool IsBitwiseBinaryShift() {
553    return IsShl() || IsShr() || IsSar();
554  }
555
556  explicit HValue(HType type = HType::Tagged())
557      : block_(NULL),
558        id_(kNoNumber),
559        type_(type),
560        use_list_(NULL),
561        range_(NULL),
562#ifdef DEBUG
563        range_poisoned_(false),
564#endif
565        flags_(0) {}
566  virtual ~HValue() {}
567
568  virtual HSourcePosition position() const {
569    return HSourcePosition::Unknown();
570  }
571  virtual HSourcePosition operand_position(int index) const {
572    return position();
573  }
574
575  HBasicBlock* block() const { return block_; }
576  void SetBlock(HBasicBlock* block);
577
578  // Note: Never call this method for an unlinked value.
579  Isolate* isolate() const;
580
581  int id() const { return id_; }
582  void set_id(int id) { id_ = id; }
583
584  HUseIterator uses() const { return HUseIterator(use_list_); }
585
586  virtual bool EmitAtUses() { return false; }
587
588  Representation representation() const { return representation_; }
589  void ChangeRepresentation(Representation r) {
590    DCHECK(CheckFlag(kFlexibleRepresentation));
591    DCHECK(!CheckFlag(kCannotBeTagged) || !r.IsTagged());
592    RepresentationChanged(r);
593    representation_ = r;
594    if (r.IsTagged()) {
595      // Tagged is the bottom of the lattice, don't go any further.
596      ClearFlag(kFlexibleRepresentation);
597    }
598  }
599  virtual void AssumeRepresentation(Representation r);
600
601  virtual Representation KnownOptimalRepresentation() {
602    Representation r = representation();
603    if (r.IsTagged()) {
604      HType t = type();
605      if (t.IsSmi()) return Representation::Smi();
606      if (t.IsHeapNumber()) return Representation::Double();
607      if (t.IsHeapObject()) return r;
608      return Representation::None();
609    }
610    return r;
611  }
612
613  HType type() const { return type_; }
614  void set_type(HType new_type) {
615    DCHECK(new_type.IsSubtypeOf(type_));
616    type_ = new_type;
617  }
618
619  // There are HInstructions that do not really change a value, they
620  // only add pieces of information to it (like bounds checks, map checks,
621  // smi checks...).
622  // We call these instructions "informative definitions", or "iDef".
623  // One of the iDef operands is special because it is the value that is
624  // "transferred" to the output, we call it the "redefined operand".
625  // If an HValue is an iDef it must override RedefinedOperandIndex() so that
626  // it does not return kNoRedefinedOperand;
627  static const int kNoRedefinedOperand = -1;
628  virtual int RedefinedOperandIndex() { return kNoRedefinedOperand; }
629  bool IsInformativeDefinition() {
630    return RedefinedOperandIndex() != kNoRedefinedOperand;
631  }
632  HValue* RedefinedOperand() {
633    int index = RedefinedOperandIndex();
634    return index == kNoRedefinedOperand ? NULL : OperandAt(index);
635  }
636
637  bool CanReplaceWithDummyUses();
638
639  virtual int argument_delta() const { return 0; }
640
641  // A purely informative definition is an idef that will not emit code and
642  // should therefore be removed from the graph in the RestoreActualValues
643  // phase (so that live ranges will be shorter).
644  virtual bool IsPurelyInformativeDefinition() { return false; }
645
646  // This method must always return the original HValue SSA definition,
647  // regardless of any chain of iDefs of this value.
648  HValue* ActualValue() {
649    HValue* value = this;
650    int index;
651    while ((index = value->RedefinedOperandIndex()) != kNoRedefinedOperand) {
652      value = value->OperandAt(index);
653    }
654    return value;
655  }
656
657  bool IsInteger32Constant();
658  int32_t GetInteger32Constant();
659  bool EqualsInteger32Constant(int32_t value);
660
661  bool IsDefinedAfter(HBasicBlock* other) const;
662
663  // Operands.
664  virtual int OperandCount() const = 0;
665  virtual HValue* OperandAt(int index) const = 0;
666  void SetOperandAt(int index, HValue* value);
667
668  void DeleteAndReplaceWith(HValue* other);
669  void ReplaceAllUsesWith(HValue* other);
670  bool HasNoUses() const { return use_list_ == NULL; }
671  bool HasOneUse() const {
672    return use_list_ != NULL && use_list_->tail() == NULL;
673  }
674  bool HasMultipleUses() const {
675    return use_list_ != NULL && use_list_->tail() != NULL;
676  }
677  int UseCount() const;
678
679  // Mark this HValue as dead and to be removed from other HValues' use lists.
680  void Kill();
681
682  int flags() const { return flags_; }
683  void SetFlag(Flag f) { flags_ |= (1 << f); }
684  void ClearFlag(Flag f) { flags_ &= ~(1 << f); }
685  bool CheckFlag(Flag f) const { return (flags_ & (1 << f)) != 0; }
686  void CopyFlag(Flag f, HValue* other) {
687    if (other->CheckFlag(f)) SetFlag(f);
688  }
689
690  // Returns true if the flag specified is set for all uses, false otherwise.
691  bool CheckUsesForFlag(Flag f) const;
692  // Same as before and the first one without the flag is returned in value.
693  bool CheckUsesForFlag(Flag f, HValue** value) const;
694  // Returns true if the flag specified is set for all uses, and this set
695  // of uses is non-empty.
696  bool HasAtLeastOneUseWithFlagAndNoneWithout(Flag f) const;
697
698  GVNFlagSet ChangesFlags() const { return changes_flags_; }
699  GVNFlagSet DependsOnFlags() const { return depends_on_flags_; }
700  void SetChangesFlag(GVNFlag f) { changes_flags_.Add(f); }
701  void SetDependsOnFlag(GVNFlag f) { depends_on_flags_.Add(f); }
702  void ClearChangesFlag(GVNFlag f) { changes_flags_.Remove(f); }
703  void ClearDependsOnFlag(GVNFlag f) { depends_on_flags_.Remove(f); }
704  bool CheckChangesFlag(GVNFlag f) const {
705    return changes_flags_.Contains(f);
706  }
707  bool CheckDependsOnFlag(GVNFlag f) const {
708    return depends_on_flags_.Contains(f);
709  }
710  void SetAllSideEffects() { changes_flags_.Add(AllSideEffectsFlagSet()); }
711  void ClearAllSideEffects() {
712    changes_flags_.Remove(AllSideEffectsFlagSet());
713  }
714  bool HasSideEffects() const {
715    return changes_flags_.ContainsAnyOf(AllSideEffectsFlagSet());
716  }
717  bool HasObservableSideEffects() const {
718    return !CheckFlag(kHasNoObservableSideEffects) &&
719        changes_flags_.ContainsAnyOf(AllObservableSideEffectsFlagSet());
720  }
721
722  GVNFlagSet SideEffectFlags() const {
723    GVNFlagSet result = ChangesFlags();
724    result.Intersect(AllSideEffectsFlagSet());
725    return result;
726  }
727
728  GVNFlagSet ObservableChangesFlags() const {
729    GVNFlagSet result = ChangesFlags();
730    result.Intersect(AllObservableSideEffectsFlagSet());
731    return result;
732  }
733
734  Range* range() const {
735    DCHECK(!range_poisoned_);
736    return range_;
737  }
738  bool HasRange() const {
739    DCHECK(!range_poisoned_);
740    return range_ != NULL;
741  }
742#ifdef DEBUG
743  void PoisonRange() { range_poisoned_ = true; }
744#endif
745  void AddNewRange(Range* r, Zone* zone);
746  void RemoveLastAddedRange();
747  void ComputeInitialRange(Zone* zone);
748
749  // Escape analysis helpers.
750  virtual bool HasEscapingOperandAt(int index) { return true; }
751  virtual bool HasOutOfBoundsAccess(int size) { return false; }
752
753  // Representation helpers.
754  virtual Representation observed_input_representation(int index) {
755    return Representation::None();
756  }
757  virtual Representation RequiredInputRepresentation(int index) = 0;
758  virtual void InferRepresentation(HInferRepresentationPhase* h_infer);
759
760  // This gives the instruction an opportunity to replace itself with an
761  // instruction that does the same in some better way.  To replace an
762  // instruction with a new one, first add the new instruction to the graph,
763  // then return it.  Return NULL to have the instruction deleted.
764  virtual HValue* Canonicalize() { return this; }
765
766  bool Equals(HValue* other);
767  virtual intptr_t Hashcode();
768
769  // Compute unique ids upfront that is safe wrt GC and concurrent compilation.
770  virtual void FinalizeUniqueness() { }
771
772  // Printing support.
773  virtual OStream& PrintTo(OStream& os) const = 0;  // NOLINT
774
775  const char* Mnemonic() const;
776
777  // Type information helpers.
778  bool HasMonomorphicJSObjectType();
779
780  // TODO(mstarzinger): For now instructions can override this function to
781  // specify statically known types, once HType can convey more information
782  // it should be based on the HType.
783  virtual Handle<Map> GetMonomorphicJSObjectMap() { return Handle<Map>(); }
784
785  // Updated the inferred type of this instruction and returns true if
786  // it has changed.
787  bool UpdateInferredType();
788
789  virtual HType CalculateInferredType();
790
791  // This function must be overridden for instructions which have the
792  // kTrackSideEffectDominators flag set, to track instructions that are
793  // dominating side effects.
794  // It returns true if it removed an instruction which had side effects.
795  virtual bool HandleSideEffectDominator(GVNFlag side_effect,
796                                         HValue* dominator) {
797    UNREACHABLE();
798    return false;
799  }
800
801  // Check if this instruction has some reason that prevents elimination.
802  bool CannotBeEliminated() const {
803    return HasObservableSideEffects() || !IsDeletable();
804  }
805
806#ifdef DEBUG
807  virtual void Verify() = 0;
808#endif
809
810  virtual bool TryDecompose(DecompositionResult* decomposition) {
811    if (RedefinedOperand() != NULL) {
812      return RedefinedOperand()->TryDecompose(decomposition);
813    } else {
814      return false;
815    }
816  }
817
818  // Returns true conservatively if the program might be able to observe a
819  // ToString() operation on this value.
820  bool ToStringCanBeObserved() const {
821    return ToStringOrToNumberCanBeObserved();
822  }
823
824  // Returns true conservatively if the program might be able to observe a
825  // ToNumber() operation on this value.
826  bool ToNumberCanBeObserved() const {
827    return ToStringOrToNumberCanBeObserved();
828  }
829
830  MinusZeroMode GetMinusZeroMode() {
831    return CheckFlag(kBailoutOnMinusZero)
832        ? FAIL_ON_MINUS_ZERO : TREAT_MINUS_ZERO_AS_ZERO;
833  }
834
835 protected:
836  // This function must be overridden for instructions with flag kUseGVN, to
837  // compare the non-Operand parts of the instruction.
838  virtual bool DataEquals(HValue* other) {
839    UNREACHABLE();
840    return false;
841  }
842
843  bool ToStringOrToNumberCanBeObserved() const {
844    if (type().IsTaggedPrimitive()) return false;
845    if (type().IsJSObject()) return true;
846    return !representation().IsSmiOrInteger32() && !representation().IsDouble();
847  }
848
849  virtual Representation RepresentationFromInputs() {
850    return representation();
851  }
852  virtual Representation RepresentationFromUses();
853  Representation RepresentationFromUseRequirements();
854  bool HasNonSmiUse();
855  virtual void UpdateRepresentation(Representation new_rep,
856                                    HInferRepresentationPhase* h_infer,
857                                    const char* reason);
858  void AddDependantsToWorklist(HInferRepresentationPhase* h_infer);
859
860  virtual void RepresentationChanged(Representation to) { }
861
862  virtual Range* InferRange(Zone* zone);
863  virtual void DeleteFromGraph() = 0;
864  virtual void InternalSetOperandAt(int index, HValue* value) = 0;
865  void clear_block() {
866    DCHECK(block_ != NULL);
867    block_ = NULL;
868  }
869
870  void set_representation(Representation r) {
871    DCHECK(representation_.IsNone() && !r.IsNone());
872    representation_ = r;
873  }
874
875  static GVNFlagSet AllFlagSet() {
876    GVNFlagSet result;
877#define ADD_FLAG(Type) result.Add(k##Type);
878  GVN_TRACKED_FLAG_LIST(ADD_FLAG)
879  GVN_UNTRACKED_FLAG_LIST(ADD_FLAG)
880#undef ADD_FLAG
881    return result;
882  }
883
884  // A flag mask to mark an instruction as having arbitrary side effects.
885  static GVNFlagSet AllSideEffectsFlagSet() {
886    GVNFlagSet result = AllFlagSet();
887    result.Remove(kOsrEntries);
888    return result;
889  }
890  friend OStream& operator<<(OStream& os, const ChangesOf& v);
891
892  // A flag mask of all side effects that can make observable changes in
893  // an executing program (i.e. are not safe to repeat, move or remove);
894  static GVNFlagSet AllObservableSideEffectsFlagSet() {
895    GVNFlagSet result = AllFlagSet();
896    result.Remove(kNewSpacePromotion);
897    result.Remove(kElementsKind);
898    result.Remove(kElementsPointer);
899    result.Remove(kMaps);
900    return result;
901  }
902
903  // Remove the matching use from the use list if present.  Returns the
904  // removed list node or NULL.
905  HUseListNode* RemoveUse(HValue* value, int index);
906
907  void RegisterUse(int index, HValue* new_value);
908
909  HBasicBlock* block_;
910
911  // The id of this instruction in the hydrogen graph, assigned when first
912  // added to the graph. Reflects creation order.
913  int id_;
914
915  Representation representation_;
916  HType type_;
917  HUseListNode* use_list_;
918  Range* range_;
919#ifdef DEBUG
920  bool range_poisoned_;
921#endif
922  int flags_;
923  GVNFlagSet changes_flags_;
924  GVNFlagSet depends_on_flags_;
925
926 private:
927  virtual bool IsDeletable() const { return false; }
928
929  DISALLOW_COPY_AND_ASSIGN(HValue);
930};
931
932// Support for printing various aspects of an HValue.
933struct NameOf {
934  explicit NameOf(const HValue* const v) : value(v) {}
935  const HValue* value;
936};
937
938
939struct TypeOf {
940  explicit TypeOf(const HValue* const v) : value(v) {}
941  const HValue* value;
942};
943
944
945struct ChangesOf {
946  explicit ChangesOf(const HValue* const v) : value(v) {}
947  const HValue* value;
948};
949
950
951OStream& operator<<(OStream& os, const HValue& v);
952OStream& operator<<(OStream& os, const NameOf& v);
953OStream& operator<<(OStream& os, const TypeOf& v);
954OStream& operator<<(OStream& os, const ChangesOf& v);
955
956
957#define DECLARE_INSTRUCTION_FACTORY_P0(I)                                      \
958  static I* New(Zone* zone, HValue* context) {                                 \
959    return new(zone) I();                                                      \
960}
961
962#define DECLARE_INSTRUCTION_FACTORY_P1(I, P1)                                  \
963  static I* New(Zone* zone, HValue* context, P1 p1) {                          \
964    return new(zone) I(p1);                                                    \
965  }
966
967#define DECLARE_INSTRUCTION_FACTORY_P2(I, P1, P2)                              \
968  static I* New(Zone* zone, HValue* context, P1 p1, P2 p2) {                   \
969    return new(zone) I(p1, p2);                                                \
970  }
971
972#define DECLARE_INSTRUCTION_FACTORY_P3(I, P1, P2, P3)                          \
973  static I* New(Zone* zone, HValue* context, P1 p1, P2 p2, P3 p3) {            \
974    return new(zone) I(p1, p2, p3);                                            \
975  }
976
977#define DECLARE_INSTRUCTION_FACTORY_P4(I, P1, P2, P3, P4)                      \
978  static I* New(Zone* zone,                                                    \
979                HValue* context,                                               \
980                P1 p1,                                                         \
981                P2 p2,                                                         \
982                P3 p3,                                                         \
983                P4 p4) {                                                       \
984    return new(zone) I(p1, p2, p3, p4);                                        \
985  }
986
987#define DECLARE_INSTRUCTION_FACTORY_P5(I, P1, P2, P3, P4, P5)                  \
988  static I* New(Zone* zone,                                                    \
989                HValue* context,                                               \
990                P1 p1,                                                         \
991                P2 p2,                                                         \
992                P3 p3,                                                         \
993                P4 p4,                                                         \
994                P5 p5) {                                                       \
995    return new(zone) I(p1, p2, p3, p4, p5);                                    \
996  }
997
998#define DECLARE_INSTRUCTION_FACTORY_P6(I, P1, P2, P3, P4, P5, P6)              \
999  static I* New(Zone* zone,                                                    \
1000                HValue* context,                                               \
1001                P1 p1,                                                         \
1002                P2 p2,                                                         \
1003                P3 p3,                                                         \
1004                P4 p4,                                                         \
1005                P5 p5,                                                         \
1006                P6 p6) {                                                       \
1007    return new(zone) I(p1, p2, p3, p4, p5, p6);                                \
1008  }
1009
1010#define DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P0(I)                         \
1011  static I* New(Zone* zone, HValue* context) {                                 \
1012    return new(zone) I(context);                                               \
1013  }
1014
1015#define DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P1(I, P1)                     \
1016  static I* New(Zone* zone, HValue* context, P1 p1) {                          \
1017    return new(zone) I(context, p1);                                           \
1018  }
1019
1020#define DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P2(I, P1, P2)                 \
1021  static I* New(Zone* zone, HValue* context, P1 p1, P2 p2) {                   \
1022    return new(zone) I(context, p1, p2);                                       \
1023  }
1024
1025#define DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P3(I, P1, P2, P3)             \
1026  static I* New(Zone* zone, HValue* context, P1 p1, P2 p2, P3 p3) {            \
1027    return new(zone) I(context, p1, p2, p3);                                   \
1028  }
1029
1030#define DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P4(I, P1, P2, P3, P4)         \
1031  static I* New(Zone* zone,                                                    \
1032                HValue* context,                                               \
1033                P1 p1,                                                         \
1034                P2 p2,                                                         \
1035                P3 p3,                                                         \
1036                P4 p4) {                                                       \
1037    return new(zone) I(context, p1, p2, p3, p4);                               \
1038  }
1039
1040#define DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P5(I, P1, P2, P3, P4, P5)     \
1041  static I* New(Zone* zone,                                                    \
1042                HValue* context,                                               \
1043                P1 p1,                                                         \
1044                P2 p2,                                                         \
1045                P3 p3,                                                         \
1046                P4 p4,                                                         \
1047                P5 p5) {                                                       \
1048    return new(zone) I(context, p1, p2, p3, p4, p5);                           \
1049  }
1050
1051
1052// A helper class to represent per-operand position information attached to
1053// the HInstruction in the compact form. Uses tagging to distinguish between
1054// case when only instruction's position is available and case when operands'
1055// positions are also available.
1056// In the first case it contains intruction's position as a tagged value.
1057// In the second case it points to an array which contains instruction's
1058// position and operands' positions.
1059class HPositionInfo {
1060 public:
1061  explicit HPositionInfo(int pos) : data_(TagPosition(pos)) { }
1062
1063  HSourcePosition position() const {
1064    if (has_operand_positions()) {
1065      return operand_positions()[kInstructionPosIndex];
1066    }
1067    return HSourcePosition(static_cast<int>(UntagPosition(data_)));
1068  }
1069
1070  void set_position(HSourcePosition pos) {
1071    if (has_operand_positions()) {
1072      operand_positions()[kInstructionPosIndex] = pos;
1073    } else {
1074      data_ = TagPosition(pos.raw());
1075    }
1076  }
1077
1078  void ensure_storage_for_operand_positions(Zone* zone, int operand_count) {
1079    if (has_operand_positions()) {
1080      return;
1081    }
1082
1083    const int length = kFirstOperandPosIndex + operand_count;
1084    HSourcePosition* positions =
1085        zone->NewArray<HSourcePosition>(length);
1086    for (int i = 0; i < length; i++) {
1087      positions[i] = HSourcePosition::Unknown();
1088    }
1089
1090    const HSourcePosition pos = position();
1091    data_ = reinterpret_cast<intptr_t>(positions);
1092    set_position(pos);
1093
1094    DCHECK(has_operand_positions());
1095  }
1096
1097  HSourcePosition operand_position(int idx) const {
1098    if (!has_operand_positions()) {
1099      return position();
1100    }
1101    return *operand_position_slot(idx);
1102  }
1103
1104  void set_operand_position(int idx, HSourcePosition pos) {
1105    *operand_position_slot(idx) = pos;
1106  }
1107
1108 private:
1109  static const intptr_t kInstructionPosIndex = 0;
1110  static const intptr_t kFirstOperandPosIndex = 1;
1111
1112  HSourcePosition* operand_position_slot(int idx) const {
1113    DCHECK(has_operand_positions());
1114    return &(operand_positions()[kFirstOperandPosIndex + idx]);
1115  }
1116
1117  bool has_operand_positions() const {
1118    return !IsTaggedPosition(data_);
1119  }
1120
1121  HSourcePosition* operand_positions() const {
1122    DCHECK(has_operand_positions());
1123    return reinterpret_cast<HSourcePosition*>(data_);
1124  }
1125
1126  static const intptr_t kPositionTag = 1;
1127  static const intptr_t kPositionShift = 1;
1128  static bool IsTaggedPosition(intptr_t val) {
1129    return (val & kPositionTag) != 0;
1130  }
1131  static intptr_t UntagPosition(intptr_t val) {
1132    DCHECK(IsTaggedPosition(val));
1133    return val >> kPositionShift;
1134  }
1135  static intptr_t TagPosition(intptr_t val) {
1136    const intptr_t result = (val << kPositionShift) | kPositionTag;
1137    DCHECK(UntagPosition(result) == val);
1138    return result;
1139  }
1140
1141  intptr_t data_;
1142};
1143
1144
1145class HInstruction : public HValue {
1146 public:
1147  HInstruction* next() const { return next_; }
1148  HInstruction* previous() const { return previous_; }
1149
1150  virtual OStream& PrintTo(OStream& os) const OVERRIDE;  // NOLINT
1151  virtual OStream& PrintDataTo(OStream& os) const;          // NOLINT
1152
1153  bool IsLinked() const { return block() != NULL; }
1154  void Unlink();
1155
1156  void InsertBefore(HInstruction* next);
1157
1158  template<class T> T* Prepend(T* instr) {
1159    instr->InsertBefore(this);
1160    return instr;
1161  }
1162
1163  void InsertAfter(HInstruction* previous);
1164
1165  template<class T> T* Append(T* instr) {
1166    instr->InsertAfter(this);
1167    return instr;
1168  }
1169
1170  // The position is a write-once variable.
1171  virtual HSourcePosition position() const OVERRIDE {
1172    return HSourcePosition(position_.position());
1173  }
1174  bool has_position() const {
1175    return !position().IsUnknown();
1176  }
1177  void set_position(HSourcePosition position) {
1178    DCHECK(!has_position());
1179    DCHECK(!position.IsUnknown());
1180    position_.set_position(position);
1181  }
1182
1183  virtual HSourcePosition operand_position(int index) const OVERRIDE {
1184    const HSourcePosition pos = position_.operand_position(index);
1185    return pos.IsUnknown() ? position() : pos;
1186  }
1187  void set_operand_position(Zone* zone, int index, HSourcePosition pos) {
1188    DCHECK(0 <= index && index < OperandCount());
1189    position_.ensure_storage_for_operand_positions(zone, OperandCount());
1190    position_.set_operand_position(index, pos);
1191  }
1192
1193  bool Dominates(HInstruction* other);
1194  bool CanTruncateToSmi() const { return CheckFlag(kTruncatingToSmi); }
1195  bool CanTruncateToInt32() const { return CheckFlag(kTruncatingToInt32); }
1196
1197  virtual LInstruction* CompileToLithium(LChunkBuilder* builder) = 0;
1198
1199#ifdef DEBUG
1200  virtual void Verify() OVERRIDE;
1201#endif
1202
1203  bool CanDeoptimize();
1204
1205  virtual bool HasStackCheck() { return false; }
1206
1207  DECLARE_ABSTRACT_INSTRUCTION(Instruction)
1208
1209 protected:
1210  explicit HInstruction(HType type = HType::Tagged())
1211      : HValue(type),
1212        next_(NULL),
1213        previous_(NULL),
1214        position_(RelocInfo::kNoPosition) {
1215    SetDependsOnFlag(kOsrEntries);
1216  }
1217
1218  virtual void DeleteFromGraph() OVERRIDE { Unlink(); }
1219
1220 private:
1221  void InitializeAsFirst(HBasicBlock* block) {
1222    DCHECK(!IsLinked());
1223    SetBlock(block);
1224  }
1225
1226  HInstruction* next_;
1227  HInstruction* previous_;
1228  HPositionInfo position_;
1229
1230  friend class HBasicBlock;
1231};
1232
1233
1234template<int V>
1235class HTemplateInstruction : public HInstruction {
1236 public:
1237  virtual int OperandCount() const FINAL OVERRIDE { return V; }
1238  virtual HValue* OperandAt(int i) const FINAL OVERRIDE {
1239    return inputs_[i];
1240  }
1241
1242 protected:
1243  explicit HTemplateInstruction(HType type = HType::Tagged())
1244      : HInstruction(type) {}
1245
1246  virtual void InternalSetOperandAt(int i, HValue* value) FINAL OVERRIDE {
1247    inputs_[i] = value;
1248  }
1249
1250 private:
1251  EmbeddedContainer<HValue*, V> inputs_;
1252};
1253
1254
1255class HControlInstruction : public HInstruction {
1256 public:
1257  virtual HBasicBlock* SuccessorAt(int i) const = 0;
1258  virtual int SuccessorCount() const = 0;
1259  virtual void SetSuccessorAt(int i, HBasicBlock* block) = 0;
1260
1261  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
1262
1263  virtual bool KnownSuccessorBlock(HBasicBlock** block) {
1264    *block = NULL;
1265    return false;
1266  }
1267
1268  HBasicBlock* FirstSuccessor() {
1269    return SuccessorCount() > 0 ? SuccessorAt(0) : NULL;
1270  }
1271  HBasicBlock* SecondSuccessor() {
1272    return SuccessorCount() > 1 ? SuccessorAt(1) : NULL;
1273  }
1274
1275  void Not() {
1276    HBasicBlock* swap = SuccessorAt(0);
1277    SetSuccessorAt(0, SuccessorAt(1));
1278    SetSuccessorAt(1, swap);
1279  }
1280
1281  DECLARE_ABSTRACT_INSTRUCTION(ControlInstruction)
1282};
1283
1284
1285class HSuccessorIterator FINAL BASE_EMBEDDED {
1286 public:
1287  explicit HSuccessorIterator(const HControlInstruction* instr)
1288      : instr_(instr), current_(0) {}
1289
1290  bool Done() { return current_ >= instr_->SuccessorCount(); }
1291  HBasicBlock* Current() { return instr_->SuccessorAt(current_); }
1292  void Advance() { current_++; }
1293
1294 private:
1295  const HControlInstruction* instr_;
1296  int current_;
1297};
1298
1299
1300template<int S, int V>
1301class HTemplateControlInstruction : public HControlInstruction {
1302 public:
1303  int SuccessorCount() const OVERRIDE { return S; }
1304  HBasicBlock* SuccessorAt(int i) const OVERRIDE { return successors_[i]; }
1305  void SetSuccessorAt(int i, HBasicBlock* block) OVERRIDE {
1306    successors_[i] = block;
1307  }
1308
1309  int OperandCount() const OVERRIDE { return V; }
1310  HValue* OperandAt(int i) const OVERRIDE { return inputs_[i]; }
1311
1312
1313 protected:
1314  void InternalSetOperandAt(int i, HValue* value) OVERRIDE {
1315    inputs_[i] = value;
1316  }
1317
1318 private:
1319  EmbeddedContainer<HBasicBlock*, S> successors_;
1320  EmbeddedContainer<HValue*, V> inputs_;
1321};
1322
1323
1324class HBlockEntry FINAL : public HTemplateInstruction<0> {
1325 public:
1326  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
1327    return Representation::None();
1328  }
1329
1330  DECLARE_CONCRETE_INSTRUCTION(BlockEntry)
1331};
1332
1333
1334class HDummyUse FINAL : public HTemplateInstruction<1> {
1335 public:
1336  explicit HDummyUse(HValue* value)
1337      : HTemplateInstruction<1>(HType::Smi()) {
1338    SetOperandAt(0, value);
1339    // Pretend to be a Smi so that the HChange instructions inserted
1340    // before any use generate as little code as possible.
1341    set_representation(Representation::Tagged());
1342  }
1343
1344  HValue* value() const { return OperandAt(0); }
1345
1346  virtual bool HasEscapingOperandAt(int index) OVERRIDE { return false; }
1347  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
1348    return Representation::None();
1349  }
1350
1351  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
1352
1353  DECLARE_CONCRETE_INSTRUCTION(DummyUse);
1354};
1355
1356
1357// Inserts an int3/stop break instruction for debugging purposes.
1358class HDebugBreak FINAL : public HTemplateInstruction<0> {
1359 public:
1360  DECLARE_INSTRUCTION_FACTORY_P0(HDebugBreak);
1361
1362  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
1363    return Representation::None();
1364  }
1365
1366  DECLARE_CONCRETE_INSTRUCTION(DebugBreak)
1367};
1368
1369
1370class HGoto FINAL : public HTemplateControlInstruction<1, 0> {
1371 public:
1372  explicit HGoto(HBasicBlock* target) {
1373    SetSuccessorAt(0, target);
1374  }
1375
1376  virtual bool KnownSuccessorBlock(HBasicBlock** block) OVERRIDE {
1377    *block = FirstSuccessor();
1378    return true;
1379  }
1380
1381  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
1382    return Representation::None();
1383  }
1384
1385  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
1386
1387  DECLARE_CONCRETE_INSTRUCTION(Goto)
1388};
1389
1390
1391class HDeoptimize FINAL : public HTemplateControlInstruction<1, 0> {
1392 public:
1393  static HDeoptimize* New(Zone* zone,
1394                          HValue* context,
1395                          const char* reason,
1396                          Deoptimizer::BailoutType type,
1397                          HBasicBlock* unreachable_continuation) {
1398    return new(zone) HDeoptimize(reason, type, unreachable_continuation);
1399  }
1400
1401  virtual bool KnownSuccessorBlock(HBasicBlock** block) OVERRIDE {
1402    *block = NULL;
1403    return true;
1404  }
1405
1406  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
1407    return Representation::None();
1408  }
1409
1410  const char* reason() const { return reason_; }
1411  Deoptimizer::BailoutType type() { return type_; }
1412
1413  DECLARE_CONCRETE_INSTRUCTION(Deoptimize)
1414
1415 private:
1416  explicit HDeoptimize(const char* reason,
1417                       Deoptimizer::BailoutType type,
1418                       HBasicBlock* unreachable_continuation)
1419      : reason_(reason), type_(type) {
1420    SetSuccessorAt(0, unreachable_continuation);
1421  }
1422
1423  const char* reason_;
1424  Deoptimizer::BailoutType type_;
1425};
1426
1427
1428class HUnaryControlInstruction : public HTemplateControlInstruction<2, 1> {
1429 public:
1430  HUnaryControlInstruction(HValue* value,
1431                           HBasicBlock* true_target,
1432                           HBasicBlock* false_target) {
1433    SetOperandAt(0, value);
1434    SetSuccessorAt(0, true_target);
1435    SetSuccessorAt(1, false_target);
1436  }
1437
1438  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
1439
1440  HValue* value() const { return OperandAt(0); }
1441};
1442
1443
1444class HBranch FINAL : public HUnaryControlInstruction {
1445 public:
1446  DECLARE_INSTRUCTION_FACTORY_P1(HBranch, HValue*);
1447  DECLARE_INSTRUCTION_FACTORY_P2(HBranch, HValue*,
1448                                 ToBooleanStub::Types);
1449  DECLARE_INSTRUCTION_FACTORY_P4(HBranch, HValue*,
1450                                 ToBooleanStub::Types,
1451                                 HBasicBlock*, HBasicBlock*);
1452
1453  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
1454    return Representation::None();
1455  }
1456  virtual Representation observed_input_representation(int index) OVERRIDE;
1457
1458  virtual bool KnownSuccessorBlock(HBasicBlock** block) OVERRIDE;
1459
1460  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
1461
1462  ToBooleanStub::Types expected_input_types() const {
1463    return expected_input_types_;
1464  }
1465
1466  DECLARE_CONCRETE_INSTRUCTION(Branch)
1467
1468 private:
1469  HBranch(HValue* value,
1470          ToBooleanStub::Types expected_input_types = ToBooleanStub::Types(),
1471          HBasicBlock* true_target = NULL,
1472          HBasicBlock* false_target = NULL)
1473      : HUnaryControlInstruction(value, true_target, false_target),
1474        expected_input_types_(expected_input_types) {
1475    SetFlag(kAllowUndefinedAsNaN);
1476  }
1477
1478  ToBooleanStub::Types expected_input_types_;
1479};
1480
1481
1482class HCompareMap FINAL : public HUnaryControlInstruction {
1483 public:
1484  DECLARE_INSTRUCTION_FACTORY_P2(HCompareMap, HValue*, Handle<Map>);
1485  DECLARE_INSTRUCTION_FACTORY_P4(HCompareMap, HValue*, Handle<Map>,
1486                                 HBasicBlock*, HBasicBlock*);
1487
1488  virtual bool KnownSuccessorBlock(HBasicBlock** block) OVERRIDE {
1489    if (known_successor_index() != kNoKnownSuccessorIndex) {
1490      *block = SuccessorAt(known_successor_index());
1491      return true;
1492    }
1493    *block = NULL;
1494    return false;
1495  }
1496
1497  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
1498
1499  static const int kNoKnownSuccessorIndex = -1;
1500  int known_successor_index() const { return known_successor_index_; }
1501  void set_known_successor_index(int known_successor_index) {
1502    known_successor_index_ = known_successor_index;
1503  }
1504
1505  Unique<Map> map() const { return map_; }
1506  bool map_is_stable() const { return map_is_stable_; }
1507
1508  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
1509    return Representation::Tagged();
1510  }
1511
1512  DECLARE_CONCRETE_INSTRUCTION(CompareMap)
1513
1514 protected:
1515  virtual int RedefinedOperandIndex() { return 0; }
1516
1517 private:
1518  HCompareMap(HValue* value,
1519              Handle<Map> map,
1520              HBasicBlock* true_target = NULL,
1521              HBasicBlock* false_target = NULL)
1522      : HUnaryControlInstruction(value, true_target, false_target),
1523        known_successor_index_(kNoKnownSuccessorIndex),
1524        map_is_stable_(map->is_stable()),
1525        map_(Unique<Map>::CreateImmovable(map)) {
1526    set_representation(Representation::Tagged());
1527  }
1528
1529  int known_successor_index_ : 31;
1530  bool map_is_stable_ : 1;
1531  Unique<Map> map_;
1532};
1533
1534
1535class HContext FINAL : public HTemplateInstruction<0> {
1536 public:
1537  static HContext* New(Zone* zone) {
1538    return new(zone) HContext();
1539  }
1540
1541  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
1542    return Representation::None();
1543  }
1544
1545  DECLARE_CONCRETE_INSTRUCTION(Context)
1546
1547 protected:
1548  virtual bool DataEquals(HValue* other) OVERRIDE { return true; }
1549
1550 private:
1551  HContext() {
1552    set_representation(Representation::Tagged());
1553    SetFlag(kUseGVN);
1554  }
1555
1556  virtual bool IsDeletable() const OVERRIDE { return true; }
1557};
1558
1559
1560class HReturn FINAL : public HTemplateControlInstruction<0, 3> {
1561 public:
1562  DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P2(HReturn, HValue*, HValue*);
1563  DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P1(HReturn, HValue*);
1564
1565  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
1566    // TODO(titzer): require an Int32 input for faster returns.
1567    if (index == 2) return Representation::Smi();
1568    return Representation::Tagged();
1569  }
1570
1571  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
1572
1573  HValue* value() const { return OperandAt(0); }
1574  HValue* context() const { return OperandAt(1); }
1575  HValue* parameter_count() const { return OperandAt(2); }
1576
1577  DECLARE_CONCRETE_INSTRUCTION(Return)
1578
1579 private:
1580  HReturn(HValue* context, HValue* value, HValue* parameter_count = 0) {
1581    SetOperandAt(0, value);
1582    SetOperandAt(1, context);
1583    SetOperandAt(2, parameter_count);
1584  }
1585};
1586
1587
1588class HAbnormalExit FINAL : public HTemplateControlInstruction<0, 0> {
1589 public:
1590  DECLARE_INSTRUCTION_FACTORY_P0(HAbnormalExit);
1591
1592  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
1593    return Representation::None();
1594  }
1595
1596  DECLARE_CONCRETE_INSTRUCTION(AbnormalExit)
1597 private:
1598  HAbnormalExit() {}
1599};
1600
1601
1602class HUnaryOperation : public HTemplateInstruction<1> {
1603 public:
1604  explicit HUnaryOperation(HValue* value, HType type = HType::Tagged())
1605      : HTemplateInstruction<1>(type) {
1606    SetOperandAt(0, value);
1607  }
1608
1609  static HUnaryOperation* cast(HValue* value) {
1610    return reinterpret_cast<HUnaryOperation*>(value);
1611  }
1612
1613  HValue* value() const { return OperandAt(0); }
1614  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
1615};
1616
1617
1618class HUseConst FINAL : public HUnaryOperation {
1619 public:
1620  DECLARE_INSTRUCTION_FACTORY_P1(HUseConst, HValue*);
1621
1622  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
1623    return Representation::None();
1624  }
1625
1626  DECLARE_CONCRETE_INSTRUCTION(UseConst)
1627
1628 private:
1629    explicit HUseConst(HValue* old_value) : HUnaryOperation(old_value) { }
1630};
1631
1632
1633class HForceRepresentation FINAL : public HTemplateInstruction<1> {
1634 public:
1635  static HInstruction* New(Zone* zone, HValue* context, HValue* value,
1636                           Representation required_representation);
1637
1638  HValue* value() const { return OperandAt(0); }
1639
1640  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
1641    return representation();  // Same as the output representation.
1642  }
1643
1644  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
1645
1646  DECLARE_CONCRETE_INSTRUCTION(ForceRepresentation)
1647
1648 private:
1649  HForceRepresentation(HValue* value, Representation required_representation) {
1650    SetOperandAt(0, value);
1651    set_representation(required_representation);
1652  }
1653};
1654
1655
1656class HChange FINAL : public HUnaryOperation {
1657 public:
1658  HChange(HValue* value,
1659          Representation to,
1660          bool is_truncating_to_smi,
1661          bool is_truncating_to_int32)
1662      : HUnaryOperation(value) {
1663    DCHECK(!value->representation().IsNone());
1664    DCHECK(!to.IsNone());
1665    DCHECK(!value->representation().Equals(to));
1666    set_representation(to);
1667    SetFlag(kUseGVN);
1668    SetFlag(kCanOverflow);
1669    if (is_truncating_to_smi && to.IsSmi()) {
1670      SetFlag(kTruncatingToSmi);
1671      SetFlag(kTruncatingToInt32);
1672    }
1673    if (is_truncating_to_int32) SetFlag(kTruncatingToInt32);
1674    if (value->representation().IsSmi() || value->type().IsSmi()) {
1675      set_type(HType::Smi());
1676    } else {
1677      set_type(HType::TaggedNumber());
1678      if (to.IsTagged()) SetChangesFlag(kNewSpacePromotion);
1679    }
1680  }
1681
1682  bool can_convert_undefined_to_nan() {
1683    return CheckUsesForFlag(kAllowUndefinedAsNaN);
1684  }
1685
1686  virtual HType CalculateInferredType() OVERRIDE;
1687  virtual HValue* Canonicalize() OVERRIDE;
1688
1689  Representation from() const { return value()->representation(); }
1690  Representation to() const { return representation(); }
1691  bool deoptimize_on_minus_zero() const {
1692    return CheckFlag(kBailoutOnMinusZero);
1693  }
1694  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
1695    return from();
1696  }
1697
1698  virtual Range* InferRange(Zone* zone) OVERRIDE;
1699
1700  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
1701
1702  DECLARE_CONCRETE_INSTRUCTION(Change)
1703
1704 protected:
1705  virtual bool DataEquals(HValue* other) OVERRIDE { return true; }
1706
1707 private:
1708  virtual bool IsDeletable() const OVERRIDE {
1709    return !from().IsTagged() || value()->type().IsSmi();
1710  }
1711};
1712
1713
1714class HClampToUint8 FINAL : public HUnaryOperation {
1715 public:
1716  DECLARE_INSTRUCTION_FACTORY_P1(HClampToUint8, HValue*);
1717
1718  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
1719    return Representation::None();
1720  }
1721
1722  DECLARE_CONCRETE_INSTRUCTION(ClampToUint8)
1723
1724 protected:
1725  virtual bool DataEquals(HValue* other) OVERRIDE { return true; }
1726
1727 private:
1728  explicit HClampToUint8(HValue* value)
1729      : HUnaryOperation(value) {
1730    set_representation(Representation::Integer32());
1731    SetFlag(kAllowUndefinedAsNaN);
1732    SetFlag(kUseGVN);
1733  }
1734
1735  virtual bool IsDeletable() const OVERRIDE { return true; }
1736};
1737
1738
1739class HDoubleBits FINAL : public HUnaryOperation {
1740 public:
1741  enum Bits { HIGH, LOW };
1742  DECLARE_INSTRUCTION_FACTORY_P2(HDoubleBits, HValue*, Bits);
1743
1744  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
1745    return Representation::Double();
1746  }
1747
1748  DECLARE_CONCRETE_INSTRUCTION(DoubleBits)
1749
1750  Bits bits() { return bits_; }
1751
1752 protected:
1753  virtual bool DataEquals(HValue* other) OVERRIDE {
1754    return other->IsDoubleBits() && HDoubleBits::cast(other)->bits() == bits();
1755  }
1756
1757 private:
1758  HDoubleBits(HValue* value, Bits bits)
1759      : HUnaryOperation(value), bits_(bits) {
1760    set_representation(Representation::Integer32());
1761    SetFlag(kUseGVN);
1762  }
1763
1764  virtual bool IsDeletable() const OVERRIDE { return true; }
1765
1766  Bits bits_;
1767};
1768
1769
1770class HConstructDouble FINAL : public HTemplateInstruction<2> {
1771 public:
1772  DECLARE_INSTRUCTION_FACTORY_P2(HConstructDouble, HValue*, HValue*);
1773
1774  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
1775    return Representation::Integer32();
1776  }
1777
1778  DECLARE_CONCRETE_INSTRUCTION(ConstructDouble)
1779
1780  HValue* hi() { return OperandAt(0); }
1781  HValue* lo() { return OperandAt(1); }
1782
1783 protected:
1784  virtual bool DataEquals(HValue* other) OVERRIDE { return true; }
1785
1786 private:
1787  explicit HConstructDouble(HValue* hi, HValue* lo) {
1788    set_representation(Representation::Double());
1789    SetFlag(kUseGVN);
1790    SetOperandAt(0, hi);
1791    SetOperandAt(1, lo);
1792  }
1793
1794  virtual bool IsDeletable() const OVERRIDE { return true; }
1795};
1796
1797
1798enum RemovableSimulate {
1799  REMOVABLE_SIMULATE,
1800  FIXED_SIMULATE
1801};
1802
1803
1804class HSimulate FINAL : public HInstruction {
1805 public:
1806  HSimulate(BailoutId ast_id,
1807            int pop_count,
1808            Zone* zone,
1809            RemovableSimulate removable)
1810      : ast_id_(ast_id),
1811        pop_count_(pop_count),
1812        values_(2, zone),
1813        assigned_indexes_(2, zone),
1814        zone_(zone),
1815        removable_(removable),
1816        done_with_replay_(false) {}
1817  ~HSimulate() {}
1818
1819  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
1820
1821  bool HasAstId() const { return !ast_id_.IsNone(); }
1822  BailoutId ast_id() const { return ast_id_; }
1823  void set_ast_id(BailoutId id) {
1824    DCHECK(!HasAstId());
1825    ast_id_ = id;
1826  }
1827
1828  int pop_count() const { return pop_count_; }
1829  const ZoneList<HValue*>* values() const { return &values_; }
1830  int GetAssignedIndexAt(int index) const {
1831    DCHECK(HasAssignedIndexAt(index));
1832    return assigned_indexes_[index];
1833  }
1834  bool HasAssignedIndexAt(int index) const {
1835    return assigned_indexes_[index] != kNoIndex;
1836  }
1837  void AddAssignedValue(int index, HValue* value) {
1838    AddValue(index, value);
1839  }
1840  void AddPushedValue(HValue* value) {
1841    AddValue(kNoIndex, value);
1842  }
1843  int ToOperandIndex(int environment_index) {
1844    for (int i = 0; i < assigned_indexes_.length(); ++i) {
1845      if (assigned_indexes_[i] == environment_index) return i;
1846    }
1847    return -1;
1848  }
1849  virtual int OperandCount() const OVERRIDE { return values_.length(); }
1850  virtual HValue* OperandAt(int index) const OVERRIDE {
1851    return values_[index];
1852  }
1853
1854  virtual bool HasEscapingOperandAt(int index) OVERRIDE { return false; }
1855  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
1856    return Representation::None();
1857  }
1858
1859  void MergeWith(ZoneList<HSimulate*>* list);
1860  bool is_candidate_for_removal() { return removable_ == REMOVABLE_SIMULATE; }
1861
1862  // Replay effects of this instruction on the given environment.
1863  void ReplayEnvironment(HEnvironment* env);
1864
1865  DECLARE_CONCRETE_INSTRUCTION(Simulate)
1866
1867#ifdef DEBUG
1868  virtual void Verify() OVERRIDE;
1869  void set_closure(Handle<JSFunction> closure) { closure_ = closure; }
1870  Handle<JSFunction> closure() const { return closure_; }
1871#endif
1872
1873 protected:
1874  virtual void InternalSetOperandAt(int index, HValue* value) OVERRIDE {
1875    values_[index] = value;
1876  }
1877
1878 private:
1879  static const int kNoIndex = -1;
1880  void AddValue(int index, HValue* value) {
1881    assigned_indexes_.Add(index, zone_);
1882    // Resize the list of pushed values.
1883    values_.Add(NULL, zone_);
1884    // Set the operand through the base method in HValue to make sure that the
1885    // use lists are correctly updated.
1886    SetOperandAt(values_.length() - 1, value);
1887  }
1888  bool HasValueForIndex(int index) {
1889    for (int i = 0; i < assigned_indexes_.length(); ++i) {
1890      if (assigned_indexes_[i] == index) return true;
1891    }
1892    return false;
1893  }
1894  BailoutId ast_id_;
1895  int pop_count_;
1896  ZoneList<HValue*> values_;
1897  ZoneList<int> assigned_indexes_;
1898  Zone* zone_;
1899  RemovableSimulate removable_ : 2;
1900  bool done_with_replay_ : 1;
1901
1902#ifdef DEBUG
1903  Handle<JSFunction> closure_;
1904#endif
1905};
1906
1907
1908class HEnvironmentMarker FINAL : public HTemplateInstruction<1> {
1909 public:
1910  enum Kind { BIND, LOOKUP };
1911
1912  DECLARE_INSTRUCTION_FACTORY_P2(HEnvironmentMarker, Kind, int);
1913
1914  Kind kind() const { return kind_; }
1915  int index() const { return index_; }
1916  HSimulate* next_simulate() { return next_simulate_; }
1917  void set_next_simulate(HSimulate* simulate) {
1918    next_simulate_ = simulate;
1919  }
1920
1921  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
1922    return Representation::None();
1923  }
1924
1925  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
1926
1927#ifdef DEBUG
1928  void set_closure(Handle<JSFunction> closure) {
1929    DCHECK(closure_.is_null());
1930    DCHECK(!closure.is_null());
1931    closure_ = closure;
1932  }
1933  Handle<JSFunction> closure() const { return closure_; }
1934#endif
1935
1936  DECLARE_CONCRETE_INSTRUCTION(EnvironmentMarker);
1937
1938 private:
1939  HEnvironmentMarker(Kind kind, int index)
1940      : kind_(kind), index_(index), next_simulate_(NULL) { }
1941
1942  Kind kind_;
1943  int index_;
1944  HSimulate* next_simulate_;
1945
1946#ifdef DEBUG
1947  Handle<JSFunction> closure_;
1948#endif
1949};
1950
1951
1952class HStackCheck FINAL : public HTemplateInstruction<1> {
1953 public:
1954  enum Type {
1955    kFunctionEntry,
1956    kBackwardsBranch
1957  };
1958
1959  DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P1(HStackCheck, Type);
1960
1961  HValue* context() { return OperandAt(0); }
1962
1963  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
1964    return Representation::Tagged();
1965  }
1966
1967  void Eliminate() {
1968    // The stack check eliminator might try to eliminate the same stack
1969    // check instruction multiple times.
1970    if (IsLinked()) {
1971      DeleteAndReplaceWith(NULL);
1972    }
1973  }
1974
1975  bool is_function_entry() { return type_ == kFunctionEntry; }
1976  bool is_backwards_branch() { return type_ == kBackwardsBranch; }
1977
1978  DECLARE_CONCRETE_INSTRUCTION(StackCheck)
1979
1980 private:
1981  HStackCheck(HValue* context, Type type) : type_(type) {
1982    SetOperandAt(0, context);
1983    SetChangesFlag(kNewSpacePromotion);
1984  }
1985
1986  Type type_;
1987};
1988
1989
1990enum InliningKind {
1991  NORMAL_RETURN,          // Drop the function from the environment on return.
1992  CONSTRUCT_CALL_RETURN,  // Either use allocated receiver or return value.
1993  GETTER_CALL_RETURN,     // Returning from a getter, need to restore context.
1994  SETTER_CALL_RETURN      // Use the RHS of the assignment as the return value.
1995};
1996
1997
1998class HArgumentsObject;
1999class HConstant;
2000
2001
2002class HEnterInlined FINAL : public HTemplateInstruction<0> {
2003 public:
2004  static HEnterInlined* New(Zone* zone, HValue* context, BailoutId return_id,
2005                            Handle<JSFunction> closure,
2006                            HConstant* closure_context, int arguments_count,
2007                            FunctionLiteral* function,
2008                            InliningKind inlining_kind, Variable* arguments_var,
2009                            HArgumentsObject* arguments_object) {
2010    return new (zone) HEnterInlined(return_id, closure, closure_context,
2011                                    arguments_count, function, inlining_kind,
2012                                    arguments_var, arguments_object, zone);
2013  }
2014
2015  void RegisterReturnTarget(HBasicBlock* return_target, Zone* zone);
2016  ZoneList<HBasicBlock*>* return_targets() { return &return_targets_; }
2017
2018  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
2019
2020  Handle<JSFunction> closure() const { return closure_; }
2021  HConstant* closure_context() const { return closure_context_; }
2022  int arguments_count() const { return arguments_count_; }
2023  bool arguments_pushed() const { return arguments_pushed_; }
2024  void set_arguments_pushed() { arguments_pushed_ = true; }
2025  FunctionLiteral* function() const { return function_; }
2026  InliningKind inlining_kind() const { return inlining_kind_; }
2027  BailoutId ReturnId() const { return return_id_; }
2028
2029  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
2030    return Representation::None();
2031  }
2032
2033  Variable* arguments_var() { return arguments_var_; }
2034  HArgumentsObject* arguments_object() { return arguments_object_; }
2035
2036  DECLARE_CONCRETE_INSTRUCTION(EnterInlined)
2037
2038 private:
2039  HEnterInlined(BailoutId return_id, Handle<JSFunction> closure,
2040                HConstant* closure_context, int arguments_count,
2041                FunctionLiteral* function, InliningKind inlining_kind,
2042                Variable* arguments_var, HArgumentsObject* arguments_object,
2043                Zone* zone)
2044      : return_id_(return_id),
2045        closure_(closure),
2046        closure_context_(closure_context),
2047        arguments_count_(arguments_count),
2048        arguments_pushed_(false),
2049        function_(function),
2050        inlining_kind_(inlining_kind),
2051        arguments_var_(arguments_var),
2052        arguments_object_(arguments_object),
2053        return_targets_(2, zone) {}
2054
2055  BailoutId return_id_;
2056  Handle<JSFunction> closure_;
2057  HConstant* closure_context_;
2058  int arguments_count_;
2059  bool arguments_pushed_;
2060  FunctionLiteral* function_;
2061  InliningKind inlining_kind_;
2062  Variable* arguments_var_;
2063  HArgumentsObject* arguments_object_;
2064  ZoneList<HBasicBlock*> return_targets_;
2065};
2066
2067
2068class HLeaveInlined FINAL : public HTemplateInstruction<0> {
2069 public:
2070  HLeaveInlined(HEnterInlined* entry,
2071                int drop_count)
2072      : entry_(entry),
2073        drop_count_(drop_count) { }
2074
2075  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
2076    return Representation::None();
2077  }
2078
2079  virtual int argument_delta() const OVERRIDE {
2080    return entry_->arguments_pushed() ? -drop_count_ : 0;
2081  }
2082
2083  DECLARE_CONCRETE_INSTRUCTION(LeaveInlined)
2084
2085 private:
2086  HEnterInlined* entry_;
2087  int drop_count_;
2088};
2089
2090
2091class HPushArguments FINAL : public HInstruction {
2092 public:
2093  static HPushArguments* New(Zone* zone, HValue* context) {
2094    return new(zone) HPushArguments(zone);
2095  }
2096  static HPushArguments* New(Zone* zone, HValue* context, HValue* arg1) {
2097    HPushArguments* instr = new(zone) HPushArguments(zone);
2098    instr->AddInput(arg1);
2099    return instr;
2100  }
2101  static HPushArguments* New(Zone* zone, HValue* context, HValue* arg1,
2102                             HValue* arg2) {
2103    HPushArguments* instr = new(zone) HPushArguments(zone);
2104    instr->AddInput(arg1);
2105    instr->AddInput(arg2);
2106    return instr;
2107  }
2108  static HPushArguments* New(Zone* zone, HValue* context, HValue* arg1,
2109                             HValue* arg2, HValue* arg3) {
2110    HPushArguments* instr = new(zone) HPushArguments(zone);
2111    instr->AddInput(arg1);
2112    instr->AddInput(arg2);
2113    instr->AddInput(arg3);
2114    return instr;
2115  }
2116  static HPushArguments* New(Zone* zone, HValue* context, HValue* arg1,
2117                             HValue* arg2, HValue* arg3, HValue* arg4) {
2118    HPushArguments* instr = new(zone) HPushArguments(zone);
2119    instr->AddInput(arg1);
2120    instr->AddInput(arg2);
2121    instr->AddInput(arg3);
2122    instr->AddInput(arg4);
2123    return instr;
2124  }
2125
2126  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
2127    return Representation::Tagged();
2128  }
2129
2130  virtual int argument_delta() const OVERRIDE { return inputs_.length(); }
2131  HValue* argument(int i) { return OperandAt(i); }
2132
2133  virtual int OperandCount() const FINAL OVERRIDE {
2134    return inputs_.length();
2135  }
2136  virtual HValue* OperandAt(int i) const FINAL OVERRIDE {
2137    return inputs_[i];
2138  }
2139
2140  void AddInput(HValue* value);
2141
2142  DECLARE_CONCRETE_INSTRUCTION(PushArguments)
2143
2144 protected:
2145  virtual void InternalSetOperandAt(int i, HValue* value) FINAL OVERRIDE {
2146    inputs_[i] = value;
2147  }
2148
2149 private:
2150  explicit HPushArguments(Zone* zone)
2151      : HInstruction(HType::Tagged()), inputs_(4, zone) {
2152    set_representation(Representation::Tagged());
2153  }
2154
2155  ZoneList<HValue*> inputs_;
2156};
2157
2158
2159class HThisFunction FINAL : public HTemplateInstruction<0> {
2160 public:
2161  DECLARE_INSTRUCTION_FACTORY_P0(HThisFunction);
2162
2163  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
2164    return Representation::None();
2165  }
2166
2167  DECLARE_CONCRETE_INSTRUCTION(ThisFunction)
2168
2169 protected:
2170  virtual bool DataEquals(HValue* other) OVERRIDE { return true; }
2171
2172 private:
2173  HThisFunction() {
2174    set_representation(Representation::Tagged());
2175    SetFlag(kUseGVN);
2176  }
2177
2178  virtual bool IsDeletable() const OVERRIDE { return true; }
2179};
2180
2181
2182class HDeclareGlobals FINAL : public HUnaryOperation {
2183 public:
2184  DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P2(HDeclareGlobals,
2185                                              Handle<FixedArray>,
2186                                              int);
2187
2188  HValue* context() { return OperandAt(0); }
2189  Handle<FixedArray> pairs() const { return pairs_; }
2190  int flags() const { return flags_; }
2191
2192  DECLARE_CONCRETE_INSTRUCTION(DeclareGlobals)
2193
2194  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
2195    return Representation::Tagged();
2196  }
2197
2198 private:
2199  HDeclareGlobals(HValue* context,
2200                  Handle<FixedArray> pairs,
2201                  int flags)
2202      : HUnaryOperation(context),
2203        pairs_(pairs),
2204        flags_(flags) {
2205    set_representation(Representation::Tagged());
2206    SetAllSideEffects();
2207  }
2208
2209  Handle<FixedArray> pairs_;
2210  int flags_;
2211};
2212
2213
2214template <int V>
2215class HCall : public HTemplateInstruction<V> {
2216 public:
2217  // The argument count includes the receiver.
2218  explicit HCall<V>(int argument_count) : argument_count_(argument_count) {
2219    this->set_representation(Representation::Tagged());
2220    this->SetAllSideEffects();
2221  }
2222
2223  virtual HType CalculateInferredType() FINAL OVERRIDE {
2224    return HType::Tagged();
2225  }
2226
2227  virtual int argument_count() const {
2228    return argument_count_;
2229  }
2230
2231  virtual int argument_delta() const OVERRIDE {
2232    return -argument_count();
2233  }
2234
2235 private:
2236  int argument_count_;
2237};
2238
2239
2240class HUnaryCall : public HCall<1> {
2241 public:
2242  HUnaryCall(HValue* value, int argument_count)
2243      : HCall<1>(argument_count) {
2244    SetOperandAt(0, value);
2245  }
2246
2247  virtual Representation RequiredInputRepresentation(
2248      int index) FINAL OVERRIDE {
2249    return Representation::Tagged();
2250  }
2251
2252  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
2253
2254  HValue* value() const { return OperandAt(0); }
2255};
2256
2257
2258class HBinaryCall : public HCall<2> {
2259 public:
2260  HBinaryCall(HValue* first, HValue* second, int argument_count)
2261      : HCall<2>(argument_count) {
2262    SetOperandAt(0, first);
2263    SetOperandAt(1, second);
2264  }
2265
2266  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
2267
2268  virtual Representation RequiredInputRepresentation(
2269      int index) FINAL OVERRIDE {
2270    return Representation::Tagged();
2271  }
2272
2273  HValue* first() const { return OperandAt(0); }
2274  HValue* second() const { return OperandAt(1); }
2275};
2276
2277
2278class HCallJSFunction FINAL : public HCall<1> {
2279 public:
2280  static HCallJSFunction* New(Zone* zone,
2281                              HValue* context,
2282                              HValue* function,
2283                              int argument_count,
2284                              bool pass_argument_count);
2285
2286  HValue* function() const { return OperandAt(0); }
2287
2288  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
2289
2290  virtual Representation RequiredInputRepresentation(
2291      int index) FINAL OVERRIDE {
2292    DCHECK(index == 0);
2293    return Representation::Tagged();
2294  }
2295
2296  bool pass_argument_count() const { return pass_argument_count_; }
2297
2298  virtual bool HasStackCheck() FINAL OVERRIDE {
2299    return has_stack_check_;
2300  }
2301
2302  DECLARE_CONCRETE_INSTRUCTION(CallJSFunction)
2303
2304 private:
2305  // The argument count includes the receiver.
2306  HCallJSFunction(HValue* function,
2307                  int argument_count,
2308                  bool pass_argument_count,
2309                  bool has_stack_check)
2310      : HCall<1>(argument_count),
2311        pass_argument_count_(pass_argument_count),
2312        has_stack_check_(has_stack_check) {
2313      SetOperandAt(0, function);
2314  }
2315
2316  bool pass_argument_count_;
2317  bool has_stack_check_;
2318};
2319
2320
2321class HCallWithDescriptor FINAL : public HInstruction {
2322 public:
2323  static HCallWithDescriptor* New(Zone* zone, HValue* context, HValue* target,
2324                                  int argument_count,
2325                                  CallInterfaceDescriptor descriptor,
2326                                  const Vector<HValue*>& operands) {
2327    DCHECK(operands.length() == descriptor.GetEnvironmentLength());
2328    HCallWithDescriptor* res = new (zone)
2329        HCallWithDescriptor(target, argument_count, descriptor, operands, zone);
2330    return res;
2331  }
2332
2333  virtual int OperandCount() const FINAL OVERRIDE {
2334    return values_.length();
2335  }
2336  virtual HValue* OperandAt(int index) const FINAL OVERRIDE {
2337    return values_[index];
2338  }
2339
2340  virtual Representation RequiredInputRepresentation(
2341      int index) FINAL OVERRIDE {
2342    if (index == 0) {
2343      return Representation::Tagged();
2344    } else {
2345      int par_index = index - 1;
2346      DCHECK(par_index < descriptor_.GetEnvironmentLength());
2347      return descriptor_.GetParameterRepresentation(par_index);
2348    }
2349  }
2350
2351  DECLARE_CONCRETE_INSTRUCTION(CallWithDescriptor)
2352
2353  virtual HType CalculateInferredType() FINAL OVERRIDE {
2354    return HType::Tagged();
2355  }
2356
2357  virtual int argument_count() const {
2358    return argument_count_;
2359  }
2360
2361  virtual int argument_delta() const OVERRIDE {
2362    return -argument_count_;
2363  }
2364
2365  CallInterfaceDescriptor descriptor() const { return descriptor_; }
2366
2367  HValue* target() {
2368    return OperandAt(0);
2369  }
2370
2371  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
2372
2373 private:
2374  // The argument count includes the receiver.
2375  HCallWithDescriptor(HValue* target, int argument_count,
2376                      CallInterfaceDescriptor descriptor,
2377                      const Vector<HValue*>& operands, Zone* zone)
2378      : descriptor_(descriptor),
2379        values_(descriptor.GetEnvironmentLength() + 1, zone) {
2380    argument_count_ = argument_count;
2381    AddOperand(target, zone);
2382    for (int i = 0; i < operands.length(); i++) {
2383      AddOperand(operands[i], zone);
2384    }
2385    this->set_representation(Representation::Tagged());
2386    this->SetAllSideEffects();
2387  }
2388
2389  void AddOperand(HValue* v, Zone* zone) {
2390    values_.Add(NULL, zone);
2391    SetOperandAt(values_.length() - 1, v);
2392  }
2393
2394  void InternalSetOperandAt(int index,
2395                            HValue* value) FINAL OVERRIDE {
2396    values_[index] = value;
2397  }
2398
2399  CallInterfaceDescriptor descriptor_;
2400  ZoneList<HValue*> values_;
2401  int argument_count_;
2402};
2403
2404
2405class HInvokeFunction FINAL : public HBinaryCall {
2406 public:
2407  DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P2(HInvokeFunction, HValue*, int);
2408
2409  HInvokeFunction(HValue* context,
2410                  HValue* function,
2411                  Handle<JSFunction> known_function,
2412                  int argument_count)
2413      : HBinaryCall(context, function, argument_count),
2414        known_function_(known_function) {
2415    formal_parameter_count_ = known_function.is_null()
2416        ? 0 : known_function->shared()->formal_parameter_count();
2417    has_stack_check_ = !known_function.is_null() &&
2418        (known_function->code()->kind() == Code::FUNCTION ||
2419         known_function->code()->kind() == Code::OPTIMIZED_FUNCTION);
2420  }
2421
2422  static HInvokeFunction* New(Zone* zone,
2423                              HValue* context,
2424                              HValue* function,
2425                              Handle<JSFunction> known_function,
2426                              int argument_count) {
2427    return new(zone) HInvokeFunction(context, function,
2428                                     known_function, argument_count);
2429  }
2430
2431  HValue* context() { return first(); }
2432  HValue* function() { return second(); }
2433  Handle<JSFunction> known_function() { return known_function_; }
2434  int formal_parameter_count() const { return formal_parameter_count_; }
2435
2436  virtual bool HasStackCheck() FINAL OVERRIDE {
2437    return has_stack_check_;
2438  }
2439
2440  DECLARE_CONCRETE_INSTRUCTION(InvokeFunction)
2441
2442 private:
2443  HInvokeFunction(HValue* context, HValue* function, int argument_count)
2444      : HBinaryCall(context, function, argument_count),
2445        has_stack_check_(false) {
2446  }
2447
2448  Handle<JSFunction> known_function_;
2449  int formal_parameter_count_;
2450  bool has_stack_check_;
2451};
2452
2453
2454class HCallFunction FINAL : public HBinaryCall {
2455 public:
2456  DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P2(HCallFunction, HValue*, int);
2457  DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P3(
2458      HCallFunction, HValue*, int, CallFunctionFlags);
2459
2460  HValue* context() { return first(); }
2461  HValue* function() { return second(); }
2462  CallFunctionFlags function_flags() const { return function_flags_; }
2463
2464  DECLARE_CONCRETE_INSTRUCTION(CallFunction)
2465
2466  virtual int argument_delta() const OVERRIDE { return -argument_count(); }
2467
2468 private:
2469  HCallFunction(HValue* context,
2470                HValue* function,
2471                int argument_count,
2472                CallFunctionFlags flags = NO_CALL_FUNCTION_FLAGS)
2473      : HBinaryCall(context, function, argument_count), function_flags_(flags) {
2474  }
2475  CallFunctionFlags function_flags_;
2476};
2477
2478
2479class HCallNew FINAL : public HBinaryCall {
2480 public:
2481  DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P2(HCallNew, HValue*, int);
2482
2483  HValue* context() { return first(); }
2484  HValue* constructor() { return second(); }
2485
2486  DECLARE_CONCRETE_INSTRUCTION(CallNew)
2487
2488 private:
2489  HCallNew(HValue* context, HValue* constructor, int argument_count)
2490      : HBinaryCall(context, constructor, argument_count) {}
2491};
2492
2493
2494class HCallNewArray FINAL : public HBinaryCall {
2495 public:
2496  DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P3(HCallNewArray,
2497                                              HValue*,
2498                                              int,
2499                                              ElementsKind);
2500
2501  HValue* context() { return first(); }
2502  HValue* constructor() { return second(); }
2503
2504  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
2505
2506  ElementsKind elements_kind() const { return elements_kind_; }
2507
2508  DECLARE_CONCRETE_INSTRUCTION(CallNewArray)
2509
2510 private:
2511  HCallNewArray(HValue* context, HValue* constructor, int argument_count,
2512                ElementsKind elements_kind)
2513      : HBinaryCall(context, constructor, argument_count),
2514        elements_kind_(elements_kind) {}
2515
2516  ElementsKind elements_kind_;
2517};
2518
2519
2520class HCallRuntime FINAL : public HCall<1> {
2521 public:
2522  DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P3(HCallRuntime,
2523                                              Handle<String>,
2524                                              const Runtime::Function*,
2525                                              int);
2526
2527  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
2528
2529  HValue* context() { return OperandAt(0); }
2530  const Runtime::Function* function() const { return c_function_; }
2531  Handle<String> name() const { return name_; }
2532  SaveFPRegsMode save_doubles() const { return save_doubles_; }
2533  void set_save_doubles(SaveFPRegsMode save_doubles) {
2534    save_doubles_ = save_doubles;
2535  }
2536
2537  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
2538    return Representation::Tagged();
2539  }
2540
2541  DECLARE_CONCRETE_INSTRUCTION(CallRuntime)
2542
2543 private:
2544  HCallRuntime(HValue* context,
2545               Handle<String> name,
2546               const Runtime::Function* c_function,
2547               int argument_count)
2548      : HCall<1>(argument_count), c_function_(c_function), name_(name),
2549        save_doubles_(kDontSaveFPRegs) {
2550    SetOperandAt(0, context);
2551  }
2552
2553  const Runtime::Function* c_function_;
2554  Handle<String> name_;
2555  SaveFPRegsMode save_doubles_;
2556};
2557
2558
2559class HMapEnumLength FINAL : public HUnaryOperation {
2560 public:
2561  DECLARE_INSTRUCTION_FACTORY_P1(HMapEnumLength, HValue*);
2562
2563  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
2564    return Representation::Tagged();
2565  }
2566
2567  DECLARE_CONCRETE_INSTRUCTION(MapEnumLength)
2568
2569 protected:
2570  virtual bool DataEquals(HValue* other) OVERRIDE { return true; }
2571
2572 private:
2573  explicit HMapEnumLength(HValue* value)
2574      : HUnaryOperation(value, HType::Smi()) {
2575    set_representation(Representation::Smi());
2576    SetFlag(kUseGVN);
2577    SetDependsOnFlag(kMaps);
2578  }
2579
2580  virtual bool IsDeletable() const OVERRIDE { return true; }
2581};
2582
2583
2584class HUnaryMathOperation FINAL : public HTemplateInstruction<2> {
2585 public:
2586  static HInstruction* New(Zone* zone,
2587                           HValue* context,
2588                           HValue* value,
2589                           BuiltinFunctionId op);
2590
2591  HValue* context() const { return OperandAt(0); }
2592  HValue* value() const { return OperandAt(1); }
2593
2594  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
2595
2596  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
2597    if (index == 0) {
2598      return Representation::Tagged();
2599    } else {
2600      switch (op_) {
2601        case kMathFloor:
2602        case kMathRound:
2603        case kMathFround:
2604        case kMathSqrt:
2605        case kMathPowHalf:
2606        case kMathLog:
2607        case kMathExp:
2608          return Representation::Double();
2609        case kMathAbs:
2610          return representation();
2611        case kMathClz32:
2612          return Representation::Integer32();
2613        default:
2614          UNREACHABLE();
2615          return Representation::None();
2616      }
2617    }
2618  }
2619
2620  virtual Range* InferRange(Zone* zone) OVERRIDE;
2621
2622  virtual HValue* Canonicalize() OVERRIDE;
2623  virtual Representation RepresentationFromUses() OVERRIDE;
2624  virtual Representation RepresentationFromInputs() OVERRIDE;
2625
2626  BuiltinFunctionId op() const { return op_; }
2627  const char* OpName() const;
2628
2629  DECLARE_CONCRETE_INSTRUCTION(UnaryMathOperation)
2630
2631 protected:
2632  virtual bool DataEquals(HValue* other) OVERRIDE {
2633    HUnaryMathOperation* b = HUnaryMathOperation::cast(other);
2634    return op_ == b->op();
2635  }
2636
2637 private:
2638  // Indicates if we support a double (and int32) output for Math.floor and
2639  // Math.round.
2640  bool SupportsFlexibleFloorAndRound() const {
2641#ifdef V8_TARGET_ARCH_ARM64
2642    return true;
2643#else
2644    return false;
2645#endif
2646  }
2647  HUnaryMathOperation(HValue* context, HValue* value, BuiltinFunctionId op)
2648      : HTemplateInstruction<2>(HType::TaggedNumber()), op_(op) {
2649    SetOperandAt(0, context);
2650    SetOperandAt(1, value);
2651    switch (op) {
2652      case kMathFloor:
2653      case kMathRound:
2654        if (SupportsFlexibleFloorAndRound()) {
2655          SetFlag(kFlexibleRepresentation);
2656        } else {
2657          set_representation(Representation::Integer32());
2658        }
2659        break;
2660      case kMathClz32:
2661        set_representation(Representation::Integer32());
2662        break;
2663      case kMathAbs:
2664        // Not setting representation here: it is None intentionally.
2665        SetFlag(kFlexibleRepresentation);
2666        // TODO(svenpanne) This flag is actually only needed if representation()
2667        // is tagged, and not when it is an unboxed double or unboxed integer.
2668        SetChangesFlag(kNewSpacePromotion);
2669        break;
2670      case kMathFround:
2671      case kMathLog:
2672      case kMathExp:
2673      case kMathSqrt:
2674      case kMathPowHalf:
2675        set_representation(Representation::Double());
2676        break;
2677      default:
2678        UNREACHABLE();
2679    }
2680    SetFlag(kUseGVN);
2681    SetFlag(kAllowUndefinedAsNaN);
2682  }
2683
2684  virtual bool IsDeletable() const OVERRIDE { return true; }
2685
2686  HValue* SimplifiedDividendForMathFloorOfDiv(HDiv* hdiv);
2687  HValue* SimplifiedDivisorForMathFloorOfDiv(HDiv* hdiv);
2688
2689  BuiltinFunctionId op_;
2690};
2691
2692
2693class HLoadRoot FINAL : public HTemplateInstruction<0> {
2694 public:
2695  DECLARE_INSTRUCTION_FACTORY_P1(HLoadRoot, Heap::RootListIndex);
2696  DECLARE_INSTRUCTION_FACTORY_P2(HLoadRoot, Heap::RootListIndex, HType);
2697
2698  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
2699    return Representation::None();
2700  }
2701
2702  Heap::RootListIndex index() const { return index_; }
2703
2704  DECLARE_CONCRETE_INSTRUCTION(LoadRoot)
2705
2706 protected:
2707  virtual bool DataEquals(HValue* other) OVERRIDE {
2708    HLoadRoot* b = HLoadRoot::cast(other);
2709    return index_ == b->index_;
2710  }
2711
2712 private:
2713  explicit HLoadRoot(Heap::RootListIndex index, HType type = HType::Tagged())
2714      : HTemplateInstruction<0>(type), index_(index) {
2715    SetFlag(kUseGVN);
2716    // TODO(bmeurer): We'll need kDependsOnRoots once we add the
2717    // corresponding HStoreRoot instruction.
2718    SetDependsOnFlag(kCalls);
2719  }
2720
2721  virtual bool IsDeletable() const OVERRIDE { return true; }
2722
2723  const Heap::RootListIndex index_;
2724};
2725
2726
2727class HCheckMaps FINAL : public HTemplateInstruction<2> {
2728 public:
2729  static HCheckMaps* New(Zone* zone, HValue* context, HValue* value,
2730                         Handle<Map> map, HValue* typecheck = NULL) {
2731    return new(zone) HCheckMaps(value, new(zone) UniqueSet<Map>(
2732            Unique<Map>::CreateImmovable(map), zone), typecheck);
2733  }
2734  static HCheckMaps* New(Zone* zone, HValue* context,
2735                         HValue* value, SmallMapList* map_list,
2736                         HValue* typecheck = NULL) {
2737    UniqueSet<Map>* maps = new(zone) UniqueSet<Map>(map_list->length(), zone);
2738    for (int i = 0; i < map_list->length(); ++i) {
2739      maps->Add(Unique<Map>::CreateImmovable(map_list->at(i)), zone);
2740    }
2741    return new(zone) HCheckMaps(value, maps, typecheck);
2742  }
2743
2744  bool IsStabilityCheck() const { return is_stability_check_; }
2745  void MarkAsStabilityCheck() {
2746    maps_are_stable_ = true;
2747    has_migration_target_ = false;
2748    is_stability_check_ = true;
2749    ClearChangesFlag(kNewSpacePromotion);
2750    ClearDependsOnFlag(kElementsKind);
2751    ClearDependsOnFlag(kMaps);
2752  }
2753
2754  virtual bool HasEscapingOperandAt(int index) OVERRIDE { return false; }
2755  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
2756    return Representation::Tagged();
2757  }
2758
2759  virtual HType CalculateInferredType() OVERRIDE {
2760    if (value()->type().IsHeapObject()) return value()->type();
2761    return HType::HeapObject();
2762  }
2763
2764  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
2765
2766  HValue* value() const { return OperandAt(0); }
2767  HValue* typecheck() const { return OperandAt(1); }
2768
2769  const UniqueSet<Map>* maps() const { return maps_; }
2770  void set_maps(const UniqueSet<Map>* maps) { maps_ = maps; }
2771
2772  bool maps_are_stable() const { return maps_are_stable_; }
2773
2774  bool HasMigrationTarget() const { return has_migration_target_; }
2775
2776  virtual HValue* Canonicalize() OVERRIDE;
2777
2778  static HCheckMaps* CreateAndInsertAfter(Zone* zone,
2779                                          HValue* value,
2780                                          Unique<Map> map,
2781                                          bool map_is_stable,
2782                                          HInstruction* instr) {
2783    return instr->Append(new(zone) HCheckMaps(
2784            value, new(zone) UniqueSet<Map>(map, zone), map_is_stable));
2785  }
2786
2787  static HCheckMaps* CreateAndInsertBefore(Zone* zone,
2788                                           HValue* value,
2789                                           const UniqueSet<Map>* maps,
2790                                           bool maps_are_stable,
2791                                           HInstruction* instr) {
2792    return instr->Prepend(new(zone) HCheckMaps(value, maps, maps_are_stable));
2793  }
2794
2795  DECLARE_CONCRETE_INSTRUCTION(CheckMaps)
2796
2797 protected:
2798  virtual bool DataEquals(HValue* other) OVERRIDE {
2799    return this->maps()->Equals(HCheckMaps::cast(other)->maps());
2800  }
2801
2802  virtual int RedefinedOperandIndex() { return 0; }
2803
2804 private:
2805  HCheckMaps(HValue* value, const UniqueSet<Map>* maps, bool maps_are_stable)
2806      : HTemplateInstruction<2>(HType::HeapObject()), maps_(maps),
2807        has_migration_target_(false), is_stability_check_(false),
2808        maps_are_stable_(maps_are_stable) {
2809    DCHECK_NE(0, maps->size());
2810    SetOperandAt(0, value);
2811    // Use the object value for the dependency.
2812    SetOperandAt(1, value);
2813    set_representation(Representation::Tagged());
2814    SetFlag(kUseGVN);
2815    SetDependsOnFlag(kMaps);
2816    SetDependsOnFlag(kElementsKind);
2817  }
2818
2819  HCheckMaps(HValue* value, const UniqueSet<Map>* maps, HValue* typecheck)
2820      : HTemplateInstruction<2>(HType::HeapObject()), maps_(maps),
2821        has_migration_target_(false), is_stability_check_(false),
2822        maps_are_stable_(true) {
2823    DCHECK_NE(0, maps->size());
2824    SetOperandAt(0, value);
2825    // Use the object value for the dependency if NULL is passed.
2826    SetOperandAt(1, typecheck ? typecheck : value);
2827    set_representation(Representation::Tagged());
2828    SetFlag(kUseGVN);
2829    SetDependsOnFlag(kMaps);
2830    SetDependsOnFlag(kElementsKind);
2831    for (int i = 0; i < maps->size(); ++i) {
2832      Handle<Map> map = maps->at(i).handle();
2833      if (map->is_migration_target()) has_migration_target_ = true;
2834      if (!map->is_stable()) maps_are_stable_ = false;
2835    }
2836    if (has_migration_target_) SetChangesFlag(kNewSpacePromotion);
2837  }
2838
2839  const UniqueSet<Map>* maps_;
2840  bool has_migration_target_ : 1;
2841  bool is_stability_check_ : 1;
2842  bool maps_are_stable_ : 1;
2843};
2844
2845
2846class HCheckValue FINAL : public HUnaryOperation {
2847 public:
2848  static HCheckValue* New(Zone* zone, HValue* context,
2849                          HValue* value, Handle<JSFunction> func) {
2850    bool in_new_space = zone->isolate()->heap()->InNewSpace(*func);
2851    // NOTE: We create an uninitialized Unique and initialize it later.
2852    // This is because a JSFunction can move due to GC during graph creation.
2853    // TODO(titzer): This is a migration crutch. Replace with some kind of
2854    // Uniqueness scope later.
2855    Unique<JSFunction> target = Unique<JSFunction>::CreateUninitialized(func);
2856    HCheckValue* check = new(zone) HCheckValue(value, target, in_new_space);
2857    return check;
2858  }
2859  static HCheckValue* New(Zone* zone, HValue* context,
2860                          HValue* value, Unique<HeapObject> target,
2861                          bool object_in_new_space) {
2862    return new(zone) HCheckValue(value, target, object_in_new_space);
2863  }
2864
2865  virtual void FinalizeUniqueness() OVERRIDE {
2866    object_ = Unique<HeapObject>(object_.handle());
2867  }
2868
2869  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
2870    return Representation::Tagged();
2871  }
2872  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
2873
2874  virtual HValue* Canonicalize() OVERRIDE;
2875
2876#ifdef DEBUG
2877  virtual void Verify() OVERRIDE;
2878#endif
2879
2880  Unique<HeapObject> object() const { return object_; }
2881  bool object_in_new_space() const { return object_in_new_space_; }
2882
2883  DECLARE_CONCRETE_INSTRUCTION(CheckValue)
2884
2885 protected:
2886  virtual bool DataEquals(HValue* other) OVERRIDE {
2887    HCheckValue* b = HCheckValue::cast(other);
2888    return object_ == b->object_;
2889  }
2890
2891 private:
2892  HCheckValue(HValue* value, Unique<HeapObject> object,
2893               bool object_in_new_space)
2894      : HUnaryOperation(value, value->type()),
2895        object_(object),
2896        object_in_new_space_(object_in_new_space) {
2897    set_representation(Representation::Tagged());
2898    SetFlag(kUseGVN);
2899  }
2900
2901  Unique<HeapObject> object_;
2902  bool object_in_new_space_;
2903};
2904
2905
2906class HCheckInstanceType FINAL : public HUnaryOperation {
2907 public:
2908  enum Check {
2909    IS_SPEC_OBJECT,
2910    IS_JS_ARRAY,
2911    IS_STRING,
2912    IS_INTERNALIZED_STRING,
2913    LAST_INTERVAL_CHECK = IS_JS_ARRAY
2914  };
2915
2916  DECLARE_INSTRUCTION_FACTORY_P2(HCheckInstanceType, HValue*, Check);
2917
2918  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
2919
2920  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
2921    return Representation::Tagged();
2922  }
2923
2924  virtual HType CalculateInferredType() OVERRIDE {
2925    switch (check_) {
2926      case IS_SPEC_OBJECT: return HType::JSObject();
2927      case IS_JS_ARRAY: return HType::JSArray();
2928      case IS_STRING: return HType::String();
2929      case IS_INTERNALIZED_STRING: return HType::String();
2930    }
2931    UNREACHABLE();
2932    return HType::Tagged();
2933  }
2934
2935  virtual HValue* Canonicalize() OVERRIDE;
2936
2937  bool is_interval_check() const { return check_ <= LAST_INTERVAL_CHECK; }
2938  void GetCheckInterval(InstanceType* first, InstanceType* last);
2939  void GetCheckMaskAndTag(uint8_t* mask, uint8_t* tag);
2940
2941  Check check() const { return check_; }
2942
2943  DECLARE_CONCRETE_INSTRUCTION(CheckInstanceType)
2944
2945 protected:
2946  // TODO(ager): It could be nice to allow the ommision of instance
2947  // type checks if we have already performed an instance type check
2948  // with a larger range.
2949  virtual bool DataEquals(HValue* other) OVERRIDE {
2950    HCheckInstanceType* b = HCheckInstanceType::cast(other);
2951    return check_ == b->check_;
2952  }
2953
2954  virtual int RedefinedOperandIndex() { return 0; }
2955
2956 private:
2957  const char* GetCheckName() const;
2958
2959  HCheckInstanceType(HValue* value, Check check)
2960      : HUnaryOperation(value, HType::HeapObject()), check_(check) {
2961    set_representation(Representation::Tagged());
2962    SetFlag(kUseGVN);
2963  }
2964
2965  const Check check_;
2966};
2967
2968
2969class HCheckSmi FINAL : public HUnaryOperation {
2970 public:
2971  DECLARE_INSTRUCTION_FACTORY_P1(HCheckSmi, HValue*);
2972
2973  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
2974    return Representation::Tagged();
2975  }
2976
2977  virtual HValue* Canonicalize() OVERRIDE {
2978    HType value_type = value()->type();
2979    if (value_type.IsSmi()) {
2980      return NULL;
2981    }
2982    return this;
2983  }
2984
2985  DECLARE_CONCRETE_INSTRUCTION(CheckSmi)
2986
2987 protected:
2988  virtual bool DataEquals(HValue* other) OVERRIDE { return true; }
2989
2990 private:
2991  explicit HCheckSmi(HValue* value) : HUnaryOperation(value, HType::Smi()) {
2992    set_representation(Representation::Smi());
2993    SetFlag(kUseGVN);
2994  }
2995};
2996
2997
2998class HCheckHeapObject FINAL : public HUnaryOperation {
2999 public:
3000  DECLARE_INSTRUCTION_FACTORY_P1(HCheckHeapObject, HValue*);
3001
3002  virtual bool HasEscapingOperandAt(int index) OVERRIDE { return false; }
3003  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
3004    return Representation::Tagged();
3005  }
3006
3007  virtual HType CalculateInferredType() OVERRIDE {
3008    if (value()->type().IsHeapObject()) return value()->type();
3009    return HType::HeapObject();
3010  }
3011
3012#ifdef DEBUG
3013  virtual void Verify() OVERRIDE;
3014#endif
3015
3016  virtual HValue* Canonicalize() OVERRIDE {
3017    return value()->type().IsHeapObject() ? NULL : this;
3018  }
3019
3020  DECLARE_CONCRETE_INSTRUCTION(CheckHeapObject)
3021
3022 protected:
3023  virtual bool DataEquals(HValue* other) OVERRIDE { return true; }
3024
3025 private:
3026  explicit HCheckHeapObject(HValue* value) : HUnaryOperation(value) {
3027    set_representation(Representation::Tagged());
3028    SetFlag(kUseGVN);
3029  }
3030};
3031
3032
3033class InductionVariableData;
3034
3035
3036struct InductionVariableLimitUpdate {
3037  InductionVariableData* updated_variable;
3038  HValue* limit;
3039  bool limit_is_upper;
3040  bool limit_is_included;
3041
3042  InductionVariableLimitUpdate()
3043      : updated_variable(NULL), limit(NULL),
3044        limit_is_upper(false), limit_is_included(false) {}
3045};
3046
3047
3048class HBoundsCheck;
3049class HPhi;
3050class HBitwise;
3051
3052
3053class InductionVariableData FINAL : public ZoneObject {
3054 public:
3055  class InductionVariableCheck : public ZoneObject {
3056   public:
3057    HBoundsCheck* check() { return check_; }
3058    InductionVariableCheck* next() { return next_; }
3059    bool HasUpperLimit() { return upper_limit_ >= 0; }
3060    int32_t upper_limit() {
3061      DCHECK(HasUpperLimit());
3062      return upper_limit_;
3063    }
3064    void set_upper_limit(int32_t upper_limit) {
3065      upper_limit_ = upper_limit;
3066    }
3067
3068    bool processed() { return processed_; }
3069    void set_processed() { processed_ = true; }
3070
3071    InductionVariableCheck(HBoundsCheck* check,
3072                           InductionVariableCheck* next,
3073                           int32_t upper_limit = kNoLimit)
3074        : check_(check), next_(next), upper_limit_(upper_limit),
3075          processed_(false) {}
3076
3077   private:
3078    HBoundsCheck* check_;
3079    InductionVariableCheck* next_;
3080    int32_t upper_limit_;
3081    bool processed_;
3082  };
3083
3084  class ChecksRelatedToLength : public ZoneObject {
3085   public:
3086    HValue* length() { return length_; }
3087    ChecksRelatedToLength* next() { return next_; }
3088    InductionVariableCheck* checks() { return checks_; }
3089
3090    void AddCheck(HBoundsCheck* check, int32_t upper_limit = kNoLimit);
3091    void CloseCurrentBlock();
3092
3093    ChecksRelatedToLength(HValue* length, ChecksRelatedToLength* next)
3094      : length_(length), next_(next), checks_(NULL),
3095        first_check_in_block_(NULL),
3096        added_index_(NULL),
3097        added_constant_(NULL),
3098        current_and_mask_in_block_(0),
3099        current_or_mask_in_block_(0) {}
3100
3101   private:
3102    void UseNewIndexInCurrentBlock(Token::Value token,
3103                                   int32_t mask,
3104                                   HValue* index_base,
3105                                   HValue* context);
3106
3107    HBoundsCheck* first_check_in_block() { return first_check_in_block_; }
3108    HBitwise* added_index() { return added_index_; }
3109    void set_added_index(HBitwise* index) { added_index_ = index; }
3110    HConstant* added_constant() { return added_constant_; }
3111    void set_added_constant(HConstant* constant) { added_constant_ = constant; }
3112    int32_t current_and_mask_in_block() { return current_and_mask_in_block_; }
3113    int32_t current_or_mask_in_block() { return current_or_mask_in_block_; }
3114    int32_t current_upper_limit() { return current_upper_limit_; }
3115
3116    HValue* length_;
3117    ChecksRelatedToLength* next_;
3118    InductionVariableCheck* checks_;
3119
3120    HBoundsCheck* first_check_in_block_;
3121    HBitwise* added_index_;
3122    HConstant* added_constant_;
3123    int32_t current_and_mask_in_block_;
3124    int32_t current_or_mask_in_block_;
3125    int32_t current_upper_limit_;
3126  };
3127
3128  struct LimitFromPredecessorBlock {
3129    InductionVariableData* variable;
3130    Token::Value token;
3131    HValue* limit;
3132    HBasicBlock* other_target;
3133
3134    bool LimitIsValid() { return token != Token::ILLEGAL; }
3135
3136    bool LimitIsIncluded() {
3137      return Token::IsEqualityOp(token) ||
3138          token == Token::GTE || token == Token::LTE;
3139    }
3140    bool LimitIsUpper() {
3141      return token == Token::LTE || token == Token::LT || token == Token::NE;
3142    }
3143
3144    LimitFromPredecessorBlock()
3145        : variable(NULL),
3146          token(Token::ILLEGAL),
3147          limit(NULL),
3148          other_target(NULL) {}
3149  };
3150
3151  static const int32_t kNoLimit = -1;
3152
3153  static InductionVariableData* ExaminePhi(HPhi* phi);
3154  static void ComputeLimitFromPredecessorBlock(
3155      HBasicBlock* block,
3156      LimitFromPredecessorBlock* result);
3157  static bool ComputeInductionVariableLimit(
3158      HBasicBlock* block,
3159      InductionVariableLimitUpdate* additional_limit);
3160
3161  struct BitwiseDecompositionResult {
3162    HValue* base;
3163    int32_t and_mask;
3164    int32_t or_mask;
3165    HValue* context;
3166
3167    BitwiseDecompositionResult()
3168        : base(NULL), and_mask(0), or_mask(0), context(NULL) {}
3169  };
3170  static void DecomposeBitwise(HValue* value,
3171                               BitwiseDecompositionResult* result);
3172
3173  void AddCheck(HBoundsCheck* check, int32_t upper_limit = kNoLimit);
3174
3175  bool CheckIfBranchIsLoopGuard(Token::Value token,
3176                                HBasicBlock* current_branch,
3177                                HBasicBlock* other_branch);
3178
3179  void UpdateAdditionalLimit(InductionVariableLimitUpdate* update);
3180
3181  HPhi* phi() { return phi_; }
3182  HValue* base() { return base_; }
3183  int32_t increment() { return increment_; }
3184  HValue* limit() { return limit_; }
3185  bool limit_included() { return limit_included_; }
3186  HBasicBlock* limit_validity() { return limit_validity_; }
3187  HBasicBlock* induction_exit_block() { return induction_exit_block_; }
3188  HBasicBlock* induction_exit_target() { return induction_exit_target_; }
3189  ChecksRelatedToLength* checks() { return checks_; }
3190  HValue* additional_upper_limit() { return additional_upper_limit_; }
3191  bool additional_upper_limit_is_included() {
3192    return additional_upper_limit_is_included_;
3193  }
3194  HValue* additional_lower_limit() { return additional_lower_limit_; }
3195  bool additional_lower_limit_is_included() {
3196    return additional_lower_limit_is_included_;
3197  }
3198
3199  bool LowerLimitIsNonNegativeConstant() {
3200    if (base()->IsInteger32Constant() && base()->GetInteger32Constant() >= 0) {
3201      return true;
3202    }
3203    if (additional_lower_limit() != NULL &&
3204        additional_lower_limit()->IsInteger32Constant() &&
3205        additional_lower_limit()->GetInteger32Constant() >= 0) {
3206      // Ignoring the corner case of !additional_lower_limit_is_included()
3207      // is safe, handling it adds unneeded complexity.
3208      return true;
3209    }
3210    return false;
3211  }
3212
3213  int32_t ComputeUpperLimit(int32_t and_mask, int32_t or_mask);
3214
3215 private:
3216  template <class T> void swap(T* a, T* b) {
3217    T c(*a);
3218    *a = *b;
3219    *b = c;
3220  }
3221
3222  InductionVariableData(HPhi* phi, HValue* base, int32_t increment)
3223      : phi_(phi), base_(IgnoreOsrValue(base)), increment_(increment),
3224        limit_(NULL), limit_included_(false), limit_validity_(NULL),
3225        induction_exit_block_(NULL), induction_exit_target_(NULL),
3226        checks_(NULL),
3227        additional_upper_limit_(NULL),
3228        additional_upper_limit_is_included_(false),
3229        additional_lower_limit_(NULL),
3230        additional_lower_limit_is_included_(false) {}
3231
3232  static int32_t ComputeIncrement(HPhi* phi, HValue* phi_operand);
3233
3234  static HValue* IgnoreOsrValue(HValue* v);
3235  static InductionVariableData* GetInductionVariableData(HValue* v);
3236
3237  HPhi* phi_;
3238  HValue* base_;
3239  int32_t increment_;
3240  HValue* limit_;
3241  bool limit_included_;
3242  HBasicBlock* limit_validity_;
3243  HBasicBlock* induction_exit_block_;
3244  HBasicBlock* induction_exit_target_;
3245  ChecksRelatedToLength* checks_;
3246  HValue* additional_upper_limit_;
3247  bool additional_upper_limit_is_included_;
3248  HValue* additional_lower_limit_;
3249  bool additional_lower_limit_is_included_;
3250};
3251
3252
3253class HPhi FINAL : public HValue {
3254 public:
3255  HPhi(int merged_index, Zone* zone)
3256      : inputs_(2, zone),
3257        merged_index_(merged_index),
3258        phi_id_(-1),
3259        induction_variable_data_(NULL) {
3260    for (int i = 0; i < Representation::kNumRepresentations; i++) {
3261      non_phi_uses_[i] = 0;
3262      indirect_uses_[i] = 0;
3263    }
3264    DCHECK(merged_index >= 0 || merged_index == kInvalidMergedIndex);
3265    SetFlag(kFlexibleRepresentation);
3266    SetFlag(kAllowUndefinedAsNaN);
3267  }
3268
3269  virtual Representation RepresentationFromInputs() OVERRIDE;
3270
3271  virtual Range* InferRange(Zone* zone) OVERRIDE;
3272  virtual void InferRepresentation(
3273      HInferRepresentationPhase* h_infer) OVERRIDE;
3274  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
3275    return representation();
3276  }
3277  virtual Representation KnownOptimalRepresentation() OVERRIDE {
3278    return representation();
3279  }
3280  virtual HType CalculateInferredType() OVERRIDE;
3281  virtual int OperandCount() const OVERRIDE { return inputs_.length(); }
3282  virtual HValue* OperandAt(int index) const OVERRIDE {
3283    return inputs_[index];
3284  }
3285  HValue* GetRedundantReplacement();
3286  void AddInput(HValue* value);
3287  bool HasRealUses();
3288
3289  bool IsReceiver() const { return merged_index_ == 0; }
3290  bool HasMergedIndex() const { return merged_index_ != kInvalidMergedIndex; }
3291
3292  virtual HSourcePosition position() const OVERRIDE;
3293
3294  int merged_index() const { return merged_index_; }
3295
3296  InductionVariableData* induction_variable_data() {
3297    return induction_variable_data_;
3298  }
3299  bool IsInductionVariable() {
3300    return induction_variable_data_ != NULL;
3301  }
3302  bool IsLimitedInductionVariable() {
3303    return IsInductionVariable() &&
3304        induction_variable_data_->limit() != NULL;
3305  }
3306  void DetectInductionVariable() {
3307    DCHECK(induction_variable_data_ == NULL);
3308    induction_variable_data_ = InductionVariableData::ExaminePhi(this);
3309  }
3310
3311  virtual OStream& PrintTo(OStream& os) const OVERRIDE;  // NOLINT
3312
3313#ifdef DEBUG
3314  virtual void Verify() OVERRIDE;
3315#endif
3316
3317  void InitRealUses(int id);
3318  void AddNonPhiUsesFrom(HPhi* other);
3319  void AddIndirectUsesTo(int* use_count);
3320
3321  int tagged_non_phi_uses() const {
3322    return non_phi_uses_[Representation::kTagged];
3323  }
3324  int smi_non_phi_uses() const {
3325    return non_phi_uses_[Representation::kSmi];
3326  }
3327  int int32_non_phi_uses() const {
3328    return non_phi_uses_[Representation::kInteger32];
3329  }
3330  int double_non_phi_uses() const {
3331    return non_phi_uses_[Representation::kDouble];
3332  }
3333  int tagged_indirect_uses() const {
3334    return indirect_uses_[Representation::kTagged];
3335  }
3336  int smi_indirect_uses() const {
3337    return indirect_uses_[Representation::kSmi];
3338  }
3339  int int32_indirect_uses() const {
3340    return indirect_uses_[Representation::kInteger32];
3341  }
3342  int double_indirect_uses() const {
3343    return indirect_uses_[Representation::kDouble];
3344  }
3345  int phi_id() { return phi_id_; }
3346
3347  static HPhi* cast(HValue* value) {
3348    DCHECK(value->IsPhi());
3349    return reinterpret_cast<HPhi*>(value);
3350  }
3351  virtual Opcode opcode() const OVERRIDE { return HValue::kPhi; }
3352
3353  void SimplifyConstantInputs();
3354
3355  // Marker value representing an invalid merge index.
3356  static const int kInvalidMergedIndex = -1;
3357
3358 protected:
3359  virtual void DeleteFromGraph() OVERRIDE;
3360  virtual void InternalSetOperandAt(int index, HValue* value) OVERRIDE {
3361    inputs_[index] = value;
3362  }
3363
3364 private:
3365  ZoneList<HValue*> inputs_;
3366  int merged_index_;
3367
3368  int non_phi_uses_[Representation::kNumRepresentations];
3369  int indirect_uses_[Representation::kNumRepresentations];
3370  int phi_id_;
3371  InductionVariableData* induction_variable_data_;
3372
3373  // TODO(titzer): we can't eliminate the receiver for generating backtraces
3374  virtual bool IsDeletable() const OVERRIDE { return !IsReceiver(); }
3375};
3376
3377
3378// Common base class for HArgumentsObject and HCapturedObject.
3379class HDematerializedObject : public HInstruction {
3380 public:
3381  HDematerializedObject(int count, Zone* zone) : values_(count, zone) {}
3382
3383  virtual int OperandCount() const FINAL OVERRIDE {
3384    return values_.length();
3385  }
3386  virtual HValue* OperandAt(int index) const FINAL OVERRIDE {
3387    return values_[index];
3388  }
3389
3390  virtual bool HasEscapingOperandAt(int index) FINAL OVERRIDE {
3391    return false;
3392  }
3393  virtual Representation RequiredInputRepresentation(
3394      int index) FINAL OVERRIDE {
3395    return Representation::None();
3396  }
3397
3398 protected:
3399  virtual void InternalSetOperandAt(int index,
3400                                    HValue* value) FINAL OVERRIDE {
3401    values_[index] = value;
3402  }
3403
3404  // List of values tracked by this marker.
3405  ZoneList<HValue*> values_;
3406};
3407
3408
3409class HArgumentsObject FINAL : public HDematerializedObject {
3410 public:
3411  static HArgumentsObject* New(Zone* zone, HValue* context, int count) {
3412    return new(zone) HArgumentsObject(count, zone);
3413  }
3414
3415  // The values contain a list of all elements in the arguments object
3416  // including the receiver object, which is skipped when materializing.
3417  const ZoneList<HValue*>* arguments_values() const { return &values_; }
3418  int arguments_count() const { return values_.length(); }
3419
3420  void AddArgument(HValue* argument, Zone* zone) {
3421    values_.Add(NULL, zone);  // Resize list.
3422    SetOperandAt(values_.length() - 1, argument);
3423  }
3424
3425  DECLARE_CONCRETE_INSTRUCTION(ArgumentsObject)
3426
3427 private:
3428  HArgumentsObject(int count, Zone* zone)
3429      : HDematerializedObject(count, zone) {
3430    set_representation(Representation::Tagged());
3431    SetFlag(kIsArguments);
3432  }
3433};
3434
3435
3436class HCapturedObject FINAL : public HDematerializedObject {
3437 public:
3438  HCapturedObject(int length, int id, Zone* zone)
3439      : HDematerializedObject(length, zone), capture_id_(id) {
3440    set_representation(Representation::Tagged());
3441    values_.AddBlock(NULL, length, zone);  // Resize list.
3442  }
3443
3444  // The values contain a list of all in-object properties inside the
3445  // captured object and is index by field index. Properties in the
3446  // properties or elements backing store are not tracked here.
3447  const ZoneList<HValue*>* values() const { return &values_; }
3448  int length() const { return values_.length(); }
3449  int capture_id() const { return capture_id_; }
3450
3451  // Shortcut for the map value of this captured object.
3452  HValue* map_value() const { return values()->first(); }
3453
3454  void ReuseSideEffectsFromStore(HInstruction* store) {
3455    DCHECK(store->HasObservableSideEffects());
3456    DCHECK(store->IsStoreNamedField());
3457    changes_flags_.Add(store->ChangesFlags());
3458  }
3459
3460  // Replay effects of this instruction on the given environment.
3461  void ReplayEnvironment(HEnvironment* env);
3462
3463  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
3464
3465  DECLARE_CONCRETE_INSTRUCTION(CapturedObject)
3466
3467 private:
3468  int capture_id_;
3469
3470  // Note that we cannot DCE captured objects as they are used to replay
3471  // the environment. This method is here as an explicit reminder.
3472  // TODO(mstarzinger): Turn HSimulates into full snapshots maybe?
3473  virtual bool IsDeletable() const FINAL OVERRIDE { return false; }
3474};
3475
3476
3477class HConstant FINAL : public HTemplateInstruction<0> {
3478 public:
3479  DECLARE_INSTRUCTION_FACTORY_P1(HConstant, int32_t);
3480  DECLARE_INSTRUCTION_FACTORY_P2(HConstant, int32_t, Representation);
3481  DECLARE_INSTRUCTION_FACTORY_P1(HConstant, double);
3482  DECLARE_INSTRUCTION_FACTORY_P1(HConstant, Handle<Object>);
3483  DECLARE_INSTRUCTION_FACTORY_P1(HConstant, ExternalReference);
3484
3485  static HConstant* CreateAndInsertAfter(Zone* zone,
3486                                         HValue* context,
3487                                         int32_t value,
3488                                         Representation representation,
3489                                         HInstruction* instruction) {
3490    return instruction->Append(HConstant::New(
3491        zone, context, value, representation));
3492  }
3493
3494  virtual Handle<Map> GetMonomorphicJSObjectMap() OVERRIDE {
3495    Handle<Object> object = object_.handle();
3496    if (!object.is_null() && object->IsHeapObject()) {
3497      return v8::internal::handle(HeapObject::cast(*object)->map());
3498    }
3499    return Handle<Map>();
3500  }
3501
3502  static HConstant* CreateAndInsertBefore(Zone* zone,
3503                                          HValue* context,
3504                                          int32_t value,
3505                                          Representation representation,
3506                                          HInstruction* instruction) {
3507    return instruction->Prepend(HConstant::New(
3508        zone, context, value, representation));
3509  }
3510
3511  static HConstant* CreateAndInsertBefore(Zone* zone,
3512                                          Unique<Map> map,
3513                                          bool map_is_stable,
3514                                          HInstruction* instruction) {
3515    return instruction->Prepend(new(zone) HConstant(
3516        map, Unique<Map>(Handle<Map>::null()), map_is_stable,
3517        Representation::Tagged(), HType::HeapObject(), true,
3518        false, false, MAP_TYPE));
3519  }
3520
3521  static HConstant* CreateAndInsertAfter(Zone* zone,
3522                                         Unique<Map> map,
3523                                         bool map_is_stable,
3524                                         HInstruction* instruction) {
3525    return instruction->Append(new(zone) HConstant(
3526            map, Unique<Map>(Handle<Map>::null()), map_is_stable,
3527            Representation::Tagged(), HType::HeapObject(), true,
3528            false, false, MAP_TYPE));
3529  }
3530
3531  Handle<Object> handle(Isolate* isolate) {
3532    if (object_.handle().is_null()) {
3533      // Default arguments to is_not_in_new_space depend on this heap number
3534      // to be tenured so that it's guaranteed not to be located in new space.
3535      object_ = Unique<Object>::CreateUninitialized(
3536          isolate->factory()->NewNumber(double_value_, TENURED));
3537    }
3538    AllowDeferredHandleDereference smi_check;
3539    DCHECK(has_int32_value_ || !object_.handle()->IsSmi());
3540    return object_.handle();
3541  }
3542
3543  bool IsSpecialDouble() const {
3544    return has_double_value_ &&
3545           (bit_cast<int64_t>(double_value_) == bit_cast<int64_t>(-0.0) ||
3546            FixedDoubleArray::is_the_hole_nan(double_value_) ||
3547            std::isnan(double_value_));
3548  }
3549
3550  bool NotInNewSpace() const {
3551    return is_not_in_new_space_;
3552  }
3553
3554  bool ImmortalImmovable() const;
3555
3556  bool IsCell() const {
3557    return instance_type_ == CELL_TYPE || instance_type_ == PROPERTY_CELL_TYPE;
3558  }
3559
3560  bool IsMap() const {
3561    return instance_type_ == MAP_TYPE;
3562  }
3563
3564  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
3565    return Representation::None();
3566  }
3567
3568  virtual Representation KnownOptimalRepresentation() OVERRIDE {
3569    if (HasSmiValue() && SmiValuesAre31Bits()) return Representation::Smi();
3570    if (HasInteger32Value()) return Representation::Integer32();
3571    if (HasNumberValue()) return Representation::Double();
3572    if (HasExternalReferenceValue()) return Representation::External();
3573    return Representation::Tagged();
3574  }
3575
3576  virtual bool EmitAtUses() OVERRIDE;
3577  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
3578  HConstant* CopyToRepresentation(Representation r, Zone* zone) const;
3579  Maybe<HConstant*> CopyToTruncatedInt32(Zone* zone);
3580  Maybe<HConstant*> CopyToTruncatedNumber(Zone* zone);
3581  bool HasInteger32Value() const { return has_int32_value_; }
3582  int32_t Integer32Value() const {
3583    DCHECK(HasInteger32Value());
3584    return int32_value_;
3585  }
3586  bool HasSmiValue() const { return has_smi_value_; }
3587  bool HasDoubleValue() const { return has_double_value_; }
3588  double DoubleValue() const {
3589    DCHECK(HasDoubleValue());
3590    return double_value_;
3591  }
3592  bool IsTheHole() const {
3593    if (HasDoubleValue() && FixedDoubleArray::is_the_hole_nan(double_value_)) {
3594      return true;
3595    }
3596    return object_.IsInitialized() &&
3597           object_.IsKnownGlobal(isolate()->heap()->the_hole_value());
3598  }
3599  bool HasNumberValue() const { return has_double_value_; }
3600  int32_t NumberValueAsInteger32() const {
3601    DCHECK(HasNumberValue());
3602    // Irrespective of whether a numeric HConstant can be safely
3603    // represented as an int32, we store the (in some cases lossy)
3604    // representation of the number in int32_value_.
3605    return int32_value_;
3606  }
3607  bool HasStringValue() const {
3608    if (has_double_value_ || has_int32_value_) return false;
3609    DCHECK(!object_.handle().is_null());
3610    return instance_type_ < FIRST_NONSTRING_TYPE;
3611  }
3612  Handle<String> StringValue() const {
3613    DCHECK(HasStringValue());
3614    return Handle<String>::cast(object_.handle());
3615  }
3616  bool HasInternalizedStringValue() const {
3617    return HasStringValue() && StringShape(instance_type_).IsInternalized();
3618  }
3619
3620  bool HasExternalReferenceValue() const {
3621    return has_external_reference_value_;
3622  }
3623  ExternalReference ExternalReferenceValue() const {
3624    return external_reference_value_;
3625  }
3626
3627  bool HasBooleanValue() const { return type_.IsBoolean(); }
3628  bool BooleanValue() const { return boolean_value_; }
3629  bool IsUndetectable() const { return is_undetectable_; }
3630  InstanceType GetInstanceType() const { return instance_type_; }
3631
3632  bool HasMapValue() const { return instance_type_ == MAP_TYPE; }
3633  Unique<Map> MapValue() const {
3634    DCHECK(HasMapValue());
3635    return Unique<Map>::cast(GetUnique());
3636  }
3637  bool HasStableMapValue() const {
3638    DCHECK(HasMapValue() || !has_stable_map_value_);
3639    return has_stable_map_value_;
3640  }
3641
3642  bool HasObjectMap() const { return !object_map_.IsNull(); }
3643  Unique<Map> ObjectMap() const {
3644    DCHECK(HasObjectMap());
3645    return object_map_;
3646  }
3647
3648  virtual intptr_t Hashcode() OVERRIDE {
3649    if (has_int32_value_) {
3650      return static_cast<intptr_t>(int32_value_);
3651    } else if (has_double_value_) {
3652      return static_cast<intptr_t>(bit_cast<int64_t>(double_value_));
3653    } else if (has_external_reference_value_) {
3654      return reinterpret_cast<intptr_t>(external_reference_value_.address());
3655    } else {
3656      DCHECK(!object_.handle().is_null());
3657      return object_.Hashcode();
3658    }
3659  }
3660
3661  virtual void FinalizeUniqueness() OVERRIDE {
3662    if (!has_double_value_ && !has_external_reference_value_) {
3663      DCHECK(!object_.handle().is_null());
3664      object_ = Unique<Object>(object_.handle());
3665    }
3666  }
3667
3668  Unique<Object> GetUnique() const {
3669    return object_;
3670  }
3671
3672  bool EqualsUnique(Unique<Object> other) const {
3673    return object_.IsInitialized() && object_ == other;
3674  }
3675
3676  virtual bool DataEquals(HValue* other) OVERRIDE {
3677    HConstant* other_constant = HConstant::cast(other);
3678    if (has_int32_value_) {
3679      return other_constant->has_int32_value_ &&
3680          int32_value_ == other_constant->int32_value_;
3681    } else if (has_double_value_) {
3682      return other_constant->has_double_value_ &&
3683             bit_cast<int64_t>(double_value_) ==
3684                 bit_cast<int64_t>(other_constant->double_value_);
3685    } else if (has_external_reference_value_) {
3686      return other_constant->has_external_reference_value_ &&
3687          external_reference_value_ ==
3688          other_constant->external_reference_value_;
3689    } else {
3690      if (other_constant->has_int32_value_ ||
3691          other_constant->has_double_value_ ||
3692          other_constant->has_external_reference_value_) {
3693        return false;
3694      }
3695      DCHECK(!object_.handle().is_null());
3696      return other_constant->object_ == object_;
3697    }
3698  }
3699
3700#ifdef DEBUG
3701  virtual void Verify() OVERRIDE { }
3702#endif
3703
3704  DECLARE_CONCRETE_INSTRUCTION(Constant)
3705
3706 protected:
3707  virtual Range* InferRange(Zone* zone) OVERRIDE;
3708
3709 private:
3710  friend class HGraph;
3711  explicit HConstant(Handle<Object> handle,
3712                     Representation r = Representation::None());
3713  HConstant(int32_t value,
3714            Representation r = Representation::None(),
3715            bool is_not_in_new_space = true,
3716            Unique<Object> optional = Unique<Object>(Handle<Object>::null()));
3717  HConstant(double value,
3718            Representation r = Representation::None(),
3719            bool is_not_in_new_space = true,
3720            Unique<Object> optional = Unique<Object>(Handle<Object>::null()));
3721  HConstant(Unique<Object> object,
3722            Unique<Map> object_map,
3723            bool has_stable_map_value,
3724            Representation r,
3725            HType type,
3726            bool is_not_in_new_space,
3727            bool boolean_value,
3728            bool is_undetectable,
3729            InstanceType instance_type);
3730
3731  explicit HConstant(ExternalReference reference);
3732
3733  void Initialize(Representation r);
3734
3735  virtual bool IsDeletable() const OVERRIDE { return true; }
3736
3737  // If this is a numerical constant, object_ either points to the
3738  // HeapObject the constant originated from or is null.  If the
3739  // constant is non-numeric, object_ always points to a valid
3740  // constant HeapObject.
3741  Unique<Object> object_;
3742
3743  // If object_ is a heap object, this points to the stable map of the object.
3744  Unique<Map> object_map_;
3745
3746  // If object_ is a map, this indicates whether the map is stable.
3747  bool has_stable_map_value_ : 1;
3748
3749  // We store the HConstant in the most specific form safely possible.
3750  // The two flags, has_int32_value_ and has_double_value_ tell us if
3751  // int32_value_ and double_value_ hold valid, safe representations
3752  // of the constant.  has_int32_value_ implies has_double_value_ but
3753  // not the converse.
3754  bool has_smi_value_ : 1;
3755  bool has_int32_value_ : 1;
3756  bool has_double_value_ : 1;
3757  bool has_external_reference_value_ : 1;
3758  bool is_not_in_new_space_ : 1;
3759  bool boolean_value_ : 1;
3760  bool is_undetectable_: 1;
3761  int32_t int32_value_;
3762  double double_value_;
3763  ExternalReference external_reference_value_;
3764
3765  static const InstanceType kUnknownInstanceType = FILLER_TYPE;
3766  InstanceType instance_type_;
3767};
3768
3769
3770class HBinaryOperation : public HTemplateInstruction<3> {
3771 public:
3772  HBinaryOperation(HValue* context, HValue* left, HValue* right,
3773                   HType type = HType::Tagged())
3774      : HTemplateInstruction<3>(type),
3775        observed_output_representation_(Representation::None()) {
3776    DCHECK(left != NULL && right != NULL);
3777    SetOperandAt(0, context);
3778    SetOperandAt(1, left);
3779    SetOperandAt(2, right);
3780    observed_input_representation_[0] = Representation::None();
3781    observed_input_representation_[1] = Representation::None();
3782  }
3783
3784  HValue* context() const { return OperandAt(0); }
3785  HValue* left() const { return OperandAt(1); }
3786  HValue* right() const { return OperandAt(2); }
3787
3788  // True if switching left and right operands likely generates better code.
3789  bool AreOperandsBetterSwitched() {
3790    if (!IsCommutative()) return false;
3791
3792    // Constant operands are better off on the right, they can be inlined in
3793    // many situations on most platforms.
3794    if (left()->IsConstant()) return true;
3795    if (right()->IsConstant()) return false;
3796
3797    // Otherwise, if there is only one use of the right operand, it would be
3798    // better off on the left for platforms that only have 2-arg arithmetic
3799    // ops (e.g ia32, x64) that clobber the left operand.
3800    return right()->HasOneUse();
3801  }
3802
3803  HValue* BetterLeftOperand() {
3804    return AreOperandsBetterSwitched() ? right() : left();
3805  }
3806
3807  HValue* BetterRightOperand() {
3808    return AreOperandsBetterSwitched() ? left() : right();
3809  }
3810
3811  void set_observed_input_representation(int index, Representation rep) {
3812    DCHECK(index >= 1 && index <= 2);
3813    observed_input_representation_[index - 1] = rep;
3814  }
3815
3816  virtual void initialize_output_representation(Representation observed) {
3817    observed_output_representation_ = observed;
3818  }
3819
3820  virtual Representation observed_input_representation(int index) OVERRIDE {
3821    if (index == 0) return Representation::Tagged();
3822    return observed_input_representation_[index - 1];
3823  }
3824
3825  virtual void UpdateRepresentation(Representation new_rep,
3826                                    HInferRepresentationPhase* h_infer,
3827                                    const char* reason) OVERRIDE {
3828    Representation rep = !FLAG_smi_binop && new_rep.IsSmi()
3829        ? Representation::Integer32() : new_rep;
3830    HValue::UpdateRepresentation(rep, h_infer, reason);
3831  }
3832
3833  virtual void InferRepresentation(
3834      HInferRepresentationPhase* h_infer) OVERRIDE;
3835  virtual Representation RepresentationFromInputs() OVERRIDE;
3836  Representation RepresentationFromOutput();
3837  virtual void AssumeRepresentation(Representation r) OVERRIDE;
3838
3839  virtual bool IsCommutative() const { return false; }
3840
3841  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
3842
3843  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
3844    if (index == 0) return Representation::Tagged();
3845    return representation();
3846  }
3847
3848  void SetOperandPositions(Zone* zone,
3849                           HSourcePosition left_pos,
3850                           HSourcePosition right_pos) {
3851    set_operand_position(zone, 1, left_pos);
3852    set_operand_position(zone, 2, right_pos);
3853  }
3854
3855  bool RightIsPowerOf2() {
3856    if (!right()->IsInteger32Constant()) return false;
3857    int32_t value = right()->GetInteger32Constant();
3858    if (value < 0) {
3859      return base::bits::IsPowerOfTwo32(static_cast<uint32_t>(-value));
3860    }
3861    return base::bits::IsPowerOfTwo32(static_cast<uint32_t>(value));
3862  }
3863
3864  DECLARE_ABSTRACT_INSTRUCTION(BinaryOperation)
3865
3866 private:
3867  bool IgnoreObservedOutputRepresentation(Representation current_rep);
3868
3869  Representation observed_input_representation_[2];
3870  Representation observed_output_representation_;
3871};
3872
3873
3874class HWrapReceiver FINAL : public HTemplateInstruction<2> {
3875 public:
3876  DECLARE_INSTRUCTION_FACTORY_P2(HWrapReceiver, HValue*, HValue*);
3877
3878  virtual bool DataEquals(HValue* other) OVERRIDE { return true; }
3879
3880  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
3881    return Representation::Tagged();
3882  }
3883
3884  HValue* receiver() const { return OperandAt(0); }
3885  HValue* function() const { return OperandAt(1); }
3886
3887  virtual HValue* Canonicalize() OVERRIDE;
3888
3889  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
3890  bool known_function() const { return known_function_; }
3891
3892  DECLARE_CONCRETE_INSTRUCTION(WrapReceiver)
3893
3894 private:
3895  HWrapReceiver(HValue* receiver, HValue* function) {
3896    known_function_ = function->IsConstant() &&
3897        HConstant::cast(function)->handle(function->isolate())->IsJSFunction();
3898    set_representation(Representation::Tagged());
3899    SetOperandAt(0, receiver);
3900    SetOperandAt(1, function);
3901    SetFlag(kUseGVN);
3902  }
3903
3904  bool known_function_;
3905};
3906
3907
3908class HApplyArguments FINAL : public HTemplateInstruction<4> {
3909 public:
3910  DECLARE_INSTRUCTION_FACTORY_P4(HApplyArguments, HValue*, HValue*, HValue*,
3911                                 HValue*);
3912
3913  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
3914    // The length is untagged, all other inputs are tagged.
3915    return (index == 2)
3916        ? Representation::Integer32()
3917        : Representation::Tagged();
3918  }
3919
3920  HValue* function() { return OperandAt(0); }
3921  HValue* receiver() { return OperandAt(1); }
3922  HValue* length() { return OperandAt(2); }
3923  HValue* elements() { return OperandAt(3); }
3924
3925  DECLARE_CONCRETE_INSTRUCTION(ApplyArguments)
3926
3927 private:
3928  HApplyArguments(HValue* function,
3929                  HValue* receiver,
3930                  HValue* length,
3931                  HValue* elements) {
3932    set_representation(Representation::Tagged());
3933    SetOperandAt(0, function);
3934    SetOperandAt(1, receiver);
3935    SetOperandAt(2, length);
3936    SetOperandAt(3, elements);
3937    SetAllSideEffects();
3938  }
3939};
3940
3941
3942class HArgumentsElements FINAL : public HTemplateInstruction<0> {
3943 public:
3944  DECLARE_INSTRUCTION_FACTORY_P1(HArgumentsElements, bool);
3945
3946  DECLARE_CONCRETE_INSTRUCTION(ArgumentsElements)
3947
3948  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
3949    return Representation::None();
3950  }
3951
3952  bool from_inlined() const { return from_inlined_; }
3953
3954 protected:
3955  virtual bool DataEquals(HValue* other) OVERRIDE { return true; }
3956
3957 private:
3958  explicit HArgumentsElements(bool from_inlined) : from_inlined_(from_inlined) {
3959    // The value produced by this instruction is a pointer into the stack
3960    // that looks as if it was a smi because of alignment.
3961    set_representation(Representation::Tagged());
3962    SetFlag(kUseGVN);
3963  }
3964
3965  virtual bool IsDeletable() const OVERRIDE { return true; }
3966
3967  bool from_inlined_;
3968};
3969
3970
3971class HArgumentsLength FINAL : public HUnaryOperation {
3972 public:
3973  DECLARE_INSTRUCTION_FACTORY_P1(HArgumentsLength, HValue*);
3974
3975  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
3976    return Representation::Tagged();
3977  }
3978
3979  DECLARE_CONCRETE_INSTRUCTION(ArgumentsLength)
3980
3981 protected:
3982  virtual bool DataEquals(HValue* other) OVERRIDE { return true; }
3983
3984 private:
3985  explicit HArgumentsLength(HValue* value) : HUnaryOperation(value) {
3986    set_representation(Representation::Integer32());
3987    SetFlag(kUseGVN);
3988  }
3989
3990  virtual bool IsDeletable() const OVERRIDE { return true; }
3991};
3992
3993
3994class HAccessArgumentsAt FINAL : public HTemplateInstruction<3> {
3995 public:
3996  DECLARE_INSTRUCTION_FACTORY_P3(HAccessArgumentsAt, HValue*, HValue*, HValue*);
3997
3998  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
3999
4000  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
4001    // The arguments elements is considered tagged.
4002    return index == 0
4003        ? Representation::Tagged()
4004        : Representation::Integer32();
4005  }
4006
4007  HValue* arguments() const { return OperandAt(0); }
4008  HValue* length() const { return OperandAt(1); }
4009  HValue* index() const { return OperandAt(2); }
4010
4011  DECLARE_CONCRETE_INSTRUCTION(AccessArgumentsAt)
4012
4013 private:
4014  HAccessArgumentsAt(HValue* arguments, HValue* length, HValue* index) {
4015    set_representation(Representation::Tagged());
4016    SetFlag(kUseGVN);
4017    SetOperandAt(0, arguments);
4018    SetOperandAt(1, length);
4019    SetOperandAt(2, index);
4020  }
4021
4022  virtual bool DataEquals(HValue* other) OVERRIDE { return true; }
4023};
4024
4025
4026class HBoundsCheckBaseIndexInformation;
4027
4028
4029class HBoundsCheck FINAL : public HTemplateInstruction<2> {
4030 public:
4031  DECLARE_INSTRUCTION_FACTORY_P2(HBoundsCheck, HValue*, HValue*);
4032
4033  bool skip_check() const { return skip_check_; }
4034  void set_skip_check() { skip_check_ = true; }
4035
4036  HValue* base() const { return base_; }
4037  int offset() const { return offset_; }
4038  int scale() const { return scale_; }
4039
4040  void ApplyIndexChange();
4041  bool DetectCompoundIndex() {
4042    DCHECK(base() == NULL);
4043
4044    DecompositionResult decomposition;
4045    if (index()->TryDecompose(&decomposition)) {
4046      base_ = decomposition.base();
4047      offset_ = decomposition.offset();
4048      scale_ = decomposition.scale();
4049      return true;
4050    } else {
4051      base_ = index();
4052      offset_ = 0;
4053      scale_ = 0;
4054      return false;
4055    }
4056  }
4057
4058  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
4059    return representation();
4060  }
4061
4062  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
4063  virtual void InferRepresentation(
4064      HInferRepresentationPhase* h_infer) OVERRIDE;
4065
4066  HValue* index() const { return OperandAt(0); }
4067  HValue* length() const { return OperandAt(1); }
4068  bool allow_equality() const { return allow_equality_; }
4069  void set_allow_equality(bool v) { allow_equality_ = v; }
4070
4071  virtual int RedefinedOperandIndex() OVERRIDE { return 0; }
4072  virtual bool IsPurelyInformativeDefinition() OVERRIDE {
4073    return skip_check();
4074  }
4075
4076  DECLARE_CONCRETE_INSTRUCTION(BoundsCheck)
4077
4078 protected:
4079  friend class HBoundsCheckBaseIndexInformation;
4080
4081  virtual Range* InferRange(Zone* zone) OVERRIDE;
4082
4083  virtual bool DataEquals(HValue* other) OVERRIDE { return true; }
4084  bool skip_check_;
4085  HValue* base_;
4086  int offset_;
4087  int scale_;
4088  bool allow_equality_;
4089
4090 private:
4091  // Normally HBoundsCheck should be created using the
4092  // HGraphBuilder::AddBoundsCheck() helper.
4093  // However when building stubs, where we know that the arguments are Int32,
4094  // it makes sense to invoke this constructor directly.
4095  HBoundsCheck(HValue* index, HValue* length)
4096    : skip_check_(false),
4097      base_(NULL), offset_(0), scale_(0),
4098      allow_equality_(false) {
4099    SetOperandAt(0, index);
4100    SetOperandAt(1, length);
4101    SetFlag(kFlexibleRepresentation);
4102    SetFlag(kUseGVN);
4103  }
4104
4105  virtual bool IsDeletable() const OVERRIDE {
4106    return skip_check() && !FLAG_debug_code;
4107  }
4108};
4109
4110
4111class HBoundsCheckBaseIndexInformation FINAL
4112    : public HTemplateInstruction<2> {
4113 public:
4114  explicit HBoundsCheckBaseIndexInformation(HBoundsCheck* check) {
4115    DecompositionResult decomposition;
4116    if (check->index()->TryDecompose(&decomposition)) {
4117      SetOperandAt(0, decomposition.base());
4118      SetOperandAt(1, check);
4119    } else {
4120      UNREACHABLE();
4121    }
4122  }
4123
4124  HValue* base_index() const { return OperandAt(0); }
4125  HBoundsCheck* bounds_check() { return HBoundsCheck::cast(OperandAt(1)); }
4126
4127  DECLARE_CONCRETE_INSTRUCTION(BoundsCheckBaseIndexInformation)
4128
4129  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
4130    return representation();
4131  }
4132
4133  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
4134
4135  virtual int RedefinedOperandIndex() OVERRIDE { return 0; }
4136  virtual bool IsPurelyInformativeDefinition() OVERRIDE { return true; }
4137};
4138
4139
4140class HBitwiseBinaryOperation : public HBinaryOperation {
4141 public:
4142  HBitwiseBinaryOperation(HValue* context, HValue* left, HValue* right,
4143                          HType type = HType::TaggedNumber())
4144      : HBinaryOperation(context, left, right, type) {
4145    SetFlag(kFlexibleRepresentation);
4146    SetFlag(kTruncatingToInt32);
4147    SetFlag(kAllowUndefinedAsNaN);
4148    SetAllSideEffects();
4149  }
4150
4151  virtual void RepresentationChanged(Representation to) OVERRIDE {
4152    if (to.IsTagged() &&
4153        (left()->ToNumberCanBeObserved() || right()->ToNumberCanBeObserved())) {
4154      SetAllSideEffects();
4155      ClearFlag(kUseGVN);
4156    } else {
4157      ClearAllSideEffects();
4158      SetFlag(kUseGVN);
4159    }
4160    if (to.IsTagged()) SetChangesFlag(kNewSpacePromotion);
4161  }
4162
4163  virtual void UpdateRepresentation(Representation new_rep,
4164                                    HInferRepresentationPhase* h_infer,
4165                                    const char* reason) OVERRIDE {
4166    // We only generate either int32 or generic tagged bitwise operations.
4167    if (new_rep.IsDouble()) new_rep = Representation::Integer32();
4168    HBinaryOperation::UpdateRepresentation(new_rep, h_infer, reason);
4169  }
4170
4171  virtual Representation observed_input_representation(int index) OVERRIDE {
4172    Representation r = HBinaryOperation::observed_input_representation(index);
4173    if (r.IsDouble()) return Representation::Integer32();
4174    return r;
4175  }
4176
4177  virtual void initialize_output_representation(Representation observed) {
4178    if (observed.IsDouble()) observed = Representation::Integer32();
4179    HBinaryOperation::initialize_output_representation(observed);
4180  }
4181
4182  DECLARE_ABSTRACT_INSTRUCTION(BitwiseBinaryOperation)
4183
4184 private:
4185  virtual bool IsDeletable() const OVERRIDE { return true; }
4186};
4187
4188
4189class HMathFloorOfDiv FINAL : public HBinaryOperation {
4190 public:
4191  DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P2(HMathFloorOfDiv,
4192                                              HValue*,
4193                                              HValue*);
4194
4195  DECLARE_CONCRETE_INSTRUCTION(MathFloorOfDiv)
4196
4197 protected:
4198  virtual bool DataEquals(HValue* other) OVERRIDE { return true; }
4199
4200 private:
4201  HMathFloorOfDiv(HValue* context, HValue* left, HValue* right)
4202      : HBinaryOperation(context, left, right) {
4203    set_representation(Representation::Integer32());
4204    SetFlag(kUseGVN);
4205    SetFlag(kCanOverflow);
4206    SetFlag(kCanBeDivByZero);
4207    SetFlag(kLeftCanBeMinInt);
4208    SetFlag(kLeftCanBeNegative);
4209    SetFlag(kLeftCanBePositive);
4210    SetFlag(kAllowUndefinedAsNaN);
4211  }
4212
4213  virtual Range* InferRange(Zone* zone) OVERRIDE;
4214
4215  virtual bool IsDeletable() const OVERRIDE { return true; }
4216};
4217
4218
4219class HArithmeticBinaryOperation : public HBinaryOperation {
4220 public:
4221  HArithmeticBinaryOperation(HValue* context, HValue* left, HValue* right)
4222      : HBinaryOperation(context, left, right, HType::TaggedNumber()) {
4223    SetAllSideEffects();
4224    SetFlag(kFlexibleRepresentation);
4225    SetFlag(kAllowUndefinedAsNaN);
4226  }
4227
4228  virtual void RepresentationChanged(Representation to) OVERRIDE {
4229    if (to.IsTagged() &&
4230        (left()->ToNumberCanBeObserved() || right()->ToNumberCanBeObserved())) {
4231      SetAllSideEffects();
4232      ClearFlag(kUseGVN);
4233    } else {
4234      ClearAllSideEffects();
4235      SetFlag(kUseGVN);
4236    }
4237    if (to.IsTagged()) SetChangesFlag(kNewSpacePromotion);
4238  }
4239
4240  DECLARE_ABSTRACT_INSTRUCTION(ArithmeticBinaryOperation)
4241
4242 private:
4243  virtual bool IsDeletable() const OVERRIDE { return true; }
4244};
4245
4246
4247class HCompareGeneric FINAL : public HBinaryOperation {
4248 public:
4249  DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P3(HCompareGeneric, HValue*,
4250                                              HValue*, Token::Value);
4251
4252  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
4253    return index == 0
4254        ? Representation::Tagged()
4255        : representation();
4256  }
4257
4258  Token::Value token() const { return token_; }
4259  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
4260
4261  DECLARE_CONCRETE_INSTRUCTION(CompareGeneric)
4262
4263 private:
4264  HCompareGeneric(HValue* context,
4265                  HValue* left,
4266                  HValue* right,
4267                  Token::Value token)
4268      : HBinaryOperation(context, left, right, HType::Boolean()),
4269        token_(token) {
4270    DCHECK(Token::IsCompareOp(token));
4271    set_representation(Representation::Tagged());
4272    SetAllSideEffects();
4273  }
4274
4275  Token::Value token_;
4276};
4277
4278
4279class HCompareNumericAndBranch : public HTemplateControlInstruction<2, 2> {
4280 public:
4281  DECLARE_INSTRUCTION_FACTORY_P3(HCompareNumericAndBranch,
4282                                 HValue*, HValue*, Token::Value);
4283  DECLARE_INSTRUCTION_FACTORY_P5(HCompareNumericAndBranch,
4284                                 HValue*, HValue*, Token::Value,
4285                                 HBasicBlock*, HBasicBlock*);
4286
4287  HValue* left() const { return OperandAt(0); }
4288  HValue* right() const { return OperandAt(1); }
4289  Token::Value token() const { return token_; }
4290
4291  void set_observed_input_representation(Representation left,
4292                                         Representation right) {
4293      observed_input_representation_[0] = left;
4294      observed_input_representation_[1] = right;
4295  }
4296
4297  virtual void InferRepresentation(
4298      HInferRepresentationPhase* h_infer) OVERRIDE;
4299
4300  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
4301    return representation();
4302  }
4303  virtual Representation observed_input_representation(int index) OVERRIDE {
4304    return observed_input_representation_[index];
4305  }
4306
4307  virtual bool KnownSuccessorBlock(HBasicBlock** block) OVERRIDE;
4308
4309  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
4310
4311  void SetOperandPositions(Zone* zone,
4312                           HSourcePosition left_pos,
4313                           HSourcePosition right_pos) {
4314    set_operand_position(zone, 0, left_pos);
4315    set_operand_position(zone, 1, right_pos);
4316  }
4317
4318  DECLARE_CONCRETE_INSTRUCTION(CompareNumericAndBranch)
4319
4320 private:
4321  HCompareNumericAndBranch(HValue* left,
4322                           HValue* right,
4323                           Token::Value token,
4324                           HBasicBlock* true_target = NULL,
4325                           HBasicBlock* false_target = NULL)
4326      : token_(token) {
4327    SetFlag(kFlexibleRepresentation);
4328    DCHECK(Token::IsCompareOp(token));
4329    SetOperandAt(0, left);
4330    SetOperandAt(1, right);
4331    SetSuccessorAt(0, true_target);
4332    SetSuccessorAt(1, false_target);
4333  }
4334
4335  Representation observed_input_representation_[2];
4336  Token::Value token_;
4337};
4338
4339
4340class HCompareHoleAndBranch FINAL : public HUnaryControlInstruction {
4341 public:
4342  DECLARE_INSTRUCTION_FACTORY_P1(HCompareHoleAndBranch, HValue*);
4343  DECLARE_INSTRUCTION_FACTORY_P3(HCompareHoleAndBranch, HValue*,
4344                                 HBasicBlock*, HBasicBlock*);
4345
4346  virtual void InferRepresentation(
4347      HInferRepresentationPhase* h_infer) OVERRIDE;
4348
4349  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
4350    return representation();
4351  }
4352
4353  DECLARE_CONCRETE_INSTRUCTION(CompareHoleAndBranch)
4354
4355 private:
4356  HCompareHoleAndBranch(HValue* value,
4357                        HBasicBlock* true_target = NULL,
4358                        HBasicBlock* false_target = NULL)
4359      : HUnaryControlInstruction(value, true_target, false_target) {
4360    SetFlag(kFlexibleRepresentation);
4361    SetFlag(kAllowUndefinedAsNaN);
4362  }
4363};
4364
4365
4366class HCompareMinusZeroAndBranch FINAL : public HUnaryControlInstruction {
4367 public:
4368  DECLARE_INSTRUCTION_FACTORY_P1(HCompareMinusZeroAndBranch, HValue*);
4369
4370  virtual void InferRepresentation(
4371      HInferRepresentationPhase* h_infer) OVERRIDE;
4372
4373  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
4374    return representation();
4375  }
4376
4377  virtual bool KnownSuccessorBlock(HBasicBlock** block) OVERRIDE;
4378
4379  DECLARE_CONCRETE_INSTRUCTION(CompareMinusZeroAndBranch)
4380
4381 private:
4382  explicit HCompareMinusZeroAndBranch(HValue* value)
4383      : HUnaryControlInstruction(value, NULL, NULL) {
4384  }
4385};
4386
4387
4388class HCompareObjectEqAndBranch : public HTemplateControlInstruction<2, 2> {
4389 public:
4390  DECLARE_INSTRUCTION_FACTORY_P2(HCompareObjectEqAndBranch, HValue*, HValue*);
4391  DECLARE_INSTRUCTION_FACTORY_P4(HCompareObjectEqAndBranch, HValue*, HValue*,
4392                                 HBasicBlock*, HBasicBlock*);
4393
4394  virtual bool KnownSuccessorBlock(HBasicBlock** block) OVERRIDE;
4395
4396  static const int kNoKnownSuccessorIndex = -1;
4397  int known_successor_index() const { return known_successor_index_; }
4398  void set_known_successor_index(int known_successor_index) {
4399    known_successor_index_ = known_successor_index;
4400  }
4401
4402  HValue* left() const { return OperandAt(0); }
4403  HValue* right() const { return OperandAt(1); }
4404
4405  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
4406
4407  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
4408    return Representation::Tagged();
4409  }
4410
4411  virtual Representation observed_input_representation(int index) OVERRIDE {
4412    return Representation::Tagged();
4413  }
4414
4415  DECLARE_CONCRETE_INSTRUCTION(CompareObjectEqAndBranch)
4416
4417 private:
4418  HCompareObjectEqAndBranch(HValue* left,
4419                            HValue* right,
4420                            HBasicBlock* true_target = NULL,
4421                            HBasicBlock* false_target = NULL)
4422      : known_successor_index_(kNoKnownSuccessorIndex) {
4423    SetOperandAt(0, left);
4424    SetOperandAt(1, right);
4425    SetSuccessorAt(0, true_target);
4426    SetSuccessorAt(1, false_target);
4427  }
4428
4429  int known_successor_index_;
4430};
4431
4432
4433class HIsObjectAndBranch FINAL : public HUnaryControlInstruction {
4434 public:
4435  DECLARE_INSTRUCTION_FACTORY_P1(HIsObjectAndBranch, HValue*);
4436  DECLARE_INSTRUCTION_FACTORY_P3(HIsObjectAndBranch, HValue*,
4437                                 HBasicBlock*, HBasicBlock*);
4438
4439  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
4440    return Representation::Tagged();
4441  }
4442
4443  virtual bool KnownSuccessorBlock(HBasicBlock** block) OVERRIDE;
4444
4445  DECLARE_CONCRETE_INSTRUCTION(IsObjectAndBranch)
4446
4447 private:
4448  HIsObjectAndBranch(HValue* value,
4449                     HBasicBlock* true_target = NULL,
4450                     HBasicBlock* false_target = NULL)
4451    : HUnaryControlInstruction(value, true_target, false_target) {}
4452};
4453
4454
4455class HIsStringAndBranch FINAL : public HUnaryControlInstruction {
4456 public:
4457  DECLARE_INSTRUCTION_FACTORY_P1(HIsStringAndBranch, HValue*);
4458  DECLARE_INSTRUCTION_FACTORY_P3(HIsStringAndBranch, HValue*,
4459                                 HBasicBlock*, HBasicBlock*);
4460
4461  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
4462    return Representation::Tagged();
4463  }
4464
4465  virtual bool KnownSuccessorBlock(HBasicBlock** block) OVERRIDE;
4466
4467  static const int kNoKnownSuccessorIndex = -1;
4468  int known_successor_index() const { return known_successor_index_; }
4469  void set_known_successor_index(int known_successor_index) {
4470    known_successor_index_ = known_successor_index;
4471  }
4472
4473  DECLARE_CONCRETE_INSTRUCTION(IsStringAndBranch)
4474
4475 protected:
4476  virtual int RedefinedOperandIndex() { return 0; }
4477
4478 private:
4479  HIsStringAndBranch(HValue* value,
4480                     HBasicBlock* true_target = NULL,
4481                     HBasicBlock* false_target = NULL)
4482    : HUnaryControlInstruction(value, true_target, false_target),
4483      known_successor_index_(kNoKnownSuccessorIndex) { }
4484
4485  int known_successor_index_;
4486};
4487
4488
4489class HIsSmiAndBranch FINAL : public HUnaryControlInstruction {
4490 public:
4491  DECLARE_INSTRUCTION_FACTORY_P1(HIsSmiAndBranch, HValue*);
4492  DECLARE_INSTRUCTION_FACTORY_P3(HIsSmiAndBranch, HValue*,
4493                                 HBasicBlock*, HBasicBlock*);
4494
4495  DECLARE_CONCRETE_INSTRUCTION(IsSmiAndBranch)
4496
4497  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
4498    return Representation::Tagged();
4499  }
4500
4501 protected:
4502  virtual bool DataEquals(HValue* other) OVERRIDE { return true; }
4503  virtual int RedefinedOperandIndex() { return 0; }
4504
4505 private:
4506  HIsSmiAndBranch(HValue* value,
4507                  HBasicBlock* true_target = NULL,
4508                  HBasicBlock* false_target = NULL)
4509      : HUnaryControlInstruction(value, true_target, false_target) {
4510    set_representation(Representation::Tagged());
4511  }
4512};
4513
4514
4515class HIsUndetectableAndBranch FINAL : public HUnaryControlInstruction {
4516 public:
4517  DECLARE_INSTRUCTION_FACTORY_P1(HIsUndetectableAndBranch, HValue*);
4518  DECLARE_INSTRUCTION_FACTORY_P3(HIsUndetectableAndBranch, HValue*,
4519                                 HBasicBlock*, HBasicBlock*);
4520
4521  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
4522    return Representation::Tagged();
4523  }
4524
4525  virtual bool KnownSuccessorBlock(HBasicBlock** block) OVERRIDE;
4526
4527  DECLARE_CONCRETE_INSTRUCTION(IsUndetectableAndBranch)
4528
4529 private:
4530  HIsUndetectableAndBranch(HValue* value,
4531                           HBasicBlock* true_target = NULL,
4532                           HBasicBlock* false_target = NULL)
4533      : HUnaryControlInstruction(value, true_target, false_target) {}
4534};
4535
4536
4537class HStringCompareAndBranch : public HTemplateControlInstruction<2, 3> {
4538 public:
4539  DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P3(HStringCompareAndBranch,
4540                                              HValue*,
4541                                              HValue*,
4542                                              Token::Value);
4543
4544  HValue* context() { return OperandAt(0); }
4545  HValue* left() { return OperandAt(1); }
4546  HValue* right() { return OperandAt(2); }
4547  Token::Value token() const { return token_; }
4548
4549  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
4550
4551  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
4552    return Representation::Tagged();
4553  }
4554
4555  Representation GetInputRepresentation() const {
4556    return Representation::Tagged();
4557  }
4558
4559  DECLARE_CONCRETE_INSTRUCTION(StringCompareAndBranch)
4560
4561 private:
4562  HStringCompareAndBranch(HValue* context,
4563                          HValue* left,
4564                          HValue* right,
4565                          Token::Value token)
4566      : token_(token) {
4567    DCHECK(Token::IsCompareOp(token));
4568    SetOperandAt(0, context);
4569    SetOperandAt(1, left);
4570    SetOperandAt(2, right);
4571    set_representation(Representation::Tagged());
4572    SetChangesFlag(kNewSpacePromotion);
4573  }
4574
4575  Token::Value token_;
4576};
4577
4578
4579class HIsConstructCallAndBranch : public HTemplateControlInstruction<2, 0> {
4580 public:
4581  DECLARE_INSTRUCTION_FACTORY_P0(HIsConstructCallAndBranch);
4582
4583  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
4584    return Representation::None();
4585  }
4586
4587  DECLARE_CONCRETE_INSTRUCTION(IsConstructCallAndBranch)
4588 private:
4589  HIsConstructCallAndBranch() {}
4590};
4591
4592
4593class HHasInstanceTypeAndBranch FINAL : public HUnaryControlInstruction {
4594 public:
4595  DECLARE_INSTRUCTION_FACTORY_P2(
4596      HHasInstanceTypeAndBranch, HValue*, InstanceType);
4597  DECLARE_INSTRUCTION_FACTORY_P3(
4598      HHasInstanceTypeAndBranch, HValue*, InstanceType, InstanceType);
4599
4600  InstanceType from() { return from_; }
4601  InstanceType to() { return to_; }
4602
4603  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
4604
4605  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
4606    return Representation::Tagged();
4607  }
4608
4609  virtual bool KnownSuccessorBlock(HBasicBlock** block) OVERRIDE;
4610
4611  DECLARE_CONCRETE_INSTRUCTION(HasInstanceTypeAndBranch)
4612
4613 private:
4614  HHasInstanceTypeAndBranch(HValue* value, InstanceType type)
4615      : HUnaryControlInstruction(value, NULL, NULL), from_(type), to_(type) { }
4616  HHasInstanceTypeAndBranch(HValue* value, InstanceType from, InstanceType to)
4617      : HUnaryControlInstruction(value, NULL, NULL), from_(from), to_(to) {
4618    DCHECK(to == LAST_TYPE);  // Others not implemented yet in backend.
4619  }
4620
4621  InstanceType from_;
4622  InstanceType to_;  // Inclusive range, not all combinations work.
4623};
4624
4625
4626class HHasCachedArrayIndexAndBranch FINAL : public HUnaryControlInstruction {
4627 public:
4628  DECLARE_INSTRUCTION_FACTORY_P1(HHasCachedArrayIndexAndBranch, HValue*);
4629
4630  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
4631    return Representation::Tagged();
4632  }
4633
4634  DECLARE_CONCRETE_INSTRUCTION(HasCachedArrayIndexAndBranch)
4635 private:
4636  explicit HHasCachedArrayIndexAndBranch(HValue* value)
4637      : HUnaryControlInstruction(value, NULL, NULL) { }
4638};
4639
4640
4641class HGetCachedArrayIndex FINAL : public HUnaryOperation {
4642 public:
4643  DECLARE_INSTRUCTION_FACTORY_P1(HGetCachedArrayIndex, HValue*);
4644
4645  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
4646    return Representation::Tagged();
4647  }
4648
4649  DECLARE_CONCRETE_INSTRUCTION(GetCachedArrayIndex)
4650
4651 protected:
4652  virtual bool DataEquals(HValue* other) OVERRIDE { return true; }
4653
4654 private:
4655  explicit HGetCachedArrayIndex(HValue* value) : HUnaryOperation(value) {
4656    set_representation(Representation::Tagged());
4657    SetFlag(kUseGVN);
4658  }
4659
4660  virtual bool IsDeletable() const OVERRIDE { return true; }
4661};
4662
4663
4664class HClassOfTestAndBranch FINAL : public HUnaryControlInstruction {
4665 public:
4666  DECLARE_INSTRUCTION_FACTORY_P2(HClassOfTestAndBranch, HValue*,
4667                                 Handle<String>);
4668
4669  DECLARE_CONCRETE_INSTRUCTION(ClassOfTestAndBranch)
4670
4671  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
4672    return Representation::Tagged();
4673  }
4674
4675  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
4676
4677  Handle<String> class_name() const { return class_name_; }
4678
4679 private:
4680  HClassOfTestAndBranch(HValue* value, Handle<String> class_name)
4681      : HUnaryControlInstruction(value, NULL, NULL),
4682        class_name_(class_name) { }
4683
4684  Handle<String> class_name_;
4685};
4686
4687
4688class HTypeofIsAndBranch FINAL : public HUnaryControlInstruction {
4689 public:
4690  DECLARE_INSTRUCTION_FACTORY_P2(HTypeofIsAndBranch, HValue*, Handle<String>);
4691
4692  Handle<String> type_literal() const { return type_literal_.handle(); }
4693  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
4694
4695  DECLARE_CONCRETE_INSTRUCTION(TypeofIsAndBranch)
4696
4697  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
4698    return Representation::None();
4699  }
4700
4701  virtual bool KnownSuccessorBlock(HBasicBlock** block) OVERRIDE;
4702
4703  virtual void FinalizeUniqueness() OVERRIDE {
4704    type_literal_ = Unique<String>(type_literal_.handle());
4705  }
4706
4707 private:
4708  HTypeofIsAndBranch(HValue* value, Handle<String> type_literal)
4709      : HUnaryControlInstruction(value, NULL, NULL),
4710        type_literal_(Unique<String>::CreateUninitialized(type_literal)) { }
4711
4712  Unique<String> type_literal_;
4713};
4714
4715
4716class HInstanceOf FINAL : public HBinaryOperation {
4717 public:
4718  DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P2(HInstanceOf, HValue*, HValue*);
4719
4720  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
4721    return Representation::Tagged();
4722  }
4723
4724  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
4725
4726  DECLARE_CONCRETE_INSTRUCTION(InstanceOf)
4727
4728 private:
4729  HInstanceOf(HValue* context, HValue* left, HValue* right)
4730      : HBinaryOperation(context, left, right, HType::Boolean()) {
4731    set_representation(Representation::Tagged());
4732    SetAllSideEffects();
4733  }
4734};
4735
4736
4737class HInstanceOfKnownGlobal FINAL : public HTemplateInstruction<2> {
4738 public:
4739  DECLARE_INSTRUCTION_WITH_CONTEXT_FACTORY_P2(HInstanceOfKnownGlobal,
4740                                              HValue*,
4741                                              Handle<JSFunction>);
4742
4743  HValue* context() { return OperandAt(0); }
4744  HValue* left() { return OperandAt(1); }
4745  Handle<JSFunction> function() { return function_; }
4746
4747  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
4748    return Representation::Tagged();
4749  }
4750
4751  DECLARE_CONCRETE_INSTRUCTION(InstanceOfKnownGlobal)
4752
4753 private:
4754  HInstanceOfKnownGlobal(HValue* context,
4755                         HValue* left,
4756                         Handle<JSFunction> right)
4757      : HTemplateInstruction<2>(HType::Boolean()), function_(right) {
4758    SetOperandAt(0, context);
4759    SetOperandAt(1, left);
4760    set_representation(Representation::Tagged());
4761    SetAllSideEffects();
4762  }
4763
4764  Handle<JSFunction> function_;
4765};
4766
4767
4768class HPower FINAL : public HTemplateInstruction<2> {
4769 public:
4770  static HInstruction* New(Zone* zone,
4771                           HValue* context,
4772                           HValue* left,
4773                           HValue* right);
4774
4775  HValue* left() { return OperandAt(0); }
4776  HValue* right() const { return OperandAt(1); }
4777
4778  virtual Representation RequiredInputRepresentation(int index) OVERRIDE {
4779    return index == 0
4780      ? Representation::Double()
4781      : Representation::None();
4782  }
4783  virtual Representation observed_input_representation(int index) OVERRIDE {
4784    return RequiredInputRepresentation(index);
4785  }
4786
4787  DECLARE_CONCRETE_INSTRUCTION(Power)
4788
4789 protected:
4790  virtual bool DataEquals(HValue* other) OVERRIDE { return true; }
4791
4792 private:
4793  HPower(HValue* left, HValue* right) {
4794    SetOperandAt(0, left);
4795    SetOperandAt(1, right);
4796    set_representation(Representation::Double());
4797    SetFlag(kUseGVN);
4798    SetChangesFlag(kNewSpacePromotion);
4799  }
4800
4801  virtual bool IsDeletable() const OVERRIDE {
4802    return !right()->representation().IsTagged();
4803  }
4804};
4805
4806
4807class HAdd FINAL : public HArithmeticBinaryOperation {
4808 public:
4809  static HInstruction* New(Zone* zone,
4810                           HValue* context,
4811                           HValue* left,
4812                           HValue* right);
4813
4814  // Add is only commutative if two integer values are added and not if two
4815  // tagged values are added (because it might be a String concatenation).
4816  // We also do not commute (pointer + offset).
4817  virtual bool IsCommutative() const OVERRIDE {
4818    return !representation().IsTagged() && !representation().IsExternal();
4819  }
4820
4821  virtual HValue* Canonicalize() OVERRIDE;
4822
4823  virtual bool TryDecompose(DecompositionResult* decomposition) OVERRIDE {
4824    if (left()->IsInteger32Constant()) {
4825      decomposition->Apply(right(), left()->GetInteger32Constant());
4826      return true;
4827    } else if (right()->IsInteger32Constant()) {
4828      decomposition->Apply(left(), right()->GetInteger32Constant());
4829      return true;
4830    } else {
4831      return false;
4832    }
4833  }
4834
4835  virtual void RepresentationChanged(Representation to) OVERRIDE {
4836    if (to.IsTagged() &&
4837        (left()->ToNumberCanBeObserved() || right()->ToNumberCanBeObserved() ||
4838         left()->ToStringCanBeObserved() || right()->ToStringCanBeObserved())) {
4839      SetAllSideEffects();
4840      ClearFlag(kUseGVN);
4841    } else {
4842      ClearAllSideEffects();
4843      SetFlag(kUseGVN);
4844    }
4845    if (to.IsTagged()) {
4846      SetChangesFlag(kNewSpacePromotion);
4847      ClearFlag(kAllowUndefinedAsNaN);
4848    }
4849  }
4850
4851  virtual Representation RepresentationFromInputs() OVERRIDE;
4852
4853  virtual Representation RequiredInputRepresentation(int index) OVERRIDE;
4854
4855  DECLARE_CONCRETE_INSTRUCTION(Add)
4856
4857 protected:
4858  virtual bool DataEquals(HValue* other) OVERRIDE { return true; }
4859
4860  virtual Range* InferRange(Zone* zone) OVERRIDE;
4861
4862 private:
4863  HAdd(HValue* context, HValue* left, HValue* right)
4864      : HArithmeticBinaryOperation(context, left, right) {
4865    SetFlag(kCanOverflow);
4866  }
4867};
4868
4869
4870class HSub FINAL : public HArithmeticBinaryOperation {
4871 public:
4872  static HInstruction* New(Zone* zone,
4873                           HValue* context,
4874                           HValue* left,
4875                           HValue* right);
4876
4877  virtual HValue* Canonicalize() OVERRIDE;
4878
4879  virtual bool TryDecompose(DecompositionResult* decomposition) OVERRIDE {
4880    if (right()->IsInteger32Constant()) {
4881      decomposition->Apply(left(), -right()->GetInteger32Constant());
4882      return true;
4883    } else {
4884      return false;
4885    }
4886  }
4887
4888  DECLARE_CONCRETE_INSTRUCTION(Sub)
4889
4890 protected:
4891  virtual bool DataEquals(HValue* other) OVERRIDE { return true; }
4892
4893  virtual Range* InferRange(Zone* zone) OVERRIDE;
4894
4895 private:
4896  HSub(HValue* context, HValue* left, HValue* right)
4897      : HArithmeticBinaryOperation(context, left, right) {
4898    SetFlag(kCanOverflow);
4899  }
4900};
4901
4902
4903class HMul FINAL : public HArithmeticBinaryOperation {
4904 public:
4905  static HInstruction* New(Zone* zone,
4906                           HValue* context,
4907                           HValue* left,
4908                           HValue* right);
4909
4910  static HInstruction* NewImul(Zone* zone,
4911                         HValue* context,
4912                         HValue* left,
4913                         HValue* right) {
4914    HInstruction* instr = HMul::New(zone, context, left, right);
4915    if (!instr->IsMul()) return instr;
4916    HMul* mul = HMul::cast(instr);
4917    // TODO(mstarzinger): Prevent bailout on minus zero for imul.
4918    mul->AssumeRepresentation(Representation::Integer32());
4919    mul->ClearFlag(HValue::kCanOverflow);
4920    return mul;
4921  }
4922
4923  virtual HValue* Canonicalize() OVERRIDE;
4924
4925  // Only commutative if it is certain that not two objects are multiplicated.
4926  virtual bool IsCommutative() const OVERRIDE {
4927    return !representation().IsTagged();
4928  }
4929
4930  virtual void UpdateRepresentation(Representation new_rep,
4931                                    HInferRepresentationPhase* h_infer,
4932                                    const char* reason) OVERRIDE {
4933    HArithmeticBinaryOperation::UpdateRepresentation(new_rep, h_infer, reason);
4934  }
4935
4936  bool MulMinusOne();
4937
4938  DECLARE_CONCRETE_INSTRUCTION(Mul)
4939
4940 protected:
4941  virtual bool DataEquals(HValue* other) OVERRIDE { return true; }
4942
4943  virtual Range* InferRange(Zone* zone) OVERRIDE;
4944
4945 private:
4946  HMul(HValue* context, HValue* left, HValue* right)
4947      : HArithmeticBinaryOperation(context, left, right) {
4948    SetFlag(kCanOverflow);
4949  }
4950};
4951
4952
4953class HMod 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() OVERRIDE;
4961
4962  virtual void UpdateRepresentation(Representation new_rep,
4963                                    HInferRepresentationPhase* h_infer,
4964                                    const char* reason) OVERRIDE {
4965    if (new_rep.IsSmi()) new_rep = Representation::Integer32();
4966    HArithmeticBinaryOperation::UpdateRepresentation(new_rep, h_infer, reason);
4967  }
4968
4969  DECLARE_CONCRETE_INSTRUCTION(Mod)
4970
4971 protected:
4972  virtual bool DataEquals(HValue* other) OVERRIDE { return true; }
4973
4974  virtual Range* InferRange(Zone* zone) OVERRIDE;
4975
4976 private:
4977  HMod(HValue* context,
4978       HValue* left,
4979       HValue* right) : HArithmeticBinaryOperation(context, left, right) {
4980    SetFlag(kCanBeDivByZero);
4981    SetFlag(kCanOverflow);
4982    SetFlag(kLeftCanBeNegative);
4983  }
4984};
4985
4986
4987class HDiv FINAL : public HArithmeticBinaryOperation {
4988 public:
4989  static HInstruction* New(Zone* zone,
4990                           HValue* context,
4991                           HValue* left,
4992                           HValue* right);
4993
4994  virtual HValue* Canonicalize() OVERRIDE;
4995
4996  virtual void UpdateRepresentation(Representation new_rep,
4997                                    HInferRepresentationPhase* h_infer,
4998                                    const char* reason) OVERRIDE {
4999    if (new_rep.IsSmi()) new_rep = Representation::Integer32();
5000    HArithmeticBinaryOperation::UpdateRepresentation(new_rep, h_infer, reason);
5001  }
5002
5003  DECLARE_CONCRETE_INSTRUCTION(Div)
5004
5005 protected:
5006  virtual bool DataEquals(HValue* other) OVERRIDE { return true; }
5007
5008  virtual Range* InferRange(Zone* zone) OVERRIDE;
5009
5010 private:
5011  HDiv(HValue* context, HValue* left, HValue* right)
5012      : HArithmeticBinaryOperation(context, left, right) {
5013    SetFlag(kCanBeDivByZero);
5014    SetFlag(kCanOverflow);
5015  }
5016};
5017
5018
5019class HMathMinMax FINAL : public HArithmeticBinaryOperation {
5020 public:
5021  enum Operation { kMathMin, kMathMax };
5022
5023  static HInstruction* New(Zone* zone,
5024                           HValue* context,
5025                           HValue* left,
5026                           HValue* right,
5027                           Operation op);
5028
5029  virtual Representation observed_input_representation(int index) OVERRIDE {
5030    return RequiredInputRepresentation(index);
5031  }
5032
5033  virtual void InferRepresentation(
5034      HInferRepresentationPhase* h_infer) OVERRIDE;
5035
5036  virtual Representation RepresentationFromInputs() OVERRIDE {
5037    Representation left_rep = left()->representation();
5038    Representation right_rep = right()->representation();
5039    Representation result = Representation::Smi();
5040    result = result.generalize(left_rep);
5041    result = result.generalize(right_rep);
5042    if (result.IsTagged()) return Representation::Double();
5043    return result;
5044  }
5045
5046  virtual bool IsCommutative() const OVERRIDE { return true; }
5047
5048  Operation operation() { return operation_; }
5049
5050  DECLARE_CONCRETE_INSTRUCTION(MathMinMax)
5051
5052 protected:
5053  virtual bool DataEquals(HValue* other) OVERRIDE {
5054    return other->IsMathMinMax() &&
5055        HMathMinMax::cast(other)->operation_ == operation_;
5056  }
5057
5058  virtual Range* InferRange(Zone* zone) OVERRIDE;
5059
5060 private:
5061  HMathMinMax(HValue* context, HValue* left, HValue* right, Operation op)
5062      : HArithmeticBinaryOperation(context, left, right),
5063        operation_(op) { }
5064
5065  Operation operation_;
5066};
5067
5068
5069class HBitwise FINAL : public HBitwiseBinaryOperation {
5070 public:
5071  static HInstruction* New(Zone* zone,
5072                           HValue* context,
5073                           Token::Value op,
5074                           HValue* left,
5075                           HValue* right);
5076
5077  Token::Value op() const { return op_; }
5078
5079  virtual bool IsCommutative() const OVERRIDE { return true; }
5080
5081  virtual HValue* Canonicalize() OVERRIDE;
5082
5083  virtual OStream& PrintDataTo(OStream& os) const OVERRIDE;  // NOLINT
5084
5085  DECLARE_CONCRETE_INSTRUCTION(Bitwise)
5086
5087 protected:
5088  virtual bool DataEquals(HValue* other) OVERRIDE {
5089    return op() == HBitwise::cast(other)->op();
5090  }
5091
5092  virtual Range* InferRange(Zone* zone) OVERRIDE;
5093
5094 private:
5095  HBitwise(HValue* context,
5096           Token::Value op,
5097           HValue* left,
5098           HValue* right)
5099      : HBitwiseBinaryOperation(context, left, right),
5100        op_(op) {
5101    DCHECK(op == Token::BIT_AND || op == Token::BIT_OR || op == Token::BIT_XOR);
5102    // BIT_AND with a smi-range positive value will always unset the
5103    // entire sign-extension of the smi-sign.
5104    if (op == Token::BIT_AND &&
5105        ((left->IsConstant() &&
5106          left->representation().IsSmi() &&
5107          HConstant::cast(left)->Integer32Value() >= 0) ||
5108         (right->IsConstant() &&
5109          right->representation().IsSmi() &&
5110          HConstant::cast(right)->Integer32Value() >= 0))) {
5111      SetFlag(kTruncatingToSmi);
5112      SetFlag(kTruncatingToInt32);
5113    // BIT_OR with a smi-range negative value will always set the entire
5114    // sign-extension of the smi-sign.
5115    } else if (op == Token::BIT_OR &&
5116        ((left->IsConstant() &&
5117          left->representation().IsSmi() &&
5118          HConstant::cast(left)->Integer32Value() < 0) ||
5119         (right->IsConstant() &&
5120          right->representation().IsSmi() &&
5121          HConstant::cast(right)->Integer32Value() < 0))) {
5122      SetFlag(kTruncatingToSmi);
5123      SetFlag(kTruncatingToInt32);
5124    }
5125  }
5126
5127  Token::Value op_;
5128};
5129
5130
5131class HShl FINAL : public HBitwiseBinaryOperation {
5132 public:
5133  static HInstruction* New(Zone* zone,
5134                           HValue* context,
5135                           HValue* left,
5136                           HValue* right);
5137
5138  virtual Range* InferRange(Zone* zone) OVERRIDE;
5139
5140  virtual void UpdateRepresentation(Representation new_rep,
5141                                    HInferRepresentationPhase* h_infer,
5142                                    const char* reason) OVERRIDE {
5143    if (new_rep.IsSmi() &&
5144        !(right()->IsInteger32Constant() &&
5145          right()->GetInteger32Constant() >= 0)) {
5146      new_rep = Representation::Integer32();
5147    }
5148    HBitwiseBinaryOperation::UpdateRepresentation(new_rep, h_infer, reason);
5149  }
5150
5151  DECLARE_CONCRETE_INSTRUCTION(Shl)
5152
5153 protected:
5154  virtual bool DataEquals(HValue* other) OVERRIDE { return true; }
5155
5156 private:
5157  HShl(HValue* context, HValue* left, HValue* right)
5158      : HBitwiseBinaryOperation(context, left, right) { }
5159};
5160
5161
5162class HShr FINAL : public HBitwiseBinaryOperation {
5163 public:
5164  static HInstruction* New(Zone* zone,
5165                           HValue* context,
5166                           HValue* left,
5167                           HValue* right);
5168
5169  virtual bool TryDecompose(DecompositionResult* decomposition) OVERRIDE {
5170    if (right()->IsInteger32Constant()) {
5171      if (decomposition->Apply(left(), 0, right()->GetInteger32Constant())) {
5172        // This is intended to look for HAdd and HSub, to handle compounds
5173        // like ((base + offset) >> scale) with one single decomposition.
5174        left()->TryDecompose(decomposition);
5175        return true;
5176      }
5177    }
5178    return false;
5179  }
5180
5181  virtual Range* InferRange(Zone* zone) OVERRIDE;
5182
5183  virtual void UpdateRepresentation(Representation new_rep,
5184                                    HInferRepresentationPhase* h_infer,
5185                                    const char* reason) OVERRIDE {
5186    if (new_rep.IsSmi()) new_rep = Representation::Integer32();
5187    HBitwiseBinaryOperation::UpdateRepresentation(new_rep, h_infer, reason);
5188  }
5189
5190  DECLARE_CONCRETE_INSTRUCTION(Shr)
5191
5192 protected:
5193  virtual bool DataEquals(HValue* other) OVERRIDE { return true; }
5194
5195 private:
5196  HShr(HValue* context, HValue* left, HValue* right)
5197      : HBitwiseBinaryOperation(context, left, right) { }
5198};
5199
5200
5201class HSar FINAL : public HBitwiseBinaryOperation {
5202 public:
5203  static HInstruction* New(Zone* zone,
5204                           HValue* context,
5205                           HValue* left,
5206                           HVa