gcc/graphite-poly.h

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