1 //===-- MachineBlockPlacement.cpp - Basic Block Code Layout optimization --===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements basic block placement transformations using branch
11 // probability estimates. It is based around "Algo2" from Profile Guided Code
12 // Positioning [http://portal.acm.org/citation.cfm?id=989433].
14 // We combine the BlockFrequencyInfo with BranchProbabilityInfo to simulate
15 // measured edge-weights. The BlockFrequencyInfo effectively summarizes the
16 // probability of starting from any particular block, and the
17 // BranchProbabilityInfo the probability of exiting the block via a particular
18 // edge. Combined they form a function-wide ordering of the edges.
20 //===----------------------------------------------------------------------===//
22 #define DEBUG_TYPE "block-placement2"
23 #include "llvm/CodeGen/Passes.h"
24 #include "llvm/CodeGen/MachineModuleInfo.h"
25 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
26 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
27 #include "llvm/CodeGen/MachineFunction.h"
28 #include "llvm/CodeGen/MachineBasicBlock.h"
29 #include "llvm/CodeGen/MachineFunctionPass.h"
30 #include "llvm/Support/Allocator.h"
31 #include "llvm/Support/ErrorHandling.h"
32 #include "llvm/ADT/DenseMap.h"
33 #include "llvm/ADT/SCCIterator.h"
34 #include "llvm/ADT/SmallPtrSet.h"
35 #include "llvm/ADT/SmallVector.h"
36 #include "llvm/ADT/Statistic.h"
37 #include "llvm/Target/TargetInstrInfo.h"
42 /// \brief A structure for storing a weighted edge.
44 /// This stores an edge and its weight, computed as the product of the
45 /// frequency that the starting block is entered with the probability of
46 /// a particular exit block.
48 BlockFrequency EdgeFrequency;
49 MachineBasicBlock *From, *To;
51 bool operator<(const WeightedEdge &RHS) const {
52 return EdgeFrequency < RHS.EdgeFrequency;
59 /// \brief Type for our function-wide basic block -> block chain mapping.
60 typedef DenseMap<MachineBasicBlock *, BlockChain *> BlockToChainMapType;
64 /// \brief A chain of blocks which will be laid out contiguously.
66 /// This is the datastructure representing a chain of consecutive blocks that
67 /// are profitable to layout together in order to maximize fallthrough
68 /// probabilities. We also can use a block chain to represent a sequence of
69 /// basic blocks which have some external (correctness) requirement for
70 /// sequential layout.
72 /// Eventually, the block chains will form a directed graph over the function.
73 /// We provide an SCC-supporting-iterator in order to quicky build and walk the
74 /// SCCs of block chains within a function.
76 /// The block chains also have support for calculating and caching probability
77 /// information related to the chain itself versus other chains. This is used
78 /// for ranking during the final layout of block chains.
82 /// \brief The first and last basic block that from this chain.
84 /// The chain is stored within the existing function ilist of basic blocks.
85 /// When merging chains or otherwise manipulating them, we splice the blocks
86 /// within this ilist, giving us very cheap storage here and constant time
89 /// It is extremely important to note that LastBB is the iterator pointing
90 /// *at* the last basic block in the chain. That is, the chain consists of
91 /// the *closed* range [FirstBB, LastBB]. We cannot use half-open ranges
92 /// because the next basic block may get relocated to a different part of the
93 /// function at any time during the run of this pass.
94 MachineFunction::iterator FirstBB, LastBB;
96 /// \brief A handle to the function-wide basic block to block chain mapping.
98 /// This is retained in each block chain to simplify the computation of child
99 /// block chains for SCC-formation and iteration. We store the edges to child
100 /// basic blocks, and map them back to their associated chains using this
102 BlockToChainMapType &BlockToChain;
104 /// \brief The weight used to rank two block chains in the same SCC.
106 /// This is used during SCC layout of block chains to cache and rank the
107 /// chains. It is supposed to represent the expected frequency with which
108 /// control reaches a block within this chain, has the option of branching to
109 /// a block in some other chain participating in the SCC, but instead
110 /// continues within this chain. The higher this is, the more costly we
111 /// expect mis-predicted branches between this chain and other chains within
112 /// the SCC to be. Thus, since we expect branches between chains to be
113 /// predicted when backwards and not predicted when forwards, the higher this
114 /// is the more important that this chain is laid out first among those
115 /// chains in the same SCC as it.
116 BlockFrequency InChainEdgeFrequency;
118 /// \brief Construct a new BlockChain.
120 /// This builds a new block chain representing a single basic block in the
121 /// function. It also registers itself as the chain that block participates
122 /// in with the BlockToChain mapping.
123 BlockChain(BlockToChainMapType &BlockToChain, MachineBasicBlock *BB)
124 : FirstBB(BB), LastBB(BB), BlockToChain(BlockToChain) {
125 assert(BB && "Cannot create a chain with a null basic block");
126 BlockToChain[BB] = this;
129 /// \brief Merge another block chain into this one.
131 /// This routine merges a block chain into this one. It takes care of forming
132 /// a contiguous sequence of basic blocks, updating the edge list, and
133 /// updating the block -> chain mapping. It does not free or tear down the
134 /// old chain, but the old chain's block list is no longer valid.
135 void merge(BlockChain *Chain) {
136 assert(Chain && "Cannot merge a null chain");
137 MachineFunction::iterator EndBB = llvm::next(LastBB);
138 MachineFunction::iterator ChainEndBB = llvm::next(Chain->LastBB);
140 // Update the incoming blocks to point to this chain.
141 for (MachineFunction::iterator BI = Chain->FirstBB, BE = ChainEndBB;
143 assert(BlockToChain[BI] == Chain && "Incoming blocks not in chain");
144 BlockToChain[BI] = this;
147 // We splice the blocks together within the function (unless they already
148 // are adjacent) so we can represent the new chain with a pair of pointers
149 // to basic blocks within the function. This is also useful as each chain
150 // of blocks will end up being laid out contiguously within the function.
151 if (EndBB != Chain->FirstBB)
152 FirstBB->getParent()->splice(EndBB, Chain->FirstBB, ChainEndBB);
153 LastBB = Chain->LastBB;
159 /// \brief Successor iterator for BlockChains.
161 /// This is an iterator that walks over the successor block chains by looking
162 /// through its blocks successors and mapping those back to block chains. This
163 /// iterator is not a fully-functioning iterator, it is designed specifically
164 /// to support the interface required by SCCIterator when forming and walking
165 /// SCCs of BlockChains.
167 /// Note that this iterator cannot be used while the chains are still being
168 /// formed and/or merged. Unlike the chains themselves, it does store end
169 /// iterators which could be moved if the chains are re-ordered. Once we begin
170 /// forming and iterating over an SCC of chains, the order of blocks within the
171 /// function must not change until we finish using the SCC iterators.
172 class BlockChain::SuccIterator
173 : public std::iterator<std::forward_iterator_tag,
174 BlockChain *, ptrdiff_t> {
176 MachineFunction::iterator BI, BE;
177 MachineBasicBlock::succ_iterator SI;
180 explicit SuccIterator(BlockChain *Chain)
181 : Chain(Chain), BI(Chain->FirstBB), BE(llvm::next(Chain->LastBB)),
182 SI(BI->succ_begin()) {
183 while (BI != BE && BI->succ_begin() == BI->succ_end())
186 SI = BI->succ_begin();
189 /// \brief Helper function to create an end iterator for a particular chain.
191 /// The "end" state is extremely arbitrary. We chose to have BI == BE, and SI
192 /// == Chain->FirstBB->succ_begin(). The value of SI doesn't really make any
193 /// sense, but rather than try to rationalize SI and our increment, when we
194 /// detect an "end" state, we just immediately call this function to build
195 /// the canonical end iterator.
196 static SuccIterator CreateEnd(BlockChain *Chain) {
197 SuccIterator It(Chain);
202 bool operator==(const SuccIterator &RHS) const {
203 return (Chain == RHS.Chain && BI == RHS.BI && SI == RHS.SI);
205 bool operator!=(const SuccIterator &RHS) const {
206 return !operator==(RHS);
209 SuccIterator& operator++() {
210 assert(*this != CreateEnd(Chain) && "Cannot increment the end iterator");
211 // There may be null successor pointers, skip over them.
212 // FIXME: I don't understand *why* there are null successor pointers.
215 if (SI != BI->succ_end() && *SI)
218 // There may be a basic block without successors. Skip over them.
222 return *this = CreateEnd(Chain);
223 } while (BI->succ_begin() == BI->succ_end());
224 SI = BI->succ_begin();
228 SuccIterator operator++(int) {
229 SuccIterator tmp = *this;
234 BlockChain *operator*() const {
235 assert(Chain->BlockToChain.lookup(*SI) && "Missing chain");
236 return Chain->BlockToChain.lookup(*SI);
242 /// \brief Sorter used with containers of BlockChain pointers.
244 /// Sorts based on the \see BlockChain::InChainEdgeFrequency -- see its
245 /// comments for details on what this ordering represents.
246 struct ChainPtrPrioritySorter {
247 bool operator()(const BlockChain *LHS, const BlockChain *RHS) const {
248 assert(LHS && RHS && "Null chain entry");
249 return LHS->InChainEdgeFrequency < RHS->InChainEdgeFrequency;
255 class MachineBlockPlacement : public MachineFunctionPass {
256 /// \brief A handle to the branch probability pass.
257 const MachineBranchProbabilityInfo *MBPI;
259 /// \brief A handle to the function-wide block frequency pass.
260 const MachineBlockFrequencyInfo *MBFI;
262 /// \brief A handle to the target's instruction info.
263 const TargetInstrInfo *TII;
265 /// \brief A prioritized list of edges in the BB-graph.
267 /// For each function, we insert all control flow edges between BBs, along
268 /// with their "global" frequency. The Frequency of an edge being taken is
269 /// defined as the frequency of entering the source BB (from MBFI) times the
270 /// probability of taking a particular branch out of that block (from MBPI).
272 /// Once built, this list is sorted in ascending frequency, making the last
273 /// edge the hottest one in the function.
274 SmallVector<WeightedEdge, 64> Edges;
276 /// \brief Allocator and owner of BlockChain structures.
278 /// We build BlockChains lazily by merging together high probability BB
279 /// sequences acording to the "Algo2" in the paper mentioned at the top of
280 /// the file. To reduce malloc traffic, we allocate them using this slab-like
281 /// allocator, and destroy them after the pass completes.
282 SpecificBumpPtrAllocator<BlockChain> ChainAllocator;
284 /// \brief Function wide BasicBlock to BlockChain mapping.
286 /// This mapping allows efficiently moving from any given basic block to the
287 /// BlockChain it participates in, if any. We use it to, among other things,
288 /// allow implicitly defining edges between chains as the existing edges
289 /// between basic blocks.
290 DenseMap<MachineBasicBlock *, BlockChain *> BlockToChain;
292 /// \brief A prioritized sequence of chains.
294 /// We build up the ideal sequence of basic block chains in reverse order
295 /// here, and then walk backwards to arrange the final function ordering.
296 SmallVector<BlockChain *, 16> PChains;
299 /// \brief A set of active chains used to sanity-check the pass algorithm.
301 /// All operations on this member should be wrapped in an assert or NDEBUG.
302 SmallPtrSet<BlockChain *, 16> ActiveChains;
305 BlockChain *CreateChain(MachineBasicBlock *BB);
306 void PrioritizeEdges(MachineFunction &F);
307 void BuildBlockChains();
308 void PrioritizeChains(MachineFunction &F);
309 void PlaceBlockChains(MachineFunction &F);
312 static char ID; // Pass identification, replacement for typeid
313 MachineBlockPlacement() : MachineFunctionPass(ID) {
314 initializeMachineBlockPlacementPass(*PassRegistry::getPassRegistry());
317 bool runOnMachineFunction(MachineFunction &F);
319 void getAnalysisUsage(AnalysisUsage &AU) const {
320 AU.addRequired<MachineBranchProbabilityInfo>();
321 AU.addRequired<MachineBlockFrequencyInfo>();
322 MachineFunctionPass::getAnalysisUsage(AU);
325 const char *getPassName() const { return "Block Placement"; }
329 char MachineBlockPlacement::ID = 0;
330 INITIALIZE_PASS_BEGIN(MachineBlockPlacement, "block-placement2",
331 "Branch Probability Basic Block Placement", false, false)
332 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
333 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
334 INITIALIZE_PASS_END(MachineBlockPlacement, "block-placement2",
335 "Branch Probability Basic Block Placement", false, false)
337 FunctionPass *llvm::createMachineBlockPlacementPass() {
338 return new MachineBlockPlacement();
342 /// \brief GraphTraits specialization for our BlockChain graph.
343 template <> struct GraphTraits<BlockChain *> {
344 typedef BlockChain NodeType;
345 typedef BlockChain::SuccIterator ChildIteratorType;
347 static NodeType *getEntryNode(NodeType *N) { return N; }
348 static BlockChain::SuccIterator child_begin(NodeType *N) {
349 return BlockChain::SuccIterator(N);
351 static BlockChain::SuccIterator child_end(NodeType *N) {
352 return BlockChain::SuccIterator::CreateEnd(N);
357 /// \brief Helper to create a new chain for a single BB.
359 /// Takes care of growing the Chains, setting up the BlockChain object, and any
360 /// debug checking logic.
361 /// \returns A pointer to the new BlockChain.
362 BlockChain *MachineBlockPlacement::CreateChain(MachineBasicBlock *BB) {
364 new (ChainAllocator.Allocate()) BlockChain(BlockToChain, BB);
365 assert(ActiveChains.insert(Chain));
369 /// \brief Build a prioritized list of edges.
371 /// The priority is determined by the product of the block frequency (how
372 /// likely it is to arrive at a particular block) times the probability of
373 /// taking this particular edge out of the block. This provides a function-wide
374 /// ordering of the edges.
375 void MachineBlockPlacement::PrioritizeEdges(MachineFunction &F) {
376 assert(Edges.empty() && "Already have an edge list");
377 SmallVector<MachineOperand, 4> Cond; // For AnalyzeBranch.
378 BlockChain *RequiredChain = 0;
379 for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
380 MachineBasicBlock *From = &*FI;
381 // We only consider MBBs with analyzable branches. Even if the analysis
382 // fails, if there is no fallthrough, we can still work with the MBB.
383 MachineBasicBlock *TBB = 0, *FBB = 0;
385 if (TII->AnalyzeBranch(*From, TBB, FBB, Cond) && From->canFallThrough()) {
386 // We push all unanalyzed blocks onto a chain eagerly to prevent them
387 // from being split later. Create the chain if needed, otherwise just
388 // keep track that these blocks reside on it.
390 RequiredChain = CreateChain(From);
392 BlockToChain[From] = RequiredChain;
394 // As soon as we find an analyzable branch, add that block to and
395 // finalize any required chain that has been started. The required chain
396 // is only modeling potentially inexplicable fallthrough, so the first
397 // block to have analyzable fallthrough is a known-safe stopping point.
399 BlockToChain[From] = RequiredChain;
400 RequiredChain->LastBB = FI;
405 BlockFrequency BaseFrequency = MBFI->getBlockFreq(From);
406 for (MachineBasicBlock::succ_iterator SI = From->succ_begin(),
407 SE = From->succ_end();
409 MachineBasicBlock *To = *SI;
410 WeightedEdge WE = { BaseFrequency * MBPI->getEdgeProbability(From, To),
415 assert(!RequiredChain && "Never found a terminator for a required chain");
416 std::stable_sort(Edges.begin(), Edges.end());
419 /// \brief Build chains of basic blocks along hot paths.
421 /// Build chains by trying to merge each pair of blocks from the mostly costly
422 /// edge first. This is essentially "Algo2" from the Profile Guided Code
423 /// Placement paper. While each node is considered a chain of one block, this
424 /// routine lazily build the chain objects themselves so that when possible it
425 /// can just merge a block into an existing chain.
426 void MachineBlockPlacement::BuildBlockChains() {
427 for (SmallVectorImpl<WeightedEdge>::reverse_iterator EI = Edges.rbegin(),
430 MachineBasicBlock *SourceB = EI->From, *DestB = EI->To;
431 if (SourceB == DestB) continue;
433 BlockChain *SourceChain = BlockToChain.lookup(SourceB);
434 if (!SourceChain) SourceChain = CreateChain(SourceB);
435 BlockChain *DestChain = BlockToChain.lookup(DestB);
436 if (!DestChain) DestChain = CreateChain(DestB);
437 if (SourceChain == DestChain)
441 SourceChain->LastBB == MachineFunction::iterator(SourceB);
443 DestChain->FirstBB == MachineFunction::iterator(DestB);
445 if (!IsSourceTail || !IsDestHead)
448 SourceChain->merge(DestChain);
449 assert(ActiveChains.erase(DestChain));
453 /// \brief Prioritize the chains to minimize back-edges between chains.
455 /// This is the trickiest part of the placement algorithm. Each chain is
456 /// a hot-path through a sequence of basic blocks, but there are conditional
457 /// branches away from this hot path, and to some other chain. Hardware branch
458 /// predictors favor back edges over forward edges, and so it is desirable to
459 /// arrange the targets of branches away from a hot path and to some other
460 /// chain to come later in the function, making them forward branches, and
461 /// helping the branch predictor to predict fallthrough.
463 /// In some cases, this is easy. simply topologically walking from the entry
464 /// chain through its successors in order would work if there were no cycles
465 /// between the chains of blocks, but often there are. In such a case, we first
466 /// need to identify the participants in the cycle, and then rank them so that
467 /// the linearizing of the chains has the lowest *probability* of causing
468 /// a mispredicted branch. To compute the correct rank for a chain, we take the
469 /// complement of the branch probability for each branch leading away from the
470 /// chain and multiply it by the frequency of the source block for that branch.
471 /// This gives us the probability of that particular branch *not* being taken
472 /// in this function. The sum of these probabilities for each chain is used as
473 /// a rank, so that we order the chain with the highest such sum first.
474 /// FIXME: This seems like a good approximation, but there is probably a known
475 /// technique for ordering of an SCC given edge weights. It would be good to
476 /// use that, or even use its code if possible.
478 /// Also notable is that we prioritize the chains from the bottom up, and so
479 /// all of the "first" and "before" relationships end up inverted in the code.
480 void MachineBlockPlacement::PrioritizeChains(MachineFunction &F) {
481 MachineBasicBlock *EntryB = &F.front();
482 BlockChain *EntryChain = BlockToChain[EntryB];
483 assert(EntryChain && "Missing chain for entry block");
484 assert(EntryChain->FirstBB == F.begin() &&
485 "Entry block is not the head of the entry block chain");
487 // Form an SCC and walk it from the bottom up.
488 SmallPtrSet<BlockChain *, 4> IsInSCC;
489 for (scc_iterator<BlockChain *> I = scc_begin(EntryChain);
491 const std::vector<BlockChain *> &SCC = *I;
492 PChains.insert(PChains.end(), SCC.begin(), SCC.end());
494 // If there is only one chain in the SCC, it's trivially sorted so just
495 // bail out early. Sorting the SCC is expensive.
499 // We work strictly on the PChains range from here on out to maximize
501 SmallVectorImpl<BlockChain *>::iterator SCCEnd = PChains.end(),
502 SCCBegin = SCCEnd - SCC.size();
504 IsInSCC.insert(SCCBegin, SCCEnd);
506 // Compute the edge frequency of staying in a chain, despite the existency
507 // of an edge to some other chain within this SCC.
508 for (SmallVectorImpl<BlockChain *>::iterator SCCI = SCCBegin;
509 SCCI != SCCEnd; ++SCCI) {
510 BlockChain *Chain = *SCCI;
512 // Special case the entry chain. Regardless of the weights of other
513 // chains, the entry chain *must* come first, so move it to the end, and
514 // avoid processing that chain at all.
515 if (Chain == EntryChain) {
517 if (SCCI == SCCEnd) break;
518 Chain = *SCCI = *SCCEnd;
519 *SCCEnd = EntryChain;
522 // Walk over every block in this chain looking for out-bound edges to
523 // other chains in this SCC.
524 for (MachineFunction::iterator BI = Chain->FirstBB,
525 BE = llvm::next(Chain->LastBB);
527 MachineBasicBlock *From = &*BI;
528 for (MachineBasicBlock::succ_iterator SI = BI->succ_begin(),
531 MachineBasicBlock *To = *SI;
532 if (!To || !IsInSCC.count(BlockToChain[To]))
534 BranchProbability ComplEdgeProb =
535 MBPI->getEdgeProbability(From, To).getCompl();
536 Chain->InChainEdgeFrequency +=
537 MBFI->getBlockFreq(From) * ComplEdgeProb;
542 // Sort the chains within the SCC according to their edge frequencies,
543 // which should make the least costly chain of blocks to mis-place be
544 // ordered first in the prioritized sequence.
545 std::stable_sort(SCCBegin, SCCEnd, ChainPtrPrioritySorter());
549 /// \brief Splice the function blocks together based on the chain priorities.
551 /// Each chain is already represented as a contiguous range of blocks in the
552 /// function. Simply walk backwards down the prioritized chains and splice in
553 /// any chains out of order. Note that the first chain we visit is necessarily
554 /// the entry chain. It has no predecessors and so must be the top of the SCC.
555 /// Also, we cannot splice any chain prior to the entry chain as we can't
556 /// splice any blocks prior to the entry block.
557 void MachineBlockPlacement::PlaceBlockChains(MachineFunction &F) {
558 assert(!PChains.empty() && "No chains were prioritized");
559 assert(PChains.back() == BlockToChain[&F.front()] &&
560 "The entry chain must always be the final chain");
562 MachineFunction::iterator InsertPos = F.begin();
563 for (SmallVectorImpl<BlockChain *>::reverse_iterator CI = PChains.rbegin(),
566 BlockChain *Chain = *CI;
567 // Check that we process this chain only once for debugging.
568 assert(ActiveChains.erase(Chain) && "Processed a chain twice");
570 // If this chain is already in the right position, just skip past it.
571 // Otherwise, splice it into position.
572 if (InsertPos == Chain->FirstBB)
573 InsertPos = llvm::next(Chain->LastBB);
575 F.splice(InsertPos, Chain->FirstBB, llvm::next(Chain->LastBB));
578 // Note that we can't assert this is empty as there may be unreachable blocks
581 ActiveChains.clear();
584 // Now that every block is in its final position, update all of the
586 SmallVector<MachineOperand, 4> Cond; // For AnalyzeBranch.
587 for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
588 // FIXME: It would be awesome of updateTerminator would just return rather
589 // than assert when the branch cannot be analyzed in order to remove this
592 MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch.
593 if (!TII->AnalyzeBranch(*FI, TBB, FBB, Cond))
594 FI->updateTerminator();
598 bool MachineBlockPlacement::runOnMachineFunction(MachineFunction &F) {
599 // Check for single-block functions and skip them.
600 if (llvm::next(F.begin()) == F.end())
603 MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
604 MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
605 TII = F.getTarget().getInstrInfo();
606 assert(Edges.empty());
607 assert(BlockToChain.empty());
608 assert(PChains.empty());
609 assert(ActiveChains.empty());
617 BlockToChain.clear();
619 ChainAllocator.DestroyAll();
621 // We always return true as we have no way to track whether the final order
622 // differs from the original order.