2 * Copyright 2010-2011 INRIA Saclay
3 * Copyright 2021 Sven Verdoolaege
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
19 #include <isl/constraint.h>
20 #include <isl/union_set.h>
21 #include <isl/union_map.h>
26 /* Add parameters with identifiers "ids" to "set".
28 static __isl_give isl_set
*add_params(__isl_take isl_set
*set
,
29 __isl_keep isl_id_list
*ids
)
34 n
= isl_id_list_n_id(ids
);
36 nparam
= isl_set_dim(set
, isl_dim_param
);
37 set
= isl_set_add_dims(set
, isl_dim_param
, n
);
39 for (i
= 0; i
< n
; ++i
) {
42 id
= isl_id_list_get_id(ids
, i
);
43 set
= isl_set_set_dim_id(set
, isl_dim_param
, nparam
+ i
, id
);
49 /* Equate the dimensions of "set" starting at "first" to
50 * freshly created parameters with identifiers "ids".
51 * The number of equated dimensions is equal to the number of elements in "ids".
53 static __isl_give isl_set
*parametrize(__isl_take isl_set
*set
,
54 int first
, __isl_keep isl_id_list
*ids
)
59 nparam
= isl_set_dim(set
, isl_dim_param
);
61 set
= add_params(set
, ids
);
63 n
= isl_id_list_n_id(ids
);
64 for (i
= 0; i
< n
; ++i
)
65 set
= isl_set_equate(set
, isl_dim_param
, nparam
+ i
,
66 isl_dim_set
, first
+ i
);
71 /* Given a parameter space "space", create a set of dimension "len"
72 * of which the dimensions starting at "first" are equated to
73 * freshly created parameters with identifiers "ids".
75 __isl_give isl_set
*parametrization(__isl_take isl_space
*space
,
76 int len
, int first
, __isl_keep isl_id_list
*ids
)
80 space
= isl_space_set_from_params(space
);
81 space
= isl_space_add_dims(space
, isl_dim_set
, len
);
82 set
= isl_set_universe(space
);
84 return parametrize(set
, first
, ids
);
87 /* Load and return a schedule from a file called "filename".
89 static __isl_give isl_schedule
*load_schedule(isl_ctx
*ctx
,
93 isl_schedule
*schedule
;
95 file
= fopen(filename
, "r");
97 fprintf(stderr
, "Unable to open '%s' for reading\n", filename
);
100 schedule
= isl_schedule_read_from_file(ctx
, file
);
106 /* Save the schedule "schedule" to a file called "filename".
107 * The schedule is printed in block style.
109 static void save_schedule(__isl_keep isl_schedule
*schedule
,
110 const char *filename
)
119 file
= fopen(filename
, "w");
121 fprintf(stderr
, "Unable to open '%s' for writing\n", filename
);
124 ctx
= isl_schedule_get_ctx(schedule
);
125 p
= isl_printer_to_file(ctx
, file
);
126 p
= isl_printer_set_yaml_style(p
, ISL_YAML_STYLE_BLOCK
);
127 p
= isl_printer_print_schedule(p
, schedule
);
132 /* Compute a schedule on the domain of "sc" that respects the schedule
133 * constraints in "sc", without trying to combine groups of statements.
135 __isl_give isl_schedule
*ppcg_compute_non_grouping_schedule(
136 __isl_take isl_schedule_constraints
*sc
, struct ppcg_options
*options
)
138 if (options
->debug
->dump_schedule_constraints
)
139 isl_schedule_constraints_dump(sc
);
140 return isl_schedule_constraints_compute_schedule(sc
);
143 /* Compute a schedule on the domain of "sc" that respects the schedule
144 * constraints in "sc".
146 * "schedule" is a known correct schedule that is used to combine
147 * groups of statements if options->group_chains is set.
149 __isl_give isl_schedule
*ppcg_compute_schedule(
150 __isl_take isl_schedule_constraints
*sc
,
151 __isl_keep isl_schedule
*schedule
, struct ppcg_options
*options
)
153 if (options
->group_chains
)
154 return ppcg_compute_grouping_schedule(sc
, schedule
, options
);
155 return ppcg_compute_non_grouping_schedule(sc
, options
);
158 /* Obtain a schedule, either by reading it form a file
159 * or by computing it using "compute".
160 * Also take care of saving the computed schedule and/or
161 * dumping the obtained schedule if requested by the user.
163 __isl_give isl_schedule
*ppcg_get_schedule(isl_ctx
*ctx
,
164 struct ppcg_options
*options
,
165 __isl_give isl_schedule
*(*compute
)(void *user
), void *user
)
167 isl_schedule
*schedule
;
169 if (options
->load_schedule_file
) {
170 schedule
= load_schedule(ctx
, options
->load_schedule_file
);
172 schedule
= compute(user
);
173 if (options
->save_schedule_file
)
174 save_schedule(schedule
, options
->save_schedule_file
);
176 if (options
->debug
->dump_schedule
)
177 isl_schedule_dump(schedule
);
182 /* Mark all dimensions in the band node "node" to be of "type".
184 __isl_give isl_schedule_node
*ppcg_set_schedule_node_type(
185 __isl_take isl_schedule_node
*node
, enum isl_ast_loop_type type
)
189 n
= isl_schedule_node_band_n_member(node
);
190 for (i
= 0; i
< n
; ++i
)
191 node
= isl_schedule_node_band_member_set_ast_loop_type(node
, i
,
197 /* Does "tile" represent a trivial lattice tile, i.e.,
198 * one with size 1 in all directions?
200 static isl_bool
lattice_is_trivial(__isl_keep isl_fixed_box
*tile
)
205 isl_multi_val
*zero
, *one
;
207 size
= isl_fixed_box_get_size(tile
);
208 zero
= isl_multi_val_sub(isl_multi_val_copy(size
),
209 isl_multi_val_copy(size
));
210 val_one
= isl_val_one(isl_fixed_box_get_ctx(tile
));
211 one
= isl_multi_val_add_val(zero
, val_one
);
212 trivial
= isl_multi_val_plain_is_equal(size
, one
);
213 isl_multi_val_free(size
);
214 isl_multi_val_free(one
);
219 /* Given that the elements of "set" lie on a (rectangular) lattice
220 * with tile "tile", scale it down such that the origin of the result
221 * corresponds to "tile".
223 * The lattice is of the form
227 * Plug this into "set" to obtain a set in terms of "j"
228 * with j = 0 corresponding to offset in "set".
230 static __isl_give isl_set
*scale_down_set(__isl_keep isl_fixed_box
*tile
,
231 __isl_take isl_set
*set
)
235 isl_multi_aff
*offset
;
237 isl_multi_aff
*to_lattice
;
239 size
= isl_fixed_box_get_size(tile
);
240 offset
= isl_fixed_box_get_offset(tile
);
241 space
= isl_multi_aff_get_space(offset
);
242 id
= isl_space_identity_multi_aff_on_domain(isl_space_copy(space
));
243 offset
= isl_multi_aff_insert_domain(offset
, space
);
244 to_lattice
= isl_multi_aff_scale_multi_val(id
, size
);
245 to_lattice
= isl_multi_aff_add(to_lattice
, offset
);
246 set
= isl_set_preimage_multi_aff(set
, to_lattice
);
251 /* Given that the schedule values of the band node "node"
252 * lie on a (rectangular) lattice with tile "tile",
253 * scale it down such that the values corresponding to "tile"
254 * are mapped to the origin.
255 * "domain" is the (universe) domain reaching "node".
257 * The lattice is of the form
261 * Subtract offset and scale down by size.
263 static __isl_give isl_schedule_node
*scale_down_band(
264 __isl_keep isl_fixed_box
*tile
, __isl_take isl_schedule_node
*node
,
265 __isl_keep isl_union_set
*domain
)
268 isl_multi_aff
*offset
;
269 isl_multi_union_pw_aff
*mupa
;
271 size
= isl_fixed_box_get_size(tile
);
272 offset
= isl_multi_aff_neg(isl_fixed_box_get_offset(tile
));
273 domain
= isl_union_set_copy(domain
);
274 mupa
= isl_multi_union_pw_aff_multi_aff_on_domain(domain
, offset
);
275 node
= isl_schedule_node_band_shift(node
, mupa
);
276 node
= isl_schedule_node_band_scale_down(node
, size
);
281 /* Try and shift the given band node to the origin after
282 * potentially scaling it down first.
284 * In particular, obtain the set of schedule values and
285 * first check if they lie on a non-trivial (rectangular) lattice.
286 * If so, scale down both the band node and the set. Then
287 * compute the element-wise minimal value, which may
288 * depend on the parameters.
289 * If this results in any piecewise expressions,
290 * then do not perform any shifting as that may
291 * very well make the resulting code more complicated.
292 * Otherwise shift the band by the opposite of this minimal value.
294 static __isl_give isl_schedule_node
*scale_down_and_shift_to_origin(
295 __isl_take isl_schedule_node
*node
)
297 isl_bool is_multi_aff
, trivial
;
299 isl_union_set
*domain
, *range
;
300 isl_union_map
*partial
;
303 isl_multi_pw_aff
*min
;
304 isl_multi_aff
*min_ma
, *shift
;
305 isl_multi_union_pw_aff
*mupa
;
308 partial
= isl_schedule_node_band_get_partial_schedule_union_map(node
);
309 domain
= isl_schedule_node_get_domain(node
);
310 range
= isl_union_set_apply(isl_union_set_copy(domain
), partial
);
311 space
= isl_schedule_node_band_get_space(node
);
312 set
= isl_union_set_extract_set(range
, space
);
313 isl_union_set_free(range
);
314 domain
= isl_union_set_universe(domain
);
316 tile
= isl_set_get_lattice_tile(set
);
317 trivial
= lattice_is_trivial(tile
);
319 node
= isl_schedule_node_free(node
);
320 } else if (!trivial
) {
321 set
= scale_down_set(tile
, set
);
322 node
= scale_down_band(tile
, node
, domain
);
324 isl_fixed_box_free(tile
);
326 min
= isl_set_min_multi_pw_aff(set
);
327 min_domain
= isl_multi_pw_aff_domain(isl_multi_pw_aff_copy(min
));
328 min
= isl_multi_pw_aff_gist(min
, min_domain
);
329 is_multi_aff
= isl_multi_pw_aff_isa_multi_aff(min
);
330 if (is_multi_aff
< 0 || !is_multi_aff
) {
331 isl_union_set_free(domain
);
332 isl_multi_pw_aff_free(min
);
333 if (is_multi_aff
< 0)
334 return isl_schedule_node_free(node
);
338 min_ma
= isl_multi_pw_aff_as_multi_aff(min
);
339 shift
= isl_multi_aff_neg(min_ma
);
340 mupa
= isl_multi_union_pw_aff_multi_aff_on_domain(domain
, shift
);
341 node
= isl_schedule_node_band_shift(node
, mupa
);
346 /* Tile "node" with tile sizes "sizes", but first try and shift the band
348 * Tiling a band that does not start at the origin is likely
349 * to result in initial partial tiles.
351 __isl_give isl_schedule_node
*ppcg_tile(__isl_take isl_schedule_node
*node
,
352 __isl_take isl_multi_val
*sizes
)
354 node
= scale_down_and_shift_to_origin(node
);
355 return isl_schedule_node_band_tile(node
, sizes
);