LLVM  14.0.0git
Macros | 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/SmallSet.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/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.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/InitializePasses.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/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/ScalarEvolutionExpander.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"
 

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 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 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 bool isLoopExitTestBasedOn (Value *V, BasicBlock *ExitingBB)
 Whether the current loop exit test is based on this value. More...
 
static bool needsLFTR (Loop *L, BasicBlock *ExitingBB)
 linearFunctionTestReplace policy. More...
 
static bool mustExecuteUBIfPoisonOnPathTo (Instruction *Root, Instruction *OnPathTo, DominatorTree *DT)
 Return true if undefined behavior would provable be executed on the path to OnPathTo if Root produced a posion result. 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, BasicBlock *ExitingBB, const SCEV *BECount, ScalarEvolution *SE, DominatorTree *DT)
 Search the loop header for a loop counter (anadd rec w/step of one) suitable for use by LFTR. More...
 
static ValuegenLoopLimit (PHINode *IndVar, BasicBlock *ExitingBB, const SCEV *ExitCount, bool UsePostInc, 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 ExitCount times. More...
 
static void replaceExitCond (BranchInst *BI, Value *NewCond, SmallVectorImpl< WeakTrackingVH > &DeadInsts)
 
static void foldExit (const Loop *L, BasicBlock *ExitingBB, bool IsTaken, SmallVectorImpl< WeakTrackingVH > &DeadInsts)
 
static void replaceLoopPHINodesWithPreheaderValues (Loop *L, SmallVectorImpl< WeakTrackingVH > &DeadInsts)
 
static void replaceWithInvariantCond (const Loop *L, BasicBlock *ExitingBB, ICmpInst::Predicate InvariantPred, const SCEV *InvariantLHS, const SCEV *InvariantRHS, SCEVExpander &Rewriter, SmallVectorImpl< WeakTrackingVH > &DeadInsts)
 
static bool optimizeLoopExitWithUnknownExitCount (const Loop *L, BranchInst *BI, BasicBlock *ExitingBB, const SCEV *MaxIter, bool Inverted, bool SkipLastIter, ScalarEvolution *SE, SCEVExpander &Rewriter, SmallVectorImpl< WeakTrackingVH > &DeadInsts)
 
 INITIALIZE_PASS_BEGIN (IndVarSimplifyLegacyPass, "indvars", "Induction Variable Simplification", false, false) INITIALIZE_PASS_END(IndVarSimplifyLegacyPass
 

Variables

static cl::opt< bool > VerifyIndvars ("verify-indvars", cl::Hidden, cl::desc("Verify the ScalarEvolution result after running indvars. Has no " "effect in release builds. (Note: this adds additional SCEV " "queries potentially changing the analysis result)"))
 
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(NoHardUse, "noharduse", "only replace exit values when loop def likely dead"), clEnumValN(AlwaysRepl, "always", "always replace exit value whenever possible")))
 
static cl::opt< bool > UsePostIncrementRanges ("indvars-post-increment-ranges", cl::Hidden, cl::desc("Use post increment control-dependent ranges in IndVarSimplify"), cl::init(true))
 
static cl::opt< bool > DisableLFTR ("disable-lftr", cl::Hidden, cl::init(false), cl::desc("Disable Linear Function Test Replace optimization"))
 
static cl::opt< bool > LoopPredication ("indvars-predicate-loops", cl::Hidden, cl::init(true), cl::desc("Predicate conditions in read only loops"))
 
static cl::opt< bool > AllowIVWidening ("indvars-widen-indvars", cl::Hidden, cl::init(true), cl::desc("Allow widening of indvars to eliminate s/zext"))
 
 indvars
 
Induction Variable Simplification
 
Induction Variable false
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "indvars"

Definition at line 94 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 851 of file IndVarSimplify.cpp.

References Cond, llvm::PHINode::getBasicBlockIndex(), llvm::PHINode::getIncomingValue(), and llvm::Value::users().

Referenced by FindLoopCounter().

◆ ConvertToSInt()

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

◆ FindLoopCounter()

static PHINode* FindLoopCounter ( Loop L,
BasicBlock ExitingBB,
const SCEV BECount,
ScalarEvolution SE,
DominatorTree DT 
)
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 895 of file IndVarSimplify.cpp.

