Lines Matching defs:FC0
394 // order. Thus, if FC0 comes *before* FC1 in a FusionCandidateSet, then FC0
395 // dominates FC1 and FC1 post-dominates FC0.
596 bool isControlFlowEquivalent(const FusionCandidate &FC0,
598 assert(FC0.Preheader && FC1.Preheader && "Expecting valid preheaders");
600 return ::isControlFlowEquivalent(*FC0.getEntryBlock(), *FC1.getEntryBlock(),
651 bool isBeneficialFusion(const FusionCandidate &FC0,
665 bool identicalTripCounts(const FusionCandidate &FC0,
667 const SCEV *TripCount0 = SE.getBackedgeTakenCount(FC0.L);
705 for (auto FC0 = CandidateSet.begin(); FC0 != CandidateSet.end(); ++FC0) {
706 assert(!LDT.isRemovedLoop(FC0->L) &&
708 auto FC1 = FC0;
713 LLVM_DEBUG(dbgs() << "Attempting to fuse candidate \n"; FC0->dump();
716 FC0->verify();
719 if (!identicalTripCounts(*FC0, *FC1)) {
722 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
727 if (!isAdjacent(*FC0, *FC1)) {
730 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1, NonAdjacent);
734 // Ensure that FC0 and FC1 have identical guards.
736 if (FC0->GuardBranch && FC1->GuardBranch &&
737 !haveIdenticalGuards(*FC0, *FC1)) {
740 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
746 *FC0->Preheader->getTerminator(), DT, &PDT,
750 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
755 if (FC0->GuardBranch) {
758 if (!isSafeToMoveBefore(*FC0->ExitBlock,
763 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
770 *FC0->GuardBranch->getParent()->getTerminator(), DT, &PDT,
775 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
783 if (!dependencesAllowFusion(*FC0, *FC1)) {
785 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
790 bool BeneficialToFuse = isBeneficialFusion(*FC0, *FC1);
795 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
803 LLVM_DEBUG(dbgs() << "\tFusion is performed: " << *FC0 << " and "
810 reportLoopFusion<OptimizationRemark>(*FC0, *FC1, FuseCounter);
812 FusionCandidate FusedCand(performFusion(*FC0, *FC1), &DT, &PDT, ORE);
820 CandidateSet.erase(FC0);
828 // Reset FC0 and FC1 the new (fused) candidate. Subsequent iterations
831 FC0 = FC1 = InsertPos.first;
936 bool dependencesAllowFusion(const FusionCandidate &FC0,
948 return accessDiffIsPositive(*FC0.L, *FC1.L, I0, I1, AnyDep);
973 return dependencesAllowFusion(FC0, FC1, I0, I1, AnyDep,
975 dependencesAllowFusion(FC0, FC1, I0, I1, AnyDep,
982 /// Perform a dependence check and return if @p FC0 and @p FC1 can be fused.
983 bool dependencesAllowFusion(const FusionCandidate &FC0,
985 LLVM_DEBUG(dbgs() << "Check if " << FC0 << " can be fused with " << FC1
987 assert(FC0.L->getLoopDepth() == FC1.L->getLoopDepth());
988 assert(DT.dominates(FC0.getEntryBlock(), FC1.getEntryBlock()));
990 for (Instruction *WriteL0 : FC0.MemWrites) {
992 if (!dependencesAllowFusion(FC0, FC1, *WriteL0, *WriteL1,
999 if (!dependencesAllowFusion(FC0, FC1, *WriteL0, *ReadL1,
1008 for (Instruction *WriteL0 : FC0.MemWrites)
1009 if (!dependencesAllowFusion(FC0, FC1, *WriteL0, *WriteL1,
1015 for (Instruction *ReadL0 : FC0.MemReads)
1016 if (!dependencesAllowFusion(FC0, FC1, *ReadL0, *WriteL1,
1025 // def is located in FC0 then it is is not safe to fuse.
1030 if (FC0.L->contains(Def->getParent())) {
1041 /// between the exit of \p FC0 and the entry of \p FC1.
1043 /// non-loop successor of the \p FC0 guard branch is the entry block of \p
1045 /// not guarded loops, then it checks whether the exit block of \p FC0 is the
1047 bool isAdjacent(const FusionCandidate &FC0,
1050 if (FC0.GuardBranch)
1051 return FC0.getNonLoopBlock() == FC1.getEntryBlock();
1053 return FC0.ExitBlock == FC1.getEntryBlock();
1068 bool haveIdenticalGuards(const FusionCandidate &FC0,
1070 assert(FC0.GuardBranch && FC1.GuardBranch &&
1071 "Expecting FC0 and FC1 to be guarded loops.");
1074 dyn_cast<Instruction>(FC0.GuardBranch->getCondition()))
1083 if (FC0.GuardBranch->getSuccessor(0) == FC0.Preheader)
1102 /// Move instructions from FC0.Latch to FC1.Latch. If FC0.Latch has an unique
1103 /// successor, then merge FC0.Latch with its unique successor.
1104 void mergeLatch(const FusionCandidate &FC0, const FusionCandidate &FC1) {
1105 moveInstructionsToTheBeginning(*FC0.Latch, *FC1.Latch, DT, PDT, DI);
1106 if (BasicBlock *Succ = FC0.Latch->getUniqueSuccessor()) {
1115 /// FC0 and \p FC1. It is assumed that \p FC0 dominates \p FC1 and \p FC1
1116 /// postdominates \p FC0 (making them control flow equivalent). It also
1127 /// 2. The latch of \p FC0 is modified to jump to the header of \p FC1.
1128 /// 3. The latch of \p FC1 i modified to jump to the header of \p FC0.
1129 /// 4. All blocks from \p FC1 are removed from FC1 and added to FC0.
1136 /// preheader of \p FC0. This would allow loops with more than a single
1141 Loop *performFusion(const FusionCandidate &FC0, const FusionCandidate &FC1) {
1142 assert(FC0.isValid() && FC1.isValid() &&
1145 LLVM_DEBUG(dbgs() << "Fusion Candidate 0: \n"; FC0.dump();
1149 // of FC0.
1150 moveInstructionsToTheEnd(*FC1.Preheader, *FC0.Preheader, DT, PDT, DI);
1155 if (FC0.GuardBranch)
1156 return fuseGuardedLoops(FC0, FC1);
1158 assert(FC1.Preheader == FC0.ExitBlock);
1162 // Remember the phi nodes originally in the header of FC0 in order to rewire
1172 if (FC0.ExitingBlock != FC0.Latch)
1173 for (PHINode &PHI : FC0.Header->phis())
1177 FC1.Preheader->replaceSuccessorsPhiUsesWith(FC0.Preheader);
1178 FC0.Latch->replaceSuccessorsPhiUsesWith(FC1.Latch);
1183 // The old exiting block of the first loop (FC0) has to jump to the header
1196 // KB: Would this sequence be simpler to just just make FC0.ExitingBlock go
1200 FC0.ExitingBlock->getTerminator()->replaceUsesOfWith(FC1.Preheader,
1203 DominatorTree::Delete, FC0.ExitingBlock, FC1.Preheader));
1205 DominatorTree::Insert, FC0.ExitingBlock, FC1.Header));
1219 PHI->moveBefore(&*FC0.Header->getFirstInsertionPt());
1238 L1HeaderPHI->addIncoming(LCV, FC0.Latch);
1240 FC0.ExitingBlock);
1246 FC0.Latch->getTerminator()->replaceUsesOfWith(FC0.Header, FC1.Header);
1247 FC1.Latch->getTerminator()->replaceUsesOfWith(FC1.Header, FC0.Header);
1249 // Change the condition of FC0 latch branch to true, as both successors of
1251 simplifyLatchBranch(FC0);
1253 // If FC0.Latch and FC0.ExitingBlock are the same then we have already
1255 if (FC0.Latch != FC0.ExitingBlock)
1257 DominatorTree::Insert, FC0.Latch, FC1.Header));
1260 FC0.Latch, FC0.Header));
1262 FC1.Latch, FC0.Header));
1278 SE.forgetLoop(FC0.L);
1280 // Move instructions from FC0.Latch to FC1.Latch.
1282 mergeLatch(FC0, FC1);
1288 FC0.L->addBlockEntry(BB);
1292 LI.changeLoopFor(BB, FC0.L);
1298 FC0.L->addChildLoop(ChildLoop);
1305 assert(!verifyFunction(*FC0.Header->getParent(), &errs()));
1314 return FC0.L;
1330 void reportLoopFusion(const FusionCandidate &FC0, const FusionCandidate &FC1,
1332 assert(FC0.Preheader && FC1.Preheader &&
1336 ORE.emit(RemarkKind(DEBUG_TYPE, Stat.getName(), FC0.L->getStartLoc(),
1337 FC0.Preheader)
1338 << "[" << FC0.Preheader->getParent()->getName()
1339 << "]: " << NV("Cand1", StringRef(FC0.Preheader->getName()))
1350 /// 1. Keep the guard branch from FC0 and use the non-loop block target
1352 /// 2. Remove the exit block from FC0 (this exit block should be empty
1356 /// The exit block successor for the latch of FC0 is updated to be the header
1358 /// be the header of FC0, thus creating the fused loop.
1359 Loop *fuseGuardedLoops(const FusionCandidate &FC0,
1361 assert(FC0.GuardBranch && FC1.GuardBranch && "Expecting guarded loops");
1363 BasicBlock *FC0GuardBlock = FC0.GuardBranch->getParent();
1365 BasicBlock *FC0NonLoopBlock = FC0.getNonLoopBlock();
1368 // Move instructions from the exit block of FC0 to the beginning of the exit
1370 moveInstructionsToTheBeginning(*FC0.ExitBlock, *FC1.ExitBlock, DT, PDT, DI);
1373 // block of FC0.
1383 // The guard for FC0 is updated to guard both FC0 and FC1. This is done by
1384 // changing the NonLoopGuardBlock for FC0 to the NonLoopGuardBlock for FC1.
1385 // Thus, one path from the guard goes to the preheader for FC0 (and thus
1389 FC0.GuardBranch->replaceUsesOfWith(FC0NonLoopBlock, FC1NonLoopBlock);
1390 FC0.ExitBlock->getTerminator()->replaceUsesOfWith(FC1GuardBlock,
1411 // Remember the phi nodes originally in the header of FC0 in order to rewire
1420 // KB: This is no longer necessary because FC0.ExitingBlock == FC0.Latch
1424 if (FC0.ExitingBlock != FC0.Latch)
1425 for (PHINode &PHI : FC0.Header->phis())
1431 FC1.Preheader->replaceSuccessorsPhiUsesWith(FC0.Preheader);
1432 FC0.Latch->replaceSuccessorsPhiUsesWith(FC1.Latch);
1434 // The old exiting block of the first loop (FC0) has to jump to the header
1447 FC0.ExitingBlock->getTerminator()->replaceUsesOfWith(FC0.ExitBlock,
1451 DominatorTree::Delete, FC0.ExitingBlock, FC0.ExitBlock));
1453 DominatorTree::Insert, FC0.ExitingBlock, FC1.Header));
1455 // Remove FC0 Exit Block
1456 // The exit block for FC0 is no longer needed since control will flow
1460 // instructions from FC0 exit block into FC1 exit block prior to removing
1462 assert(pred_begin(FC0.ExitBlock) == pred_end(FC0.ExitBlock) &&
1464 FC0.ExitBlock->getTerminator()->eraseFromParent();
1465 new UnreachableInst(FC0.ExitBlock->getContext(), FC0.ExitBlock);
1480 PHI->moveBefore(&*FC0.Header->getFirstInsertionPt());
1499 L1HeaderPHI->addIncoming(LCV, FC0.Latch);
1501 FC0.ExitingBlock);
1509 FC0.Latch->getTerminator()->replaceUsesOfWith(FC0.Header, FC1.Header);
1510 FC1.Latch->getTerminator()->replaceUsesOfWith(FC1.Header, FC0.Header);
1512 // Change the condition of FC0 latch branch to true, as both successors of
1514 simplifyLatchBranch(FC0);
1516 // If FC0.Latch and FC0.ExitingBlock are the same then we have already
1518 if (FC0.Latch != FC0.ExitingBlock)
1520 DominatorTree::Insert, FC0.Latch, FC1.Header));
1523 FC0.Latch, FC0.Header));
1525 FC1.Latch, FC0.Header));
1542 LI.removeBlock(FC0.ExitBlock);
1545 DTU.deleteBB(FC0.ExitBlock);
1553 SE.forgetLoop(FC0.L);
1555 // Move instructions from FC0.Latch to FC1.Latch.
1557 mergeLatch(FC0, FC1);
1563 FC0.L->addBlockEntry(BB);
1567 LI.changeLoopFor(BB, FC0.L);
1573 FC0.L->addChildLoop(ChildLoop);
1580 assert(!verifyFunction(*FC0.Header->getParent(), &errs()));
1589 return FC0.L;