LLVM API Documentation

LoopStrengthReduce.cpp File Reference

#include "llvm/Transforms/Scalar.h"
#include "llvm/Constants.h"
#include "llvm/Instructions.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/LLVMContext.h"
#include "llvm/Type.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/IVUsers.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Transforms/Utils/AddrModeMatcher.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/ValueHandle.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetLowering.h"
#include <algorithm>

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 IV uses 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")
 STATISTIC (NumImmSunk,"Number of common expr immediates sunk into uses")
 STATISTIC (NumLoopCond,"Number of loop terminating conds optimized")
Pass * llvm::createLoopStrengthReducePass (const TargetLowering *TLI=0)
static bool containsAddRecFromDifferentLoop (const SCEV *S, Loop *L)
static bool isAddressUse (Instruction *Inst, Value *OperandVal)
static const Type * getAccessType (const Instruction *Inst)
 getAccessType - Return the type of the memory being accessed.
static bool fitsInAddressMode (const SCEV *const &V, const Type *AccessTy, const TargetLowering *TLI, bool HasBaseReg)
static void MoveLoopVariantsToImmediateField (const SCEV *&Val, const SCEV *&Imm, Loop *L, ScalarEvolution *SE)
static void MoveImmediateValues (const TargetLowering *TLI, const Type *AccessTy, const SCEV *&Val, const SCEV *&Imm, bool isAddress, Loop *L, ScalarEvolution *SE)
static void MoveImmediateValues (const TargetLowering *TLI, Instruction *User, const SCEV *&Val, const SCEV *&Imm, bool isAddress, Loop *L, ScalarEvolution *SE)
static void SeparateSubExprs (SmallVector< const SCEV *, 16 > &SubExprs, const SCEV *Expr, ScalarEvolution *SE)
static const SCEV * RemoveCommonExpressionsFromUseBases (std::vector< BasedUser > &Uses, ScalarEvolution *SE, Loop *L, const TargetLowering *TLI)
static bool PartitionByIsUseOfPostIncrementedValue (const BasedUser &Val)
static bool isNonConstantNegative (const SCEV *const &Expr)
static PHINode * InsertAffinePhi (const SCEV *Start, const SCEV *Step, Instruction *IVIncInsertPt, const Loop *L, SCEVExpander &Rewriter)
static void SortUsersToProcess (std::vector< BasedUser > &UsersToProcess)
static Instruction * FindIVIncInsertPt (std::vector< BasedUser > &UsersToProcess, const Loop *L)
static bool IsImmFoldedIntoAddrMode (GlobalValue *GV, int64_t Offset, const Type *AccessTy, std::vector< BasedUser > &UsersToProcess, const TargetLowering *TLI)

Variables

static cl::opt< bool > EnableFullLSRMode ("enable-full-lsr", cl::init(false), cl::Hidden)
static RegisterPass
< LoopStrengthReduce > 
X ("loop-reduce","Loop Strength Reduction")


Define Documentation

#define DEBUG_TYPE   "loop-reduce"

Definition at line 22 of file LoopStrengthReduce.cpp.


Function Documentation

