Deleted Added
sdiff udiff text old ( 208954 ) new ( 212904 )
full compact
IVUsers.cpp (208954) IVUsers.cpp (212904)
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//===----------------------------------------------------------------------===//

--- 7 unchanged lines hidden (view full) ---

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"
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//===----------------------------------------------------------------------===//

--- 7 unchanged lines hidden (view full) ---

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"
28#include <algorithm>
29using namespace llvm;
30
31char IVUsers::ID = 0;
24#include "llvm/ADT/STLExtras.h"
25#include "llvm/Support/Debug.h"
26#include "llvm/Support/raw_ostream.h"
27#include <algorithm>
28using namespace llvm;
29
30char IVUsers::ID = 0;
32static RegisterPass<IVUsers>
33X("iv-users", "Induction Variable Users", false, true);
31INITIALIZE_PASS(IVUsers, "iv-users", "Induction Variable Users", false, true);
34
35Pass *llvm::createIVUsersPass() {
36 return new IVUsers();
37}
38
39/// isInteresting - Test whether the given expression is "interesting" when
40/// used by the given expression, within the context of analyzing the
41/// given loop.
32
33Pass *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.
42static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L) {
43 // Anything loop-invariant is interesting.
44 if (!isa<SCEVUnknown>(S) && S->isLoopInvariant(L))
45 return true;
46
40static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L,
41 ScalarEvolution *SE) {
47 // An addrec is interesting if it's affine or if it has an interesting start.
48 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
49 // Keep things simple. Don't touch loop-variant strides.
50 if (AR->getLoop() == L)
51 return AR->isAffine() || !L->contains(I);
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);
52 // Otherwise recurse to see if the start value is interesting.
53 return isInteresting(AR->getStart(), I, L);
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);
54 }
55
52 }
53
56 // An add is interesting if any of its operands is.
54 // An add is interesting if exactly one of its operands is interesting.
57 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
55 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
56 bool AnyInterestingYet = false;
58 for (SCEVAddExpr::op_iterator OI = Add->op_begin(), OE = Add->op_end();
59 OI != OE; ++OI)
57 for (SCEVAddExpr::op_iterator OI = Add->op_begin(), OE = Add->op_end();
58 OI != OE; ++OI)
60 if (isInteresting(*OI, I, L))
61 return true;
62 return false;
59 if (isInteresting(*OI, I, L, SE)) {
60 if (AnyInterestingYet)
61 return false;
62 AnyInterestingYet = true;
63 }
64 return AnyInterestingYet;
63 }
64
65 // Nothing else is interesting here.
66 return false;
67}
68
69/// AddUsersIfInteresting - Inspect the specified instruction. If it is a
70/// reducible SCEV, recursively add its users to the IVUsesByStride set and

--- 9 unchanged lines hidden (view full) ---

80 if (!Processed.insert(I))
81 return true; // Instruction already handled.
82
83 // Get the symbolic expression for this instruction.
84 const SCEV *ISE = SE->getSCEV(I);
85
86 // If we've come to an uninteresting expression, stop the traversal and
87 // call this a user.
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

--- 9 unchanged lines hidden (view full) ---

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.
88 if (!isInteresting(ISE, I, L))
90 if (!isInteresting(ISE, I, L, SE))
89 return false;
90
91 SmallPtrSet<Instruction *, 4> UniqueUsers;
92 for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
93 UI != E; ++UI) {
94 Instruction *User = cast<Instruction>(*UI);
95 if (!UniqueUsers.insert(User))
96 continue;

--- 39 unchanged lines hidden (view full) ---

136}
137
138IVStrideUse &IVUsers::AddUser(Instruction *User, Value *Operand) {
139 IVUses.push_back(new IVStrideUse(this, User, Operand));
140 return IVUses.back();
141}
142
143IVUsers::IVUsers()
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;

--- 39 unchanged lines hidden (view full) ---

138}
139
140IVStrideUse &IVUsers::AddUser(Instruction *User, Value *Operand) {
141 IVUses.push_back(new IVStrideUse(this, User, Operand));
142 return IVUses.back();
143}
144
145IVUsers::IVUsers()
144 : LoopPass(&ID) {
146 : LoopPass(ID) {
145}
146
147void IVUsers::getAnalysisUsage(AnalysisUsage &AU) const {
148 AU.addRequired<LoopInfo>();
149 AU.addRequired<DominatorTree>();
150 AU.addRequired<ScalarEvolution>();
151 AU.setPreservesAll();
152}

--- 18 unchanged lines hidden (view full) ---

171 OS << "IV Users for loop ";
172 WriteAsOperand(OS, L->getHeader(), false);
173 if (SE->hasLoopInvariantBackedgeTakenCount(L)) {
174 OS << " with backedge-taken count "
175 << *SE->getBackedgeTakenCount(L);
176 }
177 OS << ":\n";
178
147}
148
149void IVUsers::getAnalysisUsage(AnalysisUsage &AU) const {
150 AU.addRequired<LoopInfo>();
151 AU.addRequired<DominatorTree>();
152 AU.addRequired<ScalarEvolution>();
153 AU.setPreservesAll();
154}

--- 18 unchanged lines hidden (view full) ---

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
179 // Use a default AssemblyAnnotationWriter to suppress the default info
180 // comments, which aren't relevant here.
181 AssemblyAnnotationWriter Annotator;
182 for (ilist<IVStrideUse>::const_iterator UI = IVUses.begin(),
183 E = IVUses.end(); UI != E; ++UI) {
184 OS << " ";
185 WriteAsOperand(OS, UI->getOperandValToReplace(), false);
186 OS << " = " << *getReplacementExpr(*UI);
187 for (PostIncLoopSet::const_iterator
188 I = UI->PostIncLoops.begin(),
189 E = UI->PostIncLoops.end(); I != E; ++I) {
190 OS << " (post-inc with loop ";
191 WriteAsOperand(OS, (*I)->getHeader(), false);
192 OS << ")";
193 }
194 OS << " in ";
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 ";
195 UI->getUser()->print(OS, &Annotator);
194 UI->getUser()->print(OS);
196 OS << '\n';
197 }
198}
199
200void IVUsers::dump() const {
201 print(dbgs());
202}
203

--- 53 unchanged lines hidden --- 		195 OS << '\n';
196 }
197}
198
199void IVUsers::dump() const {
200 print(dbgs());
201}
202

--- 53 unchanged lines hidden ---