From 79e2045531cb4d1978be42591e9254c38a463d30 Mon Sep 17 00:00:00 2001
From: Jakob Stoklund Olesen <stoklund@2pi.dk>
Date: Fri, 11 May 2012 19:01:01 +0000
Subject: [PATCH] Defer computation of SuperRegs.

Don't compute the SuperRegs list until the sub-register graph is
completely finished. This guarantees that the list of super-registers is
properly topologically ordered, and has no duplicates.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156629 91177308-0d34-0410-b5e6-96231b3b80d8
---
 utils/TableGen/CodeGenRegisters.cpp | 42 +++++++++++++++++++++--------
 utils/TableGen/CodeGenRegisters.h   |  5 ++++
 2 files changed, 36 insertions(+), 11 deletions(-)

diff --git a/utils/TableGen/CodeGenRegisters.cpp b/utils/TableGen/CodeGenRegisters.cpp
index 94782871c76..8f4fdf5acf0 100644
--- a/utils/TableGen/CodeGenRegisters.cpp
+++ b/utils/TableGen/CodeGenRegisters.cpp
@@ -83,7 +83,8 @@ CodeGenRegister::CodeGenRegister(Record *R, unsigned Enum)
     EnumValue(Enum),
     CostPerUse(R->getValueAsInt("CostPerUse")),
     CoveredBySubRegs(R->getValueAsBit("CoveredBySubRegs")),
-    SubRegsComplete(false)
+    SubRegsComplete(false),
+    SuperRegsComplete(false)
 {}
 
 void CodeGenRegister::buildObjectGraph(CodeGenRegBank &RegBank) {
@@ -219,19 +220,10 @@ CodeGenRegister::computeSubRegs(CodeGenRegBank &RegBank) {
     CodeGenRegister *SR = ExplicitSubRegs[i];
     const SubRegMap &Map = SR->computeSubRegs(RegBank);
 
-    // Add this as a super-register of SR now all sub-registers are in the list.
-    // This creates a topological ordering, the exact order depends on the
-    // order computeSubRegs is called on all registers.
-    SR->SuperRegs.push_back(this);
-
     for (SubRegMap::const_iterator SI = Map.begin(), SE = Map.end(); SI != SE;
          ++SI) {
       if (!SubRegs.insert(*SI).second)
         Orphans.insert(SI->second);
-
-      // Noop sub-register indexes are possible, so avoid duplicates.
-      if (SI->second != SR)
-        SI->second->SuperRegs.push_back(this);
     }
   }
 
@@ -439,7 +431,6 @@ void CodeGenRegister::computeSecondarySubRegs(CodeGenRegBank &RegBank) {
     CodeGenSubRegIndex *NewIdx = NewSubRegs[i].first;
     CodeGenRegister *NewSubReg = NewSubRegs[i].second;
     SubReg2Idx.insert(std::make_pair(NewSubReg, NewIdx));
-    NewSubReg->SuperRegs.push_back(this);
   }
 
   // Create sub-register index composition maps for the synthesized indices.
@@ -457,6 +448,30 @@ void CodeGenRegister::computeSecondarySubRegs(CodeGenRegBank &RegBank) {
   }
 }
 
+void CodeGenRegister::computeSuperRegs() {
+  // Only visit each register once.
+  if (SuperRegsComplete)
+    return;
+  SuperRegsComplete = true;
+
+  // Make sure all sub-registers have been visited first, so the super-reg
+  // lists will be topologically ordered.
+  for (SubRegMap::const_iterator I = SubRegs.begin(), E = SubRegs.end();
+       I != E; ++I)
+    I->second->computeSuperRegs();
+
+  // Now add this as a super-register on all sub-registers.
+  for (SubRegMap::const_iterator I = SubRegs.begin(), E = SubRegs.end();
+       I != E; ++I) {
+    if (I->second == this)
+      continue;
+    // Don't add duplicate entries.
+    if (!I->second->SuperRegs.empty() && I->second->SuperRegs.back() == this)
+      continue;
+    I->second->SuperRegs.push_back(this);
+  }
+}
+
 void
 CodeGenRegister::addSubRegsPreOrder(SetVector<const CodeGenRegister*> &OSet,
                                     CodeGenRegBank &RegBank) const {
@@ -900,6 +915,11 @@ CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) : Records(Records) {
     if (Registers[i]->CoveredBySubRegs)
       Registers[i]->computeSecondarySubRegs(*this);
 
+  // After the sub-register graph is complete, compute the topologically
+  // ordered SuperRegs list.
+  for (unsigned i = 0, e = Registers.size(); i != e; ++i)
+    Registers[i]->computeSuperRegs();
+
   // Native register units are associated with a leaf register. They've all been
   // discovered now.
   NumNativeRegUnits = NumRegUnits;
diff --git a/utils/TableGen/CodeGenRegisters.h b/utils/TableGen/CodeGenRegisters.h
index 23cc53932d9..f5413b6a740 100644
--- a/utils/TableGen/CodeGenRegisters.h
+++ b/utils/TableGen/CodeGenRegisters.h
@@ -112,6 +112,10 @@ namespace llvm {
     // Compute extra sub-registers by combining the existing sub-registers.
     void computeSecondarySubRegs(CodeGenRegBank&);
 
+    // Add this as a super-register to all sub-registers after the sub-register
+    // graph has been built.
+    void computeSuperRegs();
+
     const SubRegMap &getSubRegs() const {
       assert(SubRegsComplete && "Must precompute sub-registers");
       return SubRegs;
@@ -169,6 +173,7 @@ namespace llvm {
 
   private:
     bool SubRegsComplete;
+    bool SuperRegsComplete;
 
     // The sub-registers explicit in the .td file form a tree.
     SmallVector<CodeGenSubRegIndex*, 8> ExplicitSubRegIndices;
-- 
2.34.1