LLVM  8.0.1
Macros | Functions
IVDescriptors.cpp File Reference
#include "llvm/Analysis/IVDescriptors.h"
#include "llvm/ADT/ScopeExit.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/MustExecute.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/DomTreeUpdater.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/KnownBits.h"
Include dependency graph for IVDescriptors.cpp:

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "iv-descriptors"
 

Functions

static InstructionlookThroughAnd (PHINode *Phi, Type *&RT, SmallPtrSetImpl< Instruction *> &Visited, SmallPtrSetImpl< Instruction *> &CI)
 Determines if Phi may have been type-promoted. More...
 
static std::pair< Type *, boolcomputeRecurrenceType (Instruction *Exit, DemandedBits *DB, AssumptionCache *AC, DominatorTree *DT)
 Compute the minimal bit width needed to represent a reduction whose exit instruction is given by Exit. More...
 
static void collectCastsToIgnore (Loop *TheLoop, Instruction *Exit, Type *RecurrenceType, SmallPtrSetImpl< Instruction *> &Casts)
 Collect cast instructions that can be ignored in the vectorizer's cost model, given a reduction exit value and the minimal type in which the reduction can be represented. More...
 
static bool getCastsForInductionPHI (PredicatedScalarEvolution &PSE, const SCEVUnknown *PhiScev, const SCEVAddRecExpr *AR, SmallVectorImpl< Instruction *> &CastInsts)
 This function is called when we suspect that the update-chain of a phi node (whose symbolic SCEV expression sin PhiScev) contains redundant casts, that can be ignored. More...
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "iv-descriptors"

Definition at line 42 of file IVDescriptors.cpp.

Function Documentation

◆ collectCastsToIgnore()

static void collectCastsToIgnore ( Loop TheLoop,
Instruction Exit,
Type RecurrenceType,
SmallPtrSetImpl< Instruction *> &  Casts 
)
static

Collect cast instructions that can be ignored in the vectorizer's cost model, given a reduction exit value and the minimal type in which the reduction can be represented.

Definition at line 162 of file IVDescriptors.cpp.

References llvm::LoopBase< BlockT, LoopT >::contains(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::SmallVectorBase::empty(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::RISCVFenceField::O, llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateBase< T >::push_back().

◆ computeRecurrenceType()

static std::pair<Type *, bool> computeRecurrenceType ( Instruction Exit,
DemandedBits DB,
AssumptionCache AC,
DominatorTree DT 
)
static

◆ getCastsForInductionPHI()

static bool getCastsForInductionPHI ( PredicatedScalarEvolution PSE,
const SCEVUnknown PhiScev,
const SCEVAddRecExpr AR,
SmallVectorImpl< Instruction *> &  CastInsts 
)
static

This function is called when we suspect that the update-chain of a phi node (whose symbolic SCEV expression sin PhiScev) contains redundant casts, that can be ignored.

(This can happen when the PSCEV rewriter adds a runtime predicate P under which the SCEV expression for the phi can be the AddRecurrence AR; See createAddRecFromPHIWithCast). We want to find the cast instructions that are involved in the update-chain of this induction. A caller that adds the required runtime predicate can be free to drop these cast instructions, and compute the phi using AR (instead of some scev expression with casts).

For example, without a predicate the scev expression can take the following form: (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy)

It corresponds to the following IR sequence: for.body: x = phi i64 [ 0, ph ], [ add, for.body ] casted_phi = "ExtTrunc i64 %x" add = add i64 casted_phi, step

where x is given in PN, PSE.getSCEV(x) is equal to PSE.getSCEV(casted_phi) under a predicate, and the IR sequence that "ExtTrunc i64 %x" represents can take one of several forms, for example, such as: ExtTrunc1: casted_phi = and x, 2^n-1 or: ExtTrunc2: t = shl x, m casted_phi = ashr t, m

If we are able to find such sequence, we return the instructions we found, namely casted_phi and the instructions on its use-def chain up to the phi (not including the phi).

Definition at line 907 of file IVDescriptors.cpp.

References llvm::PredicatedScalarEvolution::areAddRecsEqualWithPreds(), assert(), llvm::tgtok::Def, llvm::dyn_cast(), llvm::SmallVectorBase::empty(), llvm::SCEVAddRecExpr::getLoop(), llvm::User::getOperand(), llvm::PredicatedScalarEvolution::getSCEV(), llvm::SCEVUnknown::getValue(), and llvm::SmallVectorTemplateBase< T >::push_back().

Referenced by llvm::InductionDescriptor::isInductionPHI().

◆ lookThroughAnd()

static Instruction* lookThroughAnd ( PHINode Phi,
Type *&  RT,
SmallPtrSetImpl< Instruction *> &  Visited,
SmallPtrSetImpl< Instruction *> &  CI 
)
static

Determines if Phi may have been type-promoted.

If Phi has a single user that ANDs the Phi with a type mask, return the user. RT is updated to account for the narrower bit width represented by the mask, and the AND instruction is added to CI.

Definition at line 88 of file IVDescriptors.cpp.

References llvm::tgtok::Bits, llvm::IntegerType::get(), llvm::Value::getContext(), llvm::Value::hasOneUse(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_c_And(), llvm::PatternMatch::m_Instruction(), llvm::PatternMatch::match(), and llvm::Value::use_begin().