Coverage Report

Created: 2017-06-28 17:40

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/Transform/Simplify.cpp
Line
Count
Source (jump to first uncovered line)
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 "polly/Support/ISLOStream.h"
19
#include "llvm/ADT/Statistic.h"
20
#include "llvm/Support/Debug.h"
21
#define DEBUG_TYPE "polly-simplify"
22
23
using namespace llvm;
24
using namespace polly;
25
26
namespace {
27
28
STATISTIC(ScopsProcessed, "Number of SCoPs processed");
29
STATISTIC(ScopsModified, "Number of SCoPs simplified");
30
31
STATISTIC(PairUnequalAccRels, "Number of Load-Store pairs NOT removed because "
32
                              "of different access relations");
33
STATISTIC(InBetweenStore, "Number of Load-Store pairs NOT removed because "
34
                          "there is another store between them");
35
STATISTIC(TotalOverwritesRemoved, "Number of removed overwritten writes");
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
37
static bool isImplicitRead(MemoryAccess *MA) {
41
12
  return MA->isRead() && MA->isOriginalScalarKind();
42
37
}
43
44
37
static bool isExplicitAccess(MemoryAccess *MA) {
45
37
  return MA->isOriginalArrayKind();
46
37
}
47
48
37
static bool isImplicitWrite(MemoryAccess *MA) {
49
25
  return MA->isWrite() && MA->isOriginalScalarKind();
50
37
}
51
52
/// Return a vector that contains MemoryAccesses in the order in
53
/// which they are executed.
54
///
55
/// The order is:
56
/// - Implicit reads (BlockGenerator::generateScalarLoads)
57
/// - Explicit reads and writes (BlockGenerator::generateArrayLoad,
58
///   BlockGenerator::generateArrayStore)
59
///   - In block statements, the accesses are in order in which their
60
///     instructions are executed.
61
///   - In region statements, that order of execution is not predictable at
62
///     compile-time.
63
/// - Implicit writes (BlockGenerator::generateScalarStores)
64
///   The order in which implicit writes are executed relative to each other is
65
///   undefined.
66
16
static SmallVector<MemoryAccess *, 32> getAccessesInOrder(ScopStmt &Stmt) {
67
16
68
16
  SmallVector<MemoryAccess *, 32> Accesses;
69
16
70
16
  for (MemoryAccess *MemAcc : Stmt)
71
37
    
if (37
isImplicitRead(MemAcc)37
)
72
9
      Accesses.push_back(MemAcc);
73
16
74
16
  for (MemoryAccess *MemAcc : Stmt)
75
37
    
if (37
isExplicitAccess(MemAcc)37
)
76
20
      Accesses.push_back(MemAcc);
77
16
78
16
  for (MemoryAccess *MemAcc : Stmt)
79
37
    
if (37
isImplicitWrite(MemAcc)37
)
80
8
      Accesses.push_back(MemAcc);
81
16
82
16
  return Accesses;
83
16
}
84
85
class Simplify : public ScopPass {
86
private:
87
  /// The last/current SCoP that is/has been processed.
88
  Scop *S;
89
90
  /// Number of writes that are overwritten anyway.
91
  int OverwritesRemoved = 0;
92
93
  /// Number of redundant writes removed from this SCoP.
94
  int RedundantWritesRemoved = 0;
95
96
  /// Number of unnecessary statements removed from the SCoP.
97
  int StmtsRemoved = 0;
98
99
  /// Return whether at least one simplification has been applied.
100
18
  bool isModified() const {
101
8
    return OverwritesRemoved > 0 || RedundantWritesRemoved > 0 ||
102
4
           StmtsRemoved > 0;
103
18
  }
104
105
11
  MemoryAccess *getReadAccessForValue(ScopStmt *Stmt, llvm::Value *Val) {
106
11
    if (!isa<Instruction>(Val))
107
5
      return nullptr;
108
11
109
14
    
for (auto *MA : *Stmt) 6
{14
110
14
      if (!MA->isRead())
111
5
        continue;
112
9
      
if (9
MA->getAccessValue() != Val9
)
113
5
        continue;
114
9
115
4
      return MA;
116
9
    }
117
6
118
2
    return nullptr;
119
6
  }
120
121
  /// Return a write access that occurs between @p From and @p To.
122
  ///
123
  /// In region statements the order is ignored because we cannot predict it.
124
  ///
125
  /// @param Stmt    Statement of both writes.
126
  /// @param From    Start looking after this access.
127
  /// @param To      Stop looking at this access, with the access itself.
128
  /// @param Targets Look for an access that may wrote to one of these elements.
129
  ///
130
  /// @return A write access between @p From and @p To that writes to at least
131
  ///         one element in @p Targets.
132
  MemoryAccess *hasWriteBetween(ScopStmt *Stmt, MemoryAccess *From,
133
2
                                MemoryAccess *To, isl::map Targets) {
134
2
    auto TargetsSpace = Targets.get_space();
135
2
136
2
    bool Started = Stmt->isRegionStmt();
137
2
    auto Accesses = getAccessesInOrder(*Stmt);
138
4
    for (auto *Acc : Accesses) {
139
4
      if (Acc->isLatestScalarKind())
140
0
        continue;
141
4
142
4
      
if (4
Stmt->isBlockStmt() && 4
From == Acc4
)
{2
143
2
        assert(!Started);
144
2
        Started = true;
145
2
        continue;
146
2
      }
147
2
      
if (2
Stmt->isBlockStmt() && 2
To == Acc2
)
{2
148
2
        assert(Started);
149
2
        return nullptr;
150
2
      }
151
0
      
if (0
!Started0
)
152
0
        continue;
153
0
154
0
      
if (0
!Acc->isWrite()0
)
155
0
        continue;
156
0
157
0
      auto AccRel = give(Acc->getAccessRelation());
158
0
      auto AccRelSpace = AccRel.get_space();
159
0
160
0
      // Spaces being different means that they access different arrays.
161
0
      if (!TargetsSpace.has_equal_tuples(AccRelSpace))
162
0
        continue;
163
0
164
0
      AccRel = AccRel.intersect_domain(give(Acc->getStatement()->getDomain()));
165
0
      AccRel = AccRel.intersect_params(give(S->getContext()));
166
0
      auto CommonElt = Targets.intersect(AccRel);
167
0
      if (!CommonElt.is_empty())
168
0
        return Acc;
169
0
    }
170
0
    assert(Stmt->isRegionStmt() &&
171
0
           "To must be encountered in block statements");
172
0
    return nullptr;
173
2
  }
174
175
  /// Remove writes that are overwritten unconditionally later in the same
176
  /// statement.
177
  ///
178
  /// There must be no read of the same value between the write (that is to be
179
  /// removed) and the overwrite.
180
9
  void removeOverwrites() {
181
14
    for (auto &Stmt : *S) {
182
14
      auto Domain = give(Stmt.getDomain());
183
14
      isl::union_map WillBeOverwritten =
184
14
          isl::union_map::empty(give(S->getParamSpace()));
185
14
186
14
      SmallVector<MemoryAccess *, 32> Accesses(getAccessesInOrder(Stmt));
187
14
188
14
      // Iterate in reverse order, so the overwrite comes before the write that
189
14
      // is to be removed.
190
33
      for (auto *MA : reverse(Accesses)) {
191
33
192
33
        // In region statements, the explicit accesses can be in blocks that are
193
33
        // can be executed in any order. We therefore process only the implicit
194
33
        // writes and stop after that.
195
33
        if (
Stmt.isRegionStmt() && 33
isExplicitAccess(MA)0
)
196
0
          break;
197
33
198
33
        auto AccRel = give(MA->getAccessRelation());
199
33
        AccRel = AccRel.intersect_domain(Domain);
200
33
        AccRel = AccRel.intersect_params(give(S->getContext()));
201
33
202
33
        // If a value is read in-between, do not consider it as overwritten.
203
33
        if (
MA->isRead()33
)
{10
204
10
          WillBeOverwritten = WillBeOverwritten.subtract(AccRel);
205
10
          continue;
206
10
        }
207
33
208
33
        // If all of a write's elements are overwritten, remove it.
209
23
        isl::union_map AccRelUnion = AccRel;
210
23
        if (
AccRelUnion.is_subset(WillBeOverwritten)23
)
{7
211
7
          DEBUG(dbgs() << "Removing " << MA
212
7
                       << " which will be overwritten anyway\n");
213
7
214
7
          Stmt.removeSingleMemoryAccess(MA);
215
7
          OverwritesRemoved++;
216
7
          TotalOverwritesRemoved++;
217
7
        }
218
23
219
23
        // Unconditional writes overwrite other values.
220
23
        if (MA->isMustWrite())
221
23
          WillBeOverwritten = WillBeOverwritten.add_map(AccRel);
222
23
      }
223
14
    }
224
9
  }
225
226
  /// Remove writes that just write the same value already stored in the
227
  /// element.
228
9
  void removeRedundantWrites() {
229
9
    // Delay actual removal to not invalidate iterators.
230
9
    SmallVector<MemoryAccess *, 8> StoresToRemove;
231
9
232
14
    for (auto &Stmt : *S) {
233
26
      for (auto *WA : Stmt) {
234
26
        if (!WA->isMustWrite())
235
10
          continue;
236
16
        
if (16
!WA->isLatestArrayKind()16
)
237
1
          continue;
238
15
        
if (15
!isa<StoreInst>(WA->getAccessInstruction())15
)
239
4
          continue;
240
15
241
11
        auto ReadingValue = WA->getAccessValue();
242
11
        if (!ReadingValue)
243
0
          continue;
244
11
245
11
        auto RA = getReadAccessForValue(&Stmt, ReadingValue);
246
11
        if (!RA)
247
7
          continue;
248
4
        
if (4
!RA->isLatestArrayKind()4
)
249
2
          continue;
250
4
251
2
        auto WARel = give(WA->getLatestAccessRelation());
252
2
        WARel = WARel.intersect_domain(give(WA->getStatement()->getDomain()));
253
2
        WARel = WARel.intersect_params(give(S->getContext()));
254
2
        auto RARel = give(RA->getLatestAccessRelation());
255
2
        RARel = RARel.intersect_domain(give(RA->getStatement()->getDomain()));
256
2
        RARel = RARel.intersect_params(give(S->getContext()));
257
2
258
2
        if (
!RARel.is_equal(WARel)2
)
{0
259
0
          PairUnequalAccRels++;
260
0
          DEBUG(dbgs() << "Not cleaning up " << WA
261
0
                       << " because of unequal access relations:\n");
262
0
          DEBUG(dbgs() << "      RA: " << RARel << "\n");
263
0
          DEBUG(dbgs() << "      WA: " << WARel << "\n");
264
0
          continue;
265
0
        }
266
2
267
2
        
if (auto *2
Conflicting2
= hasWriteBetween(&Stmt, RA, WA, WARel))
{0
268
0
          (void)Conflicting;
269
0
          InBetweenStore++;
270
0
          DEBUG(dbgs() << "Not cleaning up " << WA
271
0
                       << " because there is another store to the same element "
272
0
                          "between\n");
273
0
          DEBUG(Conflicting->print(dbgs()));
274
0
          continue;
275
0
        }
276
2
277
2
        StoresToRemove.push_back(WA);
278
2
      }
279
14
    }
280
9
281
2
    for (auto *WA : StoresToRemove) {
282
2
      auto Stmt = WA->getStatement();
283
2
      auto AccRel = give(WA->getAccessRelation());
284
2
      auto AccVal = WA->getAccessValue();
285
2
286
2
      DEBUG(dbgs() << "Cleanup of " << WA << ":\n");
287
2
      DEBUG(dbgs() << "      Scalar: " << *AccVal << "\n");
288
2
      DEBUG(dbgs() << "      AccRel: " << AccRel << "\n");
289
2
      (void)AccVal;
290
2
      (void)AccRel;
291
2
292
2
      Stmt->removeSingleMemoryAccess(WA);
293
2
294
2
      RedundantWritesRemoved++;
295
2
      TotalRedundantWritesRemoved++;
296
2
    }
297
9
  }
298
299
  /// Remove statements without side effects.
300
9
  void removeUnnecessayStmts() {
301
9
    auto NumStmtsBefore = S->getSize();
302
9
    S->simplifySCoP(true);
303
9
    assert(NumStmtsBefore >= S->getSize());
304
9
    StmtsRemoved = NumStmtsBefore - S->getSize();
305
9
    DEBUG(dbgs() << "Removed " << StmtsRemoved << " (of " << NumStmtsBefore
306
9
                 << ") statements\n");
307
9
    TotalStmtsRemoved += StmtsRemoved;
308
9
  }
309
310
  /// Print simplification statistics to @p OS.
311
9
  void printStatistics(llvm::raw_ostream &OS, int Indent = 0) const {
312
9
    OS.indent(Indent) << "Statistics {\n";
313
9
    OS.indent(Indent + 4) << "Overwrites removed: " << OverwritesRemoved
314
9
                          << '\n';
315
9
    OS.indent(Indent + 4) << "Redundant writes removed: "
316
9
                          << RedundantWritesRemoved << "\n";
317
9
    OS.indent(Indent + 4) << "Stmts removed: " << StmtsRemoved << "\n";
318
9
    OS.indent(Indent) << "}\n";
319
9
  }
320
321
  /// Print the current state of all MemoryAccesses to @p OS.
322
7
  void printAccesses(llvm::raw_ostream &OS, int Indent = 0) const {
323
7
    OS.indent(Indent) << "After accesses {\n";
324
9
    for (auto &Stmt : *S) {
325
9
      OS.indent(Indent + 4) << Stmt.getBaseName() << "\n";
326
9
      for (auto *MA : Stmt)
327
15
        MA->print(OS);
328
9
    }
329
7
    OS.indent(Indent) << "}\n";
330
7
  }
331
332
public:
333
  static char ID;
334
9
  explicit Simplify() : ScopPass(ID) {}
335
336
9
  virtual void getAnalysisUsage(AnalysisUsage &AU) const override {
337
9
    AU.addRequiredTransitive<ScopInfoRegionPass>();
338
9
    AU.setPreservesAll();
339
9
  }
340
341
9
  virtual bool runOnScop(Scop &S) override {
342
9
    // Reset statistics of last processed SCoP.
343
9
    releaseMemory();
344
9
345
9
    // Prepare processing of this SCoP.
346
9
    this->S = &S;
347
9
    ScopsProcessed++;
348
9
349
9
    DEBUG(dbgs() << "Removing overwrites...\n");
350
9
    removeOverwrites();
351
9
352
9
    DEBUG(dbgs() << "Removing redundant writes...\n");
353
9
    removeRedundantWrites();
354
9
355
9
    DEBUG(dbgs() << "Removing statements without side effects...\n");
356
9
    removeUnnecessayStmts();
357
9
358
9
    if (isModified())
359
7
      ScopsModified++;
360
9
    DEBUG(dbgs() << "\nFinal Scop:\n");
361
9
    DEBUG(S.print(dbgs()));
362
9
363
9
    return false;
364
9
  }
365
366
9
  virtual void printScop(raw_ostream &OS, Scop &S) const override {
367
9
    assert(&S == this->S &&
368
9
           "Can only print analysis for the last processed SCoP");
369
9
    printStatistics(OS);
370
9
371
9
    if (
!isModified()9
)
{2
372
2
      OS << "SCoP could not be simplified\n";
373
2
      return;
374
2
    }
375
7
    printAccesses(OS);
376
7
  }
377
378
36
  virtual void releaseMemory() override {
379
36
    S = nullptr;
380
36
381
36
    OverwritesRemoved = 0;
382
36
    RedundantWritesRemoved = 0;
383
36
    StmtsRemoved = 0;
384
36
  }
385
};
386
387
char Simplify::ID;
388
} // anonymous namespace
389
390
0
Pass *polly::createSimplifyPass() { return new Simplify(); }
391
392
41.0k
INITIALIZE_PASS_BEGIN41.0k
(Simplify, "polly-simplify", "Polly - Simplify", false,41.0k
393
41.0k
                      false)
394
41.0k
INITIALIZE_PASS_END(Simplify, "polly-simplify", "Polly - Simplify", false,
395
                    false)