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
42using namespace llvm;
43using namespace polly;
44
45namespace {
46
47cl::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(Val: -1), cl::cat(PollyCategory));
53
54class DeadCodeElimWrapperPass final : public ScopPass {
55public:
56 static char ID;
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
66char 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.
85static 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(umap2: Schedule);
90
91 isl::union_map LastWriteTimes = WriteTimes.lexmax();
92 isl::union_map LastWriteIterations =
93 LastWriteTimes.apply_range(umap2: Schedule.reverse());
94
95 isl::union_set Live = LastWriteIterations.range();
96 isl::union_map MayWrites = S.getMayWrites();
97 Live = Live.unite(uset2: 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.
109static 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(Kinds: 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(umap: Dep);
128
129 if (Extra.is_subset(uset2: Live))
130 break;
131
132 Live = Live.unite(uset2: Extra);
133
134 if (Steps > PreciseSteps) {
135 Steps = 0;
136 Live = Live.affine_hull();
137 }
138
139 Live = Live.intersect(uset2: OriginalDomain);
140 }
141
142 Live = Live.coalesce();
143
144 return S.restrictDomains(Domain: Live);
145}
146
147bool DeadCodeElimWrapperPass::runOnScop(Scop &S) {
148 auto &DI = getAnalysis<DependenceInfo>();
149 const Dependences &Deps = DI.getDependences(Level: Dependences::AL_Statement);
150
151 bool Changed = runDeadCodeElimination(S, PreciseSteps: DCEPreciseSteps, D: Deps);
152
153 // FIXME: We can probably avoid the recomputation of all dependences by
154 // updating them explicitly.
155 if (Changed)
156 DI.recomputeDependences(Level: Dependences::AL_Statement);
157
158 return false;
159}
160
161void DeadCodeElimWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
162 ScopPass::getAnalysisUsage(AU);
163 AU.addRequired<DependenceInfo>();
164}
165
166} // namespace
167
168Pass *polly::createDeadCodeElimWrapperPass() {
169 return new DeadCodeElimWrapperPass();
170}
171
172llvm::PreservedAnalyses DeadCodeElimPass::run(Scop &S, ScopAnalysisManager &SAM,
173 ScopStandardAnalysisResults &SAR,
174 SPMUpdater &U) {
175 DependenceAnalysis::Result &DA = SAM.getResult<DependenceAnalysis>(IR&: S, ExtraArgs&: SAR);
176 const Dependences &Deps = DA.getDependences(Level: Dependences::AL_Statement);
177
178 bool Changed = runDeadCodeElimination(S, PreciseSteps: DCEPreciseSteps, D: Deps);
179
180 // FIXME: We can probably avoid the recomputation of all dependences by
181 // updating them explicitly.
182 if (Changed)
183 DA.recomputeDependences(Level: 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
195INITIALIZE_PASS_BEGIN(DeadCodeElimWrapperPass, "polly-dce",
196 "Polly - Remove dead iterations", false, false)
197INITIALIZE_PASS_DEPENDENCY(DependenceInfo)
198INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass)
199INITIALIZE_PASS_END(DeadCodeElimWrapperPass, "polly-dce",
200 "Polly - Remove dead iterations", false, false)
201

source code of polly/lib/Transform/DeadCodeElimination.cpp