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   /* The sum of all the memory strides for an LST loop.  */
 636   Value memory_strides;
 637
 638   /* Loop nodes contain a sequence SEQ of LST nodes, statements
 639      contain a pointer to their polyhedral representation PBB.  */
 640   union {
 641     poly_bb_p pbb;
 642     VEC (lst_p, heap) *seq;
 643   } node;
 644 };
 645
 646 #define LST_LOOP_P(LST) ((LST)->loop_p)
 647 #define LST_LOOP_FATHER(LST) ((LST)->loop_father)
 648 #define LST_PBB(LST) ((LST)->node.pbb)
 649 #define LST_SEQ(LST) ((LST)->node.seq)
 650 #define LST_LOOP_MEMORY_STRIDES(LST) ((LST)->memory_strides)
 651
 652 void scop_to_lst (scop_p);
 653 void print_lst (FILE *, lst_p, int);
 654 void debug_lst (lst_p);
 655 void dot_lst (lst_p);
 656
 657 /* Creates a new LST loop with SEQ.  */
 658
 659 static inline lst_p
 660 new_lst_loop (VEC (lst_p, heap) *seq)
 661 {
 662   lst_p lst = XNEW (struct lst);
 663   int i;
 664   lst_p l;
 665
 666   LST_LOOP_P (lst) = true;
 667   LST_SEQ (lst) = seq;
 668   LST_LOOP_FATHER (lst) = NULL;
 669   value_init (LST_LOOP_MEMORY_STRIDES (lst));
 670   value_set_si (LST_LOOP_MEMORY_STRIDES (lst), -1);
 671
 672   for (i = 0; VEC_iterate (lst_p, seq, i, l); i++)
 673     LST_LOOP_FATHER (l) = lst;
 674
 675   return lst;
 676 }
 677
 678 /* Creates a new LST statement with PBB.  */
 679
 680 static inline lst_p
 681 new_lst_stmt (poly_bb_p pbb)
 682 {
 683   lst_p lst = XNEW (struct lst);
 684
 685   LST_LOOP_P (lst) = false;
 686   LST_PBB (lst) = pbb;
 687   LST_LOOP_FATHER (lst) = NULL;
 688   return lst;
 689 }
 690
 691 /* Frees the memory used by LST.  */
 692
 693 static inline void
 694 free_lst (lst_p lst)
 695 {
 696   if (!lst)
 697     return;
 698
 699   if (LST_LOOP_P (lst))
 700     {
 701       int i;
 702       lst_p l;
 703
 704       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 705         free_lst (l);
 706
 707       value_clear (LST_LOOP_MEMORY_STRIDES (lst));
 708       VEC_free (lst_p, heap, LST_SEQ (lst));
 709     }
 710
 711   free (lst);
 712 }
 713
 714 /* Returns a copy of LST.  */
 715
 716 static inline lst_p
 717 copy_lst (lst_p lst)
 718 {
 719   if (!lst)
 720     return NULL;
 721
 722   if (LST_LOOP_P (lst))
 723     {
 724       int i;
 725       lst_p l;
 726       VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
 727
 728       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 729         VEC_safe_push (lst_p, heap, seq, copy_lst (l));
 730
 731       return new_lst_loop (seq);
 732     }
 733
 734   return new_lst_stmt (LST_PBB (lst));
 735 }
 736
 737 /* Adds a new loop under the loop LST.  */
 738
 739 static inline void
 740 lst_add_loop_under_loop (lst_p lst)
 741 {
 742   VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 1);
 743   lst_p l = new_lst_loop (LST_SEQ (lst));
 744
 745   gcc_assert (LST_LOOP_P (lst));
 746
 747   LST_LOOP_FATHER (l) = lst;
 748   VEC_quick_push (lst_p, seq, l);
 749   LST_SEQ (lst) = seq;
 750 }
 751
 752 /* Returns the loop depth of LST.  */
 753
 754 static inline int
 755 lst_depth (lst_p lst)
 756 {
 757   if (!lst)
 758     return -2;
 759
 760   /* The depth of the outermost "fake" loop is -1.  This outermost
 761      loop does not have a loop father and it is just a container, as
 762      in the loop representation of GCC.  */
 763   if (!LST_LOOP_FATHER (lst))
 764     return -1;
 765
 766   return lst_depth (LST_LOOP_FATHER (lst)) + 1;
 767 }
 768
 769 /* Returns the Dewey number for LST.  */
 770
 771 static inline int
 772 lst_dewey_number (lst_p lst)
 773 {
 774   int i;
 775   lst_p l;
 776
 777   if (!lst)
 778     return -1;
 779
 780   if (!LST_LOOP_FATHER (lst))
 781     return 0;
 782
 783   for (i = 0; VEC_iterate (lst_p, LST_SEQ (LST_LOOP_FATHER (lst)), i, l); i++)
 784     if (l == lst)
 785       return i;
 786
 787   return -1;
 788 }
 789
 790 /* Returns the Dewey number of LST at depth DEPTH.  */
 791
 792 static inline int
 793 lst_dewey_number_at_depth (lst_p lst, int depth)
 794 {
 795   gcc_assert (lst && depth >= 0 && lst_depth (lst) <= depth);
 796
 797   if (lst_depth (lst) == depth)
 798     return lst_dewey_number (lst);
 799
 800   return lst_dewey_number_at_depth (LST_LOOP_FATHER (lst), depth);
 801 }
 802
 803 /* Returns the predecessor of LST in the sequence of its loop father.
 804    Returns NULL if LST is the first statement in the sequence.  */
 805
 806 static inline lst_p
 807 lst_pred (lst_p lst)
 808 {
 809   int dewey;
 810   lst_p father;
 811
 812   if (!lst || !LST_LOOP_FATHER (lst))
 813     return NULL;
 814
 815   dewey = lst_dewey_number (lst);
 816   if (dewey == 0)
 817     return NULL;
 818
 819   father = LST_LOOP_FATHER (lst);
 820   return VEC_index (lst_p, LST_SEQ (father), dewey - 1);
 821 }
 822
 823 /* Returns the successor of LST in the sequence of its loop father.
 824    Returns NULL if there is none.  */
 825
 826 static inline lst_p
 827 lst_succ (lst_p lst)
 828 {
 829   int dewey;
 830   lst_p father;
 831
 832   if (!lst || !LST_LOOP_FATHER (lst))
 833     return NULL;
 834
 835   dewey = lst_dewey_number (lst);
 836   father = LST_LOOP_FATHER (lst);
 837
 838   if (VEC_length (lst_p, LST_SEQ (father)) == (unsigned) dewey + 1)
 839     return NULL;
 840
 841   return VEC_index (lst_p, LST_SEQ (father), dewey + 1);
 842 }
 843
 844
 845 /* Return the LST node corresponding to PBB.  */
 846
 847 static inline lst_p
 848 lst_find_pbb (lst_p lst, poly_bb_p pbb)
 849 {
 850   int i;
 851   lst_p l;
 852
 853   if (!lst)
 854     return NULL;
 855
 856   if (!LST_LOOP_P (lst))
 857     return (pbb == LST_PBB (lst)) ? lst : NULL;
 858
 859   for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 860     {
 861       lst_p res = lst_find_pbb (l, pbb);
 862       if (res)
 863         return res;
 864     }
 865
 866   return NULL;
 867 }
 868
 869 /* Return the LST node corresponding to the loop around STMT at depth
 870    LOOP_DEPTH.  */
 871
 872 static inline lst_p
 873 find_lst_loop (lst_p stmt, int loop_depth)
 874 {
 875   lst_p loop = LST_LOOP_FATHER (stmt);
 876
 877   gcc_assert (loop_depth >= 0);
 878
 879   while (loop_depth < lst_depth (loop))
 880     loop = LST_LOOP_FATHER (loop);
 881
 882   return loop;
 883 }
 884
 885 /* Return the first lst representing a PBB statement in LST.  */
 886
 887 static inline lst_p
 888 lst_find_first_pbb (lst_p lst)
 889 {
 890   int i;
 891   lst_p l;
 892
 893   if (!lst)
 894     return NULL;
 895
 896   if (!LST_LOOP_P (lst))
 897     return lst;
 898
 899   for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 900     {
 901       lst_p res = lst_find_first_pbb (l);
 902       if (res)
 903         return res;
 904     }
 905
 906   return NULL;
 907 }
 908
 909 /* Returns true when LST is a loop that does not contains
 910    statements.  */
 911
 912 static inline bool
 913 lst_empty_p (lst_p lst)
 914 {
 915   return !lst_find_first_pbb (lst);
 916 }
 917
 918 /* Return the last lst representing a PBB statement in LST.  */
 919
 920 static inline lst_p
 921 lst_find_last_pbb (lst_p lst)
 922 {
 923   int i;
 924   lst_p l, res = NULL;
 925
 926   if (!lst)
 927     return NULL;
 928
 929   if (!LST_LOOP_P (lst))
 930     return lst;
 931
 932   for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 933     {
 934       lst_p last = lst_find_last_pbb (l);
 935
 936       if (last)
 937         res = last;
 938     }
 939
 940   gcc_assert (res);
 941   return res;
 942 }
 943
 944 /* Returns true if LOOP contains LST, in other words, if LST is nested
 945    in LOOP.  */
 946
 947 static inline bool
 948 lst_contains_p (lst_p loop, lst_p lst)
 949 {
 950   if (!loop || !lst || !LST_LOOP_P (loop))
 951     return false;
 952
 953   if (loop == lst)
 954     return true;
 955
 956   return lst_contains_p (loop, LST_LOOP_FATHER (lst));
 957 }
 958
 959 /* Returns true if LOOP contains PBB, in other words, if PBB is nested
 960    in LOOP.  */
 961
 962 static inline bool
 963 lst_contains_pbb (lst_p loop, poly_bb_p pbb)
 964 {
 965   return lst_find_pbb (loop, pbb) ? true : false;
 966 }
 967
 968 /* Creates a loop nest of depth NB_LOOPS containing LST.  */
 969
 970 static inline lst_p
 971 lst_create_nest (int nb_loops, lst_p lst)
 972 {
 973   lst_p res, loop;
 974   VEC (lst_p, heap) *seq;
 975
 976   if (nb_loops == 0)
 977     return lst;
 978
 979   seq = VEC_alloc (lst_p, heap, 1);
 980   loop = lst_create_nest (nb_loops - 1, lst);
 981   VEC_quick_push (lst_p, seq, loop);
 982   res = new_lst_loop (seq);
 983   LST_LOOP_FATHER (loop) = res;
 984
 985   return res;
 986 }
 987
 988 /* Removes LST from the sequence of statements of its loop father.  */
 989
 990 static inline void
 991 lst_remove_from_sequence (lst_p lst)
 992 {
 993   lst_p father = LST_LOOP_FATHER (lst);
 994   int dewey = lst_dewey_number (lst);
 995
 996   gcc_assert (lst && father && dewey >= 0);
 997
 998   VEC_ordered_remove (lst_p, LST_SEQ (father), dewey);
 999   LST_LOOP_FATHER (lst) = NULL;
1000 }
1001
1002 /* Updates the scattering of PBB to be at the DEWEY number in the loop
1003    at depth LEVEL.  */
1004
1005 static inline void
1006 pbb_update_scattering (poly_bb_p pbb, graphite_dim_t level, int dewey)
1007 {
1008   ppl_Polyhedron_t ph = PBB_TRANSFORMED_SCATTERING (pbb);
1009   ppl_dimension_type sched = psct_static_dim (pbb, level);
1010   ppl_dimension_type ds[1];
1011   ppl_Constraint_t new_cstr;
1012   ppl_Linear_Expression_t expr;
1013   ppl_dimension_type dim;
1014
1015   ppl_Polyhedron_space_dimension (ph, &dim);
1016   ds[0] = sched;
1017   ppl_Polyhedron_remove_space_dimensions (ph, ds, 1);
1018   ppl_insert_dimensions (ph, sched, 1);
1019
1020   ppl_new_Linear_Expression_with_dimension (&expr, dim);
1021   ppl_set_coef (expr, sched, -1);
1022   ppl_set_inhomogeneous (expr, dewey);
1023   ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
1024   ppl_delete_Linear_Expression (expr);
1025   ppl_Polyhedron_add_constraint (ph, new_cstr);
1026   ppl_delete_Constraint (new_cstr);
1027 }
1028
1029 /* Updates the scattering of all the PBBs under LST to be at the DEWEY
1030    number in the loop at depth LEVEL.  */
1031
1032 static inline void
1033 lst_update_scattering_under (lst_p lst, int level, int dewey)
1034 {
1035   int i;
1036   lst_p l;
1037
1038   gcc_assert (lst && level >= 0 && dewey >= 0);
1039
1040   if (LST_LOOP_P (lst))
1041     for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
1042       lst_update_scattering_under (l, level, dewey);
1043   else
1044     pbb_update_scattering (LST_PBB (lst), level, dewey);
1045 }
1046
1047 /* Updates the scattering of all the PBBs under LST and in sequence
1048    with LST.  */
1049
1050 static inline void
1051 lst_update_scattering_seq (lst_p lst)
1052 {
1053   int i;
1054   lst_p l;
1055   lst_p father = LST_LOOP_FATHER (lst);
1056   int dewey = lst_dewey_number (lst);
1057   int level = lst_depth (lst);
1058
1059   gcc_assert (lst && father && dewey >= 0 && level >= 0);
1060
1061   for (i = dewey; VEC_iterate (lst_p, LST_SEQ (father), i, l); i++)
1062     lst_update_scattering_under (l, level, i);
1063 }
1064
1065 /* Updates the all the scattering levels of all the PBBs under
1066    LST.  */
1067
1068 static inline void
1069 lst_update_scattering (lst_p lst)
1070 {
1071   int i;
1072   lst_p l;
1073
1074   if (!lst || !LST_LOOP_P (lst))
1075     return;
1076
1077   if (LST_LOOP_FATHER (lst))
1078     lst_update_scattering_seq (lst);
1079
1080   for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
1081     lst_update_scattering (l);
1082 }
1083
1084 /* Inserts LST1 before LST2 if BEFORE is true; inserts LST1 after LST2
1085    if BEFORE is false.  */
1086
1087 static inline void
1088 lst_insert_in_sequence (lst_p lst1, lst_p lst2, bool before)
1089 {
1090   lst_p father;
1091   int dewey;
1092
1093   /* Do not insert empty loops.  */
1094   if (!lst1 || lst_empty_p (lst1))
1095     return;
1096
1097   father = LST_LOOP_FATHER (lst2);
1098   dewey = lst_dewey_number (lst2);
1099
1100   gcc_assert (lst2 && father && dewey >= 0);
1101
1102   VEC_safe_insert (lst_p, heap, LST_SEQ (father), before ? dewey : dewey + 1,
1103                    lst1);
1104   LST_LOOP_FATHER (lst1) = father;
1105 }
1106
1107 /* Replaces LST1 with LST2.  */
1108
1109 static inline void
1110 lst_replace (lst_p lst1, lst_p lst2)
1111 {
1112   lst_p father;
1113   int dewey;
1114
1115   if (!lst2 || lst_empty_p (lst2))
1116     return;
1117
1118   father = LST_LOOP_FATHER (lst1);
1119   dewey = lst_dewey_number (lst1);
1120   LST_LOOP_FATHER (lst2) = father;
1121   VEC_replace (lst_p, LST_SEQ (father), dewey, lst2);
1122 }
1123
1124 /* Returns a copy of ROOT where LST has been replaced by a copy of the
1125    LSTs A B C in this sequence.  */
1126
1127 static inline lst_p
1128 lst_substitute_3 (lst_p root, lst_p lst, lst_p a, lst_p b, lst_p c)
1129 {
1130   int i;
1131   lst_p l;
1132   VEC (lst_p, heap) *seq;
1133
1134   if (!root)
1135     return NULL;
1136
1137   gcc_assert (lst && root != lst);
1138
1139   if (!LST_LOOP_P (root))
1140     return new_lst_stmt (LST_PBB (root));
1141
1142   seq = VEC_alloc (lst_p, heap, 5);
1143
1144   for (i = 0; VEC_iterate (lst_p, LST_SEQ (root), i, l); i++)
1145     if (l != lst)
1146       VEC_safe_push (lst_p, heap, seq, lst_substitute_3 (l, lst, a, b, c));
1147     else
1148       {
1149         if (!lst_empty_p (a))
1150           VEC_safe_push (lst_p, heap, seq, copy_lst (a));
1151         if (!lst_empty_p (b))
1152           VEC_safe_push (lst_p, heap, seq, copy_lst (b));
1153         if (!lst_empty_p (c))
1154           VEC_safe_push (lst_p, heap, seq, copy_lst (c));
1155       }
1156
1157   return new_lst_loop (seq);
1158 }
1159
1160 /* Moves LST before LOOP if BEFORE is true, and after the LOOP if
1161    BEFORE is false.  */
1162
1163 static inline void
1164 lst_distribute_lst (lst_p loop, lst_p lst, bool before)
1165 {
1166   int loop_depth = lst_depth (loop);
1167   int depth = lst_depth (lst);
1168   int nb_loops = depth - loop_depth;
1169
1170   gcc_assert (lst && loop && LST_LOOP_P (loop) && nb_loops > 0);
1171
1172   lst_remove_from_sequence (lst);
1173   lst_insert_in_sequence (lst_create_nest (nb_loops, lst), loop, before);
1174 }
1175
1176 /* Removes from LOOP all the statements before/after and including PBB
1177    if BEFORE is true/false.  Returns the negation of BEFORE when the
1178    statement PBB has been found.  */
1179
1180 static inline bool
1181 lst_remove_all_before_including_pbb (lst_p loop, poly_bb_p pbb, bool before)
1182 {
1183   int i;
1184   lst_p l;
1185
1186   if (!loop || !LST_LOOP_P (loop))
1187     return before;
1188
1189   for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l);)
1190     if (LST_LOOP_P (l))
1191       {
1192         before = lst_remove_all_before_including_pbb (l, pbb, before);
1193
1194         if (VEC_length (lst_p, LST_SEQ (l)) == 0)
1195           {
1196             VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1197             free_lst (l);
1198           }
1199         else
1200           i++;
1201       }
1202     else
1203       {
1204         if (before)
1205           {
1206             if (LST_PBB (l) == pbb)
1207               before = false;
1208
1209             VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1210             free_lst (l);
1211           }
1212         else if (LST_PBB (l) == pbb)
1213           {
1214             before = true;
1215             VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1216             free_lst (l);
1217           }
1218         else
1219           i++;
1220       }
1221
1222   return before;
1223 }
1224
1225 /* Removes from LOOP all the statements before/after and excluding PBB
1226    if BEFORE is true/false; Returns the negation of BEFORE when the
1227    statement PBB has been found.  */
1228
1229 static inline bool
1230 lst_remove_all_before_excluding_pbb (lst_p loop, poly_bb_p pbb, bool before)
1231 {
1232   int i;
1233   lst_p l;
1234
1235   if (!loop || !LST_LOOP_P (loop))
1236     return before;
1237
1238   for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l);)
1239     if (LST_LOOP_P (l))
1240       {
1241         before = lst_remove_all_before_excluding_pbb (l, pbb, before);
1242
1243         if (VEC_length (lst_p, LST_SEQ (l)) == 0)
1244           {
1245             VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1246             free_lst (l);
1247             continue;
1248           }
1249
1250         i++;
1251       }
1252     else
1253       {
1254         if (before && LST_PBB (l) != pbb)
1255           {
1256             VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1257             free_lst (l);
1258             continue;
1259           }
1260
1261         i++;
1262
1263         if (LST_PBB (l) == pbb)
1264           before = before ? false : true;
1265       }
1266
1267   return before;
1268 }
1269
1270 /* A SCOP is a Static Control Part of the program, simple enough to be
1271    represented in polyhedral form.  */
1272 struct scop
1273 {
1274   /* A SCOP is defined as a SESE region.  */
1275   void *region;
1276
1277   /* Number of parameters in SCoP.  */
1278   graphite_dim_t nb_params;
1279
1280   /* All the basic blocks in this scop that contain memory references
1281      and that will be represented as statements in the polyhedral
1282      representation.  */
1283   VEC (poly_bb_p, heap) *bbs;
1284
1285   /* Original, transformed and saved schedules.  */
1286   lst_p original_schedule, transformed_schedule, saved_schedule;
1287
1288   /* The context describes known restrictions concerning the parameters
1289      and relations in between the parameters.
1290
1291   void f (int8_t a, uint_16_t b) {
1292     c = 2 a + b;
1293     ...
1294   }
1295
1296   Here we can add these restrictions to the context:
1297
1298   -128 >= a >= 127
1299      0 >= b >= 65,535
1300      c = 2a + b  */
1301   ppl_Pointset_Powerset_C_Polyhedron_t context;
1302
1303   /* A hashtable of the data dependence relations for the original
1304      scattering.  */
1305   htab_t original_pddrs;
1306 };
1307
1308 #define SCOP_BBS(S) (S->bbs)
1309 #define SCOP_REGION(S) ((sese) S->region)
1310 #define SCOP_CONTEXT(S) (S->context)
1311 #define SCOP_ORIGINAL_PDDRS(S) (S->original_pddrs)
1312 #define SCOP_ORIGINAL_SCHEDULE(S) (S->original_schedule)
1313 #define SCOP_TRANSFORMED_SCHEDULE(S) (S->transformed_schedule)
1314 #define SCOP_SAVED_SCHEDULE(S) (S->saved_schedule)
1315
1316 extern scop_p new_scop (void *);
1317 extern void free_scop (scop_p);
1318 extern void free_scops (VEC (scop_p, heap) *);
1319 extern void print_generated_program (FILE *, scop_p);
1320 extern void debug_generated_program (scop_p);
1321 extern void print_scattering_function (FILE *, poly_bb_p);
1322 extern void print_scattering_functions (FILE *, scop_p);
1323 extern void debug_scattering_function (poly_bb_p);
1324 extern void debug_scattering_functions (scop_p);
1325 extern int scop_max_loop_depth (scop_p);
1326 extern int unify_scattering_dimensions (scop_p);
1327 extern bool apply_poly_transforms (scop_p);
1328 extern bool graphite_legal_transform (scop_p);
1329
1330 /* Set the region of SCOP to REGION.  */
1331
1332 static inline void
1333 scop_set_region (scop_p scop, void *region)
1334 {
1335   scop->region = region;
1336 }
1337
1338 /* Returns the number of parameters for SCOP.  */
1339
1340 static inline graphite_dim_t
1341 scop_nb_params (scop_p scop)
1342 {
1343   return scop->nb_params;
1344 }
1345
1346 /* Set the number of params of SCOP to NB_PARAMS.  */
1347
1348 static inline void
1349 scop_set_nb_params (scop_p scop, graphite_dim_t nb_params)
1350 {
1351   scop->nb_params = nb_params;
1352 }
1353
1354 /* Allocates a new empty poly_scattering structure.  */
1355
1356 static inline poly_scattering_p
1357 poly_scattering_new (void)
1358 {
1359   poly_scattering_p res = XNEW (struct poly_scattering);
1360
1361   res->scattering = NULL;
1362   res->nb_local_variables = 0;
1363   res->nb_scattering = 0;
1364   return res;
1365 }
1366
1367 /* Free a poly_scattering structure.  */
1368
1369 static inline void
1370 poly_scattering_free (poly_scattering_p s)
1371 {
1372   ppl_delete_Polyhedron (s->scattering);
1373   free (s);
1374 }
1375
1376 /* Copies S and return a new scattering.  */
1377
1378 static inline poly_scattering_p
1379 poly_scattering_copy (poly_scattering_p s)
1380 {
1381   poly_scattering_p res = poly_scattering_new ();
1382
1383   ppl_new_C_Polyhedron_from_C_Polyhedron (&(res->scattering), s->scattering);
1384   res->nb_local_variables = s->nb_local_variables;
1385   res->nb_scattering = s->nb_scattering;
1386   return res;
1387 }
1388
1389 /* Saves the transformed scattering of PBB.  */
1390
1391 static inline void
1392 store_scattering_pbb (poly_bb_p pbb)
1393 {
1394   gcc_assert (PBB_TRANSFORMED (pbb));
1395
1396   if (PBB_SAVED (pbb))
1397     poly_scattering_free (PBB_SAVED (pbb));
1398
1399   PBB_SAVED (pbb) = poly_scattering_copy (PBB_TRANSFORMED (pbb));
1400 }
1401
1402 /* Stores the SCOP_TRANSFORMED_SCHEDULE to SCOP_SAVED_SCHEDULE.  */
1403
1404 static inline void
1405 store_lst_schedule (scop_p scop)
1406 {
1407   if (SCOP_SAVED_SCHEDULE (scop))
1408     free_lst (SCOP_SAVED_SCHEDULE (scop));
1409
1410   SCOP_SAVED_SCHEDULE (scop) = copy_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
1411 }
1412
1413 /* Restores the SCOP_TRANSFORMED_SCHEDULE from SCOP_SAVED_SCHEDULE.  */
1414
1415 static inline void
1416 restore_lst_schedule (scop_p scop)
1417 {
1418   if (SCOP_TRANSFORMED_SCHEDULE (scop))
1419     free_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
1420
1421   SCOP_TRANSFORMED_SCHEDULE (scop) = copy_lst (SCOP_SAVED_SCHEDULE (scop));
1422 }
1423
1424 /* Saves the scattering for all the pbbs in the SCOP.  */
1425
1426 static inline void
1427 store_scattering (scop_p scop)
1428 {
1429   int i;
1430   poly_bb_p pbb;
1431
1432   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1433     store_scattering_pbb (pbb);
1434
1435   store_lst_schedule (scop);
1436 }
1437
1438 /* Restores the scattering of PBB.  */
1439
1440 static inline void
1441 restore_scattering_pbb (poly_bb_p pbb)
1442 {
1443   gcc_assert (PBB_SAVED (pbb));
1444
1445   poly_scattering_free (PBB_TRANSFORMED (pbb));
1446   PBB_TRANSFORMED (pbb) = poly_scattering_copy (PBB_SAVED (pbb));
1447 }
1448
1449 /* Restores the scattering for all the pbbs in the SCOP.  */
1450
1451 static inline void
1452 restore_scattering (scop_p scop)
1453 {
1454   int i;
1455   poly_bb_p pbb;
1456
1457   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1458     restore_scattering_pbb (pbb);
1459
1460   restore_lst_schedule (scop);
1461 }
1462
1463 #endif