LLVM
8.0.1
|
#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"
Go to the source code of this file.
Macros | |
#define | DEBUG_TYPE "iv-descriptors" |
Functions | |
static Instruction * | lookThroughAnd (PHINode *Phi, Type *&RT, SmallPtrSetImpl< Instruction *> &Visited, SmallPtrSetImpl< Instruction *> &CI) |
Determines if Phi may have been type-promoted. More... | |
static std::pair< Type *, bool > | computeRecurrenceType (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... | |
#define DEBUG_TYPE "iv-descriptors" |
Definition at line 42 of file IVDescriptors.cpp.
|
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().
|
static |
Compute the minimal bit width needed to represent a reduction whose exit instruction is given by Exit.
Definition at line 113 of file IVDescriptors.cpp.
References llvm::tgtok::Bits, llvm::computeKnownBits(), llvm::ComputeNumSignBits(), llvm::Value::getContext(), llvm::Module::getDataLayout(), llvm::DemandedBits::getDemandedBits(), llvm::Type::getIntNTy(), llvm::Instruction::getModule(), llvm::Value::getType(), llvm::DataLayout::getTypeSizeInBits(), llvm::KnownBits::isNegative(), llvm::KnownBits::isNonNegative(), llvm::isPowerOf2_64(), llvm::BitmaskEnumDetail::Mask(), and llvm::NextPowerOf2().
|
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().
|
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().