190075Sobrien/* Control flow graph manipulation code for GNU compiler. 290075Sobrien Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 3169689Skan 1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 490075Sobrien 590075SobrienThis file is part of GCC. 690075Sobrien 790075SobrienGCC is free software; you can redistribute it and/or modify it under 890075Sobrienthe terms of the GNU General Public License as published by the Free 990075SobrienSoftware Foundation; either version 2, or (at your option) any later 1090075Sobrienversion. 1190075Sobrien 1290075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1390075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1490075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1590075Sobrienfor more details. 1690075Sobrien 1790075SobrienYou should have received a copy of the GNU General Public License 1890075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. */ 2190075Sobrien 2290075Sobrien/* This file contains low level functions to manipulate the CFG and analyze it 2390075Sobrien that are aware of the RTL intermediate language. 2490075Sobrien 2590075Sobrien Available functionality: 26132718Skan - Basic CFG/RTL manipulation API documented in cfghooks.h 2790075Sobrien - CFG-aware instruction chain manipulation 2890075Sobrien delete_insn, delete_insn_chain 29132718Skan - Edge splitting and committing to edges 30132718Skan insert_insn_on_edge, commit_edge_insertions 31132718Skan - CFG updating after insn simplification 32132718Skan purge_dead_edges, purge_all_dead_edges 33132718Skan 34132718Skan Functions not supposed for generic use: 3590075Sobrien - Infrastructure to determine quickly basic block for insn 3690075Sobrien compute_bb_for_insn, update_bb_for_insn, set_block_for_insn, 3790075Sobrien - Edge redirection with updating and optimizing of insn chain 38132718Skan block_label, tidy_fallthru_edge, force_nonfallthru */ 3990075Sobrien 4090075Sobrien#include "config.h" 4190075Sobrien#include "system.h" 42132718Skan#include "coretypes.h" 43132718Skan#include "tm.h" 4490075Sobrien#include "tree.h" 4590075Sobrien#include "rtl.h" 4690075Sobrien#include "hard-reg-set.h" 4790075Sobrien#include "basic-block.h" 4890075Sobrien#include "regs.h" 4990075Sobrien#include "flags.h" 5090075Sobrien#include "output.h" 5190075Sobrien#include "function.h" 5290075Sobrien#include "except.h" 5390075Sobrien#include "toplev.h" 5490075Sobrien#include "tm_p.h" 5590075Sobrien#include "obstack.h" 56117395Skan#include "insn-config.h" 57132718Skan#include "cfglayout.h" 58132718Skan#include "expr.h" 59169689Skan#include "target.h" 60169689Skan#include "cfgloop.h" 61169689Skan#include "ggc.h" 62169689Skan#include "tree-pass.h" 6390075Sobrien 64132718Skanstatic int can_delete_note_p (rtx); 65132718Skanstatic int can_delete_label_p (rtx); 66132718Skanstatic void commit_one_edge_insertion (edge, int); 67132718Skanstatic basic_block rtl_split_edge (edge); 68169689Skanstatic bool rtl_move_block_after (basic_block, basic_block); 69132718Skanstatic int rtl_verify_flow_info (void); 70169689Skanstatic basic_block cfg_layout_split_block (basic_block, void *); 71169689Skanstatic edge cfg_layout_redirect_edge_and_branch (edge, basic_block); 72132718Skanstatic basic_block cfg_layout_redirect_edge_and_branch_force (edge, basic_block); 73132718Skanstatic void cfg_layout_delete_block (basic_block); 74132718Skanstatic void rtl_delete_block (basic_block); 75132718Skanstatic basic_block rtl_redirect_edge_and_branch_force (edge, basic_block); 76169689Skanstatic edge rtl_redirect_edge_and_branch (edge, basic_block); 77169689Skanstatic basic_block rtl_split_block (basic_block, void *); 78169689Skanstatic void rtl_dump_bb (basic_block, FILE *, int); 79132718Skanstatic int rtl_verify_flow_info_1 (void); 80169689Skanstatic void rtl_make_forwarder_block (edge); 8190075Sobrien 8290075Sobrien/* Return true if NOTE is not one of the ones that must be kept paired, 8390075Sobrien so that we may simply delete it. */ 8490075Sobrien 8590075Sobrienstatic int 86132718Skancan_delete_note_p (rtx note) 8790075Sobrien{ 8890075Sobrien return (NOTE_LINE_NUMBER (note) == NOTE_INSN_DELETED 89169689Skan || NOTE_LINE_NUMBER (note) == NOTE_INSN_BASIC_BLOCK); 9090075Sobrien} 9190075Sobrien 9290075Sobrien/* True if a given label can be deleted. */ 9390075Sobrien 9490075Sobrienstatic int 95132718Skancan_delete_label_p (rtx label) 9690075Sobrien{ 9790075Sobrien return (!LABEL_PRESERVE_P (label) 9890075Sobrien /* User declared labels must be preserved. */ 9990075Sobrien && LABEL_NAME (label) == 0 100169689Skan && !in_expr_list_p (forced_labels, label)); 10190075Sobrien} 10290075Sobrien 10390075Sobrien/* Delete INSN by patching it out. Return the next insn. */ 10490075Sobrien 10590075Sobrienrtx 106132718Skandelete_insn (rtx insn) 10790075Sobrien{ 10890075Sobrien rtx next = NEXT_INSN (insn); 10990075Sobrien rtx note; 11090075Sobrien bool really_delete = true; 11190075Sobrien 112169689Skan if (LABEL_P (insn)) 11390075Sobrien { 11490075Sobrien /* Some labels can't be directly removed from the INSN chain, as they 115169689Skan might be references via variables, constant pool etc. 116169689Skan Convert them to the special NOTE_INSN_DELETED_LABEL note. */ 11790075Sobrien if (! can_delete_label_p (insn)) 11890075Sobrien { 11990075Sobrien const char *name = LABEL_NAME (insn); 12090075Sobrien 12190075Sobrien really_delete = false; 12290075Sobrien PUT_CODE (insn, NOTE); 12390075Sobrien NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED_LABEL; 124169689Skan NOTE_DELETED_LABEL_NAME (insn) = name; 12590075Sobrien } 12690075Sobrien 12790075Sobrien remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels); 12890075Sobrien } 12990075Sobrien 13090075Sobrien if (really_delete) 13190075Sobrien { 13290075Sobrien /* If this insn has already been deleted, something is very wrong. */ 133169689Skan gcc_assert (!INSN_DELETED_P (insn)); 13490075Sobrien remove_insn (insn); 13590075Sobrien INSN_DELETED_P (insn) = 1; 13690075Sobrien } 13790075Sobrien 13890075Sobrien /* If deleting a jump, decrement the use count of the label. Deleting 13990075Sobrien the label itself should happen in the normal course of block merging. */ 140169689Skan if (JUMP_P (insn) 14190075Sobrien && JUMP_LABEL (insn) 142169689Skan && LABEL_P (JUMP_LABEL (insn))) 14390075Sobrien LABEL_NUSES (JUMP_LABEL (insn))--; 14490075Sobrien 14590075Sobrien /* Also if deleting an insn that references a label. */ 146132718Skan else 147132718Skan { 148132718Skan while ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)) != NULL_RTX 149169689Skan && LABEL_P (XEXP (note, 0))) 150132718Skan { 151132718Skan LABEL_NUSES (XEXP (note, 0))--; 152132718Skan remove_note (insn, note); 153132718Skan } 154132718Skan } 15590075Sobrien 156169689Skan if (JUMP_P (insn) 15790075Sobrien && (GET_CODE (PATTERN (insn)) == ADDR_VEC 15890075Sobrien || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)) 15990075Sobrien { 16090075Sobrien rtx pat = PATTERN (insn); 16190075Sobrien int diff_vec_p = GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC; 16290075Sobrien int len = XVECLEN (pat, diff_vec_p); 16390075Sobrien int i; 16490075Sobrien 16590075Sobrien for (i = 0; i < len; i++) 16690075Sobrien { 16790075Sobrien rtx label = XEXP (XVECEXP (pat, diff_vec_p, i), 0); 16890075Sobrien 16990075Sobrien /* When deleting code in bulk (e.g. removing many unreachable 17090075Sobrien blocks) we can delete a label that's a target of the vector 17190075Sobrien before deleting the vector itself. */ 172169689Skan if (!NOTE_P (label)) 17390075Sobrien LABEL_NUSES (label)--; 17490075Sobrien } 17590075Sobrien } 17690075Sobrien 17790075Sobrien return next; 17890075Sobrien} 17990075Sobrien 180117395Skan/* Like delete_insn but also purge dead edges from BB. */ 181117395Skanrtx 182132718Skandelete_insn_and_edges (rtx insn) 183117395Skan{ 184117395Skan rtx x; 185117395Skan bool purge = false; 186117395Skan 187117395Skan if (INSN_P (insn) 188117395Skan && BLOCK_FOR_INSN (insn) 189132718Skan && BB_END (BLOCK_FOR_INSN (insn)) == insn) 190117395Skan purge = true; 191117395Skan x = delete_insn (insn); 192117395Skan if (purge) 193117395Skan purge_dead_edges (BLOCK_FOR_INSN (insn)); 194117395Skan return x; 195117395Skan} 196117395Skan 19790075Sobrien/* Unlink a chain of insns between START and FINISH, leaving notes 19890075Sobrien that must be paired. */ 19990075Sobrien 20090075Sobrienvoid 201132718Skandelete_insn_chain (rtx start, rtx finish) 20290075Sobrien{ 20390075Sobrien rtx next; 20490075Sobrien 20590075Sobrien /* Unchain the insns one by one. It would be quicker to delete all of these 20690075Sobrien with a single unchaining, rather than one at a time, but we need to keep 20790075Sobrien the NOTE's. */ 20890075Sobrien while (1) 20990075Sobrien { 21090075Sobrien next = NEXT_INSN (start); 211169689Skan if (NOTE_P (start) && !can_delete_note_p (start)) 21290075Sobrien ; 21390075Sobrien else 21490075Sobrien next = delete_insn (start); 21590075Sobrien 21690075Sobrien if (start == finish) 21790075Sobrien break; 21890075Sobrien start = next; 21990075Sobrien } 22090075Sobrien} 221117395Skan 222117395Skan/* Like delete_insn but also purge dead edges from BB. */ 223117395Skanvoid 224132718Skandelete_insn_chain_and_edges (rtx first, rtx last) 225117395Skan{ 226117395Skan bool purge = false; 227117395Skan 228117395Skan if (INSN_P (last) 229117395Skan && BLOCK_FOR_INSN (last) 230132718Skan && BB_END (BLOCK_FOR_INSN (last)) == last) 231117395Skan purge = true; 232117395Skan delete_insn_chain (first, last); 233117395Skan if (purge) 234117395Skan purge_dead_edges (BLOCK_FOR_INSN (last)); 235117395Skan} 23690075Sobrien 23790075Sobrien/* Create a new basic block consisting of the instructions between HEAD and END 23890075Sobrien inclusive. This function is designed to allow fast BB construction - reuses 23990075Sobrien the note and basic block struct in BB_NOTE, if any and do not grow 24090075Sobrien BASIC_BLOCK chain and should be used directly only by CFG construction code. 24190075Sobrien END can be NULL in to create new empty basic block before HEAD. Both END 242117395Skan and HEAD can be NULL to create basic block at the end of INSN chain. 243117395Skan AFTER is the basic block we should be put after. */ 24490075Sobrien 24590075Sobrienbasic_block 246132718Skancreate_basic_block_structure (rtx head, rtx end, rtx bb_note, basic_block after) 24790075Sobrien{ 24890075Sobrien basic_block bb; 24990075Sobrien 25090075Sobrien if (bb_note 25190075Sobrien && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL 25290075Sobrien && bb->aux == NULL) 25390075Sobrien { 25490075Sobrien /* If we found an existing note, thread it back onto the chain. */ 25590075Sobrien 25690075Sobrien rtx after; 25790075Sobrien 258169689Skan if (LABEL_P (head)) 25990075Sobrien after = head; 26090075Sobrien else 26190075Sobrien { 26290075Sobrien after = PREV_INSN (head); 26390075Sobrien head = bb_note; 26490075Sobrien } 26590075Sobrien 26690075Sobrien if (after != bb_note && NEXT_INSN (after) != bb_note) 267117395Skan reorder_insns_nobb (bb_note, bb_note, after); 26890075Sobrien } 26990075Sobrien else 27090075Sobrien { 27190075Sobrien /* Otherwise we must create a note and a basic block structure. */ 27290075Sobrien 27390075Sobrien bb = alloc_block (); 27490075Sobrien 275169689Skan init_rtl_bb_info (bb); 27690075Sobrien if (!head && !end) 27790075Sobrien head = end = bb_note 27890075Sobrien = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ()); 279169689Skan else if (LABEL_P (head) && end) 28090075Sobrien { 28190075Sobrien bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head); 28290075Sobrien if (head == end) 28390075Sobrien end = bb_note; 28490075Sobrien } 28590075Sobrien else 28690075Sobrien { 28790075Sobrien bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head); 28890075Sobrien head = bb_note; 28990075Sobrien if (!end) 29090075Sobrien end = head; 29190075Sobrien } 29290075Sobrien 29390075Sobrien NOTE_BASIC_BLOCK (bb_note) = bb; 29490075Sobrien } 29590075Sobrien 29690075Sobrien /* Always include the bb note in the block. */ 29790075Sobrien if (NEXT_INSN (end) == bb_note) 29890075Sobrien end = bb_note; 29990075Sobrien 300132718Skan BB_HEAD (bb) = head; 301132718Skan BB_END (bb) = end; 302117395Skan bb->index = last_basic_block++; 303169689Skan bb->flags = BB_NEW | BB_RTL; 304117395Skan link_block (bb, after); 305169689Skan SET_BASIC_BLOCK (bb->index, bb); 306117395Skan update_bb_for_insn (bb); 307169689Skan BB_SET_PARTITION (bb, BB_UNPARTITIONED); 30890075Sobrien 30990075Sobrien /* Tag the block so that we know it has been used when considering 31090075Sobrien other basic block notes. */ 31190075Sobrien bb->aux = bb; 31290075Sobrien 31390075Sobrien return bb; 31490075Sobrien} 31590075Sobrien 31690075Sobrien/* Create new basic block consisting of instructions in between HEAD and END 317117395Skan and place it to the BB chain after block AFTER. END can be NULL in to 31890075Sobrien create new empty basic block before HEAD. Both END and HEAD can be NULL to 31990075Sobrien create basic block at the end of INSN chain. */ 32090075Sobrien 321132718Skanstatic basic_block 322132718Skanrtl_create_basic_block (void *headp, void *endp, basic_block after) 32390075Sobrien{ 324132718Skan rtx head = headp, end = endp; 32590075Sobrien basic_block bb; 32690075Sobrien 327169689Skan /* Grow the basic block array if needed. */ 328169689Skan if ((size_t) last_basic_block >= VEC_length (basic_block, basic_block_info)) 329169689Skan { 330169689Skan size_t old_size = VEC_length (basic_block, basic_block_info); 331169689Skan size_t new_size = last_basic_block + (last_basic_block + 3) / 4; 332169689Skan basic_block *p; 333169689Skan VEC_safe_grow (basic_block, gc, basic_block_info, new_size); 334169689Skan p = VEC_address (basic_block, basic_block_info); 335169689Skan memset (&p[old_size], 0, sizeof (basic_block) * (new_size - old_size)); 336169689Skan } 33790075Sobrien 338117395Skan n_basic_blocks++; 33990075Sobrien 340117395Skan bb = create_basic_block_structure (head, end, NULL, after); 34190075Sobrien bb->aux = NULL; 34290075Sobrien return bb; 34390075Sobrien} 344132718Skan 345132718Skanstatic basic_block 346132718Skancfg_layout_create_basic_block (void *head, void *end, basic_block after) 347132718Skan{ 348132718Skan basic_block newbb = rtl_create_basic_block (head, end, after); 349132718Skan 350132718Skan return newbb; 351132718Skan} 35290075Sobrien 35390075Sobrien/* Delete the insns in a (non-live) block. We physically delete every 35490075Sobrien non-deleted-note insn, and update the flow graph appropriately. 35590075Sobrien 35690075Sobrien Return nonzero if we deleted an exception handler. */ 35790075Sobrien 35890075Sobrien/* ??? Preserving all such notes strikes me as wrong. It would be nice 35990075Sobrien to post-process the stream to remove empty blocks, loops, ranges, etc. */ 36090075Sobrien 361132718Skanstatic void 362132718Skanrtl_delete_block (basic_block b) 36390075Sobrien{ 364169689Skan rtx insn, end; 36590075Sobrien 36690075Sobrien /* If the head of this block is a CODE_LABEL, then it might be the 367169689Skan label for an exception handler which can't be reached. We need 368169689Skan to remove the label from the exception_handler_label list. */ 369132718Skan insn = BB_HEAD (b); 370169689Skan if (LABEL_P (insn)) 37190075Sobrien maybe_remove_eh_handler (insn); 37290075Sobrien 373169689Skan end = get_last_bb_insn (b); 37490075Sobrien 37590075Sobrien /* Selectively delete the entire chain. */ 376132718Skan BB_HEAD (b) = NULL; 37790075Sobrien delete_insn_chain (insn, end); 378169689Skan if (b->il.rtl->global_live_at_start) 379169689Skan { 380169689Skan FREE_REG_SET (b->il.rtl->global_live_at_start); 381169689Skan FREE_REG_SET (b->il.rtl->global_live_at_end); 382169689Skan b->il.rtl->global_live_at_start = NULL; 383169689Skan b->il.rtl->global_live_at_end = NULL; 384169689Skan } 38590075Sobrien} 38690075Sobrien 387117395Skan/* Records the basic block struct in BLOCK_FOR_INSN for every insn. */ 38890075Sobrien 38990075Sobrienvoid 390132718Skancompute_bb_for_insn (void) 39190075Sobrien{ 392117395Skan basic_block bb; 39390075Sobrien 394117395Skan FOR_EACH_BB (bb) 39590075Sobrien { 396132718Skan rtx end = BB_END (bb); 39790075Sobrien rtx insn; 39890075Sobrien 399132718Skan for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn)) 40090075Sobrien { 401117395Skan BLOCK_FOR_INSN (insn) = bb; 40290075Sobrien if (insn == end) 40390075Sobrien break; 40490075Sobrien } 40590075Sobrien } 40690075Sobrien} 40790075Sobrien 40890075Sobrien/* Release the basic_block_for_insn array. */ 40990075Sobrien 410169689Skanunsigned int 411132718Skanfree_bb_for_insn (void) 41290075Sobrien{ 413117395Skan rtx insn; 414117395Skan for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 415169689Skan if (!BARRIER_P (insn)) 416117395Skan BLOCK_FOR_INSN (insn) = NULL; 417169689Skan return 0; 41890075Sobrien} 41990075Sobrien 420169689Skanstruct tree_opt_pass pass_free_cfg = 421169689Skan{ 422169689Skan NULL, /* name */ 423169689Skan NULL, /* gate */ 424169689Skan free_bb_for_insn, /* execute */ 425169689Skan NULL, /* sub */ 426169689Skan NULL, /* next */ 427169689Skan 0, /* static_pass_number */ 428169689Skan 0, /* tv_id */ 429169689Skan 0, /* properties_required */ 430169689Skan 0, /* properties_provided */ 431169689Skan PROP_cfg, /* properties_destroyed */ 432169689Skan 0, /* todo_flags_start */ 433169689Skan 0, /* todo_flags_finish */ 434169689Skan 0 /* letter */ 435169689Skan}; 436169689Skan 437169689Skan/* Return RTX to emit after when we want to emit code on the entry of function. */ 438169689Skanrtx 439169689Skanentry_of_function (void) 440169689Skan{ 441169689Skan return (n_basic_blocks > NUM_FIXED_BLOCKS ? 442169689Skan BB_HEAD (ENTRY_BLOCK_PTR->next_bb) : get_insns ()); 443169689Skan} 444169689Skan 445169689Skan/* Emit INSN at the entry point of the function, ensuring that it is only 446169689Skan executed once per function. */ 447169689Skanvoid 448169689Skanemit_insn_at_entry (rtx insn) 449169689Skan{ 450169689Skan edge_iterator ei = ei_start (ENTRY_BLOCK_PTR->succs); 451169689Skan edge e = ei_safe_edge (ei); 452169689Skan gcc_assert (e->flags & EDGE_FALLTHRU); 453169689Skan 454169689Skan insert_insn_on_edge (insn, e); 455169689Skan commit_edge_insertions (); 456169689Skan} 457169689Skan 45890075Sobrien/* Update insns block within BB. */ 45990075Sobrien 46090075Sobrienvoid 461132718Skanupdate_bb_for_insn (basic_block bb) 46290075Sobrien{ 46390075Sobrien rtx insn; 46490075Sobrien 465132718Skan for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn)) 46690075Sobrien { 467169689Skan if (!BARRIER_P (insn)) 468132718Skan set_block_for_insn (insn, bb); 469132718Skan if (insn == BB_END (bb)) 47090075Sobrien break; 47190075Sobrien } 47290075Sobrien} 47390075Sobrien 474169689Skan/* Creates a new basic block just after basic block B by splitting 475169689Skan everything after specified instruction I. */ 47690075Sobrien 477169689Skanstatic basic_block 478132718Skanrtl_split_block (basic_block bb, void *insnp) 47990075Sobrien{ 48090075Sobrien basic_block new_bb; 481169689Skan rtx insn = insnp; 48290075Sobrien edge e; 483169689Skan edge_iterator ei; 48490075Sobrien 485146895Skan if (!insn) 486146895Skan { 487146895Skan insn = first_insn_after_basic_block_note (bb); 48890075Sobrien 489146895Skan if (insn) 490146895Skan insn = PREV_INSN (insn); 491146895Skan else 492146895Skan insn = get_last_insn (); 493146895Skan } 494146895Skan 495146895Skan /* We probably should check type of the insn so that we do not create 496146895Skan inconsistent cfg. It is checked in verify_flow_info anyway, so do not 497146895Skan bother. */ 498146895Skan if (insn == BB_END (bb)) 499146895Skan emit_note_after (NOTE_INSN_DELETED, insn); 500146895Skan 50190075Sobrien /* Create the new basic block. */ 502132718Skan new_bb = create_basic_block (NEXT_INSN (insn), BB_END (bb), bb); 503169689Skan BB_COPY_PARTITION (new_bb, bb); 504132718Skan BB_END (bb) = insn; 50590075Sobrien 50690075Sobrien /* Redirect the outgoing edges. */ 507169689Skan new_bb->succs = bb->succs; 508169689Skan bb->succs = NULL; 509169689Skan FOR_EACH_EDGE (e, ei, new_bb->succs) 51090075Sobrien e->src = new_bb; 51190075Sobrien 512169689Skan if (bb->il.rtl->global_live_at_start) 51390075Sobrien { 514169689Skan new_bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack); 515169689Skan new_bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack); 516169689Skan COPY_REG_SET (new_bb->il.rtl->global_live_at_end, bb->il.rtl->global_live_at_end); 51790075Sobrien 51890075Sobrien /* We now have to calculate which registers are live at the end 51990075Sobrien of the split basic block and at the start of the new basic 52090075Sobrien block. Start with those registers that are known to be live 52190075Sobrien at the end of the original basic block and get 52290075Sobrien propagate_block to determine which registers are live. */ 523169689Skan COPY_REG_SET (new_bb->il.rtl->global_live_at_start, bb->il.rtl->global_live_at_end); 524169689Skan propagate_block (new_bb, new_bb->il.rtl->global_live_at_start, NULL, NULL, 0); 525169689Skan COPY_REG_SET (bb->il.rtl->global_live_at_end, 526169689Skan new_bb->il.rtl->global_live_at_start); 527117395Skan#ifdef HAVE_conditional_execution 528117395Skan /* In the presence of conditional execution we are not able to update 529117395Skan liveness precisely. */ 530117395Skan if (reload_completed) 531117395Skan { 532117395Skan bb->flags |= BB_DIRTY; 533117395Skan new_bb->flags |= BB_DIRTY; 534117395Skan } 535117395Skan#endif 53690075Sobrien } 53790075Sobrien 538169689Skan return new_bb; 53990075Sobrien} 54090075Sobrien 54190075Sobrien/* Blocks A and B are to be merged into a single block A. The insns 542132718Skan are already contiguous. */ 54390075Sobrien 544132718Skanstatic void 545132718Skanrtl_merge_blocks (basic_block a, basic_block b) 54690075Sobrien{ 547132718Skan rtx b_head = BB_HEAD (b), b_end = BB_END (b), a_end = BB_END (a); 54890075Sobrien rtx del_first = NULL_RTX, del_last = NULL_RTX; 54990075Sobrien int b_empty = 0; 55090075Sobrien 55190075Sobrien /* If there was a CODE_LABEL beginning B, delete it. */ 552169689Skan if (LABEL_P (b_head)) 55390075Sobrien { 554169689Skan /* This might have been an EH label that no longer has incoming 555169689Skan EH edges. Update data structures to match. */ 556169689Skan maybe_remove_eh_handler (b_head); 557169689Skan 55890075Sobrien /* Detect basic blocks with nothing but a label. This can happen 55990075Sobrien in particular at the end of a function. */ 56090075Sobrien if (b_head == b_end) 56190075Sobrien b_empty = 1; 56290075Sobrien 56390075Sobrien del_first = del_last = b_head; 56490075Sobrien b_head = NEXT_INSN (b_head); 56590075Sobrien } 56690075Sobrien 56790075Sobrien /* Delete the basic block note and handle blocks containing just that 56890075Sobrien note. */ 56990075Sobrien if (NOTE_INSN_BASIC_BLOCK_P (b_head)) 57090075Sobrien { 57190075Sobrien if (b_head == b_end) 57290075Sobrien b_empty = 1; 57390075Sobrien if (! del_last) 57490075Sobrien del_first = b_head; 57590075Sobrien 57690075Sobrien del_last = b_head; 57790075Sobrien b_head = NEXT_INSN (b_head); 57890075Sobrien } 57990075Sobrien 58090075Sobrien /* If there was a jump out of A, delete it. */ 581169689Skan if (JUMP_P (a_end)) 58290075Sobrien { 58390075Sobrien rtx prev; 58490075Sobrien 58590075Sobrien for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev)) 586169689Skan if (!NOTE_P (prev) 58790075Sobrien || NOTE_LINE_NUMBER (prev) == NOTE_INSN_BASIC_BLOCK 588132718Skan || prev == BB_HEAD (a)) 58990075Sobrien break; 59090075Sobrien 59190075Sobrien del_first = a_end; 59290075Sobrien 59390075Sobrien#ifdef HAVE_cc0 59490075Sobrien /* If this was a conditional jump, we need to also delete 59590075Sobrien the insn that set cc0. */ 59690075Sobrien if (only_sets_cc0_p (prev)) 59790075Sobrien { 59890075Sobrien rtx tmp = prev; 59990075Sobrien 60090075Sobrien prev = prev_nonnote_insn (prev); 60190075Sobrien if (!prev) 602132718Skan prev = BB_HEAD (a); 60390075Sobrien del_first = tmp; 60490075Sobrien } 60590075Sobrien#endif 60690075Sobrien 60790075Sobrien a_end = PREV_INSN (del_first); 60890075Sobrien } 609169689Skan else if (BARRIER_P (NEXT_INSN (a_end))) 61090075Sobrien del_first = NEXT_INSN (a_end); 61190075Sobrien 61290075Sobrien /* Delete everything marked above as well as crap that might be 61390075Sobrien hanging out between the two blocks. */ 614169689Skan BB_HEAD (b) = NULL; 61590075Sobrien delete_insn_chain (del_first, del_last); 61690075Sobrien 61790075Sobrien /* Reassociate the insns of B with A. */ 61890075Sobrien if (!b_empty) 61990075Sobrien { 620117395Skan rtx x; 62190075Sobrien 622117395Skan for (x = a_end; x != b_end; x = NEXT_INSN (x)) 623117395Skan set_block_for_insn (x, a); 62490075Sobrien 625117395Skan set_block_for_insn (b_end, a); 62690075Sobrien 62790075Sobrien a_end = b_end; 62890075Sobrien } 62990075Sobrien 630132718Skan BB_END (a) = a_end; 631169689Skan a->il.rtl->global_live_at_end = b->il.rtl->global_live_at_end; 63290075Sobrien} 633132718Skan 634132718Skan/* Return true when block A and B can be merged. */ 635132718Skanstatic bool 636132718Skanrtl_can_merge_blocks (basic_block a,basic_block b) 637132718Skan{ 638169689Skan /* If we are partitioning hot/cold basic blocks, we don't want to 639169689Skan mess up unconditional or indirect jumps that cross between hot 640169689Skan and cold sections. 641169689Skan 642169689Skan Basic block partitioning may result in some jumps that appear to 643169689Skan be optimizable (or blocks that appear to be mergeable), but which really 644169689Skan must be left untouched (they are required to make it safely across 645169689Skan partition boundaries). See the comments at the top of 646169689Skan bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */ 647169689Skan 648169689Skan if (BB_PARTITION (a) != BB_PARTITION (b)) 649169689Skan return false; 650169689Skan 651132718Skan /* There must be exactly one edge in between the blocks. */ 652169689Skan return (single_succ_p (a) 653169689Skan && single_succ (a) == b 654169689Skan && single_pred_p (b) 655169689Skan && a != b 656132718Skan /* Must be simple edge. */ 657169689Skan && !(single_succ_edge (a)->flags & EDGE_COMPLEX) 658132718Skan && a->next_bb == b 659132718Skan && a != ENTRY_BLOCK_PTR && b != EXIT_BLOCK_PTR 660132718Skan /* If the jump insn has side effects, 661132718Skan we can't kill the edge. */ 662169689Skan && (!JUMP_P (BB_END (a)) 663132718Skan || (reload_completed 664132718Skan ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a))))); 665132718Skan} 66690075Sobrien 66790075Sobrien/* Return the label in the head of basic block BLOCK. Create one if it doesn't 66890075Sobrien exist. */ 66990075Sobrien 67090075Sobrienrtx 671132718Skanblock_label (basic_block block) 67290075Sobrien{ 67390075Sobrien if (block == EXIT_BLOCK_PTR) 67490075Sobrien return NULL_RTX; 67590075Sobrien 676169689Skan if (!LABEL_P (BB_HEAD (block))) 67790075Sobrien { 678132718Skan BB_HEAD (block) = emit_label_before (gen_label_rtx (), BB_HEAD (block)); 67990075Sobrien } 68090075Sobrien 681132718Skan return BB_HEAD (block); 68290075Sobrien} 68390075Sobrien 68490075Sobrien/* Attempt to perform edge redirection by replacing possibly complex jump 68590075Sobrien instruction by unconditional jump or removing jump completely. This can 68690075Sobrien apply only if all edges now point to the same block. The parameters and 68790075Sobrien return values are equivalent to redirect_edge_and_branch. */ 68890075Sobrien 689169689Skanedge 690132718Skantry_redirect_by_replacing_jump (edge e, basic_block target, bool in_cfglayout) 69190075Sobrien{ 69290075Sobrien basic_block src = e->src; 693132718Skan rtx insn = BB_END (src), kill_from; 694132718Skan rtx set; 69590075Sobrien int fallthru = 0; 69690075Sobrien 697169689Skan /* If we are partitioning hot/cold basic blocks, we don't want to 698169689Skan mess up unconditional or indirect jumps that cross between hot 699169689Skan and cold sections. 70090075Sobrien 701169689Skan Basic block partitioning may result in some jumps that appear to 702169689Skan be optimizable (or blocks that appear to be mergeable), but which really 703169689Skan must be left untouched (they are required to make it safely across 704169689Skan partition boundaries). See the comments at the top of 705169689Skan bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */ 706169689Skan 707169689Skan if (find_reg_note (insn, REG_CROSSING_JUMP, NULL_RTX) 708169689Skan || BB_PARTITION (src) != BB_PARTITION (target)) 709169689Skan return NULL; 710169689Skan 711169689Skan /* We can replace or remove a complex jump only when we have exactly 712169689Skan two edges. Also, if we have exactly one outgoing edge, we can 713169689Skan redirect that. */ 714169689Skan if (EDGE_COUNT (src->succs) >= 3 715169689Skan /* Verify that all targets will be TARGET. Specifically, the 716169689Skan edge that is not E must also go to TARGET. */ 717169689Skan || (EDGE_COUNT (src->succs) == 2 718169689Skan && EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)) 719169689Skan return NULL; 720169689Skan 721169689Skan if (!onlyjump_p (insn)) 722169689Skan return NULL; 723132718Skan if ((!optimize || reload_completed) && tablejump_p (insn, NULL, NULL)) 724169689Skan return NULL; 725107590Sobrien 72690075Sobrien /* Avoid removing branch with side effects. */ 72790075Sobrien set = single_set (insn); 72890075Sobrien if (!set || side_effects_p (set)) 729169689Skan return NULL; 73090075Sobrien 73190075Sobrien /* In case we zap a conditional jump, we'll need to kill 73290075Sobrien the cc0 setter too. */ 73390075Sobrien kill_from = insn; 73490075Sobrien#ifdef HAVE_cc0 73590075Sobrien if (reg_mentioned_p (cc0_rtx, PATTERN (insn))) 73690075Sobrien kill_from = PREV_INSN (insn); 73790075Sobrien#endif 73890075Sobrien 73990075Sobrien /* See if we can create the fallthru edge. */ 740132718Skan if (in_cfglayout || can_fallthru (src, target)) 74190075Sobrien { 742169689Skan if (dump_file) 743169689Skan fprintf (dump_file, "Removing jump %i.\n", INSN_UID (insn)); 74490075Sobrien fallthru = 1; 74590075Sobrien 74690075Sobrien /* Selectively unlink whole insn chain. */ 747132718Skan if (in_cfglayout) 748132718Skan { 749169689Skan rtx insn = src->il.rtl->footer; 750132718Skan 751169689Skan delete_insn_chain (kill_from, BB_END (src)); 752132718Skan 753132718Skan /* Remove barriers but keep jumptables. */ 754132718Skan while (insn) 755132718Skan { 756169689Skan if (BARRIER_P (insn)) 757132718Skan { 758132718Skan if (PREV_INSN (insn)) 759132718Skan NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn); 760132718Skan else 761169689Skan src->il.rtl->footer = NEXT_INSN (insn); 762132718Skan if (NEXT_INSN (insn)) 763132718Skan PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn); 764132718Skan } 765169689Skan if (LABEL_P (insn)) 766132718Skan break; 767132718Skan insn = NEXT_INSN (insn); 768132718Skan } 769132718Skan } 770132718Skan else 771169689Skan delete_insn_chain (kill_from, PREV_INSN (BB_HEAD (target))); 77290075Sobrien } 77390075Sobrien 77490075Sobrien /* If this already is simplejump, redirect it. */ 77590075Sobrien else if (simplejump_p (insn)) 77690075Sobrien { 77790075Sobrien if (e->dest == target) 778169689Skan return NULL; 779169689Skan if (dump_file) 780169689Skan fprintf (dump_file, "Redirecting jump %i from %i to %i.\n", 78190075Sobrien INSN_UID (insn), e->dest->index, target->index); 78290075Sobrien if (!redirect_jump (insn, block_label (target), 0)) 78390075Sobrien { 784169689Skan gcc_assert (target == EXIT_BLOCK_PTR); 785169689Skan return NULL; 78690075Sobrien } 78790075Sobrien } 78890075Sobrien 78990075Sobrien /* Cannot do anything for target exit block. */ 79090075Sobrien else if (target == EXIT_BLOCK_PTR) 791169689Skan return NULL; 79290075Sobrien 79390075Sobrien /* Or replace possibly complicated jump insn by simple jump insn. */ 79490075Sobrien else 79590075Sobrien { 79690075Sobrien rtx target_label = block_label (target); 797132718Skan rtx barrier, label, table; 79890075Sobrien 799132718Skan emit_jump_insn_after_noloc (gen_jump (target_label), insn); 800132718Skan JUMP_LABEL (BB_END (src)) = target_label; 80190075Sobrien LABEL_NUSES (target_label)++; 802169689Skan if (dump_file) 803169689Skan fprintf (dump_file, "Replacing insn %i by jump %i\n", 804132718Skan INSN_UID (insn), INSN_UID (BB_END (src))); 80590075Sobrien 80696263Sobrien 80790075Sobrien delete_insn_chain (kill_from, insn); 80890075Sobrien 80996263Sobrien /* Recognize a tablejump that we are converting to a 81096263Sobrien simple jump and remove its associated CODE_LABEL 81196263Sobrien and ADDR_VEC or ADDR_DIFF_VEC. */ 812132718Skan if (tablejump_p (insn, &label, &table)) 813132718Skan delete_insn_chain (label, table); 814132718Skan 815132718Skan barrier = next_nonnote_insn (BB_END (src)); 816169689Skan if (!barrier || !BARRIER_P (barrier)) 817132718Skan emit_barrier_after (BB_END (src)); 818132718Skan else 81996263Sobrien { 820132718Skan if (barrier != NEXT_INSN (BB_END (src))) 821132718Skan { 822132718Skan /* Move the jump before barrier so that the notes 823132718Skan which originally were or were created before jump table are 824132718Skan inside the basic block. */ 825132718Skan rtx new_insn = BB_END (src); 826132718Skan rtx tmp; 827132718Skan 828132718Skan for (tmp = NEXT_INSN (BB_END (src)); tmp != barrier; 829132718Skan tmp = NEXT_INSN (tmp)) 830132718Skan set_block_for_insn (tmp, src); 831132718Skan 832132718Skan NEXT_INSN (PREV_INSN (new_insn)) = NEXT_INSN (new_insn); 833132718Skan PREV_INSN (NEXT_INSN (new_insn)) = PREV_INSN (new_insn); 834132718Skan 835132718Skan NEXT_INSN (new_insn) = barrier; 836132718Skan NEXT_INSN (PREV_INSN (barrier)) = new_insn; 837132718Skan 838132718Skan PREV_INSN (new_insn) = PREV_INSN (barrier); 839132718Skan PREV_INSN (barrier) = new_insn; 840132718Skan } 84196263Sobrien } 84290075Sobrien } 84390075Sobrien 84490075Sobrien /* Keep only one edge out and set proper flags. */ 845169689Skan if (!single_succ_p (src)) 846169689Skan remove_edge (e); 847169689Skan gcc_assert (single_succ_p (src)); 848169689Skan 849169689Skan e = single_succ_edge (src); 85090075Sobrien if (fallthru) 85190075Sobrien e->flags = EDGE_FALLTHRU; 85290075Sobrien else 85390075Sobrien e->flags = 0; 85490075Sobrien 85590075Sobrien e->probability = REG_BR_PROB_BASE; 85690075Sobrien e->count = src->count; 85790075Sobrien 85890075Sobrien /* We don't want a block to end on a line-number note since that has 85990075Sobrien the potential of changing the code between -g and not -g. */ 860169689Skan while (NOTE_P (BB_END (e->src)) 861132718Skan && NOTE_LINE_NUMBER (BB_END (e->src)) >= 0) 862132718Skan delete_insn (BB_END (e->src)); 86390075Sobrien 86490075Sobrien if (e->dest != target) 86590075Sobrien redirect_edge_succ (e, target); 86690075Sobrien 867169689Skan return e; 86890075Sobrien} 86990075Sobrien 870169689Skan/* Redirect edge representing branch of (un)conditional jump or tablejump, 871169689Skan NULL on failure */ 872169689Skanstatic edge 873132718Skanredirect_branch_edge (edge e, basic_block target) 87490075Sobrien{ 87590075Sobrien rtx tmp; 876132718Skan rtx old_label = BB_HEAD (e->dest); 87790075Sobrien basic_block src = e->src; 878132718Skan rtx insn = BB_END (src); 87990075Sobrien 88090075Sobrien /* We can only redirect non-fallthru edges of jump insn. */ 88190075Sobrien if (e->flags & EDGE_FALLTHRU) 882169689Skan return NULL; 883169689Skan else if (!JUMP_P (insn)) 884169689Skan return NULL; 88590075Sobrien 88690075Sobrien /* Recognize a tablejump and adjust all matching cases. */ 887132718Skan if (tablejump_p (insn, NULL, &tmp)) 88890075Sobrien { 88990075Sobrien rtvec vec; 89090075Sobrien int j; 89190075Sobrien rtx new_label = block_label (target); 89290075Sobrien 89390075Sobrien if (target == EXIT_BLOCK_PTR) 894169689Skan return NULL; 89590075Sobrien if (GET_CODE (PATTERN (tmp)) == ADDR_VEC) 89690075Sobrien vec = XVEC (PATTERN (tmp), 0); 89790075Sobrien else 89890075Sobrien vec = XVEC (PATTERN (tmp), 1); 89990075Sobrien 90090075Sobrien for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j) 90190075Sobrien if (XEXP (RTVEC_ELT (vec, j), 0) == old_label) 90290075Sobrien { 90390075Sobrien RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label); 90490075Sobrien --LABEL_NUSES (old_label); 90590075Sobrien ++LABEL_NUSES (new_label); 90690075Sobrien } 90790075Sobrien 908132718Skan /* Handle casesi dispatch insns. */ 90990075Sobrien if ((tmp = single_set (insn)) != NULL 91090075Sobrien && SET_DEST (tmp) == pc_rtx 91190075Sobrien && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE 91290075Sobrien && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF 91390075Sobrien && XEXP (XEXP (SET_SRC (tmp), 2), 0) == old_label) 91490075Sobrien { 915169689Skan XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (Pmode, 91690075Sobrien new_label); 91790075Sobrien --LABEL_NUSES (old_label); 91890075Sobrien ++LABEL_NUSES (new_label); 91990075Sobrien } 92090075Sobrien } 92190075Sobrien else 92290075Sobrien { 92390075Sobrien /* ?? We may play the games with moving the named labels from 92490075Sobrien one basic block to the other in case only one computed_jump is 92590075Sobrien available. */ 92690075Sobrien if (computed_jump_p (insn) 92790075Sobrien /* A return instruction can't be redirected. */ 92890075Sobrien || returnjump_p (insn)) 929169689Skan return NULL; 93090075Sobrien 93190075Sobrien /* If the insn doesn't go where we think, we're confused. */ 932169689Skan gcc_assert (JUMP_LABEL (insn) == old_label); 93390075Sobrien 93490075Sobrien /* If the substitution doesn't succeed, die. This can happen 93590075Sobrien if the back end emitted unrecognizable instructions or if 93690075Sobrien target is exit block on some arches. */ 93790075Sobrien if (!redirect_jump (insn, block_label (target), 0)) 93890075Sobrien { 939169689Skan gcc_assert (target == EXIT_BLOCK_PTR); 940169689Skan return NULL; 94190075Sobrien } 94290075Sobrien } 94390075Sobrien 944169689Skan if (dump_file) 945169689Skan fprintf (dump_file, "Edge %i->%i redirected to %i\n", 94690075Sobrien e->src->index, e->dest->index, target->index); 94790075Sobrien 94890075Sobrien if (e->dest != target) 949169689Skan e = redirect_edge_succ_nodup (e, target); 950169689Skan return e; 951132718Skan} 95290075Sobrien 953132718Skan/* Attempt to change code to redirect edge E to TARGET. Don't do that on 954132718Skan expense of adding new instructions or reordering basic blocks. 955132718Skan 956132718Skan Function can be also called with edge destination equivalent to the TARGET. 957132718Skan Then it should try the simplifications and do nothing if none is possible. 958132718Skan 959169689Skan Return edge representing the branch if transformation succeeded. Return NULL 960169689Skan on failure. 961169689Skan We still return NULL in case E already destinated TARGET and we didn't 962169689Skan managed to simplify instruction stream. */ 963132718Skan 964169689Skanstatic edge 965132718Skanrtl_redirect_edge_and_branch (edge e, basic_block target) 966132718Skan{ 967169689Skan edge ret; 968169689Skan basic_block src = e->src; 969169689Skan 970132718Skan if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)) 971169689Skan return NULL; 972132718Skan 973132718Skan if (e->dest == target) 974169689Skan return e; 975132718Skan 976169689Skan if ((ret = try_redirect_by_replacing_jump (e, target, false)) != NULL) 977169689Skan { 978169689Skan src->flags |= BB_DIRTY; 979169689Skan return ret; 980169689Skan } 981132718Skan 982169689Skan ret = redirect_branch_edge (e, target); 983169689Skan if (!ret) 984169689Skan return NULL; 985132718Skan 986169689Skan src->flags |= BB_DIRTY; 987169689Skan return ret; 98890075Sobrien} 98990075Sobrien 99090075Sobrien/* Like force_nonfallthru below, but additionally performs redirection 99190075Sobrien Used by redirect_edge_and_branch_force. */ 99290075Sobrien 993169689Skanstatic basic_block 994132718Skanforce_nonfallthru_and_redirect (edge e, basic_block target) 99590075Sobrien{ 996117395Skan basic_block jump_block, new_bb = NULL, src = e->src; 99790075Sobrien rtx note; 99890075Sobrien edge new_edge; 999117395Skan int abnormal_edge_flags = 0; 100090075Sobrien 1001117395Skan /* In the case the last instruction is conditional jump to the next 1002117395Skan instruction, first redirect the jump itself and then continue 1003132718Skan by creating a basic block afterwards to redirect fallthru edge. */ 1004117395Skan if (e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR 1005132718Skan && any_condjump_p (BB_END (e->src)) 1006132718Skan && JUMP_LABEL (BB_END (e->src)) == BB_HEAD (e->dest)) 1007117395Skan { 1008117395Skan rtx note; 1009117395Skan edge b = unchecked_make_edge (e->src, target, 0); 1010169689Skan bool redirected; 1011117395Skan 1012169689Skan redirected = redirect_jump (BB_END (e->src), block_label (target), 0); 1013169689Skan gcc_assert (redirected); 1014169689Skan 1015132718Skan note = find_reg_note (BB_END (e->src), REG_BR_PROB, NULL_RTX); 1016117395Skan if (note) 1017117395Skan { 1018117395Skan int prob = INTVAL (XEXP (note, 0)); 1019117395Skan 1020117395Skan b->probability = prob; 1021117395Skan b->count = e->count * prob / REG_BR_PROB_BASE; 1022117395Skan e->probability -= e->probability; 1023117395Skan e->count -= b->count; 1024117395Skan if (e->probability < 0) 1025117395Skan e->probability = 0; 1026117395Skan if (e->count < 0) 1027117395Skan e->count = 0; 1028117395Skan } 1029117395Skan } 1030117395Skan 103190075Sobrien if (e->flags & EDGE_ABNORMAL) 1032117395Skan { 1033117395Skan /* Irritating special case - fallthru edge to the same block as abnormal 1034117395Skan edge. 1035117395Skan We can't redirect abnormal edge, but we still can split the fallthru 1036132718Skan one and create separate abnormal edge to original destination. 1037117395Skan This allows bb-reorder to make such edge non-fallthru. */ 1038169689Skan gcc_assert (e->dest == target); 1039117395Skan abnormal_edge_flags = e->flags & ~(EDGE_FALLTHRU | EDGE_CAN_FALLTHRU); 1040117395Skan e->flags &= EDGE_FALLTHRU | EDGE_CAN_FALLTHRU; 1041117395Skan } 1042169689Skan else 104390075Sobrien { 1044169689Skan gcc_assert (e->flags & EDGE_FALLTHRU); 1045169689Skan if (e->src == ENTRY_BLOCK_PTR) 1046169689Skan { 1047169689Skan /* We can't redirect the entry block. Create an empty block 1048169689Skan at the start of the function which we use to add the new 1049169689Skan jump. */ 1050169689Skan edge tmp; 1051169689Skan edge_iterator ei; 1052169689Skan bool found = false; 105396263Sobrien 1054169689Skan basic_block bb = create_basic_block (BB_HEAD (e->dest), NULL, ENTRY_BLOCK_PTR); 1055169689Skan 1056169689Skan /* Change the existing edge's source to be the new block, and add 1057169689Skan a new edge from the entry block to the new block. */ 1058169689Skan e->src = bb; 1059169689Skan for (ei = ei_start (ENTRY_BLOCK_PTR->succs); (tmp = ei_safe_edge (ei)); ) 1060169689Skan { 1061169689Skan if (tmp == e) 1062169689Skan { 1063169689Skan VEC_unordered_remove (edge, ENTRY_BLOCK_PTR->succs, ei.index); 1064169689Skan found = true; 1065169689Skan break; 1066169689Skan } 1067169689Skan else 1068169689Skan ei_next (&ei); 1069169689Skan } 1070169689Skan 1071169689Skan gcc_assert (found); 1072169689Skan 1073169689Skan VEC_safe_push (edge, gc, bb->succs, e); 1074169689Skan make_single_succ_edge (ENTRY_BLOCK_PTR, bb, EDGE_FALLTHRU); 1075169689Skan } 107696263Sobrien } 107796263Sobrien 1078169689Skan if (EDGE_COUNT (e->src->succs) >= 2 || abnormal_edge_flags) 107996263Sobrien { 108090075Sobrien /* Create the new structures. */ 1081102780Skan 1082132718Skan /* If the old block ended with a tablejump, skip its table 1083132718Skan by searching forward from there. Otherwise start searching 1084132718Skan forward from the last instruction of the old block. */ 1085132718Skan if (!tablejump_p (BB_END (e->src), NULL, ¬e)) 1086132718Skan note = BB_END (e->src); 1087102780Skan note = NEXT_INSN (note); 1088102780Skan 1089117395Skan jump_block = create_basic_block (note, NULL, e->src); 109090075Sobrien jump_block->count = e->count; 109190075Sobrien jump_block->frequency = EDGE_FREQUENCY (e); 109290075Sobrien jump_block->loop_depth = target->loop_depth; 109390075Sobrien 1094169689Skan if (target->il.rtl->global_live_at_start) 109590075Sobrien { 1096169689Skan jump_block->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack); 1097169689Skan jump_block->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack); 1098169689Skan COPY_REG_SET (jump_block->il.rtl->global_live_at_start, 1099169689Skan target->il.rtl->global_live_at_start); 1100169689Skan COPY_REG_SET (jump_block->il.rtl->global_live_at_end, 1101169689Skan target->il.rtl->global_live_at_start); 110290075Sobrien } 110390075Sobrien 1104169689Skan /* Make sure new block ends up in correct hot/cold section. */ 1105169689Skan 1106169689Skan BB_COPY_PARTITION (jump_block, e->src); 1107169689Skan if (flag_reorder_blocks_and_partition 1108169689Skan && targetm.have_named_sections 1109169689Skan && JUMP_P (BB_END (jump_block)) 1110169689Skan && !any_condjump_p (BB_END (jump_block)) 1111169689Skan && (EDGE_SUCC (jump_block, 0)->flags & EDGE_CROSSING)) 1112169689Skan REG_NOTES (BB_END (jump_block)) = gen_rtx_EXPR_LIST (REG_CROSSING_JUMP, 1113169689Skan NULL_RTX, 1114169689Skan REG_NOTES 1115169689Skan (BB_END 1116169689Skan (jump_block))); 1117169689Skan 111890075Sobrien /* Wire edge in. */ 111990075Sobrien new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU); 112090075Sobrien new_edge->probability = e->probability; 112190075Sobrien new_edge->count = e->count; 112290075Sobrien 112390075Sobrien /* Redirect old edge. */ 112490075Sobrien redirect_edge_pred (e, jump_block); 112590075Sobrien e->probability = REG_BR_PROB_BASE; 112690075Sobrien 112790075Sobrien new_bb = jump_block; 112890075Sobrien } 112990075Sobrien else 113090075Sobrien jump_block = e->src; 113190075Sobrien 113290075Sobrien e->flags &= ~EDGE_FALLTHRU; 113390075Sobrien if (target == EXIT_BLOCK_PTR) 113490075Sobrien { 1135169689Skan#ifdef HAVE_return 1136132718Skan emit_jump_insn_after_noloc (gen_return (), BB_END (jump_block)); 1137169689Skan#else 1138169689Skan gcc_unreachable (); 1139169689Skan#endif 114090075Sobrien } 114190075Sobrien else 114290075Sobrien { 114390075Sobrien rtx label = block_label (target); 1144132718Skan emit_jump_insn_after_noloc (gen_jump (label), BB_END (jump_block)); 1145132718Skan JUMP_LABEL (BB_END (jump_block)) = label; 114690075Sobrien LABEL_NUSES (label)++; 114790075Sobrien } 114890075Sobrien 1149132718Skan emit_barrier_after (BB_END (jump_block)); 115090075Sobrien redirect_edge_succ_nodup (e, target); 115190075Sobrien 1152117395Skan if (abnormal_edge_flags) 1153117395Skan make_edge (src, target, abnormal_edge_flags); 1154117395Skan 115590075Sobrien return new_bb; 115690075Sobrien} 115790075Sobrien 115890075Sobrien/* Edge E is assumed to be fallthru edge. Emit needed jump instruction 115990075Sobrien (and possibly create new basic block) to make edge non-fallthru. 116090075Sobrien Return newly created BB or NULL if none. */ 116190075Sobrien 116290075Sobrienbasic_block 1163132718Skanforce_nonfallthru (edge e) 116490075Sobrien{ 116590075Sobrien return force_nonfallthru_and_redirect (e, e->dest); 116690075Sobrien} 116790075Sobrien 116890075Sobrien/* Redirect edge even at the expense of creating new jump insn or 116990075Sobrien basic block. Return new basic block if created, NULL otherwise. 1170169689Skan Conversion must be possible. */ 117190075Sobrien 1172132718Skanstatic basic_block 1173132718Skanrtl_redirect_edge_and_branch_force (edge e, basic_block target) 117490075Sobrien{ 117590075Sobrien if (redirect_edge_and_branch (e, target) 117690075Sobrien || e->dest == target) 117790075Sobrien return NULL; 117890075Sobrien 117990075Sobrien /* In case the edge redirection failed, try to force it to be non-fallthru 118090075Sobrien and redirect newly created simplejump. */ 1181169689Skan e->src->flags |= BB_DIRTY; 118290075Sobrien return force_nonfallthru_and_redirect (e, target); 118390075Sobrien} 118490075Sobrien 118590075Sobrien/* The given edge should potentially be a fallthru edge. If that is in 118690075Sobrien fact true, delete the jump and barriers that are in the way. */ 118790075Sobrien 1188169689Skanstatic void 1189169689Skanrtl_tidy_fallthru_edge (edge e) 119090075Sobrien{ 119190075Sobrien rtx q; 1192169689Skan basic_block b = e->src, c = b->next_bb; 119390075Sobrien 119490075Sobrien /* ??? In a late-running flow pass, other folks may have deleted basic 119590075Sobrien blocks by nopping out blocks, leaving multiple BARRIERs between here 1196169689Skan and the target label. They ought to be chastised and fixed. 119790075Sobrien 119890075Sobrien We can also wind up with a sequence of undeletable labels between 119990075Sobrien one block and the next. 120090075Sobrien 120190075Sobrien So search through a sequence of barriers, labels, and notes for 120290075Sobrien the head of block C and assert that we really do fall through. */ 120390075Sobrien 1204132718Skan for (q = NEXT_INSN (BB_END (b)); q != BB_HEAD (c); q = NEXT_INSN (q)) 1205117395Skan if (INSN_P (q)) 1206117395Skan return; 120790075Sobrien 120890075Sobrien /* Remove what will soon cease being the jump insn from the source block. 120990075Sobrien If block B consisted only of this single jump, turn it into a deleted 121090075Sobrien note. */ 1211132718Skan q = BB_END (b); 1212169689Skan if (JUMP_P (q) 121390075Sobrien && onlyjump_p (q) 121490075Sobrien && (any_uncondjump_p (q) 1215169689Skan || single_succ_p (b))) 121690075Sobrien { 121790075Sobrien#ifdef HAVE_cc0 121890075Sobrien /* If this was a conditional jump, we need to also delete 121990075Sobrien the insn that set cc0. */ 122090075Sobrien if (any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q))) 122190075Sobrien q = PREV_INSN (q); 122290075Sobrien#endif 122390075Sobrien 122490075Sobrien q = PREV_INSN (q); 122590075Sobrien 122690075Sobrien /* We don't want a block to end on a line-number note since that has 122790075Sobrien the potential of changing the code between -g and not -g. */ 1228169689Skan while (NOTE_P (q) && NOTE_LINE_NUMBER (q) >= 0) 122990075Sobrien q = PREV_INSN (q); 123090075Sobrien } 123190075Sobrien 123290075Sobrien /* Selectively unlink the sequence. */ 1233132718Skan if (q != PREV_INSN (BB_HEAD (c))) 1234132718Skan delete_insn_chain (NEXT_INSN (q), PREV_INSN (BB_HEAD (c))); 123590075Sobrien 123690075Sobrien e->flags |= EDGE_FALLTHRU; 123790075Sobrien} 123890075Sobrien 1239169689Skan/* Should move basic block BB after basic block AFTER. NIY. */ 124090075Sobrien 124190075Sobrienstatic bool 1242169689Skanrtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED, 1243169689Skan basic_block after ATTRIBUTE_UNUSED) 124490075Sobrien{ 1245169689Skan return false; 124690075Sobrien} 124790075Sobrien 124890075Sobrien/* Split a (typically critical) edge. Return the new block. 1249169689Skan The edge must not be abnormal. 125090075Sobrien 125190075Sobrien ??? The code generally expects to be called on critical edges. 125290075Sobrien The case of a block ending in an unconditional jump to a 125390075Sobrien block with multiple predecessors is not handled optimally. */ 125490075Sobrien 1255132718Skanstatic basic_block 1256132718Skanrtl_split_edge (edge edge_in) 125790075Sobrien{ 125890075Sobrien basic_block bb; 125990075Sobrien rtx before; 126090075Sobrien 126190075Sobrien /* Abnormal edges cannot be split. */ 1262169689Skan gcc_assert (!(edge_in->flags & EDGE_ABNORMAL)); 126390075Sobrien 126490075Sobrien /* We are going to place the new block in front of edge destination. 126590075Sobrien Avoid existence of fallthru predecessors. */ 126690075Sobrien if ((edge_in->flags & EDGE_FALLTHRU) == 0) 126790075Sobrien { 126890075Sobrien edge e; 1269169689Skan edge_iterator ei; 127090075Sobrien 1271169689Skan FOR_EACH_EDGE (e, ei, edge_in->dest->preds) 127290075Sobrien if (e->flags & EDGE_FALLTHRU) 127390075Sobrien break; 127490075Sobrien 127590075Sobrien if (e) 127690075Sobrien force_nonfallthru (e); 127790075Sobrien } 127890075Sobrien 1279169689Skan /* Create the basic block note. */ 1280169689Skan if (edge_in->dest != EXIT_BLOCK_PTR) 1281132718Skan before = BB_HEAD (edge_in->dest); 128290075Sobrien else 128390075Sobrien before = NULL_RTX; 128490075Sobrien 1285169689Skan /* If this is a fall through edge to the exit block, the blocks might be 1286169689Skan not adjacent, and the right place is the after the source. */ 1287169689Skan if (edge_in->flags & EDGE_FALLTHRU && edge_in->dest == EXIT_BLOCK_PTR) 1288169689Skan { 1289169689Skan before = NEXT_INSN (BB_END (edge_in->src)); 1290169689Skan bb = create_basic_block (before, NULL, edge_in->src); 1291169689Skan BB_COPY_PARTITION (bb, edge_in->src); 1292169689Skan } 1293169689Skan else 1294169689Skan { 1295169689Skan bb = create_basic_block (before, NULL, edge_in->dest->prev_bb); 1296169689Skan /* ??? Why not edge_in->dest->prev_bb here? */ 1297169689Skan BB_COPY_PARTITION (bb, edge_in->dest); 1298169689Skan } 129990075Sobrien 130090075Sobrien /* ??? This info is likely going to be out of date very soon. */ 1301169689Skan if (edge_in->dest->il.rtl->global_live_at_start) 130290075Sobrien { 1303169689Skan bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack); 1304169689Skan bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack); 1305169689Skan COPY_REG_SET (bb->il.rtl->global_live_at_start, 1306169689Skan edge_in->dest->il.rtl->global_live_at_start); 1307169689Skan COPY_REG_SET (bb->il.rtl->global_live_at_end, 1308169689Skan edge_in->dest->il.rtl->global_live_at_start); 130990075Sobrien } 131090075Sobrien 1311132718Skan make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU); 131290075Sobrien 1313132718Skan /* For non-fallthru edges, we must adjust the predecessor's 131490075Sobrien jump instruction to target our new block. */ 131590075Sobrien if ((edge_in->flags & EDGE_FALLTHRU) == 0) 131690075Sobrien { 1317169689Skan edge redirected = redirect_edge_and_branch (edge_in, bb); 1318169689Skan gcc_assert (redirected); 131990075Sobrien } 132090075Sobrien else 132190075Sobrien redirect_edge_succ (edge_in, bb); 132290075Sobrien 132390075Sobrien return bb; 132490075Sobrien} 132590075Sobrien 132690075Sobrien/* Queue instructions for insertion on an edge between two basic blocks. 132790075Sobrien The new instructions and basic blocks (if any) will not appear in the 132890075Sobrien CFG until commit_edge_insertions is called. */ 132990075Sobrien 133090075Sobrienvoid 1331132718Skaninsert_insn_on_edge (rtx pattern, edge e) 133290075Sobrien{ 133390075Sobrien /* We cannot insert instructions on an abnormal critical edge. 133490075Sobrien It will be easier to find the culprit if we die now. */ 1335169689Skan gcc_assert (!((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))); 133690075Sobrien 1337169689Skan if (e->insns.r == NULL_RTX) 133890075Sobrien start_sequence (); 133990075Sobrien else 1340169689Skan push_to_sequence (e->insns.r); 134190075Sobrien 134290075Sobrien emit_insn (pattern); 134390075Sobrien 1344169689Skan e->insns.r = get_insns (); 134590075Sobrien end_sequence (); 134690075Sobrien} 134790075Sobrien 134890075Sobrien/* Update the CFG for the instructions queued on edge E. */ 134990075Sobrien 135090075Sobrienstatic void 1351132718Skancommit_one_edge_insertion (edge e, int watch_calls) 135290075Sobrien{ 135390075Sobrien rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last; 1354117395Skan basic_block bb = NULL; 135590075Sobrien 135690075Sobrien /* Pull the insns off the edge now since the edge might go away. */ 1357169689Skan insns = e->insns.r; 1358169689Skan e->insns.r = NULL_RTX; 135990075Sobrien 1360117395Skan /* Special case -- avoid inserting code between call and storing 1361117395Skan its return value. */ 1362169689Skan if (watch_calls && (e->flags & EDGE_FALLTHRU) 1363169689Skan && single_pred_p (e->dest) 1364117395Skan && e->src != ENTRY_BLOCK_PTR 1365169689Skan && CALL_P (BB_END (e->src))) 136690075Sobrien { 1367132718Skan rtx next = next_nonnote_insn (BB_END (e->src)); 1368117395Skan 1369132718Skan after = BB_HEAD (e->dest); 1370117395Skan /* The first insn after the call may be a stack pop, skip it. */ 1371117395Skan while (next 1372117395Skan && keep_with_call_p (next)) 1373117395Skan { 1374117395Skan after = next; 1375117395Skan next = next_nonnote_insn (next); 1376117395Skan } 137790075Sobrien bb = e->dest; 137890075Sobrien } 1379117395Skan if (!before && !after) 138090075Sobrien { 1381117395Skan /* Figure out where to put these things. If the destination has 1382169689Skan one predecessor, insert there. Except for the exit block. */ 1383169689Skan if (single_pred_p (e->dest) && e->dest != EXIT_BLOCK_PTR) 1384117395Skan { 1385117395Skan bb = e->dest; 138690075Sobrien 1387117395Skan /* Get the location correct wrt a code label, and "nice" wrt 1388117395Skan a basic block note, and before everything else. */ 1389132718Skan tmp = BB_HEAD (bb); 1390169689Skan if (LABEL_P (tmp)) 1391117395Skan tmp = NEXT_INSN (tmp); 1392117395Skan if (NOTE_INSN_BASIC_BLOCK_P (tmp)) 1393117395Skan tmp = NEXT_INSN (tmp); 1394132718Skan if (tmp == BB_HEAD (bb)) 1395117395Skan before = tmp; 1396117395Skan else if (tmp) 1397117395Skan after = PREV_INSN (tmp); 1398117395Skan else 1399117395Skan after = get_last_insn (); 1400117395Skan } 140190075Sobrien 1402117395Skan /* If the source has one successor and the edge is not abnormal, 1403169689Skan insert there. Except for the entry block. */ 1404117395Skan else if ((e->flags & EDGE_ABNORMAL) == 0 1405169689Skan && single_succ_p (e->src) 1406117395Skan && e->src != ENTRY_BLOCK_PTR) 1407117395Skan { 1408117395Skan bb = e->src; 1409117395Skan 1410117395Skan /* It is possible to have a non-simple jump here. Consider a target 1411117395Skan where some forms of unconditional jumps clobber a register. This 1412117395Skan happens on the fr30 for example. 1413117395Skan 1414117395Skan We know this block has a single successor, so we can just emit 1415117395Skan the queued insns before the jump. */ 1416169689Skan if (JUMP_P (BB_END (bb))) 1417169689Skan before = BB_END (bb); 1418117395Skan else 1419117395Skan { 1420169689Skan /* We'd better be fallthru, or we've lost track of 1421169689Skan what's what. */ 1422169689Skan gcc_assert (e->flags & EDGE_FALLTHRU); 1423117395Skan 1424132718Skan after = BB_END (bb); 1425117395Skan } 1426117395Skan } 1427117395Skan /* Otherwise we must split the edge. */ 142890075Sobrien else 142990075Sobrien { 1430117395Skan bb = split_edge (e); 1431132718Skan after = BB_END (bb); 1432169689Skan 1433169689Skan if (flag_reorder_blocks_and_partition 1434169689Skan && targetm.have_named_sections 1435169689Skan && e->src != ENTRY_BLOCK_PTR 1436169689Skan && BB_PARTITION (e->src) == BB_COLD_PARTITION 1437169689Skan && !(e->flags & EDGE_CROSSING)) 1438169689Skan { 1439169689Skan rtx bb_note, cur_insn; 1440169689Skan 1441169689Skan bb_note = NULL_RTX; 1442169689Skan for (cur_insn = BB_HEAD (bb); cur_insn != NEXT_INSN (BB_END (bb)); 1443169689Skan cur_insn = NEXT_INSN (cur_insn)) 1444169689Skan if (NOTE_P (cur_insn) 1445169689Skan && NOTE_LINE_NUMBER (cur_insn) == NOTE_INSN_BASIC_BLOCK) 1446169689Skan { 1447169689Skan bb_note = cur_insn; 1448169689Skan break; 1449169689Skan } 1450169689Skan 1451169689Skan if (JUMP_P (BB_END (bb)) 1452169689Skan && !any_condjump_p (BB_END (bb)) 1453169689Skan && (single_succ_edge (bb)->flags & EDGE_CROSSING)) 1454169689Skan REG_NOTES (BB_END (bb)) = gen_rtx_EXPR_LIST 1455169689Skan (REG_CROSSING_JUMP, NULL_RTX, REG_NOTES (BB_END (bb))); 1456169689Skan } 145790075Sobrien } 145890075Sobrien } 145990075Sobrien 146090075Sobrien /* Now that we've found the spot, do the insertion. */ 146190075Sobrien 146290075Sobrien if (before) 146390075Sobrien { 1464132718Skan emit_insn_before_noloc (insns, before); 146590075Sobrien last = prev_nonnote_insn (before); 146690075Sobrien } 146790075Sobrien else 1468132718Skan last = emit_insn_after_noloc (insns, after); 146990075Sobrien 147090075Sobrien if (returnjump_p (last)) 147190075Sobrien { 147290075Sobrien /* ??? Remove all outgoing edges from BB and add one for EXIT. 1473169689Skan This is not currently a problem because this only happens 1474169689Skan for the (single) epilogue, which already has a fallthru edge 1475169689Skan to EXIT. */ 147690075Sobrien 1477169689Skan e = single_succ_edge (bb); 1478169689Skan gcc_assert (e->dest == EXIT_BLOCK_PTR 1479169689Skan && single_succ_p (bb) && (e->flags & EDGE_FALLTHRU)); 148090075Sobrien 148190075Sobrien e->flags &= ~EDGE_FALLTHRU; 148290075Sobrien emit_barrier_after (last); 148390075Sobrien 148490075Sobrien if (before) 148590075Sobrien delete_insn (before); 148690075Sobrien } 1487169689Skan else 1488169689Skan gcc_assert (!JUMP_P (last)); 148990075Sobrien 1490169689Skan /* Mark the basic block for find_many_sub_basic_blocks. */ 1491117395Skan bb->aux = &bb->aux; 149290075Sobrien} 149390075Sobrien 149490075Sobrien/* Update the CFG for all queued instructions. */ 149590075Sobrien 149690075Sobrienvoid 1497132718Skancommit_edge_insertions (void) 149890075Sobrien{ 149990075Sobrien basic_block bb; 1500117395Skan sbitmap blocks; 1501117395Skan bool changed = false; 150290075Sobrien 150390075Sobrien#ifdef ENABLE_CHECKING 150490075Sobrien verify_flow_info (); 150590075Sobrien#endif 150690075Sobrien 1507117395Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 150890075Sobrien { 1509169689Skan edge e; 1510169689Skan edge_iterator ei; 151190075Sobrien 1512169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 1513169689Skan if (e->insns.r) 1514169689Skan { 1515169689Skan changed = true; 1516169689Skan commit_one_edge_insertion (e, false); 1517169689Skan } 1518117395Skan } 151990075Sobrien 1520117395Skan if (!changed) 1521117395Skan return; 1522117395Skan 1523117395Skan blocks = sbitmap_alloc (last_basic_block); 1524117395Skan sbitmap_zero (blocks); 1525117395Skan FOR_EACH_BB (bb) 1526117395Skan if (bb->aux) 1527117395Skan { 1528169689Skan SET_BIT (blocks, bb->index); 1529132718Skan /* Check for forgotten bb->aux values before commit_edge_insertions 1530132718Skan call. */ 1531169689Skan gcc_assert (bb->aux == &bb->aux); 1532117395Skan bb->aux = NULL; 1533117395Skan } 1534117395Skan find_many_sub_basic_blocks (blocks); 1535117395Skan sbitmap_free (blocks); 1536117395Skan} 1537117395Skan 1538117395Skan/* Update the CFG for all queued instructions, taking special care of inserting 1539117395Skan code on edges between call and storing its return value. */ 1540117395Skan 1541117395Skanvoid 1542132718Skancommit_edge_insertions_watch_calls (void) 1543117395Skan{ 1544117395Skan basic_block bb; 1545117395Skan sbitmap blocks; 1546117395Skan bool changed = false; 1547117395Skan 1548117395Skan#ifdef ENABLE_CHECKING 1549117395Skan verify_flow_info (); 1550117395Skan#endif 1551117395Skan 1552117395Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 1553117395Skan { 1554169689Skan edge e; 1555169689Skan edge_iterator ei; 1556117395Skan 1557169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 1558169689Skan if (e->insns.r) 1559169689Skan { 1560169689Skan changed = true; 1561169689Skan commit_one_edge_insertion (e, true); 1562169689Skan } 156390075Sobrien } 1564117395Skan 1565117395Skan if (!changed) 1566117395Skan return; 1567117395Skan 1568117395Skan blocks = sbitmap_alloc (last_basic_block); 1569117395Skan sbitmap_zero (blocks); 1570117395Skan FOR_EACH_BB (bb) 1571117395Skan if (bb->aux) 1572117395Skan { 1573169689Skan SET_BIT (blocks, bb->index); 1574132718Skan /* Check for forgotten bb->aux values before commit_edge_insertions 1575132718Skan call. */ 1576169689Skan gcc_assert (bb->aux == &bb->aux); 1577117395Skan bb->aux = NULL; 1578117395Skan } 1579117395Skan find_many_sub_basic_blocks (blocks); 1580117395Skan sbitmap_free (blocks); 158190075Sobrien} 158290075Sobrien 1583169689Skan/* Print out RTL-specific basic block information (live information 1584169689Skan at start and end). */ 158590075Sobrien 1586132718Skanstatic void 1587169689Skanrtl_dump_bb (basic_block bb, FILE *outf, int indent) 158890075Sobrien{ 158990075Sobrien rtx insn; 159090075Sobrien rtx last; 1591169689Skan char *s_indent; 159290075Sobrien 1593169689Skan s_indent = alloca ((size_t) indent + 1); 1594169689Skan memset (s_indent, ' ', (size_t) indent); 1595169689Skan s_indent[indent] = '\0'; 1596169689Skan 1597169689Skan fprintf (outf, ";;%s Registers live at start: ", s_indent); 1598169689Skan dump_regset (bb->il.rtl->global_live_at_start, outf); 159990075Sobrien putc ('\n', outf); 160090075Sobrien 1601132718Skan for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb)); insn != last; 160290075Sobrien insn = NEXT_INSN (insn)) 160390075Sobrien print_rtl_single (outf, insn); 160490075Sobrien 1605169689Skan fprintf (outf, ";;%s Registers live at end: ", s_indent); 1606169689Skan dump_regset (bb->il.rtl->global_live_at_end, outf); 160790075Sobrien putc ('\n', outf); 160890075Sobrien} 160990075Sobrien 161090075Sobrien/* Like print_rtl, but also print out live information for the start of each 161190075Sobrien basic block. */ 161290075Sobrien 161390075Sobrienvoid 1614132718Skanprint_rtl_with_bb (FILE *outf, rtx rtx_first) 161590075Sobrien{ 161690075Sobrien rtx tmp_rtx; 161790075Sobrien 161890075Sobrien if (rtx_first == 0) 161990075Sobrien fprintf (outf, "(nil)\n"); 162090075Sobrien else 162190075Sobrien { 162290075Sobrien enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB }; 162390075Sobrien int max_uid = get_max_uid (); 1624169689Skan basic_block *start = XCNEWVEC (basic_block, max_uid); 1625169689Skan basic_block *end = XCNEWVEC (basic_block, max_uid); 1626169689Skan enum bb_state *in_bb_p = XCNEWVEC (enum bb_state, max_uid); 162790075Sobrien 1628117395Skan basic_block bb; 1629117395Skan 1630117395Skan FOR_EACH_BB_REVERSE (bb) 163190075Sobrien { 163290075Sobrien rtx x; 163390075Sobrien 1634132718Skan start[INSN_UID (BB_HEAD (bb))] = bb; 1635132718Skan end[INSN_UID (BB_END (bb))] = bb; 1636132718Skan for (x = BB_HEAD (bb); x != NULL_RTX; x = NEXT_INSN (x)) 163790075Sobrien { 163890075Sobrien enum bb_state state = IN_MULTIPLE_BB; 163990075Sobrien 164090075Sobrien if (in_bb_p[INSN_UID (x)] == NOT_IN_BB) 164190075Sobrien state = IN_ONE_BB; 164290075Sobrien in_bb_p[INSN_UID (x)] = state; 164390075Sobrien 1644132718Skan if (x == BB_END (bb)) 164590075Sobrien break; 164690075Sobrien } 164790075Sobrien } 164890075Sobrien 164990075Sobrien for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx)) 165090075Sobrien { 165190075Sobrien int did_output; 165290075Sobrien 165390075Sobrien if ((bb = start[INSN_UID (tmp_rtx)]) != NULL) 165490075Sobrien { 165590075Sobrien fprintf (outf, ";; Start of basic block %d, registers live:", 165690075Sobrien bb->index); 1657169689Skan dump_regset (bb->il.rtl->global_live_at_start, outf); 165890075Sobrien putc ('\n', outf); 165990075Sobrien } 166090075Sobrien 166190075Sobrien if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB 1662169689Skan && !NOTE_P (tmp_rtx) 1663169689Skan && !BARRIER_P (tmp_rtx)) 166490075Sobrien fprintf (outf, ";; Insn is not within a basic block\n"); 166590075Sobrien else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB) 166690075Sobrien fprintf (outf, ";; Insn is in multiple basic blocks\n"); 166790075Sobrien 166890075Sobrien did_output = print_rtl_single (outf, tmp_rtx); 166990075Sobrien 167090075Sobrien if ((bb = end[INSN_UID (tmp_rtx)]) != NULL) 167190075Sobrien { 167290075Sobrien fprintf (outf, ";; End of basic block %d, registers live:\n", 167390075Sobrien bb->index); 1674169689Skan dump_regset (bb->il.rtl->global_live_at_end, outf); 167590075Sobrien putc ('\n', outf); 167690075Sobrien } 167790075Sobrien 167890075Sobrien if (did_output) 167990075Sobrien putc ('\n', outf); 168090075Sobrien } 168190075Sobrien 168290075Sobrien free (start); 168390075Sobrien free (end); 168490075Sobrien free (in_bb_p); 168590075Sobrien } 168690075Sobrien 168790075Sobrien if (current_function_epilogue_delay_list != 0) 168890075Sobrien { 168990075Sobrien fprintf (outf, "\n;; Insns in epilogue delay list:\n\n"); 169090075Sobrien for (tmp_rtx = current_function_epilogue_delay_list; tmp_rtx != 0; 169190075Sobrien tmp_rtx = XEXP (tmp_rtx, 1)) 169290075Sobrien print_rtl_single (outf, XEXP (tmp_rtx, 0)); 169390075Sobrien } 169490075Sobrien} 169590075Sobrien 169690075Sobrienvoid 1697132718Skanupdate_br_prob_note (basic_block bb) 169890075Sobrien{ 169990075Sobrien rtx note; 1700169689Skan if (!JUMP_P (BB_END (bb))) 170190075Sobrien return; 1702132718Skan note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX); 170390075Sobrien if (!note || INTVAL (XEXP (note, 0)) == BRANCH_EDGE (bb)->probability) 170490075Sobrien return; 170590075Sobrien XEXP (note, 0) = GEN_INT (BRANCH_EDGE (bb)->probability); 170690075Sobrien} 1707169689Skan 1708169689Skan/* Get the last insn associated with block BB (that includes barriers and 1709169689Skan tablejumps after BB). */ 1710169689Skanrtx 1711169689Skanget_last_bb_insn (basic_block bb) 1712169689Skan{ 1713169689Skan rtx tmp; 1714169689Skan rtx end = BB_END (bb); 1715169689Skan 1716169689Skan /* Include any jump table following the basic block. */ 1717169689Skan if (tablejump_p (end, NULL, &tmp)) 1718169689Skan end = tmp; 1719169689Skan 1720169689Skan /* Include any barriers that may follow the basic block. */ 1721169689Skan tmp = next_nonnote_insn (end); 1722169689Skan while (tmp && BARRIER_P (tmp)) 1723169689Skan { 1724169689Skan end = tmp; 1725169689Skan tmp = next_nonnote_insn (end); 1726169689Skan } 1727169689Skan 1728169689Skan return end; 1729169689Skan} 173090075Sobrien 1731132718Skan/* Verify the CFG and RTL consistency common for both underlying RTL and 1732132718Skan cfglayout RTL. 173390075Sobrien 173490075Sobrien Currently it does following checks: 173590075Sobrien 173690075Sobrien - test head/end pointers 173790075Sobrien - overlapping of basic blocks 173890075Sobrien - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note) 173990075Sobrien - tails of basic blocks (ensure that boundary is necessary) 174090075Sobrien - scans body of the basic block for JUMP_INSN, CODE_LABEL 174190075Sobrien and NOTE_INSN_BASIC_BLOCK 1742169689Skan - verify that no fall_thru edge crosses hot/cold partition boundaries 174390075Sobrien 174490075Sobrien In future it can be extended check a lot of other stuff as well 174590075Sobrien (reachability of basic blocks, life information, etc. etc.). */ 1746169689Skan 1747132718Skanstatic int 1748132718Skanrtl_verify_flow_info_1 (void) 174990075Sobrien{ 175090075Sobrien const int max_uid = get_max_uid (); 175190075Sobrien rtx last_head = get_last_insn (); 1752132718Skan basic_block *bb_info; 175390075Sobrien rtx x; 1754132718Skan int err = 0; 1755169689Skan basic_block bb; 175690075Sobrien 1757169689Skan bb_info = XCNEWVEC (basic_block, max_uid); 175890075Sobrien 1759117395Skan FOR_EACH_BB_REVERSE (bb) 1760117395Skan { 1761132718Skan rtx head = BB_HEAD (bb); 1762132718Skan rtx end = BB_END (bb); 176390075Sobrien 176490075Sobrien /* Verify the end of the basic block is in the INSN chain. */ 176590075Sobrien for (x = last_head; x != NULL_RTX; x = PREV_INSN (x)) 176690075Sobrien if (x == end) 176790075Sobrien break; 176890075Sobrien 1769169689Skan if (!(bb->flags & BB_RTL)) 1770169689Skan { 1771169689Skan error ("BB_RTL flag not set for block %d", bb->index); 1772169689Skan err = 1; 1773169689Skan } 1774169689Skan 177590075Sobrien if (!x) 177690075Sobrien { 177790075Sobrien error ("end insn %d for block %d not found in the insn stream", 177890075Sobrien INSN_UID (end), bb->index); 177990075Sobrien err = 1; 178090075Sobrien } 178190075Sobrien 178290075Sobrien /* Work backwards from the end to the head of the basic block 178390075Sobrien to verify the head is in the RTL chain. */ 178490075Sobrien for (; x != NULL_RTX; x = PREV_INSN (x)) 178590075Sobrien { 178690075Sobrien /* While walking over the insn chain, verify insns appear 178790075Sobrien in only one basic block and initialize the BB_INFO array 178890075Sobrien used by other passes. */ 178990075Sobrien if (bb_info[INSN_UID (x)] != NULL) 179090075Sobrien { 179190075Sobrien error ("insn %d is in multiple basic blocks (%d and %d)", 179290075Sobrien INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index); 179390075Sobrien err = 1; 179490075Sobrien } 179590075Sobrien 179690075Sobrien bb_info[INSN_UID (x)] = bb; 179790075Sobrien 179890075Sobrien if (x == head) 179990075Sobrien break; 180090075Sobrien } 180190075Sobrien if (!x) 180290075Sobrien { 180390075Sobrien error ("head insn %d for block %d not found in the insn stream", 180490075Sobrien INSN_UID (head), bb->index); 180590075Sobrien err = 1; 180690075Sobrien } 180790075Sobrien 180890075Sobrien last_head = x; 180990075Sobrien } 181090075Sobrien 181190075Sobrien /* Now check the basic blocks (boundaries etc.) */ 1812117395Skan FOR_EACH_BB_REVERSE (bb) 181390075Sobrien { 1814117395Skan int n_fallthru = 0, n_eh = 0, n_call = 0, n_abnormal = 0, n_branch = 0; 1815132718Skan edge e, fallthru = NULL; 1816117395Skan rtx note; 1817169689Skan edge_iterator ei; 181890075Sobrien 1819169689Skan if (JUMP_P (BB_END (bb)) 1820132718Skan && (note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX)) 1821169689Skan && EDGE_COUNT (bb->succs) >= 2 1822132718Skan && any_condjump_p (BB_END (bb))) 1823117395Skan { 1824169689Skan if (INTVAL (XEXP (note, 0)) != BRANCH_EDGE (bb)->probability 1825169689Skan && profile_status != PROFILE_ABSENT) 1826117395Skan { 1827132718Skan error ("verify_flow_info: REG_BR_PROB does not match cfg %wi %i", 1828117395Skan INTVAL (XEXP (note, 0)), BRANCH_EDGE (bb)->probability); 1829117395Skan err = 1; 1830117395Skan } 1831117395Skan } 1832169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 183390075Sobrien { 183490075Sobrien if (e->flags & EDGE_FALLTHRU) 1835169689Skan { 1836169689Skan n_fallthru++, fallthru = e; 1837169689Skan if ((e->flags & EDGE_CROSSING) 1838169689Skan || (BB_PARTITION (e->src) != BB_PARTITION (e->dest) 1839169689Skan && e->src != ENTRY_BLOCK_PTR 1840169689Skan && e->dest != EXIT_BLOCK_PTR)) 1841169689Skan { 1842169689Skan error ("fallthru edge crosses section boundary (bb %i)", 1843169689Skan e->src->index); 1844169689Skan err = 1; 1845169689Skan } 1846169689Skan } 184790075Sobrien 1848132718Skan if ((e->flags & ~(EDGE_DFS_BACK 1849132718Skan | EDGE_CAN_FALLTHRU 1850132718Skan | EDGE_IRREDUCIBLE_LOOP 1851169689Skan | EDGE_LOOP_EXIT 1852169689Skan | EDGE_CROSSING)) == 0) 1853117395Skan n_branch++; 1854117395Skan 1855117395Skan if (e->flags & EDGE_ABNORMAL_CALL) 1856117395Skan n_call++; 1857117395Skan 1858117395Skan if (e->flags & EDGE_EH) 1859117395Skan n_eh++; 1860117395Skan else if (e->flags & EDGE_ABNORMAL) 1861117395Skan n_abnormal++; 186290075Sobrien } 186390075Sobrien 1864132718Skan if (n_eh && GET_CODE (PATTERN (BB_END (bb))) != RESX 1865132718Skan && !find_reg_note (BB_END (bb), REG_EH_REGION, NULL_RTX)) 186690075Sobrien { 1867169689Skan error ("missing REG_EH_REGION note in the end of bb %i", bb->index); 1868117395Skan err = 1; 1869117395Skan } 1870117395Skan if (n_branch 1871169689Skan && (!JUMP_P (BB_END (bb)) 1872132718Skan || (n_branch > 1 && (any_uncondjump_p (BB_END (bb)) 1873132718Skan || any_condjump_p (BB_END (bb)))))) 1874117395Skan { 1875169689Skan error ("too many outgoing branch edges from bb %i", bb->index); 1876117395Skan err = 1; 1877117395Skan } 1878132718Skan if (n_fallthru && any_uncondjump_p (BB_END (bb))) 1879117395Skan { 1880169689Skan error ("fallthru edge after unconditional jump %i", bb->index); 1881117395Skan err = 1; 1882117395Skan } 1883132718Skan if (n_branch != 1 && any_uncondjump_p (BB_END (bb))) 1884117395Skan { 1885169689Skan error ("wrong amount of branch edges after unconditional jump %i", bb->index); 1886117395Skan err = 1; 1887117395Skan } 1888132718Skan if (n_branch != 1 && any_condjump_p (BB_END (bb)) 1889132718Skan && JUMP_LABEL (BB_END (bb)) != BB_HEAD (fallthru->dest)) 1890117395Skan { 1891169689Skan error ("wrong amount of branch edges after conditional jump %i", 1892169689Skan bb->index); 1893117395Skan err = 1; 1894117395Skan } 1895169689Skan if (n_call && !CALL_P (BB_END (bb))) 1896117395Skan { 1897169689Skan error ("call edges for non-call insn in bb %i", bb->index); 1898117395Skan err = 1; 1899117395Skan } 1900117395Skan if (n_abnormal 1901169689Skan && (!CALL_P (BB_END (bb)) && n_call != n_abnormal) 1902169689Skan && (!JUMP_P (BB_END (bb)) 1903132718Skan || any_condjump_p (BB_END (bb)) 1904132718Skan || any_uncondjump_p (BB_END (bb)))) 1905117395Skan { 1906169689Skan error ("abnormal edges for no purpose in bb %i", bb->index); 1907117395Skan err = 1; 1908117395Skan } 1909117395Skan 1910132718Skan for (x = BB_HEAD (bb); x != NEXT_INSN (BB_END (bb)); x = NEXT_INSN (x)) 1911169689Skan /* We may have a barrier inside a basic block before dead code 1912169689Skan elimination. There is no BLOCK_FOR_INSN field in a barrier. */ 1913169689Skan if (!BARRIER_P (x) && BLOCK_FOR_INSN (x) != bb) 191490075Sobrien { 191590075Sobrien debug_rtx (x); 191690075Sobrien if (! BLOCK_FOR_INSN (x)) 191790075Sobrien error 191890075Sobrien ("insn %d inside basic block %d but block_for_insn is NULL", 191990075Sobrien INSN_UID (x), bb->index); 192090075Sobrien else 192190075Sobrien error 192290075Sobrien ("insn %d inside basic block %d but block_for_insn is %i", 192390075Sobrien INSN_UID (x), bb->index, BLOCK_FOR_INSN (x)->index); 192490075Sobrien 192590075Sobrien err = 1; 192690075Sobrien } 192790075Sobrien 192890075Sobrien /* OK pointers are correct. Now check the header of basic 1929169689Skan block. It ought to contain optional CODE_LABEL followed 193090075Sobrien by NOTE_BASIC_BLOCK. */ 1931132718Skan x = BB_HEAD (bb); 1932169689Skan if (LABEL_P (x)) 193390075Sobrien { 1934132718Skan if (BB_END (bb) == x) 193590075Sobrien { 193690075Sobrien error ("NOTE_INSN_BASIC_BLOCK is missing for block %d", 193790075Sobrien bb->index); 193890075Sobrien err = 1; 193990075Sobrien } 194090075Sobrien 194190075Sobrien x = NEXT_INSN (x); 194290075Sobrien } 194390075Sobrien 194490075Sobrien if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb) 194590075Sobrien { 194690075Sobrien error ("NOTE_INSN_BASIC_BLOCK is missing for block %d", 194790075Sobrien bb->index); 194890075Sobrien err = 1; 194990075Sobrien } 195090075Sobrien 1951132718Skan if (BB_END (bb) == x) 1952169689Skan /* Do checks for empty blocks here. */ 195390075Sobrien ; 195490075Sobrien else 195590075Sobrien for (x = NEXT_INSN (x); x; x = NEXT_INSN (x)) 195690075Sobrien { 195790075Sobrien if (NOTE_INSN_BASIC_BLOCK_P (x)) 195890075Sobrien { 195990075Sobrien error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d", 196090075Sobrien INSN_UID (x), bb->index); 196190075Sobrien err = 1; 196290075Sobrien } 196390075Sobrien 1964132718Skan if (x == BB_END (bb)) 196590075Sobrien break; 196690075Sobrien 1967132718Skan if (control_flow_insn_p (x)) 196890075Sobrien { 196990075Sobrien error ("in basic block %d:", bb->index); 197090075Sobrien fatal_insn ("flow control insn inside a basic block", x); 197190075Sobrien } 197290075Sobrien } 197390075Sobrien } 197490075Sobrien 1975132718Skan /* Clean up. */ 1976132718Skan free (bb_info); 1977132718Skan return err; 1978132718Skan} 197990075Sobrien 1980132718Skan/* Verify the CFG and RTL consistency common for both underlying RTL and 1981132718Skan cfglayout RTL. 198290075Sobrien 1983132718Skan Currently it does following checks: 1984132718Skan - all checks of rtl_verify_flow_info_1 1985132718Skan - check that all insns are in the basic blocks 1986132718Skan (except the switch handling code, barriers and notes) 1987132718Skan - check that all returns are followed by barriers 1988132718Skan - check that all fallthru edge points to the adjacent blocks. */ 1989132718Skanstatic int 1990132718Skanrtl_verify_flow_info (void) 1991132718Skan{ 1992132718Skan basic_block bb; 1993132718Skan int err = rtl_verify_flow_info_1 (); 1994132718Skan rtx x; 1995132718Skan int num_bb_notes; 1996132718Skan const rtx rtx_first = get_insns (); 1997132718Skan basic_block last_bb_seen = ENTRY_BLOCK_PTR, curr_bb = NULL; 199890075Sobrien 1999132718Skan FOR_EACH_BB_REVERSE (bb) 2000132718Skan { 2001132718Skan edge e; 2002169689Skan edge_iterator ei; 2003169689Skan 2004169689Skan if (bb->predictions) 2005169689Skan { 2006169689Skan error ("bb prediction set for block %i, but it is not used in RTL land", bb->index); 2007169689Skan err = 1; 2008169689Skan } 2009169689Skan 2010169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 2011132718Skan if (e->flags & EDGE_FALLTHRU) 2012132718Skan break; 2013132718Skan if (!e) 2014132718Skan { 2015132718Skan rtx insn; 201690075Sobrien 2017132718Skan /* Ensure existence of barrier in BB with no fallthru edges. */ 2018169689Skan for (insn = BB_END (bb); !insn || !BARRIER_P (insn); 2019132718Skan insn = NEXT_INSN (insn)) 2020132718Skan if (!insn 2021169689Skan || (NOTE_P (insn) 2022132718Skan && NOTE_LINE_NUMBER (insn) == NOTE_INSN_BASIC_BLOCK)) 2023132718Skan { 2024132718Skan error ("missing barrier after block %i", bb->index); 2025132718Skan err = 1; 2026132718Skan break; 2027132718Skan } 2028132718Skan } 2029132718Skan else if (e->src != ENTRY_BLOCK_PTR 2030132718Skan && e->dest != EXIT_BLOCK_PTR) 2031169689Skan { 2032132718Skan rtx insn; 2033132718Skan 2034132718Skan if (e->src->next_bb != e->dest) 2035132718Skan { 2036132718Skan error 2037132718Skan ("verify_flow_info: Incorrect blocks for fallthru %i->%i", 2038132718Skan e->src->index, e->dest->index); 2039132718Skan err = 1; 2040132718Skan } 2041132718Skan else 2042132718Skan for (insn = NEXT_INSN (BB_END (e->src)); insn != BB_HEAD (e->dest); 2043132718Skan insn = NEXT_INSN (insn)) 2044169689Skan if (BARRIER_P (insn) || INSN_P (insn)) 2045132718Skan { 2046132718Skan error ("verify_flow_info: Incorrect fallthru %i->%i", 2047132718Skan e->src->index, e->dest->index); 2048132718Skan fatal_insn ("wrong insn in the fallthru edge", insn); 2049132718Skan err = 1; 2050132718Skan } 2051169689Skan } 2052132718Skan } 2053132718Skan 205490075Sobrien num_bb_notes = 0; 2055117395Skan last_bb_seen = ENTRY_BLOCK_PTR; 2056117395Skan 205790075Sobrien for (x = rtx_first; x; x = NEXT_INSN (x)) 205890075Sobrien { 205990075Sobrien if (NOTE_INSN_BASIC_BLOCK_P (x)) 206090075Sobrien { 2061117395Skan bb = NOTE_BASIC_BLOCK (x); 206290075Sobrien 206390075Sobrien num_bb_notes++; 2064117395Skan if (bb != last_bb_seen->next_bb) 2065132718Skan internal_error ("basic blocks not laid down consecutively"); 206690075Sobrien 2067132718Skan curr_bb = last_bb_seen = bb; 206890075Sobrien } 206990075Sobrien 2070132718Skan if (!curr_bb) 207190075Sobrien { 207290075Sobrien switch (GET_CODE (x)) 207390075Sobrien { 207490075Sobrien case BARRIER: 207590075Sobrien case NOTE: 207690075Sobrien break; 207790075Sobrien 207890075Sobrien case CODE_LABEL: 2079169689Skan /* An addr_vec is placed outside any basic block. */ 208090075Sobrien if (NEXT_INSN (x) 2081169689Skan && JUMP_P (NEXT_INSN (x)) 208290075Sobrien && (GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_DIFF_VEC 208390075Sobrien || GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_VEC)) 208490075Sobrien x = NEXT_INSN (x); 208590075Sobrien 208690075Sobrien /* But in any case, non-deletable labels can appear anywhere. */ 208790075Sobrien break; 208890075Sobrien 208990075Sobrien default: 209090075Sobrien fatal_insn ("insn outside basic block", x); 209190075Sobrien } 209290075Sobrien } 209390075Sobrien 2094169689Skan if (JUMP_P (x) 209590075Sobrien && returnjump_p (x) && ! condjump_p (x) 2096169689Skan && ! (NEXT_INSN (x) && BARRIER_P (NEXT_INSN (x)))) 209790075Sobrien fatal_insn ("return not followed by barrier", x); 2098132718Skan if (curr_bb && x == BB_END (curr_bb)) 2099132718Skan curr_bb = NULL; 210090075Sobrien } 210190075Sobrien 2102169689Skan if (num_bb_notes != n_basic_blocks - NUM_FIXED_BLOCKS) 210390075Sobrien internal_error 210490075Sobrien ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)", 210590075Sobrien num_bb_notes, n_basic_blocks); 210690075Sobrien 2107132718Skan return err; 210890075Sobrien} 210990075Sobrien 211090075Sobrien/* Assume that the preceding pass has possibly eliminated jump instructions 211190075Sobrien or converted the unconditional jumps. Eliminate the edges from CFG. 211290075Sobrien Return true if any edges are eliminated. */ 211390075Sobrien 211490075Sobrienbool 2115132718Skanpurge_dead_edges (basic_block bb) 211690075Sobrien{ 2117169689Skan edge e; 2118132718Skan rtx insn = BB_END (bb), note; 211990075Sobrien bool purged = false; 2120169689Skan bool found; 2121169689Skan edge_iterator ei; 212290075Sobrien 212396263Sobrien /* If this instruction cannot trap, remove REG_EH_REGION notes. */ 2124169689Skan if (NONJUMP_INSN_P (insn) 212596263Sobrien && (note = find_reg_note (insn, REG_EH_REGION, NULL))) 212696263Sobrien { 212796263Sobrien rtx eqnote; 212890075Sobrien 212996263Sobrien if (! may_trap_p (PATTERN (insn)) 213096263Sobrien || ((eqnote = find_reg_equal_equiv_note (insn)) 213196263Sobrien && ! may_trap_p (XEXP (eqnote, 0)))) 213296263Sobrien remove_note (insn, note); 213396263Sobrien } 213496263Sobrien 2135117395Skan /* Cleanup abnormal edges caused by exceptions or non-local gotos. */ 2136169689Skan for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) 2137117395Skan { 2138169689Skan /* There are three types of edges we need to handle correctly here: EH 2139169689Skan edges, abnormal call EH edges, and abnormal call non-EH edges. The 2140169689Skan latter can appear when nonlocal gotos are used. */ 2141117395Skan if (e->flags & EDGE_EH) 2142117395Skan { 2143169689Skan if (can_throw_internal (BB_END (bb)) 2144169689Skan /* If this is a call edge, verify that this is a call insn. */ 2145169689Skan && (! (e->flags & EDGE_ABNORMAL_CALL) 2146169689Skan || CALL_P (BB_END (bb)))) 2147169689Skan { 2148169689Skan ei_next (&ei); 2149169689Skan continue; 2150169689Skan } 2151117395Skan } 2152117395Skan else if (e->flags & EDGE_ABNORMAL_CALL) 2153117395Skan { 2154169689Skan if (CALL_P (BB_END (bb)) 2155117395Skan && (! (note = find_reg_note (insn, REG_EH_REGION, NULL)) 2156117395Skan || INTVAL (XEXP (note, 0)) >= 0)) 2157169689Skan { 2158169689Skan ei_next (&ei); 2159169689Skan continue; 2160169689Skan } 2161117395Skan } 2162117395Skan else 2163169689Skan { 2164169689Skan ei_next (&ei); 2165169689Skan continue; 2166169689Skan } 216796263Sobrien 2168117395Skan remove_edge (e); 2169117395Skan bb->flags |= BB_DIRTY; 2170117395Skan purged = true; 2171117395Skan } 2172117395Skan 2173169689Skan if (JUMP_P (insn)) 217490075Sobrien { 217590075Sobrien rtx note; 217690075Sobrien edge b,f; 2177169689Skan edge_iterator ei; 217890075Sobrien 217990075Sobrien /* We do care only about conditional jumps and simplejumps. */ 218090075Sobrien if (!any_condjump_p (insn) 218190075Sobrien && !returnjump_p (insn) 218290075Sobrien && !simplejump_p (insn)) 2183117395Skan return purged; 218490075Sobrien 2185117395Skan /* Branch probability/prediction notes are defined only for 2186117395Skan condjumps. We've possibly turned condjump into simplejump. */ 2187117395Skan if (simplejump_p (insn)) 2188117395Skan { 2189117395Skan note = find_reg_note (insn, REG_BR_PROB, NULL); 2190117395Skan if (note) 2191117395Skan remove_note (insn, note); 2192117395Skan while ((note = find_reg_note (insn, REG_BR_PRED, NULL))) 2193117395Skan remove_note (insn, note); 2194117395Skan } 2195117395Skan 2196169689Skan for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) 219790075Sobrien { 219890075Sobrien /* Avoid abnormal flags to leak from computed jumps turned 219990075Sobrien into simplejumps. */ 2200117395Skan 220190075Sobrien e->flags &= ~EDGE_ABNORMAL; 220290075Sobrien 2203102780Skan /* See if this edge is one we should keep. */ 2204102780Skan if ((e->flags & EDGE_FALLTHRU) && any_condjump_p (insn)) 2205102780Skan /* A conditional jump can fall through into the next 2206102780Skan block, so we should keep the edge. */ 2207169689Skan { 2208169689Skan ei_next (&ei); 2209169689Skan continue; 2210169689Skan } 221190075Sobrien else if (e->dest != EXIT_BLOCK_PTR 2212132718Skan && BB_HEAD (e->dest) == JUMP_LABEL (insn)) 2213102780Skan /* If the destination block is the target of the jump, 2214102780Skan keep the edge. */ 2215169689Skan { 2216169689Skan ei_next (&ei); 2217169689Skan continue; 2218169689Skan } 2219102780Skan else if (e->dest == EXIT_BLOCK_PTR && returnjump_p (insn)) 2220102780Skan /* If the destination block is the exit block, and this 2221102780Skan instruction is a return, then keep the edge. */ 2222169689Skan { 2223169689Skan ei_next (&ei); 2224169689Skan continue; 2225169689Skan } 2226102780Skan else if ((e->flags & EDGE_EH) && can_throw_internal (insn)) 2227102780Skan /* Keep the edges that correspond to exceptions thrown by 2228132718Skan this instruction and rematerialize the EDGE_ABNORMAL 2229132718Skan flag we just cleared above. */ 2230122180Skan { 2231122180Skan e->flags |= EDGE_ABNORMAL; 2232169689Skan ei_next (&ei); 2233122180Skan continue; 2234122180Skan } 223590075Sobrien 2236102780Skan /* We do not need this edge. */ 2237117395Skan bb->flags |= BB_DIRTY; 223890075Sobrien purged = true; 223990075Sobrien remove_edge (e); 224090075Sobrien } 224190075Sobrien 2242169689Skan if (EDGE_COUNT (bb->succs) == 0 || !purged) 2243117395Skan return purged; 224490075Sobrien 2245169689Skan if (dump_file) 2246169689Skan fprintf (dump_file, "Purged edges from bb %i\n", bb->index); 224790075Sobrien 224890075Sobrien if (!optimize) 224990075Sobrien return purged; 225090075Sobrien 225190075Sobrien /* Redistribute probabilities. */ 2252169689Skan if (single_succ_p (bb)) 225390075Sobrien { 2254169689Skan single_succ_edge (bb)->probability = REG_BR_PROB_BASE; 2255169689Skan single_succ_edge (bb)->count = bb->count; 2256117395Skan } 225790075Sobrien else 225890075Sobrien { 225990075Sobrien note = find_reg_note (insn, REG_BR_PROB, NULL); 226090075Sobrien if (!note) 226190075Sobrien return purged; 226290075Sobrien 226390075Sobrien b = BRANCH_EDGE (bb); 226490075Sobrien f = FALLTHRU_EDGE (bb); 226590075Sobrien b->probability = INTVAL (XEXP (note, 0)); 226690075Sobrien f->probability = REG_BR_PROB_BASE - b->probability; 226790075Sobrien b->count = bb->count * b->probability / REG_BR_PROB_BASE; 226890075Sobrien f->count = bb->count * f->probability / REG_BR_PROB_BASE; 226990075Sobrien } 227090075Sobrien 227190075Sobrien return purged; 227290075Sobrien } 2273169689Skan else if (CALL_P (insn) && SIBLING_CALL_P (insn)) 2274132718Skan { 2275132718Skan /* First, there should not be any EH or ABCALL edges resulting 2276132718Skan from non-local gotos and the like. If there were, we shouldn't 2277132718Skan have created the sibcall in the first place. Second, there 2278132718Skan should of course never have been a fallthru edge. */ 2279169689Skan gcc_assert (single_succ_p (bb)); 2280169689Skan gcc_assert (single_succ_edge (bb)->flags 2281169689Skan == (EDGE_SIBCALL | EDGE_ABNORMAL)); 228290075Sobrien 2283132718Skan return 0; 2284132718Skan } 2285132718Skan 228690075Sobrien /* If we don't see a jump insn, we don't know exactly why the block would 228790075Sobrien have been broken at this point. Look for a simple, non-fallthru edge, 228890075Sobrien as these are only created by conditional branches. If we find such an 228990075Sobrien edge we know that there used to be a jump here and can then safely 229090075Sobrien remove all non-fallthru edges. */ 2291169689Skan found = false; 2292169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 2293169689Skan if (! (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))) 2294169689Skan { 2295169689Skan found = true; 2296169689Skan break; 2297169689Skan } 229890075Sobrien 2299169689Skan if (!found) 230090075Sobrien return purged; 230190075Sobrien 2302169689Skan /* Remove all but the fake and fallthru edges. The fake edge may be 2303169689Skan the only successor for this block in the case of noreturn 2304169689Skan calls. */ 2305169689Skan for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) 230690075Sobrien { 2307169689Skan if (!(e->flags & (EDGE_FALLTHRU | EDGE_FAKE))) 2308117395Skan { 2309117395Skan bb->flags |= BB_DIRTY; 2310117395Skan remove_edge (e); 2311117395Skan purged = true; 2312117395Skan } 2313169689Skan else 2314169689Skan ei_next (&ei); 231590075Sobrien } 231690075Sobrien 2317169689Skan gcc_assert (single_succ_p (bb)); 231890075Sobrien 2319169689Skan single_succ_edge (bb)->probability = REG_BR_PROB_BASE; 2320169689Skan single_succ_edge (bb)->count = bb->count; 232190075Sobrien 2322169689Skan if (dump_file) 2323169689Skan fprintf (dump_file, "Purged non-fallthru edges from bb %i\n", 232490075Sobrien bb->index); 232590075Sobrien return purged; 232690075Sobrien} 232790075Sobrien 232890075Sobrien/* Search all basic blocks for potentially dead edges and purge them. Return 232990075Sobrien true if some edge has been eliminated. */ 233090075Sobrien 233190075Sobrienbool 2332169689Skanpurge_all_dead_edges (void) 233390075Sobrien{ 2334117395Skan int purged = false; 2335117395Skan basic_block bb; 233690075Sobrien 2337117395Skan FOR_EACH_BB (bb) 233890075Sobrien { 2339117395Skan bool purged_here = purge_dead_edges (bb); 234090075Sobrien 234190075Sobrien purged |= purged_here; 234290075Sobrien } 234390075Sobrien 234490075Sobrien return purged; 234590075Sobrien} 2346132718Skan 2347132718Skan/* Same as split_block but update cfg_layout structures. */ 2348169689Skan 2349169689Skanstatic basic_block 2350132718Skancfg_layout_split_block (basic_block bb, void *insnp) 2351132718Skan{ 2352132718Skan rtx insn = insnp; 2353169689Skan basic_block new_bb = rtl_split_block (bb, insn); 2354132718Skan 2355169689Skan new_bb->il.rtl->footer = bb->il.rtl->footer; 2356169689Skan bb->il.rtl->footer = NULL; 2357132718Skan 2358169689Skan return new_bb; 2359132718Skan} 2360132718Skan 2361132718Skan 2362132718Skan/* Redirect Edge to DEST. */ 2363169689Skanstatic edge 2364132718Skancfg_layout_redirect_edge_and_branch (edge e, basic_block dest) 2365132718Skan{ 2366132718Skan basic_block src = e->src; 2367169689Skan edge ret; 2368132718Skan 2369132718Skan if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)) 2370169689Skan return NULL; 2371132718Skan 2372132718Skan if (e->dest == dest) 2373169689Skan return e; 2374132718Skan 2375132718Skan if (e->src != ENTRY_BLOCK_PTR 2376169689Skan && (ret = try_redirect_by_replacing_jump (e, dest, true))) 2377169689Skan { 2378169689Skan src->flags |= BB_DIRTY; 2379169689Skan return ret; 2380169689Skan } 2381132718Skan 2382132718Skan if (e->src == ENTRY_BLOCK_PTR 2383132718Skan && (e->flags & EDGE_FALLTHRU) && !(e->flags & EDGE_COMPLEX)) 2384132718Skan { 2385169689Skan if (dump_file) 2386169689Skan fprintf (dump_file, "Redirecting entry edge from bb %i to %i\n", 2387132718Skan e->src->index, dest->index); 2388132718Skan 2389169689Skan e->src->flags |= BB_DIRTY; 2390132718Skan redirect_edge_succ (e, dest); 2391169689Skan return e; 2392132718Skan } 2393132718Skan 2394132718Skan /* Redirect_edge_and_branch may decide to turn branch into fallthru edge 2395132718Skan in the case the basic block appears to be in sequence. Avoid this 2396132718Skan transformation. */ 2397132718Skan 2398132718Skan if (e->flags & EDGE_FALLTHRU) 2399132718Skan { 2400132718Skan /* Redirect any branch edges unified with the fallthru one. */ 2401169689Skan if (JUMP_P (BB_END (src)) 2402132718Skan && label_is_jump_target_p (BB_HEAD (e->dest), 2403132718Skan BB_END (src))) 2404132718Skan { 2405169689Skan edge redirected; 2406169689Skan 2407169689Skan if (dump_file) 2408169689Skan fprintf (dump_file, "Fallthru edge unified with branch " 2409132718Skan "%i->%i redirected to %i\n", 2410132718Skan e->src->index, e->dest->index, dest->index); 2411132718Skan e->flags &= ~EDGE_FALLTHRU; 2412169689Skan redirected = redirect_branch_edge (e, dest); 2413169689Skan gcc_assert (redirected); 2414132718Skan e->flags |= EDGE_FALLTHRU; 2415169689Skan e->src->flags |= BB_DIRTY; 2416169689Skan return e; 2417132718Skan } 2418132718Skan /* In case we are redirecting fallthru edge to the branch edge 2419169689Skan of conditional jump, remove it. */ 2420169689Skan if (EDGE_COUNT (src->succs) == 2) 2421132718Skan { 2422169689Skan /* Find the edge that is different from E. */ 2423169689Skan edge s = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e); 2424169689Skan 2425132718Skan if (s->dest == dest 2426132718Skan && any_condjump_p (BB_END (src)) 2427132718Skan && onlyjump_p (BB_END (src))) 2428132718Skan delete_insn (BB_END (src)); 2429132718Skan } 2430169689Skan ret = redirect_edge_succ_nodup (e, dest); 2431169689Skan if (dump_file) 2432169689Skan fprintf (dump_file, "Fallthru edge %i->%i redirected to %i\n", 2433132718Skan e->src->index, e->dest->index, dest->index); 2434132718Skan } 2435132718Skan else 2436132718Skan ret = redirect_branch_edge (e, dest); 2437132718Skan 2438132718Skan /* We don't want simplejumps in the insn stream during cfglayout. */ 2439169689Skan gcc_assert (!simplejump_p (BB_END (src))); 2440132718Skan 2441169689Skan src->flags |= BB_DIRTY; 2442132718Skan return ret; 2443132718Skan} 2444132718Skan 2445132718Skan/* Simple wrapper as we always can redirect fallthru edges. */ 2446132718Skanstatic basic_block 2447132718Skancfg_layout_redirect_edge_and_branch_force (edge e, basic_block dest) 2448132718Skan{ 2449169689Skan edge redirected = cfg_layout_redirect_edge_and_branch (e, dest); 2450169689Skan 2451169689Skan gcc_assert (redirected); 2452132718Skan return NULL; 2453132718Skan} 2454132718Skan 2455169689Skan/* Same as delete_basic_block but update cfg_layout structures. */ 2456169689Skan 2457132718Skanstatic void 2458132718Skancfg_layout_delete_block (basic_block bb) 2459132718Skan{ 2460132718Skan rtx insn, next, prev = PREV_INSN (BB_HEAD (bb)), *to, remaints; 2461132718Skan 2462169689Skan if (bb->il.rtl->header) 2463132718Skan { 2464132718Skan next = BB_HEAD (bb); 2465132718Skan if (prev) 2466169689Skan NEXT_INSN (prev) = bb->il.rtl->header; 2467132718Skan else 2468169689Skan set_first_insn (bb->il.rtl->header); 2469169689Skan PREV_INSN (bb->il.rtl->header) = prev; 2470169689Skan insn = bb->il.rtl->header; 2471132718Skan while (NEXT_INSN (insn)) 2472132718Skan insn = NEXT_INSN (insn); 2473132718Skan NEXT_INSN (insn) = next; 2474132718Skan PREV_INSN (next) = insn; 2475132718Skan } 2476132718Skan next = NEXT_INSN (BB_END (bb)); 2477169689Skan if (bb->il.rtl->footer) 2478132718Skan { 2479169689Skan insn = bb->il.rtl->footer; 2480132718Skan while (insn) 2481132718Skan { 2482169689Skan if (BARRIER_P (insn)) 2483132718Skan { 2484132718Skan if (PREV_INSN (insn)) 2485132718Skan NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn); 2486132718Skan else 2487169689Skan bb->il.rtl->footer = NEXT_INSN (insn); 2488132718Skan if (NEXT_INSN (insn)) 2489132718Skan PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn); 2490132718Skan } 2491169689Skan if (LABEL_P (insn)) 2492132718Skan break; 2493132718Skan insn = NEXT_INSN (insn); 2494132718Skan } 2495169689Skan if (bb->il.rtl->footer) 2496132718Skan { 2497132718Skan insn = BB_END (bb); 2498169689Skan NEXT_INSN (insn) = bb->il.rtl->footer; 2499169689Skan PREV_INSN (bb->il.rtl->footer) = insn; 2500132718Skan while (NEXT_INSN (insn)) 2501132718Skan insn = NEXT_INSN (insn); 2502132718Skan NEXT_INSN (insn) = next; 2503132718Skan if (next) 2504132718Skan PREV_INSN (next) = insn; 2505132718Skan else 2506132718Skan set_last_insn (insn); 2507132718Skan } 2508132718Skan } 2509132718Skan if (bb->next_bb != EXIT_BLOCK_PTR) 2510169689Skan to = &bb->next_bb->il.rtl->header; 2511132718Skan else 2512132718Skan to = &cfg_layout_function_footer; 2513169689Skan 2514132718Skan rtl_delete_block (bb); 2515132718Skan 2516132718Skan if (prev) 2517132718Skan prev = NEXT_INSN (prev); 2518132718Skan else 2519132718Skan prev = get_insns (); 2520132718Skan if (next) 2521132718Skan next = PREV_INSN (next); 2522132718Skan else 2523132718Skan next = get_last_insn (); 2524132718Skan 2525132718Skan if (next && NEXT_INSN (next) != prev) 2526132718Skan { 2527132718Skan remaints = unlink_insn_chain (prev, next); 2528132718Skan insn = remaints; 2529132718Skan while (NEXT_INSN (insn)) 2530132718Skan insn = NEXT_INSN (insn); 2531132718Skan NEXT_INSN (insn) = *to; 2532132718Skan if (*to) 2533132718Skan PREV_INSN (*to) = insn; 2534132718Skan *to = remaints; 2535132718Skan } 2536132718Skan} 2537132718Skan 2538132718Skan/* Return true when blocks A and B can be safely merged. */ 2539132718Skanstatic bool 2540132718Skancfg_layout_can_merge_blocks_p (basic_block a, basic_block b) 2541132718Skan{ 2542169689Skan /* If we are partitioning hot/cold basic blocks, we don't want to 2543169689Skan mess up unconditional or indirect jumps that cross between hot 2544169689Skan and cold sections. 2545169689Skan 2546169689Skan Basic block partitioning may result in some jumps that appear to 2547169689Skan be optimizable (or blocks that appear to be mergeable), but which really 2548169689Skan must be left untouched (they are required to make it safely across 2549169689Skan partition boundaries). See the comments at the top of 2550169689Skan bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */ 2551169689Skan 2552169689Skan if (BB_PARTITION (a) != BB_PARTITION (b)) 2553169689Skan return false; 2554169689Skan 2555132718Skan /* There must be exactly one edge in between the blocks. */ 2556169689Skan return (single_succ_p (a) 2557169689Skan && single_succ (a) == b 2558169689Skan && single_pred_p (b) == 1 2559169689Skan && a != b 2560132718Skan /* Must be simple edge. */ 2561169689Skan && !(single_succ_edge (a)->flags & EDGE_COMPLEX) 2562132718Skan && a != ENTRY_BLOCK_PTR && b != EXIT_BLOCK_PTR 2563132718Skan /* If the jump insn has side effects, 2564132718Skan we can't kill the edge. */ 2565169689Skan && (!JUMP_P (BB_END (a)) 2566132718Skan || (reload_completed 2567132718Skan ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a))))); 2568132718Skan} 2569132718Skan 2570169689Skan/* Merge block A and B. The blocks must be mergeable. */ 2571169689Skan 2572132718Skanstatic void 2573132718Skancfg_layout_merge_blocks (basic_block a, basic_block b) 2574132718Skan{ 2575132718Skan#ifdef ENABLE_CHECKING 2576169689Skan gcc_assert (cfg_layout_can_merge_blocks_p (a, b)); 2577132718Skan#endif 2578132718Skan 2579132718Skan /* If there was a CODE_LABEL beginning B, delete it. */ 2580169689Skan if (LABEL_P (BB_HEAD (b))) 2581169689Skan { 2582169689Skan /* This might have been an EH label that no longer has incoming 2583169689Skan EH edges. Update data structures to match. */ 2584169689Skan maybe_remove_eh_handler (BB_HEAD (b)); 2585132718Skan 2586169689Skan delete_insn (BB_HEAD (b)); 2587169689Skan } 2588169689Skan 2589132718Skan /* We should have fallthru edge in a, or we can do dummy redirection to get 2590132718Skan it cleaned up. */ 2591169689Skan if (JUMP_P (BB_END (a))) 2592169689Skan try_redirect_by_replacing_jump (EDGE_SUCC (a, 0), b, true); 2593169689Skan gcc_assert (!JUMP_P (BB_END (a))); 2594132718Skan 2595132718Skan /* Possible line number notes should appear in between. */ 2596169689Skan if (b->il.rtl->header) 2597132718Skan { 2598132718Skan rtx first = BB_END (a), last; 2599132718Skan 2600169689Skan last = emit_insn_after_noloc (b->il.rtl->header, BB_END (a)); 2601132718Skan delete_insn_chain (NEXT_INSN (first), last); 2602169689Skan b->il.rtl->header = NULL; 2603132718Skan } 2604132718Skan 2605132718Skan /* In the case basic blocks are not adjacent, move them around. */ 2606132718Skan if (NEXT_INSN (BB_END (a)) != BB_HEAD (b)) 2607132718Skan { 2608132718Skan rtx first = unlink_insn_chain (BB_HEAD (b), BB_END (b)); 2609132718Skan 2610132718Skan emit_insn_after_noloc (first, BB_END (a)); 2611132718Skan /* Skip possible DELETED_LABEL insn. */ 2612132718Skan if (!NOTE_INSN_BASIC_BLOCK_P (first)) 2613132718Skan first = NEXT_INSN (first); 2614169689Skan gcc_assert (NOTE_INSN_BASIC_BLOCK_P (first)); 2615132718Skan BB_HEAD (b) = NULL; 2616132718Skan delete_insn (first); 2617132718Skan } 2618132718Skan /* Otherwise just re-associate the instructions. */ 2619132718Skan else 2620132718Skan { 2621132718Skan rtx insn; 2622132718Skan 2623132718Skan for (insn = BB_HEAD (b); 2624132718Skan insn != NEXT_INSN (BB_END (b)); 2625132718Skan insn = NEXT_INSN (insn)) 2626132718Skan set_block_for_insn (insn, a); 2627132718Skan insn = BB_HEAD (b); 2628132718Skan /* Skip possible DELETED_LABEL insn. */ 2629132718Skan if (!NOTE_INSN_BASIC_BLOCK_P (insn)) 2630132718Skan insn = NEXT_INSN (insn); 2631169689Skan gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn)); 2632132718Skan BB_HEAD (b) = NULL; 2633132718Skan BB_END (a) = BB_END (b); 2634132718Skan delete_insn (insn); 2635132718Skan } 2636132718Skan 2637132718Skan /* Possible tablejumps and barriers should appear after the block. */ 2638169689Skan if (b->il.rtl->footer) 2639132718Skan { 2640169689Skan if (!a->il.rtl->footer) 2641169689Skan a->il.rtl->footer = b->il.rtl->footer; 2642132718Skan else 2643132718Skan { 2644169689Skan rtx last = a->il.rtl->footer; 2645132718Skan 2646132718Skan while (NEXT_INSN (last)) 2647132718Skan last = NEXT_INSN (last); 2648169689Skan NEXT_INSN (last) = b->il.rtl->footer; 2649169689Skan PREV_INSN (b->il.rtl->footer) = last; 2650132718Skan } 2651169689Skan b->il.rtl->footer = NULL; 2652132718Skan } 2653169689Skan a->il.rtl->global_live_at_end = b->il.rtl->global_live_at_end; 2654132718Skan 2655169689Skan if (dump_file) 2656169689Skan fprintf (dump_file, "Merged blocks %d and %d.\n", 2657132718Skan a->index, b->index); 2658132718Skan} 2659132718Skan 2660132718Skan/* Split edge E. */ 2661169689Skan 2662132718Skanstatic basic_block 2663132718Skancfg_layout_split_edge (edge e) 2664132718Skan{ 2665132718Skan basic_block new_bb = 2666132718Skan create_basic_block (e->src != ENTRY_BLOCK_PTR 2667132718Skan ? NEXT_INSN (BB_END (e->src)) : get_insns (), 2668132718Skan NULL_RTX, e->src); 2669132718Skan 2670146895Skan /* ??? This info is likely going to be out of date very soon, but we must 2671146895Skan create it to avoid getting an ICE later. */ 2672169689Skan if (e->dest->il.rtl->global_live_at_start) 2673146895Skan { 2674169689Skan new_bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack); 2675169689Skan new_bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack); 2676169689Skan COPY_REG_SET (new_bb->il.rtl->global_live_at_start, 2677169689Skan e->dest->il.rtl->global_live_at_start); 2678169689Skan COPY_REG_SET (new_bb->il.rtl->global_live_at_end, 2679169689Skan e->dest->il.rtl->global_live_at_start); 2680146895Skan } 2681146895Skan 2682169689Skan make_edge (new_bb, e->dest, EDGE_FALLTHRU); 2683132718Skan redirect_edge_and_branch_force (e, new_bb); 2684132718Skan 2685132718Skan return new_bb; 2686132718Skan} 2687132718Skan 2688169689Skan/* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */ 2689169689Skan 2690169689Skanstatic void 2691169689Skanrtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED) 2692169689Skan{ 2693169689Skan} 2694169689Skan 2695169689Skan/* Return 1 if BB ends with a call, possibly followed by some 2696169689Skan instructions that must stay with the call, 0 otherwise. */ 2697169689Skan 2698169689Skanstatic bool 2699169689Skanrtl_block_ends_with_call_p (basic_block bb) 2700169689Skan{ 2701169689Skan rtx insn = BB_END (bb); 2702169689Skan 2703169689Skan while (!CALL_P (insn) 2704169689Skan && insn != BB_HEAD (bb) 2705169689Skan && keep_with_call_p (insn)) 2706169689Skan insn = PREV_INSN (insn); 2707169689Skan return (CALL_P (insn)); 2708169689Skan} 2709169689Skan 2710169689Skan/* Return 1 if BB ends with a conditional branch, 0 otherwise. */ 2711169689Skan 2712169689Skanstatic bool 2713169689Skanrtl_block_ends_with_condjump_p (basic_block bb) 2714169689Skan{ 2715169689Skan return any_condjump_p (BB_END (bb)); 2716169689Skan} 2717169689Skan 2718169689Skan/* Return true if we need to add fake edge to exit. 2719169689Skan Helper function for rtl_flow_call_edges_add. */ 2720169689Skan 2721169689Skanstatic bool 2722169689Skanneed_fake_edge_p (rtx insn) 2723169689Skan{ 2724169689Skan if (!INSN_P (insn)) 2725169689Skan return false; 2726169689Skan 2727169689Skan if ((CALL_P (insn) 2728169689Skan && !SIBLING_CALL_P (insn) 2729169689Skan && !find_reg_note (insn, REG_NORETURN, NULL) 2730169689Skan && !CONST_OR_PURE_CALL_P (insn))) 2731169689Skan return true; 2732169689Skan 2733169689Skan return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS 2734169689Skan && MEM_VOLATILE_P (PATTERN (insn))) 2735169689Skan || (GET_CODE (PATTERN (insn)) == PARALLEL 2736169689Skan && asm_noperands (insn) != -1 2737169689Skan && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0))) 2738169689Skan || GET_CODE (PATTERN (insn)) == ASM_INPUT); 2739169689Skan} 2740169689Skan 2741169689Skan/* Add fake edges to the function exit for any non constant and non noreturn 2742169689Skan calls, volatile inline assembly in the bitmap of blocks specified by 2743169689Skan BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks 2744169689Skan that were split. 2745169689Skan 2746169689Skan The goal is to expose cases in which entering a basic block does not imply 2747169689Skan that all subsequent instructions must be executed. */ 2748169689Skan 2749169689Skanstatic int 2750169689Skanrtl_flow_call_edges_add (sbitmap blocks) 2751169689Skan{ 2752169689Skan int i; 2753169689Skan int blocks_split = 0; 2754169689Skan int last_bb = last_basic_block; 2755169689Skan bool check_last_block = false; 2756169689Skan 2757169689Skan if (n_basic_blocks == NUM_FIXED_BLOCKS) 2758169689Skan return 0; 2759169689Skan 2760169689Skan if (! blocks) 2761169689Skan check_last_block = true; 2762169689Skan else 2763169689Skan check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index); 2764169689Skan 2765169689Skan /* In the last basic block, before epilogue generation, there will be 2766169689Skan a fallthru edge to EXIT. Special care is required if the last insn 2767169689Skan of the last basic block is a call because make_edge folds duplicate 2768169689Skan edges, which would result in the fallthru edge also being marked 2769169689Skan fake, which would result in the fallthru edge being removed by 2770169689Skan remove_fake_edges, which would result in an invalid CFG. 2771169689Skan 2772169689Skan Moreover, we can't elide the outgoing fake edge, since the block 2773169689Skan profiler needs to take this into account in order to solve the minimal 2774169689Skan spanning tree in the case that the call doesn't return. 2775169689Skan 2776169689Skan Handle this by adding a dummy instruction in a new last basic block. */ 2777169689Skan if (check_last_block) 2778169689Skan { 2779169689Skan basic_block bb = EXIT_BLOCK_PTR->prev_bb; 2780169689Skan rtx insn = BB_END (bb); 2781169689Skan 2782169689Skan /* Back up past insns that must be kept in the same block as a call. */ 2783169689Skan while (insn != BB_HEAD (bb) 2784169689Skan && keep_with_call_p (insn)) 2785169689Skan insn = PREV_INSN (insn); 2786169689Skan 2787169689Skan if (need_fake_edge_p (insn)) 2788169689Skan { 2789169689Skan edge e; 2790169689Skan 2791169689Skan e = find_edge (bb, EXIT_BLOCK_PTR); 2792169689Skan if (e) 2793169689Skan { 2794169689Skan insert_insn_on_edge (gen_rtx_USE (VOIDmode, const0_rtx), e); 2795169689Skan commit_edge_insertions (); 2796169689Skan } 2797169689Skan } 2798169689Skan } 2799169689Skan 2800169689Skan /* Now add fake edges to the function exit for any non constant 2801169689Skan calls since there is no way that we can determine if they will 2802169689Skan return or not... */ 2803169689Skan 2804169689Skan for (i = NUM_FIXED_BLOCKS; i < last_bb; i++) 2805169689Skan { 2806169689Skan basic_block bb = BASIC_BLOCK (i); 2807169689Skan rtx insn; 2808169689Skan rtx prev_insn; 2809169689Skan 2810169689Skan if (!bb) 2811169689Skan continue; 2812169689Skan 2813169689Skan if (blocks && !TEST_BIT (blocks, i)) 2814169689Skan continue; 2815169689Skan 2816169689Skan for (insn = BB_END (bb); ; insn = prev_insn) 2817169689Skan { 2818169689Skan prev_insn = PREV_INSN (insn); 2819169689Skan if (need_fake_edge_p (insn)) 2820169689Skan { 2821169689Skan edge e; 2822169689Skan rtx split_at_insn = insn; 2823169689Skan 2824169689Skan /* Don't split the block between a call and an insn that should 2825169689Skan remain in the same block as the call. */ 2826169689Skan if (CALL_P (insn)) 2827169689Skan while (split_at_insn != BB_END (bb) 2828169689Skan && keep_with_call_p (NEXT_INSN (split_at_insn))) 2829169689Skan split_at_insn = NEXT_INSN (split_at_insn); 2830169689Skan 2831169689Skan /* The handling above of the final block before the epilogue 2832169689Skan should be enough to verify that there is no edge to the exit 2833169689Skan block in CFG already. Calling make_edge in such case would 2834169689Skan cause us to mark that edge as fake and remove it later. */ 2835169689Skan 2836169689Skan#ifdef ENABLE_CHECKING 2837169689Skan if (split_at_insn == BB_END (bb)) 2838169689Skan { 2839169689Skan e = find_edge (bb, EXIT_BLOCK_PTR); 2840169689Skan gcc_assert (e == NULL); 2841169689Skan } 2842169689Skan#endif 2843169689Skan 2844169689Skan /* Note that the following may create a new basic block 2845169689Skan and renumber the existing basic blocks. */ 2846169689Skan if (split_at_insn != BB_END (bb)) 2847169689Skan { 2848169689Skan e = split_block (bb, split_at_insn); 2849169689Skan if (e) 2850169689Skan blocks_split++; 2851169689Skan } 2852169689Skan 2853169689Skan make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE); 2854169689Skan } 2855169689Skan 2856169689Skan if (insn == BB_HEAD (bb)) 2857169689Skan break; 2858169689Skan } 2859169689Skan } 2860169689Skan 2861169689Skan if (blocks_split) 2862169689Skan verify_flow_info (); 2863169689Skan 2864169689Skan return blocks_split; 2865169689Skan} 2866169689Skan 2867169689Skan/* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is 2868169689Skan the conditional branch target, SECOND_HEAD should be the fall-thru 2869169689Skan there is no need to handle this here the loop versioning code handles 2870169689Skan this. the reason for SECON_HEAD is that it is needed for condition 2871169689Skan in trees, and this should be of the same type since it is a hook. */ 2872169689Skanstatic void 2873169689Skanrtl_lv_add_condition_to_bb (basic_block first_head , 2874169689Skan basic_block second_head ATTRIBUTE_UNUSED, 2875169689Skan basic_block cond_bb, void *comp_rtx) 2876169689Skan{ 2877169689Skan rtx label, seq, jump; 2878169689Skan rtx op0 = XEXP ((rtx)comp_rtx, 0); 2879169689Skan rtx op1 = XEXP ((rtx)comp_rtx, 1); 2880169689Skan enum rtx_code comp = GET_CODE ((rtx)comp_rtx); 2881169689Skan enum machine_mode mode; 2882169689Skan 2883169689Skan 2884169689Skan label = block_label (first_head); 2885169689Skan mode = GET_MODE (op0); 2886169689Skan if (mode == VOIDmode) 2887169689Skan mode = GET_MODE (op1); 2888169689Skan 2889169689Skan start_sequence (); 2890169689Skan op0 = force_operand (op0, NULL_RTX); 2891169689Skan op1 = force_operand (op1, NULL_RTX); 2892169689Skan do_compare_rtx_and_jump (op0, op1, comp, 0, 2893169689Skan mode, NULL_RTX, NULL_RTX, label); 2894169689Skan jump = get_last_insn (); 2895169689Skan JUMP_LABEL (jump) = label; 2896169689Skan LABEL_NUSES (label)++; 2897169689Skan seq = get_insns (); 2898169689Skan end_sequence (); 2899169689Skan 2900169689Skan /* Add the new cond , in the new head. */ 2901169689Skan emit_insn_after(seq, BB_END(cond_bb)); 2902169689Skan} 2903169689Skan 2904169689Skan 2905169689Skan/* Given a block B with unconditional branch at its end, get the 2906169689Skan store the return the branch edge and the fall-thru edge in 2907169689Skan BRANCH_EDGE and FALLTHRU_EDGE respectively. */ 2908169689Skanstatic void 2909169689Skanrtl_extract_cond_bb_edges (basic_block b, edge *branch_edge, 2910169689Skan edge *fallthru_edge) 2911169689Skan{ 2912169689Skan edge e = EDGE_SUCC (b, 0); 2913169689Skan 2914169689Skan if (e->flags & EDGE_FALLTHRU) 2915169689Skan { 2916169689Skan *fallthru_edge = e; 2917169689Skan *branch_edge = EDGE_SUCC (b, 1); 2918169689Skan } 2919169689Skan else 2920169689Skan { 2921169689Skan *branch_edge = e; 2922169689Skan *fallthru_edge = EDGE_SUCC (b, 1); 2923169689Skan } 2924169689Skan} 2925169689Skan 2926169689Skanvoid 2927169689Skaninit_rtl_bb_info (basic_block bb) 2928169689Skan{ 2929169689Skan gcc_assert (!bb->il.rtl); 2930169689Skan bb->il.rtl = ggc_alloc_cleared (sizeof (struct rtl_bb_info)); 2931169689Skan} 2932169689Skan 2933169689Skan 2934169689Skan/* Add EXPR to the end of basic block BB. */ 2935169689Skan 2936169689Skanrtx 2937169689Skaninsert_insn_end_bb_new (rtx pat, basic_block bb) 2938169689Skan{ 2939169689Skan rtx insn = BB_END (bb); 2940169689Skan rtx new_insn; 2941169689Skan rtx pat_end = pat; 2942169689Skan 2943169689Skan while (NEXT_INSN (pat_end) != NULL_RTX) 2944169689Skan pat_end = NEXT_INSN (pat_end); 2945169689Skan 2946169689Skan /* If the last insn is a jump, insert EXPR in front [taking care to 2947169689Skan handle cc0, etc. properly]. Similarly we need to care trapping 2948169689Skan instructions in presence of non-call exceptions. */ 2949169689Skan 2950169689Skan if (JUMP_P (insn) 2951169689Skan || (NONJUMP_INSN_P (insn) 2952169689Skan && (!single_succ_p (bb) 2953169689Skan || single_succ_edge (bb)->flags & EDGE_ABNORMAL))) 2954169689Skan { 2955169689Skan#ifdef HAVE_cc0 2956169689Skan rtx note; 2957169689Skan#endif 2958169689Skan /* If this is a jump table, then we can't insert stuff here. Since 2959169689Skan we know the previous real insn must be the tablejump, we insert 2960169689Skan the new instruction just before the tablejump. */ 2961169689Skan if (GET_CODE (PATTERN (insn)) == ADDR_VEC 2962169689Skan || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC) 2963169689Skan insn = prev_real_insn (insn); 2964169689Skan 2965169689Skan#ifdef HAVE_cc0 2966169689Skan /* FIXME: 'twould be nice to call prev_cc0_setter here but it aborts 2967169689Skan if cc0 isn't set. */ 2968169689Skan note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX); 2969169689Skan if (note) 2970169689Skan insn = XEXP (note, 0); 2971169689Skan else 2972169689Skan { 2973169689Skan rtx maybe_cc0_setter = prev_nonnote_insn (insn); 2974169689Skan if (maybe_cc0_setter 2975169689Skan && INSN_P (maybe_cc0_setter) 2976169689Skan && sets_cc0_p (PATTERN (maybe_cc0_setter))) 2977169689Skan insn = maybe_cc0_setter; 2978169689Skan } 2979169689Skan#endif 2980169689Skan /* FIXME: What if something in cc0/jump uses value set in new 2981169689Skan insn? */ 2982169689Skan new_insn = emit_insn_before_noloc (pat, insn); 2983169689Skan } 2984169689Skan 2985169689Skan /* Likewise if the last insn is a call, as will happen in the presence 2986169689Skan of exception handling. */ 2987169689Skan else if (CALL_P (insn) 2988169689Skan && (!single_succ_p (bb) 2989169689Skan || single_succ_edge (bb)->flags & EDGE_ABNORMAL)) 2990169689Skan { 2991169689Skan /* Keeping in mind SMALL_REGISTER_CLASSES and parameters in registers, 2992169689Skan we search backward and place the instructions before the first 2993169689Skan parameter is loaded. Do this for everyone for consistency and a 2994169689Skan presumption that we'll get better code elsewhere as well. */ 2995169689Skan 2996169689Skan /* Since different machines initialize their parameter registers 2997169689Skan in different orders, assume nothing. Collect the set of all 2998169689Skan parameter registers. */ 2999169689Skan insn = find_first_parameter_load (insn, BB_HEAD (bb)); 3000169689Skan 3001169689Skan /* If we found all the parameter loads, then we want to insert 3002169689Skan before the first parameter load. 3003169689Skan 3004169689Skan If we did not find all the parameter loads, then we might have 3005169689Skan stopped on the head of the block, which could be a CODE_LABEL. 3006169689Skan If we inserted before the CODE_LABEL, then we would be putting 3007169689Skan the insn in the wrong basic block. In that case, put the insn 3008169689Skan after the CODE_LABEL. Also, respect NOTE_INSN_BASIC_BLOCK. */ 3009169689Skan while (LABEL_P (insn) 3010169689Skan || NOTE_INSN_BASIC_BLOCK_P (insn)) 3011169689Skan insn = NEXT_INSN (insn); 3012169689Skan 3013169689Skan new_insn = emit_insn_before_noloc (pat, insn); 3014169689Skan } 3015169689Skan else 3016169689Skan new_insn = emit_insn_after_noloc (pat, insn); 3017169689Skan 3018169689Skan return new_insn; 3019169689Skan} 3020169689Skan 3021132718Skan/* Implementation of CFG manipulation for linearized RTL. */ 3022132718Skanstruct cfg_hooks rtl_cfg_hooks = { 3023169689Skan "rtl", 3024132718Skan rtl_verify_flow_info, 3025132718Skan rtl_dump_bb, 3026132718Skan rtl_create_basic_block, 3027132718Skan rtl_redirect_edge_and_branch, 3028132718Skan rtl_redirect_edge_and_branch_force, 3029132718Skan rtl_delete_block, 3030132718Skan rtl_split_block, 3031169689Skan rtl_move_block_after, 3032132718Skan rtl_can_merge_blocks, /* can_merge_blocks_p */ 3033132718Skan rtl_merge_blocks, 3034169689Skan rtl_predict_edge, 3035169689Skan rtl_predicted_by_p, 3036169689Skan NULL, /* can_duplicate_block_p */ 3037169689Skan NULL, /* duplicate_block */ 3038169689Skan rtl_split_edge, 3039169689Skan rtl_make_forwarder_block, 3040169689Skan rtl_tidy_fallthru_edge, 3041169689Skan rtl_block_ends_with_call_p, 3042169689Skan rtl_block_ends_with_condjump_p, 3043169689Skan rtl_flow_call_edges_add, 3044169689Skan NULL, /* execute_on_growing_pred */ 3045169689Skan NULL, /* execute_on_shrinking_pred */ 3046169689Skan NULL, /* duplicate loop for trees */ 3047169689Skan NULL, /* lv_add_condition_to_bb */ 3048169689Skan NULL, /* lv_adjust_loop_header_phi*/ 3049169689Skan NULL, /* extract_cond_bb_edges */ 3050169689Skan NULL /* flush_pending_stmts */ 3051132718Skan}; 3052132718Skan 3053132718Skan/* Implementation of CFG manipulation for cfg layout RTL, where 3054132718Skan basic block connected via fallthru edges does not have to be adjacent. 3055132718Skan This representation will hopefully become the default one in future 3056132718Skan version of the compiler. */ 3057169689Skan 3058169689Skan/* We do not want to declare these functions in a header file, since they 3059169689Skan should only be used through the cfghooks interface, and we do not want to 3060169689Skan move them here since it would require also moving quite a lot of related 3061169689Skan code. */ 3062169689Skanextern bool cfg_layout_can_duplicate_bb_p (basic_block); 3063169689Skanextern basic_block cfg_layout_duplicate_bb (basic_block); 3064169689Skan 3065132718Skanstruct cfg_hooks cfg_layout_rtl_cfg_hooks = { 3066169689Skan "cfglayout mode", 3067132718Skan rtl_verify_flow_info_1, 3068132718Skan rtl_dump_bb, 3069132718Skan cfg_layout_create_basic_block, 3070132718Skan cfg_layout_redirect_edge_and_branch, 3071132718Skan cfg_layout_redirect_edge_and_branch_force, 3072132718Skan cfg_layout_delete_block, 3073132718Skan cfg_layout_split_block, 3074169689Skan rtl_move_block_after, 3075132718Skan cfg_layout_can_merge_blocks_p, 3076132718Skan cfg_layout_merge_blocks, 3077169689Skan rtl_predict_edge, 3078169689Skan rtl_predicted_by_p, 3079169689Skan cfg_layout_can_duplicate_bb_p, 3080169689Skan cfg_layout_duplicate_bb, 3081169689Skan cfg_layout_split_edge, 3082169689Skan rtl_make_forwarder_block, 3083169689Skan NULL, 3084169689Skan rtl_block_ends_with_call_p, 3085169689Skan rtl_block_ends_with_condjump_p, 3086169689Skan rtl_flow_call_edges_add, 3087169689Skan NULL, /* execute_on_growing_pred */ 3088169689Skan NULL, /* execute_on_shrinking_pred */ 3089169689Skan duplicate_loop_to_header_edge, /* duplicate loop for trees */ 3090169689Skan rtl_lv_add_condition_to_bb, /* lv_add_condition_to_bb */ 3091169689Skan NULL, /* lv_adjust_loop_header_phi*/ 3092169689Skan rtl_extract_cond_bb_edges, /* extract_cond_bb_edges */ 3093169689Skan NULL /* flush_pending_stmts */ 3094132718Skan}; 3095