1 //===- LoopInstSimplify.cpp - Loop Instruction Simplification Pass --------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass performs lightweight instruction simplification on loop bodies.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "llvm/Transforms/Scalar/LoopInstSimplify.h"
15 #include "llvm/ADT/PointerIntPair.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/Analysis/AssumptionCache.h"
21 #include "llvm/Analysis/InstructionSimplify.h"
22 #include "llvm/Analysis/LoopInfo.h"
23 #include "llvm/Analysis/LoopIterator.h"
24 #include "llvm/Analysis/LoopPass.h"
25 #include "llvm/Analysis/TargetLibraryInfo.h"
26 #include "llvm/Transforms/Utils/Local.h"
27 #include "llvm/IR/BasicBlock.h"
28 #include "llvm/IR/CFG.h"
29 #include "llvm/IR/DataLayout.h"
30 #include "llvm/IR/Dominators.h"
31 #include "llvm/IR/Instruction.h"
32 #include "llvm/IR/Instructions.h"
33 #include "llvm/IR/Module.h"
34 #include "llvm/IR/PassManager.h"
35 #include "llvm/IR/User.h"
36 #include "llvm/Pass.h"
37 #include "llvm/Support/Casting.h"
38 #include "llvm/Transforms/Scalar.h"
39 #include "llvm/Transforms/Utils/LoopUtils.h"
40 #include <algorithm>
41 #include <utility>
42
43 using namespace llvm;
44
45 #define DEBUG_TYPE "loop-instsimplify"
46
47 STATISTIC(NumSimplified, "Number of redundant instructions simplified");
48
simplifyLoopInst(Loop & L,DominatorTree & DT,LoopInfo & LI,AssumptionCache & AC,const TargetLibraryInfo & TLI)49 static bool simplifyLoopInst(Loop &L, DominatorTree &DT, LoopInfo &LI,
50 AssumptionCache &AC,
51 const TargetLibraryInfo &TLI) {
52 const DataLayout &DL = L.getHeader()->getModule()->getDataLayout();
53 SimplifyQuery SQ(DL, &TLI, &DT, &AC);
54
55 // On the first pass over the loop body we try to simplify every instruction.
56 // On subsequent passes, we can restrict this to only simplifying instructions
57 // where the inputs have been updated. We end up needing two sets: one
58 // containing the instructions we are simplifying in *this* pass, and one for
59 // the instructions we will want to simplify in the *next* pass. We use
60 // pointers so we can swap between two stably allocated sets.
61 SmallPtrSet<const Instruction *, 8> S1, S2, *ToSimplify = &S1, *Next = &S2;
62
63 // Track the PHI nodes that have already been visited during each iteration so
64 // that we can identify when it is necessary to iterate.
65 SmallPtrSet<PHINode *, 4> VisitedPHIs;
66
67 // While simplifying we may discover dead code or cause code to become dead.
68 // Keep track of all such instructions and we will delete them at the end.
69 SmallVector<Instruction *, 8> DeadInsts;
70
71 // First we want to create an RPO traversal of the loop body. By processing in
72 // RPO we can ensure that definitions are processed prior to uses (for non PHI
73 // uses) in all cases. This ensures we maximize the simplifications in each
74 // iteration over the loop and minimizes the possible causes for continuing to
75 // iterate.
76 LoopBlocksRPO RPOT(&L);
77 RPOT.perform(&LI);
78
79 bool Changed = false;
80 for (;;) {
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 (Value::use_iterator UI = I.use_begin(), UE = I.use_end();
104 UI != UE;) {
105 Use &U = *UI++;
106 auto *UserI = cast<Instruction>(U.getUser());
107 U.set(V);
108
109 // If the instruction is used by a PHI node we have already processed
110 // we'll need to iterate on the loop body to converge, so add it to
111 // the next set.
112 if (auto *UserPI = dyn_cast<PHINode>(UserI))
113 if (VisitedPHIs.count(UserPI)) {
114 Next->insert(UserPI);
115 continue;
116 }
117
118 // If we are only simplifying targeted instructions and the user is an
119 // instruction in the loop body, add it to our set of targeted
120 // instructions. Because we process defs before uses (outside of PHIs)
121 // we won't have visited it yet.
122 //
123 // We also skip any uses outside of the loop being simplified. Those
124 // should always be PHI nodes due to LCSSA form, and we don't want to
125 // try to simplify those away.
126 assert((L.contains(UserI) || isa<PHINode>(UserI)) &&
127 "Uses outside the loop should be PHI nodes due to LCSSA!");
128 if (!IsFirstIteration && L.contains(UserI))
129 ToSimplify->insert(UserI);
130 }
131
132 assert(I.use_empty() && "Should always have replaced all uses!");
133 if (isInstructionTriviallyDead(&I, &TLI))
134 DeadInsts.push_back(&I);
135 ++NumSimplified;
136 Changed = true;
137 }
138 }
139
140 // Delete any dead instructions found thus far now that we've finished an
141 // iteration over all instructions in all the loop blocks.
142 if (!DeadInsts.empty()) {
143 Changed = true;
144 RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, &TLI);
145 }
146
147 // If we never found a PHI that needs to be simplified in the next
148 // iteration, we're done.
149 if (Next->empty())
150 break;
151
152 // Otherwise, put the next set in place for the next iteration and reset it
153 // and the visited PHIs for that iteration.
154 std::swap(Next, ToSimplify);
155 Next->clear();
156 VisitedPHIs.clear();
157 DeadInsts.clear();
158 }
159
160 return Changed;
161 }
162
163 namespace {
164
165 class LoopInstSimplifyLegacyPass : public LoopPass {
166 public:
167 static char ID; // Pass ID, replacement for typeid
168
LoopInstSimplifyLegacyPass()169 LoopInstSimplifyLegacyPass() : LoopPass(ID) {
170 initializeLoopInstSimplifyLegacyPassPass(*PassRegistry::getPassRegistry());
171 }
172
runOnLoop(Loop * L,LPPassManager & LPM)173 bool runOnLoop(Loop *L, LPPassManager &LPM) override {
174 if (skipLoop(L))
175 return false;
176 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
177 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
178 AssumptionCache &AC =
179 getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
180 *L->getHeader()->getParent());
181 const TargetLibraryInfo &TLI =
182 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
183
184 return simplifyLoopInst(*L, DT, LI, AC, TLI);
185 }
186
getAnalysisUsage(AnalysisUsage & AU) const187 void getAnalysisUsage(AnalysisUsage &AU) const override {
188 AU.addRequired<AssumptionCacheTracker>();
189 AU.addRequired<DominatorTreeWrapperPass>();
190 AU.addRequired<TargetLibraryInfoWrapperPass>();
191 AU.setPreservesCFG();
192 getLoopAnalysisUsage(AU);
193 }
194 };
195
196 } // end anonymous namespace
197
run(Loop & L,LoopAnalysisManager & AM,LoopStandardAnalysisResults & AR,LPMUpdater &)198 PreservedAnalyses LoopInstSimplifyPass::run(Loop &L, LoopAnalysisManager &AM,
199 LoopStandardAnalysisResults &AR,
200 LPMUpdater &) {
201 if (!simplifyLoopInst(L, AR.DT, AR.LI, AR.AC, AR.TLI))
202 return PreservedAnalyses::all();
203
204 auto PA = getLoopPassPreservedAnalyses();
205 PA.preserveSet<CFGAnalyses>();
206 return PA;
207 }
208
209 char LoopInstSimplifyLegacyPass::ID = 0;
210
211 INITIALIZE_PASS_BEGIN(LoopInstSimplifyLegacyPass, "loop-instsimplify",
212 "Simplify instructions in loops", false, false)
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)213 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
214 INITIALIZE_PASS_DEPENDENCY(LoopPass)
215 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
216 INITIALIZE_PASS_END(LoopInstSimplifyLegacyPass, "loop-instsimplify",
217 "Simplify instructions in loops", false, false)
218
219 Pass *llvm::createLoopInstSimplifyPass() {
220 return new LoopInstSimplifyLegacyPass();
221 }
222