path: root/lib/CodeGen/MachineBlockPlacement.cpp

//===-- MachineBlockPlacement.cpp - Basic Block Code Layout optimization --===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements basic block placement transformations using branch
// probability estimates. It is based around "Algo2" from Profile Guided Code
// Positioning [http://portal.acm.org/citation.cfm?id=989433].
//
// We combine the BlockFrequencyInfo with BranchProbabilityInfo to simulate
// measured edge-weights. The BlockFrequencyInfo effectively summarizes the
// probability of starting from any particular block, and the
// BranchProbabilityInfo the probability of exiting the block via a particular
// edge. Combined they form a function-wide ordering of the edges.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "block-placement2"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Target/TargetInstrInfo.h"
#include <algorithm>
using namespace llvm;

namespace {
/// \brief A structure for storing a weighted edge.
///
/// This stores an edge and its weight, computed as the product of the
/// frequency that the starting block is entered with the probability of
/// a particular exit block.
struct WeightedEdge {
  BlockFrequency EdgeFrequency;
  MachineBasicBlock *From, *To;

  bool operator<(const WeightedEdge &RHS) const {
    return EdgeFrequency < RHS.EdgeFrequency;
  }
};
}

namespace {
struct BlockChain;
/// \brief Type for our function-wide basic block -> block chain mapping.
typedef DenseMap<MachineBasicBlock *, BlockChain *> BlockToChainMapType;
}

namespace {
/// \brief A chain of blocks which will be laid out contiguously.
///
/// This is the datastructure representing a chain of consecutive blocks that
/// are profitable to layout together in order to maximize fallthrough
/// probabilities. We also can use a block chain to represent a sequence of
/// basic blocks which have some external (correctness) requirement for
/// sequential layout.
///
/// Eventually, the block chains will form a directed graph over the function.
/// We provide an SCC-supporting-iterator in order to quicky build and walk the
/// SCCs of block chains within a function.
///
/// The block chains also have support for calculating and caching probability
/// information related to the chain itself versus other chains. This is used
/// for ranking during the final layout of block chains.
struct BlockChain {
  class SuccIterator;

  /// \brief The first and last basic block that from this chain.
  ///
  /// The chain is stored within the existing function ilist of basic blocks.
  /// When merging chains or otherwise manipulating them, we splice the blocks
  /// within this ilist, giving us very cheap storage here and constant time
  /// merge operations.
  ///
  /// It is extremely important to note that LastBB is the iterator pointing
  /// *at* the last basic block in the chain. That is, the chain consists of
  /// the *closed* range [FirstBB, LastBB]. We cannot use half-open ranges
  /// because the next basic block may get relocated to a different part of the
  /// function at any time during the run of this pass.
  MachineFunction::iterator FirstBB, LastBB;

  /// \brief A handle to the function-wide basic block to block chain mapping.
  ///
  /// This is retained in each block chain to simplify the computation of child
  /// block chains for SCC-formation and iteration. We store the edges to child
  /// basic blocks, and map them back to their associated chains using this
  /// structure.
  BlockToChainMapType &BlockToChain;

  /// \brief The weight used to rank two block chains in the same SCC.
  ///
  /// This is used during SCC layout of block chains to cache and rank the
  /// chains. It is supposed to represent the expected frequency with which
  /// control reaches a block within this chain, has the option of branching to
  /// a block in some other chain participating in the SCC, but instead
  /// continues within this chain. The higher this is, the more costly we
  /// expect mis-predicted branches between this chain and other chains within
  /// the SCC to be. Thus, since we expect branches between chains to be
  /// predicted when backwards and not predicted when forwards, the higher this
  /// is the more important that this chain is laid out first among those
  /// chains in the same SCC as it.
  BlockFrequency InChainEdgeFrequency;

  /// \brief Construct a new BlockChain.
  ///
  /// This builds a new block chain representing a single basic block in the
  /// function. It also registers itself as the chain that block participates
  /// in with the BlockToChain mapping.
  BlockChain(BlockToChainMapType &BlockToChain, MachineBasicBlock *BB)
    : FirstBB(BB), LastBB(BB), BlockToChain(BlockToChain) {
    assert(BB && "Cannot create a chain with a null basic block");
    BlockToChain[BB] = this;
  }

