Infrastructure classes for evaluating numeric relations between values.

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 129 matching lines @@
   V(LoadKeyed)                                 \
   V(LoadKeyedGeneric)                          \
   V(LoadNamedField)                            \
   V(LoadNamedFieldPolymorphic)                 \
   V(LoadNamedGeneric)                          \
   V(MapEnumLength)                             \
   V(MathFloorOfDiv)                            \
   V(MathMinMax)                                \
   V(Mod)                                       \
   V(Mul)                                       \
+  V(NumericConstraint)                         \
   V(ObjectLiteral)                             \
   V(OsrEntry)                                  \
   V(OuterContext)                              \
   V(Parameter)                                 \
   V(Power)                                     \
   V(PushArgument)                              \
   V(Random)                                    \
   V(RegExpLiteral)                             \
   V(Return)                                    \
   V(Ror)                                       \
@@ skipping 546 matching lines @@
 
   virtual void AddInformativeDefinitions() {}
 
   void UpdateRedefinedUsesWhileSettingUpInformativeDefinitions() {
     UpdateRedefinedUsesInner<TestDominanceUsingProcessedFlag>();
   }
   void UpdateRedefinedUses() {
     UpdateRedefinedUsesInner<Dominates>();
   }
 
+  bool IsInteger32Constant();
+  int32_t GetInteger32Constant();
+
   bool IsDefinedAfter(HBasicBlock* other) const;
 
   // Operands.
   virtual int OperandCount() = 0;
   virtual HValue* OperandAt(int index) const = 0;
   void SetOperandAt(int index, HValue* value);
 
   void DeleteAndReplaceWith(HValue* other);
   void ReplaceAllUsesWith(HValue* other);
   bool HasNoUses() const { return use_list_ == NULL; }
@@ skipping 106 matching lines @@
   }
 
   bool IsDead() const {
     return HasNoUses() && !HasObservableSideEffects() && IsDeletable();
   }
 
 #ifdef DEBUG
   virtual void Verify() = 0;
 #endif
 
+  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) 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 operator==(const NumericRelation& other) {
+      return kind_ == other.kind_;
+    }
+    bool operator!=(const NumericRelation& other) {
+      return kind_ != other.kind_;
+    }
+
+    // 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 "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);
+        default:
+          UNREACHABLE();
+          return false;
+      }
+    }
+
+    // The semantics of "IsExtendable" is that if
+    // "rel.IsExtendable(direction) is true" then

[Jakob Kummerow, 2013/02/12 15:10:42]

nit: position of the closing quote:
    // "rel.IsExtendable(direction)" is true then

[Massi, 2013/02/13 11:56:42]

Done.

+    // "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;
+    }
+
+   private:
+    explicit NumericRelation(Kind kind) : kind_(kind) {}
+
+    Kind kind_;
+  };
+
+  // This method is recursive but it is guaranteed to terminate because
+  // RedefinedOperand() always dominates "this".
+  bool IsRelationTrue(NumericRelation relation, HValue* other) {
+    if (this == other) {
+      return NumericRelation::Eq().Implies(relation);
+    }
+
+    bool result = CheckRelation(relation, other) ||
+        other->CheckRelation(relation.Reversed(), this);
+    if (!result) {
+      HValue* redefined = RedefinedOperand();
+      if (redefined != NULL) {
+        result = redefined->IsRelationTrue(relation, other);
+      }
+    }
+    return result;
+  }
+
+  HValue* AddNumericConstraint(HInstruction* insertion_point,
+                               HValue* related_value,
+                               NumericRelation relation);
+
  protected:
   // 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 42 matching lines @@
     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.
