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/Target/TargetMachine.h"
20 #include <utility>
21 using namespace llvm;
22 
23 namespace {
24   class UnpackMachineBundles : public MachineFunctionPass {
25   public:
26     static char ID; // Pass identification
27     UnpackMachineBundles(
28         std::function<bool(const MachineFunction &)> Ftor = nullptr)
29         : MachineFunctionPass(ID), PredicateFtor(std::move(Ftor)) {
30       initializeUnpackMachineBundlesPass(*PassRegistry::getPassRegistry());
31     }
32 
33     bool runOnMachineFunction(MachineFunction &MF) override;
34 
35   private:
36     std::function<bool(const MachineFunction &)> PredicateFtor;
37   };
38 } // end anonymous namespace
39 
40 char UnpackMachineBundles::ID = 0;
41 char &llvm::UnpackMachineBundlesID = UnpackMachineBundles::ID;
42 INITIALIZE_PASS(UnpackMachineBundles, "unpack-mi-bundles",
43                 "Unpack machine instruction bundles", false, false)
44 
45 bool 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 (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) {
61             MachineOperand &MO = MII->getOperand(i);
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 
79 FunctionPass *
80 llvm::createUnpackMachineBundles(
81     std::function<bool(const MachineFunction &)> Ftor) {
82   return new UnpackMachineBundles(std::move(Ftor));
83 }
84 
85 namespace {
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 
97 char FinalizeMachineBundles::ID = 0;
98 char &llvm::FinalizeMachineBundlesID = FinalizeMachineBundles::ID;
99 INITIALIZE_PASS(FinalizeMachineBundles, "finalize-mi-bundles",
100                 "Finalize machine instruction bundles", false, false)
101 
102 bool 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.
109 static DebugLoc getDebugLoc(MachineBasicBlock::instr_iterator FirstMI,
110                             MachineBasicBlock::instr_iterator LastMI) {
111   for (auto MII = FirstMI; MII != LastMI; ++MII)
112     if (MII->getDebugLoc().get())
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.
123 void 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, getDebugLoc(FirstMI, LastMI), TII->get(TargetOpcode::BUNDLE));
135   Bundle.prepend(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     for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) {
148       MachineOperand &MO = MII->getOperand(i);
149       if (!MO.isReg())
150         continue;
151       if (MO.isDef()) {
152         Defs.push_back(&MO);
153         continue;
154       }
155 
156       Register Reg = MO.getReg();
157       if (!Reg)
158         continue;
159 
160       if (LocalDefSet.count(Reg)) {
161         MO.setIsInternalRead();
162         if (MO.isKill())
163           // Internal def is now killed.
164           KilledDefSet.insert(Reg);
165       } else {
166         if (ExternUseSet.insert(Reg).second) {
167           ExternUses.push_back(Reg);
168           if (MO.isUndef())
169             UndefUseSet.insert(Reg);
170         }
171         if (MO.isKill())
172           // External def is now killed.
173           KilledUseSet.insert(Reg);
174       }
175     }
176 
177     for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
178       MachineOperand &MO = *Defs[i];
179       Register Reg = MO.getReg();
180       if (!Reg)
181         continue;
182 
183       if (LocalDefSet.insert(Reg).second) {
184         LocalDefs.push_back(Reg);
185         if (MO.isDead()) {
186           DeadDefSet.insert(Reg);
187         }
188       } else {
189         // Re-defined inside the bundle, it's no longer killed.
190         KilledDefSet.erase(Reg);
191         if (!MO.isDead())
192           // Previously defined but dead.
193           DeadDefSet.erase(Reg);
194       }
195 
196       if (!MO.isDead() && Register::isPhysicalRegister(Reg)) {
197         for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
198           unsigned SubReg = *SubRegs;
199           if (LocalDefSet.insert(SubReg).second)
200             LocalDefs.push_back(SubReg);
201         }
202       }
203     }
204 
205     Defs.clear();
206   }
207 
208   SmallSet<Register, 32> Added;
209   for (unsigned i = 0, e = LocalDefs.size(); i != e; ++i) {
210     Register Reg = LocalDefs[i];
211     if (Added.insert(Reg).second) {
212       // If it's not live beyond end of the bundle, mark it dead.
213       bool isDead = DeadDefSet.count(Reg) || KilledDefSet.count(Reg);
214       MIB.addReg(Reg, getDefRegState(true) | getDeadRegState(isDead) |
215                  getImplRegState(true));
216     }
217   }
218 
219   for (unsigned i = 0, e = ExternUses.size(); i != e; ++i) {
220     Register Reg = ExternUses[i];
221     bool isKill = KilledUseSet.count(Reg);
222     bool isUndef = UndefUseSet.count(Reg);
223     MIB.addReg(Reg, getKillRegState(isKill) | getUndefRegState(isUndef) |
224                getImplRegState(true));
225   }
226 
227   // Set FrameSetup/FrameDestroy for the bundle. If any of the instructions got
228   // the property, then also set it on the bundle.
229   for (auto MII = FirstMI; MII != LastMI; ++MII) {
230     if (MII->getFlag(MachineInstr::FrameSetup))
231       MIB.setMIFlag(MachineInstr::FrameSetup);
232     if (MII->getFlag(MachineInstr::FrameDestroy))
233       MIB.setMIFlag(MachineInstr::FrameDestroy);
234   }
235 }
236 
237 /// finalizeBundle - Same functionality as the previous finalizeBundle except
238 /// the last instruction in the bundle is not provided as an input. This is
239 /// used in cases where bundles are pre-determined by marking instructions
240 /// with 'InsideBundle' marker. It returns the MBB instruction iterator that
241 /// points to the end of the bundle.
242 MachineBasicBlock::instr_iterator
243 llvm::finalizeBundle(MachineBasicBlock &MBB,
244                      MachineBasicBlock::instr_iterator FirstMI) {
245   MachineBasicBlock::instr_iterator E = MBB.instr_end();
246   MachineBasicBlock::instr_iterator LastMI = std::next(FirstMI);
247   while (LastMI != E && LastMI->isInsideBundle())
248     ++LastMI;
249   finalizeBundle(MBB, FirstMI, LastMI);
250   return LastMI;
251 }
252 
253 /// finalizeBundles - Finalize instruction bundles in the specified
254 /// MachineFunction. Return true if any bundles are finalized.
255 bool llvm::finalizeBundles(MachineFunction &MF) {
256   bool Changed = false;
257   for (MachineBasicBlock &MBB : MF) {
258     MachineBasicBlock::instr_iterator MII = MBB.instr_begin();
259     MachineBasicBlock::instr_iterator MIE = MBB.instr_end();
260     if (MII == MIE)
261       continue;
262     assert(!MII->isInsideBundle() &&
263            "First instr cannot be inside bundle before finalization!");
264 
265     for (++MII; MII != MIE; ) {
266       if (!MII->isInsideBundle())
267         ++MII;
268       else {
269         MII = finalizeBundle(MBB, std::prev(MII));
270         Changed = true;
271       }
272     }
273   }
274 
275   return Changed;
276 }
277 
278 VirtRegInfo llvm::AnalyzeVirtRegInBundle(
279     MachineInstr &MI, Register Reg,
280     SmallVectorImpl<std::pair<MachineInstr *, unsigned>> *Ops) {
281   VirtRegInfo RI = {false, false, false};
282   for (MIBundleOperands O(MI); O.isValid(); ++O) {
283     MachineOperand &MO = *O;
284     if (!MO.isReg() || MO.getReg() != Reg)
285       continue;
286 
287     // Remember each (MI, OpNo) that refers to Reg.
288     if (Ops)
289       Ops->push_back(std::make_pair(MO.getParent(), O.getOperandNo()));
290 
291     // Both defs and uses can read virtual registers.
292     if (MO.readsReg()) {
293       RI.Reads = true;
294       if (MO.isDef())
295         RI.Tied = true;
296     }
297 
298     // Only defs can write.
299     if (MO.isDef())
300       RI.Writes = true;
301     else if (!RI.Tied &&
302              MO.getParent()->isRegTiedToDefOperand(O.getOperandNo()))
303       RI.Tied = true;
304   }
305   return RI;
306 }
307 
308 PhysRegInfo llvm::AnalyzePhysRegInBundle(const MachineInstr &MI, Register Reg,
309                                          const TargetRegisterInfo *TRI) {
310   bool AllDefsDead = true;
311   PhysRegInfo PRI = {false, false, false, false, false, false, false, false};
312 
313   assert(Reg.isPhysical() && "analyzePhysReg not given a physical register!");
314   for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
315     const MachineOperand &MO = *O;
316 
317     if (MO.isRegMask() && MO.clobbersPhysReg(Reg)) {
318       PRI.Clobbered = true;
319       continue;
320     }
321 
322     if (!MO.isReg())
323       continue;
324 
325     Register MOReg = MO.getReg();
326     if (!MOReg || !Register::isPhysicalRegister(MOReg))
327       continue;
328 
329     if (!TRI->regsOverlap(MOReg, Reg))
330       continue;
331 
332     bool Covered = TRI->isSuperRegisterEq(Reg, MOReg);
333     if (MO.readsReg()) {
334       PRI.Read = true;
335       if (Covered) {
336         PRI.FullyRead = true;
337         if (MO.isKill())
338           PRI.Killed = true;
339       }
340     } else if (MO.isDef()) {
341       PRI.Defined = true;
342       if (Covered)
343         PRI.FullyDefined = true;
344       if (!MO.isDead())
345         AllDefsDead = false;
346     }
347   }
348 
349   if (AllDefsDead) {
350     if (PRI.FullyDefined || PRI.Clobbered)
351       PRI.DeadDef = true;
352     else if (PRI.Defined)
353       PRI.PartialDeadDef = true;
354   }
355 
356   return PRI;
357 }
358