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
49 limit the expressiveness. */
56 /* An identifier for this PDR. */
59 /* The number of data refs identical to this one in the PBB. */
62 /* A pointer to compiler's data reference description. */
65 /* A pointer to the PBB that contains this data reference. */
68 enum poly_dr_type type
;
70 /* The access polyhedron contains the polyhedral space this data
71 reference will access.
73 The polyhedron contains these dimensions:
76 Every memory access is classified in at least one alias set.
78 - The subscripts (s_0, ..., s_n):
79 The memory is accessed using zero or more subscript dimensions.
81 - The iteration domain (variables and parameters)
83 Do not hardcode the dimensions. Use the following accessor functions:
97 | if (unknown_function ())
104 The data access A[i][j+k] in alias set "5" is described like this:
109 | 0 -1 -1 0 0 1 0 = 0
110 | 0 0 0 0 1 0 0 >= 0 # The last four lines describe the
111 | 0 0 0 0 0 1 0 >= 0 # array size.
112 | 0 0 0 0 -1 0 1335 >= 0
113 | 0 0 0 0 0 -1 123 >= 0
115 The pointer "*p" in alias set "5" and "7" is described as a union of
129 "*p" accesses all of the object allocated with 'malloc'.
131 The scalar data access "m" is represented as an array with zero subscript
136 ppl_Pointset_Powerset_C_Polyhedron_t accesses
;
138 /* Data reference's base object set number, we must assure 2 pdrs are in the
139 same base object set before dependency checking. */
140 int dr_base_object_set
;
142 /* The number of subscripts. */
143 graphite_dim_t nb_subscripts
;
146 #define PDR_ID(PDR) (PDR->id)
147 #define PDR_NB_REFS(PDR) (PDR->nb_refs)
148 #define PDR_CDR(PDR) (PDR->compiler_dr)
149 #define PDR_PBB(PDR) (PDR->pbb)
150 #define PDR_TYPE(PDR) (PDR->type)
151 #define PDR_ACCESSES(PDR) (PDR->accesses)
152 #define PDR_BASE_OBJECT_SET(PDR) (PDR->dr_base_object_set)
153 #define PDR_NB_SUBSCRIPTS(PDR) (PDR->nb_subscripts)
155 void new_poly_dr (poly_bb_p
, int, ppl_Pointset_Powerset_C_Polyhedron_t
,
156 enum poly_dr_type
, void *, graphite_dim_t
);
157 void free_poly_dr (poly_dr_p
);
158 void debug_pdr (poly_dr_p
);
159 void print_pdr (FILE *, poly_dr_p
);
160 static inline scop_p
pdr_scop (poly_dr_p pdr
);
162 /* The dimension of the PDR_ACCESSES polyhedron of PDR. */
164 static inline ppl_dimension_type
165 pdr_dim (poly_dr_p pdr
)
167 ppl_dimension_type dim
;
168 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PDR_ACCESSES (pdr
),
173 /* The dimension of the iteration domain of the scop of PDR. */
175 static inline ppl_dimension_type
176 pdr_dim_iter_domain (poly_dr_p pdr
)
178 return pbb_dim_iter_domain (PDR_PBB (pdr
));
181 /* The number of parameters of the scop of PDR. */
183 static inline ppl_dimension_type
184 pdr_nb_params (poly_dr_p pdr
)
186 return scop_nb_params (pdr_scop (pdr
));
189 /* The dimension of the alias set in PDR. */
191 static inline ppl_dimension_type
192 pdr_alias_set_dim (poly_dr_p pdr
)
194 poly_bb_p pbb
= PDR_PBB (pdr
);
196 return pbb_dim_iter_domain (pbb
) + pbb_nb_params (pbb
);
199 /* The dimension in PDR containing subscript S. */
201 static inline ppl_dimension_type
202 pdr_subscript_dim (poly_dr_p pdr
, graphite_dim_t s
)
204 poly_bb_p pbb
= PDR_PBB (pdr
);
206 return pbb_dim_iter_domain (pbb
) + pbb_nb_params (pbb
) + 1 + s
;
209 /* The dimension in PDR containing the loop iterator ITER. */
211 static inline ppl_dimension_type
212 pdr_iterator_dim (poly_dr_p pdr ATTRIBUTE_UNUSED
, graphite_dim_t iter
)
217 /* The dimension in PDR containing parameter PARAM. */
219 static inline ppl_dimension_type
220 pdr_parameter_dim (poly_dr_p pdr
, graphite_dim_t param
)
222 poly_bb_p pbb
= PDR_PBB (pdr
);
224 return pbb_dim_iter_domain (pbb
) + param
;
227 /* Returns true when PDR is a "read". */
230 pdr_read_p (poly_dr_p pdr
)
232 return PDR_TYPE (pdr
) == PDR_READ
;
235 /* Returns true when PDR is a "write". */
238 pdr_write_p (poly_dr_p pdr
)
240 return PDR_TYPE (pdr
) == PDR_WRITE
;
243 /* Returns true when PDR is a "may write". */
246 pdr_may_write_p (poly_dr_p pdr
)
248 return PDR_TYPE (pdr
) == PDR_MAY_WRITE
;
251 /* Return true when PDR1 and PDR2 are similar data accesses: they have
252 the same base array, and the same access functions. */
255 same_pdr_p (poly_dr_p pdr1
, poly_dr_p pdr2
)
257 return PDR_TYPE (pdr1
) == PDR_TYPE (pdr2
)
258 && PDR_NB_SUBSCRIPTS (pdr1
) == PDR_NB_SUBSCRIPTS (pdr2
)
259 && PDR_BASE_OBJECT_SET (pdr1
) == PDR_BASE_OBJECT_SET (pdr2
);
262 typedef struct poly_scattering
*poly_scattering_p
;
264 struct poly_scattering
266 /* The scattering function containing the transformations: the
267 layout of this polyhedron is: T|I|G with T the transform
268 scattering, I the iteration domain, G the context parameters. */
269 ppl_Polyhedron_t scattering
;
271 /* The number of local variables. */
272 int nb_local_variables
;
274 /* The number of scattering dimensions. */
278 /* POLY_BB represents a blackbox in the polyhedral model. */
282 /* Pointer to a basic block or a statement in the compiler. */
285 /* Pointer to the SCOP containing this PBB. */
288 /* The iteration domain of this bb. The layout of this polyhedron
289 is I|G with I the iteration domain, G the context parameters.
293 for (i = a - 7*b + 8; i <= 3*a + 13*b + 20; i++)
294 for (j = 2; j <= 2*i + 5; j++)
295 for (k = 0; k <= 5; k++)
298 Loop iterators: i, j, k
308 The number of variables in the DOMAIN may change and is not
309 related to the number of loops in the original code. */
310 ppl_Pointset_Powerset_C_Polyhedron_t domain
;
312 /* The data references we access. */
313 VEC (poly_dr_p
, heap
) *drs
;
315 /* The original scattering. */
316 poly_scattering_p original
;
318 /* The transformed scattering. */
319 poly_scattering_p transformed
;
321 /* A copy of the transformed scattering. */
322 poly_scattering_p saved
;
324 /* True when the PDR duplicates have already been removed. */
325 bool pdr_duplicates_removed
;
327 /* True when this PBB contains only a reduction statement. */
331 #define PBB_BLACK_BOX(PBB) ((gimple_bb_p) PBB->black_box)
332 #define PBB_SCOP(PBB) (PBB->scop)
333 #define PBB_DOMAIN(PBB) (PBB->domain)
334 #define PBB_DRS(PBB) (PBB->drs)
335 #define PBB_ORIGINAL(PBB) (PBB->original)
336 #define PBB_ORIGINAL_SCATTERING(PBB) (PBB->original->scattering)
337 #define PBB_TRANSFORMED(PBB) (PBB->transformed)
338 #define PBB_TRANSFORMED_SCATTERING(PBB) (PBB->transformed->scattering)
339 #define PBB_SAVED(PBB) (PBB->saved)
340 #define PBB_NB_LOCAL_VARIABLES(PBB) (PBB->transformed->nb_local_variables)
341 #define PBB_NB_SCATTERING_TRANSFORM(PBB) (PBB->transformed->nb_scattering)
342 #define PBB_PDR_DUPLICATES_REMOVED(PBB) (PBB->pdr_duplicates_removed)
343 #define PBB_IS_REDUCTION(PBB) (PBB->is_reduction)
345 extern void new_poly_bb (scop_p
, void *, bool);
346 extern void free_poly_bb (poly_bb_p
);
347 extern void debug_loop_vec (poly_bb_p
);
348 extern void schedule_to_scattering (poly_bb_p
, int);
349 extern void print_pbb_domain (FILE *, poly_bb_p
);
350 extern void print_pbb (FILE *, poly_bb_p
);
351 extern void print_scop_context (FILE *, scop_p
);
352 extern void print_scop (FILE *, scop_p
);
353 extern void debug_pbb_domain (poly_bb_p
);
354 extern void debug_pbb (poly_bb_p
);
355 extern void print_pdrs (FILE *, poly_bb_p
);
356 extern void debug_pdrs (poly_bb_p
);
357 extern void debug_scop_context (scop_p
);
358 extern void debug_scop (scop_p
);
359 extern void print_scop_params (FILE *, scop_p
);
360 extern void debug_scop_params (scop_p
);
361 extern void print_iteration_domain (FILE *, poly_bb_p
);
362 extern void print_iteration_domains (FILE *, scop_p
);
363 extern void debug_iteration_domain (poly_bb_p
);
364 extern void debug_iteration_domains (scop_p
);
365 extern bool scop_do_interchange (scop_p
);
366 extern bool scop_do_strip_mine (scop_p
);
367 extern bool scop_do_block (scop_p
);
368 extern void pbb_number_of_iterations (poly_bb_p
, graphite_dim_t
, Value
);
369 extern void pbb_number_of_iterations_at_time (poly_bb_p
, graphite_dim_t
, Value
);
370 extern void pbb_remove_duplicate_pdrs (poly_bb_p
);
372 /* Return the number of write data references in PBB. */
375 number_of_write_pdrs (poly_bb_p pbb
)
381 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb
), i
, pdr
); i
++)
382 if (PDR_TYPE (pdr
) == PDR_WRITE
)
388 /* The basic block of the PBB. */
389 static inline basic_block
390 pbb_bb (poly_bb_p pbb
)
392 return GBB_BB (PBB_BLACK_BOX (pbb
));
395 /* The index of the PBB. */
398 pbb_index (poly_bb_p pbb
)
400 return pbb_bb (pbb
)->index
;
403 /* The loop of the PBB. */
406 pbb_loop (poly_bb_p pbb
)
408 return gbb_loop (PBB_BLACK_BOX (pbb
));
411 /* The scop that contains the PDR. */
414 pdr_scop (poly_dr_p pdr
)
416 return PBB_SCOP (PDR_PBB (pdr
));
419 /* Set black box of PBB to BLACKBOX. */
422 pbb_set_black_box (poly_bb_p pbb
, void *black_box
)
424 pbb
->black_box
= black_box
;
427 /* The number of loops around PBB: the dimension of the iteration
430 static inline graphite_dim_t
431 pbb_dim_iter_domain (const struct poly_bb
*pbb
)
433 scop_p scop
= PBB_SCOP (pbb
);
434 ppl_dimension_type dim
;
436 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb
), &dim
);
437 return dim
- scop_nb_params (scop
);
440 /* The number of params defined in PBB. */
442 static inline graphite_dim_t
443 pbb_nb_params (const struct poly_bb
*pbb
)
445 scop_p scop
= PBB_SCOP (pbb
);
447 return scop_nb_params (scop
);
450 /* The number of scattering dimensions in the SCATTERING polyhedron
451 of a PBB for a given SCOP. */
453 static inline graphite_dim_t
454 pbb_nb_scattering_orig (const struct poly_bb
*pbb
)
456 return 2 * pbb_dim_iter_domain (pbb
) + 1;
459 /* The number of scattering dimensions in PBB. */
461 static inline graphite_dim_t
462 pbb_nb_scattering_transform (const struct poly_bb
*pbb
)
464 return PBB_NB_SCATTERING_TRANSFORM (pbb
);
467 /* The number of dynamic scattering dimensions in PBB. */
469 static inline graphite_dim_t
470 pbb_nb_dynamic_scattering_transform (const struct poly_bb
*pbb
)
472 /* This function requires the 2d + 1 scattering format to be
473 invariant during all transformations. */
474 gcc_assert (PBB_NB_SCATTERING_TRANSFORM (pbb
) % 2);
475 return PBB_NB_SCATTERING_TRANSFORM (pbb
) / 2;
478 /* Returns the number of local variables used in the transformed
479 scattering polyhedron of PBB. */
481 static inline graphite_dim_t
482 pbb_nb_local_vars (const struct poly_bb
*pbb
)
484 /* For now we do not have any local variables, as we do not do strip
485 mining for example. */
486 return PBB_NB_LOCAL_VARIABLES (pbb
);
489 /* The dimension in the domain of PBB containing the iterator ITER. */
491 static inline ppl_dimension_type
492 pbb_iterator_dim (poly_bb_p pbb ATTRIBUTE_UNUSED
, graphite_dim_t iter
)
497 /* The dimension in the domain of PBB containing the iterator ITER. */
499 static inline ppl_dimension_type
500 pbb_parameter_dim (poly_bb_p pbb
, graphite_dim_t param
)
503 + pbb_dim_iter_domain (pbb
);
506 /* The dimension in the original scattering polyhedron of PBB
507 containing the scattering iterator SCATTER. */
509 static inline ppl_dimension_type
510 psco_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED
, graphite_dim_t scatter
)
512 gcc_assert (scatter
< pbb_nb_scattering_orig (pbb
));
516 /* The dimension in the transformed scattering polyhedron of PBB
517 containing the scattering iterator SCATTER. */
519 static inline ppl_dimension_type
520 psct_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED
, graphite_dim_t scatter
)
522 gcc_assert (scatter
<= pbb_nb_scattering_transform (pbb
));
526 ppl_dimension_type
psct_scattering_dim_for_loop_depth (poly_bb_p
,
529 /* The dimension in the transformed scattering polyhedron of PBB of
530 the local variable LV. */
532 static inline ppl_dimension_type
533 psct_local_var_dim (poly_bb_p pbb
, graphite_dim_t lv
)
535 gcc_assert (lv
<= pbb_nb_local_vars (pbb
));
536 return lv
+ pbb_nb_scattering_transform (pbb
);
539 /* The dimension in the original scattering polyhedron of PBB
540 containing the loop iterator ITER. */
542 static inline ppl_dimension_type
543 psco_iterator_dim (poly_bb_p pbb
, graphite_dim_t iter
)
545 gcc_assert (iter
< pbb_dim_iter_domain (pbb
));
546 return iter
+ pbb_nb_scattering_orig (pbb
);
549 /* The dimension in the transformed scattering polyhedron of PBB
550 containing the loop iterator ITER. */
552 static inline ppl_dimension_type
553 psct_iterator_dim (poly_bb_p pbb
, graphite_dim_t iter
)
555 gcc_assert (iter
< pbb_dim_iter_domain (pbb
));
557 + pbb_nb_scattering_transform (pbb
)
558 + pbb_nb_local_vars (pbb
);
561 /* The dimension in the original scattering polyhedron of PBB
562 containing parameter PARAM. */
564 static inline ppl_dimension_type
565 psco_parameter_dim (poly_bb_p pbb
, graphite_dim_t param
)
567 gcc_assert (param
< pbb_nb_params (pbb
));
569 + pbb_nb_scattering_orig (pbb
)
570 + pbb_dim_iter_domain (pbb
);
573 /* The dimension in the transformed scattering polyhedron of PBB
574 containing parameter PARAM. */
576 static inline ppl_dimension_type
577 psct_parameter_dim (poly_bb_p pbb
, graphite_dim_t param
)
579 gcc_assert (param
< pbb_nb_params (pbb
));
581 + pbb_nb_scattering_transform (pbb
)
582 + pbb_nb_local_vars (pbb
)
583 + pbb_dim_iter_domain (pbb
);
586 /* The scattering dimension of PBB corresponding to the dynamic level
589 static inline ppl_dimension_type
590 psct_dynamic_dim (poly_bb_p pbb
, graphite_dim_t level
)
592 graphite_dim_t result
= 1 + 2 * level
;
594 gcc_assert (result
< pbb_nb_scattering_transform (pbb
));
598 /* The scattering dimension of PBB corresponding to the static
599 sequence of the loop level LEVEL. */
601 static inline ppl_dimension_type
602 psct_static_dim (poly_bb_p pbb
, graphite_dim_t level
)
604 graphite_dim_t result
= 2 * level
;
606 gcc_assert (result
< pbb_nb_scattering_transform (pbb
));
610 /* Adds to the transformed scattering polyhedron of PBB a new local
611 variable and returns its index. */
613 static inline graphite_dim_t
614 psct_add_local_variable (poly_bb_p pbb
)
616 graphite_dim_t nlv
= pbb_nb_local_vars (pbb
);
617 ppl_dimension_type lv_column
= psct_local_var_dim (pbb
, nlv
);
618 ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb
), lv_column
, 1);
619 PBB_NB_LOCAL_VARIABLES (pbb
) += 1;
623 /* Adds a dimension to the transformed scattering polyhedron of PBB at
627 psct_add_scattering_dimension (poly_bb_p pbb
, ppl_dimension_type index
)
629 gcc_assert (index
< pbb_nb_scattering_transform (pbb
));
631 ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb
), index
, 1);
632 PBB_NB_SCATTERING_TRANSFORM (pbb
) += 1;
635 typedef struct lst
*lst_p
;
637 DEF_VEC_ALLOC_P (lst_p
, heap
);
639 /* Loops and Statements Tree. */
642 /* LOOP_P is true when an LST node is a loop. */
645 /* A pointer to the loop that contains this node. */
648 /* The sum of all the memory strides for an LST loop. */
649 Value memory_strides
;
651 /* Loop nodes contain a sequence SEQ of LST nodes, statements
652 contain a pointer to their polyhedral representation PBB. */
655 VEC (lst_p
, heap
) *seq
;
659 #define LST_LOOP_P(LST) ((LST)->loop_p)
660 #define LST_LOOP_FATHER(LST) ((LST)->loop_father)
661 #define LST_PBB(LST) ((LST)->node.pbb)
662 #define LST_SEQ(LST) ((LST)->node.seq)
663 #define LST_LOOP_MEMORY_STRIDES(LST) ((LST)->memory_strides)
665 void scop_to_lst (scop_p
);
666 void print_lst (FILE *, lst_p
, int);
667 void debug_lst (lst_p
);
668 void dot_lst (lst_p
);
670 /* Creates a new LST loop with SEQ. */
673 new_lst_loop (VEC (lst_p
, heap
) *seq
)
675 lst_p lst
= XNEW (struct lst
);
679 LST_LOOP_P (lst
) = true;
681 LST_LOOP_FATHER (lst
) = NULL
;
682 value_init (LST_LOOP_MEMORY_STRIDES (lst
));
683 value_set_si (LST_LOOP_MEMORY_STRIDES (lst
), -1);
685 for (i
= 0; VEC_iterate (lst_p
, seq
, i
, l
); i
++)
686 LST_LOOP_FATHER (l
) = lst
;
691 /* Creates a new LST statement with PBB. */
694 new_lst_stmt (poly_bb_p pbb
)
696 lst_p lst
= XNEW (struct lst
);
698 LST_LOOP_P (lst
) = false;
700 LST_LOOP_FATHER (lst
) = NULL
;
704 /* Frees the memory used by LST. */
712 if (LST_LOOP_P (lst
))
717 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (lst
), i
, l
); i
++)
720 value_clear (LST_LOOP_MEMORY_STRIDES (lst
));
721 VEC_free (lst_p
, heap
, LST_SEQ (lst
));
727 /* Returns a copy of LST. */
735 if (LST_LOOP_P (lst
))
739 VEC (lst_p
, heap
) *seq
= VEC_alloc (lst_p
, heap
, 5);
741 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (lst
), i
, l
); i
++)
742 VEC_safe_push (lst_p
, heap
, seq
, copy_lst (l
));
744 return new_lst_loop (seq
);
747 return new_lst_stmt (LST_PBB (lst
));
750 /* Adds a new loop under the loop LST. */
753 lst_add_loop_under_loop (lst_p lst
)
755 VEC (lst_p
, heap
) *seq
= VEC_alloc (lst_p
, heap
, 1);
756 lst_p l
= new_lst_loop (LST_SEQ (lst
));
758 gcc_assert (LST_LOOP_P (lst
));
760 LST_LOOP_FATHER (l
) = lst
;
761 VEC_quick_push (lst_p
, seq
, l
);
765 /* Returns the loop depth of LST. */
768 lst_depth (lst_p lst
)
773 /* The depth of the outermost "fake" loop is -1. This outermost
774 loop does not have a loop father and it is just a container, as
775 in the loop representation of GCC. */
776 if (!LST_LOOP_FATHER (lst
))
779 return lst_depth (LST_LOOP_FATHER (lst
)) + 1;
782 /* Returns the Dewey number for LST. */
785 lst_dewey_number (lst_p lst
)
793 if (!LST_LOOP_FATHER (lst
))
796 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (LST_LOOP_FATHER (lst
)), i
, l
); i
++)
803 /* Returns the Dewey number of LST at depth DEPTH. */
806 lst_dewey_number_at_depth (lst_p lst
, int depth
)
808 gcc_assert (lst
&& depth
>= 0 && lst_depth (lst
) <= depth
);
810 if (lst_depth (lst
) == depth
)
811 return lst_dewey_number (lst
);
813 return lst_dewey_number_at_depth (LST_LOOP_FATHER (lst
), depth
);
816 /* Returns the predecessor of LST in the sequence of its loop father.
817 Returns NULL if LST is the first statement in the sequence. */
825 if (!lst
|| !LST_LOOP_FATHER (lst
))
828 dewey
= lst_dewey_number (lst
);
832 father
= LST_LOOP_FATHER (lst
);
833 return VEC_index (lst_p
, LST_SEQ (father
), dewey
- 1);
836 /* Returns the successor of LST in the sequence of its loop father.
837 Returns NULL if there is none. */
845 if (!lst
|| !LST_LOOP_FATHER (lst
))
848 dewey
= lst_dewey_number (lst
);
849 father
= LST_LOOP_FATHER (lst
);
851 if (VEC_length (lst_p
, LST_SEQ (father
)) == (unsigned) dewey
+ 1)
854 return VEC_index (lst_p
, LST_SEQ (father
), dewey
+ 1);
858 /* Return the LST node corresponding to PBB. */
861 lst_find_pbb (lst_p lst
, poly_bb_p pbb
)
869 if (!LST_LOOP_P (lst
))
870 return (pbb
== LST_PBB (lst
)) ? lst
: NULL
;
872 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (lst
), i
, l
); i
++)
874 lst_p res
= lst_find_pbb (l
, pbb
);
882 /* Return the LST node corresponding to the loop around STMT at depth
886 find_lst_loop (lst_p stmt
, int loop_depth
)
888 lst_p loop
= LST_LOOP_FATHER (stmt
);
890 gcc_assert (loop_depth
>= 0);
892 while (loop_depth
< lst_depth (loop
))
893 loop
= LST_LOOP_FATHER (loop
);
898 /* Return the first lst representing a PBB statement in LST. */
901 lst_find_first_pbb (lst_p lst
)
909 if (!LST_LOOP_P (lst
))
912 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (lst
), i
, l
); i
++)
914 lst_p res
= lst_find_first_pbb (l
);
922 /* Returns true when LST is a loop that does not contains
926 lst_empty_p (lst_p lst
)
928 return !lst_find_first_pbb (lst
);
931 /* Return the last lst representing a PBB statement in LST. */
934 lst_find_last_pbb (lst_p lst
)
942 if (!LST_LOOP_P (lst
))
945 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (lst
), i
, l
); i
++)
947 lst_p last
= lst_find_last_pbb (l
);
957 /* Returns true if LOOP contains LST, in other words, if LST is nested
961 lst_contains_p (lst_p loop
, lst_p lst
)
963 if (!loop
|| !lst
|| !LST_LOOP_P (loop
))
969 return lst_contains_p (loop
, LST_LOOP_FATHER (lst
));
972 /* Returns true if LOOP contains PBB, in other words, if PBB is nested
976 lst_contains_pbb (lst_p loop
, poly_bb_p pbb
)
978 return lst_find_pbb (loop
, pbb
) ? true : false;
981 /* Creates a loop nest of depth NB_LOOPS containing LST. */
984 lst_create_nest (int nb_loops
, lst_p lst
)
987 VEC (lst_p
, heap
) *seq
;
992 seq
= VEC_alloc (lst_p
, heap
, 1);
993 loop
= lst_create_nest (nb_loops
- 1, lst
);
994 VEC_quick_push (lst_p
, seq
, loop
);
995 res
= new_lst_loop (seq
);
996 LST_LOOP_FATHER (loop
) = res
;
1001 /* Removes LST from the sequence of statements of its loop father. */
1004 lst_remove_from_sequence (lst_p lst
)
1006 lst_p father
= LST_LOOP_FATHER (lst
);
1007 int dewey
= lst_dewey_number (lst
);
1009 gcc_assert (lst
&& father
&& dewey
>= 0);
1011 VEC_ordered_remove (lst_p
, LST_SEQ (father
), dewey
);
1012 LST_LOOP_FATHER (lst
) = NULL
;
1015 /* Updates the scattering of PBB to be at the DEWEY number in the loop
1019 pbb_update_scattering (poly_bb_p pbb
, graphite_dim_t level
, int dewey
)
1021 ppl_Polyhedron_t ph
= PBB_TRANSFORMED_SCATTERING (pbb
);
1022 ppl_dimension_type sched
= psct_static_dim (pbb
, level
);
1023 ppl_dimension_type ds
[1];
1024 ppl_Constraint_t new_cstr
;
1025 ppl_Linear_Expression_t expr
;
1026 ppl_dimension_type dim
;
1028 ppl_Polyhedron_space_dimension (ph
, &dim
);
1030 ppl_Polyhedron_remove_space_dimensions (ph
, ds
, 1);
1031 ppl_insert_dimensions (ph
, sched
, 1);
1033 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
1034 ppl_set_coef (expr
, sched
, -1);
1035 ppl_set_inhomogeneous (expr
, dewey
);
1036 ppl_new_Constraint (&new_cstr
, expr
, PPL_CONSTRAINT_TYPE_EQUAL
);
1037 ppl_delete_Linear_Expression (expr
);
1038 ppl_Polyhedron_add_constraint (ph
, new_cstr
);
1039 ppl_delete_Constraint (new_cstr
);
1042 /* Updates the scattering of all the PBBs under LST to be at the DEWEY
1043 number in the loop at depth LEVEL. */
1046 lst_update_scattering_under (lst_p lst
, int level
, int dewey
)
1051 gcc_assert (lst
&& level
>= 0 && dewey
>= 0);
1053 if (LST_LOOP_P (lst
))
1054 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (lst
), i
, l
); i
++)
1055 lst_update_scattering_under (l
, level
, dewey
);
1057 pbb_update_scattering (LST_PBB (lst
), level
, dewey
);
1060 /* Updates the scattering of all the PBBs under LST and in sequence
1064 lst_update_scattering_seq (lst_p lst
)
1068 lst_p father
= LST_LOOP_FATHER (lst
);
1069 int dewey
= lst_dewey_number (lst
);
1070 int level
= lst_depth (lst
);
1072 gcc_assert (lst
&& father
&& dewey
>= 0 && level
>= 0);
1074 for (i
= dewey
; VEC_iterate (lst_p
, LST_SEQ (father
), i
, l
); i
++)
1075 lst_update_scattering_under (l
, level
, i
);
1078 /* Updates the all the scattering levels of all the PBBs under
1082 lst_update_scattering (lst_p lst
)
1087 if (!lst
|| !LST_LOOP_P (lst
))
1090 if (LST_LOOP_FATHER (lst
))
1091 lst_update_scattering_seq (lst
);
1093 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (lst
), i
, l
); i
++)
1094 lst_update_scattering (l
);
1097 /* Inserts LST1 before LST2 if BEFORE is true; inserts LST1 after LST2
1098 if BEFORE is false. */
1101 lst_insert_in_sequence (lst_p lst1
, lst_p lst2
, bool before
)
1106 /* Do not insert empty loops. */
1107 if (!lst1
|| lst_empty_p (lst1
))
1110 father
= LST_LOOP_FATHER (lst2
);
1111 dewey
= lst_dewey_number (lst2
);
1113 gcc_assert (lst2
&& father
&& dewey
>= 0);
1115 VEC_safe_insert (lst_p
, heap
, LST_SEQ (father
), before
? dewey
: dewey
+ 1,
1117 LST_LOOP_FATHER (lst1
) = father
;
1120 /* Replaces LST1 with LST2. */
1123 lst_replace (lst_p lst1
, lst_p lst2
)
1128 if (!lst2
|| lst_empty_p (lst2
))
1131 father
= LST_LOOP_FATHER (lst1
);
1132 dewey
= lst_dewey_number (lst1
);
1133 LST_LOOP_FATHER (lst2
) = father
;
1134 VEC_replace (lst_p
, LST_SEQ (father
), dewey
, lst2
);
1137 /* Returns a copy of ROOT where LST has been replaced by a copy of the
1138 LSTs A B C in this sequence. */
1141 lst_substitute_3 (lst_p root
, lst_p lst
, lst_p a
, lst_p b
, lst_p c
)
1145 VEC (lst_p
, heap
) *seq
;
1150 gcc_assert (lst
&& root
!= lst
);
1152 if (!LST_LOOP_P (root
))
1153 return new_lst_stmt (LST_PBB (root
));
1155 seq
= VEC_alloc (lst_p
, heap
, 5);
1157 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (root
), i
, l
); i
++)
1159 VEC_safe_push (lst_p
, heap
, seq
, lst_substitute_3 (l
, lst
, a
, b
, c
));
1162 if (!lst_empty_p (a
))
1163 VEC_safe_push (lst_p
, heap
, seq
, copy_lst (a
));
1164 if (!lst_empty_p (b
))
1165 VEC_safe_push (lst_p
, heap
, seq
, copy_lst (b
));
1166 if (!lst_empty_p (c
))
1167 VEC_safe_push (lst_p
, heap
, seq
, copy_lst (c
));
1170 return new_lst_loop (seq
);
1173 /* Moves LST before LOOP if BEFORE is true, and after the LOOP if
1177 lst_distribute_lst (lst_p loop
, lst_p lst
, bool before
)
1179 int loop_depth
= lst_depth (loop
);
1180 int depth
= lst_depth (lst
);
1181 int nb_loops
= depth
- loop_depth
;
1183 gcc_assert (lst
&& loop
&& LST_LOOP_P (loop
) && nb_loops
> 0);
1185 lst_remove_from_sequence (lst
);
1186 lst_insert_in_sequence (lst_create_nest (nb_loops
, lst
), loop
, before
);
1189 /* Removes from LOOP all the statements before/after and including PBB
1190 if BEFORE is true/false. Returns the negation of BEFORE when the
1191 statement PBB has been found. */
1194 lst_remove_all_before_including_pbb (lst_p loop
, poly_bb_p pbb
, bool before
)
1199 if (!loop
|| !LST_LOOP_P (loop
))
1202 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (loop
), i
, l
);)
1205 before
= lst_remove_all_before_including_pbb (l
, pbb
, before
);
1207 if (VEC_length (lst_p
, LST_SEQ (l
)) == 0)
1209 VEC_ordered_remove (lst_p
, LST_SEQ (loop
), i
);
1219 if (LST_PBB (l
) == pbb
)
1222 VEC_ordered_remove (lst_p
, LST_SEQ (loop
), i
);
1225 else if (LST_PBB (l
) == pbb
)
1228 VEC_ordered_remove (lst_p
, LST_SEQ (loop
), i
);
1238 /* Removes from LOOP all the statements before/after and excluding PBB
1239 if BEFORE is true/false; Returns the negation of BEFORE when the
1240 statement PBB has been found. */
1243 lst_remove_all_before_excluding_pbb (lst_p loop
, poly_bb_p pbb
, bool before
)
1248 if (!loop
|| !LST_LOOP_P (loop
))
1251 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (loop
), i
, l
);)
1254 before
= lst_remove_all_before_excluding_pbb (l
, pbb
, before
);
1256 if (VEC_length (lst_p
, LST_SEQ (l
)) == 0)
1258 VEC_ordered_remove (lst_p
, LST_SEQ (loop
), i
);
1267 if (before
&& LST_PBB (l
) != pbb
)
1269 VEC_ordered_remove (lst_p
, LST_SEQ (loop
), i
);
1276 if (LST_PBB (l
) == pbb
)
1277 before
= before
? false : true;
1283 /* A SCOP is a Static Control Part of the program, simple enough to be
1284 represented in polyhedral form. */
1287 /* A SCOP is defined as a SESE region. */
1290 /* Number of parameters in SCoP. */
1291 graphite_dim_t nb_params
;
1293 /* All the basic blocks in this scop that contain memory references
1294 and that will be represented as statements in the polyhedral
1296 VEC (poly_bb_p
, heap
) *bbs
;
1298 /* Original, transformed and saved schedules. */
1299 lst_p original_schedule
, transformed_schedule
, saved_schedule
;
1301 /* The context describes known restrictions concerning the parameters
1302 and relations in between the parameters.
1304 void f (int8_t a, uint_16_t b) {
1309 Here we can add these restrictions to the context:
1314 ppl_Pointset_Powerset_C_Polyhedron_t context
;
1316 /* A hashtable of the data dependence relations for the original
1318 htab_t original_pddrs
;
1320 /* True when the scop has been converted to its polyhedral
1325 #define SCOP_BBS(S) (S->bbs)
1326 #define SCOP_REGION(S) ((sese) S->region)
1327 #define SCOP_CONTEXT(S) (S->context)
1328 #define SCOP_ORIGINAL_PDDRS(S) (S->original_pddrs)
1329 #define SCOP_ORIGINAL_SCHEDULE(S) (S->original_schedule)
1330 #define SCOP_TRANSFORMED_SCHEDULE(S) (S->transformed_schedule)
1331 #define SCOP_SAVED_SCHEDULE(S) (S->saved_schedule)
1332 #define POLY_SCOP_P(S) (S->poly_scop_p)
1334 extern scop_p
new_scop (void *);
1335 extern void free_scop (scop_p
);
1336 extern void free_scops (VEC (scop_p
, heap
) *);
1337 extern void print_generated_program (FILE *, scop_p
);
1338 extern void debug_generated_program (scop_p
);
1339 extern void print_scattering_function (FILE *, poly_bb_p
);
1340 extern void print_scattering_functions (FILE *, scop_p
);
1341 extern void debug_scattering_function (poly_bb_p
);
1342 extern void debug_scattering_functions (scop_p
);
1343 extern int scop_max_loop_depth (scop_p
);
1344 extern int unify_scattering_dimensions (scop_p
);
1345 extern bool apply_poly_transforms (scop_p
);
1346 extern bool graphite_legal_transform (scop_p
);
1348 /* Set the region of SCOP to REGION. */
1351 scop_set_region (scop_p scop
, void *region
)
1353 scop
->region
= region
;
1356 /* Returns the number of parameters for SCOP. */
1358 static inline graphite_dim_t
1359 scop_nb_params (scop_p scop
)
1361 return scop
->nb_params
;
1364 /* Set the number of params of SCOP to NB_PARAMS. */
1367 scop_set_nb_params (scop_p scop
, graphite_dim_t nb_params
)
1369 scop
->nb_params
= nb_params
;
1372 /* Allocates a new empty poly_scattering structure. */
1374 static inline poly_scattering_p
1375 poly_scattering_new (void)
1377 poly_scattering_p res
= XNEW (struct poly_scattering
);
1379 res
->scattering
= NULL
;
1380 res
->nb_local_variables
= 0;
1381 res
->nb_scattering
= 0;
1385 /* Free a poly_scattering structure. */
1388 poly_scattering_free (poly_scattering_p s
)
1390 ppl_delete_Polyhedron (s
->scattering
);
1394 /* Copies S and return a new scattering. */
1396 static inline poly_scattering_p
1397 poly_scattering_copy (poly_scattering_p s
)
1399 poly_scattering_p res
= poly_scattering_new ();
1401 ppl_new_C_Polyhedron_from_C_Polyhedron (&(res
->scattering
), s
->scattering
);
1402 res
->nb_local_variables
= s
->nb_local_variables
;
1403 res
->nb_scattering
= s
->nb_scattering
;
1407 /* Saves the transformed scattering of PBB. */
1410 store_scattering_pbb (poly_bb_p pbb
)
1412 gcc_assert (PBB_TRANSFORMED (pbb
));
1414 if (PBB_SAVED (pbb
))
1415 poly_scattering_free (PBB_SAVED (pbb
));
1417 PBB_SAVED (pbb
) = poly_scattering_copy (PBB_TRANSFORMED (pbb
));
1420 /* Stores the SCOP_TRANSFORMED_SCHEDULE to SCOP_SAVED_SCHEDULE. */
1423 store_lst_schedule (scop_p scop
)
1425 if (SCOP_SAVED_SCHEDULE (scop
))
1426 free_lst (SCOP_SAVED_SCHEDULE (scop
));
1428 SCOP_SAVED_SCHEDULE (scop
) = copy_lst (SCOP_TRANSFORMED_SCHEDULE (scop
));
1431 /* Restores the SCOP_TRANSFORMED_SCHEDULE from SCOP_SAVED_SCHEDULE. */
1434 restore_lst_schedule (scop_p scop
)
1436 if (SCOP_TRANSFORMED_SCHEDULE (scop
))
1437 free_lst (SCOP_TRANSFORMED_SCHEDULE (scop
));
1439 SCOP_TRANSFORMED_SCHEDULE (scop
) = copy_lst (SCOP_SAVED_SCHEDULE (scop
));
1442 /* Saves the scattering for all the pbbs in the SCOP. */
1445 store_scattering (scop_p scop
)
1450 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1451 store_scattering_pbb (pbb
);
1453 store_lst_schedule (scop
);
1456 /* Restores the scattering of PBB. */
1459 restore_scattering_pbb (poly_bb_p pbb
)
1461 gcc_assert (PBB_SAVED (pbb
));
1463 poly_scattering_free (PBB_TRANSFORMED (pbb
));
1464 PBB_TRANSFORMED (pbb
) = poly_scattering_copy (PBB_SAVED (pbb
));
1467 /* Restores the scattering for all the pbbs in the SCOP. */
1470 restore_scattering (scop_p scop
)
1475 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1476 restore_scattering_pbb (pbb
);
1478 restore_lst_schedule (scop
);
1481 /* For a given PBB, add to RES the scop context, the iteration domain,
1482 the original scattering when ORIGINAL_P is true, otherwise add the
1483 transformed scattering. */
1486 combine_context_id_scat (ppl_Pointset_Powerset_C_Polyhedron_t
*res
,
1487 poly_bb_p pbb
, bool original_p
)
1489 ppl_Pointset_Powerset_C_Polyhedron_t context
;
1490 ppl_Pointset_Powerset_C_Polyhedron_t id
;
1492 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1494 PBB_ORIGINAL_SCATTERING (pbb
) : PBB_TRANSFORMED_SCATTERING (pbb
));
1496 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1497 (&context
, SCOP_CONTEXT (PBB_SCOP (pbb
)));
1499 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1500 (&id
, PBB_DOMAIN (pbb
));
1502 /* Extend the context and the iteration domain to the dimension of
1503 the scattering: T|I|G. */
1505 ppl_dimension_type gdim
, tdim
, idim
;
1507 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (*res
, &tdim
);
1508 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (context
, &gdim
);
1509 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (id
, &idim
);
1512 ppl_insert_dimensions_pointset (context
, 0, tdim
- gdim
);
1515 ppl_insert_dimensions_pointset (id
, 0, tdim
- idim
);
1518 /* Add the context and the iteration domain to the result. */
1519 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (*res
, context
);
1520 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (*res
, id
);
1522 ppl_delete_Pointset_Powerset_C_Polyhedron (context
);
1523 ppl_delete_Pointset_Powerset_C_Polyhedron (id
);