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/Support/Casting.h" 31 #include "llvm/Transforms/Utils/Local.h" 32 #include "llvm/Transforms/Utils/LoopUtils.h" 33 #include <optional> 34 #include <utility> 35 36 using namespace llvm; 37 38 #define DEBUG_TYPE "loop-instsimplify" 39 40 STATISTIC(NumSimplified, "Number of redundant instructions simplified"); 41 42 static bool simplifyLoopInst(Loop &L, DominatorTree &DT, LoopInfo &LI, 43 AssumptionCache &AC, const TargetLibraryInfo &TLI, 44 MemorySSAUpdater *MSSAU) { 45 const DataLayout &DL = L.getHeader()->getDataLayout(); 46 SimplifyQuery SQ(DL, &TLI, &DT, &AC); 47 48 // On the first pass over the loop body we try to simplify every instruction. 49 // On subsequent passes, we can restrict this to only simplifying instructions 50 // where the inputs have been updated. We end up needing two sets: one 51 // containing the instructions we are simplifying in *this* pass, and one for 52 // the instructions we will want to simplify in the *next* pass. We use 53 // pointers so we can swap between two stably allocated sets. 54 SmallPtrSet<const Instruction *, 8> S1, S2, *ToSimplify = &S1, *Next = &S2; 55 56 // Track the PHI nodes that have already been visited during each iteration so 57 // that we can identify when it is necessary to iterate. 58 SmallPtrSet<PHINode *, 4> VisitedPHIs; 59 60 // While simplifying we may discover dead code or cause code to become dead. 61 // Keep track of all such instructions and we will delete them at the end. 62 SmallVector<WeakTrackingVH, 8> DeadInsts; 63 64 // First we want to create an RPO traversal of the loop body. By processing in 65 // RPO we can ensure that definitions are processed prior to uses (for non PHI 66 // uses) in all cases. This ensures we maximize the simplifications in each 67 // iteration over the loop and minimizes the possible causes for continuing to 68 // iterate. 69 LoopBlocksRPO RPOT(&L); 70 RPOT.perform(&LI); 71 MemorySSA *MSSA = MSSAU ? MSSAU->getMemorySSA() : nullptr; 72 73 bool Changed = false; 74 for (;;) { 75 if (MSSAU && VerifyMemorySSA) 76 MSSA->verifyMemorySSA(); 77 for (BasicBlock *BB : RPOT) { 78 for (Instruction &I : *BB) { 79 if (auto *PI = dyn_cast<PHINode>(&I)) 80 VisitedPHIs.insert(PI); 81 82 if (I.use_empty()) { 83 if (isInstructionTriviallyDead(&I, &TLI)) 84 DeadInsts.push_back(&I); 85 continue; 86 } 87 88 // We special case the first iteration which we can detect due to the 89 // empty `ToSimplify` set. 90 bool IsFirstIteration = ToSimplify->empty(); 91 92 if (!IsFirstIteration && !ToSimplify->count(&I)) 93 continue; 94 95 Value *V = simplifyInstruction(&I, SQ.getWithInstruction(&I)); 96 if (!V || !LI.replacementPreservesLCSSAForm(&I, V)) 97 continue; 98 99 for (Use &U : llvm::make_early_inc_range(I.uses())) { 100 auto *UserI = cast<Instruction>(U.getUser()); 101 U.set(V); 102 103 // Do not bother dealing with unreachable code. 104 if (!DT.isReachableFromEntry(UserI->getParent())) 105 continue; 106 107 // If the instruction is used by a PHI node we have already processed 108 // we'll need to iterate on the loop body to converge, so add it to 109 // the next set. 110 if (auto *UserPI = dyn_cast<PHINode>(UserI)) 111 if (VisitedPHIs.count(UserPI)) { 112 Next->insert(UserPI); 113 continue; 114 } 115 116 // If we are only simplifying targeted instructions and the user is an 117 // instruction in the loop body, add it to our set of targeted 118 // instructions. Because we process defs before uses (outside of PHIs) 119 // we won't have visited it yet. 120 // 121 // We also skip any uses outside of the loop being simplified. Those 122 // should always be PHI nodes due to LCSSA form, and we don't want to 123 // try to simplify those away. 124 assert((L.contains(UserI) || isa<PHINode>(UserI)) && 125 "Uses outside the loop should be PHI nodes due to LCSSA!"); 126 if (!IsFirstIteration && L.contains(UserI)) 127 ToSimplify->insert(UserI); 128 } 129 130 if (MSSAU) 131 if (Instruction *SimpleI = dyn_cast_or_null<Instruction>(V)) 132 if (MemoryAccess *MA = MSSA->getMemoryAccess(&I)) 133 if (MemoryAccess *ReplacementMA = MSSA->getMemoryAccess(SimpleI)) 134 MA->replaceAllUsesWith(ReplacementMA); 135 136 assert(I.use_empty() && "Should always have replaced all uses!"); 137 if (isInstructionTriviallyDead(&I, &TLI)) 138 DeadInsts.push_back(&I); 139 ++NumSimplified; 140 Changed = true; 141 } 142 } 143 144 // Delete any dead instructions found thus far now that we've finished an 145 // iteration over all instructions in all the loop blocks. 146 if (!DeadInsts.empty()) { 147 Changed = true; 148 RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, &TLI, MSSAU); 149 } 150 151 if (MSSAU && VerifyMemorySSA) 152 MSSA->verifyMemorySSA(); 153 154 // If we never found a PHI that needs to be simplified in the next 155 // iteration, we're done. 156 if (Next->empty()) 157 break; 158 159 // Otherwise, put the next set in place for the next iteration and reset it 160 // and the visited PHIs for that iteration. 161 std::swap(Next, ToSimplify); 162 Next->clear(); 163 VisitedPHIs.clear(); 164 DeadInsts.clear(); 165 } 166 167 return Changed; 168 } 169 170 PreservedAnalyses LoopInstSimplifyPass::run(Loop &L, LoopAnalysisManager &AM, 171 LoopStandardAnalysisResults &AR, 172 LPMUpdater &) { 173 std::optional<MemorySSAUpdater> MSSAU; 174 if (AR.MSSA) { 175 MSSAU = MemorySSAUpdater(AR.MSSA); 176 if (VerifyMemorySSA) 177 AR.MSSA->verifyMemorySSA(); 178 } 179 if (!simplifyLoopInst(L, AR.DT, AR.LI, AR.AC, AR.TLI, 180 MSSAU ? &*MSSAU : nullptr)) 181 return PreservedAnalyses::all(); 182 183 auto PA = getLoopPassPreservedAnalyses(); 184 PA.preserveSet<CFGAnalyses>(); 185 if (AR.MSSA) 186 PA.preserve<MemorySSAAnalysis>(); 187 return PA; 188 } 189