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