Fix NASTY N^2 behavior that was causing the gzip benchmark to take forever to

assemble.  Now we scan the use-list from the back when removing users instead
of from the front.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4086 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 12 insertions, 6 deletions

diff --git a/lib/VMCore/Value.cpp b/lib/VMCore/Value.cpp
index 402171be36..efb0cdf8e1 100644
--- a/lib/VMCore/Value.cpp
+++ b/lib/VMCore/Value.cpp
@@ -77,12 +77,18 @@ void Value::refineAbstractType(const DerivedType *OldTy, const Type *NewTy) {
   Ty = NewTy;
 }
 
-void Value::killUse(User *i) {
-  if (i == 0) return;
-  use_iterator I = find(Uses.begin(), Uses.end(), i);
-
-  assert(I != Uses.end() && "Use not in uses list!!");
-  Uses.erase(I);
+void Value::killUse(User *U) {
+  if (U == 0) return;
+  unsigned i;
+
+  // Scan backwards through the uses list looking for the user.  We do this
+  // because vectors like to be accessed on the end.  This is incredibly
+  // important from a performance perspective.
+  for (i = Uses.size()-1; Uses[i] != U; --i)
+    /* empty */;
+
+  assert(i < Uses.size() && "Use not in uses list!!");
+  Uses.erase(Uses.begin()+i);
 }
 
 User *Value::use_remove(use_iterator &I) {