Coverage Report

Created: 2017-10-03 07:32

/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 "polly/Support/ISLTools.h"
20
#include "polly/Support/VirtualInstruction.h"
21
#include "llvm/ADT/Statistic.h"
22
#include "llvm/Support/Debug.h"
23
#define DEBUG_TYPE "polly-simplify"
24
25
using namespace llvm;
26
using namespace polly;
27
28
namespace {
29
30
#define TWO_STATISTICS(VARNAME, DESC)                                          \
31
  static llvm::Statistic VARNAME[2] = {                                        \
32
      {DEBUG_TYPE, #VARNAME "0", DESC " (first)", {0}, false},                 \
33
      {DEBUG_TYPE, #VARNAME "1", DESC " (second)", {0}, false}}
34
35
/// Number of max disjuncts we allow in removeOverwrites(). This is to avoid
36
/// that the analysis of accesses in a statement is becoming too complex. Chosen
37
/// to be relatively small because all the common cases should access only few
38
/// array elements per statement.
39
static int const SimplifyMaxDisjuncts = 4;
40
41
TWO_STATISTICS(ScopsProcessed, "Number of SCoPs processed");
42
TWO_STATISTICS(ScopsModified, "Number of SCoPs simplified");
43
44
TWO_STATISTICS(TotalOverwritesRemoved, "Number of removed overwritten writes");
45
TWO_STATISTICS(TotalWritesCoalesced, "Number of writes coalesced with another");
46
TWO_STATISTICS(TotalRedundantWritesRemoved,
47
               "Number of writes of same value removed in any SCoP");
48
TWO_STATISTICS(TotalEmptyPartialAccessesRemoved,
49
               "Number of empty partial accesses removed");
50
TWO_STATISTICS(TotalDeadAccessesRemoved, "Number of dead accesses removed");
51
TWO_STATISTICS(TotalDeadInstructionsRemoved,
52
               "Number of unused instructions removed");
53
TWO_STATISTICS(TotalStmtsRemoved, "Number of statements removed in any SCoP");
54
55
TWO_STATISTICS(NumValueWrites, "Number of scalar value writes after Simplify");
56
TWO_STATISTICS(
57
    NumValueWritesInLoops,
58
    "Number of scalar value writes nested in affine loops after Simplify");
59
TWO_STATISTICS(NumPHIWrites,
60
               "Number of scalar phi writes after the first simplification");
61
TWO_STATISTICS(
62
    NumPHIWritesInLoops,
63
    "Number of scalar phi writes nested in affine loops after Simplify");
64
TWO_STATISTICS(NumSingletonWrites, "Number of singleton writes after Simplify");
65
TWO_STATISTICS(
66
    NumSingletonWritesInLoops,
67
    "Number of singleton writes nested in affine loops after Simplify");
68
69
779
static bool isImplicitRead(MemoryAccess *MA) {
70
330
  return MA->isRead() && MA->isOriginalScalarKind();
71
779
}
72
73
805
static bool isExplicitAccess(MemoryAccess *MA) {
74
805
  return MA->isOriginalArrayKind();
75
805
}
76
77
779
static bool isImplicitWrite(MemoryAccess *MA) {
78
449
  return MA->isWrite() && MA->isOriginalScalarKind();
79
779
}
80
81
/// Like isl::union_map::add_map, but may also return an underapproximated
82
/// result if getting too complex.
83
///
84
/// This is implemented by adding disjuncts to the results until the limit is
85
/// reached.
86
static isl::union_map underapproximatedAddMap(isl::union_map UMap,
87
139
                                              isl::map Map) {
88
139
  if (
UMap.is_null() || 139
Map.is_null()139
)
89
0
    return {};
90
139
91
139
  isl::map PrevMap = UMap.extract_map(Map.get_space());
92
139
93
139
  // Fast path: If known that we cannot exceed the disjunct limit, just add
94
139
  // them.
95
139
  if (isl_map_n_basic_map(PrevMap.get()) + isl_map_n_basic_map(Map.get()) <=
96
139
      SimplifyMaxDisjuncts)
97
133
    return UMap.add_map(Map);
98
6
99
6
  isl::map Result = isl::map::empty(PrevMap.get_space());
100
24
  PrevMap.foreach_basic_map([&Result](isl::basic_map BMap) -> isl::stat {
101
24
    if (isl_map_n_basic_map(Result.get()) > SimplifyMaxDisjuncts)
102
0
      return isl::stat::error;
103
24
    Result = Result.unite(BMap);
104
24
    return isl::stat::ok;
105
24
  });
106
6
  Map.foreach_basic_map([&Result](isl::basic_map BMap) -> isl::stat {
107
6
    if (isl_map_n_basic_map(Result.get()) > SimplifyMaxDisjuncts)
108
0
      return isl::stat::error;
109
6
    Result = Result.unite(BMap);
110
6
    return isl::stat::ok;
111
6
  });
112
139
113
139
  isl::union_map UResult =
114
139
      UMap.subtract(isl::map::universe(PrevMap.get_space()));
115
139
  UResult.add_map(Result);
116
139
117
139
  return UResult;
118
139
}
119
120
class Simplify : public ScopPass {
121
private:
122
  /// The invocation id (if there are multiple instances in the pass manager's
123
  /// pipeline) to determine which statistics to update.
124
  int CallNo;
125
126
  /// The last/current SCoP that is/has been processed.
127
  Scop *S;
128
129
  /// Number of writes that are overwritten anyway.
130
  int OverwritesRemoved = 0;
131
132
  /// Number of combined writes.
133
  int WritesCoalesced = 0;
134
135
  /// Number of redundant writes removed from this SCoP.
136
  int RedundantWritesRemoved = 0;
137
138
  /// Number of writes with empty access domain removed.
139
  int EmptyPartialAccessesRemoved = 0;
140
141
  /// Number of unused accesses removed from this SCoP.
142
  int DeadAccessesRemoved = 0;
143
144
  /// Number of unused instructions removed from this SCoP.
145
  int DeadInstructionsRemoved = 0;
146
147
  /// Number of unnecessary statements removed from the SCoP.
148
  int StmtsRemoved = 0;
149
150
  /// Return whether at least one simplification has been applied.
151
81
  bool isModified() const {
152
71
    return OverwritesRemoved > 0 || WritesCoalesced > 0 ||
153
81
           
RedundantWritesRemoved > 061
||
EmptyPartialAccessesRemoved > 049
||
154
81
           
DeadAccessesRemoved > 047
||
DeadInstructionsRemoved > 036
||
155
30
           StmtsRemoved > 0;
156
81
  }
157
158
  /// Remove writes that are overwritten unconditionally later in the same
159
  /// statement.
160
  ///
161
  /// There must be no read of the same value between the write (that is to be
162
  /// removed) and the overwrite.
163
41
  void removeOverwrites() {
164
61
    for (auto &Stmt : *S) {
165
61
      isl::set Domain = Stmt.getDomain();
166
61
      isl::union_map WillBeOverwritten =
167
61
          isl::union_map::empty(S->getParamSpace());
168
61
169
61
      SmallVector<MemoryAccess *, 32> Accesses(getAccessesInOrder(Stmt));
170
61
171
61
      // Iterate in reverse order, so the overwrite comes before the write that
172
61
      // is to be removed.
173
214
      for (auto *MA : reverse(Accesses)) {
174
214
175
214
        // In region statements, the explicit accesses can be in blocks that are
176
214
        // can be executed in any order. We therefore process only the implicit
177
214
        // writes and stop after that.
178
214
        if (
Stmt.isRegionStmt() && 214
isExplicitAccess(MA)13
)
179
8
          break;
180
206
181
206
        auto AccRel = MA->getAccessRelation();
182
206
        AccRel = AccRel.intersect_domain(Domain);
183
206
        AccRel = AccRel.intersect_params(S->getContext());
184
206
185
206
        // If a value is read in-between, do not consider it as overwritten.
186
206
        if (
MA->isRead()206
) {
187
67
          // Invalidate all overwrites for the array it accesses to avoid too
188
67
          // complex isl sets.
189
67
          isl::map AccRelUniv = isl::map::universe(AccRel.get_space());
190
67
          WillBeOverwritten = WillBeOverwritten.subtract(AccRelUniv);
191
67
          continue;
192
67
        }
193
139
194
139
        // If all of a write's elements are overwritten, remove it.
195
139
        isl::union_map AccRelUnion = AccRel;
196
139
        if (
AccRelUnion.is_subset(WillBeOverwritten)139
) {
197
7
          DEBUG(dbgs() << "Removing " << MA
198
7
                       << " which will be overwritten anyway\n");
199
7
200
7
          Stmt.removeSingleMemoryAccess(MA);
201
7
          OverwritesRemoved++;
202
7
          TotalOverwritesRemoved[CallNo]++;
203
7
        }
204
139
205
139
        // Unconditional writes overwrite other values.
206
139
        if (
MA->isMustWrite()139
) {
207
139
          // Avoid too complex isl sets. If necessary, throw away some of the
208
139
          // knowledge.
209
139
          WillBeOverwritten =
210
139
              underapproximatedAddMap(WillBeOverwritten, AccRel);
211
139
        }
212
214
      }
213
61
    }
214
41
  }
215
216
  /// Combine writes that write the same value if possible.
217
  ///
218
  /// This function is able to combine:
219
  /// - Partial writes with disjoint domain.
220
  /// - Writes that write to the same array element.
221
  ///
222
  /// In all cases, both writes must write the same values.
223
41
  void coalesceWrites() {
224
61
    for (auto &Stmt : *S) {
225
61
      isl::set Domain = Stmt.getDomain().intersect_params(S->getContext());
226
61
227
61
      // We let isl do the lookup for the same-value condition. For this, we
228
61
      // wrap llvm::Value into an isl::set such that isl can do the lookup in
229
61
      // its hashtable implementation. llvm::Values are only compared within a
230
61
      // ScopStmt, so the map can be local to this scope. TODO: Refactor with
231
61
      // ZoneAlgorithm::makeValueSet()
232
61
      SmallDenseMap<Value *, isl::set> ValueSets;
233
132
      auto makeValueSet = [&ValueSets, this](Value *V) -> isl::set {
234
132
        assert(V);
235
132
        isl::set &Result = ValueSets[V];
236
132
        if (
Result.is_null()132
) {
237
90
          isl_ctx *Ctx = S->getIslCtx();
238
90
          std::string Name =
239
90
              getIslCompatibleName("Val", V, ValueSets.size() - 1,
240
90
                                   std::string(), UseInstructionNames);
241
90
          isl::id Id = give(isl_id_alloc(Ctx, Name.c_str(), V));
242
90
          Result = isl::set::universe(
243
90
              isl::space(Ctx, 0, 0).set_tuple_id(isl::dim::set, Id));
244
90
        }
245
132
        return Result;
246
132
      };
247
61
248
61
      // List of all eligible (for coalescing) writes of the future.
249
61
      // { [Domain[] -> Element[]] -> [Value[] -> MemoryAccess[]] }
250
61
      isl::union_map FutureWrites = isl::union_map::empty(S->getParamSpace());
251
61
252
61
      // Iterate over accesses from the last to the first.
253
61
      SmallVector<MemoryAccess *, 32> Accesses(getAccessesInOrder(Stmt));
254
207
      for (MemoryAccess *MA : reverse(Accesses)) {
255
207
        // In region statements, the explicit accesses can be in blocks that can
256
207
        // be executed in any order. We therefore process only the implicit
257
207
        // writes and stop after that.
258
207
        if (
Stmt.isRegionStmt() && 207
isExplicitAccess(MA)13
)
259
8
          break;
260
199
261
199
        // { Domain[] -> Element[] }
262
199
        isl::map AccRel =
263
199
            MA->getLatestAccessRelation().intersect_domain(Domain);
264
199
265
199
        // { [Domain[] -> Element[]] }
266
199
        isl::set AccRelWrapped = AccRel.wrap();
267
199
268
199
        // { Value[] }
269
199
        isl::set ValSet;
270
199
271
199
        if (
MA->isMustWrite() && 199
(MA->isOriginalScalarKind() ||
272
199
                                  
isa<StoreInst>(MA->getAccessInstruction())107
)) {
273
132
          // Normally, tryGetValueStored() should be used to determine which
274
132
          // element is written, but it can return nullptr; For PHI accesses,
275
132
          // getAccessValue() returns the PHI instead of the PHI's incoming
276
132
          // value. In this case, where we only compare values of a single
277
132
          // statement, this is fine, because within a statement, a PHI in a
278
132
          // successor block has always the same value as the incoming write. We
279
132
          // still preferably use the incoming value directly so we also catch
280
132
          // direct uses of that.
281
132
          Value *StoredVal = MA->tryGetValueStored();
282
132
          if (!StoredVal)
283
1
            StoredVal = MA->getAccessValue();
284
132
          ValSet = makeValueSet(StoredVal);
285
132
286
132
          // { Domain[] }
287
132
          isl::set AccDomain = AccRel.domain();
288
132
289
132
          // Parts of the statement's domain that is not written by this access.
290
132
          isl::set UndefDomain = Domain.subtract(AccDomain);
291
132
292
132
          // { Element[] }
293
132
          isl::set ElementUniverse =
294
132
              isl::set::universe(AccRel.get_space().range());
295
132
296
132
          // { Domain[] -> Element[] }
297
132
          isl::map UndefAnything =
298
132
              isl::map::from_domain_and_range(UndefDomain, ElementUniverse);
299
132
300
132
          // We are looking a compatible write access. The other write can
301
132
          // access these elements...
302
132
          isl::map AllowedAccesses = AccRel.unite(UndefAnything);
303
132
304
132
          // ... and must write the same value.
305
132
          // { [Domain[] -> Element[]] -> Value[] }
306
132
          isl::map Filter =
307
132
              isl::map::from_domain_and_range(AllowedAccesses.wrap(), ValSet);
308
132
309
132
          // Lookup future write that fulfills these conditions.
310
132
          // { [[Domain[] -> Element[]] -> Value[]] -> MemoryAccess[] }
311
132
          isl::union_map Filtered =
312
132
              FutureWrites.uncurry().intersect_domain(Filter.wrap());
313
132
314
132
          // Iterate through the candidates.
315
39
          Filtered.foreach_map([&, this](isl::map Map) -> isl::stat {
316
39
            MemoryAccess *OtherMA = (MemoryAccess *)Map.get_space()
317
39
                                        .get_tuple_id(isl::dim::out)
318
39
                                        .get_user();
319
39
320
39
            isl::map OtherAccRel =
321
39
                OtherMA->getLatestAccessRelation().intersect_domain(Domain);
322
39
323
39
            // The filter only guaranteed that some of OtherMA's accessed
324
39
            // elements are allowed. Verify that it only accesses allowed
325
39
            // elements. Otherwise, continue with the next candidate.
326
39
            if (!OtherAccRel.is_subset(AllowedAccesses).is_true())
327
32
              return isl::stat::ok;
328
7
329
7
            // The combined access relation.
330
7
            // { Domain[] -> Element[] }
331
7
            isl::map NewAccRel = AccRel.unite(OtherAccRel);
332
7
            simplify(NewAccRel);
333
7
334
7
            // Carry out the coalescing.
335
7
            Stmt.removeSingleMemoryAccess(MA);
336
7
            OtherMA->setNewAccessRelation(NewAccRel);
337
7
338
7
            // We removed MA, OtherMA takes its role.
339
7
            MA = OtherMA;
340
7
341
7
            TotalWritesCoalesced[CallNo]++;
342
7
            WritesCoalesced++;
343
7
344
7
            // Don't look for more candidates.
345
7
            return isl::stat::error;
346
7
          });
347
132
        }
348
199
349
199
        // Two writes cannot be coalesced if there is another access (to some of
350
199
        // the written elements) between them. Remove all visited write accesses
351
199
        // from the list of eligible writes. Don't just remove the accessed
352
199
        // elements, but any MemoryAccess that touches any of the invalidated
353
199
        // elements.
354
199
        SmallPtrSet<MemoryAccess *, 2> TouchedAccesses;
355
199
        FutureWrites.intersect_domain(AccRelWrapped)
356
86
            .foreach_map([&TouchedAccesses](isl::map Map) -> isl::stat {
357
86
              MemoryAccess *MA = (MemoryAccess *)Map.get_space()
358
86
                                     .range()
359
86
                                     .unwrap()
360
86
                                     .get_tuple_id(isl::dim::out)
361
86
                                     .get_user();
362
86
              TouchedAccesses.insert(MA);
363
86
              return isl::stat::ok;
364
86
            });
365
199
        isl::union_map NewFutureWrites =
366
199
            isl::union_map::empty(FutureWrites.get_space());
367
199
        FutureWrites.foreach_map([&TouchedAccesses, &NewFutureWrites](
368
121
                                     isl::map FutureWrite) -> isl::stat {
369
121
          MemoryAccess *MA = (MemoryAccess *)FutureWrite.get_space()
370
121
                                 .range()
371
121
                                 .unwrap()
372
121
                                 .get_tuple_id(isl::dim::out)
373
121
                                 .get_user();
374
121
          if (!TouchedAccesses.count(MA))
375
35
            NewFutureWrites = NewFutureWrites.add_map(FutureWrite);
376
121
          return isl::stat::ok;
377
121
        });
378
199
        FutureWrites = NewFutureWrites;
379
199
380
199
        if (
MA->isMustWrite() && 199
!ValSet.is_null()132
) {
381
132
          // { MemoryAccess[] }
382
132
          auto AccSet =
383
132
              isl::set::universe(isl::space(S->getIslCtx(), 0, 0)
384
132
                                     .set_tuple_id(isl::dim::set, MA->getId()));
385
132
386
132
          // { Val[] -> MemoryAccess[] }
387
132
          isl::map ValAccSet = isl::map::from_domain_and_range(ValSet, AccSet);
388
132
389
132
          // { [Domain[] -> Element[]] -> [Value[] -> MemoryAccess[]] }
390
132
          isl::map AccRelValAcc =
391
132
              isl::map::from_domain_and_range(AccRelWrapped, ValAccSet.wrap());
392
132
          FutureWrites = FutureWrites.add_map(AccRelValAcc);
393
132
        }
394
207
      }
395
61
    }
396
41
  }
397
398
  /// Remove writes that just write the same value already stored in the
399
  /// element.
400
41
  void removeRedundantWrites() {
401
61
    for (auto &Stmt : *S) {
402
61
      SmallDenseMap<Value *, isl::set> ValueSets;
403
202
      auto makeValueSet = [&ValueSets, this](Value *V) -> isl::set {
404
202
        assert(V);
405
202
        isl::set &Result = ValueSets[V];
406
202
        if (
Result.is_null()202
) {
407
115
          isl_ctx *Ctx = S->getIslCtx();
408
115
          std::string Name =
409
115
              getIslCompatibleName("Val", V, ValueSets.size() - 1,
410
115
                                   std::string(), UseInstructionNames);
411
115
          isl::id Id = give(isl_id_alloc(Ctx, Name.c_str(), V));
412
115
          Result = isl::set::universe(
413
115
              isl::space(Ctx, 0, 0).set_tuple_id(isl::dim::set, Id));
414
115
        }
415
202
        return Result;
416
202
      };
417
61
418
61
      isl::set Domain = Stmt.getDomain();
419
61
      Domain = Domain.intersect_params(S->getContext());
420
61
421
61
      // List of element reads that still have the same value while iterating
422
61
      // through the MemoryAccesses.
423
61
      // { [Domain[] -> Element[]] -> Val[] }
424
61
      isl::union_map Known = isl::union_map::empty(S->getParamSpace());
425
61
426
61
      SmallVector<MemoryAccess *, 32> Accesses(getAccessesInOrder(Stmt));
427
210
      for (MemoryAccess *MA : Accesses) {
428
210
        // Is the memory access in a defined order relative to the other
429
210
        // accesses? In region statements, only the first and the last accesses
430
210
        // have defined order. Execution of those in the middle may depend on
431
210
        // runtime conditions an therefore cannot be modified.
432
210
        bool IsOrdered =
433
23
            Stmt.isBlockStmt() || MA->isOriginalScalarKind() ||
434
14
            
(!S->getBoxedLoops().size() && 14
MA->getAccessInstruction()12
&&
435
14
             Stmt.getEntryBlock() == MA->getAccessInstruction()->getParent());
436
210
437
210
        isl::map AccRel = MA->getAccessRelation();
438
210
        AccRel = AccRel.intersect_domain(Domain);
439
210
        isl::set AccRelWrapped = AccRel.wrap();
440
210
441
210
        // Determine whether a write is redundant (stores only values that are
442
210
        // already present in the written array elements) and remove it if this
443
210
        // is the case.
444
210
        if (
IsOrdered && 210
MA->isMustWrite()202
&&
445
125
            (isa<StoreInst>(MA->getAccessInstruction()) ||
446
210
             
MA->isOriginalScalarKind()24
)) {
447
125
          Value *StoredVal = MA->tryGetValueStored();
448
125
          if (!StoredVal)
449
1
            StoredVal = MA->getAccessValue();
450
125
451
125
          if (
StoredVal125
) {
452
125
            // Lookup in the set of known values.
453
125
            isl::map AccRelStoredVal = isl::map::from_domain_and_range(
454
125
                AccRelWrapped, makeValueSet(StoredVal));
455
125
            if (
isl::union_map(AccRelStoredVal).is_subset(Known)125
) {
456
14
              DEBUG(dbgs() << "Cleanup of " << MA << ":\n");
457
14
              DEBUG(dbgs() << "      Scalar: " << *StoredVal << "\n");
458
14
              DEBUG(dbgs() << "      AccRel: " << AccRel << "\n");
459
14
460
14
              Stmt.removeSingleMemoryAccess(MA);
461
14
462
14
              RedundantWritesRemoved++;
463
14
              TotalRedundantWritesRemoved[CallNo]++;
464
14
            }
465
125
          }
466
125
        }
467
210
468
210
        // Update the know values set.
469
210
        if (
MA->isRead()210
) {
470
77
          // Loaded values are the currently known values of the array element
471
77
          // it was loaded from.
472
77
          Value *LoadedVal = MA->getAccessValue();
473
77
          if (
LoadedVal && 77
IsOrdered77
) {
474
77
            isl::map AccRelVal = isl::map::from_domain_and_range(
475
77
                AccRelWrapped, makeValueSet(LoadedVal));
476
77
477
77
            Known = Known.add_map(AccRelVal);
478
77
          }
479
210
        } else 
if (133
MA->isWrite()133
) {
480
133
          // Remove (possibly) overwritten values from the known elements set.
481
133
          // We remove all elements of the accessed array to avoid too complex
482
133
          // isl sets.
483
133
          isl::set AccRelUniv = isl::set::universe(AccRelWrapped.get_space());
484
133
          Known = Known.subtract_domain(AccRelUniv);
485
133
486
133
          // At this point, we could add the written value of must-writes.
487
133
          // However, writing same values is already handled by
488
133
          // coalesceWrites().
489
133
        }
490
210
      }
491
61
    }
492
41
  }
493
494
  /// Remove statements without side effects.
495
41
  void removeUnnecessaryStmts() {
496
41
    auto NumStmtsBefore = S->getSize();
497
41
    S->simplifySCoP(true);
498
41
    assert(NumStmtsBefore >= S->getSize());
499
41
    StmtsRemoved = NumStmtsBefore - S->getSize();
500
41
    DEBUG(dbgs() << "Removed " << StmtsRemoved << " (of " << NumStmtsBefore
501
41
                 << ") statements\n");
502
41
    TotalStmtsRemoved[CallNo] += StmtsRemoved;
503
41
  }
504
505
  /// Remove accesses that have an empty domain.
506
41
  void removeEmptyPartialAccesses() {
507
61
    for (ScopStmt &Stmt : *S) {
508
61
      // Defer the actual removal to not invalidate iterators.
509
61
      SmallVector<MemoryAccess *, 8> DeferredRemove;
510
61
511
225
      for (MemoryAccess *MA : Stmt) {
512
225
        if (!MA->isWrite())
513
77
          continue;
514
148
515
148
        isl::map AccRel = MA->getAccessRelation();
516
148
        if (!AccRel.is_empty().is_true())
517
147
          continue;
518
1
519
1
        
DEBUG1
(dbgs() << "Removing " << MA
520
1
                     << " because it's a partial access that never occurs\n");
521
1
        DeferredRemove.push_back(MA);
522
1
      }
523
61
524
1
      for (MemoryAccess *MA : DeferredRemove) {
525
1
        Stmt.removeSingleMemoryAccess(MA);
526
1
        EmptyPartialAccessesRemoved++;
527
1
        TotalEmptyPartialAccessesRemoved[CallNo]++;
528
1
      }
529
61
    }
530
41
  }
531
532
  /// Mark all reachable instructions and access, and sweep those that are not
533
  /// reachable.
534
41
  void markAndSweep(LoopInfo *LI) {
535
41
    DenseSet<MemoryAccess *> UsedMA;
536
41
    DenseSet<VirtualInstruction> UsedInsts;
537
41
538
41
    // Get all reachable instructions and accesses.
539
41
    markReachable(S, LI, UsedInsts, UsedMA);
540
41
541
41
    // Remove all non-reachable accesses.
542
41
    // We need get all MemoryAccesses first, in order to not invalidate the
543
41
    // iterators when removing them.
544
41
    SmallVector<MemoryAccess *, 64> AllMAs;
545
41
    for (ScopStmt &Stmt : *S)
546
61
      AllMAs.append(Stmt.begin(), Stmt.end());
547
41
548
196
    for (MemoryAccess *MA : AllMAs) {
549
196
      if (UsedMA.count(MA))
550
175
        continue;
551
21
      
DEBUG21
(dbgs() << "Removing " << MA << " because its value is not used\n");
552
21
      ScopStmt *Stmt = MA->getStatement();
553
21
      Stmt->removeSingleMemoryAccess(MA);
554
21
555
21
      DeadAccessesRemoved++;
556
21
      TotalDeadAccessesRemoved[CallNo]++;
557
21
    }
558
41
559
41
    // Remove all non-reachable instructions.
560
61
    for (ScopStmt &Stmt : *S) {
561
61
      // Note that for region statements, we can only remove the non-terminator
562
61
      // instructions of the entry block. All other instructions are not in the
563
61
      // instructions list, but implicitly always part of the statement.
564
61
565
61
      SmallVector<Instruction *, 32> AllInsts(Stmt.insts_begin(),
566
61
                                              Stmt.insts_end());
567
61
      SmallVector<Instruction *, 32> RemainInsts;
568
61
569
204
      for (Instruction *Inst : AllInsts) {
570
204
        auto It = UsedInsts.find({&Stmt, Inst});
571
204
        if (
It == UsedInsts.end()204
) {
572
39
          DEBUG(dbgs() << "Removing "; Inst->print(dbgs());
573
39
                dbgs() << " because it is not used\n");
574
39
          DeadInstructionsRemoved++;
575
39
          TotalDeadInstructionsRemoved[CallNo]++;
576
39
          continue;
577
39
        }
578
165
579
165
        RemainInsts.push_back(Inst);
580
165
581
165
        // If instructions appear multiple times, keep only the first.
582
165
        UsedInsts.erase(It);
583
165
      }
584
61
585
61
      // Set the new instruction list to be only those we did not remove.
586
61
      Stmt.setInstructions(RemainInsts);
587
61
    }
588
41
  }
589
590
  /// Print simplification statistics to @p OS.
591
40
  void printStatistics(llvm::raw_ostream &OS, int Indent = 0) const {
592
40
    OS.indent(Indent) << "Statistics {\n";
593
40
    OS.indent(Indent + 4) << "Overwrites removed: " << OverwritesRemoved
594
40
                          << '\n';
595
40
    OS.indent(Indent + 4) << "Partial writes coalesced: " << WritesCoalesced
596
40
                          << "\n";
597
40
    OS.indent(Indent + 4) << "Redundant writes removed: "
598
40
                          << RedundantWritesRemoved << "\n";
599
40
    OS.indent(Indent + 4) << "Accesses with empty domains removed: "
600
40
                          << EmptyPartialAccessesRemoved << "\n";
601
40
    OS.indent(Indent + 4) << "Dead accesses removed: " << DeadAccessesRemoved
602
40
                          << '\n';
603
40
    OS.indent(Indent + 4) << "Dead instructions removed: "
604
40
                          << DeadInstructionsRemoved << '\n';
605
40
    OS.indent(Indent + 4) << "Stmts removed: " << StmtsRemoved << "\n";
606
40
    OS.indent(Indent) << "}\n";
607
40
  }
608
609
  /// Print the current state of all MemoryAccesses to @p OS.
610
25
  void printAccesses(llvm::raw_ostream &OS, int Indent = 0) const {
611
25
    OS.indent(Indent) << "After accesses {\n";
612
23
    for (auto &Stmt : *S) {
613
23
      OS.indent(Indent + 4) << Stmt.getBaseName() << "\n";
614
23
      for (auto *MA : Stmt)
615
38
        MA->print(OS);
616
23
    }
617
25
    OS.indent(Indent) << "}\n";
618
25
  }
619
620
public:
621
  static char ID;
622
41
  explicit Simplify(int CallNo = 0) : ScopPass(ID), CallNo(CallNo) {}
623
624
41
  virtual void getAnalysisUsage(AnalysisUsage &AU) const override {
625
41
    AU.addRequiredTransitive<ScopInfoRegionPass>();
626
41
    AU.addRequired<LoopInfoWrapperPass>();
627
41
    AU.setPreservesAll();
628
41
  }
629
630
41
  virtual bool runOnScop(Scop &S) override {
631
41
    // Reset statistics of last processed SCoP.
632
41
    releaseMemory();
633
41
    assert(!isModified());
634
41
635
41
    // Prepare processing of this SCoP.
636
41
    this->S = &S;
637
41
    ScopsProcessed[CallNo]++;
638
41
639
41
    DEBUG(dbgs() << "Removing partial writes that never happen...\n");
640
41
    removeEmptyPartialAccesses();
641
41
642
41
    DEBUG(dbgs() << "Removing overwrites...\n");
643
41
    removeOverwrites();
644
41
645
41
    DEBUG(dbgs() << "Coalesce partial writes...\n");
646
41
    coalesceWrites();
647
41
648
41
    DEBUG(dbgs() << "Removing redundant writes...\n");
649
41
    removeRedundantWrites();
650
41
651
41
    DEBUG(dbgs() << "Cleanup unused accesses...\n");
652
41
    LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
653
41
    markAndSweep(LI);
654
41
655
41
    DEBUG(dbgs() << "Removing statements without side effects...\n");
656
41
    removeUnnecessaryStmts();
657
41
658
41
    if (isModified())
659
26
      ScopsModified[CallNo]++;
660
41
    DEBUG(dbgs() << "\nFinal Scop:\n");
661
41
    DEBUG(dbgs() << S);
662
41
663
41
    auto ScopStats = S.getStatistics();
664
41
    NumValueWrites[CallNo] += ScopStats.NumValueWrites;
665
41
    NumValueWritesInLoops[CallNo] += ScopStats.NumValueWritesInLoops;
666
41
    NumPHIWrites[CallNo] += ScopStats.NumPHIWrites;
667
41
    NumPHIWritesInLoops[CallNo] += ScopStats.NumPHIWritesInLoops;
668
41
    NumSingletonWrites[CallNo] += ScopStats.NumSingletonWrites;
669
41
    NumSingletonWritesInLoops[CallNo] += ScopStats.NumSingletonWritesInLoops;
670
41
671
41
    return false;
672
41
  }
673
674
40
  virtual void printScop(raw_ostream &OS, Scop &S) const override {
675
40
    assert(&S == this->S &&
676
40
           "Can only print analysis for the last processed SCoP");
677
40
    printStatistics(OS);
678
40
679
40
    if (
!isModified()40
) {
680
15
      OS << "SCoP could not be simplified\n";
681
15
      return;
682
15
    }
683
25
    printAccesses(OS);
684
25
  }
685
686
177
  virtual void releaseMemory() override {
687
177
    S = nullptr;
688
177
689
177
    OverwritesRemoved = 0;
690
177
    WritesCoalesced = 0;
691
177
    RedundantWritesRemoved = 0;
692
177
    EmptyPartialAccessesRemoved = 0;
693
177
    DeadAccessesRemoved = 0;
694
177
    DeadInstructionsRemoved = 0;
695
177
    StmtsRemoved = 0;
696
177
  }
697
};
698
699
char Simplify::ID;
700
} // anonymous namespace
701
702
namespace polly {
703
212
SmallVector<MemoryAccess *, 32> getAccessesInOrder(ScopStmt &Stmt) {
704
212
705
212
  SmallVector<MemoryAccess *, 32> Accesses;
706
212
707
212
  for (MemoryAccess *MemAcc : Stmt)
708
779
    
if (779
isImplicitRead(MemAcc)779
)
709
88
      Accesses.push_back(MemAcc);
710
212
711
212
  for (MemoryAccess *MemAcc : Stmt)
712
779
    
if (779
isExplicitAccess(MemAcc)779
)
713
614
      Accesses.push_back(MemAcc);
714
212
715
212
  for (MemoryAccess *MemAcc : Stmt)
716
779
    
if (779
isImplicitWrite(MemAcc)779
)
717
77
      Accesses.push_back(MemAcc);
718
212
719
212
  return Accesses;
720
212
}
721
} // namespace polly
722
723
0
Pass *polly::createSimplifyPass(int CallNo) { return new Simplify(CallNo); }
724
725
41.7k
INITIALIZE_PASS_BEGIN41.7k
(Simplify, "polly-simplify", "Polly - Simplify", false,
726
41.7k
                      false)
727
41.7k
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
728
41.7k
INITIALIZE_PASS_END(Simplify, "polly-simplify", "Polly - Simplify", false,
729
                    false)