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

Generated by: LCOV version 1.13