1/* Graphite polyhedral representation. 2 Copyright (C) 2009-2015 Free Software Foundation, Inc. 3 Contributed by Sebastian Pop <sebastian.pop@amd.com> and 4 Tobias Grosser <grosser@fim.uni-passau.de>. 5 6This file is part of GCC. 7 8GCC is free software; you can redistribute it and/or modify 9it under the terms of the GNU General Public License as published by 10the Free Software Foundation; either version 3, or (at your option) 11any later version. 12 13GCC is distributed in the hope that it will be useful, 14but WITHOUT ANY WARRANTY; without even the implied warranty of 15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16GNU General Public License for more details. 17 18You should have received a copy of the GNU General Public License 19along with GCC; see the file COPYING3. If not see 20<http://www.gnu.org/licenses/>. */ 21 22#include "config.h" 23 24#ifdef HAVE_isl 25#include <isl/constraint.h> 26#include <isl/set.h> 27#include <isl/map.h> 28#include <isl/union_map.h> 29#include <isl/constraint.h> 30#include <isl/ilp.h> 31#include <isl/aff.h> 32#include <isl/val.h> 33 34/* Since ISL-0.13, the extern is in val_gmp.h. */ 35#if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus) 36extern "C" { 37#endif 38#include <isl/val_gmp.h> 39#if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus) 40} 41#endif 42#endif 43 44#include "system.h" 45#include "coretypes.h" 46#include "diagnostic-core.h" 47#include "hash-set.h" 48#include "machmode.h" 49#include "vec.h" 50#include "double-int.h" 51#include "input.h" 52#include "alias.h" 53#include "symtab.h" 54#include "options.h" 55#include "wide-int.h" 56#include "inchash.h" 57#include "tree.h" 58#include "fold-const.h" 59#include "predict.h" 60#include "tm.h" 61#include "hard-reg-set.h" 62#include "input.h" 63#include "function.h" 64#include "dominance.h" 65#include "cfg.h" 66#include "basic-block.h" 67#include "tree-ssa-alias.h" 68#include "internal-fn.h" 69#include "gimple-expr.h" 70#include "is-a.h" 71#include "gimple.h" 72#include "gimple-iterator.h" 73#include "tree-ssa-loop.h" 74#include "dumpfile.h" 75#include "gimple-pretty-print.h" 76#include "cfgloop.h" 77#include "tree-chrec.h" 78#include "tree-data-ref.h" 79#include "tree-scalar-evolution.h" 80#include "sese.h" 81 82#ifdef HAVE_isl 83#include "graphite-poly.h" 84 85#define OPENSCOP_MAX_STRING 256 86 87 88/* Print to STDERR the GMP value VAL. */ 89 90DEBUG_FUNCTION void 91debug_gmp_value (mpz_t val) 92{ 93 gmp_fprintf (stderr, "%Zd", val); 94} 95 96/* Return the maximal loop depth in SCOP. */ 97 98int 99scop_max_loop_depth (scop_p scop) 100{ 101 int i; 102 poly_bb_p pbb; 103 int max_nb_loops = 0; 104 105 FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb) 106 { 107 int nb_loops = pbb_dim_iter_domain (pbb); 108 if (max_nb_loops < nb_loops) 109 max_nb_loops = nb_loops; 110 } 111 112 return max_nb_loops; 113} 114 115/* Prints to FILE the scattering function of PBB, at some VERBOSITY 116 level. */ 117 118static void 119print_scattering_function_1 (FILE *file, poly_bb_p pbb, int verbosity) 120{ 121 graphite_dim_t i; 122 123 if (verbosity > 0) 124 { 125 fprintf (file, "# scattering bb_%d (\n", pbb_index (pbb)); 126 fprintf (file, "#eq"); 127 128 for (i = 0; i < pbb_nb_scattering_transform (pbb); i++) 129 fprintf (file, " s%d", (int) i); 130 131 for (i = 0; i < pbb_nb_local_vars (pbb); i++) 132 fprintf (file, " lv%d", (int) i); 133 134 for (i = 0; i < pbb_dim_iter_domain (pbb); i++) 135 fprintf (file, " i%d", (int) i); 136 137 for (i = 0; i < pbb_nb_params (pbb); i++) 138 fprintf (file, " p%d", (int) i); 139 140 fprintf (file, " cst\n"); 141 } 142 143 fprintf (file, "isl\n"); 144 print_isl_map (file, pbb->transformed ? pbb->transformed : pbb->schedule); 145 146 if (verbosity > 0) 147 fprintf (file, "#)\n"); 148} 149 150/* Prints to FILE the scattering function of PBB, at some VERBOSITY 151 level. */ 152 153void 154print_scattering_function (FILE *file, poly_bb_p pbb, int verbosity) 155{ 156 if (!PBB_TRANSFORMED (pbb)) 157 return; 158 159 if (pbb->schedule || pbb->transformed) 160 { 161 if (verbosity > 0) 162 fprintf (file, "# Scattering function is provided\n"); 163 164 fprintf (file, "1\n"); 165 } 166 else 167 { 168 if (verbosity > 0) 169 fprintf (file, "# Scattering function is not provided\n"); 170 171 fprintf (file, "0\n"); 172 return; 173 } 174 175 print_scattering_function_1 (file, pbb, verbosity); 176 177 if (verbosity > 0) 178 fprintf (file, "# Scattering names are not provided\n"); 179 180 fprintf (file, "0\n"); 181 182} 183 184/* Prints to FILE the iteration domain of PBB, at some VERBOSITY 185 level. */ 186 187void 188print_iteration_domain (FILE *file, poly_bb_p pbb, int verbosity) 189{ 190 print_pbb_domain (file, pbb, verbosity); 191} 192 193/* Prints to FILE the scattering functions of every PBB of SCOP. */ 194 195void 196print_scattering_functions (FILE *file, scop_p scop, int verbosity) 197{ 198 int i; 199 poly_bb_p pbb; 200 201 FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb) 202 print_scattering_function (file, pbb, verbosity); 203} 204 205/* Prints to FILE the iteration domains of every PBB of SCOP, at some 206 VERBOSITY level. */ 207 208void 209print_iteration_domains (FILE *file, scop_p scop, int verbosity) 210{ 211 int i; 212 poly_bb_p pbb; 213 214 FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb) 215 print_iteration_domain (file, pbb, verbosity); 216} 217 218/* Prints to STDERR the scattering function of PBB, at some VERBOSITY 219 level. */ 220 221DEBUG_FUNCTION void 222debug_scattering_function (poly_bb_p pbb, int verbosity) 223{ 224 print_scattering_function (stderr, pbb, verbosity); 225} 226 227/* Prints to STDERR the iteration domain of PBB, at some VERBOSITY 228 level. */ 229 230DEBUG_FUNCTION void 231debug_iteration_domain (poly_bb_p pbb, int verbosity) 232{ 233 print_iteration_domain (stderr, pbb, verbosity); 234} 235 236/* Prints to STDERR the scattering functions of every PBB of SCOP, at 237 some VERBOSITY level. */ 238 239DEBUG_FUNCTION void 240debug_scattering_functions (scop_p scop, int verbosity) 241{ 242 print_scattering_functions (stderr, scop, verbosity); 243} 244 245/* Prints to STDERR the iteration domains of every PBB of SCOP, at 246 some VERBOSITY level. */ 247 248DEBUG_FUNCTION void 249debug_iteration_domains (scop_p scop, int verbosity) 250{ 251 print_iteration_domains (stderr, scop, verbosity); 252} 253 254/* Apply graphite transformations to all the basic blocks of SCOP. */ 255 256bool 257apply_poly_transforms (scop_p scop) 258{ 259 bool transform_done = false; 260 261 /* Generate code even if we did not apply any real transformation. 262 This also allows to check the performance for the identity 263 transformation: GIMPLE -> GRAPHITE -> GIMPLE 264 Keep in mind that CLooG optimizes in control, so the loop structure 265 may change, even if we only use -fgraphite-identity. */ 266 if (flag_graphite_identity) 267 transform_done = true; 268 269 if (flag_loop_parallelize_all) 270 transform_done = true; 271 272 if (flag_loop_block) 273 transform_done |= scop_do_block (scop); 274 else 275 { 276 if (flag_loop_strip_mine) 277 transform_done |= scop_do_strip_mine (scop, 0); 278 279 if (flag_loop_interchange) 280 transform_done |= scop_do_interchange (scop); 281 } 282 283 /* This pass needs to be run at the final stage, as it does not 284 update the lst. */ 285 if (flag_loop_optimize_isl || flag_loop_unroll_jam) 286 transform_done |= optimize_isl (scop); 287 288 return transform_done; 289} 290 291/* Create a new polyhedral data reference and add it to PBB. It is 292 defined by its ACCESSES, its TYPE, and the number of subscripts 293 NB_SUBSCRIPTS. */ 294 295void 296new_poly_dr (poly_bb_p pbb, int dr_base_object_set, 297 enum poly_dr_type type, void *cdr, graphite_dim_t nb_subscripts, 298 isl_map *acc, isl_set *extent) 299{ 300 static int id = 0; 301 poly_dr_p pdr = XNEW (struct poly_dr); 302 303 PDR_ID (pdr) = id++; 304 PDR_BASE_OBJECT_SET (pdr) = dr_base_object_set; 305 PDR_NB_REFS (pdr) = 1; 306 PDR_PBB (pdr) = pbb; 307 pdr->accesses = acc; 308 pdr->extent = extent; 309 PDR_TYPE (pdr) = type; 310 PDR_CDR (pdr) = cdr; 311 PDR_NB_SUBSCRIPTS (pdr) = nb_subscripts; 312 PBB_DRS (pbb).safe_push (pdr); 313} 314 315/* Free polyhedral data reference PDR. */ 316 317void 318free_poly_dr (poly_dr_p pdr) 319{ 320 isl_map_free (pdr->accesses); 321 isl_set_free (pdr->extent); 322 XDELETE (pdr); 323} 324 325/* Create a new polyhedral black box. */ 326 327poly_bb_p 328new_poly_bb (scop_p scop, void *black_box) 329{ 330 poly_bb_p pbb = XNEW (struct poly_bb); 331 332 pbb->domain = NULL; 333 pbb->schedule = NULL; 334 pbb->transformed = NULL; 335 pbb->saved = NULL; 336 pbb->map_sepclass = NULL; 337 PBB_SCOP (pbb) = scop; 338 pbb_set_black_box (pbb, black_box); 339 PBB_TRANSFORMED (pbb) = NULL; 340 PBB_SAVED (pbb) = NULL; 341 PBB_ORIGINAL (pbb) = NULL; 342 PBB_DRS (pbb).create (3); 343 PBB_IS_REDUCTION (pbb) = false; 344 GBB_PBB ((gimple_bb_p) black_box) = pbb; 345 346 return pbb; 347} 348 349/* Free polyhedral black box. */ 350 351void 352free_poly_bb (poly_bb_p pbb) 353{ 354 int i; 355 poly_dr_p pdr; 356 357 isl_set_free (pbb->domain); 358 isl_map_free (pbb->schedule); 359 isl_map_free (pbb->transformed); 360 isl_map_free (pbb->saved); 361 362 if (PBB_DRS (pbb).exists ()) 363 FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr) 364 free_poly_dr (pdr); 365 366 PBB_DRS (pbb).release (); 367 XDELETE (pbb); 368} 369 370static void 371print_pdr_access_layout (FILE *file, poly_bb_p pbb, poly_dr_p pdr) 372{ 373 graphite_dim_t i; 374 375 fprintf (file, "# eq"); 376 377 fprintf (file, " alias"); 378 379 for (i = 0; i < PDR_NB_SUBSCRIPTS (pdr); i++) 380 fprintf (file, " sub%d", (int) i); 381 382 for (i = 0; i < pbb_dim_iter_domain (pbb); i++) 383 fprintf (file, " i%d", (int) i); 384 385 for (i = 0; i < pbb_nb_params (pbb); i++) 386 fprintf (file, " p%d", (int) i); 387 388 fprintf (file, " cst\n"); 389} 390 391/* Prints to FILE the polyhedral data reference PDR, at some VERBOSITY 392 level. */ 393 394void 395print_pdr (FILE *file, poly_dr_p pdr, int verbosity) 396{ 397 if (verbosity > 1) 398 { 399 fprintf (file, "# pdr_%d (", PDR_ID (pdr)); 400 401 switch (PDR_TYPE (pdr)) 402 { 403 case PDR_READ: 404 fprintf (file, "read \n"); 405 break; 406 407 case PDR_WRITE: 408 fprintf (file, "write \n"); 409 break; 410 411 case PDR_MAY_WRITE: 412 fprintf (file, "may_write \n"); 413 break; 414 415 default: 416 gcc_unreachable (); 417 } 418 419 dump_data_reference (file, (data_reference_p) PDR_CDR (pdr)); 420 } 421 422 if (verbosity > 0) 423 { 424 fprintf (file, "# data accesses (\n"); 425 print_pdr_access_layout (file, PDR_PBB (pdr), pdr); 426 } 427 428 /* XXX isl dump accesses/subscripts */ 429 430 if (verbosity > 0) 431 fprintf (file, "#)\n"); 432 433 if (verbosity > 1) 434 fprintf (file, "#)\n"); 435} 436 437/* Prints to STDERR the polyhedral data reference PDR, at some 438 VERBOSITY level. */ 439 440DEBUG_FUNCTION void 441debug_pdr (poly_dr_p pdr, int verbosity) 442{ 443 print_pdr (stderr, pdr, verbosity); 444} 445 446/* Creates a new SCOP containing REGION. */ 447 448scop_p 449new_scop (void *region) 450{ 451 scop_p scop = XNEW (struct scop); 452 453 scop->context = NULL; 454 scop->must_raw = NULL; 455 scop->may_raw = NULL; 456 scop->must_raw_no_source = NULL; 457 scop->may_raw_no_source = NULL; 458 scop->must_war = NULL; 459 scop->may_war = NULL; 460 scop->must_war_no_source = NULL; 461 scop->may_war_no_source = NULL; 462 scop->must_waw = NULL; 463 scop->may_waw = NULL; 464 scop->must_waw_no_source = NULL; 465 scop->may_waw_no_source = NULL; 466 scop_set_region (scop, region); 467 SCOP_BBS (scop).create (3); 468 SCOP_ORIGINAL_SCHEDULE (scop) = NULL; 469 SCOP_TRANSFORMED_SCHEDULE (scop) = NULL; 470 SCOP_SAVED_SCHEDULE (scop) = NULL; 471 POLY_SCOP_P (scop) = false; 472 473 return scop; 474} 475 476/* Deletes SCOP. */ 477 478void 479free_scop (scop_p scop) 480{ 481 int i; 482 poly_bb_p pbb; 483 484 FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb) 485 free_poly_bb (pbb); 486 487 SCOP_BBS (scop).release (); 488 489 isl_set_free (scop->context); 490 isl_union_map_free (scop->must_raw); 491 isl_union_map_free (scop->may_raw); 492 isl_union_map_free (scop->must_raw_no_source); 493 isl_union_map_free (scop->may_raw_no_source); 494 isl_union_map_free (scop->must_war); 495 isl_union_map_free (scop->may_war); 496 isl_union_map_free (scop->must_war_no_source); 497 isl_union_map_free (scop->may_war_no_source); 498 isl_union_map_free (scop->must_waw); 499 isl_union_map_free (scop->may_waw); 500 isl_union_map_free (scop->must_waw_no_source); 501 isl_union_map_free (scop->may_waw_no_source); 502 free_lst (SCOP_ORIGINAL_SCHEDULE (scop)); 503 free_lst (SCOP_TRANSFORMED_SCHEDULE (scop)); 504 free_lst (SCOP_SAVED_SCHEDULE (scop)); 505 XDELETE (scop); 506} 507 508/* Print to FILE the domain of PBB in OpenScop format, at some VERBOSITY 509 level. */ 510 511static void 512openscop_print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity) 513{ 514 graphite_dim_t i; 515 gimple_bb_p gbb = PBB_BLACK_BOX (pbb); 516 517 if (!pbb->domain) 518 return; 519 520 if (verbosity > 0) 521 { 522 fprintf (file, "\n# Iteration domain of bb_%d (\n", GBB_BB (gbb)->index); 523 fprintf (file, "#eq"); 524 525 for (i = 0; i < pbb_dim_iter_domain (pbb); i++) 526 fprintf (file, " i%d", (int) i); 527 528 for (i = 0; i < pbb_nb_params (pbb); i++) 529 fprintf (file, " p%d", (int) i); 530 531 fprintf (file, " cst\n"); 532 } 533 534 fprintf (file, "XXX isl\n"); 535 536 if (verbosity > 0) 537 fprintf (file, "#)\n"); 538} 539 540/* Print to FILE the domain of PBB, at some VERBOSITY level. */ 541 542void 543print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity ATTRIBUTE_UNUSED) 544{ 545 print_isl_set (file, pbb->domain); 546} 547 548/* Dump the cases of a graphite basic block GBB on FILE. */ 549 550static void 551dump_gbb_cases (FILE *file, gimple_bb_p gbb) 552{ 553 int i; 554 gimple stmt; 555 vec<gimple> cases; 556 557 if (!gbb) 558 return; 559 560 cases = GBB_CONDITION_CASES (gbb); 561 if (cases.is_empty ()) 562 return; 563 564 fprintf (file, "# cases bb_%d (\n", GBB_BB (gbb)->index); 565 566 FOR_EACH_VEC_ELT (cases, i, stmt) 567 { 568 fprintf (file, "# "); 569 print_gimple_stmt (file, stmt, 0, 0); 570 } 571 572 fprintf (file, "#)\n"); 573} 574 575/* Dump conditions of a graphite basic block GBB on FILE. */ 576 577static void 578dump_gbb_conditions (FILE *file, gimple_bb_p gbb) 579{ 580 int i; 581 gimple stmt; 582 vec<gimple> conditions; 583 584 if (!gbb) 585 return; 586 587 conditions = GBB_CONDITIONS (gbb); 588 if (conditions.is_empty ()) 589 return; 590 591 fprintf (file, "# conditions bb_%d (\n", GBB_BB (gbb)->index); 592 593 FOR_EACH_VEC_ELT (conditions, i, stmt) 594 { 595 fprintf (file, "# "); 596 print_gimple_stmt (file, stmt, 0, 0); 597 } 598 599 fprintf (file, "#)\n"); 600} 601 602/* Print to FILE all the data references of PBB, at some VERBOSITY 603 level. */ 604 605void 606print_pdrs (FILE *file, poly_bb_p pbb, int verbosity) 607{ 608 int i; 609 poly_dr_p pdr; 610 int nb_reads = 0; 611 int nb_writes = 0; 612 613 if (PBB_DRS (pbb).length () == 0) 614 { 615 if (verbosity > 0) 616 fprintf (file, "# Access informations are not provided\n");\ 617 fprintf (file, "0\n"); 618 return; 619 } 620 621 if (verbosity > 1) 622 fprintf (file, "# Data references (\n"); 623 624 if (verbosity > 0) 625 fprintf (file, "# Access informations are provided\n"); 626 fprintf (file, "1\n"); 627 628 FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr) 629 if (PDR_TYPE (pdr) == PDR_READ) 630 nb_reads++; 631 else 632 nb_writes++; 633 634 if (verbosity > 1) 635 fprintf (file, "# Read data references (\n"); 636 637 if (verbosity > 0) 638 fprintf (file, "# Read access informations\n"); 639 fprintf (file, "%d\n", nb_reads); 640 641 FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr) 642 if (PDR_TYPE (pdr) == PDR_READ) 643 print_pdr (file, pdr, verbosity); 644 645 if (verbosity > 1) 646 fprintf (file, "#)\n"); 647 648 if (verbosity > 1) 649 fprintf (file, "# Write data references (\n"); 650 651 if (verbosity > 0) 652 fprintf (file, "# Write access informations\n"); 653 fprintf (file, "%d\n", nb_writes); 654 655 FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr) 656 if (PDR_TYPE (pdr) != PDR_READ) 657 print_pdr (file, pdr, verbosity); 658 659 if (verbosity > 1) 660 fprintf (file, "#)\n"); 661 662 if (verbosity > 1) 663 fprintf (file, "#)\n"); 664} 665 666/* Print to STDERR all the data references of PBB. */ 667 668DEBUG_FUNCTION void 669debug_pdrs (poly_bb_p pbb, int verbosity) 670{ 671 print_pdrs (stderr, pbb, verbosity); 672} 673 674/* Print to FILE the body of PBB, at some VERBOSITY level. 675 If statement_body_provided is false statement body is not printed. */ 676 677static void 678print_pbb_body (FILE *file, poly_bb_p pbb, int verbosity, 679 bool statement_body_provided) 680{ 681 if (verbosity > 1) 682 fprintf (file, "# Body (\n"); 683 684 if (!statement_body_provided) 685 { 686 if (verbosity > 0) 687 fprintf (file, "# Statement body is not provided\n"); 688 689 fprintf (file, "0\n"); 690 691 if (verbosity > 1) 692 fprintf (file, "#)\n"); 693 return; 694 } 695 696 if (verbosity > 0) 697 fprintf (file, "# Statement body is provided\n"); 698 fprintf (file, "1\n"); 699 700 if (verbosity > 0) 701 fprintf (file, "# Original iterator names\n# Iterator names are not provided yet.\n"); 702 703 if (verbosity > 0) 704 fprintf (file, "# Statement body\n"); 705 706 fprintf (file, "{\n"); 707 dump_bb (file, pbb_bb (pbb), 0, 0); 708 fprintf (file, "}\n"); 709 710 if (verbosity > 1) 711 fprintf (file, "#)\n"); 712} 713 714/* Print to FILE the domain and scattering function of PBB, at some 715 VERBOSITY level. */ 716 717void 718print_pbb (FILE *file, poly_bb_p pbb, int verbosity) 719{ 720 if (verbosity > 1) 721 { 722 fprintf (file, "# pbb_%d (\n", pbb_index (pbb)); 723 dump_gbb_conditions (file, PBB_BLACK_BOX (pbb)); 724 dump_gbb_cases (file, PBB_BLACK_BOX (pbb)); 725 } 726 727 openscop_print_pbb_domain (file, pbb, verbosity); 728 print_scattering_function (file, pbb, verbosity); 729 print_pdrs (file, pbb, verbosity); 730 print_pbb_body (file, pbb, verbosity, false); 731 732 if (verbosity > 1) 733 fprintf (file, "#)\n"); 734} 735 736/* Print to FILE the parameters of SCOP, at some VERBOSITY level. */ 737 738void 739print_scop_params (FILE *file, scop_p scop, int verbosity) 740{ 741 int i; 742 tree t; 743 744 if (verbosity > 1) 745 fprintf (file, "# parameters (\n"); 746 747 if (SESE_PARAMS (SCOP_REGION (scop)).length ()) 748 { 749 if (verbosity > 0) 750 fprintf (file, "# Parameter names are provided\n"); 751 752 fprintf (file, "1\n"); 753 754 if (verbosity > 0) 755 fprintf (file, "# Parameter names\n"); 756 } 757 else 758 { 759 if (verbosity > 0) 760 fprintf (file, "# Parameter names are not provided\n"); 761 fprintf (file, "0\n"); 762 } 763 764 FOR_EACH_VEC_ELT (SESE_PARAMS (SCOP_REGION (scop)), i, t) 765 { 766 print_generic_expr (file, t, 0); 767 fprintf (file, " "); 768 } 769 770 fprintf (file, "\n"); 771 772 if (verbosity > 1) 773 fprintf (file, "#)\n"); 774} 775 776/* Print to FILE the context of SCoP in OpenScop format, at some VERBOSITY 777 level. */ 778 779static void 780openscop_print_scop_context (FILE *file, scop_p scop, int verbosity) 781{ 782 graphite_dim_t i; 783 784 if (verbosity > 0) 785 { 786 fprintf (file, "# Context (\n"); 787 fprintf (file, "#eq"); 788 789 for (i = 0; i < scop_nb_params (scop); i++) 790 fprintf (file, " p%d", (int) i); 791 792 fprintf (file, " cst\n"); 793 } 794 795 if (scop->context) 796 /* XXX isl print context */ 797 fprintf (file, "XXX isl\n"); 798 else 799 fprintf (file, "0 %d 0 0 0 %d\n", (int) scop_nb_params (scop) + 2, 800 (int) scop_nb_params (scop)); 801 802 if (verbosity > 0) 803 fprintf (file, "# )\n"); 804} 805 806/* Print to FILE the context of SCoP, at some VERBOSITY level. */ 807 808void 809print_scop_context (FILE *file, scop_p scop, int verbosity) 810{ 811 graphite_dim_t i; 812 813 if (verbosity > 0) 814 { 815 fprintf (file, "# Context (\n"); 816 fprintf (file, "#eq"); 817 818 for (i = 0; i < scop_nb_params (scop); i++) 819 fprintf (file, " p%d", (int) i); 820 821 fprintf (file, " cst\n"); 822 } 823 824 if (scop->context) 825 print_isl_set (file, scop->context); 826 else 827 fprintf (file, "no isl context %d\n", (int) scop_nb_params (scop) + 2); 828 829 if (verbosity > 0) 830 fprintf (file, "# )\n"); 831} 832 833/* Print to FILE the SCOP, at some VERBOSITY level. */ 834 835void 836print_scop (FILE *file, scop_p scop, int verbosity) 837{ 838 int i; 839 poly_bb_p pbb; 840 841 fprintf (file, "SCoP 1\n#(\n"); 842 fprintf (file, "# Language\nGimple\n"); 843 openscop_print_scop_context (file, scop, verbosity); 844 print_scop_params (file, scop, verbosity); 845 846 if (verbosity > 0) 847 fprintf (file, "# Number of statements\n"); 848 849 fprintf (file, "%d\n", SCOP_BBS (scop).length ()); 850 851 FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb) 852 print_pbb (file, pbb, verbosity); 853 854 if (verbosity > 1) 855 { 856 fprintf (file, "# original_lst (\n"); 857 print_lst (file, SCOP_ORIGINAL_SCHEDULE (scop), 0); 858 fprintf (file, "\n#)\n"); 859 860 fprintf (file, "# transformed_lst (\n"); 861 print_lst (file, SCOP_TRANSFORMED_SCHEDULE (scop), 0); 862 fprintf (file, "\n#)\n"); 863 } 864 865 fprintf (file, "#)\n"); 866} 867 868/* Print to STDERR the domain of PBB, at some VERBOSITY level. */ 869 870DEBUG_FUNCTION void 871debug_pbb_domain (poly_bb_p pbb, int verbosity) 872{ 873 print_pbb_domain (stderr, pbb, verbosity); 874} 875 876/* Print to FILE the domain and scattering function of PBB, at some 877 VERBOSITY level. */ 878 879DEBUG_FUNCTION void 880debug_pbb (poly_bb_p pbb, int verbosity) 881{ 882 print_pbb (stderr, pbb, verbosity); 883} 884 885/* Print to STDERR the context of SCOP, at some VERBOSITY level. */ 886 887DEBUG_FUNCTION void 888debug_scop_context (scop_p scop, int verbosity) 889{ 890 print_scop_context (stderr, scop, verbosity); 891} 892 893/* Print to STDERR the SCOP, at some VERBOSITY level. */ 894 895DEBUG_FUNCTION void 896debug_scop (scop_p scop, int verbosity) 897{ 898 print_scop (stderr, scop, verbosity); 899} 900 901/* Print to STDERR the parameters of SCOP, at some VERBOSITY 902 level. */ 903 904DEBUG_FUNCTION void 905debug_scop_params (scop_p scop, int verbosity) 906{ 907 print_scop_params (stderr, scop, verbosity); 908} 909 910extern isl_ctx *the_isl_ctx; 911void 912print_isl_set (FILE *f, isl_set *set) 913{ 914 isl_printer *p = isl_printer_to_file (the_isl_ctx, f); 915 p = isl_printer_print_set (p, set); 916 isl_printer_free (p); 917} 918 919DEBUG_FUNCTION void 920debug_isl_set (isl_set *set) 921{ 922 print_isl_set (stderr, set); 923} 924 925void 926print_isl_map (FILE *f, isl_map *map) 927{ 928 isl_printer *p = isl_printer_to_file (the_isl_ctx, f); 929 p = isl_printer_print_map (p, map); 930 isl_printer_free (p); 931} 932 933DEBUG_FUNCTION void 934debug_isl_map (isl_map *map) 935{ 936 print_isl_map (stderr, map); 937} 938 939void 940print_isl_aff (FILE *f, isl_aff *aff) 941{ 942 isl_printer *p = isl_printer_to_file (the_isl_ctx, f); 943 p = isl_printer_print_aff (p, aff); 944 isl_printer_free (p); 945} 946 947DEBUG_FUNCTION void 948debug_isl_aff (isl_aff *aff) 949{ 950 print_isl_aff (stderr, aff); 951} 952 953void 954print_isl_constraint (FILE *f, isl_constraint *c) 955{ 956 isl_printer *p = isl_printer_to_file (the_isl_ctx, f); 957 p = isl_printer_print_constraint (p, c); 958 isl_printer_free (p); 959} 960 961DEBUG_FUNCTION void 962debug_isl_constraint (isl_constraint *c) 963{ 964 print_isl_constraint (stderr, c); 965} 966 967/* Returns the number of iterations RES of the loop around PBB at 968 time(scattering) dimension TIME_DEPTH. */ 969 970void 971pbb_number_of_iterations_at_time (poly_bb_p pbb, 972 graphite_dim_t time_depth, 973 mpz_t res) 974{ 975 isl_set *transdomain; 976 isl_space *dc; 977 isl_aff *aff; 978 isl_val *isllb, *islub; 979 980 /* Map the iteration domain through the current scatter, and work 981 on the resulting set. */ 982 transdomain = isl_set_apply (isl_set_copy (pbb->domain), 983 isl_map_copy (pbb->transformed)); 984 985 /* Select the time_depth' dimension via an affine expression. */ 986 dc = isl_set_get_space (transdomain); 987 aff = isl_aff_zero_on_domain (isl_local_space_from_space (dc)); 988 aff = isl_aff_set_coefficient_si (aff, isl_dim_in, time_depth, 1); 989 990 /* And find the min/max for that function. */ 991 /* XXX isl check results? */ 992 isllb = isl_set_min_val (transdomain, aff); 993 islub = isl_set_max_val (transdomain, aff); 994 995 islub = isl_val_sub (islub, isllb); 996 islub = isl_val_add_ui (islub, 1); 997 isl_val_get_num_gmp (islub, res); 998 999 isl_val_free (islub); 1000 isl_aff_free (aff); 1001 isl_set_free (transdomain); 1002} 1003 1004/* Translates LOOP to LST. */ 1005 1006static lst_p 1007loop_to_lst (loop_p loop, vec<poly_bb_p> bbs, int *i) 1008{ 1009 poly_bb_p pbb; 1010 vec<lst_p> seq; 1011 seq.create (5); 1012 1013 for (; bbs.iterate (*i, &pbb); (*i)++) 1014 { 1015 lst_p stmt; 1016 basic_block bb = GBB_BB (PBB_BLACK_BOX (pbb)); 1017 1018 if (bb->loop_father == loop) 1019 stmt = new_lst_stmt (pbb); 1020 else if (flow_bb_inside_loop_p (loop, bb)) 1021 { 1022 loop_p next = loop->inner; 1023 1024 while (next && !flow_bb_inside_loop_p (next, bb)) 1025 next = next->next; 1026 1027 stmt = loop_to_lst (next, bbs, i); 1028 } 1029 else 1030 { 1031 (*i)--; 1032 return new_lst_loop (seq); 1033 } 1034 1035 seq.safe_push (stmt); 1036 } 1037 1038 return new_lst_loop (seq); 1039} 1040 1041/* Reads the original scattering of the SCOP and returns an LST 1042 representing it. */ 1043 1044void 1045scop_to_lst (scop_p scop) 1046{ 1047 lst_p res; 1048 int i, n = SCOP_BBS (scop).length (); 1049 vec<lst_p> seq; 1050 seq.create (5); 1051 sese region = SCOP_REGION (scop); 1052 1053 for (i = 0; i < n; i++) 1054 { 1055 poly_bb_p pbb = SCOP_BBS (scop)[i]; 1056 loop_p loop = outermost_loop_in_sese (region, GBB_BB (PBB_BLACK_BOX (pbb))); 1057 1058 if (loop_in_sese_p (loop, region)) 1059 res = loop_to_lst (loop, SCOP_BBS (scop), &i); 1060 else 1061 res = new_lst_stmt (pbb); 1062 1063 seq.safe_push (res); 1064 } 1065 1066 res = new_lst_loop (seq); 1067 SCOP_ORIGINAL_SCHEDULE (scop) = res; 1068 SCOP_TRANSFORMED_SCHEDULE (scop) = copy_lst (res); 1069} 1070 1071/* Print to FILE on a new line COLUMN white spaces. */ 1072 1073static void 1074lst_indent_to (FILE *file, int column) 1075{ 1076 int i; 1077 1078 if (column > 0) 1079 fprintf (file, "\n#"); 1080 1081 for (i = 0; i < column; i++) 1082 fprintf (file, " "); 1083} 1084 1085/* Print LST to FILE with INDENT spaces of indentation. */ 1086 1087void 1088print_lst (FILE *file, lst_p lst, int indent) 1089{ 1090 if (!lst) 1091 return; 1092 1093 lst_indent_to (file, indent); 1094 1095 if (LST_LOOP_P (lst)) 1096 { 1097 int i; 1098 lst_p l; 1099 1100 if (LST_LOOP_FATHER (lst)) 1101 fprintf (file, "%d (loop", lst_dewey_number (lst)); 1102 else 1103 fprintf (file, "#(root"); 1104 1105 FOR_EACH_VEC_ELT (LST_SEQ (lst), i, l) 1106 print_lst (file, l, indent + 2); 1107 1108 fprintf (file, ")"); 1109 } 1110 else 1111 fprintf (file, "%d stmt_%d", lst_dewey_number (lst), pbb_index (LST_PBB (lst))); 1112} 1113 1114/* Print LST to STDERR. */ 1115 1116DEBUG_FUNCTION void 1117debug_lst (lst_p lst) 1118{ 1119 print_lst (stderr, lst, 0); 1120} 1121 1122/* Pretty print to FILE the loop statement tree LST in DOT format. */ 1123 1124static void 1125dot_lst_1 (FILE *file, lst_p lst) 1126{ 1127 if (!lst) 1128 return; 1129 1130 if (LST_LOOP_P (lst)) 1131 { 1132 int i; 1133 lst_p l; 1134 1135 if (!LST_LOOP_FATHER (lst)) 1136 fprintf (file, "L -> L_%d_%d\n", 1137 lst_depth (lst), 1138 lst_dewey_number (lst)); 1139 else 1140 fprintf (file, "L_%d_%d -> L_%d_%d\n", 1141 lst_depth (LST_LOOP_FATHER (lst)), 1142 lst_dewey_number (LST_LOOP_FATHER (lst)), 1143 lst_depth (lst), 1144 lst_dewey_number (lst)); 1145 1146 FOR_EACH_VEC_ELT (LST_SEQ (lst), i, l) 1147 dot_lst_1 (file, l); 1148 } 1149 1150 else 1151 fprintf (file, "L_%d_%d -> S_%d\n", 1152 lst_depth (LST_LOOP_FATHER (lst)), 1153 lst_dewey_number (LST_LOOP_FATHER (lst)), 1154 pbb_index (LST_PBB (lst))); 1155 1156} 1157 1158/* Display the LST using dotty. */ 1159 1160DEBUG_FUNCTION void 1161dot_lst (lst_p lst) 1162{ 1163 /* When debugging, enable the following code. This cannot be used 1164 in production compilers because it calls "system". */ 1165#if 0 1166 FILE *stream = fopen ("/tmp/lst.dot", "w"); 1167 gcc_assert (stream); 1168 1169 fputs ("digraph all {\n", stream); 1170 dot_lst_1 (stream, lst); 1171 fputs ("}\n\n", stream); 1172 fclose (stream); 1173 1174 system ("dotty /tmp/lst.dot &"); 1175#else 1176 fputs ("digraph all {\n", stderr); 1177 dot_lst_1 (stderr, lst); 1178 fputs ("}\n\n", stderr); 1179 1180#endif 1181} 1182 1183/* Reverse the loop around PBB at level DEPTH. */ 1184 1185isl_map * 1186reverse_loop_at_level (poly_bb_p pbb, int depth) 1187{ 1188 unsigned i, depth_dim = psct_dynamic_dim (pbb, depth); 1189 isl_space *d = isl_map_get_space (pbb->transformed); 1190 isl_space *d1 = isl_space_range (d); 1191 unsigned n = isl_space_dim (d1, isl_dim_out); 1192 isl_space *d2 = isl_space_add_dims (d1, isl_dim_in, n); 1193 isl_map *x = isl_map_universe (isl_space_copy (d2)); 1194 isl_constraint *c = isl_equality_alloc (isl_local_space_from_space (d2)); 1195 1196 for (i = 0; i < n; i++) 1197 if (i != depth_dim) 1198 x = isl_map_equate (x, isl_dim_in, i, isl_dim_out, i); 1199 1200 c = isl_constraint_set_coefficient_si (c, isl_dim_in, depth_dim, 1); 1201 c = isl_constraint_set_coefficient_si (c, isl_dim_out, depth_dim, 1); 1202 x = isl_map_add_constraint (x, c); 1203 return x; 1204} 1205 1206/* Reverse the loop at level DEPTH for all the PBBS. */ 1207 1208isl_union_map * 1209reverse_loop_for_pbbs (scop_p scop, vec<poly_bb_p> pbbs, int depth) 1210{ 1211 poly_bb_p pbb; 1212 int i; 1213 isl_space *space = isl_space_from_domain (isl_set_get_space (scop->context)); 1214 isl_union_map *res = isl_union_map_empty (space); 1215 1216 for (i = 0; pbbs.iterate (i, &pbb); i++) 1217 res = isl_union_map_add_map (res, reverse_loop_at_level (pbb, depth)); 1218 1219 return res; 1220} 1221 1222 1223#endif 1224 1225