Home | History | Annotate | Download | only in Scalar 
      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/Analysis/ProfileInfo.h"
     31 #include "llvm/Function.h"
     32 #include "llvm/Pass.h"
     33 #include "llvm/Support/CFG.h"
     34 #include "llvm/ADT/Statistic.h"
     35 #include "llvm/Transforms/Scalar.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 }
    153