1 /* Graphite polyhedral representation.
2 Copyright (C) 2009-2016 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/options.h>
28 #include <isl/val_gmp.h>
30 #include <isl/union_set.h>
32 #include <isl/union_map.h>
34 #include <isl/constraint.h>
37 #include <isl/schedule.h>
38 #include <isl/ast_build.h>
40 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
41 /* isl 0.15 or later. */
42 #include <isl/schedule_node.h>
45 /* isl 0.14 or 0.13. */
47 # define isl_stat_ok 0
50 typedef struct poly_dr
*poly_dr_p
;
52 typedef struct poly_bb
*poly_bb_p
;
54 typedef struct scop
*scop_p
;
56 typedef unsigned graphite_dim_t
;
58 static inline graphite_dim_t
scop_nb_params (scop_p
);
60 /* A data reference can write or read some memory or we
61 just know it may write some memory. */
65 /* PDR_MAY_READs are represented using PDR_READS. This does not
66 limit the expressiveness. */
73 /* An identifier for this PDR. */
76 /* The number of data refs identical to this one in the PBB. */
79 /* A pointer to the gimple stmt containing this reference. */
82 /* A pointer to the PBB that contains this data reference. */
85 enum poly_dr_type type
;
87 /* The access polyhedron contains the polyhedral space this data
88 reference will access.
90 The polyhedron contains these dimensions:
93 Every memory access is classified in at least one alias set.
95 - The subscripts (s_0, ..., s_n):
96 The memory is accessed using zero or more subscript dimensions.
98 - The iteration domain (variables and parameters)
100 Do not hardcode the dimensions. Use the following accessor functions:
109 | int *p = malloc ();
114 | if (unknown_function ())
121 The data access A[i][j+k] in alias set "5" is described like this:
126 | 0 -1 -1 0 0 1 0 = 0
127 | 0 0 0 0 1 0 0 >= 0 # The last four lines describe the
128 | 0 0 0 0 0 1 0 >= 0 # array size.
129 | 0 0 0 0 -1 0 1335 >= 0
130 | 0 0 0 0 0 -1 123 >= 0
132 The pointer "*p" in alias set "5" and "7" is described as a union of
146 "*p" accesses all of the object allocated with 'malloc'.
148 The scalar data access "m" is represented as an array with zero subscript
154 The difference between the graphite internal format for access data and
155 the OpenSop format is in the order of columns.
161 | 0 -1 -1 0 0 1 0 = 0
162 | 0 0 0 0 1 0 0 >= 0 # The last four lines describe the
163 | 0 0 0 0 0 1 0 >= 0 # array size.
164 | 0 0 0 0 -1 0 1335 >= 0
165 | 0 0 0 0 0 -1 123 >= 0
172 | 0 0 1 0 -1 -1 0 = 0
173 | 0 1 0 0 0 0 0 >= 0 # The last four lines describe the
174 | 0 0 1 0 0 0 0 >= 0 # array size.
175 | 0 -1 0 0 0 0 1335 >= 0
176 | 0 0 -1 0 0 0 123 >= 0
178 The OpenScop access function is printed as follows:
180 | 1 # The number of disjunct components in a union of access functions.
181 | R C O I L P # Described bellow.
185 | 0 0 1 0 -1 -1 0 = 0
186 | 0 1 0 0 0 0 0 >= 0 # The last four lines describe the
187 | 0 0 1 0 0 0 0 >= 0 # array size.
188 | 0 -1 0 0 0 0 1335 >= 0
189 | 0 0 -1 0 0 0 123 >= 0
193 - C: Number of columns.
194 - O: Number of output dimensions = alias set + number of subscripts.
195 - I: Number of input dimensions (iterators).
196 - L: Number of local (existentially quantified) dimensions.
197 - P: Number of parameters.
199 In the example, the vector "R C O I L P" is "7 7 3 2 0 1". */
201 isl_set
*subscript_sizes
;
204 #define PDR_ID(PDR) (PDR->id)
205 #define PDR_NB_REFS(PDR) (PDR->nb_refs)
206 #define PDR_PBB(PDR) (PDR->pbb)
207 #define PDR_TYPE(PDR) (PDR->type)
208 #define PDR_ACCESSES(PDR) (NULL)
210 void new_poly_dr (poly_bb_p
, gimple
*, enum poly_dr_type
,
211 isl_map
*, isl_set
*);
212 void free_poly_dr (poly_dr_p
);
213 void debug_pdr (poly_dr_p
);
214 void print_pdr (FILE *, poly_dr_p
);
217 pdr_read_p (poly_dr_p pdr
)
219 return PDR_TYPE (pdr
) == PDR_READ
;
222 /* Returns true when PDR is a "write". */
225 pdr_write_p (poly_dr_p pdr
)
227 return PDR_TYPE (pdr
) == PDR_WRITE
;
230 /* Returns true when PDR is a "may write". */
233 pdr_may_write_p (poly_dr_p pdr
)
235 return PDR_TYPE (pdr
) == PDR_MAY_WRITE
;
238 /* POLY_BB represents a blackbox in the polyhedral model. */
242 /* Pointer to a basic block or a statement in the compiler. */
243 gimple_poly_bb_p black_box
;
245 /* Pointer to the SCOP containing this PBB. */
248 /* The iteration domain of this bb. The layout of this polyhedron
249 is I|G with I the iteration domain, G the context parameters.
253 for (i = a - 7*b + 8; i <= 3*a + 13*b + 20; i++)
254 for (j = 2; j <= 2*i + 5; j++)
255 for (k = 0; k <= 5; k++)
258 Loop iterators: i, j, k
268 The number of variables in the DOMAIN may change and is not
269 related to the number of loops in the original code. */
272 /* The data references we access. */
275 /* The original scattering. */
278 /* The transformed scattering. */
279 isl_map
*transformed
;
281 /* A copy of the transformed scattering. */
284 /* The last basic block generated for this pbb. */
288 #define PBB_BLACK_BOX(PBB) ((gimple_poly_bb_p) PBB->black_box)
289 #define PBB_SCOP(PBB) (PBB->scop)
290 #define PBB_DRS(PBB) (PBB->drs)
292 extern poly_bb_p
new_poly_bb (scop_p
, gimple_poly_bb_p
);
293 extern void free_poly_bb (poly_bb_p
);
294 extern void debug_loop_vec (poly_bb_p
);
295 extern void print_pbb_domain (FILE *, poly_bb_p
);
296 extern void print_pbb (FILE *, poly_bb_p
);
297 extern void print_scop_context (FILE *, scop_p
);
298 extern void print_scop (FILE *, scop_p
);
299 extern void debug_pbb_domain (poly_bb_p
);
300 extern void debug_pbb (poly_bb_p
);
301 extern void print_pdrs (FILE *, poly_bb_p
);
302 extern void debug_pdrs (poly_bb_p
);
303 extern void debug_scop_context (scop_p
);
304 extern void debug_scop (scop_p
);
305 extern void print_scop_params (FILE *, scop_p
);
306 extern void debug_scop_params (scop_p
);
307 extern void print_iteration_domain (FILE *, poly_bb_p
);
308 extern void print_iteration_domains (FILE *, scop_p
);
309 extern void debug_iteration_domain (poly_bb_p
);
310 extern void debug_iteration_domains (scop_p
);
311 extern void print_isl_set (FILE *, isl_set
*);
312 extern void print_isl_map (FILE *, isl_map
*);
313 extern void print_isl_union_map (FILE *, isl_union_map
*);
314 extern void print_isl_aff (FILE *, isl_aff
*);
315 extern void print_isl_constraint (FILE *, isl_constraint
*);
316 extern void debug_isl_set (isl_set
*);
317 extern void debug_isl_map (isl_map
*);
318 extern void debug_isl_union_map (isl_union_map
*);
319 extern void debug_isl_aff (isl_aff
*);
320 extern void debug_isl_constraint (isl_constraint
*);
321 extern int scop_do_interchange (scop_p
);
322 extern int scop_do_strip_mine (scop_p
, int);
323 extern bool scop_do_block (scop_p
);
324 extern bool flatten_all_loops (scop_p
);
325 extern bool optimize_isl (scop_p
);
326 extern void pbb_number_of_iterations_at_time (poly_bb_p
, graphite_dim_t
, mpz_t
);
327 extern void debug_gmp_value (mpz_t
);
329 /* The basic block of the PBB. */
331 static inline basic_block
332 pbb_bb (poly_bb_p pbb
)
334 return GBB_BB (PBB_BLACK_BOX (pbb
));
338 pbb_index (poly_bb_p pbb
)
340 return pbb_bb (pbb
)->index
;
343 /* The loop of the PBB. */
346 pbb_loop (poly_bb_p pbb
)
348 return gbb_loop (PBB_BLACK_BOX (pbb
));
351 /* The scop that contains the PDR. */
354 pdr_scop (poly_dr_p pdr
)
356 return PBB_SCOP (PDR_PBB (pdr
));
359 /* Set black box of PBB to BLACKBOX. */
362 pbb_set_black_box (poly_bb_p pbb
, gimple_poly_bb_p black_box
)
364 pbb
->black_box
= black_box
;
367 /* A helper structure to keep track of data references, polyhedral BBs, and
373 invalid_alias_set
= -1
375 /* The data reference. */
378 /* The polyhedral BB containing this DR. */
381 /* ALIAS_SET is the SCC number assigned by a graph_dfs of the alias graph.
382 -1 is an invalid alias set. */
385 /* Construct a DR_INFO from a data reference DR, an ALIAS_SET, and a PBB. */
386 dr_info (data_reference_p dr
, poly_bb_p pbb
,
387 int alias_set
= invalid_alias_set
)
388 : dr (dr
), pbb (pbb
), alias_set (alias_set
) {}
391 /* A SCOP is a Static Control Part of the program, simple enough to be
392 represented in polyhedral form. */
395 /* A SCOP is defined as a SESE region. */
396 sese_info_p scop_info
;
398 /* Number of parameters in SCoP. */
399 graphite_dim_t nb_params
;
401 /* All the basic blocks in this scop that contain memory references
402 and that will be represented as statements in the polyhedral
406 /* All the data references in this scop. */
409 /* The context describes known restrictions concerning the parameters
410 and relations in between the parameters.
412 void f (int8_t a, uint_16_t b) {
417 Here we can add these restrictions to the context:
422 isl_set
*param_context
;
424 /* The context used internally by isl. */
425 isl_ctx
*isl_context
;
427 /* SCoP final schedule. */
428 isl_schedule
*schedule
;
430 /* The data dependence relation among the data references in this scop. */
431 isl_union_map
*dependence
;
434 extern scop_p
new_scop (edge
, edge
);
435 extern void free_scop (scop_p
);
436 extern gimple_poly_bb_p
new_gimple_poly_bb (basic_block
, vec
<data_reference_p
>,
437 vec
<scalar_use
>, vec
<tree
>);
438 extern void free_gimple_poly_bb (gimple_poly_bb_p
);
439 extern void print_generated_program (FILE *, scop_p
);
440 extern void debug_generated_program (scop_p
);
441 extern int unify_scattering_dimensions (scop_p
);
442 extern bool apply_poly_transforms (scop_p
);
444 /* Set the region of SCOP to REGION. */
447 scop_set_region (scop_p scop
, sese_info_p region
)
449 scop
->scop_info
= region
;
452 /* Returns the number of parameters for SCOP. */
454 static inline graphite_dim_t
455 scop_nb_params (scop_p scop
)
457 return scop
->nb_params
;
460 /* Set the number of params of SCOP to NB_PARAMS. */
463 scop_set_nb_params (scop_p scop
, graphite_dim_t nb_params
)
465 scop
->nb_params
= nb_params
;
469 scop_get_dependences (scop_p scop
);
472 carries_deps (__isl_keep isl_union_map
*schedule
,
473 __isl_keep isl_union_map
*deps
,
476 extern bool build_poly_scop (scop_p
);
477 extern bool graphite_regenerate_ast_isl (scop_p
);
479 extern void build_scops (vec
<scop_p
> *);
480 extern void dot_all_sese (FILE *, vec
<sese_l
> &);
481 extern void dot_sese (sese_l
&);
482 extern void dot_cfg ();