LLVM  9.0.0svn
Macros | Enumerations | Functions | Variables
IndVarSimplify.cpp File Reference
#include "llvm/Transforms/Scalar/IndVarSimplify.h"
#include "llvm/ADT/APFloat.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/None.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Scalar/LoopPassManager.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/SimplifyIndVar.h"
#include <cassert>
#include <cstdint>
#include <utility>

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "indvars"
 

Enumerations

enum  ReplaceExitVal { NeverRepl, OnlyCheapRepl, AlwaysRepl }
 

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")
 
static InstructiongetInsertPointForUses (Instruction *User, Value *Def, DominatorTree *DT, LoopInfo *LI)
 Determine the insertion point for this user. More...
 
static bool ConvertToSInt (const APFloat &APF, int64_t &IntVal)
 Convert APF to an integer, if possible. More...
 
static void visitIVCast (CastInst *Cast, WideIVInfo &WI, ScalarEvolution *SE, const TargetTransformInfo *TTI)
 Update information about the induction variable that is extended by this sign or zero extend operation. More...
 
static void truncateIVUse (NarrowIVDefUse DU, DominatorTree *DT, LoopInfo *LI)
 This IV user cannot be widen. More...
 
static bool canExpandBackedgeTakenCount (Loop *L, ScalarEvolution *SE, SCEVExpander &Rewriter)
 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. More...
 
static PHINodegetLoopPhiForCounter (Value *IncV, Loop *L)
 Given an Value which is hoped to be part of an add recurance in the given loop, return the associated Phi node if so. More...
 
static ICmpInstgetLoopTest (Loop *L)
 Given a loop with one backedge and one exit, return the ICmpInst controlling the sole loop exit. More...
 
static bool needsLFTR (Loop *L)
 linearFunctionTestReplace policy. More...
 
static bool hasConcreteDefImpl (Value *V, SmallPtrSetImpl< Value *> &Visited, unsigned Depth)
 Recursive helper for hasConcreteDef(). More...
 
static bool hasConcreteDef (Value *V)
 Return true if the given value is concrete. More...
 
static bool AlmostDeadIV (PHINode *Phi, BasicBlock *LatchBlock, Value *Cond)
 Return true if this IV has any uses other than the (soon to be rewritten) loop exit test. More...
 
static bool isLoopCounter (PHINode *Phi, Loop *L, ScalarEvolution *SE)
 Return true if the given phi is a "counter" in L. More...
 
static PHINodeFindLoopCounter (Loop *L, const SCEV *BECount, ScalarEvolution *SE)
 Search the loop header for a loop counter (anadd rec w/step of one) suitable for use by LFTR. More...
 
