Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(423)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: src/hydrogen-instructions.h

Issue 12226112: Infrastructure classes for evaluating numeric relations between values. (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: Added basic support for numeric relations with the result of an arithmetical operation. Created 7 years, 10 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/arm/lithium-arm.cc ('k') | src/hydrogen-instructions.cc » ('j') | src/hydrogen-instructions.cc » ('J')
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/hydrogen-instructions.h
diff --git a/src/hydrogen-instructions.h b/src/hydrogen-instructions.h
index 3e53eca7092293b0d2c5a41766db8d8c50ec60fc..0ea82b68d17bde64f1c0a010210d87c7edd2b8f6 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) \
@@ -713,6 +714,9 @@ class HValue: public ZoneObject {
UpdateRedefinedUsesInner<Dominates>();
}
+ bool IsInteger32Constant();
+ int32_t GetInteger32Constant();
+
bool IsDefinedAfter(HBasicBlock* other) const;
// Operands.
@@ -839,6 +843,123 @@ class HValue: public ZoneObject {
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.Is
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.
@@ -901,6 +1022,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) {
+ return false;
+ }
+
static GVNFlagSet AllDependsOnFlagSet() {
GVNFlagSet result;
// Create changes mask.
@@ -1125,6 +1252,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);
+ }
+
+ 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.
@@ -3154,6 +3325,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);
@@ -3741,6 +3914,23 @@ class HAdd: public HArithmeticBinaryOperation {
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:
@@ -3766,6 +3956,17 @@ class HSub: public HArithmeticBinaryOperation {
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:
@@ -3794,6 +3995,24 @@ class HMul: public HArithmeticBinaryOperation {
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 imp
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:
@@ -3967,6 +4186,8 @@ class HShl: public HBitwiseBinaryOperation {
HValue* left,
HValue* right);
+ virtual bool CheckRelation(NumericRelation relation, HValue* other);
+
DECLARE_CONCRETE_INSTRUCTION(Shl)
protected:
@@ -3986,6 +4207,8 @@ class HShr: public HBitwiseBinaryOperation {
HValue* left,
HValue* right);
+ virtual bool CheckRelation(NumericRelation relation, HValue* other);
+
DECLARE_CONCRETE_INSTRUCTION(Shr)
protected:
« no previous file with comments | « src/arm/lithium-arm.cc ('k') | src/hydrogen-instructions.cc » ('j') | src/hydrogen-instructions.cc » ('J')

Powered by Google App Engine
This is Rietveld 408576698