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

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

48 return true;
49 return false;
50 }
51 if (const SCEVAddRecExpr *AE = dyn_cast<SCEVAddRecExpr>(S)) {
52 if (const Loop *newLoop = AE->getLoop()) {
53 if (newLoop == L)
54 return false;
55 // if newLoop is an outer loop of L, this is OK.
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//===----------------------------------------------------------------------===//

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

48 return true;
49 return false;
50 }
51 if (const SCEVAddRecExpr *AE = dyn_cast<SCEVAddRecExpr>(S)) {
52 if (const Loop *newLoop = AE->getLoop()) {
53 if (newLoop == L)
54 return false;
55 // if newLoop is an outer loop of L, this is OK.
56 if (newLoop->contains(L->getHeader()))
56 if (newLoop->contains(L))
57 return false;
58 }
59 return true;
60 }
61 if (const SCEVUDivExpr *DE = dyn_cast<SCEVUDivExpr>(S))
62 return containsAddRecFromDifferentLoop(DE->getLHS(), L) ||
63 containsAddRecFromDifferentLoop(DE->getRHS(), L);
64#if 0

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

123
124 // If stride is an instruction, make sure it properly dominates the header.
125 // Otherwise we could end up with a use before def situation.
126 if (!isa<SCEVConstant>(AddRecStride)) {
127 BasicBlock *Header = L->getHeader();
128 if (!AddRecStride->properlyDominates(Header, DT))
129 return false;
130
57 return false;
58 }
59 return true;
60 }
61 if (const SCEVUDivExpr *DE = dyn_cast<SCEVUDivExpr>(S))
62 return containsAddRecFromDifferentLoop(DE->getLHS(), L) ||
63 containsAddRecFromDifferentLoop(DE->getRHS(), L);
64#if 0

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

