Lines Matching full:fusion

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()