#include "llvm/Transforms/Vectorize.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Analysis/Verifier.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Value.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/PatternMatch.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Support/ValueHandle.h"
#include "llvm/Target/TargetLibraryInfo.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include <algorithm>
#include <map>

Include dependency graph for LoopVectorize.cpp:

Namespaces
	llvm
	List of target independent CodeGen pass IDs.

Macros
#define	LV_NAME "loop-vectorize"

#define	DEBUG_TYPE LV_NAME

Functions
static unsigned	getGEPInductionOperand (DataLayout DL, const GetElementPtrInst Gep)
	Find the operand of the GEP that should be checked for consecutive stores. This ignores trailing indices that have no effect on the final pointer. More...

static Intrinsic::ID	checkUnaryFloatSignature (const CallInst &I, Intrinsic::ID ValidIntrinsicID)

static Intrinsic::ID	checkBinaryFloatSignature (const CallInst &I, Intrinsic::ID ValidIntrinsicID)

static Intrinsic::ID	getIntrinsicIDForCall (CallInst CI, const TargetLibraryInfo TLI)

static unsigned	getReductionBinOp (LoopVectorizationLegality::ReductionKind Kind)
	This function translates the reduction kind to an LLVM binary operator. More...

Value *	createMinMaxOp (IRBuilder<> &Builder, LoopVectorizationLegality::MinMaxReductionKind RK, Value Left, Value Right)

static void	cse (BasicBlock *BB)
	Perform cse of induction variable instructions. More...

static Type *	convertPointerToIntegerType (DataLayout &DL, Type *Ty)

static Type *	getWiderType (DataLayout &DL, Type Ty0, Type Ty1)

static bool	hasOutsideLoopUser (const Loop TheLoop, Instruction Inst, SmallPtrSet< Value *, 4 > &Reductions)
	Check that the instruction has outside loop users and is not an identified reduction variable. More...

static bool	hasComputableBounds (ScalarEvolution SE, Value Ptr)
	Check whether a pointer can participate in a runtime bounds check. More...

static int	isStridedPtr (ScalarEvolution SE, DataLayout DL, Value Ptr, const Loop Lp)
	Check the stride of the pointer and ensure that it does not wrap in the address space. More...

static bool	isFunctionScopeIdentifiedObject (Value *Ptr)

static bool	isInBoundsGep (Value *Ptr)

static bool	hasMultipleUsesOf (Instruction I, SmallPtrSet< Instruction , 8 > &Insts)

static bool	areAllUsesIn (Instruction I, SmallPtrSet< Instruction , 8 > &Set)

static bool	isLikelyComplexAddressComputation (Value Ptr, LoopVectorizationLegality Legal, ScalarEvolution SE, const Loop TheLoop)
	Check whether the address computation for a non-consecutive memory access looks like an unlikely candidate for being merged into the indexing mode. More...

Pass *	llvm::createLoopVectorizePass (bool NoUnrolling=false)

Variables
static cl::opt< unsigned >	VectorizationFactor ("force-vector-width", cl::init(0), cl::Hidden, cl::desc("Sets the SIMD width. Zero is autoselect."))

static cl::opt< unsigned >	VectorizationUnroll ("force-vector-unroll", cl::init(0), cl::Hidden, cl::desc("Sets the vectorization unroll count. ""Zero is autoselect."))

static cl::opt< bool >	EnableIfConversion ("enable-if-conversion", cl::init(true), cl::Hidden, cl::desc("Enable if-conversion during vectorization."))

static cl::opt< unsigned >	TinyTripCountVectorThreshold ("vectorizer-min-trip-count", cl::init(16), cl::Hidden, cl::desc("Don't vectorize loops with a constant ""trip count that is smaller than this ""value."))
	We don't vectorize loops with a known constant trip count below this number. More...

static const unsigned	TinyTripCountUnrollThreshold = 128
	We don't unroll loops with a known constant trip count below this number. More...

static const unsigned	RuntimeMemoryCheckThreshold = 8

static const unsigned	MaxVectorWidth = 64
	Maximum simd width. More...

static const unsigned	MaxUnrollFactor = 16
	Maximum vectorization unroll count. More...

