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
56using namespace llvm;
57
58#define DEBUG_TYPE "init-undef"
59#define INIT_UNDEF_NAME "Init Undef Pass"
60
61namespace {
62
63class InitUndefLegacy : public MachineFunctionPass {
64public:
65 static char ID;
66
67 InitUndefLegacy() : MachineFunctionPass(ID) {}
68
69 bool runOnMachineFunction(MachineFunction &MF) override;
70
71 void getAnalysisUsage(AnalysisUsage &AU) const override {
72 AU.setPreservesCFG();
73 MachineFunctionPass::getAnalysisUsage(AU);
74 }
75
76 StringRef getPassName() const override { return INIT_UNDEF_NAME; }
77};
78
79class 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
89public:
90 bool run(MachineFunction &MF);
91
92private:
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
103char InitUndefLegacy::ID = 0;
104INITIALIZE_PASS(InitUndefLegacy, DEBUG_TYPE, INIT_UNDEF_NAME, false, false)
105char &llvm::InitUndefID = InitUndefLegacy::ID;
106
107static bool isEarlyClobberMI(MachineInstr &MI) {
108 return llvm::any_of(Range: MI.all_defs(), P: [](const MachineOperand &DefMO) {
109 return DefMO.isReg() && DefMO.isEarlyClobber();
110 });
111}
112
113static 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
121bool 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(Reg: UseMO.getReg(), MRI))
132 Changed |= fixupIllOperand(MI, MO&: UseMO);
133 }
134 return Changed;
135}
136
137bool 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(V: Reg))
151 continue;
152 DeadLaneDetector::VRegInfo Info = DLD.getVRegInfo(RegIdx: 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(RC: TargetRegClass, LaneMask: NeedDef,
171 Indexes&: 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(Range&: SubRegIndexNeedInsert, P: [&](unsigned Ind) -> bool {
177 return !TRI->getSubRegisterClass(SuperRC: TargetRegClass, SubRegIdx: Ind);
178 }))
179 continue;
180
181 Register LatestReg = Reg;
182 for (auto ind : SubRegIndexNeedInsert) {
183 Changed = true;
184 const TargetRegisterClass *SubRegClass =
185 TRI->getSubRegisterClass(SuperRC: TargetRegClass, SubRegIdx: ind);
186 Register TmpInitSubReg = MRI->createVirtualRegister(RegClass: SubRegClass);
187 LLVM_DEBUG(dbgs() << "Register Class ID" << SubRegClass->getID() << "\n");
188 BuildMI(BB&: *MI.getParent(), I: &MI, MIMD: MI.getDebugLoc(),
189 MCID: TII->get(Opcode: TargetOpcode::INIT_UNDEF), DestReg: TmpInitSubReg);
190 Register NewReg = MRI->createVirtualRegister(RegClass: TargetRegClass);
191 BuildMI(BB&: *MI.getParent(), I: &MI, MIMD: MI.getDebugLoc(),
192 MCID: TII->get(Opcode: TargetOpcode::INSERT_SUBREG), DestReg: NewReg)
193 .addReg(RegNo: LatestReg)
194 .addReg(RegNo: TmpInitSubReg)
195 .addImm(Val: ind);
196 LatestReg = NewReg;
197 }
198
199 UseMO.setReg(LatestReg);
200 }
201
202 return Changed;
203}
204
205bool 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(Reg: MO.getReg());
212 LLVM_DEBUG(dbgs() << "Register Class ID" << TargetRegClass->getID() << "\n");
213 Register NewReg = MRI->createVirtualRegister(RegClass: TargetRegClass);
214 BuildMI(BB&: *MI->getParent(), I: MI, MIMD: MI->getDebugLoc(),
215 MCID: TII->get(Opcode: TargetOpcode::INIT_UNDEF), DestReg: NewReg);
216 MO.setReg(NewReg);
217 if (MO.isUndef())
218 MO.setIsUndef(false);
219 return true;
220}
221
222bool 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(DefOpIdx: 0, UseOpIdx: &UseOpIdx)) {
232 MachineOperand &UseMO = MI.getOperand(i: UseOpIdx);
233 if (UseMO.getReg() == MCRegister::NoRegister) {
234 const TargetRegisterClass *RC =
235 TII->getRegClass(MCID: MI.getDesc(), OpNum: UseOpIdx);
236 Register NewDest = MRI->createVirtualRegister(RegClass: 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(V: NewDest);
240 BuildMI(BB&: MBB, I, MIMD: I->getDebugLoc(), MCID: TII->get(Opcode: TargetOpcode::IMPLICIT_DEF),
241 DestReg: 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: *DLD);
250 Changed |= handleReg(MI: &MI);
251 }
252 }
253 return Changed;
254}
255
256bool InitUndefLegacy::runOnMachineFunction(MachineFunction &MF) {
257 return InitUndef().run(MF);
258}
259
260PreservedAnalyses 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
269bool 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>(args&: MRI, args&: TRI);
285 DLD->computeSubRegisterLaneBitInfo();
286 }
287
288 for (MachineBasicBlock &BB : MF)
289 Changed |= processBasicBlock(MF, MBB&: BB, DLD: DLD.get());
290
291 for (auto *DeadMI : DeadInsts)
292 DeadMI->eraseFromParent();
293 DeadInsts.clear();
294 NewRegs.clear();
295
296 return Changed;
297}
298