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

runtime/vm/intermediate_language.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/intermediate_language.h"
 
 #include "vm/bit_vector.h"
 #include "vm/dart_entry.h"
 #include "vm/flow_graph_allocator.h"
 #include "vm/flow_graph_builder.h"
@@ skipping 55 matching lines @@
     // TODO(fschneider): Make sure ic_data are sorted to hit more cases.
     if (ic_data()->GetReceiverClassIdAt(i) !=
         other->ic_data()->GetReceiverClassIdAt(i)) {
       return false;
     }
   }
   return true;
 }
 
 
-UseVal::UseVal(Definition* definition)
-    : definition_(definition), next_use_(NULL), previous_use_(NULL) {
-  AddToUseList();
-}
-
-
-void UseVal::SetDefinition(Definition* definition) {
-  ASSERT(definition != NULL);
-  RemoveFromUseList();
-  definition_ = definition;
-  AddToUseList();
-}
-
-
 // Returns true if the value represents a constant.
 bool UseVal::BindsToConstant() const {
   BindInstr* bind = definition()->AsBind();
   if (bind == NULL) {
     return false;
   }
   return bind->computation()->AsMaterialize() != NULL;
 }
 
 
@@ skipping 14 matching lines @@
 const Object& UseVal::BoundConstant() const {
   ASSERT(BindsToConstant());
   BindInstr* bind = definition()->AsBind();
   ASSERT(bind != NULL);
   MaterializeComp* constant = bind->computation()->AsMaterialize();
   ASSERT(constant != NULL);
   return constant->constant_val()->value();
 }
 
 
-void UseVal::RemoveFromUseList() {
-  ASSERT(definition_ != NULL);
-  if (next_use_ != NULL) {
-    next_use_->previous_use_ = previous_use_;
-  }
-  if (previous_use_ != NULL) {
-    previous_use_->next_use_ = next_use_;
-  } else {
-    // This is the head of the list.
-    ASSERT(definition_->use_list() == this);
-    definition_->set_use_list(next_use_);
-  }
-  previous_use_ = next_use_ = NULL;
-  definition_ = NULL;
-}
-
-
-void UseVal::AddToUseList() {
-  ASSERT(next_use_ == NULL && previous_use_ == NULL && definition_ != NULL);
-  UseVal* head = definition_->use_list();
-  if (head != NULL) {
-    next_use_ = head;
-    head->previous_use_ = this;
-  }
-  definition_->set_use_list(this);
-}
-
-
 MethodRecognizer::Kind MethodRecognizer::RecognizeKind(
     const Function& function) {
   // Only core and math library methods can be recognized.
   const Library& core_lib = Library::Handle(Library::CoreLibrary());
   const Library& core_impl_lib = Library::Handle(Library::CoreImplLibrary());
   const Library& math_lib = Library::Handle(Library::MathLibrary());
   const Class& function_class = Class::Handle(function.Owner());
   if ((function_class.library() != core_lib.raw()) &&
       (function_class.library() != core_impl_lib.raw()) &&
       (function_class.library() != math_lib.raw())) {
@@ skipping 57 matching lines @@
   Instruction* prev_instr = previous();
   Instruction* next_instr = next();
   ASSERT(next_instr != NULL);
   ASSERT(!next_instr->IsBlockEntry());
   prev_instr->set_next(next_instr);
   next_instr->set_previous(prev_instr);
   // Reset successor and previous instruction to indicate
   // that the instruction is removed from the graph.
   set_previous(NULL);
   set_next(NULL);
-  ASSERT(!IsDefinition() || AsDefinition()->use_list() == NULL);
   return return_previous ? prev_instr : next_instr;
 }
 
 
 void BindInstr::InsertBefore(BindInstr* next) {
   ASSERT(previous_ == NULL);
   ASSERT(next_ == NULL);
   next_ = next;
   previous_ = next->previous_;
   next->previous_ = this;
@@ skipping 158 matching lines @@
   }
 }
 
 
 void Instruction::RecordAssignedVars(BitVector* assigned_vars,
                                      intptr_t fixed_parameter_count) {
   // Nothing to do for the base class.
 }
 
 
+void UseVal::AddToInputUseList() {
+  set_next_use(definition()->input_use_list());
+  definition()->set_input_use_list(this);
+}
+
+
+void UseVal::AddToEnvUseList() {
+  set_next_use(definition()->env_use_list());
+  definition()->set_env_use_list(this);
+}
+
+
 void Definition::ReplaceUsesWith(Definition* other) {
-  UseVal* head = use_list();
-  if (head == NULL) return;
-
-  UseVal* current = head;
-  while (current->next_use() != NULL) {
-    current->definition_ = other;
-    current = current->next_use();
+  ASSERT(other != NULL);
+  while (input_use_list_ != NULL) {
+    UseVal* current = input_use_list_;
+    input_use_list_ = input_use_list_->next_use();
+    current->set_definition(other);
+    current->AddToInputUseList();
   }
-  current->definition_ = other;
-
-  if (other->use_list() != NULL) {
-    current->next_use_ = other->use_list();
-    other->use_list()->previous_use_ = current;
+  while (env_use_list_ != NULL) {
+    UseVal* current = env_use_list_;
+    env_use_list_ = env_use_list_->next_use();
+    current->set_definition(other);
+    current->AddToEnvUseList();
   }
-  other->set_use_list(head);
-  set_use_list(NULL);
 }
 
 
+void Definition::ReplaceUsesWith(Value* value) {
+  ASSERT(value != NULL);
+  if (value->IsUse()) {
+    ReplaceUsesWith(value->AsUse()->definition());
+    return;
+  }
+  ASSERT(value->IsConstant());
+  while (input_use_list_ != NULL) {
+    Instruction* instr = input_use_list_->instruction();
+    instr->SetInputAt(input_use_list_->use_index(), value);
+    input_use_list_ = input_use_list_->next_use();
+  }
+  while (env_use_list_ != NULL) {
+    Environment* env = env_use_list_->instruction()->env();
+    ASSERT(env != NULL);
+    env->values()[env_use_list_->use_index()] = value;
+    env_use_list_ = env_use_list_->next_use();
+  }
+}
+
+
 bool Definition::SetPropagatedCid(intptr_t cid) {
   ASSERT(cid != kIllegalCid);
   if (propagated_cid_ == kIllegalCid) {
     // First setting, nothing has changed.
     propagated_cid_ = cid;
     return false;
   }
   bool has_changed = (propagated_cid_ != cid);
   propagated_cid_ = cid;
   return has_changed;
@@ skipping 640 matching lines @@
   const Object& right_constant = right_use->BoundConstant();
   Definition* left = left_use->definition();
   // TODO(fschneider): Handle other cases: e === false and e !== true/false.
   // Handles e === true.
   if ((kind() == Token::kEQ_STRICT) &&
       (right_constant.raw() == Bool::True()) &&
       (left_use->ResultCid() == kBoolCid)) {
     // Remove the constant from the graph.
     BindInstr* right = right_use->definition()->AsBind();
     if (right != NULL) {
-      right->set_use_list(NULL);
       right->RemoveFromGraph();
     }
     // Return left subexpression as the replacement for this instruction.
     return left;
   }
   return instr;
 }
 
 
 Definition* CheckSmiComp::TryReplace(BindInstr* instr) const {
@@ skipping 445 matching lines @@
                      ? UseDefinition(values()[i]->AsUse()->definition())
                      : val);
   }
   return copy;
 }
 
 
 #undef __
 
 }  // namespace dart