#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/Twine.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/MustExecute.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/IR/ValueMap.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/GenericDomTree.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/UnrollLoop.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <assert.h>
#include <memory>
#include <type_traits>
#include <vector>

Include dependency graph for LoopUnrollAndJam.cpp:

Macros
#define	DEBUG_TYPE "loop-unroll-and-jam"

Typedefs
typedef SmallPtrSet< BasicBlock *, 4 >	BasicBlockSet

Functions
	STATISTIC (NumUnrolledAndJammed, "Number of loops unroll and jammed")

	STATISTIC (NumCompletelyUnrolledAndJammed, "Number of loops unroll and jammed")

static bool	partitionLoopBlocks (Loop &L, BasicBlockSet &ForeBlocks, BasicBlockSet &AftBlocks, DominatorTree &DT)

static bool	partitionOuterLoopBlocks (Loop &Root, Loop &JamLoop, BasicBlockSet &JamLoopBlocks, DenseMap< Loop , BasicBlockSet > &ForeBlocksMap, DenseMap< Loop , BasicBlockSet > &AftBlocksMap, DominatorTree &DT)
	Partition blocks in a loop nest into blocks before and after each inner loop. More...

static bool	partitionOuterLoopBlocks (Loop L, Loop SubLoop, BasicBlockSet &ForeBlocks, BasicBlockSet &SubLoopBlocks, BasicBlockSet &AftBlocks, DominatorTree *DT)

template<typename T >
static bool	processHeaderPhiOperands (BasicBlock Header, BasicBlock Latch, BasicBlockSet &AftBlocks, T Visit)

static void	moveHeaderPhiOperandsToForeBlocks (BasicBlock Header, BasicBlock Latch, Instruction *InsertLoc, BasicBlockSet &AftBlocks)

static bool	getLoadsAndStores (BasicBlockSet &Blocks, SmallVector< Instruction *, 4 > &MemInstr)

static bool	preservesForwardDependence (Instruction Src, Instruction Dst, unsigned UnrollLevel, unsigned JamLevel, bool Sequentialized, Dependence *D)

static bool	preservesBackwardDependence (Instruction Src, Instruction Dst, unsigned UnrollLevel, unsigned JamLevel, bool Sequentialized, Dependence *D)

static bool	checkDependency (Instruction Src, Instruction Dst, unsigned UnrollLevel, unsigned JamLevel, bool Sequentialized, DependenceInfo &DI)

static bool	checkDependencies (Loop &Root, const BasicBlockSet &SubLoopBlocks, const DenseMap< Loop , BasicBlockSet > &ForeBlocksMap, const DenseMap< Loop , BasicBlockSet > &AftBlocksMap, DependenceInfo &DI, LoopInfo &LI)

static bool	isEligibleLoopForm (const Loop &Root)

static Loop *	getInnerMostLoop (Loop *L)

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "loop-unroll-and-jam"

Definition at line 61 of file LoopUnrollAndJam.cpp.

Typedef Documentation

◆ BasicBlockSet

typedef SmallPtrSet<BasicBlock *, 4> BasicBlockSet

Definition at line 66 of file LoopUnrollAndJam.cpp.

Function Documentation

◆ checkDependencies()

static bool checkDependencies	(	Loop &	Root,
		const BasicBlockSet &	SubLoopBlocks,
		const DenseMap< Loop *, BasicBlockSet > &	ForeBlocksMap,
		const DenseMap< Loop *, BasicBlockSet > &	AftBlocksMap,
		DependenceInfo &	DI,
		LoopInfo &	LI
	)

static

Definition at line 758 of file LoopUnrollAndJam.cpp.

