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/SetVector.h"
11#include "llvm/ADT/SmallSet.h"
12#include "llvm/ADT/SmallVector.h"
13#include "llvm/CodeGen/MachineFunctionPass.h"
14#include "llvm/CodeGen/MachineInstrBuilder.h"
15#include "llvm/CodeGen/Passes.h"
16#include "llvm/CodeGen/TargetInstrInfo.h"
17#include "llvm/CodeGen/TargetRegisterInfo.h"
18#include "llvm/CodeGen/TargetSubtargetInfo.h"
19#include "llvm/InitializePasses.h"
20#include "llvm/Pass.h"
21#include "llvm/PassRegistry.h"
22#include <utility>
23using namespace llvm;
24
25namespace {
26 class UnpackMachineBundles : public MachineFunctionPass {
27 public:
28 static char ID; // Pass identification
29 UnpackMachineBundles(
30 std::function<bool(const MachineFunction &)> Ftor = nullptr)
31 : MachineFunctionPass(ID), PredicateFtor(std::move(Ftor)) {}
32
33 bool runOnMachineFunction(MachineFunction &MF) override;
34
35 private:
36 std::function<bool(const MachineFunction &)> PredicateFtor;
37 };
38} // end anonymous namespace
39
40char UnpackMachineBundles::ID = 0;
41char &llvm::UnpackMachineBundlesID = UnpackMachineBundles::ID;
42INITIALIZE_PASS(UnpackMachineBundles, "unpack-mi-bundles",
43 "Unpack machine instruction bundles", false, false)
44
45bool UnpackMachineBundles::runOnMachineFunction(MachineFunction &MF) {
46 if (PredicateFtor && !PredicateFtor(MF))
47 return false;
48
49 bool Changed = false;
50 for (MachineBasicBlock &MBB : MF) {
51 for (MachineBasicBlock::instr_iterator MII = MBB.instr_begin(),
52 MIE = MBB.instr_end(); MII != MIE; ) {
53 MachineInstr *MI = &*MII;
54
55 // Remove BUNDLE instruction and the InsideBundle flags from bundled
56 // instructions.
57 if (MI->isBundle()) {
58 while (++MII != MIE && MII->isBundledWithPred()) {
59 MII->unbundleFromPred();
60 for (MachineOperand &MO : MII->operands()) {
61 if (MO.isReg() && MO.isInternalRead())
62 MO.setIsInternalRead(false);
63 }
64 }
65 MI->eraseFromParent();
66
67 Changed = true;
68 continue;
69 }
70
71 ++MII;
72 }
73 }
74
75 return Changed;
76}
77
78FunctionPass *
79llvm::createUnpackMachineBundles(
80 std::function<bool(const MachineFunction &)> Ftor) {
81 return new UnpackMachineBundles(std::move(Ftor));
82}
83
84/// Return the first DebugLoc that has line number information, given a
85/// range of instructions. The search range is from FirstMI to LastMI
86/// (exclusive). Otherwise return the first DILocation or an empty location if
87/// there are none.
88static DebugLoc getDebugLoc(MachineBasicBlock::instr_iterator FirstMI,
89 MachineBasicBlock::instr_iterator LastMI) {
90 DebugLoc DL;
91 for (auto MII = FirstMI; MII != LastMI; ++MII) {
92 if (DebugLoc MIIDL = MII->getDebugLoc()) {
93 if (MIIDL.getLine() != 0)
94 return MIIDL;
95 DL = MIIDL.get();
96 }
97 }
98 return DL;
99}
100
101/// Check if target reg is contained in given lists, which are:
102/// LocalDefsV as given list for virtual regs
103/// LocalDefsP as given list for physical regs, in BitVector[RegUnit] form
104static bool containsReg(SmallSetVector<Register, 32> LocalDefsV,
105 const BitVector &LocalDefsP, Register Reg,
106 const TargetRegisterInfo *TRI) {
107 if (Reg.isPhysical()) {
108 for (MCRegUnit Unit : TRI->regunits(Reg: Reg.asMCReg()))
109 if (!LocalDefsP[static_cast<unsigned>(Unit)])
110 return false;
111
112 return true;
113 }
114 return LocalDefsV.contains(key: Reg);
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 SmallSetVector<Register, 32> LocalDefs;
138 BitVector LocalDefsP(TRI->getNumRegUnits());
139 SmallSet<Register, 8> DeadDefSet;
140 SmallSetVector<Register, 8> ExternUses;
141 SmallSet<Register, 8> KilledUseSet;
142 SmallSet<Register, 8> UndefUseSet;
143 SmallVector<std::pair<Register, Register>> TiedOperands;
144 SmallVector<MachineInstr *> MemMIs;
145 for (auto MII = FirstMI; MII != LastMI; ++MII) {
146 // Debug instructions have no effects to track.
147 if (MII->isDebugInstr())
148 continue;
149
150 for (MachineOperand &MO : MII->all_uses()) {
151 Register Reg = MO.getReg();
152 if (!Reg)
153 continue;
154
155 if (containsReg(LocalDefsV: LocalDefs, LocalDefsP, Reg, TRI)) {
156 MO.setIsInternalRead();
157 if (MO.isKill()) {
158 // Internal def is now killed.
159 DeadDefSet.insert(V: Reg);
160 }
161 } else {
162 if (ExternUses.insert(X: Reg)) {
163 if (MO.isUndef())
164 UndefUseSet.insert(V: Reg);
165 }
166 if (MO.isKill()) {
167 // External def is now killed.
168 KilledUseSet.insert(V: Reg);
169 }
170 if (MO.isTied() && Reg.isVirtual()) {
171 // Record tied operand constraints that involve virtual registers so
172 // that bundles that are formed pre-register allocation reflect the
173 // relevant constraints.
174 unsigned TiedIdx = MII->findTiedOperandIdx(OpIdx: MO.getOperandNo());
175 MachineOperand &TiedMO = MII->getOperand(i: TiedIdx);
176 Register DefReg = TiedMO.getReg();
177 TiedOperands.emplace_back(Args&: DefReg, Args&: Reg);
178 }
179 }
180 }
181
182 for (MachineOperand &MO : MII->all_defs()) {
183 Register Reg = MO.getReg();
184 if (!Reg)
185 continue;
186
187 if (LocalDefs.insert(X: Reg)) {
188 if (!MO.isDead() && Reg.isPhysical()) {
189 for (MCRegUnit Unit : TRI->regunits(Reg: Reg.asMCReg()))
190 LocalDefsP.set(static_cast<unsigned>(Unit));
191 }
192 } else {
193 if (!MO.isDead()) {
194 // Re-defined inside the bundle, it's no longer dead.
195 DeadDefSet.erase(V: Reg);
196 }
197 }
198 if (MO.isDead())
199 DeadDefSet.insert(V: Reg);
200 }
201
202 // Set FrameSetup/FrameDestroy for the bundle. If any of the instructions
203 // got the property, then also set it on the bundle.
204 if (MII->getFlag(Flag: MachineInstr::FrameSetup))
205 MIB.setMIFlag(MachineInstr::FrameSetup);
206 if (MII->getFlag(Flag: MachineInstr::FrameDestroy))
207 MIB.setMIFlag(MachineInstr::FrameDestroy);
208
209 if (MII->mayLoadOrStore())
210 MemMIs.push_back(Elt: &*MII);
211 }
212
213 for (Register Reg : LocalDefs) {
214 // If it's not live beyond end of the bundle, mark it dead.
215 bool isDead = DeadDefSet.contains(V: Reg);
216 MIB.addReg(RegNo: Reg, Flags: getDefRegState(B: true) | getDeadRegState(B: isDead) |
217 getImplRegState(B: true));
218 }
219
220 for (Register Reg : ExternUses) {
221 bool isKill = KilledUseSet.contains(V: Reg);
222 bool isUndef = UndefUseSet.contains(V: Reg);
223 MIB.addReg(RegNo: Reg, Flags: getKillRegState(B: isKill) | getUndefRegState(B: isUndef) |
224 getImplRegState(B: true));
225 }
226
227 for (auto [DefReg, UseReg] : TiedOperands) {
228 unsigned DefIdx =
229 std::distance(first: LocalDefs.begin(), last: llvm::find(Range&: LocalDefs, Val: DefReg));
230 unsigned UseIdx =
231 std::distance(first: ExternUses.begin(), last: llvm::find(Range&: ExternUses, Val: UseReg));
232 assert(DefIdx < LocalDefs.size());
233 assert(UseIdx < ExternUses.size());
234 MIB->tieOperands(DefIdx, UseIdx: LocalDefs.size() + UseIdx);
235 }
236
237 MIB->cloneMergedMemRefs(MF, MIs: MemMIs);
238}
239
240/// finalizeBundle - Same functionality as the previous finalizeBundle except
241/// the last instruction in the bundle is not provided as an input. This is
242/// used in cases where bundles are pre-determined by marking instructions
243/// with 'InsideBundle' marker. It returns the MBB instruction iterator that
244/// points to the end of the bundle.
245MachineBasicBlock::instr_iterator
246llvm::finalizeBundle(MachineBasicBlock &MBB,
247 MachineBasicBlock::instr_iterator FirstMI) {
248 MachineBasicBlock::instr_iterator E = MBB.instr_end();
249 MachineBasicBlock::instr_iterator LastMI = std::next(x: FirstMI);
250 while (LastMI != E && LastMI->isInsideBundle())
251 ++LastMI;
252 finalizeBundle(MBB, FirstMI, LastMI);
253 return LastMI;
254}
255
256/// finalizeBundles - Finalize instruction bundles in the specified
257/// MachineFunction. Return true if any bundles are finalized.
258bool llvm::finalizeBundles(MachineFunction &MF) {
259 bool Changed = false;
260 for (MachineBasicBlock &MBB : MF) {
261 MachineBasicBlock::instr_iterator MII = MBB.instr_begin();
262 MachineBasicBlock::instr_iterator MIE = MBB.instr_end();
263 if (MII == MIE)
264 continue;
265 assert(!MII->isInsideBundle() &&
266 "First instr cannot be inside bundle before finalization!");
267
268 for (++MII; MII != MIE; ) {
269 if (!MII->isInsideBundle())
270 ++MII;
271 else {
272 MII = finalizeBundle(MBB, FirstMI: std::prev(x: MII));
273 Changed = true;
274 }
275 }
276 }
277
278 return Changed;
279}
280
281VirtRegInfo llvm::AnalyzeVirtRegInBundle(
282 MachineInstr &MI, Register Reg,
283 SmallVectorImpl<std::pair<MachineInstr *, unsigned>> *Ops) {
284 VirtRegInfo RI = {.Reads: false, .Writes: false, .Tied: false};
285 for (MIBundleOperands O(MI); O.isValid(); ++O) {
286 MachineOperand &MO = *O;
287 if (!MO.isReg() || MO.getReg() != Reg)
288 continue;
289
290 // Remember each (MI, OpNo) that refers to Reg.
291 if (Ops)
292 Ops->push_back(Elt: std::make_pair(x: MO.getParent(), y: O.getOperandNo()));
293
294 // Both defs and uses can read virtual registers.
295 if (MO.readsReg()) {
296 RI.Reads = true;
297 if (MO.isDef())
298 RI.Tied = true;
299 }
300
301 // Only defs can write.
302 if (MO.isDef())
303 RI.Writes = true;
304 else if (!RI.Tied &&
305 MO.getParent()->isRegTiedToDefOperand(UseOpIdx: O.getOperandNo()))
306 RI.Tied = true;
307 }
308 return RI;
309}
310
311std::pair<LaneBitmask, LaneBitmask>
312llvm::AnalyzeVirtRegLanesInBundle(const MachineInstr &MI, Register Reg,
313 const MachineRegisterInfo &MRI,
314 const TargetRegisterInfo &TRI) {
315
316 LaneBitmask UseMask, DefMask;
317
318 for (const MachineOperand &MO : const_mi_bundle_ops(MI)) {
319 if (!MO.isReg() || MO.getReg() != Reg)
320 continue;
321
322 unsigned SubReg = MO.getSubReg();
323 if (SubReg == 0 && MO.isUse() && !MO.isUndef())
324 UseMask |= MRI.getMaxLaneMaskForVReg(Reg);
325
326 LaneBitmask SubRegMask = TRI.getSubRegIndexLaneMask(SubIdx: SubReg);
327 if (MO.isDef()) {
328 if (!MO.isUndef())
329 UseMask |= ~SubRegMask;
330 DefMask |= SubRegMask;
331 } else if (!MO.isUndef())
332 UseMask |= SubRegMask;
333 }
334
335 return {UseMask, DefMask};
336}
337
338PhysRegInfo llvm::AnalyzePhysRegInBundle(const MachineInstr &MI, Register Reg,
339 const TargetRegisterInfo *TRI) {
340 bool AllDefsDead = true;
341 PhysRegInfo PRI = {.Clobbered: false, .Defined: false, .FullyDefined: false, .Read: false, .FullyRead: false, .DeadDef: false, .PartialDeadDef: false, .Killed: false};
342
343 assert(Reg.isPhysical() && "analyzePhysReg not given a physical register!");
344 for (const MachineOperand &MO : const_mi_bundle_ops(MI)) {
345 if (MO.isRegMask() && MO.clobbersPhysReg(PhysReg: Reg)) {
346 PRI.Clobbered = true;
347 continue;
348 }
349
350 if (!MO.isReg())
351 continue;
352
353 Register MOReg = MO.getReg();
354 if (!MOReg || !MOReg.isPhysical())
355 continue;
356
357 if (!TRI->regsOverlap(RegA: MOReg, RegB: Reg))
358 continue;
359
360 bool Covered = TRI->isSuperRegisterEq(RegA: Reg, RegB: MOReg);
361 if (MO.readsReg()) {
362 PRI.Read = true;
363 if (Covered) {
364 PRI.FullyRead = true;
365 if (MO.isKill())
366 PRI.Killed = true;
367 }
368 } else if (MO.isDef()) {
369 PRI.Defined = true;
370 if (Covered)
371 PRI.FullyDefined = true;
372 if (!MO.isDead())
373 AllDefsDead = false;
374 }
375 }
376
377 if (AllDefsDead) {
378 if (PRI.FullyDefined || PRI.Clobbered)
379 PRI.DeadDef = true;
380 else if (PRI.Defined)
381 PRI.PartialDeadDef = true;
382 }
383
384 return PRI;
385}
386
387PreservedAnalyses
388llvm::FinalizeBundleTestPass::run(MachineFunction &MF,
389 MachineFunctionAnalysisManager &) {
390 // For testing purposes, bundle the entire contents of each basic block
391 // except for terminators.
392 for (MachineBasicBlock &MBB : MF)
393 finalizeBundle(MBB, FirstMI: MBB.instr_begin(), LastMI: MBB.getFirstInstrTerminator());
394 return getMachineFunctionPassPreservedAnalyses();
395}
396