Deal with more conditional expressions in the value range analyzer.

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 {
@@ skipping 280 matching lines @@
 
   Range operator &(Range other) {
     return new Range.normalize(lower & other.lower, upper & other.upper);
   }
 
   bool operator ==(other) {
     if (other is! Range) return false;
     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();
 
   String toString() => '[$lower, $upper]';
 }
 
 /**
  * Visits the graph in dominator order, and computes value ranges for
  * integer instructions. While visiting the graph, this phase also
  * removes unnecessary bounds checks, and comparisons that are proven
@@ skipping 113 matching lines @@
         && indexRange.upper.min(maxIndex) == indexRange.upper;
 
     // Check if the index is strictly below the lower bound of the length
     // range.
     belowLength = belowLength
         || (indexRange.upper != lengthRange.lower
             && indexRange.upper.min(lengthRange.lower) == indexRange.upper);
     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.
       return indexRange;
     } else if (indexRange.isPositive()) {
       check.staticChecks = HBoundsCheck.ALWAYS_ABOVE_ZERO;
     } else if (belowLength) {
       check.staticChecks = HBoundsCheck.ALWAYS_BELOW_LENGTH;
     }
 
@@ skipping 15 matching lines @@
           new Range(lengthRange.lower, maxIndex));
       if (indexRange == newIndexRange) return indexRange;
       HInstruction instruction = createRangeConversion(next, check.index);
       ranges[instruction] = newIndexRange;
       return newIndexRange;
     }
 
     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();
-    }
-    if (ranges[right].isLessThan(ranges[left])) {
-      less.block.rewrite(less, graph.addConstantBool(false, 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);
     }
     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(
         ranges[instruction.left], ranges[instruction.right]);
   }
 
   Range visitAdd(HAdd add) {
     return handleBinaryOperation(add);
   }
 
@@ skipping 41 matching lines @@
     cursor.block.addBefore(cursor, newInstruction);
     // Update the users of the instruction dominated by [cursor] to
     // use the new instruction, that has an narrower range.
     Set<HInstruction> dominatedUsers = instruction.dominatedUsers(cursor);
     for (HInstruction user in dominatedUsers) {
       user.changeUse(instruction, newInstruction);
     }
     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();
   }
 
   Range visitRangeConversion(HRangeConversion conversion) {
     return ranges[conversion];
   }
 }
 
 /**
@@ skipping 92 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;
   }
 }