#include "config.h"
#include "system.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 PARAMS ((rtx));
static void find_basic_blocks_1 PARAMS ((rtx));
static rtx find_label_refs PARAMS ((rtx, rtx));
static void make_edges PARAMS ((rtx, basic_block,
basic_block, int));
static void make_label_edge PARAMS ((sbitmap *, basic_block,
rtx, int));
static void make_eh_edge PARAMS ((sbitmap *, basic_block, rtx));
static void find_bb_boundaries PARAMS ((basic_block));
static void compute_outgoing_frequencies PARAMS ((basic_block));
static bool inside_basic_block_p PARAMS ((rtx));
static bool
inside_basic_block_p (insn)
rtx insn;
{
switch (GET_CODE (insn))
{
case CODE_LABEL:
return (NEXT_INSN (insn) == 0
|| GET_CODE (NEXT_INSN (insn)) != JUMP_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:
abort ();
}
}
bool
control_flow_insn_p (insn)
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:
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:
abort ();
}
}
static int
count_basic_blocks (f)
rtx f;
{
int count = 0;
bool saw_insn = false;
rtx insn;
for (insn = f; insn; insn = NEXT_INSN (insn))
{
if ((GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == BARRIER)
&& 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 rtx
find_label_refs (f, lvl)
rtx f;
rtx lvl;
{
rtx insn;
for (insn = f; insn; insn = NEXT_INSN (insn))
if (INSN_P (insn) && GET_CODE (insn) != JUMP_INSN)
{
rtx note;
for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
if (REG_NOTE_KIND (note) == REG_LABEL)
{
rtx lab = XEXP (note, 0), next;
if ((next = next_nonnote_insn (lab)) != NULL
&& GET_CODE (next) == JUMP_INSN
&& (GET_CODE (PATTERN (next)) == ADDR_VEC
|| GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
;
else if (GET_CODE (lab) == NOTE)
;
else if (GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
&& find_reg_note (NEXT_INSN (insn), REG_LABEL, lab))
;
else
lvl = alloc_EXPR_LIST (0, XEXP (note, 0), lvl);
}
}
return lvl;
}
static void
make_label_edge (edge_cache, src, label, flags)
sbitmap *edge_cache;
basic_block src;
rtx label;
int flags;
{
if (GET_CODE (label) != CODE_LABEL)
abort ();
if (INSN_UID (label) == 0)
return;
cached_make_edge (edge_cache, src, BLOCK_FOR_INSN (label), flags);
}
static void
make_eh_edge (edge_cache, src, insn)
sbitmap *edge_cache;
basic_block src;
rtx insn;
{
int is_call = GET_CODE (insn) == CALL_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 (label_value_list, min, max, update_p)
rtx label_value_list;
basic_block min, max;
int update_p;
{
basic_block bb;
sbitmap *edge_cache = NULL;
current_function_has_computed_jump = 0;
if (forced_labels || label_value_list || 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;
for (e = bb->succ; e ; e = e->succ_next)
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;
int force_fallthru = 0;
if (GET_CODE (bb->head) == CODE_LABEL && LABEL_ALT_ENTRY_P (bb->head))
cached_make_edge (NULL, ENTRY_BLOCK_PTR, bb, 0);
insn = bb->end;
code = GET_CODE (insn);
if (code == JUMP_INSN)
{
rtx tmp;
if (GET_CODE (PATTERN (insn)) == RESX)
make_eh_edge (edge_cache, bb, insn);
else if (find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
;
else if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
&& (tmp = NEXT_INSN (tmp)) != NULL_RTX
&& GET_CODE (tmp) == JUMP_INSN
&& (GET_CODE (PATTERN (tmp)) == ADDR_VEC
|| GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
{
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);
#ifdef CASE_DROPS_THROUGH
force_fallthru = 1;
#endif
}
else if (computed_jump_p (insn))
{
current_function_has_computed_jump = 1;
for (x = label_value_list; x; x = XEXP (x, 1))
make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL);
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
{
if (! JUMP_LABEL (insn))
abort ();
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_ABNORMAL | EDGE_ABNORMAL_CALL);
else if (code == CALL_INSN || flag_non_call_exceptions)
{
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_nonnote_insn (insn);
if (!insn || (bb->next_bb == EXIT_BLOCK_PTR && force_fallthru))
cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
else if (bb->next_bb != EXIT_BLOCK_PTR)
{
rtx tmp = bb->next_bb->head;
if (GET_CODE (tmp) == NOTE)
tmp = next_nonnote_insn (tmp);
if (force_fallthru || insn == tmp)
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 (f)
rtx f;
{
rtx insn, next;
rtx bb_note = NULL_RTX;
rtx lvl = NULL_RTX;
rtx trll = 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 ((GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == BARRIER)
&& 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 INSN:
case BARRIER:
break;
case CALL_INSN:
if (GET_CODE (PATTERN (insn)) == CALL_PLACEHOLDER)
{
lvl = find_label_refs (XEXP (PATTERN (insn), 0), lvl);
lvl = find_label_refs (XEXP (PATTERN (insn), 1), lvl);
lvl = find_label_refs (XEXP (PATTERN (insn), 2), lvl);
if (XEXP (PATTERN (insn), 3) != NULL_RTX)
trll = alloc_EXPR_LIST (0, XEXP (PATTERN (insn), 3), trll);
}
break;
default:
abort ();
}
if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
{
rtx note;
for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
if (REG_NOTE_KIND (note) == REG_LABEL)
{
rtx lab = XEXP (note, 0), next;
if ((next = next_nonnote_insn (lab)) != NULL
&& GET_CODE (next) == JUMP_INSN
&& (GET_CODE (PATTERN (next)) == ADDR_VEC
|| GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
;
else if (GET_CODE (lab) == NOTE)
;
else if (GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
&& find_reg_note (NEXT_INSN (insn), REG_LABEL, lab))
;
else
lvl = alloc_EXPR_LIST (0, XEXP (note, 0), lvl);
}
}
}
if (head != NULL_RTX)
create_basic_block_structure (head, end, bb_note, prev);
else if (bb_note)
delete_insn (bb_note);
if (last_basic_block != n_basic_blocks)
abort ();
label_value_list = lvl;
tail_recursion_label_list = trll;
clear_aux_for_blocks ();
}
void
find_basic_blocks (f, nregs, file)
rtx f;
int nregs ATTRIBUTE_UNUSED;
FILE *file ATTRIBUTE_UNUSED;
{
basic_block bb;
timevar_push (TV_CFG);
if (basic_block_info != NULL)
{
clear_edges ();
FOR_EACH_BB (bb)
bb->aux = NULL;
VARRAY_FREE (basic_block_info);
}
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);
make_edges (label_value_list, 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))
static void
find_bb_boundaries (bb)
basic_block bb;
{
rtx insn = bb->head;
rtx end = bb->end;
rtx flow_transfer_insn = NULL_RTX;
edge fallthru = NULL;
if (insn == bb->end)
return;
if (GET_CODE (insn) == CODE_LABEL)
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 = 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 = 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 = flow_transfer_insn;
purge_dead_edges (bb);
}
static void
compute_outgoing_frequencies (b)
basic_block b;
{
edge e, f;
if (b->succ && b->succ->succ_next && !b->succ->succ_next->succ_next)
{
rtx note = find_reg_note (b->end, REG_BR_PROB, NULL);
int probability;
if (!note)
return;
probability = INTVAL (XEXP (find_reg_note (b->end,
REG_BR_PROB, NULL),
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;
}
if (b->succ && !b->succ->succ_next)
{
e = b->succ;
e->probability = REG_BR_PROB_BASE;
e->count = b->count;
}
}
void
find_many_sub_basic_blocks (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 (NULL, min, max, 1);
FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
{
edge e;
if (STATE (bb) == BLOCK_ORIGINAL)
continue;
if (STATE (bb) == BLOCK_NEW)
{
bb->count = 0;
bb->frequency = 0;
for (e = bb->pred; e; e=e->pred_next)
{
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 (bb)
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 (NULL, min, max, 1);
FOR_BB_BETWEEN (b, min, max->next_bb, next_bb)
{
edge e;
if (b != min)
{
b->count = 0;
b->frequency = 0;
for (e = b->pred; e; e=e->pred_next)
{
b->count += e->count;
b->frequency += EDGE_FREQUENCY (e);
}
}
compute_outgoing_frequencies (b);
}
}