polly/lib/Support/SCEVAffinator.cpp

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