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