Deal with more conditional expressions in the value range analyzer.

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 13020)
+++ lib/compiler/implementation/ssa/value_range_analyzer.dart	(working copy)
@@ -298,10 +298,22 @@
     return other.lower == lower && other.upper == upper;
   }
 
-  bool isLessThan(Range other) {
+  bool operator <(Range other) {
     return upper != other.lower && upper.min(other.lower) == upper;
   }
 
+  bool operator >(Range other) {
+    return lower != other.upper && lower.max(other.upper) == lower;
+  }
+
+  bool operator <=(Range other) {
+    return upper.min(other.lower) == upper;
+  }
+
+  bool operator >=(Range other) {
+    return lower.max(other.upper) == lower;
+  }
+
   bool isNegative() => upper.isNegative();
   bool isPositive() => lower.isPositive();
 
@@ -435,7 +447,7 @@
     if (indexRange.isPositive() && belowLength) {
       check.block.rewrite(check, check.index);
       check.block.remove(check);
-    } else if (indexRange.isNegative() || lengthRange.isLessThan(indexRange)) {
+    } else if (indexRange.isNegative() || lengthRange < indexRange) {
       check.staticChecks = HBoundsCheck.ALWAYS_FALSE;
       // The check is always false, and whatever instruction it
       // dominates is dead code.
@@ -471,24 +483,39 @@
     return indexRange;
   }
 
-  Range visitLess(HLess less) {
-    HInstruction right = less.right;
-    HInstruction left = less.left;
+  Range visitRelational(HRelation relational) {
+    HInstruction right = relational.right;
+    HInstruction left = relational.left;
     if (!left.isInteger(types)) return const Range.unbound();
     if (!right.isInteger(types)) return const Range.unbound();
-    if (ranges[left].isLessThan(ranges[right])) {
-      less.block.rewrite(less, graph.addConstantBool(true, constantSystem));
-      less.block.remove(less);
-      return const Range.unbound();
+    Operation operation = relational.operation(constantSystem);
+    Range rightRange = ranges[relational.right];
+    Range leftRange = ranges[relational.left];
+
+    if (relational is HEquals || relational is HIdentity) {
+      handleEqualityCheck(relational);
+    } else if (operation.apply(leftRange, rightRange)) {
+      relational.block.rewrite(
+          relational, graph.addConstantBool(true, constantSystem));
+      relational.block.remove(relational);
+    } else if (reverseOperation(operation).apply(leftRange, rightRange)) {
+      relational.block.rewrite(
+          relational, graph.addConstantBool(false, constantSystem));
+      relational.block.remove(relational);
     }
-    if (ranges[right].isLessThan(ranges[left])) {
-      less.block.rewrite(less, graph.addConstantBool(false, constantSystem));
-      less.block.remove(less);
-      return const Range.unbound();
-    }
     return const Range.unbound();
   }
 
+  void handleEqualityCheck(HRelational node) {
+    Range right = ranges[node.right];
+    Range left = ranges[node.left];
+    if (left.lower == left.upper && left == right) {

[Søren Gjesse, 2012/10/02 08:07:20]

Maybe have an isSingleValue on Range and express this as (left.isSingleValue &&
right.isSingleValue && left == right)

[ngeoffray, 2012/10/04 08:51:08]

Done.

+      node.block.rewrite(
+          node, graph.addConstantBool(true, constantSystem));
+      node.block.remove(node);
+    }
+  }
+
   Range handleBinaryOperation(HBinaryArithmetic instruction) {
     if (!instruction.isInteger(types)) return const Range.unbound();
     return instruction.operation(constantSystem).apply(
@@ -550,31 +577,85 @@
     return newInstruction;
   }
 
+  static Operation reverseOperation(BinaryOperation operation) {
+    if (operation == const LessOperation()) {
+      return const GreaterEqualOperation();
+    } else if (operation == const LessEqualOperation()) {
+      return const GreaterOperation();
+    } else if (operation == const GreaterOperation()) {
+      return const LessEqualOperation();
+    } else if (operation == const GreaterEqualOperation()) {
+      return const LessOperation();
+    } else {
+      return null;
+    }
+  }
+
+  static Range computeNewRange(BinaryOperation operation, Range range) {
+    if (operation == const LessOperation()) {
+      return new Range(const MinIntValue(), range.upper - const IntValue(1));
+    } else if (operation == const LessEqualOperation()) {
+      return new Range(const MinIntValue(), range.upper);
+    } else if (operation == const GreaterOperation()) {
+      return new Range(range.lower + const IntValue(1), const MaxIntValue());
+    } else if (operation == const GreaterEqualOperation()) {
+      return new Range(range.lower, const MaxIntValue());
+    } else {
+      return const Range.unbound();
+    }
+  }
+
   Range visitConditionalBranch(HConditionalBranch branch) {
     var condition = branch.condition;
-    // TODO(ngeoffray): Handle more condition kinds.
-    if (condition is !HLess) return const Range.unbound();
+    // TODO(ngeoffray): Handle complex conditions.
+    if (condition is !HRelational) return const Range.unbound();
+    if (condition is HEquals) return const Range.unbound();
+    if (condition is HIdentity) return const Range.unbound();
     HInstruction right = condition.right;
     HInstruction left = condition.left;
     if (!left.isInteger(types)) return const Range.unbound();
     if (!right.isInteger(types)) return const Range.unbound();
 
-    // Update the true branch to use a narrower range for [left].
-    // TODO(ngeoffray): Also do it for [right].
-    HInstruction instruction =
-        createRangeConversion(branch.trueBranch.first, left);
-    Range range = new Range(
-        const MinIntValue(), ranges[right].upper - const IntValue(1));
-    range = range.intersection(ranges[left]);
-    ranges[instruction] = range;
+    Range rightRange = ranges[right];
+    Range leftRange = ranges[left];
+    Operation operation = condition.operation(constantSystem);
+    Operation reverse = reverseOperation(operation);
+    // Update the true branch to use narrower ranges for [left] and
+    // [right].
+    Range range = computeNewRange(operation, rightRange);

[Søren Gjesse, 2012/10/02 08:07:20]

Wouldn't it be better to include the intersection in the computeNewRange and
pass both ranges to it?

[ngeoffray, 2012/10/02 16:03:09]

Not sure I understand that comment. Could you expand a bit?

[Søren Gjesse, 2012/10/02 16:26:56]

What I ment was to change

  Range range = computeNewRange(operation, rightRange);
  range = range.intersection(leftRange);

to one function like this:

  Range range = computeNewRange(operation, leftRange, rightRange);

and maybe call it something else.

[ngeoffray, 2012/10/04 08:51:08]

Done.

+    range = range.intersection(leftRange);
+    if (leftRange != range) {
+      HInstruction instruction =
+          createRangeConversion(branch.trueBranch.first, left);
+      ranges[instruction] = range;
+    }
 
-    // Update the false branch to use a narrower range for [left].
-    // TODO(ngeoffray): Also do it for [right].
-    instruction = createRangeConversion(branch.falseBranch.first, left);
-    range = new Range(ranges[right].lower, const MaxIntValue());
-    range = range.intersection(ranges[left]);
-    ranges[instruction] = range;
+    range = computeNewRange(reverse, leftRange);
+    range = range.intersection(rightRange);
+    if (rightRange != range) {
+      HInstruction instruction =
+          createRangeConversion(branch.trueBranch.first, right);
+      ranges[instruction] = range;
+    }
 
+    // Update the false branch to use narrower ranges for [left] and
+    // [right].
+    range = computeNewRange(reverse, rightRange);
+    range = range.intersection(leftRange);
+    if (leftRange != range) {
+      HInstruction instruction =
+          createRangeConversion(branch.falseBranch.first, left);
+      ranges[instruction] = range;
+    }
+
+    range = computeNewRange(operation, leftRange);
+    range = range.intersection(rightRange);
+    if (rightRange != range) {
+      HInstruction instruction =
+          createRangeConversion(branch.falseBranch.first, right);
+      ranges[instruction] = range;
+    }
+
     return const Range.unbound();
   }