1 //===- LoopInstSimplify.cpp - Loop Instruction Simplification Pass --------===// 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 pass performs lightweight instruction simplification on loop bodies. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "llvm/Transforms/Scalar/LoopInstSimplify.h" 14 #include "llvm/ADT/STLExtras.h" 15 #include "llvm/ADT/SmallPtrSet.h" 16 #include "llvm/ADT/SmallVector.h" 17 #include "llvm/ADT/Statistic.h" 18 #include "llvm/Analysis/AssumptionCache.h" 19 #include "llvm/Analysis/InstructionSimplify.h" 20 #include "llvm/Analysis/LoopInfo.h" 21 #include "llvm/Analysis/LoopIterator.h" 22 #include "llvm/Analysis/LoopPass.h" 23 #include "llvm/Analysis/MemorySSA.h" 24 #include "llvm/Analysis/MemorySSAUpdater.h" 25 #include "llvm/Analysis/TargetLibraryInfo.h" 26 #include "llvm/IR/BasicBlock.h" 27 #include "llvm/IR/Dominators.h" 28 #include "llvm/IR/Instruction.h" 29 #include "llvm/IR/Instructions.h" 30 #include "llvm/IR/Module.h" 31 #include "llvm/IR/PassManager.h" 32 #include "llvm/InitializePasses.h" 33 #include "llvm/Pass.h" 34 #include "llvm/Support/Casting.h" 35 #include "llvm/Transforms/Scalar.h" 36 #include "llvm/Transforms/Utils/Local.h" 37 #include "llvm/Transforms/Utils/LoopUtils.h" 38 #include <utility> 39 40 using namespace llvm; 41 42 #define DEBUG_TYPE "loop-instsimplify" 43 44 STATISTIC(NumSimplified, "Number of redundant instructions simplified"); 45 46 static bool simplifyLoopInst(Loop &L, DominatorTree &DT, LoopInfo &LI, 47 AssumptionCache &AC, const TargetLibraryInfo &TLI, 48 MemorySSAUpdater *MSSAU) { 49 const DataLayout &DL = L.getHeader()->getModule()->getDataLayout(); 50 SimplifyQuery SQ(DL, &TLI, &DT, &AC); 51 52 // On the first pass over the loop body we try to simplify every instruction. 53 // On subsequent passes, we can restrict this to only simplifying instructions 54 // where the inputs have been updated. We end up needing two sets: one 55 // containing the instructions we are simplifying in *this* pass, and one for 56 // the instructions we will want to simplify in the *next* pass. We use 57 // pointers so we can swap between two stably allocated sets. 58 SmallPtrSet<const Instruction *, 8> S1, S2, *ToSimplify = &S1, *Next = &S2; 59 60 // Track the PHI nodes that have already been visited during each iteration so 61 // that we can identify when it is necessary to iterate. 62 SmallPtrSet<PHINode *, 4> VisitedPHIs; 63 64 // While simplifying we may discover dead code or cause code to become dead. 65 // Keep track of all such instructions and we will delete them at the end. 66 SmallVector<WeakTrackingVH, 8> DeadInsts; 67 68 // First we want to create an RPO traversal of the loop body. By processing in 69 // RPO we can ensure that definitions are processed prior to uses (for non PHI 70 // uses) in all cases. This ensures we maximize the simplifications in each 71 // iteration over the loop and minimizes the possible causes for continuing to 72 // iterate. 73 LoopBlocksRPO RPOT(&L); 74 RPOT.perform(&LI); 75 MemorySSA *MSSA = MSSAU ? MSSAU->getMemorySSA() : nullptr; 76 77 bool Changed = false; 78 for (;;) { 79 if (MSSAU && VerifyMemorySSA) 80 MSSA->verifyMemorySSA(); 81 for (BasicBlock *BB : RPOT) { 82 for (Instruction &I : *BB) { 83 if (auto *PI = dyn_cast<PHINode>(&I)) 84 VisitedPHIs.insert(PI); 85 86 if (I.use_empty()) { 87 if (isInstructionTriviallyDead(&I, &TLI)) 88 DeadInsts.push_back(&I); 89 continue; 90 } 91 92 // We special case the first iteration which we can detect due to the 93 // empty `ToSimplify` set. 94 bool IsFirstIteration = ToSimplify->empty(); 95 96 if (!IsFirstIteration && !ToSimplify->count(&I)) 97 continue; 98 99 Value *V = simplifyInstruction(&I, SQ.getWithInstruction(&I)); 100 if (!V || !LI.replacementPreservesLCSSAForm(&I, V)) 101 continue; 102 103 for (Use &U : llvm::make_early_inc_range(I.uses())) { 104 auto *UserI = cast<Instruction>(U.getUser()); 105 U.set(V); 106 107 // Do not bother dealing with unreachable code. 108 if (!DT.isReachableFromEntry(UserI->getParent())) 109 continue; 110 111 // If the instruction is used by a PHI node we have already processed 112 // we'll need to iterate on the loop body to converge, so add it to 113 // the next set. 114 if (auto *UserPI = dyn_cast<PHINode>(UserI)) 115 if (VisitedPHIs.count(UserPI)) { 116 Next->insert(UserPI); 117 continue; 118 } 119 120 // If we are only simplifying targeted instructions and the user is an 121 // instruction in the loop body, add it to our set of targeted 122 // instructions. Because we process defs before uses (outside of PHIs) 123 // we won't have visited it yet. 124 // 125 // We also skip any uses outside of the loop being simplified. Those 126 // should always be PHI nodes due to LCSSA form, and we don't want to 127 // try to simplify those away. 128 assert((L.contains(UserI) || isa<PHINode>(UserI)) && 129 "Uses outside the loop should be PHI nodes due to LCSSA!"); 130 if (!IsFirstIteration && L.contains(UserI)) 131 ToSimplify->insert(UserI); 132 } 133 134 if (MSSAU) 135 if (Instruction *SimpleI = dyn_cast_or_null<Instruction>(V)) 136 if (MemoryAccess *MA = MSSA->getMemoryAccess(&I)) 137 if (MemoryAccess *ReplacementMA = MSSA->getMemoryAccess(SimpleI)) 138 MA->replaceAllUsesWith(ReplacementMA); 139 140 assert(I.use_empty() && "Should always have replaced all uses!"); 141 if (isInstructionTriviallyDead(&I, &TLI)) 142 DeadInsts.push_back(&I); 143 ++NumSimplified; 144 Changed = true; 145 } 146 } 147 148 // Delete any dead instructions found thus far now that we've finished an 149 // iteration over all instructions in all the loop blocks. 150 if (!DeadInsts.empty()) { 151 Changed = true; 152 RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, &TLI, MSSAU); 153 } 154 155 if (MSSAU && VerifyMemorySSA) 156 MSSA->verifyMemorySSA(); 157 158 // If we never found a PHI that needs to be simplified in the next 159 // iteration, we're done. 160 if (Next->empty()) 161 break; 162 163 // Otherwise, put the next set in place for the next iteration and reset it 164 // and the visited PHIs for that iteration. 165 std::swap(Next, ToSimplify); 166 Next->clear(); 167 VisitedPHIs.clear(); 168 DeadInsts.clear(); 169 } 170 171 return Changed; 172 } 173 174 namespace { 175 176 class LoopInstSimplifyLegacyPass : public LoopPass { 177 public: 178 static char ID; // Pass ID, replacement for typeid 179 180 LoopInstSimplifyLegacyPass() : LoopPass(ID) { 181 initializeLoopInstSimplifyLegacyPassPass(*PassRegistry::getPassRegistry()); 182 } 183 184 bool runOnLoop(Loop *L, LPPassManager &LPM) override { 185 if (skipLoop(L)) 186 return false; 187 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 188 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 189 AssumptionCache &AC = 190 getAnalysis<AssumptionCacheTracker>().getAssumptionCache( 191 *L->getHeader()->getParent()); 192 const TargetLibraryInfo &TLI = 193 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI( 194 *L->getHeader()->getParent()); 195 MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA(); 196 MemorySSAUpdater MSSAU(MSSA); 197 198 return simplifyLoopInst(*L, DT, LI, AC, TLI, &MSSAU); 199 } 200 201 void getAnalysisUsage(AnalysisUsage &AU) const override { 202 AU.addRequired<AssumptionCacheTracker>(); 203 AU.addRequired<DominatorTreeWrapperPass>(); 204 AU.addRequired<TargetLibraryInfoWrapperPass>(); 205 AU.setPreservesCFG(); 206 AU.addRequired<MemorySSAWrapperPass>(); 207 AU.addPreserved<MemorySSAWrapperPass>(); 208 getLoopAnalysisUsage(AU); 209 } 210 }; 211 212 } // end anonymous namespace 213 214 PreservedAnalyses LoopInstSimplifyPass::run(Loop &L, LoopAnalysisManager &AM, 215 LoopStandardAnalysisResults &AR, 216 LPMUpdater &) { 217 Optional<MemorySSAUpdater> MSSAU; 218 if (AR.MSSA) { 219 MSSAU = MemorySSAUpdater(AR.MSSA); 220 if (VerifyMemorySSA) 221 AR.MSSA->verifyMemorySSA(); 222 } 223 if (!simplifyLoopInst(L, AR.DT, AR.LI, AR.AC, AR.TLI, 224 MSSAU ? MSSAU.getPointer() : nullptr)) 225 return PreservedAnalyses::all(); 226 227 auto PA = getLoopPassPreservedAnalyses(); 228 PA.preserveSet<CFGAnalyses>(); 229 if (AR.MSSA) 230 PA.preserve<MemorySSAAnalysis>(); 231 return PA; 232 } 233 234 char LoopInstSimplifyLegacyPass::ID = 0; 235 236 INITIALIZE_PASS_BEGIN(LoopInstSimplifyLegacyPass, "loop-instsimplify", 237 "Simplify instructions in loops", false, false) 238 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 239 INITIALIZE_PASS_DEPENDENCY(LoopPass) 240 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass) 241 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 242 INITIALIZE_PASS_END(LoopInstSimplifyLegacyPass, "loop-instsimplify", 243 "Simplify instructions in loops", false, false) 244 245 Pass *llvm::createLoopInstSimplifyPass() { 246 return new LoopInstSimplifyLegacyPass(); 247 } 248