1 /* Detection of Static Control Parts (SCoP) for Graphite. 2 Copyright (C) 2009-2018 Free Software Foundation, Inc. 3 Contributed by Sebastian Pop <sebastian.pop@amd.com> and 4 Tobias Grosser <grosser@fim.uni-passau.de>. 5 6 This file is part of GCC. 7 8 GCC is free software; you can redistribute it and/or modify 9 it under the terms of the GNU General Public License as published by 10 the Free Software Foundation; either version 3, or (at your option) 11 any later version. 12 13 GCC is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 GNU General Public License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with GCC; see the file COPYING3. If not see 20 <http://www.gnu.org/licenses/>. */ 21 22 #define USES_ISL 23 24 #include "config.h" 25 26 #ifdef HAVE_isl 27 28 #include "system.h" 29 #include "coretypes.h" 30 #include "backend.h" 31 #include "cfghooks.h" 32 #include "domwalk.h" 33 #include "params.h" 34 #include "tree.h" 35 #include "gimple.h" 36 #include "ssa.h" 37 #include "fold-const.h" 38 #include "gimple-iterator.h" 39 #include "tree-cfg.h" 40 #include "tree-ssa-loop-manip.h" 41 #include "tree-ssa-loop-niter.h" 42 #include "tree-ssa-loop.h" 43 #include "tree-into-ssa.h" 44 #include "tree-ssa.h" 45 #include "cfgloop.h" 46 #include "tree-data-ref.h" 47 #include "tree-scalar-evolution.h" 48 #include "tree-pass.h" 49 #include "tree-ssa-propagate.h" 50 #include "gimple-pretty-print.h" 51 #include "cfganal.h" 52 #include "graphite.h" 53 54 class debug_printer 55 { 56 private: 57 FILE *dump_file; 58 59 public: 60 void 61 set_dump_file (FILE *f) 62 { 63 gcc_assert (f); 64 dump_file = f; 65 } 66 67 friend debug_printer & 68 operator<< (debug_printer &output, int i) 69 { 70 fprintf (output.dump_file, "%d", i); 71 return output; 72 } 73 friend debug_printer & 74 operator<< (debug_printer &output, const char *s) 75 { 76 fprintf (output.dump_file, "%s", s); 77 return output; 78 } 79 } dp; 80 81 #define DEBUG_PRINT(args) do \ 82 { \ 83 if (dump_file && (dump_flags & TDF_DETAILS)) { args; } \ 84 } while (0) 85 86 /* Pretty print to FILE all the SCoPs in DOT format and mark them with 87 different colors. If there are not enough colors, paint the 88 remaining SCoPs in gray. 89 90 Special nodes: 91 - "*" after the node number denotes the entry of a SCoP, 92 - "#" after the node number denotes the exit of a SCoP, 93 - "()" around the node number denotes the entry or the 94 exit nodes of the SCOP. These are not part of SCoP. */ 95 96 DEBUG_FUNCTION void 97 dot_all_sese (FILE *file, vec<sese_l>& scops) 98 { 99 /* Disable debugging while printing graph. */ 100 dump_flags_t tmp_dump_flags = dump_flags; 101 dump_flags = TDF_NONE; 102 103 fprintf (file, "digraph all {\n"); 104 105 basic_block bb; 106 FOR_ALL_BB_FN (bb, cfun) 107 { 108 int part_of_scop = false; 109 110 /* Use HTML for every bb label. So we are able to print bbs 111 which are part of two different SCoPs, with two different 112 background colors. */ 113 fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ", 114 bb->index); 115 fprintf (file, "CELLSPACING=\"0\">\n"); 116 117 /* Select color for SCoP. */ 118 sese_l *region; 119 int i; 120 FOR_EACH_VEC_ELT (scops, i, region) 121 { 122 bool sese_in_region = bb_in_sese_p (bb, *region); 123 if (sese_in_region || (region->exit->dest == bb) 124 || (region->entry->dest == bb)) 125 { 126 const char *color; 127 switch (i % 17) 128 { 129 case 0: /* red */ 130 color = "#e41a1c"; 131 break; 132 case 1: /* blue */ 133 color = "#377eb8"; 134 break; 135 case 2: /* green */ 136 color = "#4daf4a"; 137 break; 138 case 3: /* purple */ 139 color = "#984ea3"; 140 break; 141 case 4: /* orange */ 142 color = "#ff7f00"; 143 break; 144 case 5: /* yellow */ 145 color = "#ffff33"; 146 break; 147 case 6: /* brown */ 148 color = "#a65628"; 149 break; 150 case 7: /* rose */ 151 color = "#f781bf"; 152 break; 153 case 8: 154 color = "#8dd3c7"; 155 break; 156 case 9: 157 color = "#ffffb3"; 158 break; 159 case 10: 160 color = "#bebada"; 161 break; 162 case 11: 163 color = "#fb8072"; 164 break; 165 case 12: 166 color = "#80b1d3"; 167 break; 168 case 13: 169 color = "#fdb462"; 170 break; 171 case 14: 172 color = "#b3de69"; 173 break; 174 case 15: 175 color = "#fccde5"; 176 break; 177 case 16: 178 color = "#bc80bd"; 179 break; 180 default: /* gray */ 181 color = "#999999"; 182 } 183 184 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", 185 color); 186 187 if (!sese_in_region) 188 fprintf (file, " ("); 189 190 if (bb == region->entry->dest && bb == region->exit->dest) 191 fprintf (file, " %d*# ", bb->index); 192 else if (bb == region->entry->dest) 193 fprintf (file, " %d* ", bb->index); 194 else if (bb == region->exit->dest) 195 fprintf (file, " %d# ", bb->index); 196 else 197 fprintf (file, " %d ", bb->index); 198 199 fprintf (file, "{lp_%d}", bb->loop_father->num); 200 201 if (!sese_in_region) 202 fprintf (file, ")"); 203 204 fprintf (file, "</TD></TR>\n"); 205 part_of_scop = true; 206 } 207 } 208 209 if (!part_of_scop) 210 { 211 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">"); 212 fprintf (file, " %d {lp_%d} </TD></TR>\n", bb->index, 213 bb->loop_father->num); 214 } 215 fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n"); 216 } 217 218 FOR_ALL_BB_FN (bb, cfun) 219 { 220 edge e; 221 edge_iterator ei; 222 FOR_EACH_EDGE (e, ei, bb->succs) 223 fprintf (file, "%d -> %d;\n", bb->index, e->dest->index); 224 } 225 226 fputs ("}\n\n", file); 227 228 /* Enable debugging again. */ 229 dump_flags = tmp_dump_flags; 230 } 231 232 /* Display SCoP on stderr. */ 233 234 DEBUG_FUNCTION void 235 dot_sese (sese_l& scop) 236 { 237 vec<sese_l> scops; 238 scops.create (1); 239 240 if (scop) 241 scops.safe_push (scop); 242 243 dot_all_sese (stderr, scops); 244 245 scops.release (); 246 } 247 248 DEBUG_FUNCTION void 249 dot_cfg () 250 { 251 vec<sese_l> scops; 252 scops.create (1); 253 dot_all_sese (stderr, scops); 254 scops.release (); 255 } 256 257 /* Returns a COND_EXPR statement when BB has a single predecessor, the 258 edge between BB and its predecessor is not a loop exit edge, and 259 the last statement of the single predecessor is a COND_EXPR. */ 260 261 static gcond * 262 single_pred_cond_non_loop_exit (basic_block bb) 263 { 264 if (single_pred_p (bb)) 265 { 266 edge e = single_pred_edge (bb); 267 basic_block pred = e->src; 268 gimple *stmt; 269 270 if (loop_depth (pred->loop_father) > loop_depth (bb->loop_father)) 271 return NULL; 272 273 stmt = last_stmt (pred); 274 275 if (stmt && gimple_code (stmt) == GIMPLE_COND) 276 return as_a<gcond *> (stmt); 277 } 278 279 return NULL; 280 } 281 282 namespace 283 { 284 285 /* Build the maximal scop containing LOOPs and add it to SCOPS. */ 286 287 class scop_detection 288 { 289 public: 290 scop_detection () : scops (vNULL) {} 291 292 ~scop_detection () 293 { 294 scops.release (); 295 } 296 297 /* A marker for invalid sese_l. */ 298 static sese_l invalid_sese; 299 300 /* Return the SCOPS in this SCOP_DETECTION. */ 301 302 vec<sese_l> 303 get_scops () 304 { 305 return scops; 306 } 307 308 /* Return an sese_l around the LOOP. */ 309 310 sese_l get_sese (loop_p loop); 311 312 /* Merge scops at same loop depth and returns the new sese. 313 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */ 314 315 sese_l merge_sese (sese_l first, sese_l second) const; 316 317 /* Build scop outer->inner if possible. */ 318 319 void build_scop_depth (loop_p loop); 320 321 /* Return true when BEGIN is the preheader edge of a loop with a single exit 322 END. */ 323 324 static bool region_has_one_loop (sese_l s); 325 326 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */ 327 328 void add_scop (sese_l s); 329 330 /* Returns true if S1 subsumes/surrounds S2. */ 331 static bool subsumes (sese_l s1, sese_l s2); 332 333 /* Remove a SCoP which is subsumed by S1. */ 334 void remove_subscops (sese_l s1); 335 336 /* Returns true if S1 intersects with S2. Since we already know that S1 does 337 not subsume S2 or vice-versa, we only check for entry bbs. */ 338 339 static bool intersects (sese_l s1, sese_l s2); 340 341 /* Remove one of the scops when it intersects with any other. */ 342 343 void remove_intersecting_scops (sese_l s1); 344 345 /* Return true when a statement in SCOP cannot be represented by Graphite. */ 346 347 bool harmful_loop_in_region (sese_l scop) const; 348 349 /* Return true only when STMT is simple enough for being handled by Graphite. 350 This depends on SCOP, as the parameters are initialized relatively to 351 this basic block, the linear functions are initialized based on the 352 outermost loop containing STMT inside the SCOP. BB is the place where we 353 try to evaluate the STMT. */ 354 355 bool stmt_simple_for_scop_p (sese_l scop, gimple *stmt, 356 basic_block bb) const; 357 358 /* Something like "n * m" is not allowed. */ 359 360 static bool graphite_can_represent_init (tree e); 361 362 /* Return true when SCEV can be represented in the polyhedral model. 363 364 An expression can be represented, if it can be expressed as an 365 affine expression. For loops (i, j) and parameters (m, n) all 366 affine expressions are of the form: 367 368 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z 369 370 1 i + 20 j + (-2) m + 25 371 372 Something like "i * n" or "n * m" is not allowed. */ 373 374 static bool graphite_can_represent_scev (sese_l scop, tree scev); 375 376 /* Return true when EXPR can be represented in the polyhedral model. 377 378 This means an expression can be represented, if it is linear with respect 379 to the loops and the strides are non parametric. LOOP is the place where 380 the expr will be evaluated. SCOP defines the region we analyse. */ 381 382 static bool graphite_can_represent_expr (sese_l scop, loop_p loop, 383 tree expr); 384 385 /* Return true if the data references of STMT can be represented by Graphite. 386 We try to analyze the data references in a loop contained in the SCOP. */ 387 388 static bool stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt); 389 390 /* Remove the close phi node at GSI and replace its rhs with the rhs 391 of PHI. */ 392 393 static void remove_duplicate_close_phi (gphi *phi, gphi_iterator *gsi); 394 395 /* Returns true when Graphite can represent LOOP in SCOP. 396 FIXME: For the moment, graphite cannot be used on loops that iterate using 397 induction variables that wrap. */ 398 399 static bool can_represent_loop (loop_p loop, sese_l scop); 400 401 /* Returns the number of pbbs that are in loops contained in SCOP. */ 402 403 static int nb_pbbs_in_loops (scop_p scop); 404 405 private: 406 vec<sese_l> scops; 407 }; 408 409 sese_l scop_detection::invalid_sese (NULL, NULL); 410 411 /* Return an sese_l around the LOOP. */ 412 413 sese_l 414 scop_detection::get_sese (loop_p loop) 415 { 416 if (!loop) 417 return invalid_sese; 418 419 edge scop_begin = loop_preheader_edge (loop); 420 edge scop_end = single_exit (loop); 421 if (!scop_end || (scop_end->flags & (EDGE_COMPLEX|EDGE_FAKE))) 422 return invalid_sese; 423 424 return sese_l (scop_begin, scop_end); 425 } 426 427 /* Merge scops at same loop depth and returns the new sese. 428 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */ 429 430 sese_l 431 scop_detection::merge_sese (sese_l first, sese_l second) const 432 { 433 /* In the trivial case first/second may be NULL. */ 434 if (!first) 435 return second; 436 if (!second) 437 return first; 438 439 DEBUG_PRINT (dp << "[scop-detection] try merging sese s1: "; 440 print_sese (dump_file, first); 441 dp << "[scop-detection] try merging sese s2: "; 442 print_sese (dump_file, second)); 443 444 auto_bitmap worklist, in_sese_region; 445 bitmap_set_bit (worklist, get_entry_bb (first)->index); 446 bitmap_set_bit (worklist, get_exit_bb (first)->index); 447 bitmap_set_bit (worklist, get_entry_bb (second)->index); 448 bitmap_set_bit (worklist, get_exit_bb (second)->index); 449 edge entry = NULL, exit = NULL; 450 451 /* We can optimize the case of adding a loop entry dest or exit 452 src to the worklist (for single-exit loops) by skipping 453 directly to the exit dest / entry src. in_sese_region 454 doesn't have to cover all blocks in the region but merely 455 its border it acts more like a visited bitmap. */ 456 do 457 { 458 int index = bitmap_first_set_bit (worklist); 459 bitmap_clear_bit (worklist, index); 460 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, index); 461 edge_iterator ei; 462 edge e; 463 464 /* With fake exit edges we can end up with no possible exit. */ 465 if (index == EXIT_BLOCK) 466 { 467 DEBUG_PRINT (dp << "[scop-detection-fail] cannot merge seses.\n"); 468 return invalid_sese; 469 } 470 471 bitmap_set_bit (in_sese_region, bb->index); 472 473 basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb); 474 FOR_EACH_EDGE (e, ei, bb->preds) 475 if (e->src == dom 476 && (! entry 477 || dominated_by_p (CDI_DOMINATORS, entry->dest, bb))) 478 { 479 if (entry 480 && ! bitmap_bit_p (in_sese_region, entry->src->index)) 481 bitmap_set_bit (worklist, entry->src->index); 482 entry = e; 483 } 484 else if (! bitmap_bit_p (in_sese_region, e->src->index)) 485 bitmap_set_bit (worklist, e->src->index); 486 487 basic_block pdom = get_immediate_dominator (CDI_POST_DOMINATORS, bb); 488 FOR_EACH_EDGE (e, ei, bb->succs) 489 if (e->dest == pdom 490 && (! exit 491 || dominated_by_p (CDI_POST_DOMINATORS, exit->src, bb))) 492 { 493 if (exit 494 && ! bitmap_bit_p (in_sese_region, exit->dest->index)) 495 bitmap_set_bit (worklist, exit->dest->index); 496 exit = e; 497 } 498 else if (! bitmap_bit_p (in_sese_region, e->dest->index)) 499 bitmap_set_bit (worklist, e->dest->index); 500 } 501 while (! bitmap_empty_p (worklist)); 502 503 sese_l combined (entry, exit); 504 505 DEBUG_PRINT (dp << "[merged-sese] s1: "; print_sese (dump_file, combined)); 506 507 return combined; 508 } 509 510 /* Build scop outer->inner if possible. */ 511 512 void 513 scop_detection::build_scop_depth (loop_p loop) 514 { 515 sese_l s = invalid_sese; 516 loop = loop->inner; 517 while (loop) 518 { 519 sese_l next = get_sese (loop); 520 if (! next 521 || harmful_loop_in_region (next)) 522 { 523 if (s) 524 add_scop (s); 525 build_scop_depth (loop); 526 s = invalid_sese; 527 } 528 else if (! s) 529 s = next; 530 else 531 { 532 sese_l combined = merge_sese (s, next); 533 if (! combined 534 || harmful_loop_in_region (combined)) 535 { 536 add_scop (s); 537 s = next; 538 } 539 else 540 s = combined; 541 } 542 loop = loop->next; 543 } 544 if (s) 545 add_scop (s); 546 } 547 548 /* Returns true when Graphite can represent LOOP in SCOP. 549 FIXME: For the moment, graphite cannot be used on loops that iterate using 550 induction variables that wrap. */ 551 552 bool 553 scop_detection::can_represent_loop (loop_p loop, sese_l scop) 554 { 555 tree niter; 556 struct tree_niter_desc niter_desc; 557 558 /* We can only handle do {} while () style loops correctly. */ 559 edge exit = single_exit (loop); 560 if (!exit 561 || !single_pred_p (loop->latch) 562 || exit->src != single_pred (loop->latch) 563 || !empty_block_p (loop->latch)) 564 return false; 565 566 return !(loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP) 567 && number_of_iterations_exit (loop, single_exit (loop), &niter_desc, false) 568 && niter_desc.control.no_overflow 569 && (niter = number_of_latch_executions (loop)) 570 && !chrec_contains_undetermined (niter) 571 && !chrec_contains_undetermined (scalar_evolution_in_region (scop, 572 loop, niter)) 573 && graphite_can_represent_expr (scop, loop, niter); 574 } 575 576 /* Return true when BEGIN is the preheader edge of a loop with a single exit 577 END. */ 578 579 bool 580 scop_detection::region_has_one_loop (sese_l s) 581 { 582 edge begin = s.entry; 583 edge end = s.exit; 584 /* Check for a single perfectly nested loop. */ 585 if (begin->dest->loop_father->inner) 586 return false; 587 588 /* Otherwise, check whether we have adjacent loops. */ 589 return (single_pred_p (end->src) 590 && begin->dest->loop_father == single_pred (end->src)->loop_father); 591 } 592 593 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */ 594 595 void 596 scop_detection::add_scop (sese_l s) 597 { 598 gcc_assert (s); 599 600 /* If the exit edge is fake discard the SCoP for now as we're removing the 601 fake edges again after analysis. */ 602 if (s.exit->flags & EDGE_FAKE) 603 { 604 DEBUG_PRINT (dp << "[scop-detection-fail] Discarding infinite loop SCoP: "; 605 print_sese (dump_file, s)); 606 return; 607 } 608 609 /* Include the BB with the loop-closed SSA PHI nodes, we need this 610 block in the region for code-generating out-of-SSA copies. 611 canonicalize_loop_closed_ssa makes sure that is in proper shape. */ 612 if (s.exit->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) 613 && loop_exit_edge_p (s.exit->src->loop_father, s.exit)) 614 { 615 gcc_assert (single_pred_p (s.exit->dest) 616 && single_succ_p (s.exit->dest) 617 && sese_trivially_empty_bb_p (s.exit->dest)); 618 s.exit = single_succ_edge (s.exit->dest); 619 } 620 621 /* Do not add scops with only one loop. */ 622 if (region_has_one_loop (s)) 623 { 624 DEBUG_PRINT (dp << "[scop-detection-fail] Discarding one loop SCoP: "; 625 print_sese (dump_file, s)); 626 return; 627 } 628 629 if (get_exit_bb (s) == EXIT_BLOCK_PTR_FOR_FN (cfun)) 630 { 631 DEBUG_PRINT (dp << "[scop-detection-fail] " 632 << "Discarding SCoP exiting to return: "; 633 print_sese (dump_file, s)); 634 return; 635 } 636 637 /* Remove all the scops which are subsumed by s. */ 638 remove_subscops (s); 639 640 /* Remove intersecting scops. FIXME: It will be a good idea to keep 641 the non-intersecting part of the scop already in the list. */ 642 remove_intersecting_scops (s); 643 644 scops.safe_push (s); 645 DEBUG_PRINT (dp << "[scop-detection] Adding SCoP: "; print_sese (dump_file, s)); 646 } 647 648 /* Return true when a statement in SCOP cannot be represented by Graphite. */ 649 650 bool 651 scop_detection::harmful_loop_in_region (sese_l scop) const 652 { 653 basic_block exit_bb = get_exit_bb (scop); 654 basic_block entry_bb = get_entry_bb (scop); 655 656 DEBUG_PRINT (dp << "[checking-harmful-bbs] "; 657 print_sese (dump_file, scop)); 658 gcc_assert (dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb)); 659 660 auto_vec<basic_block> worklist; 661 auto_bitmap loops; 662 663 worklist.safe_push (entry_bb); 664 while (! worklist.is_empty ()) 665 { 666 basic_block bb = worklist.pop (); 667 DEBUG_PRINT (dp << "Visiting bb_" << bb->index << "\n"); 668 669 /* The basic block should not be part of an irreducible loop. */ 670 if (bb->flags & BB_IRREDUCIBLE_LOOP) 671 return true; 672 673 /* Check for unstructured control flow: CFG not generated by structured 674 if-then-else. */ 675 if (bb->succs->length () > 1) 676 { 677 edge e; 678 edge_iterator ei; 679 FOR_EACH_EDGE (e, ei, bb->succs) 680 if (!dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest) 681 && !dominated_by_p (CDI_DOMINATORS, e->dest, bb)) 682 return true; 683 } 684 685 /* Collect all loops in the current region. */ 686 loop_p loop = bb->loop_father; 687 if (loop_in_sese_p (loop, scop)) 688 bitmap_set_bit (loops, loop->num); 689 690 /* Check for harmful statements in basic blocks part of the region. */ 691 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); 692 !gsi_end_p (gsi); gsi_next (&gsi)) 693 if (!stmt_simple_for_scop_p (scop, gsi_stmt (gsi), bb)) 694 return true; 695 696 for (basic_block dom = first_dom_son (CDI_DOMINATORS, bb); 697 dom; 698 dom = next_dom_son (CDI_DOMINATORS, dom)) 699 if (dom != scop.exit->dest) 700 worklist.safe_push (dom); 701 } 702 703 /* Go through all loops and check that they are still valid in the combined 704 scop. */ 705 unsigned j; 706 bitmap_iterator bi; 707 EXECUTE_IF_SET_IN_BITMAP (loops, 0, j, bi) 708 { 709 loop_p loop = (*current_loops->larray)[j]; 710 gcc_assert (loop->num == (int) j); 711 712 /* Check if the loop nests are to be optimized for speed. */ 713 if (! loop->inner 714 && ! optimize_loop_for_speed_p (loop)) 715 { 716 DEBUG_PRINT (dp << "[scop-detection-fail] loop_" 717 << loop->num << " is not on a hot path.\n"); 718 return true; 719 } 720 721 if (! can_represent_loop (loop, scop)) 722 { 723 DEBUG_PRINT (dp << "[scop-detection-fail] cannot represent loop_" 724 << loop->num << "\n"); 725 return true; 726 } 727 728 /* Check if all loop nests have at least one data reference. 729 ??? This check is expensive and loops premature at this point. 730 If important to retain we can pre-compute this for all innermost 731 loops and reject those when we build a SESE region for a loop 732 during SESE discovery. */ 733 if (! loop->inner 734 && ! loop_nest_has_data_refs (loop)) 735 { 736 DEBUG_PRINT (dp << "[scop-detection-fail] loop_" << loop->num 737 << "does not have any data reference.\n"); 738 return true; 739 } 740 } 741 742 return false; 743 } 744 745 /* Returns true if S1 subsumes/surrounds S2. */ 746 bool 747 scop_detection::subsumes (sese_l s1, sese_l s2) 748 { 749 if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2), 750 get_entry_bb (s1)) 751 && dominated_by_p (CDI_POST_DOMINATORS, s2.exit->dest, 752 s1.exit->dest)) 753 return true; 754 return false; 755 } 756 757 /* Remove a SCoP which is subsumed by S1. */ 758 void 759 scop_detection::remove_subscops (sese_l s1) 760 { 761 int j; 762 sese_l *s2; 763 FOR_EACH_VEC_ELT_REVERSE (scops, j, s2) 764 { 765 if (subsumes (s1, *s2)) 766 { 767 DEBUG_PRINT (dp << "Removing sub-SCoP"; 768 print_sese (dump_file, *s2)); 769 scops.unordered_remove (j); 770 } 771 } 772 } 773 774 /* Returns true if S1 intersects with S2. Since we already know that S1 does 775 not subsume S2 or vice-versa, we only check for entry bbs. */ 776 777 bool 778 scop_detection::intersects (sese_l s1, sese_l s2) 779 { 780 if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2), 781 get_entry_bb (s1)) 782 && !dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2), 783 get_exit_bb (s1))) 784 return true; 785 if ((s1.exit == s2.entry) || (s2.exit == s1.entry)) 786 return true; 787 788 return false; 789 } 790 791 /* Remove one of the scops when it intersects with any other. */ 792 793 void 794 scop_detection::remove_intersecting_scops (sese_l s1) 795 { 796 int j; 797 sese_l *s2; 798 FOR_EACH_VEC_ELT_REVERSE (scops, j, s2) 799 { 800 if (intersects (s1, *s2)) 801 { 802 DEBUG_PRINT (dp << "Removing intersecting SCoP"; 803 print_sese (dump_file, *s2); 804 dp << "Intersects with:"; 805 print_sese (dump_file, s1)); 806 scops.unordered_remove (j); 807 } 808 } 809 } 810 811 /* Something like "n * m" is not allowed. */ 812 813 bool 814 scop_detection::graphite_can_represent_init (tree e) 815 { 816 switch (TREE_CODE (e)) 817 { 818 case POLYNOMIAL_CHREC: 819 return graphite_can_represent_init (CHREC_LEFT (e)) 820 && graphite_can_represent_init (CHREC_RIGHT (e)); 821 822 case MULT_EXPR: 823 if (chrec_contains_symbols (TREE_OPERAND (e, 0))) 824 return graphite_can_represent_init (TREE_OPERAND (e, 0)) 825 && tree_fits_shwi_p (TREE_OPERAND (e, 1)); 826 else 827 return graphite_can_represent_init (TREE_OPERAND (e, 1)) 828 && tree_fits_shwi_p (TREE_OPERAND (e, 0)); 829 830 case PLUS_EXPR: 831 case POINTER_PLUS_EXPR: 832 case MINUS_EXPR: 833 return graphite_can_represent_init (TREE_OPERAND (e, 0)) 834 && graphite_can_represent_init (TREE_OPERAND (e, 1)); 835 836 case NEGATE_EXPR: 837 case BIT_NOT_EXPR: 838 CASE_CONVERT: 839 case NON_LVALUE_EXPR: 840 return graphite_can_represent_init (TREE_OPERAND (e, 0)); 841 842 default: 843 break; 844 } 845 846 return true; 847 } 848 849 /* Return true when SCEV can be represented in the polyhedral model. 850 851 An expression can be represented, if it can be expressed as an 852 affine expression. For loops (i, j) and parameters (m, n) all 853 affine expressions are of the form: 854 855 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z 856 857 1 i + 20 j + (-2) m + 25 858 859 Something like "i * n" or "n * m" is not allowed. */ 860 861 bool 862 scop_detection::graphite_can_represent_scev (sese_l scop, tree scev) 863 { 864 if (chrec_contains_undetermined (scev)) 865 return false; 866 867 switch (TREE_CODE (scev)) 868 { 869 case NEGATE_EXPR: 870 case BIT_NOT_EXPR: 871 CASE_CONVERT: 872 case NON_LVALUE_EXPR: 873 return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0)); 874 875 case PLUS_EXPR: 876 case POINTER_PLUS_EXPR: 877 case MINUS_EXPR: 878 return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0)) 879 && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1)); 880 881 case MULT_EXPR: 882 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0))) 883 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1))) 884 && !(chrec_contains_symbols (TREE_OPERAND (scev, 0)) 885 && chrec_contains_symbols (TREE_OPERAND (scev, 1))) 886 && graphite_can_represent_init (scev) 887 && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0)) 888 && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1)); 889 890 case POLYNOMIAL_CHREC: 891 /* Check for constant strides. With a non constant stride of 892 'n' we would have a value of 'iv * n'. Also check that the 893 initial value can represented: for example 'n * m' cannot be 894 represented. */ 895 gcc_assert (loop_in_sese_p (get_loop (cfun, 896 CHREC_VARIABLE (scev)), scop)); 897 if (!evolution_function_right_is_integer_cst (scev) 898 || !graphite_can_represent_init (scev)) 899 return false; 900 return graphite_can_represent_scev (scop, CHREC_LEFT (scev)); 901 902 default: 903 break; 904 } 905 906 /* Only affine functions can be represented. */ 907 if (tree_contains_chrecs (scev, NULL) || !scev_is_linear_expression (scev)) 908 return false; 909 910 return true; 911 } 912 913 /* Return true when EXPR can be represented in the polyhedral model. 914 915 This means an expression can be represented, if it is linear with respect to 916 the loops and the strides are non parametric. LOOP is the place where the 917 expr will be evaluated. SCOP defines the region we analyse. */ 918 919 bool 920 scop_detection::graphite_can_represent_expr (sese_l scop, loop_p loop, 921 tree expr) 922 { 923 tree scev = scalar_evolution_in_region (scop, loop, expr); 924 return graphite_can_represent_scev (scop, scev); 925 } 926 927 /* Return true if the data references of STMT can be represented by Graphite. 928 We try to analyze the data references in a loop contained in the SCOP. */ 929 930 bool 931 scop_detection::stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt) 932 { 933 edge nest = scop.entry; 934 loop_p loop = loop_containing_stmt (stmt); 935 if (!loop_in_sese_p (loop, scop)) 936 loop = NULL; 937 938 auto_vec<data_reference_p> drs; 939 if (! graphite_find_data_references_in_stmt (nest, loop, stmt, &drs)) 940 return false; 941 942 int j; 943 data_reference_p dr; 944 FOR_EACH_VEC_ELT (drs, j, dr) 945 { 946 for (unsigned i = 0; i < DR_NUM_DIMENSIONS (dr); ++i) 947 if (! graphite_can_represent_scev (scop, DR_ACCESS_FN (dr, i))) 948 return false; 949 } 950 951 return true; 952 } 953 954 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects. 955 Calls have side-effects, except those to const or pure 956 functions. */ 957 958 static bool 959 stmt_has_side_effects (gimple *stmt) 960 { 961 if (gimple_has_volatile_ops (stmt) 962 || (gimple_code (stmt) == GIMPLE_CALL 963 && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE))) 964 || (gimple_code (stmt) == GIMPLE_ASM)) 965 { 966 DEBUG_PRINT (dp << "[scop-detection-fail] " 967 << "Statement has side-effects:\n"; 968 print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS)); 969 return true; 970 } 971 return false; 972 } 973 974 /* Return true only when STMT is simple enough for being handled by Graphite. 975 This depends on SCOP, as the parameters are initialized relatively to 976 this basic block, the linear functions are initialized based on the outermost 977 loop containing STMT inside the SCOP. BB is the place where we try to 978 evaluate the STMT. */ 979 980 bool 981 scop_detection::stmt_simple_for_scop_p (sese_l scop, gimple *stmt, 982 basic_block bb) const 983 { 984 gcc_assert (scop); 985 986 if (is_gimple_debug (stmt)) 987 return true; 988 989 if (stmt_has_side_effects (stmt)) 990 return false; 991 992 if (!stmt_has_simple_data_refs_p (scop, stmt)) 993 { 994 DEBUG_PRINT (dp << "[scop-detection-fail] " 995 << "Graphite cannot handle data-refs in stmt:\n"; 996 print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS);); 997 return false; 998 } 999 1000 switch (gimple_code (stmt)) 1001 { 1002 case GIMPLE_LABEL: 1003 return true; 1004 1005 case GIMPLE_COND: 1006 { 1007 /* We can handle all binary comparisons. Inequalities are 1008 also supported as they can be represented with union of 1009 polyhedra. */ 1010 enum tree_code code = gimple_cond_code (stmt); 1011 if (!(code == LT_EXPR 1012 || code == GT_EXPR 1013 || code == LE_EXPR 1014 || code == GE_EXPR 1015 || code == EQ_EXPR 1016 || code == NE_EXPR)) 1017 { 1018 DEBUG_PRINT (dp << "[scop-detection-fail] " 1019 << "Graphite cannot handle cond stmt:\n"; 1020 print_gimple_stmt (dump_file, stmt, 0, 1021 TDF_VOPS | TDF_MEMSYMS)); 1022 return false; 1023 } 1024 1025 loop_p loop = bb->loop_father; 1026 for (unsigned i = 0; i < 2; ++i) 1027 { 1028 tree op = gimple_op (stmt, i); 1029 if (!graphite_can_represent_expr (scop, loop, op) 1030 /* We can only constrain on integer type. */ 1031 || ! INTEGRAL_TYPE_P (TREE_TYPE (op))) 1032 { 1033 DEBUG_PRINT (dp << "[scop-detection-fail] " 1034 << "Graphite cannot represent stmt:\n"; 1035 print_gimple_stmt (dump_file, stmt, 0, 1036 TDF_VOPS | TDF_MEMSYMS)); 1037 return false; 1038 } 1039 } 1040 1041 return true; 1042 } 1043 1044 case GIMPLE_ASSIGN: 1045 case GIMPLE_CALL: 1046 { 1047 tree op, lhs = gimple_get_lhs (stmt); 1048 ssa_op_iter i; 1049 /* If we are not going to instantiate the stmt do not require 1050 its operands to be instantiatable at this point. */ 1051 if (lhs 1052 && TREE_CODE (lhs) == SSA_NAME 1053 && scev_analyzable_p (lhs, scop)) 1054 return true; 1055 /* Verify that if we can analyze operands at their def site we 1056 also can represent them when analyzed at their uses. */ 1057 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE) 1058 if (scev_analyzable_p (op, scop) 1059 && chrec_contains_undetermined 1060 (scalar_evolution_in_region (scop, bb->loop_father, op))) 1061 { 1062 DEBUG_PRINT (dp << "[scop-detection-fail] " 1063 << "Graphite cannot code-gen stmt:\n"; 1064 print_gimple_stmt (dump_file, stmt, 0, 1065 TDF_VOPS | TDF_MEMSYMS)); 1066 return false; 1067 } 1068 return true; 1069 } 1070 1071 default: 1072 /* These nodes cut a new scope. */ 1073 DEBUG_PRINT ( 1074 dp << "[scop-detection-fail] " 1075 << "Gimple stmt not handled in Graphite:\n"; 1076 print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS)); 1077 return false; 1078 } 1079 } 1080 1081 /* Returns the number of pbbs that are in loops contained in SCOP. */ 1082 1083 int 1084 scop_detection::nb_pbbs_in_loops (scop_p scop) 1085 { 1086 int i; 1087 poly_bb_p pbb; 1088 int res = 0; 1089 1090 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) 1091 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), scop->scop_info->region)) 1092 res++; 1093 1094 return res; 1095 } 1096 1097 /* Assigns the parameter NAME an index in REGION. */ 1098 1099 static void 1100 assign_parameter_index_in_region (tree name, sese_info_p region) 1101 { 1102 gcc_assert (TREE_CODE (name) == SSA_NAME 1103 && INTEGRAL_TYPE_P (TREE_TYPE (name)) 1104 && ! defined_in_sese_p (name, region->region)); 1105 1106 int i; 1107 tree p; 1108 FOR_EACH_VEC_ELT (region->params, i, p) 1109 if (p == name) 1110 return; 1111 1112 i = region->params.length (); 1113 region->params.safe_push (name); 1114 } 1115 1116 /* In the context of sese S, scan the expression E and translate it to 1117 a linear expression C. When parsing a symbolic multiplication, K 1118 represents the constant multiplier of an expression containing 1119 parameters. */ 1120 1121 static void 1122 scan_tree_for_params (sese_info_p s, tree e) 1123 { 1124 if (e == chrec_dont_know) 1125 return; 1126 1127 switch (TREE_CODE (e)) 1128 { 1129 case POLYNOMIAL_CHREC: 1130 scan_tree_for_params (s, CHREC_LEFT (e)); 1131 break; 1132 1133 case MULT_EXPR: 1134 if (chrec_contains_symbols (TREE_OPERAND (e, 0))) 1135 scan_tree_for_params (s, TREE_OPERAND (e, 0)); 1136 else 1137 scan_tree_for_params (s, TREE_OPERAND (e, 1)); 1138 break; 1139 1140 case PLUS_EXPR: 1141 case POINTER_PLUS_EXPR: 1142 case MINUS_EXPR: 1143 scan_tree_for_params (s, TREE_OPERAND (e, 0)); 1144 scan_tree_for_params (s, TREE_OPERAND (e, 1)); 1145 break; 1146 1147 case NEGATE_EXPR: 1148 case BIT_NOT_EXPR: 1149 CASE_CONVERT: 1150 case NON_LVALUE_EXPR: 1151 scan_tree_for_params (s, TREE_OPERAND (e, 0)); 1152 break; 1153 1154 case SSA_NAME: 1155 assign_parameter_index_in_region (e, s); 1156 break; 1157 1158 case INTEGER_CST: 1159 case ADDR_EXPR: 1160 case REAL_CST: 1161 case COMPLEX_CST: 1162 case VECTOR_CST: 1163 break; 1164 1165 default: 1166 gcc_unreachable (); 1167 break; 1168 } 1169 } 1170 1171 /* Find parameters with respect to REGION in BB. We are looking in memory 1172 access functions, conditions and loop bounds. */ 1173 1174 static void 1175 find_params_in_bb (sese_info_p region, gimple_poly_bb_p gbb) 1176 { 1177 /* Find parameters in the access functions of data references. */ 1178 int i; 1179 data_reference_p dr; 1180 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb), i, dr) 1181 for (unsigned j = 0; j < DR_NUM_DIMENSIONS (dr); j++) 1182 scan_tree_for_params (region, DR_ACCESS_FN (dr, j)); 1183 1184 /* Find parameters in conditional statements. */ 1185 gimple *stmt; 1186 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt) 1187 { 1188 loop_p loop = gimple_bb (stmt)->loop_father; 1189 tree lhs = scalar_evolution_in_region (region->region, loop, 1190 gimple_cond_lhs (stmt)); 1191 tree rhs = scalar_evolution_in_region (region->region, loop, 1192 gimple_cond_rhs (stmt)); 1193 gcc_assert (!chrec_contains_undetermined (lhs) 1194 && !chrec_contains_undetermined (rhs)); 1195 1196 scan_tree_for_params (region, lhs); 1197 scan_tree_for_params (region, rhs); 1198 } 1199 } 1200 1201 /* Record the parameters used in the SCOP BBs. A variable is a parameter 1202 in a scop if it does not vary during the execution of that scop. */ 1203 1204 static void 1205 find_scop_parameters (scop_p scop) 1206 { 1207 unsigned i; 1208 sese_info_p region = scop->scop_info; 1209 1210 /* Parameters used in loop bounds are processed during gather_bbs. */ 1211 1212 /* Find the parameters used in data accesses. */ 1213 poly_bb_p pbb; 1214 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) 1215 find_params_in_bb (region, PBB_BLACK_BOX (pbb)); 1216 1217 int nbp = sese_nb_params (region); 1218 scop_set_nb_params (scop, nbp); 1219 } 1220 1221 static void 1222 add_write (vec<tree> *writes, tree def) 1223 { 1224 writes->safe_push (def); 1225 DEBUG_PRINT (dp << "Adding scalar write: "; 1226 print_generic_expr (dump_file, def); 1227 dp << "\nFrom stmt: "; 1228 print_gimple_stmt (dump_file, 1229 SSA_NAME_DEF_STMT (def), 0)); 1230 } 1231 1232 static void 1233 add_read (vec<scalar_use> *reads, tree use, gimple *use_stmt) 1234 { 1235 DEBUG_PRINT (dp << "Adding scalar read: "; 1236 print_generic_expr (dump_file, use); 1237 dp << "\nFrom stmt: "; 1238 print_gimple_stmt (dump_file, use_stmt, 0)); 1239 reads->safe_push (std::make_pair (use_stmt, use)); 1240 } 1241 1242 1243 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */ 1244 1245 static void 1246 build_cross_bb_scalars_def (scop_p scop, tree def, basic_block def_bb, 1247 vec<tree> *writes) 1248 { 1249 if (!is_gimple_reg (def)) 1250 return; 1251 1252 bool scev_analyzable = scev_analyzable_p (def, scop->scop_info->region); 1253 1254 gimple *use_stmt; 1255 imm_use_iterator imm_iter; 1256 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def) 1257 /* Do not gather scalar variables that can be analyzed by SCEV as they can 1258 be generated out of the induction variables. */ 1259 if ((! scev_analyzable 1260 /* But gather SESE liveouts as we otherwise fail to rewrite their 1261 exit PHIs. */ 1262 || ! bb_in_sese_p (gimple_bb (use_stmt), scop->scop_info->region)) 1263 && (def_bb != gimple_bb (use_stmt) && !is_gimple_debug (use_stmt))) 1264 { 1265 add_write (writes, def); 1266 /* This is required by the FOR_EACH_IMM_USE_STMT when we want to break 1267 before all the uses have been visited. */ 1268 BREAK_FROM_IMM_USE_STMT (imm_iter); 1269 } 1270 } 1271 1272 /* Record USE if it is defined in other bbs different than USE_STMT 1273 in the SCOP. */ 1274 1275 static void 1276 build_cross_bb_scalars_use (scop_p scop, tree use, gimple *use_stmt, 1277 vec<scalar_use> *reads) 1278 { 1279 if (!is_gimple_reg (use)) 1280 return; 1281 1282 /* Do not gather scalar variables that can be analyzed by SCEV as they can be 1283 generated out of the induction variables. */ 1284 if (scev_analyzable_p (use, scop->scop_info->region)) 1285 return; 1286 1287 gimple *def_stmt = SSA_NAME_DEF_STMT (use); 1288 if (gimple_bb (def_stmt) != gimple_bb (use_stmt)) 1289 add_read (reads, use, use_stmt); 1290 } 1291 1292 /* Generates a polyhedral black box only if the bb contains interesting 1293 information. */ 1294 1295 static gimple_poly_bb_p 1296 try_generate_gimple_bb (scop_p scop, basic_block bb) 1297 { 1298 vec<data_reference_p> drs = vNULL; 1299 vec<tree> writes = vNULL; 1300 vec<scalar_use> reads = vNULL; 1301 1302 sese_l region = scop->scop_info->region; 1303 edge nest = region.entry; 1304 loop_p loop = bb->loop_father; 1305 if (!loop_in_sese_p (loop, region)) 1306 loop = NULL; 1307 1308 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); 1309 gsi_next (&gsi)) 1310 { 1311 gimple *stmt = gsi_stmt (gsi); 1312 if (is_gimple_debug (stmt)) 1313 continue; 1314 1315 graphite_find_data_references_in_stmt (nest, loop, stmt, &drs); 1316 1317 tree def = gimple_get_lhs (stmt); 1318 if (def) 1319 build_cross_bb_scalars_def (scop, def, gimple_bb (stmt), &writes); 1320 1321 ssa_op_iter iter; 1322 tree use; 1323 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) 1324 build_cross_bb_scalars_use (scop, use, stmt, &reads); 1325 } 1326 1327 /* Handle defs and uses in PHIs. Those need special treatment given 1328 that we have to present ISL with sth that looks like we've rewritten 1329 the IL out-of-SSA. */ 1330 for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi); 1331 gsi_next (&psi)) 1332 { 1333 gphi *phi = psi.phi (); 1334 tree res = gimple_phi_result (phi); 1335 if (virtual_operand_p (res) 1336 || scev_analyzable_p (res, scop->scop_info->region)) 1337 continue; 1338 /* To simulate out-of-SSA the block containing the PHI node has 1339 reads of the PHI destination. And to preserve SSA dependences 1340 we also write to it (the out-of-SSA decl and the SSA result 1341 are coalesced for dependence purposes which is good enough). */ 1342 add_read (&reads, res, phi); 1343 add_write (&writes, res); 1344 } 1345 basic_block bb_for_succs = bb; 1346 if (bb_for_succs == bb_for_succs->loop_father->latch 1347 && bb_in_sese_p (bb_for_succs, scop->scop_info->region) 1348 && sese_trivially_empty_bb_p (bb_for_succs)) 1349 bb_for_succs = NULL; 1350 while (bb_for_succs) 1351 { 1352 basic_block latch = NULL; 1353 edge_iterator ei; 1354 edge e; 1355 FOR_EACH_EDGE (e, ei, bb_for_succs->succs) 1356 { 1357 for (gphi_iterator psi = gsi_start_phis (e->dest); !gsi_end_p (psi); 1358 gsi_next (&psi)) 1359 { 1360 gphi *phi = psi.phi (); 1361 tree res = gimple_phi_result (phi); 1362 if (virtual_operand_p (res)) 1363 continue; 1364 /* To simulate out-of-SSA the predecessor of edges into PHI nodes 1365 has a copy from the PHI argument to the PHI destination. */ 1366 if (! scev_analyzable_p (res, scop->scop_info->region)) 1367 add_write (&writes, res); 1368 tree use = PHI_ARG_DEF_FROM_EDGE (phi, e); 1369 if (TREE_CODE (use) == SSA_NAME 1370 && ! SSA_NAME_IS_DEFAULT_DEF (use) 1371 && gimple_bb (SSA_NAME_DEF_STMT (use)) != bb_for_succs 1372 && ! scev_analyzable_p (use, scop->scop_info->region)) 1373 add_read (&reads, use, phi); 1374 } 1375 if (e->dest == bb_for_succs->loop_father->latch 1376 && bb_in_sese_p (e->dest, scop->scop_info->region) 1377 && sese_trivially_empty_bb_p (e->dest)) 1378 latch = e->dest; 1379 } 1380 /* Handle empty latch block PHIs here, otherwise we confuse ISL 1381 with extra conditional code where it then peels off the last 1382 iteration just because of that. It would be simplest if we 1383 just didn't force simple latches (thus remove the forwarder). */ 1384 bb_for_succs = latch; 1385 } 1386 1387 /* For the region exit block add reads for all live-out vars. */ 1388 if (bb == scop->scop_info->region.exit->src) 1389 { 1390 sese_build_liveouts (scop->scop_info); 1391 unsigned i; 1392 bitmap_iterator bi; 1393 EXECUTE_IF_SET_IN_BITMAP (scop->scop_info->liveout, 0, i, bi) 1394 { 1395 tree use = ssa_name (i); 1396 add_read (&reads, use, NULL); 1397 } 1398 } 1399 1400 if (drs.is_empty () && writes.is_empty () && reads.is_empty ()) 1401 return NULL; 1402 1403 return new_gimple_poly_bb (bb, drs, reads, writes); 1404 } 1405 1406 /* Compute alias-sets for all data references in DRS. */ 1407 1408 static bool 1409 build_alias_set (scop_p scop) 1410 { 1411 int num_vertices = scop->drs.length (); 1412 struct graph *g = new_graph (num_vertices); 1413 dr_info *dr1, *dr2; 1414 int i, j; 1415 int *all_vertices; 1416 1417 struct loop *nest 1418 = find_common_loop (scop->scop_info->region.entry->dest->loop_father, 1419 scop->scop_info->region.exit->src->loop_father); 1420 1421 FOR_EACH_VEC_ELT (scop->drs, i, dr1) 1422 for (j = i+1; scop->drs.iterate (j, &dr2); j++) 1423 if (dr_may_alias_p (dr1->dr, dr2->dr, nest)) 1424 { 1425 /* Dependences in the same alias set need to be handled 1426 by just looking at DR_ACCESS_FNs. */ 1427 if (DR_NUM_DIMENSIONS (dr1->dr) == 0 1428 || DR_NUM_DIMENSIONS (dr1->dr) != DR_NUM_DIMENSIONS (dr2->dr) 1429 || ! operand_equal_p (DR_BASE_OBJECT (dr1->dr), 1430 DR_BASE_OBJECT (dr2->dr), 1431 OEP_ADDRESS_OF) 1432 || ! types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1->dr)), 1433 TREE_TYPE (DR_BASE_OBJECT (dr2->dr)))) 1434 { 1435 free_graph (g); 1436 return false; 1437 } 1438 add_edge (g, i, j); 1439 add_edge (g, j, i); 1440 } 1441 1442 all_vertices = XNEWVEC (int, num_vertices); 1443 for (i = 0; i < num_vertices; i++) 1444 all_vertices[i] = i; 1445 1446 scop->max_alias_set 1447 = graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL) + 1; 1448 free (all_vertices); 1449 1450 for (i = 0; i < g->n_vertices; i++) 1451 scop->drs[i].alias_set = g->vertices[i].component + 1; 1452 1453 free_graph (g); 1454 return true; 1455 } 1456 1457 /* Gather BBs and conditions for a SCOP. */ 1458 class gather_bbs : public dom_walker 1459 { 1460 public: 1461 gather_bbs (cdi_direction, scop_p, int *); 1462 1463 virtual edge before_dom_children (basic_block); 1464 virtual void after_dom_children (basic_block); 1465 1466 private: 1467 auto_vec<gimple *, 3> conditions, cases; 1468 scop_p scop; 1469 }; 1470 } 1471 gather_bbs::gather_bbs (cdi_direction direction, scop_p scop, int *bb_to_rpo) 1472 : dom_walker (direction, ALL_BLOCKS, bb_to_rpo), scop (scop) 1473 { 1474 } 1475 1476 /* Call-back for dom_walk executed before visiting the dominated 1477 blocks. */ 1478 1479 edge 1480 gather_bbs::before_dom_children (basic_block bb) 1481 { 1482 sese_info_p region = scop->scop_info; 1483 if (!bb_in_sese_p (bb, region->region)) 1484 return dom_walker::STOP; 1485 1486 /* For loops fully contained in the region record parameters in the 1487 loop bounds. */ 1488 loop_p loop = bb->loop_father; 1489 if (loop->header == bb 1490 && loop_in_sese_p (loop, region->region)) 1491 { 1492 tree nb_iters = number_of_latch_executions (loop); 1493 if (chrec_contains_symbols (nb_iters)) 1494 { 1495 nb_iters = scalar_evolution_in_region (region->region, 1496 loop, nb_iters); 1497 scan_tree_for_params (region, nb_iters); 1498 } 1499 } 1500 1501 if (gcond *stmt = single_pred_cond_non_loop_exit (bb)) 1502 { 1503 edge e = single_pred_edge (bb); 1504 /* Make sure the condition is in the region and thus was verified 1505 to be handled. */ 1506 if (e != region->region.entry) 1507 { 1508 conditions.safe_push (stmt); 1509 if (e->flags & EDGE_TRUE_VALUE) 1510 cases.safe_push (stmt); 1511 else 1512 cases.safe_push (NULL); 1513 } 1514 } 1515 1516 scop->scop_info->bbs.safe_push (bb); 1517 1518 gimple_poly_bb_p gbb = try_generate_gimple_bb (scop, bb); 1519 if (!gbb) 1520 return NULL; 1521 1522 GBB_CONDITIONS (gbb) = conditions.copy (); 1523 GBB_CONDITION_CASES (gbb) = cases.copy (); 1524 1525 poly_bb_p pbb = new_poly_bb (scop, gbb); 1526 scop->pbbs.safe_push (pbb); 1527 1528 int i; 1529 data_reference_p dr; 1530 FOR_EACH_VEC_ELT (gbb->data_refs, i, dr) 1531 { 1532 DEBUG_PRINT (dp << "Adding memory "; 1533 if (dr->is_read) 1534 dp << "read: "; 1535 else 1536 dp << "write: "; 1537 print_generic_expr (dump_file, dr->ref); 1538 dp << "\nFrom stmt: "; 1539 print_gimple_stmt (dump_file, dr->stmt, 0)); 1540 1541 scop->drs.safe_push (dr_info (dr, pbb)); 1542 } 1543 1544 return NULL; 1545 } 1546 1547 /* Call-back for dom_walk executed after visiting the dominated 1548 blocks. */ 1549 1550 void 1551 gather_bbs::after_dom_children (basic_block bb) 1552 { 1553 if (!bb_in_sese_p (bb, scop->scop_info->region)) 1554 return; 1555 1556 if (single_pred_cond_non_loop_exit (bb)) 1557 { 1558 edge e = single_pred_edge (bb); 1559 if (e != scop->scop_info->region.entry) 1560 { 1561 conditions.pop (); 1562 cases.pop (); 1563 } 1564 } 1565 } 1566 1567 1568 /* Compute sth like an execution order, dominator order with first executing 1569 edges that stay inside the current loop, delaying processing exit edges. */ 1570 1571 static int *bb_to_rpo; 1572 1573 /* Helper for qsort, sorting after order above. */ 1574 1575 static int 1576 cmp_pbbs (const void *pa, const void *pb) 1577 { 1578 poly_bb_p bb1 = *((const poly_bb_p *)pa); 1579 poly_bb_p bb2 = *((const poly_bb_p *)pb); 1580 if (bb_to_rpo[bb1->black_box->bb->index] 1581 < bb_to_rpo[bb2->black_box->bb->index]) 1582 return -1; 1583 else if (bb_to_rpo[bb1->black_box->bb->index] 1584 > bb_to_rpo[bb2->black_box->bb->index]) 1585 return 1; 1586 else 1587 return 0; 1588 } 1589 1590 /* Find Static Control Parts (SCoP) in the current function and pushes 1591 them to SCOPS. */ 1592 1593 void 1594 build_scops (vec<scop_p> *scops) 1595 { 1596 if (dump_file) 1597 dp.set_dump_file (dump_file); 1598 1599 scop_detection sb; 1600 sb.build_scop_depth (current_loops->tree_root); 1601 1602 /* Now create scops from the lightweight SESEs. */ 1603 vec<sese_l> scops_l = sb.get_scops (); 1604 1605 /* Domwalk needs a bb to RPO mapping. Compute it once here. */ 1606 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun)); 1607 int postorder_num = pre_and_rev_post_order_compute (NULL, postorder, true); 1608 bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun)); 1609 for (int i = 0; i < postorder_num; ++i) 1610 bb_to_rpo[postorder[i]] = i; 1611 free (postorder); 1612 1613 int i; 1614 sese_l *s; 1615 FOR_EACH_VEC_ELT (scops_l, i, s) 1616 { 1617 scop_p scop = new_scop (s->entry, s->exit); 1618 1619 /* Record all basic blocks and their conditions in REGION. */ 1620 gather_bbs (CDI_DOMINATORS, scop, bb_to_rpo).walk (s->entry->dest); 1621 1622 /* Sort pbbs after execution order for initial schedule generation. */ 1623 scop->pbbs.qsort (cmp_pbbs); 1624 1625 if (! build_alias_set (scop)) 1626 { 1627 DEBUG_PRINT (dp << "[scop-detection-fail] cannot handle dependences\n"); 1628 free_scop (scop); 1629 continue; 1630 } 1631 1632 /* Do not optimize a scop containing only PBBs that do not belong 1633 to any loops. */ 1634 if (sb.nb_pbbs_in_loops (scop) == 0) 1635 { 1636 DEBUG_PRINT (dp << "[scop-detection-fail] no data references.\n"); 1637 free_scop (scop); 1638 continue; 1639 } 1640 1641 unsigned max_arrays = PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP); 1642 if (max_arrays > 0 1643 && scop->drs.length () >= max_arrays) 1644 { 1645 DEBUG_PRINT (dp << "[scop-detection-fail] too many data references: " 1646 << scop->drs.length () 1647 << " is larger than --param graphite-max-arrays-per-scop=" 1648 << max_arrays << ".\n"); 1649 free_scop (scop); 1650 continue; 1651 } 1652 1653 find_scop_parameters (scop); 1654 graphite_dim_t max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS); 1655 if (max_dim > 0 1656 && scop_nb_params (scop) > max_dim) 1657 { 1658 DEBUG_PRINT (dp << "[scop-detection-fail] too many parameters: " 1659 << scop_nb_params (scop) 1660 << " larger than --param graphite-max-nb-scop-params=" 1661 << max_dim << ".\n"); 1662 free_scop (scop); 1663 continue; 1664 } 1665 1666 scops->safe_push (scop); 1667 } 1668 1669 free (bb_to_rpo); 1670 bb_to_rpo = NULL; 1671 DEBUG_PRINT (dp << "number of SCoPs: " << (scops ? scops->length () : 0);); 1672 } 1673 1674 #endif /* HAVE_isl */ 1675