Index: include/polly/CodeGen/IslAst.h =================================================================== --- include/polly/CodeGen/IslAst.h +++ include/polly/CodeGen/IslAst.h @@ -78,6 +78,26 @@ IslAst(Scop &Scop); void init(const Dependences &D); + + /// Extract precondition to include in RTC from an isl ast node + /// + /// @param Node The node to extract the condition from + /// @param Cond The set of conditions to add constraints to + /// + /// @returns A set of constraints from \p Node including \p Cond + /// + /// This method visits all nodes in the AST tree given by \p Node, + /// passing off all expression trees to + /// @link extractPreconditionFromAST(Expr, Cond) + isl_set *extractPreconditionFromAST(isl_ast_node *Node, isl_set *Cond); + + /// Extract precondition to include in RTC from an isl ast expression + /// + /// @param Expr The expression to extract the condition from + /// @param Cond The set of conditions to add constraints to + /// + /// @returns A set of constraints from \p Expr including \p Cond + isl_set *extractPreconditionFromAST(isl_ast_expr *Expr, isl_set *Cond); }; class IslAstInfo { Index: include/polly/CodeGen/IslExprBuilder.h =================================================================== --- include/polly/CodeGen/IslExprBuilder.h +++ include/polly/CodeGen/IslExprBuilder.h @@ -184,7 +184,48 @@ /// @return The llvm::Value* containing the result of the computation. llvm::Value *createAccessAddress(__isl_take isl_ast_expr *Expr); + /// Inject \p Bound into the expression generator. Normally, a node in the + /// AST tree is preceded by it's bound, therefore it's sufficient to store + /// the bound in @link CurrentBound before descending. + /// However, when generating nodes manually (e.g. as done in our + /// LoopGenerators), this does not work as the nodes we create do not form + /// a full AST tree. This function is therefore used in those instances to + /// manually inject a bound for the next expression before calling + /// @link create. + /// + /// @param Bound The bound to inject + void injectBound(__isl_keep isl_ast_expr *Bound); + + /// Execute the enclosed funtion with @link FixedSizeMode set to true. + template R withFixedSizeMode(std::function Fun) { + FixedSizeMode = true; + R Result = Fun(); + FixedSizeMode = false; + return Result; + }; + + /// Execute the enclosed funtion with @link FixedSizeMode set to true. + void withFixedSizeMode(std::function Fun) { + FixedSizeMode = true; + Fun(); + FixedSizeMode = false; + }; + private: + /// The current bound, that is the bound that we expect the next call of + /// @link getType to refer to. This is set everytime we encounter an AST + /// expression node with a type of isl_ast_expr_bound_t and cleared on every + /// call to @link getType. + isl_ast_expr *CurrentBound = nullptr; + + /// Whether to always use 64 bits. + /// If enabled, the expression generator will always use 64 bit types + /// regardless of what bounds were actually calculated. This is useful for + /// example when generating the RTC, where we track overflows and therefore + /// do not need to use types >64 bits, which can be generated for ISL in this + /// context. + bool FixedSizeMode = false; + Scop &S; /// Flag that will be set if an overflow occurred at runtime. @@ -223,6 +264,18 @@ llvm::Value *createInt(__isl_take isl_ast_expr *Expr); llvm::Value *createOpAddressOf(__isl_take isl_ast_expr *Expr); + /// Create a 'bound': An expression node with a type of isl_ast_expr_bound_t + /// is inserted into the AST expression tree directly above each 'numerical' + /// node. To use them, we store the bound in @link CurrentBound before + /// generating the inner expression which is then read by @link getType when + /// asked for the expression's type. + /// When encountering a bound while the previous bound is not consumed, it is + /// saved and restored after the subtree has been generated. + /// + /// @param Expr The expression to generate + /// @return The value the expression represents + llvm::Value *createBound(__isl_take isl_ast_expr *Expr); + /// Create a binary operation @p Opc and track overflows if requested. /// /// @param OpC The binary operation that should be performed [Add/Sub/Mul]. @@ -268,3 +321,4 @@ } // namespace polly #endif +/* vim: set ts=8 sw=8 tw=0 noet :*/ Index: lib/Analysis/ScopInfo.cpp =================================================================== --- lib/Analysis/ScopInfo.cpp +++ lib/Analysis/ScopInfo.cpp @@ -185,6 +185,21 @@ "polly-print-instructions", cl::desc("Output instructions per ScopStmt"), cl::Hidden, cl::Optional, cl::init(false), cl::cat(PollyCategory)); +static cl::opt ComputeBounds( + "polly-ast-compute-bounds", + cl::desc("Compute bounds on isl_asl_exprs to determine their type"), + cl::init(true), cl::Hidden, cl::Optional, cl::cat(PollyCategory)); + +static cl::opt ApproximateBounds( + "polly-ast-approximate-bounds", + cl::desc("Approximate compute bounds to speed up computation"), + cl::init(true), cl::Hidden, cl::Optional, cl::cat(PollyCategory)); + +static cl::opt MaximumNativeType( + "polly-ast-maximum-native-type", + cl::desc("Maximum native type, try to keep types smaller than this"), + cl::init(63), cl::Hidden, cl::Optional, cl::cat(PollyCategory)); + //===----------------------------------------------------------------------===// // Create a sequence of two schedules. Either argument may be null and is @@ -3572,6 +3587,12 @@ ID(getNextID((*R.getEntry()->getParent()).getName().str())) { if (IslOnErrorAbort) isl_options_set_on_error(getIslCtx(), ISL_ON_ERROR_ABORT); + isl_options_set_ast_build_compute_bounds(getIslCtx(), ComputeBounds); + isl_options_set_ast_build_maximum_native_type(getIslCtx(), MaximumNativeType); + isl_options_set_ast_build_approximate_computed_bounds(getIslCtx(), + ApproximateBounds); + isl_options_set_ast_build_print_computed_bounds(getIslCtx(), false); + buildContext(); } Index: lib/CodeGen/IslAst.cpp =================================================================== --- lib/CodeGen/IslAst.cpp +++ lib/CodeGen/IslAst.cpp @@ -37,6 +37,7 @@ #include "llvm/Analysis/RegionInfo.h" #include "llvm/Support/Debug.h" #include "isl/aff.h" +#include "isl/ast.h" #include "isl/ast_build.h" #include "isl/list.h" #include "isl/map.h" @@ -451,10 +452,100 @@ RunCondition = buildRunCondition(S, Build); Root = isl_ast_build_node_from_schedule(Build, S.getScheduleTree()); + isl_set *AdditionalConditionSet = + extractPreconditionFromAST(isl_ast_node_copy(Root), nullptr); + if (AdditionalConditionSet) { + AdditionalConditionSet = + isl_set_gist(AdditionalConditionSet, isl_set_params(S.getContext())); + isl_ast_expr *AdditionalConditions = + isl_ast_build_expr_from_set(Build, AdditionalConditionSet); + // As the set contains all parameter values we want to exclude, we need to + // negate it. + AdditionalConditions = isl_ast_expr_neg(AdditionalConditions); + RunCondition = isl_ast_expr_and(RunCondition, AdditionalConditions); + } isl_ast_build_free(Build); } +isl_set *IslAst::extractPreconditionFromAST(isl_ast_node *Node, isl_set *Cond) { + if (!Node) { + return Cond; + } + switch (isl_ast_node_get_type(Node)) { + case isl_ast_node_error: + llvm_unreachable("Code generation error"); + case isl_ast_node_mark: + Cond = extractPreconditionFromAST(isl_ast_node_mark_get_node(Node), Cond); + isl_ast_node_free(Node); + break; + case isl_ast_node_for: + Cond = extractPreconditionFromAST(isl_ast_node_for_get_init(Node), Cond); + Cond = extractPreconditionFromAST(isl_ast_node_for_get_inc(Node), Cond); + Cond = + extractPreconditionFromAST(isl_ast_node_for_get_iterator(Node), Cond); + Cond = extractPreconditionFromAST(isl_ast_node_for_get_body(Node), Cond); + isl_ast_node_free(Node); + break; + case isl_ast_node_if: + Cond = extractPreconditionFromAST(isl_ast_node_if_get_cond(Node), Cond); + Cond = extractPreconditionFromAST(isl_ast_node_if_get_then(Node), Cond); + Cond = extractPreconditionFromAST(isl_ast_node_if_get_else(Node), Cond); + isl_ast_node_free(Node); + break; + case isl_ast_node_user: + Cond = extractPreconditionFromAST(isl_ast_node_user_get_expr(Node), Cond); + isl_ast_node_free(Node); + break; + case isl_ast_node_block: + isl_ast_node_list *List = isl_ast_node_block_get_children(Node); + + for (int i = 0; i < isl_ast_node_list_n_ast_node(List); ++i) { + Cond = extractPreconditionFromAST(isl_ast_node_list_get_ast_node(List, i), + Cond); + } + isl_ast_node_list_free(List); + isl_ast_node_free(Node); + break; + } + return Cond; +} + +isl_set *IslAst::extractPreconditionFromAST(isl_ast_expr *Expr, isl_set *Cond) { + int NumArgs; + isl_set *OtherCondition; + + switch (isl_ast_expr_get_type(Expr)) { + case isl_ast_expr_error: + llvm_unreachable("Code generation error"); + case isl_ast_expr_op: + NumArgs = isl_ast_expr_get_op_n_arg(Expr); + for (int i = 0; i < NumArgs; i++) + Cond = extractPreconditionFromAST(isl_ast_expr_get_op_arg(Expr, i), Cond); + isl_ast_expr_free(Expr); + return Cond; + case isl_ast_expr_id: + isl_ast_expr_free(Expr); + return Cond; + case isl_ast_expr_int: + isl_ast_expr_free(Expr); + return Cond; + case isl_ast_expr_bound_t: + OtherCondition = isl_ast_expr_get_bound_condition(Expr); + if (OtherCondition) { + if (Cond) + Cond = isl_set_union(Cond, OtherCondition); + else + Cond = OtherCondition; + } + + Cond = extractPreconditionFromAST(isl_ast_expr_get_bound_expr(Expr), Cond); + + isl_ast_expr_free(Expr); + return Cond; + } +} + IslAst IslAst::create(Scop &Scop, const Dependences &D) { IslAst Ast{Scop}; Ast.init(D); Index: lib/CodeGen/IslExprBuilder.cpp =================================================================== --- lib/CodeGen/IslExprBuilder.cpp +++ lib/CodeGen/IslExprBuilder.cpp @@ -21,6 +21,17 @@ using namespace llvm; using namespace polly; +static cl::opt + UseBounds("polly-ast-use-bounds", + cl::desc("Use computed bounds to determine types"), + cl::init(true), cl::ZeroOrMore, cl::cat(PollyCategory)); + +static cl::opt + ExtendBounds("polly-ast-extend-bounds", + cl::desc("Extend types smaller than 64 bits to 64 bits"), + cl::init(true), cl::Hidden, cl::Optional, + cl::cat(PollyCategory)); + /// Different overflow tracking modes. enum OverflowTrackingChoice { OT_NEVER, ///< Never tack potential overflows. @@ -713,10 +724,34 @@ } IntegerType *IslExprBuilder::getType(__isl_keep isl_ast_expr *Expr) { - // XXX: We assume i64 is large enough. This is often true, but in general - // incorrect. Also, on 32bit architectures, it would be beneficial to - // use a smaller type. We can and should directly derive this information - // during code generation. + if (isl_options_get_ast_build_compute_bounds(isl_ast_expr_get_ctx(Expr)) && + UseBounds && !FixedSizeMode) { + if (CurrentBound == NULL) { + // Bail out with verbose error during dev: + llvm::errs() << "BEGIN EXPR\n"; + isl_printer *p = isl_printer_to_file(isl_ast_expr_get_ctx(Expr), stderr); + p = isl_printer_set_output_format(p, ISL_FORMAT_C); + p = isl_printer_print_ast_expr(p, Expr); + isl_printer_free(p); + llvm::errs() << "\nEND EXPR\n"; + llvm_unreachable("Unbound expression!"); + } + + int size = isl_ast_expr_get_bound_bits(CurrentBound); + if (isl_ast_expr_get_bound_signed(CurrentBound) != isl_bool_true) + size++; + + // Extend to 64. After discussing this with Tobias, it might actually be + // more useful to only use the exact type for annotations and only use this + // for code generation on specific request. For now, there is a flag to + // toggle this behaviour. + if (size < 64 && ExtendBounds) + size = 64; + + CurrentBound = nullptr; + return IntegerType::get(Builder.getContext(), size); + } + CurrentBound = nullptr; return IntegerType::get(Builder.getContext(), 64); } @@ -754,7 +789,31 @@ return createId(Expr); case isl_ast_expr_int: return createInt(Expr); + case isl_ast_expr_bound_t: + return createBound(Expr); } llvm_unreachable("Unexpected enum value"); } + +Value *IslExprBuilder::createBound(__isl_take isl_ast_expr *Expr) { + Value *V; + assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_bound_t && + "Expression not of type isl_ast_expr_bound_t"); + + isl_ast_expr *OldBound = CurrentBound; + CurrentBound = Expr; + V = create(isl_ast_expr_get_bound_expr(Expr)); + isl_ast_expr_free(Expr); + CurrentBound = OldBound; + return V; +} + +void IslExprBuilder::injectBound(__isl_keep isl_ast_expr *Bound) { + if (UseBounds) { + assert(!CurrentBound && + "Cannot inject bound while previous bound is not consumed"); + + CurrentBound = Bound; + } +} Index: lib/CodeGen/IslNodeBuilder.cpp =================================================================== --- lib/CodeGen/IslNodeBuilder.cpp +++ lib/CodeGen/IslNodeBuilder.cpp @@ -76,11 +76,22 @@ IslNodeBuilder::getUpperBound(__isl_keep isl_ast_node *For, ICmpInst::Predicate &Predicate) { isl_id *UBID, *IteratorID; - isl_ast_expr *Cond, *Iterator, *UB, *Arg0; + isl_ast_expr *Cond, *Tmp, *Iterator, *UB, *Arg0; isl_ast_op_type Type; Cond = isl_ast_node_for_get_cond(For); + if (isl_ast_expr_get_type(Cond) == isl_ast_expr_bound_t) { + Tmp = Cond; + Cond = isl_ast_expr_get_bound_expr(Cond); + isl_ast_expr_free(Tmp); + } Iterator = isl_ast_node_for_get_iterator(For); + if (isl_ast_expr_get_type(Iterator) == isl_ast_expr_bound_t) { + Tmp = Iterator; + Iterator = isl_ast_expr_get_bound_expr(Iterator); + isl_ast_expr_free(Tmp); + } + isl_ast_expr_get_type(Cond); assert(isl_ast_expr_get_type(Cond) == isl_ast_expr_op && "conditional expression is not an atomic upper bound"); @@ -99,6 +110,11 @@ } Arg0 = isl_ast_expr_get_op_arg(Cond, 0); + if (isl_ast_expr_get_type(Arg0) == isl_ast_expr_bound_t) { + Tmp = Arg0; + Arg0 = isl_ast_expr_get_bound_expr(Arg0); + isl_ast_expr_free(Tmp); + } assert(isl_ast_expr_get_type(Arg0) == isl_ast_expr_id && "conditional expression is not an atomic upper bound"); @@ -128,6 +144,11 @@ /// by passed isl_ast_expr_int. static bool checkIslAstExprInt(__isl_take isl_ast_expr *Expr, isl_bool (*Predicate)(__isl_keep isl_val *)) { + if (isl_ast_expr_get_type(Expr) == isl_ast_expr_bound_t) { + auto Tmp0 = Expr; + Expr = isl_ast_expr_get_bound_expr(Expr); + isl_ast_expr_free(Tmp0); + } if (isl_ast_expr_get_type(Expr) != isl_ast_expr_int) { isl_ast_expr_free(Expr); return false; @@ -179,6 +200,11 @@ return -1; CmpInst::Predicate Predicate; auto UB = getUpperBound(For, Predicate); + if (isl_ast_expr_get_type(UB) == isl_ast_expr_bound_t) { + auto Tmp0 = UB; + UB = isl_ast_expr_get_bound_expr(UB); + isl_ast_expr_free(Tmp0); + } if (isl_ast_expr_get_type(UB) != isl_ast_expr_int) { isl_ast_expr_free(UB); return -1; @@ -405,12 +431,27 @@ isl_ast_expr *Init = isl_ast_node_for_get_init(For); isl_ast_expr *Inc = isl_ast_node_for_get_inc(For); isl_ast_expr *Iterator = isl_ast_node_for_get_iterator(For); - isl_id *IteratorID = isl_ast_expr_get_id(Iterator); + isl_id *IteratorID; + if (isl_ast_expr_get_type(Iterator) == isl_ast_expr_bound_t) { + auto Content = isl_ast_expr_get_bound_expr(Iterator); + IteratorID = isl_ast_expr_get_id(Content); + isl_ast_expr_free(Content); + } else { + IteratorID = isl_ast_expr_get_id(Iterator); + } Value *ValueLB = ExprBuilder.create(Init); Value *ValueInc = ExprBuilder.create(Inc); - Type *MaxType = ExprBuilder.getType(Iterator); + Type *MaxType; + if (isl_ast_expr_get_type(Iterator) == isl_ast_expr_bound_t) { + ExprBuilder.injectBound(Iterator); + auto Content = isl_ast_expr_get_bound_expr(Iterator); + MaxType = ExprBuilder.getType(Content); + isl_ast_expr_free(Content); + } else { + MaxType = ExprBuilder.getType(Iterator); + } MaxType = ExprBuilder.getWidestType(MaxType, ValueLB->getType()); MaxType = ExprBuilder.getWidestType(MaxType, ValueInc->getType()); @@ -462,7 +503,7 @@ void IslNodeBuilder::createForSequential(__isl_take isl_ast_node *For, bool KnownParallel) { isl_ast_node *Body; - isl_ast_expr *Init, *Inc, *Iterator, *UB; + isl_ast_expr *Init, *Inc, *Iterator, *IteratorContent, *UB; isl_id *IteratorID; Value *ValueLB, *ValueUB, *ValueInc; Type *MaxType; @@ -485,14 +526,38 @@ Init = isl_ast_node_for_get_init(For); Inc = isl_ast_node_for_get_inc(For); Iterator = isl_ast_node_for_get_iterator(For); - IteratorID = isl_ast_expr_get_id(Iterator); + + if (isl_ast_expr_get_type(Iterator) == isl_ast_expr_bound_t) { + IteratorContent = isl_ast_expr_get_bound_expr(Iterator); + IteratorID = isl_ast_expr_get_id(IteratorContent); + isl_ast_expr_free(IteratorContent); + } else { + IteratorID = isl_ast_expr_get_id(Iterator); + } UB = getUpperBound(For, Predicate); ValueLB = ExprBuilder.create(Init); ValueUB = ExprBuilder.create(UB); ValueInc = ExprBuilder.create(Inc); - MaxType = ExprBuilder.getType(Iterator); + // When computing bounds, the iterator will be a subtree of the shape + // .... + // | + // isl_ast_expr_bound_t + // | + // isl_ast_expr + // When codegenerating this tree, the visitor would store the bound before + // descending, but we're not using the visitor. If there are no bound nodes, + // we can simply use getType(Iterator), but if we compute bounds + // (polly-ast-compute-bounds is set), we have to do this differently... + if (isl_ast_expr_get_type(Iterator) == isl_ast_expr_bound_t) { + ExprBuilder.injectBound(Iterator); + IteratorContent = isl_ast_expr_get_bound_expr(Iterator); + MaxType = ExprBuilder.getType(IteratorContent); + isl_ast_expr_free(IteratorContent); + } else { + MaxType = ExprBuilder.getType(Iterator); + } MaxType = ExprBuilder.getWidestType(MaxType, ValueLB->getType()); MaxType = ExprBuilder.getWidestType(MaxType, ValueUB->getType()); MaxType = ExprBuilder.getWidestType(MaxType, ValueInc->getType()); @@ -571,7 +636,7 @@ void IslNodeBuilder::createForParallel(__isl_take isl_ast_node *For) { isl_ast_node *Body; - isl_ast_expr *Init, *Inc, *Iterator, *UB; + isl_ast_expr *Init, *Inc, *Iterator, *UB, *IteratorContent; isl_id *IteratorID; Value *ValueLB, *ValueUB, *ValueInc; Type *MaxType; @@ -590,7 +655,13 @@ Init = isl_ast_node_for_get_init(For); Inc = isl_ast_node_for_get_inc(For); Iterator = isl_ast_node_for_get_iterator(For); - IteratorID = isl_ast_expr_get_id(Iterator); + if (isl_ast_expr_get_type(Iterator) == isl_ast_expr_bound_t) { + IteratorContent = isl_ast_expr_get_bound_expr(Iterator); + IteratorID = isl_ast_expr_get_id(IteratorContent); + isl_ast_expr_free(IteratorContent); + } else { + IteratorID = isl_ast_expr_get_id(Iterator); + } UB = getUpperBound(For, Predicate); ValueLB = ExprBuilder.create(Init); @@ -603,7 +674,24 @@ ValueUB = Builder.CreateAdd( ValueUB, Builder.CreateSExt(Builder.getTrue(), ValueUB->getType())); - MaxType = ExprBuilder.getType(Iterator); + // When computing bounds, the iterator will be a subtree of the shape + // .... + // | + // isl_ast_expr_bound_t + // | + // isl_ast_expr + // When codegenerating this tree, the visitor would store the bound before + // descending, but we're not using the visitor. If there are no bound nodes, + // we can simply use getType(Iterator), but if we compute bounds + // (polly-ast-compute-bounds is set), we have to do this differently... + if (isl_ast_expr_get_type(Iterator) == isl_ast_expr_bound_t) { + ExprBuilder.injectBound(Iterator); + IteratorContent = isl_ast_expr_get_bound_expr(Iterator); + MaxType = ExprBuilder.getType(IteratorContent); + isl_ast_expr_free(IteratorContent); + } else { + MaxType = ExprBuilder.getType(Iterator); + } MaxType = ExprBuilder.getWidestType(MaxType, ValueLB->getType()); MaxType = ExprBuilder.getWidestType(MaxType, ValueUB->getType()); MaxType = ExprBuilder.getWidestType(MaxType, ValueInc->getType()); @@ -1170,7 +1258,8 @@ return nullptr; } - auto *Build = isl_ast_build_from_context(isl_set_universe(S.getParamSpace())); + isl_ast_build *Build = isl_ast_build_from_context(S.getContext()); + isl_set *Universe = isl_set_universe(isl_set_get_space(Domain)); bool AlwaysExecuted = isl_set_is_equal(Domain, Universe); isl_set_free(Universe); @@ -1517,22 +1606,25 @@ Value *IslNodeBuilder::createRTC(isl_ast_expr *Condition) { auto ExprBuilder = getExprBuilder(); ExprBuilder.setTrackOverflow(true); - Value *RTC = ExprBuilder.create(Condition); - if (!RTC->getType()->isIntegerTy(1)) - RTC = Builder.CreateIsNotNull(RTC); - Value *OverflowHappened = - Builder.CreateNot(ExprBuilder.getOverflowState(), "polly.rtc.overflown"); - - if (PollyGenerateRTCPrint) { - auto *F = Builder.GetInsertBlock()->getParent(); - RuntimeDebugBuilder::createCPUPrinter( - Builder, - "F: " + F->getName().str() + " R: " + S.getRegion().getNameStr() + - " __RTC: ", - RTC, " Overflow: ", OverflowHappened, "\n"); - } + Value *RTC; + ExprBuilder.withFixedSizeMode([&]() { + RTC = ExprBuilder.create(Condition); + if (!RTC->getType()->isIntegerTy(1)) + RTC = Builder.CreateIsNotNull(RTC); + Value *OverflowHappened = Builder.CreateNot(ExprBuilder.getOverflowState(), + "polly.rtc.overflown"); + + if (PollyGenerateRTCPrint) { + auto *F = Builder.GetInsertBlock()->getParent(); + RuntimeDebugBuilder::createCPUPrinter( + Builder, + "F: " + F->getName().str() + " R: " + S.getRegion().getNameStr() + + " __RTC: ", + RTC, " Overflow: ", OverflowHappened, "\n"); + } - RTC = Builder.CreateAnd(RTC, OverflowHappened, "polly.rtc.result"); + RTC = Builder.CreateAnd(RTC, OverflowHappened, "polly.rtc.result"); + }); ExprBuilder.setTrackOverflow(false); if (!isa(RTC)) Index: lib/CodeGen/LoopGenerators.cpp =================================================================== --- lib/CodeGen/LoopGenerators.cpp +++ lib/CodeGen/LoopGenerators.cpp @@ -161,7 +161,7 @@ // Add one as the upper bound provided by OpenMP is a < comparison // whereas the codegenForSequential function creates a <= comparison. - UB = Builder.CreateAdd(UB, ConstantInt::get(LongType, 1)); + UB = Builder.CreateAdd(UB, ConstantInt::get(UB->getType(), 1)); // Tell the runtime we start a parallel loop createCallSpawnThreads(SubFn, SubFnParam, LB, UB, Stride); Index: lib/CodeGen/PPCGCodeGeneration.cpp =================================================================== --- lib/CodeGen/PPCGCodeGeneration.cpp +++ lib/CodeGen/PPCGCodeGeneration.cpp @@ -1026,7 +1026,8 @@ Res = isl_ast_expr_mul(Res, Expr); } - Value *NumElements = ExprBuilder.create(Res); + Value *NumElements = + ExprBuilder.withFixedSizeMode([&]() { ExprBuilder.create(Res); }); if (NumElements->getType() != ArraySize->getType()) NumElements = Builder.CreateSExt(NumElements, ArraySize->getType()); ArraySize = Builder.CreateMul(ArraySize, NumElements); @@ -1070,7 +1071,9 @@ Result = isl_ast_expr_add(Result, MExpr); } - Value *ResultValue = ExprBuilder.create(Result); + Value *ResultValue = + ExprBuilder.withFixedSizeMode([&]() { ExprBuilder.create(Result); }); + isl_set_free(Min); isl_ast_build_free(Build); @@ -1227,10 +1230,14 @@ void GPUNodeBuilder::createKernelCopy(ppcg_kernel_stmt *KernelStmt) { isl_ast_expr *LocalIndex = isl_ast_expr_copy(KernelStmt->u.c.local_index); LocalIndex = isl_ast_expr_address_of(LocalIndex); - Value *LocalAddr = ExprBuilder.create(LocalIndex); - isl_ast_expr *Index = isl_ast_expr_copy(KernelStmt->u.c.index); - Index = isl_ast_expr_address_of(Index); - Value *GlobalAddr = ExprBuilder.create(Index); + + Value *GlobalAddr, *LocalAddr; + ExprBuilder.withFixedSizeMode([&]() { + LocalAddr = ExprBuilder.create(LocalIndex); + isl_ast_expr *Index = isl_ast_expr_copy(KernelStmt->u.c.index); + Index = isl_ast_expr_address_of(Index); + GlobalAddr = ExprBuilder.create(Index); + }); if (KernelStmt->u.c.read) { LoadInst *Load = Builder.CreateLoad(GlobalAddr, "shared.read"); @@ -3167,7 +3174,7 @@ Builder.SetInsertPoint(SplitBlock->getTerminator()); NodeBuilder.addParameters(S->getContext()); - isl_ast_build *Build = isl_ast_build_alloc(S->getIslCtx()); + isl_ast_build *Build = isl_ast_build_from_context(S->getContext()); isl_ast_expr *Condition = IslAst::buildRunCondition(*S, Build); isl_ast_expr *SufficientCompute = createSufficientComputeCheck(*S, Build); Condition = isl_ast_expr_and(Condition, SufficientCompute); Index: lib/External/isl/codegen.c =================================================================== --- lib/External/isl/codegen.c +++ lib/External/isl/codegen.c @@ -21,18 +21,25 @@ #include #include #include +#include #include #include -#include #include -#include #include #include +#include +#include "isl_ast_private.h" +#include "isl_ast_build_private.h" +#include "isl_union_map_private.h" +#include "isl_aff_private.h" +#include "isl_space_private.h" +#include "isl_options_private.h" struct options { struct isl_options *isl; unsigned atomic; unsigned separate; + char* infile; }; ISL_ARGS_START(struct options, options_args) @@ -41,6 +48,7 @@ "globally set the atomic option") ISL_ARG_BOOL(struct options, separate, 0, "separate", 0, "globally set the separate option") +ISL_ARG_STR(struct options, infile, 0, "infile", "file", "-", "File to read instead of stdin or - for stdin") ISL_ARGS_END ISL_ARG_DEF(cg_options, struct options, options_args) @@ -108,19 +116,25 @@ return build; } +struct ast_from_union_ret { + isl_ast_node* tree; + isl_ast_expr* expr; +}; /* Construct an AST in case the schedule is specified by a union map. * * We read the context and the options from "s" and construct the AST. */ -static __isl_give isl_ast_node *construct_ast_from_union_map( +static __isl_give struct ast_from_union_ret *construct_ast_from_union_map( __isl_take isl_union_map *schedule, __isl_keep isl_stream *s) { isl_set *context; isl_union_map *options_map; - isl_ast_build *build; + isl_ast_build *build, *aff_build; isl_ast_node *tree; struct options *options; - + struct isl_obj obj; + isl_ast_expr *expr = NULL; + struct ast_from_union_ret *retval; options = isl_ctx_peek_cg_options(isl_stream_get_ctx(s)); context = isl_stream_read_set(s); @@ -129,9 +143,24 @@ build = isl_ast_build_from_context(context); build = set_options(build, options_map, options, schedule); tree = isl_ast_build_node_from_schedule_map(build, schedule); + isl_pw_aff *aff = isl_stream_read_pw_aff(s); + if (aff) { + aff_build = isl_ast_build_copy(build); + aff_build = isl_ast_build_set_single_valued(aff_build, 0); + aff_build = isl_ast_build_init_options(aff_build); + expr = isl_ast_build_expr_from_pw_aff(aff_build, aff); + isl_ast_build_free(aff_build); + } + isl_ast_build_free(build); - return tree; + retval = malloc(sizeof(struct ast_from_union_ret)); + if (expr) + retval->expr = expr; + else + retval->expr = NULL; + retval->tree = tree; + return retval; } /* If "node" is a band node, then replace the AST build options @@ -200,11 +229,14 @@ { isl_ctx *ctx; isl_stream *s; + struct ast_from_union_ret *retval = NULL; isl_ast_node *tree = NULL; struct options *options; isl_printer *p; struct isl_obj obj; int r = EXIT_SUCCESS; + FILE *fd; + isl_ast_expr *expr = NULL; options = cg_options_new_with_defaults(); assert(options); @@ -212,17 +244,35 @@ isl_options_set_ast_build_detect_min_max(ctx, 1); argc = cg_options_parse(options, argc, argv, ISL_ARG_ALL); - s = isl_stream_new_file(ctx, stdin); + if (strcmp(options->infile, "-") != 0) { + fd = fopen(options->infile, "r"); + if (!fd) { + isl_die(ctx, isl_error_invalid, "Couldn't open file", + r = EXIT_FAILURE); + return r; + } + } else { + fd = stdin; + } + + s = isl_stream_new_file(ctx, fd); obj = isl_stream_read_obj(s); + if (obj.v == NULL) { r = EXIT_FAILURE; } else if (obj.type == isl_obj_map) { isl_union_map *umap; umap = isl_union_map_from_map(obj.v); - tree = construct_ast_from_union_map(umap, s); + retval = construct_ast_from_union_map(umap, s); + tree = retval->tree; + expr = retval->expr; + free(retval); } else if (obj.type == isl_obj_union_map) { - tree = construct_ast_from_union_map(obj.v, s); + retval = construct_ast_from_union_map(obj.v, s); + tree = retval->tree; + expr = retval->expr; + free(retval); } else if (obj.type == isl_obj_schedule) { tree = construct_ast_from_schedule(obj.v); } else { @@ -230,15 +280,27 @@ isl_die(ctx, isl_error_invalid, "unknown input", r = EXIT_FAILURE); } + p = isl_printer_to_file(ctx, stdout); isl_stream_free(s); - p = isl_printer_to_file(ctx, stdout); - p = isl_printer_set_output_format(p, ISL_FORMAT_C); +//if (isl_options_get_ast_build_print_computed_bounds(ctx)) { + p = isl_printer_set_output_format(p, ISL_FORMAT_C); +/* p = isl_printer_set_yaml_style(p, ISL_YAML_STYLE_BLOCK);*/ +/* } else { + p = isl_printer_set_output_format(p, ISL_FORMAT_C); + }*/ p = isl_printer_print_ast_node(p, tree); + if (expr) { + p = isl_printer_print_ast_expr(p, expr); + isl_ast_expr_free(expr); + } + isl_printer_free(p); isl_ast_node_free(tree); isl_ctx_free(ctx); + if (fd != stdin) + fclose(fd); return r; } Index: lib/External/isl/include/isl/ast.h =================================================================== --- lib/External/isl/include/isl/ast.h +++ lib/External/isl/include/isl/ast.h @@ -19,6 +19,9 @@ isl_stat isl_options_set_ast_always_print_block(isl_ctx *ctx, int val); int isl_options_get_ast_always_print_block(isl_ctx *ctx); +isl_stat isl_options_set_ast_build_print_computed_bounds(isl_ctx *ctx, int val); +int isl_options_get_ast_build_print_computed_bounds(isl_ctx *ctx); + __isl_give isl_ast_expr *isl_ast_expr_from_val(__isl_take isl_val *v); __isl_give isl_ast_expr *isl_ast_expr_from_id(__isl_take isl_id *id); __isl_give isl_ast_expr *isl_ast_expr_neg(__isl_take isl_ast_expr *expr); @@ -57,6 +60,8 @@ __isl_give isl_ast_expr *isl_ast_expr_call(__isl_take isl_ast_expr *function, __isl_take isl_ast_expr_list *arguments); __isl_give isl_ast_expr *isl_ast_expr_address_of(__isl_take isl_ast_expr *expr); +__isl_give isl_ast_expr *isl_ast_expr_bound(__isl_take isl_ast_expr *expr, + isl_bool is_signed, unsigned int size, __isl_take isl_set *conditions); __isl_give isl_ast_expr *isl_ast_expr_copy(__isl_keep isl_ast_expr *expr); __isl_null isl_ast_expr *isl_ast_expr_free(__isl_take isl_ast_expr *expr); @@ -66,6 +71,11 @@ __isl_give isl_val *isl_ast_expr_get_val(__isl_keep isl_ast_expr *expr); __isl_give isl_id *isl_ast_expr_get_id(__isl_keep isl_ast_expr *expr); +unsigned int isl_ast_expr_get_bound_bits(__isl_keep isl_ast_expr *expr); +isl_bool isl_ast_expr_get_bound_signed(__isl_keep isl_ast_expr *expr); +__isl_give isl_ast_expr* isl_ast_expr_get_bound_expr (__isl_keep isl_ast_expr *expr); +__isl_give isl_set* isl_ast_expr_get_bound_condition (__isl_keep isl_ast_expr *expr); + enum isl_ast_op_type isl_ast_expr_get_op_type(__isl_keep isl_ast_expr *expr); int isl_ast_expr_get_op_n_arg(__isl_keep isl_ast_expr *expr); __isl_give isl_ast_expr *isl_ast_expr_get_op_arg(__isl_keep isl_ast_expr *expr, Index: lib/External/isl/include/isl/ast_build.h =================================================================== --- lib/External/isl/include/isl/ast_build.h +++ lib/External/isl/include/isl/ast_build.h @@ -20,6 +20,12 @@ isl_stat isl_options_set_ast_build_prefer_pdiv(isl_ctx *ctx, int val); int isl_options_get_ast_build_prefer_pdiv(isl_ctx *ctx); +isl_stat isl_options_set_ast_build_compute_bounds(isl_ctx *ctx, int val); +int isl_options_get_ast_build_compute_bounds(isl_ctx *ctx); +isl_stat isl_options_set_ast_build_approximate_computed_bounds(isl_ctx *ctx, int val); +int isl_options_get_ast_build_approximate_computed_bounds(isl_ctx *ctx); +isl_stat isl_options_set_ast_build_maximum_native_type(isl_ctx *ctx, int val); +int isl_options_get_ast_build_maximum_native_type(isl_ctx *ctx); isl_stat isl_options_set_ast_build_detect_min_max(isl_ctx *ctx, int val); int isl_options_get_ast_build_detect_min_max(isl_ctx *ctx); @@ -121,6 +127,9 @@ __isl_give isl_ast_node *isl_ast_build_ast_from_schedule( __isl_keep isl_ast_build *build, __isl_take isl_union_map *schedule); +__isl_give isl_ast_expr *isl_ast_bin_op_set_size(__isl_take isl_ast_expr *expr, + __isl_keep isl_ast_build *build); + #if defined(__cplusplus) } #endif Index: lib/External/isl/include/isl/ast_type.h =================================================================== --- lib/External/isl/include/isl/ast_type.h +++ lib/External/isl/include/isl/ast_type.h @@ -47,7 +47,8 @@ isl_ast_expr_error = -1, isl_ast_expr_op, isl_ast_expr_id, - isl_ast_expr_int + isl_ast_expr_int, + isl_ast_expr_bound_t }; enum isl_ast_node_type { Index: lib/External/isl/include/isl/stream.h =================================================================== --- lib/External/isl/include/isl/stream.h +++ lib/External/isl/include/isl/stream.h @@ -83,6 +83,7 @@ __isl_give isl_union_set *isl_stream_read_union_set(__isl_keep isl_stream *s); __isl_give isl_union_map *isl_stream_read_union_map(__isl_keep isl_stream *s); __isl_give isl_schedule *isl_stream_read_schedule(isl_stream *s); +__isl_give isl_pw_aff *isl_stream_read_pw_aff(__isl_keep isl_stream *s); int isl_stream_yaml_read_start_mapping(__isl_keep isl_stream *s); int isl_stream_yaml_read_end_mapping(__isl_keep isl_stream *s); Index: lib/External/isl/include/isl/val.h =================================================================== --- lib/External/isl/include/isl/val.h +++ lib/External/isl/include/isl/val.h @@ -160,6 +160,8 @@ void isl_multi_val_dump(__isl_keep isl_multi_val *mv); __isl_give char *isl_multi_val_to_str(__isl_keep isl_multi_val *mv); +int isl_val_size_in_bits(__isl_keep isl_val *v, int is_signed); + #if defined(__cplusplus) } #endif Index: lib/External/isl/isl_ast.c =================================================================== --- lib/External/isl/isl_ast.c +++ lib/External/isl/isl_ast.c @@ -10,6 +10,7 @@ #include #include +#include #undef BASE #define BASE ast_expr @@ -20,6 +21,7 @@ #define BASE ast_node #include +#include "isl_ast_private.h" isl_ctx *isl_ast_print_options_get_ctx( __isl_keep isl_ast_print_options *options) @@ -179,6 +181,10 @@ dup->u.op.args[i] = isl_ast_expr_copy(expr->u.op.args[i]); break; + case isl_ast_expr_bound_t: + dup = isl_ast_expr_bound(isl_ast_expr_copy(expr->u.bound.expr), + expr->u.bound.is_signed, expr->u.bound.size, + expr->u.bound.condition); case isl_ast_expr_error: dup = NULL; } @@ -225,6 +231,10 @@ isl_ast_expr_free(expr->u.op.args[i]); free(expr->u.op.args); break; + case isl_ast_expr_bound_t: + isl_ast_expr_free(expr->u.bound.expr); + isl_set_free(expr->u.bound.condition); + break; case isl_ast_expr_error: break; } @@ -243,6 +253,56 @@ return expr ? expr->type : isl_ast_expr_error; } +/* Return the number of bits required to represent 'expr' in two's complement + */ +unsigned int isl_ast_expr_get_bound_bits(__isl_keep isl_ast_expr *expr) +{ + if (!expr) + return isl_ast_op_error; + if (expr->type != isl_ast_expr_bound_t) + isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid, + "expression not a bound", return isl_ast_op_error); + return expr->u.bound.size; +} + +/* Return whether the value of 'expr' at runtime can be signed. + */ +isl_bool isl_ast_expr_get_bound_signed(__isl_keep isl_ast_expr *expr) +{ + if (!expr) + return isl_bool_error; + if (expr->type != isl_ast_expr_bound_t) + isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid, + "expression not a bound", return isl_ast_op_error); + return expr->u.bound.is_signed; +} + +/* Return the expression contained within the bounds of "expr". + */ +__isl_give isl_ast_expr* isl_ast_expr_get_bound_expr (__isl_keep isl_ast_expr *expr) +{ + + if (!expr) + return NULL; + if (expr->type != isl_ast_expr_bound_t) + isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid, + "expression not an int", return NULL); + return isl_ast_expr_copy(expr->u.bound.expr); +} + +/* Return the condition under which the bound "expr" is valid. + */ +__isl_give isl_set* isl_ast_expr_get_bound_condition (__isl_keep isl_ast_expr *expr) +{ + + if (!expr) + return NULL; + if (expr->type != isl_ast_expr_bound_t) + isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid, + "expression not an int", return NULL); + return isl_set_copy(expr->u.bound.condition); +} + /* Return the integer value represented by "expr". */ __isl_give isl_val *isl_ast_expr_get_val(__isl_keep isl_ast_expr *expr) @@ -423,6 +483,8 @@ __isl_give isl_ast_expr *isl_ast_expr_alloc_int_si(isl_ctx *ctx, int i) { isl_ast_expr *expr; + isl_bool is_neg; + int size; expr = isl_calloc_type(ctx, isl_ast_expr); if (!expr) @@ -436,6 +498,12 @@ if (!expr->u.v) return isl_ast_expr_free(expr); + if (isl_options_get_ast_build_compute_bounds(ctx)) { + is_neg = isl_val_is_neg(expr->u.v); + size = isl_val_size_in_bits(expr->u.v, is_neg); + expr = isl_ast_expr_bound(expr, is_neg, size, NULL); + } + return expr; } @@ -445,6 +513,8 @@ { isl_ctx *ctx; isl_ast_expr *expr; + isl_bool is_neg; + int size; if (!v) return NULL; @@ -463,6 +533,12 @@ expr->type = isl_ast_expr_int; expr->u.v = v; + if (isl_options_get_ast_build_compute_bounds(isl_val_get_ctx(v))) { + is_neg = isl_val_is_neg(expr->u.v); + size = isl_val_size_in_bits(expr->u.v, is_neg); + expr = isl_ast_expr_bound(expr, is_neg, size, NULL); + } + return expr; error: isl_val_free(v); @@ -517,6 +593,43 @@ return isl_ast_expr_alloc_unary(isl_ast_op_address_of, expr); } +/* Create an expression representing the bounds on "expr". + * + */ +__isl_give isl_ast_expr *isl_ast_expr_bound(__isl_take isl_ast_expr *expr, + isl_bool is_signed, unsigned int size, __isl_take isl_set *conditions) +{ + isl_ctx *ctx; + isl_ast_expr *result; + + if (!expr) + return NULL; + + if (expr->type == isl_ast_expr_bound_t) { + isl_die(isl_ast_expr_get_ctx(expr), isl_error_internal, + "Cannot take bound of bound", + return isl_ast_expr_free(expr)); + } + + ctx = isl_ast_expr_get_ctx(expr); + result = isl_calloc_type(ctx, isl_ast_expr); + if (!result) { + isl_ast_expr_free(result); + return NULL; + } + result->type = isl_ast_expr_bound_t; + + result->ctx = ctx; + isl_ctx_ref(ctx); + result->ref = 1; + result->u.bound.expr = expr; + result->u.bound.is_signed = is_signed; + result->u.bound.size = size; + result->u.bound.condition = conditions; + + return result; +} + /* Create an expression representing the binary operation "type" * applied to "expr1" and "expr2". */ @@ -1557,16 +1670,51 @@ return 0; } +/* Print a c-style cast operator containing the integer type of expr + */ +__isl_give isl_printer *printer_print_cast(__isl_take isl_printer *p, + __isl_keep isl_ast_expr *expr) +{ + if (isl_ast_expr_get_type(expr) != isl_ast_expr_bound_t) + return p; + + if (!isl_options_get_ast_build_print_computed_bounds( + isl_printer_get_ctx(p))) + return p; + + p = isl_printer_print_str(p, "("); + if (!isl_ast_expr_get_bound_signed(expr)) + p = isl_printer_print_str(p, "u"); + + p = isl_printer_print_str(p, "int"); + p = isl_printer_print_int(p, isl_ast_expr_get_bound_bits(expr)); + p = isl_printer_print_str(p, ")"); + + return p; +} + /* Print "expr" as a subexpression of an "op" operation in C format. * If "left" is set, then "expr" is the left-most operand. */ static __isl_give isl_printer *print_sub_expr_c(__isl_take isl_printer *p, - enum isl_ast_op_type op, __isl_keep isl_ast_expr *expr, int left) + enum isl_ast_op_type op, __isl_keep isl_ast_expr *expr, int left, + __isl_keep isl_ast_expr *parent) { int need_parens; need_parens = sub_expr_need_parens(op, expr, left); + if (isl_ast_expr_get_type(expr) == isl_ast_expr_bound_t) { + p = printer_print_cast(p, expr); + expr = expr->u.bound.expr; + if (isl_options_get_ast_build_print_computed_bounds( + isl_printer_get_ctx(p))) + need_parens = 1; + else + need_parens = sub_expr_need_parens(op, expr, left); + + } + if (need_parens) p = isl_printer_print_str(p, "("); p = print_ast_expr_c(p, expr); @@ -1810,8 +1958,9 @@ if (expr->u.op.n_arg == 1) { p = isl_printer_print_str(p, get_op_str_c(p, expr->u.op.op)); + p = printer_print_cast(p, expr); p = print_sub_expr_c(p, expr->u.op.op, - expr->u.op.args[0], 0); + expr->u.op.args[0], 0, expr); break; } if (expr->u.op.op == isl_ast_op_fdiv_q) { @@ -1842,13 +1991,15 @@ isl_die(isl_printer_get_ctx(p), isl_error_internal, "operation should have two arguments", return isl_printer_free(p)); - p = print_sub_expr_c(p, expr->u.op.op, expr->u.op.args[0], 1); + p = print_sub_expr_c(p, expr->u.op.op, expr->u.op.args[0], 1, + expr); if (expr->u.op.op != isl_ast_op_member) p = isl_printer_print_str(p, " "); p = isl_printer_print_str(p, get_op_str_c(p, expr->u.op.op)); if (expr->u.op.op != isl_ast_op_member) p = isl_printer_print_str(p, " "); - p = print_sub_expr_c(p, expr->u.op.op, expr->u.op.args[1], 0); + p = print_sub_expr_c(p, expr->u.op.op, expr->u.op.args[1], 0, + expr); break; case isl_ast_expr_id: p = isl_printer_print_str(p, isl_id_get_name(expr->u.id)); @@ -1856,6 +2007,17 @@ case isl_ast_expr_int: p = isl_printer_print_val(p, expr->u.v); break; + case isl_ast_expr_bound_t: + if (!isl_options_get_ast_build_print_computed_bounds( + isl_printer_get_ctx(p))) + p = print_ast_expr_c(p, expr->u.bound.expr); + else { + p = printer_print_cast(p, expr); + p = isl_printer_print_str(p, "("); + p = print_ast_expr_c(p, expr->u.bound.expr); + p = isl_printer_print_str(p, ")"); + } + break; case isl_ast_expr_error: break; } @@ -1931,6 +2093,27 @@ return p; } +isl_printer *print_ast_expr_size_isl(__isl_take isl_printer *p, + __isl_keep isl_ast_expr *expr) { + if (isl_ast_expr_get_type(expr) == isl_ast_expr_bound_t) { + p = isl_printer_yaml_next(p); + p = isl_printer_print_str(p, "size"); + p = isl_printer_yaml_next(p); + p = isl_printer_print_int(p, expr->u.bound.size); + p = isl_printer_yaml_next(p); + p = isl_printer_print_str(p, "is_signed"); + p = isl_printer_yaml_next(p); + p = isl_printer_print_int(p, expr->u.bound.is_signed); + if (expr->u.bound.condition) { + p = isl_printer_yaml_next(p); + p = isl_printer_print_str(p, "condition"); + p = isl_printer_yaml_next(p); + isl_printer_print_set(p, expr->u.bound.condition); + } + } + return p; +} + /* Print "expr" to "p" in isl format. * * In particular, print the isl_ast_expr as a YAML document. @@ -1958,6 +2141,7 @@ p = isl_printer_print_str(p, "op"); p = isl_printer_yaml_next(p); p = isl_printer_print_str(p, op_str[op]); + p = print_ast_expr_size_isl(p, expr); p = isl_printer_yaml_next(p); p = print_arguments(p, expr); break; @@ -1967,14 +2151,21 @@ id = isl_ast_expr_get_id(expr); p = isl_printer_print_id(p, id); isl_id_free(id); + p = print_ast_expr_size_isl(p, expr); break; case isl_ast_expr_int: p = isl_printer_print_str(p, "val"); p = isl_printer_yaml_next(p); v = isl_ast_expr_get_val(expr); p = isl_printer_print_val(p, v); + p = print_ast_expr_size_isl(p, expr); isl_val_free(v); break; + case isl_ast_expr_bound_t: + if (!isl_options_get_ast_build_print_computed_bounds( + isl_printer_get_ctx(p))) + p = print_ast_expr_size_isl(p, expr); + p = print_ast_expr_isl(p, expr->u.bound.expr); } p = isl_printer_yaml_end_mapping(p); @@ -2273,8 +2464,14 @@ const char *type; type = isl_options_get_ast_iterator_type(isl_printer_get_ctx(p)); + if (!node->u.f.degenerate) { - id = isl_ast_expr_get_id(node->u.f.iterator); + if (node->u.f.iterator->type == isl_ast_expr_bound_t) { + id = isl_ast_expr_get_id(node->u.f.iterator-> + u.bound.expr); + } else { + id = isl_ast_expr_get_id(node->u.f.iterator); + } name = isl_id_get_name(id); isl_id_free(id); p = isl_printer_start_line(p); Index: lib/External/isl/isl_ast_build.c =================================================================== --- lib/External/isl/isl_ast_build.c +++ lib/External/isl/isl_ast_build.c @@ -19,6 +19,7 @@ #include #include #include +#include /* Construct a map that isolates the current dimension. * @@ -43,6 +44,26 @@ return map; } +/* Initialize the local copy of the build-specific options + * from the associated isl_ctx. + */ +__isl_give isl_ast_build *isl_ast_build_init_options( + __isl_take isl_ast_build *build) +{ + isl_ctx *ctx; + + build = isl_ast_build_cow(build); + if (!build) + return NULL; + + ctx = isl_ast_build_get_ctx(build); + build->compute_bounds = isl_options_get_ast_build_compute_bounds(ctx); + build->approximate_bounds = isl_options_get_ast_build_approximate_computed_bounds(ctx); + build->maximum_size = isl_options_get_ast_build_maximum_native_type(ctx); + + return build; +} + /* Initialize the information derived during the AST generation to default * values for a schedule domain in "space". * @@ -145,6 +166,10 @@ space = isl_set_get_space(set); if (isl_space_is_params(space)) space = isl_space_set_from_params(space); + build->compute_bounds = isl_options_get_ast_build_compute_bounds(ctx); + build->approximate_bounds = isl_options_get_ast_build_approximate_computed_bounds(ctx); + build->maximum_size = isl_options_get_ast_build_maximum_native_type(ctx); + return isl_ast_build_init_derived(build, space); error: @@ -188,6 +213,9 @@ return NULL; dup->ref = 1; + dup->compute_bounds = build->compute_bounds; + dup->approximate_bounds = build->approximate_bounds; + dup->maximum_size = build->maximum_size; dup->outer_pos = build->outer_pos; dup->depth = build->depth; dup->iterators = isl_id_list_copy(build->iterators); @@ -292,6 +320,15 @@ return isl_ast_build_dup(build); } +static isl_stat free_cache_entry(void **p, void *user) +{ + struct isl_aff *expr = *p; + + isl_aff_free(expr); + + return isl_stat_ok; +} + __isl_null isl_ast_build *isl_ast_build_free( __isl_take isl_ast_build *build) { @@ -301,6 +338,11 @@ if (--build->ref > 0) return NULL; + if (build->cache) { + isl_hash_table_foreach(isl_ast_build_get_ctx(build), build->cache, &free_cache_entry, NULL); + isl_hash_table_free(isl_ast_build_get_ctx(build), build->cache); + } + isl_id_list_free(build->iterators); isl_set_free(build->domain); isl_set_free(build->generated); @@ -2563,4 +2605,4 @@ build->single_valued = sv; return build; -} +} \ No newline at end of file Index: lib/External/isl/isl_ast_build_expr.h =================================================================== --- lib/External/isl/isl_ast_build_expr.h +++ lib/External/isl/isl_ast_build_expr.h @@ -16,6 +16,10 @@ __isl_give isl_ast_expr *isl_ast_expr_set_op_arg(__isl_take isl_ast_expr *expr, int pos, __isl_take isl_ast_expr *arg); +__isl_give isl_ast_expr *isl_ast_build_set_size( + __isl_keep isl_ast_build *build, __isl_take isl_ast_expr *expr, + __isl_keep isl_aff *aff); + __isl_give isl_ast_node *isl_ast_build_call_from_executed( __isl_keep isl_ast_build *build, __isl_take isl_map *executed); Index: lib/External/isl/isl_ast_build_expr.c =================================================================== --- lib/External/isl/isl_ast_build_expr.c +++ lib/External/isl/isl_ast_build_expr.c @@ -16,6 +16,515 @@ #include #include #include +#include + +static int ast_expr_is_zero(__isl_keep isl_ast_expr *expr); + +/* Compute the minimum of the integer affine expression "obj" over the points + * in build->domain and put the result in *opt. + */ +__isl_give isl_val *isl_ast_build_min(__isl_keep isl_ast_build *build, + __isl_keep isl_aff *obj) +{ + if (!build) + return NULL; + + return isl_set_min_val(build->domain, obj); +} + +/* Compute the maximum of the integer affine expression "obj" over the points + * in build->domain and put the result in *opt. + */ +__isl_give isl_val *isl_ast_build_max(__isl_keep isl_ast_build *build, + __isl_keep isl_aff *obj) +{ + if (!build) + return NULL; + + return isl_set_max_val(build->domain, obj); +} + +/* Approximate the size of the binary operation "expr" by looking at the type + * of it's arguments. This only works if the size of the arguments is already + * know. + */ +__isl_give isl_ast_expr *isl_ast_bin_op_set_size_max( + __isl_take isl_ast_expr *expr, __isl_keep isl_ast_build *build) +{ + int flag, num_args; + int base_offset = 0; + int add = 0; + isl_bool is_signed; + size_t bits; + + if (!build->compute_bounds) + return expr; + + switch (expr->u.op.op) { + case isl_ast_op_min: + flag = 0; + break; + case isl_ast_op_sub: + case isl_ast_op_max: + flag = 1; + break; + case isl_ast_op_select: + flag = 1; + base_offset = 1; + break; + case isl_ast_op_add: + flag = 1; + add = 1; + break; + default: + isl_die(isl_ast_expr_get_ctx(expr), isl_error_internal, + "invalid expression type", goto error); + } + + num_args = expr->u.op.n_arg; + for (int i = base_offset; i < num_args; i++) { + if (expr->u.op.args[i]->type != isl_ast_expr_bound_t) { + return expr; + } + } + + is_signed = expr->u.op.args[base_offset]->u.bound.is_signed; + bits = expr->u.op.args[base_offset]->u.bound.size; + if (flag == 1) { + // Result is maximum type + if (expr->u.op.args[base_offset + 1]->u.bound.size > bits) { + bits = expr->u.op.args[base_offset + 1]->u.bound.size; + if (is_signed && !expr->u.op.args[base_offset + 1]-> + u.bound.is_signed) + bits++; + else + is_signed = expr->u.op.args[base_offset + 1]-> + u.bound.is_signed; + } else if (!is_signed && expr->u.op.args[base_offset + 1]-> + u.bound.is_signed) { + is_signed = expr->u.op.args[base_offset + 1]-> + u.bound.is_signed; + if (bits == expr->u.op.args[base_offset + 1]-> + u.bound.size) + bits++; + } + } else { + // Result is minimum type + if (expr->u.op.args[base_offset + 1]->u.bound.size < bits || + (expr->u.op.args[base_offset + 1]->u.bound.size == bits + && !expr->u.op.args[base_offset + 1]-> + u.bound.is_signed)) { + bits = expr->u.op.args[base_offset + 1]->u.bound.size; + is_signed = expr->u.op.args[base_offset + 1]-> + u.bound.is_signed; + } + } + + if (add) + bits++; + + return isl_ast_expr_bound(expr, is_signed, bits, NULL); + +error: + return isl_ast_expr_free(expr); +} + +__isl_give isl_ast_expr *isl_ast_bin_op_set_size_mul( + __isl_take isl_ast_expr *expr, __isl_keep isl_ast_build *build) +{ + int flag; + int add = 0; + isl_bool is_signed; + size_t bits; + + if (expr->u.op.args[0]->type == isl_ast_expr_bound_t && + expr->u.op.args[1]->type == isl_ast_expr_bound_t) { + is_signed = expr->u.op.args[0]->u.bound.is_signed; + bits = expr->u.op.args[0]->u.bound.size + + expr->u.op.args[1]->u.bound.size; + if (is_signed != expr->u.op.args[1]->u.bound.is_signed) { + bits++; + is_signed = isl_bool_true; + } + + expr = isl_ast_expr_bound(expr, is_signed, bits, NULL); + } + return expr; +} + +__isl_give isl_ast_expr *isl_ast_bin_op_set_size_div( + __isl_take isl_ast_expr *expr, __isl_keep isl_ast_build *build) +{ + int flag; + int add = 0; + isl_bool is_signed; + size_t bits; + + if (expr->u.op.args[0]->type == isl_ast_expr_bound_t && + expr->u.op.args[1]->type == isl_ast_expr_bound_t) { + is_signed = expr->u.op.args[1]->u.bound.is_signed; + bits = expr->u.op.args[1]->u.bound.size; + if (expr->u.op.args[0]->u.bound.is_signed || is_signed) { + bits++; + is_signed = isl_bool_true; + } + + expr = isl_ast_expr_bound(expr, is_signed, bits, NULL); + } + return expr; +} + +__isl_give isl_ast_expr *isl_ast_bin_op_set_size_minus( + __isl_take isl_ast_expr *expr, __isl_keep isl_ast_build *build) +{ + int flag; + int add = 0; + isl_bool is_signed; + size_t bits; + + if (expr->u.op.args[0]->type == isl_ast_expr_bound_t) { + is_signed = expr->u.op.args[0]->u.bound.is_signed; + bits = expr->u.op.args[0]->u.bound.size; + + if (!is_signed) { + is_signed = isl_bool_true; + bits++; + } else { + bits++; + } + + expr = isl_ast_expr_bound(expr, is_signed, bits, NULL); + } + return expr; +} + +/* Approximates the size of some binary operators by looking at the size + * of their arguments. If the arguments of the operation are not already + * bounded, the function will recurse if possible. + */ +__isl_give isl_ast_expr *isl_ast_bin_op_set_size(__isl_take isl_ast_expr *expr, + __isl_keep isl_ast_build *build) +{ + if (!build->compute_bounds) + return expr; + if (expr->type != isl_ast_expr_op) + isl_die(isl_ast_expr_get_ctx(expr), isl_error_internal, + "invalid expression type - not an isl_ast_expr_op", + goto error); + + for (int i = 0; i < expr->u.op.n_arg; i++) { + if (expr->u.op.args[i]->type != isl_ast_expr_bound_t) { + if (expr->u.op.args[i]->type == isl_ast_expr_op) { + expr->u.op.args[i] = isl_ast_bin_op_set_size( + expr->u.op.args[i], build); + } + } + } + switch (expr->u.op.op) { + case isl_ast_op_min: + case isl_ast_op_max: + case isl_ast_op_select: + case isl_ast_op_add: + case isl_ast_op_sub: + return isl_ast_bin_op_set_size_max(expr, build); + case isl_ast_op_mul: + return isl_ast_bin_op_set_size_mul(expr, build); + case isl_ast_op_div: + case isl_ast_op_fdiv_q: + case isl_ast_op_pdiv_r: + case isl_ast_op_zdiv_r: + case isl_ast_op_pdiv_q: + return isl_ast_bin_op_set_size_div(expr, build); + case isl_ast_op_minus: + return isl_ast_bin_op_set_size_minus(expr, build); + default: + return expr; + } + +error: + return isl_ast_expr_free(expr); +} + +static int same_aff(const void *entry, const void *val) +{ + if (!entry || !val) + return 0; + return isl_aff_plain_is_equal((isl_aff*)entry, (isl_aff*)val); +} + +/* Compute the minimum type needed to hold 'expr' using 'aff'. This function + * gives an exact result but imposes a performance penalty as it invokes the + * ILP solver twice. + */ +__isl_give isl_ast_expr *isl_ast_build_set_size_with_solver( + __isl_keep isl_ast_build *build, __isl_take isl_ast_expr *expr, + __isl_keep isl_aff *aff) +{ + isl_val *res = NULL; + int upper_bits, lower_bits; + uint64_t bound_val; + isl_bool is_lower_signed; + isl_local_space *ls; + isl_aff *upper_val, *lower_val; + isl_set *problems = NULL, *problems_parameters; + isl_basic_set *bigger; + isl_set *smaller; + + if (!build || !expr) + return NULL; + + if (!build->compute_bounds) + return expr; + + res = isl_ast_build_min(build, aff); + + if (!isl_val_is_int(res)) { + isl_val_free(res); + return expr; + } + + is_lower_signed = isl_val_is_neg(res); + lower_bits = isl_val_size_in_bits(res, is_lower_signed); + isl_val_free(res); + + res = isl_ast_build_max(build, aff); + + if (!isl_val_is_int(res)) { + isl_val_free(res); + return expr; + } + + upper_bits = isl_val_size_in_bits(res, is_lower_signed); + isl_val_free(res); + + if (upper_bits > lower_bits) + lower_bits = upper_bits; + + if (build->maximum_size && lower_bits > build->maximum_size) { + isl_val *upper, *lower; + if (is_lower_signed) { + bound_val = (1UL << (build->maximum_size-1))-1; + upper = isl_val_int_from_si( + isl_ast_build_get_ctx(build), + bound_val); + bound_val = -(1UL << (build->maximum_size-1)); + lower = isl_val_int_from_si( + isl_ast_build_get_ctx(build), + bound_val); + } else { + bound_val = ~(1UL<< (build->maximum_size)); + upper = isl_val_int_from_ui( + isl_ast_build_get_ctx(build), + bound_val); + lower = isl_val_int_from_ui( + isl_ast_build_get_ctx(build), 0); + } + ls = isl_aff_get_domain_local_space(aff); + upper_val = isl_aff_val_on_domain(isl_local_space_copy(ls), + upper); + lower_val = isl_aff_val_on_domain(ls, lower); + + bigger = isl_aff_ge_basic_set(isl_aff_copy(aff), upper_val); + smaller = isl_pw_aff_lt_set(isl_pw_aff_from_aff( + isl_aff_copy(aff)), + isl_pw_aff_from_aff(lower_val)); + problems = isl_set_union(isl_set_from_basic_set(bigger), + smaller); + + problems_parameters = isl_set_params(isl_set_copy(problems)); + if (isl_set_plain_is_universe(problems_parameters)) { + problems = isl_set_intersect(problems, + isl_set_copy(build->generated)); + } + isl_set_free(problems_parameters); + + problems = isl_set_params(problems); + problems = isl_set_gist(problems, + isl_set_params(isl_set_copy(build->domain))); + lower_bits = build->maximum_size; + } + + expr = isl_ast_expr_bound(expr, is_lower_signed, lower_bits, problems); + + return expr; +} + +static int bare_var_cached = 0; +static int expr_approximated_try = 0; +static int expr_approximated_success = 0; +static int expr_total = 0; + +/* Try to approximate the binary operation expr (also represented by aff) + * by looking at it's arguments. + */ +__isl_give isl_ast_expr *isl_ast_build_try_approximate_size( + __isl_keep isl_ast_build *build, __isl_take isl_ast_expr *expr, + __isl_keep isl_aff *aff) +{ + int all_bound = 1; + isl_ast_expr *result; + + for (int i = 0; i < expr->u.op.n_arg; i++) + if (expr->u.op.args[i]->type != isl_ast_expr_bound_t) + all_bound = 0; + + if (all_bound) { + expr = isl_ast_bin_op_set_size(expr, build); + expr_approximated_try++; + if (expr->type == isl_ast_expr_bound_t && + expr->u.bound.size > build->maximum_size) { + result = isl_ast_build_set_size_with_solver(build, + isl_ast_expr_get_bound_expr(expr), aff); + isl_ast_expr_free(expr); + return result; + } + expr_approximated_success++; + return expr; + } + return isl_ast_build_set_size_with_solver(build, expr, aff); +} + +/* If the ast_build_compute_bounds is set, then compute bounds on "expr" + * based on the possible value of "aff" over build->domain. + */ +__isl_give isl_ast_expr *isl_ast_build_set_size( + __isl_keep isl_ast_build *build, __isl_take isl_ast_expr *expr, + __isl_keep isl_aff *aff) +{ + expr_total++; + + if (build->approximate_bounds) { + if (!build->cache) { + build->cache = isl_hash_table_alloc( + isl_ast_build_get_ctx(build), 16); + isl_hash_table_init(isl_ast_build_get_ctx(build), + build->cache, 16); + } + + if (expr->type == isl_ast_expr_id) { + uint32_t hash = isl_id_get_hash(expr->u.id); + struct isl_hash_table_entry *entry = + isl_hash_table_find( + isl_ast_build_get_ctx(build), + build->cache, hash, same_aff, aff, 1); + if (!entry->data) { + expr = isl_ast_build_set_size_with_solver(build, + expr, aff); + entry->data = isl_aff_copy(aff); + } else { + bare_var_cached++; + } + return expr; + } else if (expr->type == isl_ast_expr_op) { + switch (expr->u.op.op) { + case isl_ast_op_min: + case isl_ast_op_max: + case isl_ast_op_select: + case isl_ast_op_add: + case isl_ast_op_sub: + case isl_ast_op_mul: + case isl_ast_op_div: + case isl_ast_op_fdiv_q: + case isl_ast_op_pdiv_r: + case isl_ast_op_zdiv_r: + case isl_ast_op_pdiv_q: + case isl_ast_op_minus: + // (Default: Fall through to solver) + return isl_ast_build_try_approximate_size( + build, expr, aff); + } + } + } + + return isl_ast_build_set_size_with_solver(build, expr, aff); +} + +/* Data structure that holds an isl_ast_expr and its corresponding + * isl_aff. + */ +struct isl_ast_expr_constructor { + isl_ast_expr *expr; + isl_aff *aff; +}; +typedef struct isl_ast_expr_constructor isl_ast_expr_constructor; + +__isl_give isl_ast_expr_constructor *ast_expr_constructor_from_aff( + __isl_take isl_aff *aff, __isl_keep isl_ast_build *build); + +static void *isl_ast_expr_constructor_free( + __isl_take isl_ast_expr_constructor *cons) +{ + if (!cons) + return NULL; + + isl_ast_expr_free(cons->expr); + isl_aff_free(cons->aff); + free(cons); + return NULL; +} + +static __isl_give isl_ast_expr *isl_ast_expr_constructor_get_ast_expr( + __isl_take isl_ast_expr_constructor *cons) +{ + if (!cons) + return NULL; + + return isl_ast_expr_copy(cons->expr); +} + +static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_alloc( + __isl_take isl_local_space *ls) +{ + isl_ast_expr_constructor *cons; + isl_ctx *ctx; + + if (!ls) + return NULL; + + ctx = isl_local_space_get_ctx(ls); + cons = isl_alloc_type(ctx, isl_ast_expr_constructor); + if (!cons) + goto error; + + cons->expr = isl_ast_expr_alloc_int_si(ctx, 0); + cons->aff = isl_aff_zero_on_domain(ls); + + if (!cons->expr || !cons->aff) + return isl_ast_expr_constructor_free(cons); + + return cons; +error: + isl_local_space_free(ls); + return NULL; +} + +static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_val( + __isl_take isl_local_space *ls, __isl_take isl_val *v, + __isl_keep isl_ast_build *build) +{ + isl_ast_expr_constructor *cons; + isl_ctx *ctx; + + if (!ls) + return NULL; + + ctx = isl_local_space_get_ctx(ls); + cons = isl_alloc_type(ctx, isl_ast_expr_constructor); + if (!cons) + goto error; + + cons->aff = isl_aff_zero_on_domain(ls); + cons->aff = isl_aff_add_constant_val(cons->aff, isl_val_copy(v)); + cons->expr = isl_ast_expr_from_val(v); + + if (!cons->expr || !cons->aff) + return isl_ast_expr_constructor_free(cons); + + return cons; +error: + isl_local_space_free(ls); + return NULL; +} /* Compute the "opposite" of the (numerator of the) argument of a div * with denominator "d". @@ -144,6 +653,188 @@ return isl_aff_add_constant_val(aff, shift); } +/* Set the size of cons->expr based on range of values attained + * by cons->aff over build->domain. This is used to handle edge-cases + * where the constructor does not actually contain a composite expression. + */ +static void isl_ast_expr_constructor_set_size( + __isl_keep isl_ast_expr_constructor *cons, + __isl_keep isl_ast_build *build) +{ + if (cons->expr->type != isl_ast_expr_bound_t) { + cons->expr = isl_ast_build_set_size(build, cons->expr, + cons->aff); + } +} + +/* Add cons2->expr to cons1->expr and compute the size of the result. + * The result is simplified in terms of build->domain. + */ +static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_add( + __isl_take isl_ast_expr_constructor *cons1, + __isl_take isl_ast_expr_constructor *cons2, + __isl_keep isl_ast_build *build) +{ + if (!cons1 || !cons2) + goto error; + + if (isl_aff_plain_is_zero(cons1->aff)) { + isl_ast_expr_constructor_free(cons1); + return cons2; + } + + if (isl_aff_plain_is_zero(cons2->aff)) { + isl_ast_expr_constructor_free(cons2); + return cons1; + } + + cons1->expr = isl_ast_expr_add(cons1->expr, + isl_ast_expr_copy(cons2->expr)); + cons1->aff = isl_aff_add(cons1->aff, isl_aff_copy(cons2->aff)); + isl_ast_expr_constructor_set_size(cons1, build); + + isl_ast_expr_constructor_free(cons2); + + if (!cons1->expr || !cons1->aff) + return isl_ast_expr_constructor_free(cons1); + return cons1; +error: + isl_ast_expr_constructor_free(cons2); + return isl_ast_expr_constructor_free(cons1); +} + +/* Subtract cons2->expr from cons1->expr and compute the size of the result. + * The result is simplified in terms of build->domain. + * + * If cons2->expr is zero, we simply return cons1->expr. + * If cons1->expr is zero, we return + * + * (isl_ast_op_minus, cons2->expr) + * + * Otherwise, we return + * + * (isl_ast_op_sub, cons1->expr, cons2->expr) + */ +static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_sub( + __isl_take isl_ast_expr_constructor *cons1, + __isl_take isl_ast_expr_constructor *cons2, + __isl_keep isl_ast_build *build) +{ + if (!cons1 || !cons2) + goto error; + + if (isl_aff_plain_is_zero(cons2->aff)) { + isl_ast_expr_constructor_free(cons2); + return cons1; + } + + if (isl_aff_plain_is_zero(cons1->aff)) { + cons2->aff = isl_aff_neg(cons2->aff); + cons2->expr = isl_ast_expr_neg(cons2->expr); + isl_ast_expr_constructor_free(cons1); + isl_ast_expr_constructor_set_size(cons2, build); + if (!cons2->expr || !cons2->aff) + return isl_ast_expr_constructor_free(cons2); + return cons2; + } + + cons1->expr = isl_ast_expr_sub(cons1->expr, + isl_ast_expr_copy(cons2->expr)); + cons1->aff = isl_aff_sub(cons1->aff, isl_aff_copy(cons2->aff)); + isl_ast_expr_constructor_set_size(cons1, build); + + isl_ast_expr_constructor_free(cons2); + + if (!cons1->expr || !cons1->aff) + return isl_ast_expr_constructor_free(cons1); + return cons1; +error: + isl_ast_expr_constructor_free(cons2); + return isl_ast_expr_constructor_free(cons1); +} + +/* Return an isl_ast_expr_constructor that represents + * + * v * (aff mod d) + * + * v is assumed to be non-negative. + * The result is simplified in terms of build->domain. + */ +static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_mod( + __isl_take isl_val *v, __isl_keep isl_aff *aff, + __isl_take isl_val *d, + __isl_keep isl_ast_build *build) +{ + isl_ctx *ctx; + isl_ast_expr_constructor *cons; + isl_ast_expr *c; + + if (!aff) + goto out; + + ctx = isl_aff_get_ctx(aff); + cons = isl_alloc_type(ctx, isl_ast_expr_constructor); + if (!cons) + goto out; + + cons->aff = isl_aff_copy(aff); + cons->expr = isl_ast_expr_from_aff(isl_aff_copy(aff), build); + + c = isl_ast_expr_from_val(isl_val_copy(d)); + cons->expr = isl_ast_expr_alloc_binary(isl_ast_op_pdiv_r, + cons->expr, c); + cons->aff = isl_aff_mod_val(cons->aff, d); + isl_ast_expr_constructor_set_size(cons, build); + + if (!isl_val_is_one(v)) { + c = isl_ast_expr_from_val(isl_val_copy(v)); + cons->expr = isl_ast_expr_mul(c, cons->expr); + cons->aff = isl_aff_scale_val(cons->aff, isl_val_copy(v)); + isl_ast_expr_constructor_set_size(cons, build); + } + + if (!cons->expr || !cons->aff) { + isl_val_free(v); + return isl_ast_expr_constructor_free(cons); + } + + + isl_val_free(v); + return cons; + +out: + isl_val_free(v); + isl_val_free(d); + return NULL; +} + +/* Devide cons2->expr by cons1->expr and compute the size of the result. + * The result is simplified in terms of build->domain. + */ +static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_div( + __isl_take isl_ast_expr_constructor *cons1, + __isl_take isl_ast_expr_constructor *cons2, + __isl_keep isl_ast_build *build) +{ + if (!cons1 || !cons2) + goto error; + + cons1->expr = isl_ast_expr_div(cons1->expr, + isl_ast_expr_copy(cons2->expr)); + cons1->aff = isl_aff_div(cons1->aff, isl_aff_copy(cons2->aff)); + cons1->aff = isl_aff_floor(cons1->aff); + isl_ast_expr_constructor_set_size(cons1, build); + + isl_ast_expr_constructor_free(cons2); + + if (!cons1->expr || !cons1->aff) + return isl_ast_expr_constructor_free(cons1); + return cons1; +error: + isl_ast_expr_constructor_free(cons2); + return isl_ast_expr_constructor_free(cons1); +} + /* Create an isl_ast_expr evaluating the div at position "pos" in "ls". * The result is simplified in terms of data->build->domain. * This function may change (the sign of) data->v. @@ -252,12 +943,20 @@ return isl_ast_expr_from_id(id); } +/* Add an expression for "v" to cons->expr. + */ +static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_add_int( + __isl_take isl_ast_expr_constructor *cons, __isl_take isl_val *v, + __isl_keep isl_ast_build *build); + /* Does "expr" represent the zero integer? */ static int ast_expr_is_zero(__isl_keep isl_ast_expr *expr) { if (!expr) return -1; + if (expr->type == isl_ast_expr_bound_t) + expr = expr->u.bound.expr; if (expr->type != isl_ast_expr_int) return 0; return isl_val_is_zero(expr->u.v); @@ -323,36 +1022,6 @@ return NULL; } -/* Return an isl_ast_expr that represents - * - * v * (aff mod d) - * - * v is assumed to be non-negative. - * The result is simplified in terms of build->domain. - */ -static __isl_give isl_ast_expr *isl_ast_expr_mod(__isl_keep isl_val *v, - __isl_keep isl_aff *aff, __isl_keep isl_val *d, - __isl_keep isl_ast_build *build) -{ - isl_ast_expr *expr; - isl_ast_expr *c; - - if (!aff) - return NULL; - - expr = isl_ast_expr_from_aff(isl_aff_copy(aff), build); - - c = isl_ast_expr_from_val(isl_val_copy(d)); - expr = isl_ast_expr_alloc_binary(isl_ast_op_pdiv_r, expr, c); - - if (!isl_val_is_one(v)) { - c = isl_ast_expr_from_val(isl_val_copy(v)); - expr = isl_ast_expr_mul(c, expr); - } - - return expr; -} - /* Create an isl_ast_expr that scales "expr" by "v". * * If v is 1, we simply return expr. @@ -364,33 +1033,74 @@ * * (isl_ast_op_mul, expr(v), expr) */ -static __isl_give isl_ast_expr *scale(__isl_take isl_ast_expr *expr, - __isl_take isl_val *v) +static __isl_give isl_ast_expr_constructor *scale( + __isl_take isl_ast_expr_constructor *cons, + __isl_take isl_val *v, __isl_keep isl_ast_build *build) { isl_ast_expr *c; - if (!expr || !v) + if (!cons || !v) goto error; if (isl_val_is_one(v)) { isl_val_free(v); - return expr; + return cons; } if (isl_val_is_negone(v)) { isl_val_free(v); - expr = isl_ast_expr_neg(expr); + cons->expr = isl_ast_expr_neg(cons->expr); + cons->aff = isl_aff_neg(cons->aff); } else { - c = isl_ast_expr_from_val(v); - expr = isl_ast_expr_mul(c, expr); + c = isl_ast_expr_from_val(isl_val_copy(v)); + cons->expr = isl_ast_expr_mul(c, cons->expr); + cons->aff = isl_aff_scale_val(cons->aff, v); } - return expr; + isl_ast_expr_constructor_set_size(cons, build); + + return cons; error: isl_val_free(v); - isl_ast_expr_free(expr); + isl_ast_expr_constructor_free(cons); return NULL; } +/* Create an isl_ast_expr evaluating "v" times the specified dimension of "ls". + * The result is simplified in terms of build->domain. + * + * Let e be the expression for the specified dimension. + * If v is 1, we simply return e. + * If v is -1, we return + * + * (isl_ast_op_minus, e) + * + * Otherwise, we return + * + * (isl_ast_op_mul, expr(v), e) + */ +static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_term( + __isl_keep isl_local_space *ls, enum isl_dim_type type, int pos, + struct isl_ast_add_term_data *data) +{ + isl_ctx *ctx; + isl_ast_expr_constructor *cons; + if (!ls) + return NULL; + + ctx = isl_local_space_get_ctx(ls); + cons = isl_alloc_type(ctx, isl_ast_expr_constructor); + if (!cons) + return NULL; + + cons->expr = var(data, ls, type, pos); + cons->aff = isl_aff_var_on_domain(isl_local_space_copy(ls), type, pos); + isl_ast_expr_constructor_set_size(cons, data->build); + + if (!cons->expr || !cons->aff) + return isl_ast_expr_constructor_free(cons); + return cons; +} + /* Add an expression for "*v" times the specified dimension of "ls" * to expr. * If the dimension is an integer division, then this function @@ -414,27 +1124,29 @@ * (isl_ast_op_add, expr, e) * */ -static __isl_give isl_ast_expr *isl_ast_expr_add_term( - __isl_take isl_ast_expr *expr, +static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_add_term( + __isl_take isl_ast_expr_constructor *cons, __isl_keep isl_local_space *ls, enum isl_dim_type type, int pos, __isl_take isl_val *v, struct isl_ast_add_term_data *data) { - isl_ast_expr *term; + isl_ast_expr_constructor *term; - if (!expr) + if (!cons) return NULL; data->v = v; - term = var(data, ls, type, pos); + term = isl_ast_expr_constructor_term(ls, type, pos, data); v = data->v; - if (isl_val_is_neg(v) && !ast_expr_is_zero(expr)) { + if (isl_val_is_neg(v) && !ast_expr_is_zero(cons->expr)) { v = isl_val_neg(v); - term = scale(term, v); - return ast_expr_sub(expr, term); + term = scale(term, v, data->build); + cons = isl_ast_expr_constructor_sub(cons, term, data->build); + return cons; } else { - term = scale(term, v); - return ast_expr_add(expr, term); + term = scale(term, v, data->build); + cons = isl_ast_expr_constructor_add(cons, term, data->build); + return cons; } } @@ -467,6 +1179,45 @@ return NULL; } +/* Add an expression for "v" to expr. + */ +static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_add_int( + __isl_take isl_ast_expr_constructor *cons, __isl_take isl_val *v, + __isl_keep isl_ast_build *build) +{ + isl_local_space *ls; + isl_ast_expr_constructor *cons_int; + + if (!cons || !v) + goto error; + + if (isl_val_is_zero(v)) { + isl_val_free(v); + return cons; + } + + ls = isl_aff_get_domain_local_space(cons->aff); + + if (isl_val_is_neg(v) && !ast_expr_is_zero(cons->expr)) { + v = isl_val_neg(v); + cons_int = isl_ast_expr_constructor_val(ls, v, build); + if (!cons_int) + goto error; + cons = isl_ast_expr_constructor_sub(cons, cons_int, build); + } else { + cons_int = isl_ast_expr_constructor_val(ls, v, build); + if (!cons_int) + goto error; + cons = isl_ast_expr_constructor_add(cons, cons_int, build); + } + + return cons; +error: + isl_ast_expr_constructor_free(cons); + isl_val_free(v); + return NULL; +} + /* Internal data structure used inside extract_modulos. * * If any modulo expressions are detected in "aff", then the @@ -493,8 +1244,8 @@ isl_ast_build *build; isl_aff *aff; - isl_ast_expr *pos; - isl_ast_expr *neg; + isl_ast_expr_constructor *pos; + isl_ast_expr_constructor *neg; isl_aff *add; @@ -522,22 +1273,26 @@ * to data->neg or data->pos depending on the sign of -f. */ static int extract_term_and_mod(struct isl_extract_mod_data *data, - __isl_take isl_aff *term, __isl_take isl_aff *arg) + __isl_take isl_aff *term, __isl_take isl_aff *arg, + __isl_keep isl_ast_build *build) { - isl_ast_expr *expr; + isl_ast_expr_constructor *cons; int s; data->v = isl_val_div(data->v, isl_val_copy(data->d)); s = isl_val_sgn(data->v); data->v = isl_val_abs(data->v); - expr = isl_ast_expr_mod(data->v, arg, data->d, data->build); + cons = isl_ast_expr_constructor_mod(isl_val_copy(data->v), arg, + isl_val_copy(data->d), data->build); isl_aff_free(arg); if (s > 0) - data->neg = ast_expr_add(data->neg, expr); + data->neg = isl_ast_expr_constructor_add(data->neg, cons, + build); else - data->pos = ast_expr_add(data->pos, expr); + data->pos = isl_ast_expr_constructor_add(data->pos, cons, + build); data->aff = isl_aff_set_coefficient_si(data->aff, - isl_dim_div, data->i, 0); + isl_dim_div, data->i, 0); if (s < 0) data->v = isl_val_neg(data->v); term = isl_aff_scale_val(term, isl_val_copy(data->v)); @@ -570,10 +1325,11 @@ * * to data->neg or data->pos depending on the sign of -f. */ -static int extract_mod(struct isl_extract_mod_data *data) +static int extract_mod(struct isl_extract_mod_data *data, + __isl_keep isl_ast_build *build) { return extract_term_and_mod(data, isl_aff_copy(data->div), - isl_aff_copy(data->div)); + isl_aff_copy(data->div), build); } /* Given that data->v * div_i in data->aff is of the form @@ -594,7 +1350,8 @@ * * This function may modify data->div. */ -static int extract_nonneg_mod(struct isl_extract_mod_data *data) +static int extract_nonneg_mod(struct isl_extract_mod_data *data, + __isl_take isl_ast_build *build) { int mod; @@ -602,7 +1359,7 @@ if (mod < 0) goto error; if (mod) - return extract_mod(data); + return extract_mod(data, build); data->div = oppose_div_arg(data->div, isl_val_copy(data->d)); mod = isl_ast_build_aff_is_nonneg(data->build, data->div); @@ -610,7 +1367,7 @@ goto error; if (mod) { data->v = isl_val_neg(data->v); - return extract_mod(data); + return extract_mod(data, build); } return 0; @@ -817,7 +1574,8 @@ * Alternatively, we could first compute the dual of the domain * and plug in the constraints on the coefficients. */ -static int try_extract_mod(struct isl_extract_mod_data *data) +static int try_extract_mod(struct isl_extract_mod_data *data, + __isl_keep isl_ast_build *build) { isl_basic_set *hull; isl_val *v1, *v2; @@ -829,7 +1587,7 @@ n = isl_aff_dim(data->div, isl_dim_div); if (isl_aff_involves_dims(data->div, isl_dim_div, 0, n)) - return extract_nonneg_mod(data); + return extract_nonneg_mod(data, build); hull = isl_set_simple_hull(isl_set_copy(data->build->domain)); hull = isl_basic_set_remove_divs(hull); @@ -843,7 +1601,7 @@ isl_aff_free(data->nonneg); if (r < 0) goto error; - return extract_nonneg_mod(data); + return extract_nonneg_mod(data, build); } v1 = isl_aff_get_constant_val(data->div); @@ -871,7 +1629,7 @@ } return extract_term_and_mod(data, - isl_aff_copy(data->div), data->nonneg); + isl_aff_copy(data->div), data->nonneg, build); error: data->aff = isl_aff_free(data->aff); return -1; @@ -908,13 +1666,14 @@ * * and still extract a modulo. */ -static int extract_modulo(struct isl_extract_mod_data *data) +static int extract_modulo(struct isl_extract_mod_data *data, + __isl_keep isl_ast_build *build) { data->div = isl_aff_get_div(data->aff, data->i); data->d = isl_aff_get_denominator_val(data->div); if (isl_val_is_divisible_by(data->v, data->d)) { data->div = isl_aff_scale_val(data->div, isl_val_copy(data->d)); - if (try_extract_mod(data) < 0) + if (try_extract_mod(data, build) < 0) data->aff = isl_aff_free(data->aff); } isl_aff_free(data->div); @@ -946,10 +1705,11 @@ * If f < 0, we add ((-f) * (a mod m)) to *pos. */ static __isl_give isl_aff *extract_modulos(__isl_take isl_aff *aff, - __isl_keep isl_ast_expr **pos, __isl_keep isl_ast_expr **neg, + __isl_keep isl_ast_expr_constructor **cons_pos, + __isl_keep isl_ast_expr_constructor **cons_neg, __isl_keep isl_ast_build *build) { - struct isl_extract_mod_data data = { build, aff, *pos, *neg }; + struct isl_extract_mod_data data = { build, aff, *cons_pos, *cons_neg }; isl_ctx *ctx; int n; @@ -971,7 +1731,7 @@ isl_val_free(data.v); continue; } - if (extract_modulo(&data) < 0) + if (extract_modulo(&data, build) < 0) data.aff = isl_aff_free(data.aff); isl_val_free(data.v); if (!data.aff) @@ -981,8 +1741,8 @@ if (data.add) data.aff = isl_aff_add(data.aff, data.add); - *pos = data.pos; - *neg = data.neg; + *cons_pos = data.pos; + *cons_neg = data.neg; return data.aff; } @@ -995,12 +1755,12 @@ * Return aff1 and add (aff2 / d) to *expr. */ static __isl_give isl_aff *extract_rational(__isl_take isl_aff *aff, - __isl_keep isl_ast_expr **expr, __isl_keep isl_ast_build *build) + __isl_keep isl_ast_expr_constructor **cons, __isl_keep isl_ast_build *build) { int i, j, n; isl_aff *rat = NULL; isl_local_space *ls = NULL; - isl_ast_expr *rat_expr; + isl_ast_expr_constructor *rat_cons; isl_val *v, *d; enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div }; enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div }; @@ -1049,14 +1809,13 @@ rat = isl_aff_add(rat, rat_0); } - isl_local_space_free(ls); - aff = isl_aff_sub(aff, isl_aff_copy(rat)); aff = isl_aff_scale_down_val(aff, isl_val_copy(d)); - rat_expr = isl_ast_expr_from_aff(rat, build); - rat_expr = isl_ast_expr_div(rat_expr, isl_ast_expr_from_val(d)); - *expr = ast_expr_add(*expr, rat_expr); + rat_cons = ast_expr_constructor_from_aff(rat, build); + rat_cons = isl_ast_expr_constructor_div(rat_cons, + isl_ast_expr_constructor_val(ls, d, build), build); + *cons = isl_ast_expr_constructor_add(*cons, rat_cons, build); return aff; error: @@ -1075,14 +1834,13 @@ * Finally, if the affine expression has a non-trivial denominator, * we divide the resulting isl_ast_expr by this denominator. */ -__isl_give isl_ast_expr *isl_ast_expr_from_aff(__isl_take isl_aff *aff, - __isl_keep isl_ast_build *build) +__isl_give isl_ast_expr_constructor *ast_expr_constructor_from_aff( + __isl_take isl_aff *aff, __isl_keep isl_ast_build *build) { int i, j; int n; isl_val *v; - isl_ctx *ctx = isl_aff_get_ctx(aff); - isl_ast_expr *expr, *expr_neg; + isl_ast_expr_constructor *cons, *cons_neg; enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div }; enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div }; isl_local_space *ls; @@ -1091,15 +1849,14 @@ if (!aff) return NULL; - expr = isl_ast_expr_alloc_int_si(ctx, 0); - expr_neg = isl_ast_expr_alloc_int_si(ctx, 0); - - aff = extract_rational(aff, &expr, build); + ls = isl_aff_get_domain_local_space(aff); - aff = extract_modulos(aff, &expr, &expr_neg, build); - expr = ast_expr_sub(expr, expr_neg); + cons = isl_ast_expr_constructor_alloc(isl_local_space_copy(ls)); + cons_neg = isl_ast_expr_constructor_alloc(isl_local_space_copy(ls)); + aff = extract_rational(aff, &cons, build); + aff = extract_modulos(aff, &cons, &cons_neg, build); - ls = isl_aff_get_domain_local_space(aff); + cons = isl_ast_expr_constructor_sub(cons, cons_neg, build); data.build = build; data.cst = isl_aff_get_constant_val(aff); @@ -1108,20 +1865,43 @@ for (j = 0; j < n; ++j) { v = isl_aff_get_coefficient_val(aff, t[i], j); if (!v) - expr = isl_ast_expr_free(expr); + cons = isl_ast_expr_constructor_free(cons); if (isl_val_is_zero(v)) { isl_val_free(v); continue; } - expr = isl_ast_expr_add_term(expr, + cons = isl_ast_expr_constructor_add_term(cons, ls, l[i], j, v, &data); } } - expr = isl_ast_expr_add_int(expr, data.cst); + v = data.cst; + cons = isl_ast_expr_constructor_add_int(cons, v, build); + if (!cons) + isl_die(isl_val_get_ctx(v), isl_error_internal, + "couldn't create constructor", goto out); +out: isl_local_space_free(ls); isl_aff_free(aff); + return cons; +} + +/* Construct an isl_ast_expr that evaluates the affine expression "aff", + * The result is simplified in terms of build->domain. + */ +__isl_give isl_ast_expr *isl_ast_expr_from_aff(__isl_take isl_aff *aff, + __isl_keep isl_ast_build *build) +{ + isl_ast_expr_constructor *cons; + isl_ast_expr *expr; + + cons = ast_expr_constructor_from_aff(aff, build); + if (cons) + isl_ast_expr_constructor_set_size(cons, build); + expr = isl_ast_expr_constructor_get_ast_expr(cons); + isl_ast_expr_constructor_free(cons); + return expr; } @@ -1129,7 +1909,8 @@ * with sign equal to "sign". * The result is simplified in terms of data->build->domain. */ -static __isl_give isl_ast_expr *add_signed_terms(__isl_take isl_ast_expr *expr, +static __isl_give isl_ast_expr_constructor *add_signed_terms( + __isl_take isl_ast_expr_constructor *cons, __isl_keep isl_aff *aff, int sign, struct isl_ast_add_term_data *data) { int i, j; @@ -1149,14 +1930,14 @@ continue; } v = isl_val_abs(v); - expr = isl_ast_expr_add_term(expr, + cons = isl_ast_expr_constructor_add_term(cons, ls, l[i], j, v, data); } } isl_local_space_free(ls); - return expr; + return cons; } /* Should the constant term "v" be considered positive? @@ -1277,6 +2058,7 @@ isl_ctx *ctx; isl_val *c; isl_ast_expr *expr, *cst; + isl_aff *aff_in; if (!aff) return NULL; @@ -1290,12 +2072,16 @@ aff = isl_aff_neg(aff); cst = isl_ast_expr_from_val(isl_val_abs(c)); + aff_in = isl_aff_copy(aff); expr = isl_ast_expr_from_aff(aff, build); expr = isl_ast_expr_alloc_binary(isl_ast_op_zdiv_r, expr, cst); cst = isl_ast_expr_alloc_int_si(ctx, 0); expr = isl_ast_expr_alloc_binary(isl_ast_op_eq, expr, cst); + expr = isl_ast_build_set_size(build,expr,aff_in); + isl_aff_free(aff_in); + return expr; } @@ -1340,10 +2126,12 @@ { int i, n; isl_ctx *ctx; - isl_ast_expr *expr_pos; - isl_ast_expr *expr_neg; + isl_ast_expr *expr_pos, *expr_pos_t; + isl_ast_expr *expr_neg, *expr_neg_t; isl_ast_expr *expr; - isl_aff *aff; + isl_ast_expr_constructor *cons_pos, *cons_neg; + isl_local_space *ls; + isl_aff *aff, *aff_val; int eq; enum isl_ast_op_type type; struct isl_ast_add_term_data data; @@ -1366,28 +2154,50 @@ return extract_stride_constraint(aff, i, build); } - ctx = isl_aff_get_ctx(aff); - expr_pos = isl_ast_expr_alloc_int_si(ctx, 0); - expr_neg = isl_ast_expr_alloc_int_si(ctx, 0); - - aff = extract_modulos(aff, &expr_pos, &expr_neg, build); + ls = isl_aff_get_domain_local_space(aff); + cons_pos = isl_ast_expr_constructor_alloc(isl_local_space_copy(ls)); + cons_neg = isl_ast_expr_constructor_alloc(ls); + aff = extract_modulos(aff, &cons_pos, &cons_neg, build); data.build = build; data.cst = isl_aff_get_constant_val(aff); - expr_pos = add_signed_terms(expr_pos, aff, 1, &data); + + cons_pos = add_signed_terms(cons_pos, aff, 1, &data); + expr_pos = isl_ast_expr_constructor_get_ast_expr(cons_pos); + data.cst = isl_val_neg(data.cst); - expr_neg = add_signed_terms(expr_neg, aff, -1, &data); + cons_neg = add_signed_terms(cons_neg, aff, -1, &data); + expr_neg = isl_ast_expr_constructor_get_ast_expr(cons_neg); data.cst = isl_val_neg(data.cst); if (constant_is_considered_positive(data.cst, expr_pos, expr_neg)) { - expr_pos = isl_ast_expr_add_int(expr_pos, data.cst); + cons_pos = isl_ast_expr_constructor_add_int(cons_pos, data.cst, + build); + isl_ast_expr_free(expr_pos); + expr_pos = isl_ast_expr_constructor_get_ast_expr(cons_pos); } else { data.cst = isl_val_neg(data.cst); - expr_neg = isl_ast_expr_add_int(expr_neg, data.cst); + cons_neg = isl_ast_expr_constructor_add_int(cons_neg, data.cst, + build); + isl_ast_expr_free(expr_neg); + expr_neg = isl_ast_expr_constructor_get_ast_expr(cons_neg); } - if (isl_ast_expr_get_type(expr_pos) == isl_ast_expr_int && - isl_ast_expr_get_type(expr_neg) != isl_ast_expr_int) { + isl_ast_expr_constructor_free(cons_pos); + isl_ast_expr_constructor_free(cons_neg); + + if (isl_ast_expr_get_type(expr_pos) == isl_ast_expr_bound_t) + expr_pos_t = expr_pos->u.bound.expr; + else + expr_pos_t = expr_pos; + + if (isl_ast_expr_get_type(expr_neg) == isl_ast_expr_bound_t) + expr_neg_t = expr_neg->u.bound.expr; + else + expr_neg_t = expr_neg; + + if (isl_ast_expr_get_type(expr_pos_t) == isl_ast_expr_int && + isl_ast_expr_get_type(expr_neg_t) != isl_ast_expr_int) { type = eq ? isl_ast_op_eq : isl_ast_op_le; expr = isl_ast_expr_alloc_binary(type, expr_neg, expr_pos); } else { @@ -1794,6 +2604,7 @@ expr->u.op.args[i] = expr_i; } + expr = isl_ast_bin_op_set_size(expr, build); isl_aff_list_free(list); return expr; error: @@ -1942,6 +2753,8 @@ if (add_last_piece(data, data->n - 1, next) < 0) return isl_ast_expr_free(res); + if (res->type == isl_ast_expr_op) + res = isl_ast_bin_op_set_size(res, data->build); return res; } Index: lib/External/isl/isl_ast_build_private.h =================================================================== --- lib/External/isl/isl_ast_build_private.h +++ lib/External/isl/isl_ast_build_private.h @@ -12,6 +12,9 @@ * generated. That is, it (mostly) contains information about outer * loops that can be used to simplify inner loops. * + * "compute_bounds", "approximate_bounds" and maximum_size are local copies + * of the corresponding option. + * * "domain" represents constraints on the internal schedule domain, * corresponding to the context of the AST generation and the constraints * implied by the loops that have already been generated. @@ -145,6 +148,10 @@ struct isl_ast_build { int ref; + int compute_bounds; + int approximate_bounds; + int maximum_size; + int outer_pos; int depth; @@ -197,8 +204,12 @@ int n; enum isl_ast_loop_type *loop_type; isl_set *isolated; + + struct isl_hash_table *cache; }; +__isl_give isl_ast_build *isl_ast_build_init_options( + __isl_take isl_ast_build *context); __isl_give isl_ast_build *isl_ast_build_clear_local_info( __isl_take isl_ast_build *build); __isl_give isl_ast_build *isl_ast_build_increase_depth( Index: lib/External/isl/isl_ast_codegen.c =================================================================== --- lib/External/isl/isl_ast_codegen.c +++ lib/External/isl/isl_ast_codegen.c @@ -658,6 +658,8 @@ __isl_keep isl_pw_aff_list *list, __isl_keep isl_ast_build *build) { int i, n; + isl_bool is_signed = isl_bool_false; + size_t bits = 0; isl_ctx *ctx; isl_ast_expr *expr; @@ -688,9 +690,24 @@ if (!expr_i) goto error; expr->u.op.args[i] = expr_i; + if (build->compute_bounds) { + if (expr->u.op.args[i]->type != isl_ast_expr_bound_t) + isl_die(isl_ast_build_get_ctx(build), + isl_error_internal, + "Unbound expression found", continue); + if (expr->u.op.args[i]->u.bound.is_signed && !is_signed) { + is_signed = 1; + bits++; + } + if (expr->u.op.args[i]->u.bound.size > bits) + bits = expr->u.op.args[i]->u.bound.size; + } } isl_pw_aff_list_free(list); + if (build->compute_bounds && bits > 0) { + expr = isl_ast_expr_bound(expr, is_signed, bits, NULL); + } return expr; error: isl_pw_aff_list_free(list); @@ -971,6 +988,51 @@ return list; } +/* + * Set the bounds of node->u.f.iterator by calculating max(size(bound), + * size(bound + add_offset)). + */ +static void isl_ast_node_for_set_iterator_type( + __isl_keep isl_ast_node *node, __isl_take isl_aff *bound, + __isl_take isl_local_space *ls, __isl_take isl_val *add_offset, + __isl_take isl_ast_build *build) +{ + isl_aff *constant, *pos_bound; + size_t bits; + isl_bool is_signed; + isl_ast_expr *org_expr = node->u.f.iterator; + + constant = isl_aff_val_on_domain(ls, add_offset); + pos_bound = isl_aff_add(isl_aff_copy(bound), constant); + node->u.f.iterator = isl_ast_build_set_size(build, + isl_ast_expr_copy(org_expr), + pos_bound); + + if (node->u.f.iterator->type != isl_ast_expr_bound_t) { + isl_die(isl_ast_build_get_ctx(build), isl_error_internal, + "Unbound loop iterator found", goto out); + } + bits = node->u.f.iterator->u.bound.size; + is_signed = node->u.f.iterator->u.bound.is_signed; + isl_ast_expr_free(node->u.f.iterator); + + node->u.f.iterator = isl_ast_build_set_size(build, org_expr, bound); + if (node->u.f.iterator->type != isl_ast_expr_bound_t) { + isl_die(isl_ast_build_get_ctx(build), isl_error_internal, + "Unbound loop iterator found", goto out); + } + + if (node->u.f.iterator->u.bound.size < bits) { + node->u.f.iterator->u.bound.size = bits; + node->u.f.iterator->u.bound.is_signed = is_signed; + } + +out: + isl_aff_free(pos_bound); + isl_aff_free(bound); + isl_ast_build_free(build); +} + /* Set the condition part of the for node graft->node in case * the upper bound is represented as a list of piecewise affine expressions. * @@ -1034,24 +1096,64 @@ return graft; } +__isl_give isl_ast_node_for_priv *isl_ast_node_alloc_for_priv( + __isl_keep isl_ctx *ctx) +{ + return isl_calloc_type(ctx, isl_ast_node_for_priv); +} + +__isl_null isl_ast_node_for_priv *isl_ast_node_for_priv_free( + __isl_take isl_ast_node_for_priv *priv) +{ + isl_ast_build_free(priv->inner_build); + isl_aff_free(priv->iterator_expr); + free(priv); + + return NULL; +} + /* Construct an isl_ast_expr for the increment (i.e., stride) of * the current dimension. */ -static __isl_give isl_ast_expr *for_inc(__isl_keep isl_ast_build *build) +static __isl_give isl_ast_expr *for_inc(__isl_keep isl_ast_build *build, + __isl_keep isl_ast_node *node) { int depth; isl_val *v; isl_ctx *ctx; + isl_local_space *ls; + isl_aff *iterator_expr; + isl_ast_build *inner_build; if (!build) return NULL; ctx = isl_ast_build_get_ctx(build); depth = isl_ast_build_get_depth(build); - if (!isl_ast_build_has_stride(build, depth)) + if (build->compute_bounds) { + iterator_expr = isl_aff_copy(node->u.f.priv->iterator_expr); + ls = isl_aff_get_domain_local_space(iterator_expr); + inner_build = isl_ast_build_copy(node->u.f.priv->inner_build); + isl_ast_node_for_priv_free(node->u.f.priv); + } + + if (!isl_ast_build_has_stride(build, depth)) { + if (build->compute_bounds) { + v = isl_val_int_from_ui(ctx, 1); + isl_ast_node_for_set_iterator_type(node, iterator_expr, + ls, v, inner_build); + } + return isl_ast_expr_alloc_int_si(ctx, 1); + } v = isl_ast_build_get_stride(build, depth); + + if (build->compute_bounds) { + isl_ast_node_for_set_iterator_type(node, iterator_expr, ls, + isl_val_copy(v), inner_build); + } + return isl_ast_expr_from_val(v); } @@ -1097,6 +1199,7 @@ __isl_keep isl_set *upper_set, __isl_keep isl_ast_build *build) { isl_ast_node *node; + isl_ast_expr *incr; if (!graft) return NULL; @@ -1105,7 +1208,7 @@ node = graft->node; node->u.f.init = reduce_list(isl_ast_op_max, lower, build); - node->u.f.inc = for_inc(build); + node->u.f.inc = for_inc(build, node); if (!node->u.f.init || !node->u.f.inc) graft = isl_ast_graft_free(graft); @@ -1320,11 +1423,16 @@ * Mark the for node degenerate if "degenerate" is set. */ static __isl_give isl_ast_node *create_for(__isl_keep isl_ast_build *build, + __isl_keep isl_basic_set* bounds, + __isl_keep isl_ast_build *sub_build, int degenerate) { int depth; isl_id *id; isl_ast_node *node; + isl_local_space *ls; + isl_aff *iterator_expr; + isl_val *v; if (!build) return NULL; @@ -1332,6 +1440,24 @@ depth = isl_ast_build_get_depth(build); id = isl_ast_build_get_iterator_id(build, depth); node = isl_ast_node_alloc_for(id); + + if (build->compute_bounds) { + ls = isl_basic_set_get_local_space(bounds); + iterator_expr = isl_aff_var_on_domain(ls, isl_dim_out, depth); + + node->u.f.priv = isl_ast_node_alloc_for_priv( + isl_aff_get_ctx(iterator_expr)); + node->u.f.priv->inner_build = isl_ast_build_copy(sub_build); + node->u.f.priv->iterator_expr = iterator_expr; + if (degenerate) { + v = isl_val_int_from_ui(isl_aff_get_ctx(iterator_expr), 1); + ls = isl_basic_set_get_local_space(bounds); + isl_ast_node_for_set_iterator_type(node, isl_aff_copy(iterator_expr), + ls, v, isl_ast_build_copy(node->u.f.priv->inner_build)); + isl_ast_node_for_priv_free(node->u.f.priv); + } + } + if (degenerate) node = isl_ast_node_for_mark_degenerate(node); @@ -1486,7 +1612,7 @@ if (eliminated) executed = plug_in_values(executed, sub_build); else - node = create_for(build, degenerate); + node = create_for(build, bounds, sub_build, degenerate); body_build = isl_ast_build_copy(sub_build); body_build = isl_ast_build_increase_depth(body_build); @@ -5038,6 +5164,7 @@ build = isl_ast_build_copy(build); build = isl_ast_build_set_single_valued(build, 0); + build = isl_ast_build_init_options(build); schedule = isl_union_map_coalesce(schedule); schedule = isl_union_map_remove_redundancies(schedule); executed = isl_union_map_reverse(schedule); Index: lib/External/isl/isl_ast_private.h =================================================================== --- lib/External/isl/isl_ast_private.h +++ lib/External/isl/isl_ast_private.h @@ -7,6 +7,7 @@ #include #include #include +#include /* An expression is either an integer, an identifier or an operation * with zero or more arguments. @@ -15,7 +16,6 @@ int ref; isl_ctx *ctx; - enum isl_ast_expr_type type; union { @@ -26,6 +26,12 @@ unsigned n_arg; isl_ast_expr **args; } op; + struct { + unsigned int size; + isl_bool is_signed; + isl_ast_expr *expr; + isl_set *condition; + } bound; } u; }; @@ -45,6 +51,12 @@ #include +struct isl_ast_node_for_priv { + isl_aff *iterator_expr; + isl_ast_build *inner_build; +}; +typedef struct isl_ast_node_for_priv isl_ast_node_for_priv; + /* A node is either a block, an if, a for, a user node or a mark node. * "else_node" is NULL if the if node does not have an else branch. * "cond" and "inc" are NULL for degenerate for nodes. @@ -72,6 +84,7 @@ isl_ast_expr *cond; isl_ast_expr *inc; isl_ast_node *body; + isl_ast_node_for_priv *priv; } f; struct { isl_ast_expr *expr; Index: lib/External/isl/isl_gmp.c =================================================================== --- lib/External/isl/isl_gmp.c +++ lib/External/isl/isl_gmp.c @@ -22,3 +22,20 @@ isl_hash_byte(hash, *data); return hash; } + +size_t isl_gmp_size_in_bits(mpz_t v, int is_signed) +{ + size_t bits; + + if (!is_signed) + return mpz_sizeinbase(v, 2); + + if (mpz_sgn(v) >= 0) + return 1 + mpz_sizeinbase(v, 2); + + mpz_add_ui(v, v, 1); + bits = 1 + mpz_sizeinbase(v, 2); + mpz_sub_ui(v, v, 1); + + return bits; +} Index: lib/External/isl/isl_imath.c =================================================================== --- lib/External/isl/isl_imath.c +++ lib/External/isl/isl_imath.c @@ -54,6 +54,26 @@ mp_int_clear(&temp); } +size_t isl_imath_size_in_bits(mp_int val, int sign) { + mp_result result; + mpz_t tmp; + + if ((result = mp_int_count_bits(val)) < 0) + isl_die(NULL, isl_error_invalid, "Coudln't get size", return 1); + + if (MP_SIGN(val)!=0) { + mp_int_init(&tmp); + mp_int_neg(val, &tmp); + if (mp_int_is_pow2(&tmp)<0) + result++; + mp_int_clear(&tmp); + } else if (MP_SIGN(val)==0 && sign==1) { + result++; + } + + return result; +} + /* Compute the division of lhs by a rhs of type unsigned long, rounding towards * positive infinity (Ceil). */ Index: lib/External/isl/isl_int_gmp.h =================================================================== --- lib/External/isl/isl_int_gmp.h +++ lib/External/isl/isl_int_gmp.h @@ -68,6 +68,10 @@ #define isl_int_abs_ge(i,j) (mpz_cmpabs(i,j) >= 0) #define isl_int_is_divisible_by(i,j) mpz_divisible_p(i,j) + +size_t isl_gmp_size_in_bits(mpz_t v, int is_signed); +#define isl_int_size_in_bits(v,s) isl_gmp_size_in_bits(v,s) + uint32_t isl_gmp_hash(mpz_t v, uint32_t hash); #define isl_int_hash(v,h) isl_gmp_hash(v,h) Index: lib/External/isl/isl_int_imath.h =================================================================== --- lib/External/isl/isl_int_imath.h +++ lib/External/isl/isl_int_imath.h @@ -74,4 +74,5 @@ typedef void (*isl_int_print_mp_free_t)(void *, size_t); #define isl_int_free_str(s) free(s) +#define isl_int_size_in_bits(v,s) isl_imath_size_in_bits(v,s) #endif /* ISL_INT_IMATH_H */ Index: lib/External/isl/isl_int_sioimath.h =================================================================== --- lib/External/isl/isl_int_sioimath.h +++ lib/External/isl/isl_int_sioimath.h @@ -1251,4 +1251,6 @@ #define isl_int_free_str(s) free(s) #define isl_int_print(out, i, width) isl_sioimath_print(out, *(i), width) +#define isl_int_size_in_bits(v,s) isl_sioimath_size_in_bits(v,s) + #endif /* ISL_INT_SIOIMATH_H */ Index: lib/External/isl/isl_int_sioimath.c =================================================================== --- lib/External/isl/isl_int_sioimath.c +++ lib/External/isl/isl_int_sioimath.c @@ -78,6 +78,8 @@ extern void isl_sioimath_submul_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs, unsigned long rhs); +extern size_t isl_imath_size_in_bits(mp_int val, int sign); + /* Implements the Euclidean algorithm to compute the greatest common divisor of * two values in small representation. */ @@ -221,3 +223,24 @@ { isl_sioimath_print(stdout, arg, 0); } + +size_t isl_sioimath_size_in_bits(isl_sioimath_ptr val, int sign) { + int32_t small; + size_t size = 1; + + if (isl_sioimath_decode_small(*val, &small)) { + if (small >= 0) { + while ((small=(small>>1))!=0) + size++; + if (sign) + size++; + } else { + while ((small=(small>>1))!=-1) + size++; + size++; + } + return size; + } else { + return isl_imath_size_in_bits(*val, sign); + } +} \ No newline at end of file Index: lib/External/isl/isl_options.c =================================================================== --- lib/External/isl/isl_options.c +++ lib/External/isl/isl_options.c @@ -193,6 +193,17 @@ "ast-build-atomic-upper-bound", 1, "generate atomic upper bounds") ISL_ARG_BOOL(struct isl_options, ast_build_prefer_pdiv, 0, "ast-build-prefer-pdiv", 1, "prefer pdiv operation over fdiv") +ISL_ARG_BOOL(struct isl_options, ast_build_compute_bounds, 0, + "ast-build-compute-bounds", 0, "compute bounds on isl_ast_expr objects") +ISL_ARG_BOOL(struct isl_options, ast_build_print_computed_bounds, 0, + "ast-build-print-computed-bounds", 1, + "print computed bounds on isl_ast_expr objects") +ISL_ARG_BOOL(struct isl_options, ast_build_approximate_computed_bounds, 0, + "ast-build-approximate-computed-bounds", + 0, "approximate computed bounds on isl_ast_expr objects") +ISL_ARG_INT(struct isl_options, ast_build_maximum_native_type, 0, 0, + "ast-build-maximum-native-type", 0, + "try to keep computed bounds within this type (in bits)") ISL_ARG_BOOL(struct isl_options, ast_build_detect_min_max, 0, "ast-build-detect-min-max", 0, "detect min/max expressions") ISL_ARG_BOOL(struct isl_options, ast_build_exploit_nested_bounds, 0, @@ -326,6 +337,22 @@ ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, ast_build_prefer_pdiv) +ISL_CTX_SET_INT_DEF(isl_options, struct isl_options, isl_options_args, + ast_build_maximum_native_type) +ISL_CTX_GET_INT_DEF(isl_options, struct isl_options, isl_options_args, + ast_build_maximum_native_type) +ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, + ast_build_print_computed_bounds) +ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, + ast_build_print_computed_bounds) +ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, + ast_build_compute_bounds) +ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, + ast_build_compute_bounds) +ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, + ast_build_approximate_computed_bounds) +ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, + ast_build_approximate_computed_bounds) ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, ast_build_detect_min_max) ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, Index: lib/External/isl/isl_options_private.h =================================================================== --- lib/External/isl/isl_options_private.h +++ lib/External/isl/isl_options_private.h @@ -58,6 +58,10 @@ int ast_build_atomic_upper_bound; int ast_build_prefer_pdiv; + int ast_build_compute_bounds; + int ast_build_print_computed_bounds; + int ast_build_approximate_computed_bounds; + int ast_build_maximum_native_type; int ast_build_detect_min_max; int ast_build_exploit_nested_bounds; int ast_build_group_coscheduled; Index: lib/External/isl/isl_test.c =================================================================== --- lib/External/isl/isl_test.c +++ lib/External/isl/isl_test.c @@ -665,6 +665,47 @@ return 0; } +struct { + const char *val; + int sgn; + int size; +} val_size_in_bits_tests[] = { + { "0", 0, 1 }, + { "1", 0, 1 }, + { "2", 0, 2 }, + { "3", 0, 2 }, + { "15", 0, 4 }, + { "16", 0, 5 }, + { "340282366920938463463374607431768211455", 0, 128 }, + { "340282366920938463463374607431768211456", 0, 129 }, + { "0", 1, 2 }, + { "1", 1, 2 }, + { "2", 1, 3 }, + { "3", 1, 3 }, + { "340282366920938463463374607431768211455", 1, 129 }, + { "340282366920938463463374607431768211456", 1, 130 }, +}; + +/* Perform some basic tests of the isl_val_size_in_bits function + */ +static int test_size_in_bits_val(isl_ctx *ctx) +{ + int i; + isl_val *v; + int size; + + for (i = 0; i < ARRAY_SIZE(val_size_in_bits_tests); ++i) { + v = isl_val_read_from_str(ctx, val_size_in_bits_tests[i].val); + size = isl_val_size_in_bits(v, val_size_in_bits_tests[i].sgn); + isl_val_free(v); + if (size != val_size_in_bits_tests[i].size) + isl_die(ctx, isl_error_unknown, + "unexpected result", return -1); + } + + return 0; +} + /* Perform some basic tests on isl_val objects. */ static int test_val(isl_ctx *ctx) @@ -673,6 +714,8 @@ return -1; if (test_bin_val(ctx) < 0) return -1; + if (test_size_in_bits_val(ctx) < 0) + return -1; return 0; } Index: lib/External/isl/isl_val.c =================================================================== --- lib/External/isl/isl_val.c +++ lib/External/isl/isl_val.c @@ -1691,3 +1691,15 @@ { return isl_multi_val_fn_val(mv, &isl_val_mod, v); } + +int isl_val_size_in_bits(__isl_keep isl_val *v, int is_signed) +{ + if (!v) + return 0; + + if (!isl_val_is_int(v)) + isl_die(isl_val_get_ctx(v), isl_error_invalid, + "expecting integral value", return 0); + + return isl_int_size_in_bits(v->n, is_signed); +} Index: test/Isl/Ast/simple-run-time-condition.ll =================================================================== --- test/Isl/Ast/simple-run-time-condition.ll +++ test/Isl/Ast/simple-run-time-condition.ll @@ -20,7 +20,7 @@ ; for the delinearization is simplified such that conditions that would not ; cause any code to be executed are not generated. -; 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 >= 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)) && -(o <= -4611686018427387905 || o >= 4611686018427387903)) ; CHECK: if (o <= 0) { ; CHECK: for (int c0 = 0; c0 < n; c0 += 1)