Coverage Report

Created: 2019-02-20 07:29

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