From 5aefcad35bc81e3de4031b1f779c9a9520790cd7 Mon Sep 17 00:00:00 2001
From: "Vikram S. Adve" <vadve@cs.uiuc.edu>
Date: Sun, 13 Oct 2002 00:37:46 +0000
Subject: [PATCH] Use vectors instead of hash_maps for issueGaps and
 conflictLists. These hash lookups were a major sink of time because they
 happen so often!

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4136 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/Target/TargetSchedInfo.h | 34 +++++++++++++++-----------
 lib/Target/TargetSchedInfo.cpp        | 35 ++++++++++++++-------------
 2 files changed, 38 insertions(+), 31 deletions(-)

diff --git a/include/llvm/Target/TargetSchedInfo.h b/include/llvm/Target/TargetSchedInfo.h
index 00d4b188dce..9bb7068cdfd 100644
--- a/include/llvm/Target/TargetSchedInfo.h
+++ b/include/llvm/Target/TargetSchedInfo.h
@@ -242,21 +242,20 @@ public:
   inline int	getLongestIssueConflict	() const {
     return longestIssueConflict;
   }
-  
+
   inline  int 	getMinIssueGap		(MachineOpCode fromOp,
 					 MachineOpCode toOp)   const {
-    hash_map<OpCodePair,int>::const_iterator
-      I = issueGaps.find(OpCodePair(fromOp, toOp));
-    return (I == issueGaps.end())? 0 : (*I).second;
+    assert(fromOp < (int) issueGaps.size());
+    const std::vector<int>& toGaps = issueGaps[fromOp];
+    return (toOp < (int) toGaps.size())? toGaps[toOp] : 0;
   }
-  
-  inline const std::vector<MachineOpCode>*
+
+  inline const std::vector<MachineOpCode>&
 		getConflictList(MachineOpCode opCode) const {
-    hash_map<MachineOpCode, std::vector<MachineOpCode> >::const_iterator
-      I = conflictLists.find(opCode);
-    return (I == conflictLists.end())? NULL : & (*I).second;
+    assert(opCode < (int) conflictLists.size());
+    return conflictLists[opCode];
   }
-  
+
   inline  bool	isSingleIssue		(MachineOpCode opCode) const {
     return getInstrRUsage(opCode).isSingleIssue;
   }
@@ -276,6 +275,13 @@ private:
   void computeInstrResources(const std::vector<InstrRUsage>& instrRUForClasses);
   void computeIssueGaps(const std::vector<InstrRUsage>& instrRUForClasses);
   
+  void setGap(int gap, MachineOpCode fromOp, MachineOpCode toOp) {
+    std::vector<int>& toGaps = issueGaps[fromOp];
+    if (toOp >= (int) toGaps.size())
+      toGaps.resize(toOp+1);
+    toGaps[toOp] = gap;
+  }
+  
 protected:
   int		           numSchedClasses;
   const MachineInstrInfo*  mii;
@@ -285,10 +291,10 @@ protected:
   unsigned 		   numUsageDeltas;
   unsigned 		   numIssueDeltas;
   
-  std::vector<InstrRUsage>      instrRUsages;   // indexed by opcode
-  hash_map<OpCodePair,int> issueGaps;      // indexed by opcode pair
-  hash_map<MachineOpCode, std::vector<MachineOpCode> >
-			   conflictLists;       // indexed by opcode
+  std::vector<InstrRUsage> instrRUsages;    // indexed by opcode
+  std::vector<std::vector<int> > issueGaps; // indexed by [opcode1][opcode2]
+  std::vector<std::vector<MachineOpCode> >
+			   conflictLists;   // indexed by [opcode]
 };
 
 #endif
diff --git a/lib/Target/TargetSchedInfo.cpp b/lib/Target/TargetSchedInfo.cpp
index 6a3c9c717b2..9eb3d98d1df 100644
--- a/lib/Target/TargetSchedInfo.cpp
+++ b/lib/Target/TargetSchedInfo.cpp
@@ -151,11 +151,12 @@ MachineSchedInfo::computeIssueGaps(const std::vector<InstrRUsage>&
 				   instrRUForClasses)
 {
   int numOpCodes =  mii->getNumRealOpCodes();
-  instrRUsages.resize(numOpCodes);
-  
+  issueGaps.resize(numOpCodes);
+  conflictLists.resize(numOpCodes);
+
   assert(numOpCodes < (1 << MAX_OPCODE_SIZE) - 1
          && "numOpCodes invalid for implementation of class OpCodePair!");
-  
+
   // First, compute issue gaps between pairs of classes based on common
   // resources usages for each class, because most instruction pairs will
   // usually behave the same as their class.
@@ -168,27 +169,27 @@ MachineSchedInfo::computeIssueGaps(const std::vector<InstrRUsage>&
 					 instrRUForClasses[toSC]);
 	classPairGaps[fromSC][toSC] = classPairGap; 
       }
-  
+
   // Now, for each pair of instructions, use the class pair gap if both
   // instructions have identical resource usage as their respective classes.
   // If not, recompute the gap for the pair from scratch.
-  
+
   longestIssueConflict = 0;
-  
+
   for (MachineOpCode fromOp=0; fromOp < numOpCodes; fromOp++)
     for (MachineOpCode toOp=0; toOp < numOpCodes; toOp++)
       {
-	int instrPairGap = 
-	  (instrRUsages[fromOp].sameAsClass && instrRUsages[toOp].sameAsClass)
-	  ? classPairGaps[getSchedClass(fromOp)][getSchedClass(toOp)]
-	  : ComputeMinGap(instrRUsages[fromOp], instrRUsages[toOp]);
-      
-	if (instrPairGap > 0)
-	  {
-	    issueGaps[OpCodePair(fromOp,toOp)] = instrPairGap;
-	    conflictLists[fromOp].push_back(toOp);
-	    longestIssueConflict = std::max(longestIssueConflict, instrPairGap);
-	  }
+        int instrPairGap = 
+          (instrRUsages[fromOp].sameAsClass && instrRUsages[toOp].sameAsClass)
+          ? classPairGaps[getSchedClass(fromOp)][getSchedClass(toOp)]
+          : ComputeMinGap(instrRUsages[fromOp], instrRUsages[toOp]);
+
+        if (instrPairGap > 0)
+          {
+            this->setGap(instrPairGap, fromOp, toOp);
+            conflictLists[fromOp].push_back(toOp);
+            longestIssueConflict=std::max(longestIssueConflict, instrPairGap);
+          }
       }
 }
 
-- 
2.34.1