Mercurial > hg > CbC > CbC_gcc

comparison gcc/graphite-poly.h @ 67:f6334be47118

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
author nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
date Tue, 22 Mar 2011 17:18:12 +0900
parents b7f97abdc517
children
comparison
equal deleted inserted replaced
65:65488c3d617d 67:f6334be47118
130 130
131 The scalar data access "m" is represented as an array with zero subscript 131 The scalar data access "m" is represented as an array with zero subscript
132 dimensions. 132 dimensions.
133 133
134 | i j k a 1 134 | i j k a 1
135 | 0 0 0 -1 15 = 0 */ 135 | 0 0 0 -1 15 = 0
136
137 The difference between the graphite internal format for access data and
138 the OpenSop format is in the order of columns.
139 Instead of having:
140
141 | i j k a s0 s1 1
142 | 0 0 0 1 0 0 -5 = 0
143 |-1 0 0 0 1 0 0 = 0
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
149
150 In OpenScop we have:
151
152 | a s0 s1 i j k 1
153 | 1 0 0 0 0 0 -5 = 0
154 | 0 1 0 -1 0 0 0 = 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
160
161 The OpenScop access function is printed as follows:
162
163 | 1 # The number of disjunct components in a union of access functions.
164 | R C O I L P # Described bellow.
165 | a s0 s1 i j k 1
166 | 1 0 0 0 0 0 -5 = 0
167 | 0 1 0 -1 0 0 0 = 0
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
173
174 Where:
175 - R: Number of rows.
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.
181
182 In the example, the vector "R C O I L P" is "7 7 3 2 0 1". */
136 ppl_Pointset_Powerset_C_Polyhedron_t accesses; 183 ppl_Pointset_Powerset_C_Polyhedron_t accesses;
137 184
138 /* Data reference's base object set number, we must assure 2 pdrs are in the 185 /* Data reference's base object set number, we must assure 2 pdrs are in the
139 same base object set before dependency checking. */ 186 same base object set before dependency checking. */
140 int dr_base_object_set; 187 int dr_base_object_set;
252 the same base array, and the same access functions. */ 299 the same base array, and the same access functions. */
253 300
254 static inline bool 301 static inline bool
255 same_pdr_p (poly_dr_p pdr1, poly_dr_p pdr2) 302 same_pdr_p (poly_dr_p pdr1, poly_dr_p pdr2)
256 { 303 {
257 return PDR_TYPE (pdr1) == PDR_TYPE (pdr2) 304 return PDR_NB_SUBSCRIPTS (pdr1) == PDR_NB_SUBSCRIPTS (pdr2)
258 && PDR_NB_SUBSCRIPTS (pdr1) == PDR_NB_SUBSCRIPTS (pdr2)
259 && PDR_BASE_OBJECT_SET (pdr1) == PDR_BASE_OBJECT_SET (pdr2); 305 && PDR_BASE_OBJECT_SET (pdr1) == PDR_BASE_OBJECT_SET (pdr2);
260 } 306 }
261 307
262 typedef struct poly_scattering *poly_scattering_p; 308 typedef struct poly_scattering *poly_scattering_p;
263 309
340 #define PBB_NB_LOCAL_VARIABLES(PBB) (PBB->transformed->nb_local_variables) 386 #define PBB_NB_LOCAL_VARIABLES(PBB) (PBB->transformed->nb_local_variables)
341 #define PBB_NB_SCATTERING_TRANSFORM(PBB) (PBB->transformed->nb_scattering) 387 #define PBB_NB_SCATTERING_TRANSFORM(PBB) (PBB->transformed->nb_scattering)
342 #define PBB_PDR_DUPLICATES_REMOVED(PBB) (PBB->pdr_duplicates_removed) 388 #define PBB_PDR_DUPLICATES_REMOVED(PBB) (PBB->pdr_duplicates_removed)
343 #define PBB_IS_REDUCTION(PBB) (PBB->is_reduction) 389 #define PBB_IS_REDUCTION(PBB) (PBB->is_reduction)
344 390
345 extern void new_poly_bb (scop_p, void *, bool); 391 extern poly_bb_p new_poly_bb (scop_p, void *);
346 extern void free_poly_bb (poly_bb_p); 392 extern void free_poly_bb (poly_bb_p);
347 extern void debug_loop_vec (poly_bb_p); 393 extern void debug_loop_vec (poly_bb_p);
348 extern void schedule_to_scattering (poly_bb_p, int); 394 extern void schedule_to_scattering (poly_bb_p, int);
349 extern void print_pbb_domain (FILE *, poly_bb_p, int); 395 extern void print_pbb_domain (FILE *, poly_bb_p, int);
350 extern void print_pbb (FILE *, poly_bb_p, int); 396 extern void print_pbb (FILE *, poly_bb_p, int);
363 extern void print_iteration_domain (FILE *, poly_bb_p, int); 409 extern void print_iteration_domain (FILE *, poly_bb_p, int);
364 extern void print_iteration_domains (FILE *, scop_p, int); 410 extern void print_iteration_domains (FILE *, scop_p, int);
365 extern void debug_iteration_domain (poly_bb_p, int); 411 extern void debug_iteration_domain (poly_bb_p, int);
366 extern void debug_iteration_domains (scop_p, int); 412 extern void debug_iteration_domains (scop_p, int);
367 extern bool scop_do_interchange (scop_p); 413 extern bool scop_do_interchange (scop_p);
368 extern bool scop_do_strip_mine (scop_p); 414 extern bool scop_do_strip_mine (scop_p, int);
369 extern bool scop_do_block (scop_p); 415 extern bool scop_do_block (scop_p);
370 extern void pbb_number_of_iterations (poly_bb_p, graphite_dim_t, mpz_t); 416 extern bool flatten_all_loops (scop_p);
371 extern void pbb_number_of_iterations_at_time (poly_bb_p, graphite_dim_t, mpz_t); 417 extern void pbb_number_of_iterations_at_time (poly_bb_p, graphite_dim_t, mpz_t);
372 extern void pbb_remove_duplicate_pdrs (poly_bb_p); 418 extern void pbb_remove_duplicate_pdrs (poly_bb_p);
373 419
374 /* Return the number of write data references in PBB. */ 420 /* Return the number of write data references in PBB. */
375 421
385 res++; 431 res++;
386 432
387 return res; 433 return res;
388 } 434 }
389 435
436 /* Returns a gimple_bb from BB. */
437
438 static inline gimple_bb_p
439 gbb_from_bb (basic_block bb)
440 {
441 return (gimple_bb_p) bb->aux;
442 }
443
444 /* The poly_bb of the BB. */
445
446 static inline poly_bb_p
447 pbb_from_bb (basic_block bb)
448 {
449 return GBB_PBB (gbb_from_bb (bb));
450 }
451
390 /* The basic block of the PBB. */ 452 /* The basic block of the PBB. */
453
391 static inline basic_block 454 static inline basic_block
392 pbb_bb (poly_bb_p pbb) 455 pbb_bb (poly_bb_p pbb)
393 { 456 {
394 return GBB_BB (PBB_BLACK_BOX (pbb)); 457 return GBB_BB (PBB_BLACK_BOX (pbb));
395 } 458 }
793 return -1; 856 return -1;
794 857
795 if (!LST_LOOP_FATHER (lst)) 858 if (!LST_LOOP_FATHER (lst))
796 return 0; 859 return 0;
797 860
798 for (i = 0; VEC_iterate (lst_p, LST_SEQ (LST_LOOP_FATHER (lst)), i, l); i++) 861 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (LST_LOOP_FATHER (lst)), i, l)
799 if (l == lst) 862 if (l == lst)
800 return i; 863 return i;
801 864
802 return -1; 865 return -1;
803 } 866 }
895 loop = LST_LOOP_FATHER (loop); 958 loop = LST_LOOP_FATHER (loop);
896 959
897 return loop; 960 return loop;
898 } 961 }
899 962
900 /* Return the first lst representing a PBB statement in LST. */ 963 /* Return the first LST representing a PBB statement in LST. */
901 964
902 static inline lst_p 965 static inline lst_p
903 lst_find_first_pbb (lst_p lst) 966 lst_find_first_pbb (lst_p lst)
904 { 967 {
905 int i; 968 int i;
919 } 982 }
920 983
921 return NULL; 984 return NULL;
922 } 985 }
923 986
924 /* Returns true when LST is a loop that does not contains 987 /* Returns true when LST is a loop that does not contain
925 statements. */ 988 statements. */
926 989
927 static inline bool 990 static inline bool
928 lst_empty_p (lst_p lst) 991 lst_empty_p (lst_p lst)
929 { 992 {
930 return !lst_find_first_pbb (lst); 993 return !lst_find_first_pbb (lst);
931 } 994 }
932 995
933 /* Return the last lst representing a PBB statement in LST. */ 996 /* Return the last LST representing a PBB statement in LST. */
934 997
935 static inline lst_p 998 static inline lst_p
936 lst_find_last_pbb (lst_p lst) 999 lst_find_last_pbb (lst_p lst)
937 { 1000 {
938 int i; 1001 int i;
1010 1073
1011 gcc_assert (lst && father && dewey >= 0); 1074 gcc_assert (lst && father && dewey >= 0);
1012 1075
1013 VEC_ordered_remove (lst_p, LST_SEQ (father), dewey); 1076 VEC_ordered_remove (lst_p, LST_SEQ (father), dewey);
1014 LST_LOOP_FATHER (lst) = NULL; 1077 LST_LOOP_FATHER (lst) = NULL;
1078 }
1079
1080 /* Removes the loop LST and inline its body in the father loop. */
1081
1082 static inline void
1083 lst_remove_loop_and_inline_stmts_in_loop_father (lst_p lst)
1084 {
1085 lst_p l, father = LST_LOOP_FATHER (lst);
1086 int i, dewey = lst_dewey_number (lst);
1087
1088 gcc_assert (lst && father && dewey >= 0);
1089
1090 VEC_ordered_remove (lst_p, LST_SEQ (father), dewey);
1091 LST_LOOP_FATHER (lst) = NULL;
1092
1093 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
1094 {
1095 VEC_safe_insert (lst_p, heap, LST_SEQ (father), dewey + i, l);
1096 LST_LOOP_FATHER (l) = father;
1097 }
1098 }
1099
1100 /* Sets NITER to the upper bound approximation of the number of
1101 iterations of loop LST. */
1102
1103 static inline void
1104 lst_niter_for_loop (lst_p lst, mpz_t niter)
1105 {
1106 int depth = lst_depth (lst);
1107 poly_bb_p pbb = LST_PBB (lst_find_first_pbb (lst));
1108
1109 gcc_assert (LST_LOOP_P (lst));
1110 pbb_number_of_iterations_at_time (pbb, psct_dynamic_dim (pbb, depth), niter);
1015 } 1111 }
1016 1112
1017 /* Updates the scattering of PBB to be at the DEWEY number in the loop 1113 /* Updates the scattering of PBB to be at the DEWEY number in the loop
1018 at depth LEVEL. */ 1114 at depth LEVEL. */
1019 1115
1057 lst_update_scattering_under (l, level, dewey); 1153 lst_update_scattering_under (l, level, dewey);
1058 else 1154 else
1059 pbb_update_scattering (LST_PBB (lst), level, dewey); 1155 pbb_update_scattering (LST_PBB (lst), level, dewey);
1060 } 1156 }
1061 1157
1062 /* Updates the scattering of all the PBBs under LST and in sequence 1158 /* Updates the all the scattering levels of all the PBBs under
1063 with LST. */ 1159 LST. */
1064 1160
1065 static inline void 1161 static inline void
1066 lst_update_scattering_seq (lst_p lst) 1162 lst_update_scattering (lst_p lst)
1067 { 1163 {
1068 int i; 1164 int i;
1069 lst_p l; 1165 lst_p l;
1070 lst_p father = LST_LOOP_FATHER (lst); 1166
1071 int dewey = lst_dewey_number (lst); 1167 if (!lst)
1072 int level = lst_depth (lst);
1073
1074 gcc_assert (lst && father && dewey >= 0 && level >= 0);
1075
1076 for (i = dewey; VEC_iterate (lst_p, LST_SEQ (father), i, l); i++)
1077 lst_update_scattering_under (l, level, i);
1078 }
1079
1080 /* Updates the all the scattering levels of all the PBBs under
1081 LST. */
1082
1083 static inline void
1084 lst_update_scattering (lst_p lst)
1085 {
1086 int i;
1087 lst_p l;
1088
1089 if (!lst || !LST_LOOP_P (lst))
1090 return; 1168 return;
1091 1169
1092 if (LST_LOOP_FATHER (lst)) 1170 if (LST_LOOP_FATHER (lst))
1093 lst_update_scattering_seq (lst); 1171 {
1094 1172 lst_p father = LST_LOOP_FATHER (lst);
1095 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++) 1173 int dewey = lst_dewey_number (lst);
1096 lst_update_scattering (l); 1174 int level = lst_depth (lst);
1175
1176 gcc_assert (lst && father && dewey >= 0 && level >= 0);
1177
1178 for (i = dewey; VEC_iterate (lst_p, LST_SEQ (father), i, l); i++)
1179 lst_update_scattering_under (l, level, i);
1180 }
1181
1182 if (LST_LOOP_P (lst))
1183 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
1184 lst_update_scattering (l);
1097 } 1185 }
1098 1186
1099 /* Inserts LST1 before LST2 if BEFORE is true; inserts LST1 after LST2 1187 /* Inserts LST1 before LST2 if BEFORE is true; inserts LST1 after LST2
1100 if BEFORE is false. */ 1188 if BEFORE is false. */
1101 1189
1344 extern void debug_scattering_functions (scop_p, int); 1432 extern void debug_scattering_functions (scop_p, int);
1345 extern int scop_max_loop_depth (scop_p); 1433 extern int scop_max_loop_depth (scop_p);
1346 extern int unify_scattering_dimensions (scop_p); 1434 extern int unify_scattering_dimensions (scop_p);
1347 extern bool apply_poly_transforms (scop_p); 1435 extern bool apply_poly_transforms (scop_p);
1348 extern bool graphite_legal_transform (scop_p); 1436 extern bool graphite_legal_transform (scop_p);
1437 extern void cloog_checksum (scop_p);
1349 1438
1350 /* Set the region of SCOP to REGION. */ 1439 /* Set the region of SCOP to REGION. */
1351 1440
1352 static inline void 1441 static inline void
1353 scop_set_region (scop_p scop, void *region) 1442 scop_set_region (scop_p scop, void *region)