gcc/graphite-poly.h

   1 /* Graphite polyhedral representation.
   2    Copyright (C) 2009, 2010 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
 137      The difference between the graphite internal format for access data and
 138      the OpenSop format is in the order of columns.
 139      Instead of having:
 140
 141      | i   j   k   a  s0  s1   1
 142      | 0   0   0   1   0   0  -5     =  0
 143      |-1   0   0   0   1   0   0     =  0
 144      | 0  -1  -1   0   0   1   0     =  0
 145      | 0   0   0   0   1   0   0     >= 0  # The last four lines describe the
 146      | 0   0   0   0   0   1   0     >= 0  # array size.
 147      | 0   0   0   0  -1   0 1335    >= 0
 148      | 0   0   0   0   0  -1 123     >= 0
 149
 150      In OpenScop we have:
 151
 152      | a  s0  s1   i   j   k   1
 153      | 1   0   0   0   0   0  -5     =  0
 154      | 0   1   0  -1   0   0   0     =  0
 155      | 0   0   1   0  -1  -1   0     =  0
 156      | 0   1   0   0   0   0   0     >= 0  # The last four lines describe the
 157      | 0   0   1   0   0   0   0     >= 0  # array size.
 158      | 0  -1   0   0   0   0 1335    >= 0
 159      | 0   0  -1   0   0   0 123     >= 0
 160
 161      The OpenScop access function is printed as follows:
 162
 163      | 1  # The number of disjunct components in a union of access functions.
 164      | R C O I L P  # Described bellow.
 165      | a  s0  s1   i   j   k   1
 166      | 1   0   0   0   0   0  -5     =  0
 167      | 0   1   0  -1   0   0   0     =  0
 168      | 0   0   1   0  -1  -1   0     =  0
 169      | 0   1   0   0   0   0   0     >= 0  # The last four lines describe the
 170      | 0   0   1   0   0   0   0     >= 0  # array size.
 171      | 0  -1   0   0   0   0 1335    >= 0
 172      | 0   0  -1   0   0   0 123     >= 0
 173
 174      Where:
 175      - R: Number of rows.
 176      - C: Number of columns.
 177      - O: Number of output dimensions = alias set + number of subscripts.
 178      - I: Number of input dimensions (iterators).
 179      - L: Number of local (existentially quantified) dimensions.
 180      - P: Number of parameters.
 181
 182      In the example, the vector "R C O I L P" is "7 7 3 2 0 1".  */
 183   ppl_Pointset_Powerset_C_Polyhedron_t accesses;
 184
 185   /* Data reference's base object set number, we must assure 2 pdrs are in the
 186      same base object set before dependency checking.  */
 187   int dr_base_object_set;
 188
 189   /* The number of subscripts.  */
 190   graphite_dim_t nb_subscripts;
 191 };
 192
 193 #define PDR_ID(PDR) (PDR->id)
 194 #define PDR_NB_REFS(PDR) (PDR->nb_refs)
 195 #define PDR_CDR(PDR) (PDR->compiler_dr)
 196 #define PDR_PBB(PDR) (PDR->pbb)
 197 #define PDR_TYPE(PDR) (PDR->type)
 198 #define PDR_ACCESSES(PDR) (PDR->accesses)
 199 #define PDR_BASE_OBJECT_SET(PDR) (PDR->dr_base_object_set)
 200 #define PDR_NB_SUBSCRIPTS(PDR) (PDR->nb_subscripts)
 201
 202 void new_poly_dr (poly_bb_p, int, ppl_Pointset_Powerset_C_Polyhedron_t,
 203                   enum poly_dr_type, void *, graphite_dim_t);
 204 void free_poly_dr (poly_dr_p);
 205 void debug_pdr (poly_dr_p, int);
 206 void print_pdr (FILE *, poly_dr_p, int);
 207 static inline scop_p pdr_scop (poly_dr_p pdr);
 208
 209 /* The dimension of the PDR_ACCESSES polyhedron of PDR.  */
 210
 211 static inline ppl_dimension_type
 212 pdr_dim (poly_dr_p pdr)
 213 {
 214   ppl_dimension_type dim;
 215   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PDR_ACCESSES (pdr),
 216                                                       &dim);
 217   return dim;
 218 }
 219
 220 /* The dimension of the iteration domain of the scop of PDR.  */
 221
 222 static inline ppl_dimension_type
 223 pdr_dim_iter_domain (poly_dr_p pdr)
 224 {
 225   return pbb_dim_iter_domain (PDR_PBB (pdr));
 226 }
 227
 228 /* The number of parameters of the scop of PDR.  */
 229
 230 static inline ppl_dimension_type
 231 pdr_nb_params (poly_dr_p pdr)
 232 {
 233   return scop_nb_params (pdr_scop (pdr));
 234 }
 235
 236 /* The dimension of the alias set in PDR.  */
 237
 238 static inline ppl_dimension_type
 239 pdr_alias_set_dim (poly_dr_p pdr)
 240 {
 241   poly_bb_p pbb = PDR_PBB (pdr);
 242
 243   return pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
 244 }
 245
 246 /* The dimension in PDR containing subscript S.  */
 247
 248 static inline ppl_dimension_type
 249 pdr_subscript_dim (poly_dr_p pdr, graphite_dim_t s)
 250 {
 251   poly_bb_p pbb = PDR_PBB (pdr);
 252
 253   return pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb) + 1 + s;
 254 }
 255
 256 /* The dimension in PDR containing the loop iterator ITER.  */
 257
 258 static inline ppl_dimension_type
 259 pdr_iterator_dim (poly_dr_p pdr ATTRIBUTE_UNUSED, graphite_dim_t iter)
 260 {
 261   return iter;
 262 }
 263
 264 /* The dimension in PDR containing parameter PARAM.  */
 265
 266 static inline ppl_dimension_type
 267 pdr_parameter_dim (poly_dr_p pdr, graphite_dim_t param)
 268 {
 269   poly_bb_p pbb = PDR_PBB (pdr);
 270
 271   return pbb_dim_iter_domain (pbb) + param;
 272 }
 273
 274 /* Returns true when PDR is a "read".  */
 275
 276 static inline bool
 277 pdr_read_p (poly_dr_p pdr)
 278 {
 279   return PDR_TYPE (pdr) == PDR_READ;
 280 }
 281
 282 /* Returns true when PDR is a "write".  */
 283
 284 static inline bool
 285 pdr_write_p (poly_dr_p pdr)
 286 {
 287   return PDR_TYPE (pdr) == PDR_WRITE;
 288 }
 289
 290 /* Returns true when PDR is a "may write".  */
 291
 292 static inline bool
 293 pdr_may_write_p (poly_dr_p pdr)
 294 {
 295   return PDR_TYPE (pdr) == PDR_MAY_WRITE;
 296 }
 297
 298 /* Return true when PDR1 and PDR2 are similar data accesses: they have
 299    the same base array, and the same access functions.  */
 300
 301 static inline bool
 302 same_pdr_p (poly_dr_p pdr1, poly_dr_p pdr2)
 303 {
 304   return PDR_TYPE (pdr1) == PDR_TYPE (pdr2)
 305     && PDR_NB_SUBSCRIPTS (pdr1) == PDR_NB_SUBSCRIPTS (pdr2)
 306     && PDR_BASE_OBJECT_SET (pdr1) == PDR_BASE_OBJECT_SET (pdr2);
 307 }
 308
 309 typedef struct poly_scattering *poly_scattering_p;
 310
 311 struct poly_scattering
 312 {
 313   /* The scattering function containing the transformations: the
 314      layout of this polyhedron is: T|I|G with T the transform
 315      scattering, I the iteration domain, G the context parameters.  */
 316   ppl_Polyhedron_t scattering;
 317
 318   /* The number of local variables.  */
 319   int nb_local_variables;
 320
 321   /* The number of scattering dimensions.  */
 322   int nb_scattering;
 323 };
 324
 325 /* POLY_BB represents a blackbox in the polyhedral model.  */
 326
 327 struct poly_bb
 328 {
 329   /* Pointer to a basic block or a statement in the compiler.  */
 330   void *black_box;
 331
 332   /* Pointer to the SCOP containing this PBB.  */
 333   scop_p scop;
 334
 335   /* The iteration domain of this bb.  The layout of this polyhedron
 336      is I|G with I the iteration domain, G the context parameters.
 337
 338      Example:
 339
 340      for (i = a - 7*b + 8; i <= 3*a + 13*b + 20; i++)
 341        for (j = 2; j <= 2*i + 5; j++)
 342          for (k = 0; k <= 5; k++)
 343            S (i,j,k)
 344
 345      Loop iterators: i, j, k
 346      Parameters: a, b
 347
 348      | i >=  a -  7b +  8
 349      | i <= 3a + 13b + 20
 350      | j >= 2
 351      | j <= 2i + 5
 352      | k >= 0
 353      | k <= 5
 354
 355      The number of variables in the DOMAIN may change and is not
 356      related to the number of loops in the original code.  */
 357   ppl_Pointset_Powerset_C_Polyhedron_t domain;
 358
 359   /* The data references we access.  */
 360   VEC (poly_dr_p, heap) *drs;
 361
 362   /* The original scattering.  */
 363   poly_scattering_p original;
 364
 365   /* The transformed scattering.  */
 366   poly_scattering_p transformed;
 367
 368   /* A copy of the transformed scattering.  */
 369   poly_scattering_p saved;
 370
 371   /* True when the PDR duplicates have already been removed.  */
 372   bool pdr_duplicates_removed;
 373
 374   /* True when this PBB contains only a reduction statement.  */
 375   bool is_reduction;
 376 };
 377
 378 #define PBB_BLACK_BOX(PBB) ((gimple_bb_p) PBB->black_box)
 379 #define PBB_SCOP(PBB) (PBB->scop)
 380 #define PBB_DOMAIN(PBB) (PBB->domain)
 381 #define PBB_DRS(PBB) (PBB->drs)
 382 #define PBB_ORIGINAL(PBB) (PBB->original)
 383 #define PBB_ORIGINAL_SCATTERING(PBB) (PBB->original->scattering)
 384 #define PBB_TRANSFORMED(PBB) (PBB->transformed)
 385 #define PBB_TRANSFORMED_SCATTERING(PBB) (PBB->transformed->scattering)
 386 #define PBB_SAVED(PBB) (PBB->saved)
 387 #define PBB_NB_LOCAL_VARIABLES(PBB) (PBB->transformed->nb_local_variables)
 388 #define PBB_NB_SCATTERING_TRANSFORM(PBB) (PBB->transformed->nb_scattering)
 389 #define PBB_PDR_DUPLICATES_REMOVED(PBB) (PBB->pdr_duplicates_removed)
 390 #define PBB_IS_REDUCTION(PBB) (PBB->is_reduction)
 391
 392 extern void new_poly_bb (scop_p, void *, bool);
 393 extern void free_poly_bb (poly_bb_p);
 394 extern void debug_loop_vec (poly_bb_p);
 395 extern void schedule_to_scattering (poly_bb_p, int);
 396 extern void print_pbb_domain (FILE *, poly_bb_p, int);
 397 extern void print_pbb (FILE *, poly_bb_p, int);
 398 extern void print_scop_context (FILE *, scop_p, int);
 399 extern void print_scop (FILE *, scop_p, int);
 400 extern void print_cloog (FILE *, scop_p, int);
 401 extern void debug_pbb_domain (poly_bb_p, int);
 402 extern void debug_pbb (poly_bb_p, int);
 403 extern void print_pdrs (FILE *, poly_bb_p, int);
 404 extern void debug_pdrs (poly_bb_p, int);
 405 extern void debug_scop_context (scop_p, int);
 406 extern void debug_scop (scop_p, int);
 407 extern void debug_cloog (scop_p, int);
 408 extern void print_scop_params (FILE *, scop_p, int);
 409 extern void debug_scop_params (scop_p, int);
 410 extern void print_iteration_domain (FILE *, poly_bb_p, int);
 411 extern void print_iteration_domains (FILE *, scop_p, int);
 412 extern void debug_iteration_domain (poly_bb_p, int);
 413 extern void debug_iteration_domains (scop_p, int);
 414 extern bool scop_do_interchange (scop_p);
 415 extern bool scop_do_strip_mine (scop_p);
 416 extern bool scop_do_block (scop_p);
 417 extern void pbb_number_of_iterations (poly_bb_p, graphite_dim_t, mpz_t);
 418 extern void pbb_number_of_iterations_at_time (poly_bb_p, graphite_dim_t, mpz_t);
 419 extern void pbb_remove_duplicate_pdrs (poly_bb_p);
 420
 421 /* Return the number of write data references in PBB.  */
 422
 423 static inline int
 424 number_of_write_pdrs (poly_bb_p pbb)
 425 {
 426   int res = 0;
 427   int i;
 428   poly_dr_p pdr;
 429
 430   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
 431     if (PDR_TYPE (pdr) == PDR_WRITE)
 432       res++;
 433
 434   return res;
 435 }
 436
 437 /* The basic block of the PBB.  */
 438
 439 static inline basic_block
 440 pbb_bb (poly_bb_p pbb)
 441 {
 442   return GBB_BB (PBB_BLACK_BOX (pbb));
 443 }
 444
 445 /* The index of the PBB.  */
 446
 447 static inline int
 448 pbb_index (poly_bb_p pbb)
 449 {
 450   return pbb_bb (pbb)->index;
 451 }
 452
 453 /* The loop of the PBB.  */
 454
 455 static inline loop_p
 456 pbb_loop (poly_bb_p pbb)
 457 {
 458   return gbb_loop (PBB_BLACK_BOX (pbb));
 459 }
 460
 461 /* The scop that contains the PDR.  */
 462
 463 static inline scop_p
 464 pdr_scop (poly_dr_p pdr)
 465 {
 466   return PBB_SCOP (PDR_PBB (pdr));
 467 }
 468
 469 /* Set black box of PBB to BLACKBOX.  */
 470
 471 static inline void
 472 pbb_set_black_box (poly_bb_p pbb, void *black_box)
 473 {
 474   pbb->black_box = black_box;
 475 }
 476
 477 /* The number of loops around PBB: the dimension of the iteration
 478    domain.  */
 479
 480 static inline graphite_dim_t
 481 pbb_dim_iter_domain (const struct poly_bb *pbb)
 482 {
 483   scop_p scop = PBB_SCOP (pbb);
 484   ppl_dimension_type dim;
 485
 486   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb), &dim);
 487   return dim - scop_nb_params (scop);
 488 }
 489
 490 /* The number of params defined in PBB.  */
 491
 492 static inline graphite_dim_t
 493 pbb_nb_params (const struct poly_bb *pbb)
 494 {
 495   scop_p scop = PBB_SCOP (pbb);
 496
 497   return scop_nb_params (scop);
 498 }
 499
 500 /* The number of scattering dimensions in the SCATTERING polyhedron
 501    of a PBB for a given SCOP.  */
 502
 503 static inline graphite_dim_t
 504 pbb_nb_scattering_orig (const struct poly_bb *pbb)
 505 {
 506   return 2 * pbb_dim_iter_domain (pbb) + 1;
 507 }
 508
 509 /* The number of scattering dimensions in PBB.  */
 510
 511 static inline graphite_dim_t
 512 pbb_nb_scattering_transform (const struct poly_bb *pbb)
 513 {
 514   return PBB_NB_SCATTERING_TRANSFORM (pbb);
 515 }
 516
 517 /* The number of dynamic scattering dimensions in PBB.  */
 518
 519 static inline graphite_dim_t
 520 pbb_nb_dynamic_scattering_transform (const struct poly_bb *pbb)
 521 {
 522   /* This function requires the 2d + 1 scattering format to be
 523      invariant during all transformations.  */
 524   gcc_assert (PBB_NB_SCATTERING_TRANSFORM (pbb) % 2);
 525   return PBB_NB_SCATTERING_TRANSFORM (pbb) / 2;
 526 }
 527
 528 /* Returns the number of local variables used in the transformed
 529    scattering polyhedron of PBB.  */
 530
 531 static inline graphite_dim_t
 532 pbb_nb_local_vars (const struct poly_bb *pbb)
 533 {
 534   /* For now we do not have any local variables, as we do not do strip
 535      mining for example.  */
 536   return PBB_NB_LOCAL_VARIABLES (pbb);
 537 }
 538
 539 /* The dimension in the domain of PBB containing the iterator ITER.  */
 540
 541 static inline ppl_dimension_type
 542 pbb_iterator_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t iter)
 543 {
 544   return iter;
 545 }
 546
 547 /* The dimension in the domain of PBB containing the iterator ITER.  */
 548
 549 static inline ppl_dimension_type
 550 pbb_parameter_dim (poly_bb_p pbb, graphite_dim_t param)
 551 {
 552   return param
 553     + pbb_dim_iter_domain (pbb);
 554 }
 555
 556 /* The dimension in the original scattering polyhedron of PBB
 557    containing the scattering iterator SCATTER.  */
 558
 559 static inline ppl_dimension_type
 560 psco_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t scatter)
 561 {
 562   gcc_assert (scatter < pbb_nb_scattering_orig (pbb));
 563   return scatter;
 564 }
 565
 566 /* The dimension in the transformed scattering polyhedron of PBB
 567    containing the scattering iterator SCATTER.  */
 568
 569 static inline ppl_dimension_type
 570 psct_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t scatter)
 571 {
 572   gcc_assert (scatter <= pbb_nb_scattering_transform (pbb));
 573   return scatter;
 574 }
 575
 576 ppl_dimension_type psct_scattering_dim_for_loop_depth (poly_bb_p,
 577                                                        graphite_dim_t);
 578
 579 /* The dimension in the transformed scattering polyhedron of PBB of
 580    the local variable LV.  */
 581
 582 static inline ppl_dimension_type
 583 psct_local_var_dim (poly_bb_p pbb, graphite_dim_t lv)
 584 {
 585   gcc_assert (lv <= pbb_nb_local_vars (pbb));
 586   return lv + pbb_nb_scattering_transform (pbb);
 587 }
 588
 589 /* The dimension in the original scattering polyhedron of PBB
 590    containing the loop iterator ITER.  */
 591
 592 static inline ppl_dimension_type
 593 psco_iterator_dim (poly_bb_p pbb, graphite_dim_t iter)
 594 {
 595   gcc_assert (iter < pbb_dim_iter_domain (pbb));
 596   return iter + pbb_nb_scattering_orig (pbb);
 597 }
 598
 599 /* The dimension in the transformed scattering polyhedron of PBB
 600    containing the loop iterator ITER.  */
 601
 602 static inline ppl_dimension_type
 603 psct_iterator_dim (poly_bb_p pbb, graphite_dim_t iter)
 604 {
 605   gcc_assert (iter < pbb_dim_iter_domain (pbb));
 606   return iter
 607     + pbb_nb_scattering_transform (pbb)
 608     + pbb_nb_local_vars (pbb);
 609 }
 610
 611 /* The dimension in the original scattering polyhedron of PBB
 612    containing parameter PARAM.  */
 613
 614 static inline ppl_dimension_type
 615 psco_parameter_dim (poly_bb_p pbb, graphite_dim_t param)
 616 {
 617   gcc_assert (param < pbb_nb_params (pbb));
 618   return param
 619     + pbb_nb_scattering_orig (pbb)
 620     + pbb_dim_iter_domain (pbb);
 621 }
 622
 623 /* The dimension in the transformed scattering polyhedron of PBB
 624    containing parameter PARAM.  */
 625
 626 static inline ppl_dimension_type
 627 psct_parameter_dim (poly_bb_p pbb, graphite_dim_t param)
 628 {
 629   gcc_assert (param < pbb_nb_params (pbb));
 630   return param
 631     + pbb_nb_scattering_transform (pbb)
 632     + pbb_nb_local_vars (pbb)
 633     + pbb_dim_iter_domain (pbb);
 634 }
 635
 636 /* The scattering dimension of PBB corresponding to the dynamic level
 637    LEVEL.  */
 638
 639 static inline ppl_dimension_type
 640 psct_dynamic_dim (poly_bb_p pbb, graphite_dim_t level)
 641 {
 642   graphite_dim_t result = 1 + 2 * level;
 643
 644   gcc_assert (result < pbb_nb_scattering_transform (pbb));
 645   return result;
 646 }
 647
 648 /* The scattering dimension of PBB corresponding to the static
 649    sequence of the loop level LEVEL.  */
 650
 651 static inline ppl_dimension_type
 652 psct_static_dim (poly_bb_p pbb, graphite_dim_t level)
 653 {
 654   graphite_dim_t result = 2 * level;
 655
 656   gcc_assert (result < pbb_nb_scattering_transform (pbb));
 657   return result;
 658 }
 659
 660 /* Adds to the transformed scattering polyhedron of PBB a new local
 661    variable and returns its index.  */
 662
 663 static inline graphite_dim_t
 664 psct_add_local_variable (poly_bb_p pbb)
 665 {
 666   graphite_dim_t nlv = pbb_nb_local_vars (pbb);
 667   ppl_dimension_type lv_column = psct_local_var_dim (pbb, nlv);
 668   ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb), lv_column, 1);
 669   PBB_NB_LOCAL_VARIABLES (pbb) += 1;
 670   return nlv;
 671 }
 672
 673 /* Adds a dimension to the transformed scattering polyhedron of PBB at
 674    INDEX.  */
 675
 676 static inline void
 677 psct_add_scattering_dimension (poly_bb_p pbb, ppl_dimension_type index)
 678 {
 679   gcc_assert (index < pbb_nb_scattering_transform (pbb));
 680
 681   ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb), index, 1);
 682   PBB_NB_SCATTERING_TRANSFORM (pbb) += 1;
 683 }
 684
 685 typedef struct lst *lst_p;
 686 DEF_VEC_P(lst_p);
 687 DEF_VEC_ALLOC_P (lst_p, heap);
 688
 689 /* Loops and Statements Tree.  */
 690 struct lst {
 691
 692   /* LOOP_P is true when an LST node is a loop.  */
 693   bool loop_p;
 694
 695   /* A pointer to the loop that contains this node.  */
 696   lst_p loop_father;
 697
 698   /* The sum of all the memory strides for an LST loop.  */
 699   mpz_t memory_strides;
 700
 701   /* Loop nodes contain a sequence SEQ of LST nodes, statements
 702      contain a pointer to their polyhedral representation PBB.  */
 703   union {
 704     poly_bb_p pbb;
 705     VEC (lst_p, heap) *seq;
 706   } node;
 707 };
 708
 709 #define LST_LOOP_P(LST) ((LST)->loop_p)
 710 #define LST_LOOP_FATHER(LST) ((LST)->loop_father)
 711 #define LST_PBB(LST) ((LST)->node.pbb)
 712 #define LST_SEQ(LST) ((LST)->node.seq)
 713 #define LST_LOOP_MEMORY_STRIDES(LST) ((LST)->memory_strides)
 714
 715 void scop_to_lst (scop_p);
 716 void print_lst (FILE *, lst_p, int);
 717 void debug_lst (lst_p);
 718 void dot_lst (lst_p);
 719
 720 /* Creates a new LST loop with SEQ.  */
 721
 722 static inline lst_p
 723 new_lst_loop (VEC (lst_p, heap) *seq)
 724 {
 725   lst_p lst = XNEW (struct lst);
 726   int i;
 727   lst_p l;
 728
 729   LST_LOOP_P (lst) = true;
 730   LST_SEQ (lst) = seq;
 731   LST_LOOP_FATHER (lst) = NULL;
 732   mpz_init (LST_LOOP_MEMORY_STRIDES (lst));
 733   mpz_set_si (LST_LOOP_MEMORY_STRIDES (lst), -1);
 734
 735   for (i = 0; VEC_iterate (lst_p, seq, i, l); i++)
 736     LST_LOOP_FATHER (l) = lst;
 737
 738   return lst;
 739 }
 740
 741 /* Creates a new LST statement with PBB.  */
 742
 743 static inline lst_p
 744 new_lst_stmt (poly_bb_p pbb)
 745 {
 746   lst_p lst = XNEW (struct lst);
 747
 748   LST_LOOP_P (lst) = false;
 749   LST_PBB (lst) = pbb;
 750   LST_LOOP_FATHER (lst) = NULL;
 751   return lst;
 752 }
 753
 754 /* Frees the memory used by LST.  */
 755
 756 static inline void
 757 free_lst (lst_p lst)
 758 {
 759   if (!lst)
 760     return;
 761
 762   if (LST_LOOP_P (lst))
 763     {
 764       int i;
 765       lst_p l;
 766
 767       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 768         free_lst (l);
 769
 770       mpz_clear (LST_LOOP_MEMORY_STRIDES (lst));
 771       VEC_free (lst_p, heap, LST_SEQ (lst));
 772     }
 773
 774   free (lst);
 775 }
 776
 777 /* Returns a copy of LST.  */
 778
 779 static inline lst_p
 780 copy_lst (lst_p lst)
 781 {
 782   if (!lst)
 783     return NULL;
 784
 785   if (LST_LOOP_P (lst))
 786     {
 787       int i;
 788       lst_p l;
 789       VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
 790
 791       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 792         VEC_safe_push (lst_p, heap, seq, copy_lst (l));
 793
 794       return new_lst_loop (seq);
 795     }
 796
 797   return new_lst_stmt (LST_PBB (lst));
 798 }
 799
 800 /* Adds a new loop under the loop LST.  */
 801
 802 static inline void
 803 lst_add_loop_under_loop (lst_p lst)
 804 {
 805   VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 1);
 806   lst_p l = new_lst_loop (LST_SEQ (lst));
 807
 808   gcc_assert (LST_LOOP_P (lst));
 809
 810   LST_LOOP_FATHER (l) = lst;
 811   VEC_quick_push (lst_p, seq, l);
 812   LST_SEQ (lst) = seq;
 813 }
 814
 815 /* Returns the loop depth of LST.  */
 816
 817 static inline int
 818 lst_depth (lst_p lst)
 819 {
 820   if (!lst)
 821     return -2;
 822
 823   /* The depth of the outermost "fake" loop is -1.  This outermost
 824      loop does not have a loop father and it is just a container, as
 825      in the loop representation of GCC.  */
 826   if (!LST_LOOP_FATHER (lst))
 827     return -1;
 828
 829   return lst_depth (LST_LOOP_FATHER (lst)) + 1;
 830 }
 831
 832 /* Returns the Dewey number for LST.  */
 833
 834 static inline int
 835 lst_dewey_number (lst_p lst)
 836 {
 837   int i;
 838   lst_p l;
 839
 840   if (!lst)
 841     return -1;
 842
 843   if (!LST_LOOP_FATHER (lst))
 844     return 0;
 845
 846   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (LST_LOOP_FATHER (lst)), i, l)
 847     if (l == lst)
 848       return i;
 849
 850   return -1;
 851 }
 852
 853 /* Returns the Dewey number of LST at depth DEPTH.  */
 854
 855 static inline int
 856 lst_dewey_number_at_depth (lst_p lst, int depth)
 857 {
 858   gcc_assert (lst && depth >= 0 && lst_depth (lst) <= depth);
 859
 860   if (lst_depth (lst) == depth)
 861     return lst_dewey_number (lst);
 862
 863   return lst_dewey_number_at_depth (LST_LOOP_FATHER (lst), depth);
 864 }
 865
 866 /* Returns the predecessor of LST in the sequence of its loop father.
 867    Returns NULL if LST is the first statement in the sequence.  */
 868
 869 static inline lst_p
 870 lst_pred (lst_p lst)
 871 {
 872   int dewey;
 873   lst_p father;
 874
 875   if (!lst || !LST_LOOP_FATHER (lst))
 876     return NULL;
 877
 878   dewey = lst_dewey_number (lst);
 879   if (dewey == 0)
 880     return NULL;
 881
 882   father = LST_LOOP_FATHER (lst);
 883   return VEC_index (lst_p, LST_SEQ (father), dewey - 1);
 884 }
 885
 886 /* Returns the successor of LST in the sequence of its loop father.
 887    Returns NULL if there is none.  */
 888
 889 static inline lst_p
 890 lst_succ (lst_p lst)
 891 {
 892   int dewey;
 893   lst_p father;
 894
 895   if (!lst || !LST_LOOP_FATHER (lst))
 896     return NULL;
 897
 898   dewey = lst_dewey_number (lst);
 899   father = LST_LOOP_FATHER (lst);
 900
 901   if (VEC_length (lst_p, LST_SEQ (father)) == (unsigned) dewey + 1)
 902     return NULL;
 903
 904   return VEC_index (lst_p, LST_SEQ (father), dewey + 1);
 905 }
 906
 907
 908 /* Return the LST node corresponding to PBB.  */
 909
 910 static inline lst_p
 911 lst_find_pbb (lst_p lst, poly_bb_p pbb)
 912 {
 913   int i;
 914   lst_p l;
 915
 916   if (!lst)
 917     return NULL;
 918
 919   if (!LST_LOOP_P (lst))
 920     return (pbb == LST_PBB (lst)) ? lst : NULL;
 921
 922   for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 923     {
 924       lst_p res = lst_find_pbb (l, pbb);
 925       if (res)
 926         return res;
 927     }
 928
 929   return NULL;
 930 }
 931
 932 /* Return the LST node corresponding to the loop around STMT at depth
 933    LOOP_DEPTH.  */
 934
 935 static inline lst_p
 936 find_lst_loop (lst_p stmt, int loop_depth)
 937 {
 938   lst_p loop = LST_LOOP_FATHER (stmt);
 939
 940   gcc_assert (loop_depth >= 0);
 941
 942   while (loop_depth < lst_depth (loop))
 943     loop = LST_LOOP_FATHER (loop);
 944
 945   return loop;
 946 }
 947
 948 /* Return the first lst representing a PBB statement in LST.  */
 949
 950 static inline lst_p
 951 lst_find_first_pbb (lst_p lst)
 952 {
 953   int i;
 954   lst_p l;
 955
 956   if (!lst)
 957     return NULL;
 958
 959   if (!LST_LOOP_P (lst))
 960     return lst;
 961
 962   for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 963     {
 964       lst_p res = lst_find_first_pbb (l);
 965       if (res)
 966         return res;
 967     }
 968
 969   return NULL;
 970 }
 971
 972 /* Returns true when LST is a loop that does not contains
 973    statements.  */
 974
 975 static inline bool
 976 lst_empty_p (lst_p lst)
 977 {
 978   return !lst_find_first_pbb (lst);
 979 }
 980
 981 /* Return the last lst representing a PBB statement in LST.  */
 982
 983 static inline lst_p
 984 lst_find_last_pbb (lst_p lst)
 985 {
 986   int i;
 987   lst_p l, res = NULL;
 988
 989   if (!lst)
 990     return NULL;
 991
 992   if (!LST_LOOP_P (lst))
 993     return lst;
 994
 995   for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 996     {
 997       lst_p last = lst_find_last_pbb (l);
 998
 999       if (last)
1000         res = last;
1001     }
1002
1003   gcc_assert (res);
1004   return res;
1005 }
1006
1007 /* Returns true if LOOP contains LST, in other words, if LST is nested
1008    in LOOP.  */
1009
1010 static inline bool
1011 lst_contains_p (lst_p loop, lst_p lst)
1012 {
1013   if (!loop || !lst || !LST_LOOP_P (loop))
1014     return false;
1015
1016   if (loop == lst)
1017     return true;
1018
1019   return lst_contains_p (loop, LST_LOOP_FATHER (lst));
1020 }
1021
1022 /* Returns true if LOOP contains PBB, in other words, if PBB is nested
1023    in LOOP.  */
1024
1025 static inline bool
1026 lst_contains_pbb (lst_p loop, poly_bb_p pbb)
1027 {
1028   return lst_find_pbb (loop, pbb) ? true : false;
1029 }
1030
1031 /* Creates a loop nest of depth NB_LOOPS containing LST.  */
1032
1033 static inline lst_p
1034 lst_create_nest (int nb_loops, lst_p lst)
1035 {
1036   lst_p res, loop;
1037   VEC (lst_p, heap) *seq;
1038
1039   if (nb_loops == 0)
1040     return lst;
1041
1042   seq = VEC_alloc (lst_p, heap, 1);
1043   loop = lst_create_nest (nb_loops - 1, lst);
1044   VEC_quick_push (lst_p, seq, loop);
1045   res = new_lst_loop (seq);
1046   LST_LOOP_FATHER (loop) = res;
1047
1048   return res;
1049 }
1050
1051 /* Removes LST from the sequence of statements of its loop father.  */
1052
1053 static inline void
1054 lst_remove_from_sequence (lst_p lst)
1055 {
1056   lst_p father = LST_LOOP_FATHER (lst);
1057   int dewey = lst_dewey_number (lst);
1058
1059   gcc_assert (lst && father && dewey >= 0);
1060
1061   VEC_ordered_remove (lst_p, LST_SEQ (father), dewey);
1062   LST_LOOP_FATHER (lst) = NULL;
1063 }
1064
1065 /* Sets NITER to the upper bound approximation of the number of
1066    iterations of loop LST.  */
1067
1068 static inline void
1069 lst_niter_for_loop (lst_p lst, mpz_t niter)
1070 {
1071   int depth = lst_depth (lst);
1072   poly_bb_p pbb = LST_PBB (lst_find_first_pbb (lst));
1073
1074   gcc_assert (LST_LOOP_P (lst));
1075   pbb_number_of_iterations_at_time (pbb, psct_dynamic_dim (pbb, depth), niter);
1076 }
1077
1078 /* Updates the scattering of PBB to be at the DEWEY number in the loop
1079    at depth LEVEL.  */
1080
1081 static inline void
1082 pbb_update_scattering (poly_bb_p pbb, graphite_dim_t level, int dewey)
1083 {
1084   ppl_Polyhedron_t ph = PBB_TRANSFORMED_SCATTERING (pbb);
1085   ppl_dimension_type sched = psct_static_dim (pbb, level);
1086   ppl_dimension_type ds[1];
1087   ppl_Constraint_t new_cstr;
1088   ppl_Linear_Expression_t expr;
1089   ppl_dimension_type dim;
1090
1091   ppl_Polyhedron_space_dimension (ph, &dim);
1092   ds[0] = sched;
1093   ppl_Polyhedron_remove_space_dimensions (ph, ds, 1);
1094   ppl_insert_dimensions (ph, sched, 1);
1095
1096   ppl_new_Linear_Expression_with_dimension (&expr, dim);
1097   ppl_set_coef (expr, sched, -1);
1098   ppl_set_inhomogeneous (expr, dewey);
1099   ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
1100   ppl_delete_Linear_Expression (expr);
1101   ppl_Polyhedron_add_constraint (ph, new_cstr);
1102   ppl_delete_Constraint (new_cstr);
1103 }
1104
1105 /* Updates the scattering of all the PBBs under LST to be at the DEWEY
1106    number in the loop at depth LEVEL.  */
1107
1108 static inline void
1109 lst_update_scattering_under (lst_p lst, int level, int dewey)
1110 {
1111   int i;
1112   lst_p l;
1113
1114   gcc_assert (lst && level >= 0 && dewey >= 0);
1115
1116   if (LST_LOOP_P (lst))
1117     for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
1118       lst_update_scattering_under (l, level, dewey);
1119   else
1120     pbb_update_scattering (LST_PBB (lst), level, dewey);
1121 }
1122
1123 /* Updates the all the scattering levels of all the PBBs under
1124    LST.  */
1125
1126 static inline void
1127 lst_update_scattering (lst_p lst)
1128 {
1129   int i;
1130   lst_p l;
1131
1132   if (!lst)
1133     return;
1134
1135   if (LST_LOOP_FATHER (lst))
1136     {
1137       lst_p father = LST_LOOP_FATHER (lst);
1138       int dewey = lst_dewey_number (lst);
1139       int level = lst_depth (lst);
1140
1141       gcc_assert (lst && father && dewey >= 0 && level >= 0);
1142
1143       for (i = dewey; VEC_iterate (lst_p, LST_SEQ (father), i, l); i++)
1144         lst_update_scattering_under (l, level, i);
1145     }
1146
1147   if (LST_LOOP_P (lst))
1148     for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
1149       lst_update_scattering (l);
1150 }
1151
1152 /* Inserts LST1 before LST2 if BEFORE is true; inserts LST1 after LST2
1153    if BEFORE is false.  */
1154
1155 static inline void
1156 lst_insert_in_sequence (lst_p lst1, lst_p lst2, bool before)
1157 {
1158   lst_p father;
1159   int dewey;
1160
1161   /* Do not insert empty loops.  */
1162   if (!lst1 || lst_empty_p (lst1))
1163     return;
1164
1165   father = LST_LOOP_FATHER (lst2);
1166   dewey = lst_dewey_number (lst2);
1167
1168   gcc_assert (lst2 && father && dewey >= 0);
1169
1170   VEC_safe_insert (lst_p, heap, LST_SEQ (father), before ? dewey : dewey + 1,
1171                    lst1);
1172   LST_LOOP_FATHER (lst1) = father;
1173 }
1174
1175 /* Replaces LST1 with LST2.  */
1176
1177 static inline void
1178 lst_replace (lst_p lst1, lst_p lst2)
1179 {
1180   lst_p father;
1181   int dewey;
1182
1183   if (!lst2 || lst_empty_p (lst2))
1184     return;
1185
1186   father = LST_LOOP_FATHER (lst1);
1187   dewey = lst_dewey_number (lst1);
1188   LST_LOOP_FATHER (lst2) = father;
1189   VEC_replace (lst_p, LST_SEQ (father), dewey, lst2);
1190 }
1191
1192 /* Returns a copy of ROOT where LST has been replaced by a copy of the
1193    LSTs A B C in this sequence.  */
1194
1195 static inline lst_p
1196 lst_substitute_3 (lst_p root, lst_p lst, lst_p a, lst_p b, lst_p c)
1197 {
1198   int i;
1199   lst_p l;
1200   VEC (lst_p, heap) *seq;
1201
1202   if (!root)
1203     return NULL;
1204
1205   gcc_assert (lst && root != lst);
1206
1207   if (!LST_LOOP_P (root))
1208     return new_lst_stmt (LST_PBB (root));
1209
1210   seq = VEC_alloc (lst_p, heap, 5);
1211
1212   for (i = 0; VEC_iterate (lst_p, LST_SEQ (root), i, l); i++)
1213     if (l != lst)
1214       VEC_safe_push (lst_p, heap, seq, lst_substitute_3 (l, lst, a, b, c));
1215     else
1216       {
1217         if (!lst_empty_p (a))
1218           VEC_safe_push (lst_p, heap, seq, copy_lst (a));
1219         if (!lst_empty_p (b))
1220           VEC_safe_push (lst_p, heap, seq, copy_lst (b));
1221         if (!lst_empty_p (c))
1222           VEC_safe_push (lst_p, heap, seq, copy_lst (c));
1223       }
1224
1225   return new_lst_loop (seq);
1226 }
1227
1228 /* Moves LST before LOOP if BEFORE is true, and after the LOOP if
1229    BEFORE is false.  */
1230
1231 static inline void
1232 lst_distribute_lst (lst_p loop, lst_p lst, bool before)
1233 {
1234   int loop_depth = lst_depth (loop);
1235   int depth = lst_depth (lst);
1236   int nb_loops = depth - loop_depth;
1237
1238   gcc_assert (lst && loop && LST_LOOP_P (loop) && nb_loops > 0);
1239
1240   lst_remove_from_sequence (lst);
1241   lst_insert_in_sequence (lst_create_nest (nb_loops, lst), loop, before);
1242 }
1243
1244 /* Removes from LOOP all the statements before/after and including PBB
1245    if BEFORE is true/false.  Returns the negation of BEFORE when the
1246    statement PBB has been found.  */
1247
1248 static inline bool
1249 lst_remove_all_before_including_pbb (lst_p loop, poly_bb_p pbb, bool before)
1250 {
1251   int i;
1252   lst_p l;
1253
1254   if (!loop || !LST_LOOP_P (loop))
1255     return before;
1256
1257   for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l);)
1258     if (LST_LOOP_P (l))
1259       {
1260         before = lst_remove_all_before_including_pbb (l, pbb, before);
1261
1262         if (VEC_length (lst_p, LST_SEQ (l)) == 0)
1263           {
1264             VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1265             free_lst (l);
1266           }
1267         else
1268           i++;
1269       }
1270     else
1271       {
1272         if (before)
1273           {
1274             if (LST_PBB (l) == pbb)
1275               before = false;
1276
1277             VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1278             free_lst (l);
1279           }
1280         else if (LST_PBB (l) == pbb)
1281           {
1282             before = true;
1283             VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1284             free_lst (l);
1285           }
1286         else
1287           i++;
1288       }
1289
1290   return before;
1291 }
1292
1293 /* Removes from LOOP all the statements before/after and excluding PBB
1294    if BEFORE is true/false; Returns the negation of BEFORE when the
1295    statement PBB has been found.  */
1296
1297 static inline bool
1298 lst_remove_all_before_excluding_pbb (lst_p loop, poly_bb_p pbb, bool before)
1299 {
1300   int i;
1301   lst_p l;
1302
1303   if (!loop || !LST_LOOP_P (loop))
1304     return before;
1305
1306   for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l);)
1307     if (LST_LOOP_P (l))
1308       {
1309         before = lst_remove_all_before_excluding_pbb (l, pbb, before);
1310
1311         if (VEC_length (lst_p, LST_SEQ (l)) == 0)
1312           {
1313             VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1314             free_lst (l);
1315             continue;
1316           }
1317
1318         i++;
1319       }
1320     else
1321       {
1322         if (before && LST_PBB (l) != pbb)
1323           {
1324             VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1325             free_lst (l);
1326             continue;
1327           }
1328
1329         i++;
1330
1331         if (LST_PBB (l) == pbb)
1332           before = before ? false : true;
1333       }
1334
1335   return before;
1336 }
1337
1338 /* A SCOP is a Static Control Part of the program, simple enough to be
1339    represented in polyhedral form.  */
1340 struct scop
1341 {
1342   /* A SCOP is defined as a SESE region.  */
1343   void *region;
1344
1345   /* Number of parameters in SCoP.  */
1346   graphite_dim_t nb_params;
1347
1348   /* All the basic blocks in this scop that contain memory references
1349      and that will be represented as statements in the polyhedral
1350      representation.  */
1351   VEC (poly_bb_p, heap) *bbs;
1352
1353   /* Original, transformed and saved schedules.  */
1354   lst_p original_schedule, transformed_schedule, saved_schedule;
1355
1356   /* The context describes known restrictions concerning the parameters
1357      and relations in between the parameters.
1358
1359   void f (int8_t a, uint_16_t b) {
1360     c = 2 a + b;
1361     ...
1362   }
1363
1364   Here we can add these restrictions to the context:
1365
1366   -128 >= a >= 127
1367      0 >= b >= 65,535
1368      c = 2a + b  */
1369   ppl_Pointset_Powerset_C_Polyhedron_t context;
1370
1371   /* A hashtable of the data dependence relations for the original
1372      scattering.  */
1373   htab_t original_pddrs;
1374
1375   /* True when the scop has been converted to its polyhedral
1376      representation.  */
1377   bool poly_scop_p;
1378 };
1379
1380 #define SCOP_BBS(S) (S->bbs)
1381 #define SCOP_REGION(S) ((sese) S->region)
1382 #define SCOP_CONTEXT(S) (S->context)
1383 #define SCOP_ORIGINAL_PDDRS(S) (S->original_pddrs)
1384 #define SCOP_ORIGINAL_SCHEDULE(S) (S->original_schedule)
1385 #define SCOP_TRANSFORMED_SCHEDULE(S) (S->transformed_schedule)
1386 #define SCOP_SAVED_SCHEDULE(S) (S->saved_schedule)
1387 #define POLY_SCOP_P(S) (S->poly_scop_p)
1388
1389 extern scop_p new_scop (void *);
1390 extern void free_scop (scop_p);
1391 extern void free_scops (VEC (scop_p, heap) *);
1392 extern void print_generated_program (FILE *, scop_p);
1393 extern void debug_generated_program (scop_p);
1394 extern void print_scattering_function (FILE *, poly_bb_p, int);
1395 extern void print_scattering_functions (FILE *, scop_p, int);
1396 extern void debug_scattering_function (poly_bb_p, int);
1397 extern void debug_scattering_functions (scop_p, int);
1398 extern int scop_max_loop_depth (scop_p);
1399 extern int unify_scattering_dimensions (scop_p);
1400 extern bool apply_poly_transforms (scop_p);
1401 extern bool graphite_legal_transform (scop_p);
1402
1403 /* Set the region of SCOP to REGION.  */
1404
1405 static inline void
1406 scop_set_region (scop_p scop, void *region)
1407 {
1408   scop->region = region;
1409 }
1410
1411 /* Returns the number of parameters for SCOP.  */
1412
1413 static inline graphite_dim_t
1414 scop_nb_params (scop_p scop)
1415 {
1416   return scop->nb_params;
1417 }
1418
1419 /* Set the number of params of SCOP to NB_PARAMS.  */
1420
1421 static inline void
1422 scop_set_nb_params (scop_p scop, graphite_dim_t nb_params)
1423 {
1424   scop->nb_params = nb_params;
1425 }
1426
1427 /* Allocates a new empty poly_scattering structure.  */
1428
1429 static inline poly_scattering_p
1430 poly_scattering_new (void)
1431 {
1432   poly_scattering_p res = XNEW (struct poly_scattering);
1433
1434   res->scattering = NULL;
1435   res->nb_local_variables = 0;
1436   res->nb_scattering = 0;
1437   return res;
1438 }
1439
1440 /* Free a poly_scattering structure.  */
1441
1442 static inline void
1443 poly_scattering_free (poly_scattering_p s)
1444 {
1445   ppl_delete_Polyhedron (s->scattering);
1446   free (s);
1447 }
1448
1449 /* Copies S and return a new scattering.  */
1450
1451 static inline poly_scattering_p
1452 poly_scattering_copy (poly_scattering_p s)
1453 {
1454   poly_scattering_p res = poly_scattering_new ();
1455
1456   ppl_new_C_Polyhedron_from_C_Polyhedron (&(res->scattering), s->scattering);
1457   res->nb_local_variables = s->nb_local_variables;
1458   res->nb_scattering = s->nb_scattering;
1459   return res;
1460 }
1461
1462 /* Saves the transformed scattering of PBB.  */
1463
1464 static inline void
1465 store_scattering_pbb (poly_bb_p pbb)
1466 {
1467   gcc_assert (PBB_TRANSFORMED (pbb));
1468
1469   if (PBB_SAVED (pbb))
1470     poly_scattering_free (PBB_SAVED (pbb));
1471
1472   PBB_SAVED (pbb) = poly_scattering_copy (PBB_TRANSFORMED (pbb));
1473 }
1474
1475 /* Stores the SCOP_TRANSFORMED_SCHEDULE to SCOP_SAVED_SCHEDULE.  */
1476
1477 static inline void
1478 store_lst_schedule (scop_p scop)
1479 {
1480   if (SCOP_SAVED_SCHEDULE (scop))
1481     free_lst (SCOP_SAVED_SCHEDULE (scop));
1482
1483   SCOP_SAVED_SCHEDULE (scop) = copy_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
1484 }
1485
1486 /* Restores the SCOP_TRANSFORMED_SCHEDULE from SCOP_SAVED_SCHEDULE.  */
1487
1488 static inline void
1489 restore_lst_schedule (scop_p scop)
1490 {
1491   if (SCOP_TRANSFORMED_SCHEDULE (scop))
1492     free_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
1493
1494   SCOP_TRANSFORMED_SCHEDULE (scop) = copy_lst (SCOP_SAVED_SCHEDULE (scop));
1495 }
1496
1497 /* Saves the scattering for all the pbbs in the SCOP.  */
1498
1499 static inline void
1500 store_scattering (scop_p scop)
1501 {
1502   int i;
1503   poly_bb_p pbb;
1504
1505   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1506     store_scattering_pbb (pbb);
1507
1508   store_lst_schedule (scop);
1509 }
1510
1511 /* Restores the scattering of PBB.  */
1512
1513 static inline void
1514 restore_scattering_pbb (poly_bb_p pbb)
1515 {
1516   gcc_assert (PBB_SAVED (pbb));
1517
1518   poly_scattering_free (PBB_TRANSFORMED (pbb));
1519   PBB_TRANSFORMED (pbb) = poly_scattering_copy (PBB_SAVED (pbb));
1520 }
1521
1522 /* Restores the scattering for all the pbbs in the SCOP.  */
1523
1524 static inline void
1525 restore_scattering (scop_p scop)
1526 {
1527   int i;
1528   poly_bb_p pbb;
1529
1530   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1531     restore_scattering_pbb (pbb);
1532
1533   restore_lst_schedule (scop);
1534 }
1535
1536 /* For a given PBB, add to RES the scop context, the iteration domain,
1537    the original scattering when ORIGINAL_P is true, otherwise add the
1538    transformed scattering.  */
1539
1540 static inline void
1541 combine_context_id_scat (ppl_Pointset_Powerset_C_Polyhedron_t *res,
1542                          poly_bb_p pbb, bool original_p)
1543 {
1544   ppl_Pointset_Powerset_C_Polyhedron_t context;
1545   ppl_Pointset_Powerset_C_Polyhedron_t id;
1546
1547   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1548     (res, original_p ?
1549      PBB_ORIGINAL_SCATTERING (pbb) : PBB_TRANSFORMED_SCATTERING (pbb));
1550
1551   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1552     (&context, SCOP_CONTEXT (PBB_SCOP (pbb)));
1553
1554   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1555     (&id, PBB_DOMAIN (pbb));
1556
1557   /* Extend the context and the iteration domain to the dimension of
1558      the scattering: T|I|G.  */
1559   {
1560     ppl_dimension_type gdim, tdim, idim;
1561
1562     ppl_Pointset_Powerset_C_Polyhedron_space_dimension (*res, &tdim);
1563     ppl_Pointset_Powerset_C_Polyhedron_space_dimension (context, &gdim);
1564     ppl_Pointset_Powerset_C_Polyhedron_space_dimension (id, &idim);
1565
1566     if (tdim > gdim)
1567       ppl_insert_dimensions_pointset (context, 0, tdim - gdim);
1568
1569     if (tdim > idim)
1570       ppl_insert_dimensions_pointset (id, 0, tdim - idim);
1571   }
1572
1573   /* Add the context and the iteration domain to the result.  */
1574   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (*res, context);
1575   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (*res, id);
1576
1577   ppl_delete_Pointset_Powerset_C_Polyhedron (context);
1578   ppl_delete_Pointset_Powerset_C_Polyhedron (id);
1579 }
1580
1581 #endif