LoopUnroll.cpp File Reference

#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopedHashTable.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/Twine.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.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/Metadata.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/IR/ValueMap.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.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/Local.h"
#include "llvm/Transforms/Utils/LoopSimplify.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
#include "llvm/Transforms/Utils/SimplifyIndVar.h"
#include "llvm/Transforms/Utils/UnrollLoop.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <algorithm>
#include <assert.h>
#include <numeric>
#include <type_traits>
#include <vector>

Go to the source code of this file.

Classes
struct	LoadValue
class	StackNode

Namespaces
namespace	llvm
	This is an optimization pass for GlobalISel generic memory operations.

Macros
#define	DEBUG_TYPE   "loop-unroll"

Functions
	STATISTIC (NumCompletelyUnrolled, "Number of loops completely unrolled")
	STATISTIC (NumUnrolled, "Number of loops unrolled (completely or otherwise)")
	STATISTIC (NumUnrolledNotLatch, "Number of loops unrolled without a conditional " "latch (completely or otherwise)")
static bool	needToInsertPhisForLCSSA (Loop *L, const std::vector< BasicBlock * > &Blocks, LoopInfo *LI)
	Check if unrolling created a situation where we need to insert phi nodes to preserve LCSSA form.
static bool	isEpilogProfitable (Loop *L)
	The function chooses which type of unroll (epilog or prolog) is more profitabale.
Value *	getMatchingValue (LoadValue LV, LoadInst *LI, unsigned CurrentGeneration, BatchAAResults &BAA, function_ref< MemorySSA *()> GetMSSA)
void	loadCSE (Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, BatchAAResults &BAA, function_ref< MemorySSA *()> GetMSSA)
static LLVM_ATTRIBUTE_USED bool	canHaveUnrollRemainder (const Loop *L)

Variables
static cl::opt< bool >	UnrollRuntimeEpilog ("unroll-runtime-epilog", cl::init(false), cl::Hidden, cl::desc("Allow runtime unrolled loops to be unrolled " "with epilog instead of prolog."))
static cl::opt< bool >	UnrollVerifyDomtree ("unroll-verify-domtree", cl::Hidden, cl::desc("Verify domtree after unrolling"), cl::init(false))
static cl::opt< bool >	UnrollVerifyLoopInfo ("unroll-verify-loopinfo", cl::Hidden, cl::desc("Verify loopinfo after unrolling"), cl::init(false))

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "loop-unroll"

Definition at line 80 of file LoopUnroll.cpp.

Function Documentation

canHaveUnrollRemainder()

static LLVM_ATTRIBUTE_USED bool canHaveUnrollRemainder ( const Loop *  L )

static

Definition at line 423 of file LoopUnroll.cpp.

References llvm::getLoopConvergenceHeart(), and I.

Referenced by llvm::UnrollLoop().

getMatchingValue()

Value * getMatchingValue	(	LoadValue	LV,
		LoadInst *	LI,
		unsigned	CurrentGeneration,
		BatchAAResults &	BAA,
		function_ref< MemorySSA *()>	GetMSSA
	)

Definition at line 254 of file LoopUnroll.cpp.

References LoadValue::DefI, llvm::MemorySSA::dominates(), LoadValue::Generation, llvm::MemorySSAWalker::getClobberingMemoryAccess(), llvm::MemorySSA::getMemoryAccess(), llvm::Value::getType(), and llvm::MemorySSA::getWalker().

Referenced by loadCSE().

isEpilogProfitable()

static bool isEpilogProfitable ( Loop *  L )

static

The function chooses which type of unroll (epilog or prolog) is more profitabale.

Epilog unroll is more profitable when there is PHI that starts from constant. In this case epilog will leave PHI start from constant, but prolog will convert it to non-constant.

loop: PN = PHI [I, Latch], [CI, PreHeader] I = foo(PN) ...

Epilog unroll case. loop: PN = PHI [I2, Latch], [CI, PreHeader] I1 = foo(PN) I2 = foo(I1) ... Prolog unroll case. NewPN = PHI [PrologI, Prolog], [CI, PreHeader] loop: PN = PHI [I2, Latch], [NewPN, PreHeader] I1 = foo(PN) I2 = foo(I1) ...

