1 //===- InitUndef.cpp - Initialize undef value to pseudo ----===//
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 // This file implements a function pass that initializes undef value to
10 // temporary pseudo instruction to prevent register allocation resulting in a
11 // constraint violated result for the particular instruction. It also rewrites
12 // the NoReg tied operand back to an IMPLICIT_DEF.
13 //
14 // Certain instructions have register overlapping constraints, and
15 // will cause illegal instruction trap if violated, we use early clobber to
16 // model this constraint, but it can't prevent register allocator allocating
17 // same or overlapped if the input register is undef value, so convert
18 // IMPLICIT_DEF to temporary pseudo instruction and remove it later could
19 // prevent that happen, it's not best way to resolve this, and it might
20 // change the order of program or increase the register pressure, so ideally we
21 // should model the constraint right, but before we model the constraint right,
22 // it's the only way to prevent that happen.
23 //
24 // When we enable the subregister liveness option, it will also trigger the same
25 // issue due to the partial of register is undef. If we pseudoinit the whole
26 // register, then it will generate redundant COPY instruction. Currently, it
27 // will generate INSERT_SUBREG to make sure the whole register is occupied
28 // when program encounter operation that has early-clobber constraint.
29 //
30 //
31 // See also: https://github.com/llvm/llvm-project/issues/50157
32 //
33 // Additionally, this pass rewrites tied operands of instructions
34 // from NoReg to IMPLICIT_DEF. (Not that this is a non-overlapping set of
35 // operands to the above.) We use NoReg to side step a MachineCSE
36 // optimization quality problem but need to convert back before
37 // TwoAddressInstruction. See pr64282 for context.
38 //
39 //===----------------------------------------------------------------------===//
40
41 #include "llvm/ADT/SmallSet.h"
42 #include "llvm/ADT/SmallVector.h"
43 #include "llvm/CodeGen/DetectDeadLanes.h"
44 #include "llvm/CodeGen/MachineFunction.h"
45 #include "llvm/CodeGen/MachineFunctionPass.h"
46 #include "llvm/CodeGen/MachineRegisterInfo.h"
47 #include "llvm/CodeGen/TargetInstrInfo.h"
48 #include "llvm/CodeGen/TargetRegisterInfo.h"
49 #include "llvm/CodeGen/TargetSubtargetInfo.h"
50 #include "llvm/InitializePasses.h"
51 #include "llvm/MC/MCRegister.h"
52 #include "llvm/Pass.h"
53 #include "llvm/Support/Debug.h"
54
55 using namespace llvm;
56
57 #define DEBUG_TYPE "init-undef"
58 #define INIT_UNDEF_NAME "Init Undef Pass"
59
60 namespace {
61
62 class InitUndef : public MachineFunctionPass {
63 const TargetInstrInfo *TII;
64 MachineRegisterInfo *MRI;
65 const TargetSubtargetInfo *ST;
66 const TargetRegisterInfo *TRI;
67
68 // Newly added vregs, assumed to be fully rewritten
69 SmallSet<Register, 8> NewRegs;
70 SmallVector<MachineInstr *, 8> DeadInsts;
71
72 public:
73 static char ID;
74
InitUndef()75 InitUndef() : MachineFunctionPass(ID) {}
76 bool runOnMachineFunction(MachineFunction &MF) override;
77
getAnalysisUsage(AnalysisUsage & AU) const78 void getAnalysisUsage(AnalysisUsage &AU) const override {
79 AU.setPreservesCFG();
80 MachineFunctionPass::getAnalysisUsage(AU);
81 }
82
getPassName() const83 StringRef getPassName() const override { return INIT_UNDEF_NAME; }
84
85 private:
86 bool processBasicBlock(MachineFunction &MF, MachineBasicBlock &MBB,
87 const DeadLaneDetector &DLD);
88 bool handleSubReg(MachineFunction &MF, MachineInstr &MI,
89 const DeadLaneDetector &DLD);
90 bool fixupIllOperand(MachineInstr *MI, MachineOperand &MO);
91 bool handleReg(MachineInstr *MI);
92 };
93
94 } // end anonymous namespace
95
96 char InitUndef::ID = 0;
97 INITIALIZE_PASS(InitUndef, DEBUG_TYPE, INIT_UNDEF_NAME, false, false)
98 char &llvm::InitUndefID = InitUndef::ID;
99
isEarlyClobberMI(MachineInstr & MI)100 static bool isEarlyClobberMI(MachineInstr &MI) {
101 return llvm::any_of(MI.defs(), [](const MachineOperand &DefMO) {
102 return DefMO.isReg() && DefMO.isEarlyClobber();
103 });
104 }
105
findImplictDefMIFromReg(Register Reg,MachineRegisterInfo * MRI)106 static bool findImplictDefMIFromReg(Register Reg, MachineRegisterInfo *MRI) {
107 for (auto &DefMI : MRI->def_instructions(Reg)) {
108 if (DefMI.getOpcode() == TargetOpcode::IMPLICIT_DEF)
109 return true;
110 }
111 return false;
112 }
113
handleReg(MachineInstr * MI)114 bool InitUndef::handleReg(MachineInstr *MI) {
115 bool Changed = false;
116 for (auto &UseMO : MI->uses()) {
117 if (!UseMO.isReg())
118 continue;
119 if (UseMO.isTied())
120 continue;
121 if (!UseMO.getReg().isVirtual())
122 continue;
123 if (!TRI->doesRegClassHavePseudoInitUndef(MRI->getRegClass(UseMO.getReg())))
124 continue;
125
126 if (UseMO.isUndef() || findImplictDefMIFromReg(UseMO.getReg(), MRI))
127 Changed |= fixupIllOperand(MI, UseMO);
128 }
129 return Changed;
130 }
131
handleSubReg(MachineFunction & MF,MachineInstr & MI,const DeadLaneDetector & DLD)132 bool InitUndef::handleSubReg(MachineFunction &MF, MachineInstr &MI,
133 const DeadLaneDetector &DLD) {
134 bool Changed = false;
135
136 for (MachineOperand &UseMO : MI.uses()) {
137 if (!UseMO.isReg())
138 continue;
139 if (!UseMO.getReg().isVirtual())
140 continue;
141 if (UseMO.isTied())
142 continue;
143 if (!TRI->doesRegClassHavePseudoInitUndef(MRI->getRegClass(UseMO.getReg())))
144 continue;
145
146 Register Reg = UseMO.getReg();
147 if (NewRegs.count(Reg))
148 continue;
149 DeadLaneDetector::VRegInfo Info =
150 DLD.getVRegInfo(Register::virtReg2Index(Reg));
151
152 if (Info.UsedLanes == Info.DefinedLanes)
153 continue;
154
155 const TargetRegisterClass *TargetRegClass =
156 TRI->getLargestSuperClass(MRI->getRegClass(Reg));
157
158 LaneBitmask NeedDef = Info.UsedLanes & ~Info.DefinedLanes;
159
160 LLVM_DEBUG({
161 dbgs() << "Instruction has undef subregister.\n";
162 dbgs() << printReg(Reg, nullptr)
163 << " Used: " << PrintLaneMask(Info.UsedLanes)
164 << " Def: " << PrintLaneMask(Info.DefinedLanes)
165 << " Need Def: " << PrintLaneMask(NeedDef) << "\n";
166 });
167
168 SmallVector<unsigned> SubRegIndexNeedInsert;
169 TRI->getCoveringSubRegIndexes(*MRI, TargetRegClass, NeedDef,
170 SubRegIndexNeedInsert);
171
172 Register LatestReg = Reg;
173 for (auto ind : SubRegIndexNeedInsert) {
174 Changed = true;
175 const TargetRegisterClass *SubRegClass = TRI->getLargestSuperClass(
176 TRI->getSubRegisterClass(TargetRegClass, ind));
177 Register TmpInitSubReg = MRI->createVirtualRegister(SubRegClass);
178 LLVM_DEBUG(dbgs() << "Register Class ID" << SubRegClass->getID() << "\n");
179 BuildMI(*MI.getParent(), &MI, MI.getDebugLoc(),
180 TII->get(TII->getUndefInitOpcode(SubRegClass->getID())),
181 TmpInitSubReg);
182 Register NewReg = MRI->createVirtualRegister(TargetRegClass);
183 BuildMI(*MI.getParent(), &MI, MI.getDebugLoc(),
184 TII->get(TargetOpcode::INSERT_SUBREG), NewReg)
185 .addReg(LatestReg)
186 .addReg(TmpInitSubReg)
187 .addImm(ind);
188 LatestReg = NewReg;
189 }
190
191 UseMO.setReg(LatestReg);
192 }
193
194 return Changed;
195 }
196
fixupIllOperand(MachineInstr * MI,MachineOperand & MO)197 bool InitUndef::fixupIllOperand(MachineInstr *MI, MachineOperand &MO) {
198
199 LLVM_DEBUG(
200 dbgs() << "Emitting PseudoInitUndef Instruction for implicit register "
201 << MO.getReg() << '\n');
202
203 const TargetRegisterClass *TargetRegClass =
204 TRI->getLargestSuperClass(MRI->getRegClass(MO.getReg()));
205 LLVM_DEBUG(dbgs() << "Register Class ID" << TargetRegClass->getID() << "\n");
206 unsigned Opcode = TII->getUndefInitOpcode(TargetRegClass->getID());
207 Register NewReg = MRI->createVirtualRegister(TargetRegClass);
208 BuildMI(*MI->getParent(), MI, MI->getDebugLoc(), TII->get(Opcode), NewReg);
209 MO.setReg(NewReg);
210 if (MO.isUndef())
211 MO.setIsUndef(false);
212 return true;
213 }
214
processBasicBlock(MachineFunction & MF,MachineBasicBlock & MBB,const DeadLaneDetector & DLD)215 bool InitUndef::processBasicBlock(MachineFunction &MF, MachineBasicBlock &MBB,
216 const DeadLaneDetector &DLD) {
217 bool Changed = false;
218 for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I) {
219 MachineInstr &MI = *I;
220
221 // If we used NoReg to represent the passthru, switch this back to being
222 // an IMPLICIT_DEF before TwoAddressInstructions.
223 unsigned UseOpIdx;
224 if (MI.getNumDefs() != 0 && MI.isRegTiedToUseOperand(0, &UseOpIdx)) {
225 MachineOperand &UseMO = MI.getOperand(UseOpIdx);
226 if (UseMO.getReg() == MCRegister::NoRegister) {
227 const TargetRegisterClass *RC =
228 TII->getRegClass(MI.getDesc(), UseOpIdx, TRI, MF);
229 Register NewDest = MRI->createVirtualRegister(RC);
230 // We don't have a way to update dead lanes, so keep track of the
231 // new register so that we avoid querying it later.
232 NewRegs.insert(NewDest);
233 BuildMI(MBB, I, I->getDebugLoc(), TII->get(TargetOpcode::IMPLICIT_DEF),
234 NewDest);
235 UseMO.setReg(NewDest);
236 Changed = true;
237 }
238 }
239
240 if (isEarlyClobberMI(MI)) {
241 if (MRI->subRegLivenessEnabled())
242 Changed |= handleSubReg(MF, MI, DLD);
243 Changed |= handleReg(&MI);
244 }
245 }
246 return Changed;
247 }
248
runOnMachineFunction(MachineFunction & MF)249 bool InitUndef::runOnMachineFunction(MachineFunction &MF) {
250 ST = &MF.getSubtarget();
251
252 // supportsInitUndef is implemented to reflect if an architecture has support
253 // for the InitUndef pass. Support comes from having the relevant Pseudo
254 // instructions that can be used to initialize the register. The function
255 // returns false by default so requires an implementation per architecture.
256 // Support can be added by overriding the function in a way that best fits
257 // the architecture.
258 if (!ST->supportsInitUndef())
259 return false;
260
261 MRI = &MF.getRegInfo();
262 TII = ST->getInstrInfo();
263 TRI = MRI->getTargetRegisterInfo();
264
265 bool Changed = false;
266 DeadLaneDetector DLD(MRI, TRI);
267 DLD.computeSubRegisterLaneBitInfo();
268
269 for (MachineBasicBlock &BB : MF)
270 Changed |= processBasicBlock(MF, BB, DLD);
271
272 for (auto *DeadMI : DeadInsts)
273 DeadMI->eraseFromParent();
274 DeadInsts.clear();
275 NewRegs.clear();
276
277 return Changed;
278 }
279