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