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. */
267 ppl_Polyhedron_t scattering
;
269 /* The number of local variables. */
270 int nb_local_variables
;
272 /* The number of scattering dimensions. */
276 /* POLY_BB represents a blackbox in the polyhedral model. */
284 /* The iteration domain of this bb.
287 for (i = a - 7*b + 8; i <= 3*a + 13*b + 20; i++)
288 for (j = 2; j <= 2*i + 5; j++)
289 for (k = 0; k <= 5; k++)
292 Loop iterators: i, j, k
302 The number of variables in the DOMAIN may change and is not
303 related to the number of loops in the original code. */
304 ppl_Pointset_Powerset_C_Polyhedron_t domain
;
306 /* The data references we access. */
307 VEC (poly_dr_p
, heap
) *drs
;
309 /* The original scattering. */
310 poly_scattering_p original
;
312 /* The transformed scattering. */
313 poly_scattering_p transformed
;
315 /* A copy of the transformed scattering. */
316 poly_scattering_p saved
;
318 /* True when the PDR duplicates have already been removed. */
319 bool pdr_duplicates_removed
;
321 /* True when this PBB contains only a reduction statement. */
325 #define PBB_BLACK_BOX(PBB) ((gimple_bb_p) PBB->black_box)
326 #define PBB_SCOP(PBB) (PBB->scop)
327 #define PBB_DOMAIN(PBB) (PBB->domain)
328 #define PBB_DRS(PBB) (PBB->drs)
329 #define PBB_ORIGINAL(PBB) (PBB->original)
330 #define PBB_ORIGINAL_SCATTERING(PBB) (PBB->original->scattering)
331 #define PBB_TRANSFORMED(PBB) (PBB->transformed)
332 #define PBB_TRANSFORMED_SCATTERING(PBB) (PBB->transformed->scattering)
333 #define PBB_SAVED(PBB) (PBB->saved)
334 #define PBB_NB_LOCAL_VARIABLES(PBB) (PBB->transformed->nb_local_variables)
335 #define PBB_NB_SCATTERING_TRANSFORM(PBB) (PBB->transformed->nb_scattering)
336 #define PBB_PDR_DUPLICATES_REMOVED(PBB) (PBB->pdr_duplicates_removed)
337 #define PBB_IS_REDUCTION(PBB) (PBB->is_reduction)
339 extern void new_poly_bb (scop_p
, void *, bool);
340 extern void free_poly_bb (poly_bb_p
);
341 extern void debug_loop_vec (poly_bb_p
);
342 extern void schedule_to_scattering (poly_bb_p
, int);
343 extern void print_pbb_domain (FILE *, poly_bb_p
);
344 extern void print_pbb (FILE *, poly_bb_p
);
345 extern void print_scop_context (FILE *, scop_p
);
346 extern void print_scop (FILE *, scop_p
);
347 extern void debug_pbb_domain (poly_bb_p
);
348 extern void debug_pbb (poly_bb_p
);
349 extern void print_pdrs (FILE *, poly_bb_p
);
350 extern void debug_pdrs (poly_bb_p
);
351 extern void debug_scop_context (scop_p
);
352 extern void debug_scop (scop_p
);
353 extern void print_scop_params (FILE *, scop_p
);
354 extern void debug_scop_params (scop_p
);
355 extern void print_iteration_domain (FILE *, poly_bb_p
);
356 extern void print_iteration_domains (FILE *, scop_p
);
357 extern void debug_iteration_domain (poly_bb_p
);
358 extern void debug_iteration_domains (scop_p
);
359 extern bool scop_do_interchange (scop_p
);
360 extern bool scop_do_strip_mine (scop_p
);
361 extern bool scop_do_block (scop_p
);
362 extern void pbb_number_of_iterations (poly_bb_p
, graphite_dim_t
, Value
);
363 extern void pbb_number_of_iterations_at_time (poly_bb_p
, graphite_dim_t
, Value
);
364 extern void pbb_remove_duplicate_pdrs (poly_bb_p
);
366 /* Return the number of write data references in PBB. */
369 number_of_write_pdrs (poly_bb_p pbb
)
375 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb
), i
, pdr
); i
++)
376 if (PDR_TYPE (pdr
) == PDR_WRITE
)
382 /* The index of the PBB. */
385 pbb_index (poly_bb_p pbb
)
387 return GBB_BB (PBB_BLACK_BOX (pbb
))->index
;
390 /* The loop of the PBB. */
393 pbb_loop (poly_bb_p pbb
)
395 return gbb_loop (PBB_BLACK_BOX (pbb
));
398 /* The scop that contains the PDR. */
401 pdr_scop (poly_dr_p pdr
)
403 return PBB_SCOP (PDR_PBB (pdr
));
406 /* Set black box of PBB to BLACKBOX. */
409 pbb_set_black_box (poly_bb_p pbb
, void *black_box
)
411 pbb
->black_box
= black_box
;
414 /* The number of loops around PBB: the dimension of the iteration
417 static inline graphite_dim_t
418 pbb_dim_iter_domain (const struct poly_bb
*pbb
)
420 scop_p scop
= PBB_SCOP (pbb
);
421 ppl_dimension_type dim
;
423 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb
), &dim
);
424 return dim
- scop_nb_params (scop
);
427 /* The number of params defined in PBB. */
429 static inline graphite_dim_t
430 pbb_nb_params (const struct poly_bb
*pbb
)
432 scop_p scop
= PBB_SCOP (pbb
);
434 return scop_nb_params (scop
);
437 /* The number of scattering dimensions in the SCATTERING polyhedron
438 of a PBB for a given SCOP. */
440 static inline graphite_dim_t
441 pbb_nb_scattering_orig (const struct poly_bb
*pbb
)
443 return 2 * pbb_dim_iter_domain (pbb
) + 1;
446 /* The number of scattering dimensions in PBB. */
448 static inline graphite_dim_t
449 pbb_nb_scattering_transform (const struct poly_bb
*pbb
)
451 return PBB_NB_SCATTERING_TRANSFORM (pbb
);
454 /* The number of dynamic scattering dimensions in PBB. */
456 static inline graphite_dim_t
457 pbb_nb_dynamic_scattering_transform (const struct poly_bb
*pbb
)
459 /* This function requires the 2d + 1 scattering format to be
460 invariant during all transformations. */
461 gcc_assert (PBB_NB_SCATTERING_TRANSFORM (pbb
) % 2);
462 return PBB_NB_SCATTERING_TRANSFORM (pbb
) / 2;
465 /* Returns the number of local variables used in the transformed
466 scattering polyhedron of PBB. */
468 static inline graphite_dim_t
469 pbb_nb_local_vars (const struct poly_bb
*pbb
)
471 /* For now we do not have any local variables, as we do not do strip
472 mining for example. */
473 return PBB_NB_LOCAL_VARIABLES (pbb
);
476 /* The dimension in the domain of PBB containing the iterator ITER. */
478 static inline ppl_dimension_type
479 pbb_iterator_dim (poly_bb_p pbb ATTRIBUTE_UNUSED
, graphite_dim_t iter
)
484 /* The dimension in the domain of PBB containing the iterator ITER. */
486 static inline ppl_dimension_type
487 pbb_parameter_dim (poly_bb_p pbb
, graphite_dim_t param
)
490 + pbb_dim_iter_domain (pbb
);
493 /* The dimension in the original scattering polyhedron of PBB
494 containing the scattering iterator SCATTER. */
496 static inline ppl_dimension_type
497 psco_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED
, graphite_dim_t scatter
)
499 gcc_assert (scatter
< pbb_nb_scattering_orig (pbb
));
503 /* The dimension in the transformed scattering polyhedron of PBB
504 containing the scattering iterator SCATTER. */
506 static inline ppl_dimension_type
507 psct_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED
, graphite_dim_t scatter
)
509 gcc_assert (scatter
<= pbb_nb_scattering_transform (pbb
));
513 ppl_dimension_type
psct_scattering_dim_for_loop_depth (poly_bb_p
,
516 /* The dimension in the transformed scattering polyhedron of PBB of
517 the local variable LV. */
519 static inline ppl_dimension_type
520 psct_local_var_dim (poly_bb_p pbb
, graphite_dim_t lv
)
522 gcc_assert (lv
<= pbb_nb_local_vars (pbb
));
523 return lv
+ pbb_nb_scattering_transform (pbb
);
526 /* The dimension in the original scattering polyhedron of PBB
527 containing the loop iterator ITER. */
529 static inline ppl_dimension_type
530 psco_iterator_dim (poly_bb_p pbb
, graphite_dim_t iter
)
532 gcc_assert (iter
< pbb_dim_iter_domain (pbb
));
533 return iter
+ pbb_nb_scattering_orig (pbb
);
536 /* The dimension in the transformed scattering polyhedron of PBB
537 containing the loop iterator ITER. */
539 static inline ppl_dimension_type
540 psct_iterator_dim (poly_bb_p pbb
, graphite_dim_t iter
)
542 gcc_assert (iter
< pbb_dim_iter_domain (pbb
));
544 + pbb_nb_scattering_transform (pbb
)
545 + pbb_nb_local_vars (pbb
);
548 /* The dimension in the original scattering polyhedron of PBB
549 containing parameter PARAM. */
551 static inline ppl_dimension_type
552 psco_parameter_dim (poly_bb_p pbb
, graphite_dim_t param
)
554 gcc_assert (param
< pbb_nb_params (pbb
));
556 + pbb_nb_scattering_orig (pbb
)
557 + pbb_dim_iter_domain (pbb
);
560 /* The dimension in the transformed scattering polyhedron of PBB
561 containing parameter PARAM. */
563 static inline ppl_dimension_type
564 psct_parameter_dim (poly_bb_p pbb
, graphite_dim_t param
)
566 gcc_assert (param
< pbb_nb_params (pbb
));
568 + pbb_nb_scattering_transform (pbb
)
569 + pbb_nb_local_vars (pbb
)
570 + pbb_dim_iter_domain (pbb
);
573 /* The scattering dimension of PBB corresponding to the dynamic level
576 static inline ppl_dimension_type
577 psct_dynamic_dim (poly_bb_p pbb
, graphite_dim_t level
)
579 graphite_dim_t result
= 1 + 2 * level
;
581 gcc_assert (result
< pbb_nb_scattering_transform (pbb
));
585 /* The scattering dimension of PBB corresponding to the static
586 sequence of the loop level LEVEL. */
588 static inline ppl_dimension_type
589 psct_static_dim (poly_bb_p pbb
, graphite_dim_t level
)
591 graphite_dim_t result
= 2 * level
;
593 gcc_assert (result
< pbb_nb_scattering_transform (pbb
));
597 /* Adds to the transformed scattering polyhedron of PBB a new local
598 variable and returns its index. */
600 static inline graphite_dim_t
601 psct_add_local_variable (poly_bb_p pbb
)
603 graphite_dim_t nlv
= pbb_nb_local_vars (pbb
);
604 ppl_dimension_type lv_column
= psct_local_var_dim (pbb
, nlv
);
605 ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb
), lv_column
, 1);
606 PBB_NB_LOCAL_VARIABLES (pbb
) += 1;
610 /* Adds a dimension to the transformed scattering polyhedron of PBB at
614 psct_add_scattering_dimension (poly_bb_p pbb
, ppl_dimension_type index
)
616 gcc_assert (index
< pbb_nb_scattering_transform (pbb
));
618 ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb
), index
, 1);
619 PBB_NB_SCATTERING_TRANSFORM (pbb
) += 1;
622 typedef struct lst
*lst_p
;
624 DEF_VEC_ALLOC_P (lst_p
, heap
);
626 /* Loops and Statements Tree. */
629 /* LOOP_P is true when an LST node is a loop. */
632 /* A pointer to the loop that contains this node. */
635 /* Loop nodes contain a sequence SEQ of LST nodes, statements
636 contain a pointer to their polyhedral representation PBB. */
639 VEC (lst_p
, heap
) *seq
;
643 #define LST_LOOP_P(LST) ((LST)->loop_p)
644 #define LST_LOOP_FATHER(LST) ((LST)->loop_father)
645 #define LST_PBB(LST) ((LST)->node.pbb)
646 #define LST_SEQ(LST) ((LST)->node.seq)
648 void scop_to_lst (scop_p
);
649 void print_lst (FILE *, lst_p
, int);
650 void debug_lst (lst_p
);
651 void dot_lst (lst_p
);
653 /* Creates a new LST loop with SEQ. */
656 new_lst_loop (VEC (lst_p
, heap
) *seq
)
658 lst_p lst
= XNEW (struct lst
);
662 LST_LOOP_P (lst
) = true;
664 LST_LOOP_FATHER (lst
) = NULL
;
666 for (i
= 0; VEC_iterate (lst_p
, seq
, i
, l
); i
++)
667 LST_LOOP_FATHER (l
) = lst
;
672 /* Creates a new LST statement with PBB. */
675 new_lst_stmt (poly_bb_p pbb
)
677 lst_p lst
= XNEW (struct lst
);
679 LST_LOOP_P (lst
) = false;
681 LST_LOOP_FATHER (lst
) = NULL
;
685 /* Frees the memory used by LST. */
693 if (LST_LOOP_P (lst
))
698 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (lst
), i
, l
); i
++)
701 VEC_free (lst_p
, heap
, LST_SEQ (lst
));
707 /* Returns a copy of LST. */
715 if (LST_LOOP_P (lst
))
719 VEC (lst_p
, heap
) *seq
= VEC_alloc (lst_p
, heap
, 5);
721 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (lst
), i
, l
); i
++)
722 VEC_safe_push (lst_p
, heap
, seq
, copy_lst (l
));
724 return new_lst_loop (seq
);
727 return new_lst_stmt (LST_PBB (lst
));
730 /* Adds a new loop under the loop LST. */
733 lst_add_loop_under_loop (lst_p lst
)
735 VEC (lst_p
, heap
) *seq
= VEC_alloc (lst_p
, heap
, 1);
736 lst_p l
= new_lst_loop (LST_SEQ (lst
));
738 gcc_assert (LST_LOOP_P (lst
));
740 LST_LOOP_FATHER (l
) = lst
;
741 VEC_quick_push (lst_p
, seq
, l
);
745 /* Returns the loop depth of LST. */
748 lst_depth (lst_p lst
)
753 /* The depth of the outermost "fake" loop is -1. This outermost
754 loop does not have a loop father and it is just a container, as
755 in the loop representation of GCC. */
756 if (!LST_LOOP_FATHER (lst
))
759 return lst_depth (LST_LOOP_FATHER (lst
)) + 1;
762 /* Returns the Dewey number for LST. */
765 lst_dewey_number (lst_p lst
)
773 if (!LST_LOOP_FATHER (lst
))
776 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (LST_LOOP_FATHER (lst
)), i
, l
); i
++)
783 /* Returns the Dewey number of LST at depth DEPTH. */
786 lst_dewey_number_at_depth (lst_p lst
, int depth
)
788 gcc_assert (lst
&& depth
>= 0 && lst_depth (lst
) <= depth
);
790 if (lst_depth (lst
) == depth
)
791 return lst_dewey_number (lst
);
793 return lst_dewey_number_at_depth (LST_LOOP_FATHER (lst
), depth
);
796 /* Returns the predecessor of LST in the sequence of its loop father.
797 Returns NULL if LST is the first statement in the sequence. */
805 if (!lst
|| !LST_LOOP_FATHER (lst
))
808 dewey
= lst_dewey_number (lst
);
812 father
= LST_LOOP_FATHER (lst
);
813 return VEC_index (lst_p
, LST_SEQ (father
), dewey
- 1);
816 /* Returns the successor of LST in the sequence of its loop father.
817 Returns NULL if there is none. */
825 if (!lst
|| !LST_LOOP_FATHER (lst
))
828 dewey
= lst_dewey_number (lst
);
829 father
= LST_LOOP_FATHER (lst
);
831 if (VEC_length (lst_p
, LST_SEQ (father
)) == (unsigned) dewey
+ 1)
834 return VEC_index (lst_p
, LST_SEQ (father
), dewey
+ 1);
838 /* Return the LST node corresponding to PBB. */
841 lst_find_pbb (lst_p lst
, poly_bb_p pbb
)
849 if (!LST_LOOP_P (lst
))
850 return (pbb
== LST_PBB (lst
)) ? lst
: NULL
;
852 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (lst
), i
, l
); i
++)
854 lst_p res
= lst_find_pbb (l
, pbb
);
862 /* Return the LST node corresponding to the loop around STMT at depth
866 find_lst_loop (lst_p stmt
, int loop_depth
)
868 lst_p loop
= LST_LOOP_FATHER (stmt
);
870 gcc_assert (loop_depth
>= 0);
872 while (loop_depth
< lst_depth (loop
))
873 loop
= LST_LOOP_FATHER (loop
);
878 /* Return the first lst representing a PBB statement in LST. */
881 lst_find_first_pbb (lst_p lst
)
889 if (!LST_LOOP_P (lst
))
892 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (lst
), i
, l
); i
++)
894 lst_p res
= lst_find_first_pbb (l
);
902 /* Returns true when LST is a loop that does not contains
906 lst_empty_p (lst_p lst
)
908 return !lst_find_first_pbb (lst
);
911 /* Return the last lst representing a PBB statement in LST. */
914 lst_find_last_pbb (lst_p lst
)
922 if (!LST_LOOP_P (lst
))
925 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (lst
), i
, l
); i
++)
927 lst_p last
= lst_find_last_pbb (l
);
937 /* Returns true if LOOP contains LST, in other words, if LST is nested
941 lst_contains_p (lst_p loop
, lst_p lst
)
943 if (!loop
|| !lst
|| !LST_LOOP_P (loop
))
949 return lst_contains_p (loop
, LST_LOOP_FATHER (lst
));
952 /* Returns true if LOOP contains PBB, in other words, if PBB is nested
956 lst_contains_pbb (lst_p loop
, poly_bb_p pbb
)
958 return lst_find_pbb (loop
, pbb
) ? true : false;
961 /* Creates a loop nest of depth NB_LOOPS containing LST. */
964 lst_create_nest (int nb_loops
, lst_p lst
)
967 VEC (lst_p
, heap
) *seq
;
972 seq
= VEC_alloc (lst_p
, heap
, 1);
973 loop
= lst_create_nest (nb_loops
- 1, lst
);
974 VEC_quick_push (lst_p
, seq
, loop
);
975 res
= new_lst_loop (seq
);
976 LST_LOOP_FATHER (loop
) = res
;
981 /* Removes LST from the sequence of statements of its loop father. */
984 lst_remove_from_sequence (lst_p lst
)
986 lst_p father
= LST_LOOP_FATHER (lst
);
987 int dewey
= lst_dewey_number (lst
);
989 gcc_assert (lst
&& father
&& dewey
>= 0);
991 VEC_ordered_remove (lst_p
, LST_SEQ (father
), dewey
);
992 LST_LOOP_FATHER (lst
) = NULL
;
995 /* Updates the scattering of PBB to be at the DEWEY number in the loop
999 pbb_update_scattering (poly_bb_p pbb
, graphite_dim_t level
, int dewey
)
1001 ppl_Polyhedron_t ph
= PBB_TRANSFORMED_SCATTERING (pbb
);
1002 ppl_dimension_type sched
= psct_static_dim (pbb
, level
);
1003 ppl_dimension_type ds
[1];
1004 ppl_Constraint_t new_cstr
;
1005 ppl_Linear_Expression_t expr
;
1006 ppl_dimension_type dim
;
1008 ppl_Polyhedron_space_dimension (ph
, &dim
);
1010 ppl_Polyhedron_remove_space_dimensions (ph
, ds
, 1);
1011 ppl_insert_dimensions (ph
, sched
, 1);
1013 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
1014 ppl_set_coef (expr
, sched
, -1);
1015 ppl_set_inhomogeneous (expr
, dewey
);
1016 ppl_new_Constraint (&new_cstr
, expr
, PPL_CONSTRAINT_TYPE_EQUAL
);
1017 ppl_delete_Linear_Expression (expr
);
1018 ppl_Polyhedron_add_constraint (ph
, new_cstr
);
1019 ppl_delete_Constraint (new_cstr
);
1022 /* Updates the scattering of all the PBBs under LST to be at the DEWEY
1023 number in the loop at depth LEVEL. */
1026 lst_update_scattering_under (lst_p lst
, int level
, int dewey
)
1031 gcc_assert (lst
&& level
>= 0 && dewey
>= 0);
1033 if (LST_LOOP_P (lst
))
1034 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (lst
), i
, l
); i
++)
1035 lst_update_scattering_under (l
, level
, dewey
);
1037 pbb_update_scattering (LST_PBB (lst
), level
, dewey
);
1040 /* Updates the scattering of all the PBBs under LST and in sequence
1044 lst_update_scattering_seq (lst_p lst
)
1048 lst_p father
= LST_LOOP_FATHER (lst
);
1049 int dewey
= lst_dewey_number (lst
);
1050 int level
= lst_depth (lst
);
1052 gcc_assert (lst
&& father
&& dewey
>= 0 && level
>= 0);
1054 for (i
= dewey
; VEC_iterate (lst_p
, LST_SEQ (father
), i
, l
); i
++)
1055 lst_update_scattering_under (l
, level
, i
);
1058 /* Updates the all the scattering levels of all the PBBs under
1062 lst_update_scattering (lst_p lst
)
1067 if (!lst
|| !LST_LOOP_P (lst
))
1070 if (LST_LOOP_FATHER (lst
))
1071 lst_update_scattering_seq (lst
);
1073 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (lst
), i
, l
); i
++)
1074 lst_update_scattering (l
);
1077 /* Inserts LST1 before LST2 if BEFORE is true; inserts LST1 after LST2
1078 if BEFORE is false. */
1081 lst_insert_in_sequence (lst_p lst1
, lst_p lst2
, bool before
)
1086 /* Do not insert empty loops. */
1087 if (!lst1
|| lst_empty_p (lst1
))
1090 father
= LST_LOOP_FATHER (lst2
);
1091 dewey
= lst_dewey_number (lst2
);
1093 gcc_assert (lst2
&& father
&& dewey
>= 0);
1095 VEC_safe_insert (lst_p
, heap
, LST_SEQ (father
), before
? dewey
: dewey
+ 1,
1097 LST_LOOP_FATHER (lst1
) = father
;
1100 /* Replaces LST1 with LST2. */
1103 lst_replace (lst_p lst1
, lst_p lst2
)
1108 if (!lst2
|| lst_empty_p (lst2
))
1111 father
= LST_LOOP_FATHER (lst1
);
1112 dewey
= lst_dewey_number (lst1
);
1113 LST_LOOP_FATHER (lst2
) = father
;
1114 VEC_replace (lst_p
, LST_SEQ (father
), dewey
, lst2
);
1117 /* Returns a copy of ROOT where LST has been replaced by a copy of the
1118 LSTs A B C in this sequence. */
1121 lst_substitute_3 (lst_p root
, lst_p lst
, lst_p a
, lst_p b
, lst_p c
)
1125 VEC (lst_p
, heap
) *seq
;
1130 gcc_assert (lst
&& root
!= lst
);
1132 if (!LST_LOOP_P (root
))
1133 return new_lst_stmt (LST_PBB (root
));
1135 seq
= VEC_alloc (lst_p
, heap
, 5);
1137 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (root
), i
, l
); i
++)
1139 VEC_safe_push (lst_p
, heap
, seq
, lst_substitute_3 (l
, lst
, a
, b
, c
));
1142 if (!lst_empty_p (a
))
1143 VEC_safe_push (lst_p
, heap
, seq
, copy_lst (a
));
1144 if (!lst_empty_p (b
))
1145 VEC_safe_push (lst_p
, heap
, seq
, copy_lst (b
));
1146 if (!lst_empty_p (c
))
1147 VEC_safe_push (lst_p
, heap
, seq
, copy_lst (c
));
1150 return new_lst_loop (seq
);
1153 /* Moves LST before LOOP if BEFORE is true, and after the LOOP if
1157 lst_distribute_lst (lst_p loop
, lst_p lst
, bool before
)
1159 int loop_depth
= lst_depth (loop
);
1160 int depth
= lst_depth (lst
);
1161 int nb_loops
= depth
- loop_depth
;
1163 gcc_assert (lst
&& loop
&& LST_LOOP_P (loop
) && nb_loops
> 0);
1165 lst_remove_from_sequence (lst
);
1166 lst_insert_in_sequence (lst_create_nest (nb_loops
, lst
), loop
, before
);
1169 /* Removes from LOOP all the statements before/after and including PBB
1170 if BEFORE is true/false. Returns the negation of BEFORE when the
1171 statement PBB has been found. */
1174 lst_remove_all_before_including_pbb (lst_p loop
, poly_bb_p pbb
, bool before
)
1179 if (!loop
|| !LST_LOOP_P (loop
))
1182 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (loop
), i
, l
);)
1185 before
= lst_remove_all_before_including_pbb (l
, pbb
, before
);
1187 if (VEC_length (lst_p
, LST_SEQ (l
)) == 0)
1189 VEC_ordered_remove (lst_p
, LST_SEQ (loop
), i
);
1199 if (LST_PBB (l
) == pbb
)
1202 VEC_ordered_remove (lst_p
, LST_SEQ (loop
), i
);
1205 else if (LST_PBB (l
) == pbb
)
1208 VEC_ordered_remove (lst_p
, LST_SEQ (loop
), i
);
1218 /* Removes from LOOP all the statements before/after and excluding PBB
1219 if BEFORE is true/false; Returns the negation of BEFORE when the
1220 statement PBB has been found. */
1223 lst_remove_all_before_excluding_pbb (lst_p loop
, poly_bb_p pbb
, bool before
)
1228 if (!loop
|| !LST_LOOP_P (loop
))
1231 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (loop
), i
, l
);)
1234 before
= lst_remove_all_before_excluding_pbb (l
, pbb
, before
);
1236 if (VEC_length (lst_p
, LST_SEQ (l
)) == 0)
1238 VEC_ordered_remove (lst_p
, LST_SEQ (loop
), i
);
1247 if (before
&& LST_PBB (l
) != pbb
)
1249 VEC_ordered_remove (lst_p
, LST_SEQ (loop
), i
);
1256 if (LST_PBB (l
) == pbb
)
1257 before
= before
? false : true;
1263 /* A SCOP is a Static Control Part of the program, simple enough to be
1264 represented in polyhedral form. */
1267 /* A SCOP is defined as a SESE region. */
1270 /* Number of parameters in SCoP. */
1271 graphite_dim_t nb_params
;
1273 /* All the basic blocks in this scop that contain memory references
1274 and that will be represented as statements in the polyhedral
1276 VEC (poly_bb_p
, heap
) *bbs
;
1278 /* Original, transformed and saved schedules. */
1279 lst_p original_schedule
, transformed_schedule
, saved_schedule
;
1281 /* The context describes known restrictions concerning the parameters
1282 and relations in between the parameters.
1284 void f (int8_t a, uint_16_t b) {
1289 Here we can add these restrictions to the context:
1294 ppl_Pointset_Powerset_C_Polyhedron_t context
;
1296 /* A hashtable of the data dependence relations for the original
1298 htab_t original_pddrs
;
1301 #define SCOP_BBS(S) (S->bbs)
1302 #define SCOP_REGION(S) ((sese) S->region)
1303 #define SCOP_CONTEXT(S) (S->context)
1304 #define SCOP_ORIGINAL_PDDRS(S) (S->original_pddrs)
1305 #define SCOP_ORIGINAL_SCHEDULE(S) (S->original_schedule)
1306 #define SCOP_TRANSFORMED_SCHEDULE(S) (S->transformed_schedule)
1307 #define SCOP_SAVED_SCHEDULE(S) (S->saved_schedule)
1309 extern scop_p
new_scop (void *);
1310 extern void free_scop (scop_p
);
1311 extern void free_scops (VEC (scop_p
, heap
) *);
1312 extern void print_generated_program (FILE *, scop_p
);
1313 extern void debug_generated_program (scop_p
);
1314 extern void print_scattering_function (FILE *, poly_bb_p
);
1315 extern void print_scattering_functions (FILE *, scop_p
);
1316 extern void debug_scattering_function (poly_bb_p
);
1317 extern void debug_scattering_functions (scop_p
);
1318 extern int scop_max_loop_depth (scop_p
);
1319 extern int unify_scattering_dimensions (scop_p
);
1320 extern bool apply_poly_transforms (scop_p
);
1321 extern bool graphite_legal_transform (scop_p
);
1323 /* Set the region of SCOP to REGION. */
1326 scop_set_region (scop_p scop
, void *region
)
1328 scop
->region
= region
;
1331 /* Returns the number of parameters for SCOP. */
1333 static inline graphite_dim_t
1334 scop_nb_params (scop_p scop
)
1336 return scop
->nb_params
;
1339 /* Set the number of params of SCOP to NB_PARAMS. */
1342 scop_set_nb_params (scop_p scop
, graphite_dim_t nb_params
)
1344 scop
->nb_params
= nb_params
;
1347 /* Allocates a new empty poly_scattering structure. */
1349 static inline poly_scattering_p
1350 poly_scattering_new (void)
1352 poly_scattering_p res
= XNEW (struct poly_scattering
);
1354 res
->scattering
= NULL
;
1355 res
->nb_local_variables
= 0;
1356 res
->nb_scattering
= 0;
1360 /* Free a poly_scattering structure. */
1363 poly_scattering_free (poly_scattering_p s
)
1365 ppl_delete_Polyhedron (s
->scattering
);
1369 /* Copies S and return a new scattering. */
1371 static inline poly_scattering_p
1372 poly_scattering_copy (poly_scattering_p s
)
1374 poly_scattering_p res
= poly_scattering_new ();
1376 ppl_new_C_Polyhedron_from_C_Polyhedron (&(res
->scattering
), s
->scattering
);
1377 res
->nb_local_variables
= s
->nb_local_variables
;
1378 res
->nb_scattering
= s
->nb_scattering
;
1382 /* Saves the transformed scattering of PBB. */
1385 store_scattering_pbb (poly_bb_p pbb
)
1387 gcc_assert (PBB_TRANSFORMED (pbb
));
1389 if (PBB_SAVED (pbb
))
1390 poly_scattering_free (PBB_SAVED (pbb
));
1392 PBB_SAVED (pbb
) = poly_scattering_copy (PBB_TRANSFORMED (pbb
));
1395 /* Stores the SCOP_TRANSFORMED_SCHEDULE to SCOP_SAVED_SCHEDULE. */
1398 store_lst_schedule (scop_p scop
)
1400 if (SCOP_SAVED_SCHEDULE (scop
))
1401 free_lst (SCOP_SAVED_SCHEDULE (scop
));
1403 SCOP_SAVED_SCHEDULE (scop
) = copy_lst (SCOP_TRANSFORMED_SCHEDULE (scop
));
1406 /* Restores the SCOP_TRANSFORMED_SCHEDULE from SCOP_SAVED_SCHEDULE. */
1409 restore_lst_schedule (scop_p scop
)
1411 if (SCOP_TRANSFORMED_SCHEDULE (scop
))
1412 free_lst (SCOP_TRANSFORMED_SCHEDULE (scop
));
1414 SCOP_TRANSFORMED_SCHEDULE (scop
) = copy_lst (SCOP_SAVED_SCHEDULE (scop
));
1417 /* Saves the scattering for all the pbbs in the SCOP. */
1420 store_scattering (scop_p scop
)
1425 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1426 store_scattering_pbb (pbb
);
1428 store_lst_schedule (scop
);
1431 /* Restores the scattering of PBB. */
1434 restore_scattering_pbb (poly_bb_p pbb
)
1436 gcc_assert (PBB_SAVED (pbb
));
1438 poly_scattering_free (PBB_TRANSFORMED (pbb
));
1439 PBB_TRANSFORMED (pbb
) = poly_scattering_copy (PBB_SAVED (pbb
));
1442 /* Restores the scattering for all the pbbs in the SCOP. */
1445 restore_scattering (scop_p scop
)
1450 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1451 restore_scattering_pbb (pbb
);
1453 restore_lst_schedule (scop
);