Lazy removal of dead HValues in GVN from use lists.

src/hydrogen-instructions.cc

 // Copyright 2012 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 258 matching lines @@
   }
   return result;
 }
 
 
 bool HValue::IsDefinedAfter(HBasicBlock* other) const {
   return block()->block_id() > other->block_id();
 }
 
 
+HUseListNode* HUseListNode::tail() {
+  // Skip and remove dead items in the use list.
+  while (tail_ != NULL && tail_->value()->CheckFlag(HValue::kIsDead)) {
+    tail_ = tail_->tail_;
+  }
+  return tail_;
+}
+
+
 HUseIterator::HUseIterator(HUseListNode* head) : next_(head) {
   Advance();
 }
 
 
 void HUseIterator::Advance() {
   current_ = next_;
   if (current_ != NULL) {
     next_ = current_->tail();
     value_ = current_->value();
@@ skipping 78 matching lines @@
 void HValue::SetOperandAt(int index, HValue* value) {
   RegisterUse(index, value);
   InternalSetOperandAt(index, value);
 }
 
 
 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();
+  // Clearing the operands includes going through the use list of each operand
+  // to remove this HValue, which can be expensive.  Instead, we simply mark it
+  // as dead and remove it lazily from the operands' use lists.
+  SetFlag(kIsDead);
   DeleteFromGraph();
 }
 
 
 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;
   }
 }
 
 
 void HValue::ClearOperands() {

[fschneider, 2012/02/23 14:01:14]

Could you get rid of all uses of ClearOperands?

   for (int i = 0; i < OperandCount(); ++i) {
     SetOperandAt(i, NULL);
   }
 }
 
 
 void HValue::SetBlock(HBasicBlock* block) {
   ASSERT(block_ == NULL || block == NULL);
   block_ = block;
   if (id_ == kNoNumber && block != NULL) {
@@ skipping 1821 matching lines @@
 
 
 void HCheckPrototypeMaps::Verify() {
   HInstruction::Verify();
   ASSERT(HasNoUses());
 }
 
 #endif
 
 } }  // namespace v8::internal