Validate well-formedness of the use lists in debug mode.

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 47 matching lines @@
     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_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();
+// Debugging code to verify the construction of use lists.
+
+static intptr_t MembershipCount(UseVal* use, UseVal* list) {
+  intptr_t count = 0;
+  while (list != NULL) {
+    if (list == use) ++count;
+    list = list->next_use();
+  }
+  return count;
+}
+
+
+static void ResetUseListsInInstruction(Instruction* instr) {
+  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);
+    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);
     }
-    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);
+  }
+}
+
+
+bool FlowGraph::ResetUseLists() {
+  // Reset use lists of parameters in the start environment.

[Kevin Millikin (Google), 2012/08/27 12:11:12]

It's not just parameters, but all definitions, right?

+  for (intptr_t i = 0; i < graph_entry_->start_env()->values().length(); ++i) {
+    UseVal* env_use = graph_entry_->start_env()->values()[i]->AsUse();
+    if (env_use != NULL) ResetUseListsInInstruction(env_use->definition());
+  }
+  // Reset phis in join entries and the instructions in each block.
+  for (intptr_t i = 0; i < preorder_.length(); ++i) {
+    BlockEntryInstr* entry = preorder_[i];
+    JoinEntryInstr* join = entry->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) ResetUseListsInInstruction(phi);
       }
     }
+    for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) {
+      ResetUseListsInInstruction(it.Current());
+    }
   }
-#define DEFINE_VISIT(type)                                                     \
-  virtual void Visit##type(type##Instr* instr) { CleanupInstruction(instr); }
-  FOR_EACH_INSTRUCTION(DEFINE_VISIT)
-#undef DEFINE_VISIT
-};
+  return true;  // Return true so we can ASSERT the reset code.
+}
+
+
+static void ValidateUseListsInInstruction(Instruction* instr) {
+  ASSERT(instr != NULL);
+  ASSERT(!instr->IsJoinEntry());
+  for (intptr_t i = 0; i < instr->InputCount(); ++i) {
+    UseVal* use = instr->InputAt(i)->AsUse();
+    if (use == NULL) continue;
+    ASSERT(use->use_index() == i);
+    ASSERT(1 == MembershipCount(use, use->definition()->input_use_list()));
+  }
+  Environment* env = instr->env();
+  if (env != NULL) {
+    for (intptr_t i = 0; i < env->values().length(); ++i) {
+      UseVal* use = env->values()[i]->AsUse();
+      if (use == NULL) continue;
+      ASSERT(use->use_index() == i);
+      ASSERT(1 == MembershipCount(use, use->definition()->env_use_list()));
+    }
+  }
+  Definition* defn = instr->AsDefinition();
+  if (defn != NULL) {
+    for (UseVal* use = defn->input_use_list();
+         use != NULL;
+         use = use->next_use()) {
+      ASSERT(defn == use->definition());
+      ASSERT(use == use->instruction()->InputAt(use->use_index()));
+    }
+    for (UseVal* use = defn->env_use_list();
+         use != NULL;
+         use = use->next_use()) {
+      ASSERT(defn == use->definition());
+      ASSERT(use == use->instruction()->env()->values()[use->use_index()]);
+    }
+  }
+}
+
+
+bool FlowGraph::ValidateUseLists() {
+  // Validate parameters in the start environment.

[Kevin Millikin (Google), 2012/08/27 12:11:12]

All definitions.

+  for (intptr_t i = 0; i < graph_entry_->start_env()->values().length(); ++i) {
+    UseVal* env_use = graph_entry_->start_env()->values()[i]->AsUse();
+    if (env_use != NULL) ValidateUseListsInInstruction(env_use->definition());
+  }
+  // Validate phis in join entries and the instructions in each block.
+  for (intptr_t i = 0; i < preorder_.length(); ++i) {
+    BlockEntryInstr* entry = preorder_[i];
+    JoinEntryInstr* join = entry->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) ValidateUseListsInInstruction(phi);
+      }
+    }
+    for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) {
+      ValidateUseListsInInstruction(it.Current());
+    }
+  }
+  return true;  // Return true so we can ASSERT validation.
+}
 #endif  // DEBUG
 
 
 static void ClearUseLists(Definition* defn) {
   ASSERT(defn != NULL);
-  ASSERT(defn->input_use_list() == NULL);
-  ASSERT(defn->env_use_list() == NULL);
+  DEBUG_ASSERT(defn->input_use_list() == NULL);
+  DEBUG_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);
+    DEBUG_ASSERT(use->instruction() == NULL);
+    DEBUG_ASSERT(use->use_index() == -1);
+    DEBUG_ASSERT(use->next_use() == NULL);
+    DEBUG_ASSERT(0 == MembershipCount(use,
+                                      use->definition()->input_use_list()));
     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);
+    DEBUG_ASSERT(use->instruction() == NULL);
+    DEBUG_ASSERT(use->use_index() == -1);
+    DEBUG_ASSERT(use->next_use() == NULL);
+    DEBUG_ASSERT(0 == MembershipCount(use, use->definition()->env_use_list()));
     use->set_instruction(instr);
     use->set_use_index(i);
     use->AddToEnvUseList();
   }
 }
 
 
 static void ComputeUseListsRecursive(BlockEntryInstr* block) {
   // Clear phi definitions.
   JoinEntryInstr* join = block->AsJoinEntry();
@@ skipping 20 matching lines @@
     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);
+        DEBUG_ASSERT(use->instruction() == NULL);
+        DEBUG_ASSERT(use->use_index() == -1);
+        DEBUG_ASSERT(use->next_use() == NULL);
+        DEBUG_ASSERT(0 == MembershipCount(use,
+                                          use->definition()->input_use_list()));
         use->set_instruction(phi);
         use->set_use_index(pred_index);
         use->AddToInputUseList();
       }
     }
   }
 }
 
 
 void FlowGraph::ComputeUseLists() {
-#ifdef DEBUG
-  DefUseCleanup cleanup(this);
-  cleanup.VisitBlocks();
-#endif  // DEBUG
+  DEBUG_ASSERT(ResetUseLists());
   ComputeUseListsRecursive(graph_entry_);
+  DEBUG_ASSERT(ValidateUseLists());
 }
 
 
 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.
@@ skipping 383 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