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/Options.h"
38 #include "polly/ScopInfo.h"
39 #include "llvm/Support/CommandLine.h"
40 #include "isl/flow.h"
41 #include "isl/map.h"
42 #include "isl/set.h"
43 #include "isl/union_map.h"
44 #include "isl/union_set.h"
45 
46 #include "isl-noexceptions.h"
47 
48 using namespace llvm;
49 using namespace polly;
50 
51 namespace {
52 
53 cl::opt<int> DCEPreciseSteps(
54     "polly-dce-precise-steps",
55     cl::desc("The number of precise steps between two approximating "
56              "iterations. (A value of -1 schedules another approximation stage "
57              "before the actual dead code elimination."),
58     cl::ZeroOrMore, cl::init(-1), cl::cat(PollyCategory));
59 
60 class DeadCodeElim : public ScopPass {
61 public:
62   static char ID;
63   explicit DeadCodeElim() : ScopPass(ID) {}
64 
65   /// Remove dead iterations from the schedule of @p S.
66   bool runOnScop(Scop &S) override;
67 
68   /// Register all analyses and transformation required.
69   void getAnalysisUsage(AnalysisUsage &AU) const override;
70 
71 private:
72   /// Return the set of live iterations.
73   ///
74   /// The set of live iterations are all iterations that write to memory and for
75   /// which we can not prove that there will be a later write that _must_
76   /// overwrite the same memory location and is consequently the only one that
77   /// is visible after the execution of the SCoP.
78   ///
79   isl::union_set getLiveOut(Scop &S);
80   bool eliminateDeadCode(Scop &S, int PreciseSteps);
81 };
82 } // namespace
83 
84 char DeadCodeElim::ID = 0;
85 
86 // To compute the live outs, we compute for the data-locations that are
87 // must-written to the last statement that touches these locations. On top of
88 // this we add all statements that perform may-write accesses.
89 //
90 // We could be more precise by removing may-write accesses for which we know
91 // that they are overwritten by a must-write after. However, at the moment the
92 // only may-writes we introduce access the full (unbounded) array, such that
93 // bounded write accesses can not overwrite all of the data-locations. As
94 // this means may-writes are in the current situation always live, there is
95 // no point in trying to remove them from the live-out set.
96 isl::union_set DeadCodeElim::getLiveOut(Scop &S) {
97   isl::union_map Schedule = isl::manage(S.getSchedule());
98   isl::union_map MustWrites = isl::manage(S.getMustWrites());
99   isl::union_map WriteIterations = MustWrites.reverse();
100   isl::union_map WriteTimes = WriteIterations.apply_range(Schedule);
101 
102   isl::union_map LastWriteTimes = WriteTimes.lexmax();
103   isl::union_map LastWriteIterations =
104       LastWriteTimes.apply_range(Schedule.reverse());
105 
106   isl::union_set Live = LastWriteIterations.range();
107   isl::union_map MayWrites = isl::manage(S.getMayWrites());
108   Live = Live.unite(MayWrites.domain());
109   return Live.coalesce();
110 }
111 
112 /// Performs polyhedral dead iteration elimination by:
113 /// o Assuming that the last write to each location is live.
114 /// o Following each RAW dependency from a live iteration backwards and adding
115 ///   that iteration to the live set.
116 ///
117 /// To ensure the set of live iterations does not get too complex we always
118 /// combine a certain number of precise steps with one approximating step that
119 /// simplifies the life set with an affine hull.
120 bool DeadCodeElim::eliminateDeadCode(Scop &S, int PreciseSteps) {
121   DependenceInfo &DI = getAnalysis<DependenceInfo>();
122   const Dependences &D = DI.getDependences(Dependences::AL_Statement);
123 
124   if (!D.hasValidDependences())
125     return false;
126 
127   isl::union_set Live = getLiveOut(S);
128   isl::union_map Dep = isl::manage(
129       D.getDependences(Dependences::TYPE_RAW | Dependences::TYPE_RED));
130   Dep = Dep.reverse();
131 
132   if (PreciseSteps == -1)
133     Live = Live.affine_hull();
134 
135   isl::union_set OriginalDomain = isl::manage(S.getDomains());
136   int Steps = 0;
137   while (true) {
138     Steps++;
139 
140     isl::union_set Extra = Live.apply(Dep);
141 
142     if (Extra.is_subset(Live))
143       break;
144 
145     Live = Live.unite(Extra);
146 
147     if (Steps > PreciseSteps) {
148       Steps = 0;
149       Live = Live.affine_hull();
150     }
151 
152     Live = Live.intersect(OriginalDomain);
153   }
154 
155   Live = Live.coalesce();
156 
157   bool Changed = S.restrictDomains(Live.copy());
158 
159   // FIXME: We can probably avoid the recomputation of all dependences by
160   // updating them explicitly.
161   if (Changed)
162     DI.recomputeDependences(Dependences::AL_Statement);
163   return Changed;
164 }
165 
166 bool DeadCodeElim::runOnScop(Scop &S) {
167   return eliminateDeadCode(S, DCEPreciseSteps);
168 }
169 
170 void DeadCodeElim::getAnalysisUsage(AnalysisUsage &AU) const {
171   ScopPass::getAnalysisUsage(AU);
172   AU.addRequired<DependenceInfo>();
173 }
174 
175 Pass *polly::createDeadCodeElimPass() { return new DeadCodeElim(); }
176 
177 INITIALIZE_PASS_BEGIN(DeadCodeElim, "polly-dce",
178                       "Polly - Remove dead iterations", false, false)
179 INITIALIZE_PASS_DEPENDENCY(DependenceInfo)
180 INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass)
181 INITIALIZE_PASS_END(DeadCodeElim, "polly-dce", "Polly - Remove dead iterations",
182                     false, false)
183