LLVM API Documentation
#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>
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 DEBUG_TYPE "loop-reduce" |
Definition at line 22 of file LoopStrengthReduce.cpp.
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] |
getAccessType - Return the type of the memory being accessed.
Definition at line 301 of file LoopStrengthReduce.cpp.
References llvm::Value::getType(), II, llvm::Intrinsic::x86_sse2_storel_dq, llvm::Intrinsic::x86_sse2_storeu_dq, llvm::Intrinsic::x86_sse2_storeu_pd, and llvm::Intrinsic::x86_sse_storeu_ps.
Referenced by MoveImmediateValues(), and RemoveCommonExpressionsFromUseBases().
| 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] |
isAddressUse - Returns true if the specified instruction is using the specified value as an address.
Definition at line 274 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 IsImmFoldedIntoAddrMode | ( | GlobalValue * | GV, | |
| int64_t | Offset, | |||
| const Type * | AccessTy, | |||
| std::vector< BasedUser > & | UsersToProcess, | |||
| const TargetLowering * | TLI | |||
| ) | [static] |
Definition at line 1471 of file LoopStrengthReduce.cpp.
References llvm::TargetLowering::AddrMode::BaseGV, llvm::TargetLowering::AddrMode::BaseOffs, llvm::SmallVectorImpl< T >::clear(), and isUseOfPostIncrementedValue.
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] |
MoveLoopVariantsToImmediateField - Move any subexpressions from Val that are loop varying to the Imm operand.
Definition at line 571 of file LoopStrengthReduce.cpp.
References llvm::SmallVectorImpl< T >::empty(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getAddRecExpr(), llvm::ScalarEvolution::getIntegerSCEV(), llvm::SCEV::getType(), llvm::SCEV::isLoopInvariant(), llvm::SmallVectorImpl< T >::push_back(), llvm::SmallVectorImpl< T >::reserve(), and Start.
| 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] |
Definition at line 1333 of file LoopStrengthReduce.cpp.
References PartitionByIsUseOfPostIncrementedValue(), and std::swap().
| 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" | ||||
| ) |
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.
| SmallVector<WeakVH, 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 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.
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.
Inst - The instruction using the induction variable.
Definition at line 335 of file LoopStrengthReduce.cpp.
Referenced by llvm::FindAvailableLoadedValue(), GatherConstantSetEQs(), GatherConstantSetNEs(), llvm::MSILWriter::printBasicBlock(), llvm::MSILWriter::printLocalVariables(), RemoveCommonExpressionsFromUseBases(), llvm::UnrollLoop(), ValueIsOnlyUsedLocallyOrStoredToOneGlobal(), and llvm::Interpreter::visitUnwindInst().
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().
Definition at line 71 of file LoopStrengthReduce.cpp.
Referenced by llvm::PHINode::classof(), llvm::ComputeMaskedBits(), llvm::XCoreTargetLowering::EmitInstrWithCustomInserter(), llvm::X86TargetLowering::EmitInstrWithCustomInserter(), llvm::SystemZTargetLowering::EmitInstrWithCustomInserter(), llvm::SparcTargetLowering::EmitInstrWithCustomInserter(), llvm::PPCTargetLowering::EmitInstrWithCustomInserter(), llvm::PIC16TargetLowering::EmitInstrWithCustomInserter(), llvm::MSP430TargetLowering::EmitInstrWithCustomInserter(), llvm::ARMTargetLowering::EmitInstrWithCustomInserter(), getConstantEvolvingPHI(), getNextStopPoint(), llvm::Instruction::getOpcodeName(), HasPHIUses(), llvm::InlineFunction(), llvm::Instruction::isSafeToSpeculativelyExecute(), isUnmovableInstruction(), llvm::PointerMayBeCaptured(), llvm::MSILWriter::printBasicBlock(), llvm::FastISel::SelectOperator(), and WriteInstruction().
| const ScalarEvolution* SE |
Definition at line 69 of file LoopStrengthReduce.cpp.
Referenced by llvm::IVUsers::AddUsersIfInteresting(), and llvm::IVUsers::print().
| SmallSet<const SCEV *, 4> StrideNoReuse |
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.
| const TargetLowering* TLI |
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] |