1 //===- ScopInfo.cpp -------------------------------------------------------===//
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
7 //===----------------------------------------------------------------------===//
9 // Create a polyhedral description for a static control flow region.
11 // The pass creates a polyhedral description of the Scops detected by the Scop
12 // detection derived from their LLVM-IR code.
14 // This representation is shared among several tools in the polyhedral
15 // community, which are e.g. Cloog, Pluto, Loopo, Graphite.
17 //===----------------------------------------------------------------------===//
19 #include "polly/ScopInfo.h"
20 #include "polly/LinkAllPasses.h"
21 #include "polly/Options.h"
22 #include "polly/ScopBuilder.h"
23 #include "polly/ScopDetection.h"
24 #include "polly/Support/GICHelper.h"
25 #include "polly/Support/ISLOStream.h"
26 #include "polly/Support/ISLTools.h"
27 #include "polly/Support/SCEVAffinator.h"
28 #include "polly/Support/SCEVValidator.h"
29 #include "polly/Support/ScopHelper.h"
30 #include "llvm/ADT/APInt.h"
31 #include "llvm/ADT/ArrayRef.h"
32 #include "llvm/ADT/PostOrderIterator.h"
33 #include "llvm/ADT/SmallPtrSet.h"
34 #include "llvm/ADT/SmallSet.h"
35 #include "llvm/ADT/Statistic.h"
36 #include "llvm/Analysis/AliasAnalysis.h"
37 #include "llvm/Analysis/AssumptionCache.h"
38 #include "llvm/Analysis/Loads.h"
39 #include "llvm/Analysis/LoopInfo.h"
40 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
41 #include "llvm/Analysis/RegionInfo.h"
42 #include "llvm/Analysis/RegionIterator.h"
43 #include "llvm/Analysis/ScalarEvolution.h"
44 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
45 #include "llvm/IR/BasicBlock.h"
46 #include "llvm/IR/ConstantRange.h"
47 #include "llvm/IR/DataLayout.h"
48 #include "llvm/IR/DebugLoc.h"
49 #include "llvm/IR/Dominators.h"
50 #include "llvm/IR/Function.h"
51 #include "llvm/IR/InstrTypes.h"
52 #include "llvm/IR/Instruction.h"
53 #include "llvm/IR/Instructions.h"
54 #include "llvm/IR/Module.h"
55 #include "llvm/IR/PassManager.h"
56 #include "llvm/IR/Type.h"
57 #include "llvm/IR/Value.h"
58 #include "llvm/Support/Compiler.h"
59 #include "llvm/Support/Debug.h"
60 #include "llvm/Support/ErrorHandling.h"
61 #include "llvm/Support/raw_ostream.h"
63 #include "isl/local_space.h"
65 #include "isl/options.h"
70 using namespace polly
;
72 #define DEBUG_TYPE "polly-scops"
74 STATISTIC(AssumptionsAliasing
, "Number of aliasing assumptions taken.");
75 STATISTIC(AssumptionsInbounds
, "Number of inbounds assumptions taken.");
76 STATISTIC(AssumptionsWrapping
, "Number of wrapping assumptions taken.");
77 STATISTIC(AssumptionsUnsigned
, "Number of unsigned assumptions taken.");
78 STATISTIC(AssumptionsComplexity
, "Number of too complex SCoPs.");
79 STATISTIC(AssumptionsUnprofitable
, "Number of unprofitable SCoPs.");
80 STATISTIC(AssumptionsErrorBlock
, "Number of error block assumptions taken.");
81 STATISTIC(AssumptionsInfiniteLoop
, "Number of bounded loop assumptions taken.");
82 STATISTIC(AssumptionsInvariantLoad
,
83 "Number of invariant loads assumptions taken.");
84 STATISTIC(AssumptionsDelinearization
,
85 "Number of delinearization assumptions taken.");
87 STATISTIC(NumScops
, "Number of feasible SCoPs after ScopInfo");
88 STATISTIC(NumLoopsInScop
, "Number of loops in scops");
89 STATISTIC(NumBoxedLoops
, "Number of boxed loops in SCoPs after ScopInfo");
90 STATISTIC(NumAffineLoops
, "Number of affine loops in SCoPs after ScopInfo");
92 STATISTIC(NumScopsDepthZero
, "Number of scops with maximal loop depth 0");
93 STATISTIC(NumScopsDepthOne
, "Number of scops with maximal loop depth 1");
94 STATISTIC(NumScopsDepthTwo
, "Number of scops with maximal loop depth 2");
95 STATISTIC(NumScopsDepthThree
, "Number of scops with maximal loop depth 3");
96 STATISTIC(NumScopsDepthFour
, "Number of scops with maximal loop depth 4");
97 STATISTIC(NumScopsDepthFive
, "Number of scops with maximal loop depth 5");
98 STATISTIC(NumScopsDepthLarger
,
99 "Number of scops with maximal loop depth 6 and larger");
100 STATISTIC(MaxNumLoopsInScop
, "Maximal number of loops in scops");
102 STATISTIC(NumValueWrites
, "Number of scalar value writes after ScopInfo");
104 NumValueWritesInLoops
,
105 "Number of scalar value writes nested in affine loops after ScopInfo");
106 STATISTIC(NumPHIWrites
, "Number of scalar phi writes after ScopInfo");
107 STATISTIC(NumPHIWritesInLoops
,
108 "Number of scalar phi writes nested in affine loops after ScopInfo");
109 STATISTIC(NumSingletonWrites
, "Number of singleton writes after ScopInfo");
110 STATISTIC(NumSingletonWritesInLoops
,
111 "Number of singleton writes nested in affine loops after ScopInfo");
113 int const polly::MaxDisjunctsInDomain
= 20;
115 // The number of disjunct in the context after which we stop to add more
116 // disjuncts. This parameter is there to avoid exponential growth in the
117 // number of disjunct when adding non-convex sets to the context.
118 static int const MaxDisjunctsInContext
= 4;
120 static cl::opt
<bool> PollyRemarksMinimal(
121 "polly-remarks-minimal",
122 cl::desc("Do not emit remarks about assumptions that are known"),
123 cl::Hidden
, cl::ZeroOrMore
, cl::init(false), cl::cat(PollyCategory
));
126 IslOnErrorAbort("polly-on-isl-error-abort",
127 cl::desc("Abort if an isl error is encountered"),
128 cl::init(true), cl::cat(PollyCategory
));
130 static cl::opt
<bool> PollyPreciseInbounds(
131 "polly-precise-inbounds",
132 cl::desc("Take more precise inbounds assumptions (do not scale well)"),
133 cl::Hidden
, cl::init(false), cl::cat(PollyCategory
));
136 PollyIgnoreInbounds("polly-ignore-inbounds",
137 cl::desc("Do not take inbounds assumptions at all"),
138 cl::Hidden
, cl::init(false), cl::cat(PollyCategory
));
140 static cl::opt
<bool> PollyIgnoreParamBounds(
141 "polly-ignore-parameter-bounds",
143 "Do not add parameter bounds and do no gist simplify sets accordingly"),
144 cl::Hidden
, cl::init(false), cl::cat(PollyCategory
));
146 static cl::opt
<bool> PollyPreciseFoldAccesses(
147 "polly-precise-fold-accesses",
148 cl::desc("Fold memory accesses to model more possible delinearizations "
149 "(does not scale well)"),
150 cl::Hidden
, cl::init(false), cl::cat(PollyCategory
));
152 bool polly::UseInstructionNames
;
154 static cl::opt
<bool, true> XUseInstructionNames(
155 "polly-use-llvm-names",
156 cl::desc("Use LLVM-IR names when deriving statement names"),
157 cl::location(UseInstructionNames
), cl::Hidden
, cl::init(false),
158 cl::ZeroOrMore
, cl::cat(PollyCategory
));
160 static cl::opt
<bool> PollyPrintInstructions(
161 "polly-print-instructions", cl::desc("Output instructions per ScopStmt"),
162 cl::Hidden
, cl::Optional
, cl::init(false), cl::cat(PollyCategory
));
164 //===----------------------------------------------------------------------===//
166 static isl::set
addRangeBoundsToSet(isl::set S
, const ConstantRange
&Range
,
167 int dim
, isl::dim type
) {
169 isl::ctx Ctx
= S
.get_ctx();
171 // The upper and lower bound for a parameter value is derived either from
172 // the data type of the parameter or from the - possibly more restrictive -
174 V
= valFromAPInt(Ctx
.get(), Range
.getSignedMin(), true);
175 S
= S
.lower_bound_val(type
, dim
, V
);
176 V
= valFromAPInt(Ctx
.get(), Range
.getSignedMax(), true);
177 S
= S
.upper_bound_val(type
, dim
, V
);
179 if (Range
.isFullSet())
182 if (S
.n_basic_set() > MaxDisjunctsInContext
)
185 // In case of signed wrapping, we can refine the set of valid values by
186 // excluding the part not covered by the wrapping range.
187 if (Range
.isSignWrappedSet()) {
188 V
= valFromAPInt(Ctx
.get(), Range
.getLower(), true);
189 isl::set SLB
= S
.lower_bound_val(type
, dim
, V
);
191 V
= valFromAPInt(Ctx
.get(), Range
.getUpper(), true);
193 isl::set SUB
= S
.upper_bound_val(type
, dim
, V
);
200 static const ScopArrayInfo
*identifyBasePtrOriginSAI(Scop
*S
, Value
*BasePtr
) {
201 LoadInst
*BasePtrLI
= dyn_cast
<LoadInst
>(BasePtr
);
205 if (!S
->contains(BasePtrLI
))
208 ScalarEvolution
&SE
= *S
->getSE();
210 auto *OriginBaseSCEV
=
211 SE
.getPointerBase(SE
.getSCEV(BasePtrLI
->getPointerOperand()));
215 auto *OriginBaseSCEVUnknown
= dyn_cast
<SCEVUnknown
>(OriginBaseSCEV
);
216 if (!OriginBaseSCEVUnknown
)
219 return S
->getScopArrayInfo(OriginBaseSCEVUnknown
->getValue(),
223 ScopArrayInfo::ScopArrayInfo(Value
*BasePtr
, Type
*ElementType
, isl::ctx Ctx
,
224 ArrayRef
<const SCEV
*> Sizes
, MemoryKind Kind
,
225 const DataLayout
&DL
, Scop
*S
,
226 const char *BaseName
)
227 : BasePtr(BasePtr
), ElementType(ElementType
), Kind(Kind
), DL(DL
), S(*S
) {
228 std::string BasePtrName
=
230 : getIslCompatibleName("MemRef", BasePtr
, S
->getNextArrayIdx(),
231 Kind
== MemoryKind::PHI
? "__phi" : "",
232 UseInstructionNames
);
233 Id
= isl::id::alloc(Ctx
, BasePtrName
, this);
237 if (!BasePtr
|| Kind
!= MemoryKind::Array
) {
238 BasePtrOriginSAI
= nullptr;
242 BasePtrOriginSAI
= identifyBasePtrOriginSAI(S
, BasePtr
);
243 if (BasePtrOriginSAI
)
244 const_cast<ScopArrayInfo
*>(BasePtrOriginSAI
)->addDerivedSAI(this);
247 ScopArrayInfo::~ScopArrayInfo() = default;
249 isl::space
ScopArrayInfo::getSpace() const {
250 auto Space
= isl::space(Id
.get_ctx(), 0, getNumberOfDimensions());
251 Space
= Space
.set_tuple_id(isl::dim::set
, Id
);
255 bool ScopArrayInfo::isReadOnly() {
256 isl::union_set WriteSet
= S
.getWrites().range();
257 isl::space Space
= getSpace();
258 WriteSet
= WriteSet
.extract_set(Space
);
260 return bool(WriteSet
.is_empty());
263 bool ScopArrayInfo::isCompatibleWith(const ScopArrayInfo
*Array
) const {
264 if (Array
->getElementType() != getElementType())
267 if (Array
->getNumberOfDimensions() != getNumberOfDimensions())
270 for (unsigned i
= 0; i
< getNumberOfDimensions(); i
++)
271 if (Array
->getDimensionSize(i
) != getDimensionSize(i
))
277 void ScopArrayInfo::updateElementType(Type
*NewElementType
) {
278 if (NewElementType
== ElementType
)
281 auto OldElementSize
= DL
.getTypeAllocSizeInBits(ElementType
);
282 auto NewElementSize
= DL
.getTypeAllocSizeInBits(NewElementType
);
284 if (NewElementSize
== OldElementSize
|| NewElementSize
== 0)
287 if (NewElementSize
% OldElementSize
== 0 && NewElementSize
< OldElementSize
) {
288 ElementType
= NewElementType
;
290 auto GCD
= GreatestCommonDivisor64(NewElementSize
, OldElementSize
);
291 ElementType
= IntegerType::get(ElementType
->getContext(), GCD
);
295 /// Make the ScopArrayInfo model a Fortran Array
296 void ScopArrayInfo::applyAndSetFAD(Value
*FAD
) {
297 assert(FAD
&& "got invalid Fortran array descriptor");
299 assert(this->FAD
== FAD
&&
300 "receiving different array descriptors for same array");
304 assert(DimensionSizesPw
.size() > 0 && !DimensionSizesPw
[0]);
308 isl::space
Space(S
.getIslCtx(), 1, 0);
310 std::string param_name
= getName();
311 param_name
+= "_fortranarr_size";
312 isl::id IdPwAff
= isl::id::alloc(S
.getIslCtx(), param_name
, this);
314 Space
= Space
.set_dim_id(isl::dim::param
, 0, IdPwAff
);
316 isl::aff::var_on_domain(isl::local_space(Space
), isl::dim::param
, 0);
318 DimensionSizesPw
[0] = PwAff
;
321 bool ScopArrayInfo::updateSizes(ArrayRef
<const SCEV
*> NewSizes
,
322 bool CheckConsistency
) {
323 int SharedDims
= std::min(NewSizes
.size(), DimensionSizes
.size());
324 int ExtraDimsNew
= NewSizes
.size() - SharedDims
;
325 int ExtraDimsOld
= DimensionSizes
.size() - SharedDims
;
327 if (CheckConsistency
) {
328 for (int i
= 0; i
< SharedDims
; i
++) {
329 auto *NewSize
= NewSizes
[i
+ ExtraDimsNew
];
330 auto *KnownSize
= DimensionSizes
[i
+ ExtraDimsOld
];
331 if (NewSize
&& KnownSize
&& NewSize
!= KnownSize
)
335 if (DimensionSizes
.size() >= NewSizes
.size())
339 DimensionSizes
.clear();
340 DimensionSizes
.insert(DimensionSizes
.begin(), NewSizes
.begin(),
342 DimensionSizesPw
.clear();
343 for (const SCEV
*Expr
: DimensionSizes
) {
345 DimensionSizesPw
.push_back(nullptr);
348 isl::pw_aff Size
= S
.getPwAffOnly(Expr
);
349 DimensionSizesPw
.push_back(Size
);
354 std::string
ScopArrayInfo::getName() const { return Id
.get_name(); }
356 int ScopArrayInfo::getElemSizeInBytes() const {
357 return DL
.getTypeAllocSize(ElementType
);
360 isl::id
ScopArrayInfo::getBasePtrId() const { return Id
; }
362 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
363 LLVM_DUMP_METHOD
void ScopArrayInfo::dump() const { print(errs()); }
366 void ScopArrayInfo::print(raw_ostream
&OS
, bool SizeAsPwAff
) const {
367 OS
.indent(8) << *getElementType() << " " << getName();
369 // If this is a Fortran array, then we can print the outermost dimension
370 // as a isl_pw_aff even though there is no SCEV information.
371 bool IsOutermostSizeKnown
= SizeAsPwAff
&& FAD
;
373 if (!IsOutermostSizeKnown
&& getNumberOfDimensions() > 0 &&
374 !getDimensionSize(0)) {
378 for (; u
< getNumberOfDimensions(); u
++) {
382 isl::pw_aff Size
= getDimensionSizePw(u
);
383 OS
<< " " << Size
<< " ";
385 OS
<< *getDimensionSize(u
);
393 if (BasePtrOriginSAI
)
394 OS
<< " [BasePtrOrigin: " << BasePtrOriginSAI
->getName() << "]";
396 OS
<< " // Element size " << getElemSizeInBytes() << "\n";
399 const ScopArrayInfo
*
400 ScopArrayInfo::getFromAccessFunction(isl::pw_multi_aff PMA
) {
401 isl::id Id
= PMA
.get_tuple_id(isl::dim::out
);
402 assert(!Id
.is_null() && "Output dimension didn't have an ID");
403 return getFromId(Id
);
406 const ScopArrayInfo
*ScopArrayInfo::getFromId(isl::id Id
) {
407 void *User
= Id
.get_user();
408 const ScopArrayInfo
*SAI
= static_cast<ScopArrayInfo
*>(User
);
412 void MemoryAccess::wrapConstantDimensions() {
413 auto *SAI
= getScopArrayInfo();
414 isl::space ArraySpace
= SAI
->getSpace();
415 isl::ctx Ctx
= ArraySpace
.get_ctx();
416 unsigned DimsArray
= SAI
->getNumberOfDimensions();
418 isl::multi_aff DivModAff
= isl::multi_aff::identity(
419 ArraySpace
.map_from_domain_and_range(ArraySpace
));
420 isl::local_space LArraySpace
= isl::local_space(ArraySpace
);
422 // Begin with last dimension, to iteratively carry into higher dimensions.
423 for (int i
= DimsArray
- 1; i
> 0; i
--) {
424 auto *DimSize
= SAI
->getDimensionSize(i
);
425 auto *DimSizeCst
= dyn_cast
<SCEVConstant
>(DimSize
);
427 // This transformation is not applicable to dimensions with dynamic size.
431 // This transformation is not applicable to dimensions of size zero.
432 if (DimSize
->isZero())
435 isl::val DimSizeVal
=
436 valFromAPInt(Ctx
.get(), DimSizeCst
->getAPInt(), false);
437 isl::aff Var
= isl::aff::var_on_domain(LArraySpace
, isl::dim::set
, i
);
439 isl::aff::var_on_domain(LArraySpace
, isl::dim::set
, i
- 1);
441 // Compute: index % size
442 // Modulo must apply in the divide of the previous iteration, if any.
443 isl::aff Modulo
= Var
.mod(DimSizeVal
);
444 Modulo
= Modulo
.pullback(DivModAff
);
446 // Compute: floor(index / size)
447 isl::aff Divide
= Var
.div(isl::aff(LArraySpace
, DimSizeVal
));
448 Divide
= Divide
.floor();
449 Divide
= Divide
.add(PrevVar
);
450 Divide
= Divide
.pullback(DivModAff
);
452 // Apply Modulo and Divide.
453 DivModAff
= DivModAff
.set_aff(i
, Modulo
);
454 DivModAff
= DivModAff
.set_aff(i
- 1, Divide
);
457 // Apply all modulo/divides on the accesses.
458 isl::map Relation
= AccessRelation
;
459 Relation
= Relation
.apply_range(isl::map::from_multi_aff(DivModAff
));
460 Relation
= Relation
.detect_equalities();
461 AccessRelation
= Relation
;
464 void MemoryAccess::updateDimensionality() {
465 auto *SAI
= getScopArrayInfo();
466 isl::space ArraySpace
= SAI
->getSpace();
467 isl::space AccessSpace
= AccessRelation
.get_space().range();
468 isl::ctx Ctx
= ArraySpace
.get_ctx();
470 auto DimsArray
= ArraySpace
.dim(isl::dim::set
);
471 auto DimsAccess
= AccessSpace
.dim(isl::dim::set
);
472 auto DimsMissing
= DimsArray
- DimsAccess
;
474 auto *BB
= getStatement()->getEntryBlock();
475 auto &DL
= BB
->getModule()->getDataLayout();
476 unsigned ArrayElemSize
= SAI
->getElemSizeInBytes();
477 unsigned ElemBytes
= DL
.getTypeAllocSize(getElementType());
479 isl::map Map
= isl::map::from_domain_and_range(
480 isl::set::universe(AccessSpace
), isl::set::universe(ArraySpace
));
482 for (unsigned i
= 0; i
< DimsMissing
; i
++)
483 Map
= Map
.fix_si(isl::dim::out
, i
, 0);
485 for (unsigned i
= DimsMissing
; i
< DimsArray
; i
++)
486 Map
= Map
.equate(isl::dim::in
, i
- DimsMissing
, isl::dim::out
, i
);
488 AccessRelation
= AccessRelation
.apply_range(Map
);
490 // For the non delinearized arrays, divide the access function of the last
491 // subscript by the size of the elements in the array.
493 // A stride one array access in C expressed as A[i] is expressed in
494 // LLVM-IR as something like A[i * elementsize]. This hides the fact that
495 // two subsequent values of 'i' index two values that are stored next to
496 // each other in memory. By this division we make this characteristic
497 // obvious again. If the base pointer was accessed with offsets not divisible
498 // by the accesses element size, we will have chosen a smaller ArrayElemSize
499 // that divides the offsets of all accesses to this base pointer.
500 if (DimsAccess
== 1) {
501 isl::val V
= isl::val(Ctx
, ArrayElemSize
);
502 AccessRelation
= AccessRelation
.floordiv_val(V
);
505 // We currently do this only if we added at least one dimension, which means
506 // some dimension's indices have not been specified, an indicator that some
507 // index values have been added together.
508 // TODO: Investigate general usefulness; Effect on unit tests is to make index
509 // expressions more complicated.
511 wrapConstantDimensions();
514 computeBoundsOnAccessRelation(ArrayElemSize
);
516 // Introduce multi-element accesses in case the type loaded by this memory
517 // access is larger than the canonical element type of the array.
519 // An access ((float *)A)[i] to an array char *A is modeled as
520 // {[i] -> A[o] : 4 i <= o <= 4 i + 3
521 if (ElemBytes
> ArrayElemSize
) {
522 assert(ElemBytes
% ArrayElemSize
== 0 &&
523 "Loaded element size should be multiple of canonical element size");
524 isl::map Map
= isl::map::from_domain_and_range(
525 isl::set::universe(ArraySpace
), isl::set::universe(ArraySpace
));
526 for (unsigned i
= 0; i
< DimsArray
- 1; i
++)
527 Map
= Map
.equate(isl::dim::in
, i
, isl::dim::out
, i
);
532 LS
= isl::local_space(Map
.get_space());
533 int Num
= ElemBytes
/ getScopArrayInfo()->getElemSizeInBytes();
535 C
= isl::constraint::alloc_inequality(LS
);
536 C
= C
.set_constant_val(isl::val(Ctx
, Num
- 1));
537 C
= C
.set_coefficient_si(isl::dim::in
, DimsArray
- 1, 1);
538 C
= C
.set_coefficient_si(isl::dim::out
, DimsArray
- 1, -1);
539 Map
= Map
.add_constraint(C
);
541 C
= isl::constraint::alloc_inequality(LS
);
542 C
= C
.set_coefficient_si(isl::dim::in
, DimsArray
- 1, -1);
543 C
= C
.set_coefficient_si(isl::dim::out
, DimsArray
- 1, 1);
544 C
= C
.set_constant_val(isl::val(Ctx
, 0));
545 Map
= Map
.add_constraint(C
);
546 AccessRelation
= AccessRelation
.apply_range(Map
);
551 MemoryAccess::getReductionOperatorStr(MemoryAccess::ReductionType RT
) {
553 case MemoryAccess::RT_NONE
:
554 llvm_unreachable("Requested a reduction operator string for a memory "
555 "access which isn't a reduction");
556 case MemoryAccess::RT_ADD
:
558 case MemoryAccess::RT_MUL
:
560 case MemoryAccess::RT_BOR
:
562 case MemoryAccess::RT_BXOR
:
564 case MemoryAccess::RT_BAND
:
567 llvm_unreachable("Unknown reduction type");
570 const ScopArrayInfo
*MemoryAccess::getOriginalScopArrayInfo() const {
571 isl::id ArrayId
= getArrayId();
572 void *User
= ArrayId
.get_user();
573 const ScopArrayInfo
*SAI
= static_cast<ScopArrayInfo
*>(User
);
577 const ScopArrayInfo
*MemoryAccess::getLatestScopArrayInfo() const {
578 isl::id ArrayId
= getLatestArrayId();
579 void *User
= ArrayId
.get_user();
580 const ScopArrayInfo
*SAI
= static_cast<ScopArrayInfo
*>(User
);
584 isl::id
MemoryAccess::getOriginalArrayId() const {
585 return AccessRelation
.get_tuple_id(isl::dim::out
);
588 isl::id
MemoryAccess::getLatestArrayId() const {
589 if (!hasNewAccessRelation())
590 return getOriginalArrayId();
591 return NewAccessRelation
.get_tuple_id(isl::dim::out
);
594 isl::map
MemoryAccess::getAddressFunction() const {
595 return getAccessRelation().lexmin();
599 MemoryAccess::applyScheduleToAccessRelation(isl::union_map USchedule
) const {
600 isl::map Schedule
, ScheduledAccRel
;
601 isl::union_set UDomain
;
603 UDomain
= getStatement()->getDomain();
604 USchedule
= USchedule
.intersect_domain(UDomain
);
605 Schedule
= isl::map::from_union_map(USchedule
);
606 ScheduledAccRel
= getAddressFunction().apply_domain(Schedule
);
607 return isl::pw_multi_aff::from_map(ScheduledAccRel
);
610 isl::map
MemoryAccess::getOriginalAccessRelation() const {
611 return AccessRelation
;
614 std::string
MemoryAccess::getOriginalAccessRelationStr() const {
615 return AccessRelation
.to_str();
618 isl::space
MemoryAccess::getOriginalAccessRelationSpace() const {
619 return AccessRelation
.get_space();
622 isl::map
MemoryAccess::getNewAccessRelation() const {
623 return NewAccessRelation
;
626 std::string
MemoryAccess::getNewAccessRelationStr() const {
627 return NewAccessRelation
.to_str();
630 std::string
MemoryAccess::getAccessRelationStr() const {
631 return getAccessRelation().to_str();
634 isl::basic_map
MemoryAccess::createBasicAccessMap(ScopStmt
*Statement
) {
635 isl::space Space
= isl::space(Statement
->getIslCtx(), 0, 1);
636 Space
= Space
.align_params(Statement
->getDomainSpace());
638 return isl::basic_map::from_domain_and_range(
639 isl::basic_set::universe(Statement
->getDomainSpace()),
640 isl::basic_set::universe(Space
));
643 // Formalize no out-of-bound access assumption
645 // When delinearizing array accesses we optimistically assume that the
646 // delinearized accesses do not access out of bound locations (the subscript
647 // expression of each array evaluates for each statement instance that is
648 // executed to a value that is larger than zero and strictly smaller than the
649 // size of the corresponding dimension). The only exception is the outermost
650 // dimension for which we do not need to assume any upper bound. At this point
651 // we formalize this assumption to ensure that at code generation time the
652 // relevant run-time checks can be generated.
654 // To find the set of constraints necessary to avoid out of bound accesses, we
655 // first build the set of data locations that are not within array bounds. We
656 // then apply the reverse access relation to obtain the set of iterations that
657 // may contain invalid accesses and reduce this set of iterations to the ones
658 // that are actually executed by intersecting them with the domain of the
659 // statement. If we now project out all loop dimensions, we obtain a set of
660 // parameters that may cause statement instances to be executed that may
661 // possibly yield out of bound memory accesses. The complement of these
662 // constraints is the set of constraints that needs to be assumed to ensure such
663 // statement instances are never executed.
664 void MemoryAccess::assumeNoOutOfBound() {
665 if (PollyIgnoreInbounds
)
667 auto *SAI
= getScopArrayInfo();
668 isl::space Space
= getOriginalAccessRelationSpace().range();
669 isl::set Outside
= isl::set::empty(Space
);
670 for (int i
= 1, Size
= Space
.dim(isl::dim::set
); i
< Size
; ++i
) {
671 isl::local_space
LS(Space
);
672 isl::pw_aff Var
= isl::pw_aff::var_on_domain(LS
, isl::dim::set
, i
);
673 isl::pw_aff Zero
= isl::pw_aff(LS
);
675 isl::set DimOutside
= Var
.lt_set(Zero
);
676 isl::pw_aff SizeE
= SAI
->getDimensionSizePw(i
);
677 SizeE
= SizeE
.add_dims(isl::dim::in
, Space
.dim(isl::dim::set
));
678 SizeE
= SizeE
.set_tuple_id(isl::dim::in
, Space
.get_tuple_id(isl::dim::set
));
679 DimOutside
= DimOutside
.unite(SizeE
.le_set(Var
));
681 Outside
= Outside
.unite(DimOutside
);
684 Outside
= Outside
.apply(getAccessRelation().reverse());
685 Outside
= Outside
.intersect(Statement
->getDomain());
686 Outside
= Outside
.params();
688 // Remove divs to avoid the construction of overly complicated assumptions.
689 // Doing so increases the set of parameter combinations that are assumed to
690 // not appear. This is always save, but may make the resulting run-time check
691 // bail out more often than strictly necessary.
692 Outside
= Outside
.remove_divs();
693 Outside
= Outside
.complement();
694 const auto &Loc
= getAccessInstruction()
695 ? getAccessInstruction()->getDebugLoc()
697 if (!PollyPreciseInbounds
)
698 Outside
= Outside
.gist_params(Statement
->getDomain().params());
699 Statement
->getParent()->recordAssumption(INBOUNDS
, Outside
, Loc
,
703 void MemoryAccess::buildMemIntrinsicAccessRelation() {
704 assert(isMemoryIntrinsic());
705 assert(Subscripts
.size() == 2 && Sizes
.size() == 1);
707 isl::pw_aff SubscriptPWA
= getPwAff(Subscripts
[0]);
708 isl::map SubscriptMap
= isl::map::from_pw_aff(SubscriptPWA
);
711 if (Subscripts
[1] == nullptr) {
712 LengthMap
= isl::map::universe(SubscriptMap
.get_space());
714 isl::pw_aff LengthPWA
= getPwAff(Subscripts
[1]);
715 LengthMap
= isl::map::from_pw_aff(LengthPWA
);
716 isl::space RangeSpace
= LengthMap
.get_space().range();
717 LengthMap
= LengthMap
.apply_range(isl::map::lex_gt(RangeSpace
));
719 LengthMap
= LengthMap
.lower_bound_si(isl::dim::out
, 0, 0);
720 LengthMap
= LengthMap
.align_params(SubscriptMap
.get_space());
721 SubscriptMap
= SubscriptMap
.align_params(LengthMap
.get_space());
722 LengthMap
= LengthMap
.sum(SubscriptMap
);
724 LengthMap
.set_tuple_id(isl::dim::in
, getStatement()->getDomainId());
727 void MemoryAccess::computeBoundsOnAccessRelation(unsigned ElementSize
) {
728 ScalarEvolution
*SE
= Statement
->getParent()->getSE();
730 auto MAI
= MemAccInst(getAccessInstruction());
731 if (isa
<MemIntrinsic
>(MAI
))
734 Value
*Ptr
= MAI
.getPointerOperand();
735 if (!Ptr
|| !SE
->isSCEVable(Ptr
->getType()))
738 auto *PtrSCEV
= SE
->getSCEV(Ptr
);
739 if (isa
<SCEVCouldNotCompute
>(PtrSCEV
))
742 auto *BasePtrSCEV
= SE
->getPointerBase(PtrSCEV
);
743 if (BasePtrSCEV
&& !isa
<SCEVCouldNotCompute
>(BasePtrSCEV
))
744 PtrSCEV
= SE
->getMinusSCEV(PtrSCEV
, BasePtrSCEV
);
746 const ConstantRange
&Range
= SE
->getSignedRange(PtrSCEV
);
747 if (Range
.isFullSet())
750 if (Range
.isUpperWrapped() || Range
.isSignWrappedSet())
753 bool isWrapping
= Range
.isSignWrappedSet();
755 unsigned BW
= Range
.getBitWidth();
756 const auto One
= APInt(BW
, 1);
757 const auto LB
= isWrapping
? Range
.getLower() : Range
.getSignedMin();
758 const auto UB
= isWrapping
? (Range
.getUpper() - One
) : Range
.getSignedMax();
760 auto Min
= LB
.sdiv(APInt(BW
, ElementSize
));
761 auto Max
= UB
.sdiv(APInt(BW
, ElementSize
)) + One
;
763 assert(Min
.sle(Max
) && "Minimum expected to be less or equal than max");
765 isl::map Relation
= AccessRelation
;
766 isl::set AccessRange
= Relation
.range();
767 AccessRange
= addRangeBoundsToSet(AccessRange
, ConstantRange(Min
, Max
), 0,
769 AccessRelation
= Relation
.intersect_range(AccessRange
);
772 void MemoryAccess::foldAccessRelation() {
773 if (Sizes
.size() < 2 || isa
<SCEVConstant
>(Sizes
[1]))
776 int Size
= Subscripts
.size();
778 isl::map NewAccessRelation
= AccessRelation
;
780 for (int i
= Size
- 2; i
>= 0; --i
) {
782 isl::map MapOne
, MapTwo
;
783 isl::pw_aff DimSize
= getPwAff(Sizes
[i
+ 1]);
785 isl::space SpaceSize
= DimSize
.get_space();
786 isl::id ParamId
= SpaceSize
.get_dim_id(isl::dim::param
, 0);
788 Space
= AccessRelation
.get_space();
789 Space
= Space
.range().map_from_set();
790 Space
= Space
.align_params(SpaceSize
);
792 int ParamLocation
= Space
.find_dim_by_id(isl::dim::param
, ParamId
);
794 MapOne
= isl::map::universe(Space
);
795 for (int j
= 0; j
< Size
; ++j
)
796 MapOne
= MapOne
.equate(isl::dim::in
, j
, isl::dim::out
, j
);
797 MapOne
= MapOne
.lower_bound_si(isl::dim::in
, i
+ 1, 0);
799 MapTwo
= isl::map::universe(Space
);
800 for (int j
= 0; j
< Size
; ++j
)
801 if (j
< i
|| j
> i
+ 1)
802 MapTwo
= MapTwo
.equate(isl::dim::in
, j
, isl::dim::out
, j
);
804 isl::local_space
LS(Space
);
806 C
= isl::constraint::alloc_equality(LS
);
807 C
= C
.set_constant_si(-1);
808 C
= C
.set_coefficient_si(isl::dim::in
, i
, 1);
809 C
= C
.set_coefficient_si(isl::dim::out
, i
, -1);
810 MapTwo
= MapTwo
.add_constraint(C
);
811 C
= isl::constraint::alloc_equality(LS
);
812 C
= C
.set_coefficient_si(isl::dim::in
, i
+ 1, 1);
813 C
= C
.set_coefficient_si(isl::dim::out
, i
+ 1, -1);
814 C
= C
.set_coefficient_si(isl::dim::param
, ParamLocation
, 1);
815 MapTwo
= MapTwo
.add_constraint(C
);
816 MapTwo
= MapTwo
.upper_bound_si(isl::dim::in
, i
+ 1, -1);
818 MapOne
= MapOne
.unite(MapTwo
);
819 NewAccessRelation
= NewAccessRelation
.apply_range(MapOne
);
822 isl::id BaseAddrId
= getScopArrayInfo()->getBasePtrId();
823 isl::space Space
= Statement
->getDomainSpace();
824 NewAccessRelation
= NewAccessRelation
.set_tuple_id(
825 isl::dim::in
, Space
.get_tuple_id(isl::dim::set
));
826 NewAccessRelation
= NewAccessRelation
.set_tuple_id(isl::dim::out
, BaseAddrId
);
827 NewAccessRelation
= NewAccessRelation
.gist_domain(Statement
->getDomain());
829 // Access dimension folding might in certain cases increase the number of
830 // disjuncts in the memory access, which can possibly complicate the generated
831 // run-time checks and can lead to costly compilation.
832 if (!PollyPreciseFoldAccesses
&&
833 NewAccessRelation
.n_basic_map() > AccessRelation
.n_basic_map()) {
835 AccessRelation
= NewAccessRelation
;
839 void MemoryAccess::buildAccessRelation(const ScopArrayInfo
*SAI
) {
840 assert(AccessRelation
.is_null() && "AccessRelation already built");
842 // Initialize the invalid domain which describes all iterations for which the
843 // access relation is not modeled correctly.
844 isl::set StmtInvalidDomain
= getStatement()->getInvalidDomain();
845 InvalidDomain
= isl::set::empty(StmtInvalidDomain
.get_space());
847 isl::ctx Ctx
= Id
.get_ctx();
848 isl::id BaseAddrId
= SAI
->getBasePtrId();
850 if (getAccessInstruction() && isa
<MemIntrinsic
>(getAccessInstruction())) {
851 buildMemIntrinsicAccessRelation();
852 AccessRelation
= AccessRelation
.set_tuple_id(isl::dim::out
, BaseAddrId
);
857 // We overapproximate non-affine accesses with a possible access to the
858 // whole array. For read accesses it does not make a difference, if an
859 // access must or may happen. However, for write accesses it is important to
860 // differentiate between writes that must happen and writes that may happen.
861 if (AccessRelation
.is_null())
862 AccessRelation
= createBasicAccessMap(Statement
);
864 AccessRelation
= AccessRelation
.set_tuple_id(isl::dim::out
, BaseAddrId
);
868 isl::space Space
= isl::space(Ctx
, 0, Statement
->getNumIterators(), 0);
869 AccessRelation
= isl::map::universe(Space
);
871 for (int i
= 0, Size
= Subscripts
.size(); i
< Size
; ++i
) {
872 isl::pw_aff Affine
= getPwAff(Subscripts
[i
]);
873 isl::map SubscriptMap
= isl::map::from_pw_aff(Affine
);
874 AccessRelation
= AccessRelation
.flat_range_product(SubscriptMap
);
877 Space
= Statement
->getDomainSpace();
878 AccessRelation
= AccessRelation
.set_tuple_id(
879 isl::dim::in
, Space
.get_tuple_id(isl::dim::set
));
880 AccessRelation
= AccessRelation
.set_tuple_id(isl::dim::out
, BaseAddrId
);
882 AccessRelation
= AccessRelation
.gist_domain(Statement
->getDomain());
885 MemoryAccess::MemoryAccess(ScopStmt
*Stmt
, Instruction
*AccessInst
,
886 AccessType AccType
, Value
*BaseAddress
,
887 Type
*ElementType
, bool Affine
,
888 ArrayRef
<const SCEV
*> Subscripts
,
889 ArrayRef
<const SCEV
*> Sizes
, Value
*AccessValue
,
891 : Kind(Kind
), AccType(AccType
), Statement(Stmt
), InvalidDomain(nullptr),
892 BaseAddr(BaseAddress
), ElementType(ElementType
),
893 Sizes(Sizes
.begin(), Sizes
.end()), AccessInstruction(AccessInst
),
894 AccessValue(AccessValue
), IsAffine(Affine
),
895 Subscripts(Subscripts
.begin(), Subscripts
.end()), AccessRelation(nullptr),
896 NewAccessRelation(nullptr), FAD(nullptr) {
897 static const std::string TypeStrings
[] = {"", "_Read", "_Write", "_MayWrite"};
898 const std::string Access
= TypeStrings
[AccType
] + utostr(Stmt
->size());
900 std::string IdName
= Stmt
->getBaseName() + Access
;
901 Id
= isl::id::alloc(Stmt
->getParent()->getIslCtx(), IdName
, this);
904 MemoryAccess::MemoryAccess(ScopStmt
*Stmt
, AccessType AccType
, isl::map AccRel
)
905 : Kind(MemoryKind::Array
), AccType(AccType
), Statement(Stmt
),
906 InvalidDomain(nullptr), AccessRelation(nullptr),
907 NewAccessRelation(AccRel
), FAD(nullptr) {
908 isl::id ArrayInfoId
= NewAccessRelation
.get_tuple_id(isl::dim::out
);
909 auto *SAI
= ScopArrayInfo::getFromId(ArrayInfoId
);
910 Sizes
.push_back(nullptr);
911 for (unsigned i
= 1; i
< SAI
->getNumberOfDimensions(); i
++)
912 Sizes
.push_back(SAI
->getDimensionSize(i
));
913 ElementType
= SAI
->getElementType();
914 BaseAddr
= SAI
->getBasePtr();
915 static const std::string TypeStrings
[] = {"", "_Read", "_Write", "_MayWrite"};
916 const std::string Access
= TypeStrings
[AccType
] + utostr(Stmt
->size());
918 std::string IdName
= Stmt
->getBaseName() + Access
;
919 Id
= isl::id::alloc(Stmt
->getParent()->getIslCtx(), IdName
, this);
922 MemoryAccess::~MemoryAccess() = default;
924 void MemoryAccess::realignParams() {
925 isl::set Ctx
= Statement
->getParent()->getContext();
926 InvalidDomain
= InvalidDomain
.gist_params(Ctx
);
927 AccessRelation
= AccessRelation
.gist_params(Ctx
);
930 const std::string
MemoryAccess::getReductionOperatorStr() const {
931 return MemoryAccess::getReductionOperatorStr(getReductionType());
934 isl::id
MemoryAccess::getId() const { return Id
; }
936 raw_ostream
&polly::operator<<(raw_ostream
&OS
,
937 MemoryAccess::ReductionType RT
) {
938 if (RT
== MemoryAccess::RT_NONE
)
941 OS
<< MemoryAccess::getReductionOperatorStr(RT
);
945 void MemoryAccess::setFortranArrayDescriptor(Value
*FAD
) { this->FAD
= FAD
; }
947 void MemoryAccess::print(raw_ostream
&OS
) const {
950 OS
.indent(12) << "ReadAccess :=\t";
953 OS
.indent(12) << "MustWriteAccess :=\t";
956 OS
.indent(12) << "MayWriteAccess :=\t";
960 OS
<< "[Reduction Type: " << getReductionType() << "] ";
963 OS
<< "[Fortran array descriptor: " << FAD
->getName();
967 OS
<< "[Scalar: " << isScalarKind() << "]\n";
968 OS
.indent(16) << getOriginalAccessRelationStr() << ";\n";
969 if (hasNewAccessRelation())
970 OS
.indent(11) << "new: " << getNewAccessRelationStr() << ";\n";
973 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
974 LLVM_DUMP_METHOD
void MemoryAccess::dump() const { print(errs()); }
977 isl::pw_aff
MemoryAccess::getPwAff(const SCEV
*E
) {
978 auto *Stmt
= getStatement();
979 PWACtx PWAC
= Stmt
->getParent()->getPwAff(E
, Stmt
->getEntryBlock());
980 isl::set StmtDom
= getStatement()->getDomain();
981 StmtDom
= StmtDom
.reset_tuple_id();
982 isl::set NewInvalidDom
= StmtDom
.intersect(PWAC
.second
);
983 InvalidDomain
= InvalidDomain
.unite(NewInvalidDom
);
987 // Create a map in the size of the provided set domain, that maps from the
988 // one element of the provided set domain to another element of the provided
990 // The mapping is limited to all points that are equal in all but the last
991 // dimension and for which the last dimension of the input is strict smaller
992 // than the last dimension of the output.
994 // getEqualAndLarger(set[i0, i1, ..., iX]):
996 // set[i0, i1, ..., iX] -> set[o0, o1, ..., oX]
997 // : i0 = o0, i1 = o1, ..., i(X-1) = o(X-1), iX < oX
999 static isl::map
getEqualAndLarger(isl::space SetDomain
) {
1000 isl::space Space
= SetDomain
.map_from_set();
1001 isl::map Map
= isl::map::universe(Space
);
1002 unsigned lastDimension
= Map
.dim(isl::dim::in
) - 1;
1004 // Set all but the last dimension to be equal for the input and output
1006 // input[i0, i1, ..., iX] -> output[o0, o1, ..., oX]
1007 // : i0 = o0, i1 = o1, ..., i(X-1) = o(X-1)
1008 for (unsigned i
= 0; i
< lastDimension
; ++i
)
1009 Map
= Map
.equate(isl::dim::in
, i
, isl::dim::out
, i
);
1011 // Set the last dimension of the input to be strict smaller than the
1012 // last dimension of the output.
1014 // input[?,?,?,...,iX] -> output[?,?,?,...,oX] : iX < oX
1015 Map
= Map
.order_lt(isl::dim::in
, lastDimension
, isl::dim::out
, lastDimension
);
1019 isl::set
MemoryAccess::getStride(isl::map Schedule
) const {
1020 isl::map AccessRelation
= getAccessRelation();
1021 isl::space Space
= Schedule
.get_space().range();
1022 isl::map NextScatt
= getEqualAndLarger(Space
);
1024 Schedule
= Schedule
.reverse();
1025 NextScatt
= NextScatt
.lexmin();
1027 NextScatt
= NextScatt
.apply_range(Schedule
);
1028 NextScatt
= NextScatt
.apply_range(AccessRelation
);
1029 NextScatt
= NextScatt
.apply_domain(Schedule
);
1030 NextScatt
= NextScatt
.apply_domain(AccessRelation
);
1032 isl::set Deltas
= NextScatt
.deltas();
1036 bool MemoryAccess::isStrideX(isl::map Schedule
, int StrideWidth
) const {
1037 isl::set Stride
, StrideX
;
1040 Stride
= getStride(Schedule
);
1041 StrideX
= isl::set::universe(Stride
.get_space());
1042 for (unsigned i
= 0; i
< StrideX
.dim(isl::dim::set
) - 1; i
++)
1043 StrideX
= StrideX
.fix_si(isl::dim::set
, i
, 0);
1044 StrideX
= StrideX
.fix_si(isl::dim::set
, StrideX
.dim(isl::dim::set
) - 1,
1046 IsStrideX
= Stride
.is_subset(StrideX
);
1051 bool MemoryAccess::isStrideZero(isl::map Schedule
) const {
1052 return isStrideX(Schedule
, 0);
1055 bool MemoryAccess::isStrideOne(isl::map Schedule
) const {
1056 return isStrideX(Schedule
, 1);
1059 void MemoryAccess::setAccessRelation(isl::map NewAccess
) {
1060 AccessRelation
= NewAccess
;
1063 void MemoryAccess::setNewAccessRelation(isl::map NewAccess
) {
1067 // Check domain space compatibility.
1068 isl::space NewSpace
= NewAccess
.get_space();
1069 isl::space NewDomainSpace
= NewSpace
.domain();
1070 isl::space OriginalDomainSpace
= getStatement()->getDomainSpace();
1071 assert(OriginalDomainSpace
.has_equal_tuples(NewDomainSpace
));
1073 // Reads must be executed unconditionally. Writes might be executed in a
1076 // Check whether there is an access for every statement instance.
1077 isl::set StmtDomain
= getStatement()->getDomain();
1079 StmtDomain
.intersect_params(getStatement()->getParent()->getContext());
1080 isl::set NewDomain
= NewAccess
.domain();
1081 assert(StmtDomain
.is_subset(NewDomain
) &&
1082 "Partial READ accesses not supported");
1085 isl::space NewAccessSpace
= NewAccess
.get_space();
1086 assert(NewAccessSpace
.has_tuple_id(isl::dim::set
) &&
1087 "Must specify the array that is accessed");
1088 isl::id NewArrayId
= NewAccessSpace
.get_tuple_id(isl::dim::set
);
1089 auto *SAI
= static_cast<ScopArrayInfo
*>(NewArrayId
.get_user());
1090 assert(SAI
&& "Must set a ScopArrayInfo");
1092 if (SAI
->isArrayKind() && SAI
->getBasePtrOriginSAI()) {
1093 InvariantEquivClassTy
*EqClass
=
1094 getStatement()->getParent()->lookupInvariantEquivClass(
1097 "Access functions to indirect arrays must have an invariant and "
1098 "hoisted base pointer");
1101 // Check whether access dimensions correspond to number of dimensions of the
1103 auto Dims
= SAI
->getNumberOfDimensions();
1104 assert(NewAccessSpace
.dim(isl::dim::set
) == Dims
&&
1105 "Access dims must match array dims");
1108 NewAccess
= NewAccess
.gist_domain(getStatement()->getDomain());
1109 NewAccessRelation
= NewAccess
;
1112 bool MemoryAccess::isLatestPartialAccess() const {
1113 isl::set StmtDom
= getStatement()->getDomain();
1114 isl::set AccDom
= getLatestAccessRelation().domain();
1116 return !StmtDom
.is_subset(AccDom
);
1119 //===----------------------------------------------------------------------===//
1121 isl::map
ScopStmt::getSchedule() const {
1122 isl::set Domain
= getDomain();
1123 if (Domain
.is_empty())
1124 return isl::map::from_aff(isl::aff(isl::local_space(getDomainSpace())));
1125 auto Schedule
= getParent()->getSchedule();
1128 Schedule
= Schedule
.intersect_domain(isl::union_set(Domain
));
1129 if (Schedule
.is_empty())
1130 return isl::map::from_aff(isl::aff(isl::local_space(getDomainSpace())));
1131 isl::map M
= M
.from_union_map(Schedule
);
1133 M
= M
.gist_domain(Domain
);
1138 void ScopStmt::restrictDomain(isl::set NewDomain
) {
1139 assert(NewDomain
.is_subset(Domain
) &&
1140 "New domain is not a subset of old domain!");
1144 void ScopStmt::addAccess(MemoryAccess
*Access
, bool Prepend
) {
1145 Instruction
*AccessInst
= Access
->getAccessInstruction();
1147 if (Access
->isArrayKind()) {
1148 MemoryAccessList
&MAL
= InstructionToAccess
[AccessInst
];
1149 MAL
.emplace_front(Access
);
1150 } else if (Access
->isValueKind() && Access
->isWrite()) {
1151 Instruction
*AccessVal
= cast
<Instruction
>(Access
->getAccessValue());
1152 assert(!ValueWrites
.lookup(AccessVal
));
1154 ValueWrites
[AccessVal
] = Access
;
1155 } else if (Access
->isValueKind() && Access
->isRead()) {
1156 Value
*AccessVal
= Access
->getAccessValue();
1157 assert(!ValueReads
.lookup(AccessVal
));
1159 ValueReads
[AccessVal
] = Access
;
1160 } else if (Access
->isAnyPHIKind() && Access
->isWrite()) {
1161 PHINode
*PHI
= cast
<PHINode
>(Access
->getAccessValue());
1162 assert(!PHIWrites
.lookup(PHI
));
1164 PHIWrites
[PHI
] = Access
;
1165 } else if (Access
->isAnyPHIKind() && Access
->isRead()) {
1166 PHINode
*PHI
= cast
<PHINode
>(Access
->getAccessValue());
1167 assert(!PHIReads
.lookup(PHI
));
1169 PHIReads
[PHI
] = Access
;
1173 MemAccs
.insert(MemAccs
.begin(), Access
);
1176 MemAccs
.push_back(Access
);
1179 void ScopStmt::realignParams() {
1180 for (MemoryAccess
*MA
: *this)
1181 MA
->realignParams();
1183 isl::set Ctx
= Parent
.getContext();
1184 InvalidDomain
= InvalidDomain
.gist_params(Ctx
);
1185 Domain
= Domain
.gist_params(Ctx
);
1188 ScopStmt::ScopStmt(Scop
&parent
, Region
&R
, StringRef Name
,
1189 Loop
*SurroundingLoop
,
1190 std::vector
<Instruction
*> EntryBlockInstructions
)
1191 : Parent(parent
), InvalidDomain(nullptr), Domain(nullptr), R(&R
),
1192 Build(nullptr), BaseName(Name
), SurroundingLoop(SurroundingLoop
),
1193 Instructions(EntryBlockInstructions
) {}
1195 ScopStmt::ScopStmt(Scop
&parent
, BasicBlock
&bb
, StringRef Name
,
1196 Loop
*SurroundingLoop
,
1197 std::vector
<Instruction
*> Instructions
)
1198 : Parent(parent
), InvalidDomain(nullptr), Domain(nullptr), BB(&bb
),
1199 Build(nullptr), BaseName(Name
), SurroundingLoop(SurroundingLoop
),
1200 Instructions(Instructions
) {}
1202 ScopStmt::ScopStmt(Scop
&parent
, isl::map SourceRel
, isl::map TargetRel
,
1204 : Parent(parent
), InvalidDomain(nullptr), Domain(NewDomain
),
1206 BaseName
= getIslCompatibleName("CopyStmt_", "",
1207 std::to_string(parent
.getCopyStmtsNum()));
1208 isl::id Id
= isl::id::alloc(getIslCtx(), getBaseName(), this);
1209 Domain
= Domain
.set_tuple_id(Id
);
1210 TargetRel
= TargetRel
.set_tuple_id(isl::dim::in
, Id
);
1212 new MemoryAccess(this, MemoryAccess::AccessType::MUST_WRITE
, TargetRel
);
1213 parent
.addAccessFunction(Access
);
1215 SourceRel
= SourceRel
.set_tuple_id(isl::dim::in
, Id
);
1216 Access
= new MemoryAccess(this, MemoryAccess::AccessType::READ
, SourceRel
);
1217 parent
.addAccessFunction(Access
);
1221 ScopStmt::~ScopStmt() = default;
1223 std::string
ScopStmt::getDomainStr() const { return Domain
.to_str(); }
1225 std::string
ScopStmt::getScheduleStr() const {
1226 auto *S
= getSchedule().release();
1229 auto Str
= stringFromIslObj(S
);
1234 void ScopStmt::setInvalidDomain(isl::set ID
) { InvalidDomain
= ID
; }
1236 BasicBlock
*ScopStmt::getEntryBlock() const {
1238 return getBasicBlock();
1239 return getRegion()->getEntry();
1242 unsigned ScopStmt::getNumIterators() const { return NestLoops
.size(); }
1244 const char *ScopStmt::getBaseName() const { return BaseName
.c_str(); }
1246 Loop
*ScopStmt::getLoopForDimension(unsigned Dimension
) const {
1247 return NestLoops
[Dimension
];
1250 isl::ctx
ScopStmt::getIslCtx() const { return Parent
.getIslCtx(); }
1252 isl::set
ScopStmt::getDomain() const { return Domain
; }
1254 isl::space
ScopStmt::getDomainSpace() const { return Domain
.get_space(); }
1256 isl::id
ScopStmt::getDomainId() const { return Domain
.get_tuple_id(); }
1258 void ScopStmt::printInstructions(raw_ostream
&OS
) const {
1259 OS
<< "Instructions {\n";
1261 for (Instruction
*Inst
: Instructions
)
1262 OS
.indent(16) << *Inst
<< "\n";
1264 OS
.indent(12) << "}\n";
1267 void ScopStmt::print(raw_ostream
&OS
, bool PrintInstructions
) const {
1268 OS
<< "\t" << getBaseName() << "\n";
1269 OS
.indent(12) << "Domain :=\n";
1272 OS
.indent(16) << getDomainStr() << ";\n";
1274 OS
.indent(16) << "n/a\n";
1276 OS
.indent(12) << "Schedule :=\n";
1279 OS
.indent(16) << getScheduleStr() << ";\n";
1281 OS
.indent(16) << "n/a\n";
1283 for (MemoryAccess
*Access
: MemAccs
)
1286 if (PrintInstructions
)
1287 printInstructions(OS
.indent(12));
1290 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1291 LLVM_DUMP_METHOD
void ScopStmt::dump() const { print(dbgs(), true); }
1294 void ScopStmt::removeAccessData(MemoryAccess
*MA
) {
1295 if (MA
->isRead() && MA
->isOriginalValueKind()) {
1296 bool Found
= ValueReads
.erase(MA
->getAccessValue());
1298 assert(Found
&& "Expected access data not found");
1300 if (MA
->isWrite() && MA
->isOriginalValueKind()) {
1301 bool Found
= ValueWrites
.erase(cast
<Instruction
>(MA
->getAccessValue()));
1303 assert(Found
&& "Expected access data not found");
1305 if (MA
->isWrite() && MA
->isOriginalAnyPHIKind()) {
1306 bool Found
= PHIWrites
.erase(cast
<PHINode
>(MA
->getAccessInstruction()));
1308 assert(Found
&& "Expected access data not found");
1310 if (MA
->isRead() && MA
->isOriginalAnyPHIKind()) {
1311 bool Found
= PHIReads
.erase(cast
<PHINode
>(MA
->getAccessInstruction()));
1313 assert(Found
&& "Expected access data not found");
1317 void ScopStmt::removeMemoryAccess(MemoryAccess
*MA
) {
1318 // Remove the memory accesses from this statement together with all scalar
1319 // accesses that were caused by it. MemoryKind::Value READs have no access
1320 // instruction, hence would not be removed by this function. However, it is
1321 // only used for invariant LoadInst accesses, its arguments are always affine,
1322 // hence synthesizable, and therefore there are no MemoryKind::Value READ
1323 // accesses to be removed.
1324 auto Predicate
= [&](MemoryAccess
*Acc
) {
1325 return Acc
->getAccessInstruction() == MA
->getAccessInstruction();
1327 for (auto *MA
: MemAccs
) {
1328 if (Predicate(MA
)) {
1329 removeAccessData(MA
);
1330 Parent
.removeAccessData(MA
);
1333 MemAccs
.erase(std::remove_if(MemAccs
.begin(), MemAccs
.end(), Predicate
),
1335 InstructionToAccess
.erase(MA
->getAccessInstruction());
1338 void ScopStmt::removeSingleMemoryAccess(MemoryAccess
*MA
, bool AfterHoisting
) {
1339 if (AfterHoisting
) {
1340 auto MAIt
= std::find(MemAccs
.begin(), MemAccs
.end(), MA
);
1341 assert(MAIt
!= MemAccs
.end());
1342 MemAccs
.erase(MAIt
);
1344 removeAccessData(MA
);
1345 Parent
.removeAccessData(MA
);
1348 auto It
= InstructionToAccess
.find(MA
->getAccessInstruction());
1349 if (It
!= InstructionToAccess
.end()) {
1350 It
->second
.remove(MA
);
1351 if (It
->second
.empty())
1352 InstructionToAccess
.erase(MA
->getAccessInstruction());
1356 MemoryAccess
*ScopStmt::ensureValueRead(Value
*V
) {
1357 MemoryAccess
*Access
= lookupInputAccessOf(V
);
1361 ScopArrayInfo
*SAI
=
1362 Parent
.getOrCreateScopArrayInfo(V
, V
->getType(), {}, MemoryKind::Value
);
1363 Access
= new MemoryAccess(this, nullptr, MemoryAccess::READ
, V
, V
->getType(),
1364 true, {}, {}, V
, MemoryKind::Value
);
1365 Parent
.addAccessFunction(Access
);
1366 Access
->buildAccessRelation(SAI
);
1368 Parent
.addAccessData(Access
);
1372 raw_ostream
&polly::operator<<(raw_ostream
&OS
, const ScopStmt
&S
) {
1373 S
.print(OS
, PollyPrintInstructions
);
1377 //===----------------------------------------------------------------------===//
1378 /// Scop class implement
1380 void Scop::setContext(isl::set NewContext
) {
1381 Context
= NewContext
.align_params(Context
.get_space());
1386 /// Remap parameter values but keep AddRecs valid wrt. invariant loads.
1387 struct SCEVSensitiveParameterRewriter
1388 : public SCEVRewriteVisitor
<SCEVSensitiveParameterRewriter
> {
1389 const ValueToValueMap
&VMap
;
1392 SCEVSensitiveParameterRewriter(const ValueToValueMap
&VMap
,
1393 ScalarEvolution
&SE
)
1394 : SCEVRewriteVisitor(SE
), VMap(VMap
) {}
1396 static const SCEV
*rewrite(const SCEV
*E
, ScalarEvolution
&SE
,
1397 const ValueToValueMap
&VMap
) {
1398 SCEVSensitiveParameterRewriter
SSPR(VMap
, SE
);
1399 return SSPR
.visit(E
);
1402 const SCEV
*visitAddRecExpr(const SCEVAddRecExpr
*E
) {
1403 auto *Start
= visit(E
->getStart());
1404 auto *AddRec
= SE
.getAddRecExpr(SE
.getConstant(E
->getType(), 0),
1405 visit(E
->getStepRecurrence(SE
)),
1406 E
->getLoop(), SCEV::FlagAnyWrap
);
1407 return SE
.getAddExpr(Start
, AddRec
);
1410 const SCEV
*visitUnknown(const SCEVUnknown
*E
) {
1411 if (auto *NewValue
= VMap
.lookup(E
->getValue()))
1412 return SE
.getUnknown(NewValue
);
1417 /// Check whether we should remap a SCEV expression.
1418 struct SCEVFindInsideScop
: public SCEVTraversal
<SCEVFindInsideScop
> {
1419 const ValueToValueMap
&VMap
;
1420 bool FoundInside
= false;
1424 SCEVFindInsideScop(const ValueToValueMap
&VMap
, ScalarEvolution
&SE
,
1426 : SCEVTraversal(*this), VMap(VMap
), S(S
) {}
1428 static bool hasVariant(const SCEV
*E
, ScalarEvolution
&SE
,
1429 const ValueToValueMap
&VMap
, const Scop
*S
) {
1430 SCEVFindInsideScop
SFIS(VMap
, SE
, S
);
1432 return SFIS
.FoundInside
;
1435 bool follow(const SCEV
*E
) {
1436 if (auto *AddRec
= dyn_cast
<SCEVAddRecExpr
>(E
)) {
1437 FoundInside
|= S
->getRegion().contains(AddRec
->getLoop());
1438 } else if (auto *Unknown
= dyn_cast
<SCEVUnknown
>(E
)) {
1439 if (Instruction
*I
= dyn_cast
<Instruction
>(Unknown
->getValue()))
1440 FoundInside
|= S
->getRegion().contains(I
) && !VMap
.count(I
);
1442 return !FoundInside
;
1445 bool isDone() { return FoundInside
; }
1447 } // end anonymous namespace
1449 const SCEV
*Scop::getRepresentingInvariantLoadSCEV(const SCEV
*E
) const {
1450 // Check whether it makes sense to rewrite the SCEV. (ScalarEvolution
1451 // doesn't like addition between an AddRec and an expression that
1452 // doesn't have a dominance relationship with it.)
1453 if (SCEVFindInsideScop::hasVariant(E
, *SE
, InvEquivClassVMap
, this))
1457 return SCEVSensitiveParameterRewriter::rewrite(E
, *SE
, InvEquivClassVMap
);
1460 // This table of function names is used to translate parameter names in more
1461 // human-readable names. This makes it easier to interpret Polly analysis
1463 StringMap
<std::string
> KnownNames
= {
1464 {"_Z13get_global_idj", "global_id"},
1465 {"_Z12get_local_idj", "local_id"},
1466 {"_Z15get_global_sizej", "global_size"},
1467 {"_Z14get_local_sizej", "local_size"},
1468 {"_Z12get_work_dimv", "work_dim"},
1469 {"_Z17get_global_offsetj", "global_offset"},
1470 {"_Z12get_group_idj", "group_id"},
1471 {"_Z14get_num_groupsj", "num_groups"},
1474 static std::string
getCallParamName(CallInst
*Call
) {
1476 raw_string_ostream
OS(Result
);
1477 std::string Name
= Call
->getCalledFunction()->getName();
1479 auto Iterator
= KnownNames
.find(Name
);
1480 if (Iterator
!= KnownNames
.end())
1481 Name
= "__" + Iterator
->getValue();
1483 for (auto &Operand
: Call
->arg_operands()) {
1484 ConstantInt
*Op
= cast
<ConstantInt
>(&Operand
);
1485 OS
<< "_" << Op
->getValue();
1491 void Scop::createParameterId(const SCEV
*Parameter
) {
1492 assert(Parameters
.count(Parameter
));
1493 assert(!ParameterIds
.count(Parameter
));
1495 std::string ParameterName
= "p_" + std::to_string(getNumParams() - 1);
1497 if (const SCEVUnknown
*ValueParameter
= dyn_cast
<SCEVUnknown
>(Parameter
)) {
1498 Value
*Val
= ValueParameter
->getValue();
1499 CallInst
*Call
= dyn_cast
<CallInst
>(Val
);
1501 if (Call
&& isConstCall(Call
)) {
1502 ParameterName
= getCallParamName(Call
);
1503 } else if (UseInstructionNames
) {
1504 // If this parameter references a specific Value and this value has a name
1505 // we use this name as it is likely to be unique and more useful than just
1508 ParameterName
= Val
->getName();
1509 else if (LoadInst
*LI
= dyn_cast
<LoadInst
>(Val
)) {
1510 auto *LoadOrigin
= LI
->getPointerOperand()->stripInBoundsOffsets();
1511 if (LoadOrigin
->hasName()) {
1512 ParameterName
+= "_loaded_from_";
1514 LI
->getPointerOperand()->stripInBoundsOffsets()->getName();
1519 ParameterName
= getIslCompatibleName("", ParameterName
, "");
1522 isl::id Id
= isl::id::alloc(getIslCtx(), ParameterName
,
1523 const_cast<void *>((const void *)Parameter
));
1524 ParameterIds
[Parameter
] = Id
;
1527 void Scop::addParams(const ParameterSetTy
&NewParameters
) {
1528 for (const SCEV
*Parameter
: NewParameters
) {
1529 // Normalize the SCEV to get the representing element for an invariant load.
1530 Parameter
= extractConstantFactor(Parameter
, *SE
).second
;
1531 Parameter
= getRepresentingInvariantLoadSCEV(Parameter
);
1533 if (Parameters
.insert(Parameter
))
1534 createParameterId(Parameter
);
1538 isl::id
Scop::getIdForParam(const SCEV
*Parameter
) const {
1539 // Normalize the SCEV to get the representing element for an invariant load.
1540 Parameter
= getRepresentingInvariantLoadSCEV(Parameter
);
1541 return ParameterIds
.lookup(Parameter
);
1544 bool Scop::isDominatedBy(const DominatorTree
&DT
, BasicBlock
*BB
) const {
1545 return DT
.dominates(BB
, getEntry());
1548 void Scop::buildContext() {
1549 isl::space Space
= isl::space::params_alloc(getIslCtx(), 0);
1550 Context
= isl::set::universe(Space
);
1551 InvalidContext
= isl::set::empty(Space
);
1552 AssumedContext
= isl::set::universe(Space
);
1555 void Scop::addParameterBounds() {
1557 for (auto *Parameter
: Parameters
) {
1558 ConstantRange SRange
= SE
->getSignedRange(Parameter
);
1559 Context
= addRangeBoundsToSet(Context
, SRange
, PDim
++, isl::dim::param
);
1563 static std::vector
<isl::id
> getFortranArrayIds(Scop::array_range Arrays
) {
1564 std::vector
<isl::id
> OutermostSizeIds
;
1565 for (auto Array
: Arrays
) {
1566 // To check if an array is a Fortran array, we check if it has a isl_pw_aff
1567 // for its outermost dimension. Fortran arrays will have this since the
1568 // outermost dimension size can be picked up from their runtime description.
1569 // TODO: actually need to check if it has a FAD, but for now this works.
1570 if (Array
->getNumberOfDimensions() > 0) {
1571 isl::pw_aff PwAff
= Array
->getDimensionSizePw(0);
1575 isl::id Id
= PwAff
.get_dim_id(isl::dim::param
, 0);
1576 assert(!Id
.is_null() &&
1577 "Invalid Id for PwAff expression in Fortran array");
1578 OutermostSizeIds
.push_back(Id
);
1581 return OutermostSizeIds
;
1584 // The FORTRAN array size parameters are known to be non-negative.
1585 static isl::set
boundFortranArrayParams(isl::set Context
,
1586 Scop::array_range Arrays
) {
1587 std::vector
<isl::id
> OutermostSizeIds
;
1588 OutermostSizeIds
= getFortranArrayIds(Arrays
);
1590 for (isl::id Id
: OutermostSizeIds
) {
1591 int dim
= Context
.find_dim_by_id(isl::dim::param
, Id
);
1592 Context
= Context
.lower_bound_si(isl::dim::param
, dim
, 0);
1598 void Scop::realignParams() {
1599 if (PollyIgnoreParamBounds
)
1602 // Add all parameters into a common model.
1603 isl::space Space
= getFullParamSpace();
1605 // Align the parameters of all data structures to the model.
1606 Context
= Context
.align_params(Space
);
1608 // Bound the size of the fortran array dimensions.
1609 Context
= boundFortranArrayParams(Context
, arrays());
1611 // As all parameters are known add bounds to them.
1612 addParameterBounds();
1614 for (ScopStmt
&Stmt
: *this)
1615 Stmt
.realignParams();
1616 // Simplify the schedule according to the context too.
1617 Schedule
= Schedule
.gist_domain_params(getContext());
1620 static isl::set
simplifyAssumptionContext(isl::set AssumptionContext
,
1622 // If we have modeled all blocks in the SCoP that have side effects we can
1623 // simplify the context with the constraints that are needed for anything to
1624 // be executed at all. However, if we have error blocks in the SCoP we already
1625 // assumed some parameter combinations cannot occur and removed them from the
1626 // domains, thus we cannot use the remaining domain to simplify the
1628 if (!S
.hasErrorBlock()) {
1629 auto DomainParameters
= S
.getDomains().params();
1630 AssumptionContext
= AssumptionContext
.gist_params(DomainParameters
);
1633 AssumptionContext
= AssumptionContext
.gist_params(S
.getContext());
1634 return AssumptionContext
;
1637 void Scop::simplifyContexts() {
1638 // The parameter constraints of the iteration domains give us a set of
1639 // constraints that need to hold for all cases where at least a single
1640 // statement iteration is executed in the whole scop. We now simplify the
1641 // assumed context under the assumption that such constraints hold and at
1642 // least a single statement iteration is executed. For cases where no
1643 // statement instances are executed, the assumptions we have taken about
1644 // the executed code do not matter and can be changed.
1646 // WARNING: This only holds if the assumptions we have taken do not reduce
1647 // the set of statement instances that are executed. Otherwise we
1648 // may run into a case where the iteration domains suggest that
1649 // for a certain set of parameter constraints no code is executed,
1650 // but in the original program some computation would have been
1651 // performed. In such a case, modifying the run-time conditions and
1652 // possibly influencing the run-time check may cause certain scops
1653 // to not be executed.
1657 // When delinearizing the following code:
1659 // for (long i = 0; i < 100; i++)
1660 // for (long j = 0; j < m; j++)
1663 // we assume that the condition m <= 0 or (m >= 1 and p >= 0) holds as
1664 // otherwise we would access out of bound data. Now, knowing that code is
1665 // only executed for the case m >= 0, it is sufficient to assume p >= 0.
1666 AssumedContext
= simplifyAssumptionContext(AssumedContext
, *this);
1667 InvalidContext
= InvalidContext
.align_params(getParamSpace());
1670 isl::set
Scop::getDomainConditions(const ScopStmt
*Stmt
) const {
1671 return getDomainConditions(Stmt
->getEntryBlock());
1674 isl::set
Scop::getDomainConditions(BasicBlock
*BB
) const {
1675 auto DIt
= DomainMap
.find(BB
);
1676 if (DIt
!= DomainMap
.end())
1677 return DIt
->getSecond();
1679 auto &RI
= *R
.getRegionInfo();
1680 auto *BBR
= RI
.getRegionFor(BB
);
1681 while (BBR
->getEntry() == BB
)
1682 BBR
= BBR
->getParent();
1683 return getDomainConditions(BBR
->getEntry());
1686 int Scop::NextScopID
= 0;
1688 std::string
Scop::CurrentFunc
;
1690 int Scop::getNextID(std::string ParentFunc
) {
1691 if (ParentFunc
!= CurrentFunc
) {
1692 CurrentFunc
= ParentFunc
;
1695 return NextScopID
++;
1698 Scop::Scop(Region
&R
, ScalarEvolution
&ScalarEvolution
, LoopInfo
&LI
,
1699 DominatorTree
&DT
, ScopDetection::DetectionContext
&DC
,
1700 OptimizationRemarkEmitter
&ORE
)
1701 : IslCtx(isl_ctx_alloc(), isl_ctx_free
), SE(&ScalarEvolution
), DT(&DT
),
1702 R(R
), name(None
), HasSingleExitEdge(R
.getExitingBlock()), DC(DC
),
1703 ORE(ORE
), Affinator(this, LI
),
1704 ID(getNextID((*R
.getEntry()->getParent()).getName().str())) {
1705 if (IslOnErrorAbort
)
1706 isl_options_set_on_error(getIslCtx().get(), ISL_ON_ERROR_ABORT
);
1710 Scop::~Scop() = default;
1712 void Scop::removeFromStmtMap(ScopStmt
&Stmt
) {
1713 for (Instruction
*Inst
: Stmt
.getInstructions())
1714 InstStmtMap
.erase(Inst
);
1716 if (Stmt
.isRegionStmt()) {
1717 for (BasicBlock
*BB
: Stmt
.getRegion()->blocks()) {
1719 // Skip entry basic block, as its instructions are already deleted as
1720 // part of the statement's instruction list.
1721 if (BB
== Stmt
.getEntryBlock())
1723 for (Instruction
&Inst
: *BB
)
1724 InstStmtMap
.erase(&Inst
);
1727 auto StmtMapIt
= StmtMap
.find(Stmt
.getBasicBlock());
1728 if (StmtMapIt
!= StmtMap
.end())
1729 StmtMapIt
->second
.erase(std::remove(StmtMapIt
->second
.begin(),
1730 StmtMapIt
->second
.end(), &Stmt
),
1731 StmtMapIt
->second
.end());
1732 for (Instruction
*Inst
: Stmt
.getInstructions())
1733 InstStmtMap
.erase(Inst
);
1737 void Scop::removeStmts(std::function
<bool(ScopStmt
&)> ShouldDelete
,
1738 bool AfterHoisting
) {
1739 for (auto StmtIt
= Stmts
.begin(), StmtEnd
= Stmts
.end(); StmtIt
!= StmtEnd
;) {
1740 if (!ShouldDelete(*StmtIt
)) {
1745 // Start with removing all of the statement's accesses including erasing it
1746 // from all maps that are pointing to them.
1747 // Make a temporary copy because removing MAs invalidates the iterator.
1748 SmallVector
<MemoryAccess
*, 16> MAList(StmtIt
->begin(), StmtIt
->end());
1749 for (MemoryAccess
*MA
: MAList
)
1750 StmtIt
->removeSingleMemoryAccess(MA
, AfterHoisting
);
1752 removeFromStmtMap(*StmtIt
);
1753 StmtIt
= Stmts
.erase(StmtIt
);
1757 void Scop::removeStmtNotInDomainMap() {
1758 auto ShouldDelete
= [this](ScopStmt
&Stmt
) -> bool {
1759 isl::set Domain
= DomainMap
.lookup(Stmt
.getEntryBlock());
1762 return Domain
.is_empty();
1764 removeStmts(ShouldDelete
, false);
1767 void Scop::simplifySCoP(bool AfterHoisting
) {
1768 auto ShouldDelete
= [AfterHoisting
](ScopStmt
&Stmt
) -> bool {
1769 // Never delete statements that contain calls to debug functions.
1770 if (hasDebugCall(&Stmt
))
1773 bool RemoveStmt
= Stmt
.isEmpty();
1775 // Remove read only statements only after invariant load hoisting.
1776 if (!RemoveStmt
&& AfterHoisting
) {
1777 bool OnlyRead
= true;
1778 for (MemoryAccess
*MA
: Stmt
) {
1786 RemoveStmt
= OnlyRead
;
1791 removeStmts(ShouldDelete
, AfterHoisting
);
1794 InvariantEquivClassTy
*Scop::lookupInvariantEquivClass(Value
*Val
) {
1795 LoadInst
*LInst
= dyn_cast
<LoadInst
>(Val
);
1799 if (Value
*Rep
= InvEquivClassVMap
.lookup(LInst
))
1800 LInst
= cast
<LoadInst
>(Rep
);
1802 Type
*Ty
= LInst
->getType();
1803 const SCEV
*PointerSCEV
= SE
->getSCEV(LInst
->getPointerOperand());
1804 for (auto &IAClass
: InvariantEquivClasses
) {
1805 if (PointerSCEV
!= IAClass
.IdentifyingPointer
|| Ty
!= IAClass
.AccessType
)
1808 auto &MAs
= IAClass
.InvariantAccesses
;
1809 for (auto *MA
: MAs
)
1810 if (MA
->getAccessInstruction() == Val
)
1817 ScopArrayInfo
*Scop::getOrCreateScopArrayInfo(Value
*BasePtr
, Type
*ElementType
,
1818 ArrayRef
<const SCEV
*> Sizes
,
1820 const char *BaseName
) {
1821 assert((BasePtr
|| BaseName
) &&
1822 "BasePtr and BaseName can not be nullptr at the same time.");
1823 assert(!(BasePtr
&& BaseName
) && "BaseName is redundant.");
1824 auto &SAI
= BasePtr
? ScopArrayInfoMap
[std::make_pair(BasePtr
, Kind
)]
1825 : ScopArrayNameMap
[BaseName
];
1827 auto &DL
= getFunction().getParent()->getDataLayout();
1828 SAI
.reset(new ScopArrayInfo(BasePtr
, ElementType
, getIslCtx(), Sizes
, Kind
,
1829 DL
, this, BaseName
));
1830 ScopArrayInfoSet
.insert(SAI
.get());
1832 SAI
->updateElementType(ElementType
);
1833 // In case of mismatching array sizes, we bail out by setting the run-time
1834 // context to false.
1835 if (!SAI
->updateSizes(Sizes
))
1836 invalidate(DELINEARIZATION
, DebugLoc());
1841 ScopArrayInfo
*Scop::createScopArrayInfo(Type
*ElementType
,
1842 const std::string
&BaseName
,
1843 const std::vector
<unsigned> &Sizes
) {
1844 auto *DimSizeType
= Type::getInt64Ty(getSE()->getContext());
1845 std::vector
<const SCEV
*> SCEVSizes
;
1847 for (auto size
: Sizes
)
1849 SCEVSizes
.push_back(getSE()->getConstant(DimSizeType
, size
, false));
1851 SCEVSizes
.push_back(nullptr);
1853 auto *SAI
= getOrCreateScopArrayInfo(nullptr, ElementType
, SCEVSizes
,
1854 MemoryKind::Array
, BaseName
.c_str());
1858 const ScopArrayInfo
*Scop::getScopArrayInfoOrNull(Value
*BasePtr
,
1860 auto *SAI
= ScopArrayInfoMap
[std::make_pair(BasePtr
, Kind
)].get();
1864 const ScopArrayInfo
*Scop::getScopArrayInfo(Value
*BasePtr
, MemoryKind Kind
) {
1865 auto *SAI
= getScopArrayInfoOrNull(BasePtr
, Kind
);
1866 assert(SAI
&& "No ScopArrayInfo available for this base pointer");
1870 std::string
Scop::getContextStr() const { return getContext().to_str(); }
1872 std::string
Scop::getAssumedContextStr() const {
1873 assert(AssumedContext
&& "Assumed context not yet built");
1874 return AssumedContext
.to_str();
1877 std::string
Scop::getInvalidContextStr() const {
1878 return InvalidContext
.to_str();
1881 std::string
Scop::getNameStr() const {
1882 std::string ExitName
, EntryName
;
1883 std::tie(EntryName
, ExitName
) = getEntryExitStr();
1884 return EntryName
+ "---" + ExitName
;
1887 std::pair
<std::string
, std::string
> Scop::getEntryExitStr() const {
1888 std::string ExitName
, EntryName
;
1889 raw_string_ostream
ExitStr(ExitName
);
1890 raw_string_ostream
EntryStr(EntryName
);
1892 R
.getEntry()->printAsOperand(EntryStr
, false);
1896 R
.getExit()->printAsOperand(ExitStr
, false);
1899 ExitName
= "FunctionExit";
1901 return std::make_pair(EntryName
, ExitName
);
1904 isl::set
Scop::getContext() const { return Context
; }
1906 isl::space
Scop::getParamSpace() const { return getContext().get_space(); }
1908 isl::space
Scop::getFullParamSpace() const {
1909 std::vector
<isl::id
> FortranIDs
;
1910 FortranIDs
= getFortranArrayIds(arrays());
1912 isl::space Space
= isl::space::params_alloc(
1913 getIslCtx(), ParameterIds
.size() + FortranIDs
.size());
1916 for (const SCEV
*Parameter
: Parameters
) {
1917 isl::id Id
= getIdForParam(Parameter
);
1918 Space
= Space
.set_dim_id(isl::dim::param
, PDim
++, Id
);
1921 for (isl::id Id
: FortranIDs
)
1922 Space
= Space
.set_dim_id(isl::dim::param
, PDim
++, Id
);
1927 isl::set
Scop::getAssumedContext() const {
1928 assert(AssumedContext
&& "Assumed context not yet built");
1929 return AssumedContext
;
1932 bool Scop::isProfitable(bool ScalarsAreUnprofitable
) const {
1933 if (PollyProcessUnprofitable
)
1939 unsigned OptimizableStmtsOrLoops
= 0;
1940 for (auto &Stmt
: *this) {
1941 if (Stmt
.getNumIterators() == 0)
1944 bool ContainsArrayAccs
= false;
1945 bool ContainsScalarAccs
= false;
1946 for (auto *MA
: Stmt
) {
1949 ContainsArrayAccs
|= MA
->isLatestArrayKind();
1950 ContainsScalarAccs
|= MA
->isLatestScalarKind();
1953 if (!ScalarsAreUnprofitable
|| (ContainsArrayAccs
&& !ContainsScalarAccs
))
1954 OptimizableStmtsOrLoops
+= Stmt
.getNumIterators();
1957 return OptimizableStmtsOrLoops
> 1;
1960 bool Scop::hasFeasibleRuntimeContext() const {
1961 auto PositiveContext
= getAssumedContext();
1962 auto NegativeContext
= getInvalidContext();
1963 PositiveContext
= addNonEmptyDomainConstraints(PositiveContext
);
1964 // addNonEmptyDomainConstraints returns null if ScopStmts have a null domain
1965 if (!PositiveContext
)
1968 bool IsFeasible
= !(PositiveContext
.is_empty() ||
1969 PositiveContext
.is_subset(NegativeContext
));
1973 auto DomainContext
= getDomains().params();
1974 IsFeasible
= !DomainContext
.is_subset(NegativeContext
);
1975 IsFeasible
&= !getContext().is_subset(NegativeContext
);
1980 isl::set
Scop::addNonEmptyDomainConstraints(isl::set C
) const {
1981 isl::set DomainContext
= getDomains().params();
1982 return C
.intersect_params(DomainContext
);
1985 MemoryAccess
*Scop::lookupBasePtrAccess(MemoryAccess
*MA
) {
1986 Value
*PointerBase
= MA
->getOriginalBaseAddr();
1988 auto *PointerBaseInst
= dyn_cast
<Instruction
>(PointerBase
);
1989 if (!PointerBaseInst
)
1992 auto *BasePtrStmt
= getStmtFor(PointerBaseInst
);
1996 return BasePtrStmt
->getArrayAccessOrNULLFor(PointerBaseInst
);
1999 static std::string
toString(AssumptionKind Kind
) {
2002 return "No-aliasing";
2006 return "No-overflows";
2008 return "Signed-unsigned";
2010 return "Low complexity";
2012 return "Profitable";
2016 return "Finite loop";
2018 return "Invariant load";
2019 case DELINEARIZATION
:
2020 return "Delinearization";
2022 llvm_unreachable("Unknown AssumptionKind!");
2025 bool Scop::isEffectiveAssumption(isl::set Set
, AssumptionSign Sign
) {
2026 if (Sign
== AS_ASSUMPTION
) {
2027 if (Context
.is_subset(Set
))
2030 if (AssumedContext
.is_subset(Set
))
2033 if (Set
.is_disjoint(Context
))
2036 if (Set
.is_subset(InvalidContext
))
2042 bool Scop::trackAssumption(AssumptionKind Kind
, isl::set Set
, DebugLoc Loc
,
2043 AssumptionSign Sign
, BasicBlock
*BB
) {
2044 if (PollyRemarksMinimal
&& !isEffectiveAssumption(Set
, Sign
))
2047 // Do never emit trivial assumptions as they only clutter the output.
2048 if (!PollyRemarksMinimal
) {
2050 if (Sign
== AS_ASSUMPTION
)
2051 Univ
= isl::set::universe(Set
.get_space());
2053 bool IsTrivial
= (Sign
== AS_RESTRICTION
&& Set
.is_empty()) ||
2054 (Sign
== AS_ASSUMPTION
&& Univ
.is_equal(Set
));
2062 AssumptionsAliasing
++;
2065 AssumptionsInbounds
++;
2068 AssumptionsWrapping
++;
2071 AssumptionsUnsigned
++;
2074 AssumptionsComplexity
++;
2077 AssumptionsUnprofitable
++;
2080 AssumptionsErrorBlock
++;
2083 AssumptionsInfiniteLoop
++;
2086 AssumptionsInvariantLoad
++;
2088 case DELINEARIZATION
:
2089 AssumptionsDelinearization
++;
2093 auto Suffix
= Sign
== AS_ASSUMPTION
? " assumption:\t" : " restriction:\t";
2094 std::string Msg
= toString(Kind
) + Suffix
+ Set
.to_str();
2096 ORE
.emit(OptimizationRemarkAnalysis(DEBUG_TYPE
, "AssumpRestrict", Loc
, BB
)
2099 ORE
.emit(OptimizationRemarkAnalysis(DEBUG_TYPE
, "AssumpRestrict", Loc
,
2105 void Scop::addAssumption(AssumptionKind Kind
, isl::set Set
, DebugLoc Loc
,
2106 AssumptionSign Sign
, BasicBlock
*BB
) {
2107 // Simplify the assumptions/restrictions first.
2108 Set
= Set
.gist_params(getContext());
2110 if (!trackAssumption(Kind
, Set
, Loc
, Sign
, BB
))
2113 if (Sign
== AS_ASSUMPTION
)
2114 AssumedContext
= AssumedContext
.intersect(Set
).coalesce();
2116 InvalidContext
= InvalidContext
.unite(Set
).coalesce();
2119 void Scop::recordAssumption(AssumptionKind Kind
, isl::set Set
, DebugLoc Loc
,
2120 AssumptionSign Sign
, BasicBlock
*BB
) {
2121 assert((Set
.is_params() || BB
) &&
2122 "Assumptions without a basic block must be parameter sets");
2123 RecordedAssumptions
.push_back({Kind
, Sign
, Set
, Loc
, BB
});
2126 void Scop::invalidate(AssumptionKind Kind
, DebugLoc Loc
, BasicBlock
*BB
) {
2127 LLVM_DEBUG(dbgs() << "Invalidate SCoP because of reason " << Kind
<< "\n");
2128 addAssumption(Kind
, isl::set::empty(getParamSpace()), Loc
, AS_ASSUMPTION
, BB
);
2131 isl::set
Scop::getInvalidContext() const { return InvalidContext
; }
2133 void Scop::printContext(raw_ostream
&OS
) const {
2135 OS
.indent(4) << Context
<< "\n";
2137 OS
.indent(4) << "Assumed Context:\n";
2138 OS
.indent(4) << AssumedContext
<< "\n";
2140 OS
.indent(4) << "Invalid Context:\n";
2141 OS
.indent(4) << InvalidContext
<< "\n";
2144 for (const SCEV
*Parameter
: Parameters
)
2145 OS
.indent(4) << "p" << Dim
++ << ": " << *Parameter
<< "\n";
2148 void Scop::printAliasAssumptions(raw_ostream
&OS
) const {
2150 for (const MinMaxVectorPairTy
&Pair
: MinMaxAliasGroups
) {
2151 if (Pair
.second
.size() == 0)
2154 noOfGroups
+= Pair
.second
.size();
2157 OS
.indent(4) << "Alias Groups (" << noOfGroups
<< "):\n";
2158 if (MinMaxAliasGroups
.empty()) {
2159 OS
.indent(8) << "n/a\n";
2163 for (const MinMaxVectorPairTy
&Pair
: MinMaxAliasGroups
) {
2165 // If the group has no read only accesses print the write accesses.
2166 if (Pair
.second
.empty()) {
2167 OS
.indent(8) << "[[";
2168 for (const MinMaxAccessTy
&MMANonReadOnly
: Pair
.first
) {
2169 OS
<< " <" << MMANonReadOnly
.first
<< ", " << MMANonReadOnly
.second
2175 for (const MinMaxAccessTy
&MMAReadOnly
: Pair
.second
) {
2176 OS
.indent(8) << "[[";
2177 OS
<< " <" << MMAReadOnly
.first
<< ", " << MMAReadOnly
.second
<< ">";
2178 for (const MinMaxAccessTy
&MMANonReadOnly
: Pair
.first
) {
2179 OS
<< " <" << MMANonReadOnly
.first
<< ", " << MMANonReadOnly
.second
2187 void Scop::printStatements(raw_ostream
&OS
, bool PrintInstructions
) const {
2188 OS
<< "Statements {\n";
2190 for (const ScopStmt
&Stmt
: *this) {
2192 Stmt
.print(OS
, PrintInstructions
);
2195 OS
.indent(4) << "}\n";
2198 void Scop::printArrayInfo(raw_ostream
&OS
) const {
2201 for (auto &Array
: arrays())
2204 OS
.indent(4) << "}\n";
2206 OS
.indent(4) << "Arrays (Bounds as pw_affs) {\n";
2208 for (auto &Array
: arrays())
2209 Array
->print(OS
, /* SizeAsPwAff */ true);
2211 OS
.indent(4) << "}\n";
2214 void Scop::print(raw_ostream
&OS
, bool PrintInstructions
) const {
2215 OS
.indent(4) << "Function: " << getFunction().getName() << "\n";
2216 OS
.indent(4) << "Region: " << getNameStr() << "\n";
2217 OS
.indent(4) << "Max Loop Depth: " << getMaxLoopDepth() << "\n";
2218 OS
.indent(4) << "Invariant Accesses: {\n";
2219 for (const auto &IAClass
: InvariantEquivClasses
) {
2220 const auto &MAs
= IAClass
.InvariantAccesses
;
2222 OS
.indent(12) << "Class Pointer: " << *IAClass
.IdentifyingPointer
<< "\n";
2224 MAs
.front()->print(OS
);
2225 OS
.indent(12) << "Execution Context: " << IAClass
.ExecutionContext
2229 OS
.indent(4) << "}\n";
2230 printContext(OS
.indent(4));
2231 printArrayInfo(OS
.indent(4));
2232 printAliasAssumptions(OS
);
2233 printStatements(OS
.indent(4), PrintInstructions
);
2236 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2237 LLVM_DUMP_METHOD
void Scop::dump() const { print(dbgs(), true); }
2240 isl::ctx
Scop::getIslCtx() const { return IslCtx
.get(); }
2242 __isl_give PWACtx
Scop::getPwAff(const SCEV
*E
, BasicBlock
*BB
,
2244 // First try to use the SCEVAffinator to generate a piecewise defined
2245 // affine function from @p E in the context of @p BB. If that tasks becomes to
2246 // complex the affinator might return a nullptr. In such a case we invalidate
2247 // the SCoP and return a dummy value. This way we do not need to add error
2248 // handling code to all users of this function.
2249 auto PWAC
= Affinator
.getPwAff(E
, BB
);
2251 // TODO: We could use a heuristic and either use:
2252 // SCEVAffinator::takeNonNegativeAssumption
2254 // SCEVAffinator::interpretAsUnsigned
2255 // to deal with unsigned or "NonNegative" SCEVs.
2257 Affinator
.takeNonNegativeAssumption(PWAC
);
2261 auto DL
= BB
? BB
->getTerminator()->getDebugLoc() : DebugLoc();
2262 invalidate(COMPLEXITY
, DL
, BB
);
2263 return Affinator
.getPwAff(SE
->getZero(E
->getType()), BB
);
2266 isl::union_set
Scop::getDomains() const {
2267 isl_space
*EmptySpace
= isl_space_params_alloc(getIslCtx().get(), 0);
2268 isl_union_set
*Domain
= isl_union_set_empty(EmptySpace
);
2270 for (const ScopStmt
&Stmt
: *this)
2271 Domain
= isl_union_set_add_set(Domain
, Stmt
.getDomain().release());
2273 return isl::manage(Domain
);
2276 isl::pw_aff
Scop::getPwAffOnly(const SCEV
*E
, BasicBlock
*BB
) {
2277 PWACtx PWAC
= getPwAff(E
, BB
);
2282 Scop::getAccessesOfType(std::function
<bool(MemoryAccess
&)> Predicate
) {
2283 isl::union_map Accesses
= isl::union_map::empty(getParamSpace());
2285 for (ScopStmt
&Stmt
: *this) {
2286 for (MemoryAccess
*MA
: Stmt
) {
2287 if (!Predicate(*MA
))
2290 isl::set Domain
= Stmt
.getDomain();
2291 isl::map AccessDomain
= MA
->getAccessRelation();
2292 AccessDomain
= AccessDomain
.intersect_domain(Domain
);
2293 Accesses
= Accesses
.add_map(AccessDomain
);
2297 return Accesses
.coalesce();
2300 isl::union_map
Scop::getMustWrites() {
2301 return getAccessesOfType([](MemoryAccess
&MA
) { return MA
.isMustWrite(); });
2304 isl::union_map
Scop::getMayWrites() {
2305 return getAccessesOfType([](MemoryAccess
&MA
) { return MA
.isMayWrite(); });
2308 isl::union_map
Scop::getWrites() {
2309 return getAccessesOfType([](MemoryAccess
&MA
) { return MA
.isWrite(); });
2312 isl::union_map
Scop::getReads() {
2313 return getAccessesOfType([](MemoryAccess
&MA
) { return MA
.isRead(); });
2316 isl::union_map
Scop::getAccesses() {
2317 return getAccessesOfType([](MemoryAccess
&MA
) { return true; });
2320 isl::union_map
Scop::getAccesses(ScopArrayInfo
*Array
) {
2321 return getAccessesOfType(
2322 [Array
](MemoryAccess
&MA
) { return MA
.getScopArrayInfo() == Array
; });
2325 isl::union_map
Scop::getSchedule() const {
2326 auto Tree
= getScheduleTree();
2327 return Tree
.get_map();
2330 isl::schedule
Scop::getScheduleTree() const {
2331 return Schedule
.intersect_domain(getDomains());
2334 void Scop::setSchedule(isl::union_map NewSchedule
) {
2335 auto S
= isl::schedule::from_domain(getDomains());
2336 Schedule
= S
.insert_partial_schedule(
2337 isl::multi_union_pw_aff::from_union_map(NewSchedule
));
2338 ScheduleModified
= true;
2341 void Scop::setScheduleTree(isl::schedule NewSchedule
) {
2342 Schedule
= NewSchedule
;
2343 ScheduleModified
= true;
2346 bool Scop::restrictDomains(isl::union_set Domain
) {
2347 bool Changed
= false;
2348 for (ScopStmt
&Stmt
: *this) {
2349 isl::union_set StmtDomain
= isl::union_set(Stmt
.getDomain());
2350 isl::union_set NewStmtDomain
= StmtDomain
.intersect(Domain
);
2352 if (StmtDomain
.is_subset(NewStmtDomain
))
2357 NewStmtDomain
= NewStmtDomain
.coalesce();
2359 if (NewStmtDomain
.is_empty())
2360 Stmt
.restrictDomain(isl::set::empty(Stmt
.getDomainSpace()));
2362 Stmt
.restrictDomain(isl::set(NewStmtDomain
));
2367 ScalarEvolution
*Scop::getSE() const { return SE
; }
2369 void Scop::addScopStmt(BasicBlock
*BB
, StringRef Name
, Loop
*SurroundingLoop
,
2370 std::vector
<Instruction
*> Instructions
) {
2371 assert(BB
&& "Unexpected nullptr!");
2372 Stmts
.emplace_back(*this, *BB
, Name
, SurroundingLoop
, Instructions
);
2373 auto *Stmt
= &Stmts
.back();
2374 StmtMap
[BB
].push_back(Stmt
);
2375 for (Instruction
*Inst
: Instructions
) {
2376 assert(!InstStmtMap
.count(Inst
) &&
2377 "Unexpected statement corresponding to the instruction.");
2378 InstStmtMap
[Inst
] = Stmt
;
2382 void Scop::addScopStmt(Region
*R
, StringRef Name
, Loop
*SurroundingLoop
,
2383 std::vector
<Instruction
*> Instructions
) {
2384 assert(R
&& "Unexpected nullptr!");
2385 Stmts
.emplace_back(*this, *R
, Name
, SurroundingLoop
, Instructions
);
2386 auto *Stmt
= &Stmts
.back();
2388 for (Instruction
*Inst
: Instructions
) {
2389 assert(!InstStmtMap
.count(Inst
) &&
2390 "Unexpected statement corresponding to the instruction.");
2391 InstStmtMap
[Inst
] = Stmt
;
2394 for (BasicBlock
*BB
: R
->blocks()) {
2395 StmtMap
[BB
].push_back(Stmt
);
2396 if (BB
== R
->getEntry())
2398 for (Instruction
&Inst
: *BB
) {
2399 assert(!InstStmtMap
.count(&Inst
) &&
2400 "Unexpected statement corresponding to the instruction.");
2401 InstStmtMap
[&Inst
] = Stmt
;
2406 ScopStmt
*Scop::addScopStmt(isl::map SourceRel
, isl::map TargetRel
,
2409 isl::set SourceDomain
= SourceRel
.domain();
2410 isl::set TargetDomain
= TargetRel
.domain();
2411 assert(Domain
.is_subset(TargetDomain
) &&
2412 "Target access not defined for complete statement domain");
2413 assert(Domain
.is_subset(SourceDomain
) &&
2414 "Source access not defined for complete statement domain");
2416 Stmts
.emplace_back(*this, SourceRel
, TargetRel
, Domain
);
2418 return &(Stmts
.back());
2421 ArrayRef
<ScopStmt
*> Scop::getStmtListFor(BasicBlock
*BB
) const {
2422 auto StmtMapIt
= StmtMap
.find(BB
);
2423 if (StmtMapIt
== StmtMap
.end())
2425 return StmtMapIt
->second
;
2428 ScopStmt
*Scop::getIncomingStmtFor(const Use
&U
) const {
2429 auto *PHI
= cast
<PHINode
>(U
.getUser());
2430 BasicBlock
*IncomingBB
= PHI
->getIncomingBlock(U
);
2432 // If the value is a non-synthesizable from the incoming block, use the
2433 // statement that contains it as user statement.
2434 if (auto *IncomingInst
= dyn_cast
<Instruction
>(U
.get())) {
2435 if (IncomingInst
->getParent() == IncomingBB
) {
2436 if (ScopStmt
*IncomingStmt
= getStmtFor(IncomingInst
))
2437 return IncomingStmt
;
2441 // Otherwise, use the epilogue/last statement.
2442 return getLastStmtFor(IncomingBB
);
2445 ScopStmt
*Scop::getLastStmtFor(BasicBlock
*BB
) const {
2446 ArrayRef
<ScopStmt
*> StmtList
= getStmtListFor(BB
);
2447 if (!StmtList
.empty())
2448 return StmtList
.back();
2452 ArrayRef
<ScopStmt
*> Scop::getStmtListFor(RegionNode
*RN
) const {
2453 if (RN
->isSubRegion())
2454 return getStmtListFor(RN
->getNodeAs
<Region
>());
2455 return getStmtListFor(RN
->getNodeAs
<BasicBlock
>());
2458 ArrayRef
<ScopStmt
*> Scop::getStmtListFor(Region
*R
) const {
2459 return getStmtListFor(R
->getEntry());
2462 int Scop::getRelativeLoopDepth(const Loop
*L
) const {
2463 if (!L
|| !R
.contains(L
))
2465 // outermostLoopInRegion always returns nullptr for top level regions
2466 if (R
.isTopLevelRegion()) {
2467 // LoopInfo's depths start at 1, we start at 0
2468 return L
->getLoopDepth() - 1;
2470 Loop
*OuterLoop
= R
.outermostLoopInRegion(const_cast<Loop
*>(L
));
2472 return L
->getLoopDepth() - OuterLoop
->getLoopDepth();
2476 ScopArrayInfo
*Scop::getArrayInfoByName(const std::string BaseName
) {
2477 for (auto &SAI
: arrays()) {
2478 if (SAI
->getName() == BaseName
)
2484 void Scop::addAccessData(MemoryAccess
*Access
) {
2485 const ScopArrayInfo
*SAI
= Access
->getOriginalScopArrayInfo();
2486 assert(SAI
&& "can only use after access relations have been constructed");
2488 if (Access
->isOriginalValueKind() && Access
->isRead())
2489 ValueUseAccs
[SAI
].push_back(Access
);
2490 else if (Access
->isOriginalAnyPHIKind() && Access
->isWrite())
2491 PHIIncomingAccs
[SAI
].push_back(Access
);
2494 void Scop::removeAccessData(MemoryAccess
*Access
) {
2495 if (Access
->isOriginalValueKind() && Access
->isWrite()) {
2496 ValueDefAccs
.erase(Access
->getAccessValue());
2497 } else if (Access
->isOriginalValueKind() && Access
->isRead()) {
2498 auto &Uses
= ValueUseAccs
[Access
->getScopArrayInfo()];
2499 auto NewEnd
= std::remove(Uses
.begin(), Uses
.end(), Access
);
2500 Uses
.erase(NewEnd
, Uses
.end());
2501 } else if (Access
->isOriginalPHIKind() && Access
->isRead()) {
2502 PHINode
*PHI
= cast
<PHINode
>(Access
->getAccessInstruction());
2503 PHIReadAccs
.erase(PHI
);
2504 } else if (Access
->isOriginalAnyPHIKind() && Access
->isWrite()) {
2505 auto &Incomings
= PHIIncomingAccs
[Access
->getScopArrayInfo()];
2506 auto NewEnd
= std::remove(Incomings
.begin(), Incomings
.end(), Access
);
2507 Incomings
.erase(NewEnd
, Incomings
.end());
2511 MemoryAccess
*Scop::getValueDef(const ScopArrayInfo
*SAI
) const {
2512 assert(SAI
->isValueKind());
2514 Instruction
*Val
= dyn_cast
<Instruction
>(SAI
->getBasePtr());
2518 return ValueDefAccs
.lookup(Val
);
2521 ArrayRef
<MemoryAccess
*> Scop::getValueUses(const ScopArrayInfo
*SAI
) const {
2522 assert(SAI
->isValueKind());
2523 auto It
= ValueUseAccs
.find(SAI
);
2524 if (It
== ValueUseAccs
.end())
2529 MemoryAccess
*Scop::getPHIRead(const ScopArrayInfo
*SAI
) const {
2530 assert(SAI
->isPHIKind() || SAI
->isExitPHIKind());
2532 if (SAI
->isExitPHIKind())
2535 PHINode
*PHI
= cast
<PHINode
>(SAI
->getBasePtr());
2536 return PHIReadAccs
.lookup(PHI
);
2539 ArrayRef
<MemoryAccess
*> Scop::getPHIIncomings(const ScopArrayInfo
*SAI
) const {
2540 assert(SAI
->isPHIKind() || SAI
->isExitPHIKind());
2541 auto It
= PHIIncomingAccs
.find(SAI
);
2542 if (It
== PHIIncomingAccs
.end())
2547 bool Scop::isEscaping(Instruction
*Inst
) {
2548 assert(contains(Inst
) && "The concept of escaping makes only sense for "
2549 "values defined inside the SCoP");
2551 for (Use
&Use
: Inst
->uses()) {
2552 BasicBlock
*UserBB
= getUseBlock(Use
);
2553 if (!contains(UserBB
))
2556 // When the SCoP region exit needs to be simplified, PHIs in the region exit
2557 // move to a new basic block such that its incoming blocks are not in the
2559 if (hasSingleExitEdge() && isa
<PHINode
>(Use
.getUser()) &&
2560 isExit(cast
<PHINode
>(Use
.getUser())->getParent()))
2566 void Scop::incrementNumberOfAliasingAssumptions(unsigned step
) {
2567 AssumptionsAliasing
+= step
;
2570 Scop::ScopStatistics
Scop::getStatistics() const {
2571 ScopStatistics Result
;
2572 #if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
2573 auto LoopStat
= ScopDetection::countBeneficialLoops(&R
, *SE
, *getLI(), 0);
2575 int NumTotalLoops
= LoopStat
.NumLoops
;
2576 Result
.NumBoxedLoops
= getBoxedLoops().size();
2577 Result
.NumAffineLoops
= NumTotalLoops
- Result
.NumBoxedLoops
;
2579 for (const ScopStmt
&Stmt
: *this) {
2580 isl::set Domain
= Stmt
.getDomain().intersect_params(getContext());
2581 bool IsInLoop
= Stmt
.getNumIterators() >= 1;
2582 for (MemoryAccess
*MA
: Stmt
) {
2586 if (MA
->isLatestValueKind()) {
2587 Result
.NumValueWrites
+= 1;
2589 Result
.NumValueWritesInLoops
+= 1;
2592 if (MA
->isLatestAnyPHIKind()) {
2593 Result
.NumPHIWrites
+= 1;
2595 Result
.NumPHIWritesInLoops
+= 1;
2599 MA
->getAccessRelation().intersect_domain(Domain
).range();
2600 if (AccSet
.is_singleton()) {
2601 Result
.NumSingletonWrites
+= 1;
2603 Result
.NumSingletonWritesInLoops
+= 1;
2611 raw_ostream
&polly::operator<<(raw_ostream
&OS
, const Scop
&scop
) {
2612 scop
.print(OS
, PollyPrintInstructions
);
2616 //===----------------------------------------------------------------------===//
2617 void ScopInfoRegionPass::getAnalysisUsage(AnalysisUsage
&AU
) const {
2618 AU
.addRequired
<LoopInfoWrapperPass
>();
2619 AU
.addRequired
<RegionInfoPass
>();
2620 AU
.addRequired
<DominatorTreeWrapperPass
>();
2621 AU
.addRequiredTransitive
<ScalarEvolutionWrapperPass
>();
2622 AU
.addRequiredTransitive
<ScopDetectionWrapperPass
>();
2623 AU
.addRequired
<AAResultsWrapperPass
>();
2624 AU
.addRequired
<AssumptionCacheTracker
>();
2625 AU
.addRequired
<OptimizationRemarkEmitterWrapperPass
>();
2626 AU
.setPreservesAll();
2629 void updateLoopCountStatistic(ScopDetection::LoopStats Stats
,
2630 Scop::ScopStatistics ScopStats
) {
2631 assert(Stats
.NumLoops
== ScopStats
.NumAffineLoops
+ ScopStats
.NumBoxedLoops
);
2634 NumLoopsInScop
+= Stats
.NumLoops
;
2636 std::max(MaxNumLoopsInScop
.getValue(), (unsigned)Stats
.NumLoops
);
2638 if (Stats
.MaxDepth
== 0)
2639 NumScopsDepthZero
++;
2640 else if (Stats
.MaxDepth
== 1)
2642 else if (Stats
.MaxDepth
== 2)
2644 else if (Stats
.MaxDepth
== 3)
2645 NumScopsDepthThree
++;
2646 else if (Stats
.MaxDepth
== 4)
2647 NumScopsDepthFour
++;
2648 else if (Stats
.MaxDepth
== 5)
2649 NumScopsDepthFive
++;
2651 NumScopsDepthLarger
++;
2653 NumAffineLoops
+= ScopStats
.NumAffineLoops
;
2654 NumBoxedLoops
+= ScopStats
.NumBoxedLoops
;
2656 NumValueWrites
+= ScopStats
.NumValueWrites
;
2657 NumValueWritesInLoops
+= ScopStats
.NumValueWritesInLoops
;
2658 NumPHIWrites
+= ScopStats
.NumPHIWrites
;
2659 NumPHIWritesInLoops
+= ScopStats
.NumPHIWritesInLoops
;
2660 NumSingletonWrites
+= ScopStats
.NumSingletonWrites
;
2661 NumSingletonWritesInLoops
+= ScopStats
.NumSingletonWritesInLoops
;
2664 bool ScopInfoRegionPass::runOnRegion(Region
*R
, RGPassManager
&RGM
) {
2665 auto &SD
= getAnalysis
<ScopDetectionWrapperPass
>().getSD();
2667 if (!SD
.isMaxRegionInScop(*R
))
2670 Function
*F
= R
->getEntry()->getParent();
2671 auto &SE
= getAnalysis
<ScalarEvolutionWrapperPass
>().getSE();
2672 auto &LI
= getAnalysis
<LoopInfoWrapperPass
>().getLoopInfo();
2673 auto &AA
= getAnalysis
<AAResultsWrapperPass
>().getAAResults();
2674 auto const &DL
= F
->getParent()->getDataLayout();
2675 auto &DT
= getAnalysis
<DominatorTreeWrapperPass
>().getDomTree();
2676 auto &AC
= getAnalysis
<AssumptionCacheTracker
>().getAssumptionCache(*F
);
2677 auto &ORE
= getAnalysis
<OptimizationRemarkEmitterWrapperPass
>().getORE();
2679 ScopBuilder
SB(R
, AC
, AA
, DL
, DT
, LI
, SD
, SE
, ORE
);
2680 S
= SB
.getScop(); // take ownership of scop object
2682 #if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
2684 ScopDetection::LoopStats Stats
=
2685 ScopDetection::countBeneficialLoops(&S
->getRegion(), SE
, LI
, 0);
2686 updateLoopCountStatistic(Stats
, S
->getStatistics());
2693 void ScopInfoRegionPass::print(raw_ostream
&OS
, const Module
*) const {
2695 S
->print(OS
, PollyPrintInstructions
);
2697 OS
<< "Invalid Scop!\n";
2700 char ScopInfoRegionPass::ID
= 0;
2702 Pass
*polly::createScopInfoRegionPassPass() { return new ScopInfoRegionPass(); }
2704 INITIALIZE_PASS_BEGIN(ScopInfoRegionPass
, "polly-scops",
2705 "Polly - Create polyhedral description of Scops", false,
2707 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass
);
2708 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker
);
2709 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass
);
2710 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass
);
2711 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass
);
2712 INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass
);
2713 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass
);
2714 INITIALIZE_PASS_END(ScopInfoRegionPass
, "polly-scops",
2715 "Polly - Create polyhedral description of Scops", false,
2718 //===----------------------------------------------------------------------===//
2719 ScopInfo::ScopInfo(const DataLayout
&DL
, ScopDetection
&SD
, ScalarEvolution
&SE
,
2720 LoopInfo
&LI
, AliasAnalysis
&AA
, DominatorTree
&DT
,
2721 AssumptionCache
&AC
, OptimizationRemarkEmitter
&ORE
)
2722 : DL(DL
), SD(SD
), SE(SE
), LI(LI
), AA(AA
), DT(DT
), AC(AC
), ORE(ORE
) {
2726 void ScopInfo::recompute() {
2727 RegionToScopMap
.clear();
2728 /// Create polyhedral description of scops for all the valid regions of a
2730 for (auto &It
: SD
) {
2731 Region
*R
= const_cast<Region
*>(It
);
2732 if (!SD
.isMaxRegionInScop(*R
))
2735 ScopBuilder
SB(R
, AC
, AA
, DL
, DT
, LI
, SD
, SE
, ORE
);
2736 std::unique_ptr
<Scop
> S
= SB
.getScop();
2739 #if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
2740 ScopDetection::LoopStats Stats
=
2741 ScopDetection::countBeneficialLoops(&S
->getRegion(), SE
, LI
, 0);
2742 updateLoopCountStatistic(Stats
, S
->getStatistics());
2744 bool Inserted
= RegionToScopMap
.insert({R
, std::move(S
)}).second
;
2745 assert(Inserted
&& "Building Scop for the same region twice!");
2750 bool ScopInfo::invalidate(Function
&F
, const PreservedAnalyses
&PA
,
2751 FunctionAnalysisManager::Invalidator
&Inv
) {
2752 // Check whether the analysis, all analyses on functions have been preserved
2753 // or anything we're holding references to is being invalidated
2754 auto PAC
= PA
.getChecker
<ScopInfoAnalysis
>();
2755 return !(PAC
.preserved() || PAC
.preservedSet
<AllAnalysesOn
<Function
>>()) ||
2756 Inv
.invalidate
<ScopAnalysis
>(F
, PA
) ||
2757 Inv
.invalidate
<ScalarEvolutionAnalysis
>(F
, PA
) ||
2758 Inv
.invalidate
<LoopAnalysis
>(F
, PA
) ||
2759 Inv
.invalidate
<AAManager
>(F
, PA
) ||
2760 Inv
.invalidate
<DominatorTreeAnalysis
>(F
, PA
) ||
2761 Inv
.invalidate
<AssumptionAnalysis
>(F
, PA
);
2764 AnalysisKey
ScopInfoAnalysis::Key
;
2766 ScopInfoAnalysis::Result
ScopInfoAnalysis::run(Function
&F
,
2767 FunctionAnalysisManager
&FAM
) {
2768 auto &SD
= FAM
.getResult
<ScopAnalysis
>(F
);
2769 auto &SE
= FAM
.getResult
<ScalarEvolutionAnalysis
>(F
);
2770 auto &LI
= FAM
.getResult
<LoopAnalysis
>(F
);
2771 auto &AA
= FAM
.getResult
<AAManager
>(F
);
2772 auto &DT
= FAM
.getResult
<DominatorTreeAnalysis
>(F
);
2773 auto &AC
= FAM
.getResult
<AssumptionAnalysis
>(F
);
2774 auto &DL
= F
.getParent()->getDataLayout();
2775 auto &ORE
= FAM
.getResult
<OptimizationRemarkEmitterAnalysis
>(F
);
2776 return {DL
, SD
, SE
, LI
, AA
, DT
, AC
, ORE
};
2779 PreservedAnalyses
ScopInfoPrinterPass::run(Function
&F
,
2780 FunctionAnalysisManager
&FAM
) {
2781 auto &SI
= FAM
.getResult
<ScopInfoAnalysis
>(F
);
2782 // Since the legacy PM processes Scops in bottom up, we print them in reverse
2783 // order here to keep the output persistent
2784 for (auto &It
: reverse(SI
)) {
2786 It
.second
->print(Stream
, PollyPrintInstructions
);
2788 Stream
<< "Invalid Scop!\n";
2790 return PreservedAnalyses::all();
2793 void ScopInfoWrapperPass::getAnalysisUsage(AnalysisUsage
&AU
) const {
2794 AU
.addRequired
<LoopInfoWrapperPass
>();
2795 AU
.addRequired
<RegionInfoPass
>();
2796 AU
.addRequired
<DominatorTreeWrapperPass
>();
2797 AU
.addRequiredTransitive
<ScalarEvolutionWrapperPass
>();
2798 AU
.addRequiredTransitive
<ScopDetectionWrapperPass
>();
2799 AU
.addRequired
<AAResultsWrapperPass
>();
2800 AU
.addRequired
<AssumptionCacheTracker
>();
2801 AU
.addRequired
<OptimizationRemarkEmitterWrapperPass
>();
2802 AU
.setPreservesAll();
2805 bool ScopInfoWrapperPass::runOnFunction(Function
&F
) {
2806 auto &SD
= getAnalysis
<ScopDetectionWrapperPass
>().getSD();
2807 auto &SE
= getAnalysis
<ScalarEvolutionWrapperPass
>().getSE();
2808 auto &LI
= getAnalysis
<LoopInfoWrapperPass
>().getLoopInfo();
2809 auto &AA
= getAnalysis
<AAResultsWrapperPass
>().getAAResults();
2810 auto const &DL
= F
.getParent()->getDataLayout();
2811 auto &DT
= getAnalysis
<DominatorTreeWrapperPass
>().getDomTree();
2812 auto &AC
= getAnalysis
<AssumptionCacheTracker
>().getAssumptionCache(F
);
2813 auto &ORE
= getAnalysis
<OptimizationRemarkEmitterWrapperPass
>().getORE();
2815 Result
.reset(new ScopInfo
{DL
, SD
, SE
, LI
, AA
, DT
, AC
, ORE
});
2819 void ScopInfoWrapperPass::print(raw_ostream
&OS
, const Module
*) const {
2820 for (auto &It
: *Result
) {
2822 It
.second
->print(OS
, PollyPrintInstructions
);
2824 OS
<< "Invalid Scop!\n";
2828 char ScopInfoWrapperPass::ID
= 0;
2830 Pass
*polly::createScopInfoWrapperPassPass() {
2831 return new ScopInfoWrapperPass();
2834 INITIALIZE_PASS_BEGIN(
2835 ScopInfoWrapperPass
, "polly-function-scops",
2836 "Polly - Create polyhedral description of all Scops of a function", false,
2838 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass
);
2839 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker
);
2840 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass
);
2841 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass
);
2842 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass
);
2843 INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass
);
2844 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass
);
2845 INITIALIZE_PASS_END(
2846 ScopInfoWrapperPass
, "polly-function-scops",
2847 "Polly - Create polyhedral description of all Scops of a function", false,