IVUsers.cpp revision 86eeeaf87747912a6c2404c383a416b07233c748
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/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; 32static RegisterPass<IVUsers> 33X("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. 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 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); 52 // Otherwise recurse to see if the start value is interesting. 53 return isInteresting(AR->getStart(), I, L); 54 } 55 56 // An add is interesting if any of its operands is. 57 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 58 for (SCEVAddExpr::op_iterator OI = Add->op_begin(), OE = Add->op_end(); 59 OI != OE; ++OI) 60 if (isInteresting(*OI, I, L)) 61 return true; 62 return false; 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 71/// return true. Otherwise, return false. 72bool IVUsers::AddUsersIfInteresting(Instruction *I) { 73 if (!SE->isSCEVable(I->getType())) 74 return false; // Void and FP expressions cannot be reduced. 75 76 // LSR is not APInt clean, do not touch integers bigger than 64-bits. 77 if (SE->getTypeSizeInBits(I->getType()) > 64) 78 return false; 79 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 if (isa<SCEVCouldNotCompute>(ISE)) return false; 86 87 // If we've come to an uninteresting expression, stop the traversal and 88 // call this a user. 89 if (!isInteresting(ISE, I, L)) 90 return false; 91 92 SmallPtrSet<Instruction *, 4> UniqueUsers; 93 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 94 UI != E; ++UI) { 95 Instruction *User = cast<Instruction>(*UI); 96 if (!UniqueUsers.insert(User)) 97 continue; 98 99 // Do not infinitely recurse on PHI nodes. 100 if (isa<PHINode>(User) && Processed.count(User)) 101 continue; 102 103 // Descend recursively, but not into PHI nodes outside the current loop. 104 // It's important to see the entire expression outside the loop to get 105 // choices that depend on addressing mode use right, although we won't 106 // consider references outside the loop in all cases. 107 // If User is already in Processed, we don't want to recurse into it again, 108 // but do want to record a second reference in the same instruction. 109 bool AddUserToIVUsers = false; 110 if (LI->getLoopFor(User->getParent()) != L) { 111 if (isa<PHINode>(User) || Processed.count(User) || 112 !AddUsersIfInteresting(User)) { 113 DEBUG(dbgs() << "FOUND USER in other loop: " << *User << '\n' 114 << " OF SCEV: " << *ISE << '\n'); 115 AddUserToIVUsers = true; 116 } 117 } else if (Processed.count(User) || 118 !AddUsersIfInteresting(User)) { 119 DEBUG(dbgs() << "FOUND USER: " << *User << '\n' 120 << " OF SCEV: " << *ISE << '\n'); 121 AddUserToIVUsers = true; 122 } 123 124 if (AddUserToIVUsers) { 125 // Okay, we found a user that we cannot reduce. 126 IVUses.push_back(new IVStrideUse(this, ISE, User, I)); 127 IVStrideUse &NewUse = IVUses.back(); 128 // Transform the expression into a normalized form. 129 NewUse.Expr = 130 TransformForPostIncUse(NormalizeAutodetect, NewUse.Expr, 131 User, I, 132 NewUse.PostIncLoops, 133 *SE, *DT); 134 DEBUG(dbgs() << " NORMALIZED TO: " << *NewUse.Expr << '\n'); 135 } 136 } 137 return true; 138} 139 140IVStrideUse &IVUsers::AddUser(const SCEV *Expr, 141 Instruction *User, Value *Operand) { 142 IVUses.push_back(new IVStrideUse(this, Expr, User, Operand)); 143 return IVUses.back(); 144} 145 146IVUsers::IVUsers() 147 : LoopPass(&ID) { 148} 149 150void IVUsers::getAnalysisUsage(AnalysisUsage &AU) const { 151 AU.addRequired<LoopInfo>(); 152 AU.addRequired<DominatorTree>(); 153 AU.addRequired<ScalarEvolution>(); 154 AU.setPreservesAll(); 155} 156 157bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) { 158 159 L = l; 160 LI = &getAnalysis<LoopInfo>(); 161 DT = &getAnalysis<DominatorTree>(); 162 SE = &getAnalysis<ScalarEvolution>(); 163 164 // Find all uses of induction variables in this loop, and categorize 165 // them by stride. Start by finding all of the PHI nodes in the header for 166 // this loop. If they are induction variables, inspect their uses. 167 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) 168 AddUsersIfInteresting(I); 169 170 return false; 171} 172 173/// getReplacementExpr - Return a SCEV expression which computes the 174/// value of the OperandValToReplace of the given IVStrideUse. 175const SCEV *IVUsers::getReplacementExpr(const IVStrideUse &U) const { 176 PostIncLoopSet &Loops = const_cast<PostIncLoopSet &>(U.PostIncLoops); 177 return TransformForPostIncUse(Denormalize, U.getExpr(), 178 U.getUser(), U.getOperandValToReplace(), 179 Loops, *SE, *DT); 180} 181 182void IVUsers::print(raw_ostream &OS, const Module *M) const { 183 OS << "IV Users for loop "; 184 WriteAsOperand(OS, L->getHeader(), false); 185 if (SE->hasLoopInvariantBackedgeTakenCount(L)) { 186 OS << " with backedge-taken count " 187 << *SE->getBackedgeTakenCount(L); 188 } 189 OS << ":\n"; 190 191 // Use a default AssemblyAnnotationWriter to suppress the default info 192 // comments, which aren't relevant here. 193 AssemblyAnnotationWriter Annotator; 194 for (ilist<IVStrideUse>::const_iterator UI = IVUses.begin(), 195 E = IVUses.end(); UI != E; ++UI) { 196 OS << " "; 197 WriteAsOperand(OS, UI->getOperandValToReplace(), false); 198 OS << " = " 199 << *getReplacementExpr(*UI); 200 for (PostIncLoopSet::const_iterator 201 I = UI->PostIncLoops.begin(), 202 E = UI->PostIncLoops.end(); I != E; ++I) { 203 OS << " (post-inc with loop "; 204 WriteAsOperand(OS, (*I)->getHeader(), false); 205 OS << ")"; 206 } 207 OS << " in "; 208 UI->getUser()->print(OS, &Annotator); 209 OS << '\n'; 210 } 211} 212 213void IVUsers::dump() const { 214 print(dbgs()); 215} 216 217void IVUsers::releaseMemory() { 218 Processed.clear(); 219 IVUses.clear(); 220} 221 222static const SCEVAddRecExpr *findAddRecForLoop(const SCEV *S, const Loop *L) { 223 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 224 if (AR->getLoop() == L) 225 return AR; 226 return findAddRecForLoop(AR->getStart(), L); 227 } 228 229 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 230 for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); 231 I != E; ++I) 232 if (const SCEVAddRecExpr *AR = findAddRecForLoop(*I, L)) 233 return AR; 234 return 0; 235 } 236 237 return 0; 238} 239 240const SCEV *IVStrideUse::getStride(const Loop *L) const { 241 if (const SCEVAddRecExpr *AR = findAddRecForLoop(getExpr(), L)) 242 return AR->getStepRecurrence(*Parent->SE); 243 return 0; 244} 245 246void IVStrideUse::transformToPostInc(const Loop *L) { 247 PostIncLoopSet Loops; 248 Loops.insert(L); 249 Expr = TransformForPostIncUse(Normalize, Expr, 250 getUser(), getOperandValToReplace(), 251 Loops, *Parent->SE, *Parent->DT); 252 PostIncLoops.insert(L); 253} 254 255void IVStrideUse::deleted() { 256 // Remove this user from the list. 257 Parent->IVUses.erase(this); 258 // this now dangles! 259} 260