Generalize bounds checks.

runtime/vm/flow_graph_range_analysis.h

 // 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.
 
 #ifndef VM_FLOW_GRAPH_RANGE_ANALYSIS_H_
 #define VM_FLOW_GRAPH_RANGE_ANALYSIS_H_
 
 #include "vm/flow_graph.h"
 #include "vm/intermediate_language.h"
 
@@ skipping 472 matching lines @@
 
 class RangeUtils : public AllStatic  {
  public:
   static bool Fits(Range* range, RangeBoundary::RangeSize size) {
     return !Range::IsUnknown(range) && range->Fits(size);
   }
 
   static bool IsWithin(Range* range, int64_t min, int64_t max) {
     return !Range::IsUnknown(range) && range->IsWithin(min, max);
   }
+
+  static bool IsPositive(Range* range) {
+    return !Range::IsUnknown(range) && range->IsPositive();
+  }
 };
 
 
 // Range analysis for integer values.
 class RangeAnalysis : public ValueObject {
  public:
   explicit RangeAnalysis(FlowGraph* flow_graph)
       : flow_graph_(flow_graph),
         smi_range_(Range::Full(RangeBoundary::kRangeBoundarySmi)) { }
 
   // Infer ranges for all values and remove overflow checks from binary smi
   // operations when proven redundant.
   void Analyze();
 
   // Helper that should be used to access ranges of inputs during range
   // inference.
   // Returns meaningful results for uses of non-smi definitions that have smi
   // as a reaching type.
   const Range* GetSmiRange(Value* value) const;
 
+  static bool IsIntegerDefinition(Definition* defn) {
+    return (defn->Type()->ToCid() == kSmiCid) ||
+        defn->IsMintDefinition() ||
+        defn->IsInt32Definition();
+  }
+
+  void AssignRangesRecursively(Definition* defn);
+
  private:
   enum JoinOperator {
     NONE,
     WIDEN,
     NARROW
   };
   static char OpPrefix(JoinOperator op);
 
   // Collect all values that were proven to be smi in smi_values_ array and all
   // CheckSmi instructions in smi_check_ array.
   void CollectValues();
 
   // Iterate over smi values and constrain them at branch successors.
   // Additionally constraint values after CheckSmi instructions.
   void InsertConstraints();
 
   // Iterate over uses of the given definition and discover branches that
   // constrain it. Insert appropriate Constraint instructions at true
   // and false successor and rename all dominated uses to refer to a
   // Constraint instead of this definition.
   void InsertConstraintsFor(Definition* defn);
 
   // Create a constraint for defn, insert it after given instruction and
   // rename all uses that are dominated by it.
   ConstraintInstr* InsertConstraintFor(Value* use,
                                        Definition* defn,
                                        Range* constraint,
                                        Instruction* after);
 
-  void ConstrainValueAfterBranch(Value* use, Definition* defn);
+  bool ConstrainValueAfterBranch(Value* use, Definition* defn);
   void ConstrainValueAfterCheckArrayBound(Value* use, Definition* defn);
 
   // Replace uses of the definition def that are dominated by instruction dom
   // with uses of other definition.
   void RenameDominatedUses(Definition* def,
                            Instruction* dom,
                            Definition* other);
 
 
   // Infer ranges for integer (smi or mint) definitions.
   void InferRanges();
 
   // Collect integer definition in the reverse postorder.
-  void CollectDefinitions(BlockEntryInstr* block, BitVector* set);
+  void CollectDefinitions(BitVector* set);
 
   // Recompute ranges of all definitions until they stop changing.
   // Apply the given JoinOperator when computing Phi ranges.
   void Iterate(JoinOperator op, intptr_t max_iterations);
   bool InferRange(JoinOperator op, Definition* defn, intptr_t iteration);
 
   // Based on computed ranges find and eliminate redundant CheckArrayBound
   // instructions.
   void EliminateRedundantBoundsChecks();
 
   // Find unsatisfiable constraints and mark corresponding blocks unreachable.
   void MarkUnreachableBlocks();
 
   // Convert mint operations that stay within int32 range into Int32 operations.
   void NarrowMintToInt32();
 
+  void DiscoverSimpleInductionVariables();
+
   // Remove artificial Constraint instructions and replace them with actual
   // unconstrained definitions.
   void RemoveConstraints();
 
   Range* ConstraintSmiRange(Token::Kind op, Definition* boundary);
 
   Isolate* isolate() const { return flow_graph_->isolate(); }
 
   FlowGraph* flow_graph_;
 
@@ skipping 47 matching lines @@
   BitVector* selected_uint32_defs_;
 
   FlowGraph* flow_graph_;
   Isolate* isolate_;
 };
 
 
 }  // namespace dart
 
 #endif  // VM_FLOW_GRAPH_RANGE_ANALYSIS_H_