1 //===-- RenameIndependentSubregs.cpp - Live Interval Analysis -------------===//
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
7 //===----------------------------------------------------------------------===//
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> = ...
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> = ...
23 /// %2:sub1<read-undef> = ...
27 //===----------------------------------------------------------------------===//
29 #include "LiveRangeUtils.h"
30 #include "PHIEliminationUtils.h"
31 #include "llvm/CodeGen/LiveInterval.h"
32 #include "llvm/CodeGen/LiveIntervals.h"
33 #include "llvm/CodeGen/MachineFunctionPass.h"
34 #include "llvm/CodeGen/MachineInstrBuilder.h"
35 #include "llvm/CodeGen/MachineRegisterInfo.h"
36 #include "llvm/CodeGen/Passes.h"
37 #include "llvm/CodeGen/TargetInstrInfo.h"
41 #define DEBUG_TYPE "rename-independent-subregs"
45 class RenameIndependentSubregs
: public MachineFunctionPass
{
48 RenameIndependentSubregs() : MachineFunctionPass(ID
) {}
50 StringRef
getPassName() const override
{
51 return "Rename Disconnected Subregister Components";
54 void getAnalysisUsage(AnalysisUsage
&AU
) const override
{
56 AU
.addRequired
<LiveIntervals
>();
57 AU
.addPreserved
<LiveIntervals
>();
58 AU
.addRequired
<SlotIndexes
>();
59 AU
.addPreserved
<SlotIndexes
>();
60 MachineFunctionPass::getAnalysisUsage(AU
);
63 bool runOnMachineFunction(MachineFunction
&MF
) override
;
67 ConnectedVNInfoEqClasses ConEQ
;
68 LiveInterval::SubRange
*SR
;
71 SubRangeInfo(LiveIntervals
&LIS
, LiveInterval::SubRange
&SR
,
73 : ConEQ(LIS
), SR(&SR
), Index(Index
) {}
76 /// Split unrelated subregister components and rename them to new vregs.
77 bool renameComponents(LiveInterval
&LI
) const;
79 /// Build a vector of SubRange infos and a union find set of
80 /// equivalence classes.
81 /// Returns true if more than 1 equivalence class was found.
82 bool findComponents(IntEqClasses
&Classes
,
83 SmallVectorImpl
<SubRangeInfo
> &SubRangeInfos
,
84 LiveInterval
&LI
) const;
86 /// Distribute the LiveInterval segments into the new LiveIntervals
87 /// belonging to their class.
88 void distribute(const IntEqClasses
&Classes
,
89 const SmallVectorImpl
<SubRangeInfo
> &SubRangeInfos
,
90 const SmallVectorImpl
<LiveInterval
*> &Intervals
) const;
92 /// Constructs main liverange and add missing undef+dead flags.
93 void computeMainRangesFixFlags(const IntEqClasses
&Classes
,
94 const SmallVectorImpl
<SubRangeInfo
> &SubRangeInfos
,
95 const SmallVectorImpl
<LiveInterval
*> &Intervals
) const;
97 /// Rewrite Machine Operands to use the new vreg belonging to their class.
98 void rewriteOperands(const IntEqClasses
&Classes
,
99 const SmallVectorImpl
<SubRangeInfo
> &SubRangeInfos
,
100 const SmallVectorImpl
<LiveInterval
*> &Intervals
) const;
104 MachineRegisterInfo
*MRI
;
105 const TargetInstrInfo
*TII
;
108 } // end anonymous namespace
110 char RenameIndependentSubregs::ID
;
112 char &llvm::RenameIndependentSubregsID
= RenameIndependentSubregs::ID
;
114 INITIALIZE_PASS_BEGIN(RenameIndependentSubregs
, DEBUG_TYPE
,
115 "Rename Independent Subregisters", false, false)
116 INITIALIZE_PASS_DEPENDENCY(SlotIndexes
)
117 INITIALIZE_PASS_DEPENDENCY(LiveIntervals
)
118 INITIALIZE_PASS_END(RenameIndependentSubregs
, DEBUG_TYPE
,
119 "Rename Independent Subregisters", false, false)
121 bool RenameIndependentSubregs::renameComponents(LiveInterval
&LI
) const {
122 // Shortcut: We cannot have split components with a single definition.
123 if (LI
.valnos
.size() < 2)
126 SmallVector
<SubRangeInfo
, 4> SubRangeInfos
;
127 IntEqClasses Classes
;
128 if (!findComponents(Classes
, SubRangeInfos
, LI
))
131 // Create a new VReg for each class.
132 unsigned Reg
= LI
.reg
;
133 const TargetRegisterClass
*RegClass
= MRI
->getRegClass(Reg
);
134 SmallVector
<LiveInterval
*, 4> Intervals
;
135 Intervals
.push_back(&LI
);
136 LLVM_DEBUG(dbgs() << printReg(Reg
) << ": Found " << Classes
.getNumClasses()
137 << " equivalence classes.\n");
138 LLVM_DEBUG(dbgs() << printReg(Reg
) << ": Splitting into newly created:");
139 for (unsigned I
= 1, NumClasses
= Classes
.getNumClasses(); I
< NumClasses
;
141 Register NewVReg
= MRI
->createVirtualRegister(RegClass
);
142 LiveInterval
&NewLI
= LIS
->createEmptyInterval(NewVReg
);
143 Intervals
.push_back(&NewLI
);
144 LLVM_DEBUG(dbgs() << ' ' << printReg(NewVReg
));
146 LLVM_DEBUG(dbgs() << '\n');
148 rewriteOperands(Classes
, SubRangeInfos
, Intervals
);
149 distribute(Classes
, SubRangeInfos
, Intervals
);
150 computeMainRangesFixFlags(Classes
, SubRangeInfos
, Intervals
);
154 bool RenameIndependentSubregs::findComponents(IntEqClasses
&Classes
,
155 SmallVectorImpl
<RenameIndependentSubregs::SubRangeInfo
> &SubRangeInfos
,
156 LiveInterval
&LI
) const {
157 // First step: Create connected components for the VNInfos inside the
158 // subranges and count the global number of such components.
159 unsigned NumComponents
= 0;
160 for (LiveInterval::SubRange
&SR
: LI
.subranges()) {
161 SubRangeInfos
.push_back(SubRangeInfo(*LIS
, SR
, NumComponents
));
162 ConnectedVNInfoEqClasses
&ConEQ
= SubRangeInfos
.back().ConEQ
;
164 unsigned NumSubComponents
= ConEQ
.Classify(SR
);
165 NumComponents
+= NumSubComponents
;
167 // Shortcut: With only 1 subrange, the normal separate component tests are
168 // enough and we do not need to perform the union-find on the subregister
170 if (SubRangeInfos
.size() < 2)
173 // Next step: Build union-find structure over all subranges and merge classes
174 // across subranges when they are affected by the same MachineOperand.
175 const TargetRegisterInfo
&TRI
= *MRI
->getTargetRegisterInfo();
176 Classes
.grow(NumComponents
);
177 unsigned Reg
= LI
.reg
;
178 for (const MachineOperand
&MO
: MRI
->reg_nodbg_operands(Reg
)) {
179 if (!MO
.isDef() && !MO
.readsReg())
181 unsigned SubRegIdx
= MO
.getSubReg();
182 LaneBitmask LaneMask
= TRI
.getSubRegIndexLaneMask(SubRegIdx
);
183 unsigned MergedID
= ~0u;
184 for (RenameIndependentSubregs::SubRangeInfo
&SRInfo
: SubRangeInfos
) {
185 const LiveInterval::SubRange
&SR
= *SRInfo
.SR
;
186 if ((SR
.LaneMask
& LaneMask
).none())
188 SlotIndex Pos
= LIS
->getInstructionIndex(*MO
.getParent());
189 Pos
= MO
.isDef() ? Pos
.getRegSlot(MO
.isEarlyClobber())
190 : Pos
.getBaseIndex();
191 const VNInfo
*VNI
= SR
.getVNInfoAt(Pos
);
195 // Map to local representant ID.
196 unsigned LocalID
= SRInfo
.ConEQ
.getEqClass(VNI
);
198 unsigned ID
= LocalID
+ SRInfo
.Index
;
200 MergedID
= MergedID
== ~0u ? ID
: Classes
.join(MergedID
, ID
);
204 // Early exit if we ended up with a single equivalence class.
206 unsigned NumClasses
= Classes
.getNumClasses();
207 return NumClasses
> 1;
210 void RenameIndependentSubregs::rewriteOperands(const IntEqClasses
&Classes
,
211 const SmallVectorImpl
<SubRangeInfo
> &SubRangeInfos
,
212 const SmallVectorImpl
<LiveInterval
*> &Intervals
) const {
213 const TargetRegisterInfo
&TRI
= *MRI
->getTargetRegisterInfo();
214 unsigned Reg
= Intervals
[0]->reg
;
215 for (MachineRegisterInfo::reg_nodbg_iterator I
= MRI
->reg_nodbg_begin(Reg
),
216 E
= MRI
->reg_nodbg_end(); I
!= E
; ) {
217 MachineOperand
&MO
= *I
++;
218 if (!MO
.isDef() && !MO
.readsReg())
221 auto *MI
= MO
.getParent();
222 SlotIndex Pos
= LIS
->getInstructionIndex(*MI
);
223 Pos
= MO
.isDef() ? Pos
.getRegSlot(MO
.isEarlyClobber())
224 : Pos
.getBaseIndex();
225 unsigned SubRegIdx
= MO
.getSubReg();
226 LaneBitmask LaneMask
= TRI
.getSubRegIndexLaneMask(SubRegIdx
);
229 for (const SubRangeInfo
&SRInfo
: SubRangeInfos
) {
230 const LiveInterval::SubRange
&SR
= *SRInfo
.SR
;
231 if ((SR
.LaneMask
& LaneMask
).none())
233 const VNInfo
*VNI
= SR
.getVNInfoAt(Pos
);
237 // Map to local representant ID.
238 unsigned LocalID
= SRInfo
.ConEQ
.getEqClass(VNI
);
240 ID
= Classes
[LocalID
+ SRInfo
.Index
];
244 unsigned VReg
= Intervals
[ID
]->reg
;
247 if (MO
.isTied() && Reg
!= VReg
) {
248 /// Undef use operands are not tracked in the equivalence class,
249 /// but need to be updated if they are tied; take care to only
250 /// update the tied operand.
251 unsigned OperandNo
= MI
->getOperandNo(&MO
);
252 unsigned TiedIdx
= MI
->findTiedOperandIdx(OperandNo
);
253 MI
->getOperand(TiedIdx
).setReg(VReg
);
255 // above substitution breaks the iterator, so restart.
256 I
= MRI
->reg_nodbg_begin(Reg
);
259 // TODO: We could attempt to recompute new register classes while visiting
260 // the operands: Some of the split register may be fine with less constraint
261 // classes than the original vreg.
264 void RenameIndependentSubregs::distribute(const IntEqClasses
&Classes
,
265 const SmallVectorImpl
<SubRangeInfo
> &SubRangeInfos
,
266 const SmallVectorImpl
<LiveInterval
*> &Intervals
) const {
267 unsigned NumClasses
= Classes
.getNumClasses();
268 SmallVector
<unsigned, 8> VNIMapping
;
269 SmallVector
<LiveInterval::SubRange
*, 8> SubRanges
;
270 BumpPtrAllocator
&Allocator
= LIS
->getVNInfoAllocator();
271 for (const SubRangeInfo
&SRInfo
: SubRangeInfos
) {
272 LiveInterval::SubRange
&SR
= *SRInfo
.SR
;
273 unsigned NumValNos
= SR
.valnos
.size();
275 VNIMapping
.reserve(NumValNos
);
277 SubRanges
.resize(NumClasses
-1, nullptr);
278 for (unsigned I
= 0; I
< NumValNos
; ++I
) {
279 const VNInfo
&VNI
= *SR
.valnos
[I
];
280 unsigned LocalID
= SRInfo
.ConEQ
.getEqClass(&VNI
);
281 unsigned ID
= Classes
[LocalID
+ SRInfo
.Index
];
282 VNIMapping
.push_back(ID
);
283 if (ID
> 0 && SubRanges
[ID
-1] == nullptr)
284 SubRanges
[ID
-1] = Intervals
[ID
]->createSubRange(Allocator
, SR
.LaneMask
);
286 DistributeRange(SR
, SubRanges
.data(), VNIMapping
);
290 static bool subRangeLiveAt(const LiveInterval
&LI
, SlotIndex Pos
) {
291 for (const LiveInterval::SubRange
&SR
: LI
.subranges()) {
298 void RenameIndependentSubregs::computeMainRangesFixFlags(
299 const IntEqClasses
&Classes
,
300 const SmallVectorImpl
<SubRangeInfo
> &SubRangeInfos
,
301 const SmallVectorImpl
<LiveInterval
*> &Intervals
) const {
302 BumpPtrAllocator
&Allocator
= LIS
->getVNInfoAllocator();
303 const SlotIndexes
&Indexes
= *LIS
->getSlotIndexes();
304 for (size_t I
= 0, E
= Intervals
.size(); I
< E
; ++I
) {
305 LiveInterval
&LI
= *Intervals
[I
];
306 unsigned Reg
= LI
.reg
;
308 LI
.removeEmptySubRanges();
310 // There must be a def (or live-in) before every use. Splitting vregs may
311 // violate this principle as the splitted vreg may not have a definition on
312 // every path. Fix this by creating IMPLICIT_DEF instruction as necessary.
313 for (const LiveInterval::SubRange
&SR
: LI
.subranges()) {
314 // Search for "PHI" value numbers in the subranges. We must find a live
315 // value in each predecessor block, add an IMPLICIT_DEF where it is
317 for (unsigned I
= 0; I
< SR
.valnos
.size(); ++I
) {
318 const VNInfo
&VNI
= *SR
.valnos
[I
];
319 if (VNI
.isUnused() || !VNI
.isPHIDef())
322 SlotIndex Def
= VNI
.def
;
323 MachineBasicBlock
&MBB
= *Indexes
.getMBBFromIndex(Def
);
324 for (MachineBasicBlock
*PredMBB
: MBB
.predecessors()) {
325 SlotIndex PredEnd
= Indexes
.getMBBEndIdx(PredMBB
);
326 if (subRangeLiveAt(LI
, PredEnd
.getPrevSlot()))
329 MachineBasicBlock::iterator InsertPos
=
330 llvm::findPHICopyInsertPoint(PredMBB
, &MBB
, Reg
);
331 const MCInstrDesc
&MCDesc
= TII
->get(TargetOpcode::IMPLICIT_DEF
);
332 MachineInstrBuilder ImpDef
= BuildMI(*PredMBB
, InsertPos
,
333 DebugLoc(), MCDesc
, Reg
);
334 SlotIndex DefIdx
= LIS
->InsertMachineInstrInMaps(*ImpDef
);
335 SlotIndex RegDefIdx
= DefIdx
.getRegSlot();
336 for (LiveInterval::SubRange
&SR
: LI
.subranges()) {
337 VNInfo
*SRVNI
= SR
.getNextValue(RegDefIdx
, Allocator
);
338 SR
.addSegment(LiveRange::Segment(RegDefIdx
, PredEnd
, SRVNI
));
344 for (MachineOperand
&MO
: MRI
->reg_nodbg_operands(Reg
)) {
347 unsigned SubRegIdx
= MO
.getSubReg();
350 // After assigning the new vreg we may not have any other sublanes living
351 // in and out of the instruction anymore. We need to add new dead and
352 // undef flags in these cases.
354 SlotIndex Pos
= LIS
->getInstructionIndex(*MO
.getParent());
355 if (!subRangeLiveAt(LI
, Pos
))
359 SlotIndex Pos
= LIS
->getInstructionIndex(*MO
.getParent()).getDeadSlot();
360 if (!subRangeLiveAt(LI
, Pos
))
367 LIS
->constructMainRangeFromSubranges(LI
);
368 // A def of a subregister may be a use of other register lanes. Replacing
369 // such a def with a def of a different register will eliminate the use,
370 // and may cause the recorded live range to be larger than the actual
371 // liveness in the program IR.
372 LIS
->shrinkToUses(&LI
);
376 bool RenameIndependentSubregs::runOnMachineFunction(MachineFunction
&MF
) {
377 // Skip renaming if liveness of subregister is not tracked.
378 MRI
= &MF
.getRegInfo();
379 if (!MRI
->subRegLivenessEnabled())
382 LLVM_DEBUG(dbgs() << "Renaming independent subregister live ranges in "
383 << MF
.getName() << '\n');
385 LIS
= &getAnalysis
<LiveIntervals
>();
386 TII
= MF
.getSubtarget().getInstrInfo();
388 // Iterate over all vregs. Note that we query getNumVirtRegs() the newly
389 // created vregs end up with higher numbers but do not need to be visited as
390 // there can't be any further splitting.
391 bool Changed
= false;
392 for (size_t I
= 0, E
= MRI
->getNumVirtRegs(); I
< E
; ++I
) {
393 unsigned Reg
= Register::index2VirtReg(I
);
394 if (!LIS
->hasInterval(Reg
))
396 LiveInterval
&LI
= LIS
->getInterval(Reg
);
397 if (!LI
.hasSubRanges())
400 Changed
|= renameComponents(LI
);