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