#include "llvm/Transforms/Scalar.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallBitVector.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/IVUsers.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ValueHandle.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include <algorithm>

Include dependency graph for LoopStrengthReduce.cpp:

Macros
#define	DEBUG_TYPE "loop-reduce"

Functions
static void	DoInitialMatch (const SCEV S, Loop L, SmallVectorImpl< const SCEV * > &Good, SmallVectorImpl< const SCEV * > &Bad, ScalarEvolution &SE)
	DoInitialMatch - Recursion helper for InitialMatch. More...

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

static bool	isAddSExtable (const SCEVAddExpr *A, ScalarEvolution &SE)

static bool	isMulSExtable (const SCEVMulExpr *M, ScalarEvolution &SE)

static const SCEV *	getExactSDiv (const SCEV LHS, const SCEV RHS, ScalarEvolution &SE, bool IgnoreSignificantBits=false)

static int64_t	ExtractImmediate (const SCEV *&S, ScalarEvolution &SE)

static GlobalValue *	ExtractSymbol (const SCEV *&S, ScalarEvolution &SE)

static bool	isAddressUse (Instruction Inst, Value OperandVal)

static Type *	getAccessType (const Instruction *Inst)
	getAccessType - Return the type of the memory being accessed. More...

static bool	isExistingPhi (const SCEVAddRecExpr *AR, ScalarEvolution &SE)
	isExistingPhi - Return true if this AddRec is already a phi in its loop. More...

static bool	isHighCostExpansion (const SCEV S, SmallPtrSet< const SCEV , 8 > &Processed, ScalarEvolution &SE)

static bool	DeleteTriviallyDeadInstructions (SmallVectorImpl< WeakVH > &DeadInsts)

static bool	isLegal2RegAMUse (const TargetTransformInfo &TTI, const LSRUse &LU, const Formula &F)

static unsigned	getScalingFactorCost (const TargetTransformInfo &TTI, const LSRUse &LU, const Formula &F)

static bool	isLegalUse (const TargetTransformInfo &TTI, LSRUse::KindType Kind, Type AccessTy, GlobalValue BaseGV, int64_t BaseOffset, bool HasBaseReg, int64_t Scale)

static bool	isLegalUse (const TargetTransformInfo &TTI, int64_t MinOffset, int64_t MaxOffset, LSRUse::KindType Kind, Type AccessTy, GlobalValue BaseGV, int64_t BaseOffset, bool HasBaseReg, int64_t Scale)

static bool	isLegalUse (const TargetTransformInfo &TTI, int64_t MinOffset, int64_t MaxOffset, LSRUse::KindType Kind, Type *AccessTy, const Formula &F)

static bool	isAlwaysFoldable (const TargetTransformInfo &TTI, LSRUse::KindType Kind, Type AccessTy, GlobalValue BaseGV, int64_t BaseOffset, bool HasBaseReg)

static bool	isAlwaysFoldable (const TargetTransformInfo &TTI, ScalarEvolution &SE, int64_t MinOffset, int64_t MaxOffset, LSRUse::KindType Kind, Type AccessTy, const SCEV S, bool HasBaseReg)

static User::op_iterator	findIVOperand (User::op_iterator OI, User::op_iterator OE, Loop *L, ScalarEvolution &SE)

static Value *	getWideOperand (Value *Oper)

static bool	isCompatibleIVType (Value LVal, Value RVal)

static const SCEV *	getExprBase (const SCEV *S)

static bool	isProfitableChain (IVChain &Chain, SmallPtrSet< Instruction *, 4 > &Users, ScalarEvolution &SE, const TargetTransformInfo &TTI)

static bool	canFoldIVIncExpr (const SCEV IncExpr, Instruction UserInst, Value *Operand, const TargetTransformInfo &TTI)
	Return true if the IVInc can be folded into an addressing mode. More...

