190075Sobrien/* Control flow graph building 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/* find_basic_blocks divides the current function's rtl into basic 2390075Sobrien blocks and constructs the CFG. The blocks are recorded in the 2490075Sobrien basic_block_info array; the CFG exists in the edge structures 2590075Sobrien referenced by the blocks. 2690075Sobrien 2790075Sobrien find_basic_blocks also finds any unreachable loops and deletes them. 2890075Sobrien 2990075Sobrien Available functionality: 3090075Sobrien - CFG construction 31169689Skan find_basic_blocks */ 3290075Sobrien 3390075Sobrien#include "config.h" 3490075Sobrien#include "system.h" 35132718Skan#include "coretypes.h" 36132718Skan#include "tm.h" 3790075Sobrien#include "tree.h" 3890075Sobrien#include "rtl.h" 3990075Sobrien#include "hard-reg-set.h" 4090075Sobrien#include "basic-block.h" 4190075Sobrien#include "regs.h" 4290075Sobrien#include "flags.h" 4390075Sobrien#include "output.h" 4490075Sobrien#include "function.h" 4590075Sobrien#include "except.h" 4690075Sobrien#include "toplev.h" 4790075Sobrien#include "timevar.h" 4890075Sobrien 49132718Skanstatic int count_basic_blocks (rtx); 50132718Skanstatic void find_basic_blocks_1 (rtx); 51169689Skanstatic void make_edges (basic_block, basic_block, int); 52169689Skanstatic void make_label_edge (sbitmap, basic_block, rtx, int); 53132718Skanstatic void find_bb_boundaries (basic_block); 54132718Skanstatic void compute_outgoing_frequencies (basic_block); 5590075Sobrien 5690075Sobrien/* Return true if insn is something that should be contained inside basic 5790075Sobrien block. */ 5890075Sobrien 59132718Skanbool 60132718Skaninside_basic_block_p (rtx insn) 6190075Sobrien{ 6290075Sobrien switch (GET_CODE (insn)) 6390075Sobrien { 6490075Sobrien case CODE_LABEL: 6590075Sobrien /* Avoid creating of basic block for jumptables. */ 6690075Sobrien return (NEXT_INSN (insn) == 0 67169689Skan || !JUMP_P (NEXT_INSN (insn)) 6890075Sobrien || (GET_CODE (PATTERN (NEXT_INSN (insn))) != ADDR_VEC 6990075Sobrien && GET_CODE (PATTERN (NEXT_INSN (insn))) != ADDR_DIFF_VEC)); 7090075Sobrien 7190075Sobrien case JUMP_INSN: 7290075Sobrien return (GET_CODE (PATTERN (insn)) != ADDR_VEC 7390075Sobrien && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC); 7490075Sobrien 7590075Sobrien case CALL_INSN: 7690075Sobrien case INSN: 7790075Sobrien return true; 7890075Sobrien 7990075Sobrien case BARRIER: 8090075Sobrien case NOTE: 8190075Sobrien return false; 8290075Sobrien 8390075Sobrien default: 84169689Skan gcc_unreachable (); 8590075Sobrien } 8690075Sobrien} 8790075Sobrien 8890075Sobrien/* Return true if INSN may cause control flow transfer, so it should be last in 8990075Sobrien the basic block. */ 9090075Sobrien 91110611Skanbool 92132718Skancontrol_flow_insn_p (rtx insn) 9390075Sobrien{ 9490075Sobrien rtx note; 9590075Sobrien 9690075Sobrien switch (GET_CODE (insn)) 9790075Sobrien { 98117395Skan case NOTE: 99117395Skan case CODE_LABEL: 100117395Skan return false; 10190075Sobrien 102117395Skan case JUMP_INSN: 103117395Skan /* Jump insn always causes control transfer except for tablejumps. */ 104117395Skan return (GET_CODE (PATTERN (insn)) != ADDR_VEC 105117395Skan && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC); 10690075Sobrien 107117395Skan case CALL_INSN: 108169689Skan /* Noreturn and sibling call instructions terminate the basic blocks 109169689Skan (but only if they happen unconditionally). */ 110169689Skan if ((SIBLING_CALL_P (insn) 111169689Skan || find_reg_note (insn, REG_NORETURN, 0)) 112169689Skan && GET_CODE (PATTERN (insn)) != COND_EXEC) 113169689Skan return true; 114117395Skan /* Call insn may return to the nonlocal goto handler. */ 115117395Skan return ((nonlocal_goto_handler_labels 116117395Skan && (0 == (note = find_reg_note (insn, REG_EH_REGION, 117117395Skan NULL_RTX)) 118117395Skan || INTVAL (XEXP (note, 0)) >= 0)) 119117395Skan /* Or may trap. */ 120117395Skan || can_throw_internal (insn)); 12190075Sobrien 122117395Skan case INSN: 123169689Skan /* Treat trap instructions like noreturn calls (same provision). */ 124169689Skan if (GET_CODE (PATTERN (insn)) == TRAP_IF 125169689Skan && XEXP (PATTERN (insn), 0) == const1_rtx) 126169689Skan return true; 127169689Skan 128117395Skan return (flag_non_call_exceptions && can_throw_internal (insn)); 12990075Sobrien 130117395Skan case BARRIER: 131132718Skan /* It is nonsense to reach barrier when looking for the 132169689Skan end of basic block, but before dead code is eliminated 133169689Skan this may happen. */ 134117395Skan return false; 13590075Sobrien 136117395Skan default: 137169689Skan gcc_unreachable (); 13890075Sobrien } 13990075Sobrien} 14090075Sobrien 14190075Sobrien/* Count the basic blocks of the function. */ 14290075Sobrien 14390075Sobrienstatic int 144132718Skancount_basic_blocks (rtx f) 14590075Sobrien{ 146169689Skan int count = NUM_FIXED_BLOCKS; 14790075Sobrien bool saw_insn = false; 14890075Sobrien rtx insn; 14990075Sobrien 15090075Sobrien for (insn = f; insn; insn = NEXT_INSN (insn)) 15190075Sobrien { 152132718Skan /* Code labels and barriers causes current basic block to be 153169689Skan terminated at previous real insn. */ 154169689Skan if ((LABEL_P (insn) || BARRIER_P (insn)) 15590075Sobrien && saw_insn) 15690075Sobrien count++, saw_insn = false; 15790075Sobrien 15890075Sobrien /* Start basic block if needed. */ 15990075Sobrien if (!saw_insn && inside_basic_block_p (insn)) 16090075Sobrien saw_insn = true; 16190075Sobrien 16290075Sobrien /* Control flow insn causes current basic block to be terminated. */ 16390075Sobrien if (saw_insn && control_flow_insn_p (insn)) 16490075Sobrien count++, saw_insn = false; 16590075Sobrien } 16690075Sobrien 16790075Sobrien if (saw_insn) 16890075Sobrien count++; 16990075Sobrien 17090075Sobrien /* The rest of the compiler works a bit smoother when we don't have to 17190075Sobrien check for the edge case of do-nothing functions with no basic blocks. */ 172169689Skan if (count == NUM_FIXED_BLOCKS) 17390075Sobrien { 17490075Sobrien emit_insn (gen_rtx_USE (VOIDmode, const0_rtx)); 175169689Skan count = NUM_FIXED_BLOCKS + 1; 17690075Sobrien } 17790075Sobrien 17890075Sobrien return count; 17990075Sobrien} 18090075Sobrien 18190075Sobrien/* Create an edge between two basic blocks. FLAGS are auxiliary information 18290075Sobrien about the edge that is accumulated between calls. */ 18390075Sobrien 18490075Sobrien/* Create an edge from a basic block to a label. */ 18590075Sobrien 18690075Sobrienstatic void 187169689Skanmake_label_edge (sbitmap edge_cache, basic_block src, rtx label, int flags) 18890075Sobrien{ 189169689Skan gcc_assert (LABEL_P (label)); 19090075Sobrien 19190075Sobrien /* If the label was never emitted, this insn is junk, but avoid a 19290075Sobrien crash trying to refer to BLOCK_FOR_INSN (label). This can happen 19390075Sobrien as a result of a syntax error and a diagnostic has already been 19490075Sobrien printed. */ 19590075Sobrien 19690075Sobrien if (INSN_UID (label) == 0) 19790075Sobrien return; 19890075Sobrien 19990075Sobrien cached_make_edge (edge_cache, src, BLOCK_FOR_INSN (label), flags); 20090075Sobrien} 20190075Sobrien 20290075Sobrien/* Create the edges generated by INSN in REGION. */ 20390075Sobrien 204169689Skanvoid 205169689Skanrtl_make_eh_edge (sbitmap edge_cache, basic_block src, rtx insn) 20690075Sobrien{ 207169689Skan int is_call = CALL_P (insn) ? EDGE_ABNORMAL_CALL : 0; 20890075Sobrien rtx handlers, i; 20990075Sobrien 21090075Sobrien handlers = reachable_handlers (insn); 21190075Sobrien 21290075Sobrien for (i = handlers; i; i = XEXP (i, 1)) 21390075Sobrien make_label_edge (edge_cache, src, XEXP (i, 0), 21490075Sobrien EDGE_ABNORMAL | EDGE_EH | is_call); 21590075Sobrien 21690075Sobrien free_INSN_LIST_list (&handlers); 21790075Sobrien} 21890075Sobrien 219169689Skan/* States of basic block as seen by find_many_sub_basic_blocks. */ 220169689Skanenum state { 221169689Skan /* Basic blocks created via split_block belong to this state. 222169689Skan make_edges will examine these basic blocks to see if we need to 223169689Skan create edges going out of them. */ 224169689Skan BLOCK_NEW = 0, 22590075Sobrien 226169689Skan /* Basic blocks that do not need examining belong to this state. 227169689Skan These blocks will be left intact. In particular, make_edges will 228169689Skan not create edges going out of these basic blocks. */ 229169689Skan BLOCK_ORIGINAL, 23090075Sobrien 231169689Skan /* Basic blocks that may need splitting (due to a label appearing in 232169689Skan the middle, etc) belong to this state. After splitting them, 233169689Skan make_edges will create edges going out of them as needed. */ 234169689Skan BLOCK_TO_SPLIT 235169689Skan}; 23690075Sobrien 237169689Skan#define STATE(BB) (enum state) ((size_t) (BB)->aux) 238169689Skan#define SET_STATE(BB, STATE) ((BB)->aux = (void *) (size_t) (STATE)) 239169689Skan 240169689Skan/* Used internally by purge_dead_tablejump_edges, ORed into state. */ 241169689Skan#define BLOCK_USED_BY_TABLEJUMP 32 242169689Skan#define FULL_STATE(BB) ((size_t) (BB)->aux) 243169689Skan 244169689Skan/* Identify the edges going out of basic blocks between MIN and MAX, 245169689Skan inclusive, that have their states set to BLOCK_NEW or 246169689Skan BLOCK_TO_SPLIT. 247169689Skan 248169689Skan UPDATE_P should be nonzero if we are updating CFG and zero if we 249169689Skan are building CFG from scratch. */ 250169689Skan 25190075Sobrienstatic void 252169689Skanmake_edges (basic_block min, basic_block max, int update_p) 25390075Sobrien{ 254117395Skan basic_block bb; 255169689Skan sbitmap edge_cache = NULL; 25690075Sobrien 25790075Sobrien /* Heavy use of computed goto in machine-generated code can lead to 25890075Sobrien nearly fully-connected CFGs. In that case we spend a significant 25990075Sobrien amount of time searching the edge lists for duplicates. */ 260169689Skan if (forced_labels || cfun->max_jumptable_ents > 100) 261169689Skan edge_cache = sbitmap_alloc (last_basic_block); 26290075Sobrien 263117395Skan /* By nature of the way these get numbered, ENTRY_BLOCK_PTR->next_bb block 264117395Skan is always the entry. */ 265117395Skan if (min == ENTRY_BLOCK_PTR->next_bb) 266169689Skan make_edge (ENTRY_BLOCK_PTR, min, EDGE_FALLTHRU); 26790075Sobrien 268117395Skan FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb) 26990075Sobrien { 27090075Sobrien rtx insn, x; 27190075Sobrien enum rtx_code code; 272169689Skan edge e; 273169689Skan edge_iterator ei; 27490075Sobrien 275169689Skan if (STATE (bb) == BLOCK_ORIGINAL) 276169689Skan continue; 277169689Skan 278169689Skan /* If we have an edge cache, cache edges going out of BB. */ 279169689Skan if (edge_cache) 280169689Skan { 281169689Skan sbitmap_zero (edge_cache); 282169689Skan if (update_p) 283169689Skan { 284169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 285169689Skan if (e->dest != EXIT_BLOCK_PTR) 286169689Skan SET_BIT (edge_cache, e->dest->index); 287169689Skan } 288169689Skan } 289169689Skan 290169689Skan if (LABEL_P (BB_HEAD (bb)) 291132718Skan && LABEL_ALT_ENTRY_P (BB_HEAD (bb))) 29290075Sobrien cached_make_edge (NULL, ENTRY_BLOCK_PTR, bb, 0); 29390075Sobrien 29490075Sobrien /* Examine the last instruction of the block, and discover the 29590075Sobrien ways we can leave the block. */ 29690075Sobrien 297132718Skan insn = BB_END (bb); 29890075Sobrien code = GET_CODE (insn); 29990075Sobrien 30090075Sobrien /* A branch. */ 30190075Sobrien if (code == JUMP_INSN) 30290075Sobrien { 30390075Sobrien rtx tmp; 30490075Sobrien 30590075Sobrien /* Recognize exception handling placeholders. */ 30690075Sobrien if (GET_CODE (PATTERN (insn)) == RESX) 307169689Skan rtl_make_eh_edge (edge_cache, bb, insn); 30890075Sobrien 30990075Sobrien /* Recognize a non-local goto as a branch outside the 31090075Sobrien current function. */ 31190075Sobrien else if (find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX)) 31290075Sobrien ; 31390075Sobrien 314132718Skan /* Recognize a tablejump and do the right thing. */ 315132718Skan else if (tablejump_p (insn, NULL, &tmp)) 31690075Sobrien { 31790075Sobrien rtvec vec; 31890075Sobrien int j; 31990075Sobrien 32090075Sobrien if (GET_CODE (PATTERN (tmp)) == ADDR_VEC) 32190075Sobrien vec = XVEC (PATTERN (tmp), 0); 32290075Sobrien else 32390075Sobrien vec = XVEC (PATTERN (tmp), 1); 32490075Sobrien 32590075Sobrien for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j) 32690075Sobrien make_label_edge (edge_cache, bb, 32790075Sobrien XEXP (RTVEC_ELT (vec, j), 0), 0); 32890075Sobrien 32990075Sobrien /* Some targets (eg, ARM) emit a conditional jump that also 33090075Sobrien contains the out-of-range target. Scan for these and 33190075Sobrien add an edge if necessary. */ 33290075Sobrien if ((tmp = single_set (insn)) != NULL 33390075Sobrien && SET_DEST (tmp) == pc_rtx 33490075Sobrien && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE 33590075Sobrien && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF) 33690075Sobrien make_label_edge (edge_cache, bb, 33790075Sobrien XEXP (XEXP (SET_SRC (tmp), 2), 0), 0); 33890075Sobrien } 33990075Sobrien 34090075Sobrien /* If this is a computed jump, then mark it as reaching 341169689Skan everything on the forced_labels list. */ 34290075Sobrien else if (computed_jump_p (insn)) 34390075Sobrien { 34490075Sobrien for (x = forced_labels; x; x = XEXP (x, 1)) 34590075Sobrien make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL); 34690075Sobrien } 34790075Sobrien 34890075Sobrien /* Returns create an exit out. */ 34990075Sobrien else if (returnjump_p (insn)) 35090075Sobrien cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, 0); 35190075Sobrien 35290075Sobrien /* Otherwise, we have a plain conditional or unconditional jump. */ 35390075Sobrien else 35490075Sobrien { 355169689Skan gcc_assert (JUMP_LABEL (insn)); 35690075Sobrien make_label_edge (edge_cache, bb, JUMP_LABEL (insn), 0); 35790075Sobrien } 35890075Sobrien } 35990075Sobrien 36090075Sobrien /* If this is a sibling call insn, then this is in effect a combined call 36190075Sobrien and return, and so we need an edge to the exit block. No need to 36290075Sobrien worry about EH edges, since we wouldn't have created the sibling call 36390075Sobrien in the first place. */ 36490075Sobrien if (code == CALL_INSN && SIBLING_CALL_P (insn)) 36590075Sobrien cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, 366132718Skan EDGE_SIBCALL | EDGE_ABNORMAL); 36790075Sobrien 36890075Sobrien /* If this is a CALL_INSN, then mark it as reaching the active EH 36990075Sobrien handler for this CALL_INSN. If we're handling non-call 37090075Sobrien exceptions then any insn can reach any of the active handlers. 37190075Sobrien Also mark the CALL_INSN as reaching any nonlocal goto handler. */ 37290075Sobrien else if (code == CALL_INSN || flag_non_call_exceptions) 37390075Sobrien { 37490075Sobrien /* Add any appropriate EH edges. */ 375169689Skan rtl_make_eh_edge (edge_cache, bb, insn); 37690075Sobrien 37790075Sobrien if (code == CALL_INSN && nonlocal_goto_handler_labels) 37890075Sobrien { 37990075Sobrien /* ??? This could be made smarter: in some cases it's possible 38090075Sobrien to tell that certain calls will not do a nonlocal goto. 38190075Sobrien For example, if the nested functions that do the nonlocal 38290075Sobrien gotos do not have their addresses taken, then only calls to 38390075Sobrien those functions or to other nested functions that use them 38490075Sobrien could possibly do nonlocal gotos. */ 38590075Sobrien 38690075Sobrien /* We do know that a REG_EH_REGION note with a value less 38790075Sobrien than 0 is guaranteed not to perform a non-local goto. */ 38890075Sobrien rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX); 38990075Sobrien 39090075Sobrien if (!note || INTVAL (XEXP (note, 0)) >= 0) 39190075Sobrien for (x = nonlocal_goto_handler_labels; x; x = XEXP (x, 1)) 39290075Sobrien make_label_edge (edge_cache, bb, XEXP (x, 0), 39390075Sobrien EDGE_ABNORMAL | EDGE_ABNORMAL_CALL); 39490075Sobrien } 39590075Sobrien } 39690075Sobrien 39790075Sobrien /* Find out if we can drop through to the next block. */ 398132718Skan insn = NEXT_INSN (insn); 399169689Skan e = find_edge (bb, EXIT_BLOCK_PTR); 400169689Skan if (e && e->flags & EDGE_FALLTHRU) 401169689Skan insn = NULL; 402169689Skan 403132718Skan while (insn 404169689Skan && NOTE_P (insn) 405132718Skan && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK) 406132718Skan insn = NEXT_INSN (insn); 407132718Skan 408169689Skan if (!insn) 40990075Sobrien cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, EDGE_FALLTHRU); 410117395Skan else if (bb->next_bb != EXIT_BLOCK_PTR) 41190075Sobrien { 412169689Skan if (insn == BB_HEAD (bb->next_bb)) 413117395Skan cached_make_edge (edge_cache, bb, bb->next_bb, EDGE_FALLTHRU); 41490075Sobrien } 41590075Sobrien } 41690075Sobrien 41790075Sobrien if (edge_cache) 41890075Sobrien sbitmap_vector_free (edge_cache); 41990075Sobrien} 42090075Sobrien 42190075Sobrien/* Find all basic blocks of the function whose first insn is F. 42290075Sobrien 42390075Sobrien Collect and return a list of labels whose addresses are taken. This 42490075Sobrien will be used in make_edges for use with computed gotos. */ 42590075Sobrien 42690075Sobrienstatic void 427132718Skanfind_basic_blocks_1 (rtx f) 42890075Sobrien{ 42990075Sobrien rtx insn, next; 43090075Sobrien rtx bb_note = NULL_RTX; 43190075Sobrien rtx head = NULL_RTX; 43290075Sobrien rtx end = NULL_RTX; 433117395Skan basic_block prev = ENTRY_BLOCK_PTR; 43490075Sobrien 43590075Sobrien /* We process the instructions in a slightly different way than we did 43690075Sobrien previously. This is so that we see a NOTE_BASIC_BLOCK after we have 43790075Sobrien closed out the previous block, so that it gets attached at the proper 43890075Sobrien place. Since this form should be equivalent to the previous, 43990075Sobrien count_basic_blocks continues to use the old form as a check. */ 44090075Sobrien 44190075Sobrien for (insn = f; insn; insn = next) 44290075Sobrien { 44390075Sobrien enum rtx_code code = GET_CODE (insn); 44490075Sobrien 44590075Sobrien next = NEXT_INSN (insn); 44690075Sobrien 447169689Skan if ((LABEL_P (insn) || BARRIER_P (insn)) 44890075Sobrien && head) 44990075Sobrien { 450117395Skan prev = create_basic_block_structure (head, end, bb_note, prev); 45190075Sobrien head = end = NULL_RTX; 45290075Sobrien bb_note = NULL_RTX; 45390075Sobrien } 45490075Sobrien 45590075Sobrien if (inside_basic_block_p (insn)) 45690075Sobrien { 45790075Sobrien if (head == NULL_RTX) 45890075Sobrien head = insn; 45990075Sobrien end = insn; 46090075Sobrien } 46190075Sobrien 46290075Sobrien if (head && control_flow_insn_p (insn)) 46390075Sobrien { 464117395Skan prev = create_basic_block_structure (head, end, bb_note, prev); 46590075Sobrien head = end = NULL_RTX; 46690075Sobrien bb_note = NULL_RTX; 46790075Sobrien } 46890075Sobrien 46990075Sobrien switch (code) 47090075Sobrien { 47190075Sobrien case NOTE: 47290075Sobrien { 47390075Sobrien int kind = NOTE_LINE_NUMBER (insn); 47490075Sobrien 47590075Sobrien /* Look for basic block notes with which to keep the 47690075Sobrien basic_block_info pointers stable. Unthread the note now; 47790075Sobrien we'll put it back at the right place in create_basic_block. 47890075Sobrien Or not at all if we've already found a note in this block. */ 47990075Sobrien if (kind == NOTE_INSN_BASIC_BLOCK) 48090075Sobrien { 48190075Sobrien if (bb_note == NULL_RTX) 48290075Sobrien bb_note = insn; 48390075Sobrien else 48490075Sobrien next = delete_insn (insn); 48590075Sobrien } 48690075Sobrien break; 48790075Sobrien } 48890075Sobrien 48990075Sobrien case CODE_LABEL: 49090075Sobrien case JUMP_INSN: 491169689Skan case CALL_INSN: 49290075Sobrien case INSN: 49390075Sobrien case BARRIER: 49490075Sobrien break; 49590075Sobrien 49690075Sobrien default: 497169689Skan gcc_unreachable (); 49890075Sobrien } 49990075Sobrien } 50090075Sobrien 50190075Sobrien if (head != NULL_RTX) 502117395Skan create_basic_block_structure (head, end, bb_note, prev); 50390075Sobrien else if (bb_note) 50490075Sobrien delete_insn (bb_note); 50590075Sobrien 506169689Skan gcc_assert (last_basic_block == n_basic_blocks); 50790075Sobrien 508117395Skan clear_aux_for_blocks (); 50990075Sobrien} 51090075Sobrien 51190075Sobrien 51290075Sobrien/* Find basic blocks of the current function. 513169689Skan F is the first insn of the function. */ 51490075Sobrien 51590075Sobrienvoid 516169689Skanfind_basic_blocks (rtx f) 51790075Sobrien{ 518117395Skan basic_block bb; 519117395Skan 52090075Sobrien timevar_push (TV_CFG); 52190075Sobrien 52290075Sobrien /* Flush out existing data. */ 52390075Sobrien if (basic_block_info != NULL) 52490075Sobrien { 52590075Sobrien clear_edges (); 52690075Sobrien 52790075Sobrien /* Clear bb->aux on all extant basic blocks. We'll use this as a 52890075Sobrien tag for reuse during create_basic_block, just in case some pass 52990075Sobrien copies around basic block notes improperly. */ 530117395Skan FOR_EACH_BB (bb) 531132718Skan bb->aux = NULL; 53290075Sobrien 533169689Skan basic_block_info = NULL; 53490075Sobrien } 53590075Sobrien 53690075Sobrien n_basic_blocks = count_basic_blocks (f); 537169689Skan last_basic_block = NUM_FIXED_BLOCKS; 538117395Skan ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR; 539117395Skan EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR; 54090075Sobrien 541169689Skan 54290075Sobrien /* Size the basic block table. The actual structures will be allocated 54390075Sobrien by find_basic_blocks_1, since we want to keep the structure pointers 54490075Sobrien stable across calls to find_basic_blocks. */ 54590075Sobrien /* ??? This whole issue would be much simpler if we called find_basic_blocks 54690075Sobrien exactly once, and thereafter we don't have a single long chain of 54790075Sobrien instructions at all until close to the end of compilation when we 54890075Sobrien actually lay them out. */ 54990075Sobrien 550169689Skan basic_block_info = VEC_alloc (basic_block, gc, n_basic_blocks); 551169689Skan VEC_safe_grow (basic_block, gc, basic_block_info, n_basic_blocks); 552169689Skan memset (VEC_address (basic_block, basic_block_info), 0, 553169689Skan sizeof (basic_block) * n_basic_blocks); 554169689Skan SET_BASIC_BLOCK (ENTRY_BLOCK, ENTRY_BLOCK_PTR); 555169689Skan SET_BASIC_BLOCK (EXIT_BLOCK, EXIT_BLOCK_PTR); 55690075Sobrien 55790075Sobrien find_basic_blocks_1 (f); 55890075Sobrien 559169689Skan profile_status = PROFILE_ABSENT; 560169689Skan 561169689Skan /* Tell make_edges to examine every block for out-going edges. */ 562169689Skan FOR_EACH_BB (bb) 563169689Skan SET_STATE (bb, BLOCK_NEW); 564169689Skan 56590075Sobrien /* Discover the edges of our cfg. */ 566169689Skan make_edges (ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, 0); 56790075Sobrien 56890075Sobrien /* Do very simple cleanup now, for the benefit of code that runs between 56990075Sobrien here and cleanup_cfg, e.g. thread_prologue_and_epilogue_insns. */ 57090075Sobrien tidy_fallthru_edges (); 57190075Sobrien 57290075Sobrien#ifdef ENABLE_CHECKING 57390075Sobrien verify_flow_info (); 57490075Sobrien#endif 57590075Sobrien timevar_pop (TV_CFG); 57690075Sobrien} 57790075Sobrien 578169689Skanstatic void 579169689Skanmark_tablejump_edge (rtx label) 580169689Skan{ 581169689Skan basic_block bb; 58290075Sobrien 583169689Skan gcc_assert (LABEL_P (label)); 584169689Skan /* See comment in make_label_edge. */ 585169689Skan if (INSN_UID (label) == 0) 586169689Skan return; 587169689Skan bb = BLOCK_FOR_INSN (label); 588169689Skan SET_STATE (bb, FULL_STATE (bb) | BLOCK_USED_BY_TABLEJUMP); 589169689Skan} 59090075Sobrien 591169689Skanstatic void 592169689Skanpurge_dead_tablejump_edges (basic_block bb, rtx table) 593169689Skan{ 594169689Skan rtx insn = BB_END (bb), tmp; 595169689Skan rtvec vec; 596169689Skan int j; 597169689Skan edge_iterator ei; 598169689Skan edge e; 599169689Skan 600169689Skan if (GET_CODE (PATTERN (table)) == ADDR_VEC) 601169689Skan vec = XVEC (PATTERN (table), 0); 602169689Skan else 603169689Skan vec = XVEC (PATTERN (table), 1); 604169689Skan 605169689Skan for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j) 606169689Skan mark_tablejump_edge (XEXP (RTVEC_ELT (vec, j), 0)); 607169689Skan 608169689Skan /* Some targets (eg, ARM) emit a conditional jump that also 609169689Skan contains the out-of-range target. Scan for these and 610169689Skan add an edge if necessary. */ 611169689Skan if ((tmp = single_set (insn)) != NULL 612169689Skan && SET_DEST (tmp) == pc_rtx 613169689Skan && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE 614169689Skan && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF) 615169689Skan mark_tablejump_edge (XEXP (XEXP (SET_SRC (tmp), 2), 0)); 616169689Skan 617169689Skan for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) 618169689Skan { 619169689Skan if (FULL_STATE (e->dest) & BLOCK_USED_BY_TABLEJUMP) 620169689Skan SET_STATE (e->dest, FULL_STATE (e->dest) 621169689Skan & ~(size_t) BLOCK_USED_BY_TABLEJUMP); 622169689Skan else if (!(e->flags & (EDGE_ABNORMAL | EDGE_EH))) 623169689Skan { 624169689Skan remove_edge (e); 625169689Skan continue; 626169689Skan } 627169689Skan ei_next (&ei); 628169689Skan } 629169689Skan} 630169689Skan 63190075Sobrien/* Scan basic block BB for possible BB boundaries inside the block 63290075Sobrien and create new basic blocks in the progress. */ 63390075Sobrien 63490075Sobrienstatic void 635132718Skanfind_bb_boundaries (basic_block bb) 63690075Sobrien{ 637169689Skan basic_block orig_bb = bb; 638132718Skan rtx insn = BB_HEAD (bb); 639132718Skan rtx end = BB_END (bb); 640169689Skan rtx table; 64190075Sobrien rtx flow_transfer_insn = NULL_RTX; 64290075Sobrien edge fallthru = NULL; 64390075Sobrien 644132718Skan if (insn == BB_END (bb)) 64590075Sobrien return; 64690075Sobrien 647169689Skan if (LABEL_P (insn)) 64890075Sobrien insn = NEXT_INSN (insn); 64990075Sobrien 65090075Sobrien /* Scan insn chain and try to find new basic block boundaries. */ 65190075Sobrien while (1) 65290075Sobrien { 65390075Sobrien enum rtx_code code = GET_CODE (insn); 65490075Sobrien 65590075Sobrien /* On code label, split current basic block. */ 65690075Sobrien if (code == CODE_LABEL) 65790075Sobrien { 65890075Sobrien fallthru = split_block (bb, PREV_INSN (insn)); 65990075Sobrien if (flow_transfer_insn) 660132718Skan BB_END (bb) = flow_transfer_insn; 66190075Sobrien 66290075Sobrien bb = fallthru->dest; 66390075Sobrien remove_edge (fallthru); 66490075Sobrien flow_transfer_insn = NULL_RTX; 665117395Skan if (LABEL_ALT_ENTRY_P (insn)) 66690075Sobrien make_edge (ENTRY_BLOCK_PTR, bb, 0); 66790075Sobrien } 66890075Sobrien 66990075Sobrien /* In case we've previously seen an insn that effects a control 67090075Sobrien flow transfer, split the block. */ 67190075Sobrien if (flow_transfer_insn && inside_basic_block_p (insn)) 67290075Sobrien { 67390075Sobrien fallthru = split_block (bb, PREV_INSN (insn)); 674132718Skan BB_END (bb) = flow_transfer_insn; 67590075Sobrien bb = fallthru->dest; 67690075Sobrien remove_edge (fallthru); 67790075Sobrien flow_transfer_insn = NULL_RTX; 67890075Sobrien } 67990075Sobrien 68090075Sobrien if (control_flow_insn_p (insn)) 68190075Sobrien flow_transfer_insn = insn; 68290075Sobrien if (insn == end) 68390075Sobrien break; 68490075Sobrien insn = NEXT_INSN (insn); 68590075Sobrien } 68690075Sobrien 68790075Sobrien /* In case expander replaced normal insn by sequence terminating by 68890075Sobrien return and barrier, or possibly other sequence not behaving like 68990075Sobrien ordinary jump, we need to take care and move basic block boundary. */ 69090075Sobrien if (flow_transfer_insn) 691132718Skan BB_END (bb) = flow_transfer_insn; 69290075Sobrien 69390075Sobrien /* We've possibly replaced the conditional jump by conditional jump 69490075Sobrien followed by cleanup at fallthru edge, so the outgoing edges may 69590075Sobrien be dead. */ 69690075Sobrien purge_dead_edges (bb); 697169689Skan 698169689Skan /* purge_dead_edges doesn't handle tablejump's, but if we have split the 699169689Skan basic block, we might need to kill some edges. */ 700169689Skan if (bb != orig_bb && tablejump_p (BB_END (bb), NULL, &table)) 701169689Skan purge_dead_tablejump_edges (bb, table); 70290075Sobrien} 70390075Sobrien 70490075Sobrien/* Assume that frequency of basic block B is known. Compute frequencies 70590075Sobrien and probabilities of outgoing edges. */ 70690075Sobrien 70790075Sobrienstatic void 708132718Skancompute_outgoing_frequencies (basic_block b) 70990075Sobrien{ 71090075Sobrien edge e, f; 711169689Skan edge_iterator ei; 71290075Sobrien 713169689Skan if (EDGE_COUNT (b->succs) == 2) 71490075Sobrien { 715132718Skan rtx note = find_reg_note (BB_END (b), REG_BR_PROB, NULL); 71690075Sobrien int probability; 71790075Sobrien 718169689Skan if (note) 719169689Skan { 720169689Skan probability = INTVAL (XEXP (note, 0)); 721169689Skan e = BRANCH_EDGE (b); 722169689Skan e->probability = probability; 723169689Skan e->count = ((b->count * probability + REG_BR_PROB_BASE / 2) 724169689Skan / REG_BR_PROB_BASE); 725169689Skan f = FALLTHRU_EDGE (b); 726169689Skan f->probability = REG_BR_PROB_BASE - probability; 727169689Skan f->count = b->count - e->count; 728169689Skan return; 729169689Skan } 73090075Sobrien } 73190075Sobrien 732169689Skan if (single_succ_p (b)) 73390075Sobrien { 734169689Skan e = single_succ_edge (b); 73590075Sobrien e->probability = REG_BR_PROB_BASE; 73690075Sobrien e->count = b->count; 737169689Skan return; 73890075Sobrien } 739169689Skan guess_outgoing_edge_probabilities (b); 740169689Skan if (b->count) 741169689Skan FOR_EACH_EDGE (e, ei, b->succs) 742169689Skan e->count = ((b->count * e->probability + REG_BR_PROB_BASE / 2) 743169689Skan / REG_BR_PROB_BASE); 74490075Sobrien} 74590075Sobrien 746169689Skan/* Assume that some pass has inserted labels or control flow 747169689Skan instructions within a basic block. Split basic blocks as needed 748169689Skan and create edges. */ 74990075Sobrien 75090075Sobrienvoid 751132718Skanfind_many_sub_basic_blocks (sbitmap blocks) 75290075Sobrien{ 753117395Skan basic_block bb, min, max; 75490075Sobrien 755117395Skan FOR_EACH_BB (bb) 756117395Skan SET_STATE (bb, 757117395Skan TEST_BIT (blocks, bb->index) ? BLOCK_TO_SPLIT : BLOCK_ORIGINAL); 75890075Sobrien 759117395Skan FOR_EACH_BB (bb) 760117395Skan if (STATE (bb) == BLOCK_TO_SPLIT) 761117395Skan find_bb_boundaries (bb); 76290075Sobrien 763117395Skan FOR_EACH_BB (bb) 764117395Skan if (STATE (bb) != BLOCK_ORIGINAL) 76590075Sobrien break; 76690075Sobrien 767117395Skan min = max = bb; 768117395Skan for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb) 769117395Skan if (STATE (bb) != BLOCK_ORIGINAL) 770117395Skan max = bb; 77190075Sobrien 77290075Sobrien /* Now re-scan and wire in all edges. This expect simple (conditional) 77390075Sobrien jumps at the end of each new basic blocks. */ 774169689Skan make_edges (min, max, 1); 77590075Sobrien 77690075Sobrien /* Update branch probabilities. Expect only (un)conditional jumps 77790075Sobrien to be created with only the forward edges. */ 778169689Skan if (profile_status != PROFILE_ABSENT) 779169689Skan FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb) 780169689Skan { 781169689Skan edge e; 782169689Skan edge_iterator ei; 78390075Sobrien 784169689Skan if (STATE (bb) == BLOCK_ORIGINAL) 785169689Skan continue; 786169689Skan if (STATE (bb) == BLOCK_NEW) 787169689Skan { 788169689Skan bb->count = 0; 789169689Skan bb->frequency = 0; 790169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 791169689Skan { 792169689Skan bb->count += e->count; 793169689Skan bb->frequency += EDGE_FREQUENCY (e); 794169689Skan } 795169689Skan } 79690075Sobrien 797169689Skan compute_outgoing_frequencies (bb); 798169689Skan } 79990075Sobrien 800117395Skan FOR_EACH_BB (bb) 801117395Skan SET_STATE (bb, 0); 80290075Sobrien} 803