1 //===- DeadCodeElimination.cpp - Eliminate dead iteration ----------------===//
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 // The polyhedral dead code elimination pass analyses a SCoP to eliminate
10 // statement instances that can be proven dead.
11 // As a consequence, the code generated for this SCoP may execute a statement
12 // less often. This means, a statement may be executed only in certain loop
13 // iterations or it may not even be part of the generated code at all.
14 //
15 // This code:
16 //
17 // for (i = 0; i < N; i++)
18 // arr[i] = 0;
19 // for (i = 0; i < N; i++)
20 // arr[i] = 10;
21 // for (i = 0; i < N; i++)
22 // arr[i] = i;
23 //
24 // is e.g. simplified to:
25 //
26 // for (i = 0; i < N; i++)
27 // arr[i] = i;
28 //
29 // The idea and the algorithm used was first implemented by Sven Verdoolaege in
30 // the 'ppcg' tool.
31 //
32 //===----------------------------------------------------------------------===//
33
34 #include "polly/DeadCodeElimination.h"
35 #include "polly/DependenceInfo.h"
36 #include "polly/LinkAllPasses.h"
37 #include "polly/Options.h"
38 #include "polly/ScopInfo.h"
39 #include "llvm/Support/CommandLine.h"
40 #include "isl/isl-noexceptions.h"
41
42 using namespace llvm;
43 using namespace polly;
44
45 namespace {
46
47 cl::opt<int> DCEPreciseSteps(
48 "polly-dce-precise-steps",
49 cl::desc("The number of precise steps between two approximating "
50 "iterations. (A value of -1 schedules another approximation stage "
51 "before the actual dead code elimination."),
52 cl::init(-1), cl::cat(PollyCategory));
53
54 class DeadCodeElimWrapperPass final : public ScopPass {
55 public:
56 static char ID;
DeadCodeElimWrapperPass()57 explicit DeadCodeElimWrapperPass() : ScopPass(ID) {}
58
59 /// Remove dead iterations from the schedule of @p S.
60 bool runOnScop(Scop &S) override;
61
62 /// Register all analyses and transformation required.
63 void getAnalysisUsage(AnalysisUsage &AU) const override;
64 };
65
66 char DeadCodeElimWrapperPass::ID = 0;
67
68 /// Return the set of live iterations.
69 ///
70 /// The set of live iterations are all iterations that write to memory and for
71 /// which we can not prove that there will be a later write that _must_
72 /// overwrite the same memory location and is consequently the only one that
73 /// is visible after the execution of the SCoP.
74 ///
75 /// To compute the live outs, we compute for the data-locations that are
76 /// must-written to the last statement that touches these locations. On top of
77 /// this we add all statements that perform may-write accesses.
78 ///
79 /// We could be more precise by removing may-write accesses for which we know
80 /// that they are overwritten by a must-write after. However, at the moment the
81 /// only may-writes we introduce access the full (unbounded) array, such that
82 /// bounded write accesses can not overwrite all of the data-locations. As
83 /// this means may-writes are in the current situation always live, there is
84 /// no point in trying to remove them from the live-out set.
getLiveOut(Scop & S)85 static isl::union_set getLiveOut(Scop &S) {
86 isl::union_map Schedule = S.getSchedule();
87 isl::union_map MustWrites = S.getMustWrites();
88 isl::union_map WriteIterations = MustWrites.reverse();
89 isl::union_map WriteTimes = WriteIterations.apply_range(Schedule);
90
91 isl::union_map LastWriteTimes = WriteTimes.lexmax();
92 isl::union_map LastWriteIterations =
93 LastWriteTimes.apply_range(Schedule.reverse());
94
95 isl::union_set Live = LastWriteIterations.range();
96 isl::union_map MayWrites = S.getMayWrites();
97 Live = Live.unite(MayWrites.domain());
98 return Live.coalesce();
99 }
100
101 /// Performs polyhedral dead iteration elimination by:
102 /// o Assuming that the last write to each location is live.
103 /// o Following each RAW dependency from a live iteration backwards and adding
104 /// that iteration to the live set.
105 ///
106 /// To ensure the set of live iterations does not get too complex we always
107 /// combine a certain number of precise steps with one approximating step that
108 /// simplifies the life set with an affine hull.
runDeadCodeElimination(Scop & S,int PreciseSteps,const Dependences & D)109 static bool runDeadCodeElimination(Scop &S, int PreciseSteps,
110 const Dependences &D) {
111 if (!D.hasValidDependences())
112 return false;
113
114 isl::union_set Live = getLiveOut(S);
115 isl::union_map Dep =
116 D.getDependences(Dependences::TYPE_RAW | Dependences::TYPE_RED);
117 Dep = Dep.reverse();
118
119 if (PreciseSteps == -1)
120 Live = Live.affine_hull();
121
122 isl::union_set OriginalDomain = S.getDomains();
123 int Steps = 0;
124 while (true) {
125 Steps++;
126
127 isl::union_set Extra = Live.apply(Dep);
128
129 if (Extra.is_subset(Live))
130 break;
131
132 Live = Live.unite(Extra);
133
134 if (Steps > PreciseSteps) {
135 Steps = 0;
136 Live = Live.affine_hull();
137 }
138
139 Live = Live.intersect(OriginalDomain);
140 }
141
142 Live = Live.coalesce();
143
144 return S.restrictDomains(Live);
145 }
146
runOnScop(Scop & S)147 bool DeadCodeElimWrapperPass::runOnScop(Scop &S) {
148 auto &DI = getAnalysis<DependenceInfo>();
149 const Dependences &Deps = DI.getDependences(Dependences::AL_Statement);
150
151 bool Changed = runDeadCodeElimination(S, DCEPreciseSteps, Deps);
152
153 // FIXME: We can probably avoid the recomputation of all dependences by
154 // updating them explicitly.
155 if (Changed)
156 DI.recomputeDependences(Dependences::AL_Statement);
157
158 return false;
159 }
160
getAnalysisUsage(AnalysisUsage & AU) const161 void DeadCodeElimWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
162 ScopPass::getAnalysisUsage(AU);
163 AU.addRequired<DependenceInfo>();
164 }
165
166 } // namespace
167
createDeadCodeElimWrapperPass()168 Pass *polly::createDeadCodeElimWrapperPass() {
169 return new DeadCodeElimWrapperPass();
170 }
171
run(Scop & S,ScopAnalysisManager & SAM,ScopStandardAnalysisResults & SAR,SPMUpdater & U)172 llvm::PreservedAnalyses DeadCodeElimPass::run(Scop &S, ScopAnalysisManager &SAM,
173 ScopStandardAnalysisResults &SAR,
174 SPMUpdater &U) {
175 DependenceAnalysis::Result &DA = SAM.getResult<DependenceAnalysis>(S, SAR);
176 const Dependences &Deps = DA.getDependences(Dependences::AL_Statement);
177
178 bool Changed = runDeadCodeElimination(S, DCEPreciseSteps, Deps);
179
180 // FIXME: We can probably avoid the recomputation of all dependences by
181 // updating them explicitly.
182 if (Changed)
183 DA.recomputeDependences(Dependences::AL_Statement);
184
185 if (!Changed)
186 return PreservedAnalyses::all();
187
188 PreservedAnalyses PA;
189 PA.preserveSet<AllAnalysesOn<Module>>();
190 PA.preserveSet<AllAnalysesOn<Function>>();
191 PA.preserveSet<AllAnalysesOn<Loop>>();
192 return PA;
193 }
194
195 INITIALIZE_PASS_BEGIN(DeadCodeElimWrapperPass, "polly-dce",
196 "Polly - Remove dead iterations", false, false)
197 INITIALIZE_PASS_DEPENDENCY(DependenceInfo)
198 INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass)
199 INITIALIZE_PASS_END(DeadCodeElimWrapperPass, "polly-dce",
200 "Polly - Remove dead iterations", false, false)
201