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/CommandLine.h"
23 #include "llvm/Support/Compiler.h"
24 #include "llvm/Support/Debug.h"
25 #include "llvm/ADT/Statistic.h"
29 OptLoopBBPlacement("opt-loop-bb-placement",
30 cl::init(false), cl::Hidden,
31 cl::desc("Optimize block placements in loops"));
33 STATISTIC(NumHeaderAligned, "Number of loop header aligned");
34 STATISTIC(NumIntraElim, "Number of intra loop branches eliminated");
35 STATISTIC(NumIntraMoved, "Number of intra loop branches moved");
38 class CodePlacementOpt : public MachineFunctionPass {
39 const MachineLoopInfo *MLI;
40 const TargetInstrInfo *TII;
41 const TargetLowering *TLI;
43 /// ChangedMBBs - BBs which are modified by OptimizeIntraLoopEdges.
44 SmallPtrSet<MachineBasicBlock*, 8> ChangedMBBs;
46 /// UncondJmpMBBs - A list of BBs which are in loops and end with
47 /// unconditional branches.
48 SmallVector<std::pair<MachineBasicBlock*,MachineBasicBlock*>, 4>
51 /// LoopHeaders - A list of BBs which are loop headers.
52 SmallVector<MachineBasicBlock*, 4> LoopHeaders;
56 CodePlacementOpt() : MachineFunctionPass(&ID) {}
58 virtual bool runOnMachineFunction(MachineFunction &MF);
59 virtual const char *getPassName() const {
60 return "Code Placement Optimizater";
63 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
64 AU.addRequired<MachineLoopInfo>();
65 AU.addPreservedID(MachineDominatorsID);
66 MachineFunctionPass::getAnalysisUsage(AU);
70 bool OptimizeIntraLoopEdges();
71 bool AlignLoops(MachineFunction &MF);
74 char CodePlacementOpt::ID = 0;
75 } // end anonymous namespace
77 FunctionPass *llvm::createCodePlacementOptPass() {
78 return new CodePlacementOpt();
81 /// OptimizeBackEdges - Place loop back edges to move unconditional branches
86 /// <fallthrough to B>
88 /// B: --> loop header
90 /// jcc <cond> C, [exit]
102 /// C: --> new loop header
104 /// <fallthough to B>
108 /// jcc <cond> C, [exit]
110 bool CodePlacementOpt::OptimizeIntraLoopEdges() {
111 if (!OptLoopBBPlacement)
114 bool Changed = false;
115 for (unsigned i = 0, e = UncondJmpMBBs.size(); i != e; ++i) {
116 MachineBasicBlock *MBB = UncondJmpMBBs[i].first;
117 MachineBasicBlock *SuccMBB = UncondJmpMBBs[i].second;
118 MachineLoop *L = MLI->getLoopFor(MBB);
119 assert(L && "BB is expected to be in a loop!");
121 if (ChangedMBBs.count(MBB)) {
122 // BB has been modified, re-analyze.
123 MachineBasicBlock *TBB = 0, *FBB = 0;
124 SmallVector<MachineOperand, 4> Cond;
125 if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond) || !Cond.empty())
127 if (MLI->getLoopFor(TBB) != L || TBB->isLandingPad())
131 assert(MLI->getLoopFor(SuccMBB) == L &&
132 "Successor is not in the same loop!");
135 if (MBB->isLayoutSuccessor(SuccMBB)) {
136 // Successor is right after MBB, just eliminate the unconditional jmp.
138 TII->RemoveBranch(*MBB);
139 ChangedMBBs.insert(MBB);
144 // Now check if the predecessor is fallthrough from any BB. If there is,
145 // that BB should be from outside the loop since edge will become a jmp.
146 bool OkToMove = true;
147 MachineBasicBlock *FtMBB = 0, *FtTBB = 0, *FtFBB = 0;
148 SmallVector<MachineOperand, 4> FtCond;
149 for (MachineBasicBlock::pred_iterator PI = SuccMBB->pred_begin(),
150 PE = SuccMBB->pred_end(); PI != PE; ++PI) {
151 MachineBasicBlock *PredMBB = *PI;
152 if (PredMBB->isLayoutSuccessor(SuccMBB)) {
153 if (TII->AnalyzeBranch(*PredMBB, FtTBB, FtFBB, FtCond)) {
160 assert(FtFBB != SuccMBB && "Unexpected control flow!");
166 MachineLoop *PL = MLI->getLoopFor(PredMBB);
167 if (PL && (PL == L || PL->getLoopDepth() >= L->getLoopDepth())) {
177 // Is it profitable? If SuccMBB can fallthrough itself, that can be changed
179 MachineBasicBlock *TBB = 0, *FBB = 0;
180 SmallVector<MachineOperand, 4> Cond;
181 if (TII->AnalyzeBranch(*SuccMBB, TBB, FBB, Cond))
183 if (!TBB && Cond.empty())
184 TBB = next(MachineFunction::iterator(SuccMBB));
185 else if (!FBB && !Cond.empty())
186 FBB = next(MachineFunction::iterator(SuccMBB));
188 // This calculate the cost of the transformation. Also, it finds the *only*
189 // intra-loop edge if there is one.
191 bool HasOneIntraSucc = true;
192 MachineBasicBlock *IntraSucc = 0;
193 for (MachineBasicBlock::succ_iterator SI = SuccMBB->succ_begin(),
194 SE = SuccMBB->succ_end(); SI != SE; ++SI) {
195 MachineBasicBlock *SSMBB = *SI;
196 if (MLI->getLoopFor(SSMBB) == L) {
200 HasOneIntraSucc = false;
203 if (SuccMBB->isLayoutSuccessor(SSMBB))
204 // This will become a jmp.
206 else if (MBB->isLayoutSuccessor(SSMBB))
207 // One of the successor will become the new fallthrough.
211 } else if (!FBB && SSMBB == TBB && Cond.empty()) {
214 } else if (!TII->ReverseBranchCondition(Cond)) {
223 // Now, let's move the successor to below the BB to eliminate the jmp.
224 SuccMBB->moveAfter(MBB);
225 TII->RemoveBranch(*MBB);
226 TII->RemoveBranch(*SuccMBB);
228 TII->InsertBranch(*SuccMBB, TBB, FBB, Cond);
229 ChangedMBBs.insert(MBB);
230 ChangedMBBs.insert(SuccMBB);
232 TII->RemoveBranch(*FtMBB);
233 TII->InsertBranch(*FtMBB, FtTBB, FtFBB, FtCond);
234 ChangedMBBs.insert(FtMBB);
237 // If BB is the loop latch, we may have a new loop headr.
238 if (MBB == L->getLoopLatch()) {
239 assert(MLI->isLoopHeader(SuccMBB) &&
240 "Only succ of loop latch is not the header?");
241 if (HasOneIntraSucc && IntraSucc)
242 std::replace(LoopHeaders.begin(),LoopHeaders.end(), SuccMBB, IntraSucc);
250 /// AlignLoops - Align loop headers to target preferred alignments.
252 bool CodePlacementOpt::AlignLoops(MachineFunction &MF) {
253 const Function *F = MF.getFunction();
254 if (F->hasFnAttr(Attribute::OptimizeForSize))
257 unsigned Align = TLI->getPrefLoopAlignment();
259 return false; // Don't care about loop alignment.
261 // Make sure blocks are numbered in order
264 bool Changed = false;
265 for (unsigned i = 0, e = LoopHeaders.size(); i != e; ++i) {
266 MachineBasicBlock *HeaderMBB = LoopHeaders[i];
267 MachineBasicBlock *PredMBB = prior(MachineFunction::iterator(HeaderMBB));
268 if (MLI->getLoopFor(HeaderMBB) != MLI->getLoopFor(PredMBB)) {
269 // If previously BB is in the same loop, don't align this BB. We want
270 // to prevent adding noop's inside a loop.
271 HeaderMBB->setAlignment(Align);
280 bool CodePlacementOpt::runOnMachineFunction(MachineFunction &MF) {
281 MLI = &getAnalysis<MachineLoopInfo>();
283 return false; // No loops.
285 TLI = MF.getTarget().getTargetLowering();
286 TII = MF.getTarget().getInstrInfo();
288 // Analyze the BBs first and keep track of loop headers and BBs that
289 // end with an unconditional jmp to another block in the same loop.
290 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
291 MachineBasicBlock *MBB = I;
292 if (MBB->isLandingPad())
294 MachineLoop *L = MLI->getLoopFor(MBB);
297 if (MLI->isLoopHeader(MBB))
298 LoopHeaders.push_back(MBB);
300 MachineBasicBlock *TBB = 0, *FBB = 0;
301 SmallVector<MachineOperand, 4> Cond;
302 if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond) || !Cond.empty())
304 if (MLI->getLoopFor(TBB) == L && !TBB->isLandingPad())
305 UncondJmpMBBs.push_back(std::make_pair(MBB, TBB));
308 bool Changed = OptimizeIntraLoopEdges();
310 Changed |= AlignLoops(MF);
313 UncondJmpMBBs.clear();