22#include "llvm/Config/llvm-config.h"
32#define DEBUG_TYPE "iv-users"
43 "Induction Variable Users",
false,
true)
62 if (AR->getLoop() == L)
63 return AR->isAffine() ||
75 bool AnyInterestingYet =
false;
78 if (AnyInterestingYet)
80 AnyInterestingYet =
true;
82 return AnyInterestingYet;
100 if (L->contains(
User))
141 if (!Processed.insert(
I).second)
157 if (Width > 64 || !
DL.isLegalInteger(Width))
162 if (EphValues.count(
I))
174 for (
Use &U :
I->uses()) {
180 if (isa<PHINode>(
User) && Processed.count(
User))
189 bool AddUserToIVUsers =
false;
191 if (isa<PHINode>(
User) || Processed.count(
User) ||
194 <<
" OF SCEV: " << *ISE <<
'\n');
195 AddUserToIVUsers =
true;
199 <<
" OF SCEV: " << *ISE <<
'\n');
200 AddUserToIVUsers =
true;
203 if (AddUserToIVUsers) {
209 const SCEV *OriginalISE = ISE;
212 auto *L = AR->getLoop();
215 NewUse.PostIncLoops.
insert(L);
225 if (OriginalISE != ISE) {
226 const SCEV *DenormalizedISE =
231 if (OriginalISE != DenormalizedISE) {
233 <<
" DISCARDING (NORMALIZATION ISN'T INVERTIBLE): "
240 <<
" NORMALIZED TO: " << *ISE <<
'\n');
248 return IVUses.back();
253 : L(L), AC(AC), LI(LI), DT(DT), SE(SE) {
266 OS <<
"IV Users for loop ";
275 IVUse.getOperandValToReplace()->printAsOperand(
OS,
false);
277 for (
const auto *PostIncLoop : IVUse.PostIncLoops) {
278 OS <<
" (post-inc with loop ";
279 PostIncLoop->getHeader()->printAsOperand(
OS,
false);
284 IVUse.getUser()->print(
OS);
286 OS <<
"Printing <null> User";
291#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
313 auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
314 *L->getHeader()->getParent());
315 auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
316 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
317 auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
319 IU.reset(
new IVUsers(L, AC, LI, DT, SE));
343 if (AR->getLoop() == L)
363 return AR->getStepRecurrence(*SE);
371void IVStrideUse::deleted() {
373 Parent->Processed.erase(this->
getUser());
374 Parent->IVUses.erase(
this);
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
static const SCEVAddRecExpr * findAddRecForLoop(const SCEV *S, const Loop *L)
iv Induction Variable Users
static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L, ScalarEvolution *SE, LoopInfo *LI)
isInteresting - Test whether the given expression is "interesting" when used by the given expression,...
static bool IVUseShouldUsePostIncValue(Instruction *User, Value *Operand, const Loop *L, DominatorTree *DT)
IVUseShouldUsePostIncValue - We have discovered a "User" of an IV expression and now we need to decid...
This header provides classes for managing per-loop analyses.
Module.h This file contains the declarations for the Module class.
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
A container for analyses that lazily runs them and caches their results.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesAll()
Set by analyses that do not transform their input at all.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
InstListType::iterator iterator
Instruction iterators...
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
IVStrideUse - Keep track of one use of a strided induction variable.
Instruction * getUser() const
getUser - Return the user instruction for this use.
const PostIncLoopSet & getPostIncLoops() const
getPostIncLoops - Return the set of loops for which the expression has been adjusted to use post-inc ...
void transformToPostInc(const Loop *L)
transformToPostInc - Transform the expression to post-inc form for the given loop.
Value * getOperandValToReplace() const
getOperandValToReplace - Return the Value of the operand in the user instruction that this IVStrideUs...
IVUsers run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
bool runOnLoop(Loop *L, LPPassManager &LPM) override
void print(raw_ostream &OS, const Module *=nullptr) const override
print - Print out the internal state of the pass.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
void dump() const
dump - This method is used for debugging.
IVStrideUse & AddUser(Instruction *User, Value *Operand)
IVUsers(Loop *L, AssumptionCache *AC, LoopInfo *LI, DominatorTree *DT, ScalarEvolution *SE)
const SCEV * getStride(const IVStrideUse &IU, const Loop *L) const
const SCEV * getReplacementExpr(const IVStrideUse &IU) const
getReplacementExpr - Return a SCEV expression which computes the value of the OperandValToReplace of ...
bool AddUsersIfInteresting(Instruction *I)
AddUsersIfInteresting - Inspect the specified Instruction.
const SCEV * getExpr(const IVStrideUse &IU) const
getExpr - Return the expression for the use.
void print(raw_ostream &OS, const Module *=nullptr) const
BlockT * getHeader() const
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
Represents a single loop in the control flow graph.
A Module instance is used to store all the information related to an LLVM module.
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
This node represents an addition of some number of SCEVs.
This node represents a polynomial recurrence on the trip count of the specified loop.
This class represents an analyzed expression in the program.
The main scalar evolution driver.
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
This class implements an extremely fast bulk output stream that can only output to a stream.
This is an optimization pass for GlobalISel generic memory operations.
const SCEV * denormalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, ScalarEvolution &SE)
Denormalize S to be post-increment for all loops present in Loops.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void initializeIVUsersWrapperPassPass(PassRegistry &)
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
const SCEV * normalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, ScalarEvolution &SE, bool CheckInvertible=true)
Normalize S to be post-increment for all loops present in Loops.
Pass * createIVUsersPass()
const SCEV * normalizeForPostIncUseIf(const SCEV *S, NormalizePredTy Pred, ScalarEvolution &SE)
Normalize S for all add recurrence sub-expressions for which Pred returns true.
A special type used by analysis passes to provide an address that identifies that particular analysis...
static void collectEphemeralValues(const Loop *L, AssumptionCache *AC, SmallPtrSetImpl< const Value * > &EphValues)
Collect a loop's ephemeral values (those used only by an assume or similar intrinsics in the loop).
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...