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
55using namespace llvm;
56
57#define DEBUG_TYPE "init-undef"
58#define INIT_UNDEF_NAME "Init Undef Pass"
59
60namespace {
61
62class 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
72public:
73 static char ID;
74
75 InitUndef() : MachineFunctionPass(ID) {}
76 bool runOnMachineFunction(MachineFunction &MF) override;
77
78 void getAnalysisUsage(AnalysisUsage &AU) const override {
79 AU.setPreservesCFG();
80 MachineFunctionPass::getAnalysisUsage(AU);
81 }
82
83 StringRef getPassName() const override { return INIT_UNDEF_NAME; }
84
85private:
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
96char InitUndef::ID = 0;
97INITIALIZE_PASS(InitUndef, DEBUG_TYPE, INIT_UNDEF_NAME, false, false)
98char &llvm::InitUndefID = InitUndef::ID;
99
100static bool isEarlyClobberMI(MachineInstr &MI) {
101 return llvm::any_of(Range: MI.defs(), P: [](const MachineOperand &DefMO) {
102 return DefMO.isReg() && DefMO.isEarlyClobber();
103 });
104}
105
106static 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
114bool 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(RC: MRI->getRegClass(Reg: UseMO.getReg())))
124 continue;
125
126 if (UseMO.isUndef() || findImplictDefMIFromReg(Reg: UseMO.getReg(), MRI))
127 Changed |= fixupIllOperand(MI, MO&: UseMO);
128 }
129 return Changed;
130}
131
132bool 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(RC: MRI->getRegClass(Reg: UseMO.getReg())))
144 continue;
145
146 Register Reg = UseMO.getReg();
147 if (NewRegs.count(V: Reg))
148 continue;
149 DeadLaneDetector::VRegInfo Info =
150 DLD.getVRegInfo(RegIdx: Register::virtReg2Index(Reg));
151
152 if (Info.UsedLanes == Info.DefinedLanes)
153 continue;
154
155 const TargetRegisterClass *TargetRegClass =
156 TRI->getLargestSuperClass(RC: 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: *MRI, RC: TargetRegClass, LaneMask: NeedDef,
170 Indexes&: SubRegIndexNeedInsert);
171
172 Register LatestReg = Reg;
173 for (auto ind : SubRegIndexNeedInsert) {
174 Changed = true;
175 const TargetRegisterClass *SubRegClass = TRI->getLargestSuperClass(
176 RC: TRI->getSubRegisterClass(SuperRC: TargetRegClass, SubRegIdx: ind));
177 Register TmpInitSubReg = MRI->createVirtualRegister(RegClass: SubRegClass);
178 LLVM_DEBUG(dbgs() << "Register Class ID" << SubRegClass->getID() << "\n");
179 BuildMI(BB&: *MI.getParent(), I: &MI, MIMD: MI.getDebugLoc(),
180 MCID: TII->get(Opcode: TII->getUndefInitOpcode(RegClassID: SubRegClass->getID())),
181 DestReg: TmpInitSubReg);
182 Register NewReg = MRI->createVirtualRegister(RegClass: TargetRegClass);
183 BuildMI(BB&: *MI.getParent(), I: &MI, MIMD: MI.getDebugLoc(),
184 MCID: TII->get(Opcode: TargetOpcode::INSERT_SUBREG), DestReg: NewReg)
185 .addReg(RegNo: LatestReg)
186 .addReg(RegNo: TmpInitSubReg)
187 .addImm(Val: ind);
188 LatestReg = NewReg;
189 }
190
191 UseMO.setReg(LatestReg);
192 }
193
194 return Changed;
195}
196
197bool 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(RC: MRI->getRegClass(Reg: MO.getReg()));
205 LLVM_DEBUG(dbgs() << "Register Class ID" << TargetRegClass->getID() << "\n");
206 unsigned Opcode = TII->getUndefInitOpcode(RegClassID: TargetRegClass->getID());
207 Register NewReg = MRI->createVirtualRegister(RegClass: TargetRegClass);
208 BuildMI(BB&: *MI->getParent(), I: MI, MIMD: MI->getDebugLoc(), MCID: TII->get(Opcode), DestReg: NewReg);
209 MO.setReg(NewReg);
210 if (MO.isUndef())
211 MO.setIsUndef(false);
212 return true;
213}
214
215bool 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(DefOpIdx: 0, UseOpIdx: &UseOpIdx)) {
225 MachineOperand &UseMO = MI.getOperand(i: UseOpIdx);
226 if (UseMO.getReg() == MCRegister::NoRegister) {
227 const TargetRegisterClass *RC =
228 TII->getRegClass(MCID: MI.getDesc(), OpNum: UseOpIdx, TRI, MF);
229 Register NewDest = MRI->createVirtualRegister(RegClass: 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(V: NewDest);
233 BuildMI(BB&: MBB, I, MIMD: I->getDebugLoc(), MCID: TII->get(Opcode: TargetOpcode::IMPLICIT_DEF),
234 DestReg: 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: &MI);
244 }
245 }
246 return Changed;
247}
248
249bool 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, MBB&: BB, DLD);
271
272 for (auto *DeadMI : DeadInsts)
273 DeadMI->eraseFromParent();
274 DeadInsts.clear();
275
276 return Changed;
277}
278