From 8eb10cef39c7ac99a8992e17f7a4941bfcbeef31 Mon Sep 17 00:00:00 2001
From: Chris Lattner <sabre@nondot.org>
Date: Thu, 9 Oct 2003 06:05:40 +0000
Subject: [PATCH] Eliminate the old LateResolveValues data structure, replacing
 it with a new, simpler, ForwardReferences data structure.  This is just the
 first simple replacement, subsequent changes will improve the code more.

This simple change improves the performance of loading a file from HDF5
(contributed by Bill) from 2.36s to 1.93s, a 22% improvement.  This
presumably has to do with the fact that we only create ONE placeholder for
a particular forward referenced values, and also may be because the data
structure is much simpler.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8979 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Bytecode/Reader/Reader.cpp        | 48 ++++++++++++++-------------
 lib/Bytecode/Reader/ReaderInternals.h |  4 +--
 2 files changed, 27 insertions(+), 25 deletions(-)

diff --git a/lib/Bytecode/Reader/Reader.cpp b/lib/Bytecode/Reader/Reader.cpp
index 66111dd93d0..714d813a685 100644
--- a/lib/Bytecode/Reader/Reader.cpp
+++ b/lib/Bytecode/Reader/Reader.cpp
@@ -128,8 +128,14 @@ Value *BytecodeParser::getValue(unsigned type, unsigned oNum, bool Create) {
 
   if (!Create) return 0;  // Do not create a placeholder?
 
+  std::pair<unsigned,unsigned> KeyValue(type, oNum);
+  std::map<std::pair<unsigned,unsigned>, Value*>::iterator I = 
+    ForwardReferences.lower_bound(KeyValue);
+  if (I != ForwardReferences.end() && I->first == KeyValue)
+    return I->second;   // We have already created this placeholder
+
   Value *Val = new ValPHolder(getType(type), oNum);
-  if (insertValue(Val, LateResolveValues) == -1) return 0;
+  ForwardReferences.insert(I, std::make_pair(KeyValue, Val));
   return Val;
 }
 
@@ -377,31 +383,27 @@ void BytecodeParser::materializeFunction(Function* F) {
   ParsedBasicBlocks.clear();
 
 
-  // Check for unresolvable references
-  while (!LateResolveValues.empty()) {
-    ValueList &VL = *LateResolveValues.back();
-    LateResolveValues.pop_back();    
-
-    while (!VL.empty()) {
-      Value *V = VL.back();
-      unsigned IDNumber = getValueIDNumberFromPlaceHolder(V);
-      VL.pop_back();
+  // Resolve forward references
+  while (!ForwardReferences.empty()) {
+    std::map<std::pair<unsigned,unsigned>, Value*>::iterator I = ForwardReferences.begin();
+    unsigned type = I->first.first;
+    unsigned Slot = I->first.second;
+    Value *PlaceHolder = I->second;
+    ForwardReferences.erase(I);
 
-      Value *NewVal = getValue(V->getType(), IDNumber, false);
-      if (NewVal == 0)
-        throw std::string("Unresolvable reference found: <" +
-                          V->getType()->getDescription() + ">:" + 
-                          utostr(IDNumber) + ".");
+    Value *NewVal = getValue(type, Slot, false);
+    if (NewVal == 0)
+      throw std::string("Unresolvable reference found: <" +
+                        PlaceHolder->getType()->getDescription() + ">:" + 
+                        utostr(Slot) + ".");
 
-      // Fixup all of the uses of this placeholder def...
-      V->replaceAllUsesWith(NewVal);
+    // Fixup all of the uses of this placeholder def...
+    PlaceHolder->replaceAllUsesWith(NewVal);
       
-      // Now that all the uses are gone, delete the placeholder...
-      // If we couldn't find a def (error case), then leak a little
-      // memory, because otherwise we can't remove all uses!
-      delete V;
-    }
-    delete &VL;
+    // Now that all the uses are gone, delete the placeholder...
+    // If we couldn't find a def (error case), then leak a little
+    // memory, because otherwise we can't remove all uses!
+    delete PlaceHolder;
   }
 
   // Clear out function-level types...
diff --git a/lib/Bytecode/Reader/ReaderInternals.h b/lib/Bytecode/Reader/ReaderInternals.h
index 58ad8df8ceb..d53fcab2326 100644
--- a/lib/Bytecode/Reader/ReaderInternals.h
+++ b/lib/Bytecode/Reader/ReaderInternals.h
@@ -57,7 +57,6 @@ public:
   }
   void freeState() {
     freeTable(Values);
-    freeTable(LateResolveValues);
     freeTable(ModuleValues);
   }
 
@@ -100,8 +99,9 @@ private:
   bool hasInternalMarkerOnly;       // Only types of linkage are intern/external
 
   typedef std::vector<ValueList*> ValueTable;
-  ValueTable Values, LateResolveValues;
+  ValueTable Values;
   ValueTable ModuleValues;
+  std::map<std::pair<unsigned,unsigned>, Value*> ForwardReferences;
 
   std::vector<BasicBlock*> ParsedBasicBlocks;
 
-- 
2.34.1