1 //===- IVUsers.cpp - Induction Variable Users -------------------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements bookkeeping for "interesting" users of expressions
11 // computed from induction variables.
12 //
13 //===----------------------------------------------------------------------===//
14 
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/ADT/STLExtras.h"
25 #include "llvm/Support/Debug.h"
26 #include "llvm/Support/raw_ostream.h"
27 #include <algorithm>
28 using namespace llvm;
29 
30 char IVUsers::ID = 0;
31 INITIALIZE_PASS(IVUsers, "iv-users", "Induction Variable Users", false, true);
32 
33 Pass *llvm::createIVUsersPass() {
34   return new IVUsers();
35 }
36 
37 /// isInteresting - Test whether the given expression is "interesting" when
38 /// used by the given expression, within the context of analyzing the
39 /// given loop.
40 static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L,
41                           ScalarEvolution *SE) {
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)
46       return AR->isAffine() || !L->contains(I);
47     // Otherwise recurse to see if the start value is interesting, and that
48     // the step value is not interesting, since we don't yet know how to
49     // do effective SCEV expansions for addrecs with interesting steps.
50     return isInteresting(AR->getStart(), I, L, SE) &&
51           !isInteresting(AR->getStepRecurrence(*SE), I, L, SE);
52   }
53 
54   // An add is interesting if exactly one of its operands is interesting.
55   if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
56     bool AnyInterestingYet = false;
57     for (SCEVAddExpr::op_iterator OI = Add->op_begin(), OE = Add->op_end();
58          OI != OE; ++OI)
59       if (isInteresting(*OI, I, L, SE)) {
60         if (AnyInterestingYet)
61           return false;
62         AnyInterestingYet = true;
63       }
64     return AnyInterestingYet;
65   }
66 
67   // Nothing else is interesting here.
68   return false;
69 }
70 
71 /// AddUsersIfInteresting - Inspect the specified instruction.  If it is a
72 /// reducible SCEV, recursively add its users to the IVUsesByStride set and
73 /// return true.  Otherwise, return false.
74 bool IVUsers::AddUsersIfInteresting(Instruction *I) {
75   if (!SE->isSCEVable(I->getType()))
76     return false;   // Void and FP expressions cannot be reduced.
77 
78   // LSR is not APInt clean, do not touch integers bigger than 64-bits.
79   if (SE->getTypeSizeInBits(I->getType()) > 64)
80     return false;
81 
82   if (!Processed.insert(I))
83     return true;    // Instruction already handled.
84 
85   // Get the symbolic expression for this instruction.
86   const SCEV *ISE = SE->getSCEV(I);
87 
88   // If we've come to an uninteresting expression, stop the traversal and
89   // call this a user.
90   if (!isInteresting(ISE, I, L, SE))
91     return false;
92 
93   SmallPtrSet<Instruction *, 4> UniqueUsers;
94   for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
95        UI != E; ++UI) {
96     Instruction *User = cast<Instruction>(*UI);
97     if (!UniqueUsers.insert(User))
98       continue;
99 
100     // Do not infinitely recurse on PHI nodes.
101     if (isa<PHINode>(User) && Processed.count(User))
102       continue;
103 
104     // Descend recursively, but not into PHI nodes outside the current loop.
105     // It's important to see the entire expression outside the loop to get
106     // choices that depend on addressing mode use right, although we won't
107     // consider references outside the loop in all cases.
108     // If User is already in Processed, we don't want to recurse into it again,
109     // but do want to record a second reference in the same instruction.
110     bool AddUserToIVUsers = false;
111     if (LI->getLoopFor(User->getParent()) != L) {
112       if (isa<PHINode>(User) || Processed.count(User) ||
113           !AddUsersIfInteresting(User)) {
114         DEBUG(dbgs() << "FOUND USER in other loop: " << *User << '\n'
115                      << "   OF SCEV: " << *ISE << '\n');
116         AddUserToIVUsers = true;
117       }
118     } else if (Processed.count(User) ||
119                !AddUsersIfInteresting(User)) {
120       DEBUG(dbgs() << "FOUND USER: " << *User << '\n'
121                    << "   OF SCEV: " << *ISE << '\n');
122       AddUserToIVUsers = true;
123     }
124 
125     if (AddUserToIVUsers) {
126       // Okay, we found a user that we cannot reduce.
127       IVUses.push_back(new IVStrideUse(this, User, I));
128       IVStrideUse &NewUse = IVUses.back();
129       // Transform the expression into a normalized form.
130       ISE = TransformForPostIncUse(NormalizeAutodetect,
131                                    ISE, User, I,
132                                    NewUse.PostIncLoops,
133                                    *SE, *DT);
134       DEBUG(dbgs() << "   NORMALIZED TO: " << *ISE << '\n');
135     }
136   }
137   return true;
138 }
139 
140 IVStrideUse &IVUsers::AddUser(Instruction *User, Value *Operand) {
141   IVUses.push_back(new IVStrideUse(this, User, Operand));
142   return IVUses.back();
143 }
144 
145 IVUsers::IVUsers()
146  : LoopPass(ID) {
147 }
148 
149 void IVUsers::getAnalysisUsage(AnalysisUsage &AU) const {
150   AU.addRequired<LoopInfo>();
151   AU.addRequired<DominatorTree>();
152   AU.addRequired<ScalarEvolution>();
153   AU.setPreservesAll();
154 }
155 
156 bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) {
157 
158   L = l;
159   LI = &getAnalysis<LoopInfo>();
160   DT = &getAnalysis<DominatorTree>();
161   SE = &getAnalysis<ScalarEvolution>();
162 
163   // Find all uses of induction variables in this loop, and categorize
164   // them by stride.  Start by finding all of the PHI nodes in the header for
165   // this loop.  If they are induction variables, inspect their uses.
166   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I)
167     (void)AddUsersIfInteresting(I);
168 
169   return false;
170 }
171 
172 void IVUsers::print(raw_ostream &OS, const Module *M) const {
173   OS << "IV Users for loop ";
174   WriteAsOperand(OS, L->getHeader(), false);
175   if (SE->hasLoopInvariantBackedgeTakenCount(L)) {
176     OS << " with backedge-taken count "
177        << *SE->getBackedgeTakenCount(L);
178   }
179   OS << ":\n";
180 
181   for (ilist<IVStrideUse>::const_iterator UI = IVUses.begin(),
182        E = IVUses.end(); UI != E; ++UI) {
183     OS << "  ";
184     WriteAsOperand(OS, UI->getOperandValToReplace(), false);
185     OS << " = " << *getReplacementExpr(*UI);
186     for (PostIncLoopSet::const_iterator
187          I = UI->PostIncLoops.begin(),
188          E = UI->PostIncLoops.end(); I != E; ++I) {
189       OS << " (post-inc with loop ";
190       WriteAsOperand(OS, (*I)->getHeader(), false);
191       OS << ")";
192     }
193     OS << " in  ";
194     UI->getUser()->print(OS);
195     OS << '\n';
196   }
197 }
198 
199 void IVUsers::dump() const {
200   print(dbgs());
201 }
202 
203 void IVUsers::releaseMemory() {
204   Processed.clear();
205   IVUses.clear();
206 }
207 
208 /// getReplacementExpr - Return a SCEV expression which computes the
209 /// value of the OperandValToReplace.
210 const SCEV *IVUsers::getReplacementExpr(const IVStrideUse &IU) const {
211   return SE->getSCEV(IU.getOperandValToReplace());
212 }
213 
214 /// getExpr - Return the expression for the use.
215 const SCEV *IVUsers::getExpr(const IVStrideUse &IU) const {
216   return
217     TransformForPostIncUse(Normalize, getReplacementExpr(IU),
218                            IU.getUser(), IU.getOperandValToReplace(),
219                            const_cast<PostIncLoopSet &>(IU.getPostIncLoops()),
220                            *SE, *DT);
221 }
222 
223 static const SCEVAddRecExpr *findAddRecForLoop(const SCEV *S, const Loop *L) {
224   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
225     if (AR->getLoop() == L)
226       return AR;
227     return findAddRecForLoop(AR->getStart(), L);
228   }
229 
230   if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
231     for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end();
232          I != E; ++I)
233       if (const SCEVAddRecExpr *AR = findAddRecForLoop(*I, L))
234         return AR;
235     return 0;
236   }
237 
238   return 0;
239 }
240 
241 const SCEV *IVUsers::getStride(const IVStrideUse &IU, const Loop *L) const {
242   if (const SCEVAddRecExpr *AR = findAddRecForLoop(getExpr(IU), L))
243     return AR->getStepRecurrence(*SE);
244   return 0;
245 }
246 
247 void IVStrideUse::transformToPostInc(const Loop *L) {
248   PostIncLoops.insert(L);
249 }
250 
251 void IVStrideUse::deleted() {
252   // Remove this user from the list.
253   Parent->IVUses.erase(this);
254   // this now dangles!
255 }
256