static const unsigned	SmallLoopCost = 20
	The cost of a loop that is considered 'small' by the unroller. More...

static const char	lv_name [] = "Loop Vectorization"

Macro Definition Documentation

#define DEBUG_TYPE LV_NAME

Definition at line 46 of file LoopVectorize.cpp.

#define LV_NAME "loop-vectorize"

Definition at line 45 of file LoopVectorize.cpp.

Function Documentation

static bool areAllUsesIn	(	Instruction *	I,
		SmallPtrSet< Instruction *, 8 > &	Set
	)

static

Definition at line 4028 of file LoopVectorize.cpp.

References llvm::SmallPtrSet< PtrType, SmallSize >::count(), llvm::User::op_begin(), and llvm::User::op_end().

static Intrinsic::ID checkBinaryFloatSignature	(	const CallInst &	I,
		Intrinsic::ID	ValidIntrinsicID
	)

static

Definition at line 1864 of file LoopVectorize.cpp.

References llvm::CallInst::getArgOperand(), llvm::CallInst::getNumArgOperands(), llvm::Value::getType(), llvm::Type::isFloatingPointTy(), llvm::Intrinsic::not_intrinsic, and llvm::CallInst::onlyReadsMemory().

Referenced by getIntrinsicIDForCall().

static Intrinsic::ID checkUnaryFloatSignature	(	const CallInst &	I,
		Intrinsic::ID	ValidIntrinsicID
	)

static

Definition at line 1853 of file LoopVectorize.cpp.

References llvm::CallInst::getArgOperand(), llvm::CallInst::getNumArgOperands(), llvm::Value::getType(), llvm::Type::isFloatingPointTy(), llvm::Intrinsic::not_intrinsic, and llvm::CallInst::onlyReadsMemory().

Referenced by getIntrinsicIDForCall().

static Type* convertPointerToIntegerType	(	DataLayout &	DL,
		Type *	Ty
	)

static

Definition at line 2888 of file LoopVectorize.cpp.

References llvm::Type::getContext(), llvm::Type::getInt32Ty(), llvm::DataLayout::getIntPtrType(), llvm::Type::getScalarSizeInBits(), and llvm::Type::isPointerTy().

Referenced by getWiderType().

Value* createMinMaxOp	(	IRBuilder<> &	Builder,
		LoopVectorizationLegality::MinMaxReductionKind	RK,
		Value *	Left,
		Value *	Right
	)

Definition at line 2022 of file LoopVectorize.cpp.

