Coverage Report

Created: 2017-08-18 19:41

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