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 OptimizeIntraLoopEdges(MachineFunction &MF);
61 bool OptimizeIntraLoopEdgesInLoop(MachineFunction &MF, MachineLoop *L);
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 /// 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 // Ignore blocks which look like they might have EH-related control flow.
103 // At the time of this writing, there are blocks which AnalyzeBranch
104 // thinks end in single uncoditional branches, yet which have two CFG
105 // successors. Code in this file is not prepared to reason about such things.
106 if (!MBB->empty() && MBB->back().getOpcode() == TargetInstrInfo::EH_LABEL)
109 // Aggressively handle return blocks and similar constructs.
110 if (MBB->succ_empty()) return true;
112 // Ask the target's AnalyzeBranch if it can handle this block.
113 MachineBasicBlock *TBB = 0, *FBB = 0;
114 SmallVector<MachineOperand, 4> Cond;
115 // Make the the terminator is understood.
116 if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond))
118 // Make sure we have the option of reversing the condition.
119 if (!Cond.empty() && TII->ReverseBranchCondition(Cond))
124 /// Splice - Move the sequence of instructions [Begin,End) to just before
125 /// InsertPt. Update branch instructions as needed to account for broken
126 /// fallthrough edges and to take advantage of newly exposed fallthrough
129 void CodePlacementOpt::Splice(MachineFunction &MF,
130 MachineFunction::iterator InsertPt,
131 MachineFunction::iterator Begin,
132 MachineFunction::iterator End) {
133 assert(Begin != MF.begin() && End != MF.begin() && InsertPt != MF.begin() &&
134 "Splice can't change the entry block!");
135 MachineFunction::iterator OldBeginPrior = prior(Begin);
136 MachineFunction::iterator OldEndPrior = prior(End);
138 MF.splice(InsertPt, Begin, End);
140 UpdateTerminator(prior(Begin));
141 UpdateTerminator(OldBeginPrior);
142 UpdateTerminator(OldEndPrior);
145 /// UpdateTerminator - Update the terminator instructions in MBB to account
146 /// for changes to the layout. If the block previously used a fallthrough,
147 /// it may now need a branch, and if it previously used branching it may now
148 /// be able to use a fallthrough.
150 void CodePlacementOpt::UpdateTerminator(MachineBasicBlock *MBB) {
151 // A block with no successors has no concerns with fall-through edges.
152 if (MBB->succ_empty()) return;
154 MachineBasicBlock *TBB = 0, *FBB = 0;
155 SmallVector<MachineOperand, 4> Cond;
156 bool B = TII->AnalyzeBranch(*MBB, TBB, FBB, Cond);
157 assert(!B && "UpdateTerminators requires analyzable predecessors!");
160 // The block has an unconditional branch. If its successor is now
161 // its layout successor, delete the branch.
162 if (MBB->isLayoutSuccessor(TBB))
163 TII->RemoveBranch(*MBB);
165 // The block has an unconditional fallthrough. If its successor is not
166 // its layout successor, insert a branch.
167 TBB = *MBB->succ_begin();
168 if (!MBB->isLayoutSuccessor(TBB))
169 TII->InsertBranch(*MBB, TBB, 0, Cond);
173 // The block has a non-fallthrough conditional branch. If one of its
174 // successors is its layout successor, rewrite it to a fallthrough
175 // conditional branch.
176 if (MBB->isLayoutSuccessor(TBB)) {
177 TII->RemoveBranch(*MBB);
178 TII->ReverseBranchCondition(Cond);
179 TII->InsertBranch(*MBB, FBB, 0, Cond);
180 } else if (MBB->isLayoutSuccessor(FBB)) {
181 TII->RemoveBranch(*MBB);
182 TII->InsertBranch(*MBB, TBB, 0, Cond);
185 // The block has a fallthrough conditional branch.
186 MachineBasicBlock *MBBA = *MBB->succ_begin();
187 MachineBasicBlock *MBBB = *next(MBB->succ_begin());
188 if (MBBA == TBB) std::swap(MBBB, MBBA);
189 if (MBB->isLayoutSuccessor(TBB)) {
190 TII->RemoveBranch(*MBB);
191 TII->ReverseBranchCondition(Cond);
192 TII->InsertBranch(*MBB, MBBA, 0, Cond);
193 } else if (!MBB->isLayoutSuccessor(MBBA)) {
194 TII->RemoveBranch(*MBB);
195 TII->InsertBranch(*MBB, TBB, MBBA, Cond);
201 /// OptimizeIntraLoopEdges - Reposition loop blocks to minimize
202 /// intra-loop branching and to form contiguous loops.
204 bool CodePlacementOpt::OptimizeIntraLoopEdges(MachineFunction &MF) {
205 bool Changed = false;
207 if (!TLI->shouldOptimizeCodePlacement())
210 for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
212 Changed |= OptimizeIntraLoopEdgesInLoop(MF, *I);
217 /// OptimizeIntraLoopEdgesInLoop - Reposition loop blocks to minimize
218 /// intra-loop branching and to form contiguous loops.
220 /// This code takes the approach of making minor changes to the existing
221 /// layout to fix specific loop-oriented problems. Also, it depends on
222 /// AnalyzeBranch, which can't understand complex control instructions.
224 bool CodePlacementOpt::OptimizeIntraLoopEdgesInLoop(MachineFunction &MF,
226 bool Changed = false;
228 // Do optimization for nested loops.
229 for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
230 Changed |= OptimizeIntraLoopEdgesInLoop(MF, *I);
232 // Keep a record of which blocks are in the portion of the loop contiguous
233 // with the loop header.
234 SmallPtrSet<MachineBasicBlock *, 8> ContiguousBlocks;
235 ContiguousBlocks.insert(L->getHeader());
237 // Find the loop "top", ignoring any discontiguous parts.
238 MachineBasicBlock *TopMBB = L->getHeader();
239 if (TopMBB != MF.begin()) {
240 MachineBasicBlock *PriorMBB = prior(MachineFunction::iterator(TopMBB));
241 while (L->contains(PriorMBB)) {
242 ContiguousBlocks.insert(PriorMBB);
244 if (TopMBB == MF.begin()) break;
245 PriorMBB = prior(MachineFunction::iterator(TopMBB));
249 // Find the loop "bottom", ignoring any discontiguous parts.
250 MachineBasicBlock *BotMBB = L->getHeader();
251 if (BotMBB != prior(MF.end())) {
252 MachineBasicBlock *NextMBB = next(MachineFunction::iterator(BotMBB));
253 while (L->contains(NextMBB)) {
254 ContiguousBlocks.insert(NextMBB);
256 if (BotMBB == next(MachineFunction::iterator(BotMBB))) break;
257 NextMBB = next(MachineFunction::iterator(BotMBB));
261 // First, move blocks which unconditionally jump to the loop top to the
262 // top of the loop so that they have a fall through. This can introduce a
263 // branch on entry to the loop, but it can eliminate a branch within the
264 // loop. See the @simple case in test/CodeGen/X86/loop_blocks.ll for an
267 bool BotHasFallthrough = HasFallthrough(BotMBB);
269 if (TopMBB == MF.begin() ||
270 HasAnalyzableTerminator(prior(MachineFunction::iterator(TopMBB)))) {
272 for (MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin(),
273 PE = TopMBB->pred_end(); PI != PE; ++PI) {
274 MachineBasicBlock *Pred = *PI;
275 if (Pred == TopMBB) continue;
276 if (HasFallthrough(Pred)) continue;
277 if (!L->contains(Pred)) continue;
279 // Verify that we can analyze all the loop entry edges before beginning
280 // any changes which will require us to be able to analyze them.
281 if (Pred == MF.begin())
283 if (!HasAnalyzableTerminator(Pred))
285 if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(Pred))))
290 ContiguousBlocks.insert(Pred);
292 // Move it and all the blocks that can reach it via fallthrough edges
293 // exclusively, to keep existing fallthrough-edges intact.
294 MachineFunction::iterator Begin = Pred;
295 MachineFunction::iterator End = next(Begin);
296 while (Begin != MF.begin()) {
297 MachineFunction::iterator Prior = prior(Begin);
298 if (Prior == MF.begin())
300 // Stop when a non-fallthrough edge is found.
301 if (!HasFallthrough(Prior))
303 // Stop if a block which could fall-through out of the loop is found.
304 if (Prior->isSuccessor(End))
306 // If we've reached the top, stop scanning.
307 if (Prior == MachineFunction::iterator(TopMBB)) {
308 // We know top currently has a fall through (because we just checked
309 // it) which would be lost if we do the transformation, so it isn't
310 // worthwhile to do the transformation unless it would expose a new
312 if (!Prior->isSuccessor(End))
314 // Otherwise we can stop scanning and procede to move the blocks.
317 // If we hit a switch or something complicated, don't move anything
318 // for this predecessor.
319 if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(Prior))))
322 ContiguousBlocks.insert(Begin);
326 // Update BotMBB, before moving Begin/End around and forgetting where
327 // the new bottom is.
328 if (BotMBB == prior(End))
329 BotMBB = prior(Begin);
332 Splice(MF, TopMBB, Begin, End);
334 // Update TopMBB, now that all the updates requiring the old top are
338 // We have a new loop top. Iterate on it. We shouldn't have to do this
339 // too many times if BranchFolding has done a reasonable job.
345 // If the loop previously didn't exit with a fall-through and it now does,
346 // we eliminated a branch.
347 if (!BotHasFallthrough && HasFallthrough(BotMBB)) {
349 BotHasFallthrough = true;
352 // Next, move any loop blocks that are not in the portion of the loop
353 // contiguous with the header. This makes the loop contiguous, provided that
354 // AnalyzeBranch can handle all the relevant branching. See the @cfg_islands
355 // case in test/CodeGen/X86/loop_blocks.ll for an example of this.
357 // Determine a position to move orphaned loop blocks to. If TopMBB is not
358 // entered via fallthrough and BotMBB is exited via fallthrough, prepend them
359 // to the top of the loop to avoid loosing that fallthrough. Otherwise append
360 // them to the bottom, even if it previously had a fallthrough, on the theory
361 // that it's worth an extra branch to keep the loop contiguous.
362 MachineFunction::iterator InsertPt = next(MachineFunction::iterator(BotMBB));
363 bool InsertAtTop = false;
364 if (TopMBB != MF.begin() &&
365 !HasFallthrough(prior(MachineFunction::iterator(TopMBB))) &&
366 HasFallthrough(BotMBB)) {
371 // Find non-contigous blocks and fix them.
372 if (InsertPt != MF.begin() && HasAnalyzableTerminator(prior(InsertPt)))
373 for (MachineLoop::block_iterator BI = L->block_begin(), BE = L->block_end();
375 MachineBasicBlock *BB = *BI;
377 // Verify that we can analyze all the loop entry edges before beginning
378 // any changes which will require us to be able to analyze them.
379 if (!HasAnalyzableTerminator(BB))
381 if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(BB))))
384 // If the layout predecessor is part of the loop, this block will be
385 // processed along with it. This keeps them in their relative order.
386 if (BB != MF.begin() &&
387 L->contains(prior(MachineFunction::iterator(BB))))
390 // Check to see if this block is already contiguous with the main
391 // portion of the loop.
392 if (!ContiguousBlocks.insert(BB))
398 // Process this block and all loop blocks contiguous with it, to keep
399 // them in their relative order.
400 MachineFunction::iterator Begin = BB;
401 MachineFunction::iterator End = next(MachineFunction::iterator(BB));
402 for (; End != MF.end(); ++End) {
403 if (!L->contains(End)) break;
404 if (!HasAnalyzableTerminator(End)) break;
405 ContiguousBlocks.insert(End);
413 // If we're inserting at the bottom of the loop, and the code we're
414 // moving originally had fall-through successors, bring the sucessors
415 // up with the loop blocks to preserve the fall-through edges.
417 for (; End != MF.end(); ++End) {
418 if (L->contains(End)) break;
419 if (!HasAnalyzableTerminator(End)) break;
420 if (!HasFallthrough(prior(End))) break;
424 Splice(MF, InsertPt, Begin, End);
434 /// AlignLoops - Align loop headers to target preferred alignments.
436 bool CodePlacementOpt::AlignLoops(MachineFunction &MF) {
437 const Function *F = MF.getFunction();
438 if (F->hasFnAttr(Attribute::OptimizeForSize))
441 unsigned Align = TLI->getPrefLoopAlignment();
443 return false; // Don't care about loop alignment.
445 bool Changed = false;
447 for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
449 Changed |= AlignLoop(MF, *I, Align);
454 /// AlignLoop - Align loop headers to target preferred alignments.
456 bool CodePlacementOpt::AlignLoop(MachineFunction &MF, MachineLoop *L,
458 bool Changed = false;
460 // Do alignment for nested loops.
461 for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
462 Changed |= AlignLoop(MF, *I, Align);
464 MachineBasicBlock *TopMBB = L->getHeader();
465 if (TopMBB != MF.begin()) {
466 MachineBasicBlock *PredMBB = prior(MachineFunction::iterator(TopMBB));
467 while (L->contains(PredMBB)) {
469 if (TopMBB == MF.begin()) break;
470 PredMBB = prior(MachineFunction::iterator(TopMBB));
474 TopMBB->setAlignment(Align);
481 bool CodePlacementOpt::runOnMachineFunction(MachineFunction &MF) {
482 MLI = &getAnalysis<MachineLoopInfo>();
484 return false; // No loops.
486 TLI = MF.getTarget().getTargetLowering();
487 TII = MF.getTarget().getInstrInfo();
489 bool Changed = OptimizeIntraLoopEdges(MF);
491 Changed |= AlignLoops(MF);