[WIP] improve debug-info in stack-slot-coloring

[markus]

Summary

In response to https://bugs.llvm.org/show_bug.cgi?id=50072

[markus]

Prototype of the 'terminate debug-info for slots when they go out of liveness, before being merged' idea in the TR.

[jmorse]

Looks good as a starting place -- I took this for test drive, see inline comments. On a clang-3.4 build, the "PC ranges covered" statistic ticks down from 66% to 65%, however I believe that's due to rounding. Using llvm-locstats, roughly six thousand variables move out of the 100% covered bucket, or about 0.2% of all variables in clang-3.4. 0% covered goes up by a negligible amount. In my opinion: this is a reasonable sacrifice to make in the name of accuracy, and some of those dropped locations will be incorrect. Plus, there's a longer term plan for not needing this.

The LiveIntervals range only identifies spans of instructions: it doesn't contain any information about control flow. There can be scenarios where a stack slot goes out of liveness but doesn't get terminated by this implementation: for example, when we branch out of of a block, the branch target might be somewhere where the slot isn't live.

Seeing how this is a pragmatic fix to eliminate some false locations, I don't think we need to cover all circumstances with a patch like this -- up to you if you want to cover the extra scenarios.

llvm/lib/CodeGen/StackSlotColoring.cpp

548

I get an assertion about SS being a tombstone value for SS2DbgValues, sometimes it comes out as -2. Elsewhere there are loops that continue/bypass if FI is negative, perhaps that's needed here?

569

Needs to clear the collections you added to the pass

[markus]

In D101064#2722608, @jmorse wrote:

Looks good as a starting place -- I took this for test drive, see inline comments. On a clang-3.4 build, the "PC ranges covered" statistic ticks down from 66% to 65%, however I believe that's due to rounding. Using llvm-locstats, roughly six thousand variables move out of the 100% covered bucket, or about 0.2% of all variables in clang-3.4. 0% covered goes up by a negligible amount. In my opinion: this is a reasonable sacrifice to make in the name of accuracy, and some of those dropped locations will be incorrect. Plus, there's a longer term plan for not needing this.

Doesn't sound too bad then. Thanks for testing!

The LiveIntervals range only identifies spans of instructions: it doesn't contain any information about control flow. There can be scenarios where a stack slot goes out of liveness but doesn't get terminated by this implementation: for example, when we branch out of of a block, the branch target might be somewhere where the slot isn't live.

That is a good point and I actually had not thought about that. I guess it is not too hard to fix though as one can; look for branches leaving these LiveIntervals and terminate at the point of the branch target is that is not also live.

Should be enough right?

Seeing how this is a pragmatic fix to eliminate some false locations, I don't think we need to cover all circumstances with a patch like this -- up to you if you want to cover the extra scenarios.

I will give it a try.

[jmorse]

[Digging back through my inbox,]

In D101064#2724952, @markus wrote:

That is a good point and I actually had not thought about that. I guess it is not too hard to fix though as one can; look for branches leaving these LiveIntervals and terminate at the point of the branch target is that is not also live.

Should be enough right?

Sounds good to me, again there's a small risk that legitimate locations will be terminated when they shouldn't. But, we'll still be able to make an educated judgement about whether it's worth it.

[markus]

In D101064#2768775, @jmorse wrote:

Sounds good to me, again there's a small risk that legitimate locations will be terminated when they shouldn't. But, we'll still be able to make an educated judgement about whether it's worth it.

Yes, may be a bit overconservative but should at least be correct. I gave it a go and then got sidetracked by other tasks. Seems it was not as easy as I originally thought as a SlotIndex does not always map to an instruction (or something like that IIRC). Will try to pick it up again in a not too distant future.

llvm/lib/CodeGen/StackSlotColoring.cpp

 
 STATISTIC(NumEliminated, "Number of stack slots eliminated due to coloring");
 STATISTIC(NumDead,       "Number of trivially dead stack accesses eliminated");
 
 namespace {
 
   class StackSlotColoring : public MachineFunctionPass {
     LiveStacks* LS;
+    SlotIndexes *Indexes;
     MachineFrameInfo *MFI;
     const TargetInstrInfo  *TII;
     const MachineBlockFrequencyInfo *MBFI;
 
     // SSIntervals - Spill slot intervals.
     std::vector<LiveInterval*> SSIntervals;
 
     // SSRefs - Keep a list of MachineMemOperands for each spill slot.
     // MachineMemOperands can be shared between instructions, so we need
     // to be careful that renames like [FI0, FI1] -> [FI1, FI2] do not
     // become FI0 -> FI1 -> FI2.
     SmallVector<SmallVector<MachineMemOperand *, 8>, 16> SSRefs;
+    DenseMap<unsigned, SmallVector<MachineInstr *, 8>> SS2DbgValues;
+    DenseMap<unsigned, LiveInterval *> SS2LI;
 
     // OrigAlignments - Alignments of stack objects before coloring.
     SmallVector<Align, 16> OrigAlignments;
 
     // OrigSizes - Sizess of stack objects before coloring.
     SmallVector<unsigned, 16> OrigSizes;
 
     // AllColors - If index is set, it's a spill slot, i.e. color.
private:
     void InitializeSlots();
     void ScanForSpillSlotRefs(MachineFunction &MF);
     bool OverlapWithAssignments(LiveInterval *li, int Color) const;
     int ColorSlot(LiveInterval *li);
     bool ColorSlots(MachineFunction &MF);
     void RewriteInstruction(MachineInstr &MI, SmallVectorImpl<int> &SlotMapping,
                             MachineFunction &MF);
     bool RemoveDeadStores(MachineBasicBlock* MBB);
+    void TerminateDbgForSlot(unsigned FI, LiveInterval *LI);
   };
 
 } // end anonymous namespace
 
 char StackSlotColoring::ID = 0;
 
 char &llvm::StackSlotColoringID = StackSlotColoring::ID;
 
