/* * Copyright 2013-2014 Ecole Normale Superieure * Copyright 2014 INRIA Rocquencourt * Copyright 2016 Sven Verdoolaege * * Use of this software is governed by the MIT license * * Written by Sven Verdoolaege, * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt, * B.P. 105 - 78153 Le Chesnay, France */ #include <isl/id.h> #include <isl/val.h> #include <isl/space.h> #include <isl/set.h> #include <isl_schedule_band.h> #include <isl_schedule_private.h> #include <isl_schedule_node_private.h> /* Create a new schedule node in the given schedule, point at the given * tree with given ancestors and child positions. * "child_pos" may be NULL if there are no ancestors. */ __isl_give isl_schedule_node *isl_schedule_node_alloc( __isl_take isl_schedule *schedule, __isl_take isl_schedule_tree *tree, __isl_take isl_schedule_tree_list *ancestors, int *child_pos) { … } /* Return a pointer to the root of a schedule tree with as single * node a domain node with the given domain. */ __isl_give isl_schedule_node *isl_schedule_node_from_domain( __isl_take isl_union_set *domain) { … } /* Return a pointer to the root of a schedule tree with as single * node a extension node with the given extension. */ __isl_give isl_schedule_node *isl_schedule_node_from_extension( __isl_take isl_union_map *extension) { … } /* Return the isl_ctx to which "node" belongs. */ isl_ctx *isl_schedule_node_get_ctx(__isl_keep isl_schedule_node *node) { … } /* Return a pointer to the leaf of the schedule into which "node" points. */ __isl_keep isl_schedule_tree *isl_schedule_node_peek_leaf( __isl_keep isl_schedule_node *node) { … } /* Return a copy of the leaf of the schedule into which "node" points. */ __isl_give isl_schedule_tree *isl_schedule_node_get_leaf( __isl_keep isl_schedule_node *node) { … } /* Return the type of the node or isl_schedule_node_error on error. */ enum isl_schedule_node_type isl_schedule_node_get_type( __isl_keep isl_schedule_node *node) { … } /* Return the type of the parent of "node" or isl_schedule_node_error on error. */ enum isl_schedule_node_type isl_schedule_node_get_parent_type( __isl_keep isl_schedule_node *node) { … } /* Return a copy of the subtree that this node points to. */ __isl_give isl_schedule_tree *isl_schedule_node_get_tree( __isl_keep isl_schedule_node *node) { … } /* Return a copy of the schedule into which "node" points. */ __isl_give isl_schedule *isl_schedule_node_get_schedule( __isl_keep isl_schedule_node *node) { … } /* Return a fresh copy of "node". */ __isl_give isl_schedule_node *isl_schedule_node_dup( __isl_keep isl_schedule_node *node) { … } /* Return an isl_schedule_node that is equal to "node" and that has only * a single reference. */ __isl_give isl_schedule_node *isl_schedule_node_cow( __isl_take isl_schedule_node *node) { … } /* Return a new reference to "node". */ __isl_give isl_schedule_node *isl_schedule_node_copy( __isl_keep isl_schedule_node *node) { … } /* Free "node" and return NULL. */ __isl_null isl_schedule_node *isl_schedule_node_free( __isl_take isl_schedule_node *node) { … } /* Do "node1" and "node2" point to the same position in the same * schedule? */ isl_bool isl_schedule_node_is_equal(__isl_keep isl_schedule_node *node1, __isl_keep isl_schedule_node *node2) { … } /* Return the number of outer schedule dimensions of "node" * in its schedule tree. * * Return isl_size_error on error. */ isl_size isl_schedule_node_get_schedule_depth( __isl_keep isl_schedule_node *node) { … } /* Internal data structure for * isl_schedule_node_get_prefix_schedule_union_pw_multi_aff * * "initialized" is set if the filter field has been initialized. * If "universe_domain" is not set, then the collected filter is intersected * with the domain of the root domain node. * "universe_filter" is set if we are only collecting the universes of filters * "collect_prefix" is set if we are collecting prefixes. * "filter" collects all outer filters and is NULL until "initialized" is set. * "prefix" collects all outer band partial schedules (if "collect_prefix" * is set). If it is used, then it is initialized by the caller * of collect_filter_prefix to a zero-dimensional function. */ struct isl_schedule_node_get_filter_prefix_data { … }; static isl_stat collect_filter_prefix(__isl_keep isl_schedule_tree_list *list, int n, struct isl_schedule_node_get_filter_prefix_data *data); /* Update the filter and prefix information in "data" based on the first "n" * elements in "list" and the expansion tree root "tree". * * We first collect the information from the elements in "list", * initializing the filter based on the domain of the expansion. * Then we map the results to the expanded space and combined them * with the results already in "data". */ static isl_stat collect_filter_prefix_expansion( __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_tree_list *list, int n, struct isl_schedule_node_get_filter_prefix_data *data) { … } /* Update the filter information in "data" based on the first "n" * elements in "list" and the extension tree root "tree", in case * data->universe_domain is set and data->collect_prefix is not. * * We collect the universe domain of the elements in "list" and * add it to the universe range of the extension (intersected * with the already collected filter, if any). */ static isl_stat collect_universe_domain_extension( __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_tree_list *list, int n, struct isl_schedule_node_get_filter_prefix_data *data) { … } /* Update "data" based on the tree node "tree" in case "data" has * not been initialized yet. * * Return 0 on success and -1 on error. * * If "tree" is a filter, then we set data->filter to this filter * (or its universe). * If "tree" is a domain, then this means we have reached the root * of the schedule tree without being able to extract any information. * We therefore initialize data->filter to the universe of the domain, * or the domain itself if data->universe_domain is not set. * If "tree" is a band with at least one member, then we set data->filter * to the universe of the schedule domain and replace the zero-dimensional * data->prefix by the band schedule (if data->collect_prefix is set). */ static isl_stat collect_filter_prefix_init(__isl_keep isl_schedule_tree *tree, struct isl_schedule_node_get_filter_prefix_data *data) { … } /* Update "data" based on the tree node "tree" in case "data" has * already been initialized. * * Return 0 on success and -1 on error. * * If "tree" is a domain and data->universe_domain is not set, then * intersect data->filter with the domain. * If "tree" is a filter, then we intersect data->filter with this filter * (or its universe). * If "tree" is a band with at least one member and data->collect_prefix * is set, then we extend data->prefix with the band schedule. * If "tree" is an extension, then we make sure that we are not collecting * information on any extended domain elements. */ static isl_stat collect_filter_prefix_update(__isl_keep isl_schedule_tree *tree, struct isl_schedule_node_get_filter_prefix_data *data) { … } /* Collect filter and/or prefix information from the first "n" * elements in "list" (which represent the ancestors of a node). * Store the results in "data". * * Extension nodes are only supported if they do not affect the outcome, * i.e., if we are collecting information on non-extended domain elements, * or if we are collecting the universe domain (without prefix). * * Return 0 on success and -1 on error. * * We traverse the list from innermost ancestor (last element) * to outermost ancestor (first element), calling collect_filter_prefix_init * on each node as long as we have not been able to extract any information * yet and collect_filter_prefix_update afterwards. * If we come across an expansion node, then we interrupt the traversal * and call collect_filter_prefix_expansion to restart the traversal * over the remaining ancestors and to combine the results with those * that have already been collected. * If we come across an extension node and we are only computing * the universe domain, then we interrupt the traversal and call * collect_universe_domain_extension to restart the traversal * over the remaining ancestors and to combine the results with those * that have already been collected. * On successful return, data->initialized will be set since the outermost * ancestor is a domain node, which always results in an initialization. */ static isl_stat collect_filter_prefix(__isl_keep isl_schedule_tree_list *list, int n, struct isl_schedule_node_get_filter_prefix_data *data) { … } /* Return the concatenation of the partial schedules of all outer band * nodes of "node" interesected with all outer filters * as an isl_multi_union_pw_aff. * None of the ancestors of "node" may be an extension node, unless * there is also a filter ancestor that filters out all the extended * domain elements. * * If "node" is pointing at the root of the schedule tree, then * there are no domain elements reaching the current node, so * we return an empty result. * * We collect all the filters and partial schedules in collect_filter_prefix * and intersect the domain of the combined schedule with the combined filter. */ __isl_give isl_multi_union_pw_aff * isl_schedule_node_get_prefix_schedule_multi_union_pw_aff( __isl_keep isl_schedule_node *node) { … } /* Return the concatenation of the partial schedules of all outer band * nodes of "node" interesected with all outer filters * as an isl_union_pw_multi_aff. * None of the ancestors of "node" may be an extension node, unless * there is also a filter ancestor that filters out all the extended * domain elements. * * If "node" is pointing at the root of the schedule tree, then * there are no domain elements reaching the current node, so * we return an empty result. * * We collect all the filters and partial schedules in collect_filter_prefix. * The partial schedules are collected as an isl_multi_union_pw_aff. * If this isl_multi_union_pw_aff is zero-dimensional, then it does not * contain any domain information, so we construct the isl_union_pw_multi_aff * result as a zero-dimensional function on the collected filter. * Otherwise, we convert the isl_multi_union_pw_aff to * an isl_multi_union_pw_aff and intersect the domain with the filter. */ __isl_give isl_union_pw_multi_aff * isl_schedule_node_get_prefix_schedule_union_pw_multi_aff( __isl_keep isl_schedule_node *node) { … } /* Return the concatenation of the partial schedules of all outer band * nodes of "node" interesected with all outer filters * as an isl_union_map. */ __isl_give isl_union_map *isl_schedule_node_get_prefix_schedule_union_map( __isl_keep isl_schedule_node *node) { … } /* Return the concatenation of the partial schedules of all outer band * nodes of "node" intersected with all outer domain constraints. * None of the ancestors of "node" may be an extension node, unless * there is also a filter ancestor that filters out all the extended * domain elements. * * Essentially, this function intersects the domain of the output * of isl_schedule_node_get_prefix_schedule_union_map with the output * of isl_schedule_node_get_domain, except that it only traverses * the ancestors of "node" once. */ __isl_give isl_union_map *isl_schedule_node_get_prefix_schedule_relation( __isl_keep isl_schedule_node *node) { … } /* Return the domain elements that reach "node". * * If "node" is pointing at the root of the schedule tree, then * there are no domain elements reaching the current node, so * we return an empty result. * None of the ancestors of "node" may be an extension node, unless * there is also a filter ancestor that filters out all the extended * domain elements. * * Otherwise, we collect all filters reaching the node, * intersected with the root domain in collect_filter_prefix. */ __isl_give isl_union_set *isl_schedule_node_get_domain( __isl_keep isl_schedule_node *node) { … } /* Return the union of universe sets of the domain elements that reach "node". * * If "node" is pointing at the root of the schedule tree, then * there are no domain elements reaching the current node, so * we return an empty result. * * Otherwise, we collect the universes of all filters reaching the node * in collect_filter_prefix. */ __isl_give isl_union_set *isl_schedule_node_get_universe_domain( __isl_keep isl_schedule_node *node) { … } /* Return the subtree schedule of "node". * * Since isl_schedule_tree_get_subtree_schedule_union_map does not handle * trees that do not contain any schedule information, we first * move down to the first relevant descendant and handle leaves ourselves. * * If the subtree rooted at "node" contains any expansion nodes, then * the returned subtree schedule is formulated in terms of the expanded * domains. * The subtree is not allowed to contain any extension nodes. */ __isl_give isl_union_map *isl_schedule_node_get_subtree_schedule_union_map( __isl_keep isl_schedule_node *node) { … } /* Return the number of ancestors of "node" in its schedule tree. */ isl_size isl_schedule_node_get_tree_depth(__isl_keep isl_schedule_node *node) { … } /* Does "node" have a parent? * * That is, does it point to any node of the schedule other than the root? */ isl_bool isl_schedule_node_has_parent(__isl_keep isl_schedule_node *node) { … } /* Return the position of "node" among the children of its parent. */ isl_size isl_schedule_node_get_child_position( __isl_keep isl_schedule_node *node) { … } /* Does the parent (if any) of "node" have any children with a smaller child * position than this one? */ isl_bool isl_schedule_node_has_previous_sibling( __isl_keep isl_schedule_node *node) { … } /* Does the parent (if any) of "node" have any children with a greater child * position than this one? */ isl_bool isl_schedule_node_has_next_sibling(__isl_keep isl_schedule_node *node) { … } /* Does "node" have any children? * * Any node other than the leaf nodes is considered to have at least * one child, even if the corresponding isl_schedule_tree does not * have any children. */ isl_bool isl_schedule_node_has_children(__isl_keep isl_schedule_node *node) { … } /* Return the number of children of "node"? * * Any node other than the leaf nodes is considered to have at least * one child, even if the corresponding isl_schedule_tree does not * have any children. That is, the number of children of "node" is * only zero if its tree is the explicit empty tree. Otherwise, * if the isl_schedule_tree has any children, then it is equal * to the number of children of "node". If it has zero children, * then "node" still has a leaf node as child. */ isl_size isl_schedule_node_n_children(__isl_keep isl_schedule_node *node) { … } /* Move the "node" pointer to the ancestor of the given generation * of the node it currently points to, where generation 0 is the node * itself and generation 1 is its parent. */ __isl_give isl_schedule_node *isl_schedule_node_ancestor( __isl_take isl_schedule_node *node, int generation) { … } /* Move the "node" pointer to the parent of the node it currently points to. */ __isl_give isl_schedule_node *isl_schedule_node_parent( __isl_take isl_schedule_node *node) { … } /* Move the "node" pointer to the parent of its parent. */ __isl_give isl_schedule_node *isl_schedule_node_grandparent( __isl_take isl_schedule_node *node) { … } /* Move the "node" pointer to the root of its schedule tree. */ __isl_give isl_schedule_node *isl_schedule_node_root( __isl_take isl_schedule_node *node) { … } /* Move the "node" pointer to the child at position "pos" of the node * it currently points to. */ __isl_give isl_schedule_node *isl_schedule_node_child( __isl_take isl_schedule_node *node, int pos) { … } /* Move the "node" pointer to the child at position "pos2" of the child * at position "pos1". */ __isl_give isl_schedule_node *isl_schedule_node_grandchild( __isl_take isl_schedule_node *node, int pos1, int pos2) { … } /* Move the "node" pointer to the first child of the node * it currently points to. */ __isl_give isl_schedule_node *isl_schedule_node_first_child( __isl_take isl_schedule_node *node) { … } /* Move the "node" pointer to the child of this node's parent in * the previous child position. */ __isl_give isl_schedule_node *isl_schedule_node_previous_sibling( __isl_take isl_schedule_node *node) { … } /* Move the "node" pointer to the child of this node's parent in * the next child position. */ __isl_give isl_schedule_node *isl_schedule_node_next_sibling( __isl_take isl_schedule_node *node) { … } /* Return a copy to the child at position "pos" of "node". */ __isl_give isl_schedule_node *isl_schedule_node_get_child( __isl_keep isl_schedule_node *node, int pos) { … } /* Traverse the descendant of "node" in depth-first order, including * "node" itself. Call "enter" whenever a node is entered and "leave" * whenever a node is left. The callback "enter" is responsible * for moving to the deepest initial subtree of its argument that * should be traversed. */ static __isl_give isl_schedule_node *traverse( __isl_take isl_schedule_node *node, __isl_give isl_schedule_node *(*enter)( __isl_take isl_schedule_node *node, void *user), __isl_give isl_schedule_node *(*leave)( __isl_take isl_schedule_node *node, void *user), void *user) { … } /* Internal data structure for isl_schedule_node_foreach_descendant_top_down. * * "fn" is the user-specified callback function. * "user" is the user-specified argument for the callback. */ struct isl_schedule_node_preorder_data { … }; /* Callback for "traverse" to enter a node and to move * to the deepest initial subtree that should be traversed * for use in a preorder visit. * * If the user callback returns a negative value, then we abort * the traversal. If this callback returns zero, then we skip * the subtree rooted at the current node. Otherwise, we move * down to the first child and repeat the process until a leaf * is reached. */ static __isl_give isl_schedule_node *preorder_enter( __isl_take isl_schedule_node *node, void *user) { … } /* Callback for "traverse" to leave a node * for use in a preorder visit. * Since we already visited the node when we entered it, * we do not need to do anything here. */ static __isl_give isl_schedule_node *preorder_leave( __isl_take isl_schedule_node *node, void *user) { … } /* Traverse the descendants of "node" (including the node itself) * in depth first preorder. * * If "fn" returns isl_bool_error on any of the nodes, * then the traversal is aborted. * If "fn" returns isl_bool_false on any of the nodes, then the subtree rooted * at that node is skipped. * * Return isl_stat_ok on success and isl_stat_error on failure. */ isl_stat isl_schedule_node_foreach_descendant_top_down( __isl_keep isl_schedule_node *node, isl_bool (*fn)(__isl_keep isl_schedule_node *node, void *user), void *user) { … } /* Internal data structure for isl_schedule_node_every_descendant. * * "test" is the user-specified callback function. * "user" is the user-specified callback function argument. * * "failed" is initialized to 0 and set to 1 if "test" fails * on any node. */ struct isl_union_map_every_data { … }; /* isl_schedule_node_foreach_descendant_top_down callback * that sets data->failed if data->test returns false and * subsequently aborts the traversal. */ static isl_bool call_every(__isl_keep isl_schedule_node *node, void *user) { … } /* Does "test" succeed on every descendant of "node" (including "node" itself)? */ isl_bool isl_schedule_node_every_descendant(__isl_keep isl_schedule_node *node, isl_bool (*test)(__isl_keep isl_schedule_node *node, void *user), void *user) { … } /* Internal data structure for isl_schedule_node_map_descendant_bottom_up. * * "fn" is the user-specified callback function. * "user" is the user-specified argument for the callback. */ struct isl_schedule_node_postorder_data { … }; /* Callback for "traverse" to enter a node and to move * to the deepest initial subtree that should be traversed * for use in a postorder visit. * * Since we are performing a postorder visit, we only need * to move to the deepest initial leaf here. */ static __isl_give isl_schedule_node *postorder_enter( __isl_take isl_schedule_node *node, void *user) { … } /* Callback for "traverse" to leave a node * for use in a postorder visit. * * Since we are performing a postorder visit, we need * to call the user callback here. */ static __isl_give isl_schedule_node *postorder_leave( __isl_take isl_schedule_node *node, void *user) { … } /* Traverse the descendants of "node" (including the node itself) * in depth first postorder, allowing the user to modify the visited node. * The traversal continues from the node returned by the callback function. * It is the responsibility of the user to ensure that this does not * lead to an infinite loop. It is safest to always return a pointer * to the same position (same ancestors and child positions) as the input node. */ __isl_give isl_schedule_node *isl_schedule_node_map_descendant_bottom_up( __isl_take isl_schedule_node *node, __isl_give isl_schedule_node *(*fn)(__isl_take isl_schedule_node *node, void *user), void *user) { … } /* Traverse the ancestors of "node" from the root down to and including * the parent of "node", calling "fn" on each of them. * * If "fn" returns -1 on any of the nodes, then the traversal is aborted. * * Return 0 on success and -1 on failure. */ isl_stat isl_schedule_node_foreach_ancestor_top_down( __isl_keep isl_schedule_node *node, isl_stat (*fn)(__isl_keep isl_schedule_node *node, void *user), void *user) { … } /* Is any node in the subtree rooted at "node" anchored? * That is, do any of these nodes reference the outer band nodes? */ isl_bool isl_schedule_node_is_subtree_anchored( __isl_keep isl_schedule_node *node) { … } /* Return the number of members in the given band node. */ isl_size isl_schedule_node_band_n_member(__isl_keep isl_schedule_node *node) { … } /* Is the band member at position "pos" of the band node "node" * marked coincident? */ isl_bool isl_schedule_node_band_member_get_coincident( __isl_keep isl_schedule_node *node, int pos) { … } /* Mark the band member at position "pos" the band node "node" * as being coincident or not according to "coincident". */ __isl_give isl_schedule_node *isl_schedule_node_band_member_set_coincident( __isl_take isl_schedule_node *node, int pos, int coincident) { … } /* Is the band node "node" marked permutable? */ isl_bool isl_schedule_node_band_get_permutable( __isl_keep isl_schedule_node *node) { … } /* Mark the band node "node" permutable or not according to "permutable"? */ __isl_give isl_schedule_node *isl_schedule_node_band_set_permutable( __isl_take isl_schedule_node *node, int permutable) { … } /* Return the schedule space of the band node. */ __isl_give isl_space *isl_schedule_node_band_get_space( __isl_keep isl_schedule_node *node) { … } /* Return the schedule of the band node in isolation. */ __isl_give isl_multi_union_pw_aff *isl_schedule_node_band_get_partial_schedule( __isl_keep isl_schedule_node *node) { … } /* Return the schedule of the band node in isolation in the form of * an isl_union_map. * * If the band does not have any members, then we construct a universe map * with the universe of the domain elements reaching the node as domain. * Otherwise, we extract an isl_multi_union_pw_aff representation and * convert that to an isl_union_map. */ __isl_give isl_union_map *isl_schedule_node_band_get_partial_schedule_union_map( __isl_keep isl_schedule_node *node) { … } /* Return the loop AST generation type for the band member of band node "node" * at position "pos". */ enum isl_ast_loop_type isl_schedule_node_band_member_get_ast_loop_type( __isl_keep isl_schedule_node *node, int pos) { … } /* Set the loop AST generation type for the band member of band node "node" * at position "pos" to "type". */ __isl_give isl_schedule_node *isl_schedule_node_band_member_set_ast_loop_type( __isl_take isl_schedule_node *node, int pos, enum isl_ast_loop_type type) { … } /* Return the loop AST generation type for the band member of band node "node" * at position "pos" for the isolated part. */ enum isl_ast_loop_type isl_schedule_node_band_member_get_isolate_ast_loop_type( __isl_keep isl_schedule_node *node, int pos) { … } /* Set the loop AST generation type for the band member of band node "node" * at position "pos" for the isolated part to "type". */ __isl_give isl_schedule_node * isl_schedule_node_band_member_set_isolate_ast_loop_type( __isl_take isl_schedule_node *node, int pos, enum isl_ast_loop_type type) { … } /* Return the AST build options associated to band node "node". */ __isl_give isl_union_set *isl_schedule_node_band_get_ast_build_options( __isl_keep isl_schedule_node *node) { … } /* Replace the AST build options associated to band node "node" by "options". */ __isl_give isl_schedule_node *isl_schedule_node_band_set_ast_build_options( __isl_take isl_schedule_node *node, __isl_take isl_union_set *options) { … } /* Return the "isolate" option associated to band node "node". */ __isl_give isl_set *isl_schedule_node_band_get_ast_isolate_option( __isl_keep isl_schedule_node *node) { … } /* Make sure that that spaces of "node" and "mv" are the same. * Return -1 on error, reporting the error to the user. */ static int check_space_multi_val(__isl_keep isl_schedule_node *node, __isl_keep isl_multi_val *mv) { … } /* Multiply the partial schedule of the band node "node" * with the factors in "mv". */ __isl_give isl_schedule_node *isl_schedule_node_band_scale( __isl_take isl_schedule_node *node, __isl_take isl_multi_val *mv) { … } /* Divide the partial schedule of the band node "node" * by the factors in "mv". */ __isl_give isl_schedule_node *isl_schedule_node_band_scale_down( __isl_take isl_schedule_node *node, __isl_take isl_multi_val *mv) { … } /* Reduce the partial schedule of the band node "node" * modulo the factors in "mv". */ __isl_give isl_schedule_node *isl_schedule_node_band_mod( __isl_take isl_schedule_node *node, __isl_take isl_multi_val *mv) { … } /* Make sure that that spaces of "node" and "mupa" are the same. * Return isl_stat_error on error, reporting the error to the user. */ static isl_stat check_space_multi_union_pw_aff( __isl_keep isl_schedule_node *node, __isl_keep isl_multi_union_pw_aff *mupa) { … } /* Shift the partial schedule of the band node "node" by "shift". */ __isl_give isl_schedule_node *isl_schedule_node_band_shift( __isl_take isl_schedule_node *node, __isl_take isl_multi_union_pw_aff *shift) { … } /* Tile "node" with tile sizes "sizes". * * The current node is replaced by two nested nodes corresponding * to the tile dimensions and the point dimensions. * * Return a pointer to the outer (tile) node. * * If any of the descendants of "node" depend on the set of outer band nodes, * then we refuse to tile the node. * * If the scale tile loops option is set, then the tile loops * are scaled by the tile sizes. If the shift point loops option is set, * then the point loops are shifted to start at zero. * In particular, these options affect the tile and point loop schedules * as follows * * scale shift original tile point * * 0 0 i floor(i/s) i * 1 0 i s * floor(i/s) i * 0 1 i floor(i/s) i - s * floor(i/s) * 1 1 i s * floor(i/s) i - s * floor(i/s) */ __isl_give isl_schedule_node *isl_schedule_node_band_tile( __isl_take isl_schedule_node *node, __isl_take isl_multi_val *sizes) { … } /* Move the band node "node" down to all the leaves in the subtree * rooted at "node". * Return a pointer to the node in the resulting tree that is in the same * position as the node pointed to by "node" in the original tree. * * If the node only has a leaf child, then nothing needs to be done. * Otherwise, the child of the node is removed and the result is * appended to all the leaves in the subtree rooted at the original child. * Since the node is moved to the leaves, it needs to be expanded * according to the expansion, if any, defined by that subtree. * In the end, the original node is replaced by the result of * attaching copies of the expanded node to the leaves. * * If any of the nodes in the subtree rooted at "node" depend on * the set of outer band nodes then we refuse to sink the band node. */ __isl_give isl_schedule_node *isl_schedule_node_band_sink( __isl_take isl_schedule_node *node) { … } /* Split "node" into two nested band nodes, one with the first "pos" * dimensions and one with the remaining dimensions. * The schedules of the two band nodes live in anonymous spaces. * The loop AST generation type options and the isolate option * are split over the two band nodes. */ __isl_give isl_schedule_node *isl_schedule_node_band_split( __isl_take isl_schedule_node *node, int pos) { … } /* Return the context of the context node "node". */ __isl_give isl_set *isl_schedule_node_context_get_context( __isl_keep isl_schedule_node *node) { … } /* Return the domain of the domain node "node". */ __isl_give isl_union_set *isl_schedule_node_domain_get_domain( __isl_keep isl_schedule_node *node) { … } /* Return the expansion map of expansion node "node". */ __isl_give isl_union_map *isl_schedule_node_expansion_get_expansion( __isl_keep isl_schedule_node *node) { … } /* Return the contraction of expansion node "node". */ __isl_give isl_union_pw_multi_aff *isl_schedule_node_expansion_get_contraction( __isl_keep isl_schedule_node *node) { … } /* Replace the contraction and the expansion of the expansion node "node" * by "contraction" and "expansion". */ __isl_give isl_schedule_node * isl_schedule_node_expansion_set_contraction_and_expansion( __isl_take isl_schedule_node *node, __isl_take isl_union_pw_multi_aff *contraction, __isl_take isl_union_map *expansion) { … } /* Return the extension of the extension node "node". */ __isl_give isl_union_map *isl_schedule_node_extension_get_extension( __isl_keep isl_schedule_node *node) { … } /* Replace the extension of extension node "node" by "extension". */ __isl_give isl_schedule_node *isl_schedule_node_extension_set_extension( __isl_take isl_schedule_node *node, __isl_take isl_union_map *extension) { … } /* Return the filter of the filter node "node". */ __isl_give isl_union_set *isl_schedule_node_filter_get_filter( __isl_keep isl_schedule_node *node) { … } /* Replace the filter of filter node "node" by "filter". */ __isl_give isl_schedule_node *isl_schedule_node_filter_set_filter( __isl_take isl_schedule_node *node, __isl_take isl_union_set *filter) { … } /* Intersect the filter of filter node "node" with "filter". * * If the filter of the node is already a subset of "filter", * then leave the node unchanged. */ __isl_give isl_schedule_node *isl_schedule_node_filter_intersect_filter( __isl_take isl_schedule_node *node, __isl_take isl_union_set *filter) { … } /* Return the guard of the guard node "node". */ __isl_give isl_set *isl_schedule_node_guard_get_guard( __isl_keep isl_schedule_node *node) { … } /* Return the mark identifier of the mark node "node". */ __isl_give isl_id *isl_schedule_node_mark_get_id( __isl_keep isl_schedule_node *node) { … } /* Check that "node" is a sequence node. */ static isl_stat check_is_sequence(__isl_keep isl_schedule_node *node) { … } /* Replace the child at position "pos" of the sequence node "node" * by the children of sequence root node of "tree". */ __isl_give isl_schedule_node *isl_schedule_node_sequence_splice( __isl_take isl_schedule_node *node, int pos, __isl_take isl_schedule_tree *tree) { … } /* Given a sequence node "node", with a child at position "pos" that * is also a sequence node, attach the children of that node directly * as children of "node" at that position, replacing the original child. * * The filters of these children are intersected with the filter * of the child at position "pos". */ __isl_give isl_schedule_node *isl_schedule_node_sequence_splice_child( __isl_take isl_schedule_node *node, int pos) { … } /* Given a sequence node "node", for each child that is also * (the parent of) a sequence node, attach the children of that node directly * as children of "node" at the position of the child, * replacing this original child. * * Since splicing in a child may change the positions of later children, * iterate through the children from last to first. */ __isl_give isl_schedule_node *isl_schedule_node_sequence_splice_children( __isl_take isl_schedule_node *node) { … } /* Update the ancestors of "node" to point to the tree that "node" * now points to. * That is, replace the child in the original parent that corresponds * to the current tree position by node->tree and continue updating * the ancestors in the same way until the root is reached. * * If "fn" is not NULL, then it is called on each ancestor as we move up * the tree so that it can modify the ancestor before it is added * to the list of ancestors of the modified node. * The additional "pos" argument records the position * of the "tree" argument in the original schedule tree. * * If "node" originally points to a leaf of the schedule tree, then make sure * that in the end it points to a leaf in the updated schedule tree. */ static __isl_give isl_schedule_node *update_ancestors( __isl_take isl_schedule_node *node, __isl_give isl_schedule_tree *(*fn)(__isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_node *pos, void *user), void *user) { … } /* Replace the subtree that "pos" points to by "tree", updating * the ancestors to maintain a consistent state. */ __isl_give isl_schedule_node *isl_schedule_node_graft_tree( __isl_take isl_schedule_node *pos, __isl_take isl_schedule_tree *tree) { … } /* Make sure we can insert a node between "node" and its parent. * Return -1 on error, reporting the reason why we cannot insert a node. */ static int check_insert(__isl_keep isl_schedule_node *node) { … } /* Insert a band node with partial schedule "mupa" between "node" and * its parent. * Return a pointer to the new band node. * * If any of the nodes in the subtree rooted at "node" depend on * the set of outer band nodes then we refuse to insert the band node. */ __isl_give isl_schedule_node *isl_schedule_node_insert_partial_schedule( __isl_take isl_schedule_node *node, __isl_take isl_multi_union_pw_aff *mupa) { … } /* Insert a context node with context "context" between "node" and its parent. * Return a pointer to the new context node. */ __isl_give isl_schedule_node *isl_schedule_node_insert_context( __isl_take isl_schedule_node *node, __isl_take isl_set *context) { … } /* Insert an expansion node with the given "contraction" and "expansion" * between "node" and its parent. * Return a pointer to the new expansion node. * * Typically the domain and range spaces of the expansion are different. * This means that only one of them can refer to the current domain space * in a consistent tree. It is up to the caller to ensure that the tree * returns to a consistent state. */ __isl_give isl_schedule_node *isl_schedule_node_insert_expansion( __isl_take isl_schedule_node *node, __isl_take isl_union_pw_multi_aff *contraction, __isl_take isl_union_map *expansion) { … } /* Insert an extension node with extension "extension" between "node" and * its parent. * Return a pointer to the new extension node. */ __isl_give isl_schedule_node *isl_schedule_node_insert_extension( __isl_take isl_schedule_node *node, __isl_take isl_union_map *extension) { … } /* Insert a filter node with filter "filter" between "node" and its parent. * Return a pointer to the new filter node. */ __isl_give isl_schedule_node *isl_schedule_node_insert_filter( __isl_take isl_schedule_node *node, __isl_take isl_union_set *filter) { … } /* Insert a guard node with guard "guard" between "node" and its parent. * Return a pointer to the new guard node. */ __isl_give isl_schedule_node *isl_schedule_node_insert_guard( __isl_take isl_schedule_node *node, __isl_take isl_set *guard) { … } /* Insert a mark node with mark identifier "mark" between "node" and * its parent. * Return a pointer to the new mark node. */ __isl_give isl_schedule_node *isl_schedule_node_insert_mark( __isl_take isl_schedule_node *node, __isl_take isl_id *mark) { … } /* Attach the current subtree of "node" to a sequence of filter tree nodes * with filters described by "filters", attach this sequence * of filter tree nodes as children to a new tree of type "type" and * replace the original subtree of "node" by this new tree. * Each copy of the original subtree is simplified with respect * to the corresponding filter. */ static __isl_give isl_schedule_node *isl_schedule_node_insert_children( __isl_take isl_schedule_node *node, enum isl_schedule_node_type type, __isl_take isl_union_set_list *filters) { … } /* Insert a sequence node with child filters "filters" between "node" and * its parent. That is, the tree that "node" points to is attached * to each of the child nodes of the filter nodes. * Return a pointer to the new sequence node. */ __isl_give isl_schedule_node *isl_schedule_node_insert_sequence( __isl_take isl_schedule_node *node, __isl_take isl_union_set_list *filters) { … } /* Insert a set node with child filters "filters" between "node" and * its parent. That is, the tree that "node" points to is attached * to each of the child nodes of the filter nodes. * Return a pointer to the new set node. */ __isl_give isl_schedule_node *isl_schedule_node_insert_set( __isl_take isl_schedule_node *node, __isl_take isl_union_set_list *filters) { … } /* Remove "node" from its schedule tree and return a pointer * to the leaf at the same position in the updated schedule tree. * * It is not allowed to remove the root of a schedule tree or * a child of a set or sequence node. */ __isl_give isl_schedule_node *isl_schedule_node_cut( __isl_take isl_schedule_node *node) { … } /* Remove a single node from the schedule tree, attaching the child * of "node" directly to its parent. * Return a pointer to this former child or to the leaf the position * of the original node if there was no child. * It is not allowed to remove the root of a schedule tree, * a set or sequence node, a child of a set or sequence node or * a band node with an anchored subtree. */ __isl_give isl_schedule_node *isl_schedule_node_delete( __isl_take isl_schedule_node *node) { … } /* Internal data structure for the group_ancestor callback. * * If "finished" is set, then we no longer need to modify * any further ancestors. * * "contraction" and "expansion" represent the expansion * that reflects the grouping. * * "domain" contains the domain elements that reach the position * where the grouping is performed. That is, it is the range * of the resulting expansion. * "domain_universe" is the universe of "domain". * "group" is the set of group elements, i.e., the domain * of the resulting expansion. * "group_universe" is the universe of "group". * * "sched" is the schedule for the group elements, in pratice * an identity mapping on "group_universe". * "dim" is the dimension of "sched". */ struct isl_schedule_group_data { … }; /* Is domain covered by data->domain within data->domain_universe? */ static isl_bool locally_covered_by_domain(__isl_keep isl_union_set *domain, struct isl_schedule_group_data *data) { … } /* Update the band tree root "tree" to refer to the group instances * in data->group rather than the original domain elements in data->domain. * "pos" is the position in the original schedule tree where the modified * "tree" will be attached. * * Add the part of the identity schedule on the group instances data->sched * that corresponds to this band node to the band schedule. * If the domain elements that reach the node and that are part * of data->domain_universe are all elements of data->domain (and therefore * replaced by the group instances) then this data->domain_universe * is removed from the domain of the band schedule. */ static __isl_give isl_schedule_tree *group_band( __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_node *pos, struct isl_schedule_group_data *data) { … } /* Drop the parameters in "uset" that are not also in "space". * "n" is the number of parameters in "space". */ static __isl_give isl_union_set *union_set_drop_extra_params( __isl_take isl_union_set *uset, __isl_keep isl_space *space, int n) { … } /* Update the context tree root "tree" to refer to the group instances * in data->group rather than the original domain elements in data->domain. * "pos" is the position in the original schedule tree where the modified * "tree" will be attached. * * We do not actually need to update "tree" since a context node only * refers to the schedule space. However, we may need to update "data" * to not refer to any parameters introduced by the context node. */ static __isl_give isl_schedule_tree *group_context( __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_node *pos, struct isl_schedule_group_data *data) { … } /* Update the domain tree root "tree" to refer to the group instances * in data->group rather than the original domain elements in data->domain. * "pos" is the position in the original schedule tree where the modified * "tree" will be attached. * * We first double-check that all grouped domain elements are actually * part of the root domain and then replace those elements by the group * instances. */ static __isl_give isl_schedule_tree *group_domain( __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_node *pos, struct isl_schedule_group_data *data) { … } /* Update the expansion tree root "tree" to refer to the group instances * in data->group rather than the original domain elements in data->domain. * "pos" is the position in the original schedule tree where the modified * "tree" will be attached. * * Let G_1 -> D_1 be the expansion of "tree" and G_2 -> D_2 the newly * introduced expansion in a descendant of "tree". * We first double-check that D_2 is a subset of D_1. * Then we remove D_2 from the range of G_1 -> D_1 and add the mapping * G_1 -> D_1 . D_2 -> G_2. * Simmilarly, we restrict the domain of the contraction to the universe * of the range of the updated expansion and add G_2 -> D_2 . D_1 -> G_1, * attempting to remove the domain constraints of this additional part. */ static __isl_give isl_schedule_tree *group_expansion( __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_node *pos, struct isl_schedule_group_data *data) { … } /* Update the tree root "tree" to refer to the group instances * in data->group rather than the original domain elements in data->domain. * "pos" is the position in the original schedule tree where the modified * "tree" will be attached. * * If we have come across a domain or expansion node before (data->finished * is set), then we no longer need perform any modifications. * * If "tree" is a filter, then we add data->group_universe to the filter. * We also remove data->domain_universe from the filter if all the domain * elements in this universe that reach the filter node are part of * the elements that are being grouped by data->expansion. * If "tree" is a band, domain or expansion, then it is handled * in a separate function. */ static __isl_give isl_schedule_tree *group_ancestor( __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_node *pos, void *user) { … } /* Group the domain elements that reach "node" into instances * of a single statement with identifier "group_id". * In particular, group the domain elements according to their * prefix schedule. * * That is, introduce an expansion node with as contraction * the prefix schedule (with the target space replaced by "group_id") * and as expansion the inverse of this contraction (with its range * intersected with the domain elements that reach "node"). * The outer nodes are then modified to refer to the group instances * instead of the original domain elements. * * No instance of "group_id" is allowed to reach "node" prior * to the grouping. * No ancestor of "node" is allowed to be an extension node. * * Return a pointer to original node in tree, i.e., the child * of the newly introduced expansion node. */ __isl_give isl_schedule_node *isl_schedule_node_group( __isl_take isl_schedule_node *node, __isl_take isl_id *group_id) { … } /* Compute the gist of the given band node with respect to "context". */ __isl_give isl_schedule_node *isl_schedule_node_band_gist( __isl_take isl_schedule_node *node, __isl_take isl_union_set *context) { … } /* Internal data structure for isl_schedule_node_gist. * "n_expansion" is the number of outer expansion nodes * with respect to the current position * "filters" contains an element for each outer filter, expansion or * extension node with respect to the current position, each representing * the intersection of the previous element and the filter on the filter node * or the expansion/extension of the previous element. * The first element in the original context passed to isl_schedule_node_gist. */ struct isl_node_gist_data { … }; /* Enter the expansion node "node" during a isl_schedule_node_gist traversal. * * In particular, add an extra element to data->filters containing * the expansion of the previous element and replace the expansion * and contraction on "node" by the gist with respect to these filters. * Also keep track of the fact that we have entered another expansion. */ static __isl_give isl_schedule_node *gist_enter_expansion( __isl_take isl_schedule_node *node, struct isl_node_gist_data *data) { … } /* Leave the expansion node "node" during a isl_schedule_node_gist traversal. * * In particular, remove the element in data->filters that was added by * gist_enter_expansion and decrement the number of outer expansions. * * The expansion has already been simplified in gist_enter_expansion. * If this simplification results in an identity expansion, then * it is removed here. */ static __isl_give isl_schedule_node *gist_leave_expansion( __isl_take isl_schedule_node *node, struct isl_node_gist_data *data) { … } /* Enter the extension node "node" during a isl_schedule_node_gist traversal. * * In particular, add an extra element to data->filters containing * the union of the previous element with the additional domain elements * introduced by the extension. */ static __isl_give isl_schedule_node *gist_enter_extension( __isl_take isl_schedule_node *node, struct isl_node_gist_data *data) { … } /* Can we finish gisting at this node? * That is, is the filter on the current filter node a subset of * the original context passed to isl_schedule_node_gist? * If we have gone through any expansions, then we cannot perform * this test since the current domain elements are incomparable * to the domain elements in the original context. */ static isl_bool gist_done(__isl_keep isl_schedule_node *node, struct isl_node_gist_data *data) { … } /* Callback for "traverse" to enter a node and to move * to the deepest initial subtree that should be traversed * by isl_schedule_node_gist. * * The "filters" list is extended by one element each time * we come across a filter node by the result of intersecting * the last element in the list with the filter on the filter node. * * If the filter on the current filter node is a subset of * the original context passed to isl_schedule_node_gist, * then there is no need to go into its subtree since it cannot * be further simplified by the context. The "filters" list is * still extended for consistency, but the actual value of the * added element is immaterial since it will not be used. * * Otherwise, the filter on the current filter node is replaced by * the gist of the original filter with respect to the intersection * of the original context with the intermediate filters. * * If the new element in the "filters" list is empty, then no elements * can reach the descendants of the current filter node. The subtree * underneath the filter node is therefore removed. * * Each expansion node we come across is handled by * gist_enter_expansion. * * Each extension node we come across is handled by * gist_enter_extension. */ static __isl_give isl_schedule_node *gist_enter( __isl_take isl_schedule_node *node, void *user) { … } /* Callback for "traverse" to leave a node for isl_schedule_node_gist. * * In particular, if the current node is a filter node, then we remove * the element on the "filters" list that was added when we entered * the node. There is no need to compute any gist here, since we * already did that when we entered the node. * * Expansion nodes are handled by gist_leave_expansion. * * If the current node is an extension, then remove the element * in data->filters that was added by gist_enter_extension. * * If the current node is a band node, then we compute the gist of * the band node with respect to the intersection of the original context * and the intermediate filters. * * If the current node is a sequence or set node, then some of * the filter children may have become empty and so they are removed. * If only one child is left, then the set or sequence node along with * the single remaining child filter is removed. The filter can be * removed because the filters on a sequence or set node are supposed * to partition the incoming domain instances. * In principle, it should then be impossible for there to be zero * remaining children, but should this happen, we replace the entire * subtree with an empty filter. */ static __isl_give isl_schedule_node *gist_leave( __isl_take isl_schedule_node *node, void *user) { … } /* Compute the gist of the subtree at "node" with respect to * the reaching domain elements in "context". * In particular, compute the gist of all band and filter nodes * in the subtree with respect to "context". Children of set or sequence * nodes that end up with an empty filter are removed completely. * * We keep track of the intersection of "context" with all outer filters * of the current node within the subtree in the final element of "filters". * Initially, this list contains the single element "context" and it is * extended or shortened each time we enter or leave a filter node. */ __isl_give isl_schedule_node *isl_schedule_node_gist( __isl_take isl_schedule_node *node, __isl_take isl_union_set *context) { … } /* Intersect the domain of domain node "node" with "domain". * * If the domain of "node" is already a subset of "domain", * then nothing needs to be changed. * * Otherwise, we replace the domain of the domain node by the intersection * and simplify the subtree rooted at "node" with respect to this intersection. */ __isl_give isl_schedule_node *isl_schedule_node_domain_intersect_domain( __isl_take isl_schedule_node *node, __isl_take isl_union_set *domain) { … } /* Replace the domain of domain node "node" with the gist * of the original domain with respect to the parameter domain "context". */ __isl_give isl_schedule_node *isl_schedule_node_domain_gist_params( __isl_take isl_schedule_node *node, __isl_take isl_set *context) { … } /* Internal data structure for isl_schedule_node_get_subtree_expansion. * "expansions" contains a list of accumulated expansions * for each outer expansion, set or sequence node. The first element * in the list is an identity mapping on the reaching domain elements. * "res" collects the results. */ struct isl_subtree_expansion_data { … }; /* Callback for "traverse" to enter a node and to move * to the deepest initial subtree that should be traversed * by isl_schedule_node_get_subtree_expansion. * * Whenever we come across an expansion node, the last element * of data->expansions is combined with the expansion * on the expansion node. * * Whenever we come across a filter node that is the child * of a set or sequence node, data->expansions is extended * with a new element that restricts the previous element * to the elements selected by the filter. * The previous element can then be reused while backtracking. */ static __isl_give isl_schedule_node *subtree_expansion_enter( __isl_take isl_schedule_node *node, void *user) { … } /* Callback for "traverse" to leave a node for * isl_schedule_node_get_subtree_expansion. * * If we come across a filter node that is the child * of a set or sequence node, then we remove the element * of data->expansions that was added in subtree_expansion_enter. * * If we reach a leaf node, then the accumulated expansion is * added to data->res. */ static __isl_give isl_schedule_node *subtree_expansion_leave( __isl_take isl_schedule_node *node, void *user) { … } /* Return a mapping from the domain elements that reach "node" * to the corresponding domain elements in the leaves of the subtree * rooted at "node" obtained by composing the intermediate expansions. * * We start out with an identity mapping between the domain elements * that reach "node" and compose it with all the expansions * on a path from "node" to a leaf while traversing the subtree. * Within the children of an a sequence or set node, the * accumulated expansion is restricted to the elements selected * by the filter child. */ __isl_give isl_union_map *isl_schedule_node_get_subtree_expansion( __isl_keep isl_schedule_node *node) { … } /* Internal data structure for isl_schedule_node_get_subtree_contraction. * "contractions" contains a list of accumulated contractions * for each outer expansion, set or sequence node. The first element * in the list is an identity mapping on the reaching domain elements. * "res" collects the results. */ struct isl_subtree_contraction_data { … }; /* Callback for "traverse" to enter a node and to move * to the deepest initial subtree that should be traversed * by isl_schedule_node_get_subtree_contraction. * * Whenever we come across an expansion node, the last element * of data->contractions is combined with the contraction * on the expansion node. * * Whenever we come across a filter node that is the child * of a set or sequence node, data->contractions is extended * with a new element that restricts the previous element * to the elements selected by the filter. * The previous element can then be reused while backtracking. */ static __isl_give isl_schedule_node *subtree_contraction_enter( __isl_take isl_schedule_node *node, void *user) { … } /* Callback for "traverse" to leave a node for * isl_schedule_node_get_subtree_contraction. * * If we come across a filter node that is the child * of a set or sequence node, then we remove the element * of data->contractions that was added in subtree_contraction_enter. * * If we reach a leaf node, then the accumulated contraction is * added to data->res. */ static __isl_give isl_schedule_node *subtree_contraction_leave( __isl_take isl_schedule_node *node, void *user) { … } /* Return a mapping from the domain elements in the leaves of the subtree * rooted at "node" to the corresponding domain elements that reach "node" * obtained by composing the intermediate contractions. * * We start out with an identity mapping between the domain elements * that reach "node" and compose it with all the contractions * on a path from "node" to a leaf while traversing the subtree. * Within the children of an a sequence or set node, the * accumulated contraction is restricted to the elements selected * by the filter child. */ __isl_give isl_union_pw_multi_aff *isl_schedule_node_get_subtree_contraction( __isl_keep isl_schedule_node *node) { … } /* Do the nearest "n" ancestors of "node" have the types given in "types" * (starting at the parent of "node")? */ static isl_bool has_ancestors(__isl_keep isl_schedule_node *node, int n, enum isl_schedule_node_type *types) { … } /* Given a node "node" that appears in an extension (i.e., it is the child * of a filter in a sequence inside an extension node), are the spaces * of the extension specified by "extension" disjoint from those * of both the original extension and the domain elements that reach * that original extension? */ static isl_bool is_disjoint_extension(__isl_keep isl_schedule_node *node, __isl_keep isl_union_map *extension) { … } /* Given a node "node" that is governed by an extension node, extend * that extension node with "extension". * * In particular, "node" is the child of a filter in a sequence that * is in turn a child of an extension node. Extend that extension node * with "extension". * * Return a pointer to the parent of the original node (i.e., a filter). */ static __isl_give isl_schedule_node *extend_extension( __isl_take isl_schedule_node *node, __isl_take isl_union_map *extension) { … } /* Return the universe of "uset" if this universe is disjoint from "ref". * Otherwise, return "uset". * * Also check if "uset" itself is disjoint from "ref", reporting * an error if it is not. */ static __isl_give isl_union_set *replace_by_universe_if_disjoint( __isl_take isl_union_set *uset, __isl_keep isl_union_set *ref) { … } /* Insert an extension node on top of "node" with extension "extension". * In addition, insert a filter that separates node from the extension * between the extension node and "node". * Return a pointer to the inserted filter node. * * If "node" already appears in an extension (i.e., if it is the child * of a filter in a sequence inside an extension node), then extend that * extension with "extension" instead. * In this case, a pointer to the original filter node is returned. * Note that if some of the elements in the new extension live in the * same space as those of the original extension or the domain elements * reaching the original extension, then we insert a new extension anyway. * Otherwise, we would have to adjust the filters in the sequence child * of the extension to ensure that the elements in the new extension * are filtered out. */ static __isl_give isl_schedule_node *insert_extension( __isl_take isl_schedule_node *node, __isl_take isl_union_map *extension) { … } /* Replace the subtree that "node" points to by "tree" (which has * a sequence root with two children), except if the parent of "node" * is a sequence as well, in which case "tree" is spliced at the position * of "node" in its parent. * Return a pointer to the child of the "tree_pos" (filter) child of "tree" * in the updated schedule tree. */ static __isl_give isl_schedule_node *graft_or_splice( __isl_take isl_schedule_node *node, __isl_take isl_schedule_tree *tree, int tree_pos) { … } /* Insert a node "graft" into the schedule tree of "node" such that it * is executed before (if "before" is set) or after (if "before" is not set) * the node that "node" points to. * The root of "graft" is an extension node. * Return a pointer to the node that "node" pointed to. * * We first insert an extension node on top of "node" (or extend * the extension node if there already is one), with a filter on "node" * separating it from the extension. * We then insert a filter in the graft to separate it from the original * domain elements and combine the original and new tree in a sequence. * If we have extended an extension node, then the children of this * sequence are spliced in the sequence of the extended extension * at the position where "node" appears in the original extension. * Otherwise, the sequence pair is attached to the new extension node. */ static __isl_give isl_schedule_node *graft_extension( __isl_take isl_schedule_node *node, __isl_take isl_schedule_node *graft, int before) { … } /* Replace the root domain node of "node" by an extension node suitable * for insertion at "pos". * That is, create an extension node that maps the outer band nodes * at "pos" to the domain of the root node of "node" and attach * the child of this root node to the extension node. */ static __isl_give isl_schedule_node *extension_from_domain( __isl_take isl_schedule_node *node, __isl_keep isl_schedule_node *pos) { … } /* Insert a node "graft" into the schedule tree of "node" such that it * is executed before (if "before" is set) or after (if "before" is not set) * the node that "node" points to. * The root of "graft" may be either a domain or an extension node. * In the latter case, the domain of the extension needs to correspond * to the outer band nodes of "node". * The elements of the domain or the range of the extension may not * intersect with the domain elements that reach "node". * The schedule tree of "graft" may not be anchored. * * The schedule tree of "node" is modified to include an extension node * corresponding to the root node of "graft" as a child of the original * parent of "node". The original node that "node" points to and the * child of the root node of "graft" are attached to this extension node * through a sequence, with appropriate filters and with the child * of "graft" appearing before or after the original "node". * * If "node" already appears inside a sequence that is the child of * an extension node and if the spaces of the new domain elements * do not overlap with those of the original domain elements, * then that extension node is extended with the new extension * rather than introducing a new segment of extension and sequence nodes. * * Return a pointer to the same node in the modified tree that * "node" pointed to in the original tree. */ static __isl_give isl_schedule_node *isl_schedule_node_graft_before_or_after( __isl_take isl_schedule_node *node, __isl_take isl_schedule_node *graft, int before) { … } /* Insert a node "graft" into the schedule tree of "node" such that it * is executed before the node that "node" points to. * The root of "graft" may be either a domain or an extension node. * In the latter case, the domain of the extension needs to correspond * to the outer band nodes of "node". * The elements of the domain or the range of the extension may not * intersect with the domain elements that reach "node". * The schedule tree of "graft" may not be anchored. * * Return a pointer to the same node in the modified tree that * "node" pointed to in the original tree. */ __isl_give isl_schedule_node *isl_schedule_node_graft_before( __isl_take isl_schedule_node *node, __isl_take isl_schedule_node *graft) { … } /* Insert a node "graft" into the schedule tree of "node" such that it * is executed after the node that "node" points to. * The root of "graft" may be either a domain or an extension node. * In the latter case, the domain of the extension needs to correspond * to the outer band nodes of "node". * The elements of the domain or the range of the extension may not * intersect with the domain elements that reach "node". * The schedule tree of "graft" may not be anchored. * * Return a pointer to the same node in the modified tree that * "node" pointed to in the original tree. */ __isl_give isl_schedule_node *isl_schedule_node_graft_after( __isl_take isl_schedule_node *node, __isl_take isl_schedule_node *graft) { … } /* Split the domain elements that reach "node" into those that satisfy * "filter" and those that do not. Arrange for the first subset to be * executed before or after the second subset, depending on the value * of "before". * Return a pointer to the tree corresponding to the second subset, * except when this subset is empty in which case the original pointer * is returned. * If both subsets are non-empty, then a sequence node is introduced * to impose the order. If the grandparent of the original node was * itself a sequence, then the original child is replaced by two children * in this sequence instead. * The children in the sequence are copies of the original subtree, * simplified with respect to their filters. */ static __isl_give isl_schedule_node *isl_schedule_node_order_before_or_after( __isl_take isl_schedule_node *node, __isl_take isl_union_set *filter, int before) { … } /* Split the domain elements that reach "node" into those that satisfy * "filter" and those that do not. Arrange for the first subset to be * executed before the second subset. * Return a pointer to the tree corresponding to the second subset, * except when this subset is empty in which case the original pointer * is returned. */ __isl_give isl_schedule_node *isl_schedule_node_order_before( __isl_take isl_schedule_node *node, __isl_take isl_union_set *filter) { … } /* Split the domain elements that reach "node" into those that satisfy * "filter" and those that do not. Arrange for the first subset to be * executed after the second subset. * Return a pointer to the tree corresponding to the second subset, * except when this subset is empty in which case the original pointer * is returned. */ __isl_give isl_schedule_node *isl_schedule_node_order_after( __isl_take isl_schedule_node *node, __isl_take isl_union_set *filter) { … } /* Reset the user pointer on all identifiers of parameters and tuples * in the schedule node "node". */ __isl_give isl_schedule_node *isl_schedule_node_reset_user( __isl_take isl_schedule_node *node) { … } /* Align the parameters of the schedule node "node" to those of "space". */ __isl_give isl_schedule_node *isl_schedule_node_align_params( __isl_take isl_schedule_node *node, __isl_take isl_space *space) { … } /* Compute the pullback of schedule node "node" * by the function represented by "upma". * In other words, plug in "upma" in the iteration domains * of schedule node "node". * We currently do not handle expansion nodes. * * Note that this is only a helper function for * isl_schedule_pullback_union_pw_multi_aff. In order to maintain consistency, * this function should not be called on a single node without also * calling it on all the other nodes. */ __isl_give isl_schedule_node *isl_schedule_node_pullback_union_pw_multi_aff( __isl_take isl_schedule_node *node, __isl_take isl_union_pw_multi_aff *upma) { … } /* Internal data structure for isl_schedule_node_expand. * "tree" is the tree that needs to be plugged in in all the leaves. * "domain" is the set of domain elements in the original leaves * to which the tree applies. */ struct isl_schedule_expand_data { … }; /* If "node" is a leaf, then plug in data->tree, simplifying it * within its new context. * * If there are any domain elements at the leaf where the tree * should not be plugged in (i.e., there are elements not in data->domain) * then first extend the tree to only apply to the elements in data->domain * by constructing a set node that selects data->tree for elements * in data->domain and a leaf for the other elements. */ static __isl_give isl_schedule_node *expand(__isl_take isl_schedule_node *node, void *user) { … } /* Expand the tree rooted at "node" by extending all leaves * with an expansion node with as child "tree". * The expansion is determined by "contraction" and "domain". * That is, the elements of "domain" are contracted according * to "contraction". The expansion relation is then the inverse * of "contraction" with its range intersected with "domain". * * Insert the appropriate expansion node on top of "tree" and * then plug in the result in all leaves of "node". */ __isl_give isl_schedule_node *isl_schedule_node_expand( __isl_take isl_schedule_node *node, __isl_take isl_union_pw_multi_aff *contraction, __isl_take isl_union_set *domain, __isl_take isl_schedule_tree *tree) { … } /* Return the position of the subtree containing "node" among the children * of "ancestor". "node" is assumed to be a descendant of "ancestor". * In particular, both nodes should point to the same schedule tree. * * Return isl_size_error on error. */ isl_size isl_schedule_node_get_ancestor_child_position( __isl_keep isl_schedule_node *node, __isl_keep isl_schedule_node *ancestor) { … } /* Given two nodes that point to the same schedule tree, return their * closest shared ancestor. * * Since the two nodes point to the same schedule, they share at least * one ancestor, the root of the schedule. We move down from the root * to the first ancestor where the respective children have a different * child position. This is the requested ancestor. * If there is no ancestor where the children have a different position, * then one node is an ancestor of the other and then this node is * the requested ancestor. */ __isl_give isl_schedule_node *isl_schedule_node_get_shared_ancestor( __isl_keep isl_schedule_node *node1, __isl_keep isl_schedule_node *node2) { … } /* Print "node" to "p". */ __isl_give isl_printer *isl_printer_print_schedule_node( __isl_take isl_printer *p, __isl_keep isl_schedule_node *node) { … } void isl_schedule_node_dump(__isl_keep isl_schedule_node *node) { … } /* Return a string representation of "node". * Print the schedule node in block format as it would otherwise * look identical to the entire schedule. */ __isl_give char *isl_schedule_node_to_str(__isl_keep isl_schedule_node *node) { … }
Codebase Browser
llvm