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 (MachineOperand &MO  : MII->operands()) {
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())
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     // Debug instructions have no effects to track.
148     if (MII->isDebugInstr())
149       continue;
150 
151     for (MachineOperand &MO : MII->operands()) {
152       if (!MO.isReg())
153         continue;
154       if (MO.isDef()) {
155         Defs.push_back(&MO);
156         continue;
157       }
158 
159       Register Reg = MO.getReg();
160       if (!Reg)
161         continue;
162 
163       if (LocalDefSet.count(Reg)) {
164         MO.setIsInternalRead();
165         if (MO.isKill())
166           // Internal def is now killed.
167           KilledDefSet.insert(Reg);
168       } else {
169         if (ExternUseSet.insert(Reg).second) {
170           ExternUses.push_back(Reg);
171           if (MO.isUndef())
172             UndefUseSet.insert(Reg);
173         }
174         if (MO.isKill())
175           // External def is now killed.
176           KilledUseSet.insert(Reg);
177       }
178     }
179 
180     for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
181       MachineOperand &MO = *Defs[i];
182       Register Reg = MO.getReg();
183       if (!Reg)
184         continue;
185 
186       if (LocalDefSet.insert(Reg).second) {
187         LocalDefs.push_back(Reg);
188         if (MO.isDead()) {
189           DeadDefSet.insert(Reg);
190         }
191       } else {
192         // Re-defined inside the bundle, it's no longer killed.
193         KilledDefSet.erase(Reg);
194         if (!MO.isDead())
195           // Previously defined but dead.
196           DeadDefSet.erase(Reg);
197       }
198 
199       if (!MO.isDead() && Reg.isPhysical()) {
200         for (MCPhysReg SubReg : TRI->subregs(Reg)) {
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 (MachineBasicBlock &MBB : MF) {
260     MachineBasicBlock::instr_iterator MII = MBB.instr_begin();
261     MachineBasicBlock::instr_iterator MIE = MBB.instr_end();
262     if (MII == MIE)
263       continue;
264     assert(!MII->isInsideBundle() &&
265            "First instr cannot be inside bundle before finalization!");
266 
267     for (++MII; MII != MIE; ) {
268       if (!MII->isInsideBundle())
269         ++MII;
270       else {
271         MII = finalizeBundle(MBB, std::prev(MII));
272         Changed = true;
273       }
274     }
275   }
276 
277   return Changed;
278 }
279 
280 VirtRegInfo llvm::AnalyzeVirtRegInBundle(
281     MachineInstr &MI, Register Reg,
282     SmallVectorImpl<std::pair<MachineInstr *, unsigned>> *Ops) {
283   VirtRegInfo RI = {false, false, false};
284   for (MIBundleOperands O(MI); O.isValid(); ++O) {
285     MachineOperand &MO = *O;
286     if (!MO.isReg() || MO.getReg() != Reg)
287       continue;
288 
289     // Remember each (MI, OpNo) that refers to Reg.
290     if (Ops)
291       Ops->push_back(std::make_pair(MO.getParent(), O.getOperandNo()));
292 
293     // Both defs and uses can read virtual registers.
294     if (MO.readsReg()) {
295       RI.Reads = true;
296       if (MO.isDef())
297         RI.Tied = true;
298     }
299 
300     // Only defs can write.
301     if (MO.isDef())
302       RI.Writes = true;
303     else if (!RI.Tied &&
304              MO.getParent()->isRegTiedToDefOperand(O.getOperandNo()))
305       RI.Tied = true;
306   }
307   return RI;
308 }
309 
310 std::pair<LaneBitmask, LaneBitmask>
311 llvm::AnalyzeVirtRegLanesInBundle(const MachineInstr &MI, Register Reg,
312                                   const MachineRegisterInfo &MRI,
313                                   const TargetRegisterInfo &TRI) {
314 
315   LaneBitmask UseMask, DefMask;
316 
317   for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
318     const MachineOperand &MO = *O;
319     if (!MO.isReg() || MO.getReg() != Reg)
320       continue;
321 
322     unsigned SubReg = MO.getSubReg();
323     if (SubReg == 0 && MO.isUse() && !MO.isUndef())
324       UseMask |= MRI.getMaxLaneMaskForVReg(Reg);
325 
326     LaneBitmask SubRegMask = TRI.getSubRegIndexLaneMask(SubReg);
327     if (MO.isDef()) {
328       if (!MO.isUndef())
329         UseMask |= ~SubRegMask;
330       DefMask |= SubRegMask;
331     } else if (!MO.isUndef())
332       UseMask |= SubRegMask;
333   }
334 
335   return {UseMask, DefMask};
336 }
337 
338 PhysRegInfo llvm::AnalyzePhysRegInBundle(const MachineInstr &MI, Register Reg,
339                                          const TargetRegisterInfo *TRI) {
340   bool AllDefsDead = true;
341   PhysRegInfo PRI = {false, false, false, false, false, false, false, false};
342 
343   assert(Reg.isPhysical() && "analyzePhysReg not given a physical register!");
344   for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
345     const MachineOperand &MO = *O;
346 
347     if (MO.isRegMask() && MO.clobbersPhysReg(Reg)) {
348       PRI.Clobbered = true;
349       continue;
350     }
351 
352     if (!MO.isReg())
353       continue;
354 
355     Register MOReg = MO.getReg();
356     if (!MOReg || !MOReg.isPhysical())
357       continue;
358 
359     if (!TRI->regsOverlap(MOReg, Reg))
360       continue;
361 
362     bool Covered = TRI->isSuperRegisterEq(Reg, MOReg);
363     if (MO.readsReg()) {
364       PRI.Read = true;
365       if (Covered) {
366         PRI.FullyRead = true;
367         if (MO.isKill())
368           PRI.Killed = true;
369       }
370     } else if (MO.isDef()) {
371       PRI.Defined = true;
372       if (Covered)
373         PRI.FullyDefined = true;
374       if (!MO.isDead())
375         AllDefsDead = false;
376     }
377   }
378 
379   if (AllDefsDead) {
380     if (PRI.FullyDefined || PRI.Clobbered)
381       PRI.DeadDef = true;
382     else if (PRI.Defined)
383       PRI.PartialDeadDef = true;
384   }
385 
386   return PRI;
387 }
388