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

runtime/vm/flow_graph.cc

 // Copyright (c) 2012, 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.
 
 #include "vm/flow_graph.h"
 
 #include "vm/bit_vector.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/intermediate_language.h"
 #include "vm/longjump.h"
@@ skipping 46 matching lines @@
     Instruction* previous = entry;
     for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) {
       Instruction* current = it.Current();
       current->set_previous(previous);
       previous = current;
     }
   }
 }
 
 
+#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 {

[Kevin Millikin (Google), 2012/08/24 08:53:05]

While it's a noun, this isn't a very tangible name for the class.

I think it's fine to just make it a free function that iterates blocks (in any
order) and instructions in each block.

You could also consider replacing the CleanupInstruction function with virtual
functions on the instruction classes.  The mutually exclusive AsJoinEntry,
AsDefinition is a bit distracting.

+ public:
+  explicit DefUseCleanup(FlowGraph* flow_graph)
+      : FlowGraphVisitor(flow_graph->preorder()) { }
+  void CleanupInstruction(Instruction* instr) {

[Kevin Millikin (Google), 2012/08/24 08:53:05]

I like "ResetInstruction" slightly better.  Cleanup sounds a bit like something
that goes after an algorithm, not before.

+    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_input_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);

[Kevin Millikin (Google), 2012/08/24 08:53:05]

Here you could just use a virtual Reset function on values:

for (...) {
  instr->InputAt(i)->Reset();
}

+      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->input_use_list() == NULL);
+  ASSERT(defn->env_use_list() == NULL);
+  defn->set_input_use_list(NULL);
+  defn->set_env_use_list(NULL);
+}
+
+
+static void RecordInputUses(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->AddToInputUseList();
+  }
+}
+
+
+static void RecordEnvUses(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);
+    use->set_use_index(i);
+    use->AddToEnvUseList();
+  }
+}
+
+
+static void ComputeUseListsRecursive(BlockEntryInstr* block) {
+  // 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());
+    RecordInputUses(instr);
+    RecordEnvUses(instr);
+  }
+  // Compute recursively on dominated blocks.
+  for (intptr_t i = 0; i < block->dominated_blocks().length(); ++i) {
+    ComputeUseListsRecursive(block->dominated_blocks()[i]);
+  }
+  // Add phi uses on 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->AddToInputUseList();
+      }
+    }
+  }
+}
+
+
+void FlowGraph::ComputeUseLists() {
+#ifdef DEBUG
+  DefUseCleanup cleanup(this);
+  cleanup.VisitBlocks();
+#endif  // DEBUG
+  ComputeUseListsRecursive(graph_entry_);
+}
+
+
 void FlowGraph::ComputeSSA() {
   GrowableArray<BitVector*> dominance_frontier;
   ComputeDominators(&preorder_, &parent_, &dominance_frontier);
   InsertPhis(preorder_, assigned_vars_, dominance_frontier);
   GrowableArray<PhiInstr*> live_phis;
   // Rename uses to reference inserted phis where appropriate.
   // Collect phis that reach a non-environment use.
   Rename(&live_phis);
   // Propagate alive mark transitively from alive phis.
   MarkLivePhis(&live_phis);
@@ skipping 258 matching lines @@
       // Update expression stack.
       ASSERT(env->length() > variable_count());
 
       Definition* input_defn = env->Last();
       env->RemoveLast();
 
       BindInstr* as_bind = v->AsUse()->definition()->AsBind();
       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);
         current->SetInputAt(i, new UseVal(input_defn));
       }
     }
 
     // Drop pushed arguments for calls.
     for (intptr_t j = 0; j < current->ArgumentCount(); j++) {
       env->RemoveLast();
@@ skipping 20 matching lines @@
           index = load->local().BitIndexIn(non_copied_parameter_count_);
 
           PhiInstr* phi = (*env)[index]->AsPhi();
           if ((phi != NULL) && !phi->is_alive()) {
             phi->mark_alive();
             live_phis->Add(phi);
           }
         }
         // 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 {
           it.RemoveCurrentFromGraph();
         }
       } else {
         // Not a load or store.
         if (bind->is_used()) {
           // Assign fresh SSA temporary and update expression stack.
           bind->set_ssa_temp_index(alloc_ssa_temp_index());
@@ skipping 61 matching lines @@
   intptr_t len = OS::SNPrint(NULL, 0, kFormat, function_name, reason) + 1;
   char* chars = Isolate::Current()->current_zone()->Alloc<char>(len);
   OS::SNPrint(chars, len, kFormat, function_name, reason);
   const Error& error = Error::Handle(
       LanguageError::New(String::Handle(String::New(chars))));
   Isolate::Current()->long_jump_base()->Jump(1, error);
 }
 
 
 }  // namespace dart