gcc/graphite-poly.h

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