Remove includes of Support/Compiler.h that are no longer needed after the
[oota-llvm.git] / lib / CodeGen / MachineLICM.cpp
1 //===-- MachineLICM.cpp - Machine Loop Invariant Code Motion Pass ---------===//
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 // This pass performs loop invariant code motion on machine instructions. We
11 // attempt to remove as much code from the body of a loop as possible.
12 //
13 // This pass does not attempt to throttle itself to limit register pressure.
14 // The register allocation phases are expected to perform rematerialization
15 // to recover when register pressure is high.
16 //
17 // This pass is not intended to be a replacement or a complete alternative
18 // for the LLVM-IR-level LICM pass. It is only designed to hoist simple
19 // constructs that are not exposed before lowering and instruction selection.
20 //
21 //===----------------------------------------------------------------------===//
22
23 #define DEBUG_TYPE "machine-licm"
24 #include "llvm/CodeGen/Passes.h"
25 #include "llvm/CodeGen/MachineDominators.h"
26 #include "llvm/CodeGen/MachineLoopInfo.h"
27 #include "llvm/CodeGen/MachineRegisterInfo.h"
28 #include "llvm/Target/TargetRegisterInfo.h"
29 #include "llvm/Target/TargetInstrInfo.h"
30 #include "llvm/Target/TargetMachine.h"
31 #include "llvm/Analysis/AliasAnalysis.h"
32 #include "llvm/ADT/DenseMap.h"
33 #include "llvm/ADT/Statistic.h"
34 #include "llvm/Support/Debug.h"
35 #include "llvm/Support/raw_ostream.h"
36
37 using namespace llvm;
38
39 STATISTIC(NumHoisted, "Number of machine instructions hoisted out of loops");
40 STATISTIC(NumCSEed,   "Number of hoisted machine instructions CSEed");
41
42 namespace {
43   class MachineLICM : public MachineFunctionPass {
44     const TargetMachine   *TM;
45     const TargetInstrInfo *TII;
46     const TargetRegisterInfo *TRI;
47     BitVector AllocatableSet;
48
49     // Various analyses that we use...
50     AliasAnalysis        *AA;      // Alias analysis info.
51     MachineLoopInfo      *LI;      // Current MachineLoopInfo
52     MachineDominatorTree *DT;      // Machine dominator tree for the cur loop
53     MachineRegisterInfo  *RegInfo; // Machine register information
54
55     // State that is updated as we process loops
56     bool         Changed;          // True if a loop is changed.
57     MachineLoop *CurLoop;          // The current loop we are working on.
58     MachineBasicBlock *CurPreheader; // The preheader for CurLoop.
59
60     // For each BB and opcode pair, keep a list of hoisted instructions.
61     DenseMap<std::pair<unsigned, unsigned>,
62       std::vector<const MachineInstr*> > CSEMap;
63   public:
64     static char ID; // Pass identification, replacement for typeid
65     MachineLICM() : MachineFunctionPass(&ID) {}
66
67     virtual bool runOnMachineFunction(MachineFunction &MF);
68
69     const char *getPassName() const { return "Machine Instruction LICM"; }
70
71     // FIXME: Loop preheaders?
72     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
73       AU.setPreservesCFG();
74       AU.addRequired<MachineLoopInfo>();
75       AU.addRequired<MachineDominatorTree>();
76       AU.addRequired<AliasAnalysis>();
77       AU.addPreserved<MachineLoopInfo>();
78       AU.addPreserved<MachineDominatorTree>();
79       MachineFunctionPass::getAnalysisUsage(AU);
80     }
81
82     virtual void releaseMemory() {
83       CSEMap.clear();
84     }
85
86   private:
87     /// IsLoopInvariantInst - Returns true if the instruction is loop
88     /// invariant. I.e., all virtual register operands are defined outside of
89     /// the loop, physical registers aren't accessed (explicitly or implicitly),
90     /// and the instruction is hoistable.
91     /// 
92     bool IsLoopInvariantInst(MachineInstr &I);
93
94     /// IsProfitableToHoist - Return true if it is potentially profitable to
95     /// hoist the given loop invariant.
96     bool IsProfitableToHoist(MachineInstr &MI);
97
98     /// HoistRegion - Walk the specified region of the CFG (defined by all
99     /// blocks dominated by the specified block, and that are in the current
100     /// loop) in depth first order w.r.t the DominatorTree. This allows us to
101     /// visit definitions before uses, allowing us to hoist a loop body in one
102     /// pass without iteration.
103     ///
104     void HoistRegion(MachineDomTreeNode *N);
105
106     /// Hoist - When an instruction is found to only use loop invariant operands
107     /// that is safe to hoist, this instruction is called to do the dirty work.
108     ///
109     void Hoist(MachineInstr &MI);
110   };
111 } // end anonymous namespace
112
113 char MachineLICM::ID = 0;
114 static RegisterPass<MachineLICM>
115 X("machinelicm", "Machine Loop Invariant Code Motion");
116
117 FunctionPass *llvm::createMachineLICMPass() { return new MachineLICM(); }
118
119 /// LoopIsOuterMostWithPreheader - Test if the given loop is the outer-most
120 /// loop that has a preheader.
121 static bool LoopIsOuterMostWithPreheader(MachineLoop *CurLoop) {
122   for (MachineLoop *L = CurLoop->getParentLoop(); L; L = L->getParentLoop())
123     if (L->getLoopPreheader())
124       return false;
125   return true;
126 }
127
128 /// Hoist expressions out of the specified loop. Note, alias info for inner loop
129 /// is not preserved so it is not a good idea to run LICM multiple times on one
130 /// loop.
131 ///
132 bool MachineLICM::runOnMachineFunction(MachineFunction &MF) {
133   DEBUG(errs() << "******** Machine LICM ********\n");
134
135   Changed = false;
136   TM = &MF.getTarget();
137   TII = TM->getInstrInfo();
138   TRI = TM->getRegisterInfo();
139   RegInfo = &MF.getRegInfo();
140   AllocatableSet = TRI->getAllocatableSet(MF);
141
142   // Get our Loop information...
143   LI = &getAnalysis<MachineLoopInfo>();
144   DT = &getAnalysis<MachineDominatorTree>();
145   AA = &getAnalysis<AliasAnalysis>();
146
147   for (MachineLoopInfo::iterator
148          I = LI->begin(), E = LI->end(); I != E; ++I) {
149     CurLoop = *I;
150
151     // Only visit outer-most preheader-sporting loops.
152     if (!LoopIsOuterMostWithPreheader(CurLoop))
153       continue;
154
155     // Determine the block to which to hoist instructions. If we can't find a
156     // suitable loop preheader, we can't do any hoisting.
157     //
158     // FIXME: We are only hoisting if the basic block coming into this loop
159     // has only one successor. This isn't the case in general because we haven't
160     // broken critical edges or added preheaders.
161     CurPreheader = CurLoop->getLoopPreheader();
162     if (!CurPreheader)
163       continue;
164
165     HoistRegion(DT->getNode(CurLoop->getHeader()));
166   }
167
168   return Changed;
169 }
170
171 /// HoistRegion - Walk the specified region of the CFG (defined by all blocks
172 /// dominated by the specified block, and that are in the current loop) in depth
173 /// first order w.r.t the DominatorTree. This allows us to visit definitions
174 /// before uses, allowing us to hoist a loop body in one pass without iteration.
175 ///
176 void MachineLICM::HoistRegion(MachineDomTreeNode *N) {
177   assert(N != 0 && "Null dominator tree node?");
178   MachineBasicBlock *BB = N->getBlock();
179
180   // If this subregion is not in the top level loop at all, exit.
181   if (!CurLoop->contains(BB)) return;
182
183   for (MachineBasicBlock::iterator
184          MII = BB->begin(), E = BB->end(); MII != E; ) {
185     MachineBasicBlock::iterator NextMII = MII; ++NextMII;
186     MachineInstr &MI = *MII;
187
188     Hoist(MI);
189
190     MII = NextMII;
191   }
192
193   const std::vector<MachineDomTreeNode*> &Children = N->getChildren();
194
195   for (unsigned I = 0, E = Children.size(); I != E; ++I)
196     HoistRegion(Children[I]);
197 }
198
199 /// IsLoopInvariantInst - Returns true if the instruction is loop
200 /// invariant. I.e., all virtual register operands are defined outside of the
201 /// loop, physical registers aren't accessed explicitly, and there are no side
202 /// effects that aren't captured by the operands or other flags.
203 /// 
204 bool MachineLICM::IsLoopInvariantInst(MachineInstr &I) {
205   const TargetInstrDesc &TID = I.getDesc();
206   
207   // Ignore stuff that we obviously can't hoist.
208   if (TID.mayStore() || TID.isCall() || TID.isTerminator() ||
209       TID.hasUnmodeledSideEffects())
210     return false;
211
212   if (TID.mayLoad()) {
213     // Okay, this instruction does a load. As a refinement, we allow the target
214     // to decide whether the loaded value is actually a constant. If so, we can
215     // actually use it as a load.
216     if (!I.isInvariantLoad(AA))
217       // FIXME: we should be able to sink loads with no other side effects if
218       // there is nothing that can change memory from here until the end of
219       // block. This is a trivial form of alias analysis.
220       return false;
221   }
222
223   DEBUG({
224       errs() << "--- Checking if we can hoist " << I;
225       if (I.getDesc().getImplicitUses()) {
226         errs() << "  * Instruction has implicit uses:\n";
227
228         const TargetRegisterInfo *TRI = TM->getRegisterInfo();
229         for (const unsigned *ImpUses = I.getDesc().getImplicitUses();
230              *ImpUses; ++ImpUses)
231           errs() << "      -> " << TRI->getName(*ImpUses) << "\n";
232       }
233
234       if (I.getDesc().getImplicitDefs()) {
235         errs() << "  * Instruction has implicit defines:\n";
236
237         const TargetRegisterInfo *TRI = TM->getRegisterInfo();
238         for (const unsigned *ImpDefs = I.getDesc().getImplicitDefs();
239              *ImpDefs; ++ImpDefs)
240           errs() << "      -> " << TRI->getName(*ImpDefs) << "\n";
241       }
242     });
243
244   if (I.getDesc().getImplicitDefs() || I.getDesc().getImplicitUses()) {
245     DEBUG(errs() << "Cannot hoist with implicit defines or uses\n");
246     return false;
247   }
248
249   // The instruction is loop invariant if all of its operands are.
250   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
251     const MachineOperand &MO = I.getOperand(i);
252
253     if (!MO.isReg())
254       continue;
255
256     unsigned Reg = MO.getReg();
257     if (Reg == 0) continue;
258
259     // Don't hoist an instruction that uses or defines a physical register.
260     if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
261       if (MO.isUse()) {
262         // If the physreg has no defs anywhere, it's just an ambient register
263         // and we can freely move its uses. Alternatively, if it's allocatable,
264         // it could get allocated to something with a def during allocation.
265         if (!RegInfo->def_empty(Reg))
266           return false;
267         if (AllocatableSet.test(Reg))
268           return false;
269         // Check for a def among the register's aliases too.
270         for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
271           unsigned AliasReg = *Alias;
272           if (!RegInfo->def_empty(AliasReg))
273             return false;
274           if (AllocatableSet.test(AliasReg))
275             return false;
276         }
277         // Otherwise it's safe to move.
278         continue;
279       } else if (!MO.isDead()) {
280         // A def that isn't dead. We can't move it.
281         return false;
282       }
283     }
284
285     if (!MO.isUse())
286       continue;
287
288     assert(RegInfo->getVRegDef(Reg) &&
289            "Machine instr not mapped for this vreg?!");
290
291     // If the loop contains the definition of an operand, then the instruction
292     // isn't loop invariant.
293     if (CurLoop->contains(RegInfo->getVRegDef(Reg)->getParent()))
294       return false;
295   }
296
297   // If we got this far, the instruction is loop invariant!
298   return true;
299 }
300
301
302 /// HasPHIUses - Return true if the specified register has any PHI use.
303 static bool HasPHIUses(unsigned Reg, MachineRegisterInfo *RegInfo) {
304   for (MachineRegisterInfo::use_iterator UI = RegInfo->use_begin(Reg),
305          UE = RegInfo->use_end(); UI != UE; ++UI) {
306     MachineInstr *UseMI = &*UI;
307     if (UseMI->getOpcode() == TargetInstrInfo::PHI)
308       return true;
309   }
310   return false;
311 }
312
313 /// IsProfitableToHoist - Return true if it is potentially profitable to hoist
314 /// the given loop invariant.
315 bool MachineLICM::IsProfitableToHoist(MachineInstr &MI) {
316   if (MI.getOpcode() == TargetInstrInfo::IMPLICIT_DEF)
317     return false;
318
319   // FIXME: For now, only hoist re-materilizable instructions. LICM will
320   // increase register pressure. We want to make sure it doesn't increase
321   // spilling.
322   if (!TII->isTriviallyReMaterializable(&MI, AA))
323     return false;
324
325   // If result(s) of this instruction is used by PHIs, then don't hoist it.
326   // The presence of joins makes it difficult for current register allocator
327   // implementation to perform remat.
328   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
329     const MachineOperand &MO = MI.getOperand(i);
330     if (!MO.isReg() || !MO.isDef())
331       continue;
332     if (HasPHIUses(MO.getReg(), RegInfo))
333       return false;
334   }
335
336   return true;
337 }
338
339 static const MachineInstr *LookForDuplicate(const MachineInstr *MI,
340                                       std::vector<const MachineInstr*> &PrevMIs,
341                                       MachineRegisterInfo *RegInfo) {
342   unsigned NumOps = MI->getNumOperands();
343   for (unsigned i = 0, e = PrevMIs.size(); i != e; ++i) {
344     const MachineInstr *PrevMI = PrevMIs[i];
345     unsigned NumOps2 = PrevMI->getNumOperands();
346     if (NumOps != NumOps2)
347       continue;
348     bool IsSame = true;
349     for (unsigned j = 0; j != NumOps; ++j) {
350       const MachineOperand &MO = MI->getOperand(j);
351       if (MO.isReg() && MO.isDef()) {
352         if (RegInfo->getRegClass(MO.getReg()) !=
353             RegInfo->getRegClass(PrevMI->getOperand(j).getReg())) {
354           IsSame = false;
355           break;
356         }
357         continue;
358       }
359       if (!MO.isIdenticalTo(PrevMI->getOperand(j))) {
360         IsSame = false;
361         break;
362       }
363     }
364     if (IsSame)
365       return PrevMI;
366   }
367   return 0;
368 }
369
370 /// Hoist - When an instruction is found to use only loop invariant operands
371 /// that are safe to hoist, this instruction is called to do the dirty work.
372 ///
373 void MachineLICM::Hoist(MachineInstr &MI) {
374   if (!IsLoopInvariantInst(MI)) return;
375   if (!IsProfitableToHoist(MI)) return;
376
377   // Now move the instructions to the predecessor, inserting it before any
378   // terminator instructions.
379   DEBUG({
380       errs() << "Hoisting " << MI;
381       if (CurPreheader->getBasicBlock())
382         errs() << " to MachineBasicBlock "
383                << CurPreheader->getBasicBlock()->getName();
384       if (MI.getParent()->getBasicBlock())
385         errs() << " from MachineBasicBlock "
386                << MI.getParent()->getBasicBlock()->getName();
387       errs() << "\n";
388     });
389
390   // Look for opportunity to CSE the hoisted instruction.
391   std::pair<unsigned, unsigned> BBOpcPair =
392     std::make_pair(CurPreheader->getNumber(), MI.getOpcode());
393   DenseMap<std::pair<unsigned, unsigned>,
394     std::vector<const MachineInstr*> >::iterator CI = CSEMap.find(BBOpcPair);
395   bool DoneCSE = false;
396   if (CI != CSEMap.end()) {
397     const MachineInstr *Dup = LookForDuplicate(&MI, CI->second, RegInfo);
398     if (Dup) {
399       DEBUG(errs() << "CSEing " << MI << " with " << *Dup);
400       for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
401         const MachineOperand &MO = MI.getOperand(i);
402         if (MO.isReg() && MO.isDef())
403           RegInfo->replaceRegWith(MO.getReg(), Dup->getOperand(i).getReg());
404       }
405       MI.eraseFromParent();
406       DoneCSE = true;
407       ++NumCSEed;
408     }
409   }
410
411   // Otherwise, splice the instruction to the preheader.
412   if (!DoneCSE) {
413     CurPreheader->splice(CurPreheader->getFirstTerminator(),
414                          MI.getParent(), &MI);
415     // Add to the CSE map.
416     if (CI != CSEMap.end())
417       CI->second.push_back(&MI);
418     else {
419       std::vector<const MachineInstr*> CSEMIs;
420       CSEMIs.push_back(&MI);
421       CSEMap.insert(std::make_pair(BBOpcPair, CSEMIs));
422     }
423   }
424
425   ++NumHoisted;
426   Changed = true;
427 }