gcc/graphite-poly.h

   1 /* Graphite polyhedral representation.
   2    Copyright (C) 2009 Free Software Foundation, Inc.
   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 typedef struct poly_dr *poly_dr_p;
  26 DEF_VEC_P(poly_dr_p);
  27 DEF_VEC_ALLOC_P (poly_dr_p, heap);
  28
  29 typedef struct poly_bb *poly_bb_p;
  30 DEF_VEC_P(poly_bb_p);
  31 DEF_VEC_ALLOC_P (poly_bb_p, heap);
  32
  33 typedef struct scop *scop_p;
  34 DEF_VEC_P(scop_p);
  35 DEF_VEC_ALLOC_P (scop_p, heap);
  36
  37 typedef ppl_dimension_type graphite_dim_t;
  38
  39 static inline graphite_dim_t pbb_dim_iter_domain (const struct poly_bb *);
  40 static inline graphite_dim_t pbb_nb_params (const struct poly_bb *);
  41 static inline graphite_dim_t scop_nb_params (scop_p);
  42
  43 /* A data reference can write or read some memory or we
  44    just know it may write some memory.  */
  45 enum POLY_DR_TYPE
  46 {
  47   PDR_READ,
  48   /* PDR_MAY_READs are represented using PDR_READS. This does not limit the
  49      expressiveness.  */
  50   PDR_WRITE,
  51   PDR_MAY_WRITE
  52 };
  53
  54 struct poly_dr
  55 {
  56   /* A pointer to compiler's data reference description.  */
  57   void *compiler_dr;
  58
  59   /* A pointer to the PBB that contains this data reference.  */
  60   poly_bb_p pbb;
  61
  62   enum POLY_DR_TYPE type;
  63
  64   /* The access polyhedron contains the polyhedral space this data
  65      reference will access.
  66
  67      The polyhedron contains these dimensions:
  68
  69       - The alias set (a):
  70       Every memory access is classified in at least one alias set.
  71
  72       - The subscripts (s_0, ..., s_n):
  73       The memory is accessed using zero or more subscript dimensions.
  74
  75       - The iteration domain (variables and parameters)
  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
  95      |       A[i][j+b] = m;
  96      |   }
  97
  98      The data access A[i][j+k] in alias set "5" is described like this:
  99
 100      | i   j   k   a   s0  s1  1
 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
 104
 105      The constraints on the data container A[1335][123] are:
 106
 107      | i   j   k   a   s0  s1  1
 108      | 0   0   0   0   1   0   0     >= 0
 109      | 0   0   0   0   0   1   0     >= 0
 110      | 0   0   0   0  -1   0 1335    >= 0
 111      | 0   0   0   0   0  -1 123     >= 0
 112
 113      The pointer "*p" in alias set "5" and "7" is described as a union of
 114      polyhedron:
 115
 116
 117      | i   k   a   s0  1
 118      | 0   0   1   0  -5   =  0
 119      | 0   0   0   1   0   >= 0
 120
 121      "or"
 122
 123      | i   k   a   s0  1
 124      | 0   0   1   0  -7   =  0
 125      | 0   0   0   1   0   >= 0
 126
 127      "*p" accesses all of the object allocated with 'malloc'.
 128
 129      The scalar data access "m" is represented as an array with zero subscript
 130      dimensions.
 131
 132      | i   j   k   a   1
 133      | 0   0   0  -1   15  = 0 */
 134   ppl_Pointset_Powerset_C_Polyhedron_t accesses;
 135   ppl_Pointset_Powerset_C_Polyhedron_t data_container;
 136 };
 137
 138 #define PDR_CDR(PDR) (PDR->compiler_dr)
 139 #define PDR_PBB(PDR) (PDR->pbb)
 140 #define PDR_TYPE(PDR) (PDR->type)
 141 #define PDR_ACCESSES(PDR) (PDR->accesses)
 142 #define PDR_DATA_CONTAINER(PDR) (PDR->data_container)
 143
 144 void new_poly_dr (poly_bb_p, ppl_Pointset_Powerset_C_Polyhedron_t,
 145                   ppl_Pointset_Powerset_C_Polyhedron_t,
 146                   enum POLY_DR_TYPE, void *);
 147 void free_poly_dr (poly_dr_p);
 148 void debug_pdr (poly_dr_p);
 149 void print_pdr (FILE *, poly_dr_p);
 150 static inline scop_p pdr_scop (poly_dr_p pdr);
 151
 152 /* The number of subscripts of the PDR.  */
 153
 154 static inline graphite_dim_t
 155 pdr_nb_subscripts (poly_dr_p pdr)
 156 {
 157   poly_bb_p pbb = PDR_PBB (pdr);
 158   ppl_dimension_type dim;
 159
 160   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PDR_ACCESSES (pdr),
 161                                                       &dim);
 162   return dim - pbb_dim_iter_domain (pbb) - pbb_nb_params (pbb) - 1;
 163 }
 164
 165 /* The dimension of the iteration domain of the scop of PDR.  */
 166
 167 static inline ppl_dimension_type
 168 pdr_dim_iter_domain (poly_dr_p pdr)
 169 {
 170   return pbb_dim_iter_domain (PDR_PBB (pdr));
 171 }
 172
 173 /* The number of parameters of the scop of PDR.  */
 174
 175 static inline ppl_dimension_type
 176 pdr_nb_params (poly_dr_p pdr)
 177 {
 178   return scop_nb_params (pdr_scop (pdr));
 179 }
 180
 181 /* The dimension of the accesses polyhedron of PDR.  */
 182
 183 static inline graphite_dim_t
 184 pdr_dim (poly_dr_p pdr)
 185 {
 186   graphite_dim_t alias_nb_dimensions = 1;
 187
 188   return pbb_dim_iter_domain (PDR_PBB (pdr)) + alias_nb_dimensions
 189     + pdr_nb_subscripts (pdr) + scop_nb_params (pdr_scop (pdr));
 190 }
 191
 192 /* The dimension of the alias set in PDR.  */
 193
 194 static inline ppl_dimension_type
 195 pdr_alias_set_dim (poly_dr_p pdr)
 196 {
 197   poly_bb_p pbb = PDR_PBB (pdr);
 198
 199   return pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
 200 }
 201
 202 /* The dimension in PDR containing subscript S.  */
 203
 204 static inline ppl_dimension_type
 205 pdr_subscript_dim (poly_dr_p pdr, graphite_dim_t s)
 206 {
 207   poly_bb_p pbb = PDR_PBB (pdr);
 208
 209   return pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb) + 1 + s;
 210 }
 211
 212 /* The dimension in PDR containing the loop iterator ITER.  */
 213
 214 static inline ppl_dimension_type
 215 pdr_iterator_dim (poly_dr_p pdr ATTRIBUTE_UNUSED, graphite_dim_t iter)
 216 {
 217   return iter;
 218 }
 219
 220 /* The dimension in PDR containing parameter PARAM.  */
 221
 222 static inline ppl_dimension_type
 223 pdr_parameter_dim (poly_dr_p pdr, graphite_dim_t param)
 224 {
 225   poly_bb_p pbb = PDR_PBB (pdr);
 226
 227   return pbb_dim_iter_domain (pbb) + param;
 228 }
 229
 230 /* POLY_BB represents a blackbox in the polyhedral model.  */
 231
 232 struct poly_bb
 233 {
 234   void *black_box;
 235
 236   scop_p scop;
 237
 238   /* The iteration domain of this bb.
 239      Example:
 240
 241      for (i = a - 7*b + 8; i <= 3*a + 13*b + 20; i++)
 242        for (j = 2; j <= 2*i + 5; j++)
 243          for (k = 0; k <= 5; k++)
 244            S (i,j,k)
 245
 246      Loop iterators: i, j, k
 247      Parameters: a, b
 248
 249      | i >=  a -  7b +  8
 250      | i <= 3a + 13b + 20
 251      | j >= 2
 252      | j <= 2i + 5
 253      | k >= 0
 254      | k <= 5
 255
 256      The number of variables in the DOMAIN may change and is not
 257      related to the number of loops in the original code.  */
 258   ppl_Pointset_Powerset_C_Polyhedron_t domain;
 259
 260   /* The data references we access.  */
 261   VEC (poly_dr_p, heap) *drs;
 262
 263   /* The scattering function containing the transformations.  */
 264   ppl_Polyhedron_t transformed_scattering;
 265
 266
 267   /* The original scattering function.  */
 268   ppl_Polyhedron_t original_scattering;
 269
 270   /* The number of local variables.  */
 271   int nb_local_variables;
 272
 273   /* The number of scattering dimensions in the TRANSFORMED scattering.  */
 274   int nb_scattering_transform;
 275 };
 276
 277 #define PBB_BLACK_BOX(PBB) ((gimple_bb_p) PBB->black_box)
 278 #define PBB_SCOP(PBB) (PBB->scop)
 279 #define PBB_DOMAIN(PBB) (PBB->domain)
 280 #define PBB_DRS(PBB) (PBB->drs)
 281 #define PBB_TRANSFORMED_SCATTERING(PBB) (PBB->transformed_scattering)
 282 #define PBB_ORIGINAL_SCATTERING(PBB) (PBB->original_scattering)
 283 #define PBB_NB_LOCAL_VARIABLES(PBB) (PBB->nb_local_variables)
 284 #define PBB_NB_SCATTERING_TRANSFORM(PBB) (PBB->nb_scattering_transform)
 285
 286 extern void new_poly_bb (scop_p, void *);
 287 extern void free_poly_bb (poly_bb_p);
 288 extern void debug_loop_vec (poly_bb_p);
 289 extern void schedule_to_scattering (poly_bb_p, int);
 290 extern void print_pbb_domain (FILE *, poly_bb_p);
 291 extern void print_pbb (FILE *, poly_bb_p);
 292 extern void print_scop_context (FILE *, scop_p);
 293 extern void print_scop (FILE *, scop_p);
 294 extern void debug_pbb_domain (poly_bb_p);
 295 extern void debug_pbb (poly_bb_p);
 296 extern void print_pdrs (FILE *, poly_bb_p);
 297 extern void debug_pdrs (poly_bb_p);
 298 extern void debug_scop_context (scop_p);
 299 extern void debug_scop (scop_p);
 300 extern void print_scop_params (FILE *, scop_p);
 301 extern void debug_scop_params (scop_p);
 302 extern void print_iteration_domain (FILE *, poly_bb_p);
 303 extern void print_iteration_domains (FILE *, scop_p);
 304 extern void debug_iteration_domain (poly_bb_p);
 305 extern void debug_iteration_domains (scop_p);
 306 extern bool scop_do_interchange (scop_p);
 307 extern bool scop_do_strip_mine (scop_p);
 308 extern void pbb_number_of_iterations (poly_bb_p, graphite_dim_t, Value);
 309
 310 /* The scop that contains the PDR.  */
 311
 312 static inline scop_p pdr_scop (poly_dr_p pdr)
 313 {
 314   return PBB_SCOP (PDR_PBB (pdr));
 315 }
 316
 317 /* Set black box of PBB to BLACKBOX.  */
 318
 319 static inline void
 320 pbb_set_black_box (poly_bb_p pbb, void *black_box)
 321 {
 322   pbb->black_box = black_box;
 323 }
 324
 325 /* The number of loops around PBB: the dimension of the iteration
 326    domain.  */
 327
 328 static inline graphite_dim_t
 329 pbb_dim_iter_domain (const struct poly_bb *pbb)
 330 {
 331   scop_p scop = PBB_SCOP (pbb);
 332   ppl_dimension_type dim;
 333
 334   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb), &dim);
 335   return dim - scop_nb_params (scop);
 336 }
 337
 338 /* The number of params defined in PBB.  */
 339
 340 static inline graphite_dim_t
 341 pbb_nb_params (const struct poly_bb *pbb)
 342 {
 343   scop_p scop = PBB_SCOP (pbb);
 344
 345   return scop_nb_params (scop);
 346 }
 347
 348 /* The number of scattering dimensions in the SCATTERING polyhedron
 349    of a PBB for a given SCOP.  */
 350
 351 static inline graphite_dim_t
 352 pbb_nb_scattering_orig (const struct poly_bb *pbb)
 353 {
 354   return 2 * pbb_dim_iter_domain (pbb) + 1;
 355 }
 356
 357 /* The number of scattering dimensions in PBB.  */
 358
 359 static inline graphite_dim_t
 360 pbb_nb_scattering_transform (const struct poly_bb *pbb)
 361 {
 362   return PBB_NB_SCATTERING_TRANSFORM (pbb);
 363 }
 364
 365 /* Returns the number of local variables used in the transformed
 366    scattering polyhedron of PBB.  */
 367
 368 static inline graphite_dim_t
 369 pbb_nb_local_vars (const struct poly_bb *pbb)
 370 {
 371   /* For now we do not have any local variables, as we do not do strip
 372      mining for example.  */
 373   return PBB_NB_LOCAL_VARIABLES (pbb);
 374 }
 375
 376 /* The dimension in the domain of PBB containing the iterator ITER.  */
 377
 378 static inline ppl_dimension_type
 379 pbb_iterator_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t iter)
 380 {
 381   return iter;
 382 }
 383
 384 /* The dimension in the domain of PBB containing the iterator ITER.  */
 385
 386 static inline ppl_dimension_type
 387 pbb_parameter_dim (poly_bb_p pbb, graphite_dim_t param)
 388 {
 389   return param
 390     + pbb_dim_iter_domain (pbb);
 391 }
 392
 393 /* The dimension in the original scattering polyhedron of PBB
 394    containing the scattering iterator SCATTER.  */
 395
 396 static inline ppl_dimension_type
 397 psco_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t scatter)
 398 {
 399   gcc_assert (scatter < pbb_nb_scattering_orig (pbb));
 400   return scatter;
 401 }
 402
 403 /* The dimension in the transformed scattering polyhedron of PBB
 404    containing the scattering iterator SCATTER.  */
 405
 406 static inline ppl_dimension_type
 407 psct_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t scatter)
 408 {
 409   gcc_assert (scatter <= pbb_nb_scattering_transform (pbb));
 410   return scatter;
 411 }
 412
 413 ppl_dimension_type psct_scattering_dim_for_loop_depth (poly_bb_p,
 414                                                        graphite_dim_t);
 415
 416 /* The dimension in the transformed scattering polyhedron of PBB of
 417    the local variable LV.  */
 418
 419 static inline ppl_dimension_type
 420 psct_local_var_dim (poly_bb_p pbb, graphite_dim_t lv)
 421 {
 422   gcc_assert (lv <= pbb_nb_local_vars (pbb));
 423   return lv + pbb_nb_scattering_transform (pbb);
 424 }
 425
 426 /* The dimension in the original scattering polyhedron of PBB
 427    containing the loop iterator ITER.  */
 428
 429 static inline ppl_dimension_type
 430 psco_iterator_dim (poly_bb_p pbb, graphite_dim_t iter)
 431 {
 432   gcc_assert (iter < pbb_dim_iter_domain (pbb));
 433   return iter + pbb_nb_scattering_orig (pbb);
 434 }
 435
 436 /* The dimension in the transformed scattering polyhedron of PBB
 437    containing the loop iterator ITER.  */
 438
 439 static inline ppl_dimension_type
 440 psct_iterator_dim (poly_bb_p pbb, graphite_dim_t iter)
 441 {
 442   gcc_assert (iter < pbb_dim_iter_domain (pbb));
 443   return iter
 444     + pbb_nb_scattering_transform (pbb)
 445     + pbb_nb_local_vars (pbb);
 446 }
 447
 448 /* The dimension in the original scattering polyhedron of PBB
 449    containing parameter PARAM.  */
 450
 451 static inline ppl_dimension_type
 452 psco_parameter_dim (poly_bb_p pbb, graphite_dim_t param)
 453 {
 454   gcc_assert (param < pbb_nb_params (pbb));
 455   return param
 456     + pbb_nb_scattering_orig (pbb)
 457     + pbb_dim_iter_domain (pbb);
 458 }
 459
 460 /* The dimension in the transformed scattering polyhedron of PBB
 461    containing parameter PARAM.  */
 462
 463 static inline ppl_dimension_type
 464 psct_parameter_dim (poly_bb_p pbb, graphite_dim_t param)
 465 {
 466   gcc_assert (param < pbb_nb_params (pbb));
 467   return param
 468     + pbb_nb_scattering_transform (pbb)
 469     + pbb_nb_local_vars (pbb)
 470     + pbb_dim_iter_domain (pbb);
 471 }
 472
 473 /* Adds to the transformed scattering polyhedron of PBB a new local
 474    variable and returns its index.  */
 475
 476 static inline graphite_dim_t
 477 psct_add_local_variable (poly_bb_p pbb)
 478 {
 479   graphite_dim_t nlv = pbb_nb_local_vars (pbb);
 480   ppl_dimension_type lv_column = psct_local_var_dim (pbb, nlv);
 481   ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb), lv_column, 1);
 482   PBB_NB_LOCAL_VARIABLES (pbb) += 1;
 483   return nlv;
 484 }
 485
 486 /* Adds a dimension to the transformed scattering polyhedron of PBB at
 487    INDEX.  */
 488
 489 static inline void
 490 psct_add_scattering_dimension (poly_bb_p pbb, ppl_dimension_type index)
 491 {
 492   gcc_assert (index < pbb_nb_scattering_transform (pbb));
 493
 494   ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb), index, 1);
 495   PBB_NB_SCATTERING_TRANSFORM (pbb) += 1;
 496 }
 497
 498 /* A SCOP is a Static Control Part of the program, simple enough to be
 499    represented in polyhedral form.  */
 500 struct scop
 501 {
 502   /* A SCOP is defined as a SESE region.  */
 503   void *region;
 504
 505   /* Number of parameters in SCoP.  */
 506   graphite_dim_t nb_params;
 507
 508   /* All the basic blocks in this scop that contain memory references
 509      and that will be represented as statements in the polyhedral
 510      representation.  */
 511   VEC (poly_bb_p, heap) *bbs;
 512
 513   /* Data dependence graph for this SCoP.  */
 514   struct graph *dep_graph;
 515
 516   /* The context describes known restrictions concerning the parameters
 517      and relations in between the parameters.
 518
 519   void f (int8_t a, uint_16_t b) {
 520     c = 2 a + b;
 521     ...
 522   }
 523
 524   Here we can add these restrictions to the context:
 525
 526   -128 >= a >= 127
 527      0 >= b >= 65,535
 528      c = 2a + b  */
 529   ppl_Pointset_Powerset_C_Polyhedron_t context;
 530
 531   /* A hashtable of the original pairs of dependent data references.
 532      For each pair of dependent data references, the dependence
 533      polyhedron is stored also.  */
 534   htab_t original_pdr_pairs;
 535 };
 536
 537 #define SCOP_BBS(S) (S->bbs)
 538 #define SCOP_REGION(S) ((sese) S->region)
 539 #define SCOP_DEP_GRAPH(S) (S->dep_graph)
 540 #define SCOP_CONTEXT(S) (S->context)
 541 #define SCOP_ORIGINAL_PDR_PAIRS(S) (S->original_pdr_pairs)
 542
 543 extern scop_p new_scop (void *);
 544 extern void free_scop (scop_p);
 545 extern void free_scops (VEC (scop_p, heap) *);
 546 extern void print_generated_program (FILE *, scop_p);
 547 extern void debug_generated_program (scop_p);
 548 extern void print_scattering_function (FILE *, poly_bb_p);
 549 extern void print_scattering_functions (FILE *, scop_p);
 550 extern void debug_scattering_function (poly_bb_p);
 551 extern void debug_scattering_functions (scop_p);
 552 extern int scop_max_loop_depth (scop_p);
 553 extern int unify_scattering_dimensions (scop_p);
 554 extern bool apply_poly_transforms (scop_p);
 555 extern bool graphite_legal_transform (scop_p);
 556
 557 /* Set the region of SCOP to REGION.  */
 558
 559 static inline void
 560 scop_set_region (scop_p scop, void *region)
 561 {
 562   scop->region = region;
 563 }
 564
 565 /* Returns the number of parameters for SCOP.  */
 566
 567 static inline graphite_dim_t
 568 scop_nb_params (scop_p scop)
 569 {
 570   return scop->nb_params;
 571 }
 572
 573 /* Set the number of params of SCOP to NB_PARAMS.  */
 574
 575 static inline void
 576 scop_set_nb_params (scop_p scop, graphite_dim_t nb_params)
 577 {
 578   scop->nb_params = nb_params;
 579 }
 580
 581 #endif