27 "polly-ignore-integer-wrapping",
28 cl::desc(
"Do not build run-time checks to proof absence of integer "
44 auto *NumBasicSets =
static_cast<unsigned *
>(User);
53 unsigned NumBasicSets = 0;
62 if (
auto *NAry = dyn_cast<SCEVNAryExpr>(Expr))
63 return NAry->getNoWrapFlags();
64 return SCEV::NoWrapMask;
70 PWAC0.first =
isl::manage(Fn(PWAC0.first.release(), PWAC1.first.release()));
71 PWAC0.second = PWAC0.second.unite(PWAC1.second);
84 :
S(
S),
Ctx(
S->getIslCtx().get()), SE(*
S->getSE()), LI(LI),
85 TD(
S->getFunction().getParent()->getDataLayout()) {}
107 auto DL =
BB ?
BB->getTerminator()->getDebugLoc() : DebugLoc();
122 auto *DC =
S->getDomainConditions(
BB).release();
144 isl::set NotEqualSet = PWAC.first.ne_set(PWAMod);
147 const DebugLoc &Loc =
BB ?
BB->getTerminator()->getDebugLoc() : DebugLoc();
149 NotEqualSet = NotEqualSet.
params();
150 NotEqualSet = NotEqualSet.
coalesce();
160 Type *ExprType)
const {
161 unsigned Width =
TD.getTypeSizeInBits(ExprType);
164 ModVal = ModVal.pow2();
170 return PWA.
add(AddPW).mod(ModVal).
sub(AddPW);
175 auto *AddRec = dyn_cast<SCEVAddRecExpr>(CachedPair.first.first);
178 if (AddRec->getLoop() != L)
180 if (AddRec->getNoWrapFlags() & SCEV::FlagNSW)
188 unsigned Width =
TD.getTypeSizeInBits(Expr->getType());
190 if (
auto *NAry = dyn_cast<SCEVNAryExpr>(Expr))
191 if (NAry->getNoWrapFlags() & SCEV::FlagNSW)
198 auto Key = std::make_pair(Expr,
BB);
200 if (!PWAC.first.is_null())
204 auto *Factor = ConstantAndLeftOverPair.first;
205 Expr = ConstantAndLeftOverPair.second;
214 if (
isl_id *Id =
S->getIdForParam(Expr).release()) {
224 PWAC = SCEVVisitor<SCEVAffinator, PWACtx>::visit(Expr);
231 if (!Factor->getType()->isIntegerTy(1)) {
239 PWAC.first = PWAC.first.coalesce();
248 ConstantInt *
Value = Expr->getValue();
270 llvm_unreachable(
"SCEVVScale not yet supported");
274 return visit(Expr->getOperand(0));
283 auto *Op = Expr->getOperand();
284 auto OpPWAC =
visit(Op);
286 unsigned Width =
TD.getTypeSizeInBits(Expr->getType());
291 auto *Dom = OpPWAC.first.domain().release();
297 auto *OutOfBoundsDom =
isl_set_union(SmallerDom, GreaterDom);
302 "Expected a zero dimensional set for non-basic-block domains");
356 auto *Op = Expr->getOperand();
357 auto OpPWAC =
visit(Op);
367 unsigned Width =
TD.getTypeSizeInBits(Op->getType());
374 return visit(Expr->getOperand());
380 for (
int i = 1, e = Expr->getNumOperands(); i < e; ++i) {
392 for (
int i = 1, e = Expr->getNumOperands(); i < e; ++i) {
402 assert(Expr->isAffine() &&
"Only affine AddRecurrences allowed");
404 auto Flags = Expr->getNoWrapFlags();
407 if (Expr->getStart()->isZero()) {
408 assert(
S->contains(Expr->getLoop()) &&
409 "Scop does not contain the loop referenced in this AddRec");
415 unsigned loopDimension =
S->getRelativeLoopDepth(Expr->getLoop());
430 const SCEV *ZeroStartExpr =
431 SE.getAddRecExpr(
SE.getConstant(Expr->getStart()->getType(), 0),
432 Expr->getStepRecurrence(
SE), Expr->getLoop(), Flags);
443 for (
int i = 1, e = Expr->getNumOperands(); i < e; ++i) {
455 for (
int i = 1, e = Expr->getNumOperands(); i < e; ++i) {
465 llvm_unreachable(
"SCEVUMaxExpr not yet supported");
469 llvm_unreachable(
"SCEVUMinExpr not yet supported");
474 llvm_unreachable(
"SCEVSequentialUMinExpr not yet supported");
485 auto *Dividend = Expr->getLHS();
486 auto *Divisor = Expr->getRHS();
487 assert(isa<SCEVConstant>(Divisor) &&
488 "UDiv is no parameter but has a non-constant RHS.");
490 auto DividendPWAC =
visit(Dividend);
491 auto DivisorPWAC =
visit(Divisor);
493 if (
SE.isKnownNegative(Divisor)) {
497 unsigned Width =
TD.getTypeSizeInBits(Expr->getType());
498 auto *DivisorDom = DivisorPWAC.first.domain().release();
500 DivisorPWAC.first = DivisorPWAC.first.add(
isl::manage(WidthExpPWA));
510 DividendPWAC.first = DividendPWAC.first.floor();
516 assert(SDiv->getOpcode() == Instruction::SDiv &&
"Assumed SDiv instruction!");
519 auto *Divisor = SDiv->getOperand(1);
520 auto *DivisorSCEV =
SE.getSCEVAtScope(Divisor, Scope);
521 auto DivisorPWAC =
visit(DivisorSCEV);
522 assert(isa<SCEVConstant>(DivisorSCEV) &&
523 "SDiv is no parameter but has a non-constant RHS.");
525 auto *Dividend = SDiv->getOperand(0);
526 auto *DividendSCEV =
SE.getSCEVAtScope(Dividend, Scope);
527 auto DividendPWAC =
visit(DividendSCEV);
533 assert(SRem->getOpcode() == Instruction::SRem &&
"Assumed SRem instruction!");
536 auto *Divisor = SRem->getOperand(1);
537 auto *DivisorSCEV =
SE.getSCEVAtScope(Divisor, Scope);
538 auto DivisorPWAC =
visit(DivisorSCEV);
539 assert(isa<ConstantInt>(Divisor) &&
540 "SRem is no parameter but has a non-constant RHS.");
542 auto *Dividend = SRem->getOperand(0);
543 auto *DividendSCEV =
SE.getSCEVAtScope(Dividend, Scope);
544 auto DividendPWAC =
visit(DividendSCEV);
550 if (Instruction *I = dyn_cast<Instruction>(Expr->getValue())) {
551 switch (I->getOpcode()) {
552 case Instruction::IntToPtr:
554 case Instruction::SDiv:
556 case Instruction::SRem:
563 if (isa<ConstantPointerNull>(Expr->getValue())) {
570 llvm_unreachable(
"Unknowns SCEV was neither a parameter, a constant nor a "
571 "valid instruction.");
577 const DebugLoc &Loc =
BB ?
BB->getTerminator()->getDebugLoc() : DebugLoc();
579 return visit(
SE.getZero(Type::getInt32Ty(
S->getFunction().getContext())));
llvm::cl::OptionCategory PollyCategory
static __isl_give isl_pw_aff * getWidthExpValOnDomain(unsigned Width, __isl_take isl_set *Dom)
static unsigned const MaxSmallBitWidth
static PWACtx combine(PWACtx PWAC0, PWACtx PWAC1, __isl_give isl_pw_aff *(Fn)(__isl_take isl_pw_aff *, __isl_take isl_pw_aff *))
static bool isTooComplex(PWACtx PWAC)
Determine if PWAC is too complex to continue.
static isl_stat addNumBasicSets(__isl_take isl_set *Domain, __isl_take isl_aff *Aff, void *User)
Add the number of basic sets in Domain to User.
static SCEV::NoWrapFlags getNoWrapFlags(const SCEV *Expr)
Return the flag describing the possible wrapping of Expr.
static int const MaxDisjunctionsInPwAff
static cl::opt< bool > IgnoreIntegerWrapping("polly-ignore-integer-wrapping", cl::desc("Do not build run-time checks to proof absence of integer " "wrapping"), cl::Hidden, cl::cat(PollyCategory))
__isl_null isl_aff * isl_aff_free(__isl_take isl_aff *aff)
__isl_give isl_pw_aff * isl_pw_aff_val_on_domain(__isl_take isl_set *domain, __isl_take isl_val *v)
__isl_export __isl_give isl_pw_aff * isl_pw_aff_div(__isl_take isl_pw_aff *pa1, __isl_take isl_pw_aff *pa2)
__isl_export __isl_give isl_pw_aff * isl_pw_aff_tdiv_r(__isl_take isl_pw_aff *pa1, __isl_take isl_pw_aff *pa2)
__isl_give isl_aff * isl_aff_val_on_domain(__isl_take isl_local_space *ls, __isl_take isl_val *val)
__isl_export __isl_give isl_pw_aff * isl_pw_aff_tdiv_q(__isl_take isl_pw_aff *pa1, __isl_take isl_pw_aff *pa2)
__isl_export __isl_give isl_pw_aff * isl_pw_aff_mul(__isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2)
__isl_give isl_pw_aff * isl_pw_aff_alloc(__isl_take isl_set *set, __isl_take isl_aff *aff)
isl_stat isl_pw_aff_foreach_piece(__isl_keep isl_pw_aff *pwaff, isl_stat(*fn)(__isl_take isl_set *set, __isl_take isl_aff *aff, void *user), void *user)
__isl_export __isl_give isl_pw_aff * isl_pw_aff_union_add(__isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2)
__isl_give isl_aff * isl_aff_set_coefficient_si(__isl_take isl_aff *aff, enum isl_dim_type type, int pos, int v)
__isl_export __isl_give isl_pw_aff * isl_pw_aff_min(__isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2)
__isl_export __isl_give isl_pw_aff * isl_pw_aff_intersect_domain(__isl_take isl_pw_aff *pa, __isl_take isl_set *set)
__isl_export __isl_give isl_pw_aff * isl_pw_aff_neg(__isl_take isl_pw_aff *pwaff)
__isl_give isl_set * isl_pw_aff_pos_set(__isl_take isl_pw_aff *pa)
__isl_give isl_aff * isl_aff_add_coefficient_si(__isl_take isl_aff *aff, enum isl_dim_type type, int pos, int v)
__isl_give isl_aff * isl_aff_zero_on_domain(__isl_take isl_local_space *ls)
__isl_constructor __isl_give isl_pw_aff * isl_pw_aff_from_aff(__isl_take isl_aff *aff)
__isl_give isl_set * isl_pw_aff_nonneg_set(__isl_take isl_pw_aff *pwaff)
__isl_export __isl_give isl_set * isl_pw_aff_lt_set(__isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2)
__isl_export __isl_give isl_pw_aff * isl_pw_aff_add(__isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2)
__isl_export __isl_give isl_pw_aff * isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2)
__isl_give isl_pw_aff * isl_pw_aff_copy(__isl_keep isl_pw_aff *pwaff)
__isl_export __isl_give isl_set * isl_pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2)
isl::multi_pw_aff sub(isl::multi_pw_aff multi2) const
isl::multi_pw_aff add(const isl::multi_pw_aff &multi2) const
isl::set coalesce() const
static isl::set empty(isl::space space)
isl::set unite(isl::set set2) const
static isl::val int_from_ui(isl::ctx ctx, unsigned long u)
PWACtx visitMulExpr(const llvm::SCEVMulExpr *E)
PWACtx visitUMinExpr(const llvm::SCEVUMinExpr *E)
void interpretAsUnsigned(PWACtx &PWAC, unsigned Width)
Interpret the PWA in PWAC as an unsigned value.
bool computeModuloForExpr(const llvm::SCEV *Expr)
Whether to track the value of this expression precisely, rather than assuming it won't wrap.
PWACtx visitUMaxExpr(const llvm::SCEVUMaxExpr *E)
SCEVAffinator(Scop *S, llvm::LoopInfo &LI)
PWACtx visitUDivExpr(const llvm::SCEVUDivExpr *E)
PWACtx visit(const llvm::SCEV *E)
bool hasNSWAddRecForLoop(llvm::Loop *L) const
Check an <nsw> AddRec for the loop L is cached.
PWACtx complexityBailout()
void takeNonNegativeAssumption(PWACtx &PWAC, RecordedAssumptionsTy *RecordedAssumptions=nullptr)
Take the assumption that PWAC is non-negative.
llvm::DenseMap< CacheKey, PWACtx > CachedExpressions
Map to remembered cached expressions.
RecordedAssumptionsTy * RecordedAssumptions
PWACtx visitTruncateExpr(const llvm::SCEVTruncateExpr *E)
PWACtx visitSMinExpr(const llvm::SCEVSMinExpr *E)
PWACtx visitSDivInstruction(llvm::Instruction *SDiv)
PWACtx visitConstant(const llvm::SCEVConstant *E)
PWACtx visitPtrToIntExpr(const llvm::SCEVPtrToIntExpr *E)
const llvm::DataLayout & TD
Target data for element size computing.
PWACtx visitAddExpr(const llvm::SCEVAddExpr *E)
PWACtx visitVScale(const llvm::SCEVVScale *E)
PWACtx visitSequentialUMinExpr(const llvm::SCEVSequentialUMinExpr *E)
PWACtx getPwAff(const llvm::SCEV *E, llvm::BasicBlock *BB=nullptr, RecordedAssumptionsTy *RecordedAssumptions=nullptr)
Translate a SCEV to an isl::pw_aff.
isl::pw_aff addModuloSemantic(isl::pw_aff PWA, llvm::Type *ExprType) const
Compute the non-wrapping version of PWA for type ExprType.
llvm::ScalarEvolution & SE
PWACtx visitSRemInstruction(llvm::Instruction *SRem)
PWACtx visitAddRecExpr(const llvm::SCEVAddRecExpr *E)
PWACtx checkForWrapping(const llvm::SCEV *Expr, PWACtx PWAC) const
If Expr might cause an integer wrap record an assumption.
PWACtx visitUnknown(const llvm::SCEVUnknown *E)
PWACtx getPWACtxFromPWA(isl::pw_aff PWA)
Return a PWACtx for PWA that is always valid.
llvm::Loop * getScope()
Return the loop for the current block if any.
PWACtx visitSMaxExpr(const llvm::SCEVSMaxExpr *E)
PWACtx visitSignExtendExpr(const llvm::SCEVSignExtendExpr *E)
PWACtx visitZeroExtendExpr(const llvm::SCEVZeroExtendExpr *E)
__isl_give isl_local_space * isl_local_space_from_space(__isl_take isl_space *space)
aff manage_copy(__isl_keep isl_aff *ptr)
boolean manage(isl_bool val)
This file contains the declaration of the PolyhedralInfo class, which will provide an interface to ex...
std::pair< isl::pw_aff, isl::set > PWACtx
The result type of the SCEVAffinator.
__isl_give isl_val * isl_valFromAPInt(isl_ctx *Ctx, const llvm::APInt Int, bool IsSigned)
Translate an llvm::APInt to an isl_val.
@ Value
MemoryKind::Value: Models an llvm::Value.
llvm::SmallVector< Assumption, 8 > RecordedAssumptionsTy
void recordAssumption(RecordedAssumptionsTy *RecordedAssumptions, AssumptionKind Kind, isl::set Set, llvm::DebugLoc Loc, AssumptionSign Sign, llvm::BasicBlock *BB=nullptr, bool RTC=true)
Record an assumption for later addition to the assumed context.
std::pair< const llvm::SCEVConstant *, const llvm::SCEV * > extractConstantFactor(const llvm::SCEV *M, llvm::ScalarEvolution &SE)
Extract the constant factors from the multiplication M.
ParameterSetTy getParamsInAffineExpr(const llvm::Region *R, llvm::Loop *Scope, const llvm::SCEV *Expression, llvm::ScalarEvolution &SE)
__isl_export __isl_give isl_set * isl_set_universe(__isl_take isl_space *space)
isl_ctx * isl_set_get_ctx(__isl_keep isl_set *set)
__isl_export __isl_give isl_set * isl_set_union(__isl_take isl_set *set1, __isl_take isl_set *set2)
__isl_export __isl_give isl_set * isl_set_complement(__isl_take isl_set *set)
__isl_null isl_set * isl_set_free(__isl_take isl_set *set)
isl_size isl_set_n_dim(__isl_keep isl_set *set)
__isl_give isl_set * isl_set_copy(__isl_keep isl_set *set)
isl_size isl_set_dim(__isl_keep isl_set *set, enum isl_dim_type type)
__isl_export isl_size isl_set_n_basic_set(__isl_keep isl_set *set)
__isl_export __isl_give isl_set * isl_set_params(__isl_take isl_set *set)
__isl_give isl_space * isl_space_copy(__isl_keep isl_space *space)
__isl_give isl_space * isl_space_set_dim_id(__isl_take isl_space *space, enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
__isl_give isl_space * isl_space_set_alloc(isl_ctx *ctx, unsigned nparam, unsigned dim)
static TupleKindPtr Domain("Domain")
static void combine(std::vector< std::string > &vec1, const std::vector< std::string > &vec2)
__isl_give isl_val * isl_val_2exp(__isl_take isl_val *v)
__isl_give isl_val * isl_val_int_from_ui(isl_ctx *ctx, unsigned long u)