References llvm::IRBuilder< preserveNames, T, Inserter >::CreateFCmp(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateICmp(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateSelect(), llvm::CmpInst::FCMP_OGT, llvm::CmpInst::FCMP_OLT, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLT, llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULT, llvm_unreachable, P, and llvm::MCID::Select.

static void cse ( BasicBlock * BB )

static

Perform cse of induction variable instructions.

Definition at line 2088 of file LoopVectorize.cpp.

References llvm::BasicBlock::begin(), llvm::BasicBlock::end(), llvm::Instruction::eraseFromParent(), llvm::tgtok::In, llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT >, KeyT, ValueT, KeyInfoT >::lookup(), and llvm::Value::replaceAllUsesWith().

static unsigned getGEPInductionOperand	(	DataLayout *	DL,
		const GetElementPtrInst *	Gep
	)

static

Find the operand of the GEP that should be checked for consecutive stores. This ignores trailing indices that have no effect on the final pointer.

Definition at line 1073 of file LoopVectorize.cpp.

References llvm::object::advance(), llvm::gep_type_begin(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::Type::getScalarType(), llvm::GetElementPtrInst::getType(), llvm::DataLayout::getTypeAllocSize(), llvm::PatternMatch::m_Zero(), and llvm::PatternMatch::match().

static Intrinsic::ID getIntrinsicIDForCall	(	CallInst *	CI,
		const TargetLibraryInfo *	TLI
	)

static

Definition at line 1879 of file LoopVectorize.cpp.

References llvm::LibFunc::ceil, llvm::Intrinsic::ceil, llvm::LibFunc::ceilf, llvm::LibFunc::ceill, checkBinaryFloatSignature(), checkUnaryFloatSignature(), llvm::LibFunc::copysign, llvm::Intrinsic::copysign, llvm::LibFunc::copysignf, llvm::LibFunc::copysignl, llvm::LibFunc::cos, llvm::Intrinsic::cos, llvm::LibFunc::cosf, llvm::LibFunc::cosl, llvm::LibFunc::exp, llvm::Intrinsic::exp, llvm::LibFunc::exp2, llvm::Intrinsic::exp2, llvm::LibFunc::exp2f, llvm::LibFunc::exp2l, llvm::LibFunc::expf, llvm::LibFunc::expl, F(), llvm::LibFunc::fabs, llvm::Intrinsic::fabs, llvm::LibFunc::fabsf, llvm::LibFunc::fabsl, llvm::LibFunc::floor, llvm::Intrinsic::floor, llvm::LibFunc::floorf, llvm::LibFunc::floorl, llvm::Intrinsic::fma, llvm::Intrinsic::fmuladd, llvm::CallInst::getCalledFunction(), llvm::TargetLibraryInfo::getLibFunc(), llvm::Value::getName(), llvm::GlobalValue::hasLocalLinkage(), llvm::Intrinsic::lifetime_end, llvm::Intrinsic::lifetime_start, llvm::LibFunc::log, llvm::Intrinsic::log, llvm::LibFunc::log10, llvm::Intrinsic::log10, llvm::LibFunc::log10f, llvm::LibFunc::log10l, llvm::LibFunc::log2, llvm::Intrinsic::log2, llvm::LibFunc::log2f, llvm::LibFunc::log2l, llvm::LibFunc::logf, llvm::LibFunc::logl, llvm::LibFunc::nearbyint, llvm::Intrinsic::nearbyint, llvm::LibFunc::nearbyintf, llvm::LibFunc::nearbyintl, llvm::Intrinsic::not_intrinsic, llvm::LibFunc::pow, llvm::Intrinsic::pow, llvm::LibFunc::powf, llvm::LibFunc::powl, llvm::LibFunc::rint, llvm::Intrinsic::rint, llvm::LibFunc::rintf, llvm::LibFunc::rintl, llvm::LibFunc::round, llvm::Intrinsic::round, llvm::LibFunc::roundf, llvm::LibFunc::roundl, llvm::LibFunc::sin, llvm::Intrinsic::sin, llvm::LibFunc::sinf, llvm::LibFunc::sinl, llvm::Intrinsic::sqrt, llvm::LibFunc::trunc, llvm::Intrinsic::trunc, llvm::LibFunc::truncf, and llvm::LibFunc::truncl.

static unsigned getReductionBinOp ( LoopVectorizationLegality::ReductionKind Kind )

static

This function translates the reduction kind to an LLVM binary operator.

Definition at line 1997 of file LoopVectorize.cpp.

References llvm::APIntOps::And(), llvm_unreachable, llvm::APIntOps::Or(), and llvm::APIntOps::Xor().

static Type* getWiderType	(	DataLayout &	DL,
		Type *	Ty0,
		Type *	Ty1
	)

static

Definition at line 2900 of file LoopVectorize.cpp.

References convertPointerToIntegerType(), and llvm::Type::getScalarSizeInBits().

static bool hasComputableBounds	(	ScalarEvolution *	SE,
		Value *	Ptr
	)

static

Check whether a pointer can participate in a runtime bounds check.

Definition at line 3210 of file LoopVectorize.cpp.

References llvm::dyn_cast(), llvm::ScalarEvolution::getSCEV(), and llvm::SCEVAddRecExpr::isAffine().

static bool hasMultipleUsesOf	(	Instruction *	I,
		SmallPtrSet< Instruction *, 8 > &	Insts
	)

static

Definition at line 4015 of file LoopVectorize.cpp.

References llvm::SmallPtrSet< PtrType, SmallSize >::count(), llvm::User::op_begin(), and llvm::User::op_end().

static bool hasOutsideLoopUser	(	const Loop *	TheLoop,
		Instruction *	Inst,
		SmallPtrSet< Value *, 4 > &	Reductions
	)

static

Check that the instruction has outside loop users and is not an identified reduction variable.

Definition at line 2910 of file LoopVectorize.cpp.

References llvm::LoopBase< N, M >::contains(), llvm::SmallPtrSet< PtrType, SmallSize >::count(), llvm::dbgs(), DEBUG, I, llvm::Value::use_begin(), and llvm::Value::use_end().

static bool isFunctionScopeIdentifiedObject ( Value * Ptr )

static

Definition at line 3315 of file LoopVectorize.cpp.

References llvm::isNoAliasArgument(), and llvm::isNoAliasCall().

static bool isInBoundsGep ( Value * Ptr )

static

Definition at line 3519 of file LoopVectorize.cpp.

Referenced by isStridedPtr().

static bool isLikelyComplexAddressComputation	(	Value *	Ptr,
		LoopVectorizationLegality *	Legal,
		ScalarEvolution *	SE,
		const Loop *	TheLoop
	)

static

Check whether the address computation for a non-consecutive memory access looks like an unlikely candidate for being merged into the indexing mode.

We look for a GEP which has one index that is an induction variable and all other indices are loop invariant. If the stride of this access is also within a small bound we decide that this address computation can likely be merged into the addressing mode. In all other cases, we identify the address computation as complex.

Definition at line 4764 of file LoopVectorize.cpp.

References llvm::dyn_cast(), llvm::APInt::getBitWidth(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::ScalarEvolution::getSCEV(), llvm::APInt::getSExtValue(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::SCEVConstant::getValue(), llvm::ConstantInt::getValue(), and llvm::ScalarEvolution::isLoopInvariant().

static int isStridedPtr	(	ScalarEvolution *	SE,
		DataLayout *	DL,
		Value *	Ptr,
		const Loop *	Lp
	)

static

Check the stride of the pointer and ensure that it does not wrap in the address space.

Check whether the access through Ptr has a constant stride.

Definition at line 3526 of file LoopVectorize.cpp.

References llvm::dbgs(), DEBUG, llvm::dyn_cast(), llvm::APInt::getBitWidth(), llvm::SCEVAddRecExpr::getLoop(), llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::ScalarEvolution::getSCEV(), llvm::APInt::getSExtValue(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::Value::getType(), llvm::DataLayout::getTypeAllocSize(), llvm::SCEVConstant::getValue(), llvm::ConstantInt::getValue(), isInBoundsGep(), llvm::Type::isPointerTy(), and llvm::SCEV::NoWrapMask.

Variable Documentation

cl::opt<bool> EnableIfConversion("enable-if-conversion", cl::init(true), cl::Hidden, cl::desc("Enable if-conversion during vectorization."))

static

const char lv_name[] = "Loop Vectorization"

static

Definition at line 4999 of file LoopVectorize.cpp.

const unsigned MaxUnrollFactor = 16

static

Maximum vectorization unroll count.

Definition at line 128 of file LoopVectorize.cpp.

const unsigned MaxVectorWidth = 64

static

Maximum simd width.

Definition at line 125 of file LoopVectorize.cpp.

const unsigned RuntimeMemoryCheckThreshold = 8

static

When performing memory disambiguation checks at runtime do not make more than this number of comparisons.

Definition at line 122 of file LoopVectorize.cpp.

const unsigned SmallLoopCost = 20

static

The cost of a loop that is considered 'small' by the unroller.

Definition at line 131 of file LoopVectorize.cpp.

const unsigned TinyTripCountUnrollThreshold = 128

static

We don't unroll loops with a known constant trip count below this number.

Definition at line 118 of file LoopVectorize.cpp.

cl::opt<unsigned> TinyTripCountVectorThreshold("vectorizer-min-trip-count", cl::init(16), cl::Hidden, cl::desc("Don't vectorize loops with a constant ""trip count that is smaller than this ""value."))

static

We don't vectorize loops with a known constant trip count below this number.

cl::opt<unsigned> VectorizationFactor("force-vector-width", cl::init(0), cl::Hidden, cl::desc("Sets the SIMD width. Zero is autoselect."))

static

cl::opt<unsigned> VectorizationUnroll("force-vector-unroll", cl::init(0), cl::Hidden, cl::desc("Sets the vectorization unroll count. ""Zero is autoselect."))

static

Namespaces

Macros

Functions

Variables

Macro Definition Documentation

Function Documentation

Variable Documentation