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.


 Compute iterated dominance frontiers using a linear time algorithm.


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. More...

Function Documentation

◆ canBeCheaplyTransformed()

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.

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 

◆ FactorOutConstant()

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.

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 

◆ IsIncrementNSW()

static bool IsIncrementNSW ( ScalarEvolution SE,
const SCEVAddRecExpr AR 

◆ IsIncrementNUW()

static bool IsIncrementNUW ( ScalarEvolution SE,
const SCEVAddRecExpr AR 

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 

◆ SimplifyAddOperands()

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

◆ SplitAddRecs()

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