#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/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/Constants.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.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/InitializePasses.h"
#include "llvm/Pass.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.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>

Include dependency graph for LoopInterchange.cpp:

Macros
#define	DEBUG_TYPE "loop-interchange"

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

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

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

static bool	containsNoDependence (CharMatrix &DepMatrix, unsigned Row, unsigned Column)

static bool	validDepInterchange (CharMatrix &DepMatrix, unsigned Row, unsigned OuterLoopId, char InnerDep, char OuterDep)

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

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

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 bool	isProfitableForVectorization (unsigned InnerLoopId, unsigned OuterLoopId, CharMatrix &DepMatrix)

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

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

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)

	INITIALIZE_PASS_BEGIN (LoopInterchangeLegacyPass, "loop-interchange", "Interchanges loops for cache reuse", false, false) INITIALIZE_PASS_END(LoopInterchangeLegacyPass

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 const unsigned	MaxMemInstrCount = 100

static const unsigned	MaxLoopNestDepth = 10

loop	interchange

loop Interchanges loops for cache	reuse

loop Interchanges loops for cache	false

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "loop-interchange"

Definition at line 56 of file LoopInterchange.cpp.

Function Documentation

◆ areInnerLoopExitPHIsSupported()

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

static

Definition at line 877 of file LoopInterchange.cpp.

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

◆ areInnerLoopLatchPHIsSupported()

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

static

Definition at line 935 of file LoopInterchange.cpp.

References llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::Instruction::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 902 of file LoopInterchange.cpp.

References llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::Instruction::getParent(), llvm::LoopBase< BlockT, LoopT >::getUniqueExitBlock(), llvm::BasicBlock::getUniquePredecessor(), i, PHI, and llvm::BasicBlock::phis().

◆ containsNoDependence()

static bool containsNoDependence	(	CharMatrix &	DepMatrix,
		unsigned	Row,
		unsigned	Column
	)

static

Definition at line 186 of file LoopInterchange.cpp.

References i.

Referenced by validDepInterchange().

◆ findInnerReductionPhi()

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

static

Definition at line 731 of file LoopInterchange.cpp.

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

◆ followLCSSA()

static Value* followLCSSA ( Value * SV )

static

Definition at line 720 of file LoopInterchange.cpp.

References PHI.

Referenced by moveLCSSAPhis().

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	LoopInterchangeLegacyPass	,
		"loop-interchange"	,
		"Interchanges loops for cache reuse"	,
		false	,
		false
	)

◆ interChangeDependencies()

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

static

Definition at line 179 of file LoopInterchange.cpp.

References E, I, and std::swap().

◆ isLegalToInterChangeLoops()

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

static

Definition at line 231 of file LoopInterchange.cpp.

References validDepInterchange().

◆ isProfitableForVectorization()

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

static

Definition at line 1113 of file LoopInterchange.cpp.

◆ moveBBContents()

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

static

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

Definition at line 1371 of file LoopInterchange.cpp.

References llvm::BasicBlock::getInstList(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::Instruction::getParent(), and llvm::BasicBlock::getTerminator().

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 1425 of file LoopInterchange.cpp.

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

◆ populateDependencyMatrix()

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

static

Definition at line 89 of file LoopInterchange.cpp.

References assert(), BB, llvm::LoopBase< BlockT, LoopT >::blocks(), D, llvm::dbgs(), llvm::DependenceInfo::depends(), llvm::Dependence::DVEntry::EQ, llvm::Dependence::DVEntry::GE, llvm::Dependence::DVEntry::GT, I, llvm::ARM_PROC::IE, llvm::Dependence::DVEntry::LE, LLVM_DEBUG, llvm::Dependence::DVEntry::LT, and MaxMemInstrCount.

◆ populateWorklist()

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

static

Definition at line 247 of file LoopInterchange.cpp.

References assert(), llvm::dbgs(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::Value::getName(), llvm::BasicBlock::getParent(), llvm::LoopBase< BlockT, LoopT >::getSubLoops(), 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 1380 of file LoopInterchange.cpp.

References 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 1399 of file LoopInterchange.cpp.

References assert(), BB, llvm::count_if(), llvm::cfg::Delete, llvm::Instruction::getParent(), llvm::cfg::Insert, llvm::User::operands(), and llvm::successors().

◆ validDepInterchange()

static bool validDepInterchange	(	CharMatrix &	DepMatrix,
		unsigned	Row,
		unsigned	OuterLoopId,
		char	InnerDep,
		char	OuterDep
	)

static

Definition at line 196 of file LoopInterchange.cpp.

References containsNoDependence().

Referenced by isLegalToInterChangeLoops().

Variable Documentation

◆ false

loop Interchanges loops for cache false

Definition at line 1733 of file LoopInterchange.cpp.

◆ interchange

loop interchange

Definition at line 1732 of file LoopInterchange.cpp.

◆ LoopInterchangeCostThreshold

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

static

◆ MaxLoopNestDepth

const unsigned MaxLoopNestDepth = 10

static

Definition at line 77 of file LoopInterchange.cpp.

◆ MaxMemInstrCount

const unsigned MaxMemInstrCount = 100

static

Definition at line 74 of file LoopInterchange.cpp.

Referenced by populateDependencyMatrix().

◆ reuse

loop Interchanges loops for cache reuse

Definition at line 1733 of file LoopInterchange.cpp.

Macros

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Function Documentation

◆ areInnerLoopExitPHIsSupported()

◆ areInnerLoopLatchPHIsSupported()

◆ areOuterLoopExitPHIsSupported()

◆ containsNoDependence()

◆ findInnerReductionPhi()

◆ followLCSSA()

◆ INITIALIZE_PASS_BEGIN()

◆ interChangeDependencies()

◆ isLegalToInterChangeLoops()

◆ isProfitableForVectorization()

◆ moveBBContents()

◆ moveLCSSAPhis()

◆ populateDependencyMatrix()

◆ populateWorklist()

◆ STATISTIC()

◆ swapBBContents()

◆ updateSuccessor()

◆ validDepInterchange()

Variable Documentation

◆ false

◆ interchange

◆ LoopInterchangeCostThreshold

◆ MaxLoopNestDepth

◆ MaxMemInstrCount

◆ reuse