|
111
|
1 /* Graphite polyhedral representation.
|
|
145
|
2 Copyright (C) 2009-2020 Free Software Foundation, Inc.
|
|
111
|
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 #include "sese.h"
|
|
|
26 #include <isl/options.h>
|
|
|
27 #include <isl/ctx.h>
|
|
|
28 #include <isl/val.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>
|
|
|
37 #include <isl/schedule.h>
|
|
|
38 #include <isl/ast_build.h>
|
|
|
39 #include <isl/schedule_node.h>
|
|
131
|
40 #include <isl/id.h>
|
|
|
41 #include <isl/space.h>
|
|
111
|
42
|
|
|
43 typedef struct poly_dr *poly_dr_p;
|
|
|
44
|
|
|
45 typedef struct poly_bb *poly_bb_p;
|
|
|
46
|
|
|
47 typedef struct scop *scop_p;
|
|
|
48
|
|
|
49 typedef unsigned graphite_dim_t;
|
|
|
50
|
|
|
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. */
|
|
|
55 enum poly_dr_type
|
|
|
56 {
|
|
|
57 PDR_READ,
|
|
|
58 /* PDR_MAY_READs are represented using PDR_READS. This does not
|
|
|
59 limit the expressiveness. */
|
|
|
60 PDR_WRITE,
|
|
|
61 PDR_MAY_WRITE
|
|
|
62 };
|
|
|
63
|
|
|
64 struct poly_dr
|
|
|
65 {
|
|
|
66 /* An identifier for this PDR. */
|
|
|
67 int id;
|
|
|
68
|
|
|
69 /* The number of data refs identical to this one in the PBB. */
|
|
|
70 int nb_refs;
|
|
|
71
|
|
|
72 /* A pointer to the gimple stmt containing this reference. */
|
|
|
73 gimple *stmt;
|
|
|
74
|
|
|
75 /* A pointer to the PBB that contains this data reference. */
|
|
|
76 poly_bb_p pbb;
|
|
|
77
|
|
|
78 enum poly_dr_type type;
|
|
|
79
|
|
|
80 /* The access polyhedron contains the polyhedral space this data
|
|
|
81 reference will access.
|
|
|
82
|
|
|
83 The polyhedron contains these dimensions:
|
|
|
84
|
|
|
85 - The alias set (a):
|
|
|
86 Every memory access is classified in at least one alias set.
|
|
|
87
|
|
|
88 - The subscripts (s_0, ..., s_n):
|
|
|
89 The memory is accessed using zero or more subscript dimensions.
|
|
|
90
|
|
|
91 - The iteration domain (variables and parameters)
|
|
|
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
|
|
|
111 | A[i][j+k] = m;
|
|
|
112 | }
|
|
|
113
|
|
|
114 The data access A[i][j+k] in alias set "5" is described like this:
|
|
|
115
|
|
|
116 | i j k a s0 s1 1
|
|
|
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
|
|
|
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.
|
|
|
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
|
|
|
129 | i k a s0 1
|
|
|
130 | 0 0 1 0 -5 = 0
|
|
|
131 | 0 0 0 1 0 >= 0
|
|
|
132
|
|
|
133 "or"
|
|
|
134
|
|
|
135 | i k a s0 1
|
|
|
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
|
|
|
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". */
|
|
|
193 isl_map *accesses;
|
|
|
194 isl_set *subscript_sizes;
|
|
|
195 };
|
|
|
196
|
|
|
197 #define PDR_ID(PDR) (PDR->id)
|
|
|
198 #define PDR_NB_REFS(PDR) (PDR->nb_refs)
|
|
|
199 #define PDR_PBB(PDR) (PDR->pbb)
|
|
|
200 #define PDR_TYPE(PDR) (PDR->type)
|
|
|
201 #define PDR_ACCESSES(PDR) (NULL)
|
|
|
202
|
|
|
203 void new_poly_dr (poly_bb_p, gimple *, enum poly_dr_type,
|
|
|
204 isl_map *, isl_set *);
|
|
|
205 void debug_pdr (poly_dr_p);
|
|
|
206 void print_pdr (FILE *, poly_dr_p);
|
|
|
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
|
|
|
230 /* POLY_BB represents a blackbox in the polyhedral model. */
|
|
|
231
|
|
|
232 struct poly_bb
|
|
|
233 {
|
|
|
234 /* Pointer to a basic block or a statement in the compiler. */
|
|
|
235 gimple_poly_bb_p black_box;
|
|
|
236
|
|
|
237 /* Pointer to the SCOP containing this PBB. */
|
|
|
238 scop_p scop;
|
|
|
239
|
|
|
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
|
|
|
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. */
|
|
|
262 isl_set *domain;
|
|
|
263 isl_set *iterators;
|
|
|
264
|
|
|
265 /* The data references we access. */
|
|
|
266 vec<poly_dr_p> drs;
|
|
|
267
|
|
|
268 /* The last basic block generated for this pbb. */
|
|
|
269 basic_block new_bb;
|
|
|
270 };
|
|
|
271
|
|
|
272 #define PBB_BLACK_BOX(PBB) ((gimple_poly_bb_p) PBB->black_box)
|
|
|
273 #define PBB_SCOP(PBB) (PBB->scop)
|
|
|
274 #define PBB_DRS(PBB) (PBB->drs)
|
|
|
275
|
|
|
276 extern poly_bb_p new_poly_bb (scop_p, gimple_poly_bb_p);
|
|
|
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);
|
|
|
293 extern void print_isl_set (FILE *, isl_set *);
|
|
|
294 extern void print_isl_map (FILE *, isl_map *);
|
|
|
295 extern void print_isl_union_map (FILE *, isl_union_map *);
|
|
|
296 extern void print_isl_aff (FILE *, isl_aff *);
|
|
|
297 extern void print_isl_constraint (FILE *, isl_constraint *);
|
|
|
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 *);
|
|
|
302 extern void debug_isl_set (isl_set *);
|
|
|
303 extern void debug_isl_map (isl_map *);
|
|
|
304 extern void debug_isl_union_map (isl_union_map *);
|
|
|
305 extern void debug_isl_aff (isl_aff *);
|
|
|
306 extern void debug_isl_constraint (isl_constraint *);
|
|
|
307 extern void debug_gmp_value (mpz_t);
|
|
|
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);
|
|
|
311
|
|
|
312 /* The basic block of the PBB. */
|
|
|
313
|
|
|
314 static inline basic_block
|
|
|
315 pbb_bb (poly_bb_p pbb)
|
|
|
316 {
|
|
|
317 return GBB_BB (PBB_BLACK_BOX (pbb));
|
|
|
318 }
|
|
|
319
|
|
|
320 static inline int
|
|
|
321 pbb_index (poly_bb_p pbb)
|
|
|
322 {
|
|
|
323 return pbb_bb (pbb)->index;
|
|
|
324 }
|
|
|
325
|
|
|
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
|
|
|
334 /* The scop that contains the PDR. */
|
|
|
335
|
|
|
336 static inline scop_p
|
|
|
337 pdr_scop (poly_dr_p pdr)
|
|
|
338 {
|
|
|
339 return PBB_SCOP (PDR_PBB (pdr));
|
|
|
340 }
|
|
|
341
|
|
|
342 /* Set black box of PBB to BLACKBOX. */
|
|
|
343
|
|
|
344 static inline void
|
|
|
345 pbb_set_black_box (poly_bb_p pbb, gimple_poly_bb_p black_box)
|
|
|
346 {
|
|
|
347 pbb->black_box = black_box;
|
|
|
348 }
|
|
|
349
|
|
|
350 /* A helper structure to keep track of data references, polyhedral BBs, and
|
|
|
351 alias sets. */
|
|
|
352
|
|
|
353 struct dr_info
|
|
|
354 {
|
|
|
355 enum {
|
|
|
356 invalid_alias_set = -1
|
|
|
357 };
|
|
|
358 /* The data reference. */
|
|
|
359 data_reference_p dr;
|
|
|
360
|
|
|
361 /* The polyhedral BB containing this DR. */
|
|
|
362 poly_bb_p pbb;
|
|
|
363
|
|
|
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
|
|
|
368 /* Construct a DR_INFO from a data reference DR, an ALIAS_SET, and a PBB. */
|
|
|
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) {}
|
|
|
372 };
|
|
|
373
|
|
|
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. */
|
|
|
379 sese_info_p scop_info;
|
|
|
380
|
|
|
381 /* Number of parameters in SCoP. */
|
|
|
382 graphite_dim_t nb_params;
|
|
|
383
|
|
|
384 /* The maximum alias set as assigned to drs by build_alias_sets. */
|
|
|
385 unsigned max_alias_set;
|
|
|
386
|
|
|
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. */
|
|
|
390 vec<poly_bb_p> pbbs;
|
|
|
391
|
|
|
392 /* All the data references in this scop. */
|
|
|
393 vec<dr_info> drs;
|
|
|
394
|
|
|
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 */
|
|
|
408 isl_set *param_context;
|
|
|
409
|
|
|
410 /* The context used internally by isl. */
|
|
|
411 isl_ctx *isl_context;
|
|
|
412
|
|
|
413 /* SCoP original schedule. */
|
|
|
414 isl_schedule *original_schedule;
|
|
|
415
|
|
|
416 /* SCoP transformed schedule. */
|
|
|
417 isl_schedule *transformed_schedule;
|
|
|
418
|
|
|
419 /* The data dependence relation among the data references in this scop. */
|
|
|
420 isl_union_map *dependence;
|
|
|
421 };
|
|
|
422
|
|
|
423 extern scop_p new_scop (edge, edge);
|
|
|
424 extern void free_scop (scop_p);
|
|
|
425 extern gimple_poly_bb_p new_gimple_poly_bb (basic_block, vec<data_reference_p>,
|
|
|
426 vec<scalar_use>, vec<tree>);
|
|
|
427 extern bool apply_poly_transforms (scop_p);
|
|
|
428
|
|
|
429 /* Set the region of SCOP to REGION. */
|
|
|
430
|
|
|
431 static inline void
|
|
|
432 scop_set_region (scop_p scop, sese_info_p region)
|
|
|
433 {
|
|
|
434 scop->scop_info = region;
|
|
|
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
|
|
|
453 extern void scop_get_dependences (scop_p scop);
|
|
|
454
|
|
|
455 bool
|
|
|
456 carries_deps (__isl_keep isl_union_map *schedule,
|
|
|
457 __isl_keep isl_union_map *deps,
|
|
|
458 int depth);
|
|
|
459
|
|
|
460 extern bool build_poly_scop (scop_p);
|
|
|
461 extern bool graphite_regenerate_ast_isl (scop_p);
|
|
|
462 extern void build_scops (vec<scop_p> *);
|
|
145
|
463 extern tree cached_scalar_evolution_in_region (const sese_l &, loop_p, tree);
|
|
111
|
464 extern void dot_all_sese (FILE *, vec<sese_l> &);
|
|
|
465 extern void dot_sese (sese_l &);
|
|
|
466 extern void dot_cfg ();
|
|
|
467
|
|
|
468 #endif
|
