Compute assigned variables and dominance frontiers.

runtime/vm/intermediate_language.cc

Index: runtime/vm/intermediate_language.cc
diff --git a/runtime/vm/intermediate_language.cc b/runtime/vm/intermediate_language.cc
index 5f28215f9589f4cb6dcbd9e1875d014a250c9ab8..e5f9048d10d53b930a2fbbeb2c00983923037975 100644
--- a/runtime/vm/intermediate_language.cc
+++ b/runtime/vm/intermediate_language.cc
@@ -4,6 +4,7 @@
 
 #include "vm/intermediate_language.h"
 
+#include "vm/bit_vector.h"
 #include "vm/object.h"
 #include "vm/os.h"
 #include "vm/scopes.h"
@@ -192,86 +193,101 @@ intptr_t JoinEntryInstr::InputCount() const {
 }
 
 
-// ==== Postorder graph traversal.
-void JoinEntryInstr::DiscoverBlocks(
-    BlockEntryInstr* current_block,
-    GrowableArray<BlockEntryInstr*>* preorder,
-    GrowableArray<BlockEntryInstr*>* postorder,
-    GrowableArray<intptr_t>* parent) {
-  // The global graph entry is a TargetEntryInstr, so we can assume
-  // current_block is non-null and preorder array is non-empty.
-  ASSERT(current_block != NULL);
-  ASSERT(!preorder->is_empty());
+// ==== Recording assigned variables.
+void Computation::RecordAssignedVars(BitVector* assigned_vars) {
+  // Nothing to do for the base class.
+}
 
-  // 1. Record control-flow-graph basic-block predecessors.
-  predecessors_.Add(current_block);
 
-  // 2. If the block has already been reached by the traversal, we are done.
-  if (preorder_number() >= 0) return;
+void StoreLocalComp::RecordAssignedVars(BitVector* assigned_vars) {
+  if (!local().is_captured()) {
+    int index = local().index();
+    // Parameters have positive indexes with the lowest index being 2.
+    // Locals and copied parameters have negative indexes with the lowest
+    // being -1.
+    if (index > 0) {
+      // Shift parameter indexes so that the lowest index is 0.
+      index -= 2;

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

Note that soon we will add a third word after ebp (upcoming Siva's change). Why
not allocate a BitMap that includes return address, ebp (and the new code
reference entry).  Index would remain unchanged if positive and will be computed
as below if negative.

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

Well, we either have to deal with the 'magic' extra frame elements here or else
when we allocate the bit vector.

Both of those will each happen one place in the code, so it seems better to not
track them if we don't care about them.  

Unfortunately, I can't find a canonical place with named constants for the frame
description (are they platform independent?  guaranteed so?), so that's why I
have the magic numbers in there for now. :(

What I really want is a 0-based variable index assigned to each frame-allocated
variable (e.g., one that can be used for printing and doesn't need to know the
size of the frame to be computed every time), but it turns out it's not entirely
simple to make the scopes code do that because we sometimes whack variables in
to the frame after scope analysis.

[srdjan, 2012/05/15 22:05:32]

Can we put intelligence into LocalVariable? If you do not like any alternatives,
leave the code here.

Check a new constant in ParsedFunction in Siva's change:

https://chromiumcodereview.appspot.com/10375059/diff/13001/vm/parser.h

+    } else {
+      // Store local and copied parameters backward from the end of the bit
+      // vector.
+      index = assigned_vars->length() + index;  // Index is negative.
+    }
+    assigned_vars->Add(index);
+  }
+}
 
-  // 3. The last entry in the preorder array is the spanning-tree parent.
-  intptr_t parent_number = preorder->length() - 1;
-  parent->Add(parent_number);
 
-  // 4. Assign preorder number and add the block entry to the list.
-  set_preorder_number(parent_number + 1);
-  preorder->Add(this);
-  // The preorder and parent arrays are both indexed by preorder block
-  // number, so they should stay in lockstep.
-  ASSERT(preorder->length() == parent->length());
+void Instruction::RecordAssignedVars(BitVector* assigned_vars) {
+  // Nothing to do for the base class.
+}
 
-  // 5. Iterate straight-line successors until a branch instruction or
-  // another basic block entry instruction, and visit that instruction.
-  ASSERT(successor_ != NULL);
-  Instruction* next = successor_;
-  while ((next != NULL) && !next->IsBlockEntry() && !next->IsBranch()) {
-    set_last_instruction(next);
-    next = next->StraightLineSuccessor();
-  }
-  if (next != NULL) {
-    next->DiscoverBlocks(this, preorder, postorder, parent);
-  }
 
-  // 6. Assign postorder number and add the block entry to the list.
-  set_postorder_number(postorder->length());
-  postorder->Add(this);
+void DoInstr::RecordAssignedVars(BitVector* assigned_vars) {
+  computation()->RecordAssignedVars(assigned_vars);
 }
 
 
-void TargetEntryInstr::DiscoverBlocks(
+void BindInstr::RecordAssignedVars(BitVector* assigned_vars) {
+  computation()->RecordAssignedVars(assigned_vars);
+}
+
+
+// ==== Postorder graph traversal.
+void BlockEntryInstr::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) {
+  // The global graph entry is a TargetEntryInstr, so we can assume
+  // current_block is non-null and preorder array is non-empty.
+  ASSERT(!IsJoinEntry() || (current_block != NULL));
+  ASSERT(!IsJoinEntry() || !preorder->is_empty());
+
   // 1. Record control-flow-graph basic-block predecessors.
-  ASSERT(predecessor_ == NULL);
-  predecessor_ = current_block;  // Might be NULL (for the graph entry).
+  AddPredecessor(current_block);
 
-  // 2. There is a single predecessor, so we should only reach this block once.
-  ASSERT(preorder_number() == -1);
+  // 2. If the block has already been reached by the traversal, we are
+  // done.  Blocks with a single predecessor cannot have been reached
+  // before.
+  ASSERT(!IsTargetEntry() || (preorder_number() == -1));
+  if (preorder_number() >= 0) return;
 
   // 3. The last entry in the preorder array is the spanning-tree parent.
-  // The global graph entry has no parent, indicated by -1.
   intptr_t parent_number = preorder->length() - 1;
   parent->Add(parent_number);
 
   // 4. Assign preorder number and add the block entry to the list.
+  // Allocate an empty set of assigned variables for the block.
   set_preorder_number(parent_number + 1);
   preorder->Add(this);
-  // The preorder and parent arrays are indexed by preorder block number, so
-  // they should stay in lockstep.
+  BitVector* vars = (variable_count == 0)
+      ? NULL
+      : new BitVector(variable_count, Isolate::Current()->current_zone());
+  assigned_vars->Add(vars);
+  // The preorder, parent, and assigned_vars arrays are all indexed by
+  // preorder block number, so they should stay in lockstep.
   ASSERT(preorder->length() == parent->length());
+  ASSERT(preorder->length() == assigned_vars->length());
 
   // 5. Iterate straight-line successors until a branch instruction or
   // another basic block entry instruction, and visit that instruction.
-  ASSERT(successor_ != NULL);
-  Instruction* next = successor_;
-  while ((next != NULL) && !next->IsBlockEntry() && !next->IsBranch()) {
-    set_last_instruction(next);
-    next = next->StraightLineSuccessor();
+  ASSERT(StraightLineSuccessor() != NULL);
+  Instruction* next = StraightLineSuccessor();
+  if (next->IsBlockEntry()) {
+    set_last_instruction(this);
+  } else {
+    while ((next != NULL) && !next->IsBlockEntry() && !next->IsBranch()) {
+      next->RecordAssignedVars(assigned_vars->Last());

[Florian Schneider, 2012/05/11 13:19:37]

assigned_vars->Last() == vars

The one that's just been added in line 269. Maybe just use vars here instead.

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

Well spotted.  Done.

+      set_last_instruction(next);
+      next = next->StraightLineSuccessor();
+    }
   }
   if (next != NULL) {
-    next->DiscoverBlocks(this, preorder, postorder, parent);
+    next->DiscoverBlocks(this, preorder, postorder, parent, assigned_vars,
+                         variable_count);
   }
 
   // 6. Assign postorder number and add the block entry to the list.
@@ -284,15 +300,19 @@ void BranchInstr::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) {
   current_block->set_last_instruction(this);
   // Visit the false successor before the true successor so they appear in
   // true/false order in reverse postorder used as the block ordering in the
   // nonoptimizing compiler.
   ASSERT(true_successor_ != NULL);
   ASSERT(false_successor_ != NULL);
-  false_successor_->DiscoverBlocks(current_block, preorder, postorder, parent);
-  true_successor_->DiscoverBlocks(current_block, preorder, postorder, parent);
+  false_successor_->DiscoverBlocks(current_block, preorder, postorder, parent,
+                                   assigned_vars, variable_count);
+  true_successor_->DiscoverBlocks(current_block, preorder, postorder, parent,
+                                  assigned_vars, variable_count);
 }