blob: 0a62efddd6e20fd6fb53286e518c8045c0a4e2ba [file] [log] [blame]
Tobias Grosser75805372011-04-29 06:27:02 +00001//===--------- ScopInfo.cpp - Create Scops from LLVM IR ------------------===//
2//
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"
Sebastian Pop27c10c62013-03-22 22:07:43 +000021#include "polly/ScopInfo.h"
Johannes Doerfert0ee1f212014-06-17 17:31:36 +000022#include "polly/Options.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"
Sebastian Pop27c10c62013-03-22 22:07:43 +000026#include "polly/TempScopInfo.h"
Tobias Grosser75805372011-04-29 06:27:02 +000027#include "llvm/ADT/SetVector.h"
Tobias Grosser83628182013-05-07 08:11:54 +000028#include "llvm/ADT/Statistic.h"
Hongbin Zheng86a37742012-04-25 08:01:38 +000029#include "llvm/ADT/StringExtras.h"
Tobias Grosser83628182013-05-07 08:11:54 +000030#include "llvm/Analysis/LoopInfo.h"
Johannes Doerfertb164c792014-09-18 11:17:17 +000031#include "llvm/Analysis/AliasAnalysis.h"
Tobias Grosser83628182013-05-07 08:11:54 +000032#include "llvm/Analysis/RegionIterator.h"
33#include "llvm/Analysis/ScalarEvolutionExpressions.h"
Tobias Grosser75805372011-04-29 06:27:02 +000034#include "llvm/Support/Debug.h"
35
36#include "isl/constraint.h"
37#include "isl/set.h"
38#include "isl/map.h"
Tobias Grosser37eb4222014-02-20 21:43:54 +000039#include "isl/union_map.h"
Tobias Grosser33ba62ad2011-08-18 06:31:50 +000040#include "isl/aff.h"
41#include "isl/printer.h"
Tobias Grosserf5338802011-10-06 00:03:35 +000042#include "isl/local_space.h"
Tobias Grosser4a8e3562011-12-07 07:42:51 +000043#include "isl/options.h"
Tobias Grosseredab1352013-06-21 06:41:31 +000044#include "isl/val.h"
Chandler Carruth95fef942014-04-22 03:30:19 +000045
Tobias Grosser75805372011-04-29 06:27:02 +000046#include <sstream>
47#include <string>
48#include <vector>
49
50using namespace llvm;
51using namespace polly;
52
Chandler Carruth95fef942014-04-22 03:30:19 +000053#define DEBUG_TYPE "polly-scops"
54
Tobias Grosser74394f02013-01-14 22:40:23 +000055STATISTIC(ScopFound, "Number of valid Scops");
56STATISTIC(RichScopFound, "Number of Scops containing a loop");
Tobias Grosser75805372011-04-29 06:27:02 +000057
Johannes Doerfert9e7b17b2014-08-18 00:40:13 +000058// Multiplicative reductions can be disabled separately as these kind of
Johannes Doerfert0ee1f212014-06-17 17:31:36 +000059// operations can overflow easily. Additive reductions and bit operations
60// are in contrast pretty stable.
Tobias Grosser483a90d2014-07-09 10:50:10 +000061static cl::opt<bool> DisableMultiplicativeReductions(
62 "polly-disable-multiplicative-reductions",
63 cl::desc("Disable multiplicative reductions"), cl::Hidden, cl::ZeroOrMore,
64 cl::init(false), cl::cat(PollyCategory));
Johannes Doerfert0ee1f212014-06-17 17:31:36 +000065
Johannes Doerfert9143d672014-09-27 11:02:39 +000066static cl::opt<unsigned> RunTimeChecksMaxParameters(
67 "polly-rtc-max-parameters",
68 cl::desc("The maximal number of parameters allowed in RTCs."), cl::Hidden,
69 cl::ZeroOrMore, cl::init(8), cl::cat(PollyCategory));
70
Tobias Grosser71500722015-03-28 15:11:14 +000071static cl::opt<unsigned> RunTimeChecksMaxArraysPerGroup(
72 "polly-rtc-max-arrays-per-group",
73 cl::desc("The maximal number of arrays to compare in each alias group."),
74 cl::Hidden, cl::ZeroOrMore, cl::init(20), cl::cat(PollyCategory));
75
Tobias Grosser0695ee42013-09-17 03:30:31 +000076/// Translate a 'const SCEV *' expression in an isl_pw_aff.
Tobias Grosserabfbe632013-02-05 12:09:06 +000077struct SCEVAffinator : public SCEVVisitor<SCEVAffinator, isl_pw_aff *> {
Tobias Grosser0695ee42013-09-17 03:30:31 +000078public:
Tobias Grosser0695ee42013-09-17 03:30:31 +000079 /// @brief Translate a 'const SCEV *' to an isl_pw_aff.
80 ///
81 /// @param Stmt The location at which the scalar evolution expression
82 /// is evaluated.
83 /// @param Expr The expression that is translated.
84 static __isl_give isl_pw_aff *getPwAff(ScopStmt *Stmt, const SCEV *Expr);
85
Tobias Grosser33ba62ad2011-08-18 06:31:50 +000086private:
Tobias Grosser3cc99742012-06-06 16:33:15 +000087 isl_ctx *Ctx;
Tobias Grosserf5338802011-10-06 00:03:35 +000088 int NbLoopSpaces;
Tobias Grosser3cc99742012-06-06 16:33:15 +000089 const Scop *S;
Tobias Grosser33ba62ad2011-08-18 06:31:50 +000090
Tobias Grosser0695ee42013-09-17 03:30:31 +000091 SCEVAffinator(const ScopStmt *Stmt);
92 int getLoopDepth(const Loop *L);
Tobias Grosser60b54f12011-11-08 15:41:28 +000093
Tobias Grosser0695ee42013-09-17 03:30:31 +000094 __isl_give isl_pw_aff *visit(const SCEV *Expr);
95 __isl_give isl_pw_aff *visitConstant(const SCEVConstant *Expr);
96 __isl_give isl_pw_aff *visitTruncateExpr(const SCEVTruncateExpr *Expr);
97 __isl_give isl_pw_aff *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr);
98 __isl_give isl_pw_aff *visitSignExtendExpr(const SCEVSignExtendExpr *Expr);
99 __isl_give isl_pw_aff *visitAddExpr(const SCEVAddExpr *Expr);
100 __isl_give isl_pw_aff *visitMulExpr(const SCEVMulExpr *Expr);
101 __isl_give isl_pw_aff *visitUDivExpr(const SCEVUDivExpr *Expr);
102 __isl_give isl_pw_aff *visitAddRecExpr(const SCEVAddRecExpr *Expr);
103 __isl_give isl_pw_aff *visitSMaxExpr(const SCEVSMaxExpr *Expr);
104 __isl_give isl_pw_aff *visitUMaxExpr(const SCEVUMaxExpr *Expr);
105 __isl_give isl_pw_aff *visitUnknown(const SCEVUnknown *Expr);
Johannes Doerfertb9d18882015-02-11 14:54:50 +0000106 __isl_give isl_pw_aff *visitSDivInstruction(Instruction *SDiv);
Tobias Grosser60b54f12011-11-08 15:41:28 +0000107
Tobias Grosser0695ee42013-09-17 03:30:31 +0000108 friend struct SCEVVisitor<SCEVAffinator, isl_pw_aff *>;
109};
Tobias Grosser33ba62ad2011-08-18 06:31:50 +0000110
Tobias Grosser0695ee42013-09-17 03:30:31 +0000111SCEVAffinator::SCEVAffinator(const ScopStmt *Stmt)
112 : Ctx(Stmt->getIslCtx()), NbLoopSpaces(Stmt->getNumIterators()),
113 S(Stmt->getParent()) {}
Tobias Grosser33ba62ad2011-08-18 06:31:50 +0000114
Tobias Grosser0695ee42013-09-17 03:30:31 +0000115__isl_give isl_pw_aff *SCEVAffinator::getPwAff(ScopStmt *Stmt,
116 const SCEV *Scev) {
117 Scop *S = Stmt->getParent();
118 const Region *Reg = &S->getRegion();
Tobias Grosser33ba62ad2011-08-18 06:31:50 +0000119
Tobias Grosser0695ee42013-09-17 03:30:31 +0000120 S->addParams(getParamsInAffineExpr(Reg, Scev, *S->getSE()));
Tobias Grosser33ba62ad2011-08-18 06:31:50 +0000121
Tobias Grosser0695ee42013-09-17 03:30:31 +0000122 SCEVAffinator Affinator(Stmt);
123 return Affinator.visit(Scev);
124}
Tobias Grosser33ba62ad2011-08-18 06:31:50 +0000125
Tobias Grosser0695ee42013-09-17 03:30:31 +0000126__isl_give isl_pw_aff *SCEVAffinator::visit(const SCEV *Expr) {
127 // In case the scev is a valid parameter, we do not further analyze this
128 // expression, but create a new parameter in the isl_pw_aff. This allows us
129 // to treat subexpressions that we cannot translate into an piecewise affine
130 // expression, as constant parameters of the piecewise affine expression.
131 if (isl_id *Id = S->getIdForParam(Expr)) {
132 isl_space *Space = isl_space_set_alloc(Ctx, 1, NbLoopSpaces);
133 Space = isl_space_set_dim_id(Space, isl_dim_param, 0, Id);
Tobias Grosser33ba62ad2011-08-18 06:31:50 +0000134
Tobias Grosser0695ee42013-09-17 03:30:31 +0000135 isl_set *Domain = isl_set_universe(isl_space_copy(Space));
136 isl_aff *Affine = isl_aff_zero_on_domain(isl_local_space_from_space(Space));
137 Affine = isl_aff_add_coefficient_si(Affine, isl_dim_param, 0, 1);
Tobias Grosser33ba62ad2011-08-18 06:31:50 +0000138
139 return isl_pw_aff_alloc(Domain, Affine);
140 }
141
Tobias Grosser0695ee42013-09-17 03:30:31 +0000142 return SCEVVisitor<SCEVAffinator, isl_pw_aff *>::visit(Expr);
143}
144
Tobias Grosser0d170132013-10-03 13:09:19 +0000145__isl_give isl_pw_aff *SCEVAffinator::visitConstant(const SCEVConstant *Expr) {
Tobias Grosser0695ee42013-09-17 03:30:31 +0000146 ConstantInt *Value = Expr->getValue();
147 isl_val *v;
148
149 // LLVM does not define if an integer value is interpreted as a signed or
150 // unsigned value. Hence, without further information, it is unknown how
151 // this value needs to be converted to GMP. At the moment, we only support
152 // signed operations. So we just interpret it as signed. Later, there are
153 // two options:
154 //
155 // 1. We always interpret any value as signed and convert the values on
156 // demand.
157 // 2. We pass down the signedness of the calculation and use it to interpret
158 // this constant correctly.
159 v = isl_valFromAPInt(Ctx, Value->getValue(), /* isSigned */ true);
160
161 isl_space *Space = isl_space_set_alloc(Ctx, 0, NbLoopSpaces);
Johannes Doerfert9c147372014-11-19 15:36:59 +0000162 isl_local_space *ls = isl_local_space_from_space(Space);
163 return isl_pw_aff_from_aff(isl_aff_val_on_domain(ls, v));
Tobias Grosser0695ee42013-09-17 03:30:31 +0000164}
165
166__isl_give isl_pw_aff *
167SCEVAffinator::visitTruncateExpr(const SCEVTruncateExpr *Expr) {
168 llvm_unreachable("SCEVTruncateExpr not yet supported");
169}
170
171__isl_give isl_pw_aff *
172SCEVAffinator::visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
173 llvm_unreachable("SCEVZeroExtendExpr not yet supported");
174}
175
176__isl_give isl_pw_aff *
177SCEVAffinator::visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
178 // Assuming the value is signed, a sign extension is basically a noop.
179 // TODO: Reconsider this as soon as we support unsigned values.
180 return visit(Expr->getOperand());
181}
182
183__isl_give isl_pw_aff *SCEVAffinator::visitAddExpr(const SCEVAddExpr *Expr) {
184 isl_pw_aff *Sum = visit(Expr->getOperand(0));
185
186 for (int i = 1, e = Expr->getNumOperands(); i < e; ++i) {
187 isl_pw_aff *NextSummand = visit(Expr->getOperand(i));
188 Sum = isl_pw_aff_add(Sum, NextSummand);
Tobias Grosser33ba62ad2011-08-18 06:31:50 +0000189 }
190
Tobias Grosser0695ee42013-09-17 03:30:31 +0000191 // TODO: Check for NSW and NUW.
Tobias Grosser33ba62ad2011-08-18 06:31:50 +0000192
Tobias Grosser0695ee42013-09-17 03:30:31 +0000193 return Sum;
194}
Tobias Grosser33ba62ad2011-08-18 06:31:50 +0000195
Tobias Grosser0695ee42013-09-17 03:30:31 +0000196__isl_give isl_pw_aff *SCEVAffinator::visitMulExpr(const SCEVMulExpr *Expr) {
197 isl_pw_aff *Product = visit(Expr->getOperand(0));
Tobias Grosser33ba62ad2011-08-18 06:31:50 +0000198
Tobias Grosser0695ee42013-09-17 03:30:31 +0000199 for (int i = 1, e = Expr->getNumOperands(); i < e; ++i) {
200 isl_pw_aff *NextOperand = visit(Expr->getOperand(i));
201
202 if (!isl_pw_aff_is_cst(Product) && !isl_pw_aff_is_cst(NextOperand)) {
203 isl_pw_aff_free(Product);
204 isl_pw_aff_free(NextOperand);
Tobias Grosser5a56cbf2014-04-16 07:33:47 +0000205 return nullptr;
Tobias Grosser33ba62ad2011-08-18 06:31:50 +0000206 }
207
Tobias Grosser0695ee42013-09-17 03:30:31 +0000208 Product = isl_pw_aff_mul(Product, NextOperand);
Tobias Grosser33ba62ad2011-08-18 06:31:50 +0000209 }
210
Tobias Grosser0695ee42013-09-17 03:30:31 +0000211 // TODO: Check for NSW and NUW.
212 return Product;
213}
Tobias Grosser33ba62ad2011-08-18 06:31:50 +0000214
Tobias Grosser0695ee42013-09-17 03:30:31 +0000215__isl_give isl_pw_aff *SCEVAffinator::visitUDivExpr(const SCEVUDivExpr *Expr) {
216 llvm_unreachable("SCEVUDivExpr not yet supported");
217}
Tobias Grosser33ba62ad2011-08-18 06:31:50 +0000218
Tobias Grosser0695ee42013-09-17 03:30:31 +0000219__isl_give isl_pw_aff *
220SCEVAffinator::visitAddRecExpr(const SCEVAddRecExpr *Expr) {
221 assert(Expr->isAffine() && "Only affine AddRecurrences allowed");
Tobias Grosser33ba62ad2011-08-18 06:31:50 +0000222
Tobias Grosser0695ee42013-09-17 03:30:31 +0000223 // Directly generate isl_pw_aff for Expr if 'start' is zero.
224 if (Expr->getStart()->isZero()) {
225 assert(S->getRegion().contains(Expr->getLoop()) &&
226 "Scop does not contain the loop referenced in this AddRec");
Tobias Grosser33ba62ad2011-08-18 06:31:50 +0000227
Tobias Grosser33ba62ad2011-08-18 06:31:50 +0000228 isl_pw_aff *Start = visit(Expr->getStart());
Tobias Grosser0695ee42013-09-17 03:30:31 +0000229 isl_pw_aff *Step = visit(Expr->getOperand(1));
230 isl_space *Space = isl_space_set_alloc(Ctx, 0, NbLoopSpaces);
231 isl_local_space *LocalSpace = isl_local_space_from_space(Space);
Tobias Grosser33ba62ad2011-08-18 06:31:50 +0000232
Tobias Grosser0695ee42013-09-17 03:30:31 +0000233 int loopDimension = getLoopDepth(Expr->getLoop());
234
235 isl_aff *LAff = isl_aff_set_coefficient_si(
236 isl_aff_zero_on_domain(LocalSpace), isl_dim_in, loopDimension, 1);
237 isl_pw_aff *LPwAff = isl_pw_aff_from_aff(LAff);
238
239 // TODO: Do we need to check for NSW and NUW?
240 return isl_pw_aff_add(Start, isl_pw_aff_mul(Step, LPwAff));
Tobias Grosser33ba62ad2011-08-18 06:31:50 +0000241 }
242
Tobias Grosser0695ee42013-09-17 03:30:31 +0000243 // Translate AddRecExpr from '{start, +, inc}' into 'start + {0, +, inc}'
244 // if 'start' is not zero.
245 ScalarEvolution &SE = *S->getSE();
246 const SCEV *ZeroStartExpr = SE.getAddRecExpr(
247 SE.getConstant(Expr->getStart()->getType(), 0),
248 Expr->getStepRecurrence(SE), Expr->getLoop(), SCEV::FlagAnyWrap);
Tobias Grosser33ba62ad2011-08-18 06:31:50 +0000249
Tobias Grosser0695ee42013-09-17 03:30:31 +0000250 isl_pw_aff *ZeroStartResult = visit(ZeroStartExpr);
251 isl_pw_aff *Start = visit(Expr->getStart());
Tobias Grosser33ba62ad2011-08-18 06:31:50 +0000252
Tobias Grosser0695ee42013-09-17 03:30:31 +0000253 return isl_pw_aff_add(ZeroStartResult, Start);
254}
255
256__isl_give isl_pw_aff *SCEVAffinator::visitSMaxExpr(const SCEVSMaxExpr *Expr) {
257 isl_pw_aff *Max = visit(Expr->getOperand(0));
258
259 for (int i = 1, e = Expr->getNumOperands(); i < e; ++i) {
260 isl_pw_aff *NextOperand = visit(Expr->getOperand(i));
261 Max = isl_pw_aff_max(Max, NextOperand);
Tobias Grosser33ba62ad2011-08-18 06:31:50 +0000262 }
263
Tobias Grosser0695ee42013-09-17 03:30:31 +0000264 return Max;
265}
Tobias Grosser33ba62ad2011-08-18 06:31:50 +0000266
Tobias Grosser0695ee42013-09-17 03:30:31 +0000267__isl_give isl_pw_aff *SCEVAffinator::visitUMaxExpr(const SCEVUMaxExpr *Expr) {
268 llvm_unreachable("SCEVUMaxExpr not yet supported");
269}
270
Johannes Doerfertb9d18882015-02-11 14:54:50 +0000271__isl_give isl_pw_aff *SCEVAffinator::visitSDivInstruction(Instruction *SDiv) {
272 assert(SDiv->getOpcode() == Instruction::SDiv && "Assumed SDiv instruction!");
273 auto *SE = S->getSE();
274
275 auto *Divisor = SDiv->getOperand(1);
276 auto *DivisorSCEV = SE->getSCEV(Divisor);
277 auto *DivisorPWA = visit(DivisorSCEV);
278 assert(isa<ConstantInt>(Divisor) &&
279 "SDiv is no parameter but has a non-constant RHS.");
280
281 auto *Dividend = SDiv->getOperand(0);
282 auto *DividendSCEV = SE->getSCEV(Dividend);
283 auto *DividendPWA = visit(DividendSCEV);
284 return isl_pw_aff_tdiv_q(DividendPWA, DivisorPWA);
285}
286
Tobias Grosser0695ee42013-09-17 03:30:31 +0000287__isl_give isl_pw_aff *SCEVAffinator::visitUnknown(const SCEVUnknown *Expr) {
Johannes Doerfertb9d18882015-02-11 14:54:50 +0000288 if (Instruction *I = dyn_cast<Instruction>(Expr->getValue())) {
289 switch (I->getOpcode()) {
290 case Instruction::SDiv:
291 return visitSDivInstruction(I);
292 default:
293 break; // Fall through.
294 }
295 }
296
297 llvm_unreachable(
298 "Unknowns SCEV was neither parameter nor a valid instruction.");
Tobias Grosser0695ee42013-09-17 03:30:31 +0000299}
300
301int SCEVAffinator::getLoopDepth(const Loop *L) {
302 Loop *outerLoop = S->getRegion().outermostLoopInRegion(const_cast<Loop *>(L));
303 assert(outerLoop && "Scop does not contain this loop");
304 return L->getLoopDepth() - outerLoop->getLoopDepth();
305}
Tobias Grosser33ba62ad2011-08-18 06:31:50 +0000306
Johannes Doerferte7044942015-02-24 11:58:30 +0000307/// @brief Add the bounds of @p Range to the set @p S for dimension @p dim.
308static __isl_give isl_set *addRangeBoundsToSet(__isl_take isl_set *S,
309 const ConstantRange &Range,
310 int dim,
311 enum isl_dim_type type) {
312 isl_val *V;
313 isl_ctx *ctx = isl_set_get_ctx(S);
314
Johannes Doerferte4bd53b2015-03-08 19:49:50 +0000315 bool isWrapping = Range.isSignWrappedSet();
316 const auto LB = isWrapping ? Range.getLower() : Range.getSignedMin();
317 V = isl_valFromAPInt(ctx, LB, true);
Johannes Doerferte7044942015-02-24 11:58:30 +0000318 isl_set *SLB = isl_set_lower_bound_val(isl_set_copy(S), type, dim, V);
319
Johannes Doerferte4bd53b2015-03-08 19:49:50 +0000320 const auto UB = isWrapping ? Range.getUpper() : Range.getSignedMax();
321 V = isl_valFromAPInt(ctx, UB, true);
322 if (isWrapping)
323 V = isl_val_sub_ui(V, 1);
Johannes Doerferte7044942015-02-24 11:58:30 +0000324 isl_set *SUB = isl_set_upper_bound_val(S, type, dim, V);
325
Johannes Doerferte4bd53b2015-03-08 19:49:50 +0000326 if (isWrapping)
Johannes Doerferte7044942015-02-24 11:58:30 +0000327 return isl_set_union(SLB, SUB);
328 else
329 return isl_set_intersect(SLB, SUB);
330}
331
Johannes Doerfert1a28a892014-10-05 11:32:18 +0000332ScopArrayInfo::ScopArrayInfo(Value *BasePtr, Type *AccessType, isl_ctx *Ctx,
333 const SmallVector<const SCEV *, 4> &DimensionSizes)
334 : BasePtr(BasePtr), AccessType(AccessType), DimensionSizes(DimensionSizes) {
335 const std::string BasePtrName = getIslCompatibleName("MemRef_", BasePtr, "");
336 Id = isl_id_alloc(Ctx, BasePtrName.c_str(), this);
337}
338
339ScopArrayInfo::~ScopArrayInfo() { isl_id_free(Id); }
340
341isl_id *ScopArrayInfo::getBasePtrId() const { return isl_id_copy(Id); }
342
343void ScopArrayInfo::dump() const { print(errs()); }
344
345void ScopArrayInfo::print(raw_ostream &OS) const {
346 OS << "ScopArrayInfo:\n";
347 OS << " Base: " << *getBasePtr() << "\n";
348 OS << " Type: " << *getType() << "\n";
349 OS << " Dimension Sizes:\n";
350 for (unsigned u = 0; u < getNumberOfDimensions(); u++)
351 OS << " " << u << ") " << *DimensionSizes[u] << "\n";
352 OS << "\n";
353}
354
355const ScopArrayInfo *
356ScopArrayInfo::getFromAccessFunction(__isl_keep isl_pw_multi_aff *PMA) {
357 isl_id *Id = isl_pw_multi_aff_get_tuple_id(PMA, isl_dim_out);
358 assert(Id && "Output dimension didn't have an ID");
359 return getFromId(Id);
360}
361
362const ScopArrayInfo *ScopArrayInfo::getFromId(isl_id *Id) {
363 void *User = isl_id_get_user(Id);
364 const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User);
365 isl_id_free(Id);
366 return SAI;
367}
368
Johannes Doerfert32868bf2014-08-01 08:13:25 +0000369const std::string
370MemoryAccess::getReductionOperatorStr(MemoryAccess::ReductionType RT) {
371 switch (RT) {
372 case MemoryAccess::RT_NONE:
373 llvm_unreachable("Requested a reduction operator string for a memory "
374 "access which isn't a reduction");
375 case MemoryAccess::RT_ADD:
376 return "+";
377 case MemoryAccess::RT_MUL:
378 return "*";
379 case MemoryAccess::RT_BOR:
380 return "|";
381 case MemoryAccess::RT_BXOR:
382 return "^";
383 case MemoryAccess::RT_BAND:
384 return "&";
385 }
386 llvm_unreachable("Unknown reduction type");
387 return "";
388}
389
Johannes Doerfertf6183392014-07-01 20:52:51 +0000390/// @brief Return the reduction type for a given binary operator
391static MemoryAccess::ReductionType getReductionType(const BinaryOperator *BinOp,
392 const Instruction *Load) {
393 if (!BinOp)
394 return MemoryAccess::RT_NONE;
395 switch (BinOp->getOpcode()) {
396 case Instruction::FAdd:
397 if (!BinOp->hasUnsafeAlgebra())
398 return MemoryAccess::RT_NONE;
399 // Fall through
400 case Instruction::Add:
401 return MemoryAccess::RT_ADD;
402 case Instruction::Or:
403 return MemoryAccess::RT_BOR;
404 case Instruction::Xor:
405 return MemoryAccess::RT_BXOR;
406 case Instruction::And:
407 return MemoryAccess::RT_BAND;
408 case Instruction::FMul:
409 if (!BinOp->hasUnsafeAlgebra())
410 return MemoryAccess::RT_NONE;
411 // Fall through
412 case Instruction::Mul:
413 if (DisableMultiplicativeReductions)
414 return MemoryAccess::RT_NONE;
415 return MemoryAccess::RT_MUL;
416 default:
417 return MemoryAccess::RT_NONE;
418 }
419}
Tobias Grosser75805372011-04-29 06:27:02 +0000420//===----------------------------------------------------------------------===//
421
422MemoryAccess::~MemoryAccess() {
Tobias Grosser54a86e62011-08-18 06:31:46 +0000423 isl_map_free(AccessRelation);
Raghesh Aloor129e8672011-08-15 02:33:39 +0000424 isl_map_free(newAccessRelation);
Tobias Grosser75805372011-04-29 06:27:02 +0000425}
426
Johannes Doerfert8f7124c2014-09-12 11:00:49 +0000427static MemoryAccess::AccessType getMemoryAccessType(const IRAccess &Access) {
428 switch (Access.getType()) {
429 case IRAccess::READ:
430 return MemoryAccess::READ;
431 case IRAccess::MUST_WRITE:
432 return MemoryAccess::MUST_WRITE;
433 case IRAccess::MAY_WRITE:
434 return MemoryAccess::MAY_WRITE;
435 }
436 llvm_unreachable("Unknown IRAccess type!");
437}
438
Johannes Doerfert1a28a892014-10-05 11:32:18 +0000439const ScopArrayInfo *MemoryAccess::getScopArrayInfo() const {
440 isl_id *ArrayId = getArrayId();
441 void *User = isl_id_get_user(ArrayId);
442 const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User);
443 isl_id_free(ArrayId);
444 return SAI;
445}
446
Johannes Doerfert5d83f092014-07-29 08:37:55 +0000447isl_id *MemoryAccess::getArrayId() const {
448 return isl_map_get_tuple_id(AccessRelation, isl_dim_out);
449}
450
Johannes Doerferta99130f2014-10-13 12:58:03 +0000451isl_pw_multi_aff *
452MemoryAccess::applyScheduleToAccessRelation(isl_union_map *USchedule) const {
453 isl_map *Schedule, *ScheduledAccRel;
454 isl_union_set *UDomain;
455
456 UDomain = isl_union_set_from_set(getStatement()->getDomain());
457 USchedule = isl_union_map_intersect_domain(USchedule, UDomain);
458 Schedule = isl_map_from_union_map(USchedule);
459 ScheduledAccRel = isl_map_apply_domain(getAccessRelation(), Schedule);
460 return isl_pw_multi_aff_from_map(ScheduledAccRel);
461}
462
463isl_map *MemoryAccess::getOriginalAccessRelation() const {
Tobias Grosser5d453812011-10-06 00:04:11 +0000464 return isl_map_copy(AccessRelation);
465}
466
Johannes Doerferta99130f2014-10-13 12:58:03 +0000467std::string MemoryAccess::getOriginalAccessRelationStr() const {
Tobias Grosser5d453812011-10-06 00:04:11 +0000468 return stringFromIslObj(AccessRelation);
469}
470
Johannes Doerferta99130f2014-10-13 12:58:03 +0000471__isl_give isl_space *MemoryAccess::getOriginalAccessRelationSpace() const {
Tobias Grosser5e6813d2014-07-02 17:47:48 +0000472 return isl_map_get_space(AccessRelation);
473}
474
Tobias Grosser5d453812011-10-06 00:04:11 +0000475isl_map *MemoryAccess::getNewAccessRelation() const {
476 return isl_map_copy(newAccessRelation);
Tobias Grosser75805372011-04-29 06:27:02 +0000477}
478
479isl_basic_map *MemoryAccess::createBasicAccessMap(ScopStmt *Statement) {
Tobias Grosser084d8f72012-05-29 09:29:44 +0000480 isl_space *Space = isl_space_set_alloc(Statement->getIslCtx(), 0, 1);
Tobias Grossered295662012-09-11 13:50:21 +0000481 Space = isl_space_align_params(Space, Statement->getDomainSpace());
Tobias Grosser75805372011-04-29 06:27:02 +0000482
Tobias Grosser084d8f72012-05-29 09:29:44 +0000483 return isl_basic_map_from_domain_and_range(
Tobias Grosserabfbe632013-02-05 12:09:06 +0000484 isl_basic_set_universe(Statement->getDomainSpace()),
485 isl_basic_set_universe(Space));
Tobias Grosser75805372011-04-29 06:27:02 +0000486}
487
Tobias Grosser5e6813d2014-07-02 17:47:48 +0000488// Formalize no out-of-bound access assumption
489//
490// When delinearizing array accesses we optimistically assume that the
491// delinearized accesses do not access out of bound locations (the subscript
492// expression of each array evaluates for each statement instance that is
493// executed to a value that is larger than zero and strictly smaller than the
494// size of the corresponding dimension). The only exception is the outermost
Tobias Grosserf57d63f2014-08-03 21:07:30 +0000495// dimension for which we do not need to assume any upper bound. At this point
496// we formalize this assumption to ensure that at code generation time the
497// relevant run-time checks can be generated.
Tobias Grosser5e6813d2014-07-02 17:47:48 +0000498//
499// To find the set of constraints necessary to avoid out of bound accesses, we
500// first build the set of data locations that are not within array bounds. We
501// then apply the reverse access relation to obtain the set of iterations that
502// may contain invalid accesses and reduce this set of iterations to the ones
503// that are actually executed by intersecting them with the domain of the
504// statement. If we now project out all loop dimensions, we obtain a set of
505// parameters that may cause statement instances to be executed that may
506// possibly yield out of bound memory accesses. The complement of these
507// constraints is the set of constraints that needs to be assumed to ensure such
508// statement instances are never executed.
509void MemoryAccess::assumeNoOutOfBound(const IRAccess &Access) {
Johannes Doerferta99130f2014-10-13 12:58:03 +0000510 isl_space *Space = isl_space_range(getOriginalAccessRelationSpace());
Tobias Grosser5e6813d2014-07-02 17:47:48 +0000511 isl_set *Outside = isl_set_empty(isl_space_copy(Space));
Tobias Grosserf57d63f2014-08-03 21:07:30 +0000512 for (int i = 1, Size = Access.Subscripts.size(); i < Size; ++i) {
Tobias Grosser5e6813d2014-07-02 17:47:48 +0000513 isl_local_space *LS = isl_local_space_from_space(isl_space_copy(Space));
514 isl_pw_aff *Var =
515 isl_pw_aff_var_on_domain(isl_local_space_copy(LS), isl_dim_set, i);
516 isl_pw_aff *Zero = isl_pw_aff_zero_on_domain(LS);
517
518 isl_set *DimOutside;
519
Tobias Grosserf57d63f2014-08-03 21:07:30 +0000520 DimOutside = isl_pw_aff_lt_set(isl_pw_aff_copy(Var), Zero);
521 isl_pw_aff *SizeE = SCEVAffinator::getPwAff(Statement, Access.Sizes[i - 1]);
Tobias Grosser5e6813d2014-07-02 17:47:48 +0000522
Tobias Grosserf57d63f2014-08-03 21:07:30 +0000523 SizeE = isl_pw_aff_drop_dims(SizeE, isl_dim_in, 0,
524 Statement->getNumIterators());
525 SizeE = isl_pw_aff_add_dims(SizeE, isl_dim_in,
526 isl_space_dim(Space, isl_dim_set));
527 SizeE = isl_pw_aff_set_tuple_id(SizeE, isl_dim_in,
528 isl_space_get_tuple_id(Space, isl_dim_set));
Tobias Grosser5e6813d2014-07-02 17:47:48 +0000529
Tobias Grosserf57d63f2014-08-03 21:07:30 +0000530 DimOutside = isl_set_union(DimOutside, isl_pw_aff_le_set(SizeE, Var));
Tobias Grosser5e6813d2014-07-02 17:47:48 +0000531
532 Outside = isl_set_union(Outside, DimOutside);
533 }
534
535 Outside = isl_set_apply(Outside, isl_map_reverse(getAccessRelation()));
536 Outside = isl_set_intersect(Outside, Statement->getDomain());
537 Outside = isl_set_params(Outside);
538 Outside = isl_set_complement(Outside);
539 Statement->getParent()->addAssumption(Outside);
540 isl_space_free(Space);
541}
542
Johannes Doerferte7044942015-02-24 11:58:30 +0000543void MemoryAccess::computeBoundsOnAccessRelation(unsigned ElementSize) {
544 ScalarEvolution *SE = Statement->getParent()->getSE();
545
546 Value *Ptr = getPointerOperand(*getAccessInstruction());
547 if (!Ptr || !SE->isSCEVable(Ptr->getType()))
548 return;
549
550 auto *PtrSCEV = SE->getSCEV(Ptr);
551 if (isa<SCEVCouldNotCompute>(PtrSCEV))
552 return;
553
554 auto *BasePtrSCEV = SE->getPointerBase(PtrSCEV);
555 if (BasePtrSCEV && !isa<SCEVCouldNotCompute>(BasePtrSCEV))
556 PtrSCEV = SE->getMinusSCEV(PtrSCEV, BasePtrSCEV);
557
558 const ConstantRange &Range = SE->getSignedRange(PtrSCEV);
559 if (Range.isFullSet())
560 return;
561
Johannes Doerferte4bd53b2015-03-08 19:49:50 +0000562 bool isWrapping = Range.isSignWrappedSet();
Johannes Doerferte7044942015-02-24 11:58:30 +0000563 unsigned BW = Range.getBitWidth();
Johannes Doerferte4bd53b2015-03-08 19:49:50 +0000564 const auto LB = isWrapping ? Range.getLower() : Range.getSignedMin();
565 const auto UB = isWrapping ? Range.getUpper() : Range.getSignedMax();
566
567 auto Min = LB.sdiv(APInt(BW, ElementSize));
568 auto Max = (UB - APInt(BW, 1)).sdiv(APInt(BW, ElementSize));
Johannes Doerferte7044942015-02-24 11:58:30 +0000569
570 isl_set *AccessRange = isl_map_range(isl_map_copy(AccessRelation));
571 AccessRange =
572 addRangeBoundsToSet(AccessRange, ConstantRange(Min, Max), 0, isl_dim_set);
573 AccessRelation = isl_map_intersect_range(AccessRelation, AccessRange);
574}
575
Johannes Doerfert13c8cf22014-08-10 08:09:38 +0000576MemoryAccess::MemoryAccess(const IRAccess &Access, Instruction *AccInst,
Johannes Doerfert1a28a892014-10-05 11:32:18 +0000577 ScopStmt *Statement, const ScopArrayInfo *SAI)
Johannes Doerfert4c7ce472014-10-08 10:11:33 +0000578 : AccType(getMemoryAccessType(Access)), Statement(Statement), Inst(AccInst),
Johannes Doerfert8f7124c2014-09-12 11:00:49 +0000579 newAccessRelation(nullptr) {
Tobias Grosser75805372011-04-29 06:27:02 +0000580
Johannes Doerfert5d83f092014-07-29 08:37:55 +0000581 isl_ctx *Ctx = Statement->getIslCtx();
Tobias Grosser9759f852011-11-10 12:44:55 +0000582 BaseAddr = Access.getBase();
Johannes Doerfert79fc23f2014-07-24 23:48:02 +0000583 BaseName = getIslCompatibleName("MemRef_", getBaseAddr(), "");
Johannes Doerfert1a28a892014-10-05 11:32:18 +0000584
585 isl_id *BaseAddrId = SAI->getBasePtrId();
Tobias Grosser5683df42011-11-09 22:34:34 +0000586
Tobias Grossera1879642011-12-20 10:43:14 +0000587 if (!Access.isAffine()) {
Tobias Grosser4f967492013-06-23 05:21:18 +0000588 // We overapproximate non-affine accesses with a possible access to the
589 // whole array. For read accesses it does not make a difference, if an
590 // access must or may happen. However, for write accesses it is important to
591 // differentiate between writes that must happen and writes that may happen.
Tobias Grosser04d6ae62013-06-23 06:04:54 +0000592 AccessRelation = isl_map_from_basic_map(createBasicAccessMap(Statement));
Johannes Doerfert5d83f092014-07-29 08:37:55 +0000593 AccessRelation =
594 isl_map_set_tuple_id(AccessRelation, isl_dim_out, BaseAddrId);
Johannes Doerferte7044942015-02-24 11:58:30 +0000595
596 computeBoundsOnAccessRelation(Access.getElemSizeInBytes());
Tobias Grossera1879642011-12-20 10:43:14 +0000597 return;
598 }
599
Johannes Doerfert5d83f092014-07-29 08:37:55 +0000600 isl_space *Space = isl_space_alloc(Ctx, 0, Statement->getNumIterators(), 0);
Tobias Grosser79baa212014-04-10 08:38:02 +0000601 AccessRelation = isl_map_universe(Space);
Tobias Grossera1879642011-12-20 10:43:14 +0000602
Tobias Grosser79baa212014-04-10 08:38:02 +0000603 for (int i = 0, Size = Access.Subscripts.size(); i < Size; ++i) {
Sebastian Pop18016682014-04-08 21:20:44 +0000604 isl_pw_aff *Affine =
605 SCEVAffinator::getPwAff(Statement, Access.Subscripts[i]);
Tobias Grosser75805372011-04-29 06:27:02 +0000606
Sebastian Pop422e33f2014-06-03 18:16:31 +0000607 if (Size == 1) {
608 // For the non delinearized arrays, divide the access function of the last
609 // subscript by the size of the elements in the array.
Sebastian Pop18016682014-04-08 21:20:44 +0000610 //
611 // A stride one array access in C expressed as A[i] is expressed in
612 // LLVM-IR as something like A[i * elementsize]. This hides the fact that
613 // two subsequent values of 'i' index two values that are stored next to
614 // each other in memory. By this division we make this characteristic
615 // obvious again.
Johannes Doerfert5d83f092014-07-29 08:37:55 +0000616 isl_val *v = isl_val_int_from_si(Ctx, Access.getElemSizeInBytes());
Sebastian Pop18016682014-04-08 21:20:44 +0000617 Affine = isl_pw_aff_scale_down_val(Affine, v);
618 }
619
620 isl_map *SubscriptMap = isl_map_from_pw_aff(Affine);
621
Tobias Grosser79baa212014-04-10 08:38:02 +0000622 AccessRelation = isl_map_flat_range_product(AccessRelation, SubscriptMap);
Sebastian Pop18016682014-04-08 21:20:44 +0000623 }
624
Tobias Grosser79baa212014-04-10 08:38:02 +0000625 Space = Statement->getDomainSpace();
Tobias Grosserabfbe632013-02-05 12:09:06 +0000626 AccessRelation = isl_map_set_tuple_id(
627 AccessRelation, isl_dim_in, isl_space_get_tuple_id(Space, isl_dim_set));
Johannes Doerfert5d83f092014-07-29 08:37:55 +0000628 AccessRelation =
629 isl_map_set_tuple_id(AccessRelation, isl_dim_out, BaseAddrId);
630
Tobias Grosser5e6813d2014-07-02 17:47:48 +0000631 assumeNoOutOfBound(Access);
Johannes Doerfert5d83f092014-07-29 08:37:55 +0000632 isl_space_free(Space);
Tobias Grosser8cae72f2011-11-08 15:41:08 +0000633}
Tobias Grosser30b8a092011-08-18 07:51:37 +0000634
Tobias Grosser8cae72f2011-11-08 15:41:08 +0000635void MemoryAccess::realignParams() {
Tobias Grosser6defb5b2014-04-10 08:37:44 +0000636 isl_space *ParamSpace = Statement->getParent()->getParamSpace();
Tobias Grosser37487052011-10-06 00:03:42 +0000637 AccessRelation = isl_map_align_params(AccessRelation, ParamSpace);
Tobias Grosser75805372011-04-29 06:27:02 +0000638}
639
Johannes Doerfert32868bf2014-08-01 08:13:25 +0000640const std::string MemoryAccess::getReductionOperatorStr() const {
641 return MemoryAccess::getReductionOperatorStr(getReductionType());
642}
643
Johannes Doerfertf6183392014-07-01 20:52:51 +0000644raw_ostream &polly::operator<<(raw_ostream &OS,
645 MemoryAccess::ReductionType RT) {
Johannes Doerfert32868bf2014-08-01 08:13:25 +0000646 if (RT == MemoryAccess::RT_NONE)
Johannes Doerfertf6183392014-07-01 20:52:51 +0000647 OS << "NONE";
Johannes Doerfert32868bf2014-08-01 08:13:25 +0000648 else
649 OS << MemoryAccess::getReductionOperatorStr(RT);
Johannes Doerfertf6183392014-07-01 20:52:51 +0000650 return OS;
651}
652
Tobias Grosser75805372011-04-29 06:27:02 +0000653void MemoryAccess::print(raw_ostream &OS) const {
Johannes Doerfert4c7ce472014-10-08 10:11:33 +0000654 switch (AccType) {
Tobias Grosserb58f6a42013-07-13 20:41:24 +0000655 case READ:
Johannes Doerfert6780bc32014-06-26 18:47:03 +0000656 OS.indent(12) << "ReadAccess :=\t";
Tobias Grosser4f967492013-06-23 05:21:18 +0000657 break;
Tobias Grosserb58f6a42013-07-13 20:41:24 +0000658 case MUST_WRITE:
Johannes Doerfert6780bc32014-06-26 18:47:03 +0000659 OS.indent(12) << "MustWriteAccess :=\t";
Tobias Grosser4f967492013-06-23 05:21:18 +0000660 break;
Tobias Grosserb58f6a42013-07-13 20:41:24 +0000661 case MAY_WRITE:
Johannes Doerfert6780bc32014-06-26 18:47:03 +0000662 OS.indent(12) << "MayWriteAccess :=\t";
Tobias Grosser4f967492013-06-23 05:21:18 +0000663 break;
664 }
Johannes Doerfert0ff23ec2015-02-06 20:13:15 +0000665 OS << "[Reduction Type: " << getReductionType() << "] ";
666 OS << "[Scalar: " << isScalar() << "]\n";
Johannes Doerferta99130f2014-10-13 12:58:03 +0000667 OS.indent(16) << getOriginalAccessRelationStr() << ";\n";
Tobias Grosser75805372011-04-29 06:27:02 +0000668}
669
Tobias Grosser74394f02013-01-14 22:40:23 +0000670void MemoryAccess::dump() const { print(errs()); }
Tobias Grosser75805372011-04-29 06:27:02 +0000671
672// Create a map in the size of the provided set domain, that maps from the
673// one element of the provided set domain to another element of the provided
674// set domain.
675// The mapping is limited to all points that are equal in all but the last
676// dimension and for which the last dimension of the input is strict smaller
677// than the last dimension of the output.
678//
679// getEqualAndLarger(set[i0, i1, ..., iX]):
680//
681// set[i0, i1, ..., iX] -> set[o0, o1, ..., oX]
682// : i0 = o0, i1 = o1, ..., i(X-1) = o(X-1), iX < oX
683//
Tobias Grosserf5338802011-10-06 00:03:35 +0000684static isl_map *getEqualAndLarger(isl_space *setDomain) {
Tobias Grosserc327932c2012-02-01 14:23:36 +0000685 isl_space *Space = isl_space_map_from_set(setDomain);
686 isl_map *Map = isl_map_universe(isl_space_copy(Space));
687 isl_local_space *MapLocalSpace = isl_local_space_from_space(Space);
Sebastian Pop40408762013-10-04 17:14:53 +0000688 unsigned lastDimension = isl_map_dim(Map, isl_dim_in) - 1;
Tobias Grosser75805372011-04-29 06:27:02 +0000689
690 // Set all but the last dimension to be equal for the input and output
691 //
692 // input[i0, i1, ..., iX] -> output[o0, o1, ..., oX]
693 // : i0 = o0, i1 = o1, ..., i(X-1) = o(X-1)
Sebastian Pop40408762013-10-04 17:14:53 +0000694 for (unsigned i = 0; i < lastDimension; ++i)
Tobias Grosserc327932c2012-02-01 14:23:36 +0000695 Map = isl_map_equate(Map, isl_dim_in, i, isl_dim_out, i);
Tobias Grosser75805372011-04-29 06:27:02 +0000696
697 // Set the last dimension of the input to be strict smaller than the
698 // last dimension of the output.
699 //
700 // input[?,?,?,...,iX] -> output[?,?,?,...,oX] : iX < oX
701 //
Tobias Grosseredab1352013-06-21 06:41:31 +0000702 isl_val *v;
703 isl_ctx *Ctx = isl_map_get_ctx(Map);
Tobias Grosserf5338802011-10-06 00:03:35 +0000704 isl_constraint *c = isl_inequality_alloc(isl_local_space_copy(MapLocalSpace));
Tobias Grosseredab1352013-06-21 06:41:31 +0000705 v = isl_val_int_from_si(Ctx, -1);
706 c = isl_constraint_set_coefficient_val(c, isl_dim_in, lastDimension, v);
707 v = isl_val_int_from_si(Ctx, 1);
708 c = isl_constraint_set_coefficient_val(c, isl_dim_out, lastDimension, v);
709 v = isl_val_int_from_si(Ctx, -1);
710 c = isl_constraint_set_constant_val(c, v);
Tobias Grosser75805372011-04-29 06:27:02 +0000711
Tobias Grosserc327932c2012-02-01 14:23:36 +0000712 Map = isl_map_add_constraint(Map, c);
Tobias Grosser75805372011-04-29 06:27:02 +0000713
Tobias Grosser23b36662011-10-17 08:32:36 +0000714 isl_local_space_free(MapLocalSpace);
Tobias Grosserc327932c2012-02-01 14:23:36 +0000715 return Map;
Tobias Grosser75805372011-04-29 06:27:02 +0000716}
717
Sebastian Popa00a0292012-12-18 07:46:06 +0000718isl_set *MemoryAccess::getStride(__isl_take const isl_map *Schedule) const {
Tobias Grosserabfbe632013-02-05 12:09:06 +0000719 isl_map *S = const_cast<isl_map *>(Schedule);
Johannes Doerferta99130f2014-10-13 12:58:03 +0000720 isl_map *AccessRelation = getAccessRelation();
Sebastian Popa00a0292012-12-18 07:46:06 +0000721 isl_space *Space = isl_space_range(isl_map_get_space(S));
722 isl_map *NextScatt = getEqualAndLarger(Space);
Tobias Grosser75805372011-04-29 06:27:02 +0000723
Sebastian Popa00a0292012-12-18 07:46:06 +0000724 S = isl_map_reverse(S);
725 NextScatt = isl_map_lexmin(NextScatt);
Tobias Grosser75805372011-04-29 06:27:02 +0000726
Sebastian Popa00a0292012-12-18 07:46:06 +0000727 NextScatt = isl_map_apply_range(NextScatt, isl_map_copy(S));
728 NextScatt = isl_map_apply_range(NextScatt, isl_map_copy(AccessRelation));
729 NextScatt = isl_map_apply_domain(NextScatt, S);
730 NextScatt = isl_map_apply_domain(NextScatt, AccessRelation);
Tobias Grosser75805372011-04-29 06:27:02 +0000731
Sebastian Popa00a0292012-12-18 07:46:06 +0000732 isl_set *Deltas = isl_map_deltas(NextScatt);
733 return Deltas;
Tobias Grosser75805372011-04-29 06:27:02 +0000734}
735
Sebastian Popa00a0292012-12-18 07:46:06 +0000736bool MemoryAccess::isStrideX(__isl_take const isl_map *Schedule,
Tobias Grosser28dd4862012-01-24 16:42:16 +0000737 int StrideWidth) const {
738 isl_set *Stride, *StrideX;
739 bool IsStrideX;
Tobias Grosser75805372011-04-29 06:27:02 +0000740
Sebastian Popa00a0292012-12-18 07:46:06 +0000741 Stride = getStride(Schedule);
Tobias Grosser28dd4862012-01-24 16:42:16 +0000742 StrideX = isl_set_universe(isl_set_get_space(Stride));
743 StrideX = isl_set_fix_si(StrideX, isl_dim_set, 0, StrideWidth);
744 IsStrideX = isl_set_is_equal(Stride, StrideX);
Tobias Grosser75805372011-04-29 06:27:02 +0000745
Tobias Grosser28dd4862012-01-24 16:42:16 +0000746 isl_set_free(StrideX);
Tobias Grosserdea98232012-01-17 20:34:27 +0000747 isl_set_free(Stride);
Tobias Grosserb76f38532011-08-20 11:11:25 +0000748
Tobias Grosser28dd4862012-01-24 16:42:16 +0000749 return IsStrideX;
750}
751
Sebastian Popa00a0292012-12-18 07:46:06 +0000752bool MemoryAccess::isStrideZero(const isl_map *Schedule) const {
753 return isStrideX(Schedule, 0);
Tobias Grosser75805372011-04-29 06:27:02 +0000754}
755
Tobias Grosser79baa212014-04-10 08:38:02 +0000756bool MemoryAccess::isScalar() const {
757 return isl_map_n_out(AccessRelation) == 0;
758}
759
Sebastian Popa00a0292012-12-18 07:46:06 +0000760bool MemoryAccess::isStrideOne(const isl_map *Schedule) const {
761 return isStrideX(Schedule, 1);
Tobias Grosser75805372011-04-29 06:27:02 +0000762}
763
Tobias Grosser5d453812011-10-06 00:04:11 +0000764void MemoryAccess::setNewAccessRelation(isl_map *newAccess) {
Tobias Grosserb76f38532011-08-20 11:11:25 +0000765 isl_map_free(newAccessRelation);
Raghesh Aloor7a04f4f2011-08-03 13:47:59 +0000766 newAccessRelation = newAccess;
Raghesh Aloor3cb66282011-07-12 17:14:03 +0000767}
Tobias Grosser75805372011-04-29 06:27:02 +0000768
769//===----------------------------------------------------------------------===//
Tobias Grossercf3942d2011-10-06 00:04:05 +0000770
Tobias Grosser74394f02013-01-14 22:40:23 +0000771isl_map *ScopStmt::getScattering() const { return isl_map_copy(Scattering); }
Tobias Grossercf3942d2011-10-06 00:04:05 +0000772
Tobias Grosser37eb4222014-02-20 21:43:54 +0000773void ScopStmt::restrictDomain(__isl_take isl_set *NewDomain) {
774 assert(isl_set_is_subset(NewDomain, Domain) &&
775 "New domain is not a subset of old domain!");
776 isl_set_free(Domain);
777 Domain = NewDomain;
778 Scattering = isl_map_intersect_domain(Scattering, isl_set_copy(Domain));
779}
780
Tobias Grossercf3942d2011-10-06 00:04:05 +0000781void ScopStmt::setScattering(isl_map *NewScattering) {
Tobias Grosser5a56cbf2014-04-16 07:33:47 +0000782 assert(NewScattering && "New scattering is nullptr");
Tobias Grosserb76f38532011-08-20 11:11:25 +0000783 isl_map_free(Scattering);
Tobias Grossercf3942d2011-10-06 00:04:05 +0000784 Scattering = NewScattering;
Tobias Grosserb76f38532011-08-20 11:11:25 +0000785}
786
Tobias Grosser75805372011-04-29 06:27:02 +0000787void ScopStmt::buildScattering(SmallVectorImpl<unsigned> &Scatter) {
Tobias Grosser78d8a3d2012-01-17 20:34:23 +0000788 unsigned NbIterators = getNumIterators();
789 unsigned NbScatteringDims = Parent.getMaxLoopDepth() * 2 + 1;
790
Tobias Grosser084d8f72012-05-29 09:29:44 +0000791 isl_space *Space = isl_space_set_alloc(getIslCtx(), 0, NbScatteringDims);
Tobias Grosser78d8a3d2012-01-17 20:34:23 +0000792
Tobias Grosser084d8f72012-05-29 09:29:44 +0000793 Scattering = isl_map_from_domain_and_range(isl_set_universe(getDomainSpace()),
794 isl_set_universe(Space));
Tobias Grosser75805372011-04-29 06:27:02 +0000795
796 // Loop dimensions.
Tobias Grosser78d8a3d2012-01-17 20:34:23 +0000797 for (unsigned i = 0; i < NbIterators; ++i)
Tobias Grosserabfbe632013-02-05 12:09:06 +0000798 Scattering =
799 isl_map_equate(Scattering, isl_dim_out, 2 * i + 1, isl_dim_in, i);
Tobias Grosser75805372011-04-29 06:27:02 +0000800
801 // Constant dimensions
Tobias Grosser78d8a3d2012-01-17 20:34:23 +0000802 for (unsigned i = 0; i < NbIterators + 1; ++i)
803 Scattering = isl_map_fix_si(Scattering, isl_dim_out, 2 * i, Scatter[i]);
Tobias Grosser75805372011-04-29 06:27:02 +0000804
805 // Fill scattering dimensions.
Tobias Grosser78d8a3d2012-01-17 20:34:23 +0000806 for (unsigned i = 2 * NbIterators + 1; i < NbScatteringDims; ++i)
807 Scattering = isl_map_fix_si(Scattering, isl_dim_out, i, 0);
Tobias Grosser75805372011-04-29 06:27:02 +0000808
Tobias Grosser37487052011-10-06 00:03:42 +0000809 Scattering = isl_map_align_params(Scattering, Parent.getParamSpace());
Tobias Grosser75805372011-04-29 06:27:02 +0000810}
811
Johannes Doerfertff9d1982015-02-24 12:00:50 +0000812void ScopStmt::buildAccesses(TempScop &tempScop, BasicBlock *Block,
813 bool isApproximated) {
814 AccFuncSetType *AFS = tempScop.getAccessFunctions(Block);
815 if (!AFS)
816 return;
817
818 for (auto &AccessPair : *AFS) {
819 IRAccess &Access = AccessPair.first;
Johannes Doerfert1a28a892014-10-05 11:32:18 +0000820 Instruction *AccessInst = AccessPair.second;
821
Johannes Doerfert80ef1102014-11-07 08:31:31 +0000822 Type *AccessType = getAccessInstType(AccessInst)->getPointerTo();
823 const ScopArrayInfo *SAI = getParent()->getOrCreateScopArrayInfo(
824 Access.getBase(), AccessType, Access.Sizes);
825
Johannes Doerfertff9d1982015-02-24 12:00:50 +0000826 if (isApproximated && Access.isWrite())
827 Access.setMayWrite();
828
Johannes Doerfert1a28a892014-10-05 11:32:18 +0000829 MemAccs.push_back(new MemoryAccess(Access, AccessInst, this, SAI));
Tobias Grosserd6aafa72014-02-20 21:29:09 +0000830
831 // We do not track locations for scalar memory accesses at the moment.
832 //
833 // We do not have a use for this information at the moment. If we need this
834 // at some point, the "instruction -> access" mapping needs to be enhanced
835 // as a single instruction could then possibly perform multiple accesses.
Johannes Doerfert1a28a892014-10-05 11:32:18 +0000836 if (!Access.isScalar()) {
837 assert(!InstructionToAccess.count(AccessInst) &&
Tobias Grosser3fc91542014-02-20 21:43:45 +0000838 "Unexpected 1-to-N mapping on instruction to access map!");
Johannes Doerfert1a28a892014-10-05 11:32:18 +0000839 InstructionToAccess[AccessInst] = MemAccs.back();
Tobias Grosserd6aafa72014-02-20 21:29:09 +0000840 }
Tobias Grosser75805372011-04-29 06:27:02 +0000841 }
842}
843
Tobias Grosser8cae72f2011-11-08 15:41:08 +0000844void ScopStmt::realignParams() {
Johannes Doerfertf6752892014-06-13 18:01:45 +0000845 for (MemoryAccess *MA : *this)
846 MA->realignParams();
Tobias Grosser8cae72f2011-11-08 15:41:08 +0000847
848 Domain = isl_set_align_params(Domain, Parent.getParamSpace());
849 Scattering = isl_map_align_params(Scattering, Parent.getParamSpace());
850}
851
Tobias Grosser65b00582011-11-08 15:41:19 +0000852__isl_give isl_set *ScopStmt::buildConditionSet(const Comparison &Comp) {
Tobias Grossera601fbd2011-11-09 22:34:44 +0000853 isl_pw_aff *L = SCEVAffinator::getPwAff(this, Comp.getLHS());
854 isl_pw_aff *R = SCEVAffinator::getPwAff(this, Comp.getRHS());
Tobias Grosser75805372011-04-29 06:27:02 +0000855
Tobias Grosserd2795d02011-08-18 07:51:40 +0000856 switch (Comp.getPred()) {
Tobias Grosser75805372011-04-29 06:27:02 +0000857 case ICmpInst::ICMP_EQ:
Tobias Grosser048c8792011-10-23 20:59:20 +0000858 return isl_pw_aff_eq_set(L, R);
Tobias Grosser75805372011-04-29 06:27:02 +0000859 case ICmpInst::ICMP_NE:
Tobias Grosser048c8792011-10-23 20:59:20 +0000860 return isl_pw_aff_ne_set(L, R);
Tobias Grosser75805372011-04-29 06:27:02 +0000861 case ICmpInst::ICMP_SLT:
Tobias Grosser048c8792011-10-23 20:59:20 +0000862 return isl_pw_aff_lt_set(L, R);
Tobias Grosser75805372011-04-29 06:27:02 +0000863 case ICmpInst::ICMP_SLE:
Tobias Grosser048c8792011-10-23 20:59:20 +0000864 return isl_pw_aff_le_set(L, R);
Tobias Grosserd2795d02011-08-18 07:51:40 +0000865 case ICmpInst::ICMP_SGT:
Tobias Grosser048c8792011-10-23 20:59:20 +0000866 return isl_pw_aff_gt_set(L, R);
Tobias Grosser75805372011-04-29 06:27:02 +0000867 case ICmpInst::ICMP_SGE:
Tobias Grosser048c8792011-10-23 20:59:20 +0000868 return isl_pw_aff_ge_set(L, R);
Tobias Grosserd2795d02011-08-18 07:51:40 +0000869 case ICmpInst::ICMP_ULT:
Tobias Grosserbfbc3692015-01-09 00:01:33 +0000870 return isl_pw_aff_lt_set(L, R);
Tobias Grosserd2795d02011-08-18 07:51:40 +0000871 case ICmpInst::ICMP_UGT:
Tobias Grosserbfbc3692015-01-09 00:01:33 +0000872 return isl_pw_aff_gt_set(L, R);
Tobias Grosserd2795d02011-08-18 07:51:40 +0000873 case ICmpInst::ICMP_ULE:
Tobias Grosserbfbc3692015-01-09 00:01:33 +0000874 return isl_pw_aff_le_set(L, R);
Tobias Grosser75805372011-04-29 06:27:02 +0000875 case ICmpInst::ICMP_UGE:
Tobias Grosserbfbc3692015-01-09 00:01:33 +0000876 return isl_pw_aff_ge_set(L, R);
Tobias Grosser75805372011-04-29 06:27:02 +0000877 default:
878 llvm_unreachable("Non integer predicate not supported");
879 }
Tobias Grosser75805372011-04-29 06:27:02 +0000880}
881
Tobias Grossere19661e2011-10-07 08:46:57 +0000882__isl_give isl_set *ScopStmt::addLoopBoundsToDomain(__isl_take isl_set *Domain,
Tobias Grosser60b54f12011-11-08 15:41:28 +0000883 TempScop &tempScop) {
Tobias Grossere19661e2011-10-07 08:46:57 +0000884 isl_space *Space;
885 isl_local_space *LocalSpace;
Tobias Grosser75805372011-04-29 06:27:02 +0000886
Tobias Grossere19661e2011-10-07 08:46:57 +0000887 Space = isl_set_get_space(Domain);
888 LocalSpace = isl_local_space_from_space(Space);
Tobias Grosserf5338802011-10-06 00:03:35 +0000889
Johannes Doerfert5ad8a6a2014-11-01 01:14:56 +0000890 ScalarEvolution *SE = getParent()->getSE();
Tobias Grosser75805372011-04-29 06:27:02 +0000891 for (int i = 0, e = getNumIterators(); i != e; ++i) {
Tobias Grosser9b13d3d2011-10-06 22:32:58 +0000892 isl_aff *Zero = isl_aff_zero_on_domain(isl_local_space_copy(LocalSpace));
Tobias Grosserabfbe632013-02-05 12:09:06 +0000893 isl_pw_aff *IV =
894 isl_pw_aff_from_aff(isl_aff_set_coefficient_si(Zero, isl_dim_in, i, 1));
Tobias Grosser75805372011-04-29 06:27:02 +0000895
Tobias Grosser9b13d3d2011-10-06 22:32:58 +0000896 // 0 <= IV.
897 isl_set *LowerBound = isl_pw_aff_nonneg_set(isl_pw_aff_copy(IV));
898 Domain = isl_set_intersect(Domain, LowerBound);
899
900 // IV <= LatchExecutions.
Hongbin Zheng27f3afb2011-04-30 03:26:51 +0000901 const Loop *L = getLoopForDimension(i);
Johannes Doerfert5ad8a6a2014-11-01 01:14:56 +0000902 const SCEV *LatchExecutions = SE->getBackedgeTakenCount(L);
Tobias Grosser9b13d3d2011-10-06 22:32:58 +0000903 isl_pw_aff *UpperBound = SCEVAffinator::getPwAff(this, LatchExecutions);
904 isl_set *UpperBoundSet = isl_pw_aff_le_set(IV, UpperBound);
Tobias Grosser75805372011-04-29 06:27:02 +0000905 Domain = isl_set_intersect(Domain, UpperBoundSet);
906 }
907
Tobias Grosserf5338802011-10-06 00:03:35 +0000908 isl_local_space_free(LocalSpace);
Tobias Grossere19661e2011-10-07 08:46:57 +0000909 return Domain;
Tobias Grosser75805372011-04-29 06:27:02 +0000910}
911
Tobias Grossere602a072013-05-07 07:30:56 +0000912__isl_give isl_set *ScopStmt::addConditionsToDomain(__isl_take isl_set *Domain,
913 TempScop &tempScop,
914 const Region &CurRegion) {
Tobias Grossere19661e2011-10-07 08:46:57 +0000915 const Region *TopRegion = tempScop.getMaxRegion().getParent(),
Tobias Grosserd7e58642013-04-10 06:55:45 +0000916 *CurrentRegion = &CurRegion;
Johannes Doerfertff9d1982015-02-24 12:00:50 +0000917 const BasicBlock *BranchingBB = BB ? BB : R->getEntry();
Tobias Grosser75805372011-04-29 06:27:02 +0000918
Tobias Grosser75805372011-04-29 06:27:02 +0000919 do {
Tobias Grossere19661e2011-10-07 08:46:57 +0000920 if (BranchingBB != CurrentRegion->getEntry()) {
921 if (const BBCond *Condition = tempScop.getBBCond(BranchingBB))
Tobias Grosser083d3d32014-06-28 08:59:45 +0000922 for (const auto &C : *Condition) {
923 isl_set *ConditionSet = buildConditionSet(C);
Tobias Grossere19661e2011-10-07 08:46:57 +0000924 Domain = isl_set_intersect(Domain, ConditionSet);
Tobias Grosser75805372011-04-29 06:27:02 +0000925 }
926 }
Tobias Grossere19661e2011-10-07 08:46:57 +0000927 BranchingBB = CurrentRegion->getEntry();
928 CurrentRegion = CurrentRegion->getParent();
929 } while (TopRegion != CurrentRegion);
Tobias Grosser75805372011-04-29 06:27:02 +0000930
Tobias Grossere19661e2011-10-07 08:46:57 +0000931 return Domain;
Tobias Grosser75805372011-04-29 06:27:02 +0000932}
933
Tobias Grossere602a072013-05-07 07:30:56 +0000934__isl_give isl_set *ScopStmt::buildDomain(TempScop &tempScop,
935 const Region &CurRegion) {
Tobias Grossere19661e2011-10-07 08:46:57 +0000936 isl_space *Space;
937 isl_set *Domain;
Tobias Grosser084d8f72012-05-29 09:29:44 +0000938 isl_id *Id;
Tobias Grossere19661e2011-10-07 08:46:57 +0000939
940 Space = isl_space_set_alloc(getIslCtx(), 0, getNumIterators());
941
Tobias Grosser084d8f72012-05-29 09:29:44 +0000942 Id = isl_id_alloc(getIslCtx(), getBaseName(), this);
943
Tobias Grossere19661e2011-10-07 08:46:57 +0000944 Domain = isl_set_universe(Space);
Tobias Grossere19661e2011-10-07 08:46:57 +0000945 Domain = addLoopBoundsToDomain(Domain, tempScop);
946 Domain = addConditionsToDomain(Domain, tempScop, CurRegion);
Tobias Grosser084d8f72012-05-29 09:29:44 +0000947 Domain = isl_set_set_tuple_id(Domain, Id);
Tobias Grossere19661e2011-10-07 08:46:57 +0000948
949 return Domain;
Tobias Grosser75805372011-04-29 06:27:02 +0000950}
951
Tobias Grosser7b50bee2014-11-25 10:51:12 +0000952void ScopStmt::deriveAssumptionsFromGEP(GetElementPtrInst *GEP) {
953 int Dimension = 0;
954 isl_ctx *Ctx = Parent.getIslCtx();
955 isl_local_space *LSpace = isl_local_space_from_space(getDomainSpace());
956 Type *Ty = GEP->getPointerOperandType();
957 ScalarEvolution &SE = *Parent.getSE();
958
959 if (auto *PtrTy = dyn_cast<PointerType>(Ty)) {
960 Dimension = 1;
961 Ty = PtrTy->getElementType();
962 }
963
964 while (auto ArrayTy = dyn_cast<ArrayType>(Ty)) {
965 unsigned int Operand = 1 + Dimension;
966
967 if (GEP->getNumOperands() <= Operand)
968 break;
969
970 const SCEV *Expr = SE.getSCEV(GEP->getOperand(Operand));
971
972 if (isAffineExpr(&Parent.getRegion(), Expr, SE)) {
973 isl_pw_aff *AccessOffset = SCEVAffinator::getPwAff(this, Expr);
974 AccessOffset =
975 isl_pw_aff_set_tuple_id(AccessOffset, isl_dim_in, getDomainId());
976
977 isl_pw_aff *DimSize = isl_pw_aff_from_aff(isl_aff_val_on_domain(
978 isl_local_space_copy(LSpace),
979 isl_val_int_from_si(Ctx, ArrayTy->getNumElements())));
980
981 isl_set *OutOfBound = isl_pw_aff_ge_set(AccessOffset, DimSize);
982 OutOfBound = isl_set_intersect(getDomain(), OutOfBound);
983 OutOfBound = isl_set_params(OutOfBound);
984 isl_set *InBound = isl_set_complement(OutOfBound);
985 isl_set *Executed = isl_set_params(getDomain());
986
987 // A => B == !A or B
988 isl_set *InBoundIfExecuted =
989 isl_set_union(isl_set_complement(Executed), InBound);
990
991 Parent.addAssumption(InBoundIfExecuted);
992 }
993
994 Dimension += 1;
995 Ty = ArrayTy->getElementType();
996 }
997
998 isl_local_space_free(LSpace);
999}
1000
Johannes Doerfertff9d1982015-02-24 12:00:50 +00001001void ScopStmt::deriveAssumptions(BasicBlock *Block) {
1002 for (Instruction &Inst : *Block)
Tobias Grosser7b50bee2014-11-25 10:51:12 +00001003 if (auto *GEP = dyn_cast<GetElementPtrInst>(&Inst))
1004 deriveAssumptionsFromGEP(GEP);
1005}
1006
Tobias Grosser74394f02013-01-14 22:40:23 +00001007ScopStmt::ScopStmt(Scop &parent, TempScop &tempScop, const Region &CurRegion,
Johannes Doerfertff9d1982015-02-24 12:00:50 +00001008 Region &R, SmallVectorImpl<Loop *> &Nest,
1009 SmallVectorImpl<unsigned> &Scatter)
1010 : Parent(parent), BB(nullptr), R(&R), Build(nullptr),
1011 NestLoops(Nest.size()) {
1012 // Setup the induction variables.
1013 for (unsigned i = 0, e = Nest.size(); i < e; ++i)
1014 NestLoops[i] = Nest[i];
1015
1016 BaseName = getIslCompatibleName("Stmt_(", R.getNameStr(), ")");
1017
1018 Domain = buildDomain(tempScop, CurRegion);
1019 buildScattering(Scatter);
1020
1021 BasicBlock *EntryBB = R.getEntry();
1022 for (BasicBlock *Block : R.blocks()) {
1023 buildAccesses(tempScop, Block, Block != EntryBB);
1024 deriveAssumptions(Block);
1025 }
1026 checkForReductions();
1027}
1028
1029ScopStmt::ScopStmt(Scop &parent, TempScop &tempScop, const Region &CurRegion,
Sebastian Pop860e0212013-02-15 21:26:44 +00001030 BasicBlock &bb, SmallVectorImpl<Loop *> &Nest,
Tobias Grosser75805372011-04-29 06:27:02 +00001031 SmallVectorImpl<unsigned> &Scatter)
Johannes Doerfertff9d1982015-02-24 12:00:50 +00001032 : Parent(parent), BB(&bb), R(nullptr), Build(nullptr),
1033 NestLoops(Nest.size()) {
Tobias Grosser75805372011-04-29 06:27:02 +00001034 // Setup the induction variables.
Tobias Grosser683b8e42014-11-30 14:33:31 +00001035 for (unsigned i = 0, e = Nest.size(); i < e; ++i)
Sebastian Pop860e0212013-02-15 21:26:44 +00001036 NestLoops[i] = Nest[i];
Tobias Grosser75805372011-04-29 06:27:02 +00001037
Johannes Doerfert79fc23f2014-07-24 23:48:02 +00001038 BaseName = getIslCompatibleName("Stmt_", &bb, "");
Tobias Grosser75805372011-04-29 06:27:02 +00001039
Tobias Grossere19661e2011-10-07 08:46:57 +00001040 Domain = buildDomain(tempScop, CurRegion);
Tobias Grosser75805372011-04-29 06:27:02 +00001041 buildScattering(Scatter);
Johannes Doerfertff9d1982015-02-24 12:00:50 +00001042 buildAccesses(tempScop, BB);
1043 deriveAssumptions(BB);
Johannes Doerferte58a0122014-06-27 20:31:28 +00001044 checkForReductions();
Johannes Doerfert0ee1f212014-06-17 17:31:36 +00001045}
1046
Johannes Doerferte58a0122014-06-27 20:31:28 +00001047/// @brief Collect loads which might form a reduction chain with @p StoreMA
1048///
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00001049/// Check if the stored value for @p StoreMA is a binary operator with one or
1050/// two loads as operands. If the binary operand is commutative & associative,
Johannes Doerferte58a0122014-06-27 20:31:28 +00001051/// used only once (by @p StoreMA) and its load operands are also used only
1052/// once, we have found a possible reduction chain. It starts at an operand
1053/// load and includes the binary operator and @p StoreMA.
1054///
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00001055/// Note: We allow only one use to ensure the load and binary operator cannot
Johannes Doerferte58a0122014-06-27 20:31:28 +00001056/// escape this block or into any other store except @p StoreMA.
1057void ScopStmt::collectCandiateReductionLoads(
1058 MemoryAccess *StoreMA, SmallVectorImpl<MemoryAccess *> &Loads) {
1059 auto *Store = dyn_cast<StoreInst>(StoreMA->getAccessInstruction());
1060 if (!Store)
Johannes Doerfert0ee1f212014-06-17 17:31:36 +00001061 return;
1062
1063 // Skip if there is not one binary operator between the load and the store
1064 auto *BinOp = dyn_cast<BinaryOperator>(Store->getValueOperand());
Johannes Doerferte58a0122014-06-27 20:31:28 +00001065 if (!BinOp)
1066 return;
1067
1068 // Skip if the binary operators has multiple uses
1069 if (BinOp->getNumUses() != 1)
Johannes Doerfert0ee1f212014-06-17 17:31:36 +00001070 return;
1071
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00001072 // Skip if the opcode of the binary operator is not commutative/associative
Johannes Doerfert0ee1f212014-06-17 17:31:36 +00001073 if (!BinOp->isCommutative() || !BinOp->isAssociative())
1074 return;
1075
Johannes Doerfert9890a052014-07-01 00:32:29 +00001076 // Skip if the binary operator is outside the current SCoP
1077 if (BinOp->getParent() != Store->getParent())
1078 return;
1079
Johannes Doerfert0ee1f212014-06-17 17:31:36 +00001080 // Skip if it is a multiplicative reduction and we disabled them
1081 if (DisableMultiplicativeReductions &&
1082 (BinOp->getOpcode() == Instruction::Mul ||
1083 BinOp->getOpcode() == Instruction::FMul))
1084 return;
1085
Johannes Doerferte58a0122014-06-27 20:31:28 +00001086 // Check the binary operator operands for a candidate load
1087 auto *PossibleLoad0 = dyn_cast<LoadInst>(BinOp->getOperand(0));
1088 auto *PossibleLoad1 = dyn_cast<LoadInst>(BinOp->getOperand(1));
1089 if (!PossibleLoad0 && !PossibleLoad1)
1090 return;
1091
1092 // A load is only a candidate if it cannot escape (thus has only this use)
1093 if (PossibleLoad0 && PossibleLoad0->getNumUses() == 1)
Johannes Doerfert9890a052014-07-01 00:32:29 +00001094 if (PossibleLoad0->getParent() == Store->getParent())
1095 Loads.push_back(lookupAccessFor(PossibleLoad0));
Johannes Doerferte58a0122014-06-27 20:31:28 +00001096 if (PossibleLoad1 && PossibleLoad1->getNumUses() == 1)
Johannes Doerfert9890a052014-07-01 00:32:29 +00001097 if (PossibleLoad1->getParent() == Store->getParent())
1098 Loads.push_back(lookupAccessFor(PossibleLoad1));
Johannes Doerferte58a0122014-06-27 20:31:28 +00001099}
1100
1101/// @brief Check for reductions in this ScopStmt
1102///
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00001103/// Iterate over all store memory accesses and check for valid binary reduction
1104/// like chains. For all candidates we check if they have the same base address
1105/// and there are no other accesses which overlap with them. The base address
1106/// check rules out impossible reductions candidates early. The overlap check,
1107/// together with the "only one user" check in collectCandiateReductionLoads,
Johannes Doerferte58a0122014-06-27 20:31:28 +00001108/// guarantees that none of the intermediate results will escape during
1109/// execution of the loop nest. We basically check here that no other memory
1110/// access can access the same memory as the potential reduction.
1111void ScopStmt::checkForReductions() {
1112 SmallVector<MemoryAccess *, 2> Loads;
1113 SmallVector<std::pair<MemoryAccess *, MemoryAccess *>, 4> Candidates;
1114
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00001115 // First collect candidate load-store reduction chains by iterating over all
Johannes Doerferte58a0122014-06-27 20:31:28 +00001116 // stores and collecting possible reduction loads.
1117 for (MemoryAccess *StoreMA : MemAccs) {
1118 if (StoreMA->isRead())
1119 continue;
1120
1121 Loads.clear();
1122 collectCandiateReductionLoads(StoreMA, Loads);
1123 for (MemoryAccess *LoadMA : Loads)
1124 Candidates.push_back(std::make_pair(LoadMA, StoreMA));
1125 }
1126
1127 // Then check each possible candidate pair.
1128 for (const auto &CandidatePair : Candidates) {
1129 bool Valid = true;
1130 isl_map *LoadAccs = CandidatePair.first->getAccessRelation();
1131 isl_map *StoreAccs = CandidatePair.second->getAccessRelation();
1132
1133 // Skip those with obviously unequal base addresses.
1134 if (!isl_map_has_equal_space(LoadAccs, StoreAccs)) {
1135 isl_map_free(LoadAccs);
1136 isl_map_free(StoreAccs);
1137 continue;
1138 }
1139
1140 // And check if the remaining for overlap with other memory accesses.
1141 isl_map *AllAccsRel = isl_map_union(LoadAccs, StoreAccs);
1142 AllAccsRel = isl_map_intersect_domain(AllAccsRel, getDomain());
1143 isl_set *AllAccs = isl_map_range(AllAccsRel);
1144
1145 for (MemoryAccess *MA : MemAccs) {
1146 if (MA == CandidatePair.first || MA == CandidatePair.second)
1147 continue;
1148
1149 isl_map *AccRel =
1150 isl_map_intersect_domain(MA->getAccessRelation(), getDomain());
1151 isl_set *Accs = isl_map_range(AccRel);
1152
1153 if (isl_set_has_equal_space(AllAccs, Accs) || isl_set_free(Accs)) {
1154 isl_set *OverlapAccs = isl_set_intersect(Accs, isl_set_copy(AllAccs));
1155 Valid = Valid && isl_set_is_empty(OverlapAccs);
1156 isl_set_free(OverlapAccs);
1157 }
1158 }
1159
1160 isl_set_free(AllAccs);
1161 if (!Valid)
1162 continue;
1163
Johannes Doerfertf6183392014-07-01 20:52:51 +00001164 const LoadInst *Load =
1165 dyn_cast<const LoadInst>(CandidatePair.first->getAccessInstruction());
1166 MemoryAccess::ReductionType RT =
1167 getReductionType(dyn_cast<BinaryOperator>(Load->user_back()), Load);
1168
Johannes Doerferte58a0122014-06-27 20:31:28 +00001169 // If no overlapping access was found we mark the load and store as
1170 // reduction like.
Johannes Doerfertf6183392014-07-01 20:52:51 +00001171 CandidatePair.first->markAsReductionLike(RT);
1172 CandidatePair.second->markAsReductionLike(RT);
Johannes Doerferte58a0122014-06-27 20:31:28 +00001173 }
Tobias Grosser75805372011-04-29 06:27:02 +00001174}
1175
Tobias Grosser74394f02013-01-14 22:40:23 +00001176std::string ScopStmt::getDomainStr() const { return stringFromIslObj(Domain); }
Tobias Grosser75805372011-04-29 06:27:02 +00001177
1178std::string ScopStmt::getScatteringStr() const {
Tobias Grossercf3942d2011-10-06 00:04:05 +00001179 return stringFromIslObj(Scattering);
Tobias Grosser75805372011-04-29 06:27:02 +00001180}
1181
Tobias Grosser74394f02013-01-14 22:40:23 +00001182unsigned ScopStmt::getNumParams() const { return Parent.getNumParams(); }
Tobias Grosser75805372011-04-29 06:27:02 +00001183
Tobias Grosserf567e1a2015-02-19 22:16:12 +00001184unsigned ScopStmt::getNumIterators() const { return NestLoops.size(); }
Tobias Grosser75805372011-04-29 06:27:02 +00001185
1186unsigned ScopStmt::getNumScattering() const {
1187 return isl_map_dim(Scattering, isl_dim_out);
1188}
1189
1190const char *ScopStmt::getBaseName() const { return BaseName.c_str(); }
1191
Hongbin Zheng27f3afb2011-04-30 03:26:51 +00001192const Loop *ScopStmt::getLoopForDimension(unsigned Dimension) const {
Sebastian Pop860e0212013-02-15 21:26:44 +00001193 return NestLoops[Dimension];
Tobias Grosser75805372011-04-29 06:27:02 +00001194}
1195
Tobias Grosser74394f02013-01-14 22:40:23 +00001196isl_ctx *ScopStmt::getIslCtx() const { return Parent.getIslCtx(); }
Tobias Grosser75805372011-04-29 06:27:02 +00001197
Tobias Grosser74394f02013-01-14 22:40:23 +00001198isl_set *ScopStmt::getDomain() const { return isl_set_copy(Domain); }
Tobias Grosserd5a7bfc2011-05-06 19:52:19 +00001199
Tobias Grosser78d8a3d2012-01-17 20:34:23 +00001200isl_space *ScopStmt::getDomainSpace() const {
1201 return isl_set_get_space(Domain);
1202}
1203
Tobias Grosser74394f02013-01-14 22:40:23 +00001204isl_id *ScopStmt::getDomainId() const { return isl_set_get_tuple_id(Domain); }
Tobias Grossercd95b772012-08-30 11:49:38 +00001205
Tobias Grosser75805372011-04-29 06:27:02 +00001206ScopStmt::~ScopStmt() {
1207 while (!MemAccs.empty()) {
1208 delete MemAccs.back();
1209 MemAccs.pop_back();
1210 }
1211
1212 isl_set_free(Domain);
1213 isl_map_free(Scattering);
1214}
1215
1216void ScopStmt::print(raw_ostream &OS) const {
1217 OS << "\t" << getBaseName() << "\n";
Tobias Grosser75805372011-04-29 06:27:02 +00001218 OS.indent(12) << "Domain :=\n";
1219
1220 if (Domain) {
1221 OS.indent(16) << getDomainStr() << ";\n";
1222 } else
1223 OS.indent(16) << "n/a\n";
1224
1225 OS.indent(12) << "Scattering :=\n";
1226
1227 if (Domain) {
1228 OS.indent(16) << getScatteringStr() << ";\n";
1229 } else
1230 OS.indent(16) << "n/a\n";
1231
Tobias Grosser083d3d32014-06-28 08:59:45 +00001232 for (MemoryAccess *Access : MemAccs)
1233 Access->print(OS);
Tobias Grosser75805372011-04-29 06:27:02 +00001234}
1235
1236void ScopStmt::dump() const { print(dbgs()); }
1237
1238//===----------------------------------------------------------------------===//
1239/// Scop class implement
Tobias Grosser60b54f12011-11-08 15:41:28 +00001240
Tobias Grosser7ffe4e82011-11-17 12:56:10 +00001241void Scop::setContext(__isl_take isl_set *NewContext) {
Tobias Grosserff9b54d2011-11-15 11:38:44 +00001242 NewContext = isl_set_align_params(NewContext, isl_set_get_space(Context));
1243 isl_set_free(Context);
1244 Context = NewContext;
1245}
1246
Tobias Grosserabfbe632013-02-05 12:09:06 +00001247void Scop::addParams(std::vector<const SCEV *> NewParameters) {
Tobias Grosser083d3d32014-06-28 08:59:45 +00001248 for (const SCEV *Parameter : NewParameters) {
Tobias Grosser60b54f12011-11-08 15:41:28 +00001249 if (ParameterIds.find(Parameter) != ParameterIds.end())
1250 continue;
1251
1252 int dimension = Parameters.size();
1253
1254 Parameters.push_back(Parameter);
1255 ParameterIds[Parameter] = dimension;
1256 }
1257}
1258
Tobias Grosser9a38ab82011-11-08 15:41:03 +00001259__isl_give isl_id *Scop::getIdForParam(const SCEV *Parameter) const {
1260 ParamIdType::const_iterator IdIter = ParameterIds.find(Parameter);
Tobias Grosser76c2e322011-11-07 12:58:59 +00001261
Tobias Grosser9a38ab82011-11-08 15:41:03 +00001262 if (IdIter == ParameterIds.end())
Tobias Grosser5a56cbf2014-04-16 07:33:47 +00001263 return nullptr;
Tobias Grosser76c2e322011-11-07 12:58:59 +00001264
Tobias Grosser8f99c162011-11-15 11:38:55 +00001265 std::string ParameterName;
1266
1267 if (const SCEVUnknown *ValueParameter = dyn_cast<SCEVUnknown>(Parameter)) {
1268 Value *Val = ValueParameter->getValue();
Tobias Grosser29ee0b12011-11-17 14:52:36 +00001269 ParameterName = Val->getName();
Tobias Grosser8f99c162011-11-15 11:38:55 +00001270 }
1271
1272 if (ParameterName == "" || ParameterName.substr(0, 2) == "p_")
Hongbin Zheng86a37742012-04-25 08:01:38 +00001273 ParameterName = "p_" + utostr_32(IdIter->second);
Tobias Grosser8f99c162011-11-15 11:38:55 +00001274
Tobias Grosser20532b82014-04-11 17:56:49 +00001275 return isl_id_alloc(getIslCtx(), ParameterName.c_str(),
1276 const_cast<void *>((const void *)Parameter));
Tobias Grosser76c2e322011-11-07 12:58:59 +00001277}
Tobias Grosser75805372011-04-29 06:27:02 +00001278
Tobias Grosser6be480c2011-11-08 15:41:13 +00001279void Scop::buildContext() {
1280 isl_space *Space = isl_space_params_alloc(IslCtx, 0);
Tobias Grossere86109f2013-10-29 21:05:49 +00001281 Context = isl_set_universe(isl_space_copy(Space));
1282 AssumedContext = isl_set_universe(Space);
Tobias Grosser0e27e242011-10-06 00:03:48 +00001283}
1284
Tobias Grosser18daaca2012-05-22 10:47:27 +00001285void Scop::addParameterBounds() {
Johannes Doerfert4f8ac3d2015-02-23 16:15:51 +00001286 for (const auto &ParamID : ParameterIds) {
Johannes Doerfert4f8ac3d2015-02-23 16:15:51 +00001287 int dim = ParamID.second;
Tobias Grosser18daaca2012-05-22 10:47:27 +00001288
Johannes Doerfert4f8ac3d2015-02-23 16:15:51 +00001289 ConstantRange SRange = SE->getSignedRange(ParamID.first);
Tobias Grosser18daaca2012-05-22 10:47:27 +00001290
Johannes Doerfert4f8ac3d2015-02-23 16:15:51 +00001291 // TODO: Find a case where the full set is actually helpful.
1292 if (SRange.isFullSet())
Tobias Grosser55bc4c02015-01-08 19:26:53 +00001293 continue;
1294
Johannes Doerferte7044942015-02-24 11:58:30 +00001295 Context = addRangeBoundsToSet(Context, SRange, dim, isl_dim_param);
Tobias Grosser18daaca2012-05-22 10:47:27 +00001296 }
1297}
1298
Tobias Grosser8cae72f2011-11-08 15:41:08 +00001299void Scop::realignParams() {
Tobias Grosser6be480c2011-11-08 15:41:13 +00001300 // Add all parameters into a common model.
Tobias Grosser60b54f12011-11-08 15:41:28 +00001301 isl_space *Space = isl_space_params_alloc(IslCtx, ParameterIds.size());
Tobias Grosser6be480c2011-11-08 15:41:13 +00001302
Tobias Grosser083d3d32014-06-28 08:59:45 +00001303 for (const auto &ParamID : ParameterIds) {
1304 const SCEV *Parameter = ParamID.first;
Tobias Grosser6be480c2011-11-08 15:41:13 +00001305 isl_id *id = getIdForParam(Parameter);
Tobias Grosser083d3d32014-06-28 08:59:45 +00001306 Space = isl_space_set_dim_id(Space, isl_dim_param, ParamID.second, id);
Tobias Grosser6be480c2011-11-08 15:41:13 +00001307 }
1308
1309 // Align the parameters of all data structures to the model.
1310 Context = isl_set_align_params(Context, Space);
1311
Tobias Grosser083d3d32014-06-28 08:59:45 +00001312 for (ScopStmt *Stmt : *this)
1313 Stmt->realignParams();
Tobias Grosser8cae72f2011-11-08 15:41:08 +00001314}
1315
Tobias Grosser5e6813d2014-07-02 17:47:48 +00001316void Scop::simplifyAssumedContext() {
1317 // The parameter constraints of the iteration domains give us a set of
1318 // constraints that need to hold for all cases where at least a single
1319 // statement iteration is executed in the whole scop. We now simplify the
1320 // assumed context under the assumption that such constraints hold and at
1321 // least a single statement iteration is executed. For cases where no
1322 // statement instances are executed, the assumptions we have taken about
1323 // the executed code do not matter and can be changed.
1324 //
1325 // WARNING: This only holds if the assumptions we have taken do not reduce
1326 // the set of statement instances that are executed. Otherwise we
1327 // may run into a case where the iteration domains suggest that
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00001328 // for a certain set of parameter constraints no code is executed,
Tobias Grosser5e6813d2014-07-02 17:47:48 +00001329 // but in the original program some computation would have been
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00001330 // performed. In such a case, modifying the run-time conditions and
1331 // possibly influencing the run-time check may cause certain scops
Tobias Grosser5e6813d2014-07-02 17:47:48 +00001332 // to not be executed.
1333 //
1334 // Example:
1335 //
1336 // When delinearizing the following code:
1337 //
1338 // for (long i = 0; i < 100; i++)
1339 // for (long j = 0; j < m; j++)
1340 // A[i+p][j] = 1.0;
1341 //
1342 // we assume that the condition m <= 0 or (m >= 1 and p >= 0) holds as
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00001343 // otherwise we would access out of bound data. Now, knowing that code is
Tobias Grosser5e6813d2014-07-02 17:47:48 +00001344 // only executed for the case m >= 0, it is sufficient to assume p >= 0.
1345 AssumedContext =
1346 isl_set_gist_params(AssumedContext, isl_union_set_params(getDomains()));
Johannes Doerfert4f8ac3d2015-02-23 16:15:51 +00001347 AssumedContext = isl_set_gist_params(AssumedContext, getContext());
Tobias Grosser5e6813d2014-07-02 17:47:48 +00001348}
1349
Johannes Doerfertb164c792014-09-18 11:17:17 +00001350/// @brief Add the minimal/maximal access in @p Set to @p User.
1351static int buildMinMaxAccess(__isl_take isl_set *Set, void *User) {
1352 Scop::MinMaxVectorTy *MinMaxAccesses = (Scop::MinMaxVectorTy *)User;
1353 isl_pw_multi_aff *MinPMA, *MaxPMA;
1354 isl_pw_aff *LastDimAff;
1355 isl_aff *OneAff;
1356 unsigned Pos;
1357
Johannes Doerfert9143d672014-09-27 11:02:39 +00001358 // Restrict the number of parameters involved in the access as the lexmin/
1359 // lexmax computation will take too long if this number is high.
1360 //
1361 // Experiments with a simple test case using an i7 4800MQ:
1362 //
1363 // #Parameters involved | Time (in sec)
1364 // 6 | 0.01
1365 // 7 | 0.04
1366 // 8 | 0.12
1367 // 9 | 0.40
1368 // 10 | 1.54
1369 // 11 | 6.78
1370 // 12 | 30.38
1371 //
1372 if (isl_set_n_param(Set) > RunTimeChecksMaxParameters) {
1373 unsigned InvolvedParams = 0;
1374 for (unsigned u = 0, e = isl_set_n_param(Set); u < e; u++)
1375 if (isl_set_involves_dims(Set, isl_dim_param, u, 1))
1376 InvolvedParams++;
1377
1378 if (InvolvedParams > RunTimeChecksMaxParameters) {
1379 isl_set_free(Set);
1380 return -1;
1381 }
1382 }
1383
Johannes Doerfertb6755bb2015-02-14 12:00:06 +00001384 Set = isl_set_remove_divs(Set);
1385
Johannes Doerfertb164c792014-09-18 11:17:17 +00001386 MinPMA = isl_set_lexmin_pw_multi_aff(isl_set_copy(Set));
1387 MaxPMA = isl_set_lexmax_pw_multi_aff(isl_set_copy(Set));
1388
Johannes Doerfert219b20e2014-10-07 14:37:59 +00001389 MinPMA = isl_pw_multi_aff_coalesce(MinPMA);
1390 MaxPMA = isl_pw_multi_aff_coalesce(MaxPMA);
1391
Johannes Doerfertb164c792014-09-18 11:17:17 +00001392 // Adjust the last dimension of the maximal access by one as we want to
1393 // enclose the accessed memory region by MinPMA and MaxPMA. The pointer
1394 // we test during code generation might now point after the end of the
1395 // allocated array but we will never dereference it anyway.
1396 assert(isl_pw_multi_aff_dim(MaxPMA, isl_dim_out) &&
1397 "Assumed at least one output dimension");
1398 Pos = isl_pw_multi_aff_dim(MaxPMA, isl_dim_out) - 1;
1399 LastDimAff = isl_pw_multi_aff_get_pw_aff(MaxPMA, Pos);
1400 OneAff = isl_aff_zero_on_domain(
1401 isl_local_space_from_space(isl_pw_aff_get_domain_space(LastDimAff)));
1402 OneAff = isl_aff_add_constant_si(OneAff, 1);
1403 LastDimAff = isl_pw_aff_add(LastDimAff, isl_pw_aff_from_aff(OneAff));
1404 MaxPMA = isl_pw_multi_aff_set_pw_aff(MaxPMA, Pos, LastDimAff);
1405
1406 MinMaxAccesses->push_back(std::make_pair(MinPMA, MaxPMA));
1407
1408 isl_set_free(Set);
1409 return 0;
1410}
1411
Johannes Doerferteeab05a2014-10-01 12:42:37 +00001412static __isl_give isl_set *getAccessDomain(MemoryAccess *MA) {
1413 isl_set *Domain = MA->getStatement()->getDomain();
1414 Domain = isl_set_project_out(Domain, isl_dim_set, 0, isl_set_n_dim(Domain));
1415 return isl_set_reset_tuple_id(Domain);
1416}
1417
Johannes Doerfert9143d672014-09-27 11:02:39 +00001418bool Scop::buildAliasGroups(AliasAnalysis &AA) {
Johannes Doerfertb164c792014-09-18 11:17:17 +00001419 // To create sound alias checks we perform the following steps:
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00001420 // o) Use the alias analysis and an alias set tracker to build alias sets
Johannes Doerfertb164c792014-09-18 11:17:17 +00001421 // for all memory accesses inside the SCoP.
1422 // o) For each alias set we then map the aliasing pointers back to the
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00001423 // memory accesses we know, thus obtain groups of memory accesses which
Johannes Doerfertb164c792014-09-18 11:17:17 +00001424 // might alias.
Johannes Doerferteeab05a2014-10-01 12:42:37 +00001425 // o) We divide each group based on the domains of the minimal/maximal
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00001426 // accesses. That means two minimal/maximal accesses are only in a group
Johannes Doerferteeab05a2014-10-01 12:42:37 +00001427 // if their access domains intersect, otherwise they are in different
1428 // ones.
Johannes Doerfert13771732014-10-01 12:40:46 +00001429 // o) We split groups such that they contain at most one read only base
1430 // address.
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00001431 // o) For each group with more than one base pointer we then compute minimal
Johannes Doerfertb164c792014-09-18 11:17:17 +00001432 // and maximal accesses to each array in this group.
1433 using AliasGroupTy = SmallVector<MemoryAccess *, 4>;
1434
1435 AliasSetTracker AST(AA);
1436
1437 DenseMap<Value *, MemoryAccess *> PtrToAcc;
Johannes Doerfert13771732014-10-01 12:40:46 +00001438 DenseSet<Value *> HasWriteAccess;
Johannes Doerfertb164c792014-09-18 11:17:17 +00001439 for (ScopStmt *Stmt : *this) {
Johannes Doerfertf1ee2622014-10-06 17:43:00 +00001440
1441 // Skip statements with an empty domain as they will never be executed.
1442 isl_set *StmtDomain = Stmt->getDomain();
1443 bool StmtDomainEmpty = isl_set_is_empty(StmtDomain);
1444 isl_set_free(StmtDomain);
1445 if (StmtDomainEmpty)
1446 continue;
1447
Johannes Doerfertb164c792014-09-18 11:17:17 +00001448 for (MemoryAccess *MA : *Stmt) {
1449 if (MA->isScalar())
1450 continue;
Johannes Doerfert13771732014-10-01 12:40:46 +00001451 if (!MA->isRead())
1452 HasWriteAccess.insert(MA->getBaseAddr());
Johannes Doerfertb164c792014-09-18 11:17:17 +00001453 Instruction *Acc = MA->getAccessInstruction();
1454 PtrToAcc[getPointerOperand(*Acc)] = MA;
1455 AST.add(Acc);
1456 }
1457 }
1458
1459 SmallVector<AliasGroupTy, 4> AliasGroups;
1460 for (AliasSet &AS : AST) {
Johannes Doerfert74f68692014-10-08 02:23:48 +00001461 if (AS.isMustAlias() || AS.isForwardingAliasSet())
Johannes Doerfertb164c792014-09-18 11:17:17 +00001462 continue;
1463 AliasGroupTy AG;
1464 for (auto PR : AS)
1465 AG.push_back(PtrToAcc[PR.getValue()]);
1466 assert(AG.size() > 1 &&
1467 "Alias groups should contain at least two accesses");
1468 AliasGroups.push_back(std::move(AG));
1469 }
1470
Johannes Doerferteeab05a2014-10-01 12:42:37 +00001471 // Split the alias groups based on their domain.
1472 for (unsigned u = 0; u < AliasGroups.size(); u++) {
1473 AliasGroupTy NewAG;
1474 AliasGroupTy &AG = AliasGroups[u];
1475 AliasGroupTy::iterator AGI = AG.begin();
1476 isl_set *AGDomain = getAccessDomain(*AGI);
1477 while (AGI != AG.end()) {
1478 MemoryAccess *MA = *AGI;
1479 isl_set *MADomain = getAccessDomain(MA);
1480 if (isl_set_is_disjoint(AGDomain, MADomain)) {
1481 NewAG.push_back(MA);
1482 AGI = AG.erase(AGI);
1483 isl_set_free(MADomain);
1484 } else {
1485 AGDomain = isl_set_union(AGDomain, MADomain);
1486 AGI++;
1487 }
1488 }
1489 if (NewAG.size() > 1)
1490 AliasGroups.push_back(std::move(NewAG));
1491 isl_set_free(AGDomain);
1492 }
1493
Johannes Doerfert13771732014-10-01 12:40:46 +00001494 DenseMap<const Value *, SmallPtrSet<MemoryAccess *, 8>> ReadOnlyPairs;
1495 SmallPtrSet<const Value *, 4> NonReadOnlyBaseValues;
1496 for (AliasGroupTy &AG : AliasGroups) {
1497 NonReadOnlyBaseValues.clear();
1498 ReadOnlyPairs.clear();
1499
Johannes Doerferteeab05a2014-10-01 12:42:37 +00001500 if (AG.size() < 2) {
1501 AG.clear();
1502 continue;
1503 }
1504
Johannes Doerfert13771732014-10-01 12:40:46 +00001505 for (auto II = AG.begin(); II != AG.end();) {
1506 Value *BaseAddr = (*II)->getBaseAddr();
1507 if (HasWriteAccess.count(BaseAddr)) {
1508 NonReadOnlyBaseValues.insert(BaseAddr);
1509 II++;
1510 } else {
1511 ReadOnlyPairs[BaseAddr].insert(*II);
1512 II = AG.erase(II);
1513 }
1514 }
1515
1516 // If we don't have read only pointers check if there are at least two
1517 // non read only pointers, otherwise clear the alias group.
1518 if (ReadOnlyPairs.empty()) {
1519 if (NonReadOnlyBaseValues.size() <= 1)
1520 AG.clear();
1521 continue;
1522 }
1523
1524 // If we don't have non read only pointers clear the alias group.
1525 if (NonReadOnlyBaseValues.empty()) {
1526 AG.clear();
1527 continue;
1528 }
1529
1530 // If we have both read only and non read only base pointers we combine
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00001531 // the non read only ones with exactly one read only one at a time into a
Johannes Doerfert13771732014-10-01 12:40:46 +00001532 // new alias group and clear the old alias group in the end.
1533 for (const auto &ReadOnlyPair : ReadOnlyPairs) {
1534 AliasGroupTy AGNonReadOnly = AG;
1535 for (MemoryAccess *MA : ReadOnlyPair.second)
1536 AGNonReadOnly.push_back(MA);
1537 AliasGroups.push_back(std::move(AGNonReadOnly));
1538 }
1539 AG.clear();
Johannes Doerfertb164c792014-09-18 11:17:17 +00001540 }
1541
1542 for (AliasGroupTy &AG : AliasGroups) {
Johannes Doerfert13771732014-10-01 12:40:46 +00001543 if (AG.empty())
1544 continue;
1545
Johannes Doerfertb164c792014-09-18 11:17:17 +00001546 MinMaxVectorTy *MinMaxAccesses = new MinMaxVectorTy();
1547 MinMaxAccesses->reserve(AG.size());
1548
1549 isl_union_map *Accesses = isl_union_map_empty(getParamSpace());
1550 for (MemoryAccess *MA : AG)
1551 Accesses = isl_union_map_add_map(Accesses, MA->getAccessRelation());
1552 Accesses = isl_union_map_intersect_domain(Accesses, getDomains());
1553
1554 isl_union_set *Locations = isl_union_map_range(Accesses);
1555 Locations = isl_union_set_intersect_params(Locations, getAssumedContext());
1556 Locations = isl_union_set_coalesce(Locations);
1557 Locations = isl_union_set_detect_equalities(Locations);
Tobias Grosser50d4e2e2015-03-28 14:50:32 +00001558 bool Valid = (0 == isl_union_set_foreach_set(Locations, buildMinMaxAccess,
1559 MinMaxAccesses));
Johannes Doerfertb164c792014-09-18 11:17:17 +00001560 isl_union_set_free(Locations);
Johannes Doerfertb164c792014-09-18 11:17:17 +00001561 MinMaxAliasGroups.push_back(MinMaxAccesses);
Johannes Doerfert9143d672014-09-27 11:02:39 +00001562
1563 if (!Valid)
Tobias Grosser50d4e2e2015-03-28 14:50:32 +00001564 return false;
Johannes Doerfertb164c792014-09-18 11:17:17 +00001565 }
Johannes Doerfert9143d672014-09-27 11:02:39 +00001566
Tobias Grosser71500722015-03-28 15:11:14 +00001567 // Bail out if the number of values we need to compare is too large.
1568 // This is important as the number of comparisions grows quadratically with
1569 // the number of values we need to compare.
1570 for (const auto *Values : MinMaxAliasGroups)
1571 if (Values->size() > RunTimeChecksMaxArraysPerGroup)
1572 return false;
1573
Tobias Grosser50d4e2e2015-03-28 14:50:32 +00001574 return true;
Johannes Doerfertb164c792014-09-18 11:17:17 +00001575}
1576
Johannes Doerferte3da05a2014-11-01 00:12:13 +00001577static unsigned getMaxLoopDepthInRegion(const Region &R, LoopInfo &LI) {
1578 unsigned MinLD = INT_MAX, MaxLD = 0;
1579 for (BasicBlock *BB : R.blocks()) {
1580 if (Loop *L = LI.getLoopFor(BB)) {
David Peixottodc0a11c2015-01-13 18:31:55 +00001581 if (!R.contains(L))
1582 continue;
Johannes Doerferte3da05a2014-11-01 00:12:13 +00001583 unsigned LD = L->getLoopDepth();
1584 MinLD = std::min(MinLD, LD);
1585 MaxLD = std::max(MaxLD, LD);
1586 }
1587 }
1588
1589 // Handle the case that there is no loop in the SCoP first.
1590 if (MaxLD == 0)
1591 return 1;
1592
1593 assert(MinLD >= 1 && "Minimal loop depth should be at least one");
1594 assert(MaxLD >= MinLD &&
1595 "Maximal loop depth was smaller than mininaml loop depth?");
1596 return MaxLD - MinLD + 1;
1597}
1598
Tobias Grosser3f296192015-01-01 23:01:11 +00001599void Scop::dropConstantScheduleDims() {
1600 isl_union_map *FullSchedule = getSchedule();
1601
1602 if (isl_union_map_n_map(FullSchedule) == 0) {
1603 isl_union_map_free(FullSchedule);
1604 return;
1605 }
1606
1607 isl_set *ScheduleSpace =
1608 isl_set_from_union_set(isl_union_map_range(FullSchedule));
1609 isl_map *DropDimMap = isl_set_identity(isl_set_copy(ScheduleSpace));
1610
1611 int NumDimsDropped = 0;
Johannes Doerfert3f21e272015-03-04 22:23:21 +00001612 for (unsigned i = 0; i < isl_set_dim(ScheduleSpace, isl_dim_set); i += 2) {
1613 isl_val *FixedVal =
1614 isl_set_plain_get_val_if_fixed(ScheduleSpace, isl_dim_set, i);
1615 if (isl_val_is_int(FixedVal)) {
1616 DropDimMap =
1617 isl_map_project_out(DropDimMap, isl_dim_out, i - NumDimsDropped, 1);
1618 NumDimsDropped++;
Tobias Grosser3f296192015-01-01 23:01:11 +00001619 }
Johannes Doerfert3f21e272015-03-04 22:23:21 +00001620 isl_val_free(FixedVal);
1621 }
Tobias Grosser3f296192015-01-01 23:01:11 +00001622
Tobias Grosser3f296192015-01-01 23:01:11 +00001623 for (auto *S : *this) {
1624 isl_map *Schedule = S->getScattering();
1625 Schedule = isl_map_apply_range(Schedule, isl_map_copy(DropDimMap));
1626 S->setScattering(Schedule);
1627 }
1628 isl_set_free(ScheduleSpace);
1629 isl_map_free(DropDimMap);
1630}
1631
Tobias Grosser0e27e242011-10-06 00:03:48 +00001632Scop::Scop(TempScop &tempScop, LoopInfo &LI, ScalarEvolution &ScalarEvolution,
Johannes Doerfertff9d1982015-02-24 12:00:50 +00001633 ScopDetection &SD, isl_ctx *Context)
Johannes Doerfert7ceb0402015-02-11 17:25:09 +00001634 : SE(&ScalarEvolution), R(tempScop.getMaxRegion()), IsOptimized(false),
Johannes Doerferte3da05a2014-11-01 00:12:13 +00001635 MaxLoopDepth(getMaxLoopDepthInRegion(tempScop.getMaxRegion(), LI)) {
Tobias Grosser9a38ab82011-11-08 15:41:03 +00001636 IslCtx = Context;
Johannes Doerfertff9d1982015-02-24 12:00:50 +00001637
Tobias Grosser6be480c2011-11-08 15:41:13 +00001638 buildContext();
Tobias Grosser75805372011-04-29 06:27:02 +00001639
Tobias Grosserabfbe632013-02-05 12:09:06 +00001640 SmallVector<Loop *, 8> NestLoops;
Tobias Grosser75805372011-04-29 06:27:02 +00001641 SmallVector<unsigned, 8> Scatter;
1642
1643 Scatter.assign(MaxLoopDepth + 1, 0);
1644
1645 // Build the iteration domain, access functions and scattering functions
1646 // traversing the region tree.
Johannes Doerfertff9d1982015-02-24 12:00:50 +00001647 buildScop(tempScop, getRegion(), NestLoops, Scatter, LI, SD);
Tobias Grosser75805372011-04-29 06:27:02 +00001648
Tobias Grosser8cae72f2011-11-08 15:41:08 +00001649 realignParams();
Tobias Grosser18daaca2012-05-22 10:47:27 +00001650 addParameterBounds();
Tobias Grosser5e6813d2014-07-02 17:47:48 +00001651 simplifyAssumedContext();
Tobias Grosser3f296192015-01-01 23:01:11 +00001652 dropConstantScheduleDims();
Tobias Grosser8cae72f2011-11-08 15:41:08 +00001653
Tobias Grosser75805372011-04-29 06:27:02 +00001654 assert(NestLoops.empty() && "NestLoops not empty at top level!");
1655}
1656
1657Scop::~Scop() {
1658 isl_set_free(Context);
Tobias Grossere86109f2013-10-29 21:05:49 +00001659 isl_set_free(AssumedContext);
Tobias Grosser75805372011-04-29 06:27:02 +00001660
1661 // Free the statements;
Tobias Grosser083d3d32014-06-28 08:59:45 +00001662 for (ScopStmt *Stmt : *this)
1663 delete Stmt;
Johannes Doerfertb164c792014-09-18 11:17:17 +00001664
Johannes Doerfert1a28a892014-10-05 11:32:18 +00001665 // Free the ScopArrayInfo objects.
1666 for (auto &ScopArrayInfoPair : ScopArrayInfoMap)
1667 delete ScopArrayInfoPair.second;
1668
Johannes Doerfertb164c792014-09-18 11:17:17 +00001669 // Free the alias groups
1670 for (MinMaxVectorTy *MinMaxAccesses : MinMaxAliasGroups) {
1671 for (MinMaxAccessTy &MMA : *MinMaxAccesses) {
1672 isl_pw_multi_aff_free(MMA.first);
1673 isl_pw_multi_aff_free(MMA.second);
1674 }
1675 delete MinMaxAccesses;
1676 }
Tobias Grosser75805372011-04-29 06:27:02 +00001677}
1678
Johannes Doerfert80ef1102014-11-07 08:31:31 +00001679const ScopArrayInfo *
1680Scop::getOrCreateScopArrayInfo(Value *BasePtr, Type *AccessType,
1681 const SmallVector<const SCEV *, 4> &Sizes) {
Johannes Doerfert1a28a892014-10-05 11:32:18 +00001682 const ScopArrayInfo *&SAI = ScopArrayInfoMap[BasePtr];
Johannes Doerfert80ef1102014-11-07 08:31:31 +00001683 if (!SAI)
1684 SAI = new ScopArrayInfo(BasePtr, AccessType, getIslCtx(), Sizes);
Johannes Doerfert1a28a892014-10-05 11:32:18 +00001685 return SAI;
1686}
1687
1688const ScopArrayInfo *Scop::getScopArrayInfo(Value *BasePtr) {
1689 const SCEV *PtrSCEV = SE->getSCEV(BasePtr);
1690 const SCEVUnknown *PtrBaseSCEV =
1691 cast<SCEVUnknown>(SE->getPointerBase(PtrSCEV));
1692 const ScopArrayInfo *SAI = ScopArrayInfoMap[PtrBaseSCEV->getValue()];
1693 assert(SAI && "No ScopArrayInfo available for this base pointer");
1694 return SAI;
1695}
1696
Tobias Grosser74394f02013-01-14 22:40:23 +00001697std::string Scop::getContextStr() const { return stringFromIslObj(Context); }
Tobias Grosser5e6813d2014-07-02 17:47:48 +00001698std::string Scop::getAssumedContextStr() const {
1699 return stringFromIslObj(AssumedContext);
1700}
Tobias Grosser75805372011-04-29 06:27:02 +00001701
1702std::string Scop::getNameStr() const {
1703 std::string ExitName, EntryName;
1704 raw_string_ostream ExitStr(ExitName);
1705 raw_string_ostream EntryStr(EntryName);
1706
Tobias Grosserf240b482014-01-09 10:42:15 +00001707 R.getEntry()->printAsOperand(EntryStr, false);
Tobias Grosser75805372011-04-29 06:27:02 +00001708 EntryStr.str();
1709
1710 if (R.getExit()) {
Tobias Grosserf240b482014-01-09 10:42:15 +00001711 R.getExit()->printAsOperand(ExitStr, false);
Tobias Grosser75805372011-04-29 06:27:02 +00001712 ExitStr.str();
1713 } else
1714 ExitName = "FunctionExit";
1715
1716 return EntryName + "---" + ExitName;
1717}
1718
Tobias Grosser74394f02013-01-14 22:40:23 +00001719__isl_give isl_set *Scop::getContext() const { return isl_set_copy(Context); }
Tobias Grosser37487052011-10-06 00:03:42 +00001720__isl_give isl_space *Scop::getParamSpace() const {
1721 return isl_set_get_space(this->Context);
1722}
1723
Tobias Grossere86109f2013-10-29 21:05:49 +00001724__isl_give isl_set *Scop::getAssumedContext() const {
1725 return isl_set_copy(AssumedContext);
1726}
1727
Tobias Grosser5e6813d2014-07-02 17:47:48 +00001728void Scop::addAssumption(__isl_take isl_set *Set) {
1729 AssumedContext = isl_set_intersect(AssumedContext, Set);
Tobias Grosser7b50bee2014-11-25 10:51:12 +00001730 AssumedContext = isl_set_coalesce(AssumedContext);
Tobias Grosser5e6813d2014-07-02 17:47:48 +00001731}
1732
Tobias Grosser75805372011-04-29 06:27:02 +00001733void Scop::printContext(raw_ostream &OS) const {
1734 OS << "Context:\n";
1735
1736 if (!Context) {
1737 OS.indent(4) << "n/a\n\n";
1738 return;
1739 }
1740
1741 OS.indent(4) << getContextStr() << "\n";
Tobias Grosser60b54f12011-11-08 15:41:28 +00001742
Tobias Grosser5e6813d2014-07-02 17:47:48 +00001743 OS.indent(4) << "Assumed Context:\n";
1744 if (!AssumedContext) {
1745 OS.indent(4) << "n/a\n\n";
1746 return;
1747 }
1748
1749 OS.indent(4) << getAssumedContextStr() << "\n";
1750
Tobias Grosser083d3d32014-06-28 08:59:45 +00001751 for (const SCEV *Parameter : Parameters) {
Tobias Grosser60b54f12011-11-08 15:41:28 +00001752 int Dim = ParameterIds.find(Parameter)->second;
Tobias Grosser60b54f12011-11-08 15:41:28 +00001753 OS.indent(4) << "p" << Dim << ": " << *Parameter << "\n";
1754 }
Tobias Grosser75805372011-04-29 06:27:02 +00001755}
1756
Johannes Doerfertb164c792014-09-18 11:17:17 +00001757void Scop::printAliasAssumptions(raw_ostream &OS) const {
1758 OS.indent(4) << "Alias Groups (" << MinMaxAliasGroups.size() << "):\n";
1759 if (MinMaxAliasGroups.empty()) {
1760 OS.indent(8) << "n/a\n";
1761 return;
1762 }
1763 for (MinMaxVectorTy *MinMaxAccesses : MinMaxAliasGroups) {
1764 OS.indent(8) << "[[";
1765 for (MinMaxAccessTy &MinMacAccess : *MinMaxAccesses)
1766 OS << " <" << MinMacAccess.first << ", " << MinMacAccess.second << ">";
1767 OS << " ]]\n";
1768 }
1769}
1770
Tobias Grosser75805372011-04-29 06:27:02 +00001771void Scop::printStatements(raw_ostream &OS) const {
1772 OS << "Statements {\n";
1773
Tobias Grosser083d3d32014-06-28 08:59:45 +00001774 for (ScopStmt *Stmt : *this)
1775 OS.indent(4) << *Stmt;
Tobias Grosser75805372011-04-29 06:27:02 +00001776
1777 OS.indent(4) << "}\n";
1778}
1779
Tobias Grosser75805372011-04-29 06:27:02 +00001780void Scop::print(raw_ostream &OS) const {
Tobias Grosser4eb7ddb2014-03-18 18:51:11 +00001781 OS.indent(4) << "Function: " << getRegion().getEntry()->getParent()->getName()
1782 << "\n";
Tobias Grosser483fdd42014-03-18 18:05:38 +00001783 OS.indent(4) << "Region: " << getNameStr() << "\n";
David Peixottodc0a11c2015-01-13 18:31:55 +00001784 OS.indent(4) << "Max Loop Depth: " << getMaxLoopDepth() << "\n";
Tobias Grosser75805372011-04-29 06:27:02 +00001785 printContext(OS.indent(4));
Johannes Doerfertb164c792014-09-18 11:17:17 +00001786 printAliasAssumptions(OS);
Tobias Grosser75805372011-04-29 06:27:02 +00001787 printStatements(OS.indent(4));
1788}
1789
1790void Scop::dump() const { print(dbgs()); }
1791
Tobias Grosser9a38ab82011-11-08 15:41:03 +00001792isl_ctx *Scop::getIslCtx() const { return IslCtx; }
Tobias Grosser75805372011-04-29 06:27:02 +00001793
Tobias Grosser5f9a7622012-02-14 14:02:40 +00001794__isl_give isl_union_set *Scop::getDomains() {
Tobias Grosserbc4ef902014-06-28 08:59:38 +00001795 isl_union_set *Domain = isl_union_set_empty(getParamSpace());
Tobias Grosser5f9a7622012-02-14 14:02:40 +00001796
Tobias Grosserbc4ef902014-06-28 08:59:38 +00001797 for (ScopStmt *Stmt : *this)
1798 Domain = isl_union_set_add_set(Domain, Stmt->getDomain());
Tobias Grosser5f9a7622012-02-14 14:02:40 +00001799
1800 return Domain;
1801}
1802
Tobias Grosser780ce0f2014-07-11 07:12:10 +00001803__isl_give isl_union_map *Scop::getMustWrites() {
1804 isl_union_map *Write = isl_union_map_empty(this->getParamSpace());
1805
1806 for (ScopStmt *Stmt : *this) {
1807 for (MemoryAccess *MA : *Stmt) {
1808 if (!MA->isMustWrite())
1809 continue;
1810
1811 isl_set *Domain = Stmt->getDomain();
1812 isl_map *AccessDomain = MA->getAccessRelation();
1813 AccessDomain = isl_map_intersect_domain(AccessDomain, Domain);
1814 Write = isl_union_map_add_map(Write, AccessDomain);
1815 }
1816 }
1817 return isl_union_map_coalesce(Write);
1818}
1819
1820__isl_give isl_union_map *Scop::getMayWrites() {
1821 isl_union_map *Write = isl_union_map_empty(this->getParamSpace());
1822
1823 for (ScopStmt *Stmt : *this) {
1824 for (MemoryAccess *MA : *Stmt) {
1825 if (!MA->isMayWrite())
1826 continue;
1827
1828 isl_set *Domain = Stmt->getDomain();
1829 isl_map *AccessDomain = MA->getAccessRelation();
1830 AccessDomain = isl_map_intersect_domain(AccessDomain, Domain);
1831 Write = isl_union_map_add_map(Write, AccessDomain);
1832 }
1833 }
1834 return isl_union_map_coalesce(Write);
1835}
1836
Tobias Grosser37eb4222014-02-20 21:43:54 +00001837__isl_give isl_union_map *Scop::getWrites() {
1838 isl_union_map *Write = isl_union_map_empty(this->getParamSpace());
1839
Tobias Grosserbc4ef902014-06-28 08:59:38 +00001840 for (ScopStmt *Stmt : *this) {
Johannes Doerfertf6752892014-06-13 18:01:45 +00001841 for (MemoryAccess *MA : *Stmt) {
1842 if (!MA->isWrite())
Tobias Grosser37eb4222014-02-20 21:43:54 +00001843 continue;
1844
1845 isl_set *Domain = Stmt->getDomain();
Johannes Doerfertf6752892014-06-13 18:01:45 +00001846 isl_map *AccessDomain = MA->getAccessRelation();
Tobias Grosser37eb4222014-02-20 21:43:54 +00001847 AccessDomain = isl_map_intersect_domain(AccessDomain, Domain);
1848 Write = isl_union_map_add_map(Write, AccessDomain);
1849 }
1850 }
1851 return isl_union_map_coalesce(Write);
1852}
1853
1854__isl_give isl_union_map *Scop::getReads() {
Tobias Grosserbc4ef902014-06-28 08:59:38 +00001855 isl_union_map *Read = isl_union_map_empty(getParamSpace());
Tobias Grosser37eb4222014-02-20 21:43:54 +00001856
Tobias Grosserbc4ef902014-06-28 08:59:38 +00001857 for (ScopStmt *Stmt : *this) {
Johannes Doerfertf6752892014-06-13 18:01:45 +00001858 for (MemoryAccess *MA : *Stmt) {
1859 if (!MA->isRead())
Tobias Grosser37eb4222014-02-20 21:43:54 +00001860 continue;
1861
1862 isl_set *Domain = Stmt->getDomain();
Johannes Doerfertf6752892014-06-13 18:01:45 +00001863 isl_map *AccessDomain = MA->getAccessRelation();
Tobias Grosser37eb4222014-02-20 21:43:54 +00001864
1865 AccessDomain = isl_map_intersect_domain(AccessDomain, Domain);
1866 Read = isl_union_map_add_map(Read, AccessDomain);
1867 }
1868 }
1869 return isl_union_map_coalesce(Read);
1870}
1871
1872__isl_give isl_union_map *Scop::getSchedule() {
Tobias Grosserbc4ef902014-06-28 08:59:38 +00001873 isl_union_map *Schedule = isl_union_map_empty(getParamSpace());
Tobias Grosser37eb4222014-02-20 21:43:54 +00001874
Tobias Grosserbc4ef902014-06-28 08:59:38 +00001875 for (ScopStmt *Stmt : *this)
Tobias Grosser37eb4222014-02-20 21:43:54 +00001876 Schedule = isl_union_map_add_map(Schedule, Stmt->getScattering());
Tobias Grosserbc4ef902014-06-28 08:59:38 +00001877
Tobias Grosser37eb4222014-02-20 21:43:54 +00001878 return isl_union_map_coalesce(Schedule);
1879}
1880
1881bool Scop::restrictDomains(__isl_take isl_union_set *Domain) {
1882 bool Changed = false;
Tobias Grosserbc4ef902014-06-28 08:59:38 +00001883 for (ScopStmt *Stmt : *this) {
Tobias Grosser37eb4222014-02-20 21:43:54 +00001884 isl_union_set *StmtDomain = isl_union_set_from_set(Stmt->getDomain());
Tobias Grosser37eb4222014-02-20 21:43:54 +00001885 isl_union_set *NewStmtDomain = isl_union_set_intersect(
1886 isl_union_set_copy(StmtDomain), isl_union_set_copy(Domain));
1887
1888 if (isl_union_set_is_subset(StmtDomain, NewStmtDomain)) {
1889 isl_union_set_free(StmtDomain);
1890 isl_union_set_free(NewStmtDomain);
1891 continue;
1892 }
1893
1894 Changed = true;
1895
1896 isl_union_set_free(StmtDomain);
1897 NewStmtDomain = isl_union_set_coalesce(NewStmtDomain);
1898
1899 if (isl_union_set_is_empty(NewStmtDomain)) {
1900 Stmt->restrictDomain(isl_set_empty(Stmt->getDomainSpace()));
1901 isl_union_set_free(NewStmtDomain);
1902 } else
1903 Stmt->restrictDomain(isl_set_from_union_set(NewStmtDomain));
1904 }
1905 isl_union_set_free(Domain);
1906 return Changed;
1907}
1908
Tobias Grosser75805372011-04-29 06:27:02 +00001909ScalarEvolution *Scop::getSE() const { return SE; }
1910
1911bool Scop::isTrivialBB(BasicBlock *BB, TempScop &tempScop) {
1912 if (tempScop.getAccessFunctions(BB))
1913 return false;
1914
1915 return true;
1916}
1917
Johannes Doerfertff9d1982015-02-24 12:00:50 +00001918void Scop::addScopStmt(BasicBlock *BB, Region *R, TempScop &tempScop,
1919 const Region &CurRegion,
1920 SmallVectorImpl<Loop *> &NestLoops,
1921 SmallVectorImpl<unsigned> &Scatter) {
1922 ScopStmt *Stmt;
1923
1924 if (BB) {
1925 Stmt = new ScopStmt(*this, tempScop, CurRegion, *BB, NestLoops, Scatter);
1926 StmtMap[BB] = Stmt;
1927 } else {
1928 assert(R && "Either a basic block or a region is needed to "
1929 "create a new SCoP stmt.");
1930 Stmt = new ScopStmt(*this, tempScop, CurRegion, *R, NestLoops, Scatter);
1931 for (BasicBlock *BB : R->blocks())
1932 StmtMap[BB] = Stmt;
1933 }
1934
1935 // Insert all statements into the statement map and the statement vector.
1936 Stmts.push_back(Stmt);
1937
1938 // Increasing the Scattering function is OK for the moment, because
1939 // we are using a depth first iterator and the program is well structured.
1940 ++Scatter[NestLoops.size()];
1941}
1942
Tobias Grosser74394f02013-01-14 22:40:23 +00001943void Scop::buildScop(TempScop &tempScop, const Region &CurRegion,
1944 SmallVectorImpl<Loop *> &NestLoops,
Johannes Doerfertff9d1982015-02-24 12:00:50 +00001945 SmallVectorImpl<unsigned> &Scatter, LoopInfo &LI,
1946 ScopDetection &SD) {
1947 if (SD.isNonAffineSubRegion(&CurRegion, &getRegion()))
1948 return addScopStmt(nullptr, const_cast<Region *>(&CurRegion), tempScop,
1949 CurRegion, NestLoops, Scatter);
1950
Tobias Grosser75805372011-04-29 06:27:02 +00001951 Loop *L = castToLoop(CurRegion, LI);
1952
1953 if (L)
1954 NestLoops.push_back(L);
1955
1956 unsigned loopDepth = NestLoops.size();
1957 assert(Scatter.size() > loopDepth && "Scatter not big enough!");
1958
1959 for (Region::const_element_iterator I = CurRegion.element_begin(),
Tobias Grosserabfbe632013-02-05 12:09:06 +00001960 E = CurRegion.element_end();
1961 I != E; ++I)
Johannes Doerfertff9d1982015-02-24 12:00:50 +00001962 if (I->isSubRegion()) {
1963 buildScop(tempScop, *I->getNodeAs<Region>(), NestLoops, Scatter, LI, SD);
1964 } else {
Tobias Grosser75805372011-04-29 06:27:02 +00001965 BasicBlock *BB = I->getNodeAs<BasicBlock>();
1966
1967 if (isTrivialBB(BB, tempScop))
1968 continue;
1969
Johannes Doerfertff9d1982015-02-24 12:00:50 +00001970 addScopStmt(BB, nullptr, tempScop, CurRegion, NestLoops, Scatter);
Tobias Grosser75805372011-04-29 06:27:02 +00001971 }
1972
1973 if (!L)
1974 return;
1975
1976 // Exiting a loop region.
1977 Scatter[loopDepth] = 0;
1978 NestLoops.pop_back();
Tobias Grosser74394f02013-01-14 22:40:23 +00001979 ++Scatter[loopDepth - 1];
Tobias Grosser75805372011-04-29 06:27:02 +00001980}
1981
Johannes Doerfert7c494212014-10-31 23:13:39 +00001982ScopStmt *Scop::getStmtForBasicBlock(BasicBlock *BB) const {
1983 const auto &StmtMapIt = StmtMap.find(BB);
1984 if (StmtMapIt == StmtMap.end())
1985 return nullptr;
1986 return StmtMapIt->second;
1987}
1988
Tobias Grosser75805372011-04-29 06:27:02 +00001989//===----------------------------------------------------------------------===//
Tobias Grosserb76f38532011-08-20 11:11:25 +00001990ScopInfo::ScopInfo() : RegionPass(ID), scop(0) {
1991 ctx = isl_ctx_alloc();
Tobias Grosser4a8e3562011-12-07 07:42:51 +00001992 isl_options_set_on_error(ctx, ISL_ON_ERROR_ABORT);
Tobias Grosserb76f38532011-08-20 11:11:25 +00001993}
1994
1995ScopInfo::~ScopInfo() {
1996 clear();
1997 isl_ctx_free(ctx);
1998}
1999
Tobias Grosser75805372011-04-29 06:27:02 +00002000void ScopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
Chandler Carruthf5579872015-01-17 14:16:56 +00002001 AU.addRequired<LoopInfoWrapperPass>();
Matt Arsenault8ca36812014-07-19 18:40:17 +00002002 AU.addRequired<RegionInfoPass>();
Tobias Grosser75805372011-04-29 06:27:02 +00002003 AU.addRequired<ScalarEvolution>();
Johannes Doerfertff9d1982015-02-24 12:00:50 +00002004 AU.addRequired<ScopDetection>();
Tobias Grosser75805372011-04-29 06:27:02 +00002005 AU.addRequired<TempScopInfo>();
Johannes Doerfertb164c792014-09-18 11:17:17 +00002006 AU.addRequired<AliasAnalysis>();
Tobias Grosser75805372011-04-29 06:27:02 +00002007 AU.setPreservesAll();
2008}
2009
2010bool ScopInfo::runOnRegion(Region *R, RGPassManager &RGM) {
Chandler Carruthf5579872015-01-17 14:16:56 +00002011 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
Johannes Doerfertb164c792014-09-18 11:17:17 +00002012 AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
Johannes Doerfertff9d1982015-02-24 12:00:50 +00002013 ScopDetection &SD = getAnalysis<ScopDetection>();
Tobias Grosser75805372011-04-29 06:27:02 +00002014 ScalarEvolution &SE = getAnalysis<ScalarEvolution>();
2015
2016 TempScop *tempScop = getAnalysis<TempScopInfo>().getTempScop(R);
2017
2018 // This region is no Scop.
2019 if (!tempScop) {
Tobias Grosserc98a8fc2014-11-14 11:12:31 +00002020 scop = nullptr;
Tobias Grosser75805372011-04-29 06:27:02 +00002021 return false;
2022 }
2023
Johannes Doerfertff9d1982015-02-24 12:00:50 +00002024 scop = new Scop(*tempScop, LI, SE, SD, ctx);
Tobias Grosser75805372011-04-29 06:27:02 +00002025
Johannes Doerfert21aa3dc2014-11-01 01:30:11 +00002026 if (!PollyUseRuntimeAliasChecks) {
2027 // Statistics.
2028 ++ScopFound;
2029 if (scop->getMaxLoopDepth() > 0)
2030 ++RichScopFound;
Johannes Doerfert9143d672014-09-27 11:02:39 +00002031 return false;
Johannes Doerfert21aa3dc2014-11-01 01:30:11 +00002032 }
Johannes Doerfertb164c792014-09-18 11:17:17 +00002033
Johannes Doerfert9143d672014-09-27 11:02:39 +00002034 // If a problem occurs while building the alias groups we need to delete
2035 // this SCoP and pretend it wasn't valid in the first place.
Johannes Doerfert21aa3dc2014-11-01 01:30:11 +00002036 if (scop->buildAliasGroups(AA)) {
2037 // Statistics.
2038 ++ScopFound;
2039 if (scop->getMaxLoopDepth() > 0)
2040 ++RichScopFound;
Johannes Doerfert9143d672014-09-27 11:02:39 +00002041 return false;
Johannes Doerfert21aa3dc2014-11-01 01:30:11 +00002042 }
Johannes Doerfert9143d672014-09-27 11:02:39 +00002043
2044 DEBUG(dbgs()
2045 << "\n\nNOTE: Run time checks for " << scop->getNameStr()
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00002046 << " could not be created as the number of parameters involved is too "
Johannes Doerfert9143d672014-09-27 11:02:39 +00002047 "high. The SCoP will be "
2048 "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust the "
Johannes Doerfert6cad9c42015-02-24 16:00:29 +00002049 "maximal number of parameters but be advised that the compile time "
Johannes Doerfert9143d672014-09-27 11:02:39 +00002050 "might increase exponentially.\n\n");
2051
2052 delete scop;
2053 scop = nullptr;
Tobias Grosser75805372011-04-29 06:27:02 +00002054 return false;
2055}
2056
2057char ScopInfo::ID = 0;
2058
Tobias Grosser4d96c8d2013-03-23 01:05:07 +00002059Pass *polly::createScopInfoPass() { return new ScopInfo(); }
2060
Tobias Grosser73600b82011-10-08 00:30:40 +00002061INITIALIZE_PASS_BEGIN(ScopInfo, "polly-scops",
2062 "Polly - Create polyhedral description of Scops", false,
Tobias Grosser4d96c8d2013-03-23 01:05:07 +00002063 false);
Johannes Doerfertb164c792014-09-18 11:17:17 +00002064INITIALIZE_AG_DEPENDENCY(AliasAnalysis);
Chandler Carruthf5579872015-01-17 14:16:56 +00002065INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
Matt Arsenault8ca36812014-07-19 18:40:17 +00002066INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
Tobias Grosser4d96c8d2013-03-23 01:05:07 +00002067INITIALIZE_PASS_DEPENDENCY(ScalarEvolution);
Johannes Doerfertff9d1982015-02-24 12:00:50 +00002068INITIALIZE_PASS_DEPENDENCY(ScopDetection);
Tobias Grosser4d96c8d2013-03-23 01:05:07 +00002069INITIALIZE_PASS_DEPENDENCY(TempScopInfo);
Tobias Grosser73600b82011-10-08 00:30:40 +00002070INITIALIZE_PASS_END(ScopInfo, "polly-scops",
2071 "Polly - Create polyhedral description of Scops", false,
2072 false)