From 8ae3ac7a8c2112ab739b4a0dc24f28b2bbb84117 Mon Sep 17 00:00:00 2001
From: Andrew Trick <atrick@apple.com>
Date: Wed, 22 Feb 2012 21:59:00 +0000
Subject: [PATCH] misched: Use SparseSet for VRegDegs for constant time
 clear().

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151205 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/CodeGen/ScheduleDAGInstrs.cpp | 32 ++++++++++++++++++-------------
 lib/CodeGen/ScheduleDAGInstrs.h   | 25 +++++++++++++++++++++---
 2 files changed, 41 insertions(+), 16 deletions(-)

diff --git a/lib/CodeGen/ScheduleDAGInstrs.cpp b/lib/CodeGen/ScheduleDAGInstrs.cpp
index 02d07fa08c6..61bca5294ee 100644
--- a/lib/CodeGen/ScheduleDAGInstrs.cpp
+++ b/lib/CodeGen/ScheduleDAGInstrs.cpp
@@ -373,13 +373,18 @@ void ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU, unsigned OperIdx) {
   // uses. We're conservative for now until we have a way to guarantee the uses
   // are not eliminated sometime during scheduling. The output dependence edge
   // is also useful if output latency exceeds def-use latency.
-  SUnit *&DefSU = VRegDefs[Reg];
-  if (DefSU && DefSU != SU && DefSU != &ExitSU) {
-    unsigned OutLatency = TII->getOutputLatency(InstrItins, MI, OperIdx,
-                                                DefSU->getInstr());
-    DefSU->addPred(SDep(SU, SDep::Output, OutLatency, Reg));
+  VReg2SUnitMap::iterator DefI = findVRegDef(Reg);
+  if (DefI == VRegDefs.end())
+    VRegDefs.insert(VReg2SUnit(Reg, SU));
+  else {
+    SUnit *DefSU = DefI->SU;
+    if (DefSU != SU && DefSU != &ExitSU) {
+      unsigned OutLatency = TII->getOutputLatency(InstrItins, MI, OperIdx,
+                                                  DefSU->getInstr());
+      DefSU->addPred(SDep(SU, SDep::Output, OutLatency, Reg));
+    }
+    DefI->SU = SU;
   }
-  DefSU = SU;
 }
 
 /// addVRegUseDeps - Add a register data dependency if the instruction that
@@ -418,12 +423,9 @@ void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) {
   }
 
   // Add antidependence to the following def of the vreg it uses.
-  DenseMap<unsigned, SUnit*>::const_iterator I = VRegDefs.find(Reg);
-  if (I != VRegDefs.end()) {
-    SUnit *DefSU = I->second;
-    if (DefSU != SU)
-      DefSU->addPred(SDep(SU, SDep::Anti, 0, Reg));
-  }
+  VReg2SUnitMap::iterator DefI = findVRegDef(Reg);
+  if (DefI != VRegDefs.end() && DefI->SU != SU)
+    DefI->SU->addPred(SDep(SU, SDep::Anti, 0, Reg));
 }
 
 /// Create an SUnit for each real instruction, numbered in top-down toplological
@@ -488,7 +490,11 @@ void ScheduleDAGInstrs::BuildSchedGraph(AliasAnalysis *AA) {
     assert(Defs[i].empty() && "Only BuildGraph should push/pop Defs");
   }
 
-  assert(VRegDefs.size() == 0 && "Only BuildSchedGraph may access VRegDefs");
+  assert(VRegDefs.empty() && "Only BuildSchedGraph may access VRegDefs");
+  // FIXME: Allow SparseSet to reserve space for the creation of virtual
+  // registers during scheduling. Don't artificially inflate the Universe
+  // because we want to assert that vregs are not created during DAG building.
+  VRegDefs.setUniverse(MRI.getNumVirtRegs());
 
   // Walk the list of instructions, from bottom moving up.
   MachineInstr *PrevMI = NULL;
diff --git a/lib/CodeGen/ScheduleDAGInstrs.h b/lib/CodeGen/ScheduleDAGInstrs.h
index 9a209fff4c4..3b450b0de90 100644
--- a/lib/CodeGen/ScheduleDAGInstrs.h
+++ b/lib/CodeGen/ScheduleDAGInstrs.h
@@ -20,8 +20,8 @@
 #include "llvm/CodeGen/ScheduleDAG.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Target/TargetRegisterInfo.h"
-#include "llvm/ADT/IndexedMap.h"
 #include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/SparseSet.h"
 #include <map>
 
 namespace llvm {
@@ -125,9 +125,24 @@ namespace llvm {
     std::vector<std::vector<SUnit *> > Defs;
     std::vector<std::vector<SUnit *> > Uses;
 
+    /// An individual mapping from virtual register number to SUnit.
+    struct VReg2SUnit {
+      unsigned VirtReg;
+      SUnit *SU;
+
+      VReg2SUnit(unsigned reg, SUnit *su): VirtReg(reg), SU(su) {}
+
+      unsigned getSparseSetKey() const {
+        return TargetRegisterInfo::virtReg2Index(VirtReg);
+      }
+    };
+    // Use SparseSet as a SparseMap by relying on the fact that it never
+    // compares ValueT's, only unsigned keys. This allows the set to be cleared
+    // between scheduling regions in constant time.
+    typedef SparseSet<VReg2SUnit> VReg2SUnitMap;
+
     // Track the last instructon in this region defining each virtual register.
-    // FIXME: turn this into a sparse set with constant time clear().
-    DenseMap<unsigned, SUnit*> VRegDefs;
+    VReg2SUnitMap VRegDefs;
 
     /// PendingLoads - Remember where unknown loads are after the most recent
     /// unknown store, as we iterate. As with Defs and Uses, this is here
@@ -235,6 +250,10 @@ namespace llvm {
     void addPhysRegDeps(SUnit *SU, unsigned OperIdx);
     void addVRegDefDeps(SUnit *SU, unsigned OperIdx);
     void addVRegUseDeps(SUnit *SU, unsigned OperIdx);
+
+    VReg2SUnitMap::iterator findVRegDef(unsigned VirtReg) {
+      return VRegDefs.find(TargetRegisterInfo::virtReg2Index(VirtReg));
+    }
   };
 }
 
-- 
2.34.1