Compute local variable liveness before translation to SSA.

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 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)
       : ValueObject(),
         block_order_(other.block_order_),
         current_(other.current_) { }
@@ skipping 129 matching lines @@
   // SSA transformation methods and fields.
   void ComputeDominators(GrowableArray<BitVector*>* dominance_frontier);
 
   void CompressPath(
       intptr_t start_index,
       intptr_t current_index,
       GrowableArray<intptr_t>* parent,
       GrowableArray<intptr_t>* label);
 
   void Rename(GrowableArray<PhiInstr*>* live_phis,
+              VariableLivenessAnalysis* variable_liveness,
               GrowableArray<Definition*>* inlining_parameters);
+
   void RenameRecursive(
       BlockEntryInstr* block_entry,
       GrowableArray<Definition*>* env,
-      GrowableArray<PhiInstr*>* live_phis);
+      GrowableArray<PhiInstr*>* live_phis,
+      VariableLivenessAnalysis* variable_liveness);
 
   void InsertPhis(
       const GrowableArray<BlockEntryInstr*>& preorder,
       const GrowableArray<BitVector*>& assigned_vars,
       const GrowableArray<BitVector*>& dom_frontier);
 
   void RemoveDeadPhis(GrowableArray<PhiInstr*>* live_phis);
 
   void ReplacePredecessor(BlockEntryInstr* old_block,
                           BlockEntryInstr* new_block);
@@ skipping 12 matching lines @@
   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_;
   bool invalid_dominator_tree_;
   ConstantInstr* constant_null_;
 };
 
+
+class LivenessAnalysis : public ValueObject {
+ public:
+  LivenessAnalysis(intptr_t variable_count,
+                   const GrowableArray<BlockEntryInstr*>& postorder);
+
+  void Analyze();
+
+  virtual ~LivenessAnalysis() { }
+
+  BitVector* GetLiveInSetAt(intptr_t postorder_number) const {
+    return live_in_[postorder_number];
+  }
+
+  BitVector* GetLiveOutSetAt(intptr_t postorder_number) const {
+    return live_out_[postorder_number];
+  }
+
+  BitVector* GetLiveInSet(BlockEntryInstr* block) const {
+    return GetLiveInSetAt(block->postorder_number());
+  }
+
+  BitVector* GetKillSet(BlockEntryInstr* block) const {
+    return kill_[block->postorder_number()];
+  }
+
+  BitVector* GetLiveOutSet(BlockEntryInstr* block) const {
+    return GetLiveOutSetAt(block->postorder_number());
+  }
+
+  // Print results of liveness analysis.
+  void Dump();
+
+ protected:
+  // Compute initial values for live-out, kill and live-in sets.
+  virtual void ComputeInitialSets() = 0;
+
+  // Update live-out set for the given block: live-out should contain
+  // all values that are live-in for block's successors.
+  // Returns true if live-out set was changed.
+  bool UpdateLiveOut(const BlockEntryInstr& instr);
+
+  // Update live-in set for the given block: live-in should contain
+  // all values that are live-out from the block and are not defined
+  // by this block.
+  // Returns true if live-in set was changed.
+  bool UpdateLiveIn(const BlockEntryInstr& instr);
+
+  // Perform fix-point iteration updating live-out and live-in sets
+  // for blocks until they stop changing.
+  void ComputeLiveInAndLiveOutSets();
+
+  const intptr_t variable_count_;
+
+  const GrowableArray<BlockEntryInstr*>& postorder_;
+
+  // Live-out sets for each block.  They contain indices of SSA values

[Kevin Millikin (Google), 2013/03/22 11:57:52]

This comment and the ones below should not mention SSA values.  Just say
"indexes of variables".

[Vyacheslav Egorov (Google), 2013/03/22 12:16:15]

Done.

+  // that are live out from this block: that is values that were either
+  // defined in this block or live into it and that are used in some
+  // successor block.
+  GrowableArray<BitVector*> live_out_;
+
+  // Kill sets for each block.  They contain indices of SSA values that
+  // are defined by this block.
+  GrowableArray<BitVector*> kill_;
+
+  // Live-in sets for each block.  They contain indices of SSA values
+  // that are used by this block or its successors.
+  GrowableArray<BitVector*> live_in_;
+};
+
 }  // namespace dart
 
 #endif  // VM_FLOW_GRAPH_H_