gcc/graphite-poly.h

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