Improve precision of range analysis by allowing it to track ranges across all int typed phis.

runtime/vm/flow_graph_range_analysis.cc

 // Copyright (c) 2014, 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/flow_graph_range_analysis.h"
 
 #include "vm/bit_vector.h"
 #include "vm/il_printer.h"
 
 namespace dart {
@@ skipping 227 matching lines @@
         if (IsIntegerDefinition(current)) {
           values_.Add(current);
         }
       }
     }
 
     JoinEntryInstr* join = block->AsJoinEntry();
     if (join != NULL) {
       for (PhiIterator phi_it(join); !phi_it.Done(); phi_it.Advance()) {
         PhiInstr* current = phi_it.Current();
-        if ((current->Type()->ToCid() == kSmiCid) ||
-            (current->representation() == kUnboxedInt32)) {
+        if (current->Type()->IsInt()) {
           values_.Add(current);
         }
       }
     }
 
     for (ForwardInstructionIterator instr_it(block);
          !instr_it.Done();
          instr_it.Advance()) {
       Instruction* current = instr_it.Current();
       Definition* defn = current->AsDefinition();
@@ skipping 250 matching lines @@
     // and will have a range assigned to it.
     // Note: that we can't return NULL here because it is used as lattice's
     // bottom element to indicate that the range was not computed *yet*.
     return &smi_range_;
   }
 
   return range;
 }
 
 
+const Range* RangeAnalysis::GetIntRange(Value* value) const {
+  Definition* defn = value->definition();
+  const Range* range = defn->range();
+
+  if ((range == NULL) && !defn->Type()->IsInt()) {
+    // Type propagator determined that reaching type for this use is int.
+    // However the definition itself is not a int-definition and
+    // thus it will never have range assigned to it. Just return the widest
+    // range possible for this value.
+    // It is safe to return Int64 range as this is the widest possible range
+    // supported by our unboxing operations - if this definition produces
+    // Bigint outside of Int64 we will deoptimize whenever we actually try
+    // to unbox it.
+    // Note: that we can't return NULL here because it is used as lattice's
+    // bottom element to indicate that the range was not computed *yet*.
+    return &int64_range_;
+  }
+
+  return range;
+}
+
+
 static bool AreEqualDefinitions(Definition* a, Definition* b) {
   a = UnwrapConstraint(a);
   b = UnwrapConstraint(b);
   return (a == b) ||
       (a->AllowsCSE() &&
        a->Dependencies().IsNone() &&
        b->AllowsCSE() &&
        b->Dependencies().IsNone() &&
        a->Equals(b));
 }
@@ skipping 102 matching lines @@
   switch (op) {
     case WIDEN: return 'W';
     case NARROW: return 'N';
     case NONE: return 'I';
   }
   UNREACHABLE();
   return ' ';
 }
 
 
