LoopPeel.cpp File Reference

#include "llvm/Transforms/Utils/LoopPeel.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ScalarEvolutionPatternMatch.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/PatternMatch.h"
#include "llvm/IR/ProfDataUtils.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/ScalarEvolutionExpander.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <optional>

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "loop-peel"

Functions
	STATISTIC (NumPeeled, "Number of loops peeled")
	STATISTIC (NumPeeledEnd, "Number of loops peeled from end")
static unsigned	peelToTurnInvariantLoadsDerefencebale (Loop &L, DominatorTree &DT, AssumptionCache *AC)
static bool	shouldPeelLastIteration (Loop &L, CmpPredicate Pred, const SCEVAddRecExpr *LeftAR, const SCEV *RightSCEV, ScalarEvolution &SE, const TargetTransformInfo &TTI)
	Returns true if the last iteration can be peeled off and the condition (Pred LeftAR, RightSCEV) is known at the last iteration and the inverse condition is known at the second-to-last.
static std::pair< unsigned, unsigned >	countToEliminateCompares (Loop &L, unsigned MaxPeelCount, ScalarEvolution &SE, const TargetTransformInfo &TTI)
static bool	violatesLegacyMultiExitLoopCheck (Loop *L)
	This "heuristic" exactly matches implicit behavior which used to exist inside getLoopEstimatedTripCount.
static void	cloneLoopBlocks (Loop *L, unsigned IterNumber, bool PeelLast, BasicBlock *InsertTop, BasicBlock *InsertBot, BasicBlock *OrigPreHeader, SmallVectorImpl< std::pair< BasicBlock *, BasicBlock * > > &ExitEdges, SmallVectorImpl< BasicBlock * > &NewBlocks, LoopBlocksDFS &LoopBlocks, ValueToValueMapTy &VMap, ValueToValueMapTy &LVMap, DominatorTree *DT, LoopInfo *LI, ArrayRef< MDNode * > LoopLocalNoAliasDeclScopes, ScalarEvolution &SE)
	Clones the body of the loop L, putting it between InsertTop and InsertBot.

Variables
static cl::opt< unsigned >	UnrollPeelCount ("unroll-peel-count", cl::Hidden, cl::desc("Set the unroll peeling count, for testing purposes"))
static cl::opt< bool >	UnrollAllowPeeling ("unroll-allow-peeling", cl::init(true), cl::Hidden, cl::desc("Allows loops to be peeled when the dynamic " "trip count is known to be low."))
static cl::opt< bool >	UnrollAllowLoopNestsPeeling ("unroll-allow-loop-nests-peeling", cl::init(false), cl::Hidden, cl::desc("Allows loop nests to be peeled."))
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 cl::opt< bool >	DisableAdvancedPeeling ("disable-advanced-peeling", cl::init(false), cl::Hidden, cl::desc("Disable advance peeling. Issues for convergent targets (D134803)."))
static cl::opt< bool >	EnablePeelingForIV ("enable-peeling-for-iv", cl::init(false), cl::Hidden, cl::desc("Enable peeling to convert Phi nodes into IVs"))
static const char *	PeeledCountMetaData = "llvm.loop.peeled.count"

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "loop-peel"

Definition at line 52 of file LoopPeel.cpp.

Function Documentation

cloneLoopBlocks()

void cloneLoopBlocks ( Loop * L, unsigned IterNumber, bool PeelLast, BasicBlock * InsertTop, BasicBlock * InsertBot, BasicBlock * OrigPreHeader, SmallVectorImpl< std::pair< BasicBlock *, BasicBlock * > > & ExitEdges, SmallVectorImpl< BasicBlock * > & NewBlocks, LoopBlocksDFS & LoopBlocks, ValueToValueMapTy & VMap, ValueToValueMapTy & LVMap, DominatorTree * DT, LoopInfo * LI, ArrayRef< MDNode * > LoopLocalNoAliasDeclScopes, ScalarEvolution & SE )

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.
	PeelLast	Peel off the last iterations from L.
	ExitEdges	The exit edges 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 897 of file LoopPeel.cpp.

