375 lines · 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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements bookkeeping for "interesting" users of expressions10// 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"30using namespace llvm;31 32#define DEBUG_TYPE "iv-users"33 34AnalysisKey IVUsersAnalysis::Key;35 36IVUsers IVUsersAnalysis::run(Loop &L, LoopAnalysisManager &AM,37 LoopStandardAnalysisResults &AR) {38 return IVUsers(&L, &AR.AC, &AR.LI, &AR.DT, &AR.SE);39}40 41char IVUsersWrapperPass::ID = 0;42INITIALIZE_PASS_BEGIN(IVUsersWrapperPass, "iv-users",43 "Induction Variable Users", false, true)44INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)45INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)46INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)47INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)48INITIALIZE_PASS_END(IVUsersWrapperPass, "iv-users", "Induction Variable Users",49 false, true)50 51Pass *llvm::createIVUsersPass() { return new IVUsersWrapperPass(); }52 53/// isInteresting - Test whether the given expression is "interesting" when54/// used by the given expression, within the context of analyzing the55/// given loop.56static 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're61 // 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 that67 // the step value is not interesting, since we don't yet know how to68 // 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 SCEV *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 expression90/// and now we need to decide whether the user should use the preinc or post-inc91/// 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 the94/// post-inc value when we cannot) or it can end up adding extra live-ranges to95/// the loop, resulting in reg-reg copies (if we use the pre-inc value when we96/// should use the post-inc value).97static 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 latch108 // 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 guys113 // can live in blocks that are not dominated by the latch block, but (since114 // 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 corresponds121 // to a block that is not dominated by the latch block, give up and use the122 // 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 are129 // 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, recursively134/// add its users to the IVUsesByStride set and return true. Otherwise, return135/// false.136bool 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 that140 // 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 to148 // pass to SCEVExpander. Expressions are not safe to expand if they represent149 // 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 a155 // 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 removed161 // 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 and169 // 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 get185 // choices that depend on addressing mode use right, although we won't186 // 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 recording208 // 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 under222 // pre-increment assumptions. Those assumptions (no wrapping) might not223 // hold for the post-inc value. Catch such cases by making sure the224 // 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 the230 // 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 246IVStrideUse &IVUsers::AddUser(Instruction *User, Value *Operand) {247 IVUses.push_back(new IVStrideUse(this, User, Operand));248 return IVUses.back();249}250 251IVUsers::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 categorize259 // them by stride. Start by finding all of the PHI nodes in the header for260 // 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 265void 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 else286 OS << "Printing <null> User";287 OS << '\n';288 }289}290 291#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)292LLVM_DUMP_METHOD void IVUsers::dump() const { print(dbgs()); }293#endif294 295void IVUsers::releaseMemory() {296 Processed.clear();297 IVUses.clear();298}299 300IVUsersWrapperPass::IVUsersWrapperPass() : LoopPass(ID) {}301 302void IVUsersWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {303 AU.addRequired<AssumptionCacheTracker>();304 AU.addRequired<LoopInfoWrapperPass>();305 AU.addRequired<DominatorTreeWrapperPass>();306 AU.addRequired<ScalarEvolutionWrapperPass>();307 AU.setPreservesAll();308}309 310bool IVUsersWrapperPass::runOnLoop(Loop *L, LPPassManager &LPM) {311 auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(312 *L->getHeader()->getParent());313 auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();314 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();315 auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();316 317 IU.reset(new IVUsers(L, AC, LI, DT, SE));318 return false;319}320 321void IVUsersWrapperPass::print(raw_ostream &OS, const Module *M) const {322 IU->print(OS, M);323}324 325void IVUsersWrapperPass::releaseMemory() { IU->releaseMemory(); }326 327/// getReplacementExpr - Return a SCEV expression which computes the328/// value of the OperandValToReplace.329const SCEV *IVUsers::getReplacementExpr(const IVStrideUse &IU) const {330 return SE->getSCEV(IU.getOperandValToReplace());331}332 333/// getExpr - Return the expression for the use.334const SCEV *IVUsers::getExpr(const IVStrideUse &IU) const {335 const SCEV *Replacement = getReplacementExpr(IU);336 return normalizeForPostIncUse(Replacement, IU.getPostIncLoops(), *SE);337}338 339static const SCEVAddRecExpr *findAddRecForLoop(const SCEV *S, const Loop *L) {340 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {341 if (AR->getLoop() == L)342 return AR;343 return findAddRecForLoop(AR->getStart(), L);344 }345 346 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {347 for (const SCEV *Op : Add->operands())348 if (const SCEVAddRecExpr *AR = findAddRecForLoop(Op, L))349 return AR;350 return nullptr;351 }352 353 return nullptr;354}355 356const SCEV *IVUsers::getStride(const IVStrideUse &IU, const Loop *L) const {357 const SCEV *Expr = getExpr(IU);358 if (!Expr)359 return nullptr;360 if (const SCEVAddRecExpr *AR = findAddRecForLoop(Expr, L))361 return AR->getStepRecurrence(*SE);362 return nullptr;363}364 365void IVStrideUse::transformToPostInc(const Loop *L) {366 PostIncLoops.insert(L);367}368 369void IVStrideUse::deleted() {370 // Remove this user from the list.371 Parent->Processed.erase(this->getUser());372 Parent->IVUses.erase(this);373 // this now dangles!374}375