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