Change the Hydrogen representation of uses.

src/hydrogen-instructions.cc

 // Copyright 2011 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 246 matching lines @@
     result = HType::Boolean();
   } else if (value->IsJSObject()) {
     result = HType::JSObject();
   } else if (value->IsJSArray()) {
     result = HType::JSArray();
   }
   return result;
 }
 
 
-int HValue::LookupOperandIndex(int occurrence_index, HValue* op) {
-  for (int i = 0; i < OperandCount(); ++i) {
-    if (OperandAt(i) == op) {
-      if (occurrence_index == 0) return i;
-      --occurrence_index;
-    }
-  }
-  return -1;
-}
-
-
 bool HValue::IsDefinedAfter(HBasicBlock* other) const {
   return block()->block_id() > other->block_id();
 }
 
 
-bool HValue::UsesMultipleTimes(HValue* op) {
-  bool seen = false;
-  for (int i = 0; i < OperandCount(); ++i) {
-    if (OperandAt(i) == op) {
-      if (seen) return true;
-      seen = true;
-    }
-  }
-  return false;
+HUseIterator::HUseIterator(HUseListNode* head) : next_(head) {
+  Advance();
 }
 
 
+void HUseIterator::Advance() {
+  current_ = next_;
+  if (current_ != NULL) {
+    next_ = current_->tail();
+    value_ = current_->value();
+    index_ = current_->index();
+  }
+}
+
+
+int HValue::UseCount() const {
+  int count = 0;
+  for (HUseIterator it(uses()); !it.Done(); it.Advance()) ++count;
+  return count;
+}
+
+
+HUseListNode* HValue::RemoveUse(HValue* value, int index) {
+  HUseListNode* previous = NULL;
+  HUseListNode* current = use_list_;
+  while (current != NULL) {
+    if (current->value() == value && current->index() == index) {
+      if (previous == NULL) {
+        use_list_ = current->tail();
+      } else {
+        previous->set_tail(current->tail());
+      }
+      break;
+    }
+
+    previous = current;
+    current = current->tail();
+  }
+
+#ifdef DEBUG
+  // Do not reuse use list nodes in debug mode, zap them.
+  if (current != NULL) {
+    HUseListNode* temp =
+        new HUseListNode(current->value(), current->index(), NULL);
+    current->Zap();
+    current = temp;
+  }
+#endif
+  return current;
+}
+
+
 bool HValue::Equals(HValue* other) {
   if (other->opcode() != opcode()) return false;
   if (!other->representation().Equals(representation())) return false;
   if (!other->type_.Equals(type_)) return false;
   if (other->flags() != flags()) return false;
   if (OperandCount() != other->OperandCount()) return false;
   for (int i = 0; i < OperandCount(); ++i) {
     if (OperandAt(i)->id() != other->OperandAt(i)->id()) return false;
   }
   bool result = DataEquals(other);
@@ skipping 23 matching lines @@
 }
 
 
 void HValue::SetOperandAt(int index, HValue* value) {
   ASSERT(value == NULL || !value->representation().IsNone());
   RegisterUse(index, value);
   InternalSetOperandAt(index, value);
 }
 
 
-void HValue::ReplaceAndDelete(HValue* other) {
-  if (other != NULL) ReplaceValue(other);
-  Delete();
+void HValue::DeleteAndReplaceWith(HValue* other) {
+  // We replace all uses first, so Delete can assert that there are none.
+  if (other != NULL) ReplaceAllUsesWith(other);
+  ASSERT(HasNoUses());
+  ClearOperands();
+  DeleteFromGraph();
 }
 
 
-void HValue::ReplaceValue(HValue* other) {
-  for (int i = 0; i < uses_.length(); ++i) {
-    HValue* use = uses_[i];
-    ASSERT(!use->block()->IsStartBlock());
-    InternalReplaceAtUse(use, other);
-    other->uses_.Add(use);
+void HValue::ReplaceAllUsesWith(HValue* other) {
+  while (use_list_ != NULL) {
+    HUseListNode* list_node = use_list_;
+    HValue* value = list_node->value();
+    ASSERT(!value->block()->IsStartBlock());
+    value->InternalSetOperandAt(list_node->index(), other);
+    use_list_ = list_node->tail();
+    list_node->set_tail(other->use_list_);
+    other->use_list_ = list_node;
   }
-  uses_.Rewind(0);
 }
 
 
 void HValue::ClearOperands() {
   for (int i = 0; i < OperandCount(); ++i) {
     SetOperandAt(i, NULL);
   }
 }
 
-
-void HValue::Delete() {
-  ASSERT(HasNoUses());
-  ClearOperands();
-  DeleteFromGraph();
-}
-
-
-void HValue::ReplaceAtUse(HValue* use, HValue* other) {
-  for (int i = 0; i < use->OperandCount(); ++i) {
-    if (use->OperandAt(i) == this) {
-      use->SetOperandAt(i, other);
-    }
-  }
-}
-
-
-void HValue::ReplaceFirstAtUse(HValue* use, HValue* other, Representation r) {
-  for (int i = 0; i < use->OperandCount(); ++i) {
-    if (use->RequiredInputRepresentation(i).Equals(r) &&
-        use->OperandAt(i) == this) {
-      use->SetOperandAt(i, other);
-      return;
-    }
-  }
-}
-
-
-void HValue::InternalReplaceAtUse(HValue* use, HValue* other) {
-  for (int i = 0; i < use->OperandCount(); ++i) {
-    if (use->OperandAt(i) == this) {
-      // Call internal method that does not update use lists. The caller is
-      // responsible for doing so.
-      use->InternalSetOperandAt(i, other);
-    }
-  }
-}
-
 
 void HValue::SetBlock(HBasicBlock* block) {
   ASSERT(block_ == NULL || block == NULL);
   block_ = block;
   if (id_ == kNoNumber && block != NULL) {
     id_ = block->graph()->GetNextValueID(this);
   }
 }
 
 
@@ skipping 11 matching lines @@
   HType type = CalculateInferredType();
   bool result = (!type.Equals(type_));
   type_ = type;
   return result;
 }
 
 
 void HValue::RegisterUse(int index, HValue* new_value) {
   HValue* old_value = OperandAt(index);
   if (old_value == new_value) return;
-  if (old_value != NULL) old_value->uses_.RemoveElement(this);
+
+  HUseListNode* removed = NULL;
+  if (old_value != NULL) {
+    removed = old_value->RemoveUse(this, index);
+  }
+
   if (new_value != NULL) {
-    new_value->uses_.Add(this);
+#ifdef DEBUG
+    // Never reuse list nodes in debug builds.
+    removed = NULL;
+#endif
+    if (removed == NULL) {
+      new_value->use_list_ = new HUseListNode(this, index, new_value->use_list_);
+    } else {
+      removed->set_tail(new_value->use_list_);
+      new_value->use_list_ = removed;
+    }
   }
 }
 
 
 void HValue::AddNewRange(Range* r) {
   if (!HasRange()) ComputeInitialRange();
   if (!HasRange()) range_ = new Range();
   ASSERT(HasRange());
   r->StackUpon(range_);
   range_ = r;
@@ skipping 476 matching lines @@
 
 void HPhi::PrintTo(StringStream* stream) {
   stream->Add("[");
   for (int i = 0; i < OperandCount(); ++i) {
     HValue* value = OperandAt(i);
     stream->Add(" ");
     value->PrintNameTo(stream);
     stream->Add(" ");
   }
   stream->Add(" uses%d_%di_%dd_%dt]",
-              uses()->length(),
+              UseCount(),
               int32_non_phi_uses() + int32_indirect_uses(),
               double_non_phi_uses() + double_indirect_uses(),
               tagged_non_phi_uses() + tagged_indirect_uses());
 }
 
 
 void HPhi::AddInput(HValue* value) {
   inputs_.Add(NULL);
   SetOperandAt(OperandCount() - 1, value);
   // Mark phis that may have 'arguments' directly or indirectly as an operand.
   if (!CheckFlag(kIsArguments) && value->CheckFlag(kIsArguments)) {
     SetFlag(kIsArguments);
   }
 }
 
 
 bool HPhi::HasRealUses() {
-  for (int i = 0; i < uses()->length(); i++) {
-    if (!uses()->at(i)->IsPhi()) return true;
+  for (HUseIterator it(uses()); !it.Done(); it.Advance()) {
+    if (!it.value()->IsPhi()) return true;
   }
   return false;
 }
 
 
 HValue* HPhi::GetRedundantReplacement() {
   HValue* candidate = NULL;
   int count = OperandCount();
   int position = 0;
   while (position < count && candidate == NULL) {
@@ skipping 12 matching lines @@
 void HPhi::DeleteFromGraph() {
   ASSERT(block() != NULL);
   block()->RemovePhi(this);
   ASSERT(block() == NULL);
 }
 
 
 void HPhi::InitRealUses(int phi_id) {
   // Initialize real uses.
   phi_id_ = phi_id;
-  for (int j = 0; j < uses()->length(); j++) {
-    HValue* use = uses()->at(j);
-    if (!use->IsPhi()) {
-      int index = use->LookupOperandIndex(0, this);
-      Representation req_rep = use->RequiredInputRepresentation(index);
-      non_phi_uses_[req_rep.kind()]++;
+  for (HUseIterator it(uses()); !it.Done(); it.Advance()) {
+    HValue* value = it.value();
+    if (!value->IsPhi()) {
+      Representation rep = value->RequiredInputRepresentation(it.index());
+      ++non_phi_uses_[rep.kind()];
     }
   }
 }
 
 
 void HPhi::AddNonPhiUsesFrom(HPhi* other) {
   for (int i = 0; i < Representation::kNumRepresentations; i++) {
     indirect_uses_[i] += other->non_phi_uses_[i];
   }
 }
@@ skipping 660 matching lines @@
 
 
 void HCheckPrototypeMaps::Verify() {
   HInstruction::Verify();
   ASSERT(HasNoUses());
 }
 
 #endif
 
 } }  // namespace v8::internal