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;
39 CodePlacementOpt() : MachineFunctionPass(&ID) {}
41 virtual bool runOnMachineFunction(MachineFunction &MF);
42 virtual const char *getPassName() const {
43 return "Code Placement Optimizater";
46 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
47 AU.addRequired<MachineLoopInfo>();
48 AU.addPreservedID(MachineDominatorsID);
49 MachineFunctionPass::getAnalysisUsage(AU);
53 bool HasFallthrough(MachineBasicBlock *MBB);
54 bool HasAnalyzableTerminator(MachineBasicBlock *MBB);
55 void Splice(MachineFunction &MF,
56 MachineFunction::iterator InsertPt,
57 MachineFunction::iterator Begin,
58 MachineFunction::iterator End);
59 void UpdateTerminator(MachineBasicBlock *MBB);
60 bool EliminateUnconditionalJumpsToTop(MachineFunction &MF,
62 bool MoveDiscontiguousLoopBlocks(MachineFunction &MF,
64 bool OptimizeIntraLoopEdgesInLoopNest(MachineFunction &MF, MachineLoop *L);
65 bool OptimizeIntraLoopEdges(MachineFunction &MF);
66 bool AlignLoops(MachineFunction &MF);
67 bool AlignLoop(MachineFunction &MF, MachineLoop *L, unsigned Align);
70 char CodePlacementOpt::ID = 0;
71 } // end anonymous namespace
73 FunctionPass *llvm::createCodePlacementOptPass() {
74 return new CodePlacementOpt();
77 /// HasFallthrough - Test whether the given branch has a fallthrough, either as
78 /// a plain fallthrough or as a fallthrough case of a conditional branch.
80 bool CodePlacementOpt::HasFallthrough(MachineBasicBlock *MBB) {
81 MachineBasicBlock *TBB = 0, *FBB = 0;
82 SmallVector<MachineOperand, 4> Cond;
83 if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond))
85 // This conditional branch has no fallthrough.
88 // An unconditional branch has no fallthrough.
89 if (Cond.empty() && TBB)
91 // It has a fallthrough.
95 /// HasAnalyzableTerminator - Test whether AnalyzeBranch will succeed on MBB.
96 /// This is called before major changes are begun to test whether it will be
97 /// possible to complete the changes.
99 /// Target-specific code is hereby encouraged to make AnalyzeBranch succeed
100 /// whenever possible.
102 bool CodePlacementOpt::HasAnalyzableTerminator(MachineBasicBlock *MBB) {
103 // Conservatively ignore EH landing pads.
104 if (MBB->isLandingPad()) return false;
106 // Ignore blocks which look like they might have EH-related control flow.
107 // At the time of this writing, there are blocks which AnalyzeBranch
108 // thinks end in single uncoditional branches, yet which have two CFG
109 // successors. Code in this file is not prepared to reason about such things.
110 if (!MBB->empty() && MBB->back().getOpcode() == TargetInstrInfo::EH_LABEL)
113 // Aggressively handle return blocks and similar constructs.
114 if (MBB->succ_empty()) return true;
116 // Ask the target's AnalyzeBranch if it can handle this block.
117 MachineBasicBlock *TBB = 0, *FBB = 0;
118 SmallVector<MachineOperand, 4> Cond;
119 // Make the the terminator is understood.
120 if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond))
122 // Make sure we have the option of reversing the condition.
123 if (!Cond.empty() && TII->ReverseBranchCondition(Cond))
128 /// Splice - Move the sequence of instructions [Begin,End) to just before
129 /// InsertPt. Update branch instructions as needed to account for broken
130 /// fallthrough edges and to take advantage of newly exposed fallthrough
133 void CodePlacementOpt::Splice(MachineFunction &MF,
134 MachineFunction::iterator InsertPt,
135 MachineFunction::iterator Begin,
136 MachineFunction::iterator End) {
137 assert(Begin != MF.begin() && End != MF.begin() && InsertPt != MF.begin() &&
138 "Splice can't change the entry block!");
139 MachineFunction::iterator OldBeginPrior = prior(Begin);
140 MachineFunction::iterator OldEndPrior = prior(End);
142 MF.splice(InsertPt, Begin, End);
144 UpdateTerminator(prior(Begin));
145 UpdateTerminator(OldBeginPrior);
146 UpdateTerminator(OldEndPrior);
149 /// UpdateTerminator - Update the terminator instructions in MBB to account
150 /// for changes to the layout. If the block previously used a fallthrough,
151 /// it may now need a branch, and if it previously used branching it may now
152 /// be able to use a fallthrough.
154 void CodePlacementOpt::UpdateTerminator(MachineBasicBlock *MBB) {
155 // A block with no successors has no concerns with fall-through edges.
156 if (MBB->succ_empty()) return;
158 MachineBasicBlock *TBB = 0, *FBB = 0;
159 SmallVector<MachineOperand, 4> Cond;
160 bool B = TII->AnalyzeBranch(*MBB, TBB, FBB, Cond);
162 assert(!B && "UpdateTerminators requires analyzable predecessors!");
165 // The block has an unconditional branch. If its successor is now
166 // its layout successor, delete the branch.
167 if (MBB->isLayoutSuccessor(TBB))
168 TII->RemoveBranch(*MBB);
170 // The block has an unconditional fallthrough. If its successor is not
171 // its layout successor, insert a branch.
172 TBB = *MBB->succ_begin();
173 if (!MBB->isLayoutSuccessor(TBB))
174 TII->InsertBranch(*MBB, TBB, 0, Cond);
178 // The block has a non-fallthrough conditional branch. If one of its
179 // successors is its layout successor, rewrite it to a fallthrough
180 // conditional branch.
181 if (MBB->isLayoutSuccessor(TBB)) {
182 TII->RemoveBranch(*MBB);
183 TII->ReverseBranchCondition(Cond);
184 TII->InsertBranch(*MBB, FBB, 0, Cond);
185 } else if (MBB->isLayoutSuccessor(FBB)) {
186 TII->RemoveBranch(*MBB);
187 TII->InsertBranch(*MBB, TBB, 0, Cond);
190 // The block has a fallthrough conditional branch.
191 MachineBasicBlock *MBBA = *MBB->succ_begin();
192 MachineBasicBlock *MBBB = *next(MBB->succ_begin());
193 if (MBBA == TBB) std::swap(MBBB, MBBA);
194 if (MBB->isLayoutSuccessor(TBB)) {
195 TII->RemoveBranch(*MBB);
196 TII->ReverseBranchCondition(Cond);
197 TII->InsertBranch(*MBB, MBBA, 0, Cond);
198 } else if (!MBB->isLayoutSuccessor(MBBA)) {
199 TII->RemoveBranch(*MBB);
200 TII->InsertBranch(*MBB, TBB, MBBA, Cond);
206 /// EliminateUnconditionalJumpsToTop - Move blocks which unconditionally jump
207 /// to the loop top to the top of the loop so that they have a fall through.
208 /// This can introduce a branch on entry to the loop, but it can eliminate a
209 /// branch within the loop. See the @simple case in
210 /// test/CodeGen/X86/loop_blocks.ll for an example of this.
211 bool CodePlacementOpt::EliminateUnconditionalJumpsToTop(MachineFunction &MF,
213 bool Changed = false;
214 MachineBasicBlock *TopMBB = L->getTopBlock();
216 bool BotHasFallthrough = HasFallthrough(L->getBottomBlock());
218 if (TopMBB == MF.begin() ||
219 HasAnalyzableTerminator(prior(MachineFunction::iterator(TopMBB)))) {
221 for (MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin(),
222 PE = TopMBB->pred_end(); PI != PE; ++PI) {
223 MachineBasicBlock *Pred = *PI;
224 if (Pred == TopMBB) continue;
225 if (HasFallthrough(Pred)) continue;
226 if (!L->contains(Pred)) continue;
228 // Verify that we can analyze all the loop entry edges before beginning
229 // any changes which will require us to be able to analyze them.
230 if (Pred == MF.begin())
232 if (!HasAnalyzableTerminator(Pred))
234 if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(Pred))))
240 // Move it and all the blocks that can reach it via fallthrough edges
241 // exclusively, to keep existing fallthrough edges intact.
242 MachineFunction::iterator Begin = Pred;
243 MachineFunction::iterator End = next(Begin);
244 while (Begin != MF.begin()) {
245 MachineFunction::iterator Prior = prior(Begin);
246 if (Prior == MF.begin())
248 // Stop when a non-fallthrough edge is found.
249 if (!HasFallthrough(Prior))
251 // Stop if a block which could fall-through out of the loop is found.
252 if (Prior->isSuccessor(End))
254 // If we've reached the top, stop scanning.
255 if (Prior == MachineFunction::iterator(TopMBB)) {
256 // We know top currently has a fall through (because we just checked
257 // it) which would be lost if we do the transformation, so it isn't
258 // worthwhile to do the transformation unless it would expose a new
260 if (!Prior->isSuccessor(End))
262 // Otherwise we can stop scanning and procede to move the blocks.
265 // If we hit a switch or something complicated, don't move anything
266 // for this predecessor.
267 if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(Prior))))
269 // Ok, the block prior to Begin will be moved along with the rest.
270 // Extend the range to include it.
276 Splice(MF, TopMBB, Begin, End);
279 TopMBB = L->getTopBlock();
281 // We have a new loop top. Iterate on it. We shouldn't have to do this
282 // too many times if BranchFolding has done a reasonable job.
288 // If the loop previously didn't exit with a fall-through and it now does,
289 // we eliminated a branch.
291 !BotHasFallthrough &&
292 HasFallthrough(L->getBottomBlock())) {
294 BotHasFallthrough = true;
300 /// MoveDiscontiguousLoopBlocks - Move any loop blocks that are not in the
301 /// portion of the loop contiguous with the header. This usually makes the loop
302 /// contiguous, provided that AnalyzeBranch can handle all the relevant
303 /// branching. See the @cfg_islands case in test/CodeGen/X86/loop_blocks.ll
304 /// for an example of this.
305 bool CodePlacementOpt::MoveDiscontiguousLoopBlocks(MachineFunction &MF,
307 bool Changed = false;
308 MachineBasicBlock *TopMBB = L->getTopBlock();
309 MachineBasicBlock *BotMBB = L->getBottomBlock();
311 // Determine a position to move orphaned loop blocks to. If TopMBB is not
312 // entered via fallthrough and BotMBB is exited via fallthrough, prepend them
313 // to the top of the loop to avoid loosing that fallthrough. Otherwise append
314 // them to the bottom, even if it previously had a fallthrough, on the theory
315 // that it's worth an extra branch to keep the loop contiguous.
316 MachineFunction::iterator InsertPt = next(MachineFunction::iterator(BotMBB));
317 bool InsertAtTop = false;
318 if (TopMBB != MF.begin() &&
319 !HasFallthrough(prior(MachineFunction::iterator(TopMBB))) &&
320 HasFallthrough(BotMBB)) {
325 // Keep a record of which blocks are in the portion of the loop contiguous
326 // with the loop header.
327 SmallPtrSet<MachineBasicBlock *, 8> ContiguousBlocks;
328 for (MachineFunction::iterator I = TopMBB,
329 E = next(MachineFunction::iterator(BotMBB)); I != E; ++I)
330 ContiguousBlocks.insert(I);
332 // Find non-contigous blocks and fix them.
333 if (InsertPt != MF.begin() && HasAnalyzableTerminator(prior(InsertPt)))
334 for (MachineLoop::block_iterator BI = L->block_begin(), BE = L->block_end();
336 MachineBasicBlock *BB = *BI;
338 // Verify that we can analyze all the loop entry edges before beginning
339 // any changes which will require us to be able to analyze them.
340 if (!HasAnalyzableTerminator(BB))
342 if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(BB))))
345 // If the layout predecessor is part of the loop, this block will be
346 // processed along with it. This keeps them in their relative order.
347 if (BB != MF.begin() &&
348 L->contains(prior(MachineFunction::iterator(BB))))
351 // Check to see if this block is already contiguous with the main
352 // portion of the loop.
353 if (!ContiguousBlocks.insert(BB))
359 // Process this block and all loop blocks contiguous with it, to keep
360 // them in their relative order.
361 MachineFunction::iterator Begin = BB;
362 MachineFunction::iterator End = next(MachineFunction::iterator(BB));
363 for (; End != MF.end(); ++End) {
364 if (!L->contains(End)) break;
365 if (!HasAnalyzableTerminator(End)) break;
366 ContiguousBlocks.insert(End);
370 // If we're inserting at the bottom of the loop, and the code we're
371 // moving originally had fall-through successors, bring the sucessors
372 // up with the loop blocks to preserve the fall-through edges.
374 for (; End != MF.end(); ++End) {
375 if (L->contains(End)) break;
376 if (!HasAnalyzableTerminator(End)) break;
377 if (!HasFallthrough(prior(End))) break;
380 // Move the blocks. This may invalidate TopMBB and/or BotMBB, but
381 // we don't need them anymore at this point.
382 Splice(MF, InsertPt, Begin, End);
388 /// OptimizeIntraLoopEdgesInLoopNest - Reposition loop blocks to minimize
389 /// intra-loop branching and to form contiguous loops.
391 /// This code takes the approach of making minor changes to the existing
392 /// layout to fix specific loop-oriented problems. Also, it depends on
393 /// AnalyzeBranch, which can't understand complex control instructions.
395 bool CodePlacementOpt::OptimizeIntraLoopEdgesInLoopNest(MachineFunction &MF,
397 bool Changed = false;
399 // Do optimization for nested loops.
400 for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
401 Changed |= OptimizeIntraLoopEdgesInLoopNest(MF, *I);
403 // Do optimization for this loop.
404 Changed |= EliminateUnconditionalJumpsToTop(MF, L);
405 Changed |= MoveDiscontiguousLoopBlocks(MF, L);
410 /// OptimizeIntraLoopEdges - Reposition loop blocks to minimize
411 /// intra-loop branching and to form contiguous loops.
413 bool CodePlacementOpt::OptimizeIntraLoopEdges(MachineFunction &MF) {
414 bool Changed = false;
416 if (!TLI->shouldOptimizeCodePlacement())
419 // Do optimization for each loop in the function.
420 for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
422 if (!(*I)->getParentLoop())
423 Changed |= OptimizeIntraLoopEdgesInLoopNest(MF, *I);
428 /// AlignLoops - Align loop headers to target preferred alignments.
430 bool CodePlacementOpt::AlignLoops(MachineFunction &MF) {
431 const Function *F = MF.getFunction();
432 if (F->hasFnAttr(Attribute::OptimizeForSize))
435 unsigned Align = TLI->getPrefLoopAlignment();
437 return false; // Don't care about loop alignment.
439 bool Changed = false;
441 for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
443 Changed |= AlignLoop(MF, *I, Align);
448 /// AlignLoop - Align loop headers to target preferred alignments.
450 bool CodePlacementOpt::AlignLoop(MachineFunction &MF, MachineLoop *L,
452 bool Changed = false;
454 // Do alignment for nested loops.
455 for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
456 Changed |= AlignLoop(MF, *I, Align);
458 L->getTopBlock()->setAlignment(Align);
465 bool CodePlacementOpt::runOnMachineFunction(MachineFunction &MF) {
466 MLI = &getAnalysis<MachineLoopInfo>();
468 return false; // No loops.
470 TLI = MF.getTarget().getTargetLowering();
471 TII = MF.getTarget().getInstrInfo();
473 bool Changed = OptimizeIntraLoopEdges(MF);
475 Changed |= AlignLoops(MF);