1 /* Graphite polyhedral representation.
2 Copyright (C) 2009-2014 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 typedef struct poly_bb
*poly_bb_p
;
29 typedef struct scop
*scop_p
;
31 typedef unsigned graphite_dim_t
;
33 static inline graphite_dim_t
pbb_dim_iter_domain (const struct poly_bb
*);
34 static inline graphite_dim_t
pbb_nb_params (const struct poly_bb
*);
35 static inline graphite_dim_t
scop_nb_params (scop_p
);
37 /* A data reference can write or read some memory or we
38 just know it may write some memory. */
42 /* PDR_MAY_READs are represented using PDR_READS. This does not
43 limit the expressiveness. */
50 /* An identifier for this PDR. */
53 /* The number of data refs identical to this one in the PBB. */
56 /* A pointer to compiler's data reference description. */
59 /* A pointer to the PBB that contains this data reference. */
62 enum poly_dr_type type
;
64 /* The access polyhedron contains the polyhedral space this data
65 reference will access.
67 The polyhedron contains these dimensions:
70 Every memory access is classified in at least one alias set.
72 - The subscripts (s_0, ..., s_n):
73 The memory is accessed using zero or more subscript dimensions.
75 - The iteration domain (variables and parameters)
77 Do not hardcode the dimensions. Use the following accessor functions:
91 | if (unknown_function ())
98 The data access A[i][j+k] in alias set "5" is described like this:
103 | 0 -1 -1 0 0 1 0 = 0
104 | 0 0 0 0 1 0 0 >= 0 # The last four lines describe the
105 | 0 0 0 0 0 1 0 >= 0 # array size.
106 | 0 0 0 0 -1 0 1335 >= 0
107 | 0 0 0 0 0 -1 123 >= 0
109 The pointer "*p" in alias set "5" and "7" is described as a union of
123 "*p" accesses all of the object allocated with 'malloc'.
125 The scalar data access "m" is represented as an array with zero subscript
131 The difference between the graphite internal format for access data and
132 the OpenSop format is in the order of columns.
138 | 0 -1 -1 0 0 1 0 = 0
139 | 0 0 0 0 1 0 0 >= 0 # The last four lines describe the
140 | 0 0 0 0 0 1 0 >= 0 # array size.
141 | 0 0 0 0 -1 0 1335 >= 0
142 | 0 0 0 0 0 -1 123 >= 0
149 | 0 0 1 0 -1 -1 0 = 0
150 | 0 1 0 0 0 0 0 >= 0 # The last four lines describe the
151 | 0 0 1 0 0 0 0 >= 0 # array size.
152 | 0 -1 0 0 0 0 1335 >= 0
153 | 0 0 -1 0 0 0 123 >= 0
155 The OpenScop access function is printed as follows:
157 | 1 # The number of disjunct components in a union of access functions.
158 | R C O I L P # Described bellow.
162 | 0 0 1 0 -1 -1 0 = 0
163 | 0 1 0 0 0 0 0 >= 0 # The last four lines describe the
164 | 0 0 1 0 0 0 0 >= 0 # array size.
165 | 0 -1 0 0 0 0 1335 >= 0
166 | 0 0 -1 0 0 0 123 >= 0
170 - C: Number of columns.
171 - O: Number of output dimensions = alias set + number of subscripts.
172 - I: Number of input dimensions (iterators).
173 - L: Number of local (existentially quantified) dimensions.
174 - P: Number of parameters.
176 In the example, the vector "R C O I L P" is "7 7 3 2 0 1". */
180 /* Data reference's base object set number, we must assure 2 pdrs are in the
181 same base object set before dependency checking. */
182 int dr_base_object_set
;
184 /* The number of subscripts. */
185 graphite_dim_t nb_subscripts
;
188 #define PDR_ID(PDR) (PDR->id)
189 #define PDR_NB_REFS(PDR) (PDR->nb_refs)
190 #define PDR_CDR(PDR) (PDR->compiler_dr)
191 #define PDR_PBB(PDR) (PDR->pbb)
192 #define PDR_TYPE(PDR) (PDR->type)
193 #define PDR_ACCESSES(PDR) (NULL)
194 #define PDR_BASE_OBJECT_SET(PDR) (PDR->dr_base_object_set)
195 #define PDR_NB_SUBSCRIPTS(PDR) (PDR->nb_subscripts)
197 void new_poly_dr (poly_bb_p
, int, enum poly_dr_type
, void *,
198 graphite_dim_t
, isl_map
*, isl_set
*);
199 void free_poly_dr (poly_dr_p
);
200 void debug_pdr (poly_dr_p
, int);
201 void print_pdr (FILE *, poly_dr_p
, int);
202 static inline scop_p
pdr_scop (poly_dr_p pdr
);
204 /* The dimension of the iteration domain of the scop of PDR. */
206 static inline graphite_dim_t
207 pdr_dim_iter_domain (poly_dr_p pdr
)
209 return pbb_dim_iter_domain (PDR_PBB (pdr
));
212 /* The number of parameters of the scop of PDR. */
214 static inline graphite_dim_t
215 pdr_nb_params (poly_dr_p pdr
)
217 return scop_nb_params (pdr_scop (pdr
));
220 /* The dimension of the alias set in PDR. */
222 static inline graphite_dim_t
223 pdr_alias_set_dim (poly_dr_p pdr
)
225 poly_bb_p pbb
= PDR_PBB (pdr
);
227 return pbb_dim_iter_domain (pbb
) + pbb_nb_params (pbb
);
230 /* The dimension in PDR containing subscript S. */
232 static inline graphite_dim_t
233 pdr_subscript_dim (poly_dr_p pdr
, graphite_dim_t s
)
235 poly_bb_p pbb
= PDR_PBB (pdr
);
237 return pbb_dim_iter_domain (pbb
) + pbb_nb_params (pbb
) + 1 + s
;
240 /* The dimension in PDR containing the loop iterator ITER. */
242 static inline graphite_dim_t
243 pdr_iterator_dim (poly_dr_p pdr ATTRIBUTE_UNUSED
, graphite_dim_t iter
)
248 /* The dimension in PDR containing parameter PARAM. */
250 static inline graphite_dim_t
251 pdr_parameter_dim (poly_dr_p pdr
, graphite_dim_t param
)
253 poly_bb_p pbb
= PDR_PBB (pdr
);
255 return pbb_dim_iter_domain (pbb
) + param
;
258 /* Returns true when PDR is a "read". */
261 pdr_read_p (poly_dr_p pdr
)
263 return PDR_TYPE (pdr
) == PDR_READ
;
266 /* Returns true when PDR is a "write". */
269 pdr_write_p (poly_dr_p pdr
)
271 return PDR_TYPE (pdr
) == PDR_WRITE
;
274 /* Returns true when PDR is a "may write". */
277 pdr_may_write_p (poly_dr_p pdr
)
279 return PDR_TYPE (pdr
) == PDR_MAY_WRITE
;
282 /* Return true when PDR1 and PDR2 are similar data accesses: they have
283 the same base array, and the same access functions. */
286 same_pdr_p (poly_dr_p pdr1
, poly_dr_p pdr2
)
288 return PDR_NB_SUBSCRIPTS (pdr1
) == PDR_NB_SUBSCRIPTS (pdr2
)
289 && PDR_BASE_OBJECT_SET (pdr1
) == PDR_BASE_OBJECT_SET (pdr2
);
292 typedef struct poly_scattering
*poly_scattering_p
;
294 struct poly_scattering
296 /* The number of local variables. */
297 int nb_local_variables
;
299 /* The number of scattering dimensions. */
303 /* POLY_BB represents a blackbox in the polyhedral model. */
307 /* Pointer to a basic block or a statement in the compiler. */
310 /* Pointer to the SCOP containing this PBB. */
313 /* The iteration domain of this bb. The layout of this polyhedron
314 is I|G with I the iteration domain, G the context parameters.
318 for (i = a - 7*b + 8; i <= 3*a + 13*b + 20; i++)
319 for (j = 2; j <= 2*i + 5; j++)
320 for (k = 0; k <= 5; k++)
323 Loop iterators: i, j, k
333 The number of variables in the DOMAIN may change and is not
334 related to the number of loops in the original code. */
337 /* The data references we access. */
340 /* The original scattering. */
341 poly_scattering_p _original
;
344 /* The transformed scattering. */
345 poly_scattering_p _transformed
;
346 isl_map
*transformed
;
348 /* A copy of the transformed scattering. */
349 poly_scattering_p _saved
;
352 /* True when this PBB contains only a reduction statement. */
356 #define PBB_BLACK_BOX(PBB) ((gimple_bb_p) PBB->black_box)
357 #define PBB_SCOP(PBB) (PBB->scop)
358 #define PBB_DOMAIN(PBB) (NULL)
359 #define PBB_DRS(PBB) (PBB->drs)
360 #define PBB_ORIGINAL(PBB) (PBB->_original)
361 #define PBB_ORIGINAL_SCATTERING(PBB) (NULL)
362 #define PBB_TRANSFORMED(PBB) (PBB->_transformed)
363 #define PBB_TRANSFORMED_SCATTERING(PBB) (NULL)
364 #define PBB_SAVED(PBB) (PBB->_saved)
365 /* XXX isl if we ever need local vars in the scatter, we can't use the
366 out dimension of transformed to count the scatterting transform dimension.
368 #define PBB_NB_LOCAL_VARIABLES(PBB) (0)
369 #define PBB_NB_SCATTERING_TRANSFORM(PBB) (isl_map_n_out (PBB->transformed))
370 #define PBB_IS_REDUCTION(PBB) (PBB->is_reduction)
372 extern poly_bb_p
new_poly_bb (scop_p
, void *);
373 extern void free_poly_bb (poly_bb_p
);
374 extern void debug_loop_vec (poly_bb_p
);
375 extern void schedule_to_scattering (poly_bb_p
, int);
376 extern void print_pbb_domain (FILE *, poly_bb_p
, int);
377 extern void print_pbb (FILE *, poly_bb_p
, int);
378 extern void print_scop_context (FILE *, scop_p
, int);
379 extern void print_scop (FILE *, scop_p
, int);
380 extern void debug_pbb_domain (poly_bb_p
, int);
381 extern void debug_pbb (poly_bb_p
, int);
382 extern void print_pdrs (FILE *, poly_bb_p
, int);
383 extern void debug_pdrs (poly_bb_p
, int);
384 extern void debug_scop_context (scop_p
, int);
385 extern void debug_scop (scop_p
, int);
386 extern void print_scop_params (FILE *, scop_p
, int);
387 extern void debug_scop_params (scop_p
, int);
388 extern void print_iteration_domain (FILE *, poly_bb_p
, int);
389 extern void print_iteration_domains (FILE *, scop_p
, int);
390 extern void debug_iteration_domain (poly_bb_p
, int);
391 extern void debug_iteration_domains (scop_p
, int);
392 extern void print_isl_set (FILE *, isl_set
*);
393 extern void print_isl_map (FILE *, isl_map
*);
394 extern void print_isl_aff (FILE *, isl_aff
*);
395 extern void print_isl_constraint (FILE *, isl_constraint
*);
396 extern void debug_isl_set (isl_set
*);
397 extern void debug_isl_map (isl_map
*);
398 extern void debug_isl_aff (isl_aff
*);
399 extern void debug_isl_constraint (isl_constraint
*);
400 extern int scop_do_interchange (scop_p
);
401 extern int scop_do_strip_mine (scop_p
, int);
402 extern bool scop_do_block (scop_p
);
403 extern bool flatten_all_loops (scop_p
);
404 extern bool optimize_isl (scop_p
);
405 extern void pbb_number_of_iterations_at_time (poly_bb_p
, graphite_dim_t
, mpz_t
);
406 extern void debug_gmp_value (mpz_t
);
408 /* Return the number of write data references in PBB. */
411 number_of_write_pdrs (poly_bb_p pbb
)
417 for (i
= 0; PBB_DRS (pbb
).iterate (i
, &pdr
); i
++)
418 if (PDR_TYPE (pdr
) == PDR_WRITE
)
424 /* Returns a gimple_bb from BB. */
426 static inline gimple_bb_p
427 gbb_from_bb (basic_block bb
)
429 return (gimple_bb_p
) bb
->aux
;
432 /* The poly_bb of the BB. */
434 static inline poly_bb_p
435 pbb_from_bb (basic_block bb
)
437 return GBB_PBB (gbb_from_bb (bb
));
440 /* The basic block of the PBB. */
442 static inline basic_block
443 pbb_bb (poly_bb_p pbb
)
445 return GBB_BB (PBB_BLACK_BOX (pbb
));
448 /* The index of the PBB. */
451 pbb_index (poly_bb_p pbb
)
453 return pbb_bb (pbb
)->index
;
456 /* The loop of the PBB. */
459 pbb_loop (poly_bb_p pbb
)
461 return gbb_loop (PBB_BLACK_BOX (pbb
));
464 /* The scop that contains the PDR. */
467 pdr_scop (poly_dr_p pdr
)
469 return PBB_SCOP (PDR_PBB (pdr
));
472 /* Set black box of PBB to BLACKBOX. */
475 pbb_set_black_box (poly_bb_p pbb
, void *black_box
)
477 pbb
->black_box
= black_box
;
480 /* The number of loops around PBB: the dimension of the iteration
483 static inline graphite_dim_t
484 pbb_dim_iter_domain (const struct poly_bb
*pbb
)
486 return isl_set_dim (pbb
->domain
, isl_dim_set
);
489 /* The number of params defined in PBB. */
491 static inline graphite_dim_t
492 pbb_nb_params (const struct poly_bb
*pbb
)
494 scop_p scop
= PBB_SCOP (pbb
);
496 return scop_nb_params (scop
);
499 /* The number of scattering dimensions in the SCATTERING polyhedron
500 of a PBB for a given SCOP. */
502 static inline graphite_dim_t
503 pbb_nb_scattering_orig (const struct poly_bb
*pbb
)
505 return 2 * pbb_dim_iter_domain (pbb
) + 1;
508 /* The number of scattering dimensions in PBB. */
510 static inline graphite_dim_t
511 pbb_nb_scattering_transform (const struct poly_bb
*pbb
)
513 return PBB_NB_SCATTERING_TRANSFORM (pbb
);
516 /* The number of dynamic scattering dimensions in PBB. */
518 static inline graphite_dim_t
519 pbb_nb_dynamic_scattering_transform (const struct poly_bb
*pbb
)
521 /* This function requires the 2d + 1 scattering format to be
522 invariant during all transformations. */
523 gcc_assert (PBB_NB_SCATTERING_TRANSFORM (pbb
) % 2);
524 return PBB_NB_SCATTERING_TRANSFORM (pbb
) / 2;
527 /* Returns the number of local variables used in the transformed
528 scattering polyhedron of PBB. */
530 static inline graphite_dim_t
531 pbb_nb_local_vars (const struct poly_bb
*pbb ATTRIBUTE_UNUSED
)
533 /* For now we do not have any local variables, as we do not do strip
534 mining for example. */
535 return PBB_NB_LOCAL_VARIABLES (pbb
);
538 /* The dimension in the domain of PBB containing the iterator ITER. */
540 static inline graphite_dim_t
541 pbb_iterator_dim (poly_bb_p pbb ATTRIBUTE_UNUSED
, graphite_dim_t iter
)
546 /* The dimension in the domain of PBB containing the iterator ITER. */
548 static inline graphite_dim_t
549 pbb_parameter_dim (poly_bb_p pbb
, graphite_dim_t param
)
552 + pbb_dim_iter_domain (pbb
);
555 /* The dimension in the original scattering polyhedron of PBB
556 containing the scattering iterator SCATTER. */
558 static inline graphite_dim_t
559 psco_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED
, graphite_dim_t scatter
)
561 gcc_assert (scatter
< pbb_nb_scattering_orig (pbb
));
565 /* The dimension in the transformed scattering polyhedron of PBB
566 containing the scattering iterator SCATTER. */
568 static inline graphite_dim_t
569 psct_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED
, graphite_dim_t scatter
)
571 gcc_assert (scatter
<= pbb_nb_scattering_transform (pbb
));
575 /* The dimension in the transformed scattering polyhedron of PBB of
576 the local variable LV. */
578 static inline graphite_dim_t
579 psct_local_var_dim (poly_bb_p pbb
, graphite_dim_t lv
)
581 gcc_assert (lv
<= pbb_nb_local_vars (pbb
));
582 return lv
+ pbb_nb_scattering_transform (pbb
);
585 /* The dimension in the original scattering polyhedron of PBB
586 containing the loop iterator ITER. */
588 static inline graphite_dim_t
589 psco_iterator_dim (poly_bb_p pbb
, graphite_dim_t iter
)
591 gcc_assert (iter
< pbb_dim_iter_domain (pbb
));
592 return iter
+ pbb_nb_scattering_orig (pbb
);
595 /* The dimension in the transformed scattering polyhedron of PBB
596 containing the loop iterator ITER. */
598 static inline graphite_dim_t
599 psct_iterator_dim (poly_bb_p pbb
, graphite_dim_t iter
)
601 gcc_assert (iter
< pbb_dim_iter_domain (pbb
));
603 + pbb_nb_scattering_transform (pbb
)
604 + pbb_nb_local_vars (pbb
);
607 /* The dimension in the original scattering polyhedron of PBB
608 containing parameter PARAM. */
610 static inline graphite_dim_t
611 psco_parameter_dim (poly_bb_p pbb
, graphite_dim_t param
)
613 gcc_assert (param
< pbb_nb_params (pbb
));
615 + pbb_nb_scattering_orig (pbb
)
616 + pbb_dim_iter_domain (pbb
);
619 /* The dimension in the transformed scattering polyhedron of PBB
620 containing parameter PARAM. */
622 static inline graphite_dim_t
623 psct_parameter_dim (poly_bb_p pbb
, graphite_dim_t param
)
625 gcc_assert (param
< pbb_nb_params (pbb
));
627 + pbb_nb_scattering_transform (pbb
)
628 + pbb_nb_local_vars (pbb
)
629 + pbb_dim_iter_domain (pbb
);
632 /* The scattering dimension of PBB corresponding to the dynamic level
635 static inline graphite_dim_t
636 psct_dynamic_dim (poly_bb_p pbb
, graphite_dim_t level
)
638 graphite_dim_t result
= 1 + 2 * level
;
640 gcc_assert (result
< pbb_nb_scattering_transform (pbb
));
644 /* The scattering dimension of PBB corresponding to the static
645 sequence of the loop level LEVEL. */
647 static inline graphite_dim_t
648 psct_static_dim (poly_bb_p pbb
, graphite_dim_t level
)
650 graphite_dim_t result
= 2 * level
;
652 gcc_assert (result
< pbb_nb_scattering_transform (pbb
));
656 /* Adds to the transformed scattering polyhedron of PBB a new local
657 variable and returns its index. */
659 static inline graphite_dim_t
660 psct_add_local_variable (poly_bb_p pbb ATTRIBUTE_UNUSED
)
666 typedef struct lst
*lst_p
;
668 /* Loops and Statements Tree. */
671 /* LOOP_P is true when an LST node is a loop. */
674 /* A pointer to the loop that contains this node. */
677 /* The sum of all the memory strides for an LST loop. */
678 mpz_t memory_strides
;
680 /* Loop nodes contain a sequence SEQ of LST nodes, statements
681 contain a pointer to their polyhedral representation PBB. */
688 #define LST_LOOP_P(LST) ((LST)->loop_p)
689 #define LST_LOOP_FATHER(LST) ((LST)->loop_father)
690 #define LST_PBB(LST) ((LST)->node.pbb)
691 #define LST_SEQ(LST) ((LST)->node.seq)
692 #define LST_LOOP_MEMORY_STRIDES(LST) ((LST)->memory_strides)
694 void scop_to_lst (scop_p
);
695 void print_lst (FILE *, lst_p
, int);
696 void debug_lst (lst_p
);
697 void dot_lst (lst_p
);
699 /* Creates a new LST loop with SEQ. */
702 new_lst_loop (vec
<lst_p
> seq
)
704 lst_p lst
= XNEW (struct lst
);
708 LST_LOOP_P (lst
) = true;
710 LST_LOOP_FATHER (lst
) = NULL
;
711 mpz_init (LST_LOOP_MEMORY_STRIDES (lst
));
712 mpz_set_si (LST_LOOP_MEMORY_STRIDES (lst
), -1);
714 for (i
= 0; seq
.iterate (i
, &l
); i
++)
715 LST_LOOP_FATHER (l
) = lst
;
720 /* Creates a new LST statement with PBB. */
723 new_lst_stmt (poly_bb_p pbb
)
725 lst_p lst
= XNEW (struct lst
);
727 LST_LOOP_P (lst
) = false;
729 LST_LOOP_FATHER (lst
) = NULL
;
733 /* Frees the memory used by LST. */
741 if (LST_LOOP_P (lst
))
746 for (i
= 0; LST_SEQ (lst
).iterate (i
, &l
); i
++)
749 mpz_clear (LST_LOOP_MEMORY_STRIDES (lst
));
750 LST_SEQ (lst
).release ();
756 /* Returns a copy of LST. */
764 if (LST_LOOP_P (lst
))
771 for (i
= 0; LST_SEQ (lst
).iterate (i
, &l
); i
++)
772 seq
.safe_push (copy_lst (l
));
774 return new_lst_loop (seq
);
777 return new_lst_stmt (LST_PBB (lst
));
780 /* Adds a new loop under the loop LST. */
783 lst_add_loop_under_loop (lst_p lst
)
787 lst_p l
= new_lst_loop (LST_SEQ (lst
));
789 gcc_assert (LST_LOOP_P (lst
));
791 LST_LOOP_FATHER (l
) = lst
;
796 /* Returns the loop depth of LST. */
799 lst_depth (lst_p lst
)
804 /* The depth of the outermost "fake" loop is -1. This outermost
805 loop does not have a loop father and it is just a container, as
806 in the loop representation of GCC. */
807 if (!LST_LOOP_FATHER (lst
))
810 return lst_depth (LST_LOOP_FATHER (lst
)) + 1;
813 /* Returns the Dewey number for LST. */
816 lst_dewey_number (lst_p lst
)
824 if (!LST_LOOP_FATHER (lst
))
827 FOR_EACH_VEC_ELT (LST_SEQ (LST_LOOP_FATHER (lst
)), i
, l
)
834 /* Returns the Dewey number of LST at depth DEPTH. */
837 lst_dewey_number_at_depth (lst_p lst
, int depth
)
839 gcc_assert (lst
&& depth
>= 0 && lst_depth (lst
) <= depth
);
841 if (lst_depth (lst
) == depth
)
842 return lst_dewey_number (lst
);
844 return lst_dewey_number_at_depth (LST_LOOP_FATHER (lst
), depth
);
847 /* Returns the predecessor of LST in the sequence of its loop father.
848 Returns NULL if LST is the first statement in the sequence. */
856 if (!lst
|| !LST_LOOP_FATHER (lst
))
859 dewey
= lst_dewey_number (lst
);
863 father
= LST_LOOP_FATHER (lst
);
864 return LST_SEQ (father
)[dewey
- 1];
867 /* Returns the successor of LST in the sequence of its loop father.
868 Returns NULL if there is none. */
876 if (!lst
|| !LST_LOOP_FATHER (lst
))
879 dewey
= lst_dewey_number (lst
);
880 father
= LST_LOOP_FATHER (lst
);
882 if (LST_SEQ (father
).length () == (unsigned) dewey
+ 1)
885 return LST_SEQ (father
)[dewey
+ 1];
889 /* Return the LST node corresponding to PBB. */
892 lst_find_pbb (lst_p lst
, poly_bb_p pbb
)
900 if (!LST_LOOP_P (lst
))
901 return (pbb
== LST_PBB (lst
)) ? lst
: NULL
;
903 for (i
= 0; LST_SEQ (lst
).iterate (i
, &l
); i
++)
905 lst_p res
= lst_find_pbb (l
, pbb
);
913 /* Return the LST node corresponding to the loop around STMT at depth
917 find_lst_loop (lst_p stmt
, int loop_depth
)
919 lst_p loop
= LST_LOOP_FATHER (stmt
);
921 gcc_assert (loop_depth
>= 0);
923 while (loop_depth
< lst_depth (loop
))
924 loop
= LST_LOOP_FATHER (loop
);
929 /* Return the first LST representing a PBB statement in LST. */
932 lst_find_first_pbb (lst_p lst
)
940 if (!LST_LOOP_P (lst
))
943 for (i
= 0; LST_SEQ (lst
).iterate (i
, &l
); i
++)
945 lst_p res
= lst_find_first_pbb (l
);
953 /* Returns true when LST is a loop that does not contain
957 lst_empty_p (lst_p lst
)
959 return !lst_find_first_pbb (lst
);
962 /* Return the last LST representing a PBB statement in LST. */
965 lst_find_last_pbb (lst_p lst
)
973 if (!LST_LOOP_P (lst
))
976 for (i
= 0; LST_SEQ (lst
).iterate (i
, &l
); i
++)
978 lst_p last
= lst_find_last_pbb (l
);
988 /* Returns true if LOOP contains LST, in other words, if LST is nested
992 lst_contains_p (lst_p loop
, lst_p lst
)
994 if (!loop
|| !lst
|| !LST_LOOP_P (loop
))
1000 return lst_contains_p (loop
, LST_LOOP_FATHER (lst
));
1003 /* Returns true if LOOP contains PBB, in other words, if PBB is nested
1007 lst_contains_pbb (lst_p loop
, poly_bb_p pbb
)
1009 return lst_find_pbb (loop
, pbb
) ? true : false;
1012 /* Creates a loop nest of depth NB_LOOPS containing LST. */
1015 lst_create_nest (int nb_loops
, lst_p lst
)
1024 loop
= lst_create_nest (nb_loops
- 1, lst
);
1025 seq
.quick_push (loop
);
1026 res
= new_lst_loop (seq
);
1027 LST_LOOP_FATHER (loop
) = res
;
1032 /* Removes LST from the sequence of statements of its loop father. */
1035 lst_remove_from_sequence (lst_p lst
)
1037 lst_p father
= LST_LOOP_FATHER (lst
);
1038 int dewey
= lst_dewey_number (lst
);
1040 gcc_assert (lst
&& father
&& dewey
>= 0);
1042 LST_SEQ (father
).ordered_remove (dewey
);
1043 LST_LOOP_FATHER (lst
) = NULL
;
1046 /* Removes the loop LST and inline its body in the father loop. */
1049 lst_remove_loop_and_inline_stmts_in_loop_father (lst_p lst
)
1051 lst_p l
, father
= LST_LOOP_FATHER (lst
);
1052 int i
, dewey
= lst_dewey_number (lst
);
1054 gcc_assert (lst
&& father
&& dewey
>= 0);
1056 LST_SEQ (father
).ordered_remove (dewey
);
1057 LST_LOOP_FATHER (lst
) = NULL
;
1059 FOR_EACH_VEC_ELT (LST_SEQ (lst
), i
, l
)
1061 LST_SEQ (father
).safe_insert (dewey
+ i
, l
);
1062 LST_LOOP_FATHER (l
) = father
;
1066 /* Sets NITER to the upper bound approximation of the number of
1067 iterations of loop LST. */
1070 lst_niter_for_loop (lst_p lst
, mpz_t niter
)
1072 int depth
= lst_depth (lst
);
1073 poly_bb_p pbb
= LST_PBB (lst_find_first_pbb (lst
));
1075 gcc_assert (LST_LOOP_P (lst
));
1076 pbb_number_of_iterations_at_time (pbb
, psct_dynamic_dim (pbb
, depth
), niter
);
1079 /* Updates the scattering of PBB to be at the DEWEY number in the loop
1083 pbb_update_scattering (poly_bb_p pbb
, graphite_dim_t level
, int dewey
)
1085 graphite_dim_t sched
= psct_static_dim (pbb
, level
);
1086 isl_space
*d
= isl_map_get_space (pbb
->transformed
);
1087 isl_space
*d1
= isl_space_range (d
);
1088 unsigned i
, n
= isl_space_dim (d1
, isl_dim_out
);
1089 isl_space
*d2
= isl_space_add_dims (d1
, isl_dim_in
, n
);
1090 isl_map
*x
= isl_map_universe (d2
);
1092 x
= isl_map_fix_si (x
, isl_dim_out
, sched
, dewey
);
1094 for (i
= 0; i
< n
; i
++)
1096 x
= isl_map_equate (x
, isl_dim_in
, i
, isl_dim_out
, i
);
1098 pbb
->transformed
= isl_map_apply_range (pbb
->transformed
, x
);
1101 /* Updates the scattering of all the PBBs under LST to be at the DEWEY
1102 number in the loop at depth LEVEL. */
1105 lst_update_scattering_under (lst_p lst
, int level
, int dewey
)
1110 gcc_assert (lst
&& level
>= 0 && dewey
>= 0);
1112 if (LST_LOOP_P (lst
))
1113 for (i
= 0; LST_SEQ (lst
).iterate (i
, &l
); i
++)
1114 lst_update_scattering_under (l
, level
, dewey
);
1116 pbb_update_scattering (LST_PBB (lst
), level
, dewey
);
1119 /* Updates the all the scattering levels of all the PBBs under
1123 lst_update_scattering (lst_p lst
)
1131 if (LST_LOOP_FATHER (lst
))
1133 lst_p father
= LST_LOOP_FATHER (lst
);
1134 int dewey
= lst_dewey_number (lst
);
1135 int level
= lst_depth (lst
);
1137 gcc_assert (lst
&& father
&& dewey
>= 0 && level
>= 0);
1139 for (i
= dewey
; LST_SEQ (father
).iterate (i
, &l
); i
++)
1140 lst_update_scattering_under (l
, level
, i
);
1143 if (LST_LOOP_P (lst
))
1144 for (i
= 0; LST_SEQ (lst
).iterate (i
, &l
); i
++)
1145 lst_update_scattering (l
);
1148 /* Inserts LST1 before LST2 if BEFORE is true; inserts LST1 after LST2
1149 if BEFORE is false. */
1152 lst_insert_in_sequence (lst_p lst1
, lst_p lst2
, bool before
)
1157 /* Do not insert empty loops. */
1158 if (!lst1
|| lst_empty_p (lst1
))
1161 father
= LST_LOOP_FATHER (lst2
);
1162 dewey
= lst_dewey_number (lst2
);
1164 gcc_assert (lst2
&& father
&& dewey
>= 0);
1166 LST_SEQ (father
).safe_insert (before
? dewey
: dewey
+ 1, lst1
);
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 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
)
1200 gcc_assert (lst
&& root
!= lst
);
1202 if (!LST_LOOP_P (root
))
1203 return new_lst_stmt (LST_PBB (root
));
1207 for (i
= 0; LST_SEQ (root
).iterate (i
, &l
); i
++)
1209 seq
.safe_push (lst_substitute_3 (l
, lst
, a
, b
, c
));
1212 if (!lst_empty_p (a
))
1213 seq
.safe_push (copy_lst (a
));
1214 if (!lst_empty_p (b
))
1215 seq
.safe_push (copy_lst (b
));
1216 if (!lst_empty_p (c
))
1217 seq
.safe_push (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; LST_SEQ (loop
).iterate (i
, &l
);)
1255 before
= lst_remove_all_before_including_pbb (l
, pbb
, before
);
1257 if (LST_SEQ (l
).length () == 0)
1259 LST_SEQ (loop
).ordered_remove (i
);
1269 if (LST_PBB (l
) == pbb
)
1272 LST_SEQ (loop
).ordered_remove (i
);
1275 else if (LST_PBB (l
) == pbb
)
1278 LST_SEQ (loop
).ordered_remove (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; LST_SEQ (loop
).iterate (i
, &l
);)
1304 before
= lst_remove_all_before_excluding_pbb (l
, pbb
, before
);
1306 if (LST_SEQ (l
).length () == 0)
1308 LST_SEQ (loop
).ordered_remove (i
);
1317 if (before
&& LST_PBB (l
) != pbb
)
1319 LST_SEQ (loop
).ordered_remove (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
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:
1366 /* The context used internally by ISL. */
1369 /* The original dependence relations:
1370 RAW are read after write dependences,
1371 WAR are write after read dependences,
1372 WAW are write after write dependences. */
1373 isl_union_map
*must_raw
, *may_raw
, *must_raw_no_source
, *may_raw_no_source
,
1374 *must_war
, *may_war
, *must_war_no_source
, *may_war_no_source
,
1375 *must_waw
, *may_waw
, *must_waw_no_source
, *may_waw_no_source
;
1377 /* True when the scop has been converted to its polyhedral
1382 #define SCOP_BBS(S) (S->bbs)
1383 #define SCOP_REGION(S) ((sese) S->region)
1384 #define SCOP_CONTEXT(S) (NULL)
1385 #define SCOP_ORIGINAL_SCHEDULE(S) (S->original_schedule)
1386 #define SCOP_TRANSFORMED_SCHEDULE(S) (S->transformed_schedule)
1387 #define SCOP_SAVED_SCHEDULE(S) (S->saved_schedule)
1388 #define POLY_SCOP_P(S) (S->poly_scop_p)
1390 extern scop_p
new_scop (void *);
1391 extern void free_scop (scop_p
);
1392 extern void free_scops (vec
<scop_p
> );
1393 extern void print_generated_program (FILE *, scop_p
);
1394 extern void debug_generated_program (scop_p
);
1395 extern void print_scattering_function (FILE *, poly_bb_p
, int);
1396 extern void print_scattering_functions (FILE *, scop_p
, int);
1397 extern void debug_scattering_function (poly_bb_p
, int);
1398 extern void debug_scattering_functions (scop_p
, int);
1399 extern int scop_max_loop_depth (scop_p
);
1400 extern int unify_scattering_dimensions (scop_p
);
1401 extern bool apply_poly_transforms (scop_p
);
1402 extern bool graphite_legal_transform (scop_p
);
1404 /* Set the region of SCOP to REGION. */
1407 scop_set_region (scop_p scop
, void *region
)
1409 scop
->region
= region
;
1412 /* Returns the number of parameters for SCOP. */
1414 static inline graphite_dim_t
1415 scop_nb_params (scop_p scop
)
1417 return scop
->nb_params
;
1420 /* Set the number of params of SCOP to NB_PARAMS. */
1423 scop_set_nb_params (scop_p scop
, graphite_dim_t nb_params
)
1425 scop
->nb_params
= nb_params
;
1428 /* Allocates a new empty poly_scattering structure. */
1430 static inline poly_scattering_p
1431 poly_scattering_new (void)
1433 poly_scattering_p res
= XNEW (struct poly_scattering
);
1435 res
->nb_local_variables
= 0;
1436 res
->nb_scattering
= 0;
1440 /* Free a poly_scattering structure. */
1443 poly_scattering_free (poly_scattering_p s
)
1448 /* Copies S and return a new scattering. */
1450 static inline poly_scattering_p
1451 poly_scattering_copy (poly_scattering_p s
)
1453 poly_scattering_p res
= poly_scattering_new ();
1455 res
->nb_local_variables
= s
->nb_local_variables
;
1456 res
->nb_scattering
= s
->nb_scattering
;
1460 /* Saves the transformed scattering of PBB. */
1463 store_scattering_pbb (poly_bb_p pbb
)
1465 isl_map_free (pbb
->saved
);
1466 pbb
->saved
= isl_map_copy (pbb
->transformed
);
1469 /* Stores the SCOP_TRANSFORMED_SCHEDULE to SCOP_SAVED_SCHEDULE. */
1472 store_lst_schedule (scop_p scop
)
1474 if (SCOP_SAVED_SCHEDULE (scop
))
1475 free_lst (SCOP_SAVED_SCHEDULE (scop
));
1477 SCOP_SAVED_SCHEDULE (scop
) = copy_lst (SCOP_TRANSFORMED_SCHEDULE (scop
));
1480 /* Restores the SCOP_TRANSFORMED_SCHEDULE from SCOP_SAVED_SCHEDULE. */
1483 restore_lst_schedule (scop_p scop
)
1485 if (SCOP_TRANSFORMED_SCHEDULE (scop
))
1486 free_lst (SCOP_TRANSFORMED_SCHEDULE (scop
));
1488 SCOP_TRANSFORMED_SCHEDULE (scop
) = copy_lst (SCOP_SAVED_SCHEDULE (scop
));
1491 /* Saves the scattering for all the pbbs in the SCOP. */
1494 store_scattering (scop_p scop
)
1499 for (i
= 0; SCOP_BBS (scop
).iterate (i
, &pbb
); i
++)
1500 store_scattering_pbb (pbb
);
1502 store_lst_schedule (scop
);
1505 /* Restores the scattering of PBB. */
1508 restore_scattering_pbb (poly_bb_p pbb
)
1510 gcc_assert (pbb
->saved
);
1512 isl_map_free (pbb
->transformed
);
1513 pbb
->transformed
= isl_map_copy (pbb
->saved
);
1516 /* Restores the scattering for all the pbbs in the SCOP. */
1519 restore_scattering (scop_p scop
)
1524 for (i
= 0; SCOP_BBS (scop
).iterate (i
, &pbb
); i
++)
1525 restore_scattering_pbb (pbb
);
1527 restore_lst_schedule (scop
);
1530 bool graphite_legal_transform (scop_p
);
1531 isl_map
*reverse_loop_at_level (poly_bb_p
, int);
1532 isl_union_map
*reverse_loop_for_pbbs (scop_p
, vec
<poly_bb_p
> , int);
1533 __isl_give isl_union_map
*extend_schedule (__isl_take isl_union_map
*);
1537 compute_deps (scop_p scop
, vec
<poly_bb_p
> pbbs
,
1538 isl_union_map
**must_raw
,
1539 isl_union_map
**may_raw
,
1540 isl_union_map
**must_raw_no_source
,
1541 isl_union_map
**may_raw_no_source
,
1542 isl_union_map
**must_war
,
1543 isl_union_map
**may_war
,
1544 isl_union_map
**must_war_no_source
,
1545 isl_union_map
**may_war_no_source
,
1546 isl_union_map
**must_waw
,
1547 isl_union_map
**may_waw
,
1548 isl_union_map
**must_waw_no_source
,
1549 isl_union_map
**may_waw_no_source
);
1552 scop_get_dependences (scop_p scop
);
1555 carries_deps (__isl_keep isl_union_map
*schedule
,
1556 __isl_keep isl_union_map
*deps
,