blob: ef52bd34a1cd87be8f2ad4cfe1fe999d48b784ed [file] [log] [blame]
Johannes Doerfert58a7c752015-09-28 09:48:53 +00001//===--------- ScopInfo.cpp - Create Scops from LLVM IR ------------------===//
Tobias Grosser75805372011-04-29 06:27:02 +00002//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// Create a polyhedral description for a static control flow region.
11//
12// The pass creates a polyhedral description of the Scops detected by the Scop
13// detection derived from their LLVM-IR code.
14//
Tobias Grossera5605d32014-10-29 19:58:28 +000015// This representation is shared among several tools in the polyhedral
Tobias Grosser75805372011-04-29 06:27:02 +000016// community, which are e.g. Cloog, Pluto, Loopo, Graphite.
17//
18//===----------------------------------------------------------------------===//
19
Tobias Grosser75805372011-04-29 06:27:02 +000020#include "polly/LinkAllPasses.h"
Johannes Doerfert0ee1f212014-06-17 17:31:36 +000021#include "polly/Options.h"
Tobias Grosserba0d0922015-05-09 09:13:42 +000022#include "polly/ScopInfo.h"
Tobias Grosser75805372011-04-29 06:27:02 +000023#include "polly/Support/GICHelper.h"
Tobias Grosser60b54f12011-11-08 15:41:28 +000024#include "polly/Support/SCEVValidator.h"
Tobias Grosser83628182013-05-07 08:11:54 +000025#include "polly/Support/ScopHelper.h"
Tobias Grosserf4c24b22015-04-05 13:11:54 +000026#include "llvm/ADT/MapVector.h"
Tobias Grosserc2bb0cb2015-09-25 09:49:19 +000027#include "llvm/ADT/PostOrderIterator.h"
28#include "llvm/ADT/STLExtras.h"
Tobias Grosserba0d0922015-05-09 09:13:42 +000029#include "llvm/ADT/SetVector.h"
Tobias Grosser83628182013-05-07 08:11:54 +000030#include "llvm/ADT/Statistic.h"
Hongbin Zheng86a37742012-04-25 08:01:38 +000031#include "llvm/ADT/StringExtras.h"
Johannes Doerfertb164c792014-09-18 11:17:17 +000032#include "llvm/Analysis/AliasAnalysis.h"
Tobias Grosserba0d0922015-05-09 09:13:42 +000033#include "llvm/Analysis/LoopInfo.h"
Tobias Grosserc2bb0cb2015-09-25 09:49:19 +000034#include "llvm/Analysis/LoopIterator.h"
Tobias Grosser83628182013-05-07 08:11:54 +000035#include "llvm/Analysis/RegionIterator.h"
36#include "llvm/Analysis/ScalarEvolutionExpressions.h"
Tobias Grosser75805372011-04-29 06:27:02 +000037#include "llvm/Support/Debug.h"
Tobias Grosser33ba62ad2011-08-18 06:31:50 +000038#include "isl/aff.h"
Tobias Grosserba0d0922015-05-09 09:13:42 +000039#include "isl/constraint.h"
Tobias Grosserf5338802011-10-06 00:03:35 +000040#include "isl/local_space.h"
Tobias Grosserba0d0922015-05-09 09:13:42 +000041#include "isl/map.h"
Tobias Grosser4a8e3562011-12-07 07:42:51 +000042#include "isl/options.h"
Tobias Grosserba0d0922015-05-09 09:13:42 +000043#include "isl/printer.h"
Tobias Grosser808cd692015-07-14 09:33:13 +000044#include "isl/schedule.h"
45#include "isl/schedule_node.h"
Tobias Grosserba0d0922015-05-09 09:13:42 +000046#include "isl/set.h"
47#include "isl/union_map.h"
Tobias Grossercd524dc2015-05-09 09:36:38 +000048#include "isl/union_set.h"
Tobias Grosseredab1352013-06-21 06:41:31 +000049#include "isl/val.h"
Tobias Grosser75805372011-04-29 06:27:02 +000050#include <sstream>
51#include <string>
52#include <vector>
53
54using namespace llvm;
55using namespace polly;
56
Chandler Carruth95fef942014-04-22 03:30:19 +000057#define DEBUG_TYPE "polly-scops"
58
Tobias Grosser74394f02013-01-14 22:40:23 +000059STATISTIC(ScopFound, "Number of valid Scops");
60STATISTIC(RichScopFound, "Number of Scops containing a loop");
Tobias Grosser75805372011-04-29 06:27:02 +000061
Michael Kruse7bf39442015-09-10 12:46:52 +000062static cl::opt<bool> ModelReadOnlyScalars(
63 "polly-analyze-read-only-scalars",
64 cl::desc("Model read-only scalar values in the scop description"),
65 cl::Hidden, cl::ZeroOrMore, cl::init(true), cl::cat(PollyCategory));
66
Johannes Doerfert9e7b17b2014-08-18 00:40:13 +000067// Multiplicative reductions can be disabled separately as these kind of
Johannes Doerfert0ee1f212014-06-17 17:31:36 +000068// operations can overflow easily. Additive reductions and bit operations
69// are in contrast pretty stable.
Tobias Grosser483a90d2014-07-09 10:50:10 +000070static cl::opt<bool> DisableMultiplicativeReductions(
71 "polly-disable-multiplicative-reductions",
72 cl::desc("Disable multiplicative reductions"), cl::Hidden, cl::ZeroOrMore,
73 cl::init(false), cl::cat(PollyCategory));
Johannes Doerfert0ee1f212014-06-17 17:31:36 +000074
Johannes Doerfert9143d672014-09-27 11:02:39 +000075static cl::opt<unsigned> RunTimeChecksMaxParameters(
76 "polly-rtc-max-parameters",
77 cl::desc("The maximal number of parameters allowed in RTCs."), cl::Hidden,
78 cl::ZeroOrMore, cl::init(8), cl::cat(PollyCategory));
79
Tobias Grosser71500722015-03-28 15:11:14 +000080static cl::opt<unsigned> RunTimeChecksMaxArraysPerGroup(
81 "polly-rtc-max-arrays-per-group",
82 cl::desc("The maximal number of arrays to compare in each alias group."),
83 cl::Hidden, cl::ZeroOrMore, cl::init(20), cl::cat(PollyCategory));
Tobias Grosser8a9c2352015-08-16 10:19:29 +000084static cl::opt<std::string> UserContextStr(
85 "polly-context", cl::value_desc("isl parameter set"),
86 cl::desc("Provide additional constraints on the context parameters"),
87 cl::init(""), cl::cat(PollyCategory));
Tobias Grosser71500722015-03-28 15:11:14 +000088
Tobias Grosserd83b8a82015-08-20 19:08:11 +000089static cl::opt<bool> DetectReductions("polly-detect-reductions",
90 cl::desc("Detect and exploit reductions"),
91 cl::Hidden, cl::ZeroOrMore,
92 cl::init(true), cl::cat(PollyCategory));
93
Michael Kruse7bf39442015-09-10 12:46:52 +000094//===----------------------------------------------------------------------===//
Michael Kruse7bf39442015-09-10 12:46:52 +000095
Michael Kruse046dde42015-08-10 13:01:57 +000096// Create a sequence of two schedules. Either argument may be null and is
97// interpreted as the empty schedule. Can also return null if both schedules are
98// empty.
99static __isl_give isl_schedule *
100combineInSequence(__isl_take isl_schedule *Prev,
101 __isl_take isl_schedule *Succ) {
102 if (!Prev)
103 return Succ;
104 if (!Succ)
105 return Prev;
106
107 return isl_schedule_sequence(Prev, Succ);
108}
109
Johannes Doerferte7044942015-02-24 11:58:30 +0000110static __isl_give isl_set *addRangeBoundsToSet(__isl_take isl_set *S,
111 const ConstantRange &Range,
112 int dim,
113 enum isl_dim_type type) {
114 isl_val *V;
115 isl_ctx *ctx = isl_set_get_ctx(S);
116
Johannes Doerfert8f8af432015-04-26 20:07:21 +0000117 bool useLowerUpperBound = Range.isSignWrappedSet() && !Range.isFullSet();
118 const auto LB = useLowerUpperBound ? Range.getLower() : Range.getSignedMin();
Johannes Doerferte4bd53b2015-03-08 19:49:50 +0000119 V = isl_valFromAPInt(ctx, LB, true);
Johannes Doerferte7044942015-02-24 11:58:30 +0000120 isl_set *SLB = isl_set_lower_bound_val(isl_set_copy(S), type, dim, V);
121
Johannes Doerfert8f8af432015-04-26 20:07:21 +0000122 const auto UB = useLowerUpperBound ? Range.getUpper() : Range.getSignedMax();
Johannes Doerferte4bd53b2015-03-08 19:49:50 +0000123 V = isl_valFromAPInt(ctx, UB, true);
Johannes Doerfert8f8af432015-04-26 20:07:21 +0000124 if (useLowerUpperBound)
Johannes Doerferte4bd53b2015-03-08 19:49:50 +0000125 V = isl_val_sub_ui(V, 1);
Johannes Doerferte7044942015-02-24 11:58:30 +0000126 isl_set *SUB = isl_set_upper_bound_val(S, type, dim, V);
127
Johannes Doerfert8f8af432015-04-26 20:07:21 +0000128 if (useLowerUpperBound)
Johannes Doerferte7044942015-02-24 11:58:30 +0000129 return isl_set_union(SLB, SUB);
130 else
131 return isl_set_intersect(SLB, SUB);
132}
133
Johannes Doerfert4eed5be2015-08-20 18:04:22 +0000134static const ScopArrayInfo *identifyBasePtrOriginSAI(Scop *S, Value *BasePtr) {
135 LoadInst *BasePtrLI = dyn_cast<LoadInst>(BasePtr);
136 if (!BasePtrLI)
137 return nullptr;
138
139 if (!S->getRegion().contains(BasePtrLI))
140 return nullptr;
141
142 ScalarEvolution &SE = *S->getSE();
143
144 auto *OriginBaseSCEV =
145 SE.getPointerBase(SE.getSCEV(BasePtrLI->getPointerOperand()));
146 if (!OriginBaseSCEV)
147 return nullptr;
148
149 auto *OriginBaseSCEVUnknown = dyn_cast<SCEVUnknown>(OriginBaseSCEV);
150 if (!OriginBaseSCEVUnknown)
151 return nullptr;
152
153 return S->getScopArrayInfo(OriginBaseSCEVUnknown->getValue());
154}
155
Tobias Grosser49ad36c2015-05-20 08:05:31 +0000156ScopArrayInfo::ScopArrayInfo(Value *BasePtr, Type *ElementType, isl_ctx *Ctx,
Tobias Grosser99c70dd2015-09-26 08:55:54 +0000157 ArrayRef<const SCEV *> Sizes, bool IsPHI, Scop *S)
158 : BasePtr(BasePtr), ElementType(ElementType), IsPHI(IsPHI), S(*S) {
Tobias Grosser92245222015-07-28 14:53:44 +0000159 std::string BasePtrName =
160 getIslCompatibleName("MemRef_", BasePtr, IsPHI ? "__phi" : "");
Johannes Doerfert1a28a892014-10-05 11:32:18 +0000161 Id = isl_id_alloc(Ctx, BasePtrName.c_str(), this);
Johannes Doerfert4eed5be2015-08-20 18:04:22 +0000162
Tobias Grosser99c70dd2015-09-26 08:55:54 +0000163 updateSizes(Sizes);
Johannes Doerfert4eed5be2015-08-20 18:04:22 +0000164 BasePtrOriginSAI = identifyBasePtrOriginSAI(S, BasePtr);
165 if (BasePtrOriginSAI)
166 const_cast<ScopArrayInfo *>(BasePtrOriginSAI)->addDerivedSAI(this);
Johannes Doerfert1a28a892014-10-05 11:32:18 +0000167}
168
Tobias Grosser99c70dd2015-09-26 08:55:54 +0000169__isl_give isl_space *ScopArrayInfo::getSpace() const {
170 auto Space =
171 isl_space_set_alloc(isl_id_get_ctx(Id), 0, getNumberOfDimensions());
172 Space = isl_space_set_tuple_id(Space, isl_dim_set, isl_id_copy(Id));
173 return Space;
174}
175
176void ScopArrayInfo::updateSizes(ArrayRef<const SCEV *> NewSizes) {
177#ifndef NDEBUG
178 int SharedDims = std::min(NewSizes.size(), DimensionSizes.size());
179 int ExtraDimsNew = NewSizes.size() - SharedDims;
180 int ExtraDimsOld = DimensionSizes.size() - SharedDims;
181 for (int i = 0; i < SharedDims; i++) {
182 assert(NewSizes[i + ExtraDimsNew] == DimensionSizes[i + ExtraDimsOld] &&
183 "Array update with non-matching dimension sizes");
184 }
185#endif
186
187 DimensionSizes.clear();
188 DimensionSizes.insert(DimensionSizes.begin(), NewSizes.begin(),
189 NewSizes.end());
190 for (isl_pw_aff *Size : DimensionSizesPw)
191 isl_pw_aff_free(Size);
192 DimensionSizesPw.clear();
193 for (const SCEV *Expr : DimensionSizes) {
194 isl_pw_aff *Size = S.getPwAff(Expr);
195 DimensionSizesPw.push_back(Size);
196 }
197}
198
Tobias Grosserd46fd5e2015-08-12 15:27:16 +0000199ScopArrayInfo::~ScopArrayInfo() {
200 isl_id_free(Id);
201 for (isl_pw_aff *Size : DimensionSizesPw)
202 isl_pw_aff_free(Size);
203}
Johannes Doerfert1a28a892014-10-05 11:32:18 +0000204
Tobias Grosser49ad36c2015-05-20 08:05:31 +0000205std::string ScopArrayInfo::getName() const { return isl_id_get_name(Id); }
206
207int ScopArrayInfo::getElemSizeInBytes() const {
208 return ElementType->getPrimitiveSizeInBits() / 8;
209}
210
Johannes Doerfert1a28a892014-10-05 11:32:18 +0000211isl_id *ScopArrayInfo::getBasePtrId() const { return isl_id_copy(Id); }
212
213void ScopArrayInfo::dump() const { print(errs()); }
214
Tobias Grosserd46fd5e2015-08-12 15:27:16 +0000215void ScopArrayInfo::print(raw_ostream &OS, bool SizeAsPwAff) const {
Tobias Grosser49ad36c2015-05-20 08:05:31 +0000216 OS.indent(8) << *getElementType() << " " << getName() << "[*]";
Tobias Grosserd46fd5e2015-08-12 15:27:16 +0000217 for (unsigned u = 0; u < getNumberOfDimensions(); u++) {
218 OS << "[";
219
220 if (SizeAsPwAff)
221 OS << " " << DimensionSizesPw[u] << " ";
222 else
223 OS << *DimensionSizes[u];
224
225 OS << "]";
226 }
227
Johannes Doerfert4eed5be2015-08-20 18:04:22 +0000228 if (BasePtrOriginSAI)
229 OS << " [BasePtrOrigin: " << BasePtrOriginSAI->getName() << "]";
230
Tobias Grosser49ad36c2015-05-20 08:05:31 +0000231 OS << " // Element size " << getElemSizeInBytes() << "\n";
Johannes Doerfert1a28a892014-10-05 11:32:18 +0000232}
233
234const ScopArrayInfo *
235ScopArrayInfo::getFromAccessFunction(__isl_keep isl_pw_multi_aff *PMA) {
236 isl_id *Id = isl_pw_multi_aff_get_tuple_id(PMA, isl_dim_out);
237 assert(Id && "Output dimension didn't have an ID");
238 return getFromId(Id);
239}
240
241const ScopArrayInfo *ScopArrayInfo::getFromId(isl_id *Id) {
242 void *User = isl_id_get_user(Id);
243 const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User);
244 isl_id_free(Id);
245 return SAI;
246}
247
Tobias Grosser99c70dd2015-09-26 08:55:54 +0000248void MemoryAccess::updateDimensionality() {
249 auto ArraySpace = getScopArrayInfo()->getSpace();
250 auto AccessSpace = isl_space_range(isl_map_get_space(AccessRelation));
251
252 auto DimsArray = isl_space_dim(ArraySpace, isl_dim_set);
253 auto DimsAccess = isl_space_dim(AccessSpace, isl_dim_set);
254 auto DimsMissing = DimsArray - DimsAccess;
255
256 auto Map = isl_map_from_domain_and_range(isl_set_universe(AccessSpace),
257 isl_set_universe(ArraySpace));
258
259 for (unsigned i = 0; i < DimsMissing; i++)
260 Map = isl_map_fix_si(Map, isl_dim_out, i, 0);
261
262 for (unsigned i = DimsMissing; i < DimsArray; i++)
263 Map = isl_map_equate(Map, isl_dim_in, i - DimsMissing, isl_dim_out, i);
264
265 AccessRelation = isl_map_apply_range(AccessRelation, Map);
266}
267
Johannes Doerfert32868bf2014-08-01 08:13:25 +0000268const std::string
269MemoryAccess::getReductionOperatorStr(MemoryAccess::ReductionType RT) {
270 switch (RT) {
271 case MemoryAccess::RT_NONE:
272 llvm_unreachable("Requested a reduction operator string for a memory "
273 "access which isn't a reduction");
274 case MemoryAccess::RT_ADD:
275 return "+";
276 case MemoryAccess::RT_MUL:
277 return "*";
278 case MemoryAccess::RT_BOR:
279 return "|";
280 case MemoryAccess::RT_BXOR:
281 return "^";
282 case MemoryAccess::RT_BAND:
283 return "&";
284 }
285 llvm_unreachable("Unknown reduction type");
286 return "";
287}
288
Johannes Doerfertf6183392014-07-01 20:52:51 +0000289/// @brief Return the reduction type for a given binary operator
290static MemoryAccess::ReductionType getReductionType(const BinaryOperator *BinOp,
291 const Instruction *Load) {
292 if (!BinOp)
293 return MemoryAccess::RT_NONE;
294 switch (BinOp->getOpcode()) {
295 case Instruction::FAdd:
296 if (!BinOp->hasUnsafeAlgebra())
297 return MemoryAccess::RT_NONE;
298 // Fall through
299 case Instruction::Add:
300 return MemoryAccess::RT_ADD;
301 case Instruction::Or:
302 return MemoryAccess::RT_BOR;
303 case Instruction::Xor:
304 return MemoryAccess::RT_BXOR;
305 case Instruction::And:
306 return MemoryAccess::RT_BAND;
307 case Instruction::FMul:
308 if (!BinOp->hasUnsafeAlgebra())
309 return MemoryAccess::RT_NONE;
310 // Fall through
311 case Instruction::Mul:
312 if (DisableMultiplicativeReductions)
313 return MemoryAccess::RT_NONE;
314 return MemoryAccess::RT_MUL;
315 default:
316 return MemoryAccess::RT_NONE;
317 }
318}
Tobias Grosser5fd8c092015-09-17 17:28:15 +0000319
Tobias Grosser5fd8c092015-09-17 17:28:15 +0000320/// @brief Derive the individual index expressions from a GEP instruction
321///
322/// This function optimistically assumes the GEP references into a fixed size
323/// array. If this is actually true, this function returns a list of array
324/// subscript expressions as SCEV as well as a list of integers describing
325/// the size of the individual array dimensions. Both lists have either equal
326/// length of the size list is one element shorter in case there is no known
327/// size available for the outermost array dimension.
328///
329/// @param GEP The GetElementPtr instruction to analyze.
330///
331/// @return A tuple with the subscript expressions and the dimension sizes.
332static std::tuple<std::vector<const SCEV *>, std::vector<int>>
333getIndexExpressionsFromGEP(GetElementPtrInst *GEP, ScalarEvolution &SE) {
334 std::vector<const SCEV *> Subscripts;
335 std::vector<int> Sizes;
336
337 Type *Ty = GEP->getPointerOperandType();
338
339 bool DroppedFirstDim = false;
340
Michael Kruse26ed65e2015-09-24 17:32:49 +0000341 for (unsigned i = 1; i < GEP->getNumOperands(); i++) {
Tobias Grosser5fd8c092015-09-17 17:28:15 +0000342
343 const SCEV *Expr = SE.getSCEV(GEP->getOperand(i));
344
345 if (i == 1) {
346 if (auto PtrTy = dyn_cast<PointerType>(Ty)) {
347 Ty = PtrTy->getElementType();
348 } else if (auto ArrayTy = dyn_cast<ArrayType>(Ty)) {
349 Ty = ArrayTy->getElementType();
350 } else {
351 Subscripts.clear();
352 Sizes.clear();
353 break;
354 }
355 if (auto Const = dyn_cast<SCEVConstant>(Expr))
356 if (Const->getValue()->isZero()) {
357 DroppedFirstDim = true;
358 continue;
359 }
360 Subscripts.push_back(Expr);
361 continue;
362 }
363
364 auto ArrayTy = dyn_cast<ArrayType>(Ty);
365 if (!ArrayTy) {
366 Subscripts.clear();
367 Sizes.clear();
368 break;
369 }
370
371 Subscripts.push_back(Expr);
372 if (!(DroppedFirstDim && i == 2))
373 Sizes.push_back(ArrayTy->getNumElements());
374
375 Ty = ArrayTy->getElementType();
376 }
377
378 return std::make_tuple(Subscripts, Sizes);
379}
380
Tobias Grosser75805372011-04-29 06:27:02 +0000381MemoryAccess::~MemoryAccess() {
Tobias Grosser6f48e0f2015-05-15 09:58:32 +0000382 isl_id_free(Id);
Tobias Grosser54a86e62011-08-18 06:31:46 +0000383 isl_map_free(AccessRelation);
Tobias Grosser166c4222015-09-05 07:46:40 +0000384 isl_map_free(NewAccessRelation);
Tobias Grosser75805372011-04-29 06:27:02 +0000385}
386
Johannes Doerfert1a28a892014-10-05 11:32:18 +0000387const ScopArrayInfo *MemoryAccess::getScopArrayInfo() const {
388 isl_id *ArrayId = getArrayId();
389 void *User = isl_id_get_user(ArrayId);
390 const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User);
391 isl_id_free(ArrayId);
392 return SAI;
393}
394
Tobias Grosser4f663aa2015-03-30 11:52:59 +0000395__isl_give isl_id *MemoryAccess::getArrayId() const {
Johannes Doerfert5d83f092014-07-29 08:37:55 +0000396 return isl_map_get_tuple_id(AccessRelation, isl_dim_out);
397}
398
Tobias Grosser4f663aa2015-03-30 11:52:59 +0000399__isl_give isl_pw_multi_aff *MemoryAccess::applyScheduleToAccessRelation(
400 __isl_take isl_union_map *USchedule) const {
Johannes Doerferta99130f2014-10-13 12:58:03 +0000401 isl_map *Schedule, *ScheduledAccRel;
402 isl_union_set *UDomain;
403
404 UDomain = isl_union_set_from_set(getStatement()->getDomain());
405 USchedule = isl_union_map_intersect_domain(USchedule, UDomain);
406 Schedule = isl_map_from_union_map(USchedule);
407 ScheduledAccRel = isl_map_apply_domain(getAccessRelation(), Schedule);
408 return isl_pw_multi_aff_from_map(ScheduledAccRel);
409}
410
Tobias Grosser4f663aa2015-03-30 11:52:59 +0000411__isl_give isl_map *MemoryAccess::getOriginalAccessRelation() const {
Tobias Grosser5d453812011-10-06 00:04:11 +0000412 return isl_map_copy(AccessRelation);
413}
414
Johannes Doerferta99130f2014-10-13 12:58:03 +0000415std::string MemoryAccess::getOriginalAccessRelationStr() const {
Tobias Grosser5d453812011-10-06 00:04:11 +0000416 return stringFromIslObj(AccessRelation);
417}
418
Johannes Doerferta99130f2014-10-13 12:58:03 +0000419__isl_give isl_space *MemoryAccess::getOriginalAccessRelationSpace() const {
Tobias Grosser5e6813d2014-07-02 17:47:48 +0000420 return isl_map_get_space(AccessRelation);
421}
422
Tobias Grosser4f663aa2015-03-30 11:52:59 +0000423__isl_give isl_map *MemoryAccess::getNewAccessRelation() const {
Tobias Grosser166c4222015-09-05 07:46:40 +0000424 return isl_map_copy(NewAccessRelation);
Tobias Grosser75805372011-04-29 06:27:02 +0000425}
426
Tobias Grosser6f730082015-09-05 07:46:47 +0000427std::string MemoryAccess::getNewAccessRelationStr() const {
428 return stringFromIslObj(NewAccessRelation);
429}
430
Tobias Grosser4f663aa2015-03-30 11:52:59 +0000431__isl_give isl_basic_map *
432MemoryAccess::createBasicAccessMap(ScopStmt *Statement) {
Tobias Grosser084d8f72012-05-29 09:29:44 +0000433 isl_space *Space = isl_space_set_alloc(Statement->getIslCtx(), 0, 1);
Tobias Grossered295662012-09-11 13:50:21 +0000434 Space = isl_space_align_params(Space, Statement->getDomainSpace());
Tobias Grosser75805372011-04-29 06:27:02 +0000435
Tobias Grosser084d8f72012-05-29 09:29:44 +0000436 return isl_basic_map_from_domain_and_range(
Tobias Grosserabfbe632013-02-05 12:09:06 +0000437 isl_basic_set_universe(Statement->getDomainSpace()),
438 isl_basic_set_universe(Space));
Tobias Grosser75805372011-04-29 06:27:02 +0000439}
440
Tobias Grosser5e6813d2014-07-02 17:47:48 +0000441// Formalize no out-of-bound access assumption
442//
443// When delinearizing array accesses we optimistically assume that the
444// delinearized accesses do not access out of bound locations (the subscript
445// expression of each array evaluates for each statement instance that is
446// executed to a value that is larger than zero and strictly smaller than the
447// size of the corresponding dimension). The only exception is the outermost
Tobias Grosserf57d63f2014-08-03 21:07:30 +0000448// dimension for which we do not need to assume any upper bound. At this point
449// we formalize this assumption to ensure that at code generation time the
450// relevant run-time checks can be generated.
Tobias Grosser5e6813d2014-07-02 17:47:48 +0000451//
452// To find the set of constraints necessary to avoid out of bound accesses, we
453// first build the set of data locations that are not within array bounds. We
454// then apply the reverse access relation to obtain the set of iterations that
455// may contain invalid accesses and reduce this set of iterations to the ones
456// that are actually executed by intersecting them with the domain of the
457// statement. If we now project out all loop dimensions, we obtain a set of
458// parameters that may cause statement instances to be executed that may
459// possibly yield out of bound memory accesses. The complement of these
460// constraints is the set of constraints that needs to be assumed to ensure such
461// statement instances are never executed.
Michael Krusee2bccbb2015-09-18 19:59:43 +0000462void MemoryAccess::assumeNoOutOfBound() {
Johannes Doerferta99130f2014-10-13 12:58:03 +0000463 isl_space *Space = isl_space_range(getOriginalAccessRelationSpace());
Tobias Grosser5e6813d2014-07-02 17:47:48 +0000464 isl_set *Outside = isl_set_empty(isl_space_copy(Space));
Michael Krusee2bccbb2015-09-18 19:59:43 +0000465 for (int i = 1, Size = Subscripts.size(); i < Size; ++i) {
Tobias Grosser5e6813d2014-07-02 17:47:48 +0000466 isl_local_space *LS = isl_local_space_from_space(isl_space_copy(Space));
467 isl_pw_aff *Var =
468 isl_pw_aff_var_on_domain(isl_local_space_copy(LS), isl_dim_set, i);
469 isl_pw_aff *Zero = isl_pw_aff_zero_on_domain(LS);
470
471 isl_set *DimOutside;
472
Tobias Grosserf57d63f2014-08-03 21:07:30 +0000473 DimOutside = isl_pw_aff_lt_set(isl_pw_aff_copy(Var), Zero);
Michael Krusee2bccbb2015-09-18 19:59:43 +0000474 isl_pw_aff *SizeE = Statement->getPwAff(Sizes[i - 1]);
Tobias Grosser5e6813d2014-07-02 17:47:48 +0000475
Tobias Grosserf57d63f2014-08-03 21:07:30 +0000476 SizeE = isl_pw_aff_drop_dims(SizeE, isl_dim_in, 0,
477 Statement->getNumIterators());
478 SizeE = isl_pw_aff_add_dims(SizeE, isl_dim_in,
479 isl_space_dim(Space, isl_dim_set));
480 SizeE = isl_pw_aff_set_tuple_id(SizeE, isl_dim_in,
481 isl_space_get_tuple_id(Space, isl_dim_set));
Tobias Grosser5e6813d2014-07-02 17:47:48 +0000482
Tobias Grosserf57d63f2014-08-03 21:07:30 +0000483 DimOutside = isl_set_union(DimOutside, isl_pw_aff_le_set(SizeE, Var));
Tobias Grosser5e6813d2014-07-02 17:47:48 +0000484
485 Outside = isl_set_union(Outside, DimOutside);
486 }
487
488 Outside = isl_set_apply(Outside, isl_map_reverse(getAccessRelation()));
489 Outside = isl_set_intersect(Outside, Statement->getDomain());
490 Outside = isl_set_params(Outside);
Tobias Grosserf54bb772015-06-26 12:09:28 +0000491
492 // Remove divs to avoid the construction of overly complicated assumptions.
493 // Doing so increases the set of parameter combinations that are assumed to
494 // not appear. This is always save, but may make the resulting run-time check
495 // bail out more often than strictly necessary.
496 Outside = isl_set_remove_divs(Outside);
Tobias Grosser5e6813d2014-07-02 17:47:48 +0000497 Outside = isl_set_complement(Outside);
498 Statement->getParent()->addAssumption(Outside);
499 isl_space_free(Space);
500}
501
Johannes Doerferte7044942015-02-24 11:58:30 +0000502void MemoryAccess::computeBoundsOnAccessRelation(unsigned ElementSize) {
503 ScalarEvolution *SE = Statement->getParent()->getSE();
504
505 Value *Ptr = getPointerOperand(*getAccessInstruction());
506 if (!Ptr || !SE->isSCEVable(Ptr->getType()))
507 return;
508
509 auto *PtrSCEV = SE->getSCEV(Ptr);
510 if (isa<SCEVCouldNotCompute>(PtrSCEV))
511 return;
512
513 auto *BasePtrSCEV = SE->getPointerBase(PtrSCEV);
514 if (BasePtrSCEV && !isa<SCEVCouldNotCompute>(BasePtrSCEV))
515 PtrSCEV = SE->getMinusSCEV(PtrSCEV, BasePtrSCEV);
516
517 const ConstantRange &Range = SE->getSignedRange(PtrSCEV);
518 if (Range.isFullSet())
519 return;
520
Johannes Doerferte4bd53b2015-03-08 19:49:50 +0000521 bool isWrapping = Range.isSignWrappedSet();
Johannes Doerferte7044942015-02-24 11:58:30 +0000522 unsigned BW = Range.getBitWidth();
Johannes Doerferte4bd53b2015-03-08 19:49:50 +0000523 const auto LB = isWrapping ? Range.getLower() : Range.getSignedMin();
524 const auto UB = isWrapping ? Range.getUpper() : Range.getSignedMax();
525
526 auto Min = LB.sdiv(APInt(BW, ElementSize));
527 auto Max = (UB - APInt(BW, 1)).sdiv(APInt(BW, ElementSize));
Johannes Doerferte7044942015-02-24 11:58:30 +0000528
529 isl_set *AccessRange = isl_map_range(isl_map_copy(AccessRelation));
530 AccessRange =
531 addRangeBoundsToSet(AccessRange, ConstantRange(Min, Max), 0, isl_dim_set);
532 AccessRelation = isl_map_intersect_range(AccessRelation, AccessRange);
533}
534
Michael Krusee2bccbb2015-09-18 19:59:43 +0000535__isl_give isl_map *MemoryAccess::foldAccess(__isl_take isl_map *AccessRelation,
Tobias Grosser619190d2015-03-30 17:22:28 +0000536 ScopStmt *Statement) {
Michael Krusee2bccbb2015-09-18 19:59:43 +0000537 int Size = Subscripts.size();
Tobias Grosser619190d2015-03-30 17:22:28 +0000538
539 for (int i = Size - 2; i >= 0; --i) {
540 isl_space *Space;
541 isl_map *MapOne, *MapTwo;
Michael Krusee2bccbb2015-09-18 19:59:43 +0000542 isl_pw_aff *DimSize = Statement->getPwAff(Sizes[i]);
Tobias Grosser619190d2015-03-30 17:22:28 +0000543
544 isl_space *SpaceSize = isl_pw_aff_get_space(DimSize);
545 isl_pw_aff_free(DimSize);
546 isl_id *ParamId = isl_space_get_dim_id(SpaceSize, isl_dim_param, 0);
547
548 Space = isl_map_get_space(AccessRelation);
549 Space = isl_space_map_from_set(isl_space_range(Space));
550 Space = isl_space_align_params(Space, SpaceSize);
551
552 int ParamLocation = isl_space_find_dim_by_id(Space, isl_dim_param, ParamId);
553 isl_id_free(ParamId);
554
555 MapOne = isl_map_universe(isl_space_copy(Space));
556 for (int j = 0; j < Size; ++j)
557 MapOne = isl_map_equate(MapOne, isl_dim_in, j, isl_dim_out, j);
558 MapOne = isl_map_lower_bound_si(MapOne, isl_dim_in, i + 1, 0);
559
560 MapTwo = isl_map_universe(isl_space_copy(Space));
561 for (int j = 0; j < Size; ++j)
562 if (j < i || j > i + 1)
563 MapTwo = isl_map_equate(MapTwo, isl_dim_in, j, isl_dim_out, j);
564
565 isl_local_space *LS = isl_local_space_from_space(Space);
566 isl_constraint *C;
567 C = isl_equality_alloc(isl_local_space_copy(LS));
568 C = isl_constraint_set_constant_si(C, -1);
569 C = isl_constraint_set_coefficient_si(C, isl_dim_in, i, 1);
570 C = isl_constraint_set_coefficient_si(C, isl_dim_out, i, -1);
571 MapTwo = isl_map_add_constraint(MapTwo, C);
572 C = isl_equality_alloc(LS);
573 C = isl_constraint_set_coefficient_si(C, isl_dim_in, i + 1, 1);
574 C = isl_constraint_set_coefficient_si(C, isl_dim_out, i + 1, -1);
575 C = isl_constraint_set_coefficient_si(C, isl_dim_param, ParamLocation, 1);
576 MapTwo = isl_map_add_constraint(MapTwo, C);
577 MapTwo = isl_map_upper_bound_si(MapTwo, isl_dim_in, i + 1, -1);
578
579 MapOne = isl_map_union(MapOne, MapTwo);
580 AccessRelation = isl_map_apply_range(AccessRelation, MapOne);
581 }
582 return AccessRelation;
583}
584
Michael Krusee2bccbb2015-09-18 19:59:43 +0000585void MemoryAccess::buildAccessRelation(const ScopArrayInfo *SAI) {
586 assert(!AccessRelation && "AccessReltation already built");
Tobias Grosser75805372011-04-29 06:27:02 +0000587
Michael Krusee2bccbb2015-09-18 19:59:43 +0000588 isl_ctx *Ctx = isl_id_get_ctx(Id);
Johannes Doerfert1a28a892014-10-05 11:32:18 +0000589 isl_id *BaseAddrId = SAI->getBasePtrId();
Tobias Grosser5683df42011-11-09 22:34:34 +0000590
Michael Krusee2bccbb2015-09-18 19:59:43 +0000591 if (!isAffine()) {
Tobias Grosser4f967492013-06-23 05:21:18 +0000592 // We overapproximate non-affine accesses with a possible access to the
593 // whole array. For read accesses it does not make a difference, if an
594 // access must or may happen. However, for write accesses it is important to
595 // differentiate between writes that must happen and writes that may happen.
Tobias Grosser04d6ae62013-06-23 06:04:54 +0000596 AccessRelation = isl_map_from_basic_map(createBasicAccessMap(Statement));
Johannes Doerfert5d83f092014-07-29 08:37:55 +0000597 AccessRelation =
598 isl_map_set_tuple_id(AccessRelation, isl_dim_out, BaseAddrId);
Johannes Doerferte7044942015-02-24 11:58:30 +0000599
Michael Krusee2bccbb2015-09-18 19:59:43 +0000600 computeBoundsOnAccessRelation(getElemSizeInBytes());
Tobias Grossera1879642011-12-20 10:43:14 +0000601 return;
602 }
603
Johannes Doerfert5d83f092014-07-29 08:37:55 +0000604 isl_space *Space = isl_space_alloc(Ctx, 0, Statement->getNumIterators(), 0);
Tobias Grosser79baa212014-04-10 08:38:02 +0000605 AccessRelation = isl_map_universe(Space);
Tobias Grossera1879642011-12-20 10:43:14 +0000606
Michael Krusee2bccbb2015-09-18 19:59:43 +0000607 for (int i = 0, Size = Subscripts.size(); i < Size; ++i) {
608 isl_pw_aff *Affine = Statement->getPwAff(Subscripts[i]);
Tobias Grosser75805372011-04-29 06:27:02 +0000609
Sebastian Pop422e33f2014-06-03 18:16:31 +0000610 if (Size == 1) {
611 // For the non delinearized arrays, divide the access function of the last
612 // subscript by the size of the elements in the array.
Sebastian Pop18016682014-04-08 21:20:44 +0000613 //
614 // A stride one array access in C expressed as A[i] is expressed in
615 // LLVM-IR as something like A[i * elementsize]. This hides the fact that
616 // two subsequent values of 'i' index two values that are stored next to
617 // each other in memory. By this division we make this characteristic
618 // obvious again.
Michael Krusee2bccbb2015-09-18 19:59:43 +0000619 isl_val *v = isl_val_int_from_si(Ctx, getElemSizeInBytes());
Sebastian Pop18016682014-04-08 21:20:44 +0000620 Affine = isl_pw_aff_scale_down_val(Affine, v);
621 }
622
623 isl_map *SubscriptMap = isl_map_from_pw_aff(Affine);
624
Tobias Grosser79baa212014-04-10 08:38:02 +0000625 AccessRelation = isl_map_flat_range_product(AccessRelation, SubscriptMap);
Sebastian Pop18016682014-04-08 21:20:44 +0000626 }
627
Michael Krusee2bccbb2015-09-18 19:59:43 +0000628 if (Sizes.size() > 1 && !isa<SCEVConstant>(Sizes[0]))
629 AccessRelation = foldAccess(AccessRelation, Statement);
Tobias Grosser619190d2015-03-30 17:22:28 +0000630
Tobias Grosser79baa212014-04-10 08:38:02 +0000631 Space = Statement->getDomainSpace();
Tobias Grosserabfbe632013-02-05 12:09:06 +0000632 AccessRelation = isl_map_set_tuple_id(
633 AccessRelation, isl_dim_in, isl_space_get_tuple_id(Space, isl_dim_set));
Johannes Doerfert5d83f092014-07-29 08:37:55 +0000634 AccessRelation =
635 isl_map_set_tuple_id(AccessRelation, isl_dim_out, BaseAddrId);
636
Michael Krusee2bccbb2015-09-18 19:59:43 +0000637 assumeNoOutOfBound();
Tobias Grosseraa660a92015-03-30 00:07:50 +0000638 AccessRelation = isl_map_gist_domain(AccessRelation, Statement->getDomain());
Johannes Doerfert5d83f092014-07-29 08:37:55 +0000639 isl_space_free(Space);
Tobias Grosser8cae72f2011-11-08 15:41:08 +0000640}
Tobias Grosser30b8a092011-08-18 07:51:37 +0000641
Michael Krusecac948e2015-10-02 13:53:07 +0000642MemoryAccess::MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst,
643 __isl_take isl_id *Id, AccessType Type,
644 Value *BaseAddress, unsigned ElemBytes, bool Affine,
Michael Krusee2bccbb2015-09-18 19:59:43 +0000645 ArrayRef<const SCEV *> Subscripts,
646 ArrayRef<const SCEV *> Sizes, Value *AccessValue,
Michael Kruse8d0b7342015-09-25 21:21:00 +0000647 AccessOrigin Origin, StringRef BaseName)
Michael Krusecac948e2015-10-02 13:53:07 +0000648 : Id(Id), Origin(Origin), AccType(Type), RedType(RT_NONE), Statement(Stmt),
649 BaseAddr(BaseAddress), BaseName(BaseName), ElemBytes(ElemBytes),
650 Sizes(Sizes.begin(), Sizes.end()), AccessInstruction(AccessInst),
651 AccessValue(AccessValue), IsAffine(Affine),
Michael Krusee2bccbb2015-09-18 19:59:43 +0000652 Subscripts(Subscripts.begin(), Subscripts.end()), AccessRelation(nullptr),
653 NewAccessRelation(nullptr) {}
654
Tobias Grosser8cae72f2011-11-08 15:41:08 +0000655void MemoryAccess::realignParams() {
Tobias Grosser6defb5b2014-04-10 08:37:44 +0000656 isl_space *ParamSpace = Statement->getParent()->getParamSpace();
Tobias Grosser37487052011-10-06 00:03:42 +0000657 AccessRelation = isl_map_align_params(AccessRelation, ParamSpace);
Tobias Grosser75805372011-04-29 06:27:02 +0000658}
659
Johannes Doerfert32868bf2014-08-01 08:13:25 +0000660const std::string MemoryAccess::getReductionOperatorStr() const {
661 return MemoryAccess::getReductionOperatorStr(getReductionType());
662}
663
Tobias Grosser6f48e0f2015-05-15 09:58:32 +0000664__isl_give isl_id *MemoryAccess::getId() const { return isl_id_copy(Id); }
665
Johannes Doerfertf6183392014-07-01 20:52:51 +0000666raw_ostream &polly::operator<<(raw_ostream &OS,
667 MemoryAccess::ReductionType RT) {
Johannes Doerfert32868bf2014-08-01 08:13:25 +0000668 if (RT == MemoryAccess::RT_NONE)
Johannes Doerfertf6183392014-07-01 20:52:51 +0000669 OS << "NONE";
Johannes Doerfert32868bf2014-08-01 08:13:25 +0000670 else
671 OS << MemoryAccess::getReductionOperatorStr(RT);
Johannes Doerfertf6183392014-07-01 20:52:51 +0000672 return OS;
673}
674
Tobias Grosser75805372011-04-29 06:27:02 +0000675void MemoryAccess::print(raw_ostream &OS) const {
Johannes Doerfert4c7ce472014-10-08 10:11:33 +0000676 switch (AccType) {
Tobias Grosserb58f6a42013-07-13 20:41:24 +0000677 case READ:
Johannes Doerfert6780bc32014-06-26 18:47:03 +0000678 OS.indent(12) << "ReadAccess :=\t";
Tobias Grosser4f967492013-06-23 05:21:18 +0000679 break;
Tobias Grosserb58f6a42013-07-13 20:41:24 +0000680 case MUST_WRITE:
Johannes Doerfert6780bc32014-06-26 18:47:03 +0000681 OS.indent(12) << "MustWriteAccess :=\t";
Tobias Grosser4f967492013-06-23 05:21:18 +0000682 break;
Tobias Grosserb58f6a42013-07-13 20:41:24 +0000683 case MAY_WRITE:
Johannes Doerfert6780bc32014-06-26 18:47:03 +0000684 OS.indent(12) << "MayWriteAccess :=\t";
Tobias Grosser4f967492013-06-23 05:21:18 +0000685 break;
686 }
Johannes Doerfert0ff23ec2015-02-06 20:13:15 +0000687 OS << "[Reduction Type: " << getReductionType() << "] ";
Michael Kruse8d0b7342015-09-25 21:21:00 +0000688 OS << "[Scalar: " << isImplicit() << "]\n";
Johannes Doerferta99130f2014-10-13 12:58:03 +0000689 OS.indent(16) << getOriginalAccessRelationStr() << ";\n";
Tobias Grosser6f730082015-09-05 07:46:47 +0000690 if (hasNewAccessRelation())
691 OS.indent(11) << "new: " << getNewAccessRelationStr() << ";\n";
Tobias Grosser75805372011-04-29 06:27:02 +0000692}
693
Tobias Grosser74394f02013-01-14 22:40:23 +0000694void MemoryAccess::dump() const { print(errs()); }
Tobias Grosser75805372011-04-29 06:27:02 +0000695
696// Create a map in the size of the provided set domain, that maps from the
697// one element of the provided set domain to another element of the provided
698// set domain.
699// The mapping is limited to all points that are equal in all but the last
700// dimension and for which the last dimension of the input is strict smaller
701// than the last dimension of the output.
702//
703// getEqualAndLarger(set[i0, i1, ..., iX]):
704//
705// set[i0, i1, ..., iX] -> set[o0, o1, ..., oX]
706// : i0 = o0, i1 = o1, ..., i(X-1) = o(X-1), iX < oX
707//
Tobias Grosserf5338802011-10-06 00:03:35 +0000708static isl_map *getEqualAndLarger(isl_space *setDomain) {
Tobias Grosserc327932c2012-02-01 14:23:36 +0000709 isl_space *Space = isl_space_map_from_set(setDomain);
Tobias Grosser1b6ea572015-05-21 19:02:44 +0000710 isl_map *Map = isl_map_universe(Space);
Sebastian Pop40408762013-10-04 17:14:53 +0000711 unsigned lastDimension = isl_map_dim(Map, isl_dim_in) - 1;
Tobias Grosser75805372011-04-29 06:27:02 +0000712
713 // Set all but the last dimension to be equal for the input and output
714 //
715 // input[i0, i1, ..., iX] -> output[o0, o1, ..., oX]
716 // : i0 = o0, i1 = o1, ..., i(X-1) = o(X-1)
Sebastian Pop40408762013-10-04 17:14:53 +0000717 for (unsigned i = 0; i < lastDimension; ++i)
Tobias Grosserc327932c2012-02-01 14:23:36 +0000718 Map = isl_map_equate(Map, isl_dim_in, i, isl_dim_out, i);
Tobias Grosser75805372011-04-29 06:27:02 +0000719
720 // Set the last dimension of the input to be strict smaller than the
721 // last dimension of the output.
722 //
723 // input[?,?,?,...,iX] -> output[?,?,?,...,oX] : iX < oX
Tobias Grosser1b6ea572015-05-21 19:02:44 +0000724 Map = isl_map_order_lt(Map, isl_dim_in, lastDimension, isl_dim_out,
725 lastDimension);
Tobias Grosserc327932c2012-02-01 14:23:36 +0000726 return Map;
Tobias Grosser75805372011-04-29 06:27:02 +0000727}
728
Tobias Grosser4f663aa2015-03-30 11:52:59 +0000729__isl_give isl_set *
730MemoryAccess::getStride(__isl_take const isl_map *Schedule) const {
Tobias Grosserabfbe632013-02-05 12:09:06 +0000731 isl_map *S = const_cast<isl_map *>(Schedule);
Johannes Doerferta99130f2014-10-13 12:58:03 +0000732 isl_map *AccessRelation = getAccessRelation();
Sebastian Popa00a0292012-12-18 07:46:06 +0000733 isl_space *Space = isl_space_range(isl_map_get_space(S));
734 isl_map *NextScatt = getEqualAndLarger(Space);
Tobias Grosser75805372011-04-29 06:27:02 +0000735
Sebastian Popa00a0292012-12-18 07:46:06 +0000736 S = isl_map_reverse(S);
737 NextScatt = isl_map_lexmin(NextScatt);
Tobias Grosser75805372011-04-29 06:27:02 +0000738
Sebastian Popa00a0292012-12-18 07:46:06 +0000739 NextScatt = isl_map_apply_range(NextScatt, isl_map_copy(S));
740 NextScatt = isl_map_apply_range(NextScatt, isl_map_copy(AccessRelation));
741 NextScatt = isl_map_apply_domain(NextScatt, S);
742 NextScatt = isl_map_apply_domain(NextScatt, AccessRelation);
Tobias Grosser75805372011-04-29 06:27:02 +0000743
Sebastian Popa00a0292012-12-18 07:46:06 +0000744 isl_set *Deltas = isl_map_deltas(NextScatt);
745 return Deltas;
Tobias Grosser75805372011-04-29 06:27:02 +0000746}
747
Sebastian Popa00a0292012-12-18 07:46:06 +0000748bool MemoryAccess::isStrideX(__isl_take const isl_map *Schedule,
Tobias Grosser28dd4862012-01-24 16:42:16 +0000749 int StrideWidth) const {
750 isl_set *Stride, *StrideX;
751 bool IsStrideX;
Tobias Grosser75805372011-04-29 06:27:02 +0000752
Sebastian Popa00a0292012-12-18 07:46:06 +0000753 Stride = getStride(Schedule);
Tobias Grosser28dd4862012-01-24 16:42:16 +0000754 StrideX = isl_set_universe(isl_set_get_space(Stride));
Tobias Grosser01c8f5f2015-08-24 22:20:46 +0000755 for (unsigned i = 0; i < isl_set_dim(StrideX, isl_dim_set) - 1; i++)
756 StrideX = isl_set_fix_si(StrideX, isl_dim_set, i, 0);
757 StrideX = isl_set_fix_si(StrideX, isl_dim_set,
758 isl_set_dim(StrideX, isl_dim_set) - 1, StrideWidth);
Roman Gareevf2bd72e2015-08-18 16:12:05 +0000759 IsStrideX = isl_set_is_subset(Stride, StrideX);
Tobias Grosser75805372011-04-29 06:27:02 +0000760
Tobias Grosser28dd4862012-01-24 16:42:16 +0000761 isl_set_free(StrideX);
Tobias Grosserdea98232012-01-17 20:34:27 +0000762 isl_set_free(Stride);
Tobias Grosserb76f38532011-08-20 11:11:25 +0000763
Tobias Grosser28dd4862012-01-24 16:42:16 +0000764 return IsStrideX;
765}
766
Sebastian Popa00a0292012-12-18 07:46:06 +0000767bool MemoryAccess::isStrideZero(const isl_map *Schedule) const {
768 return isStrideX(Schedule, 0);
Tobias Grosser75805372011-04-29 06:27:02 +0000769}
770
Sebastian Popa00a0292012-12-18 07:46:06 +0000771bool MemoryAccess::isStrideOne(const isl_map *Schedule) const {
772 return isStrideX(Schedule, 1);
Tobias Grosser75805372011-04-29 06:27:02 +0000773}
774
Tobias Grosser166c4222015-09-05 07:46:40 +0000775void MemoryAccess::setNewAccessRelation(isl_map *NewAccess) {
776 isl_map_free(NewAccessRelation);
777 NewAccessRelation = NewAccess;
Raghesh Aloor3cb66282011-07-12 17:14:03 +0000778}
Tobias Grosser75805372011-04-29 06:27:02 +0000779
780//===----------------------------------------------------------------------===//
Tobias Grossercf3942d2011-10-06 00:04:05 +0000781
Tobias Grosser808cd692015-07-14 09:33:13 +0000782isl_map *ScopStmt::getSchedule() const {
783 isl_set *Domain = getDomain();
784 if (isl_set_is_empty(Domain)) {
785 isl_set_free(Domain);
786 return isl_map_from_aff(
787 isl_aff_zero_on_domain(isl_local_space_from_space(getDomainSpace())));
788 }
789 auto *Schedule = getParent()->getSchedule();
790 Schedule = isl_union_map_intersect_domain(
791 Schedule, isl_union_set_from_set(isl_set_copy(Domain)));
792 if (isl_union_map_is_empty(Schedule)) {
793 isl_set_free(Domain);
794 isl_union_map_free(Schedule);
795 return isl_map_from_aff(
796 isl_aff_zero_on_domain(isl_local_space_from_space(getDomainSpace())));
797 }
798 auto *M = isl_map_from_union_map(Schedule);
799 M = isl_map_coalesce(M);
800 M = isl_map_gist_domain(M, Domain);
801 M = isl_map_coalesce(M);
802 return M;
803}
Tobias Grossercf3942d2011-10-06 00:04:05 +0000804
Johannes Doerfert574182d2015-08-12 10:19:50 +0000805__isl_give isl_pw_aff *ScopStmt::getPwAff(const SCEV *E) {
Johannes Doerfertcef616f2015-09-15 22:49:04 +0000806 return getParent()->getPwAff(E, isBlockStmt() ? getBasicBlock()
807 : getRegion()->getEntry());
Johannes Doerfert574182d2015-08-12 10:19:50 +0000808}
809
Tobias Grosser37eb4222014-02-20 21:43:54 +0000810void ScopStmt::restrictDomain(__isl_take isl_set *NewDomain) {
811 assert(isl_set_is_subset(NewDomain, Domain) &&
812 "New domain is not a subset of old domain!");
813 isl_set_free(Domain);
814 Domain = NewDomain;
Tobias Grosser75805372011-04-29 06:27:02 +0000815}
816
Michael Krusecac948e2015-10-02 13:53:07 +0000817void ScopStmt::buildAccessRelations() {
818 for (MemoryAccess *Access : MemAccs) {
819 Type *ElementType = Access->getAccessValue()->getType();
Johannes Doerfert1a28a892014-10-05 11:32:18 +0000820
Johannes Doerfert80ef1102014-11-07 08:31:31 +0000821 const ScopArrayInfo *SAI = getParent()->getOrCreateScopArrayInfo(
Michael Krusecac948e2015-10-02 13:53:07 +0000822 Access->getBaseAddr(), ElementType, Access->Sizes, Access->isPHI());
Johannes Doerfert80ef1102014-11-07 08:31:31 +0000823
Michael Krusecac948e2015-10-02 13:53:07 +0000824 Access->buildAccessRelation(SAI);
Tobias Grosser75805372011-04-29 06:27:02 +0000825 }
826}
827
Michael Krusecac948e2015-10-02 13:53:07 +0000828void ScopStmt::addAccess(MemoryAccess *Access) {
829 Instruction *AccessInst = Access->getAccessInstruction();
830
831 MemoryAccessList *&MAL = InstructionToAccess[AccessInst];
832 if (!MAL)
833 MAL = new MemoryAccessList();
834 MAL->emplace_front(Access);
835 MemAccs.push_back(MAL->front());
836}
837
Tobias Grosser8cae72f2011-11-08 15:41:08 +0000838void ScopStmt::realignParams() {
Johannes Doerfertf6752892014-06-13 18:01:45 +0000839 for (MemoryAccess *MA : *this)
840 MA->realignParams();
Tobias Grosser8cae72f2011-11-08 15:41:08 +0000841
842 Domain = isl_set_align_params(Domain, Parent.getParamSpace());
Tobias Grosser8cae72f2011-11-08 15:41:08 +0000843}
844
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +0000845/// @brief Add @p BSet to the set @p User if @p BSet is bounded.
846static isl_stat collectBoundedParts(__isl_take isl_basic_set *BSet,
847 void *User) {
848 isl_set **BoundedParts = static_cast<isl_set **>(User);
849 if (isl_basic_set_is_bounded(BSet))
850 *BoundedParts = isl_set_union(*BoundedParts, isl_set_from_basic_set(BSet));
851 else
852 isl_basic_set_free(BSet);
853 return isl_stat_ok;
854}
855
856/// @brief Return the bounded parts of @p S.
857static __isl_give isl_set *collectBoundedParts(__isl_take isl_set *S) {
858 isl_set *BoundedParts = isl_set_empty(isl_set_get_space(S));
859 isl_set_foreach_basic_set(S, collectBoundedParts, &BoundedParts);
860 isl_set_free(S);
861 return BoundedParts;
862}
863
864/// @brief Compute the (un)bounded parts of @p S wrt. to dimension @p Dim.
865///
866/// @returns A separation of @p S into first an unbounded then a bounded subset,
867/// both with regards to the dimension @p Dim.
868static std::pair<__isl_give isl_set *, __isl_give isl_set *>
869partitionSetParts(__isl_take isl_set *S, unsigned Dim) {
870
871 for (unsigned u = 0, e = isl_set_n_dim(S); u < e; u++)
Johannes Doerfertf2cc86e2015-09-20 16:15:32 +0000872 S = isl_set_lower_bound_si(S, isl_dim_set, u, 0);
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +0000873
874 unsigned NumDimsS = isl_set_n_dim(S);
Johannes Doerfertf2cc86e2015-09-20 16:15:32 +0000875 isl_set *OnlyDimS = isl_set_copy(S);
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +0000876
877 // Remove dimensions that are greater than Dim as they are not interesting.
878 assert(NumDimsS >= Dim + 1);
879 OnlyDimS =
880 isl_set_project_out(OnlyDimS, isl_dim_set, Dim + 1, NumDimsS - Dim - 1);
881
882 // Create artificial parametric upper bounds for dimensions smaller than Dim
883 // as we are not interested in them.
884 OnlyDimS = isl_set_insert_dims(OnlyDimS, isl_dim_param, 0, Dim);
885 for (unsigned u = 0; u < Dim; u++) {
886 isl_constraint *C = isl_inequality_alloc(
887 isl_local_space_from_space(isl_set_get_space(OnlyDimS)));
888 C = isl_constraint_set_coefficient_si(C, isl_dim_param, u, 1);
889 C = isl_constraint_set_coefficient_si(C, isl_dim_set, u, -1);
890 OnlyDimS = isl_set_add_constraint(OnlyDimS, C);
891 }
892
893 // Collect all bounded parts of OnlyDimS.
894 isl_set *BoundedParts = collectBoundedParts(OnlyDimS);
895
896 // Create the dimensions greater than Dim again.
897 BoundedParts = isl_set_insert_dims(BoundedParts, isl_dim_set, Dim + 1,
898 NumDimsS - Dim - 1);
899
900 // Remove the artificial upper bound parameters again.
901 BoundedParts = isl_set_remove_dims(BoundedParts, isl_dim_param, 0, Dim);
902
Johannes Doerfertf2cc86e2015-09-20 16:15:32 +0000903 isl_set *UnboundedParts = isl_set_subtract(S, isl_set_copy(BoundedParts));
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +0000904 return std::make_pair(UnboundedParts, BoundedParts);
905}
906
Johannes Doerfert9a132f32015-09-28 09:33:22 +0000907/// @brief Set the dimension Ids from @p From in @p To.
908static __isl_give isl_set *setDimensionIds(__isl_keep isl_set *From,
909 __isl_take isl_set *To) {
910 for (unsigned u = 0, e = isl_set_n_dim(From); u < e; u++) {
911 isl_id *DimId = isl_set_get_dim_id(From, isl_dim_set, u);
912 To = isl_set_set_dim_id(To, isl_dim_set, u, DimId);
913 }
914 return To;
915}
916
917/// @brief Create the conditions under which @p L @p Pred @p R is true.
Johannes Doerfert96425c22015-08-30 21:13:53 +0000918static __isl_give isl_set *buildConditionSet(ICmpInst::Predicate Pred,
Johannes Doerfert9a132f32015-09-28 09:33:22 +0000919 __isl_take isl_pw_aff *L,
920 __isl_take isl_pw_aff *R) {
Johannes Doerfert96425c22015-08-30 21:13:53 +0000921 switch (Pred) {
922 case ICmpInst::ICMP_EQ:
923 return isl_pw_aff_eq_set(L, R);
924 case ICmpInst::ICMP_NE:
925 return isl_pw_aff_ne_set(L, R);
926 case ICmpInst::ICMP_SLT:
927 return isl_pw_aff_lt_set(L, R);
928 case ICmpInst::ICMP_SLE:
929 return isl_pw_aff_le_set(L, R);
930 case ICmpInst::ICMP_SGT:
931 return isl_pw_aff_gt_set(L, R);
932 case ICmpInst::ICMP_SGE:
933 return isl_pw_aff_ge_set(L, R);
934 case ICmpInst::ICMP_ULT:
935 return isl_pw_aff_lt_set(L, R);
936 case ICmpInst::ICMP_UGT:
937 return isl_pw_aff_gt_set(L, R);
938 case ICmpInst::ICMP_ULE:
939 return isl_pw_aff_le_set(L, R);
940 case ICmpInst::ICMP_UGE:
941 return isl_pw_aff_ge_set(L, R);
942 default:
943 llvm_unreachable("Non integer predicate not supported");
944 }
945}
946
Johannes Doerfert9a132f32015-09-28 09:33:22 +0000947/// @brief Create the conditions under which @p L @p Pred @p R is true.
948///
949/// Helper function that will make sure the dimensions of the result have the
950/// same isl_id's as the @p Domain.
951static __isl_give isl_set *buildConditionSet(ICmpInst::Predicate Pred,
952 __isl_take isl_pw_aff *L,
953 __isl_take isl_pw_aff *R,
954 __isl_keep isl_set *Domain) {
955 isl_set *ConsequenceCondSet = buildConditionSet(Pred, L, R);
956 return setDimensionIds(Domain, ConsequenceCondSet);
957}
958
959/// @brief Build the conditions sets for the switch @p SI in the @p Domain.
Johannes Doerfert96425c22015-08-30 21:13:53 +0000960///
961/// This will fill @p ConditionSets with the conditions under which control
Johannes Doerfert9a132f32015-09-28 09:33:22 +0000962/// will be moved from @p SI to its successors. Hence, @p ConditionSets will
963/// have as many elements as @p SI has successors.
Johannes Doerfert96425c22015-08-30 21:13:53 +0000964static void
Johannes Doerfert9a132f32015-09-28 09:33:22 +0000965buildConditionSets(Scop &S, SwitchInst *SI, Loop *L, __isl_keep isl_set *Domain,
Johannes Doerfert96425c22015-08-30 21:13:53 +0000966 SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
967
Johannes Doerfert9a132f32015-09-28 09:33:22 +0000968 Value *Condition = getConditionFromTerminator(SI);
969 assert(Condition && "No condition for switch");
970
971 ScalarEvolution &SE = *S.getSE();
972 BasicBlock *BB = SI->getParent();
973 isl_pw_aff *LHS, *RHS;
974 LHS = S.getPwAff(SE.getSCEVAtScope(Condition, L), BB);
975
976 unsigned NumSuccessors = SI->getNumSuccessors();
977 ConditionSets.resize(NumSuccessors);
978 for (auto &Case : SI->cases()) {
979 unsigned Idx = Case.getSuccessorIndex();
980 ConstantInt *CaseValue = Case.getCaseValue();
981
982 RHS = S.getPwAff(SE.getSCEV(CaseValue), BB);
983 isl_set *CaseConditionSet =
984 buildConditionSet(ICmpInst::ICMP_EQ, isl_pw_aff_copy(LHS), RHS, Domain);
985 ConditionSets[Idx] = isl_set_coalesce(
986 isl_set_intersect(CaseConditionSet, isl_set_copy(Domain)));
987 }
988
989 assert(ConditionSets[0] == nullptr && "Default condition set was set");
990 isl_set *ConditionSetUnion = isl_set_copy(ConditionSets[1]);
991 for (unsigned u = 2; u < NumSuccessors; u++)
992 ConditionSetUnion =
993 isl_set_union(ConditionSetUnion, isl_set_copy(ConditionSets[u]));
994 ConditionSets[0] = setDimensionIds(
995 Domain, isl_set_subtract(isl_set_copy(Domain), ConditionSetUnion));
996
997 S.markAsOptimized();
998 isl_pw_aff_free(LHS);
999}
1000
1001/// @brief Build the conditions sets for the terminator @p TI in the @p Domain.
1002///
1003/// This will fill @p ConditionSets with the conditions under which control
1004/// will be moved from @p TI to its successors. Hence, @p ConditionSets will
1005/// have as many elements as @p TI has successors.
1006static void
1007buildConditionSets(Scop &S, TerminatorInst *TI, Loop *L,
1008 __isl_keep isl_set *Domain,
1009 SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
1010
1011 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
1012 return buildConditionSets(S, SI, L, Domain, ConditionSets);
1013
1014 assert(isa<BranchInst>(TI) && "Terminator was neither branch nor switch.");
1015
1016 if (TI->getNumSuccessors() == 1) {
Johannes Doerfert96425c22015-08-30 21:13:53 +00001017 ConditionSets.push_back(isl_set_copy(Domain));
1018 return;
1019 }
1020
Johannes Doerfert9a132f32015-09-28 09:33:22 +00001021 Value *Condition = getConditionFromTerminator(TI);
1022 assert(Condition && "No condition for Terminator");
Johannes Doerfert96425c22015-08-30 21:13:53 +00001023
1024 isl_set *ConsequenceCondSet = nullptr;
1025 if (auto *CCond = dyn_cast<ConstantInt>(Condition)) {
1026 if (CCond->isZero())
1027 ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain));
1028 else
1029 ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain));
1030 } else {
1031 auto *ICond = dyn_cast<ICmpInst>(Condition);
1032 assert(ICond &&
1033 "Condition of exiting branch was neither constant nor ICmp!");
1034
1035 ScalarEvolution &SE = *S.getSE();
Johannes Doerfert9a132f32015-09-28 09:33:22 +00001036 BasicBlock *BB = TI->getParent();
Johannes Doerfert96425c22015-08-30 21:13:53 +00001037 isl_pw_aff *LHS, *RHS;
Johannes Doerfertcef616f2015-09-15 22:49:04 +00001038 LHS = S.getPwAff(SE.getSCEVAtScope(ICond->getOperand(0), L), BB);
1039 RHS = S.getPwAff(SE.getSCEVAtScope(ICond->getOperand(1), L), BB);
Johannes Doerfert9a132f32015-09-28 09:33:22 +00001040 ConsequenceCondSet =
1041 buildConditionSet(ICond->getPredicate(), LHS, RHS, Domain);
Johannes Doerfert96425c22015-08-30 21:13:53 +00001042 }
1043
1044 assert(ConsequenceCondSet);
1045 isl_set *AlternativeCondSet =
1046 isl_set_complement(isl_set_copy(ConsequenceCondSet));
1047
1048 ConditionSets.push_back(isl_set_coalesce(
1049 isl_set_intersect(ConsequenceCondSet, isl_set_copy(Domain))));
1050 ConditionSets.push_back(isl_set_coalesce(
1051 isl_set_intersect(AlternativeCondSet, isl_set_copy(Domain))));
1052}
1053
Johannes Doerfert32ae76e2015-09-10 13:12:02 +00001054void ScopStmt::buildDomain() {
Tobias Grosser084d8f72012-05-29 09:29:44 +00001055 isl_id *Id;
Tobias Grossere19661e2011-10-07 08:46:57 +00001056
Tobias Grosser084d8f72012-05-29 09:29:44 +00001057 Id = isl_id_alloc(getIslCtx(), getBaseName(), this);
1058
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +00001059 Domain = getParent()->getDomainConditions(this);
Tobias Grosser084d8f72012-05-29 09:29:44 +00001060 Domain = isl_set_set_tuple_id(Domain, Id);
Tobias Grosser75805372011-04-29 06:27:02 +00001061}
1062
Tobias Grosser7b50bee2014-11-25 10:51:12 +00001063void ScopStmt::deriveAssumptionsFromGEP(GetElementPtrInst *GEP) {
Tobias Grosser7b50bee2014-11-25 10:51:12 +00001064 isl_ctx *Ctx = Parent.getIslCtx();
1065 isl_local_space *LSpace = isl_local_space_from_space(getDomainSpace());
1066 Type *Ty = GEP->getPointerOperandType();
1067 ScalarEvolution &SE = *Parent.getSE();
Johannes Doerfert09e36972015-10-07 20:17:36 +00001068 ScopDetection &SD = Parent.getSD();
1069
1070 // The set of loads that are required to be invariant.
1071 auto &ScopRIL = *SD.getRequiredInvariantLoads(&Parent.getRegion());
Tobias Grosser7b50bee2014-11-25 10:51:12 +00001072
Tobias Grosserfaf8f6f2015-09-17 15:47:52 +00001073 std::vector<const SCEV *> Subscripts;
1074 std::vector<int> Sizes;
1075
Tobias Grosser5fd8c092015-09-17 17:28:15 +00001076 std::tie(Subscripts, Sizes) = getIndexExpressionsFromGEP(GEP, SE);
Tobias Grosserfaf8f6f2015-09-17 15:47:52 +00001077
Tobias Grosser7b50bee2014-11-25 10:51:12 +00001078 if (auto *PtrTy = dyn_cast<PointerType>(Ty)) {
Tobias Grosser7b50bee2014-11-25 10:51:12 +00001079 Ty = PtrTy->getElementType();
1080 }
1081
Tobias Grosserfaf8f6f2015-09-17 15:47:52 +00001082 int IndexOffset = Subscripts.size() - Sizes.size();
Tobias Grosser7b50bee2014-11-25 10:51:12 +00001083
Tobias Grosserfaf8f6f2015-09-17 15:47:52 +00001084 assert(IndexOffset <= 1 && "Unexpected large index offset");
Tobias Grosser7b50bee2014-11-25 10:51:12 +00001085
Tobias Grosserfaf8f6f2015-09-17 15:47:52 +00001086 for (size_t i = 0; i < Sizes.size(); i++) {
1087 auto Expr = Subscripts[i + IndexOffset];
1088 auto Size = Sizes[i];
Tobias Grosser7b50bee2014-11-25 10:51:12 +00001089
Johannes Doerfert09e36972015-10-07 20:17:36 +00001090 InvariantLoadsSetTy AccessILS;
1091 if (!isAffineExpr(&Parent.getRegion(), Expr, SE, nullptr, &AccessILS))
1092 continue;
1093
1094 bool NonAffine = false;
1095 for (LoadInst *LInst : AccessILS)
1096 if (!ScopRIL.count(LInst))
1097 NonAffine = true;
1098
1099 if (NonAffine)
Tobias Grosserfaf8f6f2015-09-17 15:47:52 +00001100 continue;
Tobias Grosser7b50bee2014-11-25 10:51:12 +00001101
Tobias Grosserfaf8f6f2015-09-17 15:47:52 +00001102 isl_pw_aff *AccessOffset = getPwAff(Expr);
1103 AccessOffset =
1104 isl_pw_aff_set_tuple_id(AccessOffset, isl_dim_in, getDomainId());
Tobias Grosser7b50bee2014-11-25 10:51:12 +00001105
Tobias Grosserfaf8f6f2015-09-17 15:47:52 +00001106 isl_pw_aff *DimSize = isl_pw_aff_from_aff(isl_aff_val_on_domain(
1107 isl_local_space_copy(LSpace), isl_val_int_from_si(Ctx, Size)));
Tobias Grosser7b50bee2014-11-25 10:51:12 +00001108
Tobias Grosserfaf8f6f2015-09-17 15:47:52 +00001109 isl_set *OutOfBound = isl_pw_aff_ge_set(AccessOffset, DimSize);
1110 OutOfBound = isl_set_intersect(getDomain(), OutOfBound);
1111 OutOfBound = isl_set_params(OutOfBound);
1112 isl_set *InBound = isl_set_complement(OutOfBound);
1113 isl_set *Executed = isl_set_params(getDomain());
Tobias Grosser7b50bee2014-11-25 10:51:12 +00001114
Tobias Grosserfaf8f6f2015-09-17 15:47:52 +00001115 // A => B == !A or B
1116 isl_set *InBoundIfExecuted =
1117 isl_set_union(isl_set_complement(Executed), InBound);
Tobias Grosser7b50bee2014-11-25 10:51:12 +00001118
Tobias Grosserfaf8f6f2015-09-17 15:47:52 +00001119 Parent.addAssumption(InBoundIfExecuted);
Tobias Grosser7b50bee2014-11-25 10:51:12 +00001120 }
1121
1122 isl_local_space_free(LSpace);
1123}
1124
Johannes Doerfertff9d1982015-02-24 12:00:50 +00001125void ScopStmt::deriveAssumptions(BasicBlock *Block) {
1126 for (Instruction &Inst : *Block)
Tobias Grosser7b50bee2014-11-25 10:51:12 +00001127 if (auto *GEP = dyn_cast<GetElementPtrInst>(&Inst))
1128 deriveAssumptionsFromGEP(GEP);
1129}
1130
Johannes Doerfertb68cffb2015-09-10 15:27:46 +00001131void ScopStmt::collectSurroundingLoops() {
1132 for (unsigned u = 0, e = isl_set_n_dim(Domain); u < e; u++) {
1133 isl_id *DimId = isl_set_get_dim_id(Domain, isl_dim_set, u);
1134 NestLoops.push_back(static_cast<Loop *>(isl_id_get_user(DimId)));
1135 isl_id_free(DimId);
1136 }
1137}
1138
Michael Kruse9d080092015-09-11 21:41:48 +00001139ScopStmt::ScopStmt(Scop &parent, Region &R)
Michael Krusecac948e2015-10-02 13:53:07 +00001140 : Parent(parent), Domain(nullptr), BB(nullptr), R(&R), Build(nullptr) {
Johannes Doerfertff9d1982015-02-24 12:00:50 +00001141
Tobias Grosser16c44032015-07-09 07:31:45 +00001142 BaseName = getIslCompatibleName("Stmt_", R.getNameStr(), "");
Johannes Doerfertff9d1982015-02-24 12:00:50 +00001143}
1144
Michael Kruse9d080092015-09-11 21:41:48 +00001145ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb)
Michael Krusecac948e2015-10-02 13:53:07 +00001146 : Parent(parent), Domain(nullptr), BB(&bb), R(nullptr), Build(nullptr) {
Tobias Grosser75805372011-04-29 06:27:02 +00001147
Johannes Doerfert79fc23f2014-07-24 23:48:02 +00001148 BaseName = getIslCompatibleName("Stmt_", &bb, "");
Michael Krusecac948e2015-10-02 13:53:07 +00001149}
1150
1151void ScopStmt::init() {
1152 assert(!Domain && "init must be called only once");
Tobias Grosser75805372011-04-29 06:27:02 +00001153
Johannes Doerfert32ae76e2015-09-10 13:12:02 +00001154 buildDomain();
Johannes Doerfertb68cffb2015-09-10 15:27:46 +00001155 collectSurroundingLoops();
Michael Krusecac948e2015-10-02 13:53:07 +00001156 buildAccessRelations();
1157
1158 if (BB) {
1159 deriveAssumptions(BB);
1160 } else {
1161 for (BasicBlock *Block : R->blocks()) {
1162 deriveAssumptions(Block);
1163 }
1164 }
1165
Tobias Grosserd83b8a82015-08-20 19:08:11 +00001166 if (DetectReductions)
1167 checkForReductions();
Johannes Doerfert0ee1f212014-06-17 17:31:36 +00001168}
1169
Johannes Doerferte58a0122014-06-27 20:31:28 +00001170/// @brief Collect loads which might form a reduction chain with @p StoreMA
1171///
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00001172/// Check if the stored value for @p StoreMA is a binary operator with one or
1173/// two loads as operands. If the binary operand is commutative & associative,
Johannes Doerferte58a0122014-06-27 20:31:28 +00001174/// used only once (by @p StoreMA) and its load operands are also used only
1175/// once, we have found a possible reduction chain. It starts at an operand
1176/// load and includes the binary operator and @p StoreMA.
1177///
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00001178/// Note: We allow only one use to ensure the load and binary operator cannot
Johannes Doerferte58a0122014-06-27 20:31:28 +00001179/// escape this block or into any other store except @p StoreMA.
1180void ScopStmt::collectCandiateReductionLoads(
1181 MemoryAccess *StoreMA, SmallVectorImpl<MemoryAccess *> &Loads) {
1182 auto *Store = dyn_cast<StoreInst>(StoreMA->getAccessInstruction());
1183 if (!Store)
Johannes Doerfert0ee1f212014-06-17 17:31:36 +00001184 return;
1185
1186 // Skip if there is not one binary operator between the load and the store
1187 auto *BinOp = dyn_cast<BinaryOperator>(Store->getValueOperand());
Johannes Doerferte58a0122014-06-27 20:31:28 +00001188 if (!BinOp)
1189 return;
1190
1191 // Skip if the binary operators has multiple uses
1192 if (BinOp->getNumUses() != 1)
Johannes Doerfert0ee1f212014-06-17 17:31:36 +00001193 return;
1194
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00001195 // Skip if the opcode of the binary operator is not commutative/associative
Johannes Doerfert0ee1f212014-06-17 17:31:36 +00001196 if (!BinOp->isCommutative() || !BinOp->isAssociative())
1197 return;
1198
Johannes Doerfert9890a052014-07-01 00:32:29 +00001199 // Skip if the binary operator is outside the current SCoP
1200 if (BinOp->getParent() != Store->getParent())
1201 return;
1202
Johannes Doerfert0ee1f212014-06-17 17:31:36 +00001203 // Skip if it is a multiplicative reduction and we disabled them
1204 if (DisableMultiplicativeReductions &&
1205 (BinOp->getOpcode() == Instruction::Mul ||
1206 BinOp->getOpcode() == Instruction::FMul))
1207 return;
1208
Johannes Doerferte58a0122014-06-27 20:31:28 +00001209 // Check the binary operator operands for a candidate load
1210 auto *PossibleLoad0 = dyn_cast<LoadInst>(BinOp->getOperand(0));
1211 auto *PossibleLoad1 = dyn_cast<LoadInst>(BinOp->getOperand(1));
1212 if (!PossibleLoad0 && !PossibleLoad1)
1213 return;
1214
1215 // A load is only a candidate if it cannot escape (thus has only this use)
1216 if (PossibleLoad0 && PossibleLoad0->getNumUses() == 1)
Johannes Doerfert9890a052014-07-01 00:32:29 +00001217 if (PossibleLoad0->getParent() == Store->getParent())
1218 Loads.push_back(lookupAccessFor(PossibleLoad0));
Johannes Doerferte58a0122014-06-27 20:31:28 +00001219 if (PossibleLoad1 && PossibleLoad1->getNumUses() == 1)
Johannes Doerfert9890a052014-07-01 00:32:29 +00001220 if (PossibleLoad1->getParent() == Store->getParent())
1221 Loads.push_back(lookupAccessFor(PossibleLoad1));
Johannes Doerferte58a0122014-06-27 20:31:28 +00001222}
1223
1224/// @brief Check for reductions in this ScopStmt
1225///
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00001226/// Iterate over all store memory accesses and check for valid binary reduction
1227/// like chains. For all candidates we check if they have the same base address
1228/// and there are no other accesses which overlap with them. The base address
1229/// check rules out impossible reductions candidates early. The overlap check,
1230/// together with the "only one user" check in collectCandiateReductionLoads,
Johannes Doerferte58a0122014-06-27 20:31:28 +00001231/// guarantees that none of the intermediate results will escape during
1232/// execution of the loop nest. We basically check here that no other memory
1233/// access can access the same memory as the potential reduction.
1234void ScopStmt::checkForReductions() {
1235 SmallVector<MemoryAccess *, 2> Loads;
1236 SmallVector<std::pair<MemoryAccess *, MemoryAccess *>, 4> Candidates;
1237
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00001238 // First collect candidate load-store reduction chains by iterating over all
Johannes Doerferte58a0122014-06-27 20:31:28 +00001239 // stores and collecting possible reduction loads.
1240 for (MemoryAccess *StoreMA : MemAccs) {
1241 if (StoreMA->isRead())
1242 continue;
1243
1244 Loads.clear();
1245 collectCandiateReductionLoads(StoreMA, Loads);
1246 for (MemoryAccess *LoadMA : Loads)
1247 Candidates.push_back(std::make_pair(LoadMA, StoreMA));
1248 }
1249
1250 // Then check each possible candidate pair.
1251 for (const auto &CandidatePair : Candidates) {
1252 bool Valid = true;
1253 isl_map *LoadAccs = CandidatePair.first->getAccessRelation();
1254 isl_map *StoreAccs = CandidatePair.second->getAccessRelation();
1255
1256 // Skip those with obviously unequal base addresses.
1257 if (!isl_map_has_equal_space(LoadAccs, StoreAccs)) {
1258 isl_map_free(LoadAccs);
1259 isl_map_free(StoreAccs);
1260 continue;
1261 }
1262
1263 // And check if the remaining for overlap with other memory accesses.
1264 isl_map *AllAccsRel = isl_map_union(LoadAccs, StoreAccs);
1265 AllAccsRel = isl_map_intersect_domain(AllAccsRel, getDomain());
1266 isl_set *AllAccs = isl_map_range(AllAccsRel);
1267
1268 for (MemoryAccess *MA : MemAccs) {
1269 if (MA == CandidatePair.first || MA == CandidatePair.second)
1270 continue;
1271
1272 isl_map *AccRel =
1273 isl_map_intersect_domain(MA->getAccessRelation(), getDomain());
1274 isl_set *Accs = isl_map_range(AccRel);
1275
1276 if (isl_set_has_equal_space(AllAccs, Accs) || isl_set_free(Accs)) {
1277 isl_set *OverlapAccs = isl_set_intersect(Accs, isl_set_copy(AllAccs));
1278 Valid = Valid && isl_set_is_empty(OverlapAccs);
1279 isl_set_free(OverlapAccs);
1280 }
1281 }
1282
1283 isl_set_free(AllAccs);
1284 if (!Valid)
1285 continue;
1286
Johannes Doerfertf6183392014-07-01 20:52:51 +00001287 const LoadInst *Load =
1288 dyn_cast<const LoadInst>(CandidatePair.first->getAccessInstruction());
1289 MemoryAccess::ReductionType RT =
1290 getReductionType(dyn_cast<BinaryOperator>(Load->user_back()), Load);
1291
Johannes Doerferte58a0122014-06-27 20:31:28 +00001292 // If no overlapping access was found we mark the load and store as
1293 // reduction like.
Johannes Doerfertf6183392014-07-01 20:52:51 +00001294 CandidatePair.first->markAsReductionLike(RT);
1295 CandidatePair.second->markAsReductionLike(RT);
Johannes Doerferte58a0122014-06-27 20:31:28 +00001296 }
Tobias Grosser75805372011-04-29 06:27:02 +00001297}
1298
Tobias Grosser74394f02013-01-14 22:40:23 +00001299std::string ScopStmt::getDomainStr() const { return stringFromIslObj(Domain); }
Tobias Grosser75805372011-04-29 06:27:02 +00001300
Tobias Grosser54839312015-04-21 11:37:25 +00001301std::string ScopStmt::getScheduleStr() const {
Tobias Grosser808cd692015-07-14 09:33:13 +00001302 auto *S = getSchedule();
1303 auto Str = stringFromIslObj(S);
1304 isl_map_free(S);
1305 return Str;
Tobias Grosser75805372011-04-29 06:27:02 +00001306}
1307
Tobias Grosser74394f02013-01-14 22:40:23 +00001308unsigned ScopStmt::getNumParams() const { return Parent.getNumParams(); }
Tobias Grosser75805372011-04-29 06:27:02 +00001309
Tobias Grosserf567e1a2015-02-19 22:16:12 +00001310unsigned ScopStmt::getNumIterators() const { return NestLoops.size(); }
Tobias Grosser75805372011-04-29 06:27:02 +00001311
Tobias Grosser75805372011-04-29 06:27:02 +00001312const char *ScopStmt::getBaseName() const { return BaseName.c_str(); }
1313
Hongbin Zheng27f3afb2011-04-30 03:26:51 +00001314const Loop *ScopStmt::getLoopForDimension(unsigned Dimension) const {
Sebastian Pop860e0212013-02-15 21:26:44 +00001315 return NestLoops[Dimension];
Tobias Grosser75805372011-04-29 06:27:02 +00001316}
1317
Tobias Grosser74394f02013-01-14 22:40:23 +00001318isl_ctx *ScopStmt::getIslCtx() const { return Parent.getIslCtx(); }
Tobias Grosser75805372011-04-29 06:27:02 +00001319
Tobias Grosser4f663aa2015-03-30 11:52:59 +00001320__isl_give isl_set *ScopStmt::getDomain() const { return isl_set_copy(Domain); }
Tobias Grosserd5a7bfc2011-05-06 19:52:19 +00001321
Tobias Grosser6e6c7e02015-03-30 12:22:39 +00001322__isl_give isl_space *ScopStmt::getDomainSpace() const {
Tobias Grosser78d8a3d2012-01-17 20:34:23 +00001323 return isl_set_get_space(Domain);
1324}
1325
Tobias Grosser4f663aa2015-03-30 11:52:59 +00001326__isl_give isl_id *ScopStmt::getDomainId() const {
1327 return isl_set_get_tuple_id(Domain);
1328}
Tobias Grossercd95b772012-08-30 11:49:38 +00001329
Tobias Grosser75805372011-04-29 06:27:02 +00001330ScopStmt::~ScopStmt() {
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001331 DeleteContainerSeconds(InstructionToAccess);
Tobias Grosser75805372011-04-29 06:27:02 +00001332 isl_set_free(Domain);
Tobias Grosser75805372011-04-29 06:27:02 +00001333}
1334
1335void ScopStmt::print(raw_ostream &OS) const {
1336 OS << "\t" << getBaseName() << "\n";
Tobias Grosser75805372011-04-29 06:27:02 +00001337 OS.indent(12) << "Domain :=\n";
1338
1339 if (Domain) {
1340 OS.indent(16) << getDomainStr() << ";\n";
1341 } else
1342 OS.indent(16) << "n/a\n";
1343
Tobias Grosser54839312015-04-21 11:37:25 +00001344 OS.indent(12) << "Schedule :=\n";
Tobias Grosser75805372011-04-29 06:27:02 +00001345
1346 if (Domain) {
Tobias Grosser54839312015-04-21 11:37:25 +00001347 OS.indent(16) << getScheduleStr() << ";\n";
Tobias Grosser75805372011-04-29 06:27:02 +00001348 } else
1349 OS.indent(16) << "n/a\n";
1350
Tobias Grosser083d3d32014-06-28 08:59:45 +00001351 for (MemoryAccess *Access : MemAccs)
1352 Access->print(OS);
Tobias Grosser75805372011-04-29 06:27:02 +00001353}
1354
1355void ScopStmt::dump() const { print(dbgs()); }
1356
Johannes Doerfertc1db67e2015-09-29 23:47:21 +00001357void ScopStmt::hoistMemoryAccesses(MemoryAccessList &InvMAs,
Johannes Doerfert697fdf82015-10-09 17:12:26 +00001358 InvariantAccessesTy &InvariantEquivClasses) {
Johannes Doerfertc1db67e2015-09-29 23:47:21 +00001359
1360 // Remove all memory accesses in @p InvMAs from this statement together
1361 // with all scalar accesses that were caused by them. The tricky iteration
1362 // order uses is needed because the MemAccs is a vector and the order in
1363 // which the accesses of each memory access list (MAL) are stored in this
1364 // vector is reversed.
1365 for (MemoryAccess *MA : InvMAs) {
1366 auto &MAL = *lookupAccessesFor(MA->getAccessInstruction());
1367 MAL.reverse();
1368
1369 auto MALIt = MAL.begin();
1370 auto MALEnd = MAL.end();
1371 auto MemAccsIt = MemAccs.begin();
1372 while (MALIt != MALEnd) {
1373 while (*MemAccsIt != *MALIt)
1374 MemAccsIt++;
1375
1376 MALIt++;
1377 MemAccs.erase(MemAccsIt);
1378 }
1379
1380 InstructionToAccess.erase(MA->getAccessInstruction());
1381 delete &MAL;
1382 }
1383
1384 // Get the context under which this statement, hence the memory accesses, are
1385 // executed.
1386 isl_set *DomainCtx = isl_set_params(getDomain());
1387 DomainCtx = isl_set_remove_redundancies(DomainCtx);
1388 DomainCtx = isl_set_detect_equalities(DomainCtx);
1389 DomainCtx = isl_set_coalesce(DomainCtx);
1390
Johannes Doerfertf7e29672015-10-08 11:05:57 +00001391 Scop &S = *getParent();
1392 ScalarEvolution &SE = *S.getSE();
1393
1394 // Project out all parameters that relate to loads in this statement that
1395 // we will hoist. Otherwise we would have cyclic dependences on the
1396 // constraints under which the hoisted loads are executed and we could not
1397 // determine an order in which to preload them. This happens because not only
1398 // lower bounds are part of the domain but also upper bounds.
1399 for (MemoryAccess *MA : InvMAs) {
1400 Instruction *AccInst = MA->getAccessInstruction();
1401 if (SE.isSCEVable(AccInst->getType())) {
1402 isl_id *ParamId = S.getIdForParam(SE.getSCEV(AccInst));
1403 if (ParamId) {
1404 int Dim = isl_set_find_dim_by_id(DomainCtx, isl_dim_param, ParamId);
1405 DomainCtx = isl_set_eliminate(DomainCtx, isl_dim_param, Dim, 1);
1406 }
1407 isl_id_free(ParamId);
1408 }
1409 }
1410
Johannes Doerfert697fdf82015-10-09 17:12:26 +00001411 for (MemoryAccess *MA : InvMAs) {
1412
1413 // Check for another invariant access that accesses the same location as
1414 // MA and if found consolidate them. Otherwise create a new equivalence
1415 // class at the end of InvariantEquivClasses.
1416 LoadInst *LInst = cast<LoadInst>(MA->getAccessInstruction());
1417 const SCEV *PointerSCEV = SE.getSCEV(LInst->getPointerOperand());
1418 bool Consolidated = false;
1419
1420 for (auto &IAClass : InvariantEquivClasses) {
1421 const SCEV *ClassPointerSCEV = IAClass.first;
1422 if (PointerSCEV != ClassPointerSCEV)
1423 continue;
1424
1425 Consolidated = true;
1426
1427 // We created empty equivalence classes for required invariant loads
1428 // in the beginning and might encounter one of them here. If so, this
1429 // MA will be the first in that equivalence class.
1430 auto &ClassList = IAClass.second;
1431 if (ClassList.empty()) {
1432 ClassList.push_front(std::make_pair(MA, isl_set_copy(DomainCtx)));
1433 break;
1434 }
1435
1436 // If the equivalence class for MA is not empty we unify the execution
1437 // context and add MA to the list of accesses that are in this class.
1438 isl_set *IAClassDomainCtx = IAClass.second.front().second;
1439 IAClassDomainCtx =
1440 isl_set_union(IAClassDomainCtx, isl_set_copy(DomainCtx));
1441 ClassList.push_front(std::make_pair(MA, IAClassDomainCtx));
1442 break;
1443 }
1444
1445 if (Consolidated)
1446 continue;
1447
1448 // If we did not consolidate MA, thus did not find an equivalence class
1449 // that for it, we create a new one.
1450 InvariantAccessTy IA = std::make_pair(MA, isl_set_copy(DomainCtx));
1451 InvariantEquivClasses.emplace_back(InvariantEquivClassTy(
1452 std::make_pair(PointerSCEV, InvariantAccessListTy({IA}))));
1453 }
Johannes Doerfertc1db67e2015-09-29 23:47:21 +00001454
1455 isl_set_free(DomainCtx);
1456}
1457
Tobias Grosser75805372011-04-29 06:27:02 +00001458//===----------------------------------------------------------------------===//
1459/// Scop class implement
Tobias Grosser60b54f12011-11-08 15:41:28 +00001460
Tobias Grosser7ffe4e82011-11-17 12:56:10 +00001461void Scop::setContext(__isl_take isl_set *NewContext) {
Tobias Grosserff9b54d2011-11-15 11:38:44 +00001462 NewContext = isl_set_align_params(NewContext, isl_set_get_space(Context));
1463 isl_set_free(Context);
1464 Context = NewContext;
1465}
1466
Johannes Doerfert697fdf82015-10-09 17:12:26 +00001467const SCEV *Scop::getRepresentingInvariantLoadSCEV(const SCEV *S) const {
1468 const SCEVUnknown *SU = dyn_cast_or_null<SCEVUnknown>(S);
1469 if (!SU)
1470 return S;
1471
1472 LoadInst *LInst = dyn_cast<LoadInst>(SU->getValue());
1473 if (!LInst)
1474 return S;
1475
1476 // Try to find an equivalence class for the load, if found return
1477 // the SCEV for the representing element, otherwise return S.
1478 const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand());
1479 for (const InvariantEquivClassTy &IAClass : InvariantEquivClasses) {
1480 const SCEV *ClassPointerSCEV = IAClass.first;
1481 if (ClassPointerSCEV == PointerSCEV)
1482 return ClassPointerSCEV;
1483 }
1484
1485 return S;
1486}
1487
Tobias Grosserabfbe632013-02-05 12:09:06 +00001488void Scop::addParams(std::vector<const SCEV *> NewParameters) {
Tobias Grosser083d3d32014-06-28 08:59:45 +00001489 for (const SCEV *Parameter : NewParameters) {
Johannes Doerfertbe409962015-03-29 20:45:09 +00001490 Parameter = extractConstantFactor(Parameter, *SE).second;
Johannes Doerfert697fdf82015-10-09 17:12:26 +00001491
1492 // Normalize the SCEV to get the representing element for an invariant load.
1493 Parameter = getRepresentingInvariantLoadSCEV(Parameter);
1494
Tobias Grosser60b54f12011-11-08 15:41:28 +00001495 if (ParameterIds.find(Parameter) != ParameterIds.end())
1496 continue;
1497
1498 int dimension = Parameters.size();
1499
1500 Parameters.push_back(Parameter);
1501 ParameterIds[Parameter] = dimension;
1502 }
1503}
1504
Tobias Grosser9a38ab82011-11-08 15:41:03 +00001505__isl_give isl_id *Scop::getIdForParam(const SCEV *Parameter) const {
Johannes Doerfert697fdf82015-10-09 17:12:26 +00001506 // Normalize the SCEV to get the representing element for an invariant load.
1507 Parameter = getRepresentingInvariantLoadSCEV(Parameter);
1508
Tobias Grosser9a38ab82011-11-08 15:41:03 +00001509 ParamIdType::const_iterator IdIter = ParameterIds.find(Parameter);
Tobias Grosser76c2e322011-11-07 12:58:59 +00001510
Tobias Grosser9a38ab82011-11-08 15:41:03 +00001511 if (IdIter == ParameterIds.end())
Tobias Grosser5a56cbf2014-04-16 07:33:47 +00001512 return nullptr;
Tobias Grosser76c2e322011-11-07 12:58:59 +00001513
Tobias Grosser8f99c162011-11-15 11:38:55 +00001514 std::string ParameterName;
1515
1516 if (const SCEVUnknown *ValueParameter = dyn_cast<SCEVUnknown>(Parameter)) {
1517 Value *Val = ValueParameter->getValue();
Tobias Grosser29ee0b12011-11-17 14:52:36 +00001518 ParameterName = Val->getName();
Tobias Grosser8f99c162011-11-15 11:38:55 +00001519 }
1520
1521 if (ParameterName == "" || ParameterName.substr(0, 2) == "p_")
Hongbin Zheng86a37742012-04-25 08:01:38 +00001522 ParameterName = "p_" + utostr_32(IdIter->second);
Tobias Grosser8f99c162011-11-15 11:38:55 +00001523
Tobias Grosser20532b82014-04-11 17:56:49 +00001524 return isl_id_alloc(getIslCtx(), ParameterName.c_str(),
1525 const_cast<void *>((const void *)Parameter));
Tobias Grosser76c2e322011-11-07 12:58:59 +00001526}
Tobias Grosser75805372011-04-29 06:27:02 +00001527
Johannes Doerfert5d5b3062015-08-20 18:06:30 +00001528isl_set *Scop::addNonEmptyDomainConstraints(isl_set *C) const {
1529 isl_set *DomainContext = isl_union_set_params(getDomains());
1530 return isl_set_intersect_params(C, DomainContext);
1531}
1532
Johannes Doerfert883f8c12015-09-15 22:52:53 +00001533void Scop::buildBoundaryContext() {
1534 BoundaryContext = Affinator.getWrappingContext();
1535 BoundaryContext = isl_set_complement(BoundaryContext);
1536 BoundaryContext = isl_set_gist_params(BoundaryContext, getContext());
1537}
1538
Tobias Grosser8a9c2352015-08-16 10:19:29 +00001539void Scop::addUserContext() {
1540 if (UserContextStr.empty())
1541 return;
1542
1543 isl_set *UserContext = isl_set_read_from_str(IslCtx, UserContextStr.c_str());
1544 isl_space *Space = getParamSpace();
1545 if (isl_space_dim(Space, isl_dim_param) !=
1546 isl_set_dim(UserContext, isl_dim_param)) {
1547 auto SpaceStr = isl_space_to_str(Space);
1548 errs() << "Error: the context provided in -polly-context has not the same "
1549 << "number of dimensions than the computed context. Due to this "
1550 << "mismatch, the -polly-context option is ignored. Please provide "
1551 << "the context in the parameter space: " << SpaceStr << ".\n";
1552 free(SpaceStr);
1553 isl_set_free(UserContext);
1554 isl_space_free(Space);
1555 return;
1556 }
1557
1558 for (unsigned i = 0; i < isl_space_dim(Space, isl_dim_param); i++) {
1559 auto NameContext = isl_set_get_dim_name(Context, isl_dim_param, i);
1560 auto NameUserContext = isl_set_get_dim_name(UserContext, isl_dim_param, i);
1561
1562 if (strcmp(NameContext, NameUserContext) != 0) {
1563 auto SpaceStr = isl_space_to_str(Space);
1564 errs() << "Error: the name of dimension " << i
1565 << " provided in -polly-context "
1566 << "is '" << NameUserContext << "', but the name in the computed "
1567 << "context is '" << NameContext
1568 << "'. Due to this name mismatch, "
1569 << "the -polly-context option is ignored. Please provide "
1570 << "the context in the parameter space: " << SpaceStr << ".\n";
1571 free(SpaceStr);
1572 isl_set_free(UserContext);
1573 isl_space_free(Space);
1574 return;
1575 }
1576
1577 UserContext =
1578 isl_set_set_dim_id(UserContext, isl_dim_param, i,
1579 isl_space_get_dim_id(Space, isl_dim_param, i));
1580 }
1581
1582 Context = isl_set_intersect(Context, UserContext);
1583 isl_space_free(Space);
1584}
1585
Johannes Doerfert697fdf82015-10-09 17:12:26 +00001586void Scop::buildInvariantEquivalenceClasses() {
1587 const InvariantLoadsSetTy &RIL = *SD.getRequiredInvariantLoads(&getRegion());
1588 SmallPtrSet<const SCEV *, 4> ClassPointerSet;
1589 for (LoadInst *LInst : RIL) {
1590 const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand());
1591
1592 // Skip the load if we already have a equivalence class for the pointer.
1593 if (!ClassPointerSet.insert(PointerSCEV).second)
1594 continue;
1595
1596 InvariantEquivClasses.emplace_back(InvariantEquivClassTy(
1597 std::make_pair(PointerSCEV, InvariantAccessListTy())));
1598 }
1599}
1600
Tobias Grosser6be480c2011-11-08 15:41:13 +00001601void Scop::buildContext() {
1602 isl_space *Space = isl_space_params_alloc(IslCtx, 0);
Tobias Grossere86109f2013-10-29 21:05:49 +00001603 Context = isl_set_universe(isl_space_copy(Space));
1604 AssumedContext = isl_set_universe(Space);
Tobias Grosser0e27e242011-10-06 00:03:48 +00001605}
1606
Tobias Grosser18daaca2012-05-22 10:47:27 +00001607void Scop::addParameterBounds() {
Johannes Doerfert4f8ac3d2015-02-23 16:15:51 +00001608 for (const auto &ParamID : ParameterIds) {
Johannes Doerfert4f8ac3d2015-02-23 16:15:51 +00001609 int dim = ParamID.second;
Tobias Grosser18daaca2012-05-22 10:47:27 +00001610
Johannes Doerfert4f8ac3d2015-02-23 16:15:51 +00001611 ConstantRange SRange = SE->getSignedRange(ParamID.first);
Tobias Grosser18daaca2012-05-22 10:47:27 +00001612
Johannes Doerferte7044942015-02-24 11:58:30 +00001613 Context = addRangeBoundsToSet(Context, SRange, dim, isl_dim_param);
Tobias Grosser18daaca2012-05-22 10:47:27 +00001614 }
1615}
1616
Tobias Grosser8cae72f2011-11-08 15:41:08 +00001617void Scop::realignParams() {
Tobias Grosser6be480c2011-11-08 15:41:13 +00001618 // Add all parameters into a common model.
Tobias Grosser60b54f12011-11-08 15:41:28 +00001619 isl_space *Space = isl_space_params_alloc(IslCtx, ParameterIds.size());
Tobias Grosser6be480c2011-11-08 15:41:13 +00001620
Tobias Grosser083d3d32014-06-28 08:59:45 +00001621 for (const auto &ParamID : ParameterIds) {
1622 const SCEV *Parameter = ParamID.first;
Tobias Grosser6be480c2011-11-08 15:41:13 +00001623 isl_id *id = getIdForParam(Parameter);
Tobias Grosser083d3d32014-06-28 08:59:45 +00001624 Space = isl_space_set_dim_id(Space, isl_dim_param, ParamID.second, id);
Tobias Grosser6be480c2011-11-08 15:41:13 +00001625 }
1626
1627 // Align the parameters of all data structures to the model.
1628 Context = isl_set_align_params(Context, Space);
1629
Tobias Grosser7c3bad52015-05-27 05:16:57 +00001630 for (ScopStmt &Stmt : *this)
1631 Stmt.realignParams();
Tobias Grosser8cae72f2011-11-08 15:41:08 +00001632}
1633
Johannes Doerfert883f8c12015-09-15 22:52:53 +00001634static __isl_give isl_set *
1635simplifyAssumptionContext(__isl_take isl_set *AssumptionContext,
1636 const Scop &S) {
1637 isl_set *DomainParameters = isl_union_set_params(S.getDomains());
1638 AssumptionContext = isl_set_gist_params(AssumptionContext, DomainParameters);
1639 AssumptionContext = isl_set_gist_params(AssumptionContext, S.getContext());
1640 return AssumptionContext;
1641}
1642
1643void Scop::simplifyContexts() {
Tobias Grosser5e6813d2014-07-02 17:47:48 +00001644 // The parameter constraints of the iteration domains give us a set of
1645 // constraints that need to hold for all cases where at least a single
1646 // statement iteration is executed in the whole scop. We now simplify the
1647 // assumed context under the assumption that such constraints hold and at
1648 // least a single statement iteration is executed. For cases where no
1649 // statement instances are executed, the assumptions we have taken about
1650 // the executed code do not matter and can be changed.
1651 //
1652 // WARNING: This only holds if the assumptions we have taken do not reduce
1653 // the set of statement instances that are executed. Otherwise we
1654 // may run into a case where the iteration domains suggest that
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00001655 // for a certain set of parameter constraints no code is executed,
Tobias Grosser5e6813d2014-07-02 17:47:48 +00001656 // but in the original program some computation would have been
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00001657 // performed. In such a case, modifying the run-time conditions and
1658 // possibly influencing the run-time check may cause certain scops
Tobias Grosser5e6813d2014-07-02 17:47:48 +00001659 // to not be executed.
1660 //
1661 // Example:
1662 //
1663 // When delinearizing the following code:
1664 //
1665 // for (long i = 0; i < 100; i++)
1666 // for (long j = 0; j < m; j++)
1667 // A[i+p][j] = 1.0;
1668 //
1669 // we assume that the condition m <= 0 or (m >= 1 and p >= 0) holds as
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00001670 // otherwise we would access out of bound data. Now, knowing that code is
Tobias Grosser5e6813d2014-07-02 17:47:48 +00001671 // only executed for the case m >= 0, it is sufficient to assume p >= 0.
Johannes Doerfert883f8c12015-09-15 22:52:53 +00001672 AssumedContext = simplifyAssumptionContext(AssumedContext, *this);
1673 BoundaryContext = simplifyAssumptionContext(BoundaryContext, *this);
Tobias Grosser5e6813d2014-07-02 17:47:48 +00001674}
1675
Johannes Doerfertb164c792014-09-18 11:17:17 +00001676/// @brief Add the minimal/maximal access in @p Set to @p User.
Tobias Grosserb2f39922015-05-28 13:32:11 +00001677static isl_stat buildMinMaxAccess(__isl_take isl_set *Set, void *User) {
Johannes Doerfertb164c792014-09-18 11:17:17 +00001678 Scop::MinMaxVectorTy *MinMaxAccesses = (Scop::MinMaxVectorTy *)User;
1679 isl_pw_multi_aff *MinPMA, *MaxPMA;
1680 isl_pw_aff *LastDimAff;
1681 isl_aff *OneAff;
1682 unsigned Pos;
1683
Johannes Doerfert9143d672014-09-27 11:02:39 +00001684 // Restrict the number of parameters involved in the access as the lexmin/
1685 // lexmax computation will take too long if this number is high.
1686 //
1687 // Experiments with a simple test case using an i7 4800MQ:
1688 //
1689 // #Parameters involved | Time (in sec)
1690 // 6 | 0.01
1691 // 7 | 0.04
1692 // 8 | 0.12
1693 // 9 | 0.40
1694 // 10 | 1.54
1695 // 11 | 6.78
1696 // 12 | 30.38
1697 //
1698 if (isl_set_n_param(Set) > RunTimeChecksMaxParameters) {
1699 unsigned InvolvedParams = 0;
1700 for (unsigned u = 0, e = isl_set_n_param(Set); u < e; u++)
1701 if (isl_set_involves_dims(Set, isl_dim_param, u, 1))
1702 InvolvedParams++;
1703
1704 if (InvolvedParams > RunTimeChecksMaxParameters) {
1705 isl_set_free(Set);
Tobias Grosserb2f39922015-05-28 13:32:11 +00001706 return isl_stat_error;
Johannes Doerfert9143d672014-09-27 11:02:39 +00001707 }
1708 }
1709
Johannes Doerfertb6755bb2015-02-14 12:00:06 +00001710 Set = isl_set_remove_divs(Set);
1711
Johannes Doerfertb164c792014-09-18 11:17:17 +00001712 MinPMA = isl_set_lexmin_pw_multi_aff(isl_set_copy(Set));
1713 MaxPMA = isl_set_lexmax_pw_multi_aff(isl_set_copy(Set));
1714
Johannes Doerfert219b20e2014-10-07 14:37:59 +00001715 MinPMA = isl_pw_multi_aff_coalesce(MinPMA);
1716 MaxPMA = isl_pw_multi_aff_coalesce(MaxPMA);
1717
Johannes Doerfertb164c792014-09-18 11:17:17 +00001718 // Adjust the last dimension of the maximal access by one as we want to
1719 // enclose the accessed memory region by MinPMA and MaxPMA. The pointer
1720 // we test during code generation might now point after the end of the
1721 // allocated array but we will never dereference it anyway.
1722 assert(isl_pw_multi_aff_dim(MaxPMA, isl_dim_out) &&
1723 "Assumed at least one output dimension");
1724 Pos = isl_pw_multi_aff_dim(MaxPMA, isl_dim_out) - 1;
1725 LastDimAff = isl_pw_multi_aff_get_pw_aff(MaxPMA, Pos);
1726 OneAff = isl_aff_zero_on_domain(
1727 isl_local_space_from_space(isl_pw_aff_get_domain_space(LastDimAff)));
1728 OneAff = isl_aff_add_constant_si(OneAff, 1);
1729 LastDimAff = isl_pw_aff_add(LastDimAff, isl_pw_aff_from_aff(OneAff));
1730 MaxPMA = isl_pw_multi_aff_set_pw_aff(MaxPMA, Pos, LastDimAff);
1731
1732 MinMaxAccesses->push_back(std::make_pair(MinPMA, MaxPMA));
1733
1734 isl_set_free(Set);
Tobias Grosserb2f39922015-05-28 13:32:11 +00001735 return isl_stat_ok;
Johannes Doerfertb164c792014-09-18 11:17:17 +00001736}
1737
Johannes Doerferteeab05a2014-10-01 12:42:37 +00001738static __isl_give isl_set *getAccessDomain(MemoryAccess *MA) {
1739 isl_set *Domain = MA->getStatement()->getDomain();
1740 Domain = isl_set_project_out(Domain, isl_dim_set, 0, isl_set_n_dim(Domain));
1741 return isl_set_reset_tuple_id(Domain);
1742}
1743
Johannes Doerfert338b42c2015-07-23 17:04:54 +00001744/// @brief Wrapper function to calculate minimal/maximal accesses to each array.
1745static bool calculateMinMaxAccess(__isl_take isl_union_map *Accesses,
Tobias Grosserbb853c22015-07-25 12:31:03 +00001746 __isl_take isl_union_set *Domains,
Johannes Doerfert210b09a2015-07-26 13:14:38 +00001747 Scop::MinMaxVectorTy &MinMaxAccesses) {
Johannes Doerfert338b42c2015-07-23 17:04:54 +00001748
1749 Accesses = isl_union_map_intersect_domain(Accesses, Domains);
1750 isl_union_set *Locations = isl_union_map_range(Accesses);
Johannes Doerfert338b42c2015-07-23 17:04:54 +00001751 Locations = isl_union_set_coalesce(Locations);
1752 Locations = isl_union_set_detect_equalities(Locations);
1753 bool Valid = (0 == isl_union_set_foreach_set(Locations, buildMinMaxAccess,
Johannes Doerfert210b09a2015-07-26 13:14:38 +00001754 &MinMaxAccesses));
Johannes Doerfert338b42c2015-07-23 17:04:54 +00001755 isl_union_set_free(Locations);
1756 return Valid;
1757}
1758
Johannes Doerfert96425c22015-08-30 21:13:53 +00001759/// @brief Helper to treat non-affine regions and basic blocks the same.
1760///
1761///{
1762
1763/// @brief Return the block that is the representing block for @p RN.
1764static inline BasicBlock *getRegionNodeBasicBlock(RegionNode *RN) {
1765 return RN->isSubRegion() ? RN->getNodeAs<Region>()->getEntry()
1766 : RN->getNodeAs<BasicBlock>();
1767}
1768
1769/// @brief Return the @p idx'th block that is executed after @p RN.
Johannes Doerfert9a132f32015-09-28 09:33:22 +00001770static inline BasicBlock *
1771getRegionNodeSuccessor(RegionNode *RN, TerminatorInst *TI, unsigned idx) {
Johannes Doerfert96425c22015-08-30 21:13:53 +00001772 if (RN->isSubRegion()) {
1773 assert(idx == 0);
1774 return RN->getNodeAs<Region>()->getExit();
1775 }
Johannes Doerfert9a132f32015-09-28 09:33:22 +00001776 return TI->getSuccessor(idx);
Johannes Doerfert96425c22015-08-30 21:13:53 +00001777}
1778
1779/// @brief Return the smallest loop surrounding @p RN.
1780static inline Loop *getRegionNodeLoop(RegionNode *RN, LoopInfo &LI) {
1781 if (!RN->isSubRegion())
1782 return LI.getLoopFor(RN->getNodeAs<BasicBlock>());
1783
1784 Region *NonAffineSubRegion = RN->getNodeAs<Region>();
1785 Loop *L = LI.getLoopFor(NonAffineSubRegion->getEntry());
1786 while (L && NonAffineSubRegion->contains(L))
1787 L = L->getParentLoop();
1788 return L;
1789}
1790
Johannes Doerfertb68cffb2015-09-10 15:27:46 +00001791static inline unsigned getNumBlocksInRegionNode(RegionNode *RN) {
1792 if (!RN->isSubRegion())
1793 return 1;
1794
1795 unsigned NumBlocks = 0;
1796 Region *R = RN->getNodeAs<Region>();
1797 for (auto BB : R->blocks()) {
1798 (void)BB;
1799 NumBlocks++;
1800 }
1801 return NumBlocks;
1802}
1803
Johannes Doerfert08d90a32015-10-07 20:32:43 +00001804static bool containsErrorBlock(RegionNode *RN, const Region &R, LoopInfo &LI,
1805 const DominatorTree &DT) {
Johannes Doerfertf5673802015-10-01 23:48:18 +00001806 if (!RN->isSubRegion())
Johannes Doerfert08d90a32015-10-07 20:32:43 +00001807 return isErrorBlock(*RN->getNodeAs<BasicBlock>(), R, LI, DT);
Johannes Doerfertf5673802015-10-01 23:48:18 +00001808 for (BasicBlock *BB : RN->getNodeAs<Region>()->blocks())
Johannes Doerfert08d90a32015-10-07 20:32:43 +00001809 if (isErrorBlock(*BB, R, LI, DT))
Johannes Doerfertf5673802015-10-01 23:48:18 +00001810 return true;
1811 return false;
1812}
1813
Johannes Doerfert96425c22015-08-30 21:13:53 +00001814///}
1815
Johannes Doerfertb68cffb2015-09-10 15:27:46 +00001816static inline __isl_give isl_set *addDomainDimId(__isl_take isl_set *Domain,
1817 unsigned Dim, Loop *L) {
Johannes Doerfertf2cc86e2015-09-20 16:15:32 +00001818 Domain = isl_set_lower_bound_si(Domain, isl_dim_set, Dim, -1);
Johannes Doerfertb68cffb2015-09-10 15:27:46 +00001819 isl_id *DimId =
1820 isl_id_alloc(isl_set_get_ctx(Domain), nullptr, static_cast<void *>(L));
1821 return isl_set_set_dim_id(Domain, isl_dim_set, Dim, DimId);
1822}
1823
Johannes Doerfert96425c22015-08-30 21:13:53 +00001824isl_set *Scop::getDomainConditions(ScopStmt *Stmt) {
1825 BasicBlock *BB = Stmt->isBlockStmt() ? Stmt->getBasicBlock()
1826 : Stmt->getRegion()->getEntry();
Johannes Doerfertcef616f2015-09-15 22:49:04 +00001827 return getDomainConditions(BB);
1828}
1829
1830isl_set *Scop::getDomainConditions(BasicBlock *BB) {
1831 assert(DomainMap.count(BB) && "Requested BB did not have a domain");
Johannes Doerfertf08bd002015-08-31 13:56:32 +00001832 return isl_set_copy(DomainMap[BB]);
Johannes Doerfert96425c22015-08-30 21:13:53 +00001833}
1834
Johannes Doerfertd8dd8632015-10-07 20:31:36 +00001835void Scop::buildDomains(Region *R) {
Johannes Doerfert96425c22015-08-30 21:13:53 +00001836
Johannes Doerfertf08bd002015-08-31 13:56:32 +00001837 auto *EntryBB = R->getEntry();
1838 int LD = getRelativeLoopDepth(LI.getLoopFor(EntryBB));
1839 auto *S = isl_set_universe(isl_space_set_alloc(getIslCtx(), 0, LD + 1));
Johannes Doerfertb68cffb2015-09-10 15:27:46 +00001840
1841 Loop *L = LI.getLoopFor(EntryBB);
1842 while (LD-- >= 0) {
1843 S = addDomainDimId(S, LD + 1, L);
1844 L = L->getParentLoop();
1845 }
1846
Johannes Doerfertf08bd002015-08-31 13:56:32 +00001847 DomainMap[EntryBB] = S;
Johannes Doerfert96425c22015-08-30 21:13:53 +00001848
Johannes Doerfert40fa56f2015-09-14 11:15:07 +00001849 if (SD.isNonAffineSubRegion(R, R))
1850 return;
1851
Johannes Doerfertd8dd8632015-10-07 20:31:36 +00001852 buildDomainsWithBranchConstraints(R);
1853 propagateDomainConstraints(R);
Johannes Doerfert96425c22015-08-30 21:13:53 +00001854}
1855
Johannes Doerfertd8dd8632015-10-07 20:31:36 +00001856void Scop::buildDomainsWithBranchConstraints(Region *R) {
Johannes Doerfertf08bd002015-08-31 13:56:32 +00001857 RegionInfo &RI = *R->getRegionInfo();
Johannes Doerfert96425c22015-08-30 21:13:53 +00001858
1859 // To create the domain for each block in R we iterate over all blocks and
1860 // subregions in R and propagate the conditions under which the current region
1861 // element is executed. To this end we iterate in reverse post order over R as
1862 // it ensures that we first visit all predecessors of a region node (either a
1863 // basic block or a subregion) before we visit the region node itself.
1864 // Initially, only the domain for the SCoP region entry block is set and from
1865 // there we propagate the current domain to all successors, however we add the
1866 // condition that the successor is actually executed next.
1867 // As we are only interested in non-loop carried constraints here we can
1868 // simply skip loop back edges.
1869
1870 ReversePostOrderTraversal<Region *> RTraversal(R);
1871 for (auto *RN : RTraversal) {
1872
1873 // Recurse for affine subregions but go on for basic blocks and non-affine
1874 // subregions.
1875 if (RN->isSubRegion()) {
1876 Region *SubRegion = RN->getNodeAs<Region>();
1877 if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) {
Johannes Doerfertd8dd8632015-10-07 20:31:36 +00001878 buildDomainsWithBranchConstraints(SubRegion);
Johannes Doerfert96425c22015-08-30 21:13:53 +00001879 continue;
1880 }
1881 }
1882
Johannes Doerfertf5673802015-10-01 23:48:18 +00001883 // Error blocks are assumed not to be executed. Therefor they are not
1884 // checked properly in the ScopDetection. Any attempt to generate control
1885 // conditions from them might result in a crash. However, this is only true
1886 // for the first step of the domain generation (this function) where we
1887 // push the control conditions of a block to the successors. In the second
1888 // step (propagateDomainConstraints) we only receive domain constraints from
1889 // the predecessors and can therefor look at the domain of a error block.
1890 // That allows us to generate the assumptions needed for them not to be
1891 // executed at runtime.
Johannes Doerfert08d90a32015-10-07 20:32:43 +00001892 if (containsErrorBlock(RN, getRegion(), LI, DT))
Johannes Doerfertf5673802015-10-01 23:48:18 +00001893 continue;
1894
Johannes Doerfert96425c22015-08-30 21:13:53 +00001895 BasicBlock *BB = getRegionNodeBasicBlock(RN);
Johannes Doerfert90db75e2015-09-10 17:51:27 +00001896 TerminatorInst *TI = BB->getTerminator();
1897
Johannes Doerfertf5673802015-10-01 23:48:18 +00001898 isl_set *Domain = DomainMap.lookup(BB);
1899 if (!Domain) {
1900 DEBUG(dbgs() << "\tSkip: " << BB->getName()
1901 << ", it is only reachable from error blocks.\n");
Johannes Doerfert90db75e2015-09-10 17:51:27 +00001902 continue;
1903 }
1904
Johannes Doerfert96425c22015-08-30 21:13:53 +00001905 DEBUG(dbgs() << "\tVisit: " << BB->getName() << " : " << Domain << "\n");
Johannes Doerfert96425c22015-08-30 21:13:53 +00001906
1907 Loop *BBLoop = getRegionNodeLoop(RN, LI);
1908 int BBLoopDepth = getRelativeLoopDepth(BBLoop);
1909
1910 // Build the condition sets for the successor nodes of the current region
1911 // node. If it is a non-affine subregion we will always execute the single
1912 // exit node, hence the single entry node domain is the condition set. For
1913 // basic blocks we use the helper function buildConditionSets.
Johannes Doerfert9a132f32015-09-28 09:33:22 +00001914 SmallVector<isl_set *, 8> ConditionSets;
Johannes Doerfert96425c22015-08-30 21:13:53 +00001915 if (RN->isSubRegion())
1916 ConditionSets.push_back(isl_set_copy(Domain));
1917 else
Johannes Doerfert9a132f32015-09-28 09:33:22 +00001918 buildConditionSets(*this, TI, BBLoop, Domain, ConditionSets);
Johannes Doerfert96425c22015-08-30 21:13:53 +00001919
1920 // Now iterate over the successors and set their initial domain based on
1921 // their condition set. We skip back edges here and have to be careful when
1922 // we leave a loop not to keep constraints over a dimension that doesn't
1923 // exist anymore.
Johannes Doerfert9a132f32015-09-28 09:33:22 +00001924 assert(RN->isSubRegion() || TI->getNumSuccessors() == ConditionSets.size());
Johannes Doerfert96425c22015-08-30 21:13:53 +00001925 for (unsigned u = 0, e = ConditionSets.size(); u < e; u++) {
Johannes Doerfert96425c22015-08-30 21:13:53 +00001926 isl_set *CondSet = ConditionSets[u];
Johannes Doerfert9a132f32015-09-28 09:33:22 +00001927 BasicBlock *SuccBB = getRegionNodeSuccessor(RN, TI, u);
Johannes Doerfert96425c22015-08-30 21:13:53 +00001928
1929 // Skip back edges.
1930 if (DT.dominates(SuccBB, BB)) {
1931 isl_set_free(CondSet);
1932 continue;
1933 }
1934
Johannes Doerfertf08bd002015-08-31 13:56:32 +00001935 // Do not adjust the number of dimensions if we enter a boxed loop or are
1936 // in a non-affine subregion or if the surrounding loop stays the same.
Johannes Doerfert96425c22015-08-30 21:13:53 +00001937 Loop *SuccBBLoop = LI.getLoopFor(SuccBB);
Johannes Doerfertf08bd002015-08-31 13:56:32 +00001938 Region *SuccRegion = RI.getRegionFor(SuccBB);
Johannes Doerfert634909c2015-10-04 14:57:41 +00001939 if (SD.isNonAffineSubRegion(SuccRegion, &getRegion()))
1940 while (SuccBBLoop && SuccRegion->contains(SuccBBLoop))
1941 SuccBBLoop = SuccBBLoop->getParentLoop();
1942
1943 if (BBLoop != SuccBBLoop) {
Johannes Doerfertf08bd002015-08-31 13:56:32 +00001944
1945 // Check if the edge to SuccBB is a loop entry or exit edge. If so
1946 // adjust the dimensionality accordingly. Lastly, if we leave a loop
1947 // and enter a new one we need to drop the old constraints.
1948 int SuccBBLoopDepth = getRelativeLoopDepth(SuccBBLoop);
Johannes Doerfertf4fa9872015-09-10 15:53:59 +00001949 unsigned LoopDepthDiff = std::abs(BBLoopDepth - SuccBBLoopDepth);
Tobias Grosser2df884f2015-09-01 18:17:41 +00001950 if (BBLoopDepth > SuccBBLoopDepth) {
Johannes Doerfertf4fa9872015-09-10 15:53:59 +00001951 CondSet = isl_set_project_out(CondSet, isl_dim_set,
1952 isl_set_n_dim(CondSet) - LoopDepthDiff,
1953 LoopDepthDiff);
Tobias Grosser2df884f2015-09-01 18:17:41 +00001954 } else if (SuccBBLoopDepth > BBLoopDepth) {
Johannes Doerfertf4fa9872015-09-10 15:53:59 +00001955 assert(LoopDepthDiff == 1);
Johannes Doerfertf08bd002015-08-31 13:56:32 +00001956 CondSet = isl_set_add_dims(CondSet, isl_dim_set, 1);
Johannes Doerfertb68cffb2015-09-10 15:27:46 +00001957 CondSet = addDomainDimId(CondSet, SuccBBLoopDepth, SuccBBLoop);
Tobias Grosser2df884f2015-09-01 18:17:41 +00001958 } else if (BBLoopDepth >= 0) {
Johannes Doerfertf4fa9872015-09-10 15:53:59 +00001959 assert(LoopDepthDiff <= 1);
Tobias Grosser2df884f2015-09-01 18:17:41 +00001960 CondSet = isl_set_project_out(CondSet, isl_dim_set, BBLoopDepth, 1);
1961 CondSet = isl_set_add_dims(CondSet, isl_dim_set, 1);
Johannes Doerfertb68cffb2015-09-10 15:27:46 +00001962 CondSet = addDomainDimId(CondSet, SuccBBLoopDepth, SuccBBLoop);
Tobias Grosser2df884f2015-09-01 18:17:41 +00001963 }
Johannes Doerfert96425c22015-08-30 21:13:53 +00001964 }
1965
1966 // Set the domain for the successor or merge it with an existing domain in
1967 // case there are multiple paths (without loop back edges) to the
1968 // successor block.
1969 isl_set *&SuccDomain = DomainMap[SuccBB];
1970 if (!SuccDomain)
1971 SuccDomain = CondSet;
1972 else
1973 SuccDomain = isl_set_union(SuccDomain, CondSet);
1974
1975 SuccDomain = isl_set_coalesce(SuccDomain);
Johannes Doerfert634909c2015-10-04 14:57:41 +00001976 DEBUG(dbgs() << "\tSet SuccBB: " << SuccBB->getName() << " : "
1977 << SuccDomain << "\n");
Johannes Doerfert96425c22015-08-30 21:13:53 +00001978 }
1979 }
1980}
1981
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +00001982/// @brief Return the domain for @p BB wrt @p DomainMap.
1983///
1984/// This helper function will lookup @p BB in @p DomainMap but also handle the
1985/// case where @p BB is contained in a non-affine subregion using the region
1986/// tree obtained by @p RI.
1987static __isl_give isl_set *
1988getDomainForBlock(BasicBlock *BB, DenseMap<BasicBlock *, isl_set *> &DomainMap,
1989 RegionInfo &RI) {
1990 auto DIt = DomainMap.find(BB);
1991 if (DIt != DomainMap.end())
1992 return isl_set_copy(DIt->getSecond());
1993
1994 Region *R = RI.getRegionFor(BB);
1995 while (R->getEntry() == BB)
1996 R = R->getParent();
1997 return getDomainForBlock(R->getEntry(), DomainMap, RI);
1998}
1999
Johannes Doerfertd8dd8632015-10-07 20:31:36 +00002000void Scop::propagateDomainConstraints(Region *R) {
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +00002001 // Iterate over the region R and propagate the domain constrains from the
2002 // predecessors to the current node. In contrast to the
2003 // buildDomainsWithBranchConstraints function, this one will pull the domain
2004 // information from the predecessors instead of pushing it to the successors.
2005 // Additionally, we assume the domains to be already present in the domain
2006 // map here. However, we iterate again in reverse post order so we know all
2007 // predecessors have been visited before a block or non-affine subregion is
2008 // visited.
2009
2010 // The set of boxed loops (loops in non-affine subregions) for this SCoP.
2011 auto &BoxedLoops = *SD.getBoxedLoops(&getRegion());
2012
2013 ReversePostOrderTraversal<Region *> RTraversal(R);
2014 for (auto *RN : RTraversal) {
2015
2016 // Recurse for affine subregions but go on for basic blocks and non-affine
2017 // subregions.
2018 if (RN->isSubRegion()) {
2019 Region *SubRegion = RN->getNodeAs<Region>();
2020 if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) {
Johannes Doerfertd8dd8632015-10-07 20:31:36 +00002021 propagateDomainConstraints(SubRegion);
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +00002022 continue;
2023 }
2024 }
2025
Johannes Doerfertf5673802015-10-01 23:48:18 +00002026 // Get the domain for the current block and check if it was initialized or
2027 // not. The only way it was not is if this block is only reachable via error
2028 // blocks, thus will not be executed under the assumptions we make. Such
2029 // blocks have to be skipped as their predecessors might not have domains
2030 // either. It would not benefit us to compute the domain anyway, only the
2031 // domains of the error blocks that are reachable from non-error blocks
2032 // are needed to generate assumptions.
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +00002033 BasicBlock *BB = getRegionNodeBasicBlock(RN);
Johannes Doerfertf5673802015-10-01 23:48:18 +00002034 isl_set *&Domain = DomainMap[BB];
2035 if (!Domain) {
2036 DEBUG(dbgs() << "\tSkip: " << BB->getName()
2037 << ", it is only reachable from error blocks.\n");
2038 DomainMap.erase(BB);
2039 continue;
2040 }
2041 DEBUG(dbgs() << "\tVisit: " << BB->getName() << " : " << Domain << "\n");
2042
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +00002043 Loop *BBLoop = getRegionNodeLoop(RN, LI);
2044 int BBLoopDepth = getRelativeLoopDepth(BBLoop);
2045
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +00002046 isl_set *PredDom = isl_set_empty(isl_set_get_space(Domain));
2047 for (auto *PredBB : predecessors(BB)) {
2048
2049 // Skip backedges
2050 if (DT.dominates(BB, PredBB))
2051 continue;
2052
2053 isl_set *PredBBDom = nullptr;
2054
2055 // Handle the SCoP entry block with its outside predecessors.
2056 if (!getRegion().contains(PredBB))
2057 PredBBDom = isl_set_universe(isl_set_get_space(PredDom));
2058
2059 if (!PredBBDom) {
2060 // Determine the loop depth of the predecessor and adjust its domain to
2061 // the domain of the current block. This can mean we have to:
2062 // o) Drop a dimension if this block is the exit of a loop, not the
2063 // header of a new loop and the predecessor was part of the loop.
2064 // o) Add an unconstrainted new dimension if this block is the header
2065 // of a loop and the predecessor is not part of it.
2066 // o) Drop the information about the innermost loop dimension when the
2067 // predecessor and the current block are surrounded by different
2068 // loops in the same depth.
2069 PredBBDom = getDomainForBlock(PredBB, DomainMap, *R->getRegionInfo());
2070 Loop *PredBBLoop = LI.getLoopFor(PredBB);
2071 while (BoxedLoops.count(PredBBLoop))
2072 PredBBLoop = PredBBLoop->getParentLoop();
2073
2074 int PredBBLoopDepth = getRelativeLoopDepth(PredBBLoop);
Johannes Doerfertf4fa9872015-09-10 15:53:59 +00002075 unsigned LoopDepthDiff = std::abs(BBLoopDepth - PredBBLoopDepth);
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +00002076 if (BBLoopDepth < PredBBLoopDepth)
Johannes Doerfertf4fa9872015-09-10 15:53:59 +00002077 PredBBDom = isl_set_project_out(
2078 PredBBDom, isl_dim_set, isl_set_n_dim(PredBBDom) - LoopDepthDiff,
2079 LoopDepthDiff);
2080 else if (PredBBLoopDepth < BBLoopDepth) {
2081 assert(LoopDepthDiff == 1);
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +00002082 PredBBDom = isl_set_add_dims(PredBBDom, isl_dim_set, 1);
Johannes Doerfertf4fa9872015-09-10 15:53:59 +00002083 } else if (BBLoop != PredBBLoop && BBLoopDepth >= 0) {
2084 assert(LoopDepthDiff <= 1);
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +00002085 PredBBDom = isl_set_drop_constraints_involving_dims(
2086 PredBBDom, isl_dim_set, BBLoopDepth, 1);
Johannes Doerfertf4fa9872015-09-10 15:53:59 +00002087 }
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +00002088 }
2089
2090 PredDom = isl_set_union(PredDom, PredBBDom);
2091 }
2092
2093 // Under the union of all predecessor conditions we can reach this block.
Johannes Doerfertb20f1512015-09-15 22:11:49 +00002094 Domain = isl_set_coalesce(isl_set_intersect(Domain, PredDom));
Johannes Doerfert90db75e2015-09-10 17:51:27 +00002095
Johannes Doerfertf32f5f22015-09-28 01:30:37 +00002096 if (BBLoop && BBLoop->getHeader() == BB && getRegion().contains(BBLoop))
Johannes Doerfertd8dd8632015-10-07 20:31:36 +00002097 addLoopBoundsToHeaderDomain(BBLoop);
Johannes Doerfertf2cc86e2015-09-20 16:15:32 +00002098
Johannes Doerfert90db75e2015-09-10 17:51:27 +00002099 // Add assumptions for error blocks.
Johannes Doerfert08d90a32015-10-07 20:32:43 +00002100 if (containsErrorBlock(RN, getRegion(), LI, DT)) {
Johannes Doerfert90db75e2015-09-10 17:51:27 +00002101 IsOptimized = true;
2102 isl_set *DomPar = isl_set_params(isl_set_copy(Domain));
2103 addAssumption(isl_set_complement(DomPar));
2104 }
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +00002105 }
2106}
2107
2108/// @brief Create a map from SetSpace -> SetSpace where the dimensions @p Dim
2109/// is incremented by one and all other dimensions are equal, e.g.,
2110/// [i0, i1, i2, i3] -> [i0, i1, i2 + 1, i3]
2111/// if @p Dim is 2 and @p SetSpace has 4 dimensions.
2112static __isl_give isl_map *
2113createNextIterationMap(__isl_take isl_space *SetSpace, unsigned Dim) {
2114 auto *MapSpace = isl_space_map_from_set(SetSpace);
2115 auto *NextIterationMap = isl_map_universe(isl_space_copy(MapSpace));
2116 for (unsigned u = 0; u < isl_map_n_in(NextIterationMap); u++)
2117 if (u != Dim)
2118 NextIterationMap =
2119 isl_map_equate(NextIterationMap, isl_dim_in, u, isl_dim_out, u);
2120 auto *C = isl_constraint_alloc_equality(isl_local_space_from_space(MapSpace));
2121 C = isl_constraint_set_constant_si(C, 1);
2122 C = isl_constraint_set_coefficient_si(C, isl_dim_in, Dim, 1);
2123 C = isl_constraint_set_coefficient_si(C, isl_dim_out, Dim, -1);
2124 NextIterationMap = isl_map_add_constraint(NextIterationMap, C);
2125 return NextIterationMap;
2126}
2127
Johannes Doerfertd8dd8632015-10-07 20:31:36 +00002128void Scop::addLoopBoundsToHeaderDomain(Loop *L) {
Johannes Doerfertf2cc86e2015-09-20 16:15:32 +00002129 int LoopDepth = getRelativeLoopDepth(L);
2130 assert(LoopDepth >= 0 && "Loop in region should have at least depth one");
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +00002131
Johannes Doerfertf2cc86e2015-09-20 16:15:32 +00002132 BasicBlock *HeaderBB = L->getHeader();
2133 assert(DomainMap.count(HeaderBB));
2134 isl_set *&HeaderBBDom = DomainMap[HeaderBB];
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +00002135
Johannes Doerfertf2cc86e2015-09-20 16:15:32 +00002136 isl_map *NextIterationMap =
2137 createNextIterationMap(isl_set_get_space(HeaderBBDom), LoopDepth);
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +00002138
Johannes Doerfertf2cc86e2015-09-20 16:15:32 +00002139 isl_set *UnionBackedgeCondition =
2140 isl_set_empty(isl_set_get_space(HeaderBBDom));
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +00002141
Johannes Doerfertf2cc86e2015-09-20 16:15:32 +00002142 SmallVector<llvm::BasicBlock *, 4> LatchBlocks;
2143 L->getLoopLatches(LatchBlocks);
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +00002144
Johannes Doerfertf2cc86e2015-09-20 16:15:32 +00002145 for (BasicBlock *LatchBB : LatchBlocks) {
Johannes Doerfertf5673802015-10-01 23:48:18 +00002146
2147 // If the latch is only reachable via error statements we skip it.
2148 isl_set *LatchBBDom = DomainMap.lookup(LatchBB);
2149 if (!LatchBBDom)
2150 continue;
2151
Johannes Doerfertf2cc86e2015-09-20 16:15:32 +00002152 isl_set *BackedgeCondition = nullptr;
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +00002153
Johannes Doerfert9a132f32015-09-28 09:33:22 +00002154 TerminatorInst *TI = LatchBB->getTerminator();
2155 BranchInst *BI = dyn_cast<BranchInst>(TI);
2156 if (BI && BI->isUnconditional())
Johannes Doerfertf2cc86e2015-09-20 16:15:32 +00002157 BackedgeCondition = isl_set_copy(LatchBBDom);
2158 else {
Johannes Doerfert9a132f32015-09-28 09:33:22 +00002159 SmallVector<isl_set *, 8> ConditionSets;
Johannes Doerfertf2cc86e2015-09-20 16:15:32 +00002160 int idx = BI->getSuccessor(0) != HeaderBB;
Johannes Doerfert9a132f32015-09-28 09:33:22 +00002161 buildConditionSets(*this, TI, L, LatchBBDom, ConditionSets);
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +00002162
Johannes Doerfertf2cc86e2015-09-20 16:15:32 +00002163 // Free the non back edge condition set as we do not need it.
2164 isl_set_free(ConditionSets[1 - idx]);
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +00002165
Johannes Doerfertf2cc86e2015-09-20 16:15:32 +00002166 BackedgeCondition = ConditionSets[idx];
Johannes Doerfert06c57b52015-09-20 15:00:20 +00002167 }
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +00002168
Johannes Doerfertf2cc86e2015-09-20 16:15:32 +00002169 int LatchLoopDepth = getRelativeLoopDepth(LI.getLoopFor(LatchBB));
2170 assert(LatchLoopDepth >= LoopDepth);
2171 BackedgeCondition =
2172 isl_set_project_out(BackedgeCondition, isl_dim_set, LoopDepth + 1,
2173 LatchLoopDepth - LoopDepth);
2174 UnionBackedgeCondition =
2175 isl_set_union(UnionBackedgeCondition, BackedgeCondition);
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +00002176 }
Johannes Doerfertf2cc86e2015-09-20 16:15:32 +00002177
2178 isl_map *ForwardMap = isl_map_lex_le(isl_set_get_space(HeaderBBDom));
2179 for (int i = 0; i < LoopDepth; i++)
2180 ForwardMap = isl_map_equate(ForwardMap, isl_dim_in, i, isl_dim_out, i);
2181
2182 isl_set *UnionBackedgeConditionComplement =
2183 isl_set_complement(UnionBackedgeCondition);
2184 UnionBackedgeConditionComplement = isl_set_lower_bound_si(
2185 UnionBackedgeConditionComplement, isl_dim_set, LoopDepth, 0);
2186 UnionBackedgeConditionComplement =
2187 isl_set_apply(UnionBackedgeConditionComplement, ForwardMap);
2188 HeaderBBDom = isl_set_subtract(HeaderBBDom, UnionBackedgeConditionComplement);
2189 HeaderBBDom = isl_set_apply(HeaderBBDom, NextIterationMap);
2190
2191 auto Parts = partitionSetParts(HeaderBBDom, LoopDepth);
2192 HeaderBBDom = Parts.second;
2193
Johannes Doerfert6a72a2a2015-09-20 16:59:23 +00002194 // Check if there is a <nsw> tagged AddRec for this loop and if so do not add
2195 // the bounded assumptions to the context as they are already implied by the
2196 // <nsw> tag.
2197 if (Affinator.hasNSWAddRecForLoop(L)) {
2198 isl_set_free(Parts.first);
2199 return;
2200 }
2201
Johannes Doerfertf2cc86e2015-09-20 16:15:32 +00002202 isl_set *UnboundedCtx = isl_set_params(Parts.first);
2203 isl_set *BoundedCtx = isl_set_complement(UnboundedCtx);
Johannes Doerfert707a4062015-09-20 16:38:19 +00002204 addAssumption(BoundedCtx);
Johannes Doerfert5b9ff8b2015-09-10 13:00:06 +00002205}
2206
Johannes Doerfert120de4b2015-08-20 18:30:08 +00002207void Scop::buildAliasChecks(AliasAnalysis &AA) {
2208 if (!PollyUseRuntimeAliasChecks)
2209 return;
2210
2211 if (buildAliasGroups(AA))
2212 return;
2213
2214 // If a problem occurs while building the alias groups we need to delete
2215 // this SCoP and pretend it wasn't valid in the first place. To this end
2216 // we make the assumed context infeasible.
2217 addAssumption(isl_set_empty(getParamSpace()));
2218
2219 DEBUG(dbgs() << "\n\nNOTE: Run time checks for " << getNameStr()
2220 << " could not be created as the number of parameters involved "
2221 "is too high. The SCoP will be "
2222 "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust "
2223 "the maximal number of parameters but be advised that the "
2224 "compile time might increase exponentially.\n\n");
2225}
2226
Johannes Doerfert9143d672014-09-27 11:02:39 +00002227bool Scop::buildAliasGroups(AliasAnalysis &AA) {
Johannes Doerfertb164c792014-09-18 11:17:17 +00002228 // To create sound alias checks we perform the following steps:
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00002229 // o) Use the alias analysis and an alias set tracker to build alias sets
Johannes Doerfertb164c792014-09-18 11:17:17 +00002230 // for all memory accesses inside the SCoP.
2231 // o) For each alias set we then map the aliasing pointers back to the
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00002232 // memory accesses we know, thus obtain groups of memory accesses which
Johannes Doerfertb164c792014-09-18 11:17:17 +00002233 // might alias.
Johannes Doerferteeab05a2014-10-01 12:42:37 +00002234 // o) We divide each group based on the domains of the minimal/maximal
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00002235 // accesses. That means two minimal/maximal accesses are only in a group
Johannes Doerferteeab05a2014-10-01 12:42:37 +00002236 // if their access domains intersect, otherwise they are in different
2237 // ones.
Johannes Doerfert338b42c2015-07-23 17:04:54 +00002238 // o) We partition each group into read only and non read only accesses.
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00002239 // o) For each group with more than one base pointer we then compute minimal
Johannes Doerfert338b42c2015-07-23 17:04:54 +00002240 // and maximal accesses to each array of a group in read only and non
2241 // read only partitions separately.
Johannes Doerfertb164c792014-09-18 11:17:17 +00002242 using AliasGroupTy = SmallVector<MemoryAccess *, 4>;
2243
2244 AliasSetTracker AST(AA);
2245
2246 DenseMap<Value *, MemoryAccess *> PtrToAcc;
Johannes Doerfert13771732014-10-01 12:40:46 +00002247 DenseSet<Value *> HasWriteAccess;
Tobias Grosser7c3bad52015-05-27 05:16:57 +00002248 for (ScopStmt &Stmt : *this) {
Johannes Doerfertf1ee2622014-10-06 17:43:00 +00002249
2250 // Skip statements with an empty domain as they will never be executed.
Tobias Grosser7c3bad52015-05-27 05:16:57 +00002251 isl_set *StmtDomain = Stmt.getDomain();
Johannes Doerfertf1ee2622014-10-06 17:43:00 +00002252 bool StmtDomainEmpty = isl_set_is_empty(StmtDomain);
2253 isl_set_free(StmtDomain);
2254 if (StmtDomainEmpty)
2255 continue;
2256
Tobias Grosser7c3bad52015-05-27 05:16:57 +00002257 for (MemoryAccess *MA : Stmt) {
Michael Kruse8d0b7342015-09-25 21:21:00 +00002258 if (MA->isImplicit())
Johannes Doerfertb164c792014-09-18 11:17:17 +00002259 continue;
Johannes Doerfert13771732014-10-01 12:40:46 +00002260 if (!MA->isRead())
2261 HasWriteAccess.insert(MA->getBaseAddr());
Johannes Doerfertb164c792014-09-18 11:17:17 +00002262 Instruction *Acc = MA->getAccessInstruction();
2263 PtrToAcc[getPointerOperand(*Acc)] = MA;
2264 AST.add(Acc);
2265 }
2266 }
2267
2268 SmallVector<AliasGroupTy, 4> AliasGroups;
2269 for (AliasSet &AS : AST) {
Johannes Doerfert74f68692014-10-08 02:23:48 +00002270 if (AS.isMustAlias() || AS.isForwardingAliasSet())
Johannes Doerfertb164c792014-09-18 11:17:17 +00002271 continue;
2272 AliasGroupTy AG;
2273 for (auto PR : AS)
2274 AG.push_back(PtrToAcc[PR.getValue()]);
2275 assert(AG.size() > 1 &&
2276 "Alias groups should contain at least two accesses");
2277 AliasGroups.push_back(std::move(AG));
2278 }
2279
Johannes Doerferteeab05a2014-10-01 12:42:37 +00002280 // Split the alias groups based on their domain.
2281 for (unsigned u = 0; u < AliasGroups.size(); u++) {
2282 AliasGroupTy NewAG;
2283 AliasGroupTy &AG = AliasGroups[u];
2284 AliasGroupTy::iterator AGI = AG.begin();
2285 isl_set *AGDomain = getAccessDomain(*AGI);
2286 while (AGI != AG.end()) {
2287 MemoryAccess *MA = *AGI;
2288 isl_set *MADomain = getAccessDomain(MA);
2289 if (isl_set_is_disjoint(AGDomain, MADomain)) {
2290 NewAG.push_back(MA);
2291 AGI = AG.erase(AGI);
2292 isl_set_free(MADomain);
2293 } else {
2294 AGDomain = isl_set_union(AGDomain, MADomain);
2295 AGI++;
2296 }
2297 }
2298 if (NewAG.size() > 1)
2299 AliasGroups.push_back(std::move(NewAG));
2300 isl_set_free(AGDomain);
2301 }
2302
Tobias Grosserf4c24b22015-04-05 13:11:54 +00002303 MapVector<const Value *, SmallPtrSet<MemoryAccess *, 8>> ReadOnlyPairs;
Johannes Doerfert13771732014-10-01 12:40:46 +00002304 SmallPtrSet<const Value *, 4> NonReadOnlyBaseValues;
2305 for (AliasGroupTy &AG : AliasGroups) {
2306 NonReadOnlyBaseValues.clear();
2307 ReadOnlyPairs.clear();
2308
Johannes Doerferteeab05a2014-10-01 12:42:37 +00002309 if (AG.size() < 2) {
2310 AG.clear();
2311 continue;
2312 }
2313
Johannes Doerfert13771732014-10-01 12:40:46 +00002314 for (auto II = AG.begin(); II != AG.end();) {
2315 Value *BaseAddr = (*II)->getBaseAddr();
2316 if (HasWriteAccess.count(BaseAddr)) {
2317 NonReadOnlyBaseValues.insert(BaseAddr);
2318 II++;
2319 } else {
2320 ReadOnlyPairs[BaseAddr].insert(*II);
2321 II = AG.erase(II);
2322 }
2323 }
2324
2325 // If we don't have read only pointers check if there are at least two
2326 // non read only pointers, otherwise clear the alias group.
Tobias Grosserbb853c22015-07-25 12:31:03 +00002327 if (ReadOnlyPairs.empty() && NonReadOnlyBaseValues.size() <= 1) {
Johannes Doerfert338b42c2015-07-23 17:04:54 +00002328 AG.clear();
Johannes Doerfert13771732014-10-01 12:40:46 +00002329 continue;
2330 }
2331
2332 // If we don't have non read only pointers clear the alias group.
2333 if (NonReadOnlyBaseValues.empty()) {
2334 AG.clear();
2335 continue;
2336 }
2337
Johannes Doerfert338b42c2015-07-23 17:04:54 +00002338 // Calculate minimal and maximal accesses for non read only accesses.
Johannes Doerfert210b09a2015-07-26 13:14:38 +00002339 MinMaxAliasGroups.emplace_back();
2340 MinMaxVectorPairTy &pair = MinMaxAliasGroups.back();
2341 MinMaxVectorTy &MinMaxAccessesNonReadOnly = pair.first;
2342 MinMaxVectorTy &MinMaxAccessesReadOnly = pair.second;
2343 MinMaxAccessesNonReadOnly.reserve(AG.size());
Johannes Doerfertb164c792014-09-18 11:17:17 +00002344
2345 isl_union_map *Accesses = isl_union_map_empty(getParamSpace());
Johannes Doerfert338b42c2015-07-23 17:04:54 +00002346
2347 // AG contains only non read only accesses.
Johannes Doerfertb164c792014-09-18 11:17:17 +00002348 for (MemoryAccess *MA : AG)
2349 Accesses = isl_union_map_add_map(Accesses, MA->getAccessRelation());
Johannes Doerfertb164c792014-09-18 11:17:17 +00002350
Tobias Grosserdaaed0e2015-08-20 21:29:26 +00002351 bool Valid = calculateMinMaxAccess(Accesses, getDomains(),
2352 MinMaxAccessesNonReadOnly);
Johannes Doerfert338b42c2015-07-23 17:04:54 +00002353
2354 // Bail out if the number of values we need to compare is too large.
2355 // This is important as the number of comparisions grows quadratically with
2356 // the number of values we need to compare.
Johannes Doerfert210b09a2015-07-26 13:14:38 +00002357 if (!Valid || (MinMaxAccessesNonReadOnly.size() + !ReadOnlyPairs.empty() >
2358 RunTimeChecksMaxArraysPerGroup))
Johannes Doerfert338b42c2015-07-23 17:04:54 +00002359 return false;
Johannes Doerfert338b42c2015-07-23 17:04:54 +00002360
2361 // Calculate minimal and maximal accesses for read only accesses.
Johannes Doerfert210b09a2015-07-26 13:14:38 +00002362 MinMaxAccessesReadOnly.reserve(ReadOnlyPairs.size());
Johannes Doerfert338b42c2015-07-23 17:04:54 +00002363 Accesses = isl_union_map_empty(getParamSpace());
2364
2365 for (const auto &ReadOnlyPair : ReadOnlyPairs)
2366 for (MemoryAccess *MA : ReadOnlyPair.second)
2367 Accesses = isl_union_map_add_map(Accesses, MA->getAccessRelation());
2368
Tobias Grosserdaaed0e2015-08-20 21:29:26 +00002369 Valid =
2370 calculateMinMaxAccess(Accesses, getDomains(), MinMaxAccessesReadOnly);
Johannes Doerfert9143d672014-09-27 11:02:39 +00002371
2372 if (!Valid)
Tobias Grosser50d4e2e2015-03-28 14:50:32 +00002373 return false;
Johannes Doerfertb164c792014-09-18 11:17:17 +00002374 }
Johannes Doerfert9143d672014-09-27 11:02:39 +00002375
Tobias Grosser50d4e2e2015-03-28 14:50:32 +00002376 return true;
Johannes Doerfertb164c792014-09-18 11:17:17 +00002377}
2378
Johannes Doerfertb68cffb2015-09-10 15:27:46 +00002379static Loop *getLoopSurroundingRegion(Region &R, LoopInfo &LI) {
2380 Loop *L = LI.getLoopFor(R.getEntry());
2381 return L ? (R.contains(L) ? L->getParentLoop() : L) : nullptr;
2382}
2383
Johannes Doerfertf8206cf2015-04-12 22:58:40 +00002384static unsigned getMaxLoopDepthInRegion(const Region &R, LoopInfo &LI,
2385 ScopDetection &SD) {
2386
2387 const ScopDetection::BoxedLoopsSetTy *BoxedLoops = SD.getBoxedLoops(&R);
2388
Johannes Doerferte3da05a2014-11-01 00:12:13 +00002389 unsigned MinLD = INT_MAX, MaxLD = 0;
2390 for (BasicBlock *BB : R.blocks()) {
2391 if (Loop *L = LI.getLoopFor(BB)) {
David Peixottodc0a11c2015-01-13 18:31:55 +00002392 if (!R.contains(L))
2393 continue;
Johannes Doerfertf8206cf2015-04-12 22:58:40 +00002394 if (BoxedLoops && BoxedLoops->count(L))
2395 continue;
Johannes Doerferte3da05a2014-11-01 00:12:13 +00002396 unsigned LD = L->getLoopDepth();
2397 MinLD = std::min(MinLD, LD);
2398 MaxLD = std::max(MaxLD, LD);
2399 }
2400 }
2401
2402 // Handle the case that there is no loop in the SCoP first.
2403 if (MaxLD == 0)
2404 return 1;
2405
2406 assert(MinLD >= 1 && "Minimal loop depth should be at least one");
2407 assert(MaxLD >= MinLD &&
2408 "Maximal loop depth was smaller than mininaml loop depth?");
2409 return MaxLD - MinLD + 1;
2410}
2411
Johannes Doerfert478a7de2015-10-02 13:09:31 +00002412Scop::Scop(Region &R, AccFuncMapType &AccFuncMap, ScopDetection &SD,
Johannes Doerfertd8dd8632015-10-07 20:31:36 +00002413 ScalarEvolution &ScalarEvolution, DominatorTree &DT, LoopInfo &LI,
Johannes Doerfert96425c22015-08-30 21:13:53 +00002414 isl_ctx *Context, unsigned MaxLoopDepth)
Johannes Doerfertd8dd8632015-10-07 20:31:36 +00002415 : LI(LI), DT(DT), SE(&ScalarEvolution), SD(SD), R(R),
2416 AccFuncMap(AccFuncMap), IsOptimized(false),
2417 HasSingleExitEdge(R.getExitingBlock()), MaxLoopDepth(MaxLoopDepth),
2418 IslCtx(Context), Context(nullptr), Affinator(this),
2419 AssumedContext(nullptr), BoundaryContext(nullptr), Schedule(nullptr) {}
Johannes Doerfertff9d1982015-02-24 12:00:50 +00002420
Johannes Doerfertd8dd8632015-10-07 20:31:36 +00002421void Scop::init(AliasAnalysis &AA) {
Tobias Grosser6be480c2011-11-08 15:41:13 +00002422 buildContext();
Johannes Doerfert697fdf82015-10-09 17:12:26 +00002423 buildInvariantEquivalenceClasses();
2424
Johannes Doerfertd8dd8632015-10-07 20:31:36 +00002425 buildDomains(&R);
Johannes Doerfert96425c22015-08-30 21:13:53 +00002426
Michael Krusecac948e2015-10-02 13:53:07 +00002427 // Remove empty and ignored statements.
Michael Kruseafe06702015-10-02 16:33:27 +00002428 // Exit early in case there are no executable statements left in this scop.
Michael Krusecac948e2015-10-02 13:53:07 +00002429 simplifySCoP(true);
Michael Kruseafe06702015-10-02 16:33:27 +00002430 if (Stmts.empty())
2431 return;
Tobias Grosser75805372011-04-29 06:27:02 +00002432
Michael Krusecac948e2015-10-02 13:53:07 +00002433 // The ScopStmts now have enough information to initialize themselves.
2434 for (ScopStmt &Stmt : Stmts)
2435 Stmt.init();
2436
2437 DenseMap<Loop *, std::pair<isl_schedule *, unsigned>> LoopSchedules;
Johannes Doerfertb68cffb2015-09-10 15:27:46 +00002438 Loop *L = getLoopSurroundingRegion(R, LI);
2439 LoopSchedules[L];
Johannes Doerfertd8dd8632015-10-07 20:31:36 +00002440 buildSchedule(&R, LoopSchedules);
Tobias Grosser99c70dd2015-09-26 08:55:54 +00002441 updateAccessDimensionality();
Johannes Doerfertb68cffb2015-09-10 15:27:46 +00002442 Schedule = LoopSchedules[L].first;
Tobias Grosser75805372011-04-29 06:27:02 +00002443
Tobias Grosser8cae72f2011-11-08 15:41:08 +00002444 realignParams();
Tobias Grosser18daaca2012-05-22 10:47:27 +00002445 addParameterBounds();
Tobias Grosser8a9c2352015-08-16 10:19:29 +00002446 addUserContext();
Johannes Doerfert883f8c12015-09-15 22:52:53 +00002447 buildBoundaryContext();
2448 simplifyContexts();
Johannes Doerfert120de4b2015-08-20 18:30:08 +00002449 buildAliasChecks(AA);
Johannes Doerfertc1db67e2015-09-29 23:47:21 +00002450
2451 hoistInvariantLoads();
Michael Krusecac948e2015-10-02 13:53:07 +00002452 simplifySCoP(false);
Tobias Grosser75805372011-04-29 06:27:02 +00002453}
2454
2455Scop::~Scop() {
2456 isl_set_free(Context);
Tobias Grossere86109f2013-10-29 21:05:49 +00002457 isl_set_free(AssumedContext);
Johannes Doerfert883f8c12015-09-15 22:52:53 +00002458 isl_set_free(BoundaryContext);
Tobias Grosser808cd692015-07-14 09:33:13 +00002459 isl_schedule_free(Schedule);
Tobias Grosser75805372011-04-29 06:27:02 +00002460
Johannes Doerfert96425c22015-08-30 21:13:53 +00002461 for (auto It : DomainMap)
2462 isl_set_free(It.second);
2463
Johannes Doerfertb164c792014-09-18 11:17:17 +00002464 // Free the alias groups
Johannes Doerfert338b42c2015-07-23 17:04:54 +00002465 for (MinMaxVectorPairTy &MinMaxAccessPair : MinMaxAliasGroups) {
Johannes Doerfert210b09a2015-07-26 13:14:38 +00002466 for (MinMaxAccessTy &MMA : MinMaxAccessPair.first) {
Johannes Doerfertb164c792014-09-18 11:17:17 +00002467 isl_pw_multi_aff_free(MMA.first);
2468 isl_pw_multi_aff_free(MMA.second);
2469 }
Johannes Doerfert210b09a2015-07-26 13:14:38 +00002470 for (MinMaxAccessTy &MMA : MinMaxAccessPair.second) {
Johannes Doerfert338b42c2015-07-23 17:04:54 +00002471 isl_pw_multi_aff_free(MMA.first);
2472 isl_pw_multi_aff_free(MMA.second);
2473 }
Johannes Doerfertb164c792014-09-18 11:17:17 +00002474 }
Johannes Doerfertc1db67e2015-09-29 23:47:21 +00002475
Johannes Doerfert697fdf82015-10-09 17:12:26 +00002476 for (const auto &IAClass : InvariantEquivClasses)
2477 if (!IAClass.second.empty())
2478 isl_set_free(IAClass.second.front().second);
Tobias Grosser75805372011-04-29 06:27:02 +00002479}
2480
Tobias Grosser99c70dd2015-09-26 08:55:54 +00002481void Scop::updateAccessDimensionality() {
2482 for (auto &Stmt : *this)
2483 for (auto &Access : Stmt)
2484 Access->updateDimensionality();
2485}
2486
Michael Krusecac948e2015-10-02 13:53:07 +00002487void Scop::simplifySCoP(bool RemoveIgnoredStmts) {
Johannes Doerfertc1db67e2015-09-29 23:47:21 +00002488 for (auto StmtIt = Stmts.begin(), StmtEnd = Stmts.end(); StmtIt != StmtEnd;) {
2489 ScopStmt &Stmt = *StmtIt;
Michael Krusecac948e2015-10-02 13:53:07 +00002490 RegionNode *RN = Stmt.isRegionStmt()
2491 ? Stmt.getRegion()->getNode()
2492 : getRegion().getBBNode(Stmt.getBasicBlock());
Johannes Doerfertc1db67e2015-09-29 23:47:21 +00002493
Johannes Doerfertf17a78e2015-10-04 15:00:05 +00002494 if (StmtIt->isEmpty() ||
2495 isl_set_is_empty(DomainMap[getRegionNodeBasicBlock(RN)]) ||
2496 (RemoveIgnoredStmts && isIgnored(RN))) {
2497
Michael Krusecac948e2015-10-02 13:53:07 +00002498 // Remove the statement because it is unnecessary.
2499 if (Stmt.isRegionStmt())
2500 for (BasicBlock *BB : Stmt.getRegion()->blocks())
2501 StmtMap.erase(BB);
2502 else
2503 StmtMap.erase(Stmt.getBasicBlock());
2504
2505 StmtIt = Stmts.erase(StmtIt);
Johannes Doerfertc1db67e2015-09-29 23:47:21 +00002506 continue;
2507 }
2508
Michael Krusecac948e2015-10-02 13:53:07 +00002509 StmtIt++;
Johannes Doerfertc1db67e2015-09-29 23:47:21 +00002510 }
2511}
2512
2513void Scop::hoistInvariantLoads() {
2514 isl_union_map *Writes = getWrites();
2515 for (ScopStmt &Stmt : *this) {
2516
2517 // TODO: Loads that are not loop carried, hence are in a statement with
2518 // zero iterators, are by construction invariant, though we
Johannes Doerfert09e36972015-10-07 20:17:36 +00002519 // currently "hoist" them anyway. This is necessary because we allow
2520 // them to be treated as parameters (e.g., in conditions) and our code
2521 // generation would otherwise use the old value.
Johannes Doerfertc1db67e2015-09-29 23:47:21 +00002522
Johannes Doerfert8930f482015-10-02 14:51:00 +00002523 BasicBlock *BB = Stmt.isBlockStmt() ? Stmt.getBasicBlock()
2524 : Stmt.getRegion()->getEntry();
Johannes Doerfertc1db67e2015-09-29 23:47:21 +00002525 isl_set *Domain = Stmt.getDomain();
2526 MemoryAccessList InvMAs;
2527
2528 for (MemoryAccess *MA : Stmt) {
2529 if (MA->isImplicit() || MA->isWrite() || !MA->isAffine())
2530 continue;
2531
Johannes Doerfert8930f482015-10-02 14:51:00 +00002532 // Skip accesses in non-affine subregions as they might not be executed
2533 // under the same condition as the entry of the non-affine subregion.
2534 if (BB != MA->getAccessInstruction()->getParent())
2535 continue;
2536
Johannes Doerfertc1db67e2015-09-29 23:47:21 +00002537 isl_map *AccessRelation = MA->getAccessRelation();
2538 if (isl_map_involves_dims(AccessRelation, isl_dim_in, 0,
2539 Stmt.getNumIterators())) {
2540 isl_map_free(AccessRelation);
2541 continue;
2542 }
2543
2544 AccessRelation =
2545 isl_map_intersect_domain(AccessRelation, isl_set_copy(Domain));
2546 isl_set *AccessRange = isl_map_range(AccessRelation);
2547
2548 isl_union_map *Written = isl_union_map_intersect_range(
2549 isl_union_map_copy(Writes), isl_union_set_from_set(AccessRange));
2550 bool IsWritten = !isl_union_map_is_empty(Written);
2551 isl_union_map_free(Written);
2552
2553 if (IsWritten)
2554 continue;
2555
2556 InvMAs.push_front(MA);
2557 }
2558
2559 // We inserted invariant accesses always in the front but need them to be
2560 // sorted in a "natural order". The statements are already sorted in reverse
2561 // post order and that suffices for the accesses too. The reason we require
2562 // an order in the first place is the dependences between invariant loads
2563 // that can be caused by indirect loads.
2564 InvMAs.reverse();
2565
2566 // Transfer the memory access from the statement to the SCoP.
Johannes Doerfert697fdf82015-10-09 17:12:26 +00002567 Stmt.hoistMemoryAccesses(InvMAs, InvariantEquivClasses);
Johannes Doerfertc1db67e2015-09-29 23:47:21 +00002568
2569 isl_set_free(Domain);
2570 }
2571 isl_union_map_free(Writes);
2572
Johannes Doerfert697fdf82015-10-09 17:12:26 +00002573 if (!InvariantEquivClasses.empty())
Johannes Doerfertc1db67e2015-09-29 23:47:21 +00002574 IsOptimized = true;
Johannes Doerfert09e36972015-10-07 20:17:36 +00002575
Johannes Doerfert697fdf82015-10-09 17:12:26 +00002576 auto &ScopRIL = *SD.getRequiredInvariantLoads(&getRegion());
Johannes Doerfert09e36972015-10-07 20:17:36 +00002577 // Check required invariant loads that were tagged during SCoP detection.
Johannes Doerfert697fdf82015-10-09 17:12:26 +00002578 for (LoadInst *LI : ScopRIL) {
Johannes Doerfert09e36972015-10-07 20:17:36 +00002579 assert(LI && getRegion().contains(LI));
2580 ScopStmt *Stmt = getStmtForBasicBlock(LI->getParent());
2581 if (Stmt && Stmt->lookupAccessesFor(LI) != nullptr) {
2582 DEBUG(dbgs() << "\n\nWARNING: Load (" << *LI
2583 << ") is required to be invariant but was not marked as "
2584 "such. SCoP for "
2585 << getRegion() << " will be dropped\n\n");
2586 addAssumption(isl_set_empty(getParamSpace()));
2587 return;
2588 }
2589 }
2590
2591 // We want invariant accesses to be sorted in a "natural order" because there
2592 // might be dependences between invariant loads. These can be caused by
2593 // indirect loads but also because an invariant load is only conditionally
2594 // executed and the condition is dependent on another invariant load. As we
2595 // want to do code generation in a straight forward way, e.g., preload the
2596 // accesses in the list one after another, we sort them such that the
2597 // preloaded values needed in the conditions will always be in front. Before
2598 // we already ordered the accesses such that indirect loads can be resolved,
2599 // thus we use a stable sort here.
2600
Johannes Doerfert697fdf82015-10-09 17:12:26 +00002601 auto compareInvariantAccesses = [this](
2602 const InvariantEquivClassTy &IAClass0,
2603 const InvariantEquivClassTy &IAClass1) {
2604 const InvariantAccessTy &IA0 = IAClass0.second.front();
2605 const InvariantAccessTy &IA1 = IAClass1.second.front();
2606
Johannes Doerfert09e36972015-10-07 20:17:36 +00002607 Instruction *AI0 = IA0.first->getAccessInstruction();
2608 Instruction *AI1 = IA1.first->getAccessInstruction();
2609
2610 const SCEV *S0 =
2611 SE->isSCEVable(AI0->getType()) ? SE->getSCEV(AI0) : nullptr;
2612 const SCEV *S1 =
2613 SE->isSCEVable(AI1->getType()) ? SE->getSCEV(AI1) : nullptr;
2614
2615 isl_id *Id0 = getIdForParam(S0);
2616 isl_id *Id1 = getIdForParam(S1);
2617
2618 if (Id0 && !Id1) {
2619 isl_id_free(Id0);
2620 isl_id_free(Id1);
2621 return true;
2622 }
2623
2624 if (!Id0) {
2625 isl_id_free(Id0);
2626 isl_id_free(Id1);
2627 return false;
2628 }
2629
2630 assert(Id0 && Id1);
2631
2632 isl_set *Dom0 = IA0.second;
2633 isl_set *Dom1 = IA1.second;
2634
2635 int Dim0 = isl_set_find_dim_by_id(Dom0, isl_dim_param, Id0);
Johannes Doerfert09e36972015-10-07 20:17:36 +00002636
Johannes Doerfert09e36972015-10-07 20:17:36 +00002637 bool Involves1Id0 = isl_set_involves_dims(Dom1, isl_dim_param, Dim0, 1);
David Blaikie91e113d2015-10-09 18:22:18 +00002638 assert(!Involves1Id0 ||
2639 !isl_set_involves_dims(
2640 Dom0, isl_dim_param,
2641 isl_set_find_dim_by_id(Dom0, isl_dim_param, Id1), 1));
Johannes Doerfert09e36972015-10-07 20:17:36 +00002642
2643 isl_id_free(Id0);
2644 isl_id_free(Id1);
2645
2646 return Involves1Id0;
2647 };
2648
Johannes Doerfert697fdf82015-10-09 17:12:26 +00002649 std::stable_sort(InvariantEquivClasses.begin(), InvariantEquivClasses.end(),
Johannes Doerfert09e36972015-10-07 20:17:36 +00002650 compareInvariantAccesses);
Johannes Doerfertc1db67e2015-09-29 23:47:21 +00002651}
2652
Johannes Doerfert80ef1102014-11-07 08:31:31 +00002653const ScopArrayInfo *
2654Scop::getOrCreateScopArrayInfo(Value *BasePtr, Type *AccessType,
Michael Kruse28468772015-09-14 15:45:33 +00002655 ArrayRef<const SCEV *> Sizes, bool IsPHI) {
Tobias Grosser92245222015-07-28 14:53:44 +00002656 auto &SAI = ScopArrayInfoMap[std::make_pair(BasePtr, IsPHI)];
Tobias Grosser99c70dd2015-09-26 08:55:54 +00002657 if (!SAI) {
Tobias Grosserd46fd5e2015-08-12 15:27:16 +00002658 SAI.reset(new ScopArrayInfo(BasePtr, AccessType, getIslCtx(), Sizes, IsPHI,
2659 this));
Tobias Grosser99c70dd2015-09-26 08:55:54 +00002660 } else {
2661 if (Sizes.size() > SAI->getNumberOfDimensions())
2662 SAI->updateSizes(Sizes);
2663 }
Tobias Grosserab671442015-05-23 05:58:27 +00002664 return SAI.get();
Johannes Doerfert1a28a892014-10-05 11:32:18 +00002665}
2666
Tobias Grosser92245222015-07-28 14:53:44 +00002667const ScopArrayInfo *Scop::getScopArrayInfo(Value *BasePtr, bool IsPHI) {
2668 auto *SAI = ScopArrayInfoMap[std::make_pair(BasePtr, IsPHI)].get();
Johannes Doerfert1a28a892014-10-05 11:32:18 +00002669 assert(SAI && "No ScopArrayInfo available for this base pointer");
2670 return SAI;
2671}
2672
Tobias Grosser74394f02013-01-14 22:40:23 +00002673std::string Scop::getContextStr() const { return stringFromIslObj(Context); }
Tobias Grosser5e6813d2014-07-02 17:47:48 +00002674std::string Scop::getAssumedContextStr() const {
2675 return stringFromIslObj(AssumedContext);
2676}
Johannes Doerfert883f8c12015-09-15 22:52:53 +00002677std::string Scop::getBoundaryContextStr() const {
2678 return stringFromIslObj(BoundaryContext);
2679}
Tobias Grosser75805372011-04-29 06:27:02 +00002680
2681std::string Scop::getNameStr() const {
2682 std::string ExitName, EntryName;
2683 raw_string_ostream ExitStr(ExitName);
2684 raw_string_ostream EntryStr(EntryName);
2685
Tobias Grosserf240b482014-01-09 10:42:15 +00002686 R.getEntry()->printAsOperand(EntryStr, false);
Tobias Grosser75805372011-04-29 06:27:02 +00002687 EntryStr.str();
2688
2689 if (R.getExit()) {
Tobias Grosserf240b482014-01-09 10:42:15 +00002690 R.getExit()->printAsOperand(ExitStr, false);
Tobias Grosser75805372011-04-29 06:27:02 +00002691 ExitStr.str();
2692 } else
2693 ExitName = "FunctionExit";
2694
2695 return EntryName + "---" + ExitName;
2696}
2697
Tobias Grosser74394f02013-01-14 22:40:23 +00002698__isl_give isl_set *Scop::getContext() const { return isl_set_copy(Context); }
Tobias Grosser37487052011-10-06 00:03:42 +00002699__isl_give isl_space *Scop::getParamSpace() const {
Tobias Grossereeb9f3c2015-05-26 21:37:31 +00002700 return isl_set_get_space(Context);
Tobias Grosser37487052011-10-06 00:03:42 +00002701}
2702
Tobias Grossere86109f2013-10-29 21:05:49 +00002703__isl_give isl_set *Scop::getAssumedContext() const {
2704 return isl_set_copy(AssumedContext);
2705}
2706
Johannes Doerfert43788c52015-08-20 05:58:56 +00002707__isl_give isl_set *Scop::getRuntimeCheckContext() const {
2708 isl_set *RuntimeCheckContext = getAssumedContext();
Johannes Doerfert883f8c12015-09-15 22:52:53 +00002709 RuntimeCheckContext =
2710 isl_set_intersect(RuntimeCheckContext, getBoundaryContext());
2711 RuntimeCheckContext = simplifyAssumptionContext(RuntimeCheckContext, *this);
Johannes Doerfert43788c52015-08-20 05:58:56 +00002712 return RuntimeCheckContext;
2713}
2714
Johannes Doerfert5d5b3062015-08-20 18:06:30 +00002715bool Scop::hasFeasibleRuntimeContext() const {
Johannes Doerfert43788c52015-08-20 05:58:56 +00002716 isl_set *RuntimeCheckContext = getRuntimeCheckContext();
Johannes Doerfert5d5b3062015-08-20 18:06:30 +00002717 RuntimeCheckContext = addNonEmptyDomainConstraints(RuntimeCheckContext);
Johannes Doerfert43788c52015-08-20 05:58:56 +00002718 bool IsFeasible = !isl_set_is_empty(RuntimeCheckContext);
2719 isl_set_free(RuntimeCheckContext);
2720 return IsFeasible;
2721}
2722
Tobias Grosser5e6813d2014-07-02 17:47:48 +00002723void Scop::addAssumption(__isl_take isl_set *Set) {
2724 AssumedContext = isl_set_intersect(AssumedContext, Set);
Tobias Grosser7b50bee2014-11-25 10:51:12 +00002725 AssumedContext = isl_set_coalesce(AssumedContext);
Tobias Grosser5e6813d2014-07-02 17:47:48 +00002726}
2727
Johannes Doerfert883f8c12015-09-15 22:52:53 +00002728__isl_give isl_set *Scop::getBoundaryContext() const {
2729 return isl_set_copy(BoundaryContext);
2730}
2731
Tobias Grosser75805372011-04-29 06:27:02 +00002732void Scop::printContext(raw_ostream &OS) const {
2733 OS << "Context:\n";
2734
2735 if (!Context) {
2736 OS.indent(4) << "n/a\n\n";
2737 return;
2738 }
2739
2740 OS.indent(4) << getContextStr() << "\n";
Tobias Grosser60b54f12011-11-08 15:41:28 +00002741
Tobias Grosser5e6813d2014-07-02 17:47:48 +00002742 OS.indent(4) << "Assumed Context:\n";
2743 if (!AssumedContext) {
2744 OS.indent(4) << "n/a\n\n";
2745 return;
2746 }
2747
2748 OS.indent(4) << getAssumedContextStr() << "\n";
2749
Johannes Doerfert883f8c12015-09-15 22:52:53 +00002750 OS.indent(4) << "Boundary Context:\n";
2751 if (!BoundaryContext) {
2752 OS.indent(4) << "n/a\n\n";
2753 return;
2754 }
2755
2756 OS.indent(4) << getBoundaryContextStr() << "\n";
2757
Tobias Grosser083d3d32014-06-28 08:59:45 +00002758 for (const SCEV *Parameter : Parameters) {
Tobias Grosser60b54f12011-11-08 15:41:28 +00002759 int Dim = ParameterIds.find(Parameter)->second;
Tobias Grosser60b54f12011-11-08 15:41:28 +00002760 OS.indent(4) << "p" << Dim << ": " << *Parameter << "\n";
2761 }
Tobias Grosser75805372011-04-29 06:27:02 +00002762}
2763
Johannes Doerfertb164c792014-09-18 11:17:17 +00002764void Scop::printAliasAssumptions(raw_ostream &OS) const {
Tobias Grosserbb853c22015-07-25 12:31:03 +00002765 int noOfGroups = 0;
2766 for (const MinMaxVectorPairTy &Pair : MinMaxAliasGroups) {
Johannes Doerfert210b09a2015-07-26 13:14:38 +00002767 if (Pair.second.size() == 0)
Johannes Doerfert338b42c2015-07-23 17:04:54 +00002768 noOfGroups += 1;
2769 else
Johannes Doerfert210b09a2015-07-26 13:14:38 +00002770 noOfGroups += Pair.second.size();
Johannes Doerfert338b42c2015-07-23 17:04:54 +00002771 }
2772
Tobias Grosserbb853c22015-07-25 12:31:03 +00002773 OS.indent(4) << "Alias Groups (" << noOfGroups << "):\n";
Johannes Doerfertb164c792014-09-18 11:17:17 +00002774 if (MinMaxAliasGroups.empty()) {
2775 OS.indent(8) << "n/a\n";
2776 return;
2777 }
Johannes Doerfert338b42c2015-07-23 17:04:54 +00002778
Tobias Grosserbb853c22015-07-25 12:31:03 +00002779 for (const MinMaxVectorPairTy &Pair : MinMaxAliasGroups) {
Johannes Doerfert338b42c2015-07-23 17:04:54 +00002780
2781 // If the group has no read only accesses print the write accesses.
Johannes Doerfert210b09a2015-07-26 13:14:38 +00002782 if (Pair.second.empty()) {
Johannes Doerfert338b42c2015-07-23 17:04:54 +00002783 OS.indent(8) << "[[";
Johannes Doerfert210b09a2015-07-26 13:14:38 +00002784 for (const MinMaxAccessTy &MMANonReadOnly : Pair.first) {
Tobias Grosserbb853c22015-07-25 12:31:03 +00002785 OS << " <" << MMANonReadOnly.first << ", " << MMANonReadOnly.second
2786 << ">";
Johannes Doerfert338b42c2015-07-23 17:04:54 +00002787 }
2788 OS << " ]]\n";
2789 }
2790
Johannes Doerfert210b09a2015-07-26 13:14:38 +00002791 for (const MinMaxAccessTy &MMAReadOnly : Pair.second) {
Johannes Doerfert338b42c2015-07-23 17:04:54 +00002792 OS.indent(8) << "[[";
Tobias Grosserbb853c22015-07-25 12:31:03 +00002793 OS << " <" << MMAReadOnly.first << ", " << MMAReadOnly.second << ">";
Johannes Doerfert210b09a2015-07-26 13:14:38 +00002794 for (const MinMaxAccessTy &MMANonReadOnly : Pair.first) {
Tobias Grosserbb853c22015-07-25 12:31:03 +00002795 OS << " <" << MMANonReadOnly.first << ", " << MMANonReadOnly.second
2796 << ">";
Johannes Doerfert338b42c2015-07-23 17:04:54 +00002797 }
2798 OS << " ]]\n";
2799 }
Johannes Doerfertb164c792014-09-18 11:17:17 +00002800 }
2801}
2802
Tobias Grosser75805372011-04-29 06:27:02 +00002803void Scop::printStatements(raw_ostream &OS) const {
2804 OS << "Statements {\n";
2805
Tobias Grosser7c3bad52015-05-27 05:16:57 +00002806 for (const ScopStmt &Stmt : *this)
2807 OS.indent(4) << Stmt;
Tobias Grosser75805372011-04-29 06:27:02 +00002808
2809 OS.indent(4) << "}\n";
2810}
2811
Tobias Grosser49ad36c2015-05-20 08:05:31 +00002812void Scop::printArrayInfo(raw_ostream &OS) const {
2813 OS << "Arrays {\n";
2814
Tobias Grosserab671442015-05-23 05:58:27 +00002815 for (auto &Array : arrays())
Tobias Grosser49ad36c2015-05-20 08:05:31 +00002816 Array.second->print(OS);
2817
2818 OS.indent(4) << "}\n";
Tobias Grosserd46fd5e2015-08-12 15:27:16 +00002819
2820 OS.indent(4) << "Arrays (Bounds as pw_affs) {\n";
2821
2822 for (auto &Array : arrays())
2823 Array.second->print(OS, /* SizeAsPwAff */ true);
2824
2825 OS.indent(4) << "}\n";
Tobias Grosser49ad36c2015-05-20 08:05:31 +00002826}
2827
Tobias Grosser75805372011-04-29 06:27:02 +00002828void Scop::print(raw_ostream &OS) const {
Tobias Grosser4eb7ddb2014-03-18 18:51:11 +00002829 OS.indent(4) << "Function: " << getRegion().getEntry()->getParent()->getName()
2830 << "\n";
Tobias Grosser483fdd42014-03-18 18:05:38 +00002831 OS.indent(4) << "Region: " << getNameStr() << "\n";
David Peixottodc0a11c2015-01-13 18:31:55 +00002832 OS.indent(4) << "Max Loop Depth: " << getMaxLoopDepth() << "\n";
Johannes Doerfertc1db67e2015-09-29 23:47:21 +00002833 OS.indent(4) << "Invariant Accesses: {\n";
Johannes Doerfert697fdf82015-10-09 17:12:26 +00002834 for (const auto &IAClass : InvariantEquivClasses) {
2835 if (IAClass.second.empty()) {
2836 OS.indent(12) << "Class Pointer: " << IAClass.first << "\n";
2837 } else {
2838 IAClass.second.front().first->print(OS);
2839 OS.indent(12) << "Execution Context: " << IAClass.second.front().second
2840 << "\n";
2841 }
Johannes Doerfertc1db67e2015-09-29 23:47:21 +00002842 }
2843 OS.indent(4) << "}\n";
Tobias Grosser75805372011-04-29 06:27:02 +00002844 printContext(OS.indent(4));
Tobias Grosser49ad36c2015-05-20 08:05:31 +00002845 printArrayInfo(OS.indent(4));
Johannes Doerfertb164c792014-09-18 11:17:17 +00002846 printAliasAssumptions(OS);
Tobias Grosser75805372011-04-29 06:27:02 +00002847 printStatements(OS.indent(4));
2848}
2849
2850void Scop::dump() const { print(dbgs()); }
2851
Tobias Grosser9a38ab82011-11-08 15:41:03 +00002852isl_ctx *Scop::getIslCtx() const { return IslCtx; }
Tobias Grosser75805372011-04-29 06:27:02 +00002853
Johannes Doerfertcef616f2015-09-15 22:49:04 +00002854__isl_give isl_pw_aff *Scop::getPwAff(const SCEV *E, BasicBlock *BB) {
2855 return Affinator.getPwAff(E, BB);
Johannes Doerfert574182d2015-08-12 10:19:50 +00002856}
2857
Tobias Grosser808cd692015-07-14 09:33:13 +00002858__isl_give isl_union_set *Scop::getDomains() const {
Tobias Grosserbc4ef902014-06-28 08:59:38 +00002859 isl_union_set *Domain = isl_union_set_empty(getParamSpace());
Tobias Grosser5f9a7622012-02-14 14:02:40 +00002860
Tobias Grosser808cd692015-07-14 09:33:13 +00002861 for (const ScopStmt &Stmt : *this)
Tobias Grosser7c3bad52015-05-27 05:16:57 +00002862 Domain = isl_union_set_add_set(Domain, Stmt.getDomain());
Tobias Grosser5f9a7622012-02-14 14:02:40 +00002863
2864 return Domain;
2865}
2866
Tobias Grosser780ce0f2014-07-11 07:12:10 +00002867__isl_give isl_union_map *Scop::getMustWrites() {
Tobias Grossereeb9f3c2015-05-26 21:37:31 +00002868 isl_union_map *Write = isl_union_map_empty(getParamSpace());
Tobias Grosser780ce0f2014-07-11 07:12:10 +00002869
Tobias Grosser7c3bad52015-05-27 05:16:57 +00002870 for (ScopStmt &Stmt : *this) {
2871 for (MemoryAccess *MA : Stmt) {
Tobias Grosser780ce0f2014-07-11 07:12:10 +00002872 if (!MA->isMustWrite())
2873 continue;
2874
Tobias Grosser7c3bad52015-05-27 05:16:57 +00002875 isl_set *Domain = Stmt.getDomain();
Tobias Grosser780ce0f2014-07-11 07:12:10 +00002876 isl_map *AccessDomain = MA->getAccessRelation();
2877 AccessDomain = isl_map_intersect_domain(AccessDomain, Domain);
2878 Write = isl_union_map_add_map(Write, AccessDomain);
2879 }
2880 }
2881 return isl_union_map_coalesce(Write);
2882}
2883
2884__isl_give isl_union_map *Scop::getMayWrites() {
Tobias Grossereeb9f3c2015-05-26 21:37:31 +00002885 isl_union_map *Write = isl_union_map_empty(getParamSpace());
Tobias Grosser780ce0f2014-07-11 07:12:10 +00002886
Tobias Grosser7c3bad52015-05-27 05:16:57 +00002887 for (ScopStmt &Stmt : *this) {
2888 for (MemoryAccess *MA : Stmt) {
Tobias Grosser780ce0f2014-07-11 07:12:10 +00002889 if (!MA->isMayWrite())
2890 continue;
2891
Tobias Grosser7c3bad52015-05-27 05:16:57 +00002892 isl_set *Domain = Stmt.getDomain();
Tobias Grosser780ce0f2014-07-11 07:12:10 +00002893 isl_map *AccessDomain = MA->getAccessRelation();
2894 AccessDomain = isl_map_intersect_domain(AccessDomain, Domain);
2895 Write = isl_union_map_add_map(Write, AccessDomain);
2896 }
2897 }
2898 return isl_union_map_coalesce(Write);
2899}
2900
Tobias Grosser37eb4222014-02-20 21:43:54 +00002901__isl_give isl_union_map *Scop::getWrites() {
Tobias Grossereeb9f3c2015-05-26 21:37:31 +00002902 isl_union_map *Write = isl_union_map_empty(getParamSpace());
Tobias Grosser37eb4222014-02-20 21:43:54 +00002903
Tobias Grosser7c3bad52015-05-27 05:16:57 +00002904 for (ScopStmt &Stmt : *this) {
2905 for (MemoryAccess *MA : Stmt) {
Johannes Doerfertf6752892014-06-13 18:01:45 +00002906 if (!MA->isWrite())
Tobias Grosser37eb4222014-02-20 21:43:54 +00002907 continue;
2908
Tobias Grosser7c3bad52015-05-27 05:16:57 +00002909 isl_set *Domain = Stmt.getDomain();
Johannes Doerfertf6752892014-06-13 18:01:45 +00002910 isl_map *AccessDomain = MA->getAccessRelation();
Tobias Grosser37eb4222014-02-20 21:43:54 +00002911 AccessDomain = isl_map_intersect_domain(AccessDomain, Domain);
2912 Write = isl_union_map_add_map(Write, AccessDomain);
2913 }
2914 }
2915 return isl_union_map_coalesce(Write);
2916}
2917
2918__isl_give isl_union_map *Scop::getReads() {
Tobias Grosserbc4ef902014-06-28 08:59:38 +00002919 isl_union_map *Read = isl_union_map_empty(getParamSpace());
Tobias Grosser37eb4222014-02-20 21:43:54 +00002920
Tobias Grosser7c3bad52015-05-27 05:16:57 +00002921 for (ScopStmt &Stmt : *this) {
2922 for (MemoryAccess *MA : Stmt) {
Johannes Doerfertf6752892014-06-13 18:01:45 +00002923 if (!MA->isRead())
Tobias Grosser37eb4222014-02-20 21:43:54 +00002924 continue;
2925
Tobias Grosser7c3bad52015-05-27 05:16:57 +00002926 isl_set *Domain = Stmt.getDomain();
Johannes Doerfertf6752892014-06-13 18:01:45 +00002927 isl_map *AccessDomain = MA->getAccessRelation();
Tobias Grosser37eb4222014-02-20 21:43:54 +00002928
2929 AccessDomain = isl_map_intersect_domain(AccessDomain, Domain);
2930 Read = isl_union_map_add_map(Read, AccessDomain);
2931 }
2932 }
2933 return isl_union_map_coalesce(Read);
2934}
2935
Tobias Grosser808cd692015-07-14 09:33:13 +00002936__isl_give isl_union_map *Scop::getSchedule() const {
2937 auto Tree = getScheduleTree();
2938 auto S = isl_schedule_get_map(Tree);
2939 isl_schedule_free(Tree);
2940 return S;
2941}
Tobias Grosser37eb4222014-02-20 21:43:54 +00002942
Tobias Grosser808cd692015-07-14 09:33:13 +00002943__isl_give isl_schedule *Scop::getScheduleTree() const {
2944 return isl_schedule_intersect_domain(isl_schedule_copy(Schedule),
2945 getDomains());
2946}
Tobias Grosserbc4ef902014-06-28 08:59:38 +00002947
Tobias Grosser808cd692015-07-14 09:33:13 +00002948void Scop::setSchedule(__isl_take isl_union_map *NewSchedule) {
2949 auto *S = isl_schedule_from_domain(getDomains());
2950 S = isl_schedule_insert_partial_schedule(
2951 S, isl_multi_union_pw_aff_from_union_map(NewSchedule));
2952 isl_schedule_free(Schedule);
2953 Schedule = S;
2954}
2955
2956void Scop::setScheduleTree(__isl_take isl_schedule *NewSchedule) {
2957 isl_schedule_free(Schedule);
2958 Schedule = NewSchedule;
Tobias Grosser37eb4222014-02-20 21:43:54 +00002959}
2960
2961bool Scop::restrictDomains(__isl_take isl_union_set *Domain) {
2962 bool Changed = false;
Tobias Grosser7c3bad52015-05-27 05:16:57 +00002963 for (ScopStmt &Stmt : *this) {
2964 isl_union_set *StmtDomain = isl_union_set_from_set(Stmt.getDomain());
Tobias Grosser37eb4222014-02-20 21:43:54 +00002965 isl_union_set *NewStmtDomain = isl_union_set_intersect(
2966 isl_union_set_copy(StmtDomain), isl_union_set_copy(Domain));
2967
2968 if (isl_union_set_is_subset(StmtDomain, NewStmtDomain)) {
2969 isl_union_set_free(StmtDomain);
2970 isl_union_set_free(NewStmtDomain);
2971 continue;
2972 }
2973
2974 Changed = true;
2975
2976 isl_union_set_free(StmtDomain);
2977 NewStmtDomain = isl_union_set_coalesce(NewStmtDomain);
2978
2979 if (isl_union_set_is_empty(NewStmtDomain)) {
Tobias Grosser7c3bad52015-05-27 05:16:57 +00002980 Stmt.restrictDomain(isl_set_empty(Stmt.getDomainSpace()));
Tobias Grosser37eb4222014-02-20 21:43:54 +00002981 isl_union_set_free(NewStmtDomain);
2982 } else
Tobias Grosser7c3bad52015-05-27 05:16:57 +00002983 Stmt.restrictDomain(isl_set_from_union_set(NewStmtDomain));
Tobias Grosser37eb4222014-02-20 21:43:54 +00002984 }
2985 isl_union_set_free(Domain);
2986 return Changed;
2987}
2988
Tobias Grosser75805372011-04-29 06:27:02 +00002989ScalarEvolution *Scop::getSE() const { return SE; }
2990
Johannes Doerfertf5673802015-10-01 23:48:18 +00002991bool Scop::isIgnored(RegionNode *RN) {
2992 BasicBlock *BB = getRegionNodeBasicBlock(RN);
Tobias Grosser75805372011-04-29 06:27:02 +00002993
Johannes Doerfertf5673802015-10-01 23:48:18 +00002994 // Check if there are accesses contained.
2995 bool ContainsAccesses = false;
2996 if (!RN->isSubRegion())
2997 ContainsAccesses = getAccessFunctions(BB);
2998 else
2999 for (BasicBlock *RBB : RN->getNodeAs<Region>()->blocks())
3000 ContainsAccesses |= (getAccessFunctions(RBB) != nullptr);
3001 if (!ContainsAccesses)
3002 return true;
3003
3004 // Check for reachability via non-error blocks.
3005 if (!DomainMap.count(BB))
3006 return true;
3007
3008 // Check if error blocks are contained.
Johannes Doerfert08d90a32015-10-07 20:32:43 +00003009 if (containsErrorBlock(RN, getRegion(), LI, DT))
Johannes Doerfertf5673802015-10-01 23:48:18 +00003010 return true;
3011
3012 return false;
Tobias Grosser75805372011-04-29 06:27:02 +00003013}
3014
Tobias Grosser808cd692015-07-14 09:33:13 +00003015struct MapToDimensionDataTy {
3016 int N;
3017 isl_union_pw_multi_aff *Res;
3018};
Johannes Doerfertff9d1982015-02-24 12:00:50 +00003019
Tobias Grosser808cd692015-07-14 09:33:13 +00003020// @brief Create a function that maps the elements of 'Set' to its N-th
3021// dimension.
3022//
3023// The result is added to 'User->Res'.
3024//
3025// @param Set The input set.
3026// @param N The dimension to map to.
3027//
3028// @returns Zero if no error occurred, non-zero otherwise.
3029static isl_stat mapToDimension_AddSet(__isl_take isl_set *Set, void *User) {
3030 struct MapToDimensionDataTy *Data = (struct MapToDimensionDataTy *)User;
3031 int Dim;
3032 isl_space *Space;
3033 isl_pw_multi_aff *PMA;
3034
3035 Dim = isl_set_dim(Set, isl_dim_set);
3036 Space = isl_set_get_space(Set);
3037 PMA = isl_pw_multi_aff_project_out_map(Space, isl_dim_set, Data->N,
3038 Dim - Data->N);
3039 if (Data->N > 1)
3040 PMA = isl_pw_multi_aff_drop_dims(PMA, isl_dim_out, 0, Data->N - 1);
3041 Data->Res = isl_union_pw_multi_aff_add_pw_multi_aff(Data->Res, PMA);
3042
3043 isl_set_free(Set);
3044
3045 return isl_stat_ok;
Johannes Doerfertff9d1982015-02-24 12:00:50 +00003046}
3047
Tobias Grosser808cd692015-07-14 09:33:13 +00003048// @brief Create a function that maps the elements of Domain to their Nth
3049// dimension.
3050//
3051// @param Domain The set of elements to map.
3052// @param N The dimension to map to.
3053static __isl_give isl_multi_union_pw_aff *
3054mapToDimension(__isl_take isl_union_set *Domain, int N) {
Johannes Doerfertb68cffb2015-09-10 15:27:46 +00003055 if (N <= 0 || isl_union_set_is_empty(Domain)) {
3056 isl_union_set_free(Domain);
3057 return nullptr;
3058 }
3059
Tobias Grosser808cd692015-07-14 09:33:13 +00003060 struct MapToDimensionDataTy Data;
3061 isl_space *Space;
3062
3063 Space = isl_union_set_get_space(Domain);
3064 Data.N = N;
3065 Data.Res = isl_union_pw_multi_aff_empty(Space);
3066 if (isl_union_set_foreach_set(Domain, &mapToDimension_AddSet, &Data) < 0)
3067 Data.Res = isl_union_pw_multi_aff_free(Data.Res);
3068
3069 isl_union_set_free(Domain);
3070 return isl_multi_union_pw_aff_from_union_pw_multi_aff(Data.Res);
3071}
3072
Michael Kruse9d080092015-09-11 21:41:48 +00003073ScopStmt *Scop::addScopStmt(BasicBlock *BB, Region *R) {
Tobias Grosser808cd692015-07-14 09:33:13 +00003074 ScopStmt *Stmt;
3075 if (BB) {
Michael Kruse9d080092015-09-11 21:41:48 +00003076 Stmts.emplace_back(*this, *BB);
Tobias Grosser808cd692015-07-14 09:33:13 +00003077 Stmt = &Stmts.back();
3078 StmtMap[BB] = Stmt;
3079 } else {
3080 assert(R && "Either basic block or a region expected.");
Michael Kruse9d080092015-09-11 21:41:48 +00003081 Stmts.emplace_back(*this, *R);
Tobias Grosser808cd692015-07-14 09:33:13 +00003082 Stmt = &Stmts.back();
3083 for (BasicBlock *BB : R->blocks())
3084 StmtMap[BB] = Stmt;
3085 }
3086 return Stmt;
3087}
3088
Johannes Doerfertb68cffb2015-09-10 15:27:46 +00003089void Scop::buildSchedule(
Johannes Doerfertd8dd8632015-10-07 20:31:36 +00003090 Region *R,
Johannes Doerfertb68cffb2015-09-10 15:27:46 +00003091 DenseMap<Loop *, std::pair<isl_schedule *, unsigned>> &LoopSchedules) {
Michael Kruse046dde42015-08-10 13:01:57 +00003092
Johannes Doerfert40fa56f2015-09-14 11:15:07 +00003093 if (SD.isNonAffineSubRegion(R, &getRegion())) {
Johannes Doerfertc6987c12015-09-26 13:41:43 +00003094 Loop *L = getLoopSurroundingRegion(*R, LI);
3095 auto &LSchedulePair = LoopSchedules[L];
Michael Krusecac948e2015-10-02 13:53:07 +00003096 ScopStmt *Stmt = getStmtForBasicBlock(R->getEntry());
Michael Kruseafe06702015-10-02 16:33:27 +00003097 isl_set *Domain = Stmt->getDomain();
Michael Krusecac948e2015-10-02 13:53:07 +00003098 auto *UDomain = isl_union_set_from_set(Domain);
3099 auto *StmtSchedule = isl_schedule_from_domain(UDomain);
Johannes Doerfert40fa56f2015-09-14 11:15:07 +00003100 LSchedulePair.first = StmtSchedule;
3101 return;
3102 }
3103
Johannes Doerfertb68cffb2015-09-10 15:27:46 +00003104 ReversePostOrderTraversal<Region *> RTraversal(R);
3105 for (auto *RN : RTraversal) {
Michael Kruse046dde42015-08-10 13:01:57 +00003106
Johannes Doerfertb68cffb2015-09-10 15:27:46 +00003107 if (RN->isSubRegion()) {
3108 Region *SubRegion = RN->getNodeAs<Region>();
3109 if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) {
Johannes Doerfertd8dd8632015-10-07 20:31:36 +00003110 buildSchedule(SubRegion, LoopSchedules);
Johannes Doerfertb68cffb2015-09-10 15:27:46 +00003111 continue;
3112 }
Tobias Grosser75805372011-04-29 06:27:02 +00003113 }
Johannes Doerfertb68cffb2015-09-10 15:27:46 +00003114
3115 Loop *L = getRegionNodeLoop(RN, LI);
3116 int LD = getRelativeLoopDepth(L);
3117 auto &LSchedulePair = LoopSchedules[L];
3118 LSchedulePair.second += getNumBlocksInRegionNode(RN);
3119
Michael Krusecac948e2015-10-02 13:53:07 +00003120 BasicBlock *BB = getRegionNodeBasicBlock(RN);
3121 ScopStmt *Stmt = getStmtForBasicBlock(BB);
3122 if (Stmt) {
Johannes Doerfertb68cffb2015-09-10 15:27:46 +00003123 auto *UDomain = isl_union_set_from_set(Stmt->getDomain());
3124 auto *StmtSchedule = isl_schedule_from_domain(UDomain);
3125 LSchedulePair.first =
3126 combineInSequence(LSchedulePair.first, StmtSchedule);
3127 }
3128
3129 unsigned NumVisited = LSchedulePair.second;
3130 while (L && NumVisited == L->getNumBlocks()) {
3131 auto *LDomain = isl_schedule_get_domain(LSchedulePair.first);
3132 if (auto *MUPA = mapToDimension(LDomain, LD + 1))
3133 LSchedulePair.first =
3134 isl_schedule_insert_partial_schedule(LSchedulePair.first, MUPA);
3135
3136 auto *PL = L->getParentLoop();
3137 assert(LoopSchedules.count(PL));
3138 auto &PSchedulePair = LoopSchedules[PL];
3139 PSchedulePair.first =
3140 combineInSequence(PSchedulePair.first, LSchedulePair.first);
3141 PSchedulePair.second += NumVisited;
3142
3143 L = PL;
3144 NumVisited = PSchedulePair.second;
3145 }
Tobias Grosser808cd692015-07-14 09:33:13 +00003146 }
Tobias Grosser75805372011-04-29 06:27:02 +00003147}
3148
Johannes Doerfert7c494212014-10-31 23:13:39 +00003149ScopStmt *Scop::getStmtForBasicBlock(BasicBlock *BB) const {
Tobias Grosser57411e32015-05-27 06:51:34 +00003150 auto StmtMapIt = StmtMap.find(BB);
Johannes Doerfert7c494212014-10-31 23:13:39 +00003151 if (StmtMapIt == StmtMap.end())
3152 return nullptr;
3153 return StmtMapIt->second;
3154}
3155
Johannes Doerfert96425c22015-08-30 21:13:53 +00003156int Scop::getRelativeLoopDepth(const Loop *L) const {
3157 Loop *OuterLoop =
3158 L ? R.outermostLoopInRegion(const_cast<Loop *>(L)) : nullptr;
3159 if (!OuterLoop)
3160 return -1;
Johannes Doerfertd020b772015-08-27 06:53:52 +00003161 return L->getLoopDepth() - OuterLoop->getLoopDepth();
3162}
3163
Michael Krused868b5d2015-09-10 15:25:24 +00003164void ScopInfo::buildPHIAccesses(PHINode *PHI, Region &R,
Michael Krused868b5d2015-09-10 15:25:24 +00003165 Region *NonAffineSubRegion, bool IsExitBlock) {
Michael Kruse7bf39442015-09-10 12:46:52 +00003166
3167 // PHI nodes that are in the exit block of the region, hence if IsExitBlock is
3168 // true, are not modeled as ordinary PHI nodes as they are not part of the
3169 // region. However, we model the operands in the predecessor blocks that are
3170 // part of the region as regular scalar accesses.
3171
3172 // If we can synthesize a PHI we can skip it, however only if it is in
3173 // the region. If it is not it can only be in the exit block of the region.
3174 // In this case we model the operands but not the PHI itself.
3175 if (!IsExitBlock && canSynthesize(PHI, LI, SE, &R))
3176 return;
3177
3178 // PHI nodes are modeled as if they had been demoted prior to the SCoP
3179 // detection. Hence, the PHI is a load of a new memory location in which the
3180 // incoming value was written at the end of the incoming basic block.
3181 bool OnlyNonAffineSubRegionOperands = true;
3182 for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) {
3183 Value *Op = PHI->getIncomingValue(u);
3184 BasicBlock *OpBB = PHI->getIncomingBlock(u);
3185
3186 // Do not build scalar dependences inside a non-affine subregion.
3187 if (NonAffineSubRegion && NonAffineSubRegion->contains(OpBB))
3188 continue;
3189
3190 OnlyNonAffineSubRegionOperands = false;
3191
3192 if (!R.contains(OpBB))
3193 continue;
3194
3195 Instruction *OpI = dyn_cast<Instruction>(Op);
3196 if (OpI) {
3197 BasicBlock *OpIBB = OpI->getParent();
3198 // As we pretend there is a use (or more precise a write) of OpI in OpBB
3199 // we have to insert a scalar dependence from the definition of OpI to
3200 // OpBB if the definition is not in OpBB.
3201 if (OpIBB != OpBB) {
Michael Kruse33d6c0b2015-09-25 18:53:27 +00003202 addScalarReadAccess(OpI, PHI, OpBB);
3203 addScalarWriteAccess(OpI);
Michael Kruse7bf39442015-09-10 12:46:52 +00003204 }
Tobias Grosserda95a4a2015-09-24 20:59:59 +00003205 } else if (ModelReadOnlyScalars && !isa<Constant>(Op)) {
Michael Kruse33d6c0b2015-09-25 18:53:27 +00003206 addScalarReadAccess(Op, PHI, OpBB);
Michael Kruse7bf39442015-09-10 12:46:52 +00003207 }
3208
Michael Kruse33d6c0b2015-09-25 18:53:27 +00003209 addPHIWriteAccess(PHI, OpBB, Op, IsExitBlock);
Michael Kruse7bf39442015-09-10 12:46:52 +00003210 }
3211
Michael Kruse33d6c0b2015-09-25 18:53:27 +00003212 if (!OnlyNonAffineSubRegionOperands && !IsExitBlock) {
3213 addPHIReadAccess(PHI);
Michael Kruse7bf39442015-09-10 12:46:52 +00003214 }
3215}
3216
Michael Krused868b5d2015-09-10 15:25:24 +00003217bool ScopInfo::buildScalarDependences(Instruction *Inst, Region *R,
3218 Region *NonAffineSubRegion) {
Michael Kruse7bf39442015-09-10 12:46:52 +00003219 bool canSynthesizeInst = canSynthesize(Inst, LI, SE, R);
3220 if (isIgnoredIntrinsic(Inst))
3221 return false;
3222
3223 bool AnyCrossStmtUse = false;
3224 BasicBlock *ParentBB = Inst->getParent();
3225
3226 for (User *U : Inst->users()) {
3227 Instruction *UI = dyn_cast<Instruction>(U);
3228
3229 // Ignore the strange user
3230 if (UI == 0)
3231 continue;
3232
3233 BasicBlock *UseParent = UI->getParent();
3234
3235 // Ignore the users in the same BB (statement)
3236 if (UseParent == ParentBB)
3237 continue;
3238
3239 // Do not build scalar dependences inside a non-affine subregion.
3240 if (NonAffineSubRegion && NonAffineSubRegion->contains(UseParent))
3241 continue;
3242
3243 // Check whether or not the use is in the SCoP.
3244 if (!R->contains(UseParent)) {
3245 AnyCrossStmtUse = true;
3246 continue;
3247 }
3248
3249 // If the instruction can be synthesized and the user is in the region
3250 // we do not need to add scalar dependences.
3251 if (canSynthesizeInst)
3252 continue;
3253
3254 // No need to translate these scalar dependences into polyhedral form,
3255 // because synthesizable scalars can be generated by the code generator.
3256 if (canSynthesize(UI, LI, SE, R))
3257 continue;
3258
3259 // Skip PHI nodes in the region as they handle their operands on their own.
3260 if (isa<PHINode>(UI))
3261 continue;
3262
3263 // Now U is used in another statement.
3264 AnyCrossStmtUse = true;
3265
3266 // Do not build a read access that is not in the current SCoP
Michael Krusee2bccbb2015-09-18 19:59:43 +00003267 // Use the def instruction as base address of the MemoryAccess, so that it
3268 // will become the name of the scalar access in the polyhedral form.
Michael Kruse33d6c0b2015-09-25 18:53:27 +00003269 addScalarReadAccess(Inst, UI);
Michael Kruse7bf39442015-09-10 12:46:52 +00003270 }
3271
Tobias Grosserda95a4a2015-09-24 20:59:59 +00003272 if (ModelReadOnlyScalars && !isa<PHINode>(Inst)) {
Michael Kruse7bf39442015-09-10 12:46:52 +00003273 for (Value *Op : Inst->operands()) {
3274 if (canSynthesize(Op, LI, SE, R))
3275 continue;
3276
3277 if (Instruction *OpInst = dyn_cast<Instruction>(Op))
3278 if (R->contains(OpInst))
3279 continue;
3280
3281 if (isa<Constant>(Op))
3282 continue;
3283
Michael Kruse33d6c0b2015-09-25 18:53:27 +00003284 addScalarReadAccess(Op, Inst);
Michael Kruse7bf39442015-09-10 12:46:52 +00003285 }
3286 }
3287
3288 return AnyCrossStmtUse;
3289}
3290
3291extern MapInsnToMemAcc InsnToMemAcc;
3292
Michael Krusee2bccbb2015-09-18 19:59:43 +00003293void ScopInfo::buildMemoryAccess(
3294 Instruction *Inst, Loop *L, Region *R,
Johannes Doerfert09e36972015-10-07 20:17:36 +00003295 const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
3296 const InvariantLoadsSetTy &ScopRIL) {
Michael Kruse7bf39442015-09-10 12:46:52 +00003297 unsigned Size;
3298 Type *SizeType;
3299 Value *Val;
Michael Krusee2bccbb2015-09-18 19:59:43 +00003300 enum MemoryAccess::AccessType Type;
Michael Kruse7bf39442015-09-10 12:46:52 +00003301
3302 if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
3303 SizeType = Load->getType();
3304 Size = TD->getTypeStoreSize(SizeType);
Michael Krusee2bccbb2015-09-18 19:59:43 +00003305 Type = MemoryAccess::READ;
Michael Kruse7bf39442015-09-10 12:46:52 +00003306 Val = Load;
3307 } else {
3308 StoreInst *Store = cast<StoreInst>(Inst);
3309 SizeType = Store->getValueOperand()->getType();
3310 Size = TD->getTypeStoreSize(SizeType);
Michael Krusee2bccbb2015-09-18 19:59:43 +00003311 Type = MemoryAccess::MUST_WRITE;
Michael Kruse7bf39442015-09-10 12:46:52 +00003312 Val = Store->getValueOperand();
3313 }
3314
Tobias Grosser5fd8c092015-09-17 17:28:15 +00003315 auto Address = getPointerOperand(*Inst);
3316
3317 const SCEV *AccessFunction = SE->getSCEVAtScope(Address, L);
Michael Kruse7bf39442015-09-10 12:46:52 +00003318 const SCEVUnknown *BasePointer =
3319 dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction));
3320
3321 assert(BasePointer && "Could not find base pointer");
3322 AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer);
3323
Tobias Grosser6f36d9a2015-09-17 20:16:21 +00003324 if (isa<GetElementPtrInst>(Address) || isa<BitCastInst>(Address)) {
3325 auto NewAddress = Address;
3326 if (auto *BitCast = dyn_cast<BitCastInst>(Address)) {
3327 auto Src = BitCast->getOperand(0);
3328 auto SrcTy = Src->getType();
3329 auto DstTy = BitCast->getType();
3330 if (SrcTy->getPrimitiveSizeInBits() == DstTy->getPrimitiveSizeInBits())
3331 NewAddress = Src;
3332 }
Tobias Grosser5fd8c092015-09-17 17:28:15 +00003333
Tobias Grosser6f36d9a2015-09-17 20:16:21 +00003334 if (auto *GEP = dyn_cast<GetElementPtrInst>(NewAddress)) {
3335 std::vector<const SCEV *> Subscripts;
3336 std::vector<int> Sizes;
3337 std::tie(Subscripts, Sizes) = getIndexExpressionsFromGEP(GEP, *SE);
3338 auto BasePtr = GEP->getOperand(0);
Tobias Grosser5fd8c092015-09-17 17:28:15 +00003339
Tobias Grosser6f36d9a2015-09-17 20:16:21 +00003340 std::vector<const SCEV *> SizesSCEV;
Tobias Grosser5fd8c092015-09-17 17:28:15 +00003341
Tobias Grosser6f36d9a2015-09-17 20:16:21 +00003342 bool AllAffineSubcripts = true;
Johannes Doerfert09e36972015-10-07 20:17:36 +00003343 for (auto Subscript : Subscripts) {
3344 InvariantLoadsSetTy AccessILS;
3345 AllAffineSubcripts =
3346 isAffineExpr(R, Subscript, *SE, nullptr, &AccessILS);
3347
3348 for (LoadInst *LInst : AccessILS)
3349 if (!ScopRIL.count(LInst))
3350 AllAffineSubcripts = false;
3351
3352 if (!AllAffineSubcripts)
Tobias Grosser6f36d9a2015-09-17 20:16:21 +00003353 break;
Johannes Doerfert09e36972015-10-07 20:17:36 +00003354 }
Tobias Grosser6f36d9a2015-09-17 20:16:21 +00003355
3356 if (AllAffineSubcripts && Sizes.size() > 0) {
3357 for (auto V : Sizes)
3358 SizesSCEV.push_back(SE->getSCEV(ConstantInt::get(
3359 IntegerType::getInt64Ty(BasePtr->getContext()), V)));
Tobias Grosser5fd8c092015-09-17 17:28:15 +00003360 SizesSCEV.push_back(SE->getSCEV(ConstantInt::get(
Tobias Grosser6f36d9a2015-09-17 20:16:21 +00003361 IntegerType::getInt64Ty(BasePtr->getContext()), Size)));
Tobias Grosser5fd8c092015-09-17 17:28:15 +00003362
Michael Kruse33d6c0b2015-09-25 18:53:27 +00003363 addExplicitAccess(Inst, Type, BasePointer->getValue(), Size, true,
3364 Subscripts, SizesSCEV, Val);
Tobias Grosserb1c39422015-09-21 16:19:25 +00003365 return;
Tobias Grosser6f36d9a2015-09-17 20:16:21 +00003366 }
Tobias Grosser5fd8c092015-09-17 17:28:15 +00003367 }
3368 }
3369
Michael Kruse7bf39442015-09-10 12:46:52 +00003370 auto AccItr = InsnToMemAcc.find(Inst);
Michael Krusee2bccbb2015-09-18 19:59:43 +00003371 if (PollyDelinearize && AccItr != InsnToMemAcc.end()) {
Michael Kruse33d6c0b2015-09-25 18:53:27 +00003372 addExplicitAccess(Inst, Type, BasePointer->getValue(), Size, true,
3373 AccItr->second.DelinearizedSubscripts,
3374 AccItr->second.Shape->DelinearizedSizes, Val);
Michael Krusee2bccbb2015-09-18 19:59:43 +00003375 return;
3376 }
Michael Kruse7bf39442015-09-10 12:46:52 +00003377
3378 // Check if the access depends on a loop contained in a non-affine subregion.
3379 bool isVariantInNonAffineLoop = false;
3380 if (BoxedLoops) {
3381 SetVector<const Loop *> Loops;
3382 findLoops(AccessFunction, Loops);
3383 for (const Loop *L : Loops)
3384 if (BoxedLoops->count(L))
3385 isVariantInNonAffineLoop = true;
3386 }
3387
Johannes Doerfert09e36972015-10-07 20:17:36 +00003388 InvariantLoadsSetTy AccessILS;
3389 bool IsAffine =
3390 !isVariantInNonAffineLoop &&
3391 isAffineExpr(R, AccessFunction, *SE, BasePointer->getValue(), &AccessILS);
3392
3393 for (LoadInst *LInst : AccessILS)
3394 if (!ScopRIL.count(LInst))
3395 IsAffine = false;
Michael Kruse7bf39442015-09-10 12:46:52 +00003396
Michael Krusecaac2b62015-09-26 15:51:44 +00003397 // FIXME: Size of the number of bytes of an array element, not the number of
Michael Kruse33d6c0b2015-09-25 18:53:27 +00003398 // elements as probably intended here.
Tobias Grossera43b6e92015-09-27 17:54:50 +00003399 const SCEV *SizeSCEV =
3400 SE->getConstant(TD->getIntPtrType(Inst->getContext()), Size);
Michael Kruse7bf39442015-09-10 12:46:52 +00003401
Michael Krusee2bccbb2015-09-18 19:59:43 +00003402 if (!IsAffine && Type == MemoryAccess::MUST_WRITE)
3403 Type = MemoryAccess::MAY_WRITE;
Michael Kruse7bf39442015-09-10 12:46:52 +00003404
Michael Kruse33d6c0b2015-09-25 18:53:27 +00003405 addExplicitAccess(Inst, Type, BasePointer->getValue(), Size, IsAffine,
3406 ArrayRef<const SCEV *>(AccessFunction),
3407 ArrayRef<const SCEV *>(SizeSCEV), Val);
Michael Kruse7bf39442015-09-10 12:46:52 +00003408}
3409
Michael Krused868b5d2015-09-10 15:25:24 +00003410void ScopInfo::buildAccessFunctions(Region &R, Region &SR) {
Michael Kruse7bf39442015-09-10 12:46:52 +00003411
3412 if (SD->isNonAffineSubRegion(&SR, &R)) {
3413 for (BasicBlock *BB : SR.blocks())
3414 buildAccessFunctions(R, *BB, &SR);
3415 return;
3416 }
3417
3418 for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
3419 if (I->isSubRegion())
3420 buildAccessFunctions(R, *I->getNodeAs<Region>());
3421 else
3422 buildAccessFunctions(R, *I->getNodeAs<BasicBlock>());
3423}
3424
Michael Krusecac948e2015-10-02 13:53:07 +00003425void ScopInfo::buildStmts(Region &SR) {
3426 Region *R = getRegion();
3427
3428 if (SD->isNonAffineSubRegion(&SR, R)) {
3429 scop->addScopStmt(nullptr, &SR);
3430 return;
3431 }
3432
3433 for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
3434 if (I->isSubRegion())
3435 buildStmts(*I->getNodeAs<Region>());
3436 else
3437 scop->addScopStmt(I->getNodeAs<BasicBlock>(), nullptr);
3438}
3439
Michael Krused868b5d2015-09-10 15:25:24 +00003440void ScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB,
3441 Region *NonAffineSubRegion,
3442 bool IsExitBlock) {
Michael Kruse7bf39442015-09-10 12:46:52 +00003443 Loop *L = LI->getLoopFor(&BB);
3444
3445 // The set of loops contained in non-affine subregions that are part of R.
3446 const ScopDetection::BoxedLoopsSetTy *BoxedLoops = SD->getBoxedLoops(&R);
3447
Johannes Doerfert09e36972015-10-07 20:17:36 +00003448 // The set of loads that are required to be invariant.
3449 auto &ScopRIL = *SD->getRequiredInvariantLoads(&R);
3450
Michael Kruse7bf39442015-09-10 12:46:52 +00003451 for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) {
3452 Instruction *Inst = I;
3453
3454 PHINode *PHI = dyn_cast<PHINode>(Inst);
3455 if (PHI)
Michael Krusee2bccbb2015-09-18 19:59:43 +00003456 buildPHIAccesses(PHI, R, NonAffineSubRegion, IsExitBlock);
Michael Kruse7bf39442015-09-10 12:46:52 +00003457
3458 // For the exit block we stop modeling after the last PHI node.
3459 if (!PHI && IsExitBlock)
3460 break;
3461
Johannes Doerfert09e36972015-10-07 20:17:36 +00003462 // TODO: At this point we only know that elements of ScopRIL have to be
3463 // invariant and will be hoisted for the SCoP to be processed. Though,
3464 // there might be other invariant accesses that will be hoisted and
3465 // that would allow to make a non-affine access affine.
Michael Kruse7bf39442015-09-10 12:46:52 +00003466 if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst))
Johannes Doerfert09e36972015-10-07 20:17:36 +00003467 buildMemoryAccess(Inst, L, &R, BoxedLoops, ScopRIL);
Michael Kruse7bf39442015-09-10 12:46:52 +00003468
3469 if (isIgnoredIntrinsic(Inst))
3470 continue;
3471
Johannes Doerfert09e36972015-10-07 20:17:36 +00003472 // Do not build scalar dependences for required invariant loads as we will
3473 // hoist them later on anyway or drop the SCoP if we cannot.
3474 if (ScopRIL.count(dyn_cast<LoadInst>(Inst)))
3475 continue;
3476
Michael Kruse7bf39442015-09-10 12:46:52 +00003477 if (buildScalarDependences(Inst, &R, NonAffineSubRegion)) {
Michael Krusee2bccbb2015-09-18 19:59:43 +00003478 if (!isa<StoreInst>(Inst))
Michael Kruse33d6c0b2015-09-25 18:53:27 +00003479 addScalarWriteAccess(Inst);
Michael Kruse7bf39442015-09-10 12:46:52 +00003480 }
3481 }
Michael Krusee2bccbb2015-09-18 19:59:43 +00003482}
Michael Kruse7bf39442015-09-10 12:46:52 +00003483
Michael Kruse2d0ece92015-09-24 11:41:21 +00003484void ScopInfo::addMemoryAccess(BasicBlock *BB, Instruction *Inst,
3485 MemoryAccess::AccessType Type,
3486 Value *BaseAddress, unsigned ElemBytes,
3487 bool Affine, Value *AccessValue,
3488 ArrayRef<const SCEV *> Subscripts,
Michael Kruse8d0b7342015-09-25 21:21:00 +00003489 ArrayRef<const SCEV *> Sizes,
3490 MemoryAccess::AccessOrigin Origin) {
Michael Krusecac948e2015-10-02 13:53:07 +00003491 ScopStmt *Stmt = scop->getStmtForBasicBlock(BB);
3492
3493 // Do not create a memory access for anything not in the SCoP. It would be
3494 // ignored anyway.
3495 if (!Stmt)
3496 return;
3497
Michael Krusee2bccbb2015-09-18 19:59:43 +00003498 AccFuncSetType &AccList = AccFuncMap[BB];
3499 size_t Identifier = AccList.size();
Michael Kruse7bf39442015-09-10 12:46:52 +00003500
Michael Krusee2bccbb2015-09-18 19:59:43 +00003501 Value *BaseAddr = BaseAddress;
3502 std::string BaseName = getIslCompatibleName("MemRef_", BaseAddr, "");
3503
3504 std::string IdName = "__polly_array_ref_" + std::to_string(Identifier);
3505 isl_id *Id = isl_id_alloc(ctx, IdName.c_str(), nullptr);
3506
Michael Krusecac948e2015-10-02 13:53:07 +00003507 bool isApproximated =
3508 Stmt->isRegionStmt() && (Stmt->getRegion()->getEntry() != BB);
3509 if (isApproximated && Type == MemoryAccess::MUST_WRITE)
3510 Type = MemoryAccess::MAY_WRITE;
3511
3512 AccList.emplace_back(Stmt, Inst, Id, Type, BaseAddress, ElemBytes, Affine,
Michael Kruse8d0b7342015-09-25 21:21:00 +00003513 Subscripts, Sizes, AccessValue, Origin, BaseName);
Michael Krusecac948e2015-10-02 13:53:07 +00003514 Stmt->addAccess(&AccList.back());
Michael Kruse7bf39442015-09-10 12:46:52 +00003515}
3516
Michael Kruse33d6c0b2015-09-25 18:53:27 +00003517void ScopInfo::addExplicitAccess(
3518 Instruction *MemAccInst, MemoryAccess::AccessType Type, Value *BaseAddress,
3519 unsigned ElemBytes, bool IsAffine, ArrayRef<const SCEV *> Subscripts,
3520 ArrayRef<const SCEV *> Sizes, Value *AccessValue) {
3521 assert(isa<LoadInst>(MemAccInst) || isa<StoreInst>(MemAccInst));
3522 assert(isa<LoadInst>(MemAccInst) == (Type == MemoryAccess::READ));
3523 addMemoryAccess(MemAccInst->getParent(), MemAccInst, Type, BaseAddress,
Michael Kruse8d0b7342015-09-25 21:21:00 +00003524 ElemBytes, IsAffine, AccessValue, Subscripts, Sizes,
3525 MemoryAccess::EXPLICIT);
Michael Kruse33d6c0b2015-09-25 18:53:27 +00003526}
3527void ScopInfo::addScalarWriteAccess(Instruction *Value) {
3528 addMemoryAccess(Value->getParent(), Value, MemoryAccess::MUST_WRITE, Value, 1,
3529 true, Value, ArrayRef<const SCEV *>(),
Michael Kruse8d0b7342015-09-25 21:21:00 +00003530 ArrayRef<const SCEV *>(), MemoryAccess::SCALAR);
Michael Kruse33d6c0b2015-09-25 18:53:27 +00003531}
3532void ScopInfo::addScalarReadAccess(Value *Value, Instruction *User) {
3533 assert(!isa<PHINode>(User));
3534 addMemoryAccess(User->getParent(), User, MemoryAccess::READ, Value, 1, true,
3535 Value, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
Michael Kruse8d0b7342015-09-25 21:21:00 +00003536 MemoryAccess::SCALAR);
Michael Kruse33d6c0b2015-09-25 18:53:27 +00003537}
3538void ScopInfo::addScalarReadAccess(Value *Value, PHINode *User,
3539 BasicBlock *UserBB) {
3540 addMemoryAccess(UserBB, User, MemoryAccess::READ, Value, 1, true, Value,
Michael Kruse8d0b7342015-09-25 21:21:00 +00003541 ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
3542 MemoryAccess::SCALAR);
Michael Kruse33d6c0b2015-09-25 18:53:27 +00003543}
3544void ScopInfo::addPHIWriteAccess(PHINode *PHI, BasicBlock *IncomingBlock,
3545 Value *IncomingValue, bool IsExitBlock) {
3546 addMemoryAccess(IncomingBlock, IncomingBlock->getTerminator(),
3547 MemoryAccess::MUST_WRITE, PHI, 1, true, IncomingValue,
3548 ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
Michael Kruse8d0b7342015-09-25 21:21:00 +00003549 IsExitBlock ? MemoryAccess::SCALAR : MemoryAccess::PHI);
Michael Kruse33d6c0b2015-09-25 18:53:27 +00003550}
3551void ScopInfo::addPHIReadAccess(PHINode *PHI) {
3552 addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true, PHI,
Michael Kruse8d0b7342015-09-25 21:21:00 +00003553 ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
3554 MemoryAccess::PHI);
Michael Kruse33d6c0b2015-09-25 18:53:27 +00003555}
3556
Michael Kruse76e924d2015-09-30 09:16:07 +00003557void ScopInfo::buildScop(Region &R, DominatorTree &DT) {
Michael Kruse9d080092015-09-11 21:41:48 +00003558 unsigned MaxLoopDepth = getMaxLoopDepthInRegion(R, *LI, *SD);
Johannes Doerfertd8dd8632015-10-07 20:31:36 +00003559 scop = new Scop(R, AccFuncMap, *SD, *SE, DT, *LI, ctx, MaxLoopDepth);
Michael Kruse7bf39442015-09-10 12:46:52 +00003560
Michael Krusecac948e2015-10-02 13:53:07 +00003561 buildStmts(R);
Michael Kruse7bf39442015-09-10 12:46:52 +00003562 buildAccessFunctions(R, R);
3563
3564 // In case the region does not have an exiting block we will later (during
3565 // code generation) split the exit block. This will move potential PHI nodes
3566 // from the current exit block into the new region exiting block. Hence, PHI
3567 // nodes that are at this point not part of the region will be.
3568 // To handle these PHI nodes later we will now model their operands as scalar
3569 // accesses. Note that we do not model anything in the exit block if we have
3570 // an exiting block in the region, as there will not be any splitting later.
3571 if (!R.getExitingBlock())
3572 buildAccessFunctions(R, *R.getExit(), nullptr, /* IsExitBlock */ true);
3573
Johannes Doerfertd8dd8632015-10-07 20:31:36 +00003574 scop->init(*AA);
Michael Kruse7bf39442015-09-10 12:46:52 +00003575}
3576
Michael Krused868b5d2015-09-10 15:25:24 +00003577void ScopInfo::print(raw_ostream &OS, const Module *) const {
Michael Kruse9d080092015-09-11 21:41:48 +00003578 if (!scop) {
Michael Krused868b5d2015-09-10 15:25:24 +00003579 OS << "Invalid Scop!\n";
Michael Kruse9d080092015-09-11 21:41:48 +00003580 return;
3581 }
3582
Michael Kruse9d080092015-09-11 21:41:48 +00003583 scop->print(OS);
Michael Kruse7bf39442015-09-10 12:46:52 +00003584}
3585
Michael Krused868b5d2015-09-10 15:25:24 +00003586void ScopInfo::clear() {
Michael Kruse7bf39442015-09-10 12:46:52 +00003587 AccFuncMap.clear();
Michael Krused868b5d2015-09-10 15:25:24 +00003588 if (scop) {
3589 delete scop;
3590 scop = 0;
3591 }
Michael Kruse7bf39442015-09-10 12:46:52 +00003592}
3593
3594//===----------------------------------------------------------------------===//
Michael Kruse9d080092015-09-11 21:41:48 +00003595ScopInfo::ScopInfo() : RegionPass(ID), scop(0) {
Tobias Grosserb76f38532011-08-20 11:11:25 +00003596 ctx = isl_ctx_alloc();
Tobias Grosser4a8e3562011-12-07 07:42:51 +00003597 isl_options_set_on_error(ctx, ISL_ON_ERROR_ABORT);
Tobias Grosserb76f38532011-08-20 11:11:25 +00003598}
3599
3600ScopInfo::~ScopInfo() {
3601 clear();
3602 isl_ctx_free(ctx);
3603}
3604
Tobias Grosser75805372011-04-29 06:27:02 +00003605void ScopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
Michael Krused868b5d2015-09-10 15:25:24 +00003606 AU.addRequiredID(IndependentBlocksID);
Chandler Carruthf5579872015-01-17 14:16:56 +00003607 AU.addRequired<LoopInfoWrapperPass>();
Matt Arsenault8ca36812014-07-19 18:40:17 +00003608 AU.addRequired<RegionInfoPass>();
Johannes Doerfert96425c22015-08-30 21:13:53 +00003609 AU.addRequired<DominatorTreeWrapperPass>();
Michael Krused868b5d2015-09-10 15:25:24 +00003610 AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
3611 AU.addRequiredTransitive<ScopDetection>();
Chandler Carruth66ef16b2015-09-09 22:13:56 +00003612 AU.addRequired<AAResultsWrapperPass>();
Tobias Grosser75805372011-04-29 06:27:02 +00003613 AU.setPreservesAll();
3614}
3615
3616bool ScopInfo::runOnRegion(Region *R, RGPassManager &RGM) {
Michael Krused868b5d2015-09-10 15:25:24 +00003617 SD = &getAnalysis<ScopDetection>();
Tobias Grosser75805372011-04-29 06:27:02 +00003618
Michael Krused868b5d2015-09-10 15:25:24 +00003619 if (!SD->isMaxRegionInScop(*R))
3620 return false;
3621
3622 Function *F = R->getEntry()->getParent();
3623 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
3624 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
3625 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
3626 TD = &F->getParent()->getDataLayout();
3627 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
Michael Krused868b5d2015-09-10 15:25:24 +00003628
Michael Kruse76e924d2015-09-30 09:16:07 +00003629 buildScop(*R, DT);
Tobias Grosser75805372011-04-29 06:27:02 +00003630
Tobias Grosserd6a50b32015-05-30 06:26:21 +00003631 DEBUG(scop->print(dbgs()));
3632
Michael Kruseafe06702015-10-02 16:33:27 +00003633 if (scop->isEmpty() || !scop->hasFeasibleRuntimeContext()) {
Johannes Doerfert43788c52015-08-20 05:58:56 +00003634 delete scop;
3635 scop = nullptr;
3636 return false;
3637 }
3638
Johannes Doerfert120de4b2015-08-20 18:30:08 +00003639 // Statistics.
3640 ++ScopFound;
3641 if (scop->getMaxLoopDepth() > 0)
3642 ++RichScopFound;
Tobias Grosser75805372011-04-29 06:27:02 +00003643 return false;
3644}
3645
3646char ScopInfo::ID = 0;
3647
Tobias Grosser4d96c8d2013-03-23 01:05:07 +00003648Pass *polly::createScopInfoPass() { return new ScopInfo(); }
3649
Tobias Grosser73600b82011-10-08 00:30:40 +00003650INITIALIZE_PASS_BEGIN(ScopInfo, "polly-scops",
3651 "Polly - Create polyhedral description of Scops", false,
Tobias Grosser4d96c8d2013-03-23 01:05:07 +00003652 false);
Chandler Carruth66ef16b2015-09-09 22:13:56 +00003653INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass);
Chandler Carruthf5579872015-01-17 14:16:56 +00003654INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
Matt Arsenault8ca36812014-07-19 18:40:17 +00003655INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
Tobias Grosserc5bcf242015-08-17 10:57:08 +00003656INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
Johannes Doerfertff9d1982015-02-24 12:00:50 +00003657INITIALIZE_PASS_DEPENDENCY(ScopDetection);
Johannes Doerfert96425c22015-08-30 21:13:53 +00003658INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
Tobias Grosser73600b82011-10-08 00:30:40 +00003659INITIALIZE_PASS_END(ScopInfo, "polly-scops",
3660 "Polly - Create polyhedral description of Scops", false,
3661 false)