LoopStrengthReduce.cpp File Reference

#include "llvm/Transforms/Scalar.h"
#include "llvm/Constants.h"
#include "llvm/Instructions.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Type.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Target/TargetData.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Target/TargetLowering.h"
#include <algorithm>
#include <set>

Include dependency graph for LoopStrengthReduce.cpp:

Go to the source code of this file.

Classes

struct SubExprUseData

Defines

#define DEBUG_TYPE "loop-reduce"

Functions

STATISTIC (NumReduced,"Number of GEPs strength reduced")

STATISTIC (NumInserted,"Number of PHIs inserted")

STATISTIC (NumVariable,"Number of PHIs with variable strides")

STATISTIC (NumEliminated,"Number of strides eliminated")

STATISTIC (NumShadow,"Number of Shadow IVs optimized")

Pass * llvm::createLoopStrengthReducePass (const TargetLowering *TLI=0)

static bool containsAddRecFromDifferentLoop (SCEVHandle S, Loop *L)

static bool getSCEVStartAndStride (const SCEVHandle &SH, Loop *L, SCEVHandle &Start, SCEVHandle &Stride, ScalarEvolution *SE, DominatorTree *DT)

static bool IVUseShouldUsePostIncValue (Instruction *User, Instruction *IV, Loop *L, DominatorTree *DT, Pass *P, SmallVectorImpl< Instruction * > &DeadInsts)

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

static bool fitsInAddressMode (const SCEVHandle &V, const Type *UseTy, const TargetLowering *TLI, bool HasBaseReg)

static void MoveLoopVariantsToImmediateField (SCEVHandle &Val, SCEVHandle &Imm, Loop *L, ScalarEvolution *SE)

static void MoveImmediateValues (const TargetLowering *TLI, Instruction *User, SCEVHandle &Val, SCEVHandle &Imm, bool isAddress, Loop *L, ScalarEvolution *SE)

static void SeparateSubExprs (std::vector< SCEVHandle > &SubExprs, SCEVHandle Expr, ScalarEvolution *SE)

static SCEVHandle RemoveCommonExpressionsFromUseBases (std::vector< BasedUser > &Uses, ScalarEvolution *SE, Loop *L, const TargetLowering *TLI)

static bool PartitionByIsUseOfPostIncrementedValue (const BasedUser &Val)

static bool isNonConstantNegative (const SCEVHandle &Expr)

Variables

static RegisterPass
< LoopStrengthReduce > X ("loop-reduce","Loop Strength Reduction")

Define Documentation

#define DEBUG_TYPE "loop-reduce"

Definition at line 18 of file LoopStrengthReduce.cpp.

Function Documentation

static bool containsAddRecFromDifferentLoop	(	SCEVHandle	S,
		Loop *	L
	)			`[static]`

containsAddRecFromDifferentLoop - Determine whether expression S involves a subexpression that is an AddRec from a loop other than L. An outer loop of L is OK, but not an inner loop nor a disjoint loop.

Definition at line 356 of file LoopStrengthReduce.cpp.

References DE, and SE.

Referenced by getSCEVStartAndStride().

static bool fitsInAddressMode	(	const SCEVHandle &	V,
		const Type *	UseTy,
		const TargetLowering *	TLI,
		bool	HasBaseReg
	)			`[static]`

fitsInAddressMode - Return true if V can be subsumed within an addressing mode, and does not need to be put in a register first.

Definition at line 851 of file LoopStrengthReduce.cpp.

References llvm::TargetLowering::AddrMode::BaseGV, llvm::TargetLowering::AddrMode::BaseOffs, GV, llvm::TargetLowering::AddrMode::HasBaseReg, llvm::TargetLowering::isLegalAddressingMode(), PtrToInt, and llvm::ARMCC::VC.

Referenced by MoveImmediateValues(), and RemoveCommonExpressionsFromUseBases().

static bool getSCEVStartAndStride	(	const SCEVHandle &	SH,
		Loop *	L,
		SCEVHandle &	Start,
		SCEVHandle &	Stride,
		ScalarEvolution *	SE,
		DominatorTree *	DT
	)			`[static]`

getSCEVStartAndStride - Compute the start and stride of this expression, returning false if the expression is not a start/stride pair, or true if it is. The stride must be a loop invariant expression, but the start may be a mix of loop invariant and loop variant expressions. The start cannot, however, contain an AddRec from a different loop, unless that loop is an outer loop of the current loop.