123
124 // If stride is an instruction, make sure it properly dominates the header.
125 // Otherwise we could end up with a use before def situation.
126 if (!isa<SCEVConstant>(AddRecStride)) {
127 BasicBlock *Header = L->getHeader();
128 if (!AddRecStride->properlyDominates(Header, DT))
129 return false;
130
131 DEBUG(errs() << "[" << L->getHeader()->getName()
131 DEBUG(dbgs() << "[" << L->getHeader()->getName()
132 << "] Variable stride: " << *AddRec << "\n");
133 }
134
135 Stride = AddRecStride;
136 return true;
137}
138
139/// IVUseShouldUsePostIncValue - We have discovered a "User" of an IV expression
140/// and now we need to decide whether the user should use the preinc or post-inc
141/// value. If this user should use the post-inc version of the IV, return true.
142///
143/// Choosing wrong here can break dominance properties (if we choose to use the
144/// post-inc value when we cannot) or it can end up adding extra live-ranges to
145/// the loop, resulting in reg-reg copies (if we use the pre-inc value when we
146/// should use the post-inc value).
147static bool IVUseShouldUsePostIncValue(Instruction *User, Instruction *IV,
148 Loop *L, LoopInfo *LI, DominatorTree *DT,
149 Pass *P) {
150 // If the user is in the loop, use the preinc value.
132 << "] Variable stride: " << *AddRec << "\n");
133 }
134
135 Stride = AddRecStride;
136 return true;
137}
138
139/// IVUseShouldUsePostIncValue - We have discovered a "User" of an IV expression
140/// and now we need to decide whether the user should use the preinc or post-inc
141/// value. If this user should use the post-inc version of the IV, return true.
142///
143/// Choosing wrong here can break dominance properties (if we choose to use the
144/// post-inc value when we cannot) or it can end up adding extra live-ranges to
145/// the loop, resulting in reg-reg copies (if we use the pre-inc value when we
146/// should use the post-inc value).
147static bool IVUseShouldUsePostIncValue(Instruction *User, Instruction *IV,
148 Loop *L, LoopInfo *LI, DominatorTree *DT,
149 Pass *P) {
150 // If the user is in the loop, use the preinc value.
151 if (L->contains(User->getParent())) return false;
151 if (L->contains(User)) return false;
152
153 BasicBlock *LatchBlock = L->getLoopLatch();
154 if (!LatchBlock)
155 return false;
156
157 // Ok, the user is outside of the loop. If it is dominated by the latch
158 // block, use the post-inc value.
159 if (DT->dominates(LatchBlock, User->getParent()))

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

204 Loop *UseLoop = LI->getLoopFor(I->getParent());
205 const SCEV *Start = SE->getIntegerSCEV(0, ISE->getType());
206 const SCEV *Stride = Start;
207
208 if (!getSCEVStartAndStride(ISE, L, UseLoop, Start, Stride, SE, DT))
209 return false; // Non-reducible symbolic expression, bail out.
210
211 // Keep things simple. Don't touch loop-variant strides.
152
153 BasicBlock *LatchBlock = L->getLoopLatch();
154 if (!LatchBlock)
155 return false;
156
157 // Ok, the user is outside of the loop. If it is dominated by the latch
158 // block, use the post-inc value.
159 if (DT->dominates(LatchBlock, User->getParent()))

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

204 Loop *UseLoop = LI->getLoopFor(I->getParent());
205 const SCEV *Start = SE->getIntegerSCEV(0, ISE->getType());
206 const SCEV *Stride = Start;
207
208 if (!getSCEVStartAndStride(ISE, L, UseLoop, Start, Stride, SE, DT))
209 return false; // Non-reducible symbolic expression, bail out.
210
211 // Keep things simple. Don't touch loop-variant strides.
212 if (!Stride->isLoopInvariant(L) && L->contains(I->getParent()))
212 if (!Stride->isLoopInvariant(L) && L->contains(I))
213 return false;
214
215 SmallPtrSet<Instruction *, 4> UniqueUsers;
216 for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
217 UI != E; ++UI) {
218 Instruction *User = cast<Instruction>(*UI);
219 if (!UniqueUsers.insert(User))
220 continue;

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

228 // choices that depend on addressing mode use right, although we won't
229 // consider references ouside the loop in all cases.
230 // If User is already in Processed, we don't want to recurse into it again,
231 // but do want to record a second reference in the same instruction.
232 bool AddUserToIVUsers = false;
233 if (LI->getLoopFor(User->getParent()) != L) {
234 if (isa<PHINode>(User) || Processed.count(User) ||
235 !AddUsersIfInteresting(User)) {
213 return false;
214
215 SmallPtrSet<Instruction *, 4> UniqueUsers;
216 for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
217 UI != E; ++UI) {
218 Instruction *User = cast<Instruction>(*UI);
219 if (!UniqueUsers.insert(User))
220 continue;

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

228 // choices that depend on addressing mode use right, although we won't
229 // consider references ouside the loop in all cases.
230 // If User is already in Processed, we don't want to recurse into it again,
231 // but do want to record a second reference in the same instruction.
232 bool AddUserToIVUsers = false;
233 if (LI->getLoopFor(User->getParent()) != L) {
234 if (isa<PHINode>(User) || Processed.count(User) ||
235 !AddUsersIfInteresting(User)) {
236 DEBUG(errs() << "FOUND USER in other loop: " << *User << '\n'
236 DEBUG(dbgs() << "FOUND USER in other loop: " << *User << '\n'
237 << " OF SCEV: " << *ISE << '\n');
238 AddUserToIVUsers = true;
239 }
240 } else if (Processed.count(User) ||
241 !AddUsersIfInteresting(User)) {
237 << " OF SCEV: " << *ISE << '\n');
238 AddUserToIVUsers = true;
239 }
240 } else if (Processed.count(User) ||
241 !AddUsersIfInteresting(User)) {
242 DEBUG(errs() << "FOUND USER: " << *User << '\n'
242 DEBUG(dbgs() << "FOUND USER: " << *User << '\n'
243 << " OF SCEV: " << *ISE << '\n');
244 AddUserToIVUsers = true;
245 }
246
247 if (AddUserToIVUsers) {
248 IVUsersOfOneStride *StrideUses = IVUsesByStride[Stride];
249 if (!StrideUses) { // First occurrence of this stride?
250 StrideOrder.push_back(Stride);

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

257 // and decide what to do with it. If we are a use inside of the loop, use
258 // the value before incrementation, otherwise use it after incrementation.
259 if (IVUseShouldUsePostIncValue(User, I, L, LI, DT, this)) {
260 // The value used will be incremented by the stride more than we are
261 // expecting, so subtract this off.
262 const SCEV *NewStart = SE->getMinusSCEV(Start, Stride);
263 StrideUses->addUser(NewStart, User, I);
264 StrideUses->Users.back().setIsUseOfPostIncrementedValue(true);
243 << " OF SCEV: " << *ISE << '\n');
244 AddUserToIVUsers = true;
245 }
246
247 if (AddUserToIVUsers) {
248 IVUsersOfOneStride *StrideUses = IVUsesByStride[Stride];
249 if (!StrideUses) { // First occurrence of this stride?
250 StrideOrder.push_back(Stride);

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

257 // and decide what to do with it. If we are a use inside of the loop, use
258 // the value before incrementation, otherwise use it after incrementation.
259 if (IVUseShouldUsePostIncValue(User, I, L, LI, DT, this)) {
260 // The value used will be incremented by the stride more than we are
261 // expecting, so subtract this off.
262 const SCEV *NewStart = SE->getMinusSCEV(Start, Stride);
263 StrideUses->addUser(NewStart, User, I);
264 StrideUses->Users.back().setIsUseOfPostIncrementedValue(true);
265 DEBUG(errs() << " USING POSTINC SCEV, START=" << *NewStart<< "\n");
265 DEBUG(dbgs() << " USING POSTINC SCEV, START=" << *NewStart<< "\n");
266 } else {
267 StrideUses->addUser(Start, User, I);
268 }
269 }
270 }
271 return true;
272}
273

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

302 SE = &getAnalysis<ScalarEvolution>();
303
304 // Find all uses of induction variables in this loop, and categorize
305 // them by stride. Start by finding all of the PHI nodes in the header for
306 // this loop. If they are induction variables, inspect their uses.
307 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I)
308 AddUsersIfInteresting(I);
309
266 } else {
267 StrideUses->addUser(Start, User, I);
268 }
269 }
270 }
271 return true;
272}
273

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