Definition at line 202 of file LoopUnroll.cpp.

References assert().

Referenced by llvm::UnrollLoop().

loadCSE()

void loadCSE	(	Loop *	L,
		DominatorTree &	DT,
		ScalarEvolution &	SE,
		LoopInfo &	LI,
		BatchAAResults &	BAA,
		function_ref< MemorySSA *()>	GetMSSA
	)

Definition at line 274 of file LoopUnroll.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::back(), llvm::DomTreeNodeBase< NodeT >::begin(), StackNode::childGeneration(), StackNode::childIter(), StackNode::currentGeneration(), llvm::SmallVectorImpl< T >::emplace_back(), llvm::SmallVectorBase< Size_T >::empty(), llvm::DomTreeNodeBase< NodeT >::end(), StackNode::end(), llvm::DomTreeNodeBase< NodeT >::getBlock(), getMatchingValue(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::ScalarEvolution::getSCEV(), llvm::BasicBlock::getSinglePredecessor(), I, llvm::ScopedHashTable< K, V, KInfo, AllocatorTy >::insert(), StackNode::isProcessed(), llvm::ScopedHashTable< K, V, KInfo, AllocatorTy >::lookup(), llvm::make_early_inc_range(), StackNode::nextChild(), StackNode::node(), llvm::SmallVectorTemplateBase< T, bool >::pop_back(), StackNode::process(), and llvm::LoopInfo::replacementPreservesLCSSAForm().

Referenced by llvm::simplifyLoopAfterUnroll().

needToInsertPhisForLCSSA()

static bool needToInsertPhisForLCSSA ( Loop *  L, const std::vector< BasicBlock * > &  Blocks, LoopInfo *  LI  )

static

Check if unrolling created a situation where we need to insert phi nodes to preserve LCSSA form.

Parameters

Blocks	is a vector of basic blocks representing unrolled loop.
L	is the outer loop. It's possible that some of the blocks are in L, and some are not. In this case, if there is a use is outside L, and definition is inside L, we need to insert a phi-node, otherwise LCSSA will be broken. The function is just a helper function for llvm::UnrollLoop that returns true if this situation occurs, indicating that LCSSA needs to be fixed.

Definition at line 123 of file LoopUnroll.cpp.

References Blocks, llvm::LoopBase< BlockT, LoopT >::contains(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), and I.

Referenced by llvm::UnrollLoop().

STATISTIC() [1/3]

STATISTIC	(	NumCompletelyUnrolled	,
		"Number of loops completely unrolled"
	)

STATISTIC() [2/3]

STATISTIC	(	NumUnrolled	,
		"Number of loops unrolled (completely or otherwise)"
	)

STATISTIC() [3/3]

STATISTIC	(	NumUnrolledNotLatch	,
		"Number of loops unrolled without a conditional " "latch (completely or otherwise)"
	)

Variable Documentation

UnrollRuntimeEpilog

cl::opt< bool > UnrollRuntimeEpilog("unroll-runtime-epilog", cl::init(false), cl::Hidden, cl::desc("Allow runtime unrolled loops to be unrolled " "with epilog instead of prolog.")) ( "unroll-runtime-epilog"  , cl::init(false)  , cl::Hidden  , cl::desc("Allow runtime unrolled loops to be unrolled " "with epilog instead of prolog.")    )

static

Referenced by llvm::UnrollLoop().

UnrollVerifyDomtree

cl::opt< bool > UnrollVerifyDomtree("unroll-verify-domtree", cl::Hidden, cl::desc("Verify domtree after unrolling"), cl::init(false)) ( "unroll-verify-domtree"  , cl::Hidden  , cl::desc("Verify domtree after unrolling")  , cl::init(false)    )

static

Referenced by llvm::UnrollLoop().

UnrollVerifyLoopInfo

cl::opt< bool > UnrollVerifyLoopInfo("unroll-verify-loopinfo", cl::Hidden, cl::desc("Verify loopinfo after unrolling"), cl::init(false)) ( "unroll-verify-loopinfo"  , cl::Hidden  , cl::desc("Verify loopinfo after unrolling")  , cl::init(false)    )

static

Referenced by llvm::UnrollLoop().