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 #include "config.h" 22 #include "system.h" 23 #include "coretypes.h" 24 #include "diagnostic-core.h" 25 #include "tree-flow.h" 26 #include "tree-dump.h" 27 #include "gimple-pretty-print.h" 28 #include "cfgloop.h" 29 #include "tree-chrec.h" 30 #include "tree-data-ref.h" 31 #include "tree-scalar-evolution.h" 32 #include "sese.h" 33 34 #ifdef HAVE_cloog 35 #include "ppl_c.h" 36 #include "graphite-ppl.h" 37 #include "graphite-poly.h" 38 #include "graphite-dependences.h" 39 #include "graphite-cloog-util.h" 40 41 #define OPENSCOP_MAX_STRING 256 42 43 /* Return the maximal loop depth in SCOP. */ 44 45 int 46 scop_max_loop_depth (scop_p scop) 47 { 48 int i; 49 poly_bb_p pbb; 50 int max_nb_loops = 0; 51 52 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) 53 { 54 int nb_loops = pbb_dim_iter_domain (pbb); 55 if (max_nb_loops < nb_loops) 56 max_nb_loops = nb_loops; 57 } 58 59 return max_nb_loops; 60 } 61 62 /* Extend the scattering matrix of PBB to MAX_SCATTERING scattering 63 dimensions. */ 64 65 static void 66 extend_scattering (poly_bb_p pbb, int max_scattering) 67 { 68 ppl_dimension_type nb_old_dims, nb_new_dims; 69 int nb_added_dims, i; 70 ppl_Coefficient_t coef; 71 mpz_t one; 72 73 nb_added_dims = max_scattering - pbb_nb_scattering_transform (pbb); 74 mpz_init (one); 75 mpz_set_si (one, 1); 76 ppl_new_Coefficient (&coef); 77 ppl_assign_Coefficient_from_mpz_t (coef, one); 78 79 gcc_assert (nb_added_dims >= 0); 80 81 nb_old_dims = pbb_nb_scattering_transform (pbb) + pbb_dim_iter_domain (pbb) 82 + scop_nb_params (PBB_SCOP (pbb)); 83 nb_new_dims = nb_old_dims + nb_added_dims; 84 85 ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb), 86 pbb_nb_scattering_transform (pbb), nb_added_dims); 87 PBB_NB_SCATTERING_TRANSFORM (pbb) += nb_added_dims; 88 89 /* Add identity matrix for the added dimensions. */ 90 for (i = max_scattering - nb_added_dims; i < max_scattering; i++) 91 { 92 ppl_Constraint_t cstr; 93 ppl_Linear_Expression_t expr; 94 95 ppl_new_Linear_Expression_with_dimension (&expr, nb_new_dims); 96 ppl_Linear_Expression_add_to_coefficient (expr, i, coef); 97 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL); 98 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb), cstr); 99 ppl_delete_Constraint (cstr); 100 ppl_delete_Linear_Expression (expr); 101 } 102 103 ppl_delete_Coefficient (coef); 104 mpz_clear (one); 105 } 106 107 /* All scattering matrices in SCOP will have the same number of scattering 108 dimensions. */ 109 110 int 111 unify_scattering_dimensions (scop_p scop) 112 { 113 int i; 114 poly_bb_p pbb; 115 graphite_dim_t max_scattering = 0; 116 117 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) 118 max_scattering = MAX (pbb_nb_scattering_transform (pbb), max_scattering); 119 120 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) 121 extend_scattering (pbb, max_scattering); 122 123 return max_scattering; 124 } 125 126 /* Print to FILE the pdr PH in OpenScop format. NB_SUBSCRIPTS is the number 127 of subscripts in PH, ALIAS_SET_DIM is the dimension of the alias set and 128 NB_PARAMS is the number of parameters in PH. */ 129 130 static void 131 openscop_print_pdr_polyhedron (FILE *file, ppl_const_Polyhedron_t ph, 132 int nb_subscripts, int alias_set_dimension, 133 int nb_params) 134 { 135 int input, locals, output; 136 ppl_dimension_type alias_set_dim = (ppl_dimension_type) alias_set_dimension; 137 ppl_dimension_type sub_dim_last = alias_set_dim + nb_subscripts; 138 ppl_dimension_type *map, i, ph_space_dim = sub_dim_last + 1; 139 ppl_Polyhedron_t pph; 140 141 ppl_new_C_Polyhedron_from_C_Polyhedron (&pph, ph); 142 143 map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, ph_space_dim); 144 145 for (i = 0; i < alias_set_dim - 1; i++) 146 map[i] = nb_subscripts + 1 + i; 147 148 for (i = alias_set_dim - 1; i < sub_dim_last; i++) 149 map[i] = i - alias_set_dim + 1; 150 151 ppl_Polyhedron_map_space_dimensions (pph, map, ph_space_dim - 1); 152 153 locals = 0; 154 input = alias_set_dim - nb_params - 1; 155 156 /* According to OpenScop specification, the alias set column is a part of 157 the output columns. */ 158 output = nb_subscripts + 1; 159 160 openscop_print_polyhedron_matrix (file, pph, output, input, locals, nb_params); 161 } 162 163 /* Print to FILE the powerset PDR. NB_SUBSCRIPTS is the number of subscripts 164 in PDR, ALIAS_SET_DIM is the dimension of the alias set in PDR and 165 NB_PARAMS is the number of parameters in PDR. */ 166 167 static void 168 openscop_print_pdr_powerset (FILE *file, 169 ppl_Pointset_Powerset_C_Polyhedron_t ps, 170 int nb_subscripts, 171 int alias_set_dim, 172 int nb_params) 173 { 174 size_t nb_disjuncts; 175 ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end; 176 177 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it); 178 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end); 179 180 ppl_Pointset_Powerset_C_Polyhedron_size (ps, &nb_disjuncts); 181 fprintf (file, "%d\n", (int) nb_disjuncts); 182 183 for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it), 184 ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end); 185 !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end); 186 ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it)) 187 { 188 ppl_const_Polyhedron_t ph; 189 190 ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph); 191 openscop_print_pdr_polyhedron (file, ph, nb_subscripts, alias_set_dim, 192 nb_params); 193 } 194 195 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it); 196 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end); 197 } 198 199 /* Print to FILE the powerset PS in its OpenScop matrix form. */ 200 201 static void 202 openscop_print_powerset_matrix (FILE *file, 203 ppl_Pointset_Powerset_C_Polyhedron_t ps, 204 int output, int input, int locals, 205 int params) 206 { 207 size_t nb_disjuncts; 208 ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end; 209 210 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it); 211 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end); 212 213 ppl_Pointset_Powerset_C_Polyhedron_size (ps, &nb_disjuncts); 214 fprintf (file, "%d\n", (int) nb_disjuncts); 215 216 for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it), 217 ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end); 218 !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end); 219 ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it)) 220 { 221 ppl_const_Polyhedron_t ph; 222 223 ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph); 224 openscop_print_polyhedron_matrix (file, ph, output, input, locals, 225 params); 226 } 227 228 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it); 229 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end); 230 } 231 232 /* Prints to FILE the scattering function of PBB in OpenScop format, at some 233 VERBOSITY level. */ 234 235 static void 236 openscop_print_scattering_function_1 (FILE *file, poly_bb_p pbb, int verbosity) 237 { 238 graphite_dim_t i; 239 ppl_const_Polyhedron_t ph; 240 241 if (verbosity > 0) 242 { 243 fprintf (file, "# scattering bb_%d (\n", pbb_index (pbb)); 244 fprintf (file, "#eq"); 245 246 for (i = 0; i < pbb_nb_scattering_transform (pbb); i++) 247 fprintf (file, " s%d", (int) i); 248 249 for (i = 0; i < pbb_nb_local_vars (pbb); i++) 250 fprintf (file, " lv%d", (int) i); 251 252 for (i = 0; i < pbb_dim_iter_domain (pbb); i++) 253 fprintf (file, " i%d", (int) i); 254 255 for (i = 0; i < pbb_nb_params (pbb); i++) 256 fprintf (file, " p%d", (int) i); 257 258 fprintf (file, " cst\n"); 259 } 260 261 /* Number of disjunct components. Remove this when 262 PBB_TRANSFORMED_SCATTERING will be a pointset_powerset. */ 263 fprintf (file, "1\n"); 264 265 ph = PBB_TRANSFORMED_SCATTERING (pbb) 266 ? PBB_TRANSFORMED_SCATTERING (pbb) 267 : PBB_ORIGINAL_SCATTERING (pbb); 268 269 openscop_print_polyhedron_matrix (file, ph, 270 pbb_nb_scattering_transform (pbb), 271 pbb_dim_iter_domain (pbb), 272 pbb_nb_local_vars (pbb), 273 pbb_nb_params (pbb)); 274 275 if (verbosity > 0) 276 fprintf (file, "#)\n"); 277 } 278 279 /* Prints to FILE the scattering function of PBB, at some VERBOSITY 280 level. */ 281 282 static void 283 print_scattering_function_1 (FILE *file, poly_bb_p pbb, int verbosity) 284 { 285 graphite_dim_t i; 286 287 if (verbosity > 0) 288 { 289 fprintf (file, "# scattering bb_%d (\n", pbb_index (pbb)); 290 fprintf (file, "#eq"); 291 292 for (i = 0; i < pbb_nb_scattering_transform (pbb); i++) 293 fprintf (file, " s%d", (int) i); 294 295 for (i = 0; i < pbb_nb_local_vars (pbb); i++) 296 fprintf (file, " lv%d", (int) i); 297 298 for (i = 0; i < pbb_dim_iter_domain (pbb); i++) 299 fprintf (file, " i%d", (int) i); 300 301 for (i = 0; i < pbb_nb_params (pbb); i++) 302 fprintf (file, " p%d", (int) i); 303 304 fprintf (file, " cst\n"); 305 } 306 307 /* Number of disjunct components. Remove this when 308 PBB_TRANSFORMED_SCATTERING will be a pointset_powerset. */ 309 fprintf (file, "1\n"); 310 ppl_print_polyhedron_matrix (file, PBB_TRANSFORMED_SCATTERING (pbb) 311 ? PBB_TRANSFORMED_SCATTERING (pbb) 312 : PBB_ORIGINAL_SCATTERING (pbb)); 313 314 if (verbosity > 0) 315 fprintf (file, "#)\n"); 316 } 317 318 /* Prints to FILE the scattering function of PBB, at some VERBOSITY 319 level. */ 320 321 void 322 print_scattering_function (FILE *file, poly_bb_p pbb, int verbosity) 323 { 324 if (!PBB_TRANSFORMED (pbb)) 325 return; 326 327 if (PBB_TRANSFORMED_SCATTERING (pbb) 328 || PBB_ORIGINAL_SCATTERING (pbb)) 329 { 330 if (verbosity > 0) 331 fprintf (file, "# Scattering function is provided\n"); 332 333 fprintf (file, "1\n"); 334 } 335 else 336 { 337 if (verbosity > 0) 338 fprintf (file, "# Scattering function is not provided\n"); 339 340 fprintf (file, "0\n"); 341 return; 342 } 343 344 openscop_print_scattering_function_1 (file, pbb, verbosity); 345 346 if (verbosity > 0) 347 fprintf (file, "# Scattering names are not provided\n"); 348 349 fprintf (file, "0\n"); 350 351 } 352 353 /* Prints to FILE the iteration domain of PBB, at some VERBOSITY 354 level. */ 355 356 void 357 print_iteration_domain (FILE *file, poly_bb_p pbb, int verbosity) 358 { 359 print_pbb_domain (file, pbb, verbosity); 360 } 361 362 /* Prints to FILE the scattering functions of every PBB of SCOP. */ 363 364 void 365 print_scattering_functions (FILE *file, scop_p scop, int verbosity) 366 { 367 int i; 368 poly_bb_p pbb; 369 370 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) 371 print_scattering_function (file, pbb, verbosity); 372 } 373 374 /* Prints to FILE the iteration domains of every PBB of SCOP, at some 375 VERBOSITY level. */ 376 377 void 378 print_iteration_domains (FILE *file, scop_p scop, int verbosity) 379 { 380 int i; 381 poly_bb_p pbb; 382 383 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) 384 print_iteration_domain (file, pbb, verbosity); 385 } 386 387 /* Prints to STDERR the scattering function of PBB, at some VERBOSITY 388 level. */ 389 390 DEBUG_FUNCTION void 391 debug_scattering_function (poly_bb_p pbb, int verbosity) 392 { 393 print_scattering_function (stderr, pbb, verbosity); 394 } 395 396 /* Prints to STDERR the iteration domain of PBB, at some VERBOSITY 397 level. */ 398 399 DEBUG_FUNCTION void 400 debug_iteration_domain (poly_bb_p pbb, int verbosity) 401 { 402 print_iteration_domain (stderr, pbb, verbosity); 403 } 404 405 /* Prints to STDERR the scattering functions of every PBB of SCOP, at 406 some VERBOSITY level. */ 407 408 DEBUG_FUNCTION void 409 debug_scattering_functions (scop_p scop, int verbosity) 410 { 411 print_scattering_functions (stderr, scop, verbosity); 412 } 413 414 /* Prints to STDERR the iteration domains of every PBB of SCOP, at 415 some VERBOSITY level. */ 416 417 DEBUG_FUNCTION void 418 debug_iteration_domains (scop_p scop, int verbosity) 419 { 420 print_iteration_domains (stderr, scop, verbosity); 421 } 422 423 /* Read N integer from FILE. */ 424 425 int * 426 openscop_read_N_int (FILE *file, int N) 427 { 428 char s[OPENSCOP_MAX_STRING]; 429 char *str; 430 int i, *res = (int *) xmalloc (OPENSCOP_MAX_STRING * sizeof (int)); 431 432 /* Skip blank and commented lines. */ 433 while (fgets (s, sizeof s, file) == (char *) 0 434 || s[0] == '#' 435 || ISSPACE (s[0])) 436 ; 437 438 str = s; 439 440 for (i = 0; i < N; i++) 441 { 442 sscanf (str, "%d", &res[i]); 443 444 /* Jump the integer that was read. */ 445 while ((*str) && !ISSPACE (*str) && (*str != '#')) 446 str++; 447 448 /* Jump spaces. */ 449 while ((*str) && ISSPACE (*str) && (*str != '#')) 450 str++; 451 } 452 453 return res; 454 } 455 456 /* Read one integer from FILE. */ 457 458 static int 459 openscop_read_one_int (FILE *file) 460 { 461 int *x = openscop_read_N_int (file, 1); 462 int res = *x; 463 464 free (x); 465 return res; 466 } 467 468 /* Read N string from FILE. */ 469 470 static char * 471 openscop_read_N_string (FILE *file, int N) 472 { 473 int count, i; 474 char str[OPENSCOP_MAX_STRING]; 475 char *tmp = (char *) xmalloc (sizeof (char) * OPENSCOP_MAX_STRING); 476 char *s = NULL; 477 478 /* Skip blank and commented lines. */ 479 while (fgets (str, sizeof str, file) == (char *) 0 480 || str[0] == '#' 481 || ISSPACE (str[0])) 482 ; 483 484 s = str; 485 count = 0; 486 487 for (i = 0; i < N; i++) 488 { 489 /* Read the first word. */ 490 for (; (*s) && (!ISSPACE (*s)) && (*s != '#'); ++count) 491 tmp[count] = *(s++); 492 493 tmp[count] = ' '; 494 count++; 495 496 /* Jump spaces. */ 497 while ((*s) && ISSPACE (*s) && (*s != '#')) 498 s++; 499 } 500 501 tmp[count-1] = '\0'; 502 503 return tmp; 504 } 505 506 /* Read one string from FILE. */ 507 508 static char * 509 openscop_read_one_string (FILE *file) 510 { 511 return openscop_read_N_string (file, 1); 512 } 513 514 /* Read from FILE the powerset PS in its OpenScop matrix form. OUTPUT is the 515 number of output dimensions, INPUT is the number of input dimensions, 516 LOCALS is the number of existentially quantified variables and PARAMS is 517 the number of parameters. */ 518 519 static void 520 openscop_read_powerset_matrix (FILE *file, 521 ppl_Pointset_Powerset_C_Polyhedron_t *ps, 522 int *output, int *input, int *locals, 523 int *params) 524 { 525 int nb_disjuncts, i; 526 527 nb_disjuncts = openscop_read_one_int (file); 528 529 for (i = 0; i < nb_disjuncts; i++) 530 { 531 ppl_Polyhedron_t ph; 532 533 openscop_read_polyhedron_matrix (file, &ph, output, input, locals, 534 params); 535 if (!ph) 536 *ps = NULL; 537 else if (i == 0) 538 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (ps, ph); 539 else 540 ppl_Pointset_Powerset_C_Polyhedron_add_disjunct (*ps, ph); 541 } 542 } 543 544 /* Read a scattering function from FILE and save it to PBB. Return whether 545 the scattering function was provided or not. */ 546 547 static bool 548 graphite_read_scatt (FILE *file, poly_bb_p pbb) 549 { 550 bool scattering_provided = false; 551 int output, input, locals, params; 552 ppl_Polyhedron_t newp; 553 554 if (openscop_read_one_int (file) > 0) 555 { 556 /* Read number of disjunct components. */ 557 openscop_read_one_int (file); 558 559 /* Read scattering function. */ 560 openscop_read_polyhedron_matrix (file, &newp, &output, &input, 561 &locals, ¶ms); 562 store_scattering (PBB_SCOP (pbb)); 563 PBB_TRANSFORMED (pbb) = poly_scattering_new (); 564 PBB_TRANSFORMED_SCATTERING (pbb) = newp; 565 PBB_NB_LOCAL_VARIABLES (pbb) = locals; 566 567 /* New scattering dimension. */ 568 PBB_NB_SCATTERING_TRANSFORM (pbb) = output; 569 570 scattering_provided = true; 571 } 572 573 return scattering_provided; 574 } 575 576 /* Read a scop file. Return true if the scop is transformed. */ 577 578 static bool 579 graphite_read_scop_file (FILE *file, scop_p scop) 580 { 581 char *tmp, *language; 582 size_t i, j, nb_statements, nbr, nbw; 583 int input, output, locals, params; 584 ppl_Pointset_Powerset_C_Polyhedron_t ps; 585 poly_bb_p pbb; 586 bool transform_done = false; 587 588 /* Ensure that the file is in OpenScop format. */ 589 tmp = openscop_read_N_string (file, 2); 590 591 if (strcmp (tmp, "SCoP 1")) 592 { 593 error ("the file is not in OpenScop format"); 594 return false; 595 } 596 597 free (tmp); 598 599 /* Read the language. */ 600 language = openscop_read_one_string (file); 601 602 if (strcmp (language, "Gimple")) 603 { 604 error ("the language is not recognized"); 605 return false; 606 } 607 608 free (language); 609 610 /* Read the context but do not use it. */ 611 openscop_read_powerset_matrix (file, &ps, &input, &output, &locals, ¶ms); 612 613 if ((size_t) params != scop->nb_params) 614 { 615 error ("parameters number in the scop file is different from the" 616 " internal scop parameter number"); 617 return false; 618 } 619 620 /* Read parameter names if provided. */ 621 if (openscop_read_one_int (file)) 622 openscop_read_N_string (file, scop->nb_params); 623 624 nb_statements = openscop_read_one_int (file); 625 626 if (nb_statements != VEC_length (poly_bb_p, SCOP_BBS (scop))) 627 { 628 error ("number of statements in the OpenScop file does not match" 629 " the graphite internal statements number"); 630 return false; 631 } 632 633 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) 634 { 635 /* Read iteration domain. */ 636 openscop_read_powerset_matrix (file, &ps, &input, &output, &locals, 637 ¶ms); 638 639 /* Read scattering. */ 640 transform_done = graphite_read_scatt (file, pbb); 641 642 /* Scattering names. */ 643 openscop_read_one_int (file); 644 645 /* Read access functions. */ 646 if (openscop_read_one_int (file) > 0) 647 { 648 nbr = openscop_read_one_int (file); 649 650 /* Read access functions. */ 651 for (j = 0; j < nbr; j++) 652 openscop_read_powerset_matrix (file, &ps, &input, &output, &locals, 653 ¶ms); 654 655 nbw = openscop_read_one_int (file); 656 657 /* Write access functions. */ 658 for (j = 0; j < nbw; j++) 659 openscop_read_powerset_matrix (file, &ps, &input, &output, &locals, 660 ¶ms); 661 } 662 663 /* Statement body. */ 664 openscop_read_one_int (file); 665 } 666 667 return transform_done; 668 } 669 670 /* Initialize and return a file that will be used to write a scop. SCOP_NUMBER 671 is a sequential number (identifier) used to differentiate scop files. 672 Examples of the generated file names: dump_base_name.0.graphite, 673 dump_base_name.1.graphite, dump_base_name.2.graphite, etc. */ 674 675 static FILE * 676 init_graphite_out_file (int scop_number) 677 { 678 FILE *graphite_out_file; 679 int len = strlen (dump_base_name); 680 char *dumpname = XNEWVEC (char, len + 25); 681 char *s_scop_number = XNEWVEC (char, 15); 682 683 memcpy (dumpname, dump_base_name, len + 1); 684 strip_off_ending (dumpname, len); 685 sprintf (s_scop_number, ".%d", scop_number); 686 strcat (dumpname, s_scop_number); 687 strcat (dumpname, ".graphite"); 688 graphite_out_file = fopen (dumpname, "w+b"); 689 690 if (graphite_out_file == 0) 691 fatal_error ("can%'t open %s for writing: %m", dumpname); 692 693 free (dumpname); 694 695 return graphite_out_file; 696 } 697 698 /* Open and return a file used for scop reading. SCOP_NUMBER is a sequential 699 number (identifier) used to differentiate scop files. Examples of the 700 generated file names: dump_base_name.0.graphite, dump_base_name.1.graphite, 701 dump_base_name.2.graphite, etc. */ 702 703 static FILE * 704 init_graphite_in_file (int scop_number) 705 { 706 FILE *graphite_in_file; 707 int len = strlen (dump_base_name); 708 char *dumpname = XNEWVEC (char, len + 25); 709 char *s_scop_number = XNEWVEC (char, 15); 710 711 memcpy (dumpname, dump_base_name, len + 1); 712 strip_off_ending (dumpname, len); 713 sprintf (s_scop_number, ".%d", scop_number); 714 strcat (dumpname, s_scop_number); 715 strcat (dumpname, ".graphite"); 716 graphite_in_file = fopen (dumpname, "r+b"); 717 718 if (graphite_in_file == 0) 719 fatal_error ("can%'t open %s for reading: %m", dumpname); 720 721 free (dumpname); 722 723 return graphite_in_file; 724 } 725 726 /* Apply graphite transformations to all the basic blocks of SCOP. */ 727 728 bool 729 apply_poly_transforms (scop_p scop) 730 { 731 bool transform_done = false; 732 FILE *graphite_file; 733 static size_t file_scop_number = 0; 734 735 /* This feature is only enabled in the Graphite branch. */ 736 if (0) 737 { 738 graphite_file = init_graphite_in_file (file_scop_number); 739 transform_done |= graphite_read_scop_file (graphite_file, scop); 740 741 /* We cannot check for the legality of the transform here: there 742 are cases where graphite_legal_transform cannot determine the 743 dependence at compile time. For an example, see the 744 explanation of why http://gcc.gnu.org/PR45450 is invalid. */ 745 if (0 && !graphite_legal_transform (scop)) 746 fatal_error ("the graphite file read for scop %d does not contain a legal transform", 747 (int) file_scop_number); 748 749 file_scop_number++; 750 } 751 752 /* Generate code even if we did not apply any real transformation. 753 This also allows to check the performance for the identity 754 transformation: GIMPLE -> GRAPHITE -> GIMPLE 755 Keep in mind that CLooG optimizes in control, so the loop structure 756 may change, even if we only use -fgraphite-identity. */ 757 if (flag_graphite_identity) 758 transform_done = true; 759 760 if (flag_loop_parallelize_all) 761 transform_done = true; 762 763 if (flag_loop_block) 764 transform_done |= scop_do_block (scop); 765 else 766 { 767 if (flag_loop_strip_mine) 768 transform_done |= scop_do_strip_mine (scop, 0); 769 770 if (flag_loop_interchange) 771 transform_done |= scop_do_interchange (scop); 772 } 773 774 if (flag_loop_flatten) 775 transform_done |= flatten_all_loops (scop); 776 777 /* This feature is only enabled in the Graphite branch. */ 778 if (0) 779 { 780 graphite_file = init_graphite_out_file (file_scop_number); 781 print_scop (graphite_file, scop, 1); 782 file_scop_number++; 783 } 784 785 return transform_done; 786 } 787 788 /* Returns true when it PDR1 is a duplicate of PDR2: same PBB, and 789 their ACCESSES, TYPE, and NB_SUBSCRIPTS are the same. */ 790 791 static inline bool 792 can_collapse_pdrs (poly_dr_p pdr1, poly_dr_p pdr2) 793 { 794 bool res; 795 ppl_Pointset_Powerset_C_Polyhedron_t af1, af2, diff; 796 797 if (PDR_PBB (pdr1) != PDR_PBB (pdr2) 798 || PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2) 799 || PDR_TYPE (pdr1) != PDR_TYPE (pdr2)) 800 return false; 801 802 af1 = PDR_ACCESSES (pdr1); 803 af2 = PDR_ACCESSES (pdr2); 804 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron 805 (&diff, af1); 806 ppl_Pointset_Powerset_C_Polyhedron_difference_assign (diff, af2); 807 808 res = ppl_Pointset_Powerset_C_Polyhedron_is_empty (diff); 809 ppl_delete_Pointset_Powerset_C_Polyhedron (diff); 810 return res; 811 } 812 813 /* Removes duplicated data references in PBB. */ 814 815 void 816 pbb_remove_duplicate_pdrs (poly_bb_p pbb) 817 { 818 int i, j; 819 poly_dr_p pdr1, pdr2; 820 821 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr1) 822 for (j = i + 1; VEC_iterate (poly_dr_p, PBB_DRS (pbb), j, pdr2); j++) 823 if (can_collapse_pdrs (pdr1, pdr2)) 824 { 825 PDR_NB_REFS (pdr1) += PDR_NB_REFS (pdr2); 826 free_poly_dr (pdr2); 827 VEC_ordered_remove (poly_dr_p, PBB_DRS (pbb), j); 828 } 829 830 PBB_PDR_DUPLICATES_REMOVED (pbb) = true; 831 } 832 833 /* Create a new polyhedral data reference and add it to PBB. It is 834 defined by its ACCESSES, its TYPE, and the number of subscripts 835 NB_SUBSCRIPTS. */ 836 837 void 838 new_poly_dr (poly_bb_p pbb, int dr_base_object_set, 839 ppl_Pointset_Powerset_C_Polyhedron_t accesses, 840 enum poly_dr_type type, void *cdr, graphite_dim_t nb_subscripts) 841 { 842 static int id = 0; 843 poly_dr_p pdr = XNEW (struct poly_dr); 844 845 PDR_ID (pdr) = id++; 846 PDR_BASE_OBJECT_SET (pdr) = dr_base_object_set; 847 PDR_NB_REFS (pdr) = 1; 848 PDR_PBB (pdr) = pbb; 849 PDR_ACCESSES (pdr) = accesses; 850 PDR_TYPE (pdr) = type; 851 PDR_CDR (pdr) = cdr; 852 PDR_NB_SUBSCRIPTS (pdr) = nb_subscripts; 853 VEC_safe_push (poly_dr_p, heap, PBB_DRS (pbb), pdr); 854 } 855 856 /* Free polyhedral data reference PDR. */ 857 858 void 859 free_poly_dr (poly_dr_p pdr) 860 { 861 ppl_delete_Pointset_Powerset_C_Polyhedron (PDR_ACCESSES (pdr)); 862 XDELETE (pdr); 863 } 864 865 /* Create a new polyhedral black box. */ 866 867 poly_bb_p 868 new_poly_bb (scop_p scop, void *black_box) 869 { 870 poly_bb_p pbb = XNEW (struct poly_bb); 871 872 PBB_DOMAIN (pbb) = NULL; 873 PBB_SCOP (pbb) = scop; 874 pbb_set_black_box (pbb, black_box); 875 PBB_TRANSFORMED (pbb) = NULL; 876 PBB_SAVED (pbb) = NULL; 877 PBB_ORIGINAL (pbb) = NULL; 878 PBB_DRS (pbb) = VEC_alloc (poly_dr_p, heap, 3); 879 PBB_IS_REDUCTION (pbb) = false; 880 PBB_PDR_DUPLICATES_REMOVED (pbb) = false; 881 GBB_PBB ((gimple_bb_p) black_box) = pbb; 882 883 return pbb; 884 } 885 886 /* Free polyhedral black box. */ 887 888 void 889 free_poly_bb (poly_bb_p pbb) 890 { 891 int i; 892 poly_dr_p pdr; 893 894 ppl_delete_Pointset_Powerset_C_Polyhedron (PBB_DOMAIN (pbb)); 895 896 if (PBB_TRANSFORMED (pbb)) 897 poly_scattering_free (PBB_TRANSFORMED (pbb)); 898 899 if (PBB_SAVED (pbb)) 900 poly_scattering_free (PBB_SAVED (pbb)); 901 902 if (PBB_ORIGINAL (pbb)) 903 poly_scattering_free (PBB_ORIGINAL (pbb)); 904 905 if (PBB_DRS (pbb)) 906 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr) 907 free_poly_dr (pdr); 908 909 VEC_free (poly_dr_p, heap, PBB_DRS (pbb)); 910 XDELETE (pbb); 911 } 912 913 static void 914 print_pdr_access_layout (FILE *file, poly_bb_p pbb, poly_dr_p pdr) 915 { 916 graphite_dim_t i; 917 918 fprintf (file, "# eq"); 919 920 fprintf (file, " alias"); 921 922 for (i = 0; i < PDR_NB_SUBSCRIPTS (pdr); i++) 923 fprintf (file, " sub%d", (int) i); 924 925 for (i = 0; i < pbb_dim_iter_domain (pbb); i++) 926 fprintf (file, " i%d", (int) i); 927 928 for (i = 0; i < pbb_nb_params (pbb); i++) 929 fprintf (file, " p%d", (int) i); 930 931 fprintf (file, " cst\n"); 932 } 933 934 /* Prints to FILE the polyhedral data reference PDR, at some VERBOSITY 935 level. */ 936 937 void 938 print_pdr (FILE *file, poly_dr_p pdr, int verbosity) 939 { 940 int alias_set_dim; 941 942 if (verbosity > 1) 943 { 944 fprintf (file, "# pdr_%d (", PDR_ID (pdr)); 945 946 switch (PDR_TYPE (pdr)) 947 { 948 case PDR_READ: 949 fprintf (file, "read \n"); 950 break; 951 952 case PDR_WRITE: 953 fprintf (file, "write \n"); 954 break; 955 956 case PDR_MAY_WRITE: 957 fprintf (file, "may_write \n"); 958 break; 959 960 default: 961 gcc_unreachable (); 962 } 963 964 dump_data_reference (file, (data_reference_p) PDR_CDR (pdr)); 965 } 966 967 if (verbosity > 0) 968 { 969 fprintf (file, "# data accesses (\n"); 970 print_pdr_access_layout (file, PDR_PBB (pdr), pdr); 971 } 972 973 alias_set_dim = pdr_alias_set_dim (pdr) + 1; 974 975 openscop_print_pdr_powerset (file, 976 PDR_ACCESSES (pdr), 977 PDR_NB_SUBSCRIPTS (pdr), 978 alias_set_dim, 979 pbb_nb_params (PDR_PBB (pdr))); 980 981 if (verbosity > 0) 982 fprintf (file, "#)\n"); 983 984 if (verbosity > 1) 985 fprintf (file, "#)\n"); 986 } 987 988 /* Prints to STDERR the polyhedral data reference PDR, at some 989 VERBOSITY level. */ 990 991 DEBUG_FUNCTION void 992 debug_pdr (poly_dr_p pdr, int verbosity) 993 { 994 print_pdr (stderr, pdr, verbosity); 995 } 996 997 /* Creates a new SCOP containing REGION. */ 998 999 scop_p 1000 new_scop (void *region) 1001 { 1002 scop_p scop = XNEW (struct scop); 1003 1004 SCOP_CONTEXT (scop) = NULL; 1005 scop_set_region (scop, region); 1006 SCOP_BBS (scop) = VEC_alloc (poly_bb_p, heap, 3); 1007 SCOP_ORIGINAL_PDDRS (scop) = htab_create (10, hash_poly_ddr_p, 1008 eq_poly_ddr_p, free_poly_ddr); 1009 SCOP_ORIGINAL_SCHEDULE (scop) = NULL; 1010 SCOP_TRANSFORMED_SCHEDULE (scop) = NULL; 1011 SCOP_SAVED_SCHEDULE (scop) = NULL; 1012 POLY_SCOP_P (scop) = false; 1013 1014 return scop; 1015 } 1016 1017 /* Deletes SCOP. */ 1018 1019 void 1020 free_scop (scop_p scop) 1021 { 1022 int i; 1023 poly_bb_p pbb; 1024 1025 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) 1026 free_poly_bb (pbb); 1027 1028 VEC_free (poly_bb_p, heap, SCOP_BBS (scop)); 1029 1030 if (SCOP_CONTEXT (scop)) 1031 ppl_delete_Pointset_Powerset_C_Polyhedron (SCOP_CONTEXT (scop)); 1032 1033 htab_delete (SCOP_ORIGINAL_PDDRS (scop)); 1034 free_lst (SCOP_ORIGINAL_SCHEDULE (scop)); 1035 free_lst (SCOP_TRANSFORMED_SCHEDULE (scop)); 1036 free_lst (SCOP_SAVED_SCHEDULE (scop)); 1037 XDELETE (scop); 1038 } 1039 1040 /* Print to FILE the domain of PBB in OpenScop format, at some VERBOSITY 1041 level. */ 1042 1043 static void 1044 openscop_print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity) 1045 { 1046 graphite_dim_t i; 1047 gimple_bb_p gbb = PBB_BLACK_BOX (pbb); 1048 1049 if (!PBB_DOMAIN (pbb)) 1050 return; 1051 1052 if (verbosity > 0) 1053 { 1054 fprintf (file, "\n# Iteration domain of bb_%d (\n", GBB_BB (gbb)->index); 1055 fprintf (file, "#eq"); 1056 1057 for (i = 0; i < pbb_dim_iter_domain (pbb); i++) 1058 fprintf (file, " i%d", (int) i); 1059 1060 for (i = 0; i < pbb_nb_params (pbb); i++) 1061 fprintf (file, " p%d", (int) i); 1062 1063 fprintf (file, " cst\n"); 1064 } 1065 1066 if (PBB_DOMAIN (pbb)) 1067 openscop_print_powerset_matrix (file, PBB_DOMAIN (pbb), 1068 pbb_dim_iter_domain (pbb), 1069 0, 1070 0, 1071 pbb_nb_params (pbb)); 1072 else 1073 fprintf (file, "0\n"); 1074 1075 if (verbosity > 0) 1076 fprintf (file, "#)\n"); 1077 } 1078 1079 /* Print to FILE the domain of PBB, at some VERBOSITY level. */ 1080 1081 void 1082 print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity) 1083 { 1084 graphite_dim_t i; 1085 gimple_bb_p gbb = PBB_BLACK_BOX (pbb); 1086 1087 if (!PBB_DOMAIN (pbb)) 1088 return; 1089 1090 if (verbosity > 0) 1091 { 1092 fprintf (file, "# Iteration domain of bb_%d (\n", GBB_BB (gbb)->index); 1093 fprintf (file, "# eq"); 1094 1095 for (i = 0; i < pbb_dim_iter_domain (pbb); i++) 1096 fprintf (file, " i%d", (int) i); 1097 1098 for (i = 0; i < pbb_nb_params (pbb); i++) 1099 fprintf (file, " p%d", (int) i); 1100 1101 fprintf (file, " cst\n"); 1102 } 1103 1104 if (PBB_DOMAIN (pbb)) 1105 ppl_print_powerset_matrix (file, PBB_DOMAIN (pbb)); 1106 else 1107 fprintf (file, "0\n"); 1108 1109 if (verbosity > 0) 1110 fprintf (file, "#)\n"); 1111 } 1112 1113 /* Dump the cases of a graphite basic block GBB on FILE. */ 1114 1115 static void 1116 dump_gbb_cases (FILE *file, gimple_bb_p gbb) 1117 { 1118 int i; 1119 gimple stmt; 1120 VEC (gimple, heap) *cases; 1121 1122 if (!gbb) 1123 return; 1124 1125 cases = GBB_CONDITION_CASES (gbb); 1126 if (VEC_empty (gimple, cases)) 1127 return; 1128 1129 fprintf (file, "# cases bb_%d (\n", GBB_BB (gbb)->index); 1130 1131 FOR_EACH_VEC_ELT (gimple, cases, i, stmt) 1132 { 1133 fprintf (file, "# "); 1134 print_gimple_stmt (file, stmt, 0, 0); 1135 } 1136 1137 fprintf (file, "#)\n"); 1138 } 1139 1140 /* Dump conditions of a graphite basic block GBB on FILE. */ 1141 1142 static void 1143 dump_gbb_conditions (FILE *file, gimple_bb_p gbb) 1144 { 1145 int i; 1146 gimple stmt; 1147 VEC (gimple, heap) *conditions; 1148 1149 if (!gbb) 1150 return; 1151 1152 conditions = GBB_CONDITIONS (gbb); 1153 if (VEC_empty (gimple, conditions)) 1154 return; 1155 1156 fprintf (file, "# conditions bb_%d (\n", GBB_BB (gbb)->index); 1157 1158 FOR_EACH_VEC_ELT (gimple, conditions, i, stmt) 1159 { 1160 fprintf (file, "# "); 1161 print_gimple_stmt (file, stmt, 0, 0); 1162 } 1163 1164 fprintf (file, "#)\n"); 1165 } 1166 1167 /* Print to FILE all the data references of PBB, at some VERBOSITY 1168 level. */ 1169 1170 void 1171 print_pdrs (FILE *file, poly_bb_p pbb, int verbosity) 1172 { 1173 int i; 1174 poly_dr_p pdr; 1175 int nb_reads = 0; 1176 int nb_writes = 0; 1177 1178 if (VEC_length (poly_dr_p, PBB_DRS (pbb)) == 0) 1179 { 1180 if (verbosity > 0) 1181 fprintf (file, "# Access informations are not provided\n");\ 1182 fprintf (file, "0\n"); 1183 return; 1184 } 1185 1186 if (verbosity > 1) 1187 fprintf (file, "# Data references (\n"); 1188 1189 if (verbosity > 0) 1190 fprintf (file, "# Access informations are provided\n"); 1191 fprintf (file, "1\n"); 1192 1193 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr) 1194 if (PDR_TYPE (pdr) == PDR_READ) 1195 nb_reads++; 1196 else 1197 nb_writes++; 1198 1199 if (verbosity > 1) 1200 fprintf (file, "# Read data references (\n"); 1201 1202 if (verbosity > 0) 1203 fprintf (file, "# Read access informations\n"); 1204 fprintf (file, "%d\n", nb_reads); 1205 1206 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr) 1207 if (PDR_TYPE (pdr) == PDR_READ) 1208 print_pdr (file, pdr, verbosity); 1209 1210 if (verbosity > 1) 1211 fprintf (file, "#)\n"); 1212 1213 if (verbosity > 1) 1214 fprintf (file, "# Write data references (\n"); 1215 1216 if (verbosity > 0) 1217 fprintf (file, "# Write access informations\n"); 1218 fprintf (file, "%d\n", nb_writes); 1219 1220 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr) 1221 if (PDR_TYPE (pdr) != PDR_READ) 1222 print_pdr (file, pdr, verbosity); 1223 1224 if (verbosity > 1) 1225 fprintf (file, "#)\n"); 1226 1227 if (verbosity > 1) 1228 fprintf (file, "#)\n"); 1229 } 1230 1231 /* Print to STDERR all the data references of PBB. */ 1232 1233 DEBUG_FUNCTION void 1234 debug_pdrs (poly_bb_p pbb, int verbosity) 1235 { 1236 print_pdrs (stderr, pbb, verbosity); 1237 } 1238 1239 /* Print to FILE the body of PBB, at some VERBOSITY level. 1240 If statement_body_provided is false statement body is not printed. */ 1241 1242 static void 1243 print_pbb_body (FILE *file, poly_bb_p pbb, int verbosity, 1244 bool statement_body_provided) 1245 { 1246 if (verbosity > 1) 1247 fprintf (file, "# Body (\n"); 1248 1249 if (!statement_body_provided) 1250 { 1251 if (verbosity > 0) 1252 fprintf (file, "# Statement body is not provided\n"); 1253 1254 fprintf (file, "0\n"); 1255 1256 if (verbosity > 1) 1257 fprintf (file, "#)\n"); 1258 return; 1259 } 1260 1261 if (verbosity > 0) 1262 fprintf (file, "# Statement body is provided\n"); 1263 fprintf (file, "1\n"); 1264 1265 if (verbosity > 0) 1266 fprintf (file, "# Original iterator names\n# Iterator names are not provided yet.\n"); 1267 1268 if (verbosity > 0) 1269 fprintf (file, "# Statement body\n"); 1270 1271 fprintf (file, "{\n"); 1272 dump_bb (pbb_bb (pbb), file, 0); 1273 fprintf (file, "}\n"); 1274 1275 if (verbosity > 1) 1276 fprintf (file, "#)\n"); 1277 } 1278 1279 /* Print to FILE the domain and scattering function of PBB, at some 1280 VERBOSITY level. */ 1281 1282 void 1283 print_pbb (FILE *file, poly_bb_p pbb, int verbosity) 1284 { 1285 if (verbosity > 1) 1286 { 1287 fprintf (file, "# pbb_%d (\n", pbb_index (pbb)); 1288 dump_gbb_conditions (file, PBB_BLACK_BOX (pbb)); 1289 dump_gbb_cases (file, PBB_BLACK_BOX (pbb)); 1290 } 1291 1292 openscop_print_pbb_domain (file, pbb, verbosity); 1293 print_scattering_function (file, pbb, verbosity); 1294 print_pdrs (file, pbb, verbosity); 1295 print_pbb_body (file, pbb, verbosity, false); 1296 1297 if (verbosity > 1) 1298 fprintf (file, "#)\n"); 1299 } 1300 1301 /* Print to FILE the parameters of SCOP, at some VERBOSITY level. */ 1302 1303 void 1304 print_scop_params (FILE *file, scop_p scop, int verbosity) 1305 { 1306 int i; 1307 tree t; 1308 1309 if (verbosity > 1) 1310 fprintf (file, "# parameters (\n"); 1311 1312 if (VEC_length (tree, SESE_PARAMS (SCOP_REGION (scop)))) 1313 { 1314 if (verbosity > 0) 1315 fprintf (file, "# Parameter names are provided\n"); 1316 1317 fprintf (file, "1\n"); 1318 1319 if (verbosity > 0) 1320 fprintf (file, "# Parameter names\n"); 1321 } 1322 else 1323 { 1324 if (verbosity > 0) 1325 fprintf (file, "# Parameter names are not provided\n"); 1326 fprintf (file, "0\n"); 1327 } 1328 1329 FOR_EACH_VEC_ELT (tree, SESE_PARAMS (SCOP_REGION (scop)), i, t) 1330 { 1331 print_generic_expr (file, t, 0); 1332 fprintf (file, " "); 1333 } 1334 1335 fprintf (file, "\n"); 1336 1337 if (verbosity > 1) 1338 fprintf (file, "#)\n"); 1339 } 1340 1341 /* Print to FILE the context of SCoP in OpenScop format, at some VERBOSITY 1342 level. */ 1343 1344 static void 1345 openscop_print_scop_context (FILE *file, scop_p scop, int verbosity) 1346 { 1347 graphite_dim_t i; 1348 1349 if (verbosity > 0) 1350 { 1351 fprintf (file, "# Context (\n"); 1352 fprintf (file, "#eq"); 1353 1354 for (i = 0; i < scop_nb_params (scop); i++) 1355 fprintf (file, " p%d", (int) i); 1356 1357 fprintf (file, " cst\n"); 1358 } 1359 1360 if (SCOP_CONTEXT (scop)) 1361 openscop_print_powerset_matrix (file, SCOP_CONTEXT (scop), 0, 0, 0, 1362 scop_nb_params (scop)); 1363 else 1364 fprintf (file, "0 %d 0 0 0 %d\n", (int) scop_nb_params (scop) + 2, 1365 (int) scop_nb_params (scop)); 1366 1367 if (verbosity > 0) 1368 fprintf (file, "# )\n"); 1369 } 1370 1371 /* Print to FILE the context of SCoP, at some VERBOSITY level. */ 1372 1373 void 1374 print_scop_context (FILE *file, scop_p scop, int verbosity) 1375 { 1376 graphite_dim_t i; 1377 1378 if (verbosity > 0) 1379 { 1380 fprintf (file, "# Context (\n"); 1381 fprintf (file, "#eq"); 1382 1383 for (i = 0; i < scop_nb_params (scop); i++) 1384 fprintf (file, " p%d", (int) i); 1385 1386 fprintf (file, " cst\n"); 1387 } 1388 1389 if (SCOP_CONTEXT (scop)) 1390 ppl_print_powerset_matrix (file, SCOP_CONTEXT (scop)); 1391 else 1392 fprintf (file, "0 %d\n", (int) scop_nb_params (scop) + 2); 1393 1394 if (verbosity > 0) 1395 fprintf (file, "# )\n"); 1396 } 1397 1398 /* Print to FILE the SCOP, at some VERBOSITY level. */ 1399 1400 void 1401 print_scop (FILE *file, scop_p scop, int verbosity) 1402 { 1403 int i; 1404 poly_bb_p pbb; 1405 1406 fprintf (file, "SCoP 1\n#(\n"); 1407 fprintf (file, "# Language\nGimple\n"); 1408 openscop_print_scop_context (file, scop, verbosity); 1409 print_scop_params (file, scop, verbosity); 1410 1411 if (verbosity > 0) 1412 fprintf (file, "# Number of statements\n"); 1413 1414 fprintf (file, "%d\n",VEC_length (poly_bb_p, SCOP_BBS (scop))); 1415 1416 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) 1417 print_pbb (file, pbb, verbosity); 1418 1419 if (verbosity > 1) 1420 { 1421 fprintf (file, "# original_lst (\n"); 1422 print_lst (file, SCOP_ORIGINAL_SCHEDULE (scop), 0); 1423 fprintf (file, "\n#)\n"); 1424 1425 fprintf (file, "# transformed_lst (\n"); 1426 print_lst (file, SCOP_TRANSFORMED_SCHEDULE (scop), 0); 1427 fprintf (file, "\n#)\n"); 1428 } 1429 1430 fprintf (file, "#)\n"); 1431 } 1432 1433 /* Print to FILE the input file that CLooG would expect as input, at 1434 some VERBOSITY level. */ 1435 1436 void 1437 print_cloog (FILE *file, scop_p scop, int verbosity) 1438 { 1439 int i; 1440 poly_bb_p pbb; 1441 1442 fprintf (file, "# SCoP (generated by GCC/Graphite\n"); 1443 if (verbosity > 0) 1444 fprintf (file, "# CLooG output language\n"); 1445 fprintf (file, "c\n"); 1446 1447 print_scop_context (file, scop, verbosity); 1448 print_scop_params (file, scop, verbosity); 1449 1450 if (verbosity > 0) 1451 fprintf (file, "# Number of statements\n"); 1452 1453 fprintf (file, "%d\n", VEC_length (poly_bb_p, SCOP_BBS (scop))); 1454 1455 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) 1456 { 1457 if (verbosity > 1) 1458 fprintf (file, "# pbb_%d (\n", pbb_index (pbb)); 1459 1460 print_pbb_domain (file, pbb, verbosity); 1461 fprintf (file, "0 0 0"); 1462 1463 if (verbosity > 0) 1464 fprintf (file, "# For future CLooG options.\n"); 1465 else 1466 fprintf (file, "\n"); 1467 1468 if (verbosity > 1) 1469 fprintf (file, "#)\n"); 1470 } 1471 1472 fprintf (file, "0"); 1473 if (verbosity > 0) 1474 fprintf (file, "# Don't set the iterator names.\n"); 1475 else 1476 fprintf (file, "\n"); 1477 1478 if (verbosity > 0) 1479 fprintf (file, "# Number of scattering functions\n"); 1480 1481 fprintf (file, "%d\n", VEC_length (poly_bb_p, SCOP_BBS (scop))); 1482 unify_scattering_dimensions (scop); 1483 1484 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) 1485 { 1486 if (!PBB_TRANSFORMED (pbb) 1487 || !(PBB_TRANSFORMED_SCATTERING (pbb) 1488 || PBB_ORIGINAL_SCATTERING (pbb))) 1489 continue; 1490 1491 if (verbosity > 1) 1492 fprintf (file, "# pbb_%d (\n", pbb_index (pbb)); 1493 1494 print_scattering_function_1 (file, pbb, verbosity); 1495 1496 if (verbosity > 1) 1497 fprintf (file, "#)\n"); 1498 } 1499 1500 fprintf (file, "0"); 1501 if (verbosity > 0) 1502 fprintf (file, "# Don't set the scattering dimension names.\n"); 1503 else 1504 fprintf (file, "\n"); 1505 1506 fprintf (file, "#)\n"); 1507 } 1508 1509 /* Print to STDERR the domain of PBB, at some VERBOSITY level. */ 1510 1511 DEBUG_FUNCTION void 1512 debug_pbb_domain (poly_bb_p pbb, int verbosity) 1513 { 1514 print_pbb_domain (stderr, pbb, verbosity); 1515 } 1516 1517 /* Print to FILE the domain and scattering function of PBB, at some 1518 VERBOSITY level. */ 1519 1520 DEBUG_FUNCTION void 1521 debug_pbb (poly_bb_p pbb, int verbosity) 1522 { 1523 print_pbb (stderr, pbb, verbosity); 1524 } 1525 1526 /* Print to STDERR the context of SCOP, at some VERBOSITY level. */ 1527 1528 DEBUG_FUNCTION void 1529 debug_scop_context (scop_p scop, int verbosity) 1530 { 1531 print_scop_context (stderr, scop, verbosity); 1532 } 1533 1534 /* Print to STDERR the SCOP, at some VERBOSITY level. */ 1535 1536 DEBUG_FUNCTION void 1537 debug_scop (scop_p scop, int verbosity) 1538 { 1539 print_scop (stderr, scop, verbosity); 1540 } 1541 1542 /* Print to STDERR the SCOP under CLooG format, at some VERBOSITY 1543 level. */ 1544 1545 DEBUG_FUNCTION void 1546 debug_cloog (scop_p scop, int verbosity) 1547 { 1548 print_cloog (stderr, scop, verbosity); 1549 } 1550 1551 /* Print to STDERR the parameters of SCOP, at some VERBOSITY 1552 level. */ 1553 1554 DEBUG_FUNCTION void 1555 debug_scop_params (scop_p scop, int verbosity) 1556 { 1557 print_scop_params (stderr, scop, verbosity); 1558 } 1559 1560 1561 /* The dimension in the transformed scattering polyhedron of PBB 1562 containing the scattering iterator for the loop at depth LOOP_DEPTH. */ 1563 1564 ppl_dimension_type 1565 psct_scattering_dim_for_loop_depth (poly_bb_p pbb, graphite_dim_t loop_depth) 1566 { 1567 ppl_const_Constraint_System_t pcs; 1568 ppl_Constraint_System_const_iterator_t cit, cend; 1569 ppl_const_Constraint_t cstr; 1570 ppl_Polyhedron_t ph = PBB_TRANSFORMED_SCATTERING (pbb); 1571 ppl_dimension_type iter = psct_iterator_dim (pbb, loop_depth); 1572 ppl_Linear_Expression_t expr; 1573 ppl_Coefficient_t coef; 1574 mpz_t val; 1575 graphite_dim_t i; 1576 1577 mpz_init (val); 1578 ppl_new_Coefficient (&coef); 1579 ppl_Polyhedron_get_constraints (ph, &pcs); 1580 ppl_new_Constraint_System_const_iterator (&cit); 1581 ppl_new_Constraint_System_const_iterator (&cend); 1582 1583 for (ppl_Constraint_System_begin (pcs, cit), 1584 ppl_Constraint_System_end (pcs, cend); 1585 !ppl_Constraint_System_const_iterator_equal_test (cit, cend); 1586 ppl_Constraint_System_const_iterator_increment (cit)) 1587 { 1588 ppl_Constraint_System_const_iterator_dereference (cit, &cstr); 1589 ppl_new_Linear_Expression_from_Constraint (&expr, cstr); 1590 ppl_Linear_Expression_coefficient (expr, iter, coef); 1591 ppl_Coefficient_to_mpz_t (coef, val); 1592 1593 if (mpz_sgn (val) == 0) 1594 { 1595 ppl_delete_Linear_Expression (expr); 1596 continue; 1597 } 1598 1599 for (i = 0; i < pbb_nb_scattering_transform (pbb); i++) 1600 { 1601 ppl_dimension_type scatter = psct_scattering_dim (pbb, i); 1602 1603 ppl_Linear_Expression_coefficient (expr, scatter, coef); 1604 ppl_Coefficient_to_mpz_t (coef, val); 1605 1606 if (mpz_sgn (val) != 0) 1607 { 1608 mpz_clear (val); 1609 ppl_delete_Linear_Expression (expr); 1610 ppl_delete_Coefficient (coef); 1611 ppl_delete_Constraint_System_const_iterator (cit); 1612 ppl_delete_Constraint_System_const_iterator (cend); 1613 1614 return scatter; 1615 } 1616 } 1617 } 1618 1619 gcc_unreachable (); 1620 } 1621 1622 /* Returns the number of iterations RES of the loop around PBB at 1623 time(scattering) dimension TIME_DEPTH. */ 1624 1625 void 1626 pbb_number_of_iterations_at_time (poly_bb_p pbb, 1627 graphite_dim_t time_depth, 1628 mpz_t res) 1629 { 1630 ppl_Pointset_Powerset_C_Polyhedron_t domain, sctr_lb, sctr_ub; 1631 ppl_dimension_type domain_dim, sctr_dim; 1632 graphite_dim_t dim_iter_domain = pbb_dim_iter_domain (pbb); 1633 ppl_Linear_Expression_t le; 1634 mpz_t lb, ub, diff, one; 1635 int i; 1636 1637 ppl_Polyhedron_space_dimension (PBB_TRANSFORMED_SCATTERING (pbb), &sctr_dim); 1638 1639 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron 1640 (&domain, PBB_DOMAIN (pbb)); 1641 1642 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (domain, &domain_dim); 1643 1644 mpz_init (diff); 1645 mpz_init (lb); 1646 mpz_init (ub); 1647 mpz_init (one); 1648 mpz_set_si (one, 1); 1649 1650 /* Compute the upper bound on the original iteration domain and add 1651 that upper bound to the scattering. */ 1652 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron 1653 (&sctr_ub, PBB_TRANSFORMED_SCATTERING (pbb)); 1654 for (i = 0; i < (int) dim_iter_domain; i++) 1655 { 1656 ppl_Linear_Expression_t eq; 1657 ppl_Constraint_t pc; 1658 ppl_Constraint_System_t cs; 1659 ppl_Polyhedron_t ph; 1660 ppl_Pointset_Powerset_C_Polyhedron_t pph; 1661 1662 ppl_new_Linear_Expression_with_dimension (&le, domain_dim); 1663 ppl_set_coef (le, i, 1); 1664 ppl_min_for_le_pointset (domain, le, lb); 1665 ppl_max_for_le_pointset (domain, le, ub); 1666 mpz_sub (diff, ub, lb); 1667 mpz_add (diff, diff, one); 1668 1669 ppl_new_Linear_Expression_with_dimension (&eq, sctr_dim); 1670 ppl_set_coef (eq, psct_iterator_dim (pbb, i), -1); 1671 ppl_set_inhomogeneous_gmp (eq, diff); 1672 1673 ppl_new_Constraint (&pc, eq, PPL_CONSTRAINT_TYPE_EQUAL); 1674 ppl_new_Constraint_System_from_Constraint (&cs, pc); 1675 ppl_new_C_Polyhedron_from_Constraint_System (&ph, cs); 1676 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&pph, ph); 1677 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr_ub, pph); 1678 1679 ppl_delete_Linear_Expression (le); 1680 ppl_delete_Linear_Expression (eq); 1681 ppl_delete_Polyhedron (ph); 1682 ppl_delete_Pointset_Powerset_C_Polyhedron (pph); 1683 ppl_delete_Constraint (pc); 1684 ppl_delete_Constraint_System (cs); 1685 } 1686 1687 /* Compute the lower bound on the original iteration domain and add 1688 it to the scattering. */ 1689 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron 1690 (&sctr_lb, PBB_TRANSFORMED_SCATTERING (pbb)); 1691 for (i = 0; i < (int) dim_iter_domain; i++) 1692 { 1693 ppl_Linear_Expression_t eq; 1694 ppl_Constraint_t pc; 1695 ppl_Constraint_System_t cs; 1696 ppl_Polyhedron_t ph; 1697 ppl_Pointset_Powerset_C_Polyhedron_t pph; 1698 1699 ppl_new_Linear_Expression_with_dimension (&le, domain_dim); 1700 ppl_set_coef (le, i, 1); 1701 ppl_min_for_le_pointset (domain, le, lb); 1702 1703 ppl_new_Linear_Expression_with_dimension (&eq, sctr_dim); 1704 ppl_set_coef (eq, psct_iterator_dim (pbb, i), -1); 1705 ppl_set_inhomogeneous_gmp (eq, lb); 1706 1707 ppl_new_Constraint (&pc, eq, PPL_CONSTRAINT_TYPE_EQUAL); 1708 ppl_new_Constraint_System_from_Constraint (&cs, pc); 1709 ppl_new_C_Polyhedron_from_Constraint_System (&ph, cs); 1710 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&pph, ph); 1711 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr_lb, pph); 1712 1713 ppl_delete_Linear_Expression (le); 1714 ppl_delete_Linear_Expression (eq); 1715 ppl_delete_Polyhedron (ph); 1716 ppl_delete_Pointset_Powerset_C_Polyhedron (pph); 1717 ppl_delete_Constraint (pc); 1718 ppl_delete_Constraint_System (cs); 1719 } 1720 1721 /* Extract the number of iterations. */ 1722 ppl_new_Linear_Expression_with_dimension (&le, sctr_dim); 1723 ppl_set_coef (le, time_depth, 1); 1724 ppl_min_for_le_pointset (sctr_lb, le, lb); 1725 ppl_max_for_le_pointset (sctr_ub, le, ub); 1726 mpz_sub (res, ub, lb); 1727 1728 mpz_clear (one); 1729 mpz_clear (diff); 1730 mpz_clear (lb); 1731 mpz_clear (ub); 1732 ppl_delete_Linear_Expression (le); 1733 ppl_delete_Pointset_Powerset_C_Polyhedron (sctr_ub); 1734 ppl_delete_Pointset_Powerset_C_Polyhedron (sctr_lb); 1735 ppl_delete_Pointset_Powerset_C_Polyhedron (domain); 1736 } 1737 1738 /* Translates LOOP to LST. */ 1739 1740 static lst_p 1741 loop_to_lst (loop_p loop, VEC (poly_bb_p, heap) *bbs, int *i) 1742 { 1743 poly_bb_p pbb; 1744 VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5); 1745 1746 for (; VEC_iterate (poly_bb_p, bbs, *i, pbb); (*i)++) 1747 { 1748 lst_p stmt; 1749 basic_block bb = GBB_BB (PBB_BLACK_BOX (pbb)); 1750 1751 if (bb->loop_father == loop) 1752 stmt = new_lst_stmt (pbb); 1753 else if (flow_bb_inside_loop_p (loop, bb)) 1754 { 1755 loop_p next = loop->inner; 1756 1757 while (next && !flow_bb_inside_loop_p (next, bb)) 1758 next = next->next; 1759 1760 stmt = loop_to_lst (next, bbs, i); 1761 } 1762 else 1763 { 1764 (*i)--; 1765 return new_lst_loop (seq); 1766 } 1767 1768 VEC_safe_push (lst_p, heap, seq, stmt); 1769 } 1770 1771 return new_lst_loop (seq); 1772 } 1773 1774 /* Reads the original scattering of the SCOP and returns an LST 1775 representing it. */ 1776 1777 void 1778 scop_to_lst (scop_p scop) 1779 { 1780 lst_p res; 1781 int i, n = VEC_length (poly_bb_p, SCOP_BBS (scop)); 1782 VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5); 1783 sese region = SCOP_REGION (scop); 1784 1785 for (i = 0; i < n; i++) 1786 { 1787 poly_bb_p pbb = VEC_index (poly_bb_p, SCOP_BBS (scop), i); 1788 loop_p loop = outermost_loop_in_sese (region, GBB_BB (PBB_BLACK_BOX (pbb))); 1789 1790 if (loop_in_sese_p (loop, region)) 1791 res = loop_to_lst (loop, SCOP_BBS (scop), &i); 1792 else 1793 res = new_lst_stmt (pbb); 1794 1795 VEC_safe_push (lst_p, heap, seq, res); 1796 } 1797 1798 res = new_lst_loop (seq); 1799 SCOP_ORIGINAL_SCHEDULE (scop) = res; 1800 SCOP_TRANSFORMED_SCHEDULE (scop) = copy_lst (res); 1801 } 1802 1803 /* Print to FILE on a new line COLUMN white spaces. */ 1804 1805 static void 1806 lst_indent_to (FILE *file, int column) 1807 { 1808 int i; 1809 1810 if (column > 0) 1811 fprintf (file, "\n#"); 1812 1813 for (i = 0; i < column; i++) 1814 fprintf (file, " "); 1815 } 1816 1817 /* Print LST to FILE with INDENT spaces of indentation. */ 1818 1819 void 1820 print_lst (FILE *file, lst_p lst, int indent) 1821 { 1822 if (!lst) 1823 return; 1824 1825 lst_indent_to (file, indent); 1826 1827 if (LST_LOOP_P (lst)) 1828 { 1829 int i; 1830 lst_p l; 1831 1832 if (LST_LOOP_FATHER (lst)) 1833 fprintf (file, "%d (loop", lst_dewey_number (lst)); 1834 else 1835 fprintf (file, "#(root"); 1836 1837 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l) 1838 print_lst (file, l, indent + 2); 1839 1840 fprintf (file, ")"); 1841 } 1842 else 1843 fprintf (file, "%d stmt_%d", lst_dewey_number (lst), pbb_index (LST_PBB (lst))); 1844 } 1845 1846 /* Print LST to STDERR. */ 1847 1848 DEBUG_FUNCTION void 1849 debug_lst (lst_p lst) 1850 { 1851 print_lst (stderr, lst, 0); 1852 } 1853 1854 /* Pretty print to FILE the loop statement tree LST in DOT format. */ 1855 1856 static void 1857 dot_lst_1 (FILE *file, lst_p lst) 1858 { 1859 if (!lst) 1860 return; 1861 1862 if (LST_LOOP_P (lst)) 1863 { 1864 int i; 1865 lst_p l; 1866 1867 if (!LST_LOOP_FATHER (lst)) 1868 fprintf (file, "L -> L_%d_%d\n", 1869 lst_depth (lst), 1870 lst_dewey_number (lst)); 1871 else 1872 fprintf (file, "L_%d_%d -> L_%d_%d\n", 1873 lst_depth (LST_LOOP_FATHER (lst)), 1874 lst_dewey_number (LST_LOOP_FATHER (lst)), 1875 lst_depth (lst), 1876 lst_dewey_number (lst)); 1877 1878 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l) 1879 dot_lst_1 (file, l); 1880 } 1881 1882 else 1883 fprintf (file, "L_%d_%d -> S_%d\n", 1884 lst_depth (LST_LOOP_FATHER (lst)), 1885 lst_dewey_number (LST_LOOP_FATHER (lst)), 1886 pbb_index (LST_PBB (lst))); 1887 1888 } 1889 1890 /* Display the LST using dotty. */ 1891 1892 DEBUG_FUNCTION void 1893 dot_lst (lst_p lst) 1894 { 1895 /* When debugging, enable the following code. This cannot be used 1896 in production compilers because it calls "system". */ 1897 #if 0 1898 FILE *stream = fopen ("/tmp/lst.dot", "w"); 1899 gcc_assert (stream); 1900 1901 fputs ("digraph all {\n", stream); 1902 dot_lst_1 (stream, lst); 1903 fputs ("}\n\n", stream); 1904 fclose (stream); 1905 1906 system ("dotty /tmp/lst.dot &"); 1907 #else 1908 fputs ("digraph all {\n", stderr); 1909 dot_lst_1 (stderr, lst); 1910 fputs ("}\n\n", stderr); 1911 1912 #endif 1913 } 1914 1915 /* Computes a checksum for the code generated by CLooG for SCOP. */ 1916 1917 DEBUG_FUNCTION void 1918 cloog_checksum (scop_p scop ATTRIBUTE_UNUSED) 1919 { 1920 /* When debugging, enable the following code. This cannot be used 1921 in production compilers because it calls "system". */ 1922 #if 0 1923 FILE *stream = fopen ("/tmp/scop.cloog", "w"); 1924 gcc_assert (stream); 1925 print_cloog (stream, scop, 0); 1926 fclose (stream); 1927 1928 fputs ("\n", stdout); 1929 system ("cloog -compilable 1 /tmp/scop.cloog > /tmp/scop.c ; gcc -O0 -g /tmp/scop.c -lm -o /tmp/scop; /tmp/scop | md5sum "); 1930 #endif 1931 } 1932 1933 #endif 1934 1935