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 
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()->getModule()->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 
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