References AlmostDeadIV(), assert(), llvm::BasicBlock::begin(), Cond, DL, llvm::Module::getDataLayout(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingValueForBlock(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::BasicBlock::getModule(), llvm::ScalarEvolution::getSCEV(), llvm::BasicBlock::getTerminator(), llvm::SCEV::getType(), llvm::Value::getType(), llvm::ScalarEvolution::getTypeSizeInBits(), hasConcreteDef(), I, llvm::Type::isIntegerTy(), isLoopCounter(), isLoopExitTestBasedOn(), llvm::Type::isPointerTy(), llvm::SCEV::isZero(), and mustExecuteUBIfPoisonOnPathTo().

◆ foldExit()

static void foldExit ( const Loop L,
BasicBlock ExitingBB,
bool  IsTaken,
SmallVectorImpl< WeakTrackingVH > &  DeadInsts 
)
static

◆ genLoopLimit()

static Value* genLoopLimit ( PHINode IndVar,
BasicBlock ExitingBB,
const SCEV ExitCount,
bool  UsePostInc,
Loop L,
SCEVExpander Rewriter,
ScalarEvolution SE 
)
static

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

References llvm::MCID::Add, 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(), and needsLFTR().

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

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

Referenced by FindLoopCounter().

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

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

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

◆ isLoopExitTestBasedOn()

static bool isLoopExitTestBasedOn ( Value V,
BasicBlock ExitingBB 
)
static

Whether the current loop exit test is based on this value.

Currently this is limited to a direct use in the loop condition.

Definition at line 705 of file IndVarSimplify.cpp.

References llvm::BranchInst::getCondition(), llvm::User::getOperand(), and llvm::BasicBlock::getTerminator().

Referenced by FindLoopCounter().

◆ mustExecuteUBIfPoisonOnPathTo()

static bool mustExecuteUBIfPoisonOnPathTo ( Instruction Root,
Instruction OnPathTo,
DominatorTree DT 
)
static

Return true if undefined behavior would provable be executed on the path to OnPathTo if Root produced a posion result.

Note that this doesn't say anything about whether OnPathTo is actually executed or whether Root is actually poison. This can be used to assess whether a new use of Root can be added at a location which is control equivalent with OnPathTo (such as immediately before it) without introducing UB which didn't previously exist. Note that a false result conveys no information.

Definition at line 772 of file IndVarSimplify.cpp.

References llvm::DominatorTree::dominates(), I, llvm::SmallSet< T, N, C >::insert(), llvm::mustTriggerUB(), llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::propagatesPoison().

Referenced by FindLoopCounter().

◆ needsLFTR()

static bool needsLFTR ( Loop L,
BasicBlock ExitingBB 
)
static

◆ optimizeLoopExitWithUnknownExitCount()

static bool optimizeLoopExitWithUnknownExitCount ( const Loop L,
BranchInst BI,
BasicBlock ExitingBB,
const SCEV MaxIter,
bool  Inverted,
bool  SkipLastIter,
ScalarEvolution SE,
SCEVExpander Rewriter,
SmallVectorImpl< WeakTrackingVH > &  DeadInsts 
)
static

◆ replaceExitCond()

static void replaceExitCond ( BranchInst BI,
Value NewCond,
SmallVectorImpl< WeakTrackingVH > &  DeadInsts 
)
static

◆ replaceLoopPHINodesWithPreheaderValues()

static void replaceLoopPHINodesWithPreheaderValues ( Loop L,
SmallVectorImpl< WeakTrackingVH > &  DeadInsts 
)
static

◆ replaceWithInvariantCond()

static void replaceWithInvariantCond ( const Loop L,
BasicBlock ExitingBB,
ICmpInst::Predicate  InvariantPred,
const SCEV InvariantLHS,
const SCEV InvariantRHS,
SCEVExpander Rewriter,
SmallVectorImpl< WeakTrackingVH > &  DeadInsts 
)
static

◆ STATISTIC() [1/5]

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

◆ STATISTIC() [2/5]

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

◆ STATISTIC() [3/5]

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

◆ STATISTIC() [4/5]

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

◆ STATISTIC() [5/5]

STATISTIC ( NumWidened  ,
"Number of indvars widened"   
)

◆ visitIVCast()

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

Variable Documentation

◆ AllowIVWidening

cl::opt<bool> AllowIVWidening("indvars-widen-indvars", cl::Hidden, cl::init(true), cl::desc("Allow widening of indvars to eliminate s/zext"))
static

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

◆ indvars

indvars

Definition at line 2129 of file IndVarSimplify.cpp.

◆ LoopPredication

cl::opt<bool> LoopPredication("indvars-predicate-loops", cl::Hidden, cl::init(true), cl::desc("Predicate conditions in read only loops"))
static

◆ 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(NoHardUse, "noharduse", "only replace exit values when loop def likely dead"), clEnumValN(AlwaysRepl, "always", "always replace exit value whenever possible")))
static

◆ Simplification

Induction Variable Simplification

Definition at line 2130 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

Referenced by llvm::createWideIV().

◆ VerifyIndvars

cl::opt<bool> VerifyIndvars("verify-indvars", cl::Hidden, cl::desc("Verify the ScalarEvolution result after running indvars. Has no " "effect in release builds. (Note: this adds additional SCEV " "queries potentially changing the analysis result)"))
static