Version 3.20.15

src/hydrogen-instructions.h

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 54 matching lines @@
 #define HYDROGEN_CONCRETE_INSTRUCTION_LIST(V)  \
   V(AbnormalExit)                              \
   V(AccessArgumentsAt)                         \
   V(Add)                                       \
   V(Allocate)                                  \
   V(ApplyArguments)                            \
   V(ArgumentsElements)                         \
   V(ArgumentsLength)                           \
   V(ArgumentsObject)                           \
   V(Bitwise)                                   \
+  V(BitNot)                                    \
   V(BlockEntry)                                \
   V(BoundsCheck)                               \
   V(BoundsCheckBaseIndexInformation)           \
   V(Branch)                                    \
   V(CallConstantFunction)                      \
   V(CallFunction)                              \
   V(CallGlobal)                                \
   V(CallKeyed)                                 \
   V(CallKnownGlobal)                           \
   V(CallNamed)                                 \
   V(CallNew)                                   \
   V(CallNewArray)                              \
   V(CallRuntime)                               \
   V(CallStub)                                  \
   V(Change)                                    \
   V(CheckFunction)                             \
   V(CheckHeapObject)                           \
   V(CheckInstanceType)                         \
   V(CheckMaps)                                 \
   V(CheckMapValue)                             \
+  V(CheckPrototypeMaps)                        \
   V(CheckSmi)                                  \
   V(ClampToUint8)                              \
   V(ClassOfTestAndBranch)                      \
   V(CompareNumericAndBranch)                   \
   V(CompareGeneric)                            \
   V(CompareObjectEqAndBranch)                  \
   V(CompareMap)                                \
   V(Constant)                                  \
   V(Context)                                   \
   V(DateField)                                 \
   V(DebugBreak)                                \
   V(DeclareGlobals)                            \
   V(Deoptimize)                                \
   V(Div)                                       \
   V(DummyUse)                                  \
   V(ElementsKind)                              \
   V(EnterInlined)                              \
   V(EnvironmentMarker)                         \
   V(ForceRepresentation)                       \
   V(ForInCacheArray)                           \
   V(ForInPrepareMap)                           \
   V(FunctionLiteral)                           \
   V(GetCachedArrayIndex)                       \
   V(GlobalObject)                              \
   V(GlobalReceiver)                            \
   V(Goto)                                      \
   V(HasCachedArrayIndexAndBranch)              \
   V(HasInstanceTypeAndBranch)                  \
+  V(InductionVariableAnnotation)               \
   V(InnerAllocatedObject)                      \
   V(InstanceOf)                                \
   V(InstanceOfKnownGlobal)                     \
   V(InstanceSize)                              \
   V(InvokeFunction)                            \
   V(IsConstructCallAndBranch)                  \
   V(IsObjectAndBranch)                         \
   V(IsNumberAndBranch)                         \
   V(IsStringAndBranch)                         \
   V(IsSmiAndBranch)                            \
   V(IsUndetectableAndBranch)                   \
   V(LeaveInlined)                              \
   V(LoadContextSlot)                           \
   V(LoadExternalArrayPointer)                  \
   V(LoadFieldByIndex)                          \
   V(LoadFunctionPrototype)                     \
   V(LoadGlobalCell)                            \
   V(LoadGlobalGeneric)                         \
   V(LoadKeyed)                                 \
   V(LoadKeyedGeneric)                          \
   V(LoadNamedField)                            \
   V(LoadNamedFieldPolymorphic)                 \
   V(LoadNamedGeneric)                          \
   V(MapEnumLength)                             \
   V(MathFloorOfDiv)                            \
   V(MathMinMax)                                \
   V(Mod)                                       \
   V(Mul)                                       \
+  V(NumericConstraint)                         \
   V(OsrEntry)                                  \
   V(OuterContext)                              \
   V(Parameter)                                 \
   V(Power)                                     \
   V(PushArgument)                              \
   V(Random)                                    \
   V(RegExpLiteral)                             \
   V(Return)                                    \
   V(Ror)                                       \
   V(Sar)                                       \
@@ skipping 370 matching lines @@
   GVN_UNTRACKED_FLAG_LIST(DECLARE_FLAG)
 #undef DECLARE_FLAG
   kAfterLastFlag,
   kLastFlag = kAfterLastFlag - 1,
 #define COUNT_FLAG(type) + 1
   kNumberOfTrackedSideEffects = 0 GVN_TRACKED_FLAG_LIST(COUNT_FLAG)
 #undef COUNT_FLAG
 };
 
 
