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-07-13 00:08:38 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/Config/llvm-config.h"
      44             : #include "llvm/IR/DebugInfoMetadata.h"
      45             : #include "llvm/IR/DebugLoc.h"
      46             : #include "llvm/IR/Function.h"
      47             : #include "llvm/IR/Module.h"
      48             : #include "llvm/MC/MCRegisterInfo.h"
      49             : #include "llvm/Pass.h"
      50             : #include "llvm/Support/Casting.h"
      51             : #include "llvm/Support/Compiler.h"
      52             : #include "llvm/Support/Debug.h"
      53             : #include "llvm/Support/raw_ostream.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             : // 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      340732 :   return MI.getOperand(0).isReg() ? MI.getOperand(0).getReg() : 0;
      76             : }
      77             : 
      78             : namespace {
      79             : 
      80       21636 : 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      530688 :   class UserValueScopes {
      90             :     DebugLoc DL;
      91             :     LexicalScopes &LS;
      92             :     SmallPtrSet<const MachineBasicBlock *, 4> LBlocks;
      93             : 
      94             :   public:
      95      154238 :     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       94498 :     bool dominates(MachineBasicBlock *MBB) {
     100       94498 :       if (LBlocks.empty())
     101       30508 :         LS.getMachineBasicBlocks(DL, LBlocks);
     102      140503 :       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             :         : 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      456770 :       if (getVar() == DV.getVar())
     119       62454 :         return getInlinedAt() < DV.getInlinedAt();
     120      394316 :       return getVar() < DV.getVar();
     121             :     }
     122             :   };
     123             : 
     124             :   /// A pair of debug variable and value location.
     125      227699 :   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       77119 :     VarLoc(const MachineInstr &MI, LexicalScopes &LS)
     139       77119 :         : Var(MI.getDebugVariable(), MI.getDebugLoc()->getInlinedAt()), MI(MI),
     140      231357 :           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       77119 :       if (int RegNo = isDbgValueDescribedByReg(MI)) {
     146       77119 :         Kind = RegisterKind;
     147       77119 :         Loc.RegNo = RegNo;
     148             :       }
     149       77119 :     }
     150             : 
     151             :     /// If this variable is described by a register, return it,
     152             :     /// otherwise return 0.
     153             :     unsigned isDescribedByReg() const {
     154     2058082 :       if (Kind == RegisterKind)
     155     2058082 :         return Loc.RegNo;
     156             :       return 0;
     157             :     }
     158             : 
     159             :     /// Determine whether the lexical scope of this value's debug location
     160             :     /// dominates MBB.
     161       94498 :     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             :       if (Var == Other.Var)
     174      143629 :         return Loc.Hash < Other.Loc.Hash;
     175             :       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       72436 :   class OpenRangesSet {
     193             :     VarLocSet VarLocs;
     194             :     SmallDenseMap<DebugVariableBase, unsigned, 8> Vars;
     195             : 
     196             :   public:
     197    11484464 :     const VarLocSet &getVarLocs() const { return VarLocs; }
     198             : 
     199             :     /// Terminate all open ranges for Var by removing it from the set.
     200       93312 :     void erase(DebugVariable Var) {
     201       93312 :       auto It = Vars.find(Var);
     202       93312 :       if (It != Vars.end()) {
     203        8657 :         unsigned ID = It->second;
     204        8657 :         VarLocs.reset(ID);
     205             :         Vars.erase(It);
     206             :       }
     207       93312 :     }
     208             : 
     209             :     /// Terminate all open ranges listed in \c KillSet by removing
     210             :     /// them from the set.
     211     2261619 :     void erase(const VarLocSet &KillSet, const VarLocMap &VarLocIDs) {
     212     2261619 :       VarLocs.intersectWithComplement(KillSet);
     213       10177 :       for (unsigned ID : KillSet)
     214       20354 :         Vars.erase(VarLocIDs[ID].Var);
     215     2261619 :     }
     216             : 
     217             :     /// Insert a new range into the set.
     218       77119 :     void insert(unsigned VarLocID, DebugVariableBase Var) {
     219       77119 :       VarLocs.set(VarLocID);
     220      154238 :       Vars.insert({Var, VarLocID});
     221       77119 :     }
     222             : 
     223             :     /// Empty the set.
     224       12733 :     void clear() {
     225             :       VarLocs.clear();
     226       12733 :       Vars.clear();
     227       12733 :     }
     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             :       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       21574 :   MachineFunctionProperties getRequiredProperties() const override {
     269       43148 :     return MachineFunctionProperties().set(
     270       21574 :         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      190080 : INITIALIZE_PASS(LiveDebugValues, DEBUG_TYPE, "Live DEBUG_VALUE analysis",
     293             :                 false, false)
     294             : 
     295             : /// Default construct and initialize the pass.
     296       21735 : LiveDebugValues::LiveDebugValues() : MachineFunctionPass(ID) {
     297       21735 :   initializeLiveDebugValuesPass(*PassRegistry::getPassRegistry());
     298       21735 : }
     299             : 
     300             : /// Tell the pass manager which passes we depend on and what information we
     301             : /// preserve.
     302       21570 : void LiveDebugValues::getAnalysisUsage(AnalysisUsage &AU) const {
     303       21570 :   AU.setPreservesCFG();
     304       21570 :   MachineFunctionPass::getAnalysisUsage(AU);
     305       21570 : }
     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          65 : int LiveDebugValues::extractSpillBaseRegAndOffset(const MachineInstr &MI,
     335             :                                                   unsigned &Reg) {
     336             :   assert(MI.hasOneMemOperand() && 
     337             :          "Spill instruction does not have exactly one memory operand?");
     338          65 :   auto MMOI = MI.memoperands_begin();
     339          65 :   const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
     340             :   assert(PVal->kind() == PseudoSourceValue::FixedStack &&
     341             :          "Inconsistent memory operand in spill instruction");
     342          65 :   int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex();
     343          65 :   const MachineBasicBlock *MBB = MI.getParent();
     344          65 :   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     2261619 : void LiveDebugValues::transferDebugValue(const MachineInstr &MI,
     350             :                                          OpenRangesSet &OpenRanges,
     351             :                                          VarLocMap &VarLocIDs) {
     352     2261619 :   if (!MI.isDebugValue())
     353     2168372 :     return;
     354       93247 :   const DILocalVariable *Var = MI.getDebugVariable();
     355             :   const DILocation *DebugLoc = MI.getDebugLoc();
     356             :   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             :   DebugVariable V(Var, InlinedAt);
     362       93247 :   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       90577 :   if (isDbgValueDescribedByReg(MI)) {
     367       77054 :     VarLoc VL(MI, LS);
     368       77054 :     unsigned ID = VarLocIDs.insert(VL);
     369       77054 :     OpenRanges.insert(ID, VL.Var);
     370             :   }
     371             : }
     372             : 
     373             : /// A definition of a register may mark the end of a range.
     374     2261619 : void LiveDebugValues::transferRegisterDef(MachineInstr &MI,
     375             :                                           OpenRangesSet &OpenRanges,
     376             :                                           const VarLocMap &VarLocIDs) {
     377             :   MachineFunction *MF = MI.getMF();
     378     2261619 :   const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
     379     2261619 :   unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
     380             :   SparseBitVector<> KillSet;
     381    21933119 :   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     8449037 :     if (MO.isReg() && MO.isDef() && MO.getReg() &&
     386    11636954 :         TRI->isPhysicalRegister(MO.getReg()) &&
     387      332412 :         !(MI.isCall() && MO.getReg() == SP)) {
     388             :       // Remove ranges of all aliased registers.
     389    27560308 :       for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
     390     2036137 :         for (unsigned ID : OpenRanges.getVarLocs())
     391     4072274 :           if (VarLocIDs[ID].isDescribedByReg() == *RAI)
     392       17383 :             KillSet.set(ID);
     393     8173016 :     } 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       20789 :       for (unsigned ID : OpenRanges.getVarLocs()) {
     399       20789 :         unsigned Reg = VarLocIDs[ID].isDescribedByReg();
     400       36526 :         if (Reg && Reg != SP && MO.clobbersPhysReg(Reg))
     401        4748 :           KillSet.set(ID);
     402             :       }
     403             :     }
     404             :   }
     405     2261619 :   OpenRanges.erase(KillSet, VarLocIDs);
     406     2261619 : }
     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      101117 : bool LiveDebugValues::isSpillInstruction(const MachineInstr &MI,
     415             :                                          MachineFunction *MF, unsigned &Reg) {
     416      101117 :   const MachineFrameInfo &FrameInfo = MF->getFrameInfo();
     417             :   int FI;
     418             :   const MachineMemOperand *MMO;
     419             : 
     420             :   // TODO: Handle multiple stores folded into one. 
     421      101117 :   if (!MI.hasOneMemOperand())
     422             :     return false;
     423             : 
     424             :   // To identify a spill instruction, use the same criteria as in AsmPrinter.
     425       23038 :   if (!((TII->isStoreToStackSlotPostFE(MI, FI) ||
     426       10936 :          TII->hasStoreToStackSlot(MI, MMO, FI)) &&
     427         595 :         FrameInfo.isSpillSlotObjectIndex(FI)))
     428             :     return false;
     429             : 
     430             :   auto isKilledReg = [&](const MachineOperand MO, unsigned &Reg) {
     431        9342 :     if (!MO.isReg() || !MO.isUse()) {
     432        1084 :       Reg = 0;
     433             :       return false;
     434             :     }
     435        2164 :     Reg = MO.getReg();
     436             :     return MO.isKill();
     437             :   };
     438             : 
     439        6111 :   for (const MachineOperand &MO : MI.operands()) {
     440             :     // In a spill instruction generated by the InlineSpiller the spilled
     441             :     // register has its kill flag set.
     442        2164 :     if (isKilledReg(MO, Reg))
     443             :       return true;
     444        2814 :     if (Reg != 0) {
     445             :       // Check whether next instruction kills the spilled register.
     446             :       // FIXME: Current solution does not cover search for killed register in
     447             :       // bundles and instructions further down the chain.
     448         654 :       auto NextI = std::next(MI.getIterator());
     449             :       // Skip next instruction that points to basic block end iterator.
     450        1308 :       if (MI.getParent()->end() == NextI)
     451             :         continue;
     452             :       unsigned RegNext;
     453        5262 :       for (const MachineOperand &MONext : NextI->operands()) {
     454             :         // Return true if we came across the register from the
     455             :         // previous spill instruction that is killed in NextI.
     456        1259 :         if (isKilledReg(MONext, RegNext) && RegNext == Reg)
     457             :           return true;
     458             :       }
     459             :     }
     460             :   }
     461             :   // Return false if we didn't find spilled register.
     462             :   return false;
     463             : }
     464             : 
     465             : /// A spilled register may indicate that we have to end the current range of
     466             : /// a variable and create a new one for the spill location.
     467             : /// We don't want to insert any instructions in transfer(), so we just create
     468             : /// the DBG_VALUE witout inserting it and keep track of it in @Spills.
     469             : /// It will be inserted into the BB when we're done iterating over the
     470             : /// instructions.
     471      101117 : void LiveDebugValues::transferSpillInst(MachineInstr &MI,
     472             :                                         OpenRangesSet &OpenRanges,
     473             :                                         VarLocMap &VarLocIDs,
     474             :                                         SpillMap &Spills) {
     475             :   unsigned Reg;
     476             :   MachineFunction *MF = MI.getMF();
     477      101117 :   if (!isSpillInstruction(MI, MF, Reg))
     478      100712 :     return;
     479             : 
     480             :   // Check if the register is the location of a debug value.
     481        1156 :   for (unsigned ID : OpenRanges.getVarLocs()) {
     482        2312 :     if (VarLocIDs[ID].isDescribedByReg() == Reg) {
     483             :       LLVM_DEBUG(dbgs() << "Spilling Register " << printReg(Reg, TRI) << '('
     484             :                         << VarLocIDs[ID].Var.getVar()->getName() << ")\n");
     485             : 
     486             :       // Create a DBG_VALUE instruction to describe the Var in its spilled
     487             :       // location, but don't insert it yet to avoid invalidating the
     488             :       // iterator in our caller.
     489             :       unsigned SpillBase;
     490          65 :       int SpillOffset = extractSpillBaseRegAndOffset(MI, SpillBase);
     491          65 :       const MachineInstr *DMI = &VarLocIDs[ID].MI;
     492          65 :       auto *SpillExpr = DIExpression::prepend(
     493          65 :           DMI->getDebugExpression(), DIExpression::NoDeref, SpillOffset);
     494             :       MachineInstr *SpDMI =
     495         130 :           BuildMI(*MF, DMI->getDebugLoc(), DMI->getDesc(), true, SpillBase,
     496         130 :                   DMI->getDebugVariable(), SpillExpr);
     497             :       LLVM_DEBUG(dbgs() << "Creating DBG_VALUE inst for spill: ";
     498             :                  SpDMI->print(dbgs(), false, TII));
     499             : 
     500             :       // The newly created DBG_VALUE instruction SpDMI must be inserted after
     501             :       // MI. Keep track of the pairing.
     502          65 :       SpillDebugPair MIP = {&MI, SpDMI};
     503          65 :       Spills.push_back(MIP);
     504             : 
     505             :       // End all previous ranges of Var.
     506          65 :       OpenRanges.erase(VarLocIDs[ID].Var);
     507             : 
     508             :       // Add the VarLoc to OpenRanges.
     509          65 :       VarLoc VL(*SpDMI, LS);
     510          65 :       unsigned SpillLocID = VarLocIDs.insert(VL);
     511          65 :       OpenRanges.insert(SpillLocID, VL.Var);
     512             :       return;
     513             :     }
     514             :   }
     515             : }
     516             : 
     517             : /// Terminate all open ranges at the end of the current basic block.
     518     2261619 : bool LiveDebugValues::transferTerminatorInst(MachineInstr &MI,
     519             :                                              OpenRangesSet &OpenRanges,
     520             :                                              VarLocInMBB &OutLocs,
     521             :                                              const VarLocMap &VarLocIDs) {
     522             :   bool Changed = false;
     523     2261619 :   const MachineBasicBlock *CurMBB = MI.getParent();
     524     4389420 :   if (!(MI.isTerminator() || (&MI == &CurMBB->back())))
     525             :     return false;
     526             : 
     527      210178 :   if (OpenRanges.empty())
     528             :     return false;
     529             : 
     530             :   LLVM_DEBUG(for (unsigned ID
     531             :                   : OpenRanges.getVarLocs()) {
     532             :     // Copy OpenRanges to OutLocs, if not already present.
     533             :     dbgs() << "Add to OutLocs: ";
     534             :     VarLocIDs[ID].dump();
     535             :   });
     536             :   VarLocSet &VLS = OutLocs[CurMBB];
     537       12733 :   Changed = VLS |= OpenRanges.getVarLocs();
     538       12733 :   OpenRanges.clear();
     539             :   return Changed;
     540             : }
     541             : 
     542             : /// This routine creates OpenRanges and OutLocs.
     543     2261619 : bool LiveDebugValues::transfer(MachineInstr &MI, OpenRangesSet &OpenRanges,
     544             :                                VarLocInMBB &OutLocs, VarLocMap &VarLocIDs,
     545             :                                SpillMap &Spills, bool transferSpills) {
     546             :   bool Changed = false;
     547     2261619 :   transferDebugValue(MI, OpenRanges, VarLocIDs);
     548     2261619 :   transferRegisterDef(MI, OpenRanges, VarLocIDs);
     549     2261619 :   if (transferSpills)
     550      101117 :     transferSpillInst(MI, OpenRanges, VarLocIDs, Spills);
     551     2261619 :   Changed = transferTerminatorInst(MI, OpenRanges, OutLocs, VarLocIDs);
     552     2261619 :   return Changed;
     553             : }
     554             : 
     555             : /// This routine joins the analysis results of all incoming edges in @MBB by
     556             : /// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same
     557             : /// source variable in all the predecessors of @MBB reside in the same location.
     558      207514 : bool LiveDebugValues::join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs,
     559             :                            VarLocInMBB &InLocs, const VarLocMap &VarLocIDs,
     560             :                            SmallPtrSet<const MachineBasicBlock *, 16> &Visited) {
     561             :   LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getName() << "\n");
     562             :   bool Changed = false;
     563             : 
     564             :   VarLocSet InLocsT; // Temporary incoming locations.
     565             : 
     566             :   // For all predecessors of this MBB, find the set of VarLocs that
     567             :   // can be joined.
     568             :   int NumVisited = 0;
     569      235549 :   for (auto p : MBB.predecessors()) {
     570             :     // Ignore unvisited predecessor blocks.  As we are processing
     571             :     // the blocks in reverse post-order any unvisited block can
     572             :     // be considered to not remove any incoming values.
     573      180817 :     if (!Visited.count(p))
     574         772 :       continue;
     575      180045 :     auto OL = OutLocs.find(p);
     576             :     // Join is null in case of empty OutLocs from any of the pred.
     577      180045 :     if (OL == OutLocs.end())
     578      152782 :       return false;
     579             : 
     580             :     // Just copy over the Out locs to incoming locs for the first visited
     581             :     // predecessor, and for all other predecessors join the Out locs.
     582       27263 :     if (!NumVisited)
     583       18764 :       InLocsT = OL->second;
     584             :     else
     585        8499 :       InLocsT &= OL->second;
     586       27263 :     NumVisited++;
     587             :   }
     588             : 
     589             :   // Filter out DBG_VALUES that are out of scope.
     590             :   VarLocSet KillSet;
     591       94498 :   for (auto ID : InLocsT)
     592       94498 :     if (!VarLocIDs[ID].dominates(MBB))
     593       24170 :       KillSet.set(ID);
     594       54732 :   InLocsT.intersectWithComplement(KillSet);
     595             : 
     596             :   // As we are processing blocks in reverse post-order we
     597             :   // should have processed at least one predecessor, unless it
     598             :   // is the entry block which has no predecessor.
     599             :   assert((NumVisited || MBB.pred_empty()) &&
     600             :          "Should have processed at least one predecessor");
     601       54732 :   if (InLocsT.empty())
     602             :     return false;
     603             : 
     604       35964 :   VarLocSet &ILS = InLocs[&MBB];
     605             : 
     606             :   // Insert DBG_VALUE instructions, if not already inserted.
     607       17982 :   VarLocSet Diff = InLocsT;
     608       17982 :   Diff.intersectWithComplement(ILS);
     609       37087 :   for (auto ID : Diff) {
     610             :     // This VarLoc is not found in InLocs i.e. it is not yet inserted. So, a
     611             :     // new range is started for the var from the mbb's beginning by inserting
     612             :     // a new DBG_VALUE. transfer() will end this range however appropriate.
     613             :     const VarLoc &DiffIt = VarLocIDs[ID];
     614       37087 :     const MachineInstr *DMI = &DiffIt.MI;
     615             :     MachineInstr *MI =
     616       74174 :         BuildMI(MBB, MBB.instr_begin(), DMI->getDebugLoc(), DMI->getDesc(),
     617       37087 :                 DMI->isIndirectDebugValue(), DMI->getOperand(0).getReg(),
     618      185435 :                 DMI->getDebugVariable(), DMI->getDebugExpression());
     619             :     if (DMI->isIndirectDebugValue())
     620        8928 :       MI->getOperand(1).setImm(DMI->getOperand(1).getImm());
     621             :     LLVM_DEBUG(dbgs() << "Inserted: "; MI->dump(););
     622       37087 :     ILS.set(ID);
     623             :     ++NumInserted;
     624             :     Changed = true;
     625             :   }
     626             :   return Changed;
     627             : }
     628             : 
     629             : /// Calculate the liveness information for the given machine function and
     630             : /// extend ranges across basic blocks.
     631       36218 : bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
     632             :   LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n");
     633             : 
     634             :   bool Changed = false;
     635             :   bool OLChanged = false;
     636             :   bool MBBJoined = false;
     637             : 
     638             :   VarLocMap VarLocIDs;      // Map VarLoc<>unique ID for use in bitvectors.
     639       36218 :   OpenRangesSet OpenRanges; // Ranges that are open until end of bb.
     640       36218 :   VarLocInMBB OutLocs;      // Ranges that exist beyond bb.
     641       36218 :   VarLocInMBB InLocs;       // Ranges that are incoming after joining.
     642             :   SpillMap Spills;          // DBG_VALUEs associated with spills.
     643             : 
     644             :   DenseMap<unsigned int, MachineBasicBlock *> OrderToBB;
     645             :   DenseMap<MachineBasicBlock *, unsigned int> BBToOrder;
     646             :   std::priority_queue<unsigned int, std::vector<unsigned int>,
     647             :                       std::greater<unsigned int>>
     648             :       Worklist;
     649             :   std::priority_queue<unsigned int, std::vector<unsigned int>,
     650             :                       std::greater<unsigned int>>
     651             :       Pending;
     652             : 
     653             :   // Initialize every mbb with OutLocs.
     654             :   // We are not looking at any spill instructions during the initial pass
     655             :   // over the BBs. The LiveDebugVariables pass has already created DBG_VALUE
     656             :   // instructions for spills of registers that are known to be user variables
     657             :   // within the BB in which the spill occurs.
     658      234954 :   for (auto &MBB : MF)
     659     2557974 :     for (auto &MI : MBB)
     660     2160502 :       transfer(MI, OpenRanges, OutLocs, VarLocIDs, Spills,
     661             :                /*transferSpills=*/false);
     662             : 
     663             :   LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
     664             :                               "OutLocs after initialization", dbgs()));
     665             : 
     666             :   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
     667       36218 :   unsigned int RPONumber = 0;
     668      234944 :   for (auto RI = RPOT.begin(), RE = RPOT.end(); RI != RE; ++RI) {
     669      198726 :     OrderToBB[RPONumber] = *RI;
     670      198726 :     BBToOrder[*RI] = RPONumber;
     671      198726 :     Worklist.push(RPONumber);
     672      198726 :     ++RPONumber;
     673             :   }
     674             :   // This is a standard "union of predecessor outs" dataflow problem.
     675             :   // To solve it, we perform join() and transfer() using the two worklist method
     676             :   // until the ranges converge.
     677             :   // Ranges have converged when both worklists are empty.
     678             :   SmallPtrSet<const MachineBasicBlock *, 16> Visited;
     679      145774 :   while (!Worklist.empty() || !Pending.empty()) {
     680             :     // We track what is on the pending worklist to avoid inserting the same
     681             :     // thing twice.  We could avoid this with a custom priority queue, but this
     682             :     // is probably not worth it.
     683             :     SmallPtrSet<MachineBasicBlock *, 16> OnPending;
     684             :     LLVM_DEBUG(dbgs() << "Processing Worklist\n");
     685      244183 :     while (!Worklist.empty()) {
     686      207514 :       MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
     687             :       Worklist.pop();
     688      207514 :       MBBJoined = join(*MBB, OutLocs, InLocs, VarLocIDs, Visited);
     689      207514 :       Visited.insert(MBB);
     690      207514 :       if (MBBJoined) {
     691             :         MBBJoined = false;
     692             :         Changed = true;
     693             :         // Now that we have started to extend ranges across BBs we need to
     694             :         // examine spill instructions to see whether they spill registers that
     695             :         // correspond to user variables.
     696      120137 :         for (auto &MI : *MBB)
     697      101117 :           OLChanged |= transfer(MI, OpenRanges, OutLocs, VarLocIDs, Spills,
     698             :                                 /*transferSpills=*/true);
     699             : 
     700             :         // Add any DBG_VALUE instructions necessitated by spills.
     701        9640 :         for (auto &SP : Spills)
     702          65 :           MBB->insertAfter(MachineBasicBlock::iterator(*SP.SpillInst),
     703          65 :                            SP.DebugInst);
     704             :         Spills.clear();
     705             : 
     706             :         LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
     707             :                                     "OutLocs after propagating", dbgs()));
     708             :         LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs,
     709             :                                     "InLocs after propagating", dbgs()));
     710             : 
     711        9510 :         if (OLChanged) {
     712             :           OLChanged = false;
     713       21861 :           for (auto s : MBB->successors())
     714       13009 :             if (OnPending.insert(s).second) {
     715        8788 :               Pending.push(BBToOrder[s]);
     716             :             }
     717             :         }
     718             :       }
     719             :     }
     720             :     Worklist.swap(Pending);
     721             :     // At this point, pending must be empty, since it was just the empty
     722             :     // worklist
     723             :     assert(Pending.empty() && "Pending should be empty");
     724             :   }
     725             : 
     726             :   LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "Final OutLocs", dbgs()));
     727             :   LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, "Final InLocs", dbgs()));
     728       36218 :   return Changed;
     729             : }
     730             : 
     731      218372 : bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) {
     732      218372 :   if (!MF.getFunction().getSubprogram())
     733             :     // LiveDebugValues will already have removed all DBG_VALUEs.
     734             :     return false;
     735             : 
     736             :   // Skip functions from NoDebug compilation units.
     737       72468 :   if (MF.getFunction().getSubprogram()->getUnit()->getEmissionKind() ==
     738             :       DICompileUnit::NoDebug)
     739             :     return false;
     740             : 
     741       36218 :   TRI = MF.getSubtarget().getRegisterInfo();
     742       36218 :   TII = MF.getSubtarget().getInstrInfo();
     743       36218 :   TFI = MF.getSubtarget().getFrameLowering();
     744       36218 :   LS.initialize(MF);
     745             : 
     746       36218 :   bool Changed = ExtendRanges(MF);
     747       36218 :   return Changed;
     748             : }

Generated by: LCOV version 1.13