X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FMachineBlockPlacement.cpp;h=2969bad4ff98b1decb94da8c5c8af02613693393;hb=008a1efecf4bc7f142dda936f79783c69524776e;hp=3eb2998116d0e1bf225d8f18a860ba51863dddee;hpb=9fd4e056e433b286f0e6576046ef2242365bfc38;p=oota-llvm.git diff --git a/lib/CodeGen/MachineBlockPlacement.cpp b/lib/CodeGen/MachineBlockPlacement.cpp index 3eb2998116d..2969bad4ff9 100644 --- a/lib/CodeGen/MachineBlockPlacement.cpp +++ b/lib/CodeGen/MachineBlockPlacement.cpp @@ -11,7 +11,7 @@ // structure and branch probability estimates. // // 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 +// a topological ordering of basic blocks) in the absence 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. @@ -25,29 +25,31 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "block-placement2" +#include "llvm/CodeGen/Passes.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" +#include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineModuleInfo.h" -#include "llvm/CodeGen/Passes.h" #include "llvm/Support/Allocator.h" +#include "llvm/Support/CommandLine.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" -#include "llvm/ADT/Statistic.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetLowering.h" +#include "llvm/Target/TargetSubtargetInfo.h" #include using namespace llvm; +#define DEBUG_TYPE "block-placement" + STATISTIC(NumCondBranches, "Number of conditional branches"); STATISTIC(NumUncondBranches, "Number of uncondittional branches"); STATISTIC(CondBranchTakenFreq, @@ -55,21 +57,29 @@ STATISTIC(CondBranchTakenFreq, STATISTIC(UncondBranchTakenFreq, "Potential frequency of taking unconditional branches"); -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; - } -}; -} +static cl::opt AlignAllBlock("align-all-blocks", + cl::desc("Force the alignment of all " + "blocks in the function."), + cl::init(0), cl::Hidden); + +// FIXME: Find a good default for this flag and remove the flag. +static cl::opt ExitBlockBias( + "block-placement-exit-block-bias", + cl::desc("Block frequency percentage a loop exit block needs " + "over the original exit to be considered the new exit."), + cl::init(0), cl::Hidden); + +static cl::opt OutlineOptionalBranches( + "outline-optional-branches", + cl::desc("Put completely optional branches, i.e. branches with a common " + "post dominator, out of line."), + cl::init(false), cl::Hidden); + +static cl::opt OutlineOptionalThreshold( + "outline-optional-threshold", + cl::desc("Don't outline optional branches that are a single block with an " + "instruction count below this threshold"), + cl::init(4), cl::Hidden); namespace { class BlockChain; @@ -82,17 +92,13 @@ namespace { /// /// 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. +/// probabilities and code locality. 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. +/// Chains can be built around a single basic block and can be merged to grow +/// them. They participate in a block-to-chain mapping, which is updated +/// automatically as chains are merged together. class BlockChain { /// \brief The sequence of blocks belonging to this chain. /// @@ -115,19 +121,19 @@ public: /// function. It also registers itself as the chain that block participates /// in with the BlockToChain mapping. BlockChain(BlockToChainMapType &BlockToChain, MachineBasicBlock *BB) - : Blocks(1, BB), BlockToChain(BlockToChain), LoopPredecessors(0) { + : Blocks(1, BB), BlockToChain(BlockToChain), LoopPredecessors(0) { assert(BB && "Cannot create a chain with a null basic block"); BlockToChain[BB] = this; } /// \brief Iterator over blocks within the chain. - typedef SmallVectorImpl::const_iterator iterator; + typedef SmallVectorImpl::iterator iterator; /// \brief Beginning of blocks within the chain. - iterator begin() const { return Blocks.begin(); } + iterator begin() { return Blocks.begin(); } /// \brief End of blocks within the chain. - iterator end() const { return Blocks.end(); } + iterator end() { return Blocks.end(); } /// \brief Merge a block chain into this one. /// @@ -152,14 +158,21 @@ public: // 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; + for (MachineBasicBlock *ChainBB : *Chain) { + Blocks.push_back(ChainBB); + assert(BlockToChain[ChainBB] == Chain && "Incoming blocks not in chain"); + BlockToChain[ChainBB] = this; } } +#ifndef NDEBUG + /// \brief Dump the blocks in this chain. + LLVM_DUMP_METHOD void dump() { + for (MachineBasicBlock *MBB : *this) + MBB->dump(); + } +#endif // NDEBUG + /// \brief Count of predecessors within the loop currently being processed. /// /// This count is updated at each loop we process to represent the number of @@ -186,14 +199,22 @@ class MachineBlockPlacement : public MachineFunctionPass { const TargetInstrInfo *TII; /// \brief A handle to the target's lowering info. - const TargetLowering *TLI; + const TargetLoweringBase *TLI; + + /// \brief A handle to the post dominator tree. + MachineDominatorTree *MDT; + + /// \brief A set of blocks that are unavoidably execute, i.e. they dominate + /// all terminators of the MachineFunction. + SmallPtrSet UnavoidableBlocks; /// \brief Allocator and owner of BlockChain structures. /// - /// We build BlockChains lazily by merging together high probability BB - /// sequences acording to the "Algo2" in the paper mentioned at the top of - /// the file. To reduce malloc traffic, we allocate them using this slab-like - /// allocator, and destroy them after the pass completes. + /// We build BlockChains lazily while processing the loop structure of + /// a function. To reduce malloc traffic, we allocate them using this + /// slab-like allocator, and destroy them after the pass completes. An + /// important guarantee is that this allocator produces stable pointers to + /// the chains. SpecificBumpPtrAllocator ChainAllocator; /// \brief Function wide BasicBlock to BlockChain mapping. @@ -204,19 +225,31 @@ class MachineBlockPlacement : public MachineFunctionPass { /// between basic blocks. DenseMap BlockToChain; - void markChainSuccessors(BlockChain &Chain, - MachineBasicBlock *LoopHeaderBB, - SmallVectorImpl &Blocks, - const BlockFilterSet *BlockFilter = 0); + void markChainSuccessors(BlockChain &Chain, MachineBasicBlock *LoopHeaderBB, + SmallVectorImpl &BlockWorkList, + const BlockFilterSet *BlockFilter = nullptr); MachineBasicBlock *selectBestSuccessor(MachineBasicBlock *BB, BlockChain &Chain, const BlockFilterSet *BlockFilter); + MachineBasicBlock * + selectBestCandidateBlock(BlockChain &Chain, + SmallVectorImpl &WorkList, + const BlockFilterSet *BlockFilter); + MachineBasicBlock * + getFirstUnplacedBlock(MachineFunction &F, const BlockChain &PlacedChain, + MachineFunction::iterator &PrevUnplacedBlockIt, + const BlockFilterSet *BlockFilter); void buildChain(MachineBasicBlock *BB, BlockChain &Chain, - SmallVectorImpl &Blocks, - const BlockFilterSet *BlockFilter = 0); + SmallVectorImpl &BlockWorkList, + const BlockFilterSet *BlockFilter = nullptr); + MachineBasicBlock *findBestLoopTop(MachineLoop &L, + const BlockFilterSet &LoopBlockSet); + MachineBasicBlock *findBestLoopExit(MachineFunction &F, MachineLoop &L, + const BlockFilterSet &LoopBlockSet); void buildLoopChains(MachineFunction &F, MachineLoop &L); + void rotateLoop(BlockChain &LoopChain, MachineBasicBlock *ExitingBB, + const BlockFilterSet &LoopBlockSet); void buildCFGChains(MachineFunction &F); - void AlignLoops(MachineFunction &F); public: static char ID; // Pass identification, replacement for typeid @@ -224,32 +257,29 @@ public: initializeMachineBlockPlacementPass(*PassRegistry::getPassRegistry()); } - bool runOnMachineFunction(MachineFunction &F); + bool runOnMachineFunction(MachineFunction &F) override; - void getAnalysisUsage(AnalysisUsage &AU) const { + void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired(); AU.addRequired(); + AU.addRequired(); AU.addRequired(); MachineFunctionPass::getAnalysisUsage(AU); } - - const char *getPassName() const { return "Block Placement"; } }; } char MachineBlockPlacement::ID = 0; -INITIALIZE_PASS_BEGIN(MachineBlockPlacement, "block-placement2", +char &llvm::MachineBlockPlacementID = MachineBlockPlacement::ID; +INITIALIZE_PASS_BEGIN(MachineBlockPlacement, "block-placement", "Branch Probability Basic Block Placement", false, false) INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) +INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) -INITIALIZE_PASS_END(MachineBlockPlacement, "block-placement2", +INITIALIZE_PASS_END(MachineBlockPlacement, "block-placement", "Branch Probability Basic Block Placement", false, false) -FunctionPass *llvm::createMachineBlockPlacementPass() { - return new MachineBlockPlacement(); -} - #ifndef NDEBUG /// \brief Helper to print the name of a MBB. /// @@ -257,8 +287,8 @@ FunctionPass *llvm::createMachineBlockPlacementPass() { 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 << "BB#" << BB->getNumber(); + OS << " (derived from LLVM BB '" << BB->getName() << "')"; OS.flush(); return Result; } @@ -275,33 +305,35 @@ static std::string getBlockNum(MachineBasicBlock *BB) { } #endif +/// \brief Mark a chain's successors as having one fewer preds. +/// +/// When a chain is being merged into the "placed" chain, this routine will +/// quickly walk the successors of each block in the chain and mark them as +/// having one fewer active predecessor. It also adds any successors of this +/// chain which reach the zero-predecessor state to the worklist passed in. void MachineBlockPlacement::markChainSuccessors( - BlockChain &Chain, - MachineBasicBlock *LoopHeaderBB, + BlockChain &Chain, MachineBasicBlock *LoopHeaderBB, SmallVectorImpl &BlockWorkList, const BlockFilterSet *BlockFilter) { // Walk all the blocks in this chain, marking their successors as having // a predecessor placed. - for (BlockChain::iterator CBI = Chain.begin(), CBE = Chain.end(); - CBI != CBE; ++CBI) { + for (MachineBasicBlock *MBB : Chain) { // Add any successors for which this is the only un-placed in-loop // predecessor to the worklist as a viable candidate for CFG-neutral // placement. No subsequent placement of this block will violate the CFG // shape, so we get to use heuristics to choose a favorable placement. - for (MachineBasicBlock::succ_iterator SI = (*CBI)->succ_begin(), - SE = (*CBI)->succ_end(); - SI != SE; ++SI) { - if (BlockFilter && !BlockFilter->count(*SI)) + for (MachineBasicBlock *Succ : MBB->successors()) { + if (BlockFilter && !BlockFilter->count(Succ)) continue; - BlockChain &SuccChain = *BlockToChain[*SI]; + BlockChain &SuccChain = *BlockToChain[Succ]; // Disregard edges within a fixed chain, or edges to the loop header. - if (&Chain == &SuccChain || *SI == LoopHeaderBB) + if (&Chain == &SuccChain || Succ == LoopHeaderBB) continue; // This is a cross-chain edge that is within the loop, so decrement the // loop predecessor count of the destination chain. if (SuccChain.LoopPredecessors > 0 && --SuccChain.LoopPredecessors == 0) - BlockWorkList.push_back(*SI); + BlockWorkList.push_back(*SuccChain.begin()); } } } @@ -315,61 +347,193 @@ void MachineBlockPlacement::markChainSuccessors( /// very hot successor edges. /// /// \returns The best successor block found, or null if none are viable. -MachineBasicBlock *MachineBlockPlacement::selectBestSuccessor( - MachineBasicBlock *BB, BlockChain &Chain, - const BlockFilterSet *BlockFilter) { +MachineBasicBlock * +MachineBlockPlacement::selectBestSuccessor(MachineBasicBlock *BB, + BlockChain &Chain, + const BlockFilterSet *BlockFilter) { const BranchProbability HotProb(4, 5); // 80% - MachineBasicBlock *BestSucc = 0; - BranchProbability BestProb = BranchProbability::getZero(); + MachineBasicBlock *BestSucc = nullptr; + // FIXME: Due to the performance of the probability and weight routines in + // the MBPI analysis, we manually compute probabilities using the edge + // weights. This is suboptimal as it means that the somewhat subtle + // definition of edge weight semantics is encoded here as well. We should + // improve the MBPI interface to efficiently support query patterns such as + // this. + uint32_t BestWeight = 0; + uint32_t WeightScale = 0; + uint32_t SumWeight = MBPI->getSumForBlock(BB, WeightScale); DEBUG(dbgs() << "Attempting merge from: " << getBlockName(BB) << "\n"); - for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), - SE = BB->succ_end(); - SI != SE; ++SI) { - if (BlockFilter && !BlockFilter->count(*SI)) + for (MachineBasicBlock *Succ : BB->successors()) { + if (BlockFilter && !BlockFilter->count(Succ)) continue; - BlockChain &SuccChain = *BlockToChain[*SI]; + BlockChain &SuccChain = *BlockToChain[Succ]; if (&SuccChain == &Chain) { - DEBUG(dbgs() << " " << getBlockName(*SI) << " -> Already merged!\n"); + DEBUG(dbgs() << " " << getBlockName(Succ) << " -> Already merged!\n"); + continue; + } + if (Succ != *SuccChain.begin()) { + DEBUG(dbgs() << " " << getBlockName(Succ) << " -> Mid chain!\n"); continue; } - BranchProbability SuccProb = MBPI->getEdgeProbability(BB, *SI); + uint32_t SuccWeight = MBPI->getEdgeWeight(BB, Succ); + BranchProbability SuccProb(SuccWeight / WeightScale, SumWeight); + + // If we outline optional branches, look whether Succ is unavoidable, i.e. + // dominates all terminators of the MachineFunction. If it does, other + // successors must be optional. Don't do this for cold branches. + if (OutlineOptionalBranches && SuccProb > HotProb.getCompl() && + UnavoidableBlocks.count(Succ) > 0) { + auto HasShortOptionalBranch = [&]() { + for (MachineBasicBlock *Pred : Succ->predecessors()) { + // Check whether there is an unplaced optional branch. + if (Pred == Succ || (BlockFilter && !BlockFilter->count(Pred)) || + BlockToChain[Pred] == &Chain) + continue; + // Check whether the optional branch has exactly one BB. + if (Pred->pred_size() > 1 || *Pred->pred_begin() != BB) + continue; + // Check whether the optional branch is small. + if (Pred->size() < OutlineOptionalThreshold) + return true; + } + return false; + }; + if (!HasShortOptionalBranch()) + return Succ; + } // Only consider successors which are either "hot", or wouldn't violate // any CFG constraints. - if (SuccChain.LoopPredecessors != 0 && SuccProb < HotProb) { - DEBUG(dbgs() << " " << getBlockName(*SI) << " -> CFG conflict\n"); - continue; + if (SuccChain.LoopPredecessors != 0) { + if (SuccProb < HotProb) { + DEBUG(dbgs() << " " << getBlockName(Succ) << " -> " << SuccProb + << " (prob) (CFG conflict)\n"); + continue; + } + + // Make sure that a hot successor doesn't have a globally more + // important predecessor. + BlockFrequency CandidateEdgeFreq = + MBFI->getBlockFreq(BB) * SuccProb * HotProb.getCompl(); + bool BadCFGConflict = false; + for (MachineBasicBlock *Pred : Succ->predecessors()) { + if (Pred == Succ || (BlockFilter && !BlockFilter->count(Pred)) || + BlockToChain[Pred] == &Chain) + continue; + BlockFrequency PredEdgeFreq = + MBFI->getBlockFreq(Pred) * MBPI->getEdgeProbability(Pred, Succ); + if (PredEdgeFreq >= CandidateEdgeFreq) { + BadCFGConflict = true; + break; + } + } + if (BadCFGConflict) { + DEBUG(dbgs() << " " << getBlockName(Succ) << " -> " << SuccProb + << " (prob) (non-cold CFG conflict)\n"); + continue; + } } - DEBUG(dbgs() << " " << getBlockName(*SI) << " -> " << SuccProb + DEBUG(dbgs() << " " << getBlockName(Succ) << " -> " << SuccProb << " (prob)" << (SuccChain.LoopPredecessors != 0 ? " (CFG break)" : "") << "\n"); - if (BestSucc && BestProb >= SuccProb) + if (BestSucc && BestWeight >= SuccWeight) continue; - BestSucc = *SI; - BestProb = SuccProb; + BestSucc = Succ; + BestWeight = SuccWeight; } return BestSucc; } +/// \brief Select the best block from a worklist. +/// +/// This looks through the provided worklist as a list of candidate basic +/// blocks and select the most profitable one to place. The definition of +/// profitable only really makes sense in the context of a loop. This returns +/// the most frequently visited block in the worklist, which in the case of +/// a loop, is the one most desirable to be physically close to the rest of the +/// loop body in order to improve icache behavior. +/// +/// \returns The best block found, or null if none are viable. +MachineBasicBlock *MachineBlockPlacement::selectBestCandidateBlock( + BlockChain &Chain, SmallVectorImpl &WorkList, + const BlockFilterSet *BlockFilter) { + // Once we need to walk the worklist looking for a candidate, cleanup the + // worklist of already placed entries. + // FIXME: If this shows up on profiles, it could be folded (at the cost of + // some code complexity) into the loop below. + WorkList.erase(std::remove_if(WorkList.begin(), WorkList.end(), + [&](MachineBasicBlock *BB) { + return BlockToChain.lookup(BB) == &Chain; + }), + WorkList.end()); + + MachineBasicBlock *BestBlock = nullptr; + BlockFrequency BestFreq; + for (MachineBasicBlock *MBB : WorkList) { + BlockChain &SuccChain = *BlockToChain[MBB]; + if (&SuccChain == &Chain) { + DEBUG(dbgs() << " " << getBlockName(MBB) << " -> Already merged!\n"); + continue; + } + assert(SuccChain.LoopPredecessors == 0 && "Found CFG-violating block"); + + BlockFrequency CandidateFreq = MBFI->getBlockFreq(MBB); + DEBUG(dbgs() << " " << getBlockName(MBB) << " -> "; + MBFI->printBlockFreq(dbgs(), CandidateFreq) << " (freq)\n"); + if (BestBlock && BestFreq >= CandidateFreq) + continue; + BestBlock = MBB; + BestFreq = CandidateFreq; + } + return BestBlock; +} + +/// \brief Retrieve the first unplaced basic block. +/// +/// This routine is called when we are unable to use the CFG to walk through +/// all of the basic blocks and form a chain due to unnatural loops in the CFG. +/// We walk through the function's blocks in order, starting from the +/// LastUnplacedBlockIt. We update this iterator on each call to avoid +/// re-scanning the entire sequence on repeated calls to this routine. +MachineBasicBlock *MachineBlockPlacement::getFirstUnplacedBlock( + MachineFunction &F, const BlockChain &PlacedChain, + MachineFunction::iterator &PrevUnplacedBlockIt, + const BlockFilterSet *BlockFilter) { + for (MachineFunction::iterator I = PrevUnplacedBlockIt, E = F.end(); I != E; + ++I) { + if (BlockFilter && !BlockFilter->count(I)) + continue; + if (BlockToChain[I] != &PlacedChain) { + PrevUnplacedBlockIt = I; + // Now select the head of the chain to which the unplaced block belongs + // as the block to place. This will force the entire chain to be placed, + // and satisfies the requirements of merging chains. + return *BlockToChain[I]->begin(); + } + } + return nullptr; +} + void MachineBlockPlacement::buildChain( - MachineBasicBlock *BB, - BlockChain &Chain, + MachineBasicBlock *BB, BlockChain &Chain, SmallVectorImpl &BlockWorkList, const BlockFilterSet *BlockFilter) { assert(BB); assert(BlockToChain[BB] == &Chain); - assert(*Chain.begin() == BB); + MachineFunction &F = *BB->getParent(); + MachineFunction::iterator PrevUnplacedBlockIt = F.begin(); + MachineBasicBlock *LoopHeaderBB = BB; markChainSuccessors(Chain, LoopHeaderBB, BlockWorkList, BlockFilter); - BB = *llvm::prior(Chain.end()); + BB = *std::prev(Chain.end()); for (;;) { assert(BB); assert(BlockToChain[BB] == &Chain); - assert(*llvm::prior(Chain.end()) == BB); + assert(*std::prev(Chain.end()) == BB); // Look for the best viable successor if there is one to place immediately // after this block. @@ -378,44 +542,253 @@ void MachineBlockPlacement::buildChain( // If an immediate successor isn't available, look for the best viable // block among those we've identified as not violating the loop's CFG at // this point. This won't be a fallthrough, but it will increase locality. - if (!BestSucc) { - BlockFrequency BestFreq; - for (SmallVectorImpl::iterator WBI = BlockWorkList.begin(), - WBE = BlockWorkList.end(); - WBI != WBE; ++WBI) { - if (BlockFilter && !BlockFilter->count(*WBI)) - continue; - BlockChain &SuccChain = *BlockToChain[*WBI]; - if (&SuccChain == &Chain) { - DEBUG(dbgs() << " " << getBlockName(*WBI) - << " -> Already merged!\n"); - continue; - } - assert(SuccChain.LoopPredecessors == 0 && "Found CFG-violating block"); + if (!BestSucc) + BestSucc = selectBestCandidateBlock(Chain, BlockWorkList, BlockFilter); - BlockFrequency CandidateFreq = MBFI->getBlockFreq(*WBI); - DEBUG(dbgs() << " " << getBlockName(*WBI) << " -> " << CandidateFreq - << " (freq)\n"); - if (BestSucc && BestFreq >= CandidateFreq) - continue; - BestSucc = *WBI; - BestFreq = CandidateFreq; - } - } if (!BestSucc) { - DEBUG(dbgs() << "Finished forming chain for header block " - << getBlockNum(*Chain.begin()) << "\n"); - return; + BestSucc = + getFirstUnplacedBlock(F, Chain, PrevUnplacedBlockIt, BlockFilter); + if (!BestSucc) + break; + + DEBUG(dbgs() << "Unnatural loop CFG detected, forcibly merging the " + "layout successor until the CFG reduces\n"); } // Place this block, updating the datastructures to reflect its placement. BlockChain &SuccChain = *BlockToChain[BestSucc]; - DEBUG(dbgs() << "Merging from " << getBlockNum(BB) - << " to " << getBlockNum(BestSucc) << "\n"); + // Zero out LoopPredecessors for the successor we're about to merge in case + // we selected a successor that didn't fit naturally into the CFG. + SuccChain.LoopPredecessors = 0; + DEBUG(dbgs() << "Merging from " << getBlockNum(BB) << " to " + << getBlockNum(BestSucc) << "\n"); markChainSuccessors(SuccChain, LoopHeaderBB, BlockWorkList, BlockFilter); Chain.merge(BestSucc, &SuccChain); - BB = *llvm::prior(Chain.end()); + BB = *std::prev(Chain.end()); + } + + DEBUG(dbgs() << "Finished forming chain for header block " + << getBlockNum(*Chain.begin()) << "\n"); +} + +/// \brief Find the best loop top block for layout. +/// +/// Look for a block which is strictly better than the loop header for laying +/// out at the top of the loop. This looks for one and only one pattern: +/// a latch block with no conditional exit. This block will cause a conditional +/// jump around it or will be the bottom of the loop if we lay it out in place, +/// but if it it doesn't end up at the bottom of the loop for any reason, +/// rotation alone won't fix it. Because such a block will always result in an +/// unconditional jump (for the backedge) rotating it in front of the loop +/// header is always profitable. +MachineBasicBlock * +MachineBlockPlacement::findBestLoopTop(MachineLoop &L, + const BlockFilterSet &LoopBlockSet) { + // Check that the header hasn't been fused with a preheader block due to + // crazy branches. If it has, we need to start with the header at the top to + // prevent pulling the preheader into the loop body. + BlockChain &HeaderChain = *BlockToChain[L.getHeader()]; + if (!LoopBlockSet.count(*HeaderChain.begin())) + return L.getHeader(); + + DEBUG(dbgs() << "Finding best loop top for: " << getBlockName(L.getHeader()) + << "\n"); + + BlockFrequency BestPredFreq; + MachineBasicBlock *BestPred = nullptr; + for (MachineBasicBlock *Pred : L.getHeader()->predecessors()) { + if (!LoopBlockSet.count(Pred)) + continue; + DEBUG(dbgs() << " header pred: " << getBlockName(Pred) << ", " + << Pred->succ_size() << " successors, "; + MBFI->printBlockFreq(dbgs(), Pred) << " freq\n"); + if (Pred->succ_size() > 1) + continue; + + BlockFrequency PredFreq = MBFI->getBlockFreq(Pred); + if (!BestPred || PredFreq > BestPredFreq || + (!(PredFreq < BestPredFreq) && + Pred->isLayoutSuccessor(L.getHeader()))) { + BestPred = Pred; + BestPredFreq = PredFreq; + } + } + + // If no direct predecessor is fine, just use the loop header. + if (!BestPred) + return L.getHeader(); + + // Walk backwards through any straight line of predecessors. + while (BestPred->pred_size() == 1 && + (*BestPred->pred_begin())->succ_size() == 1 && + *BestPred->pred_begin() != L.getHeader()) + BestPred = *BestPred->pred_begin(); + + DEBUG(dbgs() << " final top: " << getBlockName(BestPred) << "\n"); + return BestPred; +} + +/// \brief Find the best loop exiting block for layout. +/// +/// This routine implements the logic to analyze the loop looking for the best +/// block to layout at the top of the loop. Typically this is done to maximize +/// fallthrough opportunities. +MachineBasicBlock * +MachineBlockPlacement::findBestLoopExit(MachineFunction &F, MachineLoop &L, + const BlockFilterSet &LoopBlockSet) { + // We don't want to layout the loop linearly in all cases. If the loop header + // is just a normal basic block in the loop, we want to look for what block + // within the loop is the best one to layout at the top. However, if the loop + // header has be pre-merged into a chain due to predecessors not having + // analyzable branches, *and* the predecessor it is merged with is *not* part + // of the loop, rotating the header into the middle of the loop will create + // a non-contiguous range of blocks which is Very Bad. So start with the + // header and only rotate if safe. + BlockChain &HeaderChain = *BlockToChain[L.getHeader()]; + if (!LoopBlockSet.count(*HeaderChain.begin())) + return nullptr; + + BlockFrequency BestExitEdgeFreq; + unsigned BestExitLoopDepth = 0; + MachineBasicBlock *ExitingBB = nullptr; + // If there are exits to outer loops, loop rotation can severely limit + // fallthrough opportunites unless it selects such an exit. Keep a set of + // blocks where rotating to exit with that block will reach an outer loop. + SmallPtrSet BlocksExitingToOuterLoop; + + DEBUG(dbgs() << "Finding best loop exit for: " << getBlockName(L.getHeader()) + << "\n"); + for (MachineBasicBlock *MBB : L.getBlocks()) { + BlockChain &Chain = *BlockToChain[MBB]; + // Ensure that this block is at the end of a chain; otherwise it could be + // mid-way through an inner loop or a successor of an unanalyzable branch. + if (MBB != *std::prev(Chain.end())) + continue; + + // Now walk the successors. We need to establish whether this has a viable + // exiting successor and whether it has a viable non-exiting successor. + // We store the old exiting state and restore it if a viable looping + // successor isn't found. + MachineBasicBlock *OldExitingBB = ExitingBB; + BlockFrequency OldBestExitEdgeFreq = BestExitEdgeFreq; + bool HasLoopingSucc = false; + // FIXME: Due to the performance of the probability and weight routines in + // the MBPI analysis, we use the internal weights and manually compute the + // probabilities to avoid quadratic behavior. + uint32_t WeightScale = 0; + uint32_t SumWeight = MBPI->getSumForBlock(MBB, WeightScale); + for (MachineBasicBlock *Succ : MBB->successors()) { + if (Succ->isLandingPad()) + continue; + if (Succ == MBB) + continue; + BlockChain &SuccChain = *BlockToChain[Succ]; + // Don't split chains, either this chain or the successor's chain. + if (&Chain == &SuccChain) { + DEBUG(dbgs() << " exiting: " << getBlockName(MBB) << " -> " + << getBlockName(Succ) << " (chain conflict)\n"); + continue; + } + + uint32_t SuccWeight = MBPI->getEdgeWeight(MBB, Succ); + if (LoopBlockSet.count(Succ)) { + DEBUG(dbgs() << " looping: " << getBlockName(MBB) << " -> " + << getBlockName(Succ) << " (" << SuccWeight << ")\n"); + HasLoopingSucc = true; + continue; + } + + unsigned SuccLoopDepth = 0; + if (MachineLoop *ExitLoop = MLI->getLoopFor(Succ)) { + SuccLoopDepth = ExitLoop->getLoopDepth(); + if (ExitLoop->contains(&L)) + BlocksExitingToOuterLoop.insert(MBB); + } + + BranchProbability SuccProb(SuccWeight / WeightScale, SumWeight); + BlockFrequency ExitEdgeFreq = MBFI->getBlockFreq(MBB) * SuccProb; + DEBUG(dbgs() << " exiting: " << getBlockName(MBB) << " -> " + << getBlockName(Succ) << " [L:" << SuccLoopDepth << "] ("; + MBFI->printBlockFreq(dbgs(), ExitEdgeFreq) << ")\n"); + // Note that we bias this toward an existing layout successor to retain + // incoming order in the absence of better information. The exit must have + // a frequency higher than the current exit before we consider breaking + // the layout. + BranchProbability Bias(100 - ExitBlockBias, 100); + if (!ExitingBB || SuccLoopDepth > BestExitLoopDepth || + ExitEdgeFreq > BestExitEdgeFreq || + (MBB->isLayoutSuccessor(Succ) && + !(ExitEdgeFreq < BestExitEdgeFreq * Bias))) { + BestExitEdgeFreq = ExitEdgeFreq; + ExitingBB = MBB; + } + } + + if (!HasLoopingSucc) { + // Restore the old exiting state, no viable looping successor was found. + ExitingBB = OldExitingBB; + BestExitEdgeFreq = OldBestExitEdgeFreq; + continue; + } } + // Without a candidate exiting block or with only a single block in the + // loop, just use the loop header to layout the loop. + if (!ExitingBB || L.getNumBlocks() == 1) + return nullptr; + + // Also, if we have exit blocks which lead to outer loops but didn't select + // one of them as the exiting block we are rotating toward, disable loop + // rotation altogether. + if (!BlocksExitingToOuterLoop.empty() && + !BlocksExitingToOuterLoop.count(ExitingBB)) + return nullptr; + + DEBUG(dbgs() << " Best exiting block: " << getBlockName(ExitingBB) << "\n"); + return ExitingBB; +} + +/// \brief Attempt to rotate an exiting block to the bottom of the loop. +/// +/// Once we have built a chain, try to rotate it to line up the hot exit block +/// with fallthrough out of the loop if doing so doesn't introduce unnecessary +/// branches. For example, if the loop has fallthrough into its header and out +/// of its bottom already, don't rotate it. +void MachineBlockPlacement::rotateLoop(BlockChain &LoopChain, + MachineBasicBlock *ExitingBB, + const BlockFilterSet &LoopBlockSet) { + if (!ExitingBB) + return; + + MachineBasicBlock *Top = *LoopChain.begin(); + bool ViableTopFallthrough = false; + for (MachineBasicBlock *Pred : Top->predecessors()) { + BlockChain *PredChain = BlockToChain[Pred]; + if (!LoopBlockSet.count(Pred) && + (!PredChain || Pred == *std::prev(PredChain->end()))) { + ViableTopFallthrough = true; + break; + } + } + + // If the header has viable fallthrough, check whether the current loop + // bottom is a viable exiting block. If so, bail out as rotating will + // introduce an unnecessary branch. + if (ViableTopFallthrough) { + MachineBasicBlock *Bottom = *std::prev(LoopChain.end()); + for (MachineBasicBlock *Succ : Bottom->successors()) { + BlockChain *SuccChain = BlockToChain[Succ]; + if (!LoopBlockSet.count(Succ) && + (!SuccChain || Succ == *SuccChain->begin())) + return; + } + } + + BlockChain::iterator ExitIt = + std::find(LoopChain.begin(), LoopChain.end(), ExitingBB); + if (ExitIt == LoopChain.end()) + return; + + std::rotate(LoopChain.begin(), std::next(ExitIt), LoopChain.end()); } /// \brief Forms basic block chains from the natural loop structures. @@ -428,198 +801,355 @@ 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); + for (MachineLoop *InnerLoop : L) + buildLoopChains(F, *InnerLoop); SmallVector BlockWorkList; BlockFilterSet LoopBlockSet(L.block_begin(), L.block_end()); + // First check to see if there is an obviously preferable top block for the + // loop. This will default to the header, but may end up as one of the + // predecessors to the header if there is one which will result in strictly + // fewer branches in the loop body. + MachineBasicBlock *LoopTop = findBestLoopTop(L, LoopBlockSet); + + // If we selected just the header for the loop top, look for a potentially + // profitable exit block in the event that rotating the loop can eliminate + // branches by placing an exit edge at the bottom. + MachineBasicBlock *ExitingBB = nullptr; + if (LoopTop == L.getHeader()) + ExitingBB = findBestLoopExit(F, L, LoopBlockSet); + + BlockChain &LoopChain = *BlockToChain[LoopTop]; + // FIXME: This is a really lame way of walking the chains in the loop: we // walk the blocks, and use a set to prevent visiting a particular chain // twice. SmallPtrSet UpdatedPreds; - for (MachineLoop::block_iterator BI = L.block_begin(), - BE = L.block_end(); - BI != BE; ++BI) { - BlockChain &Chain = *BlockToChain[*BI]; - if (!UpdatedPreds.insert(&Chain) || BI == L.block_begin()) + assert(LoopChain.LoopPredecessors == 0); + UpdatedPreds.insert(&LoopChain); + for (MachineBasicBlock *LoopBB : L.getBlocks()) { + BlockChain &Chain = *BlockToChain[LoopBB]; + if (!UpdatedPreds.insert(&Chain).second) continue; assert(Chain.LoopPredecessors == 0); - for (BlockChain::iterator BCI = Chain.begin(), BCE = Chain.end(); - BCI != BCE; ++BCI) { - assert(BlockToChain[*BCI] == &Chain); - for (MachineBasicBlock::pred_iterator PI = (*BCI)->pred_begin(), - PE = (*BCI)->pred_end(); - PI != PE; ++PI) { - if (BlockToChain[*PI] == &Chain || !LoopBlockSet.count(*PI)) + for (MachineBasicBlock *ChainBB : Chain) { + assert(BlockToChain[ChainBB] == &Chain); + for (MachineBasicBlock *Pred : ChainBB->predecessors()) { + if (BlockToChain[Pred] == &Chain || !LoopBlockSet.count(Pred)) continue; ++Chain.LoopPredecessors; } } if (Chain.LoopPredecessors == 0) - BlockWorkList.push_back(*BI); + BlockWorkList.push_back(*Chain.begin()); } - BlockChain &LoopChain = *BlockToChain[L.getHeader()]; - buildChain(*L.block_begin(), LoopChain, BlockWorkList, &LoopBlockSet); + buildChain(LoopTop, LoopChain, BlockWorkList, &LoopBlockSet); + rotateLoop(LoopChain, ExitingBB, LoopBlockSet); DEBUG({ - if (LoopChain.LoopPredecessors) + // Crash at the end so we get all of the debugging output first. + bool BadLoop = false; + if (LoopChain.LoopPredecessors) { + BadLoop = true; dbgs() << "Loop chain contains a block without its preds placed!\n" << " Loop header: " << getBlockName(*L.block_begin()) << "\n" << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n"; - for (BlockChain::iterator BCI = LoopChain.begin(), BCE = LoopChain.end(); - BCI != BCE; ++BCI) - if (!LoopBlockSet.erase(*BCI)) + } + for (MachineBasicBlock *ChainBB : LoopChain) { + dbgs() << " ... " << getBlockName(ChainBB) << "\n"; + if (!LoopBlockSet.erase(ChainBB)) { + // We don't mark the loop as bad here because there are real situations + // where this can occur. For example, with an unanalyzable fallthrough + // from a loop block to a non-loop block or vice versa. dbgs() << "Loop chain contains a block not contained by the loop!\n" << " Loop header: " << getBlockName(*L.block_begin()) << "\n" << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n" - << " Bad block: " << getBlockName(*BCI) << "\n"; + << " Bad block: " << getBlockName(ChainBB) << "\n"; + } + } - if (!LoopBlockSet.empty()) - for (SmallPtrSet::iterator LBI = LoopBlockSet.begin(), LBE = LoopBlockSet.end(); - LBI != LBE; ++LBI) + if (!LoopBlockSet.empty()) { + BadLoop = true; + for (MachineBasicBlock *LoopBB : LoopBlockSet) dbgs() << "Loop contains blocks never placed into a chain!\n" << " Loop header: " << getBlockName(*L.block_begin()) << "\n" << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n" - << " Bad block: " << getBlockName(*LBI) << "\n"; + << " Bad block: " << getBlockName(LoopBB) << "\n"; + } + assert(!BadLoop && "Detected problems with the placement of this loop."); }); } void MachineBlockPlacement::buildCFGChains(MachineFunction &F) { // Ensure that every BB in the function has an associated chain to simplify // the assumptions of the remaining algorithm. - for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) - BlockToChain[&*FI] = - new (ChainAllocator.Allocate()) BlockChain(BlockToChain, &*FI); + SmallVector Cond; // For AnalyzeBranch. + for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { + MachineBasicBlock *BB = FI; + BlockChain *Chain = + new (ChainAllocator.Allocate()) BlockChain(BlockToChain, BB); + // Also, merge any blocks which we cannot reason about and must preserve + // the exact fallthrough behavior for. + for (;;) { + Cond.clear(); + MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For AnalyzeBranch. + if (!TII->AnalyzeBranch(*BB, TBB, FBB, Cond) || !FI->canFallThrough()) + break; + + MachineFunction::iterator NextFI(std::next(FI)); + MachineBasicBlock *NextBB = NextFI; + // Ensure that the layout successor is a viable block, as we know that + // fallthrough is a possibility. + assert(NextFI != FE && "Can't fallthrough past the last block."); + DEBUG(dbgs() << "Pre-merging due to unanalyzable fallthrough: " + << getBlockName(BB) << " -> " << getBlockName(NextBB) + << "\n"); + Chain->merge(NextBB, nullptr); + FI = NextFI; + BB = NextBB; + } + } + + if (OutlineOptionalBranches) { + // Find the nearest common dominator of all of F's terminators. + MachineBasicBlock *Terminator = nullptr; + for (MachineBasicBlock &MBB : F) { + if (MBB.succ_size() == 0) { + if (Terminator == nullptr) + Terminator = &MBB; + else + Terminator = MDT->findNearestCommonDominator(Terminator, &MBB); + } + } + + // MBBs dominating this common dominator are unavoidable. + UnavoidableBlocks.clear(); + for (MachineBasicBlock &MBB : F) { + if (MDT->dominates(&MBB, Terminator)) { + UnavoidableBlocks.insert(&MBB); + } + } + } // Build any loop-based chains. - for (MachineLoopInfo::iterator LI = MLI->begin(), LE = MLI->end(); LI != LE; - ++LI) - buildLoopChains(F, **LI); + for (MachineLoop *L : *MLI) + buildLoopChains(F, *L); SmallVector BlockWorkList; SmallPtrSet UpdatedPreds; - for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { - MachineBasicBlock *BB = &*FI; - BlockChain &Chain = *BlockToChain[BB]; - if (!UpdatedPreds.insert(&Chain)) + for (MachineBasicBlock &MBB : F) { + BlockChain &Chain = *BlockToChain[&MBB]; + if (!UpdatedPreds.insert(&Chain).second) continue; assert(Chain.LoopPredecessors == 0); - for (BlockChain::iterator BCI = Chain.begin(), BCE = Chain.end(); - BCI != BCE; ++BCI) { - assert(BlockToChain[*BCI] == &Chain); - for (MachineBasicBlock::pred_iterator PI = (*BCI)->pred_begin(), - PE = (*BCI)->pred_end(); - PI != PE; ++PI) { - if (BlockToChain[*PI] == &Chain) + for (MachineBasicBlock *ChainBB : Chain) { + assert(BlockToChain[ChainBB] == &Chain); + for (MachineBasicBlock *Pred : ChainBB->predecessors()) { + if (BlockToChain[Pred] == &Chain) continue; ++Chain.LoopPredecessors; } } if (Chain.LoopPredecessors == 0) - BlockWorkList.push_back(BB); + BlockWorkList.push_back(*Chain.begin()); } BlockChain &FunctionChain = *BlockToChain[&F.front()]; buildChain(&F.front(), FunctionChain, BlockWorkList); +#ifndef NDEBUG typedef SmallPtrSet FunctionBlockSetType; +#endif DEBUG({ + // Crash at the end so we get all of the debugging output first. + bool BadFunc = false; FunctionBlockSetType FunctionBlockSet; - for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) - FunctionBlockSet.insert(FI); + for (MachineBasicBlock &MBB : F) + FunctionBlockSet.insert(&MBB); - for (BlockChain::iterator BCI = FunctionChain.begin(), BCE = FunctionChain.end(); - BCI != BCE; ++BCI) - if (!FunctionBlockSet.erase(*BCI)) + for (MachineBasicBlock *ChainBB : FunctionChain) + if (!FunctionBlockSet.erase(ChainBB)) { + BadFunc = true; dbgs() << "Function chain contains a block not in the function!\n" - << " Bad block: " << getBlockName(*BCI) << "\n"; + << " Bad block: " << getBlockName(ChainBB) << "\n"; + } - if (!FunctionBlockSet.empty()) - for (SmallPtrSet::iterator FBI = FunctionBlockSet.begin(), - FBE = FunctionBlockSet.end(); FBI != FBE; ++FBI) + if (!FunctionBlockSet.empty()) { + BadFunc = true; + for (MachineBasicBlock *RemainingBB : FunctionBlockSet) dbgs() << "Function contains blocks never placed into a chain!\n" - << " Bad block: " << getBlockName(*FBI) << "\n"; + << " Bad block: " << getBlockName(RemainingBB) << "\n"; + } + assert(!BadFunc && "Detected problems with the block placement."); }); // Splice the blocks into place. MachineFunction::iterator InsertPos = F.begin(); - SmallVector Cond; // For AnalyzeBranch. - for (BlockChain::iterator BI = FunctionChain.begin(), BE = FunctionChain.end(); - BI != BE; ++BI) { - DEBUG(dbgs() << (BI == FunctionChain.begin() ? "Placing chain " - : " ... ") - << getBlockName(*BI) << "\n"); - if (InsertPos != MachineFunction::iterator(*BI)) - F.splice(InsertPos, *BI); + for (MachineBasicBlock *ChainBB : FunctionChain) { + DEBUG(dbgs() << (ChainBB == *FunctionChain.begin() ? "Placing chain " + : " ... ") + << getBlockName(ChainBB) << "\n"); + if (InsertPos != MachineFunction::iterator(ChainBB)) + F.splice(InsertPos, ChainBB); else ++InsertPos; // Update the terminator of the previous block. - if (BI == FunctionChain.begin()) + if (ChainBB == *FunctionChain.begin()) continue; - MachineBasicBlock *PrevBB = llvm::prior(MachineFunction::iterator(*BI)); + MachineBasicBlock *PrevBB = std::prev(MachineFunction::iterator(ChainBB)); // FIXME: It would be awesome of updateTerminator would just return rather // than assert when the branch cannot be analyzed in order to remove this // boiler plate. Cond.clear(); - MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch. - if (!TII->AnalyzeBranch(*PrevBB, TBB, FBB, Cond)) - PrevBB->updateTerminator(); + MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For AnalyzeBranch. + if (!TII->AnalyzeBranch(*PrevBB, TBB, FBB, Cond)) { + // The "PrevBB" is not yet updated to reflect current code layout, so, + // o. it may fall-through to a block without explict "goto" instruction + // before layout, and no longer fall-through it after layout; or + // o. just opposite. + // + // AnalyzeBranch() may return erroneous value for FBB when these two + // situations take place. For the first scenario FBB is mistakenly set + // NULL; for the 2nd scenario, the FBB, which is expected to be NULL, + // is mistakenly pointing to "*BI". + // + bool needUpdateBr = true; + if (!Cond.empty() && (!FBB || FBB == ChainBB)) { + PrevBB->updateTerminator(); + needUpdateBr = false; + Cond.clear(); + TBB = FBB = nullptr; + if (TII->AnalyzeBranch(*PrevBB, TBB, FBB, Cond)) { + // FIXME: This should never take place. + TBB = FBB = nullptr; + } + } + + // If PrevBB has a two-way branch, try to re-order the branches + // such that we branch to the successor with higher weight first. + if (TBB && !Cond.empty() && FBB && + MBPI->getEdgeWeight(PrevBB, FBB) > MBPI->getEdgeWeight(PrevBB, TBB) && + !TII->ReverseBranchCondition(Cond)) { + DEBUG(dbgs() << "Reverse order of the two branches: " + << getBlockName(PrevBB) << "\n"); + DEBUG(dbgs() << " Edge weight: " << MBPI->getEdgeWeight(PrevBB, FBB) + << " vs " << MBPI->getEdgeWeight(PrevBB, TBB) << "\n"); + DebugLoc dl; // FIXME: this is nowhere + TII->RemoveBranch(*PrevBB); + TII->InsertBranch(*PrevBB, FBB, TBB, Cond, dl); + needUpdateBr = true; + } + if (needUpdateBr) + PrevBB->updateTerminator(); + } } // Fixup the last block. Cond.clear(); - MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch. + MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For AnalyzeBranch. if (!TII->AnalyzeBranch(F.back(), TBB, FBB, Cond)) F.back().updateTerminator(); -} -/// \brief Recursive helper to align a loop and any nested loops. -static void AlignLoop(MachineFunction &F, MachineLoop *L, unsigned Align) { - // Recurse through nested loops. - for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) - AlignLoop(F, *I, Align); + // Walk through the backedges of the function now that we have fully laid out + // the basic blocks and align the destination of each backedge. We don't rely + // exclusively on the loop info here so that we can align backedges in + // unnatural CFGs and backedges that were introduced purely because of the + // loop rotations done during this layout pass. + if (F.getFunction()->hasFnAttribute(Attribute::OptimizeForSize)) + return; + if (FunctionChain.begin() == FunctionChain.end()) + return; // Empty chain. + + const BranchProbability ColdProb(1, 5); // 20% + BlockFrequency EntryFreq = MBFI->getBlockFreq(F.begin()); + BlockFrequency WeightedEntryFreq = EntryFreq * ColdProb; + for (MachineBasicBlock *ChainBB : FunctionChain) { + if (ChainBB == *FunctionChain.begin()) + continue; - L->getTopBlock()->setAlignment(Align); -} + // Don't align non-looping basic blocks. These are unlikely to execute + // enough times to matter in practice. Note that we'll still handle + // unnatural CFGs inside of a natural outer loop (the common case) and + // rotated loops. + MachineLoop *L = MLI->getLoopFor(ChainBB); + if (!L) + continue; -/// \brief Align loop headers to target preferred alignments. -void MachineBlockPlacement::AlignLoops(MachineFunction &F) { - if (F.getFunction()->hasFnAttr(Attribute::OptimizeForSize)) - return; + unsigned Align = TLI->getPrefLoopAlignment(L); + if (!Align) + continue; // Don't care about loop alignment. + + // If the block is cold relative to the function entry don't waste space + // aligning it. + BlockFrequency Freq = MBFI->getBlockFreq(ChainBB); + if (Freq < WeightedEntryFreq) + continue; + + // If the block is cold relative to its loop header, don't align it + // regardless of what edges into the block exist. + MachineBasicBlock *LoopHeader = L->getHeader(); + BlockFrequency LoopHeaderFreq = MBFI->getBlockFreq(LoopHeader); + if (Freq < (LoopHeaderFreq * ColdProb)) + continue; - unsigned Align = TLI->getPrefLoopAlignment(); - if (!Align) - return; // Don't care about loop alignment. + // Check for the existence of a non-layout predecessor which would benefit + // from aligning this block. + MachineBasicBlock *LayoutPred = + &*std::prev(MachineFunction::iterator(ChainBB)); - for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); I != E; ++I) - AlignLoop(F, *I, Align); + // Force alignment if all the predecessors are jumps. We already checked + // that the block isn't cold above. + if (!LayoutPred->isSuccessor(ChainBB)) { + ChainBB->setAlignment(Align); + continue; + } + + // Align this block if the layout predecessor's edge into this block is + // cold relative to the block. When this is true, other predecessors make up + // all of the hot entries into the block and thus alignment is likely to be + // important. + BranchProbability LayoutProb = + MBPI->getEdgeProbability(LayoutPred, ChainBB); + BlockFrequency LayoutEdgeFreq = MBFI->getBlockFreq(LayoutPred) * LayoutProb; + if (LayoutEdgeFreq <= (Freq * ColdProb)) + ChainBB->setAlignment(Align); + } } bool MachineBlockPlacement::runOnMachineFunction(MachineFunction &F) { // Check for single-block functions and skip them. - if (llvm::next(F.begin()) == F.end()) + if (std::next(F.begin()) == F.end()) + return false; + + if (skipOptnoneFunction(*F.getFunction())) return false; MBPI = &getAnalysis(); MBFI = &getAnalysis(); MLI = &getAnalysis(); - TII = F.getTarget().getInstrInfo(); - TLI = F.getTarget().getTargetLowering(); + TII = F.getSubtarget().getInstrInfo(); + TLI = F.getSubtarget().getTargetLowering(); + MDT = &getAnalysis(); assert(BlockToChain.empty()); buildCFGChains(F); - AlignLoops(F); BlockToChain.clear(); + ChainAllocator.DestroyAll(); + + if (AlignAllBlock) + // Align all of the blocks in the function to a specific alignment. + for (MachineBasicBlock &MBB : F) + MBB.setAlignment(AlignAllBlock); // We always return true as we have no way to track whether the final order // differs from the original order. @@ -631,7 +1161,7 @@ namespace { /// /// A separate pass to compute interesting statistics for evaluating block /// placement. This is separate from the actual placement pass so that they can -/// be computed in the absense of any placement transformations or when using +/// be computed in the absence of any placement transformations or when using /// alternative placement strategies. class MachineBlockPlacementStats : public MachineFunctionPass { /// \brief A handle to the branch probability pass. @@ -646,20 +1176,19 @@ public: initializeMachineBlockPlacementStatsPass(*PassRegistry::getPassRegistry()); } - bool runOnMachineFunction(MachineFunction &F); + bool runOnMachineFunction(MachineFunction &F) override; - void getAnalysisUsage(AnalysisUsage &AU) const { + void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired(); AU.addRequired(); AU.setPreservesAll(); MachineFunctionPass::getAnalysisUsage(AU); } - - const char *getPassName() const { return "Block Placement Stats"; } }; } char MachineBlockPlacementStats::ID = 0; +char &llvm::MachineBlockPlacementStatsID = MachineBlockPlacementStats::ID; INITIALIZE_PASS_BEGIN(MachineBlockPlacementStats, "block-placement-stats", "Basic Block Placement Stats", false, false) INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) @@ -667,32 +1196,27 @@ INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) INITIALIZE_PASS_END(MachineBlockPlacementStats, "block-placement-stats", "Basic Block Placement Stats", false, false) -FunctionPass *llvm::createMachineBlockPlacementStatsPass() { - return new MachineBlockPlacementStats(); -} - bool MachineBlockPlacementStats::runOnMachineFunction(MachineFunction &F) { // Check for single-block functions and skip them. - if (llvm::next(F.begin()) == F.end()) + if (std::next(F.begin()) == F.end()) return false; MBPI = &getAnalysis(); MBFI = &getAnalysis(); - for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) { - BlockFrequency BlockFreq = MBFI->getBlockFreq(I); - Statistic &NumBranches = (I->succ_size() > 1) ? NumCondBranches - : NumUncondBranches; - Statistic &BranchTakenFreq = (I->succ_size() > 1) ? CondBranchTakenFreq - : UncondBranchTakenFreq; - for (MachineBasicBlock::succ_iterator SI = I->succ_begin(), - SE = I->succ_end(); - SI != SE; ++SI) { + for (MachineBasicBlock &MBB : F) { + BlockFrequency BlockFreq = MBFI->getBlockFreq(&MBB); + Statistic &NumBranches = + (MBB.succ_size() > 1) ? NumCondBranches : NumUncondBranches; + Statistic &BranchTakenFreq = + (MBB.succ_size() > 1) ? CondBranchTakenFreq : UncondBranchTakenFreq; + for (MachineBasicBlock *Succ : MBB.successors()) { // Skip if this successor is a fallthrough. - if (I->isLayoutSuccessor(*SI)) + if (MBB.isLayoutSuccessor(Succ)) continue; - BlockFrequency EdgeFreq = BlockFreq * MBPI->getEdgeProbability(I, *SI); + BlockFrequency EdgeFreq = + BlockFreq * MBPI->getEdgeProbability(&MBB, Succ); ++NumBranches; BranchTakenFreq += EdgeFreq.getFrequency(); }