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 optimizes code placement and aligns loop
11 // headers to target-specific alignment boundaries.
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);
43 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
44 AU.addRequired<MachineLoopInfo>();
45 AU.addPreservedID(MachineDominatorsID);
46 MachineFunctionPass::getAnalysisUsage(AU);
50 bool HasFallthrough(MachineBasicBlock *MBB);
51 bool HasAnalyzableTerminator(MachineBasicBlock *MBB);
52 void Splice(MachineFunction &MF,
53 MachineFunction::iterator InsertPt,
54 MachineFunction::iterator Begin,
55 MachineFunction::iterator End);
56 bool EliminateUnconditionalJumpsToTop(MachineFunction &MF,
58 bool MoveDiscontiguousLoopBlocks(MachineFunction &MF,
60 bool OptimizeIntraLoopEdgesInLoopNest(MachineFunction &MF, MachineLoop *L);
61 bool OptimizeIntraLoopEdges(MachineFunction &MF);
62 bool AlignLoops(MachineFunction &MF);
63 bool AlignLoop(MachineFunction &MF, MachineLoop *L, unsigned Align);
66 char CodePlacementOpt::ID = 0;
67 } // end anonymous namespace
69 char &llvm::CodePlacementOptID = CodePlacementOpt::ID;
70 INITIALIZE_PASS(CodePlacementOpt, "code-placement",
71 "Code Placement Optimizer", false, false)
73 /// HasFallthrough - Test whether the given branch has a fallthrough, either as
74 /// a plain fallthrough or as a fallthrough case of a conditional branch.
76 bool CodePlacementOpt::HasFallthrough(MachineBasicBlock *MBB) {
77 MachineBasicBlock *TBB = 0, *FBB = 0;
78 SmallVector<MachineOperand, 4> Cond;
79 if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond))
81 // This conditional branch has no fallthrough.
84 // An unconditional branch has no fallthrough.
85 if (Cond.empty() && TBB)
87 // It has a fallthrough.
91 /// HasAnalyzableTerminator - Test whether AnalyzeBranch will succeed on MBB.
92 /// This is called before major changes are begun to test whether it will be
93 /// possible to complete the changes.
95 /// Target-specific code is hereby encouraged to make AnalyzeBranch succeed
96 /// whenever possible.
98 bool CodePlacementOpt::HasAnalyzableTerminator(MachineBasicBlock *MBB) {
99 // Conservatively ignore EH landing pads.
100 if (MBB->isLandingPad()) return false;
102 // Aggressively handle return blocks and similar constructs.
103 if (MBB->succ_empty()) return true;
105 // Ask the target's AnalyzeBranch if it can handle this block.
106 MachineBasicBlock *TBB = 0, *FBB = 0;
107 SmallVector<MachineOperand, 4> Cond;
108 // Make sure the terminator is understood.
109 if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond))
111 // Ignore blocks which look like they might have EH-related control flow.
112 // AnalyzeBranch thinks it knows how to analyze such things, but it doesn't
113 // recognize the possibility of a control transfer through an unwind.
114 // Such blocks contain EH_LABEL instructions, however they may be in the
115 // middle of the block. Instead of searching for them, just check to see
116 // if the CFG disagrees with AnalyzeBranch.
117 if (1u + !Cond.empty() != MBB->succ_size())
119 // Make sure we have the option of reversing the condition.
120 if (!Cond.empty() && TII->ReverseBranchCondition(Cond))
125 /// Splice - Move the sequence of instructions [Begin,End) to just before
126 /// InsertPt. Update branch instructions as needed to account for broken
127 /// fallthrough edges and to take advantage of newly exposed fallthrough
130 void CodePlacementOpt::Splice(MachineFunction &MF,
131 MachineFunction::iterator InsertPt,
132 MachineFunction::iterator Begin,
133 MachineFunction::iterator End) {
134 assert(Begin != MF.begin() && End != MF.begin() && InsertPt != MF.begin() &&
135 "Splice can't change the entry block!");
136 MachineFunction::iterator OldBeginPrior = prior(Begin);
137 MachineFunction::iterator OldEndPrior = prior(End);
139 MF.splice(InsertPt, Begin, End);
141 prior(Begin)->updateTerminator();
142 OldBeginPrior->updateTerminator();
143 OldEndPrior->updateTerminator();
146 /// EliminateUnconditionalJumpsToTop - Move blocks which unconditionally jump
147 /// to the loop top to the top of the loop so that they have a fall through.
148 /// This can introduce a branch on entry to the loop, but it can eliminate a
149 /// branch within the loop. See the @simple case in
150 /// test/CodeGen/X86/loop_blocks.ll for an example of this.
151 bool CodePlacementOpt::EliminateUnconditionalJumpsToTop(MachineFunction &MF,
153 bool Changed = false;
154 MachineBasicBlock *TopMBB = L->getTopBlock();
156 bool BotHasFallthrough = HasFallthrough(L->getBottomBlock());
158 if (TopMBB == MF.begin() ||
159 HasAnalyzableTerminator(prior(MachineFunction::iterator(TopMBB)))) {
161 for (MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin(),
162 PE = TopMBB->pred_end(); PI != PE; ++PI) {
163 MachineBasicBlock *Pred = *PI;
164 if (Pred == TopMBB) continue;
165 if (HasFallthrough(Pred)) continue;
166 if (!L->contains(Pred)) continue;
168 // Verify that we can analyze all the loop entry edges before beginning
169 // any changes which will require us to be able to analyze them.
170 if (Pred == MF.begin())
172 if (!HasAnalyzableTerminator(Pred))
174 if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(Pred))))
178 DEBUG(dbgs() << "CGP: Moving blocks starting at BB#" << Pred->getNumber()
179 << " to top of loop.\n");
182 // Move it and all the blocks that can reach it via fallthrough edges
183 // exclusively, to keep existing fallthrough edges intact.
184 MachineFunction::iterator Begin = Pred;
185 MachineFunction::iterator End = llvm::next(Begin);
186 while (Begin != MF.begin()) {
187 MachineFunction::iterator Prior = prior(Begin);
188 if (Prior == MF.begin())
190 // Stop when a non-fallthrough edge is found.
191 if (!HasFallthrough(Prior))
193 // Stop if a block which could fall-through out of the loop is found.
194 if (Prior->isSuccessor(End))
196 // If we've reached the top, stop scanning.
197 if (Prior == MachineFunction::iterator(TopMBB)) {
198 // We know top currently has a fall through (because we just checked
199 // it) which would be lost if we do the transformation, so it isn't
200 // worthwhile to do the transformation unless it would expose a new
202 if (!Prior->isSuccessor(End))
204 // Otherwise we can stop scanning and procede to move the blocks.
207 // If we hit a switch or something complicated, don't move anything
208 // for this predecessor.
209 if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(Prior))))
211 // Ok, the block prior to Begin will be moved along with the rest.
212 // Extend the range to include it.
218 Splice(MF, TopMBB, Begin, End);
221 TopMBB = L->getTopBlock();
223 // We have a new loop top. Iterate on it. We shouldn't have to do this
224 // too many times if BranchFolding has done a reasonable job.
230 // If the loop previously didn't exit with a fall-through and it now does,
231 // we eliminated a branch.
233 !BotHasFallthrough &&
234 HasFallthrough(L->getBottomBlock())) {
241 /// MoveDiscontiguousLoopBlocks - Move any loop blocks that are not in the
242 /// portion of the loop contiguous with the header. This usually makes the loop
243 /// contiguous, provided that AnalyzeBranch can handle all the relevant
244 /// branching. See the @cfg_islands case in test/CodeGen/X86/loop_blocks.ll
245 /// for an example of this.
246 bool CodePlacementOpt::MoveDiscontiguousLoopBlocks(MachineFunction &MF,
248 bool Changed = false;
249 MachineBasicBlock *TopMBB = L->getTopBlock();
250 MachineBasicBlock *BotMBB = L->getBottomBlock();
252 // Determine a position to move orphaned loop blocks to. If TopMBB is not
253 // entered via fallthrough and BotMBB is exited via fallthrough, prepend them
254 // to the top of the loop to avoid losing that fallthrough. Otherwise append
255 // them to the bottom, even if it previously had a fallthrough, on the theory
256 // that it's worth an extra branch to keep the loop contiguous.
257 MachineFunction::iterator InsertPt =
258 llvm::next(MachineFunction::iterator(BotMBB));
259 bool InsertAtTop = false;
260 if (TopMBB != MF.begin() &&
261 !HasFallthrough(prior(MachineFunction::iterator(TopMBB))) &&
262 HasFallthrough(BotMBB)) {
267 // Keep a record of which blocks are in the portion of the loop contiguous
268 // with the loop header.
269 SmallPtrSet<MachineBasicBlock *, 8> ContiguousBlocks;
270 for (MachineFunction::iterator I = TopMBB,
271 E = llvm::next(MachineFunction::iterator(BotMBB)); I != E; ++I)
272 ContiguousBlocks.insert(I);
274 // Find non-contigous blocks and fix them.
275 if (InsertPt != MF.begin() && HasAnalyzableTerminator(prior(InsertPt)))
276 for (MachineLoop::block_iterator BI = L->block_begin(), BE = L->block_end();
278 MachineBasicBlock *BB = *BI;
280 // Verify that we can analyze all the loop entry edges before beginning
281 // any changes which will require us to be able to analyze them.
282 if (!HasAnalyzableTerminator(BB))
284 if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(BB))))
287 // If the layout predecessor is part of the loop, this block will be
288 // processed along with it. This keeps them in their relative order.
289 if (BB != MF.begin() &&
290 L->contains(prior(MachineFunction::iterator(BB))))
293 // Check to see if this block is already contiguous with the main
294 // portion of the loop.
295 if (!ContiguousBlocks.insert(BB))
299 DEBUG(dbgs() << "CGP: Moving blocks starting at BB#" << BB->getNumber()
300 << " to be contiguous with loop.\n");
303 // Process this block and all loop blocks contiguous with it, to keep
304 // them in their relative order.
305 MachineFunction::iterator Begin = BB;
306 MachineFunction::iterator End = llvm::next(MachineFunction::iterator(BB));
307 for (; End != MF.end(); ++End) {
308 if (!L->contains(End)) break;
309 if (!HasAnalyzableTerminator(End)) break;
310 ContiguousBlocks.insert(End);
314 // If we're inserting at the bottom of the loop, and the code we're
315 // moving originally had fall-through successors, bring the sucessors
316 // up with the loop blocks to preserve the fall-through edges.
318 for (; End != MF.end(); ++End) {
319 if (L->contains(End)) break;
320 if (!HasAnalyzableTerminator(End)) break;
321 if (!HasFallthrough(prior(End))) break;
324 // Move the blocks. This may invalidate TopMBB and/or BotMBB, but
325 // we don't need them anymore at this point.
326 Splice(MF, InsertPt, Begin, End);
332 /// OptimizeIntraLoopEdgesInLoopNest - Reposition loop blocks to minimize
333 /// intra-loop branching and to form contiguous loops.
335 /// This code takes the approach of making minor changes to the existing
336 /// layout to fix specific loop-oriented problems. Also, it depends on
337 /// AnalyzeBranch, which can't understand complex control instructions.
339 bool CodePlacementOpt::OptimizeIntraLoopEdgesInLoopNest(MachineFunction &MF,
341 bool Changed = false;
343 // Do optimization for nested loops.
344 for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
345 Changed |= OptimizeIntraLoopEdgesInLoopNest(MF, *I);
347 // Do optimization for this loop.
348 Changed |= EliminateUnconditionalJumpsToTop(MF, L);
349 Changed |= MoveDiscontiguousLoopBlocks(MF, L);
354 /// OptimizeIntraLoopEdges - Reposition loop blocks to minimize
355 /// intra-loop branching and to form contiguous loops.
357 bool CodePlacementOpt::OptimizeIntraLoopEdges(MachineFunction &MF) {
358 bool Changed = false;
360 if (!TLI->shouldOptimizeCodePlacement())
363 // Do optimization for each loop in the function.
364 for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
366 if (!(*I)->getParentLoop())
367 Changed |= OptimizeIntraLoopEdgesInLoopNest(MF, *I);
372 /// AlignLoops - Align loop headers to target preferred alignments.
374 bool CodePlacementOpt::AlignLoops(MachineFunction &MF) {
375 const Function *F = MF.getFunction();
376 if (F->hasFnAttr(Attribute::OptimizeForSize))
379 unsigned Align = TLI->getPrefLoopAlignment();
381 return false; // Don't care about loop alignment.
383 bool Changed = false;
385 for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
387 Changed |= AlignLoop(MF, *I, Align);
392 /// AlignLoop - Align loop headers to target preferred alignments.
394 bool CodePlacementOpt::AlignLoop(MachineFunction &MF, MachineLoop *L,
396 bool Changed = false;
398 // Do alignment for nested loops.
399 for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
400 Changed |= AlignLoop(MF, *I, Align);
402 L->getTopBlock()->setAlignment(Align);
409 bool CodePlacementOpt::runOnMachineFunction(MachineFunction &MF) {
410 MLI = &getAnalysis<MachineLoopInfo>();
412 return false; // No loops.
414 TLI = MF.getTarget().getTargetLowering();
415 TII = MF.getTarget().getInstrInfo();
417 bool Changed = OptimizeIntraLoopEdges(MF);
419 Changed |= AlignLoops(MF);