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