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/SetVector.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.

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	getSCEVStartAndStride (const SCEVHandle &SH, Loop *L, SCEVHandle &Start, SCEVHandle &Stride, ScalarEvolution *SE)
static bool	IVUseShouldUsePostIncValue (Instruction *User, Instruction *IV, Loop *L, DominatorTree *DT, Pass *P, SetVector< Instruction * > &DeadInsts)
static bool	isTargetConstant (const SCEVHandle &V, const Type *UseTy, const TargetLowering *TLI)
static void	MoveLoopVariantsToImediateField (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)
static bool	PartitionByIsUseOfPostIncrementedValue (const BasedUser &Val)
static bool	isNonConstantNegative (const SCEVHandle &Expr)
static bool	isAddressUse (Instruction *Inst, Value *OperandVal)
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 getSCEVStartAndStride	(	const SCEVHandle &	SH,
		Loop *	L,
		SCEVHandle &	Start,
		SCEVHandle &	Stride,
		ScalarEvolution *	SE
	)			[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.

Definition at line 343 of file LoopStrengthReduce.cpp.

References DOUT, llvm::dyn_cast(), llvm::ScalarEvolution::getAddExpr(), llvm::LoopBase< BlockT >::getHeader(), llvm::SCEVAddRecExpr::getLoop(), llvm::SCEVAddRecExpr::getOperand(), and llvm::SCEVAddRecExpr::isAffine().

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 1106 of file LoopStrengthReduce.cpp.

References II.

static bool isNonConstantNegative

(

const SCEVHandle &

Expr

)

[static]

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

Definition at line 1092 of file LoopStrengthReduce.cpp.

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

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

isTargetConstant - Return true if the following can be referenced by the immediate field of a target instruction.

Definition at line 732 of file LoopStrengthReduce.cpp.

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

Referenced by MoveImmediateValues().

static bool IVUseShouldUsePostIncValue	(	Instruction *	User,
		Instruction *	IV,
		Loop *	L,
		DominatorTree *	DT,
		Pass *	P,
		SetVector< 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 392 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::SetVector< T, Vector, Set >::insert(), 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 801 of file LoopStrengthReduce.cpp.

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

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

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

Definition at line 761 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 1086 of file LoopStrengthReduce.cpp.

static SCEVHandle RemoveCommonExpressionsFromUseBases	(	std::vector< BasedUser > &	Uses,
		ScalarEvolution *	SE
	)			[static]

RemoveCommonExpressionsFromUseBases - Look through all of the uses in Bases, removing any common subexpressions from it. Anything truly common is removed, accumulated, and returned. This looks for things like (a+b+c) and (a+c+d) -> (a+c). The common expression is *removed* from the Bases.

Definition at line 917 of file LoopStrengthReduce.cpp.

References llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getIntegerSCEV(), llvm::Value::getType(), 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 886 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 93 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 137 of file LoopStrengthReduce.cpp.

bool Changed

Definition at line 119 of file LoopStrengthReduce.cpp.

SetVector<Instruction*> 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 141 of file LoopStrengthReduce.cpp.

DominatorTree* DT

Definition at line 115 of file LoopStrengthReduce.cpp.

Value* EmittedBase

EmittedBase - The actual value* to use for the base value of this operation. This is null if we should just use zero so far.

Definition at line 541 of file LoopStrengthReduce.cpp.

char ID [static]

Definition at line 148 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 537 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 95 of file LoopStrengthReduce.cpp.

Instruction* Inst

Inst - The instruction using the induction variable.

Definition at line 528 of file LoopStrengthReduce.cpp.

Referenced by AddReachableCodeToWorklist(), GatherConstantSetEQs(), GatherConstantSetNEs(), llvm::UnrollLoop(), and llvm::Interpreter::visitUnwindInst().

bool isUseOfPostIncrementedValue

Definition at line 67 of file LoopStrengthReduce.cpp.

std::vector<IVExpr> IVs

Definition at line 105 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 127 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 123 of file LoopStrengthReduce.cpp.

LoopInfo* LI

Definition at line 114 of file LoopStrengthReduce.cpp.

SCEVHandle Offset

Definition at line 59 of file LoopStrengthReduce.cpp.

Value* OperandValToReplace

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

Definition at line 61 of file LoopStrengthReduce.cpp.

PHINode* PHI

Definition at line 94 of file LoopStrengthReduce.cpp.

Referenced by llvm::PHINode::classof(), llvm::ComputeMaskedBits(), llvm::XCoreTargetLowering::EmitInstrWithCustomInserter(), llvm::X86TargetLowering::EmitInstrWithCustomInserter(), llvm::SparcTargetLowering::EmitInstrWithCustomInserter(), llvm::PPCTargetLowering::EmitInstrWithCustomInserter(), llvm::ARMTargetLowering::EmitInstrWithCustomInserter(), getConstantEvolvingPHI(), getNextStopPoint(), llvm::Instruction::getOpcodeName(), llvm::InlineFunction(), isUnmovableInstruction(), llvm::FastISel::SelectOperator(), and WriteInstruction().

ScalarEvolution* SE

SE - The current ScalarEvolution object.

Definition at line 116 of file LoopStrengthReduce.cpp.

SCEVHandle Stride

Definition at line 92 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 132 of file LoopStrengthReduce.cpp.

const TargetData* TD

Definition at line 117 of file LoopStrengthReduce.cpp.

const TargetLowering* TLI

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

Definition at line 145 of file LoopStrengthReduce.cpp.

const Type* UIntPtrTy

Definition at line 118 of file LoopStrengthReduce.cpp.

Instruction* User

Definition at line 60 of file LoopStrengthReduce.cpp.

Referenced by ChangeCalleesToFastCall(), and RemoveNestAttribute().

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 81 of file LoopStrengthReduce.cpp.

Referenced by llvm::SelectionDAG::ReplaceAllUsesOfValuesWith(), llvm::SelectionDAG::ReplaceAllUsesOfValueWith(), and llvm::UnrollLoop().

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