Track side-effect free paths in the graph to allow CSE and LICM for instructions that depend on som…

runtime/vm/flow_graph.cc

Index: runtime/vm/flow_graph.cc
diff --git a/runtime/vm/flow_graph.cc b/runtime/vm/flow_graph.cc
index 167e443edf90e0092ab3126a8634e6493807ee70..187465b9f1b45b29a3b54bbd19ee83109dc66f97 100644
--- a/runtime/vm/flow_graph.cc
+++ b/runtime/vm/flow_graph.cc
@@ -28,7 +28,8 @@ FlowGraph::FlowGraph(const FlowGraphBuilder& builder,
     graph_entry_(graph_entry),
     preorder_(),
     postorder_(),
-    reverse_postorder_() {
+    reverse_postorder_(),
+    block_effects_(NULL) {
   DiscoverBlocks();
 }
 
@@ -99,6 +100,9 @@ void FlowGraph::DiscoverBlocks() {
   for (intptr_t i = 0; i < block_count; ++i) {
     reverse_postorder_.Add(postorder_[block_count - i - 1]);
   }
+
+  // Block effects are using postorder numbering. Discard computed information.
+  block_effects_ = NULL;
 }
 
 
@@ -923,4 +927,113 @@ intptr_t FlowGraph::InstructionCount() const {
   return size;
 }
 
+
+void FlowGraph::ComputeBlockEffects() {
+  block_effects_ = new BlockEffects(this);
+}
+
+
+BlockEffects::BlockEffects(FlowGraph* flow_graph)
+    : live_in_(flow_graph->postorder().length()) {
+  // We are tracking a single effect.
+  ASSERT(EffectSet::kLastEffect == 1);
+
+  const intptr_t block_count = flow_graph->postorder().length();
+
+  // Set of blocks that contain side-effects.
+  BitVector* kill = new BitVector(block_count);
+
+  // Per block live-out sets. Block A is live-out for the block B if
+  // and only if A is either equal to B or A is live-in for B and B contains no
+  // side-effects. Initially we consider all blocks live-out for all other
+  // blocks.
+  GrowableArray<BitVector*> live_out(block_count);
+
+  // Discover all blocks with side-effects.
+  for (BlockIterator it = flow_graph->postorder_iterator();
+       !it.Done();
+       it.Advance()) {
+    live_in_.Add(NULL);
+    live_out.Add(NULL);
+
+    BlockEntryInstr* block = it.Current();
+    for (ForwardInstructionIterator it(block);
+         !it.Done();
+         it.Advance()) {
+      if (!it.Current()->Effects().IsNone()) {
+        kill->Add(block->postorder_number());
+        break;
+      }
+    }
+  }
+
+  BitVector* temp = new BitVector(block_count);
+
+  // Recompute live-in based on predecessors' live-out until fix point is
+  // reached.
+  bool changed;
+  do {
+    changed = false;
+
+    for (BlockIterator it = flow_graph->reverse_postorder_iterator();
+         !it.Done();
+         it.Advance()) {
+      BlockEntryInstr* block = it.Current();
+      const intptr_t block_num = block->postorder_number();
+
+      if (block->IsGraphEntry()) {
+        temp->Clear();  // Nothing is live-in into graph entry.
+      } else {
+        // Live-in is an intersection of all predecessors' live-out sets.
+        temp->SetAll();
+        for (intptr_t i = 0; i < block->PredecessorCount(); i++) {
+          const intptr_t pred = block->PredecessorAt(i)->postorder_number();
+          if (live_out[pred] != NULL) {
+            temp->Intersect(live_out[pred]);
+          }
+        }
+      }
+
+      BitVector* current = live_in_[block_num];
+      if ((current == NULL) || !current->Equals(*temp)) {
+        // Live-in changed: update it and recompute live-out.
+        if (live_in_[block_num] == NULL) {
+          current = live_in_[block_num] = new BitVector(block_count);
+          live_out[block_num] = new BitVector(block_count);
+          // Block is always live out from itself.
+          live_out[block_num]->Add(block_num);
+        }
+        current->CopyFrom(temp);
+        if (!kill->Contains(block_num)) {
+          live_out[block_num]->CopyFrom(temp);
+          // Block is always live out from itself.
+          live_out[block_num]->Add(block_num);
+        }
+        changed = true;
+      }
+    }
+  } while (changed);
+}
+
+
+bool BlockEffects::IsAvailableAt(Instruction* instr,
+                                 BlockEntryInstr* block) const {
+  return (instr->Dependencies().IsNone()) ||
+      IsSideEffectFreePath(instr->GetBlock(), block);
+}
+
+
+bool BlockEffects::CanBeMovedTo(Instruction* instr,
+                                BlockEntryInstr* block) const {
+  return (instr->Dependencies().IsNone()) ||
+      IsSideEffectFreePath(block, instr->GetBlock());
+}
+
+
+bool BlockEffects::IsSideEffectFreePath(BlockEntryInstr* from,
+                                        BlockEntryInstr* to) const {
+  return live_in_[to->postorder_number()]->Contains(
+      from->postorder_number());
+}
+
 }  // namespace dart