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