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