Go to the documentation of this file.
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;
76 for (
const auto *
Op : Add->operands())
78 if (AnyInterestingYet)
80 AnyInterestingYet =
true;
82 return AnyInterestingYet;
141 if (!Processed.insert(
I).second)
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(
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)
348 if (
const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(
S)) {
349 for (
const auto *
Op : Add->operands())
360 return AR->getStepRecurrence(*SE);
368 void IVStrideUse::deleted() {
370 Parent->Processed.erase(this->
getUser());
371 Parent->IVUses.erase(
this);
bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This is an optimization pass for GlobalISel generic memory operations.
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
A parsed version of the target data layout string in and methods for querying it.
InstListType::iterator iterator
Instruction iterators...
const Function * getParent() const
Return the enclosing method, or null if none.
Represents a single loop in the control flow graph.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
const SCEV * denormalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, ScalarEvolution &SE)
Denormalize S to be post-increment for all loops present in Loops.
The main scalar evolution driver.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
The legacy pass manager's analysis pass to compute loop information.
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
IVStrideUse - Keep track of one use of a strided induction variable.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
void initializeIVUsersWrapperPassPass(PassRegistry &)
LLVM Basic Block Representation.
Value * getOperandValToReplace() const
getOperandValToReplace - Return the Value of the operand in the user instruction that this IVStrideUs...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
const SCEV * normalizeForPostIncUseIf(const SCEV *S, NormalizePredTy Pred, ScalarEvolution &SE)
Normalize S for all add recurrence sub-expressions for which Pred returns true.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
iterator begin()
Instruction iterator methods.
Represent the analysis usage information of a pass.
Instruction * getUser() const
getUser - Return the user instruction for this use.
Legacy analysis pass which computes a DominatorTree.
This class implements an extremely fast bulk output stream that can only output to a stream.
static const SCEVAddRecExpr * findAddRecForLoop(const SCEV *S, const Loop *L)
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).
IVUsers(Loop *L, AssumptionCache *AC, LoopInfo *LI, DominatorTree *DT, ScalarEvolution *SE)
const SCEV * getReplacementExpr(const IVStrideUse &IU) const
getReplacementExpr - Return a SCEV expression which computes the value of the OperandValToReplace of ...
unsigned getNumIncomingValues() const
Return the number of incoming edges.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
void print(raw_ostream &OS, const Module *=nullptr) const
const PostIncLoopSet & getPostIncLoops() const
getPostIncLoops - Return the set of loops for which the expression has been adjusted to use post-inc ...
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
This class represents an analyzed expression in the program.
INITIALIZE_PASS_BEGIN(IVUsersWrapperPass, "iv-users", "Induction Variable Users", false, true) INITIALIZE_PASS_END(IVUsersWrapperPass
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
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,...
A special type used by analysis passes to provide an address that identifies that particular analysis...
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
IVStrideUse & AddUser(Instruction *User, Value *Operand)
const SCEV * getStride(const IVStrideUse &IU, const Loop *L) const
A Module instance is used to store all the information related to an LLVM module.
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.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
const SCEV * getExpr(const IVStrideUse &IU) const
getExpr - Return the expression for the use.
bool runOnLoop(Loop *L, LPPassManager &LPM) override
IVUsers run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR)
void transformToPostInc(const Loop *L)
transformToPostInc - Transform the expression to post-inc form for the given loop.
void setPreservesAll()
Set by analyses that do not transform their input at all.
const SCEV * normalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, ScalarEvolution &SE)
Normalize S to be post-increment for all loops present in Loops.
This node represents a polynomial recurrence on the trip count of the specified loop.
BlockT * getHeader() const
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
Pass interface - Implemented by all 'passes'.
This node represents an addition of some number of SCEVs.
bool AddUsersIfInteresting(Instruction *I)
AddUsersIfInteresting - Inspect the specified Instruction.
Pass * createIVUsersPass()
void print(raw_ostream &OS, const Module *=nullptr) const override
print - Print out the internal state of the pass.
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
iv Induction Variable Users
A container for analyses that lazily runs them and caches their results.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
AnalysisUsage & addRequired()
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 * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
LLVM Value Representation.
void dump() const
dump - This method is used for debugging.
A Use represents the edge between a Value definition and its users.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.