Fix an N^2 issue handling constant resolution due to RAUW in large arrays

this speeds up the bcreader from 6.67s to 0.12s on a testcase Daniel 
provided.  rdar://6158117



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

1 files changed, 31 insertions, 5 deletions

diff --git a/lib/Bitcode/Reader/BitcodeReader.h b/lib/Bitcode/Reader/BitcodeReader.h
index 9f62efec29..7bd05cfd2d 100644
--- a/lib/Bitcode/Reader/BitcodeReader.h
+++ b/lib/Bitcode/Reader/BitcodeReader.h
@@ -32,9 +32,22 @@ namespace llvm {
 
 class BitcodeReaderValueList : public User {
   unsigned Capacity;
+  
+  /// ResolveConstants - As we resolve forward-referenced constants, we add
+  /// information about them to this vector.  This allows us to resolve them in
+  /// bulk instead of resolving each reference at a time.  See the code in
+  /// ResolveConstantForwardRefs for more information about this.
+  ///
+  /// The key of this vector is the placeholder constant, the value is the slot
+  /// number that holds the resolved value.
+  typedef std::vector<std::pair<Constant*, unsigned> > ResolveConstantsTy;
+  ResolveConstantsTy ResolveConstants;
 public:
   BitcodeReaderValueList() : User(Type::VoidTy, Value::ArgumentVal, 0, 0)
                            , Capacity(0) {}
+  ~BitcodeReaderValueList() {
+    assert(ResolveConstants.empty() && "Constants not resolved?");
+  }
 
   /// Provide fast operand accessors
   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
@@ -50,6 +63,7 @@ public:
   }
   
   void clear() {
+    assert(ResolveConstants.empty() && "Constants not resolved?");
     if (OperandList) dropHungoffUses(OperandList);
     Capacity = 0;
   }
@@ -73,15 +87,26 @@ public:
     if (Idx == size()) {
       push_back(V);
     } else if (Value *OldV = getOperand(Idx)) {
-      // If there was a forward reference to this value, replace it.
-      setOperand(Idx, V);
-      OldV->replaceAllUsesWith(V);
-      delete OldV;
+      // Handle constants and non-constants (e.g. instrs) differently for
+      // efficiency.
+      if (Constant *PHC = dyn_cast<Constant>(OldV)) {
+        ResolveConstants.push_back(std::make_pair(PHC, Idx));
+        setOperand(Idx, V);
+      } else {
+        // If there was a forward reference to this value, replace it.
+        setOperand(Idx, V);
+        OldV->replaceAllUsesWith(V);
+        delete OldV;
+      }
     } else {
       initVal(Idx, V);
     }
   }
   
+  /// ResolveConstantForwardRefs - Once all constants are read, this method bulk
+  /// resolves any forward references.
+  void ResolveConstantForwardRefs();
+  
 private:
   void initVal(unsigned Idx, Value *V) {
     if (Idx >= size()) {
@@ -94,7 +119,8 @@ private:
 };
 
 template <>
-struct OperandTraits<BitcodeReaderValueList> : HungoffOperandTraits</*16 FIXME*/> {
+struct OperandTraits<BitcodeReaderValueList>
+  : HungoffOperandTraits</*16 FIXME*/> {
 };
 
 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(BitcodeReaderValueList, Value)