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