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 from dominates to and all paths between from and to are
+  // free of side effects.
+  bool IsSideEffectFreePath(BlockEntryInstr* from, BlockEntryInstr* to) const;
+
+  // Per block sets of available blocks. Block A is available at the block B if
+  // and only if A dominates B and all paths from A to B are free of side
+  // effects.
+  GrowableArray<BitVector*> available_at_;
+};
+
+
 }  // namespace dart
 
 #endif  // VM_FLOW_GRAPH_H_