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