Compute assigned variables and dominance frontiers.

runtime/vm/intermediate_language.h

Index: runtime/vm/intermediate_language.h
diff --git a/runtime/vm/intermediate_language.h b/runtime/vm/intermediate_language.h
index 3a9160d0b491c3724e0bdb5b39598c4fe60ee35d..cf84566e54b25d3fa6122a03f53e771e9c0e3fa6 100644
--- a/runtime/vm/intermediate_language.h
+++ b/runtime/vm/intermediate_language.h
@@ -13,6 +13,7 @@
 
 namespace dart {
 
+class BitVector;
 class FlowGraphVisitor;
 class LocalVariable;
 
@@ -86,6 +87,8 @@ class Computation : public ZoneAllocated {
 
   virtual intptr_t InputCount() const = 0;
 
+  virtual void RecordAssignedVars(BitVector* assigned_vars);

[srdjan, 2012/05/12 00:00:55]

Please document what does BitVector represent.

[Kevin Millikin (Google), 2012/05/15 11:51:44]

Done.

+
  private:
   friend class Instruction;
   static intptr_t GetNextCid(Isolate* isolate) {
@@ -518,6 +521,8 @@ class StoreLocalComp : public TemplateComputation<1> {
   Value* value() { return inputs_[0]; }
   intptr_t context_level() const { return context_level_; }
 
+  virtual void RecordAssignedVars(BitVector* assigned_vars);
+
  private:
   const LocalVariable& local_;
   const intptr_t context_level_;
@@ -1192,19 +1197,25 @@ class Instruction : public ZoneAllocated {
   // preorder block numbers to the block entry instruction with that number
   // and analogously for the array 'postorder'.  The depth first spanning
   // tree is recorded in the array 'parent', which maps preorder block
-  // numbers to the preorder number of the block's spanning-tree parent.  As
-  // a side effect of this function, the set of basic block predecessors
-  // (e.g., block entry instructions of predecessor blocks) and also the
-  // last instruction in the block is recorded in each entry instruction.
+  // numbers to the preorder number of the block's spanning-tree parent.
+  // The array 'assigned_vars' maps preorder block numbers to the set of
+  // assigned frame-allocated local variables in the block.  As a side
+  // effect of this function, the set of basic block predecessors (e.g.,
+  // block entry instructions of predecessor blocks) and also the last
+  // instruction in the block is recorded in each entry instruction.
   virtual void DiscoverBlocks(
       BlockEntryInstr* current_block,
       GrowableArray<BlockEntryInstr*>* preorder,
       GrowableArray<BlockEntryInstr*>* postorder,
-      GrowableArray<intptr_t>* parent) {
+      GrowableArray<intptr_t>* parent,
+      GrowableArray<BitVector*>* assigned_vars,
+      intptr_t variable_count) {
     // Never called for instructions except block entries and branches.
     UNREACHABLE();
   }
 
+  virtual void RecordAssignedVars(BitVector* assigned_vars);
+
 #define INSTRUCTION_TYPE_CHECK(type)                                           \
   virtual bool Is##type() const { return false; }                              \
   virtual type##Instr* As##type() { return NULL; }
@@ -1228,6 +1239,7 @@ class BlockEntryInstr : public Instruction {
 
   virtual intptr_t PredecessorCount() const = 0;
   virtual BlockEntryInstr* PredecessorAt(intptr_t index) const = 0;
+  virtual void AddPredecessor(BlockEntryInstr* predecessor) = 0;
 
   intptr_t preorder_number() const { return preorder_number_; }
   void set_preorder_number(intptr_t number) { preorder_number_ = number; }
@@ -1241,6 +1253,14 @@ class BlockEntryInstr : public Instruction {
   Instruction* last_instruction() const { return last_instruction_; }
   void set_last_instruction(Instruction* instr) { last_instruction_ = instr; }
 
+  virtual void DiscoverBlocks(

[Kevin Millikin (Google), 2012/05/11 10:39:00]

All these arguments is a bad smell, I plan to refactor later.

[srdjan, 2012/05/12 00:00:55]

Sounds good.

+      BlockEntryInstr* current_block,
+      GrowableArray<BlockEntryInstr*>* preorder,
+      GrowableArray<BlockEntryInstr*>* postorder,
+      GrowableArray<intptr_t>* parent,
+      GrowableArray<BitVector*>* assigned_vars,
+      intptr_t variable_count);
+
  protected:
   BlockEntryInstr()
       : preorder_number_(-1),
@@ -1271,6 +1291,9 @@ class JoinEntryInstr : public BlockEntryInstr {
   virtual BlockEntryInstr* PredecessorAt(intptr_t index) const {
     return predecessors_[index];
   }
+  virtual void AddPredecessor(BlockEntryInstr* predecessor) {
+    predecessors_.Add(predecessor);
+  }
 
   virtual Instruction* StraightLineSuccessor() const {
     return successor_;
@@ -1280,12 +1303,6 @@ class JoinEntryInstr : public BlockEntryInstr {
     successor_ = instr;
   }
 
-  virtual void DiscoverBlocks(
-      BlockEntryInstr* current_block,
-      GrowableArray<BlockEntryInstr*>* preorder,
-      GrowableArray<BlockEntryInstr*>* postorder,
-      GrowableArray<intptr_t>* parent);
-
  private:
   ZoneGrowableArray<BlockEntryInstr*> predecessors_;
   Instruction* successor_;
@@ -1318,6 +1335,10 @@ class TargetEntryInstr : public BlockEntryInstr {
     ASSERT((index == 0) && (predecessor_ != NULL));
     return predecessor_;
   }
+  virtual void AddPredecessor(BlockEntryInstr* predecessor) {
+    ASSERT(predecessor_ == NULL);
+    predecessor_ = predecessor;
+  }
 
   virtual Instruction* StraightLineSuccessor() const {
     return successor_;
@@ -1327,12 +1348,6 @@ class TargetEntryInstr : public BlockEntryInstr {
     successor_ = instr;
   }
 
-  virtual void DiscoverBlocks(
-      BlockEntryInstr* current_block,
-      GrowableArray<BlockEntryInstr*>* preorder,
-      GrowableArray<BlockEntryInstr*>* postorder,
-      GrowableArray<intptr_t>* parent);
-
   bool HasTryIndex() const {
     return try_index_ != CatchClauseNode::kInvalidTryIndex;
   }
@@ -1368,6 +1383,8 @@ class DoInstr : public Instruction {
     successor_ = instr;
   }
 
+  virtual void RecordAssignedVars(BitVector* assigned_vars);
+
  private:
   Computation* computation_;
   Instruction* successor_;
@@ -1409,6 +1426,8 @@ class BindInstr : public Definition {
     successor_ = instr;
   }
 
+  virtual void RecordAssignedVars(BitVector* assigned_vars);
+
  private:
   Computation* computation_;
   Instruction* successor_;
@@ -1610,7 +1629,9 @@ class BranchInstr : public Instruction {
       BlockEntryInstr* current_block,
       GrowableArray<BlockEntryInstr*>* preorder,
       GrowableArray<BlockEntryInstr*>* postorder,
-      GrowableArray<intptr_t>* parent);
+      GrowableArray<intptr_t>* parent,
+      GrowableArray<BitVector*>* assigned_vars,
+      intptr_t variable_count);
 
  private:
   Value* value_;