LLVM API Documentation

BasicBlockPlacement.cpp

Go to the documentation of this file.
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 }