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
31using namespace llvm;
32using namespace polly;
33
34#define DEBUG_TYPE "polly-mse"
35
36namespace {
37
38class MaximalStaticExpanderWrapperPass final : public ScopPass {
39public:
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.
65static bool isDimBoundedByConstant(isl::set Set, unsigned dim) {
66 auto ParamDims = unsignedFromIslSize(Size: Set.dim(type: isl::dim::param));
67 Set = Set.project_out(type: isl::dim::param, first: 0, n: ParamDims);
68 Set = Set.project_out(type: isl::dim::set, first: 0, n: dim);
69 auto SetDims = unsignedFromIslSize(Size: Set.tuple_dim());
70 assert(SetDims >= 1);
71 Set = Set.project_out(type: isl::dim::set, first: 1, n: SetDims - 1);
72 return bool(Set.is_bounded());
73}
74#endif
75
76class 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(OptDiag&: 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(ctx: 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(type: 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(umap2: 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(Ptr: S.getValueDef(SAI));
142 for (auto MA : S.getValueUses(SAI))
143 Reads.insert(Ptr: 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(ctx: S.getIslCtx());
154
155 for (auto Write : Writes) {
156 auto MapDeps = filterDependences(Dependences, MA: Write);
157 for (isl::map Map : MapDeps.get_map_list())
158 WriteDomain = WriteDomain.unite(uset2: Map.range());
159 }
160
161 // For now, read from original scalar is not possible.
162 if (!StmtDomain.is_equal(uset2: WriteDomain)) {
163 emitRemark(Msg: SAI->getName() + " read from its original value.",
164 Inst: 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(Msg: SAI->getName() + " is a ExitPhi node.",
172 Inst: S.getEnteringBlock()->getFirstNonPHI());
173 return false;
174 }
175
176 int NumberWrites = 0;
177 for (ScopStmt &Stmt : S) {
178 auto StmtReads = isl::union_map::empty(ctx: S.getIslCtx());
179 auto StmtWrites = isl::union_map::empty(ctx: 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(umap2: AccRel)) {
192 emitRemark(Msg: 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 Inst: MA->getAccessInstruction());
198 return false;
199 }
200
201 StmtReads = StmtReads.unite(umap2: AccRel);
202 } else {
203 StmtWrites = StmtWrites.unite(umap2: AccRel);
204 }
205
206 // For now, we are not able to expand MayWrite.
207 if (MA->isMayWrite()) {
208 emitRemark(Msg: SAI->getName() + " has a maywrite access.",
209 Inst: 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(Ptr: MA);
216 NumberWrites++;
217 if (NumberWrites > 1) {
218 emitRemark(Msg: SAI->getName() + " has more than 1 write access.",
219 Inst: 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: Dependences.reverse(), MA);
235 unsigned NumberElementMap = isl_union_map_n_map(umap: MapDependences.get());
236
237 if (NumberElementMap == 0) {
238 emitRemark(Msg: "The expansion of " + SAI->getName() +
239 " would lead to a read from the original array.",
240 Inst: 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(Msg: SAI->getName() +
250 " has too many dependences to be handle for now.",
251 Inst: 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(set2: DepsDomainSet)) {
259 emitRemark(Msg: "The expansion of " + SAI->getName() +
260 " would lead to a read from the original array.",
261 Inst: MA->getAccessInstruction());
262 return false;
263 }
264
265 Reads.insert(Ptr: MA);
266 }
267 }
268 }
269
270 // No need to expand SAI with no write.
271 if (NumberWrites == 0) {
272 emitRemark(Msg: SAI->getName() + " has 0 write access.",
273 Inst: 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(Dependences: 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(umap: 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(type: isl::dim::out, id: 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(Size: 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(set: Domain);
338
339 // Add dimensions to the new AM according to the current in_dim.
340 NewAccessMap = NewAccessMap.add_dims(type: isl::dim::out, n: 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(type: 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(type: isl::dim::out, id: 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(PwAff: CurrentStmtDomain.dim_max(pos: i), Max: true, Min: 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(x: 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, BaseName: 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(type: isl::dim::out, id: 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 space: SpaceMap, n_equal: unsignedFromIslSize(Size: SpaceMap.dim(type: 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(Ptr: MA);
405 auto Read = S.getPHIRead(SAI);
406 auto ExpandedSAI = expandAccess(MA: Read);
407
408 mapAccess(Accesses&: Writes, Dependences, ExpandedSAI, Reverse: false);
409 }
410
411public:
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, Writes&: AllWrites, Reads&: 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(MA: TheWrite);
434
435 mapAccess(Accesses&: AllReads, Dependences, ExpandedSAI: ExpandedArray, Reverse: 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(NumSpaces: 4) << Stmt.getBaseName() << "{\n";
454 for (auto *MA : Stmt)
455 MA->print(OS);
456 OS.indent(NumSpaces: 4) << "}\n";
457 }
458 OS << "}\n";
459 }
460};
461
462static std::unique_ptr<MaximalStaticExpansionImpl>
463runMaximalStaticExpansion(Scop &S, OptimizationRemarkEmitter &ORE,
464 const Dependences &D) {
465 auto Dependences = D.getDependences(Kinds: Dependences::TYPE_RAW);
466
467 std::unique_ptr<MaximalStaticExpansionImpl> Impl =
468 std::make_unique<MaximalStaticExpansionImpl>(args&: S, args&: Dependences, args&: ORE);
469
470 Impl->expand();
471 return Impl;
472}
473
474static 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>(IR&: S, ExtraArgs&: SAR);
480 auto &D = DI.getDependences(Level: 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&: *OS);
494 }
495 }
496
497 return PreservedAnalyses::all();
498}
499
500} // namespace
501
502PreservedAnalyses
503MaximalStaticExpansionPass::run(Scop &S, ScopAnalysisManager &SAM,
504 ScopStandardAnalysisResults &SAR,
505 SPMUpdater &) {
506 return runMSEUsingNPM(S, SAM, SAR, OS: nullptr);
507}
508
509PreservedAnalyses
510MaximalStaticExpansionPrinterPass::run(Scop &S, ScopAnalysisManager &SAM,
511 ScopStandardAnalysisResults &SAR,
512 SPMUpdater &) {
513 return runMSEUsingNPM(S, SAM, SAR, OS: &OS);
514}
515
516char MaximalStaticExpanderWrapperPass::ID = 0;
517
518bool 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(Level: Dependences::AL_Reference);
526
527 std::unique_ptr<MaximalStaticExpansionImpl> Impl =
528 runMaximalStaticExpansion(S, ORE&: *ORE, D);
529
530 return false;
531}
532
533void MaximalStaticExpanderWrapperPass::printScop(raw_ostream &OS,
534 Scop &S) const {
535 S.print(OS, PrintInstructions: false);
536}
537
538void MaximalStaticExpanderWrapperPass::getAnalysisUsage(
539 AnalysisUsage &AU) const {
540 ScopPass::getAnalysisUsage(AU);
541 AU.addRequired<DependenceInfo>();
542 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
543}
544
545Pass *polly::createMaximalStaticExpansionPass() {
546 return new MaximalStaticExpanderWrapperPass();
547}
548
549INITIALIZE_PASS_BEGIN(MaximalStaticExpanderWrapperPass, "polly-mse",
550 "Polly - Maximal static expansion of SCoP", false, false);
551INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
552INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass);
553INITIALIZE_PASS_END(MaximalStaticExpanderWrapperPass, "polly-mse",
554 "Polly - Maximal static expansion of SCoP", false, false)
555

source code of polly/lib/Transform/MaximalStaticExpansion.cpp