Make use lists into doubly-linked lists.

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 89 matching lines @@
 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) {
     Value* use = instr->InputAt(i);
     use->set_instruction(NULL);
     use->set_use_index(-1);
+    use->set_previous_use(NULL);
     use->set_next_use(NULL);
   }
-  if (instr->env() != NULL) {
-    for (Environment::DeepIterator it(instr->env()); !it.Done(); it.Advance()) {
-      Value* use = it.CurrentValue();
-      use->set_instruction(NULL);
-      use->set_use_index(-1);
-      use->set_next_use(NULL);
-    }
+  for (Environment::DeepIterator it(instr->env()); !it.Done(); it.Advance()) {
+    Value* use = it.CurrentValue();
+    use->set_instruction(NULL);
+    use->set_use_index(-1);
+    use->set_previous_use(NULL);
+    use->set_next_use(NULL);
   }
 }
 
 
 bool FlowGraph::ResetUseLists() {
   // Reset initial definitions.
   for (intptr_t i = 0; i < graph_entry_->initial_definitions()->length(); ++i) {
     ResetUseListsInInstruction((*graph_entry_->initial_definitions())[i]);
   }
 
@@ skipping 28 matching lines @@
     intptr_t use_index = 0;
     for (Environment::DeepIterator it(instr->env()); !it.Done(); it.Advance()) {
       Value* use = it.CurrentValue();
       ASSERT(use->use_index() == use_index++);
       ASSERT(!FLAG_verify_compiler ||
              (1 == MembershipCount(use, use->definition()->env_use_list())));
     }
   }
   Definition* defn = instr->AsDefinition();
   if (defn != NULL) {
-    for (Value* use = defn->input_use_list();
-         use != NULL;
-         use = use->next_use()) {
-      ASSERT(defn == use->definition());
-      ASSERT(use == use->instruction()->InputAt(use->use_index()));
+    Value* prev = NULL;
+    Value* curr = defn->input_use_list();
+    while (curr != NULL) {
+      ASSERT(prev == curr->previous_use());
+      ASSERT(defn == curr->definition());
+      ASSERT(curr == curr->instruction()->InputAt(curr->use_index()));
+      prev = curr;
+      curr = curr->next_use();
     }
-    for (Value* use = defn->env_use_list();
-         use != NULL;
-         use = use->next_use()) {
-      ASSERT(defn == use->definition());
-      ASSERT(use ==
-             use->instruction()->env()->ValueAtUseIndex(use->use_index()));
+
+    prev = NULL;
+    curr = defn->env_use_list();
+    while (curr != NULL) {
+      ASSERT(prev == curr->previous_use());
+      ASSERT(defn == curr->definition());
+      ASSERT(curr ==
+             curr->instruction()->env()->ValueAtUseIndex(curr->use_index()));
+      prev = curr;
+      curr = curr->next_use();
     }
   }
 }
 
 
 bool FlowGraph::ValidateUseLists() {
   // Validate initial definitions.
   for (intptr_t i = 0; i < graph_entry_->initial_definitions()->length(); ++i) {
     ValidateUseListsInInstruction((*graph_entry_->initial_definitions())[i]);
   }
@@ skipping 24 matching lines @@
   defn->set_env_use_list(NULL);
 }
 
 
 static void RecordInputUses(Instruction* instr) {
   ASSERT(instr != NULL);
   for (intptr_t i = 0; i < instr->InputCount(); ++i) {
     Value* use = instr->InputAt(i);
     ASSERT(use->instruction() == NULL);
     ASSERT(use->use_index() == -1);
+    ASSERT(use->previous_use() == NULL);
     ASSERT(use->next_use() == NULL);
     DEBUG_ASSERT(!FLAG_verify_compiler ||
         (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;
   intptr_t use_index = 0;
   for (Environment::DeepIterator it(instr->env()); !it.Done(); it.Advance()) {
     Value* use = it.CurrentValue();
     ASSERT(use->instruction() == NULL);
     ASSERT(use->use_index() == -1);
+    ASSERT(use->previous_use() == NULL);
     ASSERT(use->next_use() == NULL);
     DEBUG_ASSERT(!FLAG_verify_compiler ||
         (0 == MembershipCount(use, use->definition()->env_use_list())));
     use->set_instruction(instr);
     use->set_use_index(use_index++);
     use->AddToEnvUseList();
   }
 }
 
 
@@ skipping 24 matching lines @@
         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;
         Value* use = phi->InputAt(pred_index);
         ASSERT(use->instruction() == NULL);
         ASSERT(use->use_index() == -1);
+        ASSERT(use->previous_use() == NULL);
         ASSERT(use->next_use() == NULL);
         DEBUG_ASSERT(!FLAG_verify_compiler ||
             (0 == MembershipCount(use, use->definition()->input_use_list())));
         use->set_instruction(phi);
         use->set_use_index(pred_index);
         use->AddToInputUseList();
       }
     }
   }
 }
@@ skipping 480 matching lines @@
          !it.Done();
          it.Advance()) {
       ++size;
     }
   }
   return size;
 }
 
 
 }  // namespace dart