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 */
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 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 */
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 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 */
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#endif
290

source code of polly/lib/External/isl/isl_scheduler.h