//
//===----------------------------------------------------------------------===//
//
-// 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].
+// This file implements basic block placement transformations using the CFG
+// structure and branch probability estimates.
//
-// 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.
+// The pass strives to preserve the structure of the CFG (that is, retain
+// a topological ordering of basic blocks) in the absense of a *strong* signal
+// to the contrary from probabilities. However, within the CFG structure, it
+// attempts to choose an ordering which favors placing more likely sequences of
+// blocks adjacent to each other.
+//
+// The algorithm works from the inner-most loop within a function outward, and
+// at each stage walks through the basic blocks, trying to coalesce them into
+// sequential chains where allowed by the CFG (or demanded by heavy
+// probabilities). Finally, it walks the blocks in topological order, and the
+// first time it reaches a chain of basic blocks, it schedules them in the
+// function in-order.
//
//===----------------------------------------------------------------------===//
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/Support/Allocator.h"
+#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
}
namespace {
-struct BlockChain;
+class BlockChain;
/// \brief Type for our function-wide basic block -> block chain mapping.
typedef DenseMap<MachineBasicBlock *, BlockChain *> BlockToChainMapType;
}
/// 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.
+class BlockChain {
+ /// \brief The sequence of blocks belonging to this chain.
///
- /// 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;
+ /// This is the sequence of blocks for a particular chain. These will be laid
+ /// out in-order within the function.
+ SmallVector<MachineBasicBlock *, 4> Blocks;
/// \brief A handle to the function-wide basic block to block chain mapping.
///
/// 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;
-
+public:
/// \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) {
+ : Blocks(1, 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.
+ /// \brief Iterator over blocks within the chain.
+ typedef SmallVectorImpl<MachineBasicBlock *>::const_iterator iterator;
+
+ /// \brief Beginning of blocks within the chain.
+ iterator begin() const { return Blocks.begin(); }
+
+ /// \brief End of blocks within the chain.
+ iterator end() const { return Blocks.end(); }
+
+ /// \brief Merge a 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;
+ void merge(MachineBasicBlock *BB, BlockChain *Chain) {
+ assert(BB);
+ assert(!Blocks.empty());
+ assert(Blocks.back()->isSuccessor(BB));
+
+ // Fast path in case we don't have a chain already.
+ if (!Chain) {
+ assert(!BlockToChain[BB]);
+ Blocks.push_back(BB);
+ BlockToChain[BB] = this;
+ return;
}
- // 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;
- }
+ assert(BB == *Chain->begin());
+ assert(Chain->begin() != Chain->end());
- 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->InChainEdgeFrequency;
+ // Update the incoming blocks to point to this chain, and add them to the
+ // chain structure.
+ for (BlockChain::iterator BI = Chain->begin(), BE = Chain->end();
+ BI != BE; ++BI) {
+ Blocks.push_back(*BI);
+ assert(BlockToChain[*BI] == Chain && "Incoming blocks not in chain");
+ BlockToChain[*BI] = this;
+ }
}
};
}
namespace {
class MachineBlockPlacement : public MachineFunctionPass {
+ /// \brief A typedef for a block filter set.
+ typedef SmallPtrSet<MachineBasicBlock *, 16> BlockFilterSet;
+
/// \brief A handle to the branch probability pass.
const MachineBranchProbabilityInfo *MBPI;
/// \brief A handle to the target's lowering info.
const TargetLowering *TLI;
- /// \brief A prioritized list of edges in the BB-graph.
- ///
- /// For each function, we insert all control flow edges between BBs, along
- /// with their "global" frequency. The Frequency of an edge being taken is
- /// defined as the frequency of entering the source BB (from MBFI) times the
- /// probability of taking a particular branch out of that block (from MBPI).
- ///
- /// Once built, this list is sorted in ascending frequency, making the last
- /// edge the hottest one in the function.
- SmallVector<WeightedEdge, 64> Edges;
-
/// \brief Allocator and owner of BlockChain structures.
///
/// We build BlockChains lazily by merging together high probability BB
/// between basic blocks.
DenseMap<MachineBasicBlock *, BlockChain *> BlockToChain;
- /// \brief A prioritized sequence of chains.
- ///
- /// We build up the ideal sequence of basic block chains in reverse order
- /// here, and then walk backwards to arrange the final function ordering.
- SmallVector<BlockChain *, 16> PChains;
-
-#ifndef NDEBUG
- /// \brief A set of active chains used to sanity-check the pass algorithm.
- ///
- /// All operations on this member should be wrapped in an assert or NDEBUG.
- SmallPtrSet<BlockChain *, 16> ActiveChains;
-#endif
-
BlockChain *CreateChain(MachineBasicBlock *BB);
- void PrioritizeEdges(MachineFunction &F);
- void BuildBlockChains();
- void PrioritizeChains(MachineFunction &F);
- void PlaceBlockChains(MachineFunction &F);
+ void mergeSuccessor(MachineBasicBlock *BB, BlockChain *Chain,
+ BlockFilterSet *Filter = 0);
+ void buildLoopChains(MachineFunction &F, MachineLoop &L);
+ void buildCFGChains(MachineFunction &F);
+ void placeChainsTopologically(MachineFunction &F);
void AlignLoops(MachineFunction &F);
public:
return new MachineBlockPlacement();
}
-namespace llvm {
-/// \brief GraphTraits specialization for our BlockChain graph.
-template <> struct GraphTraits<BlockChain *> {
- typedef BlockChain NodeType;
- typedef BlockChain::SuccIterator ChildIteratorType;
+#ifndef NDEBUG
+/// \brief Helper to print the name of a MBB.
+///
+/// Only used by debug logging.
+static std::string getBlockName(MachineBasicBlock *BB) {
+ std::string Result;
+ raw_string_ostream OS(Result);
+ OS << "BB#" << BB->getNumber()
+ << " (derived from LLVM BB '" << BB->getName() << "')";
+ OS.flush();
+ return Result;
+}
- static NodeType *getEntryNode(NodeType *N) { return N; }
- static BlockChain::SuccIterator child_begin(NodeType *N) {
- return BlockChain::SuccIterator(N);
- }
- static BlockChain::SuccIterator child_end(NodeType *N) {
- return BlockChain::SuccIterator::CreateEnd(N);
- }
-};
+/// \brief Helper to print the number of a MBB.
+///
+/// Only used by debug logging.
+static std::string getBlockNum(MachineBasicBlock *BB) {
+ std::string Result;
+ raw_string_ostream OS(Result);
+ OS << "BB#" << BB->getNumber();
+ OS.flush();
+ return Result;
}
+#endif
/// \brief Helper to create a new chain for a single BB.
///
BlockChain *MachineBlockPlacement::CreateChain(MachineBasicBlock *BB) {
BlockChain *Chain =
new (ChainAllocator.Allocate()) BlockChain(BlockToChain, BB);
- assert(ActiveChains.insert(Chain));
+ //assert(ActiveChains.insert(Chain));
return Chain;
}
-/// \brief Build a prioritized list of edges.
+/// \brief Merge a chain with any viable successor.
///
-/// The priority is determined by the product of the block frequency (how
-/// likely it is to arrive at a particular block) times the probability of
-/// taking this particular edge out of the block. This provides a function-wide
-/// ordering of the edges.
-void MachineBlockPlacement::PrioritizeEdges(MachineFunction &F) {
- assert(Edges.empty() && "Already have an edge list");
- SmallVector<MachineOperand, 4> Cond; // For AnalyzeBranch.
- BlockChain *RequiredChain = 0;
- for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
- MachineBasicBlock *From = &*FI;
- // We only consider MBBs with analyzable branches. Even if the analysis
- // fails, if there is no fallthrough, we can still work with the MBB.
- MachineBasicBlock *TBB = 0, *FBB = 0;
- Cond.clear();
- if (TII->AnalyzeBranch(*From, TBB, FBB, Cond) && From->canFallThrough()) {
- // We push all unanalyzed blocks onto a chain eagerly to prevent them
- // from being split later. Create the chain if needed, otherwise just
- // keep track that these blocks reside on it.
- if (!RequiredChain)
- RequiredChain = CreateChain(From);
- else
- BlockToChain[From] = RequiredChain;
- } else {
- // As soon as we find an analyzable branch, add that block to and
- // finalize any required chain that has been started. The required chain
- // is only modeling potentially inexplicable fallthrough, so the first
- // block to have analyzable fallthrough is a known-safe stopping point.
- if (RequiredChain) {
- BlockToChain[From] = RequiredChain;
- RequiredChain->LastBB = FI;
- RequiredChain = 0;
- }
- }
+/// This routine walks the predecessors of the current block, looking for
+/// viable merge candidates. It has strict rules it uses to determine when
+/// a predecessor can be merged with the current block, which center around
+/// preserving the CFG structure. It performs the merge if any viable candidate
+/// is found.
+void MachineBlockPlacement::mergeSuccessor(MachineBasicBlock *BB,
+ BlockChain *Chain,
+ BlockFilterSet *Filter) {
+ assert(BB);
+ assert(Chain);
+
+ // If this block is not at the end of its chain, it cannot merge with any
+ // other chain.
+ if (Chain && *llvm::prior(Chain->end()) != BB)
+ return;
- BlockFrequency BaseFrequency = MBFI->getBlockFreq(From);
- for (MachineBasicBlock::succ_iterator SI = From->succ_begin(),
- SE = From->succ_end();
- SI != SE; ++SI) {
- MachineBasicBlock *To = *SI;
- WeightedEdge WE = { BaseFrequency * MBPI->getEdgeProbability(From, To),
- From, To };
- Edges.push_back(WE);
+ // Walk through the successors looking for the highest probability edge.
+ // FIXME: This is an annoying way to do the comparison, but it's correct.
+ // Support should be added to BranchProbability to properly compare two.
+ MachineBasicBlock *Successor = 0;
+ BlockFrequency BestFreq;
+ DEBUG(dbgs() << "Attempting merge from: " << getBlockName(BB) << "\n");
+ for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
+ SE = BB->succ_end();
+ SI != SE; ++SI) {
+ if (BB == *SI || (Filter && !Filter->count(*SI)))
+ continue;
+
+ BlockFrequency SuccFreq(BlockFrequency::getEntryFrequency());
+ SuccFreq *= MBPI->getEdgeProbability(BB, *SI);
+ DEBUG(dbgs() << " " << getBlockName(*SI) << " -> " << SuccFreq << "\n");
+ if (!Successor || SuccFreq > BestFreq || (!(SuccFreq < BestFreq) &&
+ BB->isLayoutSuccessor(*SI))) {
+ Successor = *SI;
+ BestFreq = SuccFreq;
}
}
- assert(!RequiredChain && "Never found a terminator for a required chain");
- std::stable_sort(Edges.begin(), Edges.end());
-}
+ if (!Successor)
+ return;
-/// \brief Build chains of basic blocks along hot paths.
-///
-/// Build chains by trying to merge each pair of blocks from the mostly costly
-/// edge first. This is essentially "Algo2" from the Profile Guided Code
-/// Placement paper. While each node is considered a chain of one block, this
-/// routine lazily build the chain objects themselves so that when possible it
-/// can just merge a block into an existing chain.
-void MachineBlockPlacement::BuildBlockChains() {
- for (SmallVectorImpl<WeightedEdge>::reverse_iterator EI = Edges.rbegin(),
- EE = Edges.rend();
- EI != EE; ++EI) {
- MachineBasicBlock *SourceB = EI->From, *DestB = EI->To;
- if (SourceB == DestB) continue;
-
- BlockChain *SourceChain = BlockToChain.lookup(SourceB);
- if (!SourceChain) SourceChain = CreateChain(SourceB);
- BlockChain *DestChain = BlockToChain.lookup(DestB);
- if (!DestChain) DestChain = CreateChain(DestB);
- if (SourceChain == DestChain)
- continue;
+ // Grab a chain if it exists already for this successor and make sure the
+ // successor is at the start of the chain as we can't merge mid-chain. Also,
+ // if the successor chain is the same as our chain, we're already merged.
+ BlockChain *SuccChain = BlockToChain[Successor];
+ if (SuccChain && (SuccChain == Chain || Successor != *SuccChain->begin()))
+ return;
+
+ // We only merge chains across a CFG merge when the desired merge path is
+ // significantly hotter than the incoming edge. We define a hot edge more
+ // strictly than the BranchProbabilityInfo does, as the two predecessor
+ // blocks may have dramatically different incoming probabilities we need to
+ // account for. Therefor we use the "global" edge weight which is the
+ // branch's probability times the block frequency of the predecessor.
+ BlockFrequency MergeWeight = MBFI->getBlockFreq(BB);
+ MergeWeight *= MBPI->getEdgeProbability(BB, Successor);
+ // We only want to consider breaking the CFG when the merge weight is much
+ // higher (80% vs. 20%), so multiply it by 1/4. This will require the merged
+ // edge to be 4x more likely before we disrupt the CFG. This number matches
+ // the definition of "hot" in BranchProbabilityAnalysis (80% vs. 20%).
+ MergeWeight *= BranchProbability(1, 4);
+ for (MachineBasicBlock::pred_iterator PI = Successor->pred_begin(),
+ PE = Successor->pred_end();
+ PI != PE; ++PI) {
+ if (BB == *PI || Successor == *PI) continue;
+ BlockFrequency PredWeight = MBFI->getBlockFreq(*PI);
+ PredWeight *= MBPI->getEdgeProbability(*PI, Successor);
+
+ // Return on the first predecessor we find which outstrips our merge weight.
+ if (MergeWeight < PredWeight)
+ return;
+ DEBUG(dbgs() << "Breaking CFG edge!\n"
+ << " Edge from " << getBlockNum(BB) << " to "
+ << getBlockNum(Successor) << ": " << MergeWeight << "\n"
+ << " vs. " << getBlockNum(BB) << " to "
+ << getBlockNum(*PI) << ": " << PredWeight << "\n");
+ }
- bool IsSourceTail =
- SourceChain->LastBB == MachineFunction::iterator(SourceB);
- bool IsDestHead =
- DestChain->FirstBB == MachineFunction::iterator(DestB);
+ DEBUG(dbgs() << "Merging from " << getBlockNum(BB) << " to "
+ << getBlockNum(Successor) << "\n");
+ Chain->merge(Successor, SuccChain);
+}
- if (!IsSourceTail || !IsDestHead)
- continue;
+/// \brief Forms basic block chains from the natural loop structures.
+///
+/// These chains are designed to preserve the existing *structure* of the code
+/// as much as possible. We can then stitch the chains together in a way which
+/// both preserves the topological structure and minimizes taken conditional
+/// branches.
+void MachineBlockPlacement::buildLoopChains(MachineFunction &F, MachineLoop &L) {
+ // First recurse through any nested loops, building chains for those inner
+ // loops.
+ for (MachineLoop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI)
+ buildLoopChains(F, **LI);
+
+ SmallPtrSet<MachineBasicBlock *, 16> LoopBlockSet(L.block_begin(),
+ L.block_end());
+
+ // Begin building up a set of chains of blocks within this loop which should
+ // remain contiguous. Some of the blocks already belong to a chain which
+ // represents an inner loop.
+ for (MachineLoop::block_iterator BI = L.block_begin(), BE = L.block_end();
+ BI != BE; ++BI) {
+ MachineBasicBlock *BB = *BI;
+ BlockChain *Chain = BlockToChain[BB];
+ if (!Chain) Chain = CreateChain(BB);
+ mergeSuccessor(BB, Chain, &LoopBlockSet);
+ }
+}
- SourceChain->merge(DestChain);
- assert(ActiveChains.erase(DestChain));
+void MachineBlockPlacement::buildCFGChains(MachineFunction &F) {
+ // First build any loop-based chains.
+ for (MachineLoopInfo::iterator LI = MLI->begin(), LE = MLI->end(); LI != LE;
+ ++LI)
+ buildLoopChains(F, **LI);
+
+ // Now walk the blocks of the function forming chains where they don't
+ // violate any CFG structure.
+ for (MachineFunction::iterator BI = F.begin(), BE = F.end();
+ BI != BE; ++BI) {
+ MachineBasicBlock *BB = BI;
+ BlockChain *Chain = BlockToChain[BB];
+ if (!Chain) Chain = CreateChain(BB);
+ mergeSuccessor(BB, Chain);
}
}
-/// \brief Prioritize the chains to minimize back-edges between chains.
-///
-/// This is the trickiest part of the placement algorithm. Each chain is
-/// a hot-path through a sequence of basic blocks, but there are conditional
-/// branches away from this hot path, and to some other chain. Hardware branch
-/// predictors favor back edges over forward edges, and so it is desirable to
-/// arrange the targets of branches away from a hot path and to some other
-/// chain to come later in the function, making them forward branches, and
-/// helping the branch predictor to predict fallthrough.
-///
-/// In some cases, this is easy. simply topologically walking from the entry
-/// chain through its successors in order would work if there were no cycles
-/// between the chains of blocks, but often there are. In such a case, we first
-/// need to identify the participants in the cycle, and then rank them so that
-/// the linearizing of the chains has the lowest *probability* of causing
-/// a mispredicted branch. To compute the correct rank for a chain, we take the
-/// complement of the branch probability for each branch leading away from the
-/// chain and multiply it by the frequency of the source block for that branch.
-/// This gives us the probability of that particular branch *not* being taken
-/// in this function. The sum of these probabilities for each chain is used as
-/// a rank, so that we order the chain with the highest such sum first.
-/// FIXME: This seems like a good approximation, but there is probably a known
-/// technique for ordering of an SCC given edge weights. It would be good to
-/// use that, or even use its code if possible.
-///
-/// Also notable is that we prioritize the chains from the bottom up, and so
-/// all of the "first" and "before" relationships end up inverted in the code.
-void MachineBlockPlacement::PrioritizeChains(MachineFunction &F) {
+void MachineBlockPlacement::placeChainsTopologically(MachineFunction &F) {
MachineBasicBlock *EntryB = &F.front();
BlockChain *EntryChain = BlockToChain[EntryB];
assert(EntryChain && "Missing chain for entry block");
- assert(EntryChain->FirstBB == F.begin() &&
+ assert(*EntryChain->begin() == EntryB &&
"Entry block is not the head of the entry block chain");
- // Form an SCC and walk it from the bottom up.
- SmallPtrSet<BlockChain *, 4> IsInSCC;
- for (scc_iterator<BlockChain *> I = scc_begin(EntryChain);
- !I.isAtEnd(); ++I) {
- const std::vector<BlockChain *> &SCC = *I;
- PChains.insert(PChains.end(), SCC.begin(), SCC.end());
-
- // If there is only one chain in the SCC, it's trivially sorted so just
- // bail out early. Sorting the SCC is expensive.
- if (SCC.size() == 1)
+ // Walk the blocks in RPO, and insert each block for a chain in order the
+ // first time we see that chain.
+ MachineFunction::iterator InsertPos = F.begin();
+ SmallPtrSet<BlockChain *, 16> VisitedChains;
+ ReversePostOrderTraversal<MachineBasicBlock *> RPOT(EntryB);
+ typedef ReversePostOrderTraversal<MachineBasicBlock *>::rpo_iterator
+ rpo_iterator;
+ for (rpo_iterator I = RPOT.begin(), E = RPOT.end(); I != E; ++I) {
+ BlockChain *Chain = BlockToChain[*I];
+ assert(Chain);
+ if(!VisitedChains.insert(Chain))
continue;
-
- // We work strictly on the PChains range from here on out to maximize
- // locality.
- SmallVectorImpl<BlockChain *>::iterator SCCEnd = PChains.end(),
- SCCBegin = SCCEnd - SCC.size();
- IsInSCC.clear();
- IsInSCC.insert(SCCBegin, SCCEnd);
-
- // Compute the edge frequency of staying in a chain, despite the existency
- // of an edge to some other chain within this SCC.
- for (SmallVectorImpl<BlockChain *>::iterator SCCI = SCCBegin;
- SCCI != SCCEnd; ++SCCI) {
- BlockChain *Chain = *SCCI;
-
- // Special case the entry chain. Regardless of the weights of other
- // chains, the entry chain *must* come first, so move it to the end, and
- // avoid processing that chain at all.
- if (Chain == EntryChain) {
- --SCCEnd;
- if (SCCI == SCCEnd) break;
- Chain = *SCCI = *SCCEnd;
- *SCCEnd = EntryChain;
- }
-
- // Walk over every block in this chain looking for out-bound edges to
- // other chains in this SCC.
- for (MachineFunction::iterator BI = Chain->FirstBB,
- BE = llvm::next(Chain->LastBB);
- BI != BE; ++BI) {
- MachineBasicBlock *From = &*BI;
- for (MachineBasicBlock::succ_iterator SI = BI->succ_begin(),
- SE = BI->succ_end();
- SI != SE; ++SI) {
- MachineBasicBlock *To = *SI;
- if (!To || !IsInSCC.count(BlockToChain[To]))
- continue;
- BranchProbability ComplEdgeProb =
- MBPI->getEdgeProbability(From, To).getCompl();
- Chain->InChainEdgeFrequency +=
- MBFI->getBlockFreq(From) * ComplEdgeProb;
- }
- }
+ for (BlockChain::iterator BI = Chain->begin(), BE = Chain->end(); BI != BE;
+ ++BI) {
+ DEBUG(dbgs() << (BI == Chain->begin() ? "Placing chain "
+ : " ... ")
+ << getBlockName(*BI) << "\n");
+ if (InsertPos != MachineFunction::iterator(*BI))
+ F.splice(InsertPos, *BI);
+ else
+ ++InsertPos;
}
-
- // Sort the chains within the SCC according to their edge frequencies,
- // which should make the least costly chain of blocks to mis-place be
- // ordered first in the prioritized sequence.
- std::stable_sort(SCCBegin, SCCEnd, ChainPtrPrioritySorter());
}
-}
-
-/// \brief Splice the function blocks together based on the chain priorities.
-///
-/// Each chain is already represented as a contiguous range of blocks in the
-/// function. Simply walk backwards down the prioritized chains and splice in
-/// any chains out of order. Note that the first chain we visit is necessarily
-/// the entry chain. It has no predecessors and so must be the top of the SCC.
-/// Also, we cannot splice any chain prior to the entry chain as we can't
-/// splice any blocks prior to the entry block.
-void MachineBlockPlacement::PlaceBlockChains(MachineFunction &F) {
- assert(!PChains.empty() && "No chains were prioritized");
- assert(PChains.back() == BlockToChain[&F.front()] &&
- "The entry chain must always be the final chain");
-
- MachineFunction::iterator InsertPos = F.begin();
- for (SmallVectorImpl<BlockChain *>::reverse_iterator CI = PChains.rbegin(),
- CE = PChains.rend();
- CI != CE; ++CI) {
- BlockChain *Chain = *CI;
- // Check that we process this chain only once for debugging.
- assert(ActiveChains.erase(Chain) && "Processed a chain twice");
-
- // If this chain is already in the right position, just skip past it.
- // Otherwise, splice it into position.
- if (InsertPos == Chain->FirstBB)
- InsertPos = llvm::next(Chain->LastBB);
- else
- F.splice(InsertPos, Chain->FirstBB, llvm::next(Chain->LastBB));
- }
-
- // Note that we can't assert this is empty as there may be unreachable blocks
- // in the function.
-#ifndef NDEBUG
- ActiveChains.clear();
-#endif
// Now that every block is in its final position, update all of the
// terminators.
MLI = &getAnalysis<MachineLoopInfo>();
TII = F.getTarget().getInstrInfo();
TLI = F.getTarget().getTargetLowering();
- assert(Edges.empty());
assert(BlockToChain.empty());
- assert(PChains.empty());
- assert(ActiveChains.empty());
- PrioritizeEdges(F);
- BuildBlockChains();
- PrioritizeChains(F);
- PlaceBlockChains(F);
+ buildCFGChains(F);
+ placeChainsTopologically(F);
AlignLoops(F);
- Edges.clear();
BlockToChain.clear();
- PChains.clear();
- ChainAllocator.DestroyAll();
// We always return true as we have no way to track whether the final order
// differs from the original order.
projects / oota-llvm.git / commitdiff