xref: /llvm-project/polly/lib/Transform/MaximalStaticExpansion.cpp (revision 6292a808b3524d9ba6f4ce55bc5b9e547b088dd8)
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()->getFirstNonPHIIt());
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()->getFirstNonPHIIt());
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)
555