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