[LiveDebugVariables] Add cache for SkipPHIsLabelsAndDebug to prevent iterating the same set of PHI/LABEL/Debug instructions repeatedly.

[wmi]

Summary

We run into a compiling timeout problem when building a target after its SampleFDO profile is updated. It is because some very large blocks with a bunch of PHIs at the beginning. LiveDebugVariables::emitDebugValues called during VirtRegRewriter phase searchs the insertion point for those large BBs repeatedly in SkipPHIsLabelsAndDebug, and each time SkipPHIsLabelsAndDebug needs to go through the same set of PHIs before it can find the first non PHI/Label/Debug instruction as an insertion point. This patch adds a cache to save the last position for the sequence which has been checked in the previous call of SkipPHIsLabelsAndDebug.

[wmi]

friendly ping.

[dblaikie]

llvm/lib/CodeGen/LiveDebugVariables.cpp

1310–1316

Could you store iterators in the map instead of pointers? Would save having to do the &* dance on the way in and the MachineBasicBlock::iterator dance on the way out?
Also, it'd be good to avoid the extra BBSkipInstsMap lookup, if possible. Would this work?

auto& I = BBSkipInstsMap.insert(MBB, MBB->begin()).first->second;
I = MBB->SkipPHIsLabelsAndDebug(I);
return I;

[wmi]

llvm/lib/CodeGen/LiveDebugVariables.cpp

1310–1316

Could you store iterators in the map instead of pointers? Would save having to do the &* dance on the way in and the MachineBasicBlock::iterator dance on the way out?

Good idea. MachineBasicBlock is an ilist so iterator should be valid after new instruction is inserted if ilist has the same property as std::list.

Also, it'd be good to avoid the extra BBSkipInstsMap lookup, if possible. Would this work?
auto& I = BBSkipInstsMap.insert(MBB, MBB->begin()).first->second;
I = MBB->SkipPHIsLabelsAndDebug(I);
return I;

That may not work. If we insert MBB->begin() into the map, after the last call of SkipPHIsLabelsAndDebug, there may be new non-phis/non-labels/non-debuginstrs inserted at the beginning of MBB and the old begin iterator saved in the map will become stale. When we call SkipPHIsLabelsAndDebug next time, it will skip those non-phis/labels/debug instructions which is not welcomed.

Note for the case that the return value of SkipPHIsLabelsAndDebug is not MBB->begin(), we will save std::prev of the returned iterator because the newly inserted instructions after last call of SkipPHIsLabelsAndDebug will be searched next time.

[wmi]

Address dblaikie's comment.

[dblaikie]

llvm/lib/CodeGen/LiveDebugVariables.cpp

1310–1316

Hmm, not quite following.

after the last call of SkipPHIsLabelsAndDebug, there may be new non-phis/non-labels/non-debuginstrs inserted at the beginning of MBB and the old begin iterator saved in the map will become stale. When we call SkipPHIsLabelsAndDebug next time, it will skip those non-phis/labels/debug instructions which is not welcomed.

Wouldn't that problem exist also... oh, I see. That's why you go back by 1.

Hmm. I guess if the map contained Optional<iterator> values it might look like this:

auto &O = BBSkipInstsMap[MBB];
auto B = MBB->Begin();
auto I = MBB->SkipPHIsLabelsAndDebug(O ? std::next(*O) : B);
if (I != B)
  O.emplace(std::prev(I));

Simplifies the code somewhat, avoids the double-lookup, but adds a bunch of memory overhead - making the values larger, and storing lots of None values where the current code avoids the entry entirely. So probably not worth it.

1311–1312

Is this comment incorrect? It sounds like from your other comments that MBB->begin() is never in the map?

1327

I guess this could be I != BeginIt - could save updates when the search doesn't find a new spot? & might be marginally cheaper comparison than calling begin() again?

[wmi]

llvm/lib/CodeGen/LiveDebugVariables.cpp

1311–1312

Good catch. Will fix it.

1327

That is better. Thanks.

[wmi]

Address David's comment.

