llvm/lib/Analysis/IVUsers.cpp

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