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

runtime/vm/flow_graph.h

 // 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.
 
 #ifndef VM_FLOW_GRAPH_H_
 #define VM_FLOW_GRAPH_H_
 
 #include "vm/growable_array.h"
 #include "vm/intermediate_language.h"
 #include "vm/parser.h"
 
 namespace dart {
 
+class BlockEffects;
 class FlowGraphBuilder;
 class ValueInliningContext;
 class VariableLivenessAnalysis;
 
 class BlockIterator : public ValueObject {
  public:
   explicit BlockIterator(const GrowableArray<BlockEntryInstr*>& block_order)
       : block_order_(block_order), current_(0) { }
 
   BlockIterator(const BlockIterator& other)
@@ skipping 109 matching lines @@
   // TODO(zerny): Once the SSA is feature complete this should be removed.
   void Bailout(const char* reason) const;
 
 #ifdef DEBUG
   // Verification methods for debugging.
   bool VerifyUseLists();
 #endif  // DEBUG
 
   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;
   friend class ConstantPropagator;
 
   // SSA transformation methods and fields.
   void ComputeDominators(GrowableArray<BitVector*>* dominance_frontier);
 
   void CompressPath(
       intptr_t start_index,
@@ skipping 33 matching lines @@
   // Flow graph fields.
   const ParsedFunction& parsed_function_;
   const intptr_t num_copied_params_;
   const intptr_t num_non_copied_params_;
   const intptr_t num_stack_locals_;
   GraphEntryInstr* graph_entry_;
   GrowableArray<BlockEntryInstr*> preorder_;
   GrowableArray<BlockEntryInstr*> postorder_;
   GrowableArray<BlockEntryInstr*> reverse_postorder_;
   ConstantInstr* constant_null_;
+
+  BlockEffects* block_effects_;
 };
 
 
 class LivenessAnalysis : public ValueObject {
  public:
   LivenessAnalysis(intptr_t variable_count,
                    const GrowableArray<BlockEntryInstr*>& postorder);
 
   void Analyze();
 
@@ skipping 53 matching lines @@
 
   // Kill sets for each block.  They contain indices of variables that
   // are defined by this block.
   GrowableArray<BitVector*> kill_;
 
   // Live-in sets for each block.  They contain indices of variables
   // that are used by this block or its successors.
   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_