LLVM API Documentation
00001 //===-- BasicBlockPlacement.cpp - Basic Block Code Layout optimization ----===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements a very simple profile guided basic block placement 00011 // algorithm. The idea is to put frequently executed blocks together at the 00012 // start of the function, and hopefully increase the number of fall-through 00013 // conditional branches. If there is no profile information for a particular 00014 // function, this pass basically orders blocks in depth-first order 00015 // 00016 // The algorithm implemented here is basically "Algo1" from "Profile Guided Code 00017 // Positioning" by Pettis and Hansen, except that it uses basic block counts 00018 // instead of edge counts. This should be improved in many ways, but is very 00019 // simple for now. 00020 // 00021 // Basically we "place" the entry block, then loop over all successors in a DFO, 00022 // placing the most frequently executed successor until we run out of blocks. I 00023 // told you this was _extremely_ simplistic. :) This is also much slower than it 00024 // could be. When it becomes important, this pass will be rewritten to use a 00025 // better algorithm, and then we can worry about efficiency. 00026 // 00027 //===----------------------------------------------------------------------===// 00028 00029 #include "llvm/Analysis/ProfileInfo.h" 00030 #include "llvm/Function.h" 00031 #include "llvm/Pass.h" 00032 #include "llvm/Support/CFG.h" 00033 #include "llvm/ADT/Statistic.h" 00034 #include "llvm/Transforms/Scalar.h" 00035 #include <set> 00036 using namespace llvm; 00037 00038 namespace { 00039 Statistic<> NumMoved("block-placement", "Number of basic blocks moved"); 00040 00041 struct BlockPlacement : public FunctionPass { 00042 virtual bool runOnFunction(Function &F); 00043 00044 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00045 AU.setPreservesCFG(); 00046 AU.addRequired<ProfileInfo>(); 00047 //AU.addPreserved<ProfileInfo>(); // Does this work? 00048 } 00049 private: 00050 /// PI - The profile information that is guiding us. 00051 /// 00052 ProfileInfo *PI; 00053 00054 /// NumMovedBlocks - Every time we move a block, increment this counter. 00055 /// 00056 unsigned NumMovedBlocks; 00057 00058 /// PlacedBlocks - Every time we place a block, remember it so we don't get 00059 /// into infinite loops. 00060 std::set<BasicBlock*> PlacedBlocks; 00061 00062 /// InsertPos - This an iterator to the next place we want to insert a 00063 /// block. 00064 Function::iterator InsertPos; 00065 00066 /// PlaceBlocks - Recursively place the specified blocks and any unplaced 00067 /// successors. 00068 void PlaceBlocks(BasicBlock *BB); 00069 }; 00070 00071 RegisterOpt<BlockPlacement> X("block-placement", 00072 "Profile Guided Basic Block Placement"); 00073 } 00074 00075 FunctionPass *llvm::createBlockPlacementPass() { return new BlockPlacement(); } 00076 00077 bool BlockPlacement::runOnFunction(Function &F) { 00078 PI = &getAnalysis<ProfileInfo>(); 00079 00080 NumMovedBlocks = 0; 00081 InsertPos = F.begin(); 00082 00083 // Recursively place all blocks. 00084 PlaceBlocks(F.begin()); 00085 00086 PlacedBlocks.clear(); 00087 NumMoved += NumMovedBlocks; 00088 return NumMovedBlocks != 0; 00089 } 00090 00091 00092 /// PlaceBlocks - Recursively place the specified blocks and any unplaced 00093 /// successors. 00094 void BlockPlacement::PlaceBlocks(BasicBlock *BB) { 00095 assert(!PlacedBlocks.count(BB) && "Already placed this block!"); 00096 PlacedBlocks.insert(BB); 00097 00098 // Place the specified block. 00099 if (&*InsertPos != BB) { 00100 // Use splice to move the block into the right place. This avoids having to 00101 // remove the block from the function then readd it, which causes a bunch of 00102 // symbol table traffic that is entirely pointless. 00103 Function::BasicBlockListType &Blocks = BB->getParent()->getBasicBlockList(); 00104 Blocks.splice(InsertPos, Blocks, BB); 00105 00106 ++NumMovedBlocks; 00107 } else { 00108 // This block is already in the right place, we don't have to do anything. 00109 ++InsertPos; 00110 } 00111 00112 // Keep placing successors until we run out of ones to place. Note that this 00113 // loop is very inefficient (N^2) for blocks with many successors, like switch 00114 // statements. FIXME! 00115 while (1) { 00116 // Okay, now place any unplaced successors. 00117 succ_iterator SI = succ_begin(BB), E = succ_end(BB); 00118 00119 // Scan for the first unplaced successor. 00120 for (; SI != E && PlacedBlocks.count(*SI); ++SI) 00121 /*empty*/; 00122 if (SI == E) return; // No more successors to place. 00123 00124 unsigned MaxExecutionCount = PI->getExecutionCount(*SI); 00125 BasicBlock *MaxSuccessor = *SI; 00126 00127 // Scan for more frequently executed successors 00128 for (; SI != E; ++SI) 00129 if (!PlacedBlocks.count(*SI)) { 00130 unsigned Count = PI->getExecutionCount(*SI); 00131 if (Count > MaxExecutionCount || 00132 // Prefer to not disturb the code. 00133 (Count == MaxExecutionCount && *SI == &*InsertPos)) { 00134 MaxExecutionCount = Count; 00135 MaxSuccessor = *SI; 00136 } 00137 } 00138 00139 // Now that we picked the maximally executed successor, place it. 00140 PlaceBlocks(MaxSuccessor); 00141 } 00142 }