Mercurial > hg > CbC > CbC_gcc
comparison gcc/graphite-poly.h @ 55:77e2b8dfacca gcc-4.4.5
update it from 4.4.3 to 4.5.0
author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
---|---|
date | Fri, 12 Feb 2010 23:39:51 +0900 |
parents | |
children | b7f97abdc517 |
comparison
equal
deleted
inserted
replaced
52:c156f1bd5cd9 | 55:77e2b8dfacca |
---|---|
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>. | |
5 | |
6 This file is part of GCC. | |
7 | |
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) | |
11 any later version. | |
12 | |
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. | |
17 | |
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/>. */ | |
21 | |
22 #ifndef GCC_GRAPHITE_POLY_H | |
23 #define GCC_GRAPHITE_POLY_H | |
24 | |
25 typedef struct poly_dr *poly_dr_p; | |
26 DEF_VEC_P(poly_dr_p); | |
27 DEF_VEC_ALLOC_P (poly_dr_p, heap); | |
28 | |
29 typedef struct poly_bb *poly_bb_p; | |
30 DEF_VEC_P(poly_bb_p); | |
31 DEF_VEC_ALLOC_P (poly_bb_p, heap); | |
32 | |
33 typedef struct scop *scop_p; | |
34 DEF_VEC_P(scop_p); | |
35 DEF_VEC_ALLOC_P (scop_p, heap); | |
36 | |
37 typedef ppl_dimension_type graphite_dim_t; | |
38 | |
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); | |
42 | |
43 /* A data reference can write or read some memory or we | |
44 just know it may write some memory. */ | |
45 enum poly_dr_type | |
46 { | |
47 PDR_READ, | |
48 /* PDR_MAY_READs are represented using PDR_READS. This does not | |
49 limit the expressiveness. */ | |
50 PDR_WRITE, | |
51 PDR_MAY_WRITE | |
52 }; | |
53 | |
54 struct poly_dr | |
55 { | |
56 /* An identifier for this PDR. */ | |
57 int id; | |
58 | |
59 /* The number of data refs identical to this one in the PBB. */ | |
60 int nb_refs; | |
61 | |
62 /* A pointer to compiler's data reference description. */ | |
63 void *compiler_dr; | |
64 | |
65 /* A pointer to the PBB that contains this data reference. */ | |
66 poly_bb_p pbb; | |
67 | |
68 enum poly_dr_type type; | |
69 | |
70 /* The access polyhedron contains the polyhedral space this data | |
71 reference will access. | |
72 | |
73 The polyhedron contains these dimensions: | |
74 | |
75 - The alias set (a): | |
76 Every memory access is classified in at least one alias set. | |
77 | |
78 - The subscripts (s_0, ..., s_n): | |
79 The memory is accessed using zero or more subscript dimensions. | |
80 | |
81 - The iteration domain (variables and parameters) | |
82 | |
83 Do not hardcode the dimensions. Use the following accessor functions: | |
84 - pdr_alias_set_dim | |
85 - pdr_subscript_dim | |
86 - pdr_iterator_dim | |
87 - pdr_parameter_dim | |
88 | |
89 Example: | |
90 | |
91 | int A[1335][123]; | |
92 | int *p = malloc (); | |
93 | | |
94 | k = ... | |
95 | for i | |
96 | { | |
97 | if (unknown_function ()) | |
98 | p = A; | |
99 | ... = p[?][?]; | |
100 | for j | |
101 | A[i][j+k] = m; | |
102 | } | |
103 | |
104 The data access A[i][j+k] in alias set "5" is described like this: | |
105 | |
106 | i j k a s0 s1 1 | |
107 | 0 0 0 1 0 0 -5 = 0 | |
108 |-1 0 0 0 1 0 0 = 0 | |
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 | |
114 | |
115 The pointer "*p" in alias set "5" and "7" is described as a union of | |
116 polyhedron: | |
117 | |
118 | |
119 | i k a s0 1 | |
120 | 0 0 1 0 -5 = 0 | |
121 | 0 0 0 1 0 >= 0 | |
122 | |
123 "or" | |
124 | |
125 | i k a s0 1 | |
126 | 0 0 1 0 -7 = 0 | |
127 | 0 0 0 1 0 >= 0 | |
128 | |
129 "*p" accesses all of the object allocated with 'malloc'. | |
130 | |
131 The scalar data access "m" is represented as an array with zero subscript | |
132 dimensions. | |
133 | |
134 | i j k a 1 | |
135 | 0 0 0 -1 15 = 0 */ | |
136 ppl_Pointset_Powerset_C_Polyhedron_t accesses; | |
137 | |
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; | |
141 | |
142 /* The number of subscripts. */ | |
143 graphite_dim_t nb_subscripts; | |
144 }; | |
145 | |
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) | |
154 | |
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); | |
161 | |
162 /* The dimension of the PDR_ACCESSES polyhedron of PDR. */ | |
163 | |
164 static inline ppl_dimension_type | |
165 pdr_dim (poly_dr_p pdr) | |
166 { | |
167 ppl_dimension_type dim; | |
168 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PDR_ACCESSES (pdr), | |
169 &dim); | |
170 return dim; | |
171 } | |
172 | |
173 /* The dimension of the iteration domain of the scop of PDR. */ | |
174 | |
175 static inline ppl_dimension_type | |
176 pdr_dim_iter_domain (poly_dr_p pdr) | |
177 { | |
178 return pbb_dim_iter_domain (PDR_PBB (pdr)); | |
179 } | |
180 | |
181 /* The number of parameters of the scop of PDR. */ | |
182 | |
183 static inline ppl_dimension_type | |
184 pdr_nb_params (poly_dr_p pdr) | |
185 { | |
186 return scop_nb_params (pdr_scop (pdr)); | |
187 } | |
188 | |
189 /* The dimension of the alias set in PDR. */ | |
190 | |
191 static inline ppl_dimension_type | |
192 pdr_alias_set_dim (poly_dr_p pdr) | |
193 { | |
194 poly_bb_p pbb = PDR_PBB (pdr); | |
195 | |
196 return pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb); | |
197 } | |
198 | |
199 /* The dimension in PDR containing subscript S. */ | |
200 | |
201 static inline ppl_dimension_type | |
202 pdr_subscript_dim (poly_dr_p pdr, graphite_dim_t s) | |
203 { | |
204 poly_bb_p pbb = PDR_PBB (pdr); | |
205 | |
206 return pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb) + 1 + s; | |
207 } | |
208 | |
209 /* The dimension in PDR containing the loop iterator ITER. */ | |
210 | |
211 static inline ppl_dimension_type | |
212 pdr_iterator_dim (poly_dr_p pdr ATTRIBUTE_UNUSED, graphite_dim_t iter) | |
213 { | |
214 return iter; | |
215 } | |
216 | |
217 /* The dimension in PDR containing parameter PARAM. */ | |
218 | |
219 static inline ppl_dimension_type | |
220 pdr_parameter_dim (poly_dr_p pdr, graphite_dim_t param) | |
221 { | |
222 poly_bb_p pbb = PDR_PBB (pdr); | |
223 | |
224 return pbb_dim_iter_domain (pbb) + param; | |
225 } | |
226 | |
227 /* Returns true when PDR is a "read". */ | |
228 | |
229 static inline bool | |
230 pdr_read_p (poly_dr_p pdr) | |
231 { | |
232 return PDR_TYPE (pdr) == PDR_READ; | |
233 } | |
234 | |
235 /* Returns true when PDR is a "write". */ | |
236 | |
237 static inline bool | |
238 pdr_write_p (poly_dr_p pdr) | |
239 { | |
240 return PDR_TYPE (pdr) == PDR_WRITE; | |
241 } | |
242 | |
243 /* Returns true when PDR is a "may write". */ | |
244 | |
245 static inline bool | |
246 pdr_may_write_p (poly_dr_p pdr) | |
247 { | |
248 return PDR_TYPE (pdr) == PDR_MAY_WRITE; | |
249 } | |
250 | |
251 /* Return true when PDR1 and PDR2 are similar data accesses: they have | |
252 the same base array, and the same access functions. */ | |
253 | |
254 static inline bool | |
255 same_pdr_p (poly_dr_p pdr1, poly_dr_p pdr2) | |
256 { | |
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); | |
260 } | |
261 | |
262 typedef struct poly_scattering *poly_scattering_p; | |
263 | |
264 struct poly_scattering | |
265 { | |
266 /* The scattering function containing the transformations. */ | |
267 ppl_Polyhedron_t scattering; | |
268 | |
269 /* The number of local variables. */ | |
270 int nb_local_variables; | |
271 | |
272 /* The number of scattering dimensions. */ | |
273 int nb_scattering; | |
274 }; | |
275 | |
276 /* POLY_BB represents a blackbox in the polyhedral model. */ | |
277 | |
278 struct poly_bb | |
279 { | |
280 void *black_box; | |
281 | |
282 scop_p scop; | |
283 | |
284 /* The iteration domain of this bb. | |
285 Example: | |
286 | |
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++) | |
290 S (i,j,k) | |
291 | |
292 Loop iterators: i, j, k | |
293 Parameters: a, b | |
294 | |
295 | i >= a - 7b + 8 | |
296 | i <= 3a + 13b + 20 | |
297 | j >= 2 | |
298 | j <= 2i + 5 | |
299 | k >= 0 | |
300 | k <= 5 | |
301 | |
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; | |
305 | |
306 /* The data references we access. */ | |
307 VEC (poly_dr_p, heap) *drs; | |
308 | |
309 /* The original scattering. */ | |
310 poly_scattering_p original; | |
311 | |
312 /* The transformed scattering. */ | |
313 poly_scattering_p transformed; | |
314 | |
315 /* A copy of the transformed scattering. */ | |
316 poly_scattering_p saved; | |
317 | |
318 /* True when the PDR duplicates have already been removed. */ | |
319 bool pdr_duplicates_removed; | |
320 | |
321 /* True when this PBB contains only a reduction statement. */ | |
322 bool is_reduction; | |
323 }; | |
324 | |
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) | |
338 | |
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); | |
365 | |
366 /* Return the number of write data references in PBB. */ | |
367 | |
368 static inline int | |
369 number_of_write_pdrs (poly_bb_p pbb) | |
370 { | |
371 int res = 0; | |
372 int i; | |
373 poly_dr_p pdr; | |
374 | |
375 for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++) | |
376 if (PDR_TYPE (pdr) == PDR_WRITE) | |
377 res++; | |
378 | |
379 return res; | |
380 } | |
381 | |
382 /* The index of the PBB. */ | |
383 | |
384 static inline int | |
385 pbb_index (poly_bb_p pbb) | |
386 { | |
387 return GBB_BB (PBB_BLACK_BOX (pbb))->index; | |
388 } | |
389 | |
390 /* The loop of the PBB. */ | |
391 | |
392 static inline loop_p | |
393 pbb_loop (poly_bb_p pbb) | |
394 { | |
395 return gbb_loop (PBB_BLACK_BOX (pbb)); | |
396 } | |
397 | |
398 /* The scop that contains the PDR. */ | |
399 | |
400 static inline scop_p | |
401 pdr_scop (poly_dr_p pdr) | |
402 { | |
403 return PBB_SCOP (PDR_PBB (pdr)); | |
404 } | |
405 | |
406 /* Set black box of PBB to BLACKBOX. */ | |
407 | |
408 static inline void | |
409 pbb_set_black_box (poly_bb_p pbb, void *black_box) | |
410 { | |
411 pbb->black_box = black_box; | |
412 } | |
413 | |
414 /* The number of loops around PBB: the dimension of the iteration | |
415 domain. */ | |
416 | |
417 static inline graphite_dim_t | |
418 pbb_dim_iter_domain (const struct poly_bb *pbb) | |
419 { | |
420 scop_p scop = PBB_SCOP (pbb); | |
421 ppl_dimension_type dim; | |
422 | |
423 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb), &dim); | |
424 return dim - scop_nb_params (scop); | |
425 } | |
426 | |
427 /* The number of params defined in PBB. */ | |
428 | |
429 static inline graphite_dim_t | |
430 pbb_nb_params (const struct poly_bb *pbb) | |
431 { | |
432 scop_p scop = PBB_SCOP (pbb); | |
433 | |
434 return scop_nb_params (scop); | |
435 } | |
436 | |
437 /* The number of scattering dimensions in the SCATTERING polyhedron | |
438 of a PBB for a given SCOP. */ | |
439 | |
440 static inline graphite_dim_t | |
441 pbb_nb_scattering_orig (const struct poly_bb *pbb) | |
442 { | |
443 return 2 * pbb_dim_iter_domain (pbb) + 1; | |
444 } | |
445 | |
446 /* The number of scattering dimensions in PBB. */ | |
447 | |
448 static inline graphite_dim_t | |
449 pbb_nb_scattering_transform (const struct poly_bb *pbb) | |
450 { | |
451 return PBB_NB_SCATTERING_TRANSFORM (pbb); | |
452 } | |
453 | |
454 /* The number of dynamic scattering dimensions in PBB. */ | |
455 | |
456 static inline graphite_dim_t | |
457 pbb_nb_dynamic_scattering_transform (const struct poly_bb *pbb) | |
458 { | |
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; | |
463 } | |
464 | |
465 /* Returns the number of local variables used in the transformed | |
466 scattering polyhedron of PBB. */ | |
467 | |
468 static inline graphite_dim_t | |
469 pbb_nb_local_vars (const struct poly_bb *pbb) | |
470 { | |
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); | |
474 } | |
475 | |
476 /* The dimension in the domain of PBB containing the iterator ITER. */ | |
477 | |
478 static inline ppl_dimension_type | |
479 pbb_iterator_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t iter) | |
480 { | |
481 return iter; | |
482 } | |
483 | |
484 /* The dimension in the domain of PBB containing the iterator ITER. */ | |
485 | |
486 static inline ppl_dimension_type | |
487 pbb_parameter_dim (poly_bb_p pbb, graphite_dim_t param) | |
488 { | |
489 return param | |
490 + pbb_dim_iter_domain (pbb); | |
491 } | |
492 | |
493 /* The dimension in the original scattering polyhedron of PBB | |
494 containing the scattering iterator SCATTER. */ | |
495 | |
496 static inline ppl_dimension_type | |
497 psco_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t scatter) | |
498 { | |
499 gcc_assert (scatter < pbb_nb_scattering_orig (pbb)); | |
500 return scatter; | |
501 } | |
502 | |
503 /* The dimension in the transformed scattering polyhedron of PBB | |
504 containing the scattering iterator SCATTER. */ | |
505 | |
506 static inline ppl_dimension_type | |
507 psct_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t scatter) | |
508 { | |
509 gcc_assert (scatter <= pbb_nb_scattering_transform (pbb)); | |
510 return scatter; | |
511 } | |
512 | |
513 ppl_dimension_type psct_scattering_dim_for_loop_depth (poly_bb_p, | |
514 graphite_dim_t); | |
515 | |
516 /* The dimension in the transformed scattering polyhedron of PBB of | |
517 the local variable LV. */ | |
518 | |
519 static inline ppl_dimension_type | |
520 psct_local_var_dim (poly_bb_p pbb, graphite_dim_t lv) | |
521 { | |
522 gcc_assert (lv <= pbb_nb_local_vars (pbb)); | |
523 return lv + pbb_nb_scattering_transform (pbb); | |
524 } | |
525 | |
526 /* The dimension in the original scattering polyhedron of PBB | |
527 containing the loop iterator ITER. */ | |
528 | |
529 static inline ppl_dimension_type | |
530 psco_iterator_dim (poly_bb_p pbb, graphite_dim_t iter) | |
531 { | |
532 gcc_assert (iter < pbb_dim_iter_domain (pbb)); | |
533 return iter + pbb_nb_scattering_orig (pbb); | |
534 } | |
535 | |
536 /* The dimension in the transformed scattering polyhedron of PBB | |
537 containing the loop iterator ITER. */ | |
538 | |
539 static inline ppl_dimension_type | |
540 psct_iterator_dim (poly_bb_p pbb, graphite_dim_t iter) | |
541 { | |
542 gcc_assert (iter < pbb_dim_iter_domain (pbb)); | |
543 return iter | |
544 + pbb_nb_scattering_transform (pbb) | |
545 + pbb_nb_local_vars (pbb); | |
546 } | |
547 | |
548 /* The dimension in the original scattering polyhedron of PBB | |
549 containing parameter PARAM. */ | |
550 | |
551 static inline ppl_dimension_type | |
552 psco_parameter_dim (poly_bb_p pbb, graphite_dim_t param) | |
553 { | |
554 gcc_assert (param < pbb_nb_params (pbb)); | |
555 return param | |
556 + pbb_nb_scattering_orig (pbb) | |
557 + pbb_dim_iter_domain (pbb); | |
558 } | |
559 | |
560 /* The dimension in the transformed scattering polyhedron of PBB | |
561 containing parameter PARAM. */ | |
562 | |
563 static inline ppl_dimension_type | |
564 psct_parameter_dim (poly_bb_p pbb, graphite_dim_t param) | |
565 { | |
566 gcc_assert (param < pbb_nb_params (pbb)); | |
567 return param | |
568 + pbb_nb_scattering_transform (pbb) | |
569 + pbb_nb_local_vars (pbb) | |
570 + pbb_dim_iter_domain (pbb); | |
571 } | |
572 | |
573 /* The scattering dimension of PBB corresponding to the dynamic level | |
574 LEVEL. */ | |
575 | |
576 static inline ppl_dimension_type | |
577 psct_dynamic_dim (poly_bb_p pbb, graphite_dim_t level) | |
578 { | |
579 graphite_dim_t result = 1 + 2 * level; | |
580 | |
581 gcc_assert (result < pbb_nb_scattering_transform (pbb)); | |
582 return result; | |
583 } | |
584 | |
585 /* The scattering dimension of PBB corresponding to the static | |
586 sequence of the loop level LEVEL. */ | |
587 | |
588 static inline ppl_dimension_type | |
589 psct_static_dim (poly_bb_p pbb, graphite_dim_t level) | |
590 { | |
591 graphite_dim_t result = 2 * level; | |
592 | |
593 gcc_assert (result < pbb_nb_scattering_transform (pbb)); | |
594 return result; | |
595 } | |
596 | |
597 /* Adds to the transformed scattering polyhedron of PBB a new local | |
598 variable and returns its index. */ | |
599 | |
600 static inline graphite_dim_t | |
601 psct_add_local_variable (poly_bb_p pbb) | |
602 { | |
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; | |
607 return nlv; | |
608 } | |
609 | |
610 /* Adds a dimension to the transformed scattering polyhedron of PBB at | |
611 INDEX. */ | |
612 | |
613 static inline void | |
614 psct_add_scattering_dimension (poly_bb_p pbb, ppl_dimension_type index) | |
615 { | |
616 gcc_assert (index < pbb_nb_scattering_transform (pbb)); | |
617 | |
618 ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb), index, 1); | |
619 PBB_NB_SCATTERING_TRANSFORM (pbb) += 1; | |
620 } | |
621 | |
622 typedef struct lst *lst_p; | |
623 DEF_VEC_P(lst_p); | |
624 DEF_VEC_ALLOC_P (lst_p, heap); | |
625 | |
626 /* Loops and Statements Tree. */ | |
627 struct lst { | |
628 | |
629 /* LOOP_P is true when an LST node is a loop. */ | |
630 bool loop_p; | |
631 | |
632 /* A pointer to the loop that contains this node. */ | |
633 lst_p loop_father; | |
634 | |
635 /* Loop nodes contain a sequence SEQ of LST nodes, statements | |
636 contain a pointer to their polyhedral representation PBB. */ | |
637 union { | |
638 poly_bb_p pbb; | |
639 VEC (lst_p, heap) *seq; | |
640 } node; | |
641 }; | |
642 | |
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) | |
647 | |
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); | |
652 | |
653 /* Creates a new LST loop with SEQ. */ | |
654 | |
655 static inline lst_p | |
656 new_lst_loop (VEC (lst_p, heap) *seq) | |
657 { | |
658 lst_p lst = XNEW (struct lst); | |
659 int i; | |
660 lst_p l; | |
661 | |
662 LST_LOOP_P (lst) = true; | |
663 LST_SEQ (lst) = seq; | |
664 LST_LOOP_FATHER (lst) = NULL; | |
665 | |
666 for (i = 0; VEC_iterate (lst_p, seq, i, l); i++) | |
667 LST_LOOP_FATHER (l) = lst; | |
668 | |
669 return lst; | |
670 } | |
671 | |
672 /* Creates a new LST statement with PBB. */ | |
673 | |
674 static inline lst_p | |
675 new_lst_stmt (poly_bb_p pbb) | |
676 { | |
677 lst_p lst = XNEW (struct lst); | |
678 | |
679 LST_LOOP_P (lst) = false; | |
680 LST_PBB (lst) = pbb; | |
681 LST_LOOP_FATHER (lst) = NULL; | |
682 return lst; | |
683 } | |
684 | |
685 /* Frees the memory used by LST. */ | |
686 | |
687 static inline void | |
688 free_lst (lst_p lst) | |
689 { | |
690 if (!lst) | |
691 return; | |
692 | |
693 if (LST_LOOP_P (lst)) | |
694 { | |
695 int i; | |
696 lst_p l; | |
697 | |
698 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++) | |
699 free_lst (l); | |
700 | |
701 VEC_free (lst_p, heap, LST_SEQ (lst)); | |
702 } | |
703 | |
704 free (lst); | |
705 } | |
706 | |
707 /* Returns a copy of LST. */ | |
708 | |
709 static inline lst_p | |
710 copy_lst (lst_p lst) | |
711 { | |
712 if (!lst) | |
713 return NULL; | |
714 | |
715 if (LST_LOOP_P (lst)) | |
716 { | |
717 int i; | |
718 lst_p l; | |
719 VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5); | |
720 | |
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)); | |
723 | |
724 return new_lst_loop (seq); | |
725 } | |
726 | |
727 return new_lst_stmt (LST_PBB (lst)); | |
728 } | |
729 | |
730 /* Adds a new loop under the loop LST. */ | |
731 | |
732 static inline void | |
733 lst_add_loop_under_loop (lst_p lst) | |
734 { | |
735 VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 1); | |
736 lst_p l = new_lst_loop (LST_SEQ (lst)); | |
737 | |
738 gcc_assert (LST_LOOP_P (lst)); | |
739 | |
740 LST_LOOP_FATHER (l) = lst; | |
741 VEC_quick_push (lst_p, seq, l); | |
742 LST_SEQ (lst) = seq; | |
743 } | |
744 | |
745 /* Returns the loop depth of LST. */ | |
746 | |
747 static inline int | |
748 lst_depth (lst_p lst) | |
749 { | |
750 if (!lst) | |
751 return -2; | |
752 | |
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)) | |
757 return -1; | |
758 | |
759 return lst_depth (LST_LOOP_FATHER (lst)) + 1; | |
760 } | |
761 | |
762 /* Returns the Dewey number for LST. */ | |
763 | |
764 static inline int | |
765 lst_dewey_number (lst_p lst) | |
766 { | |
767 int i; | |
768 lst_p l; | |
769 | |
770 if (!lst) | |
771 return -1; | |
772 | |
773 if (!LST_LOOP_FATHER (lst)) | |
774 return 0; | |
775 | |
776 for (i = 0; VEC_iterate (lst_p, LST_SEQ (LST_LOOP_FATHER (lst)), i, l); i++) | |
777 if (l == lst) | |
778 return i; | |
779 | |
780 return -1; | |
781 } | |
782 | |
783 /* Returns the Dewey number of LST at depth DEPTH. */ | |
784 | |
785 static inline int | |
786 lst_dewey_number_at_depth (lst_p lst, int depth) | |
787 { | |
788 gcc_assert (lst && depth >= 0 && lst_depth (lst) <= depth); | |
789 | |
790 if (lst_depth (lst) == depth) | |
791 return lst_dewey_number (lst); | |
792 | |
793 return lst_dewey_number_at_depth (LST_LOOP_FATHER (lst), depth); | |
794 } | |
795 | |
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. */ | |
798 | |
799 static inline lst_p | |
800 lst_pred (lst_p lst) | |
801 { | |
802 int dewey; | |
803 lst_p father; | |
804 | |
805 if (!lst || !LST_LOOP_FATHER (lst)) | |
806 return NULL; | |
807 | |
808 dewey = lst_dewey_number (lst); | |
809 if (dewey == 0) | |
810 return NULL; | |
811 | |
812 father = LST_LOOP_FATHER (lst); | |
813 return VEC_index (lst_p, LST_SEQ (father), dewey - 1); | |
814 } | |
815 | |
816 /* Returns the successor of LST in the sequence of its loop father. | |
817 Returns NULL if there is none. */ | |
818 | |
819 static inline lst_p | |
820 lst_succ (lst_p lst) | |
821 { | |
822 int dewey; | |
823 lst_p father; | |
824 | |
825 if (!lst || !LST_LOOP_FATHER (lst)) | |
826 return NULL; | |
827 | |
828 dewey = lst_dewey_number (lst); | |
829 father = LST_LOOP_FATHER (lst); | |
830 | |
831 if (VEC_length (lst_p, LST_SEQ (father)) == (unsigned) dewey + 1) | |
832 return NULL; | |
833 | |
834 return VEC_index (lst_p, LST_SEQ (father), dewey + 1); | |
835 } | |
836 | |
837 | |
838 /* Return the LST node corresponding to PBB. */ | |
839 | |
840 static inline lst_p | |
841 lst_find_pbb (lst_p lst, poly_bb_p pbb) | |
842 { | |
843 int i; | |
844 lst_p l; | |
845 | |
846 if (!lst) | |
847 return NULL; | |
848 | |
849 if (!LST_LOOP_P (lst)) | |
850 return (pbb == LST_PBB (lst)) ? lst : NULL; | |
851 | |
852 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++) | |
853 { | |
854 lst_p res = lst_find_pbb (l, pbb); | |
855 if (res) | |
856 return res; | |
857 } | |
858 | |
859 return NULL; | |
860 } | |
861 | |
862 /* Return the LST node corresponding to the loop around STMT at depth | |
863 LOOP_DEPTH. */ | |
864 | |
865 static inline lst_p | |
866 find_lst_loop (lst_p stmt, int loop_depth) | |
867 { | |
868 lst_p loop = LST_LOOP_FATHER (stmt); | |
869 | |
870 gcc_assert (loop_depth >= 0); | |
871 | |
872 while (loop_depth < lst_depth (loop)) | |
873 loop = LST_LOOP_FATHER (loop); | |
874 | |
875 return loop; | |
876 } | |
877 | |
878 /* Return the first lst representing a PBB statement in LST. */ | |
879 | |
880 static inline lst_p | |
881 lst_find_first_pbb (lst_p lst) | |
882 { | |
883 int i; | |
884 lst_p l; | |
885 | |
886 if (!lst) | |
887 return NULL; | |
888 | |
889 if (!LST_LOOP_P (lst)) | |
890 return lst; | |
891 | |
892 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++) | |
893 { | |
894 lst_p res = lst_find_first_pbb (l); | |
895 if (res) | |
896 return res; | |
897 } | |
898 | |
899 return NULL; | |
900 } | |
901 | |
902 /* Returns true when LST is a loop that does not contains | |
903 statements. */ | |
904 | |
905 static inline bool | |
906 lst_empty_p (lst_p lst) | |
907 { | |
908 return !lst_find_first_pbb (lst); | |
909 } | |
910 | |
911 /* Return the last lst representing a PBB statement in LST. */ | |
912 | |
913 static inline lst_p | |
914 lst_find_last_pbb (lst_p lst) | |
915 { | |
916 int i; | |
917 lst_p l, res = NULL; | |
918 | |
919 if (!lst) | |
920 return NULL; | |
921 | |
922 if (!LST_LOOP_P (lst)) | |
923 return lst; | |
924 | |
925 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++) | |
926 { | |
927 lst_p last = lst_find_last_pbb (l); | |
928 | |
929 if (last) | |
930 res = last; | |
931 } | |
932 | |
933 gcc_assert (res); | |
934 return res; | |
935 } | |
936 | |
937 /* Returns true if LOOP contains LST, in other words, if LST is nested | |
938 in LOOP. */ | |
939 | |
940 static inline bool | |
941 lst_contains_p (lst_p loop, lst_p lst) | |
942 { | |
943 if (!loop || !lst || !LST_LOOP_P (loop)) | |
944 return false; | |
945 | |
946 if (loop == lst) | |
947 return true; | |
948 | |
949 return lst_contains_p (loop, LST_LOOP_FATHER (lst)); | |
950 } | |
951 | |
952 /* Returns true if LOOP contains PBB, in other words, if PBB is nested | |
953 in LOOP. */ | |
954 | |
955 static inline bool | |
956 lst_contains_pbb (lst_p loop, poly_bb_p pbb) | |
957 { | |
958 return lst_find_pbb (loop, pbb) ? true : false; | |
959 } | |
960 | |
961 /* Creates a loop nest of depth NB_LOOPS containing LST. */ | |
962 | |
963 static inline lst_p | |
964 lst_create_nest (int nb_loops, lst_p lst) | |
965 { | |
966 lst_p res, loop; | |
967 VEC (lst_p, heap) *seq; | |
968 | |
969 if (nb_loops == 0) | |
970 return lst; | |
971 | |
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; | |
977 | |
978 return res; | |
979 } | |
980 | |
981 /* Removes LST from the sequence of statements of its loop father. */ | |
982 | |
983 static inline void | |
984 lst_remove_from_sequence (lst_p lst) | |
985 { | |
986 lst_p father = LST_LOOP_FATHER (lst); | |
987 int dewey = lst_dewey_number (lst); | |
988 | |
989 gcc_assert (lst && father && dewey >= 0); | |
990 | |
991 VEC_ordered_remove (lst_p, LST_SEQ (father), dewey); | |
992 LST_LOOP_FATHER (lst) = NULL; | |
993 } | |
994 | |
995 /* Updates the scattering of PBB to be at the DEWEY number in the loop | |
996 at depth LEVEL. */ | |
997 | |
998 static inline void | |
999 pbb_update_scattering (poly_bb_p pbb, graphite_dim_t level, int dewey) | |
1000 { | |
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; | |
1007 | |
1008 ppl_Polyhedron_space_dimension (ph, &dim); | |
1009 ds[0] = sched; | |
1010 ppl_Polyhedron_remove_space_dimensions (ph, ds, 1); | |
1011 ppl_insert_dimensions (ph, sched, 1); | |
1012 | |
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); | |
1020 } | |
1021 | |
1022 /* Updates the scattering of all the PBBs under LST to be at the DEWEY | |
1023 number in the loop at depth LEVEL. */ | |
1024 | |
1025 static inline void | |
1026 lst_update_scattering_under (lst_p lst, int level, int dewey) | |
1027 { | |
1028 int i; | |
1029 lst_p l; | |
1030 | |
1031 gcc_assert (lst && level >= 0 && dewey >= 0); | |
1032 | |
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); | |
1036 else | |
1037 pbb_update_scattering (LST_PBB (lst), level, dewey); | |
1038 } | |
1039 | |
1040 /* Updates the scattering of all the PBBs under LST and in sequence | |
1041 with LST. */ | |
1042 | |
1043 static inline void | |
1044 lst_update_scattering_seq (lst_p lst) | |
1045 { | |
1046 int i; | |
1047 lst_p l; | |
1048 lst_p father = LST_LOOP_FATHER (lst); | |
1049 int dewey = lst_dewey_number (lst); | |
1050 int level = lst_depth (lst); | |
1051 | |
1052 gcc_assert (lst && father && dewey >= 0 && level >= 0); | |
1053 | |
1054 for (i = dewey; VEC_iterate (lst_p, LST_SEQ (father), i, l); i++) | |
1055 lst_update_scattering_under (l, level, i); | |
1056 } | |
1057 | |
1058 /* Updates the all the scattering levels of all the PBBs under | |
1059 LST. */ | |
1060 | |
1061 static inline void | |
1062 lst_update_scattering (lst_p lst) | |
1063 { | |
1064 int i; | |
1065 lst_p l; | |
1066 | |
1067 if (!lst || !LST_LOOP_P (lst)) | |
1068 return; | |
1069 | |
1070 if (LST_LOOP_FATHER (lst)) | |
1071 lst_update_scattering_seq (lst); | |
1072 | |
1073 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++) | |
1074 lst_update_scattering (l); | |
1075 } | |
1076 | |
1077 /* Inserts LST1 before LST2 if BEFORE is true; inserts LST1 after LST2 | |
1078 if BEFORE is false. */ | |
1079 | |
1080 static inline void | |
1081 lst_insert_in_sequence (lst_p lst1, lst_p lst2, bool before) | |
1082 { | |
1083 lst_p father; | |
1084 int dewey; | |
1085 | |
1086 /* Do not insert empty loops. */ | |
1087 if (!lst1 || lst_empty_p (lst1)) | |
1088 return; | |
1089 | |
1090 father = LST_LOOP_FATHER (lst2); | |
1091 dewey = lst_dewey_number (lst2); | |
1092 | |
1093 gcc_assert (lst2 && father && dewey >= 0); | |
1094 | |
1095 VEC_safe_insert (lst_p, heap, LST_SEQ (father), before ? dewey : dewey + 1, | |
1096 lst1); | |
1097 LST_LOOP_FATHER (lst1) = father; | |
1098 } | |
1099 | |
1100 /* Replaces LST1 with LST2. */ | |
1101 | |
1102 static inline void | |
1103 lst_replace (lst_p lst1, lst_p lst2) | |
1104 { | |
1105 lst_p father; | |
1106 int dewey; | |
1107 | |
1108 if (!lst2 || lst_empty_p (lst2)) | |
1109 return; | |
1110 | |
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); | |
1115 } | |
1116 | |
1117 /* Returns a copy of ROOT where LST has been replaced by a copy of the | |
1118 LSTs A B C in this sequence. */ | |
1119 | |
1120 static inline lst_p | |
1121 lst_substitute_3 (lst_p root, lst_p lst, lst_p a, lst_p b, lst_p c) | |
1122 { | |
1123 int i; | |
1124 lst_p l; | |
1125 VEC (lst_p, heap) *seq; | |
1126 | |
1127 if (!root) | |
1128 return NULL; | |
1129 | |
1130 gcc_assert (lst && root != lst); | |
1131 | |
1132 if (!LST_LOOP_P (root)) | |
1133 return new_lst_stmt (LST_PBB (root)); | |
1134 | |
1135 seq = VEC_alloc (lst_p, heap, 5); | |
1136 | |
1137 for (i = 0; VEC_iterate (lst_p, LST_SEQ (root), i, l); i++) | |
1138 if (l != lst) | |
1139 VEC_safe_push (lst_p, heap, seq, lst_substitute_3 (l, lst, a, b, c)); | |
1140 else | |
1141 { | |
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)); | |
1148 } | |
1149 | |
1150 return new_lst_loop (seq); | |
1151 } | |
1152 | |
1153 /* Moves LST before LOOP if BEFORE is true, and after the LOOP if | |
1154 BEFORE is false. */ | |
1155 | |
1156 static inline void | |
1157 lst_distribute_lst (lst_p loop, lst_p lst, bool before) | |
1158 { | |
1159 int loop_depth = lst_depth (loop); | |
1160 int depth = lst_depth (lst); | |
1161 int nb_loops = depth - loop_depth; | |
1162 | |
1163 gcc_assert (lst && loop && LST_LOOP_P (loop) && nb_loops > 0); | |
1164 | |
1165 lst_remove_from_sequence (lst); | |
1166 lst_insert_in_sequence (lst_create_nest (nb_loops, lst), loop, before); | |
1167 } | |
1168 | |
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. */ | |
1172 | |
1173 static inline bool | |
1174 lst_remove_all_before_including_pbb (lst_p loop, poly_bb_p pbb, bool before) | |
1175 { | |
1176 int i; | |
1177 lst_p l; | |
1178 | |
1179 if (!loop || !LST_LOOP_P (loop)) | |
1180 return before; | |
1181 | |
1182 for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l);) | |
1183 if (LST_LOOP_P (l)) | |
1184 { | |
1185 before = lst_remove_all_before_including_pbb (l, pbb, before); | |
1186 | |
1187 if (VEC_length (lst_p, LST_SEQ (l)) == 0) | |
1188 { | |
1189 VEC_ordered_remove (lst_p, LST_SEQ (loop), i); | |
1190 free_lst (l); | |
1191 } | |
1192 else | |
1193 i++; | |
1194 } | |
1195 else | |
1196 { | |
1197 if (before) | |
1198 { | |
1199 if (LST_PBB (l) == pbb) | |
1200 before = false; | |
1201 | |
1202 VEC_ordered_remove (lst_p, LST_SEQ (loop), i); | |
1203 free_lst (l); | |
1204 } | |
1205 else if (LST_PBB (l) == pbb) | |
1206 { | |
1207 before = true; | |
1208 VEC_ordered_remove (lst_p, LST_SEQ (loop), i); | |
1209 free_lst (l); | |
1210 } | |
1211 else | |
1212 i++; | |
1213 } | |
1214 | |
1215 return before; | |
1216 } | |
1217 | |
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. */ | |
1221 | |
1222 static inline bool | |
1223 lst_remove_all_before_excluding_pbb (lst_p loop, poly_bb_p pbb, bool before) | |
1224 { | |
1225 int i; | |
1226 lst_p l; | |
1227 | |
1228 if (!loop || !LST_LOOP_P (loop)) | |
1229 return before; | |
1230 | |
1231 for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l);) | |
1232 if (LST_LOOP_P (l)) | |
1233 { | |
1234 before = lst_remove_all_before_excluding_pbb (l, pbb, before); | |
1235 | |
1236 if (VEC_length (lst_p, LST_SEQ (l)) == 0) | |
1237 { | |
1238 VEC_ordered_remove (lst_p, LST_SEQ (loop), i); | |
1239 free_lst (l); | |
1240 continue; | |
1241 } | |
1242 | |
1243 i++; | |
1244 } | |
1245 else | |
1246 { | |
1247 if (before && LST_PBB (l) != pbb) | |
1248 { | |
1249 VEC_ordered_remove (lst_p, LST_SEQ (loop), i); | |
1250 free_lst (l); | |
1251 continue; | |
1252 } | |
1253 | |
1254 i++; | |
1255 | |
1256 if (LST_PBB (l) == pbb) | |
1257 before = before ? false : true; | |
1258 } | |
1259 | |
1260 return before; | |
1261 } | |
1262 | |
1263 /* A SCOP is a Static Control Part of the program, simple enough to be | |
1264 represented in polyhedral form. */ | |
1265 struct scop | |
1266 { | |
1267 /* A SCOP is defined as a SESE region. */ | |
1268 void *region; | |
1269 | |
1270 /* Number of parameters in SCoP. */ | |
1271 graphite_dim_t nb_params; | |
1272 | |
1273 /* All the basic blocks in this scop that contain memory references | |
1274 and that will be represented as statements in the polyhedral | |
1275 representation. */ | |
1276 VEC (poly_bb_p, heap) *bbs; | |
1277 | |
1278 /* Original, transformed and saved schedules. */ | |
1279 lst_p original_schedule, transformed_schedule, saved_schedule; | |
1280 | |
1281 /* The context describes known restrictions concerning the parameters | |
1282 and relations in between the parameters. | |
1283 | |
1284 void f (int8_t a, uint_16_t b) { | |
1285 c = 2 a + b; | |
1286 ... | |
1287 } | |
1288 | |
1289 Here we can add these restrictions to the context: | |
1290 | |
1291 -128 >= a >= 127 | |
1292 0 >= b >= 65,535 | |
1293 c = 2a + b */ | |
1294 ppl_Pointset_Powerset_C_Polyhedron_t context; | |
1295 | |
1296 /* A hashtable of the data dependence relations for the original | |
1297 scattering. */ | |
1298 htab_t original_pddrs; | |
1299 }; | |
1300 | |
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) | |
1308 | |
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); | |
1322 | |
1323 /* Set the region of SCOP to REGION. */ | |
1324 | |
1325 static inline void | |
1326 scop_set_region (scop_p scop, void *region) | |
1327 { | |
1328 scop->region = region; | |
1329 } | |
1330 | |
1331 /* Returns the number of parameters for SCOP. */ | |
1332 | |
1333 static inline graphite_dim_t | |
1334 scop_nb_params (scop_p scop) | |
1335 { | |
1336 return scop->nb_params; | |
1337 } | |
1338 | |
1339 /* Set the number of params of SCOP to NB_PARAMS. */ | |
1340 | |
1341 static inline void | |
1342 scop_set_nb_params (scop_p scop, graphite_dim_t nb_params) | |
1343 { | |
1344 scop->nb_params = nb_params; | |
1345 } | |
1346 | |
1347 /* Allocates a new empty poly_scattering structure. */ | |
1348 | |
1349 static inline poly_scattering_p | |
1350 poly_scattering_new (void) | |
1351 { | |
1352 poly_scattering_p res = XNEW (struct poly_scattering); | |
1353 | |
1354 res->scattering = NULL; | |
1355 res->nb_local_variables = 0; | |
1356 res->nb_scattering = 0; | |
1357 return res; | |
1358 } | |
1359 | |
1360 /* Free a poly_scattering structure. */ | |
1361 | |
1362 static inline void | |
1363 poly_scattering_free (poly_scattering_p s) | |
1364 { | |
1365 ppl_delete_Polyhedron (s->scattering); | |
1366 free (s); | |
1367 } | |
1368 | |
1369 /* Copies S and return a new scattering. */ | |
1370 | |
1371 static inline poly_scattering_p | |
1372 poly_scattering_copy (poly_scattering_p s) | |
1373 { | |
1374 poly_scattering_p res = poly_scattering_new (); | |
1375 | |
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; | |
1379 return res; | |
1380 } | |
1381 | |
1382 /* Saves the transformed scattering of PBB. */ | |
1383 | |
1384 static inline void | |
1385 store_scattering_pbb (poly_bb_p pbb) | |
1386 { | |
1387 gcc_assert (PBB_TRANSFORMED (pbb)); | |
1388 | |
1389 if (PBB_SAVED (pbb)) | |
1390 poly_scattering_free (PBB_SAVED (pbb)); | |
1391 | |
1392 PBB_SAVED (pbb) = poly_scattering_copy (PBB_TRANSFORMED (pbb)); | |
1393 } | |
1394 | |
1395 /* Stores the SCOP_TRANSFORMED_SCHEDULE to SCOP_SAVED_SCHEDULE. */ | |
1396 | |
1397 static inline void | |
1398 store_lst_schedule (scop_p scop) | |
1399 { | |
1400 if (SCOP_SAVED_SCHEDULE (scop)) | |
1401 free_lst (SCOP_SAVED_SCHEDULE (scop)); | |
1402 | |
1403 SCOP_SAVED_SCHEDULE (scop) = copy_lst (SCOP_TRANSFORMED_SCHEDULE (scop)); | |
1404 } | |
1405 | |
1406 /* Restores the SCOP_TRANSFORMED_SCHEDULE from SCOP_SAVED_SCHEDULE. */ | |
1407 | |
1408 static inline void | |
1409 restore_lst_schedule (scop_p scop) | |
1410 { | |
1411 if (SCOP_TRANSFORMED_SCHEDULE (scop)) | |
1412 free_lst (SCOP_TRANSFORMED_SCHEDULE (scop)); | |
1413 | |
1414 SCOP_TRANSFORMED_SCHEDULE (scop) = copy_lst (SCOP_SAVED_SCHEDULE (scop)); | |
1415 } | |
1416 | |
1417 /* Saves the scattering for all the pbbs in the SCOP. */ | |
1418 | |
1419 static inline void | |
1420 store_scattering (scop_p scop) | |
1421 { | |
1422 int i; | |
1423 poly_bb_p pbb; | |
1424 | |
1425 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) | |
1426 store_scattering_pbb (pbb); | |
1427 | |
1428 store_lst_schedule (scop); | |
1429 } | |
1430 | |
1431 /* Restores the scattering of PBB. */ | |
1432 | |
1433 static inline void | |
1434 restore_scattering_pbb (poly_bb_p pbb) | |
1435 { | |
1436 gcc_assert (PBB_SAVED (pbb)); | |
1437 | |
1438 poly_scattering_free (PBB_TRANSFORMED (pbb)); | |
1439 PBB_TRANSFORMED (pbb) = poly_scattering_copy (PBB_SAVED (pbb)); | |
1440 } | |
1441 | |
1442 /* Restores the scattering for all the pbbs in the SCOP. */ | |
1443 | |
1444 static inline void | |
1445 restore_scattering (scop_p scop) | |
1446 { | |
1447 int i; | |
1448 poly_bb_p pbb; | |
1449 | |
1450 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) | |
1451 restore_scattering_pbb (pbb); | |
1452 | |
1453 restore_lst_schedule (scop); | |
1454 } | |
1455 | |
1456 #endif |