lib/Transforms/Scalar/BasicBlockPlacement.cpp

   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
  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
  78 char BlockPlacement::ID = 0;
  79 INITIALIZE_PASS_BEGIN(BlockPlacement, "block-placement",
  80                 "Profile Guided Basic Block Placement", false, false)
  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
  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.
 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 }