LLVM 17.0.0git
Go to the documentation of this file.
1//===- IVUsers.cpp - Induction Variable Users -------------------*- C++ -*-===//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
9// This file implements bookkeeping for "interesting" users of expressions
10// computed from induction variables.
22#include "llvm/Config/llvm-config.h"
23#include "llvm/IR/DataLayout.h"
24#include "llvm/IR/Dominators.h"
26#include "llvm/IR/Module.h"
28#include "llvm/Support/Debug.h"
30using namespace llvm;
32#define DEBUG_TYPE "iv-users"
34AnalysisKey IVUsersAnalysis::Key;
38 return IVUsers(&L, &AR.AC, &AR.LI, &AR.DT, &AR.SE);
43 "Induction Variable Users", false, true)
53/// isInteresting - Test whether the given expression is "interesting" when
54/// used by the given expression, within the context of analyzing the
55/// given loop.
56static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L,
57 ScalarEvolution *SE, LoopInfo *LI) {
58 // An addrec is interesting if it's affine or if it has an interesting start.
59 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
60 // Keep things simple. Don't touch loop-variant strides unless they're
61 // only used outside the loop and we can simplify them.
62 if (AR->getLoop() == L)
63 return AR->isAffine() ||
64 (!L->contains(I) &&
65 SE->getSCEVAtScope(AR, LI->getLoopFor(I->getParent())) != AR);
66 // Otherwise recurse to see if the start value is interesting, and that
67 // the step value is not interesting, since we don't yet know how to
68 // do effective SCEV expansions for addrecs with interesting steps.
69 return isInteresting(AR->getStart(), I, L, SE, LI) &&
70 !isInteresting(AR->getStepRecurrence(*SE), I, L, SE, LI);
71 }
73 // An add is interesting if exactly one of its operands is interesting.
74 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
75 bool AnyInterestingYet = false;
76 for (const auto *Op : Add->operands())
77 if (isInteresting(Op, I, L, SE, LI)) {
78 if (AnyInterestingYet)
79 return false;
80 AnyInterestingYet = true;
81 }
82 return AnyInterestingYet;
83 }
85 // Nothing else is interesting here.
86 return false;
89/// IVUseShouldUsePostIncValue - We have discovered a "User" of an IV expression
90/// and now we need to decide whether the user should use the preinc or post-inc
91/// value. If this user should use the post-inc version of the IV, return true.
93/// Choosing wrong here can break dominance properties (if we choose to use the
94/// post-inc value when we cannot) or it can end up adding extra live-ranges to
95/// the loop, resulting in reg-reg copies (if we use the pre-inc value when we
96/// should use the post-inc value).
98 const Loop *L, DominatorTree *DT) {
99 // If the user is in the loop, use the preinc value.
100 if (L->contains(User))
101 return false;
103 BasicBlock *LatchBlock = L->getLoopLatch();
104 if (!LatchBlock)
105 return false;
107 // Ok, the user is outside of the loop. If it is dominated by the latch
108 // block, use the post-inc value.
109 if (DT->dominates(LatchBlock, User->getParent()))
110 return true;
112 // There is one case we have to be careful of: PHI nodes. These little guys
113 // can live in blocks that are not dominated by the latch block, but (since
114 // their uses occur in the predecessor block, not the block the PHI lives in)
115 // should still use the post-inc value. Check for this case now.
116 PHINode *PN = dyn_cast<PHINode>(User);
117 if (!PN || !Operand)
118 return false; // not a phi, not dominated by latch block.
120 // Look at all of the uses of Operand by the PHI node. If any use corresponds
121 // to a block that is not dominated by the latch block, give up and use the
122 // preincremented value.
123 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
124 if (PN->getIncomingValue(i) == Operand &&
125 !DT->dominates(LatchBlock, PN->getIncomingBlock(i)))
126 return false;
128 // Okay, all uses of Operand by PN are in predecessor blocks that really are
129 // dominated by the latch block. Use the post-incremented value.
130 return true;
133/// Inspect the specified instruction. If it is a reducible SCEV, recursively
134/// add its users to the IVUsesByStride set and return true. Otherwise, return
135/// false.
137 const DataLayout &DL = I->getModule()->getDataLayout();
139 // Add this IV user to the Processed set before returning false to ensure that
140 // all IV users are members of the set. See IVUsers::isIVUserOrOperand.
141 if (!Processed.insert(I).second)
142 return true; // Instruction already handled.
144 if (!SE->isSCEVable(I->getType()))
145 return false; // Void and FP expressions cannot be reduced.
147 // IVUsers is used by LSR which assumes that all SCEV expressions are safe to
148 // pass to SCEVExpander. Expressions are not safe to expand if they represent
149 // operations that are not safe to speculate, namely integer division.
150 if (!isa<PHINode>(I) && !isSafeToSpeculativelyExecute(I))
151 return false;
153 // LSR is not APInt clean, do not touch integers bigger than 64-bits.
154 // Also avoid creating IVs of non-native types. For example, we don't want a
155 // 64-bit IV in 32-bit code just because the loop has one 64-bit cast.
156 uint64_t Width = SE->getTypeSizeInBits(I->getType());
157 if (Width > 64 || !DL.isLegalInteger(Width))
158 return false;
160 // Don't attempt to promote ephemeral values to indvars. They will be removed
161 // later anyway.
162 if (EphValues.count(I))
163 return false;
165 // Get the symbolic expression for this instruction.
166 const SCEV *ISE = SE->getSCEV(I);
168 // If we've come to an uninteresting expression, stop the traversal and
169 // call this a user.
170 if (!isInteresting(ISE, I, L, SE, LI))
171 return false;
174 for (Use &U : I->uses()) {
175 Instruction *User = cast<Instruction>(U.getUser());
176 if (!UniqueUsers.insert(User).second)
177 continue;
179 // Do not infinitely recurse on PHI nodes.
180 if (isa<PHINode>(User) && Processed.count(User))
181 continue;
183 // Descend recursively, but not into PHI nodes outside the current loop.
184 // It's important to see the entire expression outside the loop to get
185 // choices that depend on addressing mode use right, although we won't
186 // consider references outside the loop in all cases.
187 // If User is already in Processed, we don't want to recurse into it again,
188 // but do want to record a second reference in the same instruction.
189 bool AddUserToIVUsers = false;
190 if (LI->getLoopFor(User->getParent()) != L) {
191 if (isa<PHINode>(User) || Processed.count(User) ||
193 LLVM_DEBUG(dbgs() << "FOUND USER in other loop: " << *User << '\n'
194 << " OF SCEV: " << *ISE << '\n');
195 AddUserToIVUsers = true;
196 }
197 } else if (Processed.count(User) || !AddUsersIfInteresting(User)) {
198 LLVM_DEBUG(dbgs() << "FOUND USER: " << *User << '\n'
199 << " OF SCEV: " << *ISE << '\n');
200 AddUserToIVUsers = true;
201 }
203 if (AddUserToIVUsers) {
204 // Okay, we found a user that we cannot reduce.
205 IVStrideUse &NewUse = AddUser(User, I);
206 // Autodetect the post-inc loop set, populating NewUse.PostIncLoops.
207 // The regular return value here is discarded; instead of recording
208 // it, we just recompute it when we need it.
209 const SCEV *OriginalISE = ISE;
211 auto NormalizePred = [&](const SCEVAddRecExpr *AR) {
212 auto *L = AR->getLoop();
213 bool Result = IVUseShouldUsePostIncValue(User, I, L, DT);
214 if (Result)
215 NewUse.PostIncLoops.insert(L);
216 return Result;
217 };
219 ISE = normalizeForPostIncUseIf(ISE, NormalizePred, *SE);
221 // PostIncNormalization effectively simplifies the expression under
222 // pre-increment assumptions. Those assumptions (no wrapping) might not
223 // hold for the post-inc value. Catch such cases by making sure the
224 // transformation is invertible.
225 if (OriginalISE != ISE) {
226 const SCEV *DenormalizedISE =
227 denormalizeForPostIncUse(ISE, NewUse.PostIncLoops, *SE);
229 // If we normalized the expression, but denormalization doesn't give the
230 // original one, discard this user.
231 if (OriginalISE != DenormalizedISE) {
234 << *ISE << '\n');
235 IVUses.pop_back();
236 return false;
237 }
238 }
239 LLVM_DEBUG(if (SE->getSCEV(I) != ISE) dbgs()
240 << " NORMALIZED TO: " << *ISE << '\n');
241 }
242 }
243 return true;
247 IVUses.push_back(new IVStrideUse(this, User, Operand));
248 return IVUses.back();
252 ScalarEvolution *SE)
253 : L(L), AC(AC), LI(LI), DT(DT), SE(SE) {
254 // Collect ephemeral values so that AddUsersIfInteresting skips them.
255 EphValues.clear();
256 CodeMetrics::collectEphemeralValues(L, AC, EphValues);
258 // Find all uses of induction variables in this loop, and categorize
259 // them by stride. Start by finding all of the PHI nodes in the header for
260 // this loop. If they are induction variables, inspect their uses.
261 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I)
262 (void)AddUsersIfInteresting(&*I);
265void IVUsers::print(raw_ostream &OS, const Module *M) const {
266 OS << "IV Users for loop ";
267 L->getHeader()->printAsOperand(OS, false);
269 OS << " with backedge-taken count " << *SE->getBackedgeTakenCount(L);
270 }
271 OS << ":\n";
273 for (const IVStrideUse &IVUse : IVUses) {
274 OS << " ";
275 IVUse.getOperandValToReplace()->printAsOperand(OS, false);
276 OS << " = " << *getReplacementExpr(IVUse);
277 for (const auto *PostIncLoop : IVUse.PostIncLoops) {
278 OS << " (post-inc with loop ";
279 PostIncLoop->getHeader()->printAsOperand(OS, false);
280 OS << ")";
281 }
282 OS << " in ";
283 if (IVUse.getUser())
284 IVUse.getUser()->print(OS);
285 else
286 OS << "Printing <null> User";
287 OS << '\n';
288 }
291#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
296 Processed.clear();
297 IVUses.clear();
309 AU.setPreservesAll();
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));
320 return false;
324 IU->print(OS, M);
327void IVUsersWrapperPass::releaseMemory() { IU->releaseMemory(); }
329/// getReplacementExpr - Return a SCEV expression which computes the
330/// value of the OperandValToReplace.
332 return SE->getSCEV(IU.getOperandValToReplace());
335/// getExpr - Return the expression for the use.
336const SCEV *IVUsers::getExpr(const IVStrideUse &IU) const {
338 *SE);
341static const SCEVAddRecExpr *findAddRecForLoop(const SCEV *S, const Loop *L) {
342 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
343 if (AR->getLoop() == L)
344 return AR;
345 return findAddRecForLoop(AR->getStart(), L);
346 }
348 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
349 for (const auto *Op : Add->operands())
350 if (const SCEVAddRecExpr *AR = findAddRecForLoop(Op, L))
351 return AR;
352 return nullptr;
353 }
355 return nullptr;
358const SCEV *IVUsers::getStride(const IVStrideUse &IU, const Loop *L) const {
359 if (const SCEVAddRecExpr *AR = findAddRecForLoop(getExpr(IU), L))
360 return AR->getStepRecurrence(*SE);
361 return nullptr;
365 PostIncLoops.insert(L);
368void IVStrideUse::deleted() {
369 // Remove this user from the list.
370 Parent->Processed.erase(this->getUser());
371 Parent->IVUses.erase(this);
372 // this now dangles!
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
basic Basic Alias true
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:492
#define LLVM_DEBUG(X)
Definition: Debug.h:101
static const SCEVAddRecExpr * findAddRecForLoop(const SCEV *S, const Loop *L)
Definition: IVUsers.cpp:341
iv Induction Variable Users
Definition: IVUsers.cpp:48
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,...
Definition: IVUsers.cpp:56
iv users
Definition: IVUsers.cpp:48
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...
Definition: IVUsers.cpp:97
This header provides classes for managing per-loop analyses.
#define I(x, y, z)
Definition: MD5.cpp:58
Module.h This file contains the declarations for the Module class.
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
raw_pwrite_stream & OS
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
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.
Definition: BasicBlock.h:56
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:314
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
IVStrideUse - Keep track of one use of a strided induction variable.
Definition: IVUsers.h:34
Instruction * getUser() const
getUser - Return the user instruction for this use.
Definition: IVUsers.h:42
const PostIncLoopSet & getPostIncLoops() const
getPostIncLoops - Return the set of loops for which the expression has been adjusted to use post-inc ...
Definition: IVUsers.h:65
void transformToPostInc(const Loop *L)
transformToPostInc - Transform the expression to post-inc form for the given loop.
Definition: IVUsers.cpp:364
Value * getOperandValToReplace() const
getOperandValToReplace - Return the Value of the operand in the user instruction that this IVStrideUs...
Definition: IVUsers.h:53
IVUsers run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR)
Definition: IVUsers.cpp:36
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: IVUsers.cpp:304
bool runOnLoop(Loop *L, LPPassManager &LPM) override
Definition: IVUsers.cpp:312
void print(raw_ostream &OS, const Module *=nullptr) const override
print - Print out the internal state of the pass.
Definition: IVUsers.cpp:323
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: IVUsers.cpp:327
void dump() const
dump - This method is used for debugging.
Definition: IVUsers.cpp:292
IVStrideUse & AddUser(Instruction *User, Value *Operand)
Definition: IVUsers.cpp:246
IVUsers(Loop *L, AssumptionCache *AC, LoopInfo *LI, DominatorTree *DT, ScalarEvolution *SE)
Definition: IVUsers.cpp:251
void releaseMemory()
Definition: IVUsers.cpp:295
const SCEV * getStride(const IVStrideUse &IU, const Loop *L) const
Definition: IVUsers.cpp:358
const SCEV * getReplacementExpr(const IVStrideUse &IU) const
getReplacementExpr - Return a SCEV expression which computes the value of the OperandValToReplace of ...
Definition: IVUsers.cpp:331
bool AddUsersIfInteresting(Instruction *I)
AddUsersIfInteresting - Inspect the specified Instruction.
Definition: IVUsers.cpp:136
friend class IVStrideUse
Definition: IVUsers.h:91
const SCEV * getExpr(const IVStrideUse &IU) const
getExpr - Return the expression for the use.
Definition: IVUsers.cpp:336
void print(raw_ostream &OS, const Module *=nullptr) const
Definition: IVUsers.cpp:265
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.
Definition: LoopInfo.h:594
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:47
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
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'.
Definition: Pass.h:94
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.
Definition: SmallPtrSet.h:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
LLVM Value Representation.
Definition: Value.h:74
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.
Definition: AsmWriter.cpp:4778
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
const SCEV * normalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, ScalarEvolution &SE)
Normalize S to be post-increment for all loops present in Loops.
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.
Definition: Debug.cpp:163
void initializeIVUsersWrapperPassPass(PassRegistry &)
@ Add
Sum of integers.
Pass * createIVUsersPass()
Definition: IVUsers.cpp:51
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 ...
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...
Definition: PassManager.h:69
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).
Definition: CodeMetrics.cpp:70
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...