[DebugInfo][InstrRef] Recover some performance by calculating IDF for register units instead of all their alises

[jmorse]

Summary

In D110173 we start using the existing LLVM IDF calculator to place PHIs as we reconstruct an SSA form of machine-code program. Sadly that's slower than the old (but broken) way, this patch attempts to recover some of that performance.

The key observation: every time we def a register, we also have to def it's register units. A refresher on units is here [0]. If we def'd $rax, in the current implementation we independently calculate PHI locations for {al, ah, ax, eax, hax, rax}, and they will all have the same PHI positions. Instead of doing that, we can calculate the PHI positions for {al, ah} and place PHIs for any aliasing registers in the same positions. Any def of a super-register has to def the unit, and vice versa, so this is sound. It cuts down the SSA placement we need to do significantly.

There are a few escape hatches: stack slots don't have subregisters (yet), so they have to be handled independently. There are also scenarios where we only ever read from registers (such as arguments), and so never track their sub-registers or register units. In both of these cases, this patch just falls back to placing PHIs "normally". There's also a small amount of juggling to do with the stack pointer: we ignore defs of the stack pointer at calls, so register masks and SP defs get ignored. Now that we're placing PHIs for register units on top of the super-registers they alias, we need to be careful to not def the stack pointer register units either. Thus, there's now a collection of "aliases of the stack pointer" in MLocTracker that shouldn't be def'd by calls either.

Testing: because this is performance related, no tests, but this builds clang-3.4 with identical object files after being applied (save for the object file with the date/time in it).

[0] https://lists.llvm.org/pipermail/llvm-dev/2012-May/050177.html

[jmorse]

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

1819–1820

NB: this seems to be the canonical way of enumerating register unit... registers? in the rest of LLVM. What MCRegUnitIterator produces doesn't seem to necessarily correspond to a single register, therefore there's an additional process of enumerating the roots too.

Either way, it works for x86, and this pattern is used elsewhere in llvm. So It Must Be Right (TM).

[Orlando]

LGTM! Plus a couple of inline nits.

Testing: because this is performance related, no tests, but this builds clang-3.4 with identical object files after being applied (save for the object file with the date/time in it).

Out of interest do you have any numbers for the positive performance impact of this patch?

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

1819–1820

Thanks for the explanation. Nit: Please can you rename URoots to URoot?

1833

nits: If you're also stuffing (arg) registers in too, maybe SlotsToPHI should be renamed. Something like LocsToPHI or LocsWithoutRegUnits?
Also is this a dev comment that leaked into the patch?

[jmorse]

Out of interest do you have any numbers for the positive performance impact of this patch?

Loss from PHI installation:
http://llvm-compile-time-tracker.com/compare.php?from=9b9e6f1d4a7b15d5a4a076cd7e9dfbe3cc9afce6&to=c039d62f7f2bbea4cca09be7d2355700e972f9e6&stat=instructions

Gain from this patch:
http://llvm-compile-time-tracker.com/compare.php?from=7ee343ecae52ea3cd843e508e322b6b10c649a56&to=bc07cf76a31fa769786d6631fe25586bd1396c34&stat=instructions

They're not directly comparable numbers because inbetween is the variable-location PHI installation patch, which adds additional performance loss. The full set of patches are here under the "use-ssa-phi-placement3" branch, unfortunately the commit messages are written in Jeremy-speak so might not be intelligible. The order goes:

• Turn on instr-ref
• Install 2 PHI placement patches
• This patch
• Another vloc performance patch
• 2 attempts to improve performance further with corresponding reverts
• A final vloc performance patch that actually works,
• Another patch that didn't deliver any gains.

https://llvm-compile-time-tracker.com/?config=NewPM-ReleaseLTO-g&stat=instructions&remote=jmorse

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

1833

yes and yes

[Orlando]

Thanks for the info

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h

public:
   /// This, and the corresponding reverse map persist for the analysis of the
   /// whole function, and is necessarying for decoding various vectors of
   /// values.
   std::vector<LocIdx> LocIDToLocIdx;
 
   /// Inverse map of LocIDToLocIdx.
   IndexedMap<unsigned, LocIdxToIndexFunctor> LocIdxToLocID;
 
+  /// When clobbering register masks, we chose to not believe the machine model
+  /// and don't clobber SP. Do the same for SP aliases, and for efficiency,
+  /// keep a set of them here.
+  SmallSet<Register, 8> SPAliases;
+
   /// Unique-ification of spill slots. Used to number them -- their LocID
   /// number is the index in SpillLocs minus one plus NumRegs.
   UniqueVector<SpillLoc> SpillLocs;
 
   // If we discover a new machine location, assign it an mphi with this
   // block number.
   unsigned CurBB;
 
