LoopUnrollPeel.cpp File Reference

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/BasicBlock.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/LLVMContext.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/LoopSimplify.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/UnrollLoop.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>

Include dependency graph for LoopUnrollPeel.cpp:

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "loop-unroll"

Functions
	STATISTIC (NumPeeled, "Number of loops peeled")
static unsigned	calculateIterationsToInvariance (PHINode *Phi, Loop *L, BasicBlock *BackEdge, SmallDenseMap< PHINode *, unsigned > &IterationsToInvariance)
static unsigned	countToEliminateCompares (Loop &L, unsigned MaxPeelCount, ScalarEvolution &SE)
static void	updateBranchWeights (BasicBlock *Header, BranchInst *LatchBR, unsigned IterNumber, unsigned AvgIters, uint64_t &PeeledHeaderWeight)
	Update the branch weights of the latch of a peeled-off loop iteration. More...
static void	cloneLoopBlocks (Loop *L, unsigned IterNumber, BasicBlock *InsertTop, BasicBlock *InsertBot, BasicBlock *Exit, SmallVectorImpl< BasicBlock *> &NewBlocks, LoopBlocksDFS &LoopBlocks, ValueToValueMapTy &VMap, ValueToValueMapTy &LVMap, DominatorTree *DT, LoopInfo *LI)
	Clones the body of the loop L, putting it between InsertTop and InsertBot. More...

Variables
static cl::opt< unsigned >	UnrollPeelMaxCount ("unroll-peel-max-count", cl::init(7), cl::Hidden, cl::desc("Max average trip count which will cause loop peeling."))
static cl::opt< unsigned >	UnrollForcePeelCount ("unroll-force-peel-count", cl::init(0), cl::Hidden, cl::desc("Force a peel count regardless of profiling information."))
static const unsigned	InfiniteIterationsToInvariance

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "loop-unroll"

Definition at line 53 of file LoopUnrollPeel.cpp.

Function Documentation

calculateIterationsToInvariance()

static unsigned calculateIterationsToInvariance ( PHINode *  Phi, Loop *  L, BasicBlock *  BackEdge, SmallDenseMap< PHINode *, unsigned > &  IterationsToInvariance  )

static

Definition at line 104 of file LoopUnrollPeel.cpp.

References assert(), llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingValueForBlock(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::Instruction::getParent(), I, InfiniteIterationsToInvariance, and llvm::Loop::isLoopInvariant().

Referenced by llvm::computePeelCount().

cloneLoopBlocks()

static void cloneLoopBlocks ( Loop *  L, unsigned  IterNumber, BasicBlock *  InsertTop, BasicBlock *  InsertBot, BasicBlock *  Exit, SmallVectorImpl< BasicBlock *> &  NewBlocks, LoopBlocksDFS &  LoopBlocks, ValueToValueMapTy &  VMap, ValueToValueMapTy &  LVMap, DominatorTree *  DT, LoopInfo *  LI  )

static

Clones the body of the loop L, putting it between InsertTop and InsertBot.

Parameters

	IterNumber	The serial number of the iteration currently being peeled off.
	Exit	The exit block of the original loop.
[out]	NewBlocks	A list of the blocks in the newly created clone
[out]	VMap	The value map between the loop and the new clone.
	LoopBlocks	A helper for DFS-traversal of the loop.
	LVMap	A value-map that maps instructions from the original loop to instructions in the last peeled-off iteration.

Definition at line 395 of file LoopUnrollPeel.cpp.

References llvm::LoopBase< BlockT, LoopT >::addBasicBlockToLoop(), llvm::PHINode::addIncoming(), llvm::DominatorTreeBase< NodeT, IsPostDom >::addNewBlock(), llvm::BasicBlock::begin(), llvm::LoopBlocksDFS::beginRPO(), llvm::DominatorTreeBase< NodeT, IsPostDom >::changeImmediateDominator(), llvm::CloneBasicBlock(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::dyn_cast(), llvm::LoopBlocksDFS::endRPO(), F(), llvm::DomTreeNodeBase< NodeT >::getBlock(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::DomTreeNodeBase< NodeT >::getIDom(), llvm::PHINode::getIncomingValueForBlock(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::BasicBlock::getParent(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::BasicBlock::getTerminator(), I, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::Instruction::setSuccessor(), and llvm::BranchInst::setSuccessor().

Referenced by llvm::peelLoop().

countToEliminateCompares()

static unsigned countToEliminateCompares ( Loop &  L, unsigned  MaxPeelCount, ScalarEvolution &  SE  )

static

Definition at line 151 of file LoopUnrollPeel.cpp.

References assert(), llvm::LoopBase< BlockT, LoopT >::blocks(), llvm::dyn_cast(), llvm::SCEVAddRecExpr::evaluateAtIteration(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getConstant(), llvm::CmpInst::getInversePredicate(), llvm::SCEVAddRecExpr::getLoop(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::ScalarEvolution::getSCEV(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::CmpInst::getSwappedPredicate(), llvm::SCEV::getType(), llvm::SCEVAddRecExpr::isAffine(), llvm::ScalarEvolution::isKnownPredicate(), llvm::Loop::isLoopSimplifyForm(), llvm::ScalarEvolution::isMonotonicPredicate(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and std::swap().

Referenced by llvm::computePeelCount().

STATISTIC()

STATISTIC	(	NumPeeled	,
		"Number of loops peeled"
	)

updateBranchWeights()

static void updateBranchWeights ( BasicBlock *  Header, BranchInst *  LatchBR, unsigned  IterNumber, unsigned  AvgIters, uint64_t &  PeeledHeaderWeight  )

static

Update the branch weights of the latch of a peeled-off loop iteration.

This sets the branch weights for the latch of the recently peeled off loop iteration correctly. Our goal is to make sure that: a) The total weight of all the copies of the loop body is preserved. b) The total weight of the loop exit is preserved. c) The body weight is reasonably distributed between the peeled iterations.

Parameters

	Header	The copy of the header block that belongs to next iteration.
	LatchBR	The copy of the latch branch that belongs to this iteration.
	IterNumber	The serial number of the iteration that was just peeled off.
	AvgIters	The average number of iterations we expect the loop to have.
[in,out]	PeeledHeaderWeight	The total number of dynamic loop iterations that are unaccounted for. As an input, it represents the number of times we expect to enter the header of the iteration currently being peeled off. The output is the number of times we expect to enter the header of the next iteration.

Definition at line 363 of file LoopUnrollPeel.cpp.

References llvm::Value::getContext(), llvm::BranchInst::getSuccessor(), llvm::LLVMContext::MD_prof, and llvm::Instruction::setMetadata().

Referenced by llvm::peelLoop().

Variable Documentation

InfiniteIterationsToInvariance

const unsigned InfiniteIterationsToInvariance

static

Initial value:

=
    std::numeric_limits<unsigned>::max()

Definition at line 68 of file LoopUnrollPeel.cpp.

Referenced by calculateIterationsToInvariance().

UnrollForcePeelCount

cl::opt<unsigned> UnrollForcePeelCount("unroll-force-peel-count", cl::init(0), cl::Hidden, cl::desc("Force a peel count regardless of profiling information."))

static

Referenced by llvm::computePeelCount().

UnrollPeelMaxCount

cl::opt<unsigned> UnrollPeelMaxCount("unroll-peel-max-count", cl::init(7), cl::Hidden, cl::desc("Max average trip count which will cause loop peeling."))

static

Referenced by llvm::computePeelCount().