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