1//===- IVUsers.cpp - Induction Variable Users -------------------*- C++ -*-===//
2//
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
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements bookkeeping for "interesting" users of expressions
10// computed from induction variables.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Analysis/IVUsers.h"
15#include "llvm/Analysis/AssumptionCache.h"
16#include "llvm/Analysis/CodeMetrics.h"
17#include "llvm/Analysis/LoopAnalysisManager.h"
18#include "llvm/Analysis/LoopInfo.h"
19#include "llvm/Analysis/LoopPass.h"
20#include "llvm/Analysis/ScalarEvolutionExpressions.h"
21#include "llvm/Analysis/ValueTracking.h"
22#include "llvm/Config/llvm-config.h"
23#include "llvm/IR/DataLayout.h"
24#include "llvm/IR/Dominators.h"
25#include "llvm/IR/Instructions.h"
26#include "llvm/IR/Module.h"
27#include "llvm/InitializePasses.h"
28#include "llvm/Support/Debug.h"
29#include "llvm/Support/raw_ostream.h"
30using namespace llvm;
31
32#define DEBUG_TYPE "iv-users"
33
34AnalysisKey IVUsersAnalysis::Key;
35
36IVUsers IVUsersAnalysis::run(Loop &L, LoopAnalysisManager &AM,
37 LoopStandardAnalysisResults &AR) {
38 return IVUsers(&L, &AR.AC, &AR.LI, &AR.DT, &AR.SE);
39}
40
41char IVUsersWrapperPass::ID = 0;
42INITIALIZE_PASS_BEGIN(IVUsersWrapperPass, "iv-users",
43 "Induction Variable Users", false, true)
44INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
45INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
46INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
47INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
48INITIALIZE_PASS_END(IVUsersWrapperPass, "iv-users", "Induction Variable Users",
49 false, true)
50
51Pass *llvm::createIVUsersPass() { return new IVUsersWrapperPass(); }
52
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>(Val: 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(Inst: I) &&
65 SE->getSCEVAtScope(S: AR, L: LI->getLoopFor(BB: 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(S: AR->getStart(), I, L, SE, LI) &&
70 !isInteresting(S: AR->getStepRecurrence(SE&: *SE), I, L, SE, LI);
71 }
72
73 // An add is interesting if exactly one of its operands is interesting.
74 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Val: S)) {
75 bool AnyInterestingYet = false;
76 for (const SCEV *Op : Add->operands())
77 if (isInteresting(S: Op, I, L, SE, LI)) {
78 if (AnyInterestingYet)
79 return false;
80 AnyInterestingYet = true;
81 }
82 return AnyInterestingYet;
83 }
84
85 // Nothing else is interesting here.
86 return false;
87}
88
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.
92///
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).
97static bool IVUseShouldUsePostIncValue(Instruction *User, Value *Operand,
98 const Loop *L, DominatorTree *DT) {
99 // If the user is in the loop, use the preinc value.
100 if (L->contains(Inst: User))
101 return false;
102
103 BasicBlock *LatchBlock = L->getLoopLatch();
104 if (!LatchBlock)
105 return false;
106
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(A: LatchBlock, B: User->getParent()))
110 return true;
111
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>(Val: User);
117 if (!PN || !Operand)
118 return false; // not a phi, not dominated by latch block.
119
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(A: LatchBlock, B: PN->getIncomingBlock(i)))
126 return false;
127
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;
131}
132
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.
136bool IVUsers::AddUsersIfInteresting(Instruction *I) {
137 const DataLayout &DL = I->getDataLayout();
138
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(Ptr: I).second)
142 return true; // Instruction already handled.
143
144 if (!SE->isSCEVable(Ty: I->getType()))
145 return false; // Void and FP expressions cannot be reduced.
146
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>(Val: I) && !isSafeToSpeculativelyExecute(I))
151 return false;
152
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(Ty: I->getType());
157 if (Width > 64 || !DL.isLegalInteger(Width))
158 return false;
159
160 // Don't attempt to promote ephemeral values to indvars. They will be removed
161 // later anyway.
162 if (EphValues.count(Ptr: I))
163 return false;
164
165 // Get the symbolic expression for this instruction.
166 const SCEV *ISE = SE->getSCEV(V: I);
167
168 // If we've come to an uninteresting expression, stop the traversal and
169 // call this a user.
170 if (!isInteresting(S: ISE, I, L, SE, LI))
171 return false;
172
173 SmallPtrSet<Instruction *, 4> UniqueUsers;
174 for (Use &U : I->uses()) {
175 Instruction *User = cast<Instruction>(Val: U.getUser());
176 if (!UniqueUsers.insert(Ptr: User).second)
177 continue;
178
179 // Do not infinitely recurse on PHI nodes.
180 if (isa<PHINode>(Val: User) && Processed.count(Ptr: User))
181 continue;
182
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(BB: User->getParent()) != L) {
191 if (isa<PHINode>(Val: User) || Processed.count(Ptr: User) ||
192 !AddUsersIfInteresting(I: 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(Ptr: User) || !AddUsersIfInteresting(I: User)) {
198 LLVM_DEBUG(dbgs() << "FOUND USER: " << *User << '\n'
199 << " OF SCEV: " << *ISE << '\n');
200 AddUserToIVUsers = true;
201 }
202
203 if (AddUserToIVUsers) {
204 // Okay, we found a user that we cannot reduce.
205 IVStrideUse &NewUse = AddUser(User, Operand: 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;
210
211 auto NormalizePred = [&](const SCEVAddRecExpr *AR) {
212 auto *L = AR->getLoop();
213 bool Result = IVUseShouldUsePostIncValue(User, Operand: I, L, DT);
214 if (Result)
215 NewUse.PostIncLoops.insert(Ptr: L);
216 return Result;
217 };
218
219 ISE = normalizeForPostIncUseIf(S: ISE, Pred: NormalizePred, SE&: *SE);
220
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(S: ISE, Loops: NewUse.PostIncLoops, SE&: *SE);
228
229 // If we normalized the expression, but denormalization doesn't give the
230 // original one, discard this user.
231 if (OriginalISE != DenormalizedISE) {
232 LLVM_DEBUG(dbgs()
233 << " DISCARDING (NORMALIZATION ISN'T INVERTIBLE): "
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;
244}
245
246IVStrideUse &IVUsers::AddUser(Instruction *User, Value *Operand) {
247 IVUses.push_back(val: new IVStrideUse(this, User, Operand));
248 return IVUses.back();
249}
250
251IVUsers::IVUsers(Loop *L, AssumptionCache *AC, LoopInfo *LI, DominatorTree *DT,
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);
257
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>(Val: I); ++I)
262 (void)AddUsersIfInteresting(I: &*I);
263}
264
265void IVUsers::print(raw_ostream &OS, const Module *M) const {
266 OS << "IV Users for loop ";
267 L->getHeader()->printAsOperand(O&: OS, PrintType: false);
268 if (SE->hasLoopInvariantBackedgeTakenCount(L)) {
269 OS << " with backedge-taken count " << *SE->getBackedgeTakenCount(L);
270 }
271 OS << ":\n";
272
273 for (const IVStrideUse &IVUse : IVUses) {
274 OS << " ";
275 IVUse.getOperandValToReplace()->printAsOperand(O&: OS, PrintType: false);
276 OS << " = " << *getReplacementExpr(IU: IVUse);
277 for (const auto *PostIncLoop : IVUse.PostIncLoops) {
278 OS << " (post-inc with loop ";
279 PostIncLoop->getHeader()->printAsOperand(O&: OS, PrintType: false);
280 OS << ")";
281 }
282 OS << " in ";
283 if (IVUse.getUser())
284 IVUse.getUser()->print(O&: OS);
285 else
286 OS << "Printing <null> User";
287 OS << '\n';
288 }
289}
290
291#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
292LLVM_DUMP_METHOD void IVUsers::dump() const { print(dbgs()); }
293#endif
294
295void IVUsers::releaseMemory() {
296 Processed.clear();
297 IVUses.clear();
298}
299
300IVUsersWrapperPass::IVUsersWrapperPass() : LoopPass(ID) {}
301
302void IVUsersWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
303 AU.addRequired<AssumptionCacheTracker>();
304 AU.addRequired<LoopInfoWrapperPass>();
305 AU.addRequired<DominatorTreeWrapperPass>();
306 AU.addRequired<ScalarEvolutionWrapperPass>();
307 AU.setPreservesAll();
308}
309
310bool IVUsersWrapperPass::runOnLoop(Loop *L, LPPassManager &LPM) {
311 auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
312 F&: *L->getHeader()->getParent());
313 auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
314 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
315 auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
316
317 IU.reset(p: new IVUsers(L, AC, LI, DT, SE));
318 return false;
319}
320
321void IVUsersWrapperPass::print(raw_ostream &OS, const Module *M) const {
322 IU->print(OS, M);
323}
324
325void IVUsersWrapperPass::releaseMemory() { IU->releaseMemory(); }
326
327/// getReplacementExpr - Return a SCEV expression which computes the
328/// value of the OperandValToReplace.
329const SCEV *IVUsers::getReplacementExpr(const IVStrideUse &IU) const {
330 return SE->getSCEV(V: IU.getOperandValToReplace());
331}
332
333/// getExpr - Return the expression for the use.
334const SCEV *IVUsers::getExpr(const IVStrideUse &IU) const {
335 const SCEV *Replacement = getReplacementExpr(IU);
336 return normalizeForPostIncUse(S: Replacement, Loops: IU.getPostIncLoops(), SE&: *SE);
337}
338
339static const SCEVAddRecExpr *findAddRecForLoop(const SCEV *S, const Loop *L) {
340 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Val: S)) {
341 if (AR->getLoop() == L)
342 return AR;
343 return findAddRecForLoop(S: AR->getStart(), L);
344 }
345
346 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Val: S)) {
347 for (const SCEV *Op : Add->operands())
348 if (const SCEVAddRecExpr *AR = findAddRecForLoop(S: Op, L))
349 return AR;
350 return nullptr;
351 }
352
353 return nullptr;
354}
355
356const SCEV *IVUsers::getStride(const IVStrideUse &IU, const Loop *L) const {
357 const SCEV *Expr = getExpr(IU);
358 if (!Expr)
359 return nullptr;
360 if (const SCEVAddRecExpr *AR = findAddRecForLoop(S: Expr, L))
361 return AR->getStepRecurrence(SE&: *SE);
362 return nullptr;
363}
364
365void IVStrideUse::transformToPostInc(const Loop *L) {
366 PostIncLoops.insert(Ptr: L);
367}
368
369void IVStrideUse::deleted() {
370 // Remove this user from the list.
371 Parent->Processed.erase(Ptr: this->getUser());
372 Parent->IVUses.erase(IT: this);
373 // this now dangles!
374}
375