302 SE = &getAnalysis<ScalarEvolution>();
303
304 // Find all uses of induction variables in this loop, and categorize
305 // them by stride. Start by finding all of the PHI nodes in the header for
306 // this loop. If they are induction variables, inspect their uses.
307 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I)
308 AddUsersIfInteresting(I);
309
310 Processed.clear();
311 return false;
312}
313
314/// getReplacementExpr - Return a SCEV expression which computes the
315/// value of the OperandValToReplace of the given IVStrideUse.
316const SCEV *IVUsers::getReplacementExpr(const IVStrideUse &U) const {
317 // Start with zero.
318 const SCEV *RetVal = SE->getIntegerSCEV(0, U.getParent()->Stride->getType());
319 // Create the basic add recurrence.
320 RetVal = SE->getAddRecExpr(RetVal, U.getParent()->Stride, L);
321 // Add the offset in a separate step, because it may be loop-variant.
322 RetVal = SE->getAddExpr(RetVal, U.getOffset());
323 // For uses of post-incremented values, add an extra stride to compute
324 // the actual replacement value.
325 if (U.isUseOfPostIncrementedValue())
326 RetVal = SE->getAddExpr(RetVal, U.getParent()->Stride);
327 // Evaluate the expression out of the loop, if possible.
310 return false;
311}
312
313/// getReplacementExpr - Return a SCEV expression which computes the
314/// value of the OperandValToReplace of the given IVStrideUse.
315const SCEV *IVUsers::getReplacementExpr(const IVStrideUse &U) const {
316 // Start with zero.
317 const SCEV *RetVal = SE->getIntegerSCEV(0, U.getParent()->Stride->getType());
318 // Create the basic add recurrence.
319 RetVal = SE->getAddRecExpr(RetVal, U.getParent()->Stride, L);
320 // Add the offset in a separate step, because it may be loop-variant.
321 RetVal = SE->getAddExpr(RetVal, U.getOffset());
322 // For uses of post-incremented values, add an extra stride to compute
323 // the actual replacement value.
324 if (U.isUseOfPostIncrementedValue())
325 RetVal = SE->getAddExpr(RetVal, U.getParent()->Stride);
326 // Evaluate the expression out of the loop, if possible.
328 if (!L->contains(U.getUser()->getParent())) {
327 if (!L->contains(U.getUser())) {
329 const SCEV *ExitVal = SE->getSCEVAtScope(RetVal, L->getParentLoop());
330 if (ExitVal->isLoopInvariant(L))
331 RetVal = ExitVal;
332 }
333 return RetVal;
334}
335
336void IVUsers::print(raw_ostream &OS, const Module *M) const {

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

359 OS << " in ";
360 UI->getUser()->print(OS);
361 OS << '\n';
362 }
363 }
364}
365
366void IVUsers::dump() const {
328 const SCEV *ExitVal = SE->getSCEVAtScope(RetVal, L->getParentLoop());
329 if (ExitVal->isLoopInvariant(L))
330 RetVal = ExitVal;
331 }
332 return RetVal;
333}
334
335void IVUsers::print(raw_ostream &OS, const Module *M) const {

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

358 OS << " in ";
359 UI->getUser()->print(OS);
360 OS << '\n';
361 }
362 }
363}
364
365void IVUsers::dump() const {
367 print(errs());
366 print(dbgs());
368}
369
370void IVUsers::releaseMemory() {
371 IVUsesByStride.clear();
372 StrideOrder.clear();
367}
368
369void IVUsers::releaseMemory() {
370 IVUsesByStride.clear();
371 StrideOrder.clear();
372 Processed.clear();
373 IVUses.clear();
374}
375
376void IVStrideUse::deleted() {
377 // Remove this user from the list.
378 Parent->Users.erase(this);
379 // this now dangles!
380}
373 IVUses.clear();
374}
375
376void IVStrideUse::deleted() {
377 // Remove this user from the list.
378 Parent->Users.erase(this);
379 // this now dangles!
380}