llvm/lib/CodeGen/LiveDebugVariables.cpp

 
 /// Map of where a user value is live to that value.
 using LocMap = IntervalMap<SlotIndex, DbgVariableValue, 4>;
 
 /// Map of stack slot offsets for spilled locations.
 /// Non-spilled locations are not added to the map.
 using SpillOffsetMap = DenseMap<unsigned, unsigned>;
 
+/// Cache to save the location where it can be used as the starting
+/// position as input for calling MachineBasicBlock::SkipPHIsLabelsAndDebug.
+/// This is to prevent MachineBasicBlock::SkipPHIsLabelsAndDebug from
+/// repeatedly searching the same set of PHIs/Labels/Debug instructions
+/// if it is called many times for the same block.
+using BlockSkipInstsMap =
+    DenseMap<MachineBasicBlock *, MachineBasicBlock::iterator>;
+
 namespace {
 
 class LDVImpl;
 
 /// A user value is a part of a debug info user variable.
 ///
 /// A DBG_VALUE instruction notes that (a sub-register of) a virtual register
 /// holds part of a user variable. The part is identified by a byte offset.
class UserValue {
   /// lexical scope.
   SmallSet<SlotIndex, 2> trimmedDefs;
 
   /// Insert a DBG_VALUE into MBB at Idx for DbgValue.
   void insertDebugValue(MachineBasicBlock *MBB, SlotIndex StartIdx,
                         SlotIndex StopIdx, DbgVariableValue DbgValue,
                         bool Spilled, unsigned SpillOffset, LiveIntervals &LIS,
                         const TargetInstrInfo &TII,
-                        const TargetRegisterInfo &TRI);
+                        const TargetRegisterInfo &TRI,
+                        BlockSkipInstsMap &BBSkipInstsMap);
 
   /// Replace OldLocNo ranges with NewRegs ranges where NewRegs
   /// is live. Returns true if any changes were made.
   bool splitLocation(unsigned OldLocNo, ArrayRef<Register> NewRegs,
                      LiveIntervals &LIS);
 
 public:
   /// Create a new UserValue.
void rewriteLocations(VirtRegMap &VRM, const MachineFunction &MF,
                         const TargetInstrInfo &TII,
                         const TargetRegisterInfo &TRI,
                         SpillOffsetMap &SpillOffsets);
 
   /// Recreate DBG_VALUE instruction from data structures.
   void emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS,
                        const TargetInstrInfo &TII,
                        const TargetRegisterInfo &TRI,
-                       const SpillOffsetMap &SpillOffsets);
+                       const SpillOffsetMap &SpillOffsets,
+                       BlockSkipInstsMap &BBSkipInstsMap);
 
   /// Return DebugLoc of this UserValue.
   DebugLoc getDebugLoc() { return dl;}
 
   void print(raw_ostream &, const TargetRegisterInfo *);
 };
 
 /// A user label is a part of a debug info user label.
 class UserLabel {
   const DILabel *Label; ///< The debug info label we are part of.
   DebugLoc dl;          ///< The debug location for the label. This is
                         ///< used by dwarf writer to find lexical scope.
   SlotIndex loc;        ///< Slot used by the debug label.
 
   /// Insert a DBG_LABEL into MBB at Idx.
   void insertDebugLabel(MachineBasicBlock *MBB, SlotIndex Idx,
-                        LiveIntervals &LIS, const TargetInstrInfo &TII);
+                        LiveIntervals &LIS, const TargetInstrInfo &TII,
+                        BlockSkipInstsMap &BBSkipInstsMap);
 
 public:
   /// Create a new UserLabel.
   UserLabel(const DILabel *label, DebugLoc L, SlotIndex Idx)
       : Label(label), dl(std::move(L)), loc(Idx) {}
 
   /// Does this UserLabel match the parameters?
   bool matches(const DILabel *L, const DILocation *IA,
              const SlotIndex Index) const {
     return Label == L && dl->getInlinedAt() == IA && loc == Index;
   }
 
   /// Recreate DBG_LABEL instruction from data structures.
