1//===--------- SCEVAffinator.cpp - Create Scops from LLVM IR -------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Create a polyhedral description for a SCEV value.
10//
11//===----------------------------------------------------------------------===//
12
13#include "polly/Support/SCEVAffinator.h"
14#include "polly/Options.h"
15#include "polly/ScopInfo.h"
16#include "polly/Support/GICHelper.h"
17#include "polly/Support/SCEVValidator.h"
18#include "llvm/IR/DataLayout.h"
19#include "isl/aff.h"
20#include "isl/local_space.h"
21#include "isl/set.h"
22#include "isl/val.h"
23
24using namespace llvm;
25using namespace polly;
26
27static cl::opt<bool> IgnoreIntegerWrapping(
28 "polly-ignore-integer-wrapping",
29 cl::desc("Do not build run-time checks to proof absence of integer "
30 "wrapping"),
31 cl::Hidden, cl::cat(PollyCategory));
32
33// The maximal number of basic sets we allow during the construction of a
34// piecewise affine function. More complex ones will result in very high
35// compile time.
36static int const MaxDisjunctionsInPwAff = 100;
37
38// The maximal number of bits for which a general expression is modeled
39// precisely.
40static unsigned const MaxSmallBitWidth = 7;
41
42/// Add the number of basic sets in @p Domain to @p User
43static isl_stat addNumBasicSets(__isl_take isl_set *Domain,
44 __isl_take isl_aff *Aff, void *User) {
45 auto *NumBasicSets = static_cast<unsigned *>(User);
46 *NumBasicSets += isl_set_n_basic_set(set: Domain);
47 isl_set_free(set: Domain);
48 isl_aff_free(aff: Aff);
49 return isl_stat_ok;
50}
51
52/// Determine if @p PWAC is too complex to continue.
53static bool isTooComplex(PWACtx PWAC) {
54 unsigned NumBasicSets = 0;
55 isl_pw_aff_foreach_piece(pwaff: PWAC.first.get(), fn: addNumBasicSets, user: &NumBasicSets);
56 if (NumBasicSets <= MaxDisjunctionsInPwAff)
57 return false;
58 return true;
59}
60
61/// Return the flag describing the possible wrapping of @p Expr.
62static SCEV::NoWrapFlags getNoWrapFlags(const SCEV *Expr) {
63 if (auto *NAry = dyn_cast<SCEVNAryExpr>(Val: Expr))
64 return NAry->getNoWrapFlags();
65 return SCEV::NoWrapMask;
66}
67
68static PWACtx combine(PWACtx PWAC0, PWACtx PWAC1,
69 __isl_give isl_pw_aff *(Fn)(__isl_take isl_pw_aff *,
70 __isl_take isl_pw_aff *)) {
71 PWAC0.first = isl::manage(ptr: Fn(PWAC0.first.release(), PWAC1.first.release()));
72 PWAC0.second = PWAC0.second.unite(set2: PWAC1.second);
73 return PWAC0;
74}
75
76static __isl_give isl_pw_aff *getWidthExpValOnDomain(unsigned Width,
77 __isl_take isl_set *Dom) {
78 auto *Ctx = isl_set_get_ctx(set: Dom);
79 auto *WidthVal = isl_val_int_from_ui(ctx: Ctx, u: Width);
80 auto *ExpVal = isl_val_2exp(v: WidthVal);
81 return isl_pw_aff_val_on_domain(domain: Dom, v: ExpVal);
82}
83
84SCEVAffinator::SCEVAffinator(Scop *S, LoopInfo &LI)
85 : S(S), Ctx(S->getIslCtx().get()), SE(*S->getSE()), LI(LI),
86 TD(S->getFunction().getDataLayout()) {}
87
88Loop *SCEVAffinator::getScope() { return BB ? LI.getLoopFor(BB) : nullptr; }
89
90void SCEVAffinator::interpretAsUnsigned(PWACtx &PWAC, unsigned Width) {
91 auto *NonNegDom = isl_pw_aff_nonneg_set(pwaff: PWAC.first.copy());
92 auto *NonNegPWA =
93 isl_pw_aff_intersect_domain(pa: PWAC.first.copy(), set: isl_set_copy(set: NonNegDom));
94 auto *ExpPWA = getWidthExpValOnDomain(Width, Dom: isl_set_complement(set: NonNegDom));
95 PWAC.first = isl::manage(ptr: isl_pw_aff_union_add(
96 pwaff1: NonNegPWA, pwaff2: isl_pw_aff_add(pwaff1: PWAC.first.release(), pwaff2: ExpPWA)));
97}
98
99void SCEVAffinator::takeNonNegativeAssumption(
100 PWACtx &PWAC, RecordedAssumptionsTy *RecordedAssumptions) {
101 this->RecordedAssumptions = RecordedAssumptions;
102
103 auto *NegPWA = isl_pw_aff_neg(pwaff: PWAC.first.copy());
104 auto *NegDom = isl_pw_aff_pos_set(pa: NegPWA);
105 PWAC.second =
106 isl::manage(ptr: isl_set_union(set1: PWAC.second.release(), set2: isl_set_copy(set: NegDom)));
107 auto *Restriction = BB ? NegDom : isl_set_params(set: NegDom);
108 auto DL = BB ? BB->getTerminator()->getDebugLoc() : DebugLoc();
109 recordAssumption(RecordedAssumptions, Kind: UNSIGNED, Set: isl::manage(ptr: Restriction), Loc: DL,
110 Sign: AS_RESTRICTION, BB);
111}
112
113PWACtx SCEVAffinator::getPWACtxFromPWA(isl::pw_aff PWA) {
114 return std::make_pair(x&: PWA, y: isl::set::empty(space: isl::space(Ctx, 0, NumIterators)));
115}
116
117PWACtx SCEVAffinator::getPwAff(const SCEV *Expr, BasicBlock *BB,
118 RecordedAssumptionsTy *RecordedAssumptions) {
119 this->BB = BB;
120 this->RecordedAssumptions = RecordedAssumptions;
121
122 if (BB) {
123 auto *DC = S->getDomainConditions(BB).release();
124 NumIterators = isl_set_n_dim(set: DC);
125 isl_set_free(set: DC);
126 } else
127 NumIterators = 0;
128
129 return visit(E: Expr);
130}
131
132PWACtx SCEVAffinator::checkForWrapping(const SCEV *Expr, PWACtx PWAC) const {
133 // If the SCEV flags do contain NSW (no signed wrap) then PWA already
134 // represents Expr in modulo semantic (it is not allowed to overflow), thus we
135 // are done. Otherwise, we will compute:
136 // PWA = ((PWA + 2^(n-1)) mod (2 ^ n)) - 2^(n-1)
137 // whereas n is the number of bits of the Expr, hence:
138 // n = bitwidth(ExprType)
139
140 if (IgnoreIntegerWrapping || (getNoWrapFlags(Expr) & SCEV::FlagNSW))
141 return PWAC;
142
143 isl::pw_aff PWAMod = addModuloSemantic(PWA: PWAC.first, ExprType: Expr->getType());
144
145 isl::set NotEqualSet = PWAC.first.ne_set(pwaff2: PWAMod);
146 PWAC.second = PWAC.second.unite(set2: NotEqualSet).coalesce();
147
148 const DebugLoc &Loc = BB ? BB->getTerminator()->getDebugLoc() : DebugLoc();
149 if (!BB)
150 NotEqualSet = NotEqualSet.params();
151 NotEqualSet = NotEqualSet.coalesce();
152
153 if (!NotEqualSet.is_empty())
154 recordAssumption(RecordedAssumptions, Kind: WRAPPING, Set: NotEqualSet, Loc,
155 Sign: AS_RESTRICTION, BB);
156
157 return PWAC;
158}
159
160isl::pw_aff SCEVAffinator::addModuloSemantic(isl::pw_aff PWA,
161 Type *ExprType) const {
162 unsigned Width = TD.getTypeSizeInBits(Ty: ExprType);
163
164 auto ModVal = isl::val::int_from_ui(ctx: Ctx, u: Width);
165 ModVal = ModVal.pow2();
166
167 isl::set Domain = PWA.domain();
168 isl::pw_aff AddPW =
169 isl::manage(ptr: getWidthExpValOnDomain(Width: Width - 1, Dom: Domain.release()));
170
171 return PWA.add(pwaff2: AddPW).mod(mod: ModVal).sub(pwaff2: AddPW);
172}
173
174bool SCEVAffinator::hasNSWAddRecForLoop(Loop *L) const {
175 for (const auto &CachedPair : CachedExpressions) {
176 auto *AddRec = dyn_cast<SCEVAddRecExpr>(Val: CachedPair.first.first);
177 if (!AddRec)
178 continue;
179 if (AddRec->getLoop() != L)
180 continue;
181 if (AddRec->getNoWrapFlags() & SCEV::FlagNSW)
182 return true;
183 }
184
185 return false;
186}
187
188bool SCEVAffinator::computeModuloForExpr(const SCEV *Expr) {
189 unsigned Width = TD.getTypeSizeInBits(Ty: Expr->getType());
190 // We assume nsw expressions never overflow.
191 if (auto *NAry = dyn_cast<SCEVNAryExpr>(Val: Expr))
192 if (NAry->getNoWrapFlags() & SCEV::FlagNSW)
193 return false;
194 return Width <= MaxSmallBitWidth;
195}
196
197PWACtx SCEVAffinator::visit(const SCEV *Expr) {
198
199 auto Key = std::make_pair(x&: Expr, y&: BB);
200 PWACtx PWAC = CachedExpressions[Key];
201 if (!PWAC.first.is_null())
202 return PWAC;
203
204 auto ConstantAndLeftOverPair = extractConstantFactor(M: Expr, SE);
205 auto *Factor = ConstantAndLeftOverPair.first;
206 Expr = ConstantAndLeftOverPair.second;
207
208 auto *Scope = getScope();
209 S->addParams(NewParameters: getParamsInAffineExpr(R: &S->getRegion(), Scope, Expression: Expr, SE));
210
211 // In case the scev is a valid parameter, we do not further analyze this
212 // expression, but create a new parameter in the isl_pw_aff. This allows us
213 // to treat subexpressions that we cannot translate into an piecewise affine
214 // expression, as constant parameters of the piecewise affine expression.
215 if (isl_id *Id = S->getIdForParam(Parameter: Expr).release()) {
216 isl_space *Space = isl_space_set_alloc(ctx: Ctx.get(), nparam: 1, dim: NumIterators);
217 Space = isl_space_set_dim_id(space: Space, type: isl_dim_param, pos: 0, id: Id);
218
219 isl_set *Domain = isl_set_universe(space: isl_space_copy(space: Space));
220 isl_aff *Affine = isl_aff_zero_on_domain(ls: isl_local_space_from_space(space: Space));
221 Affine = isl_aff_add_coefficient_si(aff: Affine, type: isl_dim_param, pos: 0, v: 1);
222
223 PWAC = getPWACtxFromPWA(PWA: isl::manage(ptr: isl_pw_aff_alloc(set: Domain, aff: Affine)));
224 } else {
225 PWAC = SCEVVisitor<SCEVAffinator, PWACtx>::visit(S: Expr);
226 if (computeModuloForExpr(Expr))
227 PWAC.first = addModuloSemantic(PWA: PWAC.first, ExprType: Expr->getType());
228 else
229 PWAC = checkForWrapping(Expr, PWAC);
230 }
231
232 if (!Factor->getType()->isIntegerTy(Bitwidth: 1)) {
233 PWAC = combine(PWAC0: PWAC, PWAC1: visitConstant(E: Factor), Fn: isl_pw_aff_mul);
234 if (computeModuloForExpr(Expr: Key.first))
235 PWAC.first = addModuloSemantic(PWA: PWAC.first, ExprType: Expr->getType());
236 }
237
238 // For compile time reasons we need to simplify the PWAC before we cache and
239 // return it.
240 PWAC.first = PWAC.first.coalesce();
241 if (!computeModuloForExpr(Expr: Key.first))
242 PWAC = checkForWrapping(Expr: Key.first, PWAC);
243
244 CachedExpressions[Key] = PWAC;
245 return PWAC;
246}
247
248PWACtx SCEVAffinator::visitConstant(const SCEVConstant *Expr) {
249 ConstantInt *Value = Expr->getValue();
250 isl_val *v;
251
252 // LLVM does not define if an integer value is interpreted as a signed or
253 // unsigned value. Hence, without further information, it is unknown how
254 // this value needs to be converted to GMP. At the moment, we only support
255 // signed operations. So we just interpret it as signed. Later, there are
256 // two options:
257 //
258 // 1. We always interpret any value as signed and convert the values on
259 // demand.
260 // 2. We pass down the signedness of the calculation and use it to interpret
261 // this constant correctly.
262 v = isl_valFromAPInt(Ctx: Ctx.get(), Int: Value->getValue(), /* isSigned */ IsSigned: true);
263
264 isl_space *Space = isl_space_set_alloc(ctx: Ctx.get(), nparam: 0, dim: NumIterators);
265 isl_local_space *ls = isl_local_space_from_space(space: Space);
266 return getPWACtxFromPWA(
267 PWA: isl::manage(ptr: isl_pw_aff_from_aff(aff: isl_aff_val_on_domain(ls, val: v))));
268}
269
270PWACtx SCEVAffinator::visitVScale(const SCEVVScale *VScale) {
271 llvm_unreachable("SCEVVScale not yet supported");
272}
273
274PWACtx SCEVAffinator::visitPtrToIntExpr(const SCEVPtrToIntExpr *Expr) {
275 return visit(Expr: Expr->getOperand(i: 0));
276}
277
278PWACtx SCEVAffinator::visitTruncateExpr(const SCEVTruncateExpr *Expr) {
279 // Truncate operations are basically modulo operations, thus we can
280 // model them that way. However, for large types we assume the operand
281 // to fit in the new type size instead of introducing a modulo with a very
282 // large constant.
283
284 const SCEV *Op = Expr->getOperand();
285 auto OpPWAC = visit(Expr: Op);
286
287 unsigned Width = TD.getTypeSizeInBits(Ty: Expr->getType());
288
289 if (computeModuloForExpr(Expr))
290 return OpPWAC;
291
292 auto *Dom = OpPWAC.first.domain().release();
293 auto *ExpPWA = getWidthExpValOnDomain(Width: Width - 1, Dom);
294 auto *GreaterDom =
295 isl_pw_aff_ge_set(pwaff1: OpPWAC.first.copy(), pwaff2: isl_pw_aff_copy(pwaff: ExpPWA));
296 auto *SmallerDom =
297 isl_pw_aff_lt_set(pwaff1: OpPWAC.first.copy(), pwaff2: isl_pw_aff_neg(pwaff: ExpPWA));
298 auto *OutOfBoundsDom = isl_set_union(set1: SmallerDom, set2: GreaterDom);
299 OpPWAC.second = OpPWAC.second.unite(set2: isl::manage_copy(ptr: OutOfBoundsDom));
300
301 if (!BB) {
302 assert(isl_set_dim(OutOfBoundsDom, isl_dim_set) == 0 &&
303 "Expected a zero dimensional set for non-basic-block domains");
304 OutOfBoundsDom = isl_set_params(set: OutOfBoundsDom);
305 }
306
307 recordAssumption(RecordedAssumptions, Kind: UNSIGNED, Set: isl::manage(ptr: OutOfBoundsDom),
308 Loc: DebugLoc(), Sign: AS_RESTRICTION, BB);
309
310 return OpPWAC;
311}
312
313PWACtx SCEVAffinator::visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
314 // A zero-extended value can be interpreted as a piecewise defined signed
315 // value. If the value was non-negative it stays the same, otherwise it
316 // is the sum of the original value and 2^n where n is the bit-width of
317 // the original (or operand) type. Examples:
318 // zext i8 127 to i32 -> { [127] }
319 // zext i8 -1 to i32 -> { [256 + (-1)] } = { [255] }
320 // zext i8 %v to i32 -> [v] -> { [v] | v >= 0; [256 + v] | v < 0 }
321 //
322 // However, LLVM/Scalar Evolution uses zero-extend (potentially lead by a
323 // truncate) to represent some forms of modulo computation. The left-hand side
324 // of the condition in the code below would result in the SCEV
325 // "zext i1 <false, +, true>for.body" which is just another description
326 // of the C expression "i & 1 != 0" or, equivalently, "i % 2 != 0".
327 //
328 // for (i = 0; i < N; i++)
329 // if (i & 1 != 0 /* == i % 2 */)
330 // /* do something */
331 //
332 // If we do not make the modulo explicit but only use the mechanism described
333 // above we will get the very restrictive assumption "N < 3", because for all
334 // values of N >= 3 the SCEVAddRecExpr operand of the zero-extend would wrap.
335 // Alternatively, we can make the modulo in the operand explicit in the
336 // resulting piecewise function and thereby avoid the assumption on N. For the
337 // example this would result in the following piecewise affine function:
338 // { [i0] -> [(1)] : 2*floor((-1 + i0)/2) = -1 + i0;
339 // [i0] -> [(0)] : 2*floor((i0)/2) = i0 }
340 // To this end we can first determine if the (immediate) operand of the
341 // zero-extend can wrap and, in case it might, we will use explicit modulo
342 // semantic to compute the result instead of emitting non-wrapping
343 // assumptions.
344 //
345 // Note that operands with large bit-widths are less likely to be negative
346 // because it would result in a very large access offset or loop bound after
347 // the zero-extend. To this end one can optimistically assume the operand to
348 // be positive and avoid the piecewise definition if the bit-width is bigger
349 // than some threshold (here MaxZextSmallBitWidth).
350 //
351 // We choose to go with a hybrid solution of all modeling techniques described
352 // above. For small bit-widths (up to MaxZextSmallBitWidth) we will model the
353 // wrapping explicitly and use a piecewise defined function. However, if the
354 // bit-width is bigger than MaxZextSmallBitWidth we will employ overflow
355 // assumptions and assume the "former negative" piece will not exist.
356
357 const SCEV *Op = Expr->getOperand();
358 auto OpPWAC = visit(Expr: Op);
359
360 // If the width is to big we assume the negative part does not occur.
361 if (!computeModuloForExpr(Expr: Op)) {
362 takeNonNegativeAssumption(PWAC&: OpPWAC, RecordedAssumptions);
363 return OpPWAC;
364 }
365
366 // If the width is small build the piece for the non-negative part and
367 // the one for the negative part and unify them.
368 unsigned Width = TD.getTypeSizeInBits(Ty: Op->getType());
369 interpretAsUnsigned(PWAC&: OpPWAC, Width);
370 return OpPWAC;
371}
372
373PWACtx SCEVAffinator::visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
374 // As all values are represented as signed, a sign extension is a noop.
375 return visit(Expr: Expr->getOperand());
376}
377
378PWACtx SCEVAffinator::visitAddExpr(const SCEVAddExpr *Expr) {
379 PWACtx Sum = visit(Expr: Expr->getOperand(i: 0));
380
381 for (int i = 1, e = Expr->getNumOperands(); i < e; ++i) {
382 Sum = combine(PWAC0: Sum, PWAC1: visit(Expr: Expr->getOperand(i)), Fn: isl_pw_aff_add);
383 if (isTooComplex(PWAC: Sum))
384 return complexityBailout();
385 }
386
387 return Sum;
388}
389
390PWACtx SCEVAffinator::visitMulExpr(const SCEVMulExpr *Expr) {
391 PWACtx Prod = visit(Expr: Expr->getOperand(i: 0));
392
393 for (int i = 1, e = Expr->getNumOperands(); i < e; ++i) {
394 Prod = combine(PWAC0: Prod, PWAC1: visit(Expr: Expr->getOperand(i)), Fn: isl_pw_aff_mul);
395 if (isTooComplex(PWAC: Prod))
396 return complexityBailout();
397 }
398
399 return Prod;
400}
401
402PWACtx SCEVAffinator::visitAddRecExpr(const SCEVAddRecExpr *Expr) {
403 assert(Expr->isAffine() && "Only affine AddRecurrences allowed");
404
405 auto Flags = Expr->getNoWrapFlags();
406
407 // Directly generate isl_pw_aff for Expr if 'start' is zero.
408 if (Expr->getStart()->isZero()) {
409 assert(S->contains(Expr->getLoop()) &&
410 "Scop does not contain the loop referenced in this AddRec");
411
412 PWACtx Step = visit(Expr: Expr->getOperand(i: 1));
413 isl_space *Space = isl_space_set_alloc(ctx: Ctx.get(), nparam: 0, dim: NumIterators);
414 isl_local_space *LocalSpace = isl_local_space_from_space(space: Space);
415
416 unsigned loopDimension = S->getRelativeLoopDepth(L: Expr->getLoop());
417
418 isl_aff *LAff = isl_aff_set_coefficient_si(
419 aff: isl_aff_zero_on_domain(ls: LocalSpace), type: isl_dim_in, pos: loopDimension, v: 1);
420 isl_pw_aff *LPwAff = isl_pw_aff_from_aff(aff: LAff);
421
422 Step.first = Step.first.mul(pwaff2: isl::manage(ptr: LPwAff));
423 return Step;
424 }
425
426 // Translate AddRecExpr from '{start, +, inc}' into 'start + {0, +, inc}'
427 // if 'start' is not zero.
428 // TODO: Using the original SCEV no-wrap flags is not always safe, however
429 // as our code generation is reordering the expression anyway it doesn't
430 // really matter.
431 const SCEV *ZeroStartExpr =
432 SE.getAddRecExpr(Start: SE.getConstant(Ty: Expr->getStart()->getType(), V: 0),
433 Step: Expr->getStepRecurrence(SE), L: Expr->getLoop(), Flags);
434
435 PWACtx Result = visit(Expr: ZeroStartExpr);
436 PWACtx Start = visit(Expr: Expr->getStart());
437 Result = combine(PWAC0: Result, PWAC1: Start, Fn: isl_pw_aff_add);
438 return Result;
439}
440
441PWACtx SCEVAffinator::visitSMaxExpr(const SCEVSMaxExpr *Expr) {
442 PWACtx Max = visit(Expr: Expr->getOperand(i: 0));
443
444 for (int i = 1, e = Expr->getNumOperands(); i < e; ++i) {
445 Max = combine(PWAC0: Max, PWAC1: visit(Expr: Expr->getOperand(i)), Fn: isl_pw_aff_max);
446 if (isTooComplex(PWAC: Max))
447 return complexityBailout();
448 }
449
450 return Max;
451}
452
453PWACtx SCEVAffinator::visitSMinExpr(const SCEVSMinExpr *Expr) {
454 PWACtx Min = visit(Expr: Expr->getOperand(i: 0));
455
456 for (int i = 1, e = Expr->getNumOperands(); i < e; ++i) {
457 Min = combine(PWAC0: Min, PWAC1: visit(Expr: Expr->getOperand(i)), Fn: isl_pw_aff_min);
458 if (isTooComplex(PWAC: Min))
459 return complexityBailout();
460 }
461
462 return Min;
463}
464
465PWACtx SCEVAffinator::visitUMaxExpr(const SCEVUMaxExpr *Expr) {
466 llvm_unreachable("SCEVUMaxExpr not yet supported");
467}
468
469PWACtx SCEVAffinator::visitUMinExpr(const SCEVUMinExpr *Expr) {
470 llvm_unreachable("SCEVUMinExpr not yet supported");
471}
472
473PWACtx
474SCEVAffinator::visitSequentialUMinExpr(const SCEVSequentialUMinExpr *Expr) {
475 llvm_unreachable("SCEVSequentialUMinExpr not yet supported");
476}
477
478PWACtx SCEVAffinator::visitUDivExpr(const SCEVUDivExpr *Expr) {
479 // The handling of unsigned division is basically the same as for signed
480 // division, except the interpretation of the operands. As the divisor
481 // has to be constant in both cases we can simply interpret it as an
482 // unsigned value without additional complexity in the representation.
483 // For the dividend we could choose from the different representation
484 // schemes introduced for zero-extend operations but for now we will
485 // simply use an assumption.
486 const SCEV *Dividend = Expr->getLHS();
487 const SCEV *Divisor = Expr->getRHS();
488 assert(isa<SCEVConstant>(Divisor) &&
489 "UDiv is no parameter but has a non-constant RHS.");
490
491 auto DividendPWAC = visit(Expr: Dividend);
492 auto DivisorPWAC = visit(Expr: Divisor);
493
494 if (SE.isKnownNegative(S: Divisor)) {
495 // Interpret negative divisors unsigned. This is a special case of the
496 // piece-wise defined value described for zero-extends as we already know
497 // the actual value of the constant divisor.
498 unsigned Width = TD.getTypeSizeInBits(Ty: Expr->getType());
499 auto *DivisorDom = DivisorPWAC.first.domain().release();
500 auto *WidthExpPWA = getWidthExpValOnDomain(Width, Dom: DivisorDom);
501 DivisorPWAC.first = DivisorPWAC.first.add(pwaff2: isl::manage(ptr: WidthExpPWA));
502 }
503
504 // TODO: One can represent the dividend as piece-wise function to be more
505 // precise but therefore a heuristic is needed.
506
507 // Assume a non-negative dividend.
508 takeNonNegativeAssumption(PWAC&: DividendPWAC, RecordedAssumptions);
509
510 DividendPWAC = combine(PWAC0: DividendPWAC, PWAC1: DivisorPWAC, Fn: isl_pw_aff_div);
511 DividendPWAC.first = DividendPWAC.first.floor();
512
513 return DividendPWAC;
514}
515
516PWACtx SCEVAffinator::visitSDivInstruction(Instruction *SDiv) {
517 assert(SDiv->getOpcode() == Instruction::SDiv && "Assumed SDiv instruction!");
518
519 auto *Scope = getScope();
520 auto *Divisor = SDiv->getOperand(i: 1);
521 const SCEV *DivisorSCEV = SE.getSCEVAtScope(V: Divisor, L: Scope);
522 auto DivisorPWAC = visit(Expr: DivisorSCEV);
523 assert(isa<SCEVConstant>(DivisorSCEV) &&
524 "SDiv is no parameter but has a non-constant RHS.");
525
526 auto *Dividend = SDiv->getOperand(i: 0);
527 const SCEV *DividendSCEV = SE.getSCEVAtScope(V: Dividend, L: Scope);
528 auto DividendPWAC = visit(Expr: DividendSCEV);
529 DividendPWAC = combine(PWAC0: DividendPWAC, PWAC1: DivisorPWAC, Fn: isl_pw_aff_tdiv_q);
530 return DividendPWAC;
531}
532
533PWACtx SCEVAffinator::visitSRemInstruction(Instruction *SRem) {
534 assert(SRem->getOpcode() == Instruction::SRem && "Assumed SRem instruction!");
535
536 auto *Scope = getScope();
537 auto *Divisor = SRem->getOperand(i: 1);
538 const SCEV *DivisorSCEV = SE.getSCEVAtScope(V: Divisor, L: Scope);
539 auto DivisorPWAC = visit(Expr: DivisorSCEV);
540 assert(isa<ConstantInt>(Divisor) &&
541 "SRem is no parameter but has a non-constant RHS.");
542
543 auto *Dividend = SRem->getOperand(i: 0);
544 const SCEV *DividendSCEV = SE.getSCEVAtScope(V: Dividend, L: Scope);
545 auto DividendPWAC = visit(Expr: DividendSCEV);
546 DividendPWAC = combine(PWAC0: DividendPWAC, PWAC1: DivisorPWAC, Fn: isl_pw_aff_tdiv_r);
547 return DividendPWAC;
548}
549
550PWACtx SCEVAffinator::visitUnknown(const SCEVUnknown *Expr) {
551 if (Instruction *I = dyn_cast<Instruction>(Val: Expr->getValue())) {
552 switch (I->getOpcode()) {
553 case Instruction::IntToPtr:
554 return visit(Expr: SE.getSCEVAtScope(V: I->getOperand(i: 0), L: getScope()));
555 case Instruction::SDiv:
556 return visitSDivInstruction(SDiv: I);
557 case Instruction::SRem:
558 return visitSRemInstruction(SRem: I);
559 default:
560 break; // Fall through.
561 }
562 }
563
564 if (isa<ConstantPointerNull>(Val: Expr->getValue())) {
565 isl::val v{Ctx, 0};
566 isl::space Space{Ctx, 0, NumIterators};
567 isl::local_space ls{Space};
568 return getPWACtxFromPWA(PWA: isl::aff(ls, v));
569 }
570
571 llvm_unreachable("Unknowns SCEV was neither a parameter, a constant nor a "
572 "valid instruction.");
573}
574
575PWACtx SCEVAffinator::complexityBailout() {
576 // We hit the complexity limit for affine expressions; invalidate the scop
577 // and return a constant zero.
578 const DebugLoc &Loc = BB ? BB->getTerminator()->getDebugLoc() : DebugLoc();
579 S->invalidate(Kind: COMPLEXITY, Loc);
580 return visit(Expr: SE.getZero(Ty: Type::getInt32Ty(C&: S->getFunction().getContext())));
581}
582

source code of polly/lib/Support/SCEVAffinator.cpp