LoopUnrollAndJam.cpp File Reference

#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/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/ScalarEvolutionExpander.h"
#include "llvm/Transforms/Utils/UnrollLoop.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <assert.h>
#include <memory>
#include <type_traits>
#include <vector>

Go to the source code of this file.

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.
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, BasicBlock::iterator 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 754 of file LoopUnrollAndJam.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), Blocks, checkDependency(), llvm::SmallVectorImpl< T >::clear(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::contains(), llvm::SmallVectorTemplateCommon< T, typename >::end(), getLoadsAndStores(), llvm::LoopBase< BlockT, LoopT >::getLoopDepth(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getLoopsInPreorder(), I, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::SmallVectorBase< Size_T >::size().

Referenced by llvm::isSafeToUnrollAndJam().

checkDependency()

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

static

Definition at line 690 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 854 of file LoopUnrollAndJam.cpp.

Referenced by llvm::isSafeToUnrollAndJam().

getLoadsAndStores()

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

static

Definition at line 624 of file LoopUnrollAndJam.cpp.

References Blocks, I, and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by checkDependencies().

isEligibleLoopForm()

static bool isEligibleLoopForm ( const Loop &  Root )

static

Definition at line 804 of file LoopUnrollAndJam.cpp.

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

Referenced by llvm::isSafeToUnrollAndJam().

moveHeaderPhiOperandsToForeBlocks()

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

static

Definition at line 166 of file LoopUnrollAndJam.cpp.

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

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 llvm::LoopBase< BlockT, LoopT >::contains(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::DominatorTree::dominates(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), 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 664 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 646 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, II, and llvm::SmallPtrSetImpl< PtrType >::insert().

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