Lines Matching +full:assert +full:- +full:falling +full:- +full:edge
1 //===- MachineBlockPlacement.cpp - Basic Block Code Layout optimization ---===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
18 // The algorithm works from the inner-most loop within a function outward, and
23 // function in-order.
25 //===----------------------------------------------------------------------===//
78 #define DEBUG_TYPE "block-placement"
88 "align-all-blocks",
94 "align-all-nofallthru-blocks",
95 cl::desc("Force the alignment of all blocks that have no fall-through "
101 "max-bytes-for-alignment",
108 "block-placement-exit-block-bias",
114 // - Outlining: placement of a basic block outside the chain or hot path.
117 "loop-to-cold-block-ratio",
123 "force-loop-cold-block",
128 PreciseRotationCost("precise-rotation-cost",
134 ForcePreciseRotationCost("force-precise-rotation-cost",
140 "misfetch-cost",
142 "misfetch due to a jump comparing to falling through, whose cost "
146 static cl::opt<unsigned> JumpInstCost("jump-inst-cost",
150 TailDupPlacement("tail-dup-placement",
157 BranchFoldPlacement("branch-fold-placement",
164 "tail-dup-placement-threshold",
172 "tail-dup-placement-aggressive-threshold",
174 "layout. Used at -O3. Tail merging during layout is forced to "
180 "tail-dup-placement-penalty",
190 "tail-dup-profile-percent-threshold",
198 "triangle-chain-count",
199 cl::desc("Number of triangle-shaped-CFG's that need to be in a row for the "
210 "renumber-blocks-before-view",
212 "If true, basic blocks are re-numbered before MBP layout is printed "
224 // -view-block-layout-with-bfi=
228 // Defined in Analysis/BlockFrequencyInfo.cpp: -view-bfi-func-name=
236 /// Type for our function-wide basic block -> block chain mapping.
248 /// them. They participate in a block-to-chain mapping, which is updated
254 /// out in-order within the function.
257 /// A handle to the function-wide basic block to block chain mapping.
260 /// block chains for SCC-formation and iteration. We store the edges to child
273 assert(BB && "Cannot create a chain with a null basic block"); in BlockChain()
302 /// a contiguous sequence of basic blocks, updating the edge list, and
303 /// updating the block -> chain mapping. It does not free or tear down the
306 assert(BB && "Can't merge a null block."); in merge()
307 assert(!Blocks.empty() && "Can't merge into an empty chain."); in merge()
311 assert(!BlockToChain[BB] && in merge()
318 assert(BB == *Chain->begin() && "Passed BB is not head of Chain."); in merge()
319 assert(Chain->begin() != Chain->end()); in merge()
325 assert(BlockToChain[ChainBB] == Chain && "Incoming blocks not in chain."); in merge()
334 MBB->dump(); in dump()
345 /// Note: This field is reinitialized multiple times - once for each loop,
360 /// Triple struct containing edge weight and the edge.
380 /// A handle to the function-wide block frequency pass.
420 /// slab-like allocator, and destroy them after the pass completes. An
435 /// analyzed. These basic blocks cannot be re-ordered safely by
445 auto Count = MBFI->getBlockProfileCount(BB); in getBlockCountOrFrequency()
451 return MBFI->getBlockFreq(BB); in getBlockCountOrFrequency()
550 /// Returns true if a block should be tail-duplicated to increase fallthrough
553 /// Check the edge frequencies to see if tail duplication will increase
572 /// Get the best pair of non-conflicting edges.
583 /// Find chains of triangles to tail-duplicate where a global analysis works,
587 /// Apply a post-processing step optimizing block placement.
606 assert(F); in allowTailDupPlacement()
607 return TailDupPlacement && !F->getTarget().requiresStructuredCFG(); in allowTailDupPlacement()
646 OS << " ('" << BB->getName() << "')"; in INITIALIZE_PASS_DEPENDENCY()
657 /// chain which reach the zero-predecessor state to the appropriate worklist.
671 /// but if a block that was to be placed is completely tail-duplicated away,
677 // Add any successors for which this is the only un-placed in-loop in markBlockSuccessors()
678 // predecessor to the worklist as a viable candidate for CFG-neutral in markBlockSuccessors()
681 for (MachineBasicBlock *Succ : MBB->successors()) { in markBlockSuccessors()
682 if (BlockFilter && !BlockFilter->count(Succ)) in markBlockSuccessors()
689 // This is a cross-chain edge that is within the loop, so decrement the in markBlockSuccessors()
692 --SuccChain.UnscheduledPredecessors > 0) in markBlockSuccessors()
696 if (NewBB->isEHPad()) in markBlockSuccessors()
711 // Adjust edge probabilities by excluding edges pointing to blocks that is in collectViableSuccessors()
715 // --->A in collectViableSuccessors()
719 // ----D E in collectViableSuccessors()
721 // Assume A->C is very hot (>90%), and C->D has a 50% probability, then after in collectViableSuccessors()
722 // A->C is chosen as a fall-through, D won't be selected as a successor of C in collectViableSuccessors()
723 // due to CFG constraint (the probability of C->D is not greater than in collectViableSuccessors()
724 // HotProb to break topo-order). If we exclude E that is not in BlockFilter in collectViableSuccessors()
725 // when calculating the probability of C->D, D will be selected and we in collectViableSuccessors()
728 for (MachineBasicBlock *Succ : BB->successors()) { in collectViableSuccessors()
730 if (Succ->isEHPad() || (BlockFilter && !BlockFilter->count(Succ))) { in collectViableSuccessors()
736 } else if (Succ != *SuccChain->begin()) { in collectViableSuccessors()
738 << " -> Mid chain!\n"); in collectViableSuccessors()
743 AdjustedSumProb -= MBPI->getEdgeProbability(BB, Succ); in collectViableSuccessors()
773 // We don't want to count self-loops in hasSameSuccessors()
791 if (BB->succ_size() == 1) in shouldTailDuplicate()
801 /// TODO(iteratee): Use 64-bit fixed point edge frequencies everywhere.
805 BlockFrequency Gain = A - B; in greaterWithBias()
809 /// Check the edge frequencies to see if tail duplication will increase
819 // First: does succ have a successor that post-dominates? This affects the in isProfitableToTailDup()
835 // '=' : Branch taken for that CFG edge in isProfitableToTailDup()
846 BranchProbability PProb = MBPI->getEdgeProbability(BB, Succ); in isProfitableToTailDup()
847 auto BBFreq = MBFI->getBlockFreq(BB); in isProfitableToTailDup()
848 auto SuccFreq = MBFI->getBlockFreq(Succ); in isProfitableToTailDup()
851 BlockFrequency EntryFreq = MBFI->getEntryFreq(); in isProfitableToTailDup()
860 auto Prob = MBPI->getEdgeProbability(Succ, SuccSucc); in isProfitableToTailDup()
864 if (MPDT->dominates(SuccSucc, Succ)) { in isProfitableToTailDup()
869 // For the comparisons, we need to know Succ's best incoming edge that isn't in isProfitableToTailDup()
872 for (MachineBasicBlock *SuccPred : Succ->predecessors()) { in isProfitableToTailDup()
875 || (BlockFilter && !BlockFilter->count(SuccPred))) in isProfitableToTailDup()
877 auto Freq = MBFI->getBlockFreq(SuccPred) in isProfitableToTailDup()
878 * MBPI->getEdgeProbability(SuccPred, Succ); in isProfitableToTailDup()
882 // Qin is Succ's best unplaced incoming edge that isn't BB in isProfitableToTailDup()
884 // If it doesn't have a post-dominating successor, here is the calculation: in isProfitableToTailDup()
896 // '=' : Branch taken for that CFG edge in isProfitableToTailDup()
900 // Let F = SuccFreq - Qin in isProfitableToTailDup()
903 if (PDom == nullptr || !Succ->isSuccessor(PDom)) { in isProfitableToTailDup()
905 BranchProbability VProb = AdjustedSuccSumProb - UProb; in isProfitableToTailDup()
906 BlockFrequency F = SuccFreq - Qin; in isProfitableToTailDup()
913 BranchProbability UProb = MBPI->getEdgeProbability(Succ, PDom); in isProfitableToTailDup()
914 BranchProbability VProb = AdjustedSuccSumProb - UProb; in isProfitableToTailDup()
917 BlockFrequency F = SuccFreq - Qin; in isProfitableToTailDup()
918 // If there is a post-dominating successor, here is the calculation: in isProfitableToTailDup()
933 // '=' : Branch taken for that CFG edge in isProfitableToTailDup()
935 // Let F = SuccFreq - Qin in isProfitableToTailDup()
974 if (BB->succ_size() != 2 || ViableSuccs.size() != 2) in isTrellis()
977 SmallPtrSet<const MachineBasicBlock *, 2> Successors(BB->succ_begin(), in isTrellis()
978 BB->succ_end()); in isTrellis()
984 for (auto *SuccPred : Succ->predecessors()) { in isTrellis()
988 for (MachineBasicBlock *CheckSucc : SuccPred->successors()) in isTrellis()
994 if (SuccPred == BB || (BlockFilter && !BlockFilter->count(SuccPred)) || in isTrellis()
1016 /// case of a conflict, one of them should be replaced with a 2nd best edge.
1038 if (BestA->Src == BestB->Src) { in getBestNonConflictingEdges()
1042 BlockFrequency BestAScore = BestA->Weight + SecondBestB->Weight; in getBestNonConflictingEdges()
1043 BlockFrequency BestBScore = BestB->Weight + SecondBestA->Weight; in getBestNonConflictingEdges()
1049 // Arrange for the BB edge to be in BestA if it exists. in getBestNonConflictingEdges()
1050 if (BestB->Src == BB) in getBestNonConflictingEdges()
1058 /// the best incoming edge for each successor in the trellis. If those conflict,
1070 SmallPtrSet<const MachineBasicBlock *, 4> Successors(BB->succ_begin(), in getBestTrellisSuccessor()
1071 BB->succ_end()); in getBestTrellisSuccessor()
1079 // Collect the edge frequencies of all edges that form the trellis. in getBestTrellisSuccessor()
1083 for (MachineBasicBlock *SuccPred : Succ->predecessors()) { in getBestTrellisSuccessor()
1086 if ((BlockFilter && !BlockFilter->count(SuccPred)) || in getBestTrellisSuccessor()
1090 BlockFrequency EdgeFreq = MBFI->getBlockFreq(SuccPred) * in getBestTrellisSuccessor()
1091 MBPI->getEdgeProbability(SuccPred, Succ); in getBestTrellisSuccessor()
1104 // better fallthrough edge for all the successors. in getBestTrellisSuccessor()
1109 // Did we pick the triangle edge? If tail-duplication is profitable, do in getBestTrellisSuccessor()
1110 // that instead. Otherwise merge the triangle edge now while we know it is in getBestTrellisSuccessor()
1113 // The edges are BB->Succ1->Succ2, and we're looking to see if BB->Succ2 in getBestTrellisSuccessor()
1117 // Check to see if tail-duplication would be profitable. in getBestTrellisSuccessor()
1120 isProfitableToTailDup(BB, Succ2, MBPI->getEdgeProbability(BB, Succ1), in getBestTrellisSuccessor()
1123 MBPI->getEdgeProbability(BB, Succ2), AdjustedSumProb); in getBestTrellisSuccessor()
1132 // We have already computed the optimal edge for the other side of the in getBestTrellisSuccessor()
1138 MBPI->getEdgeProbability(BB, TrellisSucc), AdjustedSumProb); in getBestTrellisSuccessor()
1146 /// fallthrough candidate block \p Succ (of block \p BB) can be tail-duplicated
1160 SmallPtrSet<const MachineBasicBlock *, 4> Successors(BB->succ_begin(), in canTailDuplicateUnplacedPreds()
1161 BB->succ_end()); in canTailDuplicateUnplacedPreds()
1162 for (MachineBasicBlock *Pred : Succ->predecessors()) { in canTailDuplicateUnplacedPreds()
1164 // tail-duplicated into. in canTailDuplicateUnplacedPreds()
1166 if (Pred == BB || (BlockFilter && !BlockFilter->count(Pred)) in canTailDuplicateUnplacedPreds()
1167 || (BlockToChain[Pred] == &Chain && !Succ->succ_empty())) in canTailDuplicateUnplacedPreds()
1202 // to trellises created by tail-duplication, so we just look for the in canTailDuplicateUnplacedPreds()
1217 if (F->getFunction().hasProfileData()) in canTailDuplicateUnplacedPreds()
1224 if (Succ->succ_empty()) in canTailDuplicateUnplacedPreds()
1248 if ((NumDup > Succ->succ_size()) || !Duplicate) in canTailDuplicateUnplacedPreds()
1255 /// tail-duplicate them all, but a local analysis would not find them.
1257 /// 1) The post-dominators marked 50% are actually taken 55% (This shrinks with
1260 /// U-shaped distribution.
1261 /// [http://nrs.harvard.edu/urn-3:HUL.InstRepos:24015805]
1279 assert(getKey()->isSuccessor(dst) && in precomputeTriangleChains()
1284 unsigned count() const { return Edges.size() - 1; } in precomputeTriangleChains()
1294 LLVM_DEBUG(dbgs() << "Pre-computing triangle chains.\n"); in precomputeTriangleChains()
1304 if (!MPDT->dominates(Succ, &BB)) in precomputeTriangleChains()
1309 // If BB doesn't have a post-dominating successor, it doesn't form a in precomputeTriangleChains()
1314 if (MBPI->getEdgeProbability(&BB, PDom) < BranchProbability(50, 100)) in precomputeTriangleChains()
1321 // If PDom can't tail-duplicate into it's non-BB predecessors, then this in precomputeTriangleChains()
1323 for (MachineBasicBlock* Pred : PDom->predecessors()) { in precomputeTriangleChains()
1331 // If we can't tail-duplicate PDom to its predecessors, then skip this in precomputeTriangleChains()
1344 TriangleChain Chain = std::move(Found->second); in precomputeTriangleChains()
1350 assert(InsertResult.second && "Block seen twice."); in precomputeTriangleChains()
1357 // ComputedEdges is never iterated, so this doesn't lead to non-determinism. in precomputeTriangleChains()
1368 LLVM_DEBUG(dbgs() << "Marking edge: " << getBlockName(src) << "->" in precomputeTriangleChains()
1370 << " as pre-computed based on triangles.\n"); in precomputeTriangleChains()
1373 assert(InsertResult.second && "Block seen twice."); in precomputeTriangleChains()
1382 // When profile is available, we need to handle the triangle-shape CFG.
1385 if (!BB->getParent()->getFunction().hasProfileData()) in getLayoutSuccessorProbThreshold()
1387 if (BB->succ_size() == 2) { in getLayoutSuccessorProbThreshold()
1388 const MachineBasicBlock *Succ1 = *BB->succ_begin(); in getLayoutSuccessorProbThreshold()
1389 const MachineBasicBlock *Succ2 = *(BB->succ_begin() + 1); in getLayoutSuccessorProbThreshold()
1390 if (Succ1->isSuccessor(Succ2) || Succ2->isSuccessor(Succ1)) { in getLayoutSuccessorProbThreshold()
1391 /* See case 1 below for the cost analysis. For BB->Succ to in getLayoutSuccessorProbThreshold()
1393 * Prob(BB->Succ) > 2 * Prob(BB->Pred) in getLayoutSuccessorProbThreshold()
1395 * (1-T) * Prob(BB->Succ) > T * Prob(BB->Pred) in getLayoutSuccessorProbThreshold()
1396 * So T / (1 - T) = 2, Yielding T = 2/3 in getLayoutSuccessorProbThreshold()
1411 /// \p RealSuccProb: The un-adjusted probability.
1413 /// \p BlockFilter: if non-null, the set of blocks that make up the loop being
1426 // ------------------------------------- in hasBetterLayoutPredecessor()
1427 // Case 1: triangular shape CFG (if-then): in hasBetterLayoutPredecessor()
1434 // In this case, we are evaluating whether to select edge -> Succ, e.g. in hasBetterLayoutPredecessor()
1444 // from BB to Succ, so to make BB->Succ a viable candidate, the following in hasBetterLayoutPredecessor()
1446 // 2 * freq(BB->Pred) * taken_branch_cost + unconditional_jump_cost in hasBetterLayoutPredecessor()
1447 // < freq(BB->Succ) * taken_branch_cost. in hasBetterLayoutPredecessor()
1449 // freq(BB->Succ) > 2 * freq(BB->Pred), i.e., in hasBetterLayoutPredecessor()
1450 // prob(BB->Succ) > 2 * prob(BB->Pred) in hasBetterLayoutPredecessor()
1453 // probability threshold that is needed for edge BB->Succ to be considered. in hasBetterLayoutPredecessor()
1456 // ----------------------------------------------------------------- in hasBetterLayoutPredecessor()
1457 // Case 2: diamond like CFG (if-then-else): in hasBetterLayoutPredecessor()
1466 // The current block is BB and edge BB->Succ is now being evaluated. in hasBetterLayoutPredecessor()
1467 // Note that edge S->BB was previously already selected because in hasBetterLayoutPredecessor()
1468 // prob(S->BB) > prob(S->Pred). in hasBetterLayoutPredecessor()
1474 // topo-order: in hasBetterLayoutPredecessor()
1476 // S----- ---S in hasBetterLayoutPredecessor()
1478 // ---BB | | BB in hasBetterLayoutPredecessor()
1480 // | Pred-- | Succ-- in hasBetterLayoutPredecessor()
1482 // ---Succ ---Pred-- in hasBetterLayoutPredecessor()
1484 // cost = freq(S->Pred) + freq(BB->Succ) cost = 2 * freq (S->Pred) in hasBetterLayoutPredecessor()
1485 // = freq(S->Pred) + freq(S->BB) in hasBetterLayoutPredecessor()
1488 // cost (number of taken branches) with layout S->BB->Succ->Pred is 2 * in hasBetterLayoutPredecessor()
1489 // freq(S->Pred) while the cost of topo order is freq(S->Pred) + freq(S->BB). in hasBetterLayoutPredecessor()
1490 // We know Prob(S->BB) > Prob(S->Pred), so freq(S->BB) > freq(S->Pred), which in hasBetterLayoutPredecessor()
1493 // conservative. If the branch prediction is wrong, breaking the topo-order in hasBetterLayoutPredecessor()
1495 // strong biased branch at block S with Prob(S->BB) in order to select in hasBetterLayoutPredecessor()
1496 // BB->Succ. This is equivalent to looking the CFG backward with backward in hasBetterLayoutPredecessor()
1497 // edge: Prob(Succ->BB) needs to >= HotProb in order to be selected (without in hasBetterLayoutPredecessor()
1499 // -------------------------------------------------------------------------- in hasBetterLayoutPredecessor()
1512 // The current block is BB and edge BB->S1 is now being evaluated. in hasBetterLayoutPredecessor()
1513 // As above S->BB was already selected because in hasBetterLayoutPredecessor()
1514 // prob(S->BB) > prob(S->Pred). Assume that prob(BB->S1) >= prob(BB->S2). in hasBetterLayoutPredecessor()
1516 // topo-order: in hasBetterLayoutPredecessor()
1518 // S-------| ---S in hasBetterLayoutPredecessor()
1520 // ---BB | | BB in hasBetterLayoutPredecessor()
1522 // | Pred----| | S1---- in hasBetterLayoutPredecessor()
1524 // --(S1 or S2) ---Pred-- in hasBetterLayoutPredecessor()
1528 // topo-cost = freq(S->Pred) + freq(BB->S1) + freq(BB->S2) in hasBetterLayoutPredecessor()
1529 // + min(freq(Pred->S1), freq(Pred->S2)) in hasBetterLayoutPredecessor()
1530 // Non-topo-order cost: in hasBetterLayoutPredecessor()
1531 // non-topo-cost = 2 * freq(S->Pred) + freq(BB->S2). in hasBetterLayoutPredecessor()
1532 // To be conservative, we can assume that min(freq(Pred->S1), freq(Pred->S2)) in hasBetterLayoutPredecessor()
1534 // freq(S->Pred) < freq(BB->S1). in hasBetterLayoutPredecessor()
1542 BlockFrequency CandidateEdgeFreq = MBFI->getBlockFreq(BB) * RealSuccProb; in hasBetterLayoutPredecessor()
1545 for (MachineBasicBlock *Pred : Succ->predecessors()) { in hasBetterLayoutPredecessor()
1548 (BlockFilter && !BlockFilter->count(Pred)) || in hasBetterLayoutPredecessor()
1549 PredChain == &Chain || Pred != *std::prev(PredChain->end()) || in hasBetterLayoutPredecessor()
1561 // We select edge BB->Succ if in hasBetterLayoutPredecessor()
1562 // freq(BB->Succ) > freq(Succ) * HotProb in hasBetterLayoutPredecessor()
1563 // i.e. freq(BB->Succ) > freq(BB->Succ) * HotProb + freq(Pred->Succ) * in hasBetterLayoutPredecessor()
1565 // i.e. freq((BB->Succ) * (1 - HotProb) > freq(Pred->Succ) * HotProb in hasBetterLayoutPredecessor()
1567 // prob(BB->Succ) > HotProb. (freq(Succ) = freq(BB) for a triangle) in hasBetterLayoutPredecessor()
1569 MBFI->getBlockFreq(Pred) * MBPI->getEdgeProbability(Pred, Succ); in hasBetterLayoutPredecessor()
1577 LLVM_DEBUG(dbgs() << " Not a candidate: " << getBlockName(Succ) << " -> " in hasBetterLayoutPredecessor()
1578 << SuccProb << " (prob) (non-cold CFG conflict)\n"); in hasBetterLayoutPredecessor()
1615 MachineBasicBlock *Succ = FoundEdge->second.BB; in selectBestSuccessor()
1618 if (BB->isSuccessor(Succ) && (!BlockFilter || BlockFilter->count(Succ)) && in selectBestSuccessor()
1619 SuccChain != &Chain && Succ == *SuccChain->begin()) in selectBestSuccessor()
1620 return FoundEdge->second; in selectBestSuccessor()
1630 // tail-duplication. We keep this vector so we can perform the probability in selectBestSuccessor()
1635 auto RealSuccProb = MBPI->getEdgeProbability(BB, Succ); in selectBestSuccessor()
1640 // Skip the edge \c BB->Succ if block \c Succ has a better layout in selectBestSuccessor()
1705 /// loop body in order to improve i-cache behavior.
1721 bool IsEHPad = WorkList[0]->isEHPad(); in selectBestCandidateBlock()
1726 assert(MBB->isEHPad() == IsEHPad && in selectBestCandidateBlock()
1733 assert(SuccChain.UnscheduledPredecessors == 0 && in selectBestCandidateBlock()
1734 "Found CFG-violating block"); in selectBestCandidateBlock()
1736 BlockFrequency CandidateFreq = MBFI->getBlockFreq(MBB); in selectBestCandidateBlock()
1737 LLVM_DEBUG(dbgs() << " " << getBlockName(MBB) << " -> " in selectBestCandidateBlock()
1738 << printBlockFreq(MBFI->getMBFI(), CandidateFreq) in selectBestCandidateBlock()
1750 // +--------------------------+ in selectBestCandidateBlock()
1752 // InnerLp -> InnerCleanup OuterLp -> OuterCleanup -> Resume in selectBestCandidateBlock()
1756 // +-------------------------------------+ in selectBestCandidateBlock()
1758 // OuterLp -> OuterCleanup -> Resume InnerLp -> InnerCleanup in selectBestCandidateBlock()
1775 /// re-scanning the entire sequence on repeated calls to this routine.
1780 for (MachineFunction::iterator I = PrevUnplacedBlockIt, E = F->end(); I != E; in getFirstUnplacedBlock()
1787 return *BlockToChain[&*I]->begin(); in getFirstUnplacedBlock()
1807 assert(BlockFilter); in getFirstUnplacedBlock()
1808 for (; PrevUnplacedBlockInFilterIt != BlockFilter->end(); in getFirstUnplacedBlock()
1812 return *C->begin(); in getFirstUnplacedBlock()
1826 assert( in fillWorkLists()
1830 assert(BlockToChain[ChainBB] == &Chain && in fillWorkLists()
1832 for (MachineBasicBlock *Pred : ChainBB->predecessors()) { in fillWorkLists()
1833 if (BlockFilter && !BlockFilter->count(Pred)) in fillWorkLists()
1845 if (BB->isEHPad()) in fillWorkLists()
1854 assert(HeadBB && "BB must not be null.\n"); in buildChain()
1855 assert(BlockToChain[HeadBB] == &Chain && "BlockToChainMap mis-match.\n"); in buildChain()
1856 MachineFunction::iterator PrevUnplacedBlockIt = F->begin(); in buildChain()
1859 PrevUnplacedBlockInFilterIt = BlockFilter->begin(); in buildChain()
1865 assert(BB && "null block found at end of chain in loop."); in buildChain()
1866 assert(BlockToChain[BB] == &Chain && "BlockToChainMap mis-match in loop."); in buildChain()
1867 assert(*std::prev(Chain.end()) == BB && "BB Not found at end of chain."); in buildChain()
1909 if (!BB->isSuccessor(BestSucc)) in buildChain()
1932 // -->OldTop<-
1936 // ---Pred |
1938 // BB-----
1947 if (BottomBlock->pred_size() != 1) in canMoveBottomBlockToTop()
1949 MachineBasicBlock *Pred = *BottomBlock->pred_begin(); in canMoveBottomBlockToTop()
1950 if (Pred->succ_size() != 2) in canMoveBottomBlockToTop()
1953 MachineBasicBlock *OtherBB = *Pred->succ_begin(); in canMoveBottomBlockToTop()
1955 OtherBB = *Pred->succ_rbegin(); in canMoveBottomBlockToTop()
1968 for (MachineBasicBlock *Pred : Top->predecessors()) { in TopFallThroughFreq()
1971 (!PredChain || Pred == *std::prev(PredChain->end()))) { in TopFallThroughFreq()
1974 auto TopProb = MBPI->getEdgeProbability(Pred, Top); in TopFallThroughFreq()
1976 for (MachineBasicBlock *Succ : Pred->successors()) { in TopFallThroughFreq()
1977 auto SuccProb = MBPI->getEdgeProbability(Pred, Succ); in TopFallThroughFreq()
1982 (!SuccChain || Succ == *SuccChain->begin())) { in TopFallThroughFreq()
1988 BlockFrequency EdgeFreq = MBFI->getBlockFreq(Pred) * in TopFallThroughFreq()
1989 MBPI->getEdgeProbability(Pred, Top); in TopFallThroughFreq()
2000 // In following diagram, edges marked as "-" are reduced fallthrough, edges
2003 // SUM(increased fallthrough) - SUM(decreased fallthrough)
2006 // | -
2008 // --->OldTop
2012 // | Pred --->
2013 // | |-
2015 // --- NewTop <---
2016 // |-
2028 FallThrough2Exit = MBFI->getBlockFreq(NewTop) * in FallThroughGains()
2029 MBPI->getEdgeProbability(NewTop, ExitBB); in FallThroughGains()
2030 BlockFrequency BackEdgeFreq = MBFI->getBlockFreq(NewTop) * in FallThroughGains()
2031 MBPI->getEdgeProbability(NewTop, OldTop); in FallThroughGains()
2036 for (MachineBasicBlock *Pred : NewTop->predecessors()) { in FallThroughGains()
2040 if (!PredChain || Pred == *std::prev(PredChain->end())) { in FallThroughGains()
2042 MBFI->getBlockFreq(Pred) * MBPI->getEdgeProbability(Pred, NewTop); in FallThroughGains()
2054 for (MachineBasicBlock *Succ : BestPred->successors()) { in FallThroughGains()
2060 if ((SuccChain && (Succ != *SuccChain->begin())) || in FallThroughGains()
2063 BlockFrequency EdgeFreq = MBFI->getBlockFreq(BestPred) * in FallThroughGains()
2064 MBPI->getEdgeProbability(BestPred, Succ); in FallThroughGains()
2068 BlockFrequency OrigEdgeFreq = MBFI->getBlockFreq(BestPred) * in FallThroughGains()
2069 MBPI->getEdgeProbability(BestPred, NewTop); in FallThroughGains()
2084 Result = Gains - Lost; in FallThroughGains()
2129 for (MachineBasicBlock *Pred : OldTop->predecessors()) { in findBestLoopTopHelper()
2135 << Pred->succ_size() << " successors, " in findBestLoopTopHelper()
2136 << printBlockFreq(MBFI->getMBFI(), *Pred) << " freq\n"); in findBestLoopTopHelper()
2137 if (Pred->succ_size() > 2) in findBestLoopTopHelper()
2141 if (Pred->succ_size() == 2) { in findBestLoopTopHelper()
2142 OtherBB = *Pred->succ_begin(); in findBestLoopTopHelper()
2144 OtherBB = *Pred->succ_rbegin(); in findBestLoopTopHelper()
2154 ((Gains == BestGains) && Pred->isLayoutSuccessor(OldTop)))) { in findBestLoopTopHelper()
2167 while (BestPred->pred_size() == 1 && in findBestLoopTopHelper()
2168 (*BestPred->pred_begin())->succ_size() == 1 && in findBestLoopTopHelper()
2169 *BestPred->pred_begin() != L.getHeader()) in findBestLoopTopHelper()
2170 BestPred = *BestPred->pred_begin(); in findBestLoopTopHelper()
2190 bool OptForSize = F->getFunction().hasOptSize() || in findBestLoopTop()
2218 // header has be pre-merged into a chain due to predecessors not having in findBestLoopExit()
2221 // a non-contiguous range of blocks which is Very Bad. So start with the in findBestLoopExit()
2240 // mid-way through an inner loop or a successor of an unanalyzable branch. in findBestLoopExit()
2245 // exiting successor and whether it has a viable non-exiting successor. in findBestLoopExit()
2251 for (MachineBasicBlock *Succ : MBB->successors()) { in findBestLoopExit()
2252 if (Succ->isEHPad()) in findBestLoopExit()
2259 LLVM_DEBUG(dbgs() << " exiting: " << getBlockName(MBB) << " -> " in findBestLoopExit()
2264 auto SuccProb = MBPI->getEdgeProbability(MBB, Succ); in findBestLoopExit()
2266 LLVM_DEBUG(dbgs() << " looping: " << getBlockName(MBB) << " -> " in findBestLoopExit()
2273 if (MachineLoop *ExitLoop = MLI->getLoopFor(Succ)) { in findBestLoopExit()
2274 SuccLoopDepth = ExitLoop->getLoopDepth(); in findBestLoopExit()
2275 if (ExitLoop->contains(&L)) in findBestLoopExit()
2279 BlockFrequency ExitEdgeFreq = MBFI->getBlockFreq(MBB) * SuccProb; in findBestLoopExit()
2281 dbgs() << " exiting: " << getBlockName(MBB) << " -> " in findBestLoopExit()
2283 << printBlockFreq(MBFI->getMBFI(), ExitEdgeFreq) << ")\n"); in findBestLoopExit()
2288 BranchProbability Bias(100 - ExitBlockBias, 100); in findBestLoopExit()
2291 (MBB->isLayoutSuccessor(Succ) && in findBestLoopExit()
2337 for (MachineBasicBlock *Pred : Top->predecessors()) { in hasViableTopFallthrough()
2340 (!PredChain || Pred == *std::prev(PredChain->end()))) { in hasViableTopFallthrough()
2343 auto TopProb = MBPI->getEdgeProbability(Pred, Top); in hasViableTopFallthrough()
2345 for (MachineBasicBlock *Succ : Pred->successors()) { in hasViableTopFallthrough()
2346 auto SuccProb = MBPI->getEdgeProbability(Pred, Succ); in hasViableTopFallthrough()
2350 if ((!SuccChain || Succ == *SuccChain->begin()) && SuccProb > TopProb) { in hasViableTopFallthrough()
2383 if (Top->isEntryBlock()) in rotateLoop()
2392 for (MachineBasicBlock *Succ : Bottom->successors()) { in rotateLoop()
2395 (!SuccChain || Succ == *SuccChain->begin())) in rotateLoop()
2412 // If there is no bottom->top edge, but the chosen exit block does have in rotateLoop()
2416 // B1, B2, ..., Bn, where Bk is a ExitingBB - chosen exit block. in rotateLoop()
2420 // If we had a fallthrough Bk -> Bk+1 it is broken now. in rotateLoop()
2421 // It might be compensated by fallthrough Bn -> B1. in rotateLoop()
2430 assert(std::next(ExitIt) != LoopChain.end() && in rotateLoop()
2433 if (ExitingBB->isSuccessor(NextBlockInChain)) in rotateLoop()
2434 if (!Bottom->isSuccessor(Top)) in rotateLoop()
2448 /// 1. The possibly missed fall through edge (if it exists) from BB out of
2452 /// 3. The missed fall through edge (if it exists) from the last BB to the
2463 if (ChainHeaderBB->isEntryBlock()) in rotateLoopWithProfile()
2471 unsigned Scale) -> BlockFrequency { in rotateLoopWithProfile()
2479 // Compute the cost of the missed fall-through edge to the loop header if the in rotateLoopWithProfile()
2483 for (auto *Pred : ChainHeaderBB->predecessors()) { in rotateLoopWithProfile()
2486 (!PredChain || Pred == *std::prev(PredChain->end()))) { in rotateLoopWithProfile()
2487 auto EdgeFreq = MBFI->getBlockFreq(Pred) * in rotateLoopWithProfile()
2488 MBPI->getEdgeProbability(Pred, ChainHeaderBB); in rotateLoopWithProfile()
2492 if (Pred->succ_size() == 1) in rotateLoopWithProfile()
2499 // its hottest exit edge. For each loop rotation, we define the loop exit cost in rotateLoopWithProfile()
2501 // edge from the tail of the loop chain. in rotateLoopWithProfile()
2505 for (auto *Succ : BB->successors()) { in rotateLoopWithProfile()
2508 (!SuccChain || Succ == *SuccChain->begin())) { in rotateLoopWithProfile()
2509 auto SuccProb = MBPI->getEdgeProbability(BB, Succ); in rotateLoopWithProfile()
2514 auto ExitFreq = MBFI->getBlockFreq(BB) * LargestExitEdgeProb; in rotateLoopWithProfile()
2536 // cost of the missed fall through edge from outside of the loop to the in rotateLoopWithProfile()
2547 // The cost of breaking the once fall-through edge from the tail to the top in rotateLoopWithProfile()
2557 // of the edge to the chain head, then the cost will be in rotateLoopWithProfile()
2561 if (TailBB->isSuccessor(*Iter)) { in rotateLoopWithProfile()
2562 auto TailBBFreq = MBFI->getBlockFreq(TailBB); in rotateLoopWithProfile()
2563 if (TailBB->succ_size() == 1) in rotateLoopWithProfile()
2565 else if (TailBB->succ_size() == 2) { in rotateLoopWithProfile()
2566 auto TailToHeadProb = MBPI->getEdgeProbability(TailBB, *Iter); in rotateLoopWithProfile()
2578 << printBlockFreq(MBFI->getMBFI(), Cost) << "\n"); in rotateLoopWithProfile()
2610 if (F->getFunction().hasProfileData() || ForceLoopColdBlock) { in collectLoopBlockSet()
2612 for (auto *LoopPred : L.getHeader()->predecessors()) in collectLoopBlockSet()
2614 LoopFreq += MBFI->getBlockFreq(LoopPred) * in collectLoopBlockSet()
2615 MBPI->getEdgeProbability(LoopPred, L.getHeader()); in collectLoopBlockSet()
2620 auto Freq = MBFI->getBlockFreq(LoopBB).getFrequency(); in collectLoopBlockSet()
2645 assert(BlockWorkList.empty() && in buildLoopChains()
2647 assert(EHPadWorkList.empty() && in buildLoopChains()
2656 (PreciseRotationCost && F->getFunction().hasProfileData()); in buildLoopChains()
2666 // branches by placing an exit edge at the bottom. in buildLoopChains()
2681 assert(LoopChain.UnscheduledPredecessors == 0 && in buildLoopChains()
2709 // from a loop block to a non-loop block or vice versa. in buildLoopChains()
2725 assert(!BadLoop && "Detected problems with the placement of this loop."); in buildLoopChains()
2736 for (MachineFunction::iterator FI = F->begin(), FE = F->end(); FI != FE; in buildCFGChains()
2746 if (!TII->analyzeBranch(*BB, TBB, FBB, Cond) || !FI->canFallThrough()) in buildCFGChains()
2753 assert(NextFI != FE && "Can't fallthrough past the last block."); in buildCFGChains()
2754 LLVM_DEBUG(dbgs() << "Pre-merging due to unanalyzable fallthrough: " in buildCFGChains()
2755 << getBlockName(BB) << " -> " << getBlockName(NextBB) in buildCFGChains()
2757 Chain->merge(NextBB, nullptr); in buildCFGChains()
2766 // Build any loop-based chains. in buildCFGChains()
2771 assert(BlockWorkList.empty() && in buildCFGChains()
2773 assert(EHPadWorkList.empty() && in buildCFGChains()
2780 BlockChain &FunctionChain = *BlockToChain[&F->front()]; in buildCFGChains()
2781 buildChain(&F->front(), FunctionChain); in buildCFGChains()
2806 assert(!BadFunc && "Detected problems with the block placement."); in buildCFGChains()
2812 F->getNumBlockIDs()); in buildCFGChains()
2817 OriginalLayoutSuccessors[LastMBB->getNumber()] = &MBB; in buildCFGChains()
2820 OriginalLayoutSuccessors[F->back().getNumber()] = nullptr; in buildCFGChains()
2824 MachineFunction::iterator InsertPos = F->begin(); in buildCFGChains()
2825 LLVM_DEBUG(dbgs() << "[MBP] Function: " << F->getName() << "\n"); in buildCFGChains()
2831 F->splice(InsertPos, ChainBB); in buildCFGChains()
2841 // than assert when the branch cannot be analyzed in order to remove this in buildCFGChains()
2851 assert((!TII->analyzeBranch(*PrevBB, TBB, FBB, Cond) || in buildCFGChains()
2852 !PrevBB->canFallThrough()) && in buildCFGChains()
2853 "Unexpected block with un-analyzable fallthrough!"); in buildCFGChains()
2860 // o. it may fall-through to a block without explicit "goto" instruction in buildCFGChains()
2861 // before layout, and no longer fall-through it after layout; or in buildCFGChains()
2872 // PrevBB->updateTerminator(); in buildCFGChains()
2875 // if (TII->analyzeBranch(*PrevBB, TBB, FBB, Cond)) { in buildCFGChains()
2880 if (!TII->analyzeBranch(*PrevBB, TBB, FBB, Cond)) { in buildCFGChains()
2881 PrevBB->updateTerminator(OriginalLayoutSuccessors[PrevBB->getNumber()]); in buildCFGChains()
2888 if (!TII->analyzeBranch(F->back(), TBB, FBB, Cond)) { in buildCFGChains()
2889 MachineBasicBlock *PrevBB = &F->back(); in buildCFGChains()
2890 PrevBB->updateTerminator(OriginalLayoutSuccessors[PrevBB->getNumber()]); in buildCFGChains()
2898 BlockChain &FunctionChain = *BlockToChain[&F->front()]; in optimizeBranches()
2910 if (!TII->analyzeBranch(*ChainBB, TBB, FBB, Cond, /*AllowModify*/ true)) { in optimizeBranches()
2911 // If PrevBB has a two-way branch, try to re-order the branches in optimizeBranches()
2914 MBPI->getEdgeProbability(ChainBB, FBB) > in optimizeBranches()
2915 MBPI->getEdgeProbability(ChainBB, TBB) && in optimizeBranches()
2916 !TII->reverseBranchCondition(Cond)) { in optimizeBranches()
2919 LLVM_DEBUG(dbgs() << " Edge probability: " in optimizeBranches()
2920 << MBPI->getEdgeProbability(ChainBB, FBB) << " vs " in optimizeBranches()
2921 << MBPI->getEdgeProbability(ChainBB, TBB) << "\n"); in optimizeBranches()
2923 TII->removeBranch(*ChainBB); in optimizeBranches()
2924 TII->insertBranch(*ChainBB, FBB, TBB, Cond, dl); in optimizeBranches()
2936 if (F->getFunction().hasMinSize() || in alignBlocks()
2937 (F->getFunction().hasOptSize() && !TLI->alignLoopsWithOptSize())) in alignBlocks()
2939 BlockChain &FunctionChain = *BlockToChain[&F->front()]; in alignBlocks()
2944 BlockFrequency EntryFreq = MBFI->getBlockFreq(&F->front()); in alignBlocks()
2950 // Don't align non-looping basic blocks. These are unlikely to execute in alignBlocks()
2954 MachineLoop *L = MLI->getLoopFor(ChainBB); in alignBlocks()
2958 const Align TLIAlign = TLI->getPrefLoopAlignment(L); in alignBlocks()
2960 MDNode *LoopID = L->getLoopID(); in alignBlocks()
2962 for (const MDOperand &MDO : llvm::drop_begin(LoopID->operands())) { in alignBlocks()
2966 MDString *S = dyn_cast<MDString>(MD->getOperand(0)); in alignBlocks()
2969 if (S->getString() == "llvm.loop.align") { in alignBlocks()
2970 assert(MD->getNumOperands() == 2 && in alignBlocks()
2971 "per-loop align metadata should have two operands."); in alignBlocks()
2973 mdconst::extract<ConstantInt>(MD->getOperand(1))->getZExtValue(); in alignBlocks()
2974 assert(MDAlign >= 1 && "per-loop align value must be positive."); in alignBlocks()
2986 BlockFrequency Freq = MBFI->getBlockFreq(ChainBB); in alignBlocks()
2992 MachineBasicBlock *LoopHeader = L->getHeader(); in alignBlocks()
2993 BlockFrequency LoopHeaderFreq = MBFI->getBlockFreq(LoopHeader); in alignBlocks()
2999 !TLI->alignLoopsWithOptSize()) in alignBlocks()
3002 // Check for the existence of a non-layout predecessor which would benefit in alignBlocks()
3013 MaxBytes = TLI->getMaxPermittedBytesForAlignment(ChainBB); in alignBlocks()
3014 ChainBB->setMaxBytesForAlignment(MaxBytes); in alignBlocks()
3019 if (!LayoutPred->isSuccessor(ChainBB)) { in alignBlocks()
3020 ChainBB->setAlignment(LoopAlign); in alignBlocks()
3025 // Align this block if the layout predecessor's edge into this block is in alignBlocks()
3030 MBPI->getEdgeProbability(LayoutPred, ChainBB); in alignBlocks()
3031 BlockFrequency LayoutEdgeFreq = MBFI->getBlockFreq(LayoutPred) * LayoutProb; in alignBlocks()
3033 ChainBB->setAlignment(LoopAlign); in alignBlocks()
3041 /// \p BB - Basic block that may be duplicated.
3043 /// \p LPred - Chosen layout predecessor of \p BB.
3045 /// \p Chain - Chain to which \p LPred belongs, and \p BB will belong.
3046 /// \p BlockFilter - Set of blocks that belong to the loop being laid out.
3049 /// \p PrevUnplacedBlockIt - Iterator pointing to the last block that was
3079 DupBB = *(--ChainEnd); in repeatedlyTailDuplicateBlock()
3100 /// \p BB - Basic block that may be duplicated
3101 /// \p LPred - Chosen layout predecessor of \p BB
3102 /// \p Chain - Chain to which \p LPred belongs, and \p BB will belong.
3103 /// \p BlockFilter - Set of blocks that belong to the loop being laid out.
3106 /// \p PrevUnplacedBlockIt - Iterator pointing to the last block that was
3110 /// \p DuplicatedToLPred - True if the block was duplicated into LPred.
3111 /// \return - True if the block was duplicated into all preds and removed.
3121 LLVM_DEBUG(dbgs() << "Redoing tail duplication for Succ#" << BB->getNumber() in maybeTailDuplicateBlock()
3137 InWorkList = Chain->UnscheduledPredecessors == 0; in maybeTailDuplicateBlock()
3138 Chain->remove(RemBB); in maybeTailDuplicateBlock()
3150 if (RemBB->isEHPad()) in maybeTailDuplicateBlock()
3160 if (It != BlockFilter->end()) { in maybeTailDuplicateBlock()
3165 auto Distance = PrevUnplacedBlockInFilterIt - It - 1; in maybeTailDuplicateBlock()
3166 PrevUnplacedBlockInFilterIt = BlockFilter->erase(It) + Distance; in maybeTailDuplicateBlock()
3167 assert(*PrevUnplacedBlockInFilterIt == PrevBB); in maybeTailDuplicateBlock()
3172 PrevUnplacedBlockInFilterIt = BlockFilter->erase(It); in maybeTailDuplicateBlock()
3174 BlockFilter->erase(It); in maybeTailDuplicateBlock()
3179 MLI->removeBlock(RemBB); in maybeTailDuplicateBlock()
3193 if (F->getFunction().hasProfileData()) { in maybeTailDuplicateBlock()
3198 if (CandidatePreds.size() < BB->pred_size()) in maybeTailDuplicateBlock()
3204 // Update UnscheduledPredecessors to reflect tail-duplication. in maybeTailDuplicateBlock()
3211 if (Pred == LPred || (BlockFilter && !BlockFilter->count(Pred)) in maybeTailDuplicateBlock()
3214 for (MachineBasicBlock *NewSucc : Pred->successors()) { in maybeTailDuplicateBlock()
3215 if (BlockFilter && !BlockFilter->count(NewSucc)) in maybeTailDuplicateBlock()
3219 NewChain->UnscheduledPredecessors++; in maybeTailDuplicateBlock()
3248 if (BlockFilter && !BlockFilter->count(Pred)) in isBestSuccessor()
3251 if (PredChain && (Pred != *std::prev(PredChain->end()))) in isBestSuccessor()
3256 for (MachineBasicBlock *Succ : Pred->successors()) in isBestSuccessor()
3258 if (BlockFilter && !BlockFilter->count(Succ)) in isBestSuccessor()
3261 if (SuccChain && (Succ != *SuccChain->begin())) in isBestSuccessor()
3263 BranchProbability SuccProb = MBPI->getEdgeProbability(Pred, Succ); in isBestSuccessor()
3268 BranchProbability BBProb = MBPI->getEdgeProbability(Pred, BB); in isBestSuccessor()
3275 BlockFrequency Gain = PredFreq * (BBProb - BestProb); in isBestSuccessor()
3288 SmallVector<MachineBasicBlock *, 8> Preds(BB->predecessors()); in findDuplicateCandidates()
3289 SmallVector<MachineBasicBlock *, 8> Succs(BB->successors()); in findDuplicateCandidates()
3293 return MBPI->getEdgeProbability(BB, A) > MBPI->getEdgeProbability(BB, B); in findDuplicateCandidates()
3296 return MBFI->getBlockFreq(A) > MBFI->getBlockFreq(B); in findDuplicateCandidates()
3303 DefaultBranchProb = MBPI->getEdgeProbability(BB, *SuccIt).getCompl(); in findDuplicateCandidates()
3315 // BB----/ OB in findDuplicateCandidates()
3327 // | BB----/ OB in findDuplicateCandidates()
3334 // Orig_taken_branch - Duplicated_taken_branch in findDuplicateCandidates()
3370 DupCost -= PredFreq * MBPI->getEdgeProbability(BB, *SuccIt); in findDuplicateCandidates()
3373 assert(OrigCost >= DupCost); in findDuplicateCandidates()
3374 OrigCost -= DupCost; in findDuplicateCandidates()
3394 if (!F->getFunction().hasProfileData()) in initDupThreshold()
3398 uint64_t HotThreshold = PSI->getOrCompHotCountThreshold(); in initDupThreshold()
3409 BlockFrequency Freq = MBFI->getBlockFreq(&MBB); in initDupThreshold()
3423 // Check for single-block functions and skip them. in runOnMachineFunction()
3443 assert(BlockToChain.empty() && in runOnMachineFunction()
3445 assert(ComputedEdges.empty() && in runOnMachineFunction()
3446 "Computed Edge map should be empty before starting placement."); in runOnMachineFunction()
3457 if (PassConfig->getOptLevel() >= CodeGenOptLevel::Aggressive) { in runOnMachineFunction()
3469 (PassConfig->getOptLevel() < CodeGenOptLevel::Aggressive || in runOnMachineFunction()
3471 TailDupSize = TII->getTailDuplicateSize(PassConfig->getOptLevel()); in runOnMachineFunction()
3476 llvm::shouldOptimizeForSize(&MF, PSI, &MBFI->getMBFI()); in runOnMachineFunction()
3491 PassConfig->getEnableTailMerge() && in runOnMachineFunction()
3504 // Must redo the post-dominator tree if blocks were changed. in runOnMachineFunction()
3506 MPDT->recalculate(MF); in runOnMachineFunction()
3512 // Apply a post-processing optimizing block placement. in runOnMachineFunction()
3518 // Re-create CFG chain so that we can optimizeBranches and alignBlocks. in runOnMachineFunction()
3542 // Align all of the blocks that have no fall-through predecessors to a in runOnMachineFunction()
3546 if (!LayoutPred->isSuccessor(&*MBI)) { in runOnMachineFunction()
3548 MBI->setAlignment(Align(1ULL << AlignAllNonFallThruBlocks), in runOnMachineFunction()
3551 MBI->setAlignment(Align(1ULL << AlignAllNonFallThruBlocks)); in runOnMachineFunction()
3557 F->getFunction().getName() == ViewBlockFreqFuncName)) { in runOnMachineFunction()
3560 MBFI->view("MBP." + MF.getName(), false); in runOnMachineFunction()
3571 BlockIndex.reserve(F->size()); in applyExtTsp()
3573 CurrentBlockOrder.reserve(F->size()); in applyExtTsp()
3580 auto BlockSizes = std::vector<uint64_t>(F->size()); in applyExtTsp()
3581 auto BlockCounts = std::vector<uint64_t>(F->size()); in applyExtTsp()
3585 BlockFrequency BlockFreq = MBFI->getBlockFreq(&MBB); in applyExtTsp()
3588 // - approximate the size of an instruction by 4 bytes, and in applyExtTsp()
3589 // - ignore debug instructions. in applyExtTsp()
3590 // Note: getting the exact size of each block is target-dependent and can be in applyExtTsp()
3599 auto EP = MBPI->getEdgeProbability(&MBB, Succ); in applyExtTsp()
3606 LLVM_DEBUG(dbgs() << "Applying ext-tsp layout for |V| = " << F->size() in applyExtTsp()
3607 << " with profile = " << F->getFunction().hasProfileData() in applyExtTsp()
3608 << " (" << F->getName().str() << ")" in applyExtTsp()
3617 NewBlockOrder.reserve(F->size()); in applyExtTsp()
3631 assert(F->size() == NewBlockOrder.size() && "Incorrect size of block order"); in assignBlockOrder()
3632 F->RenumberBlocks(); in assignBlockOrder()
3636 if (NewBlockOrder[I] != F->getBlockNumbered(I)) { in assignBlockOrder()
3645 SmallVector<MachineBasicBlock *, 4> PrevFallThroughs(F->getNumBlockIDs()); in assignBlockOrder()
3655 F->sort([&](MachineBasicBlock &L, MachineBasicBlock &R) { in assignBlockOrder()
3660 // when required and re-optimize branches when possible. in assignBlockOrder()
3661 const TargetInstrInfo *TII = F->getSubtarget().getInstrInfo(); in assignBlockOrder()
3665 MachineFunction::iterator EndIt = MBB.getParent()->end(); in assignBlockOrder()
3671 TII->insertUnconditionalBranch(MBB, FTMBB, MBB.findBranchDebugLoc()); in assignBlockOrder()
3677 if (TII->analyzeBranch(MBB, TBB, FBB, Cond)) in assignBlockOrder()
3684 F->verify(this, "After optimized block reordering"); in assignBlockOrder()
3693 MachineBasicBlock *HeadBB = &F->front(); in createCFGChainExtTsp()
3700 FunctionChain->merge(&MBB, nullptr); in createCFGChainExtTsp()
3716 /// A handle to the function-wide block frequency pass.
3742 INITIALIZE_PASS_BEGIN(MachineBlockPlacementStats, "block-placement-stats",
3746 INITIALIZE_PASS_END(MachineBlockPlacementStats, "block-placement-stats", in INITIALIZE_PASS_DEPENDENCY()
3750 // Check for single-block functions and skip them. in INITIALIZE_PASS_DEPENDENCY()
3761 BlockFrequency BlockFreq = MBFI->getBlockFreq(&MBB); in INITIALIZE_PASS_DEPENDENCY()
3772 BlockFreq * MBPI->getEdgeProbability(&MBB, Succ); in INITIALIZE_PASS_DEPENDENCY()