20 /// loops and test whether they can be fused. The necessary conditions for
22 ///    1. The loops must be adjacent (there cannot be any statements between
23 ///       the two loops).
24 ///    2. The loops must be conforming (they must execute the same number of
26 ///    3. The loops must be control flow equivalent (if one loop executes, the
28 ///    4. There cannot be any negative distance dependencies between the loops.
29 /// If all of these conditions are satisfied, it is safe to fuse the loops.
42 /// conditions for fusion. Code transformations to make loops conform to each of
73 STATISTIC(FuseCounter, "Loops fused");
89 STATISTIC(NonAdjacent, "Loops are not adjacent");
280   /// This method is only valid for guarded loops.
282     assert(GuardBranch && "Only valid on guarded loops.");  in getNonLoopBlock()
317   /// does not check whether it is *legal* to fuse two loops together.
456 // loops by moving intervening code around. When this intervening code contains
457 // loops, those loops will be moved also. The corresponding FusionCandidates
494 /// Collect all loops in function at the same nest level, starting at the
497 /// This data structure collects all loops at the same nest level for a
542   /// Set of loops that have been removed from the function and are no longer
546   /// Depth of the current level, starting at 1 (outermost loops).
549   /// Vector of loops at the current depth level that have the same parent loop
588   /// specified function and collect candidate loops to fuse, starting at the
665   /// Iterate over all loops in the given loop set and identify the loops that
709   /// Determine if it is beneficial to fuse two loops.
752     LLVM_DEBUG(dbgs() << "The loops do not have the same tripcount, "  in haveIdenticalTripCounts()
755     // Currently only considering loops with a single exit point  in haveIdenticalTripCounts()
802              "Loops should have identical trip counts after peeling");  in peelFusionCandidate()
817       // in the case of unguarded loops, or the succesors of the exit block of  in peelFusionCandidate()
847                     "Both Loops have the same number of iterations now.\n");  in peelFusionCandidate()
870                "Should not have removed loops in CandidateSet!");  in fuseCandidates()
874                  "Should not have removed loops in CandidateSet!");  in fuseCandidates()
884           // the loops (second value of pair). The difference is not equal to  in fuseCandidates()
885           // std::nullopt iff the loops iterate a constant number of times, and  in fuseCandidates()
893           // both loops have different tripcounts.  in fuseCandidates()
968           // Check the dependencies across the loops and do not fuse if it would  in fuseCandidates()
984           // these loops  in fuseCandidates()
990             // pre-header, we cannot fuse these loops.  in fuseCandidates()
1022           // Peel the loop after determining that fusion is legal. The Loops  in fuseCandidates()
1030           // performFusion will change the original loops, making it not  in fuseCandidates()
1042           // Notify the loop-depth-tree that these loops are not valid objects  in fuseCandidates()
1146           // should take place, loops should not fuse  in canSinkInst()
1431   /// If the two candidates are guarded loops, then it checks whether the
1433   /// FC1. If not, then the loops are not adjacent. If the two candidates are
1434   /// not guarded loops, then it checks whether the exit block of \p FC0 is the
1438     // If the successor of the guard branch is FC1, then the loops are adjacent  in isAdjacent()
1495   /// NonLoopBlock). In other words, the first successor of both loops must
1501            "Expecting FC0 and FC1 to be guarded loops.");  in haveIdenticalGuards()
1545   /// This method contains the mechanics of fusing two loops, represented by \p
1567   /// preheader of \p FC0. This would allow loops with more than a single
1569   /// two loops could also be fused into a single block. This will require
1583     // Fusing guarded loops is handled slightly differently than non-guarded  in performFusion()
1584     // loops and has been broken out into a separate method instead of trying to  in performFusion()
1661     // Moves the phi nodes from the second to the first loops header block.  in performFusion()
1726     // Is there a way to keep SE up-to-date so we don't need to forget the loops  in performFusion()
1728     // Note: Need to forget the loops before merging the loop latches, as  in performFusion()
1738     // Merge the loops.  in performFusion()
1801   /// Fusing guarded loops is handled much the same way as fusing non-guarded
1802   /// loops. The rewiring of the CFG is slightly different though, because of
1803   /// the presence of the guards around the loops and the exit blocks after the
1816     assert(FC0.GuardBranch && FC1.GuardBranch && "Expecting guarded loops");  in fuseGuardedLoops()
1836     assert(FC0NonLoopBlock == FC1GuardBlock && "Loops are not adjacent");  in fuseGuardedLoops()
1891     // (because the loops are rotated. Thus, nothing will ever be added to  in fuseGuardedLoops()
1944     // Moves the phi nodes from the second to the first loops header block.  in fuseGuardedLoops()
2020     // Is there a way to keep SE up-to-date so we don't need to forget the loops  in fuseGuardedLoops()
2022     // Note: Need to forget the loops before merging the loop latches, as  in fuseGuardedLoops()
2032     // Merge the loops.  in fuseGuardedLoops()
2077   // Ensure loops are in simplifed form which is a pre-requisite for loop fusion  in run()