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/Target/TargetData.h"
25 #include "llvm/Assembly/Writer.h"
26 #include "llvm/ADT/STLExtras.h"
27 #include "llvm/Support/Debug.h"
28 #include "llvm/Support/raw_ostream.h"
33 INITIALIZE_PASS_BEGIN(IVUsers
, "iv-users",
34 "Induction Variable Users", false, true)
35 INITIALIZE_PASS_DEPENDENCY(LoopInfo
)
36 INITIALIZE_PASS_DEPENDENCY(DominatorTree
)
37 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution
)
38 INITIALIZE_PASS_END(IVUsers
, "iv-users",
39 "Induction Variable Users", false, true)
41 Pass
*llvm::createIVUsersPass() {
45 /// isInteresting - Test whether the given expression is "interesting" when
46 /// used by the given expression, within the context of analyzing the
48 static bool isInteresting(const SCEV
*S
, const Instruction
*I
, const Loop
*L
,
49 ScalarEvolution
*SE
, LoopInfo
*LI
) {
50 // An addrec is interesting if it's affine or if it has an interesting start.
51 if (const SCEVAddRecExpr
*AR
= dyn_cast
<SCEVAddRecExpr
>(S
)) {
52 // Keep things simple. Don't touch loop-variant strides unless they're
53 // only used outside the loop and we can simplify them.
54 if (AR
->getLoop() == L
)
55 return AR
->isAffine() ||
57 SE
->getSCEVAtScope(AR
, LI
->getLoopFor(I
->getParent())) != AR
);
58 // Otherwise recurse to see if the start value is interesting, and that
59 // the step value is not interesting, since we don't yet know how to
60 // do effective SCEV expansions for addrecs with interesting steps.
61 return isInteresting(AR
->getStart(), I
, L
, SE
, LI
) &&
62 !isInteresting(AR
->getStepRecurrence(*SE
), I
, L
, SE
, LI
);
65 // An add is interesting if exactly one of its operands is interesting.
66 if (const SCEVAddExpr
*Add
= dyn_cast
<SCEVAddExpr
>(S
)) {
67 bool AnyInterestingYet
= false;
68 for (SCEVAddExpr::op_iterator OI
= Add
->op_begin(), OE
= Add
->op_end();
70 if (isInteresting(*OI
, I
, L
, SE
, LI
)) {
71 if (AnyInterestingYet
)
73 AnyInterestingYet
= true;
75 return AnyInterestingYet
;
78 // Nothing else is interesting here.
82 /// AddUsersIfInteresting - Inspect the specified instruction. If it is a
83 /// reducible SCEV, recursively add its users to the IVUsesByStride set and
84 /// return true. Otherwise, return false.
85 bool IVUsers::AddUsersIfInteresting(Instruction
*I
) {
86 if (!SE
->isSCEVable(I
->getType()))
87 return false; // Void and FP expressions cannot be reduced.
89 // LSR is not APInt clean, do not touch integers bigger than 64-bits.
90 // Also avoid creating IVs of non-native types. For example, we don't want a
91 // 64-bit IV in 32-bit code just because the loop has one 64-bit cast.
92 uint64_t Width
= SE
->getTypeSizeInBits(I
->getType());
93 if (Width
> 64 || (TD
&& !TD
->isLegalInteger(Width
)))
96 if (!Processed
.insert(I
))
97 return true; // Instruction already handled.
99 // Get the symbolic expression for this instruction.
100 const SCEV
*ISE
= SE
->getSCEV(I
);
102 // If we've come to an uninteresting expression, stop the traversal and
104 if (!isInteresting(ISE
, I
, L
, SE
, LI
))
107 SmallPtrSet
<Instruction
*, 4> UniqueUsers
;
108 for (Value::use_iterator UI
= I
->use_begin(), E
= I
->use_end();
110 Instruction
*User
= cast
<Instruction
>(*UI
);
111 if (!UniqueUsers
.insert(User
))
114 // Do not infinitely recurse on PHI nodes.
115 if (isa
<PHINode
>(User
) && Processed
.count(User
))
118 // Descend recursively, but not into PHI nodes outside the current loop.
119 // It's important to see the entire expression outside the loop to get
120 // choices that depend on addressing mode use right, although we won't
121 // consider references outside the loop in all cases.
122 // If User is already in Processed, we don't want to recurse into it again,
123 // but do want to record a second reference in the same instruction.
124 bool AddUserToIVUsers
= false;
125 if (LI
->getLoopFor(User
->getParent()) != L
) {
126 if (isa
<PHINode
>(User
) || Processed
.count(User
) ||
127 !AddUsersIfInteresting(User
)) {
128 DEBUG(dbgs() << "FOUND USER in other loop: " << *User
<< '\n'
129 << " OF SCEV: " << *ISE
<< '\n');
130 AddUserToIVUsers
= true;
132 } else if (Processed
.count(User
) || !AddUsersIfInteresting(User
)) {
133 DEBUG(dbgs() << "FOUND USER: " << *User
<< '\n'
134 << " OF SCEV: " << *ISE
<< '\n');
135 AddUserToIVUsers
= true;
138 if (AddUserToIVUsers
) {
139 // Okay, we found a user that we cannot reduce.
140 IVUses
.push_back(new IVStrideUse(this, User
, I
));
141 IVStrideUse
&NewUse
= IVUses
.back();
142 // Autodetect the post-inc loop set, populating NewUse.PostIncLoops.
143 // The regular return value here is discarded; instead of recording
144 // it, we just recompute it when we need it.
145 ISE
= TransformForPostIncUse(NormalizeAutodetect
,
149 DEBUG(dbgs() << " NORMALIZED TO: " << *ISE
<< '\n');
155 IVStrideUse
&IVUsers::AddUser(Instruction
*User
, Value
*Operand
) {
156 IVUses
.push_back(new IVStrideUse(this, User
, Operand
));
157 return IVUses
.back();
162 initializeIVUsersPass(*PassRegistry::getPassRegistry());
165 void IVUsers::getAnalysisUsage(AnalysisUsage
&AU
) const {
166 AU
.addRequired
<LoopInfo
>();
167 AU
.addRequired
<DominatorTree
>();
168 AU
.addRequired
<ScalarEvolution
>();
169 AU
.setPreservesAll();
172 bool IVUsers::runOnLoop(Loop
*l
, LPPassManager
&LPM
) {
175 LI
= &getAnalysis
<LoopInfo
>();
176 DT
= &getAnalysis
<DominatorTree
>();
177 SE
= &getAnalysis
<ScalarEvolution
>();
178 TD
= getAnalysisIfAvailable
<TargetData
>();
180 // Find all uses of induction variables in this loop, and categorize
181 // them by stride. Start by finding all of the PHI nodes in the header for
182 // this loop. If they are induction variables, inspect their uses.
183 for (BasicBlock::iterator I
= L
->getHeader()->begin(); isa
<PHINode
>(I
); ++I
)
184 (void)AddUsersIfInteresting(I
);
189 void IVUsers::print(raw_ostream
&OS
, const Module
*M
) const {
190 OS
<< "IV Users for loop ";
191 WriteAsOperand(OS
, L
->getHeader(), false);
192 if (SE
->hasLoopInvariantBackedgeTakenCount(L
)) {
193 OS
<< " with backedge-taken count "
194 << *SE
->getBackedgeTakenCount(L
);
198 for (ilist
<IVStrideUse
>::const_iterator UI
= IVUses
.begin(),
199 E
= IVUses
.end(); UI
!= E
; ++UI
) {
201 WriteAsOperand(OS
, UI
->getOperandValToReplace(), false);
202 OS
<< " = " << *getReplacementExpr(*UI
);
203 for (PostIncLoopSet::const_iterator
204 I
= UI
->PostIncLoops
.begin(),
205 E
= UI
->PostIncLoops
.end(); I
!= E
; ++I
) {
206 OS
<< " (post-inc with loop ";
207 WriteAsOperand(OS
, (*I
)->getHeader(), false);
211 UI
->getUser()->print(OS
);
216 void IVUsers::dump() const {
220 void IVUsers::releaseMemory() {
225 /// getReplacementExpr - Return a SCEV expression which computes the
226 /// value of the OperandValToReplace.
227 const SCEV
*IVUsers::getReplacementExpr(const IVStrideUse
&IU
) const {
228 return SE
->getSCEV(IU
.getOperandValToReplace());
231 /// getExpr - Return the expression for the use.
232 const SCEV
*IVUsers::getExpr(const IVStrideUse
&IU
) const {
234 TransformForPostIncUse(Normalize
, getReplacementExpr(IU
),
235 IU
.getUser(), IU
.getOperandValToReplace(),
236 const_cast<PostIncLoopSet
&>(IU
.getPostIncLoops()),
240 static const SCEVAddRecExpr
*findAddRecForLoop(const SCEV
*S
, const Loop
*L
) {
241 if (const SCEVAddRecExpr
*AR
= dyn_cast
<SCEVAddRecExpr
>(S
)) {
242 if (AR
->getLoop() == L
)
244 return findAddRecForLoop(AR
->getStart(), L
);
247 if (const SCEVAddExpr
*Add
= dyn_cast
<SCEVAddExpr
>(S
)) {
248 for (SCEVAddExpr::op_iterator I
= Add
->op_begin(), E
= Add
->op_end();
250 if (const SCEVAddRecExpr
*AR
= findAddRecForLoop(*I
, L
))
258 const SCEV
*IVUsers::getStride(const IVStrideUse
&IU
, const Loop
*L
) const {
259 if (const SCEVAddRecExpr
*AR
= findAddRecForLoop(getExpr(IU
), L
))
260 return AR
->getStepRecurrence(*SE
);
264 void IVStrideUse::transformToPostInc(const Loop
*L
) {
265 PostIncLoops
.insert(L
);
268 void IVStrideUse::deleted() {
269 // Remove this user from the list.
270 Parent
->IVUses
.erase(this);