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 void pbb_number_of_iterations_at_time (poly_bb_p, graphite_dim_t, mpz_t);
 413 extern void debug_gmp_value (mpz_t);
 414
 415 /* Return the number of write data references in PBB.  */
 416
 417 static inline int
 418 number_of_write_pdrs (poly_bb_p pbb)
 419 {
 420   int res = 0;
 421   int i;
 422   poly_dr_p pdr;
 423
 424   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
 425     if (PDR_TYPE (pdr) == PDR_WRITE)
 426       res++;
 427
 428   return res;
 429 }
 430
 431 /* Returns a gimple_bb from BB.  */
 432
 433 static inline gimple_bb_p
 434 gbb_from_bb (basic_block bb)
 435 {
 436   return (gimple_bb_p) bb->aux;
 437 }
 438
 439 /* The poly_bb of the BB.  */
 440
 441 static inline poly_bb_p
 442 pbb_from_bb (basic_block bb)
 443 {
 444   return GBB_PBB (gbb_from_bb (bb));
 445 }
 446
 447 /* The basic block of the PBB.  */
 448
 449 static inline basic_block
 450 pbb_bb (poly_bb_p pbb)
 451 {
 452   return GBB_BB (PBB_BLACK_BOX (pbb));
 453 }
 454
 455 /* The index of the PBB.  */
 456
 457 static inline int
 458 pbb_index (poly_bb_p pbb)
 459 {
 460   return pbb_bb (pbb)->index;
 461 }
 462
 463 /* The loop of the PBB.  */
 464
 465 static inline loop_p
 466 pbb_loop (poly_bb_p pbb)
 467 {
 468   return gbb_loop (PBB_BLACK_BOX (pbb));
 469 }
 470
 471 /* The scop that contains the PDR.  */
 472
 473 static inline scop_p
 474 pdr_scop (poly_dr_p pdr)
 475 {
 476   return PBB_SCOP (PDR_PBB (pdr));
 477 }
 478
 479 /* Set black box of PBB to BLACKBOX.  */
 480
 481 static inline void
 482 pbb_set_black_box (poly_bb_p pbb, void *black_box)
 483 {
 484   pbb->black_box = black_box;
 485 }
 486
 487 /* The number of loops around PBB: the dimension of the iteration
 488    domain.  */
 489
 490 static inline graphite_dim_t
 491 pbb_dim_iter_domain (const struct poly_bb *pbb)
 492 {
 493   return isl_set_dim (pbb->domain, isl_dim_set);
 494 }
 495
 496 /* The number of params defined in PBB.  */
 497
 498 static inline graphite_dim_t
 499 pbb_nb_params (const struct poly_bb *pbb)
 500 {
 501   scop_p scop = PBB_SCOP (pbb);
 502
 503   return scop_nb_params (scop);
 504 }
 505
 506 /* The number of scattering dimensions in the SCATTERING polyhedron
 507    of a PBB for a given SCOP.  */
 508
 509 static inline graphite_dim_t
 510 pbb_nb_scattering_orig (const struct poly_bb *pbb)
 511 {
 512   return 2 * pbb_dim_iter_domain (pbb) + 1;
 513 }
 514
 515 /* The number of scattering dimensions in PBB.  */
 516
 517 static inline graphite_dim_t
 518 pbb_nb_scattering_transform (const struct poly_bb *pbb)
 519 {
 520   return PBB_NB_SCATTERING_TRANSFORM (pbb);
 521 }
 522
 523 /* The number of dynamic scattering dimensions in PBB.  */
 524
 525 static inline graphite_dim_t
 526 pbb_nb_dynamic_scattering_transform (const struct poly_bb *pbb)
 527 {
 528   /* This function requires the 2d + 1 scattering format to be
 529      invariant during all transformations.  */
 530   gcc_assert (PBB_NB_SCATTERING_TRANSFORM (pbb) % 2);
 531   return PBB_NB_SCATTERING_TRANSFORM (pbb) / 2;
 532 }
 533
 534 /* Returns the number of local variables used in the transformed
 535    scattering polyhedron of PBB.  */
 536
 537 static inline graphite_dim_t
 538 pbb_nb_local_vars (const struct poly_bb *pbb ATTRIBUTE_UNUSED)
 539 {
 540   /* For now we do not have any local variables, as we do not do strip
 541      mining for example.  */
 542   return PBB_NB_LOCAL_VARIABLES (pbb);
 543 }
 544
 545 /* The dimension in the domain of PBB containing the iterator ITER.  */
 546
 547 static inline graphite_dim_t
 548 pbb_iterator_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t iter)
 549 {
 550   return iter;
 551 }
 552
 553 /* The dimension in the domain of PBB containing the iterator ITER.  */
 554
 555 static inline graphite_dim_t
 556 pbb_parameter_dim (poly_bb_p pbb, graphite_dim_t param)
 557 {
 558   return param
 559     + pbb_dim_iter_domain (pbb);
 560 }
 561
 562 /* The dimension in the original scattering polyhedron of PBB
 563    containing the scattering iterator SCATTER.  */
 564
 565 static inline graphite_dim_t
 566 psco_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t scatter)
 567 {
 568   gcc_assert (scatter < pbb_nb_scattering_orig (pbb));
 569   return scatter;
 570 }
 571
 572 /* The dimension in the transformed scattering polyhedron of PBB
 573    containing the scattering iterator SCATTER.  */
 574
 575 static inline graphite_dim_t
 576 psct_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t scatter)
 577 {
 578   gcc_assert (scatter <= pbb_nb_scattering_transform (pbb));
 579   return scatter;
 580 }
 581
 582 /* The dimension in the transformed scattering polyhedron of PBB of
 583    the local variable LV.  */
 584
 585 static inline graphite_dim_t
 586 psct_local_var_dim (poly_bb_p pbb, graphite_dim_t lv)
 587 {
 588   gcc_assert (lv <= pbb_nb_local_vars (pbb));
 589   return lv + pbb_nb_scattering_transform (pbb);
 590 }
 591
 592 /* The dimension in the original scattering polyhedron of PBB
 593    containing the loop iterator ITER.  */
 594
 595 static inline graphite_dim_t
 596 psco_iterator_dim (poly_bb_p pbb, graphite_dim_t iter)
 597 {
 598   gcc_assert (iter < pbb_dim_iter_domain (pbb));
 599   return iter + pbb_nb_scattering_orig (pbb);
 600 }
 601
 602 /* The dimension in the transformed scattering polyhedron of PBB
 603    containing the loop iterator ITER.  */
 604
 605 static inline graphite_dim_t
 606 psct_iterator_dim (poly_bb_p pbb, graphite_dim_t iter)
 607 {
 608   gcc_assert (iter < pbb_dim_iter_domain (pbb));
 609   return iter
 610     + pbb_nb_scattering_transform (pbb)
 611     + pbb_nb_local_vars (pbb);
 612 }
 613
 614 /* The dimension in the original scattering polyhedron of PBB
 615    containing parameter PARAM.  */
 616
 617 static inline graphite_dim_t
 618 psco_parameter_dim (poly_bb_p pbb, graphite_dim_t param)
 619 {
 620   gcc_assert (param < pbb_nb_params (pbb));
 621   return param
 622     + pbb_nb_scattering_orig (pbb)
 623     + pbb_dim_iter_domain (pbb);
 624 }
 625
 626 /* The dimension in the transformed scattering polyhedron of PBB
 627    containing parameter PARAM.  */
 628
 629 static inline graphite_dim_t
 630 psct_parameter_dim (poly_bb_p pbb, graphite_dim_t param)
 631 {
 632   gcc_assert (param < pbb_nb_params (pbb));
 633   return param
 634     + pbb_nb_scattering_transform (pbb)
 635     + pbb_nb_local_vars (pbb)
 636     + pbb_dim_iter_domain (pbb);
 637 }
 638
 639 /* The scattering dimension of PBB corresponding to the dynamic level
 640    LEVEL.  */
 641
 642 static inline graphite_dim_t
 643 psct_dynamic_dim (poly_bb_p pbb, graphite_dim_t level)
 644 {
 645   graphite_dim_t result = 1 + 2 * level;
 646
 647   gcc_assert (result < pbb_nb_scattering_transform (pbb));
 648   return result;
 649 }
 650
 651 /* The scattering dimension of PBB corresponding to the static
 652    sequence of the loop level LEVEL.  */
 653
 654 static inline graphite_dim_t
 655 psct_static_dim (poly_bb_p pbb, graphite_dim_t level)
 656 {
 657   graphite_dim_t result = 2 * level;
 658
 659   gcc_assert (result < pbb_nb_scattering_transform (pbb));
 660   return result;
 661 }
 662
 663 /* Adds to the transformed scattering polyhedron of PBB a new local
 664    variable and returns its index.  */
 665
 666 static inline graphite_dim_t
 667 psct_add_local_variable (poly_bb_p pbb ATTRIBUTE_UNUSED)
 668 {
 669   gcc_unreachable ();
 670   return 0;
 671 }
 672
 673 typedef struct lst *lst_p;
 674 DEF_VEC_P(lst_p);
 675 DEF_VEC_ALLOC_P (lst_p, heap);
 676
 677 /* Loops and Statements Tree.  */
 678 struct lst {
 679
 680   /* LOOP_P is true when an LST node is a loop.  */
 681   bool loop_p;
 682
 683   /* A pointer to the loop that contains this node.  */
 684   lst_p loop_father;
 685
 686   /* The sum of all the memory strides for an LST loop.  */
 687   mpz_t memory_strides;
 688
 689   /* Loop nodes contain a sequence SEQ of LST nodes, statements
 690      contain a pointer to their polyhedral representation PBB.  */
 691   union {
 692     poly_bb_p pbb;
 693     VEC (lst_p, heap) *seq;
 694   } node;
 695 };
 696
 697 #define LST_LOOP_P(LST) ((LST)->loop_p)
 698 #define LST_LOOP_FATHER(LST) ((LST)->loop_father)
 699 #define LST_PBB(LST) ((LST)->node.pbb)
 700 #define LST_SEQ(LST) ((LST)->node.seq)
 701 #define LST_LOOP_MEMORY_STRIDES(LST) ((LST)->memory_strides)
 702
 703 void scop_to_lst (scop_p);
 704 void print_lst (FILE *, lst_p, int);
 705 void debug_lst (lst_p);
 706 void dot_lst (lst_p);
 707
 708 /* Creates a new LST loop with SEQ.  */
 709
 710 static inline lst_p
 711 new_lst_loop (VEC (lst_p, heap) *seq)
 712 {
 713   lst_p lst = XNEW (struct lst);
 714   int i;
 715   lst_p l;
 716
 717   LST_LOOP_P (lst) = true;
 718   LST_SEQ (lst) = seq;
 719   LST_LOOP_FATHER (lst) = NULL;
 720   mpz_init (LST_LOOP_MEMORY_STRIDES (lst));
 721   mpz_set_si (LST_LOOP_MEMORY_STRIDES (lst), -1);
 722
 723   for (i = 0; VEC_iterate (lst_p, seq, i, l); i++)
 724     LST_LOOP_FATHER (l) = lst;
 725
 726   return lst;
 727 }
 728
 729 /* Creates a new LST statement with PBB.  */
 730
 731 static inline lst_p
 732 new_lst_stmt (poly_bb_p pbb)
 733 {
 734   lst_p lst = XNEW (struct lst);
 735
 736   LST_LOOP_P (lst) = false;
 737   LST_PBB (lst) = pbb;
 738   LST_LOOP_FATHER (lst) = NULL;
 739   return lst;
 740 }
 741
 742 /* Frees the memory used by LST.  */
 743
 744 static inline void
 745 free_lst (lst_p lst)
 746 {
 747   if (!lst)
 748     return;
 749
 750   if (LST_LOOP_P (lst))
 751     {
 752       int i;
 753       lst_p l;
 754
 755       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 756         free_lst (l);
 757
 758       mpz_clear (LST_LOOP_MEMORY_STRIDES (lst));
 759       VEC_free (lst_p, heap, LST_SEQ (lst));
 760     }
 761
 762   free (lst);
 763 }
 764
 765 /* Returns a copy of LST.  */
 766
 767 static inline lst_p
 768 copy_lst (lst_p lst)
 769 {
 770   if (!lst)
 771     return NULL;
 772
 773   if (LST_LOOP_P (lst))
 774     {
 775       int i;
 776       lst_p l;
 777       VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
 778
 779       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 780         VEC_safe_push (lst_p, heap, seq, 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, heap) *seq = VEC_alloc (lst_p, heap, 1);
 794   lst_p l = new_lst_loop (LST_SEQ (lst));
 795
 796   gcc_assert (LST_LOOP_P (lst));
 797
 798   LST_LOOP_FATHER (l) = lst;
 799   VEC_quick_push (lst_p, seq, l);
 800   LST_SEQ (lst) = seq;
 801 }
 802
 803 /* Returns the loop depth of LST.  */
 804
 805 static inline int
 806 lst_depth (lst_p lst)
 807 {
 808   if (!lst)
 809     return -2;
 810
 811   /* The depth of the outermost "fake" loop is -1.  This outermost
 812      loop does not have a loop father and it is just a container, as
 813      in the loop representation of GCC.  */
 814   if (!LST_LOOP_FATHER (lst))
 815     return -1;
 816
 817   return lst_depth (LST_LOOP_FATHER (lst)) + 1;
 818 }
 819
 820 /* Returns the Dewey number for LST.  */
 821
 822 static inline int
 823 lst_dewey_number (lst_p lst)
 824 {
 825   int i;
 826   lst_p l;
 827
 828   if (!lst)
 829     return -1;
 830
 831   if (!LST_LOOP_FATHER (lst))
 832     return 0;
 833
 834   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (LST_LOOP_FATHER (lst)), i, l)
 835     if (l == lst)
 836       return i;
 837
 838   return -1;
 839 }
 840
 841 /* Returns the Dewey number of LST at depth DEPTH.  */
 842
 843 static inline int
 844 lst_dewey_number_at_depth (lst_p lst, int depth)
 845 {
 846   gcc_assert (lst && depth >= 0 && lst_depth (lst) <= depth);
 847
 848   if (lst_depth (lst) == depth)
 849     return lst_dewey_number (lst);
 850
 851   return lst_dewey_number_at_depth (LST_LOOP_FATHER (lst), depth);
 852 }
 853
 854 /* Returns the predecessor of LST in the sequence of its loop father.
 855    Returns NULL if LST is the first statement in the sequence.  */
 856
 857 static inline lst_p
 858 lst_pred (lst_p lst)
 859 {
 860   int dewey;
 861   lst_p father;
 862
 863   if (!lst || !LST_LOOP_FATHER (lst))
 864     return NULL;
 865
 866   dewey = lst_dewey_number (lst);
 867   if (dewey == 0)
 868     return NULL;
 869
 870   father = LST_LOOP_FATHER (lst);
 871   return VEC_index (lst_p, LST_SEQ (father), dewey - 1);
 872 }
 873
 874 /* Returns the successor of LST in the sequence of its loop father.
 875    Returns NULL if there is none.  */
 876
 877 static inline lst_p
 878 lst_succ (lst_p lst)
 879 {
 880   int dewey;
 881   lst_p father;
 882
 883   if (!lst || !LST_LOOP_FATHER (lst))
 884     return NULL;
 885
 886   dewey = lst_dewey_number (lst);
 887   father = LST_LOOP_FATHER (lst);
 888
 889   if (VEC_length (lst_p, LST_SEQ (father)) == (unsigned) dewey + 1)
 890     return NULL;
 891
 892   return VEC_index (lst_p, LST_SEQ (father), dewey + 1);
 893 }
 894
 895
 896 /* Return the LST node corresponding to PBB.  */
 897
 898 static inline lst_p
 899 lst_find_pbb (lst_p lst, poly_bb_p pbb)
 900 {
 901   int i;
 902   lst_p l;
 903
 904   if (!lst)
 905     return NULL;
 906
 907   if (!LST_LOOP_P (lst))
 908     return (pbb == LST_PBB (lst)) ? lst : NULL;
 909
 910   for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 911     {
 912       lst_p res = lst_find_pbb (l, pbb);
 913       if (res)
 914         return res;
 915     }
 916
 917   return NULL;
 918 }
 919
 920 /* Return the LST node corresponding to the loop around STMT at depth
 921    LOOP_DEPTH.  */
 922
 923 static inline lst_p
 924 find_lst_loop (lst_p stmt, int loop_depth)
 925 {
 926   lst_p loop = LST_LOOP_FATHER (stmt);
 927
 928   gcc_assert (loop_depth >= 0);
 929
 930   while (loop_depth < lst_depth (loop))
 931     loop = LST_LOOP_FATHER (loop);
 932
 933   return loop;
 934 }
 935
 936 /* Return the first LST representing a PBB statement in LST.  */
 937
 938 static inline lst_p
 939 lst_find_first_pbb (lst_p lst)
 940 {
 941   int i;
 942   lst_p l;
 943
 944   if (!lst)
 945     return NULL;
 946
 947   if (!LST_LOOP_P (lst))
 948     return lst;
 949
 950   for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 951     {
 952       lst_p res = lst_find_first_pbb (l);
 953       if (res)
 954         return res;
 955     }
 956
 957   return NULL;
 958 }
 959
 960 /* Returns true when LST is a loop that does not contain
 961    statements.  */
 962
 963 static inline bool
 964 lst_empty_p (lst_p lst)
 965 {
 966   return !lst_find_first_pbb (lst);
 967 }
 968
 969 /* Return the last LST representing a PBB statement in LST.  */
 970
 971 static inline lst_p
 972 lst_find_last_pbb (lst_p lst)
 973 {
 974   int i;
 975   lst_p l, res = NULL;
 976
 977   if (!lst)
 978     return NULL;
 979
 980   if (!LST_LOOP_P (lst))
 981     return lst;
 982
 983   for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 984     {
 985       lst_p last = lst_find_last_pbb (l);
 986
 987       if (last)
 988         res = last;
 989     }
 990
 991   gcc_assert (res);
 992   return res;
 993 }
 994
 995 /* Returns true if LOOP contains LST, in other words, if LST is nested
 996    in LOOP.  */
 997
 998 static inline bool
 999 lst_contains_p (lst_p loop, lst_p lst)
