#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)

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	hasMinimumLoopDepth (SmallVectorImpl< Loop * > &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 870 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 928 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 895 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 717 of file LoopInterchange.cpp.

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

◆ followLCSSA()

static Value * followLCSSA ( Value * SV )

static

Definition at line 706 of file LoopInterchange.cpp.

References followLCSSA(), and PHI.

Referenced by followLCSSA(), and moveLCSSAPhis().

◆ hasMinimumLoopDepth()

static bool hasMinimumLoopDepth ( SmallVectorImpl< Loop * > & LoopList )

static

Definition at line 242 of file LoopInterchange.cpp.

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

References I, and std::swap().

◆ isLegalToInterChangeLoops()

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

static

Definition at line 200 of file LoopInterchange.cpp.

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

◆ isLexicographicallyPositive()

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

static

Definition at line 189 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 1402 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 1455 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, 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 219 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 76 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 1410 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 1429 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

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

◆ hasMinimumLoopDepth()

◆ interChangeDependencies()

◆ isLegalToInterChangeLoops()

◆ isLexicographicallyPositive()

◆ moveBBContents()

◆ moveLCSSAPhis()

◆ populateDependencyMatrix()

◆ populateWorklist()

◆ printDepMatrix()

◆ STATISTIC()

◆ swapBBContents()

◆ updateSuccessor()

Variable Documentation

◆ LoopInterchangeCostThreshold

◆ MaxLoopNestDepth

◆ MaxMemInstrCount