DbgValueHistoryCalculator.cpp revision 288943
1//===-- llvm/CodeGen/AsmPrinter/DbgValueHistoryCalculator.cpp -------------===// 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#include "DbgValueHistoryCalculator.h" 11#include "llvm/ADT/BitVector.h" 12#include "llvm/ADT/SmallVector.h" 13#include "llvm/CodeGen/MachineBasicBlock.h" 14#include "llvm/CodeGen/MachineFunction.h" 15#include "llvm/IR/DebugInfo.h" 16#include "llvm/Support/Debug.h" 17#include "llvm/Support/raw_ostream.h" 18#include "llvm/Target/TargetRegisterInfo.h" 19#include <algorithm> 20#include <map> 21using namespace llvm; 22 23#define DEBUG_TYPE "dwarfdebug" 24 25// \brief If @MI is a DBG_VALUE with debug value described by a 26// defined register, returns the number of this register. 27// In the other case, returns 0. 28static unsigned isDescribedByReg(const MachineInstr &MI) { 29 assert(MI.isDebugValue()); 30 assert(MI.getNumOperands() == 4); 31 // If location of variable is described using a register (directly or 32 // indirecltly), this register is always a first operand. 33 return MI.getOperand(0).isReg() ? MI.getOperand(0).getReg() : 0; 34} 35 36void DbgValueHistoryMap::startInstrRange(InlinedVariable Var, 37 const MachineInstr &MI) { 38 // Instruction range should start with a DBG_VALUE instruction for the 39 // variable. 40 assert(MI.isDebugValue() && "not a DBG_VALUE"); 41 auto &Ranges = VarInstrRanges[Var]; 42 if (!Ranges.empty() && Ranges.back().second == nullptr && 43 Ranges.back().first->isIdenticalTo(&MI)) { 44 DEBUG(dbgs() << "Coalescing identical DBG_VALUE entries:\n" 45 << "\t" << Ranges.back().first << "\t" << MI << "\n"); 46 return; 47 } 48 Ranges.push_back(std::make_pair(&MI, nullptr)); 49} 50 51void DbgValueHistoryMap::endInstrRange(InlinedVariable Var, 52 const MachineInstr &MI) { 53 auto &Ranges = VarInstrRanges[Var]; 54 // Verify that the current instruction range is not yet closed. 55 assert(!Ranges.empty() && Ranges.back().second == nullptr); 56 // For now, instruction ranges are not allowed to cross basic block 57 // boundaries. 58 assert(Ranges.back().first->getParent() == MI.getParent()); 59 Ranges.back().second = &MI; 60} 61 62unsigned DbgValueHistoryMap::getRegisterForVar(InlinedVariable Var) const { 63 const auto &I = VarInstrRanges.find(Var); 64 if (I == VarInstrRanges.end()) 65 return 0; 66 const auto &Ranges = I->second; 67 if (Ranges.empty() || Ranges.back().second != nullptr) 68 return 0; 69 return isDescribedByReg(*Ranges.back().first); 70} 71 72namespace { 73// Maps physreg numbers to the variables they describe. 74typedef DbgValueHistoryMap::InlinedVariable InlinedVariable; 75typedef std::map<unsigned, SmallVector<InlinedVariable, 1>> RegDescribedVarsMap; 76} 77 78// \brief Claim that @Var is not described by @RegNo anymore. 79static void dropRegDescribedVar(RegDescribedVarsMap &RegVars, unsigned RegNo, 80 InlinedVariable Var) { 81 const auto &I = RegVars.find(RegNo); 82 assert(RegNo != 0U && I != RegVars.end()); 83 auto &VarSet = I->second; 84 const auto &VarPos = std::find(VarSet.begin(), VarSet.end(), Var); 85 assert(VarPos != VarSet.end()); 86 VarSet.erase(VarPos); 87 // Don't keep empty sets in a map to keep it as small as possible. 88 if (VarSet.empty()) 89 RegVars.erase(I); 90} 91 92// \brief Claim that @Var is now described by @RegNo. 93static void addRegDescribedVar(RegDescribedVarsMap &RegVars, unsigned RegNo, 94 InlinedVariable Var) { 95 assert(RegNo != 0U); 96 auto &VarSet = RegVars[RegNo]; 97 assert(std::find(VarSet.begin(), VarSet.end(), Var) == VarSet.end()); 98 VarSet.push_back(Var); 99} 100 101// \brief Terminate the location range for variables described by register at 102// @I by inserting @ClobberingInstr to their history. 103static void clobberRegisterUses(RegDescribedVarsMap &RegVars, 104 RegDescribedVarsMap::iterator I, 105 DbgValueHistoryMap &HistMap, 106 const MachineInstr &ClobberingInstr) { 107 // Iterate over all variables described by this register and add this 108 // instruction to their history, clobbering it. 109 for (const auto &Var : I->second) 110 HistMap.endInstrRange(Var, ClobberingInstr); 111 RegVars.erase(I); 112} 113 114// \brief Terminate the location range for variables described by register 115// @RegNo by inserting @ClobberingInstr to their history. 116static void clobberRegisterUses(RegDescribedVarsMap &RegVars, unsigned RegNo, 117 DbgValueHistoryMap &HistMap, 118 const MachineInstr &ClobberingInstr) { 119 const auto &I = RegVars.find(RegNo); 120 if (I == RegVars.end()) 121 return; 122 clobberRegisterUses(RegVars, I, HistMap, ClobberingInstr); 123} 124 125// \brief Collect all registers clobbered by @MI and apply the functor 126// @Func to their RegNo. 127// @Func should be a functor with a void(unsigned) signature. We're 128// not using std::function here for performance reasons. It has a 129// small but measurable impact. By using a functor instead of a 130// std::set& here, we can avoid the overhead of constructing 131// temporaries in calculateDbgValueHistory, which has a significant 132// performance impact. 133template<typename Callable> 134static void applyToClobberedRegisters(const MachineInstr &MI, 135 const TargetRegisterInfo *TRI, 136 Callable Func) { 137 for (const MachineOperand &MO : MI.operands()) { 138 if (!MO.isReg() || !MO.isDef() || !MO.getReg()) 139 continue; 140 for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI) 141 Func(*AI); 142 } 143} 144 145// \brief Returns the first instruction in @MBB which corresponds to 146// the function epilogue, or nullptr if @MBB doesn't contain an epilogue. 147static const MachineInstr *getFirstEpilogueInst(const MachineBasicBlock &MBB) { 148 auto LastMI = MBB.getLastNonDebugInstr(); 149 if (LastMI == MBB.end() || !LastMI->isReturn()) 150 return nullptr; 151 // Assume that epilogue starts with instruction having the same debug location 152 // as the return instruction. 153 DebugLoc LastLoc = LastMI->getDebugLoc(); 154 auto Res = LastMI; 155 for (MachineBasicBlock::const_reverse_iterator I(std::next(LastMI)), 156 E = MBB.rend(); 157 I != E; ++I) { 158 if (I->getDebugLoc() != LastLoc) 159 return Res; 160 Res = &*I; 161 } 162 // If all instructions have the same debug location, assume whole MBB is 163 // an epilogue. 164 return MBB.begin(); 165} 166 167// \brief Collect registers that are modified in the function body (their 168// contents is changed outside of the prologue and epilogue). 169static void collectChangingRegs(const MachineFunction *MF, 170 const TargetRegisterInfo *TRI, 171 BitVector &Regs) { 172 for (const auto &MBB : *MF) { 173 auto FirstEpilogueInst = getFirstEpilogueInst(MBB); 174 175 for (const auto &MI : MBB) { 176 if (&MI == FirstEpilogueInst) 177 break; 178 if (!MI.getFlag(MachineInstr::FrameSetup)) 179 applyToClobberedRegisters(MI, TRI, [&](unsigned r) { Regs.set(r); }); 180 } 181 } 182} 183 184void llvm::calculateDbgValueHistory(const MachineFunction *MF, 185 const TargetRegisterInfo *TRI, 186 DbgValueHistoryMap &Result) { 187 BitVector ChangingRegs(TRI->getNumRegs()); 188 collectChangingRegs(MF, TRI, ChangingRegs); 189 190 RegDescribedVarsMap RegVars; 191 for (const auto &MBB : *MF) { 192 for (const auto &MI : MBB) { 193 if (!MI.isDebugValue()) { 194 // Not a DBG_VALUE instruction. It may clobber registers which describe 195 // some variables. 196 applyToClobberedRegisters(MI, TRI, [&](unsigned RegNo) { 197 if (ChangingRegs.test(RegNo)) 198 clobberRegisterUses(RegVars, RegNo, Result, MI); 199 }); 200 continue; 201 } 202 203 assert(MI.getNumOperands() > 1 && "Invalid DBG_VALUE instruction!"); 204 // Use the base variable (without any DW_OP_piece expressions) 205 // as index into History. The full variables including the 206 // piece expressions are attached to the MI. 207 const DILocalVariable *RawVar = MI.getDebugVariable(); 208 assert(RawVar->isValidLocationForIntrinsic(MI.getDebugLoc()) && 209 "Expected inlined-at fields to agree"); 210 InlinedVariable Var(RawVar, MI.getDebugLoc()->getInlinedAt()); 211 212 if (unsigned PrevReg = Result.getRegisterForVar(Var)) 213 dropRegDescribedVar(RegVars, PrevReg, Var); 214 215 Result.startInstrRange(Var, MI); 216 217 if (unsigned NewReg = isDescribedByReg(MI)) 218 addRegDescribedVar(RegVars, NewReg, Var); 219 } 220 221 // Make sure locations for register-described variables are valid only 222 // until the end of the basic block (unless it's the last basic block, in 223 // which case let their liveness run off to the end of the function). 224 if (!MBB.empty() && &MBB != &MF->back()) { 225 for (auto I = RegVars.begin(), E = RegVars.end(); I != E;) { 226 auto CurElem = I++; // CurElem can be erased below. 227 if (ChangingRegs.test(CurElem->first)) 228 clobberRegisterUses(RegVars, CurElem, Result, MBB.back()); 229 } 230 } 231 } 232} 233