Add range analysis for left-shift smi operations.

runtime/vm/intermediate_language.cc

 // Copyright (c) 2013, 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.
 
 #include "vm/intermediate_language.h"
 
 #include "vm/bigint_operations.h"
 #include "vm/bit_vector.h"
 #include "vm/cpu.h"
 #include "vm/dart_entry.h"
@@ skipping 3094 matching lines @@
               OnlyNegativeOrZero(left_range, right_range) ? 0 : result_max;
           max = RangeBoundary::FromConstant(r_max);
           break;
         }
       }
       if (range_ == NULL) {
         range_ = Range::Unknown();
       }
       return;
     }
+    case Token::kSHL: {
+      Range::Shl(left_range, right_range, &min, &max);
+      break;
+    }
     case Token::kBIT_AND:
       if (Range::ConstantMin(right_range).value() >= 0) {
         min = RangeBoundary::FromConstant(0);
         max = Range::ConstantMax(right_range);
         break;
       }
       if (Range::ConstantMin(left_range).value() >= 0) {
         min = RangeBoundary::FromConstant(0);
         max = Range::ConstantMax(left_range);
         break;
@@ skipping 104 matching lines @@
     return true;
   }
   // Symbol case: For example [v+1, v].
   if (DependOnSameSymbol(min(), max()) && min().offset() > max().offset()) {
     return true;
   }
   return false;
 }
 
 
+void Range::Shl(Range* left,
+                Range* right,
+                RangeBoundary* result_min,
+                RangeBoundary* result_max) {
+  RangeBoundary left_max = Range::ConstantMax(left);
+  RangeBoundary left_min = Range::ConstantMin(left);
+  // Ignore negative values of shift count because shift by a negative shift
+  // count does give a result.
+  intptr_t right_max = Range::ConstantMax(right).value() > 0

[Vyacheslav Egorov (Google), 2014/06/12 14:59:00]

Can be written as Max(Range::ConstantMax(right).value(), 0)

[Florian Schneider, 2014/06/12 15:12:42]

Done.

+      ? Range::ConstantMax(right).value() : 0;
+  intptr_t right_min = Range::ConstantMin(right).value() > 0

[Vyacheslav Egorov (Google), 2014/06/12 14:59:00]

ditto

[Florian Schneider, 2014/06/12 15:12:42]

Done.

+      ? Range::ConstantMin(right).value() : 0;
+
+  *result_min = RangeBoundary::Shl(
+      left_min,
+      left_min.value() > 0 ? right_min : right_max,
+      left_min.value() > 0
+          ? RangeBoundary::PositiveInfinity()
+          : RangeBoundary::NegativeInfinity());
+
+  *result_max = RangeBoundary::Shl(
+      left_max,
+      left_max.value() > 0 ? right_max : right_min,
+      left_max.value() > 0
+          ? RangeBoundary::PositiveInfinity()
+          : RangeBoundary::NegativeInfinity());
+}
+
+
 bool CheckArrayBoundInstr::IsFixedLengthArrayType(intptr_t cid) {
   return LoadFieldInstr::IsFixedLengthArrayCid(cid);
 }
 
 
 bool CheckArrayBoundInstr::IsRedundant(RangeBoundary length) {
   Range* index_range = index()->definition()->range();
 
   // Range of the index is unknown can't decide if the check is redundant.
   if (index_range == NULL) {
@@ skipping 312 matching lines @@
     case Token::kTRUNCDIV: return 0;
     case Token::kMOD: return 1;
     default: UNIMPLEMENTED(); return -1;
   }
 }
 
 
 #undef __
 
 }  // namespace dart