/* * Copyright 2011 INRIA Saclay * Copyright 2012-2014 Ecole Normale Superieure * Copyright 2015-2016 Sven Verdoolaege * Copyright 2016 INRIA Paris * Copyright 2017 Sven Verdoolaege * * Use of this software is governed by the MIT license * * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France, * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod, * 91893 Orsay, France * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France * and Centre de Recherche Inria de Paris, 2 rue Simone Iff - Voie DQ12, * CS 42112, 75589 Paris Cedex 12, France */ #include <isl_ctx_private.h> #include <isl_map_private.h> #include <isl_space_private.h> #include <isl_aff_private.h> #include <isl/hash.h> #include <isl/id.h> #include <isl/constraint.h> #include <isl/schedule.h> #include <isl_schedule_constraints.h> #include <isl/schedule_node.h> #include <isl_mat_private.h> #include <isl_vec_private.h> #include <isl/set.h> #include <isl_union_set_private.h> #include <isl_seq.h> #include <isl_tab.h> #include <isl_dim_map.h> #include <isl/map_to_basic_set.h> #include <isl_sort.h> #include <isl_options_private.h> #include <isl_tarjan.h> #include <isl_morph.h> #include <isl/ilp.h> #include <isl_val_private.h> #include "isl_scheduler.h" #include "isl_scheduler_clustering.h" /* * The scheduling algorithm implemented in this file was inspired by * Bondhugula et al., "Automatic Transformations for Communication-Minimized * Parallelization and Locality Optimization in the Polyhedral Model". * * For a detailed description of the variant implemented in isl, * see Verdoolaege and Janssens, "Scheduling for PPCG" (2017). */ static isl_bool node_has_tuples(const void *entry, const void *val) { … } int isl_sched_node_scc_exactly(struct isl_sched_node *node, int scc) { … } static int node_scc_at_most(struct isl_sched_node *node, int scc) { … } static int node_scc_at_least(struct isl_sched_node *node, int scc) { … } /* Is "edge" marked as being of type "type"? */ int isl_sched_edge_has_type(struct isl_sched_edge *edge, enum isl_edge_type type) { … } /* Mark "edge" as being of type "type". */ static void set_type(struct isl_sched_edge *edge, enum isl_edge_type type) { … } /* No longer mark "edge" as being of type "type"? */ static void clear_type(struct isl_sched_edge *edge, enum isl_edge_type type) { … } /* Is "edge" marked as a validity edge? */ static int is_validity(struct isl_sched_edge *edge) { … } /* Mark "edge" as a validity edge. */ static void set_validity(struct isl_sched_edge *edge) { … } /* Is "edge" marked as a proximity edge? */ int isl_sched_edge_is_proximity(struct isl_sched_edge *edge) { … } /* Is "edge" marked as a local edge? */ static int is_local(struct isl_sched_edge *edge) { … } /* Mark "edge" as a local edge. */ static void set_local(struct isl_sched_edge *edge) { … } /* No longer mark "edge" as a local edge. */ static void clear_local(struct isl_sched_edge *edge) { … } /* Is "edge" marked as a coincidence edge? */ static int is_coincidence(struct isl_sched_edge *edge) { … } /* Is "edge" marked as a condition edge? */ int isl_sched_edge_is_condition(struct isl_sched_edge *edge) { … } /* Is "edge" marked as a conditional validity edge? */ int isl_sched_edge_is_conditional_validity(struct isl_sched_edge *edge) { … } /* Is "edge" of a type that can appear multiple times between * the same pair of nodes? * * Condition edges and conditional validity edges may have tagged * dependence relations, in which case an edge is added for each * pair of tags. */ static int is_multi_edge_type(struct isl_sched_edge *edge) { … } /* Initialize node_table based on the list of nodes. */ static int graph_init_table(isl_ctx *ctx, struct isl_sched_graph *graph) { … } /* Return a pointer to the node that lives within the given space, * an invalid node if there is no such node, or NULL in case of error. */ struct isl_sched_node *isl_sched_graph_find_node(isl_ctx *ctx, struct isl_sched_graph *graph, __isl_keep isl_space *space) { … } /* Is "node" a node in "graph"? */ int isl_sched_graph_is_node(struct isl_sched_graph *graph, struct isl_sched_node *node) { … } static isl_bool edge_has_src_and_dst(const void *entry, const void *val) { … } /* Add the given edge to graph->edge_table[type]. */ static isl_stat graph_edge_table_add(isl_ctx *ctx, struct isl_sched_graph *graph, enum isl_edge_type type, struct isl_sched_edge *edge) { … } /* Add "edge" to all relevant edge tables. * That is, for every type of the edge, add it to the corresponding table. */ static isl_stat graph_edge_tables_add(isl_ctx *ctx, struct isl_sched_graph *graph, struct isl_sched_edge *edge) { … } /* Allocate the edge_tables based on the maximal number of edges of * each type. */ static int graph_init_edge_tables(isl_ctx *ctx, struct isl_sched_graph *graph) { … } /* If graph->edge_table[type] contains an edge from the given source * to the given destination, then return the hash table entry of this edge. * Otherwise, return NULL. */ static struct isl_hash_table_entry *graph_find_edge_entry( struct isl_sched_graph *graph, enum isl_edge_type type, struct isl_sched_node *src, struct isl_sched_node *dst) { … } /* If graph->edge_table[type] contains an edge from the given source * to the given destination, then return this edge. * Return "none" if no such edge can be found. * Return NULL on error. */ static struct isl_sched_edge *graph_find_edge(struct isl_sched_graph *graph, enum isl_edge_type type, struct isl_sched_node *src, struct isl_sched_node *dst, struct isl_sched_edge *none) { … } /* Check whether the dependence graph has an edge of the given type * between the given two nodes. */ static isl_bool graph_has_edge(struct isl_sched_graph *graph, enum isl_edge_type type, struct isl_sched_node *src, struct isl_sched_node *dst) { … } /* Look for any edge with the same src, dst and map fields as "model". * * Return the matching edge if one can be found. * Return "model" if no matching edge is found. * Return NULL on error. */ static struct isl_sched_edge *graph_find_matching_edge( struct isl_sched_graph *graph, struct isl_sched_edge *model) { … } /* Remove the given edge from all the edge_tables that refer to it. */ static isl_stat graph_remove_edge(struct isl_sched_graph *graph, struct isl_sched_edge *edge) { … } /* Check whether the dependence graph has any edge * between the given two nodes. */ static isl_bool graph_has_any_edge(struct isl_sched_graph *graph, struct isl_sched_node *src, struct isl_sched_node *dst) { … } /* Check whether the dependence graph has a validity edge * between the given two nodes. * * Conditional validity edges are essentially validity edges that * can be ignored if the corresponding condition edges are iteration private. * Here, we are only checking for the presence of validity * edges, so we need to consider the conditional validity edges too. * In particular, this function is used during the detection * of strongly connected components and we cannot ignore * conditional validity edges during this detection. */ isl_bool isl_sched_graph_has_validity_edge(struct isl_sched_graph *graph, struct isl_sched_node *src, struct isl_sched_node *dst) { … } /* Perform all the required memory allocations for a schedule graph "graph" * with "n_node" nodes and "n_edge" edge and initialize the corresponding * fields. */ static isl_stat graph_alloc(isl_ctx *ctx, struct isl_sched_graph *graph, int n_node, int n_edge) { … } /* Free the memory associated to node "node" in "graph". * The "coincident" field is shared by nodes in a graph and its subgraph. * It therefore only needs to be freed for the original dependence graph, * i.e., one that is not the result of splitting. */ static void clear_node(struct isl_sched_graph *graph, struct isl_sched_node *node) { … } void isl_sched_graph_free(isl_ctx *ctx, struct isl_sched_graph *graph) { … } /* For each "set" on which this function is called, increment * graph->n by one and update graph->maxvar. */ static isl_stat init_n_maxvar(__isl_take isl_set *set, void *user) { … } /* Compute the number of rows that should be allocated for the schedule. * In particular, we need one row for each variable or one row * for each basic map in the dependences. * Note that it is practically impossible to exhaust both * the number of dependences and the number of variables. */ static isl_stat compute_max_row(struct isl_sched_graph *graph, __isl_keep isl_schedule_constraints *sc) { … } /* Does "bset" have any defining equalities for its set variables? */ static isl_bool has_any_defining_equality(__isl_keep isl_basic_set *bset) { … } /* Set the entries of node->max to the value of the schedule_max_coefficient * option, if set. */ static isl_stat set_max_coefficient(isl_ctx *ctx, struct isl_sched_node *node) { … } /* Set the entries of node->max to the minimum of the schedule_max_coefficient * option (if set) and half of the minimum of the sizes in the other * dimensions. Round up when computing the half such that * if the minimum of the sizes is one, half of the size is taken to be one * rather than zero. * If the global minimum is unbounded (i.e., if both * the schedule_max_coefficient is not set and the sizes in the other * dimensions are unbounded), then store a negative value. * If the schedule coefficient is close to the size of the instance set * in another dimension, then the schedule may represent a loop * coalescing transformation (especially if the coefficient * in that other dimension is one). Forcing the coefficient to be * smaller than or equal to half the minimal size should avoid this * situation. */ static isl_stat compute_max_coefficient(isl_ctx *ctx, struct isl_sched_node *node) { … } /* Construct an identifier for node "node", which will represent "set". * The name of the identifier is either "compressed" or * "compressed_<name>", with <name> the name of the space of "set". * The user pointer of the identifier points to "node". */ static __isl_give isl_id *construct_compressed_id(__isl_keep isl_set *set, struct isl_sched_node *node) { … } /* Construct a map that isolates the variable in position "pos" in "set". * * That is, construct * * [i_0, ..., i_pos-1, i_pos+1, ...] -> [i_pos] */ static __isl_give isl_map *isolate(__isl_take isl_set *set, int pos) { … } /* Compute and return the size of "set" in dimension "dim". * The size is taken to be the difference in values for that variable * for fixed values of the other variables. * This assumes that "set" is convex. * In particular, the variable is first isolated from the other variables * in the range of a map * * [i_0, ..., i_dim-1, i_dim+1, ...] -> [i_dim] * * and then duplicated * * [i_0, ..., i_dim-1, i_dim+1, ...] -> [[i_dim] -> [i_dim']] * * The shared variables are then projected out and the maximal value * of i_dim' - i_dim is computed. */ static __isl_give isl_val *compute_size(__isl_take isl_set *set, int dim) { … } /* Perform a compression on "node" where "hull" represents the constraints * that were used to derive the compression, while "compress" and * "decompress" map the original space to the compressed space and * vice versa. * * If "node" was not compressed already, then simply store * the compression information. * Otherwise the "original" space is actually the result * of a previous compression, which is then combined * with the present compression. * * The dimensionality of the compressed domain is also adjusted. * Other information, such as the sizes and the maximal coefficient values, * has not been computed yet and therefore does not need to be adjusted. */ static isl_stat compress_node(struct isl_sched_node *node, __isl_take isl_set *hull, __isl_take isl_multi_aff *compress, __isl_take isl_pw_multi_aff *decompress) { … } /* Given that dimension "pos" in "set" has a fixed value * in terms of the other dimensions, (further) compress "node" * by projecting out this dimension. * "set" may be the result of a previous compression. * "uncompressed" is the original domain (without compression). * * The compression function simply projects out the dimension. * The decompression function adds back the dimension * in the right position as an expression of the other dimensions * derived from "set". * As in extract_node, the compressed space has an identifier * that references "node" such that each compressed space is unique and * such that the node can be recovered from the compressed space. * * The constraint removed through the compression is added to the "hull" * such that only edges that relate to the original domains * are taken into account. * In particular, it is obtained by composing compression and decompression and * taking the relation among the variables in the range. */ static isl_stat project_out_fixed(struct isl_sched_node *node, __isl_keep isl_set *uncompressed, __isl_take isl_set *set, int pos) { … } /* Compute the size of the compressed domain in each dimension and * store the results in node->sizes. * "uncompressed" is the original domain (without compression). * * First compress the domain if needed and then compute the size * in each direction. * If the domain is not convex, then the sizes are computed * on a convex superset in order to avoid picking up sizes * that are valid for the individual disjuncts, but not for * the domain as a whole. * * If any of the sizes turns out to be zero, then this means * that this dimension has a fixed value in terms of * the other dimensions. Perform an (extra) compression * to remove this dimension. */ static isl_stat compute_sizes(struct isl_sched_node *node, __isl_keep isl_set *uncompressed) { … } /* Compute the size of the instance set "set" of "node", after compression, * as well as bounds on the corresponding coefficients, if needed. * * The sizes are needed when the schedule_treat_coalescing option is set. * The bounds are needed when the schedule_treat_coalescing option or * the schedule_max_coefficient option is set. * * If the schedule_treat_coalescing option is not set, then at most * the bounds need to be set and this is done in set_max_coefficient. * Otherwise, compute the size of the compressed domain * in each direction and store the results in node->size. * Finally, set the bounds on the coefficients based on the sizes * and the schedule_max_coefficient option in compute_max_coefficient. */ static isl_stat compute_sizes_and_max(isl_ctx *ctx, struct isl_sched_node *node, __isl_take isl_set *set) { … } /* Add a new node to the graph representing the given instance set. * "nvar" is the (possibly compressed) number of variables and * may be smaller than then number of set variables in "set" * if "compressed" is set. * If "compressed" is set, then "hull" represents the constraints * that were used to derive the compression, while "compress" and * "decompress" map the original space to the compressed space and * vice versa. * If "compressed" is not set, then "hull", "compress" and "decompress" * should be NULL. * * Compute the size of the instance set and bounds on the coefficients, * if needed. */ static isl_stat add_node(struct isl_sched_graph *graph, __isl_take isl_set *set, int nvar, int compressed, __isl_take isl_set *hull, __isl_take isl_multi_aff *compress, __isl_take isl_pw_multi_aff *decompress) { … } /* Add a new node to the graph representing the given set. * * If any of the set variables is defined by an equality, then * we perform variable compression such that we can perform * the scheduling on the compressed domain. * In this case, an identifier is used that references the new node * such that each compressed space is unique and * such that the node can be recovered from the compressed space. */ static isl_stat extract_node(__isl_take isl_set *set, void *user) { … } struct isl_extract_edge_data { … }; /* Merge edge2 into edge1, freeing the contents of edge2. * Return 0 on success and -1 on failure. * * edge1 and edge2 are assumed to have the same value for the map field. */ static int merge_edge(struct isl_sched_edge *edge1, struct isl_sched_edge *edge2) { … } /* Insert dummy tags in domain and range of "map". * * In particular, if "map" is of the form * * A -> B * * then return * * [A -> dummy_tag] -> [B -> dummy_tag] * * where the dummy_tags are identical and equal to any dummy tags * introduced by any other call to this function. */ static __isl_give isl_map *insert_dummy_tags(__isl_take isl_map *map) { … } /* Given that at least one of "src" or "dst" is compressed, return * a map between the spaces of these nodes restricted to the affine * hull that was used in the compression. */ static __isl_give isl_map *extract_hull(struct isl_sched_node *src, struct isl_sched_node *dst) { … } /* Intersect the domains of the nested relations in domain and range * of "tagged" with "map". */ static __isl_give isl_map *map_intersect_domains(__isl_take isl_map *tagged, __isl_keep isl_map *map) { … } /* Return a pointer to the node that lives in the domain space of "map", * an invalid node if there is no such node, or NULL in case of error. */ static struct isl_sched_node *find_domain_node(isl_ctx *ctx, struct isl_sched_graph *graph, __isl_keep isl_map *map) { … } /* Return a pointer to the node that lives in the range space of "map", * an invalid node if there is no such node, or NULL in case of error. */ static struct isl_sched_node *find_range_node(isl_ctx *ctx, struct isl_sched_graph *graph, __isl_keep isl_map *map) { … } /* Refrain from adding a new edge based on "map". * Instead, just free the map. * "tagged" is either a copy of "map" with additional tags or NULL. */ static isl_stat skip_edge(__isl_take isl_map *map, __isl_take isl_map *tagged) { … } /* Add a new edge to the graph based on the given map * and add it to data->graph->edge_table[data->type]. * If a dependence relation of a given type happens to be identical * to one of the dependence relations of a type that was added before, * then we don't create a new edge, but instead mark the original edge * as also representing a dependence of the current type. * * Edges of type isl_edge_condition or isl_edge_conditional_validity * may be specified as "tagged" dependence relations. That is, "map" * may contain elements (i -> a) -> (j -> b), where i -> j denotes * the dependence on iterations and a and b are tags. * edge->map is set to the relation containing the elements i -> j, * while edge->tagged_condition and edge->tagged_validity contain * the union of all the "map" relations * for which extract_edge is called that result in the same edge->map. * * If the source or the destination node is compressed, then * intersect both "map" and "tagged" with the constraints that * were used to construct the compression. * This ensures that there are no schedule constraints defined * outside of these domains, while the scheduler no longer has * any control over those outside parts. */ static isl_stat extract_edge(__isl_take isl_map *map, void *user) { … } /* Initialize the schedule graph "graph" from the schedule constraints "sc". * * The context is included in the domain before the nodes of * the graphs are extracted in order to be able to exploit * any possible additional equalities. * Note that this intersection is only performed locally here. */ isl_stat isl_sched_graph_init(struct isl_sched_graph *graph, __isl_keep isl_schedule_constraints *sc) { … } /* Check whether there is any dependence from node[j] to node[i] * or from node[i] to node[j]. */ static isl_bool node_follows_weak(int i, int j, void *user) { … } /* Check whether there is a (conditional) validity dependence from node[j] * to node[i], forcing node[i] to follow node[j]. */ static isl_bool node_follows_strong(int i, int j, void *user) { … } /* Use Tarjan's algorithm for computing the strongly connected components * in the dependence graph only considering those edges defined by "follows". */ isl_stat isl_sched_graph_detect_ccs(isl_ctx *ctx, struct isl_sched_graph *graph, isl_bool (*follows)(int i, int j, void *user)) { … } /* Apply Tarjan's algorithm to detect the strongly connected components * in the dependence graph. * Only consider the (conditional) validity dependences and clear "weak". */ static isl_stat detect_sccs(isl_ctx *ctx, struct isl_sched_graph *graph) { … } /* Apply Tarjan's algorithm to detect the (weakly) connected components * in the dependence graph. * Consider all dependences and set "weak". */ static isl_stat detect_wccs(isl_ctx *ctx, struct isl_sched_graph *graph) { … } static int cmp_scc(const void *a, const void *b, void *data) { … } /* Sort the elements of graph->sorted according to the corresponding SCCs. */ static int sort_sccs(struct isl_sched_graph *graph) { … } /* Return a non-parametric set in the compressed space of "node" that is * bounded by the size in each direction * * { [x] : -S_i <= x_i <= S_i } * * If S_i is infinity in direction i, then there are no constraints * in that direction. * * Cache the result in node->bounds. */ static __isl_give isl_basic_set *get_size_bounds(struct isl_sched_node *node) { … } /* Compress the dependence relation "map", if needed, i.e., * when the source node "src" and/or the destination node "dst" * has been compressed. */ static __isl_give isl_map *compress(__isl_take isl_map *map, struct isl_sched_node *src, struct isl_sched_node *dst) { … } /* Drop some constraints from "delta" that could be exploited * to construct loop coalescing schedules. * In particular, drop those constraint that bound the difference * to the size of the domain. * First project out the parameters to improve the effectiveness. */ static __isl_give isl_set *drop_coalescing_constraints( __isl_take isl_set *delta, struct isl_sched_node *node) { … } /* Given a dependence relation R from "node" to itself, * construct the set of coefficients of valid constraints for elements * in that dependence relation. * In particular, the result contains tuples of coefficients * c_0, c_n, c_x such that * * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R * * or, equivalently, * * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R } * * We choose here to compute the dual of delta R. * Alternatively, we could have computed the dual of R, resulting * in a set of tuples c_0, c_n, c_x, c_y, and then * plugged in (c_0, c_n, c_x, -c_x). * * If "need_param" is set, then the resulting coefficients effectively * include coefficients for the parameters c_n. Otherwise, they may * have been projected out already. * Since the constraints may be different for these two cases, * they are stored in separate caches. * In particular, if no parameter coefficients are required and * the schedule_treat_coalescing option is set, then the parameters * are projected out and some constraints that could be exploited * to construct coalescing schedules are removed before the dual * is computed. * * If "node" has been compressed, then the dependence relation * is also compressed before the set of coefficients is computed. */ static __isl_give isl_basic_set *intra_coefficients( struct isl_sched_graph *graph, struct isl_sched_node *node, __isl_take isl_map *map, int need_param) { … } /* Given a dependence relation R, construct the set of coefficients * of valid constraints for elements in that dependence relation. * In particular, the result contains tuples of coefficients * c_0, c_n, c_x, c_y such that * * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R * * If the source or destination nodes of "edge" have been compressed, * then the dependence relation is also compressed before * the set of coefficients is computed. */ static __isl_give isl_basic_set *inter_coefficients( struct isl_sched_graph *graph, struct isl_sched_edge *edge, __isl_take isl_map *map) { … } /* Return the position of the coefficients of the variables in * the coefficients constraints "coef". * * The space of "coef" is of the form * * { coefficients[[cst, params] -> S] } * * Return the position of S. */ static isl_size coef_var_offset(__isl_keep isl_basic_set *coef) { … } /* Return the offset of the coefficient of the constant term of "node" * within the (I)LP. * * Within each node, the coefficients have the following order: * - positive and negative parts of c_i_x * - c_i_n (if parametric) * - c_i_0 */ static int node_cst_coef_offset(struct isl_sched_node *node) { … } /* Return the offset of the coefficients of the parameters of "node" * within the (I)LP. * * Within each node, the coefficients have the following order: * - positive and negative parts of c_i_x * - c_i_n (if parametric) * - c_i_0 */ static int node_par_coef_offset(struct isl_sched_node *node) { … } /* Return the offset of the coefficients of the variables of "node" * within the (I)LP. * * Within each node, the coefficients have the following order: * - positive and negative parts of c_i_x * - c_i_n (if parametric) * - c_i_0 */ static int node_var_coef_offset(struct isl_sched_node *node) { … } /* Return the position of the pair of variables encoding * coefficient "i" of "node". * * The order of these variable pairs is the opposite of * that of the coefficients, with 2 variables per coefficient. */ static int node_var_coef_pos(struct isl_sched_node *node, int i) { … } /* Construct an isl_dim_map for mapping constraints on coefficients * for "node" to the corresponding positions in graph->lp. * "offset" is the offset of the coefficients for the variables * in the input constraints. * "s" is the sign of the mapping. * * The input constraints are given in terms of the coefficients * (c_0, c_x) or (c_0, c_n, c_x). * The mapping produced by this function essentially plugs in * (0, c_i_x^+ - c_i_x^-) if s = 1 and * (0, -c_i_x^+ + c_i_x^-) if s = -1 or * (0, 0, c_i_x^+ - c_i_x^-) if s = 1 and * (0, 0, -c_i_x^+ + c_i_x^-) if s = -1. * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart. * Furthermore, the order of these pairs is the opposite of that * of the corresponding coefficients. * * The caller can extend the mapping to also map the other coefficients * (and therefore not plug in 0). */ static __isl_give isl_dim_map *intra_dim_map(isl_ctx *ctx, struct isl_sched_graph *graph, struct isl_sched_node *node, int offset, int s) { … } /* Construct an isl_dim_map for mapping constraints on coefficients * for "src" (node i) and "dst" (node j) to the corresponding positions * in graph->lp. * "offset" is the offset of the coefficients for the variables of "src" * in the input constraints. * "s" is the sign of the mapping. * * The input constraints are given in terms of the coefficients * (c_0, c_n, c_x, c_y). * The mapping produced by this function essentially plugs in * (c_j_0 - c_i_0, c_j_n - c_i_n, * -(c_i_x^+ - c_i_x^-), c_j_x^+ - c_j_x^-) if s = 1 and * (-c_j_0 + c_i_0, -c_j_n + c_i_n, * c_i_x^+ - c_i_x^-, -(c_j_x^+ - c_j_x^-)) if s = -1. * In graph->lp, the c_*^- appear before their c_*^+ counterpart. * Furthermore, the order of these pairs is the opposite of that * of the corresponding coefficients. * * The caller can further extend the mapping. */ static __isl_give isl_dim_map *inter_dim_map(isl_ctx *ctx, struct isl_sched_graph *graph, struct isl_sched_node *src, struct isl_sched_node *dst, int offset, int s) { … } /* Add the constraints from "src" to "dst" using "dim_map", * after making sure there is enough room in "dst" for the extra constraints. */ static __isl_give isl_basic_set *add_constraints_dim_map( __isl_take isl_basic_set *dst, __isl_take isl_basic_set *src, __isl_take isl_dim_map *dim_map) { … } /* Add constraints to graph->lp that force validity for the given * dependence from a node i to itself. * That is, add constraints that enforce * * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x) * = c_i_x (y - x) >= 0 * * for each (x,y) in R. * We obtain general constraints on coefficients (c_0, c_x) * of valid constraints for (y - x) and then plug in (0, c_i_x^+ - c_i_x^-), * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative. * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart. * Note that the result of intra_coefficients may also contain * parameter coefficients c_n, in which case 0 is plugged in for them as well. */ static isl_stat add_intra_validity_constraints(struct isl_sched_graph *graph, struct isl_sched_edge *edge) { … } /* Add constraints to graph->lp that force validity for the given * dependence from node i to node j. * That is, add constraints that enforce * * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0 * * for each (x,y) in R. * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y) * of valid constraints for R and then plug in * (c_j_0 - c_i_0, c_j_n - c_i_n, -(c_i_x^+ - c_i_x^-), c_j_x^+ - c_j_x^-), * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative. * In graph->lp, the c_*^- appear before their c_*^+ counterpart. */ static isl_stat add_inter_validity_constraints(struct isl_sched_graph *graph, struct isl_sched_edge *edge) { … } /* Add constraints to graph->lp that bound the dependence distance for the given * dependence from a node i to itself. * If s = 1, we add the constraint * * c_i_x (y - x) <= m_0 + m_n n * * or * * -c_i_x (y - x) + m_0 + m_n n >= 0 * * for each (x,y) in R. * If s = -1, we add the constraint * * -c_i_x (y - x) <= m_0 + m_n n * * or * * c_i_x (y - x) + m_0 + m_n n >= 0 * * for each (x,y) in R. * We obtain general constraints on coefficients (c_0, c_n, c_x) * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x), * with each coefficient (except m_0) represented as a pair of non-negative * coefficients. * * * If "local" is set, then we add constraints * * c_i_x (y - x) <= 0 * * or * * -c_i_x (y - x) <= 0 * * instead, forcing the dependence distance to be (less than or) equal to 0. * That is, we plug in (0, 0, -s * c_i_x), * intra_coefficients is not required to have c_n in its result when * "local" is set. If they are missing, then (0, -s * c_i_x) is plugged in. * Note that dependences marked local are treated as validity constraints * by add_all_validity_constraints and therefore also have * their distances bounded by 0 from below. */ static isl_stat add_intra_proximity_constraints(struct isl_sched_graph *graph, struct isl_sched_edge *edge, int s, int local) { … } /* Add constraints to graph->lp that bound the dependence distance for the given * dependence from node i to node j. * If s = 1, we add the constraint * * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) * <= m_0 + m_n n * * or * * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) + * m_0 + m_n n >= 0 * * for each (x,y) in R. * If s = -1, we add the constraint * * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)) * <= m_0 + m_n n * * or * * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) + * m_0 + m_n n >= 0 * * for each (x,y) in R. * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y) * of valid constraints for R and then plug in * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n, * s*c_i_x, -s*c_j_x) * with each coefficient (except m_0, c_*_0 and c_*_n) * represented as a pair of non-negative coefficients. * * * If "local" is set (and s = 1), then we add constraints * * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) <= 0 * * or * * -((c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x)) >= 0 * * instead, forcing the dependence distance to be (less than or) equal to 0. * That is, we plug in * (-s*c_j_0 + s*c_i_0, -s*c_j_n + s*c_i_n, s*c_i_x, -s*c_j_x). * Note that dependences marked local are treated as validity constraints * by add_all_validity_constraints and therefore also have * their distances bounded by 0 from below. */ static isl_stat add_inter_proximity_constraints(struct isl_sched_graph *graph, struct isl_sched_edge *edge, int s, int local) { … } /* Should the distance over "edge" be forced to zero? * That is, is it marked as a local edge? * If "use_coincidence" is set, then coincidence edges are treated * as local edges. */ static int force_zero(struct isl_sched_edge *edge, int use_coincidence) { … } /* Add all validity constraints to graph->lp. * * An edge that is forced to be local needs to have its dependence * distances equal to zero. We take care of bounding them by 0 from below * here. add_all_proximity_constraints takes care of bounding them by 0 * from above. * * If "use_coincidence" is set, then we treat coincidence edges as local edges. * Otherwise, we ignore them. */ static int add_all_validity_constraints(struct isl_sched_graph *graph, int use_coincidence) { … } /* Add constraints to graph->lp that bound the dependence distance * for all dependence relations. * If a given proximity dependence is identical to a validity * dependence, then the dependence distance is already bounded * from below (by zero), so we only need to bound the distance * from above. (This includes the case of "local" dependences * which are treated as validity dependence by add_all_validity_constraints.) * Otherwise, we need to bound the distance both from above and from below. * * If "use_coincidence" is set, then we treat coincidence edges as local edges. * Otherwise, we ignore them. */ static int add_all_proximity_constraints(struct isl_sched_graph *graph, int use_coincidence) { … } /* Normalize the rows of "indep" such that all rows are lexicographically * positive and such that each row contains as many final zeros as possible, * given the choice for the previous rows. * Do this by performing elementary row operations. */ static __isl_give isl_mat *normalize_independent(__isl_take isl_mat *indep) { … } /* Extract the linear part of the current schedule for node "node". */ static __isl_give isl_mat *extract_linear_schedule(struct isl_sched_node *node) { … } /* Compute a basis for the rows in the linear part of the schedule * and extend this basis to a full basis. The remaining rows * can then be used to force linear independence from the rows * in the schedule. * * In particular, given the schedule rows S, we compute * * S = H Q * S U = H * * with H the Hermite normal form of S. That is, all but the * first rank columns of H are zero and so each row in S is * a linear combination of the first rank rows of Q. * The matrix Q can be used as a variable transformation * that isolates the directions of S in the first rank rows. * Transposing S U = H yields * * U^T S^T = H^T * * with all but the first rank rows of H^T zero. * The last rows of U^T are therefore linear combinations * of schedule coefficients that are all zero on schedule * coefficients that are linearly dependent on the rows of S. * At least one of these combinations is non-zero on * linearly independent schedule coefficients. * The rows are normalized to involve as few of the last * coefficients as possible and to have a positive initial value. */ isl_stat isl_sched_node_update_vmap(struct isl_sched_node *node) { … } /* Is "edge" marked as a validity or a conditional validity edge? */ static int is_any_validity(struct isl_sched_edge *edge) { … } /* How many times should we count the constraints in "edge"? * * We count as follows * validity -> 1 (>= 0) * validity+proximity -> 2 (>= 0 and upper bound) * proximity -> 2 (lower and upper bound) * local(+any) -> 2 (>= 0 and <= 0) * * If an edge is only marked conditional_validity then it counts * as zero since it is only checked afterwards. * * If "use_coincidence" is set, then we treat coincidence edges as local edges. * Otherwise, we ignore them. */ static int edge_multiplicity(struct isl_sched_edge *edge, int use_coincidence) { … } /* How many times should the constraints in "edge" be counted * as a parametric intra-node constraint? * * Only proximity edges that are not forced zero need * coefficient constraints that include coefficients for parameters. * If the edge is also a validity edge, then only * an upper bound is introduced. Otherwise, both lower and upper bounds * are introduced. */ static int parametric_intra_edge_multiplicity(struct isl_sched_edge *edge, int use_coincidence) { … } /* Add "f" times the number of equality and inequality constraints of "bset" * to "n_eq" and "n_ineq" and free "bset". */ static isl_stat update_count(__isl_take isl_basic_set *bset, int f, int *n_eq, int *n_ineq) { … } /* Count the number of equality and inequality constraints * that will be added for the given map. * * The edges that require parameter coefficients are counted separately. * * "use_coincidence" is set if we should take into account coincidence edges. */ static isl_stat count_map_constraints(struct isl_sched_graph *graph, struct isl_sched_edge *edge, __isl_take isl_map *map, int *n_eq, int *n_ineq, int use_coincidence) { … } /* Count the number of equality and inequality constraints * that will be added to the main lp problem. * We count as follows * validity -> 1 (>= 0) * validity+proximity -> 2 (>= 0 and upper bound) * proximity -> 2 (lower and upper bound) * local(+any) -> 2 (>= 0 and <= 0) * * If "use_coincidence" is set, then we treat coincidence edges as local edges. * Otherwise, we ignore them. */ static int count_constraints(struct isl_sched_graph *graph, int *n_eq, int *n_ineq, int use_coincidence) { … } /* Count the number of constraints that will be added by * add_bound_constant_constraints to bound the values of the constant terms * and increment *n_eq and *n_ineq accordingly. * * In practice, add_bound_constant_constraints only adds inequalities. */ static isl_stat count_bound_constant_constraints(isl_ctx *ctx, struct isl_sched_graph *graph, int *n_eq, int *n_ineq) { … } /* Add constraints to bound the values of the constant terms in the schedule, * if requested by the user. * * The maximal value of the constant terms is defined by the option * "schedule_max_constant_term". */ static isl_stat add_bound_constant_constraints(isl_ctx *ctx, struct isl_sched_graph *graph) { … } /* Count the number of constraints that will be added by * add_bound_coefficient_constraints and increment *n_eq and *n_ineq * accordingly. * * In practice, add_bound_coefficient_constraints only adds inequalities. */ static int count_bound_coefficient_constraints(isl_ctx *ctx, struct isl_sched_graph *graph, int *n_eq, int *n_ineq) { … } /* Add constraints to graph->lp that bound the values of * the parameter schedule coefficients of "node" to "max" and * the variable schedule coefficients to the corresponding entry * in node->max. * In either case, a negative value means that no bound needs to be imposed. * * For parameter coefficients, this amounts to adding a constraint * * c_n <= max * * i.e., * * -c_n + max >= 0 * * The variables coefficients are, however, not represented directly. * Instead, the variable coefficients c_x are written as differences * c_x = c_x^+ - c_x^-. * That is, * * -max_i <= c_x_i <= max_i * * is encoded as * * -max_i <= c_x_i^+ - c_x_i^- <= max_i * * or * * -(c_x_i^+ - c_x_i^-) + max_i >= 0 * c_x_i^+ - c_x_i^- + max_i >= 0 */ static isl_stat node_add_coefficient_constraints(isl_ctx *ctx, struct isl_sched_graph *graph, struct isl_sched_node *node, int max) { … } /* Add constraints that bound the values of the variable and parameter * coefficients of the schedule. * * The maximal value of the coefficients is defined by the option * 'schedule_max_coefficient' and the entries in node->max. * These latter entries are only set if either the schedule_max_coefficient * option or the schedule_treat_coalescing option is set. */ static isl_stat add_bound_coefficient_constraints(isl_ctx *ctx, struct isl_sched_graph *graph) { … } /* Add a constraint to graph->lp that equates the value at position * "sum_pos" to the sum of the "n" values starting at "first". */ static isl_stat add_sum_constraint(struct isl_sched_graph *graph, int sum_pos, int first, int n) { … } /* Add a constraint to graph->lp that equates the value at position * "sum_pos" to the sum of the parameter coefficients of all nodes. */ static isl_stat add_param_sum_constraint(struct isl_sched_graph *graph, int sum_pos) { … } /* Add a constraint to graph->lp that equates the value at position * "sum_pos" to the sum of the variable coefficients of all nodes. */ static isl_stat add_var_sum_constraint(struct isl_sched_graph *graph, int sum_pos) { … } /* Construct an ILP problem for finding schedule coefficients * that result in non-negative, but small dependence distances * over all dependences. * In particular, the dependence distances over proximity edges * are bounded by m_0 + m_n n and we compute schedule coefficients * with small values (preferably zero) of m_n and m_0. * * All variables of the ILP are non-negative. The actual coefficients * may be negative, so each coefficient is represented as the difference * of two non-negative variables. The negative part always appears * immediately before the positive part. * Other than that, the variables have the following order * * - sum of positive and negative parts of m_n coefficients * - m_0 * - sum of all c_n coefficients * (unconstrained when computing non-parametric schedules) * - sum of positive and negative parts of all c_x coefficients * - positive and negative parts of m_n coefficients * - for each node * - positive and negative parts of c_i_x, in opposite order * - c_i_n (if parametric) * - c_i_0 * * The constraints are those from the edges plus two or three equalities * to express the sums. * * If "use_coincidence" is set, then we treat coincidence edges as local edges. * Otherwise, we ignore them. */ static isl_stat setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph, int use_coincidence) { … } /* Analyze the conflicting constraint found by * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity * constraint of one of the edges between distinct nodes, living, moreover * in distinct SCCs, then record the source and sink SCC as this may * be a good place to cut between SCCs. */ static int check_conflict(int con, void *user) { … } /* Check whether the next schedule row of the given node needs to be * non-trivial. Lower-dimensional domains may have some trivial rows, * but as soon as the number of remaining required non-trivial rows * is as large as the number or remaining rows to be computed, * all remaining rows need to be non-trivial. */ static int needs_row(struct isl_sched_graph *graph, struct isl_sched_node *node) { … } /* Construct a non-triviality region with triviality directions * corresponding to the rows of "indep". * The rows of "indep" are expressed in terms of the schedule coefficients c_i, * while the triviality directions are expressed in terms of * pairs of non-negative variables c^+_i - c^-_i, with c^-_i appearing * before c^+_i. Furthermore, * the pairs of non-negative variables representing the coefficients * are stored in the opposite order. */ static __isl_give isl_mat *construct_trivial(__isl_keep isl_mat *indep) { … } /* Solve the ILP problem constructed in setup_lp. * For each node such that all the remaining rows of its schedule * need to be non-trivial, we construct a non-triviality region. * This region imposes that the next row is independent of previous rows. * In particular, the non-triviality region enforces that at least * one of the linear combinations in the rows of node->indep is non-zero. */ static __isl_give isl_vec *solve_lp(isl_ctx *ctx, struct isl_sched_graph *graph) { … } /* Extract the coefficients for the variables of "node" from "sol". * * Each schedule coefficient c_i_x is represented as the difference * between two non-negative variables c_i_x^+ - c_i_x^-. * The c_i_x^- appear before their c_i_x^+ counterpart. * Furthermore, the order of these pairs is the opposite of that * of the corresponding coefficients. * * Return c_i_x = c_i_x^+ - c_i_x^- */ static __isl_give isl_vec *extract_var_coef(struct isl_sched_node *node, __isl_keep isl_vec *sol) { … } /* Update the schedules of all nodes based on the given solution * of the LP problem. * The new row is added to the current band. * All possibly negative coefficients are encoded as a difference * of two non-negative variables, so we need to perform the subtraction * here. * * If coincident is set, then the caller guarantees that the new * row satisfies the coincidence constraints. */ static int update_schedule(struct isl_sched_graph *graph, __isl_take isl_vec *sol, int coincident) { … } /* Convert row "row" of node->sched into an isl_aff living in "ls" * and return this isl_aff. */ static __isl_give isl_aff *extract_schedule_row(__isl_take isl_local_space *ls, struct isl_sched_node *node, int row) { … } /* Convert the "n" rows starting at "first" of node->sched into a multi_aff * and return this multi_aff. * * The result is defined over the uncompressed node domain. */ __isl_give isl_multi_aff *isl_sched_node_extract_partial_schedule_multi_aff( struct isl_sched_node *node, int first, int n) { … } /* Convert node->sched into a multi_aff and return this multi_aff. * * The result is defined over the uncompressed node domain. */ static __isl_give isl_multi_aff *node_extract_schedule_multi_aff( struct isl_sched_node *node) { … } /* Convert node->sched into a map and return this map. * * The result is cached in node->sched_map, which needs to be released * whenever node->sched is updated. * It is defined over the uncompressed node domain. */ static __isl_give isl_map *node_extract_schedule(struct isl_sched_node *node) { … } /* Construct a map that can be used to update a dependence relation * based on the current schedule. * That is, construct a map expressing that source and sink * are executed within the same iteration of the current schedule. * This map can then be intersected with the dependence relation. * This is not the most efficient way, but this shouldn't be a critical * operation. */ static __isl_give isl_map *specializer(struct isl_sched_node *src, struct isl_sched_node *dst) { … } /* Intersect the domains of the nested relations in domain and range * of "umap" with "map". */ static __isl_give isl_union_map *intersect_domains( __isl_take isl_union_map *umap, __isl_keep isl_map *map) { … } /* Update the dependence relation of the given edge based * on the current schedule. * If the dependence is carried completely by the current schedule, then * it is removed from the edge_tables. It is kept in the list of edges * as otherwise all edge_tables would have to be recomputed. * * If the edge is of a type that can appear multiple times * between the same pair of nodes, then it is added to * the edge table (again). This prevents the situation * where none of these edges is referenced from the edge table * because the one that was referenced turned out to be empty and * was therefore removed from the table. */ static isl_stat update_edge(isl_ctx *ctx, struct isl_sched_graph *graph, struct isl_sched_edge *edge) { … } /* Does the domain of "umap" intersect "uset"? */ static int domain_intersects(__isl_keep isl_union_map *umap, __isl_keep isl_union_set *uset) { … } /* Does the range of "umap" intersect "uset"? */ static int range_intersects(__isl_keep isl_union_map *umap, __isl_keep isl_union_set *uset) { … } /* Are the condition dependences of "edge" local with respect to * the current schedule? * * That is, are domain and range of the condition dependences mapped * to the same point? * * In other words, is the condition false? */ static int is_condition_false(struct isl_sched_edge *edge) { … } /* For each conditional validity constraint that is adjacent * to a condition with domain in condition_source or range in condition_sink, * turn it into an unconditional validity constraint. */ static int unconditionalize_adjacent_validity(struct isl_sched_graph *graph, __isl_take isl_union_set *condition_source, __isl_take isl_union_set *condition_sink) { … } /* Update the dependence relations of all edges based on the current schedule * and enforce conditional validity constraints that are adjacent * to satisfied condition constraints. * * First check if any of the condition constraints are satisfied * (i.e., not local to the outer schedule) and keep track of * their domain and range. * Then update all dependence relations (which removes the non-local * constraints). * Finally, if any condition constraints turned out to be satisfied, * then turn all adjacent conditional validity constraints into * unconditional validity constraints. */ static int update_edges(isl_ctx *ctx, struct isl_sched_graph *graph) { … } static void next_band(struct isl_sched_graph *graph) { … } /* Return the union of the universe domains of the nodes in "graph" * that satisfy "pred". */ static __isl_give isl_union_set *isl_sched_graph_domain(isl_ctx *ctx, struct isl_sched_graph *graph, int (*pred)(struct isl_sched_node *node, int data), int data) { … } /* Return a union of universe domains corresponding to the nodes * in the SCC with index "scc". */ __isl_give isl_union_set *isl_sched_graph_extract_scc(isl_ctx *ctx, struct isl_sched_graph *graph, int scc) { … } /* Return a list of unions of universe domains, where each element * in the list corresponds to an SCC (or WCC) indexed by node->scc. */ __isl_give isl_union_set_list *isl_sched_graph_extract_sccs(isl_ctx *ctx, struct isl_sched_graph *graph) { … } /* Return a list of two unions of universe domains, one for the SCCs up * to and including graph->src_scc and another for the other SCCs. */ static __isl_give isl_union_set_list *extract_split(isl_ctx *ctx, struct isl_sched_graph *graph) { … } /* Copy nodes that satisfy node_pred from the src dependence graph * to the dst dependence graph. */ static isl_stat copy_nodes(struct isl_sched_graph *dst, struct isl_sched_graph *src, int (*node_pred)(struct isl_sched_node *node, int data), int data) { … } /* Copy non-empty edges that satisfy edge_pred from the src dependence graph * to the dst dependence graph. * If the source or destination node of the edge is not in the destination * graph, then it must be a backward proximity edge and it should simply * be ignored. */ static isl_stat copy_edges(isl_ctx *ctx, struct isl_sched_graph *dst, struct isl_sched_graph *src, int (*edge_pred)(struct isl_sched_edge *edge, int data), int data) { … } /* Compute the maximal number of variables over all nodes. * This is the maximal number of linearly independent schedule * rows that we need to compute. * Just in case we end up in a part of the dependence graph * with only lower-dimensional domains, we make sure we will * compute the required amount of extra linearly independent rows. */ isl_stat isl_sched_graph_compute_maxvar(struct isl_sched_graph *graph) { … } /* Extract the subgraph of "graph" that consists of the nodes satisfying * "node_pred" and the edges satisfying "edge_pred" and store * the result in "sub". */ isl_stat isl_sched_graph_extract_sub_graph(isl_ctx *ctx, struct isl_sched_graph *graph, int (*node_pred)(struct isl_sched_node *node, int data), int (*edge_pred)(struct isl_sched_edge *edge, int data), int data, struct isl_sched_graph *sub) { … } static __isl_give isl_schedule_node *compute_schedule(isl_schedule_node *node, struct isl_sched_graph *graph); static __isl_give isl_schedule_node *compute_schedule_wcc( isl_schedule_node *node, struct isl_sched_graph *graph); /* Compute a schedule for a subgraph of "graph". In particular, for * the graph composed of nodes that satisfy node_pred and edges that * that satisfy edge_pred. * If the subgraph is known to consist of a single component, then wcc should * be set and then we call compute_schedule_wcc on the constructed subgraph. * Otherwise, we call compute_schedule, which will check whether the subgraph * is connected. * * The schedule is inserted at "node" and the updated schedule node * is returned. */ static __isl_give isl_schedule_node *compute_sub_schedule( __isl_take isl_schedule_node *node, isl_ctx *ctx, struct isl_sched_graph *graph, int (*node_pred)(struct isl_sched_node *node, int data), int (*edge_pred)(struct isl_sched_edge *edge, int data), int data, int wcc) { … } int isl_sched_edge_scc_exactly(struct isl_sched_edge *edge, int scc) { … } static int edge_dst_scc_at_most(struct isl_sched_edge *edge, int scc) { … } static int edge_src_scc_at_least(struct isl_sched_edge *edge, int scc) { … } /* Reset the current band by dropping all its schedule rows. */ static isl_stat reset_band(struct isl_sched_graph *graph) { … } /* Split the current graph into two parts and compute a schedule for each * part individually. In particular, one part consists of all SCCs up * to and including graph->src_scc, while the other part contains the other * SCCs. The split is enforced by a sequence node inserted at position "node" * in the schedule tree. Return the updated schedule node. * If either of these two parts consists of a sequence, then it is spliced * into the sequence containing the two parts. * * The current band is reset. It would be possible to reuse * the previously computed rows as the first rows in the next * band, but recomputing them may result in better rows as we are looking * at a smaller part of the dependence graph. */ static __isl_give isl_schedule_node *compute_split_schedule( __isl_take isl_schedule_node *node, struct isl_sched_graph *graph) { … } /* Insert a band node at position "node" in the schedule tree corresponding * to the current band in "graph". Mark the band node permutable * if "permutable" is set. * The partial schedules and the coincidence property are extracted * from the graph nodes. * Return the updated schedule node. */ static __isl_give isl_schedule_node *insert_current_band( __isl_take isl_schedule_node *node, struct isl_sched_graph *graph, int permutable) { … } /* Update the dependence relations based on the current schedule, * add the current band to "node" and then continue with the computation * of the next band. * Return the updated schedule node. */ static __isl_give isl_schedule_node *compute_next_band( __isl_take isl_schedule_node *node, struct isl_sched_graph *graph, int permutable) { … } /* Add the constraints "coef" derived from an edge from "node" to itself * to graph->lp in order to respect the dependences and to try and carry them. * "pos" is the sequence number of the edge that needs to be carried. * "coef" represents general constraints on coefficients (c_0, c_x) * of valid constraints for (y - x) with x and y instances of the node. * * The constraints added to graph->lp need to enforce * * (c_j_0 + c_j_x y) - (c_j_0 + c_j_x x) * = c_j_x (y - x) >= e_i * * for each (x,y) in the dependence relation of the edge. * That is, (-e_i, c_j_x) needs to be plugged in for (c_0, c_x), * taking into account that each coefficient in c_j_x is represented * as a pair of non-negative coefficients. */ static isl_stat add_intra_constraints(struct isl_sched_graph *graph, struct isl_sched_node *node, __isl_take isl_basic_set *coef, int pos) { … } /* Add the constraints "coef" derived from an edge from "src" to "dst" * to graph->lp in order to respect the dependences and to try and carry them. * "pos" is the sequence number of the edge that needs to be carried or * -1 if no attempt should be made to carry the dependences. * "coef" represents general constraints on coefficients (c_0, c_n, c_x, c_y) * of valid constraints for (x, y) with x and y instances of "src" and "dst". * * The constraints added to graph->lp need to enforce * * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i * * for each (x,y) in the dependence relation of the edge or * * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= 0 * * if pos is -1. * That is, * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, -c_j_x, c_k_x) * or * (c_k_0 - c_j_0, c_k_n - c_j_n, -c_j_x, c_k_x) * needs to be plugged in for (c_0, c_n, c_x, c_y), * taking into account that each coefficient in c_j_x and c_k_x is represented * as a pair of non-negative coefficients. */ static isl_stat add_inter_constraints(struct isl_sched_graph *graph, struct isl_sched_node *src, struct isl_sched_node *dst, __isl_take isl_basic_set *coef, int pos) { … } /* Data structure for keeping track of the data needed * to exploit non-trivial lineality spaces. * * "any_non_trivial" is true if there are any non-trivial lineality spaces. * If "any_non_trivial" is not true, then "equivalent" and "mask" may be NULL. * "equivalent" connects instances to other instances on the same line(s). * "mask" contains the domain spaces of "equivalent". * Any instance set not in "mask" does not have a non-trivial lineality space. */ struct isl_exploit_lineality_data { … }; /* Data structure collecting information used during the construction * of an LP for carrying dependences. * * "intra" is a sequence of coefficient constraints for intra-node edges. * "inter" is a sequence of coefficient constraints for inter-node edges. * "lineality" contains data used to exploit non-trivial lineality spaces. */ struct isl_carry { … }; /* Free all the data stored in "carry". */ static void isl_carry_clear(struct isl_carry *carry) { … } /* Return a pointer to the node in "graph" that lives in "space". * If the requested node has been compressed, then "space" * corresponds to the compressed space. * The graph is assumed to have such a node. * Return NULL in case of error. * * First try and see if "space" is the space of an uncompressed node. * If so, return that node. * Otherwise, "space" was constructed by construct_compressed_id and * contains a user pointer pointing to the node in the tuple id. * However, this node belongs to the original dependence graph. * If "graph" is a subgraph of this original dependence graph, * then the node with the same space still needs to be looked up * in the current graph. */ static struct isl_sched_node *graph_find_compressed_node(isl_ctx *ctx, struct isl_sched_graph *graph, __isl_keep isl_space *space) { … } /* Internal data structure for add_all_constraints. * * "graph" is the schedule constraint graph for which an LP problem * is being constructed. * "carry_inter" indicates whether inter-node edges should be carried. * "pos" is the position of the next edge that needs to be carried. */ struct isl_add_all_constraints_data { … }; /* Add the constraints "coef" derived from an edge from a node to itself * to data->graph->lp in order to respect the dependences and * to try and carry them. * * The space of "coef" is of the form * * coefficients[[c_cst] -> S[c_x]] * * with S[c_x] the (compressed) space of the node. * Extract the node from the space and call add_intra_constraints. */ static isl_stat lp_add_intra(__isl_take isl_basic_set *coef, void *user) { … } /* Add the constraints "coef" derived from an edge from a node j * to a node k to data->graph->lp in order to respect the dependences and * to try and carry them (provided data->carry_inter is set). * * The space of "coef" is of the form * * coefficients[[c_cst, c_n] -> [S_j[c_x] -> S_k[c_y]]] * * with S_j[c_x] and S_k[c_y] the (compressed) spaces of the nodes. * Extract the nodes from the space and call add_inter_constraints. */ static isl_stat lp_add_inter(__isl_take isl_basic_set *coef, void *user) { … } /* Add constraints to graph->lp that force all (conditional) validity * dependences to be respected and attempt to carry them. * "intra" is the sequence of coefficient constraints for intra-node edges. * "inter" is the sequence of coefficient constraints for inter-node edges. * "carry_inter" indicates whether inter-node edges should be carried or * only respected. */ static isl_stat add_all_constraints(isl_ctx *ctx, struct isl_sched_graph *graph, __isl_keep isl_basic_set_list *intra, __isl_keep isl_basic_set_list *inter, int carry_inter) { … } /* Internal data structure for count_all_constraints * for keeping track of the number of equality and inequality constraints. */ struct isl_sched_count { … }; /* Add the number of equality and inequality constraints of "bset" * to data->n_eq and data->n_ineq. */ static isl_stat bset_update_count(__isl_take isl_basic_set *bset, void *user) { … } /* Count the number of equality and inequality constraints * that will be added to the carry_lp problem. * We count each edge exactly once. * "intra" is the sequence of coefficient constraints for intra-node edges. * "inter" is the sequence of coefficient constraints for inter-node edges. */ static isl_stat count_all_constraints(__isl_keep isl_basic_set_list *intra, __isl_keep isl_basic_set_list *inter, int *n_eq, int *n_ineq) { … } /* Construct an LP problem for finding schedule coefficients * such that the schedule carries as many validity dependences as possible. * In particular, for each dependence i, we bound the dependence distance * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum * of all e_i's. Dependences with e_i = 0 in the solution are simply * respected, while those with e_i > 0 (in practice e_i = 1) are carried. * "intra" is the sequence of coefficient constraints for intra-node edges. * "inter" is the sequence of coefficient constraints for inter-node edges. * "n_edge" is the total number of edges. * "carry_inter" indicates whether inter-node edges should be carried or * only respected. That is, if "carry_inter" is not set, then * no e_i variables are introduced for the inter-node edges. * * All variables of the LP are non-negative. The actual coefficients * may be negative, so each coefficient is represented as the difference * of two non-negative variables. The negative part always appears * immediately before the positive part. * Other than that, the variables have the following order * * - sum of (1 - e_i) over all edges * - sum of all c_n coefficients * (unconstrained when computing non-parametric schedules) * - sum of positive and negative parts of all c_x coefficients * - for each edge * - e_i * - for each node * - positive and negative parts of c_i_x, in opposite order * - c_i_n (if parametric) * - c_i_0 * * The constraints are those from the (validity) edges plus three equalities * to express the sums and n_edge inequalities to express e_i <= 1. */ static isl_stat setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph, int n_edge, __isl_keep isl_basic_set_list *intra, __isl_keep isl_basic_set_list *inter, int carry_inter) { … } static __isl_give isl_schedule_node *compute_component_schedule( __isl_take isl_schedule_node *node, struct isl_sched_graph *graph, int wcc); /* If the schedule_split_scaled option is set and if the linear * parts of the scheduling rows for all nodes in the graphs have * a non-trivial common divisor, then remove this * common divisor from the linear part. * Otherwise, insert a band node directly and continue with * the construction of the schedule. * * If a non-trivial common divisor is found, then * the linear part is reduced and the remainder is ignored. * The pieces of the graph that are assigned different remainders * form (groups of) strongly connected components within * the scaled down band. If needed, they can therefore * be ordered along this remainder in a sequence node. * However, this ordering is not enforced here in order to allow * the scheduler to combine some of the strongly connected components. */ static __isl_give isl_schedule_node *split_scaled( __isl_take isl_schedule_node *node, struct isl_sched_graph *graph) { … } /* Is the schedule row "sol" trivial on node "node"? * That is, is the solution zero on the dimensions linearly independent of * the previously found solutions? * Return 1 if the solution is trivial, 0 if it is not and -1 on error. * * Each coefficient is represented as the difference between * two non-negative values in "sol". * We construct the schedule row s and check if it is linearly * independent of previously computed schedule rows * by computing T s, with T the linear combinations that are zero * on linearly dependent schedule rows. * If the result consists of all zeros, then the solution is trivial. */ static int is_trivial(struct isl_sched_node *node, __isl_keep isl_vec *sol) { … } /* Is the schedule row "sol" trivial on any node where it should * not be trivial? * Return 1 if any solution is trivial, 0 if they are not and -1 on error. */ static int is_any_trivial(struct isl_sched_graph *graph, __isl_keep isl_vec *sol) { … } /* Does the schedule represented by "sol" perform loop coalescing on "node"? * If so, return the position of the coalesced dimension. * Otherwise, return node->nvar or -1 on error. * * In particular, look for pairs of coefficients c_i and c_j such that * |c_j/c_i| > ceil(size_i/2), i.e., |c_j| > |c_i * ceil(size_i/2)|. * If any such pair is found, then return i. * If size_i is infinity, then no check on c_i needs to be performed. */ static int find_node_coalescing(struct isl_sched_node *node, __isl_keep isl_vec *sol) { … } /* Force the schedule coefficient at position "pos" of "node" to be zero * in "tl". * The coefficient is encoded as the difference between two non-negative * variables. Force these two variables to have the same value. */ static __isl_give isl_tab_lexmin *zero_out_node_coef( __isl_take isl_tab_lexmin *tl, struct isl_sched_node *node, int pos) { … } /* Return the lexicographically smallest rational point in the basic set * from which "tl" was constructed, double checking that this input set * was not empty. */ static __isl_give isl_vec *non_empty_solution(__isl_keep isl_tab_lexmin *tl) { … } /* Does the solution "sol" of the LP problem constructed by setup_carry_lp * carry any of the "n_edge" groups of dependences? * The value in the first position is the sum of (1 - e_i) over all "n_edge" * edges, with 0 <= e_i <= 1 equal to 1 when the dependences represented * by the edge are carried by the solution. * If the sum of the (1 - e_i) is smaller than "n_edge" then at least * one of those is carried. * * Note that despite the fact that the problem is solved using a rational * solver, the solution is guaranteed to be integral. * Specifically, the dependence distance lower bounds e_i (and therefore * also their sum) are integers. See Lemma 5 of [1]. * * Any potential denominator of the sum is cleared by this function. * The denominator is not relevant for any of the other elements * in the solution. * * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling * Problem, Part II: Multi-Dimensional Time. * In Intl. Journal of Parallel Programming, 1992. */ static int carries_dependences(__isl_keep isl_vec *sol, int n_edge) { … } /* Return the lexicographically smallest rational point in "lp", * assuming that all variables are non-negative and performing some * additional sanity checks. * If "want_integral" is set, then compute the lexicographically smallest * integer point instead. * In particular, "lp" should not be empty by construction. * Double check that this is the case. * If dependences are not carried for any of the "n_edge" edges, * then return an empty vector. * * If the schedule_treat_coalescing option is set and * if the computed schedule performs loop coalescing on a given node, * i.e., if it is of the form * * c_i i + c_j j + ... * * with |c_j/c_i| >= size_i, then force the coefficient c_i to be zero * to cut out this solution. Repeat this process until no more loop * coalescing occurs or until no more dependences can be carried. * In the latter case, revert to the previously computed solution. * * If the caller requests an integral solution and if coalescing should * be treated, then perform the coalescing treatment first as * an integral solution computed before coalescing treatment * would carry the same number of edges and would therefore probably * also be coalescing. * * To allow the coalescing treatment to be performed first, * the initial solution is allowed to be rational and it is only * cut out (if needed) in the next iteration, if no coalescing measures * were taken. */ static __isl_give isl_vec *non_neg_lexmin(struct isl_sched_graph *graph, __isl_take isl_basic_set *lp, int n_edge, int want_integral) { … } /* If "edge" is an edge from a node to itself, then add the corresponding * dependence relation to "umap". * If "node" has been compressed, then the dependence relation * is also compressed first. */ static __isl_give isl_union_map *add_intra(__isl_take isl_union_map *umap, struct isl_sched_edge *edge) { … } /* If "edge" is an edge from a node to another node, then add the corresponding * dependence relation to "umap". * If the source or destination nodes of "edge" have been compressed, * then the dependence relation is also compressed first. */ static __isl_give isl_union_map *add_inter(__isl_take isl_union_map *umap, struct isl_sched_edge *edge) { … } /* Internal data structure used by union_drop_coalescing_constraints * to collect bounds on all relevant statements. * * "graph" is the schedule constraint graph for which an LP problem * is being constructed. * "bounds" collects the bounds. */ struct isl_collect_bounds_data { … }; /* Add the size bounds for the node with instance deltas in "set" * to data->bounds. */ static isl_stat collect_bounds(__isl_take isl_set *set, void *user) { … } /* Drop some constraints from "delta" that could be exploited * to construct loop coalescing schedules. * In particular, drop those constraint that bound the difference * to the size of the domain. * Do this for each set/node in "delta" separately. * The parameters are assumed to have been projected out by the caller. */ static __isl_give isl_union_set *union_drop_coalescing_constraints(isl_ctx *ctx, struct isl_sched_graph *graph, __isl_take isl_union_set *delta) { … } /* Given a non-trivial lineality space "lineality", add the corresponding * universe set to data->mask and add a map from elements to * other elements along the lines in "lineality" to data->equivalent. * If this is the first time this function gets called * (data->any_non_trivial is still false), then set data->any_non_trivial and * initialize data->mask and data->equivalent. * * In particular, if the lineality space is defined by equality constraints * * E x = 0 * * then construct an affine mapping * * f : x -> E x * * and compute the equivalence relation of having the same image under f: * * { x -> x' : E x = E x' } */ static isl_stat add_non_trivial_lineality(__isl_take isl_basic_set *lineality, struct isl_exploit_lineality_data *data) { … } /* Check if the lineality space "set" is non-trivial (i.e., is not just * the origin or, in other words, satisfies a number of equality constraints * that is smaller than the dimension of the set). * If so, extend data->mask and data->equivalent accordingly. * * The input should not have any local variables already, but * isl_set_remove_divs is called to make sure it does not. */ static isl_stat add_lineality(__isl_take isl_set *set, void *user) { … } /* Check if the difference set on intra-node schedule constraints "intra" * has any non-trivial lineality space. * If so, then extend the difference set to a difference set * on equivalent elements. That is, if "intra" is * * { y - x : (x,y) \in V } * * and elements are equivalent if they have the same image under f, * then return * * { y' - x' : (x,y) \in V and f(x) = f(x') and f(y) = f(y') } * * or, since f is linear, * * { y' - x' : (x,y) \in V and f(y - x) = f(y' - x') } * * The results of the search for non-trivial lineality spaces is stored * in "data". */ static __isl_give isl_union_set *exploit_intra_lineality( __isl_take isl_union_set *intra, struct isl_exploit_lineality_data *data) { … } /* If the difference set on intra-node schedule constraints was found to have * any non-trivial lineality space by exploit_intra_lineality, * as recorded in "data", then extend the inter-node * schedule constraints "inter" to schedule constraints on equivalent elements. * That is, if "inter" is V and * elements are equivalent if they have the same image under f, then return * * { (x', y') : (x,y) \in V and f(x) = f(x') and f(y) = f(y') } */ static __isl_give isl_union_map *exploit_inter_lineality( __isl_take isl_union_map *inter, struct isl_exploit_lineality_data *data) { … } /* For each (conditional) validity edge in "graph", * add the corresponding dependence relation using "add" * to a collection of dependence relations and return the result. * If "coincidence" is set, then coincidence edges are considered as well. */ static __isl_give isl_union_map *collect_validity(struct isl_sched_graph *graph, __isl_give isl_union_map *(*add)(__isl_take isl_union_map *umap, struct isl_sched_edge *edge), int coincidence) { … } /* For each dependence relation on a (conditional) validity edge * from a node to itself, * construct the set of coefficients of valid constraints for elements * in that dependence relation and collect the results. * If "coincidence" is set, then coincidence edges are considered as well. * * In particular, for each dependence relation R, constraints * on coefficients (c_0, c_x) are constructed such that * * c_0 + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R } * * If the schedule_treat_coalescing option is set, then some constraints * that could be exploited to construct coalescing schedules * are removed before the dual is computed, but after the parameters * have been projected out. * The entire computation is essentially the same as that performed * by intra_coefficients, except that it operates on multiple * edges together and that the parameters are always projected out. * * Additionally, exploit any non-trivial lineality space * in the difference set after removing coalescing constraints and * store the results of the non-trivial lineality space detection in "data". * The procedure is currently run unconditionally, but it is unlikely * to find any non-trivial lineality spaces if no coalescing constraints * have been removed. * * Note that if a dependence relation is a union of basic maps, * then each basic map needs to be treated individually as it may only * be possible to carry the dependences expressed by some of those * basic maps and not all of them. * The collected validity constraints are therefore not coalesced and * it is assumed that they are not coalesced automatically. * Duplicate basic maps can be removed, however. * In particular, if the same basic map appears as a disjunct * in multiple edges, then it only needs to be carried once. */ static __isl_give isl_basic_set_list *collect_intra_validity(isl_ctx *ctx, struct isl_sched_graph *graph, int coincidence, struct isl_exploit_lineality_data *data) { … } /* For each dependence relation on a (conditional) validity edge * from a node to some other node, * construct the set of coefficients of valid constraints for elements * in that dependence relation and collect the results. * If "coincidence" is set, then coincidence edges are considered as well. * * In particular, for each dependence relation R, constraints * on coefficients (c_0, c_n, c_x, c_y) are constructed such that * * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R * * This computation is essentially the same as that performed * by inter_coefficients, except that it operates on multiple * edges together. * * Additionally, exploit any non-trivial lineality space * that may have been discovered by collect_intra_validity * (as stored in "data"). * * Note that if a dependence relation is a union of basic maps, * then each basic map needs to be treated individually as it may only * be possible to carry the dependences expressed by some of those * basic maps and not all of them. * The collected validity constraints are therefore not coalesced and * it is assumed that they are not coalesced automatically. * Duplicate basic maps can be removed, however. * In particular, if the same basic map appears as a disjunct * in multiple edges, then it only needs to be carried once. */ static __isl_give isl_basic_set_list *collect_inter_validity( struct isl_sched_graph *graph, int coincidence, struct isl_exploit_lineality_data *data) { … } /* Construct an LP problem for finding schedule coefficients * such that the schedule carries as many of the "n_edge" groups of * dependences as possible based on the corresponding coefficient * constraints and return the lexicographically smallest non-trivial solution. * "intra" is the sequence of coefficient constraints for intra-node edges. * "inter" is the sequence of coefficient constraints for inter-node edges. * If "want_integral" is set, then compute an integral solution * for the coefficients rather than using the numerators * of a rational solution. * "carry_inter" indicates whether inter-node edges should be carried or * only respected. * * If none of the "n_edge" groups can be carried * then return an empty vector. */ static __isl_give isl_vec *compute_carrying_sol_coef(isl_ctx *ctx, struct isl_sched_graph *graph, int n_edge, __isl_keep isl_basic_set_list *intra, __isl_keep isl_basic_set_list *inter, int want_integral, int carry_inter) { … } /* Construct an LP problem for finding schedule coefficients * such that the schedule carries as many of the validity dependences * as possible and * return the lexicographically smallest non-trivial solution. * If "fallback" is set, then the carrying is performed as a fallback * for the Pluto-like scheduler. * If "coincidence" is set, then try and carry coincidence edges as well. * * The variable "n_edge" stores the number of groups that should be carried. * If none of the "n_edge" groups can be carried * then return an empty vector. * If, moreover, "n_edge" is zero, then the LP problem does not even * need to be constructed. * * If a fallback solution is being computed, then compute an integral solution * for the coefficients rather than using the numerators * of a rational solution. * * If a fallback solution is being computed, if there are any intra-node * dependences, and if requested by the user, then first try * to only carry those intra-node dependences. * If this fails to carry any dependences, then try again * with the inter-node dependences included. */ static __isl_give isl_vec *compute_carrying_sol(isl_ctx *ctx, struct isl_sched_graph *graph, int fallback, int coincidence) { … } /* Construct a schedule row for each node such that as many validity dependences * as possible are carried and then continue with the next band. * If "fallback" is set, then the carrying is performed as a fallback * for the Pluto-like scheduler. * If "coincidence" is set, then try and carry coincidence edges as well. * * If there are no validity dependences, then no dependence can be carried and * the procedure is guaranteed to fail. If there is more than one component, * then try computing a schedule on each component separately * to prevent or at least postpone this failure. * * If a schedule row is computed, then check that dependences are carried * for at least one of the edges. * * If the computed schedule row turns out to be trivial on one or * more nodes where it should not be trivial, then we throw it away * and try again on each component separately. * * If there is only one component, then we accept the schedule row anyway, * but we do not consider it as a complete row and therefore do not * increment graph->n_row. Note that the ranks of the nodes that * do get a non-trivial schedule part will get updated regardless and * graph->maxvar is computed based on these ranks. The test for * whether more schedule rows are required in compute_schedule_wcc * is therefore not affected. * * Insert a band corresponding to the schedule row at position "node" * of the schedule tree and continue with the construction of the schedule. * This insertion and the continued construction is performed by split_scaled * after optionally checking for non-trivial common divisors. */ static __isl_give isl_schedule_node *carry(__isl_take isl_schedule_node *node, struct isl_sched_graph *graph, int fallback, int coincidence) { … } /* Construct a schedule row for each node such that as many validity dependences * as possible are carried and then continue with the next band. * Do so as a fallback for the Pluto-like scheduler. * If "coincidence" is set, then try and carry coincidence edges as well. */ static __isl_give isl_schedule_node *carry_fallback( __isl_take isl_schedule_node *node, struct isl_sched_graph *graph, int coincidence) { … } /* Construct a schedule row for each node such that as many validity dependences * as possible are carried and then continue with the next band. * Do so for the case where the Feautrier scheduler was selected * by the user. */ static __isl_give isl_schedule_node *carry_feautrier( __isl_take isl_schedule_node *node, struct isl_sched_graph *graph) { … } /* Construct a schedule row for each node such that as many validity dependences * as possible are carried and then continue with the next band. * Do so as a fallback for the Pluto-like scheduler. */ static __isl_give isl_schedule_node *carry_dependences( __isl_take isl_schedule_node *node, struct isl_sched_graph *graph) { … } /* Construct a schedule row for each node such that as many validity or * coincidence dependences as possible are carried and * then continue with the next band. * Do so as a fallback for the Pluto-like scheduler. */ static __isl_give isl_schedule_node *carry_coincidence( __isl_take isl_schedule_node *node, struct isl_sched_graph *graph) { … } /* Topologically sort statements mapped to the same schedule iteration * and add insert a sequence node in front of "node" * corresponding to this order. * If "initialized" is set, then it may be assumed that * isl_sched_graph_compute_maxvar * has been called on the current band. Otherwise, call * isl_sched_graph_compute_maxvar if and before carry_dependences gets called. * * If it turns out to be impossible to sort the statements apart, * because different dependences impose different orderings * on the statements, then we extend the schedule such that * it carries at least one more dependence. */ static __isl_give isl_schedule_node *sort_statements( __isl_take isl_schedule_node *node, struct isl_sched_graph *graph, int initialized) { … } /* Are there any (non-empty) (conditional) validity edges in the graph? */ static int has_validity_edges(struct isl_sched_graph *graph) { … } /* Should we apply a Feautrier step? * That is, did the user request the Feautrier algorithm and are * there any validity dependences (left)? */ static int need_feautrier_step(isl_ctx *ctx, struct isl_sched_graph *graph) { … } /* Compute a schedule for a connected dependence graph using Feautrier's * multi-dimensional scheduling algorithm and return the updated schedule node. * * The original algorithm is described in [1]. * The main idea is to minimize the number of scheduling dimensions, by * trying to satisfy as many dependences as possible per scheduling dimension. * * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling * Problem, Part II: Multi-Dimensional Time. * In Intl. Journal of Parallel Programming, 1992. */ static __isl_give isl_schedule_node *compute_schedule_wcc_feautrier( isl_schedule_node *node, struct isl_sched_graph *graph) { … } /* Turn off the "local" bit on all (condition) edges. */ static void clear_local_edges(struct isl_sched_graph *graph) { … } /* Does "graph" have both condition and conditional validity edges? */ static int need_condition_check(struct isl_sched_graph *graph) { … } /* Does "graph" contain any coincidence edge? */ static int has_any_coincidence(struct isl_sched_graph *graph) { … } /* Extract the final schedule row as a map with the iteration domain * of "node" as domain. */ static __isl_give isl_map *final_row(struct isl_sched_node *node) { … } /* Is the conditional validity dependence in the edge with index "edge_index" * violated by the latest (i.e., final) row of the schedule? * That is, is i scheduled after j * for any conditional validity dependence i -> j? */ static int is_violated(struct isl_sched_graph *graph, int edge_index) { … } /* Does "graph" have any satisfied condition edges that * are adjacent to the conditional validity constraint with * domain "conditional_source" and range "conditional_sink"? * * A satisfied condition is one that is not local. * If a condition was forced to be local already (i.e., marked as local) * then there is no need to check if it is in fact local. * * Additionally, mark all adjacent condition edges found as local. */ static int has_adjacent_true_conditions(struct isl_sched_graph *graph, __isl_keep isl_union_set *conditional_source, __isl_keep isl_union_set *conditional_sink) { … } /* Are there any violated conditional validity dependences with * adjacent condition dependences that are not local with respect * to the current schedule? * That is, is the conditional validity constraint violated? * * Additionally, mark all those adjacent condition dependences as local. * We also mark those adjacent condition dependences that were not marked * as local before, but just happened to be local already. This ensures * that they remain local if the schedule is recomputed. * * We first collect domain and range of all violated conditional validity * dependences and then check if there are any adjacent non-local * condition dependences. */ static int has_violated_conditional_constraint(isl_ctx *ctx, struct isl_sched_graph *graph) { … } /* Examine the current band (the rows between graph->band_start and * graph->n_total_row), deciding whether to drop it or add it to "node" * and then continue with the computation of the next band, if any. * If "initialized" is set, then it may be assumed that * isl_sched_graph_compute_maxvar * has been called on the current band. Otherwise, call * isl_sched_graph_compute_maxvar if and before carry_dependences gets called. * * The caller keeps looking for a new row as long as * graph->n_row < graph->maxvar. If the latest attempt to find * such a row failed (i.e., we still have graph->n_row < graph->maxvar), * then we either * - split between SCCs and start over (assuming we found an interesting * pair of SCCs between which to split) * - continue with the next band (assuming the current band has at least * one row) * - if there is more than one SCC left, then split along all SCCs * - if outer coincidence needs to be enforced, then try to carry as many * validity or coincidence dependences as possible and * continue with the next band * - try to carry as many validity dependences as possible and * continue with the next band * In each case, we first insert a band node in the schedule tree * if any rows have been computed. * * If the caller managed to complete the schedule and the current band * is empty, then finish off by topologically * sorting the statements based on the remaining dependences. * If, on the other hand, the current band has at least one row, * then continue with the next band. Note that this next band * will necessarily be empty, but the graph may still be split up * into weakly connected components before arriving back here. */ __isl_give isl_schedule_node *isl_schedule_node_compute_finish_band( __isl_take isl_schedule_node *node, struct isl_sched_graph *graph, int initialized) { … } /* Construct a band of schedule rows for a connected dependence graph. * The caller is responsible for determining the strongly connected * components and calling isl_sched_graph_compute_maxvar first. * * We try to find a sequence of as many schedule rows as possible that result * in non-negative dependence distances (independent of the previous rows * in the sequence, i.e., such that the sequence is tilable), with as * many of the initial rows as possible satisfying the coincidence constraints. * The computation stops if we can't find any more rows or if we have found * all the rows we wanted to find. * * If ctx->opt->schedule_outer_coincidence is set, then we force the * outermost dimension to satisfy the coincidence constraints. If this * turns out to be impossible, we fall back on the general scheme above * and try to carry as many dependences as possible. * * If "graph" contains both condition and conditional validity dependences, * then we need to check that that the conditional schedule constraint * is satisfied, i.e., there are no violated conditional validity dependences * that are adjacent to any non-local condition dependences. * If there are, then we mark all those adjacent condition dependences * as local and recompute the current band. Those dependences that * are marked local will then be forced to be local. * The initial computation is performed with no dependences marked as local. * If we are lucky, then there will be no violated conditional validity * dependences adjacent to any non-local condition dependences. * Otherwise, we mark some additional condition dependences as local and * recompute. We continue this process until there are no violations left or * until we are no longer able to compute a schedule. * Since there are only a finite number of dependences, * there will only be a finite number of iterations. */ isl_stat isl_schedule_node_compute_wcc_band(isl_ctx *ctx, struct isl_sched_graph *graph) { … } /* Compute a schedule for a connected dependence graph by considering * the graph as a whole and return the updated schedule node. * * The actual schedule rows of the current band are computed by * isl_schedule_node_compute_wcc_band. isl_schedule_node_compute_finish_band * takes care of integrating the band into "node" and continuing * the computation. */ static __isl_give isl_schedule_node *compute_schedule_wcc_whole( __isl_take isl_schedule_node *node, struct isl_sched_graph *graph) { … } /* Compute a schedule for a connected dependence graph and return * the updated schedule node. * * If Feautrier's algorithm is selected, we first recursively try to satisfy * as many validity dependences as possible. When all validity dependences * are satisfied we extend the schedule to a full-dimensional schedule. * * Call compute_schedule_wcc_whole or isl_schedule_node_compute_wcc_clustering * depending on whether the user has selected the option to try and * compute a schedule for the entire (weakly connected) component first. * If there is only a single strongly connected component (SCC), then * there is no point in trying to combine SCCs * in isl_schedule_node_compute_wcc_clustering, so compute_schedule_wcc_whole * is called instead. */ static __isl_give isl_schedule_node *compute_schedule_wcc( __isl_take isl_schedule_node *node, struct isl_sched_graph *graph) { … } /* Compute a schedule for each group of nodes identified by node->scc * separately and then combine them in a sequence node (or as set node * if graph->weak is set) inserted at position "node" of the schedule tree. * Return the updated schedule node. * * If "wcc" is set then each of the groups belongs to a single * weakly connected component in the dependence graph so that * there is no need for compute_sub_schedule to look for weakly * connected components. * * If a set node would be introduced and if the number of components * is equal to the number of nodes, then check if the schedule * is already complete. If so, a redundant set node would be introduced * (without any further descendants) stating that the statements * can be executed in arbitrary order, which is also expressed * by the absence of any node. Refrain from inserting any nodes * in this case and simply return. */ static __isl_give isl_schedule_node *compute_component_schedule( __isl_take isl_schedule_node *node, struct isl_sched_graph *graph, int wcc) { … } /* Compute a schedule for the given dependence graph and insert it at "node". * Return the updated schedule node. * * We first check if the graph is connected (through validity and conditional * validity dependences) and, if not, compute a schedule * for each component separately. * If the schedule_serialize_sccs option is set, then we check for strongly * connected components instead and compute a separate schedule for * each such strongly connected component. */ static __isl_give isl_schedule_node *compute_schedule(isl_schedule_node *node, struct isl_sched_graph *graph) { … } /* Compute a schedule on sc->domain that respects the given schedule * constraints. * * In particular, the schedule respects all the validity dependences. * If the default isl scheduling algorithm is used, it tries to minimize * the dependence distances over the proximity dependences. * If Feautrier's scheduling algorithm is used, the proximity dependence * distances are only minimized during the extension to a full-dimensional * schedule. * * If there are any condition and conditional validity dependences, * then the conditional validity dependences may be violated inside * a tilable band, provided they have no adjacent non-local * condition dependences. */ __isl_give isl_schedule *isl_schedule_constraints_compute_schedule( __isl_take isl_schedule_constraints *sc) { … } /* Compute a schedule for the given union of domains that respects * all the validity dependences and minimizes * the dependence distances over the proximity dependences. * * This function is kept for backward compatibility. */ __isl_give isl_schedule *isl_union_set_compute_schedule( __isl_take isl_union_set *domain, __isl_take isl_union_map *validity, __isl_take isl_union_map *proximity) { … }
Codebase Browser
llvm