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 *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); 277 isl_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); 282 isl_stat isl_sched_graph_compute_maxvar(struct isl_sched_graph *graph); 283 isl_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 #endif 290