LLVM API Documentation

LoopStrengthReduce.cpp File Reference

#include "llvm/Transforms/Scalar.h"
#include "llvm/Constants.h"
#include "llvm/Instructions.h"
#include "llvm/Type.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/LoopInfo.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/Statistic.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Visibility.h"
#include "llvm/Target/TargetLowering.h"
#include <algorithm>
#include <iostream>
#include <set>

Include dependency graph for LoopStrengthReduce.cpp:

Go to the source code of this file.

Defines

#define DEBUG_TYPE   "loop-reduce"

Functions

FunctionPassllvm::createLoopStrengthReducePass (const TargetLowering *TLI)
static bool getSCEVStartAndStride (const SCEVHandle &SH, Loop *L, SCEVHandle &Start, SCEVHandle &Stride)
static bool IVUseShouldUsePostIncValue (Instruction *User, Instruction *IV, Loop *L, ETForest *EF, Pass *P)
static bool isTargetConstant (const SCEVHandle &V, const TargetLowering *TLI)
static void MoveLoopVariantsToImediateField (SCEVHandle &Val, SCEVHandle &Imm, Loop *L)
static void MoveImmediateValues (const TargetLowering *TLI, SCEVHandle &Val, SCEVHandle &Imm, bool isAddress, Loop *L)
static void SeparateSubExprs (std::vector< SCEVHandle > &SubExprs, SCEVHandle Expr)
static SCEVHandle RemoveCommonExpressionsFromUseBases (std::vector< BasedUser > &Uses)
static bool isZero (SCEVHandle &V)

Variables

Statistic NumReduced ("loop-reduce","Number of GEPs strength reduced")
Statistic NumInserted ("loop-reduce","Number of PHIs inserted")
Statistic NumVariable ("loop-reduce","Number of PHIs with variable strides")
RegisterOpt< 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 
) [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 293 of file LoopStrengthReduce.cpp.

References DEBUG, llvm::Loop::getHeader(), llvm::SCEVAddRecExpr::getLoop(), llvm::Value::getName(), llvm::SCEVAddRecExpr::getOperand(), llvm::SCEVAddRecExpr::isAffine(), and Stride.

static bool isTargetConstant ( const SCEVHandle V,
const TargetLowering TLI 
) [static]

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

Definition at line 613 of file LoopStrengthReduce.cpp.

References llvm::TargetLowering::isLegalAddressImmediate(), TLI, and V.

Referenced by MoveImmediateValues().

static bool isZero ( SCEVHandle V  )  [static]

isZero - returns true if the scalar evolution expression is zero.

Definition at line 863 of file LoopStrengthReduce.cpp.

References V.

static bool IVUseShouldUsePostIncValue ( Instruction User,
Instruction IV,
Loop L,
ETForest EF,
Pass P 
) [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 347 of file LoopStrengthReduce.cpp.

References llvm::Loop::contains(), llvm::ETForestBase::dominates(), EF, llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::Loop::getLoopLatch(), llvm::PHINode::getNumIncomingValues(), llvm::Instruction::getParent(), llvm::SplitCriticalEdge(), and User.

static void MoveImmediateValues ( const TargetLowering TLI,
SCEVHandle Val,
SCEVHandle Imm,
bool  isAddress,
Loop L 
) [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 677 of file LoopStrengthReduce.cpp.

References Imm, isTargetConstant(), Ops, TLI, and Val.

static void MoveLoopVariantsToImediateField ( SCEVHandle Val,
SCEVHandle Imm,
Loop L 
) [static]

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

Definition at line 637 of file LoopStrengthReduce.cpp.

References Imm, Ops, and Val.

static SCEVHandle RemoveCommonExpressionsFromUseBases ( std::vector< BasedUser > &  Uses  )  [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 787 of file LoopStrengthReduce.cpp.

References Base, and SeparateSubExprs().

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

IncrementAddExprUses - Decompose the specified expression into its added subexpressions, and increment SubExpressionUseCounts for each of these decomposed parts.

Definition at line 756 of file LoopStrengthReduce.cpp.

References Ops.

Referenced by RemoveCommonExpressionsFromUseBases().


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

SCEVHandle Base

Definition at line 85 of file LoopStrengthReduce.cpp.

std::map<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 132 of file LoopStrengthReduce.cpp.

bool Changed

Definition at line 114 of file LoopStrengthReduce.cpp.

std::set<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 136 of file LoopStrengthReduce.cpp.

ETForest* EF

Definition at line 110 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 478 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 474 of file LoopStrengthReduce.cpp.

Referenced by llvm::SelectionDAG::getZeroExtendInReg(), MoveImmediateValues(), and MoveLoopVariantsToImediateField().

Value* IncV

Definition at line 87 of file LoopStrengthReduce.cpp.

Instruction* Inst

Inst - The instruction using the induction variable.

Definition at line 465 of file LoopStrengthReduce.cpp.

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

bool isUseOfPostIncrementedValue

Definition at line 485 of file LoopStrengthReduce.cpp.

bool isUseOfPostIncrementedValue

Definition at line 59 of file LoopStrengthReduce.cpp.

std::vector<IVExpr> IVs

Definition at line 100 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 122 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 118 of file LoopStrengthReduce.cpp.

LoopInfo* LI

Definition at line 109 of file LoopStrengthReduce.cpp.

Statistic NumInserted("loop-reduce","Number of PHIs inserted") [static]

Statistic NumReduced("loop-reduce","Number of GEPs strength reduced") [static]

Statistic NumVariable("loop-reduce","Number of PHIs with variable strides") [static]

SCEVHandle Offset

Definition at line 51 of file LoopStrengthReduce.cpp.

Value* OperandValToReplace

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

Definition at line 469 of file LoopStrengthReduce.cpp.

Value* OperandValToReplace

Definition at line 53 of file LoopStrengthReduce.cpp.

PHINode* PHI

Definition at line 86 of file LoopStrengthReduce.cpp.

ScalarEvolution* SE

Definition at line 111 of file LoopStrengthReduce.cpp.

SCEVHandle Stride

Definition at line 84 of file LoopStrengthReduce.cpp.

Referenced by getSCEVStartAndStride().

std::vector<SCEVHandle> 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 127 of file LoopStrengthReduce.cpp.

const TargetData* TD

Definition at line 112 of file LoopStrengthReduce.cpp.

const TargetLowering* TLI

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

Definition at line 140 of file LoopStrengthReduce.cpp.

const Type* UIntPtrTy

Definition at line 113 of file LoopStrengthReduce.cpp.

Referenced by EmitGEPOffset(), and OptimizeGEPExpression().

Instruction* User

Definition at line 52 of file LoopStrengthReduce.cpp.

Referenced by llvm::SDNode::addUser(), IVUseShouldUsePostIncValue(), llvm::PassManagerT< llvm::BBTraits >::markPassUsed(), OptimizeNoopCopyExpression(), llvm::PPCTargetLowering::PerformDAGCombine(), and llvm::SDNode::removeUser().

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

Referenced by llvm::SelectionDAG::ReplaceAllUsesOfValueWith().

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