Line data Source code
1 : //===- LiveIntervals.cpp - Live Interval Analysis -------------------------===//
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 : /// \file This file implements the LiveInterval analysis pass which is used
11 : /// by the Linear Scan Register allocator. This pass linearizes the
12 : /// basic blocks of the function in DFS order and computes live intervals for
13 : /// each virtual and physical register.
14 : //
15 : //===----------------------------------------------------------------------===//
16 :
17 : #include "llvm/CodeGen/LiveIntervals.h"
18 : #include "LiveRangeCalc.h"
19 : #include "llvm/ADT/ArrayRef.h"
20 : #include "llvm/ADT/DepthFirstIterator.h"
21 : #include "llvm/ADT/SmallPtrSet.h"
22 : #include "llvm/ADT/SmallVector.h"
23 : #include "llvm/ADT/iterator_range.h"
24 : #include "llvm/Analysis/AliasAnalysis.h"
25 : #include "llvm/CodeGen/LiveInterval.h"
26 : #include "llvm/CodeGen/LiveVariables.h"
27 : #include "llvm/CodeGen/MachineBasicBlock.h"
28 : #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
29 : #include "llvm/CodeGen/MachineDominators.h"
30 : #include "llvm/CodeGen/MachineFunction.h"
31 : #include "llvm/CodeGen/MachineInstr.h"
32 : #include "llvm/CodeGen/MachineInstrBundle.h"
33 : #include "llvm/CodeGen/MachineOperand.h"
34 : #include "llvm/CodeGen/MachineRegisterInfo.h"
35 : #include "llvm/CodeGen/Passes.h"
36 : #include "llvm/CodeGen/SlotIndexes.h"
37 : #include "llvm/CodeGen/TargetRegisterInfo.h"
38 : #include "llvm/CodeGen/TargetSubtargetInfo.h"
39 : #include "llvm/CodeGen/VirtRegMap.h"
40 : #include "llvm/Config/llvm-config.h"
41 : #include "llvm/MC/LaneBitmask.h"
42 : #include "llvm/MC/MCRegisterInfo.h"
43 : #include "llvm/Pass.h"
44 : #include "llvm/Support/BlockFrequency.h"
45 : #include "llvm/Support/CommandLine.h"
46 : #include "llvm/Support/Compiler.h"
47 : #include "llvm/Support/Debug.h"
48 : #include "llvm/Support/MathExtras.h"
49 : #include "llvm/Support/raw_ostream.h"
50 : #include <algorithm>
51 : #include <cassert>
52 : #include <cstdint>
53 : #include <iterator>
54 : #include <tuple>
55 : #include <utility>
56 :
57 : using namespace llvm;
58 :
59 : #define DEBUG_TYPE "regalloc"
60 :
61 : char LiveIntervals::ID = 0;
62 : char &llvm::LiveIntervalsID = LiveIntervals::ID;
63 85326 : INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals",
64 : "Live Interval Analysis", false, false)
65 85326 : INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
66 85326 : INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
67 85326 : INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
68 877070 : INITIALIZE_PASS_END(LiveIntervals, "liveintervals",
69 : "Live Interval Analysis", false, false)
70 :
71 : #ifndef NDEBUG
72 : static cl::opt<bool> EnablePrecomputePhysRegs(
73 : "precompute-phys-liveness", cl::Hidden,
74 : cl::desc("Eagerly compute live intervals for all physreg units."));
75 : #else
76 : static bool EnablePrecomputePhysRegs = false;
77 : #endif // NDEBUG
78 :
79 : namespace llvm {
80 :
81 : cl::opt<bool> UseSegmentSetForPhysRegs(
82 : "use-segment-set-for-physregs", cl::Hidden, cl::init(true),
83 : cl::desc(
84 : "Use segment set for the computation of the live ranges of physregs."));
85 :
86 : } // end namespace llvm
87 :
88 24384 : void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
89 24384 : AU.setPreservesCFG();
90 : AU.addRequired<AAResultsWrapperPass>();
91 : AU.addPreserved<AAResultsWrapperPass>();
92 : AU.addPreserved<LiveVariables>();
93 24384 : AU.addPreservedID(MachineLoopInfoID);
94 24384 : AU.addRequiredTransitiveID(MachineDominatorsID);
95 : AU.addPreservedID(MachineDominatorsID);
96 : AU.addPreserved<SlotIndexes>();
97 : AU.addRequiredTransitive<SlotIndexes>();
98 24384 : MachineFunctionPass::getAnalysisUsage(AU);
99 24384 : }
100 :
101 24384 : LiveIntervals::LiveIntervals() : MachineFunctionPass(ID) {
102 24384 : initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
103 24384 : }
104 :
105 48440 : LiveIntervals::~LiveIntervals() {
106 24220 : delete LRCalc;
107 48440 : }
108 24220 :
109 : void LiveIntervals::releaseMemory() {
110 24220 : // Free the live intervals themselves.
111 24220 : for (unsigned i = 0, e = VirtRegIntervals.size(); i != e; ++i)
112 24220 : delete VirtRegIntervals[TargetRegisterInfo::index2VirtReg(i)];
113 24220 : VirtRegIntervals.clear();
114 : RegMaskSlots.clear();
115 232032 : RegMaskBits.clear();
116 : RegMaskBlocks.clear();
117 4118562 :
118 5866568 : for (LiveRange *LR : RegUnitRanges)
119 : delete LR;
120 : RegUnitRanges.clear();
121 :
122 : // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.
123 : VNInfoAllocator.Reset();
124 49456827 : }
125 49224795 :
126 : bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
127 : MF = &fn;
128 : MRI = &MF->getRegInfo();
129 232032 : TRI = MF->getSubtarget().getRegisterInfo();
130 232032 : TII = MF->getSubtarget().getInstrInfo();
131 : AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
132 232017 : Indexes = &getAnalysis<SlotIndexes>();
133 232017 : DomTree = &getAnalysis<MachineDominatorTree>();
134 232017 :
135 232017 : if (!LRCalc)
136 232017 : LRCalc = new LiveRangeCalc();
137 232017 :
138 232017 : // Allocate space for all virtual registers.
139 232017 : VirtRegIntervals.resize(MRI->getNumVirtRegs());
140 :
141 232017 : computeVirtRegs();
142 23516 : computeRegMasks();
143 : computeLiveInRegUnits();
144 :
145 464034 : if (EnablePrecomputePhysRegs) {
146 : // For stress testing, precompute live ranges of all physical register
147 232017 : // units, including reserved registers.
148 232017 : for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i)
149 232017 : getRegUnit(i);
150 : }
151 232017 : LLVM_DEBUG(dump());
152 : return true;
153 : }
154 0 :
155 0 : void LiveIntervals::print(raw_ostream &OS, const Module* ) const {
156 : OS << "********** INTERVALS **********\n";
157 :
158 232017 : // Dump the regunits.
159 : for (unsigned Unit = 0, UnitE = RegUnitRanges.size(); Unit != UnitE; ++Unit)
160 : if (LiveRange *LR = RegUnitRanges[Unit])
161 2 : OS << printRegUnit(Unit, TRI) << ' ' << *LR << '\n';
162 2 :
163 : // Dump the virtregs.
164 : for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
165 256 : unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
166 508 : if (hasInterval(Reg))
167 0 : OS << getInterval(Reg) << '\n';
168 : }
169 :
170 8 : OS << "RegMasks:";
171 : for (SlotIndex Idx : RegMaskSlots)
172 : OS << ' ' << Idx;
173 : OS << '\n';
174 :
175 : printInstrs(OS);
176 2 : }
177 2 :
178 0 : void LiveIntervals::printInstrs(raw_ostream &OS) const {
179 : OS << "********** MACHINEINSTRS **********\n";
180 : MF->print(OS, Indexes);
181 2 : }
182 2 :
183 : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
184 2 : LLVM_DUMP_METHOD void LiveIntervals::dumpInstrs() const {
185 2 : printInstrs(dbgs());
186 2 : }
187 2 : #endif
188 :
189 : LiveInterval* LiveIntervals::createInterval(unsigned reg) {
190 : float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? huge_valf : 0.0F;
191 : return new LiveInterval(reg, Weight);
192 : }
193 :
194 : /// Compute the live interval of a virtual register, based on defs and uses.
195 2866979 : void LiveIntervals::computeVirtRegInterval(LiveInterval &LI) {
196 2866979 : assert(LRCalc && "LRCalc not initialized.");
197 2866979 : assert(LI.empty() && "Should only compute empty intervals.");
198 : LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
199 : LRCalc->calculate(LI, MRI->shouldTrackSubRegLiveness(LI.reg));
200 : computeDeadValues(LI, nullptr);
201 2778645 : }
202 :
203 : void LiveIntervals::computeVirtRegs() {
204 5557290 : for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
205 5557288 : unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
206 2778645 : if (MRI->reg_nodbg_empty(Reg))
207 2778645 : continue;
208 : createAndComputeVirtRegInterval(Reg);
209 232016 : }
210 3986939 : }
211 :
212 3754922 : void LiveIntervals::computeRegMasks() {
213 : RegMaskBlocks.resize(MF->getNumBlockIDs());
214 :
215 : // Find all instructions with regmask operands.
216 232017 : for (const MachineBasicBlock &MBB : *MF) {
217 : std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB.getNumber()];
218 232017 : RMB.first = RegMaskSlots.size();
219 464034 :
220 : // Some block starts, such as EH funclets, create masks.
221 : if (const uint32_t *Mask = MBB.getBeginClobberMask(TRI)) {
222 738247 : RegMaskSlots.push_back(Indexes->getMBBStartIdx(&MBB));
223 506230 : RegMaskBits.push_back(Mask);
224 506230 : }
225 :
226 : for (const MachineInstr &MI : MBB) {
227 506230 : for (const MachineOperand &MO : MI.operands()) {
228 236 : if (!MO.isRegMask())
229 118 : continue;
230 : RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot());
231 : RegMaskBits.push_back(MO.getRegMask());
232 6087629 : }
233 27092933 : }
234 21511533 :
235 : // Some block ends, such as funclet returns, create masks. Put the mask on
236 140640 : // the last instruction of the block, because MBB slot index intervals are
237 140640 : // half-open.
238 : if (const uint32_t *Mask = MBB.getEndClobberMask(TRI)) {
239 : assert(!MBB.empty() && "empty return block?");
240 : RegMaskSlots.push_back(
241 : Indexes->getInstructionIndex(MBB.back()).getRegSlot());
242 : RegMaskBits.push_back(Mask);
243 : }
244 506230 :
245 : // Compute the number of register mask instructions in this block.
246 146 : RMB.second = RegMaskSlots.size() - RMB.first;
247 73 : }
248 73 : }
249 :
250 : //===----------------------------------------------------------------------===//
251 : // Register Unit Liveness
252 506230 : //===----------------------------------------------------------------------===//
253 : //
254 232017 : // Fixed interference typically comes from ABI boundaries: Function arguments
255 : // and return values are passed in fixed registers, and so are exception
256 : // pointers entering landing pads. Certain instructions require values to be
257 : // present in specific registers. That is also represented through fixed
258 : // interference.
259 : //
260 :
261 : /// Compute the live range of a register unit, based on the uses and defs of
262 : /// aliasing registers. The range should be empty, or contain only dead
263 : /// phi-defs from ABI blocks.
264 : void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) {
265 : assert(LRCalc && "LRCalc not initialized.");
266 : LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
267 :
268 : // The physregs aliasing Unit are the roots and their super-registers.
269 : // Create all values as dead defs before extending to uses. Note that roots
270 1317458 : // may share super-registers. That's OK because createDeadDefs() is
271 : // idempotent. It is very rare for a register unit to have multiple roots, so
272 2634916 : // uniquing super-registers is probably not worthwhile.
273 : bool IsReserved = false;
274 : for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) {
275 : bool IsRootReserved = true;
276 : for (MCSuperRegIterator Super(*Root, TRI, /*IncludeSelf=*/true);
277 : Super.isValid(); ++Super) {
278 : unsigned Reg = *Super;
279 : if (!MRI->reg_empty(Reg))
280 3953190 : LRCalc->createDeadDefs(LR, Reg);
281 : // A register unit is considered reserved if all its roots and all their
282 1318274 : // super registers are reserved.
283 8411559 : if (!MRI->isReserved(Reg))
284 : IsRootReserved = false;
285 14186570 : }
286 797480 : IsReserved |= IsRootReserved;
287 : }
288 : assert(IsReserved == MRI->isReservedRegUnit(Unit) &&
289 14186570 : "reserved computation mismatch");
290 :
291 : // Now extend LR to reach all uses.
292 1318274 : // Ignore uses of reserved registers. We only track defs of those.
293 : if (!IsReserved) {
294 : for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) {
295 : for (MCSuperRegIterator Super(*Root, TRI, /*IncludeSelf=*/true);
296 : Super.isValid(); ++Super) {
297 : unsigned Reg = *Super;
298 : if (!MRI->reg_empty(Reg))
299 1317458 : LRCalc->extendToUses(LR, Reg);
300 3922443 : }
301 1307597 : }
302 8366746 : }
303 :
304 14118298 : // Flush the segment set to the segment vector.
305 788034 : if (UseSegmentSetForPhysRegs)
306 : LR.flushSegmentSet();
307 : }
308 :
309 : /// Precompute the live ranges of any register units that are live-in to an ABI
310 : /// block somewhere. Register values can appear without a corresponding def when
311 1317458 : /// entering the entry block or a landing pad.
312 1317458 : void LiveIntervals::computeLiveInRegUnits() {
313 1317458 : RegUnitRanges.resize(TRI->getNumRegUnits());
314 : LLVM_DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n");
315 :
316 : // Keep track of the live range sets allocated.
317 : SmallVector<unsigned, 8> NewRanges;
318 232016 :
319 232016 : // Check all basic blocks for live-ins.
320 : for (const MachineBasicBlock &MBB : *MF) {
321 : // We only care about ABI blocks: Entry + landing pads.
322 : if ((&MBB != &MF->front() && !MBB.isEHPad()) || MBB.livein_empty())
323 : continue;
324 :
325 : // Create phi-defs at Begin for all live-in registers.
326 738247 : SlotIndex Begin = Indexes->getMBBStartIdx(&MBB);
327 : LLVM_DEBUG(dbgs() << Begin << "\t" << printMBBReference(MBB));
328 1012460 : for (const auto &LI : MBB.liveins()) {
329 277022 : for (MCRegUnitIterator Units(LI.PhysReg, TRI); Units.isValid(); ++Units) {
330 : unsigned Unit = *Units;
331 : LiveRange *LR = RegUnitRanges[Unit];
332 458416 : if (!LR) {
333 : // Use segment set to speed-up initial computation of the live range.
334 692432 : LR = RegUnitRanges[Unit] = new LiveRange(UseSegmentSetForPhysRegs);
335 1253894 : NewRanges.push_back(Unit);
336 790670 : }
337 790670 : VNInfo *VNI = LR->createDeadDef(Begin, getVNInfoAllocator());
338 790670 : (void)VNI;
339 : LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << '#' << VNI->id);
340 585616 : }
341 585616 : }
342 : LLVM_DEBUG(dbgs() << '\n');
343 790670 : }
344 : LLVM_DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n");
345 :
346 : // Compute the 'normal' part of the ranges.
347 : for (unsigned Unit : NewRanges)
348 : computeRegUnitRange(*RegUnitRanges[Unit], Unit);
349 : }
350 :
351 : static void createSegmentsForValues(LiveRange &LR,
352 : iterator_range<LiveInterval::vni_iterator> VNIs) {
353 817633 : for (VNInfo *VNI : VNIs) {
354 1171232 : if (VNI->isUnused())
355 232017 : continue;
356 : SlotIndex Def = VNI->def;
357 50282 : LR.addSegment(LiveRange::Segment(Def, Def.getDeadSlot(), VNI));
358 : }
359 116717 : }
360 66435 :
361 : void LiveIntervals::extendSegmentsToUses(LiveRange &Segments,
362 : ShrinkToUsesWorkList &WorkList,
363 65742 : unsigned Reg, LaneBitmask LaneMask) {
364 : // Keep track of the PHIs that are in use.
365 50282 : SmallPtrSet<VNInfo*, 8> UsedPHIs;
366 : // Blocks that have already been added to WorkList as live-out.
367 50282 : SmallPtrSet<const MachineBasicBlock*, 16> LiveOut;
368 :
369 : auto getSubRange = [](const LiveInterval &I, LaneBitmask M)
370 : -> const LiveRange& {
371 : if (M.none())
372 : return I;
373 : for (const LiveInterval::SubRange &SR : I.subranges()) {
374 : if ((SR.LaneMask & M).any()) {
375 : assert(SR.LaneMask == M && "Expecting lane masks to match exactly");
376 : return SR;
377 50282 : }
378 49938 : }
379 652 : llvm_unreachable("Subrange for mask not found");
380 1304 : };
381 :
382 344 : const LiveInterval &LI = getInterval(Reg);
383 : const LiveRange &OldRange = getSubRange(LI, LaneMask);
384 :
385 0 : // Extend intervals to reach all uses in WorkList.
386 : while (!WorkList.empty()) {
387 : SlotIndex Idx = WorkList.back().first;
388 50282 : VNInfo *VNI = WorkList.back().second;
389 : WorkList.pop_back();
390 : const MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Idx.getPrevSlot());
391 : SlotIndex BlockStart = Indexes->getMBBStartIdx(MBB);
392 342935 :
393 292653 : // Extend the live range for VNI to be live at Idx.
394 292653 : if (VNInfo *ExtVNI = Segments.extendInBlock(BlockStart, Idx)) {
395 292653 : assert(ExtVNI == VNI && "Unexpected existing value number");
396 585306 : (void)ExtVNI;
397 292653 : // Is this a PHIDef we haven't seen before?
398 : if (!VNI->isPHIDef() || VNI->def != BlockStart ||
399 : !UsedPHIs.insert(VNI).second)
400 292653 : continue;
401 : // The PHI is live, make sure the predecessors are live-out.
402 : for (const MachineBasicBlock *Pred : MBB->predecessors()) {
403 : if (!LiveOut.insert(Pred).second)
404 97487 : continue;
405 7340 : SlotIndex Stop = Indexes->getMBBEndIdx(Pred);
406 92112 : // A predecessor is not required to have a live-out value for a PHI.
407 : if (VNInfo *PVNI = OldRange.getVNInfoBefore(Stop))
408 18447 : WorkList.push_back(std::make_pair(Stop, PVNI));
409 13072 : }
410 : continue;
411 12284 : }
412 :
413 12284 : // VNI is live-in to MBB.
414 12274 : LLVM_DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
415 : Segments.addSegment(LiveRange::Segment(BlockStart, Idx, VNI));
416 :
417 : // Make sure VNI is live-out from the predecessors.
418 : for (const MachineBasicBlock *Pred : MBB->predecessors()) {
419 : if (!LiveOut.insert(Pred).second)
420 : continue;
421 195166 : SlotIndex Stop = Indexes->getMBBEndIdx(Pred);
422 : if (VNInfo *OldVNI = OldRange.getVNInfoBefore(Stop)) {
423 : assert(OldVNI == VNI && "Wrong value out of predecessor");
424 454116 : (void)OldVNI;
425 258950 : WorkList.push_back(std::make_pair(Stop, VNI));
426 : } else {
427 193250 : #ifndef NDEBUG
428 193250 : // There was no old VNI. Verify that Stop is jointly dominated
429 : // by <undef>s for this live range.
430 : assert(LaneMask.any() &&
431 193249 : "Missing value out of predecessor for main range");
432 : SmallVector<SlotIndex,8> Undefs;
433 : LI.computeSubRangeUndefs(Undefs, LaneMask, *MRI, *Indexes);
434 : assert(LiveRangeCalc::isJointlyDominated(Pred, Undefs, *Indexes) &&
435 : "Missing value out of predecessor for subrange");
436 : #endif
437 : }
438 : }
439 : }
440 : }
441 :
442 : bool LiveIntervals::shrinkToUses(LiveInterval *li,
443 : SmallVectorImpl<MachineInstr*> *dead) {
444 : LLVM_DEBUG(dbgs() << "Shrink: " << *li << '\n');
445 : assert(TargetRegisterInfo::isVirtualRegister(li->reg)
446 50282 : && "Can only shrink virtual registers");
447 :
448 49938 : // Shrink subregister live ranges.
449 : bool NeedsCleanup = false;
450 : for (LiveInterval::SubRange &S : li->subranges()) {
451 : shrinkToUses(S, li->reg);
452 : if (S.empty())
453 : NeedsCleanup = true;
454 : }
455 : if (NeedsCleanup)
456 50178 : li->removeEmptySubRanges();
457 240 :
458 240 : // Find all the values used, including PHI kills.
459 : ShrinkToUsesWorkList WorkList;
460 :
461 49938 : // Visit all instructions reading li->reg.
462 1 : unsigned Reg = li->reg;
463 : for (MachineInstr &UseMI : MRI->reg_instructions(Reg)) {
464 : if (UseMI.isDebugValue() || !UseMI.readsVirtualRegister(Reg))
465 : continue;
466 : SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot();
467 : LiveQueryResult LRQ = li->Query(Idx);
468 49938 : VNInfo *VNI = LRQ.valueIn();
469 243005 : if (!VNI) {
470 284534 : // This shouldn't happen: readsVirtualRegister returns true, but there is
471 56459 : // no live value. It is likely caused by a target getting <undef> flags
472 86672 : // wrong.
473 86672 : LLVM_DEBUG(
474 : dbgs() << Idx << '\t' << UseMI
475 86672 : << "Warning: Instr claims to read non-existent value in "
476 : << *li << '\n');
477 : continue;
478 : }
479 : // Special case: An early-clobber tied operand reads and writes the
480 : // register one slot early.
481 : if (VNInfo *DefVNI = LRQ.valueDefined())
482 : Idx = DefVNI->def;
483 :
484 : WorkList.push_back(std::make_pair(Idx, VNI));
485 : }
486 :
487 86670 : // Create new live ranges with only minimal live segments per def.
488 8751 : LiveRange NewLR;
489 : createSegmentsForValues(NewLR, make_range(li->vni_begin(), li->vni_end()));
490 86670 : extendSegmentsToUses(NewLR, WorkList, Reg, LaneBitmask::getNone());
491 :
492 : // Move the trimmed segments back.
493 : li->segments.swap(NewLR.segments);
494 99876 :
495 49938 : // Handle dead values.
496 49938 : bool CanSeparate = computeDeadValues(*li, dead);
497 : LLVM_DEBUG(dbgs() << "Shrunk: " << *li << '\n');
498 : return CanSeparate;
499 49938 : }
500 :
501 : bool LiveIntervals::computeDeadValues(LiveInterval &LI,
502 49938 : SmallVectorImpl<MachineInstr*> *dead) {
503 : bool MayHaveSplitComponents = false;
504 49938 : for (VNInfo *VNI : LI.valnos) {
505 : if (VNI->isUnused())
506 : continue;
507 2828583 : SlotIndex Def = VNI->def;
508 : LiveRange::iterator I = LI.FindSegmentContaining(Def);
509 : assert(I != LI.end() && "Missing segment for VNI");
510 6236318 :
511 3407735 : // Is the register live before? Otherwise we may have to add a read-undef
512 : // flag for subregister defs.
513 : unsigned VReg = LI.reg;
514 3407192 : if (MRI->shouldTrackSubRegLiveness(VReg)) {
515 : if ((I == LI.begin() || std::prev(I)->end < Def) && !VNI->isPHIDef()) {
516 : MachineInstr *MI = getInstructionFromIndex(Def);
517 : MI->setRegisterDefReadUndef(VReg);
518 : }
519 3407192 : }
520 3407192 :
521 369004 : if (I->end != Def.getDeadSlot())
522 : continue;
523 270541 : if (VNI->isPHIDef()) {
524 : // This is a dead PHI. Remove it.
525 : VNI->markUnused();
526 : LI.removeSegment(I);
527 3407192 : LLVM_DEBUG(dbgs() << "Dead PHI at " << Def << " may separate interval\n");
528 : MayHaveSplitComponents = true;
529 63055 : } else {
530 : // This is a dead def. Make sure the instruction knows.
531 : MachineInstr *MI = getInstructionFromIndex(Def);
532 : assert(MI && "No instruction defining live value");
533 : MI->addRegisterDead(LI.reg, TRI);
534 : if (dead && MI->allDefsAreDead()) {
535 : LLVM_DEBUG(dbgs() << "All defs dead: " << Def << '\t' << *MI);
536 : dead->push_back(MI);
537 62733 : }
538 : }
539 62733 : }
540 62733 : return MayHaveSplitComponents;
541 : }
542 30372 :
543 : void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg) {
544 : LLVM_DEBUG(dbgs() << "Shrink: " << SR << '\n');
545 : assert(TargetRegisterInfo::isVirtualRegister(Reg)
546 2828583 : && "Can only shrink virtual registers");
547 : // Find all the values used, including PHI kills.
548 : ShrinkToUsesWorkList WorkList;
549 344 :
550 : // Visit all instructions reading Reg.
551 : SlotIndex LastIdx;
552 : for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
553 : // Skip "undef" uses.
554 : if (!MO.readsReg())
555 : continue;
556 : // Maybe the operand is for a subregister we don't care about.
557 : unsigned SubReg = MO.getSubReg();
558 1665 : if (SubReg != 0) {
559 : LaneBitmask LaneMask = TRI->getSubRegIndexLaneMask(SubReg);
560 : if ((LaneMask & SR.LaneMask).none())
561 517 : continue;
562 : }
563 : // We only need to visit each instruction once.
564 971 : MachineInstr *UseMI = MO.getParent();
565 814 : SlotIndex Idx = getInstructionIndex(*UseMI).getRegSlot();
566 814 : if (Idx == LastIdx)
567 : continue;
568 : LastIdx = Idx;
569 :
570 500 : LiveQueryResult LRQ = SR.Query(Idx);
571 500 : VNInfo *VNI = LRQ.valueIn();
572 500 : // For Subranges it is possible that only undef values are left in that
573 : // part of the subregister, so there is no real liverange at the use
574 : if (!VNI)
575 : continue;
576 468 :
577 : // Special case: An early-clobber tied operand reads and writes the
578 : // register one slot early.
579 : if (VNInfo *DefVNI = LRQ.valueDefined())
580 468 : Idx = DefVNI->def;
581 :
582 : WorkList.push_back(std::make_pair(Idx, VNI));
583 : }
584 :
585 460 : // Create a new live ranges with only minimal live segments per def.
586 56 : LiveRange NewLR;
587 : createSegmentsForValues(NewLR, make_range(SR.vni_begin(), SR.vni_end()));
588 460 : extendSegmentsToUses(NewLR, WorkList, Reg, SR.LaneMask);
589 :
590 : // Move the trimmed ranges back.
591 : SR.segments.swap(NewLR.segments);
592 688 :
593 344 : // Remove dead PHI value numbers
594 344 : for (VNInfo *VNI : SR.valnos) {
595 : if (VNI->isUnused())
596 : continue;
597 344 : const LiveRange::Segment *Segment = SR.getSegmentContaining(VNI->def);
598 : assert(Segment != nullptr && "Missing segment for VNI");
599 : if (Segment->end != VNI->def.getDeadSlot())
600 1282 : continue;
601 938 : if (VNI->isPHIDef()) {
602 : // This is a dead PHI. Remove it.
603 1576 : LLVM_DEBUG(dbgs() << "Dead PHI at " << VNI->def
604 : << " may separate interval\n");
605 788 : VNI->markUnused();
606 : SR.removeSegment(*Segment);
607 215 : }
608 : }
609 :
610 : LLVM_DEBUG(dbgs() << "Shrunk: " << SR << '\n');
611 : }
612 56 :
613 : void LiveIntervals::extendToIndices(LiveRange &LR,
614 : ArrayRef<SlotIndex> Indices,
615 : ArrayRef<SlotIndex> Undefs) {
616 : assert(LRCalc && "LRCalc not initialized.");
617 344 : LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
618 : for (SlotIndex Idx : Indices)
619 67929 : LRCalc->extend(LR, Idx, /*PhysReg=*/0, Undefs);
620 : }
621 :
622 : void LiveIntervals::pruneValue(LiveRange &LR, SlotIndex Kill,
623 135858 : SmallVectorImpl<SlotIndex> *EndPoints) {
624 303684 : LiveQueryResult LRQ = LR.Query(Kill);
625 235755 : VNInfo *VNI = LRQ.valueOutOrDead();
626 67929 : if (!VNI)
627 : return;
628 159162 :
629 : MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill);
630 159162 : SlotIndex MBBEnd = Indexes->getMBBEndIdx(KillMBB);
631 159162 :
632 159162 : // If VNI isn't live out from KillMBB, the value is trivially pruned.
633 158064 : if (LRQ.endPoint() < MBBEnd) {
634 : LR.removeSegment(Kill, LRQ.endPoint());
635 116060 : if (EndPoints) EndPoints->push_back(LRQ.endPoint());
636 232120 : return;
637 : }
638 :
639 116060 : // VNI is live out of KillMBB.
640 114962 : LR.removeSegment(Kill, MBBEnd);
641 114962 : if (EndPoints) EndPoints->push_back(MBBEnd);
642 114962 :
643 : // Find all blocks that are reachable from KillMBB without leaving VNI's live
644 : // range. It is possible that KillMBB itself is reachable, so start a DFS
645 : // from each successor.
646 1098 : using VisitedTy = df_iterator_default_set<MachineBasicBlock*,9>;
647 1098 : VisitedTy Visited;
648 : for (MachineBasicBlock *Succ : KillMBB->successors()) {
649 : for (df_ext_iterator<MachineBasicBlock*, VisitedTy>
650 : I = df_ext_begin(Succ, Visited), E = df_ext_end(Succ, Visited);
651 : I != E;) {
652 : MachineBasicBlock *MBB = *I;
653 :
654 2787 : // Check if VNI is live in to MBB.
655 : SlotIndex MBBStart, MBBEnd;
656 1689 : std::tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB);
657 5619 : LiveQueryResult LRQ = LR.Query(MBBStart);
658 3930 : if (LRQ.valueIn() != VNI) {
659 : // This block isn't part of the VNI segment. Prune the search.
660 : I.skipChildren();
661 3930 : continue;
662 3930 : }
663 3930 :
664 3930 : // Prune the search if VNI is killed in MBB.
665 : if (LRQ.endPoint() < MBBEnd) {
666 : LR.removeSegment(MBBStart, LRQ.endPoint());
667 1892 : if (EndPoints) EndPoints->push_back(LRQ.endPoint());
668 : I.skipChildren();
669 : continue;
670 : }
671 2571 :
672 533 : // VNI is live through MBB.
673 533 : LR.removeSegment(MBBStart, MBBEnd);
674 : if (EndPoints) EndPoints->push_back(MBBEnd);
675 533 : ++I;
676 : }
677 : }
678 : }
679 2038 :
680 2038 : //===----------------------------------------------------------------------===//
681 : // Register allocator hooks.
682 : //
683 :
684 : void LiveIntervals::addKillFlags(const VirtRegMap *VRM) {
685 : // Keep track of regunit ranges.
686 : SmallVector<std::pair<const LiveRange*, LiveRange::const_iterator>, 8> RU;
687 : // Keep track of subregister ranges.
688 : SmallVector<std::pair<const LiveInterval::SubRange*,
689 : LiveRange::const_iterator>, 4> SRs;
690 193975 :
691 : for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
692 : unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
693 : if (MRI->reg_nodbg_empty(Reg))
694 : continue;
695 : const LiveInterval &LI = getInterval(Reg);
696 : if (LI.empty())
697 3196578 : continue;
698 :
699 3002603 : // Find the regunit intervals for the assigned register. They may overlap
700 : // the virtual register live range, cancelling any kills.
701 1407663 : RU.clear();
702 1407663 : for (MCRegUnitIterator Unit(VRM->getPhys(Reg), TRI); Unit.isValid();
703 : ++Unit) {
704 : const LiveRange &RURange = getRegUnit(*Unit);
705 : if (RURange.empty())
706 : continue;
707 : RU.push_back(std::make_pair(&RURange, RURange.find(LI.begin()->end)));
708 5194643 : }
709 :
710 2393531 : if (MRI->subRegLivenessEnabled()) {
711 2393531 : SRs.clear();
712 : for (const LiveInterval::SubRange &SR : LI.subranges()) {
713 1360969 : SRs.push_back(std::make_pair(&SR, SR.find(LI.begin()->end)));
714 : }
715 : }
716 1400556 :
717 : // Every instruction that kills Reg corresponds to a segment range end
718 465373 : // point.
719 198992 : for (LiveInterval::const_iterator RI = LI.begin(), RE = LI.end(); RI != RE;
720 : ++RI) {
721 : // A block index indicates an MBB edge.
722 : if (RI->end.isBlock())
723 : continue;
724 : MachineInstr *MI = getInstructionFromIndex(RI->end);
725 3458012 : if (!MI)
726 : continue;
727 :
728 2057456 : // Check if any of the regunits are live beyond the end of RI. That could
729 : // happen when a physreg is defined as a copy of a virtreg:
730 : //
731 1757844 : // %eax = COPY %5
732 : // FOO %5 <--- MI, cancel kill because %eax is live.
733 : // BAR killed %eax
734 : //
735 : // There should be no kill flag on FOO when %5 is rewritten as %eax.
736 : for (auto &RUP : RU) {
737 : const LiveRange &RURange = *RUP.first;
738 : LiveRange::const_iterator &I = RUP.second;
739 : if (I == RURange.end())
740 : continue;
741 : I = RURange.advanceTo(I, RI->end);
742 3371903 : if (I == RURange.end() || I->start >= RI->end)
743 1624334 : continue;
744 : // I is overlapping RI.
745 3248668 : goto CancelKill;
746 : }
747 1084121 :
748 1084121 : if (MRI->subRegLivenessEnabled()) {
749 : // When reading a partial undefined value we must not add a kill flag.
750 : // The regalloc might have used the undef lane for something else.
751 : // Example:
752 : // %1 = ... ; R32: %1
753 : // %2:high16 = ... ; R64: %2
754 1747569 : // = read killed %2 ; R64: %2
755 : // = read %1 ; R32: %1
756 : // The <kill> flag is correct for %2, but the register allocator may
757 : // assign R0L to %1, and R0 to %2 because the low 32bits of R0
758 : // are actually never written by %2. After assignment the <kill>
759 : // flag at the read instruction is invalid.
760 : LaneBitmask DefinedLanesMask;
761 : if (!SRs.empty()) {
762 : // Compute a mask of lanes that are defined.
763 : DefinedLanesMask = LaneBitmask::getNone();
764 : for (auto &SRP : SRs) {
765 : const LiveInterval::SubRange &SR = *SRP.first;
766 : LiveRange::const_iterator &I = SRP.second;
767 343105 : if (I == SR.end())
768 : continue;
769 : I = SR.advanceTo(I, RI->end);
770 593969 : if (I == SR.end() || I->start >= RI->end)
771 456036 : continue;
772 : // I is overlapping RI
773 912072 : DefinedLanesMask |= SR.LaneMask;
774 : }
775 387663 : } else
776 387663 : DefinedLanesMask = LaneBitmask::getAll();
777 :
778 : bool IsFullWrite = false;
779 : for (const MachineOperand &MO : MI->operands()) {
780 : if (!MO.isReg() || MO.getReg() != Reg)
781 : continue;
782 : if (MO.isUse()) {
783 : // Reading any undefined lanes?
784 : LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(MO.getSubReg());
785 2152546 : if ((UseMask & ~DefinedLanesMask).any())
786 1874026 : goto CancelKill;
787 : } else if (MO.getSubReg() == 0) {
788 353830 : // Writing to the full register?
789 : assert(MO.isDef());
790 537596 : IsFullWrite = true;
791 268798 : }
792 : }
793 85032 :
794 : // If an instruction writes to a subregister, a new segment starts in
795 : // the LiveInterval. But as this is only overriding part of the register
796 : // adding kill-flags is not correct here after registers have been
797 : // assigned.
798 : if (!IsFullWrite) {
799 : // Next segment has to be adjacent in the subregister write case.
800 : LiveRange::const_iterator N = std::next(RI);
801 : if (N != LI.end() && N->start == RI->end)
802 : goto CancelKill;
803 : }
804 278520 : }
805 :
806 : MI->addRegisterKilled(Reg, nullptr);
807 268055 : continue;
808 : CancelKill:
809 : MI->clearRegisterKills(Reg, nullptr);
810 : }
811 : }
812 1609637 : }
813 1609637 :
814 148207 : MachineBasicBlock*
815 148207 : LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const {
816 : // A local live range must be fully contained inside the block, meaning it is
817 : // defined and killed at instructions, not at block boundaries. It is not
818 193975 : // live in or out of any block.
819 : //
820 : // It is technically possible to have a PHI-defined live range identical to a
821 6332634 : // single block, but we are going to return false in that case.
822 :
823 : SlotIndex Start = LI.beginIndex();
824 : if (Start.isBlock())
825 : return nullptr;
826 :
827 : SlotIndex Stop = LI.endIndex();
828 : if (Stop.isBlock())
829 : return nullptr;
830 6332634 :
831 : // getMBBFromIndex doesn't need to search the MBB table when both indexes
832 : // belong to proper instructions.
833 : MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start);
834 6328945 : MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop);
835 : return MBB1 == MBB2 ? MBB1 : nullptr;
836 : }
837 :
838 : bool
839 6045433 : LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const {
840 6045433 : for (const VNInfo *PHI : LI.valnos) {
841 6045433 : if (PHI->isUnused() || !PHI->isPHIDef())
842 : continue;
843 : const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def);
844 : // Conservatively return true instead of scanning huge predecessor lists.
845 105 : if (PHIMBB->pred_size() > 100)
846 697 : return true;
847 596 : for (const MachineBasicBlock *Pred : PHIMBB->predecessors())
848 : if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(Pred)))
849 61 : return true;
850 : }
851 61 : return false;
852 : }
853 182 :
854 250 : float LiveIntervals::getSpillWeight(bool isDef, bool isUse,
855 : const MachineBlockFrequencyInfo *MBFI,
856 : const MachineInstr &MI) {
857 : return getSpillWeight(isDef, isUse, MBFI, MI.getParent());
858 : }
859 :
860 4670724 : float LiveIntervals::getSpillWeight(bool isDef, bool isUse,
861 : const MachineBlockFrequencyInfo *MBFI,
862 : const MachineBasicBlock *MBB) {
863 4670724 : BlockFrequency Freq = MBFI->getBlockFreq(MBB);
864 : const float Scale = 1.0f / MBFI->getEntryFreq();
865 : return (isDef + isUse) * (Freq.getFrequency() * Scale);
866 4672510 : }
867 :
868 : LiveRange::Segment
869 4672510 : LiveIntervals::addSegmentToEndOfBlock(unsigned reg, MachineInstr &startInst) {
870 4672510 : LiveInterval& Interval = createEmptyInterval(reg);
871 4672510 : VNInfo *VN = Interval.getNextValue(
872 : SlotIndex(getInstructionIndex(startInst).getRegSlot()),
873 : getVNInfoAllocator());
874 : LiveRange::Segment S(SlotIndex(getInstructionIndex(startInst).getRegSlot()),
875 0 : getMBBEndIdx(startInst.getParent()), VN);
876 0 : Interval.addSegment(S);
877 0 :
878 0 : return S;
879 : }
880 :
881 0 : //===----------------------------------------------------------------------===//
882 0 : // Register mask functions
883 : //===----------------------------------------------------------------------===//
884 0 :
885 : bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI,
886 : BitVector &UsableRegs) {
887 : if (LI.empty())
888 : return false;
889 : LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end();
890 :
891 1616639 : // Use a smaller arrays for local live ranges.
892 : ArrayRef<SlotIndex> Slots;
893 1616639 : ArrayRef<const uint32_t*> Bits;
894 : if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) {
895 : Slots = getRegMaskSlotsInBlock(MBB->getNumber());
896 : Bits = getRegMaskBitsInBlock(MBB->getNumber());
897 : } else {
898 : Slots = getRegMaskSlots();
899 : Bits = getRegMaskBits();
900 1616639 : }
901 1381765 :
902 : // We are going to enumerate all the register mask slots contained in LI.
903 : // Start with a binary search of RegMaskSlots to find a starting point.
904 : ArrayRef<SlotIndex>::iterator SlotI =
905 : std::lower_bound(Slots.begin(), Slots.end(), LiveI->start);
906 : ArrayRef<SlotIndex>::iterator SlotE = Slots.end();
907 :
908 : // No slots in range, LI begins after the last call.
909 : if (SlotI == SlotE)
910 : return false;
911 1616639 :
912 : bool Found = false;
913 : while (true) {
914 : assert(*SlotI >= LiveI->start);
915 1616639 : // Loop over all slots overlapping this segment.
916 : while (*SlotI < LiveI->end) {
917 : // *SlotI overlaps LI. Collect mask bits.
918 : if (!Found) {
919 : // This is the first overlap. Initialize UsableRegs to all ones.
920 : UsableRegs.clear();
921 : UsableRegs.resize(TRI->getNumRegs(), true);
922 2456278 : Found = true;
923 : }
924 1358933 : // Remove usable registers clobbered by this mask.
925 : UsableRegs.clearBitsNotInMask(Bits[SlotI-Slots.begin()]);
926 : if (++SlotI == SlotE)
927 139138 : return Found;
928 : }
929 : // *SlotI is beyond the current LI segment.
930 : LiveI = LI.advanceTo(LiveI, *SlotI);
931 2717866 : if (LiveI == LiveE)
932 1358933 : return Found;
933 25620 : // Advance SlotI until it overlaps.
934 : while (*SlotI < LiveI->start)
935 : if (++SlotI == SlotE)
936 1097345 : return Found;
937 1097345 : }
938 459488 : }
939 :
940 2226255 : //===----------------------------------------------------------------------===//
941 1600412 : // IntervalUpdate class.
942 12014 : //===----------------------------------------------------------------------===//
943 :
944 : /// Toolkit used by handleMove to trim or extend live intervals.
945 : class LiveIntervals::HMEditor {
946 : private:
947 : LiveIntervals& LIS;
948 : const MachineRegisterInfo& MRI;
949 : const TargetRegisterInfo& TRI;
950 : SlotIndex OldIdx;
951 : SlotIndex NewIdx;
952 : SmallPtrSet<LiveRange*, 8> Updated;
953 : bool UpdateFlags;
954 :
955 : public:
956 : HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI,
957 : const TargetRegisterInfo& TRI,
958 : SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags)
959 : : LIS(LIS), MRI(MRI), TRI(TRI), OldIdx(OldIdx), NewIdx(NewIdx),
960 : UpdateFlags(UpdateFlags) {}
961 :
962 : // FIXME: UpdateFlags is a workaround that creates live intervals for all
963 : // physregs, even those that aren't needed for regalloc, in order to update
964 : // kill flags. This is wasteful. Eventually, LiveVariables will strip all kill
965 218252 : // flags, and postRA passes will use a live register utility instead.
966 436504 : LiveRange *getRegUnitLI(unsigned Unit) {
967 : if (UpdateFlags && !MRI.isReservedRegUnit(Unit))
968 : return &LIS.getRegUnit(Unit);
969 : return LIS.getCachedRegUnit(Unit);
970 : }
971 :
972 314115 : /// Update all live ranges touched by MI, assuming a move from OldIdx to
973 314115 : /// NewIdx.
974 118500 : void updateAllRanges(MachineInstr *MI) {
975 391230 : LLVM_DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": "
976 : << *MI);
977 : bool hasRegMask = false;
978 : for (MachineOperand &MO : MI->operands()) {
979 : if (MO.isRegMask())
980 218252 : hasRegMask = true;
981 : if (!MO.isReg())
982 : continue;
983 : if (MO.isUse()) {
984 1466849 : if (!MO.readsReg())
985 1248597 : continue;
986 : // Aggressively clear all kill flags.
987 1248597 : // They are reinserted by VirtRegRewriter.
988 : MO.setIsKill(false);
989 638130 : }
990 :
991 : unsigned Reg = MO.getReg();
992 : if (!Reg)
993 : continue;
994 : if (TargetRegisterInfo::isVirtualRegister(Reg)) {
995 : LiveInterval &LI = LIS.getInterval(Reg);
996 : if (LI.hasSubRanges()) {
997 637904 : unsigned SubReg = MO.getSubReg();
998 637904 : LaneBitmask LaneMask = SubReg ? TRI.getSubRegIndexLaneMask(SubReg)
999 : : MRI.getMaxLaneMaskForVReg(Reg);
1000 604890 : for (LiveInterval::SubRange &S : LI.subranges()) {
1001 411384 : if ((S.LaneMask & LaneMask).none())
1002 411384 : continue;
1003 : updateRange(S, Reg, S.LaneMask);
1004 78621 : }
1005 97487 : }
1006 441243 : updateRange(LI, Reg, LaneBitmask::getNone());
1007 687512 : continue;
1008 : }
1009 142417 :
1010 : // For physregs, only update the regunits that actually have a
1011 : // precomputed live range.
1012 411384 : for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units)
1013 411384 : if (LiveRange *LR = getRegUnitLI(*Units))
1014 : updateRange(*LR, *Units, LaneBitmask::getNone());
1015 : }
1016 : if (hasRegMask)
1017 : updateRegMaskSlots();
1018 507621 : }
1019 314115 :
1020 132577 : private:
1021 : /// Update a single live range, assuming an instruction has been moved from
1022 218252 : /// OldIdx to NewIdx.
1023 0 : void updateRange(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask) {
1024 218252 : if (!Updated.insert(&LR).second)
1025 : return;
1026 : LLVM_DEBUG({
1027 : dbgs() << " ";
1028 : if (TargetRegisterInfo::isVirtualRegister(Reg)) {
1029 686378 : dbgs() << printReg(Reg);
1030 686378 : if (LaneMask.any())
1031 : dbgs() << " L" << PrintLaneMask(LaneMask);
1032 : } else {
1033 : dbgs() << printRegUnit(Reg, &TRI);
1034 : }
1035 : dbgs() << ":\t" << LR << '\n';
1036 : });
1037 : if (SlotIndex::isEarlierInstr(OldIdx, NewIdx))
1038 : handleMoveDown(LR);
1039 : else
1040 : handleMoveUp(LR, Reg, LaneMask);
1041 : LLVM_DEBUG(dbgs() << " -->\t" << LR << '\n');
1042 : LR.verify();
1043 666594 : }
1044 564416 :
1045 : /// Update LR to reflect an instruction has been moved downwards from OldIdx
1046 102178 : /// to NewIdx (OldIdx < NewIdx).
1047 : void handleMoveDown(LiveRange &LR) {
1048 : LiveRange::iterator E = LR.end();
1049 : // Segment going into OldIdx.
1050 : LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex());
1051 :
1052 : // No value live before or after OldIdx? Nothing to do.
1053 564416 : if (OldIdxIn == E || SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start))
1054 : return;
1055 :
1056 564416 : LiveRange::iterator OldIdxOut;
1057 : // Do we have a value live-in to OldIdx?
1058 : if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) {
1059 564416 : // If the live-in value already extends to NewIdx, there is nothing to do.
1060 : if (SlotIndex::isEarlierEqualInstr(NewIdx, OldIdxIn->end))
1061 : return;
1062 : // Aggressively remove all kill flags from the old kill point.
1063 : // Kill flags shouldn't be used while live intervals exist, they will be
1064 549717 : // reinserted by VirtRegRewriter.
1065 : if (MachineInstr *KillMI = LIS.getInstructionFromIndex(OldIdxIn->end))
1066 310936 : for (MIBundleOperands MO(*KillMI); MO.isValid(); ++MO)
1067 : if (MO->isReg() && MO->isUse())
1068 : MO->setIsKill(false);
1069 :
1070 : // Is there a def before NewIdx which is not OldIdx?
1071 210641 : LiveRange::iterator Next = std::next(OldIdxIn);
1072 131929 : if (Next != E && !SlotIndex::isSameInstr(OldIdx, Next->start) &&
1073 116384 : SlotIndex::isEarlierInstr(Next->start, NewIdx)) {
1074 : // If we are here then OldIdx was just a use but not a def. We only have
1075 : // to ensure liveness extends to NewIdx.
1076 : LiveRange::iterator NewIdxIn =
1077 : LR.advanceTo(Next, NewIdx.getBaseIndex());
1078 210641 : // Extend the segment before NewIdx if necessary.
1079 : if (NewIdxIn == E ||
1080 : !SlotIndex::isEarlierInstr(NewIdxIn->start, NewIdx)) {
1081 : LiveRange::iterator Prev = std::prev(NewIdxIn);
1082 : Prev->end = NewIdx.getRegSlot();
1083 266 : }
1084 : // Extend OldIdxIn.
1085 266 : OldIdxIn->end = Next->start;
1086 : return;
1087 : }
1088 67 :
1089 : // Adjust OldIdxIn->end to reach NewIdx. This may temporarily make LR
1090 : // invalid by overlapping ranges.
1091 266 : bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end);
1092 266 : OldIdxIn->end = NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber());
1093 : // If this was not a kill, then there was no def and we're done.
1094 : if (!isKill)
1095 : return;
1096 :
1097 : // Did we have a Def at OldIdx?
1098 210375 : OldIdxOut = Next;
1099 : if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start))
1100 210375 : return;
1101 : } else {
1102 : OldIdxOut = OldIdxIn;
1103 : }
1104 :
1105 195095 : // If we are here then there is a Definition at OldIdx. OldIdxOut points
1106 : // to the segment starting there.
1107 : assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) &&
1108 : "No def?");
1109 : VNInfo *OldIdxVNI = OldIdxOut->valno;
1110 : assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def");
1111 :
1112 : // If the defined value extends beyond NewIdx, just move the beginning
1113 : // of the segment to NewIdx.
1114 : SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber());
1115 272882 : if (SlotIndex::isEarlierInstr(NewIdxDef, OldIdxOut->end)) {
1116 : OldIdxVNI->def = NewIdxDef;
1117 : OldIdxOut->start = OldIdxVNI->def;
1118 : return;
1119 : }
1120 :
1121 272882 : // If we are here then we have a Definition at OldIdx which ends before
1122 254468 : // NewIdx.
1123 254468 :
1124 254468 : // Is there an existing Def at NewIdx?
1125 : LiveRange::iterator AfterNewIdx
1126 : = LR.advanceTo(OldIdxOut, NewIdx.getRegSlot());
1127 : bool OldIdxDefIsDead = OldIdxOut->end.isDead();
1128 : if (!OldIdxDefIsDead &&
1129 : SlotIndex::isEarlierInstr(OldIdxOut->end, NewIdxDef)) {
1130 : // OldIdx is not a dead def, and NewIdxDef is inside a new interval.
1131 : VNInfo *DefVNI;
1132 18414 : if (OldIdxOut != LR.begin() &&
1133 : !SlotIndex::isEarlierInstr(std::prev(OldIdxOut)->end,
1134 18414 : OldIdxOut->start)) {
1135 : // There is no gap between OldIdxOut and its predecessor anymore,
1136 : // merge them.
1137 : LiveRange::iterator IPrev = std::prev(OldIdxOut);
1138 5191 : DefVNI = OldIdxVNI;
1139 : IPrev->end = OldIdxOut->end;
1140 : } else {
1141 : // The value is live in to OldIdx
1142 : LiveRange::iterator INext = std::next(OldIdxOut);
1143 : assert(INext != E && "Must have following segment");
1144 : // We merge OldIdxOut and its successor. As we're dealing with subreg
1145 2217 : // reordering, there is always a successor to OldIdxOut in the same BB
1146 : // We don't need INext->valno anymore and will reuse for the new segment
1147 : // we create later.
1148 : DefVNI = OldIdxVNI;
1149 : INext->start = OldIdxOut->end;
1150 : INext->valno->def = INext->start;
1151 : }
1152 : // If NewIdx is behind the last segment, extend that and append a new one.
1153 : if (AfterNewIdx == E) {
1154 : // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up
1155 2974 : // one position.
1156 2974 : // |- ?/OldIdxOut -| |- X0 -| ... |- Xn -| end
1157 : // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS -| end
1158 : std::copy(std::next(OldIdxOut), E, OldIdxOut);
1159 5191 : // The last segment is undefined now, reuse it for a dead def.
1160 : LiveRange::iterator NewSegment = std::prev(E);
1161 : *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),
1162 : DefVNI);
1163 : DefVNI->def = NewIdxDef;
1164 :
1165 : LiveRange::iterator Prev = std::prev(NewSegment);
1166 : Prev->end = NewIdxDef;
1167 0 : } else {
1168 : // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up
1169 0 : // one position.
1170 : // |- ?/OldIdxOut -| |- X0 -| ... |- Xn/AfterNewIdx -| |- Next -|
1171 : // => |- X0/OldIdxOut -| ... |- Xn -| |- Xn/AfterNewIdx -| |- Next -|
1172 0 : std::copy(std::next(OldIdxOut), std::next(AfterNewIdx), OldIdxOut);
1173 : LiveRange::iterator Prev = std::prev(AfterNewIdx);
1174 : // We have two cases:
1175 : if (SlotIndex::isEarlierInstr(Prev->start, NewIdxDef)) {
1176 : // Case 1: NewIdx is inside a liverange. Split this liverange at
1177 : // NewIdxDef into the segment "Prev" followed by "NewSegment".
1178 : LiveRange::iterator NewSegment = AfterNewIdx;
1179 : *NewSegment = LiveRange::Segment(NewIdxDef, Prev->end, Prev->valno);
1180 : Prev->valno->def = NewIdxDef;
1181 5191 :
1182 : *Prev = LiveRange::Segment(Prev->start, NewIdxDef, DefVNI);
1183 : DefVNI->def = Prev->start;
1184 : } else {
1185 5191 : // Case 2: NewIdx is in a lifetime hole. Keep AfterNewIdx as is and
1186 5191 : // turn Prev into a segment from NewIdx to AfterNewIdx->start.
1187 : *Prev = LiveRange::Segment(NewIdxDef, AfterNewIdx->start, DefVNI);
1188 5191 : DefVNI->def = NewIdxDef;
1189 5191 : assert(DefVNI != AfterNewIdx->valno);
1190 : }
1191 : }
1192 : return;
1193 0 : }
1194 0 :
1195 : if (AfterNewIdx != E &&
1196 : SlotIndex::isSameInstr(AfterNewIdx->start, NewIdxDef)) {
1197 : // There is an existing def at NewIdx. The def at OldIdx is coalesced into
1198 5191 : // that value.
1199 : assert(AfterNewIdx->valno != OldIdxVNI && "Multiple defs of value?");
1200 : LR.removeValNo(OldIdxVNI);
1201 13223 : } else {
1202 : // There was no existing def at NewIdx. We need to create a dead def
1203 : // at NewIdx. Shift segments over the old OldIdxOut segment, this frees
1204 : // a new segment at the place where we want to construct the dead def.
1205 : // |- OldIdxOut -| |- X0 -| ... |- Xn -| |- AfterNewIdx -|
1206 0 : // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS. -| |- AfterNewIdx -|
1207 : assert(AfterNewIdx != OldIdxOut && "Inconsistent iterators");
1208 : std::copy(std::next(OldIdxOut), AfterNewIdx, OldIdxOut);
1209 : // We can reuse OldIdxVNI now.
1210 : LiveRange::iterator NewSegment = std::prev(AfterNewIdx);
1211 : VNInfo *NewSegmentVNI = OldIdxVNI;
1212 : NewSegmentVNI->def = NewIdxDef;
1213 : *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),
1214 : NewSegmentVNI);
1215 : }
1216 : }
1217 :
1218 13223 : /// Update LR to reflect an instruction has been moved upwards from OldIdx
1219 13223 : /// to NewIdx (NewIdx < OldIdx).
1220 : void handleMoveUp(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask) {
1221 : LiveRange::iterator E = LR.end();
1222 : // Segment going into OldIdx.
1223 : LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex());
1224 :
1225 : // No value live before or after OldIdx? Nothing to do.
1226 102178 : if (OldIdxIn == E || SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start))
1227 : return;
1228 :
1229 102178 : LiveRange::iterator OldIdxOut;
1230 : // Do we have a value live-in to OldIdx?
1231 : if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) {
1232 102178 : // If the live-in value isn't killed here, then we have no Def at
1233 : // OldIdx, moreover the value must be live at NewIdx so there is nothing
1234 : // to do.
1235 : bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end);
1236 : if (!isKill)
1237 98837 : return;
1238 :
1239 : // At this point we have to move OldIdxIn->end back to the nearest
1240 : // previous use or (dead-)def but no further than NewIdx.
1241 : SlotIndex DefBeforeOldIdx
1242 53562 : = std::max(OldIdxIn->start.getDeadSlot(),
1243 50485 : NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber()));
1244 : OldIdxIn->end = findLastUseBefore(DefBeforeOldIdx, Reg, LaneMask);
1245 :
1246 : // Did we have a Def at OldIdx? If not we are done now.
1247 : OldIdxOut = std::next(OldIdxIn);
1248 44561 : if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start))
1249 44561 : return;
1250 44561 : } else {
1251 : OldIdxOut = OldIdxIn;
1252 : OldIdxIn = OldIdxOut != LR.begin() ? std::prev(OldIdxOut) : E;
1253 : }
1254 44561 :
1255 : // If we are here then there is a Definition at OldIdx. OldIdxOut points
1256 : // to the segment starting there.
1257 : assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) &&
1258 45275 : "No def?");
1259 : VNInfo *OldIdxVNI = OldIdxOut->valno;
1260 : assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def");
1261 : bool OldIdxDefIsDead = OldIdxOut->end.isDead();
1262 :
1263 : // Is there an existing def at NewIdx?
1264 : SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber());
1265 48352 : LiveRange::iterator NewIdxOut = LR.find(NewIdx.getRegSlot());
1266 : if (SlotIndex::isSameInstr(NewIdxOut->start, NewIdx)) {
1267 : assert(NewIdxOut->valno != OldIdxVNI &&
1268 : "Same value defined more than once?");
1269 : // If OldIdx was a dead def remove it.
1270 : if (!OldIdxDefIsDead) {
1271 48352 : // Remove segment starting at NewIdx and move begin of OldIdxOut to
1272 48352 : // NewIdx so it can take its place.
1273 : OldIdxVNI->def = NewIdxDef;
1274 : OldIdxOut->start = NewIdxDef;
1275 : LR.removeValNo(NewIdxOut->valno);
1276 0 : } else {
1277 : // Simply remove the dead def at OldIdx.
1278 : LR.removeValNo(OldIdxVNI);
1279 0 : }
1280 0 : } else {
1281 0 : // Previously nothing was live after NewIdx, so all we have to do now is
1282 : // move the begin of OldIdxOut to NewIdx.
1283 : if (!OldIdxDefIsDead) {
1284 0 : // Do we have any intermediate Defs between OldIdx and NewIdx?
1285 : if (OldIdxIn != E &&
1286 : SlotIndex::isEarlierInstr(NewIdxDef, OldIdxIn->start)) {
1287 : // OldIdx is not a dead def and NewIdx is before predecessor start.
1288 : LiveRange::iterator NewIdxIn = NewIdxOut;
1289 48352 : assert(NewIdxIn == LR.find(NewIdx.getBaseIndex()));
1290 : const SlotIndex SplitPos = NewIdxDef;
1291 38143 : OldIdxVNI = OldIdxIn->valno;
1292 :
1293 : // Merge the OldIdxIn and OldIdxOut segments into OldIdxOut.
1294 : OldIdxOut->valno->def = OldIdxIn->start;
1295 : *OldIdxOut = LiveRange::Segment(OldIdxIn->start, OldIdxOut->end,
1296 : OldIdxOut->valno);
1297 326 : // OldIdxIn and OldIdxVNI are now undef and can be overridden.
1298 : // We Slide [NewIdxIn, OldIdxIn) down one position.
1299 : // |- X0/NewIdxIn -| ... |- Xn-1 -||- Xn/OldIdxIn -||- OldIdxOut -|
1300 326 : // => |- undef/NexIdxIn -| |- X0 -| ... |- Xn-1 -| |- Xn/OldIdxOut -|
1301 326 : std::copy_backward(NewIdxIn, OldIdxIn, OldIdxOut);
1302 : // NewIdxIn is now considered undef so we can reuse it for the moved
1303 : // value.
1304 : LiveRange::iterator NewSegment = NewIdxIn;
1305 : LiveRange::iterator Next = std::next(NewSegment);
1306 : if (SlotIndex::isEarlierInstr(Next->start, NewIdx)) {
1307 : // There is no gap between NewSegment and its predecessor.
1308 : *NewSegment = LiveRange::Segment(Next->start, SplitPos,
1309 : Next->valno);
1310 : *Next = LiveRange::Segment(SplitPos, Next->end, OldIdxVNI);
1311 : Next->valno->def = SplitPos;
1312 326 : } else {
1313 : // There is a gap between NewSegment and its predecessor
1314 204 : // Value becomes live in.
1315 : *NewSegment = LiveRange::Segment(SplitPos, Next->start, OldIdxVNI);
1316 204 : NewSegment->valno->def = SplitPos;
1317 204 : }
1318 : } else {
1319 : // Leave the end point of a live def.
1320 : OldIdxOut->start = NewIdxDef;
1321 122 : OldIdxVNI->def = NewIdxDef;
1322 122 : if (OldIdxIn != E && SlotIndex::isEarlierInstr(NewIdx, OldIdxIn->end))
1323 : OldIdxIn->end = NewIdx.getRegSlot();
1324 : }
1325 : } else if (OldIdxIn != E
1326 37817 : && SlotIndex::isEarlierInstr(NewIdxOut->start, NewIdx)
1327 37817 : && SlotIndex::isEarlierInstr(NewIdx, NewIdxOut->end)) {
1328 37817 : // OldIdxVNI is a dead def that has been moved into the middle of
1329 6 : // another value in LR. That can happen when LR is a whole register,
1330 : // but the dead def is a write to a subreg that is dead at NewIdx.
1331 : // The dead def may have been moved across other values
1332 9860 : // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut)
1333 10210 : // down one position.
1334 : // |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - |
1335 : // => |- X0/NewIdxOut -| |- X0 -| ... |- Xn-1 -| |- next -|
1336 : std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut));
1337 : // Modify the segment at NewIdxOut and the following segment to meet at
1338 : // the point of the dead def, with the following segment getting
1339 : // OldIdxVNI as its value number.
1340 : *NewIdxOut = LiveRange::Segment(
1341 : NewIdxOut->start, NewIdxDef.getRegSlot(), NewIdxOut->valno);
1342 : *(NewIdxOut + 1) = LiveRange::Segment(
1343 : NewIdxDef.getRegSlot(), (NewIdxOut + 1)->end, OldIdxVNI);
1344 : OldIdxVNI->def = NewIdxDef;
1345 : // Modify subsequent segments to be defined by the moved def OldIdxVNI.
1346 1 : for (auto Idx = NewIdxOut + 2; Idx <= OldIdxOut; ++Idx)
1347 : Idx->valno = OldIdxVNI;
1348 1 : // Aggressively remove all dead flags from the former dead definition.
1349 : // Kill/dead flags shouldn't be used while live intervals exist; they
1350 1 : // will be reinserted by VirtRegRewriter.
1351 : if (MachineInstr *KillMI = LIS.getInstructionFromIndex(NewIdx))
1352 1 : for (MIBundleOperands MO(*KillMI); MO.isValid(); ++MO)
1353 0 : if (MO->isReg() && !MO->isUse())
1354 : MO->setIsDead(false);
1355 : } else {
1356 : // OldIdxVNI is a dead def. It may have been moved across other values
1357 1 : // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut)
1358 6 : // down one position.
1359 5 : // |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - |
1360 : // => |- undef/NewIdxOut -| |- X0 -| ... |- Xn-1 -| |- next -|
1361 : std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut));
1362 : // OldIdxVNI can be reused now to build a new dead def segment.
1363 : LiveRange::iterator NewSegment = NewIdxOut;
1364 : VNInfo *NewSegmentVNI = OldIdxVNI;
1365 : *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),
1366 : NewSegmentVNI);
1367 : NewSegmentVNI->def = NewIdxDef;
1368 : }
1369 : }
1370 : }
1371 10208 :
1372 : void updateRegMaskSlots() {
1373 10208 : SmallVectorImpl<SlotIndex>::iterator RI =
1374 : std::lower_bound(LIS.RegMaskSlots.begin(), LIS.RegMaskSlots.end(),
1375 : OldIdx);
1376 : assert(RI != LIS.RegMaskSlots.end() && *RI == OldIdx.getRegSlot() &&
1377 : "No RegMask at OldIdx.");
1378 0 : *RI = NewIdx.getRegSlot();
1379 : assert((RI == LIS.RegMaskSlots.begin() ||
1380 0 : SlotIndex::isEarlierInstr(*std::prev(RI), *RI)) &&
1381 0 : "Cannot move regmask instruction above another call");
1382 : assert((std::next(RI) == LIS.RegMaskSlots.end() ||
1383 : SlotIndex::isEarlierInstr(*RI, *std::next(RI))) &&
1384 0 : "Cannot move regmask instruction below another call");
1385 : }
1386 :
1387 : // Return the last use of reg between NewIdx and OldIdx.
1388 : SlotIndex findLastUseBefore(SlotIndex Before, unsigned Reg,
1389 : LaneBitmask LaneMask) {
1390 : if (TargetRegisterInfo::isVirtualRegister(Reg)) {
1391 0 : SlotIndex LastUse = Before;
1392 : for (MachineOperand &MO : MRI.use_nodbg_operands(Reg)) {
1393 : if (MO.isUndef())
1394 44561 : continue;
1395 : unsigned SubReg = MO.getSubReg();
1396 44561 : if (SubReg != 0 && LaneMask.any()
1397 32898 : && (TRI.getSubRegIndexLaneMask(SubReg) & LaneMask).none())
1398 152142 : continue;
1399 86346 :
1400 : const MachineInstr &MI = *MO.getParent();
1401 : SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI);
1402 31533 : if (InstSlot > LastUse && InstSlot < OldIdx)
1403 127136 : LastUse = InstSlot.getRegSlot();
1404 : }
1405 : return LastUse;
1406 72065 : }
1407 72065 :
1408 72065 : // This is a regunit interval, so scanning the use list could be very
1409 : // expensive. Scan upwards from OldIdx instead.
1410 : assert(Before < OldIdx && "Expected upwards move");
1411 32898 : SlotIndexes *Indexes = LIS.getSlotIndexes();
1412 : MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Before);
1413 :
1414 : // OldIdx may not correspond to an instruction any longer, so set MII to
1415 : // point to the next instruction after OldIdx, or MBB->end().
1416 : MachineBasicBlock::iterator MII = MBB->end();
1417 11663 : if (MachineInstr *MI = Indexes->getInstructionFromIndex(
1418 11663 : Indexes->getNextNonNullIndex(OldIdx)))
1419 : if (MI->getParent() == MBB)
1420 : MII = MI;
1421 :
1422 11663 : MachineBasicBlock::iterator Begin = MBB->begin();
1423 11663 : while (MII != Begin) {
1424 : if ((--MII)->isDebugInstr())
1425 11663 : continue;
1426 11494 : SlotIndex Idx = Indexes->getInstructionIndex(*MII);
1427 :
1428 : // Stop searching when Before is reached.
1429 68415 : if (!SlotIndex::isEarlierInstr(Before, Idx))
1430 : return Before;
1431 460 :
1432 67955 : // Check if MII uses Reg.
1433 : for (MIBundleOperands MO(*MII); MO.isValid(); ++MO)
1434 : if (MO->isReg() && !MO->isUndef() &&
1435 67955 : TargetRegisterInfo::isPhysicalRegister(MO->getReg()) &&
1436 11663 : TRI.hasRegUnit(MO->getReg(), Reg))
1437 : return Idx.getRegSlot();
1438 : }
1439 231502 : // Didn't reach Before. It must be the first instruction in the block.
1440 117850 : return Before;
1441 346717 : }
1442 53858 : };
1443 0 :
1444 : void LiveIntervals::handleMove(MachineInstr &MI, bool UpdateFlags) {
1445 : assert(!MI.isBundled() && "Can't handle bundled instructions yet.");
1446 0 : SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
1447 : Indexes->removeMachineInstrFromMaps(MI);
1448 : SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(MI);
1449 : assert(getMBBStartIdx(MI.getParent()) <= OldIndex &&
1450 218252 : OldIndex < getMBBEndIdx(MI.getParent()) &&
1451 : "Cannot handle moves across basic block boundaries.");
1452 218252 :
1453 218252 : HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
1454 218252 : HME.updateAllRanges(&MI);
1455 : }
1456 :
1457 : void LiveIntervals::handleMoveIntoBundle(MachineInstr &MI,
1458 : MachineInstr &BundleStart,
1459 218252 : bool UpdateFlags) {
1460 218252 : SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
1461 218252 : SlotIndex NewIndex = Indexes->getInstructionIndex(BundleStart);
1462 : HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
1463 0 : HME.updateAllRanges(&MI);
1464 : }
1465 :
1466 0 : void LiveIntervals::repairOldRegInRange(const MachineBasicBlock::iterator Begin,
1467 0 : const MachineBasicBlock::iterator End,
1468 0 : const SlotIndex endIdx,
1469 0 : LiveRange &LR, const unsigned Reg,
1470 0 : LaneBitmask LaneMask) {
1471 : LiveInterval::iterator LII = LR.find(endIdx);
1472 54 : SlotIndex lastUseIdx;
1473 : if (LII == LR.begin()) {
1474 : // This happens when the function is called for a subregister that only
1475 : // occurs _after_ the range that is to be repaired.
1476 : return;
1477 54 : }
1478 : if (LII != LR.end() && LII->start < endIdx)
1479 54 : lastUseIdx = LII->end;
1480 : else
1481 : --LII;
1482 :
1483 : for (MachineBasicBlock::iterator I = End; I != Begin;) {
1484 27 : --I;
1485 0 : MachineInstr &MI = *I;
1486 : if (MI.isDebugInstr())
1487 27 : continue;
1488 :
1489 187 : SlotIndex instrIdx = getInstructionIndex(MI);
1490 : bool isStartValid = getInstructionFromIndex(LII->start);
1491 : bool isEndValid = getInstructionFromIndex(LII->end);
1492 :
1493 : // FIXME: This doesn't currently handle early-clobber or multiple removed
1494 : // defs inside of the region to repair.
1495 160 : for (MachineInstr::mop_iterator OI = MI.operands_begin(),
1496 : OE = MI.operands_end();
1497 : OI != OE; ++OI) {
1498 : const MachineOperand &MO = *OI;
1499 : if (!MO.isReg() || MO.getReg() != Reg)
1500 : continue;
1501 957 :
1502 160 : unsigned SubReg = MO.getSubReg();
1503 1117 : LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg);
1504 : if ((Mask & LaneMask).none())
1505 957 : continue;
1506 :
1507 : if (MO.isDef()) {
1508 : if (!isStartValid) {
1509 54 : if (LII->end.isDead()) {
1510 54 : SlotIndex prevStart;
1511 : if (LII != LR.begin())
1512 : prevStart = std::prev(LII)->start;
1513 54 :
1514 27 : // FIXME: This could be more efficient if there was a
1515 0 : // removeSegment method that returned an iterator.
1516 : LR.removeSegment(*LII, true);
1517 0 : if (prevStart.isValid())
1518 0 : LII = LR.find(prevStart);
1519 : else
1520 : LII = LR.begin();
1521 : } else {
1522 0 : LII->start = instrIdx.getRegSlot();
1523 0 : LII->valno->def = instrIdx.getRegSlot();
1524 0 : if (MO.getSubReg() && !MO.isUndef())
1525 : lastUseIdx = instrIdx.getRegSlot();
1526 : else
1527 : lastUseIdx = SlotIndex();
1528 0 : continue;
1529 0 : }
1530 0 : }
1531 :
1532 : if (!lastUseIdx.isValid()) {
1533 : VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator);
1534 0 : LiveRange::Segment S(instrIdx.getRegSlot(),
1535 : instrIdx.getDeadSlot(), VNI);
1536 : LII = LR.addSegment(S);
1537 : } else if (LII->start != instrIdx.getRegSlot()) {
1538 27 : VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator);
1539 0 : LiveRange::Segment S(instrIdx.getRegSlot(), lastUseIdx, VNI);
1540 : LII = LR.addSegment(S);
1541 : }
1542 0 :
1543 27 : if (MO.getSubReg() && !MO.isUndef())
1544 0 : lastUseIdx = instrIdx.getRegSlot();
1545 : else
1546 0 : lastUseIdx = SlotIndex();
1547 : } else if (MO.isUse()) {
1548 : // FIXME: This should probably be handled outside of this branch,
1549 27 : // either as part of the def case (for defs inside of the region) or
1550 : // after the loop over the region.
1551 : if (!isEndValid && !LII->end.isBlock())
1552 : LII->end = instrIdx.getRegSlot();
1553 : if (!lastUseIdx.isValid())
1554 : lastUseIdx = instrIdx.getRegSlot();
1555 : }
1556 : }
1557 27 : }
1558 27 : }
1559 27 :
1560 : void
1561 : LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB,
1562 : MachineBasicBlock::iterator Begin,
1563 : MachineBasicBlock::iterator End,
1564 : ArrayRef<unsigned> OrigRegs) {
1565 : // Find anchor points, which are at the beginning/end of blocks or at
1566 : // instructions that already have indexes.
1567 27 : while (Begin != MBB->begin() && !Indexes->hasIndex(*Begin))
1568 : --Begin;
1569 : while (End != MBB->end() && !Indexes->hasIndex(*End))
1570 : ++End;
1571 :
1572 : SlotIndex endIdx;
1573 80 : if (End == MBB->end())
1574 : endIdx = getMBBEndIdx(MBB).getPrevSlot();
1575 54 : else
1576 : endIdx = getInstructionIndex(*End);
1577 :
1578 : Indexes->repairIndexesInRange(MBB, Begin, End);
1579 27 :
1580 0 : for (MachineBasicBlock::iterator I = End; I != Begin;) {
1581 : --I;
1582 27 : MachineInstr &MI = *I;
1583 : if (MI.isDebugInstr())
1584 27 : continue;
1585 : for (MachineInstr::const_mop_iterator MOI = MI.operands_begin(),
1586 187 : MOE = MI.operands_end();
1587 : MOI != MOE; ++MOI) {
1588 : if (MOI->isReg() &&
1589 : TargetRegisterInfo::isVirtualRegister(MOI->getReg()) &&
1590 : !hasInterval(MOI->getReg())) {
1591 957 : createAndComputeVirtRegInterval(MOI->getReg());
1592 160 : }
1593 1117 : }
1594 779 : }
1595 957 :
1596 : for (unsigned Reg : OrigRegs) {
1597 : if (!TargetRegisterInfo::isVirtualRegister(Reg))
1598 : continue;
1599 :
1600 : LiveInterval &LI = getInterval(Reg);
1601 : // FIXME: Should we support undefs that gain defs?
1602 108 : if (!LI.hasAtLeastOneValue())
1603 81 : continue;
1604 :
1605 : for (LiveInterval::SubRange &S : LI.subranges())
1606 54 : repairOldRegInRange(Begin, End, endIdx, S, Reg, S.LaneMask);
1607 :
1608 54 : repairOldRegInRange(Begin, End, endIdx, LI, Reg);
1609 : }
1610 : }
1611 54 :
1612 0 : void LiveIntervals::removePhysRegDefAt(unsigned Reg, SlotIndex Pos) {
1613 : for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); ++Unit) {
1614 54 : if (LiveRange *LR = getCachedRegUnit(*Unit))
1615 : if (VNInfo *VNI = LR->getVNInfoAt(Pos))
1616 27 : LR->removeValNo(VNI);
1617 : }
1618 9111 : }
1619 27351 :
1620 9129 : void LiveIntervals::removeVRegDefAt(LiveInterval &LI, SlotIndex Pos) {
1621 281 : // LI may not have the main range computed yet, but its subranges may
1622 271 : // be present.
1623 : VNInfo *VNI = LI.getVNInfoAt(Pos);
1624 9111 : if (VNI != nullptr) {
1625 : assert(VNI->def.getBaseIndex() == Pos.getBaseIndex());
1626 77795 : LI.removeValNo(VNI);
1627 : }
1628 :
1629 77797 : // Also remove the value defined in subranges.
1630 77793 : for (LiveInterval::SubRange &S : LI.subranges()) {
1631 : if (VNInfo *SVNI = S.getVNInfoAt(Pos))
1632 77793 : if (SVNI->def.getBaseIndex() == Pos.getBaseIndex())
1633 : S.removeValNo(SVNI);
1634 : }
1635 : LI.removeEmptySubRanges();
1636 77836 : }
1637 82 :
1638 41 : void LiveIntervals::splitSeparateComponents(LiveInterval &LI,
1639 41 : SmallVectorImpl<LiveInterval*> &SplitLIs) {
1640 : ConnectedVNInfoEqClasses ConEQ(*this);
1641 77795 : unsigned NumComp = ConEQ.Classify(LI);
1642 77795 : if (NumComp <= 1)
1643 : return;
1644 79904 : LLVM_DEBUG(dbgs() << " Split " << NumComp << " components: " << LI << '\n');
1645 : unsigned Reg = LI.reg;
1646 : const TargetRegisterClass *RegClass = MRI->getRegClass(Reg);
1647 79904 : for (unsigned I = 1; I < NumComp; ++I) {
1648 79904 : unsigned NewVReg = MRI->createVirtualRegister(RegClass);
1649 : LiveInterval &NewLI = createEmptyInterval(NewVReg);
1650 : SplitLIs.push_back(&NewLI);
1651 15504 : }
1652 15504 : ConEQ.Distribute(LI, SplitLIs.data(), *MRI);
1653 33216 : }
1654 35424 :
1655 17712 : void LiveIntervals::constructMainRangeFromSubranges(LiveInterval &LI) {
1656 17712 : assert(LRCalc && "LRCalc not initialized.");
1657 : LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
1658 15504 : LRCalc->constructMainRangeFromSubranges(LI);
1659 : }
|
