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