]>
git.proxmox.com Git - rustc.git/blob - src/llvm/lib/CodeGen/LiveDebugVariables.cpp
1 //===- LiveDebugVariables.cpp - Tracking debug info variables -------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the LiveDebugVariables analysis.
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.
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.
20 //===----------------------------------------------------------------------===//
22 #include "LiveDebugVariables.h"
23 #include "llvm/ADT/IntervalMap.h"
24 #include "llvm/ADT/Statistic.h"
25 #include "llvm/CodeGen/LexicalScopes.h"
26 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
27 #include "llvm/CodeGen/MachineDominators.h"
28 #include "llvm/CodeGen/MachineFunction.h"
29 #include "llvm/CodeGen/MachineInstrBuilder.h"
30 #include "llvm/CodeGen/MachineRegisterInfo.h"
31 #include "llvm/CodeGen/Passes.h"
32 #include "llvm/CodeGen/VirtRegMap.h"
33 #include "llvm/IR/Constants.h"
34 #include "llvm/IR/DebugInfo.h"
35 #include "llvm/IR/Metadata.h"
36 #include "llvm/IR/Value.h"
37 #include "llvm/Support/CommandLine.h"
38 #include "llvm/Support/Debug.h"
39 #include "llvm/Target/TargetInstrInfo.h"
40 #include "llvm/Target/TargetMachine.h"
41 #include "llvm/Target/TargetRegisterInfo.h"
42 #include "llvm/Target/TargetSubtargetInfo.h"
47 #define DEBUG_TYPE "livedebug"
50 EnableLDV("live-debug-variables", cl::init(true),
51 cl::desc("Enable the live debug variables pass"), cl::Hidden
);
53 STATISTIC(NumInsertedDebugValues
, "Number of DBG_VALUEs inserted");
54 char LiveDebugVariables::ID
= 0;
56 INITIALIZE_PASS_BEGIN(LiveDebugVariables
, "livedebugvars",
57 "Debug Variable Analysis", false, false)
58 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree
)
59 INITIALIZE_PASS_DEPENDENCY(LiveIntervals
)
60 INITIALIZE_PASS_END(LiveDebugVariables
, "livedebugvars",
61 "Debug Variable Analysis", false, false)
63 void LiveDebugVariables::getAnalysisUsage(AnalysisUsage
&AU
) const {
64 AU
.addRequired
<MachineDominatorTree
>();
65 AU
.addRequiredTransitive
<LiveIntervals
>();
67 MachineFunctionPass::getAnalysisUsage(AU
);
70 LiveDebugVariables::LiveDebugVariables() : MachineFunctionPass(ID
), pImpl(nullptr) {
71 initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry());
74 /// LocMap - Map of where a user value is live, and its location.
75 typedef IntervalMap
<SlotIndex
, unsigned, 4> LocMap
;
78 /// UserValueScopes - Keeps track of lexical scopes associated with a
79 /// user value's source location.
80 class UserValueScopes
{
83 SmallPtrSet
<const MachineBasicBlock
*, 4> LBlocks
;
86 UserValueScopes(DebugLoc D
, LexicalScopes
&L
) : DL(D
), LS(L
) {}
88 /// dominates - Return true if current scope dominates at least one machine
89 /// instruction in a given machine basic block.
90 bool dominates(MachineBasicBlock
*MBB
) {
92 LS
.getMachineBasicBlocks(DL
, LBlocks
);
93 if (LBlocks
.count(MBB
) != 0 || LS
.dominates(DL
, MBB
))
98 } // end anonymous namespace
100 /// UserValue - A user value is a part of a debug info user variable.
102 /// A DBG_VALUE instruction notes that (a sub-register of) a virtual register
103 /// holds part of a user variable. The part is identified by a byte offset.
105 /// UserValues are grouped into equivalence classes for easier searching. Two
106 /// user values are related if they refer to the same variable, or if they are
107 /// held by the same virtual register. The equivalence class is the transitive
108 /// closure of that relation.
112 const MDNode
*Variable
; ///< The debug info variable we are part of.
113 const MDNode
*Expression
; ///< Any complex address expression.
114 unsigned offset
; ///< Byte offset into variable.
115 bool IsIndirect
; ///< true if this is a register-indirect+offset value.
116 DebugLoc dl
; ///< The debug location for the variable. This is
117 ///< used by dwarf writer to find lexical scope.
118 UserValue
*leader
; ///< Equivalence class leader.
119 UserValue
*next
; ///< Next value in equivalence class, or null.
121 /// Numbered locations referenced by locmap.
122 SmallVector
<MachineOperand
, 4> locations
;
124 /// Map of slot indices where this value is live.
127 /// coalesceLocation - After LocNo was changed, check if it has become
128 /// identical to another location, and coalesce them. This may cause LocNo or
129 /// a later location to be erased, but no earlier location will be erased.
130 void coalesceLocation(unsigned LocNo
);
132 /// insertDebugValue - Insert a DBG_VALUE into MBB at Idx for LocNo.
133 void insertDebugValue(MachineBasicBlock
*MBB
, SlotIndex Idx
, unsigned LocNo
,
134 LiveIntervals
&LIS
, const TargetInstrInfo
&TII
);
136 /// splitLocation - Replace OldLocNo ranges with NewRegs ranges where NewRegs
137 /// is live. Returns true if any changes were made.
138 bool splitLocation(unsigned OldLocNo
, ArrayRef
<unsigned> NewRegs
,
142 /// UserValue - Create a new UserValue.
143 UserValue(const MDNode
*var
, const MDNode
*expr
, unsigned o
, bool i
,
144 DebugLoc L
, LocMap::Allocator
&alloc
)
145 : Variable(var
), Expression(expr
), offset(o
), IsIndirect(i
), dl(L
),
146 leader(this), next(nullptr), locInts(alloc
) {}
148 /// getLeader - Get the leader of this value's equivalence class.
149 UserValue
*getLeader() {
150 UserValue
*l
= leader
;
151 while (l
!= l
->leader
)
156 /// getNext - Return the next UserValue in the equivalence class.
157 UserValue
*getNext() const { return next
; }
159 /// match - Does this UserValue match the parameters?
160 bool match(const MDNode
*Var
, const MDNode
*Expr
, unsigned Offset
,
161 bool indirect
) const {
162 return Var
== Variable
&& Expr
== Expression
&& Offset
== offset
&&
163 indirect
== IsIndirect
;
166 /// merge - Merge equivalence classes.
167 static UserValue
*merge(UserValue
*L1
, UserValue
*L2
) {
168 L2
= L2
->getLeader();
171 L1
= L1
->getLeader();
174 // Splice L2 before L1's members.
177 End
->leader
= L1
, End
= End
->next
;
179 End
->next
= L1
->next
;
184 /// getLocationNo - Return the location number that matches Loc.
185 unsigned getLocationNo(const MachineOperand
&LocMO
) {
187 if (LocMO
.getReg() == 0)
189 // For register locations we dont care about use/def and other flags.
190 for (unsigned i
= 0, e
= locations
.size(); i
!= e
; ++i
)
191 if (locations
[i
].isReg() &&
192 locations
[i
].getReg() == LocMO
.getReg() &&
193 locations
[i
].getSubReg() == LocMO
.getSubReg())
196 for (unsigned i
= 0, e
= locations
.size(); i
!= e
; ++i
)
197 if (LocMO
.isIdenticalTo(locations
[i
]))
199 locations
.push_back(LocMO
);
200 // We are storing a MachineOperand outside a MachineInstr.
201 locations
.back().clearParent();
202 // Don't store def operands.
203 if (locations
.back().isReg())
204 locations
.back().setIsUse();
205 return locations
.size() - 1;
208 /// mapVirtRegs - Ensure that all virtual register locations are mapped.
209 void mapVirtRegs(LDVImpl
*LDV
);
211 /// addDef - Add a definition point to this value.
212 void addDef(SlotIndex Idx
, const MachineOperand
&LocMO
) {
213 // Add a singular (Idx,Idx) -> Loc mapping.
214 LocMap::iterator I
= locInts
.find(Idx
);
215 if (!I
.valid() || I
.start() != Idx
)
216 I
.insert(Idx
, Idx
.getNextSlot(), getLocationNo(LocMO
));
218 // A later DBG_VALUE at the same SlotIndex overrides the old location.
219 I
.setValue(getLocationNo(LocMO
));
222 /// extendDef - Extend the current definition as far as possible down the
223 /// dominator tree. Stop when meeting an existing def or when leaving the live
225 /// End points where VNI is no longer live are added to Kills.
226 /// @param Idx Starting point for the definition.
227 /// @param LocNo Location number to propagate.
228 /// @param LR Restrict liveness to where LR has the value VNI. May be null.
229 /// @param VNI When LR is not null, this is the value to restrict to.
230 /// @param Kills Append end points of VNI's live range to Kills.
231 /// @param LIS Live intervals analysis.
232 /// @param MDT Dominator tree.
233 void extendDef(SlotIndex Idx
, unsigned LocNo
,
234 LiveRange
*LR
, const VNInfo
*VNI
,
235 SmallVectorImpl
<SlotIndex
> *Kills
,
236 LiveIntervals
&LIS
, MachineDominatorTree
&MDT
,
237 UserValueScopes
&UVS
);
239 /// addDefsFromCopies - The value in LI/LocNo may be copies to other
240 /// registers. Determine if any of the copies are available at the kill
241 /// points, and add defs if possible.
242 /// @param LI Scan for copies of the value in LI->reg.
243 /// @param LocNo Location number of LI->reg.
244 /// @param Kills Points where the range of LocNo could be extended.
245 /// @param NewDefs Append (Idx, LocNo) of inserted defs here.
246 void addDefsFromCopies(LiveInterval
*LI
, unsigned LocNo
,
247 const SmallVectorImpl
<SlotIndex
> &Kills
,
248 SmallVectorImpl
<std::pair
<SlotIndex
, unsigned> > &NewDefs
,
249 MachineRegisterInfo
&MRI
,
252 /// computeIntervals - Compute the live intervals of all locations after
253 /// collecting all their def points.
254 void computeIntervals(MachineRegisterInfo
&MRI
, const TargetRegisterInfo
&TRI
,
255 LiveIntervals
&LIS
, MachineDominatorTree
&MDT
,
256 UserValueScopes
&UVS
);
258 /// splitRegister - Replace OldReg ranges with NewRegs ranges where NewRegs is
259 /// live. Returns true if any changes were made.
260 bool splitRegister(unsigned OldLocNo
, ArrayRef
<unsigned> NewRegs
,
263 /// rewriteLocations - Rewrite virtual register locations according to the
264 /// provided virtual register map.
265 void rewriteLocations(VirtRegMap
&VRM
, const TargetRegisterInfo
&TRI
);
267 /// emitDebugValues - Recreate DBG_VALUE instruction from data structures.
268 void emitDebugValues(VirtRegMap
*VRM
,
269 LiveIntervals
&LIS
, const TargetInstrInfo
&TRI
);
271 /// findDebugLoc - Return DebugLoc used for this DBG_VALUE instruction. A
272 /// variable may have more than one corresponding DBG_VALUE instructions.
273 /// Only first one needs DebugLoc to identify variable's lexical scope
275 DebugLoc
findDebugLoc();
277 /// getDebugLoc - Return DebugLoc of this UserValue.
278 DebugLoc
getDebugLoc() { return dl
;}
279 void print(raw_ostream
&, const TargetMachine
*);
283 /// LDVImpl - Implementation of the LiveDebugVariables pass.
286 LiveDebugVariables
&pass
;
287 LocMap::Allocator allocator
;
291 MachineDominatorTree
*MDT
;
292 const TargetRegisterInfo
*TRI
;
294 /// Whether emitDebugValues is called.
296 /// Whether the machine function is modified during the pass.
299 /// userValues - All allocated UserValue instances.
300 SmallVector
<std::unique_ptr
<UserValue
>, 8> userValues
;
302 /// Map virtual register to eq class leader.
303 typedef DenseMap
<unsigned, UserValue
*> VRMap
;
304 VRMap virtRegToEqClass
;
306 /// Map user variable to eq class leader.
307 typedef DenseMap
<const MDNode
*, UserValue
*> UVMap
;
310 /// getUserValue - Find or create a UserValue.
311 UserValue
*getUserValue(const MDNode
*Var
, const MDNode
*Expr
,
312 unsigned Offset
, bool IsIndirect
, DebugLoc DL
);
314 /// lookupVirtReg - Find the EC leader for VirtReg or null.
315 UserValue
*lookupVirtReg(unsigned VirtReg
);
317 /// handleDebugValue - Add DBG_VALUE instruction to our maps.
318 /// @param MI DBG_VALUE instruction
319 /// @param Idx Last valid SLotIndex before instruction.
320 /// @return True if the DBG_VALUE instruction should be deleted.
321 bool handleDebugValue(MachineInstr
*MI
, SlotIndex Idx
);
323 /// collectDebugValues - Collect and erase all DBG_VALUE instructions, adding
324 /// a UserValue def for each instruction.
325 /// @param mf MachineFunction to be scanned.
326 /// @return True if any debug values were found.
327 bool collectDebugValues(MachineFunction
&mf
);
329 /// computeIntervals - Compute the live intervals of all user values after
330 /// collecting all their def points.
331 void computeIntervals();
334 LDVImpl(LiveDebugVariables
*ps
)
335 : pass(*ps
), MF(nullptr), EmitDone(false), ModifiedMF(false) {}
336 bool runOnMachineFunction(MachineFunction
&mf
);
338 /// clear - Release all memory.
342 virtRegToEqClass
.clear();
344 // Make sure we call emitDebugValues if the machine function was modified.
345 assert((!ModifiedMF
|| EmitDone
) &&
346 "Dbg values are not emitted in LDV");
352 /// mapVirtReg - Map virtual register to an equivalence class.
353 void mapVirtReg(unsigned VirtReg
, UserValue
*EC
);
355 /// splitRegister - Replace all references to OldReg with NewRegs.
356 void splitRegister(unsigned OldReg
, ArrayRef
<unsigned> NewRegs
);
358 /// emitDebugValues - Recreate DBG_VALUE instruction from data structures.
359 void emitDebugValues(VirtRegMap
*VRM
);
361 void print(raw_ostream
&);
365 void UserValue::print(raw_ostream
&OS
, const TargetMachine
*TM
) {
366 DIVariable
DV(Variable
);
368 DV
.printExtendedName(OS
);
372 for (LocMap::const_iterator I
= locInts
.begin(); I
.valid(); ++I
) {
373 OS
<< " [" << I
.start() << ';' << I
.stop() << "):";
374 if (I
.value() == ~0u)
379 for (unsigned i
= 0, e
= locations
.size(); i
!= e
; ++i
) {
380 OS
<< " Loc" << i
<< '=';
381 locations
[i
].print(OS
, TM
);
386 void LDVImpl::print(raw_ostream
&OS
) {
387 OS
<< "********** DEBUG VARIABLES **********\n";
388 for (unsigned i
= 0, e
= userValues
.size(); i
!= e
; ++i
)
389 userValues
[i
]->print(OS
, &MF
->getTarget());
392 void UserValue::coalesceLocation(unsigned LocNo
) {
393 unsigned KeepLoc
= 0;
394 for (unsigned e
= locations
.size(); KeepLoc
!= e
; ++KeepLoc
) {
395 if (KeepLoc
== LocNo
)
397 if (locations
[KeepLoc
].isIdenticalTo(locations
[LocNo
]))
401 if (KeepLoc
== locations
.size())
404 // Keep the smaller location, erase the larger one.
405 unsigned EraseLoc
= LocNo
;
406 if (KeepLoc
> EraseLoc
)
407 std::swap(KeepLoc
, EraseLoc
);
408 locations
.erase(locations
.begin() + EraseLoc
);
411 for (LocMap::iterator I
= locInts
.begin(); I
.valid(); ++I
) {
412 unsigned v
= I
.value();
414 I
.setValue(KeepLoc
); // Coalesce when possible.
415 else if (v
> EraseLoc
)
416 I
.setValueUnchecked(v
-1); // Avoid coalescing with untransformed values.
420 void UserValue::mapVirtRegs(LDVImpl
*LDV
) {
421 for (unsigned i
= 0, e
= locations
.size(); i
!= e
; ++i
)
422 if (locations
[i
].isReg() &&
423 TargetRegisterInfo::isVirtualRegister(locations
[i
].getReg()))
424 LDV
->mapVirtReg(locations
[i
].getReg(), this);
427 UserValue
*LDVImpl::getUserValue(const MDNode
*Var
, const MDNode
*Expr
,
428 unsigned Offset
, bool IsIndirect
,
430 UserValue
*&Leader
= userVarMap
[Var
];
432 UserValue
*UV
= Leader
->getLeader();
434 for (; UV
; UV
= UV
->getNext())
435 if (UV
->match(Var
, Expr
, Offset
, IsIndirect
))
439 userValues
.push_back(
440 make_unique
<UserValue
>(Var
, Expr
, Offset
, IsIndirect
, DL
, allocator
));
441 UserValue
*UV
= userValues
.back().get();
442 Leader
= UserValue::merge(Leader
, UV
);
446 void LDVImpl::mapVirtReg(unsigned VirtReg
, UserValue
*EC
) {
447 assert(TargetRegisterInfo::isVirtualRegister(VirtReg
) && "Only map VirtRegs");
448 UserValue
*&Leader
= virtRegToEqClass
[VirtReg
];
449 Leader
= UserValue::merge(Leader
, EC
);
452 UserValue
*LDVImpl::lookupVirtReg(unsigned VirtReg
) {
453 if (UserValue
*UV
= virtRegToEqClass
.lookup(VirtReg
))
454 return UV
->getLeader();
458 bool LDVImpl::handleDebugValue(MachineInstr
*MI
, SlotIndex Idx
) {
459 // DBG_VALUE loc, offset, variable
460 if (MI
->getNumOperands() != 4 ||
461 !(MI
->getOperand(1).isReg() || MI
->getOperand(1).isImm()) ||
462 !MI
->getOperand(2).isMetadata()) {
463 DEBUG(dbgs() << "Can't handle " << *MI
);
467 // Get or create the UserValue for (variable,offset).
468 bool IsIndirect
= MI
->isIndirectDebugValue();
469 unsigned Offset
= IsIndirect
? MI
->getOperand(1).getImm() : 0;
470 const MDNode
*Var
= MI
->getDebugVariable();
471 const MDNode
*Expr
= MI
->getDebugExpression();
474 getUserValue(Var
, Expr
, Offset
, IsIndirect
, MI
->getDebugLoc());
475 UV
->addDef(Idx
, MI
->getOperand(0));
479 bool LDVImpl::collectDebugValues(MachineFunction
&mf
) {
480 bool Changed
= false;
481 for (MachineFunction::iterator MFI
= mf
.begin(), MFE
= mf
.end(); MFI
!= MFE
;
483 MachineBasicBlock
*MBB
= MFI
;
484 for (MachineBasicBlock::iterator MBBI
= MBB
->begin(), MBBE
= MBB
->end();
486 if (!MBBI
->isDebugValue()) {
490 // DBG_VALUE has no slot index, use the previous instruction instead.
491 SlotIndex Idx
= MBBI
== MBB
->begin() ?
492 LIS
->getMBBStartIdx(MBB
) :
493 LIS
->getInstructionIndex(std::prev(MBBI
)).getRegSlot();
494 // Handle consecutive DBG_VALUE instructions with the same slot index.
496 if (handleDebugValue(MBBI
, Idx
)) {
497 MBBI
= MBB
->erase(MBBI
);
501 } while (MBBI
!= MBBE
&& MBBI
->isDebugValue());
507 void UserValue::extendDef(SlotIndex Idx
, unsigned LocNo
,
508 LiveRange
*LR
, const VNInfo
*VNI
,
509 SmallVectorImpl
<SlotIndex
> *Kills
,
510 LiveIntervals
&LIS
, MachineDominatorTree
&MDT
,
511 UserValueScopes
&UVS
) {
512 SmallVector
<SlotIndex
, 16> Todo
;
515 SlotIndex Start
= Todo
.pop_back_val();
516 MachineBasicBlock
*MBB
= LIS
.getMBBFromIndex(Start
);
517 SlotIndex Stop
= LIS
.getMBBEndIdx(MBB
);
518 LocMap::iterator I
= locInts
.find(Start
);
520 // Limit to VNI's live range.
523 LiveInterval::Segment
*Segment
= LR
->getSegmentContaining(Start
);
524 if (!Segment
|| Segment
->valno
!= VNI
) {
526 Kills
->push_back(Start
);
529 if (Segment
->end
< Stop
)
530 Stop
= Segment
->end
, ToEnd
= false;
533 // There could already be a short def at Start.
534 if (I
.valid() && I
.start() <= Start
) {
535 // Stop when meeting a different location or an already extended interval.
536 Start
= Start
.getNextSlot();
537 if (I
.value() != LocNo
|| I
.stop() != Start
)
539 // This is a one-slot placeholder. Just skip it.
543 // Limited by the next def.
544 if (I
.valid() && I
.start() < Stop
)
545 Stop
= I
.start(), ToEnd
= false;
546 // Limited by VNI's live range.
547 else if (!ToEnd
&& Kills
)
548 Kills
->push_back(Stop
);
553 I
.insert(Start
, Stop
, LocNo
);
555 // If we extended to the MBB end, propagate down the dominator tree.
558 const std::vector
<MachineDomTreeNode
*> &Children
=
559 MDT
.getNode(MBB
)->getChildren();
560 for (unsigned i
= 0, e
= Children
.size(); i
!= e
; ++i
) {
561 MachineBasicBlock
*MBB
= Children
[i
]->getBlock();
562 if (UVS
.dominates(MBB
))
563 Todo
.push_back(LIS
.getMBBStartIdx(MBB
));
565 } while (!Todo
.empty());
569 UserValue::addDefsFromCopies(LiveInterval
*LI
, unsigned LocNo
,
570 const SmallVectorImpl
<SlotIndex
> &Kills
,
571 SmallVectorImpl
<std::pair
<SlotIndex
, unsigned> > &NewDefs
,
572 MachineRegisterInfo
&MRI
, LiveIntervals
&LIS
) {
575 // Don't track copies from physregs, there are too many uses.
576 if (!TargetRegisterInfo::isVirtualRegister(LI
->reg
))
579 // Collect all the (vreg, valno) pairs that are copies of LI.
580 SmallVector
<std::pair
<LiveInterval
*, const VNInfo
*>, 8> CopyValues
;
581 for (MachineOperand
&MO
: MRI
.use_nodbg_operands(LI
->reg
)) {
582 MachineInstr
*MI
= MO
.getParent();
583 // Copies of the full value.
584 if (MO
.getSubReg() || !MI
->isCopy())
586 unsigned DstReg
= MI
->getOperand(0).getReg();
588 // Don't follow copies to physregs. These are usually setting up call
589 // arguments, and the argument registers are always call clobbered. We are
590 // better off in the source register which could be a callee-saved register,
591 // or it could be spilled.
592 if (!TargetRegisterInfo::isVirtualRegister(DstReg
))
595 // Is LocNo extended to reach this copy? If not, another def may be blocking
596 // it, or we are looking at a wrong value of LI.
597 SlotIndex Idx
= LIS
.getInstructionIndex(MI
);
598 LocMap::iterator I
= locInts
.find(Idx
.getRegSlot(true));
599 if (!I
.valid() || I
.value() != LocNo
)
602 if (!LIS
.hasInterval(DstReg
))
604 LiveInterval
*DstLI
= &LIS
.getInterval(DstReg
);
605 const VNInfo
*DstVNI
= DstLI
->getVNInfoAt(Idx
.getRegSlot());
606 assert(DstVNI
&& DstVNI
->def
== Idx
.getRegSlot() && "Bad copy value");
607 CopyValues
.push_back(std::make_pair(DstLI
, DstVNI
));
610 if (CopyValues
.empty())
613 DEBUG(dbgs() << "Got " << CopyValues
.size() << " copies of " << *LI
<< '\n');
615 // Try to add defs of the copied values for each kill point.
616 for (unsigned i
= 0, e
= Kills
.size(); i
!= e
; ++i
) {
617 SlotIndex Idx
= Kills
[i
];
618 for (unsigned j
= 0, e
= CopyValues
.size(); j
!= e
; ++j
) {
619 LiveInterval
*DstLI
= CopyValues
[j
].first
;
620 const VNInfo
*DstVNI
= CopyValues
[j
].second
;
621 if (DstLI
->getVNInfoAt(Idx
) != DstVNI
)
623 // Check that there isn't already a def at Idx
624 LocMap::iterator I
= locInts
.find(Idx
);
625 if (I
.valid() && I
.start() <= Idx
)
627 DEBUG(dbgs() << "Kill at " << Idx
<< " covered by valno #"
628 << DstVNI
->id
<< " in " << *DstLI
<< '\n');
629 MachineInstr
*CopyMI
= LIS
.getInstructionFromIndex(DstVNI
->def
);
630 assert(CopyMI
&& CopyMI
->isCopy() && "Bad copy value");
631 unsigned LocNo
= getLocationNo(CopyMI
->getOperand(0));
632 I
.insert(Idx
, Idx
.getNextSlot(), LocNo
);
633 NewDefs
.push_back(std::make_pair(Idx
, LocNo
));
640 UserValue::computeIntervals(MachineRegisterInfo
&MRI
,
641 const TargetRegisterInfo
&TRI
,
643 MachineDominatorTree
&MDT
,
644 UserValueScopes
&UVS
) {
645 SmallVector
<std::pair
<SlotIndex
, unsigned>, 16> Defs
;
647 // Collect all defs to be extended (Skipping undefs).
648 for (LocMap::const_iterator I
= locInts
.begin(); I
.valid(); ++I
)
649 if (I
.value() != ~0u)
650 Defs
.push_back(std::make_pair(I
.start(), I
.value()));
652 // Extend all defs, and possibly add new ones along the way.
653 for (unsigned i
= 0; i
!= Defs
.size(); ++i
) {
654 SlotIndex Idx
= Defs
[i
].first
;
655 unsigned LocNo
= Defs
[i
].second
;
656 const MachineOperand
&Loc
= locations
[LocNo
];
659 extendDef(Idx
, LocNo
, nullptr, nullptr, nullptr, LIS
, MDT
, UVS
);
663 // Register locations are constrained to where the register value is live.
664 if (TargetRegisterInfo::isVirtualRegister(Loc
.getReg())) {
665 LiveInterval
*LI
= nullptr;
666 const VNInfo
*VNI
= nullptr;
667 if (LIS
.hasInterval(Loc
.getReg())) {
668 LI
= &LIS
.getInterval(Loc
.getReg());
669 VNI
= LI
->getVNInfoAt(Idx
);
671 SmallVector
<SlotIndex
, 16> Kills
;
672 extendDef(Idx
, LocNo
, LI
, VNI
, &Kills
, LIS
, MDT
, UVS
);
674 addDefsFromCopies(LI
, LocNo
, Kills
, Defs
, MRI
, LIS
);
678 // For physregs, use the live range of the first regunit as a guide.
679 unsigned Unit
= *MCRegUnitIterator(Loc
.getReg(), &TRI
);
680 LiveRange
*LR
= &LIS
.getRegUnit(Unit
);
681 const VNInfo
*VNI
= LR
->getVNInfoAt(Idx
);
682 // Don't track copies from physregs, it is too expensive.
683 extendDef(Idx
, LocNo
, LR
, VNI
, nullptr, LIS
, MDT
, UVS
);
686 // Finally, erase all the undefs.
687 for (LocMap::iterator I
= locInts
.begin(); I
.valid();)
688 if (I
.value() == ~0u)
694 void LDVImpl::computeIntervals() {
695 for (unsigned i
= 0, e
= userValues
.size(); i
!= e
; ++i
) {
696 UserValueScopes
UVS(userValues
[i
]->getDebugLoc(), LS
);
697 userValues
[i
]->computeIntervals(MF
->getRegInfo(), *TRI
, *LIS
, *MDT
, UVS
);
698 userValues
[i
]->mapVirtRegs(this);
702 bool LDVImpl::runOnMachineFunction(MachineFunction
&mf
) {
705 LIS
= &pass
.getAnalysis
<LiveIntervals
>();
706 MDT
= &pass
.getAnalysis
<MachineDominatorTree
>();
707 TRI
= mf
.getSubtarget().getRegisterInfo();
709 DEBUG(dbgs() << "********** COMPUTING LIVE DEBUG VARIABLES: "
710 << mf
.getName() << " **********\n");
712 bool Changed
= collectDebugValues(mf
);
714 DEBUG(print(dbgs()));
715 ModifiedMF
= Changed
;
719 static void removeDebugValues(MachineFunction
&mf
) {
720 for (MachineBasicBlock
&MBB
: mf
) {
721 for (auto MBBI
= MBB
.begin(), MBBE
= MBB
.end(); MBBI
!= MBBE
; ) {
722 if (!MBBI
->isDebugValue()) {
726 MBBI
= MBB
.erase(MBBI
);
731 bool LiveDebugVariables::runOnMachineFunction(MachineFunction
&mf
) {
734 if (!FunctionDIs
.count(mf
.getFunction())) {
735 removeDebugValues(mf
);
739 pImpl
= new LDVImpl(this);
740 return static_cast<LDVImpl
*>(pImpl
)->runOnMachineFunction(mf
);
743 void LiveDebugVariables::releaseMemory() {
745 static_cast<LDVImpl
*>(pImpl
)->clear();
748 LiveDebugVariables::~LiveDebugVariables() {
750 delete static_cast<LDVImpl
*>(pImpl
);
753 //===----------------------------------------------------------------------===//
754 // Live Range Splitting
755 //===----------------------------------------------------------------------===//
758 UserValue::splitLocation(unsigned OldLocNo
, ArrayRef
<unsigned> NewRegs
,
759 LiveIntervals
& LIS
) {
761 dbgs() << "Splitting Loc" << OldLocNo
<< '\t';
762 print(dbgs(), nullptr);
764 bool DidChange
= false;
765 LocMap::iterator LocMapI
;
766 LocMapI
.setMap(locInts
);
767 for (unsigned i
= 0; i
!= NewRegs
.size(); ++i
) {
768 LiveInterval
*LI
= &LIS
.getInterval(NewRegs
[i
]);
772 // Don't allocate the new LocNo until it is needed.
773 unsigned NewLocNo
= ~0u;
775 // Iterate over the overlaps between locInts and LI.
776 LocMapI
.find(LI
->beginIndex());
777 if (!LocMapI
.valid())
779 LiveInterval::iterator LII
= LI
->advanceTo(LI
->begin(), LocMapI
.start());
780 LiveInterval::iterator LIE
= LI
->end();
781 while (LocMapI
.valid() && LII
!= LIE
) {
782 // At this point, we know that LocMapI.stop() > LII->start.
783 LII
= LI
->advanceTo(LII
, LocMapI
.start());
787 // Now LII->end > LocMapI.start(). Do we have an overlap?
788 if (LocMapI
.value() == OldLocNo
&& LII
->start
< LocMapI
.stop()) {
789 // Overlapping correct location. Allocate NewLocNo now.
790 if (NewLocNo
== ~0u) {
791 MachineOperand MO
= MachineOperand::CreateReg(LI
->reg
, false);
792 MO
.setSubReg(locations
[OldLocNo
].getSubReg());
793 NewLocNo
= getLocationNo(MO
);
797 SlotIndex LStart
= LocMapI
.start();
798 SlotIndex LStop
= LocMapI
.stop();
800 // Trim LocMapI down to the LII overlap.
801 if (LStart
< LII
->start
)
802 LocMapI
.setStartUnchecked(LII
->start
);
803 if (LStop
> LII
->end
)
804 LocMapI
.setStopUnchecked(LII
->end
);
806 // Change the value in the overlap. This may trigger coalescing.
807 LocMapI
.setValue(NewLocNo
);
809 // Re-insert any removed OldLocNo ranges.
810 if (LStart
< LocMapI
.start()) {
811 LocMapI
.insert(LStart
, LocMapI
.start(), OldLocNo
);
813 assert(LocMapI
.valid() && "Unexpected coalescing");
815 if (LStop
> LocMapI
.stop()) {
817 LocMapI
.insert(LII
->end
, LStop
, OldLocNo
);
822 // Advance to the next overlap.
823 if (LII
->end
< LocMapI
.stop()) {
826 LocMapI
.advanceTo(LII
->start
);
829 if (!LocMapI
.valid())
831 LII
= LI
->advanceTo(LII
, LocMapI
.start());
836 // Finally, remove any remaining OldLocNo intervals and OldLocNo itself.
837 locations
.erase(locations
.begin() + OldLocNo
);
839 while (LocMapI
.valid()) {
840 unsigned v
= LocMapI
.value();
842 DEBUG(dbgs() << "Erasing [" << LocMapI
.start() << ';'
843 << LocMapI
.stop() << ")\n");
847 LocMapI
.setValueUnchecked(v
-1);
852 DEBUG({dbgs() << "Split result: \t"; print(dbgs(), nullptr);});
857 UserValue::splitRegister(unsigned OldReg
, ArrayRef
<unsigned> NewRegs
,
858 LiveIntervals
&LIS
) {
859 bool DidChange
= false;
860 // Split locations referring to OldReg. Iterate backwards so splitLocation can
861 // safely erase unused locations.
862 for (unsigned i
= locations
.size(); i
; --i
) {
863 unsigned LocNo
= i
-1;
864 const MachineOperand
*Loc
= &locations
[LocNo
];
865 if (!Loc
->isReg() || Loc
->getReg() != OldReg
)
867 DidChange
|= splitLocation(LocNo
, NewRegs
, LIS
);
872 void LDVImpl::splitRegister(unsigned OldReg
, ArrayRef
<unsigned> NewRegs
) {
873 bool DidChange
= false;
874 for (UserValue
*UV
= lookupVirtReg(OldReg
); UV
; UV
= UV
->getNext())
875 DidChange
|= UV
->splitRegister(OldReg
, NewRegs
, *LIS
);
880 // Map all of the new virtual registers.
881 UserValue
*UV
= lookupVirtReg(OldReg
);
882 for (unsigned i
= 0; i
!= NewRegs
.size(); ++i
)
883 mapVirtReg(NewRegs
[i
], UV
);
886 void LiveDebugVariables::
887 splitRegister(unsigned OldReg
, ArrayRef
<unsigned> NewRegs
, LiveIntervals
&LIS
) {
889 static_cast<LDVImpl
*>(pImpl
)->splitRegister(OldReg
, NewRegs
);
893 UserValue::rewriteLocations(VirtRegMap
&VRM
, const TargetRegisterInfo
&TRI
) {
894 // Iterate over locations in reverse makes it easier to handle coalescing.
895 for (unsigned i
= locations
.size(); i
; --i
) {
896 unsigned LocNo
= i
-1;
897 MachineOperand
&Loc
= locations
[LocNo
];
898 // Only virtual registers are rewritten.
899 if (!Loc
.isReg() || !Loc
.getReg() ||
900 !TargetRegisterInfo::isVirtualRegister(Loc
.getReg()))
902 unsigned VirtReg
= Loc
.getReg();
903 if (VRM
.isAssignedReg(VirtReg
) &&
904 TargetRegisterInfo::isPhysicalRegister(VRM
.getPhys(VirtReg
))) {
905 // This can create a %noreg operand in rare cases when the sub-register
906 // index is no longer available. That means the user value is in a
907 // non-existent sub-register, and %noreg is exactly what we want.
908 Loc
.substPhysReg(VRM
.getPhys(VirtReg
), TRI
);
909 } else if (VRM
.getStackSlot(VirtReg
) != VirtRegMap::NO_STACK_SLOT
) {
910 // FIXME: Translate SubIdx to a stackslot offset.
911 Loc
= MachineOperand::CreateFI(VRM
.getStackSlot(VirtReg
));
916 coalesceLocation(LocNo
);
920 /// findInsertLocation - Find an iterator for inserting a DBG_VALUE
922 static MachineBasicBlock::iterator
923 findInsertLocation(MachineBasicBlock
*MBB
, SlotIndex Idx
,
924 LiveIntervals
&LIS
) {
925 SlotIndex Start
= LIS
.getMBBStartIdx(MBB
);
926 Idx
= Idx
.getBaseIndex();
928 // Try to find an insert location by going backwards from Idx.
930 while (!(MI
= LIS
.getInstructionFromIndex(Idx
))) {
931 // We've reached the beginning of MBB.
933 MachineBasicBlock::iterator I
= MBB
->SkipPHIsAndLabels(MBB
->begin());
936 Idx
= Idx
.getPrevIndex();
939 // Don't insert anything after the first terminator, though.
940 return MI
->isTerminator() ? MBB
->getFirstTerminator() :
941 std::next(MachineBasicBlock::iterator(MI
));
944 DebugLoc
UserValue::findDebugLoc() {
949 void UserValue::insertDebugValue(MachineBasicBlock
*MBB
, SlotIndex Idx
,
952 const TargetInstrInfo
&TII
) {
953 MachineBasicBlock::iterator I
= findInsertLocation(MBB
, Idx
, LIS
);
954 MachineOperand
&Loc
= locations
[LocNo
];
955 ++NumInsertedDebugValues
;
958 BuildMI(*MBB
, I
, findDebugLoc(), TII
.get(TargetOpcode::DBG_VALUE
),
959 IsIndirect
, Loc
.getReg(), offset
, Variable
, Expression
);
961 BuildMI(*MBB
, I
, findDebugLoc(), TII
.get(TargetOpcode::DBG_VALUE
))
964 .addMetadata(Variable
)
965 .addMetadata(Expression
);
968 void UserValue::emitDebugValues(VirtRegMap
*VRM
, LiveIntervals
&LIS
,
969 const TargetInstrInfo
&TII
) {
970 MachineFunction::iterator MFEnd
= VRM
->getMachineFunction().end();
972 for (LocMap::const_iterator I
= locInts
.begin(); I
.valid();) {
973 SlotIndex Start
= I
.start();
974 SlotIndex Stop
= I
.stop();
975 unsigned LocNo
= I
.value();
976 DEBUG(dbgs() << "\t[" << Start
<< ';' << Stop
<< "):" << LocNo
);
977 MachineFunction::iterator MBB
= LIS
.getMBBFromIndex(Start
);
978 SlotIndex MBBEnd
= LIS
.getMBBEndIdx(MBB
);
980 DEBUG(dbgs() << " BB#" << MBB
->getNumber() << '-' << MBBEnd
);
981 insertDebugValue(MBB
, Start
, LocNo
, LIS
, TII
);
982 // This interval may span multiple basic blocks.
983 // Insert a DBG_VALUE into each one.
984 while(Stop
> MBBEnd
) {
985 // Move to the next block.
989 MBBEnd
= LIS
.getMBBEndIdx(MBB
);
990 DEBUG(dbgs() << " BB#" << MBB
->getNumber() << '-' << MBBEnd
);
991 insertDebugValue(MBB
, Start
, LocNo
, LIS
, TII
);
993 DEBUG(dbgs() << '\n');
1001 void LDVImpl::emitDebugValues(VirtRegMap
*VRM
) {
1002 DEBUG(dbgs() << "********** EMITTING LIVE DEBUG VARIABLES **********\n");
1005 const TargetInstrInfo
*TII
= MF
->getSubtarget().getInstrInfo();
1006 for (unsigned i
= 0, e
= userValues
.size(); i
!= e
; ++i
) {
1007 DEBUG(userValues
[i
]->print(dbgs(), &MF
->getTarget()));
1008 userValues
[i
]->rewriteLocations(*VRM
, *TRI
);
1009 userValues
[i
]->emitDebugValues(VRM
, *LIS
, *TII
);
1014 void LiveDebugVariables::emitDebugValues(VirtRegMap
*VRM
) {
1016 static_cast<LDVImpl
*>(pImpl
)->emitDebugValues(VRM
);
1019 bool LiveDebugVariables::doInitialization(Module
&M
) {
1020 FunctionDIs
= makeSubprogramMap(M
);
1021 return Pass::doInitialization(M
);
1025 void LiveDebugVariables::dump() {
1027 static_cast<LDVImpl
*>(pImpl
)->print(dbgs());