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