dart2js cps: Add more constraint rules to bounds-check elimination.

pkg/compiler/lib/src/cps_ir/bounds_checker.dart

 // Copyright (c) 2015, 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.
 
 library dart2js.cps_ir.bounds_checker;
 
 import 'cps_ir_nodes.dart';
 import 'optimizers.dart' show Pass;
 import 'octagon.dart';
 import '../constants/values.dart';
@@ skipping 150 matching lines @@
   void makeGreaterThanOrEqual(SignedVariable v1, SignedVariable v2) {
     // v1 >= v2   <==>   v2 - v1 <= 0
     applyConstraint(v2, v1.negated, 0);
   }
 
   void makeGreaterThan(SignedVariable v1, SignedVariable v2) {
     // v1 > v2   <==>    v2 - v1 <= -1
     applyConstraint(v2, v1.negated, -1);
   }
 
+  void makeLessThanOrEqualToConstant(SignedVariable v1, int k) {
+    // v1 + v1 <= 2k
+    applyConstraint(v1, v1, 2 * k);
+  }
+
+  void makeGreaterThanOrEqualToConstant(SignedVariable v1, int k) {
+    // -v1 - v1 <= -2k
+    applyConstraint(v1.negated, v1.negated, -2 * k);
+  }
+
   void makeConstant(SignedVariable v1, int k) {
     // We model this using the constraints:
     //    v1 + v1 <=  2k
     //   -v1 - v1 <= -2k
     applyConstraint(v1, v1, 2 * k);
     applyConstraint(v1.negated, v1.negated, -2 * k);
   }
 
   /// Make `v1 = v2 + k`.
   void makeExactSum(SignedVariable v1, SignedVariable v2, int k) {
@@ skipping 141 matching lines @@
     // TODO(asgerf): It might be faster to inline the constant in the
     //               constraints that reference it.
     if (node.value.isInt) {
       IntConstantValue constant = node.value;
       makeConstant(getValue(node), constant.primitiveValue);
     }
   }
 
   @override
   void visitApplyBuiltinOperator(ApplyBuiltinOperator node) {
-    if (node.operator != BuiltinOperator.NumAdd &&
-        node.operator != BuiltinOperator.NumSubtract) {
-      return;
-    }
-    if (!isInt(node.arguments[0].definition) ||
-        !isInt(node.arguments[1].definition)) {
-      return;
-    }
-    if (!isInt(node)) {
-      // TODO(asgerf): The result of this operation should always be an integer,
-      // but currently type propagation does not always prove this.
-      return;
-    }
-    // We have `v1 = v2 +/- v3`, but the octagon cannot represent constraints
-    // involving more than two variables. Check if one operand is a constant.
-    int getConstantArgument(int n) {
-      Primitive prim = node.arguments[n].definition;
-      if (prim is Constant && prim.value.isInt) {
-        IntConstantValue constant = prim.value;
-        return constant.primitiveValue;
-      }
-      return null;
-    }
-    int constant = getConstantArgument(0);
-    int operandIndex = 1;
-    if (constant == null) {
-      constant = getConstantArgument(1);
-      operandIndex = 0;
-    }
-    if (constant == null) {
-      // Neither argument was a constant.
-      // Classical octagon-based analyzers would compute upper and lower bounds
-      // for the two operands and add constraints for the result based on
-      // those.  For performance reasons we omit that.
-      // TODO(asgerf): It seems expensive, but we should evaluate it.
-      return;
-    }
-    SignedVariable v1 = getValue(node);
-    SignedVariable v2 = getValue(node.arguments[operandIndex].definition);
-
-    if (node.operator == BuiltinOperator.NumAdd) {
-      // v1 = v2 + const
-      makeFloatingPointSum(v1, v2, constant);
-    } else if (operandIndex == 0) {
-      // v1 = v2 - const
-      makeFloatingPointSum(v1, v2, -constant);
-    } else {
-      // v1 = const - v2   <==>   v1 = (-v2) + const
-      makeFloatingPointSum(v1, v2.negated, constant);
+    if (!isInt(node)) return;
+    if (node.arguments.length == 1) {
+      applyUnaryOperator(node);
+    } else if (node.arguments.length == 2) {
+      applyBinaryOperator(node);
     }
   }
 
+  void applyBinaryOperator(ApplyBuiltinOperator node) {
+    Primitive left = node.arguments[0].definition;
+    Primitive right = node.arguments[1].definition;
+    if (!isInt(left) || !isInt(right)) {
+      return;
+    }
+    SignedVariable leftVar = getValue(left);
+    SignedVariable rightVar = getValue(right);
+    SignedVariable result = getValue(node);
+    switch (node.operator) {
+      case BuiltinOperator.NumAdd:
+        int leftConst = getIntConstant(left);
+        if (leftConst != null) {
+          makeFloatingPointSum(result, rightVar, leftConst);
+        }
+        int rightConst = getIntConstant(right);
+        if (rightConst != null) {
+          makeFloatingPointSum(result, leftVar, rightConst);
+        }
+        // Attempt to compute the sign of the result.
+        // TODO(asgerf): Compute upper/lower bounds instead of using 0.
+        if (testConstraint(leftVar, rightVar, 0)) {
+          makeLessThanOrEqualToConstant(result, 0);
+        }
+        if (testConstraint(leftVar.negated, rightVar.negated, 0)) {
+          makeGreaterThanOrEqualToConstant(result, 0);
+        }
+        // Classical octagon-based analyzers would compute upper and lower
+        // bounds for the two operands and add constraints for the result based
+        // on those.  For performance reasons we only compute the sign
+        // TODO(asgerf): It seems expensive, but we should evaluate it.
+        break;
+
+      case BuiltinOperator.NumSubtract:
+        int leftConst = getIntConstant(left);
+        if (leftConst != null) {
+          // result = leftConst - right = (-right) + leftConst
+          makeFloatingPointSum(result, rightVar.negated, leftConst);
+        }
+        int rightConst = getIntConstant(right);
+        if (rightConst != null) {
+          // result = left - rightConst = left + (-rightConst)
+          makeFloatingPointSum(result, leftVar, -rightConst);
+        }
+        // Attempt to compute the sign of the result.
+        if (isDefinitelyGreaterThanOrEqualTo(leftVar, rightVar)) {
+          makeGreaterThanOrEqualToConstant(result, 0);
+        }
+        if (isDefinitelyLessThanOrEqualTo(leftVar, rightVar)) {
+          makeLessThanOrEqualToConstant(result, 0);
+        }
+        break;
+
+      case BuiltinOperator.NumTruncatingDivideToSigned32:
+        if (isDefinitelyGreaterThanOrEqualToConstant(leftVar, 0)) {
+          // If we divide by a positive number, the result is closer to zero.
+          // If we divide by a negative number, the result is negative, and
+          // thus less than the original (non-negative) number.
+          // TODO(asgerf): The divisor is currently always positive, because
+          // type propagation checks that, but we could do better.
+          makeLessThanOrEqual(result, leftVar);
+        }
+        break;
+
+      case BuiltinOperator.NumShr:
+        if (isDefinitelyGreaterThanOrEqualToConstant(leftVar, 0)) {
+          makeLessThanOrEqual(result, leftVar);
+        }

[sra1, 2015/11/27 20:28:21]

Also:  x >> k  <=  MAX_UINT32 >> k

Base64(De|En)coder contains  s.codeUnitAt(... >> 18)
which is in bounds since s.length == 64.

[asgerf, 2015/11/30 13:46:03]

Done.

+        break;
+
+      case BuiltinOperator.NumRemainder:
+        // TODO(asgerf): This check overlaps with checks performed in a type
+        //   propagation transformation, and we can do it more precisely here.
+        //   Should we do the rewrite here?

[sra1, 2015/11/27 20:28:21]

We would want to do the check on InvokeMethod to see if we can rewrite to  a
builtin.

[asgerf, 2015/11/30 13:46:03]

My point was we could consider doing the rewriting in this pass.

+        if (isDefinitelyGreaterThanOrEqualToConstant(leftVar, 0) &&

[sra1, 2015/11/27 20:28:21]

We do this test a lot. How many steps does it take?
If we stored min/max on some of the variables, that would be a fast cache of the
information already derived from the type or constant value.

[asgerf, 2015/11/30 13:46:03]

The bounds checker is a bit wasteful like this, but so far when I have tried to
remove the redundant checks I cannot measure the difference afterwards. There
are just not enough of these operators for this to have a measurable impact on
the benchmark suite.

But we can do better.  I'll do some more rigorous performance testing and get
back to you.

[asgerf, 2015/12/01 16:19:35]

I made unary checks a bit faster with a special case in the octagon domain.
Caching the min/max or just checking for uint32 directly didn't seem to have
much impact, though.

+            isDefinitelyGreaterThanOrEqualToConstant(rightVar, 1)) {
+          makeLessThanOrEqual(result, leftVar);
+          makeLessThan(result, rightVar);
+        }
+        break;
+
+      case BuiltinOperator.NumAnd:
+        // We use the faster UInt32 check instead of constraint based checks
+        // here, because the common case is that one operand is a constant.
+        if (isUInt32(left)) {
+          makeLessThanOrEqual(result, leftVar);
+        }
+        if (isUInt32(right)) {
+          makeLessThanOrEqual(result, rightVar);
+        }
+        break;
+
+      default:
+    }
+  }
+
+  void applyUnaryOperator(ApplyBuiltinOperator node) {
+    Primitive argument = node.arguments[0].definition;
+    if (!isInt(argument)) return;
+    if (node.operator == BuiltinOperator.NumNegate) {
+      valueOf[node] = getValue(argument).negated;
+    }

[sra1, 2015/11/27 20:28:21]

~x  == MAX_UINT32 - x,  if x is uint32.

Not sure we will learn anything useful.

[asgerf, 2015/11/30 13:46:03]

Seems really unlikely to make a difference.

Connecting variables comes at a cost since it might connect two otherwise
disconnected sets of variables, making graph searches slower.

+  }
+
+  int getIntConstant(Primitive prim) {
+    if (prim is Constant && prim.value.isInt) {
+      IntConstantValue constant = prim.value;
+      return constant.primitiveValue;
+    }
+    return null;
+  }
+
   @override
   void visitGetLength(GetLength node) {
     valueOf[node] = getLength(node.object.definition, currentEffectNumber);
   }
 
   void analyzeLoopEntry(InvokeContinuation node) {
     foundLoop = true;
     Continuation cont = node.continuation.definition;
     if (isStrongLoopPass) {
       for (int i = 0; i < node.arguments.length; ++i) {
@@ skipping 195 matching lines @@
     }
     return node.body;
   }
 }
 
 /// Lattice representing the known (weak) monotonicity of a loop variable.
 ///
 /// The lattice bottom is represented by `null` and represents the case where
 /// the loop variable never changes value during the loop.
 enum Monotonicity { NotMonotone, Increasing, Decreasing, }