#include "llvm/Transforms/Scalar/LoopInterchange.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/StringSet.h"
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/Analysis/LoopCacheAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopNestAnalysis.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar/LoopPassManager.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include <cassert>
#include <utility>
#include <vector>

Macros
#define	DEBUG_TYPE "loop-interchange"

Functions
	STATISTIC (LoopsInterchanged, "Number of loops interchanged")

static void	printDepMatrix (CharMatrix &DepMatrix)

static bool	populateDependencyMatrix (CharMatrix &DepMatrix, unsigned Level, Loop L, DependenceInfo DI, ScalarEvolution SE, OptimizationRemarkEmitter ORE)

static void	interChangeDependencies (CharMatrix &DepMatrix, unsigned FromIndx, unsigned ToIndx)

static bool	isLexicographicallyPositive (std::vector< char > &DV)

static bool	isLegalToInterChangeLoops (CharMatrix &DepMatrix, unsigned InnerLoopId, unsigned OuterLoopId)

static void	populateWorklist (Loop &L, LoopVector &LoopList)

static bool	hasSupportedLoopDepth (SmallVectorImpl< Loop * > &LoopList, OptimizationRemarkEmitter &ORE)

static Value *	followLCSSA (Value *SV)

static PHINode *	findInnerReductionPhi (Loop L, Value V)

static bool	areInnerLoopExitPHIsSupported (Loop InnerL, Loop OuterL, SmallPtrSetImpl< PHINode * > &Reductions)

static bool	areOuterLoopExitPHIsSupported (Loop OuterLoop, Loop InnerLoop)

static bool	areInnerLoopLatchPHIsSupported (Loop OuterLoop, Loop InnerLoop)

static void	moveBBContents (BasicBlock FromBB, Instruction InsertBefore)
	Move all instructions except the terminator from FromBB right before InsertBefore.

static void	swapBBContents (BasicBlock BB1, BasicBlock BB2)
	Swap instructions between `BB1` and `BB2` but keep terminators intact.

static void	updateSuccessor (BranchInst BI, BasicBlock OldBB, BasicBlock *NewBB, std::vector< DominatorTree::UpdateType > &DTUpdates, bool MustUpdateOnce=true)

static void	moveLCSSAPhis (BasicBlock InnerExit, BasicBlock InnerHeader, BasicBlock InnerLatch, BasicBlock OuterHeader, BasicBlock OuterLatch, BasicBlock OuterExit, Loop InnerLoop, LoopInfo LI)

Variables
static cl::opt< int >	LoopInterchangeCostThreshold ("loop-interchange-threshold", cl::init(0), cl::Hidden, cl::desc("Interchange if you gain more than this number"))

static cl::opt< unsigned int >	MaxMemInstrCount ("loop-interchange-max-meminstr-count", cl::init(64), cl::Hidden, cl::desc("Maximum number of load-store instructions that should be handled " "in the dependency matrix. Higher value may lead to more interchanges " "at the cost of compile-time"))

static cl::opt< unsigned int >	MinLoopNestDepth ("loop-interchange-min-loop-nest-depth", cl::init(2), cl::Hidden, cl::desc("Minimum depth of loop nest considered for the transform"))

static cl::opt< unsigned int >	MaxLoopNestDepth ("loop-interchange-max-loop-nest-depth", cl::init(10), cl::Hidden, cl::desc("Maximum depth of loop nest considered for the transform"))

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "loop-interchange"

Definition at line 52 of file LoopInterchange.cpp.

Function Documentation

◆ areInnerLoopExitPHIsSupported()

static bool areInnerLoopExitPHIsSupported	(	Loop *	InnerL,
		Loop *	OuterL,
		SmallPtrSetImpl< PHINode * > &	Reductions
	)

static

Definition at line 890 of file LoopInterchange.cpp.

References llvm::any_of(), llvm::LoopBase< BlockT, LoopT >::getUniqueExitBlock(), PHI, llvm::BasicBlock::phis(), and llvm::Reductions.

◆ areInnerLoopLatchPHIsSupported()

static bool areInnerLoopLatchPHIsSupported	(	Loop *	OuterLoop,
		Loop *	InnerLoop
	)

static

Definition at line 948 of file LoopInterchange.cpp.

References llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::LoopBase< BlockT, LoopT >::getSubLoops(), llvm::BasicBlock::getUniquePredecessor(), PHI, and llvm::BasicBlock::phis().

◆ areOuterLoopExitPHIsSupported()

