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
39using namespace llvm;
40
41#define DEBUG_TYPE "loop-instsimplify"
42
43STATISTIC(NumSimplified, "Number of redundant instructions simplified");
44
45static 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: &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>(Val: &I))
83 VisitedPHIs.insert(Ptr: PI);
84
85 if (I.use_empty()) {
86 if (isInstructionTriviallyDead(I: &I, TLI: &TLI))
87 DeadInsts.push_back(Elt: &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(Ptr: &I))
96 continue;
97
98 Value *V = simplifyInstruction(I: &I, Q: SQ.getWithInstruction(I: &I));
99 if (!V || !LI.replacementPreservesLCSSAForm(From: &I, To: V))
100 continue;
101
102 for (Use &U : llvm::make_early_inc_range(Range: I.uses())) {
103 auto *UserI = cast<Instruction>(Val: U.getUser());
104 U.set(V);
105
106 // Do not bother dealing with unreachable code.
107 if (!DT.isReachableFromEntry(A: 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>(Val: UserI))
114 if (VisitedPHIs.count(Ptr: UserPI)) {
115 Next->insert(Ptr: 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(Inst: UserI))
130 ToSimplify->insert(Ptr: UserI);
131 }
132
133 if (MSSAU)
134 if (Instruction *SimpleI = dyn_cast_or_null<Instruction>(Val: V))
135 if (MemoryAccess *MA = MSSA->getMemoryAccess(I: &I))
136 if (MemoryAccess *ReplacementMA = MSSA->getMemoryAccess(I: SimpleI))
137 MA->replaceAllUsesWith(V: ReplacementMA);
138
139 assert(I.use_empty() && "Should always have replaced all uses!");
140 if (isInstructionTriviallyDead(I: &I, TLI: &TLI))
141 DeadInsts.push_back(Elt: &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: &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(a&: Next, b&: ToSimplify);
165 Next->clear();
166 VisitedPHIs.clear();
167 DeadInsts.clear();
168 }
169
170 return Changed;
171}
172
173PreservedAnalyses 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, DT&: AR.DT, LI&: AR.LI, AC&: AR.AC, TLI: AR.TLI,
183 MSSAU: 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