Coverage Report

Created: 2017-11-21 16:49

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