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.all_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
124 if (UseMO.isUndef() || findImplictDefMIFromReg(Reg: UseMO.getReg(), MRI))
125 Changed |= fixupIllOperand(MI, MO&: UseMO);
126 }
127 return Changed;
128}
129
130bool InitUndef::handleSubReg(MachineFunction &MF, MachineInstr &MI,
131 const DeadLaneDetector &DLD) {
132 bool Changed = false;
133
134 for (MachineOperand &UseMO : MI.uses()) {
135 if (!UseMO.isReg())
136 continue;
137 if (!UseMO.getReg().isVirtual())
138 continue;
139 if (UseMO.isTied())
140 continue;
141
142 Register Reg = UseMO.getReg();
143 if (NewRegs.count(V: Reg))
144 continue;
145 DeadLaneDetector::VRegInfo Info = DLD.getVRegInfo(RegIdx: Reg.virtRegIndex());
146
147 if (Info.UsedLanes == Info.DefinedLanes)
148 continue;
149
150 const TargetRegisterClass *TargetRegClass = MRI->getRegClass(Reg);
151
152 LaneBitmask NeedDef = Info.UsedLanes & ~Info.DefinedLanes;
153
154 LLVM_DEBUG({
155 dbgs() << "Instruction has undef subregister.\n";
156 dbgs() << printReg(Reg, nullptr)
157 << " Used: " << PrintLaneMask(Info.UsedLanes)
158 << " Def: " << PrintLaneMask(Info.DefinedLanes)
159 << " Need Def: " << PrintLaneMask(NeedDef) << "\n";
160 });
161
162 SmallVector<unsigned> SubRegIndexNeedInsert;
163 TRI->getCoveringSubRegIndexes(RC: TargetRegClass, LaneMask: NeedDef,
164 Indexes&: SubRegIndexNeedInsert);
165
166 // It's not possible to create the INIT_UNDEF when there is no register
167 // class associated for the subreg. This may happen for artificial subregs
168 // that are not directly addressable.
169 if (any_of(Range&: SubRegIndexNeedInsert, P: [&](unsigned Ind) -> bool {
170 return !TRI->getSubRegisterClass(SuperRC: TargetRegClass, SubRegIdx: Ind);
171 }))
172 continue;
173
174 Register LatestReg = Reg;
175 for (auto ind : SubRegIndexNeedInsert) {
176 Changed = true;
177 const TargetRegisterClass *SubRegClass =
178 TRI->getSubRegisterClass(SuperRC: TargetRegClass, SubRegIdx: ind);
179 Register TmpInitSubReg = MRI->createVirtualRegister(RegClass: SubRegClass);
180 LLVM_DEBUG(dbgs() << "Register Class ID" << SubRegClass->getID() << "\n");
181 BuildMI(BB&: *MI.getParent(), I: &MI, MIMD: MI.getDebugLoc(),
182 MCID: TII->get(Opcode: TargetOpcode::INIT_UNDEF), DestReg: TmpInitSubReg);
183 Register NewReg = MRI->createVirtualRegister(RegClass: TargetRegClass);
184 BuildMI(BB&: *MI.getParent(), I: &MI, MIMD: MI.getDebugLoc(),
185 MCID: TII->get(Opcode: TargetOpcode::INSERT_SUBREG), DestReg: NewReg)
186 .addReg(RegNo: LatestReg)
187 .addReg(RegNo: TmpInitSubReg)
188 .addImm(Val: ind);
189 LatestReg = NewReg;
190 }
191
192 UseMO.setReg(LatestReg);
193 }
194
195 return Changed;
196}
197
198bool InitUndef::fixupIllOperand(MachineInstr *MI, MachineOperand &MO) {
199
200 LLVM_DEBUG(
201 dbgs() << "Emitting PseudoInitUndef Instruction for implicit register "
202 << printReg(MO.getReg()) << '\n');
203
204 const TargetRegisterClass *TargetRegClass = MRI->getRegClass(Reg: MO.getReg());
205 LLVM_DEBUG(dbgs() << "Register Class ID" << TargetRegClass->getID() << "\n");
206 Register NewReg = MRI->createVirtualRegister(RegClass: TargetRegClass);
207 BuildMI(BB&: *MI->getParent(), I: MI, MIMD: MI->getDebugLoc(),
208 MCID: TII->get(Opcode: TargetOpcode::INIT_UNDEF), 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: *DLD);
243 Changed |= handleReg(MI: &MI);
244 }
245 }
246 return Changed;
247}
248
249bool InitUndef::runOnMachineFunction(MachineFunction &MF) {
250 ST = &MF.getSubtarget();
251
252 // The pass is only needed if early-clobber defs and undef ops cannot be
253 // allocated to the same register.
254 if (!ST->requiresDisjointEarlyClobberAndUndef())
255 return false;
256
257 MRI = &MF.getRegInfo();
258 TII = ST->getInstrInfo();
259 TRI = MRI->getTargetRegisterInfo();
260
261 bool Changed = false;
262 std::unique_ptr<DeadLaneDetector> DLD;
263 if (MRI->subRegLivenessEnabled()) {
264 DLD = std::make_unique<DeadLaneDetector>(args&: MRI, args&: TRI);
265 DLD->computeSubRegisterLaneBitInfo();
266 }
267
268 for (MachineBasicBlock &BB : MF)
269 Changed |= processBasicBlock(MF, MBB&: BB, DLD: DLD.get());
270
271 for (auto *DeadMI : DeadInsts)
272 DeadMI->eraseFromParent();
273 DeadInsts.clear();
274 NewRegs.clear();
275
276 return Changed;
277}
278