lib/CodeGen/AsmPrinter/DbgEntityHistoryCalculator.cpp

   1 //===- llvm/CodeGen/AsmPrinter/DbgEntityHistoryCalculator.cpp -------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/CodeGen/DbgEntityHistoryCalculator.h"
  10 #include "llvm/ADT/BitVector.h"
  11 #include "llvm/ADT/STLExtras.h"
  12 #include "llvm/ADT/SmallSet.h"
  13 #include "llvm/ADT/SmallVector.h"
  14 #include "llvm/CodeGen/MachineBasicBlock.h"
  15 #include "llvm/CodeGen/MachineFunction.h"
  16 #include "llvm/CodeGen/MachineInstr.h"
  17 #include "llvm/CodeGen/MachineOperand.h"
  18 #include "llvm/CodeGen/TargetLowering.h"
  19 #include "llvm/CodeGen/TargetRegisterInfo.h"
  20 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  21 #include "llvm/IR/DebugInfoMetadata.h"
  22 #include "llvm/IR/DebugLoc.h"
  23 #include "llvm/MC/MCRegisterInfo.h"
  24 #include "llvm/Support/Debug.h"
  25 #include "llvm/Support/raw_ostream.h"
  26 #include <cassert>
  27 #include <map>
  28 #include <utility>
  29
  30 using namespace llvm;
  31
  32 #define DEBUG_TYPE "dwarfdebug"
  33
  34 namespace {
  35 using EntryIndex = DbgValueHistoryMap::EntryIndex;
  36 }
  37
  38 // If @MI is a DBG_VALUE with debug value described by a
  39 // defined register, returns the number of this register.
  40 // In the other case, returns 0.
  41 static Register isDescribedByReg(const MachineInstr &MI) {
  42   assert(MI.isDebugValue());
  43   assert(MI.getNumOperands() == 4);
  44   // If the location of variable is an entry value (DW_OP_entry_value)
  45   // do not consider it as a register location.
  46   if (MI.getDebugExpression()->isEntryValue())
  47     return 0;
  48   // If location of variable is described using a register (directly or
  49   // indirectly), this register is always a first operand.
  50   return MI.getOperand(0).isReg() ? MI.getOperand(0).getReg() : Register();
  51 }
  52
  53 bool DbgValueHistoryMap::startDbgValue(InlinedEntity Var,
  54                                        const MachineInstr &MI,
  55                                        EntryIndex &NewIndex) {
  56   // Instruction range should start with a DBG_VALUE instruction for the
  57   // variable.
  58   assert(MI.isDebugValue() && "not a DBG_VALUE");
  59   auto &Entries = VarEntries[Var];
  60   if (!Entries.empty() && Entries.back().isDbgValue() &&
  61       !Entries.back().isClosed() &&
  62       Entries.back().getInstr()->isIdenticalTo(MI)) {
  63     LLVM_DEBUG(dbgs() << "Coalescing identical DBG_VALUE entries:\n"
  64                       << "\t" << Entries.back().getInstr() << "\t" << MI
  65                       << "\n");
  66     return false;
  67   }
  68   Entries.emplace_back(&MI, Entry::DbgValue);
  69   NewIndex = Entries.size() - 1;
  70   return true;
  71 }
  72
  73 EntryIndex DbgValueHistoryMap::startClobber(InlinedEntity Var,
  74                                             const MachineInstr &MI) {
  75   auto &Entries = VarEntries[Var];
  76   // If an instruction clobbers multiple registers that the variable is
  77   // described by, then we may have already created a clobbering instruction.
  78   if (Entries.back().isClobber() && Entries.back().getInstr() == &MI)
  79     return Entries.size() - 1;
  80   Entries.emplace_back(&MI, Entry::Clobber);
  81   return Entries.size() - 1;
  82 }
  83
  84 void DbgValueHistoryMap::Entry::endEntry(EntryIndex Index) {
  85   // For now, instruction ranges are not allowed to cross basic block
  86   // boundaries.
  87   assert(isDbgValue() && "Setting end index for non-debug value");
  88   assert(!isClosed() && "End index has already been set");
  89   EndIndex = Index;
  90 }
  91
  92 void DbgLabelInstrMap::addInstr(InlinedEntity Label, const MachineInstr &MI) {
  93   assert(MI.isDebugLabel() && "not a DBG_LABEL");
  94   LabelInstr[Label] = &MI;
  95 }
  96
  97 namespace {
  98
  99 // Maps physreg numbers to the variables they describe.
 100 using InlinedEntity = DbgValueHistoryMap::InlinedEntity;
 101 using RegDescribedVarsMap = std::map<unsigned, SmallVector<InlinedEntity, 1>>;
 102
 103 // Keeps track of the debug value entries that are currently live for each
 104 // inlined entity. As the history map entries are stored in a SmallVector, they
 105 // may be moved at insertion of new entries, so store indices rather than
 106 // pointers.
 107 using DbgValueEntriesMap = std::map<InlinedEntity, SmallSet<EntryIndex, 1>>;
 108
 109 } // end anonymous namespace
 110
 111 // Claim that @Var is not described by @RegNo anymore.
 112 static void dropRegDescribedVar(RegDescribedVarsMap &RegVars, unsigned RegNo,
 113                                 InlinedEntity Var) {
 114   const auto &I = RegVars.find(RegNo);
 115   assert(RegNo != 0U && I != RegVars.end());
 116   auto &VarSet = I->second;
 117   const auto &VarPos = llvm::find(VarSet, Var);
 118   assert(VarPos != VarSet.end());
 119   VarSet.erase(VarPos);
 120   // Don't keep empty sets in a map to keep it as small as possible.
 121   if (VarSet.empty())
 122     RegVars.erase(I);
 123 }
 124
 125 // Claim that @Var is now described by @RegNo.
 126 static void addRegDescribedVar(RegDescribedVarsMap &RegVars, unsigned RegNo,
 127                                InlinedEntity Var) {
 128   assert(RegNo != 0U);
 129   auto &VarSet = RegVars[RegNo];
 130   assert(!is_contained(VarSet, Var));
 131   VarSet.push_back(Var);
 132 }
 133
 134 /// Create a clobbering entry and end all open debug value entries
 135 /// for \p Var that are described by \p RegNo using that entry.
 136 static void clobberRegEntries(InlinedEntity Var, unsigned RegNo,
 137                               const MachineInstr &ClobberingInstr,
 138                               DbgValueEntriesMap &LiveEntries,
 139                               DbgValueHistoryMap &HistMap) {
 140   EntryIndex ClobberIndex = HistMap.startClobber(Var, ClobberingInstr);
 141
 142   // Close all entries whose values are described by the register.
 143   SmallVector<EntryIndex, 4> IndicesToErase;
 144   for (auto Index : LiveEntries[Var]) {
 145     auto &Entry = HistMap.getEntry(Var, Index);
 146     assert(Entry.isDbgValue() && "Not a DBG_VALUE in LiveEntries");
 147     if (isDescribedByReg(*Entry.getInstr()) == RegNo) {
 148       IndicesToErase.push_back(Index);
 149       Entry.endEntry(ClobberIndex);
 150     }
 151   }
 152
 153   // Drop all entries that have ended.
 154   for (auto Index : IndicesToErase)
 155     LiveEntries[Var].erase(Index);
 156 }
 157
 158 /// Add a new debug value for \p Var. Closes all overlapping debug values.
 159 static void handleNewDebugValue(InlinedEntity Var, const MachineInstr &DV,
 160                                 RegDescribedVarsMap &RegVars,
 161                                 DbgValueEntriesMap &LiveEntries,
 162                                 DbgValueHistoryMap &HistMap) {
 163   EntryIndex NewIndex;
 164   if (HistMap.startDbgValue(Var, DV, NewIndex)) {
 165     SmallDenseMap<unsigned, bool, 4> TrackedRegs;
 166
 167     // If we have created a new debug value entry, close all preceding
 168     // live entries that overlap.
 169     SmallVector<EntryIndex, 4> IndicesToErase;
 170     const DIExpression *DIExpr = DV.getDebugExpression();
 171     for (auto Index : LiveEntries[Var]) {
 172       auto &Entry = HistMap.getEntry(Var, Index);
 173       assert(Entry.isDbgValue() && "Not a DBG_VALUE in LiveEntries");
 174       const MachineInstr &DV = *Entry.getInstr();
 175       bool Overlaps = DIExpr->fragmentsOverlap(DV.getDebugExpression());
 176       if (Overlaps) {
 177         IndicesToErase.push_back(Index);
 178         Entry.endEntry(NewIndex);
 179       }
 180       if (Register Reg = isDescribedByReg(DV))
 181         TrackedRegs[Reg] |= !Overlaps;
 182     }
 183
 184     // If the new debug value is described by a register, add tracking of
 185     // that register if it is not already tracked.
 186     if (Register NewReg = isDescribedByReg(DV)) {
 187       if (!TrackedRegs.count(NewReg))
 188         addRegDescribedVar(RegVars, NewReg, Var);
 189       LiveEntries[Var].insert(NewIndex);
 190       TrackedRegs[NewReg] = true;
 191     }
 192
 193     // Drop tracking of registers that are no longer used.
 194     for (auto I : TrackedRegs)
 195       if (!I.second)
 196         dropRegDescribedVar(RegVars, I.first, Var);
 197
 198     // Drop all entries that have ended, and mark the new entry as live.
 199     for (auto Index : IndicesToErase)
 200       LiveEntries[Var].erase(Index);
 201     LiveEntries[Var].insert(NewIndex);
 202   }
 203 }
 204
 205 // Terminate the location range for variables described by register at
 206 // @I by inserting @ClobberingInstr to their history.
 207 static void clobberRegisterUses(RegDescribedVarsMap &RegVars,
 208                                 RegDescribedVarsMap::iterator I,
 209                                 DbgValueHistoryMap &HistMap,
 210                                 DbgValueEntriesMap &LiveEntries,
 211                                 const MachineInstr &ClobberingInstr) {
 212   // Iterate over all variables described by this register and add this
 213   // instruction to their history, clobbering it.
 214   for (const auto &Var : I->second)
 215     clobberRegEntries(Var, I->first, ClobberingInstr, LiveEntries, HistMap);
 216   RegVars.erase(I);
 217 }
 218
 219 // Terminate the location range for variables described by register
 220 // @RegNo by inserting @ClobberingInstr to their history.
 221 static void clobberRegisterUses(RegDescribedVarsMap &RegVars, unsigned RegNo,
 222                                 DbgValueHistoryMap &HistMap,
 223                                 DbgValueEntriesMap &LiveEntries,
 224                                 const MachineInstr &ClobberingInstr) {
 225   const auto &I = RegVars.find(RegNo);
 226   if (I == RegVars.end())
 227     return;
 228   clobberRegisterUses(RegVars, I, HistMap, LiveEntries, ClobberingInstr);
 229 }
 230
 231 void llvm::calculateDbgEntityHistory(const MachineFunction *MF,
 232                                      const TargetRegisterInfo *TRI,
 233                                      DbgValueHistoryMap &DbgValues,
 234                                      DbgLabelInstrMap &DbgLabels) {
 235   const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
 236   unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
 237   Register FrameReg = TRI->getFrameRegister(*MF);
 238   RegDescribedVarsMap RegVars;
 239   DbgValueEntriesMap LiveEntries;
 240   for (const auto &MBB : *MF) {
 241     for (const auto &MI : MBB) {
 242       if (MI.isDebugValue()) {
 243         assert(MI.getNumOperands() > 1 && "Invalid DBG_VALUE instruction!");
 244         // Use the base variable (without any DW_OP_piece expressions)
 245         // as index into History. The full variables including the
 246         // piece expressions are attached to the MI.
 247         const DILocalVariable *RawVar = MI.getDebugVariable();
 248         assert(RawVar->isValidLocationForIntrinsic(MI.getDebugLoc()) &&
 249                "Expected inlined-at fields to agree");
 250         InlinedEntity Var(RawVar, MI.getDebugLoc()->getInlinedAt());
 251
 252         handleNewDebugValue(Var, MI, RegVars, LiveEntries, DbgValues);
 253       } else if (MI.isDebugLabel()) {
 254         assert(MI.getNumOperands() == 1 && "Invalid DBG_LABEL instruction!");
 255         const DILabel *RawLabel = MI.getDebugLabel();
 256         assert(RawLabel->isValidLocationForIntrinsic(MI.getDebugLoc()) &&
 257             "Expected inlined-at fields to agree");
 258         // When collecting debug information for labels, there is no MCSymbol
 259         // generated for it. So, we keep MachineInstr in DbgLabels in order
 260         // to query MCSymbol afterward.
 261         InlinedEntity L(RawLabel, MI.getDebugLoc()->getInlinedAt());
 262         DbgLabels.addInstr(L, MI);
 263       }
 264
 265       if (MI.isDebugInstr())
 266         continue;
 267
 268       // Not a DBG_VALUE instruction. It may clobber registers which describe
 269       // some variables.
 270       for (const MachineOperand &MO : MI.operands()) {
 271         if (MO.isReg() && MO.isDef() && MO.getReg()) {
 272           // Ignore call instructions that claim to clobber SP. The AArch64
 273           // backend does this for aggregate function arguments.
 274           if (MI.isCall() && MO.getReg() == SP)
 275             continue;
 276           // If this is a virtual register, only clobber it since it doesn't
 277           // have aliases.
 278           if (Register::isVirtualRegister(MO.getReg()))
 279             clobberRegisterUses(RegVars, MO.getReg(), DbgValues, LiveEntries,
 280                                 MI);
 281           // If this is a register def operand, it may end a debug value
 282           // range. Ignore frame-register defs in the epilogue and prologue,
 283           // we expect debuggers to understand that stack-locations are
 284           // invalid outside of the function body.
 285           else if (MO.getReg() != FrameReg ||
 286                    (!MI.getFlag(MachineInstr::FrameDestroy) &&
 287                    !MI.getFlag(MachineInstr::FrameSetup))) {
 288             for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid();
 289                  ++AI)
 290               clobberRegisterUses(RegVars, *AI, DbgValues, LiveEntries, MI);
 291           }
 292         } else if (MO.isRegMask()) {
 293           // If this is a register mask operand, clobber all debug values in
 294           // non-CSRs.
 295           SmallVector<unsigned, 32> RegsToClobber;
 296           // Don't consider SP to be clobbered by register masks.
 297           for (auto It : RegVars) {
 298             unsigned int Reg = It.first;
 299             if (Reg != SP && Register::isPhysicalRegister(Reg) &&
 300                 MO.clobbersPhysReg(Reg))
 301               RegsToClobber.push_back(Reg);
 302           }
 303
 304           for (unsigned Reg : RegsToClobber) {
 305             clobberRegisterUses(RegVars, Reg, DbgValues, LiveEntries, MI);
 306           }
 307         }
 308       } // End MO loop.
 309     }   // End instr loop.
 310
 311     // Make sure locations for all variables are valid only until the end of
 312     // the basic block (unless it's the last basic block, in which case let
 313     // their liveness run off to the end of the function).
 314     if (!MBB.empty() && &MBB != &MF->back()) {
 315       // Iterate over all variables that have open debug values.
 316       for (auto &Pair : LiveEntries) {
 317         if (Pair.second.empty())
 318           continue;
 319
 320         // Create a clobbering entry.
 321         EntryIndex ClobIdx = DbgValues.startClobber(Pair.first, MBB.back());
 322
 323         // End all entries.
 324         for (EntryIndex Idx : Pair.second) {
 325           DbgValueHistoryMap::Entry &Ent = DbgValues.getEntry(Pair.first, Idx);
 326           assert(Ent.isDbgValue() && !Ent.isClosed());
 327           Ent.endEntry(ClobIdx);
 328         }
 329       }
 330
 331       LiveEntries.clear();
 332       RegVars.clear();
 333     }
 334   }
 335 }
 336
 337 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 338 LLVM_DUMP_METHOD void DbgValueHistoryMap::dump() const {
 339   dbgs() << "DbgValueHistoryMap:\n";
 340   for (const auto &VarRangePair : *this) {
 341     const InlinedEntity &Var = VarRangePair.first;
 342     const Entries &Entries = VarRangePair.second;
 343
 344     const DILocalVariable *LocalVar = cast<DILocalVariable>(Var.first);
 345     const DILocation *Location = Var.second;
 346
 347     dbgs() << " - " << LocalVar->getName() << " at ";
 348
 349     if (Location)
 350       dbgs() << Location->getFilename() << ":" << Location->getLine() << ":"
 351              << Location->getColumn();
 352     else
 353       dbgs() << "<unknown location>";
 354
 355     dbgs() << " --\n";
 356
 357     for (const auto &E : enumerate(Entries)) {
 358       const auto &Entry = E.value();
 359       dbgs() << "  Entry[" << E.index() << "]: ";
 360       if (Entry.isDbgValue())
 361         dbgs() << "Debug value\n";
 362       else
 363         dbgs() << "Clobber\n";
 364       dbgs() << "   Instr: " << *Entry.getInstr();
 365       if (Entry.isDbgValue()) {
 366         if (Entry.getEndIndex() == NoEntry)
 367           dbgs() << "   - Valid until end of function\n";
 368         else
 369           dbgs() << "   - Closed by Entry[" << Entry.getEndIndex() << "]\n";
 370       }
 371       dbgs() << "\n";
 372     }
 373   }
 374 }
 375 #endif