Definition at line 401 of file LoopStrengthReduce.cpp.

References containsAddRecFromDifferentLoop(), llvm::DominatorTree::dominates(), DOUT, llvm::dyn_cast(), llvm::ScalarEvolution::getAddExpr(), llvm::LoopBase< BlockT >::getHeader(), llvm::SCEVAddRecExpr::getLoop(), llvm::LoopBase< BlockT >::getLoopPreheader(), llvm::SCEVAddRecExpr::getOperand(), llvm::Instruction::getParent(), llvm::SCEVAddRecExpr::isAffine(), and Preheader.

static bool isAddressUse	(	Instruction *	Inst,
		Value *	OperandVal
	)			`[static]`

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

Definition at line 519 of file LoopStrengthReduce.cpp.

References II, llvm::Intrinsic::prefetch, llvm::Intrinsic::x86_sse2_loadu_dq, llvm::Intrinsic::x86_sse2_loadu_pd, llvm::Intrinsic::x86_sse2_storel_dq, llvm::Intrinsic::x86_sse2_storeu_dq, llvm::Intrinsic::x86_sse2_storeu_pd, llvm::Intrinsic::x86_sse_loadu_ps, and llvm::Intrinsic::x86_sse_storeu_ps.

Referenced by RemoveCommonExpressionsFromUseBases().

static bool isNonConstantNegative ( const SCEVHandle & Expr ) [static]

isNonConstantNegative - Return true if the specified scev is negated, but not a constant.

Definition at line 1357 of file LoopStrengthReduce.cpp.

References llvm::dyn_cast(), llvm::SCEVCommutativeExpr::getOperand(), llvm::ConstantInt::getValue(), llvm::SCEVConstant::getValue(), and llvm::APInt::isNegative().

static bool IVUseShouldUsePostIncValue	(	Instruction *	User,
		Instruction *	IV,
		Loop *	L,
		DominatorTree *	DT,
		Pass *	P,
		SmallVectorImpl< Instruction * > &	DeadInsts
	)			`[static]`

IVUseShouldUsePostIncValue - We have discovered a "User" of an IV expression and now we need to decide whether the user should use the preinc or post-inc value. If this user should use the post-inc version of the IV, return true.

Choosing wrong here can break dominance properties (if we choose to use the post-inc value when we cannot) or it can end up adding extra live-ranges to the loop, resulting in reg-reg copies (if we use the pre-inc value when we should use the post-inc value).

Definition at line 468 of file LoopStrengthReduce.cpp.

