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/CodeGen/InitUndef.h"
42 #include "llvm/ADT/SmallSet.h"
43 #include "llvm/ADT/SmallVector.h"
44 #include "llvm/CodeGen/DetectDeadLanes.h"
45 #include "llvm/CodeGen/MachineFunction.h"
46 #include "llvm/CodeGen/MachineFunctionPass.h"
47 #include "llvm/CodeGen/MachineRegisterInfo.h"
48 #include "llvm/CodeGen/TargetInstrInfo.h"
49 #include "llvm/CodeGen/TargetRegisterInfo.h"
50 #include "llvm/CodeGen/TargetSubtargetInfo.h"
51 #include "llvm/InitializePasses.h"
52 #include "llvm/MC/MCRegister.h"
53 #include "llvm/Pass.h"
54 #include "llvm/Support/Debug.h"
55
56 using namespace llvm;
57
58 #define DEBUG_TYPE "init-undef"
59 #define INIT_UNDEF_NAME "Init Undef Pass"
60
61 namespace {
62
63 class InitUndefLegacy : public MachineFunctionPass {
64 public:
65 static char ID;
66
InitUndefLegacy()67 InitUndefLegacy() : MachineFunctionPass(ID) {}
68
69 bool runOnMachineFunction(MachineFunction &MF) override;
70
getAnalysisUsage(AnalysisUsage & AU) const71 void getAnalysisUsage(AnalysisUsage &AU) const override {
72 AU.setPreservesCFG();
73 MachineFunctionPass::getAnalysisUsage(AU);
74 }
75
getPassName() const76 StringRef getPassName() const override { return INIT_UNDEF_NAME; }
77 };
78
79 class InitUndef {
80 const TargetInstrInfo *TII;
81 MachineRegisterInfo *MRI;
82 const TargetSubtargetInfo *ST;
83 const TargetRegisterInfo *TRI;
84
85 // Newly added vregs, assumed to be fully rewritten
86 SmallSet<Register, 8> NewRegs;
87 SmallVector<MachineInstr *, 8> DeadInsts;
88
89 public:
90 bool run(MachineFunction &MF);
91
92 private:
93 bool processBasicBlock(MachineFunction &MF, MachineBasicBlock &MBB,
94 const DeadLaneDetector *DLD);
95 bool handleSubReg(MachineFunction &MF, MachineInstr &MI,
96 const DeadLaneDetector &DLD);
97 bool fixupIllOperand(MachineInstr *MI, MachineOperand &MO);
98 bool handleReg(MachineInstr *MI);
99 };
100
101 } // end anonymous namespace
102
103 char InitUndefLegacy::ID = 0;
104 INITIALIZE_PASS(InitUndefLegacy, DEBUG_TYPE, INIT_UNDEF_NAME, false, false)
105 char &llvm::InitUndefID = InitUndefLegacy::ID;
106
isEarlyClobberMI(MachineInstr & MI)107 static bool isEarlyClobberMI(MachineInstr &MI) {
108 return llvm::any_of(MI.all_defs(), [](const MachineOperand &DefMO) {
109 return DefMO.isReg() && DefMO.isEarlyClobber();
110 });
111 }
112
findImplictDefMIFromReg(Register Reg,MachineRegisterInfo * MRI)113 static bool findImplictDefMIFromReg(Register Reg, MachineRegisterInfo *MRI) {
114 for (auto &DefMI : MRI->def_instructions(Reg)) {
115 if (DefMI.getOpcode() == TargetOpcode::IMPLICIT_DEF)
116 return true;
117 }
118 return false;
119 }
120
handleReg(MachineInstr * MI)121 bool InitUndef::handleReg(MachineInstr *MI) {
122 bool Changed = false;
123 for (auto &UseMO : MI->uses()) {
124 if (!UseMO.isReg())
125 continue;
126 if (UseMO.isTied())
127 continue;
128 if (!UseMO.getReg().isVirtual())
129 continue;
130
131 if (UseMO.isUndef() || findImplictDefMIFromReg(UseMO.getReg(), MRI))
132 Changed |= fixupIllOperand(MI, UseMO);
133 }
134 return Changed;
135 }
136
handleSubReg(MachineFunction & MF,MachineInstr & MI,const DeadLaneDetector & DLD)137 bool InitUndef::handleSubReg(MachineFunction &MF, MachineInstr &MI,
138 const DeadLaneDetector &DLD) {
139 bool Changed = false;
140
141 for (MachineOperand &UseMO : MI.uses()) {
142 if (!UseMO.isReg())
143 continue;
144 if (!UseMO.getReg().isVirtual())
145 continue;
146 if (UseMO.isTied())
147 continue;
148
149 Register Reg = UseMO.getReg();
150 if (NewRegs.count(Reg))
151 continue;
152 DeadLaneDetector::VRegInfo Info = DLD.getVRegInfo(Reg.virtRegIndex());
153
154 if (Info.UsedLanes == Info.DefinedLanes)
155 continue;
156
157 const TargetRegisterClass *TargetRegClass = MRI->getRegClass(Reg);
158
159 LaneBitmask NeedDef = Info.UsedLanes & ~Info.DefinedLanes;
160
161 LLVM_DEBUG({
162 dbgs() << "Instruction has undef subregister.\n";
163 dbgs() << printReg(Reg, nullptr)
164 << " Used: " << PrintLaneMask(Info.UsedLanes)
165 << " Def: " << PrintLaneMask(Info.DefinedLanes)
166 << " Need Def: " << PrintLaneMask(NeedDef) << "\n";
167 });
168
169 SmallVector<unsigned> SubRegIndexNeedInsert;
170 TRI->getCoveringSubRegIndexes(TargetRegClass, NeedDef,
171 SubRegIndexNeedInsert);
172
173 // It's not possible to create the INIT_UNDEF when there is no register
174 // class associated for the subreg. This may happen for artificial subregs
175 // that are not directly addressable.
176 if (any_of(SubRegIndexNeedInsert, [&](unsigned Ind) -> bool {
177 return !TRI->getSubRegisterClass(TargetRegClass, Ind);
178 }))
179 continue;
180
181 Register LatestReg = Reg;
182 for (auto ind : SubRegIndexNeedInsert) {
183 Changed = true;
184 const TargetRegisterClass *SubRegClass =
185 TRI->getSubRegisterClass(TargetRegClass, ind);
186 Register TmpInitSubReg = MRI->createVirtualRegister(SubRegClass);
187 LLVM_DEBUG(dbgs() << "Register Class ID" << SubRegClass->getID() << "\n");
188 BuildMI(*MI.getParent(), &MI, MI.getDebugLoc(),
189 TII->get(TargetOpcode::INIT_UNDEF), TmpInitSubReg);
190 Register NewReg = MRI->createVirtualRegister(TargetRegClass);
191 BuildMI(*MI.getParent(), &MI, MI.getDebugLoc(),
192 TII->get(TargetOpcode::INSERT_SUBREG), NewReg)
193 .addReg(LatestReg)
194 .addReg(TmpInitSubReg)
195 .addImm(ind);
196 LatestReg = NewReg;
197 }
198
199 UseMO.setReg(LatestReg);
200 }
201
202 return Changed;
203 }
204
fixupIllOperand(MachineInstr * MI,MachineOperand & MO)205 bool InitUndef::fixupIllOperand(MachineInstr *MI, MachineOperand &MO) {
206
207 LLVM_DEBUG(
208 dbgs() << "Emitting PseudoInitUndef Instruction for implicit register "
209 << printReg(MO.getReg()) << '\n');
210
211 const TargetRegisterClass *TargetRegClass = MRI->getRegClass(MO.getReg());
212 LLVM_DEBUG(dbgs() << "Register Class ID" << TargetRegClass->getID() << "\n");
213 Register NewReg = MRI->createVirtualRegister(TargetRegClass);
214 BuildMI(*MI->getParent(), MI, MI->getDebugLoc(),
215 TII->get(TargetOpcode::INIT_UNDEF), NewReg);
216 MO.setReg(NewReg);
217 if (MO.isUndef())
218 MO.setIsUndef(false);
219 return true;
220 }
221
processBasicBlock(MachineFunction & MF,MachineBasicBlock & MBB,const DeadLaneDetector * DLD)222 bool InitUndef::processBasicBlock(MachineFunction &MF, MachineBasicBlock &MBB,
223 const DeadLaneDetector *DLD) {
224 bool Changed = false;
225 for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I) {
226 MachineInstr &MI = *I;
227
228 // If we used NoReg to represent the passthru, switch this back to being
229 // an IMPLICIT_DEF before TwoAddressInstructions.
230 unsigned UseOpIdx;
231 if (MI.getNumDefs() != 0 && MI.isRegTiedToUseOperand(0, &UseOpIdx)) {
232 MachineOperand &UseMO = MI.getOperand(UseOpIdx);
233 if (UseMO.getReg() == MCRegister::NoRegister) {
234 const TargetRegisterClass *RC =
235 TII->getRegClass(MI.getDesc(), UseOpIdx, TRI, MF);
236 Register NewDest = MRI->createVirtualRegister(RC);
237 // We don't have a way to update dead lanes, so keep track of the
238 // new register so that we avoid querying it later.
239 NewRegs.insert(NewDest);
240 BuildMI(MBB, I, I->getDebugLoc(), TII->get(TargetOpcode::IMPLICIT_DEF),
241 NewDest);
242 UseMO.setReg(NewDest);
243 Changed = true;
244 }
245 }
246
247 if (isEarlyClobberMI(MI)) {
248 if (MRI->subRegLivenessEnabled())
249 Changed |= handleSubReg(MF, MI, *DLD);
250 Changed |= handleReg(&MI);
251 }
252 }
253 return Changed;
254 }
255
runOnMachineFunction(MachineFunction & MF)256 bool InitUndefLegacy::runOnMachineFunction(MachineFunction &MF) {
257 return InitUndef().run(MF);
258 }
259
run(MachineFunction & MF,MachineFunctionAnalysisManager & MFAM)260 PreservedAnalyses InitUndefPass::run(MachineFunction &MF,
261 MachineFunctionAnalysisManager &MFAM) {
262 if (!InitUndef().run(MF))
263 return PreservedAnalyses::all();
264 auto PA = getMachineFunctionPassPreservedAnalyses();
265 PA.preserveSet<CFGAnalyses>();
266 return PA;
267 }
268
run(MachineFunction & MF)269 bool InitUndef::run(MachineFunction &MF) {
270 ST = &MF.getSubtarget();
271
272 // The pass is only needed if early-clobber defs and undef ops cannot be
273 // allocated to the same register.
274 if (!ST->requiresDisjointEarlyClobberAndUndef())
275 return false;
276
277 MRI = &MF.getRegInfo();
278 TII = ST->getInstrInfo();
279 TRI = MRI->getTargetRegisterInfo();
280
281 bool Changed = false;
282 std::unique_ptr<DeadLaneDetector> DLD;
283 if (MRI->subRegLivenessEnabled()) {
284 DLD = std::make_unique<DeadLaneDetector>(MRI, TRI);
285 DLD->computeSubRegisterLaneBitInfo();
286 }
287
288 for (MachineBasicBlock &BB : MF)
289 Changed |= processBasicBlock(MF, BB, DLD.get());
290
291 for (auto *DeadMI : DeadInsts)
292 DeadMI->eraseFromParent();
293 DeadInsts.clear();
294 NewRegs.clear();
295
296 return Changed;
297 }
298