LLVM 17.0.0git
|
#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopeExit.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
Go to the source code of this file.
Macros | |
#define | SCEV_DEBUG_WITH_TYPE(TYPE, X) |
Functions | |
static bool | FactorOutConstant (const SCEV *&S, const SCEV *&Remainder, const SCEV *Factor, ScalarEvolution &SE, const DataLayout &DL) |
FactorOutConstant - Test if S is divisible by Factor, using signed division. | |
static void | SimplifyAddOperands (SmallVectorImpl< const SCEV * > &Ops, Type *Ty, ScalarEvolution &SE) |
SimplifyAddOperands - Sort and simplify a list of add operands. | |
static void | SplitAddRecs (SmallVectorImpl< const SCEV * > &Ops, Type *Ty, ScalarEvolution &SE) |
SplitAddRecs - Flatten a list of add operands, moving addrec start values out to the top level. | |
static const Loop * | PickMostRelevantLoop (const Loop *A, const Loop *B, DominatorTree &DT) |
PickMostRelevantLoop - Given two loops pick the one that's most relevant for SCEV expansion. | |
static bool | canBeCheaplyTransformed (ScalarEvolution &SE, const SCEVAddRecExpr *Phi, const SCEVAddRecExpr *Requested, bool &InvertStep) |
Check whether we can cheaply express the requested SCEV in terms of the available PHI SCEV by truncation and/or inversion of the step. | |
static bool | IsIncrementNSW (ScalarEvolution &SE, const SCEVAddRecExpr *AR) |
static bool | IsIncrementNUW (ScalarEvolution &SE, const SCEVAddRecExpr *AR) |
template<typename T > | |
static InstructionCost | costAndCollectOperands (const SCEVOperand &WorkItem, const TargetTransformInfo &TTI, TargetTransformInfo::TargetCostKind CostKind, SmallVectorImpl< SCEVOperand > &Worklist) |
#define SCEV_DEBUG_WITH_TYPE | ( | TYPE, | |
X | |||
) |
Definition at line 34 of file ScalarEvolutionExpander.cpp.
|
static |
Check whether we can cheaply express the requested SCEV in terms of the available PHI SCEV by truncation and/or inversion of the step.
Definition at line 1131 of file ScalarEvolutionExpander.cpp.
References llvm::ScalarEvolution::getEffectiveSCEVType(), llvm::Type::getIntegerBitWidth(), llvm::ScalarEvolution::getMinusSCEV(), llvm::SCEVAddRecExpr::getStart(), llvm::ScalarEvolution::getTruncateOrNoop(), llvm::SCEVAddRecExpr::getType(), and llvm::Type::isPointerTy().
|
static |
Definition at line 2082 of file ScalarEvolutionExpander.cpp.
References assert(), llvm::CmpInst::BAD_ICMP_PREDICATE, Cost, CostKind, llvm::count_if(), llvm::SmallVectorImpl< T >::emplace_back(), llvm::enumerate(), llvm::TargetTransformInfo::getArithmeticInstrCost(), llvm::TargetTransformInfo::getCastInstrCost(), llvm::TargetTransformInfo::getCmpSelInstrCost(), llvm_unreachable, llvm::CmpInst::makeCmpResultType(), llvm::max(), llvm::min(), llvm::TargetTransformInfo::None, llvm::SCEVOperand::S, llvm::scAddExpr, llvm::scAddRecExpr, llvm::scConstant, llvm::scCouldNotCompute, llvm::scMulExpr, llvm::scPtrToInt, llvm::scSequentialUMinExpr, llvm::scSignExtend, llvm::scSMaxExpr, llvm::scSMinExpr, llvm::scTruncate, llvm::scUDivExpr, llvm::scUMaxExpr, llvm::scUMinExpr, llvm::scUnknown, llvm::scVScale, and llvm::scZeroExtend.
|
static |
FactorOutConstant - Test if S is divisible by Factor, using signed division.
If so, update S with Factor divided out and return true. S need not be evenly divisible if a reasonable remainder can be computed.
Definition at line 294 of file ScalarEvolutionExpander.cpp.
References A, llvm::CallingConv::C, DL, FactorOutConstant(), llvm::SCEV::FlagNW, llvm::ConstantInt::get(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getAddRecExpr(), llvm::ScalarEvolution::getConstant(), llvm::ScalarEvolution::getContext(), llvm::ScalarEvolution::getMulExpr(), llvm::SCEV::getType(), llvm::SCEV::isOne(), llvm::SCEV::isZero(), and llvm::ConstantInt::isZero().
Referenced by FactorOutConstant().
|
static |
Definition at line 1165 of file ScalarEvolutionExpander.cpp.
References llvm::BitWidth, llvm::IntegerType::get(), llvm::ScalarEvolution::getAddExpr(), llvm::Type::getContext(), llvm::ScalarEvolution::getSignExtendExpr(), llvm::SCEVAddRecExpr::getStepRecurrence(), and llvm::SCEVAddRecExpr::getType().
|
static |
Definition at line 1179 of file ScalarEvolutionExpander.cpp.
References llvm::BitWidth, llvm::IntegerType::get(), llvm::ScalarEvolution::getAddExpr(), llvm::Type::getContext(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::SCEVAddRecExpr::getType(), and llvm::ScalarEvolution::getZeroExtendExpr().
|
static |
PickMostRelevantLoop - Given two loops pick the one that's most relevant for SCEV expansion.
If they are nested, this is the most nested. If they are neighboring, pick the later.
Definition at line 662 of file ScalarEvolutionExpander.cpp.
References A, B, and llvm::DominatorTree::dominates().
|
static |
SimplifyAddOperands - Sort and simplify a list of add operands.
NumAddRecs is the number of SCEVAddRecExprs present, which are kept at the end of the list.
Definition at line 367 of file ScalarEvolutionExpander.cpp.
References llvm::Add, llvm::SmallVectorImpl< T >::append(), llvm::append_range(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallVectorImpl< T >::clear(), llvm::SmallVectorBase< Size_T >::empty(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getConstant(), llvm::SCEV::isZero(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::SmallVectorBase< Size_T >::size().
Referenced by SplitAddRecs().
|
static |
SplitAddRecs - Flatten a list of add operands, moving addrec start values out to the top level.
For example, convert {a + b,+,c} to a, b, {0,+,d}. This helps expose more opportunities for folding parts of the expressions into GEP indices.
Definition at line 396 of file ScalarEvolutionExpander.cpp.
References A, llvm::Add, llvm::SmallVectorImpl< T >::append(), llvm::append_range(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallVectorBase< Size_T >::empty(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::SCEV::FlagNW, llvm::ScalarEvolution::getAddRecExpr(), llvm::ScalarEvolution::getConstant(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), SimplifyAddOperands(), and llvm::SmallVectorBase< Size_T >::size().