gcc/graphite-poly.h

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