+  virtual bool CheckRelation(NumericRelation relation, HValue* other) {
+    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 204 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* New(HInstruction* insertion_point,
+                                 HValue* constrained_value,
+                                 HValue* related_value,
+                                 NumericRelation relation);
+
+  HValue* constrained_value() { return OperandAt(0); }
+  HValue* related_value() { return OperandAt(1); }
+  NumericRelation relation() { return relation_; }
+
+  virtual int RedefinedOperandIndex() { return 0; }
+
+  virtual Representation RequiredInputRepresentation(int index) {
+    return constrained_value()->RequiredInputRepresentation(index);
+  }
+
+  virtual void PrintDataTo(StringStream* stream);
+
+  virtual bool CheckRelation(NumericRelation other_relation,
+                             HValue* other_related_value) {
+    if (related_value() == other_related_value) {
+      return relation().Implies(other_relation);
+    } else {
+      return false;
+    }
+  }
+
+  DECLARE_CONCRETE_INSTRUCTION(NumericConstraint)
+
+ private:
+  explicit HNumericConstraint(HValue* constrained_value,
+                              HValue* related_value,
+                              NumericRelation relation)
+    : relation_(relation) {
+    SetOperandAt(0, constrained_value);
+    SetOperandAt(1, related_value);
+    set_representation(constrained_value->representation());
+  }
+
+  NumericRelation relation_;
+};
+
+
 // We insert soft-deoptimize when we hit code with unknown typefeedback,
 // so that we get a chance of re-optimizing with useful typefeedback.
 // HSoftDeoptimize does not end a basic block as opposed to HDeoptimize.
 class HSoftDeoptimize: public HTemplateInstruction<0> {
  public:
   virtual Representation RequiredInputRepresentation(int index) {
     return Representation::None();
   }
 
   DECLARE_CONCRETE_INSTRUCTION(SoftDeoptimize)
@@ skipping 2009 matching lines @@
   bool skip_check() { return skip_check_; }
   void set_skip_check(bool skip_check) { skip_check_ = skip_check; }
 
   virtual Representation RequiredInputRepresentation(int arg_index) {
     return representation();
   }
   virtual Representation observed_input_representation(int index) {
     return Representation::Integer32();
   }
 
+  virtual bool CheckRelation(NumericRelation relation, HValue* related_value);
+
   virtual void PrintDataTo(StringStream* stream);
   virtual void InferRepresentation(HInferRepresentation* h_infer);
 
   HValue* index() { return OperandAt(0); }
   HValue* length() { return OperandAt(1); }
 
   virtual int RedefinedOperandIndex() { return 0; }
 
   DECLARE_CONCRETE_INSTRUCTION(BoundsCheck)
 
@@ skipping 567 matching lines @@
 
   static HInstruction* NewHAdd(Zone* zone,
                                HValue* context,
                                HValue* left,
                                HValue* right);
 
   virtual HType CalculateInferredType();
 
   virtual HValue* Canonicalize();
 
+  virtual bool CheckRelation(NumericRelation relation, HValue* other) {
+    HValue* base = NULL;
+    int32_t offset = 0;
+    if (left()->IsInteger32Constant()) {
+      base = right();
+      offset = left()->GetInteger32Constant();
+    } else if (right()->IsInteger32Constant()) {
+      base = left();
+      offset = right()->GetInteger32Constant();
+    } else {
+      return false;
+    }
+
+    return relation.IsExtendable(offset)
+        ? base->IsRelationTrue(relation, other) : false;
+  }
+
   DECLARE_CONCRETE_INSTRUCTION(Add)
 
  protected:
   virtual bool DataEquals(HValue* other) { return true; }
 
   virtual Range* InferRange(Zone* zone);
 };
 
 
 class HSub: public HArithmeticBinaryOperation {
  public:
   HSub(HValue* context, HValue* left, HValue* right)
       : HArithmeticBinaryOperation(context, left, right) {
     SetFlag(kCanOverflow);
   }
 
   virtual HValue* EnsureAndPropagateNotMinusZero(BitVector* visited);
 
   virtual HValue* Canonicalize();
 
   static HInstruction* NewHSub(Zone* zone,
                                HValue* context,
                                HValue* left,
                                HValue* right);
 
+  virtual bool CheckRelation(NumericRelation relation, HValue* other) {
+    if (right()->IsInteger32Constant()) {
+      HValue* base = left();
+      int32_t offset = right()->GetInteger32Constant();
+      return relation.IsExtendable(offset)

[Jakob Kummerow, 2013/02/12 15:10:42]

-offset

[Massi, 2013/02/13 11:56:42]

Done.

+          ? base->IsRelationTrue(relation, other) : false;
+    } else {
+      return false;
+    }
+  }
+
   DECLARE_CONCRETE_INSTRUCTION(Sub)
 
  protected:
   virtual bool DataEquals(HValue* other) { return true; }
 
   virtual Range* InferRange(Zone* zone);
 };
 
 
 class HMul: public HArithmeticBinaryOperation {
  public:
   HMul(HValue* context, HValue* left, HValue* right)
       : HArithmeticBinaryOperation(context, left, right) {
     SetFlag(kCanOverflow);
   }
 
   virtual HValue* EnsureAndPropagateNotMinusZero(BitVector* visited);
 
   // Only commutative if it is certain that not two objects are multiplicated.
   virtual bool IsCommutative() const {
     return !representation().IsTagged();
   }
 
   static HInstruction* NewHMul(Zone* zone,
                                HValue* context,
                                HValue* left,
                                HValue* right);
 
+  // The idea is that "k > 1" implies that "base * k >= base".

[Jakob Kummerow, 2013/02/12 15:10:42]

As discussed, we should probably postpone this implementation until we have a
reason to add it :-)

