1193323Sed//===- IVUsers.cpp - Induction Variable Users -------------------*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements bookkeeping for "interesting" users of expressions 11193323Sed// computed from induction variables. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15193323Sed#define DEBUG_TYPE "iv-users" 16193323Sed#include "llvm/Analysis/IVUsers.h" 17249423Sdim#include "llvm/ADT/STLExtras.h" 18193323Sed#include "llvm/Analysis/Dominators.h" 19193323Sed#include "llvm/Analysis/LoopPass.h" 20193323Sed#include "llvm/Analysis/ScalarEvolutionExpressions.h" 21239462Sdim#include "llvm/Analysis/ValueTracking.h" 22218893Sdim#include "llvm/Assembly/Writer.h" 23249423Sdim#include "llvm/IR/Constants.h" 24249423Sdim#include "llvm/IR/DataLayout.h" 25249423Sdim#include "llvm/IR/DerivedTypes.h" 26249423Sdim#include "llvm/IR/Instructions.h" 27249423Sdim#include "llvm/IR/Type.h" 28193323Sed#include "llvm/Support/Debug.h" 29193323Sed#include "llvm/Support/raw_ostream.h" 30193323Sed#include <algorithm> 31193323Sedusing namespace llvm; 32193323Sed 33193323Sedchar IVUsers::ID = 0; 34218893SdimINITIALIZE_PASS_BEGIN(IVUsers, "iv-users", 35218893Sdim "Induction Variable Users", false, true) 36218893SdimINITIALIZE_PASS_DEPENDENCY(LoopInfo) 37218893SdimINITIALIZE_PASS_DEPENDENCY(DominatorTree) 38218893SdimINITIALIZE_PASS_DEPENDENCY(ScalarEvolution) 39218893SdimINITIALIZE_PASS_END(IVUsers, "iv-users", 40218893Sdim "Induction Variable Users", false, true) 41193323Sed 42193323SedPass *llvm::createIVUsersPass() { 43193323Sed return new IVUsers(); 44193323Sed} 45193323Sed 46207618Srdivacky/// isInteresting - Test whether the given expression is "interesting" when 47207618Srdivacky/// used by the given expression, within the context of analyzing the 48207618Srdivacky/// given loop. 49212904Sdimstatic bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L, 50224145Sdim ScalarEvolution *SE, LoopInfo *LI) { 51207618Srdivacky // An addrec is interesting if it's affine or if it has an interesting start. 52207618Srdivacky if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 53224145Sdim // Keep things simple. Don't touch loop-variant strides unless they're 54224145Sdim // only used outside the loop and we can simplify them. 55207618Srdivacky if (AR->getLoop() == L) 56224145Sdim return AR->isAffine() || 57224145Sdim (!L->contains(I) && 58224145Sdim SE->getSCEVAtScope(AR, LI->getLoopFor(I->getParent())) != AR); 59212904Sdim // Otherwise recurse to see if the start value is interesting, and that 60212904Sdim // the step value is not interesting, since we don't yet know how to 61212904Sdim // do effective SCEV expansions for addrecs with interesting steps. 62224145Sdim return isInteresting(AR->getStart(), I, L, SE, LI) && 63224145Sdim !isInteresting(AR->getStepRecurrence(*SE), I, L, SE, LI); 64193323Sed } 65193323Sed 66212904Sdim // An add is interesting if exactly one of its operands is interesting. 67207618Srdivacky if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 68212904Sdim bool AnyInterestingYet = false; 69207618Srdivacky for (SCEVAddExpr::op_iterator OI = Add->op_begin(), OE = Add->op_end(); 70207618Srdivacky OI != OE; ++OI) 71224145Sdim if (isInteresting(*OI, I, L, SE, LI)) { 72212904Sdim if (AnyInterestingYet) 73212904Sdim return false; 74212904Sdim AnyInterestingYet = true; 75212904Sdim } 76212904Sdim return AnyInterestingYet; 77193323Sed } 78193323Sed 79207618Srdivacky // Nothing else is interesting here. 80207618Srdivacky return false; 81193323Sed} 82193323Sed 83234353Sdim/// Return true if all loop headers that dominate this block are in simplified 84234353Sdim/// form. 85234353Sdimstatic bool isSimplifiedLoopNest(BasicBlock *BB, const DominatorTree *DT, 86234353Sdim const LoopInfo *LI, 87234353Sdim SmallPtrSet<Loop*,16> &SimpleLoopNests) { 88234353Sdim Loop *NearestLoop = 0; 89234353Sdim for (DomTreeNode *Rung = DT->getNode(BB); 90234353Sdim Rung; Rung = Rung->getIDom()) { 91234353Sdim BasicBlock *DomBB = Rung->getBlock(); 92234353Sdim Loop *DomLoop = LI->getLoopFor(DomBB); 93234353Sdim if (DomLoop && DomLoop->getHeader() == DomBB) { 94234353Sdim // If the domtree walk reaches a loop with no preheader, return false. 95234353Sdim if (!DomLoop->isLoopSimplifyForm()) 96234353Sdim return false; 97234353Sdim // If we have already checked this loop nest, stop checking. 98234353Sdim if (SimpleLoopNests.count(DomLoop)) 99234353Sdim break; 100234353Sdim // If we have not already checked this loop nest, remember the loop 101234353Sdim // header nearest to BB. The nearest loop may not contain BB. 102234353Sdim if (!NearestLoop) 103234353Sdim NearestLoop = DomLoop; 104234353Sdim } 105234353Sdim } 106234353Sdim if (NearestLoop) 107234353Sdim SimpleLoopNests.insert(NearestLoop); 108234353Sdim return true; 109234353Sdim} 110234353Sdim 111234353Sdim/// AddUsersImpl - Inspect the specified instruction. If it is a 112193323Sed/// reducible SCEV, recursively add its users to the IVUsesByStride set and 113193323Sed/// return true. Otherwise, return false. 114234353Sdimbool IVUsers::AddUsersImpl(Instruction *I, 115234353Sdim SmallPtrSet<Loop*,16> &SimpleLoopNests) { 116234353Sdim // Add this IV user to the Processed set before returning false to ensure that 117234353Sdim // all IV users are members of the set. See IVUsers::isIVUserOrOperand. 118234353Sdim if (!Processed.insert(I)) 119234353Sdim return true; // Instruction already handled. 120234353Sdim 121193323Sed if (!SE->isSCEVable(I->getType())) 122193323Sed return false; // Void and FP expressions cannot be reduced. 123193323Sed 124239462Sdim // IVUsers is used by LSR which assumes that all SCEV expressions are safe to 125239462Sdim // pass to SCEVExpander. Expressions are not safe to expand if they represent 126239462Sdim // operations that are not safe to speculate, namely integer division. 127239462Sdim if (!isa<PHINode>(I) && !isSafeToSpeculativelyExecute(I, TD)) 128239462Sdim return false; 129239462Sdim 130193323Sed // LSR is not APInt clean, do not touch integers bigger than 64-bits. 131221345Sdim // Also avoid creating IVs of non-native types. For example, we don't want a 132221345Sdim // 64-bit IV in 32-bit code just because the loop has one 64-bit cast. 133221345Sdim uint64_t Width = SE->getTypeSizeInBits(I->getType()); 134221345Sdim if (Width > 64 || (TD && !TD->isLegalInteger(Width))) 135193323Sed return false; 136193323Sed 137193323Sed // Get the symbolic expression for this instruction. 138198090Srdivacky const SCEV *ISE = SE->getSCEV(I); 139193323Sed 140207618Srdivacky // If we've come to an uninteresting expression, stop the traversal and 141207618Srdivacky // call this a user. 142224145Sdim if (!isInteresting(ISE, I, L, SE, LI)) 143199511Srdivacky return false; 144199511Srdivacky 145193323Sed SmallPtrSet<Instruction *, 4> UniqueUsers; 146193323Sed for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 147193323Sed UI != E; ++UI) { 148193323Sed Instruction *User = cast<Instruction>(*UI); 149193323Sed if (!UniqueUsers.insert(User)) 150193323Sed continue; 151193323Sed 152193323Sed // Do not infinitely recurse on PHI nodes. 153193323Sed if (isa<PHINode>(User) && Processed.count(User)) 154193323Sed continue; 155193323Sed 156234353Sdim // Only consider IVUsers that are dominated by simplified loop 157234353Sdim // headers. Otherwise, SCEVExpander will crash. 158234353Sdim BasicBlock *UseBB = User->getParent(); 159234353Sdim // A phi's use is live out of its predecessor block. 160234353Sdim if (PHINode *PHI = dyn_cast<PHINode>(User)) { 161234353Sdim unsigned OperandNo = UI.getOperandNo(); 162234353Sdim unsigned ValNo = PHINode::getIncomingValueNumForOperand(OperandNo); 163234353Sdim UseBB = PHI->getIncomingBlock(ValNo); 164234353Sdim } 165234353Sdim if (!isSimplifiedLoopNest(UseBB, DT, LI, SimpleLoopNests)) 166234353Sdim return false; 167234353Sdim 168193323Sed // Descend recursively, but not into PHI nodes outside the current loop. 169193323Sed // It's important to see the entire expression outside the loop to get 170193323Sed // choices that depend on addressing mode use right, although we won't 171204642Srdivacky // consider references outside the loop in all cases. 172193323Sed // If User is already in Processed, we don't want to recurse into it again, 173193323Sed // but do want to record a second reference in the same instruction. 174193323Sed bool AddUserToIVUsers = false; 175193323Sed if (LI->getLoopFor(User->getParent()) != L) { 176193323Sed if (isa<PHINode>(User) || Processed.count(User) || 177234353Sdim !AddUsersImpl(User, SimpleLoopNests)) { 178201360Srdivacky DEBUG(dbgs() << "FOUND USER in other loop: " << *User << '\n' 179198090Srdivacky << " OF SCEV: " << *ISE << '\n'); 180193323Sed AddUserToIVUsers = true; 181193323Sed } 182234353Sdim } else if (Processed.count(User) || !AddUsersImpl(User, SimpleLoopNests)) { 183201360Srdivacky DEBUG(dbgs() << "FOUND USER: " << *User << '\n' 184198090Srdivacky << " OF SCEV: " << *ISE << '\n'); 185193323Sed AddUserToIVUsers = true; 186193323Sed } 187193323Sed 188193323Sed if (AddUserToIVUsers) { 189207618Srdivacky // Okay, we found a user that we cannot reduce. 190266715Sdim IVStrideUse &NewUse = AddUser(User, I); 191223017Sdim // Autodetect the post-inc loop set, populating NewUse.PostIncLoops. 192223017Sdim // The regular return value here is discarded; instead of recording 193223017Sdim // it, we just recompute it when we need it. 194266715Sdim const SCEV *OriginalISE = ISE; 195207618Srdivacky ISE = TransformForPostIncUse(NormalizeAutodetect, 196207618Srdivacky ISE, User, I, 197207618Srdivacky NewUse.PostIncLoops, 198207618Srdivacky *SE, *DT); 199266715Sdim 200266715Sdim // PostIncNormalization effectively simplifies the expression under 201266715Sdim // pre-increment assumptions. Those assumptions (no wrapping) might not 202266715Sdim // hold for the post-inc value. Catch such cases by making sure the 203266715Sdim // transformation is invertible. 204266715Sdim if (OriginalISE != ISE) { 205266715Sdim const SCEV *DenormalizedISE = 206266715Sdim TransformForPostIncUse(Denormalize, ISE, User, I, 207266715Sdim NewUse.PostIncLoops, *SE, *DT); 208266715Sdim 209266715Sdim // If we normalized the expression, but denormalization doesn't give the 210266715Sdim // original one, discard this user. 211266715Sdim if (OriginalISE != DenormalizedISE) { 212266715Sdim DEBUG(dbgs() << " DISCARDING (NORMALIZATION ISN'T INVERTIBLE): " 213266715Sdim << *ISE << '\n'); 214266715Sdim IVUses.pop_back(); 215266715Sdim return false; 216266715Sdim } 217266715Sdim } 218226633Sdim DEBUG(if (SE->getSCEV(I) != ISE) 219226633Sdim dbgs() << " NORMALIZED TO: " << *ISE << '\n'); 220193323Sed } 221193323Sed } 222193323Sed return true; 223193323Sed} 224193323Sed 225234353Sdimbool IVUsers::AddUsersIfInteresting(Instruction *I) { 226234353Sdim // SCEVExpander can only handle users that are dominated by simplified loop 227234353Sdim // entries. Keep track of all loops that are only dominated by other simple 228234353Sdim // loops so we don't traverse the domtree for each user. 229234353Sdim SmallPtrSet<Loop*,16> SimpleLoopNests; 230234353Sdim 231234353Sdim return AddUsersImpl(I, SimpleLoopNests); 232234353Sdim} 233234353Sdim 234224145SdimIVStrideUse &IVUsers::AddUser(Instruction *User, Value *Operand) { 235224145Sdim IVUses.push_back(new IVStrideUse(this, User, Operand)); 236203954Srdivacky return IVUses.back(); 237199481Srdivacky} 238199481Srdivacky 239193323SedIVUsers::IVUsers() 240218893Sdim : LoopPass(ID) { 241218893Sdim initializeIVUsersPass(*PassRegistry::getPassRegistry()); 242193323Sed} 243193323Sed 244193323Sedvoid IVUsers::getAnalysisUsage(AnalysisUsage &AU) const { 245193323Sed AU.addRequired<LoopInfo>(); 246193323Sed AU.addRequired<DominatorTree>(); 247193323Sed AU.addRequired<ScalarEvolution>(); 248193323Sed AU.setPreservesAll(); 249193323Sed} 250193323Sed 251193323Sedbool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) { 252193323Sed 253193323Sed L = l; 254193323Sed LI = &getAnalysis<LoopInfo>(); 255193323Sed DT = &getAnalysis<DominatorTree>(); 256193323Sed SE = &getAnalysis<ScalarEvolution>(); 257243830Sdim TD = getAnalysisIfAvailable<DataLayout>(); 258193323Sed 259193323Sed // Find all uses of induction variables in this loop, and categorize 260193323Sed // them by stride. Start by finding all of the PHI nodes in the header for 261193323Sed // this loop. If they are induction variables, inspect their uses. 262193323Sed for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) 263224145Sdim (void)AddUsersIfInteresting(I); 264193323Sed 265193323Sed return false; 266193323Sed} 267193323Sed 268193323Sedvoid IVUsers::print(raw_ostream &OS, const Module *M) const { 269193323Sed OS << "IV Users for loop "; 270193323Sed WriteAsOperand(OS, L->getHeader(), false); 271193323Sed if (SE->hasLoopInvariantBackedgeTakenCount(L)) { 272193323Sed OS << " with backedge-taken count " 273193323Sed << *SE->getBackedgeTakenCount(L); 274193323Sed } 275193323Sed OS << ":\n"; 276193323Sed 277203954Srdivacky for (ilist<IVStrideUse>::const_iterator UI = IVUses.begin(), 278203954Srdivacky E = IVUses.end(); UI != E; ++UI) { 279203954Srdivacky OS << " "; 280203954Srdivacky WriteAsOperand(OS, UI->getOperandValToReplace(), false); 281207618Srdivacky OS << " = " << *getReplacementExpr(*UI); 282207618Srdivacky for (PostIncLoopSet::const_iterator 283207618Srdivacky I = UI->PostIncLoops.begin(), 284207618Srdivacky E = UI->PostIncLoops.end(); I != E; ++I) { 285207618Srdivacky OS << " (post-inc with loop "; 286207618Srdivacky WriteAsOperand(OS, (*I)->getHeader(), false); 287207618Srdivacky OS << ")"; 288207618Srdivacky } 289203954Srdivacky OS << " in "; 290212904Sdim UI->getUser()->print(OS); 291203954Srdivacky OS << '\n'; 292193323Sed } 293193323Sed} 294193323Sed 295243830Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 296193323Sedvoid IVUsers::dump() const { 297201360Srdivacky print(dbgs()); 298193323Sed} 299243830Sdim#endif 300193323Sed 301193323Sedvoid IVUsers::releaseMemory() { 302201360Srdivacky Processed.clear(); 303200581Srdivacky IVUses.clear(); 304193323Sed} 305193323Sed 306207618Srdivacky/// getReplacementExpr - Return a SCEV expression which computes the 307207618Srdivacky/// value of the OperandValToReplace. 308207618Srdivackyconst SCEV *IVUsers::getReplacementExpr(const IVStrideUse &IU) const { 309207618Srdivacky return SE->getSCEV(IU.getOperandValToReplace()); 310207618Srdivacky} 311207618Srdivacky 312207618Srdivacky/// getExpr - Return the expression for the use. 313207618Srdivackyconst SCEV *IVUsers::getExpr(const IVStrideUse &IU) const { 314207618Srdivacky return 315207618Srdivacky TransformForPostIncUse(Normalize, getReplacementExpr(IU), 316207618Srdivacky IU.getUser(), IU.getOperandValToReplace(), 317207618Srdivacky const_cast<PostIncLoopSet &>(IU.getPostIncLoops()), 318207618Srdivacky *SE, *DT); 319207618Srdivacky} 320207618Srdivacky 321207618Srdivackystatic const SCEVAddRecExpr *findAddRecForLoop(const SCEV *S, const Loop *L) { 322207618Srdivacky if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 323207618Srdivacky if (AR->getLoop() == L) 324207618Srdivacky return AR; 325207618Srdivacky return findAddRecForLoop(AR->getStart(), L); 326207618Srdivacky } 327207618Srdivacky 328207618Srdivacky if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 329207618Srdivacky for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); 330207618Srdivacky I != E; ++I) 331207618Srdivacky if (const SCEVAddRecExpr *AR = findAddRecForLoop(*I, L)) 332207618Srdivacky return AR; 333207618Srdivacky return 0; 334207618Srdivacky } 335207618Srdivacky 336207618Srdivacky return 0; 337207618Srdivacky} 338207618Srdivacky 339207618Srdivackyconst SCEV *IVUsers::getStride(const IVStrideUse &IU, const Loop *L) const { 340207618Srdivacky if (const SCEVAddRecExpr *AR = findAddRecForLoop(getExpr(IU), L)) 341207618Srdivacky return AR->getStepRecurrence(*SE); 342207618Srdivacky return 0; 343207618Srdivacky} 344207618Srdivacky 345207618Srdivackyvoid IVStrideUse::transformToPostInc(const Loop *L) { 346207618Srdivacky PostIncLoops.insert(L); 347207618Srdivacky} 348207618Srdivacky 349193323Sedvoid IVStrideUse::deleted() { 350193323Sed // Remove this user from the list. 351234353Sdim Parent->Processed.erase(this->getUser()); 352203954Srdivacky Parent->IVUses.erase(this); 353193323Sed // this now dangles! 354193323Sed} 355