LLVM  6.0.0svn
Namespaces | Functions
ScalarEvolutionExpander.cpp File Reference
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
Include dependency graph for ScalarEvolutionExpander.cpp:

Go to the source code of this file.

Namespaces

 llvm
 Compute iterated dominance frontiers using a linear time algorithm.
 

Functions

static BasicBlock::iterator findInsertPointAfter (Instruction *I, BasicBlock *MustDominate)
 
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. More...
 
static void SimplifyAddOperands (SmallVectorImpl< const SCEV *> &Ops, Type *Ty, ScalarEvolution &SE)
 SimplifyAddOperands - Sort and simplify a list of add operands. More...
 
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. More...
 
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. More...
 
static void ExposePointerBase (const SCEV *&Base, const SCEV *&Rest, ScalarEvolution &SE)
 Move parts of Base into Rest to leave Base with the minimal expression that provides a pointer operand suitable for a GEP expansion. More...
 
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. More...
 
static bool IsIncrementNSW (ScalarEvolution &SE, const SCEVAddRecExpr *AR)
 
static bool IsIncrementNUW (ScalarEvolution &SE, const SCEVAddRecExpr *AR)
 
bool llvm::isSafeToExpand (const SCEV *S, ScalarEvolution &SE)
 Return true if the given expression is safe to expand in the sense that all materialized values are safe to speculate anywhere their operands are defined. More...
 
bool llvm::isSafeToExpandAt (const SCEV *S, const Instruction *InsertionPoint, ScalarEvolution &SE)
 Return true if the given expression is safe to expand in the sense that all materialized values are defined and safe to speculate at the specified location and their operands are defined at this location. More...
 

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 1059 of file ScalarEvolutionExpander.cpp.

References llvm::dyn_cast(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getEffectiveSCEVType(), llvm::Type::getIntegerBitWidth(), llvm::ScalarEvolution::getNegativeSCEV(), llvm::SCEVAddRecExpr::getStart(), llvm::ScalarEvolution::getTruncateOrNoop(), and llvm::SCEVNAryExpr::getType().

Referenced by IsIncrementNUW().

◆ ExposePointerBase()

static void ExposePointerBase ( const SCEV *&  Base,
const SCEV *&  Rest,
ScalarEvolution SE 
)
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. TODO: When ScalarEvolution gets a SCEVSDivExpr, this can be made unnecessary; in its place, just signed-divide Ops[i] by the scale and check to see if the divide was folded.

Definition at line 226 of file ScalarEvolutionExpander.cpp.

References C, R600_InstFlag::FC, llvm::SCEV::FlagNW, llvm::ConstantInt::get(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getAddRecExpr(), llvm::SCEVConstant::getAPInt(), llvm::ScalarEvolution::getConstant(), llvm::ScalarEvolution::getContext(), llvm::ScalarEvolution::getMulExpr(), llvm::SCEV::getType(), llvm::SCEV::isOne(), llvm::SCEV::isZero(), and llvm::ConstantInt::isZero().

Referenced by SplitAddRecs().

◆ findInsertPointAfter()

static BasicBlock::iterator findInsertPointAfter ( Instruction I,
BasicBlock MustDominate 
)
static

◆ IsIncrementNSW()

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

◆ IsIncrementNUW()

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

Definition at line 1104 of file ScalarEvolutionExpander.cpp.

References llvm::MCID::Add, llvm::PHINode::addIncoming(), assert(), llvm::BasicBlock::begin(), canBeCheaplyTransformed(), llvm::SmallPtrSetImplBase::clear(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::PHINode::Create(), CreateAdd(), llvm::dyn_cast(), expand(), ExposePointerBase(), llvm::MipsISD::Ext, findInsertPointAfter(), llvm::SCEV::FlagNW, llvm::BasicBlock::front(), llvm::IntegerType::get(), llvm::ConstantInt::get(), llvm::ScalarEvolution::getAddExpr(), getBitWidth(), llvm::Loop::getCanonicalInductionVariable(), llvm::Type::getContext(), llvm::Instruction::getDebugLoc(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingValueForBlock(), llvm::SCEVAddRecExpr::getLoop(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::Constant::getNullValue(), llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVCastExpr::getOperand(), llvm::SCEVNAryExpr::getOperand(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::BasicBlock::getTerminator(), llvm::SCEVCastExpr::getType(), llvm::SCEV::getType(), llvm::SCEVNAryExpr::getType(), llvm::Value::getType(), llvm::ScalarEvolution::getZeroExtendExpr(), I, llvm::SmallSet< T, N, C >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SCEVAddRecExpr::isAffine(), IsIncrementNSW(), llvm::Type::isIntegerTy(), llvm::SCEV::isNonConstantNegative(), llvm::SCEV::isOne(), llvm::Type::isPointerTy(), llvm::SCEV::isZero(), Loops, llvm::normalizeForPostIncUse(), llvm::SCEVNAryExpr::op_begin(), llvm::SCEVNAryExpr::op_end(), llvm::pred_begin(), llvm::pred_end(), and llvm::Instruction::setDebugLoc().

◆ PickMostRelevantLoop()

static const Loop* PickMostRelevantLoop ( const Loop A,
const Loop B,
DominatorTree DT 
)
static

◆ 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