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_at_time (poly_bb_p, graphite_dim_t, mpz_t);
 418 extern void pbb_remove_duplicate_pdrs (poly_bb_p);
 419
 420 /* Return the number of write data references in PBB.  */
 421
 422 static inline int
 423 number_of_write_pdrs (poly_bb_p pbb)
 424 {
 425   int res = 0;
 426   int i;
 427   poly_dr_p pdr;
 428
 429   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
 430     if (PDR_TYPE (pdr) == PDR_WRITE)
 431       res++;
 432
 433   return res;
 434 }
 435
 436 /* The basic block of the PBB.  */
 437
 438 static inline basic_block
 439 pbb_bb (poly_bb_p pbb)
 440 {
 441   return GBB_BB (PBB_BLACK_BOX (pbb));
 442 }
 443
 444 /* The index of the PBB.  */
 445
 446 static inline int
 447 pbb_index (poly_bb_p pbb)
 448 {
 449   return pbb_bb (pbb)->index;
 450 }
 451
 452 /* The loop of the PBB.  */
 453
 454 static inline loop_p
 455 pbb_loop (poly_bb_p pbb)
 456 {
 457   return gbb_loop (PBB_BLACK_BOX (pbb));
 458 }
 459
 460 /* The scop that contains the PDR.  */
 461
 462 static inline scop_p
 463 pdr_scop (poly_dr_p pdr)
 464 {
 465   return PBB_SCOP (PDR_PBB (pdr));
 466 }
 467
 468 /* Set black box of PBB to BLACKBOX.  */
 469
 470 static inline void
 471 pbb_set_black_box (poly_bb_p pbb, void *black_box)
 472 {
 473   pbb->black_box = black_box;
 474 }
 475
 476 /* The number of loops around PBB: the dimension of the iteration
 477    domain.  */
 478
 479 static inline graphite_dim_t
 480 pbb_dim_iter_domain (const struct poly_bb *pbb)
 481 {
 482   scop_p scop = PBB_SCOP (pbb);
 483   ppl_dimension_type dim;
 484
 485   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb), &dim);
 486   return dim - scop_nb_params (scop);
 487 }
 488
 489 /* The number of params defined in PBB.  */
 490
 491 static inline graphite_dim_t
 492 pbb_nb_params (const struct poly_bb *pbb)
 493 {
 494   scop_p scop = PBB_SCOP (pbb);
 495
 496   return scop_nb_params (scop);
 497 }
 498
 499 /* The number of scattering dimensions in the SCATTERING polyhedron
 500    of a PBB for a given SCOP.  */
 501
 502 static inline graphite_dim_t
 503 pbb_nb_scattering_orig (const struct poly_bb *pbb)
 504 {
 505   return 2 * pbb_dim_iter_domain (pbb) + 1;
 506 }
 507
 508 /* The number of scattering dimensions in PBB.  */
 509
 510 static inline graphite_dim_t
 511 pbb_nb_scattering_transform (const struct poly_bb *pbb)
 512 {
 513   return PBB_NB_SCATTERING_TRANSFORM (pbb);
 514 }
 515
 516 /* The number of dynamic scattering dimensions in PBB.  */
 517
 518 static inline graphite_dim_t
 519 pbb_nb_dynamic_scattering_transform (const struct poly_bb *pbb)
 520 {
 521   /* This function requires the 2d + 1 scattering format to be
 522      invariant during all transformations.  */
 523   gcc_assert (PBB_NB_SCATTERING_TRANSFORM (pbb) % 2);
 524   return PBB_NB_SCATTERING_TRANSFORM (pbb) / 2;
 525 }
 526
 527 /* Returns the number of local variables used in the transformed
 528    scattering polyhedron of PBB.  */
 529
 530 static inline graphite_dim_t
 531 pbb_nb_local_vars (const struct poly_bb *pbb)
 532 {
 533   /* For now we do not have any local variables, as we do not do strip
 534      mining for example.  */
 535   return PBB_NB_LOCAL_VARIABLES (pbb);
 536 }
 537
 538 /* The dimension in the domain of PBB containing the iterator ITER.  */
 539
 540 static inline ppl_dimension_type
 541 pbb_iterator_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t iter)
 542 {
 543   return iter;
 544 }
 545
 546 /* The dimension in the domain of PBB containing the iterator ITER.  */
 547
 548 static inline ppl_dimension_type
 549 pbb_parameter_dim (poly_bb_p pbb, graphite_dim_t param)
 550 {
 551   return param
 552     + pbb_dim_iter_domain (pbb);
 553 }
 554
 555 /* The dimension in the original scattering polyhedron of PBB
 556    containing the scattering iterator SCATTER.  */
 557
 558 static inline ppl_dimension_type
 559 psco_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t scatter)
 560 {
 561   gcc_assert (scatter < pbb_nb_scattering_orig (pbb));
 562   return scatter;
 563 }
 564
 565 /* The dimension in the transformed scattering polyhedron of PBB
 566    containing the scattering iterator SCATTER.  */
 567
 568 static inline ppl_dimension_type
 569 psct_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t scatter)
 570 {
 571   gcc_assert (scatter <= pbb_nb_scattering_transform (pbb));
 572   return scatter;
 573 }
 574
 575 ppl_dimension_type psct_scattering_dim_for_loop_depth (poly_bb_p,
 576                                                        graphite_dim_t);
 577
 578 /* The dimension in the transformed scattering polyhedron of PBB of
 579    the local variable LV.  */
 580
 581 static inline ppl_dimension_type
 582 psct_local_var_dim (poly_bb_p pbb, graphite_dim_t lv)
 583 {
 584   gcc_assert (lv <= pbb_nb_local_vars (pbb));
 585   return lv + pbb_nb_scattering_transform (pbb);
 586 }
 587
 588 /* The dimension in the original scattering polyhedron of PBB
 589    containing the loop iterator ITER.  */
 590
 591 static inline ppl_dimension_type
 592 psco_iterator_dim (poly_bb_p pbb, graphite_dim_t iter)
 593 {
 594   gcc_assert (iter < pbb_dim_iter_domain (pbb));
 595   return iter + pbb_nb_scattering_orig (pbb);
 596 }
 597
 598 /* The dimension in the transformed scattering polyhedron of PBB
 599    containing the loop iterator ITER.  */
 600
 601 static inline ppl_dimension_type
 602 psct_iterator_dim (poly_bb_p pbb, graphite_dim_t iter)
 603 {
 604   gcc_assert (iter < pbb_dim_iter_domain (pbb));
 605   return iter
 606     + pbb_nb_scattering_transform (pbb)
 607     + pbb_nb_local_vars (pbb);
 608 }
 609
 610 /* The dimension in the original scattering polyhedron of PBB
 611    containing parameter PARAM.  */
 612
 613 static inline ppl_dimension_type
 614 psco_parameter_dim (poly_bb_p pbb, graphite_dim_t param)
 615 {
 616   gcc_assert (param < pbb_nb_params (pbb));
 617   return param
 618     + pbb_nb_scattering_orig (pbb)
 619     + pbb_dim_iter_domain (pbb);
 620 }
 621
 622 /* The dimension in the transformed scattering polyhedron of PBB
 623    containing parameter PARAM.  */
 624
 625 static inline ppl_dimension_type
 626 psct_parameter_dim (poly_bb_p pbb, graphite_dim_t param)
 627 {
 628   gcc_assert (param < pbb_nb_params (pbb));
 629   return param
 630     + pbb_nb_scattering_transform (pbb)
 631     + pbb_nb_local_vars (pbb)
 632     + pbb_dim_iter_domain (pbb);
 633 }
 634
 635 /* The scattering dimension of PBB corresponding to the dynamic level
 636    LEVEL.  */
 637
 638 static inline ppl_dimension_type
 639 psct_dynamic_dim (poly_bb_p pbb, graphite_dim_t level)
 640 {
 641   graphite_dim_t result = 1 + 2 * level;
 642
 643   gcc_assert (result < pbb_nb_scattering_transform (pbb));
 644   return result;
 645 }
 646
 647 /* The scattering dimension of PBB corresponding to the static
 648    sequence of the loop level LEVEL.  */
 649
 650 static inline ppl_dimension_type
 651 psct_static_dim (poly_bb_p pbb, graphite_dim_t level)
 652 {
 653   graphite_dim_t result = 2 * level;
 654
 655   gcc_assert (result < pbb_nb_scattering_transform (pbb));
 656   return result;
 657 }
 658
 659 /* Adds to the transformed scattering polyhedron of PBB a new local
 660    variable and returns its index.  */
 661
 662 static inline graphite_dim_t
 663 psct_add_local_variable (poly_bb_p pbb)
 664 {
 665   graphite_dim_t nlv = pbb_nb_local_vars (pbb);
 666   ppl_dimension_type lv_column = psct_local_var_dim (pbb, nlv);
 667   ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb), lv_column, 1);
 668   PBB_NB_LOCAL_VARIABLES (pbb) += 1;
 669   return nlv;
 670 }
 671
 672 /* Adds a dimension to the transformed scattering polyhedron of PBB at
 673    INDEX.  */
 674
 675 static inline void
 676 psct_add_scattering_dimension (poly_bb_p pbb, ppl_dimension_type index)
 677 {
 678   gcc_assert (index < pbb_nb_scattering_transform (pbb));
 679
 680   ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb), index, 1);
 681   PBB_NB_SCATTERING_TRANSFORM (pbb) += 1;
 682 }
 683
 684 typedef struct lst *lst_p;
 685 DEF_VEC_P(lst_p);
 686 DEF_VEC_ALLOC_P (lst_p, heap);
 687
 688 /* Loops and Statements Tree.  */
 689 struct lst {
 690
 691   /* LOOP_P is true when an LST node is a loop.  */
 692   bool loop_p;
 693
 694   /* A pointer to the loop that contains this node.  */
 695   lst_p loop_father;
 696
 697   /* The sum of all the memory strides for an LST loop.  */
 698   mpz_t memory_strides;
 699
 700   /* Loop nodes contain a sequence SEQ of LST nodes, statements
 701      contain a pointer to their polyhedral representation PBB.  */
 702   union {
 703     poly_bb_p pbb;
 704     VEC (lst_p, heap) *seq;
 705   } node;
 706 };
 707
 708 #define LST_LOOP_P(LST) ((LST)->loop_p)
 709 #define LST_LOOP_FATHER(LST) ((LST)->loop_father)
 710 #define LST_PBB(LST) ((LST)->node.pbb)
 711 #define LST_SEQ(LST) ((LST)->node.seq)
 712 #define LST_LOOP_MEMORY_STRIDES(LST) ((LST)->memory_strides)
 713
 714 void scop_to_lst (scop_p);
 715 void print_lst (FILE *, lst_p, int);
 716 void debug_lst (lst_p);
 717 void dot_lst (lst_p);
 718
 719 /* Creates a new LST loop with SEQ.  */
 720
 721 static inline lst_p
 722 new_lst_loop (VEC (lst_p, heap) *seq)
 723 {
 724   lst_p lst = XNEW (struct lst);
 725   int i;
 726   lst_p l;
 727
 728   LST_LOOP_P (lst) = true;
 729   LST_SEQ (lst) = seq;
 730   LST_LOOP_FATHER (lst) = NULL;
 731   mpz_init (LST_LOOP_MEMORY_STRIDES (lst));
 732   mpz_set_si (LST_LOOP_MEMORY_STRIDES (lst), -1);
 733
 734   for (i = 0; VEC_iterate (lst_p, seq, i, l); i++)
 735     LST_LOOP_FATHER (l) = lst;
 736
 737   return lst;
 738 }
 739
 740 /* Creates a new LST statement with PBB.  */
 741
 742 static inline lst_p
 743 new_lst_stmt (poly_bb_p pbb)
 744 {
 745   lst_p lst = XNEW (struct lst);
 746
 747   LST_LOOP_P (lst) = false;
 748   LST_PBB (lst) = pbb;
 749   LST_LOOP_FATHER (lst) = NULL;
 750   return lst;
 751 }
 752
 753 /* Frees the memory used by LST.  */
 754
 755 static inline void
 756 free_lst (lst_p lst)
 757 {
 758   if (!lst)
 759     return;
 760
 761   if (LST_LOOP_P (lst))
 762     {
 763       int i;
 764       lst_p l;
 765
 766       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 767         free_lst (l);
 768
 769       mpz_clear (LST_LOOP_MEMORY_STRIDES (lst));
 770       VEC_free (lst_p, heap, LST_SEQ (lst));
 771     }
 772
 773   free (lst);
 774 }
 775
 776 /* Returns a copy of LST.  */
 777
 778 static inline lst_p
 779 copy_lst (lst_p lst)
 780 {
 781   if (!lst)
 782     return NULL;
 783
 784   if (LST_LOOP_P (lst))
 785     {
 786       int i;
 787       lst_p l;
 788       VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
 789
 790       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 791         VEC_safe_push (lst_p, heap, seq, copy_lst (l));
 792
 793       return new_lst_loop (seq);
 794     }
 795
 796   return new_lst_stmt (LST_PBB (lst));
 797 }
 798
 799 /* Adds a new loop under the loop LST.  */
 800
 801 static inline void
 802 lst_add_loop_under_loop (lst_p lst)
 803 {
 804   VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 1);
 805   lst_p l = new_lst_loop (LST_SEQ (lst));
 806
 807   gcc_assert (LST_LOOP_P (lst));
 808
 809   LST_LOOP_FATHER (l) = lst;
 810   VEC_quick_push (lst_p, seq, l);
 811   LST_SEQ (lst) = seq;
 812 }
 813
 814 /* Returns the loop depth of LST.  */
 815
 816 static inline int
 817 lst_depth (lst_p lst)
 818 {
 819   if (!lst)
 820     return -2;
 821
 822   /* The depth of the outermost "fake" loop is -1.  This outermost
 823      loop does not have a loop father and it is just a container, as
 824      in the loop representation of GCC.  */
 825   if (!LST_LOOP_FATHER (lst))
 826     return -1;
 827
 828   return lst_depth (LST_LOOP_FATHER (lst)) + 1;
 829 }
 830
 831 /* Returns the Dewey number for LST.  */
 832
 833 static inline int
 834 lst_dewey_number (lst_p lst)
 835 {
 836   int i;
 837   lst_p l;
 838
 839   if (!lst)
 840     return -1;
 841
 842   if (!LST_LOOP_FATHER (lst))
 843     return 0;
 844
 845   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (LST_LOOP_FATHER (lst)), i, l)
 846     if (l == lst)
 847       return i;
 848
 849   return -1;
 850 }
 851
 852 /* Returns the Dewey number of LST at depth DEPTH.  */
 853
 854 static inline int
 855 lst_dewey_number_at_depth (lst_p lst, int depth)
 856 {
 857   gcc_assert (lst && depth >= 0 && lst_depth (lst) <= depth);
 858
 859   if (lst_depth (lst) == depth)
 860     return lst_dewey_number (lst);
 861
 862   return lst_dewey_number_at_depth (LST_LOOP_FATHER (lst), depth);
 863 }
 864
 865 /* Returns the predecessor of LST in the sequence of its loop father.
 866    Returns NULL if LST is the first statement in the sequence.  */
 867
 868 static inline lst_p
 869 lst_pred (lst_p lst)
 870 {
 871   int dewey;
 872   lst_p father;
 873
 874   if (!lst || !LST_LOOP_FATHER (lst))
 875     return NULL;
 876
 877   dewey = lst_dewey_number (lst);
 878   if (dewey == 0)
 879     return NULL;
 880
 881   father = LST_LOOP_FATHER (lst);
 882   return VEC_index (lst_p, LST_SEQ (father), dewey - 1);
 883 }
 884
 885 /* Returns the successor of LST in the sequence of its loop father.
 886    Returns NULL if there is none.  */
 887
 888 static inline lst_p
 889 lst_succ (lst_p lst)
 890 {
 891   int dewey;
 892   lst_p father;
 893
 894   if (!lst || !LST_LOOP_FATHER (lst))
 895     return NULL;
 896
 897   dewey = lst_dewey_number (lst);
 898   father = LST_LOOP_FATHER (lst);
 899
 900   if (VEC_length (lst_p, LST_SEQ (father)) == (unsigned) dewey + 1)
 901     return NULL;
 902
 903   return VEC_index (lst_p, LST_SEQ (father), dewey + 1);
 904 }
 905
 906
 907 /* Return the LST node corresponding to PBB.  */
 908
 909 static inline lst_p
 910 lst_find_pbb (lst_p lst, poly_bb_p pbb)
 911 {
 912   int i;
 913   lst_p l;
 914
 915   if (!lst)
 916     return NULL;
 917
 918   if (!LST_LOOP_P (lst))
 919     return (pbb == LST_PBB (lst)) ? lst : NULL;
 920
 921   for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 922     {
 923       lst_p res = lst_find_pbb (l, pbb);
 924       if (res)
 925         return res;
 926     }
 927
 928   return NULL;
 929 }
 930
 931 /* Return the LST node corresponding to the loop around STMT at depth
 932    LOOP_DEPTH.  */
 933
 934 static inline lst_p
 935 find_lst_loop (lst_p stmt, int loop_depth)
 936 {
 937   lst_p loop = LST_LOOP_FATHER (stmt);
 938
 939   gcc_assert (loop_depth >= 0);
 940
 941   while (loop_depth < lst_depth (loop))
 942     loop = LST_LOOP_FATHER (loop);
 943
 944   return loop;
 945 }
 946
 947 /* Return the first lst representing a PBB statement in LST.  */
 948
 949 static inline lst_p
 950 lst_find_first_pbb (lst_p lst)
 951 {
 952   int i;
 953   lst_p l;
 954
 955   if (!lst)
 956     return NULL;
 957
 958   if (!LST_LOOP_P (lst))
 959     return lst;
 960
 961   for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 962     {
 963       lst_p res = lst_find_first_pbb (l);
 964       if (res)
 965         return res;
 966     }
 967
 968   return NULL;
 969 }
 970
 971 /* Returns true when LST is a loop that does not contains
 972    statements.  */
 973
 974 static inline bool
 975 lst_empty_p (lst_p lst)
 976 {
 977   return !lst_find_first_pbb (lst);
 978 }
 979
 980 /* Return the last lst representing a PBB statement in LST.  */
 981
 982 static inline lst_p
 983 lst_find_last_pbb (lst_p lst)
 984 {
 985   int i;
 986   lst_p l, res = NULL;
 987
 988   if (!lst)
 989     return NULL;
 990
 991   if (!LST_LOOP_P (lst))
 992     return lst;
 993
 994   for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 995     {
 996       lst_p last = lst_find_last_pbb (l);
 997
 998       if (last)
 999         res = last;
1000     }
1001
1002   gcc_assert (res);
1003   return res;
1004 }
1005
1006 /* Returns true if LOOP contains LST, in other words, if LST is nested
1007    in LOOP.  */
1008
1009 static inline bool
1010 lst_contains_p (lst_p loop, lst_p lst)
1011 {
1012   if (!loop || !lst || !LST_LOOP_P (loop))
1013     return false;
1014
1015   if (loop == lst)
1016     return true;
1017
1018   return lst_contains_p (loop, LST_LOOP_FATHER (lst));
1019 }
1020
1021 /* Returns true if LOOP contains PBB, in other words, if PBB is nested
1022    in LOOP.  */
1023
1024 static inline bool
1025 lst_contains_pbb (lst_p loop, poly_bb_p pbb)
1026 {
1027   return lst_find_pbb (loop, pbb) ? true : false;
1028 }
1029
1030 /* Creates a loop nest of depth NB_LOOPS containing LST.  */
1031
1032 static inline lst_p
1033 lst_create_nest (int nb_loops, lst_p lst)
1034 {
1035   lst_p res, loop;
1036   VEC (lst_p, heap) *seq;
1037
1038   if (nb_loops == 0)
1039     return lst;
1040
1041   seq = VEC_alloc (lst_p, heap, 1);
1042   loop = lst_create_nest (nb_loops - 1, lst);
1043   VEC_quick_push (lst_p, seq, loop);
1044   res = new_lst_loop (seq);
1045   LST_LOOP_FATHER (loop) = res;
1046
1047   return res;
1048 }
1049
1050 /* Removes LST from the sequence of statements of its loop father.  */
1051
1052 static inline void
1053 lst_remove_from_sequence (lst_p lst)
1054 {
1055   lst_p father = LST_LOOP_FATHER (lst);
1056   int dewey = lst_dewey_number (lst);
1057
1058   gcc_assert (lst && father && dewey >= 0);
1059
1060   VEC_ordered_remove (lst_p, LST_SEQ (father), dewey);
1061   LST_LOOP_FATHER (lst) = NULL;
1062 }
1063
1064 /* Sets NITER to the upper bound approximation of the number of
1065    iterations of loop LST.  */
1066
1067 static inline void
1068 lst_niter_for_loop (lst_p lst, mpz_t niter)
1069 {
1070   int depth = lst_depth (lst);
1071   poly_bb_p pbb = LST_PBB (lst_find_first_pbb (lst));
1072
1073   gcc_assert (LST_LOOP_P (lst));
1074   pbb_number_of_iterations_at_time (pbb, psct_dynamic_dim (pbb, depth), niter);
1075 }
1076
1077 /* Updates the scattering of PBB to be at the DEWEY number in the loop
1078    at depth LEVEL.  */
1079
1080 static inline void
1081 pbb_update_scattering (poly_bb_p pbb, graphite_dim_t level, int dewey)
1082 {
1083   ppl_Polyhedron_t ph = PBB_TRANSFORMED_SCATTERING (pbb);
1084   ppl_dimension_type sched = psct_static_dim (pbb, level);
1085   ppl_dimension_type ds[1];
1086   ppl_Constraint_t new_cstr;
1087   ppl_Linear_Expression_t expr;
1088   ppl_dimension_type dim;
1089
1090   ppl_Polyhedron_space_dimension (ph, &dim);
1091   ds[0] = sched;
1092   ppl_Polyhedron_remove_space_dimensions (ph, ds, 1);
1093   ppl_insert_dimensions (ph, sched, 1);
1094
1095   ppl_new_Linear_Expression_with_dimension (&expr, dim);
1096   ppl_set_coef (expr, sched, -1);
1097   ppl_set_inhomogeneous (expr, dewey);
1098   ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
1099   ppl_delete_Linear_Expression (expr);
1100   ppl_Polyhedron_add_constraint (ph, new_cstr);
1101   ppl_delete_Constraint (new_cstr);
1102 }
1103
1104 /* Updates the scattering of all the PBBs under LST to be at the DEWEY
1105    number in the loop at depth LEVEL.  */
1106
1107 static inline void
1108 lst_update_scattering_under (lst_p lst, int level, int dewey)
1109 {
1110   int i;
1111   lst_p l;
1112
1113   gcc_assert (lst && level >= 0 && dewey >= 0);
1114
1115   if (LST_LOOP_P (lst))
1116     for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
1117       lst_update_scattering_under (l, level, dewey);
1118   else
1119     pbb_update_scattering (LST_PBB (lst), level, dewey);
1120 }
1121
1122 /* Updates the all the scattering levels of all the PBBs under
1123    LST.  */
1124
1125 static inline void
1126 lst_update_scattering (lst_p lst)
1127 {
1128   int i;
1129   lst_p l;
1130
1131   if (!lst)
1132     return;
1133
1134   if (LST_LOOP_FATHER (lst))
1135     {
1136       lst_p father = LST_LOOP_FATHER (lst);
1137       int dewey = lst_dewey_number (lst);
1138       int level = lst_depth (lst);
1139
1140       gcc_assert (lst && father && dewey >= 0 && level >= 0);
1141
1142       for (i = dewey; VEC_iterate (lst_p, LST_SEQ (father), i, l); i++)
1143         lst_update_scattering_under (l, level, i);
1144     }
1145
1146   if (LST_LOOP_P (lst))
1147     for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
1148       lst_update_scattering (l);
1149 }
1150
1151 /* Inserts LST1 before LST2 if BEFORE is true; inserts LST1 after LST2
1152    if BEFORE is false.  */
1153
1154 static inline void
1155 lst_insert_in_sequence (lst_p lst1, lst_p lst2, bool before)
1156 {
1157   lst_p father;
1158   int dewey;
1159
1160   /* Do not insert empty loops.  */
1161   if (!lst1 || lst_empty_p (lst1))
1162     return;
1163
1164   father = LST_LOOP_FATHER (lst2);
1165   dewey = lst_dewey_number (lst2);
1166
1167   gcc_assert (lst2 && father && dewey >= 0);
1168
1169   VEC_safe_insert (lst_p, heap, LST_SEQ (father), before ? dewey : dewey + 1,
1170                    lst1);
1171   LST_LOOP_FATHER (lst1) = father;
1172 }
1173
1174 /* Replaces LST1 with LST2.  */
1175
1176 static inline void
1177 lst_replace (lst_p lst1, lst_p lst2)
1178 {
1179   lst_p father;
1180   int dewey;
1181
1182   if (!lst2 || lst_empty_p (lst2))
1183     return;
1184
1185   father = LST_LOOP_FATHER (lst1);
1186   dewey = lst_dewey_number (lst1);
1187   LST_LOOP_FATHER (lst2) = father;
1188   VEC_replace (lst_p, LST_SEQ (father), dewey, lst2);
1189 }
1190
1191 /* Returns a copy of ROOT where LST has been replaced by a copy of the
1192    LSTs A B C in this sequence.  */
1193
1194 static inline lst_p
1195 lst_substitute_3 (lst_p root, lst_p lst, lst_p a, lst_p b, lst_p c)
1196 {
1197   int i;
1198   lst_p l;
1199   VEC (lst_p, heap) *seq;
1200
1201   if (!root)
1202     return NULL;
1203
1204   gcc_assert (lst && root != lst);
1205
1206   if (!LST_LOOP_P (root))
1207     return new_lst_stmt (LST_PBB (root));
1208
1209   seq = VEC_alloc (lst_p, heap, 5);
1210
1211   for (i = 0; VEC_iterate (lst_p, LST_SEQ (root), i, l); i++)
1212     if (l != lst)
1213       VEC_safe_push (lst_p, heap, seq, lst_substitute_3 (l, lst, a, b, c));
1214     else
1215       {
1216         if (!lst_empty_p (a))
1217           VEC_safe_push (lst_p, heap, seq, copy_lst (a));
1218         if (!lst_empty_p (b))
1219           VEC_safe_push (lst_p, heap, seq, copy_lst (b));
1220         if (!lst_empty_p (c))
1221           VEC_safe_push (lst_p, heap, seq, copy_lst (c));
1222       }
1223
1224   return new_lst_loop (seq);
1225 }
1226
1227 /* Moves LST before LOOP if BEFORE is true, and after the LOOP if
1228    BEFORE is false.  */
1229
1230 static inline void
1231 lst_distribute_lst (lst_p loop, lst_p lst, bool before)
1232 {
1233   int loop_depth = lst_depth (loop);
1234   int depth = lst_depth (lst);
1235   int nb_loops = depth - loop_depth;
1236
1237   gcc_assert (lst && loop && LST_LOOP_P (loop) && nb_loops > 0);
1238
1239   lst_remove_from_sequence (lst);
1240   lst_insert_in_sequence (lst_create_nest (nb_loops, lst), loop, before);
1241 }
1242
1243 /* Removes from LOOP all the statements before/after and including PBB
1244    if BEFORE is true/false.  Returns the negation of BEFORE when the
1245    statement PBB has been found.  */
1246
1247 static inline bool
1248 lst_remove_all_before_including_pbb (lst_p loop, poly_bb_p pbb, bool before)
1249 {
1250   int i;
1251   lst_p l;
1252
1253   if (!loop || !LST_LOOP_P (loop))
1254     return before;
1255
1256   for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l);)
1257     if (LST_LOOP_P (l))
1258       {
1259         before = lst_remove_all_before_including_pbb (l, pbb, before);
1260
1261         if (VEC_length (lst_p, LST_SEQ (l)) == 0)
1262           {
1263             VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1264             free_lst (l);
1265           }
1266         else
1267           i++;
1268       }
1269     else
1270       {
1271         if (before)
1272           {
1273             if (LST_PBB (l) == pbb)
1274               before = false;
1275
1276             VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1277             free_lst (l);
1278           }
1279         else if (LST_PBB (l) == pbb)
1280           {
1281             before = true;
1282             VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1283             free_lst (l);
1284           }
1285         else
1286           i++;
1287       }
1288
1289   return before;
1290 }
1291
1292 /* Removes from LOOP all the statements before/after and excluding PBB
1293    if BEFORE is true/false; Returns the negation of BEFORE when the
1294    statement PBB has been found.  */
1295
1296 static inline bool
1297 lst_remove_all_before_excluding_pbb (lst_p loop, poly_bb_p pbb, bool before)
1298 {
1299   int i;
1300   lst_p l;
1301
1302   if (!loop || !LST_LOOP_P (loop))
1303     return before;
1304
1305   for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l);)
1306     if (LST_LOOP_P (l))
1307       {
1308         before = lst_remove_all_before_excluding_pbb (l, pbb, before);
1309
1310         if (VEC_length (lst_p, LST_SEQ (l)) == 0)
1311           {
1312             VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1313             free_lst (l);
1314             continue;
1315           }
1316
1317         i++;
1318       }
1319     else
1320       {
1321         if (before && LST_PBB (l) != pbb)
1322           {
1323             VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1324             free_lst (l);
1325             continue;
1326           }
1327
1328         i++;
1329
1330         if (LST_PBB (l) == pbb)
1331           before = before ? false : true;
1332       }
1333
1334   return before;
1335 }
1336
1337 /* A SCOP is a Static Control Part of the program, simple enough to be
1338    represented in polyhedral form.  */
1339 struct scop
1340 {
1341   /* A SCOP is defined as a SESE region.  */
1342   void *region;
1343
1344   /* Number of parameters in SCoP.  */
1345   graphite_dim_t nb_params;
1346
1347   /* All the basic blocks in this scop that contain memory references
1348      and that will be represented as statements in the polyhedral
1349      representation.  */
1350   VEC (poly_bb_p, heap) *bbs;
1351
1352   /* Original, transformed and saved schedules.  */
1353   lst_p original_schedule, transformed_schedule, saved_schedule;
1354
1355   /* The context describes known restrictions concerning the parameters
1356      and relations in between the parameters.
1357
1358   void f (int8_t a, uint_16_t b) {
1359     c = 2 a + b;
1360     ...
1361   }
1362
1363   Here we can add these restrictions to the context:
1364
1365   -128 >= a >= 127
1366      0 >= b >= 65,535
1367      c = 2a + b  */
1368   ppl_Pointset_Powerset_C_Polyhedron_t context;
1369
1370   /* A hashtable of the data dependence relations for the original
1371      scattering.  */
1372   htab_t original_pddrs;
1373
1374   /* True when the scop has been converted to its polyhedral
1375      representation.  */
1376   bool poly_scop_p;
1377 };
1378
1379 #define SCOP_BBS(S) (S->bbs)
1380 #define SCOP_REGION(S) ((sese) S->region)
1381 #define SCOP_CONTEXT(S) (S->context)
1382 #define SCOP_ORIGINAL_PDDRS(S) (S->original_pddrs)
1383 #define SCOP_ORIGINAL_SCHEDULE(S) (S->original_schedule)
1384 #define SCOP_TRANSFORMED_SCHEDULE(S) (S->transformed_schedule)
1385 #define SCOP_SAVED_SCHEDULE(S) (S->saved_schedule)
1386 #define POLY_SCOP_P(S) (S->poly_scop_p)
1387
1388 extern scop_p new_scop (void *);
1389 extern void free_scop (scop_p);
1390 extern void free_scops (VEC (scop_p, heap) *);
1391 extern void print_generated_program (FILE *, scop_p);
1392 extern void debug_generated_program (scop_p);
1393 extern void print_scattering_function (FILE *, poly_bb_p, int);
1394 extern void print_scattering_functions (FILE *, scop_p, int);
1395 extern void debug_scattering_function (poly_bb_p, int);
1396 extern void debug_scattering_functions (scop_p, int);
1397 extern int scop_max_loop_depth (scop_p);
1398 extern int unify_scattering_dimensions (scop_p);
1399 extern bool apply_poly_transforms (scop_p);
1400 extern bool graphite_legal_transform (scop_p);
1401 extern void cloog_checksum (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