[DebugInfo][InstrRef] Recover some performance from tracking stack-slot sublocations

[jmorse]

Summary

This patch is like D111627 -- instead of calculating IDF for every location on the stack, only do it for the smallest units of interference, and copy the PHIs for those units to any aliases.

This saves us a cool 0.5% instructions on CTMark, thanks again to the compile-time-tracker project.

The test added runs placeMLocPHIs directly, and tests that:

• A def of the lower 8 bits of a stack slot causes all aliasing regs to have PHIs placed,
• It doesn't cause the equivalent location to x86's $ah, which isn't aliased, to have a PHI placed.

[Orlando]

LGTM

llvm/unittests/CodeGen/InstrRefLDVTest.cpp

1101

What are the 10 locs? (plus nit: comment needs capital and full stop)

1149

nit: don't -> doesn't

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h

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);
 
+  /// Examine the stack indexes (i.e. offsets within the stack) to find the
+  /// basic units of interference -- like reg units, but for the stack.
+  void findStackIndexInterference(SmallVectorImpl<unsigned> &Slots);
+
   /// 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

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

if (!Disagree) {
       Changed |= true;
     }
   }
 
   // TODO: Reimplement NumInserted and NumRemoved.
   return Changed;
 }
 
-void InstrRefBasedLDV::placeMLocPHIs(MachineFunction &MF,
-                              SmallPtrSetImpl<MachineBasicBlock *> &AllBlocks,
-                              ValueIDNum **MInLocs,
-                              SmallVectorImpl<MLocTransferMap> &MLocTransfer) {
+void InstrRefBasedLDV::findStackIndexInterference(
+    SmallVectorImpl<unsigned> &Slots) {
+  // We could spend a bit of time finding the exact, minimal, set of stack
+  // indexes that interfere with each other, much like reg units. Or, we can
+  // rely on the fact that:
+  //  * The smallest / lowest index will interfere with everything at zero
+  //    offset, which will be the largest set of registers,
+  //  * Most indexes with non-zero offset will end up being interference units
+  //    anyway.
+  // So just pick those out and return them.
+
+  // We can rely on a single-byte stack index existing already, because we
+  // initialize them in MLocTracker.
+  auto It = MTracker->StackSlotIdxes.find({8, 0});
+  assert(It != MTracker->StackSlotIdxes.end());
+  Slots.push_back(It->second);
+
+  // Find anything that has a non-zero offset and add that too.
+  for (auto &Pair : MTracker->StackSlotIdxes) {
+    // Is offset zero? If so, ignore.
+    if (!Pair.first.second)
+      continue;
+    Slots.push_back(Pair.second);
+  }
+}
+
+void InstrRefBasedLDV::placeMLocPHIs(
+    MachineFunction &MF, SmallPtrSetImpl<MachineBasicBlock *> &AllBlocks,
+    ValueIDNum **MInLocs, SmallVectorImpl<MLocTransferMap> &MLocTransfer) {
+  SmallVector<unsigned, 4> StackUnits;
+  findStackIndexInterference(StackUnits);
+
   // 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 
+  // 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.
+  // those registers directly. Stack slots have their own form of "unit",
+  // store them to one side.
   SmallSet<Register, 32> RegUnitsToPHIUp;
-  SmallSet<LocIdx, 32> LocsToPHI;
+  SmallSet<LocIdx, 32> NormalLocsToPHI;
+  SmallSet<SpillLocationNo, 32> StackSlots;
   for (auto Location : MTracker->locations()) {
     LocIdx L = Location.Idx;
     if (MTracker->isSpill(L)) {
-      LocsToPHI.insert(L);
+      StackSlots.insert(MTracker->locIDToSpill(MTracker->LocIdxToLocID[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);
+      NormalLocsToPHI.insert(L);
       continue;
     }
 
     RegUnitsToPHIUp.insert(FoundRegUnits.begin(), FoundRegUnits.end());
   }
 
   // Lambda to fetch PHIs for a given location, and write into the PHIBlocks
   // collection.
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.
+  auto InstallPHIsAtLoc = [&PHIBlocks, &MInLocs](LocIdx L) {
     for (const MachineBasicBlock *MBB : PHIBlocks)
       MInLocs[MBB->getNumber()][L.asU64()] = ValueIDNum(MBB->getNumber(), 0, L);
+  };
+
+  // For locations with no reg units, just place PHIs.
+  for (LocIdx L : NormalLocsToPHI) {
+    CollectPHIsForLoc(L);
+    // Install those PHI values into the live-in value array.
+    InstallPHIsAtLoc(L);
+  }
+
+  // For stack slots, calculate PHIs for the equivalent of the units, then
+  // install for each index.
+  for (SpillLocationNo Slot : StackSlots) {
+    for (unsigned Idx : StackUnits) {
+      unsigned SpillID = MTracker->getSpillIDWithIdx(Slot, Idx);
+      LocIdx L = MTracker->getSpillMLoc(SpillID);
+      CollectPHIsForLoc(L);
+      InstallPHIsAtLoc(L);
+
+      // Find anything that aliases this stack index, install PHIs for it too.
+      unsigned Size, Offset;
+      std::tie(Size, Offset) = MTracker->StackIdxesToPos[Idx];
+      for (auto &Pair : MTracker->StackSlotIdxes) {
+        unsigned ThisSize, ThisOffset;
+        std::tie(ThisSize, ThisOffset) = Pair.first;
+        if (ThisSize + ThisOffset <= Offset || Size + Offset <= ThisOffset)
+          continue;
+
+        unsigned ThisID = MTracker->getSpillIDWithIdx(Slot, Pair.second);
+        LocIdx ThisL = MTracker->getSpillMLoc(ThisID);
+        InstallPHIsAtLoc(ThisL);
+      }
+    }
   }
 
   // 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);
+    InstallPHIsAtLoc(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);
+      InstallPHIsAtLoc(AliasLoc);
     }
   }
 }
 
 void InstrRefBasedLDV::buildMLocValueMap(
     MachineFunction &MF, ValueIDNum **MInLocs, ValueIDNum **MOutLocs,
     SmallVectorImpl<MLocTransferMap> &MLocTransfer) {
   std::priority_queue<unsigned int, std::vector<unsigned int>,

llvm/unittests/CodeGen/InstrRefLDVTest.cpp

public:
   }
 
   // Some routines for bouncing into LDV,
   void buildMLocValueMap(ValueIDNum **MInLocs, ValueIDNum **MOutLocs,
                          SmallVectorImpl<MLocTransferMap> &MLocTransfer) {
     LDV->buildMLocValueMap(*MF, MInLocs, MOutLocs, MLocTransfer);
   }
 
+  void placeMLocPHIs(MachineFunction &MF,
+                     SmallPtrSetImpl<MachineBasicBlock *> &AllBlocks,
+                     ValueIDNum **MInLocs,
+                     SmallVectorImpl<MLocTransferMap> &MLocTransfer) {
+    LDV->placeMLocPHIs(MF, AllBlocks, MInLocs, MLocTransfer);
+  }
+
   Optional<ValueIDNum>
   pickVPHILoc(const MachineBasicBlock &MBB, const DebugVariable &Var,
               const InstrRefBasedLDV::LiveIdxT &LiveOuts, ValueIDNum **MOutLocs,
               const SmallVectorImpl<const MachineBasicBlock *> &BlockOrders) {
     return LDV->pickVPHILoc(MBB, Var, LiveOuts, MOutLocs, BlockOrders);
   }
 
   bool vlocJoin(MachineBasicBlock &MBB, InstrRefBasedLDV::LiveIdxT &VLOCOutLocs,
TEST_F(InstrRefLDVTest, MLocDiamondBlocks) {
   EXPECT_EQ(OutLocs[1][0], LiveInRsp);
   EXPECT_EQ(OutLocs[2][0], LiveInRsp);
   EXPECT_EQ(OutLocs[3][0], LiveInRsp);
   TransferFunc[0].clear();
   TransferFunc[1].clear();
   TransferFunc[2].clear();
 }
 
+TEST_F(InstrRefLDVTest, MLocDiamondSpills) {
+  // Test that defs in stack locations that require PHIs, cause PHIs to be
+  // installed in aliasing locations. i.e., if there's a PHI in the lower
+  // 8 bits of the stack, there should be PHIs for 16/32/64 bit locations
+  // on the stack too.
+  // Technically this isn't needed for accuracy: we should calculate PHIs
+  // independently for each location. However, because there's an optimisation
+  // that only places PHIs for the lower "interfering" parts of stack slots,
+  // test for this behaviour.
+  setupDiamondBlocks();
+
+  ASSERT_TRUE(MTracker->getNumLocs() == 1);
+  LocIdx RspLoc(0);
+
+  // Create a stack location and ensure it's tracked.
+  SpillLoc SL = {getRegByName("RSP"), StackOffset::getFixed(-8)};
+  SpillLocationNo SpillNo = MTracker->getOrTrackSpillLoc(SL);
+  ASSERT_EQ(MTracker->getNumLocs(), 10u); // tracks all possible stack locs
+
+  // Pick out the locations on the stack that various x86 regs would be written
+  // to. HAX is the upper 16 bits of EAX.
+  unsigned ALID = MTracker->getLocID(SpillNo, {8, 0});
+  unsigned AHID = MTracker->getLocID(SpillNo, {8, 8});
+  unsigned AXID = MTracker->getLocID(SpillNo, {16, 0});
+  unsigned EAXID = MTracker->getLocID(SpillNo, {32, 0});
+  unsigned HAXID = MTracker->getLocID(SpillNo, {16, 16});
+  unsigned RAXID = MTracker->getLocID(SpillNo, {64, 0});
+  LocIdx ALStackLoc = MTracker->getSpillMLoc(ALID);
+  LocIdx AHStackLoc = MTracker->getSpillMLoc(AHID);
+  LocIdx AXStackLoc = MTracker->getSpillMLoc(AXID);
+  LocIdx EAXStackLoc = MTracker->getSpillMLoc(EAXID);
+  LocIdx HAXStackLoc = MTracker->getSpillMLoc(HAXID);
+  LocIdx RAXStackLoc = MTracker->getSpillMLoc(RAXID);
+  // There are other locations, for things like xmm0, which we're going to
+  // ignore here.
+
+  ValueIDNum InLocs[4][10];
+  ValueIDNum *InLocsPtr[4] = {InLocs[0], InLocs[1], InLocs[2], InLocs[3]};
+
+  // Transfer function: start with nothing.
+  SmallVector<MLocTransferMap, 1> TransferFunc;
+  TransferFunc.resize(4);
+
+  // Name some values.
+  unsigned EntryBlk = 0, Blk1 = 1, RetBlk = 3;
+
+  ValueIDNum LiveInRsp(EntryBlk, 0, RspLoc);
+  ValueIDNum ALLiveIn(EntryBlk, 0, ALStackLoc);
+  ValueIDNum AHLiveIn(EntryBlk, 0, AHStackLoc);
+  ValueIDNum HAXLiveIn(EntryBlk, 0, HAXStackLoc);
+  ValueIDNum ALPHI(RetBlk, 0, ALStackLoc);
+  ValueIDNum AXPHI(RetBlk, 0, AXStackLoc);
+  ValueIDNum EAXPHI(RetBlk, 0, EAXStackLoc);
+  ValueIDNum HAXPHI(RetBlk, 0, HAXStackLoc);
+  ValueIDNum RAXPHI(RetBlk, 0, RAXStackLoc);
+
+  ValueIDNum ALDefInBlk1(Blk1, 1, ALStackLoc);
+  ValueIDNum HAXDefInBlk1(Blk1, 1, HAXStackLoc);
+
+  SmallPtrSet<MachineBasicBlock *, 4> AllBlocks{MBB0, MBB1, MBB2, MBB3};
+
+  // If we put defs into one side of the diamond, for AL and HAX, then we should
+  // find all aliasing positions have PHIs placed. This isn't technically what
+  // the transfer function says to do: but we're testing that the optimisation
+  // to reduce IDF calculation does the right thing.
+  // AH should not be def'd: it don't alias AL or HAX.
+  //
+  // NB: we don't call buildMLocValueMap, because it will try to eliminate the
+  // upper-slot PHIs, and succeed because of our slightly cooked transfer
+  // function.
+  TransferFunc[1].insert({ALStackLoc, ALDefInBlk1});
+  TransferFunc[1].insert({HAXStackLoc, HAXDefInBlk1});
+  initValueArray(InLocsPtr, 4, 10);
+  placeMLocPHIs(*MF, AllBlocks, InLocsPtr, TransferFunc);
+  EXPECT_EQ(InLocs[3][ALStackLoc.asU64()], ALPHI);
+  EXPECT_EQ(InLocs[3][AXStackLoc.asU64()], AXPHI);
+  EXPECT_EQ(InLocs[3][EAXStackLoc.asU64()], EAXPHI);
+  EXPECT_EQ(InLocs[3][HAXStackLoc.asU64()], HAXPHI);
+  EXPECT_EQ(InLocs[3][RAXStackLoc.asU64()], RAXPHI);
+  // AH should be left untouched,
+  EXPECT_EQ(InLocs[3][AHStackLoc.asU64()], ValueIDNum::EmptyValue);
+
+}
+
 TEST_F(InstrRefLDVTest, MLocSimpleLoop) {
   //    entry
   //     |
   //     |/-----\
   //    loopblk |
   //     |\-----/
   //     |
   //     ret