Allow bound check elimination to eliminate checks when both array length and index boundaries are e…

runtime/vm/flow_graph_optimizer.cc

Index: runtime/vm/flow_graph_optimizer.cc
diff --git a/runtime/vm/flow_graph_optimizer.cc b/runtime/vm/flow_graph_optimizer.cc
index 4cc354dd7417325680747bd0db2094f694d98505..3a8d87b7d915ed22f2aba7fc9c266ef7bd3a7799 100644
--- a/runtime/vm/flow_graph_optimizer.cc
+++ b/runtime/vm/flow_graph_optimizer.cc
@@ -1617,6 +1617,13 @@ class RangeAnalysis : public ValueObject {
                                        Range* constraint,
                                        Instruction* after);
 
+  void ConstrainValueAfterBranch(Definition* defn, Value* use);
+  void ConstrainValueAfterCheckArrayBound(Definition* defn,
+                                          CheckArrayBoundInstr* check);
+  Definition* LoadArrayLength(CheckArrayBoundInstr* check);
+
+
+
   // Replace uses of the definition def that are dominated by instruction dom
   // with uses of other definition.
   void RenameDominatedUses(Definition* def,
@@ -1675,6 +1682,42 @@ class RangeAnalysis : public ValueObject {
   GrowableArray<Definition*> worklist_;
   BitVector* marked_defns_;
 
+  class ArrayLengthData : public ValueObject {
+   public:
+    ArrayLengthData(Definition* array, Definition* array_length)
+        : array_(array), array_length_(array_length) { }
+
+    Definition* array() const { return array_; }
+    Definition* array_length() const { return array_length_; }
+
+    typedef Definition* Value;
+    typedef Definition* Key;
+    typedef class ArrayLengthData Pair;
+
+    // KeyValueTrait members.
+    static Key KeyOf(const ArrayLengthData& data) {
+      return data.array();
+    }
+
+    static Value ValueOf(const ArrayLengthData& data) {
+      return data.array_length();
+    }
+
+    static inline intptr_t Hashcode(Key key) {
+      return reinterpret_cast<intptr_t>(key);
+    }
+
+    static inline intptr_t IsKeyEqual(const ArrayLengthData& kv, Key key) {

[Florian Schneider, 2012/10/30 15:31:39]

bool IsKeyEqual?

[Vyacheslav Egorov (Google), 2012/10/30 16:22:35]

Done.

+      return kv.array() == key;
+    }
+
+   private:
+    Definition* array_;
+    Definition* array_length_;
+  };
+
+  DirectChainedHashMap<ArrayLengthData> array_lengths_;
+
   DISALLOW_COPY_AND_ASSIGN(RangeAnalysis);
 };
 
@@ -1863,53 +1906,111 @@ ConstraintInstr* RangeAnalysis::InsertConstraintFor(Definition* defn,
 }
 
 
+void RangeAnalysis::ConstrainValueAfterBranch(Definition* defn, Value* use) {
+  BranchInstr* branch = use->instruction()->AsBranch();
+  RelationalOpInstr* rel_op = branch->comparison()->AsRelationalOp();
+  if ((rel_op != NULL) && (rel_op->operands_class_id() == kSmiCid)) {
+    // Found comparison of two smis. Constrain defn at true and false
+    // successors using the other operand as a boundary.
+    Definition* boundary;
+    Token::Kind op_kind;
+    if (use->use_index() == 0) {  // Left operand.
+      boundary = rel_op->InputAt(1)->definition();
+      op_kind = rel_op->kind();
+    } else {
+      ASSERT(use->use_index() == 1);  // Right operand.
+      boundary = rel_op->InputAt(0)->definition();
+      // InsertConstraintFor assumes that defn is left operand of a
+      // comparison if it is right operand flip the comparison.
+      op_kind = FlipComparison(rel_op->kind());
+    }
+
+    // Constrain definition at the true successor.
+    ConstraintInstr* true_constraint =
+        InsertConstraintFor(defn,
+                            ConstraintRange(op_kind, boundary),
+                            branch->true_successor());
+    // Mark true_constraint an artificial use of boundary. This ensures
+    // that constraint's range is recalculated if boundary's range changes.
+    if (true_constraint != NULL) true_constraint->AddDependency(boundary);
+
+    // Constrain definition with a negated condition at the false successor.
+    ConstraintInstr* false_constraint =
+        InsertConstraintFor(
+            defn,
+            ConstraintRange(NegateComparison(op_kind), boundary),
+            branch->false_successor());
+    // Mark false_constraint an artificial use of boundary. This ensures
+    // that constraint's range is recalculated if boundary's range changes.
+    if (false_constraint != NULL) false_constraint->AddDependency(boundary);
+  }
+}
+
 void RangeAnalysis::InsertConstraintsFor(Definition* defn) {
   for (Value* use = defn->input_use_list();
        use != NULL;
        use = use->next_use()) {
     if (use->instruction()->IsBranch()) {

[Florian Schneider, 2012/10/30 15:31:39]

Please make sure that both cases are triggered by our tests.

[Vyacheslav Egorov (Google), 2012/10/30 16:22:35]

Done.

-      BranchInstr* branch = use->instruction()->AsBranch();
-      RelationalOpInstr* rel_op = branch->comparison()->AsRelationalOp();
-      if ((rel_op != NULL) && (rel_op->operands_class_id() == kSmiCid)) {
-        // Found comparison of two smis. Constrain defn at true and false
-        // successors using the other operand as a boundary.
-        Definition* boundary;
-        Token::Kind op_kind;
-        if (use->use_index() == 0) {  // Left operand.
-          boundary = rel_op->InputAt(1)->definition();
-          op_kind = rel_op->kind();
-        } else {
-          ASSERT(use->use_index() == 1);  // Right operand.
-          boundary = rel_op->InputAt(0)->definition();
-          // InsertConstraintFor assumes that defn is left operand of a
-          // comparison if it is right operand flip the comparison.
-          op_kind = FlipComparison(rel_op->kind());
-        }
-
-        // Constrain definition at the true successor.
-        ConstraintInstr* true_constraint =
-            InsertConstraintFor(defn,
-                                ConstraintRange(op_kind, boundary),
-                                branch->true_successor());
-        // Mark true_constraint an artificial use of boundary. This ensures
-        // that constraint's range is recalculated if boundary's range changes.
-        if (true_constraint != NULL) true_constraint->AddDependency(boundary);
-
-        // Constrain definition with a negated condition at the false successor.
-        ConstraintInstr* false_constraint =
-            InsertConstraintFor(
-                defn,
-                ConstraintRange(NegateComparison(op_kind), boundary),
-                branch->false_successor());
-        // Mark false_constraint an artificial use of boundary. This ensures
-        // that constraint's range is recalculated if boundary's range changes.
-        if (false_constraint != NULL) false_constraint->AddDependency(boundary);
-      }
+      ConstrainValueAfterBranch(defn, use);
+    } else if (use->instruction()->IsCheckArrayBound()) {
+      ConstrainValueAfterCheckArrayBound(
+          defn,
+          use->instruction()->AsCheckArrayBound());
     }
   }
 }
 
 
+Definition* RangeAnalysis::LoadArrayLength(CheckArrayBoundInstr* check) {
+  Definition* array = check->array()->definition();
+
+  Definition* length = array_lengths_.Lookup(array);
+  if (length != NULL) return length;
+
+  StaticCallInstr* allocation = array->AsStaticCall();
+  if ((allocation != NULL) &&
+      allocation->is_known_constructor() &&
+      (allocation->ResultCid() == kArrayCid)) {
+    // For fixed length arrays check if array is the result of a constructor
+    // call. In this case we can use the length passed to the constructor
+    // instead of loading it from array itself.
+    length = allocation->ArgumentAt(1)->value()->definition();
+  } else {

[Florian Schneider, 2012/10/30 15:31:39]

Please make sure that both cases are triggered by our tests.

[Vyacheslav Egorov (Google), 2012/10/30 16:22:35]

Done.

[Vyacheslav Egorov (Google), 2012/10/30 16:22:35]

Done.

+    // Load length from the array.
+    LoadFieldInstr* length_load = new LoadFieldInstr(
+        check->array()->Copy(),
+        Array::length_offset(),
+        Type::ZoneHandle(Type::SmiType()),
+        true);  // Immutable.
+    length_load->set_recognized_kind(MethodRecognizer::kObjectArrayLength);
+    length_load->set_result_cid(kSmiCid);
+    length_load->set_ssa_temp_index(flow_graph_->alloc_ssa_temp_index());
+    /* length_load->InsertAfter(prev); */

[Florian Schneider, 2012/10/30 15:31:39]

Remove commented code.

[Vyacheslav Egorov (Google), 2012/10/30 16:22:35]

Done.

[Vyacheslav Egorov (Google), 2012/10/30 16:22:35]

Done.

+    length = length_load;
+  }
+
+  ASSERT(length != NULL);
+  array_lengths_.Insert(ArrayLengthData(array, length));
+  return length;
+}
+
+
+void RangeAnalysis::ConstrainValueAfterCheckArrayBound(Definition* defn,

[Florian Schneider, 2012/10/30 15:31:39]

Maybe break the line after (.

[Vyacheslav Egorov (Google), 2012/10/30 16:22:35]

Done.

+  CheckArrayBoundInstr* check) {
+  if ((check->array_type() != kArrayCid) &&
+      (check->array_type() != kImmutableArrayCid)) {
+    return;
+  }
+
+  Definition* length = LoadArrayLength(check);
+
+  Range* constraint_range = new Range(
+      RangeBoundary::FromConstant(0),
+      RangeBoundary::FromDefinition(length, -1));
+  InsertConstraintFor(defn, constraint_range, check);
+}
+
+
 void RangeAnalysis::InsertConstraints() {
   for (intptr_t i = 0; i < smi_checks_.length(); i++) {
     CheckSmiInstr* check = smi_checks_[i];
@@ -2095,9 +2196,11 @@ void RangeAnalysis::InferRangesRecursive(BlockEntryInstr* block) {
         smi_definitions_->Contains(defn->ssa_temp_index())) {
       defn->InferRange();
     } else if (FLAG_array_bounds_check_elimination &&
-               current->IsCheckArrayBound() &&
-               current->AsCheckArrayBound()->IsRedundant()) {
-      it.RemoveCurrentFromGraph();
+               current->IsCheckArrayBound()) {
+      CheckArrayBoundInstr* check = current->AsCheckArrayBound();
+      RangeBoundary array_length =
+          RangeBoundary::FromDefinition(LoadArrayLength(check));
+      if (check->IsRedundant(array_length)) it.RemoveCurrentFromGraph();
     }
   }
 
@@ -2545,7 +2648,7 @@ static bool IsLoadEliminationCandidate(Definition* def) {
 
 
 static intptr_t NumberLoadExpressions(FlowGraph* graph) {
-  DirectChainedHashMap<Definition*> map;
+  DirectChainedHashMap<PointerKeyValueTrait<Definition> > map;
   intptr_t expr_id = 0;
   for (BlockIterator it = graph->reverse_postorder_iterator();
        !it.Done();
@@ -2735,7 +2838,7 @@ bool DominatorBasedCSE::Optimize(FlowGraph* graph) {
     }
   }
 
-  DirectChainedHashMap<Instruction*> map;
+  DirectChainedHashMap<PointerKeyValueTrait<Instruction> > map;
   changed = OptimizeRecursive(graph->graph_entry(), &map) || changed;
 
   return changed;
@@ -2744,7 +2847,7 @@ bool DominatorBasedCSE::Optimize(FlowGraph* graph) {
 
 bool DominatorBasedCSE::OptimizeRecursive(
     BlockEntryInstr* block,
-    DirectChainedHashMap<Instruction*>* map) {
+    DirectChainedHashMap<PointerKeyValueTrait<Instruction> >* map) {
   bool changed = false;
   for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
     Instruction* current = it.Current();
@@ -2764,7 +2867,8 @@ bool DominatorBasedCSE::OptimizeRecursive(
   for (intptr_t i = 0; i < num_children; ++i) {
     BlockEntryInstr* child = block->dominated_blocks()[i];
     if (i  < num_children - 1) {
-      DirectChainedHashMap<Instruction*> child_map(*map);  // Copy map.
+      // Copy map.
+      DirectChainedHashMap<PointerKeyValueTrait<Instruction> > child_map(*map);
       changed = OptimizeRecursive(child, &child_map) || changed;
     } else {
       // Reuse map for the last child.