#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "regs.h"
#include "flags.h"
#include "output.h"
#include "function.h"
#include "except.h"
#include "toplev.h"
#include "timevar.h"
static int count_basic_blocks (rtx);
static void find_basic_blocks_1 (rtx);
static void make_edges (basic_block, basic_block, int);
static void make_label_edge (sbitmap *, basic_block, rtx, int);
static void find_bb_boundaries (basic_block);
static void compute_outgoing_frequencies (basic_block);
bool
inside_basic_block_p (rtx insn)
{
switch (GET_CODE (insn))
{
case CODE_LABEL:
return (NEXT_INSN (insn) == 0
|| !JUMP_P (NEXT_INSN (insn))
|| (GET_CODE (PATTERN (NEXT_INSN (insn))) != ADDR_VEC
&& GET_CODE (PATTERN (NEXT_INSN (insn))) != ADDR_DIFF_VEC));
case JUMP_INSN:
return (GET_CODE (PATTERN (insn)) != ADDR_VEC
&& GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC);
case CALL_INSN:
case INSN:
return true;
case BARRIER:
case NOTE:
return false;
default:
gcc_unreachable ();
}
}
bool
control_flow_insn_p (rtx insn)
{
rtx note;
switch (GET_CODE (insn))
{
case NOTE:
case CODE_LABEL:
return false;
case JUMP_INSN:
return (GET_CODE (PATTERN (insn)) != ADDR_VEC
&& GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC);
case CALL_INSN:
if ((SIBLING_CALL_P (insn)
|| find_reg_note (insn, REG_NORETURN, 0))
&& GET_CODE (PATTERN (insn)) != COND_EXEC)
return true;
return ((nonlocal_goto_handler_labels
&& (0 == (note = find_reg_note (insn, REG_EH_REGION,
NULL_RTX))
|| INTVAL (XEXP (note, 0)) >= 0))
|| can_throw_internal (insn));
case INSN:
return (flag_non_call_exceptions && can_throw_internal (insn));
case BARRIER:
return false;
default:
gcc_unreachable ();
}
}
static int
count_basic_blocks (rtx f)
{
int count = 0;
bool saw_insn = false;
rtx insn;
for (insn = f; insn; insn = NEXT_INSN (insn))
{
if ((LABEL_P (insn) || BARRIER_P (insn))
&& saw_insn)
count++, saw_insn = false;
if (!saw_insn && inside_basic_block_p (insn))
saw_insn = true;
if (saw_insn && control_flow_insn_p (insn))
count++, saw_insn = false;
}
if (saw_insn)
count++;
if (count == 0)
{
emit_insn (gen_rtx_USE (VOIDmode, const0_rtx));
count = 1;
}
return count;
}
static void
make_label_edge (sbitmap *edge_cache, basic_block src, rtx label, int flags)
{
gcc_assert (LABEL_P (label));
if (INSN_UID (label) == 0)
return;
cached_make_edge (edge_cache, src, BLOCK_FOR_INSN (label), flags);
}
void
rtl_make_eh_edge (sbitmap *edge_cache, basic_block src, rtx insn)
{
int is_call = CALL_P (insn) ? EDGE_ABNORMAL_CALL : 0;
rtx handlers, i;
handlers = reachable_handlers (insn);
for (i = handlers; i; i = XEXP (i, 1))
make_label_edge (edge_cache, src, XEXP (i, 0),
EDGE_ABNORMAL | EDGE_EH | is_call);
free_INSN_LIST_list (&handlers);
}
static void
make_edges (basic_block min, basic_block max, int update_p)
{
basic_block bb;
sbitmap *edge_cache = NULL;
if (forced_labels || cfun->max_jumptable_ents > 100)
{
edge_cache = sbitmap_vector_alloc (last_basic_block, last_basic_block);
sbitmap_vector_zero (edge_cache, last_basic_block);
if (update_p)
FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
{
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
if (e->dest != EXIT_BLOCK_PTR)
SET_BIT (edge_cache[bb->index], e->dest->index);
}
}
if (min == ENTRY_BLOCK_PTR->next_bb)
cached_make_edge (edge_cache, ENTRY_BLOCK_PTR, min,
EDGE_FALLTHRU);
FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
{
rtx insn, x;
enum rtx_code code;
edge e;
if (LABEL_P (BB_HEAD (bb))
&& LABEL_ALT_ENTRY_P (BB_HEAD (bb)))
cached_make_edge (NULL, ENTRY_BLOCK_PTR, bb, 0);
insn = BB_END (bb);
code = GET_CODE (insn);
if (code == JUMP_INSN)
{
rtx tmp;
if (GET_CODE (PATTERN (insn)) == RESX)
rtl_make_eh_edge (edge_cache, bb, insn);
else if (find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
;
else if (tablejump_p (insn, NULL, &tmp))
{
rtvec vec;
int j;
if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
vec = XVEC (PATTERN (tmp), 0);
else
vec = XVEC (PATTERN (tmp), 1);
for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
make_label_edge (edge_cache, bb,
XEXP (RTVEC_ELT (vec, j), 0), 0);
if ((tmp = single_set (insn)) != NULL
&& SET_DEST (tmp) == pc_rtx
&& GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
&& GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF)
make_label_edge (edge_cache, bb,
XEXP (XEXP (SET_SRC (tmp), 2), 0), 0);
}
else if (computed_jump_p (insn))
{
for (x = forced_labels; x; x = XEXP (x, 1))
make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL);
}
else if (returnjump_p (insn))
cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, 0);
else
{
gcc_assert (JUMP_LABEL (insn));
make_label_edge (edge_cache, bb, JUMP_LABEL (insn), 0);
}
}
if (code == CALL_INSN && SIBLING_CALL_P (insn))
cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR,
EDGE_SIBCALL | EDGE_ABNORMAL);
else if (code == CALL_INSN || flag_non_call_exceptions)
{
rtl_make_eh_edge (edge_cache, bb, insn);
if (code == CALL_INSN && nonlocal_goto_handler_labels)
{
rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
if (!note || INTVAL (XEXP (note, 0)) >= 0)
for (x = nonlocal_goto_handler_labels; x; x = XEXP (x, 1))
make_label_edge (edge_cache, bb, XEXP (x, 0),
EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
}
}
insn = NEXT_INSN (insn);
e = find_edge (bb, EXIT_BLOCK_PTR);
if (e && e->flags & EDGE_FALLTHRU)
insn = NULL;
while (insn
&& NOTE_P (insn)
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK)
insn = NEXT_INSN (insn);
if (!insn)
cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
else if (bb->next_bb != EXIT_BLOCK_PTR)
{
if (insn == BB_HEAD (bb->next_bb))
cached_make_edge (edge_cache, bb, bb->next_bb, EDGE_FALLTHRU);
}
}
if (edge_cache)
sbitmap_vector_free (edge_cache);
}
static void
find_basic_blocks_1 (rtx f)
{
rtx insn, next;
rtx bb_note = NULL_RTX;
rtx head = NULL_RTX;
rtx end = NULL_RTX;
basic_block prev = ENTRY_BLOCK_PTR;
for (insn = f; insn; insn = next)
{
enum rtx_code code = GET_CODE (insn);
next = NEXT_INSN (insn);
if ((LABEL_P (insn) || BARRIER_P (insn))
&& head)
{
prev = create_basic_block_structure (head, end, bb_note, prev);
head = end = NULL_RTX;
bb_note = NULL_RTX;
}
if (inside_basic_block_p (insn))
{
if (head == NULL_RTX)
head = insn;
end = insn;
}
if (head && control_flow_insn_p (insn))
{
prev = create_basic_block_structure (head, end, bb_note, prev);
head = end = NULL_RTX;
bb_note = NULL_RTX;
}
switch (code)
{
case NOTE:
{
int kind = NOTE_LINE_NUMBER (insn);
if (kind == NOTE_INSN_BASIC_BLOCK)
{
if (bb_note == NULL_RTX)
bb_note = insn;
else
next = delete_insn (insn);
}
break;
}
case CODE_LABEL:
case JUMP_INSN:
case CALL_INSN:
case INSN:
case BARRIER:
break;
default:
gcc_unreachable ();
}
}
if (head != NULL_RTX)
create_basic_block_structure (head, end, bb_note, prev);
else if (bb_note)
delete_insn (bb_note);
gcc_assert (last_basic_block == n_basic_blocks);
clear_aux_for_blocks ();
}
void
find_basic_blocks (rtx f)
{
basic_block bb;
timevar_push (TV_CFG);
if (basic_block_info != NULL)
{
clear_edges ();
FOR_EACH_BB (bb)
bb->aux = NULL;
basic_block_info = NULL;
}
n_basic_blocks = count_basic_blocks (f);
last_basic_block = 0;
ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
VARRAY_BB_INIT (basic_block_info, n_basic_blocks, "basic_block_info");
find_basic_blocks_1 (f);
profile_status = PROFILE_ABSENT;
make_edges (ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, 0);
tidy_fallthru_edges ();
#ifdef ENABLE_CHECKING
verify_flow_info ();
#endif
timevar_pop (TV_CFG);
}
enum state {BLOCK_NEW = 0, BLOCK_ORIGINAL, BLOCK_TO_SPLIT};
#define STATE(BB) (enum state) ((size_t) (BB)->aux)
#define SET_STATE(BB, STATE) ((BB)->aux = (void *) (size_t) (STATE))
#define BLOCK_USED_BY_TABLEJUMP 32
#define FULL_STATE(BB) ((size_t) (BB)->aux)
static void
mark_tablejump_edge (rtx label)
{
basic_block bb;
gcc_assert (LABEL_P (label));
if (INSN_UID (label) == 0)
return;
bb = BLOCK_FOR_INSN (label);
SET_STATE (bb, FULL_STATE (bb) | BLOCK_USED_BY_TABLEJUMP);
}
static void
purge_dead_tablejump_edges (basic_block bb, rtx table)
{
rtx insn = BB_END (bb), tmp;
rtvec vec;
int j;
edge_iterator ei;
edge e;
if (GET_CODE (PATTERN (table)) == ADDR_VEC)
vec = XVEC (PATTERN (table), 0);
else
vec = XVEC (PATTERN (table), 1);
for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
mark_tablejump_edge (XEXP (RTVEC_ELT (vec, j), 0));
if ((tmp = single_set (insn)) != NULL
&& SET_DEST (tmp) == pc_rtx
&& GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
&& GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF)
mark_tablejump_edge (XEXP (XEXP (SET_SRC (tmp), 2), 0));
for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
{
if (FULL_STATE (e->dest) & BLOCK_USED_BY_TABLEJUMP)
SET_STATE (e->dest, FULL_STATE (e->dest)
& ~(size_t) BLOCK_USED_BY_TABLEJUMP);
else if (!(e->flags & (EDGE_ABNORMAL | EDGE_EH)))
{
remove_edge (e);
continue;
}
ei_next (&ei);
}
}
static void
find_bb_boundaries (basic_block bb)
{
basic_block orig_bb = bb;
rtx insn = BB_HEAD (bb);
rtx end = BB_END (bb);
rtx table;
rtx flow_transfer_insn = NULL_RTX;
edge fallthru = NULL;
if (insn == BB_END (bb))
return;
if (LABEL_P (insn))
insn = NEXT_INSN (insn);
while (1)
{
enum rtx_code code = GET_CODE (insn);
if (code == CODE_LABEL)
{
fallthru = split_block (bb, PREV_INSN (insn));
if (flow_transfer_insn)
BB_END (bb) = flow_transfer_insn;
bb = fallthru->dest;
remove_edge (fallthru);
flow_transfer_insn = NULL_RTX;
if (LABEL_ALT_ENTRY_P (insn))
make_edge (ENTRY_BLOCK_PTR, bb, 0);
}
if (flow_transfer_insn && inside_basic_block_p (insn))
{
fallthru = split_block (bb, PREV_INSN (insn));
BB_END (bb) = flow_transfer_insn;
bb = fallthru->dest;
remove_edge (fallthru);
flow_transfer_insn = NULL_RTX;
}
if (control_flow_insn_p (insn))
flow_transfer_insn = insn;
if (insn == end)
break;
insn = NEXT_INSN (insn);
}
if (flow_transfer_insn)
BB_END (bb) = flow_transfer_insn;
purge_dead_edges (bb);
if (bb != orig_bb && tablejump_p (BB_END (bb), NULL, &table))
purge_dead_tablejump_edges (bb, table);
}
static void
compute_outgoing_frequencies (basic_block b)
{
edge e, f;
edge_iterator ei;
if (EDGE_COUNT (b->succs) == 2)
{
rtx note = find_reg_note (BB_END (b), REG_BR_PROB, NULL);
int probability;
if (note)
{
probability = INTVAL (XEXP (note, 0));
e = BRANCH_EDGE (b);
e->probability = probability;
e->count = ((b->count * probability + REG_BR_PROB_BASE / 2)
/ REG_BR_PROB_BASE);
f = FALLTHRU_EDGE (b);
f->probability = REG_BR_PROB_BASE - probability;
f->count = b->count - e->count;
return;
}
}
if (EDGE_COUNT (b->succs) == 1)
{
e = EDGE_SUCC (b, 0);
e->probability = REG_BR_PROB_BASE;
e->count = b->count;
return;
}
guess_outgoing_edge_probabilities (b);
if (b->count)
FOR_EACH_EDGE (e, ei, b->succs)
e->count = ((b->count * e->probability + REG_BR_PROB_BASE / 2)
/ REG_BR_PROB_BASE);
}
void
find_many_sub_basic_blocks (sbitmap blocks)
{
basic_block bb, min, max;
FOR_EACH_BB (bb)
SET_STATE (bb,
TEST_BIT (blocks, bb->index) ? BLOCK_TO_SPLIT : BLOCK_ORIGINAL);
FOR_EACH_BB (bb)
if (STATE (bb) == BLOCK_TO_SPLIT)
find_bb_boundaries (bb);
FOR_EACH_BB (bb)
if (STATE (bb) != BLOCK_ORIGINAL)
break;
min = max = bb;
for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb)
if (STATE (bb) != BLOCK_ORIGINAL)
max = bb;
make_edges (min, max, 1);
if (profile_status != PROFILE_ABSENT)
FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
{
edge e;
edge_iterator ei;
if (STATE (bb) == BLOCK_ORIGINAL)
continue;
if (STATE (bb) == BLOCK_NEW)
{
bb->count = 0;
bb->frequency = 0;
FOR_EACH_EDGE (e, ei, bb->preds)
{
bb->count += e->count;
bb->frequency += EDGE_FREQUENCY (e);
}
}
compute_outgoing_frequencies (bb);
}
FOR_EACH_BB (bb)
SET_STATE (bb, 0);
}
void
find_sub_basic_blocks (basic_block bb)
{
basic_block min, max, b;
basic_block next = bb->next_bb;
min = bb;
find_bb_boundaries (bb);
max = next->prev_bb;
make_edges (min, max, 1);
FOR_BB_BETWEEN (b, min, max->next_bb, next_bb)
{
edge e;
edge_iterator ei;
if (b != min)
{
b->count = 0;
b->frequency = 0;
FOR_EACH_EDGE (e, ei, b->preds)
{
b->count += e->count;
b->frequency += EDGE_FREQUENCY (e);
}
}
compute_outgoing_frequencies (b);
}
}