1/* Conversion of SESE regions to Polyhedra. 2 Copyright (C) 2009, 2010 Free Software Foundation, Inc. 3 Contributed by Sebastian Pop <sebastian.pop@amd.com>. 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 3, or (at your option) 10any later version. 11 12GCC is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING3. If not see 19<http://www.gnu.org/licenses/>. */ 20 21#include "config.h" 22#include "system.h" 23#include "coretypes.h" 24#include "tm.h" 25#include "ggc.h" 26#include "tree.h" 27#include "rtl.h" 28#include "basic-block.h" 29#include "diagnostic.h" 30#include "tree-flow.h" 31#include "toplev.h" 32#include "tree-dump.h" 33#include "timevar.h" 34#include "cfgloop.h" 35#include "tree-chrec.h" 36#include "tree-data-ref.h" 37#include "tree-scalar-evolution.h" 38#include "tree-pass.h" 39#include "domwalk.h" 40#include "value-prof.h" 41#include "pointer-set.h" 42#include "gimple.h" 43#include "sese.h" 44 45#ifdef HAVE_cloog 46#include "cloog/cloog.h" 47#include "ppl_c.h" 48#include "graphite-ppl.h" 49#include "graphite.h" 50#include "graphite-poly.h" 51#include "graphite-scop-detection.h" 52#include "graphite-clast-to-gimple.h" 53#include "graphite-sese-to-poly.h" 54 55/* Check if VAR is used in a phi node, that is no loop header. */ 56 57static bool 58var_used_in_not_loop_header_phi_node (tree var) 59{ 60 imm_use_iterator imm_iter; 61 gimple stmt; 62 bool result = false; 63 64 FOR_EACH_IMM_USE_STMT (stmt, imm_iter, var) 65 { 66 basic_block bb = gimple_bb (stmt); 67 68 if (gimple_code (stmt) == GIMPLE_PHI 69 && bb->loop_father->header != bb) 70 result = true; 71 } 72 73 return result; 74} 75 76/* Returns the index of the PHI argument defined in the outermost 77 loop. */ 78 79static size_t 80phi_arg_in_outermost_loop (gimple phi) 81{ 82 loop_p loop = gimple_bb (phi)->loop_father; 83 size_t i, res = 0; 84 85 for (i = 0; i < gimple_phi_num_args (phi); i++) 86 if (!flow_bb_inside_loop_p (loop, gimple_phi_arg_edge (phi, i)->src)) 87 { 88 loop = gimple_phi_arg_edge (phi, i)->src->loop_father; 89 res = i; 90 } 91 92 return res; 93} 94 95/* Removes a simple copy phi node "RES = phi (INIT, RES)" at position 96 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */ 97 98static void 99remove_simple_copy_phi (gimple_stmt_iterator *psi) 100{ 101 gimple phi = gsi_stmt (*psi); 102 tree res = gimple_phi_result (phi); 103 size_t entry = phi_arg_in_outermost_loop (phi); 104 tree init = gimple_phi_arg_def (phi, entry); 105 gimple stmt = gimple_build_assign (res, init); 106 edge e = gimple_phi_arg_edge (phi, entry); 107 108 remove_phi_node (psi, false); 109 gsi_insert_on_edge_immediate (e, stmt); 110 SSA_NAME_DEF_STMT (res) = stmt; 111} 112 113/* Removes an invariant phi node at position PSI by inserting on the 114 loop ENTRY edge the assignment RES = INIT. */ 115 116static void 117remove_invariant_phi (sese region, gimple_stmt_iterator *psi) 118{ 119 gimple phi = gsi_stmt (*psi); 120 loop_p loop = loop_containing_stmt (phi); 121 tree res = gimple_phi_result (phi); 122 tree scev = scalar_evolution_in_region (region, loop, res); 123 size_t entry = phi_arg_in_outermost_loop (phi); 124 edge e = gimple_phi_arg_edge (phi, entry); 125 tree var; 126 gimple stmt; 127 gimple_seq stmts; 128 gimple_stmt_iterator gsi; 129 130 if (tree_contains_chrecs (scev, NULL)) 131 scev = gimple_phi_arg_def (phi, entry); 132 133 var = force_gimple_operand (scev, &stmts, true, NULL_TREE); 134 stmt = gimple_build_assign (res, var); 135 remove_phi_node (psi, false); 136 137 if (!stmts) 138 stmts = gimple_seq_alloc (); 139 140 gsi = gsi_last (stmts); 141 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT); 142 gsi_insert_seq_on_edge (e, stmts); 143 gsi_commit_edge_inserts (); 144 SSA_NAME_DEF_STMT (res) = stmt; 145} 146 147/* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */ 148 149static inline bool 150simple_copy_phi_p (gimple phi) 151{ 152 tree res; 153 154 if (gimple_phi_num_args (phi) != 2) 155 return false; 156 157 res = gimple_phi_result (phi); 158 return (res == gimple_phi_arg_def (phi, 0) 159 || res == gimple_phi_arg_def (phi, 1)); 160} 161 162/* Returns true when the phi node at position PSI is a reduction phi 163 node in REGION. Otherwise moves the pointer PSI to the next phi to 164 be considered. */ 165 166static bool 167reduction_phi_p (sese region, gimple_stmt_iterator *psi) 168{ 169 loop_p loop; 170 tree scev; 171 affine_iv iv; 172 gimple phi = gsi_stmt (*psi); 173 tree res = gimple_phi_result (phi); 174 175 if (!is_gimple_reg (res)) 176 { 177 gsi_next (psi); 178 return false; 179 } 180 181 loop = loop_containing_stmt (phi); 182 183 if (simple_copy_phi_p (phi)) 184 { 185 /* PRE introduces phi nodes like these, for an example, 186 see id-5.f in the fortran graphite testsuite: 187 188 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)> 189 */ 190 remove_simple_copy_phi (psi); 191 return false; 192 } 193 194 /* Main induction variables with constant strides in LOOP are not 195 reductions. */ 196 if (simple_iv (loop, loop, res, &iv, true)) 197 { 198 if (integer_zerop (iv.step)) 199 remove_invariant_phi (region, psi); 200 else 201 gsi_next (psi); 202 203 return false; 204 } 205 206 scev = scalar_evolution_in_region (region, loop, res); 207 if (chrec_contains_undetermined (scev)) 208 return true; 209 210 if (evolution_function_is_invariant_p (scev, loop->num)) 211 { 212 remove_invariant_phi (region, psi); 213 return false; 214 } 215 216 /* All the other cases are considered reductions. */ 217 return true; 218} 219 220/* Returns true when BB will be represented in graphite. Return false 221 for the basic blocks that contain code eliminated in the code 222 generation pass: i.e. induction variables and exit conditions. */ 223 224static bool 225graphite_stmt_p (sese region, basic_block bb, 226 VEC (data_reference_p, heap) *drs) 227{ 228 gimple_stmt_iterator gsi; 229 loop_p loop = bb->loop_father; 230 231 if (VEC_length (data_reference_p, drs) > 0) 232 return true; 233 234 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 235 { 236 gimple stmt = gsi_stmt (gsi); 237 238 switch (gimple_code (stmt)) 239 { 240 case GIMPLE_DEBUG: 241 /* Control flow expressions can be ignored, as they are 242 represented in the iteration domains and will be 243 regenerated by graphite. */ 244 case GIMPLE_COND: 245 case GIMPLE_GOTO: 246 case GIMPLE_SWITCH: 247 break; 248 249 case GIMPLE_ASSIGN: 250 { 251 tree var = gimple_assign_lhs (stmt); 252 253 /* We need these bbs to be able to construct the phi nodes. */ 254 if (var_used_in_not_loop_header_phi_node (var)) 255 return true; 256 257 var = scalar_evolution_in_region (region, loop, var); 258 if (chrec_contains_undetermined (var)) 259 return true; 260 261 break; 262 } 263 264 default: 265 return true; 266 } 267 } 268 269 return false; 270} 271 272/* Store the GRAPHITE representation of BB. */ 273 274static gimple_bb_p 275new_gimple_bb (basic_block bb, VEC (data_reference_p, heap) *drs) 276{ 277 struct gimple_bb *gbb; 278 279 gbb = XNEW (struct gimple_bb); 280 bb->aux = gbb; 281 GBB_BB (gbb) = bb; 282 GBB_DATA_REFS (gbb) = drs; 283 GBB_CONDITIONS (gbb) = NULL; 284 GBB_CONDITION_CASES (gbb) = NULL; 285 GBB_CLOOG_IV_TYPES (gbb) = NULL; 286 287 return gbb; 288} 289 290static void 291free_data_refs_aux (VEC (data_reference_p, heap) *datarefs) 292{ 293 unsigned int i; 294 struct data_reference *dr; 295 296 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) 297 if (dr->aux) 298 { 299 base_alias_pair *bap = (base_alias_pair *)(dr->aux); 300 301 if (bap->alias_set) 302 free (bap->alias_set); 303 304 free (bap); 305 dr->aux = NULL; 306 } 307} 308/* Frees GBB. */ 309 310static void 311free_gimple_bb (struct gimple_bb *gbb) 312{ 313 if (GBB_CLOOG_IV_TYPES (gbb)) 314 htab_delete (GBB_CLOOG_IV_TYPES (gbb)); 315 316 free_data_refs_aux (GBB_DATA_REFS (gbb)); 317 free_data_refs (GBB_DATA_REFS (gbb)); 318 319 VEC_free (gimple, heap, GBB_CONDITIONS (gbb)); 320 VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb)); 321 GBB_BB (gbb)->aux = 0; 322 XDELETE (gbb); 323} 324 325/* Deletes all gimple bbs in SCOP. */ 326 327static void 328remove_gbbs_in_scop (scop_p scop) 329{ 330 int i; 331 poly_bb_p pbb; 332 333 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) 334 free_gimple_bb (PBB_BLACK_BOX (pbb)); 335} 336 337/* Deletes all scops in SCOPS. */ 338 339void 340free_scops (VEC (scop_p, heap) *scops) 341{ 342 int i; 343 scop_p scop; 344 345 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++) 346 { 347 remove_gbbs_in_scop (scop); 348 free_sese (SCOP_REGION (scop)); 349 free_scop (scop); 350 } 351 352 VEC_free (scop_p, heap, scops); 353} 354 355/* Generates a polyhedral black box only if the bb contains interesting 356 information. */ 357 358static void 359try_generate_gimple_bb (scop_p scop, basic_block bb, sbitmap reductions) 360{ 361 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5); 362 loop_p nest = outermost_loop_in_sese (SCOP_REGION (scop), bb); 363 gimple_stmt_iterator gsi; 364 365 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 366 { 367 gimple stmt = gsi_stmt (gsi); 368 if (!is_gimple_debug (stmt)) 369 graphite_find_data_references_in_stmt (nest, stmt, &drs); 370 } 371 372 if (!graphite_stmt_p (SCOP_REGION (scop), bb, drs)) 373 free_data_refs (drs); 374 else 375 new_poly_bb (scop, new_gimple_bb (bb, drs), TEST_BIT (reductions, 376 bb->index)); 377} 378 379/* Returns true if all predecessors of BB, that are not dominated by BB, are 380 marked in MAP. The predecessors dominated by BB are loop latches and will 381 be handled after BB. */ 382 383static bool 384all_non_dominated_preds_marked_p (basic_block bb, sbitmap map) 385{ 386 edge e; 387 edge_iterator ei; 388 389 FOR_EACH_EDGE (e, ei, bb->preds) 390 if (!TEST_BIT (map, e->src->index) 391 && !dominated_by_p (CDI_DOMINATORS, e->src, bb)) 392 return false; 393 394 return true; 395} 396 397/* Compare the depth of two basic_block's P1 and P2. */ 398 399static int 400compare_bb_depths (const void *p1, const void *p2) 401{ 402 const_basic_block const bb1 = *(const_basic_block const*)p1; 403 const_basic_block const bb2 = *(const_basic_block const*)p2; 404 int d1 = loop_depth (bb1->loop_father); 405 int d2 = loop_depth (bb2->loop_father); 406 407 if (d1 < d2) 408 return 1; 409 410 if (d1 > d2) 411 return -1; 412 413 return 0; 414} 415 416/* Sort the basic blocks from DOM such that the first are the ones at 417 a deepest loop level. */ 418 419static void 420graphite_sort_dominated_info (VEC (basic_block, heap) *dom) 421{ 422 size_t len = VEC_length (basic_block, dom); 423 424 qsort (VEC_address (basic_block, dom), len, sizeof (basic_block), 425 compare_bb_depths); 426} 427 428/* Recursive helper function for build_scops_bbs. */ 429 430static void 431build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb, sbitmap reductions) 432{ 433 sese region = SCOP_REGION (scop); 434 VEC (basic_block, heap) *dom; 435 436 if (TEST_BIT (visited, bb->index) 437 || !bb_in_sese_p (bb, region)) 438 return; 439 440 try_generate_gimple_bb (scop, bb, reductions); 441 SET_BIT (visited, bb->index); 442 443 dom = get_dominated_by (CDI_DOMINATORS, bb); 444 445 if (dom == NULL) 446 return; 447 448 graphite_sort_dominated_info (dom); 449 450 while (!VEC_empty (basic_block, dom)) 451 { 452 int i; 453 basic_block dom_bb; 454 455 for (i = 0; VEC_iterate (basic_block, dom, i, dom_bb); i++) 456 if (all_non_dominated_preds_marked_p (dom_bb, visited)) 457 { 458 build_scop_bbs_1 (scop, visited, dom_bb, reductions); 459 VEC_unordered_remove (basic_block, dom, i); 460 break; 461 } 462 } 463 464 VEC_free (basic_block, heap, dom); 465} 466 467/* Gather the basic blocks belonging to the SCOP. */ 468 469static void 470build_scop_bbs (scop_p scop, sbitmap reductions) 471{ 472 sbitmap visited = sbitmap_alloc (last_basic_block); 473 sese region = SCOP_REGION (scop); 474 475 sbitmap_zero (visited); 476 build_scop_bbs_1 (scop, visited, SESE_ENTRY_BB (region), reductions); 477 sbitmap_free (visited); 478} 479 480/* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron. 481 We generate SCATTERING_DIMENSIONS scattering dimensions. 482 483 CLooG 0.15.0 and previous versions require, that all 484 scattering functions of one CloogProgram have the same number of 485 scattering dimensions, therefore we allow to specify it. This 486 should be removed in future versions of CLooG. 487 488 The scattering polyhedron consists of these dimensions: scattering, 489 loop_iterators, parameters. 490 491 Example: 492 493 | scattering_dimensions = 5 494 | used_scattering_dimensions = 3 495 | nb_iterators = 1 496 | scop_nb_params = 2 497 | 498 | Schedule: 499 | i 500 | 4 5 501 | 502 | Scattering polyhedron: 503 | 504 | scattering: {s1, s2, s3, s4, s5} 505 | loop_iterators: {i} 506 | parameters: {p1, p2} 507 | 508 | s1 s2 s3 s4 s5 i p1 p2 1 509 | 1 0 0 0 0 0 0 0 -4 = 0 510 | 0 1 0 0 0 -1 0 0 0 = 0 511 | 0 0 1 0 0 0 0 0 -5 = 0 */ 512 513static void 514build_pbb_scattering_polyhedrons (ppl_Linear_Expression_t static_schedule, 515 poly_bb_p pbb, int scattering_dimensions) 516{ 517 int i; 518 scop_p scop = PBB_SCOP (pbb); 519 int nb_iterators = pbb_dim_iter_domain (pbb); 520 int used_scattering_dimensions = nb_iterators * 2 + 1; 521 int nb_params = scop_nb_params (scop); 522 ppl_Coefficient_t c; 523 ppl_dimension_type dim = scattering_dimensions + nb_iterators + nb_params; 524 Value v; 525 526 gcc_assert (scattering_dimensions >= used_scattering_dimensions); 527 528 value_init (v); 529 ppl_new_Coefficient (&c); 530 PBB_TRANSFORMED (pbb) = poly_scattering_new (); 531 ppl_new_C_Polyhedron_from_space_dimension 532 (&PBB_TRANSFORMED_SCATTERING (pbb), dim, 0); 533 534 PBB_NB_SCATTERING_TRANSFORM (pbb) = scattering_dimensions; 535 536 for (i = 0; i < scattering_dimensions; i++) 537 { 538 ppl_Constraint_t cstr; 539 ppl_Linear_Expression_t expr; 540 541 ppl_new_Linear_Expression_with_dimension (&expr, dim); 542 value_set_si (v, 1); 543 ppl_assign_Coefficient_from_mpz_t (c, v); 544 ppl_Linear_Expression_add_to_coefficient (expr, i, c); 545 546 /* Textual order inside this loop. */ 547 if ((i % 2) == 0) 548 { 549 ppl_Linear_Expression_coefficient (static_schedule, i / 2, c); 550 ppl_Coefficient_to_mpz_t (c, v); 551 value_oppose (v, v); 552 ppl_assign_Coefficient_from_mpz_t (c, v); 553 ppl_Linear_Expression_add_to_inhomogeneous (expr, c); 554 } 555 556 /* Iterations of this loop. */ 557 else /* if ((i % 2) == 1) */ 558 { 559 int loop = (i - 1) / 2; 560 561 value_set_si (v, -1); 562 ppl_assign_Coefficient_from_mpz_t (c, v); 563 ppl_Linear_Expression_add_to_coefficient 564 (expr, scattering_dimensions + loop, c); 565 } 566 567 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL); 568 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb), cstr); 569 ppl_delete_Linear_Expression (expr); 570 ppl_delete_Constraint (cstr); 571 } 572 573 value_clear (v); 574 ppl_delete_Coefficient (c); 575 576 PBB_ORIGINAL (pbb) = poly_scattering_copy (PBB_TRANSFORMED (pbb)); 577} 578 579/* Build for BB the static schedule. 580 581 The static schedule is a Dewey numbering of the abstract syntax 582 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification 583 584 The following example informally defines the static schedule: 585 586 A 587 for (i: ...) 588 { 589 for (j: ...) 590 { 591 B 592 C 593 } 594 595 for (k: ...) 596 { 597 D 598 E 599 } 600 } 601 F 602 603 Static schedules for A to F: 604 605 DEPTH 606 0 1 2 607 A 0 608 B 1 0 0 609 C 1 0 1 610 D 1 1 0 611 E 1 1 1 612 F 2 613*/ 614 615static void 616build_scop_scattering (scop_p scop) 617{ 618 int i; 619 poly_bb_p pbb; 620 gimple_bb_p previous_gbb = NULL; 621 ppl_Linear_Expression_t static_schedule; 622 ppl_Coefficient_t c; 623 Value v; 624 625 value_init (v); 626 ppl_new_Coefficient (&c); 627 ppl_new_Linear_Expression (&static_schedule); 628 629 /* We have to start schedules at 0 on the first component and 630 because we cannot compare_prefix_loops against a previous loop, 631 prefix will be equal to zero, and that index will be 632 incremented before copying. */ 633 value_set_si (v, -1); 634 ppl_assign_Coefficient_from_mpz_t (c, v); 635 ppl_Linear_Expression_add_to_coefficient (static_schedule, 0, c); 636 637 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) 638 { 639 gimple_bb_p gbb = PBB_BLACK_BOX (pbb); 640 ppl_Linear_Expression_t common; 641 int prefix; 642 int nb_scat_dims = pbb_dim_iter_domain (pbb) * 2 + 1; 643 644 if (previous_gbb) 645 prefix = nb_common_loops (SCOP_REGION (scop), previous_gbb, gbb); 646 else 647 prefix = 0; 648 649 previous_gbb = gbb; 650 ppl_new_Linear_Expression_with_dimension (&common, prefix + 1); 651 ppl_assign_Linear_Expression_from_Linear_Expression (common, 652 static_schedule); 653 654 value_set_si (v, 1); 655 ppl_assign_Coefficient_from_mpz_t (c, v); 656 ppl_Linear_Expression_add_to_coefficient (common, prefix, c); 657 ppl_assign_Linear_Expression_from_Linear_Expression (static_schedule, 658 common); 659 660 build_pbb_scattering_polyhedrons (common, pbb, nb_scat_dims); 661 662 ppl_delete_Linear_Expression (common); 663 } 664 665 value_clear (v); 666 ppl_delete_Coefficient (c); 667 ppl_delete_Linear_Expression (static_schedule); 668} 669 670/* Add the value K to the dimension D of the linear expression EXPR. */ 671 672static void 673add_value_to_dim (ppl_dimension_type d, ppl_Linear_Expression_t expr, 674 Value k) 675{ 676 Value val; 677 ppl_Coefficient_t coef; 678 679 ppl_new_Coefficient (&coef); 680 ppl_Linear_Expression_coefficient (expr, d, coef); 681 value_init (val); 682 ppl_Coefficient_to_mpz_t (coef, val); 683 684 value_addto (val, val, k); 685 686 ppl_assign_Coefficient_from_mpz_t (coef, val); 687 ppl_Linear_Expression_add_to_coefficient (expr, d, coef); 688 value_clear (val); 689 ppl_delete_Coefficient (coef); 690} 691 692/* In the context of scop S, scan E, the right hand side of a scalar 693 evolution function in loop VAR, and translate it to a linear 694 expression EXPR. */ 695 696static void 697scan_tree_for_params_right_scev (sese s, tree e, int var, 698 ppl_Linear_Expression_t expr) 699{ 700 if (expr) 701 { 702 loop_p loop = get_loop (var); 703 ppl_dimension_type l = sese_loop_depth (s, loop) - 1; 704 Value val; 705 706 /* Scalar evolutions should happen in the sese region. */ 707 gcc_assert (sese_loop_depth (s, loop) > 0); 708 709 /* We can not deal with parametric strides like: 710 711 | p = parameter; 712 | 713 | for i: 714 | a [i * p] = ... */ 715 gcc_assert (TREE_CODE (e) == INTEGER_CST); 716 717 value_init (val); 718 tree_int_to_gmp (e, val); 719 add_value_to_dim (l, expr, val); 720 value_clear (val); 721 } 722} 723 724/* Scan the integer constant CST, and add it to the inhomogeneous part of the 725 linear expression EXPR. K is the multiplier of the constant. */ 726 727static void 728scan_tree_for_params_int (tree cst, ppl_Linear_Expression_t expr, Value k) 729{ 730 Value val; 731 ppl_Coefficient_t coef; 732 tree type = TREE_TYPE (cst); 733 734 value_init (val); 735 736 /* Necessary to not get "-1 = 2^n - 1". */ 737 mpz_set_double_int (val, double_int_sext (tree_to_double_int (cst), 738 TYPE_PRECISION (type)), false); 739 740 value_multiply (val, val, k); 741 ppl_new_Coefficient (&coef); 742 ppl_assign_Coefficient_from_mpz_t (coef, val); 743 ppl_Linear_Expression_add_to_inhomogeneous (expr, coef); 744 value_clear (val); 745 ppl_delete_Coefficient (coef); 746} 747 748/* When parameter NAME is in REGION, returns its index in SESE_PARAMS. 749 Otherwise returns -1. */ 750 751static inline int 752parameter_index_in_region_1 (tree name, sese region) 753{ 754 int i; 755 tree p; 756 757 gcc_assert (TREE_CODE (name) == SSA_NAME); 758 759 for (i = 0; VEC_iterate (tree, SESE_PARAMS (region), i, p); i++) 760 if (p == name) 761 return i; 762 763 return -1; 764} 765 766/* When the parameter NAME is in REGION, returns its index in 767 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS 768 and returns the index of NAME. */ 769 770static int 771parameter_index_in_region (tree name, sese region) 772{ 773 int i; 774 775 gcc_assert (TREE_CODE (name) == SSA_NAME); 776 777 i = parameter_index_in_region_1 (name, region); 778 if (i != -1) 779 return i; 780 781 gcc_assert (SESE_ADD_PARAMS (region)); 782 783 i = VEC_length (tree, SESE_PARAMS (region)); 784 VEC_safe_push (tree, heap, SESE_PARAMS (region), name); 785 return i; 786} 787 788/* In the context of sese S, scan the expression E and translate it to 789 a linear expression C. When parsing a symbolic multiplication, K 790 represents the constant multiplier of an expression containing 791 parameters. */ 792 793static void 794scan_tree_for_params (sese s, tree e, ppl_Linear_Expression_t c, 795 Value k) 796{ 797 if (e == chrec_dont_know) 798 return; 799 800 switch (TREE_CODE (e)) 801 { 802 case POLYNOMIAL_CHREC: 803 scan_tree_for_params_right_scev (s, CHREC_RIGHT (e), 804 CHREC_VARIABLE (e), c); 805 scan_tree_for_params (s, CHREC_LEFT (e), c, k); 806 break; 807 808 case MULT_EXPR: 809 if (chrec_contains_symbols (TREE_OPERAND (e, 0))) 810 { 811 if (c) 812 { 813 Value val; 814 gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0)); 815 value_init (val); 816 tree_int_to_gmp (TREE_OPERAND (e, 1), val); 817 value_multiply (val, val, k); 818 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, val); 819 value_clear (val); 820 } 821 else 822 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k); 823 } 824 else 825 { 826 if (c) 827 { 828 Value val; 829 gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0)); 830 value_init (val); 831 tree_int_to_gmp (TREE_OPERAND (e, 0), val); 832 value_multiply (val, val, k); 833 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, val); 834 value_clear (val); 835 } 836 else 837 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k); 838 } 839 break; 840 841 case PLUS_EXPR: 842 case POINTER_PLUS_EXPR: 843 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k); 844 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k); 845 break; 846 847 case MINUS_EXPR: 848 { 849 ppl_Linear_Expression_t tmp_expr = NULL; 850 851 if (c) 852 { 853 ppl_dimension_type dim; 854 ppl_Linear_Expression_space_dimension (c, &dim); 855 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim); 856 } 857 858 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k); 859 scan_tree_for_params (s, TREE_OPERAND (e, 1), tmp_expr, k); 860 861 if (c) 862 { 863 ppl_subtract_Linear_Expression_from_Linear_Expression (c, 864 tmp_expr); 865 ppl_delete_Linear_Expression (tmp_expr); 866 } 867 868 break; 869 } 870 871 case NEGATE_EXPR: 872 { 873 ppl_Linear_Expression_t tmp_expr = NULL; 874 875 if (c) 876 { 877 ppl_dimension_type dim; 878 ppl_Linear_Expression_space_dimension (c, &dim); 879 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim); 880 } 881 882 scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k); 883 884 if (c) 885 { 886 ppl_subtract_Linear_Expression_from_Linear_Expression (c, 887 tmp_expr); 888 ppl_delete_Linear_Expression (tmp_expr); 889 } 890 891 break; 892 } 893 894 case BIT_NOT_EXPR: 895 { 896 ppl_Linear_Expression_t tmp_expr = NULL; 897 898 if (c) 899 { 900 ppl_dimension_type dim; 901 ppl_Linear_Expression_space_dimension (c, &dim); 902 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim); 903 } 904 905 scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k); 906 907 if (c) 908 { 909 ppl_Coefficient_t coef; 910 Value minus_one; 911 912 ppl_subtract_Linear_Expression_from_Linear_Expression (c, 913 tmp_expr); 914 ppl_delete_Linear_Expression (tmp_expr); 915 value_init (minus_one); 916 value_set_si (minus_one, -1); 917 ppl_new_Coefficient_from_mpz_t (&coef, minus_one); 918 ppl_Linear_Expression_add_to_inhomogeneous (c, coef); 919 value_clear (minus_one); 920 ppl_delete_Coefficient (coef); 921 } 922 923 break; 924 } 925 926 case SSA_NAME: 927 { 928 ppl_dimension_type p = parameter_index_in_region (e, s); 929 930 if (c) 931 { 932 ppl_dimension_type dim; 933 ppl_Linear_Expression_space_dimension (c, &dim); 934 p += dim - sese_nb_params (s); 935 add_value_to_dim (p, c, k); 936 } 937 break; 938 } 939 940 case INTEGER_CST: 941 if (c) 942 scan_tree_for_params_int (e, c, k); 943 break; 944 945 CASE_CONVERT: 946 case NON_LVALUE_EXPR: 947 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k); 948 break; 949 950 default: 951 gcc_unreachable (); 952 break; 953 } 954} 955 956/* Find parameters with respect to REGION in BB. We are looking in memory 957 access functions, conditions and loop bounds. */ 958 959static void 960find_params_in_bb (sese region, gimple_bb_p gbb) 961{ 962 int i; 963 unsigned j; 964 data_reference_p dr; 965 gimple stmt; 966 loop_p loop = GBB_BB (gbb)->loop_father; 967 Value one; 968 969 value_init (one); 970 value_set_si (one, 1); 971 972 /* Find parameters in the access functions of data references. */ 973 for (i = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gbb), i, dr); i++) 974 for (j = 0; j < DR_NUM_DIMENSIONS (dr); j++) 975 scan_tree_for_params (region, DR_ACCESS_FN (dr, j), NULL, one); 976 977 /* Find parameters in conditional statements. */ 978 for (i = 0; VEC_iterate (gimple, GBB_CONDITIONS (gbb), i, stmt); i++) 979 { 980 tree lhs = scalar_evolution_in_region (region, loop, 981 gimple_cond_lhs (stmt)); 982 tree rhs = scalar_evolution_in_region (region, loop, 983 gimple_cond_rhs (stmt)); 984 985 scan_tree_for_params (region, lhs, NULL, one); 986 scan_tree_for_params (region, rhs, NULL, one); 987 } 988 989 value_clear (one); 990} 991 992/* Record the parameters used in the SCOP. A variable is a parameter 993 in a scop if it does not vary during the execution of that scop. */ 994 995static void 996find_scop_parameters (scop_p scop) 997{ 998 poly_bb_p pbb; 999 unsigned i; 1000 sese region = SCOP_REGION (scop); 1001 struct loop *loop; 1002 Value one; 1003 1004 value_init (one); 1005 value_set_si (one, 1); 1006 1007 /* Find the parameters used in the loop bounds. */ 1008 for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++) 1009 { 1010 tree nb_iters = number_of_latch_executions (loop); 1011 1012 if (!chrec_contains_symbols (nb_iters)) 1013 continue; 1014 1015 nb_iters = scalar_evolution_in_region (region, loop, nb_iters); 1016 scan_tree_for_params (region, nb_iters, NULL, one); 1017 } 1018 1019 value_clear (one); 1020 1021 /* Find the parameters used in data accesses. */ 1022 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) 1023 find_params_in_bb (region, PBB_BLACK_BOX (pbb)); 1024 1025 scop_set_nb_params (scop, sese_nb_params (region)); 1026 SESE_ADD_PARAMS (region) = false; 1027 1028 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension 1029 (&SCOP_CONTEXT (scop), scop_nb_params (scop), 0); 1030} 1031 1032/* Returns a gimple_bb from BB. */ 1033 1034static inline gimple_bb_p 1035gbb_from_bb (basic_block bb) 1036{ 1037 return (gimple_bb_p) bb->aux; 1038} 1039 1040/* Insert in the SCOP context constraints from the estimation of the 1041 number of iterations. UB_EXPR is a linear expression describing 1042 the number of iterations in a loop. This expression is bounded by 1043 the estimation NIT. */ 1044 1045static void 1046add_upper_bounds_from_estimated_nit (scop_p scop, double_int nit, 1047 ppl_dimension_type dim, 1048 ppl_Linear_Expression_t ub_expr) 1049{ 1050 Value val; 1051 ppl_Linear_Expression_t nb_iters_le; 1052 ppl_Polyhedron_t pol; 1053 ppl_Coefficient_t coef; 1054 ppl_Constraint_t ub; 1055 1056 ppl_new_Linear_Expression_with_dimension (&ub_expr, dim); 1057 ppl_new_C_Polyhedron_from_space_dimension (&pol, dim, 0); 1058 ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le, 1059 ub_expr); 1060 1061 /* Construct the negated number of last iteration in VAL. */ 1062 value_init (val); 1063 mpz_set_double_int (val, nit, false); 1064 value_sub_int (val, val, 1); 1065 value_oppose (val, val); 1066 1067 /* NB_ITERS_LE holds the number of last iteration in 1068 parametrical form. Subtract estimated number of last 1069 iteration and assert that result is not positive. */ 1070 ppl_new_Coefficient_from_mpz_t (&coef, val); 1071 ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le, coef); 1072 ppl_delete_Coefficient (coef); 1073 ppl_new_Constraint (&ub, nb_iters_le, 1074 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL); 1075 ppl_Polyhedron_add_constraint (pol, ub); 1076 1077 /* Remove all but last GDIM dimensions from POL to obtain 1078 only the constraints on the parameters. */ 1079 { 1080 graphite_dim_t gdim = scop_nb_params (scop); 1081 ppl_dimension_type *dims = XNEWVEC (ppl_dimension_type, dim - gdim); 1082 graphite_dim_t i; 1083 1084 for (i = 0; i < dim - gdim; i++) 1085 dims[i] = i; 1086 1087 ppl_Polyhedron_remove_space_dimensions (pol, dims, dim - gdim); 1088 XDELETEVEC (dims); 1089 } 1090 1091 /* Add the constraints on the parameters to the SCoP context. */ 1092 { 1093 ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps; 1094 1095 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron 1096 (&constraints_ps, pol); 1097 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign 1098 (SCOP_CONTEXT (scop), constraints_ps); 1099 ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps); 1100 } 1101 1102 ppl_delete_Polyhedron (pol); 1103 ppl_delete_Linear_Expression (nb_iters_le); 1104 ppl_delete_Constraint (ub); 1105 value_clear (val); 1106} 1107 1108/* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives 1109 the constraints for the surrounding loops. */ 1110 1111static void 1112build_loop_iteration_domains (scop_p scop, struct loop *loop, 1113 ppl_Polyhedron_t outer_ph, int nb, 1114 ppl_Pointset_Powerset_C_Polyhedron_t *domains) 1115{ 1116 int i; 1117 ppl_Polyhedron_t ph; 1118 tree nb_iters = number_of_latch_executions (loop); 1119 ppl_dimension_type dim = nb + 1 + scop_nb_params (scop); 1120 sese region = SCOP_REGION (scop); 1121 1122 { 1123 ppl_const_Constraint_System_t pcs; 1124 ppl_dimension_type *map 1125 = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim); 1126 1127 ppl_new_C_Polyhedron_from_space_dimension (&ph, dim, 0); 1128 ppl_Polyhedron_get_constraints (outer_ph, &pcs); 1129 ppl_Polyhedron_add_constraints (ph, pcs); 1130 1131 for (i = 0; i < (int) nb; i++) 1132 map[i] = i; 1133 for (i = (int) nb; i < (int) dim - 1; i++) 1134 map[i] = i + 1; 1135 map[dim - 1] = nb; 1136 1137 ppl_Polyhedron_map_space_dimensions (ph, map, dim); 1138 free (map); 1139 } 1140 1141 /* 0 <= loop_i */ 1142 { 1143 ppl_Constraint_t lb; 1144 ppl_Linear_Expression_t lb_expr; 1145 1146 ppl_new_Linear_Expression_with_dimension (&lb_expr, dim); 1147 ppl_set_coef (lb_expr, nb, 1); 1148 ppl_new_Constraint (&lb, lb_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); 1149 ppl_delete_Linear_Expression (lb_expr); 1150 ppl_Polyhedron_add_constraint (ph, lb); 1151 ppl_delete_Constraint (lb); 1152 } 1153 1154 if (TREE_CODE (nb_iters) == INTEGER_CST) 1155 { 1156 ppl_Constraint_t ub; 1157 ppl_Linear_Expression_t ub_expr; 1158 1159 ppl_new_Linear_Expression_with_dimension (&ub_expr, dim); 1160 1161 /* loop_i <= cst_nb_iters */ 1162 ppl_set_coef (ub_expr, nb, -1); 1163 ppl_set_inhomogeneous_tree (ub_expr, nb_iters); 1164 ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); 1165 ppl_Polyhedron_add_constraint (ph, ub); 1166 ppl_delete_Linear_Expression (ub_expr); 1167 ppl_delete_Constraint (ub); 1168 } 1169 else if (!chrec_contains_undetermined (nb_iters)) 1170 { 1171 Value one; 1172 ppl_Constraint_t ub; 1173 ppl_Linear_Expression_t ub_expr; 1174 double_int nit; 1175 1176 value_init (one); 1177 value_set_si (one, 1); 1178 ppl_new_Linear_Expression_with_dimension (&ub_expr, dim); 1179 nb_iters = scalar_evolution_in_region (region, loop, nb_iters); 1180 scan_tree_for_params (SCOP_REGION (scop), nb_iters, ub_expr, one); 1181 value_clear (one); 1182 1183 if (estimated_loop_iterations (loop, true, &nit)) 1184 add_upper_bounds_from_estimated_nit (scop, nit, dim, ub_expr); 1185 1186 /* loop_i <= expr_nb_iters */ 1187 ppl_set_coef (ub_expr, nb, -1); 1188 ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); 1189 ppl_Polyhedron_add_constraint (ph, ub); 1190 ppl_delete_Linear_Expression (ub_expr); 1191 ppl_delete_Constraint (ub); 1192 } 1193 else 1194 gcc_unreachable (); 1195 1196 if (loop->inner && loop_in_sese_p (loop->inner, region)) 1197 build_loop_iteration_domains (scop, loop->inner, ph, nb + 1, domains); 1198 1199 if (nb != 0 1200 && loop->next 1201 && loop_in_sese_p (loop->next, region)) 1202 build_loop_iteration_domains (scop, loop->next, outer_ph, nb, domains); 1203 1204 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron 1205 (&domains[loop->num], ph); 1206 1207 ppl_delete_Polyhedron (ph); 1208} 1209 1210/* Returns a linear expression for tree T evaluated in PBB. */ 1211 1212static ppl_Linear_Expression_t 1213create_linear_expr_from_tree (poly_bb_p pbb, tree t) 1214{ 1215 Value one; 1216 ppl_Linear_Expression_t res; 1217 ppl_dimension_type dim; 1218 sese region = SCOP_REGION (PBB_SCOP (pbb)); 1219 loop_p loop = pbb_loop (pbb); 1220 1221 dim = pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb); 1222 ppl_new_Linear_Expression_with_dimension (&res, dim); 1223 1224 t = scalar_evolution_in_region (region, loop, t); 1225 gcc_assert (!automatically_generated_chrec_p (t)); 1226 1227 value_init (one); 1228 value_set_si (one, 1); 1229 scan_tree_for_params (region, t, res, one); 1230 value_clear (one); 1231 1232 return res; 1233} 1234 1235/* Returns the ppl constraint type from the gimple tree code CODE. */ 1236 1237static enum ppl_enum_Constraint_Type 1238ppl_constraint_type_from_tree_code (enum tree_code code) 1239{ 1240 switch (code) 1241 { 1242 /* We do not support LT and GT to be able to work with C_Polyhedron. 1243 As we work on integer polyhedron "a < b" can be expressed by 1244 "a + 1 <= b". */ 1245 case LT_EXPR: 1246 case GT_EXPR: 1247 gcc_unreachable (); 1248 1249 case LE_EXPR: 1250 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL; 1251 1252 case GE_EXPR: 1253 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL; 1254 1255 case EQ_EXPR: 1256 return PPL_CONSTRAINT_TYPE_EQUAL; 1257 1258 default: 1259 gcc_unreachable (); 1260 } 1261} 1262 1263/* Add conditional statement STMT to PS. It is evaluated in PBB and 1264 CODE is used as the comparison operator. This allows us to invert the 1265 condition or to handle inequalities. */ 1266 1267static void 1268add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps, gimple stmt, 1269 poly_bb_p pbb, enum tree_code code) 1270{ 1271 Value v; 1272 ppl_Coefficient_t c; 1273 ppl_Linear_Expression_t left, right; 1274 ppl_Constraint_t cstr; 1275 enum ppl_enum_Constraint_Type type; 1276 1277 left = create_linear_expr_from_tree (pbb, gimple_cond_lhs (stmt)); 1278 right = create_linear_expr_from_tree (pbb, gimple_cond_rhs (stmt)); 1279 1280 /* If we have < or > expressions convert them to <= or >= by adding 1 to 1281 the left or the right side of the expression. */ 1282 if (code == LT_EXPR) 1283 { 1284 value_init (v); 1285 value_set_si (v, 1); 1286 ppl_new_Coefficient (&c); 1287 ppl_assign_Coefficient_from_mpz_t (c, v); 1288 ppl_Linear_Expression_add_to_inhomogeneous (left, c); 1289 ppl_delete_Coefficient (c); 1290 value_clear (v); 1291 1292 code = LE_EXPR; 1293 } 1294 else if (code == GT_EXPR) 1295 { 1296 value_init (v); 1297 value_set_si (v, 1); 1298 ppl_new_Coefficient (&c); 1299 ppl_assign_Coefficient_from_mpz_t (c, v); 1300 ppl_Linear_Expression_add_to_inhomogeneous (right, c); 1301 ppl_delete_Coefficient (c); 1302 value_clear (v); 1303 1304 code = GE_EXPR; 1305 } 1306 1307 type = ppl_constraint_type_from_tree_code (code); 1308 1309 ppl_subtract_Linear_Expression_from_Linear_Expression (left, right); 1310 1311 ppl_new_Constraint (&cstr, left, type); 1312 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps, cstr); 1313 1314 ppl_delete_Constraint (cstr); 1315 ppl_delete_Linear_Expression (left); 1316 ppl_delete_Linear_Expression (right); 1317} 1318 1319/* Add conditional statement STMT to pbb. CODE is used as the comparision 1320 operator. This allows us to invert the condition or to handle 1321 inequalities. */ 1322 1323static void 1324add_condition_to_pbb (poly_bb_p pbb, gimple stmt, enum tree_code code) 1325{ 1326 if (code == NE_EXPR) 1327 { 1328 ppl_Pointset_Powerset_C_Polyhedron_t left = PBB_DOMAIN (pbb); 1329 ppl_Pointset_Powerset_C_Polyhedron_t right; 1330 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron 1331 (&right, left); 1332 add_condition_to_domain (left, stmt, pbb, LT_EXPR); 1333 add_condition_to_domain (right, stmt, pbb, GT_EXPR); 1334 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left, 1335 right); 1336 ppl_delete_Pointset_Powerset_C_Polyhedron (right); 1337 } 1338 else 1339 add_condition_to_domain (PBB_DOMAIN (pbb), stmt, pbb, code); 1340} 1341 1342/* Add conditions to the domain of PBB. */ 1343 1344static void 1345add_conditions_to_domain (poly_bb_p pbb) 1346{ 1347 unsigned int i; 1348 gimple stmt; 1349 gimple_bb_p gbb = PBB_BLACK_BOX (pbb); 1350 VEC (gimple, heap) *conditions = GBB_CONDITIONS (gbb); 1351 1352 if (VEC_empty (gimple, conditions)) 1353 return; 1354 1355 for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++) 1356 switch (gimple_code (stmt)) 1357 { 1358 case GIMPLE_COND: 1359 { 1360 enum tree_code code = gimple_cond_code (stmt); 1361 1362 /* The conditions for ELSE-branches are inverted. */ 1363 if (VEC_index (gimple, gbb->condition_cases, i) == NULL) 1364 code = invert_tree_comparison (code, false); 1365 1366 add_condition_to_pbb (pbb, stmt, code); 1367 break; 1368 } 1369 1370 case GIMPLE_SWITCH: 1371 /* Switch statements are not supported right now - fall throught. */ 1372 1373 default: 1374 gcc_unreachable (); 1375 break; 1376 } 1377} 1378 1379/* Structure used to pass data to dom_walk. */ 1380 1381struct bsc 1382{ 1383 VEC (gimple, heap) **conditions, **cases; 1384 sese region; 1385}; 1386 1387/* Returns non NULL when BB has a single predecessor and the last 1388 statement of that predecessor is a COND_EXPR. */ 1389 1390static gimple 1391single_pred_cond (basic_block bb) 1392{ 1393 if (single_pred_p (bb)) 1394 { 1395 edge e = single_pred_edge (bb); 1396 basic_block pred = e->src; 1397 gimple stmt = last_stmt (pred); 1398 1399 if (stmt && gimple_code (stmt) == GIMPLE_COND) 1400 return stmt; 1401 } 1402 return NULL; 1403} 1404 1405/* Call-back for dom_walk executed before visiting the dominated 1406 blocks. */ 1407 1408static void 1409build_sese_conditions_before (struct dom_walk_data *dw_data, 1410 basic_block bb) 1411{ 1412 struct bsc *data = (struct bsc *) dw_data->global_data; 1413 VEC (gimple, heap) **conditions = data->conditions; 1414 VEC (gimple, heap) **cases = data->cases; 1415 gimple_bb_p gbb = gbb_from_bb (bb); 1416 gimple stmt = single_pred_cond (bb); 1417 1418 if (!bb_in_sese_p (bb, data->region)) 1419 return; 1420 1421 if (stmt) 1422 { 1423 edge e = single_pred_edge (bb); 1424 1425 VEC_safe_push (gimple, heap, *conditions, stmt); 1426 1427 if (e->flags & EDGE_TRUE_VALUE) 1428 VEC_safe_push (gimple, heap, *cases, stmt); 1429 else 1430 VEC_safe_push (gimple, heap, *cases, NULL); 1431 } 1432 1433 if (gbb) 1434 { 1435 GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions); 1436 GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases); 1437 } 1438} 1439 1440/* Call-back for dom_walk executed after visiting the dominated 1441 blocks. */ 1442 1443static void 1444build_sese_conditions_after (struct dom_walk_data *dw_data, 1445 basic_block bb) 1446{ 1447 struct bsc *data = (struct bsc *) dw_data->global_data; 1448 VEC (gimple, heap) **conditions = data->conditions; 1449 VEC (gimple, heap) **cases = data->cases; 1450 1451 if (!bb_in_sese_p (bb, data->region)) 1452 return; 1453 1454 if (single_pred_cond (bb)) 1455 { 1456 VEC_pop (gimple, *conditions); 1457 VEC_pop (gimple, *cases); 1458 } 1459} 1460 1461/* Record all conditions in REGION. */ 1462 1463static void 1464build_sese_conditions (sese region) 1465{ 1466 struct dom_walk_data walk_data; 1467 VEC (gimple, heap) *conditions = VEC_alloc (gimple, heap, 3); 1468 VEC (gimple, heap) *cases = VEC_alloc (gimple, heap, 3); 1469 struct bsc data; 1470 1471 data.conditions = &conditions; 1472 data.cases = &cases; 1473 data.region = region; 1474 1475 walk_data.dom_direction = CDI_DOMINATORS; 1476 walk_data.initialize_block_local_data = NULL; 1477 walk_data.before_dom_children = build_sese_conditions_before; 1478 walk_data.after_dom_children = build_sese_conditions_after; 1479 walk_data.global_data = &data; 1480 walk_data.block_local_data_size = 0; 1481 1482 init_walk_dominator_tree (&walk_data); 1483 walk_dominator_tree (&walk_data, SESE_ENTRY_BB (region)); 1484 fini_walk_dominator_tree (&walk_data); 1485 1486 VEC_free (gimple, heap, conditions); 1487 VEC_free (gimple, heap, cases); 1488} 1489 1490/* Traverses all the GBBs of the SCOP and add their constraints to the 1491 iteration domains. */ 1492 1493static void 1494add_conditions_to_constraints (scop_p scop) 1495{ 1496 int i; 1497 poly_bb_p pbb; 1498 1499 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) 1500 add_conditions_to_domain (pbb); 1501} 1502 1503/* Add constraints on the possible values of parameter P from the type 1504 of P. */ 1505 1506static void 1507add_param_constraints (scop_p scop, ppl_Polyhedron_t context, graphite_dim_t p) 1508{ 1509 ppl_Constraint_t cstr; 1510 ppl_Linear_Expression_t le; 1511 tree parameter = VEC_index (tree, SESE_PARAMS (SCOP_REGION (scop)), p); 1512 tree type = TREE_TYPE (parameter); 1513 tree lb = NULL_TREE; 1514 tree ub = NULL_TREE; 1515 1516 if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type)) 1517 lb = lower_bound_in_type (type, type); 1518 else 1519 lb = TYPE_MIN_VALUE (type); 1520 1521 if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type)) 1522 ub = upper_bound_in_type (type, type); 1523 else 1524 ub = TYPE_MAX_VALUE (type); 1525 1526 if (lb) 1527 { 1528 ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop)); 1529 ppl_set_coef (le, p, -1); 1530 ppl_set_inhomogeneous_tree (le, lb); 1531 ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL); 1532 ppl_Polyhedron_add_constraint (context, cstr); 1533 ppl_delete_Linear_Expression (le); 1534 ppl_delete_Constraint (cstr); 1535 } 1536 1537 if (ub) 1538 { 1539 ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop)); 1540 ppl_set_coef (le, p, -1); 1541 ppl_set_inhomogeneous_tree (le, ub); 1542 ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); 1543 ppl_Polyhedron_add_constraint (context, cstr); 1544 ppl_delete_Linear_Expression (le); 1545 ppl_delete_Constraint (cstr); 1546 } 1547} 1548 1549/* Build the context of the SCOP. The context usually contains extra 1550 constraints that are added to the iteration domains that constrain 1551 some parameters. */ 1552 1553static void 1554build_scop_context (scop_p scop) 1555{ 1556 ppl_Polyhedron_t context; 1557 ppl_Pointset_Powerset_C_Polyhedron_t ps; 1558 graphite_dim_t p, n = scop_nb_params (scop); 1559 1560 ppl_new_C_Polyhedron_from_space_dimension (&context, n, 0); 1561 1562 for (p = 0; p < n; p++) 1563 add_param_constraints (scop, context, p); 1564 1565 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron 1566 (&ps, context); 1567 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign 1568 (SCOP_CONTEXT (scop), ps); 1569 1570 ppl_delete_Pointset_Powerset_C_Polyhedron (ps); 1571 ppl_delete_Polyhedron (context); 1572} 1573 1574/* Build the iteration domains: the loops belonging to the current 1575 SCOP, and that vary for the execution of the current basic block. 1576 Returns false if there is no loop in SCOP. */ 1577 1578static void 1579build_scop_iteration_domain (scop_p scop) 1580{ 1581 struct loop *loop; 1582 sese region = SCOP_REGION (scop); 1583 int i; 1584 ppl_Polyhedron_t ph; 1585 poly_bb_p pbb; 1586 int nb_loops = number_of_loops (); 1587 ppl_Pointset_Powerset_C_Polyhedron_t *domains 1588 = XNEWVEC (ppl_Pointset_Powerset_C_Polyhedron_t, nb_loops); 1589 1590 for (i = 0; i < nb_loops; i++) 1591 domains[i] = NULL; 1592 1593 ppl_new_C_Polyhedron_from_space_dimension (&ph, scop_nb_params (scop), 0); 1594 1595 for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++) 1596 if (!loop_in_sese_p (loop_outer (loop), region)) 1597 build_loop_iteration_domains (scop, loop, ph, 0, domains); 1598 1599 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) 1600 if (domains[gbb_loop (PBB_BLACK_BOX (pbb))->num]) 1601 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron 1602 (&PBB_DOMAIN (pbb), (ppl_const_Pointset_Powerset_C_Polyhedron_t) 1603 domains[gbb_loop (PBB_BLACK_BOX (pbb))->num]); 1604 else 1605 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron 1606 (&PBB_DOMAIN (pbb), ph); 1607 1608 for (i = 0; i < nb_loops; i++) 1609 if (domains[i]) 1610 ppl_delete_Pointset_Powerset_C_Polyhedron (domains[i]); 1611 1612 ppl_delete_Polyhedron (ph); 1613 free (domains); 1614} 1615 1616/* Add a constrain to the ACCESSES polyhedron for the alias set of 1617 data reference DR. ACCESSP_NB_DIMS is the dimension of the 1618 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration 1619 domain. */ 1620 1621static void 1622pdr_add_alias_set (ppl_Polyhedron_t accesses, data_reference_p dr, 1623 ppl_dimension_type accessp_nb_dims, 1624 ppl_dimension_type dom_nb_dims) 1625{ 1626 ppl_Linear_Expression_t alias; 1627 ppl_Constraint_t cstr; 1628 int alias_set_num = 0; 1629 base_alias_pair *bap = (base_alias_pair *)(dr->aux); 1630 1631 if (bap && bap->alias_set) 1632 alias_set_num = *(bap->alias_set); 1633 1634 ppl_new_Linear_Expression_with_dimension (&alias, accessp_nb_dims); 1635 1636 ppl_set_coef (alias, dom_nb_dims, 1); 1637 ppl_set_inhomogeneous (alias, -alias_set_num); 1638 ppl_new_Constraint (&cstr, alias, PPL_CONSTRAINT_TYPE_EQUAL); 1639 ppl_Polyhedron_add_constraint (accesses, cstr); 1640 1641 ppl_delete_Linear_Expression (alias); 1642 ppl_delete_Constraint (cstr); 1643} 1644 1645/* Add to ACCESSES polyhedron equalities defining the access functions 1646 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES 1647 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain. 1648 PBB is the poly_bb_p that contains the data reference DR. */ 1649 1650static void 1651pdr_add_memory_accesses (ppl_Polyhedron_t accesses, data_reference_p dr, 1652 ppl_dimension_type accessp_nb_dims, 1653 ppl_dimension_type dom_nb_dims, 1654 poly_bb_p pbb) 1655{ 1656 int i, nb_subscripts = DR_NUM_DIMENSIONS (dr); 1657 Value v; 1658 scop_p scop = PBB_SCOP (pbb); 1659 sese region = SCOP_REGION (scop); 1660 1661 value_init (v); 1662 1663 for (i = 0; i < nb_subscripts; i++) 1664 { 1665 ppl_Linear_Expression_t fn, access; 1666 ppl_Constraint_t cstr; 1667 ppl_dimension_type subscript = dom_nb_dims + 1 + i; 1668 tree afn = DR_ACCESS_FN (dr, nb_subscripts - 1 - i); 1669 1670 ppl_new_Linear_Expression_with_dimension (&fn, dom_nb_dims); 1671 ppl_new_Linear_Expression_with_dimension (&access, accessp_nb_dims); 1672 1673 value_set_si (v, 1); 1674 scan_tree_for_params (region, afn, fn, v); 1675 ppl_assign_Linear_Expression_from_Linear_Expression (access, fn); 1676 1677 ppl_set_coef (access, subscript, -1); 1678 ppl_new_Constraint (&cstr, access, PPL_CONSTRAINT_TYPE_EQUAL); 1679 ppl_Polyhedron_add_constraint (accesses, cstr); 1680 1681 ppl_delete_Linear_Expression (fn); 1682 ppl_delete_Linear_Expression (access); 1683 ppl_delete_Constraint (cstr); 1684 } 1685 1686 value_clear (v); 1687} 1688 1689/* Add constrains representing the size of the accessed data to the 1690 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the 1691 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration 1692 domain. */ 1693 1694static void 1695pdr_add_data_dimensions (ppl_Polyhedron_t accesses, data_reference_p dr, 1696 ppl_dimension_type accessp_nb_dims, 1697 ppl_dimension_type dom_nb_dims) 1698{ 1699 tree ref = DR_REF (dr); 1700 int i, nb_subscripts = DR_NUM_DIMENSIONS (dr); 1701 1702 for (i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0)) 1703 { 1704 ppl_Linear_Expression_t expr; 1705 ppl_Constraint_t cstr; 1706 ppl_dimension_type subscript = dom_nb_dims + 1 + i; 1707 tree low, high; 1708 1709 if (TREE_CODE (ref) != ARRAY_REF) 1710 break; 1711 1712 low = array_ref_low_bound (ref); 1713 1714 /* subscript - low >= 0 */ 1715 if (host_integerp (low, 0)) 1716 { 1717 tree minus_low; 1718 1719 ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims); 1720 ppl_set_coef (expr, subscript, 1); 1721 1722 minus_low = fold_build1 (NEGATE_EXPR, TREE_TYPE (low), low); 1723 ppl_set_inhomogeneous_tree (expr, minus_low); 1724 1725 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); 1726 ppl_Polyhedron_add_constraint (accesses, cstr); 1727 ppl_delete_Linear_Expression (expr); 1728 ppl_delete_Constraint (cstr); 1729 } 1730 1731 high = array_ref_up_bound (ref); 1732 1733 /* high - subscript >= 0 */ 1734 if (high && host_integerp (high, 0) 1735 /* 1-element arrays at end of structures may extend over 1736 their declared size. */ 1737 && !(array_at_struct_end_p (ref) 1738 && operand_equal_p (low, high, 0))) 1739 { 1740 ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims); 1741 ppl_set_coef (expr, subscript, -1); 1742 1743 ppl_set_inhomogeneous_tree (expr, high); 1744 1745 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); 1746 ppl_Polyhedron_add_constraint (accesses, cstr); 1747 ppl_delete_Linear_Expression (expr); 1748 ppl_delete_Constraint (cstr); 1749 } 1750 } 1751} 1752 1753/* Build data accesses for DR in PBB. */ 1754 1755static void 1756build_poly_dr (data_reference_p dr, poly_bb_p pbb) 1757{ 1758 ppl_Polyhedron_t accesses; 1759 ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps; 1760 ppl_dimension_type dom_nb_dims; 1761 ppl_dimension_type accessp_nb_dims; 1762 int dr_base_object_set; 1763 1764 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb), 1765 &dom_nb_dims); 1766 accessp_nb_dims = dom_nb_dims + 1 + DR_NUM_DIMENSIONS (dr); 1767 1768 ppl_new_C_Polyhedron_from_space_dimension (&accesses, accessp_nb_dims, 0); 1769 1770 pdr_add_alias_set (accesses, dr, accessp_nb_dims, dom_nb_dims); 1771 pdr_add_memory_accesses (accesses, dr, accessp_nb_dims, dom_nb_dims, pbb); 1772 pdr_add_data_dimensions (accesses, dr, accessp_nb_dims, dom_nb_dims); 1773 1774 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps, 1775 accesses); 1776 ppl_delete_Polyhedron (accesses); 1777 1778 if (dr->aux) 1779 dr_base_object_set = ((base_alias_pair *)(dr->aux))->base_obj_set; 1780 1781 new_poly_dr (pbb, dr_base_object_set, accesses_ps, DR_IS_READ (dr) ? PDR_READ : PDR_WRITE, 1782 dr, DR_NUM_DIMENSIONS (dr)); 1783} 1784 1785/* Write to FILE the alias graph of data references in DIMACS format. */ 1786 1787static inline bool 1788write_alias_graph_to_ascii_dimacs (FILE *file, char *comment, 1789 VEC (data_reference_p, heap) *drs) 1790{ 1791 int num_vertex = VEC_length (data_reference_p, drs); 1792 int edge_num = 0; 1793 data_reference_p dr1, dr2; 1794 int i, j; 1795 1796 if (num_vertex == 0) 1797 return true; 1798 1799 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++) 1800 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++) 1801 if (dr_may_alias_p (dr1, dr2)) 1802 edge_num++; 1803 1804 fprintf (file, "$\n"); 1805 1806 if (comment) 1807 fprintf (file, "c %s\n", comment); 1808 1809 fprintf (file, "p edge %d %d\n", num_vertex, edge_num); 1810 1811 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++) 1812 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++) 1813 if (dr_may_alias_p (dr1, dr2)) 1814 fprintf (file, "e %d %d\n", i + 1, j + 1); 1815 1816 return true; 1817} 1818 1819/* Write to FILE the alias graph of data references in DOT format. */ 1820 1821static inline bool 1822write_alias_graph_to_ascii_dot (FILE *file, char *comment, 1823 VEC (data_reference_p, heap) *drs) 1824{ 1825 int num_vertex = VEC_length (data_reference_p, drs); 1826 data_reference_p dr1, dr2; 1827 int i, j; 1828 1829 if (num_vertex == 0) 1830 return true; 1831 1832 fprintf (file, "$\n"); 1833 1834 if (comment) 1835 fprintf (file, "c %s\n", comment); 1836 1837 /* First print all the vertices. */ 1838 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++) 1839 fprintf (file, "n%d;\n", i); 1840 1841 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++) 1842 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++) 1843 if (dr_may_alias_p (dr1, dr2)) 1844 fprintf (file, "n%d n%d\n", i, j); 1845 1846 return true; 1847} 1848 1849/* Write to FILE the alias graph of data references in ECC format. */ 1850 1851static inline bool 1852write_alias_graph_to_ascii_ecc (FILE *file, char *comment, 1853 VEC (data_reference_p, heap) *drs) 1854{ 1855 int num_vertex = VEC_length (data_reference_p, drs); 1856 data_reference_p dr1, dr2; 1857 int i, j; 1858 1859 if (num_vertex == 0) 1860 return true; 1861 1862 fprintf (file, "$\n"); 1863 1864 if (comment) 1865 fprintf (file, "c %s\n", comment); 1866 1867 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++) 1868 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++) 1869 if (dr_may_alias_p (dr1, dr2)) 1870 fprintf (file, "%d %d\n", i, j); 1871 1872 return true; 1873} 1874 1875/* Check if DR1 and DR2 are in the same object set. */ 1876 1877static bool 1878dr_same_base_object_p (const struct data_reference *dr1, 1879 const struct data_reference *dr2) 1880{ 1881 return operand_equal_p (DR_BASE_OBJECT (dr1), DR_BASE_OBJECT (dr2), 0); 1882} 1883 1884/* Uses DFS component number as representative of alias-sets. Also tests for 1885 optimality by verifying if every connected component is a clique. Returns 1886 true (1) if the above test is true, and false (0) otherwise. */ 1887 1888static int 1889build_alias_set_optimal_p (VEC (data_reference_p, heap) *drs) 1890{ 1891 int num_vertices = VEC_length (data_reference_p, drs); 1892 struct graph *g = new_graph (num_vertices); 1893 data_reference_p dr1, dr2; 1894 int i, j; 1895 int num_connected_components; 1896 int v_indx1, v_indx2, num_vertices_in_component; 1897 int *all_vertices; 1898 int *vertices; 1899 struct graph_edge *e; 1900 int this_component_is_clique; 1901 int all_components_are_cliques = 1; 1902 1903 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++) 1904 for (j = i+1; VEC_iterate (data_reference_p, drs, j, dr2); j++) 1905 if (dr_may_alias_p (dr1, dr2)) 1906 { 1907 add_edge (g, i, j); 1908 add_edge (g, j, i); 1909 } 1910 1911 all_vertices = XNEWVEC (int, num_vertices); 1912 vertices = XNEWVEC (int, num_vertices); 1913 for (i = 0; i < num_vertices; i++) 1914 all_vertices[i] = i; 1915 1916 num_connected_components = graphds_dfs (g, all_vertices, num_vertices, 1917 NULL, true, NULL); 1918 for (i = 0; i < g->n_vertices; i++) 1919 { 1920 data_reference_p dr = VEC_index (data_reference_p, drs, i); 1921 base_alias_pair *bap; 1922 1923 if (dr->aux) 1924 bap = (base_alias_pair *)(dr->aux); 1925 1926 bap->alias_set = XNEW (int); 1927 *(bap->alias_set) = g->vertices[i].component + 1; 1928 } 1929 1930 /* Verify if the DFS numbering results in optimal solution. */ 1931 for (i = 0; i < num_connected_components; i++) 1932 { 1933 num_vertices_in_component = 0; 1934 /* Get all vertices whose DFS component number is the same as i. */ 1935 for (j = 0; j < num_vertices; j++) 1936 if (g->vertices[j].component == i) 1937 vertices[num_vertices_in_component++] = j; 1938 1939 /* Now test if the vertices in 'vertices' form a clique, by testing 1940 for edges among each pair. */ 1941 this_component_is_clique = 1; 1942 for (v_indx1 = 0; v_indx1 < num_vertices_in_component; v_indx1++) 1943 { 1944 for (v_indx2 = v_indx1+1; v_indx2 < num_vertices_in_component; v_indx2++) 1945 { 1946 /* Check if the two vertices are connected by iterating 1947 through all the edges which have one of these are source. */ 1948 e = g->vertices[vertices[v_indx2]].pred; 1949 while (e) 1950 { 1951 if (e->src == vertices[v_indx1]) 1952 break; 1953 e = e->pred_next; 1954 } 1955 if (!e) 1956 { 1957 this_component_is_clique = 0; 1958 break; 1959 } 1960 } 1961 if (!this_component_is_clique) 1962 all_components_are_cliques = 0; 1963 } 1964 } 1965 1966 free (all_vertices); 1967 free (vertices); 1968 free_graph (g); 1969 return all_components_are_cliques; 1970} 1971 1972/* Group each data reference in DRS with it's base object set num. */ 1973 1974static void 1975build_base_obj_set_for_drs (VEC (data_reference_p, heap) *drs) 1976{ 1977 int num_vertex = VEC_length (data_reference_p, drs); 1978 struct graph *g = new_graph (num_vertex); 1979 data_reference_p dr1, dr2; 1980 int i, j; 1981 int *queue; 1982 1983 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++) 1984 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++) 1985 if (dr_same_base_object_p (dr1, dr2)) 1986 { 1987 add_edge (g, i, j); 1988 add_edge (g, j, i); 1989 } 1990 1991 queue = XNEWVEC (int, num_vertex); 1992 for (i = 0; i < num_vertex; i++) 1993 queue[i] = i; 1994 1995 graphds_dfs (g, queue, num_vertex, NULL, true, NULL); 1996 1997 for (i = 0; i < g->n_vertices; i++) 1998 { 1999 data_reference_p dr = VEC_index (data_reference_p, drs, i); 2000 base_alias_pair *bap; 2001 2002 if (dr->aux) 2003 bap = (base_alias_pair *)(dr->aux); 2004 2005 bap->base_obj_set = g->vertices[i].component + 1; 2006 } 2007 2008 free (queue); 2009 free_graph (g); 2010} 2011 2012/* Build the data references for PBB. */ 2013 2014static void 2015build_pbb_drs (poly_bb_p pbb) 2016{ 2017 int j; 2018 data_reference_p dr; 2019 VEC (data_reference_p, heap) *gbb_drs = GBB_DATA_REFS (PBB_BLACK_BOX (pbb)); 2020 2021 for (j = 0; VEC_iterate (data_reference_p, gbb_drs, j, dr); j++) 2022 build_poly_dr (dr, pbb); 2023} 2024 2025/* Dump to file the alias graphs for the data references in DRS. */ 2026 2027static void 2028dump_alias_graphs (VEC (data_reference_p, heap) *drs) 2029{ 2030 char comment[100]; 2031 FILE *file_dimacs, *file_ecc, *file_dot; 2032 2033 file_dimacs = fopen ("/tmp/dr_alias_graph_dimacs", "ab"); 2034 if (file_dimacs) 2035 { 2036 snprintf (comment, sizeof (comment), "%s %s", main_input_filename, 2037 current_function_name ()); 2038 write_alias_graph_to_ascii_dimacs (file_dimacs, comment, drs); 2039 fclose (file_dimacs); 2040 } 2041 2042 file_ecc = fopen ("/tmp/dr_alias_graph_ecc", "ab"); 2043 if (file_ecc) 2044 { 2045 snprintf (comment, sizeof (comment), "%s %s", main_input_filename, 2046 current_function_name ()); 2047 write_alias_graph_to_ascii_ecc (file_ecc, comment, drs); 2048 fclose (file_ecc); 2049 } 2050 2051 file_dot = fopen ("/tmp/dr_alias_graph_dot", "ab"); 2052 if (file_dot) 2053 { 2054 snprintf (comment, sizeof (comment), "%s %s", main_input_filename, 2055 current_function_name ()); 2056 write_alias_graph_to_ascii_dot (file_dot, comment, drs); 2057 fclose (file_dot); 2058 } 2059} 2060 2061/* Build data references in SCOP. */ 2062 2063static void 2064build_scop_drs (scop_p scop) 2065{ 2066 int i, j; 2067 poly_bb_p pbb; 2068 data_reference_p dr; 2069 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3); 2070 2071 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) 2072 for (j = 0; VEC_iterate (data_reference_p, 2073 GBB_DATA_REFS (PBB_BLACK_BOX (pbb)), j, dr); j++) 2074 VEC_safe_push (data_reference_p, heap, drs, dr); 2075 2076 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr); i++) 2077 dr->aux = XNEW (base_alias_pair); 2078 2079 if (!build_alias_set_optimal_p (drs)) 2080 { 2081 /* TODO: Add support when building alias set is not optimal. */ 2082 ; 2083 } 2084 2085 build_base_obj_set_for_drs (drs); 2086 2087 /* When debugging, enable the following code. This cannot be used 2088 in production compilers. */ 2089 if (0) 2090 dump_alias_graphs (drs); 2091 2092 VEC_free (data_reference_p, heap, drs); 2093 2094 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) 2095 build_pbb_drs (pbb); 2096} 2097 2098/* Return a gsi at the position of the phi node STMT. */ 2099 2100static gimple_stmt_iterator 2101gsi_for_phi_node (gimple stmt) 2102{ 2103 gimple_stmt_iterator psi; 2104 basic_block bb = gimple_bb (stmt); 2105 2106 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) 2107 if (stmt == gsi_stmt (psi)) 2108 return psi; 2109 2110 gcc_unreachable (); 2111 return psi; 2112} 2113 2114/* Insert the assignment "RES := VAR" just after the definition of VAR. */ 2115 2116static void 2117insert_out_of_ssa_copy (tree res, tree var) 2118{ 2119 gimple stmt; 2120 gimple_seq stmts; 2121 gimple_stmt_iterator si; 2122 gimple_stmt_iterator gsi; 2123 2124 var = force_gimple_operand (var, &stmts, true, NULL_TREE); 2125 stmt = gimple_build_assign (res, var); 2126 if (!stmts) 2127 stmts = gimple_seq_alloc (); 2128 si = gsi_last (stmts); 2129 gsi_insert_after (&si, stmt, GSI_NEW_STMT); 2130 2131 stmt = SSA_NAME_DEF_STMT (var); 2132 if (gimple_code (stmt) == GIMPLE_PHI) 2133 { 2134 gsi = gsi_after_labels (gimple_bb (stmt)); 2135 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT); 2136 } 2137 else 2138 { 2139 gsi = gsi_for_stmt (stmt); 2140 gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT); 2141 } 2142} 2143 2144/* Insert on edge E the assignment "RES := EXPR". */ 2145 2146static void 2147insert_out_of_ssa_copy_on_edge (edge e, tree res, tree expr) 2148{ 2149 gimple_stmt_iterator gsi; 2150 gimple_seq stmts; 2151 tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE); 2152 gimple stmt = gimple_build_assign (res, var); 2153 2154 if (!stmts) 2155 stmts = gimple_seq_alloc (); 2156 2157 gsi = gsi_last (stmts); 2158 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT); 2159 gsi_insert_seq_on_edge (e, stmts); 2160 gsi_commit_edge_inserts (); 2161} 2162 2163/* Creates a zero dimension array of the same type as VAR. */ 2164 2165static tree 2166create_zero_dim_array (tree var, const char *base_name) 2167{ 2168 tree index_type = build_index_type (integer_zero_node); 2169 tree elt_type = TREE_TYPE (var); 2170 tree array_type = build_array_type (elt_type, index_type); 2171 tree base = create_tmp_var (array_type, base_name); 2172 2173 add_referenced_var (base); 2174 2175 return build4 (ARRAY_REF, elt_type, base, integer_zero_node, NULL_TREE, 2176 NULL_TREE); 2177} 2178 2179/* Returns true when PHI is a loop close phi node. */ 2180 2181static bool 2182scalar_close_phi_node_p (gimple phi) 2183{ 2184 if (gimple_code (phi) != GIMPLE_PHI 2185 || !is_gimple_reg (gimple_phi_result (phi))) 2186 return false; 2187 2188 return (gimple_phi_num_args (phi) == 1); 2189} 2190 2191/* Rewrite out of SSA the reduction phi node at PSI by creating a zero 2192 dimension array for it. */ 2193 2194static void 2195rewrite_close_phi_out_of_ssa (gimple_stmt_iterator *psi) 2196{ 2197 gimple phi = gsi_stmt (*psi); 2198 tree res = gimple_phi_result (phi); 2199 tree var = SSA_NAME_VAR (res); 2200 tree zero_dim_array = create_zero_dim_array (var, "Close_Phi"); 2201 gimple_stmt_iterator gsi = gsi_after_labels (gimple_bb (phi)); 2202 gimple stmt = gimple_build_assign (res, zero_dim_array); 2203 tree arg = gimple_phi_arg_def (phi, 0); 2204 2205 if (TREE_CODE (arg) == SSA_NAME 2206 && !SSA_NAME_IS_DEFAULT_DEF (arg)) 2207 insert_out_of_ssa_copy (zero_dim_array, arg); 2208 else 2209 insert_out_of_ssa_copy_on_edge (single_pred_edge (gimple_bb (phi)), 2210 zero_dim_array, arg); 2211 2212 remove_phi_node (psi, false); 2213 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT); 2214 SSA_NAME_DEF_STMT (res) = stmt; 2215} 2216 2217/* Rewrite out of SSA the reduction phi node at PSI by creating a zero 2218 dimension array for it. */ 2219 2220static void 2221rewrite_phi_out_of_ssa (gimple_stmt_iterator *psi) 2222{ 2223 size_t i; 2224 gimple phi = gsi_stmt (*psi); 2225 basic_block bb = gimple_bb (phi); 2226 tree res = gimple_phi_result (phi); 2227 tree var = SSA_NAME_VAR (res); 2228 tree zero_dim_array = create_zero_dim_array (var, "General_Reduction"); 2229 gimple_stmt_iterator gsi; 2230 gimple stmt; 2231 gimple_seq stmts; 2232 2233 for (i = 0; i < gimple_phi_num_args (phi); i++) 2234 { 2235 tree arg = gimple_phi_arg_def (phi, i); 2236 edge e = gimple_phi_arg_edge (phi, i); 2237 2238 /* Avoid the insertion of code in the loop latch to please the 2239 pattern matching of the vectorizer. */ 2240 if (TREE_CODE (arg) == SSA_NAME 2241 && e->src == bb->loop_father->latch) 2242 insert_out_of_ssa_copy (zero_dim_array, arg); 2243 else 2244 insert_out_of_ssa_copy_on_edge (e, zero_dim_array, arg); 2245 } 2246 2247 var = force_gimple_operand (zero_dim_array, &stmts, true, NULL_TREE); 2248 2249 if (!stmts) 2250 stmts = gimple_seq_alloc (); 2251 2252 stmt = gimple_build_assign (res, var); 2253 remove_phi_node (psi, false); 2254 SSA_NAME_DEF_STMT (res) = stmt; 2255 2256 gsi = gsi_last (stmts); 2257 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT); 2258 2259 gsi = gsi_after_labels (bb); 2260 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT); 2261} 2262 2263/* Return true when DEF can be analyzed in REGION by the scalar 2264 evolution analyzer. */ 2265 2266static bool 2267scev_analyzable_p (tree def, sese region) 2268{ 2269 gimple stmt = SSA_NAME_DEF_STMT (def); 2270 loop_p loop = loop_containing_stmt (stmt); 2271 tree scev = scalar_evolution_in_region (region, loop, def); 2272 2273 return !chrec_contains_undetermined (scev); 2274} 2275 2276/* Rewrite the scalar dependence of DEF used in USE_STMT with a memory 2277 read from ZERO_DIM_ARRAY. */ 2278 2279static void 2280rewrite_cross_bb_scalar_dependence (tree zero_dim_array, tree def, gimple use_stmt) 2281{ 2282 tree var = SSA_NAME_VAR (def); 2283 gimple name_stmt = gimple_build_assign (var, zero_dim_array); 2284 tree name = make_ssa_name (var, name_stmt); 2285 ssa_op_iter iter; 2286 use_operand_p use_p; 2287 gimple_stmt_iterator gsi; 2288 2289 gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI); 2290 2291 gimple_assign_set_lhs (name_stmt, name); 2292 2293 gsi = gsi_for_stmt (use_stmt); 2294 gsi_insert_before (&gsi, name_stmt, GSI_NEW_STMT); 2295 2296 FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, iter, SSA_OP_ALL_USES) 2297 if (operand_equal_p (def, USE_FROM_PTR (use_p), 0)) 2298 replace_exp (use_p, name); 2299 2300 update_stmt (use_stmt); 2301} 2302 2303/* Rewrite the scalar dependences crossing the boundary of the BB 2304 containing STMT with an array. */ 2305 2306static void 2307rewrite_cross_bb_scalar_deps (sese region, gimple_stmt_iterator *gsi) 2308{ 2309 gimple stmt = gsi_stmt (*gsi); 2310 imm_use_iterator imm_iter; 2311 tree def; 2312 basic_block def_bb; 2313 tree zero_dim_array = NULL_TREE; 2314 gimple use_stmt; 2315 2316 if (gimple_code (stmt) != GIMPLE_ASSIGN) 2317 return; 2318 2319 def = gimple_assign_lhs (stmt); 2320 if (!is_gimple_reg (def) 2321 || scev_analyzable_p (def, region)) 2322 return; 2323 2324 def_bb = gimple_bb (stmt); 2325 2326 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def) 2327 if (def_bb != gimple_bb (use_stmt) 2328 && gimple_code (use_stmt) != GIMPLE_PHI 2329 && !is_gimple_debug (use_stmt)) 2330 { 2331 if (!zero_dim_array) 2332 { 2333 zero_dim_array = create_zero_dim_array 2334 (SSA_NAME_VAR (def), "Cross_BB_scalar_dependence"); 2335 insert_out_of_ssa_copy (zero_dim_array, def); 2336 gsi_next (gsi); 2337 } 2338 2339 rewrite_cross_bb_scalar_dependence (zero_dim_array, def, use_stmt); 2340 } 2341} 2342 2343/* Rewrite out of SSA all the reduction phi nodes of SCOP. */ 2344 2345static void 2346rewrite_reductions_out_of_ssa (scop_p scop) 2347{ 2348 basic_block bb; 2349 gimple_stmt_iterator psi; 2350 sese region = SCOP_REGION (scop); 2351 2352 FOR_EACH_BB (bb) 2353 if (bb_in_sese_p (bb, region)) 2354 for (psi = gsi_start_phis (bb); !gsi_end_p (psi);) 2355 { 2356 if (scalar_close_phi_node_p (gsi_stmt (psi))) 2357 rewrite_close_phi_out_of_ssa (&psi); 2358 else if (reduction_phi_p (region, &psi)) 2359 rewrite_phi_out_of_ssa (&psi); 2360 } 2361 2362 update_ssa (TODO_update_ssa); 2363#ifdef ENABLE_CHECKING 2364 verify_ssa (false); 2365 verify_loop_closed_ssa (); 2366#endif 2367 2368 FOR_EACH_BB (bb) 2369 if (bb_in_sese_p (bb, region)) 2370 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) 2371 rewrite_cross_bb_scalar_deps (region, &psi); 2372 2373 update_ssa (TODO_update_ssa); 2374#ifdef ENABLE_CHECKING 2375 verify_ssa (false); 2376 verify_loop_closed_ssa (); 2377#endif 2378} 2379 2380/* Returns the number of pbbs that are in loops contained in SCOP. */ 2381 2382static int 2383nb_pbbs_in_loops (scop_p scop) 2384{ 2385 int i; 2386 poly_bb_p pbb; 2387 int res = 0; 2388 2389 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) 2390 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), SCOP_REGION (scop))) 2391 res++; 2392 2393 return res; 2394} 2395 2396/* Return the number of data references in BB that write in 2397 memory. */ 2398 2399static int 2400nb_data_writes_in_bb (basic_block bb) 2401{ 2402 int res = 0; 2403 gimple_stmt_iterator gsi; 2404 2405 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 2406 if (gimple_vdef (gsi_stmt (gsi))) 2407 res++; 2408 2409 return res; 2410} 2411 2412/* Splits STMT out of its current BB. */ 2413 2414static basic_block 2415split_reduction_stmt (gimple stmt) 2416{ 2417 gimple_stmt_iterator gsi; 2418 basic_block bb = gimple_bb (stmt); 2419 edge e; 2420 2421 /* Do not split basic blocks with no writes to memory: the reduction 2422 will be the only write to memory. */ 2423 if (nb_data_writes_in_bb (bb) == 0) 2424 return bb; 2425 2426 split_block (bb, stmt); 2427 2428 if (gsi_one_before_end_p (gsi_start_nondebug_bb (bb))) 2429 return bb; 2430 2431 gsi = gsi_last_bb (bb); 2432 gsi_prev (&gsi); 2433 e = split_block (bb, gsi_stmt (gsi)); 2434 2435 return e->dest; 2436} 2437 2438/* Return true when stmt is a reduction operation. */ 2439 2440static inline bool 2441is_reduction_operation_p (gimple stmt) 2442{ 2443 enum tree_code code; 2444 2445 gcc_assert (is_gimple_assign (stmt)); 2446 code = gimple_assign_rhs_code (stmt); 2447 2448 return flag_associative_math 2449 && commutative_tree_code (code) 2450 && associative_tree_code (code); 2451} 2452 2453/* Returns true when PHI contains an argument ARG. */ 2454 2455static bool 2456phi_contains_arg (gimple phi, tree arg) 2457{ 2458 size_t i; 2459 2460 for (i = 0; i < gimple_phi_num_args (phi); i++) 2461 if (operand_equal_p (arg, gimple_phi_arg_def (phi, i), 0)) 2462 return true; 2463 2464 return false; 2465} 2466 2467/* Return a loop phi node that corresponds to a reduction containing LHS. */ 2468 2469static gimple 2470follow_ssa_with_commutative_ops (tree arg, tree lhs) 2471{ 2472 gimple stmt; 2473 2474 if (TREE_CODE (arg) != SSA_NAME) 2475 return NULL; 2476 2477 stmt = SSA_NAME_DEF_STMT (arg); 2478 2479 if (gimple_code (stmt) == GIMPLE_NOP 2480 || gimple_code (stmt) == GIMPLE_CALL) 2481 return NULL; 2482 2483 if (gimple_code (stmt) == GIMPLE_PHI) 2484 { 2485 if (phi_contains_arg (stmt, lhs)) 2486 return stmt; 2487 return NULL; 2488 } 2489 2490 if (!is_gimple_assign (stmt)) 2491 return NULL; 2492 2493 if (gimple_num_ops (stmt) == 2) 2494 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs); 2495 2496 if (is_reduction_operation_p (stmt)) 2497 { 2498 gimple res = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs); 2499 2500 return res ? res : 2501 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt), lhs); 2502 } 2503 2504 return NULL; 2505} 2506 2507/* Detect commutative and associative scalar reductions starting at 2508 the STMT. Return the phi node of the reduction cycle, or NULL. */ 2509 2510static gimple 2511detect_commutative_reduction_arg (tree lhs, gimple stmt, tree arg, 2512 VEC (gimple, heap) **in, 2513 VEC (gimple, heap) **out) 2514{ 2515 gimple phi = follow_ssa_with_commutative_ops (arg, lhs); 2516 2517 if (!phi) 2518 return NULL; 2519 2520 VEC_safe_push (gimple, heap, *in, stmt); 2521 VEC_safe_push (gimple, heap, *out, stmt); 2522 return phi; 2523} 2524 2525/* Detect commutative and associative scalar reductions starting at 2526 the STMT. Return the phi node of the reduction cycle, or NULL. */ 2527 2528static gimple 2529detect_commutative_reduction_assign (gimple stmt, VEC (gimple, heap) **in, 2530 VEC (gimple, heap) **out) 2531{ 2532 tree lhs = gimple_assign_lhs (stmt); 2533 2534 if (gimple_num_ops (stmt) == 2) 2535 return detect_commutative_reduction_arg (lhs, stmt, 2536 gimple_assign_rhs1 (stmt), 2537 in, out); 2538 2539 if (is_reduction_operation_p (stmt)) 2540 { 2541 gimple res = detect_commutative_reduction_arg (lhs, stmt, 2542 gimple_assign_rhs1 (stmt), 2543 in, out); 2544 return res ? res 2545 : detect_commutative_reduction_arg (lhs, stmt, 2546 gimple_assign_rhs2 (stmt), 2547 in, out); 2548 } 2549 2550 return NULL; 2551} 2552 2553/* Return a loop phi node that corresponds to a reduction containing LHS. */ 2554 2555static gimple 2556follow_inital_value_to_phi (tree arg, tree lhs) 2557{ 2558 gimple stmt; 2559 2560 if (!arg || TREE_CODE (arg) != SSA_NAME) 2561 return NULL; 2562 2563 stmt = SSA_NAME_DEF_STMT (arg); 2564 2565 if (gimple_code (stmt) == GIMPLE_PHI 2566 && phi_contains_arg (stmt, lhs)) 2567 return stmt; 2568 2569 return NULL; 2570} 2571 2572 2573/* Return the argument of the loop PHI that is the inital value coming 2574 from outside the loop. */ 2575 2576static edge 2577edge_initial_value_for_loop_phi (gimple phi) 2578{ 2579 size_t i; 2580 2581 for (i = 0; i < gimple_phi_num_args (phi); i++) 2582 { 2583 edge e = gimple_phi_arg_edge (phi, i); 2584 2585 if (loop_depth (e->src->loop_father) 2586 < loop_depth (e->dest->loop_father)) 2587 return e; 2588 } 2589 2590 return NULL; 2591} 2592 2593/* Return the argument of the loop PHI that is the inital value coming 2594 from outside the loop. */ 2595 2596static tree 2597initial_value_for_loop_phi (gimple phi) 2598{ 2599 size_t i; 2600 2601 for (i = 0; i < gimple_phi_num_args (phi); i++) 2602 { 2603 edge e = gimple_phi_arg_edge (phi, i); 2604 2605 if (loop_depth (e->src->loop_father) 2606 < loop_depth (e->dest->loop_father)) 2607 return gimple_phi_arg_def (phi, i); 2608 } 2609 2610 return NULL_TREE; 2611} 2612 2613/* Detect commutative and associative scalar reductions starting at 2614 the loop closed phi node CLOSE_PHI. Return the phi node of the 2615 reduction cycle, or NULL. */ 2616 2617static gimple 2618detect_commutative_reduction (gimple stmt, VEC (gimple, heap) **in, 2619 VEC (gimple, heap) **out) 2620{ 2621 if (scalar_close_phi_node_p (stmt)) 2622 { 2623 tree arg = gimple_phi_arg_def (stmt, 0); 2624 gimple def, loop_phi; 2625 2626 if (TREE_CODE (arg) != SSA_NAME) 2627 return NULL; 2628 2629 def = SSA_NAME_DEF_STMT (arg); 2630 loop_phi = detect_commutative_reduction (def, in, out); 2631 2632 if (loop_phi) 2633 { 2634 tree lhs = gimple_phi_result (stmt); 2635 tree init = initial_value_for_loop_phi (loop_phi); 2636 gimple phi = follow_inital_value_to_phi (init, lhs); 2637 2638 VEC_safe_push (gimple, heap, *in, loop_phi); 2639 VEC_safe_push (gimple, heap, *out, stmt); 2640 return phi; 2641 } 2642 else 2643 return NULL; 2644 } 2645 2646 if (gimple_code (stmt) == GIMPLE_ASSIGN) 2647 return detect_commutative_reduction_assign (stmt, in, out); 2648 2649 return NULL; 2650} 2651 2652/* Translate the scalar reduction statement STMT to an array RED 2653 knowing that its recursive phi node is LOOP_PHI. */ 2654 2655static void 2656translate_scalar_reduction_to_array_for_stmt (tree red, gimple stmt, 2657 gimple loop_phi) 2658{ 2659 gimple_stmt_iterator insert_gsi = gsi_after_labels (gimple_bb (loop_phi)); 2660 tree res = gimple_phi_result (loop_phi); 2661 gimple assign = gimple_build_assign (res, red); 2662 2663 gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT); 2664 2665 insert_gsi = gsi_after_labels (gimple_bb (stmt)); 2666 assign = gimple_build_assign (red, gimple_assign_lhs (stmt)); 2667 insert_gsi = gsi_for_stmt (stmt); 2668 gsi_insert_after (&insert_gsi, assign, GSI_SAME_STMT); 2669} 2670 2671/* Insert the assignment "result (CLOSE_PHI) = RED". */ 2672 2673static void 2674insert_copyout (tree red, gimple close_phi) 2675{ 2676 tree res = gimple_phi_result (close_phi); 2677 basic_block bb = gimple_bb (close_phi); 2678 gimple_stmt_iterator insert_gsi = gsi_after_labels (bb); 2679 gimple assign = gimple_build_assign (res, red); 2680 2681 gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT); 2682} 2683 2684/* Insert the assignment "RED = initial_value (LOOP_PHI)". */ 2685 2686static void 2687insert_copyin (tree red, gimple loop_phi) 2688{ 2689 gimple_seq stmts; 2690 tree init = initial_value_for_loop_phi (loop_phi); 2691 tree expr = build2 (MODIFY_EXPR, TREE_TYPE (init), red, init); 2692 2693 force_gimple_operand (expr, &stmts, true, NULL); 2694 gsi_insert_seq_on_edge (edge_initial_value_for_loop_phi (loop_phi), stmts); 2695} 2696 2697/* Removes the PHI node and resets all the debug stmts that are using 2698 the PHI_RESULT. */ 2699 2700static void 2701remove_phi (gimple phi) 2702{ 2703 imm_use_iterator imm_iter; 2704 tree def; 2705 use_operand_p use_p; 2706 gimple_stmt_iterator gsi; 2707 VEC (gimple, heap) *update = VEC_alloc (gimple, heap, 3); 2708 unsigned int i; 2709 gimple stmt; 2710 2711 def = PHI_RESULT (phi); 2712 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def) 2713 { 2714 stmt = USE_STMT (use_p); 2715 2716 if (is_gimple_debug (stmt)) 2717 { 2718 gimple_debug_bind_reset_value (stmt); 2719 VEC_safe_push (gimple, heap, update, stmt); 2720 } 2721 } 2722 2723 for (i = 0; VEC_iterate (gimple, update, i, stmt); i++) 2724 update_stmt (stmt); 2725 2726 VEC_free (gimple, heap, update); 2727 2728 gsi = gsi_for_phi_node (phi); 2729 remove_phi_node (&gsi, false); 2730} 2731 2732/* Rewrite out of SSA the reduction described by the loop phi nodes 2733 IN, and the close phi nodes OUT. IN and OUT are structured by loop 2734 levels like this: 2735 2736 IN: stmt, loop_n, ..., loop_0 2737 OUT: stmt, close_n, ..., close_0 2738 2739 the first element is the reduction statement, and the next elements 2740 are the loop and close phi nodes of each of the outer loops. */ 2741 2742static void 2743translate_scalar_reduction_to_array (VEC (gimple, heap) *in, 2744 VEC (gimple, heap) *out, 2745 sbitmap reductions) 2746{ 2747 unsigned int i; 2748 gimple loop_phi; 2749 tree red = NULL_TREE; 2750 2751 for (i = 0; VEC_iterate (gimple, in, i, loop_phi); i++) 2752 { 2753 gimple close_phi = VEC_index (gimple, out, i); 2754 2755 if (i == 0) 2756 { 2757 gimple stmt = loop_phi; 2758 basic_block bb = split_reduction_stmt (stmt); 2759 2760 SET_BIT (reductions, bb->index); 2761 gcc_assert (close_phi == loop_phi); 2762 2763 red = create_zero_dim_array 2764 (gimple_assign_lhs (stmt), "Commutative_Associative_Reduction"); 2765 translate_scalar_reduction_to_array_for_stmt 2766 (red, stmt, VEC_index (gimple, in, 1)); 2767 continue; 2768 } 2769 2770 if (i == VEC_length (gimple, in) - 1) 2771 { 2772 insert_copyout (red, close_phi); 2773 insert_copyin (red, loop_phi); 2774 } 2775 2776 remove_phi (loop_phi); 2777 remove_phi (close_phi); 2778 } 2779} 2780 2781/* Rewrites out of SSA a commutative reduction at CLOSE_PHI. */ 2782 2783static void 2784rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi, 2785 sbitmap reductions) 2786{ 2787 VEC (gimple, heap) *in = VEC_alloc (gimple, heap, 10); 2788 VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10); 2789 2790 detect_commutative_reduction (close_phi, &in, &out); 2791 if (VEC_length (gimple, in) > 0) 2792 translate_scalar_reduction_to_array (in, out, reductions); 2793 2794 VEC_free (gimple, heap, in); 2795 VEC_free (gimple, heap, out); 2796} 2797 2798/* Rewrites all the commutative reductions from LOOP out of SSA. */ 2799 2800static void 2801rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop, 2802 sbitmap reductions) 2803{ 2804 gimple_stmt_iterator gsi; 2805 edge exit = single_exit (loop); 2806 2807 if (!exit) 2808 return; 2809 2810 for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi)) 2811 rewrite_commutative_reductions_out_of_ssa_close_phi (gsi_stmt (gsi), 2812 reductions); 2813} 2814 2815/* Rewrites all the commutative reductions from SCOP out of SSA. */ 2816 2817static void 2818rewrite_commutative_reductions_out_of_ssa (sese region, sbitmap reductions) 2819{ 2820 loop_iterator li; 2821 loop_p loop; 2822 2823 FOR_EACH_LOOP (li, loop, 0) 2824 if (loop_in_sese_p (loop, region)) 2825 rewrite_commutative_reductions_out_of_ssa_loop (loop, reductions); 2826 2827 gsi_commit_edge_inserts (); 2828 update_ssa (TODO_update_ssa); 2829#ifdef ENABLE_CHECKING 2830 verify_ssa (false); 2831 verify_loop_closed_ssa (); 2832#endif 2833} 2834 2835/* A LOOP is in normal form for Graphite when it contains only one 2836 scalar phi node that defines the main induction variable of the 2837 loop, only one increment of the IV, and only one exit condition. */ 2838 2839static void 2840graphite_loop_normal_form (loop_p loop) 2841{ 2842 struct tree_niter_desc niter; 2843 tree nit; 2844 gimple_seq stmts; 2845 edge exit = single_dom_exit (loop); 2846 2847 bool known_niter = number_of_iterations_exit (loop, exit, &niter, false); 2848 2849 /* At this point we should know the number of iterations. */ 2850 gcc_assert (known_niter); 2851 2852 nit = force_gimple_operand (unshare_expr (niter.niter), &stmts, true, 2853 NULL_TREE); 2854 if (stmts) 2855 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts); 2856 2857 loop->single_iv = canonicalize_loop_ivs (loop, &nit, false); 2858} 2859 2860/* Rewrite all the loops of SCOP in normal form: one induction 2861 variable per loop. */ 2862 2863static void 2864scop_canonicalize_loops (scop_p scop) 2865{ 2866 loop_iterator li; 2867 loop_p loop; 2868 2869 FOR_EACH_LOOP (li, loop, 0) 2870 if (loop_in_sese_p (loop, SCOP_REGION (scop))) 2871 graphite_loop_normal_form (loop); 2872} 2873 2874/* Java does not initialize long_long_integer_type_node. */ 2875#define my_long_long (long_long_integer_type_node ? long_long_integer_type_node : ssizetype) 2876 2877/* Can all ivs be represented by a signed integer? 2878 As CLooG might generate negative values in its expressions, signed loop ivs 2879 are required in the backend. */ 2880static bool 2881scop_ivs_can_be_represented (scop_p scop) 2882{ 2883 loop_iterator li; 2884 loop_p loop; 2885 2886 FOR_EACH_LOOP (li, loop, 0) 2887 { 2888 tree type; 2889 int precision; 2890 2891 if (!loop_in_sese_p (loop, SCOP_REGION (scop))) 2892 continue; 2893 2894 if (!loop->single_iv) 2895 continue; 2896 2897 type = TREE_TYPE(loop->single_iv); 2898 precision = TYPE_PRECISION (type); 2899 2900 if (TYPE_UNSIGNED (type) 2901 && precision >= TYPE_PRECISION (my_long_long)) 2902 return false; 2903 } 2904 2905 return true; 2906} 2907 2908#undef my_long_long 2909 2910/* Builds the polyhedral representation for a SESE region. */ 2911 2912void 2913build_poly_scop (scop_p scop) 2914{ 2915 sese region = SCOP_REGION (scop); 2916 sbitmap reductions = sbitmap_alloc (last_basic_block * 2); 2917 graphite_dim_t max_dim; 2918 2919 sbitmap_zero (reductions); 2920 rewrite_commutative_reductions_out_of_ssa (region, reductions); 2921 rewrite_reductions_out_of_ssa (scop); 2922 build_scop_bbs (scop, reductions); 2923 sbitmap_free (reductions); 2924 2925 /* FIXME: This restriction is needed to avoid a problem in CLooG. 2926 Once CLooG is fixed, remove this guard. Anyways, it makes no 2927 sense to optimize a scop containing only PBBs that do not belong 2928 to any loops. */ 2929 if (nb_pbbs_in_loops (scop) == 0) 2930 return; 2931 2932 scop_canonicalize_loops (scop); 2933 if (!scop_ivs_can_be_represented (scop)) 2934 return; 2935 2936 build_sese_loop_nests (region); 2937 build_sese_conditions (region); 2938 find_scop_parameters (scop); 2939 2940 max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS); 2941 if (scop_nb_params (scop) > max_dim) 2942 return; 2943 2944 build_scop_iteration_domain (scop); 2945 build_scop_context (scop); 2946 2947 add_conditions_to_constraints (scop); 2948 scop_to_lst (scop); 2949 build_scop_scattering (scop); 2950 build_scop_drs (scop); 2951 2952 /* This SCoP has been translated to the polyhedral 2953 representation. */ 2954 POLY_SCOP_P (scop) = true; 2955} 2956 2957/* Always return false. Exercise the scop_to_clast function. */ 2958 2959void 2960check_poly_representation (scop_p scop ATTRIBUTE_UNUSED) 2961{ 2962#ifdef ENABLE_CHECKING 2963 cloog_prog_clast pc = scop_to_clast (scop); 2964 cloog_clast_free (pc.stmt); 2965 cloog_program_free (pc.prog); 2966#endif 2967} 2968#endif 2969