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/Dependences.h"
36 #include "polly/LinkAllPasses.h"
37 #include "polly/ScopInfo.h"
38 #include "llvm/Support/CommandLine.h"
39 #include "isl/set.h"
40 #include "isl/map.h"
41 #include "isl/union_map.h"
42 
43 using namespace llvm;
44 using namespace polly;
45 
46 namespace {
47 
48 cl::opt<int> DCEPreciseSteps(
49     "polly-dce-precise-steps",
50     cl::desc("The number of precise steps between two approximating "
51              "iterations. (A value of -1 schedules another approximation stage "
52              "before the actual dead code elimination."),
53     cl::ZeroOrMore, cl::init(-1));
54 
55 class DeadCodeElim : public ScopPass {
56 public:
57   static char ID;
58   explicit DeadCodeElim() : ScopPass(ID) {}
59 
60   virtual bool runOnScop(Scop &S);
61 
62   void printScop(llvm::raw_ostream &OS) const;
63   void getAnalysisUsage(AnalysisUsage &AU) const;
64 
65 private:
66   isl_union_set *getLastWrites(isl_union_map *Writes, isl_union_map *Schedule);
67   bool eliminateDeadCode(Scop &S, int PreciseSteps);
68 };
69 }
70 
71 char DeadCodeElim::ID = 0;
72 
73 /// Return the set of iterations that contains the last write for each location.
74 isl_union_set *DeadCodeElim::getLastWrites(__isl_take isl_union_map *Writes,
75                                            __isl_take isl_union_map *Schedule) {
76   isl_union_map *WriteIterations = isl_union_map_reverse(Writes);
77   isl_union_map *WriteTimes =
78       isl_union_map_apply_range(WriteIterations, isl_union_map_copy(Schedule));
79 
80   isl_union_map *LastWriteTimes = isl_union_map_lexmax(WriteTimes);
81   isl_union_map *LastWriteIterations = isl_union_map_apply_range(
82       LastWriteTimes, isl_union_map_reverse(Schedule));
83 
84   isl_union_set *Live = isl_union_map_range(LastWriteIterations);
85   return isl_union_set_coalesce(Live);
86 }
87 
88 /// Performs polyhedral dead iteration elimination by:
89 /// o Assuming that the last write to each location is live.
90 /// o Following each RAW dependency from a live iteration backwards and adding
91 ///   that iteration to the live set.
92 ///
93 /// To ensure the set of live iterations does not get too complex we always
94 /// combine a certain number of precise steps with one approximating step that
95 /// simplifies the life set with an affine hull.
96 bool DeadCodeElim::eliminateDeadCode(Scop &S, int PreciseSteps) {
97   Dependences *D = &getAnalysis<Dependences>();
98 
99   if (!D->hasValidDependences())
100     return false;
101 
102   isl_union_set *Live = this->getLastWrites(S.getWrites(), S.getSchedule());
103   isl_union_map *Dep =
104       D->getDependences(Dependences::TYPE_RAW | Dependences::TYPE_RED);
105   Dep = isl_union_map_reverse(Dep);
106 
107   if (PreciseSteps == -1)
108     Live = isl_union_set_affine_hull(Live);
109 
110   isl_union_set *OriginalDomain = S.getDomains();
111   int Steps = 0;
112   while (true) {
113     isl_union_set *Extra;
114     Steps++;
115 
116     Extra =
117         isl_union_set_apply(isl_union_set_copy(Live), isl_union_map_copy(Dep));
118 
119     if (isl_union_set_is_subset(Extra, Live)) {
120       isl_union_set_free(Extra);
121       break;
122     }
123 
124     Live = isl_union_set_union(Live, Extra);
125 
126     if (Steps > PreciseSteps) {
127       Steps = 0;
128       Live = isl_union_set_affine_hull(Live);
129     }
130 
131     Live = isl_union_set_intersect(Live, isl_union_set_copy(OriginalDomain));
132   }
133   isl_union_map_free(Dep);
134   isl_union_set_free(OriginalDomain);
135 
136   return S.restrictDomains(isl_union_set_coalesce(Live));
137 }
138 
139 bool DeadCodeElim::runOnScop(Scop &S) {
140   return eliminateDeadCode(S, DCEPreciseSteps);
141 }
142 
143 void DeadCodeElim::printScop(raw_ostream &OS) const {}
144 
145 void DeadCodeElim::getAnalysisUsage(AnalysisUsage &AU) const {
146   ScopPass::getAnalysisUsage(AU);
147   AU.addRequired<Dependences>();
148 }
149 
150 Pass *polly::createDeadCodeElimPass() { return new DeadCodeElim(); }
151 
152 INITIALIZE_PASS_BEGIN(DeadCodeElim, "polly-dce",
153                       "Polly - Remove dead iterations", false, false)
154 INITIALIZE_PASS_DEPENDENCY(Dependences)
155 INITIALIZE_PASS_DEPENDENCY(ScopInfo)
156 INITIALIZE_PASS_END(DeadCodeElim, "polly-dce", "Polly - Remove dead iterations",
157                     false, false)
158