1 /* Graphite polyhedral representation.
2 Copyright (C) 2009-2015 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com> and
4 Tobias Grosser <grosser@fim.uni-passau.de>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 #ifndef GCC_GRAPHITE_POLY_H
23 #define GCC_GRAPHITE_POLY_H
27 #ifndef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
29 # define isl_stat_ok 0
32 typedef struct poly_dr
*poly_dr_p
;
34 typedef struct poly_bb
*poly_bb_p
;
36 typedef struct scop
*scop_p
;
38 typedef unsigned graphite_dim_t
;
40 static inline graphite_dim_t
scop_nb_params (scop_p
);
42 /* A data reference can write or read some memory or we
43 just know it may write some memory. */
47 /* PDR_MAY_READs are represented using PDR_READS. This does not
48 limit the expressiveness. */
55 /* An identifier for this PDR. */
58 /* The number of data refs identical to this one in the PBB. */
61 /* A pointer to compiler's data reference description. */
62 data_reference_p compiler_dr
;
64 /* A pointer to the PBB that contains this data reference. */
67 enum poly_dr_type type
;
69 /* The access polyhedron contains the polyhedral space this data
70 reference will access.
72 The polyhedron contains these dimensions:
75 Every memory access is classified in at least one alias set.
77 - The subscripts (s_0, ..., s_n):
78 The memory is accessed using zero or more subscript dimensions.
80 - The iteration domain (variables and parameters)
82 Do not hardcode the dimensions. Use the following accessor functions:
96 | if (unknown_function ())
103 The data access A[i][j+k] in alias set "5" is described like this:
108 | 0 -1 -1 0 0 1 0 = 0
109 | 0 0 0 0 1 0 0 >= 0 # The last four lines describe the
110 | 0 0 0 0 0 1 0 >= 0 # array size.
111 | 0 0 0 0 -1 0 1335 >= 0
112 | 0 0 0 0 0 -1 123 >= 0
114 The pointer "*p" in alias set "5" and "7" is described as a union of
128 "*p" accesses all of the object allocated with 'malloc'.
130 The scalar data access "m" is represented as an array with zero subscript
136 The difference between the graphite internal format for access data and
137 the OpenSop format is in the order of columns.
143 | 0 -1 -1 0 0 1 0 = 0
144 | 0 0 0 0 1 0 0 >= 0 # The last four lines describe the
145 | 0 0 0 0 0 1 0 >= 0 # array size.
146 | 0 0 0 0 -1 0 1335 >= 0
147 | 0 0 0 0 0 -1 123 >= 0
154 | 0 0 1 0 -1 -1 0 = 0
155 | 0 1 0 0 0 0 0 >= 0 # The last four lines describe the
156 | 0 0 1 0 0 0 0 >= 0 # array size.
157 | 0 -1 0 0 0 0 1335 >= 0
158 | 0 0 -1 0 0 0 123 >= 0
160 The OpenScop access function is printed as follows:
162 | 1 # The number of disjunct components in a union of access functions.
163 | R C O I L P # Described bellow.
167 | 0 0 1 0 -1 -1 0 = 0
168 | 0 1 0 0 0 0 0 >= 0 # The last four lines describe the
169 | 0 0 1 0 0 0 0 >= 0 # array size.
170 | 0 -1 0 0 0 0 1335 >= 0
171 | 0 0 -1 0 0 0 123 >= 0
175 - C: Number of columns.
176 - O: Number of output dimensions = alias set + number of subscripts.
177 - I: Number of input dimensions (iterators).
178 - L: Number of local (existentially quantified) dimensions.
179 - P: Number of parameters.
181 In the example, the vector "R C O I L P" is "7 7 3 2 0 1". */
183 isl_set
*subscript_sizes
;
185 /* The number of subscripts. */
186 graphite_dim_t nb_subscripts
;
189 #define PDR_ID(PDR) (PDR->id)
190 #define PDR_NB_REFS(PDR) (PDR->nb_refs)
191 #define PDR_CDR(PDR) (PDR->compiler_dr)
192 #define PDR_PBB(PDR) (PDR->pbb)
193 #define PDR_TYPE(PDR) (PDR->type)
194 #define PDR_ACCESSES(PDR) (NULL)
195 #define PDR_NB_SUBSCRIPTS(PDR) (PDR->nb_subscripts)
197 void new_poly_dr (poly_bb_p
, enum poly_dr_type
, data_reference_p
,
198 graphite_dim_t
, isl_map
*, isl_set
*);
199 void free_poly_dr (poly_dr_p
);
200 void debug_pdr (poly_dr_p
);
201 void print_pdr (FILE *, poly_dr_p
);
204 pdr_read_p (poly_dr_p pdr
)
206 return PDR_TYPE (pdr
) == PDR_READ
;
209 /* Returns true when PDR is a "write". */
212 pdr_write_p (poly_dr_p pdr
)
214 return PDR_TYPE (pdr
) == PDR_WRITE
;
217 /* Returns true when PDR is a "may write". */
220 pdr_may_write_p (poly_dr_p pdr
)
222 return PDR_TYPE (pdr
) == PDR_MAY_WRITE
;
225 /* POLY_BB represents a blackbox in the polyhedral model. */
229 /* Pointer to a basic block or a statement in the compiler. */
230 gimple_poly_bb_p black_box
;
232 /* Pointer to the SCOP containing this PBB. */
235 /* The iteration domain of this bb. The layout of this polyhedron
236 is I|G with I the iteration domain, G the context parameters.
240 for (i = a - 7*b + 8; i <= 3*a + 13*b + 20; i++)
241 for (j = 2; j <= 2*i + 5; j++)
242 for (k = 0; k <= 5; k++)
245 Loop iterators: i, j, k
255 The number of variables in the DOMAIN may change and is not
256 related to the number of loops in the original code. */
259 /* The data references we access. */
262 /* The original scattering. */
265 /* The transformed scattering. */
266 isl_map
*transformed
;
268 /* A copy of the transformed scattering. */
271 /* True when this PBB contains only a reduction statement. */
275 #define PBB_BLACK_BOX(PBB) ((gimple_poly_bb_p) PBB->black_box)
276 #define PBB_SCOP(PBB) (PBB->scop)
277 #define PBB_DRS(PBB) (PBB->drs)
278 #define PBB_IS_REDUCTION(PBB) (PBB->is_reduction)
280 extern poly_bb_p
new_poly_bb (scop_p
, gimple_poly_bb_p
);
281 extern void free_poly_bb (poly_bb_p
);
282 extern void debug_loop_vec (poly_bb_p
);
283 extern void print_pbb_domain (FILE *, poly_bb_p
);
284 extern void print_pbb (FILE *, poly_bb_p
);
285 extern void print_scop_context (FILE *, scop_p
);
286 extern void print_scop (FILE *, scop_p
);
287 extern void debug_pbb_domain (poly_bb_p
);
288 extern void debug_pbb (poly_bb_p
);
289 extern void print_pdrs (FILE *, poly_bb_p
);
290 extern void debug_pdrs (poly_bb_p
);
291 extern void debug_scop_context (scop_p
);
292 extern void debug_scop (scop_p
);
293 extern void print_scop_params (FILE *, scop_p
);
294 extern void debug_scop_params (scop_p
);
295 extern void print_iteration_domain (FILE *, poly_bb_p
);
296 extern void print_iteration_domains (FILE *, scop_p
);
297 extern void debug_iteration_domain (poly_bb_p
);
298 extern void debug_iteration_domains (scop_p
);
299 extern void print_isl_set (FILE *, isl_set
*);
300 extern void print_isl_map (FILE *, isl_map
*);
301 extern void print_isl_union_map (FILE *, isl_union_map
*);
302 extern void print_isl_aff (FILE *, isl_aff
*);
303 extern void print_isl_constraint (FILE *, isl_constraint
*);
304 extern void debug_isl_set (isl_set
*);
305 extern void debug_isl_map (isl_map
*);
306 extern void debug_isl_union_map (isl_union_map
*);
307 extern void debug_isl_aff (isl_aff
*);
308 extern void debug_isl_constraint (isl_constraint
*);
309 extern int scop_do_interchange (scop_p
);
310 extern int scop_do_strip_mine (scop_p
, int);
311 extern bool scop_do_block (scop_p
);
312 extern bool flatten_all_loops (scop_p
);
313 extern bool optimize_isl (scop_p
);
314 extern void pbb_number_of_iterations_at_time (poly_bb_p
, graphite_dim_t
, mpz_t
);
315 extern void debug_gmp_value (mpz_t
);
317 /* Returns a gimple_bb from BB. */
319 static inline gimple_poly_bb_p
320 gbb_from_bb (basic_block bb
)
322 return (gimple_poly_bb_p
) bb
->aux
;
325 /* The poly_bb of the BB. */
327 static inline poly_bb_p
328 pbb_from_bb (basic_block bb
)
330 return GBB_PBB (gbb_from_bb (bb
));
333 /* The basic block of the PBB. */
335 static inline basic_block
336 pbb_bb (poly_bb_p pbb
)
338 return GBB_BB (PBB_BLACK_BOX (pbb
));
342 pbb_index (poly_bb_p pbb
)
344 return pbb_bb (pbb
)->index
;
347 /* The loop of the PBB. */
350 pbb_loop (poly_bb_p pbb
)
352 return gbb_loop (PBB_BLACK_BOX (pbb
));
355 /* The scop that contains the PDR. */
358 pdr_scop (poly_dr_p pdr
)
360 return PBB_SCOP (PDR_PBB (pdr
));
363 /* Set black box of PBB to BLACKBOX. */
366 pbb_set_black_box (poly_bb_p pbb
, gimple_poly_bb_p black_box
)
368 pbb
->black_box
= black_box
;
371 /* A helper structure to keep track of data references, polyhedral BBs, and
377 invalid_alias_set
= -1
379 /* The data reference. */
382 /* The polyhedral BB containing this DR. */
385 /* ALIAS_SET is the SCC number assigned by a graph_dfs of the alias graph.
386 -1 is an invalid alias set. */
389 /* Construct a DR_INFO from a data reference DR, an ALIAS_SET, and a PBB. */
390 dr_info (data_reference_p dr
, poly_bb_p pbb
,
391 int alias_set
= invalid_alias_set
)
392 : dr (dr
), pbb (pbb
), alias_set (alias_set
) {}
395 /* A SCOP is a Static Control Part of the program, simple enough to be
396 represented in polyhedral form. */
399 /* A SCOP is defined as a SESE region. */
400 sese_info_p scop_info
;
402 /* Number of parameters in SCoP. */
403 graphite_dim_t nb_params
;
405 /* All the basic blocks in this scop that contain memory references
406 and that will be represented as statements in the polyhedral
410 /* All the data references in this scop. */
413 /* The context describes known restrictions concerning the parameters
414 and relations in between the parameters.
416 void f (int8_t a, uint_16_t b) {
421 Here we can add these restrictions to the context:
426 isl_set
*param_context
;
428 /* The context used internally by ISL. */
429 isl_ctx
*isl_context
;
431 /* The original dependence relations:
432 RAW are read after write dependences,
433 WAR are write after read dependences,
434 WAW are write after write dependences. */
435 isl_union_map
*must_raw
, *may_raw
, *must_raw_no_source
, *may_raw_no_source
,
436 *must_war
, *may_war
, *must_war_no_source
, *may_war_no_source
,
437 *must_waw
, *may_waw
, *must_waw_no_source
, *may_waw_no_source
;
439 /* True when the scop has been converted to its polyhedral
444 extern scop_p
new_scop (edge
, edge
);
445 extern void free_scop (scop_p
);
446 extern gimple_poly_bb_p
new_gimple_poly_bb (basic_block
, vec
<data_reference_p
>);
447 extern void free_gimple_poly_bb (gimple_poly_bb_p
);
448 extern void print_generated_program (FILE *, scop_p
);
449 extern void debug_generated_program (scop_p
);
450 extern int unify_scattering_dimensions (scop_p
);
451 extern bool apply_poly_transforms (scop_p
);
453 /* Set the region of SCOP to REGION. */
456 scop_set_region (scop_p scop
, sese_info_p region
)
458 scop
->scop_info
= region
;
461 /* Returns the number of parameters for SCOP. */
463 static inline graphite_dim_t
464 scop_nb_params (scop_p scop
)
466 return scop
->nb_params
;
469 /* Set the number of params of SCOP to NB_PARAMS. */
472 scop_set_nb_params (scop_p scop
, graphite_dim_t nb_params
)
474 scop
->nb_params
= nb_params
;
478 scop_get_dependences (scop_p scop
);
481 carries_deps (__isl_keep isl_union_map
*schedule
,
482 __isl_keep isl_union_map
*deps
,