contrib/llvm/lib/Analysis/IVUsers.cpp

   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 #include "llvm/Analysis/IVUsers.h"
  16 #include "llvm/ADT/STLExtras.h"
  17 #include "llvm/Analysis/AssumptionCache.h"
  18 #include "llvm/Analysis/CodeMetrics.h"
  19 #include "llvm/Analysis/LoopAnalysisManager.h"
  20 #include "llvm/Analysis/LoopPass.h"
  21 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  22 #include "llvm/Analysis/ValueTracking.h"
  23 #include "llvm/IR/Constants.h"
  24 #include "llvm/IR/DataLayout.h"
  25 #include "llvm/IR/DerivedTypes.h"
  26 #include "llvm/IR/Dominators.h"
  27 #include "llvm/IR/Instructions.h"
  28 #include "llvm/IR/Module.h"
  29 #include "llvm/IR/Type.h"
  30 #include "llvm/Support/Debug.h"
  31 #include "llvm/Support/raw_ostream.h"
  32 #include <algorithm>
  33 using namespace llvm;
  34
  35 #define DEBUG_TYPE "iv-users"
  36
  37 AnalysisKey IVUsersAnalysis::Key;
  38
  39 IVUsers IVUsersAnalysis::run(Loop &L, LoopAnalysisManager &AM,
  40                              LoopStandardAnalysisResults &AR) {
  41   return IVUsers(&L, &AR.AC, &AR.LI, &AR.DT, &AR.SE);
  42 }
  43
  44 char IVUsersWrapperPass::ID = 0;
  45 INITIALIZE_PASS_BEGIN(IVUsersWrapperPass, "iv-users",
  46                       "Induction Variable Users", false, true)
  47 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
  48 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
  49 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
  50 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
  51 INITIALIZE_PASS_END(IVUsersWrapperPass, "iv-users", "Induction Variable Users",
  52                     false, true)
  53
  54 Pass *llvm::createIVUsersPass() { return new IVUsersWrapperPass(); }
  55
  56 /// isInteresting - Test whether the given expression is "interesting" when
  57 /// used by the given expression, within the context of analyzing the
  58 /// given loop.
  59 static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L,
  60                           ScalarEvolution *SE, LoopInfo *LI) {
  61   // An addrec is interesting if it's affine or if it has an interesting start.
  62   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
  63     // Keep things simple. Don't touch loop-variant strides unless they're
  64     // only used outside the loop and we can simplify them.
  65     if (AR->getLoop() == L)
  66       return AR->isAffine() ||
  67              (!L->contains(I) &&
  68               SE->getSCEVAtScope(AR, LI->getLoopFor(I->getParent())) != AR);
  69     // Otherwise recurse to see if the start value is interesting, and that
  70     // the step value is not interesting, since we don't yet know how to
  71     // do effective SCEV expansions for addrecs with interesting steps.
  72     return isInteresting(AR->getStart(), I, L, SE, LI) &&
  73           !isInteresting(AR->getStepRecurrence(*SE), I, L, SE, LI);
  74   }
  75
  76   // An add is interesting if exactly one of its operands is interesting.
  77   if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
  78     bool AnyInterestingYet = false;
  79     for (SCEVAddExpr::op_iterator OI = Add->op_begin(), OE = Add->op_end();
  80          OI != OE; ++OI)
  81       if (isInteresting(*OI, I, L, SE, LI)) {
  82         if (AnyInterestingYet)
  83           return false;
  84         AnyInterestingYet = true;
  85       }
  86     return AnyInterestingYet;
  87   }
  88
  89   // Nothing else is interesting here.
  90   return false;
  91 }
  92
  93 /// Return true if all loop headers that dominate this block are in simplified
  94 /// form.
  95 static bool isSimplifiedLoopNest(BasicBlock *BB, const DominatorTree *DT,
  96                                  const LoopInfo *LI,
  97                                  SmallPtrSetImpl<Loop*> &SimpleLoopNests) {
  98   Loop *NearestLoop = nullptr;
  99   for (DomTreeNode *Rung = DT->getNode(BB);
 100        Rung; Rung = Rung->getIDom()) {
 101     BasicBlock *DomBB = Rung->getBlock();
 102     Loop *DomLoop = LI->getLoopFor(DomBB);
 103     if (DomLoop && DomLoop->getHeader() == DomBB) {
 104       // If the domtree walk reaches a loop with no preheader, return false.
 105       if (!DomLoop->isLoopSimplifyForm())
 106         return false;
 107       // If we have already checked this loop nest, stop checking.
 108       if (SimpleLoopNests.count(DomLoop))
 109         break;
 110       // If we have not already checked this loop nest, remember the loop
 111       // header nearest to BB. The nearest loop may not contain BB.
 112       if (!NearestLoop)
 113         NearestLoop = DomLoop;
 114     }
 115   }
 116   if (NearestLoop)
 117     SimpleLoopNests.insert(NearestLoop);
 118   return true;
 119 }
 120
 121 /// AddUsersImpl - Inspect the specified instruction.  If it is a
 122 /// reducible SCEV, recursively add its users to the IVUsesByStride set and
 123 /// return true.  Otherwise, return false.
 124 bool IVUsers::AddUsersImpl(Instruction *I,
 125                            SmallPtrSetImpl<Loop*> &SimpleLoopNests) {
 126   const DataLayout &DL = I->getModule()->getDataLayout();
 127
 128   // Add this IV user to the Processed set before returning false to ensure that
 129   // all IV users are members of the set. See IVUsers::isIVUserOrOperand.
 130   if (!Processed.insert(I).second)
 131     return true;    // Instruction already handled.
 132
 133   if (!SE->isSCEVable(I->getType()))
 134     return false;   // Void and FP expressions cannot be reduced.
 135
 136   // IVUsers is used by LSR which assumes that all SCEV expressions are safe to
 137   // pass to SCEVExpander. Expressions are not safe to expand if they represent
 138   // operations that are not safe to speculate, namely integer division.
 139   if (!isa<PHINode>(I) && !isSafeToSpeculativelyExecute(I))
 140     return false;
 141
 142   // LSR is not APInt clean, do not touch integers bigger than 64-bits.
 143   // Also avoid creating IVs of non-native types. For example, we don't want a
 144   // 64-bit IV in 32-bit code just because the loop has one 64-bit cast.
 145   uint64_t Width = SE->getTypeSizeInBits(I->getType());
 146   if (Width > 64 || !DL.isLegalInteger(Width))
 147     return false;
 148
 149   // Don't attempt to promote ephemeral values to indvars. They will be removed
 150   // later anyway.
 151   if (EphValues.count(I))
 152     return false;
 153
 154   // Get the symbolic expression for this instruction.
 155   const SCEV *ISE = SE->getSCEV(I);
 156
 157   // If we've come to an uninteresting expression, stop the traversal and
 158   // call this a user.
 159   if (!isInteresting(ISE, I, L, SE, LI))
 160     return false;
 161
 162   SmallPtrSet<Instruction *, 4> UniqueUsers;
 163   for (Use &U : I->uses()) {
 164     Instruction *User = cast<Instruction>(U.getUser());
 165     if (!UniqueUsers.insert(User).second)
 166       continue;
 167
 168     // Do not infinitely recurse on PHI nodes.
 169     if (isa<PHINode>(User) && Processed.count(User))
 170       continue;
 171
 172     // Only consider IVUsers that are dominated by simplified loop
 173     // headers. Otherwise, SCEVExpander will crash.
 174     BasicBlock *UseBB = User->getParent();
 175     // A phi's use is live out of its predecessor block.
 176     if (PHINode *PHI = dyn_cast<PHINode>(User)) {
 177       unsigned OperandNo = U.getOperandNo();
 178       unsigned ValNo = PHINode::getIncomingValueNumForOperand(OperandNo);
 179       UseBB = PHI->getIncomingBlock(ValNo);
 180     }
 181     if (!isSimplifiedLoopNest(UseBB, DT, LI, SimpleLoopNests))
 182       return false;
 183
 184     // Descend recursively, but not into PHI nodes outside the current loop.
 185     // It's important to see the entire expression outside the loop to get
 186     // choices that depend on addressing mode use right, although we won't
 187     // consider references outside the loop in all cases.
 188     // If User is already in Processed, we don't want to recurse into it again,
 189     // but do want to record a second reference in the same instruction.
 190     bool AddUserToIVUsers = false;
 191     if (LI->getLoopFor(User->getParent()) != L) {
 192       if (isa<PHINode>(User) || Processed.count(User) ||
 193           !AddUsersImpl(User, SimpleLoopNests)) {
 194         DEBUG(dbgs() << "FOUND USER in other loop: " << *User << '\n'
 195                      << "   OF SCEV: " << *ISE << '\n');
 196         AddUserToIVUsers = true;
 197       }
 198     } else if (Processed.count(User) || !AddUsersImpl(User, SimpleLoopNests)) {
 199       DEBUG(dbgs() << "FOUND USER: " << *User << '\n'
 200                    << "   OF SCEV: " << *ISE << '\n');
 201       AddUserToIVUsers = true;
 202     }
 203
 204     if (AddUserToIVUsers) {
 205       // Okay, we found a user that we cannot reduce.
 206       IVStrideUse &NewUse = AddUser(User, I);
 207       // Autodetect the post-inc loop set, populating NewUse.PostIncLoops.
 208       // The regular return value here is discarded; instead of recording
 209       // it, we just recompute it when we need it.
 210       const SCEV *OriginalISE = ISE;
 211       ISE = TransformForPostIncUse(NormalizeAutodetect,
 212                                    ISE, User, I,
 213                                    NewUse.PostIncLoops,
 214                                    *SE, *DT);
 215
 216       // PostIncNormalization effectively simplifies the expression under
 217       // pre-increment assumptions. Those assumptions (no wrapping) might not
 218       // hold for the post-inc value. Catch such cases by making sure the
 219       // transformation is invertible.
 220       if (OriginalISE != ISE) {
 221         const SCEV *DenormalizedISE =
 222           TransformForPostIncUse(Denormalize, ISE, User, I,
 223               NewUse.PostIncLoops, *SE, *DT);
 224
 225         // If we normalized the expression, but denormalization doesn't give the
 226         // original one, discard this user.
 227         if (OriginalISE != DenormalizedISE) {
 228           DEBUG(dbgs() << "   DISCARDING (NORMALIZATION ISN'T INVERTIBLE): "
 229                        << *ISE << '\n');
 230           IVUses.pop_back();
 231           return false;
 232         }
 233       }
 234       DEBUG(if (SE->getSCEV(I) != ISE)
 235               dbgs() << "   NORMALIZED TO: " << *ISE << '\n');
 236     }
 237   }
 238   return true;
 239 }
 240
 241 bool IVUsers::AddUsersIfInteresting(Instruction *I) {
 242   // SCEVExpander can only handle users that are dominated by simplified loop
 243   // entries. Keep track of all loops that are only dominated by other simple
 244   // loops so we don't traverse the domtree for each user.
 245   SmallPtrSet<Loop*,16> SimpleLoopNests;
 246
 247   return AddUsersImpl(I, SimpleLoopNests);
 248 }
 249
 250 IVStrideUse &IVUsers::AddUser(Instruction *User, Value *Operand) {
 251   IVUses.push_back(new IVStrideUse(this, User, Operand));
 252   return IVUses.back();
 253 }
 254
 255 IVUsers::IVUsers(Loop *L, AssumptionCache *AC, LoopInfo *LI, DominatorTree *DT,
 256                  ScalarEvolution *SE)
 257     : L(L), AC(AC), LI(LI), DT(DT), SE(SE), IVUses() {
 258   // Collect ephemeral values so that AddUsersIfInteresting skips them.
 259   EphValues.clear();
 260   CodeMetrics::collectEphemeralValues(L, AC, EphValues);
 261
 262   // Find all uses of induction variables in this loop, and categorize
 263   // them by stride.  Start by finding all of the PHI nodes in the header for
 264   // this loop.  If they are induction variables, inspect their uses.
 265   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I)
 266     (void)AddUsersIfInteresting(&*I);
 267 }
 268
 269 void IVUsers::print(raw_ostream &OS, const Module *M) const {
 270   OS << "IV Users for loop ";
 271   L->getHeader()->printAsOperand(OS, false);
 272   if (SE->hasLoopInvariantBackedgeTakenCount(L)) {
 273     OS << " with backedge-taken count " << *SE->getBackedgeTakenCount(L);
 274   }
 275   OS << ":\n";
 276
 277   for (const IVStrideUse &IVUse : IVUses) {
 278     OS << "  ";
 279     IVUse.getOperandValToReplace()->printAsOperand(OS, false);
 280     OS << " = " << *getReplacementExpr(IVUse);
 281     for (auto PostIncLoop : IVUse.PostIncLoops) {
 282       OS << " (post-inc with loop ";
 283       PostIncLoop->getHeader()->printAsOperand(OS, false);
 284       OS << ")";
 285     }
 286     OS << " in  ";
 287     if (IVUse.getUser())
 288       IVUse.getUser()->print(OS);
 289     else
 290       OS << "Printing <null> User";
 291     OS << '\n';
 292   }
 293 }
 294
 295 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 296 LLVM_DUMP_METHOD void IVUsers::dump() const { print(dbgs()); }
 297 #endif
 298
 299 void IVUsers::releaseMemory() {
 300   Processed.clear();
 301   IVUses.clear();
 302 }
 303
 304 IVUsersWrapperPass::IVUsersWrapperPass() : LoopPass(ID) {
 305   initializeIVUsersWrapperPassPass(*PassRegistry::getPassRegistry());
 306 }
 307
 308 void IVUsersWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
 309   AU.addRequired<AssumptionCacheTracker>();
 310   AU.addRequired<LoopInfoWrapperPass>();
 311   AU.addRequired<DominatorTreeWrapperPass>();
 312   AU.addRequired<ScalarEvolutionWrapperPass>();
 313   AU.setPreservesAll();
 314 }
 315
 316 bool IVUsersWrapperPass::runOnLoop(Loop *L, LPPassManager &LPM) {
 317   auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
 318       *L->getHeader()->getParent());
 319   auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 320   auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 321   auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 322
 323   IU.reset(new IVUsers(L, AC, LI, DT, SE));
 324   return false;
 325 }
 326
 327 void IVUsersWrapperPass::print(raw_ostream &OS, const Module *M) const {
 328   IU->print(OS, M);
 329 }
 330
 331 void IVUsersWrapperPass::releaseMemory() { IU->releaseMemory(); }
 332
 333 /// getReplacementExpr - Return a SCEV expression which computes the
 334 /// value of the OperandValToReplace.
 335 const SCEV *IVUsers::getReplacementExpr(const IVStrideUse &IU) const {
 336   return SE->getSCEV(IU.getOperandValToReplace());
 337 }
 338
 339 /// getExpr - Return the expression for the use.
 340 const SCEV *IVUsers::getExpr(const IVStrideUse &IU) const {
 341   return
 342     TransformForPostIncUse(Normalize, getReplacementExpr(IU),
 343                            IU.getUser(), IU.getOperandValToReplace(),
 344                            const_cast<PostIncLoopSet &>(IU.getPostIncLoops()),
 345                            *SE, *DT);
 346 }
 347
 348 static const SCEVAddRecExpr *findAddRecForLoop(const SCEV *S, const Loop *L) {
 349   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
 350     if (AR->getLoop() == L)
 351       return AR;
 352     return findAddRecForLoop(AR->getStart(), L);
 353   }
 354
 355   if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
 356     for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end();
 357          I != E; ++I)
 358       if (const SCEVAddRecExpr *AR = findAddRecForLoop(*I, L))
 359         return AR;
 360     return nullptr;
 361   }
 362
 363   return nullptr;
 364 }
 365
 366 const SCEV *IVUsers::getStride(const IVStrideUse &IU, const Loop *L) const {
 367   if (const SCEVAddRecExpr *AR = findAddRecForLoop(getExpr(IU), L))
 368     return AR->getStepRecurrence(*SE);
 369   return nullptr;
 370 }
 371
 372 void IVStrideUse::transformToPostInc(const Loop *L) {
 373   PostIncLoops.insert(L);
 374 }
 375
 376 void IVStrideUse::deleted() {
 377   // Remove this user from the list.
 378   Parent->Processed.erase(this->getUser());
 379   Parent->IVUses.erase(this);
 380   // this now dangles!
 381 }