Add range analysis for left-shift smi operations.

runtime/vm/intermediate_language.h

 // 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.
 
 #ifndef VM_INTERMEDIATE_LANGUAGE_H_
 #define VM_INTERMEDIATE_LANGUAGE_H_
 
 #include "vm/allocation.h"
 #include "vm/ast.h"
 #include "vm/growable_array.h"
@@ skipping 2486 matching lines @@
   };
 
   RangeBoundary() : kind_(kUnknown), value_(0), offset_(0) { }
 
   RangeBoundary(const RangeBoundary& other)
       : ValueObject(),
         kind_(other.kind_),
         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_;
     offset_ = other.offset_;
     return *this;
   }
 
   static RangeBoundary FromConstant(intptr_t val) {
-    return RangeBoundary(kConstant, val, 0);
+    return RangeBoundary(val);
   }
 
   static RangeBoundary NegativeInfinity() {
     return RangeBoundary(kNegativeInfinity, 0, 0);
   }
 
   static RangeBoundary PositiveInfinity() {
     return RangeBoundary(kPositiveInfinity, 0, 0);
   }
 
@@ skipping 21 matching lines @@
       return MinSmi();
     } else if (IsPositiveInfinity()) {
       return MaxSmi();
     } else if (IsConstant()) {
       if (value() < Smi::kMinValue) return MinSmi();
       if (value() > Smi::kMaxValue) return MaxSmi();
     }
     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; }
   bool IsNegativeInfinity() const { return kind_ == kNegativeInfinity; }
   bool IsPositiveInfinity() const { return kind_ == kPositiveInfinity; }
   bool IsInfinity() const {
     return IsNegativeInfinity() || IsPositiveInfinity();
   }
 
   intptr_t value() const {
@@ skipping 33 matching lines @@
                            const RangeBoundary& overflow) {
     ASSERT(a.IsConstant() && b.IsConstant());
 
     intptr_t result = a.value() - b.value();
     if (!Smi::IsValid(result)) {
       return overflow;
     }
     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) { }
 
   Kind kind_;
   intptr_t value_;
   intptr_t offset_;
 };
 
 
@@ skipping 35 matching lines @@
   bool OnlyLessThanOrEqualTo(intptr_t val) const;
 
   // Inclusive.
   bool IsWithin(intptr_t min_int, intptr_t max_int) const;
 
   // Inclusive.
   bool Overlaps(intptr_t min_int, intptr_t max_int) const;
 
   bool IsUnsatisfiable() const;
 
+  static void Shl(Range* left_range,
+                  Range* right_range,
+                  RangeBoundary* min,
+                  RangeBoundary* max);
+
  private:
   RangeBoundary min_;
   RangeBoundary max_;
 };
 
 
 class ConstraintInstr : public TemplateDefinition<2> {
  public:
   ConstraintInstr(Value* value, Range* constraint)
       : constraint_(constraint),
@@ skipping 5331 matching lines @@
   ForwardInstructionIterator* current_iterator_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_