1//===-- RenameIndependentSubregs.cpp - Live Interval Analysis -------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9/// Rename independent subregisters looks for virtual registers with
10/// independently used subregisters and renames them to new virtual registers.
11/// Example: In the following:
12/// %0:sub0<read-undef> = ...
13/// %0:sub1 = ...
14/// use %0:sub0
15/// %0:sub0 = ...
16/// use %0:sub0
17/// use %0:sub1
18/// sub0 and sub1 are never used together, and we have two independent sub0
19/// definitions. This pass will rename to:
20/// %0:sub0<read-undef> = ...
21/// %1:sub1<read-undef> = ...
22/// use %1:sub1
23/// %2:sub1<read-undef> = ...
24/// use %2:sub1
25/// use %0:sub0
26//
27//===----------------------------------------------------------------------===//
28
29#include "llvm/CodeGen/RenameIndependentSubregs.h"
30#include "LiveRangeUtils.h"
31#include "PHIEliminationUtils.h"
32#include "llvm/CodeGen/LiveInterval.h"
33#include "llvm/CodeGen/LiveIntervals.h"
34#include "llvm/CodeGen/MachineFunctionPass.h"
35#include "llvm/CodeGen/MachineInstrBuilder.h"
36#include "llvm/CodeGen/MachineRegisterInfo.h"
37#include "llvm/CodeGen/TargetInstrInfo.h"
38#include "llvm/InitializePasses.h"
39#include "llvm/Pass.h"
40
41using namespace llvm;
42
43#define DEBUG_TYPE "rename-independent-subregs"
44
45namespace {
46
47class RenameIndependentSubregs {
48public:
49 RenameIndependentSubregs(LiveIntervals *LIS) : LIS(LIS) {}
50
51 bool run(MachineFunction &MF);
52
53private:
54 struct SubRangeInfo {
55 ConnectedVNInfoEqClasses ConEQ;
56 LiveInterval::SubRange *SR;
57 unsigned Index;
58
59 SubRangeInfo(LiveIntervals &LIS, LiveInterval::SubRange &SR,
60 unsigned Index)
61 : ConEQ(LIS), SR(&SR), Index(Index) {}
62 };
63
64 /// Split unrelated subregister components and rename them to new vregs.
65 bool renameComponents(LiveInterval &LI) const;
66
67 /// Build a vector of SubRange infos and a union find set of
68 /// equivalence classes.
69 /// Returns true if more than 1 equivalence class was found.
70 bool findComponents(IntEqClasses &Classes,
71 SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
72 LiveInterval &LI) const;
73
74 /// Distribute the LiveInterval segments into the new LiveIntervals
75 /// belonging to their class.
76 void distribute(const IntEqClasses &Classes,
77 const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
78 const SmallVectorImpl<LiveInterval*> &Intervals) const;
79
80 /// Constructs main liverange and add missing undef+dead flags.
81 void computeMainRangesFixFlags(const IntEqClasses &Classes,
82 const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
83 const SmallVectorImpl<LiveInterval*> &Intervals) const;
84
85 /// Rewrite Machine Operands to use the new vreg belonging to their class.
86 void rewriteOperands(const IntEqClasses &Classes,
87 const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
88 const SmallVectorImpl<LiveInterval*> &Intervals) const;
89
90
91 LiveIntervals *LIS = nullptr;
92 MachineRegisterInfo *MRI = nullptr;
93 const TargetInstrInfo *TII = nullptr;
94};
95
96class RenameIndependentSubregsLegacy : public MachineFunctionPass {
97public:
98 static char ID;
99 RenameIndependentSubregsLegacy() : MachineFunctionPass(ID) {}
100 bool runOnMachineFunction(MachineFunction &MF) override;
101 StringRef getPassName() const override {
102 return "Rename Disconnected Subregister Components";
103 }
104
105 void getAnalysisUsage(AnalysisUsage &AU) const override {
106 AU.setPreservesCFG();
107 AU.addRequired<LiveIntervalsWrapperPass>();
108 AU.addPreserved<LiveIntervalsWrapperPass>();
109 AU.addRequired<SlotIndexesWrapperPass>();
110 AU.addPreserved<SlotIndexesWrapperPass>();
111 MachineFunctionPass::getAnalysisUsage(AU);
112 }
113};
114
115} // end anonymous namespace
116
117char RenameIndependentSubregsLegacy::ID;
118
119char &llvm::RenameIndependentSubregsID = RenameIndependentSubregsLegacy::ID;
120
121INITIALIZE_PASS_BEGIN(RenameIndependentSubregsLegacy, DEBUG_TYPE,
122 "Rename Independent Subregisters", false, false)
123INITIALIZE_PASS_DEPENDENCY(SlotIndexesWrapperPass)
124INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)
125INITIALIZE_PASS_END(RenameIndependentSubregsLegacy, DEBUG_TYPE,
126 "Rename Independent Subregisters", false, false)
127
128bool RenameIndependentSubregs::renameComponents(LiveInterval &LI) const {
129 // Shortcut: We cannot have split components with a single definition.
130 if (LI.valnos.size() < 2)
131 return false;
132
133 SmallVector<SubRangeInfo, 4> SubRangeInfos;
134 IntEqClasses Classes;
135 if (!findComponents(Classes, SubRangeInfos, LI))
136 return false;
137
138 // Create a new VReg for each class.
139 Register Reg = LI.reg();
140 const TargetRegisterClass *RegClass = MRI->getRegClass(Reg);
141 SmallVector<LiveInterval*, 4> Intervals;
142 Intervals.push_back(Elt: &LI);
143 LLVM_DEBUG(dbgs() << printReg(Reg) << ": Found " << Classes.getNumClasses()
144 << " equivalence classes.\n");
145 LLVM_DEBUG(dbgs() << printReg(Reg) << ": Splitting into newly created:");
146 for (unsigned I = 1, NumClasses = Classes.getNumClasses(); I < NumClasses;
147 ++I) {
148 Register NewVReg = MRI->createVirtualRegister(RegClass);
149 LiveInterval &NewLI = LIS->createEmptyInterval(Reg: NewVReg);
150 Intervals.push_back(Elt: &NewLI);
151 LLVM_DEBUG(dbgs() << ' ' << printReg(NewVReg));
152 }
153 LLVM_DEBUG(dbgs() << '\n');
154
155 rewriteOperands(Classes, SubRangeInfos, Intervals);
156 distribute(Classes, SubRangeInfos, Intervals);
157 computeMainRangesFixFlags(Classes, SubRangeInfos, Intervals);
158 return true;
159}
160
161bool RenameIndependentSubregs::findComponents(IntEqClasses &Classes,
162 SmallVectorImpl<RenameIndependentSubregs::SubRangeInfo> &SubRangeInfos,
163 LiveInterval &LI) const {
164 // First step: Create connected components for the VNInfos inside the
165 // subranges and count the global number of such components.
166 unsigned NumComponents = 0;
167 for (LiveInterval::SubRange &SR : LI.subranges()) {
168 SubRangeInfos.push_back(Elt: SubRangeInfo(*LIS, SR, NumComponents));
169 ConnectedVNInfoEqClasses &ConEQ = SubRangeInfos.back().ConEQ;
170
171 unsigned NumSubComponents = ConEQ.Classify(LR: SR);
172 NumComponents += NumSubComponents;
173 }
174 // Shortcut: With only 1 subrange, the normal separate component tests are
175 // enough and we do not need to perform the union-find on the subregister
176 // segments.
177 if (SubRangeInfos.size() < 2)
178 return false;
179
180 // Next step: Build union-find structure over all subranges and merge classes
181 // across subranges when they are affected by the same MachineOperand.
182 const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
183 Classes.grow(N: NumComponents);
184 Register Reg = LI.reg();
185 for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
186 if (!MO.isDef() && !MO.readsReg())
187 continue;
188 unsigned SubRegIdx = MO.getSubReg();
189 LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubIdx: SubRegIdx);
190 unsigned MergedID = ~0u;
191 for (RenameIndependentSubregs::SubRangeInfo &SRInfo : SubRangeInfos) {
192 const LiveInterval::SubRange &SR = *SRInfo.SR;
193 if ((SR.LaneMask & LaneMask).none())
194 continue;
195 SlotIndex Pos = LIS->getInstructionIndex(Instr: *MO.getParent());
196 Pos = MO.isDef() ? Pos.getRegSlot(EC: MO.isEarlyClobber())
197 : Pos.getBaseIndex();
198 const VNInfo *VNI = SR.getVNInfoAt(Idx: Pos);
199 if (VNI == nullptr)
200 continue;
201
202 // Map to local representant ID.
203 unsigned LocalID = SRInfo.ConEQ.getEqClass(VNI);
204 // Global ID
205 unsigned ID = LocalID + SRInfo.Index;
206 // Merge other sets
207 MergedID = MergedID == ~0u ? ID : Classes.join(a: MergedID, b: ID);
208 }
209 }
210
211 // Early exit if we ended up with a single equivalence class.
212 Classes.compress();
213 unsigned NumClasses = Classes.getNumClasses();
214 return NumClasses > 1;
215}
216
217void RenameIndependentSubregs::rewriteOperands(const IntEqClasses &Classes,
218 const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
219 const SmallVectorImpl<LiveInterval*> &Intervals) const {
220 const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
221 Register Reg = Intervals[0]->reg();
222 for (MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(RegNo: Reg),
223 E = MRI->reg_nodbg_end(); I != E; ) {
224 MachineOperand &MO = *I++;
225 if (!MO.isDef() && !MO.readsReg())
226 continue;
227
228 auto *MI = MO.getParent();
229 SlotIndex Pos = LIS->getInstructionIndex(Instr: *MI);
230 Pos = MO.isDef() ? Pos.getRegSlot(EC: MO.isEarlyClobber())
231 : Pos.getBaseIndex();
232 unsigned SubRegIdx = MO.getSubReg();
233 LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubIdx: SubRegIdx);
234
235 unsigned ID = ~0u;
236 for (const SubRangeInfo &SRInfo : SubRangeInfos) {
237 const LiveInterval::SubRange &SR = *SRInfo.SR;
238 if ((SR.LaneMask & LaneMask).none())
239 continue;
240 const VNInfo *VNI = SR.getVNInfoAt(Idx: Pos);
241 if (VNI == nullptr)
242 continue;
243
244 // Map to local representant ID.
245 unsigned LocalID = SRInfo.ConEQ.getEqClass(VNI);
246 // Global ID
247 ID = Classes[LocalID + SRInfo.Index];
248 break;
249 }
250
251 Register VReg = Intervals[ID]->reg();
252 MO.setReg(VReg);
253
254 if (MO.isTied() && Reg != VReg) {
255 /// Undef use operands are not tracked in the equivalence class,
256 /// but need to be updated if they are tied; take care to only
257 /// update the tied operand.
258 unsigned OperandNo = MO.getOperandNo();
259 unsigned TiedIdx = MI->findTiedOperandIdx(OpIdx: OperandNo);
260 MI->getOperand(i: TiedIdx).setReg(VReg);
261
262 // above substitution breaks the iterator, so restart.
263 I = MRI->reg_nodbg_begin(RegNo: Reg);
264 }
265 }
266 // TODO: We could attempt to recompute new register classes while visiting
267 // the operands: Some of the split register may be fine with less constraint
268 // classes than the original vreg.
269}
270
271void RenameIndependentSubregs::distribute(const IntEqClasses &Classes,
272 const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
273 const SmallVectorImpl<LiveInterval*> &Intervals) const {
274 unsigned NumClasses = Classes.getNumClasses();
275 SmallVector<unsigned, 8> VNIMapping;
276 SmallVector<LiveInterval::SubRange*, 8> SubRanges;
277 BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
278 for (const SubRangeInfo &SRInfo : SubRangeInfos) {
279 LiveInterval::SubRange &SR = *SRInfo.SR;
280 unsigned NumValNos = SR.valnos.size();
281 VNIMapping.clear();
282 VNIMapping.reserve(N: NumValNos);
283 SubRanges.clear();
284 SubRanges.resize(N: NumClasses-1, NV: nullptr);
285 for (unsigned I = 0; I < NumValNos; ++I) {
286 const VNInfo &VNI = *SR.valnos[I];
287 unsigned LocalID = SRInfo.ConEQ.getEqClass(VNI: &VNI);
288 unsigned ID = Classes[LocalID + SRInfo.Index];
289 VNIMapping.push_back(Elt: ID);
290 if (ID > 0 && SubRanges[ID-1] == nullptr)
291 SubRanges[ID-1] = Intervals[ID]->createSubRange(Allocator, LaneMask: SR.LaneMask);
292 }
293 DistributeRange(LR&: SR, SplitLRs: SubRanges.data(), VNIClasses: VNIMapping);
294 }
295}
296
297static bool subRangeLiveAt(const LiveInterval &LI, SlotIndex Pos) {
298 for (const LiveInterval::SubRange &SR : LI.subranges()) {
299 if (SR.liveAt(index: Pos))
300 return true;
301 }
302 return false;
303}
304
305void RenameIndependentSubregs::computeMainRangesFixFlags(
306 const IntEqClasses &Classes,
307 const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
308 const SmallVectorImpl<LiveInterval*> &Intervals) const {
309 const TargetRegisterInfo &TRI = TII->getRegisterInfo();
310 BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
311 const SlotIndexes &Indexes = *LIS->getSlotIndexes();
312 for (size_t I = 0, E = Intervals.size(); I < E; ++I) {
313 LiveInterval &LI = *Intervals[I];
314 Register Reg = LI.reg();
315
316 LI.removeEmptySubRanges();
317
318 // Try to establish a single subregister which covers all uses.
319 // Note: this is assuming the selected subregister will only be
320 // used for fixing up live intervals issues created by this pass.
321 LaneBitmask UsedMask, UnusedMask;
322 for (LiveInterval::SubRange &SR : LI.subranges())
323 UsedMask |= SR.LaneMask;
324 SmallVector<unsigned> SubRegIdxs;
325 RegState Flags = {};
326 unsigned SubReg = 0;
327 // TODO: Handle SubRegIdxs.size() > 1
328 if (TRI.getCoveringSubRegIndexes(RC: MRI->getRegClass(Reg), LaneMask: UsedMask,
329 Indexes&: SubRegIdxs) &&
330 SubRegIdxs.size() == 1) {
331 SubReg = SubRegIdxs.front();
332 Flags = RegState::Undef;
333 } else {
334 UnusedMask = MRI->getMaxLaneMaskForVReg(Reg) & ~UsedMask;
335 }
336
337 // There must be a def (or live-in) before every use. Splitting vregs may
338 // violate this principle as the splitted vreg may not have a definition on
339 // every path. Fix this by creating IMPLICIT_DEF instruction as necessary.
340 for (const LiveInterval::SubRange &SR : LI.subranges()) {
341 // Search for "PHI" value numbers in the subranges. We must find a live
342 // value in each predecessor block, add an IMPLICIT_DEF where it is
343 // missing.
344 for (unsigned I = 0; I < SR.valnos.size(); ++I) {
345 const VNInfo &VNI = *SR.valnos[I];
346 if (VNI.isUnused() || !VNI.isPHIDef())
347 continue;
348
349 SlotIndex Def = VNI.def;
350 MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(index: Def);
351 for (MachineBasicBlock *PredMBB : MBB.predecessors()) {
352 SlotIndex PredEnd = Indexes.getMBBEndIdx(mbb: PredMBB);
353 if (subRangeLiveAt(LI, Pos: PredEnd.getPrevSlot()))
354 continue;
355
356 MachineBasicBlock::iterator InsertPos =
357 llvm::findPHICopyInsertPoint(MBB: PredMBB, SuccMBB: &MBB, SrcReg: Reg);
358 const MCInstrDesc &MCDesc = TII->get(Opcode: TargetOpcode::IMPLICIT_DEF);
359 MachineInstrBuilder ImpDef =
360 BuildMI(BB&: *PredMBB, I: InsertPos, MIMD: DebugLoc(), MCID: MCDesc)
361 .addDef(RegNo: Reg, Flags, SubReg);
362 SlotIndex DefIdx = LIS->InsertMachineInstrInMaps(MI&: *ImpDef);
363 SlotIndex RegDefIdx = DefIdx.getRegSlot();
364 for (LiveInterval::SubRange &SR : LI.subranges()) {
365 VNInfo *SRVNI = SR.getNextValue(Def: RegDefIdx, VNInfoAllocator&: Allocator);
366 SR.addSegment(S: LiveRange::Segment(RegDefIdx, PredEnd, SRVNI));
367 }
368 if (!UnusedMask.none()) {
369 LiveInterval::SubRange *SR =
370 LI.createSubRange(Allocator, LaneMask: UnusedMask);
371 SR->createDeadDef(Def: RegDefIdx, VNIAlloc&: Allocator);
372 }
373 }
374 }
375 }
376
377 for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
378 if (!MO.isDef())
379 continue;
380 unsigned SubRegIdx = MO.getSubReg();
381 if (SubRegIdx == 0)
382 continue;
383 // After assigning the new vreg we may not have any other sublanes living
384 // in and out of the instruction anymore. We need to add new dead and
385 // undef flags in these cases.
386 if (!MO.isUndef()) {
387 SlotIndex Pos = LIS->getInstructionIndex(Instr: *MO.getParent());
388 if (!subRangeLiveAt(LI, Pos))
389 MO.setIsUndef();
390 }
391 if (!MO.isDead()) {
392 SlotIndex Pos = LIS->getInstructionIndex(Instr: *MO.getParent()).getDeadSlot();
393 if (!subRangeLiveAt(LI, Pos))
394 MO.setIsDead();
395 }
396 }
397
398 if (I == 0)
399 LI.clear();
400 LIS->constructMainRangeFromSubranges(LI);
401 // A def of a subregister may be a use of other register lanes. Replacing
402 // such a def with a def of a different register will eliminate the use,
403 // and may cause the recorded live range to be larger than the actual
404 // liveness in the program IR.
405 LIS->shrinkToUses(li: &LI);
406 }
407}
408
409PreservedAnalyses
410RenameIndependentSubregsPass::run(MachineFunction &MF,
411 MachineFunctionAnalysisManager &MFAM) {
412 auto &LIS = MFAM.getResult<LiveIntervalsAnalysis>(IR&: MF);
413 if (!RenameIndependentSubregs(&LIS).run(MF))
414 return PreservedAnalyses::all();
415 auto PA = getMachineFunctionPassPreservedAnalyses();
416 PA.preserveSet<CFGAnalyses>();
417 PA.preserve<LiveIntervalsAnalysis>();
418 PA.preserve<SlotIndexesAnalysis>();
419 return PA;
420}
421
422bool RenameIndependentSubregsLegacy::runOnMachineFunction(MachineFunction &MF) {
423 auto &LIS = getAnalysis<LiveIntervalsWrapperPass>().getLIS();
424 return RenameIndependentSubregs(&LIS).run(MF);
425}
426
427bool RenameIndependentSubregs::run(MachineFunction &MF) {
428 // Skip renaming if liveness of subregister is not tracked.
429 MRI = &MF.getRegInfo();
430 if (!MRI->subRegLivenessEnabled())
431 return false;
432
433 LLVM_DEBUG(dbgs() << "Renaming independent subregister live ranges in "
434 << MF.getName() << '\n');
435
436 TII = MF.getSubtarget().getInstrInfo();
437
438 // Iterate over all vregs. Note that we query getNumVirtRegs() the newly
439 // created vregs end up with higher numbers but do not need to be visited as
440 // there can't be any further splitting.
441 bool Changed = false;
442 for (size_t I = 0, E = MRI->getNumVirtRegs(); I < E; ++I) {
443 Register Reg = Register::index2VirtReg(Index: I);
444 if (!LIS->hasInterval(Reg))
445 continue;
446 LiveInterval &LI = LIS->getInterval(Reg);
447 if (!LI.hasSubRanges())
448 continue;
449
450 Changed |= renameComponents(LI);
451 }
452
453 return Changed;
454}
455