Change representation of instruction ranges where variable is accessible.

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.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@209698 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 110 insertions, 99 deletions

diff --git a/lib/CodeGen/AsmPrinter/DbgValueHistoryCalculator.cpp b/lib/CodeGen/AsmPrinter/DbgValueHistoryCalculator.cpp
index 450d154138..61032548ea 100644
--- a/lib/CodeGen/AsmPrinter/DbgValueHistoryCalculator.cpp
+++ b/lib/CodeGen/AsmPrinter/DbgValueHistoryCalculator.cpp
@@ -20,11 +20,6 @@
 
 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.
@@ -36,6 +31,47 @@ static unsigned isDescribedByReg(const MachineInstr &MI) {
   return MI.getOperand(0).isReg() ? MI.getOperand(0).getReg() : 0;
 }
 
+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) {
@@ -54,16 +90,9 @@ static void dropRegDescribedVar(RegDescribedVarsMap &RegVars,
 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
@@ -77,11 +106,11 @@ static void clobberRegisterUses(RegDescribedVarsMap &RegVars, unsigned RegNo,
   // 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,
@@ -105,31 +134,10 @@ static void clobberAllRegistersUses(RegDescribedVarsMap &RegVars,
                                     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) {
@@ -146,16 +154,14 @@ void calculateDbgValueHistory(const MachineFunction *MF,
 
       assert(MI.getNumOperands() > 1 && "Invalid DBG_VALUE 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
diff --git a/lib/CodeGen/AsmPrinter/DbgValueHistoryCalculator.h b/lib/CodeGen/AsmPrinter/DbgValueHistoryCalculator.h
index db5116df1b..b9177f0595 100644
--- a/lib/CodeGen/AsmPrinter/DbgValueHistoryCalculator.h
+++ b/lib/CodeGen/AsmPrinter/DbgValueHistoryCalculator.h
@@ -20,12 +20,31 @@ 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:
+  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,
diff --git a/lib/CodeGen/AsmPrinter/DwarfDebug.cpp b/lib/CodeGen/AsmPrinter/DwarfDebug.cpp
index e4e19cc91f..2a0615d74f 100644
--- a/lib/CodeGen/AsmPrinter/DwarfDebug.cpp
+++ b/lib/CodeGen/AsmPrinter/DwarfDebug.cpp
@@ -1153,12 +1153,10 @@ DwarfDebug::collectVariableInfo(SmallPtrSet<const MDNode *, 16> &Processed) {
     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 &&
@@ -1175,6 +1173,7 @@ DwarfDebug::collectVariableInfo(SmallPtrSet<const MDNode *, 16> &Processed) {
       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);
@@ -1183,9 +1182,8 @@ DwarfDebug::collectVariableInfo(SmallPtrSet<const MDNode *, 16> &Processed) {
     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;
     }
@@ -1198,42 +1196,31 @@ DwarfDebug::collectVariableInfo(SmallPtrSet<const MDNode *, 16> &Processed) {
     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;
-        }
-      }
+      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!");
 
-      // The value is valid until the next DBG_VALUE or clobber.
-      DebugLocEntry Loc(FLabel, SLabel, getDebugLocValue(Begin), TheCU);
+      DEBUG(dbgs() << "DotDebugLoc Pair:\n"
+                   << "\t" << *Begin << "\t" << *End << "\n");
+      DebugLocEntry Loc(StartLabel, EndLabel, getDebugLocValue(Begin), TheCU);
       if (DebugLoc.empty() || !DebugLoc.back().Merge(Loc))
         DebugLoc.push_back(std::move(Loc));
     }
@@ -1416,9 +1403,9 @@ void DwarfDebug::beginFunction(const MachineFunction *MF) {
   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
@@ -1426,13 +1413,12 @@ void DwarfDebug::beginFunction(const MachineFunction *MF) {
     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);
     }
   }