Compute the def-use list on-demand by walking the dominator tree.

runtime/vm/flow_graph.cc

Index: runtime/vm/flow_graph.cc
diff --git a/runtime/vm/flow_graph.cc b/runtime/vm/flow_graph.cc
index a8b3076e0d08dce663998aa5dabb4d7d130bf98b..1f1f26fea36af1597580c1899dc8addca1764dbe 100644
--- a/runtime/vm/flow_graph.cc
+++ b/runtime/vm/flow_graph.cc
@@ -64,6 +64,150 @@ void FlowGraph::DiscoverBlocks() {
 }
 
 
+#ifdef DEBUG
+// Helper class to check consistency of the use list construction.  Clears all
+// use-list data in one pass which is then used for assertions when building the
+// use lists.
+class DefUseCleanup : public FlowGraphVisitor {
+ public:
+  explicit DefUseCleanup(FlowGraph* flow_graph)
+      : FlowGraphVisitor(flow_graph->preorder()) { }
+  void CleanupInstruction(Instruction* instr) {
+    JoinEntryInstr* join = instr->AsJoinEntry();
+    if (join != NULL && join->phis() != NULL) {
+      for (intptr_t i = 0; i < join->phis()->length(); ++i) {
+        PhiInstr* phi = (*join->phis())[i];
+        if (phi != NULL) CleanupInstruction(phi);
+      }
+    }
+    Definition* defn = instr->AsDefinition();
+    if (defn != NULL) {
+      defn->set_instr_use_list(NULL);
+      defn->set_env_use_list(NULL);
+    }
+    for (intptr_t i = 0; i < instr->InputCount(); ++i) {
+      UseVal* use = instr->InputAt(i)->AsUse();
+      if (use == NULL) continue;
+      use->set_instruction(NULL);
+      use->set_use_index(-1);
+      use->set_next_use(NULL);
+    }
+    if (instr->env() != NULL) {
+      for (intptr_t i = 0; i < instr->env()->values().length(); ++i) {
+        UseVal* use = instr->env()->values()[i]->AsUse();
+        if (use == NULL) continue;
+        use->set_instruction(NULL);
+        use->set_use_index(-1);
+        use->set_next_use(NULL);
+      }
+    }
+  }
+#define DEFINE_VISIT(type)                                                     \
+  virtual void Visit##type(type##Instr* instr) { CleanupInstruction(instr); }
+  FOR_EACH_INSTRUCTION(DEFINE_VISIT)
+#undef DEFINE_VISIT
+};
+#endif  // DEBUG
+
+
+static void ClearUseLists(Definition* defn) {
+  ASSERT(defn != NULL);
+  ASSERT(defn->instr_use_list() == NULL);
+  ASSERT(defn->env_use_list() == NULL);
+  defn->set_instr_use_list(NULL);
+  defn->set_env_use_list(NULL);
+}
+
+
+static void ComputeInstructionUses(Instruction* instr) {
+  ASSERT(instr != NULL);
+  for (intptr_t i = 0; i < instr->InputCount(); ++i) {
+    UseVal* use = instr->InputAt(i)->AsUse();
+    if (use == NULL) continue;
+    ASSERT(use->instruction() == NULL);
+    ASSERT(use->use_index() == -1);
+    ASSERT(use->next_use() == NULL);
+    use->set_instruction(instr);
+    use->set_use_index(i);
+    use->set_next_use(use->definition()->instr_use_list());
+    use->definition()->set_instr_use_list(use);
+  }
+}
+
+
+static void ComputeEnvironmentUses(Instruction* instr) {
+  ASSERT(instr != NULL);
+  if (instr->env() == NULL) return;
+  for (intptr_t i = 0; i < instr->env()->values().length(); ++i) {
+    UseVal* use = instr->env()->values()[i]->AsUse();
+    if (use == NULL) continue;
+    ASSERT(use->instruction() == NULL);
+    ASSERT(use->use_index() == -1);
+    ASSERT(use->next_use() == NULL);
+    use->set_instruction(instr);

[Vyacheslav Egorov (Google), 2012/08/23 13:51:10]

This code for placing use into the list is duplicated in several places.
Consider refactoring it into a helper function.

[zerny-google, 2012/08/23 16:11:20]

Done. (Added AddToInputUse/AddToEnvUse on UseVal)

+    use->set_use_index(i);
+    use->set_next_use(use->definition()->env_use_list());
+    use->definition()->set_env_use_list(use);
+  }
+}
+
+
+static void ComputeUsesInBlock(BlockEntryInstr* block) {

[Kevin Millikin (Google), 2012/08/23 13:35:34]

Name is not quite right, because it computes uses for a whole (sub)tree. 
ComputeUsesRecursive?

[zerny-google, 2012/08/23 16:11:20]

Done.

+  // Clear phi definitions.
+  JoinEntryInstr* join = block->AsJoinEntry();
+  if (join != NULL && join->phis() != NULL) {
+    for (intptr_t i = 0; i < join->phis()->length(); ++i) {
+      PhiInstr* phi = (*join->phis())[i];
+      if (phi != NULL) ClearUseLists(phi);
+    }
+  }
+  // Compute uses on normal instructions.
+  for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
+    Instruction* instr = it.Current();
+    if (instr->IsDefinition()) ClearUseLists(instr->AsDefinition());
+    ComputeInstructionUses(instr);

[Kevin Millikin (Google), 2012/08/23 13:35:34]

Name is not quite right.  It sounds like it's computing the instruction uses for
'instr', but it's recording the input uses of instr.  RecordInputUsed(instr);
RecordEnvironmentUses(instr)?

[zerny-google, 2012/08/23 16:11:20]

Yes. Similar to this, instr_use has been replaced by input_use throughout now.

+    ComputeEnvironmentUses(instr);
+  }
+  // Compute recursively on dominated blocks.
+  for (intptr_t i = 0; i < block->dominated_blocks().length(); ++i) {
+    ComputeUsesInBlock(block->dominated_blocks()[i]);
+  }
+  // Add phi uses on back-edges.

