Change representation of instruction ranges where variable is accessible.

[samsonov]

Summary

Use more straightforward way to represent the set of instruction
ranges where the location of a user variable is defined - vector of pairs
of instructions (defining start/end of each range),
instead of a flattened vector of instructions where some instructions
are supposed to start the range, and the rest are supposed to "clobber" it.

Simplify the code which generates actual .debug_loc entries.

No functionality change.

[samsonov]

Rebase to trunk (and test the email change).

[dblaikie]

Coming through loud & clear!

[dblaikie]

lib/CodeGen/AsmPrinter/DbgValueHistoryCalculator.cpp

117

Sorry, but I forget/don't understand why/how this code was no longer necessary.

Could you explain why it was necessary before your patch and how your patch makes it unnecessary?

Hmm, I think I see - it moved into startInstrRange, did it?

lib/CodeGen/AsmPrinter/DwarfDebug.cpp

1190

You can drop this initialization, since the 3 cases below ensure the variable is initialized (this way, msan can catch bugs if that is ever violated)

1191

This if/else if chain could be done without braces, if you like (seems to be the way of things in the LLVM codebase).

1380–1381

I'd probably drop the braces from all these - might be worth refactoring into a simple utility function to make this larger function more readable/simpler.

1389

Did the need for this ahead-of-time initialization of the MapVector go away in your change? How?

1398

