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