LLVM  10.0.0svn
Classes | Macros | Enumerations | Functions | Variables
LoopFuse.cpp File Reference

This file implements the loop fusion pass. More...

#include "llvm/Transforms/Scalar/LoopFuse.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
Include dependency graph for LoopFuse.cpp:

Go to the source code of this file.

Classes

struct  FusionCandidate
 This class is used to represent a candidate for loop fusion. More...
 
struct  FusionCandidateCompare
 
struct  LoopDepthTree
 Collect all loops in function at the same nest level, starting at the outermost level. More...
 
struct  LoopFuser
 
struct  LoopFuseLegacy
 

Macros

#define DEBUG_TYPE   "loop-fusion"
 

Enumerations

enum  FusionDependenceAnalysisChoice { FUSION_DEPENDENCE_ANALYSIS_SCEV, FUSION_DEPENDENCE_ANALYSIS_DA, FUSION_DEPENDENCE_ANALYSIS_ALL }
 

Functions

 STATISTIC (FuseCounter, "Loops fused")
 
 STATISTIC (NumFusionCandidates, "Number of candidates for loop fusion")
 
 STATISTIC (InvalidPreheader, "Loop has invalid preheader")
 
 STATISTIC (InvalidHeader, "Loop has invalid header")
 
 STATISTIC (InvalidExitingBlock, "Loop has invalid exiting blocks")
 
 STATISTIC (InvalidExitBlock, "Loop has invalid exit block")
 
 STATISTIC (InvalidLatch, "Loop has invalid latch")
 
 STATISTIC (InvalidLoop, "Loop is invalid")
 
 STATISTIC (AddressTakenBB, "Basic block has address taken")
 
 STATISTIC (MayThrowException, "Loop may throw an exception")
 
 STATISTIC (ContainsVolatileAccess, "Loop contains a volatile access")
 
 STATISTIC (NotSimplifiedForm, "Loop is not in simplified form")
 
 STATISTIC (InvalidDependencies, "Dependencies prevent fusion")
 
 STATISTIC (UnknownTripCount, "Loop has unknown trip count")
 
 STATISTIC (UncomputableTripCount, "SCEV cannot compute trip count of loop")
 
 STATISTIC (NonEqualTripCount, "Loop trip counts are not the same")
 
 STATISTIC (NonAdjacent, "Loops are not adjacent")
 
 STATISTIC (NonEmptyPreheader, "Loop has a non-empty preheader")
 
 STATISTIC (FusionNotBeneficial, "Fusion is not beneficial")
 
llvm::raw_ostreamoperator<< (llvm::raw_ostream &OS, const FusionCandidate &FC)
 
llvm::raw_ostreamoperator<< (llvm::raw_ostream &OS, const FusionCandidateSet &CandSet)
 
static void printFusionCandidates (const FusionCandidateCollection &FusionCandidates)
 
static void printLoopVector (const LoopVector &LV)
 
 INITIALIZE_PASS_BEGIN (LoopFuseLegacy, "loop-fusion", "Loop Fusion", false, false) FunctionPass *llvm
 

Variables

static cl::opt< FusionDependenceAnalysisChoiceFusionDependenceAnalysis ("loop-fusion-dependence-analysis", cl::desc("Which dependence analysis should loop fusion use?"), cl::values(clEnumValN(FUSION_DEPENDENCE_ANALYSIS_SCEV, "scev", "Use the scalar evolution interface"), clEnumValN(FUSION_DEPENDENCE_ANALYSIS_DA, "da", "Use the dependence analysis interface"), clEnumValN(FUSION_DEPENDENCE_ANALYSIS_ALL, "all", "Use all available analyses")), cl::Hidden, cl::init(FUSION_DEPENDENCE_ANALYSIS_ALL), cl::ZeroOrMore)
 
static cl::opt< boolVerboseFusionDebugging ("loop-fusion-verbose-debug", cl::desc("Enable verbose debugging for Loop Fusion"), cl::Hidden, cl::init(false), cl::ZeroOrMore)
 

Detailed Description

This file implements the loop fusion pass.

The implementation is largely based on the following document:

  Code Transformations to Augment the Scope of Loop Fusion in a
    Production Compiler
  Christopher Mark Barton
  MSc Thesis
  https://webdocs.cs.ualberta.ca/~amaral/thesis/ChristopherBartonMSc.pdf

The general approach taken is to collect sets of control flow equivalent loops and test whether they can be fused. The necessary conditions for fusion are:

  1. The loops must be adjacent (there cannot be any statements between the two loops).
  2. The loops must be conforming (they must execute the same number of iterations).
  3. The loops must be control flow equivalent (if one loop executes, the other is guaranteed to execute).
  4. There cannot be any negative distance dependencies between the loops. If all of these conditions are satisfied, it is safe to fuse the loops.

This implementation creates FusionCandidates that represent the loop and the necessary information needed by fusion. It then operates on the fusion candidates, first confirming that the candidate is eligible for fusion. The candidates are then collected into control flow equivalent sets, sorted in dominance order. Each set of control flow equivalent candidates is then traversed, attempting to fuse pairs of candidates in the set. If all requirements for fusion are met, the two candidates are fused, creating a new (fused) candidate which is then added back into the set to consider for additional fusion.

This implementation currently does not make any modifications to remove conditions for fusion. Code transformations to make loops conform to each of the conditions for fusion are discussed in more detail in the document above. These can be added to the current implementation in the future.

