1 //===-- lib/CodeGen/MachineInstrBundle.cpp --------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "llvm/CodeGen/MachineInstrBundle.h"
11 #include "llvm/CodeGen/MachineInstrBuilder.h"
12 #include "llvm/CodeGen/Passes.h"
13 #include "llvm/CodeGen/MachineFunctionPass.h"
14 #include "llvm/Target/TargetInstrInfo.h"
15 #include "llvm/Target/TargetMachine.h"
16 #include "llvm/Target/TargetRegisterInfo.h"
17 #include "llvm/ADT/SmallSet.h"
18 #include "llvm/ADT/SmallVector.h"
19 using namespace llvm;
20 
21 namespace {
22   class UnpackMachineBundles : public MachineFunctionPass {
23   public:
24     static char ID; // Pass identification
25     UnpackMachineBundles() : MachineFunctionPass(ID) {
26       initializeUnpackMachineBundlesPass(*PassRegistry::getPassRegistry());
27     }
28 
29     virtual bool runOnMachineFunction(MachineFunction &MF);
30   };
31 } // end anonymous namespace
32 
33 char UnpackMachineBundles::ID = 0;
34 INITIALIZE_PASS(UnpackMachineBundles, "unpack-mi-bundles",
35                 "Unpack machine instruction bundles", false, false)
36 
37 FunctionPass *llvm::createUnpackMachineBundlesPass() {
38   return new UnpackMachineBundles();
39 }
40 
41 bool UnpackMachineBundles::runOnMachineFunction(MachineFunction &MF) {
42   bool Changed = false;
43   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
44     MachineBasicBlock *MBB = &*I;
45 
46     for (MachineBasicBlock::instr_iterator MII = MBB->instr_begin(),
47            MIE = MBB->instr_end(); MII != MIE; ) {
48       MachineInstr *MI = &*MII;
49 
50       // Remove BUNDLE instruction and the InsideBundle flags from bundled
51       // instructions.
52       if (MI->isBundle()) {
53         while (++MII != MIE && MII->isInsideBundle()) {
54           MII->setIsInsideBundle(false);
55           for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) {
56             MachineOperand &MO = MII->getOperand(i);
57             if (MO.isReg() && MO.isInternalRead())
58               MO.setIsInternalRead(false);
59           }
60         }
61         MI->eraseFromParent();
62 
63         Changed = true;
64         continue;
65       }
66 
67       ++MII;
68     }
69   }
70 
71   return Changed;
72 }
73 
74 
75 namespace {
76   class FinalizeMachineBundles : public MachineFunctionPass {
77   public:
78     static char ID; // Pass identification
79     FinalizeMachineBundles() : MachineFunctionPass(ID) {
80       initializeFinalizeMachineBundlesPass(*PassRegistry::getPassRegistry());
81     }
82 
83     virtual bool runOnMachineFunction(MachineFunction &MF);
84   };
85 } // end anonymous namespace
86 
87 char FinalizeMachineBundles::ID = 0;
88 INITIALIZE_PASS(FinalizeMachineBundles, "finalize-mi-bundles",
89                 "Finalize machine instruction bundles", false, false)
90 
91 FunctionPass *llvm::createFinalizeMachineBundlesPass() {
92   return new FinalizeMachineBundles();
93 }
94 
95 bool FinalizeMachineBundles::runOnMachineFunction(MachineFunction &MF) {
96   return llvm::finalizeBundles(MF);
97 }
98 
99 
100 /// finalizeBundle - Finalize a machine instruction bundle which includes
101 /// a sequence of instructions starting from FirstMI to LastMI (exclusive).
102 /// This routine adds a BUNDLE instruction to represent the bundle, it adds
103 /// IsInternalRead markers to MachineOperands which are defined inside the
104 /// bundle, and it copies externally visible defs and uses to the BUNDLE
105 /// instruction.
106 void llvm::finalizeBundle(MachineBasicBlock &MBB,
107                           MachineBasicBlock::instr_iterator FirstMI,
108                           MachineBasicBlock::instr_iterator LastMI) {
109   assert(FirstMI != LastMI && "Empty bundle?");
110 
111   const TargetMachine &TM = MBB.getParent()->getTarget();
112   const TargetInstrInfo *TII = TM.getInstrInfo();
113   const TargetRegisterInfo *TRI = TM.getRegisterInfo();
114 
115   MachineInstrBuilder MIB = BuildMI(MBB, FirstMI, FirstMI->getDebugLoc(),
116                                     TII->get(TargetOpcode::BUNDLE));
117 
118   SmallVector<unsigned, 8> LocalDefs;
119   SmallSet<unsigned, 8> LocalDefSet;
120   SmallSet<unsigned, 8> DeadDefSet;
121   SmallSet<unsigned, 8> KilledDefSet;
122   SmallVector<unsigned, 8> ExternUses;
123   SmallSet<unsigned, 8> ExternUseSet;
124   SmallSet<unsigned, 8> KilledUseSet;
125   SmallSet<unsigned, 8> UndefUseSet;
126   SmallVector<MachineOperand*, 4> Defs;
127   for (; FirstMI != LastMI; ++FirstMI) {
128     for (unsigned i = 0, e = FirstMI->getNumOperands(); i != e; ++i) {
129       MachineOperand &MO = FirstMI->getOperand(i);
130       if (!MO.isReg())
131         continue;
132       if (MO.isDef()) {
133         Defs.push_back(&MO);
134         continue;
135       }
136 
137       unsigned Reg = MO.getReg();
138       if (!Reg)
139         continue;
140       assert(TargetRegisterInfo::isPhysicalRegister(Reg));
141       if (LocalDefSet.count(Reg)) {
142         MO.setIsInternalRead();
143         if (MO.isKill())
144           // Internal def is now killed.
145           KilledDefSet.insert(Reg);
146       } else {
147         if (ExternUseSet.insert(Reg)) {
148           ExternUses.push_back(Reg);
149           if (MO.isUndef())
150             UndefUseSet.insert(Reg);
151         }
152         if (MO.isKill())
153           // External def is now killed.
154           KilledUseSet.insert(Reg);
155       }
156     }
157 
158     for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
159       MachineOperand &MO = *Defs[i];
160       unsigned Reg = MO.getReg();
161       if (!Reg)
162         continue;
163 
164       if (LocalDefSet.insert(Reg)) {
165         LocalDefs.push_back(Reg);
166         if (MO.isDead()) {
167           DeadDefSet.insert(Reg);
168         }
169       } else {
170         // Re-defined inside the bundle, it's no longer killed.
171         KilledDefSet.erase(Reg);
172         if (!MO.isDead())
173           // Previously defined but dead.
174           DeadDefSet.erase(Reg);
175       }
176 
177       if (!MO.isDead()) {
178         for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
179              unsigned SubReg = *SubRegs; ++SubRegs) {
180           if (LocalDefSet.insert(SubReg))
181             LocalDefs.push_back(SubReg);
182         }
183       }
184     }
185 
186     FirstMI->setIsInsideBundle();
187     Defs.clear();
188   }
189 
190   SmallSet<unsigned, 8> Added;
191   for (unsigned i = 0, e = LocalDefs.size(); i != e; ++i) {
192     unsigned Reg = LocalDefs[i];
193     if (Added.insert(Reg)) {
194       // If it's not live beyond end of the bundle, mark it dead.
195       bool isDead = DeadDefSet.count(Reg) || KilledDefSet.count(Reg);
196       MIB.addReg(Reg, getDefRegState(true) | getDeadRegState(isDead) |
197                  getImplRegState(true));
198     }
199   }
200 
201   for (unsigned i = 0, e = ExternUses.size(); i != e; ++i) {
202     unsigned Reg = ExternUses[i];
203     bool isKill = KilledUseSet.count(Reg);
204     bool isUndef = UndefUseSet.count(Reg);
205     MIB.addReg(Reg, getKillRegState(isKill) | getUndefRegState(isUndef) |
206                getImplRegState(true));
207   }
208 }
209 
210 /// finalizeBundle - Same functionality as the previous finalizeBundle except
211 /// the last instruction in the bundle is not provided as an input. This is
212 /// used in cases where bundles are pre-determined by marking instructions
213 /// with 'InsideBundle' marker. It returns the MBB instruction iterator that
214 /// points to the end of the bundle.
215 MachineBasicBlock::instr_iterator
216 llvm::finalizeBundle(MachineBasicBlock &MBB,
217                      MachineBasicBlock::instr_iterator FirstMI) {
218   MachineBasicBlock::instr_iterator E = MBB.instr_end();
219   MachineBasicBlock::instr_iterator LastMI = llvm::next(FirstMI);
220   while (LastMI != E && LastMI->isInsideBundle())
221     ++LastMI;
222   finalizeBundle(MBB, FirstMI, LastMI);
223   return LastMI;
224 }
225 
226 /// finalizeBundles - Finalize instruction bundles in the specified
227 /// MachineFunction. Return true if any bundles are finalized.
228 bool llvm::finalizeBundles(MachineFunction &MF) {
229   bool Changed = false;
230   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
231     MachineBasicBlock &MBB = *I;
232 
233     MachineBasicBlock::instr_iterator MII = MBB.instr_begin();
234     assert(!MII->isInsideBundle() &&
235            "First instr cannot be inside bundle before finalization!");
236 
237     MachineBasicBlock::instr_iterator MIE = MBB.instr_end();
238     for (++MII; MII != MIE; ) {
239       if (!MII->isInsideBundle())
240         ++MII;
241       else {
242         MII = finalizeBundle(MBB, llvm::prior(MII));
243         Changed = true;
244       }
245     }
246   }
247 
248   return Changed;
249 }
250