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

runtime/vm/flow_graph.h

Index: runtime/vm/flow_graph.h
diff --git a/runtime/vm/flow_graph.h b/runtime/vm/flow_graph.h
index 4d384f35de35d09454f2109d3a57945ffbe1b14d..b2a857400243b777679c789d9d4ef15c6ad1fcf6 100644
--- a/runtime/vm/flow_graph.h
+++ b/runtime/vm/flow_graph.h
@@ -11,6 +11,7 @@
 
 namespace dart {
 
+class BlockEffects;
 class FlowGraphBuilder;
 class ValueInliningContext;
 class VariableLivenessAnalysis;
@@ -140,6 +141,11 @@ class FlowGraph : public ZoneAllocated {
 
   void DiscoverBlocks();
 
+  // Compute information about effects occuring in different blocks and
+  // discover side-effect free paths.
+  void ComputeBlockEffects();
+  BlockEffects* block_effects() const { return block_effects_; }
+
  private:
   friend class IfConverter;
   friend class BranchSimplifier;
@@ -193,6 +199,8 @@ class FlowGraph : public ZoneAllocated {
   GrowableArray<BlockEntryInstr*> postorder_;
   GrowableArray<BlockEntryInstr*> reverse_postorder_;
   ConstantInstr* constant_null_;
+
+  BlockEffects* block_effects_;
 };
 
 
@@ -266,6 +274,35 @@ class LivenessAnalysis : public ValueObject {
   GrowableArray<BitVector*> live_in_;
 };
 
+
+// Information about side effect free paths between blocks.
+class BlockEffects : public ZoneAllocated {
+ public:
+  explicit BlockEffects(FlowGraph* flow_graph);
+
+  // Return true if the given instruction is not affected by anything between
+  // its current block and target block. Used by CSE to determine if
+  // a computation is available in the given block.
+  bool IsAvailableAt(Instruction* instr, BlockEntryInstr* block) const;
+
+  // Return true if the given instruction is not affected by anything between
+  // the given block and its current block. Used by LICM to determine if
+  // a computation can be moved to loop's preheader and remain available at
+  // its current location.
+  bool CanBeMovedTo(Instruction* instr, BlockEntryInstr* block) const;
+
+ private:
+  // Returns true if all paths between from and to are free of side effects and
+  // there is at least one path between these blocks.
+  bool IsSideEffectFreePath(BlockEntryInstr* from, BlockEntryInstr* to) const;
+
+  // Per block live-in sets. Block A is live-in for the block B if and only if
+  // all paths from A to B are free of side effects and there is at least one
+  // path between these blocks.

[Florian Schneider, 2013/04/29 12:11:54]

This definition is not precise about what the code actually computes:

Assuming no side effects in blocks A, B, C, D and a diamond-shaped graph A->B,
A->C, B->D, C->D

in(A) = {},  out(A) = {A}
in(B) = {A}, out(B) = {A,B}
in(C) = {A}, out(C) = {A,C}
in(D) = {A}, out(D) = {A,D}

There is a path without side effects from B to D, but B is not in in(D) because
{A,B} intersect {A,C} is just {A}.

[Vyacheslav Egorov (Google), 2013/04/30 14:01:33]

Done.

+  GrowableArray<BitVector*> live_in_;

[Florian Schneider, 2013/04/29 12:11:54]

Maybe choose a better name for in/out. live_in is already used for live
variables. e.g. freepath_in, freepath_out

[Vyacheslav Egorov (Google), 2013/04/30 14:01:33]

Renamed to available_at_ and available_after 

+};
+
+
 }  // namespace dart
 
 #endif  // VM_FLOW_GRAPH_H_