Generalize bounds checks.

runtime/vm/flow_graph_optimizer.cc

 // 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.
 
 #include "vm/flow_graph_optimizer.h"
 
 #include "vm/bit_vector.h"
 #include "vm/cha.h"
 #include "vm/cpu.h"
 #include "vm/dart_entry.h"
@@ skipping 4707 matching lines @@
   // can't deoptimize.
   instr->RemoveEnvironment();
   ReplaceCall(instr, store);
   return true;
 }
 
 
 #if defined(TARGET_ARCH_ARM) || defined(TARGET_ARCH_IA32)
 // Smi widening pass is only meaningful on platforms where Smi
 // is smaller than 32bit. For now only support it on ARM and ia32.
-
-class DefinitionWorklist : public ValueObject {
- public:
-  DefinitionWorklist(FlowGraph* flow_graph,
-                     intptr_t initial_capacity)
-      : defs_(initial_capacity),
-        contains_vector_(new(flow_graph->isolate()) BitVector(
-            flow_graph->isolate(), flow_graph->current_ssa_temp_index())) {
-  }
-
-  void Add(Definition* defn) {
-    if (!Contains(defn)) {
-      defs_.Add(defn);
-      contains_vector_->Add(defn->ssa_temp_index());
-    }
-  }
-
-  bool Contains(Definition* defn) const {
-    return (defn->ssa_temp_index() >= 0) &&
-        contains_vector_->Contains(defn->ssa_temp_index());
-  }
-
-  const GrowableArray<Definition*>& definitions() const { return defs_; }
-  BitVector* contains_vector() const { return contains_vector_; }
-
-  void Clear() {
-    defs_.TruncateTo(0);
-    contains_vector_->Clear();
-  }
-
- private:
-  GrowableArray<Definition*> defs_;
-  BitVector* contains_vector_;
-};
-
-
 static bool CanBeWidened(BinarySmiOpInstr* smi_op) {
   return BinaryInt32OpInstr::IsSupported(smi_op->op_kind(),
                                          smi_op->left(),
                                          smi_op->right());
 }
 
 
 static bool BenefitsFromWidening(BinarySmiOpInstr* smi_op) {
   // TODO(vegorov): when shifts with non-constants shift count are supported
   // add them here as we save untagging for the count.
@@ skipping 278 matching lines @@
             new(flow_graph->isolate()) ConstantInstr(orig->value());
         copy->set_ssa_temp_index(flow_graph->alloc_ssa_temp_index());
         old->ReplaceUsesWith(copy);
         (*idefs)[j] = copy;
       }
     }
   }
 }
 
 
-static BlockEntryInstr* FindPreHeader(BlockEntryInstr* header) {
-  for (intptr_t j = 0; j < header->PredecessorCount(); ++j) {
-    BlockEntryInstr* candidate = header->PredecessorAt(j);
-    if (header->dominator() == candidate) {
-      return candidate;
-    }
-  }
-  return NULL;
-}
-
-
 LICM::LICM(FlowGraph* flow_graph) : flow_graph_(flow_graph) {
   ASSERT(flow_graph->is_licm_allowed());
 }
 
 
 void LICM::Hoist(ForwardInstructionIterator* it,
                  BlockEntryInstr* pre_header,
                  Instruction* current) {
   if (current->IsCheckClass()) {
     current->AsCheckClass()->set_licm_hoisted(true);
@@ skipping 98 matching lines @@
     // Do not hoist any.
     return;
   }
 
   const ZoneGrowableArray<BlockEntryInstr*>& loop_headers =
       flow_graph()->LoopHeaders();
 
   for (intptr_t i = 0; i < loop_headers.length(); ++i) {
     JoinEntryInstr* header = loop_headers[i]->AsJoinEntry();
     // Skip loop that don't have a pre-header block.
-    BlockEntryInstr* pre_header = FindPreHeader(header);
+    BlockEntryInstr* pre_header = header->ImmediateDominator();
     if (pre_header == NULL) continue;
 
     for (PhiIterator it(header); !it.Done(); it.Advance()) {
       TrySpecializeSmiPhi(it.Current(), header, pre_header);
     }
   }
 }
 
 
 void LICM::Optimize() {
   if (!flow_graph()->parsed_function().function().
           allows_hoisting_check_class()) {
     // Do not hoist any.
     return;
   }
 
   const ZoneGrowableArray<BlockEntryInstr*>& loop_headers =
       flow_graph()->LoopHeaders();
 
   ZoneGrowableArray<BitVector*>* loop_invariant_loads =
       flow_graph()->loop_invariant_loads();
 
   BlockEffects* block_effects = flow_graph()->block_effects();
 
   for (intptr_t i = 0; i < loop_headers.length(); ++i) {
     BlockEntryInstr* header = loop_headers[i];
     // Skip loop that don't have a pre-header block.
-    BlockEntryInstr* pre_header = FindPreHeader(header);
+    BlockEntryInstr* pre_header = header->ImmediateDominator();
     if (pre_header == NULL) continue;
 
     for (BitVector::Iterator loop_it(header->loop_info());
          !loop_it.Done();
          loop_it.Advance()) {
       BlockEntryInstr* block = flow_graph()->preorder()[loop_it.Current()];
       for (ForwardInstructionIterator it(block);
            !it.Done();
            it.Advance()) {
         Instruction* current = it.Current();
@@ skipping 1505 matching lines @@
 
   void MarkLoopInvariantLoads() {
     const ZoneGrowableArray<BlockEntryInstr*>& loop_headers =
         graph_->LoopHeaders();
 
     ZoneGrowableArray<BitVector*>* invariant_loads =
         new(I) ZoneGrowableArray<BitVector*>(loop_headers.length());
 
     for (intptr_t i = 0; i < loop_headers.length(); i++) {
       BlockEntryInstr* header = loop_headers[i];
-      BlockEntryInstr* pre_header = FindPreHeader(header);
+      BlockEntryInstr* pre_header = header->ImmediateDominator();
       if (pre_header == NULL) {
         invariant_loads->Add(NULL);
         continue;
       }
 
       BitVector* loop_gen = new(I) BitVector(I, aliased_set_->max_place_id());
       for (BitVector::Iterator loop_it(header->loop_info());
            !loop_it.Done();
            loop_it.Advance()) {
         const intptr_t preorder_number = loop_it.Current();
@@ skipping 3364 matching lines @@
 
   // Insert materializations at environment uses.
   for (intptr_t i = 0; i < exits_collector_.exits().length(); i++) {
     CreateMaterializationAt(
         exits_collector_.exits()[i], alloc, alloc->cls(), *slots);
   }
 }
 
 
 }  // namespace dart