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