Coverage Report

Created: 2017-04-27 19:33

/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 "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
4
  bool isModified() const {
51
2
    return RedundantWritesRemoved > 0 || StmtsRemoved > 0;
52
4
  }
53
54
2
  MemoryAccess *getReadAccessForValue(ScopStmt *Stmt, llvm::Value *Val) {
55
2
    if (!isa<Instruction>(Val))
56
1
      return nullptr;
57
2
58
1
    
for (auto *MA : *Stmt) 1
{1
59
1
      if (!MA->isRead())
60
0
        continue;
61
1
      
if (1
MA->getAccessValue() != Val1
)
62
0
        continue;
63
1
64
1
      return MA;
65
1
    }
66
1
67
0
    return nullptr;
68
1
  }
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
1
                                MemoryAccess *To, isl::map Targets) {
83
1
    auto TargetsSpace = give(isl_map_get_space(Targets.keep()));
84
1
85
1
    bool Started = Stmt->isRegionStmt();
86
2
    for (auto *Acc : *Stmt) {
87
2
      if (Acc->isLatestScalarKind())
88
0
        continue;
89
2
90
2
      
if (2
Stmt->isBlockStmt() && 2
From == Acc2
)
{1
91
1
        assert(!Started);
92
1
        Started = true;
93
1
        continue;
94
1
      }
95
1
      
if (1
Stmt->isBlockStmt() && 1
To == Acc1
)
{1
96
1
        assert(Started);
97
1
        return nullptr;
98
1
      }
99
0
      
if (0
!Started0
)
100
0
        continue;
101
0
102
0
      
if (0
!Acc->isWrite()0
)
103
0
        continue;
104
0
105
0
      auto AccRel = give(Acc->getAccessRelation());
106
0
      auto AccRelSpace = give(isl_map_get_space(AccRel.keep()));
107
0
108
0
      // Spaces being different means that they access different arrays.
109
0
      if (isl_space_has_equal_tuples(TargetsSpace.keep(), AccRelSpace.keep()) ==
110
0
          isl_bool_false)
111
0
        continue;
112
0
113
0
      AccRel = give(isl_map_intersect_domain(AccRel.take(),
114
0
                                             Acc->getStatement()->getDomain()));
115
0
      AccRel = give(isl_map_intersect_params(AccRel.take(), S->getContext()));
116
0
      auto CommonElt = give(isl_map_intersect(Targets.copy(), AccRel.copy()));
117
0
      if (isl_map_is_empty(CommonElt.keep()) != isl_bool_true)
118
0
        return Acc;
119
0
    }
120
0
    assert(Stmt->isRegionStmt() &&
121
0
           "To must be encountered in block statements");
122
0
    return nullptr;
123
1
  }
124
125
  /// Remove writes that just write the same value already stored in the
126
  /// element.
127
2
  void removeRedundantWrites() {
128
2
    // Delay actual removal to not invalidate iterators.
129
2
    SmallVector<MemoryAccess *, 8> StoresToRemove;
130
2
131
2
    for (auto &Stmt : *S) {
132
3
      for (auto *WA : Stmt) {
133
3
        if (!WA->isMustWrite())
134
1
          continue;
135
2
        
if (2
!WA->isLatestArrayKind()2
)
136
0
          continue;
137
2
        
if (2
!isa<StoreInst>(WA->getAccessInstruction())2
)
138
0
          continue;
139
2
140
2
        auto ReadingValue = WA->getAccessValue();
141
2
        if (!ReadingValue)
142
0
          continue;
143
2
144
2
        auto RA = getReadAccessForValue(&Stmt, ReadingValue);
145
2
        if (!RA)
146
1
          continue;
147
1
        
if (1
!RA->isLatestArrayKind()1
)
148
0
          continue;
149
1
150
1
        auto WARel = give(WA->getLatestAccessRelation());
151
1
        WARel = give(isl_map_intersect_domain(WARel.take(),
152
1
                                              WA->getStatement()->getDomain()));
153
1
        WARel = give(isl_map_intersect_params(WARel.take(), S->getContext()));
154
1
        auto RARel = give(RA->getLatestAccessRelation());
155
1
        RARel = give(isl_map_intersect_domain(RARel.take(),
156
1
                                              RA->getStatement()->getDomain()));
157
1
        RARel = give(isl_map_intersect_params(RARel.take(), S->getContext()));
158
1
159
1
        if (
isl_map_is_equal(RARel.keep(), WARel.keep()) != isl_bool_true1
)
{0
160
0
          PairUnequalAccRels++;
161
0
          DEBUG(dbgs() << "Not cleaning up " << WA
162
0
                       << " because of unequal access relations:\n");
163
0
          DEBUG(dbgs() << "      RA: " << RARel << "\n");
164
0
          DEBUG(dbgs() << "      WA: " << WARel << "\n");
165
0
          continue;
166
0
        }
167
1
168
1
        
if (auto *1
Conflicting1
= hasWriteBetween(&Stmt, RA, WA, WARel))
{0
169
0
          InBetweenStore++;
170
0
          DEBUG(dbgs() << "Not cleaning up " << WA
171
0
                       << " because there is another store to the same element "
172
0
                          "between\n");
173
0
          DEBUG(Conflicting->print(dbgs()));
174
0
          continue;
175
0
        }
176
1
177
1
        StoresToRemove.push_back(WA);
178
1
      }
179
2
    }
180
2
181
1
    for (auto *WA : StoresToRemove) {
182
1
      auto Stmt = WA->getStatement();
183
1
      auto AccRel = give(WA->getAccessRelation());
184
1
      auto AccVal = WA->getAccessValue();
185
1
186
1
      DEBUG(dbgs() << "Cleanup of " << WA << ":\n");
187
1
      DEBUG(dbgs() << "      Scalar: " << *AccVal << "\n");
188
1
      DEBUG(dbgs() << "      AccRel: " << AccRel << "\n");
189
1
190
1
      Stmt->removeSingleMemoryAccess(WA);
191
1
192
1
      RedundantWritesRemoved++;
193
1
      TotalRedundantWritesRemoved++;
194
1
    }
195
2
  }
