1 //===------ Simplify.cpp ----------------------------------------*- C++ -*-===//
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 // Simplify a SCoP by removing unnecessary statements and accesses.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "polly/Simplify.h"
15 #include "polly/ScopInfo.h"
16 #include "polly/ScopPass.h"
17 #include "polly/Support/GICHelper.h"
18 #include "llvm/ADT/Statistic.h"
19 #include "llvm/Support/Debug.h"
20 #define DEBUG_TYPE "polly-simplify"
21 
22 using namespace llvm;
23 using namespace polly;
24 
25 namespace {
26 
27 STATISTIC(ScopsProcessed, "Number of SCoPs processed");
28 STATISTIC(ScopsModified, "Number of SCoPs simplified");
29 
30 STATISTIC(PairUnequalAccRels, "Number of Load-Store pairs NOT removed because "
31                               "of different access relations");
32 STATISTIC(InBetweenStore, "Number of Load-Store pairs NOT removed because "
33                           "there is another store between them");
34 STATISTIC(TotalRedundantWritesRemoved,
35           "Number of writes of same value removed in any SCoP");
36 STATISTIC(TotalStmtsRemoved, "Number of statements removed in any SCoP");
37 
38 class Simplify : public ScopPass {
39 private:
40   /// The last/current SCoP that is/has been processed.
41   Scop *S;
42 
43   /// Number of redundant writes removed from this SCoP.
44   int RedundantWritesRemoved = 0;
45 
46   /// Number of unnecessary statements removed from the SCoP.
47   int StmtsRemoved = 0;
48 
49   /// Return whether at least one simplification has been applied.
50   bool isModified() const {
51     return RedundantWritesRemoved > 0 || StmtsRemoved > 0;
52   }
53 
54   MemoryAccess *getReadAccessForValue(ScopStmt *Stmt, llvm::Value *Val) {
55     if (!isa<Instruction>(Val))
56       return nullptr;
57 
58     for (auto *MA : *Stmt) {
59       if (!MA->isRead())
60         continue;
61       if (MA->getAccessValue() != Val)
62         continue;
63 
64       return MA;
65     }
66 
67     return nullptr;
68   }
69 
70   /// Return a write access that occurs between @p From and @p To.
71   ///
72   /// In region statements the order is ignored because we cannot predict it.
73   ///
74   /// @param Stmt    Statement of both writes.
75   /// @param From    Start looking after this access.
76   /// @param To      Stop looking at this access, with the access itself.
77   /// @param Targets Look for an access that may wrote to one of these elements.
78   ///
79   /// @return A write access between @p From and @p To that writes to at least
80   ///         one element in @p Targets.
81   MemoryAccess *hasWriteBetween(ScopStmt *Stmt, MemoryAccess *From,
82                                 MemoryAccess *To, isl::map Targets) {
83     auto TargetsSpace = give(isl_map_get_space(Targets.keep()));
84 
85     bool Started = Stmt->isRegionStmt();
86     for (auto *Acc : *Stmt) {
87       if (Acc->isLatestScalarKind())
88         continue;
89 
90       if (Stmt->isBlockStmt() && From == Acc) {
91         assert(!Started);
92         Started = true;
93         continue;
94       }
95       if (Stmt->isBlockStmt() && To == Acc) {
96         assert(Started);
97         return nullptr;
98       }
99       if (!Started)
100         continue;
101 
102       if (!Acc->isWrite())
103         continue;
104 
105       auto AccRel = give(Acc->getAccessRelation());
106       auto AccRelSpace = give(isl_map_get_space(AccRel.keep()));
107 
108       // Spaces being different means that they access different arrays.
109       if (isl_space_has_equal_tuples(TargetsSpace.keep(), AccRelSpace.keep()) ==
110           isl_bool_false)
111         continue;
112 
113       AccRel = give(isl_map_intersect_domain(AccRel.take(),
114                                              Acc->getStatement()->getDomain()));
115       AccRel = give(isl_map_intersect_params(AccRel.take(), S->getContext()));
116       auto CommonElt = give(isl_map_intersect(Targets.copy(), AccRel.copy()));
117       if (isl_map_is_empty(CommonElt.keep()) != isl_bool_true)
118         return Acc;
119     }
120     assert(Stmt->isRegionStmt() &&
121            "To must be encountered in block statements");
122     return nullptr;
123   }
124 
125   /// Remove writes that just write the same value already stored in the
126   /// element.
127   void removeRedundantWrites() {
128     // Delay actual removal to not invalidate iterators.
129     SmallVector<MemoryAccess *, 8> StoresToRemove;
130 
131     for (auto &Stmt : *S) {
132       for (auto *WA : Stmt) {
133         if (!WA->isMustWrite())
134           continue;
135         if (!WA->isLatestArrayKind())
136           continue;
137         if (!isa<StoreInst>(WA->getAccessInstruction()))
138           continue;
139 
140         auto ReadingValue = WA->getAccessValue();
141         if (!ReadingValue)
142           continue;
143 
144         auto RA = getReadAccessForValue(&Stmt, ReadingValue);
145         if (!RA)
146           continue;
147         if (!RA->isLatestArrayKind())
148           continue;
149 
150         auto WARel = give(WA->getLatestAccessRelation());
151         WARel = give(isl_map_intersect_domain(WARel.take(),
152                                               WA->getStatement()->getDomain()));
153         WARel = give(isl_map_intersect_params(WARel.take(), S->getContext()));
154         auto RARel = give(RA->getLatestAccessRelation());
155         RARel = give(isl_map_intersect_domain(RARel.take(),
156                                               RA->getStatement()->getDomain()));
157         RARel = give(isl_map_intersect_params(RARel.take(), S->getContext()));
158 
159         if (isl_map_is_equal(RARel.keep(), WARel.keep()) != isl_bool_true) {
160           PairUnequalAccRels++;
161           DEBUG(dbgs() << "Not cleaning up " << WA
162                        << " because of unequal access relations:\n");
163           DEBUG(dbgs() << "      RA: " << RARel << "\n");
164           DEBUG(dbgs() << "      WA: " << WARel << "\n");
165           continue;
166         }
167 
168         if (auto *Conflicting = hasWriteBetween(&Stmt, RA, WA, WARel)) {
169           (void)Conflicting;
170           InBetweenStore++;
171           DEBUG(dbgs() << "Not cleaning up " << WA
172                        << " because there is another store to the same element "
173                           "between\n");
174           DEBUG(Conflicting->print(dbgs()));
175           continue;
176         }
177 
178         StoresToRemove.push_back(WA);
179       }
180     }
181 
182     for (auto *WA : StoresToRemove) {
183       auto Stmt = WA->getStatement();
184       auto AccRel = give(WA->getAccessRelation());
185       auto AccVal = WA->getAccessValue();
186 
187       DEBUG(dbgs() << "Cleanup of " << WA << ":\n");
188       DEBUG(dbgs() << "      Scalar: " << *AccVal << "\n");
189       DEBUG(dbgs() << "      AccRel: " << AccRel << "\n");
190       (void)AccVal;
191       (void)AccRel;
192 
193       Stmt->removeSingleMemoryAccess(WA);
194 
195       RedundantWritesRemoved++;
196       TotalRedundantWritesRemoved++;
197     }
198   }
199 
200   /// Remove statements without side effects.
201   void removeUnnecessayStmts() {
202     auto NumStmtsBefore = S->getSize();
203     S->simplifySCoP(true);
204     assert(NumStmtsBefore >= S->getSize());
205     StmtsRemoved = NumStmtsBefore - S->getSize();
206     DEBUG(dbgs() << "Removed " << StmtsRemoved << " (of " << NumStmtsBefore
207                  << ") statements\n");
208     TotalStmtsRemoved += StmtsRemoved;
209   }
210 
211   /// Print simplification statistics to @p OS.
212   void printStatistics(llvm::raw_ostream &OS, int Indent = 0) const {
213     OS.indent(Indent) << "Statistics {\n";
214     OS.indent(Indent + 4) << "Redundant writes removed: "
215                           << RedundantWritesRemoved << "\n";
216     OS.indent(Indent + 4) << "Stmts removed: " << StmtsRemoved << "\n";
217     OS.indent(Indent) << "}\n";
218   }
219 
220   /// Print the current state of all MemoryAccesses to @p OS.
221   void printAccesses(llvm::raw_ostream &OS, int Indent = 0) const {
222     OS.indent(Indent) << "After accesses {\n";
223     for (auto &Stmt : *S) {
224       OS.indent(Indent + 4) << Stmt.getBaseName() << "\n";
225       for (auto *MA : Stmt)
226         MA->print(OS);
227     }
228     OS.indent(Indent) << "}\n";
229   }
230 
231 public:
232   static char ID;
233   explicit Simplify() : ScopPass(ID) {}
234 
235   virtual void getAnalysisUsage(AnalysisUsage &AU) const override {
236     AU.addRequiredTransitive<ScopInfoRegionPass>();
237     AU.setPreservesAll();
238   }
239 
240   virtual bool runOnScop(Scop &S) override {
241     // Reset statistics of last processed SCoP.
242     releaseMemory();
243 
244     // Prepare processing of this SCoP.
245     this->S = &S;
246     ScopsProcessed++;
247 
248     DEBUG(dbgs() << "Removing redundant writes...\n");
249     removeRedundantWrites();
250 
251     DEBUG(dbgs() << "Removing statements without side effects...\n");
252     removeUnnecessayStmts();
253 
254     if (isModified())
255       ScopsModified++;
256     DEBUG(dbgs() << "\nFinal Scop:\n");
257     DEBUG(S.print(dbgs()));
258 
259     return false;
260   }
261 
262   virtual void printScop(raw_ostream &OS, Scop &S) const override {
263     assert(&S == this->S &&
264            "Can only print analysis for the last processed SCoP");
265     printStatistics(OS);
266 
267     if (!isModified()) {
268       OS << "SCoP could not be simplified\n";
269       return;
270     }
271     printAccesses(OS);
272   }
273 
274   virtual void releaseMemory() override {
275     S = nullptr;
276     StmtsRemoved = 0;
277   }
278 };
279 
280 char Simplify::ID;
281 } // anonymous namespace
282 
283 Pass *polly::createSimplifyPass() { return new Simplify(); }
284 
285 INITIALIZE_PASS_BEGIN(Simplify, "polly-simplify", "Polly - Simplify", false,
286                       false)
287 INITIALIZE_PASS_END(Simplify, "polly-simplify", "Polly - Simplify", false,
288                     false)
289