Bit width analysis for avoiding conversion of bitops to unsigned.

pkg/compiler/lib/src/ssa/codegen.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.
 
+import 'dart:math' as math;
 import '../common.dart';
 import '../common/codegen.dart' show CodegenRegistry, CodegenWorkItem;
 import '../common/tasks.dart' show CompilerTask;
 import '../compiler.dart' show Compiler;
 import '../constants/constant_system.dart';
 import '../constants/values.dart';
 import '../core_types.dart' show CoreClasses;
 import '../dart_types.dart';
 import '../elements/elements.dart';
 import '../elements/entities.dart';
@@ skipping 188 matching lines @@
           phiSet.add(user);
           if (hasNonBitOpUser(user, phiSet)) return true;
         }
       } else if (user is! HBitNot && user is! HBinaryBitOp) {
         return true;
       }
     }
     return false;
   }
 
+  // Returns the number of bits occupied by the value computed by [instruction].
+  // Returns `32` if the value is negative or does not fit in a smaller number
+  // of bits.
+  int bitWidth(HInstruction instruction) {
+    const int MAX = 32;
+    int constant(HInstruction insn) {
+      if (insn is HConstant && insn.isConstantInteger()) {
+        IntConstantValue constant = insn.constant;
+        return constant.primitiveValue;
+      }
+      return null;
+    }
+
+    if (instruction.isConstantInteger()) {
+      int value = constant(instruction);
+      if (value < 0) return MAX;
+      if (value > ((1 << 31) - 1)) return MAX;
+      return value.bitLength;
+    }
+    if (instruction is HBitAnd) {
+      return math.min(bitWidth(instruction.left), bitWidth(instruction.right));
+    }
+    if (instruction is HBitOr || instruction is HBitXor) {
+      HBinaryBitOp bitOp = instruction;
+      int leftWidth = bitWidth(bitOp.left);
+      if (leftWidth == MAX) return MAX;
+      return math.max(leftWidth, bitWidth(bitOp.right));
+    }
+    if (instruction is HShiftLeft) {
+      int shiftCount = constant(instruction.right);
+      if (shiftCount == null || shiftCount < 0 || shiftCount > 31) return MAX;
+      int leftWidth = bitWidth(instruction.left);
+      int width = leftWidth + shiftCount;
+      return math.min(width, MAX);
+    }
+    if (instruction is HShiftRight) {
+      int shiftCount = constant(instruction.right);
+      if (shiftCount == null || shiftCount < 0 || shiftCount > 31) return MAX;
+      int leftWidth = bitWidth(instruction.left);
+      if (leftWidth >= MAX) return MAX;
+      return math.max(leftWidth - shiftCount, 0);
+    }
+    if (instruction is HAdd) {
+      return math.min(
+          1 + math.max(bitWidth(instruction.left), bitWidth(instruction.right)),
+          MAX);
+    }
+    return MAX;
+  }
+
   bool requiresUintConversion(instruction) {
     if (instruction.isUInt31(compiler)) return false;
+    if (bitWidth(instruction) <= 31) return false;
     // If the result of a bit-operation is only used by other bit
     // operations, we do not have to convert to an unsigned integer.
     return hasNonBitOpUser(instruction, new Set<HPhi>());
   }
 
   /**
    * If the [instruction] is not `null` it will be used to attach the position
    * to the [statement].
    */
   void pushStatement(js.Statement statement) {
@@ skipping 2819 matching lines @@
     registry.registerStaticUse(new StaticUse.staticInvoke(
         helper, new CallStructure.unnamed(argumentCount)));
     return backend.emitter.staticFunctionAccess(helper);
   }
 
   @override
   void visitRef(HRef node) {
     visit(node.value);
   }
 }