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