/* * Copyright 2012 Ecole Normale Superieure * Copyright 2014 INRIA Rocquencourt * Copyright 2019 Cerebras Systems * * 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 * and Cerebras Systems, 175 S San Antonio Rd, Los Altos, CA, USA */ #include <isl/id.h> #include <isl/space.h> #include <isl/stream.h> #include <isl_ast_private.h> #include <isl_ast_build_expr.h> #include <isl_ast_build_private.h> #include <isl_ast_graft_private.h> #include "isl_set_to_ast_graft_list.h" static __isl_give isl_ast_graft *isl_ast_graft_copy( __isl_keep isl_ast_graft *graft); static __isl_give isl_ast_graft *isl_stream_read_ast_graft( __isl_keep isl_stream *s); #undef EL_BASE #define EL_BASE … #include <isl_list_templ.c> #include <isl_list_read_templ.c> #undef BASE #define BASE … #include <print_templ.c> isl_ctx *isl_ast_graft_get_ctx(__isl_keep isl_ast_graft *graft) { … } __isl_give isl_ast_node *isl_ast_graft_get_node( __isl_keep isl_ast_graft *graft) { … } /* Create a graft for "node" with guards "guard" and * enforced conditions "enforced". */ static isl_ast_graft *graft_alloc(__isl_take isl_ast_node *node, __isl_take isl_set *guard, __isl_take isl_basic_set *enforced) { … } /* Create a graft for "node" with no guards and no enforced conditions. */ __isl_give isl_ast_graft *isl_ast_graft_alloc( __isl_take isl_ast_node *node, __isl_keep isl_ast_build *build) { … } /* Create a graft with no guards and no enforced conditions * encapsulating a call to the domain element specified by "executed". * "executed" is assumed to be single-valued. */ __isl_give isl_ast_graft *isl_ast_graft_alloc_domain( __isl_take isl_map *executed, __isl_keep isl_ast_build *build) { … } static __isl_give isl_ast_graft *isl_ast_graft_copy( __isl_keep isl_ast_graft *graft) { … } /* Do all the grafts in "list" have the same guard and is this guard * independent of the current depth? */ static isl_bool equal_independent_guards(__isl_keep isl_ast_graft_list *list, __isl_keep isl_ast_build *build) { … } /* Hoist "guard" out of the current level (given by "build"). * * In particular, eliminate the dimension corresponding to the current depth. */ static __isl_give isl_set *hoist_guard(__isl_take isl_set *guard, __isl_keep isl_ast_build *build) { … } /* Extract a common guard from the grafts in "list" that can be hoisted * out of the current level. If no such guard can be found, then return * a universal set. * * If all the grafts in the list have the same guard and if this guard * is independent of the current level, then it can be hoisted out. * If there is only one graft in the list and if its guard * depends on the current level, then we eliminate this level and * return the result. * * Otherwise, we return the unshifted simple hull of the guards. * In order to be able to hoist as many constraints as possible, * but at the same time avoid hoisting constraints that did not * appear in the guards in the first place, we intersect the guards * with all the information that is available (i.e., the domain * from the build and the enforced constraints of the graft) and * compute the unshifted hull of the result using only constraints * from the original guards. * In particular, intersecting the guards with other known information * allows us to hoist guards that are only explicit is some of * the grafts and implicit in the others. * * The special case for equal guards is needed in case those guards * are non-convex. Taking the simple hull would remove information * and would not allow for these guards to be hoisted completely. */ __isl_give isl_set *isl_ast_graft_list_extract_hoistable_guard( __isl_keep isl_ast_graft_list *list, __isl_keep isl_ast_build *build) { … } /* Internal data structure used inside insert_if. * * list is the list of guarded nodes created by each call to insert_if. * node is the original node that is guarded by insert_if. * build is the build in which the AST is constructed. */ struct isl_insert_if_data { … }; static isl_stat insert_if(__isl_take isl_basic_set *bset, void *user); /* Insert an if node around "node" testing the condition encoded * in guard "guard". * * If the user does not want any disjunctions in the if conditions * and if "guard" does involve a disjunction, then we make the different * disjuncts disjoint and insert an if node corresponding to each disjunct * around a copy of "node". The result is then a block node containing * this sequence of guarded copies of "node". */ static __isl_give isl_ast_node *ast_node_insert_if( __isl_take isl_ast_node *node, __isl_take isl_set *guard, __isl_keep isl_ast_build *build) { … } /* Insert an if node around a copy of "data->node" testing the condition * encoded in guard "bset" and add the result to data->list. */ static isl_stat insert_if(__isl_take isl_basic_set *bset, void *user) { … } /* Insert an if node around graft->node testing the condition encoded * in guard "guard", assuming guard involves any conditions. */ static __isl_give isl_ast_graft *insert_if_node( __isl_take isl_ast_graft *graft, __isl_take isl_set *guard, __isl_keep isl_ast_build *build) { … } /* Insert an if node around graft->node testing the condition encoded * in graft->guard, assuming graft->guard involves any conditions. */ static __isl_give isl_ast_graft *insert_pending_guard_node( __isl_take isl_ast_graft *graft, __isl_keep isl_ast_build *build) { … } /* Replace graft->enforced by "enforced". */ __isl_give isl_ast_graft *isl_ast_graft_set_enforced( __isl_take isl_ast_graft *graft, __isl_take isl_basic_set *enforced) { … } /* Update "enforced" such that it only involves constraints that are * also enforced by "graft". */ static __isl_give isl_basic_set *update_enforced( __isl_take isl_basic_set *enforced, __isl_keep isl_ast_graft *graft, int depth) { … } /* Extend the node at *body with node. * * If body points to the else branch, then *body may still be NULL. * If so, we simply attach node to this else branch. * Otherwise, we attach a list containing the statements already * attached at *body followed by node. */ static void extend_body(__isl_keep isl_ast_node **body, __isl_take isl_ast_node *node) { … } /* Merge "graft" into the last graft of "list". * body points to the then or else branch of an if node in that last graft. * * We attach graft->node to this branch and update the enforced * set of the last graft of "list" to take into account the enforced * set of "graft". */ static __isl_give isl_ast_graft_list *graft_extend_body( __isl_take isl_ast_graft_list *list, __isl_keep isl_ast_node **body, __isl_take isl_ast_graft *graft, __isl_keep isl_ast_build *build) { … } /* Merge "graft" into the last graft of "list", attaching graft->node * to the then branch of "last_if". */ static __isl_give isl_ast_graft_list *extend_then( __isl_take isl_ast_graft_list *list, __isl_keep isl_ast_node *last_if, __isl_take isl_ast_graft *graft, __isl_keep isl_ast_build *build) { … } /* Merge "graft" into the last graft of "list", attaching graft->node * to the else branch of "last_if". */ static __isl_give isl_ast_graft_list *extend_else( __isl_take isl_ast_graft_list *list, __isl_keep isl_ast_node *last_if, __isl_take isl_ast_graft *graft, __isl_keep isl_ast_build *build) { … } /* This data structure keeps track of an if node. * * "node" is the actual if-node * "guard" is the original, non-simplified guard of the node * "complement" is the complement of "guard" in the context of outer if nodes */ struct isl_if_node { … }; /* Given a list of "n" if nodes, clear those starting at "first" * and return "first" (i.e., the updated size of the array). */ static int clear_if_nodes(struct isl_if_node *if_node, int first, int n) { … } /* For each graft in "list", * insert an if node around graft->node testing the condition encoded * in graft->guard, assuming graft->guard involves any conditions. * * We keep track of a list of generated if nodes that can be extended * without changing the order of the elements in "list". * If the guard of a graft is a subset of either the guard or its complement * of one of those if nodes, then the node * of the new graft is inserted into the then or else branch of the last graft * and the current graft is discarded. * The guard of the node is then simplified based on the conditions * enforced at that then or else branch. * Otherwise, the current graft is appended to the list. * * We only construct else branches if allowed by the user. */ static __isl_give isl_ast_graft_list *insert_pending_guard_nodes( __isl_take isl_ast_graft_list *list, __isl_keep isl_ast_build *build) { … } /* For each graft in "list", * insert an if node around graft->node testing the condition encoded * in graft->guard, assuming graft->guard involves any conditions. * Subsequently remove the guards from the grafts. */ __isl_give isl_ast_graft_list *isl_ast_graft_list_insert_pending_guard_nodes( __isl_take isl_ast_graft_list *list, __isl_keep isl_ast_build *build) { … } /* Collect the nodes contained in the grafts in "list" in a node list. */ static __isl_give isl_ast_node_list *extract_node_list( __isl_keep isl_ast_graft_list *list) { … } /* Look for shared enforced constraints by all the elements in "list" * on outer loops (with respect to the current depth) and return the result. * * If there are no elements in "list", then return the empty set. */ __isl_give isl_basic_set *isl_ast_graft_list_extract_shared_enforced( __isl_keep isl_ast_graft_list *list, __isl_keep isl_ast_build *build) { … } /* Record "guard" in "graft" so that it will be enforced somewhere * up the tree. If the graft already has a guard, then it may be partially * redundant in combination with the new guard and in the context * the generated constraints of "build". In fact, the new guard * may in itself have some redundant constraints. * We therefore (re)compute the gist of the intersection * and coalesce the result. */ static __isl_give isl_ast_graft *store_guard(__isl_take isl_ast_graft *graft, __isl_take isl_set *guard, __isl_keep isl_ast_build *build) { … } /* For each graft in "list", replace its guard with the gist with * respect to "context". */ static __isl_give isl_ast_graft_list *gist_guards( __isl_take isl_ast_graft_list *list, __isl_keep isl_set *context) { … } /* For each graft in "list", replace its guard with the gist with * respect to "context". */ __isl_give isl_ast_graft_list *isl_ast_graft_list_gist_guards( __isl_take isl_ast_graft_list *list, __isl_take isl_set *context) { … } /* Allocate a graft in "build" based on the list of grafts in "sub_build". * "guard" and "enforced" are the guard and enforced constraints * of the allocated graft. The guard is used to simplify the guards * of the elements in "list". * * The node is initialized to either a block containing the nodes of "children" * or, if there is only a single child, the node of that child. * If the current level requires a for node, it should be inserted by * a subsequent call to isl_ast_graft_insert_for. */ __isl_give isl_ast_graft *isl_ast_graft_alloc_from_children( __isl_take isl_ast_graft_list *list, __isl_take isl_set *guard, __isl_take isl_basic_set *enforced, __isl_keep isl_ast_build *build, __isl_keep isl_ast_build *sub_build) { … } /* Combine the grafts in the list into a single graft. * * The guard is initialized to the shared guard of the list elements (if any), * provided it does not depend on the current dimension. * The guards in the elements are then simplified with respect to the * hoisted guard and materialized as if nodes around the contained AST nodes * in the context of "sub_build". * * The enforced set is initialized to the simple hull of the enforced sets * of the elements, provided the ast_build_exploit_nested_bounds option is set * or the new graft will be used at the same level. * * The node is initialized to either a block containing the nodes of "list" * or, if there is only a single element, the node of that element. */ static __isl_give isl_ast_graft *ast_graft_list_fuse( __isl_take isl_ast_graft_list *list, __isl_keep isl_ast_build *build) { … } /* Combine the grafts in the list into a single graft. * Return a list containing this single graft. * If the original list is empty, then return an empty list. */ __isl_give isl_ast_graft_list *isl_ast_graft_list_fuse( __isl_take isl_ast_graft_list *list, __isl_keep isl_ast_build *build) { … } /* Combine the two grafts into a single graft. * Return a list containing this single graft. */ static __isl_give isl_ast_graft *isl_ast_graft_fuse( __isl_take isl_ast_graft *graft1, __isl_take isl_ast_graft *graft2, __isl_keep isl_ast_build *build) { … } /* Insert a for node enclosing the current graft->node. */ __isl_give isl_ast_graft *isl_ast_graft_insert_for( __isl_take isl_ast_graft *graft, __isl_take isl_ast_node *node) { … } /* Insert a mark governing the current graft->node. */ __isl_give isl_ast_graft *isl_ast_graft_insert_mark( __isl_take isl_ast_graft *graft, __isl_take isl_id *mark) { … } /* Represent the graft list as an AST node. * This operation drops the information about guards in the grafts, so * if there are any pending guards, then they are materialized as if nodes. */ __isl_give isl_ast_node *isl_ast_node_from_graft_list( __isl_take isl_ast_graft_list *list, __isl_keep isl_ast_build *build) { … } __isl_null isl_ast_graft *isl_ast_graft_free(__isl_take isl_ast_graft *graft) { … } /* Record that the grafted tree enforces * "enforced" by intersecting graft->enforced with "enforced". */ __isl_give isl_ast_graft *isl_ast_graft_enforce( __isl_take isl_ast_graft *graft, __isl_take isl_basic_set *enforced) { … } __isl_give isl_basic_set *isl_ast_graft_get_enforced( __isl_keep isl_ast_graft *graft) { … } __isl_give isl_set *isl_ast_graft_get_guard(__isl_keep isl_ast_graft *graft) { … } /* Record that "guard" needs to be inserted in "graft". */ __isl_give isl_ast_graft *isl_ast_graft_add_guard( __isl_take isl_ast_graft *graft, __isl_take isl_set *guard, __isl_keep isl_ast_build *build) { … } /* Reformulate the "graft", which was generated in the context * of an inner code generation, in terms of the outer code generation * AST build. * * If "product" is set, then the domain of the inner code generation build is * * [O -> S] * * with O the domain of the outer code generation build. * We essentially need to project out S. * * If "product" is not set, then we need to project the domains onto * their parameter spaces. */ __isl_give isl_ast_graft *isl_ast_graft_unembed(__isl_take isl_ast_graft *graft, int product) { … } /* Reformulate the grafts in "list", which were generated in the context * of an inner code generation, in terms of the outer code generation * AST build. */ __isl_give isl_ast_graft_list *isl_ast_graft_list_unembed( __isl_take isl_ast_graft_list *list, int product) { … } /* Compute the preimage of "graft" under the function represented by "ma". * In other words, plug in "ma" in "enforced" and "guard" fields of "graft". */ __isl_give isl_ast_graft *isl_ast_graft_preimage_multi_aff( __isl_take isl_ast_graft *graft, __isl_take isl_multi_aff *ma) { … } /* Compute the preimage of all the grafts in "list" under * the function represented by "ma". */ __isl_give isl_ast_graft_list *isl_ast_graft_list_preimage_multi_aff( __isl_take isl_ast_graft_list *list, __isl_take isl_multi_aff *ma) { … } /* Compare two grafts based on their guards. */ static int cmp_graft(__isl_keep isl_ast_graft *a, __isl_keep isl_ast_graft *b, void *user) { … } /* Order the elements in "list" based on their guards. */ __isl_give isl_ast_graft_list *isl_ast_graft_list_sort_guard( __isl_take isl_ast_graft_list *list) { … } /* Merge the given two lists into a single list of grafts, * merging grafts with the same guard into a single graft. * * "list2" has been sorted using isl_ast_graft_list_sort. * "list1" may be the result of a previous call to isl_ast_graft_list_merge * and may therefore not be completely sorted. * * The elements in "list2" need to be executed after those in "list1", * but if the guard of a graft in "list2" is disjoint from the guards * of some final elements in "list1", then it can be moved up to before * those final elements. * * In particular, we look at each element g of "list2" in turn * and move it up beyond elements of "list1" that would be sorted * after g as long as each of these elements has a guard that is disjoint * from that of g. * * We do not allow the second or any later element of "list2" to be moved * before a previous elements of "list2" even if the reason that * that element didn't move up further was that its guard was not disjoint * from that of the previous element in "list1". */ __isl_give isl_ast_graft_list *isl_ast_graft_list_merge( __isl_take isl_ast_graft_list *list1, __isl_take isl_ast_graft_list *list2, __isl_keep isl_ast_build *build) { … } /* Internal data structure for split_on_guard. * * "guard2list" is the constructed associative array. * "any_match" gets set if any guard was seen more than once. */ struct isl_split_on_guard_data { … }; /* Add "graft" to the list associated to its guard in data->guard2list. * If some other graft was already associated to this guard, * then set data->any_match. */ static isl_stat add_to_guard_list(__isl_take isl_ast_graft *graft, void *user) { … } /* Construct an associative array that groups the elements * of "list" based on their guards. * If any guard appears more than once, then set "any_match". */ static __isl_give isl_set_to_ast_graft_list *split_on_guard( __isl_keep isl_ast_graft_list *list, int *any_match) { … } /* Add the elements of "guard_list" to "list". */ static isl_stat add_same_guard(__isl_take isl_set *guard, __isl_take isl_ast_graft_list *guard_list, void *user) { … } /* Given an associative array "guard2list" containing the elements * of "list" grouped on common guards, reconstruct "list" * by placing elements with the same guard consecutively. */ static __isl_give isl_ast_graft_list *reconstruct( __isl_take isl_ast_graft_list *list, __isl_keep isl_set_to_ast_graft_list *guard2list, __isl_keep isl_ast_build *build) { … } /* Group the grafts in "list" based on identical guards. * * Note that there need to be a least three elements in the list * for the elements not to be grouped already. * * Group the elements in an associative array based on their guards. * If any guard was seen more than once, then reconstruct the list * from the associative array. Otherwise, simply return the original list. */ __isl_give isl_ast_graft_list *isl_ast_graft_list_group_on_guard( __isl_take isl_ast_graft_list *list, __isl_keep isl_ast_build *build) { … } /* An enumeration of the keys that appear in the textual representation * of an isl_sat_graft object. */ enum isl_graft_key { … }; /* Textual representations of the keys for an isl_sat_graft object. */ static char *key_str[] = …; __isl_give isl_printer *isl_printer_print_ast_graft(__isl_take isl_printer *p, __isl_keep isl_ast_graft *graft) { … } #undef KEY #define KEY … #undef KEY_ERROR #define KEY_ERROR … #undef KEY_END #define KEY_END … #undef KEY_STR #define KEY_STR … #undef KEY_EXTRACT #define KEY_EXTRACT … #undef KEY_GET #define KEY_GET … #include "extract_key.c" /* Read the key "key" from "s", along with the subsequent colon. */ static isl_stat read_key(__isl_keep isl_stream *s, enum isl_graft_key key) { … } /* Read an isl_ast_graft object from "s". * * Read the pieces in the way they are printed in isl_printer_print_ast_graft. */ static __isl_give isl_ast_graft *isl_stream_read_ast_graft( __isl_keep isl_stream *s) { … }
Codebase Browser
llvm