196
197
  /// Remove statements without side effects.
198
2
  void removeUnnecessayStmts() {
199
2
    auto NumStmtsBefore = S->getSize();
200
2
    S->simplifySCoP(true);
201
2
    assert(NumStmtsBefore >= S->getSize());
202
2
    StmtsRemoved = NumStmtsBefore - S->getSize();
203
2
    DEBUG(dbgs() << "Removed " << StmtsRemoved << " (of " << NumStmtsBefore
204
2
                 << ") statements\n");
205
2
    TotalStmtsRemoved += StmtsRemoved;
206
2
  }
207
208
  /// Print simplification statistics to @p OS.
209
2
  void printStatistics(llvm::raw_ostream &OS, int Indent = 0) const {
210
2
    OS.indent(Indent) << "Statistics {\n";
211
2
    OS.indent(Indent + 4) << "Redundant writes removed: "
212
2
                          << RedundantWritesRemoved << "\n";
213
2
    OS.indent(Indent + 4) << "Stmts removed: " << StmtsRemoved << "\n";
214
2
    OS.indent(Indent) << "}\n";
215
2
  }
216
217
  /// Print the current state of all MemoryAccesses to @p OS.
218
1
  void printAccesses(llvm::raw_ostream &OS, int Indent = 0) const {
219
1
    OS.indent(Indent) << "After accesses {\n";
220
0
    for (auto &Stmt : *S) {
221
0
      OS.indent(Indent + 4) << Stmt.getBaseName() << "\n";
222
0
      for (auto *MA : Stmt)
223
0
        MA->print(OS);
224
0
    }
225
1
    OS.indent(Indent) << "}\n";
226
1
  }
227
228
public:
229
  static char ID;
230
2
  explicit Simplify() : ScopPass(ID) {}
231
232
2
  virtual void getAnalysisUsage(AnalysisUsage &AU) const override {
233
2
    AU.addRequiredTransitive<ScopInfoRegionPass>();
234
2
    AU.setPreservesAll();
235
2
  }
236
237
2
  virtual bool runOnScop(Scop &S) override {
238
2
    // Reset statistics of last processed SCoP.
239
2
    releaseMemory();
240
2
241
2
    // Prepare processing of this SCoP.
242
2
    this->S = &S;
243
2
    ScopsProcessed++;
244
2
245
2
    DEBUG(dbgs() << "Removing redundant writes...\n");
246
2
    removeRedundantWrites();
247
2
248
2
    DEBUG(dbgs() << "Removing statements without side effects...\n");
249
2
    removeUnnecessayStmts();
250
2
251
2
    if (isModified())
252
1
      ScopsModified++;
253
2
    DEBUG(dbgs() << "\nFinal Scop:\n");
254
2
    DEBUG(S.print(dbgs()));
255
2
256
2
    return false;
257
2
  }
258
259
2
  virtual void printScop(raw_ostream &OS, Scop &S) const override {
260
2
    assert(&S == this->S &&
261
2
           "Can only print analysis for the last processed SCoP");
262
2
    printStatistics(OS);
263
2
264
2
    if (
!isModified()2
)
{1
265
1
      OS << "SCoP could not be simplified\n";
266
1
      return;
267
1
    }
268
1
    printAccesses(OS);
269
1
  }
270
271
8
  virtual void releaseMemory() override {
272
8
    S = nullptr;
273
8
    StmtsRemoved = 0;
274
8
  }
275
};
276
277
char Simplify::ID;
278
} // anonymous namespace
279
280
0
Pass *polly::createSimplifyPass() { return new Simplify(); }
281
282
39.7k
INITIALIZE_PASS_BEGIN39.7k
(Simplify, "polly-simplify", "Polly - Simplify", false,39.7k
283
39.7k
                      false)
284
39.7k
INITIALIZE_PASS_END(Simplify, "polly-simplify", "Polly - Simplify", false,
285
                    false)