References llvm::LoopBase< BlockT, LoopT >::addBasicBlockToLoop(), llvm::PHINode::addIncoming(), llvm::DominatorTreeBase< NodeT, IsPostDom >::addNewBlock(), assert(), B(), llvm::cast(), llvm::DominatorTreeBase< NodeT, IsPostDom >::changeImmediateDominator(), llvm::cloneAndAdaptNoAliasScopes(), llvm::CloneBasicBlock(), llvm::cloneLoop(), llvm::dyn_cast(), llvm::Instruction::eraseFromParent(), F, llvm::ScalarEvolution::forgetLcssaPhiWithNewPredecessor(), llvm::DomTreeNodeBase< NodeT >::getBlock(), llvm::BasicBlock::getFirstNonPHIIt(), llvm::DomTreeNodeBase< NodeT >::getIDom(), llvm::PHINode::getIncomingValueForBlock(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), I, llvm::isa(), PHI, llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::Instruction::setSuccessor().

Referenced by llvm::peelLoop().

countToEliminateCompares()

std::pair< unsigned, unsigned > countToEliminateCompares ( Loop & L, unsigned MaxPeelCount, ScalarEvolution & SE, const TargetTransformInfo & TTI )

static

Definition at line 541 of file LoopPeel.cpp.

References assert(), llvm::cast(), llvm::Depth, llvm::dyn_cast(), llvm::SCEVAddRecExpr::evaluateAtIteration(), llvm::ScalarEvolution::evaluatePredicate(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getConstant(), llvm::ScalarEvolution::getConstantMaxBackedgeTakenCount(), llvm::CmpInst::getInversePredicate(), llvm::SCEVAddRecExpr::getLoop(), llvm::ScalarEvolution::getMonotonicPredicateType(), llvm::ScalarEvolution::getSCEV(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::CmpInst::getSwappedPredicate(), llvm::SCEV::getType(), llvm::Value::getType(), llvm::SCEVNAryExpr::hasNoSelfWrap(), I, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLT, llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULT, llvm::isa(), llvm::SCEVAddRecExpr::isAffine(), llvm::ICmpInst::isEquality(), llvm::Type::isIntegerTy(), llvm::ScalarEvolution::isKnownNegative(), llvm::ScalarEvolution::isKnownPositive(), llvm::ScalarEvolution::isKnownPredicate(), LHS, llvm::PatternMatch::m_And(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_Or(), llvm::PatternMatch::m_Value(), llvm::SCEVPatternMatch::match(), RHS, shouldPeelLastIteration(), and std::swap().

Referenced by llvm::computePeelCount().

peelToTurnInvariantLoadsDerefencebale()

unsigned peelToTurnInvariantLoadsDerefencebale ( Loop & L, DominatorTree & DT, AssumptionCache * AC )

static

Definition at line 418 of file LoopPeel.cpp.

References llvm::any_of(), llvm::SmallPtrSetImpl< PtrType >::contains(), DL, llvm::DominatorTree::dominates(), llvm::dyn_cast(), llvm::BasicBlock::getTerminator(), I, llvm::SmallPtrSetImpl< PtrType >::insert_range(), llvm::isa(), llvm::isDereferenceablePointer(), and Ptr.

Referenced by llvm::computePeelCount().

shouldPeelLastIteration()

bool shouldPeelLastIteration ( Loop & L, CmpPredicate Pred, const SCEVAddRecExpr * LeftAR, const SCEV * RightSCEV, ScalarEvolution & SE, const TargetTransformInfo & TTI )

static

Returns true if the last iteration can be peeled off and the condition (Pred LeftAR, RightSCEV) is known at the last iteration and the inverse condition is known at the second-to-last.

Definition at line 503 of file LoopPeel.cpp.

References llvm::ScalarEvolution::applyLoopGuards(), llvm::canPeelLastIteration(), llvm::ScalarEvolution::LoopGuards::collect(), llvm::SCEVAddRecExpr::evaluateAtIteration(), llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::CmpInst::getInversePredicate(), llvm::ScalarEvolution::getMinusSCEV(), llvm::ScalarEvolution::getOne(), llvm::SCEV::getType(), llvm::SCEVExpander::isHighCostExpansion(), llvm::ScalarEvolution::isKnownNonZero(), llvm::ScalarEvolution::isKnownPredicate(), and llvm::SCEVCheapExpansionBudget.

Referenced by countToEliminateCompares().

STATISTIC() [1/2]

STATISTIC	(	NumPeeled	,
		"Number of loops peeled"	)

STATISTIC() [2/2]

STATISTIC	(	NumPeeledEnd	,
		"Number of loops peeled from end"	)

violatesLegacyMultiExitLoopCheck()

bool violatesLegacyMultiExitLoopCheck ( Loop * L )

static

This "heuristic" exactly matches implicit behavior which used to exist inside getLoopEstimatedTripCount.

It was added here to keep an improvement inside that API from causing peeling to become more aggressive. This should probably be removed.

Definition at line 722 of file LoopPeel.cpp.

References llvm::any_of(), assert(), llvm::dyn_cast(), llvm::BranchInst::getNumSuccessors(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminatingDeoptimizeCall(), and llvm::BasicBlock::getTerminator().

Referenced by llvm::computePeelCount().

Variable Documentation

DisableAdvancedPeeling

cl::opt< bool > DisableAdvancedPeeling("disable-advanced-peeling", cl::init(false), cl::Hidden, cl::desc( "Disable advance peeling. Issues for convergent targets (D134803).")) ( "disable-advanced-peeling" , cl::init(false) , cl::Hidden , cl::desc( "Disable advance peeling. Issues for convergent targets (D134803).")  )

static

Referenced by llvm::canPeel().

EnablePeelingForIV

cl::opt< bool > EnablePeelingForIV("enable-peeling-for-iv", cl::init(false), cl::Hidden, cl::desc("Enable peeling to convert Phi nodes into IVs")) ( "enable-peeling-for-iv" , cl::init(false) , cl::Hidden , cl::desc("Enable peeling to convert Phi nodes into IVs")  )

static

Referenced by llvm::computePeelCount().

PeeledCountMetaData

const char* PeeledCountMetaData = "llvm.loop.peeled.count"

static

Definition at line 88 of file LoopPeel.cpp.

Referenced by llvm::computePeelCount(), and llvm::peelLoop().

UnrollAllowLoopNestsPeeling

cl::opt< bool > UnrollAllowLoopNestsPeeling("unroll-allow-loop-nests-peeling", cl::init(false), cl::Hidden, cl::desc("Allows loop nests to be peeled.")) ( "unroll-allow-loop-nests-peeling" , cl::init(false) , cl::Hidden , cl::desc("Allows loop nests to be peeled.")  )

static

Referenced by llvm::gatherPeelingPreferences().

UnrollAllowPeeling

cl::opt< bool > UnrollAllowPeeling("unroll-allow-peeling", cl::init(true), cl::Hidden, cl::desc("Allows loops to be peeled when the dynamic " "trip count is known to be low.")) ( "unroll-allow-peeling" , cl::init(true) , cl::Hidden , cl::desc("Allows loops to be peeled when the dynamic " "trip count is known to be low.")  )

static

Referenced by llvm::gatherPeelingPreferences().

UnrollForcePeelCount

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

static

Referenced by llvm::computePeelCount().

UnrollPeelCount

cl::opt< unsigned > UnrollPeelCount("unroll-peel-count", cl::Hidden, cl::desc("Set the unroll peeling count, for testing purposes")) ( "unroll-peel-count" , cl::Hidden , cl::desc("Set the unroll peeling count, for testing purposes")  )

static

Referenced by llvm::gatherPeelingPreferences().

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