Coverage Report

Created: 2017-08-18 19:41

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