From 5f46eb157e58df285e1a0a7ce6ff1c9ed972bf65 Mon Sep 17 00:00:00 2001
From: Lang Hames <lhames@gmail.com>
Date: Tue, 27 Mar 2012 19:10:45 +0000
Subject: [PATCH] Use a SmallVector and linear lookup instead of a DenseSet -
 SourceMap values will always be tiny sets, so DenseSet is overkill (SmallSet
 won't work as we need iteration support).

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153529 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/CodeGen/MachineCopyPropagation.cpp | 27 +++++++++++++++-----------
 1 file changed, 16 insertions(+), 11 deletions(-)

diff --git a/lib/CodeGen/MachineCopyPropagation.cpp b/lib/CodeGen/MachineCopyPropagation.cpp
index 565efb3898c..9730eaacf6e 100644
--- a/lib/CodeGen/MachineCopyPropagation.cpp
+++ b/lib/CodeGen/MachineCopyPropagation.cpp
@@ -22,7 +22,6 @@
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
@@ -44,9 +43,12 @@ namespace {
     virtual bool runOnMachineFunction(MachineFunction &MF);
 
   private:
+    typedef SmallVector<unsigned, 4> DestList;
+    typedef DenseMap<unsigned, DestList> SourceMap;
+
     void SourceNoLongerAvailable(unsigned Reg,
-                                 DenseMap<unsigned, DenseSet<unsigned> > &SrcMap,
-                               DenseMap<unsigned, MachineInstr*> &AvailCopyMap);
+                                 SourceMap &SrcMap,
+                                 DenseMap<unsigned, MachineInstr*> &AvailCopyMap);
     bool CopyPropagateBlock(MachineBasicBlock &MBB);
   };
 }
@@ -58,12 +60,12 @@ INITIALIZE_PASS(MachineCopyPropagation, "machine-cp",
 
 void
 MachineCopyPropagation::SourceNoLongerAvailable(unsigned Reg,
-                              DenseMap<unsigned, DenseSet<unsigned> > &SrcMap,
+                              SourceMap &SrcMap,
                               DenseMap<unsigned, MachineInstr*> &AvailCopyMap) {
-  DenseMap<unsigned, DenseSet<unsigned> >::iterator SI = SrcMap.find(Reg);
+  SourceMap::iterator SI = SrcMap.find(Reg);
   if (SI != SrcMap.end()) {
-    const DenseSet<unsigned>& Defs = SI->second;
-    for (DenseSet<unsigned>::const_iterator I = Defs.begin(), E = Defs.end();
+    const DestList& Defs = SI->second;
+    for (DestList::const_iterator I = Defs.begin(), E = Defs.end();
          I != E; ++I) {
       unsigned MappedDef = *I;
       // Source of copy is no longer available for propagation.
@@ -76,8 +78,8 @@ MachineCopyPropagation::SourceNoLongerAvailable(unsigned Reg,
   for (const uint16_t *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
     SI = SrcMap.find(*AS);
     if (SI != SrcMap.end()) {
-      const DenseSet<unsigned>& Defs = SI->second;
-      for (DenseSet<unsigned>::const_iterator I = Defs.begin(), E = Defs.end();
+      const DestList& Defs = SI->second;
+      for (DestList::const_iterator I = Defs.begin(), E = Defs.end();
            I != E; ++I) {
         unsigned MappedDef = *I;
         if (AvailCopyMap.erase(MappedDef)) {
@@ -137,7 +139,7 @@ bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
   SmallSetVector<MachineInstr*, 8> MaybeDeadCopies;  // Candidates for deletion
   DenseMap<unsigned, MachineInstr*> AvailCopyMap;    // Def -> available copies map
   DenseMap<unsigned, MachineInstr*> CopyMap;         // Def -> copies map
-  DenseMap<unsigned, DenseSet<unsigned> > SrcMap; // Src -> Def map
+  SourceMap SrcMap; // Src -> Def map
 
   bool Changed = false;
   for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) {
@@ -222,7 +224,10 @@ bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
 
       // Remember source that's copied to Def. Once it's clobbered, then
       // it's no longer available for copy propagation.
-      SrcMap[Src].insert(Def);
+      if (std::find(SrcMap[Src].begin(), SrcMap[Src].end(), Def) ==
+          SrcMap[Src].end()) {
+        SrcMap[Src].push_back(Def);
+      }
 
       continue;
     }
-- 
2.34.1