/* * Copyright 2005-2007 Universiteit Leiden * Copyright 2008-2009 Katholieke Universiteit Leuven * Copyright 2010 INRIA Saclay * Copyright 2012 Universiteit Leiden * Copyright 2014 Ecole Normale Superieure * * Use of this software is governed by the MIT license * * Written by Sven Verdoolaege, Leiden Institute of Advanced Computer Science, * Universiteit Leiden, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands * and K.U.Leuven, Departement Computerwetenschappen, Celestijnenlaan 200A, * B-3001 Leuven, Belgium * and 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 */ #include <isl/val.h> #include <isl/space.h> #include <isl/set.h> #include <isl/map.h> #include <isl/union_set.h> #include <isl/union_map.h> #include <isl/flow.h> #include <isl/schedule_node.h> #include <isl_sort.h> #include <isl/stream.h> enum isl_restriction_type { … }; struct isl_restriction { … }; /* Create a restriction of the given type. */ static __isl_give isl_restriction *isl_restriction_alloc( __isl_take isl_map *source_map, enum isl_restriction_type type) { … } /* Create a restriction that doesn't restrict anything. */ __isl_give isl_restriction *isl_restriction_none(__isl_take isl_map *source_map) { … } /* Create a restriction that removes everything. */ __isl_give isl_restriction *isl_restriction_empty( __isl_take isl_map *source_map) { … } /* Create a restriction on the input of the maximization problem * based on the given source and sink restrictions. */ __isl_give isl_restriction *isl_restriction_input( __isl_take isl_set *source_restr, __isl_take isl_set *sink_restr) { … } /* Create a restriction on the output of the maximization problem * based on the given source restriction. */ __isl_give isl_restriction *isl_restriction_output( __isl_take isl_set *source_restr) { … } __isl_null isl_restriction *isl_restriction_free( __isl_take isl_restriction *restr) { … } isl_ctx *isl_restriction_get_ctx(__isl_keep isl_restriction *restr) { … } /* A private structure to keep track of a mapping together with * a user-specified identifier and a boolean indicating whether * the map represents a must or may access/dependence. */ struct isl_labeled_map { … }; isl_access_coscheduled; /* A structure containing the input for dependence analysis: * - a sink * - n_must + n_may (<= max_source) sources * - a function for determining the relative order of sources and sink * - an optional function "coscheduled" for determining whether sources * may be coscheduled. If "coscheduled" is NULL, then the sources * are assumed not to be coscheduled. * The must sources are placed before the may sources. * * domain_map is an auxiliary map that maps the sink access relation * to the domain of this access relation. * This field is only needed when restrict_fn is set and * the field itself is set by isl_access_info_compute_flow. * * restrict_fn is a callback that (if not NULL) will be called * right before any lexicographical maximization. */ struct isl_access_info { … }; /* A structure containing the output of dependence analysis: * - n_source dependences * - a wrapped subset of the sink for which definitely no source could be found * - a wrapped subset of the sink for which possibly no source could be found */ struct isl_flow { … }; /* Construct an isl_access_info structure and fill it up with * the given data. The number of sources is set to 0. */ __isl_give isl_access_info *isl_access_info_alloc(__isl_take isl_map *sink, void *sink_user, isl_access_level_before fn, int max_source) { … } /* Free the given isl_access_info structure. */ __isl_null isl_access_info *isl_access_info_free( __isl_take isl_access_info *acc) { … } isl_ctx *isl_access_info_get_ctx(__isl_keep isl_access_info *acc) { … } __isl_give isl_access_info *isl_access_info_set_restrict( __isl_take isl_access_info *acc, isl_access_restrict fn, void *user) { … } /* Add another source to an isl_access_info structure, making * sure the "must" sources are placed before the "may" sources. * This function may be called at most max_source times on a * given isl_access_info structure, with max_source as specified * in the call to isl_access_info_alloc that constructed the structure. */ __isl_give isl_access_info *isl_access_info_add_source( __isl_take isl_access_info *acc, __isl_take isl_map *source, int must, void *source_user) { … } /* A helper struct carrying the isl_access_info and an error condition. */ struct access_sort_info { … }; /* Return -n, 0 or n (with n a positive value), depending on whether * the source access identified by p1 should be sorted before, together * or after that identified by p2. * * If p1 appears before p2, then it should be sorted first. * For more generic initial schedules, it is possible that neither * p1 nor p2 appears before the other, or at least not in any obvious way. * We therefore also check if p2 appears before p1, in which case p2 * should be sorted first. * If not, we try to order the two statements based on the description * of the iteration domains. This results in an arbitrary, but fairly * stable ordering. * * In case of an error, sort_info.error is set to true and all elements are * reported to be equal. */ static int access_sort_cmp(const void *p1, const void *p2, void *user) { … } /* Sort the must source accesses in their textual order. */ static __isl_give isl_access_info *isl_access_info_sort_sources( __isl_take isl_access_info *acc) { … } /* Align the parameters of the two spaces if needed and then call * isl_space_join. */ static __isl_give isl_space *space_align_and_join(__isl_take isl_space *left, __isl_take isl_space *right) { … } /* Initialize an empty isl_flow structure corresponding to a given * isl_access_info structure. * For each must access, two dependences are created (initialized * to the empty relation), one for the resulting must dependences * and one for the resulting may dependences. May accesses can * only lead to may dependences, so only one dependence is created * for each of them. * This function is private as isl_flow structures are only supposed * to be created by isl_access_info_compute_flow. */ static __isl_give isl_flow *isl_flow_alloc(__isl_keep isl_access_info *acc) { … } /* Iterate over all sources and for each resulting flow dependence * that is not empty, call the user specfied function. * The second argument in this function call identifies the source, * while the third argument correspond to the final argument of * the isl_flow_foreach call. */ isl_stat isl_flow_foreach(__isl_keep isl_flow *deps, isl_stat (*fn)(__isl_take isl_map *dep, int must, void *dep_user, void *user), void *user) { … } /* Return a copy of the subset of the sink for which no source could be found. */ __isl_give isl_map *isl_flow_get_no_source(__isl_keep isl_flow *deps, int must) { … } __isl_null isl_flow *isl_flow_free(__isl_take isl_flow *deps) { … } isl_ctx *isl_flow_get_ctx(__isl_keep isl_flow *deps) { … } /* Return a map that enforces that the domain iteration occurs after * the range iteration at the given level. * If level is odd, then the domain iteration should occur after * the target iteration in their shared level/2 outermost loops. * In this case we simply need to enforce that these outermost * loop iterations are the same. * If level is even, then the loop iterator of the domain should * be greater than the loop iterator of the range at the last * of the level/2 shared loops, i.e., loop level/2 - 1. */ static __isl_give isl_map *after_at_level(__isl_take isl_space *space, int level) { … } /* Compute the partial lexicographic maximum of "dep" on domain "sink", * but first check if the user has set acc->restrict_fn and if so * update either the input or the output of the maximization problem * with respect to the resulting restriction. * * Since the user expects a mapping from sink iterations to source iterations, * whereas the domain of "dep" is a wrapped map, mapping sink iterations * to accessed array elements, we first need to project out the accessed * sink array elements by applying acc->domain_map. * Similarly, the sink restriction specified by the user needs to be * converted back to the wrapped map. */ static __isl_give isl_map *restricted_partial_lexmax( __isl_keep isl_access_info *acc, __isl_take isl_map *dep, int source, __isl_take isl_set *sink, __isl_give isl_set **empty) { … } /* Compute the last iteration of must source j that precedes the sink * at the given level for sink iterations in set_C. * The subset of set_C for which no such iteration can be found is returned * in *empty. */ static struct isl_map *last_source(struct isl_access_info *acc, struct isl_set *set_C, int j, int level, struct isl_set **empty) { … } /* For a given mapping between iterations of must source j and iterations * of the sink, compute the last iteration of must source k preceding * the sink at level before_level for any of the sink iterations, * but following the corresponding iteration of must source j at level * after_level. */ static struct isl_map *last_later_source(struct isl_access_info *acc, struct isl_map *old_map, int j, int before_level, int k, int after_level, struct isl_set **empty) { … } /* Given a shared_level between two accesses, return 1 if the * the first can precede the second at the requested target_level. * If the target level is odd, i.e., refers to a statement level * dimension, then first needs to precede second at the requested * level, i.e., shared_level must be equal to target_level. * If the target level is odd, then the two loops should share * at least the requested number of outer loops. */ static int can_precede_at_level(int shared_level, int target_level) { … } /* Given a possible flow dependence temp_rel[j] between source j and the sink * at level sink_level, remove those elements for which * there is an iteration of another source k < j that is closer to the sink. * The flow dependences temp_rel[k] are updated with the improved sources. * Any improved source needs to precede the sink at the same level * and needs to follow source j at the same or a deeper level. * The lower this level, the later the execution date of source k. * We therefore consider lower levels first. * * If temp_rel[j] is empty, then there can be no improvement and * we return immediately. * * This function returns isl_stat_ok in case it was executed successfully and * isl_stat_error in case of errors during the execution of this function. */ static isl_stat intermediate_sources(__isl_keep isl_access_info *acc, struct isl_map **temp_rel, int j, int sink_level) { … } /* Compute all iterations of may source j that precedes the sink at the given * level for sink iterations in set_C. */ static __isl_give isl_map *all_sources(__isl_keep isl_access_info *acc, __isl_take isl_set *set_C, int j, int level) { … } /* For a given mapping between iterations of must source k and iterations * of the sink, compute all iterations of may source j preceding * the sink at level before_level for any of the sink iterations, * but following the corresponding iteration of must source k at level * after_level. */ static __isl_give isl_map *all_later_sources(__isl_keep isl_access_info *acc, __isl_take isl_map *old_map, int j, int before_level, int k, int after_level) { … } /* Given the must and may dependence relations for the must accesses * for level sink_level, check if there are any accesses of may access j * that occur in between and return their union. * If some of these accesses are intermediate with respect to * (previously thought to be) must dependences, then these * must dependences are turned into may dependences. */ static __isl_give isl_map *all_intermediate_sources( __isl_keep isl_access_info *acc, __isl_take isl_map *map, struct isl_map **must_rel, struct isl_map **may_rel, int j, int sink_level) { … } /* Given a dependence relation "old_map" between a must-source and the sink, * return a subset of the dependences, augmented with instances * of the source at position "pos" in "acc" that are coscheduled * with the must-source and that access the same element. * That is, if the input lives in a space T -> K, then the output * lives in the space [T -> S] -> K, with S the space of source "pos", and * the domain factor of the domain product is a subset of the input. * The sources are considered to be coscheduled if they have the same values * for the initial "depth" coordinates. * * First construct a dependence relation S -> K and a mapping * between coscheduled sources T -> S. * The second is combined with the original dependence relation T -> K * to form a relation in T -> [S -> K], which is subsequently * uncurried to [T -> S] -> K. * This result is then intersected with the dependence relation S -> K * to form the output. * * In case a negative depth is given, NULL is returned to indicate an error. */ static __isl_give isl_map *coscheduled_source(__isl_keep isl_access_info *acc, __isl_keep isl_map *old_map, int pos, int depth) { … } /* After the dependences derived from a must-source have been computed * at a certain level, check if any of the sources of the must-dependences * may be coscheduled with other sources. * If they are any such sources, then there is no way of determining * which of the sources actually comes last and the must-dependences * need to be turned into may-dependences, while dependences from * the other sources need to be added to the may-dependences as well. * "acc" describes the sources and a callback for checking whether * two sources may be coscheduled. If acc->coscheduled is NULL then * the sources are assumed not to be coscheduled. * "must_rel" and "may_rel" describe the must and may-dependence relations * computed at the current level for the must-sources. Some of the dependences * may be moved from "must_rel" to "may_rel". * "flow" contains all dependences computed so far (apart from those * in "must_rel" and "may_rel") and may be updated with additional * dependences derived from may-sources. * * In particular, consider all the must-sources with a non-empty * dependence relation in "must_rel". They are considered in reverse * order because that is the order in which they are considered in the caller. * If any of the must-sources are coscheduled, then the last one * is the one that will have a corresponding dependence relation. * For each must-source i, consider both all the previous must-sources * and all the may-sources. If any of those may be coscheduled with * must-source i, then compute the coscheduled instances that access * the same memory elements. The result is a relation [T -> S] -> K. * The projection onto T -> K is a subset of the must-dependence relation * that needs to be turned into may-dependences. * The projection onto S -> K needs to be added to the may-dependences * of source S. * Since a given must-source instance may be coscheduled with several * other source instances, the dependences that need to be turned * into may-dependences are first collected and only actually removed * from the must-dependences after all other sources have been considered. */ static __isl_give isl_flow *handle_coscheduled(__isl_keep isl_access_info *acc, __isl_keep isl_map **must_rel, __isl_keep isl_map **may_rel, __isl_take isl_flow *flow) { … } /* Compute dependences for the case where all accesses are "may" * accesses, which boils down to computing memory based dependences. * The generic algorithm would also work in this case, but it would * be overkill to use it. */ static __isl_give isl_flow *compute_mem_based_dependences( __isl_keep isl_access_info *acc) { … } /* Compute dependences for the case where there is at least one * "must" access. * * The core algorithm considers all levels in which a source may precede * the sink, where a level may either be a statement level or a loop level. * The outermost statement level is 1, the first loop level is 2, etc... * The algorithm basically does the following: * for all levels l of the read access from innermost to outermost * for all sources w that may precede the sink access at that level * compute the last iteration of the source that precedes the sink access * at that level * add result to possible last accesses at level l of source w * for all sources w2 that we haven't considered yet at this level that may * also precede the sink access * for all levels l2 of w from l to innermost * for all possible last accesses dep of w at l * compute last iteration of w2 between the source and sink * of dep * add result to possible last accesses at level l of write w2 * and replace possible last accesses dep by the remainder * * * The above algorithm is applied to the must access. During the course * of the algorithm, we keep track of sink iterations that still * need to be considered. These iterations are split into those that * haven't been matched to any source access (mustdo) and those that have only * been matched to may accesses (maydo). * At the end of each level, must-sources and may-sources that are coscheduled * with the sources of the must-dependences at that level are considered. * If any coscheduled instances are found, then corresponding may-dependences * are added and the original must-dependences are turned into may-dependences. * Afterwards, the may accesses that occur after must-dependence sources * are considered. * In particular, we consider may accesses that precede the remaining * sink iterations, moving elements from mustdo to maydo when appropriate, * and may accesses that occur between a must source and a sink of any * dependences found at the current level, turning must dependences into * may dependences when appropriate. * */ static __isl_give isl_flow *compute_val_based_dependences( __isl_keep isl_access_info *acc) { … } /* Given a "sink" access, a list of n "source" accesses, * compute for each iteration of the sink access * and for each element accessed by that iteration, * the source access in the list that last accessed the * element accessed by the sink access before this sink access. * Each access is given as a map from the loop iterators * to the array indices. * The result is a list of n relations between source and sink * iterations and a subset of the domain of the sink access, * corresponding to those iterations that access an element * not previously accessed. * * To deal with multi-valued sink access relations, the sink iteration * domain is first extended with dimensions that correspond to the data * space. However, these extra dimensions are not projected out again. * It is up to the caller to decide whether these dimensions should be kept. */ static __isl_give isl_flow *access_info_compute_flow_core( __isl_take isl_access_info *acc) { … } /* Given a "sink" access, a list of n "source" accesses, * compute for each iteration of the sink access * and for each element accessed by that iteration, * the source access in the list that last accessed the * element accessed by the sink access before this sink access. * Each access is given as a map from the loop iterators * to the array indices. * The result is a list of n relations between source and sink * iterations and a subset of the domain of the sink access, * corresponding to those iterations that access an element * not previously accessed. * * To deal with multi-valued sink access relations, * access_info_compute_flow_core extends the sink iteration domain * with dimensions that correspond to the data space. These extra dimensions * are projected out from the result of access_info_compute_flow_core. */ __isl_give isl_flow *isl_access_info_compute_flow(__isl_take isl_access_info *acc) { … } /* Keep track of some information about a schedule for a given * access. In particular, keep track of which dimensions * have a constant value and of the actual constant values. */ struct isl_sched_info { … }; static void sched_info_free(__isl_take struct isl_sched_info *info) { … } /* Extract information on the constant dimensions of the schedule * for a given access. The "map" is of the form * * [S -> D] -> A * * with S the schedule domain, D the iteration domain and A the data domain. */ static __isl_give struct isl_sched_info *sched_info_alloc( __isl_keep isl_map *map) { … } /* The different types of access relations that isl_union_access_info * keeps track of. * "isl_access_sink" represents the sink accesses. * "isl_access_must_source" represents the definite source accesses. * "isl_access_may_source" represents the possible source accesses. * "isl_access_kill" represents the kills. * * isl_access_sink is sometimes treated differently and * should therefore appear first. */ enum isl_access_type { … }; /* This structure represents the input for a dependence analysis computation. * * "access" contains the access relations. * * "schedule" or "schedule_map" represents the execution order. * Exactly one of these fields should be NULL. The other field * determines the execution order. * * The domains of these four maps refer to the same iteration spaces(s). * The ranges of the first three maps also refer to the same data space(s). * * After a call to isl_union_access_info_introduce_schedule, * the "schedule_map" field no longer contains useful information. */ struct isl_union_access_info { … }; /* Free "access" and return NULL. */ __isl_null isl_union_access_info *isl_union_access_info_free( __isl_take isl_union_access_info *access) { … } /* Return the isl_ctx to which "access" belongs. */ isl_ctx *isl_union_access_info_get_ctx(__isl_keep isl_union_access_info *access) { … } /* Construct an empty (invalid) isl_union_access_info object. * The caller is responsible for setting the sink access relation and * initializing all the other fields, e.g., by calling * isl_union_access_info_init. */ static __isl_give isl_union_access_info *isl_union_access_info_alloc( isl_ctx *ctx) { … } /* Initialize all the fields of "info", except the sink access relation, * which is assumed to have been set by the caller. * * By default, we use the schedule field of the isl_union_access_info, * but this may be overridden by a call * to isl_union_access_info_set_schedule_map. */ static __isl_give isl_union_access_info *isl_union_access_info_init( __isl_take isl_union_access_info *info) { … } /* Create a new isl_union_access_info with the given sink accesses and * and no other accesses or schedule information. */ __isl_give isl_union_access_info *isl_union_access_info_from_sink( __isl_take isl_union_map *sink) { … } /* Replace the access relation of type "type" of "info" by "access". */ static __isl_give isl_union_access_info *isl_union_access_info_set( __isl_take isl_union_access_info *info, enum isl_access_type type, __isl_take isl_union_map *access) { … } /* Replace the definite source accesses of "access" by "must_source". */ __isl_give isl_union_access_info *isl_union_access_info_set_must_source( __isl_take isl_union_access_info *access, __isl_take isl_union_map *must_source) { … } /* Replace the possible source accesses of "access" by "may_source". */ __isl_give isl_union_access_info *isl_union_access_info_set_may_source( __isl_take isl_union_access_info *access, __isl_take isl_union_map *may_source) { … } /* Replace the kills of "info" by "kill". */ __isl_give isl_union_access_info *isl_union_access_info_set_kill( __isl_take isl_union_access_info *info, __isl_take isl_union_map *kill) { … } /* Return the access relation of type "type" of "info". */ static __isl_give isl_union_map *isl_union_access_info_get( __isl_keep isl_union_access_info *info, enum isl_access_type type) { … } /* Return the definite source accesses of "info". */ __isl_give isl_union_map *isl_union_access_info_get_must_source( __isl_keep isl_union_access_info *info) { … } /* Return the possible source accesses of "info". */ __isl_give isl_union_map *isl_union_access_info_get_may_source( __isl_keep isl_union_access_info *info) { … } /* Return the kills of "info". */ __isl_give isl_union_map *isl_union_access_info_get_kill( __isl_keep isl_union_access_info *info) { … } /* Does "info" specify any kills? */ static isl_bool isl_union_access_has_kill( __isl_keep isl_union_access_info *info) { … } /* Replace the schedule of "access" by "schedule". * Also free the schedule_map in case it was set last. */ __isl_give isl_union_access_info *isl_union_access_info_set_schedule( __isl_take isl_union_access_info *access, __isl_take isl_schedule *schedule) { … } /* Replace the schedule map of "access" by "schedule_map". * Also free the schedule in case it was set last. */ __isl_give isl_union_access_info *isl_union_access_info_set_schedule_map( __isl_take isl_union_access_info *access, __isl_take isl_union_map *schedule_map) { … } __isl_give isl_union_access_info *isl_union_access_info_copy( __isl_keep isl_union_access_info *access) { … } #undef BASE #define BASE … #include "print_yaml_field_templ.c" /* An enumeration of the various keys that may appear in a YAML mapping * of an isl_union_access_info object. * The keys for the access relation types are assumed to have the same values * as the access relation types in isl_access_type. */ enum isl_ai_key { … }; /* Textual representations of the YAML keys for an isl_union_access_info * object. */ static char *key_str[] = …; /* Print a key-value pair corresponding to the access relation of type "type" * of a YAML mapping of "info" to "p". * * The sink access relation is always printed, but any other access relation * is only printed if it is non-empty. */ static __isl_give isl_printer *print_access_field(__isl_take isl_printer *p, __isl_keep isl_union_access_info *info, enum isl_access_type type) { … } /* Print the information contained in "access" to "p". * The information is printed as a YAML document. */ __isl_give isl_printer *isl_printer_print_union_access_info( __isl_take isl_printer *p, __isl_keep isl_union_access_info *access) { … } /* Return a string representation of the information in "access". * The information is printed in flow format. */ __isl_give char *isl_union_access_info_to_str( __isl_keep isl_union_access_info *access) { … } #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" #undef BASE #define BASE … #include "read_in_string_templ.c" /* Read an isl_union_access_info object from "s". * * Start off with an empty (invalid) isl_union_access_info object and * then fill up the fields based on the input. * The input needs to contain at least a description of the sink * access relation as well as some form of schedule. * The other access relations are set to empty relations * by isl_union_access_info_init if they are not specified in the input. */ __isl_give isl_union_access_info *isl_stream_read_union_access_info( isl_stream *s) { … } /* Read an isl_union_access_info object from the file "input". */ __isl_give isl_union_access_info *isl_union_access_info_read_from_file( isl_ctx *ctx, FILE *input) { … } /* Update the fields of "access" such that they all have the same parameters, * keeping in mind that the schedule_map field may be NULL and ignoring * the schedule field. */ static __isl_give isl_union_access_info *isl_union_access_info_align_params( __isl_take isl_union_access_info *access) { … } /* Prepend the schedule dimensions to the iteration domains. * * That is, if the schedule is of the form * * D -> S * * while the access relations are of the form * * D -> A * * then the updated access relations are of the form * * [S -> D] -> A * * The schedule map is also replaced by the map * * [S -> D] -> D * * that is used during the internal computation. * Neither the original schedule map nor this updated schedule map * are used after the call to this function. */ static __isl_give isl_union_access_info * isl_union_access_info_introduce_schedule( __isl_take isl_union_access_info *access) { … } /* This structure represents the result of a dependence analysis computation. * * "must_dep" represents the full definite dependences * "may_dep" represents the full non-definite dependences. * Both are of the form * * [Source] -> [[Sink -> Data]] * * (after the schedule dimensions have been projected out). * "must_no_source" represents the subset of the sink accesses for which * definitely no source was found. * "may_no_source" represents the subset of the sink accesses for which * possibly, but not definitely, no source was found. */ struct isl_union_flow { … }; /* Return the isl_ctx to which "flow" belongs. */ isl_ctx *isl_union_flow_get_ctx(__isl_keep isl_union_flow *flow) { … } /* Free "flow" and return NULL. */ __isl_null isl_union_flow *isl_union_flow_free(__isl_take isl_union_flow *flow) { … } void isl_union_flow_dump(__isl_keep isl_union_flow *flow) { … } /* Return the full definite dependences in "flow", with accessed elements. */ __isl_give isl_union_map *isl_union_flow_get_full_must_dependence( __isl_keep isl_union_flow *flow) { … } /* Return the full possible dependences in "flow", including the definite * dependences, with accessed elements. */ __isl_give isl_union_map *isl_union_flow_get_full_may_dependence( __isl_keep isl_union_flow *flow) { … } /* Return the definite dependences in "flow", without the accessed elements. */ __isl_give isl_union_map *isl_union_flow_get_must_dependence( __isl_keep isl_union_flow *flow) { … } /* Return the possible dependences in "flow", including the definite * dependences, without the accessed elements. */ __isl_give isl_union_map *isl_union_flow_get_may_dependence( __isl_keep isl_union_flow *flow) { … } /* Return the non-definite dependences in "flow". */ static __isl_give isl_union_map *isl_union_flow_get_non_must_dependence( __isl_keep isl_union_flow *flow) { … } /* Return the subset of the sink accesses for which definitely * no source was found. */ __isl_give isl_union_map *isl_union_flow_get_must_no_source( __isl_keep isl_union_flow *flow) { … } /* Return the subset of the sink accesses for which possibly * no source was found, including those for which definitely * no source was found. */ __isl_give isl_union_map *isl_union_flow_get_may_no_source( __isl_keep isl_union_flow *flow) { … } /* Return the subset of the sink accesses for which possibly, but not * definitely, no source was found. */ static __isl_give isl_union_map *isl_union_flow_get_non_must_no_source( __isl_keep isl_union_flow *flow) { … } /* Create a new isl_union_flow object, initialized with empty * dependence relations and sink subsets. */ static __isl_give isl_union_flow *isl_union_flow_alloc( __isl_take isl_space *space) { … } /* Copy this isl_union_flow object. */ __isl_give isl_union_flow *isl_union_flow_copy(__isl_keep isl_union_flow *flow) { … } /* Drop the schedule dimensions from the iteration domains in "flow". * In particular, the schedule dimensions have been prepended * to the iteration domains prior to the dependence analysis by * replacing the iteration domain D, by the wrapped map [S -> D]. * Replace these wrapped maps by the original D. * * In particular, the dependences computed by access_info_compute_flow_core * are of the form * * [S -> D] -> [[S' -> D'] -> A] * * The schedule dimensions are projected out by first currying the range, * resulting in * * [S -> D] -> [S' -> [D' -> A]] * * and then computing the factor range * * D -> [D' -> A] */ static __isl_give isl_union_flow *isl_union_flow_drop_schedule( __isl_take isl_union_flow *flow) { … } struct isl_compute_flow_data { … }; static isl_stat count_matching_array(__isl_take isl_map *map, void *user) { … } static isl_stat collect_matching_array(__isl_take isl_map *map, void *user) { … } /* Determine the shared nesting level and the "textual order" of * the given accesses. * * We first determine the minimal schedule dimension for both accesses. * * If among those dimensions, we can find one where both have a fixed * value and if moreover those values are different, then the previous * dimension is the last shared nesting level and the textual order * is determined based on the order of the fixed values. * If no such fixed values can be found, then we set the shared * nesting level to the minimal schedule dimension, with no textual ordering. */ static int before(void *first, void *second) { … } /* Check if the given two accesses may be coscheduled. * If so, return isl_bool_true. Otherwise return isl_bool_false. * * Two accesses may only be coscheduled if the fixed schedule * coordinates have the same values. */ static isl_bool coscheduled(void *first, void *second) { … } /* Given a sink access, look for all the source accesses that access * the same array and perform dataflow analysis on them using * isl_access_info_compute_flow_core. */ static isl_stat compute_flow(__isl_take isl_map *map, void *user) { … } /* Add the kills of "info" to the must-sources. */ static __isl_give isl_union_access_info * isl_union_access_info_add_kill_to_must_source( __isl_take isl_union_access_info *info) { … } /* Drop dependences from "flow" that purely originate from kills. * That is, only keep those dependences that originate from * the original must-sources "must" and/or the original may-sources "may". * In particular, "must" contains the must-sources from before * the kills were added and "may" contains the may-source from before * the kills were removed. * * The dependences are of the form * * Source -> [Sink -> Data] * * Only those dependences are kept where the Source -> Data part * is a subset of the original may-sources or must-sources. * Of those, only the must-dependences that intersect with the must-sources * remain must-dependences. * If there is some overlap between the may-sources and the must-sources, * then the may-dependences and must-dependences may also overlap. * This should be fine since the may-dependences are only kept * disjoint from the must-dependences for the isl_union_map_compute_flow * interface. This interface does not support kills, so it will * not end up calling this function. */ static __isl_give isl_union_flow *isl_union_flow_drop_kill_source( __isl_take isl_union_flow *flow, __isl_take isl_union_map *must, __isl_take isl_union_map *may) { … } /* Remove the must accesses from the may accesses. * * A must access always trumps a may access, so there is no need * for a must access to also be considered as a may access. Doing so * would only cost extra computations only to find out that * the duplicated may access does not make any difference. */ static __isl_give isl_union_access_info *isl_union_access_info_normalize( __isl_take isl_union_access_info *access) { … } /* Given a description of the "sink" accesses, the "source" accesses and * a schedule, compute for each instance of a sink access * and for each element accessed by that instance, * the possible or definite source accesses that last accessed the * element accessed by the sink access before this sink access * in the sense that there is no intermediate definite source access. * * The must_no_source and may_no_source elements of the result * are subsets of access->sink. The elements must_dep and may_dep * map domain elements of access->{may,must)_source to * domain elements of access->sink. * * This function is used when only the schedule map representation * is available. * * We first prepend the schedule dimensions to the domain * of the accesses so that we can easily compare their relative order. * Then we consider each sink access individually in compute_flow. */ static __isl_give isl_union_flow *compute_flow_union_map( __isl_take isl_union_access_info *access) { … } /* A schedule access relation. * * The access relation "access" is of the form [S -> D] -> A, * where S corresponds to the prefix schedule at "node". * "must" is only relevant for source accesses and indicates * whether the access is a must source or a may source. */ struct isl_scheduled_access { … }; /* Data structure for keeping track of individual scheduled sink and source * accesses when computing dependence analysis based on a schedule tree. * * "n_sink" is the number of used entries in "sink" * "n_source" is the number of used entries in "source" * * "set_sink", "must" and "node" are only used inside collect_sink_source, * to keep track of the current node and * of what extract_sink_source needs to do. */ struct isl_compute_flow_schedule_data { … }; /* Align the parameters of all sinks with all sources. * * If there are no sinks or no sources, then no alignment is needed. */ static void isl_compute_flow_schedule_data_align_params( struct isl_compute_flow_schedule_data *data) { … } /* Free all the memory referenced from "data". * Do not free "data" itself as it may be allocated on the stack. */ static void isl_compute_flow_schedule_data_clear( struct isl_compute_flow_schedule_data *data) { … } /* isl_schedule_foreach_schedule_node_top_down callback for counting * (an upper bound on) the number of sinks and sources. * * Sinks and sources are only extracted at leaves of the tree, * so we skip the node if it is not a leaf. * Otherwise we increment data->n_sink and data->n_source with * the number of spaces in the sink and source access domains * that reach this node. */ static isl_bool count_sink_source(__isl_keep isl_schedule_node *node, void *user) { … } /* Add a single scheduled sink or source (depending on data->set_sink) * with scheduled access relation "map", must property data->must and * schedule node data->node to the list of sinks or sources. */ static isl_stat extract_sink_source(__isl_take isl_map *map, void *user) { … } /* isl_schedule_foreach_schedule_node_top_down callback for collecting * individual scheduled source and sink accesses (taking into account * the domain of the schedule). * * We only collect accesses at the leaves of the schedule tree. * We prepend the schedule dimensions at the leaf to the iteration * domains of the source and sink accesses and then extract * the individual accesses (per space). * * In particular, if the prefix schedule at the node is of the form * * D -> S * * while the access relations are of the form * * D -> A * * then the updated access relations are of the form * * [S -> D] -> A * * Note that S consists of a single space such that introducing S * in the access relations does not increase the number of spaces. */ static isl_bool collect_sink_source(__isl_keep isl_schedule_node *node, void *user) { … } /* isl_access_info_compute_flow callback for determining whether * the shared nesting level and the ordering within that level * for two scheduled accesses for use in compute_single_flow. * * The tokens passed to this function refer to the leaves * in the schedule tree where the accesses take place. * * If n is the shared number of loops, then we need to return * "2 * n + 1" if "first" precedes "second" inside the innermost * shared loop and "2 * n" otherwise. * * The innermost shared ancestor may be the leaves themselves * if the accesses take place in the same leaf. Otherwise, * it is either a set node or a sequence node. Only in the case * of a sequence node do we consider one access to precede the other. */ static int before_node(void *first, void *second) { … } /* Check if the given two accesses may be coscheduled. * If so, return isl_bool_true. Otherwise return isl_bool_false. * * Two accesses may only be coscheduled if they appear in the same leaf. */ static isl_bool coscheduled_node(void *first, void *second) { … } /* Add the scheduled sources from "data" that access * the same data space as "sink" to "access". */ static __isl_give isl_access_info *add_matching_sources( __isl_take isl_access_info *access, struct isl_scheduled_access *sink, struct isl_compute_flow_schedule_data *data) { … } /* Given a scheduled sink access relation "sink", compute the corresponding * dependences on the sources in "data" and add the computed dependences * to "uf". * * The dependences computed by access_info_compute_flow_core are of the form * * [S -> I] -> [[S' -> I'] -> A] * * The schedule dimensions are projected out by first currying the range, * resulting in * * [S -> I] -> [S' -> [I' -> A]] * * and then computing the factor range * * I -> [I' -> A] */ static __isl_give isl_union_flow *compute_single_flow( __isl_take isl_union_flow *uf, struct isl_scheduled_access *sink, struct isl_compute_flow_schedule_data *data) { … } /* Given a description of the "sink" accesses, the "source" accesses and * a schedule, compute for each instance of a sink access * and for each element accessed by that instance, * the possible or definite source accesses that last accessed the * element accessed by the sink access before this sink access * in the sense that there is no intermediate definite source access. * Only consider dependences between statement instances that belong * to the domain of the schedule. * * The must_no_source and may_no_source elements of the result * are subsets of access->sink. The elements must_dep and may_dep * map domain elements of access->{may,must)_source to * domain elements of access->sink. * * This function is used when a schedule tree representation * is available. * * We extract the individual scheduled source and sink access relations * (taking into account the domain of the schedule) and * then compute dependences for each scheduled sink individually. */ static __isl_give isl_union_flow *compute_flow_schedule( __isl_take isl_union_access_info *access) { … } /* Given a description of the "sink" accesses, the "source" accesses and * a schedule, compute for each instance of a sink access * and for each element accessed by that instance, * the possible or definite source accesses that last accessed the * element accessed by the sink access before this sink access * in the sense that there is no intermediate definite source access. * * The must_no_source and may_no_source elements of the result * are subsets of access->sink. The elements must_dep and may_dep * map domain elements of access->{may,must)_source to * domain elements of access->sink. * * If any kills have been specified, then they are treated as * must-sources internally. Any dependence that purely derives * from an original kill is removed from the output. * * We check whether the schedule is available as a schedule tree * or a schedule map and call the corresponding function to perform * the analysis. */ __isl_give isl_union_flow *isl_union_access_info_compute_flow( __isl_take isl_union_access_info *access) { … } /* Print the information contained in "flow" to "p". * The information is printed as a YAML document. */ __isl_give isl_printer *isl_printer_print_union_flow( __isl_take isl_printer *p, __isl_keep isl_union_flow *flow) { … } /* Return a string representation of the information in "flow". * The information is printed in flow format. */ __isl_give char *isl_union_flow_to_str(__isl_keep isl_union_flow *flow) { … } /* Given a collection of "sink" and "source" accesses, * compute for each iteration of a sink access * and for each element accessed by that iteration, * the source access in the list that last accessed the * element accessed by the sink access before this sink access. * Each access is given as a map from the loop iterators * to the array indices. * The result is a relations between source and sink * iterations and a subset of the domain of the sink accesses, * corresponding to those iterations that access an element * not previously accessed. * * We collect the inputs in an isl_union_access_info object, * call isl_union_access_info_compute_flow and extract * the outputs from the result. */ int isl_union_map_compute_flow(__isl_take isl_union_map *sink, __isl_take isl_union_map *must_source, __isl_take isl_union_map *may_source, __isl_take isl_union_map *schedule, __isl_give isl_union_map **must_dep, __isl_give isl_union_map **may_dep, __isl_give isl_union_map **must_no_source, __isl_give isl_union_map **may_no_source) { … }
Codebase Browser
llvm