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
  49      limit the expressiveness.  */
  50   PDR_WRITE,
  51   PDR_MAY_WRITE
  52 };
  53
  54 struct poly_dr
  55 {
  56   /* An identifier for this PDR.  */
  57   int id;
  58
  59   /* The number of data refs identical to this one in the PBB.  */
  60   int nb_refs;
  61
  62   /* A pointer to compiler's data reference description.  */
  63   void *compiler_dr;
  64
  65   /* A pointer to the PBB that contains this data reference.  */
  66   poly_bb_p pbb;
  67
  68   enum poly_dr_type type;
  69
  70   /* The access polyhedron contains the polyhedral space this data
  71      reference will access.
  72
  73      The polyhedron contains these dimensions:
  74
  75      - The alias set (a):
  76      Every memory access is classified in at least one alias set.
  77
  78      - The subscripts (s_0, ..., s_n):
  79      The memory is accessed using zero or more subscript dimensions.
  80
  81      - The iteration domain (variables and parameters)
  82
  83      Do not hardcode the dimensions.  Use the following accessor functions:
  84      - pdr_alias_set_dim
  85      - pdr_subscript_dim
  86      - pdr_iterator_dim
  87      - pdr_parameter_dim
  88
  89      Example:
  90
  91      | int A[1335][123];
  92      | int *p = malloc ();
  93      |
  94      | k = ...
  95      | for i
  96      |   {
  97      |     if (unknown_function ())
  98      |       p = A;
  99      |       ... = p[?][?];
 100      |     for j
 101      |       A[i][j+k] = m;
 102      |   }
 103
 104      The data access A[i][j+k] in alias set "5" is described like this:
 105
 106      | i   j   k   a  s0  s1   1
 107      | 0   0   0   1   0   0  -5     =  0
 108      |-1   0   0   0   1   0   0     =  0
 109      | 0  -1  -1   0   0   1   0     =  0
 110      | 0   0   0   0   1   0   0     >= 0  # The last four lines describe the
 111      | 0   0   0   0   0   1   0     >= 0  # array size.
 112      | 0   0   0   0  -1   0 1335    >= 0
 113      | 0   0   0   0   0  -1 123     >= 0
 114
 115      The pointer "*p" in alias set "5" and "7" is described as a union of
 116      polyhedron:
 117
 118
 119      | i   k   a  s0   1
 120      | 0   0   1   0  -5   =  0
 121      | 0   0   0   1   0   >= 0
 122
 123      "or"
 124
 125      | i   k   a  s0   1
 126      | 0   0   1   0  -7   =  0
 127      | 0   0   0   1   0   >= 0
 128
 129      "*p" accesses all of the object allocated with 'malloc'.
 130
 131      The scalar data access "m" is represented as an array with zero subscript
 132      dimensions.
 133
 134      | i   j   k   a   1
 135      | 0   0   0  -1   15  = 0 */
 136   ppl_Pointset_Powerset_C_Polyhedron_t accesses;
 137
 138   /* Data reference's base object set number, we must assure 2 pdrs are in the
 139      same base object set before dependency checking.  */
 140   int dr_base_object_set;
 141
 142   /* The number of subscripts.  */
 143   graphite_dim_t nb_subscripts;
 144 };
 145
 146 #define PDR_ID(PDR) (PDR->id)
 147 #define PDR_NB_REFS(PDR) (PDR->nb_refs)
 148 #define PDR_CDR(PDR) (PDR->compiler_dr)
 149 #define PDR_PBB(PDR) (PDR->pbb)
 150 #define PDR_TYPE(PDR) (PDR->type)
 151 #define PDR_ACCESSES(PDR) (PDR->accesses)
 152 #define PDR_BASE_OBJECT_SET(PDR) (PDR->dr_base_object_set)
 153 #define PDR_NB_SUBSCRIPTS(PDR) (PDR->nb_subscripts)
 154
 155 void new_poly_dr (poly_bb_p, int, ppl_Pointset_Powerset_C_Polyhedron_t,
 156                   enum poly_dr_type, void *, graphite_dim_t);
 157 void free_poly_dr (poly_dr_p);
 158 void debug_pdr (poly_dr_p);
 159 void print_pdr (FILE *, poly_dr_p);
 160 static inline scop_p pdr_scop (poly_dr_p pdr);
 161
 162 /* The dimension of the PDR_ACCESSES polyhedron of PDR.  */
 163
 164 static inline ppl_dimension_type
 165 pdr_dim (poly_dr_p pdr)
 166 {
 167   ppl_dimension_type dim;
 168   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PDR_ACCESSES (pdr),
 169                                                       &dim);
 170   return dim;
 171 }
 172
 173 /* The dimension of the iteration domain of the scop of PDR.  */
 174
 175 static inline ppl_dimension_type
 176 pdr_dim_iter_domain (poly_dr_p pdr)
 177 {
 178   return pbb_dim_iter_domain (PDR_PBB (pdr));
 179 }
 180
 181 /* The number of parameters of the scop of PDR.  */
 182
 183 static inline ppl_dimension_type
 184 pdr_nb_params (poly_dr_p pdr)
 185 {
 186   return scop_nb_params (pdr_scop (pdr));
 187 }
 188
 189 /* The dimension of the alias set in PDR.  */
 190
 191 static inline ppl_dimension_type
 192 pdr_alias_set_dim (poly_dr_p pdr)
 193 {
 194   poly_bb_p pbb = PDR_PBB (pdr);
 195
 196   return pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
 197 }
 198
 199 /* The dimension in PDR containing subscript S.  */
 200
 201 static inline ppl_dimension_type
 202 pdr_subscript_dim (poly_dr_p pdr, graphite_dim_t s)
 203 {
 204   poly_bb_p pbb = PDR_PBB (pdr);
 205
 206   return pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb) + 1 + s;
 207 }
 208
 209 /* The dimension in PDR containing the loop iterator ITER.  */
 210
 211 static inline ppl_dimension_type
 212 pdr_iterator_dim (poly_dr_p pdr ATTRIBUTE_UNUSED, graphite_dim_t iter)
 213 {
 214   return iter;
 215 }
 216
 217 /* The dimension in PDR containing parameter PARAM.  */
 218
 219 static inline ppl_dimension_type
 220 pdr_parameter_dim (poly_dr_p pdr, graphite_dim_t param)
 221 {
 222   poly_bb_p pbb = PDR_PBB (pdr);
 223
 224   return pbb_dim_iter_domain (pbb) + param;
 225 }
 226
 227 /* Returns true when PDR is a "read".  */
 228
 229 static inline bool
 230 pdr_read_p (poly_dr_p pdr)
 231 {
 232   return PDR_TYPE (pdr) == PDR_READ;
 233 }
 234
 235 /* Returns true when PDR is a "write".  */
 236
 237 static inline bool
 238 pdr_write_p (poly_dr_p pdr)
 239 {
 240   return PDR_TYPE (pdr) == PDR_WRITE;
 241 }
 242
 243 /* Returns true when PDR is a "may write".  */
 244
 245 static inline bool
 246 pdr_may_write_p (poly_dr_p pdr)
 247 {
 248   return PDR_TYPE (pdr) == PDR_MAY_WRITE;
 249 }
 250
 251 /* Return true when PDR1 and PDR2 are similar data accesses: they have
 252    the same base array, and the same access functions.  */
 253
 254 static inline bool
 255 same_pdr_p (poly_dr_p pdr1, poly_dr_p pdr2)
 256 {
 257   return PDR_TYPE (pdr1) == PDR_TYPE (pdr2)
 258     && PDR_NB_SUBSCRIPTS (pdr1) == PDR_NB_SUBSCRIPTS (pdr2)
 259     && PDR_BASE_OBJECT_SET (pdr1) == PDR_BASE_OBJECT_SET (pdr2);
 260 }
 261
 262 typedef struct poly_scattering *poly_scattering_p;
 263
 264 struct poly_scattering
 265 {
 266   /* The scattering function containing the transformations.  */
 267   ppl_Polyhedron_t scattering;
 268
 269   /* The number of local variables.  */
 270   int nb_local_variables;
 271
 272   /* The number of scattering dimensions.  */
 273   int nb_scattering;
 274 };
 275
 276 /* POLY_BB represents a blackbox in the polyhedral model.  */
 277
 278 struct poly_bb
 279 {
 280   void *black_box;
 281
 282   scop_p scop;
 283
 284   /* The iteration domain of this bb.
 285      Example:
 286
 287      for (i = a - 7*b + 8; i <= 3*a + 13*b + 20; i++)
 288        for (j = 2; j <= 2*i + 5; j++)
 289          for (k = 0; k <= 5; k++)
 290            S (i,j,k)
 291
 292      Loop iterators: i, j, k
 293      Parameters: a, b
 294
 295      | i >=  a -  7b +  8
 296      | i <= 3a + 13b + 20
 297      | j >= 2
 298      | j <= 2i + 5
 299      | k >= 0
 300      | k <= 5
 301
 302      The number of variables in the DOMAIN may change and is not
 303      related to the number of loops in the original code.  */
 304   ppl_Pointset_Powerset_C_Polyhedron_t domain;
 305
 306   /* The data references we access.  */
 307   VEC (poly_dr_p, heap) *drs;
 308
 309   /* The original scattering.  */
 310   poly_scattering_p original;
 311
 312   /* The transformed scattering.  */
 313   poly_scattering_p transformed;
 314
 315   /* A copy of the transformed scattering.  */
 316   poly_scattering_p saved;
 317
 318   /* True when the PDR duplicates have already been removed.  */
 319   bool pdr_duplicates_removed;
 320
 321   /* True when this PBB contains only a reduction statement.  */
 322   bool is_reduction;
 323 };
 324
 325 #define PBB_BLACK_BOX(PBB) ((gimple_bb_p) PBB->black_box)
 326 #define PBB_SCOP(PBB) (PBB->scop)
 327 #define PBB_DOMAIN(PBB) (PBB->domain)
 328 #define PBB_DRS(PBB) (PBB->drs)
 329 #define PBB_ORIGINAL(PBB) (PBB->original)
 330 #define PBB_ORIGINAL_SCATTERING(PBB) (PBB->original->scattering)
 331 #define PBB_TRANSFORMED(PBB) (PBB->transformed)
 332 #define PBB_TRANSFORMED_SCATTERING(PBB) (PBB->transformed->scattering)
 333 #define PBB_SAVED(PBB) (PBB->saved)
 334 #define PBB_NB_LOCAL_VARIABLES(PBB) (PBB->transformed->nb_local_variables)
 335 #define PBB_NB_SCATTERING_TRANSFORM(PBB) (PBB->transformed->nb_scattering)
 336 #define PBB_PDR_DUPLICATES_REMOVED(PBB) (PBB->pdr_duplicates_removed)
 337 #define PBB_IS_REDUCTION(PBB) (PBB->is_reduction)
 338
 339 extern void new_poly_bb (scop_p, void *, bool);
 340 extern void free_poly_bb (poly_bb_p);
 341 extern void debug_loop_vec (poly_bb_p);
 342 extern void schedule_to_scattering (poly_bb_p, int);
 343 extern void print_pbb_domain (FILE *, poly_bb_p);
 344 extern void print_pbb (FILE *, poly_bb_p);
 345 extern void print_scop_context (FILE *, scop_p);
 346 extern void print_scop (FILE *, scop_p);
 347 extern void debug_pbb_domain (poly_bb_p);
 348 extern void debug_pbb (poly_bb_p);
 349 extern void print_pdrs (FILE *, poly_bb_p);
 350 extern void debug_pdrs (poly_bb_p);
 351 extern void debug_scop_context (scop_p);
 352 extern void debug_scop (scop_p);
 353 extern void print_scop_params (FILE *, scop_p);
 354 extern void debug_scop_params (scop_p);
 355 extern void print_iteration_domain (FILE *, poly_bb_p);
 356 extern void print_iteration_domains (FILE *, scop_p);
 357 extern void debug_iteration_domain (poly_bb_p);
 358 extern void debug_iteration_domains (scop_p);
 359 extern bool scop_do_interchange (scop_p);
 360 extern bool scop_do_strip_mine (scop_p);
 361 extern void pbb_number_of_iterations (poly_bb_p, graphite_dim_t, Value);
 362 extern void pbb_number_of_iterations_at_time (poly_bb_p, graphite_dim_t, Value);
 363 extern void pbb_remove_duplicate_pdrs (poly_bb_p);
 364
 365 /* Return the number of write data references in PBB.  */
 366
 367 static inline int
 368 number_of_write_pdrs (poly_bb_p pbb)
 369 {
 370   int res = 0;
 371   int i;
 372   poly_dr_p pdr;
 373
 374   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
 375     if (PDR_TYPE (pdr) == PDR_WRITE)
 376       res++;
 377
 378   return res;
 379 }
 380
 381 /* The index of the PBB.  */
 382
 383 static inline int
 384 pbb_index (poly_bb_p pbb)
 385 {
 386   return GBB_BB (PBB_BLACK_BOX (pbb))->index;
 387 }
 388
 389 /* The loop of the PBB.  */
 390
 391 static inline loop_p
 392 pbb_loop (poly_bb_p pbb)
 393 {
 394   return gbb_loop (PBB_BLACK_BOX (pbb));
 395 }
 396
 397 /* The scop that contains the PDR.  */
 398
 399 static inline scop_p
 400 pdr_scop (poly_dr_p pdr)
 401 {
 402   return PBB_SCOP (PDR_PBB (pdr));
 403 }
 404
 405 /* Set black box of PBB to BLACKBOX.  */
 406
 407 static inline void
 408 pbb_set_black_box (poly_bb_p pbb, void *black_box)
 409 {
 410   pbb->black_box = black_box;
 411 }
 412
 413 /* The number of loops around PBB: the dimension of the iteration
 414    domain.  */
 415
 416 static inline graphite_dim_t
 417 pbb_dim_iter_domain (const struct poly_bb *pbb)
 418 {
 419   scop_p scop = PBB_SCOP (pbb);
 420   ppl_dimension_type dim;
 421
 422   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb), &dim);
 423   return dim - scop_nb_params (scop);
 424 }
 425
 426 /* The number of params defined in PBB.  */
 427
 428 static inline graphite_dim_t
 429 pbb_nb_params (const struct poly_bb *pbb)
 430 {
 431   scop_p scop = PBB_SCOP (pbb);
 432
 433   return scop_nb_params (scop);
 434 }
 435
 436 /* The number of scattering dimensions in the SCATTERING polyhedron
 437    of a PBB for a given SCOP.  */
 438
 439 static inline graphite_dim_t
 440 pbb_nb_scattering_orig (const struct poly_bb *pbb)
 441 {
 442   return 2 * pbb_dim_iter_domain (pbb) + 1;
 443 }
 444
 445 /* The number of scattering dimensions in PBB.  */
 446
 447 static inline graphite_dim_t
 448 pbb_nb_scattering_transform (const struct poly_bb *pbb)
 449 {
 450   return PBB_NB_SCATTERING_TRANSFORM (pbb);
 451 }
 452
 453 /* The number of dynamic scattering dimensions in PBB.  */
 454
 455 static inline graphite_dim_t
 456 pbb_nb_dynamic_scattering_transform (const struct poly_bb *pbb)
 457 {
 458   /* This function requires the 2d + 1 scattering format to be
 459      invariant during all transformations.  */
 460   gcc_assert (PBB_NB_SCATTERING_TRANSFORM (pbb) % 2);
 461   return PBB_NB_SCATTERING_TRANSFORM (pbb) / 2;
 462 }
 463
 464 /* Returns the number of local variables used in the transformed
 465    scattering polyhedron of PBB.  */
 466
 467 static inline graphite_dim_t
 468 pbb_nb_local_vars (const struct poly_bb *pbb)
 469 {
 470   /* For now we do not have any local variables, as we do not do strip
 471      mining for example.  */
 472   return PBB_NB_LOCAL_VARIABLES (pbb);
 473 }
 474
 475 /* The dimension in the domain of PBB containing the iterator ITER.  */
 476
 477 static inline ppl_dimension_type
 478 pbb_iterator_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t iter)
 479 {
 480   return iter;
 481 }
 482
 483 /* The dimension in the domain of PBB containing the iterator ITER.  */
 484
 485 static inline ppl_dimension_type
 486 pbb_parameter_dim (poly_bb_p pbb, graphite_dim_t param)
 487 {
 488   return param
 489     + pbb_dim_iter_domain (pbb);
 490 }
 491
 492 /* The dimension in the original scattering polyhedron of PBB
 493    containing the scattering iterator SCATTER.  */
 494
 495 static inline ppl_dimension_type
 496 psco_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t scatter)
 497 {
 498   gcc_assert (scatter < pbb_nb_scattering_orig (pbb));
 499   return scatter;
 500 }
 501
 502 /* The dimension in the transformed scattering polyhedron of PBB
 503    containing the scattering iterator SCATTER.  */
 504
 505 static inline ppl_dimension_type
 506 psct_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t scatter)
 507 {
 508   gcc_assert (scatter <= pbb_nb_scattering_transform (pbb));
 509   return scatter;
 510 }
 511
 512 ppl_dimension_type psct_scattering_dim_for_loop_depth (poly_bb_p,
 513                                                        graphite_dim_t);
 514
 515 /* The dimension in the transformed scattering polyhedron of PBB of
 516    the local variable LV.  */
 517
 518 static inline ppl_dimension_type
 519 psct_local_var_dim (poly_bb_p pbb, graphite_dim_t lv)
 520 {
 521   gcc_assert (lv <= pbb_nb_local_vars (pbb));
 522   return lv + pbb_nb_scattering_transform (pbb);
 523 }
 524
 525 /* The dimension in the original scattering polyhedron of PBB
 526    containing the loop iterator ITER.  */
 527
 528 static inline ppl_dimension_type
 529 psco_iterator_dim (poly_bb_p pbb, graphite_dim_t iter)
 530 {
 531   gcc_assert (iter < pbb_dim_iter_domain (pbb));
 532   return iter + pbb_nb_scattering_orig (pbb);
 533 }
 534
 535 /* The dimension in the transformed scattering polyhedron of PBB
 536    containing the loop iterator ITER.  */
 537
 538 static inline ppl_dimension_type
 539 psct_iterator_dim (poly_bb_p pbb, graphite_dim_t iter)
 540 {
 541   gcc_assert (iter < pbb_dim_iter_domain (pbb));
 542   return iter
 543     + pbb_nb_scattering_transform (pbb)
 544     + pbb_nb_local_vars (pbb);
 545 }
 546
 547 /* The dimension in the original scattering polyhedron of PBB
 548    containing parameter PARAM.  */
 549
 550 static inline ppl_dimension_type
 551 psco_parameter_dim (poly_bb_p pbb, graphite_dim_t param)
 552 {
 553   gcc_assert (param < pbb_nb_params (pbb));
 554   return param
 555     + pbb_nb_scattering_orig (pbb)
 556     + pbb_dim_iter_domain (pbb);
 557 }
 558
 559 /* The dimension in the transformed scattering polyhedron of PBB
 560    containing parameter PARAM.  */
 561
 562 static inline ppl_dimension_type
 563 psct_parameter_dim (poly_bb_p pbb, graphite_dim_t param)
 564 {
 565   gcc_assert (param < pbb_nb_params (pbb));
 566   return param
 567     + pbb_nb_scattering_transform (pbb)
 568     + pbb_nb_local_vars (pbb)
 569     + pbb_dim_iter_domain (pbb);
 570 }
 571
 572 /* The scattering dimension of PBB corresponding to the dynamic level
 573    LEVEL.  */
 574
 575 static inline ppl_dimension_type
 576 psct_dynamic_dim (poly_bb_p pbb, graphite_dim_t level)
 577 {
 578   graphite_dim_t result;
 579   result = 1 + 2 * level;
 580
 581   gcc_assert (result < pbb_nb_scattering_transform (pbb));
 582   return result;
 583 }
 584
 585 /* Adds to the transformed scattering polyhedron of PBB a new local
 586    variable and returns its index.  */
 587
 588 static inline graphite_dim_t
 589 psct_add_local_variable (poly_bb_p pbb)
 590 {
 591   graphite_dim_t nlv = pbb_nb_local_vars (pbb);
 592   ppl_dimension_type lv_column = psct_local_var_dim (pbb, nlv);
 593   ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb), lv_column, 1);
 594   PBB_NB_LOCAL_VARIABLES (pbb) += 1;
 595   return nlv;
 596 }
 597
 598 /* Adds a dimension to the transformed scattering polyhedron of PBB at
 599    INDEX.  */
 600
 601 static inline void
 602 psct_add_scattering_dimension (poly_bb_p pbb, ppl_dimension_type index)
 603 {
 604   gcc_assert (index < pbb_nb_scattering_transform (pbb));
 605
 606   ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb), index, 1);
 607   PBB_NB_SCATTERING_TRANSFORM (pbb) += 1;
 608 }
 609
 610 typedef struct lst *lst_p;
 611 DEF_VEC_P(lst_p);
 612 DEF_VEC_ALLOC_P (lst_p, heap);
 613
 614 /* Loops and Statements Tree.  */
 615 struct lst {
 616
 617   /* LOOP_P is true when an LST node is a loop.  */
 618   bool loop_p;
 619
 620   /* A pointer to the loop that contains this node.  */
 621   lst_p loop_father;
 622
 623   /* Loop nodes contain a sequence SEQ of LST nodes, statements
 624      contain a pointer to their polyhedral representation PBB.  */
 625   union {
 626     poly_bb_p pbb;
 627     VEC (lst_p, heap) *seq;
 628   } node;
 629 };
 630
 631 #define LST_LOOP_P(LST) ((LST)->loop_p)
 632 #define LST_LOOP_FATHER(LST) ((LST)->loop_father)
 633 #define LST_PBB(LST) ((LST)->node.pbb)
 634 #define LST_SEQ(LST) ((LST)->node.seq)
 635
 636 void scop_to_lst (scop_p);
 637 void print_lst (FILE *, lst_p, int);
 638 void debug_lst (lst_p);
 639 void dot_lst (lst_p);
 640
 641 /* Creates a new LST loop with SEQ.  */
 642
 643 static inline lst_p
 644 new_lst_loop (VEC (lst_p, heap) *seq)
 645 {
 646   lst_p lst = XNEW (struct lst);
 647   int i;
 648   lst_p l;
 649
 650   LST_LOOP_P (lst) = true;
 651   LST_SEQ (lst) = seq;
 652   LST_LOOP_FATHER (lst) = NULL;
 653
 654   for (i = 0; VEC_iterate (lst_p, seq, i, l); i++)
 655     LST_LOOP_FATHER (l) = lst;
 656
 657   return lst;
 658 }
 659
 660 /* Creates a new LST statement with PBB.  */
 661
 662 static inline lst_p
 663 new_lst_stmt (poly_bb_p pbb)
 664 {
 665   lst_p lst = XNEW (struct lst);
 666
 667   LST_LOOP_P (lst) = false;
 668   LST_PBB (lst) = pbb;
 669   LST_LOOP_FATHER (lst) = NULL;
 670   return lst;
 671 }
 672
 673 /* Frees the memory used by LST.  */
 674
 675 static inline void
 676 free_lst (lst_p lst)
 677 {
 678   if (!lst)
 679     return;
 680
 681   if (LST_LOOP_P (lst))
 682     {
 683       int i;
 684       lst_p l;
 685
 686       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 687         free_lst (l);
 688
 689       VEC_free (lst_p, heap, LST_SEQ (lst));
 690     }
 691
 692   free (lst);
 693 }
 694
 695 /* Returns a copy of LST.  */
 696
 697 static inline lst_p
 698 copy_lst (lst_p lst)
 699 {
 700   if (!lst)
 701     return NULL;
 702
 703   if (LST_LOOP_P (lst))
 704     {
 705       int i;
 706       lst_p l;
 707       VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
 708
 709       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 710         VEC_safe_push (lst_p, heap, seq, copy_lst (l));
 711
 712       return new_lst_loop (seq);
 713     }
 714
 715   return new_lst_stmt (LST_PBB (lst));
 716 }
 717
 718 /* Adds a new loop under the loop LST.  */
 719
 720 static inline void
 721 lst_add_loop_under_loop (lst_p lst)
 722 {
 723   VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 1);
 724   lst_p l = new_lst_loop (LST_SEQ (lst));
 725
 726   gcc_assert (LST_LOOP_P (lst));
 727
 728   LST_LOOP_FATHER (l) = lst;
 729   VEC_quick_push (lst_p, seq, l);
 730   LST_SEQ (lst) = seq;
 731 }
 732
 733 /* Returns the loop depth of LST.  */
 734
 735 static inline int
 736 lst_depth (lst_p lst)
 737 {
 738   if (!lst)
 739     return -2;
 740
 741   /* The depth of the outermost "fake" loop is -1.  This outermost
 742      loop does not have a loop father and it is just a container, as
 743      in the loop representation of GCC.  */
 744   if (!LST_LOOP_FATHER (lst))
 745     return -1;
 746
 747   return lst_depth (LST_LOOP_FATHER (lst)) + 1;
 748 }
 749
 750 /* Returns the Dewey number for LST.  */
 751
 752 static inline int
 753 lst_dewey_number (lst_p lst)
 754 {
 755   int i;
 756   lst_p l;
 757
 758   if (!lst)
 759     return -1;
 760
 761   if (!LST_LOOP_FATHER (lst))
 762     return 0;
 763
 764   for (i = 0; VEC_iterate (lst_p, LST_SEQ (LST_LOOP_FATHER (lst)), i, l); i++)
 765     if (l == lst)
 766       return i;
 767
 768   return -1;
 769 }
 770
 771 /* Return the LST node corresponding to PBB.  */
 772
 773 static inline lst_p
 774 lst_find_pbb (lst_p lst, poly_bb_p pbb)
 775 {
 776   int i;
 777   lst_p l;
 778
 779   if (!lst)
 780     return NULL;
 781
 782   if (LST_LOOP_P (lst))
 783     for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 784       {
 785         lst_p res = lst_find_pbb (l, pbb);
 786         if (res)
 787           return res;
 788       }
 789   else if (pbb == LST_PBB (lst))
 790     return lst;
 791
 792   return NULL;
 793 }
 794
 795 /* Return the LST node corresponding to the loop around STMT at depth
 796    LOOP_DEPTH.  */
 797
 798 static inline lst_p
 799 find_lst_loop (lst_p stmt, int loop_depth)
 800 {
 801   lst_p loop = LST_LOOP_FATHER (stmt);
 802
 803   gcc_assert (loop_depth >= 0);
 804
 805   while (loop_depth < lst_depth (loop))
 806     loop = LST_LOOP_FATHER (loop);
 807
 808   return loop;
 809 }
 810
 811 /* Return the LST node corresponding to PBB.  */
 812
 813 static inline lst_p
 814 lst_find_first_pbb (lst_p lst)
 815 {
 816   int i;
 817   lst_p l;
 818
 819   if (!lst)
 820     return NULL;
 821
 822   if (LST_LOOP_P (lst))
 823     for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 824       {
 825         lst_p res = lst_find_first_pbb (l);
 826         if (res)
 827           return res;
 828       }
 829
 830   return lst;
 831 }
 832
 833 /* A SCOP is a Static Control Part of the program, simple enough to be
 834    represented in polyhedral form.  */
 835 struct scop
 836 {
 837   /* A SCOP is defined as a SESE region.  */
 838   void *region;
 839
 840   /* Number of parameters in SCoP.  */
 841   graphite_dim_t nb_params;
 842
 843   /* All the basic blocks in this scop that contain memory references
 844      and that will be represented as statements in the polyhedral
 845      representation.  */
 846   VEC (poly_bb_p, heap) *bbs;
 847
 848   /* Original, transformed and saved schedules.  */
 849   lst_p original_schedule, transformed_schedule, saved_schedule;
 850
 851   /* The context describes known restrictions concerning the parameters
 852      and relations in between the parameters.
 853
 854   void f (int8_t a, uint_16_t b) {
 855     c = 2 a + b;
 856     ...
 857   }
 858
 859   Here we can add these restrictions to the context:
 860
 861   -128 >= a >= 127
 862      0 >= b >= 65,535
 863      c = 2a + b  */
 864   ppl_Pointset_Powerset_C_Polyhedron_t context;
 865
 866   /* A hashtable of the data dependence relations for the original
 867      scattering.  */
 868   htab_t original_pddrs;
 869 };
 870
 871 #define SCOP_BBS(S) (S->bbs)
 872 #define SCOP_REGION(S) ((sese) S->region)
 873 #define SCOP_CONTEXT(S) (S->context)
 874 #define SCOP_ORIGINAL_PDDRS(S) (S->original_pddrs)
 875 #define SCOP_ORIGINAL_SCHEDULE(S) (S->original_schedule)
 876 #define SCOP_TRANSFORMED_SCHEDULE(S) (S->transformed_schedule)
 877 #define SCOP_SAVED_SCHEDULE(S) (S->saved_schedule)
 878
 879 extern scop_p new_scop (void *);
 880 extern void free_scop (scop_p);
 881 extern void free_scops (VEC (scop_p, heap) *);
 882 extern void print_generated_program (FILE *, scop_p);
 883 extern void debug_generated_program (scop_p);
 884 extern void print_scattering_function (FILE *, poly_bb_p);
 885 extern void print_scattering_functions (FILE *, scop_p);
 886 extern void debug_scattering_function (poly_bb_p);
 887 extern void debug_scattering_functions (scop_p);
 888 extern int scop_max_loop_depth (scop_p);
 889 extern int unify_scattering_dimensions (scop_p);
 890 extern bool apply_poly_transforms (scop_p);
 891 extern bool graphite_legal_transform (scop_p);
 892
 893 /* Set the region of SCOP to REGION.  */
 894
 895 static inline void
 896 scop_set_region (scop_p scop, void *region)
 897 {
 898   scop->region = region;
 899 }
 900
 901 /* Returns the number of parameters for SCOP.  */
 902
 903 static inline graphite_dim_t
 904 scop_nb_params (scop_p scop)
 905 {
 906   return scop->nb_params;
 907 }
 908
 909 /* Set the number of params of SCOP to NB_PARAMS.  */
 910
 911 static inline void
 912 scop_set_nb_params (scop_p scop, graphite_dim_t nb_params)
 913 {
 914   scop->nb_params = nb_params;
 915 }
 916
 917 /* Allocates a new empty poly_scattering structure.  */
 918
 919 static inline poly_scattering_p
 920 poly_scattering_new (void)
 921 {
 922   poly_scattering_p res = XNEW (struct poly_scattering);
 923
 924   res->scattering = NULL;
 925   res->nb_local_variables = 0;
 926   res->nb_scattering = 0;
 927   return res;
 928 }
 929
 930 /* Free a poly_scattering structure.  */
 931
 932 static inline void
 933 poly_scattering_free (poly_scattering_p s)
 934 {
 935   ppl_delete_Polyhedron (s->scattering);
 936   free (s);
 937 }
 938
 939 /* Copies S and return a new scattering.  */
 940
 941 static inline poly_scattering_p
 942 poly_scattering_copy (poly_scattering_p s)
 943 {
 944   poly_scattering_p res = poly_scattering_new ();
 945
 946   ppl_new_C_Polyhedron_from_C_Polyhedron (&(res->scattering), s->scattering);
 947   res->nb_local_variables = s->nb_local_variables;
 948   res->nb_scattering = s->nb_scattering;
 949   return res;
 950 }
 951
 952 /* Saves the transformed scattering of PBB.  */
 953
 954 static inline void
 955 store_scattering_pbb (poly_bb_p pbb)
 956 {
 957   gcc_assert (PBB_TRANSFORMED (pbb));
 958
 959   if (PBB_SAVED (pbb))
 960     poly_scattering_free (PBB_SAVED (pbb));
 961
 962   PBB_SAVED (pbb) = poly_scattering_copy (PBB_TRANSFORMED (pbb));
 963 }
 964
 965 /* Stores the SCOP_TRANSFORMED_SCHEDULE to SCOP_SAVED_SCHEDULE.  */
 966
 967 static inline void
 968 store_lst_schedule (scop_p scop)
 969 {
 970   if (SCOP_SAVED_SCHEDULE (scop))
 971     free_lst (SCOP_SAVED_SCHEDULE (scop));
 972
 973   SCOP_SAVED_SCHEDULE (scop) = copy_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
 974 }
 975
 976 /* Restores the SCOP_TRANSFORMED_SCHEDULE from SCOP_SAVED_SCHEDULE.  */
 977
 978 static inline void
 979 restore_lst_schedule (scop_p scop)
 980 {
 981   if (SCOP_TRANSFORMED_SCHEDULE (scop))
 982     free_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
 983
 984   SCOP_TRANSFORMED_SCHEDULE (scop) = copy_lst (SCOP_SAVED_SCHEDULE (scop));
 985 }
 986
 987 /* Saves the scattering for all the pbbs in the SCOP.  */
 988
 989 static inline void
 990 store_scattering (scop_p scop)
 991 {
 992   int i;
 993   poly_bb_p pbb;
 994
 995   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
 996     store_scattering_pbb (pbb);
 997
 998   store_lst_schedule (scop);
 999 }
1000
1001 /* Restores the scattering of PBB.  */
1002
1003 static inline void
1004 restore_scattering_pbb (poly_bb_p pbb)
1005 {
1006   gcc_assert (PBB_SAVED (pbb));
1007
1008   poly_scattering_free (PBB_TRANSFORMED (pbb));
1009   PBB_TRANSFORMED (pbb) = poly_scattering_copy (PBB_SAVED (pbb));
1010 }
1011
1012 /* Restores the scattering for all the pbbs in the SCOP.  */
1013
1014 static inline void
1015 restore_scattering (scop_p scop)
1016 {
1017   int i;
1018   poly_bb_p pbb;
1019
1020   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1021     restore_scattering_pbb (pbb);
1022
1023   restore_lst_schedule (scop);
1024 }
1025
1026 #endif