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