aboutsummaryrefslogtreecommitdiff
path: root/gcc/graphite.h
blob: bbee9f4a73999d94b26258e6d69fa0ab211d1c9b (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
/* Graphite polyhedral representation.
   Copyright (C) 2009-2017 Free Software Foundation, Inc.
   Contributed by Sebastian Pop <sebastian.pop@amd.com> and
   Tobias Grosser <grosser@fim.uni-passau.de>.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3, or (at your option)
any later version.

GCC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

#ifndef GCC_GRAPHITE_POLY_H
#define GCC_GRAPHITE_POLY_H

#include "sese.h"
#include <isl/options.h>
#include <isl/ctx.h>
#include <isl/val_gmp.h>
#include <isl/set.h>
#include <isl/union_set.h>
#include <isl/map.h>
#include <isl/union_map.h>
#include <isl/aff.h>
#include <isl/constraint.h>
#include <isl/flow.h>
#include <isl/ilp.h>
#include <isl/schedule.h>
#include <isl/ast_build.h>

#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
/* isl 0.15 or later.  */
#include <isl/schedule_node.h>

#else
/* isl 0.14 or 0.13.  */
# define isl_stat int
# define isl_stat_ok 0
#endif

typedef struct poly_dr *poly_dr_p;

typedef struct poly_bb *poly_bb_p;

typedef struct scop *scop_p;

typedef unsigned graphite_dim_t;

static inline graphite_dim_t scop_nb_params (scop_p);

/* A data reference can write or read some memory or we
   just know it may write some memory.  */
enum poly_dr_type
{
  PDR_READ,
  /* PDR_MAY_READs are represented using PDR_READS.  This does not
     limit the expressiveness.  */
  PDR_WRITE,
  PDR_MAY_WRITE
};

struct poly_dr
{
  /* An identifier for this PDR.  */
  int id;

  /* The number of data refs identical to this one in the PBB.  */
  int nb_refs;

  /* A pointer to the gimple stmt containing this reference.  */
  gimple *stmt;

  /* A pointer to the PBB that contains this data reference.  */
  poly_bb_p pbb;

  enum poly_dr_type type;

  /* The access polyhedron contains the polyhedral space this data
     reference will access.

     The polyhedron contains these dimensions:

     - The alias set (a):
     Every memory access is classified in at least one alias set.

     - The subscripts (s_0, ..., s_n):
     The memory is accessed using zero or more subscript dimensions.

     - The iteration domain (variables and parameters)

     Do not hardcode the dimensions.  Use the following accessor functions:
     - pdr_alias_set_dim
     - pdr_subscript_dim
     - pdr_iterator_dim
     - pdr_parameter_dim

     Example:

     | int A[1335][123];
     | int *p = malloc ();
     |
     | k = ...
     | for i
     |   {
     |     if (unknown_function ())
     |       p = A;
     |       ... = p[?][?];
     | 	   for j
     |       A[i][j+k] = m;
     |   }

     The data access A[i][j+k] in alias set "5" is described like this:

     | i   j   k   a  s0  s1   1
     | 0   0   0   1   0   0  -5     =  0
     |-1   0   0   0   1   0   0     =  0
     | 0  -1  -1   0   0   1   0     =  0
     | 0   0   0   0   1   0   0     >= 0  # The last four lines describe the
     | 0   0   0   0   0   1   0     >= 0  # array size.
     | 0   0   0   0  -1   0 1335    >= 0
     | 0   0   0   0   0  -1 123     >= 0

     The pointer "*p" in alias set "5" and "7" is described as a union of
     polyhedron:


     | i   k   a  s0   1
     | 0   0   1   0  -5   =  0
     | 0   0   0   1   0   >= 0

     "or"

     | i   k   a  s0   1
     | 0   0   1   0  -7   =  0
     | 0   0   0   1   0   >= 0

     "*p" accesses all of the object allocated with 'malloc'.

     The scalar data access "m" is represented as an array with zero subscript
     dimensions.

     | i   j   k   a   1
     | 0   0   0  -1   15  = 0

     The difference between the graphite internal format for access data and
     the OpenSop format is in the order of columns.
     Instead of having:

     | i   j   k   a  s0  s1   1
     | 0   0   0   1   0   0  -5     =  0
     |-1   0   0   0   1   0   0     =  0
     | 0  -1  -1   0   0   1   0     =  0
     | 0   0   0   0   1   0   0     >= 0  # The last four lines describe the
     | 0   0   0   0   0   1   0     >= 0  # array size.
     | 0   0   0   0  -1   0 1335    >= 0
     | 0   0   0   0   0  -1 123     >= 0

     In OpenScop we have:

     | a  s0  s1   i   j   k   1
     | 1   0   0   0   0   0  -5     =  0
     | 0   1   0  -1   0   0   0     =  0
     | 0   0   1   0  -1  -1   0     =  0
     | 0   1   0   0   0   0   0     >= 0  # The last four lines describe the
     | 0   0   1   0   0   0   0     >= 0  # array size.
     | 0  -1   0   0   0   0 1335    >= 0
     | 0   0  -1   0   0   0 123     >= 0

     The OpenScop access function is printed as follows:

     | 1  # The number of disjunct components in a union of access functions.
     | R C O I L P  # Described bellow.
     | a  s0  s1   i   j   k   1
     | 1   0   0   0   0   0  -5     =  0
     | 0   1   0  -1   0   0   0     =  0
     | 0   0   1   0  -1  -1   0     =  0
     | 0   1   0   0   0   0   0     >= 0  # The last four lines describe the
     | 0   0   1   0   0   0   0     >= 0  # array size.
     | 0  -1   0   0   0   0 1335    >= 0
     | 0   0  -1   0   0   0 123     >= 0

     Where:
     - R: Number of rows.
     - C: Number of columns.
     - O: Number of output dimensions = alias set + number of subscripts.
     - I: Number of input dimensions (iterators).
     - L: Number of local (existentially quantified) dimensions.
     - P: Number of parameters.

     In the example, the vector "R C O I L P" is "7 7 3 2 0 1".  */
  isl_map *accesses;
  isl_set *subscript_sizes;
};

#define PDR_ID(PDR) (PDR->id)
#define PDR_NB_REFS(PDR) (PDR->nb_refs)
#define PDR_PBB(PDR) (PDR->pbb)
#define PDR_TYPE(PDR) (PDR->type)
#define PDR_ACCESSES(PDR) (NULL)

void new_poly_dr (poly_bb_p, gimple *, enum poly_dr_type,
		  isl_map *, isl_set *);
void debug_pdr (poly_dr_p);
void print_pdr (FILE *, poly_dr_p);

static inline bool
pdr_read_p (poly_dr_p pdr)
{
  return PDR_TYPE (pdr) == PDR_READ;
}

/* Returns true when PDR is a "write".  */

static inline bool
pdr_write_p (poly_dr_p pdr)
{
  return PDR_TYPE (pdr) == PDR_WRITE;
}

/* Returns true when PDR is a "may write".  */

static inline bool
pdr_may_write_p (poly_dr_p pdr)
{
  return PDR_TYPE (pdr) == PDR_MAY_WRITE;
}

/* POLY_BB represents a blackbox in the polyhedral model.  */

struct poly_bb
{
  /* Pointer to a basic block or a statement in the compiler.  */
  gimple_poly_bb_p black_box;

  /* Pointer to the SCOP containing this PBB.  */
  scop_p scop;

  /* The iteration domain of this bb.  The layout of this polyhedron
     is I|G with I the iteration domain, G the context parameters.

     Example:

     for (i = a - 7*b + 8; i <= 3*a + 13*b + 20; i++)
       for (j = 2; j <= 2*i + 5; j++)
         for (k = 0; k <= 5; k++)
           S (i,j,k)

     Loop iterators: i, j, k
     Parameters: a, b

     | i >=  a -  7b +  8
     | i <= 3a + 13b + 20
     | j >= 2
     | j <= 2i + 5
     | k >= 0
     | k <= 5

     The number of variables in the DOMAIN may change and is not
     related to the number of loops in the original code.  */
  isl_set *domain;
#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
  isl_set *iterators;
#else
  /* The original scattering.  */
  isl_map *schedule;

  /* The transformed scattering.  */
  isl_map *transformed;

  /* A copy of the transformed scattering.  */
  isl_map *saved;
#endif

  /* The data references we access.  */
  vec<poly_dr_p> drs;

  /* The last basic block generated for this pbb.  */
  basic_block new_bb;
};

#define PBB_BLACK_BOX(PBB) ((gimple_poly_bb_p) PBB->black_box)
#define PBB_SCOP(PBB) (PBB->scop)
#define PBB_DRS(PBB) (PBB->drs)

extern poly_bb_p new_poly_bb (scop_p, gimple_poly_bb_p);
extern void print_pbb_domain (FILE *, poly_bb_p);
extern void print_pbb (FILE *, poly_bb_p);
extern void print_scop_context (FILE *, scop_p);
extern void print_scop (FILE *, scop_p);
extern void debug_pbb_domain (poly_bb_p);
extern void debug_pbb (poly_bb_p);
extern void print_pdrs (FILE *, poly_bb_p);
extern void debug_pdrs (poly_bb_p);
extern void debug_scop_context (scop_p);
extern void debug_scop (scop_p);
extern void print_scop_params (FILE *, scop_p);
extern void debug_scop_params (scop_p);
extern void print_iteration_domain (FILE *, poly_bb_p);
extern void print_iteration_domains (FILE *, scop_p);
extern void debug_iteration_domain (poly_bb_p);
extern void debug_iteration_domains (scop_p);
extern void print_isl_set (FILE *, isl_set *);
extern void print_isl_map (FILE *, isl_map *);
extern void print_isl_union_map (FILE *, isl_union_map *);
extern void print_isl_aff (FILE *, isl_aff *);
extern void print_isl_constraint (FILE *, isl_constraint *);
extern void print_isl_schedule (FILE *, isl_schedule *);
extern void debug_isl_schedule (isl_schedule *);
extern void print_isl_ast (FILE *, isl_ast_node *);
extern void debug_isl_ast (isl_ast_node *);
extern void debug_isl_set (isl_set *);
extern void debug_isl_map (isl_map *);
extern void debug_isl_union_map (isl_union_map *);
extern void debug_isl_aff (isl_aff *);
extern void debug_isl_constraint (isl_constraint *);
extern void debug_gmp_value (mpz_t);
extern void debug_scop_pbb (scop_p scop, int i);
extern void print_schedule_ast (FILE *, __isl_keep isl_schedule *, scop_p);
extern void debug_schedule_ast (__isl_keep isl_schedule *, scop_p);

/* The basic block of the PBB.  */

static inline basic_block
pbb_bb (poly_bb_p pbb)
{
  return GBB_BB (PBB_BLACK_BOX (pbb));
}

static inline int
pbb_index (poly_bb_p pbb)
{
  return pbb_bb (pbb)->index;
}

/* The loop of the PBB.  */

static inline loop_p
pbb_loop (poly_bb_p pbb)
{
  return gbb_loop (PBB_BLACK_BOX (pbb));
}

/* The scop that contains the PDR.  */

static inline scop_p
pdr_scop (poly_dr_p pdr)
{
  return PBB_SCOP (PDR_PBB (pdr));
}

/* Set black box of PBB to BLACKBOX.  */

static inline void
pbb_set_black_box (poly_bb_p pbb, gimple_poly_bb_p black_box)
{
  pbb->black_box = black_box;
}

/* A helper structure to keep track of data references, polyhedral BBs, and
   alias sets.  */

struct dr_info
{
  enum {
    invalid_alias_set = -1
  };
  /* The data reference.  */
  data_reference_p dr;

  /* The polyhedral BB containing this DR.  */
  poly_bb_p pbb;

  /* ALIAS_SET is the SCC number assigned by a graph_dfs of the alias graph.
     -1 is an invalid alias set.  */
  int alias_set;

  /* Construct a DR_INFO from a data reference DR, an ALIAS_SET, and a PBB.  */
  dr_info (data_reference_p dr, poly_bb_p pbb,
	   int alias_set = invalid_alias_set)
    : dr (dr), pbb (pbb), alias_set (alias_set) {}
};

/* A SCOP is a Static Control Part of the program, simple enough to be
   represented in polyhedral form.  */
struct scop
{
  /* A SCOP is defined as a SESE region.  */
  sese_info_p scop_info;

  /* Number of parameters in SCoP.  */
  graphite_dim_t nb_params;

  /* All the basic blocks in this scop that contain memory references
     and that will be represented as statements in the polyhedral
     representation.  */
  vec<poly_bb_p> pbbs;

  /* All the data references in this scop.  */
  vec<dr_info> drs;

  /* The context describes known restrictions concerning the parameters
     and relations in between the parameters.

  void f (int8_t a, uint_16_t b) {
    c = 2 a + b;
    ...
  }

  Here we can add these restrictions to the context:

  -128 >= a >= 127
     0 >= b >= 65,535
     c = 2a + b  */
  isl_set *param_context;

  /* The context used internally by isl.  */
  isl_ctx *isl_context;

#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
  /* SCoP original schedule.  */
  isl_schedule *original_schedule;

  /* SCoP transformed schedule.  */
  isl_schedule *transformed_schedule;
#else
  /* SCoP final schedule.  */
  isl_schedule *schedule;
#endif

  /* The data dependence relation among the data references in this scop.  */
  isl_union_map *dependence;
};

extern scop_p new_scop (edge, edge);
extern void free_scop (scop_p);
extern gimple_poly_bb_p new_gimple_poly_bb (basic_block, vec<data_reference_p>,
					    vec<scalar_use>, vec<tree>);
extern bool apply_poly_transforms (scop_p);

/* Set the region of SCOP to REGION.  */

static inline void
scop_set_region (scop_p scop, sese_info_p region)
{
  scop->scop_info = region;
}

/* Returns the number of parameters for SCOP.  */

static inline graphite_dim_t
scop_nb_params (scop_p scop)
{
  return scop->nb_params;
}

/* Set the number of params of SCOP to NB_PARAMS.  */

static inline void
scop_set_nb_params (scop_p scop, graphite_dim_t nb_params)
{
  scop->nb_params = nb_params;
}

#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
extern void scop_get_dependences (scop_p scop);
#else
extern isl_union_map *scop_get_dependences (scop_p scop);
#endif

bool
carries_deps (__isl_keep isl_union_map *schedule,
	      __isl_keep isl_union_map *deps,
	      int depth);

extern bool build_poly_scop (scop_p);
extern bool graphite_regenerate_ast_isl (scop_p);
extern void build_scops (vec<scop_p> *);
extern void dot_all_sese (FILE *, vec<sese_l> &);
extern void dot_sese (sese_l &);
extern void dot_cfg ();

#endif