/* * Copyright 2021 Sven Verdoolaege * * Use of this software is governed by the MIT license * * Written by Sven Verdoolaege */ #include <stdio.h> #include <isl/ctx.h> #include <isl/schedule_node.h> #include <isl/union_set.h> #include "isl_hash_private.h" #include "isl_scheduler_scc.h" #include "isl_sort.h" /* Internal data structure for ordering the SCCs of "graph", * where each SCC i consists of the single cluster determined * by c->scc_cluster[i]. The nodes in this cluster all have * their "scc" field set to i. * * "graph" is the original schedule graph. * "c" contains the clustering information. * * "n" is the number of SCCs in the isl_scc_graph, which may be * a subset of those in "graph". * "graph_scc" maps the local index of an SCC in this isl_scc_graph * to the corresponding index in "graph", i.e, the index of c->scc_cluster. * The entries of "graph_scc" are kept in topological order. * * "component" contains the component to which an SCC belongs, * where the component is represented by the index of the first SCC * in the component. * The index of this first SCC is always smaller than or equal * to the index of the SCC itself. * This field is initialized by isl_scc_graph_init_component and * used by detect_components. * During construction, "component" may also contain the index * of some other SCC in the component, but then it is necessarily * smaller than the index of the current SCC and the first SCC * can be reached by recursively looking up "component". * "size" contains the number of elements in the components * indexed by a component sequence number. * * "pos" is used locally inside isl_scc_graph_sort_components * to store the position of the next SCC within a component. * It is also used inside isl_scc_graph_sub to map * the position in the original graph to the position in the subgraph. * * "sorted" contains the (possibly) reordered local indices, * sorted per component. Within each component, the original * topological order is preserved. * * "edge_table" contains "n" edge tables, one for each SCC * in this isl_scc_graph. Each table contains the local indices * of the SCCs that depend on this SCC. These local indices * are encoded as pointers to the corresponding entry in "graph_scc". * The value stored at that location is the global SCC index. * "reverse_edge_table" contains the inverse edges. */ struct isl_scc_graph { … }; /* The source SCC of a collection of edges. * * "scc_graph" is the SCC graph containing the edges. * "src" is the local index of the source SCC. */ struct isl_edge_src { … }; /* isl_hash_table_foreach callback for printing an edge * between "src" and the node identified by "entry". * The edge is printed in terms of the global SCC indices. */ static isl_stat print_edge(void **entry, void *user) { … } /* Print some debugging information about "scc_graph". * * In particular, print the nodes and the edges (both forward and backward). */ void isl_scc_graph_dump(struct isl_scc_graph *scc_graph) { … } /* Free all memory allocated for "scc_graph" and return NULL. */ struct isl_scc_graph *isl_scc_graph_free(struct isl_scc_graph *scc_graph) { … } /* Return an encoding of the local SCC index "pos" in "scc_graph" * as a pointer. * In particular, return a pointer to the corresponding entry * in scc_graph->graph_scc. */ static void *isl_scc_graph_encode_local_index(struct isl_scc_graph *scc_graph, int pos) { … } /* Return the local SCC index in "scc_graph" corresponding * to the "data" encoding in the edge table. */ static int isl_scc_graph_local_index(struct isl_scc_graph *scc_graph, int *data) { … } /* isl_hash_table_find callback to check whether the given entry * refers to an SCC encoded as "val". */ static isl_bool is_scc_node(const void *entry, const void *val) { … } /* Return the edge from local SCC index "src" to local SCC index "dst" * in "edge_table" of "scc_graph", creating one if "reserve" is set. * If "reserve" is not set, then return isl_hash_table_entry_none * if there is no such edge. * * The destination of the edge is encoded as a pointer * to the corresponding entry in scc_graph->graph_scc. */ struct isl_hash_table_entry *isl_scc_graph_find_edge( struct isl_scc_graph *scc_graph, struct isl_hash_table **edge_table, int src, int dst, int reserve) { … } /* Remove the edge between the SCCs with local indices "src" and * "dst" in "scc_graph", if it exits. * Return isl_bool_true if this is the case. * * The edge is only removed from scc_graph->edge_table. * scc_graph->reverse_edge_table is assumed to be empty * when this function is called. */ static isl_bool isl_scc_graph_remove_edge(struct isl_scc_graph *scc_graph, int src, int dst) { … } /* Internal data structure used by next_nodes. * * "scc_graph" is the SCC graph. * "next" collects the next nodes. * "n" is the number of next nodes already collected. */ struct isl_extract_dst_data { … }; /* Given an entry in the edge table, add the corresponding * target local SCC index to data->next. */ static isl_stat extract_dst(void **entry, void *user) { … } /* isl_sort callback for sorting integers in increasing order. */ static int cmp_int(const void *a, const void *b, void *data) { … } /* Return the local indices of the SCCs in "scc_graph" * for which there is an edge from the SCC with local index "i". * The indices are returned in increasing order, * i.e., in the original topological order. */ static int *next_nodes(struct isl_scc_graph *scc_graph, int i) { … } /* Internal data structure for foreach_reachable. * * "scc_graph" is the SCC graph being visited. * "fn" is the function that needs to be called on each reachable node. * "user" is the user argument to "fn". */ struct isl_foreach_reachable_data { … }; static isl_stat foreach_reachable(struct isl_foreach_reachable_data *data, int pos); /* isl_hash_table_foreach callback for calling data->fn on each SCC * reachable from the SCC encoded in "entry", * continuing from an SCC as long as data->fn returns isl_bool_true. */ static isl_stat recurse_foreach_reachable(void **entry, void *user) { … } /* Call data->fn on each SCC reachable from the SCC with local index "pos", * continuing from an SCC as long as data->fn returns isl_bool_true. * * Handle chains directly and recurse when an SCC has more than one * outgoing edge. */ static isl_stat foreach_reachable(struct isl_foreach_reachable_data *data, int pos) { … } /* If there is an edge from data->src to "pos", then remove it. * Return isl_bool_true if descendants of "pos" still need to be considered. * * Descendants only need to be considered if no edge is removed. */ static isl_bool elim_or_next(int pos, void *user) { … } /* Remove transitive edges from "scc_graph". * * Consider the SCC nodes "i" in reverse topological order. * If there is more than one edge emanating from a node, * then eliminate the edges to those nodes that can also be reached * through an edge to a node with a smaller index. * In particular, consider all but the last next nodes "next[j]" * in reverse topological order. If any node "k" can be reached * from such a node for which there is also an edge from "i" * then this edge can be removed because this node can also * be reached from "i" through the edge to "next[j]". * If such an edge is removed, then any further descendant of "k" * does not need to be considered since these were already considered * for a previous "next[j]" equal to "k", or "k" is the last next node, * in which case there is no further node with an edge from "i". */ static struct isl_scc_graph *isl_scc_graph_reduce( struct isl_scc_graph *scc_graph) { … } /* Add an edge to "edge_table" between the SCCs with local indices "src" and * "dst" in "scc_graph". * * If the edge already appeared in the table, then it is simply overwritten * with the same information. */ static isl_stat isl_scc_graph_add_edge(struct isl_scc_graph *scc_graph, struct isl_hash_table **edge_table, int src, int dst) { … } /* Add an edge from "dst" to data->src * to data->scc_graph->reverse_edge_table. */ static isl_stat add_reverse(void **entry, void *user) { … } /* Add an (inverse) edge to scc_graph->reverse_edge_table * for each edge in scc_graph->edge_table. */ static struct isl_scc_graph *isl_scc_graph_add_reverse_edges( struct isl_scc_graph *scc_graph) { … } /* Given an edge in the schedule graph, add an edge between * the corresponding SCCs in "scc_graph", if they are distinct. * * This function is used to create edges in the original isl_scc_graph. * where the local SCC indices are equal to the corresponding global * indices. */ static isl_stat add_scc_edge(void **entry, void *user) { … } /* Allocate an isl_scc_graph for ordering "n" SCCs of "graph" * with clustering information in "c". * * The caller still needs to fill in the edges. */ static struct isl_scc_graph *isl_scc_graph_alloc(isl_ctx *ctx, int n, struct isl_sched_graph *graph, struct isl_clustering *c) { … } /* Construct an isl_scc_graph for ordering the SCCs of "graph", * where each SCC i consists of the single cluster determined * by c->scc_cluster[i]. The nodes in this cluster all have * their "scc" field set to i. * * The initial isl_scc_graph has as many SCCs as "graph" and * their local indices are the same as their indices in "graph". * * Add edges between different SCCs for each (conditional) validity edge * between nodes in those SCCs, remove transitive edges and * construct the inverse edges from the remaining forward edges. */ struct isl_scc_graph *isl_scc_graph_from_sched_graph(isl_ctx *ctx, struct isl_sched_graph *graph, struct isl_clustering *c) { … } /* Internal data structure for copy_edge. * * "scc_graph" is the original graph. * "sub" is the subgraph to which edges are being copied. * "src" is the local index in "scc_graph" of the source of the edges * currently being copied. */ struct isl_copy_edge_data { … }; /* isl_hash_table_foreach callback for copying the edge * from data->src to the node identified by "entry" * to data->sub, provided the two nodes belong to the same component. * Note that by construction, there are no edges between different components * in the region handled by detect_components, but there may * be edges to nodes outside this region. * The components therefore need to be initialized for all nodes * in isl_scc_graph_init_component. */ static isl_stat copy_edge(void **entry, void *user) { … } /* Construct a subgraph of "scc_graph" for the components * consisting of the "n" SCCs with local indices in "pos". * These SCCs have the same value in scc_graph->component and * this value is different from that of any other SCC. * * The forward edges with source and destination in the component * are copied from "scc_graph". * The local index in the subgraph corresponding to a local index * in "scc_graph" is stored in scc_graph->pos for use by copy_edge(). * The inverse edges are constructed directly from the forward edges. */ static struct isl_scc_graph *isl_scc_graph_sub(struct isl_scc_graph *scc_graph, int *pos, int n) { … } /* Return a union of universe domains corresponding to the nodes * in the SCC with local index "pos". */ static __isl_give isl_union_set *isl_scc_graph_extract_local_scc( struct isl_scc_graph *scc_graph, int pos) { … } /* Construct a filter corresponding to a sequence of "n" local SCC indices * determined by successive calls to "el", * add this filter to "list" and * return the result. */ static __isl_give isl_union_set_list *add_scc_seq( struct isl_scc_graph *scc_graph, int (*el)(int i, void *user), void *user, int n, __isl_take isl_union_set_list *list) { … } /* add_scc_seq callback that, on successive calls, returns a sequence * of local SCC indices starting at "first". */ static int offset(int i, void *user) { … } /* Construct a filter corresponding to a sequence of "n" local SCC indices * starting at "first", add this filter to "list" and return the result. */ static __isl_give isl_union_set_list *isl_scc_graph_add_scc_seq( struct isl_scc_graph *scc_graph, int first, int n, __isl_take isl_union_set_list *list) { … } /* add_scc_seq callback that, on successive calls, returns the sequence * of local SCC indices in "seq". */ static int at(int i, void *user) { … } /* Construct a filter corresponding to the sequence of "n" local SCC indices * stored in "seq", add this filter to "list" and return the result. */ static __isl_give isl_union_set_list *isl_scc_graph_add_scc_indirect_seq( struct isl_scc_graph *scc_graph, int *seq, int n, __isl_take isl_union_set_list *list) { … } /* Extract out a list of filters for a sequence node that splits * the graph along the SCC with local index "pos". * * The list contains (at most) three elements, * the SCCs before "pos" (in the topological order), * "pos" itself, and * the SCCs after "pos". */ static __isl_give isl_union_set_list *extract_split_scc( struct isl_scc_graph *scc_graph, int pos) { … } /* Call isl_schedule_node_compute_finish_band on the cluster * corresponding to the SCC with local index "pos". * * First obtain the corresponding SCC index in scc_graph->graph and * then obtain the corresponding cluster. */ static __isl_give isl_schedule_node *isl_scc_graph_finish_band( struct isl_scc_graph *scc_graph, __isl_take isl_schedule_node *node, int pos) { … } /* Given that the SCCs in "scc_graph" form a chain, * call isl_schedule_node_compute_finish_band on each of the clusters * in scc_graph->c and update "node" to arrange for them to be executed * in topological order. */ static __isl_give isl_schedule_node *isl_scc_graph_chain( struct isl_scc_graph *scc_graph, __isl_take isl_schedule_node *node) { … } /* Recursively call isl_scc_graph_decompose on a subgraph * consisting of the "n" SCCs with local indices in "pos". * * If this component contains only a single SCC, * then there is no need for a further recursion and * isl_schedule_node_compute_finish_band can be called directly. */ static __isl_give isl_schedule_node *recurse(struct isl_scc_graph *scc_graph, int *pos, int n, __isl_take isl_schedule_node *node) { … } /* Initialize the component field of "scc_graph". * Initially, each SCC belongs to its own single-element component. * * Note that the SCC on which isl_scc_graph_decompose performs a split * also needs to be assigned a component because the components * are also used in copy_edge to extract a subgraph. */ static void isl_scc_graph_init_component(struct isl_scc_graph *scc_graph) { … } /* Set the component of "a" to be the same as that of "b" and * return the original component of "a". */ static int assign(int *component, int a, int b) { … } /* Merge the components containing the SCCs with indices "a" and "b". * * If "a" and "b" already belong to the same component, then nothing * needs to be done. * Otherwise, make sure both point to the same component. * In particular, use the SCC in the component entries with the smallest index. * If the other SCC was the first of its component then the entire * component now (eventually) points to the other component. * Otherwise, the earlier parts of the component still need * to be merged with the other component. * * At each stage, either a or b is replaced by either a or b itself, * in which case the merging terminates because a and b already * point to the same component, or an SCC index with a smaller value. * This ensures the merging terminates at some point. */ static void isl_scc_graph_merge_src_dst(struct isl_scc_graph *scc_graph, int a, int b) { … } /* Internal data structure for isl_scc_graph_merge_components. * * "scc_graph" is the SCC graph containing the edges. * "src" is the local index of the source SCC. * "end" is the local index beyond the sequence being considered. */ struct isl_merge_src_dst_data { … }; /* isl_hash_table_foreach callback for merging the components * of data->src and the node represented by "entry", provided * it is within the sequence being considered. */ static isl_stat merge_src_dst(void **entry, void *user) { … } /* Merge components of the "n" SCCs starting at "first" that are connected * by an edge. */ static isl_stat isl_scc_graph_merge_components(struct isl_scc_graph *scc_graph, int first, int n) { … } /* Sort the "n" local SCC indices starting at "first" according * to component, store them in scc_graph->sorted and * return the number of components. * The sizes of the components are stored in scc_graph->size. * Only positions starting at "first" are used within * scc_graph->sorted and scc_graph->size. * * The representation of the components is first normalized. * The normalization ensures that each SCC in a component * points to the first SCC in the component, whereas * before this function is called, some SCCs may only point * to some other SCC in the component with a smaller index. * * Internally, the sizes of the components are first stored * at indices corresponding to the first SCC in the component. * They are subsequently moved into consecutive positions * while reordering the local indices. * This reordering is performed by first determining the position * of the first SCC in each component and * then putting the "n" local indices in the right position * according to the component, preserving the topological order * within each component. */ static int isl_scc_graph_sort_components(struct isl_scc_graph *scc_graph, int first, int n) { … } /* Extract out a list of filters for a set node that splits up * the graph into "n_component" components. * "first" is the initial position in "scc_graph" where information * about the components is stored. * In particular, the first "n_component" entries of scc_graph->size * at this position contain the number of SCCs in each component. * The entries of scc_graph->sorted starting at "first" * contain the local indices of the SCC in those components. */ static __isl_give isl_union_set_list *extract_components( struct isl_scc_graph *scc_graph, int first, int n_component) { … } /* Detect components in the subgraph consisting of the "n" SCCs * with local index starting at "first" and further decompose them, * calling isl_schedule_node_compute_finish_band on each * of the corresponding clusters. * * If there is only one SCC, then isl_schedule_node_compute_finish_band * can be called directly. * Otherwise, determine the components and rearrange the local indices * according to component, but preserving the topological order within * each component, in scc_graph->sorted. The sizes of the components * are stored in scc_graph->size. * If there is only one component, it can be further decomposed * directly by a call to recurse(). * Otherwise, introduce a set node separating the components and * call recurse() on each component separately. */ static __isl_give isl_schedule_node *detect_components( struct isl_scc_graph *scc_graph, int first, int n, __isl_take isl_schedule_node *node) { … } /* Given a sequence node "node", where the filter at position "child" * represents the "n" SCCs with local index starting at "first", * detect components in this subgraph and further decompose them, * calling isl_schedule_node_compute_finish_band on each * of the corresponding clusters. */ static __isl_give isl_schedule_node *detect_components_at( struct isl_scc_graph *scc_graph, int first, int n, __isl_take isl_schedule_node *node, int child) { … } /* Return the local index of an SCC on which to split "scc_graph". * Return scc_graph->n if no suitable split SCC can be found. * * In particular, look for an SCC that is involved in the largest number * of edges. Splitting the graph on such an SCC has the highest chance * of exposing independent SCCs in the remaining part(s). * There is no point in splitting a chain of nodes, * so return scc_graph->n if the entire graph forms a chain. */ static int best_split(struct isl_scc_graph *scc_graph) { … } /* Call isl_schedule_node_compute_finish_band on each of the clusters * in scc_graph->c and update "node" to arrange for them to be executed * in an order possibly involving set nodes that generalizes * the topological order determined by the scc fields of the nodes * in scc_graph->graph. * * First try and find a suitable SCC on which to split the graph. * If no such SCC can be found then the graph forms a chain and * it is handled as such. * Otherwise, break up the graph into (at most) three parts, * the SCCs before the selected SCC (in the topological order), * the selected SCC itself, and * the SCCs after the selected SCC. * The first and last part (if they exist) are decomposed recursively and * the three parts are combined in a sequence. * * Since the outermost node of the recursive pieces may also be a sequence, * these potential sequence nodes are spliced into the top-level sequence node. */ __isl_give isl_schedule_node *isl_scc_graph_decompose( struct isl_scc_graph *scc_graph, __isl_take isl_schedule_node *node) { … }
Codebase Browser
llvm