290 lines · c
1#ifndef ISL_SCHEDULER_H2#define ISL_SCHEDULER_H3 4#include <isl/aff_type.h>5#include <isl/hash.h>6#include <isl/id_type.h>7#include <isl/map_type.h>8#include <isl/map_to_basic_set.h>9#include <isl/mat.h>10#include <isl/space_type.h>11#include <isl/set_type.h>12#include <isl/val_type.h>13#include <isl/vec.h>14#include <isl/union_map_type.h>15 16#include "isl_schedule_constraints.h"17#include "isl_tab.h"18 19/* Internal information about a node that is used during the construction20 * of a schedule.21 * space represents the original space in which the domain lives;22 * that is, the space is not affected by compression23 * sched is a matrix representation of the schedule being constructed24 * for this node; if compressed is set, then this schedule is25 * defined over the compressed domain space26 * sched_map is an isl_map representation of the same (partial) schedule27 * sched_map may be NULL; if compressed is set, then this map28 * is defined over the uncompressed domain space29 * rank is the number of linearly independent rows in the linear part30 * of sched31 * the rows of "vmap" represent a change of basis for the node32 * variables; the first rank rows span the linear part of33 * the schedule rows; the remaining rows are linearly independent34 * the rows of "indep" represent linear combinations of the schedule35 * coefficients that are non-zero when the schedule coefficients are36 * linearly independent of previously computed schedule rows.37 * start is the first variable in the LP problem in the sequences that38 * represents the schedule coefficients of this node39 * nvar is the dimension of the (compressed) domain40 * nparam is the number of parameters or 0 if we are not constructing41 * a parametric schedule42 *43 * If compressed is set, then hull represents the constraints44 * that were used to derive the compression, while compress and45 * decompress map the original space to the compressed space and46 * vice versa.47 *48 * scc is the index of SCC (or WCC) this node belongs to49 *50 * "cluster" is only used inside extract_clusters and identifies51 * the cluster of SCCs that the node belongs to.52 *53 * coincident contains a boolean for each of the rows of the schedule,54 * indicating whether the corresponding scheduling dimension satisfies55 * the coincidence constraints in the sense that the corresponding56 * dependence distances are zero.57 *58 * If the schedule_treat_coalescing option is set, then59 * "sizes" contains the sizes of the (compressed) instance set60 * in each direction. If there is no fixed size in a given direction,61 * then the corresponding size value is set to infinity.62 * If the schedule_treat_coalescing option or the schedule_max_coefficient63 * option is set, then "max" contains the maximal values for64 * schedule coefficients of the (compressed) variables. If no bound65 * needs to be imposed on a particular variable, then the corresponding66 * value is negative.67 * If not NULL, then "bounds" contains a non-parametric set68 * in the compressed space that is bounded by the size in each direction.69 */70struct isl_sched_node {71 isl_space *space;72 int compressed;73 isl_set *hull;74 isl_multi_aff *compress;75 isl_pw_multi_aff *decompress;76 isl_mat *sched;77 isl_map *sched_map;78 int rank;79 isl_mat *indep;80 isl_mat *vmap;81 int start;82 int nvar;83 int nparam;84 85 int scc;86 int cluster;87 88 int *coincident;89 90 isl_multi_val *sizes;91 isl_basic_set *bounds;92 isl_vec *max;93};94 95int isl_sched_node_scc_exactly(struct isl_sched_node *node, int scc);96 97isl_stat isl_sched_node_update_vmap(struct isl_sched_node *node);98__isl_give isl_multi_aff *isl_sched_node_extract_partial_schedule_multi_aff(99 struct isl_sched_node *node, int first, int n);100 101/* An edge in the dependence graph. An edge may be used to102 * ensure validity of the generated schedule, to minimize the dependence103 * distance or both104 *105 * map is the dependence relation, with i -> j in the map if j depends on i106 * tagged_condition and tagged_validity contain the union of all tagged107 * condition or conditional validity dependence relations that108 * specialize the dependence relation "map"; that is,109 * if (i -> a) -> (j -> b) is an element of "tagged_condition"110 * or "tagged_validity", then i -> j is an element of "map".111 * If these fields are NULL, then they represent the empty relation.112 * src is the source node113 * dst is the sink node114 *115 * types is a bit vector containing the types of this edge.116 * validity is set if the edge is used to ensure correctness117 * coincidence is used to enforce zero dependence distances118 * proximity is set if the edge is used to minimize dependence distances119 * condition is set if the edge represents a condition120 * for a conditional validity schedule constraint121 * local can only be set for condition edges and indicates that122 * the dependence distance over the edge should be zero123 * conditional_validity is set if the edge is used to conditionally124 * ensure correctness125 *126 * For validity edges, start and end mark the sequence of inequality127 * constraints in the LP problem that encode the validity constraint128 * corresponding to this edge.129 *130 * During clustering, an edge may be marked "no_merge" if it should131 * not be used to merge clusters.132 * The weight is also only used during clustering and it is133 * an indication of how many schedule dimensions on either side134 * of the schedule constraints can be aligned.135 * If the weight is negative, then this means that this edge was postponed136 * by has_bounded_distances or any_no_merge. The original weight can137 * be retrieved by adding 1 + graph->max_weight, with "graph"138 * the graph containing this edge.139 */140struct isl_sched_edge {141 isl_map *map;142 isl_union_map *tagged_condition;143 isl_union_map *tagged_validity;144 145 struct isl_sched_node *src;146 struct isl_sched_node *dst;147 148 unsigned types;149 150 int start;151 int end;152 153 int no_merge;154 int weight;155};156 157int isl_sched_edge_has_type(struct isl_sched_edge *edge,158 enum isl_edge_type type);159int isl_sched_edge_is_condition(struct isl_sched_edge *edge);160int isl_sched_edge_is_conditional_validity(struct isl_sched_edge *edge);161int isl_sched_edge_scc_exactly(struct isl_sched_edge *edge, int scc);162int isl_sched_edge_is_proximity(struct isl_sched_edge *edge);163 164/* Internal information about the dependence graph used during165 * the construction of the schedule.166 *167 * intra_hmap is a cache, mapping dependence relations to their dual,168 * for dependences from a node to itself, possibly without169 * coefficients for the parameters170 * intra_hmap_param is a cache, mapping dependence relations to their dual,171 * for dependences from a node to itself, including coefficients172 * for the parameters173 * inter_hmap is a cache, mapping dependence relations to their dual,174 * for dependences between distinct nodes175 * if compression is involved then the key for these maps176 * is the original, uncompressed dependence relation, while177 * the value is the dual of the compressed dependence relation.178 *179 * n is the number of nodes180 * node is the list of nodes181 * maxvar is the maximal number of variables over all nodes182 * max_row is the allocated number of rows in the schedule183 * n_row is the current (maximal) number of linearly independent184 * rows in the node schedules185 * n_total_row is the current number of rows in the node schedules186 * band_start is the starting row in the node schedules of the current band187 * root is set to the original dependence graph from which this graph188 * is derived through splitting. If this graph is not the result of189 * splitting, then the root field points to the graph itself.190 *191 * sorted contains a list of node indices sorted according to the192 * SCC to which a node belongs193 *194 * n_edge is the number of edges195 * edge is the list of edges196 * max_edge contains the maximal number of edges of each type;197 * in particular, it contains the number of edges in the inital graph.198 * edge_table contains pointers into the edge array, hashed on the source199 * and sink spaces; there is one such table for each type;200 * a given edge may be referenced from more than one table201 * if the corresponding relation appears in more than one of the202 * sets of dependences; however, for each type there is only203 * a single edge between a given pair of source and sink space204 * in the entire graph205 *206 * node_table contains pointers into the node array, hashed on the space tuples207 *208 * region contains a list of variable sequences that should be non-trivial209 *210 * lp contains the (I)LP problem used to obtain new schedule rows211 *212 * src_scc and dst_scc are the source and sink SCCs of an edge with213 * conflicting constraints214 *215 * scc represents the number of components216 * weak is set if the components are weakly connected217 *218 * max_weight is used during clustering and represents the maximal219 * weight of the relevant proximity edges.220 */221struct isl_sched_graph {222 isl_map_to_basic_set *intra_hmap;223 isl_map_to_basic_set *intra_hmap_param;224 isl_map_to_basic_set *inter_hmap;225 226 struct isl_sched_node *node;227 int n;228 int maxvar;229 int max_row;230 int n_row;231 232 int *sorted;233 234 int n_total_row;235 int band_start;236 237 struct isl_sched_graph *root;238 239 struct isl_sched_edge *edge;240 int n_edge;241 int max_edge[isl_edge_last + 1];242 struct isl_hash_table *edge_table[isl_edge_last + 1];243 244 struct isl_hash_table *node_table;245 struct isl_trivial_region *region;246 247 isl_basic_set *lp;248 249 int src_scc;250 int dst_scc;251 252 int scc;253 int weak;254 255 int max_weight;256};257 258isl_stat isl_sched_graph_init(struct isl_sched_graph *graph,259 __isl_keep isl_schedule_constraints *sc);260void isl_sched_graph_free(isl_ctx *ctx, struct isl_sched_graph *graph);261 262int isl_sched_graph_is_node(struct isl_sched_graph *graph,263 struct isl_sched_node *node);264isl_bool isl_sched_graph_has_validity_edge(struct isl_sched_graph *graph,265 struct isl_sched_node *src, struct isl_sched_node *dst);266 267struct isl_sched_node *isl_sched_graph_find_node(isl_ctx *ctx,268 struct isl_sched_graph *graph, __isl_keep isl_space *space);269 270isl_stat isl_sched_graph_detect_ccs(isl_ctx *ctx, struct isl_sched_graph *graph,271 isl_bool (*follows)(int i, int j, void *user));272 273__isl_give isl_union_set *isl_sched_graph_extract_scc(isl_ctx *ctx,274 struct isl_sched_graph *graph, int scc);275__isl_give isl_union_set_list *isl_sched_graph_extract_sccs(isl_ctx *ctx,276 struct isl_sched_graph *graph);277isl_stat isl_sched_graph_extract_sub_graph(isl_ctx *ctx,278 struct isl_sched_graph *graph,279 int (*node_pred)(struct isl_sched_node *node, int data),280 int (*edge_pred)(struct isl_sched_edge *edge, int data),281 int data, struct isl_sched_graph *sub);282isl_stat isl_sched_graph_compute_maxvar(struct isl_sched_graph *graph);283isl_stat isl_schedule_node_compute_wcc_band(isl_ctx *ctx,284 struct isl_sched_graph *graph);285__isl_give isl_schedule_node *isl_schedule_node_compute_finish_band(286 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,287 int initialized);288 289#endif290