• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===-- BasicBlockPlacement.cpp - Basic Block Code Layout optimization ----===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
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
15 //
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
19 // simple for now.
20 //
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.
26 //
27 //===----------------------------------------------------------------------===//
28 
29 #define DEBUG_TYPE "block-placement"
30 #include "llvm/Transforms/Scalar.h"
31 #include "llvm/ADT/Statistic.h"
32 #include "llvm/Analysis/ProfileInfo.h"
33 #include "llvm/IR/Function.h"
34 #include "llvm/Pass.h"
35 #include "llvm/Support/CFG.h"
36 #include <set>
37 using namespace llvm;
38 
39 STATISTIC(NumMoved, "Number of basic blocks moved");
40 
41 namespace {
42   struct BlockPlacement : public FunctionPass {
43     static char ID; // Pass identification, replacement for typeid
BlockPlacement__anon65958ee50111::BlockPlacement44     BlockPlacement() : FunctionPass(ID) {
45       initializeBlockPlacementPass(*PassRegistry::getPassRegistry());
46     }
47 
48     virtual bool runOnFunction(Function &F);
49 
getAnalysisUsage__anon65958ee50111::BlockPlacement50     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
51       AU.setPreservesCFG();
52       AU.addRequired<ProfileInfo>();
53       //AU.addPreserved<ProfileInfo>();  // Does this work?
54     }
55   private:
56     /// PI - The profile information that is guiding us.
57     ///
58     ProfileInfo *PI;
59 
60     /// NumMovedBlocks - Every time we move a block, increment this counter.
61     ///
62     unsigned NumMovedBlocks;
63 
64     /// PlacedBlocks - Every time we place a block, remember it so we don't get
65     /// into infinite loops.
66     std::set<BasicBlock*> PlacedBlocks;
67 
68     /// InsertPos - This an iterator to the next place we want to insert a
69     /// block.
70     Function::iterator InsertPos;
71 
72     /// PlaceBlocks - Recursively place the specified blocks and any unplaced
73     /// successors.
74     void PlaceBlocks(BasicBlock *BB);
75   };
76 }
77 
78 char BlockPlacement::ID = 0;
79 INITIALIZE_PASS_BEGIN(BlockPlacement, "block-placement",
80                 "Profile Guided Basic Block Placement", false, false)
INITIALIZE_AG_DEPENDENCY(ProfileInfo)81 INITIALIZE_AG_DEPENDENCY(ProfileInfo)
82 INITIALIZE_PASS_END(BlockPlacement, "block-placement",
83                 "Profile Guided Basic Block Placement", false, false)
84 
85 FunctionPass *llvm::createBlockPlacementPass() { return new BlockPlacement(); }
86 
runOnFunction(Function & F)87 bool BlockPlacement::runOnFunction(Function &F) {
88   PI = &getAnalysis<ProfileInfo>();
89 
90   NumMovedBlocks = 0;
91   InsertPos = F.begin();
92 
93   // Recursively place all blocks.
94   PlaceBlocks(F.begin());
95 
96   PlacedBlocks.clear();
97   NumMoved += NumMovedBlocks;
98   return NumMovedBlocks != 0;
99 }
100 
101 
102 /// PlaceBlocks - Recursively place the specified blocks and any unplaced
103 /// successors.
PlaceBlocks(BasicBlock * BB)104 void BlockPlacement::PlaceBlocks(BasicBlock *BB) {
105   assert(!PlacedBlocks.count(BB) && "Already placed this block!");
106   PlacedBlocks.insert(BB);
107 
108   // Place the specified block.
109   if (&*InsertPos != BB) {
110     // Use splice to move the block into the right place.  This avoids having to
111     // remove the block from the function then readd it, which causes a bunch of
112     // symbol table traffic that is entirely pointless.
113     Function::BasicBlockListType &Blocks = BB->getParent()->getBasicBlockList();
114     Blocks.splice(InsertPos, Blocks, BB);
115 
116     ++NumMovedBlocks;
117   } else {
118     // This block is already in the right place, we don't have to do anything.
119     ++InsertPos;
120   }
121 
122   // Keep placing successors until we run out of ones to place.  Note that this
123   // loop is very inefficient (N^2) for blocks with many successors, like switch
124   // statements.  FIXME!
125   while (1) {
126     // Okay, now place any unplaced successors.
127     succ_iterator SI = succ_begin(BB), E = succ_end(BB);
128 
129     // Scan for the first unplaced successor.
130     for (; SI != E && PlacedBlocks.count(*SI); ++SI)
131       /*empty*/;
132     if (SI == E) return;  // No more successors to place.
133 
134     double MaxExecutionCount = PI->getExecutionCount(*SI);
135     BasicBlock *MaxSuccessor = *SI;
136 
137     // Scan for more frequently executed successors
138     for (; SI != E; ++SI)
139       if (!PlacedBlocks.count(*SI)) {
140         double Count = PI->getExecutionCount(*SI);
141         if (Count > MaxExecutionCount ||
142             // Prefer to not disturb the code.
143             (Count == MaxExecutionCount && *SI == &*InsertPos)) {
144           MaxExecutionCount = Count;
145           MaxSuccessor = *SI;
146         }
147       }
148 
149     // Now that we picked the maximally executed successor, place it.
150     PlaceBlocks(MaxSuccessor);
151   }
152 }
153