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