LLVM API Documentation
#include "llvm/Transforms/Scalar.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Type.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetLibraryInfo.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/SimplifyIndVar.h"
Go to the source code of this file.
Macros | |
#define | DEBUG_TYPE "indvars" |
Functions | |
STATISTIC (NumWidened,"Number of indvars widened") | |
STATISTIC (NumReplaced,"Number of exit values replaced") | |
STATISTIC (NumLFTR,"Number of loop exit tests replaced") | |
STATISTIC (NumElimExt,"Number of IV sign/zero extends eliminated") | |
STATISTIC (NumElimIV,"Number of congruent IVs eliminated") | |
INITIALIZE_PASS_BEGIN (IndVarSimplify,"indvars","Induction Variable Simplification", false, false) INITIALIZE_PASS_END(IndVarSimplify | |
static Instruction * | getInsertPointForUses (Instruction *User, Value *Def, DominatorTree *DT) |
static bool | ConvertToSInt (const APFloat &APF, int64_t &IntVal) |
ConvertToSInt - Convert APF to an integer, if possible. More... | |
static bool | isLoopInvariant (Value *V, const Loop *L, const DominatorTree *DT) |
static bool | isHighCostExpansion (const SCEV *S, BranchInst *BI, SmallPtrSet< const SCEV *, 8 > &Processed, ScalarEvolution *SE) |
static bool | canExpandBackedgeTakenCount (Loop *L, ScalarEvolution *SE) |
static PHINode * | getLoopPhiForCounter (Value *IncV, Loop *L, DominatorTree *DT) |
static ICmpInst * | getLoopTest (Loop *L) |
Return the compare guarding the loop latch, or NULL for unrecognized tests. More... | |
static bool | needsLFTR (Loop *L, DominatorTree *DT) |
static bool | hasConcreteDefImpl (Value *V, SmallPtrSet< Value *, 8 > &Visited, unsigned Depth) |
static bool | hasConcreteDef (Value *V) |
static bool | AlmostDeadIV (PHINode *Phi, BasicBlock *LatchBlock, Value *Cond) |
static PHINode * | FindLoopCounter (Loop *L, const SCEV *BECount, ScalarEvolution *SE, DominatorTree *DT, const DataLayout *TD) |
static Value * | genLoopLimit (PHINode *IndVar, const SCEV *IVCount, Loop *L, SCEVExpander &Rewriter, ScalarEvolution *SE) |
Variables | |
static cl::opt< bool > | VerifyIndvars ("verify-indvars", cl::Hidden, cl::desc("Verify the ScalarEvolution result after running indvars")) |
indvars | |
Induction Variable | Simplification |
Induction Variable | false |
#define DEBUG_TYPE "indvars" |
Definition at line 27 of file IndVarSimplify.cpp.
|
static |
AlmostDeadIV - Return true if this IV has any uses other than the (soon to be rewritten) loop exit test.
Definition at line 1358 of file IndVarSimplify.cpp.
References llvm::PHINode::getBasicBlockIndex(), llvm::PHINode::getIncomingValue(), llvm::Value::use_begin(), and llvm::Value::use_end().
Referenced by FindLoopCounter().
|
static |
canExpandBackedgeTakenCount - Return true if this loop's backedge taken count expression can be safely and cheaply expanded into an instruction sequence that can be used by LinearFunctionTestReplace.
TODO: This fails for pointer-type loop counters with greater than one byte strides, consequently preventing LFTR from running. For the purpose of LFTR we could skip this check in the case that the LFTR loop counter (chosen by FindLoopCounter) is also pointer type. Instead, we could directly convert the loop test to an inequality test by checking the target data's alignment of element types (given that the initial pointer value originates from or is used by ABI constrained operation, as opposed to inttoptr/ptrtoint). However, we don't yet have a strong motivation for converting loop tests into inequality tests.
Definition at line 1202 of file IndVarSimplify.cpp.
References llvm::dyn_cast(), llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::LoopBase< N, M >::getExitingBlock(), isHighCostExpansion(), and llvm::SCEV::isZero().
ConvertToSInt - Convert APF to an integer, if possible.
Definition at line 221 of file IndVarSimplify.cpp.
References llvm::APFloat::convertToInteger(), llvm::APFloat::opOK, and llvm::APFloat::rmTowardZero.
|
static |
FindLoopCounter - Find an affine IV in canonical form.
BECount may be an i8* pointer type. The pointer difference is already valid count without scaling the address stride, so it remains a pointer expression as far as SCEV is concerned.
Currently only valid for LFTR. See the comments on hasConcreteDef below.
FIXME: Accept -1 stride and set IVLimit = IVInit - BECount
FIXME: Accept non-unit stride as long as SCEV can reduce BECount * Stride. This is difficult in general for SCEV because of potential overflow. But we could at least handle constant BECounts.
Definition at line 1388 of file IndVarSimplify.cpp.
References AlmostDeadIV(), llvm::dyn_cast(), llvm::PHINode::getBasicBlockIndex(), llvm::LoopBase< N, M >::getExitingBlock(), llvm::LoopBase< N, M >::getHeader(), llvm::PHINode::getIncomingValue(), llvm::SCEVAddRecExpr::getLoop(), llvm::LoopBase< N, M >::getLoopLatch(), getLoopPhiForCounter(), getLoopTest(), llvm::ScalarEvolution::getSCEV(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::SCEV::getType(), llvm::Value::getType(), llvm::SCEVNAryExpr::getType(), llvm::ScalarEvolution::getTypeSizeInBits(), hasConcreteDef(), I, llvm::SCEVAddRecExpr::isAffine(), llvm::DataLayout::isLegalInteger(), llvm::SCEV::isOne(), llvm::Type::isPointerTy(), llvm::ScalarEvolution::isSCEVable(), and llvm::SCEV::isZero().
|
static |
genLoopLimit - Help LinearFunctionTestReplace by generating a value that holds the RHS of the new loop test.
Definition at line 1470 of file IndVarSimplify.cpp.
References llvm::IRBuilder< preserveNames, T, Inserter >::CreateGEP(), llvm::dyn_cast(), llvm::SCEVExpander::expandCodeFor(), llvm::ScalarEvolution::getAddExpr(), llvm::Value::getContext(), llvm::ScalarEvolution::getEffectiveSCEVType(), llvm::LoopBase< N, M >::getExitingBlock(), llvm::PHINode::getIncomingValueForBlock(), llvm::Type::getInt64Ty(), llvm::SCEVAddRecExpr::getLoop(), llvm::LoopBase< N, M >::getLoopPreheader(), llvm::ScalarEvolution::getSCEV(), llvm::ScalarEvolution::getSizeOfExpr(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::ScalarEvolution::getTruncateExpr(), llvm::ScalarEvolution::getTruncateOrZeroExtend(), llvm::SCEV::getType(), llvm::Value::getType(), llvm::ScalarEvolution::getTypeSizeInBits(), llvm::SCEVAddRecExpr::isAffine(), llvm::ScalarEvolution::isLoopInvariant(), llvm::SCEV::isOne(), llvm::Type::isPointerTy(), and llvm::SCEV::isZero().
|
static |
Determine the insertion point for this user. By default, insert immediately before the user. SCEVExpander or LICM will hoist loop invariants out of the loop. For PHI nodes, there may be multiple uses, so compute the nearest common dominator for the incoming blocks.
Definition at line 190 of file IndVarSimplify.cpp.
References llvm::tgtok::Def, llvm::DominatorTree::dominates(), llvm::dyn_cast(), llvm::DominatorTree::findNearestCommonDominator(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), llvm::Instruction::getParent(), llvm::BasicBlock::getTerminator(), and llvm::TargetOpcode::PHI.
|
static |
getLoopPhiForCounter - Return the loop header phi IFF IncV adds a loop invariant value to the phi.
Definition at line 1225 of file IndVarSimplify.cpp.
References llvm::dyn_cast(), llvm::LoopBase< N, M >::getHeader(), llvm::User::getNumOperands(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::Instruction::getParent(), and isLoopInvariant().
Referenced by FindLoopCounter(), and needsLFTR().
Return the compare guarding the loop latch, or NULL for unrecognized tests.
Definition at line 1261 of file IndVarSimplify.cpp.
References llvm::dyn_cast(), llvm::BranchInst::getCondition(), llvm::LoopBase< N, M >::getExitingBlock(), and llvm::LoopBase< N, M >::getLoopLatch().
Referenced by FindLoopCounter(), and needsLFTR().
Return true if the given value is concrete. We must prove that undef can never reach it.
TODO: If we decide that this is a good approach to checking for undef, we may factor it into a common location.
Definition at line 1350 of file IndVarSimplify.cpp.
References hasConcreteDefImpl(), and llvm::SmallPtrSet< PtrType, SmallSize >::insert().
Referenced by FindLoopCounter().
|
static |
Recursive helper for hasConcreteDef(). Unfortunately, this currently boils down to checking that all operands are constant and listing instructions that may hide undef.
Definition at line 1317 of file IndVarSimplify.cpp.
References llvm::dyn_cast(), I, llvm::SmallPtrSet< PtrType, SmallSize >::insert(), llvm::Instruction::mayReadFromMemory(), llvm::User::op_begin(), and llvm::User::op_end().
Referenced by hasConcreteDef().
INITIALIZE_PASS_BEGIN | ( | IndVarSimplify | , |
"indvars" | , | ||
"Induction Variable Simplification" | , | ||
false | , | ||
false | |||
) |
|
static |
Check for expressions that ScalarEvolution generates to compute BackedgeTakenInfo. If these expressions have not been reduced, then expanding them may incur additional cost (albeit in the loop preheader).
Definition at line 1143 of file IndVarSimplify.cpp.
References llvm::dyn_cast(), llvm::BranchInst::getCondition(), llvm::ScalarEvolution::getConstant(), llvm::ScalarEvolution::getMinusSCEV(), llvm::User::getOperand(), llvm::ScalarEvolution::getSCEV(), llvm::SCEV::getType(), I, and llvm::SmallPtrSet< PtrType, SmallSize >::insert().
Referenced by canExpandBackedgeTakenCount().
|
static |
isLoopInvariant - Perform a quick domtree based check for loop invariance assuming that V is used within the loop. LoopInfo::isLoopInvariant() seems gratuitous for this purpose.
Definition at line 762 of file IndVarSimplify.cpp.
References llvm::dyn_cast(), llvm::LoopBase< N, M >::getHeader(), llvm::Instruction::getParent(), and llvm::DominatorTree::properlyDominates().
Referenced by llvm::DependenceAnalysis::depends(), getLoopPhiForCounter(), llvm::DependenceAnalysis::getSplitIteration(), and needsLFTR().
|
static |
needsLFTR - LinearFunctionTestReplace policy. Return true unless we can show that the current exit test is already sufficiently canonical.
Definition at line 1277 of file IndVarSimplify.cpp.
References llvm::dyn_cast(), llvm::PHINode::getBasicBlockIndex(), llvm::PHINode::getIncomingValue(), llvm::LoopBase< N, M >::getLoopLatch(), getLoopPhiForCounter(), getLoopTest(), llvm::User::getOperand(), llvm::CmpInst::getPredicate(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, isLoopInvariant(), and std::swap().
STATISTIC | ( | NumWidened | , |
"Number of indvars widened" | |||
) |
STATISTIC | ( | NumReplaced | , |
"Number of exit values replaced" | |||
) |
STATISTIC | ( | NumLFTR | , |
"Number of loop exit tests replaced" | |||
) |
STATISTIC | ( | NumElimExt | , |
"Number of IV sign/zero extends eliminated" | |||
) |
STATISTIC | ( | NumElimIV | , |
"Number of congruent IVs eliminated" | |||
) |
Induction Variable false |
Definition at line 127 of file IndVarSimplify.cpp.
indvars |
Definition at line 127 of file IndVarSimplify.cpp.
Induction Variable Simplification |
Definition at line 127 of file IndVarSimplify.cpp.