static bool areOuterLoopExitPHIsSupported	(	Loop *	OuterLoop,
		Loop *	InnerLoop
	)

static

Definition at line 915 of file LoopInterchange.cpp.

References llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::LoopBase< BlockT, LoopT >::getUniqueExitBlock(), llvm::BasicBlock::getUniquePredecessor(), PHI, and llvm::BasicBlock::phis().

◆ findInnerReductionPhi()

static PHINode * findInnerReductionPhi	(	Loop *	L,
		Value *	V
	)

static

Definition at line 737 of file LoopInterchange.cpp.

References llvm::RecurrenceDescriptor::getExactFPMathInst(), llvm::RecurrenceDescriptor::isReductionPHI(), and PHI.

◆ followLCSSA()

static Value * followLCSSA ( Value * SV )

static

Definition at line 726 of file LoopInterchange.cpp.

References followLCSSA(), and PHI.

Referenced by followLCSSA(), and moveLCSSAPhis().

◆ hasSupportedLoopDepth()

static bool hasSupportedLoopDepth	(	SmallVectorImpl< Loop * > &	LoopList,
		OptimizationRemarkEmitter &	ORE
	)

static

Definition at line 254 of file LoopInterchange.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::dbgs(), DEBUG_TYPE, llvm::OptimizationRemarkEmitter::emit(), LLVM_DEBUG, MaxLoopNestDepth, MinLoopNestDepth, and llvm::SmallVectorBase< Size_T >::size().

Referenced by llvm::LoopInterchangePass::run().

◆ interChangeDependencies()

static void interChangeDependencies	(	CharMatrix &	DepMatrix,
		unsigned	FromIndx,
		unsigned	ToIndx
	)

static

Definition at line 191 of file LoopInterchange.cpp.

References I, and std::swap().

◆ isLegalToInterChangeLoops()

static bool isLegalToInterChangeLoops	(	CharMatrix &	DepMatrix,
		unsigned	InnerLoopId,
		unsigned	OuterLoopId
	)

static

Definition at line 212 of file LoopInterchange.cpp.

References isLexicographicallyPositive(), and std::swap().

◆ isLexicographicallyPositive()

static bool isLexicographicallyPositive ( std::vector< char > & DV )

static

Definition at line 201 of file LoopInterchange.cpp.

Referenced by isLegalToInterChangeLoops().

◆ moveBBContents()

static void moveBBContents	(	BasicBlock *	FromBB,
		Instruction *	InsertBefore
	)

static

Move all instructions except the terminator from FromBB right before InsertBefore.

Definition at line 1423 of file LoopInterchange.cpp.

