1//=====-- Rematerializer.cpp - MIR rematerialization support ----*- C++ -*-===//
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
10/// Implements helpers for target-independent rematerialization at the MIR
11/// level.
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/CodeGen/Rematerializer.h"
16#include "llvm/ADT/MapVector.h"
17#include "llvm/ADT/STLExtras.h"
18#include "llvm/ADT/SetVector.h"
19#include "llvm/ADT/SmallSet.h"
20#include "llvm/CodeGen/LiveIntervals.h"
21#include "llvm/CodeGen/LiveRangeEdit.h"
22#include "llvm/CodeGen/MachineBasicBlock.h"
23#include "llvm/CodeGen/MachineOperand.h"
24#include "llvm/CodeGen/MachineRegisterInfo.h"
25#include "llvm/CodeGen/Register.h"
26#include "llvm/CodeGen/TargetRegisterInfo.h"
27#include "llvm/MC/LaneBitmask.h"
28#include "llvm/Support/Debug.h"
29#include <optional>
30
31#define DEBUG_TYPE "rematerializer"
32
33using namespace llvm;
34using RegisterIdx = Rematerializer::RegisterIdx;
35
36// Pin the vtable to this file.
37void Rematerializer::Listener::anchor() {}
38
39/// Checks whether the value in \p LI at \p UseIdx is identical to \p OVNI (this
40/// implies it is also live there). When \p LI has sub-ranges, checks that
41/// all sub-ranges intersecting with \p Mask are also live at \p UseIdx.
42static bool isIdenticalAtUse(const VNInfo &OVNI, LaneBitmask Mask,
43 SlotIndex UseIdx, const LiveInterval &LI) {
44 if (&OVNI != LI.getVNInfoAt(Idx: UseIdx))
45 return false;
46
47 if (LI.hasSubRanges()) {
48 // Check that intersecting subranges are live at user.
49 for (const LiveInterval::SubRange &SR : LI.subranges()) {
50 if ((SR.LaneMask & Mask).none())
51 continue;
52 if (!SR.liveAt(index: UseIdx))
53 return false;
54
55 // Early exit if all used lanes are checked. No need to continue.
56 Mask &= ~SR.LaneMask;
57 if (Mask.none())
58 break;
59 }
60 }
61 return true;
62}
63
64/// If \p MO is a virtual read register, returns it. Otherwise returns the
65/// sentinel register.
66static Register getRegDependency(const MachineOperand &MO) {
67 if (!MO.isReg() || !MO.readsReg())
68 return Register();
69 Register Reg = MO.getReg();
70 if (Reg.isPhysical()) {
71 // By the requirements on trivially rematerializable instructions, a
72 // physical register use is either constant or ignorable.
73 return Register();
74 }
75 return Reg;
76}
77
78RegisterIdx Rematerializer::rematerializeToRegion(RegisterIdx RootIdx,
79 unsigned UseRegion,
80 DependencyReuseInfo &DRI) {
81 MachineInstr *FirstMI =
82 getReg(RegIdx: RootIdx).getRegionUseBounds(UseRegion, LIS).first;
83 // If there are no users in the region, rematerialize the register at the very
84 // end of the region.
85 MachineBasicBlock::iterator InsertPos =
86 FirstMI ? FirstMI : Regions[UseRegion].second;
87 RegisterIdx NewRegIdx =
88 rematerializeToPos(RootIdx, UseRegion, InsertPos, DRI);
89 transferRegionUsers(FromRegIdx: RootIdx, ToRegIdx: NewRegIdx, UseRegion);
90 return NewRegIdx;
91}
92
93RegisterIdx
94Rematerializer::rematerializeToPos(RegisterIdx RootIdx, unsigned UseRegion,
95 MachineBasicBlock::iterator InsertPos,
96 DependencyReuseInfo &DRI) {
97 assert(!DRI.DependencyMap.contains(RootIdx));
98 LLVM_DEBUG(dbgs() << "Rematerializing " << printID(RootIdx) << '\n');
99
100 SmallVector<RegisterIdx, 2> NewDeps;
101 // Copy all dependencies because recursive rematerialization of dependencies
102 // may invalidate references to the backing vector of registers.
103 SmallVector<RegisterIdx, 2> OldDeps(getReg(RegIdx: RootIdx).Dependencies);
104 for (RegisterIdx DepRegIdx : OldDeps) {
105 // Recursively rematerialize required dependencies at the same position as
106 // the root. Registers form a DAG so the recursion is guaranteed to
107 // terminate.
108 auto RematIdx = DRI.DependencyMap.find(Val: DepRegIdx);
109 RegisterIdx NewDepRegIdx;
110 if (RematIdx == DRI.DependencyMap.end())
111 NewDepRegIdx = rematerializeToPos(RootIdx: DepRegIdx, UseRegion, InsertPos, DRI);
112 else
113 NewDepRegIdx = RematIdx->second;
114 NewDeps.push_back(Elt: NewDepRegIdx);
115 }
116 RegisterIdx NewIdx =
117 rematerializeReg(RegIdx: RootIdx, UseRegion, InsertPos, Dependencies: std::move(NewDeps));
118 DRI.DependencyMap.insert(KV: {RootIdx, NewIdx});
119 return NewIdx;
120}
121
122void Rematerializer::transferUser(RegisterIdx FromRegIdx, RegisterIdx ToRegIdx,
123 unsigned UserRegion, MachineInstr &UserMI) {
124 transferUserImpl(FromRegIdx, ToRegIdx, UserMI);
125
126 Regs[ToRegIdx].addUser(MI: &UserMI, Region: UserRegion);
127 extendToNewUsers(RegIdx: ToRegIdx, NewUsers: &UserMI);
128
129 Regs[FromRegIdx].eraseUser(MI: &UserMI, Region: UserRegion);
130 shrinkToUses(RegIdx: FromRegIdx);
131}
132
133void Rematerializer::transferRegionUsers(RegisterIdx FromRegIdx,
134 RegisterIdx ToRegIdx,
135 unsigned UseRegion) {
136 Reg &FromReg = Regs[FromRegIdx];
137 auto UsesIt = FromReg.Uses.find(Val: UseRegion);
138 if (UsesIt == FromReg.Uses.end())
139 return;
140
141 const SmallDenseSet<MachineInstr *, 4> &RegionUsers = UsesIt->getSecond();
142 SmallVector<MachineInstr *, 4> NewUsers;
143 for (MachineInstr *UserMI : RegionUsers) {
144 transferUserImpl(FromRegIdx, ToRegIdx, UserMI&: *UserMI);
145 NewUsers.push_back(Elt: UserMI);
146 }
147
148 extendToNewUsers(RegIdx: ToRegIdx, NewUsers);
149 Regs[ToRegIdx].addUsers(NewUsers: RegionUsers, Region: UseRegion);
150
151 FromReg.Uses.erase(Val: UseRegion);
152 shrinkToUses(RegIdx: FromRegIdx);
153}
154
155void Rematerializer::transferAllUsers(RegisterIdx FromRegIdx,
156 RegisterIdx ToRegIdx) {
157 Reg &FromReg = Regs[FromRegIdx];
158 SmallVector<MachineInstr *, 4> NewUsers;
159 for (const auto &[UseRegion, RegionUsers] : FromReg.Uses) {
160 for (MachineInstr *UserMI : RegionUsers) {
161 transferUserImpl(FromRegIdx, ToRegIdx, UserMI&: *UserMI);
162 NewUsers.push_back(Elt: UserMI);
163 }
164 Regs[ToRegIdx].addUsers(NewUsers: RegionUsers, Region: UseRegion);
165 }
166 extendToNewUsers(RegIdx: ToRegIdx, NewUsers);
167
168 FromReg.Uses.clear();
169 deleteReg(RootIdx: FromRegIdx);
170}
171
172void Rematerializer::transferUserImpl(RegisterIdx FromRegIdx,
173 RegisterIdx ToRegIdx,
174 MachineInstr &UserMI) {
175 assert(FromRegIdx != ToRegIdx && "identical registers");
176 assert(getOriginOrSelf(FromRegIdx) == getOriginOrSelf(ToRegIdx) &&
177 "unrelated registers");
178
179 LLVM_DEBUG(dbgs() << "User transfer from " << printID(FromRegIdx) << " to "
180 << printID(ToRegIdx) << ": " << printUser(&UserMI) << '\n');
181
182 Register FromReg = getReg(RegIdx: FromRegIdx).getDefReg();
183 UserMI.substituteRegister(FromReg, ToReg: getReg(RegIdx: ToRegIdx).getDefReg(), SubIdx: 0, RegInfo: TRI);
184
185 RegisterIdx UserRegIdx = getDefRegIdx(MI: UserMI);
186 if (UserRegIdx == NoReg)
187 return;
188
189 // When the user is rematerializable, we must reflect the change in its
190 // dependencies.
191 Reg &UserReg = Regs[UserRegIdx];
192 SmallVectorImpl<RegisterIdx> &UserDeps = Regs[UserRegIdx].Dependencies;
193 bool IsNewDep = true;
194 if (UserReg.Defs.size() > 1) {
195 // Other defining MIs might already be using the new register.
196 IsNewDep = !is_contained(Range&: UserDeps, Element: ToRegIdx);
197
198 // If any other defining instruction of the rematerializable user still uses
199 // the original register, we should not remove it from dependencies and may
200 // need to add a new dependency if it is the first time the new register is
201 // used by defining instructions.
202 for (MachineInstr *DefMI : UserReg.Defs) {
203 if (DefMI == &UserMI)
204 continue;
205 for (const MachineOperand &MO : DefMI->all_uses()) {
206 if (MO.getReg() == FromReg) {
207 if (IsNewDep)
208 UserDeps.push_back(Elt: ToRegIdx);
209 return;
210 }
211 }
212 }
213 }
214
215 // No other defining instruction has the original register as user. This
216 // either removes a dependency if the new register was previously used, or is
217 // a simple replacement if not.
218 unsigned *FindFromReg = find(Range&: UserDeps, Val: FromRegIdx);
219 assert(FindFromReg != UserDeps.end() && "broken dependency");
220 if (IsNewDep)
221 *FindFromReg = ToRegIdx;
222 else
223 UserReg.Dependencies.erase(CI: FindFromReg);
224}
225
226bool Rematerializer::isMOIdenticalAtUses(MachineOperand &MO,
227 ArrayRef<SlotIndex> Uses) const {
228 unsigned SubIdx = MO.getSubReg();
229 LaneBitmask Mask = SubIdx ? TRI.getSubRegIndexLaneMask(SubIdx)
230 : MRI.getMaxLaneMaskForVReg(Reg: MO.getReg());
231 return isRegIdenticalAtUses(
232 Reg: MO.getReg(), Mask,
233 RefSlot: LIS.getInstructionIndex(Instr: *MO.getParent()).getRegSlot(EC: true), Uses);
234}
235
236bool Rematerializer::isRegIdenticalAtUses(Register Reg, LaneBitmask Mask,
237 SlotIndex RefSlot,
238 ArrayRef<SlotIndex> Uses) const {
239 if (Uses.empty())
240 return true;
241 const LiveInterval &LI = LIS.getInterval(Reg);
242 const VNInfo *DefVN = LI.getVNInfoAt(Idx: RefSlot);
243 if (!DefVN)
244 return false;
245 for (SlotIndex Use : Uses) {
246 if (!isIdenticalAtUse(OVNI: *DefVN, Mask, UseIdx: Use, LI))
247 return false;
248 }
249 return true;
250}
251
252RegisterIdx Rematerializer::findRematInRegion(RegisterIdx RegIdx,
253 unsigned Region,
254 SlotIndex Before) const {
255 auto It = Rematerializations.find(Val: getOriginOrSelf(RegIdx));
256 if (It == Rematerializations.end())
257 return NoReg;
258 const RematsOf &Remats = It->getSecond();
259
260 SlotIndex BestSlot;
261 RegisterIdx BestRegIdx = NoReg;
262 for (RegisterIdx RematRegIdx : Remats) {
263 const Reg &RematReg = getReg(RegIdx: RematRegIdx);
264 if (RematReg.DefRegion != Region || RematReg.Uses.empty())
265 continue;
266 SlotIndex RematRegSlot =
267 LIS.getInstructionIndex(Instr: *RematReg.getLastDef()).getRegSlot();
268 if (RematRegSlot < Before &&
269 (BestRegIdx == NoReg || RematRegSlot > BestSlot)) {
270 BestSlot = RematRegSlot;
271 BestRegIdx = RematRegIdx;
272 }
273 }
274 return BestRegIdx;
275}
276
277void Rematerializer::deleteReg(RegisterIdx RootIdx) {
278 assert(getReg(RootIdx).Uses.empty() && "register still has uses");
279
280 // Traverse the root's dependency DAG depth-first to find the set of registers
281 // we can delete and a legal order to delete them in.
282 SmallVector<RegisterIdx, 4> DepDAG{RootIdx};
283 SmallVector<RegisterIdx, 8> DeleteOrder{RootIdx};
284 do {
285 // A deleted register's dependencies may be deletable too.
286 const Reg &DeleteReg = getReg(RegIdx: DepDAG.pop_back_val());
287 for (RegisterIdx DepRegIdx : DeleteReg.Dependencies) {
288 // All dependencies lose a user (the deleted register).
289 Reg &DepReg = Regs[DepRegIdx];
290 for (MachineInstr *DefMI : DeleteReg.Defs) {
291 if (DepReg.tryEraseUser(MI: DefMI, Region: DeleteReg.DefRegion) &&
292 DepReg.Uses.empty()) {
293 // The if condition will only be true at most once for any given
294 // register because, once the dependency no longer has any user,
295 // tryEraseUser will always produce false. We can therefore safely use
296 // vectors instead of sets for determining deletable registers.
297 DeleteOrder.push_back(Elt: DepRegIdx);
298 DepDAG.push_back(Elt: DepRegIdx);
299 break;
300 }
301 }
302 }
303 } while (!DepDAG.empty());
304
305 for (RegisterIdx RegIdx : DeleteOrder) {
306 preDeletion(DeleteRegIdx: RegIdx);
307 Reg &DeleteReg = Regs[RegIdx];
308 Register DefReg = DeleteReg.getDefReg();
309 for (MachineInstr *DefMI : reverse(C&: DeleteReg.Defs)) {
310 LIS.RemoveMachineInstrFromMaps(MI&: *DefMI);
311 DefMI->eraseFromParent();
312 }
313 LIS.removeInterval(Reg: DefReg);
314 DeleteReg.Defs.clear();
315 }
316
317 SmallSet<RegisterIdx, 8> ShrinkRematRegs;
318 SmallSet<Register, 8> ShrinkUnrematRegs;
319
320 // All dependencies lose a user; their live interval could be shrunk.
321 for (RegisterIdx DeletedRegIdx : DeleteOrder) {
322 for (RegisterIdx DepRegIdx : getReg(RegIdx: DeletedRegIdx).Dependencies) {
323 const Reg &DepReg = getReg(RegIdx: DepRegIdx);
324 if (DepReg.isAlive() && ShrinkRematRegs.insert(V: DepRegIdx).second) {
325 assert(!DepReg.Uses.empty() && "dep should have uses");
326 shrinkToUses(RegIdx: DepRegIdx);
327 }
328 }
329 for (const auto &[Reg, Mask] : getUnrematableDeps(RegIdx: DeletedRegIdx)) {
330 if (ShrinkUnrematRegs.insert(V: Reg).second)
331 shrinkToUsesUnremat(Reg);
332 }
333 }
334}
335
336void Rematerializer::DeadDefDelegate::LRE_WillEraseInstruction(
337 MachineInstr *MI) {
338 RegisterIdx RegIdx = Remater.getDefRegIdx(MI: *MI);
339 if (RegIdx == Rematerializer::NoReg) {
340 // This is an unrematerializable register.
341 Remater.noteMIWillBeDeleted(MI&: *MI);
342 LLVM_DEBUG(dbgs() << "** About to delete dead definition: " << *MI);
343
344 // Do a linear scan through regions to figure out which one the about to be
345 // deleted unrematerializable MI is a part of. This is expensive but should
346 // happen extremely rarely.
347 //
348 // FIXME: the rematerializer should stop tracking regions and operate on a
349 // machine basic block-basis. This would simplify this and a lot of the
350 // tracking elsewhere.
351 MachineBasicBlock::iterator It = MI->getIterator();
352 const LiveIntervals &LIS = Remater.LIS;
353 SlotIndex MISlot = LIS.getInstructionIndex(Instr: *MI);
354 unsigned MIRegion = ~0U;
355 for (auto [RegionIdx, Bounds] : enumerate(First&: Remater.Regions)) {
356 auto &[RegionBegin, RegionEnd] = Bounds;
357 MachineBasicBlock::iterator FirstMI =
358 skipDebugInstructionsForward(It: RegionBegin, End: RegionEnd);
359 if (FirstMI == RegionEnd) {
360 // The MI cannot be in an empty region.
361 continue;
362 }
363
364 if (LIS.getInstructionIndex(Instr: *FirstMI) <= MISlot) {
365 // FistMI exists inside the region so this is guaranteed to point to a
366 // non-debug MI.
367 MachineBasicBlock::iterator LastMI =
368 skipDebugInstructionsBackward(It: std::prev(x: RegionEnd), Begin: RegionBegin);
369 if (LIS.getInstructionIndex(Instr: *LastMI) < MISlot)
370 continue;
371
372 // We have found the region the MI is a part of.
373 MIRegion = RegionIdx;
374 if (RegionBegin == It)
375 ++RegionBegin;
376 break;
377 }
378 }
379
380 // All rematerializable registers that this MI uses must be notified.
381 SmallDenseSet<Register, 2> UsedRegs;
382 for (const MachineOperand &MO : MI->all_uses()) {
383 Register Reg = MO.getReg();
384 if (Reg.isVirtual() && !UsedRegs.insert(V: Reg).second)
385 continue;
386 auto RematRegUse = Remater.RegToIdx.find(Val: Reg);
387 if (RematRegUse == Remater.RegToIdx.end())
388 continue;
389 assert(MIRegion != ~0U && "remat user cannot be outside regions");
390 Remater.Regs[RematRegUse->second].eraseUser(MI, Region: MIRegion);
391 }
392 return;
393 }
394 // This is a rematerializable register.
395
396 // All rematerializable dependencies must be notified.
397 Reg &DeleteReg = Remater.Regs[RegIdx];
398 for (RegisterIdx DepRegIdx : DeleteReg.Dependencies)
399 Remater.Regs[DepRegIdx].tryEraseUser(MI, Region: DeleteReg.DefRegion);
400
401 // The constraint that no other register reads any intermediate value of a
402 // register defined over multiple MI implies that the live range editor will
403 // either not touch or fully delete rematerializable registers i.e., if this
404 // is called for any defining instruction of a rematerializable register, this
405 // will be called for every definition of the register. Furthermore, def/use
406 // order between defining instructions ensures this will be called from last
407 // definition to first definition. When the last definition / first MI
408 // deletion happens, we want to reflect the deletion in our internal
409 // data-structures and notify any rematerializer listener.
410 if (!DeleteReg.isAlive())
411 return;
412 assert(DeleteReg.getLastDef() == MI && "last def should be deleted first");
413 assert(DeleteReg.Uses.empty() && "register should no longer have uses");
414
415 // The live-reange editor will delete all defining instructions from the MIR
416 // as well as the register's live-range, so we just need to clear out the defs
417 // vector.
418 Remater.preDeletion(DeleteRegIdx: RegIdx);
419 DeleteReg.Defs.clear();
420}
421
422void Rematerializer::preDeletion(RegisterIdx DeleteRegIdx) {
423 Reg &DeleteReg = Regs[DeleteRegIdx];
424 assert(DeleteReg.isAlive() && "register must still be alive");
425 noteRegWillBeDeleted(RegIdx: DeleteRegIdx);
426 LLVM_DEBUG(dbgs() << "** About to delete " << printID(DeleteRegIdx) << "\n");
427
428 // Update region boundary if necessary. It is not possible for the deleted
429 // instruction to be the upper region boundary since we don't ever consider
430 // them rematerializable.
431 MachineBasicBlock::iterator &RegionBegin = Regions[DeleteReg.DefRegion].first;
432 for (MachineInstr *DefMI : DeleteReg.Defs) {
433 if (RegionBegin != DefMI)
434 break;
435 ++RegionBegin;
436 }
437
438 if (isOriginalRegister(RegIdx: DeleteRegIdx))
439 return;
440
441 // Delete rematerialized register from its origin's rematerializations.
442 const RegisterIdx OriginIdx = getOriginOf(RematRegIdx: DeleteRegIdx);
443 RematsOf &OriginRemats = Rematerializations.at(Val: OriginIdx);
444 assert(OriginRemats.contains(DeleteRegIdx) && "broken remat<->origin link");
445 OriginRemats.erase(V: DeleteRegIdx);
446 if (OriginRemats.empty())
447 Rematerializations.erase(Val: OriginIdx);
448}
449
450Rematerializer::Rematerializer(MachineFunction &MF,
451 SmallVectorImpl<RegionBoundaries> &Regions,
452 LiveIntervals &LIS)
453 : Regions(Regions), MRI(MF.getRegInfo()), LIS(LIS),
454 TII(*MF.getSubtarget().getInstrInfo()), TRI(TII.getRegisterInfo()) {
455#ifdef EXPENSIVE_CHECKS
456 // Check that regions are valid.
457 DenseSet<MachineInstr *> SeenMIs;
458 for (const auto &[RegionBegin, RegionEnd] : Regions) {
459 assert(RegionBegin != RegionEnd && "empty region");
460 for (auto MI = RegionBegin; MI != RegionEnd; ++MI) {
461 bool IsNewMI = SeenMIs.insert(&*MI).second;
462 assert(IsNewMI && "overlapping regions");
463 assert(!MI->isTerminator() && "terminator in region");
464 }
465 if (RegionEnd != RegionBegin->getParent()->end()) {
466 bool IsNewMI = SeenMIs.insert(&*RegionEnd).second;
467 assert(IsNewMI && "overlapping regions (upper bound)");
468 }
469 }
470#endif
471}
472
473bool Rematerializer::analyze() {
474 Regs.clear();
475 UnrematableDeps.clear();
476 Origins.clear();
477 Rematerializations.clear();
478 RegionMBB.clear();
479 RegToIdx.clear();
480 if (Regions.empty())
481 return false;
482
483 /// Maps all MIs to their parent region. Region terminators are considered
484 /// part of the region they terminate.
485 DenseMap<MachineInstr *, unsigned> MIRegion;
486
487 // Initialize MI to containing region mapping.
488 RegionMBB.reserve(N: Regions.size());
489 for (unsigned I = 0, E = Regions.size(); I < E; ++I) {
490 RegionBoundaries Region = Regions[I];
491 assert(Region.first != Region.second && "empty cannot be region");
492 for (auto MI = Region.first; MI != Region.second; ++MI) {
493 assert(!MIRegion.contains(&*MI) && "regions should not intersect");
494 MIRegion.insert(KV: {&*MI, I});
495 }
496 MachineBasicBlock &MBB = *Region.first->getParent();
497 RegionMBB.push_back(Elt: &MBB);
498
499 // A terminator instruction is considered part of the region it terminates.
500 if (Region.second != MBB.end()) {
501 MachineInstr *RegionTerm = &*Region.second;
502 assert(!MIRegion.contains(RegionTerm) && "regions should not intersect");
503 MIRegion.insert(KV: {RegionTerm, I});
504 }
505 }
506
507 const unsigned NumVirtRegs = MRI.getNumVirtRegs();
508 BitVector SeenRegs(NumVirtRegs);
509 for (unsigned I = 0, E = NumVirtRegs; I != E; ++I) {
510 if (!SeenRegs[I])
511 addRegIfRematerializable(VirtRegIdx: I, MIRegion, SeenRegs);
512 }
513 assert(Regs.size() == UnrematableDeps.size());
514
515 LLVM_DEBUG({
516 for (RegisterIdx I = 0, E = getNumRegs(); I < E; ++I)
517 dbgs() << printDependencyDAG(I) << '\n';
518 });
519 return !Regs.empty();
520}
521
522void Rematerializer::addRegIfRematerializable(
523 unsigned VirtRegIdx, const DenseMap<MachineInstr *, unsigned> &MIRegion,
524 BitVector &SeenRegs) {
525 assert(!SeenRegs[VirtRegIdx] && "register already seen");
526 Register DefReg = Register::index2VirtReg(Index: VirtRegIdx);
527 SeenRegs.set(VirtRegIdx);
528 Reg RematReg;
529
530 // Check that the register's definitions can be rematerialized.
531 SmallPtrSet<MachineInstr *, 1> DefSet;
532 for (MachineInstr &DefMI : MRI.def_instructions(Reg: DefReg)) {
533 // If a single MI has multiple defs for the same register, we don't need to
534 // redo MI-based checks.
535 if (!DefSet.insert(Ptr: &DefMI).second)
536 continue;
537
538 // The defining MI must be rematerializable and in the same region as all
539 // other defining MIs.
540 if (!isMIRematerializable(MI: DefMI))
541 return;
542 auto DefRegion = MIRegion.find(Val: &DefMI);
543 if (DefRegion == MIRegion.end())
544 return;
545 if (RematReg.Defs.empty())
546 RematReg.DefRegion = DefRegion->getSecond();
547 else if (RematReg.DefRegion != DefRegion->getSecond())
548 return;
549 RematReg.Defs.push_back(Elt: &DefMI);
550 }
551 if (RematReg.Defs.empty())
552 return;
553
554 // Order defining MIs by slot index.
555 sort(C&: RematReg.Defs, Comp: [&](MachineInstr *LHS, MachineInstr *RHS) {
556 return LIS.getInstructionIndex(Instr: *LHS) < LIS.getInstructionIndex(Instr: *RHS);
557 });
558 // None of the non-first register defintions can be marked undef.
559 for (const MachineInstr *DefMI : drop_begin(RangeOrContainer&: RematReg.Defs)) {
560 for (const MachineOperand &DefMO : DefMI->all_defs()) {
561 if (DefMO.getReg() == DefReg && DefMO.isUndef())
562 return;
563 }
564 }
565
566 SlotIndex LastDefSlot = LIS.getInstructionIndex(Instr: *RematReg.getLastDef());
567
568 // Set the register's mask to all active lanes after the last def.
569 const LiveInterval &DefLI = LIS.getInterval(Reg: DefReg);
570 SlotIndex AfterLastDef = LastDefSlot.getRegSlot();
571 if (DefLI.hasSubRanges()) {
572 for (const LiveInterval::SubRange &SR : DefLI.subranges())
573 if (SR.liveAt(index: AfterLastDef))
574 RematReg.Mask |= SR.LaneMask;
575 } else {
576 RematReg.Mask = MRI.getMaxLaneMaskForVReg(Reg: DefReg);
577 }
578
579 // Collect the candidate's direct users, both rematerializable and
580 // unrematerializable.
581 const bool MoreThanOneDef = RematReg.Defs.size() > 1;
582 for (MachineInstr &UseMI : MRI.use_nodbg_instructions(Reg: DefReg)) {
583 // We are only interested in users that do not define part of the register.
584 if (DefSet.contains(Ptr: &UseMI))
585 continue;
586 // MIs outside provided regions cannot be tracked so the registers they use
587 // are not safely rematerializable.
588 auto UseRegion = MIRegion.find(Val: &UseMI);
589 if (UseRegion == MIRegion.end())
590 return;
591 // Disallow reads before the last def.
592 if (MoreThanOneDef && RematReg.DefRegion == UseRegion->second &&
593 LastDefSlot > LIS.getInstructionIndex(Instr: UseMI))
594 return;
595
596 RematReg.addUser(MI: &UseMI, Region: UseRegion->second);
597 }
598 if (RematReg.Uses.empty())
599 return;
600
601 // Collect the candidate's dependencies, rematerializable or not. If the same
602 // rematerializable register is used multiple times we just need to consider
603 // it once.
604 SmallSetVector<RegisterIdx, 2> RematDeps;
605 SmallMapVector<Register, LaneBitmask, 2> UnrematDeps;
606 for (const MachineInstr *DefMI : RematReg.Defs) {
607 for (const MachineOperand &MO : DefMI->all_uses()) {
608 Register DepReg = getRegDependency(MO);
609 if (!DepReg || DepReg == DefReg)
610 continue;
611 unsigned DepRegIdx = DepReg.virtRegIndex();
612 if (!SeenRegs[DepRegIdx])
613 addRegIfRematerializable(VirtRegIdx: DepRegIdx, MIRegion, SeenRegs);
614 if (auto DepIt = RegToIdx.find(Val: DepReg); DepIt != RegToIdx.end()) {
615 RematDeps.insert(X: DepIt->second);
616 } else {
617 LaneBitmask &CurrentMask =
618 UnrematDeps.try_emplace(Key: DepReg, Args: LaneBitmask::getNone())
619 .first->second;
620 LaneBitmask Mask = MO.getSubReg()
621 ? TRI.getSubRegIndexLaneMask(SubIdx: MO.getSubReg())
622 : MRI.getMaxLaneMaskForVReg(Reg: DepReg);
623 CurrentMask |= Mask;
624 }
625 }
626 }
627
628 if (MoreThanOneDef) {
629 // A def of an unrematerializable dependency between the defs of the
630 // register under consideration makes the latter unrematerializable.
631 SlotIndex FirstDefSlot = LIS.getInstructionIndex(Instr: *RematReg.getFirstDef());
632 for (const auto &[UnrematDepReg, _] : UnrematDeps) {
633 for (MachineInstr &UnrematDefMI : MRI.def_instructions(Reg: UnrematDepReg)) {
634 SlotIndex UnrematDefSlot = LIS.getInstructionIndex(Instr: UnrematDefMI);
635 if (UnrematDefSlot > FirstDefSlot || UnrematDefSlot < LastDefSlot)
636 return;
637 }
638 }
639 }
640
641 // The register is rematerializable.
642 RematReg.Dependencies = RematDeps.takeVector();
643 RegToIdx.insert(KV: {DefReg, Regs.size()});
644 Regs.push_back(Elt: RematReg);
645 UnrematableDeps.push_back(Elt: UnrematDeps.takeVector());
646}
647
648bool Rematerializer::isMIRematerializable(const MachineInstr &MI) const {
649 if (!TII.isReMaterializable(MI))
650 return false;
651
652 assert(MI.getOperand(0).getReg().isVirtual() && "should be virtual");
653
654 for (const MachineOperand &MO : MI.all_uses()) {
655 // We can't remat physreg uses, unless it is a constant or an ignorable
656 // use (e.g. implicit exec use on VALU instructions)
657 if (MO.getReg().isPhysical()) {
658 if (MRI.isConstantPhysReg(PhysReg: MO.getReg()) ||
659 TII.isIgnorableUse(MI, OpIdx: MI.getOperandNo(I: &MO)))
660 continue;
661 return false;
662 }
663 }
664
665 return true;
666}
667
668RegisterIdx Rematerializer::getDefRegIdx(const MachineInstr &MI) const {
669 if (!MI.getNumOperands() || !MI.getOperand(i: 0).isReg() ||
670 !MI.getOperand(i: 0).isDef())
671 return NoReg;
672 Register Reg = MI.getOperand(i: 0).getReg();
673 auto UserRegIt = RegToIdx.find(Val: Reg);
674 if (UserRegIt == RegToIdx.end())
675 return NoReg;
676 return UserRegIt->second;
677}
678
679RegisterIdx
680Rematerializer::rematerializeReg(RegisterIdx RegIdx, unsigned UseRegion,
681 MachineBasicBlock::iterator InsertPos,
682 SmallVectorImpl<RegisterIdx> &&Dependencies) {
683 RegisterIdx NewRegIdx = Regs.size();
684
685 Reg &NewReg = Regs.emplace_back();
686 Reg &FromReg = Regs[RegIdx];
687 NewReg.Mask = FromReg.Mask;
688 NewReg.DefRegion = UseRegion;
689 NewReg.Defs.reserve(N: FromReg.Defs.size());
690 NewReg.Dependencies = std::move(Dependencies);
691
692 // Track rematerialization link between registers. Origins are always
693 // registers that existed originally, and rematerializations are always
694 // attached to them.
695 const RegisterIdx OriginIdx = getOriginOrSelf(RegIdx);
696 Origins.push_back(Elt: OriginIdx);
697 Rematerializations[OriginIdx].insert(V: NewRegIdx);
698
699 // Use the TII to rematerialize the defining instruction with a new defined
700 // register.
701 Register NewDefReg = MRI.cloneVirtualRegister(VReg: FromReg.getDefReg());
702 for (const MachineInstr *DefMI : FromReg.Defs) {
703 TII.reMaterialize(MBB&: *RegionMBB[UseRegion], MI: InsertPos, DestReg: NewDefReg, SubIdx: 0, Orig: *DefMI);
704 NewReg.Defs.push_back(Elt: &*std::prev(x: InsertPos));
705 }
706 RegToIdx.insert(KV: {NewDefReg, NewRegIdx});
707 postRematerialization(ModelRegIdx: RegIdx, RematRegIdx: NewRegIdx);
708
709 noteRegCreated(RegIdx: NewRegIdx);
710 LLVM_DEBUG(dbgs() << "** Rematerialized " << printID(RegIdx) << " as "
711 << printRematReg(NewRegIdx) << '\n');
712 return NewRegIdx;
713}
714
715void Rematerializer::recreateReg(
716 RegisterIdx RegIdx, ArrayRef<MachineBasicBlock::iterator> Positions,
717 Register DefReg) {
718 assert(RegToIdx.contains(DefReg) && "unknown defined register");
719 assert(RegToIdx.at(DefReg) == RegIdx && "incorrect defined register");
720 assert(!getReg(RegIdx).isAlive() && "register is still alive");
721 Reg &OriginReg = Regs[RegIdx];
722
723 // Re-establish the link between origin and rematerialization if necessary.
724 const bool RecreateOriginalReg = isOriginalRegister(RegIdx);
725 if (!RecreateOriginalReg)
726 Rematerializations[getOriginOf(RematRegIdx: RegIdx)].insert(V: RegIdx);
727
728 // Rematerialize from one of the existing rematerializations or from the
729 // origin. We expect at least one to exist, otherwise it would mean the value
730 // held by the original register is no longer available anywhere in the MF.
731 RegisterIdx ModelRegIdx;
732 if (RecreateOriginalReg) {
733 assert(Rematerializations.contains(RegIdx) && "expected remats");
734 ModelRegIdx = *Rematerializations.at(Val: RegIdx).begin();
735 } else {
736 assert(getReg(getOriginOf(RegIdx)).isAlive() && "expected alive origin");
737 ModelRegIdx = getOriginOf(RematRegIdx: RegIdx);
738 }
739 const Reg &ModelReg = getReg(RegIdx: ModelRegIdx);
740
741 for (auto [DefMI, InsertPos] : zip_equal(t: ModelReg.Defs, u&: Positions)) {
742 TII.reMaterialize(MBB&: *RegionMBB[OriginReg.DefRegion], MI: InsertPos, DestReg: DefReg, SubIdx: 0,
743 Orig: *DefMI);
744 OriginReg.Defs.push_back(Elt: &*std::prev(x: InsertPos));
745 }
746 postRematerialization(ModelRegIdx, RematRegIdx: RegIdx);
747 LLVM_DEBUG(dbgs() << "** Recreated " << printID(RegIdx) << " as "
748 << printRematReg(RegIdx) << '\n');
749}
750
751void Rematerializer::postRematerialization(RegisterIdx ModelRegIdx,
752 RegisterIdx RematRegIdx) {
753 Reg &ModelReg = Regs[ModelRegIdx], &RematReg = Regs[RematRegIdx];
754
755 SlotIndex UseIdx;
756 for (MachineInstr *DefMI : RematReg.Defs)
757 UseIdx = LIS.InsertMachineInstrInMaps(MI&: *DefMI);
758 UseIdx = UseIdx.getRegSlot();
759
760 // The rematerialization has no user at this point so its interval will
761 // initially be empty.
762 LIS.createAndComputeVirtRegInterval(Reg: RematReg.getDefReg());
763
764 // The start of the new register's region may have changed.
765 MachineInstr &FirstDefMI = *RematReg.getFirstDef();
766 auto &[RegionBegin, RegionEnd] = Regions[RematReg.DefRegion];
767 if (RegionBegin == RegionEnd ||
768 (!RegionBegin->isDebugInstr() && LIS.getInstructionIndex(Instr: *RegionBegin) >
769 LIS.getInstructionIndex(Instr: FirstDefMI)))
770 RegionBegin = FirstDefMI.getIterator();
771
772 // Replace dependencies as needed in the rematerialized MI. All dependencies
773 // of the latter gain a new user.
774 auto ZipedDeps = zip_equal(t&: ModelReg.Dependencies, u&: RematReg.Dependencies);
775 for (const auto &[OldDepRegIdx, NewDepRegIdx] : ZipedDeps) {
776 LLVM_DEBUG(dbgs() << " Dependency: " << printID(OldDepRegIdx) << " -> "
777 << printID(NewDepRegIdx) << '\n');
778 Register OldReg = getReg(RegIdx: OldDepRegIdx).getDefReg();
779 Register NewReg = getReg(RegIdx: NewDepRegIdx).getDefReg();
780
781 SmallVector<MachineInstr *, 2> DefsUsingNewDep;
782 for (MachineInstr *DefMI : RematReg.Defs) {
783 bool NewDefHasReg = false;
784 for (MachineOperand &MO : DefMI->operands()) {
785 if (!MO.isReg() || MO.getReg() != OldReg)
786 continue;
787 NewDefHasReg = true;
788 DefsUsingNewDep.push_back(Elt: DefMI);
789 if (OldDepRegIdx != NewDepRegIdx)
790 MO.substVirtReg(Reg: NewReg, SubIdx: 0, TRI);
791 }
792 if (NewDefHasReg)
793 Regs[NewDepRegIdx].addUser(MI: DefMI, Region: RematReg.DefRegion);
794 }
795 assert(!DefsUsingNewDep.empty() && "no user of dependency");
796 extendToNewUsers(RegIdx: NewDepRegIdx, NewUsers: DefsUsingNewDep);
797 }
798
799 // Unrematerializable dependencies always gain a new user after a
800 // rematerialization; their live range may need to be extended.
801 for (const auto &[Reg, Mask] : getUnrematableDeps(RegIdx: ModelRegIdx))
802 extendInterval(LI&: LIS.getInterval(Reg), Mask, UseIdx);
803}
804
805void Rematerializer::extendToNewUsers(RegisterIdx RegIdx,
806 ArrayRef<MachineInstr *> NewUsers) const {
807 if (NewUsers.empty())
808 return;
809 const Reg &ExtendReg = getReg(RegIdx);
810 assert(ExtendReg.isAlive() && "register must be alive");
811
812 Register DefReg = ExtendReg.getDefReg();
813 LiveInterval &LI = LIS.getInterval(Reg: DefReg);
814 const LaneBitmask FullLaneMask = MRI.getMaxLaneMaskForVReg(Reg: DefReg);
815 const bool ShouldTrackSubReg = MRI.shouldTrackSubRegLiveness(VReg: DefReg);
816
817 // Seed subranges from the main range when subreg liveness is tracked but no
818 // subrange exists yet. VirtRegRewriter later requires subranges even when a
819 // new user reads the full mask, because other users may read subregs.
820 if (!LI.hasSubRanges() && ShouldTrackSubReg)
821 LI.createSubRangeFrom(Allocator&: LIS.getVNInfoAllocator(), LaneMask: FullLaneMask, CopyFrom: LI);
822
823 // Extend all ranges in the register's live interval so that they reach the
824 // new users.
825 for (MachineInstr *UserMI : NewUsers) {
826 SlotIndex UseIdx = LIS.getInstructionIndex(Instr: *UserMI).getRegSlot();
827
828 // Derive register lanes read by that user.
829 LaneBitmask RegMask;
830 for (MachineOperand &MO : UserMI->all_uses()) {
831 if (MO.getReg() == DefReg) {
832 unsigned SubIdx = MO.getSubReg();
833 if (SubIdx == 0) {
834 RegMask = FullLaneMask;
835 break;
836 }
837 RegMask |= TRI.getSubRegIndexLaneMask(SubIdx);
838 }
839 }
840
841 if (RegMask != FullLaneMask) {
842 // Refine sub-ranges to be able to track the mask for that user.
843 LI.refineSubRanges(
844 Allocator&: LIS.getVNInfoAllocator(), LaneMask: RegMask, Apply: [](LiveInterval::SubRange &SR) {},
845 Indexes: *LIS.getSlotIndexes(), TRI);
846 // Refining may have introduced empty sub-ranges, which are illegal.
847 LI.removeEmptySubRanges();
848 }
849 extendInterval(LI, Mask: RegMask, UseIdx);
850 }
851
852 // Rematerializable registers are never read by instructions not defining them
853 // until after their last def, so adding a user to them ensures their last
854 // definition is alive. All potential other definitions are read by the last
855 // definition and are therefore already alive by construction.
856 LLVM_DEBUG({
857 if (ExtendReg.getLastDef()->getOperand(0).isDead())
858 dbgs() << "Clearing dead flag for "
859 << printRematReg(RegIdx, /*SkipRegions=*/false,
860 /*DefIdx=*/ExtendReg.Defs.size() - 1)
861 << '\n';
862 });
863 ExtendReg.getLastDef()->getOperand(i: 0).setIsDead(false);
864}
865
866void Rematerializer::extendInterval(LiveInterval &LI, LaneBitmask Mask,
867 SlotIndex UseIdx) const {
868 if (!LI.hasSubRanges()) {
869 if (!LI.liveAt(index: UseIdx))
870 LLVM_DEBUG(dbgs() << "Extending interval of register "
871 << printReg(LI.reg(), &TRI, 0, &MRI) << " to " << UseIdx
872 << '\n');
873 LIS.extendToIndices(LR&: LI, Indices: UseIdx);
874 return;
875 }
876
877 bool SubRangeExtended = false;
878 for (LiveInterval::SubRange &SR : LI.subranges()) {
879 if ((SR.LaneMask & Mask).any() && !SR.liveAt(index: UseIdx)) {
880 SubRangeExtended = true;
881 LLVM_DEBUG(dbgs() << "Extending subrange " << SR << " of register "
882 << printReg(LI.reg(), &TRI, 0, &MRI) << " to " << UseIdx
883 << '\n');
884 LIS.extendToIndices(LR&: SR, Indices: UseIdx);
885 }
886 }
887 if (!SubRangeExtended)
888 return;
889
890 // FIXME: this fully reconstructs the main live range from scratch, but
891 // there may be a more targeted way to make the update.
892 LI.clear();
893 LIS.constructMainRangeFromSubranges(LI);
894}
895
896void Rematerializer::shrinkToUses(RegisterIdx RegIdx) {
897 Reg &ShrinkReg = Regs[RegIdx];
898 assert(ShrinkReg.isAlive() && "register must be alive");
899 if (ShrinkReg.Uses.empty()) {
900 deleteReg(RootIdx: RegIdx);
901 return;
902 }
903
904 // By construction, registers should never end up with multiple disconnected
905 // components or dead definitions.
906 LiveInterval &LI = LIS.getInterval(Reg: ShrinkReg.getDefReg());
907 LLVM_DEBUG(dbgs() << "Shrinking interval of " << printID(RegIdx) << ": " << LI
908 << '\n');
909 LIS.shrinkToUses(li: &LI);
910}
911
912void Rematerializer::shrinkToUsesUnremat(Register Reg) {
913 LiveInterval &LI = LIS.getInterval(Reg);
914 LLVM_DEBUG(dbgs() << "Shrinking interval of unrematerializable register "
915 << LI << '\n');
916
917 SmallVector<MachineInstr *, 2> DeadDefs;
918 if (!LIS.shrinkToUses(li: &LI, dead: &DeadDefs)) {
919 assert(DeadDefs.empty() && "expected no dead def");
920 return;
921 }
922
923 // This should be a very rare occurence, but shrinking an unrematerializable
924 // register could create dead defs.
925 if (DeadDefs.empty())
926 return;
927
928 // The live-range editor delegate will take care of reflecting the
929 // elimination of all dead definitions in the rematerializer.
930 SmallVector<Register, 4> NewRegs;
931 DeadDefDelegate DeadDefDeleg(*this);
932 MachineFunction &MF = *DeadDefs.front()->getParent()->getParent();
933 LiveRangeEdit(nullptr, NewRegs, MF, LIS, nullptr, &DeadDefDeleg)
934 .eliminateDeadDefs(Dead&: DeadDefs);
935}
936
937std::pair<MachineInstr *, MachineInstr *>
938Rematerializer::Reg::getRegionUseBounds(unsigned UseRegion,
939 const LiveIntervals &LIS) const {
940 auto It = Uses.find(Val: UseRegion);
941 if (It == Uses.end())
942 return {nullptr, nullptr};
943 const RegionUsers &RegionUsers = It->getSecond();
944 assert(!RegionUsers.empty() && "empty userset in region");
945
946 auto User = RegionUsers.begin(), UserEnd = RegionUsers.end();
947 MachineInstr *FirstMI = *User, *LastMI = FirstMI;
948 SlotIndex FirstIndex = LIS.getInstructionIndex(Instr: *FirstMI),
949 LastIndex = FirstIndex;
950
951 while (++User != UserEnd) {
952 SlotIndex UserIndex = LIS.getInstructionIndex(Instr: **User);
953 if (UserIndex < FirstIndex) {
954 FirstIndex = UserIndex;
955 FirstMI = *User;
956 } else if (UserIndex > LastIndex) {
957 LastIndex = UserIndex;
958 LastMI = *User;
959 }
960 }
961
962 return {FirstMI, LastMI};
963}
964
965void Rematerializer::Reg::addUser(MachineInstr *MI, unsigned Region) {
966 Uses[Region].insert(V: MI);
967}
968
969void Rematerializer::Reg::addUsers(const RegionUsers &NewUsers,
970 unsigned Region) {
971 Uses[Region].insert_range(R: NewUsers);
972}
973
974void Rematerializer::Reg::eraseUser(MachineInstr *MI, unsigned Region) {
975 RegionUsers &RUsers = Uses.at(Val: Region);
976 assert(RUsers.contains(MI) && "user not in region");
977 if (RUsers.size() == 1)
978 Uses.erase(Val: Region);
979 else
980 RUsers.erase(V: MI);
981}
982
983bool Rematerializer::Reg::tryEraseUser(MachineInstr *MI, unsigned Region) {
984 auto RegionUsers = Uses.find(Val: Region);
985 if (RegionUsers == Uses.end() || !RegionUsers->getSecond().erase(V: MI))
986 return false;
987 if (RegionUsers->getSecond().empty())
988 Uses.erase(Val: Region);
989 return true;
990}
991
992Printable Rematerializer::printDependencyDAG(RegisterIdx RootIdx) const {
993 return Printable([&, RootIdx](raw_ostream &OS) {
994 DenseMap<RegisterIdx, unsigned> RegDepths;
995 std::function<void(RegisterIdx, unsigned)> WalkTree =
996 [&](RegisterIdx RegIdx, unsigned Depth) -> void {
997 unsigned MaxDepth = std::max(a: RegDepths.lookup_or(Val: RegIdx, Default&: Depth), b: Depth);
998 RegDepths.emplace_or_assign(Key: RegIdx, Args&: MaxDepth);
999 for (RegisterIdx DepRegIdx : getReg(RegIdx).Dependencies)
1000 WalkTree(DepRegIdx, Depth + 1);
1001 };
1002 WalkTree(RootIdx, 0);
1003
1004 // Sort in decreasing depth order to print root at the bottom.
1005 SmallVector<std::pair<RegisterIdx, unsigned>> Regs(RegDepths.begin(),
1006 RegDepths.end());
1007 sort(C&: Regs, Comp: [](const auto &LHS, const auto &RHS) {
1008 return LHS.second > RHS.second;
1009 });
1010
1011 OS << printID(RegIdx: RootIdx) << " has " << Regs.size() - 1 << " dependencies\n";
1012 for (const auto &[RegIdx, Depth] : Regs) {
1013 OS << indent(Depth, 2) << (Depth ? '|' : '*') << ' '
1014 << printRematReg(RegIdx, /*SkipRegions=*/Depth) << '\n';
1015 }
1016 OS << printRegUsers(RegIdx: RootIdx);
1017 });
1018}
1019
1020Printable Rematerializer::printID(RegisterIdx RegIdx) const {
1021 return Printable([&, RegIdx](raw_ostream &OS) {
1022 const Reg &PrintReg = getReg(RegIdx);
1023 OS << '(' << RegIdx << '/';
1024 if (!PrintReg.isAlive())
1025 OS << "<dead>";
1026 else
1027 OS << printReg(Reg: PrintReg.getDefReg(), TRI: &TRI, SubIdx: 0, MRI: &MRI);
1028 OS << ")[" << PrintReg.DefRegion << "]";
1029 });
1030}
1031
1032Printable Rematerializer::printRematReg(RegisterIdx RegIdx, bool SkipRegions,
1033 unsigned DefIdx) const {
1034 return Printable([&, RegIdx, SkipRegions, DefIdx](raw_ostream &OS) {
1035 const Reg &PrintReg = getReg(RegIdx);
1036 OS << printID(RegIdx);
1037 if (!SkipRegions) {
1038 OS << " [" << PrintReg.DefRegion;
1039 if (!PrintReg.Uses.empty()) {
1040 assert(PrintReg.isAlive() && "dead register cannot have uses");
1041 const LiveInterval &LI = LIS.getInterval(Reg: PrintReg.getDefReg());
1042 // First display all regions in which the register is live-through and
1043 // not used.
1044 bool First = true;
1045 for (const auto &[I, Bounds] : enumerate(First&: Regions)) {
1046 if (PrintReg.Uses.contains(Val: I))
1047 continue;
1048 // The register must be live at the live-ins and live-outs of the
1049 // region.
1050 MachineBasicBlock::iterator LiveIn =
1051 skipDebugInstructionsForward(It: Bounds.first, End: Bounds.second);
1052 if (LiveIn == Bounds.second) {
1053 // The region has no non-debug instructions, it's hard to assess
1054 // whether the register is live across it without an index.
1055 continue;
1056 }
1057 // LiveIn is inside the range and a non-debug instruction so we know
1058 // this will also point to a non-debug instruction within the region.
1059 MachineBasicBlock::iterator LiveOut = skipDebugInstructionsBackward(
1060 It: std::prev(x: Bounds.second), Begin: Bounds.first);
1061 if (LI.liveAt(index: LIS.getInstructionIndex(Instr: *LiveIn)) &&
1062 LI.liveAt(index: LIS.getInstructionIndex(Instr: *LiveOut).getDeadSlot())) {
1063 OS << (First ? " - " : ",") << I;
1064 First = false;
1065 }
1066 }
1067 OS << (First ? " --> " : " -> ");
1068
1069 // Then display regions in which the register is used.
1070 auto It = PrintReg.Uses.begin();
1071 OS << It->first;
1072 while (++It != PrintReg.Uses.end())
1073 OS << "," << It->first;
1074 }
1075 OS << "] ";
1076 }
1077 if (PrintReg.isAlive()) {
1078 assert(DefIdx < PrintReg.Defs.size() && "out-of-bound def");
1079 MachineInstr &PrintDef = *PrintReg.Defs[DefIdx];
1080 OS << "(def. " << DefIdx + 1 << " / " << PrintReg.Defs.size() << ") ";
1081 PrintDef.print(OS, /*IsStandalone=*/true, /*SkipOpers=*/false,
1082 /*SkipDebugLoc=*/false, /*AddNewLine=*/false);
1083 OS << " @ ";
1084 LIS.getInstructionIndex(Instr: PrintDef).print(os&: OS);
1085 }
1086 });
1087}
1088
1089Printable Rematerializer::printRegUsers(RegisterIdx RegIdx) const {
1090 return Printable([&, RegIdx](raw_ostream &OS) {
1091 for (const auto &[UseRegion, Users] : getReg(RegIdx).Uses) {
1092 for (MachineInstr *MI : Users)
1093 OS << " User " << printUser(MI, UseRegion) << '\n';
1094 }
1095 });
1096}
1097
1098Printable Rematerializer::printUser(const MachineInstr *MI,
1099 std::optional<unsigned> UseRegion) const {
1100 return Printable([&, MI, UseRegion](raw_ostream &OS) {
1101 RegisterIdx RegIdx = getDefRegIdx(MI: *MI);
1102 if (RegIdx != NoReg) {
1103 OS << printID(RegIdx);
1104 } else {
1105 OS << "(-/-)[";
1106 if (UseRegion)
1107 OS << *UseRegion;
1108 else
1109 OS << '?';
1110 OS << ']';
1111 }
1112 OS << ' ';
1113 MI->print(OS, /*IsStandalone=*/true, /*SkipOpers=*/false,
1114 /*SkipDebugLoc=*/false, /*AddNewLine=*/false);
1115 OS << " @ ";
1116 LIS.getInstructionIndex(Instr: *MI).print(os&: OS);
1117 });
1118}
1119
1120void Rollbacker::rematerializerNoteRegCreated(const Rematerializer &Remater,
1121 RegisterIdx RegIdx) {
1122 if (RollingBack)
1123 return;
1124 assert(Remater.isRematerializedRegister(RegIdx) && "only remats are created");
1125 Rematerializations[Remater.getOriginOf(RematRegIdx: RegIdx)].insert(V: RegIdx);
1126}
1127
1128void Rollbacker::rematerializerNoteRegWillBeDeleted(
1129 const Rematerializer &Remater, RegisterIdx RegIdx) {
1130 if (RollingBack)
1131 return;
1132
1133 const Rematerializer::Reg &Reg = Remater.getReg(RegIdx);
1134 MachineBasicBlock *ParentMBB = Reg.getFirstDef()->getParent();
1135 MachineBasicBlock::iterator LastValidPos;
1136
1137 auto GetNextValidPosAfterDef =
1138 [&](unsigned DefIdx) -> MachineBasicBlock::iterator {
1139 const MachineInstr *NextDef =
1140 DefIdx + 1 < Reg.Defs.size() ? Reg.Defs[DefIdx + 1] : nullptr;
1141 MachineBasicBlock::iterator ValidPos =
1142 std::next(x: Reg.Defs[DefIdx]->getIterator());
1143
1144 while (ValidPos != ParentMBB->end()) {
1145 // When there are no valid insert positions between the current and next
1146 // definition of the register about to be deleted, the first valid insert
1147 // position for the current definition is the same as for the next
1148 // definition.
1149 const MachineInstr &CandMI = *ValidPos;
1150 if (NextDef && &CandMI == NextDef)
1151 return LastValidPos;
1152 if (!isRollbackableMI(MI: CandMI, Remater))
1153 break;
1154
1155 // Move to the next candidate position.
1156 ValidPos = std::next(x: ValidPos);
1157 }
1158
1159 LastValidPos = ValidPos;
1160 return ValidPos;
1161 };
1162
1163 if (Remater.isRematerializedRegister(RegIdx)) {
1164 // Rematerializations will not be re-created. Previously deleted registers
1165 // that reference this register's defining instructions as their re-creation
1166 // position should instead be re-created at a valid position after the
1167 // deleted MIs.
1168 for (unsigned I = Reg.Defs.size(); I > 0; --I)
1169 invalidatePosition(MI: Reg.Defs[I - 1], It: GetNextValidPosAfterDef(I - 1));
1170 return;
1171 }
1172
1173 // Original registers can be re-created. Add a re-creation position for each
1174 // definition of the rematerializable register.
1175 DeadRegs.push_back(Elt: DeadReg(RegIdx, Remater));
1176 for (unsigned I = Reg.Defs.size(); I > 0; --I) {
1177 const InsertBeforePos InsertPos =
1178 makePos(It: GetNextValidPosAfterDef(I - 1), MBB: ParentMBB);
1179 PosToIdx[InsertPos].insert(V: Positions.size());
1180 Positions.push_back(Elt: InsertPos);
1181 }
1182}
1183
1184void Rollbacker::rematerializerNoteMIWillBeDeleted(
1185 const Rematerializer &Remater, MachineInstr &MI) {
1186 if (RollingBack)
1187 return;
1188
1189 // Previously deleted registers that reference this MI as their re-creation
1190 // position should instead be re-created at a valid position after it.
1191 MachineBasicBlock *ParentMBB = MI.getParent();
1192 MachineBasicBlock::iterator ValidPos = std::next(x: MI.getIterator());
1193 while (ValidPos != ParentMBB->end() && isRollbackableMI(MI: *ValidPos, Remater))
1194 ValidPos = std::next(x: ValidPos);
1195 invalidatePosition(MI: &MI, It: ValidPos);
1196}
1197
1198void Rollbacker::rollback(Rematerializer &Remater) {
1199 RollingBack = true;
1200
1201 // As we re-create registers, map deleted definitions to re-created ones. This
1202 // allows to replace invalid re-creation positions that reference deleted
1203 // definitions to valid new positions while restoring original MI order.
1204 DenseMap<MachineInstr *, MachineInstr *> Replacements;
1205 unsigned PositionIndex = Positions.size();
1206
1207 // Re-create deleted registers in reverse order of deletion. Related registers
1208 // are deleted in reverse def-use order so this ensures we re-create registers
1209 // in def-use order. This also ensures that re-creation positions that became
1210 // invalid due to later MI deletions can be corrected as we go.
1211 for (const DeadReg &Reg : reverse(C&: DeadRegs)) {
1212 if (Remater.isPermanentlyDead(RegIdx: Reg.Idx)) {
1213 // It is possible the register was permanently deleted as a consequence of
1214 // dead-def elimination.
1215 Rematerializations.erase(Val: Reg.Idx);
1216 PositionIndex -= Reg.Defs.size();
1217 continue;
1218 }
1219 assert(!Remater.getReg(Reg.Idx).isAlive() && "register should be dead");
1220
1221 // Determine re-creation positions for all the deleted register's defs.
1222 SmallVector<MachineBasicBlock::iterator, 1> InsertPositions;
1223 for (unsigned I = 0, E = Reg.Defs.size(); I < E; ++I) {
1224 InsertBeforePos Pos = Positions[--PositionIndex];
1225 if (auto *MBB = dyn_cast<MachineBasicBlock *>(Val&: Pos)) {
1226 InsertPositions.push_back(Elt: MBB->end());
1227 } else {
1228 auto *MI = cast<MachineInstr *>(Val&: Pos);
1229 MachineInstr *InsertBeforeMI = Replacements.lookup_or(Val: MI, Default&: MI);
1230 InsertPositions.push_back(Elt: InsertBeforeMI->getIterator());
1231 }
1232 }
1233
1234 Remater.recreateReg(RegIdx: Reg.Idx, Positions: InsertPositions, DefReg: Reg.DefReg);
1235
1236 const Rematerializer::Reg &RecreateReg = Remater.getReg(RegIdx: Reg.Idx);
1237 for (const auto [OldDef, NewDef] : zip_equal(t: Reg.Defs, u: RecreateReg.Defs)) {
1238 assert(!Replacements.contains(OldDef) && "duplicate deleted MI");
1239 Replacements[OldDef] = NewDef;
1240 }
1241 }
1242
1243 // Rollback rematerializations.
1244 for (const auto &[RegIdx, RematsOf] : Rematerializations) {
1245 for (RegisterIdx RematRegIdx : RematsOf) {
1246 // It is possible that rematerializations were deleted. Their users would
1247 // have been transfered to some other rematerialization so we can safely
1248 // ignore them. Original registers that were deleted were just re-created
1249 // so we do not need to check for that.
1250 if (Remater.getReg(RegIdx: RematRegIdx).isAlive())
1251 Remater.transferAllUsers(FromRegIdx: RematRegIdx, ToRegIdx: RegIdx);
1252 }
1253 }
1254
1255 DeadRegs.clear();
1256 Positions.clear();
1257 PosToIdx.clear();
1258 Rematerializations.clear();
1259 RollingBack = false;
1260}
1261
1262bool Rollbacker::isRollbackableMI(const MachineInstr &MI,
1263 const Rematerializer &Remater) const {
1264 RegisterIdx RegIdx = Remater.getDefRegIdx(MI);
1265 if (RegIdx == Rematerializer::NoReg ||
1266 !Remater.isRematerializedRegister(RegIdx))
1267 return false;
1268 // It is possible that the MI defines a rematerializable register that was not
1269 // recorded if the rollbacker was attached to the rematerializer after the
1270 // rematerialization happened. In such cases the MI won't be rolled back.
1271 auto RematsOf = Rematerializations.find(Val: Remater.getOriginOf(RematRegIdx: RegIdx));
1272 if (RematsOf == Rematerializations.end())
1273 return false;
1274 return RematsOf->getSecond().contains(V: RegIdx);
1275}
1276
1277void Rollbacker::invalidatePosition(MachineInstr *MI,
1278 MachineBasicBlock::iterator It) {
1279 const InsertBeforePos MIPos = InsertBeforePos(MI),
1280 NewPos = makePos(It, MBB: MI->getParent());
1281 auto MIIndices = PosToIdx.find(Val: MIPos);
1282 if (MIIndices == PosToIdx.end())
1283 return;
1284 const SmallDenseSet<unsigned, 1> &InvalIndices = MIIndices->getSecond();
1285 assert(!InvalIndices.empty() && "no index hold position");
1286 for (unsigned I : InvalIndices)
1287 Positions[I] = NewPos;
1288 PosToIdx.try_emplace(Key: NewPos).first->getSecond().insert_range(R: InvalIndices);
1289 PosToIdx.erase(Val: MIPos);
1290}
1291