Index: include/polly/CodeGen/IslAst.h =================================================================== --- include/polly/CodeGen/IslAst.h +++ include/polly/CodeGen/IslAst.h @@ -78,6 +78,12 @@ IslAst(Scop &Scop); void init(const Dependences &D); + isl_ast_expr *extractPreconditionFromAST(isl_ast_node *Node, + isl_ast_expr *cond, + isl_ast_build *Build); + isl_ast_expr *extractPreconditionFromAST(isl_ast_expr *Expr, + isl_ast_expr *cond, + isl_ast_build *Build); }; class IslAstInfo { Index: include/polly/CodeGen/IslExprBuilder.h =================================================================== --- include/polly/CodeGen/IslExprBuilder.h +++ include/polly/CodeGen/IslExprBuilder.h @@ -184,6 +184,8 @@ /// @return The llvm::Value* containing the result of the computation. llvm::Value *createAccessAddress(__isl_take isl_ast_expr *Expr); + void injectBound(isl_ast_expr *Bound); + private: Scop &S; @@ -221,6 +223,7 @@ llvm::Value *createOpBooleanConditional(__isl_take isl_ast_expr *Expr); llvm::Value *createId(__isl_take isl_ast_expr *Expr); llvm::Value *createInt(__isl_take isl_ast_expr *Expr); + llvm::Value *createBound(__isl_take isl_ast_expr *Expr); llvm::Value *createOpAddressOf(__isl_take isl_ast_expr *Expr); /// Create a binary operation @p Opc and track overflows if requested. @@ -264,6 +267,9 @@ /// @return A value that represents the result of the multiplication. llvm::Value *createMul(llvm::Value *LHS, llvm::Value *RHS, const llvm::Twine &Name = ""); + +protected: + isl_ast_expr *CurrentBound = nullptr; }; } // namespace polly Index: lib/CodeGen/IslAst.cpp =================================================================== --- lib/CodeGen/IslAst.cpp +++ lib/CodeGen/IslAst.cpp @@ -37,11 +37,13 @@ #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" #include "isl/set.h" #include "isl/union_map.h" +#include #include @@ -78,6 +80,10 @@ cl::init(false), cl::ZeroOrMore, 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::ZeroOrMore, cl::cat(PollyCategory)); namespace polly { /// Temporary information used when building the ast. struct AstBuildUserInfo { @@ -422,6 +428,9 @@ isl_ctx *Ctx = S.getIslCtx(); isl_options_set_ast_build_atomic_upper_bound(Ctx, true); isl_options_set_ast_build_detect_min_max(Ctx, true); + if (ComputeBounds) { + isl_options_set_ast_build_compute_bounds(Ctx, true); + } isl_ast_build *Build; AstBuildUserInfo BuildInfo; @@ -451,10 +460,98 @@ RunCondition = buildRunCondition(S, Build); Root = isl_ast_build_node_from_schedule(Build, S.getScheduleTree()); + RunCondition = + extractPreconditionFromAST(isl_ast_node_copy(Root), RunCondition, Build); isl_ast_build_free(Build); } +isl_ast_expr *IslAst::extractPreconditionFromAST(isl_ast_node *Node, + isl_ast_expr *cond, + isl_ast_build *Build) { + switch (isl_ast_node_get_type(Node)) { + case isl_ast_node_mark: + cond = extractPreconditionFromAST(isl_ast_node_mark_get_node(Node), cond, + Build); + isl_ast_node_free(Node); + break; + case isl_ast_node_for: + cond = extractPreconditionFromAST(isl_ast_node_for_get_init(Node), cond, + Build); + cond = + extractPreconditionFromAST(isl_ast_node_for_get_inc(Node), cond, Build); + cond = extractPreconditionFromAST(isl_ast_node_for_get_iterator(Node), cond, + Build); + cond = extractPreconditionFromAST(isl_ast_node_for_get_body(Node), cond, + Build); + isl_ast_node_free(Node); + break; + case isl_ast_node_if: + cond = + extractPreconditionFromAST(isl_ast_node_if_get_cond(Node), cond, Build); + cond = + extractPreconditionFromAST(isl_ast_node_if_get_then(Node), cond, Build); + cond = + extractPreconditionFromAST(isl_ast_node_if_get_else(Node), cond, Build); + isl_ast_node_free(Node); + break; + case isl_ast_node_user: + cond = extractPreconditionFromAST(isl_ast_node_user_get_expr(Node), cond, + Build); + 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, Build); + } + isl_ast_node_list_free(List); + isl_ast_node_free(Node); + break; + } + return cond; +} + +isl_ast_expr *IslAst::extractPreconditionFromAST(isl_ast_expr *Expr, + isl_ast_expr *cond, + isl_ast_build *Build) { + 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, + Build); + } + 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) { + cond = isl_ast_expr_and( + cond, isl_ast_build_expr_from_set(Build, OtherCondition)); + } + + cond = extractPreconditionFromAST(isl_ast_expr_get_bound_expr(Expr), cond, + Build); + + 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 @@ -17,10 +17,16 @@ #include "polly/Support/ScopHelper.h" #include "llvm/Support/Debug.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include using namespace llvm; using namespace polly; +static cl::opt + UseBounds("polly-ast-use-bounds", + cl::desc("Use computed bounds to determine types"), + cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory)); + /// Different overflow tracking modes. enum OverflowTrackingChoice { OT_NEVER, ///< Never tack potential overflows. @@ -713,10 +719,31 @@ } 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. + // XXX: Support bound computation disabled use case + if (1) { + if (CurrentBound == NULL) { + // Bail out with verbose error during dev: + std::cerr << "BEGIN EXPR" << std::endl; + 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); + std::cerr << std::endl << "END EXPR" << std::endl; + llvm_unreachable("Unbound expression!"); + } else { + 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 this exact for annotations and only use this + // for code generation on specific request + if (size < 64) + size = 64; + CurrentBound = nullptr; + return IntegerType::get(Builder.getContext(), size); + } + } return IntegerType::get(Builder.getContext(), 64); } @@ -754,7 +781,30 @@ 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"); + + auto 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_ast_expr *Bound) { + assert(CurrentBound == nullptr && "Cannot inject bound while previous " + "bound is not " + "consumed"); + + CurrentBound = Bound; +} Index: lib/CodeGen/IslNodeBuilder.cpp =================================================================== --- lib/CodeGen/IslNodeBuilder.cpp +++ lib/CodeGen/IslNodeBuilder.cpp @@ -82,11 +82,23 @@ 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); + } + + // TODO: XXX: Why is this here? This shouldn't do anything, is this a bug? 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"); @@ -105,6 +117,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"); @@ -468,7 +485,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; @@ -491,14 +508,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 + // desccending, but we're not using the visitor. In the non-compute case, + // we can simply use getType(Iterator), but in the compute case, 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()); @@ -577,7 +618,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; @@ -596,7 +637,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); @@ -609,7 +656,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. In the non-compute case, + // we can simply use getType(Iterator), but in the compute case, 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()); @@ -1193,7 +1257,14 @@ return nullptr; } - auto *Build = isl_ast_build_from_context(isl_set_universe(S.getParamSpace())); + isl_ast_build *Build; + Build = isl_ast_build_from_context(S.getContext()); + // TODO: We used to do + // Build = isl_ast_build_from_context(isl_set_universe(S.getParamSpace())); + // but that of course does not constrain the input variables, not even by + // their types. The question of which constraints can be assumed during the + // RTC remains open however. + isl_set *Universe = isl_set_universe(isl_set_get_space(Domain)); bool AlwaysExecuted = isl_set_is_equal(Domain, Universe); isl_set_free(Universe); 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/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 @@ -57,6 +57,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 +68,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,14 @@ 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_print_computed_bounds(isl_ctx *ctx, int val); +int isl_options_get_ast_build_print_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); 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,9 @@ 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 +230,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 +252,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 +482,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 +497,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 +512,8 @@ { isl_ctx *ctx; isl_ast_expr *expr; + isl_bool is_neg; + int size; if (!v) return NULL; @@ -463,6 +532,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 +592,37 @@ 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; + + 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,15 +1663,38 @@ return 0; } +__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; + + 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); + need_parens = 1; + expr = expr->u.bound.expr; + } if (need_parens) p = isl_printer_print_str(p, "("); @@ -1810,8 +1939,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 +1972,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 +1988,11 @@ case isl_ast_expr_int: p = isl_printer_print_val(p, expr->u.v); break; + case isl_ast_expr_bound_t: + 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, ")"); case isl_ast_expr_error: break; } @@ -1931,6 +2068,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 +2116,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 +2126,19 @@ 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: + 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 +2437,13 @@ 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 "compute_bounds" option + * 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,442 @@ #include #include #include +#include +#include +#include "isl_ast_private.h" +#include "isl_id_private.h" + +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); +} + +__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; + 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: + case isl_ast_op_select: + flag = 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); + } + + 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; + if (flag == 1) { + // Result is maximum type + if (expr->u.op.args[1]->u.bound.size > bits) { + bits = expr->u.op.args[1]->u.bound.size; + if (is_signed && !expr->u.op.args[1]->u.bound.is_signed) + bits++; + else + is_signed = expr->u.op.args[1]->u.bound.is_signed; + } else if (!is_signed && expr->u.op.args[1]->u.bound.is_signed) { + is_signed = expr->u.op.args[1]->u.bound.is_signed; + if (bits == expr->u.op.args[1]->u.bound.size) + bits++; + } + } else { + // Result is minimum type + if (expr->u.op.args[1]->u.bound.size < bits || + (expr->u.op.args[1]->u.bound.size == bits && + !expr->u.op.args[1]->u.bound.is_signed)) { + bits = expr->u.op.args[1]->u.bound.size; + is_signed = expr->u.op.args[1]->u.bound.is_signed; + } + } + + if (add) + bits++; + + expr = isl_ast_expr_bound(expr, is_signed, bits, NULL); + } + return expr; +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) { + // TODO: CHeck if this is correct + 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. + */ +__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); + 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: + isl_die(isl_ast_expr_get_ctx(expr), isl_error_internal, + "invalid expression type", goto error); + } + +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); +} + +__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; + 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; + + // XXX what if lower is not signed but upper is. Can this happen? + + if (build->maximum_size && lower_bits > build->maximum_size) { + isl_val *upper, *lower; + if (is_lower_signed) { + upper = isl_val_int_from_si(isl_ast_build_get_ctx(build), LONG_MAX); + lower = isl_val_int_from_si(isl_ast_build_get_ctx(build), LONG_MIN); + } else { + upper = isl_val_int_from_ui(isl_ast_build_get_ctx(build), ULONG_MAX); + 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; + +/* 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) { + int all_bound = 1; + 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: + 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) + return isl_ast_build_set_size_with_solver(build, expr, aff); + expr_approximated_success++; + return expr; + } + // Default: Fall throught to solver + } + } + } + + 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 +580,189 @@ 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) { + isl_val_free(v); + isl_val_free(d); + return NULL; + } + + ctx = isl_aff_get_ctx(aff); + cons = isl_alloc_type(ctx, isl_ast_expr_constructor); + if (!cons) { + isl_val_free(v); + isl_val_free(d); + return NULL; + } + + 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; +} + +/* 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,6 +871,12 @@ 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) @@ -323,36 +948,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 +959,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 +1050,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 +1105,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 +1170,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,20 +1199,22 @@ * 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); if (s < 0) @@ -570,10 +1249,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 +1274,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 +1283,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 +1291,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 +1498,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 +1511,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 +1525,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 +1553,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 +1590,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 +1629,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 +1655,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 +1665,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 +1679,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 +1733,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 +1758,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 +1773,14 @@ if (!aff) return NULL; - expr = isl_ast_expr_alloc_int_si(ctx, 0); - expr_neg = isl_ast_expr_alloc_int_si(ctx, 0); + ls = isl_aff_get_domain_local_space(aff); - aff = extract_rational(aff, &expr, build); + 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); - aff = extract_modulos(aff, &expr, &expr_neg, build); - expr = ast_expr_sub(expr, expr_neg); - - 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 +1789,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 +1833,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 +1854,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 +1982,7 @@ isl_ctx *ctx; isl_val *c; isl_ast_expr *expr, *cst; + isl_aff *aff_in; if (!aff) return NULL; @@ -1290,12 +1996,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; } @@ -1343,7 +2053,9 @@ isl_ast_expr *expr_pos; isl_ast_expr *expr_neg; 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 +2078,40 @@ 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); } + 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_int && - isl_ast_expr_get_type(expr_neg) != isl_ast_expr_int) { + isl_ast_expr_get_type(expr_neg) != 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 { @@ -1446,6 +2170,7 @@ isl_constraint_list *list; isl_ast_expr *res; isl_set *set; + isl_ast_build *outer_build = build; list = isl_basic_set_get_constraint_list(bset); isl_basic_set_free(bset); @@ -1791,9 +2516,11 @@ expr_i = isl_ast_expr_from_aff(aff, build); if (!expr_i) goto error; + isl_ast_build_set_size(build, expr_i, aff); expr->u.op.args[i] = expr_i; } + expr = isl_ast_bin_op_set_size(expr, build); isl_aff_list_free(list); return expr; error: @@ -2486,4 +3213,4 @@ expr = isl_ast_build_from_pw_multi_aff_internal(build, isl_ast_op_call, iteration); return isl_ast_node_alloc_user(expr); -} +} \ No newline at end of file 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,8 @@ * generated. That is, it (mostly) contains information about outer * loops that can be used to simplify inner loops. * + * "compute_bounds" is a local copy 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 +147,10 @@ struct isl_ast_build { int ref; + int compute_bounds; + int approximate_bounds; + int maximum_size; + int outer_pos; int depth; @@ -197,8 +203,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 @@ -24,6 +24,7 @@ #include #include #include +#include "isl_ast_private.h" /* Data used in generate_domain. * @@ -658,6 +659,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 +691,28 @@ 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) { + if (n > 1) { + expr = isl_ast_expr_bound(expr, is_signed, bits, NULL); + } else { + isl_die(isl_ast_build_get_ctx(build), isl_error_internal, "Should not happen!", return NULL); + } + } return expr; error: isl_pw_aff_list_free(list); @@ -971,6 +993,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 +1101,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 +1204,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 +1213,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,18 +1428,42 @@ * 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; 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 +1618,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); @@ -1520,6 +1652,7 @@ else graft = refine_generic(graft, bounds, domain, for_build); + isl_ast_build_free(for_build); } isl_set_free(guard); @@ -5038,6 +5171,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_graft.c =================================================================== --- lib/External/isl/isl_ast_graft.c +++ lib/External/isl/isl_ast_graft.c @@ -853,13 +853,13 @@ isl_set_copy(guard)); list = gist_guards(list, guard); list = insert_pending_guard_nodes(list, guard_build); - isl_ast_build_free(guard_build); node_list = extract_node_list(list); node = isl_ast_node_from_ast_node_list(node_list); + graft = isl_ast_graft_alloc(node, build); + isl_ast_build_free(guard_build); isl_ast_graft_list_free(list); - graft = isl_ast_graft_alloc(node, build); graft = store_guard(graft, guard, build); graft = isl_ast_graft_enforce(graft, enforced); @@ -983,6 +983,7 @@ __isl_keep isl_ast_build *build) { isl_ast_node_list *node_list; + isl_ast_graft *tmp; list = insert_pending_guard_nodes(list, build); node_list = extract_node_list(list); Index: lib/External/isl/isl_ast_graft_private.h =================================================================== --- lib/External/isl/isl_ast_graft_private.h +++ lib/External/isl/isl_ast_graft_private.h @@ -99,4 +99,5 @@ __isl_give isl_printer *isl_printer_print_ast_graft(__isl_take isl_printer *p, __isl_keep isl_ast_graft *graft); + #endif 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,13 @@ "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_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 +333,18 @@ 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_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,9 @@ int ast_build_atomic_upper_bound; int ast_build_prefer_pdiv; + int ast_build_compute_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); +}