1 /* Graphite polyhedral representation. 2 Copyright (C) 2009, 2010 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 ppl_dimension_type 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 ppl_Pointset_Powerset_C_Polyhedron_t accesses; 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) (PDR->accesses) 199 #define PDR_BASE_OBJECT_SET(PDR) (PDR->dr_base_object_set) 200 #define PDR_NB_SUBSCRIPTS(PDR) (PDR->nb_subscripts) 201 202 void new_poly_dr (poly_bb_p, int, ppl_Pointset_Powerset_C_Polyhedron_t, 203 enum poly_dr_type, void *, graphite_dim_t); 204 void free_poly_dr (poly_dr_p); 205 void debug_pdr (poly_dr_p, int); 206 void print_pdr (FILE *, poly_dr_p, int); 207 static inline scop_p pdr_scop (poly_dr_p pdr); 208 209 /* The dimension of the PDR_ACCESSES polyhedron of PDR. */ 210 211 static inline ppl_dimension_type 212 pdr_dim (poly_dr_p pdr) 213 { 214 ppl_dimension_type dim; 215 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PDR_ACCESSES (pdr), 216 &dim); 217 return dim; 218 } 219 220 /* The dimension of the iteration domain of the scop of PDR. */ 221 222 static inline ppl_dimension_type 223 pdr_dim_iter_domain (poly_dr_p pdr) 224 { 225 return pbb_dim_iter_domain (PDR_PBB (pdr)); 226 } 227 228 /* The number of parameters of the scop of PDR. */ 229 230 static inline ppl_dimension_type 231 pdr_nb_params (poly_dr_p pdr) 232 { 233 return scop_nb_params (pdr_scop (pdr)); 234 } 235 236 /* The dimension of the alias set in PDR. */ 237 238 static inline ppl_dimension_type 239 pdr_alias_set_dim (poly_dr_p pdr) 240 { 241 poly_bb_p pbb = PDR_PBB (pdr); 242 243 return pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb); 244 } 245 246 /* The dimension in PDR containing subscript S. */ 247 248 static inline ppl_dimension_type 249 pdr_subscript_dim (poly_dr_p pdr, graphite_dim_t s) 250 { 251 poly_bb_p pbb = PDR_PBB (pdr); 252 253 return pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb) + 1 + s; 254 } 255 256 /* The dimension in PDR containing the loop iterator ITER. */ 257 258 static inline ppl_dimension_type 259 pdr_iterator_dim (poly_dr_p pdr ATTRIBUTE_UNUSED, graphite_dim_t iter) 260 { 261 return iter; 262 } 263 264 /* The dimension in PDR containing parameter PARAM. */ 265 266 static inline ppl_dimension_type 267 pdr_parameter_dim (poly_dr_p pdr, graphite_dim_t param) 268 { 269 poly_bb_p pbb = PDR_PBB (pdr); 270 271 return pbb_dim_iter_domain (pbb) + param; 272 } 273 274 /* Returns true when PDR is a "read". */ 275 276 static inline bool 277 pdr_read_p (poly_dr_p pdr) 278 { 279 return PDR_TYPE (pdr) == PDR_READ; 280 } 281 282 /* Returns true when PDR is a "write". */ 283 284 static inline bool 285 pdr_write_p (poly_dr_p pdr) 286 { 287 return PDR_TYPE (pdr) == PDR_WRITE; 288 } 289 290 /* Returns true when PDR is a "may write". */ 291 292 static inline bool 293 pdr_may_write_p (poly_dr_p pdr) 294 { 295 return PDR_TYPE (pdr) == PDR_MAY_WRITE; 296 } 297 298 /* Return true when PDR1 and PDR2 are similar data accesses: they have 299 the same base array, and the same access functions. */ 300 301 static inline bool 302 same_pdr_p (poly_dr_p pdr1, poly_dr_p pdr2) 303 { 304 return PDR_NB_SUBSCRIPTS (pdr1) == PDR_NB_SUBSCRIPTS (pdr2) 305 && PDR_BASE_OBJECT_SET (pdr1) == PDR_BASE_OBJECT_SET (pdr2); 306 } 307 308 typedef struct poly_scattering *poly_scattering_p; 309 310 struct poly_scattering 311 { 312 /* The scattering function containing the transformations: the 313 layout of this polyhedron is: T|I|G with T the transform 314 scattering, I the iteration domain, G the context parameters. */ 315 ppl_Polyhedron_t scattering; 316 317 /* The number of local variables. */ 318 int nb_local_variables; 319 320 /* The number of scattering dimensions. */ 321 int nb_scattering; 322 }; 323 324 /* POLY_BB represents a blackbox in the polyhedral model. */ 325 326 struct poly_bb 327 { 328 /* Pointer to a basic block or a statement in the compiler. */ 329 void *black_box; 330 331 /* Pointer to the SCOP containing this PBB. */ 332 scop_p scop; 333 334 /* The iteration domain of this bb. The layout of this polyhedron 335 is I|G with I the iteration domain, G the context parameters. 336 337 Example: 338 339 for (i = a - 7*b + 8; i <= 3*a + 13*b + 20; i++) 340 for (j = 2; j <= 2*i + 5; j++) 341 for (k = 0; k <= 5; k++) 342 S (i,j,k) 343 344 Loop iterators: i, j, k 345 Parameters: a, b 346 347 | i >= a - 7b + 8 348 | i <= 3a + 13b + 20 349 | j >= 2 350 | j <= 2i + 5 351 | k >= 0 352 | k <= 5 353 354 The number of variables in the DOMAIN may change and is not 355 related to the number of loops in the original code. */ 356 ppl_Pointset_Powerset_C_Polyhedron_t domain; 357 358 /* The data references we access. */ 359 VEC (poly_dr_p, heap) *drs; 360 361 /* The original scattering. */ 362 poly_scattering_p original; 363 364 /* The transformed scattering. */ 365 poly_scattering_p transformed; 366 367 /* A copy of the transformed scattering. */ 368 poly_scattering_p saved; 369 370 /* True when the PDR duplicates have already been removed. */ 371 bool pdr_duplicates_removed; 372 373 /* True when this PBB contains only a reduction statement. */ 374 bool is_reduction; 375 }; 376 377 #define PBB_BLACK_BOX(PBB) ((gimple_bb_p) PBB->black_box) 378 #define PBB_SCOP(PBB) (PBB->scop) 379 #define PBB_DOMAIN(PBB) (PBB->domain) 380 #define PBB_DRS(PBB) (PBB->drs) 381 #define PBB_ORIGINAL(PBB) (PBB->original) 382 #define PBB_ORIGINAL_SCATTERING(PBB) (PBB->original->scattering) 383 #define PBB_TRANSFORMED(PBB) (PBB->transformed) 384 #define PBB_TRANSFORMED_SCATTERING(PBB) (PBB->transformed->scattering) 385 #define PBB_SAVED(PBB) (PBB->saved) 386 #define PBB_NB_LOCAL_VARIABLES(PBB) (PBB->transformed->nb_local_variables) 387 #define PBB_NB_SCATTERING_TRANSFORM(PBB) (PBB->transformed->nb_scattering) 388 #define PBB_PDR_DUPLICATES_REMOVED(PBB) (PBB->pdr_duplicates_removed) 389 #define PBB_IS_REDUCTION(PBB) (PBB->is_reduction) 390 391 extern poly_bb_p new_poly_bb (scop_p, void *); 392 extern void free_poly_bb (poly_bb_p); 393 extern void debug_loop_vec (poly_bb_p); 394 extern void schedule_to_scattering (poly_bb_p, int); 395 extern void print_pbb_domain (FILE *, poly_bb_p, int); 396 extern void print_pbb (FILE *, poly_bb_p, int); 397 extern void print_scop_context (FILE *, scop_p, int); 398 extern void print_scop (FILE *, scop_p, int); 399 extern void print_cloog (FILE *, scop_p, int); 400 extern void debug_pbb_domain (poly_bb_p, int); 401 extern void debug_pbb (poly_bb_p, int); 402 extern void print_pdrs (FILE *, poly_bb_p, int); 403 extern void debug_pdrs (poly_bb_p, int); 404 extern void debug_scop_context (scop_p, int); 405 extern void debug_scop (scop_p, int); 406 extern void debug_cloog (scop_p, int); 407 extern void print_scop_params (FILE *, scop_p, int); 408 extern void debug_scop_params (scop_p, int); 409 extern void print_iteration_domain (FILE *, poly_bb_p, int); 410 extern void print_iteration_domains (FILE *, scop_p, int); 411 extern void debug_iteration_domain (poly_bb_p, int); 412 extern void debug_iteration_domains (scop_p, int); 413 extern int scop_do_interchange (scop_p); 414 extern int scop_do_strip_mine (scop_p, int); 415 extern bool scop_do_block (scop_p); 416 extern bool flatten_all_loops (scop_p); 417 extern void pbb_number_of_iterations_at_time (poly_bb_p, graphite_dim_t, mpz_t); 418 extern void pbb_remove_duplicate_pdrs (poly_bb_p); 419 420 /* Return the number of write data references in PBB. */ 421 422 static inline int 423 number_of_write_pdrs (poly_bb_p pbb) 424 { 425 int res = 0; 426 int i; 427 poly_dr_p pdr; 428 429 for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++) 430 if (PDR_TYPE (pdr) == PDR_WRITE) 431 res++; 432 433 return res; 434 } 435 436 /* Returns a gimple_bb from BB. */ 437 438 static inline gimple_bb_p 439 gbb_from_bb (basic_block bb) 440 { 441 return (gimple_bb_p) bb->aux; 442 } 443 444 /* The poly_bb of the BB. */ 445 446 static inline poly_bb_p 447 pbb_from_bb (basic_block bb) 448 { 449 return GBB_PBB (gbb_from_bb (bb)); 450 } 451 452 /* The basic block of the PBB. */ 453 454 static inline basic_block 455 pbb_bb (poly_bb_p pbb) 456 { 457 return GBB_BB (PBB_BLACK_BOX (pbb)); 458 } 459 460 /* The index of the PBB. */ 461 462 static inline int 463 pbb_index (poly_bb_p pbb) 464 { 465 return pbb_bb (pbb)->index; 466 } 467 468 /* The loop of the PBB. */ 469 470 static inline loop_p 471 pbb_loop (poly_bb_p pbb) 472 { 473 return gbb_loop (PBB_BLACK_BOX (pbb)); 474 } 475 476 /* The scop that contains the PDR. */ 477 478 static inline scop_p 479 pdr_scop (poly_dr_p pdr) 480 { 481 return PBB_SCOP (PDR_PBB (pdr)); 482 } 483 484 /* Set black box of PBB to BLACKBOX. */ 485 486 static inline void 487 pbb_set_black_box (poly_bb_p pbb, void *black_box) 488 { 489 pbb->black_box = black_box; 490 } 491 492 /* The number of loops around PBB: the dimension of the iteration 493 domain. */ 494 495 static inline graphite_dim_t 496 pbb_dim_iter_domain (const struct poly_bb *pbb) 497 { 498 scop_p scop = PBB_SCOP (pbb); 499 ppl_dimension_type dim; 500 501 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb), &dim); 502 return dim - scop_nb_params (scop); 503 } 504 505 /* The number of params defined in PBB. */ 506 507 static inline graphite_dim_t 508 pbb_nb_params (const struct poly_bb *pbb) 509 { 510 scop_p scop = PBB_SCOP (pbb); 511 512 return scop_nb_params (scop); 513 } 514 515 /* The number of scattering dimensions in the SCATTERING polyhedron 516 of a PBB for a given SCOP. */ 517 518 static inline graphite_dim_t 519 pbb_nb_scattering_orig (const struct poly_bb *pbb) 520 { 521 return 2 * pbb_dim_iter_domain (pbb) + 1; 522 } 523 524 /* The number of scattering dimensions in PBB. */ 525 526 static inline graphite_dim_t 527 pbb_nb_scattering_transform (const struct poly_bb *pbb) 528 { 529 return PBB_NB_SCATTERING_TRANSFORM (pbb); 530 } 531 532 /* The number of dynamic scattering dimensions in PBB. */ 533 534 static inline graphite_dim_t 535 pbb_nb_dynamic_scattering_transform (const struct poly_bb *pbb) 536 { 537 /* This function requires the 2d + 1 scattering format to be 538 invariant during all transformations. */ 539 gcc_assert (PBB_NB_SCATTERING_TRANSFORM (pbb) % 2); 540 return PBB_NB_SCATTERING_TRANSFORM (pbb) / 2; 541 } 542 543 /* Returns the number of local variables used in the transformed 544 scattering polyhedron of PBB. */ 545 546 static inline graphite_dim_t 547 pbb_nb_local_vars (const struct poly_bb *pbb) 548 { 549 /* For now we do not have any local variables, as we do not do strip 550 mining for example. */ 551 return PBB_NB_LOCAL_VARIABLES (pbb); 552 } 553 554 /* The dimension in the domain of PBB containing the iterator ITER. */ 555 556 static inline ppl_dimension_type 557 pbb_iterator_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t iter) 558 { 559 return iter; 560 } 561 562 /* The dimension in the domain of PBB containing the iterator ITER. */ 563 564 static inline ppl_dimension_type 565 pbb_parameter_dim (poly_bb_p pbb, graphite_dim_t param) 566 { 567 return param 568 + pbb_dim_iter_domain (pbb); 569 } 570 571 /* The dimension in the original scattering polyhedron of PBB 572 containing the scattering iterator SCATTER. */ 573 574 static inline ppl_dimension_type 575 psco_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t scatter) 576 { 577 gcc_assert (scatter < pbb_nb_scattering_orig (pbb)); 578 return scatter; 579 } 580 581 /* The dimension in the transformed scattering polyhedron of PBB 582 containing the scattering iterator SCATTER. */ 583 584 static inline ppl_dimension_type 585 psct_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t scatter) 586 { 587 gcc_assert (scatter <= pbb_nb_scattering_transform (pbb)); 588 return scatter; 589 } 590 591 ppl_dimension_type psct_scattering_dim_for_loop_depth (poly_bb_p, 592 graphite_dim_t); 593 594 /* The dimension in the transformed scattering polyhedron of PBB of 595 the local variable LV. */ 596 597 static inline ppl_dimension_type 598 psct_local_var_dim (poly_bb_p pbb, graphite_dim_t lv) 599 { 600 gcc_assert (lv <= pbb_nb_local_vars (pbb)); 601 return lv + pbb_nb_scattering_transform (pbb); 602 } 603 604 /* The dimension in the original scattering polyhedron of PBB 605 containing the loop iterator ITER. */ 606 607 static inline ppl_dimension_type 608 psco_iterator_dim (poly_bb_p pbb, graphite_dim_t iter) 609 { 610 gcc_assert (iter < pbb_dim_iter_domain (pbb)); 611 return iter + pbb_nb_scattering_orig (pbb); 612 } 613 614 /* The dimension in the transformed scattering polyhedron of PBB 615 containing the loop iterator ITER. */ 616 617 static inline ppl_dimension_type 618 psct_iterator_dim (poly_bb_p pbb, graphite_dim_t iter) 619 { 620 gcc_assert (iter < pbb_dim_iter_domain (pbb)); 621 return iter 622 + pbb_nb_scattering_transform (pbb) 623 + pbb_nb_local_vars (pbb); 624 } 625 626 /* The dimension in the original scattering polyhedron of PBB 627 containing parameter PARAM. */ 628 629 static inline ppl_dimension_type 630 psco_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_orig (pbb) 635 + pbb_dim_iter_domain (pbb); 636 } 637 638 /* The dimension in the transformed scattering polyhedron of PBB 639 containing parameter PARAM. */ 640 641 static inline ppl_dimension_type 642 psct_parameter_dim (poly_bb_p pbb, graphite_dim_t param) 643 { 644 gcc_assert (param < pbb_nb_params (pbb)); 645 return param 646 + pbb_nb_scattering_transform (pbb) 647 + pbb_nb_local_vars (pbb) 648 + pbb_dim_iter_domain (pbb); 649 } 650 651 /* The scattering dimension of PBB corresponding to the dynamic level 652 LEVEL. */ 653 654 static inline ppl_dimension_type 655 psct_dynamic_dim (poly_bb_p pbb, graphite_dim_t level) 656 { 657 graphite_dim_t result = 1 + 2 * level; 658 659 gcc_assert (result < pbb_nb_scattering_transform (pbb)); 660 return result; 661 } 662 663 /* The scattering dimension of PBB corresponding to the static 664 sequence of the loop level LEVEL. */ 665 666 static inline ppl_dimension_type 667 psct_static_dim (poly_bb_p pbb, graphite_dim_t level) 668 { 669 graphite_dim_t result = 2 * level; 670 671 gcc_assert (result < pbb_nb_scattering_transform (pbb)); 672 return result; 673 } 674 675 /* Adds to the transformed scattering polyhedron of PBB a new local 676 variable and returns its index. */ 677 678 static inline graphite_dim_t 679 psct_add_local_variable (poly_bb_p pbb) 680 { 681 graphite_dim_t nlv = pbb_nb_local_vars (pbb); 682 ppl_dimension_type lv_column = psct_local_var_dim (pbb, nlv); 683 ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb), lv_column, 1); 684 PBB_NB_LOCAL_VARIABLES (pbb) += 1; 685 return nlv; 686 } 687 688 /* Adds a dimension to the transformed scattering polyhedron of PBB at 689 INDEX. */ 690 691 static inline void 692 psct_add_scattering_dimension (poly_bb_p pbb, ppl_dimension_type index) 693 { 694 gcc_assert (index < pbb_nb_scattering_transform (pbb)); 695 696 ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb), index, 1); 697 PBB_NB_SCATTERING_TRANSFORM (pbb) += 1; 698 } 699 700 typedef struct lst *lst_p; 701 DEF_VEC_P(lst_p); 702 DEF_VEC_ALLOC_P (lst_p, heap); 703 704 /* Loops and Statements Tree. */ 705 struct lst { 706 707 /* LOOP_P is true when an LST node is a loop. */ 708 bool loop_p; 709 710 /* A pointer to the loop that contains this node. */ 711 lst_p loop_father; 712 713 /* The sum of all the memory strides for an LST loop. */ 714 mpz_t memory_strides; 715 716 /* Loop nodes contain a sequence SEQ of LST nodes, statements 717 contain a pointer to their polyhedral representation PBB. */ 718 union { 719 poly_bb_p pbb; 720 VEC (lst_p, heap) *seq; 721 } node; 722 }; 723 724 #define LST_LOOP_P(LST) ((LST)->loop_p) 725 #define LST_LOOP_FATHER(LST) ((LST)->loop_father) 726 #define LST_PBB(LST) ((LST)->node.pbb) 727 #define LST_SEQ(LST) ((LST)->node.seq) 728 #define LST_LOOP_MEMORY_STRIDES(LST) ((LST)->memory_strides) 729 730 void scop_to_lst (scop_p); 731 void print_lst (FILE *, lst_p, int); 732 void debug_lst (lst_p); 733 void dot_lst (lst_p); 734 735 /* Creates a new LST loop with SEQ. */ 736 737 static inline lst_p 738 new_lst_loop (VEC (lst_p, heap) *seq) 739 { 740 lst_p lst = XNEW (struct lst); 741 int i; 742 lst_p l; 743 744 LST_LOOP_P (lst) = true; 745 LST_SEQ (lst) = seq; 746 LST_LOOP_FATHER (lst) = NULL; 747 mpz_init (LST_LOOP_MEMORY_STRIDES (lst)); 748 mpz_set_si (LST_LOOP_MEMORY_STRIDES (lst), -1); 749 750 for (i = 0; VEC_iterate (lst_p, seq, i, l); i++) 751 LST_LOOP_FATHER (l) = lst; 752 753 return lst; 754 } 755 756 /* Creates a new LST statement with PBB. */ 757 758 static inline lst_p 759 new_lst_stmt (poly_bb_p pbb) 760 { 761 lst_p lst = XNEW (struct lst); 762 763 LST_LOOP_P (lst) = false; 764 LST_PBB (lst) = pbb; 765 LST_LOOP_FATHER (lst) = NULL; 766 return lst; 767 } 768 769 /* Frees the memory used by LST. */ 770 771 static inline void 772 free_lst (lst_p lst) 773 { 774 if (!lst) 775 return; 776 777 if (LST_LOOP_P (lst)) 778 { 779 int i; 780 lst_p l; 781 782 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++) 783 free_lst (l); 784 785 mpz_clear (LST_LOOP_MEMORY_STRIDES (lst)); 786 VEC_free (lst_p, heap, LST_SEQ (lst)); 787 } 788 789 free (lst); 790 } 791 792 /* Returns a copy of LST. */ 793 794 static inline lst_p 795 copy_lst (lst_p lst) 796 { 797 if (!lst) 798 return NULL; 799 800 if (LST_LOOP_P (lst)) 801 { 802 int i; 803 lst_p l; 804 VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5); 805 806 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++) 807 VEC_safe_push (lst_p, heap, seq, copy_lst (l)); 808 809 return new_lst_loop (seq); 810 } 811 812 return new_lst_stmt (LST_PBB (lst)); 813 } 814 815 /* Adds a new loop under the loop LST. */ 816 817 static inline void 818 lst_add_loop_under_loop (lst_p lst) 819 { 820 VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 1); 821 lst_p l = new_lst_loop (LST_SEQ (lst)); 822 823 gcc_assert (LST_LOOP_P (lst)); 824 825 LST_LOOP_FATHER (l) = lst; 826 VEC_quick_push (lst_p, seq, l); 827 LST_SEQ (lst) = seq; 828 } 829 830 /* Returns the loop depth of LST. */ 831 832 static inline int 833 lst_depth (lst_p lst) 834 { 835 if (!lst) 836 return -2; 837 838 /* The depth of the outermost "fake" loop is -1. This outermost 839 loop does not have a loop father and it is just a container, as 840 in the loop representation of GCC. */ 841 if (!LST_LOOP_FATHER (lst)) 842 return -1; 843 844 return lst_depth (LST_LOOP_FATHER (lst)) + 1; 845 } 846 847 /* Returns the Dewey number for LST. */ 848 849 static inline int 850 lst_dewey_number (lst_p lst) 851 { 852 int i; 853 lst_p l; 854 855 if (!lst) 856 return -1; 857 858 if (!LST_LOOP_FATHER (lst)) 859 return 0; 860 861 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (LST_LOOP_FATHER (lst)), i, l) 862 if (l == lst) 863 return i; 864 865 return -1; 866 } 867 868 /* Returns the Dewey number of LST at depth DEPTH. */ 869 870 static inline int 871 lst_dewey_number_at_depth (lst_p lst, int depth) 872 { 873 gcc_assert (lst && depth >= 0 && lst_depth (lst) <= depth); 874 875 if (lst_depth (lst) == depth) 876 return lst_dewey_number (lst); 877 878 return lst_dewey_number_at_depth (LST_LOOP_FATHER (lst), depth); 879 } 880 881 /* Returns the predecessor of LST in the sequence of its loop father. 882 Returns NULL if LST is the first statement in the sequence. */ 883 884 static inline lst_p 885 lst_pred (lst_p lst) 886 { 887 int dewey; 888 lst_p father; 889 890 if (!lst || !LST_LOOP_FATHER (lst)) 891 return NULL; 892 893 dewey = lst_dewey_number (lst); 894 if (dewey == 0) 895 return NULL; 896 897 father = LST_LOOP_FATHER (lst); 898 return VEC_index (lst_p, LST_SEQ (father), dewey - 1); 899 } 900 901 /* Returns the successor of LST in the sequence of its loop father. 902 Returns NULL if there is none. */ 903 904 static inline lst_p 905 lst_succ (lst_p lst) 906 { 907 int dewey; 908 lst_p father; 909 910 if (!lst || !LST_LOOP_FATHER (lst)) 911 return NULL; 912 913 dewey = lst_dewey_number (lst); 914 father = LST_LOOP_FATHER (lst); 915 916 if (VEC_length (lst_p, LST_SEQ (father)) == (unsigned) dewey + 1) 917 return NULL; 918 919 return VEC_index (lst_p, LST_SEQ (father), dewey + 1); 920 } 921 922 923 /* Return the LST node corresponding to PBB. */ 924 925 static inline lst_p 926 lst_find_pbb (lst_p lst, poly_bb_p pbb) 927 { 928 int i; 929 lst_p l; 930 931 if (!lst) 932 return NULL; 933 934 if (!LST_LOOP_P (lst)) 935 return (pbb == LST_PBB (lst)) ? lst : NULL; 936 937 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++) 938 { 939 lst_p res = lst_find_pbb (l, pbb); 940 if (res) 941 return res; 942 } 943 944 return NULL; 945 } 946 947 /* Return the LST node corresponding to the loop around STMT at depth 948 LOOP_DEPTH. */ 949 950 static inline lst_p 951 find_lst_loop (lst_p stmt, int loop_depth) 952 { 953 lst_p loop = LST_LOOP_FATHER (stmt); 954 955 gcc_assert (loop_depth >= 0); 956 957 while (loop_depth < lst_depth (loop)) 958 loop = LST_LOOP_FATHER (loop); 959 960 return loop; 961 } 962 963 /* Return the first LST representing a PBB statement in LST. */ 964 965 static inline lst_p 966 lst_find_first_pbb (lst_p lst) 967 { 968 int i; 969 lst_p l; 970 971 if (!lst) 972 return NULL; 973 974 if (!LST_LOOP_P (lst)) 975 return lst; 976 977 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++) 978 { 979 lst_p res = lst_find_first_pbb (l); 980 if (res) 981 return res; 982 } 983 984 return NULL; 985 } 986 987 /* Returns true when LST is a loop that does not contain 988 statements. */ 989 990 static inline bool 991 lst_empty_p (lst_p lst) 992 { 993 return !lst_find_first_pbb (lst); 994 } 995 996 /* Return the last LST representing a PBB statement in LST. */ 997 998 static inline lst_p 999 lst_find_last_pbb (lst_p lst) 1000 { 1001 int i; 1002 lst_p l, res = NULL; 1003 1004 if (!lst) 1005 return NULL; 1006 1007 if (!LST_LOOP_P (lst)) 1008 return lst; 1009 1010 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++) 1011 { 1012 lst_p last = lst_find_last_pbb (l); 1013 1014 if (last) 1015 res = last; 1016 } 1017 1018 gcc_assert (res); 1019 return res; 1020 } 1021 1022 /* Returns true if LOOP contains LST, in other words, if LST is nested 1023 in LOOP. */ 1024 1025 static inline bool 1026 lst_contains_p (lst_p loop, lst_p lst) 1027 { 1028 if (!loop || !lst || !LST_LOOP_P (loop)) 1029 return false; 1030 1031 if (loop == lst) 1032 return true; 1033 1034 return lst_contains_p (loop, LST_LOOP_FATHER (lst)); 1035 } 1036 1037 /* Returns true if LOOP contains PBB, in other words, if PBB is nested 1038 in LOOP. */ 1039 1040 static inline bool 1041 lst_contains_pbb (lst_p loop, poly_bb_p pbb) 1042 { 1043 return lst_find_pbb (loop, pbb) ? true : false; 1044 } 1045 1046 /* Creates a loop nest of depth NB_LOOPS containing LST. */ 1047 1048 static inline lst_p 1049 lst_create_nest (int nb_loops, lst_p lst) 1050 { 1051 lst_p res, loop; 1052 VEC (lst_p, heap) *seq; 1053 1054 if (nb_loops == 0) 1055 return lst; 1056 1057 seq = VEC_alloc (lst_p, heap, 1); 1058 loop = lst_create_nest (nb_loops - 1, lst); 1059 VEC_quick_push (lst_p, seq, loop); 1060 res = new_lst_loop (seq); 1061 LST_LOOP_FATHER (loop) = res; 1062 1063 return res; 1064 } 1065 1066 /* Removes LST from the sequence of statements of its loop father. */ 1067 1068 static inline void 1069 lst_remove_from_sequence (lst_p lst) 1070 { 1071 lst_p father = LST_LOOP_FATHER (lst); 1072 int dewey = lst_dewey_number (lst); 1073 1074 gcc_assert (lst && father && dewey >= 0); 1075 1076 VEC_ordered_remove (lst_p, LST_SEQ (father), dewey); 1077 LST_LOOP_FATHER (lst) = NULL; 1078 } 1079 1080 /* Removes the loop LST and inline its body in the father loop. */ 1081 1082 static inline void 1083 lst_remove_loop_and_inline_stmts_in_loop_father (lst_p lst) 1084 { 1085 lst_p l, father = LST_LOOP_FATHER (lst); 1086 int i, dewey = lst_dewey_number (lst); 1087 1088 gcc_assert (lst && father && dewey >= 0); 1089 1090 VEC_ordered_remove (lst_p, LST_SEQ (father), dewey); 1091 LST_LOOP_FATHER (lst) = NULL; 1092 1093 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l) 1094 { 1095 VEC_safe_insert (lst_p, heap, LST_SEQ (father), dewey + i, l); 1096 LST_LOOP_FATHER (l) = father; 1097 } 1098 } 1099 1100 /* Sets NITER to the upper bound approximation of the number of 1101 iterations of loop LST. */ 1102 1103 static inline void 1104 lst_niter_for_loop (lst_p lst, mpz_t niter) 1105 { 1106 int depth = lst_depth (lst); 1107 poly_bb_p pbb = LST_PBB (lst_find_first_pbb (lst)); 1108 1109 gcc_assert (LST_LOOP_P (lst)); 1110 pbb_number_of_iterations_at_time (pbb, psct_dynamic_dim (pbb, depth), niter); 1111 } 1112 1113 /* Updates the scattering of PBB to be at the DEWEY number in the loop 1114 at depth LEVEL. */ 1115 1116 static inline void 1117 pbb_update_scattering (poly_bb_p pbb, graphite_dim_t level, int dewey) 1118 { 1119 ppl_Polyhedron_t ph = PBB_TRANSFORMED_SCATTERING (pbb); 1120 ppl_dimension_type sched = psct_static_dim (pbb, level); 1121 ppl_dimension_type ds[1]; 1122 ppl_Constraint_t new_cstr; 1123 ppl_Linear_Expression_t expr; 1124 ppl_dimension_type dim; 1125 1126 ppl_Polyhedron_space_dimension (ph, &dim); 1127 ds[0] = sched; 1128 ppl_Polyhedron_remove_space_dimensions (ph, ds, 1); 1129 ppl_insert_dimensions (ph, sched, 1); 1130 1131 ppl_new_Linear_Expression_with_dimension (&expr, dim); 1132 ppl_set_coef (expr, sched, -1); 1133 ppl_set_inhomogeneous (expr, dewey); 1134 ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL); 1135 ppl_delete_Linear_Expression (expr); 1136 ppl_Polyhedron_add_constraint (ph, new_cstr); 1137 ppl_delete_Constraint (new_cstr); 1138 } 1139 1140 /* Updates the scattering of all the PBBs under LST to be at the DEWEY 1141 number in the loop at depth LEVEL. */ 1142 1143 static inline void 1144 lst_update_scattering_under (lst_p lst, int level, int dewey) 1145 { 1146 int i; 1147 lst_p l; 1148 1149 gcc_assert (lst && level >= 0 && dewey >= 0); 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_under (l, level, dewey); 1154 else 1155 pbb_update_scattering (LST_PBB (lst), level, dewey); 1156 } 1157 1158 /* Updates the all the scattering levels of all the PBBs under 1159 LST. */ 1160 1161 static inline void 1162 lst_update_scattering (lst_p lst) 1163 { 1164 int i; 1165 lst_p l; 1166 1167 if (!lst) 1168 return; 1169 1170 if (LST_LOOP_FATHER (lst)) 1171 { 1172 lst_p father = LST_LOOP_FATHER (lst); 1173 int dewey = lst_dewey_number (lst); 1174 int level = lst_depth (lst); 1175 1176 gcc_assert (lst && father && dewey >= 0 && level >= 0); 1177 1178 for (i = dewey; VEC_iterate (lst_p, LST_SEQ (father), i, l); i++) 1179 lst_update_scattering_under (l, level, i); 1180 } 1181 1182 if (LST_LOOP_P (lst)) 1183 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++) 1184 lst_update_scattering (l); 1185 } 1186 1187 /* Inserts LST1 before LST2 if BEFORE is true; inserts LST1 after LST2 1188 if BEFORE is false. */ 1189 1190 static inline void 1191 lst_insert_in_sequence (lst_p lst1, lst_p lst2, bool before) 1192 { 1193 lst_p father; 1194 int dewey; 1195 1196 /* Do not insert empty loops. */ 1197 if (!lst1 || lst_empty_p (lst1)) 1198 return; 1199 1200 father = LST_LOOP_FATHER (lst2); 1201 dewey = lst_dewey_number (lst2); 1202 1203 gcc_assert (lst2 && father && dewey >= 0); 1204 1205 VEC_safe_insert (lst_p, heap, LST_SEQ (father), before ? dewey : dewey + 1, 1206 lst1); 1207 LST_LOOP_FATHER (lst1) = father; 1208 } 1209 1210 /* Replaces LST1 with LST2. */ 1211 1212 static inline void 1213 lst_replace (lst_p lst1, lst_p lst2) 1214 { 1215 lst_p father; 1216 int dewey; 1217 1218 if (!lst2 || lst_empty_p (lst2)) 1219 return; 1220 1221 father = LST_LOOP_FATHER (lst1); 1222 dewey = lst_dewey_number (lst1); 1223 LST_LOOP_FATHER (lst2) = father; 1224 VEC_replace (lst_p, LST_SEQ (father), dewey, lst2); 1225 } 1226 1227 /* Returns a copy of ROOT where LST has been replaced by a copy of the 1228 LSTs A B C in this sequence. */ 1229 1230 static inline lst_p 1231 lst_substitute_3 (lst_p root, lst_p lst, lst_p a, lst_p b, lst_p c) 1232 { 1233 int i; 1234 lst_p l; 1235 VEC (lst_p, heap) *seq; 1236 1237 if (!root) 1238 return NULL; 1239 1240 gcc_assert (lst && root != lst); 1241 1242 if (!LST_LOOP_P (root)) 1243 return new_lst_stmt (LST_PBB (root)); 1244 1245 seq = VEC_alloc (lst_p, heap, 5); 1246 1247 for (i = 0; VEC_iterate (lst_p, LST_SEQ (root), i, l); i++) 1248 if (l != lst) 1249 VEC_safe_push (lst_p, heap, seq, lst_substitute_3 (l, lst, a, b, c)); 1250 else 1251 { 1252 if (!lst_empty_p (a)) 1253 VEC_safe_push (lst_p, heap, seq, copy_lst (a)); 1254 if (!lst_empty_p (b)) 1255 VEC_safe_push (lst_p, heap, seq, copy_lst (b)); 1256 if (!lst_empty_p (c)) 1257 VEC_safe_push (lst_p, heap, seq, copy_lst (c)); 1258 } 1259 1260 return new_lst_loop (seq); 1261 } 1262 1263 /* Moves LST before LOOP if BEFORE is true, and after the LOOP if 1264 BEFORE is false. */ 1265 1266 static inline void 1267 lst_distribute_lst (lst_p loop, lst_p lst, bool before) 1268 { 1269 int loop_depth = lst_depth (loop); 1270 int depth = lst_depth (lst); 1271 int nb_loops = depth - loop_depth; 1272 1273 gcc_assert (lst && loop && LST_LOOP_P (loop) && nb_loops > 0); 1274 1275 lst_remove_from_sequence (lst); 1276 lst_insert_in_sequence (lst_create_nest (nb_loops, lst), loop, before); 1277 } 1278 1279 /* Removes from LOOP all the statements before/after and including PBB 1280 if BEFORE is true/false. Returns the negation of BEFORE when the 1281 statement PBB has been found. */ 1282 1283 static inline bool 1284 lst_remove_all_before_including_pbb (lst_p loop, poly_bb_p pbb, bool before) 1285 { 1286 int i; 1287 lst_p l; 1288 1289 if (!loop || !LST_LOOP_P (loop)) 1290 return before; 1291 1292 for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l);) 1293 if (LST_LOOP_P (l)) 1294 { 1295 before = lst_remove_all_before_including_pbb (l, pbb, before); 1296 1297 if (VEC_length (lst_p, LST_SEQ (l)) == 0) 1298 { 1299 VEC_ordered_remove (lst_p, LST_SEQ (loop), i); 1300 free_lst (l); 1301 } 1302 else 1303 i++; 1304 } 1305 else 1306 { 1307 if (before) 1308 { 1309 if (LST_PBB (l) == pbb) 1310 before = false; 1311 1312 VEC_ordered_remove (lst_p, LST_SEQ (loop), i); 1313 free_lst (l); 1314 } 1315 else if (LST_PBB (l) == pbb) 1316 { 1317 before = true; 1318 VEC_ordered_remove (lst_p, LST_SEQ (loop), i); 1319 free_lst (l); 1320 } 1321 else 1322 i++; 1323 } 1324 1325 return before; 1326 } 1327 1328 /* Removes from LOOP all the statements before/after and excluding PBB 1329 if BEFORE is true/false; Returns the negation of BEFORE when the 1330 statement PBB has been found. */ 1331 1332 static inline bool 1333 lst_remove_all_before_excluding_pbb (lst_p loop, poly_bb_p pbb, bool before) 1334 { 1335 int i; 1336 lst_p l; 1337 1338 if (!loop || !LST_LOOP_P (loop)) 1339 return before; 1340 1341 for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l);) 1342 if (LST_LOOP_P (l)) 1343 { 1344 before = lst_remove_all_before_excluding_pbb (l, pbb, before); 1345 1346 if (VEC_length (lst_p, LST_SEQ (l)) == 0) 1347 { 1348 VEC_ordered_remove (lst_p, LST_SEQ (loop), i); 1349 free_lst (l); 1350 continue; 1351 } 1352 1353 i++; 1354 } 1355 else 1356 { 1357 if (before && LST_PBB (l) != pbb) 1358 { 1359 VEC_ordered_remove (lst_p, LST_SEQ (loop), i); 1360 free_lst (l); 1361 continue; 1362 } 1363 1364 i++; 1365 1366 if (LST_PBB (l) == pbb) 1367 before = before ? false : true; 1368 } 1369 1370 return before; 1371 } 1372 1373 /* A SCOP is a Static Control Part of the program, simple enough to be 1374 represented in polyhedral form. */ 1375 struct scop 1376 { 1377 /* A SCOP is defined as a SESE region. */ 1378 void *region; 1379 1380 /* Number of parameters in SCoP. */ 1381 graphite_dim_t nb_params; 1382 1383 /* All the basic blocks in this scop that contain memory references 1384 and that will be represented as statements in the polyhedral 1385 representation. */ 1386 VEC (poly_bb_p, heap) *bbs; 1387 1388 /* Original, transformed and saved schedules. */ 1389 lst_p original_schedule, transformed_schedule, saved_schedule; 1390 1391 /* The context describes known restrictions concerning the parameters 1392 and relations in between the parameters. 1393 1394 void f (int8_t a, uint_16_t b) { 1395 c = 2 a + b; 1396 ... 1397 } 1398 1399 Here we can add these restrictions to the context: 1400 1401 -128 >= a >= 127 1402 0 >= b >= 65,535 1403 c = 2a + b */ 1404 ppl_Pointset_Powerset_C_Polyhedron_t context; 1405 1406 /* A hashtable of the data dependence relations for the original 1407 scattering. */ 1408 htab_t original_pddrs; 1409 1410 /* True when the scop has been converted to its polyhedral 1411 representation. */ 1412 bool poly_scop_p; 1413 }; 1414 1415 #define SCOP_BBS(S) (S->bbs) 1416 #define SCOP_REGION(S) ((sese) S->region) 1417 #define SCOP_CONTEXT(S) (S->context) 1418 #define SCOP_ORIGINAL_PDDRS(S) (S->original_pddrs) 1419 #define SCOP_ORIGINAL_SCHEDULE(S) (S->original_schedule) 1420 #define SCOP_TRANSFORMED_SCHEDULE(S) (S->transformed_schedule) 1421 #define SCOP_SAVED_SCHEDULE(S) (S->saved_schedule) 1422 #define POLY_SCOP_P(S) (S->poly_scop_p) 1423 1424 extern scop_p new_scop (void *); 1425 extern void free_scop (scop_p); 1426 extern void free_scops (VEC (scop_p, heap) *); 1427 extern void print_generated_program (FILE *, scop_p); 1428 extern void debug_generated_program (scop_p); 1429 extern void print_scattering_function (FILE *, poly_bb_p, int); 1430 extern void print_scattering_functions (FILE *, scop_p, int); 1431 extern void debug_scattering_function (poly_bb_p, int); 1432 extern void debug_scattering_functions (scop_p, int); 1433 extern int scop_max_loop_depth (scop_p); 1434 extern int unify_scattering_dimensions (scop_p); 1435 extern bool apply_poly_transforms (scop_p); 1436 extern bool graphite_legal_transform (scop_p); 1437 extern void cloog_checksum (scop_p); 1438 1439 /* Set the region of SCOP to REGION. */ 1440 1441 static inline void 1442 scop_set_region (scop_p scop, void *region) 1443 { 1444 scop->region = region; 1445 } 1446 1447 /* Returns the number of parameters for SCOP. */ 1448 1449 static inline graphite_dim_t 1450 scop_nb_params (scop_p scop) 1451 { 1452 return scop->nb_params; 1453 } 1454 1455 /* Set the number of params of SCOP to NB_PARAMS. */ 1456 1457 static inline void 1458 scop_set_nb_params (scop_p scop, graphite_dim_t nb_params) 1459 { 1460 scop->nb_params = nb_params; 1461 } 1462 1463 /* Allocates a new empty poly_scattering structure. */ 1464 1465 static inline poly_scattering_p 1466 poly_scattering_new (void) 1467 { 1468 poly_scattering_p res = XNEW (struct poly_scattering); 1469 1470 res->scattering = NULL; 1471 res->nb_local_variables = 0; 1472 res->nb_scattering = 0; 1473 return res; 1474 } 1475 1476 /* Free a poly_scattering structure. */ 1477 1478 static inline void 1479 poly_scattering_free (poly_scattering_p s) 1480 { 1481 ppl_delete_Polyhedron (s->scattering); 1482 free (s); 1483 } 1484 1485 /* Copies S and return a new scattering. */ 1486 1487 static inline poly_scattering_p 1488 poly_scattering_copy (poly_scattering_p s) 1489 { 1490 poly_scattering_p res = poly_scattering_new (); 1491 1492 ppl_new_C_Polyhedron_from_C_Polyhedron (&(res->scattering), s->scattering); 1493 res->nb_local_variables = s->nb_local_variables; 1494 res->nb_scattering = s->nb_scattering; 1495 return res; 1496 } 1497 1498 /* Saves the transformed scattering of PBB. */ 1499 1500 static inline void 1501 store_scattering_pbb (poly_bb_p pbb) 1502 { 1503 gcc_assert (PBB_TRANSFORMED (pbb)); 1504 1505 if (PBB_SAVED (pbb)) 1506 poly_scattering_free (PBB_SAVED (pbb)); 1507 1508 PBB_SAVED (pbb) = poly_scattering_copy (PBB_TRANSFORMED (pbb)); 1509 } 1510 1511 /* Stores the SCOP_TRANSFORMED_SCHEDULE to SCOP_SAVED_SCHEDULE. */ 1512 1513 static inline void 1514 store_lst_schedule (scop_p scop) 1515 { 1516 if (SCOP_SAVED_SCHEDULE (scop)) 1517 free_lst (SCOP_SAVED_SCHEDULE (scop)); 1518 1519 SCOP_SAVED_SCHEDULE (scop) = copy_lst (SCOP_TRANSFORMED_SCHEDULE (scop)); 1520 } 1521 1522 /* Restores the SCOP_TRANSFORMED_SCHEDULE from SCOP_SAVED_SCHEDULE. */ 1523 1524 static inline void 1525 restore_lst_schedule (scop_p scop) 1526 { 1527 if (SCOP_TRANSFORMED_SCHEDULE (scop)) 1528 free_lst (SCOP_TRANSFORMED_SCHEDULE (scop)); 1529 1530 SCOP_TRANSFORMED_SCHEDULE (scop) = copy_lst (SCOP_SAVED_SCHEDULE (scop)); 1531 } 1532 1533 /* Saves the scattering for all the pbbs in the SCOP. */ 1534 1535 static inline void 1536 store_scattering (scop_p scop) 1537 { 1538 int i; 1539 poly_bb_p pbb; 1540 1541 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) 1542 store_scattering_pbb (pbb); 1543 1544 store_lst_schedule (scop); 1545 } 1546 1547 /* Restores the scattering of PBB. */ 1548 1549 static inline void 1550 restore_scattering_pbb (poly_bb_p pbb) 1551 { 1552 gcc_assert (PBB_SAVED (pbb)); 1553 1554 poly_scattering_free (PBB_TRANSFORMED (pbb)); 1555 PBB_TRANSFORMED (pbb) = poly_scattering_copy (PBB_SAVED (pbb)); 1556 } 1557 1558 /* Restores the scattering for all the pbbs in the SCOP. */ 1559 1560 static inline void 1561 restore_scattering (scop_p scop) 1562 { 1563 int i; 1564 poly_bb_p pbb; 1565 1566 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) 1567 restore_scattering_pbb (pbb); 1568 1569 restore_lst_schedule (scop); 1570 } 1571 1572 /* For a given PBB, add to RES the scop context, the iteration domain, 1573 the original scattering when ORIGINAL_P is true, otherwise add the 1574 transformed scattering. */ 1575 1576 static inline void 1577 combine_context_id_scat (ppl_Pointset_Powerset_C_Polyhedron_t *res, 1578 poly_bb_p pbb, bool original_p) 1579 { 1580 ppl_Pointset_Powerset_C_Polyhedron_t context; 1581 ppl_Pointset_Powerset_C_Polyhedron_t id; 1582 1583 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron 1584 (res, original_p ? 1585 PBB_ORIGINAL_SCATTERING (pbb) : PBB_TRANSFORMED_SCATTERING (pbb)); 1586 1587 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron 1588 (&context, SCOP_CONTEXT (PBB_SCOP (pbb))); 1589 1590 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron 1591 (&id, PBB_DOMAIN (pbb)); 1592 1593 /* Extend the context and the iteration domain to the dimension of 1594 the scattering: T|I|G. */ 1595 { 1596 ppl_dimension_type gdim, tdim, idim; 1597 1598 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (*res, &tdim); 1599 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (context, &gdim); 1600 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (id, &idim); 1601 1602 if (tdim > gdim) 1603 ppl_insert_dimensions_pointset (context, 0, tdim - gdim); 1604 1605 if (tdim > idim) 1606 ppl_insert_dimensions_pointset (id, 0, tdim - idim); 1607 } 1608 1609 /* Add the context and the iteration domain to the result. */ 1610 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (*res, context); 1611 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (*res, id); 1612 1613 ppl_delete_Pointset_Powerset_C_Polyhedron (context); 1614 ppl_delete_Pointset_Powerset_C_Polyhedron (id); 1615 } 1616 1617 #endif 1618