gcc/graphite-poly.h

   1 /* Graphite polyhedral representation.
   2    Copyright (C) 2009, 2010, 2011 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 unsigned 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   isl_map *accesses;
 184   isl_set *extent;
 185
 186   /* Data reference's base object set number, we must assure 2 pdrs are in the
 187      same base object set before dependency checking.  */
 188   int dr_base_object_set;
 189
 190   /* The number of subscripts.  */
 191   graphite_dim_t nb_subscripts;
 192 };
 193
 194 #define PDR_ID(PDR) (PDR->id)
 195 #define PDR_NB_REFS(PDR) (PDR->nb_refs)
 196 #define PDR_CDR(PDR) (PDR->compiler_dr)
 197 #define PDR_PBB(PDR) (PDR->pbb)
 198 #define PDR_TYPE(PDR) (PDR->type)
 199 #define PDR_ACCESSES(PDR) (NULL)
 200 #define PDR_BASE_OBJECT_SET(PDR) (PDR->dr_base_object_set)
 201 #define PDR_NB_SUBSCRIPTS(PDR) (PDR->nb_subscripts)
 202
 203 void new_poly_dr (poly_bb_p, int, enum poly_dr_type, void *,
 204                   graphite_dim_t, isl_map *, isl_set *);
 205 void free_poly_dr (poly_dr_p);
 206 void debug_pdr (poly_dr_p, int);
 207 void print_pdr (FILE *, poly_dr_p, int);
 208 static inline scop_p pdr_scop (poly_dr_p pdr);
 209
 210 /* The dimension of the iteration domain of the scop of PDR.  */
 211
 212 static inline graphite_dim_t
 213 pdr_dim_iter_domain (poly_dr_p pdr)
 214 {
 215   return pbb_dim_iter_domain (PDR_PBB (pdr));
 216 }
 217
 218 /* The number of parameters of the scop of PDR.  */
 219
 220 static inline graphite_dim_t
 221 pdr_nb_params (poly_dr_p pdr)
 222 {
 223   return scop_nb_params (pdr_scop (pdr));
 224 }
 225
 226 /* The dimension of the alias set in PDR.  */
 227
 228 static inline graphite_dim_t
 229 pdr_alias_set_dim (poly_dr_p pdr)
 230 {
 231   poly_bb_p pbb = PDR_PBB (pdr);
 232
 233   return pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
 234 }
 235
 236 /* The dimension in PDR containing subscript S.  */
 237
 238 static inline graphite_dim_t
 239 pdr_subscript_dim (poly_dr_p pdr, graphite_dim_t s)
 240 {
 241   poly_bb_p pbb = PDR_PBB (pdr);
 242
 243   return pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb) + 1 + s;
 244 }
 245
 246 /* The dimension in PDR containing the loop iterator ITER.  */
 247
 248 static inline graphite_dim_t
 249 pdr_iterator_dim (poly_dr_p pdr ATTRIBUTE_UNUSED, graphite_dim_t iter)
 250 {
 251   return iter;
 252 }
 253
 254 /* The dimension in PDR containing parameter PARAM.  */
 255
 256 static inline graphite_dim_t
 257 pdr_parameter_dim (poly_dr_p pdr, graphite_dim_t param)
 258 {
 259   poly_bb_p pbb = PDR_PBB (pdr);
 260
 261   return pbb_dim_iter_domain (pbb) + param;
 262 }
 263
 264 /* Returns true when PDR is a "read".  */
 265
 266 static inline bool
 267 pdr_read_p (poly_dr_p pdr)
 268 {
 269   return PDR_TYPE (pdr) == PDR_READ;
 270 }
 271
 272 /* Returns true when PDR is a "write".  */
 273
 274 static inline bool
 275 pdr_write_p (poly_dr_p pdr)
 276 {
 277   return PDR_TYPE (pdr) == PDR_WRITE;
 278 }
 279
 280 /* Returns true when PDR is a "may write".  */
 281
 282 static inline bool
 283 pdr_may_write_p (poly_dr_p pdr)
 284 {
 285   return PDR_TYPE (pdr) == PDR_MAY_WRITE;
 286 }
 287
 288 /* Return true when PDR1 and PDR2 are similar data accesses: they have
 289    the same base array, and the same access functions.  */
 290
 291 static inline bool
 292 same_pdr_p (poly_dr_p pdr1, poly_dr_p pdr2)
 293 {
 294   return PDR_NB_SUBSCRIPTS (pdr1) == PDR_NB_SUBSCRIPTS (pdr2)
 295     && PDR_BASE_OBJECT_SET (pdr1) == PDR_BASE_OBJECT_SET (pdr2);
 296 }
 297
 298 typedef struct poly_scattering *poly_scattering_p;
 299
 300 struct poly_scattering
 301 {
 302   /* The number of local variables.  */
 303   int nb_local_variables;
 304
 305   /* The number of scattering dimensions.  */
 306   int nb_scattering;
 307 };
 308
 309 /* POLY_BB represents a blackbox in the polyhedral model.  */
 310
 311 struct poly_bb
 312 {
 313   /* Pointer to a basic block or a statement in the compiler.  */
 314   void *black_box;
 315
 316   /* Pointer to the SCOP containing this PBB.  */
 317   scop_p scop;
 318
 319   /* The iteration domain of this bb.  The layout of this polyhedron
 320      is I|G with I the iteration domain, G the context parameters.
 321
 322      Example:
 323
 324      for (i = a - 7*b + 8; i <= 3*a + 13*b + 20; i++)
 325        for (j = 2; j <= 2*i + 5; j++)
 326          for (k = 0; k <= 5; k++)
 327            S (i,j,k)
 328
 329      Loop iterators: i, j, k
 330      Parameters: a, b
 331
 332      | i >=  a -  7b +  8
 333      | i <= 3a + 13b + 20
 334      | j >= 2
 335      | j <= 2i + 5
 336      | k >= 0
 337      | k <= 5
 338
 339      The number of variables in the DOMAIN may change and is not
 340      related to the number of loops in the original code.  */
 341   isl_set *domain;
 342
 343   /* The data references we access.  */
 344   VEC (poly_dr_p, heap) *drs;
 345
 346   /* The original scattering.  */
 347   poly_scattering_p _original;
 348   isl_map *schedule;
 349
 350   /* The transformed scattering.  */
 351   poly_scattering_p _transformed;
 352   isl_map *transformed;
 353
 354   /* A copy of the transformed scattering.  */
 355   poly_scattering_p _saved;
 356   isl_map *saved;
 357
 358   /* True when this PBB contains only a reduction statement.  */
 359   bool is_reduction;
 360 };
 361
 362 #define PBB_BLACK_BOX(PBB) ((gimple_bb_p) PBB->black_box)
 363 #define PBB_SCOP(PBB) (PBB->scop)
 364 #define PBB_DOMAIN(PBB) (NULL)
 365 #define PBB_DRS(PBB) (PBB->drs)
 366 #define PBB_ORIGINAL(PBB) (PBB->_original)
 367 #define PBB_ORIGINAL_SCATTERING(PBB) (NULL)
 368 #define PBB_TRANSFORMED(PBB) (PBB->_transformed)
 369 #define PBB_TRANSFORMED_SCATTERING(PBB) (NULL)
 370 #define PBB_SAVED(PBB) (PBB->_saved)
 371 /* XXX isl if we ever need local vars in the scatter, we can't use the
 372    out dimension of transformed to count the scatterting transform dimension.
 373    */
 374 #define PBB_NB_LOCAL_VARIABLES(PBB) (0)
 375 #define PBB_NB_SCATTERING_TRANSFORM(PBB) (isl_map_n_out (PBB->transformed))
 376 #define PBB_IS_REDUCTION(PBB) (PBB->is_reduction)
 377
 378 extern poly_bb_p new_poly_bb (scop_p, void *);
 379 extern void free_poly_bb (poly_bb_p);
 380 extern void debug_loop_vec (poly_bb_p);
 381 extern void schedule_to_scattering (poly_bb_p, int);
 382 extern void print_pbb_domain (FILE *, poly_bb_p, int);
 383 extern void print_pbb (FILE *, poly_bb_p, int);
 384 extern void print_scop_context (FILE *, scop_p, int);
 385 extern void print_scop (FILE *, scop_p, int);
 386 extern void print_cloog (FILE *, scop_p, int);
 387 extern void debug_pbb_domain (poly_bb_p, int);
 388 extern void debug_pbb (poly_bb_p, int);
 389 extern void print_pdrs (FILE *, poly_bb_p, int);
 390 extern void debug_pdrs (poly_bb_p, int);
 391 extern void debug_scop_context (scop_p, int);
 392 extern void debug_scop (scop_p, int);
 393 extern void debug_cloog (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; VEC_iterate (poly_dr_p, PBB_DRS (pbb), 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 DEF_VEC_P(lst_p);
 676 DEF_VEC_ALLOC_P (lst_p, heap);
 677
 678 /* Loops and Statements Tree.  */
 679 struct lst {
 680
 681   /* LOOP_P is true when an LST node is a loop.  */
 682   bool loop_p;
 683
 684   /* A pointer to the loop that contains this node.  */
 685   lst_p loop_father;
 686
 687   /* The sum of all the memory strides for an LST loop.  */
 688   mpz_t memory_strides;
 689
 690   /* Loop nodes contain a sequence SEQ of LST nodes, statements
 691      contain a pointer to their polyhedral representation PBB.  */
 692   union {
 693     poly_bb_p pbb;
 694     VEC (lst_p, heap) *seq;
 695   } node;
 696 };
 697
 698 #define LST_LOOP_P(LST) ((LST)->loop_p)
 699 #define LST_LOOP_FATHER(LST) ((LST)->loop_father)
 700 #define LST_PBB(LST) ((LST)->node.pbb)
 701 #define LST_SEQ(LST) ((LST)->node.seq)
 702 #define LST_LOOP_MEMORY_STRIDES(LST) ((LST)->memory_strides)
 703
 704 void scop_to_lst (scop_p);
 705 void print_lst (FILE *, lst_p, int);
 706 void debug_lst (lst_p);
 707 void dot_lst (lst_p);
 708
 709 /* Creates a new LST loop with SEQ.  */
 710
 711 static inline lst_p
 712 new_lst_loop (VEC (lst_p, heap) *seq)
 713 {
 714   lst_p lst = XNEW (struct lst);
 715   int i;
 716   lst_p l;
 717
 718   LST_LOOP_P (lst) = true;
 719   LST_SEQ (lst) = seq;
 720   LST_LOOP_FATHER (lst) = NULL;
 721   mpz_init (LST_LOOP_MEMORY_STRIDES (lst));
 722   mpz_set_si (LST_LOOP_MEMORY_STRIDES (lst), -1);
 723
 724   for (i = 0; VEC_iterate (lst_p, seq, i, l); i++)
 725     LST_LOOP_FATHER (l) = lst;
 726
 727   return lst;
 728 }
 729
 730 /* Creates a new LST statement with PBB.  */
 731
 732 static inline lst_p
 733 new_lst_stmt (poly_bb_p pbb)
 734 {
 735   lst_p lst = XNEW (struct lst);
 736
 737   LST_LOOP_P (lst) = false;
 738   LST_PBB (lst) = pbb;
 739   LST_LOOP_FATHER (lst) = NULL;
 740   return lst;
 741 }
 742
 743 /* Frees the memory used by LST.  */
 744
 745 static inline void
 746 free_lst (lst_p lst)
 747 {
 748   if (!lst)
 749     return;
 750
 751   if (LST_LOOP_P (lst))
 752     {
 753       int i;
 754       lst_p l;
 755
 756       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 757         free_lst (l);
 758
 759       mpz_clear (LST_LOOP_MEMORY_STRIDES (lst));
 760       VEC_free (lst_p, heap, LST_SEQ (lst));
 761     }
 762
 763   free (lst);
 764 }
 765
 766 /* Returns a copy of LST.  */
 767
 768 static inline lst_p
 769 copy_lst (lst_p lst)
 770 {
 771   if (!lst)
 772     return NULL;
 773
 774   if (LST_LOOP_P (lst))
 775     {
 776       int i;
 777       lst_p l;
 778       VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
 779
 780       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 781         VEC_safe_push (lst_p, heap, seq, copy_lst (l));
 782
 783       return new_lst_loop (seq);
 784     }
 785
 786   return new_lst_stmt (LST_PBB (lst));
 787 }
 788
 789 /* Adds a new loop under the loop LST.  */
 790
 791 static inline void
 792 lst_add_loop_under_loop (lst_p lst)
 793 {
 794   VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 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   VEC_quick_push (lst_p, seq, 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_p, 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 VEC_index (lst_p, 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 (VEC_length (lst_p, LST_SEQ (father)) == (unsigned) dewey + 1)
 891     return NULL;
 892
 893   return VEC_index (lst_p, 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; VEC_iterate (lst_p, LST_SEQ (lst), 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; VEC_iterate (lst_p, LST_SEQ (lst), 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; VEC_iterate (lst_p, LST_SEQ (lst), 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, heap) *seq;
1027
1028   if (nb_loops == 0)
1029     return lst;
1030
1031   seq = VEC_alloc (lst_p, heap, 1);
1032   loop = lst_create_nest (nb_loops - 1, lst);
1033   VEC_quick_push (lst_p, seq, 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   VEC_ordered_remove (lst_p, LST_SEQ (father), 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   VEC_ordered_remove (lst_p, LST_SEQ (father), dewey);
1065   LST_LOOP_FATHER (lst) = NULL;
1066
1067   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
1068     {
1069       VEC_safe_insert (lst_p, heap, LST_SEQ (father), 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; VEC_iterate (lst_p, LST_SEQ (lst), 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; VEC_iterate (lst_p, LST_SEQ (father), i, l); i++)
1148         lst_update_scattering_under (l, level, i);
1149     }
1150
1151   if (LST_LOOP_P (lst))
1152     for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), 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   VEC_safe_insert (lst_p, heap, LST_SEQ (father), before ? dewey : dewey + 1,
1175                    lst1);
1176   LST_LOOP_FATHER (lst1) = father;
1177 }
1178
1179 /* Replaces LST1 with LST2.  */
1180
1181 static inline void
1182 lst_replace (lst_p lst1, lst_p lst2)
1183 {
1184   lst_p father;
1185   int dewey;
1186
1187   if (!lst2 || lst_empty_p (lst2))
1188     return;
1189
1190   father = LST_LOOP_FATHER (lst1);
1191   dewey = lst_dewey_number (lst1);
1192   LST_LOOP_FATHER (lst2) = father;
1193   VEC_replace (lst_p, LST_SEQ (father), dewey, lst2);
1194 }
1195
1196 /* Returns a copy of ROOT where LST has been replaced by a copy of the
1197    LSTs A B C in this sequence.  */
1198
1199 static inline lst_p
1200 lst_substitute_3 (lst_p root, lst_p lst, lst_p a, lst_p b, lst_p c)
1201 {
1202   int i;
1203   lst_p l;
1204   VEC (lst_p, heap) *seq;
1205
1206   if (!root)
1207     return NULL;
1208
1209   gcc_assert (lst && root != lst);
1210
1211   if (!LST_LOOP_P (root))
1212     return new_lst_stmt (LST_PBB (root));
1213
1214   seq = VEC_alloc (lst_p, heap, 5);
1215
1216   for (i = 0; VEC_iterate (lst_p, LST_SEQ (root), i, l); i++)
1217     if (l != lst)
1218       VEC_safe_push (lst_p, heap, seq, lst_substitute_3 (l, lst, a, b, c));
1219     else
1220       {
1221         if (!lst_empty_p (a))
1222           VEC_safe_push (lst_p, heap, seq, copy_lst (a));
1223         if (!lst_empty_p (b))
1224           VEC_safe_push (lst_p, heap, seq, copy_lst (b));
1225         if (!lst_empty_p (c))
1226           VEC_safe_push (lst_p, heap, seq, copy_lst (c));
1227       }
1228
1229   return new_lst_loop (seq);
1230 }
1231
1232 /* Moves LST before LOOP if BEFORE is true, and after the LOOP if
1233    BEFORE is false.  */
1234
1235 static inline void
1236 lst_distribute_lst (lst_p loop, lst_p lst, bool before)
1237 {
1238   int loop_depth = lst_depth (loop);
1239   int depth = lst_depth (lst);
1240   int nb_loops = depth - loop_depth;
1241
1242   gcc_assert (lst && loop && LST_LOOP_P (loop) && nb_loops > 0);
1243
1244   lst_remove_from_sequence (lst);
1245   lst_insert_in_sequence (lst_create_nest (nb_loops, lst), loop, before);
1246 }
1247
1248 /* Removes from LOOP all the statements before/after and including PBB
1249    if BEFORE is true/false.  Returns the negation of BEFORE when the
1250    statement PBB has been found.  */
1251
1252 static inline bool
1253 lst_remove_all_before_including_pbb (lst_p loop, poly_bb_p pbb, bool before)
1254 {
1255   int i;
1256   lst_p l;
1257
1258   if (!loop || !LST_LOOP_P (loop))
1259     return before;
1260
1261   for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l);)
1262     if (LST_LOOP_P (l))
1263       {
1264         before = lst_remove_all_before_including_pbb (l, pbb, before);
1265
1266         if (VEC_length (lst_p, LST_SEQ (l)) == 0)
1267           {
1268             VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1269             free_lst (l);
1270           }
1271         else
1272           i++;
1273       }
1274     else
1275       {
1276         if (before)
1277           {
1278             if (LST_PBB (l) == pbb)
1279               before = false;
1280
1281             VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1282             free_lst (l);
1283           }
1284         else if (LST_PBB (l) == pbb)
1285           {
1286             before = true;
1287             VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1288             free_lst (l);
1289           }
1290         else
1291           i++;
1292       }
1293
1294   return before;
1295 }
1296
1297 /* Removes from LOOP all the statements before/after and excluding PBB
1298    if BEFORE is true/false; Returns the negation of BEFORE when the
1299    statement PBB has been found.  */
1300
1301 static inline bool
1302 lst_remove_all_before_excluding_pbb (lst_p loop, poly_bb_p pbb, bool before)
1303 {
1304   int i;
1305   lst_p l;
1306
1307   if (!loop || !LST_LOOP_P (loop))
1308     return before;
1309
1310   for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l);)
1311     if (LST_LOOP_P (l))
1312       {
1313         before = lst_remove_all_before_excluding_pbb (l, pbb, before);
1314
1315         if (VEC_length (lst_p, LST_SEQ (l)) == 0)
1316           {
1317             VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1318             free_lst (l);
1319             continue;
1320           }
1321
1322         i++;
1323       }
1324     else
1325       {
1326         if (before && LST_PBB (l) != pbb)
1327           {
1328             VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1329             free_lst (l);
1330             continue;
1331           }
1332
1333         i++;
1334
1335         if (LST_PBB (l) == pbb)
1336           before = before ? false : true;
1337       }
1338
1339   return before;
1340 }
1341
1342 /* A SCOP is a Static Control Part of the program, simple enough to be
1343    represented in polyhedral form.  */
1344 struct scop
1345 {
1346   /* A SCOP is defined as a SESE region.  */
1347   void *region;
1348
1349   /* Number of parameters in SCoP.  */
1350   graphite_dim_t nb_params;
1351
1352   /* All the basic blocks in this scop that contain memory references
1353      and that will be represented as statements in the polyhedral
1354      representation.  */
1355   VEC (poly_bb_p, heap) *bbs;
1356
1357   /* Original, transformed and saved schedules.  */
1358   lst_p original_schedule, transformed_schedule, saved_schedule;
1359
1360   /* The context describes known restrictions concerning the parameters
1361      and relations in between the parameters.
1362
1363   void f (int8_t a, uint_16_t b) {
1364     c = 2 a + b;
1365     ...
1366   }
1367
1368   Here we can add these restrictions to the context:
1369
1370   -128 >= a >= 127
1371      0 >= b >= 65,535
1372      c = 2a + b  */
1373   isl_set *context;
1374
1375   /* The context used internally by ISL.  */
1376   isl_ctx *ctx;
1377
1378   /* The original dependence relations:
1379      RAW are read after write dependences,
1380      WAR are write after read dependences,
1381      WAW are write after write dependences.  */
1382   isl_union_map *must_raw, *may_raw, *must_raw_no_source, *may_raw_no_source,
1383     *must_war, *may_war, *must_war_no_source, *may_war_no_source,
1384     *must_waw, *may_waw, *must_waw_no_source, *may_waw_no_source;
1385
1386   /* A hashtable of the data dependence relations for the original
1387      scattering.  */
1388   htab_t original_pddrs;
1389
1390   /* True when the scop has been converted to its polyhedral
1391      representation.  */
1392   bool poly_scop_p;
1393 };
1394
1395 #define SCOP_BBS(S) (S->bbs)
1396 #define SCOP_REGION(S) ((sese) S->region)
1397 #define SCOP_CONTEXT(S) (NULL)
1398 #define SCOP_ORIGINAL_PDDRS(S) (S->original_pddrs)
1399 #define SCOP_ORIGINAL_SCHEDULE(S) (S->original_schedule)
1400 #define SCOP_TRANSFORMED_SCHEDULE(S) (S->transformed_schedule)
1401 #define SCOP_SAVED_SCHEDULE(S) (S->saved_schedule)
1402 #define POLY_SCOP_P(S) (S->poly_scop_p)
1403
1404 extern scop_p new_scop (void *);
1405 extern void free_scop (scop_p);
1406 extern void free_scops (VEC (scop_p, heap) *);
1407 extern void print_generated_program (FILE *, scop_p);
1408 extern void debug_generated_program (scop_p);
1409 extern void print_scattering_function (FILE *, poly_bb_p, int);
1410 extern void print_scattering_functions (FILE *, scop_p, int);
1411 extern void debug_scattering_function (poly_bb_p, int);
1412 extern void debug_scattering_functions (scop_p, int);
1413 extern int scop_max_loop_depth (scop_p);
1414 extern int unify_scattering_dimensions (scop_p);
1415 extern bool apply_poly_transforms (scop_p);
1416 extern bool graphite_legal_transform (scop_p);
1417 extern void cloog_checksum (scop_p);
1418
1419 /* Set the region of SCOP to REGION.  */
1420
1421 static inline void
1422 scop_set_region (scop_p scop, void *region)
1423 {
1424   scop->region = region;
1425 }
1426
1427 /* Returns the number of parameters for SCOP.  */
1428
1429 static inline graphite_dim_t
1430 scop_nb_params (scop_p scop)
1431 {
1432   return scop->nb_params;
1433 }
1434
1435 /* Set the number of params of SCOP to NB_PARAMS.  */
1436
1437 static inline void
1438 scop_set_nb_params (scop_p scop, graphite_dim_t nb_params)
1439 {
1440   scop->nb_params = nb_params;
1441 }
1442
1443 /* Allocates a new empty poly_scattering structure.  */
1444
1445 static inline poly_scattering_p
1446 poly_scattering_new (void)
1447 {
1448   poly_scattering_p res = XNEW (struct poly_scattering);
1449
1450   res->nb_local_variables = 0;
1451   res->nb_scattering = 0;
1452   return res;
1453 }
1454
1455 /* Free a poly_scattering structure.  */
1456
1457 static inline void
1458 poly_scattering_free (poly_scattering_p s)
1459 {
1460   free (s);
1461 }
1462
1463 /* Copies S and return a new scattering.  */
1464
1465 static inline poly_scattering_p
1466 poly_scattering_copy (poly_scattering_p s)
1467 {
1468   poly_scattering_p res = poly_scattering_new ();
1469
1470   res->nb_local_variables = s->nb_local_variables;
1471   res->nb_scattering = s->nb_scattering;
1472   return res;
1473 }
1474
1475 /* Saves the transformed scattering of PBB.  */
1476
1477 static inline void
1478 store_scattering_pbb (poly_bb_p pbb)
1479 {
1480   isl_map_free (pbb->saved);
1481   pbb->saved = isl_map_copy (pbb->transformed);
1482 }
1483
1484 /* Stores the SCOP_TRANSFORMED_SCHEDULE to SCOP_SAVED_SCHEDULE.  */
1485
1486 static inline void
1487 store_lst_schedule (scop_p scop)
1488 {
1489   if (SCOP_SAVED_SCHEDULE (scop))
1490     free_lst (SCOP_SAVED_SCHEDULE (scop));
1491
1492   SCOP_SAVED_SCHEDULE (scop) = copy_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
1493 }
1494
1495 /* Restores the SCOP_TRANSFORMED_SCHEDULE from SCOP_SAVED_SCHEDULE.  */
1496
1497 static inline void
1498 restore_lst_schedule (scop_p scop)
1499 {
1500   if (SCOP_TRANSFORMED_SCHEDULE (scop))
1501     free_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
1502
1503   SCOP_TRANSFORMED_SCHEDULE (scop) = copy_lst (SCOP_SAVED_SCHEDULE (scop));
1504 }
1505
1506 /* Saves the scattering for all the pbbs in the SCOP.  */
1507
1508 static inline void
1509 store_scattering (scop_p scop)
1510 {
1511   int i;
1512   poly_bb_p pbb;
1513
1514   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1515     store_scattering_pbb (pbb);
1516
1517   store_lst_schedule (scop);
1518 }
1519
1520 /* Restores the scattering of PBB.  */
1521
1522 static inline void
1523 restore_scattering_pbb (poly_bb_p pbb)
1524 {
1525   gcc_assert (pbb->saved);
1526
1527   isl_map_free (pbb->transformed);
1528   pbb->transformed = isl_map_copy (pbb->saved);
1529 }
1530
1531 /* Restores the scattering for all the pbbs in the SCOP.  */
1532
1533 static inline void
1534 restore_scattering (scop_p scop)
1535 {
1536   int i;
1537   poly_bb_p pbb;
1538
1539   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1540     restore_scattering_pbb (pbb);
1541
1542   restore_lst_schedule (scop);
1543 }
1544
1545 bool graphite_legal_transform (scop_p);
1546 poly_bb_p find_pbb_via_hash (htab_t, basic_block);
1547 bool loop_is_parallel_p (loop_p, htab_t, int);
1548 scop_p get_loop_body_pbbs (loop_p, htab_t, VEC (poly_bb_p, heap) **);
1549 isl_map *reverse_loop_at_level (poly_bb_p, int);
1550 isl_union_map *reverse_loop_for_pbbs (scop_p, VEC (poly_bb_p, heap) *, int);
1551 __isl_give isl_union_map *extend_schedule (__isl_take isl_union_map *);
1552
1553
1554 void
1555 compute_deps (scop_p scop, VEC (poly_bb_p, heap) *pbbs,
1556               isl_union_map **must_raw,
1557               isl_union_map **may_raw,
1558               isl_union_map **must_raw_no_source,
1559               isl_union_map **may_raw_no_source,
1560               isl_union_map **must_war,
1561               isl_union_map **may_war,
1562               isl_union_map **must_war_no_source,
1563               isl_union_map **may_war_no_source,
1564               isl_union_map **must_waw,
1565               isl_union_map **may_waw,
1566               isl_union_map **must_waw_no_source,
1567               isl_union_map **may_waw_no_source);
1568
1569 #endif