1 //===-- CodePlacementOpt.cpp - Code Placement pass. -----------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the pass that optimize code placement and align loop
11 // headers to target specific alignment boundary.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "code-placement"
16 #include "llvm/CodeGen/MachineLoopInfo.h"
17 #include "llvm/CodeGen/MachineFunctionPass.h"
18 #include "llvm/CodeGen/Passes.h"
19 #include "llvm/Target/TargetInstrInfo.h"
20 #include "llvm/Target/TargetLowering.h"
21 #include "llvm/Target/TargetMachine.h"
22 #include "llvm/Support/Compiler.h"
23 #include "llvm/Support/Debug.h"
24 #include "llvm/ADT/Statistic.h"
27 STATISTIC(NumLoopsAligned, "Number of loops aligned");
28 STATISTIC(NumIntraElim, "Number of intra loop branches eliminated");
29 STATISTIC(NumIntraMoved, "Number of intra loop branches moved");
32 class CodePlacementOpt : public MachineFunctionPass {
33 const MachineLoopInfo *MLI;
34 const TargetInstrInfo *TII;
35 const TargetLowering *TLI;
37 /// ChangedMBBs - BBs which are modified by OptimizeIntraLoopEdges.
38 SmallPtrSet<MachineBasicBlock*, 8> ChangedMBBs;
40 /// UncondJmpMBBs - A list of BBs which are in loops and end with
41 /// unconditional branches.
42 SmallVector<std::pair<MachineBasicBlock*,MachineBasicBlock*>, 4>
47 CodePlacementOpt() : MachineFunctionPass(&ID) {}
49 virtual bool runOnMachineFunction(MachineFunction &MF);
50 virtual const char *getPassName() const {
51 return "Code Placement Optimizater";
54 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
55 AU.addRequired<MachineLoopInfo>();
56 AU.addPreservedID(MachineDominatorsID);
57 MachineFunctionPass::getAnalysisUsage(AU);
61 bool OptimizeIntraLoopEdges();
62 bool AlignLoops(MachineFunction &MF);
63 bool AlignLoop(MachineFunction &MF, MachineLoop *L, unsigned Align);
66 char CodePlacementOpt::ID = 0;
67 } // end anonymous namespace
69 FunctionPass *llvm::createCodePlacementOptPass() {
70 return new CodePlacementOpt();
73 /// OptimizeBackEdges - Place loop back edges to move unconditional branches
78 /// <fallthrough to B>
80 /// B: --> loop header
82 /// jcc <cond> C, [exit]
98 /// B: --> loop header
100 /// jcc <cond> C, [exit]
102 bool CodePlacementOpt::OptimizeIntraLoopEdges() {
103 if (!TLI->shouldOptimizeCodePlacement())
106 bool Changed = false;
107 for (unsigned i = 0, e = UncondJmpMBBs.size(); i != e; ++i) {
108 MachineBasicBlock *MBB = UncondJmpMBBs[i].first;
109 MachineBasicBlock *SuccMBB = UncondJmpMBBs[i].second;
110 MachineLoop *L = MLI->getLoopFor(MBB);
111 assert(L && "BB is expected to be in a loop!");
113 if (ChangedMBBs.count(MBB)) {
114 // BB has been modified, re-analyze.
115 MachineBasicBlock *TBB = 0, *FBB = 0;
116 SmallVector<MachineOperand, 4> Cond;
117 if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond) || !Cond.empty())
119 if (MLI->getLoopFor(TBB) != L || TBB->isLandingPad())
123 assert(MLI->getLoopFor(SuccMBB) == L &&
124 "Successor is not in the same loop!");
127 if (MBB->isLayoutSuccessor(SuccMBB)) {
128 // Successor is right after MBB, just eliminate the unconditional jmp.
130 TII->RemoveBranch(*MBB);
131 ChangedMBBs.insert(MBB);
137 // Now check if the predecessor is fallthrough from any BB. If there is,
138 // that BB should be from outside the loop since edge will become a jmp.
139 bool OkToMove = true;
140 MachineBasicBlock *FtMBB = 0, *FtTBB = 0, *FtFBB = 0;
141 SmallVector<MachineOperand, 4> FtCond;
142 for (MachineBasicBlock::pred_iterator PI = SuccMBB->pred_begin(),
143 PE = SuccMBB->pred_end(); PI != PE; ++PI) {
144 MachineBasicBlock *PredMBB = *PI;
145 if (PredMBB->isLayoutSuccessor(SuccMBB)) {
146 if (TII->AnalyzeBranch(*PredMBB, FtTBB, FtFBB, FtCond)) {
153 assert(FtFBB != SuccMBB && "Unexpected control flow!");
159 MachineLoop *PL = MLI->getLoopFor(PredMBB);
160 if (PL && (PL == L || PL->getLoopDepth() >= L->getLoopDepth()))
170 // Is it profitable? If SuccMBB can fallthrough itself, that can be changed
172 MachineBasicBlock *TBB = 0, *FBB = 0;
173 SmallVector<MachineOperand, 4> Cond;
174 if (TII->AnalyzeBranch(*SuccMBB, TBB, FBB, Cond))
176 if (!TBB && Cond.empty())
177 TBB = next(MachineFunction::iterator(SuccMBB));
178 else if (!FBB && !Cond.empty())
179 FBB = next(MachineFunction::iterator(SuccMBB));
181 // This calculate the cost of the transformation. Also, it finds the *only*
182 // intra-loop edge if there is one.
184 bool HasOneIntraSucc = true;
185 MachineBasicBlock *IntraSucc = 0;
186 for (MachineBasicBlock::succ_iterator SI = SuccMBB->succ_begin(),
187 SE = SuccMBB->succ_end(); SI != SE; ++SI) {
188 MachineBasicBlock *SSMBB = *SI;
189 if (MLI->getLoopFor(SSMBB) == L) {
193 HasOneIntraSucc = false;
196 if (SuccMBB->isLayoutSuccessor(SSMBB))
197 // This will become a jmp.
199 else if (MBB->isLayoutSuccessor(SSMBB)) {
200 // One of the successor will become the new fallthrough.
204 } else if (!FBB && SSMBB == TBB && Cond.empty()) {
207 } else if (!Cond.empty() && !TII->ReverseBranchCondition(Cond)) {
208 assert(SSMBB == TBB);
218 // Now, let's move the successor to below the BB to eliminate the jmp.
219 SuccMBB->moveAfter(MBB);
220 TII->RemoveBranch(*MBB);
221 TII->RemoveBranch(*SuccMBB);
223 TII->InsertBranch(*SuccMBB, TBB, FBB, Cond);
224 ChangedMBBs.insert(MBB);
225 ChangedMBBs.insert(SuccMBB);
227 TII->RemoveBranch(*FtMBB);
228 TII->InsertBranch(*FtMBB, FtTBB, FtFBB, FtCond);
229 ChangedMBBs.insert(FtMBB);
238 /// AlignLoops - Align loop headers to target preferred alignments.
240 bool CodePlacementOpt::AlignLoops(MachineFunction &MF) {
241 const Function *F = MF.getFunction();
242 if (F->hasFnAttr(Attribute::OptimizeForSize))
245 unsigned Align = TLI->getPrefLoopAlignment();
247 return false; // Don't care about loop alignment.
249 bool Changed = false;
251 for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
253 Changed |= AlignLoop(MF, *I, Align);
258 bool CodePlacementOpt::AlignLoop(MachineFunction &MF, MachineLoop *L,
260 bool Changed = false;
262 // Do alignment for nested loops.
263 for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
264 Changed |= AlignLoop(MF, *I, Align);
266 MachineBasicBlock *TopMBB = L->getHeader();
267 if (TopMBB == MF.begin()) return Changed;
269 MachineBasicBlock *PredMBB = prior(MachineFunction::iterator(TopMBB));
270 while (MLI->getLoopFor(PredMBB) == L) {
272 if (TopMBB == MF.begin()) return Changed;
273 PredMBB = prior(MachineFunction::iterator(TopMBB));
276 TopMBB->setAlignment(Align);
283 bool CodePlacementOpt::runOnMachineFunction(MachineFunction &MF) {
284 MLI = &getAnalysis<MachineLoopInfo>();
286 return false; // No loops.
288 TLI = MF.getTarget().getTargetLowering();
289 TII = MF.getTarget().getInstrInfo();
291 // Analyze the BBs first and keep track of BBs that
292 // end with an unconditional jmp to another block in the same loop.
293 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
294 MachineBasicBlock *MBB = I;
295 if (MBB->isLandingPad())
297 MachineLoop *L = MLI->getLoopFor(MBB);
301 MachineBasicBlock *TBB = 0, *FBB = 0;
302 SmallVector<MachineOperand, 4> Cond;
303 if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond) || !Cond.empty())
305 if (MLI->getLoopFor(TBB) == L && !TBB->isLandingPad())
306 UncondJmpMBBs.push_back(std::make_pair(MBB, TBB));
309 bool Changed = OptimizeIntraLoopEdges();
311 Changed |= AlignLoops(MF);
314 UncondJmpMBBs.clear();