LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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 <set>
00035 using namespace llvm;
00036 
00037 namespace {
00038   Statistic<> NumMoved("block-placement", "Number of basic blocks moved");
00039   
00040   struct BlockPlacement : public FunctionPass {
00041     virtual bool runOnFunction(Function &F);
00042 
00043     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00044       AU.setPreservesCFG();
00045       AU.addRequired<ProfileInfo>();
00046       //AU.addPreserved<ProfileInfo>();  // Does this work?
00047     }
00048   private:
00049     /// PI - The profile information that is guiding us.
00050     ///
00051     ProfileInfo *PI;
00052 
00053     /// NumMovedBlocks - Every time we move a block, increment this counter.
00054     ///
00055     unsigned NumMovedBlocks;
00056 
00057     /// PlacedBlocks - Every time we place a block, remember it so we don't get
00058     /// into infinite loops.
00059     std::set<BasicBlock*> PlacedBlocks;
00060 
00061     /// InsertPos - This an iterator to the next place we want to insert a
00062     /// block.
00063     Function::iterator InsertPos;
00064 
00065     /// PlaceBlocks - Recursively place the specified blocks and any unplaced
00066     /// successors.
00067     void PlaceBlocks(BasicBlock *BB);
00068   };
00069 
00070   RegisterOpt<BlockPlacement> X("block-placement",
00071                                 "Profile Guided Basic Block Placement");
00072 }
00073 
00074 bool BlockPlacement::runOnFunction(Function &F) {
00075   PI = &getAnalysis<ProfileInfo>();
00076 
00077   NumMovedBlocks = 0;
00078   InsertPos = F.begin(); 
00079 
00080   // Recursively place all blocks.
00081   PlaceBlocks(F.begin());
00082   
00083   PlacedBlocks.clear();
00084   NumMoved += NumMovedBlocks;
00085   return NumMovedBlocks != 0;
00086 }
00087 
00088 
00089 /// PlaceBlocks - Recursively place the specified blocks and any unplaced
00090 /// successors.
00091 void BlockPlacement::PlaceBlocks(BasicBlock *BB) {
00092   assert(!PlacedBlocks.count(BB) && "Already placed this block!");
00093   PlacedBlocks.insert(BB);
00094 
00095   // Place the specified block.
00096   if (&*InsertPos != BB) {
00097     // Use splice to move the block into the right place.  This avoids having to
00098     // remove the block from the function then readd it, which causes a bunch of
00099     // symbol table traffic that is entirely pointless.
00100     Function::BasicBlockListType &Blocks = BB->getParent()->getBasicBlockList();
00101     Blocks.splice(InsertPos, Blocks, BB);
00102 
00103     ++NumMovedBlocks;
00104   } else {
00105     // This block is already in the right place, we don't have to do anything.
00106     ++InsertPos;
00107   }
00108 
00109   // Keep placing successors until we run out of ones to place.  Note that this
00110   // loop is very inefficient (N^2) for blocks with many successors, like switch
00111   // statements.  FIXME!
00112   while (1) {
00113     // Okay, now place any unplaced successors.
00114     succ_iterator SI = succ_begin(BB), E = succ_end(BB);
00115     
00116     // Scan for the first unplaced successor.
00117     for (; SI != E && PlacedBlocks.count(*SI); ++SI)
00118       /*empty*/;
00119     if (SI == E) return;  // No more successors to place.
00120     
00121     unsigned MaxExecutionCount = PI->getExecutionCount(*SI);
00122     BasicBlock *MaxSuccessor = *SI;
00123 
00124     // Scan for more frequently executed successors
00125     for (; SI != E; ++SI)
00126       if (!PlacedBlocks.count(*SI)) {
00127         unsigned Count = PI->getExecutionCount(*SI);
00128         if (Count > MaxExecutionCount ||
00129             // Prefer to not disturb the code.
00130             (Count == MaxExecutionCount && *SI == &*InsertPos)) {
00131           MaxExecutionCount = Count;
00132           MaxSuccessor = *SI;
00133         }
00134       }
00135 
00136     // Now that we picked the maximally executed successor, place it.
00137     PlaceBlocks(MaxSuccessor);
00138   }
00139 }