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()) || TII.isIgnorableUse(MO))
659 continue;
660 return false;
661 }
662 }
663
664 return true;
665}
666
667RegisterIdx Rematerializer::getDefRegIdx(const MachineInstr &MI) const {
668 if (!MI.getNumOperands() || !MI.getOperand(i: 0).isReg() ||
669 !MI.getOperand(i: 0).isDef())
670 return NoReg;
671 Register Reg = MI.getOperand(i: 0).getReg();
672 auto UserRegIt = RegToIdx.find(Val: Reg);
673 if (UserRegIt == RegToIdx.end())
674 return NoReg;
675 return UserRegIt->second;
676}
677
678RegisterIdx
679Rematerializer::rematerializeReg(RegisterIdx RegIdx, unsigned UseRegion,
680 MachineBasicBlock::iterator InsertPos,
681 SmallVectorImpl<RegisterIdx> &&Dependencies) {
682 RegisterIdx NewRegIdx = Regs.size();
683
684 Reg &NewReg = Regs.emplace_back();
685 Reg &FromReg = Regs[RegIdx];
686 NewReg.Mask = FromReg.Mask;
687 NewReg.DefRegion = UseRegion;
688 NewReg.Defs.reserve(N: FromReg.Defs.size());
689 NewReg.Dependencies = std::move(Dependencies);
690
691 // Track rematerialization link between registers. Origins are always
692 // registers that existed originally, and rematerializations are always
693 // attached to them.
694 const RegisterIdx OriginIdx = getOriginOrSelf(RegIdx);
695 Origins.push_back(Elt: OriginIdx);
696 Rematerializations[OriginIdx].insert(V: NewRegIdx);
697
698 // Use the TII to rematerialize the defining instruction with a new defined
699 // register.
700 Register NewDefReg = MRI.cloneVirtualRegister(VReg: FromReg.getDefReg());
701 for (const MachineInstr *DefMI : FromReg.Defs) {
702 TII.reMaterialize(MBB&: *RegionMBB[UseRegion], MI: InsertPos, DestReg: NewDefReg, SubIdx: 0, Orig: *DefMI);
703 NewReg.Defs.push_back(Elt: &*std::prev(x: InsertPos));
704 }
705 RegToIdx.insert(KV: {NewDefReg, NewRegIdx});
706 postRematerialization(ModelRegIdx: RegIdx, RematRegIdx: NewRegIdx);
707
708 noteRegCreated(RegIdx: NewRegIdx);
709 LLVM_DEBUG(dbgs() << "** Rematerialized " << printID(RegIdx) << " as "
710 << printRematReg(NewRegIdx) << '\n');
711 return NewRegIdx;
712}
713
714void Rematerializer::recreateReg(
715 RegisterIdx RegIdx, ArrayRef<MachineBasicBlock::iterator> Positions,
716 Register DefReg) {
717 assert(RegToIdx.contains(DefReg) && "unknown defined register");
718 assert(RegToIdx.at(DefReg) == RegIdx && "incorrect defined register");
719 assert(!getReg(RegIdx).isAlive() && "register is still alive");
720 Reg &OriginReg = Regs[RegIdx];
721
722 // Re-establish the link between origin and rematerialization if necessary.
723 const bool RecreateOriginalReg = isOriginalRegister(RegIdx);
724 if (!RecreateOriginalReg)
725 Rematerializations[getOriginOf(RematRegIdx: RegIdx)].insert(V: RegIdx);
726
727 // Rematerialize from one of the existing rematerializations or from the
728 // origin. We expect at least one to exist, otherwise it would mean the value
729 // held by the original register is no longer available anywhere in the MF.
730 RegisterIdx ModelRegIdx;
731 if (RecreateOriginalReg) {
732 assert(Rematerializations.contains(RegIdx) && "expected remats");
733 ModelRegIdx = *Rematerializations.at(Val: RegIdx).begin();
734 } else {
735 assert(getReg(getOriginOf(RegIdx)).isAlive() && "expected alive origin");
736 ModelRegIdx = getOriginOf(RematRegIdx: RegIdx);
737 }
738 const Reg &ModelReg = getReg(RegIdx: ModelRegIdx);
739
740 for (auto [DefMI, InsertPos] : zip_equal(t: ModelReg.Defs, u&: Positions)) {
741 TII.reMaterialize(MBB&: *RegionMBB[OriginReg.DefRegion], MI: InsertPos, DestReg: DefReg, SubIdx: 0,
742 Orig: *DefMI);
743 OriginReg.Defs.push_back(Elt: &*std::prev(x: InsertPos));
744 }
745 postRematerialization(ModelRegIdx, RematRegIdx: RegIdx);
746 LLVM_DEBUG(dbgs() << "** Recreated " << printID(RegIdx) << " as "
747 << printRematReg(RegIdx) << '\n');
748}
749
750void Rematerializer::postRematerialization(RegisterIdx ModelRegIdx,
751 RegisterIdx RematRegIdx) {
752 Reg &ModelReg = Regs[ModelRegIdx], &RematReg = Regs[RematRegIdx];
753
754 SlotIndex UseIdx;
755 for (MachineInstr *DefMI : RematReg.Defs)
756 UseIdx = LIS.InsertMachineInstrInMaps(MI&: *DefMI);
757 UseIdx = UseIdx.getRegSlot();
758
759 // The rematerialization has no user at this point so its interval will
760 // initially be empty.
761 LIS.createAndComputeVirtRegInterval(Reg: RematReg.getDefReg());
762
763 // The start of the new register's region may have changed.
764 MachineInstr &FirstDefMI = *RematReg.getFirstDef();
765 auto &[RegionBegin, RegionEnd] = Regions[RematReg.DefRegion];
766 if (RegionBegin == RegionEnd ||
767 (!RegionBegin->isDebugInstr() && LIS.getInstructionIndex(Instr: *RegionBegin) >
768 LIS.getInstructionIndex(Instr: FirstDefMI)))
769 RegionBegin = FirstDefMI.getIterator();
770
771 // Replace dependencies as needed in the rematerialized MI. All dependencies
772 // of the latter gain a new user.
773 auto ZipedDeps = zip_equal(t&: ModelReg.Dependencies, u&: RematReg.Dependencies);
774 for (const auto &[OldDepRegIdx, NewDepRegIdx] : ZipedDeps) {
775 LLVM_DEBUG(dbgs() << " Dependency: " << printID(OldDepRegIdx) << " -> "
776 << printID(NewDepRegIdx) << '\n');
777 Register OldReg = getReg(RegIdx: OldDepRegIdx).getDefReg();
778 Register NewReg = getReg(RegIdx: NewDepRegIdx).getDefReg();
779
780 SmallVector<MachineInstr *, 2> DefsUsingNewDep;
781 for (MachineInstr *DefMI : RematReg.Defs) {
782 bool NewDefHasReg = false;
783 for (MachineOperand &MO : DefMI->operands()) {
784 if (!MO.isReg() || MO.getReg() != OldReg)
785 continue;
786 NewDefHasReg = true;
787 DefsUsingNewDep.push_back(Elt: DefMI);
788 if (OldDepRegIdx != NewDepRegIdx)
789 MO.substVirtReg(Reg: NewReg, SubIdx: 0, TRI);
790 }
791 if (NewDefHasReg)
792 Regs[NewDepRegIdx].addUser(MI: DefMI, Region: RematReg.DefRegion);
793 }
794 assert(!DefsUsingNewDep.empty() && "no user of dependency");
795 extendToNewUsers(RegIdx: NewDepRegIdx, NewUsers: DefsUsingNewDep);
796 }
797
798 // Unrematerializable dependencies always gain a new user after a
799 // rematerialization; their live range may need to be extended.
800 for (const auto &[Reg, Mask] : getUnrematableDeps(RegIdx: ModelRegIdx))
801 extendInterval(LI&: LIS.getInterval(Reg), Mask, UseIdx);
802}
803
804void Rematerializer::extendToNewUsers(RegisterIdx RegIdx,
805 ArrayRef<MachineInstr *> NewUsers) const {
806 if (NewUsers.empty())
807 return;
808 const Reg &ExtendReg = getReg(RegIdx);
809 assert(ExtendReg.isAlive() && "register must be alive");
810
811 Register DefReg = ExtendReg.getDefReg();
812 LiveInterval &LI = LIS.getInterval(Reg: DefReg);
813 const LaneBitmask FullLaneMask = MRI.getMaxLaneMaskForVReg(Reg: DefReg);
814 const bool ShouldTrackSubReg = MRI.shouldTrackSubRegLiveness(VReg: DefReg);
815
816 // Seed subranges from the main range when subreg liveness is tracked but no
817 // subrange exists yet. VirtRegRewriter later requires subranges even when a
818 // new user reads the full mask, because other users may read subregs.
819 if (!LI.hasSubRanges() && ShouldTrackSubReg)
820 LI.createSubRangeFrom(Allocator&: LIS.getVNInfoAllocator(), LaneMask: FullLaneMask, CopyFrom: LI);
821
822 // Extend all ranges in the register's live interval so that they reach the
823 // new users.
824 for (MachineInstr *UserMI : NewUsers) {
825 SlotIndex UseIdx = LIS.getInstructionIndex(Instr: *UserMI).getRegSlot();
826
827 // Derive register lanes read by that user.
828 LaneBitmask RegMask;
829 for (MachineOperand &MO : UserMI->all_uses()) {
830 if (MO.getReg() == DefReg) {
831 unsigned SubIdx = MO.getSubReg();
832 if (SubIdx == 0) {
833 RegMask = FullLaneMask;
834 break;
835 }
836 RegMask |= TRI.getSubRegIndexLaneMask(SubIdx);
837 }
838 }
839
840 if (RegMask != FullLaneMask) {
841 // Refine sub-ranges to be able to track the mask for that user.
842 LI.refineSubRanges(
843 Allocator&: LIS.getVNInfoAllocator(), LaneMask: RegMask, Apply: [](LiveInterval::SubRange &SR) {},
844 Indexes: *LIS.getSlotIndexes(), TRI);
845 // Refining may have introduced empty sub-ranges, which are illegal.
846 LI.removeEmptySubRanges();
847 }
848 extendInterval(LI, Mask: RegMask, UseIdx);
849 }
850
851 // Rematerializable registers are never read by instructions not defining them
852 // until after their last def, so adding a user to them ensures their last
853 // definition is alive. All potential other definitions are read by the last
854 // definition and are therefore already alive by construction.
855 LLVM_DEBUG({
856 if (ExtendReg.getLastDef()->getOperand(0).isDead())
857 dbgs() << "Clearing dead flag for "
858 << printRematReg(RegIdx, /*SkipRegions=*/false,
859 /*DefIdx=*/ExtendReg.Defs.size() - 1)
860 << '\n';
861 });
862 ExtendReg.getLastDef()->getOperand(i: 0).setIsDead(false);
863}
864
865void Rematerializer::extendInterval(LiveInterval &LI, LaneBitmask Mask,
866 SlotIndex UseIdx) const {
867 if (!LI.hasSubRanges()) {
868 if (!LI.liveAt(index: UseIdx))
869 LLVM_DEBUG(dbgs() << "Extending interval of register "
870 << printReg(LI.reg(), &TRI, 0, &MRI) << " to " << UseIdx
871 << '\n');
872 LIS.extendToIndices(LR&: LI, Indices: UseIdx);
873 return;
874 }
875
876 bool SubRangeExtended = false;
877 for (LiveInterval::SubRange &SR : LI.subranges()) {
878 if ((SR.LaneMask & Mask).any() && !SR.liveAt(index: UseIdx)) {
879 SubRangeExtended = true;
880 LLVM_DEBUG(dbgs() << "Extending subrange " << SR << " of register "
881 << printReg(LI.reg(), &TRI, 0, &MRI) << " to " << UseIdx
882 << '\n');
883 LIS.extendToIndices(LR&: SR, Indices: UseIdx);
884 }
885 }
886 if (!SubRangeExtended)
887 return;
888
889 // FIXME: this fully reconstructs the main live range from scratch, but
890 // there may be a more targeted way to make the update.
891 LI.clear();
892 LIS.constructMainRangeFromSubranges(LI);
893}
894
895void Rematerializer::shrinkToUses(RegisterIdx RegIdx) {
896 Reg &ShrinkReg = Regs[RegIdx];
897 assert(ShrinkReg.isAlive() && "register must be alive");
898 if (ShrinkReg.Uses.empty()) {
899 deleteReg(RootIdx: RegIdx);
900 return;
901 }
902
903 // By construction, registers should never end up with multiple disconnected
904 // components or dead definitions.
905 LiveInterval &LI = LIS.getInterval(Reg: ShrinkReg.getDefReg());
906 LLVM_DEBUG(dbgs() << "Shrinking interval of " << printID(RegIdx) << ": " << LI
907 << '\n');
908 LIS.shrinkToUses(li: &LI);
909}
910
911void Rematerializer::shrinkToUsesUnremat(Register Reg) {
912 LiveInterval &LI = LIS.getInterval(Reg);
913 LLVM_DEBUG(dbgs() << "Shrinking interval of unrematerializable register "
914 << LI << '\n');
915
916 SmallVector<MachineInstr *, 2> DeadDefs;
917 if (!LIS.shrinkToUses(li: &LI, dead: &DeadDefs)) {
918 assert(DeadDefs.empty() && "expected no dead def");
919 return;
920 }
921
922 // This should be a very rare occurence, but shrinking an unrematerializable
923 // register could create dead defs.
924 if (DeadDefs.empty())
925 return;
926
927 // The live-range editor delegate will take care of reflecting the
928 // elimination of all dead definitions in the rematerializer.
929 SmallVector<Register, 4> NewRegs;
930 DeadDefDelegate DeadDefDeleg(*this);
931 MachineFunction &MF = *DeadDefs.front()->getParent()->getParent();
932 LiveRangeEdit(nullptr, NewRegs, MF, LIS, nullptr, &DeadDefDeleg)
933 .eliminateDeadDefs(Dead&: DeadDefs);
934}
935
936std::pair<MachineInstr *, MachineInstr *>
937Rematerializer::Reg::getRegionUseBounds(unsigned UseRegion,
938 const LiveIntervals &LIS) const {
939 auto It = Uses.find(Val: UseRegion);
940 if (It == Uses.end())
941 return {nullptr, nullptr};
942 const RegionUsers &RegionUsers = It->getSecond();
943 assert(!RegionUsers.empty() && "empty userset in region");
944
945 auto User = RegionUsers.begin(), UserEnd = RegionUsers.end();
946 MachineInstr *FirstMI = *User, *LastMI = FirstMI;
947 SlotIndex FirstIndex = LIS.getInstructionIndex(Instr: *FirstMI),
948 LastIndex = FirstIndex;
949
950 while (++User != UserEnd) {
951 SlotIndex UserIndex = LIS.getInstructionIndex(Instr: **User);
952 if (UserIndex < FirstIndex) {
953 FirstIndex = UserIndex;
954 FirstMI = *User;
955 } else if (UserIndex > LastIndex) {
956 LastIndex = UserIndex;
957 LastMI = *User;
958 }
959 }
960
961 return {FirstMI, LastMI};
962}
963
964void Rematerializer::Reg::addUser(MachineInstr *MI, unsigned Region) {
965 Uses[Region].insert(V: MI);
966}
967
968void Rematerializer::Reg::addUsers(const RegionUsers &NewUsers,
969 unsigned Region) {
970 Uses[Region].insert_range(R: NewUsers);
971}
972
973void Rematerializer::Reg::eraseUser(MachineInstr *MI, unsigned Region) {
974 RegionUsers &RUsers = Uses.at(Val: Region);
975 assert(RUsers.contains(MI) && "user not in region");
976 if (RUsers.size() == 1)
977 Uses.erase(Val: Region);
978 else
979 RUsers.erase(V: MI);
980}
981
982bool Rematerializer::Reg::tryEraseUser(MachineInstr *MI, unsigned Region) {
983 auto RegionUsers = Uses.find(Val: Region);
984 if (RegionUsers == Uses.end() || !RegionUsers->getSecond().erase(V: MI))
985 return false;
986 if (RegionUsers->getSecond().empty())
987 Uses.erase(Val: Region);
988 return true;
989}
990
991Printable Rematerializer::printDependencyDAG(RegisterIdx RootIdx) const {
992 return Printable([&, RootIdx](raw_ostream &OS) {
993 DenseMap<RegisterIdx, unsigned> RegDepths;
994 std::function<void(RegisterIdx, unsigned)> WalkTree =
995 [&](RegisterIdx RegIdx, unsigned Depth) -> void {
996 unsigned MaxDepth = std::max(a: RegDepths.lookup_or(Val: RegIdx, Default&: Depth), b: Depth);
997 RegDepths.emplace_or_assign(Key: RegIdx, Args&: MaxDepth);
998 for (RegisterIdx DepRegIdx : getReg(RegIdx).Dependencies)
999 WalkTree(DepRegIdx, Depth + 1);
1000 };
1001 WalkTree(RootIdx, 0);
1002
1003 // Sort in decreasing depth order to print root at the bottom.
1004 SmallVector<std::pair<RegisterIdx, unsigned>> Regs(RegDepths.begin(),
1005 RegDepths.end());
1006 sort(C&: Regs, Comp: [](const auto &LHS, const auto &RHS) {
1007 return LHS.second > RHS.second;
1008 });
1009
1010 OS << printID(RegIdx: RootIdx) << " has " << Regs.size() - 1 << " dependencies\n";
1011 for (const auto &[RegIdx, Depth] : Regs) {
1012 OS << indent(Depth, 2) << (Depth ? '|' : '*') << ' '
1013 << printRematReg(RegIdx, /*SkipRegions=*/Depth) << '\n';
1014 }
1015 OS << printRegUsers(RegIdx: RootIdx);
1016 });
1017}
1018
1019Printable Rematerializer::printID(RegisterIdx RegIdx) const {
1020 return Printable([&, RegIdx](raw_ostream &OS) {
1021 const Reg &PrintReg = getReg(RegIdx);
1022 OS << '(' << RegIdx << '/';
1023 if (!PrintReg.isAlive())
1024 OS << "<dead>";
1025 else
1026 OS << printReg(Reg: PrintReg.getDefReg(), TRI: &TRI, SubIdx: 0, MRI: &MRI);
1027 OS << ")[" << PrintReg.DefRegion << "]";
1028 });
1029}
1030
1031Printable Rematerializer::printRematReg(RegisterIdx RegIdx, bool SkipRegions,
1032 unsigned DefIdx) const {
1033 return Printable([&, RegIdx, SkipRegions, DefIdx](raw_ostream &OS) {
1034 const Reg &PrintReg = getReg(RegIdx);
1035 OS << printID(RegIdx);
1036 if (!SkipRegions) {
1037 OS << " [" << PrintReg.DefRegion;
1038 if (!PrintReg.Uses.empty()) {
1039 assert(PrintReg.isAlive() && "dead register cannot have uses");
1040 const LiveInterval &LI = LIS.getInterval(Reg: PrintReg.getDefReg());
1041 // First display all regions in which the register is live-through and
1042 // not used.
1043 bool First = true;
1044 for (const auto &[I, Bounds] : enumerate(First&: Regions)) {
1045 if (PrintReg.Uses.contains(Val: I))
1046 continue;
1047 // The register must be live at the live-ins and live-outs of the
1048 // region.
1049 MachineBasicBlock::iterator LiveIn =
1050 skipDebugInstructionsForward(It: Bounds.first, End: Bounds.second);
1051 if (LiveIn == Bounds.second) {
1052 // The region has no non-debug instructions, it's hard to assess
1053 // whether the register is live across it without an index.
1054 continue;
1055 }
1056 // LiveIn is inside the range and a non-debug instruction so we know
1057 // this will also point to a non-debug instruction within the region.
1058 MachineBasicBlock::iterator LiveOut = skipDebugInstructionsBackward(
1059 It: std::prev(x: Bounds.second), Begin: Bounds.first);
1060 if (LI.liveAt(index: LIS.getInstructionIndex(Instr: *LiveIn)) &&
1061 LI.liveAt(index: LIS.getInstructionIndex(Instr: *LiveOut).getDeadSlot())) {
1062 OS << (First ? " - " : ",") << I;
1063 First = false;
1064 }
1065 }
1066 OS << (First ? " --> " : " -> ");
1067
1068 // Then display regions in which the register is used.
1069 auto It = PrintReg.Uses.begin();
1070 OS << It->first;
1071 while (++It != PrintReg.Uses.end())
1072 OS << "," << It->first;
1073 }
1074 OS << "] ";
1075 }
1076 if (PrintReg.isAlive()) {
1077 assert(DefIdx < PrintReg.Defs.size() && "out-of-bound def");
1078 MachineInstr &PrintDef = *PrintReg.Defs[DefIdx];
1079 OS << "(def. " << DefIdx + 1 << " / " << PrintReg.Defs.size() << ") ";
1080 PrintDef.print(OS, /*IsStandalone=*/true, /*SkipOpers=*/false,
1081 /*SkipDebugLoc=*/false, /*AddNewLine=*/false);
1082 OS << " @ ";
1083 LIS.getInstructionIndex(Instr: PrintDef).print(os&: OS);
1084 }
1085 });
1086}
1087
1088Printable Rematerializer::printRegUsers(RegisterIdx RegIdx) const {
1089 return Printable([&, RegIdx](raw_ostream &OS) {
1090 for (const auto &[UseRegion, Users] : getReg(RegIdx).Uses) {
1091 for (MachineInstr *MI : Users)
1092 OS << " User " << printUser(MI, UseRegion) << '\n';
1093 }
1094 });
1095}
1096
1097Printable Rematerializer::printUser(const MachineInstr *MI,
1098 std::optional<unsigned> UseRegion) const {
1099 return Printable([&, MI, UseRegion](raw_ostream &OS) {
1100 RegisterIdx RegIdx = getDefRegIdx(MI: *MI);
1101 if (RegIdx != NoReg) {
1102 OS << printID(RegIdx);
1103 } else {
1104 OS << "(-/-)[";
1105 if (UseRegion)
1106 OS << *UseRegion;
1107 else
1108 OS << '?';
1109 OS << ']';
1110 }
1111 OS << ' ';
1112 MI->print(OS, /*IsStandalone=*/true, /*SkipOpers=*/false,
1113 /*SkipDebugLoc=*/false, /*AddNewLine=*/false);
1114 OS << " @ ";
1115 LIS.getInstructionIndex(Instr: *MI).print(os&: OS);
1116 });
1117}
1118
1119void Rollbacker::rematerializerNoteRegCreated(const Rematerializer &Remater,
1120 RegisterIdx RegIdx) {
1121 if (RollingBack)
1122 return;
1123 assert(Remater.isRematerializedRegister(RegIdx) && "only remats are created");
1124 Rematerializations[Remater.getOriginOf(RematRegIdx: RegIdx)].insert(V: RegIdx);
1125}
1126
1127void Rollbacker::rematerializerNoteRegWillBeDeleted(
1128 const Rematerializer &Remater, RegisterIdx RegIdx) {
1129 if (RollingBack)
1130 return;
1131
1132 const Rematerializer::Reg &Reg = Remater.getReg(RegIdx);
1133 MachineBasicBlock *ParentMBB = Reg.getFirstDef()->getParent();
1134 MachineBasicBlock::iterator LastValidPos;
1135
1136 auto GetNextValidPosAfterDef =
1137 [&](unsigned DefIdx) -> MachineBasicBlock::iterator {
1138 const MachineInstr *NextDef =
1139 DefIdx + 1 < Reg.Defs.size() ? Reg.Defs[DefIdx + 1] : nullptr;
1140 MachineBasicBlock::iterator ValidPos =
1141 std::next(x: Reg.Defs[DefIdx]->getIterator());
1142
1143 while (ValidPos != ParentMBB->end()) {
1144 // When there are no valid insert positions between the current and next
1145 // definition of the register about to be deleted, the first valid insert
1146 // position for the current definition is the same as for the next
1147 // definition.
1148 const MachineInstr &CandMI = *ValidPos;
1149 if (NextDef && &CandMI == NextDef)
1150 return LastValidPos;
1151 if (!isRollbackableMI(MI: CandMI, Remater))
1152 break;
1153
1154 // Move to the next candidate position.
1155 ValidPos = std::next(x: ValidPos);
1156 }
1157
1158 LastValidPos = ValidPos;
1159 return ValidPos;
1160 };
1161
1162 if (Remater.isRematerializedRegister(RegIdx)) {
1163 // Rematerializations will not be re-created. Previously deleted registers
1164 // that reference this register's defining instructions as their re-creation
1165 // position should instead be re-created at a valid position after the
1166 // deleted MIs.
1167 for (unsigned I = Reg.Defs.size(); I > 0; --I)
1168 invalidatePosition(MI: Reg.Defs[I - 1], It: GetNextValidPosAfterDef(I - 1));
1169 return;
1170 }
1171
1172 // Original registers can be re-created. Add a re-creation position for each
1173 // definition of the rematerializable register.
1174 DeadRegs.push_back(Elt: DeadReg(RegIdx, Remater));
1175 for (unsigned I = Reg.Defs.size(); I > 0; --I) {
1176 const InsertBeforePos InsertPos =
1177 makePos(It: GetNextValidPosAfterDef(I - 1), MBB: ParentMBB);
1178 PosToIdx[InsertPos].insert(V: Positions.size());
1179 Positions.push_back(Elt: InsertPos);
1180 }
1181}
1182
1183void Rollbacker::rematerializerNoteMIWillBeDeleted(
1184 const Rematerializer &Remater, MachineInstr &MI) {
1185 if (RollingBack)
1186 return;
1187
1188 // Previously deleted registers that reference this MI as their re-creation
1189 // position should instead be re-created at a valid position after it.
1190 MachineBasicBlock *ParentMBB = MI.getParent();
1191 MachineBasicBlock::iterator ValidPos = std::next(x: MI.getIterator());
1192 while (ValidPos != ParentMBB->end() && isRollbackableMI(MI: *ValidPos, Remater))
1193 ValidPos = std::next(x: ValidPos);
1194 invalidatePosition(MI: &MI, It: ValidPos);
1195}
1196
1197void Rollbacker::rollback(Rematerializer &Remater) {
1198 RollingBack = true;
1199
1200 // As we re-create registers, map deleted definitions to re-created ones. This
1201 // allows to replace invalid re-creation positions that reference deleted
1202 // definitions to valid new positions while restoring original MI order.
1203 DenseMap<MachineInstr *, MachineInstr *> Replacements;
1204 unsigned PositionIndex = Positions.size();
1205
1206 // Re-create deleted registers in reverse order of deletion. Related registers
1207 // are deleted in reverse def-use order so this ensures we re-create registers
1208 // in def-use order. This also ensures that re-creation positions that became
1209 // invalid due to later MI deletions can be corrected as we go.
1210 for (const DeadReg &Reg : reverse(C&: DeadRegs)) {
1211 if (Remater.isPermanentlyDead(RegIdx: Reg.Idx)) {
1212 // It is possible the register was permanently deleted as a consequence of
1213 // dead-def elimination.
1214 Rematerializations.erase(Val: Reg.Idx);
1215 PositionIndex -= Reg.Defs.size();
1216 continue;
1217 }
1218 assert(!Remater.getReg(Reg.Idx).isAlive() && "register should be dead");
1219
1220 // Determine re-creation positions for all the deleted register's defs.
1221 SmallVector<MachineBasicBlock::iterator, 1> InsertPositions;
1222 for (unsigned I = 0, E = Reg.Defs.size(); I < E; ++I) {
1223 InsertBeforePos Pos = Positions[--PositionIndex];
1224 if (auto *MBB = dyn_cast<MachineBasicBlock *>(Val&: Pos)) {
1225 InsertPositions.push_back(Elt: MBB->end());
1226 } else {
1227 auto *MI = cast<MachineInstr *>(Val&: Pos);
1228 MachineInstr *InsertBeforeMI = Replacements.lookup_or(Val: MI, Default&: MI);
1229 InsertPositions.push_back(Elt: InsertBeforeMI->getIterator());
1230 }
1231 }
1232
1233 Remater.recreateReg(RegIdx: Reg.Idx, Positions: InsertPositions, DefReg: Reg.DefReg);
1234
1235 const Rematerializer::Reg &RecreateReg = Remater.getReg(RegIdx: Reg.Idx);
1236 for (const auto [OldDef, NewDef] : zip_equal(t: Reg.Defs, u: RecreateReg.Defs)) {
1237 assert(!Replacements.contains(OldDef) && "duplicate deleted MI");
1238 Replacements[OldDef] = NewDef;
1239 }
1240 }
1241
1242 // Rollback rematerializations.
1243 for (const auto &[RegIdx, RematsOf] : Rematerializations) {
1244 for (RegisterIdx RematRegIdx : RematsOf) {
1245 // It is possible that rematerializations were deleted. Their users would
1246 // have been transfered to some other rematerialization so we can safely
1247 // ignore them. Original registers that were deleted were just re-created
1248 // so we do not need to check for that.
1249 if (Remater.getReg(RegIdx: RematRegIdx).isAlive())
1250 Remater.transferAllUsers(FromRegIdx: RematRegIdx, ToRegIdx: RegIdx);
1251 }
1252 }
1253
1254 DeadRegs.clear();
1255 Positions.clear();
1256 PosToIdx.clear();
1257 Rematerializations.clear();
1258 RollingBack = false;
1259}
1260
1261bool Rollbacker::isRollbackableMI(const MachineInstr &MI,
1262 const Rematerializer &Remater) const {
1263 RegisterIdx RegIdx = Remater.getDefRegIdx(MI);
1264 if (RegIdx == Rematerializer::NoReg ||
1265 !Remater.isRematerializedRegister(RegIdx))
1266 return false;
1267 // It is possible that the MI defines a rematerializable register that was not
1268 // recorded if the rollbacker was attached to the rematerializer after the
1269 // rematerialization happened. In such cases the MI won't be rolled back.
1270 auto RematsOf = Rematerializations.find(Val: Remater.getOriginOf(RematRegIdx: RegIdx));
1271 if (RematsOf == Rematerializations.end())
1272 return false;
1273 return RematsOf->getSecond().contains(V: RegIdx);
1274}
1275
1276void Rollbacker::invalidatePosition(MachineInstr *MI,
1277 MachineBasicBlock::iterator It) {
1278 const InsertBeforePos MIPos = InsertBeforePos(MI),
1279 NewPos = makePos(It, MBB: MI->getParent());
1280 auto MIIndices = PosToIdx.find(Val: MIPos);
1281 if (MIIndices == PosToIdx.end())
1282 return;
1283 const SmallDenseSet<unsigned, 1> &InvalIndices = MIIndices->getSecond();
1284 assert(!InvalIndices.empty() && "no index hold position");
1285 for (unsigned I : InvalIndices)
1286 Positions[I] = NewPos;
1287 PosToIdx.try_emplace(Key: NewPos).first->getSecond().insert_range(R: InvalIndices);
1288 PosToIdx.erase(Val: MIPos);
1289}
1290