]>
Commit | Line | Data |
---|---|---|
2abae5f1 | 1 | /* Graphite polyhedral representation. |
8d9254fc | 2 | Copyright (C) 2009-2020 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 | ||
9c358739 | 25 | #include "sese.h" |
616e2b4a | 26 | |
2abae5f1 | 27 | typedef struct poly_dr *poly_dr_p; |
2abae5f1 SP |
28 | |
29 | typedef struct poly_bb *poly_bb_p; | |
2abae5f1 SP |
30 | |
31 | typedef struct scop *scop_p; | |
2abae5f1 | 32 | |
33ad93b9 | 33 | typedef unsigned graphite_dim_t; |
2abae5f1 | 34 | |
2abae5f1 SP |
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 | ||
65b016eb AK |
56 | /* A pointer to the gimple stmt containing this reference. */ |
57 | gimple *stmt; | |
2abae5f1 SP |
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 | 177 | isl_map *accesses; |
24757752 | 178 | isl_set *subscript_sizes; |
2abae5f1 SP |
179 | }; |
180 | ||
afae0207 | 181 | #define PDR_ID(PDR) (PDR->id) |
7bd2a8a7 | 182 | #define PDR_NB_REFS(PDR) (PDR->nb_refs) |
2abae5f1 SP |
183 | #define PDR_PBB(PDR) (PDR->pbb) |
184 | #define PDR_TYPE(PDR) (PDR->type) | |
33ad93b9 | 185 | #define PDR_ACCESSES(PDR) (NULL) |
2abae5f1 | 186 | |
65b016eb AK |
187 | void new_poly_dr (poly_bb_p, gimple *, enum poly_dr_type, |
188 | isl_map *, isl_set *); | |
5c24066b AK |
189 | void debug_pdr (poly_dr_p); |
190 | void print_pdr (FILE *, poly_dr_p); | |
d8eeb078 SP |
191 | |
192 | static inline bool | |
193 | pdr_read_p (poly_dr_p pdr) | |
194 | { | |
195 | return PDR_TYPE (pdr) == PDR_READ; | |
196 | } | |
197 | ||
198 | /* Returns true when PDR is a "write". */ | |
199 | ||
200 | static inline bool | |
201 | pdr_write_p (poly_dr_p pdr) | |
202 | { | |
203 | return PDR_TYPE (pdr) == PDR_WRITE; | |
204 | } | |
205 | ||
206 | /* Returns true when PDR is a "may write". */ | |
207 | ||
208 | static inline bool | |
209 | pdr_may_write_p (poly_dr_p pdr) | |
210 | { | |
211 | return PDR_TYPE (pdr) == PDR_MAY_WRITE; | |
212 | } | |
213 | ||
2abae5f1 SP |
214 | /* POLY_BB represents a blackbox in the polyhedral model. */ |
215 | ||
216 | struct poly_bb | |
217 | { | |
a1954f72 | 218 | /* Pointer to a basic block or a statement in the compiler. */ |
8e4dc590 | 219 | gimple_poly_bb_p black_box; |
2abae5f1 | 220 | |
a1954f72 | 221 | /* Pointer to the SCOP containing this PBB. */ |
2abae5f1 SP |
222 | scop_p scop; |
223 | ||
aa52513e SP |
224 | /* The iteration domain of this bb. The layout of this polyhedron |
225 | is I|G with I the iteration domain, G the context parameters. | |
226 | ||
2abae5f1 SP |
227 | Example: |
228 | ||
229 | for (i = a - 7*b + 8; i <= 3*a + 13*b + 20; i++) | |
230 | for (j = 2; j <= 2*i + 5; j++) | |
231 | for (k = 0; k <= 5; k++) | |
232 | S (i,j,k) | |
233 | ||
234 | Loop iterators: i, j, k | |
235 | Parameters: a, b | |
236 | ||
237 | | i >= a - 7b + 8 | |
238 | | i <= 3a + 13b + 20 | |
239 | | j >= 2 | |
240 | | j <= 2i + 5 | |
241 | | k >= 0 | |
242 | | k <= 5 | |
243 | ||
244 | The number of variables in the DOMAIN may change and is not | |
245 | related to the number of loops in the original code. */ | |
33ad93b9 | 246 | isl_set *domain; |
adba512d | 247 | isl_set *iterators; |
adba512d AK |
248 | |
249 | /* The data references we access. */ | |
250 | vec<poly_dr_p> drs; | |
a0dd1440 | 251 | |
65b016eb AK |
252 | /* The last basic block generated for this pbb. */ |
253 | basic_block new_bb; | |
2abae5f1 SP |
254 | }; |
255 | ||
65ef70d6 | 256 | #define PBB_BLACK_BOX(PBB) ((gimple_poly_bb_p) PBB->black_box) |
2abae5f1 | 257 | #define PBB_SCOP(PBB) (PBB->scop) |
2abae5f1 | 258 | #define PBB_DRS(PBB) (PBB->drs) |
2abae5f1 | 259 | |
8e4dc590 | 260 | extern poly_bb_p new_poly_bb (scop_p, gimple_poly_bb_p); |
5c24066b AK |
261 | extern void print_pbb_domain (FILE *, poly_bb_p); |
262 | extern void print_pbb (FILE *, poly_bb_p); | |
263 | extern void print_scop_context (FILE *, scop_p); | |
264 | extern void print_scop (FILE *, scop_p); | |
265 | extern void debug_pbb_domain (poly_bb_p); | |
266 | extern void debug_pbb (poly_bb_p); | |
267 | extern void print_pdrs (FILE *, poly_bb_p); | |
268 | extern void debug_pdrs (poly_bb_p); | |
269 | extern void debug_scop_context (scop_p); | |
270 | extern void debug_scop (scop_p); | |
271 | extern void print_scop_params (FILE *, scop_p); | |
272 | extern void debug_scop_params (scop_p); | |
273 | extern void print_iteration_domain (FILE *, poly_bb_p); | |
274 | extern void print_iteration_domains (FILE *, scop_p); | |
275 | extern void debug_iteration_domain (poly_bb_p); | |
276 | extern void debug_iteration_domains (scop_p); | |
33ad93b9 RG |
277 | extern void print_isl_set (FILE *, isl_set *); |
278 | extern void print_isl_map (FILE *, isl_map *); | |
ea17c0fe | 279 | extern void print_isl_union_map (FILE *, isl_union_map *); |
33ad93b9 RG |
280 | extern void print_isl_aff (FILE *, isl_aff *); |
281 | extern void print_isl_constraint (FILE *, isl_constraint *); | |
adba512d AK |
282 | extern void print_isl_schedule (FILE *, isl_schedule *); |
283 | extern void debug_isl_schedule (isl_schedule *); | |
284 | extern void print_isl_ast (FILE *, isl_ast_node *); | |
285 | extern void debug_isl_ast (isl_ast_node *); | |
33ad93b9 RG |
286 | extern void debug_isl_set (isl_set *); |
287 | extern void debug_isl_map (isl_map *); | |
ea17c0fe | 288 | extern void debug_isl_union_map (isl_union_map *); |
33ad93b9 RG |
289 | extern void debug_isl_aff (isl_aff *); |
290 | extern void debug_isl_constraint (isl_constraint *); | |
33ad93b9 | 291 | extern void debug_gmp_value (mpz_t); |
adba512d AK |
292 | extern void debug_scop_pbb (scop_p scop, int i); |
293 | extern void print_schedule_ast (FILE *, __isl_keep isl_schedule *, scop_p); | |
294 | extern void debug_schedule_ast (__isl_keep isl_schedule *, scop_p); | |
2abae5f1 | 295 | |
03922af3 | 296 | /* The basic block of the PBB. */ |
072edf07 | 297 | |
03922af3 SP |
298 | static inline basic_block |
299 | pbb_bb (poly_bb_p pbb) | |
300 | { | |
301 | return GBB_BB (PBB_BLACK_BOX (pbb)); | |
302 | } | |
303 | ||
afae0207 SP |
304 | static inline int |
305 | pbb_index (poly_bb_p pbb) | |
306 | { | |
03922af3 | 307 | return pbb_bb (pbb)->index; |
afae0207 SP |
308 | } |
309 | ||
d48e288d SP |
310 | /* The loop of the PBB. */ |
311 | ||
312 | static inline loop_p | |
313 | pbb_loop (poly_bb_p pbb) | |
314 | { | |
315 | return gbb_loop (PBB_BLACK_BOX (pbb)); | |
316 | } | |
317 | ||
2abae5f1 SP |
318 | /* The scop that contains the PDR. */ |
319 | ||
afae0207 SP |
320 | static inline scop_p |
321 | pdr_scop (poly_dr_p pdr) | |
2abae5f1 SP |
322 | { |
323 | return PBB_SCOP (PDR_PBB (pdr)); | |
324 | } | |
325 | ||
326 | /* Set black box of PBB to BLACKBOX. */ | |
327 | ||
328 | static inline void | |
8e4dc590 | 329 | pbb_set_black_box (poly_bb_p pbb, gimple_poly_bb_p black_box) |
2abae5f1 SP |
330 | { |
331 | pbb->black_box = black_box; | |
332 | } | |
333 | ||
09fefdad AK |
334 | /* A helper structure to keep track of data references, polyhedral BBs, and |
335 | alias sets. */ | |
336 | ||
337 | struct dr_info | |
338 | { | |
caf5b4df AK |
339 | enum { |
340 | invalid_alias_set = -1 | |
341 | }; | |
09fefdad AK |
342 | /* The data reference. */ |
343 | data_reference_p dr; | |
344 | ||
09fefdad AK |
345 | /* The polyhedral BB containing this DR. */ |
346 | poly_bb_p pbb; | |
347 | ||
caf5b4df AK |
348 | /* ALIAS_SET is the SCC number assigned by a graph_dfs of the alias graph. |
349 | -1 is an invalid alias set. */ | |
350 | int alias_set; | |
351 | ||
09fefdad | 352 | /* Construct a DR_INFO from a data reference DR, an ALIAS_SET, and a PBB. */ |
caf5b4df AK |
353 | dr_info (data_reference_p dr, poly_bb_p pbb, |
354 | int alias_set = invalid_alias_set) | |
355 | : dr (dr), pbb (pbb), alias_set (alias_set) {} | |
09fefdad AK |
356 | }; |
357 | ||
2abae5f1 SP |
358 | /* A SCOP is a Static Control Part of the program, simple enough to be |
359 | represented in polyhedral form. */ | |
360 | struct scop | |
361 | { | |
362 | /* A SCOP is defined as a SESE region. */ | |
d37fc3aa | 363 | sese_info_p scop_info; |
2abae5f1 SP |
364 | |
365 | /* Number of parameters in SCoP. */ | |
366 | graphite_dim_t nb_params; | |
367 | ||
99124c31 RB |
368 | /* The maximum alias set as assigned to drs by build_alias_sets. */ |
369 | unsigned max_alias_set; | |
370 | ||
2abae5f1 SP |
371 | /* All the basic blocks in this scop that contain memory references |
372 | and that will be represented as statements in the polyhedral | |
373 | representation. */ | |
b0b5710c | 374 | vec<poly_bb_p> pbbs; |
2abae5f1 | 375 | |
09fefdad AK |
376 | /* All the data references in this scop. */ |
377 | vec<dr_info> drs; | |
378 | ||
2abae5f1 SP |
379 | /* The context describes known restrictions concerning the parameters |
380 | and relations in between the parameters. | |
381 | ||
382 | void f (int8_t a, uint_16_t b) { | |
383 | c = 2 a + b; | |
384 | ... | |
385 | } | |
386 | ||
387 | Here we can add these restrictions to the context: | |
388 | ||
389 | -128 >= a >= 127 | |
390 | 0 >= b >= 65,535 | |
391 | c = 2a + b */ | |
8e4dc590 | 392 | isl_set *param_context; |
33ad93b9 | 393 | |
e357a5e0 | 394 | /* The context used internally by isl. */ |
8e4dc590 | 395 | isl_ctx *isl_context; |
33ad93b9 | 396 | |
adba512d AK |
397 | /* SCoP original schedule. */ |
398 | isl_schedule *original_schedule; | |
399 | ||
400 | /* SCoP transformed schedule. */ | |
401 | isl_schedule *transformed_schedule; | |
9625f2a2 | 402 | |
0f7a02a3 AK |
403 | /* The data dependence relation among the data references in this scop. */ |
404 | isl_union_map *dependence; | |
2abae5f1 SP |
405 | }; |
406 | ||
87ccab5d | 407 | extern scop_p new_scop (edge, edge); |
2abae5f1 | 408 | extern void free_scop (scop_p); |
65b016eb AK |
409 | extern gimple_poly_bb_p new_gimple_poly_bb (basic_block, vec<data_reference_p>, |
410 | vec<scalar_use>, vec<tree>); | |
2abae5f1 | 411 | extern bool apply_poly_transforms (scop_p); |
2abae5f1 SP |
412 | |
413 | /* Set the region of SCOP to REGION. */ | |
414 | ||
415 | static inline void | |
bafcb153 | 416 | scop_set_region (scop_p scop, sese_info_p region) |
2abae5f1 | 417 | { |
d37fc3aa | 418 | scop->scop_info = region; |
2abae5f1 SP |
419 | } |
420 | ||
421 | /* Returns the number of parameters for SCOP. */ | |
422 | ||
423 | static inline graphite_dim_t | |
424 | scop_nb_params (scop_p scop) | |
425 | { | |
426 | return scop->nb_params; | |
427 | } | |
428 | ||
429 | /* Set the number of params of SCOP to NB_PARAMS. */ | |
430 | ||
431 | static inline void | |
432 | scop_set_nb_params (scop_p scop, graphite_dim_t nb_params) | |
433 | { | |
434 | scop->nb_params = nb_params; | |
435 | } | |
436 | ||
adba512d | 437 | extern void scop_get_dependences (scop_p scop); |
574921c2 RG |
438 | |
439 | bool | |
440 | carries_deps (__isl_keep isl_union_map *schedule, | |
441 | __isl_keep isl_union_map *deps, | |
442 | int depth); | |
443 | ||
cf98f0f4 AK |
444 | extern bool build_poly_scop (scop_p); |
445 | extern bool graphite_regenerate_ast_isl (scop_p); | |
cf98f0f4 | 446 | extern void build_scops (vec<scop_p> *); |
124f4f57 | 447 | extern tree cached_scalar_evolution_in_region (const sese_l &, loop_p, tree); |
15256e28 AK |
448 | extern void dot_all_sese (FILE *, vec<sese_l> &); |
449 | extern void dot_sese (sese_l &); | |
450 | extern void dot_cfg (); | |
adba512d | 451 | |
2abae5f1 | 452 | #endif |