Lines Matching refs:Pred
476 bool isBestSuccessor(MachineBasicBlock *BB, MachineBasicBlock *Pred,
1162 for (MachineBasicBlock *Pred : Succ->predecessors()) {
1166 if (Pred == BB || (BlockFilter && !BlockFilter->count(Pred))
1167 || (BlockToChain[Pred] == &Chain && !Succ->succ_empty()))
1169 if (!TailDup.canTailDuplicate(Succ, Pred)) {
1170 if (Successors.size() > 1 && hasSameSuccessors(*Pred, Successors))
1323 for (MachineBasicBlock* Pred : PDom->predecessors()) {
1324 if (Pred == &BB)
1326 if (!TailDup.canTailDuplicate(PDom, Pred)) {
1393 * Prob(BB->Succ) > 2 * Prob(BB->Pred)
1395 * (1-T) * Prob(BB->Succ) > T * Prob(BB->Pred)
1431 // | Pred
1437 // With this layout, Pred BB
1439 // branch taken from BB to Pred, plus the cost of back taken branch
1440 // from Pred to Succ, as well as the additional cost associated
1441 // with the needed unconditional jump instruction from Pred To Succ.
1446 // 2 * freq(BB->Pred) * taken_branch_cost + unconditional_jump_cost
1449 // freq(BB->Succ) > 2 * freq(BB->Pred), i.e.,
1450 // prob(BB->Succ) > 2 * prob(BB->Pred)
1461 // BB Pred
1468 // prob(S->BB) > prob(S->Pred).
1469 // At this point, 2 blocks can be placed after BB: Pred or Succ. If we
1470 // choose Pred, we will have a topological ordering as shown on the left
1480 // | Pred-- | Succ--
1482 // ---Succ ---Pred--
1484 // cost = freq(S->Pred) + freq(BB->Succ) cost = 2 * freq (S->Pred)
1485 // = freq(S->Pred) + freq(S->BB)
1488 // cost (number of taken branches) with layout S->BB->Succ->Pred is 2 *
1489 // freq(S->Pred) while the cost of topo order is freq(S->Pred) + freq(S->BB).
1490 // We know Prob(S->BB) > Prob(S->Pred), so freq(S->BB) > freq(S->Pred), which
1504 // BB Pred
1514 // prob(S->BB) > prob(S->Pred). Assume that prob(BB->S1) >= prob(BB->S2).
1522 // | Pred----| | S1----
1524 // --(S1 or S2) ---Pred--
1528 // topo-cost = freq(S->Pred) + freq(BB->S1) + freq(BB->S2)
1529 // + min(freq(Pred->S1), freq(Pred->S2))
1531 // non-topo-cost = 2 * freq(S->Pred) + freq(BB->S2).
1532 // To be conservative, we can assume that min(freq(Pred->S1), freq(Pred->S2))
1534 // freq(S->Pred) < freq(BB->S1).
1536 // Note there are other shapes that apply (Pred may not be a single block,
1545 for (MachineBasicBlock *Pred : Succ->predecessors()) {
1546 BlockChain *PredChain = BlockToChain[Pred];
1547 if (Pred == Succ || PredChain == &SuccChain ||
1548 (BlockFilter && !BlockFilter->count(Pred)) ||
1549 PredChain == &Chain || Pred != *std::prev(PredChain->end()) ||
1553 (Pred == BB))
1558 // BB Pred
1563 // i.e. freq(BB->Succ) > freq(BB->Succ) * HotProb + freq(Pred->Succ) *
1565 // i.e. freq((BB->Succ) * (1 - HotProb) > freq(Pred->Succ) * HotProb
1569 MBFI->getBlockFreq(Pred) * MBPI->getEdgeProbability(Pred, Succ);
1832 for (MachineBasicBlock *Pred : ChainBB->predecessors()) {
1833 if (BlockFilter && !BlockFilter->count(Pred))
1835 if (BlockToChain[Pred] == &Chain)
1936 // ---Pred |
1940 // If BB is moved before OldTop, Pred needs a taken branch to BB, and it can't
1949 MachineBasicBlock *Pred = *BottomBlock->pred_begin();
1950 if (Pred->succ_size() != 2)
1953 MachineBasicBlock *OtherBB = *Pred->succ_begin();
1955 OtherBB = *Pred->succ_rbegin();
1968 for (MachineBasicBlock *Pred : Top->predecessors()) {
1969 BlockChain *PredChain = BlockToChain[Pred];
1970 if (!LoopBlockSet.count(Pred) &&
1971 (!PredChain || Pred == *std::prev(PredChain->end()))) {
1972 // Found a Pred block can be placed before Top.
1973 // Check if Top is the best successor of Pred.
1974 auto TopProb = MBPI->getEdgeProbability(Pred, Top);
1976 for (MachineBasicBlock *Succ : Pred->successors()) {
1977 auto SuccProb = MBPI->getEdgeProbability(Pred, Succ);
1979 // Check if Succ can be placed after Pred.
1988 BlockFrequency EdgeFreq = MBFI->getBlockFreq(Pred) *
1989 MBPI->getEdgeProbability(Pred, Top);
2012 // | Pred --->
2033 // Find the best Pred of NewTop.
2036 for (MachineBasicBlock *Pred : NewTop->predecessors()) {
2037 if (!LoopBlockSet.count(Pred))
2039 BlockChain *PredChain = BlockToChain[Pred];
2040 if (!PredChain || Pred == *std::prev(PredChain->end())) {
2042 MBFI->getBlockFreq(Pred) * MBPI->getEdgeProbability(Pred, NewTop);
2045 BestPred = Pred;
2050 // If NewTop is not placed after Pred, another successor can be placed
2051 // after Pred.
2071 // If NewTop is not the best successor of Pred, then Pred doesn't
2129 for (MachineBasicBlock *Pred : OldTop->predecessors()) {
2130 if (!LoopBlockSet.count(Pred))
2132 if (Pred == L.getHeader())
2134 LLVM_DEBUG(dbgs() << " old top pred: " << getBlockName(Pred) << ", has "
2135 << Pred->succ_size() << " successors, "
2136 << printBlockFreq(MBFI->getMBFI(), *Pred) << " freq\n");
2137 if (Pred->succ_size() > 2)
2141 if (Pred->succ_size() == 2) {
2142 OtherBB = *Pred->succ_begin();
2144 OtherBB = *Pred->succ_rbegin();
2147 if (!canMoveBottomBlockToTop(Pred, OldTop))
2150 BlockFrequency Gains = FallThroughGains(Pred, OldTop, OtherBB,
2154 ((Gains == BestGains) && Pred->isLayoutSuccessor(OldTop)))) {
2155 BestPred = Pred;
2331 /// 1. Look for a Pred that can be layout before Top.
2332 /// 2. Check if Top is the most possible successor of Pred.
2337 for (MachineBasicBlock *Pred : Top->predecessors()) {
2338 BlockChain *PredChain = BlockToChain[Pred];
2339 if (!LoopBlockSet.count(Pred) &&
2340 (!PredChain || Pred == *std::prev(PredChain->end()))) {
2341 // Found a Pred block can be placed before Top.
2342 // Check if Top is the best successor of Pred.
2343 auto TopProb = MBPI->getEdgeProbability(Pred, Top);
2345 for (MachineBasicBlock *Succ : Pred->successors()) {
2346 auto SuccProb = MBPI->getEdgeProbability(Pred, Succ);
2348 // Check if Succ can be placed after Pred.
2483 for (auto *Pred : ChainHeaderBB->predecessors()) {
2484 BlockChain *PredChain = BlockToChain[Pred];
2485 if (!LoopBlockSet.count(Pred) &&
2486 (!PredChain || Pred == *std::prev(PredChain->end()))) {
2487 auto EdgeFreq = MBFI->getBlockFreq(Pred) *
2488 MBPI->getEdgeProbability(Pred, ChainHeaderBB);
2492 if (Pred->succ_size() == 1)
3206 for (MachineBasicBlock *Pred : DuplicatedPreds) {
3208 BlockChain* PredChain = BlockToChain[Pred];
3209 if (Pred == LPred)
3211 if (Pred == LPred || (BlockFilter && !BlockFilter->count(Pred))
3214 for (MachineBasicBlock *NewSucc : Pred->successors()) {
3242 // Returns true if BB is Pred's best successor.
3244 MachineBasicBlock *Pred,
3246 if (BB == Pred)
3248 if (BlockFilter && !BlockFilter->count(Pred))
3250 BlockChain *PredChain = BlockToChain[Pred];
3251 if (PredChain && (Pred != *std::prev(PredChain->end())))
3256 for (MachineBasicBlock *Succ : Pred->successors())
3263 BranchProbability SuccProb = MBPI->getEdgeProbability(Pred, Succ);
3268 BranchProbability BBProb = MBPI->getEdgeProbability(Pred, BB);
3272 // Compute the number of reduced taken branches if Pred falls through to BB
3274 BlockFrequency PredFreq = getBlockCountOrFrequency(Pred);
3347 for (MachineBasicBlock *Pred : Preds) {
3348 BlockFrequency PredFreq = getBlockCountOrFrequency(Pred);
3350 if (!TailDup.canTailDuplicate(BB, Pred)) {
3351 // BB can't be duplicated into Pred, but it is possible to be layout
3352 // below Pred.
3353 if (!Fallthrough && isBestSuccessor(BB, Pred, BlockFilter)) {
3354 Fallthrough = Pred;
3376 Candidates.push_back(Pred);