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
26 #include <isl/schedule.h>
28 #ifndef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
31 # define isl_stat_ok 0
34 typedef struct poly_dr
*poly_dr_p
;
36 typedef struct poly_bb
*poly_bb_p
;
38 typedef struct scop
*scop_p
;
40 typedef unsigned graphite_dim_t
;
42 static inline graphite_dim_t
scop_nb_params (scop_p
);
44 /* A data reference can write or read some memory or we
45 just know it may write some memory. */
49 /* PDR_MAY_READs are represented using PDR_READS. This does not
50 limit the expressiveness. */
57 /* An identifier for this PDR. */
60 /* The number of data refs identical to this one in the PBB. */
63 /* A pointer to the gimple stmt containing this reference. */
66 /* A pointer to the PBB that contains this data reference. */
69 enum poly_dr_type type
;
71 /* The access polyhedron contains the polyhedral space this data
72 reference will access.
74 The polyhedron contains these dimensions:
77 Every memory access is classified in at least one alias set.
79 - The subscripts (s_0, ..., s_n):
80 The memory is accessed using zero or more subscript dimensions.
82 - The iteration domain (variables and parameters)
84 Do not hardcode the dimensions. Use the following accessor functions:
98 | if (unknown_function ())
105 The data access A[i][j+k] in alias set "5" is described like this:
110 | 0 -1 -1 0 0 1 0 = 0
111 | 0 0 0 0 1 0 0 >= 0 # The last four lines describe the
112 | 0 0 0 0 0 1 0 >= 0 # array size.
113 | 0 0 0 0 -1 0 1335 >= 0
114 | 0 0 0 0 0 -1 123 >= 0
116 The pointer "*p" in alias set "5" and "7" is described as a union of
130 "*p" accesses all of the object allocated with 'malloc'.
132 The scalar data access "m" is represented as an array with zero subscript
138 The difference between the graphite internal format for access data and
139 the OpenSop format is in the order of columns.
145 | 0 -1 -1 0 0 1 0 = 0
146 | 0 0 0 0 1 0 0 >= 0 # The last four lines describe the
147 | 0 0 0 0 0 1 0 >= 0 # array size.
148 | 0 0 0 0 -1 0 1335 >= 0
149 | 0 0 0 0 0 -1 123 >= 0
156 | 0 0 1 0 -1 -1 0 = 0
157 | 0 1 0 0 0 0 0 >= 0 # The last four lines describe the
158 | 0 0 1 0 0 0 0 >= 0 # array size.
159 | 0 -1 0 0 0 0 1335 >= 0
160 | 0 0 -1 0 0 0 123 >= 0
162 The OpenScop access function is printed as follows:
164 | 1 # The number of disjunct components in a union of access functions.
165 | R C O I L P # Described bellow.
169 | 0 0 1 0 -1 -1 0 = 0
170 | 0 1 0 0 0 0 0 >= 0 # The last four lines describe the
171 | 0 0 1 0 0 0 0 >= 0 # array size.
172 | 0 -1 0 0 0 0 1335 >= 0
173 | 0 0 -1 0 0 0 123 >= 0
177 - C: Number of columns.
178 - O: Number of output dimensions = alias set + number of subscripts.
179 - I: Number of input dimensions (iterators).
180 - L: Number of local (existentially quantified) dimensions.
181 - P: Number of parameters.
183 In the example, the vector "R C O I L P" is "7 7 3 2 0 1". */
185 isl_set
*subscript_sizes
;
188 #define PDR_ID(PDR) (PDR->id)
189 #define PDR_NB_REFS(PDR) (PDR->nb_refs)
190 #define PDR_PBB(PDR) (PDR->pbb)
191 #define PDR_TYPE(PDR) (PDR->type)
192 #define PDR_ACCESSES(PDR) (NULL)
194 void new_poly_dr (poly_bb_p
, gimple
*, enum poly_dr_type
,
195 isl_map
*, isl_set
*);
196 void free_poly_dr (poly_dr_p
);
197 void debug_pdr (poly_dr_p
);
198 void print_pdr (FILE *, poly_dr_p
);
201 pdr_read_p (poly_dr_p pdr
)
203 return PDR_TYPE (pdr
) == PDR_READ
;
206 /* Returns true when PDR is a "write". */
209 pdr_write_p (poly_dr_p pdr
)
211 return PDR_TYPE (pdr
) == PDR_WRITE
;
214 /* Returns true when PDR is a "may write". */
217 pdr_may_write_p (poly_dr_p pdr
)
219 return PDR_TYPE (pdr
) == PDR_MAY_WRITE
;
222 /* POLY_BB represents a blackbox in the polyhedral model. */
226 /* Pointer to a basic block or a statement in the compiler. */
227 gimple_poly_bb_p black_box
;
229 /* Pointer to the SCOP containing this PBB. */
232 /* The iteration domain of this bb. The layout of this polyhedron
233 is I|G with I the iteration domain, G the context parameters.
237 for (i = a - 7*b + 8; i <= 3*a + 13*b + 20; i++)
238 for (j = 2; j <= 2*i + 5; j++)
239 for (k = 0; k <= 5; k++)
242 Loop iterators: i, j, k
252 The number of variables in the DOMAIN may change and is not
253 related to the number of loops in the original code. */
256 /* The data references we access. */
259 /* The original scattering. */
262 /* The transformed scattering. */
263 isl_map
*transformed
;
265 /* A copy of the transformed scattering. */
268 /* True when this PBB contains only a reduction statement. */
271 /* The last basic block generated for this pbb. */
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 /* The basic block of the PBB. */
319 static inline basic_block
320 pbb_bb (poly_bb_p pbb
)
322 return GBB_BB (PBB_BLACK_BOX (pbb
));
326 pbb_index (poly_bb_p pbb
)
328 return pbb_bb (pbb
)->index
;
331 /* The loop of the PBB. */
334 pbb_loop (poly_bb_p pbb
)
336 return gbb_loop (PBB_BLACK_BOX (pbb
));
339 /* The scop that contains the PDR. */
342 pdr_scop (poly_dr_p pdr
)
344 return PBB_SCOP (PDR_PBB (pdr
));
347 /* Set black box of PBB to BLACKBOX. */
350 pbb_set_black_box (poly_bb_p pbb
, gimple_poly_bb_p black_box
)
352 pbb
->black_box
= black_box
;
355 /* A helper structure to keep track of data references, polyhedral BBs, and
361 invalid_alias_set
= -1
363 /* The data reference. */
366 /* The polyhedral BB containing this DR. */
369 /* ALIAS_SET is the SCC number assigned by a graph_dfs of the alias graph.
370 -1 is an invalid alias set. */
373 /* Construct a DR_INFO from a data reference DR, an ALIAS_SET, and a PBB. */
374 dr_info (data_reference_p dr
, poly_bb_p pbb
,
375 int alias_set
= invalid_alias_set
)
376 : dr (dr
), pbb (pbb
), alias_set (alias_set
) {}
379 /* A SCOP is a Static Control Part of the program, simple enough to be
380 represented in polyhedral form. */
383 /* A SCOP is defined as a SESE region. */
384 sese_info_p scop_info
;
386 /* Number of parameters in SCoP. */
387 graphite_dim_t nb_params
;
389 /* All the basic blocks in this scop that contain memory references
390 and that will be represented as statements in the polyhedral
394 /* All the data references in this scop. */
397 /* The context describes known restrictions concerning the parameters
398 and relations in between the parameters.
400 void f (int8_t a, uint_16_t b) {
405 Here we can add these restrictions to the context:
410 isl_set
*param_context
;
412 /* The context used internally by ISL. */
413 isl_ctx
*isl_context
;
415 /* SCoP final schedule. */
416 isl_schedule
*schedule
;
418 /* The data dependence relation among the data references in this scop. */
419 isl_union_map
*dependence
;
422 extern scop_p
new_scop (edge
, edge
);
423 extern void free_scop (scop_p
);
424 extern gimple_poly_bb_p
new_gimple_poly_bb (basic_block
, vec
<data_reference_p
>,
425 vec
<scalar_use
>, vec
<tree
>);
426 extern void free_gimple_poly_bb (gimple_poly_bb_p
);
427 extern void print_generated_program (FILE *, scop_p
);
428 extern void debug_generated_program (scop_p
);
429 extern int unify_scattering_dimensions (scop_p
);
430 extern bool apply_poly_transforms (scop_p
);
432 /* Set the region of SCOP to REGION. */
435 scop_set_region (scop_p scop
, sese_info_p region
)
437 scop
->scop_info
= region
;
440 /* Returns the number of parameters for SCOP. */
442 static inline graphite_dim_t
443 scop_nb_params (scop_p scop
)
445 return scop
->nb_params
;
448 /* Set the number of params of SCOP to NB_PARAMS. */
451 scop_set_nb_params (scop_p scop
, graphite_dim_t nb_params
)
453 scop
->nb_params
= nb_params
;
457 scop_get_dependences (scop_p scop
);
460 carries_deps (__isl_keep isl_union_map
*schedule
,
461 __isl_keep isl_union_map
*deps
,
464 extern bool build_poly_scop (scop_p
);
465 extern bool graphite_regenerate_ast_isl (scop_p
);
467 extern void build_scops (vec
<scop_p
> *);
468 extern void dot_all_sese (FILE *, vec
<sese_l
> &);
469 extern void dot_sese (sese_l
&);
470 extern void dot_cfg ();