Lines Matching defs:FC1
452 // order. Thus, if FC0 comes *before* FC1 in a FusionCandidateSet, then FC0
453 // dominates FC1 and FC1 post-dominates FC0.
658 const FusionCandidate &FC1) const {
659 assert(FC0.Preheader && FC1.Preheader && "Expecting valid preheaders");
661 return ::isControlFlowEquivalent(*FC0.getEntryBlock(), *FC1.getEntryBlock(),
715 const FusionCandidate &FC1) {
729 const FusionCandidate &FC1) const {
737 const SCEV *TripCount1 = SE.getBackedgeTakenCount(FC1.L);
758 const unsigned TC1 = SE.getSmallConstantTripCount(FC1.L);
776 dbgs() << "Difference is less than 0. FC1 (second loop) has more "
786 void peelFusionCandidate(FusionCandidate &FC0, const FusionCandidate &FC1,
799 auto IdenticalTripCount = haveIdenticalTripCounts(FC0, FC1);
821 FC0.GuardBranch ? FC0.ExitBlock->getUniqueSuccessor() : FC1.Preheader;
871 auto FC1 = FC0;
872 for (++FC1; FC1 != CandidateSet.end(); ++FC1) {
873 assert(!LDT.isRemovedLoop(FC1->L) &&
877 dbgs() << " with\n"; FC1->dump(); dbgs() << "\n");
880 FC1->verify();
888 haveIdenticalTripCounts(*FC0, *FC1);
910 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
915 if (!isAdjacent(*FC0, *FC1)) {
918 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1, NonAdjacent);
922 if ((!FC0->GuardBranch && FC1->GuardBranch) ||
923 (FC0->GuardBranch && !FC1->GuardBranch)) {
927 *FC0, *FC1, OnlySecondCandidateIsGuarded);
931 // Ensure that FC0 and FC1 have identical guards.
933 if (FC0->GuardBranch && FC1->GuardBranch &&
934 !haveIdenticalGuards(*FC0, *FC1) && !TCDifference) {
937 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
943 assert(FC1->GuardBranch && "Expecting valid FC1 guard branch");
946 *FC1->ExitBlock->getFirstNonPHIOrDbg(), DT,
950 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
956 *FC1->GuardBranch->getParent(),
962 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
970 if (!dependencesAllowFusion(*FC0, *FC1)) {
972 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
985 if (!isEmptyPreheader(*FC1)) {
991 if (!collectMovablePreheaderInsts(*FC0, *FC1, SafeToHoist,
996 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
1002 bool BeneficialToFuse = isBeneficialFusion(*FC0, *FC1);
1007 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
1016 movePreheaderInsts(*FC0, *FC1, SafeToHoist, SafeToSink);
1019 << *FC1 << "\n");
1026 peelFusionCandidate(FC0Copy, *FC1, *TCDifference);
1032 reportLoopFusion<OptimizationRemark>((Peel ? FC0Copy : *FC0), *FC1,
1036 performFusion((Peel ? FC0Copy : *FC0), *FC1), DT, &PDT, ORE,
1043 LDT.removeLoop(FC1->L);
1046 CandidateSet.erase(FC1);
1053 // Reset FC0 and FC1 the new (fused) candidate. Subsequent iterations
1054 // of the FC1 loop will attempt to fuse the new (fused) loop with the
1056 FC0 = FC1 = InsertPos.first;
1092 // PHIs in FC1's header only have FC0 blocks as predecessors. PHIs
1107 LLVM_DEBUG(dbgs() << "Inst depends on an instruction in FC1's "
1137 // block of \p FC1.
1139 bool canSinkInst(Instruction &I, const FusionCandidate &FC1) const {
1143 // If FC1 has phi users of this value, we cannot sink it into FC1.
1144 if (FC1.L->contains(UI)) {
1156 for (Instruction *ReadInst : FC1.MemReads) {
1160 LLVM_DEBUG(dbgs() << "Inst depends on a read instruction in FC1.\n");
1166 for (Instruction *WriteInst : FC1.MemWrites) {
1170 LLVM_DEBUG(dbgs() << "Inst depends on a write instruction in FC1.\n");
1179 /// Collect instructions in the \p FC1 Preheader that can be hoisted
1180 /// to the \p FC0 Preheader or sunk into the \p FC1 Body
1182 const FusionCandidate &FC0, const FusionCandidate &FC1,
1185 BasicBlock *FC1Preheader = FC1.Preheader;
1218 if (canSinkInst(I, FC1)) {
1326 const FusionCandidate &FC1, Instruction &I0,
1337 return accessDiffIsPositive(*FC0.L, *FC1.L, I0, I1, AnyDep);
1362 return dependencesAllowFusion(FC0, FC1, I0, I1, AnyDep,
1364 dependencesAllowFusion(FC0, FC1, I0, I1, AnyDep,
1371 /// Perform a dependence check and return if @p FC0 and @p FC1 can be fused.
1373 const FusionCandidate &FC1) {
1374 LLVM_DEBUG(dbgs() << "Check if " << FC0 << " can be fused with " << FC1
1376 assert(FC0.L->getLoopDepth() == FC1.L->getLoopDepth());
1377 assert(DT.dominates(FC0.getEntryBlock(), FC1.getEntryBlock()));
1380 for (Instruction *WriteL1 : FC1.MemWrites)
1381 if (!dependencesAllowFusion(FC0, FC1, *WriteL0, *WriteL1,
1387 for (Instruction *ReadL1 : FC1.MemReads)
1388 if (!dependencesAllowFusion(FC0, FC1, *WriteL0, *ReadL1,
1396 for (Instruction *WriteL1 : FC1.MemWrites) {
1398 if (!dependencesAllowFusion(FC0, FC1, *WriteL0, *WriteL1,
1405 if (!dependencesAllowFusion(FC0, FC1, *ReadL0, *WriteL1,
1413 // Walk through all uses in FC1. For each use, find the reaching def. If the
1415 for (BasicBlock *BB : FC1.L->blocks())
1430 /// between the exit of \p FC0 and the entry of \p FC1.
1433 /// FC1. If not, then the loops are not adjacent. If the two candidates are
1435 /// preheader of \p FC1.
1437 const FusionCandidate &FC1) const {
1438 // If the successor of the guard branch is FC1, then the loops are adjacent
1440 return FC0.getNonLoopBlock() == FC1.getEntryBlock();
1442 return FC0.ExitBlock == FC1.getEntryBlock();
1449 /// Hoist \p FC1 Preheader instructions to \p FC0 Preheader
1450 /// and sink others into the body of \p FC1.
1452 const FusionCandidate &FC1,
1456 assert(HoistInsts.size() + SinkInsts.size() == FC1.Preheader->size() - 1 &&
1475 assert(I->getParent() == FC1.Preheader);
1481 assert(I->getParent() == FC1.Preheader);
1482 I->moveBefore(*FC1.ExitBlock, FC1.ExitBlock->getFirstInsertionPt());
1499 const FusionCandidate &FC1) const {
1500 assert(FC0.GuardBranch && FC1.GuardBranch &&
1501 "Expecting FC0 and FC1 to be guarded loops.");
1506 dyn_cast<Instruction>(FC1.GuardBranch->getCondition()))
1514 return (FC1.GuardBranch->getSuccessor(0) == FC1.Preheader);
1516 return (FC1.GuardBranch->getSuccessor(1) == FC1.Preheader);
1533 /// Move instructions from FC0.Latch to FC1.Latch. If FC0.Latch has an unique
1535 void mergeLatch(const FusionCandidate &FC0, const FusionCandidate &FC1) {
1536 moveInstructionsToTheBeginning(*FC0.Latch, *FC1.Latch, DT, PDT, DI);
1546 /// FC0 and \p FC1. It is assumed that \p FC0 dominates \p FC1 and \p FC1
1556 /// 1. The preheader of \p FC1 is removed as it is no longer necessary
1558 /// 2. The latch of \p FC0 is modified to jump to the header of \p FC1.
1559 /// 3. The latch of \p FC1 i modified to jump to the header of \p FC0.
1560 /// 4. All blocks from \p FC1 are removed from FC1 and added to FC0.
1566 /// fusion. For example, the preheader of \p FC1 can be merged with the
1572 Loop *performFusion(const FusionCandidate &FC0, const FusionCandidate &FC1) {
1573 assert(FC0.isValid() && FC1.isValid() &&
1577 dbgs() << "Fusion Candidate 1: \n"; FC1.dump(););
1579 // Move instructions from the preheader of FC1 to the end of the preheader
1581 moveInstructionsToTheEnd(*FC1.Preheader, *FC0.Preheader, DT, PDT, DI);
1587 return fuseGuardedLoops(FC0, FC1);
1589 assert(FC1.Preheader ==
1591 assert(FC1.Preheader->size() == 1 &&
1592 FC1.Preheader->getSingleSuccessor() == FC1.Header);
1609 FC1.Preheader->replaceSuccessorsPhiUsesWith(FC0.Preheader);
1610 FC0.Latch->replaceSuccessorsPhiUsesWith(FC1.Latch);
1629 // to FC1.Header? I think this is basically what the three sequences are
1633 FC0.ExitingBlock->getTerminator()->replaceUsesOfWith(FC1.Preheader,
1634 FC1.Header);
1636 DominatorTree::Delete, FC0.ExitingBlock, FC1.Preheader));
1638 DominatorTree::Insert, FC0.ExitingBlock, FC1.Header));
1641 DominatorTree::Delete, FC0.ExitBlock, FC1.Preheader));
1645 FC1.Header);
1650 DominatorTree::Insert, FC0.ExitingBlock, FC1.Header));
1655 assert(pred_empty(FC1.Preheader));
1656 FC1.Preheader->getTerminator()->eraseFromParent();
1657 new UnreachableInst(FC1.Preheader->getContext(), FC1.Preheader);
1659 DominatorTree::Delete, FC1.Preheader, FC1.Header));
1662 while (PHINode *PHI = dyn_cast<PHINode>(&FC1.Header->front())) {
1675 BasicBlock::iterator L1HeaderIP = FC1.Header->begin();
1677 int L1LatchBBIdx = LCPHI->getBasicBlockIndex(FC1.Latch);
1694 FC0.Latch->getTerminator()->replaceUsesOfWith(FC0.Header, FC1.Header);
1695 FC1.Latch->getTerminator()->replaceUsesOfWith(FC1.Header, FC0.Header);
1705 DominatorTree::Insert, FC0.Latch, FC1.Header));
1710 FC1.Latch, FC0.Header));
1712 FC1.Latch, FC1.Header));
1717 LI.removeBlock(FC1.Preheader);
1718 DTU.deleteBB(FC1.Preheader);
1729 // mergeLatch may remove the only block in FC1.
1730 SE.forgetLoop(FC1.L);
1734 // Move instructions from FC0.Latch to FC1.Latch.
1736 mergeLatch(FC0, FC1);
1739 SmallVector<BasicBlock *, 8> Blocks(FC1.L->blocks());
1742 FC1.L->removeBlockFromLoop(BB);
1743 if (LI.getLoopFor(BB) != FC1.L)
1747 while (!FC1.L->isInnermost()) {
1748 const auto &ChildLoopIt = FC1.L->begin();
1750 FC1.L->removeChildLoop(ChildLoopIt);
1755 LI.erase(FC1.L);
1783 void reportLoopFusion(const FusionCandidate &FC0, const FusionCandidate &FC1,
1785 assert(FC0.Preheader && FC1.Preheader &&
1794 << " and " << NV("Cand2", StringRef(FC1.Preheader->getName()))
1806 /// from the FC1 guard branch.
1809 /// 3. Remove the guard branch for FC1
1810 /// 4. Remove the preheader for FC1.
1812 /// of FC1 and the non-exit block successor of the latch of FC1 is updated to
1815 const FusionCandidate &FC1) {
1816 assert(FC0.GuardBranch && FC1.GuardBranch && "Expecting guarded loops");
1819 BasicBlock *FC1GuardBlock = FC1.GuardBranch->getParent();
1821 BasicBlock *FC1NonLoopBlock = FC1.getNonLoopBlock();
1825 // block of FC1, in the case that the FC0 loop has not been peeled. In the
1827 // of the FC0 Exit block to the beginning of the exit block of FC1.
1829 (FC0.Peeled ? *FC0ExitBlockSuccessor : *FC0.ExitBlock), *FC1.ExitBlock,
1832 // Move instructions from the guard block of FC1 to the end of the guard
1843 // The guard for FC0 is updated to guard both FC0 and FC1. This is done by
1844 // changing the NonLoopGuardBlock for FC0 to the NonLoopGuardBlock for FC1.
1847 // for FC1 (where FC1 guard would have gone if FC1 was not executed).
1852 BBToUpdate->getTerminator()->replaceUsesOfWith(FC1GuardBlock, FC1.Header);
1854 // The guard of FC1 is not necessary anymore.
1855 FC1.GuardBranch->eraseFromParent();
1859 DominatorTree::Delete, FC1GuardBlock, FC1.Preheader));
1901 FC1.Preheader->replaceSuccessorsPhiUsesWith(FC0.Preheader);
1902 FC0.Latch->replaceSuccessorsPhiUsesWith(FC1.Latch);
1918 FC1.Header);
1923 DominatorTree::Insert, FC0.ExitingBlock, FC1.Header));
1927 // directly to the header of FC1. Since it is an empty block, it can be
1930 // instructions from FC0 exit block into FC1 exit block prior to removing
1936 // Remove FC1 Preheader
1938 assert(pred_empty(FC1.Preheader));
1939 FC1.Preheader->getTerminator()->eraseFromParent();
1940 new UnreachableInst(FC1.Preheader->getContext(), FC1.Preheader);
1942 DominatorTree::Delete, FC1.Preheader, FC1.Header));
1945 while (PHINode *PHI = dyn_cast<PHINode>(&FC1.Header->front())) {
1958 BasicBlock::iterator L1HeaderIP = FC1.Header->begin();
1960 int L1LatchBBIdx = LCPHI->getBasicBlockIndex(FC1.Latch);
1979 FC0.Latch->getTerminator()->replaceUsesOfWith(FC0.Header, FC1.Header);
1980 FC1.Latch->getTerminator()->replaceUsesOfWith(FC1.Header, FC0.Header);
1990 DominatorTree::Insert, FC0.Latch, FC1.Header));
1995 FC1.Latch, FC0.Header));
1997 FC1.Latch, FC1.Header));
2009 LI.removeBlock(FC1.Preheader);
2016 DTU.deleteBB(FC1.Preheader);
2023 // mergeLatch may remove the only block in FC1.
2024 SE.forgetLoop(FC1.L);
2028 // Move instructions from FC0.Latch to FC1.Latch.
2030 mergeLatch(FC0, FC1);
2033 SmallVector<BasicBlock *, 8> Blocks(FC1.L->blocks());
2036 FC1.L->removeBlockFromLoop(BB);
2037 if (LI.getLoopFor(BB) != FC1.L)
2041 while (!FC1.L->isInnermost()) {
2042 const auto &ChildLoopIt = FC1.L->begin();
2044 FC1.L->removeChildLoop(ChildLoopIt);
2049 LI.erase(FC1.L);