isl_scheduler.h

   1 #ifndef ISL_SCHEDULER_H
   2 #define ISL_SCHEDULER_H
   3
   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 construction
  20  * of a schedule.
  21  * space represents the original space in which the domain lives;
  22  *      that is, the space is not affected by compression
  23  * sched is a matrix representation of the schedule being constructed
  24  *      for this node; if compressed is set, then this schedule is
  25  *      defined over the compressed domain space
  26  * sched_map is an isl_map representation of the same (partial) schedule
  27  *      sched_map may be NULL; if compressed is set, then this map
  28  *      is defined over the uncompressed domain space
  29  * rank is the number of linearly independent rows in the linear part
  30  *      of sched
  31  * the rows of "vmap" represent a change of basis for the node
  32  *      variables; the first rank rows span the linear part of
  33  *      the schedule rows; the remaining rows are linearly independent
  34  * the rows of "indep" represent linear combinations of the schedule
  35  * coefficients that are non-zero when the schedule coefficients are
  36  * linearly independent of previously computed schedule rows.
  37  * start is the first variable in the LP problem in the sequences that
  38  *      represents the schedule coefficients of this node
  39  * nvar is the dimension of the (compressed) domain
  40  * nparam is the number of parameters or 0 if we are not constructing
  41  *      a parametric schedule
  42  *
  43  * If compressed is set, then hull represents the constraints
  44  * that were used to derive the compression, while compress and
  45  * decompress map the original space to the compressed space and
  46  * vice versa.
  47  *
  48  * scc is the index of SCC (or WCC) this node belongs to
  49  *
  50  * "cluster" is only used inside extract_clusters and identifies
  51  * 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 satisfies
  55  * the coincidence constraints in the sense that the corresponding
  56  * dependence distances are zero.
  57  *
  58  * If the schedule_treat_coalescing option is set, then
  59  * "sizes" contains the sizes of the (compressed) instance set
  60  * 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_coefficient
  63  * option is set, then "max" contains the maximal values for
  64  * schedule coefficients of the (compressed) variables.  If no bound
  65  * needs to be imposed on a particular variable, then the corresponding
  66  * value is negative.
  67  * If not NULL, then "bounds" contains a non-parametric set
  68  * in the compressed space that is bounded by the size in each direction.
  69  */
  70 struct 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
  95 int isl_sched_node_scc_exactly(struct isl_sched_node *node, int scc);
  96
  97 isl_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 to
 102  * ensure validity of the generated schedule, to minimize the dependence
 103  * distance or both
 104  *
 105  * map is the dependence relation, with i -> j in the map if j depends on i
 106  * tagged_condition and tagged_validity contain the union of all tagged
 107  *      condition or conditional validity dependence relations that
 108  *      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 node
 113  * dst is the sink node
 114  *
 115  * types is a bit vector containing the types of this edge.
 116  * validity is set if the edge is used to ensure correctness
 117  * coincidence is used to enforce zero dependence distances
 118  * proximity is set if the edge is used to minimize dependence distances
 119  * condition is set if the edge represents a condition
 120  *      for a conditional validity schedule constraint
 121  * local can only be set for condition edges and indicates that
 122  *      the dependence distance over the edge should be zero
 123  * conditional_validity is set if the edge is used to conditionally
 124  *      ensure correctness
 125  *
 126  * For validity edges, start and end mark the sequence of inequality
 127  * constraints in the LP problem that encode the validity constraint
 128  * corresponding to this edge.
 129  *
 130  * During clustering, an edge may be marked "no_merge" if it should
 131  * not be used to merge clusters.
 132  * The weight is also only used during clustering and it is
 133  * an indication of how many schedule dimensions on either side
 134  * of the schedule constraints can be aligned.
 135  * If the weight is negative, then this means that this edge was postponed
 136  * by has_bounded_distances or any_no_merge.  The original weight can
 137  * be retrieved by adding 1 + graph->max_weight, with "graph"
 138  * the graph containing this edge.
 139  */
 140 struct 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
 157 int isl_sched_edge_has_type(struct isl_sched_edge *edge,
 158         enum isl_edge_type type);
 159 int isl_sched_edge_is_condition(struct isl_sched_edge *edge);
 160 int isl_sched_edge_is_conditional_validity(struct isl_sched_edge *edge);
 161 int isl_sched_edge_scc_exactly(struct isl_sched_edge *edge, int scc);
 162 int isl_sched_edge_is_proximity(struct isl_sched_edge *edge);
 163
 164 /* Internal information about the dependence graph used during
 165  * 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 without
 169  *      coefficients for the parameters
 170  * intra_hmap_param is a cache, mapping dependence relations to their dual,
 171  *      for dependences from a node to itself, including coefficients
 172  *      for the parameters
 173  * inter_hmap is a cache, mapping dependence relations to their dual,
 174  *      for dependences between distinct nodes
 175  * if compression is involved then the key for these maps
 176  * is the original, uncompressed dependence relation, while
 177  * the value is the dual of the compressed dependence relation.
 178  *
 179  * n is the number of nodes
 180  * node is the list of nodes
 181  * maxvar is the maximal number of variables over all nodes
 182  * max_row is the allocated number of rows in the schedule
 183  * n_row is the current (maximal) number of linearly independent
 184  *      rows in the node schedules
 185  * n_total_row is the current number of rows in the node schedules
 186  * band_start is the starting row in the node schedules of the current band
 187  * root is set to the original dependence graph from which this graph
 188  *      is derived through splitting.  If this graph is not the result of
 189  *      splitting, then the root field points to the graph itself.
 190  *
 191  * sorted contains a list of node indices sorted according to the
 192  *      SCC to which a node belongs
 193  *
 194  * n_edge is the number of edges
 195  * edge is the list of edges
 196  * 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 source
 199  *      and sink spaces; there is one such table for each type;
 200  *      a given edge may be referenced from more than one table
 201  *      if the corresponding relation appears in more than one of the
 202  *      sets of dependences; however, for each type there is only
 203  *      a single edge between a given pair of source and sink space
 204  *      in the entire graph
 205  *
 206  * node_table contains pointers into the node array, hashed on the space tuples
 207  *
 208  * region contains a list of variable sequences that should be non-trivial
 209  *
 210  * lp contains the (I)LP problem used to obtain new schedule rows
 211  *
 212  * src_scc and dst_scc are the source and sink SCCs of an edge with
 213  *      conflicting constraints
 214  *
 215  * scc represents the number of components
 216  * weak is set if the components are weakly connected
 217  *
 218  * max_weight is used during clustering and represents the maximal
 219  * weight of the relevant proximity edges.
 220  */
 221 struct 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
 258 isl_stat isl_sched_graph_init(struct isl_sched_graph *graph,
 259         __isl_keep isl_schedule_constraints *sc);
 260 void isl_sched_graph_free(isl_ctx *ctx, struct isl_sched_graph *graph);
 261
 262 int isl_sched_graph_is_node(struct isl_sched_graph *graph,
 263         struct isl_sched_node *node);
 264 isl_bool isl_sched_graph_has_validity_edge(struct isl_sched_graph *graph,
 265         struct isl_sched_node *src, struct isl_sched_node *dst);
 266
 267 struct isl_sched_node *isl_sched_graph_find_node(isl_ctx *ctx,
 268         struct isl_sched_graph *graph, __isl_keep isl_space *space);
 269
 270 isl_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_list *isl_sched_graph_extract_sccs(isl_ctx *ctx,
 274         struct isl_sched_graph *graph);
 275 isl_stat isl_sched_graph_extract_sub_graph(isl_ctx *ctx,
 276         struct isl_sched_graph *graph,
 277         int (*node_pred)(struct isl_sched_node *node, int data),
 278         int (*edge_pred)(struct isl_sched_edge *edge, int data),
 279         int data, struct isl_sched_graph *sub);
 280 isl_stat isl_sched_graph_compute_maxvar(struct isl_sched_graph *graph);
 281 isl_stat isl_schedule_node_compute_wcc_band(isl_ctx *ctx,
 282         struct isl_sched_graph *graph);
 283 __isl_give isl_schedule_node *isl_schedule_node_compute_finish_band(
 284         __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
 285         int initialized);
 286
 287 #endif