[Kevin Millikin (Google), 2012/08/23 13:35:34]

Not just back edges, all successor edges.

+  if (block->last_instruction()->SuccessorCount() == 1 &&
+      block->last_instruction()->SuccessorAt(0)->IsJoinEntry()) {
+    JoinEntryInstr* join =
+        block->last_instruction()->SuccessorAt(0)->AsJoinEntry();
+    intptr_t pred_index = join->IndexOfPredecessor(block);
+    ASSERT(pred_index >= 0);
+    if (join->phis() != NULL) {
+      for (intptr_t i = 0; i < join->phis()->length(); ++i) {
+        PhiInstr* phi = (*join->phis())[i];
+        if (phi == NULL) continue;
+        UseVal* use = phi->InputAt(pred_index)->AsUse();
+        if (use == NULL) continue;
+        ASSERT(use->instruction() == NULL);
+        ASSERT(use->use_index() == -1);
+        ASSERT(use->next_use() == NULL);
+        use->set_instruction(phi);
+        use->set_use_index(pred_index);
+        use->set_next_use(use->definition()->instr_use_list());
+        use->definition()->set_instr_use_list(use);
+      }
+    }
+  }
+}
+
+
+bool FlowGraph::ComputeUseLists() {
+#ifdef DEBUG
+  DefUseCleanup cleanup(this);

[Kevin Millikin (Google), 2012/08/23 13:35:34]

I don't really like the verification.  It's a bit confusing, and we normally use
ASSERTs to indicate/check pre- and post-conditions (i.e., they should be true in
release builds but are just not checked).

I think we could probably just get rid of it.

[zerny-google, 2012/08/23 16:11:20]

I can pull this out, but if so, it is really hard to catch the error of
duplicating the instance of a Value. The effect of doing so is simply that the
instruction_/use_index_ are overwritten and we can end up missing a use when
replacing values.

What should we do?

+  cleanup.VisitBlocks();
+#endif  // DEBUG
+  ComputeUsesInBlock(graph_entry_);
+  return true;

[Vyacheslav Egorov (Google), 2012/08/23 13:51:10]

what is the reason to have return values which is always true?

+}
+
+
 void FlowGraph::ComputeSSA() {
   GrowableArray<BitVector*> dominance_frontier;
   ComputeDominators(&preorder_, &parent_, &dominance_frontier);
@@ -342,11 +486,7 @@ void FlowGraph::RenameRecursive(BlockEntryInstr* block_entry,
       if ((as_bind != NULL) &&
           (as_bind->computation()->IsLoadLocal() ||
            as_bind->computation()->IsStoreLocal())) {
-        // Assert exactly one use.
-        ASSERT(as_bind->use_list() == v);
-        ASSERT(as_bind->use_list()->next_use() == NULL);
-        // Remove the use, its definition and copy the environment value.
-        v->RemoveFromUseList();
+        // Remove the load/store from the graph.
         as_bind->RemoveFromGraph();
         // Assert we are not referencing nulls in the initial environment.
         ASSERT(input_defn->ssa_temp_index() != -1);
@@ -387,9 +527,6 @@ void FlowGraph::RenameRecursive(BlockEntryInstr* block_entry,
         }
         // Update expression stack or remove from graph.
         if (bind->is_used()) {
-          // Assert exactly one use.
-          ASSERT(bind->use_list() != NULL);
-          ASSERT(bind->use_list()->next_use() == NULL);
           env->Add((*env)[index]);
           // We remove load/store instructions when we find their use in 2a.
         } else {