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