References llvm::SmallVectorImpl< T >::append(), checkDependency(), llvm::SmallVectorImpl< T >::clear(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find(), getLoadsAndStores(), llvm::LoopBase< BlockT, LoopT >::getLoopDepth(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getLoopsInPreorder(), I, llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::lookup(), and llvm::min().

Referenced by llvm::isSafeToUnrollAndJam().

◆ checkDependency()

static bool checkDependency	(	Instruction *	Src,
		Instruction *	Dst,
		unsigned	UnrollLevel,
		unsigned	JamLevel,
		bool	Sequentialized,
		DependenceInfo &	DI
	)

static

Definition at line 694 of file LoopUnrollAndJam.cpp.

References assert(), D, llvm::dbgs(), llvm::DependenceInfo::depends(), llvm::Dependence::DVEntry::EQ, llvm::Dependence::DVEntry::GT, LLVM_DEBUG, llvm::Dependence::DVEntry::LT, preservesBackwardDependence(), and preservesForwardDependence().

Referenced by checkDependencies().

◆ getInnerMostLoop()

static Loop* getInnerMostLoop ( Loop * L )

static

Definition at line 858 of file LoopUnrollAndJam.cpp.

References llvm::LoopBase< BlockT, LoopT >::getSubLoops().

Referenced by llvm::isSafeToUnrollAndJam().

◆ getLoadsAndStores()

static bool getLoadsAndStores	(	BasicBlockSet &	Blocks,
		SmallVector< Instruction *, 4 > &	MemInstr
	)

static

Definition at line 628 of file LoopUnrollAndJam.cpp.

References BB, and I.

Referenced by checkDependencies().

◆ isEligibleLoopForm()

static bool isEligibleLoopForm ( const Loop & Root )

static

Definition at line 808 of file LoopUnrollAndJam.cpp.

References llvm::dbgs(), llvm::LoopBase< BlockT, LoopT >::getExitBlock(), llvm::LoopBase< BlockT, LoopT >::getExitingBlock(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getSubLoops(), llvm::BasicBlock::hasAddressTaken(), llvm::Loop::isLoopSimplifyForm(), llvm::Loop::isRotatedForm(), and LLVM_DEBUG.

Referenced by llvm::isSafeToUnrollAndJam().

◆ moveHeaderPhiOperandsToForeBlocks()

static void moveHeaderPhiOperandsToForeBlocks	(	BasicBlock *	Header,
		BasicBlock *	Latch,
		Instruction *	InsertLoc,
		BasicBlockSet &	AftBlocks
	)

static

Definition at line 165 of file LoopUnrollAndJam.cpp.

References llvm::SmallPtrSetImpl< PtrType >::count(), llvm::Instruction::getParent(), I, processHeaderPhiOperands(), and llvm::reverse().

Referenced by llvm::UnrollAndJamLoop().

◆ partitionLoopBlocks()

static bool partitionLoopBlocks	(	Loop &	L,
		BasicBlockSet &	ForeBlocks,
		BasicBlockSet &	AftBlocks,
		DominatorTree &	DT
	)

static

Definition at line 70 of file LoopUnrollAndJam.cpp.

References BB, llvm::LoopBase< BlockT, LoopT >::blocks(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::DominatorTree::dominates(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::LoopBase< BlockT, LoopT >::getSubLoops(), llvm::SmallPtrSetImpl< PtrType >::insert(), and llvm::successors().

Referenced by partitionOuterLoopBlocks().

◆ partitionOuterLoopBlocks() [1/2]

static bool partitionOuterLoopBlocks	(	Loop &	Root,
		Loop &	JamLoop,
		BasicBlockSet &	JamLoopBlocks,
		DenseMap< Loop *, BasicBlockSet > &	ForeBlocksMap,
		DenseMap< Loop *, BasicBlockSet > &	AftBlocksMap,
		DominatorTree &	DT
	)

static

Partition blocks in a loop nest into blocks before and after each inner loop.

Definition at line 101 of file LoopUnrollAndJam.cpp.

References llvm::LoopBase< BlockT, LoopT >::block_begin(), llvm::LoopBase< BlockT, LoopT >::block_end(), llvm::LoopBase< BlockT, LoopT >::getLoopsInPreorder(), llvm::SmallPtrSetImpl< PtrType >::insert(), and partitionLoopBlocks().

Referenced by llvm::isSafeToUnrollAndJam(), and llvm::UnrollAndJamLoop().

◆ partitionOuterLoopBlocks() [2/2]

static bool partitionOuterLoopBlocks	(	Loop *	L,
		Loop *	SubLoop,
		BasicBlockSet &	ForeBlocks,
		BasicBlockSet &	SubLoopBlocks,
		BasicBlockSet &	AftBlocks,
		DominatorTree *	DT
	)

static

Definition at line 120 of file LoopUnrollAndJam.cpp.

References llvm::LoopBase< BlockT, LoopT >::block_begin(), llvm::LoopBase< BlockT, LoopT >::block_end(), llvm::SmallPtrSetImpl< PtrType >::insert(), and partitionLoopBlocks().

◆ preservesBackwardDependence()

static bool preservesBackwardDependence	(	Instruction *	Src,
		Instruction *	Dst,
		unsigned	UnrollLevel,
		unsigned	JamLevel,
		bool	Sequentialized,
		Dependence *	D
	)

static

Definition at line 668 of file LoopUnrollAndJam.cpp.

References D, llvm::Dependence::DVEntry::GT, and llvm::Dependence::DVEntry::LT.

Referenced by checkDependency().

◆ preservesForwardDependence()

static bool preservesForwardDependence	(	Instruction *	Src,
		Instruction *	Dst,
		unsigned	UnrollLevel,
		unsigned	JamLevel,
		bool	Sequentialized,
		Dependence *	D
	)

static

Definition at line 650 of file LoopUnrollAndJam.cpp.

References D, llvm::Dependence::DVEntry::GT, and llvm::Dependence::DVEntry::LT.

Referenced by checkDependency().

◆ processHeaderPhiOperands()

template<typename T >

static bool processHeaderPhiOperands	(	BasicBlock *	Header,
		BasicBlock *	Latch,
		BasicBlockSet &	AftBlocks,
		T	Visit
	)

static

Definition at line 138 of file LoopUnrollAndJam.cpp.

References llvm::SmallPtrSetImpl< PtrType >::count(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), and llvm::SmallVectorImpl< T >::pop_back_val().

Referenced by llvm::isSafeToUnrollAndJam(), and moveHeaderPhiOperandsToForeBlocks().

◆ STATISTIC() [1/2]

STATISTIC	(	NumCompletelyUnrolledAndJammed	,
		"Number of loops unroll and jammed"
	)

◆ STATISTIC() [2/2]

STATISTIC	(	NumUnrolledAndJammed	,
		"Number of loops unroll and jammed"
	)

Macros

Typedefs

Functions

Macro Definition Documentation

◆ DEBUG_TYPE

Typedef Documentation

◆ BasicBlockSet

Function Documentation

◆ checkDependencies()

◆ checkDependency()

◆ getInnerMostLoop()

◆ getLoadsAndStores()

◆ isEligibleLoopForm()

◆ moveHeaderPhiOperandsToForeBlocks()

◆ partitionLoopBlocks()

◆ partitionOuterLoopBlocks() [1/2]

◆ partitionOuterLoopBlocks() [2/2]

◆ preservesBackwardDependence()

◆ preservesForwardDependence()

◆ processHeaderPhiOperands()

◆ STATISTIC() [1/2]

◆ STATISTIC() [2/2]