contrib/gcc-5.0/gcc/graphite-poly.h

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