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> 37using namespace llvm; 38 39STATISTIC(NumMoved, "Number of basic blocks moved"); 40 41namespace { 42 struct BlockPlacement : public FunctionPass { 43 static char ID; // Pass identification, replacement for typeid 44 BlockPlacement() : FunctionPass(ID) { 45 initializeBlockPlacementPass(*PassRegistry::getPassRegistry()); 46 } 47 48 virtual bool runOnFunction(Function &F); 49 50 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 78char BlockPlacement::ID = 0; 79INITIALIZE_PASS_BEGIN(BlockPlacement, "block-placement", 80 "Profile Guided Basic Block Placement", false, false) 81INITIALIZE_AG_DEPENDENCY(ProfileInfo) 82INITIALIZE_PASS_END(BlockPlacement, "block-placement", 83 "Profile Guided Basic Block Placement", false, false) 84 85FunctionPass *llvm::createBlockPlacementPass() { return new BlockPlacement(); } 86 87bool 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. 104void 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