Basic support for LICM of fully invariant loads.

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/flow_graph_builder.h"
 #include "vm/flow_graph_compiler.h"
@@ skipping 3328 matching lines @@
   // Host CheckSmi instruction and make this phi smi one.
   Hoist(it, pre_header, current);
 
   // Replace value we are checking with phi's input.
   current->value()->BindTo(phi->InputAt(non_smi_input)->definition());
 
   phi->UpdateType(CompileType::FromCid(kSmiCid));
 }
 
 
+static bool IsLoopInvariantLoad(ZoneGrowableArray<BitVector*>* sets,
+                                intptr_t loop_header_index,
+                                Instruction* instr) {
+  return (sets != NULL) &&
+      instr->HasExprId() &&
+      ((*sets)[loop_header_index] != NULL) &&
+      (*sets)[loop_header_index]->Contains(instr->expr_id());
+}
+
+
 void LICM::Optimize() {
-  GrowableArray<BlockEntryInstr*> loop_headers;
-  flow_graph()->ComputeLoops(&loop_headers);
+  const ZoneGrowableArray<BlockEntryInstr*>& loop_headers =
+      flow_graph()->loop_headers();
+
+  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);
     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();
-        if (current->AllowsCSE() &&
-            flow_graph()->block_effects()->CanBeMovedTo(current, pre_header)) {
+        if ((current->AllowsCSE() &&
+             block_effects->CanBeMovedTo(current, pre_header)) ||
+             IsLoopInvariantLoad(loop_invariant_loads, i, current)) {
           bool inputs_loop_invariant = true;
           for (int i = 0; i < current->InputCount(); ++i) {
             Definition* input_def = current->InputAt(i)->definition();
             if (!input_def->GetBlock()->Dominates(pre_header)) {
               inputs_loop_invariant = false;
               break;
             }
           }
           if (inputs_loop_invariant &&
               !current->IsAssertAssignable() &&
@@ skipping 505 matching lines @@
         continue;
       }
       Definition* result = map->Lookup(defn);
       if (result == NULL) {
         map->Insert(defn);
         defn->set_expr_id(expr_id++);
         loads.Add(defn);
       } else {
         defn->set_expr_id(result->expr_id());
       }
+
+      if (FLAG_trace_optimization) {
+        OS::Print("load v%"Pd" is numbered as %"Pd"\n",
+                  defn->ssa_temp_index(),
+                  defn->expr_id());
+      }
     }
   }
 
   // Build aliasing sets mapping aliases to loads.
   AliasedSet* aliased_set = new AliasedSet(expr_id);
   for (intptr_t i = 0; i < loads.length(); i++) {
     Definition* defn = loads[i];
     aliased_set->AddRepresentative(defn);
   }
   return aliased_set;
@@ skipping 45 matching lines @@
       LoadOptimizer load_optimizer(graph, aliased_set, &map);
       return load_optimizer.Optimize();
     }
     return false;
   }
 
  private:
   bool Optimize() {
     ComputeInitialSets();
     ComputeOutValues();
+    if (graph_->is_licm_allowed()) {
+      MarkLoopInvariantLoads();
+    }
     ForwardLoads();
     EmitPhis();
     return forwarded_;
   }
 
   // Compute sets of loads generated and killed by each block.
   // Additionally compute upwards exposed and generated loads for each block.
   // Exposed loads are those that can be replaced if a corresponding
   // reaching load will be found.
   // Loads that are locally redundant will be replaced as we go through
@@ skipping 235 matching lines @@
           block_in->Print();
           block_out->Print();
           block_kill->Print();
           block_gen->Print();
           OS::Print("\n");
         }
       }
     }
   }
 
+  void MarkLoopInvariantLoads() {
+    const ZoneGrowableArray<BlockEntryInstr*>& loop_headers =
+        graph_->loop_headers();
+
+    ZoneGrowableArray<BitVector*>* invariant_loads =
+        new 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);
+      if (pre_header == NULL) {
+        invariant_loads->Add(NULL);
+        continue;
+      }
+
+      BitVector* loop_gen = new BitVector(aliased_set_->max_expr_id());
+      for (BitVector::Iterator loop_it(header->loop_info());
+           !loop_it.Done();
+           loop_it.Advance()) {
+        const intptr_t preorder_number = loop_it.Current();
+        loop_gen->AddAll(gen_[preorder_number]);
+      }
+
+      for (BitVector::Iterator loop_it(header->loop_info());
+           !loop_it.Done();
+           loop_it.Advance()) {
+        const intptr_t preorder_number = loop_it.Current();
+        loop_gen->RemoveAll(kill_[preorder_number]);
+      }
+
+      if (FLAG_trace_optimization) {
+        for (BitVector::Iterator it(loop_gen); !it.Done(); it.Advance()) {
+          OS::Print("load %"Pd" is loop invariant for B%"Pd"\n",
+                    it.Current(),
+                    header->block_id());
+        }
+      }
+
+      invariant_loads->Add(loop_gen);
+    }
+
+    graph_->set_loop_invariant_loads(invariant_loads);
+  }
+
   // Compute incoming value for the given expression id.
   // Will create a phi if different values are incoming from multiple
   // predecessors.
   Definition* MergeIncomingValues(BlockEntryInstr* block, intptr_t expr_id) {
     // First check if the same value is coming in from all predecessors.
     Definition* incoming = NULL;
     for (intptr_t i = 0; i < block->PredecessorCount(); i++) {
       BlockEntryInstr* pred = block->PredecessorAt(i);
       ZoneGrowableArray<Definition*>* pred_out_values =
           out_values_[pred->preorder_number()];
@@ skipping 2034 matching lines @@
 
   // Insert materializations at environment uses.
   const Class& cls = Class::Handle(alloc->constructor().Owner());
   for (intptr_t i = 0; i < exits.length(); i++) {
     CreateMaterializationAt(exits[i], alloc, cls, *fields);
   }
 }
 
 
 }  // namespace dart