static bool containsAddRecFromDifferentLoop ( const SCEV *  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 237 of file LoopStrengthReduce.cpp.

References containsAddRecFromDifferentLoop(), DE, and llvm::LoopInfo::isNotAlreadyContainedIn().

static Instruction* FindIVIncInsertPt ( std::vector< BasedUser > &  UsersToProcess,
const Loop *  L 
) [static]

FindIVIncInsertPt - Return the location to insert the increment instruction. If the only use if a use of postinc value, (must be the loop termination condition), then insert it just before the use.

Definition at line 1404 of file LoopStrengthReduce.cpp.

References llvm::LoopBase< BlockT, LoopT >::contains(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), and llvm::Instruction::getParent().

static bool fitsInAddressMode ( const SCEV *const &  V,
const Type *  AccessTy,
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 539 of file LoopStrengthReduce.cpp.

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

Referenced by MoveImmediateValues(), and RemoveCommonExpressionsFromUseBases().

static const Type* getAccessType ( const Instruction *  Inst  )  [static]

static PHINode* InsertAffinePhi ( const SCEV *  Start,
const SCEV *  Step,
Instruction *  IVIncInsertPt,
const Loop *  L,
SCEVExpander &  Rewriter 
) [static]

InsertAffinePhi Create and insert a PHI node for an induction variable with the specified start and step values in the specified loop.

If NegateStride is true, the stride should be negated by using a subtract instead of an add.

Return the created phi node.

Definition at line 1288 of file LoopStrengthReduce.cpp.

References llvm::PHINode::addIncoming(), llvm::SCEVExpander::expandCodeFor(), llvm::ScalarEvolution::getEffectiveSCEVType(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::ScalarEvolution::getNegativeSCEV(), llvm::BasicBlock::getTerminator(), llvm::SCEV::getType(), Header, llvm::SCEV::isLoopInvariant(), isNonConstantNegative(), Preheader, and llvm::SCEVExpander::SE.

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

static bool IsImmFoldedIntoAddrMode ( GlobalValue *  GV,
int64_t  Offset,
const Type *  AccessTy,
std::vector< BasedUser > &  UsersToProcess,
const TargetLowering *  TLI 
) [static]

static bool isNonConstantNegative ( const SCEV *const &  Expr  )  [static]

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

Definition at line 1103 of file LoopStrengthReduce.cpp.

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

Referenced by InsertAffinePhi().

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

Definition at line 689 of file LoopStrengthReduce.cpp.

References getAccessType(), and MoveImmediateValues().

static void MoveImmediateValues ( const TargetLowering *  TLI,
const Type *  AccessTy,
const SCEV *&  Val,
const SCEV *&  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 611 of file LoopStrengthReduce.cpp.

References llvm::SmallVectorImpl< T >::empty(), fitsInAddressMode(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getAddRecExpr(), llvm::ScalarEvolution::getIntegerSCEV(), llvm::ScalarEvolution::getMulExpr(), llvm::SCEV::getType(), llvm::SCEV::isLoopInvariant(), llvm::SmallVectorImpl< T >::push_back(), llvm::SmallVectorImpl< T >::reserve(), and Start.

Referenced by MoveImmediateValues().

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

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

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

Definition at line 1097 of file LoopStrengthReduce.cpp.

Referenced by SortUsersToProcess().

static const SCEV* 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 738 of file LoopStrengthReduce.cpp.

References llvm::SmallVectorImpl< T >::begin(), llvm::SmallVectorImpl< T >::clear(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::SmallVectorImpl< T >::empty(), llvm::SmallVectorImpl< T >::erase(), fitsInAddressMode(), getAccessType(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getIntegerSCEV(), llvm::ScalarEvolution::getMinusSCEV(), llvm::Value::getType(), Inst, isAddressUse(), OperandValToReplace, llvm::SmallVectorImpl< T >::push_back(), SeparateSubExprs(), llvm::SmallVectorImpl< T >::size(), and std::swap().

static void SeparateSubExprs ( SmallVector< const SCEV *, 16 > &  SubExprs,
const SCEV *  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 701 of file LoopStrengthReduce.cpp.

References llvm::ScalarEvolution::getAddRecExpr(), llvm::ScalarEvolution::getIntegerSCEV(), llvm::SCEV::getType(), llvm::SCEV::isZero(), and llvm::SmallVectorImpl< T >::push_back().

Referenced by RemoveCommonExpressionsFromUseBases().

static void SortUsersToProcess ( std::vector< BasedUser > &  UsersToProcess  )  [static]

STATISTIC ( NumLoopCond  ,
"Number of loop terminating conds optimized"   
)

STATISTIC ( NumImmSunk  ,
"Number of common expr immediates sunk into uses"   
)

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 IV uses strength reduced"   
)


Variable Documentation

const SCEV* 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 70 of file LoopStrengthReduce.cpp.

Definition at line 92 of file LoopStrengthReduce.cpp.

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

Definition at line 104 of file LoopStrengthReduce.cpp.

Referenced by llvm::RecursivelyDeleteTriviallyDeadInstructions().

Definition at line 90 of file LoopStrengthReduce.cpp.

cl::opt<bool> EnableFullLSRMode("enable-full-lsr", cl::init(false), cl::Hidden) [static]

char ID [static]

Definition at line 111 of file LoopStrengthReduce.cpp.

const SCEV* 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. This is also sometimes used for loop-variant values that must be added inside the loop.

Definition at line 345 of file LoopStrengthReduce.cpp.

Definition at line 356 of file LoopStrengthReduce.cpp.

Referenced by IsImmFoldedIntoAddrMode().

Definition at line 88 of file LoopStrengthReduce.cpp.

std::vector<IVExpr> IVs

Definition at line 80 of file LoopStrengthReduce.cpp.

std::map<const SCEV *, IVsOfOneStride> IVsByStride

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

Definition at line 96 of file LoopStrengthReduce.cpp.

Definition at line 89 of file LoopStrengthReduce.cpp.

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

Definition at line 339 of file LoopStrengthReduce.cpp.

Referenced by RemoveCommonExpressionsFromUseBases().

Phi - The induction variable that performs the striding that should be used for this user.

Definition at line 349 of file LoopStrengthReduce.cpp.

Referenced by llvm::MSILWriter::printPHICopy().

SE - The current ScalarEvolution object.

Definition at line 91 of file LoopStrengthReduce.cpp.

const SCEV* Stride

StrideNoReuse - Keep track of all the strides whose ivs cannot be reused (nor should they be rewritten to reuse other strides).

Definition at line 100 of file LoopStrengthReduce.cpp.

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

Definition at line 108 of file LoopStrengthReduce.cpp.

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