Index: polly/trunk/include/polly/ScopInfo.h =================================================================== --- polly/trunk/include/polly/ScopInfo.h +++ polly/trunk/include/polly/ScopInfo.h @@ -27,6 +27,7 @@ #include "llvm/Analysis/RegionPass.h" #include "isl/aff.h" #include "isl/ctx.h" +#include "isl/set.h" #include #include @@ -81,6 +82,9 @@ ERROR_DOMAINCONJUNCTS, }; +/// @brief Enum to distinguish between assumptions and restrictions. +enum AssumptionSign { AS_ASSUMPTION, AS_RESTRICTION }; + /// Maps from a loop to the affine function expressing its backedge taken count. /// The backedge taken count already enough to express iteration domain as we /// only allow loops with canonical induction variable. @@ -1334,16 +1338,13 @@ /// this scop and that need to be code generated as a run-time test. isl_set *AssumedContext; - /// @brief The boundary assumptions under which this scop was built. + /// @brief The restrictions under which this SCoP was built. /// - /// The boundary context is similar to the assumed context as it contains - /// constraints over the parameters we assume to be true. However, the - /// boundary context is less useful for dependence analysis and - /// simplification purposes as it contains only constraints that affect the - /// boundaries of the parameter ranges. As these constraints can become quite - /// complex, the boundary context and the assumed context are separated as a - /// meassure to save compile time. - isl_set *BoundaryContext; + /// The invalid context is similar to the assumed context as it contains + /// constraints over the parameters. However, while we need the constraints + /// in the assumed context to be "true" the constraints in the invalid context + /// need to be "false". Otherwise they behave the same. + isl_set *InvalidContext; /// @brief The schedule of the SCoP /// @@ -1550,8 +1551,8 @@ /// @brief Build the Context of the Scop. void buildContext(); - /// @brief Build the BoundaryContext based on the wrapping of expressions. - void buildBoundaryContext(); + /// @brief Add the restrictions based on the wrapping of expressions. + void addWrappingContext(); /// @brief Add user provided parameter constraints to context (source code). void addUserAssumptions(AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI); @@ -1562,7 +1563,7 @@ /// @brief Add the bounds of the parameters to the context. void addParameterBounds(); - /// @brief Simplify the assumed and boundary context. + /// @brief Simplify the assumed and invalid context. void simplifyContexts(); /// @brief Get the representing SCEV for @p S if applicable, otherwise @p S. @@ -1790,14 +1791,6 @@ /// @return The assumed context of this Scop. __isl_give isl_set *getAssumedContext() const; - /// @brief Get the runtime check context for this Scop. - /// - /// The runtime check context contains all constraints that have to - /// hold at runtime for the optimized version to be executed. - /// - /// @return The runtime check context of this Scop. - __isl_give isl_set *getRuntimeCheckContext() const; - /// @brief Return true if the optimized SCoP can be executed. /// /// In addition to the runtime check context this will also utilize the domain @@ -1808,14 +1801,18 @@ /// @brief Track and report an assumption. /// - /// Use 'clang -Rpass-analysis=polly-scops' or 'opt -pass-remarks=polly-scops' - /// to output the assumptions. + /// Use 'clang -Rpass-analysis=polly-scops' or 'opt + /// -pass-remarks-analysis=polly-scops' to output the assumptions. /// /// @param Kind The assumption kind describing the underlying cause. /// @param Set The relations between parameters that are assumed to hold. /// @param Loc The location in the source that caused this assumption. - void trackAssumption(AssumptionKind Kind, __isl_keep isl_set *Set, - DebugLoc Loc); + /// @param Sign Enum to indicate if the assumptions in @p Set are positive + /// (needed/assumptions) or negative (invalid/restrictions). + /// + /// @returns True if the assumption is not trivial. + bool trackAssumption(AssumptionKind Kind, __isl_keep isl_set *Set, + DebugLoc Loc, AssumptionSign Sign); /// @brief Add assumptions to assumed context. /// @@ -1831,8 +1828,10 @@ /// @param Kind The assumption kind describing the underlying cause. /// @param Set The relations between parameters that are assumed to hold. /// @param Loc The location in the source that caused this assumption. - void addAssumption(AssumptionKind Kind, __isl_take isl_set *Set, - DebugLoc Loc); + /// @param Sign Enum to indicate if the assumptions in @p Set are positive + /// (needed/assumptions) or negative (invalid/restrictions). + void addAssumption(AssumptionKind Kind, __isl_take isl_set *Set, DebugLoc Loc, + AssumptionSign Sign); /// @brief Mark the scop as invalid. /// @@ -1845,10 +1844,15 @@ /// @param Loc The location in the source that triggered . void invalidate(AssumptionKind Kind, DebugLoc Loc); - /// @brief Get the boundary context for this Scop. + /// @brief Get the invalid context for this Scop. /// - /// @return The boundary context of this Scop. - __isl_give isl_set *getBoundaryContext() const; + /// @return The invalid context of this Scop. + __isl_give isl_set *getInvalidContext() const; + + /// @brief Return true if and only if the InvalidContext is trivial (=empty). + bool hasTrivialInvalidContext() const { + return isl_set_is_empty(InvalidContext); + } /// @brief Build the alias checks for this SCoP. void buildAliasChecks(AliasAnalysis &AA); @@ -1869,8 +1873,8 @@ /// @brief Get an isl string representing the assumed context. std::string getAssumedContextStr() const; - /// @brief Get an isl string representing the boundary context. - std::string getBoundaryContextStr() const; + /// @brief Get an isl string representing the invalid context. + std::string getInvalidContextStr() const; /// @brief Return the ScopStmt for the given @p BB or nullptr if there is /// none. Index: polly/trunk/lib/Analysis/ScopInfo.cpp =================================================================== --- polly/trunk/lib/Analysis/ScopInfo.cpp +++ polly/trunk/lib/Analysis/ScopInfo.cpp @@ -609,9 +609,9 @@ // bail out more often than strictly necessary. Outside = isl_set_remove_divs(Outside); Outside = isl_set_complement(Outside); - Statement->getParent()->addAssumption( - INBOUNDS, Outside, - getAccessInstruction() ? getAccessInstruction()->getDebugLoc() : nullptr); + auto &Loc = getAccessInstruction() ? getAccessInstruction()->getDebugLoc() + : DebugLoc(); + Statement->getParent()->addAssumption(INBOUNDS, Outside, Loc, AS_ASSUMPTION); isl_space_free(Space); } @@ -1313,6 +1313,7 @@ assert(IndexOffset <= 1 && "Unexpected large index offset"); + auto *NotExecuted = isl_set_complement(isl_set_params(getDomain())); for (size_t i = 0; i < Sizes.size(); i++) { auto *Expr = Subscripts[i + IndexOffset]; auto Size = Sizes[i]; @@ -1340,17 +1341,18 @@ OutOfBound = isl_set_intersect(getDomain(), OutOfBound); OutOfBound = isl_set_params(OutOfBound); isl_set *InBound = isl_set_complement(OutOfBound); - isl_set *Executed = isl_set_params(getDomain()); // A => B == !A or B isl_set *InBoundIfExecuted = - isl_set_union(isl_set_complement(Executed), InBound); + isl_set_union(isl_set_copy(NotExecuted), InBound); InBoundIfExecuted = isl_set_coalesce(InBoundIfExecuted); - Parent.addAssumption(INBOUNDS, InBoundIfExecuted, GEP->getDebugLoc()); + Parent.addAssumption(INBOUNDS, InBoundIfExecuted, GEP->getDebugLoc(), + AS_ASSUMPTION); } isl_local_space_free(LSpace); + isl_set_free(NotExecuted); } void ScopStmt::deriveAssumptions(BasicBlock *Block, ScopDetection &SD) { @@ -1762,37 +1764,12 @@ return isl_set_intersect_params(C, DomainContext); } -void Scop::buildBoundaryContext() { - if (IgnoreIntegerWrapping) { - BoundaryContext = isl_set_universe(getParamSpace()); +void Scop::addWrappingContext() { + if (IgnoreIntegerWrapping) return; - } - - BoundaryContext = Affinator.getWrappingContext(); - - // The isl_set_complement operation used to create the boundary context - // can possibly become very expensive. We bound the compile time of - // this operation by setting a compute out. - // - // TODO: We can probably get around using isl_set_complement and directly - // AST generate BoundaryContext. - long MaxOpsOld = isl_ctx_get_max_operations(getIslCtx()); - isl_ctx_reset_operations(getIslCtx()); - isl_ctx_set_max_operations(getIslCtx(), 300000); - isl_options_set_on_error(getIslCtx(), ISL_ON_ERROR_CONTINUE); - - BoundaryContext = isl_set_complement(BoundaryContext); - - if (isl_ctx_last_error(getIslCtx()) == isl_error_quota) { - isl_set_free(BoundaryContext); - BoundaryContext = isl_set_empty(getParamSpace()); - } - isl_options_set_on_error(getIslCtx(), ISL_ON_ERROR_ABORT); - isl_ctx_reset_operations(getIslCtx()); - isl_ctx_set_max_operations(getIslCtx(), MaxOpsOld); - BoundaryContext = isl_set_gist_params(BoundaryContext, getContext()); - trackAssumption(WRAPPING, BoundaryContext, DebugLoc()); + auto *WrappingContext = Affinator.getWrappingContext(); + addAssumption(WRAPPING, WrappingContext, DebugLoc(), AS_RESTRICTION); } void Scop::addUserAssumptions(AssumptionCache &AC, DominatorTree &DT, @@ -1902,6 +1879,7 @@ void Scop::buildContext() { isl_space *Space = isl_space_params_alloc(getIslCtx(), 0); Context = isl_set_universe(isl_space_copy(Space)); + InvalidContext = isl_set_empty(isl_space_copy(Space)); AssumedContext = isl_set_universe(Space); } @@ -1981,7 +1959,7 @@ // otherwise we would access out of bound data. Now, knowing that code is // only executed for the case m >= 0, it is sufficient to assume p >= 0. AssumedContext = simplifyAssumptionContext(AssumedContext, *this); - BoundaryContext = simplifyAssumptionContext(BoundaryContext, *this); + InvalidContext = isl_set_align_params(InvalidContext, getParamSpace()); } /// @brief Add the minimal/maximal access in @p Set to @p User. @@ -2439,8 +2417,8 @@ if (containsErrorBlock(RN, getRegion(), LI, DT)) { IsOptimized = true; isl_set *DomPar = isl_set_params(isl_set_copy(Domain)); - addAssumption(ERRORBLOCK, isl_set_complement(DomPar), - BB->getTerminator()->getDebugLoc()); + addAssumption(ERRORBLOCK, DomPar, BB->getTerminator()->getDebugLoc(), + AS_RESTRICTION); } } } @@ -2540,9 +2518,8 @@ } isl_set *UnboundedCtx = isl_set_params(Parts.first); - isl_set *BoundedCtx = isl_set_complement(UnboundedCtx); - addAssumption(INFINITELOOP, BoundedCtx, - HeaderBB->getTerminator()->getDebugLoc()); + addAssumption(INFINITELOOP, UnboundedCtx, + HeaderBB->getTerminator()->getDebugLoc(), AS_RESTRICTION); } void Scop::buildAliasChecks(AliasAnalysis &AA) { @@ -2793,7 +2770,7 @@ HasSingleExitEdge(R.getExitingBlock()), HasErrorBlock(false), MaxLoopDepth(MaxLoopDepth), IslCtx(isl_ctx_alloc(), isl_ctx_free), Context(nullptr), Affinator(this), AssumedContext(nullptr), - BoundaryContext(nullptr), Schedule(nullptr) { + InvalidContext(nullptr), Schedule(nullptr) { isl_options_set_on_error(getIslCtx(), ISL_ON_ERROR_ABORT); buildContext(); } @@ -2817,14 +2794,14 @@ buildSchedule(SD, LI); - if (isl_set_is_empty(AssumedContext)) + if (!hasFeasibleRuntimeContext()) return; updateAccessDimensionality(); realignParams(); addParameterBounds(); addUserContext(); - buildBoundaryContext(); + addWrappingContext(); simplifyContexts(); buildAliasChecks(AA); @@ -2836,7 +2813,7 @@ Scop::~Scop() { isl_set_free(Context); isl_set_free(AssumedContext); - isl_set_free(BoundaryContext); + isl_set_free(InvalidContext); isl_schedule_free(Schedule); for (auto It : DomainMap) @@ -3159,11 +3136,12 @@ std::string Scop::getContextStr() const { return stringFromIslObj(Context); } std::string Scop::getAssumedContextStr() const { + assert(AssumedContext && "Assumed context not yet built"); return stringFromIslObj(AssumedContext); } -std::string Scop::getBoundaryContextStr() const { - return stringFromIslObj(BoundaryContext); +std::string Scop::getInvalidContextStr() const { + return stringFromIslObj(InvalidContext); } std::string Scop::getNameStr() const { @@ -3189,22 +3167,24 @@ } __isl_give isl_set *Scop::getAssumedContext() const { + assert(AssumedContext && "Assumed context not yet built"); return isl_set_copy(AssumedContext); } -__isl_give isl_set *Scop::getRuntimeCheckContext() const { - isl_set *RuntimeCheckContext = getAssumedContext(); - RuntimeCheckContext = - isl_set_intersect(RuntimeCheckContext, getBoundaryContext()); - RuntimeCheckContext = simplifyAssumptionContext(RuntimeCheckContext, *this); - return RuntimeCheckContext; -} - bool Scop::hasFeasibleRuntimeContext() const { - isl_set *RuntimeCheckContext = getRuntimeCheckContext(); - RuntimeCheckContext = addNonEmptyDomainConstraints(RuntimeCheckContext); - bool IsFeasible = !isl_set_is_empty(RuntimeCheckContext); - isl_set_free(RuntimeCheckContext); + auto *PositiveContext = getAssumedContext(); + PositiveContext = addNonEmptyDomainConstraints(PositiveContext); + bool IsFeasible = !isl_set_is_empty(PositiveContext); + isl_set_free(PositiveContext); + if (!IsFeasible) + return false; + + auto *NegativeContext = getInvalidContext(); + auto *DomainContext = isl_union_set_params(getDomains()); + IsFeasible = !isl_set_is_subset(DomainContext, NegativeContext); + isl_set_free(NegativeContext); + isl_set_free(DomainContext); + return IsFeasible; } @@ -3230,67 +3210,62 @@ llvm_unreachable("Unknown AssumptionKind!"); } -void Scop::trackAssumption(AssumptionKind Kind, __isl_keep isl_set *Set, - DebugLoc Loc) { - if (isl_set_is_subset(Context, Set)) - return; +bool Scop::trackAssumption(AssumptionKind Kind, __isl_keep isl_set *Set, + DebugLoc Loc, AssumptionSign Sign) { + if (Sign == AS_ASSUMPTION) { + if (isl_set_is_subset(Context, Set)) + return false; - if (isl_set_is_subset(AssumedContext, Set)) - return; + if (isl_set_is_subset(AssumedContext, Set)) + return false; + } else { + if (isl_set_is_disjoint(Set, Context)) + return false; + + if (isl_set_is_subset(Set, InvalidContext)) + return false; + } auto &F = *getRegion().getEntry()->getParent(); - std::string Msg = toString(Kind) + " assumption:\t" + stringFromIslObj(Set); + auto Suffix = Sign == AS_ASSUMPTION ? " assumption:\t" : " restriction:\t"; + std::string Msg = toString(Kind) + Suffix + stringFromIslObj(Set); emitOptimizationRemarkAnalysis(F.getContext(), DEBUG_TYPE, F, Loc, Msg); + return true; } void Scop::addAssumption(AssumptionKind Kind, __isl_take isl_set *Set, - DebugLoc Loc) { - trackAssumption(Kind, Set, Loc); - AssumedContext = isl_set_intersect(AssumedContext, Set); - - int NSets = isl_set_n_basic_set(AssumedContext); - if (NSets >= MaxDisjunctsAssumed) { - isl_space *Space = isl_set_get_space(AssumedContext); - isl_set_free(AssumedContext); - AssumedContext = isl_set_empty(Space); + DebugLoc Loc, AssumptionSign Sign) { + if (!trackAssumption(Kind, Set, Loc, Sign)) { + isl_set_free(Set); + return; } - AssumedContext = isl_set_coalesce(AssumedContext); + if (Sign == AS_ASSUMPTION) { + AssumedContext = isl_set_intersect(AssumedContext, Set); + AssumedContext = isl_set_coalesce(AssumedContext); + } else { + InvalidContext = isl_set_union(InvalidContext, Set); + InvalidContext = isl_set_coalesce(InvalidContext); + } } void Scop::invalidate(AssumptionKind Kind, DebugLoc Loc) { - addAssumption(Kind, isl_set_empty(getParamSpace()), Loc); + addAssumption(Kind, isl_set_empty(getParamSpace()), Loc, AS_ASSUMPTION); } -__isl_give isl_set *Scop::getBoundaryContext() const { - return isl_set_copy(BoundaryContext); +__isl_give isl_set *Scop::getInvalidContext() const { + return isl_set_copy(InvalidContext); } void Scop::printContext(raw_ostream &OS) const { OS << "Context:\n"; - - if (!Context) { - OS.indent(4) << "n/a\n\n"; - return; - } - - OS.indent(4) << getContextStr() << "\n"; + OS.indent(4) << Context << "\n"; OS.indent(4) << "Assumed Context:\n"; - if (!AssumedContext) { - OS.indent(4) << "n/a\n\n"; - return; - } - - OS.indent(4) << getAssumedContextStr() << "\n"; - - OS.indent(4) << "Boundary Context:\n"; - if (!BoundaryContext) { - OS.indent(4) << "n/a\n\n"; - return; - } + OS.indent(4) << AssumedContext << "\n"; - OS.indent(4) << getBoundaryContextStr() << "\n"; + OS.indent(4) << "Invalid Context:\n"; + OS.indent(4) << InvalidContext << "\n"; for (const SCEV *Parameter : Parameters) { int Dim = ParameterIds.find(Parameter)->second; Index: polly/trunk/lib/CodeGen/IslAst.cpp =================================================================== --- polly/trunk/lib/CodeGen/IslAst.cpp +++ polly/trunk/lib/CodeGen/IslAst.cpp @@ -336,8 +336,15 @@ // The conditions that need to be checked at run-time for this scop are // available as an isl_set in the runtime check context from which we can // directly derive a run-time condition. - RunCondition = - isl_ast_build_expr_from_set(Build, S->getRuntimeCheckContext()); + auto *PosCond = isl_ast_build_expr_from_set(Build, S->getAssumedContext()); + if (S->hasTrivialInvalidContext()) { + RunCondition = PosCond; + } else { + auto *ZeroV = isl_val_zero(isl_ast_build_get_ctx(Build)); + auto *NegCond = isl_ast_build_expr_from_set(Build, S->getInvalidContext()); + auto *NotNegCond = isl_ast_expr_eq(isl_ast_expr_from_val(ZeroV), NegCond); + RunCondition = isl_ast_expr_and(PosCond, NotNegCond); + } // Create the alias checks from the minimal/maximal accesses in each alias // group which consists of read only and non read only (read write) accesses. Index: polly/trunk/test/Isl/Ast/alias_simple_1.ll =================================================================== --- polly/trunk/test/Isl/Ast/alias_simple_1.ll +++ polly/trunk/test/Isl/Ast/alias_simple_1.ll @@ -12,11 +12,11 @@ ; A[i] = B[i]; ; } ; -; NOAA: if (1 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0])) -; BASI: if (1 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0])) -; TBAA: if (1) -; SCEV: if (1 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0])) -; GLOB: if (1 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0])) +; NOAA: if (1 && 0 == N <= 0 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0])) +; BASI: if (1 && 0 == N <= 0 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0])) +; TBAA: if (1 && 0 == N <= 0) +; SCEV: if (1 && 0 == N <= 0 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0])) +; GLOB: if (1 && 0 == N <= 0 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0])) ; target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" Index: polly/trunk/test/Isl/Ast/alias_simple_2.ll =================================================================== --- polly/trunk/test/Isl/Ast/alias_simple_2.ll +++ polly/trunk/test/Isl/Ast/alias_simple_2.ll @@ -13,12 +13,12 @@ ; A[i] = B[i]; ; } ; -; NOAA: if (1 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0])) -; BASI: if (1) -; TBAA: if (1 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0])) -; SCEV: if (1 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0])) -; GLOB: if (1 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0])) -; NONAFFINE: if (1 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0])) +; NOAA: if (1 && 0 == N <= 0 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0])) +; BASI: if (1 && 0 == N <= 0) +; TBAA: if (1 && 0 == N <= 0 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0])) +; SCEV: if (1 && 0 == N <= 0 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0])) +; GLOB: if (1 && 0 == N <= 0 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0])) +; NONAFFINE: if (1 && 0 == N <= 0 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0])) ; target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" Index: polly/trunk/test/Isl/Ast/alias_simple_3.ll =================================================================== --- polly/trunk/test/Isl/Ast/alias_simple_3.ll +++ polly/trunk/test/Isl/Ast/alias_simple_3.ll @@ -12,11 +12,11 @@ ; A[i] = B[i]; ; } ; -; NOAA: if (1 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0])) -; BASI: if (1) -; TBAA: if (1) -; SCEV: if (1 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0])) -; GLOB: if (1 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0])) +; NOAA: if (1 && 0 == N <= 0 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0])) +; BASI: if (1 && 0 == N <= 0) +; TBAA: if (1 && 0 == N <= 0) +; SCEV: if (1 && 0 == N <= 0 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0])) +; GLOB: if (1 && 0 == N <= 0 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0])) ; target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" Index: polly/trunk/test/Isl/Ast/aliasing_parametric_simple_2.ll =================================================================== --- polly/trunk/test/Isl/Ast/aliasing_parametric_simple_2.ll +++ polly/trunk/test/Isl/Ast/aliasing_parametric_simple_2.ll @@ -5,7 +5,7 @@ ; A[i] = B[c - 10] + B[5]; ; } ; -; CHECK: if (c >= -{{[0-9]*}} && (&MemRef_B[c <= 15 ? 6 : c - 9] <= &MemRef_A[0] || &MemRef_A[1024] <= &MemRef_B[c >= 15 ? 5 : c - 10])) +; CHECK: if (1 && 0 == c <= -{{[0-9]*}} && (&MemRef_B[c <= 15 ? 6 : c - 9] <= &MemRef_A[0] || &MemRef_A[1024] <= &MemRef_B[c >= 15 ? 5 : c - 10])) ; CHECK: for (int c0 = 0; c0 <= 1023; c0 += 1) ; CHECK: Stmt_for_body(c0); ; CHECK: else Index: polly/trunk/test/Isl/Ast/simple-run-time-condition.ll =================================================================== --- polly/trunk/test/Isl/Ast/simple-run-time-condition.ll +++ polly/trunk/test/Isl/Ast/simple-run-time-condition.ll @@ -17,11 +17,7 @@ ; for the delinearization is simplified such that conditions that would not ; cause any code to be executed are not generated. -; CHECK: if ( -; CHECK: (o >= 1 && n + p <= 9223372036854775808 && q <= 0 && m + q >= 0) -; CHECK: || -; CHECK; (o <= 0 && m + q >= 100 && q <= 100) -; CHECK: ) +; CHECK: if (((o >= 1 && q <= 0 && m + q >= 0) || (o <= 0 && m + q >= 100 && q <= 100)) && 0 == ((m >= 1 && n + p >= 9223372036854775809) || (o <= 0 && n >= 1 && m + q >= 9223372036854775909) || (o <= 0 && m >= 1 && n >= 1 && q <= -9223372036854775709))) ; CHECK: if (o <= 0) { ; CHECK: for (int c0 = 0; c0 < n; c0 += 1) Index: polly/trunk/test/Isl/CodeGen/aliasing_parametric_simple_2.ll =================================================================== --- polly/trunk/test/Isl/CodeGen/aliasing_parametric_simple_2.ll +++ polly/trunk/test/Isl/CodeGen/aliasing_parametric_simple_2.ll @@ -7,6 +7,7 @@ ; ; CHECK: sext i32 %c to i64 ; CHECK: sext i32 %c to i64 +; CHECK: %[[Ctx:[._a-zA-Z0-9]*]] = and i1 true ; CHECK: %[[M0:[._a-zA-Z0-9]*]] = sext i32 %c to i64 ; CHECK: %[[M1:[._a-zA-Z0-9]*]] = icmp sle i64 %[[M0]], 15 ; CHECK: %[[M2:[._a-zA-Z0-9]*]] = sext i32 %c to i64 @@ -24,7 +25,7 @@ ; CHECK: %[[BMin:[._a-zA-Z0-9]*]] = getelementptr i32, i32* %B, i64 %[[m4]] ; CHECK: %[[AltB:[._a-zA-Z0-9]*]] = icmp ule i32* %[[AMax]], %[[BMin]] ; CHECK: %[[NoAlias:[._a-zA-Z0-9]*]] = or i1 %[[BltA]], %[[AltB]] -; CHECK: %[[RTC:[._a-zA-Z0-9]*]] = and i1 %3, %[[NoAlias]] +; CHECK: %[[RTC:[._a-zA-Z0-9]*]] = and i1 %[[Ctx]], %[[NoAlias]] ; CHECK: br i1 %[[RTC]], label %polly.start, label %for.cond ; target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" Index: polly/trunk/test/Isl/CodeGen/large-numbers-in-boundary-context.ll =================================================================== --- polly/trunk/test/Isl/CodeGen/large-numbers-in-boundary-context.ll +++ polly/trunk/test/Isl/CodeGen/large-numbers-in-boundary-context.ll @@ -4,7 +4,7 @@ ; we will check that we use an appropriaty typed constant, here with 65 bits. ; An alternative would be to bail out early but that would not be as easy. ; -; CHECK: {{.*}} = icmp sge i65 {{.*}}, -9223372036854775809 +; CHECK: {{.*}} = icmp sle i65 {{.*}}, -9223372036854775810 ; ; CHECK: polly.start ; Index: polly/trunk/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_1.ll =================================================================== --- polly/trunk/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_1.ll +++ polly/trunk/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_1.ll @@ -16,8 +16,8 @@ ; SCALAR-NEXT: { : } ; SCALAR-NEXT: Assumed Context: ; SCALAR-NEXT: { : } -; SCALAR-NEXT: Boundary Context: -; SCALAR-NEXT: { : } +; SCALAR-NEXT: Invalid Context: +; SCALAR-NEXT: { : 1 = 0 } ; SCALAR-NEXT: Arrays { ; SCALAR-NEXT: i32 MemRef_C[*]; // Element size 4 ; SCALAR-NEXT: i32 MemRef_A[*]; // Element size 4 Index: polly/trunk/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_2.ll =================================================================== --- polly/trunk/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_2.ll +++ polly/trunk/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_2.ll @@ -24,8 +24,8 @@ ; INNERMOST-NEXT: [p_0, p_1, p_2] -> { : 0 <= p_0 <= 1048576 and 0 <= p_1 <= 1024 and 0 <= p_2 <= 1024 } ; INNERMOST-NEXT: Assumed Context: ; INNERMOST-NEXT: [p_0, p_1, p_2] -> { : } -; INNERMOST-NEXT: Boundary Context: -; INNERMOST-NEXT: [p_0, p_1, p_2] -> { : } +; INNERMOST-NEXT: Invalid Context: +; INNERMOST-NEXT: [p_0, p_1, p_2] -> { : 1 = 0 } ; INNERMOST-NEXT: p0: {0,+,{0,+,1}<%bb11>}<%bb13> ; INNERMOST-NEXT: p1: {0,+,1}<%bb11> ; INNERMOST-NEXT: p2: {0,+,1}<%bb13> @@ -75,8 +75,8 @@ ; ALL-NEXT: { : } ; ALL-NEXT: Assumed Context: ; ALL-NEXT: { : } -; ALL-NEXT: Boundary Context: -; ALL-NEXT: { : } +; ALL-NEXT: Invalid Context: +; ALL-NEXT: { : 1 = 0 } ; ALL-NEXT: Arrays { ; ALL-NEXT: i32 MemRef_A[*]; // Element size 4 ; ALL-NEXT: } Index: polly/trunk/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll =================================================================== --- polly/trunk/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll +++ polly/trunk/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll @@ -23,8 +23,8 @@ ; INNERMOST-NEXT: [p_0, p_1, p_2] -> { : 0 <= p_0 <= 2147483647 and 0 <= p_1 <= 1024 and 0 <= p_2 <= 1024 } ; INNERMOST-NEXT: Assumed Context: ; INNERMOST-NEXT: [p_0, p_1, p_2] -> { : } -; INNERMOST-NEXT: Boundary Context: -; INNERMOST-NEXT: [p_0, p_1, p_2] -> { : } +; INNERMOST-NEXT: Invalid Context: +; INNERMOST-NEXT: [p_0, p_1, p_2] -> { : p_0 < 0 } ; INNERMOST-NEXT: p0: {0,+,{0,+,1}<%bb11>}<%bb13> ; INNERMOST-NEXT: p1: {0,+,1}<%bb11> ; INNERMOST-NEXT: p2: {0,+,1}<%bb13> @@ -74,8 +74,8 @@ ; ALL-NEXT: { : } ; ALL-NEXT: Assumed Context: ; ALL-NEXT: { : } -; ALL-NEXT: Boundary Context: -; ALL-NEXT: { : } +; ALL-NEXT: Invalid Context: +; ALL-NEXT: { : 1 = 0 } ; ALL-NEXT: Arrays { ; ALL-NEXT: i32 MemRef_A[*]; // Element size 4 ; ALL-NEXT: } Index: polly/trunk/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_affine_loop.ll =================================================================== --- polly/trunk/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_affine_loop.ll +++ polly/trunk/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_affine_loop.ll @@ -29,8 +29,8 @@ ; ALL-NEXT: { : } ; ALL-NEXT: Assumed Context: ; ALL-NEXT: { : } -; ALL-NEXT: Boundary Context: -; ALL-NEXT: { : } +; ALL-NEXT: Invalid Context: +; ALL-NEXT: { : 1 = 0 } ; ALL-NEXT: Arrays { ; ALL-NEXT: i32 MemRef_A[*]; // Element size 4 ; ALL-NEXT: } Index: polly/trunk/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_non_affine_loop.ll =================================================================== --- polly/trunk/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_non_affine_loop.ll +++ polly/trunk/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_non_affine_loop.ll @@ -33,8 +33,8 @@ ; ALL-NEXT: { : } ; ALL-NEXT: Assumed Context: ; ALL-NEXT: { : } -; ALL-NEXT: Boundary Context: -; ALL-NEXT: { : } +; ALL-NEXT: Invalid Context: +; ALL-NEXT: { : 1 = 0 } ; ALL-NEXT: Arrays { ; ALL-NEXT: i32 MemRef_A[*]; // Element size 4 ; ALL-NEXT: } Index: polly/trunk/test/ScopInfo/NonAffine/non_affine_float_compare.ll =================================================================== --- polly/trunk/test/ScopInfo/NonAffine/non_affine_float_compare.ll +++ polly/trunk/test/ScopInfo/NonAffine/non_affine_float_compare.ll @@ -16,8 +16,8 @@ ; CHECK-NEXT: { : } ; CHECK-NEXT: Assumed Context: ; CHECK-NEXT: { : } -; CHECK-NEXT: Boundary Context: -; CHECK-NEXT: { : } +; CHECK-NEXT: Invalid Context: +; CHECK-NEXT: { : 1 = 0 } ; CHECK-NEXT: Arrays { ; CHECK-NEXT: float MemRef_A[*]; // Element size 4 ; CHECK-NEXT: } Index: polly/trunk/test/ScopInfo/NonAffine/non_affine_loop_condition.ll =================================================================== --- polly/trunk/test/ScopInfo/NonAffine/non_affine_loop_condition.ll +++ polly/trunk/test/ScopInfo/NonAffine/non_affine_loop_condition.ll @@ -30,8 +30,8 @@ ; CHECK-NEXT: { : } ; CHECK-NEXT: Assumed Context: ; CHECK-NEXT: { : } -; CHECK-NEXT: Boundary Context: -; CHECK-NEXT: { : } +; CHECK-NEXT: Invalid Context: +; CHECK-NEXT: { : 1 = 0 } ; CHECK-NEXT: Arrays { ; CHECK-NEXT: i32 MemRef_C[*]; // Element size 4 ; CHECK-NEXT: i32 MemRef_A[*]; // Element size 4 Index: polly/trunk/test/ScopInfo/NonAffine/non_affine_loop_used_later.ll =================================================================== --- polly/trunk/test/ScopInfo/NonAffine/non_affine_loop_used_later.ll +++ polly/trunk/test/ScopInfo/NonAffine/non_affine_loop_used_later.ll @@ -18,8 +18,8 @@ ; CHECK-NEXT: [N] -> { : -2147483648 <= N <= 2147483647 } ; CHECK-NEXT: Assumed Context: ; CHECK-NEXT: [N] -> { : } -; CHECK-NEXT: Boundary Context: -; CHECK-NEXT: [N] -> { : } +; CHECK-NEXT: Invalid Context: +; CHECK-NEXT: [N] -> { : 1 = 0 } ; CHECK-NEXT: p0: %N ; CHECK-NEXT: Arrays { ; CHECK-NEXT: i32 MemRef_j_0__phi; // Element size 4 Index: polly/trunk/test/ScopInfo/bounded_loop_assumptions.ll =================================================================== --- polly/trunk/test/ScopInfo/bounded_loop_assumptions.ll +++ polly/trunk/test/ScopInfo/bounded_loop_assumptions.ll @@ -7,7 +7,9 @@ ; finally, if N == 2 we would have an unbounded inner loop. ; ; CHECK: Assumed Context: -; CHECK-NEXT: [N] -> { : N >= 3 or N <= 1 } +; CHECK-NEXT: [N] -> { : } +; CHECK: Invalid Context: +; CHECK-NEXT: [N] -> { : N = 2 } ; ; int jd(int *restrict A, int x, int N) { ; for (int i = 1; i < N; i++) Index: polly/trunk/test/ScopInfo/long-sequence-of-error-blocks-2.ll =================================================================== --- polly/trunk/test/ScopInfo/long-sequence-of-error-blocks-2.ll +++ polly/trunk/test/ScopInfo/long-sequence-of-error-blocks-2.ll @@ -6,11 +6,13 @@ %struct.hoge = type { i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, [8 x [2 x i32]], [8 x [2 x i32]], [4 x [4 x i32]], i32, i32, i32, i32, [256 x i8], [256 x i8], [256 x i8], [256 x i8], [256 x i8], i32, i32, i32, i32, i32, i32, [500 x i8], i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, [256 x i8], [256 x i8], [256 x i8], i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, [1024 x i8], i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, double, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, [256 x i8], [256 x i8], i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, [256 x i8], i32, i32, i32*, i32*, i8*, i32*, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, double, double, double, [5 x double], i32, [8 x i32], i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, [6 x double], [6 x double], [256 x i8], i32, i32, i32, i32, [2 x [5 x i32]], [2 x [5 x i32]], i32, i32, i32, i32, i32, i32, i32, i32, i32, [3 x i32], i32 } ; The assumed context of this test case has at some point become very complex. -; This test case verifies that we bail out and generate an infeasible -; assumed context. It should be updated after having made the assumed context -; construction more efficient. - -; CHECK-NOT: Assumed Context: +; However, since we keep both the assumed as well as invalid context that +; problem is solved. +; +; CHECK: Assumed Context: +; CHECK-NEXT: [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { : } +; CHECK: Invalid Context: +; CHECK-NEXT: [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { : (tmp17 < 0 and tmp21 < 0) or (tmp17 < 0 and tmp21 > 0) or (tmp17 > 0 and tmp21 < 0) or (tmp17 > 0 and tmp21 > 0) or (tmp37 < 0 and tmp41 < 0 and tmp46 > 0) or (tmp37 < 0 and tmp41 > 0 and tmp46 > 0) or (tmp37 > 0 and tmp41 < 0 and tmp46 > 0) or (tmp37 > 0 and tmp41 > 0 and tmp46 > 0) or (tmp27 = 3 and tmp31 <= 143) or (tmp56 = 0 and tmp52 < 0) or (tmp56 = 0 and tmp52 > 0) } @global = external global [300 x i8], align 16 Index: polly/trunk/test/ScopInfo/long-sequence-of-error-blocks.ll =================================================================== --- polly/trunk/test/ScopInfo/long-sequence-of-error-blocks.ll +++ polly/trunk/test/ScopInfo/long-sequence-of-error-blocks.ll @@ -5,15 +5,14 @@ %struct.hoge = type { i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, [8 x [2 x i32]], [8 x [2 x i32]], [4 x [4 x i32]], i32, i32, i32, i32, [256 x i8], [256 x i8], [256 x i8], [256 x i8], [256 x i8], i32, i32, i32, i32, i32, i32, [500 x i8], i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, [256 x i8], [256 x i8], [256 x i8], i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, [1024 x i8], i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, double, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, [256 x i8], [256 x i8], i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, [256 x i8], i32, i32, i32*, i32*, i8*, i32*, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, double, double, double, [5 x double], i32, [8 x i32], i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, [6 x double], [6 x double], [256 x i8], i32, i32, i32, i32, [2 x [5 x i32]], [2 x [5 x i32]], i32, i32, i32, i32, i32, i32, i32, i32, i32, [3 x i32], i32 } -; The assumed context of this test case is still very large and should be -; reduced. - ; This test case contains a long sequence of branch instructions together with ; function calls that are considered 'error blocks'. We verify that the ; iteration spaces are not overly complicated. ; CHECK: Assumed Context: -; CHECK-NEXT: [tmp17, tmp21, tmp27, tmp31] -> { : (tmp17 = 0 and tmp27 >= 4) or (tmp17 = 0 and tmp27 <= 2) or (tmp21 = 0 and tmp17 < 0 and tmp27 >= 4) or (tmp21 = 0 and tmp17 < 0 and tmp27 <= 2) or (tmp21 = 0 and tmp17 > 0 and tmp27 >= 4) or (tmp21 = 0 and tmp17 > 0 and tmp27 <= 2) or (tmp17 = 0 and tmp27 = 3 and tmp31 >= 144) or (tmp21 = 0 and tmp27 = 3 and tmp17 < 0 and tmp31 >= 144) or (tmp21 = 0 and tmp27 = 3 and tmp17 > 0 and tmp31 >= 144) } +; CHECK-NEXT: [tmp17, tmp21, tmp27, tmp31] -> { : } +; CHECK: Invalid Context: +; CHECK-NEXT: [tmp17, tmp21, tmp27, tmp31] -> { : (tmp17 < 0 and tmp21 < 0) or (tmp17 < 0 and tmp21 > 0) or (tmp17 > 0 and tmp21 < 0) or (tmp17 > 0 and tmp21 > 0) or (tmp27 = 3 and tmp31 <= 143) } ; ; CHECK: Statements { ; CHECK-NEXT: Stmt_bb15 Index: polly/trunk/test/ScopInfo/multidim_2d_with_modref_call.ll =================================================================== --- polly/trunk/test/ScopInfo/multidim_2d_with_modref_call.ll +++ polly/trunk/test/ScopInfo/multidim_2d_with_modref_call.ll @@ -16,8 +16,8 @@ ; CHECK-NEXT: [tmp14, p_1] -> { : -9223372036854775808 <= tmp14 <= 9223372036854775807 and -9223372036854775808 <= p_1 <= 9223372036854775807 } ; CHECK-NEXT: Assumed Context: ; CHECK-NEXT: [tmp14, p_1] -> { : } -; CHECK-NEXT: Boundary Context: -; CHECK-NEXT: [tmp14, p_1] -> { : tmp14 <= 1152921504606846976 and (tmp14 <= 0 or (tmp14 > 0 and -1152921504606846976 <= p_1 <= 1152921504606846976 - tmp14)) } +; CHECK-NEXT: Invalid Context: +; CHECK-NEXT: [tmp14, p_1] -> { : tmp14 > 0 and (tmp14 >= 1152921504606846977 or p_1 <= -1152921504606846977 or p_1 >= 1152921504606846977 - tmp14) ; CHECK-NEXT: p0: %tmp14 ; CHECK-NEXT: p1: {0,+,(0 smax %tmp)}<%bb12> ; CHECK-NEXT: Arrays { @@ -69,8 +69,8 @@ ; NONAFFINE-NEXT: [tmp9, tmp14] -> { : -9223372036854775808 <= tmp9 <= 9223372036854775807 and -9223372036854775808 <= tmp14 <= 9223372036854775807 } ; NONAFFINE-NEXT: Assumed Context: ; NONAFFINE-NEXT: [tmp9, tmp14] -> { : } -; NONAFFINE-NEXT: Boundary Context: -; NONAFFINE-NEXT: [tmp9, tmp14] -> { : } +; NONAFFINE-NEXT: Invalid Context: +; NONAFFINE-NEXT: [tmp9, tmp14] -> { : 1 = 0 } ; NONAFFINE-NEXT: p0: %tmp9 ; NONAFFINE-NEXT: p1: %tmp14 ; NONAFFINE-NEXT: Arrays { Index: polly/trunk/test/ScopInfo/multidim_2d_with_modref_call_2.ll =================================================================== --- polly/trunk/test/ScopInfo/multidim_2d_with_modref_call_2.ll +++ polly/trunk/test/ScopInfo/multidim_2d_with_modref_call_2.ll @@ -16,8 +16,8 @@ ; CHECK-NEXT: [tmp14, p_1] -> { : -9223372036854775808 <= tmp14 <= 9223372036854775807 and -9223372036854775808 <= p_1 <= 9223372036854775807 } ; CHECK-NEXT: Assumed Context: ; CHECK-NEXT: [tmp14, p_1] -> { : } -; CHECK-NEXT: Boundary Context: -; CHECK-NEXT: [tmp14, p_1] -> { : tmp14 <= 1152921504606846976 and (tmp14 <= 0 or (tmp14 > 0 and -1152921504606846976 <= p_1 <= 1152921504606846976 - tmp14)) } +; CHECK-NEXT: Invalid Context: +; CHECK-NEXT: [tmp14, p_1] -> { : tmp14 > 0 and (tmp14 >= 1152921504606846977 or p_1 <= -1152921504606846977 or p_1 >= 1152921504606846977 - tmp14) } ; CHECK-NEXT: p0: %tmp14 ; CHECK-NEXT: p1: {0,+,(0 smax %tmp)}<%bb12> ; CHECK-NEXT: Arrays { @@ -67,8 +67,8 @@ ; NONAFFINE-NEXT: [tmp9, tmp14] -> { : -9223372036854775808 <= tmp9 <= 9223372036854775807 and -9223372036854775808 <= tmp14 <= 9223372036854775807 } ; NONAFFINE-NEXT: Assumed Context: ; NONAFFINE-NEXT: [tmp9, tmp14] -> { : } -; NONAFFINE-NEXT: Boundary Context: -; NONAFFINE-NEXT: [tmp9, tmp14] -> { : } +; NONAFFINE-NEXT: Invalid Context: +; NONAFFINE-NEXT: [tmp9, tmp14] -> { : 1 = 0 } ; NONAFFINE-NEXT: p0: %tmp9 ; NONAFFINE-NEXT: p1: %tmp14 ; NONAFFINE-NEXT: Arrays { Index: polly/trunk/test/ScopInfo/multidim_3d_parametric_array_static_loop_bounds.ll =================================================================== --- polly/trunk/test/ScopInfo/multidim_3d_parametric_array_static_loop_bounds.ll +++ polly/trunk/test/ScopInfo/multidim_3d_parametric_array_static_loop_bounds.ll @@ -11,6 +11,8 @@ ; CHECK: Assumed Context: ; CHECK-NEXT: [m, o] -> { : m >= 150 and o >= 200 } +; CHECK: Invalid Context: +; CHECK-NEXT: [m, o] -> { : 1 = 0 } ; ; CHECK: p0: %m ; CHECK-NEXT: p1: %o Index: polly/trunk/test/ScopInfo/multidim_fortran_2d_with_modref_call.ll =================================================================== --- polly/trunk/test/ScopInfo/multidim_fortran_2d_with_modref_call.ll +++ polly/trunk/test/ScopInfo/multidim_fortran_2d_with_modref_call.ll @@ -16,8 +16,8 @@ ; CHECK-NEXT: [tmp14, p_1] -> { : -9223372036854775808 <= tmp14 <= 9223372036854775807 and -9223372036854775808 <= p_1 <= 9223372036854775807 } ; CHECK-NEXT: Assumed Context: ; CHECK-NEXT: [tmp14, p_1] -> { : } -; CHECK-NEXT: Boundary Context: -; CHECK-NEXT: [tmp14, p_1] -> { : tmp14 <= 1152921504606846976 and (tmp14 <= 0 or (tmp14 > 0 and -1152921504606846976 <= p_1 <= 1152921504606846976 - tmp14)) } +; CHECK-NEXT: Invalid Context: +; CHECK-NEXT: [tmp14, p_1] -> { : tmp14 > 0 and (tmp14 >= 1152921504606846977 or p_1 <= -1152921504606846977 or p_1 >= 1152921504606846977 - tmp14) } ; CHECK-NEXT: p0: %tmp14 ; CHECK-NEXT: p1: {0,+,(0 smax %tmp)}<%bb12> ; CHECK-NEXT: Arrays { @@ -68,8 +68,8 @@ ; NONAFFINE-NEXT: [tmp9, tmp14] -> { : -9223372036854775808 <= tmp9 <= 9223372036854775807 and -9223372036854775808 <= tmp14 <= 9223372036854775807 } ; NONAFFINE-NEXT: Assumed Context: ; NONAFFINE-NEXT: [tmp9, tmp14] -> { : } -; NONAFFINE-NEXT: Boundary Context: -; NONAFFINE-NEXT: [tmp9, tmp14] -> { : } +; NONAFFINE-NEXT: Invalid Context: +; NONAFFINE-NEXT: [tmp9, tmp14] -> { : 1 = 0 } ; NONAFFINE-NEXT: p0: %tmp9 ; NONAFFINE-NEXT: p1: %tmp14 ; NONAFFINE-NEXT: Arrays { Index: polly/trunk/test/ScopInfo/non-pure-function-call.ll =================================================================== --- polly/trunk/test/ScopInfo/non-pure-function-call.ll +++ polly/trunk/test/ScopInfo/non-pure-function-call.ll @@ -1,7 +1,9 @@ ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s ; ; CHECK: Assumed Context: -; CHECK-NEXT: [N] -> { : N <= 101 } +; CHECK-NEXT: [N] -> { : } +; CHECK: Invalid Context: +; CHECK-NEXT: [N] -> { : N >= 102 } ; ; void g(void); ; void f(int *A, int N) { Index: polly/trunk/test/ScopInfo/non-pure-function-calls-causes-dead-blocks.ll =================================================================== --- polly/trunk/test/ScopInfo/non-pure-function-calls-causes-dead-blocks.ll +++ polly/trunk/test/ScopInfo/non-pure-function-calls-causes-dead-blocks.ll @@ -35,7 +35,9 @@ ; ; CHECK: Region: %entry.split---%if.end.20 ; CHECK: Assumed Context: -; CHECK-NEXT: [timeit, N] -> { : timeit = 0 } +; CHECK-NEXT: [timeit, N] -> { : } +; CHECK: Invalid Context: +; CHECK-NEXT: [timeit, N] -> { : timeit < 0 or timeit > 0 } ; CHECK: Statements { ; CHECK-NOT: Stmt_if_then_split ; CHECK: Stmt_for_body Index: polly/trunk/test/ScopInfo/non-pure-function-calls.ll =================================================================== --- polly/trunk/test/ScopInfo/non-pure-function-calls.ll +++ polly/trunk/test/ScopInfo/non-pure-function-calls.ll @@ -25,14 +25,16 @@ ; timer_stop(); ; } ; -; CHECK: Region: %for.cond---%if.end.20 -; CHECK: Assumed Context: -; CHECK: [N, timeit] -> { : timeit = 0 } -; CHECK: Statements { -; CHECK: Stmt -; CHECK: Stmt -; CHECK-NOT Stmt -; CHECK: } +; CHECK: Region: %for.cond---%if.end.20 +; CHECK: Assumed Context: +; CHECK-NEXT: [N, timeit] -> { : } +; CHECK: Invalid Context: +; CHECK-NEXT: [N, timeit] -> { : timeit < 0 or timeit > 0 } +; CHECK: Statements { +; CHECK: Stmt +; CHECK: Stmt +; CHECK-NOT: Stmt +; CHECK: } ; target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" Index: polly/trunk/test/ScopInfo/remarks.ll =================================================================== --- polly/trunk/test/ScopInfo/remarks.ll +++ polly/trunk/test/ScopInfo/remarks.ll @@ -1,10 +1,10 @@ ; RUN: opt %loadPolly -pass-remarks-analysis="polly-scops" -polly-scops -disable-output < %s 2>&1 | FileCheck %s ; ; CHECK: remark: test/ScopInfo/remarks.c:4:7: SCoP begins here. -; CHECK: remark: test/ScopInfo/remarks.c:8:5: Finite loop assumption: [M, N, Debug] -> { : M >= 0 or (M <= -2 and N <= 0) or (M = -1 and N <= 0) } -; CHECK: remark: test/ScopInfo/remarks.c:13:7: No-error assumption: [M, N, Debug] -> { : M < 0 or (M >= 0 and N <= 0) or (Debug = 0 and M >= 0 and N > 0) } -; CHECK: remark: test/ScopInfo/remarks.c:9:7: Inbounds assumption: [M, N, Debug] -> { : M <= 100 or (M > 0 and N <= 0) } -; CHECK: remark: :0:0: No-overflows assumption: [N, M, Debug] -> { : -2147483648 - N <= M <= 2147483647 - N } +; CHECK: remark: test/ScopInfo/remarks.c:8:5: Finite loop restriction: [M, N, Debug] -> { : N > 0 and (M <= -2 or M = -1) } +; CHECK: remark: test/ScopInfo/remarks.c:13:7: No-error restriction: [M, N, Debug] -> { : M >= 0 and N > 0 and (Debug < 0 or Debug > 0) } +; CHECK: remark: test/ScopInfo/remarks.c:9:7: Inbounds assumption: [M, N, Debug] -> { : M <= 100 or (M > 0 and N <= 0) } +; CHECK: remark: :0:0: No-overflows restriction: [N, M, Debug] -> { : M <= -2147483649 - N or M >= 2147483648 - N } ; CHECK: remark: test/ScopInfo/remarks.c:9:18: Possibly aliasing pointer, use restrict keyword. ; CHECK: remark: test/ScopInfo/remarks.c:9:33: Possibly aliasing pointer, use restrict keyword. ; CHECK: remark: test/ScopInfo/remarks.c:9:15: Possibly aliasing pointer, use restrict keyword. Index: polly/trunk/test/ScopInfo/test-wrapping-in-condition.ll =================================================================== --- polly/trunk/test/ScopInfo/test-wrapping-in-condition.ll +++ polly/trunk/test/ScopInfo/test-wrapping-in-condition.ll @@ -1,7 +1,7 @@ ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s ; -; CHECK: Boundary Context: -; CHECK: [N] -> { : N <= 128 } +; CHECK: Invalid Context: +; CHECK: [N] -> { : N >= 129 } ; ; #include ; #include Index: polly/trunk/test/ScopInfo/user_provided_assumptions.ll =================================================================== --- polly/trunk/test/ScopInfo/user_provided_assumptions.ll +++ polly/trunk/test/ScopInfo/user_provided_assumptions.ll @@ -9,11 +9,11 @@ ; CHECK-NEXT: remark: :0:0: SCoP ends here. ; SCOP: Context: -; SCOP-NEXT: [N, M, Debug] -> { : Debug = 0 and N > 0 and 0 < M <= 2147483647 - N and M <= 100 } +; SCOP-NEXT: [N, M, Debug] -> { : Debug = 0 and 0 < N <= 2147483647 and 0 < M <= 2147483647 - N and M <= 100 } ; SCOP: Assumed Context: ; SCOP-NEXT: [N, M, Debug] -> { : } -; SCOP: Boundary Context: -; SCOP-NEXT: [N, M, Debug] -> { : } +; SCOP: Invalid Context: +; SCOP-NEXT: [N, M, Debug] -> { : 1 = 0 } ; ; #include ; Index: polly/trunk/test/ScopInfo/wraping_signed_expr_0.ll =================================================================== --- polly/trunk/test/ScopInfo/wraping_signed_expr_0.ll +++ polly/trunk/test/ScopInfo/wraping_signed_expr_0.ll @@ -10,8 +10,8 @@ ; we will add the assumption that i+1 won't overflow only to the former. ; ; CHECK: Function: wrap -; CHECK: Boundary Context: -; CHECK: [N] -> { : N <= 125 } +; CHECK: Invalid Context: +; CHECK: [N] -> { : N >= 126 } ; ; ; FIXME: This is a negative test as nowrap should not need an assumed context. @@ -19,7 +19,7 @@ ; which lacks the flags we would need to avoid runtime checks. ; ; CHECK: Function: nowrap -; CHECK: Boundary Context: +; CHECK: Invalid Context: ; CHECK-NOT: [N] -> { : } ; target datalayout = "e-m:e-i8:64-f80:128-n8:16:32:64-S128" Index: polly/trunk/test/ScopInfo/wraping_signed_expr_1.ll =================================================================== --- polly/trunk/test/ScopInfo/wraping_signed_expr_1.ll +++ polly/trunk/test/ScopInfo/wraping_signed_expr_1.ll @@ -16,12 +16,12 @@ ; sizeof(long) == 8 ; ; CHECK: Function: wrap -; CHECK: Boundary Context: -; CHECK: [N] -> { : N <= 1152921504606846975 } +; CHECK: Invalid Context: +; CHECK-NEXT: [N] -> { : N >= 1152921504606846976 } ; ; CHECK: Function: nowrap -; CHECK: Boundary Context: -; CHECK: [N] -> { : } +; CHECK: Invalid Context: +; CHECK-NEXT: [N] -> { : 1 = 0 } ; target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" Index: polly/trunk/test/ScopInfo/wraping_signed_expr_2.ll =================================================================== --- polly/trunk/test/ScopInfo/wraping_signed_expr_2.ll +++ polly/trunk/test/ScopInfo/wraping_signed_expr_2.ll @@ -15,8 +15,8 @@ ; CHECK: Context: ; CHECK-NEXT: [N] -> { : -2147483648 <= N <= 2147483647 } ; -; CHECK: Boundary Context: -; CHECK-NEXT: [N] -> { : N <= 2147483618 } +; CHECK: Invalid Context: +; CHECK-NEXT: [N] -> { : N >= 2147483619 } target datalayout = "e-m:e-i32:64-f80:128-n8:16:32:64-S128" Index: polly/trunk/test/ScopInfo/wraping_signed_expr_3.ll =================================================================== --- polly/trunk/test/ScopInfo/wraping_signed_expr_3.ll +++ polly/trunk/test/ScopInfo/wraping_signed_expr_3.ll @@ -8,8 +8,8 @@ ; Note: 2147483648 == 2 ^ 31 ; ; CHECK: Function: wrap -; CHECK: Boundary Context: -; CHECK: [N, p] -> { : p <= 2147483648 - N } +; CHECK: Invalid Context: +; CHECK: [N, p] -> { : p >= 2147483649 - N } ; target datalayout = "e-m:e-i32:64-f80:128-n8:16:32:64-S128" Index: polly/trunk/test/ScopInfo/wraping_signed_expr_4.ll =================================================================== --- polly/trunk/test/ScopInfo/wraping_signed_expr_4.ll +++ polly/trunk/test/ScopInfo/wraping_signed_expr_4.ll @@ -10,8 +10,8 @@ ; CHECK: Context: ; CHECK-NEXT: [N, p] -> { : -128 <= N <= 127 and -128 <= p <= 127 } ; -; CHECK: Boundary Context: -; CHECK-NEXT: [N, p] -> { : p >= -127 } +; CHECK: Invalid Context: +; CHECK-NEXT: [N, p] -> { : p = -128 and N > 0 } target datalayout = "e-m:e-i8:64-f80:128-n8:16:32:64-S128" Index: polly/trunk/test/ScopInfo/wraping_signed_expr_5.ll =================================================================== --- polly/trunk/test/ScopInfo/wraping_signed_expr_5.ll +++ polly/trunk/test/ScopInfo/wraping_signed_expr_5.ll @@ -3,8 +3,8 @@ ; We should not generate runtime check for ((int)r1 + (int)r2) as it is known not ; to overflow. However (p + q) can, thus checks are needed. ; -; CHECK: Boundary Context: -; CHECK-NEXT: [r1, r2, q, p] -> { : r2 <= 127 + r1 and -2147483648 - q <= p <= 2147483647 - q } +; CHECK: Invalid Context: +; CHECK-NEXT: [r1, r2, q, p] -> { : r2 > r1 and (r2 >= 128 + r1 or p <= -2147483649 - q or p >= 2147483648 - q) } ; ; void wraps(int *A, int p, short q, char r1, char r2) { ; for (char i = r1; i < r2; i++) Index: polly/trunk/test/ScopInfo/wraping_signed_expr_6.ll =================================================================== --- polly/trunk/test/ScopInfo/wraping_signed_expr_6.ll +++ polly/trunk/test/ScopInfo/wraping_signed_expr_6.ll @@ -1,7 +1,7 @@ ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s ; -; CHECK: Boundary Context: -; CHECK: [N] -> { : N <= 128 } +; CHECK: Invalid Context: +; CHECK: [N] -> { : N >= 129 } ; ; void foo(float *A, long N) { ; for (long i = 0; i < N; i++) Index: polly/trunk/test/ScopInfo/wraping_signed_expr_7.ll =================================================================== --- polly/trunk/test/ScopInfo/wraping_signed_expr_7.ll +++ polly/trunk/test/ScopInfo/wraping_signed_expr_7.ll @@ -1,7 +1,7 @@ ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s ; -; CHECK: Boundary Context: -; CHECK: [N] -> { : N <= 128 } +; CHECK: Invalid Context: +; CHECK: [N] -> { : N >= 129 } ; ; void foo(float *A, long N) { ; for (long i = 0; i < N;)