[BOLT][NFC] Improve performance of MCPlusBuilder::initAliases

[jobnoorman]

Summary

It was using a redundant iteration over super regs to build
SmallerAliasMap. Removing this results in exactly the same alias maps
and a noticeable performance gain on targets with a large number of
registers.

Just anecdotally: on my machine, processing a small AArch64 binary went
from 2.7s down to 80ms.

[Amir]

Thanks!

[jobnoorman]

Thanks for the review, @Amir! I'm not sure if one accept is enough to get this landed but if it is, please note that I don't have commit rights so I cannot do it myself.

[Amir]

Yes, one accept is enough. Please provide a commit author and email and I'll push it for you.

[jobnoorman]

Job Noorman <[e-mail]>

Thanks!

[rafauler]

bolt/lib/Core/MCPlusBuilder.cpp

468

X86 has registers with subregs, which in turn has their own subregs. e.g. RAX -> EAX -> AX -> AH, AL

I'm curious whether the subreg iterator here is returning the transitive list of all sub regs of a register? e.g. would it return AL as a subreg of RAX? That's what the old code was computing.

[jobnoorman]

bolt/lib/Core/MCPlusBuilder.cpp

468

It does:

// prints EAX AX AL AH HAX
for (MCSubRegIterator SI(X86::RAX, RegInfo); SI.isValid(); ++SI) {
  dbgs() << RegInfo->getName(*SI) << " ";
}

[rafauler]

bolt/lib/Core/MCPlusBuilder.cpp

468

Awesome, thanks for checking!

bolt/lib/Core/MCPlusBuilder.cpp

void MCPlusBuilder::initAliases() {
 
   // Cache all aliases for each register
   for (MCPhysReg I = 1, E = RegInfo->getNumRegs(); I != E; ++I) {
     for (MCRegAliasIterator AI(I, RegInfo, true); AI.isValid(); ++AI)
       AliasMap[I].set(*AI);
   }
 
   // Propagate smaller alias info upwards. Skip reg 0 (mapped to NoRegister)
-  std::queue<MCPhysReg> Worklist;
   for (MCPhysReg I = 1, E = RegInfo->getNumRegs(); I < E; ++I)
-    Worklist.push(I);
-  while (!Worklist.empty()) {
-    MCPhysReg I = Worklist.front();
-    Worklist.pop();
     for (MCSubRegIterator SI(I, RegInfo); SI.isValid(); ++SI)
       SmallerAliasMap[I] |= SmallerAliasMap[*SI];
-    for (MCSuperRegIterator SI(I, RegInfo); SI.isValid(); ++SI)
-      Worklist.push(*SI);
-  }
 
   LLVM_DEBUG({
     dbgs() << "Dumping reg alias table:\n";
     for (MCPhysReg I = 0, E = RegInfo->getNumRegs(); I != E; ++I) {
       dbgs() << "Reg " << I << ": ";
       const BitVector &BV = AliasMap[I];
       int Idx = BV.find_first();
       while (Idx != -1) {