Lines Matching defs:FC1
451 // order. Thus, if FC0 comes *before* FC1 in a FusionCandidateSet, then FC0
452 // dominates FC1 and FC1 post-dominates FC0.
657 const FusionCandidate &FC1) const {
658 assert(FC0.Preheader && FC1.Preheader && "Expecting valid preheaders");
660 return ::isControlFlowEquivalent(*FC0.getEntryBlock(), *FC1.getEntryBlock(),
714 const FusionCandidate &FC1) {
728 const FusionCandidate &FC1) const {
736 const SCEV *TripCount1 = SE.getBackedgeTakenCount(FC1.L);
757 const unsigned TC1 = SE.getSmallConstantTripCount(FC1.L);
775 dbgs() << "Difference is less than 0. FC1 (second loop) has more "
785 void peelFusionCandidate(FusionCandidate &FC0, const FusionCandidate &FC1,
798 auto IdenticalTripCount = haveIdenticalTripCounts(FC0, FC1);
820 FC0.GuardBranch ? FC0.ExitBlock->getUniqueSuccessor() : FC1.Preheader;
870 auto FC1 = FC0;
871 for (++FC1; FC1 != CandidateSet.end(); ++FC1) {
872 assert(!LDT.isRemovedLoop(FC1->L) &&
876 dbgs() << " with\n"; FC1->dump(); dbgs() << "\n");
879 FC1->verify();
887 haveIdenticalTripCounts(*FC0, *FC1);
909 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
914 if (!isAdjacent(*FC0, *FC1)) {
917 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1, NonAdjacent);
921 if ((!FC0->GuardBranch && FC1->GuardBranch) ||
922 (FC0->GuardBranch && !FC1->GuardBranch)) {
926 *FC0, *FC1, OnlySecondCandidateIsGuarded);
930 // Ensure that FC0 and FC1 have identical guards.
932 if (FC0->GuardBranch && FC1->GuardBranch &&
933 !haveIdenticalGuards(*FC0, *FC1) && !TCDifference) {
936 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
942 assert(FC1->GuardBranch && "Expecting valid FC1 guard branch");
945 *FC1->ExitBlock->getFirstNonPHIOrDbg(), DT,
949 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
955 *FC1->GuardBranch->getParent(),
961 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
969 if (!dependencesAllowFusion(*FC0, *FC1)) {
971 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
984 if (!isEmptyPreheader(*FC1)) {
990 if (!collectMovablePreheaderInsts(*FC0, *FC1, SafeToHoist,
995 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
1001 bool BeneficialToFuse = isBeneficialFusion(*FC0, *FC1);
1006 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
1015 movePreheaderInsts(*FC0, *FC1, SafeToHoist, SafeToSink);
1018 << *FC1 << "\n");
1025 peelFusionCandidate(FC0Copy, *FC1, *TCDifference);
1031 reportLoopFusion<OptimizationRemark>((Peel ? FC0Copy : *FC0), *FC1,
1035 performFusion((Peel ? FC0Copy : *FC0), *FC1), DT, &PDT, ORE,
1042 LDT.removeLoop(FC1->L);
1045 CandidateSet.erase(FC1);
1052 // Reset FC0 and FC1 the new (fused) candidate. Subsequent iterations
1053 // of the FC1 loop will attempt to fuse the new (fused) loop with the
1055 FC0 = FC1 = InsertPos.first;
1091 // PHIs in FC1's header only have FC0 blocks as predecessors. PHIs
1106 LLVM_DEBUG(dbgs() << "Inst depends on an instruction in FC1's "
1136 // block of \p FC1.
1138 bool canSinkInst(Instruction &I, const FusionCandidate &FC1) const {
1142 // If FC1 has phi users of this value, we cannot sink it into FC1.
1143 if (FC1.L->contains(UI)) {
1155 for (Instruction *ReadInst : FC1.MemReads) {
1159 LLVM_DEBUG(dbgs() << "Inst depends on a read instruction in FC1.\n");
1165 for (Instruction *WriteInst : FC1.MemWrites) {
1169 LLVM_DEBUG(dbgs() << "Inst depends on a write instruction in FC1.\n");
1178 /// Collect instructions in the \p FC1 Preheader that can be hoisted
1179 /// to the \p FC0 Preheader or sunk into the \p FC1 Body
1181 const FusionCandidate &FC0, const FusionCandidate &FC1,
1184 BasicBlock *FC1Preheader = FC1.Preheader;
1217 if (canSinkInst(I, FC1)) {
1325 const FusionCandidate &FC1, Instruction &I0,
1336 return accessDiffIsPositive(*FC0.L, *FC1.L, I0, I1, AnyDep);
1361 return dependencesAllowFusion(FC0, FC1, I0, I1, AnyDep,
1363 dependencesAllowFusion(FC0, FC1, I0, I1, AnyDep,
1370 /// Perform a dependence check and return if @p FC0 and @p FC1 can be fused.
1372 const FusionCandidate &FC1) {
1373 LLVM_DEBUG(dbgs() << "Check if " << FC0 << " can be fused with " << FC1
1375 assert(FC0.L->getLoopDepth() == FC1.L->getLoopDepth());
1376 assert(DT.dominates(FC0.getEntryBlock(), FC1.getEntryBlock()));
1379 for (Instruction *WriteL1 : FC1.MemWrites)
1380 if (!dependencesAllowFusion(FC0, FC1, *WriteL0, *WriteL1,
1386 for (Instruction *ReadL1 : FC1.MemReads)
1387 if (!dependencesAllowFusion(FC0, FC1, *WriteL0, *ReadL1,
1395 for (Instruction *WriteL1 : FC1.MemWrites) {
1397 if (!dependencesAllowFusion(FC0, FC1, *WriteL0, *WriteL1,
1404 if (!dependencesAllowFusion(FC0, FC1, *ReadL0, *WriteL1,
1412 // Walk through all uses in FC1. For each use, find the reaching def. If the
1414 for (BasicBlock *BB : FC1.L->blocks())
1429 /// between the exit of \p FC0 and the entry of \p FC1.
1432 /// FC1. If not, then the loops are not adjacent. If the two candidates are
1434 /// preheader of \p FC1.
1436 const FusionCandidate &FC1) const {
1437 // If the successor of the guard branch is FC1, then the loops are adjacent
1439 return FC0.getNonLoopBlock() == FC1.getEntryBlock();
1441 return FC0.ExitBlock == FC1.getEntryBlock();
1448 /// Hoist \p FC1 Preheader instructions to \p FC0 Preheader
1449 /// and sink others into the body of \p FC1.
1451 const FusionCandidate &FC1,
1455 assert(HoistInsts.size() + SinkInsts.size() == FC1.Preheader->size() - 1 &&
1474 assert(I->getParent() == FC1.Preheader);
1480 assert(I->getParent() == FC1.Preheader);
1481 I->moveBefore(*FC1.ExitBlock, FC1.ExitBlock->getFirstInsertionPt());
1498 const FusionCandidate &FC1) const {
1499 assert(FC0.GuardBranch && FC1.GuardBranch &&
1500 "Expecting FC0 and FC1 to be guarded loops.");
1505 dyn_cast<Instruction>(FC1.GuardBranch->getCondition()))
1513 return (FC1.GuardBranch->getSuccessor(0) == FC1.Preheader);
1515 return (FC1.GuardBranch->getSuccessor(1) == FC1.Preheader);
1532 /// Move instructions from FC0.Latch to FC1.Latch. If FC0.Latch has an unique
1534 void mergeLatch(const FusionCandidate &FC0, const FusionCandidate &FC1) {
1535 moveInstructionsToTheBeginning(*FC0.Latch, *FC1.Latch, DT, PDT, DI);
1545 /// FC0 and \p FC1. It is assumed that \p FC0 dominates \p FC1 and \p FC1
1555 /// 1. The preheader of \p FC1 is removed as it is no longer necessary
1557 /// 2. The latch of \p FC0 is modified to jump to the header of \p FC1.
1558 /// 3. The latch of \p FC1 i modified to jump to the header of \p FC0.
1559 /// 4. All blocks from \p FC1 are removed from FC1 and added to FC0.
1565 /// fusion. For example, the preheader of \p FC1 can be merged with the
1571 Loop *performFusion(const FusionCandidate &FC0, const FusionCandidate &FC1) {
1572 assert(FC0.isValid() && FC1.isValid() &&
1576 dbgs() << "Fusion Candidate 1: \n"; FC1.dump(););
1578 // Move instructions from the preheader of FC1 to the end of the preheader
1580 moveInstructionsToTheEnd(*FC1.Preheader, *FC0.Preheader, DT, PDT, DI);
1586 return fuseGuardedLoops(FC0, FC1);
1588 assert(FC1.Preheader ==
1590 assert(FC1.Preheader->size() == 1 &&
1591 FC1.Preheader->getSingleSuccessor() == FC1.Header);
1608 FC1.Preheader->replaceSuccessorsPhiUsesWith(FC0.Preheader);
1609 FC0.Latch->replaceSuccessorsPhiUsesWith(FC1.Latch);
1628 // to FC1.Header? I think this is basically what the three sequences are
1632 FC0.ExitingBlock->getTerminator()->replaceUsesOfWith(FC1.Preheader,
1633 FC1.Header);
1635 DominatorTree::Delete, FC0.ExitingBlock, FC1.Preheader));
1637 DominatorTree::Insert, FC0.ExitingBlock, FC1.Header));
1640 DominatorTree::Delete, FC0.ExitBlock, FC1.Preheader));
1644 FC1.Header);
1649 DominatorTree::Insert, FC0.ExitingBlock, FC1.Header));
1654 assert(pred_empty(FC1.Preheader));
1655 FC1.Preheader->getTerminator()->eraseFromParent();
1656 new UnreachableInst(FC1.Preheader->getContext(), FC1.Preheader);
1658 DominatorTree::Delete, FC1.Preheader, FC1.Header));
1661 while (PHINode *PHI = dyn_cast<PHINode>(&FC1.Header->front())) {
1674 BasicBlock::iterator L1HeaderIP = FC1.Header->begin();
1676 int L1LatchBBIdx = LCPHI->getBasicBlockIndex(FC1.Latch);
1693 FC0.Latch->getTerminator()->replaceUsesOfWith(FC0.Header, FC1.Header);
1694 FC1.Latch->getTerminator()->replaceUsesOfWith(FC1.Header, FC0.Header);
1704 DominatorTree::Insert, FC0.Latch, FC1.Header));
1709 FC1.Latch, FC0.Header));
1711 FC1.Latch, FC1.Header));
1716 LI.removeBlock(FC1.Preheader);
1717 DTU.deleteBB(FC1.Preheader);
1728 // mergeLatch may remove the only block in FC1.
1729 SE.forgetLoop(FC1.L);
1735 // Move instructions from FC0.Latch to FC1.Latch.
1737 mergeLatch(FC0, FC1);
1740 SmallVector<BasicBlock *, 8> Blocks(FC1.L->blocks());
1743 FC1.L->removeBlockFromLoop(BB);
1744 if (LI.getLoopFor(BB) != FC1.L)
1748 while (!FC1.L->isInnermost()) {
1749 const auto &ChildLoopIt = FC1.L->begin();
1751 FC1.L->removeChildLoop(ChildLoopIt);
1756 LI.erase(FC1.L);
1784 void reportLoopFusion(const FusionCandidate &FC0, const FusionCandidate &FC1,
1786 assert(FC0.Preheader && FC1.Preheader &&
1795 << " and " << NV("Cand2", StringRef(FC1.Preheader->getName()))
1807 /// from the FC1 guard branch.
1810 /// 3. Remove the guard branch for FC1
1811 /// 4. Remove the preheader for FC1.
1813 /// of FC1 and the non-exit block successor of the latch of FC1 is updated to
1816 const FusionCandidate &FC1) {
1817 assert(FC0.GuardBranch && FC1.GuardBranch && "Expecting guarded loops");
1820 BasicBlock *FC1GuardBlock = FC1.GuardBranch->getParent();
1822 BasicBlock *FC1NonLoopBlock = FC1.getNonLoopBlock();
1826 // block of FC1, in the case that the FC0 loop has not been peeled. In the
1828 // of the FC0 Exit block to the beginning of the exit block of FC1.
1830 (FC0.Peeled ? *FC0ExitBlockSuccessor : *FC0.ExitBlock), *FC1.ExitBlock,
1833 // Move instructions from the guard block of FC1 to the end of the guard
1844 // The guard for FC0 is updated to guard both FC0 and FC1. This is done by
1845 // changing the NonLoopGuardBlock for FC0 to the NonLoopGuardBlock for FC1.
1848 // for FC1 (where FC1 guard would have gone if FC1 was not executed).
1853 BBToUpdate->getTerminator()->replaceUsesOfWith(FC1GuardBlock, FC1.Header);
1855 // The guard of FC1 is not necessary anymore.
1856 FC1.GuardBranch->eraseFromParent();
1860 DominatorTree::Delete, FC1GuardBlock, FC1.Preheader));
1902 FC1.Preheader->replaceSuccessorsPhiUsesWith(FC0.Preheader);
1903 FC0.Latch->replaceSuccessorsPhiUsesWith(FC1.Latch);
1919 FC1.Header);
1924 DominatorTree::Insert, FC0.ExitingBlock, FC1.Header));
1928 // directly to the header of FC1. Since it is an empty block, it can be
1931 // instructions from FC0 exit block into FC1 exit block prior to removing
1937 // Remove FC1 Preheader
1939 assert(pred_empty(FC1.Preheader));
1940 FC1.Preheader->getTerminator()->eraseFromParent();
1941 new UnreachableInst(FC1.Preheader->getContext(), FC1.Preheader);
1943 DominatorTree::Delete, FC1.Preheader, FC1.Header));
1946 while (PHINode *PHI = dyn_cast<PHINode>(&FC1.Header->front())) {
1959 BasicBlock::iterator L1HeaderIP = FC1.Header->begin();
1961 int L1LatchBBIdx = LCPHI->getBasicBlockIndex(FC1.Latch);
1980 FC0.Latch->getTerminator()->replaceUsesOfWith(FC0.Header, FC1.Header);
1981 FC1.Latch->getTerminator()->replaceUsesOfWith(FC1.Header, FC0.Header);
1991 DominatorTree::Insert, FC0.Latch, FC1.Header));
1996 FC1.Latch, FC0.Header));
1998 FC1.Latch, FC1.Header));
2010 LI.removeBlock(FC1.Preheader);
2017 DTU.deleteBB(FC1.Preheader);
2024 // mergeLatch may remove the only block in FC1.
2025 SE.forgetLoop(FC1.L);
2031 // Move instructions from FC0.Latch to FC1.Latch.
2033 mergeLatch(FC0, FC1);
2036 SmallVector<BasicBlock *, 8> Blocks(FC1.L->blocks());
2039 FC1.L->removeBlockFromLoop(BB);
2040 if (LI.getLoopFor(BB) != FC1.L)
2044 while (!FC1.L->isInnermost()) {
2045 const auto &ChildLoopIt = FC1.L->begin();
2047 FC1.L->removeChildLoop(ChildLoopIt);
2052 LI.erase(FC1.L);