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

runtime/vm/flow_graph_optimizer.cc

 // Copyright (c) 2012, 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_optimizer.h"
 
 #include "vm/bit_vector.h"
 #include "vm/cha.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/flow_graph_compiler.h"
@@ skipping 1599 matching lines @@
   // 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(Definition* defn,
                                        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,
                            Instruction* dom,
                            Definition* other);
 
 
   // Walk the dominator tree and infer ranges for smi values.
   void InferRanges();
   void InferRangesRecursive(BlockEntryInstr* block);
@@ skipping 38 matching lines @@
   // as smi values.
   GrowableArray<ConstraintInstr*> constraints_;
 
   // Bitvector for a quick filtering of known smi values.
   BitVector* smi_definitions_;
 
   // Worklist for induction variables analysis.
   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 bool IsKeyEqual(const ArrayLengthData& kv, Key key) {
+      return kv.array() == key;
+    }
+
+   private:
+    Definition* array_;
+    Definition* array_length_;
+  };
+
+  DirectChainedHashMap<ArrayLengthData> array_lengths_;
+
   DISALLOW_COPY_AND_ASSIGN(RangeAnalysis);
 };
 
 
 void RangeAnalysis::Analyze() {
   CollectSmiValues();
   InsertConstraints();
   InferRanges();
   RemoveConstraints();
 }
@@ skipping 168 matching lines @@
   constraint->set_ssa_temp_index(flow_graph_->alloc_ssa_temp_index());
   RenameDominatedUses(defn, after, constraint);
   constraints_.Add(constraint);
   constraint->value()->set_instruction(constraint);
   constraint->value()->set_use_index(0);
   constraint->value()->AddToInputUseList();
   return constraint;
 }
 
 
+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()) {
-      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 {
+    // Load length from the array. Do not insert instruction into the graph.
+    // It will only be used in range boundaries.
+    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 = length_load;
+  }
+
+  ASSERT(length != NULL);
+  array_lengths_.Insert(ArrayLengthData(array, length));
+  return length;
+}
+
+
+void RangeAnalysis::ConstrainValueAfterCheckArrayBound(
+    Definition* defn, 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];
     ConstraintInstr* constraint =
         InsertConstraintFor(check->value()->definition(),
                             Range::Unknown(),
                             check);
     if (constraint != NULL) {
       InsertConstraintsFor(constraint);  // Constrain uses further.
     }
@@ skipping 165 matching lines @@
 
   for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
     Instruction* current = it.Current();
 
     Definition* defn = current->AsDefinition();
     if ((defn != NULL) &&
         (defn->ssa_temp_index() != -1) &&
         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();
     }
   }
 
   for (intptr_t i = 0; i < block->dominated_blocks().length(); ++i) {
     InferRangesRecursive(block->dominated_blocks()[i]);
   }
 }
 
 
 void RangeAnalysis::InferRanges() {
@@ skipping 427 matching lines @@
 static bool IsLoadEliminationCandidate(Definition* def) {
   // Immutable loads (not affected by side effects) are handled
   // in the DominatorBasedCSE pass.
   // TODO(fschneider): Extend to other load instructions.
   return (def->IsLoadField() && def->AffectedBySideEffect())
       || def->IsLoadIndexed();
 }
 
 
 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();
        it.Advance()) {
     BlockEntryInstr* block = it.Current();
     for (ForwardInstructionIterator instr_it(block);
          !instr_it.Done();
          instr_it.Advance()) {
       Definition* defn = instr_it.Current()->AsDefinition();
       if ((defn == NULL) || !IsLoadEliminationCandidate(defn)) {
@@ skipping 169 matching lines @@
       ComputeAvailableLoads(graph, max_expr_id, avail_in);
 
       GrowableArray<Definition*> definitions(max_expr_id);
       for (intptr_t j = 0; j < max_expr_id ; j++) {
         definitions.Add(NULL);
       }
       changed = OptimizeLoads(graph->graph_entry(), &definitions, avail_in);
     }
   }
 
-  DirectChainedHashMap<Instruction*> map;
+  DirectChainedHashMap<PointerKeyValueTrait<Instruction> > map;
   changed = OptimizeRecursive(graph->graph_entry(), &map) || changed;
 
   return changed;
 }
 
 
 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();
     if (current->AffectedBySideEffect()) continue;
     Instruction* replacement = map->Lookup(current);
     if (replacement == NULL) {
       map->Insert(current);
       continue;
     }
     // Replace current with lookup result.
     ReplaceCurrentInstruction(&it, current, replacement);
     changed = true;
   }
 
   // Process children in the dominator tree recursively.
   intptr_t num_children = block->dominated_blocks().length();
   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.
       changed = OptimizeRecursive(child, map) || changed;
     }
   }
   return changed;
 }
 
 
@@ skipping 760 matching lines @@
 
   if (FLAG_trace_constant_propagation) {
     OS::Print("\n==== After constant propagation ====\n");
     FlowGraphPrinter printer(*graph_);
     printer.PrintBlocks();
   }
 }
 
 
 }  // namespace dart