Infrastructure classes for evaluating numeric relations between values.

src/hydrogen-instructions.h

Index: src/hydrogen-instructions.h
diff --git a/src/hydrogen-instructions.h b/src/hydrogen-instructions.h
index 3e53eca7092293b0d2c5a41766db8d8c50ec60fc..a3a40b1565fd71a6a4a2a684b16634d2b1de90a5 100644
--- a/src/hydrogen-instructions.h
+++ b/src/hydrogen-instructions.h
@@ -147,6 +147,7 @@ class LChunkBuilder;
   V(MathMinMax)                                \
   V(Mod)                                       \
   V(Mul)                                       \
+  V(NumericConstraint)                         \
   V(ObjectLiteral)                             \
   V(OsrEntry)                                  \
   V(OuterContext)                              \
@@ -839,6 +840,102 @@ class HValue: public ZoneObject {
   virtual void Verify() = 0;
 #endif
 
+  class NumericRelation {

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

I'd prefer making this a top-level class.

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

Done.

+   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_); }

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

C++ style casts please

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

Done.

+
+    static NumericRelation None() { return NumericRelation(NONE); }

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

I don't think these add much value. Let's just call the constructor.

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

Not having then would mean having to write constructor calls like
"NumericRelation(NumericRelation::EQ)", so these static methods make the code
less verbose in the end.

+    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) {

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

I'd prefer an Equals() method over operator overloading. (If these are used at
all.)

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

I added an "IsNone()" method instead.
I think that in all other cases calling "Implies()" is better than checking for
"hard equality" anyway.

+      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 y" is true.
+    bool Implies(NumericRelation other) {
+      switch (kind_) {
+        case NONE: return false;
+        case EQ: return (other.kind_ == EQ)
+            || (other.kind_ == GE)
+            || (other.kind_ == LE);
+        case GT: return (other.kind_ == GT)
+            || (other.kind_ == GE)
+            || (other.kind_ == NE);
+        case LT: return (other.kind_ == LT)
+            || (other.kind_ == LE)
+            || (other.kind_ == NE);
+        case GE: return (other.kind_ == GE);
+        case LE: return (other.kind_ == LE);
+        case NE: return (other.kind_ == NE);
+        default:

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

no default case

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

Done.

+          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) {
+    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.
@@ -901,6 +998,12 @@ class HValue: public ZoneObject {
     }
   }
 
+  // Informative definitions can override this method to state any numeric
+  // relation they provide on the redefined value.
+  virtual bool CheckRelation(NumericRelation relation, HValue* other) {

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

This method's name should clearly express its relation to IsRelationTrue().
Maybe IsRelationTrueInternal? I'm open to better suggestions.

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

Done.

+    return false;
+  }
+
   static GVNFlagSet AllDependsOnFlagSet() {
     GVNFlagSet result;
     // Create changes mask.
@@ -1125,6 +1228,50 @@ class HDummyUse: public HTemplateInstruction<1> {
 };
 
 
+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);

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

return representation() (or return constrained_value->representation(), which is
the same thing).

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

Done.

+  }
+
+  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,

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

no "explicit"

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

Done.

+                              HValue* related_value,

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

please swap the last two arguments

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

Done.

+                              NumericRelation relation)
+    : relation_(relation) {

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

nit: 4-space indent

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

Done.

+    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.
@@ -3154,6 +3301,8 @@ class HBoundsCheck: public HTemplateInstruction<2> {
     return Representation::Integer32();
   }
 
+  virtual bool CheckRelation(NumericRelation relation, HValue* related_value);
+
   virtual void PrintDataTo(StringStream* stream);
   virtual void InferRepresentation(HInferRepresentation* h_infer);