LCOV - code coverage report
Current view: top level - lib/CodeGen - LiveDebugValues.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 234 234 100.0 %
Date: 2017-09-14 15:23:50 Functions: 25 26 96.2 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- LiveDebugValues.cpp - Tracking Debug Value MIs ---------------------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : ///
      10             : /// This pass implements a data flow analysis that propagates debug location
      11             : /// information by inserting additional DBG_VALUE instructions into the machine
      12             : /// instruction stream. The pass internally builds debug location liveness
      13             : /// ranges to determine the points where additional DBG_VALUEs need to be
      14             : /// inserted.
      15             : ///
      16             : /// This is a separate pass from DbgValueHistoryCalculator to facilitate
      17             : /// testing and improve modularity.
      18             : ///
      19             : //===----------------------------------------------------------------------===//
      20             : 
      21             : #include "llvm/ADT/DenseMap.h"
      22             : #include "llvm/ADT/PostOrderIterator.h"
      23             : #include "llvm/ADT/SmallPtrSet.h"
      24             : #include "llvm/ADT/SmallVector.h"
      25             : #include "llvm/ADT/SparseBitVector.h"
      26             : #include "llvm/ADT/Statistic.h"
      27             : #include "llvm/ADT/UniqueVector.h"
      28             : #include "llvm/CodeGen/LexicalScopes.h"
      29             : #include "llvm/CodeGen/MachineBasicBlock.h"
      30             : #include "llvm/CodeGen/MachineFrameInfo.h"
      31             : #include "llvm/CodeGen/MachineFunction.h"
      32             : #include "llvm/CodeGen/MachineFunctionPass.h"
      33             : #include "llvm/CodeGen/MachineInstr.h"
      34             : #include "llvm/CodeGen/MachineInstrBuilder.h"
      35             : #include "llvm/CodeGen/MachineMemOperand.h"
      36             : #include "llvm/CodeGen/MachineModuleInfo.h"
      37             : #include "llvm/CodeGen/MachineOperand.h"
      38             : #include "llvm/CodeGen/PseudoSourceValue.h"
      39             : #include "llvm/IR/DebugInfoMetadata.h"
      40             : #include "llvm/IR/DebugLoc.h"
      41             : #include "llvm/IR/Function.h"
      42             : #include "llvm/IR/Module.h"
      43             : #include "llvm/MC/MCRegisterInfo.h"
      44             : #include "llvm/Pass.h"
      45             : #include "llvm/Support/Casting.h"
      46             : #include "llvm/Support/Compiler.h"
      47             : #include "llvm/Support/Debug.h"
      48             : #include "llvm/Support/raw_ostream.h"
      49             : #include "llvm/Target/TargetFrameLowering.h"
      50             : #include "llvm/Target/TargetInstrInfo.h"
      51             : #include "llvm/Target/TargetLowering.h"
      52             : #include "llvm/Target/TargetRegisterInfo.h"
      53             : #include "llvm/Target/TargetSubtargetInfo.h"
      54             : #include <algorithm>
      55             : #include <cassert>
      56             : #include <cstdint>
      57             : #include <functional>
      58             : #include <queue>
      59             : #include <utility>
      60             : #include <vector>
      61             : 
      62             : using namespace llvm;
      63             : 
      64             : #define DEBUG_TYPE "livedebugvalues"
      65             : 
      66             : STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted");
      67             : 
      68             : // \brief If @MI is a DBG_VALUE with debug value described by a defined
      69             : // register, returns the number of this register. In the other case, returns 0.
      70             : static unsigned isDbgValueDescribedByReg(const MachineInstr &MI) {
      71             :   assert(MI.isDebugValue() && "expected a DBG_VALUE");
      72             :   assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
      73             :   // If location of variable is described using a register (directly
      74             :   // or indirectly), this register is always a first operand.
      75      184290 :   return MI.getOperand(0).isReg() ? MI.getOperand(0).getReg() : 0;
      76             : }
      77             : 
      78             : namespace {
      79             : 
      80       16605 : class LiveDebugValues : public MachineFunctionPass {
      81             : private:
      82             :   const TargetRegisterInfo *TRI;
      83             :   const TargetInstrInfo *TII;
      84             :   const TargetFrameLowering *TFI;
      85             :   LexicalScopes LS;
      86             : 
      87             :   /// Keeps track of lexical scopes associated with a user value's source
      88             :   /// location.
      89      349884 :   class UserValueScopes {
      90             :     DebugLoc DL;
      91             :     LexicalScopes &LS;
      92             :     SmallPtrSet<const MachineBasicBlock *, 4> LBlocks;
      93             : 
      94             :   public:
      95      134388 :     UserValueScopes(DebugLoc D, LexicalScopes &L) : DL(std::move(D)), LS(L) {}
      96             : 
      97             :     /// Return true if current scope dominates at least one machine
      98             :     /// instruction in a given machine basic block.
      99       61053 :     bool dominates(MachineBasicBlock *MBB) {
     100      122106 :       if (LBlocks.empty())
     101       15250 :         LS.getMachineBasicBlocks(DL, LBlocks);
     102       87310 :       return LBlocks.count(MBB) != 0 || LS.dominates(DL, MBB);
     103             :     }
     104             :   };
     105             : 
     106             :   /// Based on std::pair so it can be used as an index into a DenseMap.
     107             :   using DebugVariableBase =
     108             :       std::pair<const DILocalVariable *, const DILocation *>;
     109             :   /// A potentially inlined instance of a variable.
     110             :   struct DebugVariable : public DebugVariableBase {
     111             :     DebugVariable(const DILocalVariable *Var, const DILocation *InlinedAt)
     112      184290 :         : DebugVariableBase(Var, InlinedAt) {}
     113             : 
     114             :     const DILocalVariable *getVar() const { return this->first; }
     115             :     const DILocation *getInlinedAt() const { return this->second; }
     116             : 
     117             :     bool operator<(const DebugVariable &DV) const {
     118      240298 :       if (getVar() == DV.getVar())
     119       29512 :         return getInlinedAt() < DV.getInlinedAt();
     120      210786 :       return getVar() < DV.getVar();
     121             :     }
     122             :   };
     123             : 
     124             :   /// A pair of debug variable and value location.
     125      116628 :   struct VarLoc {
     126             :     const DebugVariable Var;
     127             :     const MachineInstr &MI; ///< Only used for cloning a new DBG_VALUE.
     128             :     mutable UserValueScopes UVS;
     129             :     enum { InvalidKind = 0, RegisterKind } Kind = InvalidKind;
     130             : 
     131             :     /// The value location. Stored separately to avoid repeatedly
     132             :     /// extracting it from MI.
     133             :     union {
     134             :       uint64_t RegNo;
     135             :       uint64_t Hash;
     136             :     } Loc;
     137             : 
     138       44796 :     VarLoc(const MachineInstr &MI, LexicalScopes &LS)
     139      179184 :         : Var(MI.getDebugVariable(), MI.getDebugLoc()->getInlinedAt()), MI(MI),
     140      268776 :           UVS(MI.getDebugLoc(), LS) {
     141             :       static_assert((sizeof(Loc) == sizeof(uint64_t)),
     142             :                     "hash does not cover all members of Loc");
     143             :       assert(MI.isDebugValue() && "not a DBG_VALUE");
     144             :       assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
     145       44796 :       if (int RegNo = isDbgValueDescribedByReg(MI)) {
     146       44796 :         Kind = RegisterKind;
     147       44796 :         Loc.RegNo = RegNo;
     148             :       }
     149       44796 :     }
     150             : 
     151             :     /// If this variable is described by a register, return it,
     152             :     /// otherwise return 0.
     153             :     unsigned isDescribedByReg() const {
     154      686826 :       if (Kind == RegisterKind)
     155      686826 :         return Loc.RegNo;
     156             :       return 0;
     157             :     }
     158             : 
     159             :     /// Determine whether the lexical scope of this value's debug location
     160             :     /// dominates MBB.
     161       61053 :     bool dominates(MachineBasicBlock &MBB) const { return UVS.dominates(&MBB); }
     162             : 
     163             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     164             :     LLVM_DUMP_METHOD void dump() const { MI.dump(); }
     165             : #endif
     166             : 
     167             :     bool operator==(const VarLoc &Other) const {
     168             :       return Var == Other.Var && Loc.Hash == Other.Loc.Hash;
     169             :     }
     170             : 
     171             :     /// This operator guarantees that VarLocs are sorted by Variable first.
     172             :     bool operator<(const VarLoc &Other) const {
     173      654088 :       if (Var == Other.Var)
     174       86746 :         return Loc.Hash < Other.Loc.Hash;
     175      240298 :       return Var < Other.Var;
     176             :     }
     177             :   };
     178             : 
     179             :   using VarLocMap = UniqueVector<VarLoc>;
     180             :   using VarLocSet = SparseBitVector<>;
     181             :   using VarLocInMBB = SmallDenseMap<const MachineBasicBlock *, VarLocSet>;
     182             :   struct SpillDebugPair {
     183             :     MachineInstr *SpillInst;
     184             :     MachineInstr *DebugInst;
     185             :   };
     186             :   using SpillMap = SmallVector<SpillDebugPair, 4>;
     187             : 
     188             :   /// This holds the working set of currently open ranges. For fast
     189             :   /// access, this is done both as a set of VarLocIDs, and a map of
     190             :   /// DebugVariable to recent VarLocID. Note that a DBG_VALUE ends all
     191             :   /// previous open ranges for the same variable.
     192       37404 :   class OpenRangesSet {
     193             :     VarLocSet VarLocs;
     194             :     SmallDenseMap<DebugVariableBase, unsigned, 8> Vars;
     195             : 
     196             :   public:
     197     3873188 :     const VarLocSet &getVarLocs() const { return VarLocs; }
     198             : 
     199             :     /// Terminate all open ranges for Var by removing it from the set.
     200       47411 :     void erase(DebugVariable Var) {
     201       47411 :       auto It = Vars.find(Var);
     202      142233 :       if (It != Vars.end()) {
     203        1840 :         unsigned ID = It->second;
     204        1840 :         VarLocs.reset(ID);
     205        1840 :         Vars.erase(It);
     206             :       }
     207       47411 :     }
     208             : 
     209             :     /// Terminate all open ranges listed in \c KillSet by removing
     210             :     /// them from the set.
     211     1359079 :     void erase(const VarLocSet &KillSet, const VarLocMap &VarLocIDs) {
     212     1359079 :       VarLocs.intersectWithComplement(KillSet);
     213     2723932 :       for (unsigned ID : KillSet)
     214       11548 :         Vars.erase(VarLocIDs[ID].Var);
     215     1359079 :     }
     216             : 
     217             :     /// Insert a new range into the set.
     218       44796 :     void insert(unsigned VarLocID, DebugVariableBase Var) {
     219       44796 :       VarLocs.set(VarLocID);
     220      134388 :       Vars.insert({Var, VarLocID});
     221       44796 :     }
     222             : 
     223             :     /// Empty the set.
     224        9191 :     void clear() {
     225       18382 :       VarLocs.clear();
     226        9191 :       Vars.clear();
     227        9191 :     }
     228             : 
     229             :     /// Return whether the set is empty or not.
     230             :     bool empty() const {
     231             :       assert(Vars.empty() == VarLocs.empty() && "open ranges are inconsistent");
     232      250666 :       return VarLocs.empty();
     233             :     }
     234             :   };
     235             : 
     236             :   bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF,
     237             :                           unsigned &Reg);
     238             :   int extractSpillBaseRegAndOffset(const MachineInstr &MI, unsigned &Reg);
     239             : 
     240             :   void transferDebugValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
     241             :                           VarLocMap &VarLocIDs);
     242             :   void transferSpillInst(MachineInstr &MI, OpenRangesSet &OpenRanges,
     243             :                          VarLocMap &VarLocIDs, SpillMap &Spills);
     244             :   void transferRegisterDef(MachineInstr &MI, OpenRangesSet &OpenRanges,
     245             :                            const VarLocMap &VarLocIDs);
     246             :   bool transferTerminatorInst(MachineInstr &MI, OpenRangesSet &OpenRanges,
     247             :                               VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs);
     248             :   bool transfer(MachineInstr &MI, OpenRangesSet &OpenRanges,
     249             :                 VarLocInMBB &OutLocs, VarLocMap &VarLocIDs, SpillMap &Spills,
     250             :                 bool transferSpills);
     251             : 
     252             :   bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
     253             :             const VarLocMap &VarLocIDs,
     254             :             SmallPtrSet<const MachineBasicBlock *, 16> &Visited);
     255             : 
     256             :   bool ExtendRanges(MachineFunction &MF);
     257             : 
     258             : public:
     259             :   static char ID;
     260             : 
     261             :   /// Default construct and initialize the pass.
     262             :   LiveDebugValues();
     263             : 
     264             :   /// Tell the pass manager which passes we depend on and what
     265             :   /// information we preserve.
     266             :   void getAnalysisUsage(AnalysisUsage &AU) const override;
     267             : 
     268       16642 :   MachineFunctionProperties getRequiredProperties() const override {
     269       49926 :     return MachineFunctionProperties().set(
     270       49926 :         MachineFunctionProperties::Property::NoVRegs);
     271             :   }
     272             : 
     273             :   /// Print to ostream with a message.
     274             :   void printVarLocInMBB(const MachineFunction &MF, const VarLocInMBB &V,
     275             :                         const VarLocMap &VarLocIDs, const char *msg,
     276             :                         raw_ostream &Out) const;
     277             : 
     278             :   /// Calculate the liveness information for the given machine function.
     279             :   bool runOnMachineFunction(MachineFunction &MF) override;
     280             : };
     281             : 
     282             : } // end anonymous namespace
     283             : 
     284             : //===----------------------------------------------------------------------===//
     285             : //            Implementation
     286             : //===----------------------------------------------------------------------===//
     287             : 
     288             : char LiveDebugValues::ID = 0;
     289             : 
     290             : char &llvm::LiveDebugValuesID = LiveDebugValues::ID;
     291             : 
     292      201302 : INITIALIZE_PASS(LiveDebugValues, DEBUG_TYPE, "Live DEBUG_VALUE analysis",
     293             :                 false, false)
     294             : 
     295             : /// Default construct and initialize the pass.
     296       33402 : LiveDebugValues::LiveDebugValues() : MachineFunctionPass(ID) {
     297       16701 :   initializeLiveDebugValuesPass(*PassRegistry::getPassRegistry());
     298       16701 : }
     299             : 
     300             : /// Tell the pass manager which passes we depend on and what information we
     301             : /// preserve.
     302       16638 : void LiveDebugValues::getAnalysisUsage(AnalysisUsage &AU) const {
     303       16638 :   AU.setPreservesCFG();
     304       16638 :   MachineFunctionPass::getAnalysisUsage(AU);
     305       16638 : }
     306             : 
     307             : //===----------------------------------------------------------------------===//
     308             : //            Debug Range Extension Implementation
     309             : //===----------------------------------------------------------------------===//
     310             : 
     311             : #ifndef NDEBUG
     312             : void LiveDebugValues::printVarLocInMBB(const MachineFunction &MF,
     313             :                                        const VarLocInMBB &V,
     314             :                                        const VarLocMap &VarLocIDs,
     315             :                                        const char *msg,
     316             :                                        raw_ostream &Out) const {
     317             :   Out << '\n' << msg << '\n';
     318             :   for (const MachineBasicBlock &BB : MF) {
     319             :     const auto &L = V.lookup(&BB);
     320             :     Out << "MBB: " << BB.getName() << ":\n";
     321             :     for (unsigned VLL : L) {
     322             :       const VarLoc &VL = VarLocIDs[VLL];
     323             :       Out << " Var: " << VL.Var.getVar()->getName();
     324             :       Out << " MI: ";
     325             :       VL.dump();
     326             :     }
     327             :   }
     328             :   Out << "\n";
     329             : }
     330             : #endif
     331             : 
     332             : /// Given a spill instruction, extract the register and offset used to
     333             : /// address the spill location in a target independent way.
     334          62 : int LiveDebugValues::extractSpillBaseRegAndOffset(const MachineInstr &MI,
     335             :                                                   unsigned &Reg) {
     336             :   assert(MI.hasOneMemOperand() && 
     337             :          "Spill instruction does not have exactly one memory operand?");
     338          62 :   auto MMOI = MI.memoperands_begin();
     339         124 :   const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
     340             :   assert(PVal->kind() == PseudoSourceValue::FixedStack &&
     341             :          "Inconsistent memory operand in spill instruction");
     342          62 :   int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex();
     343          62 :   const MachineBasicBlock *MBB = MI.getParent();
     344          62 :   return TFI->getFrameIndexReference(*MBB->getParent(), FI, Reg);
     345             : }
     346             : 
     347             : /// End all previous ranges related to @MI and start a new range from @MI
     348             : /// if it is a DBG_VALUE instr.
     349     1359079 : void LiveDebugValues::transferDebugValue(const MachineInstr &MI,
     350             :                                          OpenRangesSet &OpenRanges,
     351             :                                          VarLocMap &VarLocIDs) {
     352     1359079 :   if (!MI.isDebugValue())
     353     1311730 :     return;
     354       47349 :   const DILocalVariable *Var = MI.getDebugVariable();
     355       94698 :   const DILocation *DebugLoc = MI.getDebugLoc();
     356       47349 :   const DILocation *InlinedAt = DebugLoc->getInlinedAt();
     357             :   assert(Var->isValidLocationForIntrinsic(DebugLoc) &&
     358             :          "Expected inlined-at fields to agree");
     359             : 
     360             :   // End all previous ranges of Var.
     361       47349 :   DebugVariable V(Var, InlinedAt);
     362       47349 :   OpenRanges.erase(V);
     363             : 
     364             :   // Add the VarLoc to OpenRanges from this DBG_VALUE.
     365             :   // TODO: Currently handles DBG_VALUE which has only reg as location.
     366       44888 :   if (isDbgValueDescribedByReg(MI)) {
     367       89468 :     VarLoc VL(MI, LS);
     368       44734 :     unsigned ID = VarLocIDs.insert(VL);
     369       44734 :     OpenRanges.insert(ID, VL.Var);
     370             :   }
     371             : }
     372             : 
     373             : /// A definition of a register may mark the end of a range.
     374     1359079 : void LiveDebugValues::transferRegisterDef(MachineInstr &MI,
     375             :                                           OpenRangesSet &OpenRanges,
     376             :                                           const VarLocMap &VarLocIDs) {
     377     1359079 :   MachineFunction *MF = MI.getParent()->getParent();
     378     1359079 :   const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
     379     1359079 :   unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
     380     2718158 :   SparseBitVector<> KillSet;
     381     7568126 :   for (const MachineOperand &MO : MI.operands()) {
     382             :     // Determine whether the operand is a register def.  Assume that call
     383             :     // instructions never clobber SP, because some backends (e.g., AArch64)
     384             :     // never list SP in the regmask.
     385    11426913 :     if (MO.isReg() && MO.isDef() && MO.getReg() &&
     386     9432205 :         TRI->isPhysicalRegister(MO.getReg()) &&
     387     1202325 :         !(MI.isCall() && MO.getReg() == SP)) {
     388             :       // Remove ranges of all aliased registers.
     389    10383911 :       for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
     390     8172850 :         for (unsigned ID : OpenRanges.getVarLocs())
     391     2019390 :           if (VarLocIDs[ID].isDescribedByReg() == *RAI)
     392        5627 :             KillSet.set(ID);
     393     5247650 :     } else if (MO.isRegMask()) {
     394             :       // Remove ranges of all clobbered registers. Register masks don't usually
     395             :       // list SP as preserved.  While the debug info may be off for an
     396             :       // instruction or two around callee-cleanup calls, transferring the
     397             :       // DEBUG_VALUE across the call is still a better user experience.
     398      240971 :       for (unsigned ID : OpenRanges.getVarLocs()) {
     399       26038 :         unsigned Reg = VarLocIDs[ID].isDescribedByReg();
     400       22852 :         if (Reg && Reg != SP && MO.clobbersPhysReg(Reg))
     401        2532 :           KillSet.set(ID);
     402             :       }
     403             :     }
     404             :   }
     405     1359079 :   OpenRanges.erase(KillSet, VarLocIDs);
     406     1359079 : }
     407             : 
     408             : /// Decide if @MI is a spill instruction and return true if it is. We use 2
     409             : /// criteria to make this decision:
     410             : /// - Is this instruction a store to a spill slot?
     411             : /// - Is there a register operand that is both used and killed?
     412             : /// TODO: Store optimization can fold spills into other stores (including
     413             : /// other spills). We do not handle this yet (more than one memory operand).
     414       63795 : bool LiveDebugValues::isSpillInstruction(const MachineInstr &MI,
     415             :                                          MachineFunction *MF, unsigned &Reg) {
     416       63795 :   const MachineFrameInfo &FrameInfo = MF->getFrameInfo();
     417             :   int FI;
     418             :   const MachineMemOperand *MMO;
     419             : 
     420             :   // TODO: Handle multiple stores folded into one. 
     421       63795 :   if (!MI.hasOneMemOperand())
     422             :     return false;
     423             : 
     424             :   // To identify a spill instruction, use the same criteria as in AsmPrinter.
     425       15154 :   if (!((TII->isStoreToStackSlotPostFE(MI, FI) ||
     426        7291 :          TII->hasStoreToStackSlot(MI, MMO, FI)) &&
     427         594 :         FrameInfo.isSpillSlotObjectIndex(FI)))
     428             :     return false;
     429             : 
     430             :   // In a spill instruction generated by the InlineSpiller the spilled register
     431             :   // has its kill flag set. Return false if we don't find such a register.
     432         257 :   Reg = 0;
     433        1557 :   for (const MachineOperand &MO : MI.operands()) {
     434        3409 :     if (MO.isReg() && MO.isUse() && MO.isKill()) {
     435         161 :       Reg = MO.getReg();
     436             :       break;
     437             :     }
     438             :   }
     439         257 :   return Reg != 0;
     440             : }
     441             : 
     442             : /// A spilled register may indicate that we have to end the current range of
     443             : /// a variable and create a new one for the spill location.
     444             : /// We don't want to insert any instructions in transfer(), so we just create
     445             : /// the DBG_VALUE witout inserting it and keep track of it in @Spills.
     446             : /// It will be inserted into the BB when we're done iterating over the
     447             : /// instructions.
     448       63795 : void LiveDebugValues::transferSpillInst(MachineInstr &MI,
     449             :                                         OpenRangesSet &OpenRanges,
     450             :                                         VarLocMap &VarLocIDs,
     451             :                                         SpillMap &Spills) {
     452             :   unsigned Reg;
     453       63795 :   MachineFunction *MF = MI.getParent()->getParent();
     454       63795 :   if (!isSpillInstruction(MI, MF, Reg))
     455       63696 :     return;
     456             : 
     457             :   // Check if the register is the location of a debug value.
     458         999 :   for (unsigned ID : OpenRanges.getVarLocs()) {
     459        1354 :     if (VarLocIDs[ID].isDescribedByReg() == Reg) {
     460             :       DEBUG(dbgs() << "Spilling Register " << PrintReg(Reg, TRI) << '('
     461             :                    << VarLocIDs[ID].Var.getVar()->getName() << ")\n");
     462             : 
     463             :       // Create a DBG_VALUE instruction to describe the Var in its spilled
     464             :       // location, but don't insert it yet to avoid invalidating the
     465             :       // iterator in our caller.
     466             :       unsigned SpillBase;
     467          62 :       int SpillOffset = extractSpillBaseRegAndOffset(MI, SpillBase);
     468          62 :       const MachineInstr *DMI = &VarLocIDs[ID].MI;
     469          62 :       auto *SpillExpr = DIExpression::prepend(
     470          62 :           DMI->getDebugExpression(), DIExpression::NoDeref, SpillOffset);
     471             :       MachineInstr *SpDMI =
     472         124 :           BuildMI(*MF, DMI->getDebugLoc(), DMI->getDesc(), true, SpillBase,
     473         186 :                   DMI->getDebugVariable(), SpillExpr);
     474             :       DEBUG(dbgs() << "Creating DBG_VALUE inst for spill: ";
     475             :             SpDMI->print(dbgs(), false, TII));
     476             : 
     477             :       // The newly created DBG_VALUE instruction SpDMI must be inserted after
     478             :       // MI. Keep track of the pairing.
     479          62 :       SpillDebugPair MIP = {&MI, SpDMI};
     480          62 :       Spills.push_back(MIP);
     481             : 
     482             :       // End all previous ranges of Var.
     483          62 :       OpenRanges.erase(VarLocIDs[ID].Var);
     484             : 
     485             :       // Add the VarLoc to OpenRanges.
     486         124 :       VarLoc VL(*SpDMI, LS);
     487          62 :       unsigned SpillLocID = VarLocIDs.insert(VL);
     488          62 :       OpenRanges.insert(SpillLocID, VL.Var);
     489             :       return;
     490             :     }
     491             :   }
     492             : }
     493             : 
     494             : /// Terminate all open ranges at the end of the current basic block.
     495     1359079 : bool LiveDebugValues::transferTerminatorInst(MachineInstr &MI,
     496             :                                              OpenRangesSet &OpenRanges,
     497             :                                              VarLocInMBB &OutLocs,
     498             :                                              const VarLocMap &VarLocIDs) {
     499     1359079 :   bool Changed = false;
     500     1359079 :   const MachineBasicBlock *CurMBB = MI.getParent();
     501     2653740 :   if (!(MI.isTerminator() || (&MI == &CurMBB->instr_back())))
     502             :     return false;
     503             : 
     504      125333 :   if (OpenRanges.empty())
     505             :     return false;
     506             : 
     507             :   DEBUG(for (unsigned ID : OpenRanges.getVarLocs()) {
     508             :           // Copy OpenRanges to OutLocs, if not already present.
     509             :           dbgs() << "Add to OutLocs: "; VarLocIDs[ID].dump();
     510             :         });
     511        9191 :   VarLocSet &VLS = OutLocs[CurMBB];
     512        9191 :   Changed = VLS |= OpenRanges.getVarLocs();
     513        9191 :   OpenRanges.clear();
     514             :   return Changed;
     515             : }
     516             : 
     517             : /// This routine creates OpenRanges and OutLocs.
     518     1359079 : bool LiveDebugValues::transfer(MachineInstr &MI, OpenRangesSet &OpenRanges,
     519             :                                VarLocInMBB &OutLocs, VarLocMap &VarLocIDs,
     520             :                                SpillMap &Spills, bool transferSpills) {
     521     1359079 :   bool Changed = false;
     522     1359079 :   transferDebugValue(MI, OpenRanges, VarLocIDs);
     523     1359079 :   transferRegisterDef(MI, OpenRanges, VarLocIDs);
     524     1359079 :   if (transferSpills)
     525       63795 :     transferSpillInst(MI, OpenRanges, VarLocIDs, Spills);
     526     1359079 :   Changed = transferTerminatorInst(MI, OpenRanges, OutLocs, VarLocIDs);
     527     1359079 :   return Changed;
     528             : }
     529             : 
     530             : /// This routine joins the analysis results of all incoming edges in @MBB by
     531             : /// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same
     532             : /// source variable in all the predecessors of @MBB reside in the same location.
     533      124434 : bool LiveDebugValues::join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs,
     534             :                            VarLocInMBB &InLocs, const VarLocMap &VarLocIDs,
     535             :                            SmallPtrSet<const MachineBasicBlock *, 16> &Visited) {
     536             :   DEBUG(dbgs() << "join MBB: " << MBB.getName() << "\n");
     537      124434 :   bool Changed = false;
     538             : 
     539      248868 :   VarLocSet InLocsT; // Temporary incoming locations.
     540             : 
     541             :   // For all predecessors of this MBB, find the set of VarLocs that
     542             :   // can be joined.
     543      124434 :   int NumVisited = 0;
     544      268813 :   for (auto p : MBB.predecessors()) {
     545             :     // Ignore unvisited predecessor blocks.  As we are processing
     546             :     // the blocks in reverse post-order any unvisited block can
     547             :     // be considered to not remove any incoming values.
     548      125072 :     if (!Visited.count(p))
     549         523 :       continue;
     550      124549 :     auto OL = OutLocs.find(p);
     551             :     // Join is null in case of empty OutLocs from any of the pred.
     552      249098 :     if (OL == OutLocs.end())
     553      105127 :       return false;
     554             : 
     555             :     // Just copy over the Out locs to incoming locs for the first visited
     556             :     // predecessor, and for all other predecessors join the Out locs.
     557       19422 :     if (!NumVisited)
     558       13236 :       InLocsT = OL->second;
     559             :     else
     560        6186 :       InLocsT &= OL->second;
     561       19422 :     NumVisited++;
     562             :   }
     563             : 
     564             :   // Filter out DBG_VALUES that are out of scope.
     565       19307 :   VarLocSet KillSet;
     566       99667 :   for (auto ID : InLocsT)
     567      122106 :     if (!VarLocIDs[ID].dominates(MBB))
     568       12298 :       KillSet.set(ID);
     569       19307 :   InLocsT.intersectWithComplement(KillSet);
     570             : 
     571             :   // As we are processing blocks in reverse post-order we
     572             :   // should have processed at least one predecessor, unless it
     573             :   // is the entry block which has no predecessor.
     574             :   assert((NumVisited || MBB.pred_empty()) &&
     575             :          "Should have processed at least one predecessor");
     576       19307 :   if (InLocsT.empty())
     577             :     return false;
     578             : 
     579       25548 :   VarLocSet &ILS = InLocs[&MBB];
     580             : 
     581             :   // Insert DBG_VALUE instructions, if not already inserted.
     582       12774 :   VarLocSet Diff = InLocsT;
     583       12774 :   Diff.intersectWithComplement(ILS);
     584       50873 :   for (auto ID : Diff) {
     585             :     // This VarLoc is not found in InLocs i.e. it is not yet inserted. So, a
     586             :     // new range is started for the var from the mbb's beginning by inserting
     587             :     // a new DBG_VALUE. transfer() will end this range however appropriate.
     588       25325 :     const VarLoc &DiffIt = VarLocIDs[ID];
     589       25325 :     const MachineInstr *DMI = &DiffIt.MI;
     590             :     MachineInstr *MI =
     591       50650 :         BuildMI(MBB, MBB.instr_begin(), DMI->getDebugLoc(), DMI->getDesc(),
     592       50650 :                 DMI->isIndirectDebugValue(), DMI->getOperand(0).getReg(),
     593      202600 :                 DMI->getDebugVariable(), DMI->getDebugExpression());
     594        6504 :     if (DMI->isIndirectDebugValue())
     595        6504 :       MI->getOperand(1).setImm(DMI->getOperand(1).getImm());
     596             :     DEBUG(dbgs() << "Inserted: "; MI->dump(););
     597       25325 :     ILS.set(ID);
     598       25325 :     ++NumInserted;
     599       25325 :     Changed = true;
     600             :   }
     601       12774 :   return Changed;
     602             : }
     603             : 
     604             : /// Calculate the liveness information for the given machine function and
     605             : /// extend ranges across basic blocks.
     606        6234 : bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
     607             :   DEBUG(dbgs() << "\nDebug Range Extension\n");
     608             : 
     609        6234 :   bool Changed = false;
     610        6234 :   bool OLChanged = false;
     611        6234 :   bool MBBJoined = false;
     612             : 
     613       12468 :   VarLocMap VarLocIDs;      // Map VarLoc<>unique ID for use in bitvectors.
     614       12468 :   OpenRangesSet OpenRanges; // Ranges that are open until end of bb.
     615       12468 :   VarLocInMBB OutLocs;      // Ranges that exist beyond bb.
     616       12468 :   VarLocInMBB InLocs;       // Ranges that are incoming after joining.
     617       12468 :   SpillMap Spills;          // DBG_VALUEs associated with spills.
     618             : 
     619       12468 :   DenseMap<unsigned int, MachineBasicBlock *> OrderToBB;
     620       12468 :   DenseMap<MachineBasicBlock *, unsigned int> BBToOrder;
     621             :   std::priority_queue<unsigned int, std::vector<unsigned int>,
     622             :                       std::greater<unsigned int>>
     623       12468 :       Worklist;
     624             :   std::priority_queue<unsigned int, std::vector<unsigned int>,
     625             :                       std::greater<unsigned int>>
     626       12468 :       Pending;
     627             : 
     628             :   // Initialize every mbb with OutLocs.
     629             :   // We are not looking at any spill instructions during the initial pass
     630             :   // over the BBs. The LiveDebugVariables pass has already created DBG_VALUE
     631             :   // instructions for spills of registers that are known to be user variables
     632             :   // within the BB in which the spill occurs.
     633      136901 :   for (auto &MBB : MF)
     634     3063364 :     for (auto &MI : MBB)
     635     1295284 :       transfer(MI, OpenRanges, OutLocs, VarLocIDs, Spills,
     636             :                /*transferSpills=*/false);
     637             : 
     638             :   DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "OutLocs after initialization",
     639             :                          dbgs()));
     640             : 
     641       12468 :   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
     642        6234 :   unsigned int RPONumber = 0;
     643      130657 :   for (auto RI = RPOT.begin(), RE = RPOT.end(); RI != RE; ++RI) {
     644      236378 :     OrderToBB[RPONumber] = *RI;
     645      236378 :     BBToOrder[*RI] = RPONumber;
     646      118189 :     Worklist.push(RPONumber);
     647      118189 :     ++RPONumber;
     648             :   }
     649             :   // This is a standard "union of predecessor outs" dataflow problem.
     650             :   // To solve it, we perform join() and transfer() using the two worklist method
     651             :   // until the ranges converge.
     652             :   // Ranges have converged when both worklists are empty.
     653        6234 :   SmallPtrSet<const MachineBasicBlock *, 16> Visited;
     654       25510 :   while (!Worklist.empty() || !Pending.empty()) {
     655             :     // We track what is on the pending worklist to avoid inserting the same
     656             :     // thing twice.  We could avoid this with a custom priority queue, but this
     657             :     // is probably not worth it.
     658        6521 :     SmallPtrSet<MachineBasicBlock *, 16> OnPending;
     659             :     DEBUG(dbgs() << "Processing Worklist\n");
     660      130955 :     while (!Worklist.empty()) {
     661      248868 :       MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
     662      124434 :       Worklist.pop();
     663      124434 :       MBBJoined = join(*MBB, OutLocs, InLocs, VarLocIDs, Visited);
     664      124434 :       Visited.insert(MBB);
     665      124434 :       if (MBBJoined) {
     666        6709 :         MBBJoined = false;
     667        6709 :         Changed = true;
     668             :         // Now that we have started to extend ranges across BBs we need to
     669             :         // examine spill instructions to see whether they spill registers that
     670             :         // correspond to user variables.
     671      154426 :         for (auto &MI : *MBB)
     672       63795 :           OLChanged |= transfer(MI, OpenRanges, OutLocs, VarLocIDs, Spills,
     673             :                                 /*transferSpills=*/true);
     674             : 
     675             :         // Add any DBG_VALUE instructions necessitated by spills.
     676       20189 :         for (auto &SP : Spills)
     677         124 :           MBB->insertAfter(MachineBasicBlock::iterator(*SP.SpillInst),
     678         124 :                            SP.DebugInst);
     679        6709 :         Spills.clear();
     680             : 
     681             :         DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
     682             :                                "OutLocs after propagating", dbgs()));
     683             :         DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs,
     684             :                                "InLocs after propagating", dbgs()));
     685             : 
     686        6709 :         if (OLChanged) {
     687        6252 :           OLChanged = false;
     688       21771 :           for (auto s : MBB->successors())
     689        9267 :             if (OnPending.insert(s).second) {
     690        6245 :               Pending.push(BBToOrder[s]);
     691             :             }
     692             :         }
     693             :       }
     694             :     }
     695        6521 :     Worklist.swap(Pending);
     696             :     // At this point, pending must be empty, since it was just the empty
     697             :     // worklist
     698             :     assert(Pending.empty() && "Pending should be empty");
     699             :   }
     700             : 
     701             :   DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "Final OutLocs", dbgs()));
     702             :   DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, "Final InLocs", dbgs()));
     703       12468 :   return Changed;
     704             : }
     705             : 
     706      141262 : bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) {
     707      141262 :   if (!MF.getFunction()->getSubprogram())
     708             :     // LiveDebugValues will already have removed all DBG_VALUEs.
     709             :     return false;
     710             : 
     711             :   // Skip functions from NoDebug compilation units.
     712       12498 :   if (MF.getFunction()->getSubprogram()->getUnit()->getEmissionKind() ==
     713             :       DICompileUnit::NoDebug)
     714             :     return false;
     715             : 
     716        6234 :   TRI = MF.getSubtarget().getRegisterInfo();
     717        6234 :   TII = MF.getSubtarget().getInstrInfo();
     718        6234 :   TFI = MF.getSubtarget().getFrameLowering();
     719        6234 :   LS.initialize(MF);
     720             : 
     721        6234 :   bool Changed = ExtendRanges(MF);
     722        6234 :   return Changed;
     723             : }

Generated by: LCOV version 1.13