1 /* Graphite polyhedral representation.
2 Copyright (C) 2009, 2010 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
137 The difference between the graphite internal format for access data and
138 the OpenSop format is in the order of columns.
144 | 0 -1 -1 0 0 1 0 = 0
145 | 0 0 0 0 1 0 0 >= 0 # The last four lines describe the
146 | 0 0 0 0 0 1 0 >= 0 # array size.
147 | 0 0 0 0 -1 0 1335 >= 0
148 | 0 0 0 0 0 -1 123 >= 0
155 | 0 0 1 0 -1 -1 0 = 0
156 | 0 1 0 0 0 0 0 >= 0 # The last four lines describe the
157 | 0 0 1 0 0 0 0 >= 0 # array size.
158 | 0 -1 0 0 0 0 1335 >= 0
159 | 0 0 -1 0 0 0 123 >= 0
161 The OpenScop access function is printed as follows:
163 | 1 # The number of disjunct components in a union of access functions.
164 | R C O I L P # Described bellow.
168 | 0 0 1 0 -1 -1 0 = 0
169 | 0 1 0 0 0 0 0 >= 0 # The last four lines describe the
170 | 0 0 1 0 0 0 0 >= 0 # array size.
171 | 0 -1 0 0 0 0 1335 >= 0
172 | 0 0 -1 0 0 0 123 >= 0
176 - C: Number of columns.
177 - O: Number of output dimensions = alias set + number of subscripts.
178 - I: Number of input dimensions (iterators).
179 - L: Number of local (existentially quantified) dimensions.
180 - P: Number of parameters.
182 In the example, the vector "R C O I L P" is "7 7 3 2 0 1". */
183 ppl_Pointset_Powerset_C_Polyhedron_t accesses;
185 /* Data reference's base object set number, we must assure 2 pdrs are in the
186 same base object set before dependency checking. */
187 int dr_base_object_set;
189 /* The number of subscripts. */
190 graphite_dim_t nb_subscripts;
193 #define PDR_ID(PDR) (PDR->id)
194 #define PDR_NB_REFS(PDR) (PDR->nb_refs)
195 #define PDR_CDR(PDR) (PDR->compiler_dr)
196 #define PDR_PBB(PDR) (PDR->pbb)
197 #define PDR_TYPE(PDR) (PDR->type)
198 #define PDR_ACCESSES(PDR) (PDR->accesses)
199 #define PDR_BASE_OBJECT_SET(PDR) (PDR->dr_base_object_set)
200 #define PDR_NB_SUBSCRIPTS(PDR) (PDR->nb_subscripts)
202 void new_poly_dr (poly_bb_p, int, ppl_Pointset_Powerset_C_Polyhedron_t,
203 enum poly_dr_type, void *, graphite_dim_t);
204 void free_poly_dr (poly_dr_p);
205 void debug_pdr (poly_dr_p, int);
206 void print_pdr (FILE *, poly_dr_p, int);
207 static inline scop_p pdr_scop (poly_dr_p pdr);
209 /* The dimension of the PDR_ACCESSES polyhedron of PDR. */
211 static inline ppl_dimension_type
212 pdr_dim (poly_dr_p pdr)
214 ppl_dimension_type dim;
215 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PDR_ACCESSES (pdr),
220 /* The dimension of the iteration domain of the scop of PDR. */
222 static inline ppl_dimension_type
223 pdr_dim_iter_domain (poly_dr_p pdr)
225 return pbb_dim_iter_domain (PDR_PBB (pdr));
228 /* The number of parameters of the scop of PDR. */
230 static inline ppl_dimension_type
231 pdr_nb_params (poly_dr_p pdr)
233 return scop_nb_params (pdr_scop (pdr));
236 /* The dimension of the alias set in PDR. */
238 static inline ppl_dimension_type
239 pdr_alias_set_dim (poly_dr_p pdr)
241 poly_bb_p pbb = PDR_PBB (pdr);
243 return pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
246 /* The dimension in PDR containing subscript S. */
248 static inline ppl_dimension_type
249 pdr_subscript_dim (poly_dr_p pdr, graphite_dim_t s)
251 poly_bb_p pbb = PDR_PBB (pdr);
253 return pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb) + 1 + s;
256 /* The dimension in PDR containing the loop iterator ITER. */
258 static inline ppl_dimension_type
259 pdr_iterator_dim (poly_dr_p pdr ATTRIBUTE_UNUSED, graphite_dim_t iter)
264 /* The dimension in PDR containing parameter PARAM. */
266 static inline ppl_dimension_type
267 pdr_parameter_dim (poly_dr_p pdr, graphite_dim_t param)
269 poly_bb_p pbb = PDR_PBB (pdr);
271 return pbb_dim_iter_domain (pbb) + param;
274 /* Returns true when PDR is a "read". */
277 pdr_read_p (poly_dr_p pdr)
279 return PDR_TYPE (pdr) == PDR_READ;
282 /* Returns true when PDR is a "write". */
285 pdr_write_p (poly_dr_p pdr)
287 return PDR_TYPE (pdr) == PDR_WRITE;
290 /* Returns true when PDR is a "may write". */
293 pdr_may_write_p (poly_dr_p pdr)
295 return PDR_TYPE (pdr) == PDR_MAY_WRITE;
298 /* Return true when PDR1 and PDR2 are similar data accesses: they have
299 the same base array, and the same access functions. */
302 same_pdr_p (poly_dr_p pdr1, poly_dr_p pdr2)
304 return PDR_TYPE (pdr1) == PDR_TYPE (pdr2)
305 && PDR_NB_SUBSCRIPTS (pdr1) == PDR_NB_SUBSCRIPTS (pdr2)
306 && PDR_BASE_OBJECT_SET (pdr1) == PDR_BASE_OBJECT_SET (pdr2);
309 typedef struct poly_scattering *poly_scattering_p;
311 struct poly_scattering
313 /* The scattering function containing the transformations: the
314 layout of this polyhedron is: T|I|G with T the transform
315 scattering, I the iteration domain, G the context parameters. */
316 ppl_Polyhedron_t scattering;
318 /* The number of local variables. */
319 int nb_local_variables;
321 /* The number of scattering dimensions. */
325 /* POLY_BB represents a blackbox in the polyhedral model. */
329 /* Pointer to a basic block or a statement in the compiler. */
332 /* Pointer to the SCOP containing this PBB. */
335 /* The iteration domain of this bb. The layout of this polyhedron
336 is I|G with I the iteration domain, G the context parameters.
340 for (i = a - 7*b + 8; i <= 3*a + 13*b + 20; i++)
341 for (j = 2; j <= 2*i + 5; j++)
342 for (k = 0; k <= 5; k++)
345 Loop iterators: i, j, k
355 The number of variables in the DOMAIN may change and is not
356 related to the number of loops in the original code. */
357 ppl_Pointset_Powerset_C_Polyhedron_t domain;
359 /* The data references we access. */
360 VEC (poly_dr_p, heap) *drs;
362 /* The original scattering. */
363 poly_scattering_p original;
365 /* The transformed scattering. */
366 poly_scattering_p transformed;
368 /* A copy of the transformed scattering. */
369 poly_scattering_p saved;
371 /* True when the PDR duplicates have already been removed. */
372 bool pdr_duplicates_removed;
374 /* True when this PBB contains only a reduction statement. */
378 #define PBB_BLACK_BOX(PBB) ((gimple_bb_p) PBB->black_box)
379 #define PBB_SCOP(PBB) (PBB->scop)
380 #define PBB_DOMAIN(PBB) (PBB->domain)
381 #define PBB_DRS(PBB) (PBB->drs)
382 #define PBB_ORIGINAL(PBB) (PBB->original)
383 #define PBB_ORIGINAL_SCATTERING(PBB) (PBB->original->scattering)
384 #define PBB_TRANSFORMED(PBB) (PBB->transformed)
385 #define PBB_TRANSFORMED_SCATTERING(PBB) (PBB->transformed->scattering)
386 #define PBB_SAVED(PBB) (PBB->saved)
387 #define PBB_NB_LOCAL_VARIABLES(PBB) (PBB->transformed->nb_local_variables)
388 #define PBB_NB_SCATTERING_TRANSFORM(PBB) (PBB->transformed->nb_scattering)
389 #define PBB_PDR_DUPLICATES_REMOVED(PBB) (PBB->pdr_duplicates_removed)
390 #define PBB_IS_REDUCTION(PBB) (PBB->is_reduction)
392 extern void new_poly_bb (scop_p, void *, bool);
393 extern void free_poly_bb (poly_bb_p);
394 extern void debug_loop_vec (poly_bb_p);
395 extern void schedule_to_scattering (poly_bb_p, int);
396 extern void print_pbb_domain (FILE *, poly_bb_p, int);
397 extern void print_pbb (FILE *, poly_bb_p, int);
398 extern void print_scop_context (FILE *, scop_p, int);
399 extern void print_scop (FILE *, scop_p, int);
400 extern void print_cloog (FILE *, scop_p, int);
401 extern void debug_pbb_domain (poly_bb_p, int);
402 extern void debug_pbb (poly_bb_p, int);
403 extern void print_pdrs (FILE *, poly_bb_p, int);
404 extern void debug_pdrs (poly_bb_p, int);
405 extern void debug_scop_context (scop_p, int);
406 extern void debug_scop (scop_p, int);
407 extern void debug_cloog (scop_p, int);
408 extern void print_scop_params (FILE *, scop_p, int);
409 extern void debug_scop_params (scop_p, int);
410 extern void print_iteration_domain (FILE *, poly_bb_p, int);
411 extern void print_iteration_domains (FILE *, scop_p, int);
412 extern void debug_iteration_domain (poly_bb_p, int);
413 extern void debug_iteration_domains (scop_p, int);
414 extern bool scop_do_interchange (scop_p);
415 extern bool scop_do_strip_mine (scop_p);
416 extern bool scop_do_block (scop_p);
417 extern void pbb_number_of_iterations (poly_bb_p, graphite_dim_t, mpz_t);
418 extern void pbb_number_of_iterations_at_time (poly_bb_p, graphite_dim_t, mpz_t);
419 extern void pbb_remove_duplicate_pdrs (poly_bb_p);
421 /* Return the number of write data references in PBB. */
424 number_of_write_pdrs (poly_bb_p pbb)
430 for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
431 if (PDR_TYPE (pdr) == PDR_WRITE)
437 /* The basic block of the PBB. */
439 static inline basic_block
440 pbb_bb (poly_bb_p pbb)
442 return GBB_BB (PBB_BLACK_BOX (pbb));
445 /* The index of the PBB. */
448 pbb_index (poly_bb_p pbb)
450 return pbb_bb (pbb)->index;
453 /* The loop of the PBB. */
456 pbb_loop (poly_bb_p pbb)
458 return gbb_loop (PBB_BLACK_BOX (pbb));
461 /* The scop that contains the PDR. */
464 pdr_scop (poly_dr_p pdr)
466 return PBB_SCOP (PDR_PBB (pdr));
469 /* Set black box of PBB to BLACKBOX. */
472 pbb_set_black_box (poly_bb_p pbb, void *black_box)
474 pbb->black_box = black_box;
477 /* The number of loops around PBB: the dimension of the iteration
480 static inline graphite_dim_t
481 pbb_dim_iter_domain (const struct poly_bb *pbb)
483 scop_p scop = PBB_SCOP (pbb);
484 ppl_dimension_type dim;
486 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb), &dim);
487 return dim - scop_nb_params (scop);
490 /* The number of params defined in PBB. */
492 static inline graphite_dim_t
493 pbb_nb_params (const struct poly_bb *pbb)
495 scop_p scop = PBB_SCOP (pbb);
497 return scop_nb_params (scop);
500 /* The number of scattering dimensions in the SCATTERING polyhedron
501 of a PBB for a given SCOP. */
503 static inline graphite_dim_t
504 pbb_nb_scattering_orig (const struct poly_bb *pbb)
506 return 2 * pbb_dim_iter_domain (pbb) + 1;
509 /* The number of scattering dimensions in PBB. */
511 static inline graphite_dim_t
512 pbb_nb_scattering_transform (const struct poly_bb *pbb)
514 return PBB_NB_SCATTERING_TRANSFORM (pbb);
517 /* The number of dynamic scattering dimensions in PBB. */
519 static inline graphite_dim_t
520 pbb_nb_dynamic_scattering_transform (const struct poly_bb *pbb)
522 /* This function requires the 2d + 1 scattering format to be
523 invariant during all transformations. */
524 gcc_assert (PBB_NB_SCATTERING_TRANSFORM (pbb) % 2);
525 return PBB_NB_SCATTERING_TRANSFORM (pbb) / 2;
528 /* Returns the number of local variables used in the transformed
529 scattering polyhedron of PBB. */
531 static inline graphite_dim_t
532 pbb_nb_local_vars (const struct poly_bb *pbb)
534 /* For now we do not have any local variables, as we do not do strip
535 mining for example. */
536 return PBB_NB_LOCAL_VARIABLES (pbb);
539 /* The dimension in the domain of PBB containing the iterator ITER. */
541 static inline ppl_dimension_type
542 pbb_iterator_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t iter)
547 /* The dimension in the domain of PBB containing the iterator ITER. */
549 static inline ppl_dimension_type
550 pbb_parameter_dim (poly_bb_p pbb, graphite_dim_t param)
553 + pbb_dim_iter_domain (pbb);
556 /* The dimension in the original scattering polyhedron of PBB
557 containing the scattering iterator SCATTER. */
559 static inline ppl_dimension_type
560 psco_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t scatter)
562 gcc_assert (scatter < pbb_nb_scattering_orig (pbb));
566 /* The dimension in the transformed scattering polyhedron of PBB
567 containing the scattering iterator SCATTER. */
569 static inline ppl_dimension_type
570 psct_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t scatter)
572 gcc_assert (scatter <= pbb_nb_scattering_transform (pbb));
576 ppl_dimension_type psct_scattering_dim_for_loop_depth (poly_bb_p,
579 /* The dimension in the transformed scattering polyhedron of PBB of
580 the local variable LV. */
582 static inline ppl_dimension_type
583 psct_local_var_dim (poly_bb_p pbb, graphite_dim_t lv)
585 gcc_assert (lv <= pbb_nb_local_vars (pbb));
586 return lv + pbb_nb_scattering_transform (pbb);
589 /* The dimension in the original scattering polyhedron of PBB
590 containing the loop iterator ITER. */
592 static inline ppl_dimension_type
593 psco_iterator_dim (poly_bb_p pbb, graphite_dim_t iter)
595 gcc_assert (iter < pbb_dim_iter_domain (pbb));
596 return iter + pbb_nb_scattering_orig (pbb);
599 /* The dimension in the transformed scattering polyhedron of PBB
600 containing the loop iterator ITER. */
602 static inline ppl_dimension_type
603 psct_iterator_dim (poly_bb_p pbb, graphite_dim_t iter)
605 gcc_assert (iter < pbb_dim_iter_domain (pbb));
607 + pbb_nb_scattering_transform (pbb)
608 + pbb_nb_local_vars (pbb);
611 /* The dimension in the original scattering polyhedron of PBB
612 containing parameter PARAM. */
614 static inline ppl_dimension_type
615 psco_parameter_dim (poly_bb_p pbb, graphite_dim_t param)
617 gcc_assert (param < pbb_nb_params (pbb));
619 + pbb_nb_scattering_orig (pbb)
620 + pbb_dim_iter_domain (pbb);
623 /* The dimension in the transformed scattering polyhedron of PBB
624 containing parameter PARAM. */
626 static inline ppl_dimension_type
627 psct_parameter_dim (poly_bb_p pbb, graphite_dim_t param)
629 gcc_assert (param < pbb_nb_params (pbb));
631 + pbb_nb_scattering_transform (pbb)
632 + pbb_nb_local_vars (pbb)
633 + pbb_dim_iter_domain (pbb);
636 /* The scattering dimension of PBB corresponding to the dynamic level
639 static inline ppl_dimension_type
640 psct_dynamic_dim (poly_bb_p pbb, graphite_dim_t level)
642 graphite_dim_t result = 1 + 2 * level;
644 gcc_assert (result < pbb_nb_scattering_transform (pbb));
648 /* The scattering dimension of PBB corresponding to the static
649 sequence of the loop level LEVEL. */
651 static inline ppl_dimension_type
652 psct_static_dim (poly_bb_p pbb, graphite_dim_t level)
654 graphite_dim_t result = 2 * level;
656 gcc_assert (result < pbb_nb_scattering_transform (pbb));
660 /* Adds to the transformed scattering polyhedron of PBB a new local
661 variable and returns its index. */
663 static inline graphite_dim_t
664 psct_add_local_variable (poly_bb_p pbb)
666 graphite_dim_t nlv = pbb_nb_local_vars (pbb);
667 ppl_dimension_type lv_column = psct_local_var_dim (pbb, nlv);
668 ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb), lv_column, 1);
669 PBB_NB_LOCAL_VARIABLES (pbb) += 1;
673 /* Adds a dimension to the transformed scattering polyhedron of PBB at
677 psct_add_scattering_dimension (poly_bb_p pbb, ppl_dimension_type index)
679 gcc_assert (index < pbb_nb_scattering_transform (pbb));
681 ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb), index, 1);
682 PBB_NB_SCATTERING_TRANSFORM (pbb) += 1;
685 typedef struct lst *lst_p;
687 DEF_VEC_ALLOC_P (lst_p, heap);
689 /* Loops and Statements Tree. */
692 /* LOOP_P is true when an LST node is a loop. */
695 /* A pointer to the loop that contains this node. */
698 /* The sum of all the memory strides for an LST loop. */
699 mpz_t memory_strides;
701 /* Loop nodes contain a sequence SEQ of LST nodes, statements
702 contain a pointer to their polyhedral representation PBB. */
705 VEC (lst_p, heap) *seq;
709 #define LST_LOOP_P(LST) ((LST)->loop_p)
710 #define LST_LOOP_FATHER(LST) ((LST)->loop_father)
711 #define LST_PBB(LST) ((LST)->node.pbb)
712 #define LST_SEQ(LST) ((LST)->node.seq)
713 #define LST_LOOP_MEMORY_STRIDES(LST) ((LST)->memory_strides)
715 void scop_to_lst (scop_p);
716 void print_lst (FILE *, lst_p, int);
717 void debug_lst (lst_p);
718 void dot_lst (lst_p);
720 /* Creates a new LST loop with SEQ. */
723 new_lst_loop (VEC (lst_p, heap) *seq)
725 lst_p lst = XNEW (struct lst);
729 LST_LOOP_P (lst) = true;
731 LST_LOOP_FATHER (lst) = NULL;
732 mpz_init (LST_LOOP_MEMORY_STRIDES (lst));
733 mpz_set_si (LST_LOOP_MEMORY_STRIDES (lst), -1);
735 for (i = 0; VEC_iterate (lst_p, seq, i, l); i++)
736 LST_LOOP_FATHER (l) = lst;
741 /* Creates a new LST statement with PBB. */
744 new_lst_stmt (poly_bb_p pbb)
746 lst_p lst = XNEW (struct lst);
748 LST_LOOP_P (lst) = false;
750 LST_LOOP_FATHER (lst) = NULL;
754 /* Frees the memory used by LST. */
762 if (LST_LOOP_P (lst))
767 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
770 mpz_clear (LST_LOOP_MEMORY_STRIDES (lst));
771 VEC_free (lst_p, heap, LST_SEQ (lst));
777 /* Returns a copy of LST. */
785 if (LST_LOOP_P (lst))
789 VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
791 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
792 VEC_safe_push (lst_p, heap, seq, copy_lst (l));
794 return new_lst_loop (seq);
797 return new_lst_stmt (LST_PBB (lst));
800 /* Adds a new loop under the loop LST. */
803 lst_add_loop_under_loop (lst_p lst)
805 VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 1);
806 lst_p l = new_lst_loop (LST_SEQ (lst));
808 gcc_assert (LST_LOOP_P (lst));
810 LST_LOOP_FATHER (l) = lst;
811 VEC_quick_push (lst_p, seq, l);
815 /* Returns the loop depth of LST. */
818 lst_depth (lst_p lst)
823 /* The depth of the outermost "fake" loop is -1. This outermost
824 loop does not have a loop father and it is just a container, as
825 in the loop representation of GCC. */
826 if (!LST_LOOP_FATHER (lst))
829 return lst_depth (LST_LOOP_FATHER (lst)) + 1;
832 /* Returns the Dewey number for LST. */
835 lst_dewey_number (lst_p lst)
843 if (!LST_LOOP_FATHER (lst))
846 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (LST_LOOP_FATHER (lst)), i, l)
853 /* Returns the Dewey number of LST at depth DEPTH. */
856 lst_dewey_number_at_depth (lst_p lst, int depth)
858 gcc_assert (lst && depth >= 0 && lst_depth (lst) <= depth);
860 if (lst_depth (lst) == depth)
861 return lst_dewey_number (lst);
863 return lst_dewey_number_at_depth (LST_LOOP_FATHER (lst), depth);
866 /* Returns the predecessor of LST in the sequence of its loop father.
867 Returns NULL if LST is the first statement in the sequence. */
875 if (!lst || !LST_LOOP_FATHER (lst))
878 dewey = lst_dewey_number (lst);
882 father = LST_LOOP_FATHER (lst);
883 return VEC_index (lst_p, LST_SEQ (father), dewey - 1);
886 /* Returns the successor of LST in the sequence of its loop father.
887 Returns NULL if there is none. */
895 if (!lst || !LST_LOOP_FATHER (lst))
898 dewey = lst_dewey_number (lst);
899 father = LST_LOOP_FATHER (lst);
901 if (VEC_length (lst_p, LST_SEQ (father)) == (unsigned) dewey + 1)
904 return VEC_index (lst_p, LST_SEQ (father), dewey + 1);
908 /* Return the LST node corresponding to PBB. */
911 lst_find_pbb (lst_p lst, poly_bb_p pbb)
919 if (!LST_LOOP_P (lst))
920 return (pbb == LST_PBB (lst)) ? lst : NULL;
922 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
924 lst_p res = lst_find_pbb (l, pbb);
932 /* Return the LST node corresponding to the loop around STMT at depth
936 find_lst_loop (lst_p stmt, int loop_depth)
938 lst_p loop = LST_LOOP_FATHER (stmt);
940 gcc_assert (loop_depth >= 0);
942 while (loop_depth < lst_depth (loop))
943 loop = LST_LOOP_FATHER (loop);
948 /* Return the first lst representing a PBB statement in LST. */
951 lst_find_first_pbb (lst_p lst)
959 if (!LST_LOOP_P (lst))
962 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
964 lst_p res = lst_find_first_pbb (l);
972 /* Returns true when LST is a loop that does not contains
976 lst_empty_p (lst_p lst)
978 return !lst_find_first_pbb (lst);
981 /* Return the last lst representing a PBB statement in LST. */
984 lst_find_last_pbb (lst_p lst)
992 if (!LST_LOOP_P (lst))
995 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
997 lst_p last = lst_find_last_pbb (l);
1007 /* Returns true if LOOP contains LST, in other words, if LST is nested
1011 lst_contains_p (lst_p loop, lst_p lst)
1013 if (!loop || !lst || !LST_LOOP_P (loop))
1019 return lst_contains_p (loop, LST_LOOP_FATHER (lst));
1022 /* Returns true if LOOP contains PBB, in other words, if PBB is nested
1026 lst_contains_pbb (lst_p loop, poly_bb_p pbb)
1028 return lst_find_pbb (loop, pbb) ? true : false;
1031 /* Creates a loop nest of depth NB_LOOPS containing LST. */
1034 lst_create_nest (int nb_loops, lst_p lst)
1037 VEC (lst_p, heap) *seq;
1042 seq = VEC_alloc (lst_p, heap, 1);
1043 loop = lst_create_nest (nb_loops - 1, lst);
1044 VEC_quick_push (lst_p, seq, loop);
1045 res = new_lst_loop (seq);
1046 LST_LOOP_FATHER (loop) = res;
1051 /* Removes LST from the sequence of statements of its loop father. */
1054 lst_remove_from_sequence (lst_p lst)
1056 lst_p father = LST_LOOP_FATHER (lst);
1057 int dewey = lst_dewey_number (lst);
1059 gcc_assert (lst && father && dewey >= 0);
1061 VEC_ordered_remove (lst_p, LST_SEQ (father), dewey);
1062 LST_LOOP_FATHER (lst) = NULL;
1065 /* Updates the scattering of PBB to be at the DEWEY number in the loop
1069 pbb_update_scattering (poly_bb_p pbb, graphite_dim_t level, int dewey)
1071 ppl_Polyhedron_t ph = PBB_TRANSFORMED_SCATTERING (pbb);
1072 ppl_dimension_type sched = psct_static_dim (pbb, level);
1073 ppl_dimension_type ds[1];
1074 ppl_Constraint_t new_cstr;
1075 ppl_Linear_Expression_t expr;
1076 ppl_dimension_type dim;
1078 ppl_Polyhedron_space_dimension (ph, &dim);
1080 ppl_Polyhedron_remove_space_dimensions (ph, ds, 1);
1081 ppl_insert_dimensions (ph, sched, 1);
1083 ppl_new_Linear_Expression_with_dimension (&expr, dim);
1084 ppl_set_coef (expr, sched, -1);
1085 ppl_set_inhomogeneous (expr, dewey);
1086 ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
1087 ppl_delete_Linear_Expression (expr);
1088 ppl_Polyhedron_add_constraint (ph, new_cstr);
1089 ppl_delete_Constraint (new_cstr);
1092 /* Updates the scattering of all the PBBs under LST to be at the DEWEY
1093 number in the loop at depth LEVEL. */
1096 lst_update_scattering_under (lst_p lst, int level, int dewey)
1101 gcc_assert (lst && level >= 0 && dewey >= 0);
1103 if (LST_LOOP_P (lst))
1104 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
1105 lst_update_scattering_under (l, level, dewey);
1107 pbb_update_scattering (LST_PBB (lst), level, dewey);
1110 /* Updates the scattering of all the PBBs under LST and in sequence
1114 lst_update_scattering_seq (lst_p lst)
1118 lst_p father = LST_LOOP_FATHER (lst);
1119 int dewey = lst_dewey_number (lst);
1120 int level = lst_depth (lst);
1122 gcc_assert (lst && father && dewey >= 0 && level >= 0);
1124 for (i = dewey; VEC_iterate (lst_p, LST_SEQ (father), i, l); i++)
1125 lst_update_scattering_under (l, level, i);
1128 /* Updates the all the scattering levels of all the PBBs under
1132 lst_update_scattering (lst_p lst)
1137 if (!lst || !LST_LOOP_P (lst))
1140 if (LST_LOOP_FATHER (lst))
1141 lst_update_scattering_seq (lst);
1143 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
1144 lst_update_scattering (l);
1147 /* Inserts LST1 before LST2 if BEFORE is true; inserts LST1 after LST2
1148 if BEFORE is false. */
1151 lst_insert_in_sequence (lst_p lst1, lst_p lst2, bool before)
1156 /* Do not insert empty loops. */
1157 if (!lst1 || lst_empty_p (lst1))
1160 father = LST_LOOP_FATHER (lst2);
1161 dewey = lst_dewey_number (lst2);
1163 gcc_assert (lst2 && father && dewey >= 0);
1165 VEC_safe_insert (lst_p, heap, LST_SEQ (father), before ? dewey : dewey + 1,
1167 LST_LOOP_FATHER (lst1) = father;
1170 /* Replaces LST1 with LST2. */
1173 lst_replace (lst_p lst1, lst_p lst2)
1178 if (!lst2 || lst_empty_p (lst2))
1181 father = LST_LOOP_FATHER (lst1);
1182 dewey = lst_dewey_number (lst1);
1183 LST_LOOP_FATHER (lst2) = father;
1184 VEC_replace (lst_p, LST_SEQ (father), dewey, lst2);
1187 /* Returns a copy of ROOT where LST has been replaced by a copy of the
1188 LSTs A B C in this sequence. */
1191 lst_substitute_3 (lst_p root, lst_p lst, lst_p a, lst_p b, lst_p c)
1195 VEC (lst_p, heap) *seq;
1200 gcc_assert (lst && root != lst);
1202 if (!LST_LOOP_P (root))
1203 return new_lst_stmt (LST_PBB (root));
1205 seq = VEC_alloc (lst_p, heap, 5);
1207 for (i = 0; VEC_iterate (lst_p, LST_SEQ (root), i, l); i++)
1209 VEC_safe_push (lst_p, heap, seq, lst_substitute_3 (l, lst, a, b, c));
1212 if (!lst_empty_p (a))
1213 VEC_safe_push (lst_p, heap, seq, copy_lst (a));
1214 if (!lst_empty_p (b))
1215 VEC_safe_push (lst_p, heap, seq, copy_lst (b));
1216 if (!lst_empty_p (c))
1217 VEC_safe_push (lst_p, heap, seq, copy_lst (c));
1220 return new_lst_loop (seq);
1223 /* Moves LST before LOOP if BEFORE is true, and after the LOOP if
1227 lst_distribute_lst (lst_p loop, lst_p lst, bool before)
1229 int loop_depth = lst_depth (loop);
1230 int depth = lst_depth (lst);
1231 int nb_loops = depth - loop_depth;
1233 gcc_assert (lst && loop && LST_LOOP_P (loop) && nb_loops > 0);
1235 lst_remove_from_sequence (lst);
1236 lst_insert_in_sequence (lst_create_nest (nb_loops, lst), loop, before);
1239 /* Removes from LOOP all the statements before/after and including PBB
1240 if BEFORE is true/false. Returns the negation of BEFORE when the
1241 statement PBB has been found. */
1244 lst_remove_all_before_including_pbb (lst_p loop, poly_bb_p pbb, bool before)
1249 if (!loop || !LST_LOOP_P (loop))
1252 for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l);)
1255 before = lst_remove_all_before_including_pbb (l, pbb, before);
1257 if (VEC_length (lst_p, LST_SEQ (l)) == 0)
1259 VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1269 if (LST_PBB (l) == pbb)
1272 VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1275 else if (LST_PBB (l) == pbb)
1278 VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1288 /* Removes from LOOP all the statements before/after and excluding PBB
1289 if BEFORE is true/false; Returns the negation of BEFORE when the
1290 statement PBB has been found. */
1293 lst_remove_all_before_excluding_pbb (lst_p loop, poly_bb_p pbb, bool before)
1298 if (!loop || !LST_LOOP_P (loop))
1301 for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l);)
1304 before = lst_remove_all_before_excluding_pbb (l, pbb, before);
1306 if (VEC_length (lst_p, LST_SEQ (l)) == 0)
1308 VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1317 if (before && LST_PBB (l) != pbb)
1319 VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1326 if (LST_PBB (l) == pbb)
1327 before = before ? false : true;
1333 /* A SCOP is a Static Control Part of the program, simple enough to be
1334 represented in polyhedral form. */
1337 /* A SCOP is defined as a SESE region. */
1340 /* Number of parameters in SCoP. */
1341 graphite_dim_t nb_params;
1343 /* All the basic blocks in this scop that contain memory references
1344 and that will be represented as statements in the polyhedral
1346 VEC (poly_bb_p, heap) *bbs;
1348 /* Original, transformed and saved schedules. */
1349 lst_p original_schedule, transformed_schedule, saved_schedule;
1351 /* The context describes known restrictions concerning the parameters
1352 and relations in between the parameters.
1354 void f (int8_t a, uint_16_t b) {
1359 Here we can add these restrictions to the context:
1364 ppl_Pointset_Powerset_C_Polyhedron_t context;
1366 /* A hashtable of the data dependence relations for the original
1368 htab_t original_pddrs;
1370 /* True when the scop has been converted to its polyhedral
1375 #define SCOP_BBS(S) (S->bbs)
1376 #define SCOP_REGION(S) ((sese) S->region)
1377 #define SCOP_CONTEXT(S) (S->context)
1378 #define SCOP_ORIGINAL_PDDRS(S) (S->original_pddrs)
1379 #define SCOP_ORIGINAL_SCHEDULE(S) (S->original_schedule)
1380 #define SCOP_TRANSFORMED_SCHEDULE(S) (S->transformed_schedule)
1381 #define SCOP_SAVED_SCHEDULE(S) (S->saved_schedule)
1382 #define POLY_SCOP_P(S) (S->poly_scop_p)
1384 extern scop_p new_scop (void *);
1385 extern void free_scop (scop_p);
1386 extern void free_scops (VEC (scop_p, heap) *);
1387 extern void print_generated_program (FILE *, scop_p);
1388 extern void debug_generated_program (scop_p);
1389 extern void print_scattering_function (FILE *, poly_bb_p, int);
1390 extern void print_scattering_functions (FILE *, scop_p, int);
1391 extern void debug_scattering_function (poly_bb_p, int);
1392 extern void debug_scattering_functions (scop_p, int);
1393 extern int scop_max_loop_depth (scop_p);
1394 extern int unify_scattering_dimensions (scop_p);
1395 extern bool apply_poly_transforms (scop_p);
1396 extern bool graphite_legal_transform (scop_p);
1398 /* Set the region of SCOP to REGION. */
1401 scop_set_region (scop_p scop, void *region)
1403 scop->region = region;
1406 /* Returns the number of parameters for SCOP. */
1408 static inline graphite_dim_t
1409 scop_nb_params (scop_p scop)
1411 return scop->nb_params;
1414 /* Set the number of params of SCOP to NB_PARAMS. */
1417 scop_set_nb_params (scop_p scop, graphite_dim_t nb_params)
1419 scop->nb_params = nb_params;
1422 /* Allocates a new empty poly_scattering structure. */
1424 static inline poly_scattering_p
1425 poly_scattering_new (void)
1427 poly_scattering_p res = XNEW (struct poly_scattering);
1429 res->scattering = NULL;
1430 res->nb_local_variables = 0;
1431 res->nb_scattering = 0;
1435 /* Free a poly_scattering structure. */
1438 poly_scattering_free (poly_scattering_p s)
1440 ppl_delete_Polyhedron (s->scattering);
1444 /* Copies S and return a new scattering. */
1446 static inline poly_scattering_p
1447 poly_scattering_copy (poly_scattering_p s)
1449 poly_scattering_p res = poly_scattering_new ();
1451 ppl_new_C_Polyhedron_from_C_Polyhedron (&(res->scattering), s->scattering);
1452 res->nb_local_variables = s->nb_local_variables;
1453 res->nb_scattering = s->nb_scattering;
1457 /* Saves the transformed scattering of PBB. */
1460 store_scattering_pbb (poly_bb_p pbb)
1462 gcc_assert (PBB_TRANSFORMED (pbb));
1464 if (PBB_SAVED (pbb))
1465 poly_scattering_free (PBB_SAVED (pbb));
1467 PBB_SAVED (pbb) = poly_scattering_copy (PBB_TRANSFORMED (pbb));
1470 /* Stores the SCOP_TRANSFORMED_SCHEDULE to SCOP_SAVED_SCHEDULE. */
1473 store_lst_schedule (scop_p scop)
1475 if (SCOP_SAVED_SCHEDULE (scop))
1476 free_lst (SCOP_SAVED_SCHEDULE (scop));
1478 SCOP_SAVED_SCHEDULE (scop) = copy_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
1481 /* Restores the SCOP_TRANSFORMED_SCHEDULE from SCOP_SAVED_SCHEDULE. */
1484 restore_lst_schedule (scop_p scop)
1486 if (SCOP_TRANSFORMED_SCHEDULE (scop))
1487 free_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
1489 SCOP_TRANSFORMED_SCHEDULE (scop) = copy_lst (SCOP_SAVED_SCHEDULE (scop));
1492 /* Saves the scattering for all the pbbs in the SCOP. */
1495 store_scattering (scop_p scop)
1500 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1501 store_scattering_pbb (pbb);
1503 store_lst_schedule (scop);
1506 /* Restores the scattering of PBB. */
1509 restore_scattering_pbb (poly_bb_p pbb)
1511 gcc_assert (PBB_SAVED (pbb));
1513 poly_scattering_free (PBB_TRANSFORMED (pbb));
1514 PBB_TRANSFORMED (pbb) = poly_scattering_copy (PBB_SAVED (pbb));
1517 /* Restores the scattering for all the pbbs in the SCOP. */
1520 restore_scattering (scop_p scop)
1525 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1526 restore_scattering_pbb (pbb);
1528 restore_lst_schedule (scop);
1531 /* For a given PBB, add to RES the scop context, the iteration domain,
1532 the original scattering when ORIGINAL_P is true, otherwise add the
1533 transformed scattering. */
1536 combine_context_id_scat (ppl_Pointset_Powerset_C_Polyhedron_t *res,
1537 poly_bb_p pbb, bool original_p)
1539 ppl_Pointset_Powerset_C_Polyhedron_t context;
1540 ppl_Pointset_Powerset_C_Polyhedron_t id;
1542 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1544 PBB_ORIGINAL_SCATTERING (pbb) : PBB_TRANSFORMED_SCATTERING (pbb));
1546 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1547 (&context, SCOP_CONTEXT (PBB_SCOP (pbb)));
1549 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1550 (&id, PBB_DOMAIN (pbb));
1552 /* Extend the context and the iteration domain to the dimension of
1553 the scattering: T|I|G. */
1555 ppl_dimension_type gdim, tdim, idim;
1557 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (*res, &tdim);
1558 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (context, &gdim);
1559 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (id, &idim);
1562 ppl_insert_dimensions_pointset (context, 0, tdim - gdim);
1565 ppl_insert_dimensions_pointset (id, 0, tdim - idim);
1568 /* Add the context and the iteration domain to the result. */
1569 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (*res, context);
1570 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (*res, id);
1572 ppl_delete_Pointset_Powerset_C_Polyhedron (context);
1573 ppl_delete_Pointset_Powerset_C_Polyhedron (id);