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 (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
51     MachineBasicBlock *MBB = &*I;
52 
53     for (MachineBasicBlock::instr_iterator MII = MBB->instr_begin(),
54            MIE = MBB->instr_end(); MII != MIE; ) {
55       MachineInstr *MI = &*MII;
56 
57       // Remove BUNDLE instruction and the InsideBundle flags from bundled
58       // instructions.
59       if (MI->isBundle()) {
60         while (++MII != MIE && MII->isBundledWithPred()) {
61           MII->unbundleFromPred();
62           for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) {
63             MachineOperand &MO = MII->getOperand(i);
64             if (MO.isReg() && MO.isInternalRead())
65               MO.setIsInternalRead(false);
66           }
67         }
68         MI->eraseFromParent();
69 
70         Changed = true;
71         continue;
72       }
73 
74       ++MII;
75     }
76   }
77 
78   return Changed;
79 }
80 
81 FunctionPass *
82 llvm::createUnpackMachineBundles(
83     std::function<bool(const MachineFunction &)> Ftor) {
84   return new UnpackMachineBundles(std::move(Ftor));
85 }
86 
87 namespace {
88   class FinalizeMachineBundles : public MachineFunctionPass {
89   public:
90     static char ID; // Pass identification
91     FinalizeMachineBundles() : MachineFunctionPass(ID) {
92       initializeFinalizeMachineBundlesPass(*PassRegistry::getPassRegistry());
93     }
94 
95     bool runOnMachineFunction(MachineFunction &MF) override;
96   };
97 } // end anonymous namespace
98 
99 char FinalizeMachineBundles::ID = 0;
100 char &llvm::FinalizeMachineBundlesID = FinalizeMachineBundles::ID;
101 INITIALIZE_PASS(FinalizeMachineBundles, "finalize-mi-bundles",
102                 "Finalize machine instruction bundles", false, false)
103 
104 bool FinalizeMachineBundles::runOnMachineFunction(MachineFunction &MF) {
105   return llvm::finalizeBundles(MF);
106 }
107 
108 /// Return the first found DebugLoc that has a DILocation, given a range of
109 /// instructions. The search range is from FirstMI to LastMI (exclusive). If no
110 /// DILocation is found, then an empty location is returned.
111 static DebugLoc getDebugLoc(MachineBasicBlock::instr_iterator FirstMI,
112                             MachineBasicBlock::instr_iterator LastMI) {
113   for (auto MII = FirstMI; MII != LastMI; ++MII)
114     if (MII->getDebugLoc().get())
115       return MII->getDebugLoc();
116   return DebugLoc();
117 }
118 
119 /// finalizeBundle - Finalize a machine instruction bundle which includes
120 /// a sequence of instructions starting from FirstMI to LastMI (exclusive).
121 /// This routine adds a BUNDLE instruction to represent the bundle, it adds
122 /// IsInternalRead markers to MachineOperands which are defined inside the
123 /// bundle, and it copies externally visible defs and uses to the BUNDLE
124 /// instruction.
125 void llvm::finalizeBundle(MachineBasicBlock &MBB,
126                           MachineBasicBlock::instr_iterator FirstMI,
127                           MachineBasicBlock::instr_iterator LastMI) {
128   assert(FirstMI != LastMI && "Empty bundle?");
129   MIBundleBuilder Bundle(MBB, FirstMI, LastMI);
130 
131   MachineFunction &MF = *MBB.getParent();
132   const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
133   const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
134 
135   MachineInstrBuilder MIB =
136       BuildMI(MF, getDebugLoc(FirstMI, LastMI), TII->get(TargetOpcode::BUNDLE));
137   Bundle.prepend(MIB);
138 
139   SmallVector<Register, 32> LocalDefs;
140   SmallSet<Register, 32> LocalDefSet;
141   SmallSet<Register, 8> DeadDefSet;
142   SmallSet<Register, 16> KilledDefSet;
143   SmallVector<Register, 8> ExternUses;
144   SmallSet<Register, 8> ExternUseSet;
145   SmallSet<Register, 8> KilledUseSet;
146   SmallSet<Register, 8> UndefUseSet;
147   SmallVector<MachineOperand*, 4> Defs;
148   for (auto MII = FirstMI; MII != LastMI; ++MII) {
149     for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) {
150       MachineOperand &MO = MII->getOperand(i);
151       if (!MO.isReg())
152         continue;
153       if (MO.isDef()) {
154         Defs.push_back(&MO);
155         continue;
156       }
157 
158       Register Reg = MO.getReg();
159       if (!Reg)
160         continue;
161 
162       if (LocalDefSet.count(Reg)) {
163         MO.setIsInternalRead();
164         if (MO.isKill())
165           // Internal def is now killed.
166           KilledDefSet.insert(Reg);
167       } else {
168         if (ExternUseSet.insert(Reg).second) {
169           ExternUses.push_back(Reg);
170           if (MO.isUndef())
171             UndefUseSet.insert(Reg);
172         }
173         if (MO.isKill())
174           // External def is now killed.
175           KilledUseSet.insert(Reg);
176       }
177     }
178 
179     for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
180       MachineOperand &MO = *Defs[i];
181       Register Reg = MO.getReg();
182       if (!Reg)
183         continue;
184 
185       if (LocalDefSet.insert(Reg).second) {
186         LocalDefs.push_back(Reg);
187         if (MO.isDead()) {
188           DeadDefSet.insert(Reg);
189         }
190       } else {
191         // Re-defined inside the bundle, it's no longer killed.
192         KilledDefSet.erase(Reg);
193         if (!MO.isDead())
194           // Previously defined but dead.
195           DeadDefSet.erase(Reg);
196       }
197 
198       if (!MO.isDead() && Register::isPhysicalRegister(Reg)) {
199         for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
200           unsigned SubReg = *SubRegs;
201           if (LocalDefSet.insert(SubReg).second)
202             LocalDefs.push_back(SubReg);
203         }
204       }
205     }
206 
207     Defs.clear();
208   }
209 
210   SmallSet<Register, 32> Added;
211   for (unsigned i = 0, e = LocalDefs.size(); i != e; ++i) {
212     Register Reg = LocalDefs[i];
213     if (Added.insert(Reg).second) {
214       // If it's not live beyond end of the bundle, mark it dead.
215       bool isDead = DeadDefSet.count(Reg) || KilledDefSet.count(Reg);
216       MIB.addReg(Reg, getDefRegState(true) | getDeadRegState(isDead) |
217                  getImplRegState(true));
218     }
219   }
220 
221   for (unsigned i = 0, e = ExternUses.size(); i != e; ++i) {
222     Register Reg = ExternUses[i];
223     bool isKill = KilledUseSet.count(Reg);
224     bool isUndef = UndefUseSet.count(Reg);
225     MIB.addReg(Reg, getKillRegState(isKill) | getUndefRegState(isUndef) |
226                getImplRegState(true));
227   }
228 
229   // Set FrameSetup/FrameDestroy for the bundle. If any of the instructions got
230   // the property, then also set it on the bundle.
231   for (auto MII = FirstMI; MII != LastMI; ++MII) {
232     if (MII->getFlag(MachineInstr::FrameSetup))
233       MIB.setMIFlag(MachineInstr::FrameSetup);
234     if (MII->getFlag(MachineInstr::FrameDestroy))
235       MIB.setMIFlag(MachineInstr::FrameDestroy);
236   }
237 }
238 
239 /// finalizeBundle - Same functionality as the previous finalizeBundle except
240 /// the last instruction in the bundle is not provided as an input. This is
241 /// used in cases where bundles are pre-determined by marking instructions
242 /// with 'InsideBundle' marker. It returns the MBB instruction iterator that
243 /// points to the end of the bundle.
244 MachineBasicBlock::instr_iterator
245 llvm::finalizeBundle(MachineBasicBlock &MBB,
246                      MachineBasicBlock::instr_iterator FirstMI) {
247   MachineBasicBlock::instr_iterator E = MBB.instr_end();
248   MachineBasicBlock::instr_iterator LastMI = std::next(FirstMI);
249   while (LastMI != E && LastMI->isInsideBundle())
250     ++LastMI;
251   finalizeBundle(MBB, FirstMI, LastMI);
252   return LastMI;
253 }
254 
255 /// finalizeBundles - Finalize instruction bundles in the specified
256 /// MachineFunction. Return true if any bundles are finalized.
257 bool llvm::finalizeBundles(MachineFunction &MF) {
258   bool Changed = false;
259   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
260     MachineBasicBlock &MBB = *I;
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, std::prev(MII));
273         Changed = true;
274       }
275     }
276   }
277 
278   return Changed;
279 }
280 
281 VirtRegInfo llvm::AnalyzeVirtRegInBundle(
282     MachineInstr &MI, Register Reg,
283     SmallVectorImpl<std::pair<MachineInstr *, unsigned>> *Ops) {
284   VirtRegInfo RI = {false, false, 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(std::make_pair(MO.getParent(), 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(O.getOperandNo()))
306       RI.Tied = true;
307   }
308   return RI;
309 }
310 
311 PhysRegInfo llvm::AnalyzePhysRegInBundle(const MachineInstr &MI, Register Reg,
312                                          const TargetRegisterInfo *TRI) {
313   bool AllDefsDead = true;
314   PhysRegInfo PRI = {false, false, false, false, false, false, false, false};
315 
316   assert(Reg.isPhysical() && "analyzePhysReg not given a physical register!");
317   for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
318     const MachineOperand &MO = *O;
319 
320     if (MO.isRegMask() && MO.clobbersPhysReg(Reg)) {
321       PRI.Clobbered = true;
322       continue;
323     }
324 
325     if (!MO.isReg())
326       continue;
327 
328     Register MOReg = MO.getReg();
329     if (!MOReg || !Register::isPhysicalRegister(MOReg))
330       continue;
331 
332     if (!TRI->regsOverlap(MOReg, Reg))
333       continue;
334 
335     bool Covered = TRI->isSuperRegisterEq(Reg, MOReg);
336     if (MO.readsReg()) {
337       PRI.Read = true;
338       if (Covered) {
339         PRI.FullyRead = true;
340         if (MO.isKill())
341           PRI.Killed = true;
342       }
343     } else if (MO.isDef()) {
344       PRI.Defined = true;
345       if (Covered)
346         PRI.FullyDefined = true;
347       if (!MO.isDead())
348         AllDefsDead = false;
349     }
350   }
351 
352   if (AllDefsDead) {
353     if (PRI.FullyDefined || PRI.Clobbered)
354       PRI.DeadDef = true;
355     else if (PRI.Defined)
356       PRI.PartialDeadDef = true;
357   }
358 
359   return PRI;
360 }
361