public:
 
   LocIdx lookupOrTrackRegister(unsigned ID) {
     LocIdx &Index = LocIDToLocIdx[ID];
     if (Index.isIllegal())
       Index = trackRegister(ID);
     return Index;
   }
 
+  /// Is register R currently tracked by MLocTracker?
+  bool isRegisterTracked(Register R) {
+    LocIdx &Index = LocIDToLocIdx[R];
+    return !Index.isIllegal();
+  }
+
   /// Record a definition of the specified register at the given block / inst.
   /// This doesn't take a ValueIDNum, because the definition and its location
   /// are synonymous.
   void defReg(Register R, unsigned BB, unsigned Inst) {
     unsigned ID = getLocID(R, false);
     LocIdx Idx = lookupOrTrackRegister(ID);
     ValueIDNum ValueID = {BB, Inst, Idx};
     LocIdxToIDNum[Idx] = ValueID;
private:
   /// transfer functions in \p MLocTransfer. Writes the output live-in and
   /// live-out arrays to the (initialized to zero) multidimensional arrays in
   /// \p MInLocs and \p MOutLocs. The outer dimension is indexed by block
   /// number, the inner by LocIdx.
   void buildMLocValueMap(MachineFunction &MF, ValueIDNum **MInLocs,
                          ValueIDNum **MOutLocs,
                          SmallVectorImpl<MLocTransferMap> &MLocTransfer);
 
+  /// Install PHI values into the live-in array for each block, according to
+  /// the IDF of each register.
+  void placeMLocPHIs(MachineFunction &MF,
+                     SmallPtrSetImpl<MachineBasicBlock *> &AllBlocks,
+                     ValueIDNum **MInLocs,
+                     SmallVectorImpl<MLocTransferMap> &MLocTransfer);
+
   /// Calculate the iterated-dominance-frontier for a set of defs, using the
   /// existing LLVM facilities for this. Works for a single "value" or
   /// machine/variable location.
   /// \p AllBlocks Set of blocks where we might consume the value.
   /// \p DefBlocks Set of blocks where the value/location is defined.
   /// \p PHIBlocks Output set of blocks where PHIs must be placed.
   void BlockPHIPlacement(const SmallPtrSetImpl<MachineBasicBlock *> &AllBlocks,
                          const SmallPtrSetImpl<MachineBasicBlock *> &DefBlocks,

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

MLocTracker::MLocTracker(MachineFunction &MF, const TargetInstrInfo &TII,
 
   // Always track SP. This avoids the implicit clobbering caused by regmasks
   // from affectings its values. (LiveDebugValues disbelieves calls and
   // regmasks that claim to clobber SP).
   Register SP = TLI.getStackPointerRegisterToSaveRestore();
   if (SP) {
     unsigned ID = getLocID(SP, false);
     (void)lookupOrTrackRegister(ID);
+
+    for (MCRegAliasIterator RAI(SP, &TRI, true); RAI.isValid(); ++RAI)
+      SPAliases.insert(*RAI);
   }
 }
 
 LocIdx MLocTracker::trackRegister(unsigned ID) {
   assert(ID != 0);
   LocIdx NewIdx = LocIdx(LocIdxToIDNum.size());
   LocIdxToIDNum.grow(NewIdx);
   LocIdxToLocID.grow(NewIdx);
LocIdx MLocTracker::trackRegister(unsigned ID) {
 
   LocIdxToIDNum[NewIdx] = ValNum;
   LocIdxToLocID[NewIdx] = ID;
   return NewIdx;
 }
 
 void MLocTracker::writeRegMask(const MachineOperand *MO, unsigned CurBB,
                                unsigned InstID) {
-  // Ensure SP exists, so that we don't override it later.
-  Register SP = TLI.getStackPointerRegisterToSaveRestore();
-
   // Def any register we track have that isn't preserved. The regmask
   // terminates the liveness of a register, meaning its value can't be
   // relied upon -- we represent this by giving it a new value.
   for (auto Location : locations()) {
     unsigned ID = LocIdxToLocID[Location.Idx];
     // Don't clobber SP, even if the mask says it's clobbered.
-    if (ID < NumRegs && ID != SP && MO->clobbersPhysReg(ID))
+    if (ID < NumRegs && !SPAliases.count(ID) && MO->clobbersPhysReg(ID))
       defReg(ID, CurBB, InstID);
   }
   Masks.push_back(std::make_pair(MO, InstID));
 }
 
 LocIdx MLocTracker::getOrTrackSpillLoc(SpillLoc L) {
   unsigned SpillID = SpillLocs.idFor(L);
   if (SpillID == 0) {
for (auto &MBB : MF) {
     // Accumulate any bitmask operands into the clobberred reg mask for this
     // block.
     for (auto &P : MTracker->Masks) {
       BlockMasks[CurBB].clearBitsNotInMask(P.first->getRegMask(), BVWords);
     }
   }
 
   // Compute a bitvector of all the registers that are tracked in this block.
-  const TargetLowering *TLI = MF.getSubtarget().getTargetLowering();
-  Register SP = TLI->getStackPointerRegisterToSaveRestore();
   BitVector UsedRegs(TRI->getNumRegs());
   for (auto Location : MTracker->locations()) {
     unsigned ID = MTracker->LocIdxToLocID[Location.Idx];
-    if (ID >= TRI->getNumRegs() || ID == SP)
+    // Ignore stack slots, and aliases of the stack pointer.
+    if (ID >= TRI->getNumRegs() || MTracker->SPAliases.count(ID))
       continue;
     UsedRegs.set(ID);
   }
 
   // Check that any regmask-clobber of a register that gets tracked, is not
   // live-through in the transfer function. It needs to be clobbered at the
   // very least.
   for (unsigned int I = 0; I < MaxNumBlocks; ++I) {
if (!Disagree) {
       Changed |= true;
     }
   }
 
   // TODO: Reimplement NumInserted and NumRemoved.
   return Changed;
 }
 
+void InstrRefBasedLDV::placeMLocPHIs(MachineFunction &MF,
+                              SmallPtrSetImpl<MachineBasicBlock *> &AllBlocks,
+                              ValueIDNum **MInLocs,
+                              SmallVectorImpl<MLocTransferMap> &MLocTransfer) {
+  // To avoid repeatedly running the PHI placement algorithm, leverage the
+  // fact that a def of register MUST also def its register units. Find the
+  // units for registers, place PHIs for them, and then replicate them for 
+  // aliasing registers. Some inputs that are never def'd (DBG_PHIs of
+  // arguments) don't lead to register units being tracked, just place PHIs for
+  // those registers directly. Do the same for stack slots.
+  SmallSet<Register, 32> RegUnitsToPHIUp;
+  SmallSet<LocIdx, 32> LocsToPHI;
+  for (auto Location : MTracker->locations()) {
+    LocIdx L = Location.Idx;
+    if (MTracker->isSpill(L)) {
+      LocsToPHI.insert(L);
+      continue;
+    }
+
+    Register R = MTracker->LocIdxToLocID[L];
+    SmallSet<Register, 8> FoundRegUnits;
+    bool AnyIllegal = false;
+    for (MCRegUnitIterator RUI(R.asMCReg(), TRI); RUI.isValid(); ++RUI) {
+      for (MCRegUnitRootIterator URoot(*RUI, TRI); URoot.isValid(); ++URoot){
+        if (!MTracker->isRegisterTracked(*URoot)) {
+          // Not all roots were loaded into the tracking map: this register
+          // isn't actually def'd anywhere, we only read from it. Generate PHIs
+          // for this reg, but don't iterate units.
+          AnyIllegal = true;
+        } else {
+          FoundRegUnits.insert(*URoot);
+        }
+      }
+    }
+
+    if (AnyIllegal) {
+      LocsToPHI.insert(L);
+      continue;
+    }
+
+    RegUnitsToPHIUp.insert(FoundRegUnits.begin(), FoundRegUnits.end());
+  }
+
+  // Lambda to fetch PHIs for a given location, and write into the PHIBlocks
+  // collection.
+  SmallVector<MachineBasicBlock *, 32> PHIBlocks;
+  auto CollectPHIsForLoc = [&](LocIdx L) {
+    // Collect the set of defs.
+    SmallPtrSet<MachineBasicBlock *, 32> DefBlocks;
+    for (unsigned int I = 0; I < OrderToBB.size(); ++I) {
+      MachineBasicBlock *MBB = OrderToBB[I];
+      const auto &TransferFunc = MLocTransfer[MBB->getNumber()];
+      if (TransferFunc.find(L) != TransferFunc.end())
+        DefBlocks.insert(MBB);
+    }
+
+    // The entry block defs the location too: it's the live-in / argument value.
+    // Only insert if there are other defs though; everything is trivially live
+    // through otherwise.
+    if (!DefBlocks.empty())
+      DefBlocks.insert(&*MF.begin());
+
+    // Ask the SSA construction algorithm where we should put PHIs. Clear
+    // anything that might have been hanging around from earlier.
+    PHIBlocks.clear();
+    BlockPHIPlacement(AllBlocks, DefBlocks, PHIBlocks);
+  };
+
+  // For spill slots, and locations with no reg units, just place PHIs.
+  for (LocIdx L : LocsToPHI) {
+    CollectPHIsForLoc(L);
+    // Install those PHI values into the live-in value array.
+    for (const MachineBasicBlock *MBB : PHIBlocks)
+      MInLocs[MBB->getNumber()][L.asU64()] = ValueIDNum(MBB->getNumber(), 0, L);
+  }
+
+  // For reg units, place PHIs, and then place them for any aliasing registers.
+  for (Register R : RegUnitsToPHIUp) {
+    LocIdx L = MTracker->lookupOrTrackRegister(R);
+    CollectPHIsForLoc(L);
+
+    // Install those PHI values into the live-in value array.
+    for (const MachineBasicBlock *MBB : PHIBlocks)
+      MInLocs[MBB->getNumber()][L.asU64()] = ValueIDNum(MBB->getNumber(), 0, L);
+
+    // Now find aliases and install PHIs for those.
+    for (MCRegAliasIterator RAI(R, TRI, true); RAI.isValid(); ++RAI) {
+      // Super-registers that are "above" the largest register read/written by
+      // the function will alias, but will not be tracked.
+      if (!MTracker->isRegisterTracked(*RAI))
+        continue;
+
+      LocIdx AliasLoc = MTracker->lookupOrTrackRegister(*RAI);
+      for (const MachineBasicBlock *MBB : PHIBlocks)
+        MInLocs[MBB->getNumber()][AliasLoc.asU64()] =
+            ValueIDNum(MBB->getNumber(), 0, AliasLoc);
+    }
+  }
+}
+
 void InstrRefBasedLDV::buildMLocValueMap(
     MachineFunction &MF, ValueIDNum **MInLocs, ValueIDNum **MOutLocs,
     SmallVectorImpl<MLocTransferMap> &MLocTransfer) {
   std::priority_queue<unsigned int, std::vector<unsigned int>,
                       std::greater<unsigned int>>
       Worklist, Pending;
 
   // We track what is on the current and pending worklist to avoid inserting
void InstrRefBasedLDV::buildMLocValueMap(
   for (auto Location : MTracker->locations())
     MInLocs[0][Location.Idx.asU64()] = ValueIDNum(0, 0, Location.Idx);
 
   MTracker->reset();
 
   // Start by placing PHIs, using the usual SSA constructor algorithm. Consider
   // any machine-location that isn't live-through a block to be def'd in that
   // block.
-  for (auto Location : MTracker->locations()) {
-    // Collect the set of defs.
-    SmallPtrSet<MachineBasicBlock *, 32> DefBlocks;
-    for (unsigned int I = 0; I < OrderToBB.size(); ++I) {
-      MachineBasicBlock *MBB = OrderToBB[I];
-      const auto &TransferFunc = MLocTransfer[MBB->getNumber()];
-      if (TransferFunc.find(Location.Idx) != TransferFunc.end())
-        DefBlocks.insert(MBB);
-    }
-
-    // The entry block defs the location too: it's the live-in / argument value.
-    // Only insert if there are other defs though; everything is trivially live
-    // through otherwise.
-    if (!DefBlocks.empty())
-      DefBlocks.insert(&*MF.begin());
-
-    // Ask the SSA construction algorithm where we should put PHIs.
-    SmallVector<MachineBasicBlock *, 32> PHIBlocks;
-    BlockPHIPlacement(AllBlocks, DefBlocks, PHIBlocks);
-
-    // Install those PHI values into the live-in value array.
-    for (const MachineBasicBlock *MBB : PHIBlocks) {
-      MInLocs[MBB->getNumber()][Location.Idx.asU64()] =
-          ValueIDNum(MBB->getNumber(), 0, Location.Idx);
-    }
-  }
+  placeMLocPHIs(MF, AllBlocks, MInLocs, MLocTransfer);
 
   // Propagate values to eliminate redundant PHIs. At the same time, this
   // produces the table of Block x Location => Value for the entry to each
   // block.
   // The kind of PHIs we can eliminate are, for example, where one path in a
   // conditional spills and restores a register, and the register still has
   // the same value once control flow joins, unbeknowns to the PHI placement
   // code. Propagating values allows us to identify such un-necessary PHIs and