Further bitop optimizations

lib/src/compiler/code_generator.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.
 
 import 'dart:collection' show HashMap, HashSet;
 import 'dart:math' show min, max;
 
 import 'package:analyzer/analyzer.dart' hide ConstantEvaluator;
 import 'package:analyzer/dart/ast/ast.dart';
 import 'package:analyzer/dart/ast/token.dart' show Token, TokenType;
@@ skipping 3328 matching lines @@
           return bitwise('# ^ #');
 
         case TokenType.GT_GT:
           int shiftCount = _asIntInRange(right, 0, 31);
           if (_is31BitUnsigned(left) && shiftCount != null) {
             return binary('# >> #');
           }
           if (_isDefinitelyNonNegative(left) && shiftCount != null) {
             return binary('# >>> #');
           }
-          // TODO(sra): If the context selects out only bits that can't be
-          // affected by the sign position we can use any JavaScript shift.
-          // E.g. `(x >> 6) & 3`.
+          // If the context selects out only bits that can't be affected by the
+          // sign position we can use any JavaScript shift, `(x >> 6) & 3`.
+          if (shiftCount != null &&
+              _parentMasksToWidth(node, 31 - shiftCount)) {
+            return binary('# >> #');
+          }
           return _emitSend(left, op.lexeme, [right]);
 
         case TokenType.LT_LT:
           if (_is31BitUnsigned(node)) {
             // Result is 31 bit unsigned which implies the shift count was small
             // enough not to pollute the sign bit.
             return binary('# << #');
           }
           if (_asIntInRange(right, 0, 31) != null) {
             return _coerceBitOperationResultToUnsigned(node, binary('# << #'));
           }
           return _emitSend(left, op.lexeme, [right]);
 
         default:
           // TODO(vsm): When do Dart ops not map to JS?
           return binary('# $op #');
       }
     }
 
     return _emitSend(left, op.lexeme, [right]);
   }
 
   /// Bit operations are coerced to values on [0, 2^32). The coercion changes
   /// the interpretation of the 32-bit value from signed to unsigned.  Most
   /// JavaScript operations interpret their operands as signed and generate
   /// signed results.
   JS.Expression _coerceBitOperationResultToUnsigned(
-      Expression node, JS.Expression operation) {
+      Expression node, JS.Expression uncoerced) {
     // Don't coerce if the parent will coerce.
     AstNode parent = _parentOperation(node);
-    if (_nodeIsBitwiseOperation(parent)) return operation;
+    if (_nodeIsBitwiseOperation(parent)) return uncoerced;
 
     // Don't do a no-op coerce if the most significant bit is zero.
-    if (_is31BitUnsigned(node)) return operation;
+    if (_is31BitUnsigned(node)) return uncoerced;
 
-    // TODO(sra): If the consumer of the expression is '==' or '!=' to a
-    // constant that fits in 31 bits, adding a coercion does not change the
-    // result of the comparision, e.g.  `a & ~b == 0`.
-    return js.call('# >>> 0', operation);
+    // If the consumer of the expression is '==' or '!=' with a constant that
+    // fits in 31 bits, adding a coercion does not change the result of the
+    // comparision, e.g.  `a & ~b == 0`.
+    if (parent is BinaryExpression) {
+      var tokenType = parent.operator.type;
+      Expression left = parent.leftOperand;
+      Expression right = parent.rightOperand;
+      if (tokenType == TokenType.EQ_EQ || tokenType == TokenType.BANG_EQ) {
+        const int MAX = 0x7fffffff;
+        if (_asIntInRange(right, 0, MAX) != null) return uncoerced;
+        if (_asIntInRange(left, 0, MAX) != null) return uncoerced;
+      } else if (tokenType == TokenType.GT_GT) {
+        if (_isDefinitelyNonNegative(left) &&
+            _asIntInRange(right, 0, 31) != null) {
+          // Parent will generate `# >>> n`.
+          return uncoerced;
+        }
+      }
+    }
+    return js.call('# >>> 0', uncoerced);
   }
 
   AstNode _parentOperation(AstNode node) {
     node = node.parent;
     while (node is ParenthesizedExpression) node = node.parent;
     return node;
   }
 
   bool _nodeIsBitwiseOperation(AstNode node) {
     if (node is BinaryExpression) {
       switch (node.operator.type) {
         case TokenType.AMPERSAND:
         case TokenType.BAR:
         case TokenType.CARET:
           return true;
       }
       return false;
     }
     if (node is PrefixExpression) {
       return node.operator.type == TokenType.TILDE;
     }
     return false;
   }
 
