1 /* Graphite polyhedral representation.
2 Copyright (C) 2009 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
25 typedef struct poly_dr
*poly_dr_p
;
27 DEF_VEC_ALLOC_P (poly_dr_p
, heap
);
29 typedef struct poly_bb
*poly_bb_p
;
31 DEF_VEC_ALLOC_P (poly_bb_p
, heap
);
33 typedef struct scop
*scop_p
;
35 DEF_VEC_ALLOC_P (scop_p
, heap
);
37 typedef ppl_dimension_type graphite_dim_t
;
39 static inline graphite_dim_t
pbb_dim_iter_domain (const struct poly_bb
*);
40 static inline graphite_dim_t
pbb_nb_params (const struct poly_bb
*);
41 static inline graphite_dim_t
scop_nb_params (scop_p
);
43 /* A data reference can write or read some memory or we
44 just know it may write some memory. */
48 /* PDR_MAY_READs are represented using PDR_READS. This does not limit the
56 /* A pointer to compiler's data reference description. */
59 /* A pointer to the PBB that contains this data reference. */
62 enum POLY_DR_TYPE type
;
64 /* The access polyhedron contains the polyhedral space this data
65 reference will access.
67 The polyhedron contains these dimensions:
70 Every memory access is classified in at least one alias set.
72 - The subscripts (s_0, ..., s_n):
73 The memory is accessed using zero or more subscript dimensions.
75 - The iteration domain (variables and parameters)
77 Do not hardcode the dimensions. Use the following accessor functions:
91 | if (unknown_function ())
98 The data access A[i][j+k] in alias set "5" is described like this:
103 | 0 -1 -1 0 0 1 0 = 0
104 | 0 0 0 0 1 0 0 >= 0 # The last four lines describe the
105 | 0 0 0 0 0 1 0 >= 0 # array size.
106 | 0 0 0 0 -1 0 1335 >= 0
107 | 0 0 0 0 0 -1 123 >= 0
109 The pointer "*p" in alias set "5" and "7" is described as a union of
123 "*p" accesses all of the object allocated with 'malloc'.
125 The scalar data access "m" is represented as an array with zero subscript
130 ppl_Pointset_Powerset_C_Polyhedron_t accesses
;
132 /* The number of subscripts. */
133 graphite_dim_t nb_subscripts
;
136 #define PDR_CDR(PDR) (PDR->compiler_dr)
137 #define PDR_PBB(PDR) (PDR->pbb)
138 #define PDR_TYPE(PDR) (PDR->type)
139 #define PDR_ACCESSES(PDR) (PDR->accesses)
140 #define PDR_NB_SUBSCRIPTS(PDR) (PDR->nb_subscripts)
142 void new_poly_dr (poly_bb_p
, ppl_Pointset_Powerset_C_Polyhedron_t
,
143 enum POLY_DR_TYPE
, void *, int);
144 void free_poly_dr (poly_dr_p
);
145 void debug_pdr (poly_dr_p
);
146 void print_pdr (FILE *, poly_dr_p
);
147 static inline scop_p
pdr_scop (poly_dr_p pdr
);
149 /* The dimension of the PDR_ACCESSES polyhedron of PDR. */
151 static inline ppl_dimension_type
152 pdr_dim (poly_dr_p pdr
)
154 ppl_dimension_type dim
;
155 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PDR_ACCESSES (pdr
),
160 /* The dimension of the iteration domain of the scop of PDR. */
162 static inline ppl_dimension_type
163 pdr_dim_iter_domain (poly_dr_p pdr
)
165 return pbb_dim_iter_domain (PDR_PBB (pdr
));
168 /* The number of parameters of the scop of PDR. */
170 static inline ppl_dimension_type
171 pdr_nb_params (poly_dr_p pdr
)
173 return scop_nb_params (pdr_scop (pdr
));
176 /* The dimension of the alias set in PDR. */
178 static inline ppl_dimension_type
179 pdr_alias_set_dim (poly_dr_p pdr
)
181 poly_bb_p pbb
= PDR_PBB (pdr
);
183 return pbb_dim_iter_domain (pbb
) + pbb_nb_params (pbb
);
186 /* The dimension in PDR containing subscript S. */
188 static inline ppl_dimension_type
189 pdr_subscript_dim (poly_dr_p pdr
, graphite_dim_t s
)
191 poly_bb_p pbb
= PDR_PBB (pdr
);
193 return pbb_dim_iter_domain (pbb
) + pbb_nb_params (pbb
) + 1 + s
;
196 /* The dimension in PDR containing the loop iterator ITER. */
198 static inline ppl_dimension_type
199 pdr_iterator_dim (poly_dr_p pdr ATTRIBUTE_UNUSED
, graphite_dim_t iter
)
204 /* The dimension in PDR containing parameter PARAM. */
206 static inline ppl_dimension_type
207 pdr_parameter_dim (poly_dr_p pdr
, graphite_dim_t param
)
209 poly_bb_p pbb
= PDR_PBB (pdr
);
211 return pbb_dim_iter_domain (pbb
) + param
;
214 typedef struct poly_scattering
*poly_scattering_p
;
216 struct poly_scattering
218 /* The scattering function containing the transformations. */
219 ppl_Polyhedron_t scattering
;
221 /* The number of local variables. */
222 int nb_local_variables
;
224 /* The number of scattering dimensions. */
228 /* POLY_BB represents a blackbox in the polyhedral model. */
236 /* The iteration domain of this bb.
239 for (i = a - 7*b + 8; i <= 3*a + 13*b + 20; i++)
240 for (j = 2; j <= 2*i + 5; j++)
241 for (k = 0; k <= 5; k++)
244 Loop iterators: i, j, k
254 The number of variables in the DOMAIN may change and is not
255 related to the number of loops in the original code. */
256 ppl_Pointset_Powerset_C_Polyhedron_t domain
;
258 /* The data references we access. */
259 VEC (poly_dr_p
, heap
) *drs
;
261 /* The original scattering. */
262 poly_scattering_p original
;
264 /* The transformed scattering. */
265 poly_scattering_p transformed
;
267 /* A copy of the transformed scattering. */
268 poly_scattering_p saved
;
271 #define PBB_BLACK_BOX(PBB) ((gimple_bb_p) PBB->black_box)
272 #define PBB_SCOP(PBB) (PBB->scop)
273 #define PBB_DOMAIN(PBB) (PBB->domain)
274 #define PBB_DRS(PBB) (PBB->drs)
275 #define PBB_ORIGINAL(PBB) (PBB->original)
276 #define PBB_ORIGINAL_SCATTERING(PBB) (PBB->original->scattering)
277 #define PBB_TRANSFORMED(PBB) (PBB->transformed)
278 #define PBB_TRANSFORMED_SCATTERING(PBB) (PBB->transformed->scattering)
279 #define PBB_SAVED(PBB) (PBB->saved)
280 #define PBB_NB_LOCAL_VARIABLES(PBB) (PBB->transformed->nb_local_variables)
281 #define PBB_NB_SCATTERING_TRANSFORM(PBB) (PBB->transformed->nb_scattering)
283 extern void new_poly_bb (scop_p
, void *);
284 extern void free_poly_bb (poly_bb_p
);
285 extern void debug_loop_vec (poly_bb_p
);
286 extern void schedule_to_scattering (poly_bb_p
, int);
287 extern void print_pbb_domain (FILE *, poly_bb_p
);
288 extern void print_pbb (FILE *, poly_bb_p
);
289 extern void print_scop_context (FILE *, scop_p
);
290 extern void print_scop (FILE *, scop_p
);
291 extern void debug_pbb_domain (poly_bb_p
);
292 extern void debug_pbb (poly_bb_p
);
293 extern void print_pdrs (FILE *, poly_bb_p
);
294 extern void debug_pdrs (poly_bb_p
);
295 extern void debug_scop_context (scop_p
);
296 extern void debug_scop (scop_p
);
297 extern void print_scop_params (FILE *, scop_p
);
298 extern void debug_scop_params (scop_p
);
299 extern void print_iteration_domain (FILE *, poly_bb_p
);
300 extern void print_iteration_domains (FILE *, scop_p
);
301 extern void debug_iteration_domain (poly_bb_p
);
302 extern void debug_iteration_domains (scop_p
);
303 extern bool scop_do_interchange (scop_p
);
304 extern bool scop_do_strip_mine (scop_p
);
305 extern void pbb_number_of_iterations (poly_bb_p
, graphite_dim_t
, Value
);
307 /* The scop that contains the PDR. */
309 static inline scop_p
pdr_scop (poly_dr_p pdr
)
311 return PBB_SCOP (PDR_PBB (pdr
));
314 /* Set black box of PBB to BLACKBOX. */
317 pbb_set_black_box (poly_bb_p pbb
, void *black_box
)
319 pbb
->black_box
= black_box
;
322 /* The number of loops around PBB: the dimension of the iteration
325 static inline graphite_dim_t
326 pbb_dim_iter_domain (const struct poly_bb
*pbb
)
328 scop_p scop
= PBB_SCOP (pbb
);
329 ppl_dimension_type dim
;
331 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb
), &dim
);
332 return dim
- scop_nb_params (scop
);
335 /* The number of params defined in PBB. */
337 static inline graphite_dim_t
338 pbb_nb_params (const struct poly_bb
*pbb
)
340 scop_p scop
= PBB_SCOP (pbb
);
342 return scop_nb_params (scop
);
345 /* The number of scattering dimensions in the SCATTERING polyhedron
346 of a PBB for a given SCOP. */
348 static inline graphite_dim_t
349 pbb_nb_scattering_orig (const struct poly_bb
*pbb
)
351 return 2 * pbb_dim_iter_domain (pbb
) + 1;
354 /* The number of scattering dimensions in PBB. */
356 static inline graphite_dim_t
357 pbb_nb_scattering_transform (const struct poly_bb
*pbb
)
359 return PBB_NB_SCATTERING_TRANSFORM (pbb
);
362 /* Returns the number of local variables used in the transformed
363 scattering polyhedron of PBB. */
365 static inline graphite_dim_t
366 pbb_nb_local_vars (const struct poly_bb
*pbb
)
368 /* For now we do not have any local variables, as we do not do strip
369 mining for example. */
370 return PBB_NB_LOCAL_VARIABLES (pbb
);
373 /* The dimension in the domain of PBB containing the iterator ITER. */
375 static inline ppl_dimension_type
376 pbb_iterator_dim (poly_bb_p pbb ATTRIBUTE_UNUSED
, graphite_dim_t iter
)
381 /* The dimension in the domain of PBB containing the iterator ITER. */
383 static inline ppl_dimension_type
384 pbb_parameter_dim (poly_bb_p pbb
, graphite_dim_t param
)
387 + pbb_dim_iter_domain (pbb
);
390 /* The dimension in the original scattering polyhedron of PBB
391 containing the scattering iterator SCATTER. */
393 static inline ppl_dimension_type
394 psco_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED
, graphite_dim_t scatter
)
396 gcc_assert (scatter
< pbb_nb_scattering_orig (pbb
));
400 /* The dimension in the transformed scattering polyhedron of PBB
401 containing the scattering iterator SCATTER. */
403 static inline ppl_dimension_type
404 psct_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED
, graphite_dim_t scatter
)
406 gcc_assert (scatter
<= pbb_nb_scattering_transform (pbb
));
410 ppl_dimension_type
psct_scattering_dim_for_loop_depth (poly_bb_p
,
413 /* The dimension in the transformed scattering polyhedron of PBB of
414 the local variable LV. */
416 static inline ppl_dimension_type
417 psct_local_var_dim (poly_bb_p pbb
, graphite_dim_t lv
)
419 gcc_assert (lv
<= pbb_nb_local_vars (pbb
));
420 return lv
+ pbb_nb_scattering_transform (pbb
);
423 /* The dimension in the original scattering polyhedron of PBB
424 containing the loop iterator ITER. */
426 static inline ppl_dimension_type
427 psco_iterator_dim (poly_bb_p pbb
, graphite_dim_t iter
)
429 gcc_assert (iter
< pbb_dim_iter_domain (pbb
));
430 return iter
+ pbb_nb_scattering_orig (pbb
);
433 /* The dimension in the transformed scattering polyhedron of PBB
434 containing the loop iterator ITER. */
436 static inline ppl_dimension_type
437 psct_iterator_dim (poly_bb_p pbb
, graphite_dim_t iter
)
439 gcc_assert (iter
< pbb_dim_iter_domain (pbb
));
441 + pbb_nb_scattering_transform (pbb
)
442 + pbb_nb_local_vars (pbb
);
445 /* The dimension in the original scattering polyhedron of PBB
446 containing parameter PARAM. */
448 static inline ppl_dimension_type
449 psco_parameter_dim (poly_bb_p pbb
, graphite_dim_t param
)
451 gcc_assert (param
< pbb_nb_params (pbb
));
453 + pbb_nb_scattering_orig (pbb
)
454 + pbb_dim_iter_domain (pbb
);
457 /* The dimension in the transformed scattering polyhedron of PBB
458 containing parameter PARAM. */
460 static inline ppl_dimension_type
461 psct_parameter_dim (poly_bb_p pbb
, graphite_dim_t param
)
463 gcc_assert (param
< pbb_nb_params (pbb
));
465 + pbb_nb_scattering_transform (pbb
)
466 + pbb_nb_local_vars (pbb
)
467 + pbb_dim_iter_domain (pbb
);
470 /* Adds to the transformed scattering polyhedron of PBB a new local
471 variable and returns its index. */
473 static inline graphite_dim_t
474 psct_add_local_variable (poly_bb_p pbb
)
476 graphite_dim_t nlv
= pbb_nb_local_vars (pbb
);
477 ppl_dimension_type lv_column
= psct_local_var_dim (pbb
, nlv
);
478 ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb
), lv_column
, 1);
479 PBB_NB_LOCAL_VARIABLES (pbb
) += 1;
483 /* Adds a dimension to the transformed scattering polyhedron of PBB at
487 psct_add_scattering_dimension (poly_bb_p pbb
, ppl_dimension_type index
)
489 gcc_assert (index
< pbb_nb_scattering_transform (pbb
));
491 ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb
), index
, 1);
492 PBB_NB_SCATTERING_TRANSFORM (pbb
) += 1;
495 /* A SCOP is a Static Control Part of the program, simple enough to be
496 represented in polyhedral form. */
499 /* A SCOP is defined as a SESE region. */
502 /* Number of parameters in SCoP. */
503 graphite_dim_t nb_params
;
505 /* All the basic blocks in this scop that contain memory references
506 and that will be represented as statements in the polyhedral
508 VEC (poly_bb_p
, heap
) *bbs
;
510 /* Data dependence graph for this SCoP. */
511 struct graph
*dep_graph
;
513 /* The context describes known restrictions concerning the parameters
514 and relations in between the parameters.
516 void f (int8_t a, uint_16_t b) {
521 Here we can add these restrictions to the context:
526 ppl_Pointset_Powerset_C_Polyhedron_t context
;
528 /* A hashtable of the original pairs of dependent data references.
529 For each pair of dependent data references, the dependence
530 polyhedron is stored also. */
531 htab_t original_pdr_pairs
;
534 #define SCOP_BBS(S) (S->bbs)
535 #define SCOP_REGION(S) ((sese) S->region)
536 #define SCOP_DEP_GRAPH(S) (S->dep_graph)
537 #define SCOP_CONTEXT(S) (S->context)
538 #define SCOP_ORIGINAL_PDR_PAIRS(S) (S->original_pdr_pairs)
540 extern scop_p
new_scop (void *);
541 extern void free_scop (scop_p
);
542 extern void free_scops (VEC (scop_p
, heap
) *);
543 extern void print_generated_program (FILE *, scop_p
);
544 extern void debug_generated_program (scop_p
);
545 extern void print_scattering_function (FILE *, poly_bb_p
);
546 extern void print_scattering_functions (FILE *, scop_p
);
547 extern void debug_scattering_function (poly_bb_p
);
548 extern void debug_scattering_functions (scop_p
);
549 extern int scop_max_loop_depth (scop_p
);
550 extern int unify_scattering_dimensions (scop_p
);
551 extern bool apply_poly_transforms (scop_p
);
552 extern bool graphite_legal_transform (scop_p
);
554 /* Set the region of SCOP to REGION. */
557 scop_set_region (scop_p scop
, void *region
)
559 scop
->region
= region
;
562 /* Returns the number of parameters for SCOP. */
564 static inline graphite_dim_t
565 scop_nb_params (scop_p scop
)
567 return scop
->nb_params
;
570 /* Set the number of params of SCOP to NB_PARAMS. */
573 scop_set_nb_params (scop_p scop
, graphite_dim_t nb_params
)
575 scop
->nb_params
= nb_params
;
578 /* Allocates a new empty poly_scattering structure. */
580 static inline poly_scattering_p
581 poly_scattering_new (void)
583 poly_scattering_p res
= XNEW (struct poly_scattering
);
585 res
->scattering
= NULL
;
586 res
->nb_local_variables
= 0;
587 res
->nb_scattering
= 0;
591 /* Free a poly_scattering structure. */
594 poly_scattering_free (poly_scattering_p s
)
596 ppl_delete_Polyhedron (s
->scattering
);
600 /* Copies S and return a new scattering. */
602 static inline poly_scattering_p
603 poly_scattering_copy (poly_scattering_p s
)
605 poly_scattering_p res
= poly_scattering_new ();
607 ppl_new_C_Polyhedron_from_C_Polyhedron (&(res
->scattering
), s
->scattering
);
608 res
->nb_local_variables
= s
->nb_local_variables
;
609 res
->nb_scattering
= s
->nb_scattering
;
613 /* Saves the transformed scattering of PBB. */
616 store_scattering_pbb (poly_bb_p pbb
)
618 gcc_assert (PBB_TRANSFORMED (pbb
));
621 poly_scattering_free (PBB_SAVED (pbb
));
623 PBB_SAVED (pbb
) = poly_scattering_copy (PBB_TRANSFORMED (pbb
));
626 /* Saves the scattering for all the pbbs in the SCOP. */
629 store_scattering (scop_p scop
)
634 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
635 store_scattering_pbb (pbb
);
638 /* Restores the scattering of PBB. */
641 restore_scattering_pbb (poly_bb_p pbb
)
643 gcc_assert (PBB_SAVED (pbb
));
645 poly_scattering_free (PBB_TRANSFORMED (pbb
));
646 PBB_TRANSFORMED (pbb
) = poly_scattering_copy (PBB_SAVED (pbb
));
649 /* Restores the scattering for all the pbbs in the SCOP. */
652 restore_scattering (scop_p scop
)
657 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
658 restore_scattering_pbb (pbb
);