Viewing file:  isl_ast_build.c (68.23 KB) -rw-r--r--
Select action/file-type:
 (+) |  (+) |  (+) | Code (+) | Session (+) |  (+) | SDB (+) |  (+) |  (+) |  (+) |  (+) |  (+) |
/*
* Copyright 2012-2013 Ecole Normale Superieure
* Copyright 2014 INRIA Rocquencourt
*
* Use of this software is governed by the MIT license
*
* Written by Sven Verdoolaege,
* Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
* and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
* B.P. 105 - 78153 Le Chesnay, France
*/
#include <isl/id.h>
#include <isl/val.h>
#include <isl/space.h>
#include <isl/map.h>
#include <isl/aff.h>
#include <isl/constraint.h>
#include <isl/map.h>
#include <isl/union_set.h>
#include <isl/union_map.h>
#include <isl_ast_build_private.h>
#include <isl_ast_private.h>
#include <isl_config.h>
/* Construct a map that isolates the current dimension.
*
* Essentially, the current dimension of "set" is moved to the single output
* dimension in the result, with the current dimension in the domain replaced
* by an unconstrained variable.
*/
__isl_give isl_map *isl_ast_build_map_to_iterator(
__isl_keep isl_ast_build *build, __isl_take isl_set *set)
{
isl_map *map;
map = isl_map_from_domain(set);
map = isl_map_add_dims(map, isl_dim_out, 1);
if (!build)
return isl_map_free(map);
map = isl_map_equate(map, isl_dim_in, build->depth, isl_dim_out, 0);
map = isl_map_eliminate(map, isl_dim_in, build->depth, 1);
return map;
}
/* Initialize the information derived during the AST generation to default
* values for a schedule domain in "space".
*
* We also check that the remaining fields are not NULL so that
* the calling functions don't have to perform this test.
*/
static __isl_give isl_ast_build *isl_ast_build_init_derived(
__isl_take isl_ast_build *build, __isl_take isl_space *space)
{
isl_ctx *ctx;
isl_vec *strides;
isl_size dim;
build = isl_ast_build_cow(build);
if (!build || !build->domain)
goto error;
ctx = isl_ast_build_get_ctx(build);
dim = isl_space_dim(space, isl_dim_set);
if (dim < 0)
goto error;
strides = isl_vec_alloc(ctx, dim);
strides = isl_vec_set_si(strides, 1);
isl_vec_free(build->strides);
build->strides = strides;
space = isl_space_map_from_set(space);
isl_multi_aff_free(build->offsets);
build->offsets = isl_multi_aff_zero(isl_space_copy(space));
isl_multi_aff_free(build->values);
build->values = isl_multi_aff_identity(isl_space_copy(space));
isl_multi_aff_free(build->internal2input);
build->internal2input = isl_multi_aff_identity(space);
if (!build->iterators || !build->domain || !build->generated ||
!build->pending || !build->values || !build->internal2input ||
!build->strides || !build->offsets || !build->options)
return isl_ast_build_free(build);
return build;
error:
isl_space_free(space);
return isl_ast_build_free(build);
}
/* Return an isl_id called "c%d", with "%d" set to "i".
* If an isl_id with such a name already appears among the parameters
* in build->domain, then adjust the name to "c%d_%d".
*/
static __isl_give isl_id *generate_name(isl_ctx *ctx, int i,
__isl_keep isl_ast_build *build)
{
int j;
char name[23];
isl_set *dom = build->domain;
snprintf(name, sizeof(name), "c%d", i);
j = 0;
while (isl_set_find_dim_by_name(dom, isl_dim_param, name) >= 0)
snprintf(name, sizeof(name), "c%d_%d", i, j++);
return isl_id_alloc(ctx, name, NULL);
}
/* Create an isl_ast_build with "set" as domain.
*
* The input set is usually a parameter domain, but we currently allow it to
* be any kind of set. We set the domain of the returned isl_ast_build
* to "set" and initialize all the other fields to default values.
*/
__isl_give isl_ast_build *isl_ast_build_from_context(__isl_take isl_set *set)
{
int i;
isl_size n;
isl_ctx *ctx;
isl_space *space;
isl_ast_build *build;
set = isl_set_compute_divs(set);
n = isl_set_dim(set, isl_dim_set);
if (n < 0)
goto error;
ctx = isl_set_get_ctx(set);
build = isl_calloc_type(ctx, isl_ast_build);
if (!build)
goto error;
build->ref = 1;
build->domain = set;
build->generated = isl_set_copy(build->domain);
build->pending = isl_set_universe(isl_set_get_space(build->domain));
build->options = isl_union_map_empty(isl_space_params_alloc(ctx, 0));
build->depth = n;
build->iterators = isl_id_list_alloc(ctx, n);
for (i = 0; i < n; ++i) {
isl_id *id;
if (isl_set_has_dim_id(set, isl_dim_set, i))
id = isl_set_get_dim_id(set, isl_dim_set, i);
else
id = generate_name(ctx, i, build);
build->iterators = isl_id_list_add(build->iterators, id);
}
space = isl_set_get_space(set);
if (isl_space_is_params(space))
space = isl_space_set_from_params(space);
return isl_ast_build_init_derived(build, space);
error:
isl_set_free(set);
return NULL;
}
/* Create an isl_ast_build with a universe (parametric) context.
*/
__isl_give isl_ast_build *isl_ast_build_alloc(isl_ctx *ctx)
{
isl_space *space;
isl_set *context;
space = isl_space_params_alloc(ctx, 0);
context = isl_set_universe(space);
return isl_ast_build_from_context(context);
}
__isl_give isl_ast_build *isl_ast_build_copy(__isl_keep isl_ast_build *build)
{
if (!build)
return NULL;
build->ref++;
return build;
}
__isl_give isl_ast_build *isl_ast_build_dup(__isl_keep isl_ast_build *build)
{
isl_ctx *ctx;
isl_ast_build *dup;
if (!build)
return NULL;
ctx = isl_ast_build_get_ctx(build);
dup = isl_calloc_type(ctx, isl_ast_build);
if (!dup)
return NULL;
dup->ref = 1;
dup->outer_pos = build->outer_pos;
dup->depth = build->depth;
dup->iterators = isl_id_list_copy(build->iterators);
dup->domain = isl_set_copy(build->domain);
dup->generated = isl_set_copy(build->generated);
dup->pending = isl_set_copy(build->pending);
dup->values = isl_multi_aff_copy(build->values);
dup->internal2input = isl_multi_aff_copy(build->internal2input);
dup->value = isl_pw_aff_copy(build->value);
dup->strides = isl_vec_copy(build->strides);
dup->offsets = isl_multi_aff_copy(build->offsets);
dup->executed = isl_union_map_copy(build->executed);
dup->single_valued = build->single_valued;
dup->options = isl_union_map_copy(build->options);
dup->at_each_domain = build->at_each_domain;
dup->at_each_domain_user = build->at_each_domain_user;
dup->before_each_for = build->before_each_for;
dup->before_each_for_user = build->before_each_for_user;
dup->after_each_for = build->after_each_for;
dup->after_each_for_user = build->after_each_for_user;
dup->before_each_mark = build->before_each_mark;
dup->before_each_mark_user = build->before_each_mark_user;
dup->after_each_mark = build->after_each_mark;
dup->after_each_mark_user = build->after_each_mark_user;
dup->create_leaf = build->create_leaf;
dup->create_leaf_user = build->create_leaf_user;
dup->node = isl_schedule_node_copy(build->node);
if (build->loop_type) {
int i;
dup->n = build->n;
dup->loop_type = isl_alloc_array(ctx,
enum isl_ast_loop_type, dup->n);
if (dup->n && !dup->loop_type)
return isl_ast_build_free(dup);
for (i = 0; i < dup->n; ++i)
dup->loop_type[i] = build->loop_type[i];
}
if (!dup->iterators || !dup->domain || !dup->generated ||
!dup->pending || !dup->values ||
!dup->strides || !dup->offsets || !dup->options ||
(build->internal2input && !dup->internal2input) ||
(build->executed && !dup->executed) ||
(build->value && !dup->value) ||
(build->node && !dup->node))
return isl_ast_build_free(dup);
return dup;
}
/* Align the parameters of "build" to those of "model", introducing
* additional parameters if needed.
*/
__isl_give isl_ast_build *isl_ast_build_align_params(
__isl_take isl_ast_build *build, __isl_take isl_space *model)
{
build = isl_ast_build_cow(build);
if (!build)
goto error;
build->domain = isl_set_align_params(build->domain,
isl_space_copy(model));
build->generated = isl_set_align_params(build->generated,
isl_space_copy(model));
build->pending = isl_set_align_params(build->pending,
isl_space_copy(model));
build->values = isl_multi_aff_align_params(build->values,
isl_space_copy(model));
build->offsets = isl_multi_aff_align_params(build->offsets,
isl_space_copy(model));
build->options = isl_union_map_align_params(build->options,
isl_space_copy(model));
if (build->internal2input) {
build->internal2input =
isl_multi_aff_align_params(build->internal2input,
model);
if (!build->internal2input)
return isl_ast_build_free(build);
} else {
isl_space_free(model);
}
if (!build->domain || !build->values || !build->offsets ||
!build->options)
return isl_ast_build_free(build);
return build;
error:
isl_space_free(model);
return NULL;
}
__isl_give isl_ast_build *isl_ast_build_cow(__isl_take isl_ast_build *build)
{
if (!build)
return NULL;
if (build->ref == 1)
return build;
build->ref--;
return isl_ast_build_dup(build);
}
__isl_null isl_ast_build *isl_ast_build_free(
__isl_take isl_ast_build *build)
{
if (!build)
return NULL;
if (--build->ref > 0)
return NULL;
isl_id_list_free(build->iterators);
isl_set_free(build->domain);
isl_set_free(build->generated);
isl_set_free(build->pending);
isl_multi_aff_free(build->values);
isl_multi_aff_free(build->internal2input);
isl_pw_aff_free(build->value);
isl_vec_free(build->strides);
isl_multi_aff_free(build->offsets);
isl_multi_aff_free(build->schedule_map);
isl_union_map_free(build->executed);
isl_union_map_free(build->options);
isl_schedule_node_free(build->node);
free(build->loop_type);
isl_set_free(build->isolated);
free(build);
return NULL;
}
isl_ctx *isl_ast_build_get_ctx(__isl_keep isl_ast_build *build)
{
return build ? isl_set_get_ctx(build->domain) : NULL;
}
/* Replace build->options by "options".
*/
__isl_give isl_ast_build *isl_ast_build_set_options(
__isl_take isl_ast_build *build, __isl_take isl_union_map *options)
{
build = isl_ast_build_cow(build);
if (!build || !options)
goto error;
isl_union_map_free(build->options);
build->options = options;
return build;
error:
isl_union_map_free(options);
return isl_ast_build_free(build);
}
/* Set the iterators for the next code generation.
*
* If we still have some iterators left from the previous code generation
* (if any) or if iterators have already been set by a previous
* call to this function, then we remove them first.
*/
__isl_give isl_ast_build *isl_ast_build_set_iterators(
__isl_take isl_ast_build *build, __isl_take isl_id_list *iterators)
{
isl_size dim, n_it;
build = isl_ast_build_cow(build);
if (!build)
goto error;
dim = isl_ast_build_dim(build, isl_dim_set);
n_it = isl_id_list_n_id(build->iterators);
if (dim < 0 || n_it < 0)
goto error;
if (n_it < dim)
isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
"isl_ast_build in inconsistent state", goto error);
if (n_it > dim)
build->iterators = isl_id_list_drop(build->iterators,
dim, n_it - dim);
build->iterators = isl_id_list_concat(build->iterators, iterators);
if (!build->iterators)
return isl_ast_build_free(build);
return build;
error:
isl_id_list_free(iterators);
return isl_ast_build_free(build);
}
/* Set the "at_each_domain" callback of "build" to "fn".
*/
__isl_give isl_ast_build *isl_ast_build_set_at_each_domain(
__isl_take isl_ast_build *build,
__isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
__isl_keep isl_ast_build *build, void *user), void *user)
{
build = isl_ast_build_cow(build);
if (!build)
return NULL;
build->at_each_domain = fn;
build->at_each_domain_user = user;
return build;
}
/* Set the "before_each_for" callback of "build" to "fn".
*/
__isl_give isl_ast_build *isl_ast_build_set_before_each_for(
__isl_take isl_ast_build *build,
__isl_give isl_id *(*fn)(__isl_keep isl_ast_build *build,
void *user), void *user)
{
build = isl_ast_build_cow(build);
if (!build)
return NULL;
build->before_each_for = fn;
build->before_each_for_user = user;
return build;
}
/* Set the "after_each_for" callback of "build" to "fn".
*/
__isl_give isl_ast_build *isl_ast_build_set_after_each_for(
__isl_take isl_ast_build *build,
__isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
__isl_keep isl_ast_build *build, void *user), void *user)
{
build = isl_ast_build_cow(build);
if (!build)
return NULL;
build->after_each_for = fn;
build->after_each_for_user = user;
return build;
}
/* Set the "before_each_mark" callback of "build" to "fn".
*/
__isl_give isl_ast_build *isl_ast_build_set_before_each_mark(
__isl_take isl_ast_build *build,
isl_stat (*fn)(__isl_keep isl_id *mark, __isl_keep isl_ast_build *build,
void *user), void *user)
{
build = isl_ast_build_cow(build);
if (!build)
return NULL;
build->before_each_mark = fn;
build->before_each_mark_user = user;
return build;
}
/* Set the "after_each_mark" callback of "build" to "fn".
*/
__isl_give isl_ast_build *isl_ast_build_set_after_each_mark(
__isl_take isl_ast_build *build,
__isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
__isl_keep isl_ast_build *build, void *user), void *user)
{
build = isl_ast_build_cow(build);
if (!build)
return NULL;
build->after_each_mark = fn;
build->after_each_mark_user = user;
return build;
}
/* Set the "create_leaf" callback of "build" to "fn".
*/
__isl_give isl_ast_build *isl_ast_build_set_create_leaf(
__isl_take isl_ast_build *build,
__isl_give isl_ast_node *(*fn)(__isl_take isl_ast_build *build,
void *user), void *user)
{
build = isl_ast_build_cow(build);
if (!build)
return NULL;
build->create_leaf = fn;
build->create_leaf_user = user;
return build;
}
/* Clear all information that is specific to this code generation
* and that is (probably) not meaningful to any nested code generation.
*/
__isl_give isl_ast_build *isl_ast_build_clear_local_info(
__isl_take isl_ast_build *build)
{
isl_space *space;
build = isl_ast_build_cow(build);
if (!build)
return NULL;
space = isl_union_map_get_space(build->options);
isl_union_map_free(build->options);
build->options = isl_union_map_empty(space);
build->at_each_domain = NULL;
build->at_each_domain_user = NULL;
build->before_each_for = NULL;
build->before_each_for_user = NULL;
build->after_each_for = NULL;
build->after_each_for_user = NULL;
build->before_each_mark = NULL;
build->before_each_mark_user = NULL;
build->after_each_mark = NULL;
build->after_each_mark_user = NULL;
build->create_leaf = NULL;
build->create_leaf_user = NULL;
if (!build->options)
return isl_ast_build_free(build);
return build;
}
/* Have any loops been eliminated?
* That is, do any of the original schedule dimensions have a fixed
* value that has been substituted?
*/
static int any_eliminated(isl_ast_build *build)
{
int i;
for (i = 0; i < build->depth; ++i)
if (isl_ast_build_has_affine_value(build, i))
return 1;
return 0;
}
/* Clear build->schedule_map.
* This function should be called whenever anything that might affect
* the result of isl_ast_build_get_schedule_map_multi_aff changes.
* In particular, it should be called when the depth is changed or
* when an iterator is determined to have a fixed value.
*/
static void isl_ast_build_reset_schedule_map(__isl_keep isl_ast_build *build)
{
if (!build)
return;
isl_multi_aff_free(build->schedule_map);
build->schedule_map = NULL;
}
/* Do we need a (non-trivial) schedule map?
* That is, is the internal schedule space different from
* the external schedule space?
*
* The internal and external schedule spaces are only the same
* if code has been generated for the entire schedule and if none
* of the loops have been eliminated.
*/
isl_bool isl_ast_build_need_schedule_map(__isl_keep isl_ast_build *build)
{
isl_size dim;
dim = isl_ast_build_dim(build, isl_dim_set);
if (dim < 0)
return isl_bool_error;
return isl_bool_ok(build->depth != dim || any_eliminated(build));
}
/* Return a mapping from the internal schedule space to the external
* schedule space in the form of an isl_multi_aff.
* The internal schedule space originally corresponds to that of the
* input schedule. This may change during the code generation if
* if isl_ast_build_insert_dim is ever called.
* The external schedule space corresponds to the
* loops that have been generated.
*
* Currently, the only difference between the internal schedule domain
* and the external schedule domain is that some dimensions are projected
* out in the external schedule domain. In particular, the dimensions
* for which no code has been generated yet and the dimensions that correspond
* to eliminated loops.
*
* We cache a copy of the schedule_map in build->schedule_map.
* The cache is cleared through isl_ast_build_reset_schedule_map
* whenever anything changes that might affect the result of this function.
*/
__isl_give isl_multi_aff *isl_ast_build_get_schedule_map_multi_aff(
__isl_keep isl_ast_build *build)
{
isl_bool needs_map;
isl_space *space;
isl_multi_aff *ma;
if (!build)
return NULL;
if (build->schedule_map)
return isl_multi_aff_copy(build->schedule_map);
needs_map = isl_ast_build_need_schedule_map(build);
if (needs_map < 0)
return NULL;
space = isl_ast_build_get_space(build, 1);
space = isl_space_map_from_set(space);
ma = isl_multi_aff_identity(space);
if (needs_map) {
int i;
isl_size dim = isl_ast_build_dim(build, isl_dim_set);
if (dim < 0)
ma = isl_multi_aff_free(ma);
ma = isl_multi_aff_drop_dims(ma, isl_dim_out,
build->depth, dim - build->depth);
for (i = build->depth - 1; i >= 0; --i)
if (isl_ast_build_has_affine_value(build, i))
ma = isl_multi_aff_drop_dims(ma,
isl_dim_out, i, 1);
}
build->schedule_map = ma;
return isl_multi_aff_copy(build->schedule_map);
}
/* Return a mapping from the internal schedule space to the external
* schedule space in the form of an isl_map.
*/
__isl_give isl_map *isl_ast_build_get_schedule_map(
__isl_keep isl_ast_build *build)
{
isl_multi_aff *ma;
ma = isl_ast_build_get_schedule_map_multi_aff(build);
return isl_map_from_multi_aff(ma);
}
/* Return the position of the dimension in build->domain for which
* an AST node is currently being generated.
*/
int isl_ast_build_get_depth(__isl_keep isl_ast_build *build)
{
return build ? build->depth : -1;
}
/* Prepare for generating code for the next level.
* In particular, increase the depth and reset any information
* that is local to the current depth.
*/
__isl_give isl_ast_build *isl_ast_build_increase_depth(
__isl_take isl_ast_build *build)
{
build = isl_ast_build_cow(build);
if (!build)
return NULL;
build->depth++;
isl_ast_build_reset_schedule_map(build);
build->value = isl_pw_aff_free(build->value);
return build;
}
void isl_ast_build_dump(__isl_keep isl_ast_build *build)
{
if (!build)
return;
fprintf(stderr, "domain: ");
isl_set_dump(build->domain);
fprintf(stderr, "generated: ");
isl_set_dump(build->generated);
fprintf(stderr, "pending: ");
isl_set_dump(build->pending);
fprintf(stderr, "iterators: ");
isl_id_list_dump(build->iterators);
fprintf(stderr, "values: ");
isl_multi_aff_dump(build->values);
if (build->value) {
fprintf(stderr, "value: ");
isl_pw_aff_dump(build->value);
}
fprintf(stderr, "strides: ");
isl_vec_dump(build->strides);
fprintf(stderr, "offsets: ");
isl_multi_aff_dump(build->offsets);
fprintf(stderr, "internal2input: ");
isl_multi_aff_dump(build->internal2input);
}
/* Initialize "build" for AST construction in schedule space "space"
* in the case that build->domain is a parameter set.
*
* build->iterators is assumed to have been updated already.
*/
static __isl_give isl_ast_build *isl_ast_build_init(
__isl_take isl_ast_build *build, __isl_take isl_space *space)
{
isl_set *set;
build = isl_ast_build_cow(build);
if (!build)
goto error;
set = isl_set_universe(isl_space_copy(space));
build->domain = isl_set_intersect_params(isl_set_copy(set),
build->domain);
build->pending = isl_set_intersect_params(isl_set_copy(set),
build->pending);
build->generated = isl_set_intersect_params(set, build->generated);
return isl_ast_build_init_derived(build, space);
error:
isl_ast_build_free(build);
isl_space_free(space);
return NULL;
}
/* Assign "aff" to *user and return -1, effectively extracting
* the first (and presumably only) affine expression in the isl_pw_aff
* on which this function is used.
*/
static isl_stat extract_single_piece(__isl_take isl_set *set,
__isl_take isl_aff *aff, void *user)
{
isl_aff **p = user;
*p = aff;
isl_set_free(set);
return isl_stat_error;
}
/* Intersect "set" with the stride constraint of "build", if any.
*/
static __isl_give isl_set *intersect_stride_constraint(__isl_take isl_set *set,
__isl_keep isl_ast_build *build)
{
isl_set *stride;
if (!build)
return isl_set_free(set);
if (!isl_ast_build_has_stride(build, build->depth))
return set;
stride = isl_ast_build_get_stride_constraint(build);
return isl_set_intersect(set, stride);
}
/* Check if the given bounds on the current dimension (together with
* the stride constraint, if any) imply that
* this current dimension attains only a single value (in terms of
* parameters and outer dimensions).
* If so, we record it in build->value.
* If, moreover, this value can be represented as a single affine expression,
* then we also update build->values, effectively marking the current
* dimension as "eliminated".
*
* When computing the gist of the fixed value that can be represented
* as a single affine expression, it is important to only take into
* account the domain constraints in the original AST build and
* not the domain of the affine expression itself.
* Otherwise, a [i/3] is changed into a i/3 because we know that i
* is a multiple of 3, but then we end up not expressing anywhere
* in the context that i is a multiple of 3.
*/
static __isl_give isl_ast_build *update_values(
__isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds)
{
isl_bool sv;
isl_size n;
isl_pw_multi_aff *pma;
isl_aff *aff = NULL;
isl_map *it_map;
isl_set *set;
set = isl_set_from_basic_set(bounds);
set = isl_set_intersect(set, isl_set_copy(build->domain));
set = intersect_stride_constraint(set, build);
it_map = isl_ast_build_map_to_iterator(build, set);
sv = isl_map_is_single_valued(it_map);
if (sv < 0)
build = isl_ast_build_free(build);
if (!build || !sv) {
isl_map_free(it_map);
return build;
}
pma = isl_pw_multi_aff_from_map(it_map);
build->value = isl_pw_multi_aff_get_pw_aff(pma, 0);
build->value = isl_ast_build_compute_gist_pw_aff(build, build->value);
build->value = isl_pw_aff_coalesce(build->value);
isl_pw_multi_aff_free(pma);
n = isl_pw_aff_n_piece(build->value);
if (n < 0)
return isl_ast_build_free(build);
if (n != 1)
return build;
isl_pw_aff_foreach_piece(build->value, &extract_single_piece, &aff);
build->values = isl_multi_aff_set_aff(build->values, build->depth, aff);
if (!build->values)
return isl_ast_build_free(build);
isl_ast_build_reset_schedule_map(build);
return build;
}
/* Update the AST build based on the given loop bounds for
* the current dimension and the stride information available in the build.
*
* We first make sure that the bounds do not refer to any iterators
* that have already been eliminated.
* Then, we check if the bounds imply that the current iterator
* has a fixed value.
* If they do and if this fixed value can be expressed as a single
* affine expression, we eliminate the iterators from the bounds.
* Note that we cannot simply plug in this single value using
* isl_basic_set_preimage_multi_aff as the single value may only
* be defined on a subset of the domain. Plugging in the value
* would restrict the build domain to this subset, while this
* restriction may not be reflected in the generated code.
* Finally, we intersect build->domain with the updated bounds.
* We also add the stride constraint unless we have been able
* to find a fixed value expressed as a single affine expression.
*
* Note that the check for a fixed value in update_values requires
* us to intersect the bounds with the current build domain.
* When we intersect build->domain with the updated bounds in
* the final step, we make sure that these updated bounds have
* not been intersected with the old build->domain.
* Otherwise, we would indirectly intersect the build domain with itself,
* which can lead to inefficiencies, in particular if the build domain
* contains any unknown divs.
*
* The pending and generated sets are not updated by this function to
* match the updated domain.
* The caller still needs to call isl_ast_build_set_pending_generated.
*/
__isl_give isl_ast_build *isl_ast_build_set_loop_bounds(
__isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds)
{
isl_set *set;
build = isl_ast_build_cow(build);
if (!build)
goto error;
build = update_values(build, isl_basic_set_copy(bounds));
if (!build)
goto error;
set = isl_set_from_basic_set(isl_basic_set_copy(bounds));
if (isl_ast_build_has_affine_value(build, build->depth)) {
set = isl_set_eliminate(set, isl_dim_set, build->depth, 1);
set = isl_set_compute_divs(set);
build->pending = isl_set_intersect(build->pending,
isl_set_copy(set));
build->domain = isl_set_intersect(build->domain, set);
} else {
build->domain = isl_set_intersect(build->domain, set);
build = isl_ast_build_include_stride(build);
if (!build)
goto error;
}
isl_basic_set_free(bounds);
if (!build->domain || !build->pending || !build->generated)
return isl_ast_build_free(build);
return build;
error:
isl_ast_build_free(build);
isl_basic_set_free(bounds);
return NULL;
}
/* Update the pending and generated sets of "build" according to "bounds".
* If the build has an affine value at the current depth,
* then isl_ast_build_set_loop_bounds has already set the pending set.
* Otherwise, do it here.
*/
__isl_give isl_ast_build *isl_ast_build_set_pending_generated(
__isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds)
{
isl_basic_set *generated, *pending;
if (!build)
goto error;
if (isl_ast_build_has_affine_value(build, build->depth)) {
isl_basic_set_free(bounds);
return build;
}
build = isl_ast_build_cow(build);
if (!build)
goto error;
pending = isl_basic_set_copy(bounds);
pending = isl_basic_set_drop_constraints_involving_dims(pending,
isl_dim_set, build->depth, 1);
build->pending = isl_set_intersect(build->pending,
isl_set_from_basic_set(pending));
generated = bounds;
generated = isl_basic_set_drop_constraints_not_involving_dims(
generated, isl_dim_set, build->depth, 1);
build->generated = isl_set_intersect(build->generated,
isl_set_from_basic_set(generated));
if (!build->pending || !build->generated)
return isl_ast_build_free(build);
return build;
error:
isl_ast_build_free(build);
isl_basic_set_free(bounds);
return NULL;
}
/* Intersect build->domain with "set", where "set" is specified
* in terms of the internal schedule domain.
*/
static __isl_give isl_ast_build *isl_ast_build_restrict_internal(
__isl_take isl_ast_build *build, __isl_take isl_set *set)
{
build = isl_ast_build_cow(build);
if (!build)
goto error;
set = isl_set_compute_divs(set);
build->domain = isl_set_intersect(build->domain, set);
build->domain = isl_set_coalesce(build->domain);
if (!build->domain)
return isl_ast_build_free(build);
return build;
error:
isl_ast_build_free(build);
isl_set_free(set);
return NULL;
}
/* Intersect build->generated and build->domain with "set",
* where "set" is specified in terms of the internal schedule domain.
*/
__isl_give isl_ast_build *isl_ast_build_restrict_generated(
__isl_take isl_ast_build *build, __isl_take isl_set *set)
{
set = isl_set_compute_divs(set);
build = isl_ast_build_restrict_internal(build, isl_set_copy(set));
build = isl_ast_build_cow(build);
if (!build)
goto error;
build->generated = isl_set_intersect(build->generated, set);
build->generated = isl_set_coalesce(build->generated);
if (!build->generated)
return isl_ast_build_free(build);
return build;
error:
isl_ast_build_free(build);
isl_set_free(set);
return NULL;
}
/* Replace the set of pending constraints by "guard", which is then
* no longer considered as pending.
* That is, add "guard" to the generated constraints and clear all pending
* constraints, making the domain equal to the generated constraints.
*/
__isl_give isl_ast_build *isl_ast_build_replace_pending_by_guard(
__isl_take isl_ast_build *build, __isl_take isl_set *guard)
{
build = isl_ast_build_restrict_generated(build, guard);
build = isl_ast_build_cow(build);
if (!build)
return NULL;
isl_set_free(build->domain);
build->domain = isl_set_copy(build->generated);
isl_set_free(build->pending);
build->pending = isl_set_universe(isl_set_get_space(build->domain));
if (!build->pending)
return isl_ast_build_free(build);
return build;
}
/* Intersect build->domain with "set", where "set" is specified
* in terms of the external schedule domain.
*/
__isl_give isl_ast_build *isl_ast_build_restrict(
__isl_take isl_ast_build *build, __isl_take isl_set *set)
{
isl_bool needs_map;
if (isl_set_is_params(set))
return isl_ast_build_restrict_generated(build, set);
needs_map = isl_ast_build_need_schedule_map(build);
if (needs_map < 0)
goto error;
if (needs_map) {
isl_multi_aff *ma;
ma = isl_ast_build_get_schedule_map_multi_aff(build);
set = isl_set_preimage_multi_aff(set, ma);
}
return isl_ast_build_restrict_generated(build, set);
error:
isl_ast_build_free(build);
isl_set_free(set);
return NULL;
}
/* Replace build->executed by "executed".
*/
__isl_give isl_ast_build *isl_ast_build_set_executed(
__isl_take isl_ast_build *build, __isl_take isl_union_map *executed)
{
build = isl_ast_build_cow(build);
if (!build)
goto error;
isl_union_map_free(build->executed);
build->executed = executed;
return build;
error:
isl_ast_build_free(build);
isl_union_map_free(executed);
return NULL;
}
/* Does "build" point to a band node?
* That is, are we currently handling a band node inside a schedule tree?
*/
int isl_ast_build_has_schedule_node(__isl_keep isl_ast_build *build)
{
if (!build)
return -1;
return build->node != NULL;
}
/* Return a copy of the band node that "build" refers to.
*/
__isl_give isl_schedule_node *isl_ast_build_get_schedule_node(
__isl_keep isl_ast_build *build)
{
if (!build)
return NULL;
return isl_schedule_node_copy(build->node);
}
/* Extract the loop AST generation types for the members of build->node
* and store them in build->loop_type.
*/
static __isl_give isl_ast_build *extract_loop_types(
__isl_take isl_ast_build *build)
{
int i;
isl_size n;
isl_ctx *ctx;
isl_schedule_node *node;
if (!build)
return NULL;
n = isl_schedule_node_band_n_member(build->node);
if (n < 0)
return isl_ast_build_free(build);
ctx = isl_ast_build_get_ctx(build);
if (!build->node)
isl_die(ctx, isl_error_internal, "missing AST node",
return isl_ast_build_free(build));
free(build->loop_type);
build->n = n;
build->loop_type = isl_alloc_array(ctx,
enum isl_ast_loop_type, build->n);
if (build->n && !build->loop_type)
return isl_ast_build_free(build);
node = build->node;
for (i = 0; i < build->n; ++i)
build->loop_type[i] =
isl_schedule_node_band_member_get_ast_loop_type(node, i);
return build;
}
/* Replace the band node that "build" refers to by "node" and
* extract the corresponding loop AST generation types.
*/
__isl_give isl_ast_build *isl_ast_build_set_schedule_node(
__isl_take isl_ast_build *build,
__isl_take isl_schedule_node *node)
{
build = isl_ast_build_cow(build);
if (!build || !node)
goto error;
isl_schedule_node_free(build->node);
build->node = node;
build = extract_loop_types(build);
return build;
error:
isl_ast_build_free(build);
isl_schedule_node_free(node);
return NULL;
}
/* Remove any reference to a band node from "build".
*/
__isl_give isl_ast_build *isl_ast_build_reset_schedule_node(
__isl_take isl_ast_build *build)
{
build = isl_ast_build_cow(build);
if (!build)
return NULL;
isl_schedule_node_free(build->node);
build->node = NULL;
return build;
}
/* Return a copy of the current schedule domain.
*/
__isl_give isl_set *isl_ast_build_get_domain(__isl_keep isl_ast_build *build)
{
return build ? isl_set_copy(build->domain) : NULL;
}
/* Return a copy of the set of pending constraints.
*/
__isl_give isl_set *isl_ast_build_get_pending(
__isl_keep isl_ast_build *build)
{
return build ? isl_set_copy(build->pending) : NULL;
}
/* Return a copy of the set of generated constraints.
*/
__isl_give isl_set *isl_ast_build_get_generated(
__isl_keep isl_ast_build *build)
{
return build ? isl_set_copy(build->generated) : NULL;
}
/* Return a copy of the map from the internal schedule domain
* to the original input schedule domain.
*/
__isl_give isl_multi_aff *isl_ast_build_get_internal2input(
__isl_keep isl_ast_build *build)
{
return build ? isl_multi_aff_copy(build->internal2input) : NULL;
}
/* Return the number of variables of the given type
* in the (internal) schedule space.
*/
isl_size isl_ast_build_dim(__isl_keep isl_ast_build *build,
enum isl_dim_type type)
{
if (!build)
return isl_size_error;
return isl_set_dim(build->domain, type);
}
/* Return the (schedule) space of "build".
*
* If "internal" is set, then this space is the space of the internal
* representation of the entire schedule, including those parts for
* which no code has been generated yet.
*
* If "internal" is not set, then this space is the external representation
* of the loops generated so far.
*/
__isl_give isl_space *isl_ast_build_get_space(__isl_keep isl_ast_build *build,
int internal)
{
int i;
isl_size dim;
isl_bool needs_map;
isl_space *space;
if (!build)
return NULL;
space = isl_set_get_space(build->domain);
if (internal)
return space;
needs_map = isl_ast_build_need_schedule_map(build);
if (needs_map < 0)
return isl_space_free(space);
if (!needs_map)
return space;
dim = isl_ast_build_dim(build, isl_dim_set);
if (dim < 0)
return isl_space_free(space);
space = isl_space_drop_dims(space, isl_dim_set,
build->depth, dim - build->depth);
for (i = build->depth - 1; i >= 0; --i) {
isl_bool affine = isl_ast_build_has_affine_value(build, i);
if (affine < 0)
return isl_space_free(space);
if (affine)
space = isl_space_drop_dims(space, isl_dim_set, i, 1);
}
return space;
}
/* Return the external representation of the schedule space of "build",
* i.e., a space with a dimension for each loop generated so far,
* with the names of the dimensions set to the loop iterators.
*/
__isl_give isl_space *isl_ast_build_get_schedule_space(
__isl_keep isl_ast_build *build)
{
isl_space *space;
int i, skip;
if (!build)
return NULL;
space = isl_ast_build_get_space(build, 0);
skip = 0;
for (i = 0; i < build->depth; ++i) {
isl_id *id;
if (isl_ast_build_has_affine_value(build, i)) {
skip++;
continue;
}
id = isl_ast_build_get_iterator_id(build, i);
space = isl_space_set_dim_id(space, isl_dim_set, i - skip, id);
}
return space;
}
/* Return the current schedule, as stored in build->executed, in terms
* of the external schedule domain.
*/
__isl_give isl_union_map *isl_ast_build_get_schedule(
__isl_keep isl_ast_build *build)
{
isl_bool needs_map;
isl_union_map *executed;
isl_union_map *schedule;
needs_map = isl_ast_build_need_schedule_map(build);
if (needs_map < 0)
return NULL;
executed = isl_union_map_copy(build->executed);
if (needs_map) {
isl_map *proj = isl_ast_build_get_schedule_map(build);
executed = isl_union_map_apply_domain(executed,
isl_union_map_from_map(proj));
}
schedule = isl_union_map_reverse(executed);
return schedule;
}
/* Return the iterator attached to the internal schedule dimension "pos".
*/
__isl_give isl_id *isl_ast_build_get_iterator_id(
__isl_keep isl_ast_build *build, int pos)
{
if (!build)
return NULL;
return isl_id_list_get_id(build->iterators, pos);
}
/* Set the stride and offset of the current dimension to the given
* value and expression.
*/
static __isl_give isl_ast_build *set_stride(__isl_take isl_ast_build *build,
__isl_take isl_val *stride, __isl_take isl_aff *offset)
{
int pos;
build = isl_ast_build_cow(build);
if (!build || !stride || !offset)
goto error;
pos = build->depth;
build->strides = isl_vec_set_element_val(build->strides, pos, stride);
build->offsets = isl_multi_aff_set_aff(build->offsets, pos, offset);
if (!build->strides || !build->offsets)
return isl_ast_build_free(build);
return build;
error:
isl_val_free(stride);
isl_aff_free(offset);
return isl_ast_build_free(build);
}
/* Return a set expressing the stride constraint at the current depth.
*
* In particular, if the current iterator (i) is known to attain values
*
* f + s a
*
* where f is the offset and s is the stride, then the returned set
* expresses the constraint
*
* (f - i) mod s = 0
*/
__isl_give isl_set *isl_ast_build_get_stride_constraint(
__isl_keep isl_ast_build *build)
{
isl_aff *aff;
isl_set *set;
isl_val *stride;
int pos;
if (!build)
return NULL;
pos = build->depth;
if (!isl_ast_build_has_stride(build, pos))
return isl_set_universe(isl_ast_build_get_space(build, 1));
stride = isl_ast_build_get_stride(build, pos);
aff = isl_ast_build_get_offset(build, pos);
aff = isl_aff_add_coefficient_si(aff, isl_dim_in, pos, -1);
aff = isl_aff_mod_val(aff, stride);
set = isl_set_from_basic_set(isl_aff_zero_basic_set(aff));
return set;
}
/* Return the expansion implied by the stride and offset at the current
* depth.
*
* That is, return the mapping
*
* [i_0, ..., i_{d-1}, i_d, i_{d+1}, ...]
* -> [i_0, ..., i_{d-1}, s * i_d + offset(i), i_{d+1}, ...]
*
* where s is the stride at the current depth d and offset(i) is
* the corresponding offset.
*/
__isl_give isl_multi_aff *isl_ast_build_get_stride_expansion(
__isl_keep isl_ast_build *build)
{
isl_space *space;
isl_multi_aff *ma;
int pos;
isl_aff *aff, *offset;
isl_val *stride;
if (!build)
return NULL;
pos = isl_ast_build_get_depth(build);
space = isl_ast_build_get_space(build, 1);
space = isl_space_map_from_set(space);
ma = isl_multi_aff_identity(space);
if (!isl_ast_build_has_stride(build, pos))
return ma;
offset = isl_ast_build_get_offset(build, pos);
stride = isl_ast_build_get_stride(build, pos);
aff = isl_multi_aff_get_aff(ma, pos);
aff = isl_aff_scale_val(aff, stride);
aff = isl_aff_add(aff, offset);
ma = isl_multi_aff_set_aff(ma, pos, aff);
return ma;
}
/* Add constraints corresponding to any previously detected
* stride on the current dimension to build->domain.
*/
__isl_give isl_ast_build *isl_ast_build_include_stride(
__isl_take isl_ast_build *build)
{
isl_set *set;
if (!build)
return NULL;
if (!isl_ast_build_has_stride(build, build->depth))
return build;
build = isl_ast_build_cow(build);
if (!build)
return NULL;
set = isl_ast_build_get_stride_constraint(build);
build->domain = isl_set_intersect(build->domain, isl_set_copy(set));
build->generated = isl_set_intersect(build->generated, set);
if (!build->domain || !build->generated)
return isl_ast_build_free(build);
return build;
}
/* Check if the constraints in "set" imply any stride on the current
* dimension and, if so, record the stride information in "build"
* and return the updated "build".
*
* We assume that inner dimensions have been eliminated from "set"
* by the caller. This is needed because the common stride
* may be imposed by different inner dimensions on different parts of
* the domain.
* The assumption ensures that the lower bound does not depend
* on inner dimensions.
*/
__isl_give isl_ast_build *isl_ast_build_detect_strides(
__isl_take isl_ast_build *build, __isl_take isl_set *set)
{
int pos;
isl_bool no_stride;
isl_val *stride;
isl_aff *offset;
isl_stride_info *si;
if (!build)
goto error;
pos = isl_ast_build_get_depth(build);
si = isl_set_get_stride_info(set, pos);
stride = isl_stride_info_get_stride(si);
offset = isl_stride_info_get_offset(si);
isl_stride_info_free(si);
isl_set_free(set);
no_stride = isl_val_is_one(stride);
if (no_stride >= 0 && !no_stride)
return set_stride(build, stride, offset);
isl_val_free(stride);
isl_aff_free(offset);
if (no_stride < 0)
return isl_ast_build_free(build);
return build;
error:
isl_set_free(set);
return NULL;
}
/* Does "map" not involve the input dimension data->depth?
*/
static isl_bool free_of_depth(__isl_keep isl_map *map, void *user)
{
int *depth = user;
return isl_bool_not(isl_map_involves_dims(map, isl_dim_in, *depth, 1));
}
/* Do any options depend on the value of the dimension at the current depth?
*/
int isl_ast_build_options_involve_depth(__isl_keep isl_ast_build *build)
{
isl_bool free;
if (!build)
return -1;
free = isl_union_map_every_map(build->options, &free_of_depth,
&build->depth);
return isl_bool_not(free);
}
/* Construct the map
*
* { [i] -> [i] : i < pos; [i] -> [i + 1] : i >= pos }
*
* with "space" the parameter space of the constructed map.
*/
static __isl_give isl_map *construct_insertion_map(__isl_take isl_space *space,
int pos)
{
isl_constraint *c;
isl_basic_map *bmap1, *bmap2;
space = isl_space_set_from_params(space);
space = isl_space_add_dims(space, isl_dim_set, 1);
space = isl_space_map_from_set(space);
c = isl_constraint_alloc_equality(isl_local_space_from_space(space));
c = isl_constraint_set_coefficient_si(c, isl_dim_in, 0, 1);
c = isl_constraint_set_coefficient_si(c, isl_dim_out, 0, -1);
bmap1 = isl_basic_map_from_constraint(isl_constraint_copy(c));
c = isl_constraint_set_constant_si(c, 1);
bmap2 = isl_basic_map_from_constraint(c);
bmap1 = isl_basic_map_upper_bound_si(bmap1, isl_dim_in, 0, pos - 1);
bmap2 = isl_basic_map_lower_bound_si(bmap2, isl_dim_in, 0, pos);
return isl_basic_map_union(bmap1, bmap2);
}
static const char *option_str[] = {
[isl_ast_loop_atomic] = "atomic",
[isl_ast_loop_unroll] = "unroll",
[isl_ast_loop_separate] = "separate"
};
/* Update the "options" to reflect the insertion of a dimension
* at position "pos" in the schedule domain space.
* "space" is the original domain space before the insertion and
* may be named and/or structured.
*
* The (relevant) input options all have "space" as domain, which
* has to be mapped to the extended space.
* The values of the ranges also refer to the schedule domain positions
* and they therefore also need to be adjusted. In particular, values
* smaller than pos do not need to change, while values greater than or
* equal to pos need to be incremented.
* That is, we need to apply the following map.
*
* { atomic[i] -> atomic[i] : i < pos; [i] -> [i + 1] : i >= pos;
* unroll[i] -> unroll[i] : i < pos; [i] -> [i + 1] : i >= pos;
* separate[i] -> separate[i] : i < pos; [i] -> [i + 1] : i >= pos;
* separation_class[[i] -> [c]]
* -> separation_class[[i] -> [c]] : i < pos;
* separation_class[[i] -> [c]]
* -> separation_class[[i + 1] -> [c]] : i >= pos }
*/
static __isl_give isl_union_map *options_insert_dim(
__isl_take isl_union_map *options, __isl_take isl_space *space, int pos)
{
isl_map *map;
isl_union_map *insertion;
enum isl_ast_loop_type type;
const char *name = "separation_class";
space = isl_space_map_from_set(space);
map = isl_map_identity(space);
map = isl_map_insert_dims(map, isl_dim_out, pos, 1);
options = isl_union_map_apply_domain(options,
isl_union_map_from_map(map));
if (!options)
return NULL;
map = construct_insertion_map(isl_union_map_get_space(options), pos);
insertion = isl_union_map_empty(isl_union_map_get_space(options));
for (type = isl_ast_loop_atomic;
type <= isl_ast_loop_separate; ++type) {
isl_map *map_type = isl_map_copy(map);
const char *name = option_str[type];
map_type = isl_map_set_tuple_name(map_type, isl_dim_in, name);
map_type = isl_map_set_tuple_name(map_type, isl_dim_out, name);
insertion = isl_union_map_add_map(insertion, map_type);
}
map = isl_map_product(map, isl_map_identity(isl_map_get_space(map)));
map = isl_map_set_tuple_name(map, isl_dim_in, name);
map = isl_map_set_tuple_name(map, isl_dim_out, name);
insertion = isl_union_map_add_map(insertion, map);
options = isl_union_map_apply_range(options, insertion);
return options;
}
/* If we are generating an AST from a schedule tree (build->node is set),
* then update the loop AST generation types
* to reflect the insertion of a dimension at (global) position "pos"
* in the schedule domain space.
* We do not need to adjust any isolate option since we would not be inserting
* any dimensions if there were any isolate option.
*/
static __isl_give isl_ast_build *node_insert_dim(
__isl_take isl_ast_build *build, int pos)
{
int i;
int local_pos;
enum isl_ast_loop_type *loop_type;
isl_ctx *ctx;
build = isl_ast_build_cow(build);
if (!build)
return NULL;
if (!build->node)
return build;
ctx = isl_ast_build_get_ctx(build);
local_pos = pos - build->outer_pos;
loop_type = isl_realloc_array(ctx, build->loop_type,
enum isl_ast_loop_type, build->n + 1);
if (!loop_type)
return isl_ast_build_free(build);
build->loop_type = loop_type;
for (i = build->n - 1; i >= local_pos; --i)
loop_type[i + 1] = loop_type[i];
loop_type[local_pos] = isl_ast_loop_default;
build->n++;
return build;
}
/* Insert a single dimension in the schedule domain at position "pos".
* The new dimension is given an isl_id with the empty string as name.
*
* The main difficulty is updating build->options to reflect the
* extra dimension. This is handled in options_insert_dim.
*
* Note that because of the dimension manipulations, the resulting
* schedule domain space will always be unnamed and unstructured.
* However, the original schedule domain space may be named and/or
* structured, so we have to take this possibility into account
* while performing the transformations.
*
* Since the inserted schedule dimension is used by the caller
* to differentiate between different domain spaces, there is
* no longer a uniform mapping from the internal schedule space
* to the input schedule space. The internal2input mapping is
* therefore removed.
*/
__isl_give isl_ast_build *isl_ast_build_insert_dim(
__isl_take isl_ast_build *build, int pos)
{
isl_ctx *ctx;
isl_space *space, *ma_space;
isl_id *id;
isl_multi_aff *ma;
build = isl_ast_build_cow(build);
if (!build)
return NULL;
ctx = isl_ast_build_get_ctx(build);
id = isl_id_alloc(ctx, "", NULL);
if (!build->node)
space = isl_ast_build_get_space(build, 1);
build->iterators = isl_id_list_insert(build->iterators, pos, id);
build->domain = isl_set_insert_dims(build->domain,
isl_dim_set, pos, 1);
build->generated = isl_set_insert_dims(build->generated,
isl_dim_set, pos, 1);
build->pending = isl_set_insert_dims(build->pending,
isl_dim_set, pos, 1);
build->strides = isl_vec_insert_els(build->strides, pos, 1);
build->strides = isl_vec_set_element_si(build->strides, pos, 1);
ma_space = isl_space_params(isl_multi_aff_get_space(build->offsets));
ma_space = isl_space_set_from_params(ma_space);
ma_space = isl_space_add_dims(ma_space, isl_dim_set, 1);
ma_space = isl_space_map_from_set(ma_space);
ma = isl_multi_aff_zero(isl_space_copy(ma_space));
build->offsets = isl_multi_aff_splice(build->offsets, pos, pos, ma);
ma = isl_multi_aff_identity(ma_space);
build->values = isl_multi_aff_splice(build->values, pos, pos, ma);
if (!build->node)
build->options = options_insert_dim(build->options, space, pos);
build->internal2input = isl_multi_aff_free(build->internal2input);
if (!build->iterators || !build->domain || !build->generated ||
!build->pending || !build->values ||
!build->strides || !build->offsets || !build->options)
return isl_ast_build_free(build);
build = node_insert_dim(build, pos);
return build;
}
/* Scale down the current dimension by a factor of "m".
* "umap" is an isl_union_map that implements the scaling down.
* That is, it is of the form
*
* { [.... i ....] -> [.... i' ....] : i = m i' }
*
* This function is called right after the strides have been
* detected, but before any constraints on the current dimension
* have been included in build->domain.
* We therefore only need to update stride, offset, the options and
* the mapping from internal schedule space to the original schedule
* space, if we are still keeping track of such a mapping.
* The latter mapping is updated by plugging in
* { [... i ...] -> [... m i ... ] }.
*/
__isl_give isl_ast_build *isl_ast_build_scale_down(
__isl_take isl_ast_build *build, __isl_take isl_val *m,
__isl_take isl_union_map *umap)
{
isl_aff *aff;
isl_val *v;
int depth;
build = isl_ast_build_cow(build);
if (!build || !umap || !m)
goto error;
depth = build->depth;
if (build->internal2input) {
isl_space *space;
isl_multi_aff *ma;
isl_aff *aff;
space = isl_multi_aff_get_space(build->internal2input);
space = isl_space_map_from_set(isl_space_domain(space));
ma = isl_multi_aff_identity(space);
aff = isl_multi_aff_get_aff(ma, depth);
aff = isl_aff_scale_val(aff, isl_val_copy(m));
ma = isl_multi_aff_set_aff(ma, depth, aff);
build->internal2input =
isl_multi_aff_pullback_multi_aff(build->internal2input, ma);
if (!build->internal2input)
goto error;
}
v = isl_vec_get_element_val(build->strides, depth);
v = isl_val_div(v, isl_val_copy(m));
build->strides = isl_vec_set_element_val(build->strides, depth, v);
aff = isl_multi_aff_get_aff(build->offsets, depth);
aff = isl_aff_scale_down_val(aff, m);
build->offsets = isl_multi_aff_set_aff(build->offsets, depth, aff);
build->options = isl_union_map_apply_domain(build->options, umap);
if (!build->strides || !build->offsets || !build->options)
return isl_ast_build_free(build);
return build;
error:
isl_val_free(m);
isl_union_map_free(umap);
return isl_ast_build_free(build);
}
/* Return a list of "n" isl_ids called "c%d", with "%d" starting at "first".
* If an isl_id with such a name already appears among the parameters
* in build->domain, then adjust the name to "c%d_%d".
*/
static __isl_give isl_id_list *generate_names(isl_ctx *ctx, int n, int first,
__isl_keep isl_ast_build *build)
{
int i;
isl_id_list *names;
names = isl_id_list_alloc(ctx, n);
for (i = 0; i < n; ++i) {
isl_id *id;
id = generate_name(ctx, first + i, build);
names = isl_id_list_add(names, id);
}
return names;
}
/* Embed "options" into the given isl_ast_build space.
*
* This function is called from within a nested call to
* isl_ast_build_node_from_schedule_map.
* "options" refers to the additional schedule,
* while space refers to both the space of the outer isl_ast_build and
* that of the additional schedule.
* Specifically, space is of the form
*
* [I -> S]
*
* while options lives in the space(s)
*
* S -> *
*
* We compute
*
* [I -> S] -> S
*
* and compose this with options, to obtain the new options
* living in the space(s)
*
* [I -> S] -> *
*/
static __isl_give isl_union_map *embed_options(
__isl_take isl_union_map *options, __isl_take isl_space *space)
{
isl_map *map;
map = isl_map_universe(isl_space_unwrap(space));
map = isl_map_range_map(map);
options = isl_union_map_apply_range(
isl_union_map_from_map(map), options);
return options;
}
/* Update "build" for use in a (possibly nested) code generation. That is,
* extend "build" from an AST build on some domain O to an AST build
* on domain [O -> S], with S corresponding to "space".
* If the original domain is a parameter domain, then the new domain is
* simply S.
* "iterators" is a list of iterators for S, but the number of elements
* may be smaller or greater than the number of set dimensions of S.
* If "keep_iterators" is set, then any extra ids in build->iterators
* are reused for S. Otherwise, these extra ids are dropped.
*
* We first update build->outer_pos to the current depth.
* This depth is zero in case this is the outermost code generation.
*
* We then add additional ids such that the number of iterators is at least
* equal to the dimension of the new build domain.
*
* If the original domain is parametric, then we are constructing
* an isl_ast_build for the outer code generation and we pass control
* to isl_ast_build_init.
*
* Otherwise, we adjust the fields of "build" to include "space".
*/
__isl_give isl_ast_build *isl_ast_build_product(
__isl_take isl_ast_build *build, __isl_take isl_space *space)
{
isl_ctx *ctx;
isl_vec *strides;
isl_set *set;
isl_multi_aff *embedding;
isl_size dim, space_dim, n_it;
build = isl_ast_build_cow(build);
if (!build)
goto error;
build->outer_pos = build->depth;
ctx = isl_ast_build_get_ctx(build);
dim = isl_ast_build_dim(build, isl_dim_set);
space_dim = isl_space_dim(space, isl_dim_set);
n_it = isl_id_list_n_id(build->iterators);
if (dim < 0 || space_dim < 0 || n_it < 0)
goto error;
dim += space_dim;
if (n_it < dim) {
isl_id_list *l;
l = generate_names(ctx, dim - n_it, n_it, build);
build->iterators = isl_id_list_concat(build->iterators, l);
}
if (isl_set_is_params(build->domain))
return isl_ast_build_init(build, space);
set = isl_set_universe(isl_space_copy(space));
build->domain = isl_set_product(build->domain, isl_set_copy(set));
build->pending = isl_set_product(build->pending, isl_set_copy(set));
build->generated = isl_set_product(build->generated, set);
strides = isl_vec_alloc(ctx, space_dim);
strides = isl_vec_set_si(strides, 1);
build->strides = isl_vec_concat(build->strides, strides);
space = isl_space_map_from_set(space);
build->offsets = isl_multi_aff_align_params(build->offsets,
isl_space_copy(space));
build->offsets = isl_multi_aff_product(build->offsets,
isl_multi_aff_zero(isl_space_copy(space)));
build->values = isl_multi_aff_align_params(build->values,
isl_space_copy(space));
embedding = isl_multi_aff_identity(space);
build->values = isl_multi_aff_product(build->values,
isl_multi_aff_copy(embedding));
if (build->internal2input) {
build->internal2input =
isl_multi_aff_product(build->internal2input, embedding);
build->internal2input =
isl_multi_aff_flatten_range(build->internal2input);
if (!build->internal2input)
return isl_ast_build_free(build);
} else {
isl_multi_aff_free(embedding);
}
space = isl_ast_build_get_space(build, 1);
build->options = embed_options(build->options, space);
if (!build->iterators || !build->domain || !build->generated ||
!build->pending || !build->values ||
!build->strides || !build->offsets || !build->options)
return isl_ast_build_free(build);
return build;
error:
isl_ast_build_free(build);
isl_space_free(space);
return NULL;
}
/* Does "aff" only attain non-negative values over build->domain?
* That is, does it not attain any negative values?
*/
int isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build *build,
__isl_keep isl_aff *aff)
{
isl_set *test;
int empty;
if (!build)
return -1;
aff = isl_aff_copy(aff);
test = isl_set_from_basic_set(isl_aff_neg_basic_set(aff));
test = isl_set_intersect(test, isl_set_copy(build->domain));
empty = isl_set_is_empty(test);
isl_set_free(test);
return empty;
}
/* Does the dimension at (internal) position "pos" have a non-trivial stride?
*/
isl_bool isl_ast_build_has_stride(__isl_keep isl_ast_build *build, int pos)
{
isl_val *v;
isl_bool has_stride;
if (!build)
return isl_bool_error;
v = isl_vec_get_element_val(build->strides, pos);
has_stride = isl_bool_not(isl_val_is_one(v));
isl_val_free(v);
return has_stride;
}
/* Given that the dimension at position "pos" takes on values
*
* f + s a
*
* with a an integer, return s through *stride.
*/
__isl_give isl_val *isl_ast_build_get_stride(__isl_keep isl_ast_build *build,
int pos)
{
if (!build)
return NULL;
return isl_vec_get_element_val(build->strides, pos);
}
/* Given that the dimension at position "pos" takes on values
*
* f + s a
*
* with a an integer, return f.
*/
__isl_give isl_aff *isl_ast_build_get_offset(
__isl_keep isl_ast_build *build, int pos)
{
if (!build)
return NULL;
return isl_multi_aff_get_aff(build->offsets, pos);
}
/* Is the dimension at position "pos" known to attain only a single
* value that, moreover, can be described by a single affine expression
* in terms of the outer dimensions and parameters?
*
* If not, then the corresponding affine expression in build->values
* is set to be equal to the same input dimension.
* Otherwise, it is set to the requested expression in terms of
* outer dimensions and parameters.
*/
isl_bool isl_ast_build_has_affine_value(__isl_keep isl_ast_build *build,
int pos)
{
isl_aff *aff;
isl_bool involves;
if (!build)
return isl_bool_error;
aff = isl_multi_aff_get_aff(build->values, pos);
involves = isl_aff_involves_dims(aff, isl_dim_in, pos, 1);
isl_aff_free(aff);
return isl_bool_not(involves);
}
/* Plug in the known values (fixed affine expressions in terms of
* parameters and outer loop iterators) of all loop iterators
* in the domain of "umap".
*
* We simply precompose "umap" with build->values.
*/
__isl_give isl_union_map *isl_ast_build_substitute_values_union_map_domain(
__isl_keep isl_ast_build *build, __isl_take isl_union_map *umap)
{
isl_multi_aff *values;
if (!build)
return isl_union_map_free(umap);
values = isl_multi_aff_copy(build->values);
umap = isl_union_map_preimage_domain_multi_aff(umap, values);
return umap;
}
/* Is the current dimension known to attain only a single value?
*/
int isl_ast_build_has_value(__isl_keep isl_ast_build *build)
{
if (!build)
return -1;
return build->value != NULL;
}
/* Simplify the basic set "bset" based on what we know about
* the iterators of already generated loops.
*
* "bset" is assumed to live in the (internal) schedule domain.
*/
__isl_give isl_basic_set *isl_ast_build_compute_gist_basic_set(
__isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)
{
if (!build)
goto error;
bset = isl_basic_set_preimage_multi_aff(bset,
isl_multi_aff_copy(build->values));
bset = isl_basic_set_gist(bset,
isl_set_simple_hull(isl_set_copy(build->domain)));
return bset;
error:
isl_basic_set_free(bset);
return NULL;
}
/* Simplify the set "set" based on what we know about
* the iterators of already generated loops.
*
* "set" is assumed to live in the (internal) schedule domain.
*/
__isl_give isl_set *isl_ast_build_compute_gist(
__isl_keep isl_ast_build *build, __isl_take isl_set *set)
{
if (!build)
goto error;
if (!isl_set_is_params(set))
set = isl_set_preimage_multi_aff(set,
isl_multi_aff_copy(build->values));
set = isl_set_gist(set, isl_set_copy(build->domain));
return set;
error:
isl_set_free(set);
return NULL;
}
/* Include information about what we know about the iterators of
* already generated loops to "set".
*
* We currently only plug in the known affine values of outer loop
* iterators.
* In principle we could also introduce equalities or even other
* constraints implied by the intersection of "set" and build->domain.
*/
__isl_give isl_set *isl_ast_build_specialize(__isl_keep isl_ast_build *build,
__isl_take isl_set *set)
{
if (!build)
return isl_set_free(set);
return isl_set_preimage_multi_aff(set,
isl_multi_aff_copy(build->values));
}
/* Plug in the known affine values of outer loop iterators in "bset".
*/
__isl_give isl_basic_set *isl_ast_build_specialize_basic_set(
__isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)
{
if (!build)
return isl_basic_set_free(bset);
return isl_basic_set_preimage_multi_aff(bset,
isl_multi_aff_copy(build->values));
}
/* Simplify the map "map" based on what we know about
* the iterators of already generated loops.
*
* The domain of "map" is assumed to live in the (internal) schedule domain.
*/
__isl_give isl_map *isl_ast_build_compute_gist_map_domain(
__isl_keep isl_ast_build *build, __isl_take isl_map *map)
{
if (!build)
goto error;
map = isl_map_gist_domain(map, isl_set_copy(build->domain));
return map;
error:
isl_map_free(map);
return NULL;
}
/* Simplify the affine expression "aff" based on what we know about
* the iterators of already generated loops.
*
* The domain of "aff" is assumed to live in the (internal) schedule domain.
*/
__isl_give isl_aff *isl_ast_build_compute_gist_aff(
__isl_keep isl_ast_build *build, __isl_take isl_aff *aff)
{
if (!build)
goto error;
aff = isl_aff_gist(aff, isl_set_copy(build->domain));
return aff;
error:
isl_aff_free(aff);
return NULL;
}
/* Simplify the piecewise affine expression "aff" based on what we know about
* the iterators of already generated loops.
*
* The domain of "pa" is assumed to live in the (internal) schedule domain.
*/
__isl_give isl_pw_aff *isl_ast_build_compute_gist_pw_aff(
__isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
{
if (!build)
goto error;
if (!isl_set_is_params(build->domain))
pa = isl_pw_aff_pullback_multi_aff(pa,
isl_multi_aff_copy(build->values));
pa = isl_pw_aff_gist(pa, isl_set_copy(build->domain));
return pa;
error:
isl_pw_aff_free(pa);
return NULL;
}
/* Simplify the piecewise multi-affine expression "aff" based on what
* we know about the iterators of already generated loops.
*
* The domain of "pma" is assumed to live in the (internal) schedule domain.
*/
__isl_give isl_pw_multi_aff *isl_ast_build_compute_gist_pw_multi_aff(
__isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
{
if (!build)
goto error;
pma = isl_pw_multi_aff_pullback_multi_aff(pma,
isl_multi_aff_copy(build->values));
pma = isl_pw_multi_aff_gist(pma, isl_set_copy(build->domain));
return pma;
error:
isl_pw_multi_aff_free(pma);
return NULL;
}
/* Extract the schedule domain of the given type from build->options
* at the current depth.
*
* In particular, find the subset of build->options that is of
* the following form
*
* schedule_domain -> type[depth]
*
* and return the corresponding domain, after eliminating inner dimensions
* and divs that depend on the current dimension.
*
* Note that the domain of build->options has been reformulated
* in terms of the internal build space in embed_options,
* but the position is still that within the current code generation.
*/
__isl_give isl_set *isl_ast_build_get_option_domain(
__isl_keep isl_ast_build *build, enum isl_ast_loop_type type)
{
const char *name;
isl_space *space;
isl_map *option;
isl_set *domain;
int local_pos;
if (!build)
return NULL;
name = option_str[type];
local_pos = build->depth - build->outer_pos;
space = isl_ast_build_get_space(build, 1);
space = isl_space_from_domain(space);
space = isl_space_add_dims(space, isl_dim_out, 1);
space = isl_space_set_tuple_name(space, isl_dim_out, name);
option = isl_union_map_extract_map(build->options, space);
option = isl_map_fix_si(option, isl_dim_out, 0, local_pos);
domain = isl_map_domain(option);
domain = isl_ast_build_eliminate(build, domain);
return domain;
}
/* How does the user want the current schedule dimension to be generated?
* These choices have been extracted from the schedule node
* in extract_loop_types and stored in build->loop_type.
* They have been updated to reflect any dimension insertion in
* node_insert_dim.
* Return isl_ast_domain_error on error.
*
* If "isolated" is set, then we get the loop AST generation type
* directly from the band node since node_insert_dim cannot have been
* called on a band with the isolate option.
*/
enum isl_ast_loop_type isl_ast_build_get_loop_type(
__isl_keep isl_ast_build *build, int isolated)
{
int local_pos;
isl_ctx *ctx;
if (!build)
return isl_ast_loop_error;
ctx = isl_ast_build_get_ctx(build);
if (!build->node)
isl_die(ctx, isl_error_internal,
"only works for schedule tree based AST generation",
return isl_ast_loop_error);
local_pos = build->depth - build->outer_pos;
if (!isolated)
return build->loop_type[local_pos];
return isl_schedule_node_band_member_get_isolate_ast_loop_type(
build->node, local_pos);
}
/* Extract the isolated set from the isolate option, if any,
* and store in the build.
* If there is no isolate option, then the isolated set is
* set to the empty set.
*
* The isolate option is of the form
*
* isolate[[outer bands] -> current_band]
*
* We flatten this set and then map it back to the internal
* schedule space.
*
* If we have already extracted the isolated set
* or if internal2input is no longer set, then we do not
* need to do anything. In the latter case, we know
* that the current band cannot have any isolate option.
*/
__isl_give isl_ast_build *isl_ast_build_extract_isolated(
__isl_take isl_ast_build *build)
{
isl_set *isolated;
if (!build)
return NULL;
if (!build->internal2input)
return build;
if (build->isolated)
return build;
build = isl_ast_build_cow(build);
if (!build)
return NULL;
isolated = isl_schedule_node_band_get_ast_isolate_option(build->node);
isolated = isl_set_flatten(isolated);
isolated = isl_set_preimage_multi_aff(isolated,
isl_multi_aff_copy(build->internal2input));
build->isolated = isolated;
if (!build->isolated)
return isl_ast_build_free(build);
return build;
}
/* Does "build" have a non-empty isolated set?
*
* The caller is assumed to have called isl_ast_build_extract_isolated first.
*/
int isl_ast_build_has_isolated(__isl_keep isl_ast_build *build)
{
int empty;
if (!build)
return -1;
if (!build->internal2input)
return 0;
if (!build->isolated)
isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
"isolated set not extracted yet", return -1);
empty = isl_set_plain_is_empty(build->isolated);
return empty < 0 ? -1 : !empty;
}
/* Return a copy of the isolated set of "build".
*
* The caller is assume to have called isl_ast_build_has_isolated first,
* with this function returning true.
* In particular, this function should not be called if we are no
* longer keeping track of internal2input (and there therefore could
* not possibly be any isolated set).
*/
__isl_give isl_set *isl_ast_build_get_isolated(__isl_keep isl_ast_build *build)
{
if (!build)
return NULL;
if (!build->internal2input)
isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
"build cannot have isolated set", return NULL);
return isl_set_copy(build->isolated);
}
/* Extract the separation class mapping at the current depth.
*
* In particular, find and return the subset of build->options that is of
* the following form
*
* schedule_domain -> separation_class[[depth] -> [class]]
*
* The caller is expected to eliminate inner dimensions from the domain.
*
* Note that the domain of build->options has been reformulated
* in terms of the internal build space in embed_options,
* but the position is still that within the current code generation.
*/
__isl_give isl_map *isl_ast_build_get_separation_class(
__isl_keep isl_ast_build *build)
{
isl_ctx *ctx;
isl_space *space_sep, *space;
isl_map *res;
int local_pos;
if (!build)
return NULL;
local_pos = build->depth - build->outer_pos;
ctx = isl_ast_build_get_ctx(build);
space_sep = isl_space_alloc(ctx, 0, 1, 1);
space_sep = isl_space_wrap(space_sep);
space_sep = isl_space_set_tuple_name(space_sep, isl_dim_set,
"separation_class");
space = isl_ast_build_get_space(build, 1);
space_sep = isl_space_align_params(space_sep, isl_space_copy(space));
space = isl_space_map_from_domain_and_range(space, space_sep);
res = isl_union_map_extract_map(build->options, space);
res = isl_map_fix_si(res, isl_dim_out, 0, local_pos);
res = isl_map_coalesce(res);
return res;
}
/* Eliminate dimensions inner to the current dimension.
*/
__isl_give isl_set *isl_ast_build_eliminate_inner(
__isl_keep isl_ast_build *build, __isl_take isl_set *set)
{
int dim;
int depth;
if (!build)
return isl_set_free(set);
dim = isl_set_dim(set, isl_dim_set);
depth = build->depth;
set = isl_set_detect_equalities(set);
set = isl_set_eliminate(set, isl_dim_set, depth + 1, dim - (depth + 1));
return set;
}
/* Eliminate unknown divs and divs that depend on the current dimension.
*
* Note that during the elimination of unknown divs, we may discover
* an explicit representation of some other unknown divs, which may
* depend on the current dimension. We therefore need to eliminate
* unknown divs first.
*/
__isl_give isl_set *isl_ast_build_eliminate_divs(
__isl_keep isl_ast_build *build, __isl_take isl_set *set)
{
int depth;
if (!build)
return isl_set_free(set);
set = isl_set_remove_unknown_divs(set);
depth = build->depth;
set = isl_set_remove_divs_involving_dims(set, isl_dim_set, depth, 1);
return set;
}
/* Eliminate dimensions inner to the current dimension as well as
* unknown divs and divs that depend on the current dimension.
* The result then consists only of constraints that are independent
* of the current dimension and upper and lower bounds on the current
* dimension.
*/
__isl_give isl_set *isl_ast_build_eliminate(
__isl_keep isl_ast_build *build, __isl_take isl_set *domain)
{
domain = isl_ast_build_eliminate_inner(build, domain);
domain = isl_ast_build_eliminate_divs(build, domain);
return domain;
}
/* Replace build->single_valued by "sv".
*/
__isl_give isl_ast_build *isl_ast_build_set_single_valued(
__isl_take isl_ast_build *build, int sv)
{
if (!build)
return build;
if (build->single_valued == sv)
return build;
build = isl_ast_build_cow(build);
if (!build)
return build;
build->single_valued = sv;
return build;
}
|