1000 {
1001   if (!loop || !lst || !LST_LOOP_P (loop))
1002     return false;
1003
1004   if (loop == lst)
1005     return true;
1006
1007   return lst_contains_p (loop, LST_LOOP_FATHER (lst));
1008 }
1009
1010 /* Returns true if LOOP contains PBB, in other words, if PBB is nested
1011    in LOOP.  */
1012
1013 static inline bool
1014 lst_contains_pbb (lst_p loop, poly_bb_p pbb)
1015 {
1016   return lst_find_pbb (loop, pbb) ? true : false;
1017 }
1018
1019 /* Creates a loop nest of depth NB_LOOPS containing LST.  */
1020
1021 static inline lst_p
1022 lst_create_nest (int nb_loops, lst_p lst)
1023 {
1024   lst_p res, loop;
1025   VEC (lst_p, heap) *seq;
1026
1027   if (nb_loops == 0)
1028     return lst;
1029
1030   seq = VEC_alloc (lst_p, heap, 1);
1031   loop = lst_create_nest (nb_loops - 1, lst);
1032   VEC_quick_push (lst_p, seq, loop);
1033   res = new_lst_loop (seq);
1034   LST_LOOP_FATHER (loop) = res;
1035
1036   return res;
1037 }
1038
1039 /* Removes LST from the sequence of statements of its loop father.  */
1040
1041 static inline void
1042 lst_remove_from_sequence (lst_p lst)
1043 {
1044   lst_p father = LST_LOOP_FATHER (lst);
1045   int dewey = lst_dewey_number (lst);
1046
1047   gcc_assert (lst && father && dewey >= 0);
1048
1049   VEC_ordered_remove (lst_p, LST_SEQ (father), dewey);
1050   LST_LOOP_FATHER (lst) = NULL;
1051 }
1052
1053 /* Removes the loop LST and inline its body in the father loop.  */
1054
1055 static inline void
1056 lst_remove_loop_and_inline_stmts_in_loop_father (lst_p lst)
1057 {
1058   lst_p l, father = LST_LOOP_FATHER (lst);
1059   int i, dewey = lst_dewey_number (lst);
1060
1061   gcc_assert (lst && father && dewey >= 0);
1062
1063   VEC_ordered_remove (lst_p, LST_SEQ (father), dewey);
1064   LST_LOOP_FATHER (lst) = NULL;
1065
1066   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
1067     {
1068       VEC_safe_insert (lst_p, heap, LST_SEQ (father), dewey + i, l);
1069       LST_LOOP_FATHER (l) = father;
1070     }
1071 }
1072
1073 /* Sets NITER to the upper bound approximation of the number of
1074    iterations of loop LST.  */
1075
1076 static inline void
1077 lst_niter_for_loop (lst_p lst, mpz_t niter)
1078 {
1079   int depth = lst_depth (lst);
1080   poly_bb_p pbb = LST_PBB (lst_find_first_pbb (lst));
1081
1082   gcc_assert (LST_LOOP_P (lst));
1083   pbb_number_of_iterations_at_time (pbb, psct_dynamic_dim (pbb, depth), niter);
1084 }
1085
1086 /* Updates the scattering of PBB to be at the DEWEY number in the loop
1087    at depth LEVEL.  */
1088
1089 static inline void
1090 pbb_update_scattering (poly_bb_p pbb, graphite_dim_t level, int dewey)
1091 {
1092   graphite_dim_t sched = psct_static_dim (pbb, level);
1093   isl_space *d = isl_map_get_space (pbb->transformed);
1094   isl_space *d1 = isl_space_range (d);
1095   unsigned i, n = isl_space_dim (d1, isl_dim_out);
1096   isl_space *d2 = isl_space_add_dims (d1, isl_dim_in, n);
1097   isl_map *x = isl_map_universe (d2);
1098
1099   x = isl_map_fix_si (x, isl_dim_out, sched, dewey);
1100
1101   for (i = 0; i < n; i++)
1102     if (i != sched)
1103       x = isl_map_equate (x, isl_dim_in, i, isl_dim_out, i);
1104
1105   pbb->transformed = isl_map_apply_range (pbb->transformed, x);
1106 }
1107
1108 /* Updates the scattering of all the PBBs under LST to be at the DEWEY
1109    number in the loop at depth LEVEL.  */
1110
1111 static inline void
1112 lst_update_scattering_under (lst_p lst, int level, int dewey)
1113 {
1114   int i;
1115   lst_p l;
1116
1117   gcc_assert (lst && level >= 0 && dewey >= 0);
1118
1119   if (LST_LOOP_P (lst))
1120     for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
1121       lst_update_scattering_under (l, level, dewey);
1122   else
1123     pbb_update_scattering (LST_PBB (lst), level, dewey);
1124 }
1125
1126 /* Updates the all the scattering levels of all the PBBs under
1127    LST.  */
1128
1129 static inline void
1130 lst_update_scattering (lst_p lst)
1131 {
1132   int i;
1133   lst_p l;
1134
1135   if (!lst)
1136     return;
1137
1138   if (LST_LOOP_FATHER (lst))
1139     {
1140       lst_p father = LST_LOOP_FATHER (lst);
1141       int dewey = lst_dewey_number (lst);
1142       int level = lst_depth (lst);
1143
1144       gcc_assert (lst && father && dewey >= 0 && level >= 0);
1145
1146       for (i = dewey; VEC_iterate (lst_p, LST_SEQ (father), i, l); i++)
1147         lst_update_scattering_under (l, level, i);
1148     }
1149
1150   if (LST_LOOP_P (lst))
1151     for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
1152       lst_update_scattering (l);
1153 }
1154
1155 /* Inserts LST1 before LST2 if BEFORE is true; inserts LST1 after LST2
1156    if BEFORE is false.  */
1157
1158 static inline void
1159 lst_insert_in_sequence (lst_p lst1, lst_p lst2, bool before)
1160 {
1161   lst_p father;
1162   int dewey;
1163
1164   /* Do not insert empty loops.  */
1165   if (!lst1 || lst_empty_p (lst1))
1166     return;
1167
1168   father = LST_LOOP_FATHER (lst2);
1169   dewey = lst_dewey_number (lst2);
1170
1171   gcc_assert (lst2 && father && dewey >= 0);
1172
1173   VEC_safe_insert (lst_p, heap, LST_SEQ (father), before ? dewey : dewey + 1,
1174                    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   VEC_replace (lst_p, 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, heap) *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 = VEC_alloc (lst_p, heap, 5);
1214
1215   for (i = 0; VEC_iterate (lst_p, LST_SEQ (root), i, l); i++)
1216     if (l != lst)
1217       VEC_safe_push (lst_p, heap, seq, lst_substitute_3 (l, lst, a, b, c));
1218     else
1219       {
1220         if (!lst_empty_p (a))
1221           VEC_safe_push (lst_p, heap, seq, copy_lst (a));
1222         if (!lst_empty_p (b))
1223           VEC_safe_push (lst_p, heap, seq, copy_lst (b));
1224         if (!lst_empty_p (c))
1225           VEC_safe_push (lst_p, heap, seq, 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; VEC_iterate (lst_p, LST_SEQ (loop), i, l);)
1261     if (LST_LOOP_P (l))
1262       {
1263         before = lst_remove_all_before_including_pbb (l, pbb, before);
1264
1265         if (VEC_length (lst_p, LST_SEQ (l)) == 0)
1266           {
1267             VEC_ordered_remove (lst_p, LST_SEQ (loop), 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             VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1281             free_lst (l);
1282           }
1283         else if (LST_PBB (l) == pbb)
1284           {
1285             before = true;
1286             VEC_ordered_remove (lst_p, LST_SEQ (loop), 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; VEC_iterate (lst_p, LST_SEQ (loop), i, l);)
1310     if (LST_LOOP_P (l))
1311       {
1312         before = lst_remove_all_before_excluding_pbb (l, pbb, before);
1313
1314         if (VEC_length (lst_p, LST_SEQ (l)) == 0)
1315           {
1316             VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1317             free_lst (l);
1318             continue;
1319           }
1320
1321         i++;
1322       }
1323     else
1324       {
1325         if (before && LST_PBB (l) != pbb)
1326           {
1327             VEC_ordered_remove (lst_p, LST_SEQ (loop), 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, heap) *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   /* A hashtable of the data dependence relations for the original
1386      scattering.  */
1387   htab_t original_pddrs;
1388
1389   /* True when the scop has been converted to its polyhedral
1390      representation.  */
1391   bool poly_scop_p;
1392 };
1393
1394 #define SCOP_BBS(S) (S->bbs)
1395 #define SCOP_REGION(S) ((sese) S->region)
1396 #define SCOP_CONTEXT(S) (NULL)
1397 #define SCOP_ORIGINAL_PDDRS(S) (S->original_pddrs)
1398 #define SCOP_ORIGINAL_SCHEDULE(S) (S->original_schedule)
1399 #define SCOP_TRANSFORMED_SCHEDULE(S) (S->transformed_schedule)
1400 #define SCOP_SAVED_SCHEDULE(S) (S->saved_schedule)
1401 #define POLY_SCOP_P(S) (S->poly_scop_p)
1402
1403 extern scop_p new_scop (void *);
1404 extern void free_scop (scop_p);
1405 extern void free_scops (VEC (scop_p, heap) *);
1406 extern void print_generated_program (FILE *, scop_p);
1407 extern void debug_generated_program (scop_p);
1408 extern void print_scattering_function (FILE *, poly_bb_p, int);
1409 extern void print_scattering_functions (FILE *, scop_p, int);
1410 extern void debug_scattering_function (poly_bb_p, int);
1411 extern void debug_scattering_functions (scop_p, int);
1412 extern int scop_max_loop_depth (scop_p);
1413 extern int unify_scattering_dimensions (scop_p);
1414 extern bool apply_poly_transforms (scop_p);
1415 extern bool graphite_legal_transform (scop_p);
1416 extern void cloog_checksum (scop_p);
1417
1418 /* Set the region of SCOP to REGION.  */
1419
1420 static inline void
1421 scop_set_region (scop_p scop, void *region)
1422 {
1423   scop->region = region;
1424 }
1425
1426 /* Returns the number of parameters for SCOP.  */
1427
1428 static inline graphite_dim_t
1429 scop_nb_params (scop_p scop)
1430 {
1431   return scop->nb_params;
1432 }
1433
1434 /* Set the number of params of SCOP to NB_PARAMS.  */
1435
1436 static inline void
1437 scop_set_nb_params (scop_p scop, graphite_dim_t nb_params)
1438 {
1439   scop->nb_params = nb_params;
1440 }
1441
1442 /* Allocates a new empty poly_scattering structure.  */
1443
1444 static inline poly_scattering_p
1445 poly_scattering_new (void)
1446 {
1447   poly_scattering_p res = XNEW (struct poly_scattering);
1448
1449   res->nb_local_variables = 0;
1450   res->nb_scattering = 0;
1451   return res;
1452 }
1453
1454 /* Free a poly_scattering structure.  */
1455
1456 static inline void
1457 poly_scattering_free (poly_scattering_p s)
1458 {
1459   free (s);
1460 }
1461
1462 /* Copies S and return a new scattering.  */
1463
1464 static inline poly_scattering_p
1465 poly_scattering_copy (poly_scattering_p s)
1466 {
1467   poly_scattering_p res = poly_scattering_new ();
1468
1469   res->nb_local_variables = s->nb_local_variables;
1470   res->nb_scattering = s->nb_scattering;
1471   return res;
1472 }
1473
1474 /* Saves the transformed scattering of PBB.  */
1475
1476 static inline void
1477 store_scattering_pbb (poly_bb_p pbb)
1478 {
1479   isl_map_free (pbb->saved);
1480   pbb->saved = isl_map_copy (pbb->transformed);
1481 }
1482
1483 /* Stores the SCOP_TRANSFORMED_SCHEDULE to SCOP_SAVED_SCHEDULE.  */
1484
1485 static inline void
1486 store_lst_schedule (scop_p scop)
1487 {
1488   if (SCOP_SAVED_SCHEDULE (scop))
1489     free_lst (SCOP_SAVED_SCHEDULE (scop));
1490
1491   SCOP_SAVED_SCHEDULE (scop) = copy_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
1492 }
1493
1494 /* Restores the SCOP_TRANSFORMED_SCHEDULE from SCOP_SAVED_SCHEDULE.  */
1495
1496 static inline void
1497 restore_lst_schedule (scop_p scop)
1498 {
1499   if (SCOP_TRANSFORMED_SCHEDULE (scop))
1500     free_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
1501
1502   SCOP_TRANSFORMED_SCHEDULE (scop) = copy_lst (SCOP_SAVED_SCHEDULE (scop));
1503 }
1504
1505 /* Saves the scattering for all the pbbs in the SCOP.  */
1506
1507 static inline void
1508 store_scattering (scop_p scop)
1509 {
1510   int i;
1511   poly_bb_p pbb;
1512
1513   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1514     store_scattering_pbb (pbb);
1515
1516   store_lst_schedule (scop);
1517 }
1518
1519 /* Restores the scattering of PBB.  */
1520
1521 static inline void
1522 restore_scattering_pbb (poly_bb_p pbb)
1523 {
1524   gcc_assert (pbb->saved);
1525
1526   isl_map_free (pbb->transformed);
1527   pbb->transformed = isl_map_copy (pbb->saved);
1528 }
1529
1530 /* Restores the scattering for all the pbbs in the SCOP.  */
1531
1532 static inline void
1533 restore_scattering (scop_p scop)
1534 {
1535   int i;
1536   poly_bb_p pbb;
1537
1538   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1539     restore_scattering_pbb (pbb);
1540
1541   restore_lst_schedule (scop);
1542 }
1543
1544 bool graphite_legal_transform (scop_p);
1545 poly_bb_p find_pbb_via_hash (htab_t, basic_block);
1546 bool loop_is_parallel_p (loop_p, htab_t, int);
1547 scop_p get_loop_body_pbbs (loop_p, htab_t, VEC (poly_bb_p, heap) **);
1548 isl_map *reverse_loop_at_level (poly_bb_p, int);
1549 isl_union_map *reverse_loop_for_pbbs (scop_p, VEC (poly_bb_p, heap) *, int);
1550 __isl_give isl_union_map *extend_schedule (__isl_take isl_union_map *);
1551
1552 #endif