DbgValueHistoryCalculator.cpp revision dce4a407a24b04eebc6a376f8e62b41aaa7b071f 
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/SmallVector.h"
12#include "llvm/CodeGen/MachineBasicBlock.h"
13#include "llvm/CodeGen/MachineFunction.h"
14#include "llvm/Support/Debug.h"
15#include "llvm/Target/TargetRegisterInfo.h"
16#include <algorithm>
17#include <map>
18
19#define DEBUG_TYPE "dwarfdebug"
20
21namespace llvm {
22
23// \brief If @MI is a DBG_VALUE with debug value described by a
24// defined register, returns the number of this register.
25// In the other case, returns 0.
26static unsigned isDescribedByReg(const MachineInstr &MI) {
27  assert(MI.isDebugValue());
28  assert(MI.getNumOperands() == 3);
29  // If location of variable is described using a register (directly or
30  // indirecltly), this register is always a first operand.
31  return MI.getOperand(0).isReg() ? MI.getOperand(0).getReg() : 0;
32}
33
34void DbgValueHistoryMap::startInstrRange(const MDNode *Var,
35                                         const MachineInstr &MI) {
36  // Instruction range should start with a DBG_VALUE instruction for the
37  // variable.
38  assert(MI.isDebugValue() && MI.getDebugVariable() == Var);
39  auto &Ranges = VarInstrRanges[Var];
40  if (!Ranges.empty() && Ranges.back().second == nullptr &&
41      Ranges.back().first->isIdenticalTo(&MI)) {
42    DEBUG(dbgs() << "Coalescing identical DBG_VALUE entries:\n"
43                 << "\t" << Ranges.back().first << "\t" << MI << "\n");
44    return;
45  }
46  Ranges.push_back(std::make_pair(&MI, nullptr));
47}
48
49void DbgValueHistoryMap::endInstrRange(const MDNode *Var,
50                                       const MachineInstr &MI) {
51  auto &Ranges = VarInstrRanges[Var];
52  // Verify that the current instruction range is not yet closed.
53  assert(!Ranges.empty() && Ranges.back().second == nullptr);
54  // For now, instruction ranges are not allowed to cross basic block
55  // boundaries.
56  assert(Ranges.back().first->getParent() == MI.getParent());
57  Ranges.back().second = &MI;
58}
59
60unsigned DbgValueHistoryMap::getRegisterForVar(const MDNode *Var) const {
61  const auto &I = VarInstrRanges.find(Var);
62  if (I == VarInstrRanges.end())
63    return 0;
64  const auto &Ranges = I->second;
65  if (Ranges.empty() || Ranges.back().second != nullptr)
66    return 0;
67  return isDescribedByReg(*Ranges.back().first);
68}
69
70namespace {
71// Maps physreg numbers to the variables they describe.
72typedef std::map<unsigned, SmallVector<const MDNode *, 1>> RegDescribedVarsMap;
73}
74
75// \brief Claim that @Var is not described by @RegNo anymore.
76static void dropRegDescribedVar(RegDescribedVarsMap &RegVars,
77                                unsigned RegNo, const MDNode *Var) {
78  const auto &I = RegVars.find(RegNo);
79  assert(RegNo != 0U && I != RegVars.end());
80  auto &VarSet = I->second;
81  const auto &VarPos = std::find(VarSet.begin(), VarSet.end(), Var);
82  assert(VarPos != VarSet.end());
83  VarSet.erase(VarPos);
84  // Don't keep empty sets in a map to keep it as small as possible.
85  if (VarSet.empty())
86    RegVars.erase(I);
87}
88
89// \brief Claim that @Var is now described by @RegNo.
90static void addRegDescribedVar(RegDescribedVarsMap &RegVars,
91                               unsigned RegNo, const MDNode *Var) {
92  assert(RegNo != 0U);
93  auto &VarSet = RegVars[RegNo];
94  assert(std::find(VarSet.begin(), VarSet.end(), Var) == VarSet.end());
95  VarSet.push_back(Var);
96}
97
98// \brief Terminate the location range for variables described by register
99// @RegNo by inserting @ClobberingInstr to their history.
100static void clobberRegisterUses(RegDescribedVarsMap &RegVars, unsigned RegNo,
101                                DbgValueHistoryMap &HistMap,
102                                const MachineInstr &ClobberingInstr) {
103  const auto &I = RegVars.find(RegNo);
104  if (I == RegVars.end())
105    return;
106  // Iterate over all variables described by this register and add this
107  // instruction to their history, clobbering it.
108  for (const auto &Var : I->second)
109    HistMap.endInstrRange(Var, ClobberingInstr);
110  RegVars.erase(I);
111}
112
113// \brief Terminate location ranges for all variables, described by registers
114// clobbered by @MI.
115static void clobberRegisterUses(RegDescribedVarsMap &RegVars,
116                                const MachineInstr &MI,
117                                const TargetRegisterInfo *TRI,
118                                DbgValueHistoryMap &HistMap) {
119  for (const MachineOperand &MO : MI.operands()) {
120    if (!MO.isReg() || !MO.isDef() || !MO.getReg())
121      continue;
122    for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid();
123         ++AI) {
124      unsigned RegNo = *AI;
125      clobberRegisterUses(RegVars, RegNo, HistMap, MI);
126    }
127  }
128}
129
130// \brief Terminate the location range for all register-described variables
131// by inserting @ClobberingInstr to their history.
132static void clobberAllRegistersUses(RegDescribedVarsMap &RegVars,
133                                    DbgValueHistoryMap &HistMap,
134                                    const MachineInstr &ClobberingInstr) {
135  for (const auto &I : RegVars)
136    for (const auto &Var : I.second)
137      HistMap.endInstrRange(Var, ClobberingInstr);
138  RegVars.clear();
139}
140
141void calculateDbgValueHistory(const MachineFunction *MF,
142                              const TargetRegisterInfo *TRI,
143                              DbgValueHistoryMap &Result) {
144  RegDescribedVarsMap RegVars;
145
146  for (const auto &MBB : *MF) {
147    for (const auto &MI : MBB) {
148      if (!MI.isDebugValue()) {
149        // Not a DBG_VALUE instruction. It may clobber registers which describe
150        // some variables.
151        clobberRegisterUses(RegVars, MI, TRI, Result);
152        continue;
153      }
154
155      assert(MI.getNumOperands() > 1 && "Invalid DBG_VALUE instruction!");
156      const MDNode *Var = MI.getDebugVariable();
157
158      if (unsigned PrevReg = Result.getRegisterForVar(Var))
159        dropRegDescribedVar(RegVars, PrevReg, Var);
160
161      Result.startInstrRange(Var, MI);
162
163      if (unsigned NewReg = isDescribedByReg(MI))
164        addRegDescribedVar(RegVars, NewReg, Var);
165    }
166
167    // Make sure locations for register-described variables are valid only
168    // until the end of the basic block (unless it's the last basic block, in
169    // which case let their liveness run off to the end of the function).
170    if (!MBB.empty() &&  &MBB != &MF->back())
171      clobberAllRegistersUses(RegVars, Result, MBB.back());
172  }
173}
174
175}
176