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 "llvm/ADT/Statistic.h"
  19 #include "llvm/Support/Debug.h"
  20 #define DEBUG_TYPE "polly-simplify"
  21
  22 using namespace llvm;
  23 using namespace polly;
  24
  25 namespace {
  26
  27 STATISTIC(ScopsProcessed, "Number of SCoPs processed");
  28 STATISTIC(ScopsModified, "Number of SCoPs simplified");
  29
  30 STATISTIC(PairUnequalAccRels, "Number of Load-Store pairs NOT removed because "
  31                               "of different access relations");
  32 STATISTIC(InBetweenStore, "Number of Load-Store pairs NOT removed because "
  33                           "there is another store between them");
  34 STATISTIC(TotalRedundantWritesRemoved,
  35           "Number of writes of same value removed in any SCoP");
  36 STATISTIC(TotalStmtsRemoved, "Number of statements removed in any SCoP");
  37
  38 class Simplify : public ScopPass {
  39 private:
  40   /// The last/current SCoP that is/has been processed.
  41   Scop *S;
  42
  43   /// Number of redundant writes removed from this SCoP.
  44   int RedundantWritesRemoved = 0;
  45
  46   /// Number of unnecessary statements removed from the SCoP.
  47   int StmtsRemoved = 0;
  48
  49   /// Return whether at least one simplification has been applied.
  50   bool isModified() const {
  51     return RedundantWritesRemoved > 0 || StmtsRemoved > 0;
  52   }
  53
  54   MemoryAccess *getReadAccessForValue(ScopStmt *Stmt, llvm::Value *Val) {
  55     if (!isa<Instruction>(Val))
  56       return nullptr;
  57
  58     for (auto *MA : *Stmt) {
  59       if (!MA->isRead())
  60         continue;
  61       if (MA->getAccessValue() != Val)
  62         continue;
  63
  64       return MA;
  65     }
  66
  67     return nullptr;
  68   }
  69
  70   /// Return a write access that occurs between @p From and @p To.
  71   ///
  72   /// In region statements the order is ignored because we cannot predict it.
  73   ///
  74   /// @param Stmt    Statement of both writes.
  75   /// @param From    Start looking after this access.
  76   /// @param To      Stop looking at this access, with the access itself.
  77   /// @param Targets Look for an access that may wrote to one of these elements.
  78   ///
  79   /// @return A write access between @p From and @p To that writes to at least
  80   ///         one element in @p Targets.
  81   MemoryAccess *hasWriteBetween(ScopStmt *Stmt, MemoryAccess *From,
  82                                 MemoryAccess *To, isl::map Targets) {
  83     auto TargetsSpace = give(isl_map_get_space(Targets.keep()));
  84
  85     bool Started = Stmt->isRegionStmt();
  86     for (auto *Acc : *Stmt) {
  87       if (Acc->isLatestScalarKind())
  88         continue;
  89
  90       if (Stmt->isBlockStmt() && From == Acc) {
  91         assert(!Started);
  92         Started = true;
  93         continue;
  94       }
  95       if (Stmt->isBlockStmt() && To == Acc) {
  96         assert(Started);
  97         return nullptr;
  98       }
  99       if (!Started)
 100         continue;
 101
 102       if (!Acc->isWrite())
 103         continue;
 104
 105       auto AccRel = give(Acc->getAccessRelation());
 106       auto AccRelSpace = give(isl_map_get_space(AccRel.keep()));
 107
 108       // Spaces being different means that they access different arrays.
 109       if (isl_space_has_equal_tuples(TargetsSpace.keep(), AccRelSpace.keep()) ==
 110           isl_bool_false)
 111         continue;
 112
 113       AccRel = give(isl_map_intersect_domain(AccRel.take(),
 114                                              Acc->getStatement()->getDomain()));
 115       AccRel = give(isl_map_intersect_params(AccRel.take(), S->getContext()));
 116       auto CommonElt = give(isl_map_intersect(Targets.copy(), AccRel.copy()));
 117       if (isl_map_is_empty(CommonElt.keep()) != isl_bool_true)
 118         return Acc;
 119     }
 120     assert(Stmt->isRegionStmt() &&
 121            "To must be encountered in block statements");
 122     return nullptr;
 123   }
 124
 125   /// Remove writes that just write the same value already stored in the
 126   /// element.
 127   void removeRedundantWrites() {
 128     // Delay actual removal to not invalidate iterators.
 129     SmallVector<MemoryAccess *, 8> StoresToRemove;
 130
 131     for (auto &Stmt : *S) {
 132       for (auto *WA : Stmt) {
 133         if (!WA->isMustWrite())
 134           continue;
 135         if (!WA->isLatestArrayKind())
 136           continue;
 137         if (!isa<StoreInst>(WA->getAccessInstruction()))
 138           continue;
 139
 140         auto ReadingValue = WA->getAccessValue();
 141         if (!ReadingValue)
 142           continue;
 143
 144         auto RA = getReadAccessForValue(&Stmt, ReadingValue);
 145         if (!RA)
 146           continue;
 147         if (!RA->isLatestArrayKind())
 148           continue;
 149
 150         auto WARel = give(WA->getLatestAccessRelation());
 151         WARel = give(isl_map_intersect_domain(WARel.take(),
 152                                               WA->getStatement()->getDomain()));
 153         WARel = give(isl_map_intersect_params(WARel.take(), S->getContext()));
 154         auto RARel = give(RA->getLatestAccessRelation());
 155         RARel = give(isl_map_intersect_domain(RARel.take(),
 156                                               RA->getStatement()->getDomain()));
 157         RARel = give(isl_map_intersect_params(RARel.take(), S->getContext()));
 158
 159         if (isl_map_is_equal(RARel.keep(), WARel.keep()) != isl_bool_true) {
 160           PairUnequalAccRels++;
 161           DEBUG(dbgs() << "Not cleaning up " << WA
 162                        << " because of unequal access relations:\n");
 163           DEBUG(dbgs() << "      RA: " << RARel << "\n");
 164           DEBUG(dbgs() << "      WA: " << WARel << "\n");
 165           continue;
 166         }
 167
 168         if (auto *Conflicting = hasWriteBetween(&Stmt, RA, WA, WARel)) {
 169           (void)Conflicting;
 170           InBetweenStore++;
 171           DEBUG(dbgs() << "Not cleaning up " << WA
 172                        << " because there is another store to the same element "
 173                           "between\n");
 174           DEBUG(Conflicting->print(dbgs()));
 175           continue;
 176         }
 177
 178         StoresToRemove.push_back(WA);
 179       }
 180     }
 181
 182     for (auto *WA : StoresToRemove) {
 183       auto Stmt = WA->getStatement();
 184       auto AccRel = give(WA->getAccessRelation());
 185       auto AccVal = WA->getAccessValue();
 186
 187       DEBUG(dbgs() << "Cleanup of " << WA << ":\n");
 188       DEBUG(dbgs() << "      Scalar: " << *AccVal << "\n");
 189       DEBUG(dbgs() << "      AccRel: " << AccRel << "\n");
 190       (void)AccRel;
 191
 192       Stmt->removeSingleMemoryAccess(WA);
 193
 194       RedundantWritesRemoved++;
 195       TotalRedundantWritesRemoved++;
 196     }
 197   }
 198
 199   /// Remove statements without side effects.
 200   void removeUnnecessayStmts() {
 201     auto NumStmtsBefore = S->getSize();
 202     S->simplifySCoP(true);
 203     assert(NumStmtsBefore >= S->getSize());
 204     StmtsRemoved = NumStmtsBefore - S->getSize();
 205     DEBUG(dbgs() << "Removed " << StmtsRemoved << " (of " << NumStmtsBefore
 206                  << ") statements\n");
 207     TotalStmtsRemoved += StmtsRemoved;
 208   }
 209
 210   /// Print simplification statistics to @p OS.
 211   void printStatistics(llvm::raw_ostream &OS, int Indent = 0) const {
 212     OS.indent(Indent) << "Statistics {\n";
 213     OS.indent(Indent + 4) << "Redundant writes removed: "
 214                           << RedundantWritesRemoved << "\n";
 215     OS.indent(Indent + 4) << "Stmts removed: " << StmtsRemoved << "\n";
 216     OS.indent(Indent) << "}\n";
 217   }
 218
 219   /// Print the current state of all MemoryAccesses to @p OS.
 220   void printAccesses(llvm::raw_ostream &OS, int Indent = 0) const {
 221     OS.indent(Indent) << "After accesses {\n";
 222     for (auto &Stmt : *S) {
 223       OS.indent(Indent + 4) << Stmt.getBaseName() << "\n";
 224       for (auto *MA : Stmt)
 225         MA->print(OS);
 226     }
 227     OS.indent(Indent) << "}\n";
 228   }
 229
 230 public:
 231   static char ID;
 232   explicit Simplify() : ScopPass(ID) {}
 233
 234   virtual void getAnalysisUsage(AnalysisUsage &AU) const override {
 235     AU.addRequiredTransitive<ScopInfoRegionPass>();
 236     AU.setPreservesAll();
 237   }
 238
 239   virtual bool runOnScop(Scop &S) override {
 240     // Reset statistics of last processed SCoP.
 241     releaseMemory();
 242
 243     // Prepare processing of this SCoP.
 244     this->S = &S;
 245     ScopsProcessed++;
 246
 247     DEBUG(dbgs() << "Removing redundant writes...\n");
 248     removeRedundantWrites();
 249
 250     DEBUG(dbgs() << "Removing statements without side effects...\n");
 251     removeUnnecessayStmts();
 252
 253     if (isModified())
 254       ScopsModified++;
 255     DEBUG(dbgs() << "\nFinal Scop:\n");
 256     DEBUG(S.print(dbgs()));
 257
 258     return false;
 259   }
 260
 261   virtual void printScop(raw_ostream &OS, Scop &S) const override {
 262     assert(&S == this->S &&
 263            "Can only print analysis for the last processed SCoP");
 264     printStatistics(OS);
 265
 266     if (!isModified()) {
 267       OS << "SCoP could not be simplified\n";
 268       return;
 269     }
 270     printAccesses(OS);
 271   }
 272
 273   virtual void releaseMemory() override {
 274     S = nullptr;
 275     StmtsRemoved = 0;
 276   }
 277 };
 278
 279 char Simplify::ID;
 280 } // anonymous namespace
 281
 282 Pass *polly::createSimplifyPass() { return new Simplify(); }
 283
 284 INITIALIZE_PASS_BEGIN(Simplify, "polly-simplify", "Polly - Simplify", false,
 285                       false)
 286 INITIALIZE_PASS_END(Simplify, "polly-simplify", "Polly - Simplify", false,
 287                     false)