1 /* Hooks for cfg representation specific functions. 2 Copyright (C) 2003, 2004, 2005, 2007, 2008, 2010 3 Free Software Foundation, Inc. 4 Contributed by Sebastian Pop <s.pop@laposte.net> 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 "tm.h" 26 #include "tree.h" 27 #include "rtl.h" 28 #include "basic-block.h" 29 #include "tree-flow.h" 30 #include "timevar.h" 31 #include "diagnostic-core.h" 32 #include "cfgloop.h" 33 34 /* A pointer to one of the hooks containers. */ 35 static struct cfg_hooks *cfg_hooks; 36 37 /* Initialization of functions specific to the rtl IR. */ 38 void 39 rtl_register_cfg_hooks (void) 40 { 41 cfg_hooks = &rtl_cfg_hooks; 42 } 43 44 /* Initialization of functions specific to the rtl IR. */ 45 void 46 cfg_layout_rtl_register_cfg_hooks (void) 47 { 48 cfg_hooks = &cfg_layout_rtl_cfg_hooks; 49 } 50 51 /* Initialization of functions specific to the tree IR. */ 52 53 void 54 gimple_register_cfg_hooks (void) 55 { 56 cfg_hooks = &gimple_cfg_hooks; 57 } 58 59 struct cfg_hooks 60 get_cfg_hooks (void) 61 { 62 return *cfg_hooks; 63 } 64 65 void 66 set_cfg_hooks (struct cfg_hooks new_cfg_hooks) 67 { 68 *cfg_hooks = new_cfg_hooks; 69 } 70 71 /* Returns current ir type. */ 72 73 enum ir_type 74 current_ir_type (void) 75 { 76 if (cfg_hooks == &gimple_cfg_hooks) 77 return IR_GIMPLE; 78 else if (cfg_hooks == &rtl_cfg_hooks) 79 return IR_RTL_CFGRTL; 80 else if (cfg_hooks == &cfg_layout_rtl_cfg_hooks) 81 return IR_RTL_CFGLAYOUT; 82 else 83 gcc_unreachable (); 84 } 85 86 /* Verify the CFG consistency. 87 88 Currently it does following: checks edge and basic block list correctness 89 and calls into IL dependent checking then. */ 90 91 DEBUG_FUNCTION void 92 verify_flow_info (void) 93 { 94 size_t *edge_checksum; 95 int err = 0; 96 basic_block bb, last_bb_seen; 97 basic_block *last_visited; 98 99 timevar_push (TV_CFG_VERIFY); 100 last_visited = XCNEWVEC (basic_block, last_basic_block); 101 edge_checksum = XCNEWVEC (size_t, last_basic_block); 102 103 /* Check bb chain & numbers. */ 104 last_bb_seen = ENTRY_BLOCK_PTR; 105 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb) 106 { 107 if (bb != EXIT_BLOCK_PTR 108 && bb != BASIC_BLOCK (bb->index)) 109 { 110 error ("bb %d on wrong place", bb->index); 111 err = 1; 112 } 113 114 if (bb->prev_bb != last_bb_seen) 115 { 116 error ("prev_bb of %d should be %d, not %d", 117 bb->index, last_bb_seen->index, bb->prev_bb->index); 118 err = 1; 119 } 120 121 last_bb_seen = bb; 122 } 123 124 /* Now check the basic blocks (boundaries etc.) */ 125 FOR_EACH_BB_REVERSE (bb) 126 { 127 int n_fallthru = 0; 128 edge e; 129 edge_iterator ei; 130 131 if (bb->loop_father != NULL && current_loops == NULL) 132 { 133 error ("verify_flow_info: Block %i has loop_father, but there are no loops", 134 bb->index); 135 err = 1; 136 } 137 if (bb->loop_father == NULL && current_loops != NULL) 138 { 139 error ("verify_flow_info: Block %i lacks loop_father", bb->index); 140 err = 1; 141 } 142 143 if (bb->count < 0) 144 { 145 error ("verify_flow_info: Wrong count of block %i %i", 146 bb->index, (int)bb->count); 147 err = 1; 148 } 149 if (bb->frequency < 0) 150 { 151 error ("verify_flow_info: Wrong frequency of block %i %i", 152 bb->index, bb->frequency); 153 err = 1; 154 } 155 FOR_EACH_EDGE (e, ei, bb->succs) 156 { 157 if (last_visited [e->dest->index] == bb) 158 { 159 error ("verify_flow_info: Duplicate edge %i->%i", 160 e->src->index, e->dest->index); 161 err = 1; 162 } 163 if (e->probability < 0 || e->probability > REG_BR_PROB_BASE) 164 { 165 error ("verify_flow_info: Wrong probability of edge %i->%i %i", 166 e->src->index, e->dest->index, e->probability); 167 err = 1; 168 } 169 if (e->count < 0) 170 { 171 error ("verify_flow_info: Wrong count of edge %i->%i %i", 172 e->src->index, e->dest->index, (int)e->count); 173 err = 1; 174 } 175 176 last_visited [e->dest->index] = bb; 177 178 if (e->flags & EDGE_FALLTHRU) 179 n_fallthru++; 180 181 if (e->src != bb) 182 { 183 error ("verify_flow_info: Basic block %d succ edge is corrupted", 184 bb->index); 185 fprintf (stderr, "Predecessor: "); 186 dump_edge_info (stderr, e, 0); 187 fprintf (stderr, "\nSuccessor: "); 188 dump_edge_info (stderr, e, 1); 189 fprintf (stderr, "\n"); 190 err = 1; 191 } 192 193 edge_checksum[e->dest->index] += (size_t) e; 194 } 195 if (n_fallthru > 1) 196 { 197 error ("wrong amount of branch edges after unconditional jump %i", bb->index); 198 err = 1; 199 } 200 201 FOR_EACH_EDGE (e, ei, bb->preds) 202 { 203 if (e->dest != bb) 204 { 205 error ("basic block %d pred edge is corrupted", bb->index); 206 fputs ("Predecessor: ", stderr); 207 dump_edge_info (stderr, e, 0); 208 fputs ("\nSuccessor: ", stderr); 209 dump_edge_info (stderr, e, 1); 210 fputc ('\n', stderr); 211 err = 1; 212 } 213 214 if (ei.index != e->dest_idx) 215 { 216 error ("basic block %d pred edge is corrupted", bb->index); 217 error ("its dest_idx should be %d, not %d", 218 ei.index, e->dest_idx); 219 fputs ("Predecessor: ", stderr); 220 dump_edge_info (stderr, e, 0); 221 fputs ("\nSuccessor: ", stderr); 222 dump_edge_info (stderr, e, 1); 223 fputc ('\n', stderr); 224 err = 1; 225 } 226 227 edge_checksum[e->dest->index] -= (size_t) e; 228 } 229 } 230 231 /* Complete edge checksumming for ENTRY and EXIT. */ 232 { 233 edge e; 234 edge_iterator ei; 235 236 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) 237 edge_checksum[e->dest->index] += (size_t) e; 238 239 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) 240 edge_checksum[e->dest->index] -= (size_t) e; 241 } 242 243 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 244 if (edge_checksum[bb->index]) 245 { 246 error ("basic block %i edge lists are corrupted", bb->index); 247 err = 1; 248 } 249 250 last_bb_seen = ENTRY_BLOCK_PTR; 251 252 /* Clean up. */ 253 free (last_visited); 254 free (edge_checksum); 255 256 if (cfg_hooks->verify_flow_info) 257 err |= cfg_hooks->verify_flow_info (); 258 if (err) 259 internal_error ("verify_flow_info failed"); 260 timevar_pop (TV_CFG_VERIFY); 261 } 262 263 /* Print out one basic block. This function takes care of the purely 264 graph related information. The cfg hook for the active representation 265 should dump representation-specific information. */ 266 267 void 268 dump_bb (basic_block bb, FILE *outf, int indent) 269 { 270 edge e; 271 edge_iterator ei; 272 char *s_indent; 273 274 s_indent = (char *) alloca ((size_t) indent + 1); 275 memset (s_indent, ' ', (size_t) indent); 276 s_indent[indent] = '\0'; 277 278 fprintf (outf, ";;%s basic block %d, loop depth %d, count ", 279 s_indent, bb->index, bb->loop_depth); 280 fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count); 281 putc ('\n', outf); 282 283 fprintf (outf, ";;%s prev block ", s_indent); 284 if (bb->prev_bb) 285 fprintf (outf, "%d, ", bb->prev_bb->index); 286 else 287 fprintf (outf, "(nil), "); 288 fprintf (outf, "next block "); 289 if (bb->next_bb) 290 fprintf (outf, "%d", bb->next_bb->index); 291 else 292 fprintf (outf, "(nil)"); 293 putc ('\n', outf); 294 295 fprintf (outf, ";;%s pred: ", s_indent); 296 FOR_EACH_EDGE (e, ei, bb->preds) 297 dump_edge_info (outf, e, 0); 298 putc ('\n', outf); 299 300 fprintf (outf, ";;%s succ: ", s_indent); 301 FOR_EACH_EDGE (e, ei, bb->succs) 302 dump_edge_info (outf, e, 1); 303 putc ('\n', outf); 304 305 if (cfg_hooks->dump_bb) 306 cfg_hooks->dump_bb (bb, outf, indent, 0); 307 } 308 309 /* Redirect edge E to the given basic block DEST and update underlying program 310 representation. Returns edge representing redirected branch (that may not 311 be equivalent to E in the case of duplicate edges being removed) or NULL 312 if edge is not easily redirectable for whatever reason. */ 313 314 edge 315 redirect_edge_and_branch (edge e, basic_block dest) 316 { 317 edge ret; 318 319 if (!cfg_hooks->redirect_edge_and_branch) 320 internal_error ("%s does not support redirect_edge_and_branch", 321 cfg_hooks->name); 322 323 ret = cfg_hooks->redirect_edge_and_branch (e, dest); 324 325 /* If RET != E, then either the redirection failed, or the edge E 326 was removed since RET already lead to the same destination. */ 327 if (current_loops != NULL && ret == e) 328 rescan_loop_exit (e, false, false); 329 330 return ret; 331 } 332 333 /* Returns true if it is possible to remove the edge E by redirecting it 334 to the destination of the other edge going from its source. */ 335 336 bool 337 can_remove_branch_p (const_edge e) 338 { 339 if (!cfg_hooks->can_remove_branch_p) 340 internal_error ("%s does not support can_remove_branch_p", 341 cfg_hooks->name); 342 343 if (EDGE_COUNT (e->src->succs) != 2) 344 return false; 345 346 return cfg_hooks->can_remove_branch_p (e); 347 } 348 349 /* Removes E, by redirecting it to the destination of the other edge going 350 from its source. Can_remove_branch_p must be true for E, hence this 351 operation cannot fail. */ 352 353 void 354 remove_branch (edge e) 355 { 356 edge other; 357 basic_block src = e->src; 358 int irr; 359 360 gcc_assert (EDGE_COUNT (e->src->succs) == 2); 361 362 other = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e); 363 irr = other->flags & EDGE_IRREDUCIBLE_LOOP; 364 365 e = redirect_edge_and_branch (e, other->dest); 366 gcc_assert (e != NULL); 367 368 e->flags &= ~EDGE_IRREDUCIBLE_LOOP; 369 e->flags |= irr; 370 } 371 372 /* Removes edge E from cfg. Unlike remove_branch, it does not update IL. */ 373 374 void 375 remove_edge (edge e) 376 { 377 if (current_loops != NULL) 378 rescan_loop_exit (e, false, true); 379 380 remove_edge_raw (e); 381 } 382 383 /* Redirect the edge E to basic block DEST even if it requires creating 384 of a new basic block; then it returns the newly created basic block. 385 Aborts when redirection is impossible. */ 386 387 basic_block 388 redirect_edge_and_branch_force (edge e, basic_block dest) 389 { 390 basic_block ret, src = e->src; 391 392 if (!cfg_hooks->redirect_edge_and_branch_force) 393 internal_error ("%s does not support redirect_edge_and_branch_force", 394 cfg_hooks->name); 395 396 if (current_loops != NULL) 397 rescan_loop_exit (e, false, true); 398 399 ret = cfg_hooks->redirect_edge_and_branch_force (e, dest); 400 401 if (ret != NULL && dom_info_available_p (CDI_DOMINATORS)) 402 set_immediate_dominator (CDI_DOMINATORS, ret, src); 403 404 if (current_loops != NULL) 405 { 406 if (ret != NULL) 407 { 408 struct loop *loop 409 = find_common_loop (single_pred (ret)->loop_father, 410 single_succ (ret)->loop_father); 411 add_bb_to_loop (ret, loop); 412 } 413 else if (find_edge (src, dest) == e) 414 rescan_loop_exit (e, true, false); 415 } 416 417 return ret; 418 } 419 420 /* Splits basic block BB after the specified instruction I (but at least after 421 the labels). If I is NULL, splits just after labels. The newly created edge 422 is returned. The new basic block is created just after the old one. */ 423 424 edge 425 split_block (basic_block bb, void *i) 426 { 427 basic_block new_bb; 428 edge res; 429 430 if (!cfg_hooks->split_block) 431 internal_error ("%s does not support split_block", cfg_hooks->name); 432 433 new_bb = cfg_hooks->split_block (bb, i); 434 if (!new_bb) 435 return NULL; 436 437 new_bb->count = bb->count; 438 new_bb->frequency = bb->frequency; 439 new_bb->loop_depth = bb->loop_depth; 440 new_bb->discriminator = bb->discriminator; 441 442 if (dom_info_available_p (CDI_DOMINATORS)) 443 { 444 redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb); 445 set_immediate_dominator (CDI_DOMINATORS, new_bb, bb); 446 } 447 448 if (current_loops != NULL) 449 { 450 add_bb_to_loop (new_bb, bb->loop_father); 451 if (bb->loop_father->latch == bb) 452 bb->loop_father->latch = new_bb; 453 } 454 455 res = make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU); 456 457 if (bb->flags & BB_IRREDUCIBLE_LOOP) 458 { 459 new_bb->flags |= BB_IRREDUCIBLE_LOOP; 460 res->flags |= EDGE_IRREDUCIBLE_LOOP; 461 } 462 463 return res; 464 } 465 466 /* Splits block BB just after labels. The newly created edge is returned. */ 467 468 edge 469 split_block_after_labels (basic_block bb) 470 { 471 return split_block (bb, NULL); 472 } 473 474 /* Moves block BB immediately after block AFTER. Returns false if the 475 movement was impossible. */ 476 477 bool 478 move_block_after (basic_block bb, basic_block after) 479 { 480 bool ret; 481 482 if (!cfg_hooks->move_block_after) 483 internal_error ("%s does not support move_block_after", cfg_hooks->name); 484 485 ret = cfg_hooks->move_block_after (bb, after); 486 487 return ret; 488 } 489 490 /* Deletes the basic block BB. */ 491 492 void 493 delete_basic_block (basic_block bb) 494 { 495 if (!cfg_hooks->delete_basic_block) 496 internal_error ("%s does not support delete_basic_block", cfg_hooks->name); 497 498 cfg_hooks->delete_basic_block (bb); 499 500 if (current_loops != NULL) 501 { 502 struct loop *loop = bb->loop_father; 503 504 /* If we remove the header or the latch of a loop, mark the loop for 505 removal by setting its header and latch to NULL. */ 506 if (loop->latch == bb 507 || loop->header == bb) 508 { 509 loop->header = NULL; 510 loop->latch = NULL; 511 } 512 513 remove_bb_from_loops (bb); 514 } 515 516 /* Remove the edges into and out of this block. Note that there may 517 indeed be edges in, if we are removing an unreachable loop. */ 518 while (EDGE_COUNT (bb->preds) != 0) 519 remove_edge (EDGE_PRED (bb, 0)); 520 while (EDGE_COUNT (bb->succs) != 0) 521 remove_edge (EDGE_SUCC (bb, 0)); 522 523 if (dom_info_available_p (CDI_DOMINATORS)) 524 delete_from_dominance_info (CDI_DOMINATORS, bb); 525 if (dom_info_available_p (CDI_POST_DOMINATORS)) 526 delete_from_dominance_info (CDI_POST_DOMINATORS, bb); 527 528 /* Remove the basic block from the array. */ 529 expunge_block (bb); 530 } 531 532 /* Splits edge E and returns the newly created basic block. */ 533 534 basic_block 535 split_edge (edge e) 536 { 537 basic_block ret; 538 gcov_type count = e->count; 539 int freq = EDGE_FREQUENCY (e); 540 edge f; 541 bool irr = (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0; 542 struct loop *loop; 543 basic_block src = e->src, dest = e->dest; 544 545 if (!cfg_hooks->split_edge) 546 internal_error ("%s does not support split_edge", cfg_hooks->name); 547 548 if (current_loops != NULL) 549 rescan_loop_exit (e, false, true); 550 551 ret = cfg_hooks->split_edge (e); 552 ret->count = count; 553 ret->frequency = freq; 554 single_succ_edge (ret)->probability = REG_BR_PROB_BASE; 555 single_succ_edge (ret)->count = count; 556 557 if (irr) 558 { 559 ret->flags |= BB_IRREDUCIBLE_LOOP; 560 single_pred_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP; 561 single_succ_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP; 562 } 563 564 if (dom_info_available_p (CDI_DOMINATORS)) 565 set_immediate_dominator (CDI_DOMINATORS, ret, single_pred (ret)); 566 567 if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY) 568 { 569 /* There are two cases: 570 571 If the immediate dominator of e->dest is not e->src, it 572 remains unchanged. 573 574 If immediate dominator of e->dest is e->src, it may become 575 ret, provided that all other predecessors of e->dest are 576 dominated by e->dest. */ 577 578 if (get_immediate_dominator (CDI_DOMINATORS, single_succ (ret)) 579 == single_pred (ret)) 580 { 581 edge_iterator ei; 582 FOR_EACH_EDGE (f, ei, single_succ (ret)->preds) 583 { 584 if (f == single_succ_edge (ret)) 585 continue; 586 587 if (!dominated_by_p (CDI_DOMINATORS, f->src, 588 single_succ (ret))) 589 break; 590 } 591 592 if (!f) 593 set_immediate_dominator (CDI_DOMINATORS, single_succ (ret), ret); 594 } 595 } 596 597 if (current_loops != NULL) 598 { 599 loop = find_common_loop (src->loop_father, dest->loop_father); 600 add_bb_to_loop (ret, loop); 601 602 if (loop->latch == src) 603 loop->latch = ret; 604 } 605 606 return ret; 607 } 608 609 /* Creates a new basic block just after the basic block AFTER. 610 HEAD and END are the first and the last statement belonging 611 to the block. If both are NULL, an empty block is created. */ 612 613 basic_block 614 create_basic_block (void *head, void *end, basic_block after) 615 { 616 basic_block ret; 617 618 if (!cfg_hooks->create_basic_block) 619 internal_error ("%s does not support create_basic_block", cfg_hooks->name); 620 621 ret = cfg_hooks->create_basic_block (head, end, after); 622 623 if (dom_info_available_p (CDI_DOMINATORS)) 624 add_to_dominance_info (CDI_DOMINATORS, ret); 625 if (dom_info_available_p (CDI_POST_DOMINATORS)) 626 add_to_dominance_info (CDI_POST_DOMINATORS, ret); 627 628 return ret; 629 } 630 631 /* Creates an empty basic block just after basic block AFTER. */ 632 633 basic_block 634 create_empty_bb (basic_block after) 635 { 636 return create_basic_block (NULL, NULL, after); 637 } 638 639 /* Checks whether we may merge blocks BB1 and BB2. */ 640 641 bool 642 can_merge_blocks_p (basic_block bb1, basic_block bb2) 643 { 644 bool ret; 645 646 if (!cfg_hooks->can_merge_blocks_p) 647 internal_error ("%s does not support can_merge_blocks_p", cfg_hooks->name); 648 649 ret = cfg_hooks->can_merge_blocks_p (bb1, bb2); 650 651 return ret; 652 } 653 654 void 655 predict_edge (edge e, enum br_predictor predictor, int probability) 656 { 657 if (!cfg_hooks->predict_edge) 658 internal_error ("%s does not support predict_edge", cfg_hooks->name); 659 660 cfg_hooks->predict_edge (e, predictor, probability); 661 } 662 663 bool 664 predicted_by_p (const_basic_block bb, enum br_predictor predictor) 665 { 666 if (!cfg_hooks->predict_edge) 667 internal_error ("%s does not support predicted_by_p", cfg_hooks->name); 668 669 return cfg_hooks->predicted_by_p (bb, predictor); 670 } 671 672 /* Merges basic block B into basic block A. */ 673 674 void 675 merge_blocks (basic_block a, basic_block b) 676 { 677 edge e; 678 edge_iterator ei; 679 680 if (!cfg_hooks->merge_blocks) 681 internal_error ("%s does not support merge_blocks", cfg_hooks->name); 682 683 cfg_hooks->merge_blocks (a, b); 684 685 if (current_loops != NULL) 686 remove_bb_from_loops (b); 687 688 /* Normally there should only be one successor of A and that is B, but 689 partway though the merge of blocks for conditional_execution we'll 690 be merging a TEST block with THEN and ELSE successors. Free the 691 whole lot of them and hope the caller knows what they're doing. */ 692 693 while (EDGE_COUNT (a->succs) != 0) 694 remove_edge (EDGE_SUCC (a, 0)); 695 696 /* Adjust the edges out of B for the new owner. */ 697 FOR_EACH_EDGE (e, ei, b->succs) 698 { 699 e->src = a; 700 if (current_loops != NULL) 701 rescan_loop_exit (e, true, false); 702 } 703 a->succs = b->succs; 704 a->flags |= b->flags; 705 706 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */ 707 b->preds = b->succs = NULL; 708 709 if (dom_info_available_p (CDI_DOMINATORS)) 710 redirect_immediate_dominators (CDI_DOMINATORS, b, a); 711 712 if (dom_info_available_p (CDI_DOMINATORS)) 713 delete_from_dominance_info (CDI_DOMINATORS, b); 714 if (dom_info_available_p (CDI_POST_DOMINATORS)) 715 delete_from_dominance_info (CDI_POST_DOMINATORS, b); 716 717 expunge_block (b); 718 } 719 720 /* Split BB into entry part and the rest (the rest is the newly created block). 721 Redirect those edges for that REDIRECT_EDGE_P returns true to the entry 722 part. Returns the edge connecting the entry part to the rest. */ 723 724 edge 725 make_forwarder_block (basic_block bb, bool (*redirect_edge_p) (edge), 726 void (*new_bb_cbk) (basic_block)) 727 { 728 edge e, fallthru; 729 edge_iterator ei; 730 basic_block dummy, jump; 731 struct loop *loop, *ploop, *cloop; 732 733 if (!cfg_hooks->make_forwarder_block) 734 internal_error ("%s does not support make_forwarder_block", 735 cfg_hooks->name); 736 737 fallthru = split_block_after_labels (bb); 738 dummy = fallthru->src; 739 bb = fallthru->dest; 740 741 /* Redirect back edges we want to keep. */ 742 for (ei = ei_start (dummy->preds); (e = ei_safe_edge (ei)); ) 743 { 744 basic_block e_src; 745 746 if (redirect_edge_p (e)) 747 { 748 ei_next (&ei); 749 continue; 750 } 751 752 dummy->frequency -= EDGE_FREQUENCY (e); 753 dummy->count -= e->count; 754 if (dummy->frequency < 0) 755 dummy->frequency = 0; 756 if (dummy->count < 0) 757 dummy->count = 0; 758 fallthru->count -= e->count; 759 if (fallthru->count < 0) 760 fallthru->count = 0; 761 762 e_src = e->src; 763 jump = redirect_edge_and_branch_force (e, bb); 764 if (jump != NULL) 765 { 766 /* If we redirected the loop latch edge, the JUMP block now acts like 767 the new latch of the loop. */ 768 if (current_loops != NULL 769 && dummy->loop_father != NULL 770 && dummy->loop_father->header == dummy 771 && dummy->loop_father->latch == e_src) 772 dummy->loop_father->latch = jump; 773 774 if (new_bb_cbk != NULL) 775 new_bb_cbk (jump); 776 } 777 } 778 779 if (dom_info_available_p (CDI_DOMINATORS)) 780 { 781 VEC (basic_block, heap) *doms_to_fix = VEC_alloc (basic_block, heap, 2); 782 VEC_quick_push (basic_block, doms_to_fix, dummy); 783 VEC_quick_push (basic_block, doms_to_fix, bb); 784 iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, false); 785 VEC_free (basic_block, heap, doms_to_fix); 786 } 787 788 if (current_loops != NULL) 789 { 790 /* If we do not split a loop header, then both blocks belong to the 791 same loop. In case we split loop header and do not redirect the 792 latch edge to DUMMY, then DUMMY belongs to the outer loop, and 793 BB becomes the new header. If latch is not recorded for the loop, 794 we leave this updating on the caller (this may only happen during 795 loop analysis). */ 796 loop = dummy->loop_father; 797 if (loop->header == dummy 798 && loop->latch != NULL 799 && find_edge (loop->latch, dummy) == NULL) 800 { 801 remove_bb_from_loops (dummy); 802 loop->header = bb; 803 804 cloop = loop; 805 FOR_EACH_EDGE (e, ei, dummy->preds) 806 { 807 cloop = find_common_loop (cloop, e->src->loop_father); 808 } 809 add_bb_to_loop (dummy, cloop); 810 } 811 812 /* In case we split loop latch, update it. */ 813 for (ploop = loop; ploop; ploop = loop_outer (ploop)) 814 if (ploop->latch == dummy) 815 ploop->latch = bb; 816 } 817 818 cfg_hooks->make_forwarder_block (fallthru); 819 820 return fallthru; 821 } 822 823 /* Try to make the edge fallthru. */ 824 825 void 826 tidy_fallthru_edge (edge e) 827 { 828 if (cfg_hooks->tidy_fallthru_edge) 829 cfg_hooks->tidy_fallthru_edge (e); 830 } 831 832 /* Fix up edges that now fall through, or rather should now fall through 833 but previously required a jump around now deleted blocks. Simplify 834 the search by only examining blocks numerically adjacent, since this 835 is how they were created. 836 837 ??? This routine is currently RTL specific. */ 838 839 void 840 tidy_fallthru_edges (void) 841 { 842 basic_block b, c; 843 844 if (!cfg_hooks->tidy_fallthru_edge) 845 return; 846 847 if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR) 848 return; 849 850 FOR_BB_BETWEEN (b, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, next_bb) 851 { 852 edge s; 853 854 c = b->next_bb; 855 856 /* We care about simple conditional or unconditional jumps with 857 a single successor. 858 859 If we had a conditional branch to the next instruction when 860 CFG was built, then there will only be one out edge for the 861 block which ended with the conditional branch (since we do 862 not create duplicate edges). 863 864 Furthermore, the edge will be marked as a fallthru because we 865 merge the flags for the duplicate edges. So we do not want to 866 check that the edge is not a FALLTHRU edge. */ 867 868 if (single_succ_p (b)) 869 { 870 s = single_succ_edge (b); 871 if (! (s->flags & EDGE_COMPLEX) 872 && s->dest == c 873 && !find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX)) 874 tidy_fallthru_edge (s); 875 } 876 } 877 } 878 879 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction 880 (and possibly create new basic block) to make edge non-fallthru. 881 Return newly created BB or NULL if none. */ 882 883 basic_block 884 force_nonfallthru (edge e) 885 { 886 basic_block ret, src = e->src; 887 888 if (!cfg_hooks->force_nonfallthru) 889 internal_error ("%s does not support force_nonfallthru", 890 cfg_hooks->name); 891 892 ret = cfg_hooks->force_nonfallthru (e); 893 if (ret != NULL) 894 { 895 if (dom_info_available_p (CDI_DOMINATORS)) 896 set_immediate_dominator (CDI_DOMINATORS, ret, src); 897 898 if (current_loops != NULL) 899 { 900 struct loop *loop 901 = find_common_loop (single_pred (ret)->loop_father, 902 single_succ (ret)->loop_father); 903 rescan_loop_exit (e, false, true); 904 add_bb_to_loop (ret, loop); 905 } 906 } 907 908 return ret; 909 } 910 911 /* Returns true if we can duplicate basic block BB. */ 912 913 bool 914 can_duplicate_block_p (const_basic_block bb) 915 { 916 if (!cfg_hooks->can_duplicate_block_p) 917 internal_error ("%s does not support can_duplicate_block_p", 918 cfg_hooks->name); 919 920 if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR) 921 return false; 922 923 return cfg_hooks->can_duplicate_block_p (bb); 924 } 925 926 /* Duplicates basic block BB and redirects edge E to it. Returns the 927 new basic block. The new basic block is placed after the basic block 928 AFTER. */ 929 930 basic_block 931 duplicate_block (basic_block bb, edge e, basic_block after) 932 { 933 edge s, n; 934 basic_block new_bb; 935 gcov_type new_count = e ? e->count : 0; 936 edge_iterator ei; 937 938 if (!cfg_hooks->duplicate_block) 939 internal_error ("%s does not support duplicate_block", 940 cfg_hooks->name); 941 942 if (bb->count < new_count) 943 new_count = bb->count; 944 945 gcc_checking_assert (can_duplicate_block_p (bb)); 946 947 new_bb = cfg_hooks->duplicate_block (bb); 948 if (after) 949 move_block_after (new_bb, after); 950 951 new_bb->loop_depth = bb->loop_depth; 952 new_bb->flags = bb->flags; 953 FOR_EACH_EDGE (s, ei, bb->succs) 954 { 955 /* Since we are creating edges from a new block to successors 956 of another block (which therefore are known to be disjoint), there 957 is no need to actually check for duplicated edges. */ 958 n = unchecked_make_edge (new_bb, s->dest, s->flags); 959 n->probability = s->probability; 960 if (e && bb->count) 961 { 962 /* Take care for overflows! */ 963 n->count = s->count * (new_count * 10000 / bb->count) / 10000; 964 s->count -= n->count; 965 } 966 else 967 n->count = s->count; 968 n->aux = s->aux; 969 } 970 971 if (e) 972 { 973 new_bb->count = new_count; 974 bb->count -= new_count; 975 976 new_bb->frequency = EDGE_FREQUENCY (e); 977 bb->frequency -= EDGE_FREQUENCY (e); 978 979 redirect_edge_and_branch_force (e, new_bb); 980 981 if (bb->count < 0) 982 bb->count = 0; 983 if (bb->frequency < 0) 984 bb->frequency = 0; 985 } 986 else 987 { 988 new_bb->count = bb->count; 989 new_bb->frequency = bb->frequency; 990 } 991 992 set_bb_original (new_bb, bb); 993 set_bb_copy (bb, new_bb); 994 995 /* Add the new block to the copy of the loop of BB, or directly to the loop 996 of BB if the loop is not being copied. */ 997 if (current_loops != NULL) 998 { 999 struct loop *cloop = bb->loop_father; 1000 struct loop *copy = get_loop_copy (cloop); 1001 add_bb_to_loop (new_bb, copy ? copy : cloop); 1002 } 1003 1004 return new_bb; 1005 } 1006 1007 /* Return 1 if BB ends with a call, possibly followed by some 1008 instructions that must stay with the call, 0 otherwise. */ 1009 1010 bool 1011 block_ends_with_call_p (basic_block bb) 1012 { 1013 if (!cfg_hooks->block_ends_with_call_p) 1014 internal_error ("%s does not support block_ends_with_call_p", cfg_hooks->name); 1015 1016 return (cfg_hooks->block_ends_with_call_p) (bb); 1017 } 1018 1019 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */ 1020 1021 bool 1022 block_ends_with_condjump_p (const_basic_block bb) 1023 { 1024 if (!cfg_hooks->block_ends_with_condjump_p) 1025 internal_error ("%s does not support block_ends_with_condjump_p", 1026 cfg_hooks->name); 1027 1028 return (cfg_hooks->block_ends_with_condjump_p) (bb); 1029 } 1030 1031 /* Add fake edges to the function exit for any non constant and non noreturn 1032 calls, volatile inline assembly in the bitmap of blocks specified by 1033 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks 1034 that were split. 1035 1036 The goal is to expose cases in which entering a basic block does not imply 1037 that all subsequent instructions must be executed. */ 1038 1039 int 1040 flow_call_edges_add (sbitmap blocks) 1041 { 1042 if (!cfg_hooks->flow_call_edges_add) 1043 internal_error ("%s does not support flow_call_edges_add", 1044 cfg_hooks->name); 1045 1046 return (cfg_hooks->flow_call_edges_add) (blocks); 1047 } 1048 1049 /* This function is called immediately after edge E is added to the 1050 edge vector E->dest->preds. */ 1051 1052 void 1053 execute_on_growing_pred (edge e) 1054 { 1055 if (cfg_hooks->execute_on_growing_pred) 1056 cfg_hooks->execute_on_growing_pred (e); 1057 } 1058 1059 /* This function is called immediately before edge E is removed from 1060 the edge vector E->dest->preds. */ 1061 1062 void 1063 execute_on_shrinking_pred (edge e) 1064 { 1065 if (cfg_hooks->execute_on_shrinking_pred) 1066 cfg_hooks->execute_on_shrinking_pred (e); 1067 } 1068 1069 /* This is used inside loop versioning when we want to insert 1070 stmts/insns on the edges, which have a different behavior 1071 in tree's and in RTL, so we made a CFG hook. */ 1072 void 1073 lv_flush_pending_stmts (edge e) 1074 { 1075 if (cfg_hooks->flush_pending_stmts) 1076 cfg_hooks->flush_pending_stmts (e); 1077 } 1078 1079 /* Loop versioning uses the duplicate_loop_to_header_edge to create 1080 a new version of the loop basic-blocks, the parameters here are 1081 exactly the same as in duplicate_loop_to_header_edge or 1082 tree_duplicate_loop_to_header_edge; while in tree-ssa there is 1083 additional work to maintain ssa information that's why there is 1084 a need to call the tree_duplicate_loop_to_header_edge rather 1085 than duplicate_loop_to_header_edge when we are in tree mode. */ 1086 bool 1087 cfg_hook_duplicate_loop_to_header_edge (struct loop *loop, edge e, 1088 unsigned int ndupl, 1089 sbitmap wont_exit, edge orig, 1090 VEC (edge, heap) **to_remove, 1091 int flags) 1092 { 1093 gcc_assert (cfg_hooks->cfg_hook_duplicate_loop_to_header_edge); 1094 return cfg_hooks->cfg_hook_duplicate_loop_to_header_edge (loop, e, 1095 ndupl, wont_exit, 1096 orig, to_remove, 1097 flags); 1098 } 1099 1100 /* Conditional jumps are represented differently in trees and RTL, 1101 this hook takes a basic block that is known to have a cond jump 1102 at its end and extracts the taken and not taken edges out of it 1103 and store it in E1 and E2 respectively. */ 1104 void 1105 extract_cond_bb_edges (basic_block b, edge *e1, edge *e2) 1106 { 1107 gcc_assert (cfg_hooks->extract_cond_bb_edges); 1108 cfg_hooks->extract_cond_bb_edges (b, e1, e2); 1109 } 1110 1111 /* Responsible for updating the ssa info (PHI nodes) on the 1112 new condition basic block that guards the versioned loop. */ 1113 void 1114 lv_adjust_loop_header_phi (basic_block first, basic_block second, 1115 basic_block new_block, edge e) 1116 { 1117 if (cfg_hooks->lv_adjust_loop_header_phi) 1118 cfg_hooks->lv_adjust_loop_header_phi (first, second, new_block, e); 1119 } 1120 1121 /* Conditions in trees and RTL are different so we need 1122 a different handling when we add the condition to the 1123 versioning code. */ 1124 void 1125 lv_add_condition_to_bb (basic_block first, basic_block second, 1126 basic_block new_block, void *cond) 1127 { 1128 gcc_assert (cfg_hooks->lv_add_condition_to_bb); 1129 cfg_hooks->lv_add_condition_to_bb (first, second, new_block, cond); 1130 } 1131