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 BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
310 const SlotIndexes &Indexes = *LIS->getSlotIndexes();
311 for (size_t I = 0, E = Intervals.size(); I < E; ++I) {
312 LiveInterval &LI = *Intervals[I];
313 Register Reg = LI.reg();
314
315 LI.removeEmptySubRanges();
316
317 // There must be a def (or live-in) before every use. Splitting vregs may
318 // violate this principle as the splitted vreg may not have a definition on
319 // every path. Fix this by creating IMPLICIT_DEF instruction as necessary.
320 for (const LiveInterval::SubRange &SR : LI.subranges()) {
321 // Search for "PHI" value numbers in the subranges. We must find a live
322 // value in each predecessor block, add an IMPLICIT_DEF where it is
323 // missing.
324 for (unsigned I = 0; I < SR.valnos.size(); ++I) {
325 const VNInfo &VNI = *SR.valnos[I];
326 if (VNI.isUnused() || !VNI.isPHIDef())
327 continue;
328
329 SlotIndex Def = VNI.def;
330 MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(index: Def);
331 for (MachineBasicBlock *PredMBB : MBB.predecessors()) {
332 SlotIndex PredEnd = Indexes.getMBBEndIdx(mbb: PredMBB);
333 if (subRangeLiveAt(LI, Pos: PredEnd.getPrevSlot()))
334 continue;
335
336 MachineBasicBlock::iterator InsertPos =
337 llvm::findPHICopyInsertPoint(MBB: PredMBB, SuccMBB: &MBB, SrcReg: Reg);
338 const MCInstrDesc &MCDesc = TII->get(Opcode: TargetOpcode::IMPLICIT_DEF);
339 MachineInstrBuilder ImpDef = BuildMI(BB&: *PredMBB, I: InsertPos,
340 MIMD: DebugLoc(), MCID: MCDesc, DestReg: Reg);
341 SlotIndex DefIdx = LIS->InsertMachineInstrInMaps(MI&: *ImpDef);
342 SlotIndex RegDefIdx = DefIdx.getRegSlot();
343 LaneBitmask Mask = MRI->getMaxLaneMaskForVReg(Reg);
344 for (LiveInterval::SubRange &SR : LI.subranges()) {
345 Mask = Mask & ~SR.LaneMask;
346 VNInfo *SRVNI = SR.getNextValue(Def: RegDefIdx, VNInfoAllocator&: Allocator);
347 SR.addSegment(S: LiveRange::Segment(RegDefIdx, PredEnd, SRVNI));
348 }
349
350 if (!Mask.none()) {
351 LiveInterval::SubRange *SR = LI.createSubRange(Allocator, LaneMask: Mask);
352 SR->createDeadDef(Def: RegDefIdx, VNIAlloc&: Allocator);
353 }
354 }
355 }
356 }
357
358 for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
359 if (!MO.isDef())
360 continue;
361 unsigned SubRegIdx = MO.getSubReg();
362 if (SubRegIdx == 0)
363 continue;
364 // After assigning the new vreg we may not have any other sublanes living
365 // in and out of the instruction anymore. We need to add new dead and
366 // undef flags in these cases.
367 if (!MO.isUndef()) {
368 SlotIndex Pos = LIS->getInstructionIndex(Instr: *MO.getParent());
369 if (!subRangeLiveAt(LI, Pos))
370 MO.setIsUndef();
371 }
372 if (!MO.isDead()) {
373 SlotIndex Pos = LIS->getInstructionIndex(Instr: *MO.getParent()).getDeadSlot();
374 if (!subRangeLiveAt(LI, Pos))
375 MO.setIsDead();
376 }
377 }
378
379 if (I == 0)
380 LI.clear();
381 LIS->constructMainRangeFromSubranges(LI);
382 // A def of a subregister may be a use of other register lanes. Replacing
383 // such a def with a def of a different register will eliminate the use,
384 // and may cause the recorded live range to be larger than the actual
385 // liveness in the program IR.
386 LIS->shrinkToUses(li: &LI);
387 }
388}
389
390PreservedAnalyses
391RenameIndependentSubregsPass::run(MachineFunction &MF,
392 MachineFunctionAnalysisManager &MFAM) {
393 auto &LIS = MFAM.getResult<LiveIntervalsAnalysis>(IR&: MF);
394 if (!RenameIndependentSubregs(&LIS).run(MF))
395 return PreservedAnalyses::all();
396 auto PA = getMachineFunctionPassPreservedAnalyses();
397 PA.preserveSet<CFGAnalyses>();
398 PA.preserve<LiveIntervalsAnalysis>();
399 PA.preserve<SlotIndexesAnalysis>();
400 return PA;
401}
402
403bool RenameIndependentSubregsLegacy::runOnMachineFunction(MachineFunction &MF) {
404 auto &LIS = getAnalysis<LiveIntervalsWrapperPass>().getLIS();
405 return RenameIndependentSubregs(&LIS).run(MF);
406}
407
408bool RenameIndependentSubregs::run(MachineFunction &MF) {
409 // Skip renaming if liveness of subregister is not tracked.
410 MRI = &MF.getRegInfo();
411 if (!MRI->subRegLivenessEnabled())
412 return false;
413
414 LLVM_DEBUG(dbgs() << "Renaming independent subregister live ranges in "
415 << MF.getName() << '\n');
416
417 TII = MF.getSubtarget().getInstrInfo();
418
419 // Iterate over all vregs. Note that we query getNumVirtRegs() the newly
420 // created vregs end up with higher numbers but do not need to be visited as
421 // there can't be any further splitting.
422 bool Changed = false;
423 for (size_t I = 0, E = MRI->getNumVirtRegs(); I < E; ++I) {
424 Register Reg = Register::index2VirtReg(Index: I);
425 if (!LIS->hasInterval(Reg))
426 continue;
427 LiveInterval &LI = LIS->getInterval(Reg);
428 if (!LI.hasSubRanges())
429 continue;
430
431 Changed |= renameComponents(LI);
432 }
433
434 return Changed;
435}
436