#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"

Include dependency graph for ScalarEvolutionExpander.cpp:

Namespaces
	llvm
	This class represents lattice values for constants.

Functions
static BasicBlock::iterator	findInsertPointAfter (Instruction I, BasicBlock MustDominate)

static bool	FactorOutConstant (const SCEV &S, const SCEV &Remainder, const SCEV *Factor, ScalarEvolution &SE, const DataLayout &DL)
	FactorOutConstant - Test if S is divisible by Factor, using signed division. More...

static void	SimplifyAddOperands (SmallVectorImpl< const SCEV > &Ops, Type Ty, ScalarEvolution &SE)
	SimplifyAddOperands - Sort and simplify a list of add operands. More...

static void	SplitAddRecs (SmallVectorImpl< const SCEV > &Ops, Type Ty, ScalarEvolution &SE)
	SplitAddRecs - Flatten a list of add operands, moving addrec start values out to the top level. More...

static const Loop *	PickMostRelevantLoop (const Loop A, const Loop B, DominatorTree &DT)
	PickMostRelevantLoop - Given two loops pick the one that's most relevant for SCEV expansion. More...

static void	ExposePointerBase (const SCEV &Base, const SCEV &Rest, ScalarEvolution &SE)
	Move parts of Base into Rest to leave Base with the minimal expression that provides a pointer operand suitable for a GEP expansion. More...

static bool	canBeCheaplyTransformed (ScalarEvolution &SE, const SCEVAddRecExpr Phi, const SCEVAddRecExpr Requested, bool &InvertStep)
	Check whether we can cheaply express the requested SCEV in terms of the available PHI SCEV by truncation and/or inversion of the step. More...

static bool	IsIncrementNSW (ScalarEvolution &SE, const SCEVAddRecExpr *AR)

static bool	IsIncrementNUW (ScalarEvolution &SE, const SCEVAddRecExpr *AR)

bool	llvm::isSafeToExpand (const SCEV *S, ScalarEvolution &SE)
	Return true if the given expression is safe to expand in the sense that all materialized values are safe to speculate anywhere their operands are defined. More...

bool	llvm::isSafeToExpandAt (const SCEV S, const Instruction InsertionPoint, ScalarEvolution &SE)
	Return true if the given expression is safe to expand in the sense that all materialized values are defined and safe to speculate at the specified location and their operands are defined at this location. More...

Function Documentation

◆ canBeCheaplyTransformed()

static bool canBeCheaplyTransformed	(	ScalarEvolution &	SE,
		const SCEVAddRecExpr *	Phi,
		const SCEVAddRecExpr *	Requested,
		bool &	InvertStep
	)

static

Check whether we can cheaply express the requested SCEV in terms of the available PHI SCEV by truncation and/or inversion of the step.

Definition at line 1077 of file ScalarEvolutionExpander.cpp.

