[turbofan] increased precision of range types for bitshifts

src/compiler/operation-typer.cc

 // Copyright 2016 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/compiler/operation-typer.h"
 
 #include "src/compiler/common-operator.h"
 #include "src/compiler/type-cache.h"
 #include "src/compiler/types.h"
 #include "src/factory.h"
@@ skipping 775 matching lines @@
     // TODO(jarin) Use a range here.
     return Type::Negative32();
   }
   return Type::Signed32();
 }
 
 Type* OperationTyper::NumberShiftLeft(Type* lhs, Type* rhs) {
   DCHECK(lhs->Is(Type::Number()));
   DCHECK(rhs->Is(Type::Number()));
 
-  // TODO(turbofan): Infer a better type here.
-  return Type::Signed32();
+  if (!lhs->IsInhabited() || !rhs->IsInhabited()) return Type::None();
+
+  lhs = NumberToInt32(lhs);
+  rhs = NumberToUint32(rhs);
+
+  int32_t minLhs = lhs->Min();

[Jarin, 2016/11/21 10:34:59]

Style nit: minLhs -> min_lhs.

+  int32_t maxLhs = lhs->Max();
+  uint32_t maxRhs = rhs->Max();
+  uint32_t minRhs = rhs->Min();
+  if (maxRhs > 31) {
+    // rhs can be larger than the bitmask
+    maxRhs = 31;
+    minRhs = 0;
+  }
+
+  if (maxLhs > (kMaxInt >> maxRhs) || minLhs < (kMinInt >> maxRhs)) {
+    // overflow possible
+    return Type::Signed32();
+  }
+
+  double min =
+      std::min(static_cast<int32_t>(static_cast<uint32_t>(minLhs) << minRhs),
+               static_cast<int32_t>(static_cast<uint32_t>(minLhs) << maxRhs));
+  double max =
+      std::max(static_cast<int32_t>(static_cast<uint32_t>(maxLhs) << minRhs),
+               static_cast<int32_t>(static_cast<uint32_t>(maxLhs) << maxRhs));
+
+  if (max == kMaxInt && min == kMinInt) return Type::Signed32();
+  return Type::Range(min, max, zone());
 }
 
 Type* OperationTyper::NumberShiftRight(Type* lhs, Type* rhs) {
   DCHECK(lhs->Is(Type::Number()));
   DCHECK(rhs->Is(Type::Number()));
 
   if (!lhs->IsInhabited() || !rhs->IsInhabited()) return Type::None();
 
   lhs = NumberToInt32(lhs);
   rhs = NumberToUint32(rhs);
 
-  double min = kMinInt;
-  double max = kMaxInt;
-  if (lhs->Min() >= 0) {
-    // Right-shifting a non-negative value cannot make it negative, nor larger.
-    min = std::max(min, 0.0);
-    max = std::min(max, lhs->Max());
-    if (rhs->Min() > 0 && rhs->Max() <= 31) {
-      max = static_cast<int>(max) >> static_cast<int>(rhs->Min());
-    }
+  int32_t minLhs = lhs->Min();
+  int32_t maxLhs = lhs->Max();
+  uint32_t maxRhs = rhs->Max();
+  uint32_t minRhs = rhs->Min();
+  if (maxRhs > 31) {
+    // rhs can be larger than the bitmask
+    maxRhs = 31;
+    minRhs = 0;
   }
-  if (lhs->Max() < 0) {
-    // Right-shifting a negative value cannot make it non-negative, nor smaller.
-    min = std::max(min, lhs->Min());
-    max = std::min(max, -1.0);
-    if (rhs->Min() > 0 && rhs->Max() <= 31) {
-      min = static_cast<int>(min) >> static_cast<int>(rhs->Min());
-    }
-  }
-  if (rhs->Min() > 0 && rhs->Max() <= 31) {
-    // Right-shifting by a positive value yields a small integer value.
-    double shift_min = kMinInt >> static_cast<int>(rhs->Min());
-    double shift_max = kMaxInt >> static_cast<int>(rhs->Min());
-    min = std::max(min, shift_min);
-    max = std::min(max, shift_max);
-  }
-  // TODO(jarin) Ideally, the following micro-optimization should be performed
-  // by the type constructor.
+  double min = std::min(minLhs >> minRhs, minLhs >> maxRhs);
+  double max = std::max(maxLhs >> minRhs, maxLhs >> maxRhs);
+
   if (max == kMaxInt && min == kMinInt) return Type::Signed32();
   return Type::Range(min, max, zone());
 }
 
 Type* OperationTyper::NumberShiftRightLogical(Type* lhs, Type* rhs) {
   DCHECK(lhs->Is(Type::Number()));
   DCHECK(rhs->Is(Type::Number()));
 
   if (!lhs->IsInhabited()) return Type::None();
 
@@ skipping 123 matching lines @@
   return singleton_true();
 }
 
 Type* OperationTyper::TypeTypeGuard(const Operator* sigma_op, Type* input) {
   return Type::Intersect(input, TypeGuardTypeOf(sigma_op), zone());
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8