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(TotalIdenticalWritesRemoved,
35           "Number of double writes removed in any SCoP");
36 STATISTIC(TotalRedundantWritesRemoved,
37           "Number of writes of same value removed in any SCoP");
38 STATISTIC(TotalStmtsRemoved, "Number of statements removed in any SCoP");
39 
40 /// Find the llvm::Value that is written by a MemoryAccess. Return nullptr if
41 /// there is no such unique value.
42 static Value *getWrittenScalar(MemoryAccess *WA) {
43   assert(WA->isWrite());
44 
45   if (WA->isOriginalAnyPHIKind()) {
46     Value *Result = nullptr;
47     for (auto Incoming : WA->getIncoming()) {
48       assert(Incoming.second);
49 
50       if (!Result) {
51         Result = Incoming.second;
52         continue;
53       }
54 
55       if (Result == Incoming.second)
56         continue;
57 
58       return nullptr;
59     }
60     return Result;
61   }
62 
63   return WA->getAccessInstruction();
64 }
65 
66 class Simplify : public ScopPass {
67 private:
68   /// The last/current SCoP that is/has been processed.
69   Scop *S;
70 
71   /// Number of double writes removed from this SCoP.
72   int IdenticalWritesRemoved = 0;
73 
74   /// Number of redundant writes removed from this SCoP.
75   int RedundantWritesRemoved = 0;
76 
77   /// Number of unnecessary statements removed from the SCoP.
78   int StmtsRemoved = 0;
79 
80   /// Return whether at least one simplification has been applied.
81   bool isModified() const {
82     return IdenticalWritesRemoved > 0 || RedundantWritesRemoved > 0 ||
83            StmtsRemoved > 0;
84   }
85 
86   MemoryAccess *getReadAccessForValue(ScopStmt *Stmt, llvm::Value *Val) {
87     if (!isa<Instruction>(Val))
88       return nullptr;
89 
90     for (auto *MA : *Stmt) {
91       if (!MA->isRead())
92         continue;
93       if (MA->getAccessValue() != Val)
94         continue;
95 
96       return MA;
97     }
98 
99     return nullptr;
100   }
101 
102   /// Return a write access that occurs between @p From and @p To.
103   ///
104   /// In region statements the order is ignored because we cannot predict it.
105   ///
106   /// @param Stmt    Statement of both writes.
107   /// @param From    Start looking after this access.
108   /// @param To      Stop looking at this access, with the access itself.
109   /// @param Targets Look for an access that may wrote to one of these elements.
110   ///
111   /// @return A write access between @p From and @p To that writes to at least
112   ///         one element in @p Targets.
113   MemoryAccess *hasWriteBetween(ScopStmt *Stmt, MemoryAccess *From,
114                                 MemoryAccess *To, isl::map Targets) {
115     auto TargetsSpace = give(isl_map_get_space(Targets.keep()));
116 
117     bool Started = Stmt->isRegionStmt();
118     for (auto *Acc : *Stmt) {
119       if (Acc->isLatestScalarKind())
120         continue;
121 
122       if (Stmt->isBlockStmt() && From == Acc) {
123         assert(!Started);
124         Started = true;
125         continue;
126       }
127       if (Stmt->isBlockStmt() && To == Acc) {
128         assert(Started);
129         return nullptr;
130       }
131       if (!Started)
132         continue;
133 
134       if (!Acc->isWrite())
135         continue;
136 
137       auto AccRel = give(Acc->getAccessRelation());
138       auto AccRelSpace = give(isl_map_get_space(AccRel.keep()));
139 
140       // Spaces being different means that they access different arrays.
141       if (isl_space_has_equal_tuples(TargetsSpace.keep(), AccRelSpace.keep()) ==
142           isl_bool_false)
143         continue;
144 
145       AccRel = give(isl_map_intersect_domain(AccRel.take(),
146                                              Acc->getStatement()->getDomain()));
147       AccRel = give(isl_map_intersect_params(AccRel.take(), S->getContext()));
148       auto CommonElt = give(isl_map_intersect(Targets.copy(), AccRel.copy()));
149       if (isl_map_is_empty(CommonElt.keep()) != isl_bool_true)
150         return Acc;
151     }
152     assert(Stmt->isRegionStmt() &&
153            "To must be encountered in block statements");
154     return nullptr;
155   }
156 
157   /// If there are two writes in the same statement that write the same value to
158   /// the same location, remove one of them.
159   ///
160   /// This currently handles only implicit writes (writes which logically occur
161   /// at the end of a statement when all StoreInst and LoadInst have been
162   /// executed), to avoid interference with other memory accesses.
163   ///
164   /// Two implicit writes have no defined order. It can be produced by DeLICM
165   /// when it determined that both write the same value.
166   void removeIdenticalWrites() {
167     for (auto &Stmt : *S) {
168       // Delay actual removal to not invalidate iterators.
169       SmallPtrSet<MemoryAccess *, 4> StoresToRemove;
170 
171       auto Domain = give(Stmt.getDomain());
172 
173       // TODO: This has quadratic runtime. Accesses could be grouped by
174       // getAccessValue() to avoid.
175       for (auto *WA1 : Stmt) {
176         if (!WA1->isMustWrite())
177           continue;
178         if (!WA1->isOriginalScalarKind())
179           continue;
180         if (StoresToRemove.count(WA1))
181           continue;
182 
183         auto *WrittenScalar1 = getWrittenScalar(WA1);
184         if (!WrittenScalar1)
185           continue;
186 
187         for (auto *WA2 : Stmt) {
188           if (WA1 == WA2)
189             continue;
190           if (!WA2->isMustWrite())
191             continue;
192           if (!WA2->isOriginalScalarKind())
193             continue;
194           if (StoresToRemove.count(WA2))
195             continue;
196 
197           auto *WrittenScalar2 = getWrittenScalar(WA2);
198           if (WrittenScalar1 != WrittenScalar2)
199             continue;
200 
201           auto AccRel1 = give(isl_map_intersect_domain(WA1->getAccessRelation(),
202                                                        Domain.copy()));
203           auto AccRel2 = give(isl_map_intersect_domain(WA2->getAccessRelation(),
204                                                        Domain.copy()));
205           if (isl_map_is_equal(AccRel1.keep(), AccRel2.keep()) != isl_bool_true)
206             continue;
207 
208           DEBUG(dbgs() << "Remove identical writes:\n");
209           DEBUG(dbgs() << "  First write  (kept)   : " << WA1 << '\n');
210           DEBUG(dbgs() << "  Second write (removed): " << WA2 << '\n');
211           StoresToRemove.insert(WA2);
212         }
213       }
214 
215       for (auto *WA : StoresToRemove) {
216         auto *Stmt = WA->getStatement();
217 
218         Stmt->removeSingleMemoryAccess(WA);
219 
220         IdenticalWritesRemoved++;
221         TotalIdenticalWritesRemoved++;
222       }
223     }
224   }
225 
226   /// Remove writes that just write the same value already stored in the
227   /// element.
228   void removeRedundantWrites() {
229     // Delay actual removal to not invalidate iterators.
230     SmallVector<MemoryAccess *, 8> StoresToRemove;
231 
232     for (auto &Stmt : *S) {
233       for (auto *WA : Stmt) {
234         if (!WA->isMustWrite())
235           continue;
236         if (!WA->isLatestArrayKind())
237           continue;
238         if (!isa<StoreInst>(WA->getAccessInstruction()))
239           continue;
240 
241         auto ReadingValue = WA->getAccessValue();
242         if (!ReadingValue)
243           continue;
244 
245         auto RA = getReadAccessForValue(&Stmt, ReadingValue);
246         if (!RA)
247           continue;
248         if (!RA->isLatestArrayKind())
249           continue;
250 
251         auto WARel = give(WA->getLatestAccessRelation());
252         WARel = give(isl_map_intersect_domain(WARel.take(),
253                                               WA->getStatement()->getDomain()));
254         WARel = give(isl_map_intersect_params(WARel.take(), S->getContext()));
255         auto RARel = give(RA->getLatestAccessRelation());
256         RARel = give(isl_map_intersect_domain(RARel.take(),
257                                               RA->getStatement()->getDomain()));
258         RARel = give(isl_map_intersect_params(RARel.take(), S->getContext()));
259 
260         if (isl_map_is_equal(RARel.keep(), WARel.keep()) != isl_bool_true) {
261           PairUnequalAccRels++;
262           DEBUG(dbgs() << "Not cleaning up " << WA
263                        << " because of unequal access relations:\n");
264           DEBUG(dbgs() << "      RA: " << RARel << "\n");
265           DEBUG(dbgs() << "      WA: " << WARel << "\n");
266           continue;
267         }
268 
269         if (auto *Conflicting = hasWriteBetween(&Stmt, RA, WA, WARel)) {
270           (void)Conflicting;
271           InBetweenStore++;
272           DEBUG(dbgs() << "Not cleaning up " << WA
273                        << " because there is another store to the same element "
274                           "between\n");
275           DEBUG(Conflicting->print(dbgs()));
276           continue;
277         }
278 
279         StoresToRemove.push_back(WA);
280       }
281     }
282 
283     for (auto *WA : StoresToRemove) {
284       auto Stmt = WA->getStatement();
285       auto AccRel = give(WA->getAccessRelation());
286       auto AccVal = WA->getAccessValue();
287 
288       DEBUG(dbgs() << "Cleanup of " << WA << ":\n");
289       DEBUG(dbgs() << "      Scalar: " << *AccVal << "\n");
290       DEBUG(dbgs() << "      AccRel: " << AccRel << "\n");
291       (void)AccVal;
292       (void)AccRel;
293 
294       Stmt->removeSingleMemoryAccess(WA);
295 
296       RedundantWritesRemoved++;
297       TotalRedundantWritesRemoved++;
298     }
299   }
300 
301   /// Remove statements without side effects.
302   void removeUnnecessayStmts() {
303     auto NumStmtsBefore = S->getSize();
304     S->simplifySCoP(true);
305     assert(NumStmtsBefore >= S->getSize());
306     StmtsRemoved = NumStmtsBefore - S->getSize();
307     DEBUG(dbgs() << "Removed " << StmtsRemoved << " (of " << NumStmtsBefore
308                  << ") statements\n");
309     TotalStmtsRemoved += StmtsRemoved;
310   }
311 
312   /// Print simplification statistics to @p OS.
313   void printStatistics(llvm::raw_ostream &OS, int Indent = 0) const {
314     OS.indent(Indent) << "Statistics {\n";
315     OS.indent(Indent + 4) << "Identical writes removed: "
316                           << IdenticalWritesRemoved << '\n';
317     OS.indent(Indent + 4) << "Redundant writes removed: "
318                           << RedundantWritesRemoved << "\n";
319     OS.indent(Indent + 4) << "Stmts removed: " << StmtsRemoved << "\n";
320     OS.indent(Indent) << "}\n";
321   }
322 
323   /// Print the current state of all MemoryAccesses to @p OS.
324   void printAccesses(llvm::raw_ostream &OS, int Indent = 0) const {
325     OS.indent(Indent) << "After accesses {\n";
326     for (auto &Stmt : *S) {
327       OS.indent(Indent + 4) << Stmt.getBaseName() << "\n";
328       for (auto *MA : Stmt)
329         MA->print(OS);
330     }
331     OS.indent(Indent) << "}\n";
332   }
333 
334 public:
335   static char ID;
336   explicit Simplify() : ScopPass(ID) {}
337 
338   virtual void getAnalysisUsage(AnalysisUsage &AU) const override {
339     AU.addRequiredTransitive<ScopInfoRegionPass>();
340     AU.setPreservesAll();
341   }
342 
343   virtual bool runOnScop(Scop &S) override {
344     // Reset statistics of last processed SCoP.
345     releaseMemory();
346 
347     // Prepare processing of this SCoP.
348     this->S = &S;
349     ScopsProcessed++;
350 
351     DEBUG(dbgs() << "Removing identical writes...\n");
352     removeIdenticalWrites();
353 
354     DEBUG(dbgs() << "Removing redundant writes...\n");
355     removeRedundantWrites();
356 
357     DEBUG(dbgs() << "Removing statements without side effects...\n");
358     removeUnnecessayStmts();
359 
360     if (isModified())
361       ScopsModified++;
362     DEBUG(dbgs() << "\nFinal Scop:\n");
363     DEBUG(S.print(dbgs()));
364 
365     return false;
366   }
367 
368   virtual void printScop(raw_ostream &OS, Scop &S) const override {
369     assert(&S == this->S &&
370            "Can only print analysis for the last processed SCoP");
371     printStatistics(OS);
372 
373     if (!isModified()) {
374       OS << "SCoP could not be simplified\n";
375       return;
376     }
377     printAccesses(OS);
378   }
379 
380   virtual void releaseMemory() override {
381     S = nullptr;
382     StmtsRemoved = 0;
383   }
384 };
385 
386 char Simplify::ID;
387 } // anonymous namespace
388 
389 Pass *polly::createSimplifyPass() { return new Simplify(); }
390 
391 INITIALIZE_PASS_BEGIN(Simplify, "polly-simplify", "Polly - Simplify", false,
392                       false)
393 INITIALIZE_PASS_END(Simplify, "polly-simplify", "Polly - Simplify", false,
394                     false)
395