1 //===-- BasicBlockPlacement.cpp - Basic Block Code Layout optimization ----===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a very simple profile guided basic block placement
11 // algorithm. The idea is to put frequently executed blocks together at the
12 // start of the function, and hopefully increase the number of fall-through
13 // conditional branches. If there is no profile information for a particular
14 // function, this pass basically orders blocks in depth-first order
16 // The algorithm implemented here is basically "Algo1" from "Profile Guided Code
17 // Positioning" by Pettis and Hansen, except that it uses basic block counts
18 // instead of edge counts. This should be improved in many ways, but is very
21 // Basically we "place" the entry block, then loop over all successors in a DFO,
22 // placing the most frequently executed successor until we run out of blocks. I
23 // told you this was _extremely_ simplistic. :) This is also much slower than it
24 // could be. When it becomes important, this pass will be rewritten to use a
25 // better algorithm, and then we can worry about efficiency.
27 //===----------------------------------------------------------------------===//
29 #include "llvm/Analysis/ProfileInfo.h"
30 #include "llvm/Function.h"
31 #include "llvm/Pass.h"
32 #include "llvm/Support/CFG.h"
33 #include "Support/Statistic.h"
38 Statistic<> NumMoved("block-placement", "Number of basic blocks moved");
40 struct BlockPlacement : public FunctionPass {
41 virtual bool runOnFunction(Function &F);
43 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
45 AU.addRequired<ProfileInfo>();
46 //AU.addPreserved<ProfileInfo>(); // Does this work?
49 /// PI - The profile information that is guiding us.
53 /// NumMovedBlocks - Every time we move a block, increment this counter.
55 unsigned NumMovedBlocks;
57 /// PlacedBlocks - Every time we place a block, remember it so we don't get
58 /// into infinite loops.
59 std::set<BasicBlock*> PlacedBlocks;
61 /// InsertPos - This an iterator to the next place we want to insert a
63 Function::iterator InsertPos;
65 /// PlaceBlocks - Recursively place the specified blocks and any unplaced
67 void PlaceBlocks(BasicBlock *BB);
70 RegisterOpt<BlockPlacement> X("block-placement",
71 "Profile Guided Basic Block Placement");
74 bool BlockPlacement::runOnFunction(Function &F) {
75 PI = &getAnalysis<ProfileInfo>();
78 InsertPos = F.begin();
80 // Recursively place all blocks.
81 PlaceBlocks(F.begin());
84 NumMoved += NumMovedBlocks;
85 return NumMovedBlocks != 0;
89 /// PlaceBlocks - Recursively place the specified blocks and any unplaced
91 void BlockPlacement::PlaceBlocks(BasicBlock *BB) {
92 assert(!PlacedBlocks.count(BB) && "Already placed this block!");
93 PlacedBlocks.insert(BB);
95 // Place the specified block.
96 if (&*InsertPos != BB) {
97 // Use splice to move the block into the right place. This avoids having to
98 // remove the block from the function then readd it, which causes a bunch of
99 // symbol table traffic that is entirely pointless.
100 Function::BasicBlockListType &Blocks = BB->getParent()->getBasicBlockList();
101 Blocks.splice(InsertPos, Blocks, BB);
105 // This block is already in the right place, we don't have to do anything.
109 // Keep placing successors until we run out of ones to place. Note that this
110 // loop is very inefficient (N^2) for blocks with many successors, like switch
111 // statements. FIXME!
113 // Okay, now place any unplaced successors.
114 succ_iterator SI = succ_begin(BB), E = succ_end(BB);
116 // Scan for the first unplaced successor.
117 for (; SI != E && PlacedBlocks.count(*SI); ++SI)
119 if (SI == E) return; // No more successors to place.
121 unsigned MaxExecutionCount = PI->getExecutionCount(*SI);
122 BasicBlock *MaxSuccessor = *SI;
124 // Scan for more frequently executed successors
125 for (; SI != E; ++SI)
126 if (!PlacedBlocks.count(*SI)) {
127 unsigned Count = PI->getExecutionCount(*SI);
128 if (Count > MaxExecutionCount ||
129 // Prefer to not disturb the code.
130 (Count == MaxExecutionCount && *SI == &*InsertPos)) {
131 MaxExecutionCount = Count;
136 // Now that we picked the maximally executed successor, place it.
137 PlaceBlocks(MaxSuccessor);