1 //===- IVUsers.cpp - Induction Variable Users -------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements bookkeeping for "interesting" users of expressions
11 // computed from induction variables.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "iv-users"
16 #include "llvm/Analysis/IVUsers.h"
17 #include "llvm/Constants.h"
18 #include "llvm/Instructions.h"
19 #include "llvm/Type.h"
20 #include "llvm/DerivedTypes.h"
21 #include "llvm/Analysis/Dominators.h"
22 #include "llvm/Analysis/LoopPass.h"
23 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
24 #include "llvm/Assembly/AsmAnnotationWriter.h"
25 #include "llvm/ADT/STLExtras.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/raw_ostream.h"
32 INITIALIZE_PASS(IVUsers, "iv-users", "Induction Variable Users", false, true);
34 Pass *llvm::createIVUsersPass() {
38 /// findInterestingAddRec - Test whether the given expression is interesting.
39 /// Return the addrec with the current loop which makes it interesting, or
40 /// null if it is not interesting.
41 const SCEVAddRecExpr *IVUsers::findInterestingAddRec(const SCEV *S) const {
42 // An addrec is interesting if it's affine or if it has an interesting start.
43 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
44 // Keep things simple. Don't touch loop-variant strides.
45 if (AR->getLoop() == L)
47 // We don't yet know how to do effective SCEV expansions for addrecs
48 // with interesting steps.
49 if (findInterestingAddRec(AR->getStepRecurrence(*SE)))
51 // Otherwise recurse to see if the start value is interesting.
52 return findInterestingAddRec(AR->getStart());
55 // An add is interesting if exactly one of its operands is interesting.
56 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
57 for (SCEVAddExpr::op_iterator OI = Add->op_begin(), OE = Add->op_end();
59 if (const SCEVAddRecExpr *AR = findInterestingAddRec(*OI))
64 // Nothing else is interesting here.
68 bool IVUsers::isInterestingUser(const Instruction *User) const {
69 // Void and FP expressions cannot be reduced.
70 if (!SE->isSCEVable(User->getType()))
73 // LSR is not APInt clean, do not touch integers bigger than 64-bits.
74 if (SE->getTypeSizeInBits(User->getType()) > 64)
77 // Don't descend into PHI nodes outside the current loop.
78 if (LI->getLoopFor(User->getParent()) != L &&
82 // Otherwise, it may be interesting.
86 /// AddUsersIfInteresting - Inspect the specified instruction. If it is a
87 /// reducible SCEV, recursively add its users to the IVUsesByStride set and
88 /// return true. Otherwise, return false.
89 void IVUsers::AddUsersIfInteresting(Instruction *I) {
90 // Stop if we've seen this before.
91 if (!Processed.insert(I))
94 // If this PHI node is not SCEVable, ignore it.
95 if (!SE->isSCEVable(I->getType()))
98 // If this PHI node is not an addrec for this loop, ignore it.
99 const SCEVAddRecExpr *Expr = findInterestingAddRec(SE->getSCEV(I));
103 // Walk the def-use graph.
104 SmallVector<std::pair<Instruction *, const SCEVAddRecExpr *>, 16> Worklist;
105 Worklist.push_back(std::make_pair(I, Expr));
107 std::pair<Instruction *, const SCEVAddRecExpr *> P =
108 Worklist.pop_back_val();
109 Instruction *Op = P.first;
110 const SCEVAddRecExpr *OpAR = P.second;
113 SmallPtrSet<Instruction *, 8> VisitedUsers;
114 for (Value::use_iterator UI = Op->use_begin(), E = Op->use_end();
116 // Don't visit any individual user more than once.
117 Instruction *User = cast<Instruction>(*UI);
118 if (!VisitedUsers.insert(User))
121 // If it's an affine addrec (which we can pretty safely re-expand) inside
122 // the loop, or a potentially non-affine addrec outside the loop (which
123 // we can evaluate outside of the loop), follow it.
124 if (OpAR->isAffine() || !L->contains(User)) {
125 if (isInterestingUser(User)) {
126 const SCEV *UserExpr = SE->getSCEV(User);
128 if (const SCEVAddRecExpr *AR = findInterestingAddRec(UserExpr)) {
129 // Interesting. Keep searching.
130 if (Processed.insert(User))
131 Worklist.push_back(std::make_pair(User, AR));
137 // Otherwise, this is the point where the def-use chain
138 // becomes uninteresting. Call it an IV User.
141 } while (!Worklist.empty());
144 IVStrideUse &IVUsers::AddUser(Instruction *User, Value *Operand) {
145 IVUses.push_back(new IVStrideUse(this, User, Operand));
146 IVStrideUse &NewUse = IVUses.back();
148 // Auto-detect and remember post-inc loops for this expression.
149 const SCEV *S = SE->getSCEV(Operand);
150 (void)TransformForPostIncUse(NormalizeAutodetect,
161 void IVUsers::getAnalysisUsage(AnalysisUsage &AU) const {
162 AU.addRequired<LoopInfo>();
163 AU.addRequired<DominatorTree>();
164 AU.addRequired<ScalarEvolution>();
165 AU.setPreservesAll();
168 bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) {
171 LI = &getAnalysis<LoopInfo>();
172 DT = &getAnalysis<DominatorTree>();
173 SE = &getAnalysis<ScalarEvolution>();
175 // Find all uses of induction variables in this loop, and categorize
176 // them by stride. Start by finding all of the PHI nodes in the header for
177 // this loop. If they are induction variables, inspect their uses.
178 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I)
179 AddUsersIfInteresting(I);
184 void IVUsers::print(raw_ostream &OS, const Module *M) const {
185 OS << "IV Users for loop ";
186 WriteAsOperand(OS, L->getHeader(), false);
187 if (SE->hasLoopInvariantBackedgeTakenCount(L)) {
188 OS << " with backedge-taken count "
189 << *SE->getBackedgeTakenCount(L);
193 // Use a default AssemblyAnnotationWriter to suppress the default info
194 // comments, which aren't relevant here.
195 AssemblyAnnotationWriter Annotator;
196 for (ilist<IVStrideUse>::const_iterator UI = IVUses.begin(),
197 E = IVUses.end(); UI != E; ++UI) {
199 WriteAsOperand(OS, UI->getOperandValToReplace(), false);
200 OS << " = " << *getReplacementExpr(*UI);
201 for (PostIncLoopSet::const_iterator
202 I = UI->PostIncLoops.begin(),
203 E = UI->PostIncLoops.end(); I != E; ++I) {
204 OS << " (post-inc with loop ";
205 WriteAsOperand(OS, (*I)->getHeader(), false);
209 UI->getUser()->print(OS, &Annotator);
214 void IVUsers::dump() const {
218 void IVUsers::releaseMemory() {
223 /// getReplacementExpr - Return a SCEV expression which computes the
224 /// value of the OperandValToReplace.
225 const SCEV *IVUsers::getReplacementExpr(const IVStrideUse &IU) const {
226 return SE->getSCEV(IU.getOperandValToReplace());
229 /// getExpr - Return the expression for the use.
230 const SCEV *IVUsers::getExpr(const IVStrideUse &IU) const {
232 TransformForPostIncUse(Normalize, getReplacementExpr(IU),
233 IU.getUser(), IU.getOperandValToReplace(),
234 const_cast<PostIncLoopSet &>(IU.getPostIncLoops()),
238 static const SCEVAddRecExpr *findAddRecForLoop(const SCEV *S, const Loop *L) {
239 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
240 if (AR->getLoop() == L)
242 return findAddRecForLoop(AR->getStart(), L);
245 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
246 for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end();
248 if (const SCEVAddRecExpr *AR = findAddRecForLoop(*I, L))
256 const SCEV *IVUsers::getStride(const IVStrideUse &IU, const Loop *L) const {
257 if (const SCEVAddRecExpr *AR = findAddRecForLoop(getExpr(IU), L))
258 return AR->getStepRecurrence(*SE);
262 void IVStrideUse::transformToPostInc(const Loop *L) {
263 PostIncLoops.insert(L);
266 void IVStrideUse::deleted() {
267 // Remove this user from the list.
268 Parent->IVUses.erase(this);