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 | |
24 | using namespace llvm; |
25 | using namespace polly; |
26 | |
27 | static 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. |
36 | static int const MaxDisjunctionsInPwAff = 100; |
37 | |
38 | // The maximal number of bits for which a general expression is modeled |
39 | // precisely. |
40 | static unsigned const MaxSmallBitWidth = 7; |
41 | |
42 | /// Add the number of basic sets in @p Domain to @p User |
43 | static 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. |
53 | static 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. |
62 | static 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 | |
68 | static 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 | |
76 | static __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 | |
84 | SCEVAffinator::SCEVAffinator(Scop *S, LoopInfo &LI) |
85 | : S(S), Ctx(S->getIslCtx().get()), SE(*S->getSE()), LI(LI), |
86 | TD(S->getFunction().getDataLayout()) {} |
87 | |
88 | Loop *SCEVAffinator::getScope() { return BB ? LI.getLoopFor(BB) : nullptr; } |
89 | |
90 | void 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 | |
99 | void 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 | |
113 | PWACtx 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 | |
117 | PWACtx 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 | |
132 | PWACtx 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 | |
160 | isl::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 | |
174 | bool 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 | |
188 | bool 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 | |
197 | PWACtx 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 | |
248 | PWACtx 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 | |
270 | PWACtx SCEVAffinator::visitVScale(const SCEVVScale *VScale) { |
271 | llvm_unreachable("SCEVVScale not yet supported"); |
272 | } |
273 | |
274 | PWACtx SCEVAffinator::visitPtrToIntExpr(const SCEVPtrToIntExpr *Expr) { |
275 | return visit(Expr: Expr->getOperand(i: 0)); |
276 | } |
277 | |
278 | PWACtx 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 | |
313 | PWACtx 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 | |
373 | PWACtx 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 | |
378 | PWACtx 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 | |
390 | PWACtx 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 | |
402 | PWACtx 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 | |
441 | PWACtx 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 | |
453 | PWACtx 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 | |
465 | PWACtx SCEVAffinator::visitUMaxExpr(const SCEVUMaxExpr *Expr) { |
466 | llvm_unreachable("SCEVUMaxExpr not yet supported"); |
467 | } |
468 | |
469 | PWACtx SCEVAffinator::visitUMinExpr(const SCEVUMinExpr *Expr) { |
470 | llvm_unreachable("SCEVUMinExpr not yet supported"); |
471 | } |
472 | |
473 | PWACtx |
474 | SCEVAffinator::visitSequentialUMinExpr(const SCEVSequentialUMinExpr *Expr) { |
475 | llvm_unreachable("SCEVSequentialUMinExpr not yet supported"); |
476 | } |
477 | |
478 | PWACtx 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 | |
516 | PWACtx 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 | |
533 | PWACtx 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 | |
550 | PWACtx 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 | |
575 | PWACtx 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 |
Definitions
- IgnoreIntegerWrapping
- MaxDisjunctionsInPwAff
- MaxSmallBitWidth
- addNumBasicSets
- isTooComplex
- getNoWrapFlags
- combine
- getWidthExpValOnDomain
- SCEVAffinator
- getScope
- interpretAsUnsigned
- takeNonNegativeAssumption
- getPWACtxFromPWA
- getPwAff
- checkForWrapping
- addModuloSemantic
- hasNSWAddRecForLoop
- computeModuloForExpr
- visit
- visitConstant
- visitVScale
- visitPtrToIntExpr
- visitTruncateExpr
- visitZeroExtendExpr
- visitSignExtendExpr
- visitAddExpr
- visitMulExpr
- visitAddRecExpr
- visitSMaxExpr
- visitSMinExpr
- visitUMaxExpr
- visitUMinExpr
- visitSequentialUMinExpr
- visitUDivExpr
- visitSDivInstruction
- visitSRemInstruction
- visitUnknown
Improve your Profiling and Debugging skills
Find out more