1274955Ssvnmir//===-- llvm/CodeGen/AsmPrinter/DbgValueHistoryCalculator.cpp -------------===// 2274955Ssvnmir// 3274955Ssvnmir// The LLVM Compiler Infrastructure 4274955Ssvnmir// 5274955Ssvnmir// This file is distributed under the University of Illinois Open Source 6274955Ssvnmir// License. See LICENSE.TXT for details. 7274955Ssvnmir// 8274955Ssvnmir//===----------------------------------------------------------------------===// 9274955Ssvnmir 10274955Ssvnmir#include "DbgValueHistoryCalculator.h" 11280031Sdim#include "llvm/ADT/BitVector.h" 12274955Ssvnmir#include "llvm/ADT/SmallVector.h" 13274955Ssvnmir#include "llvm/CodeGen/MachineBasicBlock.h" 14274955Ssvnmir#include "llvm/CodeGen/MachineFunction.h" 15280031Sdim#include "llvm/IR/DebugInfo.h" 16274955Ssvnmir#include "llvm/Support/Debug.h" 17288943Sdim#include "llvm/Support/raw_ostream.h" 18274955Ssvnmir#include "llvm/Target/TargetRegisterInfo.h" 19274955Ssvnmir#include <algorithm> 20274955Ssvnmir#include <map> 21280031Sdimusing namespace llvm; 22274955Ssvnmir 23274955Ssvnmir#define DEBUG_TYPE "dwarfdebug" 24274955Ssvnmir 25274955Ssvnmir// \brief If @MI is a DBG_VALUE with debug value described by a 26274955Ssvnmir// defined register, returns the number of this register. 27274955Ssvnmir// In the other case, returns 0. 28274955Ssvnmirstatic unsigned isDescribedByReg(const MachineInstr &MI) { 29274955Ssvnmir assert(MI.isDebugValue()); 30280031Sdim assert(MI.getNumOperands() == 4); 31274955Ssvnmir // If location of variable is described using a register (directly or 32274955Ssvnmir // indirecltly), this register is always a first operand. 33274955Ssvnmir return MI.getOperand(0).isReg() ? MI.getOperand(0).getReg() : 0; 34274955Ssvnmir} 35274955Ssvnmir 36288943Sdimvoid DbgValueHistoryMap::startInstrRange(InlinedVariable Var, 37274955Ssvnmir const MachineInstr &MI) { 38274955Ssvnmir // Instruction range should start with a DBG_VALUE instruction for the 39274955Ssvnmir // variable. 40280031Sdim assert(MI.isDebugValue() && "not a DBG_VALUE"); 41274955Ssvnmir auto &Ranges = VarInstrRanges[Var]; 42274955Ssvnmir if (!Ranges.empty() && Ranges.back().second == nullptr && 43274955Ssvnmir Ranges.back().first->isIdenticalTo(&MI)) { 44274955Ssvnmir DEBUG(dbgs() << "Coalescing identical DBG_VALUE entries:\n" 45274955Ssvnmir << "\t" << Ranges.back().first << "\t" << MI << "\n"); 46274955Ssvnmir return; 47274955Ssvnmir } 48274955Ssvnmir Ranges.push_back(std::make_pair(&MI, nullptr)); 49274955Ssvnmir} 50274955Ssvnmir 51288943Sdimvoid DbgValueHistoryMap::endInstrRange(InlinedVariable Var, 52274955Ssvnmir const MachineInstr &MI) { 53274955Ssvnmir auto &Ranges = VarInstrRanges[Var]; 54274955Ssvnmir // Verify that the current instruction range is not yet closed. 55274955Ssvnmir assert(!Ranges.empty() && Ranges.back().second == nullptr); 56274955Ssvnmir // For now, instruction ranges are not allowed to cross basic block 57274955Ssvnmir // boundaries. 58274955Ssvnmir assert(Ranges.back().first->getParent() == MI.getParent()); 59274955Ssvnmir Ranges.back().second = &MI; 60274955Ssvnmir} 61274955Ssvnmir 62288943Sdimunsigned DbgValueHistoryMap::getRegisterForVar(InlinedVariable Var) const { 63274955Ssvnmir const auto &I = VarInstrRanges.find(Var); 64274955Ssvnmir if (I == VarInstrRanges.end()) 65274955Ssvnmir return 0; 66274955Ssvnmir const auto &Ranges = I->second; 67274955Ssvnmir if (Ranges.empty() || Ranges.back().second != nullptr) 68274955Ssvnmir return 0; 69274955Ssvnmir return isDescribedByReg(*Ranges.back().first); 70274955Ssvnmir} 71274955Ssvnmir 72274955Ssvnmirnamespace { 73274955Ssvnmir// Maps physreg numbers to the variables they describe. 74288943Sdimtypedef DbgValueHistoryMap::InlinedVariable InlinedVariable; 75288943Sdimtypedef std::map<unsigned, SmallVector<InlinedVariable, 1>> RegDescribedVarsMap; 76274955Ssvnmir} 77274955Ssvnmir 78274955Ssvnmir// \brief Claim that @Var is not described by @RegNo anymore. 79288943Sdimstatic void dropRegDescribedVar(RegDescribedVarsMap &RegVars, unsigned RegNo, 80288943Sdim InlinedVariable Var) { 81274955Ssvnmir const auto &I = RegVars.find(RegNo); 82274955Ssvnmir assert(RegNo != 0U && I != RegVars.end()); 83274955Ssvnmir auto &VarSet = I->second; 84274955Ssvnmir const auto &VarPos = std::find(VarSet.begin(), VarSet.end(), Var); 85274955Ssvnmir assert(VarPos != VarSet.end()); 86274955Ssvnmir VarSet.erase(VarPos); 87274955Ssvnmir // Don't keep empty sets in a map to keep it as small as possible. 88274955Ssvnmir if (VarSet.empty()) 89274955Ssvnmir RegVars.erase(I); 90274955Ssvnmir} 91274955Ssvnmir 92274955Ssvnmir// \brief Claim that @Var is now described by @RegNo. 93288943Sdimstatic void addRegDescribedVar(RegDescribedVarsMap &RegVars, unsigned RegNo, 94288943Sdim InlinedVariable Var) { 95274955Ssvnmir assert(RegNo != 0U); 96274955Ssvnmir auto &VarSet = RegVars[RegNo]; 97274955Ssvnmir assert(std::find(VarSet.begin(), VarSet.end(), Var) == VarSet.end()); 98274955Ssvnmir VarSet.push_back(Var); 99274955Ssvnmir} 100274955Ssvnmir 101280031Sdim// \brief Terminate the location range for variables described by register at 102280031Sdim// @I by inserting @ClobberingInstr to their history. 103280031Sdimstatic void clobberRegisterUses(RegDescribedVarsMap &RegVars, 104280031Sdim RegDescribedVarsMap::iterator I, 105280031Sdim DbgValueHistoryMap &HistMap, 106280031Sdim const MachineInstr &ClobberingInstr) { 107280031Sdim // Iterate over all variables described by this register and add this 108280031Sdim // instruction to their history, clobbering it. 109280031Sdim for (const auto &Var : I->second) 110280031Sdim HistMap.endInstrRange(Var, ClobberingInstr); 111280031Sdim RegVars.erase(I); 112280031Sdim} 113280031Sdim 114274955Ssvnmir// \brief Terminate the location range for variables described by register 115274955Ssvnmir// @RegNo by inserting @ClobberingInstr to their history. 116274955Ssvnmirstatic void clobberRegisterUses(RegDescribedVarsMap &RegVars, unsigned RegNo, 117274955Ssvnmir DbgValueHistoryMap &HistMap, 118274955Ssvnmir const MachineInstr &ClobberingInstr) { 119274955Ssvnmir const auto &I = RegVars.find(RegNo); 120274955Ssvnmir if (I == RegVars.end()) 121274955Ssvnmir return; 122280031Sdim clobberRegisterUses(RegVars, I, HistMap, ClobberingInstr); 123274955Ssvnmir} 124274955Ssvnmir 125280031Sdim// \brief Collect all registers clobbered by @MI and apply the functor 126280031Sdim// @Func to their RegNo. 127280031Sdim// @Func should be a functor with a void(unsigned) signature. We're 128280031Sdim// not using std::function here for performance reasons. It has a 129280031Sdim// small but measurable impact. By using a functor instead of a 130280031Sdim// std::set& here, we can avoid the overhead of constructing 131280031Sdim// temporaries in calculateDbgValueHistory, which has a significant 132280031Sdim// performance impact. 133280031Sdimtemplate<typename Callable> 134280031Sdimstatic void applyToClobberedRegisters(const MachineInstr &MI, 135274955Ssvnmir const TargetRegisterInfo *TRI, 136280031Sdim Callable Func) { 137274955Ssvnmir for (const MachineOperand &MO : MI.operands()) { 138274955Ssvnmir if (!MO.isReg() || !MO.isDef() || !MO.getReg()) 139274955Ssvnmir continue; 140274955Ssvnmir for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI) 141280031Sdim Func(*AI); 142274955Ssvnmir } 143274955Ssvnmir} 144274955Ssvnmir 145274955Ssvnmir// \brief Returns the first instruction in @MBB which corresponds to 146274955Ssvnmir// the function epilogue, or nullptr if @MBB doesn't contain an epilogue. 147274955Ssvnmirstatic const MachineInstr *getFirstEpilogueInst(const MachineBasicBlock &MBB) { 148274955Ssvnmir auto LastMI = MBB.getLastNonDebugInstr(); 149274955Ssvnmir if (LastMI == MBB.end() || !LastMI->isReturn()) 150274955Ssvnmir return nullptr; 151274955Ssvnmir // Assume that epilogue starts with instruction having the same debug location 152274955Ssvnmir // as the return instruction. 153274955Ssvnmir DebugLoc LastLoc = LastMI->getDebugLoc(); 154274955Ssvnmir auto Res = LastMI; 155280031Sdim for (MachineBasicBlock::const_reverse_iterator I(std::next(LastMI)), 156280031Sdim E = MBB.rend(); 157280031Sdim I != E; ++I) { 158274955Ssvnmir if (I->getDebugLoc() != LastLoc) 159274955Ssvnmir return Res; 160280031Sdim Res = &*I; 161274955Ssvnmir } 162274955Ssvnmir // If all instructions have the same debug location, assume whole MBB is 163274955Ssvnmir // an epilogue. 164274955Ssvnmir return MBB.begin(); 165274955Ssvnmir} 166274955Ssvnmir 167274955Ssvnmir// \brief Collect registers that are modified in the function body (their 168280031Sdim// contents is changed outside of the prologue and epilogue). 169274955Ssvnmirstatic void collectChangingRegs(const MachineFunction *MF, 170274955Ssvnmir const TargetRegisterInfo *TRI, 171280031Sdim BitVector &Regs) { 172274955Ssvnmir for (const auto &MBB : *MF) { 173274955Ssvnmir auto FirstEpilogueInst = getFirstEpilogueInst(MBB); 174280031Sdim 175274955Ssvnmir for (const auto &MI : MBB) { 176280031Sdim if (&MI == FirstEpilogueInst) 177280031Sdim break; 178280031Sdim if (!MI.getFlag(MachineInstr::FrameSetup)) 179280031Sdim applyToClobberedRegisters(MI, TRI, [&](unsigned r) { Regs.set(r); }); 180274955Ssvnmir } 181274955Ssvnmir } 182274955Ssvnmir} 183274955Ssvnmir 184280031Sdimvoid llvm::calculateDbgValueHistory(const MachineFunction *MF, 185280031Sdim const TargetRegisterInfo *TRI, 186280031Sdim DbgValueHistoryMap &Result) { 187280031Sdim BitVector ChangingRegs(TRI->getNumRegs()); 188274955Ssvnmir collectChangingRegs(MF, TRI, ChangingRegs); 189274955Ssvnmir 190274955Ssvnmir RegDescribedVarsMap RegVars; 191274955Ssvnmir for (const auto &MBB : *MF) { 192274955Ssvnmir for (const auto &MI : MBB) { 193274955Ssvnmir if (!MI.isDebugValue()) { 194274955Ssvnmir // Not a DBG_VALUE instruction. It may clobber registers which describe 195274955Ssvnmir // some variables. 196280031Sdim applyToClobberedRegisters(MI, TRI, [&](unsigned RegNo) { 197280031Sdim if (ChangingRegs.test(RegNo)) 198274955Ssvnmir clobberRegisterUses(RegVars, RegNo, Result, MI); 199280031Sdim }); 200274955Ssvnmir continue; 201274955Ssvnmir } 202274955Ssvnmir 203274955Ssvnmir assert(MI.getNumOperands() > 1 && "Invalid DBG_VALUE instruction!"); 204280031Sdim // Use the base variable (without any DW_OP_piece expressions) 205280031Sdim // as index into History. The full variables including the 206280031Sdim // piece expressions are attached to the MI. 207288943Sdim const DILocalVariable *RawVar = MI.getDebugVariable(); 208288943Sdim assert(RawVar->isValidLocationForIntrinsic(MI.getDebugLoc()) && 209288943Sdim "Expected inlined-at fields to agree"); 210288943Sdim InlinedVariable Var(RawVar, MI.getDebugLoc()->getInlinedAt()); 211274955Ssvnmir 212274955Ssvnmir if (unsigned PrevReg = Result.getRegisterForVar(Var)) 213274955Ssvnmir dropRegDescribedVar(RegVars, PrevReg, Var); 214274955Ssvnmir 215274955Ssvnmir Result.startInstrRange(Var, MI); 216274955Ssvnmir 217274955Ssvnmir if (unsigned NewReg = isDescribedByReg(MI)) 218274955Ssvnmir addRegDescribedVar(RegVars, NewReg, Var); 219274955Ssvnmir } 220274955Ssvnmir 221274955Ssvnmir // Make sure locations for register-described variables are valid only 222274955Ssvnmir // until the end of the basic block (unless it's the last basic block, in 223274955Ssvnmir // which case let their liveness run off to the end of the function). 224280031Sdim if (!MBB.empty() && &MBB != &MF->back()) { 225280031Sdim for (auto I = RegVars.begin(), E = RegVars.end(); I != E;) { 226280031Sdim auto CurElem = I++; // CurElem can be erased below. 227280031Sdim if (ChangingRegs.test(CurElem->first)) 228280031Sdim clobberRegisterUses(RegVars, CurElem, Result, MBB.back()); 229280031Sdim } 230274955Ssvnmir } 231274955Ssvnmir } 232274955Ssvnmir} 233