From bc227b65c212e5c17636bfe8a5e4dfaa764c56b0 Mon Sep 17 00:00:00 2001 From: Owen Anderson Date: Fri, 30 Jan 2015 09:05:49 +0000 Subject: [PATCH] Change a very hot piece of code in TableGen's register unit computations to use bit vectors rather than arrays. For target descriptions with very large and very dense register files, TableGen can take an extremely long time to run. This change makes a dent in that (~15% in my measurements) by accelerating the single hottest operation with better data structures. I believe there's still a lot of room to make this even faster with more global changes that require replacing some of the existing datastructures in this area with bit vectors, but that's a more involved change and I wanted to get this simpler improvement in first. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@227562 91177308-0d34-0410-b5e6-96231b3b80d8 --- utils/TableGen/CodeGenRegisters.cpp | 15 ++++++++++++++- 1 file changed, 14 insertions(+), 1 deletion(-) diff --git a/utils/TableGen/CodeGenRegisters.cpp b/utils/TableGen/CodeGenRegisters.cpp index bef8a4b8fa1..1cf260d0ea1 100644 --- a/utils/TableGen/CodeGenRegisters.cpp +++ b/utils/TableGen/CodeGenRegisters.cpp @@ -17,6 +17,7 @@ #include "llvm/ADT/IntEqClasses.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/SparseBitVector.h" #include "llvm/ADT/StringExtras.h" #include "llvm/ADT/Twine.h" #include "llvm/Support/Debug.h" @@ -211,12 +212,24 @@ static bool hasRegUnit(CodeGenRegister::RegUnitList &RegUnits, unsigned Unit) { // Return true if the RegUnits changed. bool CodeGenRegister::inheritRegUnits(CodeGenRegBank &RegBank) { unsigned OldNumUnits = RegUnits.size(); + + SparseBitVector<> NewUnits; + for (unsigned RU : RegUnits) + NewUnits.set(RU); + for (SubRegMap::const_iterator I = SubRegs.begin(), E = SubRegs.end(); I != E; ++I) { CodeGenRegister *SR = I->second; // Merge the subregister's units into this register's RegUnits. - mergeRegUnits(RegUnits, SR->RegUnits); + for (unsigned RU : SR->RegUnits) + NewUnits.set(RU); } + + RegUnits.clear(); + RegUnits.reserve(NewUnits.count()); + for (unsigned RU : NewUnits) + RegUnits.push_back(RU); + return OldNumUnits != RegUnits.size(); } -- 2.34.1