Add range analysis for left-shift smi operations.

runtime/vm/intermediate_language.h

Index: runtime/vm/intermediate_language.h
===================================================================
--- runtime/vm/intermediate_language.h	(revision 37229)
+++ runtime/vm/intermediate_language.h	(working copy)
@@ -2504,6 +2504,9 @@
         value_(other.value_),
         offset_(other.offset_) { }
 
+  explicit RangeBoundary(intptr_t val)
+      : kind_(kConstant), value_(val), offset_(0) { }
+
   RangeBoundary& operator=(const RangeBoundary& other) {
     kind_ = other.kind_;
     value_ = other.value_;
@@ -2512,7 +2515,7 @@
   }
 
   static RangeBoundary FromConstant(intptr_t val) {
-    return RangeBoundary(kConstant, val, 0);
+    return RangeBoundary(val);
   }
 
   static RangeBoundary NegativeInfinity() {
@@ -2554,6 +2557,12 @@
     return *this;
   }
 
+  bool Equals(const RangeBoundary& other) {
+    return kind_ == other.kind_
+        && value_ == other.value_
+        && offset_ == other.offset_;
+  }
+
   bool IsUnknown() const { return kind_ == kUnknown; }
   bool IsConstant() const { return kind_ == kConstant; }
   bool IsSymbol() const { return kind_ == kSymbol; }
@@ -2607,6 +2616,24 @@
     return RangeBoundary::FromConstant(result);
   }
 
+  static RangeBoundary Shl(const RangeBoundary& a,

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

operand a

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

Done.

+                           intptr_t b,

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

more meaningful name: shift?

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

Done.

+                           const RangeBoundary& overflow) {
+    ASSERT(a.IsConstant());
+    ASSERT(b >= 0);
+    intptr_t limit = 63 - b;

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

I think this should be 64 (think b = 0).

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

Done.

+    if ((a.value() == 0) ||
+        ((limit > 0) &&
+         (Utils::IsInt(limit, static_cast<int64_t>(a.value()))))) {
+      // Result stays in 64 bit range.
+      int64_t result = a.value() << b;

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

this is intptr_t range shift

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

Done.

+      return Smi::IsValid(result)
+          ? RangeBoundary::FromConstant(result)
+          : overflow;
+    }
+    return overflow;
+  }
+
  private:
   RangeBoundary(Kind kind, intptr_t value, intptr_t offset)
       : kind_(kind), value_(value), offset_(offset) { }
@@ -2662,6 +2689,11 @@
 
   bool IsUnsatisfiable() const;
 
+  static void Shl(Range* left_range,
+                  Range* right_range,
+                  RangeBoundary* min,
+                  RangeBoundary* max);
+
  private:
   RangeBoundary min_;
   RangeBoundary max_;