22 #include "llvm/Config/llvm-config.h" 35 #define DEBUG_TYPE "iv-users" 46 "Induction Variable Users",
false,
true)
65 if (AR->getLoop() == L)
66 return AR->isAffine() ||
78 bool AnyInterestingYet =
false;
79 for (
const auto *
Op :
Add->operands())
81 if (AnyInterestingYet)
83 AnyInterestingYet =
true;
85 return AnyInterestingYet;
97 Loop *NearestLoop =
nullptr;
102 if (DomLoop && DomLoop->
getHeader() == DomBB) {
107 if (SimpleLoopNests.
count(DomLoop))
112 NearestLoop = DomLoop;
116 SimpleLoopNests.
insert(NearestLoop);
173 if (!Processed.insert(I).second)
176 if (!SE->isSCEVable(I->
getType()))
194 if (EphValues.count(I))
198 const SCEV *ISE = SE->getSCEV(I);
208 if (!UniqueUsers.
insert(User).second)
212 if (isa<PHINode>(User) && Processed.count(User))
219 if (
PHINode *PHI = dyn_cast<PHINode>(User)) {
220 unsigned OperandNo = U.getOperandNo();
222 UseBB = PHI->getIncomingBlock(ValNo);
233 bool AddUserToIVUsers =
false;
234 if (LI->getLoopFor(User->
getParent()) != L) {
235 if (isa<PHINode>(User) || Processed.count(User) ||
236 !AddUsersImpl(User, SimpleLoopNests)) {
237 LLVM_DEBUG(
dbgs() <<
"FOUND USER in other loop: " << *User <<
'\n' 238 <<
" OF SCEV: " << *ISE <<
'\n');
239 AddUserToIVUsers =
true;
241 }
else if (Processed.count(User) || !AddUsersImpl(User, SimpleLoopNests)) {
243 <<
" OF SCEV: " << *ISE <<
'\n');
244 AddUserToIVUsers =
true;
247 if (AddUserToIVUsers) {
253 const SCEV *OriginalISE = ISE;
256 auto *L = AR->getLoop();
259 NewUse.PostIncLoops.
insert(L);
269 if (OriginalISE != ISE) {
270 const SCEV *DenormalizedISE =
275 if (OriginalISE != DenormalizedISE) {
277 <<
" DISCARDING (NORMALIZATION ISN'T INVERTIBLE): " 284 <<
" NORMALIZED TO: " << *ISE <<
'\n');
296 return AddUsersImpl(I, SimpleLoopNests);
300 IVUses.push_back(
new IVStrideUse(
this, User, Operand));
301 return IVUses.back();
306 : L(L), AC(AC), LI(LI), DT(DT), SE(SE), IVUses() {
319 OS <<
"IV Users for loop ";
328 IVUse.getOperandValToReplace()->printAsOperand(OS,
false);
330 for (
auto PostIncLoop : IVUse.PostIncLoops) {
331 OS <<
" (post-inc with loop ";
332 PostIncLoop->getHeader()->printAsOperand(OS,
false);
337 IVUse.getUser()->print(OS);
339 OS <<
"Printing <null> User";
344 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 366 auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
368 auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
369 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
370 auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
372 IU.reset(
new IVUsers(L, AC, LI, DT, SE));
396 if (AR->getLoop() == L)
402 for (
const auto *
Op :
Add->operands())
413 return AR->getStepRecurrence(*SE);
418 PostIncLoops.insert(L);
421 void IVStrideUse::deleted() {
423 Parent->Processed.erase(this->getUser());
424 Parent->IVUses.erase(
this);
Pass interface - Implemented by all 'passes'.
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)...
bool runOnLoop(Loop *L, LPPassManager &LPM) override
A parsed version of the target data layout string in and methods for querying it. ...
bool AddUsersImpl(Instruction *I, SmallPtrSetImpl< Loop *> &SimpleLoopNests)
AddUsersImpl - Inspect the specified instruction.
iterator_range< use_iterator > uses()
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
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...
const SCEV * getReplacementExpr(const IVStrideUse &IU) const
getReplacementExpr - Return a SCEV expression which computes the value of the OperandValToReplace of ...
This class represents lattice values for constants.
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
A Module instance is used to store all the information related to an LLVM module. ...
const SCEV * normalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, ScalarEvolution &SE)
Normalize S to be post-increment for all loops present in Loops.
Pass * createIVUsersPass()
The main scalar evolution driver.
void initializeIVUsersWrapperPassPass(PassRegistry &)
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
block Block Frequency true
iv Induction Variable Users
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
iterator begin()
Instruction iterator methods.
bool AddUsersIfInteresting(Instruction *I)
AddUsersIfInteresting - Inspect the specified Instruction.
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
static bool isSimplifiedLoopNest(BasicBlock *BB, const DominatorTree *DT, const LoopInfo *LI, SmallPtrSetImpl< Loop *> &SimpleLoopNests)
Return true if all loop headers that dominate this block are in simplified form.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
A Use represents the edge between a Value definition and its users.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
BlockT * getHeader() const
void print(raw_ostream &OS, const Module *=nullptr) const
Type * getType() const
All values are typed, get the type of this value.
This node represents a polynomial recurrence on the trip count of the specified loop.
This header provides classes for managing per-loop analyses.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
const SCEV * normalizeForPostIncUseIf(const SCEV *S, NormalizePredTy Pred, ScalarEvolution &SE)
Normalize S for all add recurrence sub-expressions for which Pred returns true.
const SCEV * getStride(const IVStrideUse &IU, const Loop *L) const
LLVM Basic Block Representation.
IVUsers run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR)
DomTreeNodeBase * getIDom() const
This file contains the declarations for the subclasses of Constant, which represent the different fla...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
Represent the analysis usage information of a pass.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
const PostIncLoopSet & getPostIncLoops() const
getPostIncLoops - Return the set of loops for which the expression has been adjusted to use post-inc ...
static unsigned getIncomingValueNumForOperand(unsigned i)
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
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.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
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...
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Iterator for intrusive lists based on ilist_node.
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Module.h This file contains the declarations for the Module class.
bool isLegalInteger(uint64_t Width) const
Returns true if the specified type is known to be a native integer type supported by the CPU...
unsigned getNumIncomingValues() const
Return the number of incoming edges.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
This node represents an addition of some number of SCEVs.
void setPreservesAll()
Set by analyses that do not transform their input at all.
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to...
IVUsers(Loop *L, AssumptionCache *AC, LoopInfo *LI, DominatorTree *DT, ScalarEvolution *SE)
MCExpr const & getExpr(MCExpr const &Expr)
This class represents an analyzed expression in the program.
Represents a single loop in the control flow graph.
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getOperandValToReplace() const
getOperandValToReplace - Return the Value of the operand in the user instruction that this IVStrideUs...
const Function * getParent() const
Return the enclosing method, or null if none.
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
void dump() const
dump - This method is used for debugging.
const SCEV * getExpr(const IVStrideUse &IU) const
getExpr - Return the expression for the use.
void transformToPostInc(const Loop *L)
transformToPostInc - Transform the expression to post-inc form for the given loop.
INITIALIZE_PASS_BEGIN(IVUsersWrapperPass, "iv-users", "Induction Variable Users", false, true) INITIALIZE_PASS_END(IVUsersWrapperPass
const SCEV * getBackedgeTakenCount(const Loop *L)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
static const SCEVAddRecExpr * findAddRecForLoop(const SCEV *S, const Loop *L)
const SCEV * denormalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, ScalarEvolution &SE)
Denormalize S to be post-increment for all loops present in Loops.
LLVM Value Representation.
IVStrideUse - Keep track of one use of a strided induction variable.
This class implements an extremely fast bulk output stream that can only output to a stream...
The legacy pass manager's analysis pass to compute loop information.
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
IVStrideUse & AddUser(Instruction *User, Value *Operand)
bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count...
A special type used by analysis passes to provide an address that identifies that particular analysis...
void print(raw_ostream &OS, const Module *=nullptr) const override
print - Print out the internal state of the pass.
const BasicBlock * getParent() const