static ValuegenLoopLimit (PHINode *IndVar, const SCEV *IVCount, Loop *L, SCEVExpander &Rewriter, ScalarEvolution *SE)
 Insert an IR expression which computes the value held by the IV IndVar (which must be an loop counter w/unit stride) after the backedge of loop L is taken IVCount times. More...
 
 INITIALIZE_PASS_BEGIN (IndVarSimplifyLegacyPass, "indvars", "Induction Variable Simplification", false, false) INITIALIZE_PASS_END(IndVarSimplifyLegacyPass
 

Variables

static cl::opt< boolVerifyIndvars ("verify-indvars", cl::Hidden, cl::desc("Verify the ScalarEvolution result after running indvars"))
 
static cl::opt< ReplaceExitValReplaceExitValue ("replexitval", cl::Hidden, cl::init(OnlyCheapRepl), cl::desc("Choose the strategy to replace exit value in IndVarSimplify"), cl::values(clEnumValN(NeverRepl, "never", "never replace exit value"), clEnumValN(OnlyCheapRepl, "cheap", "only replace exit value when the cost is cheap"), clEnumValN(AlwaysRepl, "always", "always replace exit value whenever possible")))
 
static cl::opt< boolUsePostIncrementRanges ("indvars-post-increment-ranges", cl::Hidden, cl::desc("Use post increment control-dependent ranges in IndVarSimplify"), cl::init(true))
 
static cl::opt< boolDisableLFTR ("disable-lftr", cl::Hidden, cl::init(false), cl::desc("Disable Linear Function Test Replace optimization"))
 
 indvars
 
Induction Variable Simplification
 
Induction Variable false
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "indvars"

Definition at line 88 of file IndVarSimplify.cpp.

Enumeration Type Documentation

◆ ReplaceExitVal

Enumerator
NeverRepl 
OnlyCheapRepl 
AlwaysRepl 

Definition at line 103 of file IndVarSimplify.cpp.

Function Documentation

◆ AlmostDeadIV()

static bool AlmostDeadIV ( PHINode Phi,
BasicBlock LatchBlock,
Value Cond 
)
static

Return true if this IV has any uses other than the (soon to be rewritten) loop exit test.

Definition at line 2148 of file IndVarSimplify.cpp.

◆ canExpandBackedgeTakenCount()

static bool canExpandBackedgeTakenCount ( Loop L,
ScalarEvolution SE,
SCEVExpander Rewriter 
)
static

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.

Definition at line 1985 of file IndVarSimplify.cpp.

References llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::LoopBase< BlockT, LoopT >::getExitingBlock(), llvm::BasicBlock::getTerminator(), llvm::SCEVExpander::isHighCostExpansion(), and llvm::SCEV::isZero().

Referenced by genLoopLimit().

◆ ConvertToSInt()

static bool ConvertToSInt ( const APFloat APF,
int64_t &  IntVal 
)
static

Convert APF to an integer, if possible.

Definition at line 273 of file IndVarSimplify.cpp.

References llvm::PHINode::addIncoming(), assert(), llvm::CmpInst::BAD_ICMP_PREDICATE, llvm::SCEVExpander::clearInsertPoint(), llvm::MCID::Compare, llvm::LoopBase< BlockT, LoopT >::contains(), llvm::APFloat::convertToInteger(), llvm::PHINode::Create(), CreateAdd(), llvm::dbgs(), llvm::dyn_cast(), E, llvm::SmallVectorImpl< T >::emplace_back(), llvm::SmallVectorBase::empty(), llvm::Instruction::eraseFromParent(), llvm::SCEVExpander::expandCodeFor(), llvm::CmpInst::FCMP_OEQ, llvm::CmpInst::FCMP_OGE, llvm::CmpInst::FCMP_OGT, llvm::CmpInst::FCMP_OLE, llvm::CmpInst::FCMP_OLT, llvm::CmpInst::FCMP_ONE, llvm::CmpInst::FCMP_UEQ, llvm::CmpInst::FCMP_UGE, llvm::CmpInst::FCMP_UGT, llvm::CmpInst::FCMP_ULE, llvm::CmpInst::FCMP_ULT, llvm::CmpInst::FCMP_UNE, llvm::ConstantInt::get(), llvm::UndefValue::get(), llvm::Value::getContext(), llvm::BasicBlock::getFirstInsertionPt(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::Type::getInt32Ty(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::Value::getName(), llvm::PHINode::getNumIncomingValues(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::CmpInst::getPredicate(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), llvm::LoopBase< BlockT, LoopT >::getUniqueExitBlocks(), llvm::ConstantFP::getValueAPF(), H, llvm::Value::hasOneUse(), I, llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_SLT, llvm::SmallPtrSetImpl< PtrType >::insert(), Int32Ty, llvm::BranchInst::isConditional(), llvm::SCEVExpander::isHighCostExpansion(), llvm::isInstructionTriviallyDead(), llvm::isInt< 32 >(), llvm::Loop::isLCSSAForm(), llvm::Loop::isRecursivelyLCSSAForm(), llvm::isSafeToExpand(), LLVM_DEBUG, llvm::makeMutableArrayRef(), llvm::Instruction::mayHaveSideEffects(), OnlyCheapRepl, llvm::APFloatBase::opOK, P, llvm::BasicBlock::phis(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::RecursivelyDeleteTriviallyDeadInstructions(), llvm::Value::replaceAllUsesWith(), Rewriter, llvm::APFloatBase::rmTowardZero, llvm::PHINode::setIncomingValue(), llvm::SmallVectorBase::size(), llvm::Value::takeName(), llvm::Value::use_empty(), llvm::Instruction::user_back(), llvm::Value::user_begin(), and llvm::Value::users().

◆ FindLoopCounter()

static PHINode* FindLoopCounter ( Loop L,
const SCEV BECount,
ScalarEvolution SE 
)
static

Search the loop header for a loop counter (anadd rec w/step of one) suitable for use by LFTR.

If multiple counters are available, select the "best" one based profitable heuristics.

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.

Definition at line 2191 of file IndVarSimplify.cpp.

References llvm::SCEV::getType(), and llvm::ScalarEvolution::getTypeSizeInBits().

◆ genLoopLimit()

static Value* genLoopLimit ( PHINode IndVar,
const SCEV IVCount,
Loop L,
SCEVExpander Rewriter,
ScalarEvolution SE 
)
static

◆ getInsertPointForUses()

static Instruction* getInsertPointForUses ( Instruction User,
Value Def,
DominatorTree DT,
LoopInfo LI 
)
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. A nullptr can be returned if no viable location is found: it may happen if User is a PHI and Def only comes to this PHI from unreachable blocks.

Definition at line 223 of file IndVarSimplify.cpp.

References assert(), llvm::tgtok::Def, llvm::DominatorTree::dominates(), llvm::dyn_cast(), llvm::DominatorTreeBase< NodeT, IsPostDom >::findNearestCommonDominator(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::PHINode::getNumIncomingValues(), llvm::Instruction::getParent(), llvm::BasicBlock::getTerminator(), llvm::DominatorTree::isReachableFromEntry(), and llvm_unreachable.

Referenced by truncateIVUse().

◆ getLoopPhiForCounter()

static PHINode* getLoopPhiForCounter ( Value IncV,
Loop L 
)
static

Given an Value which is hoped to be part of an add recurance in the given loop, return the associated Phi node if so.

Otherwise, return null. Note that this is less general than SCEVs AddRec checking.

Definition at line 2012 of file IndVarSimplify.cpp.

References llvm::MCID::Add, llvm::dyn_cast(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::User::getNumOperands(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::Loop::isLoopInvariant(), and LLVM_FALLTHROUGH.

Referenced by isLoopCounter().

◆ getLoopTest()

static ICmpInst* getLoopTest ( Loop L)
static

Given a loop with one backedge and one exit, return the ICmpInst controlling the sole loop exit.

There is no guarantee that the exiting block is also the latch.

Definition at line 2051 of file IndVarSimplify.cpp.

References assert(), llvm::dyn_cast(), llvm::BranchInst::getCondition(), llvm::LoopBase< BlockT, LoopT >::getExitingBlock(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), and llvm::BasicBlock::getTerminator().

◆ hasConcreteDef()

static bool hasConcreteDef ( Value V)
static

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 2140 of file IndVarSimplify.cpp.

References hasConcreteDefImpl(), and llvm::SmallPtrSetImpl< PtrType >::insert().

◆ hasConcreteDefImpl()

static bool hasConcreteDefImpl ( Value V,
SmallPtrSetImpl< Value *> &  Visited,
unsigned  Depth 
)
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 2107 of file IndVarSimplify.cpp.

References llvm::dyn_cast(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::Instruction::mayReadFromMemory(), and llvm::User::operands().

Referenced by hasConcreteDef().

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN ( IndVarSimplifyLegacyPass  ,
"indvars"  ,
"Induction Variable Simplification ,
false  ,
false   
)

◆ isLoopCounter()

static bool isLoopCounter ( PHINode Phi,
Loop L,
ScalarEvolution SE 
)
static

◆ needsLFTR()

static bool needsLFTR ( Loop L)
static

linearFunctionTestReplace policy.

Return true unless we can show that the current exit test is already sufficiently canonical.

Definition at line 2067 of file IndVarSimplify.cpp.

◆ STATISTIC() [1/5]

STATISTIC ( NumWidened  ,
"Number of indvars widened"   
)

◆ STATISTIC() [2/5]

STATISTIC ( NumReplaced  ,
"Number of exit values replaced"   
)

◆ STATISTIC() [3/5]

STATISTIC ( NumLFTR  ,
"Number of loop exit tests replaced"   
)

◆ STATISTIC() [4/5]

STATISTIC ( NumElimExt  ,
"Number of IV sign/  zero 
)

◆ STATISTIC() [5/5]

STATISTIC ( NumElimIV  ,
"Number of congruent IVs eliminated"   
)

◆ truncateIVUse()

static void truncateIVUse ( NarrowIVDefUse  DU,
DominatorTree DT,
LoopInfo LI 
)
static

This IV user cannot be widen.

Replace this use of the original narrow IV with a truncation of the new wide IV to isolate and eliminate the narrow IV.

Definition at line 1308 of file IndVarSimplify.cpp.

References llvm::MCID::Add, llvm::PHINode::addIncoming(), assert(), llvm::SmallVectorTemplateCommon< T >::back(), llvm::BasicBlock::begin(), C, llvm::LoopBase< BlockT, LoopT >::contains(), llvm::BinaryOperator::Create(), llvm::PHINode::Create(), llvm::IRBuilder< T, Inserter >::CreateTrunc(), llvm::dbgs(), llvm::dyn_cast(), llvm::SmallVectorBase::empty(), llvm::SCEVExpander::expandCodeFor(), llvm::findDbgValues(), llvm::BasicBlock::front(), llvm::MetadataAsValue::get(), llvm::ValueAsMetadata::get(), llvm::LoopBase< BlockT, LoopT >::getBlocks(), llvm::BasicBlock::getFirstInsertionPt(), llvm::LoopBase< BlockT, LoopT >::getHeader(), getInsertPointForUses(), llvm::CmpInst::getInversePredicate(), llvm::SCEVAddRecExpr::getLoop(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::Intrinsic::getName(), llvm::Value::getName(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::SCEV::getType(), llvm::Value::getType(), llvm::OverflowingBinaryOperator::hasNoSignedWrap(), llvm::OverflowingBinaryOperator::hasNoUnsignedWrap(), llvm::SCEVExpander::hoistIVInc(), I, llvm::CmpInst::ICMP_SGE, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::APInt::isNonNegative(), llvm::CmpInst::isSigned(), LLVM_DEBUG, llvm::SPII::Load, llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_NSWAdd(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), llvm::make_range(), llvm::ConstantRange::makeAllowedICmpRegion(), llvm::PatternMatch::match(), P, llvm::SmallVectorTemplateBase< T >::pop_back(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::Value::replaceAllUsesWith(), llvm::Instruction::setDebugLoc(), llvm::simplifyUsersOfIV(), llvm::Unknown, llvm::Value::users(), llvm::Value::uses(), and visitIVCast().

◆ visitIVCast()

static void visitIVCast ( CastInst Cast,
WideIVInfo &  WI,
ScalarEvolution SE,
const TargetTransformInfo TTI 
)
static

Update information about the induction variable that is extended by this sign or zero extend operation.

This is used to determine the final width of the IV before actually widening it.

Definition at line 858 of file IndVarSimplify.cpp.

References llvm::MCID::Add, assert(), llvm::BinaryOperator::Create(), llvm::IRBuilder< T, Inserter >::CreateSExt(), llvm::IRBuilder< T, Inserter >::CreateZExt(), llvm::dbgs(), llvm::tgtok::Def, llvm::dyn_cast(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::TargetTransformInfo::getArithmeticInstrCost(), llvm::Module::getDataLayout(), llvm::ScalarEvolution::getEffectiveSCEVType(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::SCEVAddRecExpr::getLoop(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::Instruction::getModule(), llvm::Value::getName(), llvm::Instruction::getOpcode(), llvm::CastInst::getOpcode(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::BasicBlock::getTerminator(), llvm::SCEV::getType(), llvm::Value::getType(), llvm::ScalarEvolution::getTypeSizeInBits(), llvm::OverflowingBinaryOperator::hasNoSignedWrap(), llvm::OverflowingBinaryOperator::hasNoUnsignedWrap(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::ConstantRange::intersectWith(), llvm::DataLayout::isLegalInteger(), llvm::Loop::isLoopInvariant(), LLVM_DEBUG, llvm_unreachable, llvm::None, llvm::IRBuilderBase::SetInsertPoint(), std::swap(), and llvm::Unknown.

Referenced by truncateIVUse().

Variable Documentation

◆ DisableLFTR

cl::opt<bool> DisableLFTR("disable-lftr", cl::Hidden, cl::init(false), cl::desc("Disable Linear Function Test Replace optimization"))
static

◆ false

Induction Variable false

Definition at line 2750 of file IndVarSimplify.cpp.

◆ indvars

indvars

Definition at line 2750 of file IndVarSimplify.cpp.

◆ ReplaceExitValue

cl::opt<ReplaceExitVal> ReplaceExitValue("replexitval", cl::Hidden, cl::init(OnlyCheapRepl), cl::desc("Choose the strategy to replace exit value in IndVarSimplify"), cl::values(clEnumValN(NeverRepl, "never", "never replace exit value"), clEnumValN(OnlyCheapRepl, "cheap", "only replace exit value when the cost is cheap"), clEnumValN(AlwaysRepl, "always", "always replace exit value whenever possible")))
static

◆ Simplification

Induction Variable Simplification

Definition at line 2750 of file IndVarSimplify.cpp.

◆ UsePostIncrementRanges

cl::opt<bool> UsePostIncrementRanges("indvars-post-increment-ranges", cl::Hidden, cl::desc("Use post increment control-dependent ranges in IndVarSimplify"), cl::init(true))
static

◆ VerifyIndvars

cl::opt<bool> VerifyIndvars("verify-indvars", cl::Hidden, cl::desc("Verify the ScalarEvolution result after running indvars"))
static