I assume the case where the start of a range is non-null and the end of the range is null occurs for whole-function ranges? (we don't record the termination)

In that case, would it make sense to just record the location as an unbounded range (null for both start/end? No range? (I guess that'd be ambiguous with "variable is totally optimized away", though))

[samsonov]

lib/CodeGen/AsmPrinter/DbgValueHistoryCalculator.cpp

117

Not sure what logic you refer to. dropRegDescribedVar/addRegDescribedVar pair moved to calculateDbgValueHistory, so that now we have:

• mark that the variable is no longer described by old register (if it has been).
• start the new location range for a variable
• mark that the variable is described by a new register (if necessary).

lib/CodeGen/AsmPrinter/DwarfDebug.cpp

1190

Done

1191

Done

1380–1381

Done (and moved this function call closer to the place where PrologEndLoc is used for the first time).

1389

Yes, it went away. Need for ahead-of-time initialization is somewhat ugly, this really should be responsibility of calculateDbgValueHistory().

calculateDbgValueHistory() traverses all machine instructions in function, and the first time we see a DBG_VALUE for a new variable, it will
be added to map by the call to "startInstrRange()".

1398

Not necessarily, see description of what a range is in DbgValueHistoryCalculator.h: if we have

DBG_VALUE %r1 %noreg !"v"
...
DBG_VALUE %r2 %noreg !"v"

the range for this first DBG_VALUE will not be explicitly terminated - we assume it's valid until the next range begins.

[samsonov]

Address comments.

[samsonov]

Any more comments on this?

[dblaikie]

lib/CodeGen/AsmPrinter/DwarfDebug.cpp

1389

Was there a reason this wasn't possible previously? (I seem to recall this was kept around in the previous commit to provide stability to the output? - why is the "on first use" order stable now?)

It might've been helpful to pull this out as a separate commit if it's an isolated piece of cleanup (if it's not isolated I wouldn't mind unedrstanding what is it about the rest of your change that changed things here so that this was no longer needed)

[samsonov]

Thanks for the review!

lib/CodeGen/AsmPrinter/DwarfDebug.cpp

1389

Good point, looks like it's possible with current code as well (apparently, it became possible as code evolved during the review).
I will put this into a separate commit.

[samsonov]

Landed as r209698.

lib/CodeGen/AsmPrinter/DbgValueHistoryCalculator.h

 
 namespace llvm {
 
 class MachineFunction;
 class MachineInstr;
 class MDNode;
 class TargetRegisterInfo;
 
-// For each user variable, keep a list of DBG_VALUE instructions for it
-// in the order of appearance. The list can also contain another
-// instructions, which are assumed to clobber the previous DBG_VALUE.
-// The variables are listed in order of appearance.
-typedef MapVector<const MDNode *, SmallVector<const MachineInstr *, 4>>
-DbgValueHistoryMap;
+// For each user variable, keep a list of instruction ranges where this variable
+// is accessible. The variables are listed in order of appearance.
+class DbgValueHistoryMap {
+  // Each instruction range starts with a DBG_VALUE instruction, specifying the
+  // location of a variable, which is assumed to be valid until the end of the
+  // range. If end is not specified, location is valid until the start
+  // instruction of the next instruction range, or until the end of the
+  // function.
+  typedef std::pair<const MachineInstr *, const MachineInstr *> InstrRange;
+  typedef SmallVector<InstrRange, 4> InstrRanges;
+  typedef MapVector<const MDNode *, InstrRanges> InstrRangesMap;
+  InstrRangesMap VarInstrRanges;
+
+public:
+  DbgValueHistoryMap();
+
+  void startInstrRange(const MDNode *Var, const MachineInstr &MI);
+  void endInstrRange(const MDNode *Var, const MachineInstr &MI);
+  // Returns register currently describing @Var. If @Var is currently
+  // unaccessible or is not described by a register, returns 0.
+  unsigned getRegisterForVar(const MDNode *Var) const;
+
+  bool empty() const { return VarInstrRanges.empty(); }
+  void clear() { VarInstrRanges.clear(); }
+  InstrRangesMap::const_iterator begin() const { return VarInstrRanges.begin(); }
+  InstrRangesMap::const_iterator end() const { return VarInstrRanges.end(); }
+};
 
 void calculateDbgValueHistory(const MachineFunction *MF,
                               const TargetRegisterInfo *TRI,
                               DbgValueHistoryMap &Result);
 }
 
 #endif

lib/CodeGen/AsmPrinter/DbgValueHistoryCalculator.cpp

 #include "llvm/Target/TargetRegisterInfo.h"
 #include <algorithm>
 #include <map>
 
 #define DEBUG_TYPE "dwarfdebug"
 
 namespace llvm {
 
-namespace {
-// Maps physreg numbers to the variables they describe.
-typedef std::map<unsigned, SmallVector<const MDNode *, 1>> RegDescribedVarsMap;
-}
-
 // \brief If @MI is a DBG_VALUE with debug value described by a
 // defined register, returns the number of this register.
 // In the other case, returns 0.
 static unsigned isDescribedByReg(const MachineInstr &MI) {
   assert(MI.isDebugValue());
   assert(MI.getNumOperands() == 3);
   // If location of variable is described using a register (directly or
   // indirecltly), this register is always a first operand.
   return MI.getOperand(0).isReg() ? MI.getOperand(0).getReg() : 0;
 }
 
+DbgValueHistoryMap::DbgValueHistoryMap() {}
+
+void DbgValueHistoryMap::startInstrRange(const MDNode *Var,
+                                         const MachineInstr &MI) {
+  // Instruction range should start with a DBG_VALUE instruction for the
+  // variable.
+  assert(MI.isDebugValue() && MI.getDebugVariable() == Var);
+  auto &Ranges = VarInstrRanges[Var];
+  if (!Ranges.empty() && Ranges.back().second == nullptr &&
+      Ranges.back().first->isIdenticalTo(&MI)) {
+    DEBUG(dbgs() << "Coalescing identical DBG_VALUE entries:\n"
+                 << "\t" << Ranges.back().first << "\t" << MI << "\n");
+    return;
+  }
+  Ranges.push_back(std::make_pair(&MI, nullptr));
+}
+
+void DbgValueHistoryMap::endInstrRange(const MDNode *Var,
+                                       const MachineInstr &MI) {
+  auto &Ranges = VarInstrRanges[Var];
+  // Verify that the current instruction range is not yet closed.
+  assert(!Ranges.empty() && Ranges.back().second == nullptr);
+  // For now, instruction ranges are not allowed to cross basic block
+  // boundaries.
+  assert(Ranges.back().first->getParent() == MI.getParent());
+  Ranges.back().second = &MI;
+}
+
+unsigned DbgValueHistoryMap::getRegisterForVar(const MDNode *Var) const {
+  const auto &I = VarInstrRanges.find(Var);
+  if (I == VarInstrRanges.end())
+    return 0;
+  const auto &Ranges = I->second;
+  if (Ranges.empty() || Ranges.back().second != nullptr)
+    return 0;
+  return isDescribedByReg(*Ranges.back().first);
+}
+
+namespace {
+// Maps physreg numbers to the variables they describe.
+typedef std::map<unsigned, SmallVector<const MDNode *, 1>> RegDescribedVarsMap;
+}
+
 // \brief Claim that @Var is not described by @RegNo anymore.
 static void dropRegDescribedVar(RegDescribedVarsMap &RegVars,
                                 unsigned RegNo, const MDNode *Var) {
   const auto &I = RegVars.find(RegNo);
   assert(RegNo != 0U && I != RegVars.end());
   auto &VarSet = I->second;
   const auto &VarPos = std::find(VarSet.begin(), VarSet.end(), Var);
   assert(VarPos != VarSet.end());
   VarSet.erase(VarPos);
   // Don't keep empty sets in a map to keep it as small as possible.
   if (VarSet.empty())
     RegVars.erase(I);
 }
 
 // \brief Claim that @Var is now described by @RegNo.
 static void addRegDescribedVar(RegDescribedVarsMap &RegVars,
                                unsigned RegNo, const MDNode *Var) {
   assert(RegNo != 0U);
-  RegVars[RegNo].push_back(Var);
-}
-
-static void clobberVariableLocation(SmallVectorImpl<const MachineInstr *> &VarHistory,
-                                    const MachineInstr &ClobberingInstr) {
-  assert(!VarHistory.empty());
-  // DBG_VALUE we're clobbering should belong to the same MBB.
-  assert(VarHistory.back()->isDebugValue());
-  assert(VarHistory.back()->getParent() == ClobberingInstr.getParent());
-  VarHistory.push_back(&ClobberingInstr);
+  auto &VarSet = RegVars[RegNo];
+  assert(std::find(VarSet.begin(), VarSet.end(), Var) == VarSet.end());
+  VarSet.push_back(Var);
 }
 
 // \brief Terminate the location range for variables described by register
 // @RegNo by inserting @ClobberingInstr to their history.
 static void clobberRegisterUses(RegDescribedVarsMap &RegVars, unsigned RegNo,
                                 DbgValueHistoryMap &HistMap,
                                 const MachineInstr &ClobberingInstr) {
   const auto &I = RegVars.find(RegNo);
   if (I == RegVars.end())
     return;
   // Iterate over all variables described by this register and add this
   // instruction to their history, clobbering it.
   for (const auto &Var : I->second)
-    clobberVariableLocation(HistMap[Var], ClobberingInstr);
+    HistMap.endInstrRange(Var, ClobberingInstr);
   RegVars.erase(I);
 }
 
-// \brief Terminate the location range for all variables, described by registers
+// \brief Terminate location ranges for all variables, described by registers
 // clobbered by @MI.
 static void clobberRegisterUses(RegDescribedVarsMap &RegVars,
                                 const MachineInstr &MI,
                                 const TargetRegisterInfo *TRI,
                                 DbgValueHistoryMap &HistMap) {
   for (const MachineOperand &MO : MI.operands()) {
     if (!MO.isReg() || !MO.isDef() || !MO.getReg())
       continue;
     for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid();
          ++AI) {
       unsigned RegNo = *AI;
       clobberRegisterUses(RegVars, RegNo, HistMap, MI);
     }
   }
 }
 
 // \brief Terminate the location range for all register-described variables
 // by inserting @ClobberingInstr to their history.
 static void clobberAllRegistersUses(RegDescribedVarsMap &RegVars,
                                     DbgValueHistoryMap &HistMap,
                                     const MachineInstr &ClobberingInstr) {
   for (const auto &I : RegVars)
     for (const auto &Var : I.second)
-      clobberVariableLocation(HistMap[Var], ClobberingInstr);
+      HistMap.endInstrRange(Var, ClobberingInstr);
   RegVars.clear();
 }
 
-// \brief Update the register that describes location of @Var in @RegVars map.
-static void
-updateRegForVariable(RegDescribedVarsMap &RegVars, const MDNode *Var,
-                     const SmallVectorImpl<const MachineInstr *> &VarHistory,
-                     const MachineInstr &MI) {
-  if (!VarHistory.empty()) {
-     const MachineInstr &Prev = *VarHistory.back();
-     // Check if Var is currently described by a register by instruction in the
-     // same basic block.
-     if (Prev.isDebugValue() && Prev.getDebugVariable() == Var &&
-         Prev.getParent() == MI.getParent()) {
-       if (unsigned PrevReg = isDescribedByReg(Prev))
-         dropRegDescribedVar(RegVars, PrevReg, Var);
-     }
-  }
-
-  assert(MI.getDebugVariable() == Var);
-  if (unsigned MIReg = isDescribedByReg(MI))
-    addRegDescribedVar(RegVars, MIReg, Var);
-}
-
 void calculateDbgValueHistory(const MachineFunction *MF,
                               const TargetRegisterInfo *TRI,
                               DbgValueHistoryMap &Result) {
   RegDescribedVarsMap RegVars;
 
   for (const auto &MBB : *MF) {
     for (const auto &MI : MBB) {
       if (!MI.isDebugValue()) {
         // Not a DBG_VALUE instruction. It may clobber registers which describe
         // some variables.
         clobberRegisterUses(RegVars, MI, TRI, Result);
         continue;
       }
 
+      assert(MI.getNumOperands() > 1 && "Invalid machine instruction!");
       const MDNode *Var = MI.getDebugVariable();
-      auto &History = Result[Var];
 
-      if (!History.empty() && History.back()->isIdenticalTo(&MI)) {
-        DEBUG(dbgs() << "Coalescing identical DBG_VALUE entries:\n"
-                     << "\t" << History.back() << "\t" << MI << "\n");
-        continue;
-      }
+      if (unsigned PrevReg = Result.getRegisterForVar(Var))
+        dropRegDescribedVar(RegVars, PrevReg, Var);
+
+      Result.startInstrRange(Var, MI);
 
-      updateRegForVariable(RegVars, Var, History, MI);
-      History.push_back(&MI);
+      if (unsigned NewReg = isDescribedByReg(MI))
+        addRegDescribedVar(RegVars, NewReg, Var);
     }
 
     // Make sure locations for register-described variables are valid only
     // until the end of the basic block (unless it's the last basic block, in
     // which case let their liveness run off to the end of the function).
     if (!MBB.empty() &&  &MBB != &MF->back())
       clobberAllRegistersUses(RegVars, Result, MBB.back());
   }
 }
 
 }

lib/CodeGen/AsmPrinter/DwarfDebug.cpp

DwarfDebug::collectVariableInfo(SmallPtrSet<const MDNode *, 16> &Processed) {
   // Grab the variable info that was squirreled away in the MMI side-table.
   collectVariableInfoFromMMITable(Processed);
 
   for (const auto &I : DbgValues) {
     DIVariable DV(I.first);
     if (Processed.count(DV))
       continue;
 
-    // History contains relevant DBG_VALUE instructions for DV and instructions
-    // clobbering it.
-    const SmallVectorImpl<const MachineInstr *> &History = I.second;
-    if (History.empty())
+    // Instruction ranges, specifying where DV is accessible.
+    const auto &Ranges = I.second;
+    if (Ranges.empty())
       continue;
-    const MachineInstr *MInsn = History.front();
 
     LexicalScope *Scope = nullptr;
     if (DV.getTag() == dwarf::DW_TAG_arg_variable &&
         DISubprogram(DV.getContext()).describes(CurFn->getFunction()))
       Scope = LScopes.getCurrentFunctionScope();
     else if (MDNode *IA = DV.getInlinedAt()) {
       DebugLoc DL = DebugLoc::getFromDILocation(IA);
       Scope = LScopes.findInlinedScope(DebugLoc::get(
           DL.getLine(), DL.getCol(), DV.getContext(), IA));
     } else
       Scope = LScopes.findLexicalScope(DV.getContext());
     // If variable scope is not found then skip this variable.
     if (!Scope)
       continue;
-
     Processed.insert(DV);
+
+    const MachineInstr *MInsn = Ranges.front().first;
     assert(MInsn->isDebugValue() && "History must begin with debug value");
     DbgVariable *AbsVar = findAbstractVariable(DV, MInsn->getDebugLoc());
     DbgVariable *RegVar = new DbgVariable(DV, AbsVar, this);
     if (!addCurrentFnArgument(RegVar, Scope))
       addScopeVariable(Scope, RegVar);
     if (AbsVar)
       AbsVar->setMInsn(MInsn);
 
-    // Simplify ranges that are fully coalesced.
-    if (History.size() <= 1 ||
-        (History.size() == 2 && MInsn->isIdenticalTo(History.back()))) {
+    // Check if the first DBG_VALUE is valid for the rest of the function.
+    if (Ranges.size() == 1 && Ranges.front().second == nullptr) {
       RegVar->setMInsn(MInsn);
       continue;
     }
 
     // Handle multiple DBG_VALUE instructions describing one variable.
     RegVar->setDotDebugLocOffset(DotDebugLocEntries.size());
 
     DotDebugLocEntries.resize(DotDebugLocEntries.size() + 1);
     DebugLocList &LocList = DotDebugLocEntries.back();
     LocList.Label =
         Asm->GetTempSymbol("debug_loc", DotDebugLocEntries.size() - 1);
     SmallVector<DebugLocEntry, 4> &DebugLoc = LocList.List;
-    for (SmallVectorImpl<const MachineInstr *>::const_iterator
-             HI = History.begin(),
-             HE = History.end();
-         HI != HE; ++HI) {
-      const MachineInstr *Begin = *HI;
+    for (auto I = Ranges.begin(), E = Ranges.end(); I != E; ++I) {
+      const MachineInstr *Begin = I->first;
+      const MachineInstr *End = I->second;
       assert(Begin->isDebugValue() && "Invalid History entry");
-
-      // Check if DBG_VALUE is truncating a range.
+      // Check if a variable is unaccessible in this range.
       if (Begin->getNumOperands() > 1 && Begin->getOperand(0).isReg() &&
           !Begin->getOperand(0).getReg())
         continue;
 
-      // Compute the range for a register location.
-      const MCSymbol *FLabel = getLabelBeforeInsn(Begin);
-      const MCSymbol *SLabel = nullptr;
-
-      if (HI + 1 == HE)
-        // If Begin is the last instruction in History then its value is valid
-        // until the end of the function.
-        SLabel = FunctionEndSym;
-      else {
-        const MachineInstr *End = HI[1];
-        DEBUG(dbgs() << "DotDebugLoc Pair:\n"
-                     << "\t" << *Begin << "\t" << *End << "\n");
-        if (End->isDebugValue() && End->getDebugVariable() == DV)
-          SLabel = getLabelBeforeInsn(End);
-        else {
-          // End is clobbering the range.
-          SLabel = getLabelAfterInsn(End);
-          assert(SLabel && "Forgot label after clobber instruction");
-          ++HI;
-        }
-      }
-
-      // The value is valid until the next DBG_VALUE or clobber.
-      DebugLocEntry Loc(FLabel, SLabel, getDebugLocValue(Begin), TheCU);
+      const MCSymbol *StartLabel = getLabelBeforeInsn(Begin);
+      assert(StartLabel && "Forgot label before DBG_VALUE starting a range!");
+
+      const MCSymbol *EndLabel;
+      if (End != nullptr)
+        EndLabel = getLabelAfterInsn(End);
+      else if (std::next(I) == Ranges.end())
+        EndLabel = FunctionEndSym;
+      else
+        EndLabel = getLabelBeforeInsn(std::next(I)->first);
+      assert(EndLabel && "Forgot label after instruction ending a range!");
+
+      DebugLocEntry Loc(StartLabel, EndLabel, getDebugLocValue(Begin), TheCU);
       if (DebugLoc.empty() || !DebugLoc.back().Merge(Loc))
         DebugLoc.push_back(std::move(Loc));
     }
   }
 
   // Collect info for variables that were optimized out.
   DIArray Variables = DISubprogram(FnScope->getScopeNode()).getVariables();
   for (unsigned i = 0, e = Variables.getNumElements(); i != e; ++i) {
for (const InsnRange &R : S->getRanges()) {
       assert(R.first && "InsnRange does not have first instruction!");
       assert(R.second && "InsnRange does not have second instruction!");
       requestLabelBeforeInsn(R.first);
       requestLabelAfterInsn(R.second);
     }
   }
 }
 
+static DebugLoc findPrologueEndLoc(const MachineFunction *MF) {
+  // First known non-DBG_VALUE and non-frame setup location marks
+  // the beginning of the function body.
+  for (const auto &MBB : *MF)
+    for (const auto &MI : MBB)
+      if (!MI.isDebugValue() && !MI.getFlag(MachineInstr::FrameSetup) &&
+          !MI.getDebugLoc().isUnknown())
+        return MI.getDebugLoc();
+  return DebugLoc();
+}
+
 // Gather pre-function debug information.  Assumes being called immediately
 // after the function entry point has been emitted.
 void DwarfDebug::beginFunction(const MachineFunction *MF) {
   CurFn = MF;
 
   // If there's no debug info for the function we're not going to do anything.
   if (!MMI->hasDebugInfo())
     return;
if (Asm->OutStreamer.hasRawTextSupport())
     Asm->OutStreamer.getContext().setDwarfCompileUnitID(0);
   else
     Asm->OutStreamer.getContext().setDwarfCompileUnitID(TheCU->getUniqueID());
 
   // Emit a label for the function so that we have a beginning address.
   FunctionBeginSym = Asm->GetTempSymbol("func_begin", Asm->getFunctionNumber());
   // Assumes in correct section after the entry point.
   Asm->OutStreamer.EmitLabel(FunctionBeginSym);
 
-  // Collect user variables, find the end of the prologue.
-  for (const auto &MBB : *MF) {
-    for (const auto &MI : MBB) {
-      if (MI.isDebugValue()) {
-        assert(MI.getNumOperands() > 1 && "Invalid machine instruction!");
-        // Keep track of user variables in order of appearance. Create the
-        // empty history for each variable so that the order of keys in
-        // DbgValues is correct. Actual history will be populated in
-        // calculateDbgValueHistory() function.
-        const MDNode *Var = MI.getDebugVariable();
-        DbgValues.insert(
-            std::make_pair(Var, SmallVector<const MachineInstr *, 4>()));
-      } else if (!MI.getFlag(MachineInstr::FrameSetup) &&
-                 PrologEndLoc.isUnknown() && !MI.getDebugLoc().isUnknown()) {
-        // First known non-DBG_VALUE and non-frame setup location marks
-        // the beginning of the function body.
-        PrologEndLoc = MI.getDebugLoc();
-      }
-    }
-  }
-
   // Calculate history for local variables.
   calculateDbgValueHistory(MF, Asm->TM.getRegisterInfo(), DbgValues);
 
   // Request labels for the full history.
-  for (auto &I : DbgValues) {
-    const SmallVectorImpl<const MachineInstr *> &History = I.second;
-    if (History.empty())
+  for (const auto &I : DbgValues) {
+    const auto &Ranges = I.second;
+    if (Ranges.empty())
       continue;
 
     // The first mention of a function argument gets the FunctionBeginSym
     // label, so arguments are visible when breaking at function entry.
     DIVariable DV(I.first);
     if (DV.isVariable() && DV.getTag() == dwarf::DW_TAG_arg_variable &&
         getDISubprogram(DV.getContext()).describes(MF->getFunction()))
-      LabelsBeforeInsn[History.front()] = FunctionBeginSym;
+      LabelsBeforeInsn[Ranges.front().first] = FunctionBeginSym;
 
-    for (const MachineInstr *MI : History) {
-      if (MI->isDebugValue() && MI->getDebugVariable() == DV)
-        requestLabelBeforeInsn(MI);
-      else
-        requestLabelAfterInsn(MI);
+    for (const auto &Range : Ranges) {
+      requestLabelBeforeInsn(Range.first);
+      if (Range.second)
+        requestLabelAfterInsn(Range.second);
     }
   }
 
   PrevInstLoc = DebugLoc();
   PrevLabel = FunctionBeginSym;
 
   // Record beginning of function.
+  PrologEndLoc = findPrologueEndLoc(MF);
   if (!PrologEndLoc.isUnknown()) {
     DebugLoc FnStartDL =
         PrologEndLoc.getFnDebugLoc(MF->getFunction()->getContext());
     recordSourceLine(
         FnStartDL.getLine(), FnStartDL.getCol(),
         FnStartDL.getScope(MF->getFunction()->getContext()),
         // We'd like to list the prologue as "not statements" but GDB behaves
         // poorly if we do that. Revisit this with caution/GDB (7.5+) testing.