Better value range propagation by supporting negating ranges.

lib/compiler/implementation/ssa/value_range_analyzer.dart

Index: lib/compiler/implementation/ssa/value_range_analyzer.dart
===================================================================
--- lib/compiler/implementation/ssa/value_range_analyzer.dart	(revision 13347)
+++ lib/compiler/implementation/ssa/value_range_analyzer.dart	(working copy)
@@ -47,17 +47,22 @@
   const IntValue(this.value);
 
   Value operator +(other) {
+    if (other.isZero()) return this;
     if (other is !IntValue) return other + this;
     return new IntValue(value + other.value);
   }
 
   Value operator -(other) {
-    if (other is !IntValue) {
-      return new OperationValue(this, other, const SubtractOperation());
-    }
+    if (other.isZero()) return this;
+    if (other is !IntValue) return -other + this;
     return new IntValue(value - other.value);
   }
 
+  Value operator -() {
+    if (isZero()) return this;
+    return new IntValue(-value);
+  }
+
   Value operator &(other) {
     if (other is !IntValue) {
       if (isPositive()) return this;
@@ -96,6 +101,7 @@
   const MaxIntValue();
   Value operator +(Value other) => this;
   Value operator -(Value other) => this;
+  Value operator -() => const MinIntValue();
   Value operator &(Value other) {
     if (other.isPositive()) return other;
     if (other.isNegative()) return const IntValue(0);
@@ -116,6 +122,7 @@
   const MinIntValue();
   Value operator +(Value other) => this;
   Value operator -(Value other) => this;
+  Value operator -() => const MaxIntValue();
   Value operator &(Value other) {
     if (other.isPositive()) return const IntValue(0);
     return this;
@@ -135,6 +142,7 @@
   const UnknownValue();
   Value operator +(Value other) => const UnknownValue();
   Value operator -(Value other) => const UnknownValue();
+  Value operator -() => const UnknownValue();
   Value operator &(Value other) => const UnknownValue();
   Value min(Value other) => const UnknownValue();
   Value max(Value other) => const UnknownValue();
@@ -157,15 +165,37 @@
 
   Value operator +(Value other) {
     if (other.isZero()) return this;
-    return new OperationValue(this, other, const AddOperation());
+    if (other is IntValue) {
+      if (other.isNegative()) {
+        return new SubtractValue(this, -other);
+      }
+      return new AddValue(this, other);
+    }
+    if (other is InstructionValue) {
+      return new AddValue(this, other);
+    }
+    return other + this;
   }
 
   Value operator -(Value other) {
     if (other.isZero()) return this;
     if (this == other) return const IntValue(0);
-    return new OperationValue(this, other, const SubtractOperation());
+    if (other is IntValue) {
+      if (other.isNegative()) {
+        return new AddValue(this, -other);
+      }
+      return new SubtractValue(this, other);
+    }
+    if (other is InstructionValue) {
+      return new SubtractValue(this, other);
+    }
+    return -other + this;
   }
 
+  Value operator -() {
+    return new NegateValue(this);
+  }
+
   Value operator &(Value other) {
     if (other is IntValue) return other & this;
     return this;
@@ -193,58 +223,157 @@
  * did not yield a canonical value.
  */
 class OperationValue extends Value {
+  Operation operation;
+}
+
+class BinaryOperationValue extends OperationValue {
   final Value left;
   final Value right;
-  final BinaryOperation operation;
-  OperationValue(this.left, this.right, this.operation);
+  BinaryOperationValue(this.left, this.right);
+}
 
+class AddValue extends BinaryOperationValue {
+  AddValue(left, right) : super(left, right);
+
   bool operator ==(other) {
-    if (other is !OperationValue) return false;
-    return left == other.left
-        && right == other.right
-        && operation == other.operation;
+    if (other is !AddValue) return false;
+    return (left == other.left && right == other.right)
+      || (left == other.right && right == other.left);
   }
 
-  Value operator +(Value other) => const UnknownValue();
   Value operator &(Value other) => const UnknownValue();
+  Value operator -() => -left - right;

[Søren Gjesse, 2012/10/08 14:00:42]

Maybe -(left + right) instead.

[ngeoffray, 2012/10/08 14:16:39]

Calling -(left + right) will actually yield -left - right, after a few more
indirections. I'd rather not play with parenthesized expressions just yet :)

 
+  Value operator +(Value other) {
+    if (other.isZero()) return this;
+    Value value = left + other;
+    if (value != const UnknownValue() && value is! BinaryOperationValue) {
+      return value + right;
+    }
+    // If the result is not simple enough, we try the same approach
+    // with [right].
+    value = right + other;
+    if (value != const UnknownValue() && value is! BinaryOperationValue) {
+      return left + value;
+    }
+    return const UnknownValue();
+  }
+
   Value operator -(Value other) {
-    if (operation is! SubtractOperation && operation is! AddOperation) {
-      return const UnknownValue();
-    }
-    // We try to create a simple [Value] out of this operation. So we
-    // first try to substract [other] to [left]. If the result is simple
-    // enough (not unknown and not an operation), we return the result
-    // of doing the operation of this [OperationValue] on the previous
-    // result and [right].
-    //
-    // For example:
-    // OperationValue(LengthValue(i1), IntValue(42), '-') - LengthValue(i1)
-    //
-    // Will return IntValue(-42)
+    if (other.isZero()) return this;
     Value value = left - other;
-    if (value != const UnknownValue() && value is! OperationValue) {
-      return operation.apply(value, right);
+    if (value != const UnknownValue() && value is! BinaryOperationValue) {
+      return value + right;
     }
     // If the result is not simple enough, we try the same approach
     // with [right].
-    if (operation is SubtractOperation) {
-      value = right + other;
-    } else {
-      assert(operation is AddOperation);
-      value = right - other;
+    value = right - other;
+    if (value != const UnknownValue() && value is! BinaryOperationValue) {
+      return left + value;
     }
-    if (value != const UnknownValue() && value is! OperationValue) {
-      return operation.apply(left, value);
+    return const UnknownValue();
+  }
+
+  bool isNegative() => left.isNegative() && right.isNegative();
+  bool isPositive() => left.isPositive() && right.isPositive();
+  String toString() => '$left + $right';
+}
+
+class SubtractValue extends BinaryOperationValue {
+  SubtractValue(left, right) : super(left, right);
+
+  bool operator ==(other) {
+    if (other is !SubtractValue) return false;
+    return left == other.left && right == other.right;
+  }
+
+  Value operator &(Value other) => const UnknownValue();
+  Value operator -() => right - left;
+
+  Value operator +(Value other) {
+    if (other.isZero()) return this;
+    Value value = left + other;
+    if (value != const UnknownValue() && value is! BinaryOperationValue) {
+      return value - right;
     }
+    // If the result is not simple enough, we try the same approach
+    // with [right].
+    value = other - right;
+    if (value != const UnknownValue() && value is! BinaryOperationValue) {
+      return left + value;
+    }
     return const UnknownValue();
   }
 
+  Value operator -(Value other) {
+    if (other.isZero()) return this;
+    Value value = left - other;
+    if (value != const UnknownValue() && value is! BinaryOperationValue) {
+      return value - right;
+    }
+    // If the result is not simple enough, we try the same approach
+    // with [right].
+    value = right + other;
+    if (value != const UnknownValue() && value is! BinaryOperationValue) {
+      return left - value;
+    }
+    return const UnknownValue();
+  }
+
   bool isNegative() => false;

[Søren Gjesse, 2012/10/08 14:00:42]

Isn't this negative if left is negative and right is positive - or am I missing
something here?

[ngeoffray, 2012/10/08 14:16:39]

You're right. Done.

-  bool isPositive() => false;
-  String toString() => '$left ${operation.name} $right';
+  bool isPositive() => left.isPositive() && right.isNegative();
+  String toString() => '$left - $right';
 }
 
+class NegateValue extends OperationValue {
+  final Value value;
+  NegateValue(this.value);
+
+  bool operator ==(other) {
+    if (other is !NegateValue) return false;
+    return value == other.value;
+  }
+
+  Value operator +(other) {
+    if (other.isZero()) return this;
+    if (other == value) return const IntValue(0);
+    if (other is NegateValue) return this - other.value;
+    if (other is IntValue) {
+      if (other.isNegative()) {
+        return new SubtractValue(this, -other);
+      }
+      return new SubtractValue(other, value);
+    }
+    if (other is InstructionValue) {
+      return new SubtractValue(other, value);
+    }
+    return other - value;
+  }
+
+  Value operator &(Value other) => const UnknownValue();
+
+  Value operator -(other) {
+    if (other.isZero()) return this;
+    if (other is IntValue) {
+      if (other.isNegative()) {
+        return new SubtractValue(-other, value);
+      }
+      return new SubtractValue(this, other);
+    }
+    if (other is InstructionValue) {
+      return new SubtractValue(this, other);
+    }
+    if (other is NegateValue) return this + other.value;
+    return -other - value;
+  }
+
+  Value operator -() => value;
+
+  bool isNegative() => value.isPositive();
+  bool isPositive() => value.isNegative();
+  String toString() => '-$value';
+}
+
 /**
  * A [Range] represents the possible integer values an instruction
  * can have, from its [lower] bound to its [upper] bound, both
@@ -295,6 +424,10 @@
     return new Range.normalize(lower - other.upper, upper - other.lower);
   }
 
+  Range operator -() {
+    return new Range.normalize(-upper, -lower);
+  }
+
   Range operator &(Range other) {
     if (isSingleValue()
         && other.isSingleValue()