lib/Transform/Simplify.cpp

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