1//===-- lib/CodeGen/MachineInstrBundle.cpp --------------------------------===//
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#include "llvm/CodeGen/MachineInstrBundle.h"
10#include "llvm/ADT/SmallSet.h"
11#include "llvm/ADT/SmallVector.h"
12#include "llvm/CodeGen/MachineFunctionPass.h"
13#include "llvm/CodeGen/MachineInstrBuilder.h"
14#include "llvm/CodeGen/Passes.h"
15#include "llvm/CodeGen/TargetInstrInfo.h"
16#include "llvm/CodeGen/TargetRegisterInfo.h"
17#include "llvm/CodeGen/TargetSubtargetInfo.h"
18#include "llvm/InitializePasses.h"
19#include "llvm/Pass.h"
20#include "llvm/PassRegistry.h"
21#include <utility>
22using namespace llvm;
23
24namespace {
25 class UnpackMachineBundles : public MachineFunctionPass {
26 public:
27 static char ID; // Pass identification
28 UnpackMachineBundles(
29 std::function<bool(const MachineFunction &)> Ftor = nullptr)
30 : MachineFunctionPass(ID), PredicateFtor(std::move(Ftor)) {
31 initializeUnpackMachineBundlesPass(*PassRegistry::getPassRegistry());
32 }
33
34 bool runOnMachineFunction(MachineFunction &MF) override;
35
36 private:
37 std::function<bool(const MachineFunction &)> PredicateFtor;
38 };
39} // end anonymous namespace
40
41char UnpackMachineBundles::ID = 0;
42char &llvm::UnpackMachineBundlesID = UnpackMachineBundles::ID;
43INITIALIZE_PASS(UnpackMachineBundles, "unpack-mi-bundles",
44 "Unpack machine instruction bundles", false, false)
45
46bool UnpackMachineBundles::runOnMachineFunction(MachineFunction &MF) {
47 if (PredicateFtor && !PredicateFtor(MF))
48 return false;
49
50 bool Changed = false;
51 for (MachineBasicBlock &MBB : MF) {
52 for (MachineBasicBlock::instr_iterator MII = MBB.instr_begin(),
53 MIE = MBB.instr_end(); MII != MIE; ) {
54 MachineInstr *MI = &*MII;
55
56 // Remove BUNDLE instruction and the InsideBundle flags from bundled
57 // instructions.
58 if (MI->isBundle()) {
59 while (++MII != MIE && MII->isBundledWithPred()) {
60 MII->unbundleFromPred();
61 for (MachineOperand &MO : MII->operands()) {
62 if (MO.isReg() && MO.isInternalRead())
63 MO.setIsInternalRead(false);
64 }
65 }
66 MI->eraseFromParent();
67
68 Changed = true;
69 continue;
70 }
71
72 ++MII;
73 }
74 }
75
76 return Changed;
77}
78
79FunctionPass *
80llvm::createUnpackMachineBundles(
81 std::function<bool(const MachineFunction &)> Ftor) {
82 return new UnpackMachineBundles(std::move(Ftor));
83}
84
85namespace {
86 class FinalizeMachineBundles : public MachineFunctionPass {
87 public:
88 static char ID; // Pass identification
89 FinalizeMachineBundles() : MachineFunctionPass(ID) {
90 initializeFinalizeMachineBundlesPass(*PassRegistry::getPassRegistry());
91 }
92
93 bool runOnMachineFunction(MachineFunction &MF) override;
94 };
95} // end anonymous namespace
96
97char FinalizeMachineBundles::ID = 0;
98char &llvm::FinalizeMachineBundlesID = FinalizeMachineBundles::ID;
99INITIALIZE_PASS(FinalizeMachineBundles, "finalize-mi-bundles",
100 "Finalize machine instruction bundles", false, false)
101
102bool FinalizeMachineBundles::runOnMachineFunction(MachineFunction &MF) {
103 return llvm::finalizeBundles(MF);
104}
105
106/// Return the first found DebugLoc that has a DILocation, given a range of
107/// instructions. The search range is from FirstMI to LastMI (exclusive). If no
108/// DILocation is found, then an empty location is returned.
109static DebugLoc getDebugLoc(MachineBasicBlock::instr_iterator FirstMI,
110 MachineBasicBlock::instr_iterator LastMI) {
111 for (auto MII = FirstMI; MII != LastMI; ++MII)
112 if (MII->getDebugLoc())
113 return MII->getDebugLoc();
114 return DebugLoc();
115}
116
117/// finalizeBundle - Finalize a machine instruction bundle which includes
118/// a sequence of instructions starting from FirstMI to LastMI (exclusive).
119/// This routine adds a BUNDLE instruction to represent the bundle, it adds
120/// IsInternalRead markers to MachineOperands which are defined inside the
121/// bundle, and it copies externally visible defs and uses to the BUNDLE
122/// instruction.
123void llvm::finalizeBundle(MachineBasicBlock &MBB,
124 MachineBasicBlock::instr_iterator FirstMI,
125 MachineBasicBlock::instr_iterator LastMI) {
126 assert(FirstMI != LastMI && "Empty bundle?");
127 MIBundleBuilder Bundle(MBB, FirstMI, LastMI);
128
129 MachineFunction &MF = *MBB.getParent();
130 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
131 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
132
133 MachineInstrBuilder MIB =
134 BuildMI(MF, MIMD: getDebugLoc(FirstMI, LastMI), MCID: TII->get(Opcode: TargetOpcode::BUNDLE));
135 Bundle.prepend(MI: MIB);
136
137 SmallVector<Register, 32> LocalDefs;
138 SmallSet<Register, 32> LocalDefSet;
139 SmallSet<Register, 8> DeadDefSet;
140 SmallSet<Register, 16> KilledDefSet;
141 SmallVector<Register, 8> ExternUses;
142 SmallSet<Register, 8> ExternUseSet;
143 SmallSet<Register, 8> KilledUseSet;
144 SmallSet<Register, 8> UndefUseSet;
145 SmallVector<MachineOperand*, 4> Defs;
146 for (auto MII = FirstMI; MII != LastMI; ++MII) {
147 // Debug instructions have no effects to track.
148 if (MII->isDebugInstr())
149 continue;
150
151 for (MachineOperand &MO : MII->operands()) {
152 if (!MO.isReg())
153 continue;
154 if (MO.isDef()) {
155 Defs.push_back(Elt: &MO);
156 continue;
157 }
158
159 Register Reg = MO.getReg();
160 if (!Reg)
161 continue;
162
163 if (LocalDefSet.count(V: Reg)) {
164 MO.setIsInternalRead();
165 if (MO.isKill())
166 // Internal def is now killed.
167 KilledDefSet.insert(V: Reg);
168 } else {
169 if (ExternUseSet.insert(V: Reg).second) {
170 ExternUses.push_back(Elt: Reg);
171 if (MO.isUndef())
172 UndefUseSet.insert(V: Reg);
173 }
174 if (MO.isKill())
175 // External def is now killed.
176 KilledUseSet.insert(V: Reg);
177 }
178 }
179
180 for (MachineOperand *MO : Defs) {
181 Register Reg = MO->getReg();
182 if (!Reg)
183 continue;
184
185 if (LocalDefSet.insert(V: Reg).second) {
186 LocalDefs.push_back(Elt: Reg);
187 if (MO->isDead()) {
188 DeadDefSet.insert(V: Reg);
189 }
190 } else {
191 // Re-defined inside the bundle, it's no longer killed.
192 KilledDefSet.erase(V: Reg);
193 if (!MO->isDead())
194 // Previously defined but dead.
195 DeadDefSet.erase(V: Reg);
196 }
197
198 if (!MO->isDead() && Reg.isPhysical()) {
199 for (MCPhysReg SubReg : TRI->subregs(Reg)) {
200 if (LocalDefSet.insert(V: SubReg).second)
201 LocalDefs.push_back(Elt: SubReg);
202 }
203 }
204 }
205
206 Defs.clear();
207 }
208
209 SmallSet<Register, 32> Added;
210 for (Register Reg : LocalDefs) {
211 if (Added.insert(V: Reg).second) {
212 // If it's not live beyond end of the bundle, mark it dead.
213 bool isDead = DeadDefSet.count(V: Reg) || KilledDefSet.count(V: Reg);
214 MIB.addReg(RegNo: Reg, flags: getDefRegState(B: true) | getDeadRegState(B: isDead) |
215 getImplRegState(B: true));
216 }
217 }
218
219 for (Register Reg : ExternUses) {
220 bool isKill = KilledUseSet.count(V: Reg);
221 bool isUndef = UndefUseSet.count(V: Reg);
222 MIB.addReg(RegNo: Reg, flags: getKillRegState(B: isKill) | getUndefRegState(B: isUndef) |
223 getImplRegState(B: true));
224 }
225
226 // Set FrameSetup/FrameDestroy for the bundle. If any of the instructions got
227 // the property, then also set it on the bundle.
228 for (auto MII = FirstMI; MII != LastMI; ++MII) {
229 if (MII->getFlag(Flag: MachineInstr::FrameSetup))
230 MIB.setMIFlag(MachineInstr::FrameSetup);
231 if (MII->getFlag(Flag: MachineInstr::FrameDestroy))
232 MIB.setMIFlag(MachineInstr::FrameDestroy);
233 }
234}
235
236/// finalizeBundle - Same functionality as the previous finalizeBundle except
237/// the last instruction in the bundle is not provided as an input. This is
238/// used in cases where bundles are pre-determined by marking instructions
239/// with 'InsideBundle' marker. It returns the MBB instruction iterator that
240/// points to the end of the bundle.
241MachineBasicBlock::instr_iterator
242llvm::finalizeBundle(MachineBasicBlock &MBB,
243 MachineBasicBlock::instr_iterator FirstMI) {
244 MachineBasicBlock::instr_iterator E = MBB.instr_end();
245 MachineBasicBlock::instr_iterator LastMI = std::next(x: FirstMI);
246 while (LastMI != E && LastMI->isInsideBundle())
247 ++LastMI;
248 finalizeBundle(MBB, FirstMI, LastMI);
249 return LastMI;
250}
251
252/// finalizeBundles - Finalize instruction bundles in the specified
253/// MachineFunction. Return true if any bundles are finalized.
254bool llvm::finalizeBundles(MachineFunction &MF) {
255 bool Changed = false;
256 for (MachineBasicBlock &MBB : MF) {
257 MachineBasicBlock::instr_iterator MII = MBB.instr_begin();
258 MachineBasicBlock::instr_iterator MIE = MBB.instr_end();
259 if (MII == MIE)
260 continue;
261 assert(!MII->isInsideBundle() &&
262 "First instr cannot be inside bundle before finalization!");
263
264 for (++MII; MII != MIE; ) {
265 if (!MII->isInsideBundle())
266 ++MII;
267 else {
268 MII = finalizeBundle(MBB, FirstMI: std::prev(x: MII));
269 Changed = true;
270 }
271 }
272 }
273
274 return Changed;
275}
276
277VirtRegInfo llvm::AnalyzeVirtRegInBundle(
278 MachineInstr &MI, Register Reg,
279 SmallVectorImpl<std::pair<MachineInstr *, unsigned>> *Ops) {
280 VirtRegInfo RI = {.Reads: false, .Writes: false, .Tied: false};
281 for (MIBundleOperands O(MI); O.isValid(); ++O) {
282 MachineOperand &MO = *O;
283 if (!MO.isReg() || MO.getReg() != Reg)
284 continue;
285
286 // Remember each (MI, OpNo) that refers to Reg.
287 if (Ops)
288 Ops->push_back(Elt: std::make_pair(x: MO.getParent(), y: O.getOperandNo()));
289
290 // Both defs and uses can read virtual registers.
291 if (MO.readsReg()) {
292 RI.Reads = true;
293 if (MO.isDef())
294 RI.Tied = true;
295 }
296
297 // Only defs can write.
298 if (MO.isDef())
299 RI.Writes = true;
300 else if (!RI.Tied &&
301 MO.getParent()->isRegTiedToDefOperand(UseOpIdx: O.getOperandNo()))
302 RI.Tied = true;
303 }
304 return RI;
305}
306
307std::pair<LaneBitmask, LaneBitmask>
308llvm::AnalyzeVirtRegLanesInBundle(const MachineInstr &MI, Register Reg,
309 const MachineRegisterInfo &MRI,
310 const TargetRegisterInfo &TRI) {
311
312 LaneBitmask UseMask, DefMask;
313
314 for (const MachineOperand &MO : const_mi_bundle_ops(MI)) {
315 if (!MO.isReg() || MO.getReg() != Reg)
316 continue;
317
318 unsigned SubReg = MO.getSubReg();
319 if (SubReg == 0 && MO.isUse() && !MO.isUndef())
320 UseMask |= MRI.getMaxLaneMaskForVReg(Reg);
321
322 LaneBitmask SubRegMask = TRI.getSubRegIndexLaneMask(SubIdx: SubReg);
323 if (MO.isDef()) {
324 if (!MO.isUndef())
325 UseMask |= ~SubRegMask;
326 DefMask |= SubRegMask;
327 } else if (!MO.isUndef())
328 UseMask |= SubRegMask;
329 }
330
331 return {UseMask, DefMask};
332}
333
334PhysRegInfo llvm::AnalyzePhysRegInBundle(const MachineInstr &MI, Register Reg,
335 const TargetRegisterInfo *TRI) {
336 bool AllDefsDead = true;
337 PhysRegInfo PRI = {.Clobbered: false, .Defined: false, .FullyDefined: false, .Read: false, .FullyRead: false, .DeadDef: false, .PartialDeadDef: false, .Killed: false};
338
339 assert(Reg.isPhysical() && "analyzePhysReg not given a physical register!");
340 for (const MachineOperand &MO : const_mi_bundle_ops(MI)) {
341 if (MO.isRegMask() && MO.clobbersPhysReg(PhysReg: Reg)) {
342 PRI.Clobbered = true;
343 continue;
344 }
345
346 if (!MO.isReg())
347 continue;
348
349 Register MOReg = MO.getReg();
350 if (!MOReg || !MOReg.isPhysical())
351 continue;
352
353 if (!TRI->regsOverlap(RegA: MOReg, RegB: Reg))
354 continue;
355
356 bool Covered = TRI->isSuperRegisterEq(RegA: Reg, RegB: MOReg);
357 if (MO.readsReg()) {
358 PRI.Read = true;
359 if (Covered) {
360 PRI.FullyRead = true;
361 if (MO.isKill())
362 PRI.Killed = true;
363 }
364 } else if (MO.isDef()) {
365 PRI.Defined = true;
366 if (Covered)
367 PRI.FullyDefined = true;
368 if (!MO.isDead())
369 AllDefsDead = false;
370 }
371 }
372
373 if (AllDefsDead) {
374 if (PRI.FullyDefined || PRI.Clobbered)
375 PRI.DeadDef = true;
376 else if (PRI.Defined)
377 PRI.PartialDeadDef = true;
378 }
379
380 return PRI;
381}
382