  /// \brief Merge another block chain into this one.
  ///
  /// This routine merges a block chain into this one. It takes care of forming
  /// a contiguous sequence of basic blocks, updating the edge list, and
  /// updating the block -> chain mapping. It does not free or tear down the
  /// old chain, but the old chain's block list is no longer valid.
  void merge(BlockChain *Chain) {
    assert(Chain && "Cannot merge a null chain");
    MachineFunction::iterator EndBB = llvm::next(LastBB);
    MachineFunction::iterator ChainEndBB = llvm::next(Chain->LastBB);

    // Update the incoming blocks to point to this chain.
    for (MachineFunction::iterator BI = Chain->FirstBB, BE = ChainEndBB;
         BI != BE; ++BI) {
      assert(BlockToChain[BI] == Chain && "Incoming blocks not in chain");
      BlockToChain[BI] = this;
    }

    // We splice the blocks together within the function (unless they already
    // are adjacent) so we can represent the new chain with a pair of pointers
    // to basic blocks within the function. This is also useful as each chain
    // of blocks will end up being laid out contiguously within the function.
    if (EndBB != Chain->FirstBB)
      FirstBB->getParent()->splice(EndBB, Chain->FirstBB, ChainEndBB);
    LastBB = Chain->LastBB;
  }
};
}

namespace {
/// \brief Successor iterator for BlockChains.
///
/// This is an iterator that walks over the successor block chains by looking
/// through its blocks successors and mapping those back to block chains. This
/// iterator is not a fully-functioning iterator, it is designed specifically
/// to support the interface required by SCCIterator when forming and walking
/// SCCs of BlockChains.
///
/// Note that this iterator cannot be used while the chains are still being
/// formed and/or merged. Unlike the chains themselves, it does store end
/// iterators which could be moved if the chains are re-ordered. Once we begin
/// forming and iterating over an SCC of chains, the order of blocks within the
/// function must not change until we finish using the SCC iterators.
class BlockChain::SuccIterator
    : public std::iterator<std::forward_iterator_tag,
                           BlockChain *, ptrdiff_t> {
  BlockChain *Chain;
  MachineFunction::iterator BI, BE;
  MachineBasicBlock::succ_iterator SI;

public:
  explicit SuccIterator(BlockChain *Chain)
    : Chain(Chain), BI(Chain->FirstBB), BE(llvm::next(Chain->LastBB)),
      SI(BI->succ_begin()) {
    while (BI != BE && BI->succ_begin() == BI->succ_end())
      ++BI;
    if (BI != BE)
      SI = BI->succ_begin();
  }

  /// \brief Helper function to create an end iterator for a particular chain.
  ///
  /// The "end" state is extremely arbitrary. We chose to have BI == BE, and SI
  /// == Chain->FirstBB->succ_begin(). The value of SI doesn't really make any
  /// sense, but rather than try to rationalize SI and our increment, when we
  /// detect an "end" state, we just immediately call this function to build
  /// the canonical end iterator.
  static SuccIterator CreateEnd(BlockChain *Chain) {
    SuccIterator It(Chain);
    It.BI = It.BE;
    return It;
  }

  bool operator==(const SuccIterator &RHS) const {
    return (Chain == RHS.Chain && BI == RHS.BI && SI == RHS.SI);
  }
  bool operator!=(const SuccIterator &RHS) const {
    return !operator==(RHS);
  }

  SuccIterator& operator++() {
    assert(*this != CreateEnd(Chain) && "Cannot increment the end iterator");
    // There may be null successor pointers, skip over them.
    // FIXME: I don't understand *why* there are null successor pointers.
    do {
      ++SI;
      if (SI != BI->succ_end() && *SI)
        return *this;

      // There may be a basic block without successors. Skip over them.
      do {
        ++BI;
        if (BI == BE)
          return *this = CreateEnd(Chain);
      } while (BI->succ_begin() == BI->succ_end());
      SI = BI->succ_begin();
    } while (!*SI);
    return *this;
  }
  SuccIterator operator++(int) {
    SuccIterator tmp = *this;
    ++*this;
    return tmp;
  }

  BlockChain *operator*() const {
    assert(Chain->BlockToChain.lookup(*SI) && "Missing chain");
    return Chain->BlockToChain.lookup(*SI);
  }
};
}

namespace {
/// \brief Sorter used with containers of BlockChain pointers.
///
/// Sorts based on the \see BlockChain::InChainEdgeFrequency -- see its
/// comments for details on what this ordering represents.
struct ChainPtrPrioritySorter {
  bool operator()(const BlockChain *LHS, const BlockChain *RHS) const {
    assert(LHS && RHS && "Null chain entry");
    return LHS->InChainEdgeFrequency < RHS->