1// Copyright 2011 the V8 project authors. All rights reserved.
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions are
4// met:
5//
6//     * Redistributions of source code must retain the above copyright
7//       notice, this list of conditions and the following disclaimer.
8//     * Redistributions in binary form must reproduce the above
9//       copyright notice, this list of conditions and the following
10//       disclaimer in the documentation and/or other materials provided
11//       with the distribution.
12//     * Neither the name of Google Inc. nor the names of its
13//       contributors may be used to endorse or promote products derived
14//       from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28#ifndef V8_HYDROGEN_INSTRUCTIONS_H_
29#define V8_HYDROGEN_INSTRUCTIONS_H_
30
31#include "v8.h"
32
33#include "code-stubs.h"
34#include "small-pointer-list.h"
35#include "string-stream.h"
36#include "zone.h"
37
38namespace v8 {
39namespace internal {
40
41// Forward declarations.
42class HBasicBlock;
43class HEnvironment;
44class HInstruction;
45class HLoopInformation;
46class HValue;
47class LInstruction;
48class LChunkBuilder;
49
50
51#define HYDROGEN_ALL_INSTRUCTION_LIST(V)       \
52  V(ArithmeticBinaryOperation)                 \
53  V(BinaryCall)                                \
54  V(BinaryOperation)                           \
55  V(BitwiseBinaryOperation)                    \
56  V(ControlInstruction)                        \
57  V(Instruction)                               \
58  V(Phi)                                       \
59  V(UnaryCall)                                 \
60  V(UnaryControlInstruction)                   \
61  V(UnaryOperation)                            \
62  HYDROGEN_CONCRETE_INSTRUCTION_LIST(V)
63
64
65#define HYDROGEN_CONCRETE_INSTRUCTION_LIST(V)  \
66  V(AbnormalExit)                              \
67  V(AccessArgumentsAt)                         \
68  V(Add)                                       \
69  V(ApplyArguments)                            \
70  V(ArgumentsElements)                         \
71  V(ArgumentsLength)                           \
72  V(ArgumentsObject)                           \
73  V(ArrayLiteral)                              \
74  V(BitAnd)                                    \
75  V(BitNot)                                    \
76  V(BitOr)                                     \
77  V(BitXor)                                    \
78  V(BlockEntry)                                \
79  V(BoundsCheck)                               \
80  V(CallConstantFunction)                      \
81  V(CallFunction)                              \
82  V(CallGlobal)                                \
83  V(CallKeyed)                                 \
84  V(CallKnownGlobal)                           \
85  V(CallNamed)                                 \
86  V(CallNew)                                   \
87  V(CallRuntime)                               \
88  V(CallStub)                                  \
89  V(Change)                                    \
90  V(CheckFunction)                             \
91  V(CheckInstanceType)                         \
92  V(CheckMap)                                  \
93  V(CheckNonSmi)                               \
94  V(CheckPrototypeMaps)                        \
95  V(CheckSmi)                                  \
96  V(ClassOfTest)                               \
97  V(Compare)                                   \
98  V(CompareJSObjectEq)                         \
99  V(CompareMap)                                \
100  V(Constant)                                  \
101  V(Context)                                   \
102  V(DeleteProperty)                            \
103  V(Deoptimize)                                \
104  V(Div)                                       \
105  V(EnterInlined)                              \
106  V(ExternalArrayLength)                       \
107  V(FixedArrayLength)                          \
108  V(FunctionLiteral)                           \
109  V(GetCachedArrayIndex)                       \
110  V(GlobalObject)                              \
111  V(GlobalReceiver)                            \
112  V(Goto)                                      \
113  V(HasInstanceType)                           \
114  V(HasCachedArrayIndex)                       \
115  V(InstanceOf)                                \
116  V(InstanceOfKnownGlobal)                     \
117  V(IsNull)                                    \
118  V(IsObject)                                  \
119  V(IsSmi)                                     \
120  V(IsConstructCall)                           \
121  V(JSArrayLength)                             \
122  V(LeaveInlined)                              \
123  V(LoadContextSlot)                           \
124  V(LoadElements)                              \
125  V(LoadExternalArrayPointer)                  \
126  V(LoadFunctionPrototype)                     \
127  V(LoadGlobalCell)                            \
128  V(LoadGlobalGeneric)                         \
129  V(LoadKeyedFastElement)                      \
130  V(LoadKeyedGeneric)                          \
131  V(LoadKeyedSpecializedArrayElement)          \
132  V(LoadNamedField)                            \
133  V(LoadNamedFieldPolymorphic)                 \
134  V(LoadNamedGeneric)                          \
135  V(Mod)                                       \
136  V(Mul)                                       \
137  V(ObjectLiteral)                             \
138  V(OsrEntry)                                  \
139  V(OuterContext)                              \
140  V(Parameter)                                 \
141  V(Power)                                     \
142  V(PushArgument)                              \
143  V(RegExpLiteral)                             \
144  V(Return)                                    \
145  V(Sar)                                       \
146  V(Shl)                                       \
147  V(Shr)                                       \
148  V(Simulate)                                  \
149  V(StackCheck)                                \
150  V(StoreContextSlot)                          \
151  V(StoreGlobalCell)                           \
152  V(StoreGlobalGeneric)                        \
153  V(StoreKeyedFastElement)                     \
154  V(StoreKeyedSpecializedArrayElement)         \
155  V(StoreKeyedGeneric)                         \
156  V(StoreNamedField)                           \
157  V(StoreNamedGeneric)                         \
158  V(StringCharCodeAt)                          \
159  V(StringCharFromCode)                        \
160  V(StringLength)                              \
161  V(Sub)                                       \
162  V(Test)                                      \
163  V(Throw)                                     \
164  V(ToFastProperties)                          \
165  V(Typeof)                                    \
166  V(TypeofIs)                                  \
167  V(UnaryMathOperation)                        \
168  V(UnknownOSRValue)                           \
169  V(ValueOf)
170
171#define GVN_FLAG_LIST(V)                       \
172  V(Calls)                                     \
173  V(InobjectFields)                            \
174  V(BackingStoreFields)                        \
175  V(ArrayElements)                             \
176  V(SpecializedArrayElements)                  \
177  V(GlobalVars)                                \
178  V(Maps)                                      \
179  V(ArrayLengths)                              \
180  V(ContextSlots)                              \
181  V(OsrEntries)
182
183#define DECLARE_INSTRUCTION(type)                   \
184  virtual bool Is##type() const { return true; }    \
185  static H##type* cast(HValue* value) {             \
186    ASSERT(value->Is##type());                      \
187    return reinterpret_cast<H##type*>(value);       \
188  }                                                 \
189  Opcode opcode() const { return HValue::k##type; }
190
191
192#define DECLARE_CONCRETE_INSTRUCTION(type, mnemonic)              \
193  virtual LInstruction* CompileToLithium(LChunkBuilder* builder); \
194  virtual const char* Mnemonic() const { return mnemonic; }       \
195  DECLARE_INSTRUCTION(type)
196
197
198class Range: public ZoneObject {
199 public:
200  Range()
201      : lower_(kMinInt),
202        upper_(kMaxInt),
203        next_(NULL),
204        can_be_minus_zero_(false) { }
205
206  Range(int32_t lower, int32_t upper)
207      : lower_(lower),
208        upper_(upper),
209        next_(NULL),
210        can_be_minus_zero_(false) { }
211
212  int32_t upper() const { return upper_; }
213  int32_t lower() const { return lower_; }
214  Range* next() const { return next_; }
215  Range* CopyClearLower() const { return new Range(kMinInt, upper_); }
216  Range* CopyClearUpper() const { return new Range(lower_, kMaxInt); }
217  Range* Copy() const { return new Range(lower_, upper_); }
218  int32_t Mask() const;
219  void set_can_be_minus_zero(bool b) { can_be_minus_zero_ = b; }
220  bool CanBeMinusZero() const { return CanBeZero() && can_be_minus_zero_; }
221  bool CanBeZero() const { return upper_ >= 0 && lower_ <= 0; }
222  bool CanBeNegative() const { return lower_ < 0; }
223  bool Includes(int value) const { return lower_ <= value && upper_ >= value; }
224  bool IsMostGeneric() const { return lower_ == kMinInt && upper_ == kMaxInt; }
225  bool IsInSmiRange() const {
226    return lower_ >= Smi::kMinValue && upper_ <= Smi::kMaxValue;
227  }
228  void KeepOrder();
229  void Verify() const;
230
231  void StackUpon(Range* other) {
232    Intersect(other);
233    next_ = other;
234  }
235
236  void Intersect(Range* other);
237  void Union(Range* other);
238
239  void AddConstant(int32_t value);
240  void Sar(int32_t value);
241  void Shl(int32_t value);
242  bool AddAndCheckOverflow(Range* other);
243  bool SubAndCheckOverflow(Range* other);
244  bool MulAndCheckOverflow(Range* other);
245
246 private:
247  int32_t lower_;
248  int32_t upper_;
249  Range* next_;
250  bool can_be_minus_zero_;
251};
252
253
254class Representation {
255 public:
256  enum Kind {
257    kNone,
258    kTagged,
259    kDouble,
260    kInteger32,
261    kExternal,
262    kNumRepresentations
263  };
264
265  Representation() : kind_(kNone) { }
266
267  static Representation None() { return Representation(kNone); }
268  static Representation Tagged() { return Representation(kTagged); }
269  static Representation Integer32() { return Representation(kInteger32); }
270  static Representation Double() { return Representation(kDouble); }
271  static Representation External() { return Representation(kExternal); }
272
273  bool Equals(const Representation& other) {
274    return kind_ == other.kind_;
275  }
276
277  Kind kind() const { return static_cast<Kind>(kind_); }
278  bool IsNone() const { return kind_ == kNone; }
279  bool IsTagged() const { return kind_ == kTagged; }
280  bool IsInteger32() const { return kind_ == kInteger32; }
281  bool IsDouble() const { return kind_ == kDouble; }
282  bool IsExternal() const { return kind_ == kExternal; }
283  bool IsSpecialization() const {
284    return kind_ == kInteger32 || kind_ == kDouble;
285  }
286  const char* Mnemonic() const;
287
288 private:
289  explicit Representation(Kind k) : kind_(k) { }
290
291  // Make sure kind fits in int8.
292  STATIC_ASSERT(kNumRepresentations <= (1 << kBitsPerByte));
293
294  int8_t kind_;
295};
296
297
298class HType {
299 public:
300  HType() : type_(kUninitialized) { }
301
302  static HType Tagged() { return HType(kTagged); }
303  static HType TaggedPrimitive() { return HType(kTaggedPrimitive); }
304  static HType TaggedNumber() { return HType(kTaggedNumber); }
305  static HType Smi() { return HType(kSmi); }
306  static HType HeapNumber() { return HType(kHeapNumber); }
307  static HType String() { return HType(kString); }
308  static HType Boolean() { return HType(kBoolean); }
309  static HType NonPrimitive() { return HType(kNonPrimitive); }
310  static HType JSArray() { return HType(kJSArray); }
311  static HType JSObject() { return HType(kJSObject); }
312  static HType Uninitialized() { return HType(kUninitialized); }
313
314  // Return the weakest (least precise) common type.
315  HType Combine(HType other) {
316    return HType(static_cast<Type>(type_ & other.type_));
317  }
318
319  bool Equals(const HType& other) {
320    return type_ == other.type_;
321  }
322
323  bool IsSubtypeOf(const HType& other) {
324    return Combine(other).Equals(other);
325  }
326
327  bool IsTagged() {
328    ASSERT(type_ != kUninitialized);
329    return ((type_ & kTagged) == kTagged);
330  }
331
332  bool IsTaggedPrimitive() {
333    ASSERT(type_ != kUninitialized);
334    return ((type_ & kTaggedPrimitive) == kTaggedPrimitive);
335  }
336
337  bool IsTaggedNumber() {
338    ASSERT(type_ != kUninitialized);
339    return ((type_ & kTaggedNumber) == kTaggedNumber);
340  }
341
342  bool IsSmi() {
343    ASSERT(type_ != kUninitialized);
344    return ((type_ & kSmi) == kSmi);
345  }
346
347  bool IsHeapNumber() {
348    ASSERT(type_ != kUninitialized);
349    return ((type_ & kHeapNumber) == kHeapNumber);
350  }
351
352  bool IsString() {
353    ASSERT(type_ != kUninitialized);
354    return ((type_ & kString) == kString);
355  }
356
357  bool IsBoolean() {
358    ASSERT(type_ != kUninitialized);
359    return ((type_ & kBoolean) == kBoolean);
360  }
361
362  bool IsNonPrimitive() {
363    ASSERT(type_ != kUninitialized);
364    return ((type_ & kNonPrimitive) == kNonPrimitive);
365  }
366
367  bool IsJSArray() {
368    ASSERT(type_ != kUninitialized);
369    return ((type_ & kJSArray) == kJSArray);
370  }
371
372  bool IsJSObject() {
373    ASSERT(type_ != kUninitialized);
374    return ((type_ & kJSObject) == kJSObject);
375  }
376
377  bool IsUninitialized() {
378    return type_ == kUninitialized;
379  }
380
381  static HType TypeFromValue(Handle<Object> value);
382
383  const char* ToString();
384  const char* ToShortString();
385
386 private:
387  enum Type {
388    kTagged = 0x1,           // 0000 0000 0000 0001
389    kTaggedPrimitive = 0x5,  // 0000 0000 0000 0101
390    kTaggedNumber = 0xd,     // 0000 0000 0000 1101
391    kSmi = 0x1d,             // 0000 0000 0001 1101
392    kHeapNumber = 0x2d,      // 0000 0000 0010 1101
393    kString = 0x45,          // 0000 0000 0100 0101
394    kBoolean = 0x85,         // 0000 0000 1000 0101
395    kNonPrimitive = 0x101,   // 0000 0001 0000 0001
396    kJSObject = 0x301,       // 0000 0011 0000 0001
397    kJSArray = 0x701,        // 0000 0111 1000 0001
398    kUninitialized = 0x1fff  // 0001 1111 1111 1111
399  };
400
401  // Make sure type fits in int16.
402  STATIC_ASSERT(kUninitialized < (1 << (2 * kBitsPerByte)));
403
404  explicit HType(Type t) : type_(t) { }
405
406  int16_t type_;
407};
408
409
410class HValue: public ZoneObject {
411 public:
412  static const int kNoNumber = -1;
413
414  // There must be one corresponding kDepends flag for every kChanges flag and
415  // the order of the kChanges flags must be exactly the same as of the kDepends
416  // flags.
417  enum Flag {
418    // Declare global value numbering flags.
419  #define DECLARE_DO(type) kChanges##type, kDependsOn##type,
420    GVN_FLAG_LIST(DECLARE_DO)
421  #undef DECLARE_DO
422    kFlexibleRepresentation,
423    kUseGVN,
424    kCanOverflow,
425    kBailoutOnMinusZero,
426    kCanBeDivByZero,
427    kDeoptimizeOnUndefined,
428    kIsArguments,
429    kTruncatingToInt32,
430    kLastFlag = kTruncatingToInt32
431  };
432
433  STATIC_ASSERT(kLastFlag < kBitsPerInt);
434
435  static const int kChangesToDependsFlagsLeftShift = 1;
436
437  static int ChangesFlagsMask() {
438    int result = 0;
439    // Create changes mask.
440#define DECLARE_DO(type) result |= (1 << kChanges##type);
441  GVN_FLAG_LIST(DECLARE_DO)
442#undef DECLARE_DO
443    return result;
444  }
445
446  static int DependsFlagsMask() {
447    return ConvertChangesToDependsFlags(ChangesFlagsMask());
448  }
449
450  static int ConvertChangesToDependsFlags(int flags) {
451    return flags << kChangesToDependsFlagsLeftShift;
452  }
453
454  static HValue* cast(HValue* value) { return value; }
455
456  enum Opcode {
457    // Declare a unique enum value for each hydrogen instruction.
458  #define DECLARE_DO(type) k##type,
459    HYDROGEN_ALL_INSTRUCTION_LIST(DECLARE_DO)
460  #undef DECLARE_DO
461    kMaxInstructionClass
462  };
463
464  HValue() : block_(NULL),
465             id_(kNoNumber),
466             type_(HType::Tagged()),
467             range_(NULL),
468             flags_(0) {}
469  virtual ~HValue() {}
470
471  HBasicBlock* block() const { return block_; }
472  void SetBlock(HBasicBlock* block);
473
474  int id() const { return id_; }
475  void set_id(int id) { id_ = id; }
476
477  SmallPointerList<HValue>* uses() { return &uses_; }
478
479  virtual bool EmitAtUses() { return false; }
480  Representation representation() const { return representation_; }
481  void ChangeRepresentation(Representation r) {
482    // Representation was already set and is allowed to be changed.
483    ASSERT(!representation_.IsNone());
484    ASSERT(!r.IsNone());
485    ASSERT(CheckFlag(kFlexibleRepresentation));
486    RepresentationChanged(r);
487    representation_ = r;
488  }
489
490  HType type() const { return type_; }
491  void set_type(HType type) {
492    ASSERT(uses_.length() == 0);
493    type_ = type;
494  }
495
496  // An operation needs to override this function iff:
497  //   1) it can produce an int32 output.
498  //   2) the true value of its output can potentially be minus zero.
499  // The implementation must set a flag so that it bails out in the case where
500  // it would otherwise output what should be a minus zero as an int32 zero.
501  // If the operation also exists in a form that takes int32 and outputs int32
502  // then the operation should return its input value so that we can propagate
503  // back.  There are two operations that need to propagate back to more than
504  // one input.  They are phi and binary add.  They always return NULL and
505  // expect the caller to take care of things.
506  virtual HValue* EnsureAndPropagateNotMinusZero(BitVector* visited) {
507    visited->Add(id());
508    return NULL;
509  }
510
511  bool IsDefinedAfter(HBasicBlock* other) const;
512
513  // Operands.
514  virtual int OperandCount() = 0;
515  virtual HValue* OperandAt(int index) = 0;
516  void SetOperandAt(int index, HValue* value);
517
518  int LookupOperandIndex(int occurrence_index, HValue* op);
519  bool UsesMultipleTimes(HValue* op);
520
521  void ReplaceAndDelete(HValue* other);
522  void ReplaceValue(HValue* other);
523  void ReplaceAtUse(HValue* use, HValue* other);
524  void ReplaceFirstAtUse(HValue* use, HValue* other, Representation r);
525  bool HasNoUses() const { return uses_.is_empty(); }
526  void ClearOperands();
527  void Delete();
528
529  int flags() const { return flags_; }
530  void SetFlag(Flag f) { flags_ |= (1 << f); }
531  void ClearFlag(Flag f) { flags_ &= ~(1 << f); }
532  bool CheckFlag(Flag f) const { return (flags_ & (1 << f)) != 0; }
533
534  void SetAllSideEffects() { flags_ |= AllSideEffects(); }
535  void ClearAllSideEffects() { flags_ &= ~AllSideEffects(); }
536  bool HasSideEffects() const { return (flags_ & AllSideEffects()) != 0; }
537
538  Range* range() const { return range_; }
539  bool HasRange() const { return range_ != NULL; }
540  void AddNewRange(Range* r);
541  void RemoveLastAddedRange();
542  void ComputeInitialRange();
543
544  // Representation helpers.
545  virtual Representation RequiredInputRepresentation(int index) const = 0;
546
547  virtual Representation InferredRepresentation() {
548    return representation();
549  }
550
551  // This gives the instruction an opportunity to replace itself with an
552  // instruction that does the same in some better way.  To replace an
553  // instruction with a new one, first add the new instruction to the graph,
554  // then return it.  Return NULL to have the instruction deleted.
555  virtual HValue* Canonicalize() { return this; }
556
557  // Declare virtual type testers.
558#define DECLARE_DO(type) virtual bool Is##type() const { return false; }
559  HYDROGEN_ALL_INSTRUCTION_LIST(DECLARE_DO)
560#undef DECLARE_DO
561
562  bool Equals(HValue* other);
563  virtual intptr_t Hashcode();
564
565  // Printing support.
566  virtual void PrintTo(StringStream* stream) = 0;
567  void PrintNameTo(StringStream* stream);
568  static void PrintTypeTo(HType type, StringStream* stream);
569
570  virtual const char* Mnemonic() const = 0;
571  virtual Opcode opcode() const = 0;
572
573  // Updated the inferred type of this instruction and returns true if
574  // it has changed.
575  bool UpdateInferredType();
576
577  virtual HType CalculateInferredType();
578
579#ifdef DEBUG
580  virtual void Verify() = 0;
581#endif
582
583 protected:
584  // This function must be overridden for instructions with flag kUseGVN, to
585  // compare the non-Operand parts of the instruction.
586  virtual bool DataEquals(HValue* other) {
587    UNREACHABLE();
588    return false;
589  }
590  virtual void RepresentationChanged(Representation to) { }
591  virtual Range* InferRange();
592  virtual void DeleteFromGraph() = 0;
593  virtual void InternalSetOperandAt(int index, HValue* value) = 0;
594  void clear_block() {
595    ASSERT(block_ != NULL);
596    block_ = NULL;
597  }
598
599  void set_representation(Representation r) {
600    // Representation is set-once.
601    ASSERT(representation_.IsNone() && !r.IsNone());
602    representation_ = r;
603  }
604
605 private:
606  // A flag mask to mark an instruction as having arbitrary side effects.
607  static int AllSideEffects() {
608    return ChangesFlagsMask() & ~(1 << kChangesOsrEntries);
609  }
610
611  void InternalReplaceAtUse(HValue* use, HValue* other);
612  void RegisterUse(int index, HValue* new_value);
613
614  HBasicBlock* block_;
615
616  // The id of this instruction in the hydrogen graph, assigned when first
617  // added to the graph. Reflects creation order.
618  int id_;
619
620  Representation representation_;
621  HType type_;
622  SmallPointerList<HValue> uses_;
623  Range* range_;
624  int flags_;
625
626  DISALLOW_COPY_AND_ASSIGN(HValue);
627};
628
629
630class HInstruction: public HValue {
631 public:
632  HInstruction* next() const { return next_; }
633  HInstruction* previous() const { return previous_; }
634
635  virtual void PrintTo(StringStream* stream);
636  virtual void PrintDataTo(StringStream* stream) { }
637
638  bool IsLinked() const { return block() != NULL; }
639  void Unlink();
640  void InsertBefore(HInstruction* next);
641  void InsertAfter(HInstruction* previous);
642
643  int position() const { return position_; }
644  bool has_position() const { return position_ != RelocInfo::kNoPosition; }
645  void set_position(int position) { position_ = position; }
646
647  virtual LInstruction* CompileToLithium(LChunkBuilder* builder) = 0;
648
649#ifdef DEBUG
650  virtual void Verify();
651#endif
652
653  // Returns whether this is some kind of deoptimizing check
654  // instruction.
655  virtual bool IsCheckInstruction() const { return false; }
656
657  virtual bool IsCall() { return false; }
658
659  DECLARE_INSTRUCTION(Instruction)
660
661 protected:
662  HInstruction()
663      : next_(NULL),
664        previous_(NULL),
665        position_(RelocInfo::kNoPosition) {
666    SetFlag(kDependsOnOsrEntries);
667  }
668
669  virtual void DeleteFromGraph() { Unlink(); }
670
671 private:
672  void InitializeAsFirst(HBasicBlock* block) {
673    ASSERT(!IsLinked());
674    SetBlock(block);
675  }
676
677  HInstruction* next_;
678  HInstruction* previous_;
679  int position_;
680
681  friend class HBasicBlock;
682};
683
684
685class HControlInstruction: public HInstruction {
686 public:
687  HControlInstruction(HBasicBlock* first, HBasicBlock* second)
688      : first_successor_(first), second_successor_(second) {
689  }
690
691  HBasicBlock* FirstSuccessor() const { return first_successor_; }
692  HBasicBlock* SecondSuccessor() const { return second_successor_; }
693
694  virtual void PrintDataTo(StringStream* stream);
695
696  DECLARE_INSTRUCTION(ControlInstruction)
697
698 private:
699  HBasicBlock* first_successor_;
700  HBasicBlock* second_successor_;
701};
702
703
704template<int NumElements>
705class HOperandContainer {
706 public:
707  HOperandContainer() : elems_() { }
708
709  int length() { return NumElements; }
710  HValue*& operator[](int i) {
711    ASSERT(i < length());
712    return elems_[i];
713  }
714
715 private:
716  HValue* elems_[NumElements];
717};
718
719
720template<>
721class HOperandContainer<0> {
722 public:
723  int length() { return 0; }
724  HValue*& operator[](int i) {
725    UNREACHABLE();
726    static HValue* t = 0;
727    return t;
728  }
729};
730
731
732template<int V>
733class HTemplateInstruction : public HInstruction {
734 public:
735  int OperandCount() { return V; }
736  HValue* OperandAt(int i) { return inputs_[i]; }
737
738 protected:
739  void InternalSetOperandAt(int i, HValue* value) { inputs_[i] = value; }
740
741 private:
742  HOperandContainer<V> inputs_;
743};
744
745
746template<int V>
747class HTemplateControlInstruction : public HControlInstruction {
748 public:
749  HTemplateControlInstruction<V>(HBasicBlock* first, HBasicBlock* second)
750    : HControlInstruction(first, second) { }
751  int OperandCount() { return V; }
752  HValue* OperandAt(int i) { return inputs_[i]; }
753
754 protected:
755  void InternalSetOperandAt(int i, HValue* value) { inputs_[i] = value; }
756
757 private:
758  HOperandContainer<V> inputs_;
759};
760
761
762class HBlockEntry: public HTemplateInstruction<0> {
763 public:
764  virtual Representation RequiredInputRepresentation(int index) const {
765    return Representation::None();
766  }
767
768  DECLARE_CONCRETE_INSTRUCTION(BlockEntry, "block_entry")
769};
770
771
772class HDeoptimize: public HControlInstruction {
773 public:
774  explicit HDeoptimize(int environment_length)
775      : HControlInstruction(NULL, NULL),
776        values_(environment_length) { }
777
778  virtual Representation RequiredInputRepresentation(int index) const {
779    return Representation::None();
780  }
781
782  virtual int OperandCount() { return values_.length(); }
783  virtual HValue* OperandAt(int index) { return values_[index]; }
784
785  void AddEnvironmentValue(HValue* value) {
786    values_.Add(NULL);
787    SetOperandAt(values_.length() - 1, value);
788  }
789
790  DECLARE_CONCRETE_INSTRUCTION(Deoptimize, "deoptimize")
791
792 protected:
793  virtual void InternalSetOperandAt(int index, HValue* value) {
794    values_[index] = value;
795  }
796
797 private:
798  ZoneList<HValue*> values_;
799};
800
801
802class HGoto: public HTemplateControlInstruction<0> {
803 public:
804  explicit HGoto(HBasicBlock* target)
805      : HTemplateControlInstruction<0>(target, NULL),
806        include_stack_check_(false) { }
807
808  void set_include_stack_check(bool include_stack_check) {
809    include_stack_check_ = include_stack_check;
810  }
811  bool include_stack_check() const { return include_stack_check_; }
812
813  virtual Representation RequiredInputRepresentation(int index) const {
814    return Representation::None();
815  }
816
817  DECLARE_CONCRETE_INSTRUCTION(Goto, "goto")
818
819 private:
820  bool include_stack_check_;
821};
822
823
824class HUnaryControlInstruction: public HTemplateControlInstruction<1> {
825 public:
826  explicit HUnaryControlInstruction(HValue* value,
827                                    HBasicBlock* true_target,
828                                    HBasicBlock* false_target)
829      : HTemplateControlInstruction<1>(true_target, false_target) {
830    SetOperandAt(0, value);
831  }
832
833  virtual void PrintDataTo(StringStream* stream);
834
835  HValue* value() { return OperandAt(0); }
836
837  DECLARE_INSTRUCTION(UnaryControlInstruction)
838};
839
840
841class HTest: public HUnaryControlInstruction {
842 public:
843  HTest(HValue* value, HBasicBlock* true_target, HBasicBlock* false_target)
844      : HUnaryControlInstruction(value, true_target, false_target) {
845    ASSERT(true_target != NULL && false_target != NULL);
846  }
847
848  virtual Representation RequiredInputRepresentation(int index) const {
849    return Representation::None();
850  }
851
852  DECLARE_CONCRETE_INSTRUCTION(Test, "test")
853};
854
855
856class HCompareMap: public HUnaryControlInstruction {
857 public:
858  HCompareMap(HValue* value,
859              Handle<Map> map,
860              HBasicBlock* true_target,
861              HBasicBlock* false_target)
862      : HUnaryControlInstruction(value, true_target, false_target),
863        map_(map) {
864    ASSERT(true_target != NULL);
865    ASSERT(false_target != NULL);
866    ASSERT(!map.is_null());
867  }
868
869  virtual void PrintDataTo(StringStream* stream);
870
871  Handle<Map> map() const { return map_; }
872
873  virtual Representation RequiredInputRepresentation(int index) const {
874    return Representation::Tagged();
875  }
876
877  DECLARE_CONCRETE_INSTRUCTION(CompareMap, "compare_map")
878
879 private:
880  Handle<Map> map_;
881};
882
883
884class HReturn: public HUnaryControlInstruction {
885 public:
886  explicit HReturn(HValue* value)
887      : HUnaryControlInstruction(value, NULL, NULL) {
888  }
889
890  virtual Representation RequiredInputRepresentation(int index) const {
891    return Representation::Tagged();
892  }
893
894  DECLARE_CONCRETE_INSTRUCTION(Return, "return")
895};
896
897
898class HAbnormalExit: public HTemplateControlInstruction<0> {
899 public:
900  HAbnormalExit() : HTemplateControlInstruction<0>(NULL, NULL) { }
901
902  virtual Representation RequiredInputRepresentation(int index) const {
903    return Representation::None();
904  }
905
906  DECLARE_CONCRETE_INSTRUCTION(AbnormalExit, "abnormal_exit")
907};
908
909
910class HUnaryOperation: public HTemplateInstruction<1> {
911 public:
912  explicit HUnaryOperation(HValue* value) {
913    SetOperandAt(0, value);
914  }
915
916  HValue* value() { return OperandAt(0); }
917  virtual void PrintDataTo(StringStream* stream);
918
919  DECLARE_INSTRUCTION(UnaryOperation)
920};
921
922
923class HThrow: public HUnaryOperation {
924 public:
925  explicit HThrow(HValue* value) : HUnaryOperation(value) {
926    SetAllSideEffects();
927  }
928
929  virtual Representation RequiredInputRepresentation(int index) const {
930    return Representation::Tagged();
931  }
932
933  DECLARE_CONCRETE_INSTRUCTION(Throw, "throw")
934};
935
936
937class HChange: public HUnaryOperation {
938 public:
939  HChange(HValue* value,
940          Representation from,
941          Representation to,
942          bool is_truncating,
943          bool deoptimize_on_undefined)
944      : HUnaryOperation(value),
945        from_(from),
946        deoptimize_on_undefined_(deoptimize_on_undefined) {
947    ASSERT(!from.IsNone() && !to.IsNone());
948    ASSERT(!from.Equals(to));
949    set_representation(to);
950    SetFlag(kUseGVN);
951    if (is_truncating) SetFlag(kTruncatingToInt32);
952    if (from.IsInteger32() && to.IsTagged() && value->range() != NULL &&
953        value->range()->IsInSmiRange()) {
954      set_type(HType::Smi());
955    }
956  }
957
958  virtual HValue* EnsureAndPropagateNotMinusZero(BitVector* visited);
959
960  Representation from() const { return from_; }
961  Representation to() const { return representation(); }
962  bool deoptimize_on_undefined() const { return deoptimize_on_undefined_; }
963  virtual Representation RequiredInputRepresentation(int index) const {
964    return from_;
965  }
966
967  bool CanTruncateToInt32() const { return CheckFlag(kTruncatingToInt32); }
968
969  virtual void PrintDataTo(StringStream* stream);
970
971  DECLARE_CONCRETE_INSTRUCTION(Change,
972                               CanTruncateToInt32() ? "truncate" : "change")
973
974 protected:
975  virtual bool DataEquals(HValue* other) {
976    if (!other->IsChange()) return false;
977    HChange* change = HChange::cast(other);
978    return value() == change->value()
979        && to().Equals(change->to())
980        && deoptimize_on_undefined() == change->deoptimize_on_undefined();
981  }
982
983 private:
984  Representation from_;
985  bool deoptimize_on_undefined_;
986};
987
988
989class HSimulate: public HInstruction {
990 public:
991  HSimulate(int ast_id, int pop_count)
992      : ast_id_(ast_id),
993        pop_count_(pop_count),
994        values_(2),
995        assigned_indexes_(2) {}
996  virtual ~HSimulate() {}
997
998  virtual void PrintDataTo(StringStream* stream);
999
1000  bool HasAstId() const { return ast_id_ != AstNode::kNoNumber; }
1001  int ast_id() const { return ast_id_; }
1002  void set_ast_id(int id) {
1003    ASSERT(!HasAstId());
1004    ast_id_ = id;
1005  }
1006
1007  int pop_count() const { return pop_count_; }
1008  const ZoneList<HValue*>* values() const { return &values_; }
1009  int GetAssignedIndexAt(int index) const {
1010    ASSERT(HasAssignedIndexAt(index));
1011    return assigned_indexes_[index];
1012  }
1013  bool HasAssignedIndexAt(int index) const {
1014    return assigned_indexes_[index] != kNoIndex;
1015  }
1016  void AddAssignedValue(int index, HValue* value) {
1017    AddValue(index, value);
1018  }
1019  void AddPushedValue(HValue* value) {
1020    AddValue(kNoIndex, value);
1021  }
1022  virtual int OperandCount() { return values_.length(); }
1023  virtual HValue* OperandAt(int index) { return values_[index]; }
1024
1025  virtual Representation RequiredInputRepresentation(int index) const {
1026    return Representation::None();
1027  }
1028
1029  DECLARE_CONCRETE_INSTRUCTION(Simulate, "simulate")
1030
1031#ifdef DEBUG
1032  virtual void Verify();
1033#endif
1034
1035 protected:
1036  virtual void InternalSetOperandAt(int index, HValue* value) {
1037    values_[index] = value;
1038  }
1039
1040 private:
1041  static const int kNoIndex = -1;
1042  void AddValue(int index, HValue* value) {
1043    assigned_indexes_.Add(index);
1044    // Resize the list of pushed values.
1045    values_.Add(NULL);
1046    // Set the operand through the base method in HValue to make sure that the
1047    // use lists are correctly updated.
1048    SetOperandAt(values_.length() - 1, value);
1049  }
1050  int ast_id_;
1051  int pop_count_;
1052  ZoneList<HValue*> values_;
1053  ZoneList<int> assigned_indexes_;
1054};
1055
1056
1057class HStackCheck: public HTemplateInstruction<0> {
1058 public:
1059  HStackCheck() { }
1060
1061  virtual Representation RequiredInputRepresentation(int index) const {
1062    return Representation::None();
1063  }
1064
1065  DECLARE_CONCRETE_INSTRUCTION(StackCheck, "stack_check")
1066};
1067
1068
1069class HEnterInlined: public HTemplateInstruction<0> {
1070 public:
1071  HEnterInlined(Handle<JSFunction> closure, FunctionLiteral* function)
1072      : closure_(closure), function_(function) {
1073  }
1074
1075  virtual void PrintDataTo(StringStream* stream);
1076
1077  Handle<JSFunction> closure() const { return closure_; }
1078  FunctionLiteral* function() const { return function_; }
1079
1080  virtual Representation RequiredInputRepresentation(int index) const {
1081    return Representation::None();
1082  }
1083
1084  DECLARE_CONCRETE_INSTRUCTION(EnterInlined, "enter_inlined")
1085
1086 private:
1087  Handle<JSFunction> closure_;
1088  FunctionLiteral* function_;
1089};
1090
1091
1092class HLeaveInlined: public HTemplateInstruction<0> {
1093 public:
1094  HLeaveInlined() {}
1095
1096  virtual Representation RequiredInputRepresentation(int index) const {
1097    return Representation::None();
1098  }
1099
1100  DECLARE_CONCRETE_INSTRUCTION(LeaveInlined, "leave_inlined")
1101};
1102
1103
1104class HPushArgument: public HUnaryOperation {
1105 public:
1106  explicit HPushArgument(HValue* value) : HUnaryOperation(value) {
1107    set_representation(Representation::Tagged());
1108  }
1109
1110  virtual Representation RequiredInputRepresentation(int index) const {
1111    return Representation::Tagged();
1112  }
1113
1114  HValue* argument() { return OperandAt(0); }
1115
1116  DECLARE_CONCRETE_INSTRUCTION(PushArgument, "push_argument")
1117};
1118
1119
1120class HContext: public HTemplateInstruction<0> {
1121 public:
1122  HContext() {
1123    set_representation(Representation::Tagged());
1124    SetFlag(kUseGVN);
1125  }
1126
1127  virtual Representation RequiredInputRepresentation(int index) const {
1128    return Representation::None();
1129  }
1130
1131  DECLARE_CONCRETE_INSTRUCTION(Context, "context");
1132
1133 protected:
1134  virtual bool DataEquals(HValue* other) { return true; }
1135};
1136
1137
1138class HOuterContext: public HUnaryOperation {
1139 public:
1140  explicit HOuterContext(HValue* inner) : HUnaryOperation(inner) {
1141    set_representation(Representation::Tagged());
1142    SetFlag(kUseGVN);
1143  }
1144
1145  DECLARE_CONCRETE_INSTRUCTION(OuterContext, "outer_context");
1146
1147  virtual Representation RequiredInputRepresentation(int index) const {
1148    return Representation::Tagged();
1149  }
1150
1151 protected:
1152  virtual bool DataEquals(HValue* other) { return true; }
1153};
1154
1155
1156class HGlobalObject: public HUnaryOperation {
1157 public:
1158  explicit HGlobalObject(HValue* context) : HUnaryOperation(context) {
1159    set_representation(Representation::Tagged());
1160    SetFlag(kUseGVN);
1161  }
1162
1163  DECLARE_CONCRETE_INSTRUCTION(GlobalObject, "global_object")
1164
1165  virtual Representation RequiredInputRepresentation(int index) const {
1166    return Representation::Tagged();
1167  }
1168
1169 protected:
1170  virtual bool DataEquals(HValue* other) { return true; }
1171};
1172
1173
1174class HGlobalReceiver: public HUnaryOperation {
1175 public:
1176  explicit HGlobalReceiver(HValue* global_object)
1177      : HUnaryOperation(global_object) {
1178    set_representation(Representation::Tagged());
1179    SetFlag(kUseGVN);
1180  }
1181
1182  DECLARE_CONCRETE_INSTRUCTION(GlobalReceiver, "global_receiver")
1183
1184  virtual Representation RequiredInputRepresentation(int index) const {
1185    return Representation::Tagged();
1186  }
1187
1188 protected:
1189  virtual bool DataEquals(HValue* other) { return true; }
1190};
1191
1192
1193template <int V>
1194class HCall: public HTemplateInstruction<V> {
1195 public:
1196  // The argument count includes the receiver.
1197  explicit HCall<V>(int argument_count) : argument_count_(argument_count) {
1198    this->set_representation(Representation::Tagged());
1199    this->SetAllSideEffects();
1200  }
1201
1202  virtual HType CalculateInferredType() { return HType::Tagged(); }
1203
1204  virtual int argument_count() const { return argument_count_; }
1205
1206  virtual bool IsCall() { return true; }
1207
1208 private:
1209  int argument_count_;
1210};
1211
1212
1213class HUnaryCall: public HCall<1> {
1214 public:
1215  HUnaryCall(HValue* value, int argument_count)
1216      : HCall<1>(argument_count) {
1217    SetOperandAt(0, value);
1218  }
1219
1220  virtual Representation RequiredInputRepresentation(int index) const {
1221    return Representation::Tagged();
1222  }
1223
1224  virtual void PrintDataTo(StringStream* stream);
1225
1226  HValue* value() { return OperandAt(0); }
1227
1228  DECLARE_INSTRUCTION(UnaryCall)
1229};
1230
1231
1232class HBinaryCall: public HCall<2> {
1233 public:
1234  HBinaryCall(HValue* first, HValue* second, int argument_count)
1235      : HCall<2>(argument_count) {
1236    SetOperandAt(0, first);
1237    SetOperandAt(1, second);
1238  }
1239
1240  virtual void PrintDataTo(StringStream* stream);
1241
1242  virtual Representation RequiredInputRepresentation(int index) const {
1243    return Representation::Tagged();
1244  }
1245
1246  HValue* first() { return OperandAt(0); }
1247  HValue* second() { return OperandAt(1); }
1248
1249  DECLARE_INSTRUCTION(BinaryCall)
1250};
1251
1252
1253class HCallConstantFunction: public HCall<0> {
1254 public:
1255  HCallConstantFunction(Handle<JSFunction> function, int argument_count)
1256      : HCall<0>(argument_count), function_(function) { }
1257
1258  Handle<JSFunction> function() const { return function_; }
1259
1260  bool IsApplyFunction() const {
1261    return function_->code() ==
1262        Isolate::Current()->builtins()->builtin(Builtins::kFunctionApply);
1263  }
1264
1265  virtual void PrintDataTo(StringStream* stream);
1266
1267  virtual Representation RequiredInputRepresentation(int index) const {
1268    return Representation::None();
1269  }
1270
1271  DECLARE_CONCRETE_INSTRUCTION(CallConstantFunction, "call_constant_function")
1272
1273 private:
1274  Handle<JSFunction> function_;
1275};
1276
1277
1278class HCallKeyed: public HBinaryCall {
1279 public:
1280  HCallKeyed(HValue* context, HValue* key, int argument_count)
1281      : HBinaryCall(context, key, argument_count) {
1282  }
1283
1284  virtual Representation RequiredInputRepresentation(int index) const {
1285    return Representation::Tagged();
1286  }
1287
1288  HValue* context() { return first(); }
1289  HValue* key() { return second(); }
1290
1291  DECLARE_CONCRETE_INSTRUCTION(CallKeyed, "call_keyed")
1292};
1293
1294
1295class HCallNamed: public HUnaryCall {
1296 public:
1297  HCallNamed(HValue* context, Handle<String> name, int argument_count)
1298      : HUnaryCall(context, argument_count), name_(name) {
1299  }
1300
1301  virtual void PrintDataTo(StringStream* stream);
1302
1303  HValue* context() { return value(); }
1304  Handle<String> name() const { return name_; }
1305
1306  DECLARE_CONCRETE_INSTRUCTION(CallNamed, "call_named")
1307
1308  virtual Representation RequiredInputRepresentation(int index) const {
1309    return Representation::Tagged();
1310  }
1311
1312 private:
1313  Handle<String> name_;
1314};
1315
1316
1317class HCallFunction: public HUnaryCall {
1318 public:
1319  HCallFunction(HValue* context, int argument_count)
1320      : HUnaryCall(context, argument_count) {
1321  }
1322
1323  HValue* context() { return value(); }
1324
1325  virtual Representation RequiredInputRepresentation(int index) const {
1326    return Representation::Tagged();
1327  }
1328
1329  DECLARE_CONCRETE_INSTRUCTION(CallFunction, "call_function")
1330};
1331
1332
1333class HCallGlobal: public HUnaryCall {
1334 public:
1335  HCallGlobal(HValue* context, Handle<String> name, int argument_count)
1336      : HUnaryCall(context, argument_count), name_(name) {
1337  }
1338
1339  virtual void PrintDataTo(StringStream* stream);
1340
1341  HValue* context() { return value(); }
1342  Handle<String> name() const { return name_; }
1343
1344  virtual Representation RequiredInputRepresentation(int index) const {
1345    return Representation::Tagged();
1346  }
1347
1348  DECLARE_CONCRETE_INSTRUCTION(CallGlobal, "call_global")
1349
1350 private:
1351  Handle<String> name_;
1352};
1353
1354
1355class HCallKnownGlobal: public HCall<0> {
1356 public:
1357  HCallKnownGlobal(Handle<JSFunction> target, int argument_count)
1358      : HCall<0>(argument_count), target_(target) { }
1359
1360  virtual void PrintDataTo(StringStream* stream);
1361
1362  Handle<JSFunction> target() const { return target_; }
1363
1364  virtual Representation RequiredInputRepresentation(int index) const {
1365    return Representation::None();
1366  }
1367
1368  DECLARE_CONCRETE_INSTRUCTION(CallKnownGlobal, "call_known_global")
1369
1370 private:
1371  Handle<JSFunction> target_;
1372};
1373
1374
1375class HCallNew: public HBinaryCall {
1376 public:
1377  HCallNew(HValue* context, HValue* constructor, int argument_count)
1378      : HBinaryCall(context, constructor, argument_count) {
1379  }
1380
1381  virtual Representation RequiredInputRepresentation(int index) const {
1382    return Representation::Tagged();
1383  }
1384
1385  HValue* context() { return first(); }
1386  HValue* constructor() { return second(); }
1387
1388  DECLARE_CONCRETE_INSTRUCTION(CallNew, "call_new")
1389};
1390
1391
1392class HCallRuntime: public HCall<0> {
1393 public:
1394  HCallRuntime(Handle<String> name,
1395               const Runtime::Function* c_function,
1396               int argument_count)
1397      : HCall<0>(argument_count), c_function_(c_function), name_(name) { }
1398  virtual void PrintDataTo(StringStream* stream);
1399
1400  const Runtime::Function* function() const { return c_function_; }
1401  Handle<String> name() const { return name_; }
1402
1403  virtual Representation RequiredInputRepresentation(int index) const {
1404    return Representation::None();
1405  }
1406
1407  DECLARE_CONCRETE_INSTRUCTION(CallRuntime, "call_runtime")
1408
1409 private:
1410  const Runtime::Function* c_function_;
1411  Handle<String> name_;
1412};
1413
1414
1415class HJSArrayLength: public HUnaryOperation {
1416 public:
1417  explicit HJSArrayLength(HValue* value) : HUnaryOperation(value) {
1418    // The length of an array is stored as a tagged value in the array
1419    // object. It is guaranteed to be 32 bit integer, but it can be
1420    // represented as either a smi or heap number.
1421    set_representation(Representation::Tagged());
1422    SetFlag(kUseGVN);
1423    SetFlag(kDependsOnArrayLengths);
1424    SetFlag(kDependsOnMaps);
1425  }
1426
1427  virtual Representation RequiredInputRepresentation(int index) const {
1428    return Representation::Tagged();
1429  }
1430
1431  DECLARE_CONCRETE_INSTRUCTION(JSArrayLength, "js_array_length")
1432
1433 protected:
1434  virtual bool DataEquals(HValue* other) { return true; }
1435};
1436
1437
1438class HFixedArrayLength: public HUnaryOperation {
1439 public:
1440  explicit HFixedArrayLength(HValue* value) : HUnaryOperation(value) {
1441    set_representation(Representation::Tagged());
1442    SetFlag(kUseGVN);
1443    SetFlag(kDependsOnArrayLengths);
1444  }
1445
1446  virtual Representation RequiredInputRepresentation(int index) const {
1447    return Representation::Tagged();
1448  }
1449
1450  DECLARE_CONCRETE_INSTRUCTION(FixedArrayLength, "fixed_array_length")
1451
1452 protected:
1453  virtual bool DataEquals(HValue* other) { return true; }
1454};
1455
1456
1457class HExternalArrayLength: public HUnaryOperation {
1458 public:
1459  explicit HExternalArrayLength(HValue* value) : HUnaryOperation(value) {
1460    set_representation(Representation::Integer32());
1461    // The result of this instruction is idempotent as long as its inputs don't
1462    // change.  The length of a pixel array cannot change once set, so it's not
1463    // necessary to introduce a kDependsOnArrayLengths or any other dependency.
1464    SetFlag(kUseGVN);
1465  }
1466
1467  virtual Representation RequiredInputRepresentation(int index) const {
1468    return Representation::Tagged();
1469  }
1470
1471  DECLARE_CONCRETE_INSTRUCTION(ExternalArrayLength, "external_array_length")
1472
1473 protected:
1474  virtual bool DataEquals(HValue* other) { return true; }
1475};
1476
1477
1478class HBitNot: public HUnaryOperation {
1479 public:
1480  explicit HBitNot(HValue* value) : HUnaryOperation(value) {
1481    set_representation(Representation::Integer32());
1482    SetFlag(kUseGVN);
1483    SetFlag(kTruncatingToInt32);
1484  }
1485
1486  virtual Representation RequiredInputRepresentation(int index) const {
1487    return Representation::Integer32();
1488  }
1489  virtual HType CalculateInferredType();
1490
1491  DECLARE_CONCRETE_INSTRUCTION(BitNot, "bit_not")
1492
1493 protected:
1494  virtual bool DataEquals(HValue* other) { return true; }
1495};
1496
1497
1498class HUnaryMathOperation: public HUnaryOperation {
1499 public:
1500  HUnaryMathOperation(HValue* value, BuiltinFunctionId op)
1501      : HUnaryOperation(value), op_(op) {
1502    switch (op) {
1503      case kMathFloor:
1504      case kMathRound:
1505      case kMathCeil:
1506        set_representation(Representation::Integer32());
1507        break;
1508      case kMathAbs:
1509        set_representation(Representation::Tagged());
1510        SetFlag(kFlexibleRepresentation);
1511        break;
1512      case kMathSqrt:
1513      case kMathPowHalf:
1514      case kMathLog:
1515      case kMathSin:
1516      case kMathCos:
1517        set_representation(Representation::Double());
1518        break;
1519      default:
1520        UNREACHABLE();
1521    }
1522    SetFlag(kUseGVN);
1523  }
1524
1525  virtual void PrintDataTo(StringStream* stream);
1526
1527  virtual HType CalculateInferredType();
1528
1529  virtual HValue* EnsureAndPropagateNotMinusZero(BitVector* visited);
1530
1531  virtual Representation RequiredInputRepresentation(int index) const {
1532    switch (op_) {
1533      case kMathFloor:
1534      case kMathRound:
1535      case kMathCeil:
1536      case kMathSqrt:
1537      case kMathPowHalf:
1538      case kMathLog:
1539      case kMathSin:
1540      case kMathCos:
1541        return Representation::Double();
1542      case kMathAbs:
1543        return representation();
1544      default:
1545        UNREACHABLE();
1546        return Representation::None();
1547    }
1548  }
1549
1550  virtual HValue* Canonicalize() {
1551    // If the input is integer32 then we replace the floor instruction
1552    // with its inputs.  This happens before the representation changes are
1553    // introduced.
1554    if (op() == kMathFloor) {
1555      if (value()->representation().IsInteger32()) return value();
1556    }
1557    return this;
1558  }
1559
1560  BuiltinFunctionId op() const { return op_; }
1561  const char* OpName() const;
1562
1563  DECLARE_CONCRETE_INSTRUCTION(UnaryMathOperation, "unary_math_operation")
1564
1565 protected:
1566  virtual bool DataEquals(HValue* other) {
1567    HUnaryMathOperation* b = HUnaryMathOperation::cast(other);
1568    return op_ == b->op();
1569  }
1570
1571 private:
1572  BuiltinFunctionId op_;
1573};
1574
1575
1576class HLoadElements: public HUnaryOperation {
1577 public:
1578  explicit HLoadElements(HValue* value) : HUnaryOperation(value) {
1579    set_representation(Representation::Tagged());
1580    SetFlag(kUseGVN);
1581    SetFlag(kDependsOnMaps);
1582  }
1583
1584  virtual Representation RequiredInputRepresentation(int index) const {
1585    return Representation::Tagged();
1586  }
1587
1588  DECLARE_CONCRETE_INSTRUCTION(LoadElements, "load-elements")
1589
1590 protected:
1591  virtual bool DataEquals(HValue* other) { return true; }
1592};
1593
1594
1595class HLoadExternalArrayPointer: public HUnaryOperation {
1596 public:
1597  explicit HLoadExternalArrayPointer(HValue* value)
1598      : HUnaryOperation(value) {
1599    set_representation(Representation::External());
1600    // The result of this instruction is idempotent as long as its inputs don't
1601    // change.  The external array of a specialized array elements object cannot
1602    // change once set, so it's no necessary to introduce any additional
1603    // dependencies on top of the inputs.
1604    SetFlag(kUseGVN);
1605  }
1606
1607  virtual Representation RequiredInputRepresentation(int index) const {
1608    return Representation::Tagged();
1609  }
1610
1611  DECLARE_CONCRETE_INSTRUCTION(LoadExternalArrayPointer,
1612                               "load-external-array-pointer")
1613
1614 protected:
1615  virtual bool DataEquals(HValue* other) { return true; }
1616};
1617
1618
1619class HCheckMap: public HUnaryOperation {
1620 public:
1621  HCheckMap(HValue* value, Handle<Map> map)
1622      : HUnaryOperation(value), map_(map) {
1623    set_representation(Representation::Tagged());
1624    SetFlag(kUseGVN);
1625    SetFlag(kDependsOnMaps);
1626  }
1627
1628  virtual bool IsCheckInstruction() const { return true; }
1629
1630  virtual Representation RequiredInputRepresentation(int index) const {
1631    return Representation::Tagged();
1632  }
1633  virtual void PrintDataTo(StringStream* stream);
1634  virtual HType CalculateInferredType();
1635
1636#ifdef DEBUG
1637  virtual void Verify();
1638#endif
1639
1640  Handle<Map> map() const { return map_; }
1641
1642  DECLARE_CONCRETE_INSTRUCTION(CheckMap, "check_map")
1643
1644 protected:
1645  virtual bool DataEquals(HValue* other) {
1646    HCheckMap* b = HCheckMap::cast(other);
1647    return map_.is_identical_to(b->map());
1648  }
1649
1650 private:
1651  Handle<Map> map_;
1652};
1653
1654
1655class HCheckFunction: public HUnaryOperation {
1656 public:
1657  HCheckFunction(HValue* value, Handle<JSFunction> function)
1658      : HUnaryOperation(value), target_(function) {
1659    set_representation(Representation::Tagged());
1660    SetFlag(kUseGVN);
1661  }
1662
1663  virtual bool IsCheckInstruction() const { return true; }
1664
1665  virtual Representation RequiredInputRepresentation(int index) const {
1666    return Representation::Tagged();
1667  }
1668  virtual void PrintDataTo(StringStream* stream);
1669  virtual HType CalculateInferredType();
1670
1671#ifdef DEBUG
1672  virtual void Verify();
1673#endif
1674
1675  Handle<JSFunction> target() const { return target_; }
1676
1677  DECLARE_CONCRETE_INSTRUCTION(CheckFunction, "check_function")
1678
1679 protected:
1680  virtual bool DataEquals(HValue* other) {
1681    HCheckFunction* b = HCheckFunction::cast(other);
1682    return target_.is_identical_to(b->target());
1683  }
1684
1685 private:
1686  Handle<JSFunction> target_;
1687};
1688
1689
1690class HCheckInstanceType: public HUnaryOperation {
1691 public:
1692  // Check that the instance type is in the range [first, last] where
1693  // both first and last are included.
1694  HCheckInstanceType(HValue* value, InstanceType first, InstanceType last)
1695      : HUnaryOperation(value), first_(first), last_(last) {
1696    ASSERT(first <= last);
1697    set_representation(Representation::Tagged());
1698    SetFlag(kUseGVN);
1699    if ((FIRST_STRING_TYPE < first && last <= LAST_STRING_TYPE) ||
1700        (FIRST_STRING_TYPE <= first && last < LAST_STRING_TYPE)) {
1701      // A particular string instance type can change because of GC or
1702      // externalization, but the value still remains a string.
1703      SetFlag(kDependsOnMaps);
1704    }
1705  }
1706
1707  virtual bool IsCheckInstruction() const { return true; }
1708
1709  virtual Representation RequiredInputRepresentation(int index) const {
1710    return Representation::Tagged();
1711  }
1712
1713#ifdef DEBUG
1714  virtual void Verify();
1715#endif
1716
1717  static HCheckInstanceType* NewIsJSObjectOrJSFunction(HValue* value);
1718
1719  InstanceType first() const { return first_; }
1720  InstanceType last() const { return last_; }
1721
1722  DECLARE_CONCRETE_INSTRUCTION(CheckInstanceType, "check_instance_type")
1723
1724 protected:
1725  // TODO(ager): It could be nice to allow the ommision of instance
1726  // type checks if we have already performed an instance type check
1727  // with a larger range.
1728  virtual bool DataEquals(HValue* other) {
1729    HCheckInstanceType* b = HCheckInstanceType::cast(other);
1730    return (first_ == b->first()) && (last_ == b->last());
1731  }
1732
1733 private:
1734  InstanceType first_;
1735  InstanceType last_;
1736};
1737
1738
1739class HCheckNonSmi: public HUnaryOperation {
1740 public:
1741  explicit HCheckNonSmi(HValue* value) : HUnaryOperation(value) {
1742    set_representation(Representation::Tagged());
1743    SetFlag(kUseGVN);
1744  }
1745
1746  virtual bool IsCheckInstruction() const { return true; }
1747
1748  virtual Representation RequiredInputRepresentation(int index) const {
1749    return Representation::Tagged();
1750  }
1751
1752  virtual HType CalculateInferredType();
1753
1754#ifdef DEBUG
1755  virtual void Verify();
1756#endif
1757
1758  DECLARE_CONCRETE_INSTRUCTION(CheckNonSmi, "check_non_smi")
1759
1760 protected:
1761  virtual bool DataEquals(HValue* other) { return true; }
1762};
1763
1764
1765class HCheckPrototypeMaps: public HTemplateInstruction<0> {
1766 public:
1767  HCheckPrototypeMaps(Handle<JSObject> prototype, Handle<JSObject> holder)
1768      : prototype_(prototype), holder_(holder) {
1769    SetFlag(kUseGVN);
1770    SetFlag(kDependsOnMaps);
1771  }
1772
1773  virtual bool IsCheckInstruction() const { return true; }
1774
1775#ifdef DEBUG
1776  virtual void Verify();
1777#endif
1778
1779  Handle<JSObject> prototype() const { return prototype_; }
1780  Handle<JSObject> holder() const { return holder_; }
1781
1782  DECLARE_CONCRETE_INSTRUCTION(CheckPrototypeMaps, "check_prototype_maps")
1783
1784  virtual Representation RequiredInputRepresentation(int index) const {
1785    return Representation::None();
1786  }
1787
1788  virtual intptr_t Hashcode() {
1789    ASSERT(!HEAP->IsAllocationAllowed());
1790    intptr_t hash = reinterpret_cast<intptr_t>(*prototype());
1791    hash = 17 * hash + reinterpret_cast<intptr_t>(*holder());
1792    return hash;
1793  }
1794
1795 protected:
1796  virtual bool DataEquals(HValue* other) {
1797    HCheckPrototypeMaps* b = HCheckPrototypeMaps::cast(other);
1798    return prototype_.is_identical_to(b->prototype()) &&
1799        holder_.is_identical_to(b->holder());
1800  }
1801
1802 private:
1803  Handle<JSObject> prototype_;
1804  Handle<JSObject> holder_;
1805};
1806
1807
1808class HCheckSmi: public HUnaryOperation {
1809 public:
1810  explicit HCheckSmi(HValue* value) : HUnaryOperation(value) {
1811    set_representation(Representation::Tagged());
1812    SetFlag(kUseGVN);
1813  }
1814
1815  virtual bool IsCheckInstruction() const { return true; }
1816
1817  virtual Representation RequiredInputRepresentation(int index) const {
1818    return Representation::Tagged();
1819  }
1820  virtual HType CalculateInferredType();
1821
1822#ifdef DEBUG
1823  virtual void Verify();
1824#endif
1825
1826  DECLARE_CONCRETE_INSTRUCTION(CheckSmi, "check_smi")
1827
1828 protected:
1829  virtual bool DataEquals(HValue* other) { return true; }
1830};
1831
1832
1833class HPhi: public HValue {
1834 public:
1835  explicit HPhi(int merged_index)
1836      : inputs_(2),
1837        merged_index_(merged_index),
1838        phi_id_(-1),
1839        is_live_(false) {
1840    for (int i = 0; i < Representation::kNumRepresentations; i++) {
1841      non_phi_uses_[i] = 0;
1842      indirect_uses_[i] = 0;
1843    }
1844    ASSERT(merged_index >= 0);
1845    set_representation(Representation::Tagged());
1846    SetFlag(kFlexibleRepresentation);
1847  }
1848
1849  virtual Representation InferredRepresentation() {
1850    bool double_occurred = false;
1851    bool int32_occurred = false;
1852    for (int i = 0; i < OperandCount(); ++i) {
1853      HValue* value = OperandAt(i);
1854      if (value->representation().IsDouble()) double_occurred = true;
1855      if (value->representation().IsInteger32()) int32_occurred = true;
1856      if (value->representation().IsTagged()) return Representation::Tagged();
1857    }
1858
1859    if (double_occurred) return Representation::Double();
1860    if (int32_occurred) return Representation::Integer32();
1861    return Representation::None();
1862  }
1863
1864  virtual Range* InferRange();
1865  virtual Representation RequiredInputRepresentation(int index) const {
1866    return representation();
1867  }
1868  virtual HType CalculateInferredType();
1869  virtual int OperandCount() { return inputs_.length(); }
1870  virtual HValue* OperandAt(int index) { return inputs_[index]; }
1871  HValue* GetRedundantReplacement();
1872  void AddInput(HValue* value);
1873  bool HasRealUses();
1874
1875  bool IsReceiver() { return merged_index_ == 0; }
1876
1877  int merged_index() const { return merged_index_; }
1878
1879  virtual const char* Mnemonic() const { return "phi"; }
1880
1881  virtual void PrintTo(StringStream* stream);
1882
1883#ifdef DEBUG
1884  virtual void Verify();
1885#endif
1886
1887  DECLARE_INSTRUCTION(Phi)
1888
1889  void InitRealUses(int id);
1890  void AddNonPhiUsesFrom(HPhi* other);
1891  void AddIndirectUsesTo(int* use_count);
1892
1893  int tagged_non_phi_uses() const {
1894    return non_phi_uses_[Representation::kTagged];
1895  }
1896  int int32_non_phi_uses() const {
1897    return non_phi_uses_[Representation::kInteger32];
1898  }
1899  int double_non_phi_uses() const {
1900    return non_phi_uses_[Representation::kDouble];
1901  }
1902  int tagged_indirect_uses() const {
1903    return indirect_uses_[Representation::kTagged];
1904  }
1905  int int32_indirect_uses() const {
1906    return indirect_uses_[Representation::kInteger32];
1907  }
1908  int double_indirect_uses() const {
1909    return indirect_uses_[Representation::kDouble];
1910  }
1911  int phi_id() { return phi_id_; }
1912  bool is_live() { return is_live_; }
1913  void set_is_live(bool b) { is_live_ = b; }
1914
1915 protected:
1916  virtual void DeleteFromGraph();
1917  virtual void InternalSetOperandAt(int index, HValue* value) {
1918    inputs_[index] = value;
1919  }
1920
1921 private:
1922  ZoneList<HValue*> inputs_;
1923  int merged_index_;
1924
1925  int non_phi_uses_[Representation::kNumRepresentations];
1926  int indirect_uses_[Representation::kNumRepresentations];
1927  int phi_id_;
1928  bool is_live_;
1929};
1930
1931
1932class HArgumentsObject: public HTemplateInstruction<0> {
1933 public:
1934  HArgumentsObject() {
1935    set_representation(Representation::Tagged());
1936    SetFlag(kIsArguments);
1937  }
1938
1939  virtual Representation RequiredInputRepresentation(int index) const {
1940    return Representation::None();
1941  }
1942
1943  DECLARE_CONCRETE_INSTRUCTION(ArgumentsObject, "arguments-object")
1944};
1945
1946
1947class HConstant: public HTemplateInstruction<0> {
1948 public:
1949  HConstant(Handle<Object> handle, Representation r);
1950
1951  Handle<Object> handle() const { return handle_; }
1952
1953  bool InOldSpace() const { return !HEAP->InNewSpace(*handle_); }
1954
1955  virtual Representation RequiredInputRepresentation(int index) const {
1956    return Representation::None();
1957  }
1958
1959  virtual bool EmitAtUses() { return !representation().IsDouble(); }
1960  virtual void PrintDataTo(StringStream* stream);
1961  virtual HType CalculateInferredType();
1962  bool IsInteger() const { return handle_->IsSmi(); }
1963  HConstant* CopyToRepresentation(Representation r) const;
1964  HConstant* CopyToTruncatedInt32() const;
1965  bool HasInteger32Value() const { return has_int32_value_; }
1966  int32_t Integer32Value() const {
1967    ASSERT(HasInteger32Value());
1968    return int32_value_;
1969  }
1970  bool HasDoubleValue() const { return has_double_value_; }
1971  double DoubleValue() const {
1972    ASSERT(HasDoubleValue());
1973    return double_value_;
1974  }
1975  bool HasStringValue() const { return handle_->IsString(); }
1976
1977  bool ToBoolean() const;
1978
1979  virtual intptr_t Hashcode() {
1980    ASSERT(!HEAP->allow_allocation(false));
1981    return reinterpret_cast<intptr_t>(*handle());
1982  }
1983
1984#ifdef DEBUG
1985  virtual void Verify() { }
1986#endif
1987
1988  DECLARE_CONCRETE_INSTRUCTION(Constant, "constant")
1989
1990 protected:
1991  virtual Range* InferRange();
1992
1993  virtual bool DataEquals(HValue* other) {
1994    HConstant* other_constant = HConstant::cast(other);
1995    return handle().is_identical_to(other_constant->handle());
1996  }
1997
1998 private:
1999  Handle<Object> handle_;
2000  HType constant_type_;
2001
2002  // The following two values represent the int32 and the double value of the
2003  // given constant if there is a lossless conversion between the constant
2004  // and the specific representation.
2005  bool has_int32_value_;
2006  int32_t int32_value_;
2007  bool has_double_value_;
2008  double double_value_;
2009};
2010
2011
2012class HBinaryOperation: public HTemplateInstruction<2> {
2013 public:
2014  HBinaryOperation(HValue* left, HValue* right) {
2015    ASSERT(left != NULL && right != NULL);
2016    SetOperandAt(0, left);
2017    SetOperandAt(1, right);
2018  }
2019
2020  HValue* left() { return OperandAt(0); }
2021  HValue* right() { return OperandAt(1); }
2022
2023  // TODO(kasperl): Move these helpers to the IA-32 Lithium
2024  // instruction sequence builder.
2025  HValue* LeastConstantOperand() {
2026    if (IsCommutative() && left()->IsConstant()) return right();
2027    return left();
2028  }
2029  HValue* MostConstantOperand() {
2030    if (IsCommutative() && left()->IsConstant()) return left();
2031    return right();
2032  }
2033
2034  virtual bool IsCommutative() const { return false; }
2035
2036  virtual void PrintDataTo(StringStream* stream);
2037
2038  DECLARE_INSTRUCTION(BinaryOperation)
2039};
2040
2041
2042class HApplyArguments: public HTemplateInstruction<4> {
2043 public:
2044  HApplyArguments(HValue* function,
2045                  HValue* receiver,
2046                  HValue* length,
2047                  HValue* elements) {
2048    set_representation(Representation::Tagged());
2049    SetOperandAt(0, function);
2050    SetOperandAt(1, receiver);
2051    SetOperandAt(2, length);
2052    SetOperandAt(3, elements);
2053    SetAllSideEffects();
2054  }
2055
2056  virtual Representation RequiredInputRepresentation(int index) const {
2057    // The length is untagged, all other inputs are tagged.
2058    return (index == 2)
2059        ? Representation::Integer32()
2060        : Representation::Tagged();
2061  }
2062
2063  HValue* function() { return OperandAt(0); }
2064  HValue* receiver() { return OperandAt(1); }
2065  HValue* length() { return OperandAt(2); }
2066  HValue* elements() { return OperandAt(3); }
2067
2068  DECLARE_CONCRETE_INSTRUCTION(ApplyArguments, "apply_arguments")
2069};
2070
2071
2072class HArgumentsElements: public HTemplateInstruction<0> {
2073 public:
2074  HArgumentsElements() {
2075    // The value produced by this instruction is a pointer into the stack
2076    // that looks as if it was a smi because of alignment.
2077    set_representation(Representation::Tagged());
2078    SetFlag(kUseGVN);
2079  }
2080
2081  DECLARE_CONCRETE_INSTRUCTION(ArgumentsElements, "arguments_elements")
2082
2083  virtual Representation RequiredInputRepresentation(int index) const {
2084    return Representation::None();
2085  }
2086
2087 protected:
2088  virtual bool DataEquals(HValue* other) { return true; }
2089};
2090
2091
2092class HArgumentsLength: public HUnaryOperation {
2093 public:
2094  explicit HArgumentsLength(HValue* value) : HUnaryOperation(value) {
2095    set_representation(Representation::Integer32());
2096    SetFlag(kUseGVN);
2097  }
2098
2099  virtual Representation RequiredInputRepresentation(int index) const {
2100    return Representation::Tagged();
2101  }
2102
2103  DECLARE_CONCRETE_INSTRUCTION(ArgumentsLength, "arguments_length")
2104
2105 protected:
2106  virtual bool DataEquals(HValue* other) { return true; }
2107};
2108
2109
2110class HAccessArgumentsAt: public HTemplateInstruction<3> {
2111 public:
2112  HAccessArgumentsAt(HValue* arguments, HValue* length, HValue* index) {
2113    set_representation(Representation::Tagged());
2114    SetFlag(kUseGVN);
2115    SetOperandAt(0, arguments);
2116    SetOperandAt(1, length);
2117    SetOperandAt(2, index);
2118  }
2119
2120  virtual void PrintDataTo(StringStream* stream);
2121
2122  virtual Representation RequiredInputRepresentation(int index) const {
2123    // The arguments elements is considered tagged.
2124    return index == 0
2125        ? Representation::Tagged()
2126        : Representation::Integer32();
2127  }
2128
2129  HValue* arguments() { return OperandAt(0); }
2130  HValue* length() { return OperandAt(1); }
2131  HValue* index() { return OperandAt(2); }
2132
2133  DECLARE_CONCRETE_INSTRUCTION(AccessArgumentsAt, "access_arguments_at")
2134
2135  virtual bool DataEquals(HValue* other) { return true; }
2136};
2137
2138
2139class HBoundsCheck: public HBinaryOperation {
2140 public:
2141  HBoundsCheck(HValue* index, HValue* length)
2142      : HBinaryOperation(index, length) {
2143    set_representation(Representation::Integer32());
2144    SetFlag(kUseGVN);
2145  }
2146
2147  virtual bool IsCheckInstruction() const { return true; }
2148
2149  virtual Representation RequiredInputRepresentation(int index) const {
2150    return Representation::Integer32();
2151  }
2152
2153#ifdef DEBUG
2154  virtual void Verify();
2155#endif
2156
2157  HValue* index() { return left(); }
2158  HValue* length() { return right(); }
2159
2160  DECLARE_CONCRETE_INSTRUCTION(BoundsCheck, "bounds_check")
2161
2162 protected:
2163  virtual bool DataEquals(HValue* other) { return true; }
2164};
2165
2166
2167class HBitwiseBinaryOperation: public HBinaryOperation {
2168 public:
2169  HBitwiseBinaryOperation(HValue* left, HValue* right)
2170      : HBinaryOperation(left, right) {
2171    set_representation(Representation::Tagged());
2172    SetFlag(kFlexibleRepresentation);
2173    SetAllSideEffects();
2174  }
2175
2176  virtual Representation RequiredInputRepresentation(int index) const {
2177    return representation();
2178  }
2179
2180  virtual void RepresentationChanged(Representation to) {
2181    if (!to.IsTagged()) {
2182      ASSERT(to.IsInteger32());
2183      ClearAllSideEffects();
2184      SetFlag(kTruncatingToInt32);
2185      SetFlag(kUseGVN);
2186    }
2187  }
2188
2189  virtual HType CalculateInferredType();
2190
2191  DECLARE_INSTRUCTION(BitwiseBinaryOperation)
2192};
2193
2194
2195class HArithmeticBinaryOperation: public HBinaryOperation {
2196 public:
2197  HArithmeticBinaryOperation(HValue* left, HValue* right)
2198      : HBinaryOperation(left, right) {
2199    set_representation(Representation::Tagged());
2200    SetFlag(kFlexibleRepresentation);
2201    SetAllSideEffects();
2202  }
2203
2204  virtual void RepresentationChanged(Representation to) {
2205    if (!to.IsTagged()) {
2206      ClearAllSideEffects();
2207      SetFlag(kUseGVN);
2208    }
2209  }
2210
2211  virtual HType CalculateInferredType();
2212  virtual Representation RequiredInputRepresentation(int index) const {
2213    return representation();
2214  }
2215  virtual Representation InferredRepresentation() {
2216    if (left()->representation().Equals(right()->representation())) {
2217      return left()->representation();
2218    }
2219    return HValue::InferredRepresentation();
2220  }
2221
2222  DECLARE_INSTRUCTION(ArithmeticBinaryOperation)
2223};
2224
2225
2226class HCompare: public HBinaryOperation {
2227 public:
2228  HCompare(HValue* left, HValue* right, Token::Value token)
2229      : HBinaryOperation(left, right), token_(token) {
2230    ASSERT(Token::IsCompareOp(token));
2231    set_representation(Representation::Tagged());
2232    SetAllSideEffects();
2233  }
2234
2235  void SetInputRepresentation(Representation r);
2236
2237  virtual bool EmitAtUses() {
2238    return !HasSideEffects() && (uses()->length() <= 1);
2239  }
2240
2241  virtual Representation RequiredInputRepresentation(int index) const {
2242    return input_representation_;
2243  }
2244  Representation GetInputRepresentation() const {
2245    return input_representation_;
2246  }
2247  Token::Value token() const { return token_; }
2248  virtual void PrintDataTo(StringStream* stream);
2249
2250  virtual HType CalculateInferredType();
2251
2252  virtual intptr_t Hashcode() {
2253    return HValue::Hashcode() * 7 + token_;
2254  }
2255
2256  DECLARE_CONCRETE_INSTRUCTION(Compare, "compare")
2257
2258 protected:
2259  virtual bool DataEquals(HValue* other) {
2260    HCompare* comp = HCompare::cast(other);
2261    return token_ == comp->token();
2262  }
2263
2264 private:
2265  Representation input_representation_;
2266  Token::Value token_;
2267};
2268
2269
2270class HCompareJSObjectEq: public HBinaryOperation {
2271 public:
2272  HCompareJSObjectEq(HValue* left, HValue* right)
2273      : HBinaryOperation(left, right) {
2274    set_representation(Representation::Tagged());
2275    SetFlag(kUseGVN);
2276    SetFlag(kDependsOnMaps);
2277  }
2278
2279  virtual bool EmitAtUses() {
2280    return !HasSideEffects() && (uses()->length() <= 1);
2281  }
2282
2283  virtual Representation RequiredInputRepresentation(int index) const {
2284    return Representation::Tagged();
2285  }
2286  virtual HType CalculateInferredType();
2287
2288  DECLARE_CONCRETE_INSTRUCTION(CompareJSObjectEq, "compare-js-object-eq")
2289
2290 protected:
2291  virtual bool DataEquals(HValue* other) { return true; }
2292};
2293
2294
2295class HUnaryPredicate: public HUnaryOperation {
2296 public:
2297  explicit HUnaryPredicate(HValue* value) : HUnaryOperation(value) {
2298    set_representation(Representation::Tagged());
2299    SetFlag(kUseGVN);
2300  }
2301
2302  virtual bool EmitAtUses() {
2303    return !HasSideEffects() && (uses()->length() <= 1);
2304  }
2305
2306  virtual Representation RequiredInputRepresentation(int index) const {
2307    return Representation::Tagged();
2308  }
2309  virtual HType CalculateInferredType();
2310};
2311
2312
2313class HIsNull: public HUnaryPredicate {
2314 public:
2315  HIsNull(HValue* value, bool is_strict)
2316      : HUnaryPredicate(value), is_strict_(is_strict) { }
2317
2318  bool is_strict() const { return is_strict_; }
2319
2320  DECLARE_CONCRETE_INSTRUCTION(IsNull, "is_null")
2321
2322 protected:
2323  virtual bool DataEquals(HValue* other) {
2324    HIsNull* b = HIsNull::cast(other);
2325    return is_strict_ == b->is_strict();
2326  }
2327
2328 private:
2329  bool is_strict_;
2330};
2331
2332
2333class HIsObject: public HUnaryPredicate {
2334 public:
2335  explicit HIsObject(HValue* value) : HUnaryPredicate(value) { }
2336
2337  DECLARE_CONCRETE_INSTRUCTION(IsObject, "is_object")
2338
2339 protected:
2340  virtual bool DataEquals(HValue* other) { return true; }
2341};
2342
2343
2344class HIsSmi: public HUnaryPredicate {
2345 public:
2346  explicit HIsSmi(HValue* value) : HUnaryPredicate(value) { }
2347
2348  DECLARE_CONCRETE_INSTRUCTION(IsSmi, "is_smi")
2349
2350 protected:
2351  virtual bool DataEquals(HValue* other) { return true; }
2352};
2353
2354
2355class HIsConstructCall: public HTemplateInstruction<0> {
2356 public:
2357  HIsConstructCall() {
2358    set_representation(Representation::Tagged());
2359    SetFlag(kUseGVN);
2360  }
2361
2362  virtual bool EmitAtUses() {
2363    return !HasSideEffects() && (uses()->length() <= 1);
2364  }
2365
2366  virtual Representation RequiredInputRepresentation(int index) const {
2367    return Representation::None();
2368  }
2369
2370  DECLARE_CONCRETE_INSTRUCTION(IsConstructCall, "is_construct_call")
2371
2372 protected:
2373  virtual bool DataEquals(HValue* other) { return true; }
2374};
2375
2376
2377class HHasInstanceType: public HUnaryPredicate {
2378 public:
2379  HHasInstanceType(HValue* value, InstanceType type)
2380      : HUnaryPredicate(value), from_(type), to_(type) { }
2381  HHasInstanceType(HValue* value, InstanceType from, InstanceType to)
2382      : HUnaryPredicate(value), from_(from), to_(to) {
2383    ASSERT(to == LAST_TYPE);  // Others not implemented yet in backend.
2384  }
2385
2386  InstanceType from() { return from_; }
2387  InstanceType to() { return to_; }
2388
2389  virtual void PrintDataTo(StringStream* stream);
2390
2391  DECLARE_CONCRETE_INSTRUCTION(HasInstanceType, "has_instance_type")
2392
2393 protected:
2394  virtual bool DataEquals(HValue* other) {
2395    HHasInstanceType* b = HHasInstanceType::cast(other);
2396    return (from_ == b->from()) && (to_ == b->to());
2397  }
2398
2399 private:
2400  InstanceType from_;
2401  InstanceType to_;  // Inclusive range, not all combinations work.
2402};
2403
2404
2405class HHasCachedArrayIndex: public HUnaryPredicate {
2406 public:
2407  explicit HHasCachedArrayIndex(HValue* value) : HUnaryPredicate(value) { }
2408
2409  DECLARE_CONCRETE_INSTRUCTION(HasCachedArrayIndex, "has_cached_array_index")
2410
2411 protected:
2412  virtual bool DataEquals(HValue* other) { return true; }
2413};
2414
2415
2416class HGetCachedArrayIndex: public HUnaryPredicate {
2417 public:
2418  explicit HGetCachedArrayIndex(HValue* value) : HUnaryPredicate(value) { }
2419
2420  DECLARE_CONCRETE_INSTRUCTION(GetCachedArrayIndex, "get_cached_array_index")
2421
2422 protected:
2423  virtual bool DataEquals(HValue* other) { return true; }
2424};
2425
2426
2427class HClassOfTest: public HUnaryPredicate {
2428 public:
2429  HClassOfTest(HValue* value, Handle<String> class_name)
2430      : HUnaryPredicate(value), class_name_(class_name) { }
2431
2432  DECLARE_CONCRETE_INSTRUCTION(ClassOfTest, "class_of_test")
2433
2434  virtual void PrintDataTo(StringStream* stream);
2435
2436  Handle<String> class_name() const { return class_name_; }
2437
2438 protected:
2439  virtual bool DataEquals(HValue* other) {
2440    HClassOfTest* b = HClassOfTest::cast(other);
2441    return class_name_.is_identical_to(b->class_name_);
2442  }
2443
2444 private:
2445  Handle<String> class_name_;
2446};
2447
2448
2449class HTypeofIs: public HUnaryPredicate {
2450 public:
2451  HTypeofIs(HValue* value, Handle<String> type_literal)
2452      : HUnaryPredicate(value), type_literal_(type_literal) { }
2453
2454  Handle<String> type_literal() { return type_literal_; }
2455  virtual void PrintDataTo(StringStream* stream);
2456
2457  DECLARE_CONCRETE_INSTRUCTION(TypeofIs, "typeof_is")
2458
2459 protected:
2460  virtual bool DataEquals(HValue* other) {
2461    HTypeofIs* b = HTypeofIs::cast(other);
2462    return type_literal_.is_identical_to(b->type_literal_);
2463  }
2464
2465 private:
2466  Handle<String> type_literal_;
2467};
2468
2469
2470class HInstanceOf: public HTemplateInstruction<3> {
2471 public:
2472  HInstanceOf(HValue* context, HValue* left, HValue* right) {
2473    SetOperandAt(0, context);
2474    SetOperandAt(1, left);
2475    SetOperandAt(2, right);
2476    set_representation(Representation::Tagged());
2477    SetAllSideEffects();
2478  }
2479
2480  HValue* context() { return OperandAt(0); }
2481  HValue* left() { return OperandAt(1); }
2482  HValue* right() { return OperandAt(2); }
2483
2484  virtual bool EmitAtUses() {
2485    return !HasSideEffects() && (uses()->length() <= 1);
2486  }
2487
2488  virtual Representation RequiredInputRepresentation(int index) const {
2489    return Representation::Tagged();
2490  }
2491
2492  virtual void PrintDataTo(StringStream* stream);
2493
2494  DECLARE_CONCRETE_INSTRUCTION(InstanceOf, "instance_of")
2495};
2496
2497
2498class HInstanceOfKnownGlobal: public HUnaryOperation {
2499 public:
2500  HInstanceOfKnownGlobal(HValue* left, Handle<JSFunction> right)
2501      : HUnaryOperation(left), function_(right) {
2502    set_representation(Representation::Tagged());
2503    SetAllSideEffects();
2504  }
2505
2506  Handle<JSFunction> function() { return function_; }
2507
2508  virtual Representation RequiredInputRepresentation(int index) const {
2509    return Representation::Tagged();
2510  }
2511
2512  DECLARE_CONCRETE_INSTRUCTION(InstanceOfKnownGlobal,
2513                               "instance_of_known_global")
2514
2515 private:
2516  Handle<JSFunction> function_;
2517};
2518
2519
2520class HPower: public HBinaryOperation {
2521 public:
2522  HPower(HValue* left, HValue* right)
2523      : HBinaryOperation(left, right) {
2524    set_representation(Representation::Double());
2525    SetFlag(kUseGVN);
2526  }
2527
2528  virtual Representation RequiredInputRepresentation(int index) const {
2529    return (index == 1) ? Representation::None() : Representation::Double();
2530  }
2531
2532  DECLARE_CONCRETE_INSTRUCTION(Power, "power")
2533
2534 protected:
2535  virtual bool DataEquals(HValue* other) { return true; }
2536};
2537
2538
2539class HAdd: public HArithmeticBinaryOperation {
2540 public:
2541  HAdd(HValue* left, HValue* right) : HArithmeticBinaryOperation(left, right) {
2542    SetFlag(kCanOverflow);
2543  }
2544
2545  // Add is only commutative if two integer values are added and not if two
2546  // tagged values are added (because it might be a String concatenation).
2547  virtual bool IsCommutative() const {
2548    return !representation().IsTagged();
2549  }
2550
2551  virtual HValue* EnsureAndPropagateNotMinusZero(BitVector* visited);
2552
2553  virtual HType CalculateInferredType();
2554
2555  DECLARE_CONCRETE_INSTRUCTION(Add, "add")
2556
2557 protected:
2558  virtual bool DataEquals(HValue* other) { return true; }
2559
2560  virtual Range* InferRange();
2561};
2562
2563
2564class HSub: public HArithmeticBinaryOperation {
2565 public:
2566  HSub(HValue* left, HValue* right) : HArithmeticBinaryOperation(left, right) {
2567    SetFlag(kCanOverflow);
2568  }
2569
2570  virtual HValue* EnsureAndPropagateNotMinusZero(BitVector* visited);
2571
2572  DECLARE_CONCRETE_INSTRUCTION(Sub, "sub")
2573
2574 protected:
2575  virtual bool DataEquals(HValue* other) { return true; }
2576
2577  virtual Range* InferRange();
2578};
2579
2580
2581class HMul: public HArithmeticBinaryOperation {
2582 public:
2583  HMul(HValue* left, HValue* right) : HArithmeticBinaryOperation(left, right) {
2584    SetFlag(kCanOverflow);
2585  }
2586
2587  virtual HValue* EnsureAndPropagateNotMinusZero(BitVector* visited);
2588
2589  // Only commutative if it is certain that not two objects are multiplicated.
2590  virtual bool IsCommutative() const {
2591    return !representation().IsTagged();
2592  }
2593
2594  DECLARE_CONCRETE_INSTRUCTION(Mul, "mul")
2595
2596 protected:
2597  virtual bool DataEquals(HValue* other) { return true; }
2598
2599  virtual Range* InferRange();
2600};
2601
2602
2603class HMod: public HArithmeticBinaryOperation {
2604 public:
2605  HMod(HValue* left, HValue* right) : HArithmeticBinaryOperation(left, right) {
2606    SetFlag(kCanBeDivByZero);
2607  }
2608
2609  bool HasPowerOf2Divisor() {
2610    if (right()->IsConstant() &&
2611        HConstant::cast(right())->HasInteger32Value()) {
2612      int32_t value = HConstant::cast(right())->Integer32Value();
2613      return value != 0 && (IsPowerOf2(value) || IsPowerOf2(-value));
2614    }
2615
2616    return false;
2617  }
2618
2619  virtual HValue* EnsureAndPropagateNotMinusZero(BitVector* visited);
2620
2621  DECLARE_CONCRETE_INSTRUCTION(Mod, "mod")
2622
2623 protected:
2624  virtual bool DataEquals(HValue* other) { return true; }
2625
2626  virtual Range* InferRange();
2627};
2628
2629
2630class HDiv: public HArithmeticBinaryOperation {
2631 public:
2632  HDiv(HValue* left, HValue* right) : HArithmeticBinaryOperation(left, right) {
2633    SetFlag(kCanBeDivByZero);
2634    SetFlag(kCanOverflow);
2635  }
2636
2637  virtual HValue* EnsureAndPropagateNotMinusZero(BitVector* visited);
2638
2639  DECLARE_CONCRETE_INSTRUCTION(Div, "div")
2640
2641 protected:
2642  virtual bool DataEquals(HValue* other) { return true; }
2643
2644  virtual Range* InferRange();
2645};
2646
2647
2648class HBitAnd: public HBitwiseBinaryOperation {
2649 public:
2650  HBitAnd(HValue* left, HValue* right)
2651      : HBitwiseBinaryOperation(left, right) { }
2652
2653  virtual bool IsCommutative() const { return true; }
2654  virtual HType CalculateInferredType();
2655
2656  DECLARE_CONCRETE_INSTRUCTION(BitAnd, "bit_and")
2657
2658 protected:
2659  virtual bool DataEquals(HValue* other) { return true; }
2660
2661  virtual Range* InferRange();
2662};
2663
2664
2665class HBitXor: public HBitwiseBinaryOperation {
2666 public:
2667  HBitXor(HValue* left, HValue* right)
2668      : HBitwiseBinaryOperation(left, right) { }
2669
2670  virtual bool IsCommutative() const { return true; }
2671  virtual HType CalculateInferredType();
2672
2673  DECLARE_CONCRETE_INSTRUCTION(BitXor, "bit_xor")
2674
2675 protected:
2676  virtual bool DataEquals(HValue* other) { return true; }
2677};
2678
2679
2680class HBitOr: public HBitwiseBinaryOperation {
2681 public:
2682  HBitOr(HValue* left, HValue* right)
2683      : HBitwiseBinaryOperation(left, right) { }
2684
2685  virtual bool IsCommutative() const { return true; }
2686  virtual HType CalculateInferredType();
2687
2688  DECLARE_CONCRETE_INSTRUCTION(BitOr, "bit_or")
2689
2690 protected:
2691  virtual bool DataEquals(HValue* other) { return true; }
2692
2693  virtual Range* InferRange();
2694};
2695
2696
2697class HShl: public HBitwiseBinaryOperation {
2698 public:
2699  HShl(HValue* left, HValue* right)
2700      : HBitwiseBinaryOperation(left, right) { }
2701
2702  virtual Range* InferRange();
2703  virtual HType CalculateInferredType();
2704
2705  DECLARE_CONCRETE_INSTRUCTION(Shl, "shl")
2706
2707 protected:
2708  virtual bool DataEquals(HValue* other) { return true; }
2709};
2710
2711
2712class HShr: public HBitwiseBinaryOperation {
2713 public:
2714  HShr(HValue* left, HValue* right)
2715      : HBitwiseBinaryOperation(left, right) { }
2716
2717  virtual HType CalculateInferredType();
2718
2719  DECLARE_CONCRETE_INSTRUCTION(Shr, "shr")
2720
2721 protected:
2722  virtual bool DataEquals(HValue* other) { return true; }
2723};
2724
2725
2726class HSar: public HBitwiseBinaryOperation {
2727 public:
2728  HSar(HValue* left, HValue* right)
2729      : HBitwiseBinaryOperation(left, right) { }
2730
2731  virtual Range* InferRange();
2732  virtual HType CalculateInferredType();
2733
2734  DECLARE_CONCRETE_INSTRUCTION(Sar, "sar")
2735
2736 protected:
2737  virtual bool DataEquals(HValue* other) { return true; }
2738};
2739
2740
2741class HOsrEntry: public HTemplateInstruction<0> {
2742 public:
2743  explicit HOsrEntry(int ast_id) : ast_id_(ast_id) {
2744    SetFlag(kChangesOsrEntries);
2745  }
2746
2747  int ast_id() const { return ast_id_; }
2748
2749  virtual Representation RequiredInputRepresentation(int index) const {
2750    return Representation::None();
2751  }
2752
2753  DECLARE_CONCRETE_INSTRUCTION(OsrEntry, "osr_entry")
2754
2755 private:
2756  int ast_id_;
2757};
2758
2759
2760class HParameter: public HTemplateInstruction<0> {
2761 public:
2762  explicit HParameter(unsigned index) : index_(index) {
2763    set_representation(Representation::Tagged());
2764  }
2765
2766  unsigned index() const { return index_; }
2767
2768  virtual void PrintDataTo(StringStream* stream);
2769
2770  virtual Representation RequiredInputRepresentation(int index) const {
2771    return Representation::None();
2772  }
2773
2774  DECLARE_CONCRETE_INSTRUCTION(Parameter, "parameter")
2775
2776 private:
2777  unsigned index_;
2778};
2779
2780
2781class HCallStub: public HUnaryCall {
2782 public:
2783  HCallStub(HValue* context, CodeStub::Major major_key, int argument_count)
2784      : HUnaryCall(context, argument_count),
2785        major_key_(major_key),
2786        transcendental_type_(TranscendentalCache::kNumberOfCaches) {
2787  }
2788
2789  CodeStub::Major major_key() { return major_key_; }
2790
2791  HValue* context() { return value(); }
2792
2793  void set_transcendental_type(TranscendentalCache::Type transcendental_type) {
2794    transcendental_type_ = transcendental_type;
2795  }
2796  TranscendentalCache::Type transcendental_type() {
2797    return transcendental_type_;
2798  }
2799
2800  virtual void PrintDataTo(StringStream* stream);
2801
2802  virtual Representation RequiredInputRepresentation(int index) const {
2803    return Representation::Tagged();
2804  }
2805
2806  DECLARE_CONCRETE_INSTRUCTION(CallStub, "call_stub")
2807
2808 private:
2809  CodeStub::Major major_key_;
2810  TranscendentalCache::Type transcendental_type_;
2811};
2812
2813
2814class HUnknownOSRValue: public HTemplateInstruction<0> {
2815 public:
2816  HUnknownOSRValue() { set_representation(Representation::Tagged()); }
2817
2818  virtual Representation RequiredInputRepresentation(int index) const {
2819    return Representation::None();
2820  }
2821
2822  DECLARE_CONCRETE_INSTRUCTION(UnknownOSRValue, "unknown_osr_value")
2823};
2824
2825
2826class HLoadGlobalCell: public HTemplateInstruction<0> {
2827 public:
2828  HLoadGlobalCell(Handle<JSGlobalPropertyCell> cell, bool check_hole_value)
2829      : cell_(cell), check_hole_value_(check_hole_value) {
2830    set_representation(Representation::Tagged());
2831    SetFlag(kUseGVN);
2832    SetFlag(kDependsOnGlobalVars);
2833  }
2834
2835  Handle<JSGlobalPropertyCell>  cell() const { return cell_; }
2836  bool check_hole_value() const { return check_hole_value_; }
2837
2838  virtual void PrintDataTo(StringStream* stream);
2839
2840  virtual intptr_t Hashcode() {
2841    ASSERT(!HEAP->allow_allocation(false));
2842    return reinterpret_cast<intptr_t>(*cell_);
2843  }
2844
2845  virtual Representation RequiredInputRepresentation(int index) const {
2846    return Representation::None();
2847  }
2848
2849  DECLARE_CONCRETE_INSTRUCTION(LoadGlobalCell, "load_global_cell")
2850
2851 protected:
2852  virtual bool DataEquals(HValue* other) {
2853    HLoadGlobalCell* b = HLoadGlobalCell::cast(other);
2854    return cell_.is_identical_to(b->cell());
2855  }
2856
2857 private:
2858  Handle<JSGlobalPropertyCell> cell_;
2859  bool check_hole_value_;
2860};
2861
2862
2863class HLoadGlobalGeneric: public HBinaryOperation {
2864 public:
2865  HLoadGlobalGeneric(HValue* context,
2866                     HValue* global_object,
2867                     Handle<Object> name,
2868                     bool for_typeof)
2869      : HBinaryOperation(context, global_object),
2870        name_(name),
2871        for_typeof_(for_typeof) {
2872    set_representation(Representation::Tagged());
2873    SetAllSideEffects();
2874  }
2875
2876  HValue* context() { return OperandAt(0); }
2877  HValue* global_object() { return OperandAt(1); }
2878  Handle<Object> name() const { return name_; }
2879  bool for_typeof() const { return for_typeof_; }
2880
2881  virtual void PrintDataTo(StringStream* stream);
2882
2883  virtual Representation RequiredInputRepresentation(int index) const {
2884    return Representation::Tagged();
2885  }
2886
2887  DECLARE_CONCRETE_INSTRUCTION(LoadGlobalGeneric, "load_global_generic")
2888
2889 private:
2890  Handle<Object> name_;
2891  bool for_typeof_;
2892};
2893
2894
2895class HStoreGlobalCell: public HUnaryOperation {
2896 public:
2897  HStoreGlobalCell(HValue* value,
2898                   Handle<JSGlobalPropertyCell> cell,
2899                   bool check_hole_value)
2900      : HUnaryOperation(value),
2901        cell_(cell),
2902        check_hole_value_(check_hole_value) {
2903    SetFlag(kChangesGlobalVars);
2904  }
2905
2906  Handle<JSGlobalPropertyCell> cell() const { return cell_; }
2907  bool check_hole_value() const { return check_hole_value_; }
2908
2909  virtual Representation RequiredInputRepresentation(int index) const {
2910    return Representation::Tagged();
2911  }
2912  virtual void PrintDataTo(StringStream* stream);
2913
2914  DECLARE_CONCRETE_INSTRUCTION(StoreGlobalCell, "store_global_cell")
2915
2916 private:
2917  Handle<JSGlobalPropertyCell> cell_;
2918  bool check_hole_value_;
2919};
2920
2921
2922class HStoreGlobalGeneric: public HTemplateInstruction<3> {
2923 public:
2924  HStoreGlobalGeneric(HValue* context,
2925                      HValue* global_object,
2926                      Handle<Object> name,
2927                      HValue* value,
2928                      bool strict_mode)
2929      : name_(name),
2930        strict_mode_(strict_mode) {
2931    SetOperandAt(0, context);
2932    SetOperandAt(1, global_object);
2933    SetOperandAt(2, value);
2934    set_representation(Representation::Tagged());
2935    SetAllSideEffects();
2936  }
2937
2938  HValue* context() { return OperandAt(0); }
2939  HValue* global_object() { return OperandAt(1); }
2940  Handle<Object> name() const { return name_; }
2941  HValue* value() { return OperandAt(2); }
2942  bool strict_mode() { return strict_mode_; }
2943
2944  virtual void PrintDataTo(StringStream* stream);
2945
2946  virtual Representation RequiredInputRepresentation(int index) const {
2947    return Representation::Tagged();
2948  }
2949
2950  DECLARE_CONCRETE_INSTRUCTION(StoreGlobalGeneric, "store_global_generic")
2951
2952 private:
2953  Handle<Object> name_;
2954  bool strict_mode_;
2955};
2956
2957
2958class HLoadContextSlot: public HUnaryOperation {
2959 public:
2960  HLoadContextSlot(HValue* context , int slot_index)
2961      : HUnaryOperation(context), slot_index_(slot_index) {
2962    set_representation(Representation::Tagged());
2963    SetFlag(kUseGVN);
2964    SetFlag(kDependsOnContextSlots);
2965  }
2966
2967  int slot_index() const { return slot_index_; }
2968
2969  virtual Representation RequiredInputRepresentation(int index) const {
2970    return Representation::Tagged();
2971  }
2972
2973  virtual void PrintDataTo(StringStream* stream);
2974
2975  DECLARE_CONCRETE_INSTRUCTION(LoadContextSlot, "load_context_slot")
2976
2977 protected:
2978  virtual bool DataEquals(HValue* other) {
2979    HLoadContextSlot* b = HLoadContextSlot::cast(other);
2980    return (slot_index() == b->slot_index());
2981  }
2982
2983 private:
2984  int slot_index_;
2985};
2986
2987
2988static inline bool StoringValueNeedsWriteBarrier(HValue* value) {
2989  return !value->type().IsSmi() &&
2990      !(value->IsConstant() && HConstant::cast(value)->InOldSpace());
2991}
2992
2993
2994class HStoreContextSlot: public HBinaryOperation {
2995 public:
2996  HStoreContextSlot(HValue* context, int slot_index, HValue* value)
2997      : HBinaryOperation(context, value), slot_index_(slot_index) {
2998    SetFlag(kChangesContextSlots);
2999  }
3000
3001  HValue* context() { return OperandAt(0); }
3002  HValue* value() { return OperandAt(1); }
3003  int slot_index() const { return slot_index_; }
3004
3005  bool NeedsWriteBarrier() {
3006    return StoringValueNeedsWriteBarrier(value());
3007  }
3008
3009  virtual Representation RequiredInputRepresentation(int index) const {
3010    return Representation::Tagged();
3011  }
3012
3013  virtual void PrintDataTo(StringStream* stream);
3014
3015  DECLARE_CONCRETE_INSTRUCTION(StoreContextSlot, "store_context_slot")
3016
3017 private:
3018  int slot_index_;
3019};
3020
3021
3022class HLoadNamedField: public HUnaryOperation {
3023 public:
3024  HLoadNamedField(HValue* object, bool is_in_object, int offset)
3025      : HUnaryOperation(object),
3026        is_in_object_(is_in_object),
3027        offset_(offset) {
3028    set_representation(Representation::Tagged());
3029    SetFlag(kUseGVN);
3030    SetFlag(kDependsOnMaps);
3031    if (is_in_object) {
3032      SetFlag(kDependsOnInobjectFields);
3033    } else {
3034      SetFlag(kDependsOnBackingStoreFields);
3035    }
3036  }
3037
3038  HValue* object() { return OperandAt(0); }
3039  bool is_in_object() const { return is_in_object_; }
3040  int offset() const { return offset_; }
3041
3042  virtual Representation RequiredInputRepresentation(int index) const {
3043    return Representation::Tagged();
3044  }
3045  virtual void PrintDataTo(StringStream* stream);
3046
3047  DECLARE_CONCRETE_INSTRUCTION(LoadNamedField, "load_named_field")
3048
3049 protected:
3050  virtual bool DataEquals(HValue* other) {
3051    HLoadNamedField* b = HLoadNamedField::cast(other);
3052    return is_in_object_ == b->is_in_object_ && offset_ == b->offset_;
3053  }
3054
3055 private:
3056  bool is_in_object_;
3057  int offset_;
3058};
3059
3060
3061class HLoadNamedFieldPolymorphic: public HUnaryOperation {
3062 public:
3063  HLoadNamedFieldPolymorphic(HValue* object,
3064                             ZoneMapList* types,
3065                             Handle<String> name);
3066
3067  HValue* object() { return OperandAt(0); }
3068  ZoneMapList* types() { return &types_; }
3069  Handle<String> name() { return name_; }
3070  bool need_generic() { return need_generic_; }
3071
3072  virtual Representation RequiredInputRepresentation(int index) const {
3073    return Representation::Tagged();
3074  }
3075
3076  DECLARE_CONCRETE_INSTRUCTION(LoadNamedFieldPolymorphic,
3077                               "load_named_field_polymorphic")
3078
3079  static const int kMaxLoadPolymorphism = 4;
3080
3081 protected:
3082  virtual bool DataEquals(HValue* value);
3083
3084 private:
3085  ZoneMapList types_;
3086  Handle<String> name_;
3087  bool need_generic_;
3088};
3089
3090
3091
3092class HLoadNamedGeneric: public HBinaryOperation {
3093 public:
3094  HLoadNamedGeneric(HValue* context, HValue* object, Handle<Object> name)
3095      : HBinaryOperation(context, object), name_(name) {
3096    set_representation(Representation::Tagged());
3097    SetAllSideEffects();
3098  }
3099
3100  HValue* context() { return OperandAt(0); }
3101  HValue* object() { return OperandAt(1); }
3102  Handle<Object> name() const { return name_; }
3103
3104  virtual Representation RequiredInputRepresentation(int index) const {
3105    return Representation::Tagged();
3106  }
3107
3108  DECLARE_CONCRETE_INSTRUCTION(LoadNamedGeneric, "load_named_generic")
3109
3110 private:
3111  Handle<Object> name_;
3112};
3113
3114
3115class HLoadFunctionPrototype: public HUnaryOperation {
3116 public:
3117  explicit HLoadFunctionPrototype(HValue* function)
3118      : HUnaryOperation(function) {
3119    set_representation(Representation::Tagged());
3120    SetFlag(kUseGVN);
3121    SetFlag(kDependsOnCalls);
3122  }
3123
3124  HValue* function() { return OperandAt(0); }
3125
3126  virtual Representation RequiredInputRepresentation(int index) const {
3127    return Representation::Tagged();
3128  }
3129
3130  DECLARE_CONCRETE_INSTRUCTION(LoadFunctionPrototype, "load_function_prototype")
3131
3132 protected:
3133  virtual bool DataEquals(HValue* other) { return true; }
3134};
3135
3136
3137class HLoadKeyedFastElement: public HBinaryOperation {
3138 public:
3139  HLoadKeyedFastElement(HValue* obj, HValue* key) : HBinaryOperation(obj, key) {
3140    set_representation(Representation::Tagged());
3141    SetFlag(kDependsOnArrayElements);
3142    SetFlag(kUseGVN);
3143  }
3144
3145  HValue* object() { return OperandAt(0); }
3146  HValue* key() { return OperandAt(1); }
3147
3148  virtual Representation RequiredInputRepresentation(int index) const {
3149    // The key is supposed to be Integer32.
3150    return (index == 1) ? Representation::Integer32()
3151        : Representation::Tagged();
3152  }
3153
3154  virtual void PrintDataTo(StringStream* stream);
3155
3156  DECLARE_CONCRETE_INSTRUCTION(LoadKeyedFastElement,
3157                               "load_keyed_fast_element")
3158
3159 protected:
3160  virtual bool DataEquals(HValue* other) { return true; }
3161};
3162
3163
3164class HLoadKeyedSpecializedArrayElement: public HBinaryOperation {
3165 public:
3166  HLoadKeyedSpecializedArrayElement(HValue* external_elements,
3167                                    HValue* key,
3168                                    ExternalArrayType array_type)
3169      : HBinaryOperation(external_elements, key),
3170        array_type_(array_type) {
3171    if (array_type == kExternalFloatArray) {
3172      set_representation(Representation::Double());
3173    } else {
3174      set_representation(Representation::Integer32());
3175    }
3176    SetFlag(kDependsOnSpecializedArrayElements);
3177    // Native code could change the specialized array.
3178    SetFlag(kDependsOnCalls);
3179    SetFlag(kUseGVN);
3180  }
3181
3182  virtual void PrintDataTo(StringStream* stream);
3183
3184  virtual Representation RequiredInputRepresentation(int index) const {
3185    // The key is supposed to be Integer32, but the base pointer
3186    // for the element load is a naked pointer.
3187    return (index == 1) ? Representation::Integer32()
3188        : Representation::External();
3189  }
3190
3191  HValue* external_pointer() { return OperandAt(0); }
3192  HValue* key() { return OperandAt(1); }
3193  ExternalArrayType array_type() const { return array_type_; }
3194
3195  DECLARE_CONCRETE_INSTRUCTION(LoadKeyedSpecializedArrayElement,
3196                               "load_keyed_specialized_array_element")
3197
3198 protected:
3199  virtual bool DataEquals(HValue* other) {
3200    if (!other->IsLoadKeyedSpecializedArrayElement()) return false;
3201    HLoadKeyedSpecializedArrayElement* cast_other =
3202        HLoadKeyedSpecializedArrayElement::cast(other);
3203    return array_type_ == cast_other->array_type();
3204  }
3205
3206 private:
3207  ExternalArrayType array_type_;
3208};
3209
3210
3211class HLoadKeyedGeneric: public HTemplateInstruction<3> {
3212 public:
3213  HLoadKeyedGeneric(HContext* context, HValue* obj, HValue* key) {
3214    set_representation(Representation::Tagged());
3215    SetOperandAt(0, obj);
3216    SetOperandAt(1, key);
3217    SetOperandAt(2, context);
3218    SetAllSideEffects();
3219  }
3220
3221  HValue* object() { return OperandAt(0); }
3222  HValue* key() { return OperandAt(1); }
3223  HValue* context() { return OperandAt(2); }
3224
3225  virtual void PrintDataTo(StringStream* stream);
3226
3227  virtual Representation RequiredInputRepresentation(int index) const {
3228    return Representation::Tagged();
3229  }
3230
3231  DECLARE_CONCRETE_INSTRUCTION(LoadKeyedGeneric, "load_keyed_generic")
3232};
3233
3234
3235class HStoreNamedField: public HBinaryOperation {
3236 public:
3237  HStoreNamedField(HValue* obj,
3238                   Handle<String> name,
3239                   HValue* val,
3240                   bool in_object,
3241                   int offset)
3242      : HBinaryOperation(obj, val),
3243        name_(name),
3244        is_in_object_(in_object),
3245        offset_(offset) {
3246    if (is_in_object_) {
3247      SetFlag(kChangesInobjectFields);
3248    } else {
3249      SetFlag(kChangesBackingStoreFields);
3250    }
3251  }
3252
3253  DECLARE_CONCRETE_INSTRUCTION(StoreNamedField, "store_named_field")
3254
3255  virtual Representation RequiredInputRepresentation(int index) const {
3256    return Representation::Tagged();
3257  }
3258  virtual void PrintDataTo(StringStream* stream);
3259
3260  HValue* object() { return OperandAt(0); }
3261  HValue* value() { return OperandAt(1); }
3262
3263  Handle<String> name() const { return name_; }
3264  bool is_in_object() const { return is_in_object_; }
3265  int offset() const { return offset_; }
3266  Handle<Map> transition() const { return transition_; }
3267  void set_transition(Handle<Map> map) { transition_ = map; }
3268
3269  bool NeedsWriteBarrier() {
3270    return StoringValueNeedsWriteBarrier(value());
3271  }
3272
3273 private:
3274  Handle<String> name_;
3275  bool is_in_object_;
3276  int offset_;
3277  Handle<Map> transition_;
3278};
3279
3280
3281class HStoreNamedGeneric: public HTemplateInstruction<3> {
3282 public:
3283  HStoreNamedGeneric(HValue* context,
3284                     HValue* object,
3285                     Handle<String> name,
3286                     HValue* value,
3287                     bool strict_mode)
3288      : name_(name),
3289        strict_mode_(strict_mode) {
3290    SetOperandAt(0, object);
3291    SetOperandAt(1, value);
3292    SetOperandAt(2, context);
3293    SetAllSideEffects();
3294  }
3295
3296  HValue* object() { return OperandAt(0); }
3297  HValue* value() { return OperandAt(1); }
3298  HValue* context() { return OperandAt(2); }
3299  Handle<String> name() { return name_; }
3300  bool strict_mode() { return strict_mode_; }
3301
3302  virtual void PrintDataTo(StringStream* stream);
3303
3304  virtual Representation RequiredInputRepresentation(int index) const {
3305    return Representation::Tagged();
3306  }
3307
3308  DECLARE_CONCRETE_INSTRUCTION(StoreNamedGeneric, "store_named_generic")
3309
3310 private:
3311  Handle<String> name_;
3312  bool strict_mode_;
3313};
3314
3315
3316class HStoreKeyedFastElement: public HTemplateInstruction<3> {
3317 public:
3318  HStoreKeyedFastElement(HValue* obj, HValue* key, HValue* val) {
3319    SetOperandAt(0, obj);
3320    SetOperandAt(1, key);
3321    SetOperandAt(2, val);
3322    SetFlag(kChangesArrayElements);
3323  }
3324
3325  virtual Representation RequiredInputRepresentation(int index) const {
3326    // The key is supposed to be Integer32.
3327    return (index == 1) ? Representation::Integer32()
3328        : Representation::Tagged();
3329  }
3330
3331  HValue* object() { return OperandAt(0); }
3332  HValue* key() { return OperandAt(1); }
3333  HValue* value() { return OperandAt(2); }
3334
3335  bool NeedsWriteBarrier() {
3336    return StoringValueNeedsWriteBarrier(value());
3337  }
3338
3339  virtual void PrintDataTo(StringStream* stream);
3340
3341  DECLARE_CONCRETE_INSTRUCTION(StoreKeyedFastElement,
3342                               "store_keyed_fast_element")
3343};
3344
3345
3346class HStoreKeyedSpecializedArrayElement: public HTemplateInstruction<3> {
3347 public:
3348  HStoreKeyedSpecializedArrayElement(HValue* external_elements,
3349                                     HValue* key,
3350                                     HValue* val,
3351                                     ExternalArrayType array_type)
3352      : array_type_(array_type) {
3353    SetFlag(kChangesSpecializedArrayElements);
3354    SetOperandAt(0, external_elements);
3355    SetOperandAt(1, key);
3356    SetOperandAt(2, val);
3357  }
3358
3359  virtual void PrintDataTo(StringStream* stream);
3360
3361  virtual Representation RequiredInputRepresentation(int index) const {
3362    if (index == 0) {
3363      return Representation::External();
3364    } else {
3365      if (index == 2 && array_type() == kExternalFloatArray) {
3366        return Representation::Double();
3367      } else {
3368        return Representation::Integer32();
3369      }
3370    }
3371  }
3372
3373  HValue* external_pointer() { return OperandAt(0); }
3374  HValue* key() { return OperandAt(1); }
3375  HValue* value() { return OperandAt(2); }
3376  ExternalArrayType array_type() const { return array_type_; }
3377
3378  DECLARE_CONCRETE_INSTRUCTION(StoreKeyedSpecializedArrayElement,
3379                               "store_keyed_specialized_array_element")
3380 private:
3381  ExternalArrayType array_type_;
3382};
3383
3384
3385class HStoreKeyedGeneric: public HTemplateInstruction<4> {
3386 public:
3387  HStoreKeyedGeneric(HValue* context,
3388                     HValue* object,
3389                     HValue* key,
3390                     HValue* value,
3391                     bool strict_mode)
3392      : strict_mode_(strict_mode) {
3393    SetOperandAt(0, object);
3394    SetOperandAt(1, key);
3395    SetOperandAt(2, value);
3396    SetOperandAt(3, context);
3397    SetAllSideEffects();
3398  }
3399
3400  HValue* object() { return OperandAt(0); }
3401  HValue* key() { return OperandAt(1); }
3402  HValue* value() { return OperandAt(2); }
3403  HValue* context() { return OperandAt(3); }
3404  bool strict_mode() { return strict_mode_; }
3405
3406  virtual Representation RequiredInputRepresentation(int index) const {
3407    return Representation::Tagged();
3408  }
3409
3410  virtual void PrintDataTo(StringStream* stream);
3411
3412  DECLARE_CONCRETE_INSTRUCTION(StoreKeyedGeneric, "store_keyed_generic")
3413
3414 private:
3415  bool strict_mode_;
3416};
3417
3418
3419class HStringCharCodeAt: public HBinaryOperation {
3420 public:
3421  HStringCharCodeAt(HValue* string, HValue* index)
3422      : HBinaryOperation(string, index) {
3423    set_representation(Representation::Integer32());
3424    SetFlag(kUseGVN);
3425    SetFlag(kDependsOnMaps);
3426  }
3427
3428  virtual Representation RequiredInputRepresentation(int index) const {
3429    // The index is supposed to be Integer32.
3430    return (index == 1) ? Representation::Integer32()
3431        : Representation::Tagged();
3432  }
3433
3434  HValue* string() { return OperandAt(0); }
3435  HValue* index() { return OperandAt(1); }
3436
3437  DECLARE_CONCRETE_INSTRUCTION(StringCharCodeAt, "string_char_code_at")
3438
3439 protected:
3440  virtual bool DataEquals(HValue* other) { return true; }
3441
3442  virtual Range* InferRange() {
3443    return new Range(0, String::kMaxUC16CharCode);
3444  }
3445};
3446
3447
3448class HStringCharFromCode: public HUnaryOperation {
3449 public:
3450  explicit HStringCharFromCode(HValue* char_code) : HUnaryOperation(char_code) {
3451    set_representation(Representation::Tagged());
3452    SetFlag(kUseGVN);
3453  }
3454
3455  virtual Representation RequiredInputRepresentation(int index) const {
3456    return Representation::Integer32();
3457  }
3458
3459  virtual bool DataEquals(HValue* other) { return true; }
3460
3461  DECLARE_CONCRETE_INSTRUCTION(StringCharFromCode, "string_char_from_code")
3462};
3463
3464
3465class HStringLength: public HUnaryOperation {
3466 public:
3467  explicit HStringLength(HValue* string) : HUnaryOperation(string) {
3468    set_representation(Representation::Tagged());
3469    SetFlag(kUseGVN);
3470    SetFlag(kDependsOnMaps);
3471  }
3472
3473  virtual Representation RequiredInputRepresentation(int index) const {
3474    return Representation::Tagged();
3475  }
3476
3477  virtual HType CalculateInferredType() {
3478    STATIC_ASSERT(String::kMaxLength <= Smi::kMaxValue);
3479    return HType::Smi();
3480  }
3481
3482  DECLARE_CONCRETE_INSTRUCTION(StringLength, "string_length")
3483
3484 protected:
3485  virtual bool DataEquals(HValue* other) { return true; }
3486
3487  virtual Range* InferRange() {
3488    return new Range(0, String::kMaxLength);
3489  }
3490};
3491
3492
3493template <int V>
3494class HMaterializedLiteral: public HTemplateInstruction<V> {
3495 public:
3496  HMaterializedLiteral<V>(int index, int depth)
3497      : literal_index_(index), depth_(depth) {
3498    this->set_representation(Representation::Tagged());
3499  }
3500
3501  int literal_index() const { return literal_index_; }
3502  int depth() const { return depth_; }
3503
3504 private:
3505  int literal_index_;
3506  int depth_;
3507};
3508
3509
3510class HArrayLiteral: public HMaterializedLiteral<0> {
3511 public:
3512  HArrayLiteral(Handle<FixedArray> constant_elements,
3513                int length,
3514                int literal_index,
3515                int depth)
3516      : HMaterializedLiteral<0>(literal_index, depth),
3517        length_(length),
3518        constant_elements_(constant_elements) {}
3519
3520  Handle<FixedArray> constant_elements() const { return constant_elements_; }
3521  int length() const { return length_; }
3522
3523  bool IsCopyOnWrite() const;
3524
3525  virtual Representation RequiredInputRepresentation(int index) const {
3526    return Representation::None();
3527  }
3528
3529  DECLARE_CONCRETE_INSTRUCTION(ArrayLiteral, "array_literal")
3530
3531 private:
3532  int length_;
3533  Handle<FixedArray> constant_elements_;
3534};
3535
3536
3537class HObjectLiteral: public HMaterializedLiteral<1> {
3538 public:
3539  HObjectLiteral(HValue* context,
3540                 Handle<FixedArray> constant_properties,
3541                 bool fast_elements,
3542                 int literal_index,
3543                 int depth,
3544                 bool has_function)
3545      : HMaterializedLiteral<1>(literal_index, depth),
3546        constant_properties_(constant_properties),
3547        fast_elements_(fast_elements),
3548        has_function_(has_function) {
3549    SetOperandAt(0, context);
3550  }
3551
3552  HValue* context() { return OperandAt(0); }
3553  Handle<FixedArray> constant_properties() const {
3554    return constant_properties_;
3555  }
3556  bool fast_elements() const { return fast_elements_; }
3557  bool has_function() const { return has_function_; }
3558
3559  virtual Representation RequiredInputRepresentation(int index) const {
3560    return Representation::Tagged();
3561  }
3562
3563  DECLARE_CONCRETE_INSTRUCTION(ObjectLiteral, "object_literal")
3564
3565 private:
3566  Handle<FixedArray> constant_properties_;
3567  bool fast_elements_;
3568  bool has_function_;
3569};
3570
3571
3572class HRegExpLiteral: public HMaterializedLiteral<0> {
3573 public:
3574  HRegExpLiteral(Handle<String> pattern,
3575                 Handle<String> flags,
3576                 int literal_index)
3577      : HMaterializedLiteral<0>(literal_index, 0),
3578        pattern_(pattern),
3579        flags_(flags) { }
3580
3581  Handle<String> pattern() { return pattern_; }
3582  Handle<String> flags() { return flags_; }
3583
3584  virtual Representation RequiredInputRepresentation(int index) const {
3585    return Representation::None();
3586  }
3587
3588  DECLARE_CONCRETE_INSTRUCTION(RegExpLiteral, "regexp_literal")
3589
3590 private:
3591  Handle<String> pattern_;
3592  Handle<String> flags_;
3593};
3594
3595
3596class HFunctionLiteral: public HTemplateInstruction<0> {
3597 public:
3598  HFunctionLiteral(Handle<SharedFunctionInfo> shared, bool pretenure)
3599      : shared_info_(shared), pretenure_(pretenure) {
3600    set_representation(Representation::Tagged());
3601  }
3602
3603  virtual Representation RequiredInputRepresentation(int index) const {
3604    return Representation::None();
3605  }
3606
3607  DECLARE_CONCRETE_INSTRUCTION(FunctionLiteral, "function_literal")
3608
3609  Handle<SharedFunctionInfo> shared_info() const { return shared_info_; }
3610  bool pretenure() const { return pretenure_; }
3611
3612 private:
3613  Handle<SharedFunctionInfo> shared_info_;
3614  bool pretenure_;
3615};
3616
3617
3618class HTypeof: public HUnaryOperation {
3619 public:
3620  explicit HTypeof(HValue* value) : HUnaryOperation(value) {
3621    set_representation(Representation::Tagged());
3622  }
3623
3624  virtual Representation RequiredInputRepresentation(int index) const {
3625    return Representation::Tagged();
3626  }
3627
3628  DECLARE_CONCRETE_INSTRUCTION(Typeof, "typeof")
3629};
3630
3631
3632class HToFastProperties: public HUnaryOperation {
3633 public:
3634  explicit HToFastProperties(HValue* value) : HUnaryOperation(value) {
3635    // This instruction is not marked as having side effects, but
3636    // changes the map of the input operand. Use it only when creating
3637    // object literals.
3638    ASSERT(value->IsObjectLiteral());
3639    set_representation(Representation::Tagged());
3640  }
3641
3642  virtual Representation RequiredInputRepresentation(int index) const {
3643    return Representation::Tagged();
3644  }
3645
3646  DECLARE_CONCRETE_INSTRUCTION(ToFastProperties, "to_fast_properties")
3647};
3648
3649
3650class HValueOf: public HUnaryOperation {
3651 public:
3652  explicit HValueOf(HValue* value) : HUnaryOperation(value) {
3653    set_representation(Representation::Tagged());
3654  }
3655
3656  virtual Representation RequiredInputRepresentation(int index) const {
3657    return Representation::Tagged();
3658  }
3659
3660  DECLARE_CONCRETE_INSTRUCTION(ValueOf, "value_of")
3661};
3662
3663
3664class HDeleteProperty: public HBinaryOperation {
3665 public:
3666  HDeleteProperty(HValue* obj, HValue* key)
3667      : HBinaryOperation(obj, key) {
3668    set_representation(Representation::Tagged());
3669    SetAllSideEffects();
3670  }
3671
3672  virtual Representation RequiredInputRepresentation(int index) const {
3673    return Representation::Tagged();
3674  }
3675
3676  DECLARE_CONCRETE_INSTRUCTION(DeleteProperty, "delete_property")
3677
3678  HValue* object() { return left(); }
3679  HValue* key() { return right(); }
3680};
3681
3682#undef DECLARE_INSTRUCTION
3683#undef DECLARE_CONCRETE_INSTRUCTION
3684
3685} }  // namespace v8::internal
3686
3687#endif  // V8_HYDROGEN_INSTRUCTIONS_H_
3688