Coverage Report

Created: 2019-04-21 11:35

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