LLVM 17.0.0git
Macros | Functions
ScalarEvolutionExpander.cpp File Reference
#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"
Include dependency graph for ScalarEvolutionExpander.cpp:

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 LoopPickMostRelevantLoop (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)
 

Macro Definition Documentation

◆ SCEV_DEBUG_WITH_TYPE

#define SCEV_DEBUG_WITH_TYPE (   TYPE,
  X 
)

Definition at line 34 of file ScalarEvolutionExpander.cpp.

Function Documentation

◆ canBeCheaplyTransformed()

static bool canBeCheaplyTransformed ( ScalarEvolution SE,
const SCEVAddRecExpr Phi,
const SCEVAddRecExpr Requested,
bool InvertStep 
)
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().

◆ costAndCollectOperands()

template<typename T >
static InstructionCost costAndCollectOperands ( const SCEVOperand WorkItem,
const TargetTransformInfo TTI,
TargetTransformInfo::TargetCostKind  CostKind,
SmallVectorImpl< SCEVOperand > &  Worklist 
)
static

◆ FactorOutConstant()

static bool FactorOutConstant ( const SCEV *&  S,
const SCEV *&  Remainder,
const SCEV Factor,
ScalarEvolution SE,
const DataLayout DL 
)
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().

◆ IsIncrementNSW()

static bool IsIncrementNSW ( ScalarEvolution SE,
const SCEVAddRecExpr AR 
)
static

◆ IsIncrementNUW()

static bool IsIncrementNUW ( ScalarEvolution SE,
const SCEVAddRecExpr AR 
)
static

◆ PickMostRelevantLoop()

static const Loop * PickMostRelevantLoop ( const Loop A,
const Loop B,
DominatorTree DT 
)
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().

◆ SimplifyAddOperands()

static void SimplifyAddOperands ( SmallVectorImpl< const SCEV * > &  Ops,
Type Ty,
ScalarEvolution SE 
)
static

◆ SplitAddRecs()

static void SplitAddRecs ( SmallVectorImpl< const SCEV * > &  Ops,
Type Ty,
ScalarEvolution SE 
)
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().