Better value range propagation by supporting negating ranges.

lib/compiler/implementation/ssa/value_range_analyzer.dart

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 /**
  * A [Value] represents both symbolic values like the value of a
  * parameter, or the length of an array, and concrete values, like
  * constants.
  */
 abstract class Value {
   const Value();
 
   Value operator +(Value other);
   Value operator -(Value other);

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

Don't you want to add unary minus here as well?

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

Yes. Done.

   Value operator &(Value other);
 
   Value min(Value other) {
     if (this == other) return this;
     if (other == const MinIntValue()) return other;
     if (other == const MaxIntValue()) return this;
     Value value = this - other;
     if (value.isPositive()) return other;
     if (value.isNegative()) return this;
     return const UnknownValue();
@@ skipping 15 matching lines @@
 }
 
 /**
  * An [IntValue] contains a constant integer value.
  */
 class IntValue extends Value {
   final int value;
   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;
       if (other.isPositive()) return new IntValue(-value);
       return const UnknownValue();
     }
     return new IntValue(value & other.value);
   }
 
   Value min(other) {
@@ skipping 18 matching lines @@
 }
 
 /**
  * The [MaxIntValue] represents the maximum value an integer can have,
  * which is currently +infinity.
  */
 class MaxIntValue extends Value {
   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);
     return this;
   }
   Value min(Value other) => other;
   Value max(Value other) => this;
   String toString() => 'Max';
   bool isNegative() => false;
   bool isPositive() => true;
 }
 
 /**
  * The [MinIntValue] represents the minimum value an integer can have,
  * which is currently -infinity.
  */
 class MinIntValue extends Value {
   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;
   }
   Value min(Value other) => this;
   Value max(Value other) => other;
   String toString() => 'Min';
   bool isNegative() => true;
   bool isPositive() => false;
 }
 
 /**
  * The [UnknownValue] is the sentinel in our analysis to mark an
  * operation that could not be done because of too much complexity.
  */
 class UnknownValue extends Value {
   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();
   bool isNegative() => false;
   bool isPositive() => false;
   String toString() => 'Unknown';
 }
 
 /**
  * A symbolic value representing an [HInstruction].
  */
 class InstructionValue extends Value {
   final HInstruction instruction;
   InstructionValue(this.instruction);
 
   bool operator ==(other) {
     if (other is !InstructionValue) return false;
     return this.instruction == other.instruction;
   }
 
   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;
   }
 
   bool isNegative() => false;
   bool isPositive() => false;
 
   String toString() => 'Instruction: $instruction';
 }
 
 /**
  * Special value for instructions that represent the length of an
  * array. The difference with an [InstructionValue] is that we know
  * the value is positive.
  */
 class LengthValue extends InstructionValue {
   LengthValue(HInstruction instruction) : super(instruction);
   bool isPositive() => true;
   String toString() => 'Length: $instruction';
 }
 
 /**
  * Represents a binary operation on two [Value], where the operation
  * 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 (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)
-    Value value = left - other;
-    if (value != const UnknownValue() && value is! OperationValue) {
-      return operation.apply(value, right);
+  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].
-    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();
+  }
+
+  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() => 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
  * included.
  */
 class Range {
   final Value lower;
   final Value upper;
@@ skipping 32 matching lines @@
   }
 
   Range operator +(Range other) {
     return new Range.normalize(lower + other.lower, upper + other.upper);
   }
 
   Range operator -(Range other) {
     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()
         && lower is IntValue
         && other.lower is IntValue) {
       return new Range(lower & other.lower, upper & other.upper);
     }
     if (isPositive() && other.isPositive()) {
       Value up = upper.min(other.upper);
       if (up == const UnknownValue()) {
@@ skipping 495 matching lines @@
     if (instruction is HPhi && !instruction.block.isLoopHeader()) {
       HInstruction result = unwrap(instruction.inputs[0]);
       for (int i = 1; i < instruction.inputs.length; i++) {
         if (result != unwrap(instruction.inputs[i])) return instruction;
       }
       return result;
     }
     return instruction;
   }
 }