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
36using namespace llvm;
37
38#define DEBUG_TYPE "loop-instsimplify"
39
40STATISTIC(NumSimplified, "Number of redundant instructions simplified");
41
42static 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: &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>(Val: &I))
80 VisitedPHIs.insert(Ptr: PI);
81
82 if (I.use_empty()) {
83 if (isInstructionTriviallyDead(I: &I, TLI: &TLI))
84 DeadInsts.push_back(Elt: &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(Ptr: &I))
93 continue;
94
95 Value *V = simplifyInstruction(I: &I, Q: SQ.getWithInstruction(I: &I));
96 if (!V || !LI.replacementPreservesLCSSAForm(From: &I, To: V))
97 continue;
98
99 for (Use &U : llvm::make_early_inc_range(Range: I.uses())) {
100 auto *UserI = cast<Instruction>(Val: U.getUser());
101 U.set(V);
102
103 // Do not bother dealing with unreachable code.
104 if (!DT.isReachableFromEntry(A: 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>(Val: UserI))
111 if (VisitedPHIs.count(Ptr: UserPI)) {
112 Next->insert(Ptr: 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(Inst: UserI))
127 ToSimplify->insert(Ptr: UserI);
128 }
129
130 if (MSSAU)
131 if (Instruction *SimpleI = dyn_cast_or_null<Instruction>(Val: V))
132 if (MemoryAccess *MA = MSSA->getMemoryAccess(I: &I))
133 if (MemoryAccess *ReplacementMA = MSSA->getMemoryAccess(I: SimpleI))
134 MA->replaceAllUsesWith(V: ReplacementMA);
135
136 assert(I.use_empty() && "Should always have replaced all uses!");
137 if (isInstructionTriviallyDead(I: &I, TLI: &TLI))
138 DeadInsts.push_back(Elt: &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: &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(a&: Next, b&: ToSimplify);
162 Next->clear();
163 VisitedPHIs.clear();
164 DeadInsts.clear();
165 }
166
167 return Changed;
168}
169
170PreservedAnalyses 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, DT&: AR.DT, LI&: AR.LI, AC&: AR.AC, TLI: AR.TLI,
180 MSSAU: 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