1 /* Detection of Static Control Parts (SCoP) for Graphite. 2 Copyright (C) 2009-2015 Free Software Foundation, Inc. 3 Contributed by Sebastian Pop <sebastian.pop@amd.com> and 4 Tobias Grosser <grosser@fim.uni-passau.de>. 5 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 #include "config.h" 23 24 #ifdef HAVE_isl 25 #include <isl/constraint.h> 26 #include <isl/set.h> 27 #include <isl/map.h> 28 #include <isl/union_map.h> 29 #endif 30 31 #include "system.h" 32 #include "coretypes.h" 33 #include "hash-set.h" 34 #include "machmode.h" 35 #include "vec.h" 36 #include "double-int.h" 37 #include "input.h" 38 #include "alias.h" 39 #include "symtab.h" 40 #include "options.h" 41 #include "wide-int.h" 42 #include "inchash.h" 43 #include "tree.h" 44 #include "fold-const.h" 45 #include "predict.h" 46 #include "tm.h" 47 #include "hard-reg-set.h" 48 #include "input.h" 49 #include "function.h" 50 #include "dominance.h" 51 #include "cfg.h" 52 #include "basic-block.h" 53 #include "tree-ssa-alias.h" 54 #include "internal-fn.h" 55 #include "gimple-expr.h" 56 #include "is-a.h" 57 #include "gimple.h" 58 #include "gimple-iterator.h" 59 #include "gimple-ssa.h" 60 #include "tree-phinodes.h" 61 #include "ssa-iterators.h" 62 #include "tree-ssa-loop-manip.h" 63 #include "tree-ssa-loop-niter.h" 64 #include "tree-ssa-loop.h" 65 #include "tree-into-ssa.h" 66 #include "tree-ssa.h" 67 #include "cfgloop.h" 68 #include "tree-chrec.h" 69 #include "tree-data-ref.h" 70 #include "tree-scalar-evolution.h" 71 #include "tree-pass.h" 72 #include "sese.h" 73 #include "tree-ssa-propagate.h" 74 #include "cp/cp-tree.h" 75 76 #ifdef HAVE_isl 77 #include "graphite-poly.h" 78 #include "graphite-scop-detection.h" 79 80 /* Forward declarations. */ 81 static void make_close_phi_nodes_unique (basic_block); 82 83 /* The type of the analyzed basic block. */ 84 85 typedef enum gbb_type { 86 GBB_UNKNOWN, 87 GBB_LOOP_SING_EXIT_HEADER, 88 GBB_LOOP_MULT_EXIT_HEADER, 89 GBB_LOOP_EXIT, 90 GBB_COND_HEADER, 91 GBB_SIMPLE, 92 GBB_LAST 93 } gbb_type; 94 95 /* Detect the type of BB. Loop headers are only marked, if they are 96 new. This means their loop_father is different to LAST_LOOP. 97 Otherwise they are treated like any other bb and their type can be 98 any other type. */ 99 100 static gbb_type 101 get_bb_type (basic_block bb, struct loop *last_loop) 102 { 103 vec<basic_block> dom; 104 int nb_dom; 105 struct loop *loop = bb->loop_father; 106 107 /* Check, if we entry into a new loop. */ 108 if (loop != last_loop) 109 { 110 if (single_exit (loop) != NULL) 111 return GBB_LOOP_SING_EXIT_HEADER; 112 else if (loop->num != 0) 113 return GBB_LOOP_MULT_EXIT_HEADER; 114 else 115 return GBB_COND_HEADER; 116 } 117 118 dom = get_dominated_by (CDI_DOMINATORS, bb); 119 nb_dom = dom.length (); 120 dom.release (); 121 122 if (nb_dom == 0) 123 return GBB_LAST; 124 125 if (nb_dom == 1 && single_succ_p (bb)) 126 return GBB_SIMPLE; 127 128 return GBB_COND_HEADER; 129 } 130 131 /* A SCoP detection region, defined using bbs as borders. 132 133 All control flow touching this region, comes in passing basic_block 134 ENTRY and leaves passing basic_block EXIT. By using bbs instead of 135 edges for the borders we are able to represent also regions that do 136 not have a single entry or exit edge. 137 138 But as they have a single entry basic_block and a single exit 139 basic_block, we are able to generate for every sd_region a single 140 entry and exit edge. 141 142 1 2 143 \ / 144 3 <- entry 145 | 146 4 147 / \ This region contains: {3, 4, 5, 6, 7, 8} 148 5 6 149 | | 150 7 8 151 \ / 152 9 <- exit */ 153 154 155 typedef struct sd_region_p 156 { 157 /* The entry bb dominates all bbs in the sd_region. It is part of 158 the region. */ 159 basic_block entry; 160 161 /* The exit bb postdominates all bbs in the sd_region, but is not 162 part of the region. */ 163 basic_block exit; 164 } sd_region; 165 166 167 168 /* Moves the scops from SOURCE to TARGET and clean up SOURCE. */ 169 170 static void 171 move_sd_regions (vec<sd_region> *source, vec<sd_region> *target) 172 { 173 sd_region *s; 174 int i; 175 176 FOR_EACH_VEC_ELT (*source, i, s) 177 target->safe_push (*s); 178 179 source->release (); 180 } 181 182 /* Something like "n * m" is not allowed. */ 183 184 static bool 185 graphite_can_represent_init (tree e) 186 { 187 switch (TREE_CODE (e)) 188 { 189 case POLYNOMIAL_CHREC: 190 return graphite_can_represent_init (CHREC_LEFT (e)) 191 && graphite_can_represent_init (CHREC_RIGHT (e)); 192 193 case MULT_EXPR: 194 if (chrec_contains_symbols (TREE_OPERAND (e, 0))) 195 return graphite_can_represent_init (TREE_OPERAND (e, 0)) 196 && tree_fits_shwi_p (TREE_OPERAND (e, 1)); 197 else 198 return graphite_can_represent_init (TREE_OPERAND (e, 1)) 199 && tree_fits_shwi_p (TREE_OPERAND (e, 0)); 200 201 case PLUS_EXPR: 202 case POINTER_PLUS_EXPR: 203 case MINUS_EXPR: 204 return graphite_can_represent_init (TREE_OPERAND (e, 0)) 205 && graphite_can_represent_init (TREE_OPERAND (e, 1)); 206 207 case NEGATE_EXPR: 208 case BIT_NOT_EXPR: 209 CASE_CONVERT: 210 case NON_LVALUE_EXPR: 211 return graphite_can_represent_init (TREE_OPERAND (e, 0)); 212 213 default: 214 break; 215 } 216 217 return true; 218 } 219 220 /* Return true when SCEV can be represented in the polyhedral model. 221 222 An expression can be represented, if it can be expressed as an 223 affine expression. For loops (i, j) and parameters (m, n) all 224 affine expressions are of the form: 225 226 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z 227 228 1 i + 20 j + (-2) m + 25 229 230 Something like "i * n" or "n * m" is not allowed. */ 231 232 static bool 233 graphite_can_represent_scev (tree scev) 234 { 235 if (chrec_contains_undetermined (scev)) 236 return false; 237 238 /* We disable the handling of pointer types, because it’s currently not 239 supported by Graphite with the ISL AST generator. SSA_NAME nodes are 240 the only nodes, which are disabled in case they are pointers to object 241 types, but this can be changed. */ 242 243 if (TYPE_PTROB_P (TREE_TYPE (scev)) && TREE_CODE (scev) == SSA_NAME) 244 return false; 245 246 switch (TREE_CODE (scev)) 247 { 248 case NEGATE_EXPR: 249 case BIT_NOT_EXPR: 250 CASE_CONVERT: 251 case NON_LVALUE_EXPR: 252 return graphite_can_represent_scev (TREE_OPERAND (scev, 0)); 253 254 case PLUS_EXPR: 255 case POINTER_PLUS_EXPR: 256 case MINUS_EXPR: 257 return graphite_can_represent_scev (TREE_OPERAND (scev, 0)) 258 && graphite_can_represent_scev (TREE_OPERAND (scev, 1)); 259 260 case MULT_EXPR: 261 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0))) 262 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1))) 263 && !(chrec_contains_symbols (TREE_OPERAND (scev, 0)) 264 && chrec_contains_symbols (TREE_OPERAND (scev, 1))) 265 && graphite_can_represent_init (scev) 266 && graphite_can_represent_scev (TREE_OPERAND (scev, 0)) 267 && graphite_can_represent_scev (TREE_OPERAND (scev, 1)); 268 269 case POLYNOMIAL_CHREC: 270 /* Check for constant strides. With a non constant stride of 271 'n' we would have a value of 'iv * n'. Also check that the 272 initial value can represented: for example 'n * m' cannot be 273 represented. */ 274 if (!evolution_function_right_is_integer_cst (scev) 275 || !graphite_can_represent_init (scev)) 276 return false; 277 return graphite_can_represent_scev (CHREC_LEFT (scev)); 278 279 default: 280 break; 281 } 282 283 /* Only affine functions can be represented. */ 284 if (tree_contains_chrecs (scev, NULL) 285 || !scev_is_linear_expression (scev)) 286 return false; 287 288 return true; 289 } 290 291 292 /* Return true when EXPR can be represented in the polyhedral model. 293 294 This means an expression can be represented, if it is linear with 295 respect to the loops and the strides are non parametric. 296 LOOP is the place where the expr will be evaluated. SCOP_ENTRY defines the 297 entry of the region we analyse. */ 298 299 static bool 300 graphite_can_represent_expr (basic_block scop_entry, loop_p loop, 301 tree expr) 302 { 303 tree scev = analyze_scalar_evolution (loop, expr); 304 305 scev = instantiate_scev (scop_entry, loop, scev); 306 307 return graphite_can_represent_scev (scev); 308 } 309 310 /* Return true if the data references of STMT can be represented by 311 Graphite. */ 312 313 static bool 314 stmt_has_simple_data_refs_p (loop_p outermost_loop ATTRIBUTE_UNUSED, 315 gimple stmt) 316 { 317 data_reference_p dr; 318 unsigned i; 319 int j; 320 bool res = true; 321 vec<data_reference_p> drs = vNULL; 322 loop_p outer; 323 324 for (outer = loop_containing_stmt (stmt); outer; outer = loop_outer (outer)) 325 { 326 graphite_find_data_references_in_stmt (outer, 327 loop_containing_stmt (stmt), 328 stmt, &drs); 329 330 FOR_EACH_VEC_ELT (drs, j, dr) 331 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++) 332 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr, i))) 333 { 334 res = false; 335 goto done; 336 } 337 338 free_data_refs (drs); 339 drs.create (0); 340 } 341 342 done: 343 free_data_refs (drs); 344 return res; 345 } 346 347 /* Return true only when STMT is simple enough for being handled by 348 Graphite. This depends on SCOP_ENTRY, as the parameters are 349 initialized relatively to this basic block, the linear functions 350 are initialized to OUTERMOST_LOOP and BB is the place where we try 351 to evaluate the STMT. */ 352 353 static bool 354 stmt_simple_for_scop_p (basic_block scop_entry, loop_p outermost_loop, 355 gimple stmt, basic_block bb) 356 { 357 loop_p loop = bb->loop_father; 358 359 gcc_assert (scop_entry); 360 361 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects. 362 Calls have side-effects, except those to const or pure 363 functions. */ 364 if (gimple_has_volatile_ops (stmt) 365 || (gimple_code (stmt) == GIMPLE_CALL 366 && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE))) 367 || (gimple_code (stmt) == GIMPLE_ASM)) 368 return false; 369 370 if (is_gimple_debug (stmt)) 371 return true; 372 373 if (!stmt_has_simple_data_refs_p (outermost_loop, stmt)) 374 return false; 375 376 switch (gimple_code (stmt)) 377 { 378 case GIMPLE_RETURN: 379 case GIMPLE_LABEL: 380 return true; 381 382 case GIMPLE_COND: 383 { 384 /* We can handle all binary comparisons. Inequalities are 385 also supported as they can be represented with union of 386 polyhedra. */ 387 enum tree_code code = gimple_cond_code (stmt); 388 if (!(code == LT_EXPR 389 || code == GT_EXPR 390 || code == LE_EXPR 391 || code == GE_EXPR 392 || code == EQ_EXPR 393 || code == NE_EXPR)) 394 return false; 395 396 for (unsigned i = 0; i < 2; ++i) 397 { 398 tree op = gimple_op (stmt, i); 399 if (!graphite_can_represent_expr (scop_entry, loop, op) 400 /* We can not handle REAL_TYPE. Failed for pr39260. */ 401 || TREE_CODE (TREE_TYPE (op)) == REAL_TYPE) 402 return false; 403 } 404 405 return true; 406 } 407 408 case GIMPLE_ASSIGN: 409 case GIMPLE_CALL: 410 return true; 411 412 default: 413 /* These nodes cut a new scope. */ 414 return false; 415 } 416 417 return false; 418 } 419 420 /* Returns the statement of BB that contains a harmful operation: that 421 can be a function call with side effects, the induction variables 422 are not linear with respect to SCOP_ENTRY, etc. The current open 423 scop should end before this statement. The evaluation is limited using 424 OUTERMOST_LOOP as outermost loop that may change. */ 425 426 static gimple 427 harmful_stmt_in_bb (basic_block scop_entry, loop_p outer_loop, basic_block bb) 428 { 429 gimple_stmt_iterator gsi; 430 431 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 432 if (!stmt_simple_for_scop_p (scop_entry, outer_loop, gsi_stmt (gsi), bb)) 433 return gsi_stmt (gsi); 434 435 return NULL; 436 } 437 438 /* Return true if LOOP can be represented in the polyhedral 439 representation. This is evaluated taking SCOP_ENTRY and 440 OUTERMOST_LOOP in mind. */ 441 442 static bool 443 graphite_can_represent_loop (basic_block scop_entry, loop_p loop) 444 { 445 tree niter; 446 struct tree_niter_desc niter_desc; 447 448 /* FIXME: For the moment, graphite cannot be used on loops that 449 iterate using induction variables that wrap. */ 450 451 return number_of_iterations_exit (loop, single_exit (loop), &niter_desc, false) 452 && niter_desc.control.no_overflow 453 && (niter = number_of_latch_executions (loop)) 454 && !chrec_contains_undetermined (niter) 455 && graphite_can_represent_expr (scop_entry, loop, niter); 456 } 457 458 /* Store information needed by scopdet_* functions. */ 459 460 struct scopdet_info 461 { 462 /* Exit of the open scop would stop if the current BB is harmful. */ 463 basic_block exit; 464 465 /* Where the next scop would start if the current BB is harmful. */ 466 basic_block next; 467 468 /* The bb or one of its children contains open loop exits. That means 469 loop exit nodes that are not surrounded by a loop dominated by bb. */ 470 bool exits; 471 472 /* The bb or one of its children contains only structures we can handle. */ 473 bool difficult; 474 }; 475 476 static struct scopdet_info build_scops_1 (basic_block, loop_p, 477 vec<sd_region> *, loop_p); 478 479 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB 480 to SCOPS. TYPE is the gbb_type of BB. */ 481 482 static struct scopdet_info 483 scopdet_basic_block_info (basic_block bb, loop_p outermost_loop, 484 vec<sd_region> *scops, gbb_type type) 485 { 486 loop_p loop = bb->loop_father; 487 struct scopdet_info result; 488 gimple stmt; 489 490 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */ 491 basic_block entry_block = ENTRY_BLOCK_PTR_FOR_FN (cfun); 492 stmt = harmful_stmt_in_bb (entry_block, outermost_loop, bb); 493 result.difficult = (stmt != NULL); 494 result.exit = NULL; 495 496 switch (type) 497 { 498 case GBB_LAST: 499 result.next = NULL; 500 result.exits = false; 501 502 /* Mark bbs terminating a SESE region difficult, if they start 503 a condition or if the block it exits to cannot be split 504 with make_forwarder_block. */ 505 if (!single_succ_p (bb) 506 || bb_has_abnormal_pred (single_succ (bb))) 507 result.difficult = true; 508 else 509 result.exit = single_succ (bb); 510 511 break; 512 513 case GBB_SIMPLE: 514 result.next = single_succ (bb); 515 result.exits = false; 516 result.exit = single_succ (bb); 517 break; 518 519 case GBB_LOOP_SING_EXIT_HEADER: 520 { 521 auto_vec<sd_region, 3> regions; 522 struct scopdet_info sinfo; 523 edge exit_e = single_exit (loop); 524 525 sinfo = build_scops_1 (bb, outermost_loop, ®ions, loop); 526 527 if (!graphite_can_represent_loop (entry_block, loop)) 528 result.difficult = true; 529 530 result.difficult |= sinfo.difficult; 531 532 /* Try again with another loop level. */ 533 if (result.difficult 534 && loop_depth (outermost_loop) + 1 == loop_depth (loop)) 535 { 536 outermost_loop = loop; 537 538 regions.release (); 539 regions.create (3); 540 541 sinfo = scopdet_basic_block_info (bb, outermost_loop, scops, type); 542 543 result = sinfo; 544 result.difficult = true; 545 546 if (sinfo.difficult) 547 move_sd_regions (®ions, scops); 548 else 549 { 550 sd_region open_scop; 551 open_scop.entry = bb; 552 open_scop.exit = exit_e->dest; 553 scops->safe_push (open_scop); 554 regions.release (); 555 } 556 } 557 else 558 { 559 result.exit = exit_e->dest; 560 result.next = exit_e->dest; 561 562 /* If we do not dominate result.next, remove it. It's either 563 the exit block, or another bb dominates it and will 564 call the scop detection for this bb. */ 565 if (!dominated_by_p (CDI_DOMINATORS, result.next, bb)) 566 result.next = NULL; 567 568 if (exit_e->src->loop_father != loop) 569 result.next = NULL; 570 571 result.exits = false; 572 573 if (result.difficult) 574 move_sd_regions (®ions, scops); 575 else 576 regions.release (); 577 } 578 579 break; 580 } 581 582 case GBB_LOOP_MULT_EXIT_HEADER: 583 { 584 /* XXX: For now we just do not join loops with multiple exits. If the 585 exits lead to the same bb it may be possible to join the loop. */ 586 auto_vec<sd_region, 3> regions; 587 vec<edge> exits = get_loop_exit_edges (loop); 588 edge e; 589 int i; 590 build_scops_1 (bb, loop, ®ions, loop); 591 592 /* Scan the code dominated by this loop. This means all bbs, that are 593 are dominated by a bb in this loop, but are not part of this loop. 594 595 The easiest case: 596 - The loop exit destination is dominated by the exit sources. 597 598 TODO: We miss here the more complex cases: 599 - The exit destinations are dominated by another bb inside 600 the loop. 601 - The loop dominates bbs, that are not exit destinations. */ 602 FOR_EACH_VEC_ELT (exits, i, e) 603 if (e->src->loop_father == loop 604 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)) 605 { 606 if (loop_outer (outermost_loop)) 607 outermost_loop = loop_outer (outermost_loop); 608 609 /* Pass loop_outer to recognize e->dest as loop header in 610 build_scops_1. */ 611 if (e->dest->loop_father->header == e->dest) 612 build_scops_1 (e->dest, outermost_loop, ®ions, 613 loop_outer (e->dest->loop_father)); 614 else 615 build_scops_1 (e->dest, outermost_loop, ®ions, 616 e->dest->loop_father); 617 } 618 619 result.next = NULL; 620 result.exit = NULL; 621 result.difficult = true; 622 result.exits = false; 623 move_sd_regions (®ions, scops); 624 exits.release (); 625 break; 626 } 627 case GBB_COND_HEADER: 628 { 629 auto_vec<sd_region, 3> regions; 630 struct scopdet_info sinfo; 631 vec<basic_block> dominated; 632 int i; 633 basic_block dom_bb; 634 basic_block last_exit = NULL; 635 edge e; 636 result.exits = false; 637 638 /* First check the successors of BB, and check if it is 639 possible to join the different branches. */ 640 FOR_EACH_VEC_SAFE_ELT (bb->succs, i, e) 641 { 642 /* Ignore loop exits. They will be handled after the loop 643 body. */ 644 if (loop_exits_to_bb_p (loop, e->dest)) 645 { 646 result.exits = true; 647 continue; 648 } 649 650 /* Do not follow edges that lead to the end of the 651 conditions block. For example, in 652 653 | 0 654 | /|\ 655 | 1 2 | 656 | | | | 657 | 3 4 | 658 | \|/ 659 | 6 660 661 the edge from 0 => 6. Only check if all paths lead to 662 the same node 6. */ 663 664 if (!single_pred_p (e->dest)) 665 { 666 /* Check, if edge leads directly to the end of this 667 condition. */ 668 if (!last_exit) 669 last_exit = e->dest; 670 671 if (e->dest != last_exit) 672 result.difficult = true; 673 674 continue; 675 } 676 677 if (!dominated_by_p (CDI_DOMINATORS, e->dest, bb)) 678 { 679 result.difficult = true; 680 continue; 681 } 682 683 sinfo = build_scops_1 (e->dest, outermost_loop, ®ions, loop); 684 685 result.exits |= sinfo.exits; 686 result.difficult |= sinfo.difficult; 687 688 /* Checks, if all branches end at the same point. 689 If that is true, the condition stays joinable. 690 Have a look at the example above. */ 691 if (sinfo.exit) 692 { 693 if (!last_exit) 694 last_exit = sinfo.exit; 695 696 if (sinfo.exit != last_exit) 697 result.difficult = true; 698 } 699 else 700 result.difficult = true; 701 } 702 703 if (!last_exit) 704 result.difficult = true; 705 706 /* Join the branches of the condition if possible. */ 707 if (!result.exits && !result.difficult) 708 { 709 /* Only return a next pointer if we dominate this pointer. 710 Otherwise it will be handled by the bb dominating it. */ 711 if (dominated_by_p (CDI_DOMINATORS, last_exit, bb) 712 && last_exit != bb) 713 result.next = last_exit; 714 else 715 result.next = NULL; 716 717 result.exit = last_exit; 718 719 regions.release (); 720 break; 721 } 722 723 /* Scan remaining bbs dominated by BB. */ 724 dominated = get_dominated_by (CDI_DOMINATORS, bb); 725 726 FOR_EACH_VEC_ELT (dominated, i, dom_bb) 727 { 728 /* Ignore loop exits: they will be handled after the loop body. */ 729 if (loop_depth (find_common_loop (loop, dom_bb->loop_father)) 730 < loop_depth (loop)) 731 { 732 result.exits = true; 733 continue; 734 } 735 736 /* Ignore the bbs processed above. */ 737 if (single_pred_p (dom_bb) && single_pred (dom_bb) == bb) 738 continue; 739 740 if (loop_depth (loop) > loop_depth (dom_bb->loop_father)) 741 sinfo = build_scops_1 (dom_bb, outermost_loop, ®ions, 742 loop_outer (loop)); 743 else 744 sinfo = build_scops_1 (dom_bb, outermost_loop, ®ions, loop); 745 746 result.exits |= sinfo.exits; 747 result.difficult = true; 748 result.exit = NULL; 749 } 750 751 dominated.release (); 752 753 result.next = NULL; 754 move_sd_regions (®ions, scops); 755 756 break; 757 } 758 759 default: 760 gcc_unreachable (); 761 } 762 763 return result; 764 } 765 766 /* Starting from CURRENT we walk the dominance tree and add new sd_regions to 767 SCOPS. The analyse if a sd_region can be handled is based on the value 768 of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change. LOOP 769 is the loop in which CURRENT is handled. 770 771 TODO: These functions got a little bit big. They definitely should be cleaned 772 up. */ 773 774 static struct scopdet_info 775 build_scops_1 (basic_block current, loop_p outermost_loop, 776 vec<sd_region> *scops, loop_p loop) 777 { 778 bool in_scop = false; 779 sd_region open_scop; 780 struct scopdet_info sinfo; 781 782 /* Initialize result. */ 783 struct scopdet_info result; 784 result.exits = false; 785 result.difficult = false; 786 result.next = NULL; 787 result.exit = NULL; 788 open_scop.entry = NULL; 789 open_scop.exit = NULL; 790 sinfo.exit = NULL; 791 792 /* Loop over the dominance tree. If we meet a difficult bb, close 793 the current SCoP. Loop and condition header start a new layer, 794 and can only be added if all bbs in deeper layers are simple. */ 795 while (current != NULL) 796 { 797 sinfo = scopdet_basic_block_info (current, outermost_loop, scops, 798 get_bb_type (current, loop)); 799 800 if (!in_scop && !(sinfo.exits || sinfo.difficult)) 801 { 802 open_scop.entry = current; 803 open_scop.exit = NULL; 804 in_scop = true; 805 } 806 else if (in_scop && (sinfo.exits || sinfo.difficult)) 807 { 808 open_scop.exit = current; 809 scops->safe_push (open_scop); 810 in_scop = false; 811 } 812 813 result.difficult |= sinfo.difficult; 814 result.exits |= sinfo.exits; 815 816 current = sinfo.next; 817 } 818 819 /* Try to close open_scop, if we are still in an open SCoP. */ 820 if (in_scop) 821 { 822 open_scop.exit = sinfo.exit; 823 gcc_assert (open_scop.exit); 824 scops->safe_push (open_scop); 825 } 826 827 result.exit = sinfo.exit; 828 return result; 829 } 830 831 /* Checks if a bb is contained in REGION. */ 832 833 static bool 834 bb_in_sd_region (basic_block bb, sd_region *region) 835 { 836 return bb_in_region (bb, region->entry, region->exit); 837 } 838 839 /* Returns the single entry edge of REGION, if it does not exits NULL. */ 840 841 static edge 842 find_single_entry_edge (sd_region *region) 843 { 844 edge e; 845 edge_iterator ei; 846 edge entry = NULL; 847 848 FOR_EACH_EDGE (e, ei, region->entry->preds) 849 if (!bb_in_sd_region (e->src, region)) 850 { 851 if (entry) 852 { 853 entry = NULL; 854 break; 855 } 856 857 else 858 entry = e; 859 } 860 861 return entry; 862 } 863 864 /* Returns the single exit edge of REGION, if it does not exits NULL. */ 865 866 static edge 867 find_single_exit_edge (sd_region *region) 868 { 869 edge e; 870 edge_iterator ei; 871 edge exit = NULL; 872 873 FOR_EACH_EDGE (e, ei, region->exit->preds) 874 if (bb_in_sd_region (e->src, region)) 875 { 876 if (exit) 877 { 878 exit = NULL; 879 break; 880 } 881 882 else 883 exit = e; 884 } 885 886 return exit; 887 } 888 889 /* Create a single entry edge for REGION. */ 890 891 static void 892 create_single_entry_edge (sd_region *region) 893 { 894 if (find_single_entry_edge (region)) 895 return; 896 897 /* There are multiple predecessors for bb_3 898 899 | 1 2 900 | | / 901 | |/ 902 | 3 <- entry 903 | |\ 904 | | | 905 | 4 ^ 906 | | | 907 | |/ 908 | 5 909 910 There are two edges (1->3, 2->3), that point from outside into the region, 911 and another one (5->3), a loop latch, lead to bb_3. 912 913 We split bb_3. 914 915 | 1 2 916 | | / 917 | |/ 918 |3.0 919 | |\ (3.0 -> 3.1) = single entry edge 920 |3.1 | <- entry 921 | | | 922 | | | 923 | 4 ^ 924 | | | 925 | |/ 926 | 5 927 928 If the loop is part of the SCoP, we have to redirect the loop latches. 929 930 | 1 2 931 | | / 932 | |/ 933 |3.0 934 | | (3.0 -> 3.1) = entry edge 935 |3.1 <- entry 936 | |\ 937 | | | 938 | 4 ^ 939 | | | 940 | |/ 941 | 5 */ 942 943 if (region->entry->loop_father->header != region->entry 944 || dominated_by_p (CDI_DOMINATORS, 945 loop_latch_edge (region->entry->loop_father)->src, 946 region->exit)) 947 { 948 edge forwarder = split_block_after_labels (region->entry); 949 region->entry = forwarder->dest; 950 } 951 else 952 /* This case is never executed, as the loop headers seem always to have a 953 single edge pointing from outside into the loop. */ 954 gcc_unreachable (); 955 956 gcc_checking_assert (find_single_entry_edge (region)); 957 } 958 959 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */ 960 961 static bool 962 sd_region_without_exit (edge e) 963 { 964 sd_region *r = (sd_region *) e->aux; 965 966 if (r) 967 return r->exit == NULL; 968 else 969 return false; 970 } 971 972 /* Create a single exit edge for REGION. */ 973 974 static void 975 create_single_exit_edge (sd_region *region) 976 { 977 edge e; 978 edge_iterator ei; 979 edge forwarder = NULL; 980 basic_block exit; 981 982 /* We create a forwarder bb (5) for all edges leaving this region 983 (3->5, 4->5). All other edges leading to the same bb, are moved 984 to a new bb (6). If these edges where part of another region (2->5) 985 we update the region->exit pointer, of this region. 986 987 To identify which edge belongs to which region we depend on the e->aux 988 pointer in every edge. It points to the region of the edge or to NULL, 989 if the edge is not part of any region. 990 991 1 2 3 4 1->5 no region, 2->5 region->exit = 5, 992 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL 993 5 <- exit 994 995 changes to 996 997 1 2 3 4 1->6 no region, 2->6 region->exit = 6, 998 | | \/ 3->5 no region, 4->5 no region, 999 | | 5 1000 \| / 5->6 region->exit = 6 1001 6 1002 1003 Now there is only a single exit edge (5->6). */ 1004 exit = region->exit; 1005 region->exit = NULL; 1006 forwarder = make_forwarder_block (exit, &sd_region_without_exit, NULL); 1007 1008 /* Unmark the edges, that are no longer exit edges. */ 1009 FOR_EACH_EDGE (e, ei, forwarder->src->preds) 1010 if (e->aux) 1011 e->aux = NULL; 1012 1013 /* Mark the new exit edge. */ 1014 single_succ_edge (forwarder->src)->aux = region; 1015 1016 /* Update the exit bb of all regions, where exit edges lead to 1017 forwarder->dest. */ 1018 FOR_EACH_EDGE (e, ei, forwarder->dest->preds) 1019 if (e->aux) 1020 ((sd_region *) e->aux)->exit = forwarder->dest; 1021 1022 gcc_checking_assert (find_single_exit_edge (region)); 1023 } 1024 1025 /* Unmark the exit edges of all REGIONS. 1026 See comment in "create_single_exit_edge". */ 1027 1028 static void 1029 unmark_exit_edges (vec<sd_region> regions) 1030 { 1031 int i; 1032 sd_region *s; 1033 edge e; 1034 edge_iterator ei; 1035 1036 FOR_EACH_VEC_ELT (regions, i, s) 1037 FOR_EACH_EDGE (e, ei, s->exit->preds) 1038 e->aux = NULL; 1039 } 1040 1041 1042 /* Mark the exit edges of all REGIONS. 1043 See comment in "create_single_exit_edge". */ 1044 1045 static void 1046 mark_exit_edges (vec<sd_region> regions) 1047 { 1048 int i; 1049 sd_region *s; 1050 edge e; 1051 edge_iterator ei; 1052 1053 FOR_EACH_VEC_ELT (regions, i, s) 1054 FOR_EACH_EDGE (e, ei, s->exit->preds) 1055 if (bb_in_sd_region (e->src, s)) 1056 e->aux = s; 1057 } 1058 1059 /* Create for all scop regions a single entry and a single exit edge. */ 1060 1061 static void 1062 create_sese_edges (vec<sd_region> regions) 1063 { 1064 int i; 1065 sd_region *s; 1066 1067 FOR_EACH_VEC_ELT (regions, i, s) 1068 create_single_entry_edge (s); 1069 1070 mark_exit_edges (regions); 1071 1072 FOR_EACH_VEC_ELT (regions, i, s) 1073 /* Don't handle multiple edges exiting the function. */ 1074 if (!find_single_exit_edge (s) 1075 && s->exit != EXIT_BLOCK_PTR_FOR_FN (cfun)) 1076 create_single_exit_edge (s); 1077 1078 unmark_exit_edges (regions); 1079 1080 calculate_dominance_info (CDI_DOMINATORS); 1081 fix_loop_structure (NULL); 1082 1083 #ifdef ENABLE_CHECKING 1084 verify_loop_structure (); 1085 verify_ssa (false, true); 1086 #endif 1087 } 1088 1089 /* Create graphite SCoPs from an array of scop detection REGIONS. */ 1090 1091 static void 1092 build_graphite_scops (vec<sd_region> regions, 1093 vec<scop_p> *scops) 1094 { 1095 int i; 1096 sd_region *s; 1097 1098 FOR_EACH_VEC_ELT (regions, i, s) 1099 { 1100 edge entry = find_single_entry_edge (s); 1101 edge exit = find_single_exit_edge (s); 1102 scop_p scop; 1103 1104 if (!exit) 1105 continue; 1106 1107 scop = new_scop (new_sese (entry, exit)); 1108 scops->safe_push (scop); 1109 1110 /* Are there overlapping SCoPs? */ 1111 #ifdef ENABLE_CHECKING 1112 { 1113 int j; 1114 sd_region *s2; 1115 1116 FOR_EACH_VEC_ELT (regions, j, s2) 1117 if (s != s2) 1118 gcc_assert (!bb_in_sd_region (s->entry, s2)); 1119 } 1120 #endif 1121 } 1122 } 1123 1124 /* Returns true when BB contains only close phi nodes. */ 1125 1126 static bool 1127 contains_only_close_phi_nodes (basic_block bb) 1128 { 1129 gimple_stmt_iterator gsi; 1130 1131 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1132 if (gimple_code (gsi_stmt (gsi)) != GIMPLE_LABEL) 1133 return false; 1134 1135 return true; 1136 } 1137 1138 /* Print statistics for SCOP to FILE. */ 1139 1140 static void 1141 print_graphite_scop_statistics (FILE* file, scop_p scop) 1142 { 1143 long n_bbs = 0; 1144 long n_loops = 0; 1145 long n_stmts = 0; 1146 long n_conditions = 0; 1147 long n_p_bbs = 0; 1148 long n_p_loops = 0; 1149 long n_p_stmts = 0; 1150 long n_p_conditions = 0; 1151 1152 basic_block bb; 1153 1154 FOR_ALL_BB_FN (bb, cfun) 1155 { 1156 gimple_stmt_iterator psi; 1157 loop_p loop = bb->loop_father; 1158 1159 if (!bb_in_sese_p (bb, SCOP_REGION (scop))) 1160 continue; 1161 1162 n_bbs++; 1163 n_p_bbs += bb->count; 1164 1165 if (EDGE_COUNT (bb->succs) > 1) 1166 { 1167 n_conditions++; 1168 n_p_conditions += bb->count; 1169 } 1170 1171 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) 1172 { 1173 n_stmts++; 1174 n_p_stmts += bb->count; 1175 } 1176 1177 if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop))) 1178 { 1179 n_loops++; 1180 n_p_loops += bb->count; 1181 } 1182 1183 } 1184 1185 fprintf (file, "\nBefore limit_scops SCoP statistics ("); 1186 fprintf (file, "BBS:%ld, ", n_bbs); 1187 fprintf (file, "LOOPS:%ld, ", n_loops); 1188 fprintf (file, "CONDITIONS:%ld, ", n_conditions); 1189 fprintf (file, "STMTS:%ld)\n", n_stmts); 1190 fprintf (file, "\nBefore limit_scops SCoP profiling statistics ("); 1191 fprintf (file, "BBS:%ld, ", n_p_bbs); 1192 fprintf (file, "LOOPS:%ld, ", n_p_loops); 1193 fprintf (file, "CONDITIONS:%ld, ", n_p_conditions); 1194 fprintf (file, "STMTS:%ld)\n", n_p_stmts); 1195 } 1196 1197 /* Print statistics for SCOPS to FILE. */ 1198 1199 static void 1200 print_graphite_statistics (FILE* file, vec<scop_p> scops) 1201 { 1202 int i; 1203 scop_p scop; 1204 1205 FOR_EACH_VEC_ELT (scops, i, scop) 1206 print_graphite_scop_statistics (file, scop); 1207 } 1208 1209 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop. 1210 1211 Example: 1212 1213 for (i | 1214 { | 1215 for (j | SCoP 1 1216 for (k | 1217 } | 1218 1219 * SCoP frontier, as this line is not surrounded by any loop. * 1220 1221 for (l | SCoP 2 1222 1223 This is necessary as scalar evolution and parameter detection need a 1224 outermost loop to initialize parameters correctly. 1225 1226 TODO: FIX scalar evolution and parameter detection to allow more flexible 1227 SCoP frontiers. */ 1228 1229 static void 1230 limit_scops (vec<scop_p> *scops) 1231 { 1232 auto_vec<sd_region, 3> regions; 1233 1234 int i; 1235 scop_p scop; 1236 1237 FOR_EACH_VEC_ELT (*scops, i, scop) 1238 { 1239 int j; 1240 loop_p loop; 1241 sese region = SCOP_REGION (scop); 1242 build_sese_loop_nests (region); 1243 1244 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region), j, loop) 1245 if (!loop_in_sese_p (loop_outer (loop), region) 1246 && single_exit (loop)) 1247 { 1248 sd_region open_scop; 1249 open_scop.entry = loop->header; 1250 open_scop.exit = single_exit (loop)->dest; 1251 1252 /* This is a hack on top of the limit_scops hack. The 1253 limit_scops hack should disappear all together. */ 1254 if (single_succ_p (open_scop.exit) 1255 && contains_only_close_phi_nodes (open_scop.exit)) 1256 open_scop.exit = single_succ_edge (open_scop.exit)->dest; 1257 1258 regions.safe_push (open_scop); 1259 } 1260 } 1261 1262 free_scops (*scops); 1263 scops->create (3); 1264 1265 create_sese_edges (regions); 1266 build_graphite_scops (regions, scops); 1267 } 1268 1269 /* Returns true when P1 and P2 are close phis with the same 1270 argument. */ 1271 1272 static inline bool 1273 same_close_phi_node (gphi *p1, gphi *p2) 1274 { 1275 return operand_equal_p (gimple_phi_arg_def (p1, 0), 1276 gimple_phi_arg_def (p2, 0), 0); 1277 } 1278 1279 /* Remove the close phi node at GSI and replace its rhs with the rhs 1280 of PHI. */ 1281 1282 static void 1283 remove_duplicate_close_phi (gphi *phi, gphi_iterator *gsi) 1284 { 1285 gimple use_stmt; 1286 use_operand_p use_p; 1287 imm_use_iterator imm_iter; 1288 tree res = gimple_phi_result (phi); 1289 tree def = gimple_phi_result (gsi->phi ()); 1290 1291 gcc_assert (same_close_phi_node (phi, gsi->phi ())); 1292 1293 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def) 1294 { 1295 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter) 1296 SET_USE (use_p, res); 1297 1298 update_stmt (use_stmt); 1299 1300 /* It is possible that we just created a duplicate close-phi 1301 for an already-processed containing loop. Check for this 1302 case and clean it up. */ 1303 if (gimple_code (use_stmt) == GIMPLE_PHI 1304 && gimple_phi_num_args (use_stmt) == 1) 1305 make_close_phi_nodes_unique (gimple_bb (use_stmt)); 1306 } 1307 1308 remove_phi_node (gsi, true); 1309 } 1310 1311 /* Removes all the close phi duplicates from BB. */ 1312 1313 static void 1314 make_close_phi_nodes_unique (basic_block bb) 1315 { 1316 gphi_iterator psi; 1317 1318 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) 1319 { 1320 gphi_iterator gsi = psi; 1321 gphi *phi = psi.phi (); 1322 1323 /* At this point, PHI should be a close phi in normal form. */ 1324 gcc_assert (gimple_phi_num_args (phi) == 1); 1325 1326 /* Iterate over the next phis and remove duplicates. */ 1327 gsi_next (&gsi); 1328 while (!gsi_end_p (gsi)) 1329 if (same_close_phi_node (phi, gsi.phi ())) 1330 remove_duplicate_close_phi (phi, &gsi); 1331 else 1332 gsi_next (&gsi); 1333 } 1334 } 1335 1336 /* Transforms LOOP to the canonical loop closed SSA form. */ 1337 1338 static void 1339 canonicalize_loop_closed_ssa (loop_p loop) 1340 { 1341 edge e = single_exit (loop); 1342 basic_block bb; 1343 1344 if (!e || e->flags & EDGE_ABNORMAL) 1345 return; 1346 1347 bb = e->dest; 1348 1349 if (single_pred_p (bb)) 1350 { 1351 e = split_block_after_labels (bb); 1352 make_close_phi_nodes_unique (e->src); 1353 } 1354 else 1355 { 1356 gphi_iterator psi; 1357 basic_block close = split_edge (e); 1358 1359 e = single_succ_edge (close); 1360 1361 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) 1362 { 1363 gphi *phi = psi.phi (); 1364 unsigned i; 1365 1366 for (i = 0; i < gimple_phi_num_args (phi); i++) 1367 if (gimple_phi_arg_edge (phi, i) == e) 1368 { 1369 tree res, arg = gimple_phi_arg_def (phi, i); 1370 use_operand_p use_p; 1371 gphi *close_phi; 1372 1373 if (TREE_CODE (arg) != SSA_NAME) 1374 continue; 1375 1376 close_phi = create_phi_node (NULL_TREE, close); 1377 res = create_new_def_for (arg, close_phi, 1378 gimple_phi_result_ptr (close_phi)); 1379 add_phi_arg (close_phi, arg, 1380 gimple_phi_arg_edge (close_phi, 0), 1381 UNKNOWN_LOCATION); 1382 use_p = gimple_phi_arg_imm_use_ptr (phi, i); 1383 replace_exp (use_p, res); 1384 update_stmt (phi); 1385 } 1386 } 1387 1388 make_close_phi_nodes_unique (close); 1389 } 1390 1391 /* The code above does not properly handle changes in the post dominance 1392 information (yet). */ 1393 free_dominance_info (CDI_POST_DOMINATORS); 1394 } 1395 1396 /* Converts the current loop closed SSA form to a canonical form 1397 expected by the Graphite code generation. 1398 1399 The loop closed SSA form has the following invariant: a variable 1400 defined in a loop that is used outside the loop appears only in the 1401 phi nodes in the destination of the loop exit. These phi nodes are 1402 called close phi nodes. 1403 1404 The canonical loop closed SSA form contains the extra invariants: 1405 1406 - when the loop contains only one exit, the close phi nodes contain 1407 only one argument. That implies that the basic block that contains 1408 the close phi nodes has only one predecessor, that is a basic block 1409 in the loop. 1410 1411 - the basic block containing the close phi nodes does not contain 1412 other statements. 1413 1414 - there exist only one phi node per definition in the loop. 1415 */ 1416 1417 static void 1418 canonicalize_loop_closed_ssa_form (void) 1419 { 1420 loop_p loop; 1421 1422 #ifdef ENABLE_CHECKING 1423 verify_loop_closed_ssa (true); 1424 #endif 1425 1426 FOR_EACH_LOOP (loop, 0) 1427 canonicalize_loop_closed_ssa (loop); 1428 1429 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); 1430 update_ssa (TODO_update_ssa); 1431 1432 #ifdef ENABLE_CHECKING 1433 verify_loop_closed_ssa (true); 1434 #endif 1435 } 1436 1437 /* Find Static Control Parts (SCoP) in the current function and pushes 1438 them to SCOPS. */ 1439 1440 void 1441 build_scops (vec<scop_p> *scops) 1442 { 1443 struct loop *loop = current_loops->tree_root; 1444 auto_vec<sd_region, 3> regions; 1445 1446 canonicalize_loop_closed_ssa_form (); 1447 build_scops_1 (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)), 1448 ENTRY_BLOCK_PTR_FOR_FN (cfun)->loop_father, 1449 ®ions, loop); 1450 create_sese_edges (regions); 1451 build_graphite_scops (regions, scops); 1452 1453 if (dump_file && (dump_flags & TDF_DETAILS)) 1454 print_graphite_statistics (dump_file, *scops); 1455 1456 limit_scops (scops); 1457 regions.release (); 1458 1459 if (dump_file && (dump_flags & TDF_DETAILS)) 1460 fprintf (dump_file, "\nnumber of SCoPs: %d\n", 1461 scops ? scops->length () : 0); 1462 } 1463 1464 /* Pretty print to FILE all the SCoPs in DOT format and mark them with 1465 different colors. If there are not enough colors, paint the 1466 remaining SCoPs in gray. 1467 1468 Special nodes: 1469 - "*" after the node number denotes the entry of a SCoP, 1470 - "#" after the node number denotes the exit of a SCoP, 1471 - "()" around the node number denotes the entry or the 1472 exit nodes of the SCOP. These are not part of SCoP. */ 1473 1474 static void 1475 dot_all_scops_1 (FILE *file, vec<scop_p> scops) 1476 { 1477 basic_block bb; 1478 edge e; 1479 edge_iterator ei; 1480 scop_p scop; 1481 const char* color; 1482 int i; 1483 1484 /* Disable debugging while printing graph. */ 1485 int tmp_dump_flags = dump_flags; 1486 dump_flags = 0; 1487 1488 fprintf (file, "digraph all {\n"); 1489 1490 FOR_ALL_BB_FN (bb, cfun) 1491 { 1492 int part_of_scop = false; 1493 1494 /* Use HTML for every bb label. So we are able to print bbs 1495 which are part of two different SCoPs, with two different 1496 background colors. */ 1497 fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ", 1498 bb->index); 1499 fprintf (file, "CELLSPACING=\"0\">\n"); 1500 1501 /* Select color for SCoP. */ 1502 FOR_EACH_VEC_ELT (scops, i, scop) 1503 { 1504 sese region = SCOP_REGION (scop); 1505 if (bb_in_sese_p (bb, region) 1506 || (SESE_EXIT_BB (region) == bb) 1507 || (SESE_ENTRY_BB (region) == bb)) 1508 { 1509 switch (i % 17) 1510 { 1511 case 0: /* red */ 1512 color = "#e41a1c"; 1513 break; 1514 case 1: /* blue */ 1515 color = "#377eb8"; 1516 break; 1517 case 2: /* green */ 1518 color = "#4daf4a"; 1519 break; 1520 case 3: /* purple */ 1521 color = "#984ea3"; 1522 break; 1523 case 4: /* orange */ 1524 color = "#ff7f00"; 1525 break; 1526 case 5: /* yellow */ 1527 color = "#ffff33"; 1528 break; 1529 case 6: /* brown */ 1530 color = "#a65628"; 1531 break; 1532 case 7: /* rose */ 1533 color = "#f781bf"; 1534 break; 1535 case 8: 1536 color = "#8dd3c7"; 1537 break; 1538 case 9: 1539 color = "#ffffb3"; 1540 break; 1541 case 10: 1542 color = "#bebada"; 1543 break; 1544 case 11: 1545 color = "#fb8072"; 1546 break; 1547 case 12: 1548 color = "#80b1d3"; 1549 break; 1550 case 13: 1551 color = "#fdb462"; 1552 break; 1553 case 14: 1554 color = "#b3de69"; 1555 break; 1556 case 15: 1557 color = "#fccde5"; 1558 break; 1559 case 16: 1560 color = "#bc80bd"; 1561 break; 1562 default: /* gray */ 1563 color = "#999999"; 1564 } 1565 1566 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color); 1567 1568 if (!bb_in_sese_p (bb, region)) 1569 fprintf (file, " ("); 1570 1571 if (bb == SESE_ENTRY_BB (region) 1572 && bb == SESE_EXIT_BB (region)) 1573 fprintf (file, " %d*# ", bb->index); 1574 else if (bb == SESE_ENTRY_BB (region)) 1575 fprintf (file, " %d* ", bb->index); 1576 else if (bb == SESE_EXIT_BB (region)) 1577 fprintf (file, " %d# ", bb->index); 1578 else 1579 fprintf (file, " %d ", bb->index); 1580 1581 if (!bb_in_sese_p (bb,region)) 1582 fprintf (file, ")"); 1583 1584 fprintf (file, "</TD></TR>\n"); 1585 part_of_scop = true; 1586 } 1587 } 1588 1589 if (!part_of_scop) 1590 { 1591 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">"); 1592 fprintf (file, " %d </TD></TR>\n", bb->index); 1593 } 1594 fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n"); 1595 } 1596 1597 FOR_ALL_BB_FN (bb, cfun) 1598 { 1599 FOR_EACH_EDGE (e, ei, bb->succs) 1600 fprintf (file, "%d -> %d;\n", bb->index, e->dest->index); 1601 } 1602 1603 fputs ("}\n\n", file); 1604 1605 /* Enable debugging again. */ 1606 dump_flags = tmp_dump_flags; 1607 } 1608 1609 /* Display all SCoPs using dotty. */ 1610 1611 DEBUG_FUNCTION void 1612 dot_all_scops (vec<scop_p> scops) 1613 { 1614 /* When debugging, enable the following code. This cannot be used 1615 in production compilers because it calls "system". */ 1616 #if 0 1617 int x; 1618 FILE *stream = fopen ("/tmp/allscops.dot", "w"); 1619 gcc_assert (stream); 1620 1621 dot_all_scops_1 (stream, scops); 1622 fclose (stream); 1623 1624 x = system ("dotty /tmp/allscops.dot &"); 1625 #else 1626 dot_all_scops_1 (stderr, scops); 1627 #endif 1628 } 1629 1630 /* Display all SCoPs using dotty. */ 1631 1632 DEBUG_FUNCTION void 1633 dot_scop (scop_p scop) 1634 { 1635 auto_vec<scop_p, 1> scops; 1636 1637 if (scop) 1638 scops.safe_push (scop); 1639 1640 /* When debugging, enable the following code. This cannot be used 1641 in production compilers because it calls "system". */ 1642 #if 0 1643 { 1644 int x; 1645 FILE *stream = fopen ("/tmp/allscops.dot", "w"); 1646 gcc_assert (stream); 1647 1648 dot_all_scops_1 (stream, scops); 1649 fclose (stream); 1650 x = system ("dotty /tmp/allscops.dot &"); 1651 } 1652 #else 1653 dot_all_scops_1 (stderr, scops); 1654 #endif 1655 } 1656 1657 #endif 1658