blob: 1624851088044e369136ea70023b852a9eb72818 [file] [log] [blame]
Jakob Stoklund Olesenbb7b23f2010-11-30 02:17:10 +00001//===- LiveDebugVariables.cpp - Tracking debug info variables -------------===//
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 file implements the LiveDebugVariables analysis.
11//
12// Remove all DBG_VALUE instructions referencing virtual registers and replace
13// them with a data structure tracking where live user variables are kept - in a
14// virtual register or in a stack slot.
15//
16// Allow the data structure to be updated during register allocation when values
17// are moved between registers and stack slots. Finally emit new DBG_VALUE
18// instructions after register allocation is complete.
19//
20//===----------------------------------------------------------------------===//
21
22#include "LiveDebugVariables.h"
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +000023#include "llvm/ADT/IntervalMap.h"
Devang Patelad90d3a2011-08-04 18:45:38 +000024#include "llvm/ADT/Statistic.h"
Devang Patelc722c3d2011-08-10 21:25:34 +000025#include "llvm/CodeGen/LexicalScopes.h"
Jakob Stoklund Olesenbb7b23f2010-11-30 02:17:10 +000026#include "llvm/CodeGen/LiveIntervalAnalysis.h"
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +000027#include "llvm/CodeGen/MachineDominators.h"
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +000028#include "llvm/CodeGen/MachineFunction.h"
29#include "llvm/CodeGen/MachineInstrBuilder.h"
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +000030#include "llvm/CodeGen/MachineRegisterInfo.h"
Jakob Stoklund Olesenbb7b23f2010-11-30 02:17:10 +000031#include "llvm/CodeGen/Passes.h"
Jakob Stoklund Olesen1ead68d2012-11-28 19:13:06 +000032#include "llvm/CodeGen/VirtRegMap.h"
Chandler Carruth0b8c9a82013-01-02 11:36:10 +000033#include "llvm/IR/Constants.h"
Stephen Hines36b56882014-04-23 16:57:46 -070034#include "llvm/IR/DebugInfo.h"
Chandler Carruth0b8c9a82013-01-02 11:36:10 +000035#include "llvm/IR/Metadata.h"
36#include "llvm/IR/Value.h"
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +000037#include "llvm/Support/CommandLine.h"
38#include "llvm/Support/Debug.h"
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +000039#include "llvm/Target/TargetInstrInfo.h"
Jakob Stoklund Olesenbb7b23f2010-11-30 02:17:10 +000040#include "llvm/Target/TargetMachine.h"
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +000041#include "llvm/Target/TargetRegisterInfo.h"
Stephen Hines37ed9c12014-12-01 14:51:49 -080042#include "llvm/Target/TargetSubtargetInfo.h"
Jakob Stoklund Olesenbb7b23f2010-11-30 02:17:10 +000043
Stephen Hinesdce4a402014-05-29 02:49:00 -070044#include <memory>
45
Jakob Stoklund Olesenbb7b23f2010-11-30 02:17:10 +000046using namespace llvm;
47
Stephen Hinesdce4a402014-05-29 02:49:00 -070048#define DEBUG_TYPE "livedebug"
49
Devang Patel51a666f2011-01-07 22:33:41 +000050static cl::opt<bool>
Jakob Stoklund Olesen25dc2262011-01-12 23:36:21 +000051EnableLDV("live-debug-variables", cl::init(true),
Devang Patel51a666f2011-01-07 22:33:41 +000052 cl::desc("Enable the live debug variables pass"), cl::Hidden);
53
Devang Patelad90d3a2011-08-04 18:45:38 +000054STATISTIC(NumInsertedDebugValues, "Number of DBG_VALUEs inserted");
Jakob Stoklund Olesenbb7b23f2010-11-30 02:17:10 +000055char LiveDebugVariables::ID = 0;
56
57INITIALIZE_PASS_BEGIN(LiveDebugVariables, "livedebugvars",
58 "Debug Variable Analysis", false, false)
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +000059INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
Jakob Stoklund Olesenbb7b23f2010-11-30 02:17:10 +000060INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
61INITIALIZE_PASS_END(LiveDebugVariables, "livedebugvars",
62 "Debug Variable Analysis", false, false)
63
64void LiveDebugVariables::getAnalysisUsage(AnalysisUsage &AU) const {
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +000065 AU.addRequired<MachineDominatorTree>();
Jakob Stoklund Olesenbb7b23f2010-11-30 02:17:10 +000066 AU.addRequiredTransitive<LiveIntervals>();
67 AU.setPreservesAll();
68 MachineFunctionPass::getAnalysisUsage(AU);
69}
70
Stephen Hinesdce4a402014-05-29 02:49:00 -070071LiveDebugVariables::LiveDebugVariables() : MachineFunctionPass(ID), pImpl(nullptr) {
Jakob Stoklund Olesenbb7b23f2010-11-30 02:17:10 +000072 initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry());
73}
74
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +000075/// LocMap - Map of where a user value is live, and its location.
76typedef IntervalMap<SlotIndex, unsigned, 4> LocMap;
77
Benjamin Kramer76f58d22011-09-16 00:35:06 +000078namespace {
Stephen Hines36b56882014-04-23 16:57:46 -070079/// UserValueScopes - Keeps track of lexical scopes associated with a
Devang Patel3a2d80d2011-09-13 18:40:53 +000080/// user value's source location.
81class UserValueScopes {
82 DebugLoc DL;
83 LexicalScopes &LS;
84 SmallPtrSet<const MachineBasicBlock *, 4> LBlocks;
85
86public:
87 UserValueScopes(DebugLoc D, LexicalScopes &L) : DL(D), LS(L) {}
88
89 /// dominates - Return true if current scope dominates at least one machine
90 /// instruction in a given machine basic block.
91 bool dominates(MachineBasicBlock *MBB) {
92 if (LBlocks.empty())
93 LS.getMachineBasicBlocks(DL, LBlocks);
94 if (LBlocks.count(MBB) != 0 || LS.dominates(DL, MBB))
95 return true;
96 return false;
97 }
98};
Benjamin Kramer76f58d22011-09-16 00:35:06 +000099} // end anonymous namespace
Devang Patel3a2d80d2011-09-13 18:40:53 +0000100
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000101/// UserValue - A user value is a part of a debug info user variable.
102///
103/// A DBG_VALUE instruction notes that (a sub-register of) a virtual register
104/// holds part of a user variable. The part is identified by a byte offset.
105///
106/// UserValues are grouped into equivalence classes for easier searching. Two
107/// user values are related if they refer to the same variable, or if they are
108/// held by the same virtual register. The equivalence class is the transitive
109/// closure of that relation.
110namespace {
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000111class LDVImpl;
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000112class UserValue {
Stephen Hines37ed9c12014-12-01 14:51:49 -0800113 const MDNode *Variable; ///< The debug info variable we are part of.
114 const MDNode *Expression; ///< Any complex address expression.
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000115 unsigned offset; ///< Byte offset into variable.
Adrian Prantl35176402013-07-09 20:28:37 +0000116 bool IsIndirect; ///< true if this is a register-indirect+offset value.
Devang Patelf827cd72011-02-04 01:43:25 +0000117 DebugLoc dl; ///< The debug location for the variable. This is
118 ///< used by dwarf writer to find lexical scope.
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000119 UserValue *leader; ///< Equivalence class leader.
120 UserValue *next; ///< Next value in equivalence class, or null.
121
122 /// Numbered locations referenced by locmap.
Jakob Stoklund Olesen0804ead2011-01-09 05:33:21 +0000123 SmallVector<MachineOperand, 4> locations;
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000124
125 /// Map of slot indices where this value is live.
126 LocMap locInts;
127
Jakob Stoklund Olesen5daec222010-12-03 22:25:07 +0000128 /// coalesceLocation - After LocNo was changed, check if it has become
129 /// identical to another location, and coalesce them. This may cause LocNo or
130 /// a later location to be erased, but no earlier location will be erased.
131 void coalesceLocation(unsigned LocNo);
132
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +0000133 /// insertDebugValue - Insert a DBG_VALUE into MBB at Idx for LocNo.
134 void insertDebugValue(MachineBasicBlock *MBB, SlotIndex Idx, unsigned LocNo,
135 LiveIntervals &LIS, const TargetInstrInfo &TII);
136
Jakob Stoklund Olesenf42b6612011-05-06 18:00:02 +0000137 /// splitLocation - Replace OldLocNo ranges with NewRegs ranges where NewRegs
138 /// is live. Returns true if any changes were made.
Mark Lacey1feb5852013-08-14 23:50:04 +0000139 bool splitLocation(unsigned OldLocNo, ArrayRef<unsigned> NewRegs,
140 LiveIntervals &LIS);
Jakob Stoklund Olesenf42b6612011-05-06 18:00:02 +0000141
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000142public:
143 /// UserValue - Create a new UserValue.
Stephen Hines37ed9c12014-12-01 14:51:49 -0800144 UserValue(const MDNode *var, const MDNode *expr, unsigned o, bool i,
145 DebugLoc L, LocMap::Allocator &alloc)
146 : Variable(var), Expression(expr), offset(o), IsIndirect(i), dl(L),
147 leader(this), next(nullptr), locInts(alloc) {}
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000148
149 /// getLeader - Get the leader of this value's equivalence class.
150 UserValue *getLeader() {
151 UserValue *l = leader;
152 while (l != l->leader)
153 l = l->leader;
154 return leader = l;
155 }
156
157 /// getNext - Return the next UserValue in the equivalence class.
158 UserValue *getNext() const { return next; }
159
Devang Patela462d6e2011-07-06 23:09:51 +0000160 /// match - Does this UserValue match the parameters?
Stephen Hines37ed9c12014-12-01 14:51:49 -0800161 bool match(const MDNode *Var, const MDNode *Expr, unsigned Offset,
162 bool indirect) const {
163 return Var == Variable && Expr == Expression && Offset == offset &&
164 indirect == IsIndirect;
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000165 }
166
167 /// merge - Merge equivalence classes.
168 static UserValue *merge(UserValue *L1, UserValue *L2) {
169 L2 = L2->getLeader();
170 if (!L1)
171 return L2;
172 L1 = L1->getLeader();
173 if (L1 == L2)
174 return L1;
175 // Splice L2 before L1's members.
176 UserValue *End = L2;
177 while (End->next)
178 End->leader = L1, End = End->next;
179 End->leader = L1;
180 End->next = L1->next;
181 L1->next = L2;
182 return L1;
183 }
184
185 /// getLocationNo - Return the location number that matches Loc.
Jakob Stoklund Olesen0804ead2011-01-09 05:33:21 +0000186 unsigned getLocationNo(const MachineOperand &LocMO) {
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000187 if (LocMO.isReg()) {
188 if (LocMO.getReg() == 0)
189 return ~0u;
190 // For register locations we dont care about use/def and other flags.
191 for (unsigned i = 0, e = locations.size(); i != e; ++i)
192 if (locations[i].isReg() &&
193 locations[i].getReg() == LocMO.getReg() &&
194 locations[i].getSubReg() == LocMO.getSubReg())
195 return i;
196 } else
197 for (unsigned i = 0, e = locations.size(); i != e; ++i)
198 if (LocMO.isIdenticalTo(locations[i]))
199 return i;
Jakob Stoklund Olesen0804ead2011-01-09 05:33:21 +0000200 locations.push_back(LocMO);
201 // We are storing a MachineOperand outside a MachineInstr.
202 locations.back().clearParent();
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000203 // Don't store def operands.
204 if (locations.back().isReg())
205 locations.back().setIsUse();
Jakob Stoklund Olesen0804ead2011-01-09 05:33:21 +0000206 return locations.size() - 1;
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000207 }
208
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000209 /// mapVirtRegs - Ensure that all virtual register locations are mapped.
210 void mapVirtRegs(LDVImpl *LDV);
211
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000212 /// addDef - Add a definition point to this value.
213 void addDef(SlotIndex Idx, const MachineOperand &LocMO) {
214 // Add a singular (Idx,Idx) -> Loc mapping.
215 LocMap::iterator I = locInts.find(Idx);
216 if (!I.valid() || I.start() != Idx)
217 I.insert(Idx, Idx.getNextSlot(), getLocationNo(LocMO));
Jakob Stoklund Olesen79513ed2011-08-03 23:44:31 +0000218 else
219 // A later DBG_VALUE at the same SlotIndex overrides the old location.
220 I.setValue(getLocationNo(LocMO));
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000221 }
222
223 /// extendDef - Extend the current definition as far as possible down the
224 /// dominator tree. Stop when meeting an existing def or when leaving the live
225 /// range of VNI.
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000226 /// End points where VNI is no longer live are added to Kills.
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000227 /// @param Idx Starting point for the definition.
228 /// @param LocNo Location number to propagate.
Matthias Braun4f3b5e82013-10-10 21:29:02 +0000229 /// @param LR Restrict liveness to where LR has the value VNI. May be null.
230 /// @param VNI When LR is not null, this is the value to restrict to.
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000231 /// @param Kills Append end points of VNI's live range to Kills.
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000232 /// @param LIS Live intervals analysis.
233 /// @param MDT Dominator tree.
234 void extendDef(SlotIndex Idx, unsigned LocNo,
Matthias Braun4f3b5e82013-10-10 21:29:02 +0000235 LiveRange *LR, const VNInfo *VNI,
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000236 SmallVectorImpl<SlotIndex> *Kills,
Devang Patelc722c3d2011-08-10 21:25:34 +0000237 LiveIntervals &LIS, MachineDominatorTree &MDT,
Eric Christopherb82062f2012-03-15 21:33:39 +0000238 UserValueScopes &UVS);
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000239
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000240 /// addDefsFromCopies - The value in LI/LocNo may be copies to other
241 /// registers. Determine if any of the copies are available at the kill
242 /// points, and add defs if possible.
243 /// @param LI Scan for copies of the value in LI->reg.
244 /// @param LocNo Location number of LI->reg.
245 /// @param Kills Points where the range of LocNo could be extended.
246 /// @param NewDefs Append (Idx, LocNo) of inserted defs here.
247 void addDefsFromCopies(LiveInterval *LI, unsigned LocNo,
248 const SmallVectorImpl<SlotIndex> &Kills,
249 SmallVectorImpl<std::pair<SlotIndex, unsigned> > &NewDefs,
250 MachineRegisterInfo &MRI,
251 LiveIntervals &LIS);
252
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000253 /// computeIntervals - Compute the live intervals of all locations after
254 /// collecting all their def points.
Jakob Stoklund Olesene8a0a122012-06-22 17:15:32 +0000255 void computeIntervals(MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI,
Devang Patelc722c3d2011-08-10 21:25:34 +0000256 LiveIntervals &LIS, MachineDominatorTree &MDT,
Devang Patel3a2d80d2011-09-13 18:40:53 +0000257 UserValueScopes &UVS);
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000258
Jakob Stoklund Olesenf42b6612011-05-06 18:00:02 +0000259 /// splitRegister - Replace OldReg ranges with NewRegs ranges where NewRegs is
260 /// live. Returns true if any changes were made.
Mark Lacey1feb5852013-08-14 23:50:04 +0000261 bool splitRegister(unsigned OldLocNo, ArrayRef<unsigned> NewRegs,
262 LiveIntervals &LIS);
Jakob Stoklund Olesenf42b6612011-05-06 18:00:02 +0000263
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +0000264 /// rewriteLocations - Rewrite virtual register locations according to the
265 /// provided virtual register map.
266 void rewriteLocations(VirtRegMap &VRM, const TargetRegisterInfo &TRI);
267
Eric Christopherb3cecdf2013-02-13 02:29:18 +0000268 /// emitDebugValues - Recreate DBG_VALUE instruction from data structures.
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +0000269 void emitDebugValues(VirtRegMap *VRM,
270 LiveIntervals &LIS, const TargetInstrInfo &TRI);
271
Devang Patelf827cd72011-02-04 01:43:25 +0000272 /// findDebugLoc - Return DebugLoc used for this DBG_VALUE instruction. A
Stephen Hines37ed9c12014-12-01 14:51:49 -0800273 /// variable may have more than one corresponding DBG_VALUE instructions.
Devang Patelf827cd72011-02-04 01:43:25 +0000274 /// Only first one needs DebugLoc to identify variable's lexical scope
275 /// in source file.
276 DebugLoc findDebugLoc();
Devang Patel3a2d80d2011-09-13 18:40:53 +0000277
278 /// getDebugLoc - Return DebugLoc of this UserValue.
279 DebugLoc getDebugLoc() { return dl;}
Jakob Stoklund Olesene77150b2011-05-06 17:59:59 +0000280 void print(raw_ostream&, const TargetMachine*);
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000281};
282} // namespace
283
284/// LDVImpl - Implementation of the LiveDebugVariables pass.
285namespace {
286class LDVImpl {
287 LiveDebugVariables &pass;
288 LocMap::Allocator allocator;
289 MachineFunction *MF;
290 LiveIntervals *LIS;
Devang Patelc722c3d2011-08-10 21:25:34 +0000291 LexicalScopes LS;
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000292 MachineDominatorTree *MDT;
293 const TargetRegisterInfo *TRI;
294
Manman Renf0986202013-02-13 20:23:48 +0000295 /// Whether emitDebugValues is called.
296 bool EmitDone;
297 /// Whether the machine function is modified during the pass.
298 bool ModifiedMF;
299
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000300 /// userValues - All allocated UserValue instances.
Stephen Hinesdce4a402014-05-29 02:49:00 -0700301 SmallVector<std::unique_ptr<UserValue>, 8> userValues;
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000302
303 /// Map virtual register to eq class leader.
304 typedef DenseMap<unsigned, UserValue*> VRMap;
Jakob Stoklund Olesen6ed4c6a2010-12-03 22:25:09 +0000305 VRMap virtRegToEqClass;
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000306
307 /// Map user variable to eq class leader.
308 typedef DenseMap<const MDNode *, UserValue*> UVMap;
309 UVMap userVarMap;
310
311 /// getUserValue - Find or create a UserValue.
Stephen Hines37ed9c12014-12-01 14:51:49 -0800312 UserValue *getUserValue(const MDNode *Var, const MDNode *Expr,
313 unsigned Offset, bool IsIndirect, DebugLoc DL);
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000314
Jakob Stoklund Olesen30e21282010-12-02 18:15:44 +0000315 /// lookupVirtReg - Find the EC leader for VirtReg or null.
316 UserValue *lookupVirtReg(unsigned VirtReg);
317
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000318 /// handleDebugValue - Add DBG_VALUE instruction to our maps.
319 /// @param MI DBG_VALUE instruction
320 /// @param Idx Last valid SLotIndex before instruction.
321 /// @return True if the DBG_VALUE instruction should be deleted.
322 bool handleDebugValue(MachineInstr *MI, SlotIndex Idx);
323
324 /// collectDebugValues - Collect and erase all DBG_VALUE instructions, adding
325 /// a UserValue def for each instruction.
326 /// @param mf MachineFunction to be scanned.
327 /// @return True if any debug values were found.
328 bool collectDebugValues(MachineFunction &mf);
329
330 /// computeIntervals - Compute the live intervals of all user values after
331 /// collecting all their def points.
332 void computeIntervals();
333
334public:
Stephen Hinesc6a4f5e2014-07-21 00:45:20 -0700335 LDVImpl(LiveDebugVariables *ps)
336 : pass(*ps), MF(nullptr), EmitDone(false), ModifiedMF(false) {}
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000337 bool runOnMachineFunction(MachineFunction &mf);
338
Manman Renf0986202013-02-13 20:23:48 +0000339 /// clear - Release all memory.
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000340 void clear() {
Stephen Hinesc6a4f5e2014-07-21 00:45:20 -0700341 MF = nullptr;
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000342 userValues.clear();
Jakob Stoklund Olesen6ed4c6a2010-12-03 22:25:09 +0000343 virtRegToEqClass.clear();
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000344 userVarMap.clear();
Manman Renf0986202013-02-13 20:23:48 +0000345 // Make sure we call emitDebugValues if the machine function was modified.
346 assert((!ModifiedMF || EmitDone) &&
347 "Dbg values are not emitted in LDV");
348 EmitDone = false;
349 ModifiedMF = false;
Stephen Hines37ed9c12014-12-01 14:51:49 -0800350 LS.reset();
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000351 }
352
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000353 /// mapVirtReg - Map virtual register to an equivalence class.
354 void mapVirtReg(unsigned VirtReg, UserValue *EC);
355
Jakob Stoklund Olesenf42b6612011-05-06 18:00:02 +0000356 /// splitRegister - Replace all references to OldReg with NewRegs.
Mark Lacey1feb5852013-08-14 23:50:04 +0000357 void splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs);
Jakob Stoklund Olesenf42b6612011-05-06 18:00:02 +0000358
Eric Christopherb3cecdf2013-02-13 02:29:18 +0000359 /// emitDebugValues - Recreate DBG_VALUE instruction from data structures.
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +0000360 void emitDebugValues(VirtRegMap *VRM);
361
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000362 void print(raw_ostream&);
363};
364} // namespace
365
Jakob Stoklund Olesene77150b2011-05-06 17:59:59 +0000366void UserValue::print(raw_ostream &OS, const TargetMachine *TM) {
Stephen Hines37ed9c12014-12-01 14:51:49 -0800367 DIVariable DV(Variable);
368 OS << "!\"";
Devang Patela2b552d2011-08-09 01:03:35 +0000369 DV.printExtendedName(OS);
370 OS << "\"\t";
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000371 if (offset)
372 OS << '+' << offset;
373 for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I) {
374 OS << " [" << I.start() << ';' << I.stop() << "):";
375 if (I.value() == ~0u)
376 OS << "undef";
377 else
378 OS << I.value();
379 }
Jakob Stoklund Olesene77150b2011-05-06 17:59:59 +0000380 for (unsigned i = 0, e = locations.size(); i != e; ++i) {
381 OS << " Loc" << i << '=';
382 locations[i].print(OS, TM);
383 }
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000384 OS << '\n';
385}
386
387void LDVImpl::print(raw_ostream &OS) {
388 OS << "********** DEBUG VARIABLES **********\n";
389 for (unsigned i = 0, e = userValues.size(); i != e; ++i)
Jakob Stoklund Olesene77150b2011-05-06 17:59:59 +0000390 userValues[i]->print(OS, &MF->getTarget());
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000391}
392
Jakob Stoklund Olesen5daec222010-12-03 22:25:07 +0000393void UserValue::coalesceLocation(unsigned LocNo) {
Jakob Stoklund Olesen0804ead2011-01-09 05:33:21 +0000394 unsigned KeepLoc = 0;
395 for (unsigned e = locations.size(); KeepLoc != e; ++KeepLoc) {
396 if (KeepLoc == LocNo)
397 continue;
398 if (locations[KeepLoc].isIdenticalTo(locations[LocNo]))
399 break;
Jakob Stoklund Olesen5daec222010-12-03 22:25:07 +0000400 }
Jakob Stoklund Olesen0804ead2011-01-09 05:33:21 +0000401 // No matches.
402 if (KeepLoc == locations.size())
403 return;
404
405 // Keep the smaller location, erase the larger one.
406 unsigned EraseLoc = LocNo;
407 if (KeepLoc > EraseLoc)
408 std::swap(KeepLoc, EraseLoc);
Jakob Stoklund Olesen5daec222010-12-03 22:25:07 +0000409 locations.erase(locations.begin() + EraseLoc);
410
411 // Rewrite values.
412 for (LocMap::iterator I = locInts.begin(); I.valid(); ++I) {
413 unsigned v = I.value();
414 if (v == EraseLoc)
415 I.setValue(KeepLoc); // Coalesce when possible.
416 else if (v > EraseLoc)
417 I.setValueUnchecked(v-1); // Avoid coalescing with untransformed values.
418 }
419}
420
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000421void UserValue::mapVirtRegs(LDVImpl *LDV) {
422 for (unsigned i = 0, e = locations.size(); i != e; ++i)
423 if (locations[i].isReg() &&
424 TargetRegisterInfo::isVirtualRegister(locations[i].getReg()))
425 LDV->mapVirtReg(locations[i].getReg(), this);
426}
427
Stephen Hines37ed9c12014-12-01 14:51:49 -0800428UserValue *LDVImpl::getUserValue(const MDNode *Var, const MDNode *Expr,
429 unsigned Offset, bool IsIndirect,
430 DebugLoc DL) {
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000431 UserValue *&Leader = userVarMap[Var];
432 if (Leader) {
433 UserValue *UV = Leader->getLeader();
434 Leader = UV;
435 for (; UV; UV = UV->getNext())
Stephen Hines37ed9c12014-12-01 14:51:49 -0800436 if (UV->match(Var, Expr, Offset, IsIndirect))
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000437 return UV;
438 }
439
Stephen Hinesdce4a402014-05-29 02:49:00 -0700440 userValues.push_back(
Stephen Hines37ed9c12014-12-01 14:51:49 -0800441 make_unique<UserValue>(Var, Expr, Offset, IsIndirect, DL, allocator));
Stephen Hinesdce4a402014-05-29 02:49:00 -0700442 UserValue *UV = userValues.back().get();
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000443 Leader = UserValue::merge(Leader, UV);
444 return UV;
445}
446
447void LDVImpl::mapVirtReg(unsigned VirtReg, UserValue *EC) {
448 assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && "Only map VirtRegs");
Jakob Stoklund Olesen6ed4c6a2010-12-03 22:25:09 +0000449 UserValue *&Leader = virtRegToEqClass[VirtReg];
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000450 Leader = UserValue::merge(Leader, EC);
451}
452
Jakob Stoklund Olesen30e21282010-12-02 18:15:44 +0000453UserValue *LDVImpl::lookupVirtReg(unsigned VirtReg) {
Jakob Stoklund Olesen6ed4c6a2010-12-03 22:25:09 +0000454 if (UserValue *UV = virtRegToEqClass.lookup(VirtReg))
Jakob Stoklund Olesen30e21282010-12-02 18:15:44 +0000455 return UV->getLeader();
Stephen Hinesdce4a402014-05-29 02:49:00 -0700456 return nullptr;
Jakob Stoklund Olesen30e21282010-12-02 18:15:44 +0000457}
458
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000459bool LDVImpl::handleDebugValue(MachineInstr *MI, SlotIndex Idx) {
460 // DBG_VALUE loc, offset, variable
Stephen Hines37ed9c12014-12-01 14:51:49 -0800461 if (MI->getNumOperands() != 4 ||
Adrian Prantl35176402013-07-09 20:28:37 +0000462 !(MI->getOperand(1).isReg() || MI->getOperand(1).isImm()) ||
463 !MI->getOperand(2).isMetadata()) {
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000464 DEBUG(dbgs() << "Can't handle " << *MI);
465 return false;
466 }
467
468 // Get or create the UserValue for (variable,offset).
Adrian Prantl818833f2013-09-16 23:29:03 +0000469 bool IsIndirect = MI->isIndirectDebugValue();
Adrian Prantl35176402013-07-09 20:28:37 +0000470 unsigned Offset = IsIndirect ? MI->getOperand(1).getImm() : 0;
Stephen Hines37ed9c12014-12-01 14:51:49 -0800471 const MDNode *Var = MI->getDebugVariable();
472 const MDNode *Expr = MI->getDebugExpression();
Adrian Prantl818833f2013-09-16 23:29:03 +0000473 //here.
Stephen Hines37ed9c12014-12-01 14:51:49 -0800474 UserValue *UV =
475 getUserValue(Var, Expr, Offset, IsIndirect, MI->getDebugLoc());
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000476 UV->addDef(Idx, MI->getOperand(0));
477 return true;
478}
479
480bool LDVImpl::collectDebugValues(MachineFunction &mf) {
481 bool Changed = false;
482 for (MachineFunction::iterator MFI = mf.begin(), MFE = mf.end(); MFI != MFE;
483 ++MFI) {
484 MachineBasicBlock *MBB = MFI;
485 for (MachineBasicBlock::iterator MBBI = MBB->begin(), MBBE = MBB->end();
486 MBBI != MBBE;) {
487 if (!MBBI->isDebugValue()) {
488 ++MBBI;
489 continue;
490 }
491 // DBG_VALUE has no slot index, use the previous instruction instead.
492 SlotIndex Idx = MBBI == MBB->begin() ?
493 LIS->getMBBStartIdx(MBB) :
Stephen Hines36b56882014-04-23 16:57:46 -0700494 LIS->getInstructionIndex(std::prev(MBBI)).getRegSlot();
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000495 // Handle consecutive DBG_VALUE instructions with the same slot index.
496 do {
497 if (handleDebugValue(MBBI, Idx)) {
498 MBBI = MBB->erase(MBBI);
499 Changed = true;
500 } else
501 ++MBBI;
502 } while (MBBI != MBBE && MBBI->isDebugValue());
503 }
504 }
505 return Changed;
506}
507
508void UserValue::extendDef(SlotIndex Idx, unsigned LocNo,
Matthias Braun4f3b5e82013-10-10 21:29:02 +0000509 LiveRange *LR, const VNInfo *VNI,
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000510 SmallVectorImpl<SlotIndex> *Kills,
Devang Patelc722c3d2011-08-10 21:25:34 +0000511 LiveIntervals &LIS, MachineDominatorTree &MDT,
Eric Christopherb82062f2012-03-15 21:33:39 +0000512 UserValueScopes &UVS) {
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000513 SmallVector<SlotIndex, 16> Todo;
514 Todo.push_back(Idx);
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000515 do {
516 SlotIndex Start = Todo.pop_back_val();
517 MachineBasicBlock *MBB = LIS.getMBBFromIndex(Start);
518 SlotIndex Stop = LIS.getMBBEndIdx(MBB);
Jakob Stoklund Olesen12a40312011-01-12 23:14:04 +0000519 LocMap::iterator I = locInts.find(Start);
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000520
521 // Limit to VNI's live range.
522 bool ToEnd = true;
Matthias Braun4f3b5e82013-10-10 21:29:02 +0000523 if (LR && VNI) {
524 LiveInterval::Segment *Segment = LR->getSegmentContaining(Start);
Matthias Braun331de112013-10-10 21:28:43 +0000525 if (!Segment || Segment->valno != VNI) {
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000526 if (Kills)
527 Kills->push_back(Start);
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000528 continue;
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000529 }
Matthias Braun331de112013-10-10 21:28:43 +0000530 if (Segment->end < Stop)
531 Stop = Segment->end, ToEnd = false;
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000532 }
533
534 // There could already be a short def at Start.
535 if (I.valid() && I.start() <= Start) {
536 // Stop when meeting a different location or an already extended interval.
537 Start = Start.getNextSlot();
538 if (I.value() != LocNo || I.stop() != Start)
539 continue;
540 // This is a one-slot placeholder. Just skip it.
541 ++I;
542 }
543
544 // Limited by the next def.
545 if (I.valid() && I.start() < Stop)
546 Stop = I.start(), ToEnd = false;
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000547 // Limited by VNI's live range.
548 else if (!ToEnd && Kills)
549 Kills->push_back(Stop);
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000550
551 if (Start >= Stop)
552 continue;
553
554 I.insert(Start, Stop, LocNo);
555
556 // If we extended to the MBB end, propagate down the dominator tree.
557 if (!ToEnd)
558 continue;
559 const std::vector<MachineDomTreeNode*> &Children =
560 MDT.getNode(MBB)->getChildren();
Devang Patelc722c3d2011-08-10 21:25:34 +0000561 for (unsigned i = 0, e = Children.size(); i != e; ++i) {
562 MachineBasicBlock *MBB = Children[i]->getBlock();
Devang Patel3a2d80d2011-09-13 18:40:53 +0000563 if (UVS.dominates(MBB))
Devang Patelc722c3d2011-08-10 21:25:34 +0000564 Todo.push_back(LIS.getMBBStartIdx(MBB));
565 }
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000566 } while (!Todo.empty());
567}
568
569void
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000570UserValue::addDefsFromCopies(LiveInterval *LI, unsigned LocNo,
571 const SmallVectorImpl<SlotIndex> &Kills,
572 SmallVectorImpl<std::pair<SlotIndex, unsigned> > &NewDefs,
573 MachineRegisterInfo &MRI, LiveIntervals &LIS) {
574 if (Kills.empty())
575 return;
576 // Don't track copies from physregs, there are too many uses.
577 if (!TargetRegisterInfo::isVirtualRegister(LI->reg))
578 return;
579
580 // Collect all the (vreg, valno) pairs that are copies of LI.
581 SmallVector<std::pair<LiveInterval*, const VNInfo*>, 8> CopyValues;
Stephen Hines36b56882014-04-23 16:57:46 -0700582 for (MachineOperand &MO : MRI.use_nodbg_operands(LI->reg)) {
583 MachineInstr *MI = MO.getParent();
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000584 // Copies of the full value.
Stephen Hines36b56882014-04-23 16:57:46 -0700585 if (MO.getSubReg() || !MI->isCopy())
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000586 continue;
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000587 unsigned DstReg = MI->getOperand(0).getReg();
588
Jakob Stoklund Olesen28cf1152011-03-22 22:33:08 +0000589 // Don't follow copies to physregs. These are usually setting up call
590 // arguments, and the argument registers are always call clobbered. We are
591 // better off in the source register which could be a callee-saved register,
592 // or it could be spilled.
593 if (!TargetRegisterInfo::isVirtualRegister(DstReg))
594 continue;
595
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000596 // Is LocNo extended to reach this copy? If not, another def may be blocking
597 // it, or we are looking at a wrong value of LI.
598 SlotIndex Idx = LIS.getInstructionIndex(MI);
Jakob Stoklund Olesen2debd482011-11-13 20:45:27 +0000599 LocMap::iterator I = locInts.find(Idx.getRegSlot(true));
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000600 if (!I.valid() || I.value() != LocNo)
601 continue;
602
603 if (!LIS.hasInterval(DstReg))
604 continue;
605 LiveInterval *DstLI = &LIS.getInterval(DstReg);
Jakob Stoklund Olesen2debd482011-11-13 20:45:27 +0000606 const VNInfo *DstVNI = DstLI->getVNInfoAt(Idx.getRegSlot());
607 assert(DstVNI && DstVNI->def == Idx.getRegSlot() && "Bad copy value");
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000608 CopyValues.push_back(std::make_pair(DstLI, DstVNI));
609 }
610
611 if (CopyValues.empty())
612 return;
613
614 DEBUG(dbgs() << "Got " << CopyValues.size() << " copies of " << *LI << '\n');
615
616 // Try to add defs of the copied values for each kill point.
617 for (unsigned i = 0, e = Kills.size(); i != e; ++i) {
618 SlotIndex Idx = Kills[i];
619 for (unsigned j = 0, e = CopyValues.size(); j != e; ++j) {
620 LiveInterval *DstLI = CopyValues[j].first;
621 const VNInfo *DstVNI = CopyValues[j].second;
622 if (DstLI->getVNInfoAt(Idx) != DstVNI)
623 continue;
624 // Check that there isn't already a def at Idx
625 LocMap::iterator I = locInts.find(Idx);
626 if (I.valid() && I.start() <= Idx)
627 continue;
628 DEBUG(dbgs() << "Kill at " << Idx << " covered by valno #"
629 << DstVNI->id << " in " << *DstLI << '\n');
630 MachineInstr *CopyMI = LIS.getInstructionFromIndex(DstVNI->def);
631 assert(CopyMI && CopyMI->isCopy() && "Bad copy value");
632 unsigned LocNo = getLocationNo(CopyMI->getOperand(0));
633 I.insert(Idx, Idx.getNextSlot(), LocNo);
634 NewDefs.push_back(std::make_pair(Idx, LocNo));
635 break;
636 }
637 }
638}
639
640void
641UserValue::computeIntervals(MachineRegisterInfo &MRI,
Jakob Stoklund Olesene8a0a122012-06-22 17:15:32 +0000642 const TargetRegisterInfo &TRI,
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000643 LiveIntervals &LIS,
Devang Patelc722c3d2011-08-10 21:25:34 +0000644 MachineDominatorTree &MDT,
Eric Christopherb82062f2012-03-15 21:33:39 +0000645 UserValueScopes &UVS) {
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000646 SmallVector<std::pair<SlotIndex, unsigned>, 16> Defs;
647
648 // Collect all defs to be extended (Skipping undefs).
649 for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I)
650 if (I.value() != ~0u)
651 Defs.push_back(std::make_pair(I.start(), I.value()));
652
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000653 // Extend all defs, and possibly add new ones along the way.
654 for (unsigned i = 0; i != Defs.size(); ++i) {
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000655 SlotIndex Idx = Defs[i].first;
656 unsigned LocNo = Defs[i].second;
Jakob Stoklund Olesen0804ead2011-01-09 05:33:21 +0000657 const MachineOperand &Loc = locations[LocNo];
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000658
Jakob Stoklund Olesene8a0a122012-06-22 17:15:32 +0000659 if (!Loc.isReg()) {
Stephen Hinesdce4a402014-05-29 02:49:00 -0700660 extendDef(Idx, LocNo, nullptr, nullptr, nullptr, LIS, MDT, UVS);
Jakob Stoklund Olesene8a0a122012-06-22 17:15:32 +0000661 continue;
662 }
663
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000664 // Register locations are constrained to where the register value is live.
Jakob Stoklund Olesene8a0a122012-06-22 17:15:32 +0000665 if (TargetRegisterInfo::isVirtualRegister(Loc.getReg())) {
Stephen Hinesdce4a402014-05-29 02:49:00 -0700666 LiveInterval *LI = nullptr;
667 const VNInfo *VNI = nullptr;
Jakob Stoklund Olesenb1509302012-06-22 18:51:35 +0000668 if (LIS.hasInterval(Loc.getReg())) {
669 LI = &LIS.getInterval(Loc.getReg());
670 VNI = LI->getVNInfoAt(Idx);
671 }
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000672 SmallVector<SlotIndex, 16> Kills;
Devang Patel3a2d80d2011-09-13 18:40:53 +0000673 extendDef(Idx, LocNo, LI, VNI, &Kills, LIS, MDT, UVS);
Jakob Stoklund Olesenb1509302012-06-22 18:51:35 +0000674 if (LI)
675 addDefsFromCopies(LI, LocNo, Kills, Defs, MRI, LIS);
Jakob Stoklund Olesene8a0a122012-06-22 17:15:32 +0000676 continue;
677 }
678
679 // For physregs, use the live range of the first regunit as a guide.
680 unsigned Unit = *MCRegUnitIterator(Loc.getReg(), &TRI);
Matthias Braun4f3b5e82013-10-10 21:29:02 +0000681 LiveRange *LR = &LIS.getRegUnit(Unit);
682 const VNInfo *VNI = LR->getVNInfoAt(Idx);
Jakob Stoklund Olesene8a0a122012-06-22 17:15:32 +0000683 // Don't track copies from physregs, it is too expensive.
Stephen Hinesdce4a402014-05-29 02:49:00 -0700684 extendDef(Idx, LocNo, LR, VNI, nullptr, LIS, MDT, UVS);
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000685 }
686
687 // Finally, erase all the undefs.
688 for (LocMap::iterator I = locInts.begin(); I.valid();)
689 if (I.value() == ~0u)
690 I.erase();
691 else
692 ++I;
693}
694
695void LDVImpl::computeIntervals() {
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000696 for (unsigned i = 0, e = userValues.size(); i != e; ++i) {
Devang Patel3a2d80d2011-09-13 18:40:53 +0000697 UserValueScopes UVS(userValues[i]->getDebugLoc(), LS);
Jakob Stoklund Olesene8a0a122012-06-22 17:15:32 +0000698 userValues[i]->computeIntervals(MF->getRegInfo(), *TRI, *LIS, *MDT, UVS);
Jakob Stoklund Olesen1744e472011-03-18 21:42:19 +0000699 userValues[i]->mapVirtRegs(this);
700 }
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000701}
702
703bool LDVImpl::runOnMachineFunction(MachineFunction &mf) {
Stephen Hinesc6a4f5e2014-07-21 00:45:20 -0700704 clear();
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000705 MF = &mf;
706 LIS = &pass.getAnalysis<LiveIntervals>();
707 MDT = &pass.getAnalysis<MachineDominatorTree>();
Stephen Hines37ed9c12014-12-01 14:51:49 -0800708 TRI = mf.getSubtarget().getRegisterInfo();
Devang Patelc722c3d2011-08-10 21:25:34 +0000709 LS.initialize(mf);
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000710 DEBUG(dbgs() << "********** COMPUTING LIVE DEBUG VARIABLES: "
David Blaikie986d76d2012-08-22 17:18:53 +0000711 << mf.getName() << " **********\n");
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000712
713 bool Changed = collectDebugValues(mf);
714 computeIntervals();
715 DEBUG(print(dbgs()));
Manman Renf0986202013-02-13 20:23:48 +0000716 ModifiedMF = Changed;
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000717 return Changed;
718}
719
Stephen Hines37ed9c12014-12-01 14:51:49 -0800720static void removeDebugValues(MachineFunction &mf) {
721 for (MachineBasicBlock &MBB : mf) {
722 for (auto MBBI = MBB.begin(), MBBE = MBB.end(); MBBI != MBBE; ) {
723 if (!MBBI->isDebugValue()) {
724 ++MBBI;
725 continue;
726 }
727 MBBI = MBB.erase(MBBI);
728 }
729 }
730}
731
Jakob Stoklund Olesenbb7b23f2010-11-30 02:17:10 +0000732bool LiveDebugVariables::runOnMachineFunction(MachineFunction &mf) {
Devang Patel51a666f2011-01-07 22:33:41 +0000733 if (!EnableLDV)
734 return false;
Stephen Hines37ed9c12014-12-01 14:51:49 -0800735 if (!FunctionDIs.count(mf.getFunction())) {
736 removeDebugValues(mf);
Stephen Hinesc6a4f5e2014-07-21 00:45:20 -0700737 return false;
Stephen Hines37ed9c12014-12-01 14:51:49 -0800738 }
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000739 if (!pImpl)
740 pImpl = new LDVImpl(this);
Manman Renf0986202013-02-13 20:23:48 +0000741 return static_cast<LDVImpl*>(pImpl)->runOnMachineFunction(mf);
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000742}
743
744void LiveDebugVariables::releaseMemory() {
Manman Renf0986202013-02-13 20:23:48 +0000745 if (pImpl)
Jakob Stoklund Olesen06135162010-12-02 00:37:37 +0000746 static_cast<LDVImpl*>(pImpl)->clear();
747}
748
749LiveDebugVariables::~LiveDebugVariables() {
750 if (pImpl)
751 delete static_cast<LDVImpl*>(pImpl);
Jakob Stoklund Olesenbb7b23f2010-11-30 02:17:10 +0000752}
Jakob Stoklund Olesen30e21282010-12-02 18:15:44 +0000753
Jakob Stoklund Olesenf42b6612011-05-06 18:00:02 +0000754//===----------------------------------------------------------------------===//
755// Live Range Splitting
756//===----------------------------------------------------------------------===//
757
758bool
Mark Lacey1feb5852013-08-14 23:50:04 +0000759UserValue::splitLocation(unsigned OldLocNo, ArrayRef<unsigned> NewRegs,
760 LiveIntervals& LIS) {
Jakob Stoklund Olesenf42b6612011-05-06 18:00:02 +0000761 DEBUG({
762 dbgs() << "Splitting Loc" << OldLocNo << '\t';
Stephen Hinesdce4a402014-05-29 02:49:00 -0700763 print(dbgs(), nullptr);
Jakob Stoklund Olesenf42b6612011-05-06 18:00:02 +0000764 });
765 bool DidChange = false;
766 LocMap::iterator LocMapI;
767 LocMapI.setMap(locInts);
768 for (unsigned i = 0; i != NewRegs.size(); ++i) {
Mark Lacey1feb5852013-08-14 23:50:04 +0000769 LiveInterval *LI = &LIS.getInterval(NewRegs[i]);
Jakob Stoklund Olesenf42b6612011-05-06 18:00:02 +0000770 if (LI->empty())
771 continue;
772
773 // Don't allocate the new LocNo until it is needed.
774 unsigned NewLocNo = ~0u;
775
776 // Iterate over the overlaps between locInts and LI.
777 LocMapI.find(LI->beginIndex());
778 if (!LocMapI.valid())
779 continue;
780 LiveInterval::iterator LII = LI->advanceTo(LI->begin(), LocMapI.start());
781 LiveInterval::iterator LIE = LI->end();
782 while (LocMapI.valid() && LII != LIE) {
783 // At this point, we know that LocMapI.stop() > LII->start.
784 LII = LI->advanceTo(LII, LocMapI.start());
785 if (LII == LIE)
786 break;
787
788 // Now LII->end > LocMapI.start(). Do we have an overlap?
789 if (LocMapI.value() == OldLocNo && LII->start < LocMapI.stop()) {
790 // Overlapping correct location. Allocate NewLocNo now.
791 if (NewLocNo == ~0u) {
792 MachineOperand MO = MachineOperand::CreateReg(LI->reg, false);
793 MO.setSubReg(locations[OldLocNo].getSubReg());
794 NewLocNo = getLocationNo(MO);
795 DidChange = true;
796 }
797
798 SlotIndex LStart = LocMapI.start();
799 SlotIndex LStop = LocMapI.stop();
800
801 // Trim LocMapI down to the LII overlap.
802 if (LStart < LII->start)
803 LocMapI.setStartUnchecked(LII->start);
804 if (LStop > LII->end)
805 LocMapI.setStopUnchecked(LII->end);
806
807 // Change the value in the overlap. This may trigger coalescing.
808 LocMapI.setValue(NewLocNo);
809
810 // Re-insert any removed OldLocNo ranges.
811 if (LStart < LocMapI.start()) {
812 LocMapI.insert(LStart, LocMapI.start(), OldLocNo);
813 ++LocMapI;
814 assert(LocMapI.valid() && "Unexpected coalescing");
815 }
816 if (LStop > LocMapI.stop()) {
817 ++LocMapI;
818 LocMapI.insert(LII->end, LStop, OldLocNo);
819 --LocMapI;
820 }
821 }
822
823 // Advance to the next overlap.
824 if (LII->end < LocMapI.stop()) {
825 if (++LII == LIE)
826 break;
827 LocMapI.advanceTo(LII->start);
828 } else {
829 ++LocMapI;
830 if (!LocMapI.valid())
831 break;
832 LII = LI->advanceTo(LII, LocMapI.start());
833 }
834 }
835 }
836
837 // Finally, remove any remaining OldLocNo intervals and OldLocNo itself.
838 locations.erase(locations.begin() + OldLocNo);
839 LocMapI.goToBegin();
840 while (LocMapI.valid()) {
841 unsigned v = LocMapI.value();
842 if (v == OldLocNo) {
843 DEBUG(dbgs() << "Erasing [" << LocMapI.start() << ';'
844 << LocMapI.stop() << ")\n");
845 LocMapI.erase();
846 } else {
847 if (v > OldLocNo)
848 LocMapI.setValueUnchecked(v-1);
849 ++LocMapI;
850 }
851 }
852
Stephen Hinesdce4a402014-05-29 02:49:00 -0700853 DEBUG({dbgs() << "Split result: \t"; print(dbgs(), nullptr);});
Jakob Stoklund Olesenf42b6612011-05-06 18:00:02 +0000854 return DidChange;
855}
856
857bool
Mark Lacey1feb5852013-08-14 23:50:04 +0000858UserValue::splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs,
859 LiveIntervals &LIS) {
Jakob Stoklund Olesenf42b6612011-05-06 18:00:02 +0000860 bool DidChange = false;
Jakob Stoklund Olesen6212f9a2011-05-06 19:31:19 +0000861 // Split locations referring to OldReg. Iterate backwards so splitLocation can
Eric Christopher7cc51772012-03-15 21:33:35 +0000862 // safely erase unused locations.
Jakob Stoklund Olesen6212f9a2011-05-06 19:31:19 +0000863 for (unsigned i = locations.size(); i ; --i) {
864 unsigned LocNo = i-1;
Jakob Stoklund Olesenf42b6612011-05-06 18:00:02 +0000865 const MachineOperand *Loc = &locations[LocNo];
866 if (!Loc->isReg() || Loc->getReg() != OldReg)
867 continue;
Mark Lacey1feb5852013-08-14 23:50:04 +0000868 DidChange |= splitLocation(LocNo, NewRegs, LIS);
Jakob Stoklund Olesenf42b6612011-05-06 18:00:02 +0000869 }
870 return DidChange;
871}
872
Mark Lacey1feb5852013-08-14 23:50:04 +0000873void LDVImpl::splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs) {
Jakob Stoklund Olesenf42b6612011-05-06 18:00:02 +0000874 bool DidChange = false;
875 for (UserValue *UV = lookupVirtReg(OldReg); UV; UV = UV->getNext())
Mark Lacey1feb5852013-08-14 23:50:04 +0000876 DidChange |= UV->splitRegister(OldReg, NewRegs, *LIS);
Jakob Stoklund Olesenf42b6612011-05-06 18:00:02 +0000877
878 if (!DidChange)
879 return;
880
881 // Map all of the new virtual registers.
882 UserValue *UV = lookupVirtReg(OldReg);
883 for (unsigned i = 0; i != NewRegs.size(); ++i)
Mark Lacey1feb5852013-08-14 23:50:04 +0000884 mapVirtReg(NewRegs[i], UV);
Jakob Stoklund Olesenf42b6612011-05-06 18:00:02 +0000885}
886
887void LiveDebugVariables::
Mark Lacey1feb5852013-08-14 23:50:04 +0000888splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs, LiveIntervals &LIS) {
Jakob Stoklund Olesenf42b6612011-05-06 18:00:02 +0000889 if (pImpl)
890 static_cast<LDVImpl*>(pImpl)->splitRegister(OldReg, NewRegs);
891}
892
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +0000893void
894UserValue::rewriteLocations(VirtRegMap &VRM, const TargetRegisterInfo &TRI) {
895 // Iterate over locations in reverse makes it easier to handle coalescing.
896 for (unsigned i = locations.size(); i ; --i) {
897 unsigned LocNo = i-1;
Jakob Stoklund Olesen0804ead2011-01-09 05:33:21 +0000898 MachineOperand &Loc = locations[LocNo];
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +0000899 // Only virtual registers are rewritten.
Jakob Stoklund Olesen0804ead2011-01-09 05:33:21 +0000900 if (!Loc.isReg() || !Loc.getReg() ||
901 !TargetRegisterInfo::isVirtualRegister(Loc.getReg()))
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +0000902 continue;
Jakob Stoklund Olesen0804ead2011-01-09 05:33:21 +0000903 unsigned VirtReg = Loc.getReg();
Jakob Stoklund Olesenf2036272011-01-12 22:37:49 +0000904 if (VRM.isAssignedReg(VirtReg) &&
905 TargetRegisterInfo::isPhysicalRegister(VRM.getPhys(VirtReg))) {
Jakob Stoklund Olesencf724f02011-05-08 19:21:08 +0000906 // This can create a %noreg operand in rare cases when the sub-register
907 // index is no longer available. That means the user value is in a
908 // non-existent sub-register, and %noreg is exactly what we want.
Jakob Stoklund Olesen0804ead2011-01-09 05:33:21 +0000909 Loc.substPhysReg(VRM.getPhys(VirtReg), TRI);
Jakob Stoklund Olesencb390642011-11-13 01:23:30 +0000910 } else if (VRM.getStackSlot(VirtReg) != VirtRegMap::NO_STACK_SLOT) {
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +0000911 // FIXME: Translate SubIdx to a stackslot offset.
Jakob Stoklund Olesen0804ead2011-01-09 05:33:21 +0000912 Loc = MachineOperand::CreateFI(VRM.getStackSlot(VirtReg));
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +0000913 } else {
Jakob Stoklund Olesen0804ead2011-01-09 05:33:21 +0000914 Loc.setReg(0);
915 Loc.setSubReg(0);
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +0000916 }
Jakob Stoklund Olesen5daec222010-12-03 22:25:07 +0000917 coalesceLocation(LocNo);
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +0000918 }
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +0000919}
920
Devang Patelf827cd72011-02-04 01:43:25 +0000921/// findInsertLocation - Find an iterator for inserting a DBG_VALUE
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +0000922/// instruction.
923static MachineBasicBlock::iterator
Devang Patelf827cd72011-02-04 01:43:25 +0000924findInsertLocation(MachineBasicBlock *MBB, SlotIndex Idx,
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +0000925 LiveIntervals &LIS) {
926 SlotIndex Start = LIS.getMBBStartIdx(MBB);
927 Idx = Idx.getBaseIndex();
928
929 // Try to find an insert location by going backwards from Idx.
930 MachineInstr *MI;
931 while (!(MI = LIS.getInstructionFromIndex(Idx))) {
932 // We've reached the beginning of MBB.
933 if (Idx == Start) {
934 MachineBasicBlock::iterator I = MBB->SkipPHIsAndLabels(MBB->begin());
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +0000935 return I;
936 }
937 Idx = Idx.getPrevIndex();
938 }
Devang Patelf827cd72011-02-04 01:43:25 +0000939
Jakob Stoklund Oleseneea666f2011-01-13 23:35:53 +0000940 // Don't insert anything after the first terminator, though.
Evan Cheng5a96b3d2011-12-07 07:15:52 +0000941 return MI->isTerminator() ? MBB->getFirstTerminator() :
Stephen Hines36b56882014-04-23 16:57:46 -0700942 std::next(MachineBasicBlock::iterator(MI));
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +0000943}
944
Devang Patelf827cd72011-02-04 01:43:25 +0000945DebugLoc UserValue::findDebugLoc() {
946 DebugLoc D = dl;
947 dl = DebugLoc();
948 return D;
949}
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +0000950void UserValue::insertDebugValue(MachineBasicBlock *MBB, SlotIndex Idx,
951 unsigned LocNo,
952 LiveIntervals &LIS,
953 const TargetInstrInfo &TII) {
Devang Patelf827cd72011-02-04 01:43:25 +0000954 MachineBasicBlock::iterator I = findInsertLocation(MBB, Idx, LIS);
Jakob Stoklund Olesen0804ead2011-01-09 05:33:21 +0000955 MachineOperand &Loc = locations[LocNo];
Devang Pateld9f3fc72011-08-04 20:42:11 +0000956 ++NumInsertedDebugValues;
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +0000957
Adrian Prantl35176402013-07-09 20:28:37 +0000958 if (Loc.isReg())
959 BuildMI(*MBB, I, findDebugLoc(), TII.get(TargetOpcode::DBG_VALUE),
Stephen Hines37ed9c12014-12-01 14:51:49 -0800960 IsIndirect, Loc.getReg(), offset, Variable, Expression);
Adrian Prantl35176402013-07-09 20:28:37 +0000961 else
962 BuildMI(*MBB, I, findDebugLoc(), TII.get(TargetOpcode::DBG_VALUE))
Stephen Hines37ed9c12014-12-01 14:51:49 -0800963 .addOperand(Loc)
964 .addImm(offset)
965 .addMetadata(Variable)
966 .addMetadata(Expression);
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +0000967}
968
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +0000969void UserValue::emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS,
970 const TargetInstrInfo &TII) {
971 MachineFunction::iterator MFEnd = VRM->getMachineFunction().end();
972
973 for (LocMap::const_iterator I = locInts.begin(); I.valid();) {
974 SlotIndex Start = I.start();
975 SlotIndex Stop = I.stop();
976 unsigned LocNo = I.value();
977 DEBUG(dbgs() << "\t[" << Start << ';' << Stop << "):" << LocNo);
978 MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start);
979 SlotIndex MBBEnd = LIS.getMBBEndIdx(MBB);
980
981 DEBUG(dbgs() << " BB#" << MBB->getNumber() << '-' << MBBEnd);
982 insertDebugValue(MBB, Start, LocNo, LIS, TII);
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +0000983 // This interval may span multiple basic blocks.
984 // Insert a DBG_VALUE into each one.
985 while(Stop > MBBEnd) {
986 // Move to the next block.
987 Start = MBBEnd;
988 if (++MBB == MFEnd)
989 break;
990 MBBEnd = LIS.getMBBEndIdx(MBB);
991 DEBUG(dbgs() << " BB#" << MBB->getNumber() << '-' << MBBEnd);
992 insertDebugValue(MBB, Start, LocNo, LIS, TII);
993 }
994 DEBUG(dbgs() << '\n');
995 if (MBB == MFEnd)
996 break;
997
998 ++I;
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +0000999 }
1000}
1001
1002void LDVImpl::emitDebugValues(VirtRegMap *VRM) {
1003 DEBUG(dbgs() << "********** EMITTING LIVE DEBUG VARIABLES **********\n");
Stephen Hinesc6a4f5e2014-07-21 00:45:20 -07001004 if (!MF)
1005 return;
Stephen Hines37ed9c12014-12-01 14:51:49 -08001006 const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +00001007 for (unsigned i = 0, e = userValues.size(); i != e; ++i) {
Jakob Stoklund Olesencf724f02011-05-08 19:21:08 +00001008 DEBUG(userValues[i]->print(dbgs(), &MF->getTarget()));
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +00001009 userValues[i]->rewriteLocations(*VRM, *TRI);
1010 userValues[i]->emitDebugValues(VRM, *LIS, *TII);
1011 }
Manman Renf0986202013-02-13 20:23:48 +00001012 EmitDone = true;
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +00001013}
1014
1015void LiveDebugVariables::emitDebugValues(VirtRegMap *VRM) {
Manman Renf0986202013-02-13 20:23:48 +00001016 if (pImpl)
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +00001017 static_cast<LDVImpl*>(pImpl)->emitDebugValues(VRM);
1018}
1019
Stephen Hinesc6a4f5e2014-07-21 00:45:20 -07001020bool LiveDebugVariables::doInitialization(Module &M) {
1021 FunctionDIs = makeSubprogramMap(M);
1022 return Pass::doInitialization(M);
1023}
Jakob Stoklund Olesen42acf062010-12-03 21:47:10 +00001024
Jakob Stoklund Olesen30e21282010-12-02 18:15:44 +00001025#ifndef NDEBUG
1026void LiveDebugVariables::dump() {
1027 if (pImpl)
1028 static_cast<LDVImpl*>(pImpl)->print(dbgs());
1029}
1030#endif