LLVM 20.0.0git |
#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/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/Debug.h"#include "llvm/Support/MathExtras.h"#include "llvm/Support/raw_ostream.h"#include "llvm/Transforms/Scalar/SimpleLoopUnswitch.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 exitvalues replaced") | |
| STATISTIC (NumLFTR, "Number of loop exit tests replaced") | |
| STATISTIC (NumElimExt, "Number ofIV sign/zero extends eliminated") | |
| STATISTIC (NumElimIV, "Number of congruent IVs eliminated") | |
| staticbool | ConvertToSInt (constAPFloat &APF, int64_t &IntVal) |
| Convert APF to an integer, if possible. | |
| static void | visitIVCast (CastInst *Cast,WideIVInfo &WI,ScalarEvolution *SE,constTargetTransformInfo *TTI) |
| Update information about the induction variable that is extended by this sign or zero extend operation. | |
| staticPHINode * | getLoopPhiForCounter (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. | |
| staticbool | isLoopExitTestBasedOn (Value *V,BasicBlock *ExitingBB) |
| Whether the current loop exit test is based on this value. | |
| staticbool | needsLFTR (Loop *L,BasicBlock *ExitingBB) |
| linearFunctionTestReplace policy. | |
| staticbool | hasConcreteDefImpl (Value *V,SmallPtrSetImpl<Value * > &Visited,unsigned Depth) |
| Recursive helper forhasConcreteDef(). | |
| staticbool | hasConcreteDef (Value *V) |
| Return true if the given value is concrete. | |
| staticbool | isLoopCounter (PHINode *Phi,Loop *L,ScalarEvolution *SE) |
| Return true if the given phi is a "counter" in L. | |
| staticPHINode * | FindLoopCounter (Loop *L,BasicBlock *ExitingBB,constSCEV *BECount,ScalarEvolution *SE,DominatorTree *DT) |
| Search the loop header for a loop counter (anadd rec w/step of one) suitable for use by LFTR. | |
| staticValue * | genLoopLimit (PHINode *IndVar,BasicBlock *ExitingBB,constSCEV *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) |
| staticConstant * | createFoldedExitCond (constLoop *L,BasicBlock *ExitingBB,bool IsTaken) |
| static void | foldExit (constLoop *L,BasicBlock *ExitingBB,bool IsTaken,SmallVectorImpl<WeakTrackingVH > &DeadInsts) |
| static void | replaceLoopPHINodesWithPreheaderValues (LoopInfo *LI,Loop *L,SmallVectorImpl<WeakTrackingVH > &DeadInsts,ScalarEvolution &SE) |
| staticValue * | createInvariantCond (constLoop *L,BasicBlock *ExitingBB,constScalarEvolution::LoopInvariantPredicate &LIP,SCEVExpander &Rewriter) |
| static std::optional<Value * > | createReplacement (ICmpInst *ICmp,constLoop *L,BasicBlock *ExitingBB,constSCEV *MaxIter,bool Inverted,bool SkipLastIter,ScalarEvolution *SE,SCEVExpander &Rewriter) |
| staticbool | optimizeLoopExitWithUnknownExitCount (constLoop *L,BranchInst *BI,BasicBlock *ExitingBB,constSCEV *MaxIter,bool SkipLastIter,ScalarEvolution *SE,SCEVExpander &Rewriter,SmallVectorImpl<WeakTrackingVH > &DeadInsts) |
Variables | |
| staticcl::opt<ReplaceExitVal > | ReplaceExitValue ("replexitval", cl::Hidden, cl::init(OnlyCheapRepl),cl::desc("Choose the strategy toreplace exitvalue in IndVarSimplify"),cl::values(clEnumValN(NeverRepl, "never", "neverreplace exit value"),clEnumValN(OnlyCheapRepl, "cheap", "onlyreplace exitvalue when the cost is cheap"),clEnumValN(UnusedIndVarInLoop, "unusedindvarinloop", "onlyreplace exitvalue when it is an unused " "induction variable in the loop and has cheap replacement cost"),clEnumValN(NoHardUse, "noharduse", "onlyreplace exitvalues when loop def likely dead"),clEnumValN(AlwaysRepl, "always", "alwaysreplace exitvalue whenever possible"))) |
| staticcl::opt<bool > | UsePostIncrementRanges ("indvars-post-increment-ranges", cl::Hidden,cl::desc("Use post increment control-dependent ranges in IndVarSimplify"), cl::init(true)) |
| staticcl::opt<bool > | DisableLFTR ("disable-lftr", cl::Hidden, cl::init(false),cl::desc("Disable LinearFunction Test Replace optimization")) |
| staticcl::opt<bool > | LoopPredication ("indvars-predicate-loops", cl::Hidden, cl::init(true),cl::desc("Predicate conditions in readonly loops")) |
| staticcl::opt<bool > | AllowIVWidening ("indvars-widen-indvars", cl::Hidden, cl::init(true),cl::desc("Allow widening of indvars to eliminate s/zext")) |
| #define DEBUG_TYPE "indvars" |
Definition at line83 of fileIndVarSimplify.cpp.
Convert APF to an integer, if possible.
Definition at line184 of fileIndVarSimplify.cpp.
Referencesllvm::APFloat::convertToInteger().
| static |
Definition at line1188 of fileIndVarSimplify.cpp.
Referencesllvm::BranchInst::getCondition(),llvm::BasicBlock::getTerminator(), andllvm::succ_begin().
Referenced bycreateReplacement(), andfoldExit().
| static |
Definition at line1243 of fileIndVarSimplify.cpp.
Referencesassert(),llvm::IRBuilderBase::CreateICmp(),llvm::BranchInst::getCondition(),llvm::Value::getName(),llvm::BasicBlock::getTerminator(),llvm::ScalarEvolution::LoopInvariantPredicate::LHS,llvm::ScalarEvolution::LoopInvariantPredicate::Pred,Rewriter,llvm::ScalarEvolution::LoopInvariantPredicate::RHS, andllvm::succ_begin().
Referenced bycreateReplacement().
| static |
Definition at line1262 of fileIndVarSimplify.cpp.
ReferencescreateFoldedExitCond(),createInvariantCond(),llvm::ScalarEvolution::evaluatePredicateAt(),llvm::CmpInst::getInversePredicate(),llvm::ScalarEvolution::getLoopInvariantExitCondDuringFirstIterations(),llvm::ScalarEvolution::getMinusOne(),llvm::ScalarEvolution::getMinusSCEV(),llvm::ScalarEvolution::getOne(),llvm::User::getOperand(),llvm::CmpInst::getPredicate(),llvm::ScalarEvolution::getSCEVAtScope(),llvm::BasicBlock::getTerminator(),llvm::ScalarEvolution::getTruncateExpr(),llvm::SCEV::getType(),llvm::ScalarEvolution::getTypeSizeInBits(),llvm::ScalarEvolution::getUMinFromMismatchedTypes(),llvm::ScalarEvolution::getZeroExtendExpr(),llvm::ScalarEvolution::isKnownPredicateAt(),LHS,Rewriter,RHS, andllvm::UMin.
Referenced byoptimizeLoopExitWithUnknownExitCount().
| 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 line833 of fileIndVarSimplify.cpp.
Referencesassert(),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(), andllvm::mustExecuteUBIfPoisonOnPathTo().
| static |
Definition at line1197 of fileIndVarSimplify.cpp.
ReferencescreateFoldedExitCond(),llvm::BasicBlock::getTerminator(), andreplaceExitCond().
| static |
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.
Definition at line913 of fileIndVarSimplify.cpp.
Referencesassert(),llvm::SCEVAddRecExpr::evaluateAtIteration(),llvm::SCEVAddRecExpr::getPostIncExpr(),llvm::ScalarEvolution::getSCEV(),llvm::SCEVAddRecExpr::getStart(),llvm::SCEVAddRecExpr::getStepRecurrence(),llvm::BasicBlock::getTerminator(),llvm::ScalarEvolution::getTruncateExpr(),llvm::SCEV::getType(),llvm::SCEVAddRecExpr::getType(),llvm::Value::getType(),llvm::ScalarEvolution::getTypeSizeInBits(),llvm::Type::isIntegerTy(),isLoopCounter(),llvm::ScalarEvolution::isLoopInvariant(),llvm::SCEV::isOne(), andRewriter.
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 line661 of fileIndVarSimplify.cpp.
Referencesllvm::User::getNumOperands(),llvm::Instruction::getOpcode(), andllvm::User::getOperand().
Referenced byisLoopCounter(), andneedsLFTR().
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 line795 of fileIndVarSimplify.cpp.
ReferenceshasConcreteDefImpl(), andllvm::SmallPtrSetImpl< PtrType >::insert().
Referenced byFindLoopCounter().
| static |
Recursive helper forhasConcreteDef().
Unfortunately, this currently boils down to checking that all operands are constant and listing instructions that may hide undef.
Definition at line762 of fileIndVarSimplify.cpp.
Referencesllvm::Depth,hasConcreteDefImpl(),I, andllvm::SmallPtrSetImpl< PtrType >::insert().
Referenced byhasConcreteDef(), andhasConcreteDefImpl().
| 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 line804 of fileIndVarSimplify.cpp.
Referencesassert(),llvm::SCEVAddRecExpr::getLoop(),getLoopPhiForCounter(),llvm::ScalarEvolution::getSCEV(),llvm::SCEVAddRecExpr::getStepRecurrence(),llvm::SCEVAddRecExpr::isAffine(),llvm::SCEV::isOne(), andllvm::ScalarEvolution::isSCEVable().
Referenced byFindLoopCounter(), andgenLoopLimit().
| 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 line699 of fileIndVarSimplify.cpp.
Referencesllvm::BranchInst::getCondition(),llvm::User::getOperand(), andllvm::BasicBlock::getTerminator().
Referenced byFindLoopCounter().
| static |
linearFunctionTestReplace policy.
Return true unless we can show that the current exit test is already sufficiently canonical.
Definition at line712 of fileIndVarSimplify.cpp.
Referencesassert(),Cond,llvm::BranchInst::getCondition(),getLoopPhiForCounter(),llvm::BasicBlock::getTerminator(),Idx,LHS,RHS, andstd::swap().
| static |
Definition at line1319 of fileIndVarSimplify.cpp.
Referencesassert(),llvm::ScalarEvolution::computeExitLimitFromCond(),llvm::SmallPtrSetImpl< PtrType >::count(),createReplacement(),llvm::dbgs(),llvm::SmallVectorBase< Size_T >::empty(),llvm::SmallPtrSetImpl< PtrType >::erase(),llvm::BranchInst::getCondition(),llvm::ScalarEvolution::getExitCount(),llvm::Value::getName(),llvm::ScalarEvolution::getNoopOrZeroExtend(),llvm::BranchInst::getSuccessor(),llvm::SCEV::getType(),llvm::ScalarEvolution::getWiderType(),llvm::Value::hasOneUse(),llvm::SmallPtrSetImpl< PtrType >::insert(),LHS,LLVM_DEBUG,llvm::PatternMatch::m_LogicalAnd(),llvm::PatternMatch::m_LogicalOr(),llvm::PatternMatch::m_Value(),llvm::PatternMatch::match(),llvm::SmallVectorImpl< T >::pop_back_val(),llvm::SmallVectorTemplateBase< T, bool >::push_back(),llvm::Value::replaceAllUsesWith(),Rewriter,RHS,llvm::SmallPtrSetImplBase::size(), andllvm::SmallVectorBase< Size_T >::size().
| static |
Definition at line1178 of fileIndVarSimplify.cpp.
Referencesllvm::dbgs(),llvm::SmallVectorImpl< T >::emplace_back(),llvm::BranchInst::getCondition(),LLVM_DEBUG, andllvm::BranchInst::setCondition().
Referenced byfoldExit().
| static |
Definition at line1204 of fileIndVarSimplify.cpp.
Referencesassert(),llvm::SmallVectorImpl< T >::emplace_back(),llvm::SmallVectorBase< Size_T >::empty(),llvm::ScalarEvolution::forgetValue(),llvm::PHINode::getIncomingValueForBlock(),I,llvm::SmallPtrSetImpl< PtrType >::insert(),llvm::SmallVectorImpl< T >::pop_back_val(),llvm::SmallVectorTemplateBase< T, bool >::push_back(),llvm::Value::replaceAllUsesWith(),llvm::LoopInfo::replacementPreservesLCSSAForm(),llvm::simplifyInstruction(), andllvm::Value::users().
| STATISTIC | ( | NumElimIV | , |
| "Number of congruent IVs eliminated" | |||
| ) |
| STATISTIC | ( | NumLFTR | , |
| "Number of loop exit tests replaced" | |||
| ) |
| STATISTIC | ( | NumReplaced | , |
| "Number of exitvalues replaced" | |||
| ) |
| STATISTIC | ( | NumWidened | , |
| "Number of indvars widened" | |||
| ) |
| 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 line509 of fileIndVarSimplify.cpp.
Referencesllvm::TargetTransformInfo::getArithmeticInstrCost(),llvm::Instruction::getDataLayout(),llvm::ScalarEvolution::getEffectiveSCEVType(),llvm::CastInst::getOpcode(),llvm::User::getOperand(),llvm::Value::getType(),llvm::ScalarEvolution::getTypeSizeInBits(),llvm::DataLayout::isLegalInteger(),llvm::WideIVInfo::IsSigned,llvm::WideIVInfo::NarrowIV, andllvm::WideIVInfo::WidestNativeType.
| static |
Referenced byllvm::IndVarSimplifyPass::run().
| static |
Referenced byllvm::rewriteLoopExitValues().
| static |
Referenced byllvm::createWideIV().
1.9.6