References llvm::LoopBase< BlockT >::contains(), llvm::DominatorTree::dominates(), llvm::dyn_cast(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::LoopBase< BlockT >::getLoopLatch(), llvm::PHINode::getNumIncomingValues(), llvm::Instruction::getParent(), llvm::SmallVectorImpl< T >::push_back(), and llvm::SplitCriticalEdge().

static void MoveImmediateValues	(	const TargetLowering *	TLI,
		Instruction *	User,
		SCEVHandle &	Val,
		SCEVHandle &	Imm,
		bool	isAddress,
		Loop *	L,
		ScalarEvolution *	SE
	)			`[static]`

MoveImmediateValues - Look at Val, and pull out any additions of constants that can fit into the immediate field of instructions in the target. Accumulate these immediate values into the Imm value.

Definition at line 922 of file LoopStrengthReduce.cpp.

References fitsInAddressMode(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getAddRecExpr(), llvm::ScalarEvolution::getIntegerSCEV(), llvm::ScalarEvolution::getMulExpr(), and llvm::Value::getType().

static void MoveLoopVariantsToImmediateField	(	SCEVHandle &	Val,
		SCEVHandle &	Imm,
		Loop *	L,
		ScalarEvolution *	SE
	)			`[static]`

MoveLoopVariantsToImmediateField - Move any subexpressions from Val that are loop varying to the Imm operand.

Definition at line 882 of file LoopStrengthReduce.cpp.

References llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getAddRecExpr(), and llvm::ScalarEvolution::getIntegerSCEV().

static bool PartitionByIsUseOfPostIncrementedValue ( const BasedUser & Val ) [static]

PartitionByIsUseOfPostIncrementedValue - Simple boolean predicate that returns true if Val's isUseOfPostIncrementedValue is true.

Definition at line 1351 of file LoopStrengthReduce.cpp.

static SCEVHandle RemoveCommonExpressionsFromUseBases	(	std::vector< BasedUser > &	Uses,
		ScalarEvolution *	SE,
		Loop *	L,
		const TargetLowering *	TLI
	)			`[static]`

RemoveCommonExpressionsFromUseBases - Look through all of the Bases of all the Uses, removing any common subexpressions, except that if all such subexpressions can be folded into an addressing mode for all uses inside the loop (this case is referred to as "free" in comments herein) we do not remove anything. This looks for things like (a+b+c) and (a+c+d) and computes the common (a+c) subexpression. The common expression is *removed* from the Bases and returned.

Definition at line 1044 of file LoopStrengthReduce.cpp.

References llvm::LoopBase< BlockT >::contains(), fitsInAddressMode(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getIntegerSCEV(), llvm::ScalarEvolution::getMinusSCEV(), llvm::Value::getType(), Inst, isAddressUse(), OperandValToReplace, SeparateSubExprs(), and std::swap().

static void SeparateSubExprs	(	std::vector< SCEVHandle > &	SubExprs,
		SCEVHandle	Expr,
		ScalarEvolution *	SE
	)			`[static]`

SeparateSubExprs - Decompose Expr into all of the subexpressions that are added together. This is used to reassociate common addition subexprs together for maximal sharing when rewriting bases.

Definition at line 1007 of file LoopStrengthReduce.cpp.

References llvm::ScalarEvolution::getAddRecExpr(), and llvm::ScalarEvolution::getIntegerSCEV().

Referenced by RemoveCommonExpressionsFromUseBases().

STATISTIC	(	NumShadow	,
		"Number of Shadow IVs optimized"
	)

STATISTIC	(	NumEliminated	,
		"Number of strides eliminated"
	)

STATISTIC	(	NumVariable	,
		"Number of PHIs with variable strides"
	)

STATISTIC	(	NumInserted	,
		"Number of PHIs inserted"
	)

STATISTIC	(	NumReduced	,
		"Number of GEPs strength reduced"
	)

Variable Documentation

SCEVHandle Base

Base - The Base value for the PHI node that needs to be inserted for this use. As the use is processed, information gets moved from this field to the Imm field (below). BasedUser values are sorted by this field.

Definition at line 92 of file LoopStrengthReduce.cpp.

DenseMap<Value*, Value*> CastedPointers

CastedValues - As we need to cast values to uintptr_t, this keeps track of the casted version of each value. This is accessed by getCastedVersionOf.

Definition at line 142 of file LoopStrengthReduce.cpp.

bool Changed

Definition at line 118 of file LoopStrengthReduce.cpp.

SmallVector<Instruction*, 16> DeadInsts

DeadInsts - Keep track of instructions we may have made dead, so that we can remove them after we are done working.

Definition at line 146 of file LoopStrengthReduce.cpp.

Referenced by llvm::RecursivelyDeleteTriviallyDeadInstructions().

DominatorTree* DT

Definition at line 114 of file LoopStrengthReduce.cpp.

SmallVector<GetElementPtrInst *, 16> GEPlist

GEPlist - A list of the GEP's that have been remembered in the SCEV data structures. SCEV does not know to update these when the operands of the GEP are changed, which means we cannot leave them live across loops.

Definition at line 137 of file LoopStrengthReduce.cpp.

char ID [static]

Definition at line 153 of file LoopStrengthReduce.cpp.

SCEVHandle Imm

Imm - The immediate value that should be added to the base immediately before Inst, because it will be folded into the imm field of the instruction.

Definition at line 647 of file LoopStrengthReduce.cpp.

Referenced by llvm::SelectionDAG::getZeroExtendInReg(), printSOImm(), llvm::PPCTargetLowering::SelectAddressRegImm(), llvm::PPCTargetLowering::SelectAddressRegImmShift(), and llvm::TargetLowering::SimplifySetCC().

Value* IncV

Definition at line 94 of file LoopStrengthReduce.cpp.

Instruction* Inst

Inst - The instruction using the induction variable.

Definition at line 638 of file LoopStrengthReduce.cpp.

Referenced by llvm::FindAvailableLoadedValue(), GatherConstantSetEQs(), GatherConstantSetNEs(), RemoveCommonExpressionsFromUseBases(), llvm::UnrollLoop(), ValueIsOnlyUsedLocallyOrStoredToOneGlobal(), and llvm::Interpreter::visitUnwindInst().

bool isUseOfPostIncrementedValue

Definition at line 66 of file LoopStrengthReduce.cpp.

std::vector<IVExpr> IVs

Definition at line 104 of file LoopStrengthReduce.cpp.

std::map<SCEVHandle, IVsOfOneStride> IVsByStride

IVsByStride - Keep track of all IVs that have been inserted for a particular stride.

Definition at line 126 of file LoopStrengthReduce.cpp.

std::map<SCEVHandle, IVUsersOfOneStride> IVUsesByStride

IVUsesByStride - Keep track of all uses of induction variables that we are interested in. The key of the map is the stride of the access.

Definition at line 122 of file LoopStrengthReduce.cpp.

LoopInfo* LI

Definition at line 113 of file LoopStrengthReduce.cpp.

SCEVHandle Offset

Definition at line 58 of file LoopStrengthReduce.cpp.

Value* OperandValToReplace

OperandValToReplace - The operand value of Inst to replace with the EmittedBase.

Definition at line 60 of file LoopStrengthReduce.cpp.

Referenced by RemoveCommonExpressionsFromUseBases().

ScalarEvolution* SE

SE - The current ScalarEvolution object.

Definition at line 115 of file LoopStrengthReduce.cpp.

SCEVHandle Stride

Definition at line 91 of file LoopStrengthReduce.cpp.

SmallVector<SCEVHandle, 16> StrideOrder

StrideOrder - An ordering of the keys in IVUsesByStride that is stable: We use this to iterate over the IVUsesByStride collection without being dependent on random ordering of pointers in the process.

Definition at line 131 of file LoopStrengthReduce.cpp.

const TargetData* TD

Definition at line 116 of file LoopStrengthReduce.cpp.

const TargetLowering* TLI

TLI - Keep a pointer of a TargetLowering to consult for determining transformation profitability.

Definition at line 150 of file LoopStrengthReduce.cpp.

const Type* UIntPtrTy

Definition at line 117 of file LoopStrengthReduce.cpp.

Instruction* User

Definition at line 59 of file LoopStrengthReduce.cpp.

std::vector<IVStrideUse> Users

Users - Keep track of all of the users of this stride as well as the initial value and the operand that uses the IV.

Definition at line 80 of file LoopStrengthReduce.cpp.

Referenced by llvm::UnrollLoop().

RegisterPass<LoopStrengthReduce> X("loop-reduce","Loop Strength Reduction") [static]


Classes
struct	SubExprUseData
Defines
#define	DEBUG_TYPE "loop-reduce"
Functions
	STATISTIC (NumReduced,"Number of GEPs strength reduced")
	STATISTIC (NumInserted,"Number of PHIs inserted")
	STATISTIC (NumVariable,"Number of PHIs with variable strides")
	STATISTIC (NumEliminated,"Number of strides eliminated")
	STATISTIC (NumShadow,"Number of Shadow IVs optimized")
Pass *	llvm::createLoopStrengthReducePass (const TargetLowering *TLI=0)
static bool	containsAddRecFromDifferentLoop (SCEVHandle S, Loop *L)
static bool	getSCEVStartAndStride (const SCEVHandle &SH, Loop L, SCEVHandle &Start, SCEVHandle &Stride, ScalarEvolution SE, DominatorTree *DT)
static bool	IVUseShouldUsePostIncValue (Instruction User, Instruction IV, Loop L, DominatorTree DT, Pass P, SmallVectorImpl< Instruction > &DeadInsts)
static bool	isAddressUse (Instruction Inst, Value OperandVal)
static bool	fitsInAddressMode (const SCEVHandle &V, const Type UseTy, const TargetLowering TLI, bool HasBaseReg)
static void	MoveLoopVariantsToImmediateField (SCEVHandle &Val, SCEVHandle &Imm, Loop L, ScalarEvolution SE)
static void	MoveImmediateValues (const TargetLowering TLI, Instruction User, SCEVHandle &Val, SCEVHandle &Imm, bool isAddress, Loop L, ScalarEvolution SE)
static void	SeparateSubExprs (std::vector< SCEVHandle > &SubExprs, SCEVHandle Expr, ScalarEvolution *SE)
static SCEVHandle	RemoveCommonExpressionsFromUseBases (std::vector< BasedUser > &Uses, ScalarEvolution SE, Loop L, const TargetLowering *TLI)
static bool	PartitionByIsUseOfPostIncrementedValue (const BasedUser &Val)
static bool	isNonConstantNegative (const SCEVHandle &Expr)
Variables
static RegisterPass < LoopStrengthReduce >	X ("loop-reduce","Loop Strength Reduction")