1 /* Control flow graph manipulation code for GNU compiler. 2 Copyright (C) 1987-2018 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify it under 7 the terms of the GNU General Public License as published by the Free 8 Software Foundation; either version 3, or (at your option) any later 9 version. 10 11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12 WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GCC; see the file COPYING3. If not see 18 <http://www.gnu.org/licenses/>. */ 19 20 /* This file contains low level functions to manipulate the CFG and analyze it 21 that are aware of the RTL intermediate language. 22 23 Available functionality: 24 - Basic CFG/RTL manipulation API documented in cfghooks.h 25 - CFG-aware instruction chain manipulation 26 delete_insn, delete_insn_chain 27 - Edge splitting and committing to edges 28 insert_insn_on_edge, commit_edge_insertions 29 - CFG updating after insn simplification 30 purge_dead_edges, purge_all_dead_edges 31 - CFG fixing after coarse manipulation 32 fixup_abnormal_edges 33 34 Functions not supposed for generic use: 35 - Infrastructure to determine quickly basic block for insn 36 compute_bb_for_insn, update_bb_for_insn, set_block_for_insn, 37 - Edge redirection with updating and optimizing of insn chain 38 block_label, tidy_fallthru_edge, force_nonfallthru */ 39 40 #include "config.h" 41 #include "system.h" 42 #include "coretypes.h" 43 #include "backend.h" 44 #include "target.h" 45 #include "rtl.h" 46 #include "tree.h" 47 #include "cfghooks.h" 48 #include "df.h" 49 #include "insn-config.h" 50 #include "memmodel.h" 51 #include "emit-rtl.h" 52 #include "cfgrtl.h" 53 #include "cfganal.h" 54 #include "cfgbuild.h" 55 #include "cfgcleanup.h" 56 #include "bb-reorder.h" 57 #include "rtl-error.h" 58 #include "insn-attr.h" 59 #include "dojump.h" 60 #include "expr.h" 61 #include "cfgloop.h" 62 #include "tree-pass.h" 63 #include "print-rtl.h" 64 65 /* Holds the interesting leading and trailing notes for the function. 66 Only applicable if the CFG is in cfglayout mode. */ 67 static GTY(()) rtx_insn *cfg_layout_function_footer; 68 static GTY(()) rtx_insn *cfg_layout_function_header; 69 70 static rtx_insn *skip_insns_after_block (basic_block); 71 static void record_effective_endpoints (void); 72 static void fixup_reorder_chain (void); 73 74 void verify_insn_chain (void); 75 static void fixup_fallthru_exit_predecessor (void); 76 static int can_delete_note_p (const rtx_note *); 77 static int can_delete_label_p (const rtx_code_label *); 78 static basic_block rtl_split_edge (edge); 79 static bool rtl_move_block_after (basic_block, basic_block); 80 static int rtl_verify_flow_info (void); 81 static basic_block cfg_layout_split_block (basic_block, void *); 82 static edge cfg_layout_redirect_edge_and_branch (edge, basic_block); 83 static basic_block cfg_layout_redirect_edge_and_branch_force (edge, basic_block); 84 static void cfg_layout_delete_block (basic_block); 85 static void rtl_delete_block (basic_block); 86 static basic_block rtl_redirect_edge_and_branch_force (edge, basic_block); 87 static edge rtl_redirect_edge_and_branch (edge, basic_block); 88 static basic_block rtl_split_block (basic_block, void *); 89 static void rtl_dump_bb (FILE *, basic_block, int, dump_flags_t); 90 static int rtl_verify_flow_info_1 (void); 91 static void rtl_make_forwarder_block (edge); 92 93 /* Return true if NOTE is not one of the ones that must be kept paired, 94 so that we may simply delete it. */ 95 96 static int 97 can_delete_note_p (const rtx_note *note) 98 { 99 switch (NOTE_KIND (note)) 100 { 101 case NOTE_INSN_DELETED: 102 case NOTE_INSN_BASIC_BLOCK: 103 case NOTE_INSN_EPILOGUE_BEG: 104 return true; 105 106 default: 107 return false; 108 } 109 } 110 111 /* True if a given label can be deleted. */ 112 113 static int 114 can_delete_label_p (const rtx_code_label *label) 115 { 116 return (!LABEL_PRESERVE_P (label) 117 /* User declared labels must be preserved. */ 118 && LABEL_NAME (label) == 0 119 && !vec_safe_contains<rtx_insn *> (forced_labels, 120 const_cast<rtx_code_label *> (label))); 121 } 122 123 /* Delete INSN by patching it out. */ 124 125 void 126 delete_insn (rtx_insn *insn) 127 { 128 rtx note; 129 bool really_delete = true; 130 131 if (LABEL_P (insn)) 132 { 133 /* Some labels can't be directly removed from the INSN chain, as they 134 might be references via variables, constant pool etc. 135 Convert them to the special NOTE_INSN_DELETED_LABEL note. */ 136 if (! can_delete_label_p (as_a <rtx_code_label *> (insn))) 137 { 138 const char *name = LABEL_NAME (insn); 139 basic_block bb = BLOCK_FOR_INSN (insn); 140 rtx_insn *bb_note = NEXT_INSN (insn); 141 142 really_delete = false; 143 PUT_CODE (insn, NOTE); 144 NOTE_KIND (insn) = NOTE_INSN_DELETED_LABEL; 145 NOTE_DELETED_LABEL_NAME (insn) = name; 146 147 /* If the note following the label starts a basic block, and the 148 label is a member of the same basic block, interchange the two. */ 149 if (bb_note != NULL_RTX 150 && NOTE_INSN_BASIC_BLOCK_P (bb_note) 151 && bb != NULL 152 && bb == BLOCK_FOR_INSN (bb_note)) 153 { 154 reorder_insns_nobb (insn, insn, bb_note); 155 BB_HEAD (bb) = bb_note; 156 if (BB_END (bb) == bb_note) 157 BB_END (bb) = insn; 158 } 159 } 160 161 remove_node_from_insn_list (insn, &nonlocal_goto_handler_labels); 162 } 163 164 if (really_delete) 165 { 166 /* If this insn has already been deleted, something is very wrong. */ 167 gcc_assert (!insn->deleted ()); 168 if (INSN_P (insn)) 169 df_insn_delete (insn); 170 remove_insn (insn); 171 insn->set_deleted (); 172 } 173 174 /* If deleting a jump, decrement the use count of the label. Deleting 175 the label itself should happen in the normal course of block merging. */ 176 if (JUMP_P (insn)) 177 { 178 if (JUMP_LABEL (insn) 179 && LABEL_P (JUMP_LABEL (insn))) 180 LABEL_NUSES (JUMP_LABEL (insn))--; 181 182 /* If there are more targets, remove them too. */ 183 while ((note 184 = find_reg_note (insn, REG_LABEL_TARGET, NULL_RTX)) != NULL_RTX 185 && LABEL_P (XEXP (note, 0))) 186 { 187 LABEL_NUSES (XEXP (note, 0))--; 188 remove_note (insn, note); 189 } 190 } 191 192 /* Also if deleting any insn that references a label as an operand. */ 193 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, NULL_RTX)) != NULL_RTX 194 && LABEL_P (XEXP (note, 0))) 195 { 196 LABEL_NUSES (XEXP (note, 0))--; 197 remove_note (insn, note); 198 } 199 200 if (rtx_jump_table_data *table = dyn_cast <rtx_jump_table_data *> (insn)) 201 { 202 rtvec vec = table->get_labels (); 203 int len = GET_NUM_ELEM (vec); 204 int i; 205 206 for (i = 0; i < len; i++) 207 { 208 rtx label = XEXP (RTVEC_ELT (vec, i), 0); 209 210 /* When deleting code in bulk (e.g. removing many unreachable 211 blocks) we can delete a label that's a target of the vector 212 before deleting the vector itself. */ 213 if (!NOTE_P (label)) 214 LABEL_NUSES (label)--; 215 } 216 } 217 } 218 219 /* Like delete_insn but also purge dead edges from BB. 220 Return true if any edges are eliminated. */ 221 222 bool 223 delete_insn_and_edges (rtx_insn *insn) 224 { 225 bool purge = false; 226 227 if (INSN_P (insn) 228 && BLOCK_FOR_INSN (insn) 229 && BB_END (BLOCK_FOR_INSN (insn)) == insn) 230 purge = true; 231 delete_insn (insn); 232 if (purge) 233 return purge_dead_edges (BLOCK_FOR_INSN (insn)); 234 return false; 235 } 236 237 /* Unlink a chain of insns between START and FINISH, leaving notes 238 that must be paired. If CLEAR_BB is true, we set bb field for 239 insns that cannot be removed to NULL. */ 240 241 void 242 delete_insn_chain (rtx start, rtx_insn *finish, bool clear_bb) 243 { 244 /* Unchain the insns one by one. It would be quicker to delete all of these 245 with a single unchaining, rather than one at a time, but we need to keep 246 the NOTE's. */ 247 rtx_insn *current = finish; 248 while (1) 249 { 250 rtx_insn *prev = PREV_INSN (current); 251 if (NOTE_P (current) && !can_delete_note_p (as_a <rtx_note *> (current))) 252 ; 253 else 254 delete_insn (current); 255 256 if (clear_bb && !current->deleted ()) 257 set_block_for_insn (current, NULL); 258 259 if (current == start) 260 break; 261 current = prev; 262 } 263 } 264 265 /* Create a new basic block consisting of the instructions between HEAD and END 266 inclusive. This function is designed to allow fast BB construction - reuses 267 the note and basic block struct in BB_NOTE, if any and do not grow 268 BASIC_BLOCK chain and should be used directly only by CFG construction code. 269 END can be NULL in to create new empty basic block before HEAD. Both END 270 and HEAD can be NULL to create basic block at the end of INSN chain. 271 AFTER is the basic block we should be put after. */ 272 273 basic_block 274 create_basic_block_structure (rtx_insn *head, rtx_insn *end, rtx_note *bb_note, 275 basic_block after) 276 { 277 basic_block bb; 278 279 if (bb_note 280 && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL 281 && bb->aux == NULL) 282 { 283 /* If we found an existing note, thread it back onto the chain. */ 284 285 rtx_insn *after; 286 287 if (LABEL_P (head)) 288 after = head; 289 else 290 { 291 after = PREV_INSN (head); 292 head = bb_note; 293 } 294 295 if (after != bb_note && NEXT_INSN (after) != bb_note) 296 reorder_insns_nobb (bb_note, bb_note, after); 297 } 298 else 299 { 300 /* Otherwise we must create a note and a basic block structure. */ 301 302 bb = alloc_block (); 303 304 init_rtl_bb_info (bb); 305 if (!head && !end) 306 head = end = bb_note 307 = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ()); 308 else if (LABEL_P (head) && end) 309 { 310 bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head); 311 if (head == end) 312 end = bb_note; 313 } 314 else 315 { 316 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head); 317 head = bb_note; 318 if (!end) 319 end = head; 320 } 321 322 NOTE_BASIC_BLOCK (bb_note) = bb; 323 } 324 325 /* Always include the bb note in the block. */ 326 if (NEXT_INSN (end) == bb_note) 327 end = bb_note; 328 329 BB_HEAD (bb) = head; 330 BB_END (bb) = end; 331 bb->index = last_basic_block_for_fn (cfun)++; 332 bb->flags = BB_NEW | BB_RTL; 333 link_block (bb, after); 334 SET_BASIC_BLOCK_FOR_FN (cfun, bb->index, bb); 335 df_bb_refs_record (bb->index, false); 336 update_bb_for_insn (bb); 337 BB_SET_PARTITION (bb, BB_UNPARTITIONED); 338 339 /* Tag the block so that we know it has been used when considering 340 other basic block notes. */ 341 bb->aux = bb; 342 343 return bb; 344 } 345 346 /* Create new basic block consisting of instructions in between HEAD and END 347 and place it to the BB chain after block AFTER. END can be NULL to 348 create a new empty basic block before HEAD. Both END and HEAD can be 349 NULL to create basic block at the end of INSN chain. */ 350 351 static basic_block 352 rtl_create_basic_block (void *headp, void *endp, basic_block after) 353 { 354 rtx_insn *head = (rtx_insn *) headp; 355 rtx_insn *end = (rtx_insn *) endp; 356 basic_block bb; 357 358 /* Grow the basic block array if needed. */ 359 if ((size_t) last_basic_block_for_fn (cfun) 360 >= basic_block_info_for_fn (cfun)->length ()) 361 { 362 size_t new_size = 363 (last_basic_block_for_fn (cfun) 364 + (last_basic_block_for_fn (cfun) + 3) / 4); 365 vec_safe_grow_cleared (basic_block_info_for_fn (cfun), new_size); 366 } 367 368 n_basic_blocks_for_fn (cfun)++; 369 370 bb = create_basic_block_structure (head, end, NULL, after); 371 bb->aux = NULL; 372 return bb; 373 } 374 375 static basic_block 376 cfg_layout_create_basic_block (void *head, void *end, basic_block after) 377 { 378 basic_block newbb = rtl_create_basic_block (head, end, after); 379 380 return newbb; 381 } 382 383 /* Delete the insns in a (non-live) block. We physically delete every 384 non-deleted-note insn, and update the flow graph appropriately. 385 386 Return nonzero if we deleted an exception handler. */ 387 388 /* ??? Preserving all such notes strikes me as wrong. It would be nice 389 to post-process the stream to remove empty blocks, loops, ranges, etc. */ 390 391 static void 392 rtl_delete_block (basic_block b) 393 { 394 rtx_insn *insn, *end; 395 396 /* If the head of this block is a CODE_LABEL, then it might be the 397 label for an exception handler which can't be reached. We need 398 to remove the label from the exception_handler_label list. */ 399 insn = BB_HEAD (b); 400 401 end = get_last_bb_insn (b); 402 403 /* Selectively delete the entire chain. */ 404 BB_HEAD (b) = NULL; 405 delete_insn_chain (insn, end, true); 406 407 408 if (dump_file) 409 fprintf (dump_file, "deleting block %d\n", b->index); 410 df_bb_delete (b->index); 411 } 412 413 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */ 414 415 void 416 compute_bb_for_insn (void) 417 { 418 basic_block bb; 419 420 FOR_EACH_BB_FN (bb, cfun) 421 { 422 rtx_insn *end = BB_END (bb); 423 rtx_insn *insn; 424 425 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn)) 426 { 427 BLOCK_FOR_INSN (insn) = bb; 428 if (insn == end) 429 break; 430 } 431 } 432 } 433 434 /* Release the basic_block_for_insn array. */ 435 436 unsigned int 437 free_bb_for_insn (void) 438 { 439 rtx_insn *insn; 440 for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 441 if (!BARRIER_P (insn)) 442 BLOCK_FOR_INSN (insn) = NULL; 443 return 0; 444 } 445 446 namespace { 447 448 const pass_data pass_data_free_cfg = 449 { 450 RTL_PASS, /* type */ 451 "*free_cfg", /* name */ 452 OPTGROUP_NONE, /* optinfo_flags */ 453 TV_NONE, /* tv_id */ 454 0, /* properties_required */ 455 0, /* properties_provided */ 456 PROP_cfg, /* properties_destroyed */ 457 0, /* todo_flags_start */ 458 0, /* todo_flags_finish */ 459 }; 460 461 class pass_free_cfg : public rtl_opt_pass 462 { 463 public: 464 pass_free_cfg (gcc::context *ctxt) 465 : rtl_opt_pass (pass_data_free_cfg, ctxt) 466 {} 467 468 /* opt_pass methods: */ 469 virtual unsigned int execute (function *); 470 471 }; // class pass_free_cfg 472 473 unsigned int 474 pass_free_cfg::execute (function *) 475 { 476 /* The resource.c machinery uses DF but the CFG isn't guaranteed to be 477 valid at that point so it would be too late to call df_analyze. */ 478 if (DELAY_SLOTS && optimize > 0 && flag_delayed_branch) 479 { 480 df_note_add_problem (); 481 df_analyze (); 482 } 483 484 if (crtl->has_bb_partition) 485 insert_section_boundary_note (); 486 487 free_bb_for_insn (); 488 return 0; 489 } 490 491 } // anon namespace 492 493 rtl_opt_pass * 494 make_pass_free_cfg (gcc::context *ctxt) 495 { 496 return new pass_free_cfg (ctxt); 497 } 498 499 /* Return RTX to emit after when we want to emit code on the entry of function. */ 500 rtx_insn * 501 entry_of_function (void) 502 { 503 return (n_basic_blocks_for_fn (cfun) > NUM_FIXED_BLOCKS ? 504 BB_HEAD (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb) : get_insns ()); 505 } 506 507 /* Emit INSN at the entry point of the function, ensuring that it is only 508 executed once per function. */ 509 void 510 emit_insn_at_entry (rtx insn) 511 { 512 edge_iterator ei = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs); 513 edge e = ei_safe_edge (ei); 514 gcc_assert (e->flags & EDGE_FALLTHRU); 515 516 insert_insn_on_edge (insn, e); 517 commit_edge_insertions (); 518 } 519 520 /* Update BLOCK_FOR_INSN of insns between BEGIN and END 521 (or BARRIER if found) and notify df of the bb change. 522 The insn chain range is inclusive 523 (i.e. both BEGIN and END will be updated. */ 524 525 static void 526 update_bb_for_insn_chain (rtx_insn *begin, rtx_insn *end, basic_block bb) 527 { 528 rtx_insn *insn; 529 530 end = NEXT_INSN (end); 531 for (insn = begin; insn != end; insn = NEXT_INSN (insn)) 532 if (!BARRIER_P (insn)) 533 df_insn_change_bb (insn, bb); 534 } 535 536 /* Update BLOCK_FOR_INSN of insns in BB to BB, 537 and notify df of the change. */ 538 539 void 540 update_bb_for_insn (basic_block bb) 541 { 542 update_bb_for_insn_chain (BB_HEAD (bb), BB_END (bb), bb); 543 } 544 545 546 /* Like active_insn_p, except keep the return value clobber around 547 even after reload. */ 548 549 static bool 550 flow_active_insn_p (const rtx_insn *insn) 551 { 552 if (active_insn_p (insn)) 553 return true; 554 555 /* A clobber of the function return value exists for buggy 556 programs that fail to return a value. Its effect is to 557 keep the return value from being live across the entire 558 function. If we allow it to be skipped, we introduce the 559 possibility for register lifetime confusion. */ 560 if (GET_CODE (PATTERN (insn)) == CLOBBER 561 && REG_P (XEXP (PATTERN (insn), 0)) 562 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0))) 563 return true; 564 565 return false; 566 } 567 568 /* Return true if the block has no effect and only forwards control flow to 569 its single destination. */ 570 571 bool 572 contains_no_active_insn_p (const_basic_block bb) 573 { 574 rtx_insn *insn; 575 576 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) 577 || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) 578 || !single_succ_p (bb) 579 || (single_succ_edge (bb)->flags & EDGE_FAKE) != 0) 580 return false; 581 582 for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn)) 583 if (INSN_P (insn) && flow_active_insn_p (insn)) 584 return false; 585 586 return (!INSN_P (insn) 587 || (JUMP_P (insn) && simplejump_p (insn)) 588 || !flow_active_insn_p (insn)); 589 } 590 591 /* Likewise, but protect loop latches, headers and preheaders. */ 592 /* FIXME: Make this a cfg hook. */ 593 594 bool 595 forwarder_block_p (const_basic_block bb) 596 { 597 if (!contains_no_active_insn_p (bb)) 598 return false; 599 600 /* Protect loop latches, headers and preheaders. */ 601 if (current_loops) 602 { 603 basic_block dest; 604 if (bb->loop_father->header == bb) 605 return false; 606 dest = EDGE_SUCC (bb, 0)->dest; 607 if (dest->loop_father->header == dest) 608 return false; 609 } 610 611 return true; 612 } 613 614 /* Return nonzero if we can reach target from src by falling through. */ 615 /* FIXME: Make this a cfg hook, the result is only valid in cfgrtl mode. */ 616 617 bool 618 can_fallthru (basic_block src, basic_block target) 619 { 620 rtx_insn *insn = BB_END (src); 621 rtx_insn *insn2; 622 edge e; 623 edge_iterator ei; 624 625 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun)) 626 return true; 627 if (src->next_bb != target) 628 return false; 629 630 /* ??? Later we may add code to move jump tables offline. */ 631 if (tablejump_p (insn, NULL, NULL)) 632 return false; 633 634 FOR_EACH_EDGE (e, ei, src->succs) 635 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun) 636 && e->flags & EDGE_FALLTHRU) 637 return false; 638 639 insn2 = BB_HEAD (target); 640 if (!active_insn_p (insn2)) 641 insn2 = next_active_insn (insn2); 642 643 return next_active_insn (insn) == insn2; 644 } 645 646 /* Return nonzero if we could reach target from src by falling through, 647 if the target was made adjacent. If we already have a fall-through 648 edge to the exit block, we can't do that. */ 649 static bool 650 could_fall_through (basic_block src, basic_block target) 651 { 652 edge e; 653 edge_iterator ei; 654 655 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun)) 656 return true; 657 FOR_EACH_EDGE (e, ei, src->succs) 658 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun) 659 && e->flags & EDGE_FALLTHRU) 660 return 0; 661 return true; 662 } 663 664 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */ 665 rtx_note * 666 bb_note (basic_block bb) 667 { 668 rtx_insn *note; 669 670 note = BB_HEAD (bb); 671 if (LABEL_P (note)) 672 note = NEXT_INSN (note); 673 674 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note)); 675 return as_a <rtx_note *> (note); 676 } 677 678 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK 679 note associated with the BLOCK. */ 680 681 static rtx_insn * 682 first_insn_after_basic_block_note (basic_block block) 683 { 684 rtx_insn *insn; 685 686 /* Get the first instruction in the block. */ 687 insn = BB_HEAD (block); 688 689 if (insn == NULL_RTX) 690 return NULL; 691 if (LABEL_P (insn)) 692 insn = NEXT_INSN (insn); 693 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn)); 694 695 return NEXT_INSN (insn); 696 } 697 698 /* Creates a new basic block just after basic block BB by splitting 699 everything after specified instruction INSNP. */ 700 701 static basic_block 702 rtl_split_block (basic_block bb, void *insnp) 703 { 704 basic_block new_bb; 705 rtx_insn *insn = (rtx_insn *) insnp; 706 edge e; 707 edge_iterator ei; 708 709 if (!insn) 710 { 711 insn = first_insn_after_basic_block_note (bb); 712 713 if (insn) 714 { 715 rtx_insn *next = insn; 716 717 insn = PREV_INSN (insn); 718 719 /* If the block contains only debug insns, insn would have 720 been NULL in a non-debug compilation, and then we'd end 721 up emitting a DELETED note. For -fcompare-debug 722 stability, emit the note too. */ 723 if (insn != BB_END (bb) 724 && DEBUG_INSN_P (next) 725 && DEBUG_INSN_P (BB_END (bb))) 726 { 727 while (next != BB_END (bb) && DEBUG_INSN_P (next)) 728 next = NEXT_INSN (next); 729 730 if (next == BB_END (bb)) 731 emit_note_after (NOTE_INSN_DELETED, next); 732 } 733 } 734 else 735 insn = get_last_insn (); 736 } 737 738 /* We probably should check type of the insn so that we do not create 739 inconsistent cfg. It is checked in verify_flow_info anyway, so do not 740 bother. */ 741 if (insn == BB_END (bb)) 742 emit_note_after (NOTE_INSN_DELETED, insn); 743 744 /* Create the new basic block. */ 745 new_bb = create_basic_block (NEXT_INSN (insn), BB_END (bb), bb); 746 BB_COPY_PARTITION (new_bb, bb); 747 BB_END (bb) = insn; 748 749 /* Redirect the outgoing edges. */ 750 new_bb->succs = bb->succs; 751 bb->succs = NULL; 752 FOR_EACH_EDGE (e, ei, new_bb->succs) 753 e->src = new_bb; 754 755 /* The new block starts off being dirty. */ 756 df_set_bb_dirty (bb); 757 return new_bb; 758 } 759 760 /* Return true if the single edge between blocks A and B is the only place 761 in RTL which holds some unique locus. */ 762 763 static bool 764 unique_locus_on_edge_between_p (basic_block a, basic_block b) 765 { 766 const location_t goto_locus = EDGE_SUCC (a, 0)->goto_locus; 767 rtx_insn *insn, *end; 768 769 if (LOCATION_LOCUS (goto_locus) == UNKNOWN_LOCATION) 770 return false; 771 772 /* First scan block A backward. */ 773 insn = BB_END (a); 774 end = PREV_INSN (BB_HEAD (a)); 775 while (insn != end && (!NONDEBUG_INSN_P (insn) || !INSN_HAS_LOCATION (insn))) 776 insn = PREV_INSN (insn); 777 778 if (insn != end && INSN_LOCATION (insn) == goto_locus) 779 return false; 780 781 /* Then scan block B forward. */ 782 insn = BB_HEAD (b); 783 if (insn) 784 { 785 end = NEXT_INSN (BB_END (b)); 786 while (insn != end && !NONDEBUG_INSN_P (insn)) 787 insn = NEXT_INSN (insn); 788 789 if (insn != end && INSN_HAS_LOCATION (insn) 790 && INSN_LOCATION (insn) == goto_locus) 791 return false; 792 } 793 794 return true; 795 } 796 797 /* If the single edge between blocks A and B is the only place in RTL which 798 holds some unique locus, emit a nop with that locus between the blocks. */ 799 800 static void 801 emit_nop_for_unique_locus_between (basic_block a, basic_block b) 802 { 803 if (!unique_locus_on_edge_between_p (a, b)) 804 return; 805 806 BB_END (a) = emit_insn_after_noloc (gen_nop (), BB_END (a), a); 807 INSN_LOCATION (BB_END (a)) = EDGE_SUCC (a, 0)->goto_locus; 808 } 809 810 /* Blocks A and B are to be merged into a single block A. The insns 811 are already contiguous. */ 812 813 static void 814 rtl_merge_blocks (basic_block a, basic_block b) 815 { 816 rtx_insn *b_head = BB_HEAD (b), *b_end = BB_END (b), *a_end = BB_END (a); 817 rtx_insn *del_first = NULL, *del_last = NULL; 818 rtx_insn *b_debug_start = b_end, *b_debug_end = b_end; 819 bool forwarder_p = (b->flags & BB_FORWARDER_BLOCK) != 0; 820 int b_empty = 0; 821 822 if (dump_file) 823 fprintf (dump_file, "Merging block %d into block %d...\n", b->index, 824 a->index); 825 826 while (DEBUG_INSN_P (b_end)) 827 b_end = PREV_INSN (b_debug_start = b_end); 828 829 /* If there was a CODE_LABEL beginning B, delete it. */ 830 if (LABEL_P (b_head)) 831 { 832 /* Detect basic blocks with nothing but a label. This can happen 833 in particular at the end of a function. */ 834 if (b_head == b_end) 835 b_empty = 1; 836 837 del_first = del_last = b_head; 838 b_head = NEXT_INSN (b_head); 839 } 840 841 /* Delete the basic block note and handle blocks containing just that 842 note. */ 843 if (NOTE_INSN_BASIC_BLOCK_P (b_head)) 844 { 845 if (b_head == b_end) 846 b_empty = 1; 847 if (! del_last) 848 del_first = b_head; 849 850 del_last = b_head; 851 b_head = NEXT_INSN (b_head); 852 } 853 854 /* If there was a jump out of A, delete it. */ 855 if (JUMP_P (a_end)) 856 { 857 rtx_insn *prev; 858 859 for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev)) 860 if (!NOTE_P (prev) 861 || NOTE_INSN_BASIC_BLOCK_P (prev) 862 || prev == BB_HEAD (a)) 863 break; 864 865 del_first = a_end; 866 867 /* If this was a conditional jump, we need to also delete 868 the insn that set cc0. */ 869 if (HAVE_cc0 && only_sets_cc0_p (prev)) 870 { 871 rtx_insn *tmp = prev; 872 873 prev = prev_nonnote_insn (prev); 874 if (!prev) 875 prev = BB_HEAD (a); 876 del_first = tmp; 877 } 878 879 a_end = PREV_INSN (del_first); 880 } 881 else if (BARRIER_P (NEXT_INSN (a_end))) 882 del_first = NEXT_INSN (a_end); 883 884 /* Delete everything marked above as well as crap that might be 885 hanging out between the two blocks. */ 886 BB_END (a) = a_end; 887 BB_HEAD (b) = b_empty ? NULL : b_head; 888 delete_insn_chain (del_first, del_last, true); 889 890 /* When not optimizing and the edge is the only place in RTL which holds 891 some unique locus, emit a nop with that locus in between. */ 892 if (!optimize) 893 { 894 emit_nop_for_unique_locus_between (a, b); 895 a_end = BB_END (a); 896 } 897 898 /* Reassociate the insns of B with A. */ 899 if (!b_empty) 900 { 901 update_bb_for_insn_chain (a_end, b_debug_end, a); 902 903 BB_END (a) = b_debug_end; 904 BB_HEAD (b) = NULL; 905 } 906 else if (b_end != b_debug_end) 907 { 908 /* Move any deleted labels and other notes between the end of A 909 and the debug insns that make up B after the debug insns, 910 bringing the debug insns into A while keeping the notes after 911 the end of A. */ 912 if (NEXT_INSN (a_end) != b_debug_start) 913 reorder_insns_nobb (NEXT_INSN (a_end), PREV_INSN (b_debug_start), 914 b_debug_end); 915 update_bb_for_insn_chain (b_debug_start, b_debug_end, a); 916 BB_END (a) = b_debug_end; 917 } 918 919 df_bb_delete (b->index); 920 921 /* If B was a forwarder block, propagate the locus on the edge. */ 922 if (forwarder_p 923 && LOCATION_LOCUS (EDGE_SUCC (b, 0)->goto_locus) == UNKNOWN_LOCATION) 924 EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus; 925 926 if (dump_file) 927 fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index); 928 } 929 930 931 /* Return true when block A and B can be merged. */ 932 933 static bool 934 rtl_can_merge_blocks (basic_block a, basic_block b) 935 { 936 /* If we are partitioning hot/cold basic blocks, we don't want to 937 mess up unconditional or indirect jumps that cross between hot 938 and cold sections. 939 940 Basic block partitioning may result in some jumps that appear to 941 be optimizable (or blocks that appear to be mergeable), but which really 942 must be left untouched (they are required to make it safely across 943 partition boundaries). See the comments at the top of 944 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */ 945 946 if (BB_PARTITION (a) != BB_PARTITION (b)) 947 return false; 948 949 /* Protect the loop latches. */ 950 if (current_loops && b->loop_father->latch == b) 951 return false; 952 953 /* There must be exactly one edge in between the blocks. */ 954 return (single_succ_p (a) 955 && single_succ (a) == b 956 && single_pred_p (b) 957 && a != b 958 /* Must be simple edge. */ 959 && !(single_succ_edge (a)->flags & EDGE_COMPLEX) 960 && a->next_bb == b 961 && a != ENTRY_BLOCK_PTR_FOR_FN (cfun) 962 && b != EXIT_BLOCK_PTR_FOR_FN (cfun) 963 /* If the jump insn has side effects, 964 we can't kill the edge. */ 965 && (!JUMP_P (BB_END (a)) 966 || (reload_completed 967 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a))))); 968 } 969 970 /* Return the label in the head of basic block BLOCK. Create one if it doesn't 971 exist. */ 972 973 rtx_code_label * 974 block_label (basic_block block) 975 { 976 if (block == EXIT_BLOCK_PTR_FOR_FN (cfun)) 977 return NULL; 978 979 if (!LABEL_P (BB_HEAD (block))) 980 { 981 BB_HEAD (block) = emit_label_before (gen_label_rtx (), BB_HEAD (block)); 982 } 983 984 return as_a <rtx_code_label *> (BB_HEAD (block)); 985 } 986 987 /* Remove all barriers from BB_FOOTER of a BB. */ 988 989 static void 990 remove_barriers_from_footer (basic_block bb) 991 { 992 rtx_insn *insn = BB_FOOTER (bb); 993 994 /* Remove barriers but keep jumptables. */ 995 while (insn) 996 { 997 if (BARRIER_P (insn)) 998 { 999 if (PREV_INSN (insn)) 1000 SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn); 1001 else 1002 BB_FOOTER (bb) = NEXT_INSN (insn); 1003 if (NEXT_INSN (insn)) 1004 SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn); 1005 } 1006 if (LABEL_P (insn)) 1007 return; 1008 insn = NEXT_INSN (insn); 1009 } 1010 } 1011 1012 /* Attempt to perform edge redirection by replacing possibly complex jump 1013 instruction by unconditional jump or removing jump completely. This can 1014 apply only if all edges now point to the same block. The parameters and 1015 return values are equivalent to redirect_edge_and_branch. */ 1016 1017 edge 1018 try_redirect_by_replacing_jump (edge e, basic_block target, bool in_cfglayout) 1019 { 1020 basic_block src = e->src; 1021 rtx_insn *insn = BB_END (src), *kill_from; 1022 rtx set; 1023 int fallthru = 0; 1024 1025 /* If we are partitioning hot/cold basic blocks, we don't want to 1026 mess up unconditional or indirect jumps that cross between hot 1027 and cold sections. 1028 1029 Basic block partitioning may result in some jumps that appear to 1030 be optimizable (or blocks that appear to be mergeable), but which really 1031 must be left untouched (they are required to make it safely across 1032 partition boundaries). See the comments at the top of 1033 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */ 1034 1035 if (BB_PARTITION (src) != BB_PARTITION (target)) 1036 return NULL; 1037 1038 /* We can replace or remove a complex jump only when we have exactly 1039 two edges. Also, if we have exactly one outgoing edge, we can 1040 redirect that. */ 1041 if (EDGE_COUNT (src->succs) >= 3 1042 /* Verify that all targets will be TARGET. Specifically, the 1043 edge that is not E must also go to TARGET. */ 1044 || (EDGE_COUNT (src->succs) == 2 1045 && EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)) 1046 return NULL; 1047 1048 if (!onlyjump_p (insn)) 1049 return NULL; 1050 if ((!optimize || reload_completed) && tablejump_p (insn, NULL, NULL)) 1051 return NULL; 1052 1053 /* Avoid removing branch with side effects. */ 1054 set = single_set (insn); 1055 if (!set || side_effects_p (set)) 1056 return NULL; 1057 1058 /* In case we zap a conditional jump, we'll need to kill 1059 the cc0 setter too. */ 1060 kill_from = insn; 1061 if (HAVE_cc0 && reg_mentioned_p (cc0_rtx, PATTERN (insn)) 1062 && only_sets_cc0_p (PREV_INSN (insn))) 1063 kill_from = PREV_INSN (insn); 1064 1065 /* See if we can create the fallthru edge. */ 1066 if (in_cfglayout || can_fallthru (src, target)) 1067 { 1068 if (dump_file) 1069 fprintf (dump_file, "Removing jump %i.\n", INSN_UID (insn)); 1070 fallthru = 1; 1071 1072 /* Selectively unlink whole insn chain. */ 1073 if (in_cfglayout) 1074 { 1075 delete_insn_chain (kill_from, BB_END (src), false); 1076 remove_barriers_from_footer (src); 1077 } 1078 else 1079 delete_insn_chain (kill_from, PREV_INSN (BB_HEAD (target)), 1080 false); 1081 } 1082 1083 /* If this already is simplejump, redirect it. */ 1084 else if (simplejump_p (insn)) 1085 { 1086 if (e->dest == target) 1087 return NULL; 1088 if (dump_file) 1089 fprintf (dump_file, "Redirecting jump %i from %i to %i.\n", 1090 INSN_UID (insn), e->dest->index, target->index); 1091 if (!redirect_jump (as_a <rtx_jump_insn *> (insn), 1092 block_label (target), 0)) 1093 { 1094 gcc_assert (target == EXIT_BLOCK_PTR_FOR_FN (cfun)); 1095 return NULL; 1096 } 1097 } 1098 1099 /* Cannot do anything for target exit block. */ 1100 else if (target == EXIT_BLOCK_PTR_FOR_FN (cfun)) 1101 return NULL; 1102 1103 /* Or replace possibly complicated jump insn by simple jump insn. */ 1104 else 1105 { 1106 rtx_code_label *target_label = block_label (target); 1107 rtx_insn *barrier; 1108 rtx_insn *label; 1109 rtx_jump_table_data *table; 1110 1111 emit_jump_insn_after_noloc (targetm.gen_jump (target_label), insn); 1112 JUMP_LABEL (BB_END (src)) = target_label; 1113 LABEL_NUSES (target_label)++; 1114 if (dump_file) 1115 fprintf (dump_file, "Replacing insn %i by jump %i\n", 1116 INSN_UID (insn), INSN_UID (BB_END (src))); 1117 1118 1119 delete_insn_chain (kill_from, insn, false); 1120 1121 /* Recognize a tablejump that we are converting to a 1122 simple jump and remove its associated CODE_LABEL 1123 and ADDR_VEC or ADDR_DIFF_VEC. */ 1124 if (tablejump_p (insn, &label, &table)) 1125 delete_insn_chain (label, table, false); 1126 1127 barrier = next_nonnote_nondebug_insn (BB_END (src)); 1128 if (!barrier || !BARRIER_P (barrier)) 1129 emit_barrier_after (BB_END (src)); 1130 else 1131 { 1132 if (barrier != NEXT_INSN (BB_END (src))) 1133 { 1134 /* Move the jump before barrier so that the notes 1135 which originally were or were created before jump table are 1136 inside the basic block. */ 1137 rtx_insn *new_insn = BB_END (src); 1138 1139 update_bb_for_insn_chain (NEXT_INSN (BB_END (src)), 1140 PREV_INSN (barrier), src); 1141 1142 SET_NEXT_INSN (PREV_INSN (new_insn)) = NEXT_INSN (new_insn); 1143 SET_PREV_INSN (NEXT_INSN (new_insn)) = PREV_INSN (new_insn); 1144 1145 SET_NEXT_INSN (new_insn) = barrier; 1146 SET_NEXT_INSN (PREV_INSN (barrier)) = new_insn; 1147 1148 SET_PREV_INSN (new_insn) = PREV_INSN (barrier); 1149 SET_PREV_INSN (barrier) = new_insn; 1150 } 1151 } 1152 } 1153 1154 /* Keep only one edge out and set proper flags. */ 1155 if (!single_succ_p (src)) 1156 remove_edge (e); 1157 gcc_assert (single_succ_p (src)); 1158 1159 e = single_succ_edge (src); 1160 if (fallthru) 1161 e->flags = EDGE_FALLTHRU; 1162 else 1163 e->flags = 0; 1164 1165 e->probability = profile_probability::always (); 1166 1167 if (e->dest != target) 1168 redirect_edge_succ (e, target); 1169 return e; 1170 } 1171 1172 /* Subroutine of redirect_branch_edge that tries to patch the jump 1173 instruction INSN so that it reaches block NEW. Do this 1174 only when it originally reached block OLD. Return true if this 1175 worked or the original target wasn't OLD, return false if redirection 1176 doesn't work. */ 1177 1178 static bool 1179 patch_jump_insn (rtx_insn *insn, rtx_insn *old_label, basic_block new_bb) 1180 { 1181 rtx_jump_table_data *table; 1182 rtx tmp; 1183 /* Recognize a tablejump and adjust all matching cases. */ 1184 if (tablejump_p (insn, NULL, &table)) 1185 { 1186 rtvec vec; 1187 int j; 1188 rtx_code_label *new_label = block_label (new_bb); 1189 1190 if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) 1191 return false; 1192 vec = table->get_labels (); 1193 1194 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j) 1195 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label) 1196 { 1197 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label); 1198 --LABEL_NUSES (old_label); 1199 ++LABEL_NUSES (new_label); 1200 } 1201 1202 /* Handle casesi dispatch insns. */ 1203 if ((tmp = single_set (insn)) != NULL 1204 && SET_DEST (tmp) == pc_rtx 1205 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE 1206 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF 1207 && label_ref_label (XEXP (SET_SRC (tmp), 2)) == old_label) 1208 { 1209 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (Pmode, 1210 new_label); 1211 --LABEL_NUSES (old_label); 1212 ++LABEL_NUSES (new_label); 1213 } 1214 } 1215 else if ((tmp = extract_asm_operands (PATTERN (insn))) != NULL) 1216 { 1217 int i, n = ASM_OPERANDS_LABEL_LENGTH (tmp); 1218 rtx note; 1219 1220 if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) 1221 return false; 1222 rtx_code_label *new_label = block_label (new_bb); 1223 1224 for (i = 0; i < n; ++i) 1225 { 1226 rtx old_ref = ASM_OPERANDS_LABEL (tmp, i); 1227 gcc_assert (GET_CODE (old_ref) == LABEL_REF); 1228 if (XEXP (old_ref, 0) == old_label) 1229 { 1230 ASM_OPERANDS_LABEL (tmp, i) 1231 = gen_rtx_LABEL_REF (Pmode, new_label); 1232 --LABEL_NUSES (old_label); 1233 ++LABEL_NUSES (new_label); 1234 } 1235 } 1236 1237 if (JUMP_LABEL (insn) == old_label) 1238 { 1239 JUMP_LABEL (insn) = new_label; 1240 note = find_reg_note (insn, REG_LABEL_TARGET, new_label); 1241 if (note) 1242 remove_note (insn, note); 1243 } 1244 else 1245 { 1246 note = find_reg_note (insn, REG_LABEL_TARGET, old_label); 1247 if (note) 1248 remove_note (insn, note); 1249 if (JUMP_LABEL (insn) != new_label 1250 && !find_reg_note (insn, REG_LABEL_TARGET, new_label)) 1251 add_reg_note (insn, REG_LABEL_TARGET, new_label); 1252 } 1253 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label)) 1254 != NULL_RTX) 1255 XEXP (note, 0) = new_label; 1256 } 1257 else 1258 { 1259 /* ?? We may play the games with moving the named labels from 1260 one basic block to the other in case only one computed_jump is 1261 available. */ 1262 if (computed_jump_p (insn) 1263 /* A return instruction can't be redirected. */ 1264 || returnjump_p (insn)) 1265 return false; 1266 1267 if (!currently_expanding_to_rtl || JUMP_LABEL (insn) == old_label) 1268 { 1269 /* If the insn doesn't go where we think, we're confused. */ 1270 gcc_assert (JUMP_LABEL (insn) == old_label); 1271 1272 /* If the substitution doesn't succeed, die. This can happen 1273 if the back end emitted unrecognizable instructions or if 1274 target is exit block on some arches. Or for crossing 1275 jumps. */ 1276 if (!redirect_jump (as_a <rtx_jump_insn *> (insn), 1277 block_label (new_bb), 0)) 1278 { 1279 gcc_assert (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun) 1280 || CROSSING_JUMP_P (insn)); 1281 return false; 1282 } 1283 } 1284 } 1285 return true; 1286 } 1287 1288 1289 /* Redirect edge representing branch of (un)conditional jump or tablejump, 1290 NULL on failure */ 1291 static edge 1292 redirect_branch_edge (edge e, basic_block target) 1293 { 1294 rtx_insn *old_label = BB_HEAD (e->dest); 1295 basic_block src = e->src; 1296 rtx_insn *insn = BB_END (src); 1297 1298 /* We can only redirect non-fallthru edges of jump insn. */ 1299 if (e->flags & EDGE_FALLTHRU) 1300 return NULL; 1301 else if (!JUMP_P (insn) && !currently_expanding_to_rtl) 1302 return NULL; 1303 1304 if (!currently_expanding_to_rtl) 1305 { 1306 if (!patch_jump_insn (as_a <rtx_jump_insn *> (insn), old_label, target)) 1307 return NULL; 1308 } 1309 else 1310 /* When expanding this BB might actually contain multiple 1311 jumps (i.e. not yet split by find_many_sub_basic_blocks). 1312 Redirect all of those that match our label. */ 1313 FOR_BB_INSNS (src, insn) 1314 if (JUMP_P (insn) && !patch_jump_insn (as_a <rtx_jump_insn *> (insn), 1315 old_label, target)) 1316 return NULL; 1317 1318 if (dump_file) 1319 fprintf (dump_file, "Edge %i->%i redirected to %i\n", 1320 e->src->index, e->dest->index, target->index); 1321 1322 if (e->dest != target) 1323 e = redirect_edge_succ_nodup (e, target); 1324 1325 return e; 1326 } 1327 1328 /* Called when edge E has been redirected to a new destination, 1329 in order to update the region crossing flag on the edge and 1330 jump. */ 1331 1332 static void 1333 fixup_partition_crossing (edge e) 1334 { 1335 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || e->dest 1336 == EXIT_BLOCK_PTR_FOR_FN (cfun)) 1337 return; 1338 /* If we redirected an existing edge, it may already be marked 1339 crossing, even though the new src is missing a reg crossing note. 1340 But make sure reg crossing note doesn't already exist before 1341 inserting. */ 1342 if (BB_PARTITION (e->src) != BB_PARTITION (e->dest)) 1343 { 1344 e->flags |= EDGE_CROSSING; 1345 if (JUMP_P (BB_END (e->src))) 1346 CROSSING_JUMP_P (BB_END (e->src)) = 1; 1347 } 1348 else if (BB_PARTITION (e->src) == BB_PARTITION (e->dest)) 1349 { 1350 e->flags &= ~EDGE_CROSSING; 1351 /* Remove the section crossing note from jump at end of 1352 src if it exists, and if no other successors are 1353 still crossing. */ 1354 if (JUMP_P (BB_END (e->src)) && CROSSING_JUMP_P (BB_END (e->src))) 1355 { 1356 bool has_crossing_succ = false; 1357 edge e2; 1358 edge_iterator ei; 1359 FOR_EACH_EDGE (e2, ei, e->src->succs) 1360 { 1361 has_crossing_succ |= (e2->flags & EDGE_CROSSING); 1362 if (has_crossing_succ) 1363 break; 1364 } 1365 if (!has_crossing_succ) 1366 CROSSING_JUMP_P (BB_END (e->src)) = 0; 1367 } 1368 } 1369 } 1370 1371 /* Called when block BB has been reassigned to the cold partition, 1372 because it is now dominated by another cold block, 1373 to ensure that the region crossing attributes are updated. */ 1374 1375 static void 1376 fixup_new_cold_bb (basic_block bb) 1377 { 1378 edge e; 1379 edge_iterator ei; 1380 1381 /* This is called when a hot bb is found to now be dominated 1382 by a cold bb and therefore needs to become cold. Therefore, 1383 its preds will no longer be region crossing. Any non-dominating 1384 preds that were previously hot would also have become cold 1385 in the caller for the same region. Any preds that were previously 1386 region-crossing will be adjusted in fixup_partition_crossing. */ 1387 FOR_EACH_EDGE (e, ei, bb->preds) 1388 { 1389 fixup_partition_crossing (e); 1390 } 1391 1392 /* Possibly need to make bb's successor edges region crossing, 1393 or remove stale region crossing. */ 1394 FOR_EACH_EDGE (e, ei, bb->succs) 1395 { 1396 /* We can't have fall-through edges across partition boundaries. 1397 Note that force_nonfallthru will do any necessary partition 1398 boundary fixup by calling fixup_partition_crossing itself. */ 1399 if ((e->flags & EDGE_FALLTHRU) 1400 && BB_PARTITION (bb) != BB_PARTITION (e->dest) 1401 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) 1402 force_nonfallthru (e); 1403 else 1404 fixup_partition_crossing (e); 1405 } 1406 } 1407 1408 /* Attempt to change code to redirect edge E to TARGET. Don't do that on 1409 expense of adding new instructions or reordering basic blocks. 1410 1411 Function can be also called with edge destination equivalent to the TARGET. 1412 Then it should try the simplifications and do nothing if none is possible. 1413 1414 Return edge representing the branch if transformation succeeded. Return NULL 1415 on failure. 1416 We still return NULL in case E already destinated TARGET and we didn't 1417 managed to simplify instruction stream. */ 1418 1419 static edge 1420 rtl_redirect_edge_and_branch (edge e, basic_block target) 1421 { 1422 edge ret; 1423 basic_block src = e->src; 1424 basic_block dest = e->dest; 1425 1426 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)) 1427 return NULL; 1428 1429 if (dest == target) 1430 return e; 1431 1432 if ((ret = try_redirect_by_replacing_jump (e, target, false)) != NULL) 1433 { 1434 df_set_bb_dirty (src); 1435 fixup_partition_crossing (ret); 1436 return ret; 1437 } 1438 1439 ret = redirect_branch_edge (e, target); 1440 if (!ret) 1441 return NULL; 1442 1443 df_set_bb_dirty (src); 1444 fixup_partition_crossing (ret); 1445 return ret; 1446 } 1447 1448 /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */ 1449 1450 void 1451 emit_barrier_after_bb (basic_block bb) 1452 { 1453 rtx_barrier *barrier = emit_barrier_after (BB_END (bb)); 1454 gcc_assert (current_ir_type () == IR_RTL_CFGRTL 1455 || current_ir_type () == IR_RTL_CFGLAYOUT); 1456 if (current_ir_type () == IR_RTL_CFGLAYOUT) 1457 { 1458 rtx_insn *insn = unlink_insn_chain (barrier, barrier); 1459 1460 if (BB_FOOTER (bb)) 1461 { 1462 rtx_insn *footer_tail = BB_FOOTER (bb); 1463 1464 while (NEXT_INSN (footer_tail)) 1465 footer_tail = NEXT_INSN (footer_tail); 1466 if (!BARRIER_P (footer_tail)) 1467 { 1468 SET_NEXT_INSN (footer_tail) = insn; 1469 SET_PREV_INSN (insn) = footer_tail; 1470 } 1471 } 1472 else 1473 BB_FOOTER (bb) = insn; 1474 } 1475 } 1476 1477 /* Like force_nonfallthru below, but additionally performs redirection 1478 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only 1479 when redirecting to the EXIT_BLOCK, it is either ret_rtx or 1480 simple_return_rtx, indicating which kind of returnjump to create. 1481 It should be NULL otherwise. */ 1482 1483 basic_block 1484 force_nonfallthru_and_redirect (edge e, basic_block target, rtx jump_label) 1485 { 1486 basic_block jump_block, new_bb = NULL, src = e->src; 1487 rtx note; 1488 edge new_edge; 1489 int abnormal_edge_flags = 0; 1490 bool asm_goto_edge = false; 1491 int loc; 1492 1493 /* In the case the last instruction is conditional jump to the next 1494 instruction, first redirect the jump itself and then continue 1495 by creating a basic block afterwards to redirect fallthru edge. */ 1496 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) 1497 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) 1498 && any_condjump_p (BB_END (e->src)) 1499 && JUMP_LABEL (BB_END (e->src)) == BB_HEAD (e->dest)) 1500 { 1501 rtx note; 1502 edge b = unchecked_make_edge (e->src, target, 0); 1503 bool redirected; 1504 1505 redirected = redirect_jump (as_a <rtx_jump_insn *> (BB_END (e->src)), 1506 block_label (target), 0); 1507 gcc_assert (redirected); 1508 1509 note = find_reg_note (BB_END (e->src), REG_BR_PROB, NULL_RTX); 1510 if (note) 1511 { 1512 int prob = XINT (note, 0); 1513 1514 b->probability = profile_probability::from_reg_br_prob_note (prob); 1515 e->probability -= e->probability; 1516 } 1517 } 1518 1519 if (e->flags & EDGE_ABNORMAL) 1520 { 1521 /* Irritating special case - fallthru edge to the same block as abnormal 1522 edge. 1523 We can't redirect abnormal edge, but we still can split the fallthru 1524 one and create separate abnormal edge to original destination. 1525 This allows bb-reorder to make such edge non-fallthru. */ 1526 gcc_assert (e->dest == target); 1527 abnormal_edge_flags = e->flags & ~EDGE_FALLTHRU; 1528 e->flags &= EDGE_FALLTHRU; 1529 } 1530 else 1531 { 1532 gcc_assert (e->flags & EDGE_FALLTHRU); 1533 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)) 1534 { 1535 /* We can't redirect the entry block. Create an empty block 1536 at the start of the function which we use to add the new 1537 jump. */ 1538 edge tmp; 1539 edge_iterator ei; 1540 bool found = false; 1541 1542 basic_block bb = create_basic_block (BB_HEAD (e->dest), NULL, 1543 ENTRY_BLOCK_PTR_FOR_FN (cfun)); 1544 bb->count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count; 1545 1546 /* Make sure new block ends up in correct hot/cold section. */ 1547 BB_COPY_PARTITION (bb, e->dest); 1548 1549 /* Change the existing edge's source to be the new block, and add 1550 a new edge from the entry block to the new block. */ 1551 e->src = bb; 1552 for (ei = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs); 1553 (tmp = ei_safe_edge (ei)); ) 1554 { 1555 if (tmp == e) 1556 { 1557 ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs->unordered_remove (ei.index); 1558 found = true; 1559 break; 1560 } 1561 else 1562 ei_next (&ei); 1563 } 1564 1565 gcc_assert (found); 1566 1567 vec_safe_push (bb->succs, e); 1568 make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), bb, 1569 EDGE_FALLTHRU); 1570 } 1571 } 1572 1573 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs 1574 don't point to the target or fallthru label. */ 1575 if (JUMP_P (BB_END (e->src)) 1576 && target != EXIT_BLOCK_PTR_FOR_FN (cfun) 1577 && (e->flags & EDGE_FALLTHRU) 1578 && (note = extract_asm_operands (PATTERN (BB_END (e->src))))) 1579 { 1580 int i, n = ASM_OPERANDS_LABEL_LENGTH (note); 1581 bool adjust_jump_target = false; 1582 1583 for (i = 0; i < n; ++i) 1584 { 1585 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (e->dest)) 1586 { 1587 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))--; 1588 XEXP (ASM_OPERANDS_LABEL (note, i), 0) = block_label (target); 1589 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))++; 1590 adjust_jump_target = true; 1591 } 1592 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (target)) 1593 asm_goto_edge = true; 1594 } 1595 if (adjust_jump_target) 1596 { 1597 rtx_insn *insn = BB_END (e->src); 1598 rtx note; 1599 rtx_insn *old_label = BB_HEAD (e->dest); 1600 rtx_insn *new_label = BB_HEAD (target); 1601 1602 if (JUMP_LABEL (insn) == old_label) 1603 { 1604 JUMP_LABEL (insn) = new_label; 1605 note = find_reg_note (insn, REG_LABEL_TARGET, new_label); 1606 if (note) 1607 remove_note (insn, note); 1608 } 1609 else 1610 { 1611 note = find_reg_note (insn, REG_LABEL_TARGET, old_label); 1612 if (note) 1613 remove_note (insn, note); 1614 if (JUMP_LABEL (insn) != new_label 1615 && !find_reg_note (insn, REG_LABEL_TARGET, new_label)) 1616 add_reg_note (insn, REG_LABEL_TARGET, new_label); 1617 } 1618 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label)) 1619 != NULL_RTX) 1620 XEXP (note, 0) = new_label; 1621 } 1622 } 1623 1624 if (EDGE_COUNT (e->src->succs) >= 2 || abnormal_edge_flags || asm_goto_edge) 1625 { 1626 rtx_insn *new_head; 1627 profile_count count = e->count (); 1628 profile_probability probability = e->probability; 1629 /* Create the new structures. */ 1630 1631 /* If the old block ended with a tablejump, skip its table 1632 by searching forward from there. Otherwise start searching 1633 forward from the last instruction of the old block. */ 1634 rtx_jump_table_data *table; 1635 if (tablejump_p (BB_END (e->src), NULL, &table)) 1636 new_head = table; 1637 else 1638 new_head = BB_END (e->src); 1639 new_head = NEXT_INSN (new_head); 1640 1641 jump_block = create_basic_block (new_head, NULL, e->src); 1642 jump_block->count = count; 1643 1644 /* Make sure new block ends up in correct hot/cold section. */ 1645 1646 BB_COPY_PARTITION (jump_block, e->src); 1647 1648 /* Wire edge in. */ 1649 new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU); 1650 new_edge->probability = probability; 1651 1652 /* Redirect old edge. */ 1653 redirect_edge_pred (e, jump_block); 1654 e->probability = profile_probability::always (); 1655 1656 /* If e->src was previously region crossing, it no longer is 1657 and the reg crossing note should be removed. */ 1658 fixup_partition_crossing (new_edge); 1659 1660 /* If asm goto has any label refs to target's label, 1661 add also edge from asm goto bb to target. */ 1662 if (asm_goto_edge) 1663 { 1664 new_edge->probability = new_edge->probability.apply_scale (1, 2); 1665 jump_block->count = jump_block->count.apply_scale (1, 2); 1666 edge new_edge2 = make_edge (new_edge->src, target, 1667 e->flags & ~EDGE_FALLTHRU); 1668 new_edge2->probability = probability - new_edge->probability; 1669 } 1670 1671 new_bb = jump_block; 1672 } 1673 else 1674 jump_block = e->src; 1675 1676 loc = e->goto_locus; 1677 e->flags &= ~EDGE_FALLTHRU; 1678 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun)) 1679 { 1680 if (jump_label == ret_rtx) 1681 emit_jump_insn_after_setloc (targetm.gen_return (), 1682 BB_END (jump_block), loc); 1683 else 1684 { 1685 gcc_assert (jump_label == simple_return_rtx); 1686 emit_jump_insn_after_setloc (targetm.gen_simple_return (), 1687 BB_END (jump_block), loc); 1688 } 1689 set_return_jump_label (BB_END (jump_block)); 1690 } 1691 else 1692 { 1693 rtx_code_label *label = block_label (target); 1694 emit_jump_insn_after_setloc (targetm.gen_jump (label), 1695 BB_END (jump_block), loc); 1696 JUMP_LABEL (BB_END (jump_block)) = label; 1697 LABEL_NUSES (label)++; 1698 } 1699 1700 /* We might be in cfg layout mode, and if so, the following routine will 1701 insert the barrier correctly. */ 1702 emit_barrier_after_bb (jump_block); 1703 redirect_edge_succ_nodup (e, target); 1704 1705 if (abnormal_edge_flags) 1706 make_edge (src, target, abnormal_edge_flags); 1707 1708 df_mark_solutions_dirty (); 1709 fixup_partition_crossing (e); 1710 return new_bb; 1711 } 1712 1713 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction 1714 (and possibly create new basic block) to make edge non-fallthru. 1715 Return newly created BB or NULL if none. */ 1716 1717 static basic_block 1718 rtl_force_nonfallthru (edge e) 1719 { 1720 return force_nonfallthru_and_redirect (e, e->dest, NULL_RTX); 1721 } 1722 1723 /* Redirect edge even at the expense of creating new jump insn or 1724 basic block. Return new basic block if created, NULL otherwise. 1725 Conversion must be possible. */ 1726 1727 static basic_block 1728 rtl_redirect_edge_and_branch_force (edge e, basic_block target) 1729 { 1730 if (redirect_edge_and_branch (e, target) 1731 || e->dest == target) 1732 return NULL; 1733 1734 /* In case the edge redirection failed, try to force it to be non-fallthru 1735 and redirect newly created simplejump. */ 1736 df_set_bb_dirty (e->src); 1737 return force_nonfallthru_and_redirect (e, target, NULL_RTX); 1738 } 1739 1740 /* The given edge should potentially be a fallthru edge. If that is in 1741 fact true, delete the jump and barriers that are in the way. */ 1742 1743 static void 1744 rtl_tidy_fallthru_edge (edge e) 1745 { 1746 rtx_insn *q; 1747 basic_block b = e->src, c = b->next_bb; 1748 1749 /* ??? In a late-running flow pass, other folks may have deleted basic 1750 blocks by nopping out blocks, leaving multiple BARRIERs between here 1751 and the target label. They ought to be chastised and fixed. 1752 1753 We can also wind up with a sequence of undeletable labels between 1754 one block and the next. 1755 1756 So search through a sequence of barriers, labels, and notes for 1757 the head of block C and assert that we really do fall through. */ 1758 1759 for (q = NEXT_INSN (BB_END (b)); q != BB_HEAD (c); q = NEXT_INSN (q)) 1760 if (NONDEBUG_INSN_P (q)) 1761 return; 1762 1763 /* Remove what will soon cease being the jump insn from the source block. 1764 If block B consisted only of this single jump, turn it into a deleted 1765 note. */ 1766 q = BB_END (b); 1767 if (JUMP_P (q) 1768 && onlyjump_p (q) 1769 && (any_uncondjump_p (q) 1770 || single_succ_p (b))) 1771 { 1772 rtx_insn *label; 1773 rtx_jump_table_data *table; 1774 1775 if (tablejump_p (q, &label, &table)) 1776 { 1777 /* The label is likely mentioned in some instruction before 1778 the tablejump and might not be DCEd, so turn it into 1779 a note instead and move before the tablejump that is going to 1780 be deleted. */ 1781 const char *name = LABEL_NAME (label); 1782 PUT_CODE (label, NOTE); 1783 NOTE_KIND (label) = NOTE_INSN_DELETED_LABEL; 1784 NOTE_DELETED_LABEL_NAME (label) = name; 1785 reorder_insns (label, label, PREV_INSN (q)); 1786 delete_insn (table); 1787 } 1788 1789 /* If this was a conditional jump, we need to also delete 1790 the insn that set cc0. */ 1791 if (HAVE_cc0 && any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q))) 1792 q = PREV_INSN (q); 1793 1794 q = PREV_INSN (q); 1795 } 1796 /* Unconditional jumps with side-effects (i.e. which we can't just delete 1797 together with the barrier) should never have a fallthru edge. */ 1798 else if (JUMP_P (q) && any_uncondjump_p (q)) 1799 return; 1800 1801 /* Selectively unlink the sequence. */ 1802 if (q != PREV_INSN (BB_HEAD (c))) 1803 delete_insn_chain (NEXT_INSN (q), PREV_INSN (BB_HEAD (c)), false); 1804 1805 e->flags |= EDGE_FALLTHRU; 1806 } 1807 1808 /* Should move basic block BB after basic block AFTER. NIY. */ 1809 1810 static bool 1811 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED, 1812 basic_block after ATTRIBUTE_UNUSED) 1813 { 1814 return false; 1815 } 1816 1817 /* Locate the last bb in the same partition as START_BB. */ 1818 1819 static basic_block 1820 last_bb_in_partition (basic_block start_bb) 1821 { 1822 basic_block bb; 1823 FOR_BB_BETWEEN (bb, start_bb, EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) 1824 { 1825 if (BB_PARTITION (start_bb) != BB_PARTITION (bb->next_bb)) 1826 return bb; 1827 } 1828 /* Return bb before the exit block. */ 1829 return bb->prev_bb; 1830 } 1831 1832 /* Split a (typically critical) edge. Return the new block. 1833 The edge must not be abnormal. 1834 1835 ??? The code generally expects to be called on critical edges. 1836 The case of a block ending in an unconditional jump to a 1837 block with multiple predecessors is not handled optimally. */ 1838 1839 static basic_block 1840 rtl_split_edge (edge edge_in) 1841 { 1842 basic_block bb, new_bb; 1843 rtx_insn *before; 1844 1845 /* Abnormal edges cannot be split. */ 1846 gcc_assert (!(edge_in->flags & EDGE_ABNORMAL)); 1847 1848 /* We are going to place the new block in front of edge destination. 1849 Avoid existence of fallthru predecessors. */ 1850 if ((edge_in->flags & EDGE_FALLTHRU) == 0) 1851 { 1852 edge e = find_fallthru_edge (edge_in->dest->preds); 1853 1854 if (e) 1855 force_nonfallthru (e); 1856 } 1857 1858 /* Create the basic block note. */ 1859 if (edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) 1860 before = BB_HEAD (edge_in->dest); 1861 else 1862 before = NULL; 1863 1864 /* If this is a fall through edge to the exit block, the blocks might be 1865 not adjacent, and the right place is after the source. */ 1866 if ((edge_in->flags & EDGE_FALLTHRU) 1867 && edge_in->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) 1868 { 1869 before = NEXT_INSN (BB_END (edge_in->src)); 1870 bb = create_basic_block (before, NULL, edge_in->src); 1871 BB_COPY_PARTITION (bb, edge_in->src); 1872 } 1873 else 1874 { 1875 if (edge_in->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)) 1876 { 1877 bb = create_basic_block (before, NULL, edge_in->dest->prev_bb); 1878 BB_COPY_PARTITION (bb, edge_in->dest); 1879 } 1880 else 1881 { 1882 basic_block after = edge_in->dest->prev_bb; 1883 /* If this is post-bb reordering, and the edge crosses a partition 1884 boundary, the new block needs to be inserted in the bb chain 1885 at the end of the src partition (since we put the new bb into 1886 that partition, see below). Otherwise we may end up creating 1887 an extra partition crossing in the chain, which is illegal. 1888 It can't go after the src, because src may have a fall-through 1889 to a different block. */ 1890 if (crtl->bb_reorder_complete 1891 && (edge_in->flags & EDGE_CROSSING)) 1892 { 1893 after = last_bb_in_partition (edge_in->src); 1894 before = get_last_bb_insn (after); 1895 /* The instruction following the last bb in partition should 1896 be a barrier, since it cannot end in a fall-through. */ 1897 gcc_checking_assert (BARRIER_P (before)); 1898 before = NEXT_INSN (before); 1899 } 1900 bb = create_basic_block (before, NULL, after); 1901 /* Put the split bb into the src partition, to avoid creating 1902 a situation where a cold bb dominates a hot bb, in the case 1903 where src is cold and dest is hot. The src will dominate 1904 the new bb (whereas it might not have dominated dest). */ 1905 BB_COPY_PARTITION (bb, edge_in->src); 1906 } 1907 } 1908 1909 make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU); 1910 1911 /* Can't allow a region crossing edge to be fallthrough. */ 1912 if (BB_PARTITION (bb) != BB_PARTITION (edge_in->dest) 1913 && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) 1914 { 1915 new_bb = force_nonfallthru (single_succ_edge (bb)); 1916 gcc_assert (!new_bb); 1917 } 1918 1919 /* For non-fallthru edges, we must adjust the predecessor's 1920 jump instruction to target our new block. */ 1921 if ((edge_in->flags & EDGE_FALLTHRU) == 0) 1922 { 1923 edge redirected = redirect_edge_and_branch (edge_in, bb); 1924 gcc_assert (redirected); 1925 } 1926 else 1927 { 1928 if (edge_in->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)) 1929 { 1930 /* For asm goto even splitting of fallthru edge might 1931 need insn patching, as other labels might point to the 1932 old label. */ 1933 rtx_insn *last = BB_END (edge_in->src); 1934 if (last 1935 && JUMP_P (last) 1936 && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) 1937 && (extract_asm_operands (PATTERN (last)) 1938 || JUMP_LABEL (last) == before) 1939 && patch_jump_insn (last, before, bb)) 1940 df_set_bb_dirty (edge_in->src); 1941 } 1942 redirect_edge_succ (edge_in, bb); 1943 } 1944 1945 return bb; 1946 } 1947 1948 /* Queue instructions for insertion on an edge between two basic blocks. 1949 The new instructions and basic blocks (if any) will not appear in the 1950 CFG until commit_edge_insertions is called. */ 1951 1952 void 1953 insert_insn_on_edge (rtx pattern, edge e) 1954 { 1955 /* We cannot insert instructions on an abnormal critical edge. 1956 It will be easier to find the culprit if we die now. */ 1957 gcc_assert (!((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))); 1958 1959 if (e->insns.r == NULL_RTX) 1960 start_sequence (); 1961 else 1962 push_to_sequence (e->insns.r); 1963 1964 emit_insn (pattern); 1965 1966 e->insns.r = get_insns (); 1967 end_sequence (); 1968 } 1969 1970 /* Update the CFG for the instructions queued on edge E. */ 1971 1972 void 1973 commit_one_edge_insertion (edge e) 1974 { 1975 rtx_insn *before = NULL, *after = NULL, *insns, *tmp, *last; 1976 basic_block bb; 1977 1978 /* Pull the insns off the edge now since the edge might go away. */ 1979 insns = e->insns.r; 1980 e->insns.r = NULL; 1981 1982 /* Figure out where to put these insns. If the destination has 1983 one predecessor, insert there. Except for the exit block. */ 1984 if (single_pred_p (e->dest) && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) 1985 { 1986 bb = e->dest; 1987 1988 /* Get the location correct wrt a code label, and "nice" wrt 1989 a basic block note, and before everything else. */ 1990 tmp = BB_HEAD (bb); 1991 if (LABEL_P (tmp)) 1992 tmp = NEXT_INSN (tmp); 1993 if (NOTE_INSN_BASIC_BLOCK_P (tmp)) 1994 tmp = NEXT_INSN (tmp); 1995 if (tmp == BB_HEAD (bb)) 1996 before = tmp; 1997 else if (tmp) 1998 after = PREV_INSN (tmp); 1999 else 2000 after = get_last_insn (); 2001 } 2002 2003 /* If the source has one successor and the edge is not abnormal, 2004 insert there. Except for the entry block. 2005 Don't do this if the predecessor ends in a jump other than 2006 unconditional simple jump. E.g. for asm goto that points all 2007 its labels at the fallthru basic block, we can't insert instructions 2008 before the asm goto, as the asm goto can have various of side effects, 2009 and can't emit instructions after the asm goto, as it must end 2010 the basic block. */ 2011 else if ((e->flags & EDGE_ABNORMAL) == 0 2012 && single_succ_p (e->src) 2013 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) 2014 && (!JUMP_P (BB_END (e->src)) 2015 || simplejump_p (BB_END (e->src)))) 2016 { 2017 bb = e->src; 2018 2019 /* It is possible to have a non-simple jump here. Consider a target 2020 where some forms of unconditional jumps clobber a register. This 2021 happens on the fr30 for example. 2022 2023 We know this block has a single successor, so we can just emit 2024 the queued insns before the jump. */ 2025 if (JUMP_P (BB_END (bb))) 2026 before = BB_END (bb); 2027 else 2028 { 2029 /* We'd better be fallthru, or we've lost track of what's what. */ 2030 gcc_assert (e->flags & EDGE_FALLTHRU); 2031 2032 after = BB_END (bb); 2033 } 2034 } 2035 2036 /* Otherwise we must split the edge. */ 2037 else 2038 { 2039 bb = split_edge (e); 2040 2041 /* If E crossed a partition boundary, we needed to make bb end in 2042 a region-crossing jump, even though it was originally fallthru. */ 2043 if (JUMP_P (BB_END (bb))) 2044 before = BB_END (bb); 2045 else 2046 after = BB_END (bb); 2047 } 2048 2049 /* Now that we've found the spot, do the insertion. */ 2050 if (before) 2051 { 2052 emit_insn_before_noloc (insns, before, bb); 2053 last = prev_nonnote_insn (before); 2054 } 2055 else 2056 last = emit_insn_after_noloc (insns, after, bb); 2057 2058 if (returnjump_p (last)) 2059 { 2060 /* ??? Remove all outgoing edges from BB and add one for EXIT. 2061 This is not currently a problem because this only happens 2062 for the (single) epilogue, which already has a fallthru edge 2063 to EXIT. */ 2064 2065 e = single_succ_edge (bb); 2066 gcc_assert (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun) 2067 && single_succ_p (bb) && (e->flags & EDGE_FALLTHRU)); 2068 2069 e->flags &= ~EDGE_FALLTHRU; 2070 emit_barrier_after (last); 2071 2072 if (before) 2073 delete_insn (before); 2074 } 2075 else 2076 gcc_assert (!JUMP_P (last)); 2077 } 2078 2079 /* Update the CFG for all queued instructions. */ 2080 2081 void 2082 commit_edge_insertions (void) 2083 { 2084 basic_block bb; 2085 2086 /* Optimization passes that invoke this routine can cause hot blocks 2087 previously reached by both hot and cold blocks to become dominated only 2088 by cold blocks. This will cause the verification below to fail, 2089 and lead to now cold code in the hot section. In some cases this 2090 may only be visible after newly unreachable blocks are deleted, 2091 which will be done by fixup_partitions. */ 2092 fixup_partitions (); 2093 2094 checking_verify_flow_info (); 2095 2096 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), 2097 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) 2098 { 2099 edge e; 2100 edge_iterator ei; 2101 2102 FOR_EACH_EDGE (e, ei, bb->succs) 2103 if (e->insns.r) 2104 commit_one_edge_insertion (e); 2105 } 2106 } 2107 2108 2109 /* Print out RTL-specific basic block information (live information 2110 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks 2111 documented in dumpfile.h. */ 2112 2113 static void 2114 rtl_dump_bb (FILE *outf, basic_block bb, int indent, dump_flags_t flags) 2115 { 2116 char *s_indent; 2117 2118 s_indent = (char *) alloca ((size_t) indent + 1); 2119 memset (s_indent, ' ', (size_t) indent); 2120 s_indent[indent] = '\0'; 2121 2122 if (df && (flags & TDF_DETAILS)) 2123 { 2124 df_dump_top (bb, outf); 2125 putc ('\n', outf); 2126 } 2127 2128 if (bb->index != ENTRY_BLOCK && bb->index != EXIT_BLOCK) 2129 { 2130 rtx_insn *last = BB_END (bb); 2131 if (last) 2132 last = NEXT_INSN (last); 2133 for (rtx_insn *insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn)) 2134 { 2135 if (flags & TDF_DETAILS) 2136 df_dump_insn_top (insn, outf); 2137 if (! (flags & TDF_SLIM)) 2138 print_rtl_single (outf, insn); 2139 else 2140 dump_insn_slim (outf, insn); 2141 if (flags & TDF_DETAILS) 2142 df_dump_insn_bottom (insn, outf); 2143 } 2144 } 2145 2146 if (df && (flags & TDF_DETAILS)) 2147 { 2148 df_dump_bottom (bb, outf); 2149 putc ('\n', outf); 2150 } 2151 2152 } 2153 2154 /* Like dump_function_to_file, but for RTL. Print out dataflow information 2155 for the start of each basic block. FLAGS are the TDF_* masks documented 2156 in dumpfile.h. */ 2157 2158 void 2159 print_rtl_with_bb (FILE *outf, const rtx_insn *rtx_first, dump_flags_t flags) 2160 { 2161 const rtx_insn *tmp_rtx; 2162 if (rtx_first == 0) 2163 fprintf (outf, "(nil)\n"); 2164 else 2165 { 2166 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB }; 2167 int max_uid = get_max_uid (); 2168 basic_block *start = XCNEWVEC (basic_block, max_uid); 2169 basic_block *end = XCNEWVEC (basic_block, max_uid); 2170 enum bb_state *in_bb_p = XCNEWVEC (enum bb_state, max_uid); 2171 basic_block bb; 2172 2173 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most 2174 insns, but the CFG is not maintained so the basic block info 2175 is not reliable. Therefore it's omitted from the dumps. */ 2176 if (! (cfun->curr_properties & PROP_cfg)) 2177 flags &= ~TDF_BLOCKS; 2178 2179 if (df) 2180 df_dump_start (outf); 2181 2182 if (flags & TDF_BLOCKS) 2183 { 2184 FOR_EACH_BB_REVERSE_FN (bb, cfun) 2185 { 2186 rtx_insn *x; 2187 2188 start[INSN_UID (BB_HEAD (bb))] = bb; 2189 end[INSN_UID (BB_END (bb))] = bb; 2190 for (x = BB_HEAD (bb); x != NULL_RTX; x = NEXT_INSN (x)) 2191 { 2192 enum bb_state state = IN_MULTIPLE_BB; 2193 2194 if (in_bb_p[INSN_UID (x)] == NOT_IN_BB) 2195 state = IN_ONE_BB; 2196 in_bb_p[INSN_UID (x)] = state; 2197 2198 if (x == BB_END (bb)) 2199 break; 2200 } 2201 } 2202 } 2203 2204 for (tmp_rtx = rtx_first; tmp_rtx != NULL; tmp_rtx = NEXT_INSN (tmp_rtx)) 2205 { 2206 if (flags & TDF_BLOCKS) 2207 { 2208 bb = start[INSN_UID (tmp_rtx)]; 2209 if (bb != NULL) 2210 { 2211 dump_bb_info (outf, bb, 0, dump_flags, true, false); 2212 if (df && (flags & TDF_DETAILS)) 2213 df_dump_top (bb, outf); 2214 } 2215 2216 if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB 2217 && !NOTE_P (tmp_rtx) 2218 && !BARRIER_P (tmp_rtx)) 2219 fprintf (outf, ";; Insn is not within a basic block\n"); 2220 else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB) 2221 fprintf (outf, ";; Insn is in multiple basic blocks\n"); 2222 } 2223 2224 if (flags & TDF_DETAILS) 2225 df_dump_insn_top (tmp_rtx, outf); 2226 if (! (flags & TDF_SLIM)) 2227 print_rtl_single (outf, tmp_rtx); 2228 else 2229 dump_insn_slim (outf, tmp_rtx); 2230 if (flags & TDF_DETAILS) 2231 df_dump_insn_bottom (tmp_rtx, outf); 2232 2233 if (flags & TDF_BLOCKS) 2234 { 2235 bb = end[INSN_UID (tmp_rtx)]; 2236 if (bb != NULL) 2237 { 2238 dump_bb_info (outf, bb, 0, dump_flags, false, true); 2239 if (df && (flags & TDF_DETAILS)) 2240 df_dump_bottom (bb, outf); 2241 putc ('\n', outf); 2242 } 2243 } 2244 } 2245 2246 free (start); 2247 free (end); 2248 free (in_bb_p); 2249 } 2250 } 2251 2252 /* Update the branch probability of BB if a REG_BR_PROB is present. */ 2253 2254 void 2255 update_br_prob_note (basic_block bb) 2256 { 2257 rtx note; 2258 note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX); 2259 if (!JUMP_P (BB_END (bb)) || !BRANCH_EDGE (bb)->probability.initialized_p ()) 2260 { 2261 if (note) 2262 { 2263 rtx *note_link, this_rtx; 2264 2265 note_link = ®_NOTES (BB_END (bb)); 2266 for (this_rtx = *note_link; this_rtx; this_rtx = XEXP (this_rtx, 1)) 2267 if (this_rtx == note) 2268 { 2269 *note_link = XEXP (this_rtx, 1); 2270 break; 2271 } 2272 } 2273 return; 2274 } 2275 if (!note 2276 || XINT (note, 0) == BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ()) 2277 return; 2278 XINT (note, 0) = BRANCH_EDGE (bb)->probability.to_reg_br_prob_note (); 2279 } 2280 2281 /* Get the last insn associated with block BB (that includes barriers and 2282 tablejumps after BB). */ 2283 rtx_insn * 2284 get_last_bb_insn (basic_block bb) 2285 { 2286 rtx_jump_table_data *table; 2287 rtx_insn *tmp; 2288 rtx_insn *end = BB_END (bb); 2289 2290 /* Include any jump table following the basic block. */ 2291 if (tablejump_p (end, NULL, &table)) 2292 end = table; 2293 2294 /* Include any barriers that may follow the basic block. */ 2295 tmp = next_nonnote_nondebug_insn_bb (end); 2296 while (tmp && BARRIER_P (tmp)) 2297 { 2298 end = tmp; 2299 tmp = next_nonnote_nondebug_insn_bb (end); 2300 } 2301 2302 return end; 2303 } 2304 2305 /* Add all BBs reachable from entry via hot paths into the SET. */ 2306 2307 void 2308 find_bbs_reachable_by_hot_paths (hash_set<basic_block> *set) 2309 { 2310 auto_vec<basic_block, 64> worklist; 2311 2312 set->add (ENTRY_BLOCK_PTR_FOR_FN (cfun)); 2313 worklist.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun)); 2314 2315 while (worklist.length () > 0) 2316 { 2317 basic_block bb = worklist.pop (); 2318 edge_iterator ei; 2319 edge e; 2320 2321 FOR_EACH_EDGE (e, ei, bb->succs) 2322 if (BB_PARTITION (e->dest) != BB_COLD_PARTITION 2323 && !set->add (e->dest)) 2324 worklist.safe_push (e->dest); 2325 } 2326 } 2327 2328 /* Sanity check partition hotness to ensure that basic blocks in 2329 the cold partition don't dominate basic blocks in the hot partition. 2330 If FLAG_ONLY is true, report violations as errors. Otherwise 2331 re-mark the dominated blocks as cold, since this is run after 2332 cfg optimizations that may make hot blocks previously reached 2333 by both hot and cold blocks now only reachable along cold paths. */ 2334 2335 static vec<basic_block> 2336 find_partition_fixes (bool flag_only) 2337 { 2338 basic_block bb; 2339 vec<basic_block> bbs_in_cold_partition = vNULL; 2340 vec<basic_block> bbs_to_fix = vNULL; 2341 hash_set<basic_block> set; 2342 2343 /* Callers check this. */ 2344 gcc_checking_assert (crtl->has_bb_partition); 2345 2346 find_bbs_reachable_by_hot_paths (&set); 2347 2348 FOR_EACH_BB_FN (bb, cfun) 2349 if (!set.contains (bb) 2350 && BB_PARTITION (bb) != BB_COLD_PARTITION) 2351 { 2352 if (flag_only) 2353 error ("non-cold basic block %d reachable only " 2354 "by paths crossing the cold partition", bb->index); 2355 else 2356 BB_SET_PARTITION (bb, BB_COLD_PARTITION); 2357 bbs_to_fix.safe_push (bb); 2358 bbs_in_cold_partition.safe_push (bb); 2359 } 2360 2361 return bbs_to_fix; 2362 } 2363 2364 /* Perform cleanup on the hot/cold bb partitioning after optimization 2365 passes that modify the cfg. */ 2366 2367 void 2368 fixup_partitions (void) 2369 { 2370 basic_block bb; 2371 2372 if (!crtl->has_bb_partition) 2373 return; 2374 2375 /* Delete any blocks that became unreachable and weren't 2376 already cleaned up, for example during edge forwarding 2377 and convert_jumps_to_returns. This will expose more 2378 opportunities for fixing the partition boundaries here. 2379 Also, the calculation of the dominance graph during verification 2380 will assert if there are unreachable nodes. */ 2381 delete_unreachable_blocks (); 2382 2383 /* If there are partitions, do a sanity check on them: A basic block in 2384 a cold partition cannot dominate a basic block in a hot partition. 2385 Fixup any that now violate this requirement, as a result of edge 2386 forwarding and unreachable block deletion. */ 2387 vec<basic_block> bbs_to_fix = find_partition_fixes (false); 2388 2389 /* Do the partition fixup after all necessary blocks have been converted to 2390 cold, so that we only update the region crossings the minimum number of 2391 places, which can require forcing edges to be non fallthru. */ 2392 while (! bbs_to_fix.is_empty ()) 2393 { 2394 bb = bbs_to_fix.pop (); 2395 fixup_new_cold_bb (bb); 2396 } 2397 } 2398 2399 /* Verify, in the basic block chain, that there is at most one switch 2400 between hot/cold partitions. This condition will not be true until 2401 after reorder_basic_blocks is called. */ 2402 2403 static int 2404 verify_hot_cold_block_grouping (void) 2405 { 2406 basic_block bb; 2407 int err = 0; 2408 bool switched_sections = false; 2409 int current_partition = BB_UNPARTITIONED; 2410 2411 /* Even after bb reordering is complete, we go into cfglayout mode 2412 again (in compgoto). Ensure we don't call this before going back 2413 into linearized RTL when any layout fixes would have been committed. */ 2414 if (!crtl->bb_reorder_complete 2415 || current_ir_type () != IR_RTL_CFGRTL) 2416 return err; 2417 2418 FOR_EACH_BB_FN (bb, cfun) 2419 { 2420 if (current_partition != BB_UNPARTITIONED 2421 && BB_PARTITION (bb) != current_partition) 2422 { 2423 if (switched_sections) 2424 { 2425 error ("multiple hot/cold transitions found (bb %i)", 2426 bb->index); 2427 err = 1; 2428 } 2429 else 2430 switched_sections = true; 2431 2432 if (!crtl->has_bb_partition) 2433 error ("partition found but function partition flag not set"); 2434 } 2435 current_partition = BB_PARTITION (bb); 2436 } 2437 2438 return err; 2439 } 2440 2441 2442 /* Perform several checks on the edges out of each block, such as 2443 the consistency of the branch probabilities, the correctness 2444 of hot/cold partition crossing edges, and the number of expected 2445 successor edges. Also verify that the dominance relationship 2446 between hot/cold blocks is sane. */ 2447 2448 static int 2449 rtl_verify_edges (void) 2450 { 2451 int err = 0; 2452 basic_block bb; 2453 2454 FOR_EACH_BB_REVERSE_FN (bb, cfun) 2455 { 2456 int n_fallthru = 0, n_branch = 0, n_abnormal_call = 0, n_sibcall = 0; 2457 int n_eh = 0, n_abnormal = 0; 2458 edge e, fallthru = NULL; 2459 edge_iterator ei; 2460 rtx note; 2461 bool has_crossing_edge = false; 2462 2463 if (JUMP_P (BB_END (bb)) 2464 && (note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX)) 2465 && EDGE_COUNT (bb->succs) >= 2 2466 && any_condjump_p (BB_END (bb))) 2467 { 2468 if (!BRANCH_EDGE (bb)->probability.initialized_p ()) 2469 { 2470 if (profile_status_for_fn (cfun) != PROFILE_ABSENT) 2471 { 2472 error ("verify_flow_info: " 2473 "REG_BR_PROB is set but cfg probability is not"); 2474 err = 1; 2475 } 2476 } 2477 else if (XINT (note, 0) 2478 != BRANCH_EDGE (bb)->probability.to_reg_br_prob_note () 2479 && profile_status_for_fn (cfun) != PROFILE_ABSENT) 2480 { 2481 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i", 2482 XINT (note, 0), 2483 BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ()); 2484 err = 1; 2485 } 2486 } 2487 2488 FOR_EACH_EDGE (e, ei, bb->succs) 2489 { 2490 bool is_crossing; 2491 2492 if (e->flags & EDGE_FALLTHRU) 2493 n_fallthru++, fallthru = e; 2494 2495 is_crossing = (BB_PARTITION (e->src) != BB_PARTITION (e->dest) 2496 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) 2497 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)); 2498 has_crossing_edge |= is_crossing; 2499 if (e->flags & EDGE_CROSSING) 2500 { 2501 if (!is_crossing) 2502 { 2503 error ("EDGE_CROSSING incorrectly set across same section"); 2504 err = 1; 2505 } 2506 if (e->flags & EDGE_FALLTHRU) 2507 { 2508 error ("fallthru edge crosses section boundary in bb %i", 2509 e->src->index); 2510 err = 1; 2511 } 2512 if (e->flags & EDGE_EH) 2513 { 2514 error ("EH edge crosses section boundary in bb %i", 2515 e->src->index); 2516 err = 1; 2517 } 2518 if (JUMP_P (BB_END (bb)) && !CROSSING_JUMP_P (BB_END (bb))) 2519 { 2520 error ("No region crossing jump at section boundary in bb %i", 2521 bb->index); 2522 err = 1; 2523 } 2524 } 2525 else if (is_crossing) 2526 { 2527 error ("EDGE_CROSSING missing across section boundary"); 2528 err = 1; 2529 } 2530 2531 if ((e->flags & ~(EDGE_DFS_BACK 2532 | EDGE_CAN_FALLTHRU 2533 | EDGE_IRREDUCIBLE_LOOP 2534 | EDGE_LOOP_EXIT 2535 | EDGE_CROSSING 2536 | EDGE_PRESERVE)) == 0) 2537 n_branch++; 2538 2539 if (e->flags & EDGE_ABNORMAL_CALL) 2540 n_abnormal_call++; 2541 2542 if (e->flags & EDGE_SIBCALL) 2543 n_sibcall++; 2544 2545 if (e->flags & EDGE_EH) 2546 n_eh++; 2547 2548 if (e->flags & EDGE_ABNORMAL) 2549 n_abnormal++; 2550 } 2551 2552 if (!has_crossing_edge 2553 && JUMP_P (BB_END (bb)) 2554 && CROSSING_JUMP_P (BB_END (bb))) 2555 { 2556 print_rtl_with_bb (stderr, get_insns (), TDF_BLOCKS | TDF_DETAILS); 2557 error ("Region crossing jump across same section in bb %i", 2558 bb->index); 2559 err = 1; 2560 } 2561 2562 if (n_eh && !find_reg_note (BB_END (bb), REG_EH_REGION, NULL_RTX)) 2563 { 2564 error ("missing REG_EH_REGION note at the end of bb %i", bb->index); 2565 err = 1; 2566 } 2567 if (n_eh > 1) 2568 { 2569 error ("too many exception handling edges in bb %i", bb->index); 2570 err = 1; 2571 } 2572 if (n_branch 2573 && (!JUMP_P (BB_END (bb)) 2574 || (n_branch > 1 && (any_uncondjump_p (BB_END (bb)) 2575 || any_condjump_p (BB_END (bb)))))) 2576 { 2577 error ("too many outgoing branch edges from bb %i", bb->index); 2578 err = 1; 2579 } 2580 if (n_fallthru && any_uncondjump_p (BB_END (bb))) 2581 { 2582 error ("fallthru edge after unconditional jump in bb %i", bb->index); 2583 err = 1; 2584 } 2585 if (n_branch != 1 && any_uncondjump_p (BB_END (bb))) 2586 { 2587 error ("wrong number of branch edges after unconditional jump" 2588 " in bb %i", bb->index); 2589 err = 1; 2590 } 2591 if (n_branch != 1 && any_condjump_p (BB_END (bb)) 2592 && JUMP_LABEL (BB_END (bb)) != BB_HEAD (fallthru->dest)) 2593 { 2594 error ("wrong amount of branch edges after conditional jump" 2595 " in bb %i", bb->index); 2596 err = 1; 2597 } 2598 if (n_abnormal_call && !CALL_P (BB_END (bb))) 2599 { 2600 error ("abnormal call edges for non-call insn in bb %i", bb->index); 2601 err = 1; 2602 } 2603 if (n_sibcall && !CALL_P (BB_END (bb))) 2604 { 2605 error ("sibcall edges for non-call insn in bb %i", bb->index); 2606 err = 1; 2607 } 2608 if (n_abnormal > n_eh 2609 && !(CALL_P (BB_END (bb)) 2610 && n_abnormal == n_abnormal_call + n_sibcall) 2611 && (!JUMP_P (BB_END (bb)) 2612 || any_condjump_p (BB_END (bb)) 2613 || any_uncondjump_p (BB_END (bb)))) 2614 { 2615 error ("abnormal edges for no purpose in bb %i", bb->index); 2616 err = 1; 2617 } 2618 } 2619 2620 /* If there are partitions, do a sanity check on them: A basic block in 2621 a cold partition cannot dominate a basic block in a hot partition. */ 2622 if (crtl->has_bb_partition && !err 2623 && current_ir_type () == IR_RTL_CFGLAYOUT) 2624 { 2625 vec<basic_block> bbs_to_fix = find_partition_fixes (true); 2626 err = !bbs_to_fix.is_empty (); 2627 } 2628 2629 /* Clean up. */ 2630 return err; 2631 } 2632 2633 /* Checks on the instructions within blocks. Currently checks that each 2634 block starts with a basic block note, and that basic block notes and 2635 control flow jumps are not found in the middle of the block. */ 2636 2637 static int 2638 rtl_verify_bb_insns (void) 2639 { 2640 rtx_insn *x; 2641 int err = 0; 2642 basic_block bb; 2643 2644 FOR_EACH_BB_REVERSE_FN (bb, cfun) 2645 { 2646 /* Now check the header of basic 2647 block. It ought to contain optional CODE_LABEL followed 2648 by NOTE_BASIC_BLOCK. */ 2649 x = BB_HEAD (bb); 2650 if (LABEL_P (x)) 2651 { 2652 if (BB_END (bb) == x) 2653 { 2654 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d", 2655 bb->index); 2656 err = 1; 2657 } 2658 2659 x = NEXT_INSN (x); 2660 } 2661 2662 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb) 2663 { 2664 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d", 2665 bb->index); 2666 err = 1; 2667 } 2668 2669 if (BB_END (bb) == x) 2670 /* Do checks for empty blocks here. */ 2671 ; 2672 else 2673 for (x = NEXT_INSN (x); x; x = NEXT_INSN (x)) 2674 { 2675 if (NOTE_INSN_BASIC_BLOCK_P (x)) 2676 { 2677 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d", 2678 INSN_UID (x), bb->index); 2679 err = 1; 2680 } 2681 2682 if (x == BB_END (bb)) 2683 break; 2684 2685 if (control_flow_insn_p (x)) 2686 { 2687 error ("in basic block %d:", bb->index); 2688 fatal_insn ("flow control insn inside a basic block", x); 2689 } 2690 } 2691 } 2692 2693 /* Clean up. */ 2694 return err; 2695 } 2696 2697 /* Verify that block pointers for instructions in basic blocks, headers and 2698 footers are set appropriately. */ 2699 2700 static int 2701 rtl_verify_bb_pointers (void) 2702 { 2703 int err = 0; 2704 basic_block bb; 2705 2706 /* Check the general integrity of the basic blocks. */ 2707 FOR_EACH_BB_REVERSE_FN (bb, cfun) 2708 { 2709 rtx_insn *insn; 2710 2711 if (!(bb->flags & BB_RTL)) 2712 { 2713 error ("BB_RTL flag not set for block %d", bb->index); 2714 err = 1; 2715 } 2716 2717 FOR_BB_INSNS (bb, insn) 2718 if (BLOCK_FOR_INSN (insn) != bb) 2719 { 2720 error ("insn %d basic block pointer is %d, should be %d", 2721 INSN_UID (insn), 2722 BLOCK_FOR_INSN (insn) ? BLOCK_FOR_INSN (insn)->index : 0, 2723 bb->index); 2724 err = 1; 2725 } 2726 2727 for (insn = BB_HEADER (bb); insn; insn = NEXT_INSN (insn)) 2728 if (!BARRIER_P (insn) 2729 && BLOCK_FOR_INSN (insn) != NULL) 2730 { 2731 error ("insn %d in header of bb %d has non-NULL basic block", 2732 INSN_UID (insn), bb->index); 2733 err = 1; 2734 } 2735 for (insn = BB_FOOTER (bb); insn; insn = NEXT_INSN (insn)) 2736 if (!BARRIER_P (insn) 2737 && BLOCK_FOR_INSN (insn) != NULL) 2738 { 2739 error ("insn %d in footer of bb %d has non-NULL basic block", 2740 INSN_UID (insn), bb->index); 2741 err = 1; 2742 } 2743 } 2744 2745 /* Clean up. */ 2746 return err; 2747 } 2748 2749 /* Verify the CFG and RTL consistency common for both underlying RTL and 2750 cfglayout RTL. 2751 2752 Currently it does following checks: 2753 2754 - overlapping of basic blocks 2755 - insns with wrong BLOCK_FOR_INSN pointers 2756 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note) 2757 - tails of basic blocks (ensure that boundary is necessary) 2758 - scans body of the basic block for JUMP_INSN, CODE_LABEL 2759 and NOTE_INSN_BASIC_BLOCK 2760 - verify that no fall_thru edge crosses hot/cold partition boundaries 2761 - verify that there are no pending RTL branch predictions 2762 - verify that hot blocks are not dominated by cold blocks 2763 2764 In future it can be extended check a lot of other stuff as well 2765 (reachability of basic blocks, life information, etc. etc.). */ 2766 2767 static int 2768 rtl_verify_flow_info_1 (void) 2769 { 2770 int err = 0; 2771 2772 err |= rtl_verify_bb_pointers (); 2773 2774 err |= rtl_verify_bb_insns (); 2775 2776 err |= rtl_verify_edges (); 2777 2778 return err; 2779 } 2780 2781 /* Walk the instruction chain and verify that bb head/end pointers 2782 are correct, and that instructions are in exactly one bb and have 2783 correct block pointers. */ 2784 2785 static int 2786 rtl_verify_bb_insn_chain (void) 2787 { 2788 basic_block bb; 2789 int err = 0; 2790 rtx_insn *x; 2791 rtx_insn *last_head = get_last_insn (); 2792 basic_block *bb_info; 2793 const int max_uid = get_max_uid (); 2794 2795 bb_info = XCNEWVEC (basic_block, max_uid); 2796 2797 FOR_EACH_BB_REVERSE_FN (bb, cfun) 2798 { 2799 rtx_insn *head = BB_HEAD (bb); 2800 rtx_insn *end = BB_END (bb); 2801 2802 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x)) 2803 { 2804 /* Verify the end of the basic block is in the INSN chain. */ 2805 if (x == end) 2806 break; 2807 2808 /* And that the code outside of basic blocks has NULL bb field. */ 2809 if (!BARRIER_P (x) 2810 && BLOCK_FOR_INSN (x) != NULL) 2811 { 2812 error ("insn %d outside of basic blocks has non-NULL bb field", 2813 INSN_UID (x)); 2814 err = 1; 2815 } 2816 } 2817 2818 if (!x) 2819 { 2820 error ("end insn %d for block %d not found in the insn stream", 2821 INSN_UID (end), bb->index); 2822 err = 1; 2823 } 2824 2825 /* Work backwards from the end to the head of the basic block 2826 to verify the head is in the RTL chain. */ 2827 for (; x != NULL_RTX; x = PREV_INSN (x)) 2828 { 2829 /* While walking over the insn chain, verify insns appear 2830 in only one basic block. */ 2831 if (bb_info[INSN_UID (x)] != NULL) 2832 { 2833 error ("insn %d is in multiple basic blocks (%d and %d)", 2834 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index); 2835 err = 1; 2836 } 2837 2838 bb_info[INSN_UID (x)] = bb; 2839 2840 if (x == head) 2841 break; 2842 } 2843 if (!x) 2844 { 2845 error ("head insn %d for block %d not found in the insn stream", 2846 INSN_UID (head), bb->index); 2847 err = 1; 2848 } 2849 2850 last_head = PREV_INSN (x); 2851 } 2852 2853 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x)) 2854 { 2855 /* Check that the code before the first basic block has NULL 2856 bb field. */ 2857 if (!BARRIER_P (x) 2858 && BLOCK_FOR_INSN (x) != NULL) 2859 { 2860 error ("insn %d outside of basic blocks has non-NULL bb field", 2861 INSN_UID (x)); 2862 err = 1; 2863 } 2864 } 2865 free (bb_info); 2866 2867 return err; 2868 } 2869 2870 /* Verify that fallthru edges point to adjacent blocks in layout order and 2871 that barriers exist after non-fallthru blocks. */ 2872 2873 static int 2874 rtl_verify_fallthru (void) 2875 { 2876 basic_block bb; 2877 int err = 0; 2878 2879 FOR_EACH_BB_REVERSE_FN (bb, cfun) 2880 { 2881 edge e; 2882 2883 e = find_fallthru_edge (bb->succs); 2884 if (!e) 2885 { 2886 rtx_insn *insn; 2887 2888 /* Ensure existence of barrier in BB with no fallthru edges. */ 2889 for (insn = NEXT_INSN (BB_END (bb)); ; insn = NEXT_INSN (insn)) 2890 { 2891 if (!insn || NOTE_INSN_BASIC_BLOCK_P (insn)) 2892 { 2893 error ("missing barrier after block %i", bb->index); 2894 err = 1; 2895 break; 2896 } 2897 if (BARRIER_P (insn)) 2898 break; 2899 } 2900 } 2901 else if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) 2902 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) 2903 { 2904 rtx_insn *insn; 2905 2906 if (e->src->next_bb != e->dest) 2907 { 2908 error 2909 ("verify_flow_info: Incorrect blocks for fallthru %i->%i", 2910 e->src->index, e->dest->index); 2911 err = 1; 2912 } 2913 else 2914 for (insn = NEXT_INSN (BB_END (e->src)); insn != BB_HEAD (e->dest); 2915 insn = NEXT_INSN (insn)) 2916 if (BARRIER_P (insn) || NONDEBUG_INSN_P (insn)) 2917 { 2918 error ("verify_flow_info: Incorrect fallthru %i->%i", 2919 e->src->index, e->dest->index); 2920 fatal_insn ("wrong insn in the fallthru edge", insn); 2921 err = 1; 2922 } 2923 } 2924 } 2925 2926 return err; 2927 } 2928 2929 /* Verify that blocks are laid out in consecutive order. While walking the 2930 instructions, verify that all expected instructions are inside the basic 2931 blocks, and that all returns are followed by barriers. */ 2932 2933 static int 2934 rtl_verify_bb_layout (void) 2935 { 2936 basic_block bb; 2937 int err = 0; 2938 rtx_insn *x, *y; 2939 int num_bb_notes; 2940 rtx_insn * const rtx_first = get_insns (); 2941 basic_block last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun), curr_bb = NULL; 2942 2943 num_bb_notes = 0; 2944 last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun); 2945 2946 for (x = rtx_first; x; x = NEXT_INSN (x)) 2947 { 2948 if (NOTE_INSN_BASIC_BLOCK_P (x)) 2949 { 2950 bb = NOTE_BASIC_BLOCK (x); 2951 2952 num_bb_notes++; 2953 if (bb != last_bb_seen->next_bb) 2954 internal_error ("basic blocks not laid down consecutively"); 2955 2956 curr_bb = last_bb_seen = bb; 2957 } 2958 2959 if (!curr_bb) 2960 { 2961 switch (GET_CODE (x)) 2962 { 2963 case BARRIER: 2964 case NOTE: 2965 break; 2966 2967 case CODE_LABEL: 2968 /* An ADDR_VEC is placed outside any basic block. */ 2969 if (NEXT_INSN (x) 2970 && JUMP_TABLE_DATA_P (NEXT_INSN (x))) 2971 x = NEXT_INSN (x); 2972 2973 /* But in any case, non-deletable labels can appear anywhere. */ 2974 break; 2975 2976 default: 2977 fatal_insn ("insn outside basic block", x); 2978 } 2979 } 2980 2981 if (JUMP_P (x) 2982 && returnjump_p (x) && ! condjump_p (x) 2983 && ! ((y = next_nonnote_nondebug_insn (x)) 2984 && BARRIER_P (y))) 2985 fatal_insn ("return not followed by barrier", x); 2986 2987 if (curr_bb && x == BB_END (curr_bb)) 2988 curr_bb = NULL; 2989 } 2990 2991 if (num_bb_notes != n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS) 2992 internal_error 2993 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)", 2994 num_bb_notes, n_basic_blocks_for_fn (cfun)); 2995 2996 return err; 2997 } 2998 2999 /* Verify the CFG and RTL consistency common for both underlying RTL and 3000 cfglayout RTL, plus consistency checks specific to linearized RTL mode. 3001 3002 Currently it does following checks: 3003 - all checks of rtl_verify_flow_info_1 3004 - test head/end pointers 3005 - check that blocks are laid out in consecutive order 3006 - check that all insns are in the basic blocks 3007 (except the switch handling code, barriers and notes) 3008 - check that all returns are followed by barriers 3009 - check that all fallthru edge points to the adjacent blocks 3010 - verify that there is a single hot/cold partition boundary after bbro */ 3011 3012 static int 3013 rtl_verify_flow_info (void) 3014 { 3015 int err = 0; 3016 3017 err |= rtl_verify_flow_info_1 (); 3018 3019 err |= rtl_verify_bb_insn_chain (); 3020 3021 err |= rtl_verify_fallthru (); 3022 3023 err |= rtl_verify_bb_layout (); 3024 3025 err |= verify_hot_cold_block_grouping (); 3026 3027 return err; 3028 } 3029 3030 /* Assume that the preceding pass has possibly eliminated jump instructions 3031 or converted the unconditional jumps. Eliminate the edges from CFG. 3032 Return true if any edges are eliminated. */ 3033 3034 bool 3035 purge_dead_edges (basic_block bb) 3036 { 3037 edge e; 3038 rtx_insn *insn = BB_END (bb); 3039 rtx note; 3040 bool purged = false; 3041 bool found; 3042 edge_iterator ei; 3043 3044 if (DEBUG_INSN_P (insn) && insn != BB_HEAD (bb)) 3045 do 3046 insn = PREV_INSN (insn); 3047 while ((DEBUG_INSN_P (insn) || NOTE_P (insn)) && insn != BB_HEAD (bb)); 3048 3049 /* If this instruction cannot trap, remove REG_EH_REGION notes. */ 3050 if (NONJUMP_INSN_P (insn) 3051 && (note = find_reg_note (insn, REG_EH_REGION, NULL))) 3052 { 3053 rtx eqnote; 3054 3055 if (! may_trap_p (PATTERN (insn)) 3056 || ((eqnote = find_reg_equal_equiv_note (insn)) 3057 && ! may_trap_p (XEXP (eqnote, 0)))) 3058 remove_note (insn, note); 3059 } 3060 3061 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */ 3062 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) 3063 { 3064 bool remove = false; 3065 3066 /* There are three types of edges we need to handle correctly here: EH 3067 edges, abnormal call EH edges, and abnormal call non-EH edges. The 3068 latter can appear when nonlocal gotos are used. */ 3069 if (e->flags & EDGE_ABNORMAL_CALL) 3070 { 3071 if (!CALL_P (insn)) 3072 remove = true; 3073 else if (can_nonlocal_goto (insn)) 3074 ; 3075 else if ((e->flags & EDGE_EH) && can_throw_internal (insn)) 3076 ; 3077 else if (flag_tm && find_reg_note (insn, REG_TM, NULL)) 3078 ; 3079 else 3080 remove = true; 3081 } 3082 else if (e->flags & EDGE_EH) 3083 remove = !can_throw_internal (insn); 3084 3085 if (remove) 3086 { 3087 remove_edge (e); 3088 df_set_bb_dirty (bb); 3089 purged = true; 3090 } 3091 else 3092 ei_next (&ei); 3093 } 3094 3095 if (JUMP_P (insn)) 3096 { 3097 rtx note; 3098 edge b,f; 3099 edge_iterator ei; 3100 3101 /* We do care only about conditional jumps and simplejumps. */ 3102 if (!any_condjump_p (insn) 3103 && !returnjump_p (insn) 3104 && !simplejump_p (insn)) 3105 return purged; 3106 3107 /* Branch probability/prediction notes are defined only for 3108 condjumps. We've possibly turned condjump into simplejump. */ 3109 if (simplejump_p (insn)) 3110 { 3111 note = find_reg_note (insn, REG_BR_PROB, NULL); 3112 if (note) 3113 remove_note (insn, note); 3114 while ((note = find_reg_note (insn, REG_BR_PRED, NULL))) 3115 remove_note (insn, note); 3116 } 3117 3118 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) 3119 { 3120 /* Avoid abnormal flags to leak from computed jumps turned 3121 into simplejumps. */ 3122 3123 e->flags &= ~EDGE_ABNORMAL; 3124 3125 /* See if this edge is one we should keep. */ 3126 if ((e->flags & EDGE_FALLTHRU) && any_condjump_p (insn)) 3127 /* A conditional jump can fall through into the next 3128 block, so we should keep the edge. */ 3129 { 3130 ei_next (&ei); 3131 continue; 3132 } 3133 else if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) 3134 && BB_HEAD (e->dest) == JUMP_LABEL (insn)) 3135 /* If the destination block is the target of the jump, 3136 keep the edge. */ 3137 { 3138 ei_next (&ei); 3139 continue; 3140 } 3141 else if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun) 3142 && returnjump_p (insn)) 3143 /* If the destination block is the exit block, and this 3144 instruction is a return, then keep the edge. */ 3145 { 3146 ei_next (&ei); 3147 continue; 3148 } 3149 else if ((e->flags & EDGE_EH) && can_throw_internal (insn)) 3150 /* Keep the edges that correspond to exceptions thrown by 3151 this instruction and rematerialize the EDGE_ABNORMAL 3152 flag we just cleared above. */ 3153 { 3154 e->flags |= EDGE_ABNORMAL; 3155 ei_next (&ei); 3156 continue; 3157 } 3158 3159 /* We do not need this edge. */ 3160 df_set_bb_dirty (bb); 3161 purged = true; 3162 remove_edge (e); 3163 } 3164 3165 if (EDGE_COUNT (bb->succs) == 0 || !purged) 3166 return purged; 3167 3168 if (dump_file) 3169 fprintf (dump_file, "Purged edges from bb %i\n", bb->index); 3170 3171 if (!optimize) 3172 return purged; 3173 3174 /* Redistribute probabilities. */ 3175 if (single_succ_p (bb)) 3176 { 3177 single_succ_edge (bb)->probability = profile_probability::always (); 3178 } 3179 else 3180 { 3181 note = find_reg_note (insn, REG_BR_PROB, NULL); 3182 if (!note) 3183 return purged; 3184 3185 b = BRANCH_EDGE (bb); 3186 f = FALLTHRU_EDGE (bb); 3187 b->probability = profile_probability::from_reg_br_prob_note 3188 (XINT (note, 0)); 3189 f->probability = b->probability.invert (); 3190 } 3191 3192 return purged; 3193 } 3194 else if (CALL_P (insn) && SIBLING_CALL_P (insn)) 3195 { 3196 /* First, there should not be any EH or ABCALL edges resulting 3197 from non-local gotos and the like. If there were, we shouldn't 3198 have created the sibcall in the first place. Second, there 3199 should of course never have been a fallthru edge. */ 3200 gcc_assert (single_succ_p (bb)); 3201 gcc_assert (single_succ_edge (bb)->flags 3202 == (EDGE_SIBCALL | EDGE_ABNORMAL)); 3203 3204 return 0; 3205 } 3206 3207 /* If we don't see a jump insn, we don't know exactly why the block would 3208 have been broken at this point. Look for a simple, non-fallthru edge, 3209 as these are only created by conditional branches. If we find such an 3210 edge we know that there used to be a jump here and can then safely 3211 remove all non-fallthru edges. */ 3212 found = false; 3213 FOR_EACH_EDGE (e, ei, bb->succs) 3214 if (! (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))) 3215 { 3216 found = true; 3217 break; 3218 } 3219 3220 if (!found) 3221 return purged; 3222 3223 /* Remove all but the fake and fallthru edges. The fake edge may be 3224 the only successor for this block in the case of noreturn 3225 calls. */ 3226 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) 3227 { 3228 if (!(e->flags & (EDGE_FALLTHRU | EDGE_FAKE))) 3229 { 3230 df_set_bb_dirty (bb); 3231 remove_edge (e); 3232 purged = true; 3233 } 3234 else 3235 ei_next (&ei); 3236 } 3237 3238 gcc_assert (single_succ_p (bb)); 3239 3240 single_succ_edge (bb)->probability = profile_probability::always (); 3241 3242 if (dump_file) 3243 fprintf (dump_file, "Purged non-fallthru edges from bb %i\n", 3244 bb->index); 3245 return purged; 3246 } 3247 3248 /* Search all basic blocks for potentially dead edges and purge them. Return 3249 true if some edge has been eliminated. */ 3250 3251 bool 3252 purge_all_dead_edges (void) 3253 { 3254 int purged = false; 3255 basic_block bb; 3256 3257 FOR_EACH_BB_FN (bb, cfun) 3258 { 3259 bool purged_here = purge_dead_edges (bb); 3260 3261 purged |= purged_here; 3262 } 3263 3264 return purged; 3265 } 3266 3267 /* This is used by a few passes that emit some instructions after abnormal 3268 calls, moving the basic block's end, while they in fact do want to emit 3269 them on the fallthru edge. Look for abnormal call edges, find backward 3270 the call in the block and insert the instructions on the edge instead. 3271 3272 Similarly, handle instructions throwing exceptions internally. 3273 3274 Return true when instructions have been found and inserted on edges. */ 3275 3276 bool 3277 fixup_abnormal_edges (void) 3278 { 3279 bool inserted = false; 3280 basic_block bb; 3281 3282 FOR_EACH_BB_FN (bb, cfun) 3283 { 3284 edge e; 3285 edge_iterator ei; 3286 3287 /* Look for cases we are interested in - calls or instructions causing 3288 exceptions. */ 3289 FOR_EACH_EDGE (e, ei, bb->succs) 3290 if ((e->flags & EDGE_ABNORMAL_CALL) 3291 || ((e->flags & (EDGE_ABNORMAL | EDGE_EH)) 3292 == (EDGE_ABNORMAL | EDGE_EH))) 3293 break; 3294 3295 if (e && !CALL_P (BB_END (bb)) && !can_throw_internal (BB_END (bb))) 3296 { 3297 rtx_insn *insn; 3298 3299 /* Get past the new insns generated. Allow notes, as the insns 3300 may be already deleted. */ 3301 insn = BB_END (bb); 3302 while ((NONJUMP_INSN_P (insn) || NOTE_P (insn)) 3303 && !can_throw_internal (insn) 3304 && insn != BB_HEAD (bb)) 3305 insn = PREV_INSN (insn); 3306 3307 if (CALL_P (insn) || can_throw_internal (insn)) 3308 { 3309 rtx_insn *stop, *next; 3310 3311 e = find_fallthru_edge (bb->succs); 3312 3313 stop = NEXT_INSN (BB_END (bb)); 3314 BB_END (bb) = insn; 3315 3316 for (insn = NEXT_INSN (insn); insn != stop; insn = next) 3317 { 3318 next = NEXT_INSN (insn); 3319 if (INSN_P (insn)) 3320 { 3321 delete_insn (insn); 3322 3323 /* Sometimes there's still the return value USE. 3324 If it's placed after a trapping call (i.e. that 3325 call is the last insn anyway), we have no fallthru 3326 edge. Simply delete this use and don't try to insert 3327 on the non-existent edge. 3328 Similarly, sometimes a call that can throw is 3329 followed in the source with __builtin_unreachable (), 3330 meaning that there is UB if the call returns rather 3331 than throws. If there weren't any instructions 3332 following such calls before, supposedly even the ones 3333 we've deleted aren't significant and can be 3334 removed. */ 3335 if (e) 3336 { 3337 /* We're not deleting it, we're moving it. */ 3338 insn->set_undeleted (); 3339 SET_PREV_INSN (insn) = NULL_RTX; 3340 SET_NEXT_INSN (insn) = NULL_RTX; 3341 3342 insert_insn_on_edge (insn, e); 3343 inserted = true; 3344 } 3345 } 3346 else if (!BARRIER_P (insn)) 3347 set_block_for_insn (insn, NULL); 3348 } 3349 } 3350 3351 /* It may be that we don't find any trapping insn. In this 3352 case we discovered quite late that the insn that had been 3353 marked as can_throw_internal in fact couldn't trap at all. 3354 So we should in fact delete the EH edges out of the block. */ 3355 else 3356 purge_dead_edges (bb); 3357 } 3358 } 3359 3360 return inserted; 3361 } 3362 3363 /* Cut the insns from FIRST to LAST out of the insns stream. */ 3364 3365 rtx_insn * 3366 unlink_insn_chain (rtx_insn *first, rtx_insn *last) 3367 { 3368 rtx_insn *prevfirst = PREV_INSN (first); 3369 rtx_insn *nextlast = NEXT_INSN (last); 3370 3371 SET_PREV_INSN (first) = NULL; 3372 SET_NEXT_INSN (last) = NULL; 3373 if (prevfirst) 3374 SET_NEXT_INSN (prevfirst) = nextlast; 3375 if (nextlast) 3376 SET_PREV_INSN (nextlast) = prevfirst; 3377 else 3378 set_last_insn (prevfirst); 3379 if (!prevfirst) 3380 set_first_insn (nextlast); 3381 return first; 3382 } 3383 3384 /* Skip over inter-block insns occurring after BB which are typically 3385 associated with BB (e.g., barriers). If there are any such insns, 3386 we return the last one. Otherwise, we return the end of BB. */ 3387 3388 static rtx_insn * 3389 skip_insns_after_block (basic_block bb) 3390 { 3391 rtx_insn *insn, *last_insn, *next_head, *prev; 3392 3393 next_head = NULL; 3394 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun)) 3395 next_head = BB_HEAD (bb->next_bb); 3396 3397 for (last_insn = insn = BB_END (bb); (insn = NEXT_INSN (insn)) != 0; ) 3398 { 3399 if (insn == next_head) 3400 break; 3401 3402 switch (GET_CODE (insn)) 3403 { 3404 case BARRIER: 3405 last_insn = insn; 3406 continue; 3407 3408 case NOTE: 3409 switch (NOTE_KIND (insn)) 3410 { 3411 case NOTE_INSN_BLOCK_END: 3412 gcc_unreachable (); 3413 continue; 3414 default: 3415 continue; 3416 break; 3417 } 3418 break; 3419 3420 case CODE_LABEL: 3421 if (NEXT_INSN (insn) 3422 && JUMP_TABLE_DATA_P (NEXT_INSN (insn))) 3423 { 3424 insn = NEXT_INSN (insn); 3425 last_insn = insn; 3426 continue; 3427 } 3428 break; 3429 3430 default: 3431 break; 3432 } 3433 3434 break; 3435 } 3436 3437 /* It is possible to hit contradictory sequence. For instance: 3438 3439 jump_insn 3440 NOTE_INSN_BLOCK_BEG 3441 barrier 3442 3443 Where barrier belongs to jump_insn, but the note does not. This can be 3444 created by removing the basic block originally following 3445 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */ 3446 3447 for (insn = last_insn; insn != BB_END (bb); insn = prev) 3448 { 3449 prev = PREV_INSN (insn); 3450 if (NOTE_P (insn)) 3451 switch (NOTE_KIND (insn)) 3452 { 3453 case NOTE_INSN_BLOCK_END: 3454 gcc_unreachable (); 3455 break; 3456 case NOTE_INSN_DELETED: 3457 case NOTE_INSN_DELETED_LABEL: 3458 case NOTE_INSN_DELETED_DEBUG_LABEL: 3459 continue; 3460 default: 3461 reorder_insns (insn, insn, last_insn); 3462 } 3463 } 3464 3465 return last_insn; 3466 } 3467 3468 /* Locate or create a label for a given basic block. */ 3469 3470 static rtx_insn * 3471 label_for_bb (basic_block bb) 3472 { 3473 rtx_insn *label = BB_HEAD (bb); 3474 3475 if (!LABEL_P (label)) 3476 { 3477 if (dump_file) 3478 fprintf (dump_file, "Emitting label for block %d\n", bb->index); 3479 3480 label = block_label (bb); 3481 } 3482 3483 return label; 3484 } 3485 3486 /* Locate the effective beginning and end of the insn chain for each 3487 block, as defined by skip_insns_after_block above. */ 3488 3489 static void 3490 record_effective_endpoints (void) 3491 { 3492 rtx_insn *next_insn; 3493 basic_block bb; 3494 rtx_insn *insn; 3495 3496 for (insn = get_insns (); 3497 insn 3498 && NOTE_P (insn) 3499 && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK; 3500 insn = NEXT_INSN (insn)) 3501 continue; 3502 /* No basic blocks at all? */ 3503 gcc_assert (insn); 3504 3505 if (PREV_INSN (insn)) 3506 cfg_layout_function_header = 3507 unlink_insn_chain (get_insns (), PREV_INSN (insn)); 3508 else 3509 cfg_layout_function_header = NULL; 3510 3511 next_insn = get_insns (); 3512 FOR_EACH_BB_FN (bb, cfun) 3513 { 3514 rtx_insn *end; 3515 3516 if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb)) 3517 BB_HEADER (bb) = unlink_insn_chain (next_insn, 3518 PREV_INSN (BB_HEAD (bb))); 3519 end = skip_insns_after_block (bb); 3520 if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end) 3521 BB_FOOTER (bb) = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end); 3522 next_insn = NEXT_INSN (BB_END (bb)); 3523 } 3524 3525 cfg_layout_function_footer = next_insn; 3526 if (cfg_layout_function_footer) 3527 cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ()); 3528 } 3529 3530 namespace { 3531 3532 const pass_data pass_data_into_cfg_layout_mode = 3533 { 3534 RTL_PASS, /* type */ 3535 "into_cfglayout", /* name */ 3536 OPTGROUP_NONE, /* optinfo_flags */ 3537 TV_CFG, /* tv_id */ 3538 0, /* properties_required */ 3539 PROP_cfglayout, /* properties_provided */ 3540 0, /* properties_destroyed */ 3541 0, /* todo_flags_start */ 3542 0, /* todo_flags_finish */ 3543 }; 3544 3545 class pass_into_cfg_layout_mode : public rtl_opt_pass 3546 { 3547 public: 3548 pass_into_cfg_layout_mode (gcc::context *ctxt) 3549 : rtl_opt_pass (pass_data_into_cfg_layout_mode, ctxt) 3550 {} 3551 3552 /* opt_pass methods: */ 3553 virtual unsigned int execute (function *) 3554 { 3555 cfg_layout_initialize (0); 3556 return 0; 3557 } 3558 3559 }; // class pass_into_cfg_layout_mode 3560 3561 } // anon namespace 3562 3563 rtl_opt_pass * 3564 make_pass_into_cfg_layout_mode (gcc::context *ctxt) 3565 { 3566 return new pass_into_cfg_layout_mode (ctxt); 3567 } 3568 3569 namespace { 3570 3571 const pass_data pass_data_outof_cfg_layout_mode = 3572 { 3573 RTL_PASS, /* type */ 3574 "outof_cfglayout", /* name */ 3575 OPTGROUP_NONE, /* optinfo_flags */ 3576 TV_CFG, /* tv_id */ 3577 0, /* properties_required */ 3578 0, /* properties_provided */ 3579 PROP_cfglayout, /* properties_destroyed */ 3580 0, /* todo_flags_start */ 3581 0, /* todo_flags_finish */ 3582 }; 3583 3584 class pass_outof_cfg_layout_mode : public rtl_opt_pass 3585 { 3586 public: 3587 pass_outof_cfg_layout_mode (gcc::context *ctxt) 3588 : rtl_opt_pass (pass_data_outof_cfg_layout_mode, ctxt) 3589 {} 3590 3591 /* opt_pass methods: */ 3592 virtual unsigned int execute (function *); 3593 3594 }; // class pass_outof_cfg_layout_mode 3595 3596 unsigned int 3597 pass_outof_cfg_layout_mode::execute (function *fun) 3598 { 3599 basic_block bb; 3600 3601 FOR_EACH_BB_FN (bb, fun) 3602 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (fun)) 3603 bb->aux = bb->next_bb; 3604 3605 cfg_layout_finalize (); 3606 3607 return 0; 3608 } 3609 3610 } // anon namespace 3611 3612 rtl_opt_pass * 3613 make_pass_outof_cfg_layout_mode (gcc::context *ctxt) 3614 { 3615 return new pass_outof_cfg_layout_mode (ctxt); 3616 } 3617 3618 3619 /* Link the basic blocks in the correct order, compacting the basic 3620 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this 3621 function also clears the basic block header and footer fields. 3622 3623 This function is usually called after a pass (e.g. tracer) finishes 3624 some transformations while in cfglayout mode. The required sequence 3625 of the basic blocks is in a linked list along the bb->aux field. 3626 This functions re-links the basic block prev_bb and next_bb pointers 3627 accordingly, and it compacts and renumbers the blocks. 3628 3629 FIXME: This currently works only for RTL, but the only RTL-specific 3630 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved 3631 to GIMPLE a long time ago, but it doesn't relink the basic block 3632 chain. It could do that (to give better initial RTL) if this function 3633 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */ 3634 3635 void 3636 relink_block_chain (bool stay_in_cfglayout_mode) 3637 { 3638 basic_block bb, prev_bb; 3639 int index; 3640 3641 /* Maybe dump the re-ordered sequence. */ 3642 if (dump_file) 3643 { 3644 fprintf (dump_file, "Reordered sequence:\n"); 3645 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, index = 3646 NUM_FIXED_BLOCKS; 3647 bb; 3648 bb = (basic_block) bb->aux, index++) 3649 { 3650 fprintf (dump_file, " %i ", index); 3651 if (get_bb_original (bb)) 3652 fprintf (dump_file, "duplicate of %i ", 3653 get_bb_original (bb)->index); 3654 else if (forwarder_block_p (bb) 3655 && !LABEL_P (BB_HEAD (bb))) 3656 fprintf (dump_file, "compensation "); 3657 else 3658 fprintf (dump_file, "bb %i ", bb->index); 3659 } 3660 } 3661 3662 /* Now reorder the blocks. */ 3663 prev_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun); 3664 bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; 3665 for (; bb; prev_bb = bb, bb = (basic_block) bb->aux) 3666 { 3667 bb->prev_bb = prev_bb; 3668 prev_bb->next_bb = bb; 3669 } 3670 prev_bb->next_bb = EXIT_BLOCK_PTR_FOR_FN (cfun); 3671 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb = prev_bb; 3672 3673 /* Then, clean up the aux fields. */ 3674 FOR_ALL_BB_FN (bb, cfun) 3675 { 3676 bb->aux = NULL; 3677 if (!stay_in_cfglayout_mode) 3678 BB_HEADER (bb) = BB_FOOTER (bb) = NULL; 3679 } 3680 3681 /* Maybe reset the original copy tables, they are not valid anymore 3682 when we renumber the basic blocks in compact_blocks. If we are 3683 are going out of cfglayout mode, don't re-allocate the tables. */ 3684 if (original_copy_tables_initialized_p ()) 3685 free_original_copy_tables (); 3686 if (stay_in_cfglayout_mode) 3687 initialize_original_copy_tables (); 3688 3689 /* Finally, put basic_block_info in the new order. */ 3690 compact_blocks (); 3691 } 3692 3693 3694 /* Given a reorder chain, rearrange the code to match. */ 3695 3696 static void 3697 fixup_reorder_chain (void) 3698 { 3699 basic_block bb; 3700 rtx_insn *insn = NULL; 3701 3702 if (cfg_layout_function_header) 3703 { 3704 set_first_insn (cfg_layout_function_header); 3705 insn = cfg_layout_function_header; 3706 while (NEXT_INSN (insn)) 3707 insn = NEXT_INSN (insn); 3708 } 3709 3710 /* First do the bulk reordering -- rechain the blocks without regard to 3711 the needed changes to jumps and labels. */ 3712 3713 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb; bb = (basic_block) 3714 bb->aux) 3715 { 3716 if (BB_HEADER (bb)) 3717 { 3718 if (insn) 3719 SET_NEXT_INSN (insn) = BB_HEADER (bb); 3720 else 3721 set_first_insn (BB_HEADER (bb)); 3722 SET_PREV_INSN (BB_HEADER (bb)) = insn; 3723 insn = BB_HEADER (bb); 3724 while (NEXT_INSN (insn)) 3725 insn = NEXT_INSN (insn); 3726 } 3727 if (insn) 3728 SET_NEXT_INSN (insn) = BB_HEAD (bb); 3729 else 3730 set_first_insn (BB_HEAD (bb)); 3731 SET_PREV_INSN (BB_HEAD (bb)) = insn; 3732 insn = BB_END (bb); 3733 if (BB_FOOTER (bb)) 3734 { 3735 SET_NEXT_INSN (insn) = BB_FOOTER (bb); 3736 SET_PREV_INSN (BB_FOOTER (bb)) = insn; 3737 while (NEXT_INSN (insn)) 3738 insn = NEXT_INSN (insn); 3739 } 3740 } 3741 3742 SET_NEXT_INSN (insn) = cfg_layout_function_footer; 3743 if (cfg_layout_function_footer) 3744 SET_PREV_INSN (cfg_layout_function_footer) = insn; 3745 3746 while (NEXT_INSN (insn)) 3747 insn = NEXT_INSN (insn); 3748 3749 set_last_insn (insn); 3750 if (flag_checking) 3751 verify_insn_chain (); 3752 3753 /* Now add jumps and labels as needed to match the blocks new 3754 outgoing edges. */ 3755 3756 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb ; bb = (basic_block) 3757 bb->aux) 3758 { 3759 edge e_fall, e_taken, e; 3760 rtx_insn *bb_end_insn; 3761 rtx ret_label = NULL_RTX; 3762 basic_block nb; 3763 edge_iterator ei; 3764 3765 if (EDGE_COUNT (bb->succs) == 0) 3766 continue; 3767 3768 /* Find the old fallthru edge, and another non-EH edge for 3769 a taken jump. */ 3770 e_taken = e_fall = NULL; 3771 3772 FOR_EACH_EDGE (e, ei, bb->succs) 3773 if (e->flags & EDGE_FALLTHRU) 3774 e_fall = e; 3775 else if (! (e->flags & EDGE_EH)) 3776 e_taken = e; 3777 3778 bb_end_insn = BB_END (bb); 3779 if (rtx_jump_insn *bb_end_jump = dyn_cast <rtx_jump_insn *> (bb_end_insn)) 3780 { 3781 ret_label = JUMP_LABEL (bb_end_jump); 3782 if (any_condjump_p (bb_end_jump)) 3783 { 3784 /* This might happen if the conditional jump has side 3785 effects and could therefore not be optimized away. 3786 Make the basic block to end with a barrier in order 3787 to prevent rtl_verify_flow_info from complaining. */ 3788 if (!e_fall) 3789 { 3790 gcc_assert (!onlyjump_p (bb_end_jump) 3791 || returnjump_p (bb_end_jump) 3792 || (e_taken->flags & EDGE_CROSSING)); 3793 emit_barrier_after (bb_end_jump); 3794 continue; 3795 } 3796 3797 /* If the old fallthru is still next, nothing to do. */ 3798 if (bb->aux == e_fall->dest 3799 || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) 3800 continue; 3801 3802 /* The degenerated case of conditional jump jumping to the next 3803 instruction can happen for jumps with side effects. We need 3804 to construct a forwarder block and this will be done just 3805 fine by force_nonfallthru below. */ 3806 if (!e_taken) 3807 ; 3808 3809 /* There is another special case: if *neither* block is next, 3810 such as happens at the very end of a function, then we'll 3811 need to add a new unconditional jump. Choose the taken 3812 edge based on known or assumed probability. */ 3813 else if (bb->aux != e_taken->dest) 3814 { 3815 rtx note = find_reg_note (bb_end_jump, REG_BR_PROB, 0); 3816 3817 if (note 3818 && profile_probability::from_reg_br_prob_note 3819 (XINT (note, 0)) < profile_probability::even () 3820 && invert_jump (bb_end_jump, 3821 (e_fall->dest 3822 == EXIT_BLOCK_PTR_FOR_FN (cfun) 3823 ? NULL_RTX 3824 : label_for_bb (e_fall->dest)), 0)) 3825 { 3826 e_fall->flags &= ~EDGE_FALLTHRU; 3827 gcc_checking_assert (could_fall_through 3828 (e_taken->src, e_taken->dest)); 3829 e_taken->flags |= EDGE_FALLTHRU; 3830 update_br_prob_note (bb); 3831 e = e_fall, e_fall = e_taken, e_taken = e; 3832 } 3833 } 3834 3835 /* If the "jumping" edge is a crossing edge, and the fall 3836 through edge is non-crossing, leave things as they are. */ 3837 else if ((e_taken->flags & EDGE_CROSSING) 3838 && !(e_fall->flags & EDGE_CROSSING)) 3839 continue; 3840 3841 /* Otherwise we can try to invert the jump. This will 3842 basically never fail, however, keep up the pretense. */ 3843 else if (invert_jump (bb_end_jump, 3844 (e_fall->dest 3845 == EXIT_BLOCK_PTR_FOR_FN (cfun) 3846 ? NULL_RTX 3847 : label_for_bb (e_fall->dest)), 0)) 3848 { 3849 e_fall->flags &= ~EDGE_FALLTHRU; 3850 gcc_checking_assert (could_fall_through 3851 (e_taken->src, e_taken->dest)); 3852 e_taken->flags |= EDGE_FALLTHRU; 3853 update_br_prob_note (bb); 3854 if (LABEL_NUSES (ret_label) == 0 3855 && single_pred_p (e_taken->dest)) 3856 delete_insn (as_a<rtx_insn *> (ret_label)); 3857 continue; 3858 } 3859 } 3860 else if (extract_asm_operands (PATTERN (bb_end_insn)) != NULL) 3861 { 3862 /* If the old fallthru is still next or if 3863 asm goto doesn't have a fallthru (e.g. when followed by 3864 __builtin_unreachable ()), nothing to do. */ 3865 if (! e_fall 3866 || bb->aux == e_fall->dest 3867 || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) 3868 continue; 3869 3870 /* Otherwise we'll have to use the fallthru fixup below. */ 3871 } 3872 else 3873 { 3874 /* Otherwise we have some return, switch or computed 3875 jump. In the 99% case, there should not have been a 3876 fallthru edge. */ 3877 gcc_assert (returnjump_p (bb_end_insn) || !e_fall); 3878 continue; 3879 } 3880 } 3881 else 3882 { 3883 /* No fallthru implies a noreturn function with EH edges, or 3884 something similarly bizarre. In any case, we don't need to 3885 do anything. */ 3886 if (! e_fall) 3887 continue; 3888 3889 /* If the fallthru block is still next, nothing to do. */ 3890 if (bb->aux == e_fall->dest) 3891 continue; 3892 3893 /* A fallthru to exit block. */ 3894 if (e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) 3895 continue; 3896 } 3897 3898 /* We got here if we need to add a new jump insn. 3899 Note force_nonfallthru can delete E_FALL and thus we have to 3900 save E_FALL->src prior to the call to force_nonfallthru. */ 3901 nb = force_nonfallthru_and_redirect (e_fall, e_fall->dest, ret_label); 3902 if (nb) 3903 { 3904 nb->aux = bb->aux; 3905 bb->aux = nb; 3906 /* Don't process this new block. */ 3907 bb = nb; 3908 } 3909 } 3910 3911 relink_block_chain (/*stay_in_cfglayout_mode=*/false); 3912 3913 /* Annoying special case - jump around dead jumptables left in the code. */ 3914 FOR_EACH_BB_FN (bb, cfun) 3915 { 3916 edge e = find_fallthru_edge (bb->succs); 3917 3918 if (e && !can_fallthru (e->src, e->dest)) 3919 force_nonfallthru (e); 3920 } 3921 3922 /* Ensure goto_locus from edges has some instructions with that locus 3923 in RTL. */ 3924 if (!optimize) 3925 FOR_EACH_BB_FN (bb, cfun) 3926 { 3927 edge e; 3928 edge_iterator ei; 3929 3930 FOR_EACH_EDGE (e, ei, bb->succs) 3931 if (LOCATION_LOCUS (e->goto_locus) != UNKNOWN_LOCATION 3932 && !(e->flags & EDGE_ABNORMAL)) 3933 { 3934 edge e2; 3935 edge_iterator ei2; 3936 basic_block dest, nb; 3937 rtx_insn *end; 3938 3939 insn = BB_END (e->src); 3940 end = PREV_INSN (BB_HEAD (e->src)); 3941 while (insn != end 3942 && (!NONDEBUG_INSN_P (insn) || !INSN_HAS_LOCATION (insn))) 3943 insn = PREV_INSN (insn); 3944 if (insn != end 3945 && INSN_LOCATION (insn) == e->goto_locus) 3946 continue; 3947 if (simplejump_p (BB_END (e->src)) 3948 && !INSN_HAS_LOCATION (BB_END (e->src))) 3949 { 3950 INSN_LOCATION (BB_END (e->src)) = e->goto_locus; 3951 continue; 3952 } 3953 dest = e->dest; 3954 if (dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) 3955 { 3956 /* Non-fallthru edges to the exit block cannot be split. */ 3957 if (!(e->flags & EDGE_FALLTHRU)) 3958 continue; 3959 } 3960 else 3961 { 3962 insn = BB_HEAD (dest); 3963 end = NEXT_INSN (BB_END (dest)); 3964 while (insn != end && !NONDEBUG_INSN_P (insn)) 3965 insn = NEXT_INSN (insn); 3966 if (insn != end && INSN_HAS_LOCATION (insn) 3967 && INSN_LOCATION (insn) == e->goto_locus) 3968 continue; 3969 } 3970 nb = split_edge (e); 3971 if (!INSN_P (BB_END (nb))) 3972 BB_END (nb) = emit_insn_after_noloc (gen_nop (), BB_END (nb), 3973 nb); 3974 INSN_LOCATION (BB_END (nb)) = e->goto_locus; 3975 3976 /* If there are other incoming edges to the destination block 3977 with the same goto locus, redirect them to the new block as 3978 well, this can prevent other such blocks from being created 3979 in subsequent iterations of the loop. */ 3980 for (ei2 = ei_start (dest->preds); (e2 = ei_safe_edge (ei2)); ) 3981 if (LOCATION_LOCUS (e2->goto_locus) != UNKNOWN_LOCATION 3982 && !(e2->flags & (EDGE_ABNORMAL | EDGE_FALLTHRU)) 3983 && e->goto_locus == e2->goto_locus) 3984 redirect_edge_and_branch (e2, nb); 3985 else 3986 ei_next (&ei2); 3987 } 3988 } 3989 } 3990 3991 /* Perform sanity checks on the insn chain. 3992 1. Check that next/prev pointers are consistent in both the forward and 3993 reverse direction. 3994 2. Count insns in chain, going both directions, and check if equal. 3995 3. Check that get_last_insn () returns the actual end of chain. */ 3996 3997 DEBUG_FUNCTION void 3998 verify_insn_chain (void) 3999 { 4000 rtx_insn *x, *prevx, *nextx; 4001 int insn_cnt1, insn_cnt2; 4002 4003 for (prevx = NULL, insn_cnt1 = 1, x = get_insns (); 4004 x != 0; 4005 prevx = x, insn_cnt1++, x = NEXT_INSN (x)) 4006 gcc_assert (PREV_INSN (x) == prevx); 4007 4008 gcc_assert (prevx == get_last_insn ()); 4009 4010 for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn (); 4011 x != 0; 4012 nextx = x, insn_cnt2++, x = PREV_INSN (x)) 4013 gcc_assert (NEXT_INSN (x) == nextx); 4014 4015 gcc_assert (insn_cnt1 == insn_cnt2); 4016 } 4017 4018 /* If we have assembler epilogues, the block falling through to exit must 4019 be the last one in the reordered chain when we reach final. Ensure 4020 that this condition is met. */ 4021 static void 4022 fixup_fallthru_exit_predecessor (void) 4023 { 4024 edge e; 4025 basic_block bb = NULL; 4026 4027 /* This transformation is not valid before reload, because we might 4028 separate a call from the instruction that copies the return 4029 value. */ 4030 gcc_assert (reload_completed); 4031 4032 e = find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds); 4033 if (e) 4034 bb = e->src; 4035 4036 if (bb && bb->aux) 4037 { 4038 basic_block c = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; 4039 4040 /* If the very first block is the one with the fall-through exit 4041 edge, we have to split that block. */ 4042 if (c == bb) 4043 { 4044 bb = split_block_after_labels (bb)->dest; 4045 bb->aux = c->aux; 4046 c->aux = bb; 4047 BB_FOOTER (bb) = BB_FOOTER (c); 4048 BB_FOOTER (c) = NULL; 4049 } 4050 4051 while (c->aux != bb) 4052 c = (basic_block) c->aux; 4053 4054 c->aux = bb->aux; 4055 while (c->aux) 4056 c = (basic_block) c->aux; 4057 4058 c->aux = bb; 4059 bb->aux = NULL; 4060 } 4061 } 4062 4063 /* In case there are more than one fallthru predecessors of exit, force that 4064 there is only one. */ 4065 4066 static void 4067 force_one_exit_fallthru (void) 4068 { 4069 edge e, predecessor = NULL; 4070 bool more = false; 4071 edge_iterator ei; 4072 basic_block forwarder, bb; 4073 4074 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds) 4075 if (e->flags & EDGE_FALLTHRU) 4076 { 4077 if (predecessor == NULL) 4078 predecessor = e; 4079 else 4080 { 4081 more = true; 4082 break; 4083 } 4084 } 4085 4086 if (!more) 4087 return; 4088 4089 /* Exit has several fallthru predecessors. Create a forwarder block for 4090 them. */ 4091 forwarder = split_edge (predecessor); 4092 for (ei = ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds); 4093 (e = ei_safe_edge (ei)); ) 4094 { 4095 if (e->src == forwarder 4096 || !(e->flags & EDGE_FALLTHRU)) 4097 ei_next (&ei); 4098 else 4099 redirect_edge_and_branch_force (e, forwarder); 4100 } 4101 4102 /* Fix up the chain of blocks -- make FORWARDER immediately precede the 4103 exit block. */ 4104 FOR_EACH_BB_FN (bb, cfun) 4105 { 4106 if (bb->aux == NULL && bb != forwarder) 4107 { 4108 bb->aux = forwarder; 4109 break; 4110 } 4111 } 4112 } 4113 4114 /* Return true in case it is possible to duplicate the basic block BB. */ 4115 4116 static bool 4117 cfg_layout_can_duplicate_bb_p (const_basic_block bb) 4118 { 4119 /* Do not attempt to duplicate tablejumps, as we need to unshare 4120 the dispatch table. This is difficult to do, as the instructions 4121 computing jump destination may be hoisted outside the basic block. */ 4122 if (tablejump_p (BB_END (bb), NULL, NULL)) 4123 return false; 4124 4125 /* Do not duplicate blocks containing insns that can't be copied. */ 4126 if (targetm.cannot_copy_insn_p) 4127 { 4128 rtx_insn *insn = BB_HEAD (bb); 4129 while (1) 4130 { 4131 if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn)) 4132 return false; 4133 if (insn == BB_END (bb)) 4134 break; 4135 insn = NEXT_INSN (insn); 4136 } 4137 } 4138 4139 return true; 4140 } 4141 4142 rtx_insn * 4143 duplicate_insn_chain (rtx_insn *from, rtx_insn *to) 4144 { 4145 rtx_insn *insn, *next, *copy; 4146 rtx_note *last; 4147 4148 /* Avoid updating of boundaries of previous basic block. The 4149 note will get removed from insn stream in fixup. */ 4150 last = emit_note (NOTE_INSN_DELETED); 4151 4152 /* Create copy at the end of INSN chain. The chain will 4153 be reordered later. */ 4154 for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn)) 4155 { 4156 switch (GET_CODE (insn)) 4157 { 4158 case DEBUG_INSN: 4159 /* Don't duplicate label debug insns. */ 4160 if (DEBUG_BIND_INSN_P (insn) 4161 && TREE_CODE (INSN_VAR_LOCATION_DECL (insn)) == LABEL_DECL) 4162 break; 4163 /* FALLTHRU */ 4164 case INSN: 4165 case CALL_INSN: 4166 case JUMP_INSN: 4167 copy = emit_copy_of_insn_after (insn, get_last_insn ()); 4168 if (JUMP_P (insn) && JUMP_LABEL (insn) != NULL_RTX 4169 && ANY_RETURN_P (JUMP_LABEL (insn))) 4170 JUMP_LABEL (copy) = JUMP_LABEL (insn); 4171 maybe_copy_prologue_epilogue_insn (insn, copy); 4172 break; 4173 4174 case JUMP_TABLE_DATA: 4175 /* Avoid copying of dispatch tables. We never duplicate 4176 tablejumps, so this can hit only in case the table got 4177 moved far from original jump. 4178 Avoid copying following barrier as well if any 4179 (and debug insns in between). */ 4180 for (next = NEXT_INSN (insn); 4181 next != NEXT_INSN (to); 4182 next = NEXT_INSN (next)) 4183 if (!DEBUG_INSN_P (next)) 4184 break; 4185 if (next != NEXT_INSN (to) && BARRIER_P (next)) 4186 insn = next; 4187 break; 4188 4189 case CODE_LABEL: 4190 break; 4191 4192 case BARRIER: 4193 emit_barrier (); 4194 break; 4195 4196 case NOTE: 4197 switch (NOTE_KIND (insn)) 4198 { 4199 /* In case prologue is empty and function contain label 4200 in first BB, we may want to copy the block. */ 4201 case NOTE_INSN_PROLOGUE_END: 4202 4203 case NOTE_INSN_DELETED: 4204 case NOTE_INSN_DELETED_LABEL: 4205 case NOTE_INSN_DELETED_DEBUG_LABEL: 4206 /* No problem to strip these. */ 4207 case NOTE_INSN_FUNCTION_BEG: 4208 /* There is always just single entry to function. */ 4209 case NOTE_INSN_BASIC_BLOCK: 4210 /* We should only switch text sections once. */ 4211 case NOTE_INSN_SWITCH_TEXT_SECTIONS: 4212 break; 4213 4214 case NOTE_INSN_EPILOGUE_BEG: 4215 case NOTE_INSN_UPDATE_SJLJ_CONTEXT: 4216 emit_note_copy (as_a <rtx_note *> (insn)); 4217 break; 4218 4219 default: 4220 /* All other notes should have already been eliminated. */ 4221 gcc_unreachable (); 4222 } 4223 break; 4224 default: 4225 gcc_unreachable (); 4226 } 4227 } 4228 insn = NEXT_INSN (last); 4229 delete_insn (last); 4230 return insn; 4231 } 4232 4233 /* Create a duplicate of the basic block BB. */ 4234 4235 static basic_block 4236 cfg_layout_duplicate_bb (basic_block bb) 4237 { 4238 rtx_insn *insn; 4239 basic_block new_bb; 4240 4241 insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb)); 4242 new_bb = create_basic_block (insn, 4243 insn ? get_last_insn () : NULL, 4244 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb); 4245 4246 BB_COPY_PARTITION (new_bb, bb); 4247 if (BB_HEADER (bb)) 4248 { 4249 insn = BB_HEADER (bb); 4250 while (NEXT_INSN (insn)) 4251 insn = NEXT_INSN (insn); 4252 insn = duplicate_insn_chain (BB_HEADER (bb), insn); 4253 if (insn) 4254 BB_HEADER (new_bb) = unlink_insn_chain (insn, get_last_insn ()); 4255 } 4256 4257 if (BB_FOOTER (bb)) 4258 { 4259 insn = BB_FOOTER (bb); 4260 while (NEXT_INSN (insn)) 4261 insn = NEXT_INSN (insn); 4262 insn = duplicate_insn_chain (BB_FOOTER (bb), insn); 4263 if (insn) 4264 BB_FOOTER (new_bb) = unlink_insn_chain (insn, get_last_insn ()); 4265 } 4266 4267 return new_bb; 4268 } 4269 4270 4271 /* Main entry point to this module - initialize the datastructures for 4272 CFG layout changes. It keeps LOOPS up-to-date if not null. 4273 4274 FLAGS is a set of additional flags to pass to cleanup_cfg(). */ 4275 4276 void 4277 cfg_layout_initialize (int flags) 4278 { 4279 rtx_insn_list *x; 4280 basic_block bb; 4281 4282 /* Once bb partitioning is complete, cfg layout mode should not be 4283 re-entered. Entering cfg layout mode may require fixups. As an 4284 example, if edge forwarding performed when optimizing the cfg 4285 layout required moving a block from the hot to the cold 4286 section. This would create an illegal partitioning unless some 4287 manual fixup was performed. */ 4288 gcc_assert (!crtl->bb_reorder_complete || !crtl->has_bb_partition); 4289 4290 initialize_original_copy_tables (); 4291 4292 cfg_layout_rtl_register_cfg_hooks (); 4293 4294 record_effective_endpoints (); 4295 4296 /* Make sure that the targets of non local gotos are marked. */ 4297 for (x = nonlocal_goto_handler_labels; x; x = x->next ()) 4298 { 4299 bb = BLOCK_FOR_INSN (x->insn ()); 4300 bb->flags |= BB_NON_LOCAL_GOTO_TARGET; 4301 } 4302 4303 cleanup_cfg (CLEANUP_CFGLAYOUT | flags); 4304 } 4305 4306 /* Splits superblocks. */ 4307 void 4308 break_superblocks (void) 4309 { 4310 bool need = false; 4311 basic_block bb; 4312 4313 auto_sbitmap superblocks (last_basic_block_for_fn (cfun)); 4314 bitmap_clear (superblocks); 4315 4316 FOR_EACH_BB_FN (bb, cfun) 4317 if (bb->flags & BB_SUPERBLOCK) 4318 { 4319 bb->flags &= ~BB_SUPERBLOCK; 4320 bitmap_set_bit (superblocks, bb->index); 4321 need = true; 4322 } 4323 4324 if (need) 4325 { 4326 rebuild_jump_labels (get_insns ()); 4327 find_many_sub_basic_blocks (superblocks); 4328 } 4329 } 4330 4331 /* Finalize the changes: reorder insn list according to the sequence specified 4332 by aux pointers, enter compensation code, rebuild scope forest. */ 4333 4334 void 4335 cfg_layout_finalize (void) 4336 { 4337 free_dominance_info (CDI_DOMINATORS); 4338 force_one_exit_fallthru (); 4339 rtl_register_cfg_hooks (); 4340 if (reload_completed && !targetm.have_epilogue ()) 4341 fixup_fallthru_exit_predecessor (); 4342 fixup_reorder_chain (); 4343 4344 rebuild_jump_labels (get_insns ()); 4345 delete_dead_jumptables (); 4346 4347 if (flag_checking) 4348 verify_insn_chain (); 4349 checking_verify_flow_info (); 4350 } 4351 4352 4353 /* Same as split_block but update cfg_layout structures. */ 4354 4355 static basic_block 4356 cfg_layout_split_block (basic_block bb, void *insnp) 4357 { 4358 rtx insn = (rtx) insnp; 4359 basic_block new_bb = rtl_split_block (bb, insn); 4360 4361 BB_FOOTER (new_bb) = BB_FOOTER (bb); 4362 BB_FOOTER (bb) = NULL; 4363 4364 return new_bb; 4365 } 4366 4367 /* Redirect Edge to DEST. */ 4368 static edge 4369 cfg_layout_redirect_edge_and_branch (edge e, basic_block dest) 4370 { 4371 basic_block src = e->src; 4372 edge ret; 4373 4374 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)) 4375 return NULL; 4376 4377 if (e->dest == dest) 4378 return e; 4379 4380 if (e->flags & EDGE_CROSSING 4381 && BB_PARTITION (e->src) == BB_PARTITION (dest) 4382 && simplejump_p (BB_END (src))) 4383 { 4384 if (dump_file) 4385 fprintf (dump_file, 4386 "Removing crossing jump while redirecting edge form %i to %i\n", 4387 e->src->index, dest->index); 4388 delete_insn (BB_END (src)); 4389 remove_barriers_from_footer (src); 4390 e->flags |= EDGE_FALLTHRU; 4391 } 4392 4393 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) 4394 && (ret = try_redirect_by_replacing_jump (e, dest, true))) 4395 { 4396 df_set_bb_dirty (src); 4397 return ret; 4398 } 4399 4400 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) 4401 && (e->flags & EDGE_FALLTHRU) && !(e->flags & EDGE_COMPLEX)) 4402 { 4403 if (dump_file) 4404 fprintf (dump_file, "Redirecting entry edge from bb %i to %i\n", 4405 e->src->index, dest->index); 4406 4407 df_set_bb_dirty (e->src); 4408 redirect_edge_succ (e, dest); 4409 return e; 4410 } 4411 4412 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge 4413 in the case the basic block appears to be in sequence. Avoid this 4414 transformation. */ 4415 4416 if (e->flags & EDGE_FALLTHRU) 4417 { 4418 /* Redirect any branch edges unified with the fallthru one. */ 4419 if (JUMP_P (BB_END (src)) 4420 && label_is_jump_target_p (BB_HEAD (e->dest), 4421 BB_END (src))) 4422 { 4423 edge redirected; 4424 4425 if (dump_file) 4426 fprintf (dump_file, "Fallthru edge unified with branch " 4427 "%i->%i redirected to %i\n", 4428 e->src->index, e->dest->index, dest->index); 4429 e->flags &= ~EDGE_FALLTHRU; 4430 redirected = redirect_branch_edge (e, dest); 4431 gcc_assert (redirected); 4432 redirected->flags |= EDGE_FALLTHRU; 4433 df_set_bb_dirty (redirected->src); 4434 return redirected; 4435 } 4436 /* In case we are redirecting fallthru edge to the branch edge 4437 of conditional jump, remove it. */ 4438 if (EDGE_COUNT (src->succs) == 2) 4439 { 4440 /* Find the edge that is different from E. */ 4441 edge s = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e); 4442 4443 if (s->dest == dest 4444 && any_condjump_p (BB_END (src)) 4445 && onlyjump_p (BB_END (src))) 4446 delete_insn (BB_END (src)); 4447 } 4448 if (dump_file) 4449 fprintf (dump_file, "Redirecting fallthru edge %i->%i to %i\n", 4450 e->src->index, e->dest->index, dest->index); 4451 ret = redirect_edge_succ_nodup (e, dest); 4452 } 4453 else 4454 ret = redirect_branch_edge (e, dest); 4455 4456 if (!ret) 4457 return NULL; 4458 4459 fixup_partition_crossing (ret); 4460 /* We don't want simplejumps in the insn stream during cfglayout. */ 4461 gcc_assert (!simplejump_p (BB_END (src)) || CROSSING_JUMP_P (BB_END (src))); 4462 4463 df_set_bb_dirty (src); 4464 return ret; 4465 } 4466 4467 /* Simple wrapper as we always can redirect fallthru edges. */ 4468 static basic_block 4469 cfg_layout_redirect_edge_and_branch_force (edge e, basic_block dest) 4470 { 4471 edge redirected = cfg_layout_redirect_edge_and_branch (e, dest); 4472 4473 gcc_assert (redirected); 4474 return NULL; 4475 } 4476 4477 /* Same as delete_basic_block but update cfg_layout structures. */ 4478 4479 static void 4480 cfg_layout_delete_block (basic_block bb) 4481 { 4482 rtx_insn *insn, *next, *prev = PREV_INSN (BB_HEAD (bb)), *remaints; 4483 rtx_insn **to; 4484 4485 if (BB_HEADER (bb)) 4486 { 4487 next = BB_HEAD (bb); 4488 if (prev) 4489 SET_NEXT_INSN (prev) = BB_HEADER (bb); 4490 else 4491 set_first_insn (BB_HEADER (bb)); 4492 SET_PREV_INSN (BB_HEADER (bb)) = prev; 4493 insn = BB_HEADER (bb); 4494 while (NEXT_INSN (insn)) 4495 insn = NEXT_INSN (insn); 4496 SET_NEXT_INSN (insn) = next; 4497 SET_PREV_INSN (next) = insn; 4498 } 4499 next = NEXT_INSN (BB_END (bb)); 4500 if (BB_FOOTER (bb)) 4501 { 4502 insn = BB_FOOTER (bb); 4503 while (insn) 4504 { 4505 if (BARRIER_P (insn)) 4506 { 4507 if (PREV_INSN (insn)) 4508 SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn); 4509 else 4510 BB_FOOTER (bb) = NEXT_INSN (insn); 4511 if (NEXT_INSN (insn)) 4512 SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn); 4513 } 4514 if (LABEL_P (insn)) 4515 break; 4516 insn = NEXT_INSN (insn); 4517 } 4518 if (BB_FOOTER (bb)) 4519 { 4520 insn = BB_END (bb); 4521 SET_NEXT_INSN (insn) = BB_FOOTER (bb); 4522 SET_PREV_INSN (BB_FOOTER (bb)) = insn; 4523 while (NEXT_INSN (insn)) 4524 insn = NEXT_INSN (insn); 4525 SET_NEXT_INSN (insn) = next; 4526 if (next) 4527 SET_PREV_INSN (next) = insn; 4528 else 4529 set_last_insn (insn); 4530 } 4531 } 4532 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun)) 4533 to = &BB_HEADER (bb->next_bb); 4534 else 4535 to = &cfg_layout_function_footer; 4536 4537 rtl_delete_block (bb); 4538 4539 if (prev) 4540 prev = NEXT_INSN (prev); 4541 else 4542 prev = get_insns (); 4543 if (next) 4544 next = PREV_INSN (next); 4545 else 4546 next = get_last_insn (); 4547 4548 if (next && NEXT_INSN (next) != prev) 4549 { 4550 remaints = unlink_insn_chain (prev, next); 4551 insn = remaints; 4552 while (NEXT_INSN (insn)) 4553 insn = NEXT_INSN (insn); 4554 SET_NEXT_INSN (insn) = *to; 4555 if (*to) 4556 SET_PREV_INSN (*to) = insn; 4557 *to = remaints; 4558 } 4559 } 4560 4561 /* Return true when blocks A and B can be safely merged. */ 4562 4563 static bool 4564 cfg_layout_can_merge_blocks_p (basic_block a, basic_block b) 4565 { 4566 /* If we are partitioning hot/cold basic blocks, we don't want to 4567 mess up unconditional or indirect jumps that cross between hot 4568 and cold sections. 4569 4570 Basic block partitioning may result in some jumps that appear to 4571 be optimizable (or blocks that appear to be mergeable), but which really 4572 must be left untouched (they are required to make it safely across 4573 partition boundaries). See the comments at the top of 4574 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */ 4575 4576 if (BB_PARTITION (a) != BB_PARTITION (b)) 4577 return false; 4578 4579 /* Protect the loop latches. */ 4580 if (current_loops && b->loop_father->latch == b) 4581 return false; 4582 4583 /* If we would end up moving B's instructions, make sure it doesn't fall 4584 through into the exit block, since we cannot recover from a fallthrough 4585 edge into the exit block occurring in the middle of a function. */ 4586 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b)) 4587 { 4588 edge e = find_fallthru_edge (b->succs); 4589 if (e && e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) 4590 return false; 4591 } 4592 4593 /* There must be exactly one edge in between the blocks. */ 4594 return (single_succ_p (a) 4595 && single_succ (a) == b 4596 && single_pred_p (b) == 1 4597 && a != b 4598 /* Must be simple edge. */ 4599 && !(single_succ_edge (a)->flags & EDGE_COMPLEX) 4600 && a != ENTRY_BLOCK_PTR_FOR_FN (cfun) 4601 && b != EXIT_BLOCK_PTR_FOR_FN (cfun) 4602 /* If the jump insn has side effects, we can't kill the edge. 4603 When not optimizing, try_redirect_by_replacing_jump will 4604 not allow us to redirect an edge by replacing a table jump. */ 4605 && (!JUMP_P (BB_END (a)) 4606 || ((!optimize || reload_completed) 4607 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a))))); 4608 } 4609 4610 /* Merge block A and B. The blocks must be mergeable. */ 4611 4612 static void 4613 cfg_layout_merge_blocks (basic_block a, basic_block b) 4614 { 4615 bool forwarder_p = (b->flags & BB_FORWARDER_BLOCK) != 0; 4616 rtx_insn *insn; 4617 4618 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a, b)); 4619 4620 if (dump_file) 4621 fprintf (dump_file, "Merging block %d into block %d...\n", b->index, 4622 a->index); 4623 4624 /* If there was a CODE_LABEL beginning B, delete it. */ 4625 if (LABEL_P (BB_HEAD (b))) 4626 { 4627 delete_insn (BB_HEAD (b)); 4628 } 4629 4630 /* We should have fallthru edge in a, or we can do dummy redirection to get 4631 it cleaned up. */ 4632 if (JUMP_P (BB_END (a))) 4633 try_redirect_by_replacing_jump (EDGE_SUCC (a, 0), b, true); 4634 gcc_assert (!JUMP_P (BB_END (a))); 4635 4636 /* When not optimizing and the edge is the only place in RTL which holds 4637 some unique locus, emit a nop with that locus in between. */ 4638 if (!optimize) 4639 emit_nop_for_unique_locus_between (a, b); 4640 4641 /* Move things from b->footer after a->footer. */ 4642 if (BB_FOOTER (b)) 4643 { 4644 if (!BB_FOOTER (a)) 4645 BB_FOOTER (a) = BB_FOOTER (b); 4646 else 4647 { 4648 rtx_insn *last = BB_FOOTER (a); 4649 4650 while (NEXT_INSN (last)) 4651 last = NEXT_INSN (last); 4652 SET_NEXT_INSN (last) = BB_FOOTER (b); 4653 SET_PREV_INSN (BB_FOOTER (b)) = last; 4654 } 4655 BB_FOOTER (b) = NULL; 4656 } 4657 4658 /* Move things from b->header before a->footer. 4659 Note that this may include dead tablejump data, but we don't clean 4660 those up until we go out of cfglayout mode. */ 4661 if (BB_HEADER (b)) 4662 { 4663 if (! BB_FOOTER (a)) 4664 BB_FOOTER (a) = BB_HEADER (b); 4665 else 4666 { 4667 rtx_insn *last = BB_HEADER (b); 4668 4669 while (NEXT_INSN (last)) 4670 last = NEXT_INSN (last); 4671 SET_NEXT_INSN (last) = BB_FOOTER (a); 4672 SET_PREV_INSN (BB_FOOTER (a)) = last; 4673 BB_FOOTER (a) = BB_HEADER (b); 4674 } 4675 BB_HEADER (b) = NULL; 4676 } 4677 4678 /* In the case basic blocks are not adjacent, move them around. */ 4679 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b)) 4680 { 4681 insn = unlink_insn_chain (BB_HEAD (b), BB_END (b)); 4682 4683 emit_insn_after_noloc (insn, BB_END (a), a); 4684 } 4685 /* Otherwise just re-associate the instructions. */ 4686 else 4687 { 4688 insn = BB_HEAD (b); 4689 BB_END (a) = BB_END (b); 4690 } 4691 4692 /* emit_insn_after_noloc doesn't call df_insn_change_bb. 4693 We need to explicitly call. */ 4694 update_bb_for_insn_chain (insn, BB_END (b), a); 4695 4696 /* Skip possible DELETED_LABEL insn. */ 4697 if (!NOTE_INSN_BASIC_BLOCK_P (insn)) 4698 insn = NEXT_INSN (insn); 4699 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn)); 4700 BB_HEAD (b) = BB_END (b) = NULL; 4701 delete_insn (insn); 4702 4703 df_bb_delete (b->index); 4704 4705 /* If B was a forwarder block, propagate the locus on the edge. */ 4706 if (forwarder_p 4707 && LOCATION_LOCUS (EDGE_SUCC (b, 0)->goto_locus) == UNKNOWN_LOCATION) 4708 EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus; 4709 4710 if (dump_file) 4711 fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index); 4712 } 4713 4714 /* Split edge E. */ 4715 4716 static basic_block 4717 cfg_layout_split_edge (edge e) 4718 { 4719 basic_block new_bb = 4720 create_basic_block (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) 4721 ? NEXT_INSN (BB_END (e->src)) : get_insns (), 4722 NULL_RTX, e->src); 4723 4724 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) 4725 BB_COPY_PARTITION (new_bb, e->src); 4726 else 4727 BB_COPY_PARTITION (new_bb, e->dest); 4728 make_edge (new_bb, e->dest, EDGE_FALLTHRU); 4729 redirect_edge_and_branch_force (e, new_bb); 4730 4731 return new_bb; 4732 } 4733 4734 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */ 4735 4736 static void 4737 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED) 4738 { 4739 } 4740 4741 /* Return true if BB contains only labels or non-executable 4742 instructions. */ 4743 4744 static bool 4745 rtl_block_empty_p (basic_block bb) 4746 { 4747 rtx_insn *insn; 4748 4749 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) 4750 || bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) 4751 return true; 4752 4753 FOR_BB_INSNS (bb, insn) 4754 if (NONDEBUG_INSN_P (insn) && !any_uncondjump_p (insn)) 4755 return false; 4756 4757 return true; 4758 } 4759 4760 /* Split a basic block if it ends with a conditional branch and if 4761 the other part of the block is not empty. */ 4762 4763 static basic_block 4764 rtl_split_block_before_cond_jump (basic_block bb) 4765 { 4766 rtx_insn *insn; 4767 rtx_insn *split_point = NULL; 4768 rtx_insn *last = NULL; 4769 bool found_code = false; 4770 4771 FOR_BB_INSNS (bb, insn) 4772 { 4773 if (any_condjump_p (insn)) 4774 split_point = last; 4775 else if (NONDEBUG_INSN_P (insn)) 4776 found_code = true; 4777 last = insn; 4778 } 4779 4780 /* Did not find everything. */ 4781 if (found_code && split_point) 4782 return split_block (bb, split_point)->dest; 4783 else 4784 return NULL; 4785 } 4786 4787 /* Return 1 if BB ends with a call, possibly followed by some 4788 instructions that must stay with the call, 0 otherwise. */ 4789 4790 static bool 4791 rtl_block_ends_with_call_p (basic_block bb) 4792 { 4793 rtx_insn *insn = BB_END (bb); 4794 4795 while (!CALL_P (insn) 4796 && insn != BB_HEAD (bb) 4797 && (keep_with_call_p (insn) 4798 || NOTE_P (insn) 4799 || DEBUG_INSN_P (insn))) 4800 insn = PREV_INSN (insn); 4801 return (CALL_P (insn)); 4802 } 4803 4804 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */ 4805 4806 static bool 4807 rtl_block_ends_with_condjump_p (const_basic_block bb) 4808 { 4809 return any_condjump_p (BB_END (bb)); 4810 } 4811 4812 /* Return true if we need to add fake edge to exit. 4813 Helper function for rtl_flow_call_edges_add. */ 4814 4815 static bool 4816 need_fake_edge_p (const rtx_insn *insn) 4817 { 4818 if (!INSN_P (insn)) 4819 return false; 4820 4821 if ((CALL_P (insn) 4822 && !SIBLING_CALL_P (insn) 4823 && !find_reg_note (insn, REG_NORETURN, NULL) 4824 && !(RTL_CONST_OR_PURE_CALL_P (insn)))) 4825 return true; 4826 4827 return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS 4828 && MEM_VOLATILE_P (PATTERN (insn))) 4829 || (GET_CODE (PATTERN (insn)) == PARALLEL 4830 && asm_noperands (insn) != -1 4831 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0))) 4832 || GET_CODE (PATTERN (insn)) == ASM_INPUT); 4833 } 4834 4835 /* Add fake edges to the function exit for any non constant and non noreturn 4836 calls, volatile inline assembly in the bitmap of blocks specified by 4837 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks 4838 that were split. 4839 4840 The goal is to expose cases in which entering a basic block does not imply 4841 that all subsequent instructions must be executed. */ 4842 4843 static int 4844 rtl_flow_call_edges_add (sbitmap blocks) 4845 { 4846 int i; 4847 int blocks_split = 0; 4848 int last_bb = last_basic_block_for_fn (cfun); 4849 bool check_last_block = false; 4850 4851 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS) 4852 return 0; 4853 4854 if (! blocks) 4855 check_last_block = true; 4856 else 4857 check_last_block = bitmap_bit_p (blocks, 4858 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb->index); 4859 4860 /* In the last basic block, before epilogue generation, there will be 4861 a fallthru edge to EXIT. Special care is required if the last insn 4862 of the last basic block is a call because make_edge folds duplicate 4863 edges, which would result in the fallthru edge also being marked 4864 fake, which would result in the fallthru edge being removed by 4865 remove_fake_edges, which would result in an invalid CFG. 4866 4867 Moreover, we can't elide the outgoing fake edge, since the block 4868 profiler needs to take this into account in order to solve the minimal 4869 spanning tree in the case that the call doesn't return. 4870 4871 Handle this by adding a dummy instruction in a new last basic block. */ 4872 if (check_last_block) 4873 { 4874 basic_block bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb; 4875 rtx_insn *insn = BB_END (bb); 4876 4877 /* Back up past insns that must be kept in the same block as a call. */ 4878 while (insn != BB_HEAD (bb) 4879 && keep_with_call_p (insn)) 4880 insn = PREV_INSN (insn); 4881 4882 if (need_fake_edge_p (insn)) 4883 { 4884 edge e; 4885 4886 e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun)); 4887 if (e) 4888 { 4889 insert_insn_on_edge (gen_use (const0_rtx), e); 4890 commit_edge_insertions (); 4891 } 4892 } 4893 } 4894 4895 /* Now add fake edges to the function exit for any non constant 4896 calls since there is no way that we can determine if they will 4897 return or not... */ 4898 4899 for (i = NUM_FIXED_BLOCKS; i < last_bb; i++) 4900 { 4901 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i); 4902 rtx_insn *insn; 4903 rtx_insn *prev_insn; 4904 4905 if (!bb) 4906 continue; 4907 4908 if (blocks && !bitmap_bit_p (blocks, i)) 4909 continue; 4910 4911 for (insn = BB_END (bb); ; insn = prev_insn) 4912 { 4913 prev_insn = PREV_INSN (insn); 4914 if (need_fake_edge_p (insn)) 4915 { 4916 edge e; 4917 rtx_insn *split_at_insn = insn; 4918 4919 /* Don't split the block between a call and an insn that should 4920 remain in the same block as the call. */ 4921 if (CALL_P (insn)) 4922 while (split_at_insn != BB_END (bb) 4923 && keep_with_call_p (NEXT_INSN (split_at_insn))) 4924 split_at_insn = NEXT_INSN (split_at_insn); 4925 4926 /* The handling above of the final block before the epilogue 4927 should be enough to verify that there is no edge to the exit 4928 block in CFG already. Calling make_edge in such case would 4929 cause us to mark that edge as fake and remove it later. */ 4930 4931 if (flag_checking && split_at_insn == BB_END (bb)) 4932 { 4933 e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun)); 4934 gcc_assert (e == NULL); 4935 } 4936 4937 /* Note that the following may create a new basic block 4938 and renumber the existing basic blocks. */ 4939 if (split_at_insn != BB_END (bb)) 4940 { 4941 e = split_block (bb, split_at_insn); 4942 if (e) 4943 blocks_split++; 4944 } 4945 4946 edge ne = make_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE); 4947 ne->probability = profile_probability::guessed_never (); 4948 } 4949 4950 if (insn == BB_HEAD (bb)) 4951 break; 4952 } 4953 } 4954 4955 if (blocks_split) 4956 verify_flow_info (); 4957 4958 return blocks_split; 4959 } 4960 4961 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is 4962 the conditional branch target, SECOND_HEAD should be the fall-thru 4963 there is no need to handle this here the loop versioning code handles 4964 this. the reason for SECON_HEAD is that it is needed for condition 4965 in trees, and this should be of the same type since it is a hook. */ 4966 static void 4967 rtl_lv_add_condition_to_bb (basic_block first_head , 4968 basic_block second_head ATTRIBUTE_UNUSED, 4969 basic_block cond_bb, void *comp_rtx) 4970 { 4971 rtx_code_label *label; 4972 rtx_insn *seq, *jump; 4973 rtx op0 = XEXP ((rtx)comp_rtx, 0); 4974 rtx op1 = XEXP ((rtx)comp_rtx, 1); 4975 enum rtx_code comp = GET_CODE ((rtx)comp_rtx); 4976 machine_mode mode; 4977 4978 4979 label = block_label (first_head); 4980 mode = GET_MODE (op0); 4981 if (mode == VOIDmode) 4982 mode = GET_MODE (op1); 4983 4984 start_sequence (); 4985 op0 = force_operand (op0, NULL_RTX); 4986 op1 = force_operand (op1, NULL_RTX); 4987 do_compare_rtx_and_jump (op0, op1, comp, 0, mode, NULL_RTX, NULL, label, 4988 profile_probability::uninitialized ()); 4989 jump = get_last_insn (); 4990 JUMP_LABEL (jump) = label; 4991 LABEL_NUSES (label)++; 4992 seq = get_insns (); 4993 end_sequence (); 4994 4995 /* Add the new cond, in the new head. */ 4996 emit_insn_after (seq, BB_END (cond_bb)); 4997 } 4998 4999 5000 /* Given a block B with unconditional branch at its end, get the 5001 store the return the branch edge and the fall-thru edge in 5002 BRANCH_EDGE and FALLTHRU_EDGE respectively. */ 5003 static void 5004 rtl_extract_cond_bb_edges (basic_block b, edge *branch_edge, 5005 edge *fallthru_edge) 5006 { 5007 edge e = EDGE_SUCC (b, 0); 5008 5009 if (e->flags & EDGE_FALLTHRU) 5010 { 5011 *fallthru_edge = e; 5012 *branch_edge = EDGE_SUCC (b, 1); 5013 } 5014 else 5015 { 5016 *branch_edge = e; 5017 *fallthru_edge = EDGE_SUCC (b, 1); 5018 } 5019 } 5020 5021 void 5022 init_rtl_bb_info (basic_block bb) 5023 { 5024 gcc_assert (!bb->il.x.rtl); 5025 bb->il.x.head_ = NULL; 5026 bb->il.x.rtl = ggc_cleared_alloc<rtl_bb_info> (); 5027 } 5028 5029 /* Returns true if it is possible to remove edge E by redirecting 5030 it to the destination of the other edge from E->src. */ 5031 5032 static bool 5033 rtl_can_remove_branch_p (const_edge e) 5034 { 5035 const_basic_block src = e->src; 5036 const_basic_block target = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest; 5037 const rtx_insn *insn = BB_END (src); 5038 rtx set; 5039 5040 /* The conditions are taken from try_redirect_by_replacing_jump. */ 5041 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun)) 5042 return false; 5043 5044 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)) 5045 return false; 5046 5047 if (BB_PARTITION (src) != BB_PARTITION (target)) 5048 return false; 5049 5050 if (!onlyjump_p (insn) 5051 || tablejump_p (insn, NULL, NULL)) 5052 return false; 5053 5054 set = single_set (insn); 5055 if (!set || side_effects_p (set)) 5056 return false; 5057 5058 return true; 5059 } 5060 5061 static basic_block 5062 rtl_duplicate_bb (basic_block bb) 5063 { 5064 bb = cfg_layout_duplicate_bb (bb); 5065 bb->aux = NULL; 5066 return bb; 5067 } 5068 5069 /* Do book-keeping of basic block BB for the profile consistency checker. 5070 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1 5071 then do post-pass accounting. Store the counting in RECORD. */ 5072 static void 5073 rtl_account_profile_record (basic_block bb, int after_pass, 5074 struct profile_record *record) 5075 { 5076 rtx_insn *insn; 5077 FOR_BB_INSNS (bb, insn) 5078 if (INSN_P (insn)) 5079 { 5080 record->size[after_pass] += insn_cost (insn, false); 5081 if (bb->count.initialized_p ()) 5082 record->time[after_pass] 5083 += insn_cost (insn, true) * bb->count.to_gcov_type (); 5084 else if (profile_status_for_fn (cfun) == PROFILE_GUESSED) 5085 record->time[after_pass] 5086 += insn_cost (insn, true) * bb->count.to_frequency (cfun); 5087 } 5088 } 5089 5090 /* Implementation of CFG manipulation for linearized RTL. */ 5091 struct cfg_hooks rtl_cfg_hooks = { 5092 "rtl", 5093 rtl_verify_flow_info, 5094 rtl_dump_bb, 5095 rtl_dump_bb_for_graph, 5096 rtl_create_basic_block, 5097 rtl_redirect_edge_and_branch, 5098 rtl_redirect_edge_and_branch_force, 5099 rtl_can_remove_branch_p, 5100 rtl_delete_block, 5101 rtl_split_block, 5102 rtl_move_block_after, 5103 rtl_can_merge_blocks, /* can_merge_blocks_p */ 5104 rtl_merge_blocks, 5105 rtl_predict_edge, 5106 rtl_predicted_by_p, 5107 cfg_layout_can_duplicate_bb_p, 5108 rtl_duplicate_bb, 5109 rtl_split_edge, 5110 rtl_make_forwarder_block, 5111 rtl_tidy_fallthru_edge, 5112 rtl_force_nonfallthru, 5113 rtl_block_ends_with_call_p, 5114 rtl_block_ends_with_condjump_p, 5115 rtl_flow_call_edges_add, 5116 NULL, /* execute_on_growing_pred */ 5117 NULL, /* execute_on_shrinking_pred */ 5118 NULL, /* duplicate loop for trees */ 5119 NULL, /* lv_add_condition_to_bb */ 5120 NULL, /* lv_adjust_loop_header_phi*/ 5121 NULL, /* extract_cond_bb_edges */ 5122 NULL, /* flush_pending_stmts */ 5123 rtl_block_empty_p, /* block_empty_p */ 5124 rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */ 5125 rtl_account_profile_record, 5126 }; 5127 5128 /* Implementation of CFG manipulation for cfg layout RTL, where 5129 basic block connected via fallthru edges does not have to be adjacent. 5130 This representation will hopefully become the default one in future 5131 version of the compiler. */ 5132 5133 struct cfg_hooks cfg_layout_rtl_cfg_hooks = { 5134 "cfglayout mode", 5135 rtl_verify_flow_info_1, 5136 rtl_dump_bb, 5137 rtl_dump_bb_for_graph, 5138 cfg_layout_create_basic_block, 5139 cfg_layout_redirect_edge_and_branch, 5140 cfg_layout_redirect_edge_and_branch_force, 5141 rtl_can_remove_branch_p, 5142 cfg_layout_delete_block, 5143 cfg_layout_split_block, 5144 rtl_move_block_after, 5145 cfg_layout_can_merge_blocks_p, 5146 cfg_layout_merge_blocks, 5147 rtl_predict_edge, 5148 rtl_predicted_by_p, 5149 cfg_layout_can_duplicate_bb_p, 5150 cfg_layout_duplicate_bb, 5151 cfg_layout_split_edge, 5152 rtl_make_forwarder_block, 5153 NULL, /* tidy_fallthru_edge */ 5154 rtl_force_nonfallthru, 5155 rtl_block_ends_with_call_p, 5156 rtl_block_ends_with_condjump_p, 5157 rtl_flow_call_edges_add, 5158 NULL, /* execute_on_growing_pred */ 5159 NULL, /* execute_on_shrinking_pred */ 5160 duplicate_loop_to_header_edge, /* duplicate loop for trees */ 5161 rtl_lv_add_condition_to_bb, /* lv_add_condition_to_bb */ 5162 NULL, /* lv_adjust_loop_header_phi*/ 5163 rtl_extract_cond_bb_edges, /* extract_cond_bb_edges */ 5164 NULL, /* flush_pending_stmts */ 5165 rtl_block_empty_p, /* block_empty_p */ 5166 rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */ 5167 rtl_account_profile_record, 5168 }; 5169 5170 #include "gt-cfgrtl.h" 5171