References llvm::BasicBlock::begin(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::BasicBlock::getTerminator(), and llvm::BasicBlock::splice().

Referenced by swapBBContents().

◆ moveLCSSAPhis()

static void moveLCSSAPhis	(	BasicBlock *	InnerExit,
		BasicBlock *	InnerHeader,
		BasicBlock *	InnerLatch,
		BasicBlock *	OuterHeader,
		BasicBlock *	OuterLatch,
		BasicBlock *	OuterExit,
		Loop *	InnerLoop,
		LoopInfo *	LI
	)

static

Definition at line 1476 of file LoopInterchange.cpp.

References llvm::PHINode::addIncoming(), llvm::all_of(), assert(), followLCSSA(), llvm::BasicBlock::getFirstNonPHIIt(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::BasicBlock::getParent(), I, llvm::Instruction::insertBefore(), llvm::make_early_inc_range(), P, llvm::BasicBlock::phis(), llvm::predecessors(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::BasicBlock::replacePhiUsesWith(), llvm::PHINode::setIncomingBlock(), and llvm::PHINode::setIncomingValue().

◆ populateDependencyMatrix()

static bool populateDependencyMatrix	(	CharMatrix &	DepMatrix,
		unsigned	Level,
		Loop *	L,
		DependenceInfo *	DI,
		ScalarEvolution *	SE,
		OptimizationRemarkEmitter *	ORE
	)

static

Definition at line 97 of file LoopInterchange.cpp.

References assert(), D, llvm::dbgs(), DEBUG_TYPE, llvm::DependenceInfo::depends(), llvm::OptimizationRemarkEmitter::emit(), llvm::Dependence::DVEntry::EQ, llvm::Dependence::DVEntry::GE, llvm::Dependence::DVEntry::GT, I, II, llvm::StringSet< AllocatorTy >::insert(), llvm::Dependence::DVEntry::LE, LLVM_DEBUG, llvm::Dependence::DVEntry::LT, MaxMemInstrCount, and llvm::SmallVectorTemplateBase< T, bool >::push_back().

◆ populateWorklist()

static void populateWorklist	(	Loop &	L,
		LoopVector &	LoopList
	)

static

Definition at line 231 of file LoopInterchange.cpp.

References assert(), llvm::dbgs(), llvm::LoopBase< BlockT, LoopT >::getSubLoops(), and LLVM_DEBUG.

◆ printDepMatrix()

static void printDepMatrix ( CharMatrix & DepMatrix )

static

Definition at line 88 of file LoopInterchange.cpp.

References D, llvm::dbgs(), and LLVM_DEBUG.

◆ STATISTIC()

STATISTIC	(	LoopsInterchanged	,
		"Number of loops interchanged"
	)

◆ swapBBContents()

static void swapBBContents	(	BasicBlock *	BB1,
		BasicBlock *	BB2
	)

static

Swap instructions between BB1 and BB2 but keep terminators intact.

Definition at line 1431 of file LoopInterchange.cpp.

References llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::BasicBlock::getTerminator(), I, llvm::map_range(), and moveBBContents().

◆ updateSuccessor()

static void updateSuccessor	(	BranchInst *	BI,
		BasicBlock *	OldBB,
		BasicBlock *	NewBB,
		std::vector< DominatorTree::UpdateType > &	DTUpdates,
		bool	MustUpdateOnce = `true`
	)

static

Definition at line 1450 of file LoopInterchange.cpp.

References assert(), llvm::count_if(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::User::operands(), and llvm::successors().

Variable Documentation

◆ LoopInterchangeCostThreshold

cl::opt< int > LoopInterchangeCostThreshold("loop-interchange-threshold", cl::init(0), cl::Hidden, cl::desc("Interchange if you gain more than this number"))	(	"loop-interchange-threshold"	,
		cl::init(0)	,
		cl::Hidden	,
		cl::desc("Interchange if you gain more than this number")
	)

static

◆ MaxLoopNestDepth

cl::opt< unsigned int > MaxLoopNestDepth("loop-interchange-max-loop-nest-depth", cl::init(10), cl::Hidden, cl::desc("Maximum depth of loop nest considered for the transform"))	(	"loop-interchange-max-loop-nest-depth"	,
		cl::init(10)	,
		cl::Hidden	,
		cl::desc("Maximum depth of loop nest considered for the transform")
	)

static

Referenced by hasSupportedLoopDepth().

◆ MaxMemInstrCount

cl::opt< unsigned int > MaxMemInstrCount("loop-interchange-max-meminstr-count", cl::init(64), cl::Hidden, cl::desc( "Maximum number of load-store instructions that should be handled " "in the dependency matrix. Higher value may lead to more interchanges " "at the cost of compile-time"))	(	"loop-interchange-max-meminstr-count"	,
		cl::init(64)	,
		cl::Hidden	,
		cl::desc( "Maximum number of load-store instructions that should be handled " "in the dependency matrix. Higher value may lead to more interchanges " "at the cost of compile-time")
	)

static

Referenced by populateDependencyMatrix(), and llvm::LoopInterchangePass::run().

◆ MinLoopNestDepth

cl::opt< unsigned int > MinLoopNestDepth("loop-interchange-min-loop-nest-depth", cl::init(2), cl::Hidden, cl::desc("Minimum depth of loop nest considered for the transform"))	(	"loop-interchange-min-loop-nest-depth"	,
		cl::init(2)	,
		cl::Hidden	,
		cl::desc("Minimum depth of loop nest considered for the transform")
	)

static

Referenced by hasSupportedLoopDepth().

Macros

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Function Documentation

◆ areInnerLoopExitPHIsSupported()

◆ areInnerLoopLatchPHIsSupported()

◆ areOuterLoopExitPHIsSupported()

◆ findInnerReductionPhi()

◆ followLCSSA()

◆ hasSupportedLoopDepth()

◆ interChangeDependencies()

◆ isLegalToInterChangeLoops()

◆ isLexicographicallyPositive()

◆ moveBBContents()

◆ moveLCSSAPhis()

◆ populateDependencyMatrix()

◆ populateWorklist()

◆ printDepMatrix()

◆ STATISTIC()

◆ swapBBContents()

◆ updateSuccessor()

Variable Documentation

◆ LoopInterchangeCostThreshold

◆ MaxLoopNestDepth

◆ MaxMemInstrCount

◆ MinLoopNestDepth