1 //===- IVUsers.cpp - Induction Variable Users -------------------*- C++ -*-===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
12 //===----------------------------------------------------------------------===//
22 #include "llvm/Config/llvm-config.h"
32 #define DEBUG_TYPE "iv-users"
42 INITIALIZE_PASS_BEGIN(IVUsersWrapperPass, "iv-users",
48 INITIALIZE_PASS_END(IVUsersWrapperPass, "iv-users", "Induction Variable Users",  in INITIALIZE_PASS_DEPENDENCY()
53 /// isInteresting - Test whether the given expression is "interesting" when
60     // Keep things simple. Don't touch loop-variant strides unless they're  in isInteresting()
62     if (AR->getLoop() == L)  in isInteresting()
63       return AR->isAffine() ||  in isInteresting()
64              (!L->contains(I) &&  in isInteresting()
65               SE->getSCEVAtScope(AR, LI->getLoopFor(I->getParent())) != AR);  in isInteresting()
69     return isInteresting(AR->getStart(), I, L, SE, LI) &&  in isInteresting()
70           !isInteresting(AR->getStepRecurrence(*SE), I, L, SE, LI);  in isInteresting()
76     for (const auto *Op : Add->operands())  in isInteresting()
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.
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).
100   if (L->contains(User))  in IVUseShouldUsePostIncValue()
103   BasicBlock *LatchBlock = L->getLoopLatch();  in IVUseShouldUsePostIncValue()
107   // Ok, the user is outside of the loop.  If it is dominated by the latch  in IVUseShouldUsePostIncValue()
108   // block, use the post-inc value.  in IVUseShouldUsePostIncValue()
109   if (DT->dominates(LatchBlock, User->getParent()))  in IVUseShouldUsePostIncValue()
113   // can live in blocks that are not dominated by the latch block, but (since  in IVUseShouldUsePostIncValue()
115   // should still use the post-inc value.  Check for this case now.  in IVUseShouldUsePostIncValue()
118     return false; // not a phi, not dominated by latch block.  in IVUseShouldUsePostIncValue()
121   // to a block that is not dominated by the latch block, give up and use the  in IVUseShouldUsePostIncValue()
123   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)  in IVUseShouldUsePostIncValue()
124     if (PN->getIncomingValue(i) == Operand &&  in IVUseShouldUsePostIncValue()
125         !DT->dominates(LatchBlock, PN->getIncomingBlock(i)))  in IVUseShouldUsePostIncValue()
129   // dominated by the latch block.  Use the post-incremented value.  in IVUseShouldUsePostIncValue()
137   const DataLayout &DL = I->getDataLayout();  in AddUsersIfInteresting()
144   if (!SE->isSCEVable(I->getType()))  in AddUsersIfInteresting()
153   // LSR is not APInt clean, do not touch integers bigger than 64-bits.  in AddUsersIfInteresting()
154   // Also avoid creating IVs of non-native types. For example, we don't want a  in AddUsersIfInteresting()
155   // 64-bit IV in 32-bit code just because the loop has one 64-bit cast.  in AddUsersIfInteresting()
156   uint64_t Width = SE->getTypeSizeInBits(I->getType());  in AddUsersIfInteresting()
166   const SCEV *ISE = SE->getSCEV(I);  in AddUsersIfInteresting()
174   for (Use &U : I->uses()) {  in AddUsersIfInteresting()
190     if (LI->getLoopFor(User->getParent()) != L) {  in AddUsersIfInteresting()
206       // Autodetect the post-inc loop set, populating NewUse.PostIncLoops.  in AddUsersIfInteresting()
212         auto *L = AR->getLoop();  in AddUsersIfInteresting()
222       // pre-increment assumptions. Those assumptions (no wrapping) might not  in AddUsersIfInteresting()
223       // hold for the post-inc value. Catch such cases by making sure the  in AddUsersIfInteresting()
239       LLVM_DEBUG(if (SE->getSCEV(I) != ISE) dbgs()  in AddUsersIfInteresting()
261   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I)  in IVUsers()
267   L->getHeader()->printAsOperand(OS, false);  in print()
268   if (SE->hasLoopInvariantBackedgeTakenCount(L)) {  in print()
269     OS << " with backedge-taken count " << *SE->getBackedgeTakenCount(L);  in print()
275     IVUse.getOperandValToReplace()->printAsOperand(OS, false);  in print()
278       OS << " (post-inc with loop ";  in print()
279       PostIncLoop->getHeader()->printAsOperand(OS, false);  in print()
284       IVUse.getUser()->print(OS);  in print()
314       *L->getHeader()->getParent());  in runOnLoop()
324   IU->print(OS, M);  in print()
327 void IVUsersWrapperPass::releaseMemory() { IU->releaseMemory(); }  in releaseMemory()
329 /// getReplacementExpr - Return a SCEV expression which computes the
332   return SE->getSCEV(IU.getOperandValToReplace());  in getReplacementExpr()
335 /// getExpr - Return the expression for the use.
343     if (AR->getLoop() == L)  in findAddRecForLoop()
345     return findAddRecForLoop(AR->getStart(), L);  in findAddRecForLoop()
349     for (const auto *Op : Add->operands())  in findAddRecForLoop()
363     return AR->getStepRecurrence(*SE);  in getStride()
373   Parent->Processed.erase(this->getUser());  in deleted()
374   Parent->IVUses.erase(this);  in deleted()