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/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/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 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 PHINode * | 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. | |
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 PHINode * | FindLoopCounter (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 Value * | genLoopLimit (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 Constant * | createFoldedExitCond (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 Value * | createInvariantCond (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< 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"))) |
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")) |
#define DEBUG_TYPE "indvars" |
Definition at line 86 of file IndVarSimplify.cpp.
Convert APF to an integer, if possible.
Definition at line 187 of file IndVarSimplify.cpp.
References llvm::APFloat::convertToInteger().
|
static |
Definition at line 1191 of file IndVarSimplify.cpp.
References llvm::BranchInst::getCondition(), llvm::BasicBlock::getTerminator(), and llvm::succ_begin().
Referenced by createReplacement(), and foldExit().
|
static |
Definition at line 1246 of file IndVarSimplify.cpp.
References assert(), 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, and llvm::succ_begin().
Referenced by createReplacement().
|
static |
Definition at line 1265 of file IndVarSimplify.cpp.
References createFoldedExitCond(), 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, and llvm::UMin.
Referenced by optimizeLoopExitWithUnknownExitCount().
|
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 836 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().
|
static |
Definition at line 1200 of file IndVarSimplify.cpp.
References createFoldedExitCond(), llvm::BasicBlock::getTerminator(), and replaceExitCond().
|
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 line 916 of file IndVarSimplify.cpp.
References assert(), 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(), and Rewriter.
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 664 of file IndVarSimplify.cpp.
References llvm::User::getNumOperands(), llvm::Instruction::getOpcode(), and llvm::User::getOperand().
Referenced by isLoopCounter(), 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 798 of file IndVarSimplify.cpp.
References hasConcreteDefImpl(), and llvm::SmallPtrSetImpl< PtrType >::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 765 of file IndVarSimplify.cpp.
References llvm::Depth, hasConcreteDefImpl(), I, and llvm::SmallPtrSetImpl< PtrType >::insert().
Referenced by hasConcreteDef(), and hasConcreteDefImpl().
|
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 807 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().
|
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 702 of file IndVarSimplify.cpp.
References llvm::BranchInst::getCondition(), llvm::User::getOperand(), and llvm::BasicBlock::getTerminator().
Referenced by FindLoopCounter().
|
static |
linearFunctionTestReplace policy.
Return true unless we can show that the current exit test is already sufficiently canonical.
Definition at line 715 of file IndVarSimplify.cpp.
References assert(), Cond, llvm::BranchInst::getCondition(), getLoopPhiForCounter(), llvm::BasicBlock::getTerminator(), Idx, LHS, RHS, and std::swap().
|
static |
Definition at line 1322 of file IndVarSimplify.cpp.
References assert(), 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(), and llvm::SmallVectorBase< Size_T >::size().
|
static |
Definition at line 1181 of file IndVarSimplify.cpp.
References llvm::dbgs(), llvm::SmallVectorImpl< T >::emplace_back(), llvm::BranchInst::getCondition(), LLVM_DEBUG, and llvm::BranchInst::setCondition().
Referenced by foldExit().
|
static |
Definition at line 1207 of file IndVarSimplify.cpp.
References assert(), 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(), and llvm::Value::users().
STATISTIC | ( | NumElimIV | , |
"Number of congruent IVs eliminated" | |||
) |
STATISTIC | ( | NumLFTR | , |
"Number of loop exit tests replaced" | |||
) |
STATISTIC | ( | NumReplaced | , |
"Number of exit values 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 line 512 of file IndVarSimplify.cpp.
References llvm::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, and llvm::WideIVInfo::WidestNativeType.
|
static |
Referenced by llvm::IndVarSimplifyPass::run().
|
static |
|
static |
|
static |
Referenced by llvm::rewriteLoopExitValues().
|
static |
Referenced by llvm::createWideIV().