]>
Commit | Line | Data |
---|---|---|
2abae5f1 | 1 | /* Graphite polyhedral representation. |
23a5b65a | 2 | Copyright (C) 2009-2014 Free Software Foundation, Inc. |
2abae5f1 SP |
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; | |
2abae5f1 SP |
26 | |
27 | typedef struct poly_bb *poly_bb_p; | |
2abae5f1 SP |
28 | |
29 | typedef struct scop *scop_p; | |
2abae5f1 | 30 | |
33ad93b9 | 31 | typedef unsigned graphite_dim_t; |
2abae5f1 SP |
32 | |
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); | |
36 | ||
37 | /* A data reference can write or read some memory or we | |
38 | just know it may write some memory. */ | |
e6dec0fb | 39 | enum poly_dr_type |
2abae5f1 SP |
40 | { |
41 | PDR_READ, | |
d8eeb078 SP |
42 | /* PDR_MAY_READs are represented using PDR_READS. This does not |
43 | limit the expressiveness. */ | |
2abae5f1 SP |
44 | PDR_WRITE, |
45 | PDR_MAY_WRITE | |
46 | }; | |
47 | ||
48 | struct poly_dr | |
49 | { | |
afae0207 SP |
50 | /* An identifier for this PDR. */ |
51 | int id; | |
52 | ||
7bd2a8a7 SP |
53 | /* The number of data refs identical to this one in the PBB. */ |
54 | int nb_refs; | |
55 | ||
2abae5f1 SP |
56 | /* A pointer to compiler's data reference description. */ |
57 | void *compiler_dr; | |
58 | ||
59 | /* A pointer to the PBB that contains this data reference. */ | |
60 | poly_bb_p pbb; | |
61 | ||
e6dec0fb | 62 | enum poly_dr_type type; |
2abae5f1 SP |
63 | |
64 | /* The access polyhedron contains the polyhedral space this data | |
65 | reference will access. | |
66 | ||
67 | The polyhedron contains these dimensions: | |
68 | ||
1825f9a2 LF |
69 | - The alias set (a): |
70 | Every memory access is classified in at least one alias set. | |
2abae5f1 | 71 | |
1825f9a2 LF |
72 | - The subscripts (s_0, ..., s_n): |
73 | The memory is accessed using zero or more subscript dimensions. | |
2abae5f1 | 74 | |
1825f9a2 | 75 | - The iteration domain (variables and parameters) |
2abae5f1 SP |
76 | |
77 | Do not hardcode the dimensions. Use the following accessor functions: | |
78 | - pdr_alias_set_dim | |
79 | - pdr_subscript_dim | |
80 | - pdr_iterator_dim | |
81 | - pdr_parameter_dim | |
82 | ||
83 | Example: | |
84 | ||
85 | | int A[1335][123]; | |
86 | | int *p = malloc (); | |
87 | | | |
88 | | k = ... | |
89 | | for i | |
90 | | { | |
91 | | if (unknown_function ()) | |
92 | | p = A; | |
93 | | ... = p[?][?]; | |
94 | | for j | |
25d7cc15 | 95 | | A[i][j+k] = m; |
2abae5f1 SP |
96 | | } |
97 | ||
98 | The data access A[i][j+k] in alias set "5" is described like this: | |
99 | ||
25d7cc15 | 100 | | i j k a s0 s1 1 |
2abae5f1 SP |
101 | | 0 0 0 1 0 0 -5 = 0 |
102 | |-1 0 0 0 1 0 0 = 0 | |
103 | | 0 -1 -1 0 0 1 0 = 0 | |
66096911 SP |
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. | |
2abae5f1 SP |
106 | | 0 0 0 0 -1 0 1335 >= 0 |
107 | | 0 0 0 0 0 -1 123 >= 0 | |
108 | ||
109 | The pointer "*p" in alias set "5" and "7" is described as a union of | |
110 | polyhedron: | |
111 | ||
112 | ||
25d7cc15 | 113 | | i k a s0 1 |
2abae5f1 SP |
114 | | 0 0 1 0 -5 = 0 |
115 | | 0 0 0 1 0 >= 0 | |
116 | ||
117 | "or" | |
118 | ||
25d7cc15 | 119 | | i k a s0 1 |
2abae5f1 SP |
120 | | 0 0 1 0 -7 = 0 |
121 | | 0 0 0 1 0 >= 0 | |
122 | ||
123 | "*p" accesses all of the object allocated with 'malloc'. | |
124 | ||
125 | The scalar data access "m" is represented as an array with zero subscript | |
126 | dimensions. | |
127 | ||
128 | | i j k a 1 | |
ae403f5a RB |
129 | | 0 0 0 -1 15 = 0 |
130 | ||
131 | The difference between the graphite internal format for access data and | |
132 | the OpenSop format is in the order of columns. | |
133 | Instead of having: | |
134 | ||
135 | | i j k a s0 s1 1 | |
136 | | 0 0 0 1 0 0 -5 = 0 | |
137 | |-1 0 0 0 1 0 0 = 0 | |
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 | |
143 | ||
144 | In OpenScop we have: | |
145 | ||
146 | | a s0 s1 i j k 1 | |
147 | | 1 0 0 0 0 0 -5 = 0 | |
148 | | 0 1 0 -1 0 0 0 = 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 | |
154 | ||
155 | The OpenScop access function is printed as follows: | |
156 | ||
157 | | 1 # The number of disjunct components in a union of access functions. | |
158 | | R C O I L P # Described bellow. | |
159 | | a s0 s1 i j k 1 | |
160 | | 1 0 0 0 0 0 -5 = 0 | |
161 | | 0 1 0 -1 0 0 0 = 0 | |
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 | |
167 | ||
168 | Where: | |
169 | - R: Number of rows. | |
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. | |
175 | ||
176 | In the example, the vector "R C O I L P" is "7 7 3 2 0 1". */ | |
33ad93b9 RG |
177 | isl_map *accesses; |
178 | isl_set *extent; | |
25d7cc15 | 179 | |
1825f9a2 LF |
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; | |
183 | ||
25d7cc15 | 184 | /* The number of subscripts. */ |
afae0207 | 185 | graphite_dim_t nb_subscripts; |
2abae5f1 SP |
186 | }; |
187 | ||
afae0207 | 188 | #define PDR_ID(PDR) (PDR->id) |
7bd2a8a7 | 189 | #define PDR_NB_REFS(PDR) (PDR->nb_refs) |
2abae5f1 SP |
190 | #define PDR_CDR(PDR) (PDR->compiler_dr) |
191 | #define PDR_PBB(PDR) (PDR->pbb) | |
192 | #define PDR_TYPE(PDR) (PDR->type) | |
33ad93b9 | 193 | #define PDR_ACCESSES(PDR) (NULL) |
1825f9a2 | 194 | #define PDR_BASE_OBJECT_SET(PDR) (PDR->dr_base_object_set) |
25d7cc15 | 195 | #define PDR_NB_SUBSCRIPTS(PDR) (PDR->nb_subscripts) |
2abae5f1 | 196 | |
33ad93b9 RG |
197 | void new_poly_dr (poly_bb_p, int, enum poly_dr_type, void *, |
198 | graphite_dim_t, isl_map *, isl_set *); | |
2abae5f1 | 199 | void free_poly_dr (poly_dr_p); |
40bf935e SP |
200 | void debug_pdr (poly_dr_p, int); |
201 | void print_pdr (FILE *, poly_dr_p, int); | |
2abae5f1 SP |
202 | static inline scop_p pdr_scop (poly_dr_p pdr); |
203 | ||
2abae5f1 SP |
204 | /* The dimension of the iteration domain of the scop of PDR. */ |
205 | ||
33ad93b9 | 206 | static inline graphite_dim_t |
2abae5f1 SP |
207 | pdr_dim_iter_domain (poly_dr_p pdr) |
208 | { | |
209 | return pbb_dim_iter_domain (PDR_PBB (pdr)); | |
210 | } | |
211 | ||
212 | /* The number of parameters of the scop of PDR. */ | |
213 | ||
33ad93b9 | 214 | static inline graphite_dim_t |
2abae5f1 SP |
215 | pdr_nb_params (poly_dr_p pdr) |
216 | { | |
217 | return scop_nb_params (pdr_scop (pdr)); | |
218 | } | |
219 | ||
2abae5f1 SP |
220 | /* The dimension of the alias set in PDR. */ |
221 | ||
33ad93b9 | 222 | static inline graphite_dim_t |
2abae5f1 SP |
223 | pdr_alias_set_dim (poly_dr_p pdr) |
224 | { | |
225 | poly_bb_p pbb = PDR_PBB (pdr); | |
226 | ||
227 | return pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb); | |
228 | } | |
229 | ||
230 | /* The dimension in PDR containing subscript S. */ | |
231 | ||
33ad93b9 | 232 | static inline graphite_dim_t |
2abae5f1 SP |
233 | pdr_subscript_dim (poly_dr_p pdr, graphite_dim_t s) |
234 | { | |
235 | poly_bb_p pbb = PDR_PBB (pdr); | |
236 | ||
237 | return pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb) + 1 + s; | |
238 | } | |
239 | ||
240 | /* The dimension in PDR containing the loop iterator ITER. */ | |
241 | ||
33ad93b9 | 242 | static inline graphite_dim_t |
2abae5f1 SP |
243 | pdr_iterator_dim (poly_dr_p pdr ATTRIBUTE_UNUSED, graphite_dim_t iter) |
244 | { | |
245 | return iter; | |
246 | } | |
247 | ||
248 | /* The dimension in PDR containing parameter PARAM. */ | |
249 | ||
33ad93b9 | 250 | static inline graphite_dim_t |
2abae5f1 SP |
251 | pdr_parameter_dim (poly_dr_p pdr, graphite_dim_t param) |
252 | { | |
253 | poly_bb_p pbb = PDR_PBB (pdr); | |
254 | ||
255 | return pbb_dim_iter_domain (pbb) + param; | |
256 | } | |
257 | ||
d8eeb078 SP |
258 | /* Returns true when PDR is a "read". */ |
259 | ||
260 | static inline bool | |
261 | pdr_read_p (poly_dr_p pdr) | |
262 | { | |
263 | return PDR_TYPE (pdr) == PDR_READ; | |
264 | } | |
265 | ||
266 | /* Returns true when PDR is a "write". */ | |
267 | ||
268 | static inline bool | |
269 | pdr_write_p (poly_dr_p pdr) | |
270 | { | |
271 | return PDR_TYPE (pdr) == PDR_WRITE; | |
272 | } | |
273 | ||
274 | /* Returns true when PDR is a "may write". */ | |
275 | ||
276 | static inline bool | |
277 | pdr_may_write_p (poly_dr_p pdr) | |
278 | { | |
279 | return PDR_TYPE (pdr) == PDR_MAY_WRITE; | |
280 | } | |
281 | ||
60d2a8c3 SP |
282 | /* Return true when PDR1 and PDR2 are similar data accesses: they have |
283 | the same base array, and the same access functions. */ | |
284 | ||
285 | static inline bool | |
286 | same_pdr_p (poly_dr_p pdr1, poly_dr_p pdr2) | |
287 | { | |
ba858447 | 288 | return PDR_NB_SUBSCRIPTS (pdr1) == PDR_NB_SUBSCRIPTS (pdr2) |
60d2a8c3 SP |
289 | && PDR_BASE_OBJECT_SET (pdr1) == PDR_BASE_OBJECT_SET (pdr2); |
290 | } | |
291 | ||
f4648ed1 SP |
292 | typedef struct poly_scattering *poly_scattering_p; |
293 | ||
294 | struct poly_scattering | |
295 | { | |
f4648ed1 SP |
296 | /* The number of local variables. */ |
297 | int nb_local_variables; | |
298 | ||
299 | /* The number of scattering dimensions. */ | |
300 | int nb_scattering; | |
301 | }; | |
302 | ||
2abae5f1 SP |
303 | /* POLY_BB represents a blackbox in the polyhedral model. */ |
304 | ||
305 | struct poly_bb | |
306 | { | |
a1954f72 | 307 | /* Pointer to a basic block or a statement in the compiler. */ |
2abae5f1 SP |
308 | void *black_box; |
309 | ||
a1954f72 | 310 | /* Pointer to the SCOP containing this PBB. */ |
2abae5f1 SP |
311 | scop_p scop; |
312 | ||
aa52513e SP |
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. | |
315 | ||
2abae5f1 SP |
316 | Example: |
317 | ||
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++) | |
321 | S (i,j,k) | |
322 | ||
323 | Loop iterators: i, j, k | |
324 | Parameters: a, b | |
325 | ||
326 | | i >= a - 7b + 8 | |
327 | | i <= 3a + 13b + 20 | |
328 | | j >= 2 | |
329 | | j <= 2i + 5 | |
330 | | k >= 0 | |
331 | | k <= 5 | |
332 | ||
333 | The number of variables in the DOMAIN may change and is not | |
334 | related to the number of loops in the original code. */ | |
33ad93b9 | 335 | isl_set *domain; |
2abae5f1 SP |
336 | |
337 | /* The data references we access. */ | |
9771b263 | 338 | vec<poly_dr_p> drs; |
2abae5f1 | 339 | |
f4648ed1 | 340 | /* The original scattering. */ |
33ad93b9 RG |
341 | poly_scattering_p _original; |
342 | isl_map *schedule; | |
2abae5f1 | 343 | |
f4648ed1 | 344 | /* The transformed scattering. */ |
33ad93b9 RG |
345 | poly_scattering_p _transformed; |
346 | isl_map *transformed; | |
2abae5f1 | 347 | |
f4648ed1 | 348 | /* A copy of the transformed scattering. */ |
33ad93b9 RG |
349 | poly_scattering_p _saved; |
350 | isl_map *saved; | |
a0dd1440 SP |
351 | |
352 | /* True when this PBB contains only a reduction statement. */ | |
353 | bool is_reduction; | |
2abae5f1 SP |
354 | }; |
355 | ||
356 | #define PBB_BLACK_BOX(PBB) ((gimple_bb_p) PBB->black_box) | |
357 | #define PBB_SCOP(PBB) (PBB->scop) | |
33ad93b9 | 358 | #define PBB_DOMAIN(PBB) (NULL) |
2abae5f1 | 359 | #define PBB_DRS(PBB) (PBB->drs) |
33ad93b9 RG |
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. | |
367 | */ | |
368 | #define PBB_NB_LOCAL_VARIABLES(PBB) (0) | |
369 | #define PBB_NB_SCATTERING_TRANSFORM(PBB) (isl_map_n_out (PBB->transformed)) | |
a0dd1440 | 370 | #define PBB_IS_REDUCTION(PBB) (PBB->is_reduction) |
2abae5f1 | 371 | |
efa21390 | 372 | extern poly_bb_p new_poly_bb (scop_p, void *); |
2abae5f1 SP |
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); | |
40bf935e SP |
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 print_cloog (FILE *, scop_p, int); | |
381 | extern void debug_pbb_domain (poly_bb_p, int); | |
382 | extern void debug_pbb (poly_bb_p, int); | |
383 | extern void print_pdrs (FILE *, poly_bb_p, int); | |
384 | extern void debug_pdrs (poly_bb_p, int); | |
385 | extern void debug_scop_context (scop_p, int); | |
386 | extern void debug_scop (scop_p, int); | |
387 | extern void debug_cloog (scop_p, int); | |
388 | extern void print_scop_params (FILE *, scop_p, int); | |
389 | extern void debug_scop_params (scop_p, int); | |
390 | extern void print_iteration_domain (FILE *, poly_bb_p, int); | |
391 | extern void print_iteration_domains (FILE *, scop_p, int); | |
392 | extern void debug_iteration_domain (poly_bb_p, int); | |
393 | extern void debug_iteration_domains (scop_p, int); | |
33ad93b9 RG |
394 | extern void print_isl_set (FILE *, isl_set *); |
395 | extern void print_isl_map (FILE *, isl_map *); | |
396 | extern void print_isl_aff (FILE *, isl_aff *); | |
397 | extern void print_isl_constraint (FILE *, isl_constraint *); | |
398 | extern void debug_isl_set (isl_set *); | |
399 | extern void debug_isl_map (isl_map *); | |
400 | extern void debug_isl_aff (isl_aff *); | |
401 | extern void debug_isl_constraint (isl_constraint *); | |
cec11ec4 SP |
402 | extern int scop_do_interchange (scop_p); |
403 | extern int scop_do_strip_mine (scop_p, int); | |
25e20d33 | 404 | extern bool scop_do_block (scop_p); |
98af4c9f | 405 | extern bool flatten_all_loops (scop_p); |
c3284718 | 406 | extern bool optimize_isl (scop_p); |
e262fdda | 407 | extern void pbb_number_of_iterations_at_time (poly_bb_p, graphite_dim_t, mpz_t); |
33ad93b9 | 408 | extern void debug_gmp_value (mpz_t); |
2abae5f1 | 409 | |
60d2a8c3 SP |
410 | /* Return the number of write data references in PBB. */ |
411 | ||
412 | static inline int | |
413 | number_of_write_pdrs (poly_bb_p pbb) | |
414 | { | |
415 | int res = 0; | |
416 | int i; | |
417 | poly_dr_p pdr; | |
418 | ||
9771b263 | 419 | for (i = 0; PBB_DRS (pbb).iterate (i, &pdr); i++) |
60d2a8c3 SP |
420 | if (PDR_TYPE (pdr) == PDR_WRITE) |
421 | res++; | |
422 | ||
423 | return res; | |
424 | } | |
425 | ||
efa21390 SP |
426 | /* Returns a gimple_bb from BB. */ |
427 | ||
428 | static inline gimple_bb_p | |
429 | gbb_from_bb (basic_block bb) | |
430 | { | |
431 | return (gimple_bb_p) bb->aux; | |
432 | } | |
433 | ||
434 | /* The poly_bb of the BB. */ | |
435 | ||
436 | static inline poly_bb_p | |
437 | pbb_from_bb (basic_block bb) | |
438 | { | |
439 | return GBB_PBB (gbb_from_bb (bb)); | |
440 | } | |
441 | ||
03922af3 | 442 | /* The basic block of the PBB. */ |
072edf07 | 443 | |
03922af3 SP |
444 | static inline basic_block |
445 | pbb_bb (poly_bb_p pbb) | |
446 | { | |
447 | return GBB_BB (PBB_BLACK_BOX (pbb)); | |
448 | } | |
449 | ||
afae0207 SP |
450 | /* The index of the PBB. */ |
451 | ||
452 | static inline int | |
453 | pbb_index (poly_bb_p pbb) | |
454 | { | |
03922af3 | 455 | return pbb_bb (pbb)->index; |
afae0207 SP |
456 | } |
457 | ||
d48e288d SP |
458 | /* The loop of the PBB. */ |
459 | ||
460 | static inline loop_p | |
461 | pbb_loop (poly_bb_p pbb) | |
462 | { | |
463 | return gbb_loop (PBB_BLACK_BOX (pbb)); | |
464 | } | |
465 | ||
2abae5f1 SP |
466 | /* The scop that contains the PDR. */ |
467 | ||
afae0207 SP |
468 | static inline scop_p |
469 | pdr_scop (poly_dr_p pdr) | |
2abae5f1 SP |
470 | { |
471 | return PBB_SCOP (PDR_PBB (pdr)); | |
472 | } | |
473 | ||
474 | /* Set black box of PBB to BLACKBOX. */ | |
475 | ||
476 | static inline void | |
477 | pbb_set_black_box (poly_bb_p pbb, void *black_box) | |
478 | { | |
479 | pbb->black_box = black_box; | |
480 | } | |
481 | ||
482 | /* The number of loops around PBB: the dimension of the iteration | |
483 | domain. */ | |
484 | ||
485 | static inline graphite_dim_t | |
486 | pbb_dim_iter_domain (const struct poly_bb *pbb) | |
487 | { | |
33ad93b9 | 488 | return isl_set_dim (pbb->domain, isl_dim_set); |
2abae5f1 SP |
489 | } |
490 | ||
491 | /* The number of params defined in PBB. */ | |
492 | ||
493 | static inline graphite_dim_t | |
494 | pbb_nb_params (const struct poly_bb *pbb) | |
495 | { | |
496 | scop_p scop = PBB_SCOP (pbb); | |
497 | ||
498 | return scop_nb_params (scop); | |
499 | } | |
500 | ||
501 | /* The number of scattering dimensions in the SCATTERING polyhedron | |
502 | of a PBB for a given SCOP. */ | |
503 | ||
504 | static inline graphite_dim_t | |
505 | pbb_nb_scattering_orig (const struct poly_bb *pbb) | |
506 | { | |
507 | return 2 * pbb_dim_iter_domain (pbb) + 1; | |
508 | } | |
509 | ||
510 | /* The number of scattering dimensions in PBB. */ | |
511 | ||
512 | static inline graphite_dim_t | |
513 | pbb_nb_scattering_transform (const struct poly_bb *pbb) | |
514 | { | |
515 | return PBB_NB_SCATTERING_TRANSFORM (pbb); | |
516 | } | |
517 | ||
baf4b881 KT |
518 | /* The number of dynamic scattering dimensions in PBB. */ |
519 | ||
520 | static inline graphite_dim_t | |
521 | pbb_nb_dynamic_scattering_transform (const struct poly_bb *pbb) | |
522 | { | |
523 | /* This function requires the 2d + 1 scattering format to be | |
524 | invariant during all transformations. */ | |
525 | gcc_assert (PBB_NB_SCATTERING_TRANSFORM (pbb) % 2); | |
526 | return PBB_NB_SCATTERING_TRANSFORM (pbb) / 2; | |
527 | } | |
528 | ||
2abae5f1 SP |
529 | /* Returns the number of local variables used in the transformed |
530 | scattering polyhedron of PBB. */ | |
531 | ||
532 | static inline graphite_dim_t | |
33ad93b9 | 533 | pbb_nb_local_vars (const struct poly_bb *pbb ATTRIBUTE_UNUSED) |
2abae5f1 SP |
534 | { |
535 | /* For now we do not have any local variables, as we do not do strip | |
536 | mining for example. */ | |
537 | return PBB_NB_LOCAL_VARIABLES (pbb); | |
538 | } | |
539 | ||
540 | /* The dimension in the domain of PBB containing the iterator ITER. */ | |
541 | ||
33ad93b9 | 542 | static inline graphite_dim_t |
2abae5f1 SP |
543 | pbb_iterator_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t iter) |
544 | { | |
545 | return iter; | |
546 | } | |
547 | ||
548 | /* The dimension in the domain of PBB containing the iterator ITER. */ | |
549 | ||
33ad93b9 | 550 | static inline graphite_dim_t |
2abae5f1 SP |
551 | pbb_parameter_dim (poly_bb_p pbb, graphite_dim_t param) |
552 | { | |
553 | return param | |
554 | + pbb_dim_iter_domain (pbb); | |
555 | } | |
556 | ||
557 | /* The dimension in the original scattering polyhedron of PBB | |
558 | containing the scattering iterator SCATTER. */ | |
559 | ||
33ad93b9 | 560 | static inline graphite_dim_t |
2abae5f1 SP |
561 | psco_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t scatter) |
562 | { | |
563 | gcc_assert (scatter < pbb_nb_scattering_orig (pbb)); | |
564 | return scatter; | |
565 | } | |
566 | ||
567 | /* The dimension in the transformed scattering polyhedron of PBB | |
568 | containing the scattering iterator SCATTER. */ | |
569 | ||
33ad93b9 | 570 | static inline graphite_dim_t |
2abae5f1 SP |
571 | psct_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t scatter) |
572 | { | |
573 | gcc_assert (scatter <= pbb_nb_scattering_transform (pbb)); | |
574 | return scatter; | |
575 | } | |
576 | ||
2abae5f1 SP |
577 | /* The dimension in the transformed scattering polyhedron of PBB of |
578 | the local variable LV. */ | |
579 | ||
33ad93b9 | 580 | static inline graphite_dim_t |
2abae5f1 SP |
581 | psct_local_var_dim (poly_bb_p pbb, graphite_dim_t lv) |
582 | { | |
583 | gcc_assert (lv <= pbb_nb_local_vars (pbb)); | |
584 | return lv + pbb_nb_scattering_transform (pbb); | |
585 | } | |
586 | ||
587 | /* The dimension in the original scattering polyhedron of PBB | |
588 | containing the loop iterator ITER. */ | |
589 | ||
33ad93b9 | 590 | static inline graphite_dim_t |
2abae5f1 SP |
591 | psco_iterator_dim (poly_bb_p pbb, graphite_dim_t iter) |
592 | { | |
593 | gcc_assert (iter < pbb_dim_iter_domain (pbb)); | |
594 | return iter + pbb_nb_scattering_orig (pbb); | |
595 | } | |
596 | ||
597 | /* The dimension in the transformed scattering polyhedron of PBB | |
598 | containing the loop iterator ITER. */ | |
599 | ||
33ad93b9 | 600 | static inline graphite_dim_t |
2abae5f1 SP |
601 | psct_iterator_dim (poly_bb_p pbb, graphite_dim_t iter) |
602 | { | |
603 | gcc_assert (iter < pbb_dim_iter_domain (pbb)); | |
604 | return iter | |
605 | + pbb_nb_scattering_transform (pbb) | |
606 | + pbb_nb_local_vars (pbb); | |
607 | } | |
608 | ||
609 | /* The dimension in the original scattering polyhedron of PBB | |
610 | containing parameter PARAM. */ | |
611 | ||
33ad93b9 | 612 | static inline graphite_dim_t |
2abae5f1 SP |
613 | psco_parameter_dim (poly_bb_p pbb, graphite_dim_t param) |
614 | { | |
615 | gcc_assert (param < pbb_nb_params (pbb)); | |
616 | return param | |
617 | + pbb_nb_scattering_orig (pbb) | |
618 | + pbb_dim_iter_domain (pbb); | |
619 | } | |
620 | ||
621 | /* The dimension in the transformed scattering polyhedron of PBB | |
622 | containing parameter PARAM. */ | |
623 | ||
33ad93b9 | 624 | static inline graphite_dim_t |
2abae5f1 SP |
625 | psct_parameter_dim (poly_bb_p pbb, graphite_dim_t param) |
626 | { | |
627 | gcc_assert (param < pbb_nb_params (pbb)); | |
628 | return param | |
629 | + pbb_nb_scattering_transform (pbb) | |
630 | + pbb_nb_local_vars (pbb) | |
631 | + pbb_dim_iter_domain (pbb); | |
632 | } | |
633 | ||
baf4b881 KT |
634 | /* The scattering dimension of PBB corresponding to the dynamic level |
635 | LEVEL. */ | |
636 | ||
33ad93b9 | 637 | static inline graphite_dim_t |
baf4b881 KT |
638 | psct_dynamic_dim (poly_bb_p pbb, graphite_dim_t level) |
639 | { | |
6119e7d5 SP |
640 | graphite_dim_t result = 1 + 2 * level; |
641 | ||
642 | gcc_assert (result < pbb_nb_scattering_transform (pbb)); | |
643 | return result; | |
644 | } | |
645 | ||
646 | /* The scattering dimension of PBB corresponding to the static | |
647 | sequence of the loop level LEVEL. */ | |
648 | ||
33ad93b9 | 649 | static inline graphite_dim_t |
6119e7d5 SP |
650 | psct_static_dim (poly_bb_p pbb, graphite_dim_t level) |
651 | { | |
652 | graphite_dim_t result = 2 * level; | |
baf4b881 KT |
653 | |
654 | gcc_assert (result < pbb_nb_scattering_transform (pbb)); | |
655 | return result; | |
656 | } | |
657 | ||
2abae5f1 SP |
658 | /* Adds to the transformed scattering polyhedron of PBB a new local |
659 | variable and returns its index. */ | |
660 | ||
661 | static inline graphite_dim_t | |
33ad93b9 | 662 | psct_add_local_variable (poly_bb_p pbb ATTRIBUTE_UNUSED) |
2abae5f1 | 663 | { |
33ad93b9 RG |
664 | gcc_unreachable (); |
665 | return 0; | |
2abae5f1 SP |
666 | } |
667 | ||
a36d12e2 | 668 | typedef struct lst *lst_p; |
a36d12e2 SP |
669 | |
670 | /* Loops and Statements Tree. */ | |
671 | struct lst { | |
672 | ||
673 | /* LOOP_P is true when an LST node is a loop. */ | |
674 | bool loop_p; | |
675 | ||
676 | /* A pointer to the loop that contains this node. */ | |
677 | lst_p loop_father; | |
678 | ||
eaffa762 | 679 | /* The sum of all the memory strides for an LST loop. */ |
e262fdda | 680 | mpz_t memory_strides; |
eaffa762 | 681 | |
a36d12e2 SP |
682 | /* Loop nodes contain a sequence SEQ of LST nodes, statements |
683 | contain a pointer to their polyhedral representation PBB. */ | |
684 | union { | |
685 | poly_bb_p pbb; | |
9771b263 | 686 | vec<lst_p> seq; |
a36d12e2 SP |
687 | } node; |
688 | }; | |
689 | ||
690 | #define LST_LOOP_P(LST) ((LST)->loop_p) | |
691 | #define LST_LOOP_FATHER(LST) ((LST)->loop_father) | |
692 | #define LST_PBB(LST) ((LST)->node.pbb) | |
693 | #define LST_SEQ(LST) ((LST)->node.seq) | |
eaffa762 | 694 | #define LST_LOOP_MEMORY_STRIDES(LST) ((LST)->memory_strides) |
a36d12e2 SP |
695 | |
696 | void scop_to_lst (scop_p); | |
697 | void print_lst (FILE *, lst_p, int); | |
698 | void debug_lst (lst_p); | |
bfa00f48 | 699 | void dot_lst (lst_p); |
a36d12e2 SP |
700 | |
701 | /* Creates a new LST loop with SEQ. */ | |
702 | ||
703 | static inline lst_p | |
9771b263 | 704 | new_lst_loop (vec<lst_p> seq) |
a36d12e2 SP |
705 | { |
706 | lst_p lst = XNEW (struct lst); | |
707 | int i; | |
708 | lst_p l; | |
709 | ||
710 | LST_LOOP_P (lst) = true; | |
711 | LST_SEQ (lst) = seq; | |
712 | LST_LOOP_FATHER (lst) = NULL; | |
a0bb35c7 AS |
713 | mpz_init (LST_LOOP_MEMORY_STRIDES (lst)); |
714 | mpz_set_si (LST_LOOP_MEMORY_STRIDES (lst), -1); | |
a36d12e2 | 715 | |
9771b263 | 716 | for (i = 0; seq.iterate (i, &l); i++) |
a36d12e2 SP |
717 | LST_LOOP_FATHER (l) = lst; |
718 | ||
719 | return lst; | |
720 | } | |
721 | ||
722 | /* Creates a new LST statement with PBB. */ | |
723 | ||
724 | static inline lst_p | |
725 | new_lst_stmt (poly_bb_p pbb) | |
726 | { | |
727 | lst_p lst = XNEW (struct lst); | |
728 | ||
729 | LST_LOOP_P (lst) = false; | |
730 | LST_PBB (lst) = pbb; | |
731 | LST_LOOP_FATHER (lst) = NULL; | |
732 | return lst; | |
733 | } | |
734 | ||
f70de156 SP |
735 | /* Frees the memory used by LST. */ |
736 | ||
737 | static inline void | |
738 | free_lst (lst_p lst) | |
739 | { | |
740 | if (!lst) | |
741 | return; | |
742 | ||
743 | if (LST_LOOP_P (lst)) | |
744 | { | |
745 | int i; | |
746 | lst_p l; | |
747 | ||
9771b263 | 748 | for (i = 0; LST_SEQ (lst).iterate (i, &l); i++) |
f70de156 SP |
749 | free_lst (l); |
750 | ||
a0bb35c7 | 751 | mpz_clear (LST_LOOP_MEMORY_STRIDES (lst)); |
9771b263 | 752 | LST_SEQ (lst).release (); |
f70de156 SP |
753 | } |
754 | ||
755 | free (lst); | |
756 | } | |
757 | ||
a36d12e2 SP |
758 | /* Returns a copy of LST. */ |
759 | ||
760 | static inline lst_p | |
761 | copy_lst (lst_p lst) | |
762 | { | |
763 | if (!lst) | |
764 | return NULL; | |
765 | ||
766 | if (LST_LOOP_P (lst)) | |
75b63a91 SP |
767 | { |
768 | int i; | |
769 | lst_p l; | |
9771b263 DN |
770 | vec<lst_p> seq; |
771 | seq.create (5); | |
75b63a91 | 772 | |
9771b263 DN |
773 | for (i = 0; LST_SEQ (lst).iterate (i, &l); i++) |
774 | seq.safe_push (copy_lst (l)); | |
75b63a91 SP |
775 | |
776 | return new_lst_loop (seq); | |
777 | } | |
a36d12e2 SP |
778 | |
779 | return new_lst_stmt (LST_PBB (lst)); | |
780 | } | |
781 | ||
13ae6f91 SP |
782 | /* Adds a new loop under the loop LST. */ |
783 | ||
784 | static inline void | |
785 | lst_add_loop_under_loop (lst_p lst) | |
786 | { | |
9771b263 DN |
787 | vec<lst_p> seq; |
788 | seq.create (1); | |
13ae6f91 SP |
789 | lst_p l = new_lst_loop (LST_SEQ (lst)); |
790 | ||
791 | gcc_assert (LST_LOOP_P (lst)); | |
792 | ||
793 | LST_LOOP_FATHER (l) = lst; | |
9771b263 | 794 | seq.quick_push (l); |
13ae6f91 SP |
795 | LST_SEQ (lst) = seq; |
796 | } | |
797 | ||
a36d12e2 SP |
798 | /* Returns the loop depth of LST. */ |
799 | ||
800 | static inline int | |
801 | lst_depth (lst_p lst) | |
802 | { | |
803 | if (!lst) | |
5c6c42c9 SP |
804 | return -2; |
805 | ||
806 | /* The depth of the outermost "fake" loop is -1. This outermost | |
807 | loop does not have a loop father and it is just a container, as | |
808 | in the loop representation of GCC. */ | |
809 | if (!LST_LOOP_FATHER (lst)) | |
a36d12e2 SP |
810 | return -1; |
811 | ||
812 | return lst_depth (LST_LOOP_FATHER (lst)) + 1; | |
813 | } | |
814 | ||
815 | /* Returns the Dewey number for LST. */ | |
816 | ||
817 | static inline int | |
818 | lst_dewey_number (lst_p lst) | |
819 | { | |
820 | int i; | |
821 | lst_p l; | |
822 | ||
823 | if (!lst) | |
824 | return -1; | |
825 | ||
826 | if (!LST_LOOP_FATHER (lst)) | |
827 | return 0; | |
828 | ||
9771b263 | 829 | FOR_EACH_VEC_ELT (LST_SEQ (LST_LOOP_FATHER (lst)), i, l) |
a36d12e2 SP |
830 | if (l == lst) |
831 | return i; | |
832 | ||
833 | return -1; | |
834 | } | |
835 | ||
6119e7d5 SP |
836 | /* Returns the Dewey number of LST at depth DEPTH. */ |
837 | ||
838 | static inline int | |
839 | lst_dewey_number_at_depth (lst_p lst, int depth) | |
840 | { | |
841 | gcc_assert (lst && depth >= 0 && lst_depth (lst) <= depth); | |
842 | ||
843 | if (lst_depth (lst) == depth) | |
844 | return lst_dewey_number (lst); | |
845 | ||
846 | return lst_dewey_number_at_depth (LST_LOOP_FATHER (lst), depth); | |
847 | } | |
848 | ||
7b7f2ca7 SP |
849 | /* Returns the predecessor of LST in the sequence of its loop father. |
850 | Returns NULL if LST is the first statement in the sequence. */ | |
851 | ||
852 | static inline lst_p | |
853 | lst_pred (lst_p lst) | |
854 | { | |
855 | int dewey; | |
856 | lst_p father; | |
857 | ||
858 | if (!lst || !LST_LOOP_FATHER (lst)) | |
859 | return NULL; | |
860 | ||
861 | dewey = lst_dewey_number (lst); | |
862 | if (dewey == 0) | |
863 | return NULL; | |
864 | ||
865 | father = LST_LOOP_FATHER (lst); | |
9771b263 | 866 | return LST_SEQ (father)[dewey - 1]; |
7b7f2ca7 SP |
867 | } |
868 | ||
869 | /* Returns the successor of LST in the sequence of its loop father. | |
870 | Returns NULL if there is none. */ | |
871 | ||
872 | static inline lst_p | |
873 | lst_succ (lst_p lst) | |
874 | { | |
875 | int dewey; | |
876 | lst_p father; | |
877 | ||
878 | if (!lst || !LST_LOOP_FATHER (lst)) | |
879 | return NULL; | |
880 | ||
881 | dewey = lst_dewey_number (lst); | |
882 | father = LST_LOOP_FATHER (lst); | |
883 | ||
9771b263 | 884 | if (LST_SEQ (father).length () == (unsigned) dewey + 1) |
7b7f2ca7 SP |
885 | return NULL; |
886 | ||
9771b263 | 887 | return LST_SEQ (father)[dewey + 1]; |
7b7f2ca7 SP |
888 | } |
889 | ||
890 | ||
a0517b76 SP |
891 | /* Return the LST node corresponding to PBB. */ |
892 | ||
893 | static inline lst_p | |
894 | lst_find_pbb (lst_p lst, poly_bb_p pbb) | |
895 | { | |
896 | int i; | |
897 | lst_p l; | |
898 | ||
899 | if (!lst) | |
900 | return NULL; | |
901 | ||
6119e7d5 SP |
902 | if (!LST_LOOP_P (lst)) |
903 | return (pbb == LST_PBB (lst)) ? lst : NULL; | |
904 | ||
9771b263 | 905 | for (i = 0; LST_SEQ (lst).iterate (i, &l); i++) |
6119e7d5 SP |
906 | { |
907 | lst_p res = lst_find_pbb (l, pbb); | |
908 | if (res) | |
909 | return res; | |
910 | } | |
a0517b76 SP |
911 | |
912 | return NULL; | |
913 | } | |
914 | ||
915 | /* Return the LST node corresponding to the loop around STMT at depth | |
916 | LOOP_DEPTH. */ | |
917 | ||
918 | static inline lst_p | |
919 | find_lst_loop (lst_p stmt, int loop_depth) | |
920 | { | |
921 | lst_p loop = LST_LOOP_FATHER (stmt); | |
922 | ||
923 | gcc_assert (loop_depth >= 0); | |
924 | ||
925 | while (loop_depth < lst_depth (loop)) | |
926 | loop = LST_LOOP_FATHER (loop); | |
927 | ||
928 | return loop; | |
929 | } | |
930 | ||
98af4c9f | 931 | /* Return the first LST representing a PBB statement in LST. */ |
13ae6f91 SP |
932 | |
933 | static inline lst_p | |
934 | lst_find_first_pbb (lst_p lst) | |
935 | { | |
936 | int i; | |
937 | lst_p l; | |
938 | ||
939 | if (!lst) | |
940 | return NULL; | |
941 | ||
6119e7d5 SP |
942 | if (!LST_LOOP_P (lst)) |
943 | return lst; | |
944 | ||
9771b263 | 945 | for (i = 0; LST_SEQ (lst).iterate (i, &l); i++) |
6119e7d5 SP |
946 | { |
947 | lst_p res = lst_find_first_pbb (l); | |
948 | if (res) | |
949 | return res; | |
950 | } | |
951 | ||
6119e7d5 SP |
952 | return NULL; |
953 | } | |
954 | ||
98af4c9f | 955 | /* Returns true when LST is a loop that does not contain |
7b7f2ca7 SP |
956 | statements. */ |
957 | ||
958 | static inline bool | |
959 | lst_empty_p (lst_p lst) | |
960 | { | |
961 | return !lst_find_first_pbb (lst); | |
962 | } | |
963 | ||
98af4c9f | 964 | /* Return the last LST representing a PBB statement in LST. */ |
6119e7d5 SP |
965 | |
966 | static inline lst_p | |
967 | lst_find_last_pbb (lst_p lst) | |
968 | { | |
969 | int i; | |
970 | lst_p l, res = NULL; | |
971 | ||
972 | if (!lst) | |
973 | return NULL; | |
974 | ||
975 | if (!LST_LOOP_P (lst)) | |
976 | return lst; | |
977 | ||
9771b263 | 978 | for (i = 0; LST_SEQ (lst).iterate (i, &l); i++) |
6119e7d5 SP |
979 | { |
980 | lst_p last = lst_find_last_pbb (l); | |
981 | ||
982 | if (last) | |
983 | res = last; | |
984 | } | |
985 | ||
986 | gcc_assert (res); | |
987 | return res; | |
988 | } | |
989 | ||
990 | /* Returns true if LOOP contains LST, in other words, if LST is nested | |
991 | in LOOP. */ | |
992 | ||
993 | static inline bool | |
994 | lst_contains_p (lst_p loop, lst_p lst) | |
995 | { | |
996 | if (!loop || !lst || !LST_LOOP_P (loop)) | |
997 | return false; | |
998 | ||
999 | if (loop == lst) | |
1000 | return true; | |
1001 | ||
1002 | return lst_contains_p (loop, LST_LOOP_FATHER (lst)); | |
1003 | } | |
1004 | ||
1005 | /* Returns true if LOOP contains PBB, in other words, if PBB is nested | |
1006 | in LOOP. */ | |
1007 | ||
1008 | static inline bool | |
1009 | lst_contains_pbb (lst_p loop, poly_bb_p pbb) | |
1010 | { | |
1011 | return lst_find_pbb (loop, pbb) ? true : false; | |
1012 | } | |
1013 | ||
1014 | /* Creates a loop nest of depth NB_LOOPS containing LST. */ | |
1015 | ||
1016 | static inline lst_p | |
1017 | lst_create_nest (int nb_loops, lst_p lst) | |
1018 | { | |
1019 | lst_p res, loop; | |
9771b263 | 1020 | vec<lst_p> seq; |
6119e7d5 SP |
1021 | |
1022 | if (nb_loops == 0) | |
1023 | return lst; | |
1024 | ||
9771b263 | 1025 | seq.create (1); |
6119e7d5 | 1026 | loop = lst_create_nest (nb_loops - 1, lst); |
9771b263 | 1027 | seq.quick_push (loop); |
6119e7d5 SP |
1028 | res = new_lst_loop (seq); |
1029 | LST_LOOP_FATHER (loop) = res; | |
1030 | ||
1031 | return res; | |
1032 | } | |
1033 | ||
1034 | /* Removes LST from the sequence of statements of its loop father. */ | |
1035 | ||
1036 | static inline void | |
1037 | lst_remove_from_sequence (lst_p lst) | |
1038 | { | |
1039 | lst_p father = LST_LOOP_FATHER (lst); | |
1040 | int dewey = lst_dewey_number (lst); | |
1041 | ||
1042 | gcc_assert (lst && father && dewey >= 0); | |
1043 | ||
9771b263 | 1044 | LST_SEQ (father).ordered_remove (dewey); |
6119e7d5 SP |
1045 | LST_LOOP_FATHER (lst) = NULL; |
1046 | } | |
1047 | ||
98af4c9f SP |
1048 | /* Removes the loop LST and inline its body in the father loop. */ |
1049 | ||
1050 | static inline void | |
1051 | lst_remove_loop_and_inline_stmts_in_loop_father (lst_p lst) | |
1052 | { | |
1053 | lst_p l, father = LST_LOOP_FATHER (lst); | |
1054 | int i, dewey = lst_dewey_number (lst); | |
1055 | ||
1056 | gcc_assert (lst && father && dewey >= 0); | |
1057 | ||
9771b263 | 1058 | LST_SEQ (father).ordered_remove (dewey); |
98af4c9f SP |
1059 | LST_LOOP_FATHER (lst) = NULL; |
1060 | ||
9771b263 | 1061 | FOR_EACH_VEC_ELT (LST_SEQ (lst), i, l) |
98af4c9f | 1062 | { |
9771b263 | 1063 | LST_SEQ (father).safe_insert (dewey + i, l); |
98af4c9f SP |
1064 | LST_LOOP_FATHER (l) = father; |
1065 | } | |
1066 | } | |
1067 | ||
22280f63 SP |
1068 | /* Sets NITER to the upper bound approximation of the number of |
1069 | iterations of loop LST. */ | |
1070 | ||
1071 | static inline void | |
1072 | lst_niter_for_loop (lst_p lst, mpz_t niter) | |
1073 | { | |
1074 | int depth = lst_depth (lst); | |
1075 | poly_bb_p pbb = LST_PBB (lst_find_first_pbb (lst)); | |
1076 | ||
1077 | gcc_assert (LST_LOOP_P (lst)); | |
1078 | pbb_number_of_iterations_at_time (pbb, psct_dynamic_dim (pbb, depth), niter); | |
1079 | } | |
1080 | ||
6119e7d5 SP |
1081 | /* Updates the scattering of PBB to be at the DEWEY number in the loop |
1082 | at depth LEVEL. */ | |
1083 | ||
1084 | static inline void | |
1085 | pbb_update_scattering (poly_bb_p pbb, graphite_dim_t level, int dewey) | |
1086 | { | |
33ad93b9 RG |
1087 | graphite_dim_t sched = psct_static_dim (pbb, level); |
1088 | isl_space *d = isl_map_get_space (pbb->transformed); | |
1089 | isl_space *d1 = isl_space_range (d); | |
1090 | unsigned i, n = isl_space_dim (d1, isl_dim_out); | |
1091 | isl_space *d2 = isl_space_add_dims (d1, isl_dim_in, n); | |
1092 | isl_map *x = isl_map_universe (d2); | |
1093 | ||
1094 | x = isl_map_fix_si (x, isl_dim_out, sched, dewey); | |
6119e7d5 | 1095 | |
33ad93b9 RG |
1096 | for (i = 0; i < n; i++) |
1097 | if (i != sched) | |
1098 | x = isl_map_equate (x, isl_dim_in, i, isl_dim_out, i); | |
6119e7d5 | 1099 | |
33ad93b9 | 1100 | pbb->transformed = isl_map_apply_range (pbb->transformed, x); |
6119e7d5 SP |
1101 | } |
1102 | ||
1103 | /* Updates the scattering of all the PBBs under LST to be at the DEWEY | |
1104 | number in the loop at depth LEVEL. */ | |
1105 | ||
1106 | static inline void | |
1107 | lst_update_scattering_under (lst_p lst, int level, int dewey) | |
1108 | { | |
1109 | int i; | |
1110 | lst_p l; | |
1111 | ||
1112 | gcc_assert (lst && level >= 0 && dewey >= 0); | |
1113 | ||
13ae6f91 | 1114 | if (LST_LOOP_P (lst)) |
9771b263 | 1115 | for (i = 0; LST_SEQ (lst).iterate (i, &l); i++) |
6119e7d5 SP |
1116 | lst_update_scattering_under (l, level, dewey); |
1117 | else | |
1118 | pbb_update_scattering (LST_PBB (lst), level, dewey); | |
1119 | } | |
1120 | ||
6119e7d5 SP |
1121 | /* Updates the all the scattering levels of all the PBBs under |
1122 | LST. */ | |
1123 | ||
1124 | static inline void | |
1125 | lst_update_scattering (lst_p lst) | |
1126 | { | |
1127 | int i; | |
1128 | lst_p l; | |
1129 | ||
b8745012 | 1130 | if (!lst) |
6119e7d5 SP |
1131 | return; |
1132 | ||
1133 | if (LST_LOOP_FATHER (lst)) | |
b8745012 SP |
1134 | { |
1135 | lst_p father = LST_LOOP_FATHER (lst); | |
1136 | int dewey = lst_dewey_number (lst); | |
1137 | int level = lst_depth (lst); | |
6119e7d5 | 1138 | |
b8745012 SP |
1139 | gcc_assert (lst && father && dewey >= 0 && level >= 0); |
1140 | ||
9771b263 | 1141 | for (i = dewey; LST_SEQ (father).iterate (i, &l); i++) |
b8745012 SP |
1142 | lst_update_scattering_under (l, level, i); |
1143 | } | |
1144 | ||
1145 | if (LST_LOOP_P (lst)) | |
9771b263 | 1146 | for (i = 0; LST_SEQ (lst).iterate (i, &l); i++) |
b8745012 | 1147 | lst_update_scattering (l); |
6119e7d5 SP |
1148 | } |
1149 | ||
1150 | /* Inserts LST1 before LST2 if BEFORE is true; inserts LST1 after LST2 | |
1151 | if BEFORE is false. */ | |
1152 | ||
1153 | static inline void | |
1154 | lst_insert_in_sequence (lst_p lst1, lst_p lst2, bool before) | |
1155 | { | |
7b7f2ca7 SP |
1156 | lst_p father; |
1157 | int dewey; | |
6119e7d5 | 1158 | |
7b7f2ca7 SP |
1159 | /* Do not insert empty loops. */ |
1160 | if (!lst1 || lst_empty_p (lst1)) | |
1161 | return; | |
1162 | ||
1163 | father = LST_LOOP_FATHER (lst2); | |
1164 | dewey = lst_dewey_number (lst2); | |
1165 | ||
1166 | gcc_assert (lst2 && father && dewey >= 0); | |
6119e7d5 | 1167 | |
9771b263 | 1168 | LST_SEQ (father).safe_insert (before ? dewey : dewey + 1, lst1); |
6119e7d5 SP |
1169 | LST_LOOP_FATHER (lst1) = father; |
1170 | } | |
1171 | ||
7b7f2ca7 SP |
1172 | /* Replaces LST1 with LST2. */ |
1173 | ||
1174 | static inline void | |
1175 | lst_replace (lst_p lst1, lst_p lst2) | |
1176 | { | |
1177 | lst_p father; | |
1178 | int dewey; | |
1179 | ||
1180 | if (!lst2 || lst_empty_p (lst2)) | |
1181 | return; | |
1182 | ||
1183 | father = LST_LOOP_FATHER (lst1); | |
1184 | dewey = lst_dewey_number (lst1); | |
1185 | LST_LOOP_FATHER (lst2) = father; | |
9771b263 | 1186 | LST_SEQ (father)[dewey] = lst2; |
7b7f2ca7 SP |
1187 | } |
1188 | ||
1189 | /* Returns a copy of ROOT where LST has been replaced by a copy of the | |
1190 | LSTs A B C in this sequence. */ | |
1191 | ||
1192 | static inline lst_p | |
1193 | lst_substitute_3 (lst_p root, lst_p lst, lst_p a, lst_p b, lst_p c) | |
1194 | { | |
1195 | int i; | |
1196 | lst_p l; | |
9771b263 | 1197 | vec<lst_p> seq; |
7b7f2ca7 SP |
1198 | |
1199 | if (!root) | |
1200 | return NULL; | |
1201 | ||
1202 | gcc_assert (lst && root != lst); | |
1203 | ||
1204 | if (!LST_LOOP_P (root)) | |
1205 | return new_lst_stmt (LST_PBB (root)); | |
1206 | ||
9771b263 | 1207 | seq.create (5); |
7b7f2ca7 | 1208 | |
9771b263 | 1209 | for (i = 0; LST_SEQ (root).iterate (i, &l); i++) |
7b7f2ca7 | 1210 | if (l != lst) |
9771b263 | 1211 | seq.safe_push (lst_substitute_3 (l, lst, a, b, c)); |
7b7f2ca7 SP |
1212 | else |
1213 | { | |
1214 | if (!lst_empty_p (a)) | |
9771b263 | 1215 | seq.safe_push (copy_lst (a)); |
7b7f2ca7 | 1216 | if (!lst_empty_p (b)) |
9771b263 | 1217 | seq.safe_push (copy_lst (b)); |
7b7f2ca7 | 1218 | if (!lst_empty_p (c)) |
9771b263 | 1219 | seq.safe_push (copy_lst (c)); |
7b7f2ca7 SP |
1220 | } |
1221 | ||
1222 | return new_lst_loop (seq); | |
1223 | } | |
1224 | ||
6119e7d5 SP |
1225 | /* Moves LST before LOOP if BEFORE is true, and after the LOOP if |
1226 | BEFORE is false. */ | |
1227 | ||
1228 | static inline void | |
1229 | lst_distribute_lst (lst_p loop, lst_p lst, bool before) | |
1230 | { | |
1231 | int loop_depth = lst_depth (loop); | |
1232 | int depth = lst_depth (lst); | |
1233 | int nb_loops = depth - loop_depth; | |
1234 | ||
1235 | gcc_assert (lst && loop && LST_LOOP_P (loop) && nb_loops > 0); | |
1236 | ||
1237 | lst_remove_from_sequence (lst); | |
1238 | lst_insert_in_sequence (lst_create_nest (nb_loops, lst), loop, before); | |
1239 | } | |
1240 | ||
1241 | /* Removes from LOOP all the statements before/after and including PBB | |
1242 | if BEFORE is true/false. Returns the negation of BEFORE when the | |
1243 | statement PBB has been found. */ | |
1244 | ||
1245 | static inline bool | |
1246 | lst_remove_all_before_including_pbb (lst_p loop, poly_bb_p pbb, bool before) | |
1247 | { | |
1248 | int i; | |
1249 | lst_p l; | |
1250 | ||
1251 | if (!loop || !LST_LOOP_P (loop)) | |
1252 | return before; | |
1253 | ||
9771b263 | 1254 | for (i = 0; LST_SEQ (loop).iterate (i, &l);) |
6119e7d5 SP |
1255 | if (LST_LOOP_P (l)) |
1256 | { | |
1257 | before = lst_remove_all_before_including_pbb (l, pbb, before); | |
1258 | ||
9771b263 | 1259 | if (LST_SEQ (l).length () == 0) |
6119e7d5 | 1260 | { |
9771b263 | 1261 | LST_SEQ (loop).ordered_remove (i); |
6119e7d5 SP |
1262 | free_lst (l); |
1263 | } | |
1264 | else | |
1265 | i++; | |
1266 | } | |
1267 | else | |
13ae6f91 | 1268 | { |
6119e7d5 SP |
1269 | if (before) |
1270 | { | |
1271 | if (LST_PBB (l) == pbb) | |
1272 | before = false; | |
1273 | ||
9771b263 | 1274 | LST_SEQ (loop).ordered_remove (i); |
6119e7d5 SP |
1275 | free_lst (l); |
1276 | } | |
1277 | else if (LST_PBB (l) == pbb) | |
1278 | { | |
1279 | before = true; | |
9771b263 | 1280 | LST_SEQ (loop).ordered_remove (i); |
6119e7d5 SP |
1281 | free_lst (l); |
1282 | } | |
1283 | else | |
1284 | i++; | |
13ae6f91 SP |
1285 | } |
1286 | ||
6119e7d5 SP |
1287 | return before; |
1288 | } | |
1289 | ||
1290 | /* Removes from LOOP all the statements before/after and excluding PBB | |
1291 | if BEFORE is true/false; Returns the negation of BEFORE when the | |
1292 | statement PBB has been found. */ | |
1293 | ||
1294 | static inline bool | |
1295 | lst_remove_all_before_excluding_pbb (lst_p loop, poly_bb_p pbb, bool before) | |
1296 | { | |
1297 | int i; | |
1298 | lst_p l; | |
1299 | ||
1300 | if (!loop || !LST_LOOP_P (loop)) | |
1301 | return before; | |
1302 | ||
9771b263 | 1303 | for (i = 0; LST_SEQ (loop).iterate (i, &l);) |
6119e7d5 SP |
1304 | if (LST_LOOP_P (l)) |
1305 | { | |
1306 | before = lst_remove_all_before_excluding_pbb (l, pbb, before); | |
1307 | ||
9771b263 | 1308 | if (LST_SEQ (l).length () == 0) |
6119e7d5 | 1309 | { |
9771b263 | 1310 | LST_SEQ (loop).ordered_remove (i); |
6119e7d5 SP |
1311 | free_lst (l); |
1312 | continue; | |
1313 | } | |
1314 | ||
1315 | i++; | |
1316 | } | |
1317 | else | |
1318 | { | |
1319 | if (before && LST_PBB (l) != pbb) | |
1320 | { | |
9771b263 | 1321 | LST_SEQ (loop).ordered_remove (i); |
6119e7d5 SP |
1322 | free_lst (l); |
1323 | continue; | |
1324 | } | |
1325 | ||
1326 | i++; | |
1327 | ||
1328 | if (LST_PBB (l) == pbb) | |
1329 | before = before ? false : true; | |
1330 | } | |
1331 | ||
1332 | return before; | |
13ae6f91 | 1333 | } |
a0517b76 | 1334 | |
2abae5f1 SP |
1335 | /* A SCOP is a Static Control Part of the program, simple enough to be |
1336 | represented in polyhedral form. */ | |
1337 | struct scop | |
1338 | { | |
1339 | /* A SCOP is defined as a SESE region. */ | |
1340 | void *region; | |
1341 | ||
1342 | /* Number of parameters in SCoP. */ | |
1343 | graphite_dim_t nb_params; | |
1344 | ||
1345 | /* All the basic blocks in this scop that contain memory references | |
1346 | and that will be represented as statements in the polyhedral | |
1347 | representation. */ | |
9771b263 | 1348 | vec<poly_bb_p> bbs; |
2abae5f1 | 1349 | |
74715a9b SP |
1350 | /* Original, transformed and saved schedules. */ |
1351 | lst_p original_schedule, transformed_schedule, saved_schedule; | |
a36d12e2 | 1352 | |
2abae5f1 SP |
1353 | /* The context describes known restrictions concerning the parameters |
1354 | and relations in between the parameters. | |
1355 | ||
1356 | void f (int8_t a, uint_16_t b) { | |
1357 | c = 2 a + b; | |
1358 | ... | |
1359 | } | |
1360 | ||
1361 | Here we can add these restrictions to the context: | |
1362 | ||
1363 | -128 >= a >= 127 | |
1364 | 0 >= b >= 65,535 | |
1365 | c = 2a + b */ | |
33ad93b9 RG |
1366 | isl_set *context; |
1367 | ||
1368 | /* The context used internally by ISL. */ | |
1369 | isl_ctx *ctx; | |
1370 | ||
1371 | /* The original dependence relations: | |
1372 | RAW are read after write dependences, | |
1373 | WAR are write after read dependences, | |
1374 | WAW are write after write dependences. */ | |
1375 | isl_union_map *must_raw, *may_raw, *must_raw_no_source, *may_raw_no_source, | |
1376 | *must_war, *may_war, *must_war_no_source, *may_war_no_source, | |
1377 | *must_waw, *may_waw, *must_waw_no_source, *may_waw_no_source; | |
2abae5f1 | 1378 | |
a1954f72 SP |
1379 | /* True when the scop has been converted to its polyhedral |
1380 | representation. */ | |
1381 | bool poly_scop_p; | |
2abae5f1 SP |
1382 | }; |
1383 | ||
1384 | #define SCOP_BBS(S) (S->bbs) | |
1385 | #define SCOP_REGION(S) ((sese) S->region) | |
33ad93b9 | 1386 | #define SCOP_CONTEXT(S) (NULL) |
a36d12e2 SP |
1387 | #define SCOP_ORIGINAL_SCHEDULE(S) (S->original_schedule) |
1388 | #define SCOP_TRANSFORMED_SCHEDULE(S) (S->transformed_schedule) | |
74715a9b | 1389 | #define SCOP_SAVED_SCHEDULE(S) (S->saved_schedule) |
a1954f72 | 1390 | #define POLY_SCOP_P(S) (S->poly_scop_p) |
2abae5f1 SP |
1391 | |
1392 | extern scop_p new_scop (void *); | |
1393 | extern void free_scop (scop_p); | |
9771b263 | 1394 | extern void free_scops (vec<scop_p> ); |
2abae5f1 SP |
1395 | extern void print_generated_program (FILE *, scop_p); |
1396 | extern void debug_generated_program (scop_p); | |
40bf935e SP |
1397 | extern void print_scattering_function (FILE *, poly_bb_p, int); |
1398 | extern void print_scattering_functions (FILE *, scop_p, int); | |
1399 | extern void debug_scattering_function (poly_bb_p, int); | |
1400 | extern void debug_scattering_functions (scop_p, int); | |
2abae5f1 SP |
1401 | extern int scop_max_loop_depth (scop_p); |
1402 | extern int unify_scattering_dimensions (scop_p); | |
1403 | extern bool apply_poly_transforms (scop_p); | |
1404 | extern bool graphite_legal_transform (scop_p); | |
c498b9b9 | 1405 | extern void cloog_checksum (scop_p); |
2abae5f1 SP |
1406 | |
1407 | /* Set the region of SCOP to REGION. */ | |
1408 | ||
1409 | static inline void | |
1410 | scop_set_region (scop_p scop, void *region) | |
1411 | { | |
1412 | scop->region = region; | |
1413 | } | |
1414 | ||
1415 | /* Returns the number of parameters for SCOP. */ | |
1416 | ||
1417 | static inline graphite_dim_t | |
1418 | scop_nb_params (scop_p scop) | |
1419 | { | |
1420 | return scop->nb_params; | |
1421 | } | |
1422 | ||
1423 | /* Set the number of params of SCOP to NB_PARAMS. */ | |
1424 | ||
1425 | static inline void | |
1426 | scop_set_nb_params (scop_p scop, graphite_dim_t nb_params) | |
1427 | { | |
1428 | scop->nb_params = nb_params; | |
1429 | } | |
1430 | ||
f4648ed1 SP |
1431 | /* Allocates a new empty poly_scattering structure. */ |
1432 | ||
1433 | static inline poly_scattering_p | |
1434 | poly_scattering_new (void) | |
1435 | { | |
1436 | poly_scattering_p res = XNEW (struct poly_scattering); | |
1437 | ||
f4648ed1 SP |
1438 | res->nb_local_variables = 0; |
1439 | res->nb_scattering = 0; | |
1440 | return res; | |
1441 | } | |
1442 | ||
1443 | /* Free a poly_scattering structure. */ | |
1444 | ||
1445 | static inline void | |
1446 | poly_scattering_free (poly_scattering_p s) | |
1447 | { | |
f4648ed1 SP |
1448 | free (s); |
1449 | } | |
1450 | ||
1451 | /* Copies S and return a new scattering. */ | |
1452 | ||
1453 | static inline poly_scattering_p | |
1454 | poly_scattering_copy (poly_scattering_p s) | |
1455 | { | |
1456 | poly_scattering_p res = poly_scattering_new (); | |
1457 | ||
f4648ed1 SP |
1458 | res->nb_local_variables = s->nb_local_variables; |
1459 | res->nb_scattering = s->nb_scattering; | |
1460 | return res; | |
1461 | } | |
1462 | ||
1463 | /* Saves the transformed scattering of PBB. */ | |
1464 | ||
1465 | static inline void | |
1466 | store_scattering_pbb (poly_bb_p pbb) | |
1467 | { | |
33ad93b9 RG |
1468 | isl_map_free (pbb->saved); |
1469 | pbb->saved = isl_map_copy (pbb->transformed); | |
f4648ed1 SP |
1470 | } |
1471 | ||
74715a9b SP |
1472 | /* Stores the SCOP_TRANSFORMED_SCHEDULE to SCOP_SAVED_SCHEDULE. */ |
1473 | ||
1474 | static inline void | |
1475 | store_lst_schedule (scop_p scop) | |
1476 | { | |
f70de156 SP |
1477 | if (SCOP_SAVED_SCHEDULE (scop)) |
1478 | free_lst (SCOP_SAVED_SCHEDULE (scop)); | |
1479 | ||
74715a9b SP |
1480 | SCOP_SAVED_SCHEDULE (scop) = copy_lst (SCOP_TRANSFORMED_SCHEDULE (scop)); |
1481 | } | |
1482 | ||
1483 | /* Restores the SCOP_TRANSFORMED_SCHEDULE from SCOP_SAVED_SCHEDULE. */ | |
1484 | ||
1485 | static inline void | |
1486 | restore_lst_schedule (scop_p scop) | |
1487 | { | |
f70de156 SP |
1488 | if (SCOP_TRANSFORMED_SCHEDULE (scop)) |
1489 | free_lst (SCOP_TRANSFORMED_SCHEDULE (scop)); | |
1490 | ||
74715a9b SP |
1491 | SCOP_TRANSFORMED_SCHEDULE (scop) = copy_lst (SCOP_SAVED_SCHEDULE (scop)); |
1492 | } | |
1493 | ||
f4648ed1 SP |
1494 | /* Saves the scattering for all the pbbs in the SCOP. */ |
1495 | ||
1496 | static inline void | |
1497 | store_scattering (scop_p scop) | |
1498 | { | |
1499 | int i; | |
1500 | poly_bb_p pbb; | |
1501 | ||
9771b263 | 1502 | for (i = 0; SCOP_BBS (scop).iterate (i, &pbb); i++) |
f4648ed1 | 1503 | store_scattering_pbb (pbb); |
74715a9b SP |
1504 | |
1505 | store_lst_schedule (scop); | |
f4648ed1 SP |
1506 | } |
1507 | ||
1508 | /* Restores the scattering of PBB. */ | |
1509 | ||
1510 | static inline void | |
1511 | restore_scattering_pbb (poly_bb_p pbb) | |
1512 | { | |
33ad93b9 | 1513 | gcc_assert (pbb->saved); |
f4648ed1 | 1514 | |
33ad93b9 RG |
1515 | isl_map_free (pbb->transformed); |
1516 | pbb->transformed = isl_map_copy (pbb->saved); | |
f4648ed1 SP |
1517 | } |
1518 | ||
1519 | /* Restores the scattering for all the pbbs in the SCOP. */ | |
1520 | ||
1521 | static inline void | |
1522 | restore_scattering (scop_p scop) | |
1523 | { | |
1524 | int i; | |
1525 | poly_bb_p pbb; | |
1526 | ||
9771b263 | 1527 | for (i = 0; SCOP_BBS (scop).iterate (i, &pbb); i++) |
f4648ed1 | 1528 | restore_scattering_pbb (pbb); |
74715a9b SP |
1529 | |
1530 | restore_lst_schedule (scop); | |
f4648ed1 SP |
1531 | } |
1532 | ||
33ad93b9 | 1533 | bool graphite_legal_transform (scop_p); |
33ad93b9 | 1534 | isl_map *reverse_loop_at_level (poly_bb_p, int); |
9771b263 | 1535 | isl_union_map *reverse_loop_for_pbbs (scop_p, vec<poly_bb_p> , int); |
33ad93b9 | 1536 | __isl_give isl_union_map *extend_schedule (__isl_take isl_union_map *); |
aa52513e | 1537 | |
b60cc080 TG |
1538 | |
1539 | void | |
9771b263 | 1540 | compute_deps (scop_p scop, vec<poly_bb_p> pbbs, |
b60cc080 TG |
1541 | isl_union_map **must_raw, |
1542 | isl_union_map **may_raw, | |
1543 | isl_union_map **must_raw_no_source, | |
1544 | isl_union_map **may_raw_no_source, | |
1545 | isl_union_map **must_war, | |
1546 | isl_union_map **may_war, | |
1547 | isl_union_map **must_war_no_source, | |
1548 | isl_union_map **may_war_no_source, | |
1549 | isl_union_map **must_waw, | |
1550 | isl_union_map **may_waw, | |
1551 | isl_union_map **must_waw_no_source, | |
1552 | isl_union_map **may_waw_no_source); | |
1553 | ||
2abae5f1 | 1554 | #endif |