gcc/graphite-poly.h

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