-  void emitDebugLabel(LiveIntervals &LIS, const TargetInstrInfo &TII);
+  void emitDebugLabel(LiveIntervals &LIS, const TargetInstrInfo &TII,
+                      BlockSkipInstsMap &BBSkipInstsMap);
 
   /// Return DebugLoc of this UserLabel.
   DebugLoc getDebugLoc() { return dl; }
 
   void print(raw_ostream &, const TargetRegisterInfo *);
 };
 
 /// Implementation of the LiveDebugVariables pass.
for (LocMap::iterator I = locInts.begin(); I.valid(); ++I) {
     unsigned NewLocNo = LocNoMap[DbgValue.getLocNo()];
     I.setValueUnchecked(DbgValue.changeLocNo(NewLocNo));
     I.setStart(I.start());
   }
 }
 
 /// Find an iterator for inserting a DBG_VALUE instruction.
 static MachineBasicBlock::iterator
-findInsertLocation(MachineBasicBlock *MBB, SlotIndex Idx,
-                   LiveIntervals &LIS) {
+findInsertLocation(MachineBasicBlock *MBB, SlotIndex Idx, LiveIntervals &LIS,
+                   BlockSkipInstsMap &BBSkipInstsMap) {
   SlotIndex Start = LIS.getMBBStartIdx(MBB);
   Idx = Idx.getBaseIndex();
 
   // Try to find an insert location by going backwards from Idx.
   MachineInstr *MI;
   while (!(MI = LIS.getInstructionFromIndex(Idx))) {
     // We've reached the beginning of MBB.
     if (Idx == Start) {
-      MachineBasicBlock::iterator I = MBB->SkipPHIsLabelsAndDebug(MBB->begin());
+      // Retrieve the last PHI/Label/Debug location found when calling
+      // SkipPHIsLabelsAndDebug last time. Start searching from there.
+      //
+      // Note the iterator kept in BBSkipInstsMap is one step back based
+      // on the iterator returned by SkipPHIsLabelsAndDebug last time.
+      // One exception is when SkipPHIsLabelsAndDebug returns MBB->begin(),
+      // BBSkipInstsMap won't save it. This is to consider the case that
+      // new instructions may be inserted at the beginning of MBB after
+      // last call of SkipPHIsLabelsAndDebug. If we save MBB->begin() in
+      // BBSkipInstsMap, after new non-phi/non-label/non-debug instructions
+      // are inserted at the beginning of the MBB, the iterator in
+      // BBSkipInstsMap won't point to the beginning of the MBB anymore.
+      // Therefore The next search in SkipPHIsLabelsAndDebug will skip those
+      // newly added instructions and that is unwanted.
+      MachineBasicBlock::iterator BeginIt;
+      auto MapIt = BBSkipInstsMap.find(MBB);
+      if (MapIt == BBSkipInstsMap.end())
+        BeginIt = MBB->begin();
+      else
+        BeginIt = std::next(MapIt->second);
+      auto I = MBB->SkipPHIsLabelsAndDebug(BeginIt);
+      if (I != BeginIt)
+        BBSkipInstsMap[MBB] = std::prev(I);
       return I;
     }
     Idx = Idx.getPrevIndex();
   }
 
   // Don't insert anything after the first terminator, though.
   return MI->isTerminator() ? MBB->getFirstTerminator() :
                               std::next(MachineBasicBlock::iterator(MI));
findNextInsertLocation(MachineBasicBlock *MBB,
   }
   return MBB->end();
 }
 
 void UserValue::insertDebugValue(MachineBasicBlock *MBB, SlotIndex StartIdx,
                                  SlotIndex StopIdx, DbgVariableValue DbgValue,
                                  bool Spilled, unsigned SpillOffset,
                                  LiveIntervals &LIS, const TargetInstrInfo &TII,
-                                 const TargetRegisterInfo &TRI) {
+                                 const TargetRegisterInfo &TRI,
+                                 BlockSkipInstsMap &BBSkipInstsMap) {
   SlotIndex MBBEndIdx = LIS.getMBBEndIdx(&*MBB);
   // Only search within the current MBB.
   StopIdx = (MBBEndIdx < StopIdx) ? MBBEndIdx : StopIdx;
-  MachineBasicBlock::iterator I = findInsertLocation(MBB, StartIdx, LIS);
+  MachineBasicBlock::iterator I =
+      findInsertLocation(MBB, StartIdx, LIS, BBSkipInstsMap);
   // Undef values don't exist in locations so create new "noreg" register MOs
   // for them. See getLocationNo().
   MachineOperand MO =
       !DbgValue.isUndef()
           ? locations[DbgValue.getLocNo()]
           : MachineOperand::CreateReg(
                 /* Reg */ 0, /* isDef */ false, /* isImp */ false,
                 /* isKill */ false, /* isDead */ false,
do {
 
     // Continue and insert DBG_VALUES after every redefinition of register
     // associated with the debug value within the range
     I = findNextInsertLocation(MBB, I, StopIdx, MO, LIS, TRI);
   } while (I != MBB->end());
 }
 
 void UserLabel::insertDebugLabel(MachineBasicBlock *MBB, SlotIndex Idx,
-                                 LiveIntervals &LIS,
-                                 const TargetInstrInfo &TII) {
-  MachineBasicBlock::iterator I = findInsertLocation(MBB, Idx, LIS);
+                                 LiveIntervals &LIS, const TargetInstrInfo &TII,
+                                 BlockSkipInstsMap &BBSkipInstsMap) {
+  MachineBasicBlock::iterator I =
+      findInsertLocation(MBB, Idx, LIS, BBSkipInstsMap);
   ++NumInsertedDebugLabels;
   BuildMI(*MBB, I, getDebugLoc(), TII.get(TargetOpcode::DBG_LABEL))
       .addMetadata(Label);
 }
 
 void UserValue::emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS,
                                 const TargetInstrInfo &TII,
                                 const TargetRegisterInfo &TRI,
-                                const SpillOffsetMap &SpillOffsets) {
+                                const SpillOffsetMap &SpillOffsets,
+                                BlockSkipInstsMap &BBSkipInstsMap) {
   MachineFunction::iterator MFEnd = VRM->getMachineFunction().end();
 
   for (LocMap::const_iterator I = locInts.begin(); I.valid();) {
     SlotIndex Start = I.start();
     SlotIndex Stop = I.stop();
     DbgVariableValue DbgValue = I.value();
     auto SpillIt = !DbgValue.isUndef() ? SpillOffsets.find(DbgValue.getLocNo())
                                        : SpillOffsets.end();
     bool Spilled = SpillIt != SpillOffsets.end();
     unsigned SpillOffset = Spilled ? SpillIt->second : 0;
 
     // If the interval start was trimmed to the lexical scope insert the
     // DBG_VALUE at the previous index (otherwise it appears after the
     // first instruction in the range).
     if (trimmedDefs.count(Start))
       Start = Start.getPrevIndex();
 
     LLVM_DEBUG(dbgs() << "\t[" << Start << ';' << Stop
                       << "):" << DbgValue.getLocNo());
     MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start)->getIterator();
     SlotIndex MBBEnd = LIS.getMBBEndIdx(&*MBB);
 
     LLVM_DEBUG(dbgs() << ' ' << printMBBReference(*MBB) << '-' << MBBEnd);
     insertDebugValue(&*MBB, Start, Stop, DbgValue, Spilled, SpillOffset, LIS,
-                     TII, TRI);
+                     TII, TRI, BBSkipInstsMap);
     // This interval may span multiple basic blocks.
     // Insert a DBG_VALUE into each one.
     while (Stop > MBBEnd) {
       // Move to the next block.
       Start = MBBEnd;
       if (++MBB == MFEnd)
         break;
       MBBEnd = LIS.getMBBEndIdx(&*MBB);
       LLVM_DEBUG(dbgs() << ' ' << printMBBReference(*MBB) << '-' << MBBEnd);
       insertDebugValue(&*MBB, Start, Stop, DbgValue, Spilled, SpillOffset, LIS,
-                       TII, TRI);
+                       TII, TRI, BBSkipInstsMap);
     }
     LLVM_DEBUG(dbgs() << '\n');
     if (MBB == MFEnd)
       break;
 
     ++I;
   }
 }
 