[Massi, 2013/02/13 11:56:42]

Done.

+  virtual bool CheckRelation(NumericRelation relation, HValue* other) {
+    HValue* base = NULL;
+    int32_t k = 0;
+    if (left()->IsInteger32Constant()) {
+      base = right();
+      k = left()->GetInteger32Constant();
+    } else if (right()->IsInteger32Constant()) {
+      base = left();
+      k = right()->GetInteger32Constant();
+    } else {
+      return false;
+    }
+
+    return (k > 1 && relation.IsExtendable(1))
+        ? base->IsRelationTrue(relation, other) : false;
+  }
+
   DECLARE_CONCRETE_INSTRUCTION(Mul)
 
  protected:
   virtual bool DataEquals(HValue* other) { return true; }
 
   virtual Range* InferRange(Zone* zone);
 };
 
 
 class HMod: public HArithmeticBinaryOperation {
@@ skipping 153 matching lines @@
   HShl(HValue* context, HValue* left, HValue* right)
       : HBitwiseBinaryOperation(context, left, right) { }
 
   virtual Range* InferRange(Zone* zone);
 
   static HInstruction* NewHShl(Zone* zone,
                                HValue* context,
                                HValue* left,
                                HValue* right);
 
+  virtual bool CheckRelation(NumericRelation relation, HValue* other);
+
   DECLARE_CONCRETE_INSTRUCTION(Shl)
 
  protected:
   virtual bool DataEquals(HValue* other) { return true; }
 };
 
 
 class HShr: public HBitwiseBinaryOperation {
  public:
   HShr(HValue* context, HValue* left, HValue* right)
       : HBitwiseBinaryOperation(context, left, right) { }
 
   virtual Range* InferRange(Zone* zone);
 
   static HInstruction* NewHShr(Zone* zone,
                                HValue* context,
                                HValue* left,
                                HValue* right);
 
+  virtual bool CheckRelation(NumericRelation relation, HValue* other);
+
   DECLARE_CONCRETE_INSTRUCTION(Shr)
 
  protected:
   virtual bool DataEquals(HValue* other) { return true; }
 };
 
 
 class HSar: public HBitwiseBinaryOperation {
  public:
   HSar(HValue* context, HValue* left, HValue* right)
@@ skipping 1786 matching lines @@
   virtual bool IsDeletable() const { return true; }
 };
 
 
 #undef DECLARE_INSTRUCTION
 #undef DECLARE_CONCRETE_INSTRUCTION
 
 } }  // namespace v8::internal
 
 #endif  // V8_HYDROGEN_INSTRUCTIONS_H_