Definition in file LoopFuse.cpp.

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "loop-fusion"

Definition at line 67 of file LoopFuse.cpp.

Referenced by LoopFuser::fuseLoops(), and FusionCandidate::isEligibleForFusion().

Enumeration Type Documentation

◆ FusionDependenceAnalysisChoice

Enumerator
FUSION_DEPENDENCE_ANALYSIS_SCEV 
FUSION_DEPENDENCE_ANALYSIS_DA 
FUSION_DEPENDENCE_ANALYSIS_ALL 

Definition at line 89 of file LoopFuse.cpp.

Function Documentation

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN ( LoopFuseLegacy  ,
"loop-fusion"  ,
"Loop Fusion"  ,
false  ,
false   
)

Definition at line 1239 of file LoopFuse.cpp.

◆ operator<<() [1/2]

llvm::raw_ostream& operator<< ( llvm::raw_ostream OS,
const FusionCandidate FC 
)
inline

◆ operator<<() [2/2]

llvm::raw_ostream& operator<< ( llvm::raw_ostream OS,
const FusionCandidateSet &  CandSet 
)
inline

Definition at line 358 of file LoopFuse.cpp.

References IT.

◆ printFusionCandidates()

static void printFusionCandidates ( const FusionCandidateCollection &  FusionCandidates)
static

Definition at line 368 of file LoopFuse.cpp.

References llvm::dbgs().

Referenced by LoopFuser::fuseLoops().

◆ printLoopVector()

static void printLoopVector ( const LoopVector &  LV)
static

Definition at line 438 of file LoopFuse.cpp.

References llvm::dbgs(), and llvm::printLoop().

Referenced by LoopFuser::fuseLoops().

◆ STATISTIC() [1/19]

STATISTIC ( FuseCounter  ,
"Loops fused"   
)

◆ STATISTIC() [2/19]

STATISTIC ( NumFusionCandidates  ,
"Number of candidates for loop fusion"   
)

◆ STATISTIC() [3/19]

STATISTIC ( InvalidPreheader  ,
"Loop has invalid preheader  
)

◆ STATISTIC() [4/19]

STATISTIC ( InvalidHeader  ,
"Loop has invalid header"   
)

◆ STATISTIC() [5/19]

STATISTIC ( InvalidExitingBlock  ,
"Loop has invalid exiting blocks"   
)

◆ STATISTIC() [6/19]

STATISTIC ( InvalidExitBlock  ,
"Loop has invalid exit block"   
)

◆ STATISTIC() [7/19]

STATISTIC ( InvalidLatch  ,
"Loop has invalid latch"   
)

◆ STATISTIC() [8/19]

STATISTIC ( InvalidLoop  ,
"Loop is invalid"   
)

◆ STATISTIC() [9/19]

STATISTIC ( AddressTakenBB  ,
"Basic block has address taken"   
)

◆ STATISTIC() [10/19]

STATISTIC ( MayThrowException  ,
"Loop may throw an exception"   
)

◆ STATISTIC() [11/19]

STATISTIC ( ContainsVolatileAccess  ,
"Loop contains a volatile access"   
)

◆ STATISTIC() [12/19]

STATISTIC ( NotSimplifiedForm  ,
"Loop is not in simplified form"   
)

◆ STATISTIC() [13/19]

STATISTIC ( InvalidDependencies  ,
"Dependencies prevent fusion"   
)

◆ STATISTIC() [14/19]

STATISTIC ( UnknownTripCount  ,
"Loop has unknown trip count"   
)

◆ STATISTIC() [15/19]

STATISTIC ( UncomputableTripCount  ,
"SCEV cannot compute trip count of loop"   
)

◆ STATISTIC() [16/19]

STATISTIC ( NonEqualTripCount  ,
"Loop trip counts are not the same"   
)

◆ STATISTIC() [17/19]

STATISTIC ( NonAdjacent  ,
"Loops are not adjacent"   
)

◆ STATISTIC() [18/19]

STATISTIC ( NonEmptyPreheader  ,
"Loop has a non-empty preheader  
)

◆ STATISTIC() [19/19]

STATISTIC ( FusionNotBeneficial  ,
"Fusion is not beneficial"   
)

Variable Documentation

◆ FusionDependenceAnalysis

cl::opt<FusionDependenceAnalysisChoice> FusionDependenceAnalysis("loop-fusion-dependence-analysis", cl::desc("Which dependence analysis should loop fusion use?"), cl::values(clEnumValN(FUSION_DEPENDENCE_ANALYSIS_SCEV, "scev", "Use the scalar evolution interface"), clEnumValN(FUSION_DEPENDENCE_ANALYSIS_DA, "da", "Use the dependence analysis interface"), clEnumValN(FUSION_DEPENDENCE_ANALYSIS_ALL, "all", "Use all available analyses")), cl::Hidden, cl::init(FUSION_DEPENDENCE_ANALYSIS_ALL), cl::ZeroOrMore)
static

Referenced by LoopFuser::fuseLoops().

◆ VerboseFusionDebugging

cl::opt<bool> VerboseFusionDebugging("loop-fusion-verbose-debug", cl::desc("Enable verbose debugging for Loop Fusion"), cl::Hidden, cl::init(false), cl::ZeroOrMore)
static

Referenced by LoopFuser::fuseLoops().