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
simplifyLoopInst(Loop & L,DominatorTree & DT,LoopInfo & LI,AssumptionCache & AC,const TargetLibraryInfo & TLI,MemorySSAUpdater * MSSAU)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
run(Loop & L,LoopAnalysisManager & AM,LoopStandardAnalysisResults & AR,LPMUpdater &)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