-  Expression _skipParentheses(Expression expr) {
-    while (expr is ParenthesizedExpression) {
-      ParenthesizedExpression parenExpr = expr;
-      expr = parenExpr.expression;
-    }
-    return expr;
-  }
-
   int _asIntInRange(Expression expr, int low, int high) {
-    expr = _skipParentheses(expr);
+    expr = expr.unParenthesized;
     if (expr is IntegerLiteral) {
       if (expr.value >= low && expr.value <= high) return expr.value;
+      return null;
+    }
+    int finishIdentifier(SimpleIdentifier identifier) {
+      Element staticElement = identifier.staticElement;
+      if (staticElement is PropertyAccessorElement && staticElement.isGetter) {
+        PropertyInducingElement variable = staticElement.variable;
+        int value = variable?.constantValue?.toIntValue();
+        if (value != null && value >= low && value <= high) return value;
+      }
+      return null;
+    }
+    if (expr is SimpleIdentifier) {
+      return finishIdentifier(expr);
+    } else if (expr is PrefixedIdentifier && !expr.isDeferred) {
+      return finishIdentifier(expr.identifier);
     }
     return null;
   }
 
   bool _isDefinitelyNonNegative(Expression expr) {
-    expr = _skipParentheses(expr);
+    expr = expr.unParenthesized;
     if (expr is IntegerLiteral) {
       return expr.value >= 0;
     }
     if (_nodeIsBitwiseOperation(expr)) return true;
     // TODO(sra): Lengths of known list types etc.
     return false;
   }
 
+  /// Does the parent of [node] mask the result to [width] bits or fewer?
+  bool _parentMasksToWidth(AstNode node, int width) {
+    AstNode parent = _parentOperation(node);
+    if (parent == null) return false;
+    if (_nodeIsBitwiseOperation(parent)) {
+      if (parent is BinaryExpression &&
+          parent.operator.type == TokenType.AMPERSAND) {
+        Expression left = parent.leftOperand;
+        Expression right = parent.rightOperand;
+        final int MAX = (1 << width) - 1;
+        if (_asIntInRange(right, 0, MAX) != null) return true;
+        if (_asIntInRange(left, 0, MAX) != null) return true;
+      }
+      return _parentMasksToWidth(parent, width);
+    }
+    return false;
+  }
+
   /// Determines if the result of evaluating [expr] will be an non-negative
   /// value that fits in 31 bits.
   bool _is31BitUnsigned(Expression expr) {
     const int MAX = 32; // Includes larger and negative values.
     /// Determines how many bits are required to hold result of evaluation
     /// [expr].  [depth] is used to bound exploration of huge expressions.
     int bitWidth(Expression expr, int depth) {
       if (expr is IntegerLiteral) {
         return expr.value >= 0 ? expr.value.bitLength : MAX;
       }
       if (++depth > 5) return MAX;
       if (expr is BinaryExpression) {
-        var left = _skipParentheses(expr.leftOperand);
-        var right = _skipParentheses(expr.rightOperand);
+        var left = expr.leftOperand.unParenthesized;
+        var right = expr.rightOperand.unParenthesized;
         switch (expr.operator.type) {
           case TokenType.AMPERSAND:
             return min(bitWidth(left, depth), bitWidth(right, depth));
 
           case TokenType.BAR:
           case TokenType.CARET:
             return max(bitWidth(left, depth), bitWidth(right, depth));
 
           case TokenType.GT_GT:
             int shiftValue = _asIntInRange(right, 0, 31);
@@ skipping 13 matching lines @@
             if (rightWidth <= 5) {
               // e.g.  `1 << (x & 7)` has a rightWidth of 3, so shifts by up to
               // (1 << 3) - 1 == 7 bits.
               return min(MAX, leftWidth + ((1 << rightWidth) - 1));
             }
             return MAX;
           default:
             return MAX;
         }
       }
+      int value = _asIntInRange(expr, 0, 0x7fffffff);
+      if (value != null) return value.bitLength;
       return MAX;
     }
     return bitWidth(expr, 0) < 32;
   }
 
   /// If the type [t] is [int] or [double], or a type parameter
   /// bounded by [int], [double] or [num] returns [num].
   /// Otherwise returns [t].
   DartType _canonicalizeNumTypes(DartType t) {
     var numType = types.numType;
@@ skipping 1232 matching lines @@
 }
 
 bool isLibraryPrefix(Expression node) =>
     node is SimpleIdentifier && node.staticElement is PrefixElement;
 
 LibraryElement _getLibrary(AnalysisContext c, String uri) =>
     c.computeLibraryElement(c.sourceFactory.forUri(uri));
 
 bool _isDartRuntime(LibraryElement l) =>
     l.isInSdk && l.source.uri.toString() == 'dart:_runtime';