LLVM 19.0.0git
Macros | Functions | Variables
IndVarSimplify.cpp File Reference
#include "llvm/Transforms/Scalar/IndVarSimplify.h"
#include "llvm/ADT/APFloat.h"
#include "llvm/ADT/ArrayRef.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/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.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.
 
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.
 
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.
 
static bool isLoopExitTestBasedOn (Value *V, BasicBlock *ExitingBB)
 Whether the current loop exit test is based on this value.
 
static bool needsLFTR (Loop *L, BasicBlock *ExitingBB)
 linearFunctionTestReplace policy.
 
static bool hasConcreteDefImpl (Value *V, SmallPtrSetImpl< Value * > &Visited, unsigned Depth)
 Recursive helper for hasConcreteDef().
 
static bool hasConcreteDef (Value *V)
 Return true if the given value is concrete.
 
static bool isLoopCounter (PHINode *Phi, Loop *L, ScalarEvolution *SE)
 Return true if the given phi is a "counter" in L.
 
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.
 
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.
 
static void replaceExitCond (BranchInst *BI, Value *NewCond, SmallVectorImpl< WeakTrackingVH > &DeadInsts)
 
static ConstantcreateFoldedExitCond (const Loop *L, BasicBlock *ExitingBB, bool IsTaken)
 
static void foldExit (const Loop *L, BasicBlock *ExitingBB, bool IsTaken, SmallVectorImpl< WeakTrackingVH > &DeadInsts)
 
static void replaceLoopPHINodesWithPreheaderValues (LoopInfo *LI, Loop *L, SmallVectorImpl< WeakTrackingVH > &DeadInsts, ScalarEvolution &SE)
 
static ValuecreateInvariantCond (const Loop *L, BasicBlock *ExitingBB, const ScalarEvolution::LoopInvariantPredicate &LIP, SCEVExpander &Rewriter)
 
static std::optional< Value * > createReplacement (ICmpInst *ICmp, const Loop *L, BasicBlock *ExitingBB, const SCEV *MaxIter, bool Inverted, bool SkipLastIter, ScalarEvolution *SE, SCEVExpander &Rewriter)
 
static bool optimizeLoopExitWithUnknownExitCount (const Loop *L, BranchInst *BI, BasicBlock *ExitingBB, const SCEV *MaxIter, bool SkipLastIter, ScalarEvolution *SE, SCEVExpander &Rewriter, SmallVectorImpl< WeakTrackingVH > &DeadInsts)
 

Variables

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(UnusedIndVarInLoop, "unusedindvarinloop", "only replace exit value when it is an unused " "induction variable in the loop and has cheap replacement cost"), clEnumValN(NoHardUse, "noharduse", "only replace exit values when loop def likely dead"), 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"))
 
static cl::opt< boolLoopPredication ("indvars-predicate-loops", cl::Hidden, cl::init(true), cl::desc("Predicate conditions in read only loops"))
 
static cl::opt< boolAllowIVWidening ("indvars-widen-indvars", cl::Hidden, cl::init(true), cl::desc("Allow widening of indvars to eliminate s/zext"))
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "indvars"

Definition at line 85 of file IndVarSimplify.cpp.

Function Documentation

◆ ConvertToSInt()

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

Convert APF to an integer, if possible.

Definition at line 182 of file IndVarSimplify.cpp.

References llvm::APFloat::convertToInteger().

◆ createFoldedExitCond()

static Constant * createFoldedExitCond ( const Loop L,
BasicBlock ExitingBB,
bool  IsTaken 
)
static

◆ createInvariantCond()

static Value * createInvariantCond ( const Loop L,
BasicBlock ExitingBB,
const ScalarEvolution::LoopInvariantPredicate LIP,
SCEVExpander Rewriter 
)
static

◆ createReplacement()

static std::optional< Value * > createReplacement ( ICmpInst ICmp,
const Loop L,
BasicBlock ExitingBB,
const SCEV MaxIter,
bool  Inverted,
bool  SkipLastIter,
ScalarEvolution SE,
SCEVExpander Rewriter 
)
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 825 of file IndVarSimplify.cpp.

References assert(), Cond, DL, llvm::ScalarEvolution::getSCEV(), llvm::BasicBlock::getTerminator(), llvm::SCEV::getType(), llvm::Value::getType(), llvm::ScalarEvolution::getTypeSizeInBits(), hasConcreteDef(), I, llvm::isAlmostDeadIV(), isLoopCounter(), isLoopExitTestBasedOn(), llvm::SCEV::isZero(), and llvm::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 653 of file IndVarSimplify.cpp.

References llvm::User::getNumOperands(), llvm::Instruction::getOpcode(), and llvm::User::getOperand().

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

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

Referenced by hasConcreteDef(), and hasConcreteDefImpl().

◆ isLoopCounter()

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

Return true if the given phi is a "counter" in L.

A counter is an add recurance (of integer or pointer type) with an arbitrary start, and a step of 1. Note that L must have exactly one latch.

Definition at line 796 of file IndVarSimplify.cpp.

References assert(), llvm::SCEVAddRecExpr::getLoop(), getLoopPhiForCounter(), llvm::ScalarEvolution::getSCEV(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::SCEVAddRecExpr::isAffine(), llvm::SCEV::isOne(), and llvm::ScalarEvolution::isSCEVable().

Referenced by FindLoopCounter(), and genLoopLimit().

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

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

Referenced by FindLoopCounter().

◆ needsLFTR()

static bool needsLFTR ( Loop L,
BasicBlock ExitingBB 
)
static

linearFunctionTestReplace policy.

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

Definition at line 704 of file IndVarSimplify.cpp.

References assert(), Cond, llvm::BranchInst::getCondition(), getLoopPhiForCounter(), llvm::BasicBlock::getTerminator(), Idx, LHS, RHS, and std::swap().

◆ optimizeLoopExitWithUnknownExitCount()

static bool optimizeLoopExitWithUnknownExitCount ( const Loop L,
BranchInst BI,
BasicBlock ExitingBB,
const SCEV MaxIter,
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 ( LoopInfo LI,
Loop L,
SmallVectorImpl< WeakTrackingVH > &  DeadInsts,
ScalarEvolution SE 
)
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")) ( "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")) ( "disable-lftr"  ,
cl::Hidden  ,
cl::init(false)  ,
cl::desc("Disable Linear Function Test Replace optimization")   
)
static

◆ LoopPredication

cl::opt< bool > LoopPredication("indvars-predicate-loops", cl::Hidden, cl::init(true), cl::desc("Predicate conditions in read only loops")) ( "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( UnusedIndVarInLoop, "unusedindvarinloop", "only replace exit value when it is an unused " "induction variable in the loop and has cheap replacement cost"), clEnumValN(NoHardUse, "noharduse", "only replace exit values when loop def likely dead"), clEnumValN(AlwaysRepl, "always", "always replace exit value whenever possible"))) ( "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( UnusedIndVarInLoop, "unusedindvarinloop", "only replace exit value when it is an unused " "induction variable in the loop and has cheap replacement cost"), clEnumValN(NoHardUse, "noharduse", "only replace exit values when loop def likely dead"), clEnumValN(AlwaysRepl, "always", "always replace exit value whenever possible"))   
)
static

◆ UsePostIncrementRanges

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

Referenced by llvm::createWideIV().