int StackSlotColoring::ColorSlot(LiveInterval *li) {
   }
 
   assert(MFI->getStackID(Color) == MFI->getStackID(FI));
 
   // Record the assignment.
   Assignments[Color].push_back(li);
   LLVM_DEBUG(dbgs() << "Assigning fi#" << FI << " to fi#" << Color << "\n");
 
+  if (FI != Color)
+    TerminateDbgForSlot(Color, SS2LI[Color]);
+
   // Change size and alignment of the allocated slot. If there are multiple
   // objects sharing the same slot, then make sure the size and alignment
   // are large enough for all.
   Align Alignment = OrigAlignments[FI];
   if (!Share || Alignment > MFI->getObjectAlign(Color))
     MFI->setObjectAlignment(Color, Alignment);
   int64_t Size = OrigSizes[FI];
   if (!Share || Size > MFI->getObjectSize(Color))
bool StackSlotColoring::RemoveDeadStores(MachineBasicBlock* MBB) {
   }
 
   for (MachineInstr *MI : toErase)
     MI->eraseFromParent();
 
   return changed;
 }
 
+/// Terminate the DBG_VALUE(s) of variables residing in stack-slot with
+/// frame-index FI at the Segment.end points of LI.
+void StackSlotColoring::TerminateDbgForSlot(unsigned FI, LiveInterval *LI) {
+  for (auto &Seg : *LI) {
+    if (auto *SegEndMI = Indexes->getInstructionFromIndex(Seg.end)) {
+      for (auto *DbgValue : SS2DbgValues[FI]) {
+        auto ItMI = SegEndMI->getIterator();
+        BuildMI(*SegEndMI->getParent(), ItMI, DbgValue->getDebugLoc(),
+                TII->get(TargetOpcode::DBG_VALUE))
+            .addReg(0) // $noreg
+            .add(DbgValue->getOperand(1))
+            .add(DbgValue->getOperand(2))
+            .add(DbgValue->getOperand(3));
+      }
+    }
+  }
+}
+
 bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) {
   LLVM_DEBUG({
     dbgs() << "********** Stack Slot Coloring **********\n"
            << "********** Function: " << MF.getName() << '\n';
   });
 
   if (skipFunction(MF.getFunction()))
     return false;
 
   MFI = &MF.getFrameInfo();
   TII = MF.getSubtarget().getInstrInfo();
   LS = &getAnalysis<LiveStacks>();
   MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
+  Indexes = &getAnalysis<SlotIndexes>();
 
   bool Changed = false;
 
   unsigned NumSlots = LS->getNumIntervals();
   if (NumSlots == 0)
     // Nothing to do!
     return false;
 
   // If there are calls to setjmp or sigsetjmp, don't perform stack slot
   // coloring. The stack could be modified before the longjmp is executed,
   // resulting in the wrong value being used afterwards. (See
   // <rdar://problem/8007500>.)
   if (MF.exposesReturnsTwice())
     return false;
 
   // Gather spill slot references
   ScanForSpillSlotRefs(MF);
   InitializeSlots();
+
+  // Create mapping of SS -> LiveInterval.
+  for (unsigned i = 0; i < SSIntervals.size(); i++) {
+    LiveInterval *li = SSIntervals[i];
+    int SS = Register::stackSlot2Index(li->reg());
+    SS2LI[SS] = li;
+  }
+
+  // Create mapping of SS -> DBG_VALUE(s).
+  for (MachineBasicBlock &MBB : MF) {
+    for (MachineInstr &MI : MBB) {
+      if (MI.isDebugValue() && MI.getOperand(0).isFI()) {
+        auto SS = MI.getOperand(0).getIndex();
+        SS2DbgValues[SS].push_back(&MI);
+      }
+    }
+  }
+
   Changed = ColorSlots(MF);
 
   for (int &Next : NextColors)
     Next = -1;
 
   SSIntervals.clear();
   for (unsigned i = 0, e = SSRefs.size(); i != e; ++i)
     SSRefs[i].clear();
   SSRefs.clear();
   OrigAlignments.clear();
   OrigSizes.clear();
   AllColors.clear();
   UsedColors.clear();
   for (unsigned i = 0, e = Assignments.size(); i != e; ++i)
     Assignments[i].clear();
   Assignments.clear();
 
   return Changed;
 }