1 //===- LoopFuse.cpp - Loop Fusion Pass ------------------------------------===//
10 /// This file implements the loop fusion pass.
13 ///       Code Transformations to Augment the Scope of Loop Fusion in a
21 /// fusion are:
32 /// necessary information needed by fusion. It then operates on the fusion
33 /// candidates, first confirming that the candidate is eligible for fusion. The
37 /// requirements for fusion are met, the two candidates are fused, creating a
39 /// additional fusion.
42 /// conditions for fusion. Code transformations to make loops conform to each of
43 /// the conditions for fusion are discussed in more detail in the document
71 #define DEBUG_TYPE "loop-fusion"
74 STATISTIC(NumFusionCandidates, "Number of candidates for loop fusion");
85 STATISTIC(InvalidDependencies, "Dependencies prevent fusion");
93 STATISTIC(FusionNotBeneficial, "Fusion is not beneficial");
112     "loop-fusion-dependence-analysis",
113     cl::desc("Which dependence analysis should loop fusion use?"),
123     "loop-fusion-peel-max-count", cl::init(0), cl::Hidden,
125              "fusion can take place"));
129     VerboseFusionDebugging("loop-fusion-verbose-debug",
130                            cl::desc("Enable verbose debugging for Loop Fusion"),
135 /// This class is used to represent a candidate for loop fusion. When it is
136 /// constructed, it checks the conditions for loop fusion to ensure that it
138 /// used throughout loop fusion (e.g., loop preheader, loop header, etc) instead
140 /// assumed these will not change throughout loop fusion.
143 /// no longer a valid candidate for fusion. Similarly, the isValid() method can
144 /// be used to ensure that the FusionCandidate is still valid for fusion.
146   /// Cache of parts of the loop used throughout loop fusion. These should not
160   /// The loop that this fusion candidate represents
166   /// Are all of the members of this fusion candidate still valid
195     // prevent fusion. For each block, walk over all instructions and collect  in FusionCandidate()
196     // the memory reads and writes If any instructions that prevent fusion are  in FusionCandidate()
251   /// Get the entry block for this fusion candidate.
253   /// If this fusion candidate represents a guarded loop, the entry block is the
315   /// Determine if a fusion candidate (representing a loop) is eligible for
316   /// fusion. Note that this only checks whether a single loop can be fused - it
373     assert(L && Preheader && "Fusion candidate not initialized properly!");  in reportInvalidCandidate()
379              << "Loop is not a candidate for fusion: " << Stat.getDesc());  in reportInvalidCandidate()
386   /// Comparison functor to sort two Control Flow Equivalent fusion candidates
445         "No dominance relationship between these fusion candidates!");  in operator ()()
451 // Set of Control Flow Equivalent (CFE) Fusion Candidates, sorted in dominance
455 // iterators. A subsequent patch to loop fusion will enable fusing non-adjacent
485   dbgs() << "Fusion Candidates: \n";  in printFusionCandidates()
487     dbgs() << "*** Fusion Candidate Set ***\n";  in printFusionCandidates()
564   // Sets of control flow equivalent fusion candidates for a given nest level.
587   /// This is the main entry point for loop fusion. It will traverse the
597     LLVM_DEBUG(dbgs() << "Performing Loop Fusion on function " << F.getName()  in fuseLoops()
608         // Skip singleton loop sets as they do not offer fusion opportunities on  in fuseLoops()
637       LLVM_DEBUG(dbgs() << "Function after Loop Fusion: \n"; F.dump(););  in fuseLoops()
646     LLVM_DEBUG(dbgs() << "Loop Fusion complete\n");  in fuseLoops()
651   /// Determine if two fusion candidates are control flow equivalent.
653   /// Two fusion candidates are control flow equivalent if when one executes,
666   /// are eligible for fusion. Place all eligible fusion candidates into Control
713   /// time, to add heuristics for profitability of fusion.
719   /// Determine if two fusion candidates have the same trip count (i.e., they
851   /// Walk each set of control flow equivalent fusion candidates and attempt to
853   /// set. The conditions for legal fusion are checked at this point. If a pair
854   /// of fusion candidates passes all legality checks, they are fused together
855   /// and a new fusion candidate is created and added to the FusionCandidateSet.
856   /// The original fusion candidates are then removed, as they are no longer
865       LLVM_DEBUG(dbgs() << "Attempting fusion on Candidate Set:\n"  in fuseCandidates()
902               // assuming all other conditions for fusion return true.  in fuseCandidates()
908             LLVM_DEBUG(dbgs() << "Fusion candidates do not have identical trip "  in fuseCandidates()
917                        << "Fusion candidates are not adjacent. Not fusing.\n");  in fuseCandidates()
935             LLVM_DEBUG(dbgs() << "Fusion candidates do not have identical "  in fuseCandidates()
948               LLVM_DEBUG(dbgs() << "Fusion candidate contains unsafe "  in fuseCandidates()
960                          << "Fusion candidate contains unsafe "  in fuseCandidates()
971             LLVM_DEBUG(dbgs() << "Memory dependencies do not allow fusion!\n");  in fuseCandidates()
986             LLVM_DEBUG(dbgs() << "Fusion candidate does not have empty "  in fuseCandidates()
994                                    "Fusion Candidate Pre-header.\n"  in fuseCandidates()
1011           // All analysis has completed and has determined that fusion is legal  in fuseCandidates()
1013           // perform fusion.  in fuseCandidates()
1022           // Peel the loop after determining that fusion is legal. The Loops  in fuseCandidates()
1028           // Report fusion to the Optimization Remarks.  in fuseCandidates()
1031           // possible to identify them after fusion is complete.  in fuseCandidates()
1040                  "Fused candidate should be eligible for fusion!");  in fuseCandidates()
1058           LLVM_DEBUG(dbgs() << "Candidate Set (after fusion): " << CandidateSet  in fuseCandidates()
1323   /// @p L1) allow loop fusion of @p L0 and @p L1. The dependence analyses
1368     llvm_unreachable("Unknown fusion dependence analysis choice!");  in dependencesAllowFusion()
1427   /// Determine if two fusion candidates are adjacent in the CFG.
1486   /// Determine if two fusion candidates have identical guards
1488   /// This method will determine if two fusion candidates have the same guards.
1543   /// Fuse two fusion candidates, creating a new fused loop.
1548   /// assumes that the other conditions for fusion have been met: adjacent,
1550   /// would prevent fusion. Thus, there is no checking for these conditions in
1553   /// Fusion is performed by rewiring the CFG to update successor blocks of the
1566   /// fusion. For example, the preheader of \p FC1 can be merged with the
1574            "Expecting valid fusion candidates");  in performFusion()
1576     LLVM_DEBUG(dbgs() << "Fusion Candidate 0: \n"; FC0.dump();  in performFusion()
1577                dbgs() << "Fusion Candidate 1: \n"; FC1.dump(););  in performFusion()
1727     // and rebuild the information in subsequent passes of fusion?  in performFusion()
1765     LLVM_DEBUG(dbgs() << "Fusion done:\n");  in performFusion()
1770   /// Report details on loop fusion opportunities.
1773   /// loop fusion opportunities, based on the RemarkKind. The RemarkKind should
1775   ///   - OptimizationRemarkMissed to report when loop fusion is unsuccessful
1776   ///     given two valid fusion candidates.
1777   ///   - OptimizationRemark to report successful fusion of two fusion
1786            "Expecting valid fusion candidates");  in reportLoopFusion()
1799   /// Fuse two guarded fusion candidates, creating a new fused loop.
2021     // and rebuild the information in subsequent passes of fusion?  in fuseGuardedLoops()
2059     LLVM_DEBUG(dbgs() << "Fusion done:\n");  in fuseGuardedLoops()
2077   // Ensure loops are in simplifed form which is a pre-requisite for loop fusion  in run()