1 //===- 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 #define DEBUG_TYPE "livedebug"
23 #include "LiveDebugVariables.h"
24 #include "VirtRegMap.h"
25 #include "llvm/Constants.h"
26 #include "llvm/Metadata.h"
27 #include "llvm/Value.h"
28 #include "llvm/Analysis/DebugInfo.h"
29 #include "llvm/ADT/IntervalMap.h"
30 #include "llvm/ADT/Statistic.h"
31 #include "llvm/CodeGen/LexicalScopes.h"
32 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
33 #include "llvm/CodeGen/MachineDominators.h"
34 #include "llvm/CodeGen/MachineFunction.h"
35 #include "llvm/CodeGen/MachineInstrBuilder.h"
36 #include "llvm/CodeGen/MachineRegisterInfo.h"
37 #include "llvm/CodeGen/Passes.h"
38 #include "llvm/Support/CommandLine.h"
39 #include "llvm/Support/Debug.h"
40 #include "llvm/Target/TargetInstrInfo.h"
41 #include "llvm/Target/TargetMachine.h"
42 #include "llvm/Target/TargetRegisterInfo.h"
43
44 using namespace llvm;
45
46 static cl::opt<bool>
47 EnableLDV("live-debug-variables", cl::init(true),
48 cl::desc("Enable the live debug variables pass"), cl::Hidden);
49
50 STATISTIC(NumInsertedDebugValues, "Number of DBG_VALUEs inserted");
51 char LiveDebugVariables::ID = 0;
52
53 INITIALIZE_PASS_BEGIN(LiveDebugVariables, "livedebugvars",
54 "Debug Variable Analysis", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)55 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
56 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
57 INITIALIZE_PASS_END(LiveDebugVariables, "livedebugvars",
58 "Debug Variable Analysis", false, false)
59
60 void LiveDebugVariables::getAnalysisUsage(AnalysisUsage &AU) const {
61 AU.addRequired<MachineDominatorTree>();
62 AU.addRequiredTransitive<LiveIntervals>();
63 AU.setPreservesAll();
64 MachineFunctionPass::getAnalysisUsage(AU);
65 }
66
LiveDebugVariables()67 LiveDebugVariables::LiveDebugVariables() : MachineFunctionPass(ID), pImpl(0) {
68 initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry());
69 }
70
71 /// LocMap - Map of where a user value is live, and its location.
72 typedef IntervalMap<SlotIndex, unsigned, 4> LocMap;
73
74 namespace {
75 /// UserValueScopes - Keeps track of lexical scopes associated with an
76 /// user value's source location.
77 class UserValueScopes {
78 DebugLoc DL;
79 LexicalScopes &LS;
80 SmallPtrSet<const MachineBasicBlock *, 4> LBlocks;
81
82 public:
UserValueScopes(DebugLoc D,LexicalScopes & L)83 UserValueScopes(DebugLoc D, LexicalScopes &L) : DL(D), LS(L) {}
84
85 /// dominates - Return true if current scope dominates at least one machine
86 /// instruction in a given machine basic block.
dominates(MachineBasicBlock * MBB)87 bool dominates(MachineBasicBlock *MBB) {
88 if (LBlocks.empty())
89 LS.getMachineBasicBlocks(DL, LBlocks);
90 if (LBlocks.count(MBB) != 0 || LS.dominates(DL, MBB))
91 return true;
92 return false;
93 }
94 };
95 } // end anonymous namespace
96
97 /// UserValue - A user value is a part of a debug info user variable.
98 ///
99 /// A DBG_VALUE instruction notes that (a sub-register of) a virtual register
100 /// holds part of a user variable. The part is identified by a byte offset.
101 ///
102 /// UserValues are grouped into equivalence classes for easier searching. Two
103 /// user values are related if they refer to the same variable, or if they are
104 /// held by the same virtual register. The equivalence class is the transitive
105 /// closure of that relation.
106 namespace {
107 class LDVImpl;
108 class UserValue {
109 const MDNode *variable; ///< The debug info variable we are part of.
110 unsigned offset; ///< Byte offset into variable.
111 DebugLoc dl; ///< The debug location for the variable. This is
112 ///< used by dwarf writer to find lexical scope.
113 UserValue *leader; ///< Equivalence class leader.
114 UserValue *next; ///< Next value in equivalence class, or null.
115
116 /// Numbered locations referenced by locmap.
117 SmallVector<MachineOperand, 4> locations;
118
119 /// Map of slot indices where this value is live.
120 LocMap locInts;
121
122 /// coalesceLocation - After LocNo was changed, check if it has become
123 /// identical to another location, and coalesce them. This may cause LocNo or
124 /// a later location to be erased, but no earlier location will be erased.
125 void coalesceLocation(unsigned LocNo);
126
127 /// insertDebugValue - Insert a DBG_VALUE into MBB at Idx for LocNo.
128 void insertDebugValue(MachineBasicBlock *MBB, SlotIndex Idx, unsigned LocNo,
129 LiveIntervals &LIS, const TargetInstrInfo &TII);
130
131 /// splitLocation - Replace OldLocNo ranges with NewRegs ranges where NewRegs
132 /// is live. Returns true if any changes were made.
133 bool splitLocation(unsigned OldLocNo, ArrayRef<LiveInterval*> NewRegs);
134
135 public:
136 /// UserValue - Create a new UserValue.
UserValue(const MDNode * var,unsigned o,DebugLoc L,LocMap::Allocator & alloc)137 UserValue(const MDNode *var, unsigned o, DebugLoc L,
138 LocMap::Allocator &alloc)
139 : variable(var), offset(o), dl(L), leader(this), next(0), locInts(alloc)
140 {}
141
142 /// getLeader - Get the leader of this value's equivalence class.
getLeader()143 UserValue *getLeader() {
144 UserValue *l = leader;
145 while (l != l->leader)
146 l = l->leader;
147 return leader = l;
148 }
149
150 /// getNext - Return the next UserValue in the equivalence class.
getNext() const151 UserValue *getNext() const { return next; }
152
153 /// match - Does this UserValue match the parameters?
match(const MDNode * Var,unsigned Offset) const154 bool match(const MDNode *Var, unsigned Offset) const {
155 return Var == variable && Offset == offset;
156 }
157
158 /// merge - Merge equivalence classes.
merge(UserValue * L1,UserValue * L2)159 static UserValue *merge(UserValue *L1, UserValue *L2) {
160 L2 = L2->getLeader();
161 if (!L1)
162 return L2;
163 L1 = L1->getLeader();
164 if (L1 == L2)
165 return L1;
166 // Splice L2 before L1's members.
167 UserValue *End = L2;
168 while (End->next)
169 End->leader = L1, End = End->next;
170 End->leader = L1;
171 End->next = L1->next;
172 L1->next = L2;
173 return L1;
174 }
175
176 /// getLocationNo - Return the location number that matches Loc.
getLocationNo(const MachineOperand & LocMO)177 unsigned getLocationNo(const MachineOperand &LocMO) {
178 if (LocMO.isReg()) {
179 if (LocMO.getReg() == 0)
180 return ~0u;
181 // For register locations we dont care about use/def and other flags.
182 for (unsigned i = 0, e = locations.size(); i != e; ++i)
183 if (locations[i].isReg() &&
184 locations[i].getReg() == LocMO.getReg() &&
185 locations[i].getSubReg() == LocMO.getSubReg())
186 return i;
187 } else
188 for (unsigned i = 0, e = locations.size(); i != e; ++i)
189 if (LocMO.isIdenticalTo(locations[i]))
190 return i;
191 locations.push_back(LocMO);
192 // We are storing a MachineOperand outside a MachineInstr.
193 locations.back().clearParent();
194 // Don't store def operands.
195 if (locations.back().isReg())
196 locations.back().setIsUse();
197 return locations.size() - 1;
198 }
199
200 /// mapVirtRegs - Ensure that all virtual register locations are mapped.
201 void mapVirtRegs(LDVImpl *LDV);
202
203 /// addDef - Add a definition point to this value.
addDef(SlotIndex Idx,const MachineOperand & LocMO)204 void addDef(SlotIndex Idx, const MachineOperand &LocMO) {
205 // Add a singular (Idx,Idx) -> Loc mapping.
206 LocMap::iterator I = locInts.find(Idx);
207 if (!I.valid() || I.start() != Idx)
208 I.insert(Idx, Idx.getNextSlot(), getLocationNo(LocMO));
209 else
210 // A later DBG_VALUE at the same SlotIndex overrides the old location.
211 I.setValue(getLocationNo(LocMO));
212 }
213
214 /// extendDef - Extend the current definition as far as possible down the
215 /// dominator tree. Stop when meeting an existing def or when leaving the live
216 /// range of VNI.
217 /// End points where VNI is no longer live are added to Kills.
218 /// @param Idx Starting point for the definition.
219 /// @param LocNo Location number to propagate.
220 /// @param LI Restrict liveness to where LI has the value VNI. May be null.
221 /// @param VNI When LI is not null, this is the value to restrict to.
222 /// @param Kills Append end points of VNI's live range to Kills.
223 /// @param LIS Live intervals analysis.
224 /// @param MDT Dominator tree.
225 void extendDef(SlotIndex Idx, unsigned LocNo,
226 LiveInterval *LI, const VNInfo *VNI,
227 SmallVectorImpl<SlotIndex> *Kills,
228 LiveIntervals &LIS, MachineDominatorTree &MDT,
229 UserValueScopes &UVS);
230
231 /// addDefsFromCopies - The value in LI/LocNo may be copies to other
232 /// registers. Determine if any of the copies are available at the kill
233 /// points, and add defs if possible.
234 /// @param LI Scan for copies of the value in LI->reg.
235 /// @param LocNo Location number of LI->reg.
236 /// @param Kills Points where the range of LocNo could be extended.
237 /// @param NewDefs Append (Idx, LocNo) of inserted defs here.
238 void addDefsFromCopies(LiveInterval *LI, unsigned LocNo,
239 const SmallVectorImpl<SlotIndex> &Kills,
240 SmallVectorImpl<std::pair<SlotIndex, unsigned> > &NewDefs,
241 MachineRegisterInfo &MRI,
242 LiveIntervals &LIS);
243
244 /// computeIntervals - Compute the live intervals of all locations after
245 /// collecting all their def points.
246 void computeIntervals(MachineRegisterInfo &MRI,
247 LiveIntervals &LIS, MachineDominatorTree &MDT,
248 UserValueScopes &UVS);
249
250 /// renameRegister - Update locations to rewrite OldReg as NewReg:SubIdx.
251 void renameRegister(unsigned OldReg, unsigned NewReg, unsigned SubIdx,
252 const TargetRegisterInfo *TRI);
253
254 /// splitRegister - Replace OldReg ranges with NewRegs ranges where NewRegs is
255 /// live. Returns true if any changes were made.
256 bool splitRegister(unsigned OldLocNo, ArrayRef<LiveInterval*> NewRegs);
257
258 /// rewriteLocations - Rewrite virtual register locations according to the
259 /// provided virtual register map.
260 void rewriteLocations(VirtRegMap &VRM, const TargetRegisterInfo &TRI);
261
262 /// emitDebugVariables - Recreate DBG_VALUE instruction from data structures.
263 void emitDebugValues(VirtRegMap *VRM,
264 LiveIntervals &LIS, const TargetInstrInfo &TRI);
265
266 /// findDebugLoc - Return DebugLoc used for this DBG_VALUE instruction. A
267 /// variable may have more than one corresponding DBG_VALUE instructions.
268 /// Only first one needs DebugLoc to identify variable's lexical scope
269 /// in source file.
270 DebugLoc findDebugLoc();
271
272 /// getDebugLoc - Return DebugLoc of this UserValue.
getDebugLoc()273 DebugLoc getDebugLoc() { return dl;}
274 void print(raw_ostream&, const TargetMachine*);
275 };
276 } // namespace
277
278 /// LDVImpl - Implementation of the LiveDebugVariables pass.
279 namespace {
280 class LDVImpl {
281 LiveDebugVariables &pass;
282 LocMap::Allocator allocator;
283 MachineFunction *MF;
284 LiveIntervals *LIS;
285 LexicalScopes LS;
286 MachineDominatorTree *MDT;
287 const TargetRegisterInfo *TRI;
288
289 /// userValues - All allocated UserValue instances.
290 SmallVector<UserValue*, 8> userValues;
291
292 /// Map virtual register to eq class leader.
293 typedef DenseMap<unsigned, UserValue*> VRMap;
294 VRMap virtRegToEqClass;
295
296 /// Map user variable to eq class leader.
297 typedef DenseMap<const MDNode *, UserValue*> UVMap;
298 UVMap userVarMap;
299
300 /// getUserValue - Find or create a UserValue.
301 UserValue *getUserValue(const MDNode *Var, unsigned Offset, DebugLoc DL);
302
303 /// lookupVirtReg - Find the EC leader for VirtReg or null.
304 UserValue *lookupVirtReg(unsigned VirtReg);
305
306 /// handleDebugValue - Add DBG_VALUE instruction to our maps.
307 /// @param MI DBG_VALUE instruction
308 /// @param Idx Last valid SLotIndex before instruction.
309 /// @return True if the DBG_VALUE instruction should be deleted.
310 bool handleDebugValue(MachineInstr *MI, SlotIndex Idx);
311
312 /// collectDebugValues - Collect and erase all DBG_VALUE instructions, adding
313 /// a UserValue def for each instruction.
314 /// @param mf MachineFunction to be scanned.
315 /// @return True if any debug values were found.
316 bool collectDebugValues(MachineFunction &mf);
317
318 /// computeIntervals - Compute the live intervals of all user values after
319 /// collecting all their def points.
320 void computeIntervals();
321
322 public:
LDVImpl(LiveDebugVariables * ps)323 LDVImpl(LiveDebugVariables *ps) : pass(*ps) {}
324 bool runOnMachineFunction(MachineFunction &mf);
325
326 /// clear - Relase all memory.
clear()327 void clear() {
328 DeleteContainerPointers(userValues);
329 userValues.clear();
330 virtRegToEqClass.clear();
331 userVarMap.clear();
332 }
333
334 /// mapVirtReg - Map virtual register to an equivalence class.
335 void mapVirtReg(unsigned VirtReg, UserValue *EC);
336
337 /// renameRegister - Replace all references to OldReg with NewReg:SubIdx.
338 void renameRegister(unsigned OldReg, unsigned NewReg, unsigned SubIdx);
339
340 /// splitRegister - Replace all references to OldReg with NewRegs.
341 void splitRegister(unsigned OldReg, ArrayRef<LiveInterval*> NewRegs);
342
343 /// emitDebugVariables - Recreate DBG_VALUE instruction from data structures.
344 void emitDebugValues(VirtRegMap *VRM);
345
346 void print(raw_ostream&);
347 };
348 } // namespace
349
print(raw_ostream & OS,const TargetMachine * TM)350 void UserValue::print(raw_ostream &OS, const TargetMachine *TM) {
351 DIVariable DV(variable);
352 OS << "!\"";
353 DV.printExtendedName(OS);
354 OS << "\"\t";
355 if (offset)
356 OS << '+' << offset;
357 for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I) {
358 OS << " [" << I.start() << ';' << I.stop() << "):";
359 if (I.value() == ~0u)
360 OS << "undef";
361 else
362 OS << I.value();
363 }
364 for (unsigned i = 0, e = locations.size(); i != e; ++i) {
365 OS << " Loc" << i << '=';
366 locations[i].print(OS, TM);
367 }
368 OS << '\n';
369 }
370
print(raw_ostream & OS)371 void LDVImpl::print(raw_ostream &OS) {
372 OS << "********** DEBUG VARIABLES **********\n";
373 for (unsigned i = 0, e = userValues.size(); i != e; ++i)
374 userValues[i]->print(OS, &MF->getTarget());
375 }
376
coalesceLocation(unsigned LocNo)377 void UserValue::coalesceLocation(unsigned LocNo) {
378 unsigned KeepLoc = 0;
379 for (unsigned e = locations.size(); KeepLoc != e; ++KeepLoc) {
380 if (KeepLoc == LocNo)
381 continue;
382 if (locations[KeepLoc].isIdenticalTo(locations[LocNo]))
383 break;
384 }
385 // No matches.
386 if (KeepLoc == locations.size())
387 return;
388
389 // Keep the smaller location, erase the larger one.
390 unsigned EraseLoc = LocNo;
391 if (KeepLoc > EraseLoc)
392 std::swap(KeepLoc, EraseLoc);
393 locations.erase(locations.begin() + EraseLoc);
394
395 // Rewrite values.
396 for (LocMap::iterator I = locInts.begin(); I.valid(); ++I) {
397 unsigned v = I.value();
398 if (v == EraseLoc)
399 I.setValue(KeepLoc); // Coalesce when possible.
400 else if (v > EraseLoc)
401 I.setValueUnchecked(v-1); // Avoid coalescing with untransformed values.
402 }
403 }
404
mapVirtRegs(LDVImpl * LDV)405 void UserValue::mapVirtRegs(LDVImpl *LDV) {
406 for (unsigned i = 0, e = locations.size(); i != e; ++i)
407 if (locations[i].isReg() &&
408 TargetRegisterInfo::isVirtualRegister(locations[i].getReg()))
409 LDV->mapVirtReg(locations[i].getReg(), this);
410 }
411
getUserValue(const MDNode * Var,unsigned Offset,DebugLoc DL)412 UserValue *LDVImpl::getUserValue(const MDNode *Var, unsigned Offset,
413 DebugLoc DL) {
414 UserValue *&Leader = userVarMap[Var];
415 if (Leader) {
416 UserValue *UV = Leader->getLeader();
417 Leader = UV;
418 for (; UV; UV = UV->getNext())
419 if (UV->match(Var, Offset))
420 return UV;
421 }
422
423 UserValue *UV = new UserValue(Var, Offset, DL, allocator);
424 userValues.push_back(UV);
425 Leader = UserValue::merge(Leader, UV);
426 return UV;
427 }
428
mapVirtReg(unsigned VirtReg,UserValue * EC)429 void LDVImpl::mapVirtReg(unsigned VirtReg, UserValue *EC) {
430 assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && "Only map VirtRegs");
431 UserValue *&Leader = virtRegToEqClass[VirtReg];
432 Leader = UserValue::merge(Leader, EC);
433 }
434
lookupVirtReg(unsigned VirtReg)435 UserValue *LDVImpl::lookupVirtReg(unsigned VirtReg) {
436 if (UserValue *UV = virtRegToEqClass.lookup(VirtReg))
437 return UV->getLeader();
438 return 0;
439 }
440
handleDebugValue(MachineInstr * MI,SlotIndex Idx)441 bool LDVImpl::handleDebugValue(MachineInstr *MI, SlotIndex Idx) {
442 // DBG_VALUE loc, offset, variable
443 if (MI->getNumOperands() != 3 ||
444 !MI->getOperand(1).isImm() || !MI->getOperand(2).isMetadata()) {
445 DEBUG(dbgs() << "Can't handle " << *MI);
446 return false;
447 }
448
449 // Get or create the UserValue for (variable,offset).
450 unsigned Offset = MI->getOperand(1).getImm();
451 const MDNode *Var = MI->getOperand(2).getMetadata();
452 UserValue *UV = getUserValue(Var, Offset, MI->getDebugLoc());
453 UV->addDef(Idx, MI->getOperand(0));
454 return true;
455 }
456
collectDebugValues(MachineFunction & mf)457 bool LDVImpl::collectDebugValues(MachineFunction &mf) {
458 bool Changed = false;
459 for (MachineFunction::iterator MFI = mf.begin(), MFE = mf.end(); MFI != MFE;
460 ++MFI) {
461 MachineBasicBlock *MBB = MFI;
462 for (MachineBasicBlock::iterator MBBI = MBB->begin(), MBBE = MBB->end();
463 MBBI != MBBE;) {
464 if (!MBBI->isDebugValue()) {
465 ++MBBI;
466 continue;
467 }
468 // DBG_VALUE has no slot index, use the previous instruction instead.
469 SlotIndex Idx = MBBI == MBB->begin() ?
470 LIS->getMBBStartIdx(MBB) :
471 LIS->getInstructionIndex(llvm::prior(MBBI)).getDefIndex();
472 // Handle consecutive DBG_VALUE instructions with the same slot index.
473 do {
474 if (handleDebugValue(MBBI, Idx)) {
475 MBBI = MBB->erase(MBBI);
476 Changed = true;
477 } else
478 ++MBBI;
479 } while (MBBI != MBBE && MBBI->isDebugValue());
480 }
481 }
482 return Changed;
483 }
484
extendDef(SlotIndex Idx,unsigned LocNo,LiveInterval * LI,const VNInfo * VNI,SmallVectorImpl<SlotIndex> * Kills,LiveIntervals & LIS,MachineDominatorTree & MDT,UserValueScopes & UVS)485 void UserValue::extendDef(SlotIndex Idx, unsigned LocNo,
486 LiveInterval *LI, const VNInfo *VNI,
487 SmallVectorImpl<SlotIndex> *Kills,
488 LiveIntervals &LIS, MachineDominatorTree &MDT,
489 UserValueScopes &UVS) {
490 SmallVector<SlotIndex, 16> Todo;
491 Todo.push_back(Idx);
492 do {
493 SlotIndex Start = Todo.pop_back_val();
494 MachineBasicBlock *MBB = LIS.getMBBFromIndex(Start);
495 SlotIndex Stop = LIS.getMBBEndIdx(MBB);
496 LocMap::iterator I = locInts.find(Start);
497
498 // Limit to VNI's live range.
499 bool ToEnd = true;
500 if (LI && VNI) {
501 LiveRange *Range = LI->getLiveRangeContaining(Start);
502 if (!Range || Range->valno != VNI) {
503 if (Kills)
504 Kills->push_back(Start);
505 continue;
506 }
507 if (Range->end < Stop)
508 Stop = Range->end, ToEnd = false;
509 }
510
511 // There could already be a short def at Start.
512 if (I.valid() && I.start() <= Start) {
513 // Stop when meeting a different location or an already extended interval.
514 Start = Start.getNextSlot();
515 if (I.value() != LocNo || I.stop() != Start)
516 continue;
517 // This is a one-slot placeholder. Just skip it.
518 ++I;
519 }
520
521 // Limited by the next def.
522 if (I.valid() && I.start() < Stop)
523 Stop = I.start(), ToEnd = false;
524 // Limited by VNI's live range.
525 else if (!ToEnd && Kills)
526 Kills->push_back(Stop);
527
528 if (Start >= Stop)
529 continue;
530
531 I.insert(Start, Stop, LocNo);
532
533 // If we extended to the MBB end, propagate down the dominator tree.
534 if (!ToEnd)
535 continue;
536 const std::vector<MachineDomTreeNode*> &Children =
537 MDT.getNode(MBB)->getChildren();
538 for (unsigned i = 0, e = Children.size(); i != e; ++i) {
539 MachineBasicBlock *MBB = Children[i]->getBlock();
540 if (UVS.dominates(MBB))
541 Todo.push_back(LIS.getMBBStartIdx(MBB));
542 }
543 } while (!Todo.empty());
544 }
545
546 void
addDefsFromCopies(LiveInterval * LI,unsigned LocNo,const SmallVectorImpl<SlotIndex> & Kills,SmallVectorImpl<std::pair<SlotIndex,unsigned>> & NewDefs,MachineRegisterInfo & MRI,LiveIntervals & LIS)547 UserValue::addDefsFromCopies(LiveInterval *LI, unsigned LocNo,
548 const SmallVectorImpl<SlotIndex> &Kills,
549 SmallVectorImpl<std::pair<SlotIndex, unsigned> > &NewDefs,
550 MachineRegisterInfo &MRI, LiveIntervals &LIS) {
551 if (Kills.empty())
552 return;
553 // Don't track copies from physregs, there are too many uses.
554 if (!TargetRegisterInfo::isVirtualRegister(LI->reg))
555 return;
556
557 // Collect all the (vreg, valno) pairs that are copies of LI.
558 SmallVector<std::pair<LiveInterval*, const VNInfo*>, 8> CopyValues;
559 for (MachineRegisterInfo::use_nodbg_iterator
560 UI = MRI.use_nodbg_begin(LI->reg),
561 UE = MRI.use_nodbg_end(); UI != UE; ++UI) {
562 // Copies of the full value.
563 if (UI.getOperand().getSubReg() || !UI->isCopy())
564 continue;
565 MachineInstr *MI = &*UI;
566 unsigned DstReg = MI->getOperand(0).getReg();
567
568 // Don't follow copies to physregs. These are usually setting up call
569 // arguments, and the argument registers are always call clobbered. We are
570 // better off in the source register which could be a callee-saved register,
571 // or it could be spilled.
572 if (!TargetRegisterInfo::isVirtualRegister(DstReg))
573 continue;
574
575 // Is LocNo extended to reach this copy? If not, another def may be blocking
576 // it, or we are looking at a wrong value of LI.
577 SlotIndex Idx = LIS.getInstructionIndex(MI);
578 LocMap::iterator I = locInts.find(Idx.getUseIndex());
579 if (!I.valid() || I.value() != LocNo)
580 continue;
581
582 if (!LIS.hasInterval(DstReg))
583 continue;
584 LiveInterval *DstLI = &LIS.getInterval(DstReg);
585 const VNInfo *DstVNI = DstLI->getVNInfoAt(Idx.getDefIndex());
586 assert(DstVNI && DstVNI->def == Idx.getDefIndex() && "Bad copy value");
587 CopyValues.push_back(std::make_pair(DstLI, DstVNI));
588 }
589
590 if (CopyValues.empty())
591 return;
592
593 DEBUG(dbgs() << "Got " << CopyValues.size() << " copies of " << *LI << '\n');
594
595 // Try to add defs of the copied values for each kill point.
596 for (unsigned i = 0, e = Kills.size(); i != e; ++i) {
597 SlotIndex Idx = Kills[i];
598 for (unsigned j = 0, e = CopyValues.size(); j != e; ++j) {
599 LiveInterval *DstLI = CopyValues[j].first;
600 const VNInfo *DstVNI = CopyValues[j].second;
601 if (DstLI->getVNInfoAt(Idx) != DstVNI)
602 continue;
603 // Check that there isn't already a def at Idx
604 LocMap::iterator I = locInts.find(Idx);
605 if (I.valid() && I.start() <= Idx)
606 continue;
607 DEBUG(dbgs() << "Kill at " << Idx << " covered by valno #"
608 << DstVNI->id << " in " << *DstLI << '\n');
609 MachineInstr *CopyMI = LIS.getInstructionFromIndex(DstVNI->def);
610 assert(CopyMI && CopyMI->isCopy() && "Bad copy value");
611 unsigned LocNo = getLocationNo(CopyMI->getOperand(0));
612 I.insert(Idx, Idx.getNextSlot(), LocNo);
613 NewDefs.push_back(std::make_pair(Idx, LocNo));
614 break;
615 }
616 }
617 }
618
619 void
computeIntervals(MachineRegisterInfo & MRI,LiveIntervals & LIS,MachineDominatorTree & MDT,UserValueScopes & UVS)620 UserValue::computeIntervals(MachineRegisterInfo &MRI,
621 LiveIntervals &LIS,
622 MachineDominatorTree &MDT,
623 UserValueScopes &UVS) {
624 SmallVector<std::pair<SlotIndex, unsigned>, 16> Defs;
625
626 // Collect all defs to be extended (Skipping undefs).
627 for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I)
628 if (I.value() != ~0u)
629 Defs.push_back(std::make_pair(I.start(), I.value()));
630
631 // Extend all defs, and possibly add new ones along the way.
632 for (unsigned i = 0; i != Defs.size(); ++i) {
633 SlotIndex Idx = Defs[i].first;
634 unsigned LocNo = Defs[i].second;
635 const MachineOperand &Loc = locations[LocNo];
636
637 // Register locations are constrained to where the register value is live.
638 if (Loc.isReg() && LIS.hasInterval(Loc.getReg())) {
639 LiveInterval *LI = &LIS.getInterval(Loc.getReg());
640 const VNInfo *VNI = LI->getVNInfoAt(Idx);
641 SmallVector<SlotIndex, 16> Kills;
642 extendDef(Idx, LocNo, LI, VNI, &Kills, LIS, MDT, UVS);
643 addDefsFromCopies(LI, LocNo, Kills, Defs, MRI, LIS);
644 } else
645 extendDef(Idx, LocNo, 0, 0, 0, LIS, MDT, UVS);
646 }
647
648 // Finally, erase all the undefs.
649 for (LocMap::iterator I = locInts.begin(); I.valid();)
650 if (I.value() == ~0u)
651 I.erase();
652 else
653 ++I;
654 }
655
computeIntervals()656 void LDVImpl::computeIntervals() {
657 for (unsigned i = 0, e = userValues.size(); i != e; ++i) {
658 UserValueScopes UVS(userValues[i]->getDebugLoc(), LS);
659 userValues[i]->computeIntervals(MF->getRegInfo(), *LIS, *MDT, UVS);
660 userValues[i]->mapVirtRegs(this);
661 }
662 }
663
runOnMachineFunction(MachineFunction & mf)664 bool LDVImpl::runOnMachineFunction(MachineFunction &mf) {
665 MF = &mf;
666 LIS = &pass.getAnalysis<LiveIntervals>();
667 MDT = &pass.getAnalysis<MachineDominatorTree>();
668 TRI = mf.getTarget().getRegisterInfo();
669 clear();
670 LS.initialize(mf);
671 DEBUG(dbgs() << "********** COMPUTING LIVE DEBUG VARIABLES: "
672 << ((Value*)mf.getFunction())->getName()
673 << " **********\n");
674
675 bool Changed = collectDebugValues(mf);
676 computeIntervals();
677 DEBUG(print(dbgs()));
678 LS.releaseMemory();
679 return Changed;
680 }
681
runOnMachineFunction(MachineFunction & mf)682 bool LiveDebugVariables::runOnMachineFunction(MachineFunction &mf) {
683 if (!EnableLDV)
684 return false;
685 if (!pImpl)
686 pImpl = new LDVImpl(this);
687 return static_cast<LDVImpl*>(pImpl)->runOnMachineFunction(mf);
688 }
689
releaseMemory()690 void LiveDebugVariables::releaseMemory() {
691 if (pImpl)
692 static_cast<LDVImpl*>(pImpl)->clear();
693 }
694
~LiveDebugVariables()695 LiveDebugVariables::~LiveDebugVariables() {
696 if (pImpl)
697 delete static_cast<LDVImpl*>(pImpl);
698 }
699
700 void UserValue::
renameRegister(unsigned OldReg,unsigned NewReg,unsigned SubIdx,const TargetRegisterInfo * TRI)701 renameRegister(unsigned OldReg, unsigned NewReg, unsigned SubIdx,
702 const TargetRegisterInfo *TRI) {
703 for (unsigned i = locations.size(); i; --i) {
704 unsigned LocNo = i - 1;
705 MachineOperand &Loc = locations[LocNo];
706 if (!Loc.isReg() || Loc.getReg() != OldReg)
707 continue;
708 if (TargetRegisterInfo::isPhysicalRegister(NewReg))
709 Loc.substPhysReg(NewReg, *TRI);
710 else
711 Loc.substVirtReg(NewReg, SubIdx, *TRI);
712 coalesceLocation(LocNo);
713 }
714 }
715
716 void LDVImpl::
renameRegister(unsigned OldReg,unsigned NewReg,unsigned SubIdx)717 renameRegister(unsigned OldReg, unsigned NewReg, unsigned SubIdx) {
718 UserValue *UV = lookupVirtReg(OldReg);
719 if (!UV)
720 return;
721
722 if (TargetRegisterInfo::isVirtualRegister(NewReg))
723 mapVirtReg(NewReg, UV);
724 virtRegToEqClass.erase(OldReg);
725
726 do {
727 UV->renameRegister(OldReg, NewReg, SubIdx, TRI);
728 UV = UV->getNext();
729 } while (UV);
730 }
731
732 void LiveDebugVariables::
renameRegister(unsigned OldReg,unsigned NewReg,unsigned SubIdx)733 renameRegister(unsigned OldReg, unsigned NewReg, unsigned SubIdx) {
734 if (pImpl)
735 static_cast<LDVImpl*>(pImpl)->renameRegister(OldReg, NewReg, SubIdx);
736 }
737
738 //===----------------------------------------------------------------------===//
739 // Live Range Splitting
740 //===----------------------------------------------------------------------===//
741
742 bool
splitLocation(unsigned OldLocNo,ArrayRef<LiveInterval * > NewRegs)743 UserValue::splitLocation(unsigned OldLocNo, ArrayRef<LiveInterval*> NewRegs) {
744 DEBUG({
745 dbgs() << "Splitting Loc" << OldLocNo << '\t';
746 print(dbgs(), 0);
747 });
748 bool DidChange = false;
749 LocMap::iterator LocMapI;
750 LocMapI.setMap(locInts);
751 for (unsigned i = 0; i != NewRegs.size(); ++i) {
752 LiveInterval *LI = NewRegs[i];
753 if (LI->empty())
754 continue;
755
756 // Don't allocate the new LocNo until it is needed.
757 unsigned NewLocNo = ~0u;
758
759 // Iterate over the overlaps between locInts and LI.
760 LocMapI.find(LI->beginIndex());
761 if (!LocMapI.valid())
762 continue;
763 LiveInterval::iterator LII = LI->advanceTo(LI->begin(), LocMapI.start());
764 LiveInterval::iterator LIE = LI->end();
765 while (LocMapI.valid() && LII != LIE) {
766 // At this point, we know that LocMapI.stop() > LII->start.
767 LII = LI->advanceTo(LII, LocMapI.start());
768 if (LII == LIE)
769 break;
770
771 // Now LII->end > LocMapI.start(). Do we have an overlap?
772 if (LocMapI.value() == OldLocNo && LII->start < LocMapI.stop()) {
773 // Overlapping correct location. Allocate NewLocNo now.
774 if (NewLocNo == ~0u) {
775 MachineOperand MO = MachineOperand::CreateReg(LI->reg, false);
776 MO.setSubReg(locations[OldLocNo].getSubReg());
777 NewLocNo = getLocationNo(MO);
778 DidChange = true;
779 }
780
781 SlotIndex LStart = LocMapI.start();
782 SlotIndex LStop = LocMapI.stop();
783
784 // Trim LocMapI down to the LII overlap.
785 if (LStart < LII->start)
786 LocMapI.setStartUnchecked(LII->start);
787 if (LStop > LII->end)
788 LocMapI.setStopUnchecked(LII->end);
789
790 // Change the value in the overlap. This may trigger coalescing.
791 LocMapI.setValue(NewLocNo);
792
793 // Re-insert any removed OldLocNo ranges.
794 if (LStart < LocMapI.start()) {
795 LocMapI.insert(LStart, LocMapI.start(), OldLocNo);
796 ++LocMapI;
797 assert(LocMapI.valid() && "Unexpected coalescing");
798 }
799 if (LStop > LocMapI.stop()) {
800 ++LocMapI;
801 LocMapI.insert(LII->end, LStop, OldLocNo);
802 --LocMapI;
803 }
804 }
805
806 // Advance to the next overlap.
807 if (LII->end < LocMapI.stop()) {
808 if (++LII == LIE)
809 break;
810 LocMapI.advanceTo(LII->start);
811 } else {
812 ++LocMapI;
813 if (!LocMapI.valid())
814 break;
815 LII = LI->advanceTo(LII, LocMapI.start());
816 }
817 }
818 }
819
820 // Finally, remove any remaining OldLocNo intervals and OldLocNo itself.
821 locations.erase(locations.begin() + OldLocNo);
822 LocMapI.goToBegin();
823 while (LocMapI.valid()) {
824 unsigned v = LocMapI.value();
825 if (v == OldLocNo) {
826 DEBUG(dbgs() << "Erasing [" << LocMapI.start() << ';'
827 << LocMapI.stop() << ")\n");
828 LocMapI.erase();
829 } else {
830 if (v > OldLocNo)
831 LocMapI.setValueUnchecked(v-1);
832 ++LocMapI;
833 }
834 }
835
836 DEBUG({dbgs() << "Split result: \t"; print(dbgs(), 0);});
837 return DidChange;
838 }
839
840 bool
splitRegister(unsigned OldReg,ArrayRef<LiveInterval * > NewRegs)841 UserValue::splitRegister(unsigned OldReg, ArrayRef<LiveInterval*> NewRegs) {
842 bool DidChange = false;
843 // Split locations referring to OldReg. Iterate backwards so splitLocation can
844 // safely erase unuused locations.
845 for (unsigned i = locations.size(); i ; --i) {
846 unsigned LocNo = i-1;
847 const MachineOperand *Loc = &locations[LocNo];
848 if (!Loc->isReg() || Loc->getReg() != OldReg)
849 continue;
850 DidChange |= splitLocation(LocNo, NewRegs);
851 }
852 return DidChange;
853 }
854
splitRegister(unsigned OldReg,ArrayRef<LiveInterval * > NewRegs)855 void LDVImpl::splitRegister(unsigned OldReg, ArrayRef<LiveInterval*> NewRegs) {
856 bool DidChange = false;
857 for (UserValue *UV = lookupVirtReg(OldReg); UV; UV = UV->getNext())
858 DidChange |= UV->splitRegister(OldReg, NewRegs);
859
860 if (!DidChange)
861 return;
862
863 // Map all of the new virtual registers.
864 UserValue *UV = lookupVirtReg(OldReg);
865 for (unsigned i = 0; i != NewRegs.size(); ++i)
866 mapVirtReg(NewRegs[i]->reg, UV);
867 }
868
869 void LiveDebugVariables::
splitRegister(unsigned OldReg,ArrayRef<LiveInterval * > NewRegs)870 splitRegister(unsigned OldReg, ArrayRef<LiveInterval*> NewRegs) {
871 if (pImpl)
872 static_cast<LDVImpl*>(pImpl)->splitRegister(OldReg, NewRegs);
873 }
874
875 void
rewriteLocations(VirtRegMap & VRM,const TargetRegisterInfo & TRI)876 UserValue::rewriteLocations(VirtRegMap &VRM, const TargetRegisterInfo &TRI) {
877 // Iterate over locations in reverse makes it easier to handle coalescing.
878 for (unsigned i = locations.size(); i ; --i) {
879 unsigned LocNo = i-1;
880 MachineOperand &Loc = locations[LocNo];
881 // Only virtual registers are rewritten.
882 if (!Loc.isReg() || !Loc.getReg() ||
883 !TargetRegisterInfo::isVirtualRegister(Loc.getReg()))
884 continue;
885 unsigned VirtReg = Loc.getReg();
886 if (VRM.isAssignedReg(VirtReg) &&
887 TargetRegisterInfo::isPhysicalRegister(VRM.getPhys(VirtReg))) {
888 // This can create a %noreg operand in rare cases when the sub-register
889 // index is no longer available. That means the user value is in a
890 // non-existent sub-register, and %noreg is exactly what we want.
891 Loc.substPhysReg(VRM.getPhys(VirtReg), TRI);
892 } else if (VRM.getStackSlot(VirtReg) != VirtRegMap::NO_STACK_SLOT &&
893 VRM.isSpillSlotUsed(VRM.getStackSlot(VirtReg))) {
894 // FIXME: Translate SubIdx to a stackslot offset.
895 Loc = MachineOperand::CreateFI(VRM.getStackSlot(VirtReg));
896 } else {
897 Loc.setReg(0);
898 Loc.setSubReg(0);
899 }
900 coalesceLocation(LocNo);
901 }
902 }
903
904 /// findInsertLocation - Find an iterator for inserting a DBG_VALUE
905 /// instruction.
906 static MachineBasicBlock::iterator
findInsertLocation(MachineBasicBlock * MBB,SlotIndex Idx,LiveIntervals & LIS)907 findInsertLocation(MachineBasicBlock *MBB, SlotIndex Idx,
908 LiveIntervals &LIS) {
909 SlotIndex Start = LIS.getMBBStartIdx(MBB);
910 Idx = Idx.getBaseIndex();
911
912 // Try to find an insert location by going backwards from Idx.
913 MachineInstr *MI;
914 while (!(MI = LIS.getInstructionFromIndex(Idx))) {
915 // We've reached the beginning of MBB.
916 if (Idx == Start) {
917 MachineBasicBlock::iterator I = MBB->SkipPHIsAndLabels(MBB->begin());
918 return I;
919 }
920 Idx = Idx.getPrevIndex();
921 }
922
923 // Don't insert anything after the first terminator, though.
924 return MI->getDesc().isTerminator() ? MBB->getFirstTerminator() :
925 llvm::next(MachineBasicBlock::iterator(MI));
926 }
927
findDebugLoc()928 DebugLoc UserValue::findDebugLoc() {
929 DebugLoc D = dl;
930 dl = DebugLoc();
931 return D;
932 }
insertDebugValue(MachineBasicBlock * MBB,SlotIndex Idx,unsigned LocNo,LiveIntervals & LIS,const TargetInstrInfo & TII)933 void UserValue::insertDebugValue(MachineBasicBlock *MBB, SlotIndex Idx,
934 unsigned LocNo,
935 LiveIntervals &LIS,
936 const TargetInstrInfo &TII) {
937 MachineBasicBlock::iterator I = findInsertLocation(MBB, Idx, LIS);
938 MachineOperand &Loc = locations[LocNo];
939 ++NumInsertedDebugValues;
940
941 // Frame index locations may require a target callback.
942 if (Loc.isFI()) {
943 MachineInstr *MI = TII.emitFrameIndexDebugValue(*MBB->getParent(),
944 Loc.getIndex(), offset, variable,
945 findDebugLoc());
946 if (MI) {
947 MBB->insert(I, MI);
948 return;
949 }
950 }
951 // This is not a frame index, or the target is happy with a standard FI.
952 BuildMI(*MBB, I, findDebugLoc(), TII.get(TargetOpcode::DBG_VALUE))
953 .addOperand(Loc).addImm(offset).addMetadata(variable);
954 }
955
emitDebugValues(VirtRegMap * VRM,LiveIntervals & LIS,const TargetInstrInfo & TII)956 void UserValue::emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS,
957 const TargetInstrInfo &TII) {
958 MachineFunction::iterator MFEnd = VRM->getMachineFunction().end();
959
960 for (LocMap::const_iterator I = locInts.begin(); I.valid();) {
961 SlotIndex Start = I.start();
962 SlotIndex Stop = I.stop();
963 unsigned LocNo = I.value();
964 DEBUG(dbgs() << "\t[" << Start << ';' << Stop << "):" << LocNo);
965 MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start);
966 SlotIndex MBBEnd = LIS.getMBBEndIdx(MBB);
967
968 DEBUG(dbgs() << " BB#" << MBB->getNumber() << '-' << MBBEnd);
969 insertDebugValue(MBB, Start, LocNo, LIS, TII);
970 // This interval may span multiple basic blocks.
971 // Insert a DBG_VALUE into each one.
972 while(Stop > MBBEnd) {
973 // Move to the next block.
974 Start = MBBEnd;
975 if (++MBB == MFEnd)
976 break;
977 MBBEnd = LIS.getMBBEndIdx(MBB);
978 DEBUG(dbgs() << " BB#" << MBB->getNumber() << '-' << MBBEnd);
979 insertDebugValue(MBB, Start, LocNo, LIS, TII);
980 }
981 DEBUG(dbgs() << '\n');
982 if (MBB == MFEnd)
983 break;
984
985 ++I;
986 }
987 }
988
emitDebugValues(VirtRegMap * VRM)989 void LDVImpl::emitDebugValues(VirtRegMap *VRM) {
990 DEBUG(dbgs() << "********** EMITTING LIVE DEBUG VARIABLES **********\n");
991 const TargetInstrInfo *TII = MF->getTarget().getInstrInfo();
992 for (unsigned i = 0, e = userValues.size(); i != e; ++i) {
993 DEBUG(userValues[i]->print(dbgs(), &MF->getTarget()));
994 userValues[i]->rewriteLocations(*VRM, *TRI);
995 userValues[i]->emitDebugValues(VRM, *LIS, *TII);
996 }
997 }
998
emitDebugValues(VirtRegMap * VRM)999 void LiveDebugVariables::emitDebugValues(VirtRegMap *VRM) {
1000 if (pImpl)
1001 static_cast<LDVImpl*>(pImpl)->emitDebugValues(VRM);
1002 }
1003
1004
1005 #ifndef NDEBUG
dump()1006 void LiveDebugVariables::dump() {
1007 if (pImpl)
1008 static_cast<LDVImpl*>(pImpl)->print(dbgs());
1009 }
1010 #endif
1011
1012