]>
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 SP |
26 | #include <isl/options.h> |
27 | #include <isl/ctx.h> | |
cc46a51d | 28 | #include <isl/val.h> |
616e2b4a SP |
29 | #include <isl/set.h> |
30 | #include <isl/union_set.h> | |
31 | #include <isl/map.h> | |
32 | #include <isl/union_map.h> | |
33 | #include <isl/aff.h> | |
34 | #include <isl/constraint.h> | |
35 | #include <isl/flow.h> | |
36 | #include <isl/ilp.h> | |
9625f2a2 | 37 | #include <isl/schedule.h> |
616e2b4a | 38 | #include <isl/ast_build.h> |
616e2b4a | 39 | #include <isl/schedule_node.h> |
71f10c42 RB |
40 | #include <isl/id.h> |
41 | #include <isl/space.h> | |
616e2b4a | 42 | |
2abae5f1 | 43 | typedef struct poly_dr *poly_dr_p; |
2abae5f1 SP |
44 | |
45 | typedef struct poly_bb *poly_bb_p; | |
2abae5f1 SP |
46 | |
47 | typedef struct scop *scop_p; | |
2abae5f1 | 48 | |
33ad93b9 | 49 | typedef unsigned graphite_dim_t; |
2abae5f1 | 50 | |
2abae5f1 SP |
51 | static inline graphite_dim_t scop_nb_params (scop_p); |
52 | ||
53 | /* A data reference can write or read some memory or we | |
54 | just know it may write some memory. */ | |
e6dec0fb | 55 | enum poly_dr_type |
2abae5f1 SP |
56 | { |
57 | PDR_READ, | |
d8eeb078 SP |
58 | /* PDR_MAY_READs are represented using PDR_READS. This does not |
59 | limit the expressiveness. */ | |
2abae5f1 SP |
60 | PDR_WRITE, |
61 | PDR_MAY_WRITE | |
62 | }; | |
63 | ||
64 | struct poly_dr | |
65 | { | |
afae0207 SP |
66 | /* An identifier for this PDR. */ |
67 | int id; | |
68 | ||
7bd2a8a7 SP |
69 | /* The number of data refs identical to this one in the PBB. */ |
70 | int nb_refs; | |
71 | ||
65b016eb AK |
72 | /* A pointer to the gimple stmt containing this reference. */ |
73 | gimple *stmt; | |
2abae5f1 SP |
74 | |
75 | /* A pointer to the PBB that contains this data reference. */ | |
76 | poly_bb_p pbb; | |
77 | ||
e6dec0fb | 78 | enum poly_dr_type type; |
2abae5f1 SP |
79 | |
80 | /* The access polyhedron contains the polyhedral space this data | |
81 | reference will access. | |
82 | ||
83 | The polyhedron contains these dimensions: | |
84 | ||
1825f9a2 LF |
85 | - The alias set (a): |
86 | Every memory access is classified in at least one alias set. | |
2abae5f1 | 87 | |
1825f9a2 LF |
88 | - The subscripts (s_0, ..., s_n): |
89 | The memory is accessed using zero or more subscript dimensions. | |
2abae5f1 | 90 | |
1825f9a2 | 91 | - The iteration domain (variables and parameters) |
2abae5f1 SP |
92 | |
93 | Do not hardcode the dimensions. Use the following accessor functions: | |
94 | - pdr_alias_set_dim | |
95 | - pdr_subscript_dim | |
96 | - pdr_iterator_dim | |
97 | - pdr_parameter_dim | |
98 | ||
99 | Example: | |
100 | ||
101 | | int A[1335][123]; | |
102 | | int *p = malloc (); | |
103 | | | |
104 | | k = ... | |
105 | | for i | |
106 | | { | |
107 | | if (unknown_function ()) | |
108 | | p = A; | |
109 | | ... = p[?][?]; | |
110 | | for j | |
25d7cc15 | 111 | | A[i][j+k] = m; |
2abae5f1 SP |
112 | | } |
113 | ||
114 | The data access A[i][j+k] in alias set "5" is described like this: | |
115 | ||
25d7cc15 | 116 | | i j k a s0 s1 1 |
2abae5f1 SP |
117 | | 0 0 0 1 0 0 -5 = 0 |
118 | |-1 0 0 0 1 0 0 = 0 | |
119 | | 0 -1 -1 0 0 1 0 = 0 | |
66096911 SP |
120 | | 0 0 0 0 1 0 0 >= 0 # The last four lines describe the |
121 | | 0 0 0 0 0 1 0 >= 0 # array size. | |
2abae5f1 SP |
122 | | 0 0 0 0 -1 0 1335 >= 0 |
123 | | 0 0 0 0 0 -1 123 >= 0 | |
124 | ||
125 | The pointer "*p" in alias set "5" and "7" is described as a union of | |
126 | polyhedron: | |
127 | ||
128 | ||
25d7cc15 | 129 | | i k a s0 1 |
2abae5f1 SP |
130 | | 0 0 1 0 -5 = 0 |
131 | | 0 0 0 1 0 >= 0 | |
132 | ||
133 | "or" | |
134 | ||
25d7cc15 | 135 | | i k a s0 1 |
2abae5f1 SP |
136 | | 0 0 1 0 -7 = 0 |
137 | | 0 0 0 1 0 >= 0 | |
138 | ||
139 | "*p" accesses all of the object allocated with 'malloc'. | |
140 | ||
141 | The scalar data access "m" is represented as an array with zero subscript | |
142 | dimensions. | |
143 | ||
144 | | i j k a 1 | |
ae403f5a RB |
145 | | 0 0 0 -1 15 = 0 |
146 | ||
147 | The difference between the graphite internal format for access data and | |
148 | the OpenSop format is in the order of columns. | |
149 | Instead of having: | |
150 | ||
151 | | i j k a s0 s1 1 | |
152 | | 0 0 0 1 0 0 -5 = 0 | |
153 | |-1 0 0 0 1 0 0 = 0 | |
154 | | 0 -1 -1 0 0 1 0 = 0 | |
155 | | 0 0 0 0 1 0 0 >= 0 # The last four lines describe the | |
156 | | 0 0 0 0 0 1 0 >= 0 # array size. | |
157 | | 0 0 0 0 -1 0 1335 >= 0 | |
158 | | 0 0 0 0 0 -1 123 >= 0 | |
159 | ||
160 | In OpenScop we have: | |
161 | ||
162 | | a s0 s1 i j k 1 | |
163 | | 1 0 0 0 0 0 -5 = 0 | |
164 | | 0 1 0 -1 0 0 0 = 0 | |
165 | | 0 0 1 0 -1 -1 0 = 0 | |
166 | | 0 1 0 0 0 0 0 >= 0 # The last four lines describe the | |
167 | | 0 0 1 0 0 0 0 >= 0 # array size. | |
168 | | 0 -1 0 0 0 0 1335 >= 0 | |
169 | | 0 0 -1 0 0 0 123 >= 0 | |
170 | ||
171 | The OpenScop access function is printed as follows: | |
172 | ||
173 | | 1 # The number of disjunct components in a union of access functions. | |
174 | | R C O I L P # Described bellow. | |
175 | | a s0 s1 i j k 1 | |
176 | | 1 0 0 0 0 0 -5 = 0 | |
177 | | 0 1 0 -1 0 0 0 = 0 | |
178 | | 0 0 1 0 -1 -1 0 = 0 | |
179 | | 0 1 0 0 0 0 0 >= 0 # The last four lines describe the | |
180 | | 0 0 1 0 0 0 0 >= 0 # array size. | |
181 | | 0 -1 0 0 0 0 1335 >= 0 | |
182 | | 0 0 -1 0 0 0 123 >= 0 | |
183 | ||
184 | Where: | |
185 | - R: Number of rows. | |
186 | - C: Number of columns. | |
187 | - O: Number of output dimensions = alias set + number of subscripts. | |
188 | - I: Number of input dimensions (iterators). | |
189 | - L: Number of local (existentially quantified) dimensions. | |
190 | - P: Number of parameters. | |
191 | ||
192 | In the example, the vector "R C O I L P" is "7 7 3 2 0 1". */ | |
33ad93b9 | 193 | isl_map *accesses; |
24757752 | 194 | isl_set *subscript_sizes; |
2abae5f1 SP |
195 | }; |
196 | ||
afae0207 | 197 | #define PDR_ID(PDR) (PDR->id) |
7bd2a8a7 | 198 | #define PDR_NB_REFS(PDR) (PDR->nb_refs) |
2abae5f1 SP |
199 | #define PDR_PBB(PDR) (PDR->pbb) |
200 | #define PDR_TYPE(PDR) (PDR->type) | |
33ad93b9 | 201 | #define PDR_ACCESSES(PDR) (NULL) |
2abae5f1 | 202 | |
65b016eb AK |
203 | void new_poly_dr (poly_bb_p, gimple *, enum poly_dr_type, |
204 | isl_map *, isl_set *); | |
5c24066b AK |
205 | void debug_pdr (poly_dr_p); |
206 | void print_pdr (FILE *, poly_dr_p); | |
d8eeb078 SP |
207 | |
208 | static inline bool | |
209 | pdr_read_p (poly_dr_p pdr) | |
210 | { | |
211 | return PDR_TYPE (pdr) == PDR_READ; | |
212 | } | |
213 | ||
214 | /* Returns true when PDR is a "write". */ | |
215 | ||
216 | static inline bool | |
217 | pdr_write_p (poly_dr_p pdr) | |
218 | { | |
219 | return PDR_TYPE (pdr) == PDR_WRITE; | |
220 | } | |
221 | ||
222 | /* Returns true when PDR is a "may write". */ | |
223 | ||
224 | static inline bool | |
225 | pdr_may_write_p (poly_dr_p pdr) | |
226 | { | |
227 | return PDR_TYPE (pdr) == PDR_MAY_WRITE; | |
228 | } | |
229 | ||
2abae5f1 SP |
230 | /* POLY_BB represents a blackbox in the polyhedral model. */ |
231 | ||
232 | struct poly_bb | |
233 | { | |
a1954f72 | 234 | /* Pointer to a basic block or a statement in the compiler. */ |
8e4dc590 | 235 | gimple_poly_bb_p black_box; |
2abae5f1 | 236 | |
a1954f72 | 237 | /* Pointer to the SCOP containing this PBB. */ |
2abae5f1 SP |
238 | scop_p scop; |
239 | ||
aa52513e SP |
240 | /* The iteration domain of this bb. The layout of this polyhedron |
241 | is I|G with I the iteration domain, G the context parameters. | |
242 | ||
2abae5f1 SP |
243 | Example: |
244 | ||
245 | for (i = a - 7*b + 8; i <= 3*a + 13*b + 20; i++) | |
246 | for (j = 2; j <= 2*i + 5; j++) | |
247 | for (k = 0; k <= 5; k++) | |
248 | S (i,j,k) | |
249 | ||
250 | Loop iterators: i, j, k | |
251 | Parameters: a, b | |
252 | ||
253 | | i >= a - 7b + 8 | |
254 | | i <= 3a + 13b + 20 | |
255 | | j >= 2 | |
256 | | j <= 2i + 5 | |
257 | | k >= 0 | |
258 | | k <= 5 | |
259 | ||
260 | The number of variables in the DOMAIN may change and is not | |
261 | related to the number of loops in the original code. */ | |
33ad93b9 | 262 | isl_set *domain; |
adba512d | 263 | isl_set *iterators; |
adba512d AK |
264 | |
265 | /* The data references we access. */ | |
266 | vec<poly_dr_p> drs; | |
a0dd1440 | 267 | |
65b016eb AK |
268 | /* The last basic block generated for this pbb. */ |
269 | basic_block new_bb; | |
2abae5f1 SP |
270 | }; |
271 | ||
65ef70d6 | 272 | #define PBB_BLACK_BOX(PBB) ((gimple_poly_bb_p) PBB->black_box) |
2abae5f1 | 273 | #define PBB_SCOP(PBB) (PBB->scop) |
2abae5f1 | 274 | #define PBB_DRS(PBB) (PBB->drs) |
2abae5f1 | 275 | |
8e4dc590 | 276 | extern poly_bb_p new_poly_bb (scop_p, gimple_poly_bb_p); |
5c24066b AK |
277 | extern void print_pbb_domain (FILE *, poly_bb_p); |
278 | extern void print_pbb (FILE *, poly_bb_p); | |
279 | extern void print_scop_context (FILE *, scop_p); | |
280 | extern void print_scop (FILE *, scop_p); | |
281 | extern void debug_pbb_domain (poly_bb_p); | |
282 | extern void debug_pbb (poly_bb_p); | |
283 | extern void print_pdrs (FILE *, poly_bb_p); | |
284 | extern void debug_pdrs (poly_bb_p); | |
285 | extern void debug_scop_context (scop_p); | |
286 | extern void debug_scop (scop_p); | |
287 | extern void print_scop_params (FILE *, scop_p); | |
288 | extern void debug_scop_params (scop_p); | |
289 | extern void print_iteration_domain (FILE *, poly_bb_p); | |
290 | extern void print_iteration_domains (FILE *, scop_p); | |
291 | extern void debug_iteration_domain (poly_bb_p); | |
292 | extern void debug_iteration_domains (scop_p); | |
33ad93b9 RG |
293 | extern void print_isl_set (FILE *, isl_set *); |
294 | extern void print_isl_map (FILE *, isl_map *); | |
ea17c0fe | 295 | extern void print_isl_union_map (FILE *, isl_union_map *); |
33ad93b9 RG |
296 | extern void print_isl_aff (FILE *, isl_aff *); |
297 | extern void print_isl_constraint (FILE *, isl_constraint *); | |
adba512d AK |
298 | extern void print_isl_schedule (FILE *, isl_schedule *); |
299 | extern void debug_isl_schedule (isl_schedule *); | |
300 | extern void print_isl_ast (FILE *, isl_ast_node *); | |
301 | extern void debug_isl_ast (isl_ast_node *); | |
33ad93b9 RG |
302 | extern void debug_isl_set (isl_set *); |
303 | extern void debug_isl_map (isl_map *); | |
ea17c0fe | 304 | extern void debug_isl_union_map (isl_union_map *); |
33ad93b9 RG |
305 | extern void debug_isl_aff (isl_aff *); |
306 | extern void debug_isl_constraint (isl_constraint *); | |
33ad93b9 | 307 | extern void debug_gmp_value (mpz_t); |
adba512d AK |
308 | extern void debug_scop_pbb (scop_p scop, int i); |
309 | extern void print_schedule_ast (FILE *, __isl_keep isl_schedule *, scop_p); | |
310 | extern void debug_schedule_ast (__isl_keep isl_schedule *, scop_p); | |
2abae5f1 | 311 | |
03922af3 | 312 | /* The basic block of the PBB. */ |
072edf07 | 313 | |
03922af3 SP |
314 | static inline basic_block |
315 | pbb_bb (poly_bb_p pbb) | |
316 | { | |
317 | return GBB_BB (PBB_BLACK_BOX (pbb)); | |
318 | } | |
319 | ||
afae0207 SP |
320 | static inline int |
321 | pbb_index (poly_bb_p pbb) | |
322 | { | |
03922af3 | 323 | return pbb_bb (pbb)->index; |
afae0207 SP |
324 | } |
325 | ||
d48e288d SP |
326 | /* The loop of the PBB. */ |
327 | ||
328 | static inline loop_p | |
329 | pbb_loop (poly_bb_p pbb) | |
330 | { | |
331 | return gbb_loop (PBB_BLACK_BOX (pbb)); | |
332 | } | |
333 | ||
2abae5f1 SP |
334 | /* The scop that contains the PDR. */ |
335 | ||
afae0207 SP |
336 | static inline scop_p |
337 | pdr_scop (poly_dr_p pdr) | |
2abae5f1 SP |
338 | { |
339 | return PBB_SCOP (PDR_PBB (pdr)); | |
340 | } | |
341 | ||
342 | /* Set black box of PBB to BLACKBOX. */ | |
343 | ||
344 | static inline void | |
8e4dc590 | 345 | pbb_set_black_box (poly_bb_p pbb, gimple_poly_bb_p black_box) |
2abae5f1 SP |
346 | { |
347 | pbb->black_box = black_box; | |
348 | } | |
349 | ||
09fefdad AK |
350 | /* A helper structure to keep track of data references, polyhedral BBs, and |
351 | alias sets. */ | |
352 | ||
353 | struct dr_info | |
354 | { | |
caf5b4df AK |
355 | enum { |
356 | invalid_alias_set = -1 | |
357 | }; | |
09fefdad AK |
358 | /* The data reference. */ |
359 | data_reference_p dr; | |
360 | ||
09fefdad AK |
361 | /* The polyhedral BB containing this DR. */ |
362 | poly_bb_p pbb; | |
363 | ||
caf5b4df AK |
364 | /* ALIAS_SET is the SCC number assigned by a graph_dfs of the alias graph. |
365 | -1 is an invalid alias set. */ | |
366 | int alias_set; | |
367 | ||
09fefdad | 368 | /* Construct a DR_INFO from a data reference DR, an ALIAS_SET, and a PBB. */ |
caf5b4df AK |
369 | dr_info (data_reference_p dr, poly_bb_p pbb, |
370 | int alias_set = invalid_alias_set) | |
371 | : dr (dr), pbb (pbb), alias_set (alias_set) {} | |
09fefdad AK |
372 | }; |
373 | ||
2abae5f1 SP |
374 | /* A SCOP is a Static Control Part of the program, simple enough to be |
375 | represented in polyhedral form. */ | |
376 | struct scop | |
377 | { | |
378 | /* A SCOP is defined as a SESE region. */ | |
d37fc3aa | 379 | sese_info_p scop_info; |
2abae5f1 SP |
380 | |
381 | /* Number of parameters in SCoP. */ | |
382 | graphite_dim_t nb_params; | |
383 | ||
99124c31 RB |
384 | /* The maximum alias set as assigned to drs by build_alias_sets. */ |
385 | unsigned max_alias_set; | |
386 | ||
2abae5f1 SP |
387 | /* All the basic blocks in this scop that contain memory references |
388 | and that will be represented as statements in the polyhedral | |
389 | representation. */ | |
b0b5710c | 390 | vec<poly_bb_p> pbbs; |
2abae5f1 | 391 | |
09fefdad AK |
392 | /* All the data references in this scop. */ |
393 | vec<dr_info> drs; | |
394 | ||
2abae5f1 SP |
395 | /* The context describes known restrictions concerning the parameters |
396 | and relations in between the parameters. | |
397 | ||
398 | void f (int8_t a, uint_16_t b) { | |
399 | c = 2 a + b; | |
400 | ... | |
401 | } | |
402 | ||
403 | Here we can add these restrictions to the context: | |
404 | ||
405 | -128 >= a >= 127 | |
406 | 0 >= b >= 65,535 | |
407 | c = 2a + b */ | |
8e4dc590 | 408 | isl_set *param_context; |
33ad93b9 | 409 | |
e357a5e0 | 410 | /* The context used internally by isl. */ |
8e4dc590 | 411 | isl_ctx *isl_context; |
33ad93b9 | 412 | |
adba512d AK |
413 | /* SCoP original schedule. */ |
414 | isl_schedule *original_schedule; | |
415 | ||
416 | /* SCoP transformed schedule. */ | |
417 | isl_schedule *transformed_schedule; | |
9625f2a2 | 418 | |
0f7a02a3 AK |
419 | /* The data dependence relation among the data references in this scop. */ |
420 | isl_union_map *dependence; | |
2abae5f1 SP |
421 | }; |
422 | ||
87ccab5d | 423 | extern scop_p new_scop (edge, edge); |
2abae5f1 | 424 | extern void free_scop (scop_p); |
65b016eb AK |
425 | extern gimple_poly_bb_p new_gimple_poly_bb (basic_block, vec<data_reference_p>, |
426 | vec<scalar_use>, vec<tree>); | |
2abae5f1 | 427 | extern bool apply_poly_transforms (scop_p); |
2abae5f1 SP |
428 | |
429 | /* Set the region of SCOP to REGION. */ | |
430 | ||
431 | static inline void | |
bafcb153 | 432 | scop_set_region (scop_p scop, sese_info_p region) |
2abae5f1 | 433 | { |
d37fc3aa | 434 | scop->scop_info = region; |
2abae5f1 SP |
435 | } |
436 | ||
437 | /* Returns the number of parameters for SCOP. */ | |
438 | ||
439 | static inline graphite_dim_t | |
440 | scop_nb_params (scop_p scop) | |
441 | { | |
442 | return scop->nb_params; | |
443 | } | |
444 | ||
445 | /* Set the number of params of SCOP to NB_PARAMS. */ | |
446 | ||
447 | static inline void | |
448 | scop_set_nb_params (scop_p scop, graphite_dim_t nb_params) | |
449 | { | |
450 | scop->nb_params = nb_params; | |
451 | } | |
452 | ||
adba512d | 453 | extern void scop_get_dependences (scop_p scop); |
574921c2 RG |
454 | |
455 | bool | |
456 | carries_deps (__isl_keep isl_union_map *schedule, | |
457 | __isl_keep isl_union_map *deps, | |
458 | int depth); | |
459 | ||
cf98f0f4 AK |
460 | extern bool build_poly_scop (scop_p); |
461 | extern bool graphite_regenerate_ast_isl (scop_p); | |
cf98f0f4 | 462 | extern void build_scops (vec<scop_p> *); |
124f4f57 | 463 | extern tree cached_scalar_evolution_in_region (const sese_l &, loop_p, tree); |
15256e28 AK |
464 | extern void dot_all_sese (FILE *, vec<sese_l> &); |
465 | extern void dot_sese (sese_l &); | |
466 | extern void dot_cfg (); | |
adba512d | 467 | |
2abae5f1 | 468 | #endif |