+static RangeBoundary::RangeSize RangeSizeForPhi(Definition* phi) {
+  ASSERT(phi->IsPhi());
+  if (phi->Type()->ToCid() == kSmiCid) {
+    return RangeBoundary::kRangeBoundarySmi;
+  } else if (phi->representation() == kUnboxedInt32) {
+    return RangeBoundary::kRangeBoundaryInt32;
+  } else if (phi->Type()->IsInt()) {
+    return RangeBoundary::kRangeBoundaryInt64;
+  } else {
+    UNREACHABLE();
+    return RangeBoundary::kRangeBoundaryInt64;
+  }
+}
+
+
 bool RangeAnalysis::InferRange(JoinOperator op,
                                Definition* defn,
                                intptr_t iteration) {
   Range range;
   defn->InferRange(this, &range);
 
   if (!Range::IsUnknown(&range)) {
     if (!Range::IsUnknown(defn->range()) && defn->IsPhi()) {
-      // TODO(vegorov): we are currently supporting only smi/int32 phis.
-      ASSERT((defn->Type()->ToCid() == kSmiCid) ||
-             (defn->representation() == kUnboxedInt32));
-      const RangeBoundary::RangeSize size = (defn->Type()->ToCid() == kSmiCid) ?
-          RangeBoundary::kRangeBoundarySmi : RangeBoundary::kRangeBoundaryInt32;
+      const RangeBoundary::RangeSize size = RangeSizeForPhi(defn);
       if (op == WIDEN) {
         range = Range(WidenMin(defn->range(), &range, size),
                       WidenMax(defn->range(), &range, size));
       } else if (op == NARROW) {
         range = Range(NarrowMin(defn->range(), &range, size),
                       NarrowMax(defn->range(), &range, size));
       }
     }
 
     if (!range.Equals(defn->range())) {
@@ skipping 83 matching lines @@
     Definition* definition = initial[i];
     if (set->Contains(definition->ssa_temp_index())) {
       definitions_.Add(definition);
     }
   }
   CollectDefinitions(set);
 
   // Perform an iteration of range inference just propagating ranges
   // through the graph as-is without applying widening or narrowing.
   // This helps to improve precision of initial bounds.
-  Iterate(NONE, 1);
+  Iterate(NONE, 2);

[Florian Schneider, 2014/11/10 16:10:47]

Maybe a comment why 2 iterations help.

 
   // Perform fix-point iteration of range inference applying widening
   // operator to phis to ensure fast convergence.
   // Widening simply maps growing bounds to the respective range bound.
   Iterate(WIDEN, kMaxInt32);
 
   if (FLAG_trace_range_analysis) {
     FlowGraphPrinter::PrintGraph("Range Analysis (WIDEN)", flow_graph_);
   }
 
@@ skipping 1816 matching lines @@
 }
 
 
 void Definition::InferRange(RangeAnalysis* analysis, Range* range) {
   if (Type()->ToCid() == kSmiCid) {
     *range = Range::Full(RangeBoundary::kRangeBoundarySmi);
   } else if (IsMintDefinition()) {
     *range = Range::Full(RangeBoundary::kRangeBoundaryInt64);
   } else if (IsInt32Definition()) {
     *range = Range::Full(RangeBoundary::kRangeBoundaryInt32);
+  } else if (Type()->IsInt()) {
+    *range = Range::Full(RangeBoundary::kRangeBoundaryInt64);
   } else {
     // Only Smi and Mint supported.
     UNREACHABLE();
   }
 }
 
 
 static bool DependsOnSymbol(const RangeBoundary& a, Definition* symbol) {
   return a.IsSymbol() && (UnwrapConstraint(a.symbol()) == symbol);
 }
@@ skipping 80 matching lines @@
   Definition* unwrapped = UnwrapConstraint(a.symbol());
   if ((unwrapped != a.symbol()) &&
       DominatesPhi(unwrapped->GetBlock(), phi_block)) {
     return RangeBoundary::FromDefinition(unwrapped, a.offset());
   }
 
   return limit;
 }
 
 
+static const Range* GetInputRange(RangeAnalysis* analysis,
+                                  RangeBoundary::RangeSize size,
+                                  Value* input) {
+  switch (size) {
+    case RangeBoundary::kRangeBoundarySmi:
+      return analysis->GetSmiRange(input);
+    case RangeBoundary::kRangeBoundaryInt32:
+      return input->definition()->range();
+    case RangeBoundary::kRangeBoundaryInt64:
+      return analysis->GetIntRange(input);
+    default:
+      UNREACHABLE();
+      return NULL;
+  }
+}
+
+
 void PhiInstr::InferRange(RangeAnalysis* analysis, Range* range) {
-  ASSERT((Type()->ToCid() == kSmiCid) || (representation() == kUnboxedInt32));
-  const RangeBoundary::RangeSize size = (Type()->ToCid() == kSmiCid) ?
-      RangeBoundary::kRangeBoundarySmi : RangeBoundary::kRangeBoundaryInt32;
+  const RangeBoundary::RangeSize size = RangeSizeForPhi(this);
   for (intptr_t i = 0; i < InputCount(); i++) {
     Value* input = InputAt(i);
-    const Range* input_range = (size == RangeBoundary::kRangeBoundarySmi) ?
-        analysis->GetSmiRange(input) : input->definition()->range();
     Join(range,
-         input->definition(), input_range, size);
+         input->definition(),
+         GetInputRange(analysis, size, input),
+         size);
   }
 
   BlockEntryInstr* phi_block = GetBlock();
   range->set_min(EnsureAcyclicSymbol(
       phi_block, range->min(), RangeBoundary::MinSmi()));
   range->set_max(EnsureAcyclicSymbol(
       phi_block, range->max(), RangeBoundary::MaxSmi()));
 }
 
 
@@ skipping 73 matching lines @@
       break;
     case kTypedDataInt16ArrayCid:
       *range = Range(RangeBoundary::FromConstant(-32768),
                      RangeBoundary::FromConstant(32767));
       break;
     case kTypedDataUint16ArrayCid:
       *range = Range(RangeBoundary::FromConstant(0),
                      RangeBoundary::FromConstant(65535));
       break;
     case kTypedDataInt32ArrayCid:
