#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/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 bool	populateDependencyMatrix (CharMatrix &DepMatrix, unsigned Level, Loop L, DependenceInfo DI, ScalarEvolution *SE)

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

static const unsigned	MaxLoopNestDepth = 10

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 859 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 917 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 884 of file LoopInterchange.cpp.

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

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

◆ followLCSSA()

static Value * followLCSSA ( Value * SV )

static

Definition at line 695 of file LoopInterchange.cpp.

References followLCSSA(), and PHI.

Referenced by followLCSSA(), and moveLCSSAPhis().

◆ interChangeDependencies()

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

static

Definition at line 175 of file LoopInterchange.cpp.

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

◆ isLegalToInterChangeLoops()

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

static

Definition at line 196 of file LoopInterchange.cpp.

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

◆ isLexicographicallyPositive()

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

static

Definition at line 185 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 1391 of file LoopInterchange.cpp.

References llvm::BasicBlock::begin(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::Instruction::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 1444 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::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
	)

static

Definition at line 85 of file LoopInterchange.cpp.

References assert(), D, llvm::dbgs(), llvm::DependenceInfo::depends(), llvm::Dependence::DVEntry::EQ, llvm::Dependence::DVEntry::GE, llvm::Dependence::DVEntry::GT, I, 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 215 of file LoopInterchange.cpp.

References assert(), llvm::dbgs(), 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 1399 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 1418 of file LoopInterchange.cpp.

References assert(), llvm::count_if(), llvm::Instruction::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

const unsigned MaxLoopNestDepth = 10

static

Definition at line 73 of file LoopInterchange.cpp.

◆ MaxMemInstrCount

const unsigned MaxMemInstrCount = 100

static

Definition at line 70 of file LoopInterchange.cpp.

Referenced by populateDependencyMatrix().

Macros

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Function Documentation

◆ areInnerLoopExitPHIsSupported()

◆ areInnerLoopLatchPHIsSupported()

◆ areOuterLoopExitPHIsSupported()

◆ findInnerReductionPhi()

◆ followLCSSA()

◆ interChangeDependencies()

◆ isLegalToInterChangeLoops()

◆ isLexicographicallyPositive()

◆ moveBBContents()

◆ moveLCSSAPhis()

◆ populateDependencyMatrix()

◆ populateWorklist()

◆ STATISTIC()

◆ swapBBContents()

◆ updateSuccessor()

Variable Documentation

◆ LoopInterchangeCostThreshold

◆ MaxLoopNestDepth

◆ MaxMemInstrCount