-void UserLabel::emitDebugLabel(LiveIntervals &LIS, const TargetInstrInfo &TII) {
+void UserLabel::emitDebugLabel(LiveIntervals &LIS, const TargetInstrInfo &TII,
+                               BlockSkipInstsMap &BBSkipInstsMap) {
   LLVM_DEBUG(dbgs() << "\t" << loc);
   MachineFunction::iterator MBB = LIS.getMBBFromIndex(loc)->getIterator();
 
   LLVM_DEBUG(dbgs() << ' ' << printMBBReference(*MBB));
-  insertDebugLabel(&*MBB, loc, LIS, TII);
+  insertDebugLabel(&*MBB, loc, LIS, TII, BBSkipInstsMap);
 
   LLVM_DEBUG(dbgs() << '\n');
 }
 
 void LDVImpl::emitDebugValues(VirtRegMap *VRM) {
   LLVM_DEBUG(dbgs() << "********** EMITTING LIVE DEBUG VARIABLES **********\n");
   if (!MF)
     return;
+
+  BlockSkipInstsMap BBSkipInstsMap;
   const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
   SpillOffsetMap SpillOffsets;
   for (auto &userValue : userValues) {
     LLVM_DEBUG(userValue->print(dbgs(), TRI));
     userValue->rewriteLocations(*VRM, *MF, *TII, *TRI, SpillOffsets);
-    userValue->emitDebugValues(VRM, *LIS, *TII, *TRI, SpillOffsets);
+    userValue->emitDebugValues(VRM, *LIS, *TII, *TRI, SpillOffsets,
+                               BBSkipInstsMap);
   }
   LLVM_DEBUG(dbgs() << "********** EMITTING LIVE DEBUG LABELS **********\n");
   for (auto &userLabel : userLabels) {
     LLVM_DEBUG(userLabel->print(dbgs(), TRI));
-    userLabel->emitDebugLabel(*LIS, *TII);
+    userLabel->emitDebugLabel(*LIS, *TII, BBSkipInstsMap);
   }
 
   LLVM_DEBUG(dbgs() << "********** EMITTING INSTR REFERENCES **********\n");
 
   // Re-insert any DBG_INSTR_REFs back in the position they were. Ordering
   // is preserved by vector.
   auto Slots = LIS->getSlotIndexes();
   const MCInstrDesc &RefII = TII->get(TargetOpcode::DBG_INSTR_REF);
   for (auto &P : StashedInstrReferences) {
     const SlotIndex &Idx = P.first;
     auto *MBB = Slots->getMBBFromIndex(Idx);
-    MachineBasicBlock::iterator insertPos = findInsertLocation(MBB, Idx, *LIS);
+    MachineBasicBlock::iterator insertPos =
+        findInsertLocation(MBB, Idx, *LIS, BBSkipInstsMap);
     for (auto &Stashed : P.second) {
       auto MIB = BuildMI(*MF, std::get<4>(Stashed), RefII);
       MIB.addImm(std::get<0>(Stashed));
       MIB.addImm(std::get<1>(Stashed));
       MIB.addMetadata(std::get<2>(Stashed));
       MIB.addMetadata(std::get<3>(Stashed));
       MachineInstr *New = MIB;
       MBB->insert(insertPos, New);
     }
   }
 
   EmitDone = true;
+  BBSkipInstsMap.clear();
 }
 
 void LiveDebugVariables::emitDebugValues(VirtRegMap *VRM) {
   if (pImpl)
     static_cast<LDVImpl*>(pImpl)->emitDebugValues(VRM);
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void LiveDebugVariables::dump() const {
   if (pImpl)
     static_cast<LDVImpl*>(pImpl)->print(dbgs());
 }
 #endif