References llvm::dyn_cast(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getEffectiveSCEVType(), llvm::Type::getIntegerBitWidth(), llvm::ScalarEvolution::getNegativeSCEV(), llvm::SCEVAddRecExpr::getStart(), llvm::ScalarEvolution::getTruncateOrNoop(), and llvm::SCEVNAryExpr::getType().

Referenced by IsIncrementNUW().

◆ ExposePointerBase()

static void ExposePointerBase	(	const SCEV *&	Base,
		const SCEV *&	Rest,
		ScalarEvolution &	SE
	)

static

Move parts of Base into Rest to leave Base with the minimal expression that provides a pointer operand suitable for a GEP expansion.

Definition at line 856 of file ScalarEvolutionExpander.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::back(), llvm::dyn_cast(), llvm::SCEV::FlagNW, llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getAddRecExpr(), llvm::ScalarEvolution::getConstant(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::Instruction::mayHaveSideEffects(), llvm::User::op_begin(), and llvm::User::op_end().

◆ FactorOutConstant()

static bool FactorOutConstant	(	const SCEV *&	S,
		const SCEV *&	Remainder,
		const SCEV *	Factor,
		ScalarEvolution &	SE,
		const DataLayout &	DL
	)

static

FactorOutConstant - Test if S is divisible by Factor, using signed division.

If so, update S with Factor divided out and return true. S need not be evenly divisible if a reasonable remainder can be computed. TODO: When ScalarEvolution gets a SCEVSDivExpr, this can be made unnecessary; in its place, just signed-divide Ops[i] by the scale and check to see if the divide was folded.

Definition at line 239 of file ScalarEvolutionExpander.cpp.

References C, R600_InstFlag::FC, llvm::ConstantInt::get(), llvm::ScalarEvolution::getAddExpr(), llvm::SCEVConstant::getAPInt(), llvm::ScalarEvolution::getConstant(), llvm::ScalarEvolution::getContext(), llvm::ScalarEvolution::getMulExpr(), llvm::SCEV::getType(), llvm::SCEV::isOne(), llvm::SCEV::isZero(), and llvm::ConstantInt::isZero().

◆ findInsertPointAfter()

static BasicBlock::iterator findInsertPointAfter	(	Instruction *	I,
		BasicBlock *	MustDominate
	)

static

Definition at line 89 of file ScalarEvolutionExpander.cpp.

References assert(), C, llvm::ConstantExpr::get(), llvm::ConstantExpr::getCast(), llvm::CastInst::getCastOpcode(), llvm::BasicBlock::getFirstInsertionPt(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), I, and llvm::Instruction::setDebugLoc().

◆ IsIncrementNSW()

static bool IsIncrementNSW	(	ScalarEvolution &	SE,
		const SCEVAddRecExpr *	AR
	)

static

Definition at line 1108 of file ScalarEvolutionExpander.cpp.

References llvm::IntegerType::get(), llvm::ScalarEvolution::getAddExpr(), getBitWidth(), llvm::Type::getContext(), llvm::ScalarEvolution::getSignExtendExpr(), llvm::SCEVAddRecExpr::getStepRecurrence(), and llvm::SCEVNAryExpr::getType().

Referenced by IsIncrementNUW().

◆ IsIncrementNUW()

static bool IsIncrementNUW	(	ScalarEvolution &	SE,
		const SCEVAddRecExpr *	AR
	)

static

Definition at line 1122 of file ScalarEvolutionExpander.cpp.

References llvm::PHINode::addIncoming(), assert(), llvm::BasicBlock::begin(), canBeCheaplyTransformed(), llvm::SmallPtrSetImplBase::clear(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::dyn_cast(), llvm::BasicBlock::front(), llvm::IntegerType::get(), llvm::ScalarEvolution::getAddExpr(), getBitWidth(), llvm::Type::getContext(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingValueForBlock(), llvm::SCEVAddRecExpr::getLoop(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::BasicBlock::getTerminator(), llvm::SCEVNAryExpr::getType(), llvm::Value::getType(), llvm::ScalarEvolution::getZeroExtendExpr(), llvm::SmallPtrSetImpl< PtrType >::insert(), IsIncrementNSW(), llvm::SCEV::isNonConstantNegative(), llvm::Type::isPointerTy(), Loops, llvm::normalizeForPostIncUse(), llvm::BasicBlock::phis(), llvm::pred_begin(), and llvm::pred_end().

◆ PickMostRelevantLoop()

static const Loop* PickMostRelevantLoop	(	const Loop *	A,
		const Loop *	B,
		DominatorTree &	DT
	)

static

PickMostRelevantLoop - Given two loops pick the one that's most relevant for SCEV expansion.

If they are nested, this is the most nested. If they are neighboring, pick the later.

Definition at line 601 of file ScalarEvolutionExpander.cpp.

References llvm::MCID::Add, assert(), B, llvm::SmallVectorTemplateCommon< T >::begin(), C, llvm::LoopBase< BlockT, LoopT >::contains(), D, llvm::DominatorTree::dominates(), E, llvm::SmallVectorTemplateCommon< T >::end(), expand(), llvm::Exponent, llvm::ConstantInt::get(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::SCEVUDivExpr::getLHS(), llvm::Constant::getNullValue(), llvm::User::getOperand(), llvm::SCEVUDivExpr::getRHS(), llvm::SCEV::getType(), llvm::SCEVNAryExpr::getType(), llvm::SCEVAddExpr::getType(), llvm::SCEVUDivExpr::getType(), I, llvm::SCEV::isNonConstantNegative(), llvm::APInt::isPowerOf2(), llvm::Type::isVectorTy(), llvm_unreachable, llvm::APInt::logBase2(), llvm::PatternMatch::m_Power2(), llvm::PatternMatch::match(), N, llvm::SCEVNAryExpr::op_begin(), llvm::SCEVNAryExpr::op_end(), P, llvm::SmallVectorTemplateBase< T >::push_back(), llvm::PPCISD::SC, std::swap(), UINT64_MAX, llvm::RISCVFenceField::W, and X.

◆ SimplifyAddOperands()

static void SimplifyAddOperands	(	SmallVectorImpl< const SCEV *> &	Ops,
		Type *	Ty,
		ScalarEvolution &	SE
	)

static

SimplifyAddOperands - Sort and simplify a list of add operands.

NumAddRecs is the number of SCEVAddRecExprs present, which are kept at the end of the list.

Definition at line 312 of file ScalarEvolutionExpander.cpp.

References llvm::MCID::Add, llvm::SmallVectorImpl< T >::append(), llvm::SmallVectorTemplateCommon< T >::begin(), llvm::SmallVectorImpl< T >::clear(), llvm::SmallVectorTemplateCommon< T >::end(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getConstant(), llvm::SmallVectorTemplateBase< T >::push_back(), and llvm::SmallVectorBase::size().

◆ SplitAddRecs()

static void SplitAddRecs	(	SmallVectorImpl< const SCEV *> &	Ops,
		Type *	Ty,
		ScalarEvolution &	SE
	)

static

SplitAddRecs - Flatten a list of add operands, moving addrec start values out to the top level.

For example, convert {a + b,+,c} to a, b, {0,+,d}. This helps expose more opportunities for folding parts of the expressions into GEP indices.

Definition at line 341 of file ScalarEvolutionExpander.cpp.

References llvm::SmallVectorBase::size().

Namespaces

Functions

Function Documentation

◆ canBeCheaplyTransformed()

◆ ExposePointerBase()

◆ FactorOutConstant()

◆ findInsertPointAfter()

◆ IsIncrementNSW()

◆ IsIncrementNUW()

◆ PickMostRelevantLoop()

◆ SimplifyAddOperands()

◆ SplitAddRecs()