polly/lib/Transform/MaximalStaticExpansion.cpp

   1 //===- MaximalStaticExpansion.cpp -----------------------------------------===//
   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 // This pass fully expand the memory accesses of a Scop to get rid of
  10 // dependencies.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "polly/MaximalStaticExpansion.h"
  15 #include "polly/DependenceInfo.h"
  16 #include "polly/LinkAllPasses.h"
  17 #include "polly/ScopInfo.h"
  18 #include "polly/ScopPass.h"
  19 #include "polly/Support/ISLTools.h"
  20 #include "llvm/ADT/SmallPtrSet.h"
  21 #include "llvm/ADT/StringRef.h"
  22 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
  23 #include "llvm/InitializePasses.h"
  24 #include "isl/isl-noexceptions.h"
  25 #include "isl/union_map.h"
  26 #include <cassert>
  27 #include <limits>
  28 #include <string>
  29 #include <vector>
  30
  31 using namespace llvm;
  32 using namespace polly;
  33
  34 #define DEBUG_TYPE "polly-mse"
  35
  36 namespace {
  37
  38 class MaximalStaticExpanderWrapperPass final : public ScopPass {
  39 public:
  40   static char ID;
  41
  42   explicit MaximalStaticExpanderWrapperPass() : ScopPass(ID) {}
  43
  44   ~MaximalStaticExpanderWrapperPass() override = default;
  45
  46   /// Expand the accesses of the SCoP.
  47   ///
  48   /// @param S The SCoP that must be expanded.
  49   bool runOnScop(Scop &S) override;
  50
  51   /// Print the SCoP.
  52   ///
  53   /// @param OS The stream where to print.
  54   /// @param S The SCop that must be printed.
  55   void printScop(raw_ostream &OS, Scop &S) const override;
  56
  57   /// Register all analyses and transformations required.
  58   void getAnalysisUsage(AnalysisUsage &AU) const override;
  59 };
  60
  61 #ifndef NDEBUG
  62 /// Whether a dimension of a set is bounded (lower and upper) by a constant,
  63 /// i.e. there are two constants Min and Max, such that every value x of the
  64 /// chosen dimensions is Min <= x <= Max.
  65 static bool isDimBoundedByConstant(isl::set Set, unsigned dim) {
  66   auto ParamDims = unsignedFromIslSize(Set.dim(isl::dim::param));
  67   Set = Set.project_out(isl::dim::param, 0, ParamDims);
  68   Set = Set.project_out(isl::dim::set, 0, dim);
  69   auto SetDims = unsignedFromIslSize(Set.tuple_dim());
  70   assert(SetDims >= 1);
  71   Set = Set.project_out(isl::dim::set, 1, SetDims - 1);
  72   return bool(Set.is_bounded());
  73 }
  74 #endif
  75
  76 class MaximalStaticExpansionImpl {
  77   OptimizationRemarkEmitter &ORE;
  78   Scop &S;
  79   isl::union_map &Dependences;
  80
  81   /// Emit remark
  82   void emitRemark(StringRef Msg, Instruction *Inst) {
  83     ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "ExpansionRejection", Inst)
  84              << Msg);
  85   }
  86
  87   /// Filter the dependences to have only one related to current memory access.
  88   ///
  89   /// @param S The SCop in which the memory access appears in.
  90   /// @param MapDependences The dependences to filter.
  91   /// @param MA The memory access that need to be expanded.
  92   isl::union_map filterDependences(const isl::union_map &Dependences,
  93                                    MemoryAccess *MA) {
  94     auto SAI = MA->getLatestScopArrayInfo();
  95
  96     auto AccessDomainSet = MA->getAccessRelation().domain();
  97     auto AccessDomainId = AccessDomainSet.get_tuple_id();
  98
  99     isl::union_map MapDependences = isl::union_map::empty(S.getIslCtx());
 100
 101     for (isl::map Map : Dependences.get_map_list()) {
 102       // Filter out Statement to Statement dependences.
 103       if (!Map.can_curry())
 104         continue;
 105
 106       // Intersect with the relevant SAI.
 107       auto TmpMapDomainId =
 108           Map.get_space().domain().unwrap().range().get_tuple_id(isl::dim::set);
 109
 110       ScopArrayInfo *UserSAI =
 111           static_cast<ScopArrayInfo *>(TmpMapDomainId.get_user());
 112
 113       if (SAI != UserSAI)
 114         continue;
 115
 116       // Get the correct S1[] -> S2[] dependence.
 117       auto NewMap = Map.factor_domain();
 118       auto NewMapDomainId = NewMap.domain().get_tuple_id();
 119
 120       if (AccessDomainId.get() != NewMapDomainId.get())
 121         continue;
 122
 123       // Add the corresponding map to MapDependences.
 124       MapDependences = MapDependences.unite(NewMap);
 125     }
 126
 127     return MapDependences;
 128   }
 129
 130   /// Return true if the SAI in parameter is expandable.
 131   ///
 132   /// @param SAI the SAI that need to be checked.
 133   /// @param Writes A set that will contains all the write accesses.
 134   /// @param Reads A set that will contains all the read accesses.
 135   /// @param S The SCop in which the SAI is in.
 136   /// @param Dependences The RAW dependences of the SCop.
 137   bool isExpandable(const ScopArrayInfo *SAI,
 138                     SmallPtrSetImpl<MemoryAccess *> &Writes,
 139                     SmallPtrSetImpl<MemoryAccess *> &Reads, Scop &S) {
 140     if (SAI->isValueKind()) {
 141       Writes.insert(S.getValueDef(SAI));
 142       for (auto MA : S.getValueUses(SAI))
 143         Reads.insert(MA);
 144       return true;
 145     } else if (SAI->isPHIKind()) {
 146       auto Read = S.getPHIRead(SAI);
 147
 148       auto StmtDomain = isl::union_set(Read->getStatement()->getDomain());
 149
 150       auto Writes = S.getPHIIncomings(SAI);
 151
 152       // Get the domain where all the writes are writing to.
 153       auto WriteDomain = isl::union_set::empty(S.getIslCtx());
 154
 155       for (auto Write : Writes) {
 156         auto MapDeps = filterDependences(Dependences, Write);
 157         for (isl::map Map : MapDeps.get_map_list())
 158           WriteDomain = WriteDomain.unite(Map.range());
 159       }
 160
 161       // For now, read from original scalar is not possible.
 162       if (!StmtDomain.is_equal(WriteDomain)) {
 163         emitRemark(SAI->getName() + " read from its original value.",
 164                    Read->getAccessInstruction());
 165         return false;
 166       }
 167
 168       return true;
 169     } else if (SAI->isExitPHIKind()) {
 170       // For now, we are not able to expand ExitPhi.
 171       emitRemark(SAI->getName() + " is a ExitPhi node.",
 172                  S.getEnteringBlock()->getFirstNonPHI());
 173       return false;
 174     }
 175
 176     int NumberWrites = 0;
 177     for (ScopStmt &Stmt : S) {
 178       auto StmtReads = isl::union_map::empty(S.getIslCtx());
 179       auto StmtWrites = isl::union_map::empty(S.getIslCtx());
 180
 181       for (MemoryAccess *MA : Stmt) {
 182         // Check if the current MemoryAccess involved the current SAI.
 183         if (SAI != MA->getLatestScopArrayInfo())
 184           continue;
 185
 186         // For now, we are not able to expand array where read come after write
 187         // (to the same location) in a same statement.
 188         auto AccRel = isl::union_map(MA->getAccessRelation());
 189         if (MA->isRead()) {
 190           // Reject load after store to same location.
 191           if (!StmtWrites.is_disjoint(AccRel)) {
 192             emitRemark(SAI->getName() + " has read after write to the same "
 193                                         "element in same statement. The "
 194                                         "dependences found during analysis may "
 195                                         "be wrong because Polly is not able to "
 196                                         "handle such case for now.",
 197                        MA->getAccessInstruction());
 198             return false;
 199           }
 200
 201           StmtReads = StmtReads.unite(AccRel);
 202         } else {
 203           StmtWrites = StmtWrites.unite(AccRel);
 204         }
 205
 206         // For now, we are not able to expand MayWrite.
 207         if (MA->isMayWrite()) {
 208           emitRemark(SAI->getName() + " has a maywrite access.",
 209                      MA->getAccessInstruction());
 210           return false;
 211         }
 212
 213         // For now, we are not able to expand SAI with more than one write.
 214         if (MA->isMustWrite()) {
 215           Writes.insert(MA);
 216           NumberWrites++;
 217           if (NumberWrites > 1) {
 218             emitRemark(SAI->getName() + " has more than 1 write access.",
 219                        MA->getAccessInstruction());
 220             return false;
 221           }
 222         }
 223
 224         // Check if it is possible to expand this read.
 225         if (MA->isRead()) {
 226           // Get the domain of the current ScopStmt.
 227           auto StmtDomain = Stmt.getDomain();
 228
 229           // Get the domain of the future Read access.
 230           auto ReadDomainSet = MA->getAccessRelation().domain();
 231           auto ReadDomain = isl::union_set(ReadDomainSet);
 232
 233           // Get the dependences relevant for this MA
 234           auto MapDependences = filterDependences(Dependences.reverse(), MA);
 235           unsigned NumberElementMap = isl_union_map_n_map(MapDependences.get());
 236
 237           if (NumberElementMap == 0) {
 238             emitRemark("The expansion of " + SAI->getName() +
 239                            " would lead to a read from the original array.",
 240                        MA->getAccessInstruction());
 241             return false;
 242           }
 243
 244           auto DepsDomain = MapDependences.domain();
 245
 246           // If there are multiple maps in the Deps, we cannot handle this case
 247           // for now.
 248           if (NumberElementMap != 1) {
 249             emitRemark(SAI->getName() +
 250                            " has too many dependences to be handle for now.",
 251                        MA->getAccessInstruction());
 252             return false;
 253           }
 254
 255           auto DepsDomainSet = isl::set(DepsDomain);
 256
 257           // For now, read from the original array is not possible.
 258           if (!StmtDomain.is_subset(DepsDomainSet)) {
 259             emitRemark("The expansion of " + SAI->getName() +
 260                            " would lead to a read from the original array.",
 261                        MA->getAccessInstruction());
 262             return false;
 263           }
 264
 265           Reads.insert(MA);
 266         }
 267       }
 268     }
 269
 270     // No need to expand SAI with no write.
 271     if (NumberWrites == 0) {
 272       emitRemark(SAI->getName() + " has 0 write access.",
 273                  S.getEnteringBlock()->getFirstNonPHI());
 274       return false;
 275     }
 276
 277     return true;
 278   }
 279
 280   /// Expand the MemoryAccess according to Dependences and already expanded
 281   /// MemoryAccesses.
 282   ///
 283   /// @param The SCop in which the memory access appears in.
 284   /// @param The memory access that need to be expanded.
 285   /// @param Dependences The RAW dependences of the SCop.
 286   /// @param ExpandedSAI The expanded SAI created during write expansion.
 287   /// @param Reverse if true, the Dependences union_map is reversed before
 288   /// intersection.
 289   void mapAccess(SmallPtrSetImpl<MemoryAccess *> &Accesses,
 290                  const isl::union_map &Dependences, ScopArrayInfo *ExpandedSAI,
 291                  bool Reverse) {
 292     for (auto MA : Accesses) {
 293       // Get the current AM.
 294       auto CurrentAccessMap = MA->getAccessRelation();
 295
 296       // Get RAW dependences for the current WA.
 297       auto DomainSet = MA->getAccessRelation().domain();
 298       auto Domain = isl::union_set(DomainSet);
 299
 300       // Get the dependences relevant for this MA.
 301       isl::union_map MapDependences =
 302           filterDependences(Reverse ? Dependences.reverse() : Dependences, MA);
 303
 304       // If no dependences, no need to modify anything.
 305       if (MapDependences.is_empty())
 306         return;
 307
 308       assert(isl_union_map_n_map(MapDependences.get()) == 1 &&
 309              "There are more than one RAW dependencies in the union map.");
 310       auto NewAccessMap = isl::map::from_union_map(MapDependences);
 311
 312       auto Id = ExpandedSAI->getBasePtrId();
 313
 314       // Replace the out tuple id with the one of the access array.
 315       NewAccessMap = NewAccessMap.set_tuple_id(isl::dim::out, Id);
 316
 317       // Set the new access relation.
 318       MA->setNewAccessRelation(NewAccessMap);
 319     }
 320   }
 321
 322   /// Expand the MemoryAccess according to its domain.
 323   ///
 324   /// @param S The SCop in which the memory access appears in.
 325   /// @param MA The memory access that need to be expanded.
 326   ScopArrayInfo *expandAccess(MemoryAccess *MA) {
 327     // Get the current AM.
 328     auto CurrentAccessMap = MA->getAccessRelation();
 329
 330     unsigned in_dimensions =
 331         unsignedFromIslSize(CurrentAccessMap.domain_tuple_dim());
 332
 333     // Get domain from the current AM.
 334     auto Domain = CurrentAccessMap.domain();
 335
 336     // Create a new AM from the domain.
 337     auto NewAccessMap = isl::map::from_domain(Domain);
 338
 339     // Add dimensions to the new AM according to the current in_dim.
 340     NewAccessMap = NewAccessMap.add_dims(isl::dim::out, in_dimensions);
 341
 342     // Create the string representing the name of the new SAI.
 343     // One new SAI for each statement so that each write go to a different
 344     // memory cell.
 345     auto CurrentStmtDomain = MA->getStatement()->getDomain();
 346     auto CurrentStmtName = CurrentStmtDomain.get_tuple_name();
 347     auto CurrentOutId = CurrentAccessMap.get_tuple_id(isl::dim::out);
 348     std::string CurrentOutIdString =
 349         MA->getScopArrayInfo()->getName() + "_" + CurrentStmtName + "_expanded";
 350
 351     // Set the tuple id for the out dimension.
 352     NewAccessMap = NewAccessMap.set_tuple_id(isl::dim::out, CurrentOutId);
 353
 354     // Create the size vector.
 355     std::vector<unsigned> Sizes;
 356     for (unsigned i = 0; i < in_dimensions; i++) {
 357       assert(isDimBoundedByConstant(CurrentStmtDomain, i) &&
 358              "Domain boundary are not constant.");
 359       auto UpperBound = getConstant(CurrentStmtDomain.dim_max(i), true, false);
 360       assert(!UpperBound.is_null() && UpperBound.is_pos() &&
 361              !UpperBound.is_nan() &&
 362              "The upper bound is not a positive integer.");
 363       assert(UpperBound.le(isl::val(CurrentAccessMap.ctx(),
 364                                     std::numeric_limits<int>::max() - 1)) &&
 365              "The upper bound overflow a int.");
 366       Sizes.push_back(UpperBound.get_num_si() + 1);
 367     }
 368
 369     // Get the ElementType of the current SAI.
 370     auto ElementType = MA->getLatestScopArrayInfo()->getElementType();
 371
 372     // Create (or get if already existing) the new expanded SAI.
 373     auto ExpandedSAI =
 374         S.createScopArrayInfo(ElementType, CurrentOutIdString, Sizes);
 375     ExpandedSAI->setIsOnHeap(true);
 376
 377     // Get the out Id of the expanded Array.
 378     auto NewOutId = ExpandedSAI->getBasePtrId();
 379
 380     // Set the out id of the new AM to the new SAI id.
 381     NewAccessMap = NewAccessMap.set_tuple_id(isl::dim::out, NewOutId);
 382
 383     // Add constraints to linked output with input id.
 384     auto SpaceMap = NewAccessMap.get_space();
 385     auto ConstraintBasicMap = isl::basic_map::equal(
 386         SpaceMap, unsignedFromIslSize(SpaceMap.dim(isl::dim::in)));
 387     NewAccessMap = isl::map(ConstraintBasicMap);
 388
 389     // Set the new access relation map.
 390     MA->setNewAccessRelation(NewAccessMap);
 391
 392     return ExpandedSAI;
 393   }
 394
 395   /// Expand PHI memory accesses.
 396   ///
 397   /// @param The SCop in which the memory access appears in.
 398   /// @param The ScopArrayInfo representing the PHI accesses to expand.
 399   /// @param Dependences The RAW dependences of the SCop.
 400   void expandPhi(Scop &S, const ScopArrayInfo *SAI,
 401                  const isl::union_map &Dependences) {
 402     SmallPtrSet<MemoryAccess *, 4> Writes;
 403     for (auto MA : S.getPHIIncomings(SAI))
 404       Writes.insert(MA);
 405     auto Read = S.getPHIRead(SAI);
 406     auto ExpandedSAI = expandAccess(Read);
 407
 408     mapAccess(Writes, Dependences, ExpandedSAI, false);
 409   }
 410
 411 public:
 412   MaximalStaticExpansionImpl(Scop &S, isl::union_map &Dependences,
 413                              OptimizationRemarkEmitter &ORE)
 414       : ORE(ORE), S(S), Dependences(Dependences) {}
 415
 416   /// Expand the accesses of the SCoP
 417   ///
 418   /// @param S The SCoP that must be expanded
 419   /// @param D The dependencies information of SCoP
 420   void expand() {
 421     SmallVector<ScopArrayInfo *, 4> CurrentSAI(S.arrays().begin(),
 422                                                S.arrays().end());
 423     for (auto SAI : CurrentSAI) {
 424       SmallPtrSet<MemoryAccess *, 4> AllWrites;
 425       SmallPtrSet<MemoryAccess *, 4> AllReads;
 426       if (!isExpandable(SAI, AllWrites, AllReads, S))
 427         continue;
 428
 429       if (SAI->isValueKind() || SAI->isArrayKind()) {
 430         assert(AllWrites.size() == 1 || SAI->isValueKind());
 431
 432         auto TheWrite = *(AllWrites.begin());
 433         ScopArrayInfo *ExpandedArray = expandAccess(TheWrite);
 434
 435         mapAccess(AllReads, Dependences, ExpandedArray, true);
 436       } else if (SAI->isPHIKind()) {
 437         expandPhi(S, SAI, Dependences);
 438       }
 439     }
 440   }
 441
 442   /// Dump the internal information about a performed MSE to @p OS.
 443   void print(llvm::raw_ostream &OS) {
 444     OS << "After arrays {\n";
 445
 446     for (auto &Array : S.arrays())
 447       Array->print(OS);
 448
 449     OS << "}\n";
 450
 451     OS << "After accesses {\n";
 452     for (auto &Stmt : S) {
 453       OS.indent(4) << Stmt.getBaseName() << "{\n";
 454       for (auto *MA : Stmt)
 455         MA->print(OS);
 456       OS.indent(4) << "}\n";
 457     }
 458     OS << "}\n";
 459   }
 460 };
 461
 462 static std::unique_ptr<MaximalStaticExpansionImpl>
 463 runMaximalStaticExpansion(Scop &S, OptimizationRemarkEmitter &ORE,
 464                           const Dependences &D) {
 465   auto Dependences = D.getDependences(Dependences::TYPE_RAW);
 466
 467   std::unique_ptr<MaximalStaticExpansionImpl> Impl =
 468       std::make_unique<MaximalStaticExpansionImpl>(S, Dependences, ORE);
 469
 470   Impl->expand();
 471   return Impl;
 472 }
 473
 474 static PreservedAnalyses runMSEUsingNPM(Scop &S, ScopAnalysisManager &SAM,
 475                                         ScopStandardAnalysisResults &SAR,
 476                                         raw_ostream *OS) {
 477   OptimizationRemarkEmitter ORE(&S.getFunction());
 478
 479   auto &DI = SAM.getResult<DependenceAnalysis>(S, SAR);
 480   auto &D = DI.getDependences(Dependences::AL_Reference);
 481
 482   std::unique_ptr<MaximalStaticExpansionImpl> Impl =
 483       runMaximalStaticExpansion(S, ORE, D);
 484
 485   if (OS) {
 486     *OS << "Printing analysis 'Polly - Maximal static expansion of SCoP' for "
 487            "region: '"
 488         << S.getName() << "' in function '" << S.getFunction().getName()
 489         << "':\n";
 490
 491     if (Impl) {
 492       *OS << "MSE result:\n";
 493       Impl->print(*OS);
 494     }
 495   }
 496
 497   return PreservedAnalyses::all();
 498 }
 499
 500 } // namespace
 501
 502 PreservedAnalyses
 503 MaximalStaticExpansionPass::run(Scop &S, ScopAnalysisManager &SAM,
 504                                 ScopStandardAnalysisResults &SAR,
 505                                 SPMUpdater &) {
 506   return runMSEUsingNPM(S, SAM, SAR, nullptr);
 507 }
 508
 509 PreservedAnalyses
 510 MaximalStaticExpansionPrinterPass::run(Scop &S, ScopAnalysisManager &SAM,
 511                                        ScopStandardAnalysisResults &SAR,
 512                                        SPMUpdater &) {
 513   return runMSEUsingNPM(S, SAM, SAR, &OS);
 514 }
 515
 516 char MaximalStaticExpanderWrapperPass::ID = 0;
 517
 518 bool MaximalStaticExpanderWrapperPass::runOnScop(Scop &S) {
 519   // Get the ORE from OptimizationRemarkEmitterWrapperPass.
 520   OptimizationRemarkEmitter *ORE =
 521       &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
 522
 523   // Get the RAW Dependences.
 524   auto &DI = getAnalysis<DependenceInfo>();
 525   auto &D = DI.getDependences(Dependences::AL_Reference);
 526
 527   std::unique_ptr<MaximalStaticExpansionImpl> Impl =
 528       runMaximalStaticExpansion(S, *ORE, D);
 529
 530   return false;
 531 }
 532
 533 void MaximalStaticExpanderWrapperPass::printScop(raw_ostream &OS,
 534                                                  Scop &S) const {
 535   S.print(OS, false);
 536 }
 537
 538 void MaximalStaticExpanderWrapperPass::getAnalysisUsage(
 539     AnalysisUsage &AU) const {
 540   ScopPass::getAnalysisUsage(AU);
 541   AU.addRequired<DependenceInfo>();
 542   AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
 543 }
 544
 545 Pass *polly::createMaximalStaticExpansionPass() {
 546   return new MaximalStaticExpanderWrapperPass();
 547 }
 548
 549 INITIALIZE_PASS_BEGIN(MaximalStaticExpanderWrapperPass, "polly-mse",
 550                       "Polly - Maximal static expansion of SCoP", false, false);
 551 INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
 552 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass);
 553 INITIALIZE_PASS_END(MaximalStaticExpanderWrapperPass, "polly-mse",
 554                     "Polly - Maximal static expansion of SCoP", false, false)