static const SCEV *	CollectSubexprs (const SCEV S, const SCEVConstant C, SmallVectorImpl< const SCEV * > &Ops, const Loop *L, ScalarEvolution &SE, unsigned Depth=0)

	INITIALIZE_PASS_BEGIN (LoopStrengthReduce,"loop-reduce","Loop Strength Reduction", false, false) INITIALIZE_PASS_END(LoopStrengthReduce

Variables
static const unsigned	MaxIVUsers = 200

static cl::opt< bool >	EnablePhiElim ("enable-lsr-phielim", cl::Hidden, cl::init(true), cl::desc("Enable LSR phi elimination"))

static cl::opt< bool >	StressIVChain ("stress-ivchain", cl::Hidden, cl::init(false), cl::desc("Stress test LSR IV chains"))

static const size_t	ComplexityLimit = UINT16_MAX

loop	reduce

loop Loop Strength	Reduction

loop Loop Strength	false

Macro Definition Documentation

#define DEBUG_TYPE "loop-reduce"

Definition at line 56 of file LoopStrengthReduce.cpp.

Function Documentation

static bool canFoldIVIncExpr	(	const SCEV *	IncExpr,
		Instruction *	UserInst,
		Value *	Operand,
		const TargetTransformInfo &	TTI
	)

static

Return true if the IVInc can be folded into an addressing mode.

Definition at line 2787 of file LoopStrengthReduce.cpp.

References llvm::dyn_cast(), getAccessType(), llvm::APInt::getMinSignedBits(), llvm::ConstantInt::getSExtValue(), llvm::SCEVConstant::getValue(), llvm::ConstantInt::getValue(), isAddressUse(), and isAlwaysFoldable().

static const SCEV* CollectSubexprs	(	const SCEV *	S,
		const SCEVConstant *	C,
		SmallVectorImpl< const SCEV * > &	Ops,
		const Loop *	L,
		ScalarEvolution &	SE,
		unsigned	Depth = `0`
	)

static

CollectSubexprs - Split S into subexpressions which can be pulled out into separate registers. If C is non-null, multiply each subexpression by C.

Return remainder expression after factoring the subexpressions captured by Ops. If Ops is complete, return NULL.

Definition at line 3134 of file LoopStrengthReduce.cpp.

References llvm::CallingConv::C, llvm::SCEVAddRecExpr::getLoop(), llvm::ScalarEvolution::getMulExpr(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::SCEVNAryExpr::getType(), I, llvm::SCEV::isZero(), and llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back().

static bool DeleteTriviallyDeadInstructions ( SmallVectorImpl< WeakVH > & DeadInsts )

static

DeleteTriviallyDeadInstructions - If any of the instructions is the specified set are trivially dead, delete them and see if this makes any of their operands subsequently dead.

Definition at line 752 of file LoopStrengthReduce.cpp.

References llvm::SmallVectorBase::empty(), llvm::Instruction::eraseFromParent(), llvm::isInstructionTriviallyDead(), llvm::User::op_begin(), llvm::User::op_end(), llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back().

static void DoInitialMatch	(	const SCEV *	S,
		Loop *	L,
		SmallVectorImpl< const SCEV * > &	Good,
		SmallVectorImpl< const SCEV * > &	Bad,
		ScalarEvolution &	SE
	)

static

DoInitialMatch - Recursion helper for InitialMatch.

Definition at line 274 of file LoopStrengthReduce.cpp.

References llvm::SmallVectorTemplateCommon< T >::begin(), llvm::SmallVectorTemplateCommon< T >::end(), llvm::SCEV::FlagAnyWrap, llvm::ScalarEvolution::getAddRecExpr(), llvm::Constant::getAllOnesValue(), llvm::ScalarEvolution::getConstant(), llvm::ScalarEvolution::getEffectiveSCEVType(), llvm::LoopBase< N, M >::getHeader(), llvm::ScalarEvolution::getMulExpr(), llvm::ScalarEvolution::getSCEV(), I, llvm::ScalarEvolution::properlyDominates(), and llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back().

static int64_t ExtractImmediate	(	const SCEV *&	S,
		ScalarEvolution &	SE
	)

static

ExtractImmediate - If S involves the addition of a constant integer value, return that integer value, and mutate S to point to a new SCEV with that value excluded.

Definition at line 559 of file LoopStrengthReduce.cpp.

References llvm::CallingConv::C, llvm::SCEV::FlagAnyWrap, llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getAddRecExpr(), and llvm::ScalarEvolution::getConstant().

Referenced by isAlwaysFoldable().

static GlobalValue* ExtractSymbol	(	const SCEV *&	S,
		ScalarEvolution &	SE
	)

static

ExtractSymbol - If S involves the addition of a GlobalValue address, return that symbol, and mutate S to point to a new SCEV with that value excluded.

Definition at line 586 of file LoopStrengthReduce.cpp.

References llvm::SCEV::FlagAnyWrap, llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getAddRecExpr(), and llvm::ScalarEvolution::getConstant().

Referenced by isAlwaysFoldable().

static User::op_iterator findIVOperand	(	User::op_iterator	OI,
		User::op_iterator	OE,
		Loop *	L,
		ScalarEvolution &	SE
	)

static

findIVOperand - Helper for CollectChains that finds an IV operand (computed by an AddRec in this loop) within [OI,OE) or returns OE. If IVUsers mapped Instructions to IVStrideUses, we could partially skip this.

Definition at line 2379 of file LoopStrengthReduce.cpp.

References llvm::SCEVAddRecExpr::getLoop(), llvm::ScalarEvolution::getSCEV(), and llvm::ScalarEvolution::isSCEVable().

static Type* getAccessType ( const Instruction * Inst )

static

getAccessType - Return the type of the memory being accessed.

Definition at line 636 of file LoopStrengthReduce.cpp.

References llvm::IntegerType::get(), llvm::PointerType::get(), llvm::Value::getType(), llvm::Intrinsic::x86_sse2_storel_dq, llvm::Intrinsic::x86_sse2_storeu_dq, llvm::Intrinsic::x86_sse2_storeu_pd, and llvm::Intrinsic::x86_sse_storeu_ps.

Referenced by canFoldIVIncExpr().

static const SCEV* getExactSDiv	(	const SCEV *	LHS,
		const SCEV *	RHS,
		ScalarEvolution &	SE,
		bool	IgnoreSignificantBits = `false`
	)

static

getExactSDiv - Return an expression for LHS /s RHS, if it can be determined and if the remainder is known to be zero, or null otherwise. If IgnoreSignificantBits is true, expressions like (X * Y) /s Y are simplified to Y, ignoring that the multiplication may overflow, which is useful when the result will be used in a context where the most significant bits are ignored.

Definition at line 467 of file LoopStrengthReduce.cpp.

References llvm::CallingConv::C, llvm::dyn_cast(), llvm::SCEV::FlagAnyWrap, llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getConstant(), llvm::ScalarEvolution::getMulExpr(), llvm::SCEV::getType(), llvm::SCEVConstant::getValue(), llvm::ConstantInt::getValue(), I, isAddRecSExtable(), isAddSExtable(), llvm::APInt::isAllOnesValue(), isMulSExtable(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::APInt::sdiv(), and llvm::APInt::srem().

static const SCEV* getExprBase ( const SCEV * S )

static

getExprBase - Return an approximation of this SCEV expression's "base", or NULL for any constant. Returning the expression itself is conservative. Returning a deeper subexpression is more precise and valid as long as it isn't less complex than another subexpression. For expressions involving multiple unscaled values, we need to return the pointer-type SCEVUnknown. This avoids forming chains across objects, such as: PrevOper==a[i], IVOper==b[i], IVInc==b-a.

Since SCEVUnknown is the rightmost type, and pointers are the rightmost SCEVUnknown, we simply return the rightmost SCEV operand.

Definition at line 2422 of file LoopStrengthReduce.cpp.

References llvm::SCEV::getSCEVType(), I, llvm::SCEVNAryExpr::op_begin(), llvm::SCEVNAryExpr::op_end(), llvm::scAddExpr, llvm::scAddRecExpr, llvm::scConstant, llvm::scMulExpr, llvm::scSignExtend, llvm::scTruncate, and llvm::scZeroExtend.

static unsigned getScalingFactorCost	(	const TargetTransformInfo &	TTI,
		const LSRUse &	LU,
		const Formula &	F
	)

static

Definition at line 1422 of file LoopStrengthReduce.cpp.

References llvm::TargetTransformInfo::getScalingFactorCost(), isLegalUse(), and llvm_unreachable.

static Value* getWideOperand ( Value * Oper )

static

getWideOperand - IVChain logic must consistenctly peek base TruncInst operands, so wrap it in a convenient helper.

Definition at line 2398 of file LoopStrengthReduce.cpp.

INITIALIZE_PASS_BEGIN	(	LoopStrengthReduce	,
		"loop-reduce"	,
		"Loop Strength Reduction"	,
		false	,
		false
	)

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

static

isAddRecSExtable - Return true if the given addrec can be sign-extended without changing its value.

Definition at line 438 of file LoopStrengthReduce.cpp.

References llvm::IntegerType::get(), llvm::ScalarEvolution::getContext(), llvm::ScalarEvolution::getSignExtendExpr(), llvm::SCEVNAryExpr::getType(), and llvm::ScalarEvolution::getTypeSizeInBits().

Referenced by getExactSDiv().

static bool isAddressUse	(	Instruction *	Inst,
		Value *	OperandVal
	)

static

isAddressUse - Returns true if the specified instruction is using the specified value as an address.

Definition at line 612 of file LoopStrengthReduce.cpp.

References llvm::Intrinsic::prefetch, llvm::Intrinsic::x86_sse2_storel_dq, llvm::Intrinsic::x86_sse2_storeu_dq, llvm::Intrinsic::x86_sse2_storeu_pd, and llvm::Intrinsic::x86_sse_storeu_ps.

Referenced by canFoldIVIncExpr().

static bool isAddSExtable	(	const SCEVAddExpr *	A,
		ScalarEvolution &	SE
	)

static

isAddSExtable - Return true if the given add can be sign-extended without changing its value.

Definition at line 446 of file LoopStrengthReduce.cpp.

References llvm::IntegerType::get(), llvm::ScalarEvolution::getContext(), llvm::ScalarEvolution::getSignExtendExpr(), llvm::SCEVAddExpr::getType(), and llvm::ScalarEvolution::getTypeSizeInBits().

Referenced by getExactSDiv().

static bool isAlwaysFoldable	(	const TargetTransformInfo &	TTI,
		LSRUse::KindType	Kind,
		Type *	AccessTy,
		GlobalValue *	BaseGV,
		int64_t	BaseOffset,
		bool	HasBaseReg
	)

static

Definition at line 1458 of file LoopStrengthReduce.cpp.

References isLegalUse().

Referenced by canFoldIVIncExpr().

static bool isAlwaysFoldable	(	const TargetTransformInfo &	TTI,
		ScalarEvolution &	SE,
		int64_t	MinOffset,
		int64_t	MaxOffset,
		LSRUse::KindType	Kind,
		Type *	AccessTy,
		const SCEV *	S,
		bool	HasBaseReg
	)

static

Definition at line 1479 of file LoopStrengthReduce.cpp.

References ExtractImmediate(), ExtractSymbol(), isLegalUse(), and llvm::SCEV::isZero().

static bool isCompatibleIVType	(	Value *	LVal,
		Value *	RVal
	)

static

isCompatibleIVType - Return true if we allow an IV chain to include both types.

Definition at line 2406 of file LoopStrengthReduce.cpp.

References llvm::Value::getType(), and llvm::Type::isPointerTy().

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

static

isExistingPhi - Return true if this AddRec is already a phi in its loop.

Definition at line 664 of file LoopStrengthReduce.cpp.

References llvm::dyn_cast(), llvm::ScalarEvolution::getEffectiveSCEVType(), llvm::LoopBase< N, M >::getHeader(), llvm::SCEVAddRecExpr::getLoop(), llvm::ScalarEvolution::getSCEV(), llvm::Value::getType(), llvm::SCEVNAryExpr::getType(), I, and llvm::ScalarEvolution::isSCEVable().

Referenced by isHighCostExpansion().

static bool isHighCostExpansion	(	const SCEV *	S,
		SmallPtrSet< const SCEV *, 8 > &	Processed,
		ScalarEvolution &	SE
	)

static

Check if expanding this expression is likely to incur significant cost. This is tricky because SCEV doesn't track which expressions are actually computed by the current IR.

We currently allow expansion of IV increments that involve adds, multiplication by constants, and AddRecs from existing phis.

TODO: Allow UDivExpr if we can find an existing IV increment that is an obvious multiple of the UDivExpr.

Definition at line 685 of file LoopStrengthReduce.cpp.

References llvm::dyn_cast(), llvm::Instruction::getOpcode(), llvm::ScalarEvolution::getSCEV(), llvm::SCEV::getSCEVType(), llvm::Value::getType(), I, llvm::SmallPtrSet< PtrType, SmallSize >::insert(), isExistingPhi(), llvm::ScalarEvolution::isSCEVable(), llvm::scConstant, llvm::scSignExtend, llvm::scTruncate, llvm::scUnknown, llvm::scZeroExtend, llvm::Value::use_begin(), and llvm::Value::use_end().

static bool isLegal2RegAMUse	(	const TargetTransformInfo &	TTI,
		const LSRUse &	LU,
		const Formula &	F
	)

static

Definition at line 1398 of file LoopStrengthReduce.cpp.

References isLegalUse().

static bool isLegalUse	(	const TargetTransformInfo &	TTI,
		LSRUse::KindType	Kind,
		Type *	AccessTy,
		GlobalValue *	BaseGV,
		int64_t	BaseOffset,
		bool	HasBaseReg,
		int64_t	Scale
	)

static

isLegalUse - Test whether the use described by AM is "legal", meaning it can be completely folded into the user instruction at isel time. This includes address-mode folding and special icmp tricks.

Definition at line 1319 of file LoopStrengthReduce.cpp.

References llvm::TargetTransformInfo::isLegalAddressingMode(), llvm::TargetTransformInfo::isLegalICmpImmediate(), and llvm_unreachable.

Referenced by getScalingFactorCost(), isAlwaysFoldable(), isLegal2RegAMUse(), and isLegalUse().

static bool isLegalUse	(	const TargetTransformInfo &	TTI,
		int64_t	MinOffset,
		int64_t	MaxOffset,
		LSRUse::KindType	Kind,
		Type *	AccessTy,
		GlobalValue *	BaseGV,
		int64_t	BaseOffset,
		bool	HasBaseReg,
		int64_t	Scale
	)

static

Definition at line 1372 of file LoopStrengthReduce.cpp.

References isLegalUse().

static bool isLegalUse	(	const TargetTransformInfo &	TTI,
		int64_t	MinOffset,
		int64_t	MaxOffset,
		LSRUse::KindType	Kind,
		Type *	AccessTy,
		const Formula &	F
	)

static

Definition at line 1391 of file LoopStrengthReduce.cpp.

References isLegalUse().

static bool isMulSExtable	(	const SCEVMulExpr *	M,
		ScalarEvolution &	SE
	)

static

isMulSExtable - Return true if the given mul can be sign-extended without changing its value.

Definition at line 454 of file LoopStrengthReduce.cpp.

References llvm::IntegerType::get(), llvm::ScalarEvolution::getContext(), llvm::SCEVNAryExpr::getNumOperands(), llvm::ScalarEvolution::getSignExtendExpr(), llvm::SCEVNAryExpr::getType(), and llvm::ScalarEvolution::getTypeSizeInBits().

Referenced by getExactSDiv().

static bool isProfitableChain	(	IVChain &	Chain,
		SmallPtrSet< Instruction *, 4 > &	Users,
		ScalarEvolution &	SE,
		const TargetTransformInfo &	TTI
	)

static

Return true if the number of registers needed for the chain is estimated to be less than the number required for the individual IV users. First prohibit any IV users that keep the IV live across increments (the Users set should be empty). Next count the number and type of increments in the chain.

Chaining IVs can lead to considerable code bloat if ISEL doesn't effectively use postinc addressing modes. Only consider it profitable it the increments can be computed in fewer registers when chained.

TODO: Consider IVInc free if it's already used in another chains.

Definition at line 2490 of file LoopStrengthReduce.cpp.

References llvm::SmallPtrSet< PtrType, SmallSize >::begin(), cost, llvm::dbgs(), DEBUG, llvm::SmallPtrSetImpl::empty(), llvm::SmallPtrSet< PtrType, SmallSize >::end(), for(), llvm::ScalarEvolution::getSCEV(), I, and StressIVChain.

Variable Documentation

const size_t ComplexityLimit = UINT16_MAX

static

Definition at line 3863 of file LoopStrengthReduce.cpp.

cl::opt<bool> EnablePhiElim("enable-lsr-phielim", cl::Hidden, cl::init(true), cl::desc("Enable LSR phi elimination"))

static

loop Loop Strength false

Definition at line 4882 of file LoopStrengthReduce.cpp.

const unsigned MaxIVUsers = 200

static

MaxIVUsers is an arbitrary threshold that provides an early opportunitiy for bail out. This threshold is far beyond the number of users that LSR can conceivably solve, so it should not affect generated code, but catches the worst cases before LSR burns too much compile time and stack space.

Definition at line 85 of file LoopStrengthReduce.cpp.

loop reduce

Definition at line 4882 of file LoopStrengthReduce.cpp.

loop Loop Strength Reduction

Definition at line 4882 of file LoopStrengthReduce.cpp.

cl::opt<bool> StressIVChain("stress-ivchain", cl::Hidden, cl::init(false), cl::desc("Stress test LSR IV chains"))

static

Referenced by isProfitableChain().

Macros

Functions

Variables

Macro Definition Documentation

Function Documentation

Variable Documentation