-      if (Typed32BitIsSmi()) {

[Florian Schneider, 2014/11/10 16:10:47]

Is Typed32BitIsSmi() still used anywhere?

-        *range = Range::Full(RangeBoundary::kRangeBoundarySmi);
-      } else {
-        *range = Range(RangeBoundary::FromConstant(kMinInt32),
-                       RangeBoundary::FromConstant(kMaxInt32));
-      }
+      *range = Range(RangeBoundary::FromConstant(kMinInt32),
+                     RangeBoundary::FromConstant(kMaxInt32));
       break;
     case kTypedDataUint32ArrayCid:
-      if (Typed32BitIsSmi()) {
-        *range = Range::Full(RangeBoundary::kRangeBoundarySmi);
-      } else {
-        *range = Range(RangeBoundary::FromConstant(0),
-                       RangeBoundary::FromConstant(kMaxUint32));
-      }
+      *range = Range(RangeBoundary::FromConstant(0),
+                     RangeBoundary::FromConstant(kMaxUint32));
       break;
     case kOneByteStringCid:
       *range = Range(RangeBoundary::FromConstant(0),
                      RangeBoundary::FromConstant(0xFF));
       break;
     case kTwoByteStringCid:
       *range = Range(RangeBoundary::FromConstant(0),
                      RangeBoundary::FromConstant(0xFFFF));
       break;
     default:
@@ skipping 86 matching lines @@
 
 void BoxIntegerInstr::InferRange(RangeAnalysis* analysis, Range* range) {
   const Range* value_range = value()->definition()->range();
   if (!Range::IsUnknown(value_range)) {
     *range = *value_range;
   }
 }
 
 
 void UnboxInt32Instr::InferRange(RangeAnalysis* analysis, Range* range) {
-  if (value()->definition()->Type()->ToCid() == kSmiCid) {
+  if (value()->Type()->ToCid() == kSmiCid) {
     const Range* value_range = analysis->GetSmiRange(value());
     if (!Range::IsUnknown(value_range)) {
       *range = *value_range;
     }
-  } else if (value()->definition()->IsMintDefinition() ||
-             value()->definition()->IsInt32Definition()) {
-    const Range* value_range = value()->definition()->range();
+  } else if (RangeAnalysis::IsIntegerDefinition(value()->definition())) {
+    const Range* value_range = analysis->GetIntRange(value());
     if (!Range::IsUnknown(value_range)) {
       *range = *value_range;
     }
   } else if (value()->Type()->ToCid() == kSmiCid) {
     *range = Range::Full(RangeBoundary::kRangeBoundarySmi);
   } else {
     *range = Range::Full(RangeBoundary::kRangeBoundaryInt32);
   }
 }
 
 
+void UnboxUint32Instr::InferRange(RangeAnalysis* analysis, Range* range) {
+  const Range* value_range = NULL;
+
+  if (value()->Type()->ToCid() == kSmiCid) {
+    value_range = analysis->GetSmiRange(value());
+  } else if (RangeAnalysis::IsIntegerDefinition(value()->definition())) {
+    value_range = analysis->GetIntRange(value());
+  } else {
+    *range = Range(RangeBoundary::FromConstant(0),
+                   RangeBoundary::FromConstant(kMaxUint32));
+    return;
+  }
+
+  if (!Range::IsUnknown(value_range)) {
+    if (value_range->IsPositive()) {
+      *range = *value_range;
+    } else {
+      *range = Range(RangeBoundary::FromConstant(0),
+                     RangeBoundary::FromConstant(kMaxUint32));
+    }
+  }
+}
+
+
 void UnboxInt64Instr::InferRange(RangeAnalysis* analysis, Range* range) {
   const Range* value_range = value()->definition()->range();
   if (value_range != NULL) {
     *range = *value_range;
   } else if (!value()->definition()->IsMintDefinition() &&
              (value()->definition()->Type()->ToCid() != kSmiCid)) {
     *range = Range::Full(RangeBoundary::kRangeBoundaryInt64);
   }
 }
 
@@ skipping 80 matching lines @@
     }
   } while (CanonicalizeMaxBoundary(&max) ||
            CanonicalizeMinBoundary(&canonical_length));
 
   // Failed to prove that maximum is bounded with array length.
   return false;
 }
 
 
 }  // namespace dart