+class NumericRelation {
+ public:
+  enum Kind { NONE, EQ, GT, GE, LT, LE, NE };
+  static const char* MnemonicFromKind(Kind kind) {
+    switch (kind) {
+      case NONE: return "NONE";
+      case EQ: return "EQ";
+      case GT: return "GT";
+      case GE: return "GE";
+      case LT: return "LT";
+      case LE: return "LE";
+      case NE: return "NE";
+    }
+    UNREACHABLE();
+    return NULL;
+  }
+  const char* Mnemonic() const { return MnemonicFromKind(kind_); }
+
+  static NumericRelation None() { return NumericRelation(NONE); }
+  static NumericRelation Eq() { return NumericRelation(EQ); }
+  static NumericRelation Gt() { return NumericRelation(GT); }
+  static NumericRelation Ge() { return NumericRelation(GE); }
+  static NumericRelation Lt() { return NumericRelation(LT); }
+  static NumericRelation Le() { return NumericRelation(LE); }
+  static NumericRelation Ne() { return NumericRelation(NE); }
+
+  bool IsNone() { return kind_ == NONE; }
+
+  static NumericRelation FromToken(Token::Value token) {
+    switch (token) {
+      case Token::EQ: return Eq();
+      case Token::EQ_STRICT: return Eq();
+      case Token::LT: return Lt();
+      case Token::GT: return Gt();
+      case Token::LTE: return Le();
+      case Token::GTE: return Ge();
+      case Token::NE: return Ne();
+      case Token::NE_STRICT: return Ne();
+      default: return None();
+    }
+  }
+
+  // The semantics of "Reversed" is that if "x rel y" is true then also
+  // "y rel.Reversed() x" is true, and that rel.Reversed().Reversed() == rel.
+  NumericRelation Reversed() {
+    switch (kind_) {
+      case NONE: return None();
+      case EQ: return Eq();
+      case GT: return Lt();
+      case GE: return Le();
+      case LT: return Gt();
+      case LE: return Ge();
+      case NE: return Ne();
+    }
+    UNREACHABLE();
+    return None();
+  }
+
+  // The semantics of "Negated" is that if "x rel y" is true then also
+  // "!(x rel.Negated() y)" is true.
+  NumericRelation Negated() {
+    switch (kind_) {
+      case NONE: return None();
+      case EQ: return Ne();
+      case GT: return Le();
+      case GE: return Lt();
+      case LT: return Ge();
+      case LE: return Gt();
+      case NE: return Eq();
+    }
+    UNREACHABLE();
+    return None();
+  }
+
+  // The semantics of "Implies" is that if "x rel y" is true
+  // then also "x other_relation y" is true.
+  bool Implies(NumericRelation other_relation) {
+    switch (kind_) {
+      case NONE: return false;
+      case EQ: return (other_relation.kind_ == EQ)
+          || (other_relation.kind_ == GE)
+          || (other_relation.kind_ == LE);
+      case GT: return (other_relation.kind_ == GT)
+          || (other_relation.kind_ == GE)
+          || (other_relation.kind_ == NE);
+      case LT: return (other_relation.kind_ == LT)
+          || (other_relation.kind_ == LE)
+          || (other_relation.kind_ == NE);
+      case GE: return (other_relation.kind_ == GE);
+      case LE: return (other_relation.kind_ == LE);
+      case NE: return (other_relation.kind_ == NE);
+    }
+    UNREACHABLE();
+    return false;
+  }
+
+  // The semantics of "IsExtendable" is that if
+  // "rel.IsExtendable(direction)" is true then
+  // "x rel y" implies "(x + direction) rel y" .
+  bool IsExtendable(int direction) {
+    switch (kind_) {
+      case NONE: return false;
+      case EQ: return false;
+      case GT: return (direction >= 0);
+      case GE: return (direction >= 0);
+      case LT: return (direction <= 0);
+      case LE: return (direction <= 0);
+      case NE: return false;
+    }
+    UNREACHABLE();
+    return false;
+  }
+
+  // CompoundImplies returns true when
+  // "((x + my_offset) >> my_scale) rel y" implies
+  // "((x + other_offset) >> other_scale) other_relation y".
+  bool CompoundImplies(NumericRelation other_relation,
+                       int my_offset,
+                       int my_scale,
+                       int other_offset = 0,
+                       int other_scale = 0) {
+    return Implies(other_relation) && ComponentsImply(
+        my_offset, my_scale, other_offset, other_scale);
+  }
+
+ private:
+  // ComponentsImply returns true when
+  // "((x + my_offset) >> my_scale) rel y" implies
+  // "((x + other_offset) >> other_scale) rel y".
+  bool ComponentsImply(int my_offset,
+                       int my_scale,
+                       int other_offset,
+                       int other_scale) {
+    switch (kind_) {
+      case NONE: break;  // Fall through to UNREACHABLE().
+      case EQ:
+      case NE: return my_offset == other_offset && my_scale == other_scale;
+      case GT:
+      case GE: return my_offset <= other_offset && my_scale >= other_scale;
+      case LT:
+      case LE: return my_offset >= other_offset && my_scale <= other_scale;
+    }
+    UNREACHABLE();
+    return false;
+  }
+
+  explicit NumericRelation(Kind kind) : kind_(kind) {}
+
+  Kind kind_;
+};
+
+
 class DecompositionResult BASE_EMBEDDED {
  public:
   DecompositionResult() : base_(NULL), offset_(0), scale_(0) {}
 
   HValue* base() { return base_; }
   int offset() { return offset_; }
   int scale() { return scale_; }
 
   bool Apply(HValue* other_base, int other_offset, int other_scale = 0) {
     if (base_ == NULL) {
@@ skipping 25 matching lines @@
     *a = *b;
     *b = c;
   }
 
   HValue* base_;
   int offset_;
   int scale_;
 };
 
 
+class RangeEvaluationContext BASE_EMBEDDED {
+ public:
+  RangeEvaluationContext(HValue* value, HValue* upper);
+
+  HValue* lower_bound() { return lower_bound_; }
+  HValue* lower_bound_guarantee() { return lower_bound_guarantee_; }
+  HValue* candidate() { return candidate_; }
+  HValue* upper_bound() { return upper_bound_; }
+  HValue* upper_bound_guarantee() { return upper_bound_guarantee_; }
+  int offset() { return offset_; }
+  int scale() { return scale_; }
+
+  bool is_range_satisfied() {
+    return lower_bound_guarantee() != NULL && upper_bound_guarantee() != NULL;
+  }
+
+  void set_lower_bound_guarantee(HValue* guarantee) {
+    lower_bound_guarantee_ = ConvertGuarantee(guarantee);
+  }
+  void set_upper_bound_guarantee(HValue* guarantee) {
+    upper_bound_guarantee_ = ConvertGuarantee(guarantee);
+  }
+
+  void swap_candidate(DecompositionResult* other_candicate) {
+    other_candicate->SwapValues(&candidate_, &offset_, &scale_);
+  }
+
+ private:
+  HValue* ConvertGuarantee(HValue* guarantee);
+
+  HValue* lower_bound_;
+  HValue* lower_bound_guarantee_;
+  HValue* candidate_;
+  HValue* upper_bound_;
+  HValue* upper_bound_guarantee_;
+  int offset_;
+  int scale_;
+};
+
+
 typedef EnumSet<GVNFlag> GVNFlagSet;
 
 
 class HValue: public ZoneObject {
  public:
   static const int kNoNumber = -1;
 
   enum Flag {
     kFlexibleRepresentation,
     kCannotBeTagged,
@@ skipping 17 matching lines @@
     kAllUsesTruncatingToSmi,
     // Set after an instruction is killed.
     kIsDead,
     // Instructions that are allowed to produce full range unsigned integer
     // values are marked with kUint32 flag. If arithmetic shift or a load from
     // EXTERNAL_UNSIGNED_INT_ELEMENTS array is not marked with this flag
     // it will deoptimize if result does not fit into signed integer range.
     // HGraph::ComputeSafeUint32Operations is responsible for setting this
     // flag.
     kUint32,
+    // If a phi is involved in the evaluation of a numeric constraint the
+    // recursion can cause an endless cycle: we use this flag to exit the loop.
+    kNumericConstraintEvaluationInProgress,
+    // This flag is set to true after the SetupInformativeDefinitions() pass
+    // has processed this instruction.
+    kIDefsProcessingDone,
     kHasNoObservableSideEffects,
     // Indicates the instruction is live during dead code elimination.
     kIsLive,
 
     // HEnvironmentMarkers are deleted before dead code
     // elimination takes place, so they can repurpose the kIsLive flag:
     kEndsLiveRange = kIsLive,
 
     // TODO(everyone): Don't forget to update this!
     kLastFlag = kIsLive
@@ skipping 117 matching lines @@
   // One of the iDef operands is special because it is the value that is
   // "transferred" to the output, we call it the "redefined operand".
   // If an HValue is an iDef it must override RedefinedOperandIndex() so that
   // it does not return kNoRedefinedOperand;
   static const int kNoRedefinedOperand = -1;
   virtual int RedefinedOperandIndex() { return kNoRedefinedOperand; }
   bool IsInformativeDefinition() {
     return RedefinedOperandIndex() != kNoRedefinedOperand;
   }
   HValue* RedefinedOperand() {
-    int index = RedefinedOperandIndex();
-    return index == kNoRedefinedOperand ? NULL : OperandAt(index);
+    return IsInformativeDefinition() ? OperandAt(RedefinedOperandIndex())
+                                     : NULL;
   }
 
   // A purely informative definition is an idef that will not emit code and
   // should therefore be removed from the graph in the RestoreActualValues
   // phase (so that live ranges will be shorter).
   virtual bool IsPurelyInformativeDefinition() { return false; }
 
   // This method must always return the original HValue SSA definition
   // (regardless of any iDef of this value).
   HValue* ActualValue() {
-    int index = RedefinedOperandIndex();
-    return index == kNoRedefinedOperand ? this : OperandAt(index);
+    return IsInformativeDefinition() ? RedefinedOperand()->ActualValue()
+                                     : this;
+  }
+
+  virtual void AddInformativeDefinitions() {}
+
+  void UpdateRedefinedUsesWhileSettingUpInformativeDefinitions() {
+    UpdateRedefinedUsesInner<TestDominanceUsingProcessedFlag>();
+  }
+  void UpdateRedefinedUses() {
+    UpdateRedefinedUsesInner<Dominates>();
   }
 
   bool IsInteger32Constant();
   int32_t GetInteger32Constant();
   bool EqualsInteger32Constant(int32_t value);
 
   bool IsDefinedAfter(HBasicBlock* other) const;
 
   // Operands.
   virtual int OperandCount() = 0;
@@ skipping 130 matching lines @@
 
   // Check if this instruction has some reason that prevents elimination.
   bool CannotBeEliminated() const {
     return HasObservableSideEffects() || !IsDeletable();
   }
 
 #ifdef DEBUG
   virtual void Verify() = 0;
 #endif
 
+  bool IsRelationTrue(NumericRelation relation,
+                      HValue* other,
+                      int offset = 0,
+                      int scale = 0);
+
+  bool TryGuaranteeRange(HValue* upper_bound);
   virtual bool TryDecompose(DecompositionResult* decomposition) {
     if (RedefinedOperand() != NULL) {
       return RedefinedOperand()->TryDecompose(decomposition);
     } else {
       return false;
     }
   }
 
   // Returns true conservatively if the program might be able to observe a
   // ToString() operation on this value.
   bool ToStringCanBeObserved() const {
     return type().ToStringOrToNumberCanBeObserved(representation());
   }
 
   // Returns true conservatively if the program might be able to observe a
   // ToNumber() operation on this value.
   bool ToNumberCanBeObserved() const {
     return type().ToStringOrToNumberCanBeObserved(representation());
   }
 
  protected:
+  void TryGuaranteeRangeRecursive(RangeEvaluationContext* context);
+
+  enum RangeGuaranteeDirection {
+    DIRECTION_NONE = 0,
+    DIRECTION_UPPER = 1,
+    DIRECTION_LOWER = 2,
+    DIRECTION_BOTH = DIRECTION_UPPER | DIRECTION_LOWER
+  };
+  virtual void SetResponsibilityForRange(RangeGuaranteeDirection direction) {}
+  virtual void TryGuaranteeRangeChanging(RangeEvaluationContext* context) {}
+
   // This function must be overridden for instructions with flag kUseGVN, to
   // compare the non-Operand parts of the instruction.
   virtual bool DataEquals(HValue* other) {
     UNREACHABLE();
     return false;
   }
 
   virtual Representation RepresentationFromInputs() {
     return representation();
   }
@@ skipping 13 matching lines @@
   void clear_block() {
     ASSERT(block_ != NULL);
     block_ = NULL;
   }
 
   void set_representation(Representation r) {
     ASSERT(representation_.IsNone() && !r.IsNone());
     representation_ = r;
   }
 
+  // Signature of a function testing if a HValue properly dominates another.
+  typedef bool (*DominanceTest)(HValue*, HValue*);
+
+  // Simple implementation of DominanceTest implemented walking the chain
+  // of Hinstructions (used in UpdateRedefinedUsesInner).
+  static bool Dominates(HValue* dominator, HValue* dominated);
+
+  // A fast implementation of DominanceTest that works only for the
+  // "current" instruction in the SetupInformativeDefinitions() phase.
+  // During that phase we use a flag to mark processed instructions, and by
+  // checking the flag we can quickly test if an instruction comes before or
+  // after the "current" one.
+  static bool TestDominanceUsingProcessedFlag(HValue* dominator,
+                                              HValue* dominated);
+
+  // If we are redefining an operand, update all its dominated uses (the
+  // function that checks if a use is dominated is the template argument).
+  template<DominanceTest TestDominance>
+  void UpdateRedefinedUsesInner() {
+    HValue* input = RedefinedOperand();
+    if (input != NULL) {
+      for (HUseIterator uses = input->uses(); !uses.Done(); uses.Advance()) {
+        HValue* use = uses.value();
+        if (TestDominance(this, use)) {
+          use->SetOperandAt(uses.index(), this);
+        }
+      }
+    }
+  }
+
+  // Informative definitions can override this method to state any numeric
+  // relation they provide on the redefined value.
+  // Returns true if it is guaranteed that:
+  // ((this + offset) >> scale) relation other
+  virtual bool IsRelationTrueInternal(NumericRelation relation,
+                                      HValue* other,
+                                      int offset = 0,
+                                      int scale = 0) {
+    return false;
+  }
+
   static GVNFlagSet AllDependsOnFlagSet() {
     GVNFlagSet result;
     // Create changes mask.
 #define ADD_FLAG(type) result.Add(kDependsOn##type);
   GVN_TRACKED_FLAG_LIST(ADD_FLAG)
   GVN_UNTRACKED_FLAG_LIST(ADD_FLAG)
 #undef ADD_FLAG
     return result;
   }
 
@@ skipping 250 matching lines @@
   virtual Representation RequiredInputRepresentation(int index) {
     return Representation::None();
   }
 
   virtual void PrintDataTo(StringStream* stream);
 
   DECLARE_CONCRETE_INSTRUCTION(DummyUse);
 };
 
 
+class HNumericConstraint : public HTemplateInstruction<2> {
+ public:
+  static HNumericConstraint* AddToGraph(HValue* constrained_value,
+                                        NumericRelation relation,
+                                        HValue* related_value,
+                                        HInstruction* insertion_point = NULL);
+
+  HValue* constrained_value() { return OperandAt(0); }
+  HValue* related_value() { return OperandAt(1); }
+  NumericRelation relation() { return relation_; }
+
+  virtual int RedefinedOperandIndex() { return 0; }
+  virtual bool IsPurelyInformativeDefinition() { return true; }
+
+  virtual Representation RequiredInputRepresentation(int index) {
+    return representation();
+  }
+
+  virtual void PrintDataTo(StringStream* stream);
+
+  virtual bool IsRelationTrueInternal(NumericRelation other_relation,
+                                      HValue* other_related_value,
+                                      int offset = 0,
+                                      int scale = 0) {
+    if (related_value() == other_related_value) {
+      return relation().CompoundImplies(other_relation, offset, scale);
+    } else {
+      return false;
+    }
+  }
+
+  DECLARE_CONCRETE_INSTRUCTION(NumericConstraint)
+
+ private:
+  HNumericConstraint(HValue* constrained_value,
+                     NumericRelation relation,
+                     HValue* related_value)
+      : relation_(relation) {
+    SetOperandAt(0, constrained_value);
+    SetOperandAt(1, related_value);
+  }
+
+  NumericRelation relation_;
+};
+
+
 class HDeoptimize: public HTemplateInstruction<0> {
  public:
   DECLARE_INSTRUCTION_FACTORY_P1(HDeoptimize, Deoptimizer::BailoutType);
 
   virtual Representation RequiredInputRepresentation(int index) {
     return Representation::None();
   }
 
   Deoptimizer::BailoutType type() { return type_; }
 
@@ skipping 1126 matching lines @@
   DECLARE_CONCRETE_INSTRUCTION(ElementsKind)
 
  protected:
   virtual bool DataEquals(HValue* other) { return true; }
 
  private:
   virtual bool IsDeletable() const { return true; }
 };
 
 
+class HBitNot: public HUnaryOperation {
+ public:
+  DECLARE_INSTRUCTION_FACTORY_P1(HBitNot, HValue*);
+
+  virtual Representation RequiredInputRepresentation(int index) {
+    return Representation::Integer32();
+  }
+  virtual Representation observed_input_representation(int index) {
+    return Representation::Integer32();
+  }
+
+  virtual HValue* Canonicalize();
+
+  DECLARE_CONCRETE_INSTRUCTION(BitNot)
+
+ protected:
+  virtual bool DataEquals(HValue* other) { return true; }
+
+ private:
+  explicit HBitNot(HValue* value)
+      : HUnaryOperation(value, HType::TaggedNumber()) {
+    set_representation(Representation::Integer32());
+    SetFlag(kUseGVN);
+    SetFlag(kTruncatingToInt32);
+    SetFlag(kAllowUndefinedAsNaN);
+  }
+
+  virtual bool IsDeletable() const { return true; }
+};
+
+
 class HUnaryMathOperation: public HTemplateInstruction<2> {
  public:
   static HInstruction* New(Zone* zone,
                            HValue* context,
                            HValue* value,
                            BuiltinFunctionId op);
 
   HValue* context() { return OperandAt(0); }
   HValue* value() { return OperandAt(1); }
 
@@ skipping 121 matching lines @@
  public:
   static HCheckMaps* New(Zone* zone, HValue* context, HValue* value,
                          Handle<Map> map, CompilationInfo* info,
                          HValue *typecheck = NULL);
   static HCheckMaps* New(Zone* zone, HValue* context,
                          HValue* value, SmallMapList* maps,
                          HValue *typecheck = NULL) {
     HCheckMaps* check_map = new(zone) HCheckMaps(value, zone, typecheck);
     for (int i = 0; i < maps->length(); i++) {
       check_map->map_set_.Add(maps->at(i), zone);
-      check_map->has_migration_target_ |= maps->at(i)->is_migration_target();
     }
     check_map->map_set_.Sort();
     return check_map;
   }
 
   bool CanOmitMapChecks() { return omit_; }
 
   virtual bool HasEscapingOperandAt(int index) { return false; }
   virtual Representation RequiredInputRepresentation(int index) {
     return Representation::Tagged();
   }
   virtual void HandleSideEffectDominator(GVNFlag side_effect,
                                          HValue* dominator);
   virtual void PrintDataTo(StringStream* stream);
 
   HValue* value() { return OperandAt(0); }
   SmallMapList* map_set() { return &map_set_; }
 
-  bool has_migration_target() {
-    return has_migration_target_;
-  }
-
   virtual void FinalizeUniqueValueId();
 
   DECLARE_CONCRETE_INSTRUCTION(CheckMaps)
 
  protected:
   virtual bool DataEquals(HValue* other) {
     ASSERT_EQ(map_set_.length(), map_unique_ids_.length());
     HCheckMaps* b = HCheckMaps::cast(other);
     // Relies on the fact that map_set has been sorted before.
     if (map_unique_ids_.length() != b->map_unique_ids_.length()) {
       return false;
     }
     for (int i = 0; i < map_unique_ids_.length(); i++) {
       if (map_unique_ids_.at(i) != b->map_unique_ids_.at(i)) {
         return false;
       }
     }
     return true;
   }
 
  private:
   // Clients should use one of the static New* methods above.
   HCheckMaps(HValue* value, Zone *zone, HValue* typecheck)
       : HTemplateInstruction<2>(value->type()),
-        omit_(false), has_migration_target_(false), map_unique_ids_(0, zone) {
+        omit_(false), map_unique_ids_(0, zone) {
     SetOperandAt(0, value);
     // Use the object value for the dependency if NULL is passed.
     // TODO(titzer): do GVN flags already express this dependency?
     SetOperandAt(1, typecheck != NULL ? typecheck : value);
     set_representation(Representation::Tagged());
     SetFlag(kUseGVN);
     SetFlag(kTrackSideEffectDominators);
     SetGVNFlag(kDependsOnMaps);
     SetGVNFlag(kDependsOnElementsKind);
   }
 
   void omit(CompilationInfo* info) {
     omit_ = true;
     for (int i = 0; i < map_set_.length(); i++) {
       Handle<Map> map = map_set_.at(i);
       map->AddDependentCompilationInfo(DependentCode::kPrototypeCheckGroup,
                                        info);
     }
   }
 
   bool omit_;
-  bool has_migration_target_;
   SmallMapList map_set_;
   ZoneList<UniqueValueId> map_unique_ids_;
 };
 
 
 class HCheckFunction: public HUnaryOperation {
  public:
   DECLARE_INSTRUCTION_FACTORY_P2(HCheckFunction, HValue*, Handle<JSFunction>);
 
   virtual Representation RequiredInputRepresentation(int index) {
@@ skipping 164 matching lines @@
 
  private:
   explicit HCheckHeapObject(HValue* value)
       : HUnaryOperation(value, HType::NonPrimitive()) {
     set_representation(Representation::Tagged());
     SetFlag(kUseGVN);
   }
 };
 
 
+class HCheckPrototypeMaps: public HTemplateInstruction<0> {
+ public:
+  static HCheckPrototypeMaps* New(Zone* zone,
+                                  HValue* context,
+                                  Handle<JSObject> prototype,
+                                  Handle<JSObject> holder,
+                                  CompilationInfo* info) {
+    return new(zone) HCheckPrototypeMaps(prototype, holder, zone, info);
+  }
+
+  ZoneList<Handle<JSObject> >* prototypes() { return &prototypes_; }
+
+  ZoneList<Handle<Map> >* maps() { return &maps_; }
+
+  DECLARE_CONCRETE_INSTRUCTION(CheckPrototypeMaps)
+
+  virtual Representation RequiredInputRepresentation(int index) {
+    return Representation::None();
+  }
+
+  virtual void PrintDataTo(StringStream* stream);
+
+  virtual intptr_t Hashcode() {
+    return first_prototype_unique_id_.Hashcode() * 17 +
+           last_prototype_unique_id_.Hashcode();
+  }
+
+  virtual void FinalizeUniqueValueId() {
+    first_prototype_unique_id_ = UniqueValueId(prototypes_.first());
+    last_prototype_unique_id_ = UniqueValueId(prototypes_.last());
+  }
+
+  bool CanOmitPrototypeChecks() { return can_omit_prototype_maps_; }
+
+ protected:
+  virtual bool DataEquals(HValue* other) {
+    HCheckPrototypeMaps* b = HCheckPrototypeMaps::cast(other);
+    return first_prototype_unique_id_ == b->first_prototype_unique_id_ &&
+           last_prototype_unique_id_ == b->last_prototype_unique_id_;
+  }
+
+ private:
+  HCheckPrototypeMaps(Handle<JSObject> prototype,
+                      Handle<JSObject> holder,
+                      Zone* zone,
+                      CompilationInfo* info)
+      : prototypes_(2, zone),
+        maps_(2, zone),
+        first_prototype_unique_id_(),
+        last_prototype_unique_id_(),
+        can_omit_prototype_maps_(true) {
+    SetFlag(kUseGVN);
+    SetGVNFlag(kDependsOnMaps);
+    // Keep a list of all objects on the prototype chain up to the holder
+    // and the expected maps.
+    while (true) {
+      prototypes_.Add(prototype, zone);
+      Handle<Map> map(prototype->map());
+      maps_.Add(map, zone);
+      can_omit_prototype_maps_ &= map->CanOmitPrototypeChecks();
+      if (prototype.is_identical_to(holder)) break;
+      prototype = Handle<JSObject>(JSObject::cast(prototype->GetPrototype()));
+    }
+    if (can_omit_prototype_maps_) {
+      // Mark in-flight compilation as dependent on those maps.
+      for (int i = 0; i < maps()->length(); i++) {
+        Handle<Map> map = maps()->at(i);
+        map->AddDependentCompilationInfo(DependentCode::kPrototypeCheckGroup,
+                                         info);
+      }
+    }
+  }
+
+  ZoneList<Handle<JSObject> > prototypes_;
+  ZoneList<Handle<Map> > maps_;
+  UniqueValueId first_prototype_unique_id_;
+  UniqueValueId last_prototype_unique_id_;
+  bool can_omit_prototype_maps_;
+};
+
+
 class InductionVariableData;
 
 
 struct InductionVariableLimitUpdate {
   InductionVariableData* updated_variable;
   HValue* limit;
   bool limit_is_upper;
   bool limit_is_included;
 
   InductionVariableLimitUpdate()
@@ skipping 253 matching lines @@
   }
   bool IsLimitedInductionVariable() {
     return IsInductionVariable() &&
         induction_variable_data_->limit() != NULL;
   }
   void DetectInductionVariable() {
     ASSERT(induction_variable_data_ == NULL);
     induction_variable_data_ = InductionVariableData::ExaminePhi(this);
   }
 
+  virtual void AddInformativeDefinitions();
+
   virtual void PrintTo(StringStream* stream);
 
 #ifdef DEBUG
   virtual void Verify();
 #endif
 
   void InitRealUses(int id);
   void AddNonPhiUsesFrom(HPhi* other);
   void AddIndirectUsesTo(int* use_count);
 
@@ skipping 30 matching lines @@
   virtual Opcode opcode() const { return HValue::kPhi; }
 
   void SimplifyConstantInputs();
 
  protected:
   virtual void DeleteFromGraph();
   virtual void InternalSetOperandAt(int index, HValue* value) {
     inputs_[index] = value;
   }
 
+  virtual bool IsRelationTrueInternal(NumericRelation relation,
+                                      HValue* other,
+                                      int offset = 0,
+                                      int scale = 0);
+
  private:
   ZoneList<HValue*> inputs_;
   int merged_index_;
 
   int non_phi_uses_[Representation::kNumRepresentations];
   int indirect_uses_[Representation::kNumRepresentations];
   int phi_id_;
   InductionVariableData* induction_variable_data_;
 
   // TODO(titzer): we can't eliminate the receiver for generating backtraces
   virtual bool IsDeletable() const { return !IsReceiver(); }
 };
 
 
+class HInductionVariableAnnotation : public HUnaryOperation {
+ public:
+  static HInductionVariableAnnotation* AddToGraph(HPhi* phi,
+                                                  NumericRelation relation,
+                                                  int operand_index);
+
+  NumericRelation relation() { return relation_; }
+  HValue* induction_base() { return phi_->OperandAt(operand_index_); }
+
+  virtual int RedefinedOperandIndex() { return 0; }
+  virtual bool IsPurelyInformativeDefinition() { return true; }
+  virtual Representation RequiredInputRepresentation(int index) {
+    return representation();
+  }
+
+  virtual void PrintDataTo(StringStream* stream);
+
+  virtual bool IsRelationTrueInternal(NumericRelation other_relation,
+                                      HValue* other_related_value,
+                                      int offset = 0,
+                                      int scale = 0) {
+    if (induction_base() == other_related_value) {
+      return relation().CompoundImplies(other_relation, offset, scale);
+    } else {
+      return false;
+    }
+  }
+
+  DECLARE_CONCRETE_INSTRUCTION(InductionVariableAnnotation)
+
+ private:
+  HInductionVariableAnnotation(HPhi* phi,
+                               NumericRelation relation,
+                               int operand_index)
+      : HUnaryOperation(phi),
+    phi_(phi), relation_(relation), operand_index_(operand_index) {
+  }
+
+  // We need to store the phi both here and in the instruction operand because
+  // the operand can change if a new idef of the phi is added between the phi
+  // and this instruction (inserting an idef updates every use).
+  HPhi* phi_;
+  NumericRelation relation_;
+  int operand_index_;
+};
+
+
 class HArgumentsObject: public HTemplateInstruction<0> {
  public:
   static HArgumentsObject* New(Zone* zone,
                                HValue* context,
                                int count) {
     return new(zone) HArgumentsObject(count, zone);
   }
 
   const ZoneList<HValue*>* arguments_values() const { return &values_; }
   int arguments_count() const { return values_.length(); }
@@ skipping 69 matching lines @@
   bool ImmortalImmovable() const {
     if (has_int32_value_) {
       return false;
     }
     if (has_double_value_) {
       if (IsSpecialDouble()) {
         return true;
       }
       return false;
     }
-    if (has_external_reference_value_) {
-      return false;
-    }
 
     ASSERT(!handle_.is_null());
     Heap* heap = isolate()->heap();
     ASSERT(unique_id_ != UniqueValueId(heap->minus_zero_value()));
     ASSERT(unique_id_ != UniqueValueId(heap->nan_value()));
     return unique_id_ == UniqueValueId(heap->undefined_value()) ||
            unique_id_ == UniqueValueId(heap->null_value()) ||
            unique_id_ == UniqueValueId(heap->true_value()) ||
            unique_id_ == UniqueValueId(heap->false_value()) ||
            unique_id_ == UniqueValueId(heap->the_hole_value()) ||
@@ skipping 408 matching lines @@
 class HBoundsCheck: public HTemplateInstruction<2> {
  public:
   DECLARE_INSTRUCTION_FACTORY_P2(HBoundsCheck, HValue*, HValue*);
 
   bool skip_check() const { return skip_check_; }
   void set_skip_check() { skip_check_ = true; }
 
   HValue* base() { return base_; }
   int offset() { return offset_; }
   int scale() { return scale_; }
+  bool index_can_increase() {
+    return (responsibility_direction_ & DIRECTION_LOWER) == 0;
+  }
+  bool index_can_decrease() {
+    return (responsibility_direction_ & DIRECTION_UPPER) == 0;
+  }
 
   void ApplyIndexChange();
   bool DetectCompoundIndex() {
     ASSERT(base() == NULL);
 
     DecompositionResult decomposition;
     if (index()->TryDecompose(&decomposition)) {
       base_ = decomposition.base();
       offset_ = decomposition.offset();
       scale_ = decomposition.scale();
       return true;
     } else {
       base_ = index();
       offset_ = 0;
       scale_ = 0;
       return false;
     }
   }
 
   virtual Representation RequiredInputRepresentation(int arg_index) {
     return representation();
   }
 
+  virtual bool IsRelationTrueInternal(NumericRelation relation,
+                                      HValue* related_value,
+                                      int offset = 0,
+                                      int scale = 0);
+
   virtual void PrintDataTo(StringStream* stream);
   virtual void InferRepresentation(HInferRepresentationPhase* h_infer);
 
   HValue* index() { return OperandAt(0); }
   HValue* length() { return OperandAt(1); }
   bool allow_equality() { return allow_equality_; }
   void set_allow_equality(bool v) { allow_equality_ = v; }
 
   virtual int RedefinedOperandIndex() { return 0; }
   virtual bool IsPurelyInformativeDefinition() { return skip_check(); }
+  virtual void AddInformativeDefinitions();
 
   DECLARE_CONCRETE_INSTRUCTION(BoundsCheck)
 
  protected:
   friend class HBoundsCheckBaseIndexInformation;
 
+  virtual void SetResponsibilityForRange(RangeGuaranteeDirection direction) {
+    responsibility_direction_ = static_cast<RangeGuaranteeDirection>(
+        responsibility_direction_ | direction);
+  }
+
   virtual bool DataEquals(HValue* other) { return true; }
+  virtual void TryGuaranteeRangeChanging(RangeEvaluationContext* context);
   bool skip_check_;
   HValue* base_;
   int offset_;
   int scale_;
+  RangeGuaranteeDirection responsibility_direction_;
   bool allow_equality_;
 
  private:
   // Normally HBoundsCheck should be created using the
   // HGraphBuilder::AddBoundsCheck() helper.
   // However when building stubs, where we know that the arguments are Int32,
   // it makes sense to invoke this constructor directly.
   HBoundsCheck(HValue* index, HValue* length)
     : skip_check_(false),
       base_(NULL), offset_(0), scale_(0),
+      responsibility_direction_(DIRECTION_NONE),
       allow_equality_(false) {
     SetOperandAt(0, index);
     SetOperandAt(1, length);
     SetFlag(kFlexibleRepresentation);
     SetFlag(kUseGVN);
   }
 
   virtual bool IsDeletable() const {
     return skip_check() && !FLAG_debug_code;
   }
@@ skipping 14 matching lines @@
 
   HValue* base_index() { return OperandAt(0); }
   HBoundsCheck* bounds_check() { return HBoundsCheck::cast(OperandAt(1)); }
 
   DECLARE_CONCRETE_INSTRUCTION(BoundsCheckBaseIndexInformation)
 
   virtual Representation RequiredInputRepresentation(int arg_index) {
     return representation();
   }
 
+  virtual bool IsRelationTrueInternal(NumericRelation relation,
+                                      HValue* related_value,
+                                      int offset = 0,
+                                      int scale = 0);
   virtual void PrintDataTo(StringStream* stream);
 
   virtual int RedefinedOperandIndex() { return 0; }
   virtual bool IsPurelyInformativeDefinition() { return true; }
+
+ protected:
+  virtual void SetResponsibilityForRange(RangeGuaranteeDirection direction) {
+    bounds_check()->SetResponsibilityForRange(direction);
+  }
+  virtual void TryGuaranteeRangeChanging(RangeEvaluationContext* context) {
+    bounds_check()->TryGuaranteeRangeChanging(context);
+  }
 };
 
 
 class HBitwiseBinaryOperation: public HBinaryOperation {
  public:
   HBitwiseBinaryOperation(HValue* context, HValue* left, HValue* right,
                           HType type = HType::Tagged())
       : HBinaryOperation(context, left, right, type) {
     SetFlag(kFlexibleRepresentation);
     SetFlag(kTruncatingToInt32);
@@ skipping 152 matching lines @@
   virtual void InferRepresentation(HInferRepresentationPhase* h_infer);
 
   virtual Representation RequiredInputRepresentation(int index) {
     return representation();
   }
   virtual Representation observed_input_representation(int index) {
     return observed_input_representation_[index];
   }
   virtual void PrintDataTo(StringStream* stream);
 
+  virtual void AddInformativeDefinitions();
+
   DECLARE_CONCRETE_INSTRUCTION(CompareNumericAndBranch)
 
  private:
   Representation observed_input_representation_[2];
   Token::Value token_;
 };
 
 
 class HCompareObjectEqAndBranch: public HTemplateControlInstruction<2, 2> {
  public:
@@ skipping 1939 matching lines @@
     // tagged[tagged]
     return Representation::Tagged();
   }
 
   virtual HValue* Canonicalize();
 
   DECLARE_CONCRETE_INSTRUCTION(LoadKeyedGeneric)
 };
 
 
-class HStoreNamedField: public HTemplateInstruction<3> {
+class HStoreNamedField: public HTemplateInstruction<2> {
  public:
   DECLARE_INSTRUCTION_FACTORY_P3(HStoreNamedField, HValue*,
                                  HObjectAccess, HValue*);
 
   DECLARE_CONCRETE_INSTRUCTION(StoreNamedField)
 
   virtual bool HasEscapingOperandAt(int index) { return index == 1; }
   virtual Representation RequiredInputRepresentation(int index) {
     if (index == 0 && access().IsExternalMemory()) {
       // object must be external in case of external memory access
@@ skipping 11 matching lines @@
     ASSERT(side_effect == kChangesNewSpacePromotion);
     new_space_dominator_ = dominator;
   }
   virtual void PrintDataTo(StringStream* stream);
 
   void SkipWriteBarrier() { write_barrier_mode_ = SKIP_WRITE_BARRIER; }
   bool IsSkipWriteBarrier() const {
     return write_barrier_mode_ == SKIP_WRITE_BARRIER;
   }
 
-  HValue* object() const { return OperandAt(0); }
-  HValue* value() const { return OperandAt(1); }
-  HValue* transition() const { return OperandAt(2); }
+  HValue* object() { return OperandAt(0); }
+  HValue* value() { return OperandAt(1); }
 
   HObjectAccess access() const { return access_; }
-  HValue* new_space_dominator() const { return new_space_dominator_; }
-  bool has_transition() const { return has_transition_; }
-
-  Handle<Map> transition_map() const {
-    if (has_transition()) {
-      return Handle<Map>::cast(HConstant::cast(transition())->handle());
-    } else {
-      return Handle<Map>();
-    }
-  }
-
-  void SetTransition(HConstant* map_constant, CompilationInfo* info) {
-    ASSERT(!has_transition());  // Only set once.
-    Handle<Map> map = Handle<Map>::cast(map_constant->handle());
+  Handle<Map> transition() const { return transition_; }
+  UniqueValueId transition_unique_id() const { return transition_unique_id_; }
+  void SetTransition(Handle<Map> map, CompilationInfo* info) {
+    ASSERT(transition_.is_null());  // Only set once.
     if (map->CanBeDeprecated()) {
       map->AddDependentCompilationInfo(DependentCode::kTransitionGroup, info);
     }
-    SetOperandAt(2, map_constant);
-    has_transition_ = true;
+    transition_ = map;
   }
+  HValue* new_space_dominator() const { return new_space_dominator_; }
 
   bool NeedsWriteBarrier() {
     ASSERT(!(FLAG_track_double_fields && field_representation().IsDouble()) ||
-           !has_transition());
+           transition_.is_null());
     if (IsSkipWriteBarrier()) return false;
     if (field_representation().IsDouble()) return false;
     if (field_representation().IsSmi()) return false;
     if (field_representation().IsInteger32()) return false;
     if (field_representation().IsExternal()) return false;
     return StoringValueNeedsWriteBarrier(value()) &&
         ReceiverObjectNeedsWriteBarrier(object(), new_space_dominator());
   }
 
   bool NeedsWriteBarrierForMap() {
     if (IsSkipWriteBarrier()) return false;
     return ReceiverObjectNeedsWriteBarrier(object(), new_space_dominator());
   }
 
+  virtual void FinalizeUniqueValueId() {
+    transition_unique_id_ = UniqueValueId(transition_);
+  }
+
   Representation field_representation() const {
     return access_.representation();
   }
 
  private:
   HStoreNamedField(HValue* obj,
                    HObjectAccess access,
                    HValue* val)
       : access_(access),
+        transition_(),
+        transition_unique_id_(),
         new_space_dominator_(NULL),
-        write_barrier_mode_(UPDATE_WRITE_BARRIER),
-        has_transition_(false) {
+        write_barrier_mode_(UPDATE_WRITE_BARRIER) {
     SetOperandAt(0, obj);
     SetOperandAt(1, val);
-    SetOperandAt(2, obj);
     access.SetGVNFlags(this, true);
   }
 
   HObjectAccess access_;
+  Handle<Map> transition_;
+  UniqueValueId transition_unique_id_;
   HValue* new_space_dominator_;
-  WriteBarrierMode write_barrier_mode_ : 1;
-  bool has_transition_ : 1;
+  WriteBarrierMode write_barrier_mode_;
 };
 
 
 class HStoreNamedGeneric: public HTemplateInstruction<3> {
  public:
   HStoreNamedGeneric(HValue* context,
                      HValue* object,
                      Handle<String> name,
                      HValue* value,
                      StrictModeFlag strict_mode_flag)
@@ skipping 773 matching lines @@
   virtual bool IsDeletable() const { return true; }
 };
 
 
 #undef DECLARE_INSTRUCTION
 #undef DECLARE_CONCRETE_INSTRUCTION
 
 } }  // namespace v8::internal
 
 #endif  // V8_HYDROGEN_INSTRUCTIONS_H_