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 Reads.insert_range(R: S.getValueUses(SAI));
143 return true;
144 } else if (SAI->isPHIKind()) {
145 auto Read = S.getPHIRead(SAI);
146
147 auto StmtDomain = isl::union_set(Read->getStatement()->getDomain());
148
149 auto Writes = S.getPHIIncomings(SAI);
150
151 // Get the domain where all the writes are writing to.
152 auto WriteDomain = isl::union_set::empty(ctx: S.getIslCtx());
153
154 for (auto Write : Writes) {
155 auto MapDeps = filterDependences(Dependences, MA: Write);
156 for (isl::map Map : MapDeps.get_map_list())
157 WriteDomain = WriteDomain.unite(uset2: Map.range());
158 }
159
160 // For now, read from original scalar is not possible.
161 if (!StmtDomain.is_equal(uset2: WriteDomain)) {
162 emitRemark(Msg: SAI->getName() + " read from its original value.",
163 Inst: Read->getAccessInstruction());
164 return false;
165 }
166
167 return true;
168 } else if (SAI->isExitPHIKind()) {
169 // For now, we are not able to expand ExitPhi.
170 emitRemark(Msg: SAI->getName() + " is a ExitPhi node.",
171 Inst: &*S.getEnteringBlock()->getFirstNonPHIIt());
172 return false;
173 }
174
175 int NumberWrites = 0;
176 for (ScopStmt &Stmt : S) {
177 auto StmtReads = isl::union_map::empty(ctx: S.getIslCtx());
178 auto StmtWrites = isl::union_map::empty(ctx: S.getIslCtx());
179
180 for (MemoryAccess *MA : Stmt) {
181 // Check if the current MemoryAccess involved the current SAI.
182 if (SAI != MA->getLatestScopArrayInfo())
183 continue;
184
185 // For now, we are not able to expand array where read come after write
186 // (to the same location) in a same statement.
187 auto AccRel = isl::union_map(MA->getAccessRelation());
188 if (MA->isRead()) {
189 // Reject load after store to same location.
190 if (!StmtWrites.is_disjoint(umap2: AccRel)) {
191 emitRemark(Msg: SAI->getName() + " has read after write to the same "
192 "element in same statement. The "
193 "dependences found during analysis may "
194 "be wrong because Polly is not able to "
195 "handle such case for now.",
196 Inst: MA->getAccessInstruction());
197 return false;
198 }
199
200 StmtReads = StmtReads.unite(umap2: AccRel);
201 } else {
202 StmtWrites = StmtWrites.unite(umap2: AccRel);
203 }
204
205 // For now, we are not able to expand MayWrite.
206 if (MA->isMayWrite()) {
207 emitRemark(Msg: SAI->getName() + " has a maywrite access.",
208 Inst: MA->getAccessInstruction());
209 return false;
210 }
211
212 // For now, we are not able to expand SAI with more than one write.
213 if (MA->isMustWrite()) {
214 Writes.insert(Ptr: MA);
215 NumberWrites++;
216 if (NumberWrites > 1) {
217 emitRemark(Msg: SAI->getName() + " has more than 1 write access.",
218 Inst: MA->getAccessInstruction());
219 return false;
220 }
221 }
222
223 // Check if it is possible to expand this read.
224 if (MA->isRead()) {
225 // Get the domain of the current ScopStmt.
226 auto StmtDomain = Stmt.getDomain();
227
228 // Get the domain of the future Read access.
229 auto ReadDomainSet = MA->getAccessRelation().domain();
230 auto ReadDomain = isl::union_set(ReadDomainSet);
231
232 // Get the dependences relevant for this MA
233 auto MapDependences = filterDependences(Dependences: Dependences.reverse(), MA);
234 unsigned NumberElementMap = isl_union_map_n_map(umap: MapDependences.get());
235
236 if (NumberElementMap == 0) {
237 emitRemark(Msg: "The expansion of " + SAI->getName() +
238 " would lead to a read from the original array.",
239 Inst: MA->getAccessInstruction());
240 return false;
241 }
242
243 auto DepsDomain = MapDependences.domain();
244
245 // If there are multiple maps in the Deps, we cannot handle this case
246 // for now.
247 if (NumberElementMap != 1) {
248 emitRemark(Msg: SAI->getName() +
249 " has too many dependences to be handle for now.",
250 Inst: MA->getAccessInstruction());
251 return false;
252 }
253
254 auto DepsDomainSet = isl::set(DepsDomain);
255
256 // For now, read from the original array is not possible.
257 if (!StmtDomain.is_subset(set2: DepsDomainSet)) {
258 emitRemark(Msg: "The expansion of " + SAI->getName() +
259 " would lead to a read from the original array.",
260 Inst: MA->getAccessInstruction());
261 return false;
262 }
263
264 Reads.insert(Ptr: MA);
265 }
266 }
267 }
268
269 // No need to expand SAI with no write.
270 if (NumberWrites == 0) {
271 emitRemark(Msg: SAI->getName() + " has 0 write access.",
272 Inst: &*S.getEnteringBlock()->getFirstNonPHIIt());
273 return false;
274 }
275
276 return true;
277 }
278
279 /// Expand the MemoryAccess according to Dependences and already expanded
280 /// MemoryAccesses.
281 ///
282 /// @param The SCop in which the memory access appears in.
283 /// @param The memory access that need to be expanded.
284 /// @param Dependences The RAW dependences of the SCop.
285 /// @param ExpandedSAI The expanded SAI created during write expansion.
286 /// @param Reverse if true, the Dependences union_map is reversed before
287 /// intersection.
288 void mapAccess(SmallPtrSetImpl<MemoryAccess *> &Accesses,
289 const isl::union_map &Dependences, ScopArrayInfo *ExpandedSAI,
290 bool Reverse) {
291 for (auto MA : Accesses) {
292 // Get the current AM.
293 auto CurrentAccessMap = MA->getAccessRelation();
294
295 // Get RAW dependences for the current WA.
296 auto DomainSet = MA->getAccessRelation().domain();
297 auto Domain = isl::union_set(DomainSet);
298
299 // Get the dependences relevant for this MA.
300 isl::union_map MapDependences =
301 filterDependences(Dependences: Reverse ? Dependences.reverse() : Dependences, MA);
302
303 // If no dependences, no need to modify anything.
304 if (MapDependences.is_empty())
305 return;
306
307 assert(isl_union_map_n_map(MapDependences.get()) == 1 &&
308 "There are more than one RAW dependencies in the union map.");
309 auto NewAccessMap = isl::map::from_union_map(umap: MapDependences);
310
311 auto Id = ExpandedSAI->getBasePtrId();
312
313 // Replace the out tuple id with the one of the access array.
314 NewAccessMap = NewAccessMap.set_tuple_id(type: isl::dim::out, id: Id);
315
316 // Set the new access relation.
317 MA->setNewAccessRelation(NewAccessMap);
318 }
319 }
320
321 /// Expand the MemoryAccess according to its domain.
322 ///
323 /// @param S The SCop in which the memory access appears in.
324 /// @param MA The memory access that need to be expanded.
325 ScopArrayInfo *expandAccess(MemoryAccess *MA) {
326 // Get the current AM.
327 auto CurrentAccessMap = MA->getAccessRelation();
328
329 unsigned in_dimensions =
330 unsignedFromIslSize(Size: CurrentAccessMap.domain_tuple_dim());
331
332 // Get domain from the current AM.
333 auto Domain = CurrentAccessMap.domain();
334
335 // Create a new AM from the domain.
336 auto NewAccessMap = isl::map::from_domain(set: Domain);
337
338 // Add dimensions to the new AM according to the current in_dim.
339 NewAccessMap = NewAccessMap.add_dims(type: isl::dim::out, n: in_dimensions);
340
341 // Create the string representing the name of the new SAI.
342 // One new SAI for each statement so that each write go to a different
343 // memory cell.
344 auto CurrentStmtDomain = MA->getStatement()->getDomain();
345 auto CurrentStmtName = CurrentStmtDomain.get_tuple_name();
346 auto CurrentOutId = CurrentAccessMap.get_tuple_id(type: isl::dim::out);
347 std::string CurrentOutIdString =
348 MA->getScopArrayInfo()->getName() + "_" + CurrentStmtName + "_expanded";
349
350 // Set the tuple id for the out dimension.
351 NewAccessMap = NewAccessMap.set_tuple_id(type: isl::dim::out, id: CurrentOutId);
352
353 // Create the size vector.
354 std::vector<unsigned> Sizes;
355 for (unsigned i = 0; i < in_dimensions; i++) {
356 assert(isDimBoundedByConstant(CurrentStmtDomain, i) &&
357 "Domain boundary are not constant.");
358 auto UpperBound = getConstant(PwAff: CurrentStmtDomain.dim_max(pos: i), Max: true, Min: false);
359 assert(!UpperBound.is_null() && UpperBound.is_pos() &&
360 !UpperBound.is_nan() &&
361 "The upper bound is not a positive integer.");
362 assert(UpperBound.le(isl::val(CurrentAccessMap.ctx(),
363 std::numeric_limits<int>::max() - 1)) &&
364 "The upper bound overflow a int.");
365 Sizes.push_back(x: UpperBound.get_num_si() + 1);
366 }
367
368 // Get the ElementType of the current SAI.
369 auto ElementType = MA->getLatestScopArrayInfo()->getElementType();
370
371 // Create (or get if already existing) the new expanded SAI.
372 auto ExpandedSAI =
373 S.createScopArrayInfo(ElementType, BaseName: CurrentOutIdString, Sizes);
374 ExpandedSAI->setIsOnHeap(true);
375
376 // Get the out Id of the expanded Array.
377 auto NewOutId = ExpandedSAI->getBasePtrId();
378
379 // Set the out id of the new AM to the new SAI id.
380 NewAccessMap = NewAccessMap.set_tuple_id(type: isl::dim::out, id: NewOutId);
381
382 // Add constraints to linked output with input id.
383 auto SpaceMap = NewAccessMap.get_space();
384 auto ConstraintBasicMap = isl::basic_map::equal(
385 space: SpaceMap, n_equal: unsignedFromIslSize(Size: SpaceMap.dim(type: isl::dim::in)));
386 NewAccessMap = isl::map(ConstraintBasicMap);
387
388 // Set the new access relation map.
389 MA->setNewAccessRelation(NewAccessMap);
390
391 return ExpandedSAI;
392 }
393
394 /// Expand PHI memory accesses.
395 ///
396 /// @param The SCop in which the memory access appears in.
397 /// @param The ScopArrayInfo representing the PHI accesses to expand.
398 /// @param Dependences The RAW dependences of the SCop.
399 void expandPhi(Scop &S, const ScopArrayInfo *SAI,
400 const isl::union_map &Dependences) {
401 SmallPtrSet<MemoryAccess *, 4> Writes(llvm::from_range,
402 S.getPHIIncomings(SAI));
403 auto Read = S.getPHIRead(SAI);
404 auto ExpandedSAI = expandAccess(MA: Read);
405
406 mapAccess(Accesses&: Writes, Dependences, ExpandedSAI, Reverse: false);
407 }
408
409public:
410 MaximalStaticExpansionImpl(Scop &S, isl::union_map &Dependences,
411 OptimizationRemarkEmitter &ORE)
412 : ORE(ORE), S(S), Dependences(Dependences) {}
413
414 /// Expand the accesses of the SCoP
415 ///
416 /// @param S The SCoP that must be expanded
417 /// @param D The dependencies information of SCoP
418 void expand() {
419 SmallVector<ScopArrayInfo *, 4> CurrentSAI(S.arrays().begin(),
420 S.arrays().end());
421 for (auto SAI : CurrentSAI) {
422 SmallPtrSet<MemoryAccess *, 4> AllWrites;
423 SmallPtrSet<MemoryAccess *, 4> AllReads;
424 if (!isExpandable(SAI, Writes&: AllWrites, Reads&: AllReads, S))
425 continue;
426
427 if (SAI->isValueKind() || SAI->isArrayKind()) {
428 assert(AllWrites.size() == 1 || SAI->isValueKind());
429
430 auto TheWrite = *(AllWrites.begin());
431 ScopArrayInfo *ExpandedArray = expandAccess(MA: TheWrite);
432
433 mapAccess(Accesses&: AllReads, Dependences, ExpandedSAI: ExpandedArray, Reverse: true);
434 } else if (SAI->isPHIKind()) {
435 expandPhi(S, SAI, Dependences);
436 }
437 }
438 }
439
440 /// Dump the internal information about a performed MSE to @p OS.
441 void print(llvm::raw_ostream &OS) {
442 OS << "After arrays {\n";
443
444 for (auto &Array : S.arrays())
445 Array->print(OS);
446
447 OS << "}\n";
448
449 OS << "After accesses {\n";
450 for (auto &Stmt : S) {
451 OS.indent(NumSpaces: 4) << Stmt.getBaseName() << "{\n";
452 for (auto *MA : Stmt)
453 MA->print(OS);
454 OS.indent(NumSpaces: 4) << "}\n";
455 }
456 OS << "}\n";
457 }
458};
459
460static std::unique_ptr<MaximalStaticExpansionImpl>
461runMaximalStaticExpansion(Scop &S, OptimizationRemarkEmitter &ORE,
462 const Dependences &D) {
463 auto Dependences = D.getDependences(Kinds: Dependences::TYPE_RAW);
464
465 std::unique_ptr<MaximalStaticExpansionImpl> Impl =
466 std::make_unique<MaximalStaticExpansionImpl>(args&: S, args&: Dependences, args&: ORE);
467
468 Impl->expand();
469 return Impl;
470}
471
472static PreservedAnalyses runMSEUsingNPM(Scop &S, ScopAnalysisManager &SAM,
473 ScopStandardAnalysisResults &SAR,
474 raw_ostream *OS) {
475 OptimizationRemarkEmitter ORE(&S.getFunction());
476
477 auto &DI = SAM.getResult<DependenceAnalysis>(IR&: S, ExtraArgs&: SAR);
478 auto &D = DI.getDependences(Level: Dependences::AL_Reference);
479
480 std::unique_ptr<MaximalStaticExpansionImpl> Impl =
481 runMaximalStaticExpansion(S, ORE, D);
482
483 if (OS) {
484 *OS << "Printing analysis 'Polly - Maximal static expansion of SCoP' for "
485 "region: '"
486 << S.getName() << "' in function '" << S.getFunction().getName()
487 << "':\n";
488
489 if (Impl) {
490 *OS << "MSE result:\n";
491 Impl->print(OS&: *OS);
492 }
493 }
494
495 return PreservedAnalyses::all();
496}
497
498} // namespace
499
500PreservedAnalyses
501MaximalStaticExpansionPass::run(Scop &S, ScopAnalysisManager &SAM,
502 ScopStandardAnalysisResults &SAR,
503 SPMUpdater &) {
504 return runMSEUsingNPM(S, SAM, SAR, OS: nullptr);
505}
506
507PreservedAnalyses
508MaximalStaticExpansionPrinterPass::run(Scop &S, ScopAnalysisManager &SAM,
509 ScopStandardAnalysisResults &SAR,
510 SPMUpdater &) {
511 return runMSEUsingNPM(S, SAM, SAR, OS: &OS);
512}
513
514char MaximalStaticExpanderWrapperPass::ID = 0;
515
516bool MaximalStaticExpanderWrapperPass::runOnScop(Scop &S) {
517 // Get the ORE from OptimizationRemarkEmitterWrapperPass.
518 OptimizationRemarkEmitter *ORE =
519 &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
520
521 // Get the RAW Dependences.
522 auto &DI = getAnalysis<DependenceInfo>();
523 auto &D = DI.getDependences(Level: Dependences::AL_Reference);
524
525 std::unique_ptr<MaximalStaticExpansionImpl> Impl =
526 runMaximalStaticExpansion(S, ORE&: *ORE, D);
527
528 return false;
529}
530
531void MaximalStaticExpanderWrapperPass::printScop(raw_ostream &OS,
532 Scop &S) const {
533 S.print(OS, PrintInstructions: false);
534}
535
536void MaximalStaticExpanderWrapperPass::getAnalysisUsage(
537 AnalysisUsage &AU) const {
538 ScopPass::getAnalysisUsage(AU);
539 AU.addRequired<DependenceInfo>();
540 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
541}
542
543Pass *polly::createMaximalStaticExpansionPass() {
544 return new MaximalStaticExpanderWrapperPass();
545}
546
547INITIALIZE_PASS_BEGIN(MaximalStaticExpanderWrapperPass, "polly-mse",
548 "Polly - Maximal static expansion of SCoP", false, false);
549INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
550INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass);
551INITIALIZE_PASS_END(MaximalStaticExpanderWrapperPass, "polly-mse",
552 "Polly - Maximal static expansion of SCoP", false, false)
553

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