X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FCodeGen%2FMachineBlockPlacement.cpp;h=fba33eb93d5fe499d5156c080dc0d276079b5a17;hp=07a3e039ed6f07565d09fc24f66faa44b25805c7;hb=d663426c2fcd19aac2cba06993cde8eed5579f6b;hpb=831737d329a727f53a1fb0572f7b7a8127208881 diff --git a/lib/CodeGen/MachineBlockPlacement.cpp b/lib/CodeGen/MachineBlockPlacement.cpp index 07a3e039ed6..fba33eb93d5 100644 --- a/lib/CodeGen/MachineBlockPlacement.cpp +++ b/lib/CodeGen/MachineBlockPlacement.cpp @@ -25,7 +25,6 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "block-placement2" #include "llvm/CodeGen/Passes.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallPtrSet.h" @@ -34,24 +33,77 @@ #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/Support/Allocator.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.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(NumUncondBranches, "Number of unconditional branches"); STATISTIC(CondBranchTakenFreq, "Potential frequency of taking conditional branches"); STATISTIC(UncondBranchTakenFreq, "Potential frequency of taking unconditional branches"); +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); + +static cl::opt LoopToColdBlockRatio( + "loop-to-cold-block-ratio", + cl::desc("Outline loop blocks from loop chain if (frequency of loop) / " + "(frequency of block) is greater than this ratio"), + cl::init(5), cl::Hidden); + +static cl::opt + PreciseRotationCost("precise-rotation-cost", + cl::desc("Model the cost of loop rotation more " + "precisely by using profile data."), + cl::init(false), cl::Hidden); + +static cl::opt MisfetchCost( + "misfetch-cost", + cl::desc("Cost that models the probablistic risk of an instruction " + "misfetch due to a jump comparing to falling through, whose cost " + "is zero."), + cl::init(1), cl::Hidden); + +static cl::opt JumpInstCost("jump-inst-cost", + cl::desc("Cost of jump instructions."), + cl::init(1), cl::Hidden); + namespace { class BlockChain; /// \brief Type for our function-wide basic block -> block chain mapping. @@ -92,7 +144,7 @@ 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; } @@ -129,19 +181,18 @@ 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. - void dump() LLVM_ATTRIBUTE_USED { - for (iterator I = begin(), E = end(); I != E; ++I) - (*I)->dump(); + LLVM_DUMP_METHOD void dump() { + for (MachineBasicBlock *MBB : *this) + MBB->dump(); } #endif // NDEBUG @@ -171,7 +222,14 @@ 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. /// @@ -190,32 +248,33 @@ class MachineBlockPlacement : public MachineFunctionPass { /// between basic blocks. DenseMap BlockToChain; - void markChainSuccessors(BlockChain &Chain, - MachineBasicBlock *LoopHeaderBB, + void markChainSuccessors(BlockChain &Chain, MachineBasicBlock *LoopHeaderBB, SmallVectorImpl &BlockWorkList, - const BlockFilterSet *BlockFilter = 0); + 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); + 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 &BlockWorkList, - const BlockFilterSet *BlockFilter = 0); + const BlockFilterSet *BlockFilter = nullptr); MachineBasicBlock *findBestLoopTop(MachineLoop &L, const BlockFilterSet &LoopBlockSet); - MachineBasicBlock *findBestLoopExit(MachineFunction &F, - MachineLoop &L, + MachineBasicBlock *findBestLoopExit(MachineFunction &F, MachineLoop &L, const BlockFilterSet &LoopBlockSet); + BlockFilterSet collectLoopBlockSet(MachineFunction &F, MachineLoop &L); void buildLoopChains(MachineFunction &F, MachineLoop &L); void rotateLoop(BlockChain &LoopChain, MachineBasicBlock *ExitingBB, const BlockFilterSet &LoopBlockSet); + void rotateLoopWithProfile(BlockChain &LoopChain, MachineLoop &L, + const BlockFilterSet &LoopBlockSet); void buildCFGChains(MachineFunction &F); public: @@ -224,11 +283,12 @@ 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); } @@ -237,12 +297,13 @@ public: char MachineBlockPlacement::ID = 0; char &llvm::MachineBlockPlacementID = MachineBlockPlacement::ID; -INITIALIZE_PASS_BEGIN(MachineBlockPlacement, "block-placement2", +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) #ifndef NDEBUG @@ -252,8 +313,8 @@ INITIALIZE_PASS_END(MachineBlockPlacement, "block-placement2", 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; } @@ -277,26 +338,22 @@ static std::string getBlockNum(MachineBasicBlock *BB) { /// 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 @@ -316,12 +373,13 @@ 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; + 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 @@ -331,87 +389,121 @@ MachineBasicBlock *MachineBlockPlacement::selectBestSuccessor( 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)) - continue; - BlockChain &SuccChain = *BlockToChain[*SI]; - if (&SuccChain == &Chain) { - DEBUG(dbgs() << " " << getBlockName(*SI) << " -> Already merged!\n"); - continue; - } - if (*SI != *SuccChain.begin()) { - DEBUG(dbgs() << " " << getBlockName(*SI) << " -> Mid chain!\n"); - continue; + + // Adjust sum of weights by excluding weights on edges pointing to blocks that + // is either not in BlockFilter or is already in the current chain. Consider + // the following CFG: + // + // --->A + // | / \ + // | B C + // | \ / \ + // ----D E + // + // Assume A->C is very hot (>90%), and C->D has a 50% probability, then after + // A->C is chosen as a fall-through, D won't be selected as a successor of C + // due to CFG constraint (the probability of C->D is not greater than + // HotProb). If we exclude E that is not in BlockFilter when calculating the + // probability of C->D, D will be selected and we will get A C D B as the + // layout of this loop. + uint32_t AdjustedSumWeight = SumWeight; + SmallVector Successors; + for (MachineBasicBlock *Succ : BB->successors()) { + bool SkipSucc = false; + if (BlockFilter && !BlockFilter->count(Succ)) { + SkipSucc = true; + } else { + BlockChain *SuccChain = BlockToChain[Succ]; + if (SuccChain == &Chain) { + DEBUG(dbgs() << " " << getBlockName(Succ) + << " -> Already merged!\n"); + SkipSucc = true; + } else if (Succ != *SuccChain->begin()) { + DEBUG(dbgs() << " " << getBlockName(Succ) << " -> Mid chain!\n"); + continue; + } } + if (SkipSucc) + AdjustedSumWeight -= MBPI->getEdgeWeight(BB, Succ) / WeightScale; + else + Successors.push_back(Succ); + } - uint32_t SuccWeight = MBPI->getEdgeWeight(BB, *SI); - BranchProbability SuccProb(SuccWeight / WeightScale, SumWeight); + DEBUG(dbgs() << "Attempting merge from: " << getBlockName(BB) << "\n"); + for (MachineBasicBlock *Succ : Successors) { + uint32_t SuccWeight = MBPI->getEdgeWeight(BB, Succ); + BranchProbability SuccProb(SuccWeight / WeightScale, AdjustedSumWeight); + + // 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. + BlockChain &SuccChain = *BlockToChain[Succ]; if (SuccChain.LoopPredecessors != 0) { if (SuccProb < HotProb) { - DEBUG(dbgs() << " " << getBlockName(*SI) << " -> CFG conflict\n"); + 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(); + // Make sure that a hot successor doesn't have a globally more + // important predecessor. + BranchProbability RealSuccProb(SuccWeight / WeightScale, SumWeight); + BlockFrequency CandidateEdgeFreq = + MBFI->getBlockFreq(BB) * RealSuccProb * HotProb.getCompl(); bool BadCFGConflict = false; - for (MachineBasicBlock::pred_iterator PI = (*SI)->pred_begin(), - PE = (*SI)->pred_end(); - PI != PE; ++PI) { - if (*PI == *SI || (BlockFilter && !BlockFilter->count(*PI)) || - BlockToChain[*PI] == &Chain) + for (MachineBasicBlock *Pred : Succ->predecessors()) { + if (Pred == Succ || (BlockFilter && !BlockFilter->count(Pred)) || + BlockToChain[Pred] == &Chain) continue; - BlockFrequency PredEdgeFreq - = MBFI->getBlockFreq(*PI) * MBPI->getEdgeProbability(*PI, *SI); + BlockFrequency PredEdgeFreq = + MBFI->getBlockFreq(Pred) * MBPI->getEdgeProbability(Pred, Succ); if (PredEdgeFreq >= CandidateEdgeFreq) { BadCFGConflict = true; break; } } if (BadCFGConflict) { - DEBUG(dbgs() << " " << getBlockName(*SI) - << " -> non-cold CFG conflict\n"); + 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 && BestWeight >= SuccWeight) continue; - BestSucc = *SI; + BestSucc = Succ; BestWeight = SuccWeight; } return BestSucc; } -namespace { -/// \brief Predicate struct to detect blocks already placed. -class IsBlockPlaced { - const BlockChain &PlacedChain; - const BlockToChainMapType &BlockToChain; - -public: - IsBlockPlaced(const BlockChain &PlacedChain, - const BlockToChainMapType &BlockToChain) - : PlacedChain(PlacedChain), BlockToChain(BlockToChain) {} - - bool operator()(MachineBasicBlock *BB) const { - return BlockToChain.lookup(BB) == &PlacedChain; - } -}; -} - /// \brief Select the best block from a worklist. /// /// This looks through the provided worklist as a list of candidate basic @@ -430,28 +522,27 @@ MachineBasicBlock *MachineBlockPlacement::selectBestCandidateBlock( // 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(), - IsBlockPlaced(Chain, BlockToChain)), + [&](MachineBasicBlock *BB) { + return BlockToChain.lookup(BB) == &Chain; + }), WorkList.end()); - MachineBasicBlock *BestBlock = 0; + MachineBasicBlock *BestBlock = nullptr; BlockFrequency BestFreq; - for (SmallVectorImpl::iterator WBI = WorkList.begin(), - WBE = WorkList.end(); - WBI != WBE; ++WBI) { - BlockChain &SuccChain = *BlockToChain[*WBI]; + for (MachineBasicBlock *MBB : WorkList) { + BlockChain &SuccChain = *BlockToChain[MBB]; if (&SuccChain == &Chain) { - DEBUG(dbgs() << " " << getBlockName(*WBI) - << " -> Already merged!\n"); + DEBUG(dbgs() << " " << getBlockName(MBB) << " -> Already merged!\n"); continue; } assert(SuccChain.LoopPredecessors == 0 && "Found CFG-violating block"); - BlockFrequency CandidateFreq = MBFI->getBlockFreq(*WBI); - DEBUG(dbgs() << " " << getBlockName(*WBI) << " -> " << CandidateFreq - << " (freq)\n"); + BlockFrequency CandidateFreq = MBFI->getBlockFreq(MBB); + DEBUG(dbgs() << " " << getBlockName(MBB) << " -> "; + MBFI->printBlockFreq(dbgs(), CandidateFreq) << " (freq)\n"); if (BestBlock && BestFreq >= CandidateFreq) continue; - BestBlock = *WBI; + BestBlock = MBB; BestFreq = CandidateFreq; } return BestBlock; @@ -470,22 +561,21 @@ MachineBasicBlock *MachineBlockPlacement::getFirstUnplacedBlock( const BlockFilterSet *BlockFilter) { for (MachineFunction::iterator I = PrevUnplacedBlockIt, E = F.end(); I != E; ++I) { - if (BlockFilter && !BlockFilter->count(I)) + if (BlockFilter && !BlockFilter->count(&*I)) continue; - if (BlockToChain[I] != &PlacedChain) { + 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 *BlockToChain[&*I]->begin(); } } - return 0; + return nullptr; } void MachineBlockPlacement::buildChain( - MachineBasicBlock *BB, - BlockChain &Chain, + MachineBasicBlock *BB, BlockChain &Chain, SmallVectorImpl &BlockWorkList, const BlockFilterSet *BlockFilter) { assert(BB); @@ -495,11 +585,11 @@ void MachineBlockPlacement::buildChain( 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. @@ -512,8 +602,8 @@ void MachineBlockPlacement::buildChain( BestSucc = selectBestCandidateBlock(Chain, BlockWorkList, BlockFilter); if (!BestSucc) { - BestSucc = getFirstUnplacedBlock(F, Chain, PrevUnplacedBlockIt, - BlockFilter); + BestSucc = + getFirstUnplacedBlock(F, Chain, PrevUnplacedBlockIt, BlockFilter); if (!BestSucc) break; @@ -526,11 +616,11 @@ void MachineBlockPlacement::buildChain( // 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"); + 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 " @@ -557,20 +647,17 @@ MachineBlockPlacement::findBestLoopTop(MachineLoop &L, if (!LoopBlockSet.count(*HeaderChain.begin())) return L.getHeader(); - DEBUG(dbgs() << "Finding best loop top for: " - << getBlockName(L.getHeader()) << "\n"); + DEBUG(dbgs() << "Finding best loop top for: " << getBlockName(L.getHeader()) + << "\n"); BlockFrequency BestPredFreq; - MachineBasicBlock *BestPred = 0; - for (MachineBasicBlock::pred_iterator PI = L.getHeader()->pred_begin(), - PE = L.getHeader()->pred_end(); - PI != PE; ++PI) { - MachineBasicBlock *Pred = *PI; + 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->getBlockFreq(Pred) << " freq\n"); + << Pred->succ_size() << " successors, "; + MBFI->printBlockFreq(dbgs(), Pred) << " freq\n"); if (Pred->succ_size() > 1) continue; @@ -597,15 +684,13 @@ MachineBlockPlacement::findBestLoopTop(MachineLoop &L, 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, +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 @@ -617,25 +702,23 @@ MachineBlockPlacement::findBestLoopExit(MachineFunction &F, // header and only rotate if safe. BlockChain &HeaderChain = *BlockToChain[L.getHeader()]; if (!LoopBlockSet.count(*HeaderChain.begin())) - return 0; + return nullptr; BlockFrequency BestExitEdgeFreq; unsigned BestExitLoopDepth = 0; - MachineBasicBlock *ExitingBB = 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 (MachineLoop::block_iterator I = L.block_begin(), - E = L.block_end(); - I != E; ++I) { - BlockChain &Chain = *BlockToChain[*I]; + 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 analyzable branch. - if (*I != *llvm::prior(Chain.end())) + // 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 @@ -649,56 +732,56 @@ MachineBlockPlacement::findBestLoopExit(MachineFunction &F, // 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(*I, WeightScale); - for (MachineBasicBlock::succ_iterator SI = (*I)->succ_begin(), - SE = (*I)->succ_end(); - SI != SE; ++SI) { - if ((*SI)->isLandingPad()) + uint32_t SumWeight = MBPI->getSumForBlock(MBB, WeightScale); + for (MachineBasicBlock *Succ : MBB->successors()) { + if (Succ->isEHPad()) continue; - if (*SI == *I) + if (Succ == MBB) continue; - BlockChain &SuccChain = *BlockToChain[*SI]; + BlockChain &SuccChain = *BlockToChain[Succ]; // Don't split chains, either this chain or the successor's chain. if (&Chain == &SuccChain) { - DEBUG(dbgs() << " exiting: " << getBlockName(*I) << " -> " - << getBlockName(*SI) << " (chain conflict)\n"); + DEBUG(dbgs() << " exiting: " << getBlockName(MBB) << " -> " + << getBlockName(Succ) << " (chain conflict)\n"); continue; } - uint32_t SuccWeight = MBPI->getEdgeWeight(*I, *SI); - if (LoopBlockSet.count(*SI)) { - DEBUG(dbgs() << " looping: " << getBlockName(*I) << " -> " - << getBlockName(*SI) << " (" << SuccWeight << ")\n"); + 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(*SI)) { + if (MachineLoop *ExitLoop = MLI->getLoopFor(Succ)) { SuccLoopDepth = ExitLoop->getLoopDepth(); if (ExitLoop->contains(&L)) - BlocksExitingToOuterLoop.insert(*I); + BlocksExitingToOuterLoop.insert(MBB); } BranchProbability SuccProb(SuccWeight / WeightScale, SumWeight); - BlockFrequency ExitEdgeFreq = MBFI->getBlockFreq(*I) * SuccProb; - DEBUG(dbgs() << " exiting: " << getBlockName(*I) << " -> " - << getBlockName(*SI) << " [L:" << SuccLoopDepth - << "] (" << ExitEdgeFreq << ")\n"); - // Note that we slightly bias this toward an existing layout successor to - // retain incoming order in the absence of better information. - // FIXME: Should we bias this more strongly? It's pretty weak. - if (!ExitingBB || BestExitLoopDepth < SuccLoopDepth || + 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 || - ((*I)->isLayoutSuccessor(*SI) && - !(ExitEdgeFreq < BestExitEdgeFreq))) { + (MBB->isLayoutSuccessor(Succ) && + !(ExitEdgeFreq < BestExitEdgeFreq * Bias))) { BestExitEdgeFreq = ExitEdgeFreq; - ExitingBB = *I; + ExitingBB = MBB; } } - // Restore the old exiting state, no viable looping successor was found. if (!HasLoopingSucc) { + // Restore the old exiting state, no viable looping successor was found. ExitingBB = OldExitingBB; BestExitEdgeFreq = OldBestExitEdgeFreq; continue; @@ -707,14 +790,14 @@ MachineBlockPlacement::findBestLoopExit(MachineFunction &F, // 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 0; + 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 0; + return nullptr; DEBUG(dbgs() << " Best exiting block: " << getBlockName(ExitingBB) << "\n"); return ExitingBB; @@ -734,12 +817,10 @@ void MachineBlockPlacement::rotateLoop(BlockChain &LoopChain, MachineBasicBlock *Top = *LoopChain.begin(); bool ViableTopFallthrough = false; - for (MachineBasicBlock::pred_iterator PI = Top->pred_begin(), - PE = Top->pred_end(); - PI != PE; ++PI) { - BlockChain *PredChain = BlockToChain[*PI]; - if (!LoopBlockSet.count(*PI) && - (!PredChain || *PI == *llvm::prior(PredChain->end()))) { + for (MachineBasicBlock *Pred : Top->predecessors()) { + BlockChain *PredChain = BlockToChain[Pred]; + if (!LoopBlockSet.count(Pred) && + (!PredChain || Pred == *std::prev(PredChain->end()))) { ViableTopFallthrough = true; break; } @@ -749,23 +830,207 @@ void MachineBlockPlacement::rotateLoop(BlockChain &LoopChain, // bottom is a viable exiting block. If so, bail out as rotating will // introduce an unnecessary branch. if (ViableTopFallthrough) { - MachineBasicBlock *Bottom = *llvm::prior(LoopChain.end()); - for (MachineBasicBlock::succ_iterator SI = Bottom->succ_begin(), - SE = Bottom->succ_end(); - SI != SE; ++SI) { - BlockChain *SuccChain = BlockToChain[*SI]; - if (!LoopBlockSet.count(*SI) && - (!SuccChain || *SI == *SuccChain->begin())) + 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); + BlockChain::iterator ExitIt = + std::find(LoopChain.begin(), LoopChain.end(), ExitingBB); if (ExitIt == LoopChain.end()) return; - std::rotate(LoopChain.begin(), llvm::next(ExitIt), LoopChain.end()); + std::rotate(LoopChain.begin(), std::next(ExitIt), LoopChain.end()); +} + +/// \brief Attempt to rotate a loop based on profile data to reduce branch cost. +/// +/// With profile data, we can determine the cost in terms of missed fall through +/// opportunities when rotating a loop chain and select the best rotation. +/// Basically, there are three kinds of cost to consider for each rotation: +/// 1. The possibly missed fall through edge (if it exists) from BB out of +/// the loop to the loop header. +/// 2. The possibly missed fall through edges (if they exist) from the loop +/// exits to BB out of the loop. +/// 3. The missed fall through edge (if it exists) from the last BB to the +/// first BB in the loop chain. +/// Therefore, the cost for a given rotation is the sum of costs listed above. +/// We select the best rotation with the smallest cost. +void MachineBlockPlacement::rotateLoopWithProfile( + BlockChain &LoopChain, MachineLoop &L, const BlockFilterSet &LoopBlockSet) { + auto HeaderBB = L.getHeader(); + auto HeaderIter = std::find(LoopChain.begin(), LoopChain.end(), HeaderBB); + auto RotationPos = LoopChain.end(); + + BlockFrequency SmallestRotationCost = BlockFrequency::getMaxFrequency(); + + // A utility lambda that scales up a block frequency by dividing it by a + // branch probability which is the reciprocal of the scale. + auto ScaleBlockFrequency = [](BlockFrequency Freq, + unsigned Scale) -> BlockFrequency { + if (Scale == 0) + return 0; + // Use operator / between BlockFrequency and BranchProbability to implement + // saturating multiplication. + return Freq / BranchProbability(1, Scale); + }; + + // Compute the cost of the missed fall-through edge to the loop header if the + // chain head is not the loop header. As we only consider natural loops with + // single header, this computation can be done only once. + BlockFrequency HeaderFallThroughCost(0); + for (auto *Pred : HeaderBB->predecessors()) { + BlockChain *PredChain = BlockToChain[Pred]; + if (!LoopBlockSet.count(Pred) && + (!PredChain || Pred == *std::prev(PredChain->end()))) { + auto EdgeFreq = + MBFI->getBlockFreq(Pred) * MBPI->getEdgeProbability(Pred, HeaderBB); + auto FallThruCost = ScaleBlockFrequency(EdgeFreq, MisfetchCost); + // If the predecessor has only an unconditional jump to the header, we + // need to consider the cost of this jump. + if (Pred->succ_size() == 1) + FallThruCost += ScaleBlockFrequency(EdgeFreq, JumpInstCost); + HeaderFallThroughCost = std::max(HeaderFallThroughCost, FallThruCost); + } + } + + // Here we collect all exit blocks in the loop, and for each exit we find out + // its hottest exit edge. For each loop rotation, we define the loop exit cost + // as the sum of frequencies of exit edges we collect here, excluding the exit + // edge from the tail of the loop chain. + SmallVector, 4> ExitsWithFreq; + for (auto BB : LoopChain) { + uint32_t LargestExitEdgeWeight = 0; + for (auto *Succ : BB->successors()) { + BlockChain *SuccChain = BlockToChain[Succ]; + if (!LoopBlockSet.count(Succ) && + (!SuccChain || Succ == *SuccChain->begin())) { + uint32_t SuccWeight = MBPI->getEdgeWeight(BB, Succ); + LargestExitEdgeWeight = std::max(LargestExitEdgeWeight, SuccWeight); + } + } + if (LargestExitEdgeWeight > 0) { + uint32_t WeightScale = 0; + uint32_t SumWeight = MBPI->getSumForBlock(BB, WeightScale); + auto ExitFreq = + MBFI->getBlockFreq(BB) * + BranchProbability(LargestExitEdgeWeight / WeightScale, SumWeight); + ExitsWithFreq.emplace_back(BB, ExitFreq); + } + } + + // In this loop we iterate every block in the loop chain and calculate the + // cost assuming the block is the head of the loop chain. When the loop ends, + // we should have found the best candidate as the loop chain's head. + for (auto Iter = LoopChain.begin(), TailIter = std::prev(LoopChain.end()), + EndIter = LoopChain.end(); + Iter != EndIter; Iter++, TailIter++) { + // TailIter is used to track the tail of the loop chain if the block we are + // checking (pointed by Iter) is the head of the chain. + if (TailIter == LoopChain.end()) + TailIter = LoopChain.begin(); + + auto TailBB = *TailIter; + + // Calculate the cost by putting this BB to the top. + BlockFrequency Cost = 0; + + // If the current BB is the loop header, we need to take into account the + // cost of the missed fall through edge from outside of the loop to the + // header. + if (Iter != HeaderIter) + Cost += HeaderFallThroughCost; + + // Collect the loop exit cost by summing up frequencies of all exit edges + // except the one from the chain tail. + for (auto &ExitWithFreq : ExitsWithFreq) + if (TailBB != ExitWithFreq.first) + Cost += ExitWithFreq.second; + + // The cost of breaking the once fall-through edge from the tail to the top + // of the loop chain. Here we need to consider three cases: + // 1. If the tail node has only one successor, then we will get an + // additional jmp instruction. So the cost here is (MisfetchCost + + // JumpInstCost) * tail node frequency. + // 2. If the tail node has two successors, then we may still get an + // additional jmp instruction if the layout successor after the loop + // chain is not its CFG successor. Note that the more frequently executed + // jmp instruction will be put ahead of the other one. Assume the + // frequency of those two branches are x and y, where x is the frequency + // of the edge to the chain head, then the cost will be + // (x * MisfetechCost + min(x, y) * JumpInstCost) * tail node frequency. + // 3. If the tail node has more than two successors (this rarely happens), + // we won't consider any additional cost. + if (TailBB->isSuccessor(*Iter)) { + auto TailBBFreq = MBFI->getBlockFreq(TailBB); + if (TailBB->succ_size() == 1) + Cost += ScaleBlockFrequency(TailBBFreq.getFrequency(), + MisfetchCost + JumpInstCost); + else if (TailBB->succ_size() == 2) { + auto TailToHeadProb = MBPI->getEdgeProbability(TailBB, *Iter); + auto TailToHeadFreq = TailBBFreq * TailToHeadProb; + auto ColderEdgeFreq = TailToHeadProb > BranchProbability(1, 2) + ? TailBBFreq * TailToHeadProb.getCompl() + : TailToHeadFreq; + Cost += ScaleBlockFrequency(TailToHeadFreq, MisfetchCost) + + ScaleBlockFrequency(ColderEdgeFreq, JumpInstCost); + } + } + + DEBUG(dbgs() << "The cost of loop rotation by making " << getBlockNum(*Iter) + << " to the top: " << Cost.getFrequency() << "\n"); + + if (Cost < SmallestRotationCost) { + SmallestRotationCost = Cost; + RotationPos = Iter; + } + } + + if (RotationPos != LoopChain.end()) { + DEBUG(dbgs() << "Rotate loop by making " << getBlockNum(*RotationPos) + << " to the top\n"); + std::rotate(LoopChain.begin(), RotationPos, LoopChain.end()); + } +} + +/// \brief Collect blocks in the given loop that are to be placed. +/// +/// When profile data is available, exclude cold blocks from the returned set; +/// otherwise, collect all blocks in the loop. +MachineBlockPlacement::BlockFilterSet +MachineBlockPlacement::collectLoopBlockSet(MachineFunction &F, MachineLoop &L) { + BlockFilterSet LoopBlockSet; + + // Filter cold blocks off from LoopBlockSet when profile data is available. + // Collect the sum of frequencies of incoming edges to the loop header from + // outside. If we treat the loop as a super block, this is the frequency of + // the loop. Then for each block in the loop, we calculate the ratio between + // its frequency and the frequency of the loop block. When it is too small, + // don't add it to the loop chain. If there are outer loops, then this block + // will be merged into the first outer loop chain for which this block is not + // cold anymore. This needs precise profile data and we only do this when + // profile data is available. + if (F.getFunction()->getEntryCount()) { + BlockFrequency LoopFreq(0); + for (auto LoopPred : L.getHeader()->predecessors()) + if (!L.contains(LoopPred)) + LoopFreq += MBFI->getBlockFreq(LoopPred) * + MBPI->getEdgeProbability(LoopPred, L.getHeader()); + + for (MachineBasicBlock *LoopBB : L.getBlocks()) { + auto Freq = MBFI->getBlockFreq(LoopBB).getFrequency(); + if (Freq == 0 || LoopFreq.getFrequency() / Freq > LoopToColdBlockRatio) + continue; + LoopBlockSet.insert(LoopBB); + } + } else + LoopBlockSet.insert(L.block_begin(), L.block_end()); + + return LoopBlockSet; } /// \brief Forms basic block chains from the natural loop structures. @@ -778,23 +1043,31 @@ 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()); + BlockFilterSet LoopBlockSet = collectLoopBlockSet(F, L); + + // Check if we have profile data for this function. If yes, we will rotate + // this loop by modeling costs more precisely which requires the profile data + // for better layout. + bool RotateLoopWithProfile = + PreciseRotationCost && F.getFunction()->getEntryCount(); // 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); + // When we use profile data to rotate the loop, this is unnecessary. + MachineBasicBlock *LoopTop = + RotateLoopWithProfile ? L.getHeader() : 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 = 0; - if (LoopTop == L.getHeader()) + MachineBasicBlock *ExitingBB = nullptr; + if (!RotateLoopWithProfile && LoopTop == L.getHeader()) ExitingBB = findBestLoopExit(F, L, LoopBlockSet); BlockChain &LoopChain = *BlockToChain[LoopTop]; @@ -805,21 +1078,17 @@ void MachineBlockPlacement::buildLoopChains(MachineFunction &F, SmallPtrSet UpdatedPreds; assert(LoopChain.LoopPredecessors == 0); UpdatedPreds.insert(&LoopChain); - for (MachineLoop::block_iterator BI = L.block_begin(), - BE = L.block_end(); - BI != BE; ++BI) { - BlockChain &Chain = *BlockToChain[*BI]; - if (!UpdatedPreds.insert(&Chain)) + + for (MachineBasicBlock *LoopBB : LoopBlockSet) { + 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; } @@ -830,7 +1099,11 @@ void MachineBlockPlacement::buildLoopChains(MachineFunction &F, } buildChain(LoopTop, LoopChain, BlockWorkList, &LoopBlockSet); - rotateLoop(LoopChain, ExitingBB, LoopBlockSet); + + if (RotateLoopWithProfile) + rotateLoopWithProfile(LoopChain, L, LoopBlockSet); + else + rotateLoop(LoopChain, ExitingBB, LoopBlockSet); DEBUG({ // Crash at the end so we get all of the debugging output first. @@ -841,29 +1114,26 @@ void MachineBlockPlacement::buildLoopChains(MachineFunction &F, << " 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) { - dbgs() << " ... " << getBlockName(*BCI) << "\n"; - 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()) { BadLoop = true; - for (BlockFilterSet::iterator LBI = LoopBlockSet.begin(), - LBE = LoopBlockSet.end(); - LBI != LBE; ++LBI) + 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."); }); @@ -874,53 +1144,69 @@ void MachineBlockPlacement::buildCFGChains(MachineFunction &F) { // the assumptions of the remaining algorithm. 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); + 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 = 0, *FBB = 0; // For AnalyzeBranch. + MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For AnalyzeBranch. if (!TII->AnalyzeBranch(*BB, TBB, FBB, Cond) || !FI->canFallThrough()) break; - MachineFunction::iterator NextFI(llvm::next(FI)); - MachineBasicBlock *NextBB = NextFI; + 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, 0); + 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; } @@ -933,58 +1219,76 @@ void MachineBlockPlacement::buildCFGChains(MachineFunction &F) { 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()) { BadFunc = true; - for (FunctionBlockSetType::iterator FBI = FunctionBlockSet.begin(), - FBE = FunctionBlockSet.end(); - FBI != FBE; ++FBI) + 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(); - 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. + 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 && @@ -994,17 +1298,19 @@ void MachineBlockPlacement::buildCFGChains(MachineFunction &F) { << getBlockName(PrevBB) << "\n"); DEBUG(dbgs() << " Edge weight: " << MBPI->getEdgeWeight(PrevBB, FBB) << " vs " << MBPI->getEdgeWeight(PrevBB, TBB) << "\n"); - DebugLoc dl; // FIXME: this is nowhere + DebugLoc dl; // FIXME: this is nowhere TII->RemoveBranch(*PrevBB); TII->InsertBranch(*PrevBB, FBB, TBB, Cond, dl); + needUpdateBr = true; } - PrevBB->updateTerminator(); + 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(); @@ -1013,32 +1319,34 @@ void MachineBlockPlacement::buildCFGChains(MachineFunction &F) { // 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()->getAttributes(). - hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize)) + // FIXME: Use Function::optForSize(). + if (F.getFunction()->hasFnAttribute(Attribute::OptimizeForSize)) return; - unsigned Align = TLI->getPrefLoopAlignment(); - if (!Align) - return; // Don't care about loop alignment. if (FunctionChain.begin() == FunctionChain.end()) - return; // Empty chain. + return; // Empty chain. const BranchProbability ColdProb(1, 5); // 20% - BlockFrequency EntryFreq = MBFI->getBlockFreq(F.begin()); + BlockFrequency EntryFreq = MBFI->getBlockFreq(&F.front()); BlockFrequency WeightedEntryFreq = EntryFreq * ColdProb; - for (BlockChain::iterator BI = llvm::next(FunctionChain.begin()), - BE = FunctionChain.end(); - BI != BE; ++BI) { + for (MachineBasicBlock *ChainBB : FunctionChain) { + if (ChainBB == *FunctionChain.begin()) + continue; + // 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(*BI); + MachineLoop *L = MLI->getLoopFor(ChainBB); if (!L) continue; + 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(*BI); + BlockFrequency Freq = MBFI->getBlockFreq(ChainBB); if (Freq < WeightedEntryFreq) continue; @@ -1051,36 +1359,42 @@ void MachineBlockPlacement::buildCFGChains(MachineFunction &F) { // Check for the existence of a non-layout predecessor which would benefit // from aligning this block. - MachineBasicBlock *LayoutPred = *llvm::prior(BI); + MachineBasicBlock *LayoutPred = + &*std::prev(MachineFunction::iterator(ChainBB)); // Force alignment if all the predecessors are jumps. We already checked // that the block isn't cold above. - if (!LayoutPred->isSuccessor(*BI)) { - (*BI)->setAlignment(Align); + 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, othe predecessors make up + // 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, *BI); + BranchProbability LayoutProb = + MBPI->getEdgeProbability(LayoutPred, ChainBB); BlockFrequency LayoutEdgeFreq = MBFI->getBlockFreq(LayoutPred) * LayoutProb; if (LayoutEdgeFreq <= (Freq * ColdProb)) - (*BI)->setAlignment(Align); + 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); @@ -1088,6 +1402,11 @@ bool MachineBlockPlacement::runOnMachineFunction(MachineFunction &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. return true; @@ -1113,9 +1432,9 @@ 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(); @@ -1135,26 +1454,25 @@ INITIALIZE_PASS_END(MachineBlockPlacementStats, "block-placement-stats", 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(); } @@ -1162,4 +1480,3 @@ bool MachineBlockPlacementStats::runOnMachineFunction(MachineFunction &F) { return false; } -