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