Change the Hydrogen representation of uses.

src/hydrogen-instructions.h

 // 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 385 matching lines @@
 
   // Make sure type fits in int16.
   STATIC_ASSERT(kUninitialized < (1 << (2 * kBitsPerByte)));
 
   explicit HType(Type t) : type_(t) { }
 
   int16_t type_;
 };
 
 
+class HUseListNode: public ZoneObject {
+ public:
+  HUseListNode(HValue* value, int index, HUseListNode* tail)
+      : tail_(tail), value_(value), index_(index) {
+  }
+
+  HUseListNode* tail() const { return tail_; }
+  HValue* value() const { return value_; }
+  int index() const { return index_; }
+
+  void set_tail(HUseListNode* list) { tail_ = list; }
+
+#ifdef DEBUG
+  void Zap() {
+    tail_ = reinterpret_cast<HUseListNode*>(1);
+    value_ = NULL;
+    index_ = -1;
+  }
+#endif
+
+ private:
+  HUseListNode* tail_;
+  HValue* value_;
+  int index_;
+};
+
+
+// We reuse use list nodes behind the scenes as uses are added and deleted.
+// This class is the safe way to iterate uses while deleting them.
+class HUseIterator BASE_EMBEDDED {
+ public:
+  bool Done() { return current_ == NULL; }
+  void Advance();
+
+  HValue* value() {
+    ASSERT(!Done());
+    return value_;
+  }
+
+  int index() {
+    ASSERT(!Done());
+    return index_;
+  }
+
+ private:
+  explicit HUseIterator(HUseListNode* head);
+
+  HUseListNode* current_;
+  HUseListNode* next_;
+  HValue* value_;
+  int index_;
+
+  friend class HValue;
+};
+
+
 class HValue: public ZoneObject {
  public:
   static const int kNoNumber = -1;
 
   // There must be one corresponding kDepends flag for every kChanges flag and
   // the order of the kChanges flags must be exactly the same as of the kDepends
   // flags.
   enum Flag {
     // Declare global value numbering flags.
   #define DECLARE_DO(type) kChanges##type, kDependsOn##type,
@@ skipping 50 matching lines @@
 
   // Declare virtual predicates for abstract HInstruction or HValue
   #define DECLARE_PREDICATE(type) \
     virtual bool Is##type() const { return false; }
     HYDROGEN_ABSTRACT_INSTRUCTION_LIST(DECLARE_PREDICATE)
   #undef DECLARE_PREDICATE
 
   HValue() : block_(NULL),
              id_(kNoNumber),
              type_(HType::Tagged()),
+             use_list_(NULL),
              range_(NULL),
              flags_(0) {}
   virtual ~HValue() {}
 
   HBasicBlock* block() const { return block_; }
   void SetBlock(HBasicBlock* block);
 
   int id() const { return id_; }
   void set_id(int id) { id_ = id; }
 
-  SmallPointerList<HValue>* uses() { return &uses_; }
+  HUseIterator uses() const { return HUseIterator(use_list_); }
 
   virtual bool EmitAtUses() { return false; }
   Representation representation() const { return representation_; }
   void ChangeRepresentation(Representation r) {
     // Representation was already set and is allowed to be changed.
     ASSERT(!representation_.IsNone());
     ASSERT(!r.IsNone());
     ASSERT(CheckFlag(kFlexibleRepresentation));
     RepresentationChanged(r);
     representation_ = r;
   }
 
   HType type() const { return type_; }
   void set_type(HType type) {
-    ASSERT(uses_.length() == 0);
+    ASSERT(HasNoUses());
     type_ = type;
   }
 
   // An operation needs to override this function iff:
   //   1) it can produce an int32 output.
   //   2) the true value of its output can potentially be minus zero.
   // The implementation must set a flag so that it bails out in the case where
   // it would otherwise output what should be a minus zero as an int32 zero.
   // If the operation also exists in a form that takes int32 and outputs int32
   // then the operation should return its input value so that we can propagate
   // back.  There are two operations that need to propagate back to more than
   // one input.  They are phi and binary add.  They always return NULL and
   // expect the caller to take care of things.
   virtual HValue* EnsureAndPropagateNotMinusZero(BitVector* visited) {
     visited->Add(id());
     return NULL;
   }
 
   bool IsDefinedAfter(HBasicBlock* other) const;
 
   // Operands.
   virtual int OperandCount() = 0;
   virtual HValue* OperandAt(int index) = 0;
   void SetOperandAt(int index, HValue* value);
 
-  int LookupOperandIndex(int occurrence_index, HValue* op);
-  bool UsesMultipleTimes(HValue* op);
-
-  void ReplaceAndDelete(HValue* other);
-  void ReplaceValue(HValue* other);
-  void ReplaceAtUse(HValue* use, HValue* other);
-  void ReplaceFirstAtUse(HValue* use, HValue* other, Representation r);
-  bool HasNoUses() const { return uses_.is_empty(); }
+  void DeleteAndReplaceWith(HValue* other);
+  bool HasNoUses() const { return use_list_ == NULL; }
+  bool HasMultipleUses() const {
+    return use_list_ != NULL && use_list_->tail() != NULL;
+  }
+  int UseCount() const;
   void ClearOperands();
-  void Delete();
 
   int flags() const { return flags_; }
   void SetFlag(Flag f) { flags_ |= (1 << f); }
   void ClearFlag(Flag f) { flags_ &= ~(1 << f); }
   bool CheckFlag(Flag f) const { return (flags_ & (1 << f)) != 0; }
 
   void SetAllSideEffects() { flags_ |= AllSideEffects(); }
   void ClearAllSideEffects() { flags_ &= ~AllSideEffects(); }
   bool HasSideEffects() const { return (flags_ & AllSideEffects()) != 0; }
 
@@ skipping 57 matching lines @@
     ASSERT(representation_.IsNone() && !r.IsNone());
     representation_ = r;
   }
 
  private:
   // A flag mask to mark an instruction as having arbitrary side effects.
   static int AllSideEffects() {
     return ChangesFlagsMask() & ~(1 << kChangesOsrEntries);
   }
 
-  void InternalReplaceAtUse(HValue* use, HValue* other);
+  // Remove the matching use from the use list if present.  Returns the
+  // removed list node or NULL.
+  HUseListNode* RemoveUse(HValue* value, int index);

[danno, 2011/04/20 04:25:12]

How about wrapping HValue* and int in a HUse struct/class?

+
+  void ReplaceAllUsesWith(HValue* other);
+
   void RegisterUse(int index, HValue* new_value);
 
   HBasicBlock* block_;
 
   // The id of this instruction in the hydrogen graph, assigned when first
   // added to the graph. Reflects creation order.
   int id_;
 
   Representation representation_;
   HType type_;
-  SmallPointerList<HValue> uses_;
+  HUseListNode* use_list_;
   Range* range_;
   int flags_;
 
   DISALLOW_COPY_AND_ASSIGN(HValue);
 };
 
 
 class HInstruction: public HValue {
  public:
   HInstruction* next() const { return next_; }
@@ skipping 1614 matching lines @@
   HCompare(HValue* left, HValue* right, Token::Value token)
       : HBinaryOperation(left, right), token_(token) {
     ASSERT(Token::IsCompareOp(token));
     set_representation(Representation::Tagged());
     SetAllSideEffects();
   }
 
   void SetInputRepresentation(Representation r);
 
   virtual bool EmitAtUses() {
-    return !HasSideEffects() && (uses()->length() <= 1);
+    return !HasSideEffects() && !HasMultipleUses();
   }
 
   virtual Representation RequiredInputRepresentation(int index) const {
     return input_representation_;
   }
   Representation GetInputRepresentation() const {
     return input_representation_;
   }
   Token::Value token() const { return token_; }
   virtual void PrintDataTo(StringStream* stream);
@@ skipping 21 matching lines @@
 class HCompareJSObjectEq: public HBinaryOperation {
  public:
   HCompareJSObjectEq(HValue* left, HValue* right)
       : HBinaryOperation(left, right) {
     set_representation(Representation::Tagged());
     SetFlag(kUseGVN);
     SetFlag(kDependsOnMaps);
   }
 
   virtual bool EmitAtUses() {
-    return !HasSideEffects() && (uses()->length() <= 1);
+    return !HasSideEffects() && !HasMultipleUses();
   }
 
   virtual Representation RequiredInputRepresentation(int index) const {
     return Representation::Tagged();
   }
   virtual HType CalculateInferredType();
 
   DECLARE_CONCRETE_INSTRUCTION(CompareJSObjectEq)
 
  protected:
   virtual bool DataEquals(HValue* other) { return true; }
 };
 
 
 class HUnaryPredicate: public HUnaryOperation {
  public:
   explicit HUnaryPredicate(HValue* value) : HUnaryOperation(value) {
     set_representation(Representation::Tagged());
     SetFlag(kUseGVN);
   }
 
   virtual bool EmitAtUses() {
-    return !HasSideEffects() && (uses()->length() <= 1);
+    return !HasSideEffects() && !HasMultipleUses();
   }
 
   virtual Representation RequiredInputRepresentation(int index) const {
     return Representation::Tagged();
   }
   virtual HType CalculateInferredType();
 };
 
 
 class HIsNull: public HUnaryPredicate {
@@ skipping 39 matching lines @@
 
 
 class HIsConstructCall: public HTemplateInstruction<0> {
  public:
   HIsConstructCall() {
     set_representation(Representation::Tagged());
     SetFlag(kUseGVN);
   }
 
   virtual bool EmitAtUses() {
-    return !HasSideEffects() && (uses()->length() <= 1);
+    return !HasSideEffects() && !HasMultipleUses();
   }
 
   virtual Representation RequiredInputRepresentation(int index) const {
     return Representation::None();
   }
 
   DECLARE_CONCRETE_INSTRUCTION(IsConstructCall)
 
  protected:
   virtual bool DataEquals(HValue* other) { return true; }
@@ skipping 101 matching lines @@
     SetOperandAt(2, right);
     set_representation(Representation::Tagged());
     SetAllSideEffects();
   }
 
   HValue* context() { return OperandAt(0); }
   HValue* left() { return OperandAt(1); }
   HValue* right() { return OperandAt(2); }
 
   virtual bool EmitAtUses() {
-    return !HasSideEffects() && (uses()->length() <= 1);
+    return !HasSideEffects() && !HasMultipleUses();
   }
 
   virtual Representation RequiredInputRepresentation(int index) const {
     return Representation::Tagged();
   }
 
   virtual void PrintDataTo(StringStream* stream);
 
   DECLARE_CONCRETE_INSTRUCTION(InstanceOf)
 };
@@ skipping 1200 matching lines @@
   HValue* object() { return left(); }
   HValue* key() { return right(); }
 };
 
 #undef DECLARE_INSTRUCTION
 #undef DECLARE_CONCRETE_INSTRUCTION
 
 } }  // namespace v8::internal
 
 #endif  // V8_HYDROGEN_INSTRUCTIONS_H_