lib/Transform/Simplify.cpp

   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/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 STATISTIC(ScopsProcessed, "Number of SCoPs processed");
  30 STATISTIC(ScopsModified, "Number of SCoPs simplified");
  31
  32 STATISTIC(PairUnequalAccRels, "Number of Load-Store pairs NOT removed because "
  33                               "of different access relations");
  34 STATISTIC(InBetweenStore, "Number of Load-Store pairs NOT removed because "
  35                           "there is another store between them");
  36 STATISTIC(TotalOverwritesRemoved, "Number of removed overwritten writes");
  37 STATISTIC(TotalRedundantWritesRemoved,
  38           "Number of writes of same value removed in any SCoP");
  39 STATISTIC(TotalDeadAccessesRemoved, "Number of dead accesses removed");
  40 STATISTIC(TotalDeadInstructionsRemoved,
  41           "Number of unused instructions removed");
  42 STATISTIC(TotalStmtsRemoved, "Number of statements removed in any SCoP");
  43
  44 static bool isImplicitRead(MemoryAccess *MA) {
  45   return MA->isRead() && MA->isOriginalScalarKind();
  46 }
  47
  48 static bool isExplicitAccess(MemoryAccess *MA) {
  49   return MA->isOriginalArrayKind();
  50 }
  51
  52 static bool isImplicitWrite(MemoryAccess *MA) {
  53   return MA->isWrite() && MA->isOriginalScalarKind();
  54 }
  55
  56 /// Return a vector that contains MemoryAccesses in the order in
  57 /// which they are executed.
  58 ///
  59 /// The order is:
  60 /// - Implicit reads (BlockGenerator::generateScalarLoads)
  61 /// - Explicit reads and writes (BlockGenerator::generateArrayLoad,
  62 ///   BlockGenerator::generateArrayStore)
  63 ///   - In block statements, the accesses are in order in which their
  64 ///     instructions are executed.
  65 ///   - In region statements, that order of execution is not predictable at
  66 ///     compile-time.
  67 /// - Implicit writes (BlockGenerator::generateScalarStores)
  68 ///   The order in which implicit writes are executed relative to each other is
  69 ///   undefined.
  70 static SmallVector<MemoryAccess *, 32> getAccessesInOrder(ScopStmt &Stmt) {
  71
  72   SmallVector<MemoryAccess *, 32> Accesses;
  73
  74   for (MemoryAccess *MemAcc : Stmt)
  75     if (isImplicitRead(MemAcc))
  76       Accesses.push_back(MemAcc);
  77
  78   for (MemoryAccess *MemAcc : Stmt)
  79     if (isExplicitAccess(MemAcc))
  80       Accesses.push_back(MemAcc);
  81
  82   for (MemoryAccess *MemAcc : Stmt)
  83     if (isImplicitWrite(MemAcc))
  84       Accesses.push_back(MemAcc);
  85
  86   return Accesses;
  87 }
  88
  89 class Simplify : public ScopPass {
  90 private:
  91   /// The last/current SCoP that is/has been processed.
  92   Scop *S;
  93
  94   /// Number of writes that are overwritten anyway.
  95   int OverwritesRemoved = 0;
  96
  97   /// Number of redundant writes removed from this SCoP.
  98   int RedundantWritesRemoved = 0;
  99
 100   /// Number of unused accesses removed from this SCoP.
 101   int DeadAccessesRemoved = 0;
 102
 103   /// Number of unused instructions removed from this SCoP.
 104   int DeadInstructionsRemoved = 0;
 105
 106   /// Number of unnecessary statements removed from the SCoP.
 107   int StmtsRemoved = 0;
 108
 109   /// Return whether at least one simplification has been applied.
 110   bool isModified() const {
 111     return OverwritesRemoved > 0 || RedundantWritesRemoved > 0 ||
 112            DeadAccessesRemoved > 0 || DeadInstructionsRemoved > 0 ||
 113            StmtsRemoved > 0;
 114   }
 115
 116   MemoryAccess *getReadAccessForValue(ScopStmt *Stmt, llvm::Value *Val) {
 117     if (!isa<Instruction>(Val))
 118       return nullptr;
 119
 120     for (auto *MA : *Stmt) {
 121       if (!MA->isRead())
 122         continue;
 123       if (MA->getAccessValue() != Val)
 124         continue;
 125
 126       return MA;
 127     }
 128
 129     return nullptr;
 130   }
 131
 132   /// Return a write access that occurs between @p From and @p To.
 133   ///
 134   /// In region statements the order is ignored because we cannot predict it.
 135   ///
 136   /// @param Stmt    Statement of both writes.
 137   /// @param From    Start looking after this access.
 138   /// @param To      Stop looking at this access, with the access itself.
 139   /// @param Targets Look for an access that may wrote to one of these elements.
 140   ///
 141   /// @return A write access between @p From and @p To that writes to at least
 142   ///         one element in @p Targets.
 143   MemoryAccess *hasWriteBetween(ScopStmt *Stmt, MemoryAccess *From,
 144                                 MemoryAccess *To, isl::map Targets) {
 145     auto TargetsSpace = Targets.get_space();
 146
 147     bool Started = Stmt->isRegionStmt();
 148     auto Accesses = getAccessesInOrder(*Stmt);
 149     for (auto *Acc : Accesses) {
 150       if (Acc->isLatestScalarKind())
 151         continue;
 152
 153       if (Stmt->isBlockStmt() && From == Acc) {
 154         assert(!Started);
 155         Started = true;
 156         continue;
 157       }
 158       if (Stmt->isBlockStmt() && To == Acc) {
 159         assert(Started);
 160         return nullptr;
 161       }
 162       if (!Started)
 163         continue;
 164
 165       if (!Acc->isWrite())
 166         continue;
 167
 168       auto AccRel = give(Acc->getAccessRelation());
 169       auto AccRelSpace = AccRel.get_space();
 170
 171       // Spaces being different means that they access different arrays.
 172       if (!TargetsSpace.has_equal_tuples(AccRelSpace))
 173         continue;
 174
 175       AccRel = AccRel.intersect_domain(give(Acc->getStatement()->getDomain()));
 176       AccRel = AccRel.intersect_params(give(S->getContext()));
 177       auto CommonElt = Targets.intersect(AccRel);
 178       if (!CommonElt.is_empty())
 179         return Acc;
 180     }
 181     assert(Stmt->isRegionStmt() &&
 182            "To must be encountered in block statements");
 183     return nullptr;
 184   }
 185
 186   /// Remove writes that are overwritten unconditionally later in the same
 187   /// statement.
 188   ///
 189   /// There must be no read of the same value between the write (that is to be
 190   /// removed) and the overwrite.
 191   void removeOverwrites() {
 192     for (auto &Stmt : *S) {
 193       auto Domain = give(Stmt.getDomain());
 194       isl::union_map WillBeOverwritten =
 195           isl::union_map::empty(give(S->getParamSpace()));
 196
 197       SmallVector<MemoryAccess *, 32> Accesses(getAccessesInOrder(Stmt));
 198
 199       // Iterate in reverse order, so the overwrite comes before the write that
 200       // is to be removed.
 201       for (auto *MA : reverse(Accesses)) {
 202
 203         // In region statements, the explicit accesses can be in blocks that are
 204         // can be executed in any order. We therefore process only the implicit
 205         // writes and stop after that.
 206         if (Stmt.isRegionStmt() && isExplicitAccess(MA))
 207           break;
 208
 209         auto AccRel = give(MA->getAccessRelation());
 210         AccRel = AccRel.intersect_domain(Domain);
 211         AccRel = AccRel.intersect_params(give(S->getContext()));
 212
 213         // If a value is read in-between, do not consider it as overwritten.
 214         if (MA->isRead()) {
 215           WillBeOverwritten = WillBeOverwritten.subtract(AccRel);
 216           continue;
 217         }
 218
 219         // If all of a write's elements are overwritten, remove it.
 220         isl::union_map AccRelUnion = AccRel;
 221         if (AccRelUnion.is_subset(WillBeOverwritten)) {
 222           DEBUG(dbgs() << "Removing " << MA
 223                        << " which will be overwritten anyway\n");
 224
 225           Stmt.removeSingleMemoryAccess(MA);
 226           OverwritesRemoved++;
 227           TotalOverwritesRemoved++;
 228         }
 229
 230         // Unconditional writes overwrite other values.
 231         if (MA->isMustWrite())
 232           WillBeOverwritten = WillBeOverwritten.add_map(AccRel);
 233       }
 234     }
 235   }
 236
 237   /// Remove writes that just write the same value already stored in the
 238   /// element.
 239   void removeRedundantWrites() {
 240     // Delay actual removal to not invalidate iterators.
 241     SmallVector<MemoryAccess *, 8> StoresToRemove;
 242
 243     for (auto &Stmt : *S) {
 244       for (auto *WA : Stmt) {
 245         if (!WA->isMustWrite())
 246           continue;
 247         if (!WA->isLatestArrayKind())
 248           continue;
 249         if (!isa<StoreInst>(WA->getAccessInstruction()) && !WA->isPHIKind())
 250           continue;
 251
 252         llvm::Value *ReadingValue = WA->tryGetValueStored();
 253
 254         if (!ReadingValue)
 255           continue;
 256
 257         auto RA = getReadAccessForValue(&Stmt, ReadingValue);
 258         if (!RA)
 259           continue;
 260         if (!RA->isLatestArrayKind())
 261           continue;
 262
 263         auto WARel = give(WA->getLatestAccessRelation());
 264         WARel = WARel.intersect_domain(give(WA->getStatement()->getDomain()));
 265         WARel = WARel.intersect_params(give(S->getContext()));
 266         auto RARel = give(RA->getLatestAccessRelation());
 267         RARel = RARel.intersect_domain(give(RA->getStatement()->getDomain()));
 268         RARel = RARel.intersect_params(give(S->getContext()));
 269
 270         if (!RARel.is_equal(WARel)) {
 271           PairUnequalAccRels++;
 272           DEBUG(dbgs() << "Not cleaning up " << WA
 273                        << " because of unequal access relations:\n");
 274           DEBUG(dbgs() << "      RA: " << RARel << "\n");
 275           DEBUG(dbgs() << "      WA: " << WARel << "\n");
 276           continue;
 277         }
 278
 279         if (auto *Conflicting = hasWriteBetween(&Stmt, RA, WA, WARel)) {
 280           (void)Conflicting;
 281           InBetweenStore++;
 282           DEBUG(dbgs() << "Not cleaning up " << WA
 283                        << " because there is another store to the same element "
 284                           "between\n");
 285           DEBUG(Conflicting->print(dbgs()));
 286           continue;
 287         }
 288
 289         StoresToRemove.push_back(WA);
 290       }
 291     }
 292
 293     for (auto *WA : StoresToRemove) {
 294       auto Stmt = WA->getStatement();
 295       auto AccRel = give(WA->getAccessRelation());
 296       auto AccVal = WA->getAccessValue();
 297
 298       DEBUG(dbgs() << "Cleanup of " << WA << ":\n");
 299       DEBUG(dbgs() << "      Scalar: " << *AccVal << "\n");
 300       DEBUG(dbgs() << "      AccRel: " << AccRel << "\n");
 301       (void)AccVal;
 302       (void)AccRel;
 303
 304       Stmt->removeSingleMemoryAccess(WA);
 305
 306       RedundantWritesRemoved++;
 307       TotalRedundantWritesRemoved++;
 308     }
 309   }
 310
 311   /// Remove statements without side effects.
 312   void removeUnnecessaryStmts() {
 313     auto NumStmtsBefore = S->getSize();
 314     S->simplifySCoP(true);
 315     assert(NumStmtsBefore >= S->getSize());
 316     StmtsRemoved = NumStmtsBefore - S->getSize();
 317     DEBUG(dbgs() << "Removed " << StmtsRemoved << " (of " << NumStmtsBefore
 318                  << ") statements\n");
 319     TotalStmtsRemoved += StmtsRemoved;
 320   }
 321
 322   /// Mark all reachable instructions and access, and sweep those that are not
 323   /// reachable.
 324   void markAndSweep(LoopInfo *LI) {
 325     DenseSet<MemoryAccess *> UsedMA;
 326     DenseSet<VirtualInstruction> UsedInsts;
 327
 328     // Get all reachable instructions and accesses.
 329     markReachable(S, LI, UsedInsts, UsedMA);
 330
 331     // Remove all non-reachable accesses.
 332     // We need get all MemoryAccesses first, in order to not invalidate the
 333     // iterators when removing them.
 334     SmallVector<MemoryAccess *, 64> AllMAs;
 335     for (ScopStmt &Stmt : *S)
 336       AllMAs.append(Stmt.begin(), Stmt.end());
 337
 338     for (MemoryAccess *MA : AllMAs) {
 339       if (UsedMA.count(MA))
 340         continue;
 341       DEBUG(dbgs() << "Removing " << MA << " because its value is not used\n");
 342       ScopStmt *Stmt = MA->getStatement();
 343       Stmt->removeSingleMemoryAccess(MA);
 344
 345       DeadAccessesRemoved++;
 346       TotalDeadAccessesRemoved++;
 347     }
 348
 349     // Remove all non-reachable instructions.
 350     for (ScopStmt &Stmt : *S) {
 351       SmallVector<Instruction *, 32> AllInsts(Stmt.insts_begin(),
 352                                               Stmt.insts_end());
 353       SmallVector<Instruction *, 32> RemainInsts;
 354
 355       for (Instruction *Inst : AllInsts) {
 356         auto It = UsedInsts.find({&Stmt, Inst});
 357         if (It == UsedInsts.end()) {
 358           DEBUG(dbgs() << "Removing "; Inst->print(dbgs());
 359                 dbgs() << " because it is not used\n");
 360           DeadInstructionsRemoved++;
 361           TotalDeadInstructionsRemoved++;
 362           continue;
 363         }
 364
 365         RemainInsts.push_back(Inst);
 366
 367         // If instructions appear multiple times, keep only the first.
 368         UsedInsts.erase(It);
 369       }
 370
 371       // Set the new instruction list to be only those we did not remove.
 372       Stmt.setInstructions(RemainInsts);
 373     }
 374   }
 375
 376   /// Print simplification statistics to @p OS.
 377   void printStatistics(llvm::raw_ostream &OS, int Indent = 0) const {
 378     OS.indent(Indent) << "Statistics {\n";
 379     OS.indent(Indent + 4) << "Overwrites removed: " << OverwritesRemoved
 380                           << '\n';
 381     OS.indent(Indent + 4) << "Redundant writes removed: "
 382                           << RedundantWritesRemoved << "\n";
 383     OS.indent(Indent + 4) << "Dead accesses removed: " << DeadAccessesRemoved
 384                           << '\n';
 385     OS.indent(Indent + 4) << "Dead instructions removed: "
 386                           << DeadInstructionsRemoved << '\n';
 387     OS.indent(Indent + 4) << "Stmts removed: " << StmtsRemoved << "\n";
 388     OS.indent(Indent) << "}\n";
 389   }
 390
 391   /// Print the current state of all MemoryAccesses to @p OS.
 392   void printAccesses(llvm::raw_ostream &OS, int Indent = 0) const {
 393     OS.indent(Indent) << "After accesses {\n";
 394     for (auto &Stmt : *S) {
 395       OS.indent(Indent + 4) << Stmt.getBaseName() << "\n";
 396       for (auto *MA : Stmt)
 397         MA->print(OS);
 398     }
 399     OS.indent(Indent) << "}\n";
 400   }
 401
 402 public:
 403   static char ID;
 404   explicit Simplify() : ScopPass(ID) {}
 405
 406   virtual void getAnalysisUsage(AnalysisUsage &AU) const override {
 407     AU.addRequiredTransitive<ScopInfoRegionPass>();
 408     AU.addRequired<LoopInfoWrapperPass>();
 409     AU.setPreservesAll();
 410   }
 411
 412   virtual bool runOnScop(Scop &S) override {
 413     // Reset statistics of last processed SCoP.
 414     releaseMemory();
 415     assert(!isModified());
 416
 417     // Prepare processing of this SCoP.
 418     this->S = &S;
 419     ScopsProcessed++;
 420
 421     DEBUG(dbgs() << "Removing overwrites...\n");
 422     removeOverwrites();
 423
 424     DEBUG(dbgs() << "Removing redundant writes...\n");
 425     removeRedundantWrites();
 426
 427     DEBUG(dbgs() << "Cleanup unused accesses...\n");
 428     LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 429     markAndSweep(LI);
 430
 431     DEBUG(dbgs() << "Removing statements without side effects...\n");
 432     removeUnnecessaryStmts();
 433
 434     if (isModified())
 435       ScopsModified++;
 436     DEBUG(dbgs() << "\nFinal Scop:\n");
 437     DEBUG(dbgs() << S);
 438
 439     return false;
 440   }
 441
 442   virtual void printScop(raw_ostream &OS, Scop &S) const override {
 443     assert(&S == this->S &&
 444            "Can only print analysis for the last processed SCoP");
 445     printStatistics(OS);
 446
 447     if (!isModified()) {
 448       OS << "SCoP could not be simplified\n";
 449       return;
 450     }
 451     printAccesses(OS);
 452   }
 453
 454   virtual void releaseMemory() override {
 455     S = nullptr;
 456
 457     OverwritesRemoved = 0;
 458     RedundantWritesRemoved = 0;
 459     DeadAccessesRemoved = 0;
 460     DeadInstructionsRemoved = 0;
 461     StmtsRemoved = 0;
 462   }
 463 };
 464
 465 char Simplify::ID;
 466 } // anonymous namespace
 467
 468 Pass *polly::createSimplifyPass() { return new Simplify(); }
 469
 470 INITIALIZE_PASS_BEGIN(Simplify, "polly-simplify", "Polly - Simplify", false,
 471                       false)
 472 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 473 INITIALIZE_PASS_END(Simplify, "polly-simplify", "Polly - Simplify", false,
 474                     false)