LoopUnroll.cpp File Reference

#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.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/ADT/ilist_iterator.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/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/Module.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/MathExtras.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/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.

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.

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 79 of file LoopUnroll.cpp.

Function Documentation

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 201 of file LoopUnroll.cpp.

References assert().

Referenced by llvm::UnrollLoop().

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