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/AssumptionCache.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/Analysis/TargetTransformInfo.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/CodeMoverUtils.h"
#include "llvm/Transforms/Utils/LoopPeel.h"
#include "llvm/Transforms/Utils/LoopSimplify.h"

Go to the source code of this file.

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 with instructions that cannot be moved")
	STATISTIC (FusionNotBeneficial, "Fusion is not beneficial")
	STATISTIC (NonIdenticalGuards, "Candidates have different guards")
	STATISTIC (NonEmptyExitBlock, "Candidate has a non-empty exit block with " "instructions that cannot be moved")
	STATISTIC (NonEmptyGuardBlock, "Candidate has a non-empty guard block with " "instructions that cannot be moved")
	STATISTIC (NotRotated, "Candidate is not rotated")
	STATISTIC (OnlySecondCandidateIsGuarded, "The second candidate is guarded while the first one is not")
	STATISTIC (NumHoistedInsts, "Number of hoisted preheader instructions.")
	STATISTIC (NumSunkInsts, "Number of hoisted preheader instructions.")

Variables
static 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))
static cl::opt< unsigned >	FusionPeelMaxCount ("loop-fusion-peel-max-count", cl::init(0), cl::Hidden, cl::desc("Max number of iterations to be peeled from a loop, such that " "fusion can take place"))
static cl::opt< bool >	VerboseFusionDebugging ("loop-fusion-verbose-debug", cl::desc("Enable verbose debugging for Loop Fusion"), cl::Hidden, cl::init(false))

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 71 of file LoopFuse.cpp.

Enumeration Type Documentation

FusionDependenceAnalysisChoice

enum FusionDependenceAnalysisChoice

Enumerator
FUSION_DEPENDENCE_ANALYSIS_SCEV
FUSION_DEPENDENCE_ANALYSIS_DA
FUSION_DEPENDENCE_ANALYSIS_ALL

Definition at line 105 of file LoopFuse.cpp.

Function Documentation

STATISTIC() [1/26]

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

STATISTIC() [2/26]

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

STATISTIC() [3/26]

STATISTIC	(	FuseCounter	,
		"Loops fused"
	)

STATISTIC() [4/26]

STATISTIC	(	FusionNotBeneficial	,
		"Fusion is not beneficial"
	)

STATISTIC() [5/26]

STATISTIC	(	InvalidDependencies	,
		"Dependencies prevent fusion"
	)

STATISTIC() [6/26]

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

STATISTIC() [7/26]

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

STATISTIC() [8/26]

STATISTIC	(	InvalidHeader	,
		"Loop has invalid header"
	)

STATISTIC() [9/26]

STATISTIC	(	InvalidLatch	,
		"Loop has invalid latch"
	)

STATISTIC() [10/26]

STATISTIC	(	InvalidLoop	,
		"Loop is invalid"
	)

STATISTIC() [11/26]

STATISTIC	(	InvalidPreheader	,
		"Loop has invalid preheader"
	)

STATISTIC() [12/26]

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

STATISTIC() [13/26]

STATISTIC	(	NonAdjacent	,
		"Loops are not adjacent"
	)

STATISTIC() [14/26]

STATISTIC	(	NonEmptyExitBlock	,
		"Candidate has a non-empty exit block with " "instructions that cannot be moved"
	)

STATISTIC() [15/26]

STATISTIC	(	NonEmptyGuardBlock	,
		"Candidate has a non-empty guard block with " "instructions that cannot be moved"
	)

STATISTIC() [16/26]

STATISTIC	(	NonEmptyPreheader	,
		"Loop has a non-empty preheader with instructions that cannot be moved"
	)

STATISTIC() [17/26]

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

STATISTIC() [18/26]

STATISTIC	(	NonIdenticalGuards	,
		"Candidates have different guards"
	)

STATISTIC() [19/26]

STATISTIC	(	NotRotated	,
		"Candidate is not rotated"
	)

STATISTIC() [20/26]

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

STATISTIC() [21/26]

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

STATISTIC() [22/26]

STATISTIC	(	NumHoistedInsts	,
		"Number of hoisted preheader instructions."
	)

STATISTIC() [23/26]

STATISTIC	(	NumSunkInsts	,
		"Number of hoisted preheader instructions."
	)

STATISTIC() [24/26]

STATISTIC	(	OnlySecondCandidateIsGuarded	,
		"The second candidate is guarded while the first one is not"
	)

STATISTIC() [25/26]

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

STATISTIC() [26/26]

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

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

static

FusionPeelMaxCount

cl::opt< unsigned > FusionPeelMaxCount("loop-fusion-peel-max-count", cl::init(0), cl::Hidden, cl::desc("Max number of iterations to be peeled from a loop, such that " "fusion can take place")) ( "loop-fusion-peel-max-count"  , cl::init(0)  , cl::Hidden  , cl::desc("Max number of iterations to be peeled from a loop, such that " "fusion can take place")    )

static

VerboseFusionDebugging

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

static