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