Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
1999, 2000, 2001 Free Software Foundation, Inc.
-This file is part of GNU CC.
+This file is part of GCC.
-GNU CC is free software; you can redistribute it and/or modify
-it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 2, or (at your option)
-any later version.
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 2, or (at your option) any later
+version.
-GNU CC is distributed in the hope that it will be useful,
-but WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-GNU General Public License for more details.
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
You should have received a copy of the GNU General Public License
-along with GNU CC; see the file COPYING. If not, write to
-the Free Software Foundation, 59 Temple Place - Suite 330,
-Boston, MA 02111-1307, USA. */
+along with GCC; see the file COPYING. If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA. */
/* This file contains the data flow analysis pass of the compiler. It
computes data flow information which tells combine_instructions
ENTRY_BLOCK, /* index */
0, /* loop_depth */
0, /* count */
- 0 /* frequency */
+ 0, /* frequency */
+ 0 /* flags */
},
{
NULL, /* head */
EXIT_BLOCK, /* index */
0, /* loop_depth */
0, /* count */
- 0 /* frequency */
+ 0, /* frequency */
+ 0 /* flags */
}
};
print_rtl_and_abort_fcn (__FILE__, __LINE__, __FUNCTION__)
/* Forward declarations */
-static bool try_crossjump_to_edge PARAMS ((int, edge, edge));
+static bool try_crossjump_to_edge PARAMS ((int, edge, edge));
static bool try_crossjump_bb PARAMS ((int, basic_block));
static bool outgoing_edges_match PARAMS ((basic_block, basic_block));
static int flow_find_cross_jump PARAMS ((int, basic_block, basic_block,
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));
+static void make_edges PARAMS ((rtx, int, int, int));
static void make_label_edge PARAMS ((sbitmap *, basic_block,
rtx, int));
static void make_eh_edge PARAMS ((sbitmap *, basic_block, rtx));
static void delete_unreachable_blocks PARAMS ((void));
static int can_delete_note_p PARAMS ((rtx));
-static void expunge_block PARAMS ((basic_block));
static int can_delete_label_p PARAMS ((rtx));
static int tail_recursion_label_p PARAMS ((rtx));
static int merge_blocks_move_predecessor_nojumps PARAMS ((basic_block,
static bool can_fallthru PARAMS ((basic_block, basic_block));
static bool try_redirect_by_replacing_jump PARAMS ((edge, basic_block));
static bool try_simplify_condjump PARAMS ((basic_block));
-static bool try_forward_edges PARAMS ((basic_block));
+static bool try_forward_edges PARAMS ((int, basic_block));
static void tidy_fallthru_edges PARAMS ((void));
static int verify_wide_reg_1 PARAMS ((rtx *, void *));
static void verify_wide_reg PARAMS ((int, rtx, rtx));
static void verify_local_live_at_start PARAMS ((regset, basic_block));
-static int noop_move_p PARAMS ((rtx));
-static void delete_noop_moves PARAMS ((rtx));
static void notice_stack_pointer_modification_1 PARAMS ((rtx, rtx, void *));
static void notice_stack_pointer_modification PARAMS ((rtx));
static void mark_reg PARAMS ((rtx, void *));
const char *))
ATTRIBUTE_NORETURN;
+static void add_to_mem_set_list PARAMS ((struct propagate_block_info *,
+ rtx));
static void invalidate_mems_from_autoinc PARAMS ((struct propagate_block_info *,
rtx));
static void invalidate_mems_from_set PARAMS ((struct propagate_block_info *,
static void flow_loops_tree_build PARAMS ((struct loops *));
static int flow_loop_level_compute PARAMS ((struct loop *, int));
static int flow_loops_level_compute PARAMS ((struct loops *));
-static void find_sub_basic_blocks PARAMS ((basic_block));
+static void delete_dead_jumptables PARAMS ((void));
+static bool back_edge_of_syntactic_loop_p PARAMS ((basic_block, basic_block));
+static bool need_fake_edge_p PARAMS ((rtx));
\f
/* Find basic blocks of the current function.
F is the first insn of the function and NREGS the number of register
compute_bb_for_insn (max_uid);
/* Discover the edges of our cfg. */
- make_edges (label_value_list);
+ make_edges (label_value_list, 0, n_basic_blocks - 1, 0);
/* Do very simple cleanup now, for the benefit of code that runs between
here and cleanup_cfg, e.g. thread_prologue_and_epilogue_insns. */
/* Assume that someone emitted code with control flow instructions to the
basic block. Update the data structure. */
-static void
+void
find_sub_basic_blocks (bb)
basic_block bb;
{
- rtx first_insn = bb->head, insn;
+ rtx insn = bb->head;
rtx end = bb->end;
- edge succ_list = bb->succ;
rtx jump_insn = NULL_RTX;
- int created = 0;
- int barrier = 0;
edge falltru = 0;
- basic_block first_bb = bb, last_bb;
+ basic_block first_bb = bb;
int i;
- if (GET_CODE (first_insn) == LABEL_REF)
- first_insn = NEXT_INSN (first_insn);
- first_insn = NEXT_INSN (first_insn);
- bb->succ = NULL;
+ if (insn == bb->end)
+ return;
+
+ if (GET_CODE (insn) == CODE_LABEL)
+ insn = NEXT_INSN (insn);
- insn = first_insn;
/* Scan insn chain and try to find new basic block boundaries. */
- while (insn != end)
+ while (1)
{
enum rtx_code code = GET_CODE (insn);
switch (code)
{
- case JUMP_INSN:
- /* We need some special care for those expressions. */
- if (GET_CODE (PATTERN (insn)) == ADDR_VEC
- || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
- abort();
- jump_insn = insn;
- break;
case BARRIER:
if (!jump_insn)
abort ();
- barrier = 1;
break;
/* On code label, split current basic block. */
case CODE_LABEL:
if (jump_insn)
bb->end = jump_insn;
bb = falltru->dest;
- if (barrier)
- remove_edge (falltru);
- barrier = 0;
+ remove_edge (falltru);
jump_insn = 0;
- created = 1;
if (LABEL_ALTERNATE_NAME (insn))
make_edge (NULL, ENTRY_BLOCK_PTR, bb, 0);
break;
case INSN:
+ case JUMP_INSN:
/* In case we've previously split insn on the JUMP_INSN, move the
block header to proper place. */
if (jump_insn)
falltru = split_block (bb, PREV_INSN (insn));
bb->end = jump_insn;
bb = falltru->dest;
- if (barrier)
- abort ();
+ remove_edge (falltru);
jump_insn = 0;
}
+ /* We need some special care for those expressions. */
+ if (GET_CODE (insn) == JUMP_INSN)
+ {
+ if (GET_CODE (PATTERN (insn)) == ADDR_VEC
+ || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
+ abort();
+ jump_insn = insn;
+ }
+ break;
default:
break;
}
+ if (insn == end)
+ break;
insn = NEXT_INSN (insn);
}
- /* Last basic block must end in the original BB end. */
- if (jump_insn)
- abort ();
- /* Wire in the original edges for last basic block. */
- if (created)
- {
- bb->succ = succ_list;
- while (succ_list)
- succ_list->src = bb, succ_list = succ_list->succ_next;
- }
- else
- bb->succ = succ_list;
+ /* In case expander replaced normal insn by sequence terminating by
+ return and barrier, or possibly other sequence not behaving like
+ ordinary jump, we need to take care and move basic block boundary. */
+ if (jump_insn && GET_CODE (bb->end) != JUMP_INSN)
+ bb->end = jump_insn;
+
+ /* We've possibly replaced the conditional jump by conditional jump
+ followed by cleanup at fallthru edge, so the outgoing edges may
+ be dead. */
+ purge_dead_edges (bb);
/* Now re-scan and wire in all edges. This expect simple (conditional)
jumps at the end of each new basic blocks. */
- last_bb = bb;
- for (i = first_bb->index; i < last_bb->index; i++)
+ make_edges (NULL, first_bb->index, bb->index, 1);
+
+ /* Update branch probabilities. Expect only (un)conditional jumps
+ to be created with only the forward edges. */
+ for (i = first_bb->index; i <= bb->index; i++)
{
- bb = BASIC_BLOCK (i);
- if (GET_CODE (bb->end) == JUMP_INSN)
+ edge e,f;
+ basic_block b = BASIC_BLOCK (i);
+ if (b != first_bb)
{
- mark_jump_label (PATTERN (bb->end), bb->end, 0);
- make_label_edge (NULL, bb, JUMP_LABEL (bb->end), 0);
+ b->count = 0;
+ b->frequency = 0;
+ for (e = b->pred; e; e=e->pred_next)
+ {
+ b->count += e->count;
+ b->frequency += EDGE_FREQUENCY (e);
+ }
+ }
+ 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)
+ continue;
+ 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;
}
- insn = NEXT_INSN (insn);
}
}
cleanup_cfg (mode)
int mode;
{
+ int i;
+
timevar_push (TV_CLEANUP_CFG);
delete_unreachable_blocks ();
if (try_optimize_cfg (mode))
free_EXPR_LIST_list (&label_value_list);
free_EXPR_LIST_list (&tail_recursion_label_list);
timevar_pop (TV_CLEANUP_CFG);
+
+ /* Clear bb->aux on all basic blocks. */
+ for (i = 0; i < n_basic_blocks; ++i)
+ BASIC_BLOCK (i)->aux = NULL;
}
/* Create a new basic block consisting of the instructions between
n_edges = 0;
}
-/* Identify the edges between basic blocks.
+/* Identify the edges between basic blocks MIN to MAX.
NONLOCAL_LABEL_LIST is a list of non-local labels in the function. Blocks
that are otherwise unreachable may be reachable with a non-local goto.
the list of exception regions active at the end of the basic block. */
static void
-make_edges (label_value_list)
+make_edges (label_value_list, min, max, update_p)
rtx label_value_list;
+ int min, max, update_p;
{
int i;
sbitmap *edge_cache = NULL;
{
edge_cache = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
sbitmap_vector_zero (edge_cache, n_basic_blocks);
+
+ if (update_p)
+ for (i = min; i <= max; ++i)
+ {
+ edge e;
+ for (e = BASIC_BLOCK (i)->succ; e ; e = e->succ_next)
+ if (e->dest != EXIT_BLOCK_PTR)
+ SET_BIT (edge_cache[i], e->dest->index);
+ }
}
/* By nature of the way these get numbered, block 0 is always the entry. */
make_edge (edge_cache, ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU);
- for (i = 0; i < n_basic_blocks; ++i)
+ for (i = min; i <= max; ++i)
{
basic_block bb = BASIC_BLOCK (i);
rtx insn, x;
}
}
\f
+/* Mark the back edges in DFS traversal.
+ Return non-zero if a loop (natural or otherwise) is present.
+ Inspired by Depth_First_Search_PP described in:
+
+ Advanced Compiler Design and Implementation
+ Steven Muchnick
+ Morgan Kaufmann, 1997
+
+ and heavily borrowed from flow_depth_first_order_compute. */
+
+bool
+mark_dfs_back_edges ()
+{
+ edge *stack;
+ int *pre;
+ int *post;
+ int sp;
+ int prenum = 1;
+ int postnum = 1;
+ sbitmap visited;
+ bool found = false;
+
+ /* Allocate the preorder and postorder number arrays. */
+ pre = (int *) xcalloc (n_basic_blocks, sizeof (int));
+ post = (int *) xcalloc (n_basic_blocks, sizeof (int));
+
+ /* Allocate stack for back-tracking up CFG. */
+ stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
+ sp = 0;
+
+ /* Allocate bitmap to track nodes that have been visited. */
+ visited = sbitmap_alloc (n_basic_blocks);
+
+ /* None of the nodes in the CFG have been visited yet. */
+ sbitmap_zero (visited);
+
+ /* Push the first edge on to the stack. */
+ stack[sp++] = ENTRY_BLOCK_PTR->succ;
+
+ while (sp)
+ {
+ edge e;
+ basic_block src;
+ basic_block dest;
+
+ /* Look at the edge on the top of the stack. */
+ e = stack[sp - 1];
+ src = e->src;
+ dest = e->dest;
+ e->flags &= ~EDGE_DFS_BACK;
+
+ /* Check if the edge destination has been visited yet. */
+ if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
+ {
+ /* Mark that we have visited the destination. */
+ SET_BIT (visited, dest->index);
+
+ pre[dest->index] = prenum++;
+
+ if (dest->succ)
+ {
+ /* Since the DEST node has been visited for the first
+ time, check its successors. */
+ stack[sp++] = dest->succ;
+ }
+ else
+ post[dest->index] = postnum++;
+ }
+ else
+ {
+ if (dest != EXIT_BLOCK_PTR && src != ENTRY_BLOCK_PTR
+ && pre[src->index] >= pre[dest->index]
+ && post[dest->index] == 0)
+ e->flags |= EDGE_DFS_BACK, found = true;
+
+ if (! e->succ_next && src != ENTRY_BLOCK_PTR)
+ post[src->index] = postnum++;
+
+ if (e->succ_next)
+ stack[sp - 1] = e->succ_next;
+ else
+ sp--;
+ }
+ }
+
+ free (pre);
+ free (post);
+ free (stack);
+ sbitmap_free (visited);
+
+ return found;
+}
+\f
/* Split a block BB after insn INSN creating a new fallthru edge.
Return the new edge. Note that to keep other parts of the compiler happy,
this function renumbers all the basic blocks so that the new
if (block == EXIT_BLOCK_PTR)
return NULL_RTX;
if (GET_CODE (block->head) != CODE_LABEL)
- block->head = emit_label_before (gen_label_rtx (), block->head);
+ {
+ block->head = emit_label_before (gen_label_rtx (), block->head);
+ if (basic_block_for_insn)
+ set_block_for_insn (block->head, block);
+ }
return block->head;
}
/* Attempt to perform edge redirection by replacing possibly complex jump
instruction by unconditional jump or removing jump completely.
- This can apply only if all edges now point to the same block.
+ This can apply only if all edges now point to the same block.
The parameters and return values are equivalent to redirect_edge_and_branch.
*/
return true;
}
+/* Return last loop_beg note appearing after INSN, before start of next
+ basic block. Return INSN if there are no such notes.
+
+ When emmiting jump to redirect an fallthru edge, it should always
+ appear after the LOOP_BEG notes, as loop optimizer expect loop to
+ eighter start by fallthru edge or jump following the LOOP_BEG note
+ jumping to the loop exit test. */
+rtx
+last_loop_beg_note (insn)
+ rtx insn;
+{
+ rtx last = insn;
+ insn = NEXT_INSN (insn);
+ while (GET_CODE (insn) == NOTE
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK)
+ {
+ if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
+ last = insn;
+ insn = NEXT_INSN (insn);
+ }
+ return last;
+}
+
/* Attempt to change code to redirect edge E to TARGET.
Don't do that on expense of adding new instructions or reordering
basic blocks.
fprintf (rtl_dump_file, "Edge %i->%i redirected to %i\n",
e->src->index, e->dest->index, target->index);
if (e->dest != target)
- {
- edge s;
- /* Check whether the edge is already present. */
- for (s = src->succ; s; s=s->succ_next)
- if (s->dest == target)
- break;
- if (s)
- {
- s->flags |= e->flags;
- s->probability += e->probability;
- s->count += e->count;
- remove_edge (e);
- }
- else
- redirect_edge_succ (e, target);
- }
+ redirect_edge_succ_nodup (e, target);
return true;
}
/* Case of the fallthru block. */
if (!e->src->succ->succ_next)
{
- e->src->end = emit_jump_insn_after (gen_jump (label), e->src->end);
+ e->src->end = emit_jump_insn_after (gen_jump (label),
+ last_loop_beg_note (e->src->end));
JUMP_LABEL (e->src->end) = label;
LABEL_NUSES (label)++;
if (basic_block_for_insn)
memset (new_bb, 0, sizeof (*new_bb));
- new_bb->end = new_bb->head = e->src->end;
+ new_bb->end = new_bb->head = last_loop_beg_note (e->src->end);
new_bb->succ = NULL;
new_bb->pred = new_edge;
new_bb->count = e->count;
- new_bb->frequency = e->probability * e->src->frequency / REG_BR_PROB_BASE;
+ new_bb->frequency = EDGE_FREQUENCY (e);
new_bb->loop_depth = e->dest->loop_depth;
new_edge->flags = EDGE_FALLTHRU;
new_edge->probability = e->probability;
new_edge->count = e->count;
- if (e->dest->global_live_at_start)
+ if (target->global_live_at_start)
{
new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
return new_bb;
}
+/* Helper function for split_edge. Return true in case edge BB2 to BB1
+ is back edge of syntactic loop. */
+static bool
+back_edge_of_syntactic_loop_p (bb1, bb2)
+ basic_block bb1, bb2;
+{
+ rtx insn;
+ int count = 0;
+
+ if (bb1->index > bb2->index)
+ return false;
+
+ if (bb1->index == bb2->index)
+ return true;
+
+ for (insn = bb1->end; insn != bb2->head && count >= 0;
+ insn = NEXT_INSN (insn))
+ if (GET_CODE (insn) == NOTE)
+ {
+ if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
+ count++;
+ if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
+ count--;
+ }
+
+ return count >= 0;
+}
+
/* Split a (typically critical) edge. Return the new block.
Abort on abnormal edges.
/* Wire them up. */
bb->succ = edge_out;
bb->count = edge_in->count;
- bb->frequency = (edge_in->probability * edge_in->src->frequency
- / REG_BR_PROB_BASE);
+ bb->frequency = EDGE_FREQUENCY (edge_in);
edge_in->flags &= ~EDGE_CRITICAL;
/* Now add the jump insn ... */
pos = emit_jump_insn_after (gen_jump (old_succ->head),
- jump_block->end);
+ last_loop_beg_note (jump_block->end));
jump_block->end = pos;
if (basic_block_for_insn)
set_block_for_new_insns (pos, jump_block);
if (old_succ != EXIT_BLOCK_PTR
&& PREV_INSN (old_succ->head)
&& GET_CODE (PREV_INSN (old_succ->head)) == NOTE
- && NOTE_LINE_NUMBER (PREV_INSN (old_succ->head)) == NOTE_INSN_LOOP_BEG)
+ && NOTE_LINE_NUMBER (PREV_INSN (old_succ->head)) == NOTE_INSN_LOOP_BEG
+ && !back_edge_of_syntactic_loop_p (old_succ, old_pred))
bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK,
PREV_INSN (old_succ->head));
else if (old_succ != EXIT_BLOCK_PTR)
if (GET_CODE (bb->end) == JUMP_INSN)
{
before = bb->end;
+ while (GET_CODE (PREV_INSN (before)) == NOTE
+ && NOTE_LINE_NUMBER (PREV_INSN (before)) == NOTE_INSN_LOOP_BEG)
+ before = PREV_INSN (before);
}
else
{
{
int i;
basic_block bb;
+ compute_bb_for_insn (get_max_uid ());
#ifdef ENABLE_CHECKING
verify_flow_info ();
}
}
-/* Add fake edges to the function exit for any non constant calls in
- the bitmap of blocks specified by BLOCKS or to the whole CFG if
- BLOCKS is zero. Return the nuber of blocks that were split. */
+/* Return true if we need to add fake edge to exit.
+ Helper function for the flow_call_edges_add. */
+static bool
+need_fake_edge_p (insn)
+ rtx insn;
+{
+ if (!INSN_P (insn))
+ return false;
+
+ if ((GET_CODE (insn) == CALL_INSN
+ && !SIBLING_CALL_P (insn)
+ && !find_reg_note (insn, REG_NORETURN, NULL)
+ && !find_reg_note (insn, REG_ALWAYS_RETURN, NULL)
+ && !CONST_OR_PURE_CALL_P (insn)))
+ return true;
+
+ return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS
+ && MEM_VOLATILE_P (PATTERN (insn)))
+ || (GET_CODE (PATTERN (insn)) == PARALLEL
+ && asm_noperands (insn) != -1
+ && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0)))
+ || GET_CODE (PATTERN (insn)) == ASM_INPUT);
+}
+
+/* Add fake edges to the function exit for any non constant and non noreturn
+ calls, volatile inline assembly in the bitmap of blocks specified by
+ BLOCKS or to the whole CFG if BLOCKS is zero. Return the nuber of blocks
+ that were split.
+
+ The goal is to expose cases in which entering a basic block does not imply
+ that all subsequent instructions must be executed. */
int
flow_call_edges_add (blocks)
int blocks_split = 0;
int bb_num = 0;
basic_block *bbs;
+ bool check_last_block = false;
/* Map bb indicies into basic block pointers since split_block
will renumber the basic blocks. */
{
for (i = 0; i < n_basic_blocks; i++)
bbs[bb_num++] = BASIC_BLOCK (i);
+ check_last_block = true;
}
else
{
- EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i,
+ EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i,
{
bbs[bb_num++] = BASIC_BLOCK (i);
+ if (i == n_basic_blocks - 1)
+ check_last_block = true;
});
}
+ /* In the last basic block, before epilogue generation, there will be
+ a fallthru edge to EXIT. Special care is required if the last insn
+ of the last basic block is a call because make_edge folds duplicate
+ edges, which would result in the fallthru edge also being marked
+ fake, which would result in the fallthru edge being removed by
+ remove_fake_edges, which would result in an invalid CFG.
+
+ Moreover, we can't elide the outgoing fake edge, since the block
+ profiler needs to take this into account in order to solve the minimal
+ spanning tree in the case that the call doesn't return.
+
+ Handle this by adding a dummy instruction in a new last basic block. */
+ if (check_last_block
+ && need_fake_edge_p (BASIC_BLOCK (n_basic_blocks - 1)->end))
+ {
+ edge e;
+ for (e = BASIC_BLOCK (n_basic_blocks - 1)->succ; e; e = e->succ_next)
+ if (e->dest == EXIT_BLOCK_PTR)
+ break;
+ insert_insn_on_edge (gen_rtx_USE (VOIDmode, const0_rtx), e);
+ commit_edge_insertions ();
+ }
+
/* Now add fake edges to the function exit for any non constant
calls since there is no way that we can determine if they will
for (insn = bb->end; ; insn = prev_insn)
{
prev_insn = PREV_INSN (insn);
- if (GET_CODE (insn) == CALL_INSN && ! CONST_CALL_P (insn))
+ if (need_fake_edge_p (insn))
{
edge e;
+ /* The above condition should be enought to verify that there is
+ no edge to the exit block in CFG already. Calling make_edge in
+ such case would make us to mark that edge as fake and remove it
+ later. */
+#ifdef ENABLE_CHECKING
+ if (insn == bb->end)
+ for (e = bb->succ; e; e = e->succ_next)
+ if (e->dest == EXIT_BLOCK_PTR)
+ abort ();
+#endif
+
/* Note that the following may create a new basic block
and renumber the existing basic blocks. */
e = split_block (bb, insn);
return blocks_split;
}
\f
-/* Find unreachable blocks. An unreachable block will have NULL in
- block->aux, a non-NULL value indicates the block is reachable. */
+/* Find unreachable blocks. An unreachable block will have 0 in
+ the reachable bit in block->flags. A non-zero value indicates the
+ block is reachable. */
void
find_unreachable_blocks ()
n = n_basic_blocks;
tos = worklist = (basic_block *) xmalloc (sizeof (basic_block) * n);
- /* Use basic_block->aux as a marker. Clear them all. */
+ /* Clear all the reachability flags. */
for (i = 0; i < n; ++i)
- BASIC_BLOCK (i)->aux = NULL;
+ BASIC_BLOCK (i)->flags &= ~BB_REACHABLE;
/* Add our starting points to the worklist. Almost always there will
be only one. It isn't inconcievable that we might one day directly
{
*tos++ = e->dest;
- /* Mark the block with a handy non-null value. */
- e->dest->aux = e;
+ /* Mark the block reachable. */
+ e->dest->flags |= BB_REACHABLE;
}
/* Iterate: find everything reachable from what we've already seen. */
basic_block b = *--tos;
for (e = b->succ; e; e = e->succ_next)
- if (!e->dest->aux)
+ if (!(e->dest->flags & BB_REACHABLE))
{
*tos++ = e->dest;
- e->dest->aux = e;
+ e->dest->flags |= BB_REACHABLE;
}
}
{
basic_block b = BASIC_BLOCK (i);
- if (b->aux != NULL)
- /* This block was found. Tidy up the mark. */
- b->aux = NULL;
- else
+ if (!(b->flags & BB_REACHABLE))
flow_delete_block (b);
}
/* Remove block B from the basic block array and compact behind it. */
-static void
+void
expunge_block (b)
basic_block b;
{
#ifdef HAVE_cc0
/* If this was a conditional jump, we need to also delete
the insn that set cc0. */
- if (prev && sets_cc0_p (prev))
+ if (only_sets_cc0_p (prev))
{
rtx tmp = prev;
prev = prev_nonnote_insn (prev);
merge_blocks_move_predecessor_nojumps (a, b)
basic_block a, b;
{
- rtx start, end, barrier;
+ rtx barrier;
int index;
- start = a->head;
- end = a->end;
-
- barrier = next_nonnote_insn (end);
+ barrier = next_nonnote_insn (a->end);
if (GET_CODE (barrier) != BARRIER)
abort ();
flow_delete_insn (barrier);
and adjust the block trees appropriately. Even better would be to have
a tighter connection between block trees and rtl so that this is not
necessary. */
- start = squeeze_notes (start, end);
+ squeeze_notes (&a->head, &a->end);
/* Scramble the insn chain. */
- if (end != PREV_INSN (b->head))
- reorder_insns (start, end, PREV_INSN (b->head));
+ if (a->end != PREV_INSN (b->head))
+ reorder_insns (a->head, a->end, PREV_INSN (b->head));
if (rtl_dump_file)
{
merge_blocks_move_successor_nojumps (a, b)
basic_block a, b;
{
- rtx start, end, barrier;
+ rtx barrier;
- start = b->head;
- end = b->end;
- barrier = NEXT_INSN (end);
+ barrier = NEXT_INSN (b->end);
/* Recognize a jump table following block B. */
if (barrier
&& (GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_VEC
|| GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_DIFF_VEC))
{
- end = NEXT_INSN (barrier);
- barrier = NEXT_INSN (end);
+ b->end = NEXT_INSN (barrier);
+ barrier = NEXT_INSN (b->end);
}
/* There had better have been a barrier there. Delete it. */
and adjust the block trees appropriately. Even better would be to have
a tighter connection between block trees and rtl so that this is not
necessary. */
- start = squeeze_notes (start, end);
+ squeeze_notes (&b->head, &b->end);
/* Scramble the insn chain. */
- reorder_insns (start, end, a->end);
+ reorder_insns (b->head, b->end, a->end);
/* Now blocks A and B are contiguous. Merge them. */
merge_blocks_nomove (a, b);
if (GET_CODE (barrier) != BARRIER)
abort ();
flow_delete_insn (barrier);
+
+ return 1;
}
return 0;
/* The conditional branch must target the block after the
unconditional branch. */
cbranch_dest_block = cbranch_jump_edge->dest;
- if (cbranch_dest_block->index != jump_block->index + 1)
+
+ if (!can_fallthru (jump_block, cbranch_dest_block))
return false;
/* Invert the conditional branch. Prevent jump.c from deleting
fprintf (rtl_dump_file, "Simplifying condjump %i around jump %i\n",
INSN_UID (cbranch_insn), INSN_UID (jump_block->end));
- /* Success. Update the CFG to match. */
- redirect_edge_succ (cbranch_jump_edge, cbranch_dest_block);
- redirect_edge_succ (cbranch_fallthru_edge, jump_dest_block);
+ /* Success. Update the CFG to match. Note that after this point
+ the edge variable names appear backwards; the redirection is done
+ this way to preserve edge profile data. */
+ cbranch_jump_edge = redirect_edge_succ_nodup (cbranch_jump_edge,
+ cbranch_dest_block);
+ cbranch_fallthru_edge = redirect_edge_succ_nodup (cbranch_fallthru_edge,
+ jump_dest_block);
cbranch_jump_edge->flags |= EDGE_FALLTHRU;
cbranch_fallthru_edge->flags &= ~EDGE_FALLTHRU;
-
+
+ /* Delete the block with the unconditional jump, and clean up the mess. */
flow_delete_block (jump_block);
+ tidy_fallthru_edge (cbranch_jump_edge, cbranch_block, cbranch_dest_block);
+
return true;
}
Return true if sucessful. */
static bool
-try_forward_edges (b)
+try_forward_edges (mode, b)
basic_block b;
+ int mode;
{
bool changed = false;
edge e, next;
next = e->succ_next;
/* Skip complex edges because we don't know how to update them.
- Skip fallthru edges because there's no jump to update. */
- if (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))
+
+ Still handle fallthru edges, as we can suceed to forward fallthru
+ edge to the same place as the branch edge of conditional branch
+ and turn conditional branch to an unconditonal branch. */
+ if (e->flags & EDGE_COMPLEX)
continue;
target = first = e->dest;
/* Bypass trivial infinite loops. */
if (target == target->succ->dest)
counter = n_basic_blocks;
+
+ /* Avoid killing of loop pre-headers, as it is the place loop
+ optimizer wants to hoist code to.
+
+ For fallthru forwarders, the LOOP_BEG note must appear between
+ the header of block and CODE_LABEL of the loop, for non forwarders
+ it must appear before the JUMP_INSN. */
+ if (mode & CLEANUP_PRE_LOOP)
+ {
+ rtx insn = (target->succ->flags & EDGE_FALLTHRU
+ ? target->head : prev_nonnote_insn (target->end));
+
+ if (GET_CODE (insn) != NOTE)
+ insn = NEXT_INSN (insn);
+
+ for (;insn && GET_CODE (insn) != CODE_LABEL && !INSN_P (insn);
+ insn = NEXT_INSN (insn))
+ if (GET_CODE (insn) == NOTE
+ && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
+ break;
+
+ if (GET_CODE (insn) == NOTE)
+ break;
+ }
target = target->succ->dest, counter++;
}
}
else if (target == first)
; /* We didn't do anything. */
- else if (redirect_edge_and_branch (e, target))
+ else
{
- /* We successfully forwarded the edge. Now update profile
- data: for each edge we traversed in the chain, remove
- the original edge's execution count. */
- do
+ /* Save the values now, as the edge may get removed. */
+ gcov_type edge_count = e->count;
+ int edge_probability = e->probability;
+
+ if (redirect_edge_and_branch (e, target))
{
- first->count -= e->count;
- first->succ->count -= e->count;
- first->frequency -= ((e->probability * b->frequency
- + REG_BR_PROB_BASE / 2)
- / REG_BR_PROB_BASE);
- first = first->succ->dest;
- }
- while (first != target);
+ /* We successfully forwarded the edge. Now update profile
+ data: for each edge we traversed in the chain, remove
+ the original edge's execution count. */
+ int edge_frequency = ((edge_probability * b->frequency
+ + REG_BR_PROB_BASE / 2)
+ / REG_BR_PROB_BASE);
+
+ do
+ {
+ first->count -= edge_count;
+ first->succ->count -= edge_count;
+ first->frequency -= edge_frequency;
+ first = first->succ->dest;
+ }
+ while (first != target);
- changed = true;
- }
- else
- {
- if (rtl_dump_file)
- fprintf (rtl_dump_file, "Forwarding edge %i->%i to %i failed.\n",
- b->index, e->dest->index, target->index);
+ changed = true;
+ }
+ else
+ {
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "Forwarding edge %i->%i to %i failed.\n",
+ b->index, e->dest->index, target->index);
+ }
}
}
need to be compared for equivalence, which we'll do below. */
i1 = bb1->end;
- if (onlyjump_p (i1))
+ if (onlyjump_p (i1)
+ || (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
i1 = PREV_INSN (i1);
i2 = bb2->end;
- if (onlyjump_p (i2))
+ if (onlyjump_p (i2)
+ || (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
i2 = PREV_INSN (i2);
last1 = afterlast1 = last2 = afterlast2 = NULL_RTX;
/* Return true iff outgoing edges of BB1 and BB2 match, together with
the branch instruction. This means that if we commonize the control
- flow before end of the basic block, the semantic remains unchanged.
+ flow before end of the basic block, the semantic remains unchanged.
We may assume that there exists one edge with a common destination. */
edge s;
rtx last;
rtx label;
+ rtx note;
/* Search backward through forwarder blocks. We don't need to worry
about multiple entry or chained forwarders, as they will be optimized
&& forwarder_block_p (e2->dest->succ->dest))
return false;
- /* Likewise with dead code. */
- /* ??? Won't we have eliminated these by now? */
+ /* Likewise with dead code (possibly newly created by the other optimizations
+ of cfg_cleanup). */
if (!src1->pred || !src2->pred)
return false;
- /* Likewise with non-jump edges. */
- /* ??? Non-jump? You mean GET_CODE (e1->src-end) != JUMP_INSN?
- This fails for computed-goto as well, which may in fact be joinable. */
+ /* Likewise with complex edges.
+ ??? We should be able to handle most complex edges later with some
+ care. */
if (e1->flags & EDGE_COMPLEX)
return false;
- /* Look for the common insn sequence, part the first ... */
+ /* Look for the common insn sequence, part the first ... */
if (!outgoing_edges_match (src1, src2))
return false;
{
s->dest->succ->count += s2->count;
s->dest->count += s2->count;
- s->dest->frequency += ((s->probability * s->src->frequency)
- / REG_BR_PROB_BASE);
+ s->dest->frequency += EDGE_FREQUENCY (s);
}
if (forwarder_block_p (s2->dest))
{
s2->dest->succ->count -= s2->count;
s2->dest->count -= s2->count;
- s2->dest->frequency -= ((s->probability * s->src->frequency)
- / REG_BR_PROB_BASE);
+ s2->dest->frequency -= EDGE_FREQUENCY (s);
}
if (!redirect_to->frequency && !src1->frequency)
s->probability = (s->probability + s2->probability) / 2;
/ (redirect_to->frequency + src1->frequency));
}
- /* FIXME: enable once probabilities are fetched properly at CFG build. */
-#if 0
note = find_reg_note (redirect_to->end, REG_BR_PROB, 0);
if (note)
XEXP (note, 0) = GEN_INT (BRANCH_EDGE (redirect_to)->probability);
-#endif
/* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
while (src1->succ)
remove_edge (src1->succ);
make_edge (NULL, src1, redirect_to, 0);
+ src1->succ->probability = REG_BR_PROB_BASE;
+ src1->succ->count = src1->count;
return true;
}
If there is a match, we'll do it the other way around. */
if (e == fallthru)
continue;
-
+
if (try_crossjump_to_edge (mode, e, fallthru))
{
changed = true;
/* The "first successor" check above only prevents multiple
checks of crossjump(A,B). In order to prevent redundant
- checks of crossjump(B,A), require that A be the block
+ checks of crossjump(B,A), require that A be the block
with the lowest index. */
- /* ??? Perhaps better is lowest execution frequency. */
if (e->src->index > e2->src->index)
continue;
&& !(b->pred->flags & EDGE_COMPLEX)
&& GET_CODE (b->head) == CODE_LABEL
&& (!(mode & CLEANUP_PRE_SIBCALL)
- || !tail_recursion_label_p (b->head))
+ || !tail_recursion_label_p (b->head))
/* If previous block ends with condjump jumping to next BB,
we can't delete the label. */
&& (b->pred->src == ENTRY_BLOCK_PTR
fprintf (rtl_dump_file, "Deleting fallthru block %i.\n",
b->index);
c = BASIC_BLOCK (b->index ? b->index - 1 : 1);
- redirect_edge_succ (b->pred, b->succ->dest);
+ redirect_edge_succ_nodup (b->pred, b->succ->dest);
flow_delete_block (b);
changed = true;
b = c;
changed_here = true;
/* Simplify branch to branch. */
- if (try_forward_edges (b))
+ if (try_forward_edges (mode, b))
changed_here = true;
/* Look for shared code between blocks. */
#ifdef HAVE_cc0
/* If this was a conditional jump, we need to also delete
the insn that set cc0. */
- if (any_condjump_p (q) && sets_cc0_p (PREV_INSN (q)))
+ if (any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q)))
q = PREV_INSN (q);
#endif
#endif
if (! optimize)
- flags &= ~(PROP_LOG_LINKS | PROP_AUTOINC);
+ flags &= ~(PROP_LOG_LINKS | PROP_AUTOINC | PROP_ALLOW_CFG_CHANGES);
/* The post-reload life analysis have (on a global basis) the same
registers live as was computed by reload itself. elimination
}
}
#endif
+ /* Removing dead insns should've made jumptables really dead. */
+ delete_dead_jumptables ();
}
/* A subroutine of verify_wide_reg, called through for_each_rtx.
tmp = INITIALIZE_REG_SET (tmp_head);
+ /* Changes to the CFG are only allowed when
+ doing a global update for the entire CFG. */
+ if ((prop_flags & PROP_ALLOW_CFG_CHANGES)
+ && (extent == UPDATE_LIFE_LOCAL || blocks))
+ abort ();
+
/* For a global update, we go through the relaxation process again. */
if (extent != UPDATE_LIFE_LOCAL)
{
- calculate_global_regs_live (blocks, blocks,
- prop_flags & PROP_SCAN_DEAD_CODE);
+ for ( ; ; )
+ {
+ int changed = 0;
+
+ calculate_global_regs_live (blocks, blocks,
+ prop_flags & (PROP_SCAN_DEAD_CODE
+ | PROP_ALLOW_CFG_CHANGES));
+
+ if ((prop_flags & (PROP_KILL_DEAD_CODE | PROP_ALLOW_CFG_CHANGES))
+ != (PROP_KILL_DEAD_CODE | PROP_ALLOW_CFG_CHANGES))
+ break;
+
+ /* Removing dead code may allow the CFG to be simplified which
+ in turn may allow for further dead code detection / removal. */
+ for (i = n_basic_blocks - 1; i >= 0; --i)
+ {
+ basic_block bb = BASIC_BLOCK (i);
+
+ COPY_REG_SET (tmp, bb->global_live_at_end);
+ changed |= propagate_block (bb, tmp, NULL, NULL,
+ prop_flags & (PROP_SCAN_DEAD_CODE
+ | PROP_KILL_DEAD_CODE));
+ }
+
+ if (! changed || ! try_optimize_cfg (CLEANUP_EXPENSIVE))
+ break;
+
+ delete_unreachable_blocks ();
+ mark_critical_edges ();
+ }
/* If asked, remove notes from the blocks we'll update. */
if (extent == UPDATE_LIFE_GLOBAL_RM_NOTES)
}
}
-/* Return nonzero if an insn consists only of SETs, each of which only sets a
- value to itself. */
+/* Delete any insns that copy a register to itself. */
-static int
-noop_move_p (insn)
- rtx insn;
+void
+delete_noop_moves (f)
+ rtx f ATTRIBUTE_UNUSED;
{
- rtx pat = PATTERN (insn);
-
- /* Insns carrying these notes are useful later on. */
- if (find_reg_note (insn, REG_EQUAL, NULL_RTX))
- return 0;
-
- if (GET_CODE (pat) == SET && set_noop_p (pat))
- return 1;
+ int i;
+ rtx insn, next;
+ basic_block bb;
- if (GET_CODE (pat) == PARALLEL)
+ for (i = 0; i < n_basic_blocks; i++)
{
- int i;
- /* If nothing but SETs of registers to themselves,
- this insn can also be deleted. */
- for (i = 0; i < XVECLEN (pat, 0); i++)
+ bb = BASIC_BLOCK (i);
+ for (insn = bb->head; insn != NEXT_INSN (bb->end); insn = next)
{
- rtx tem = XVECEXP (pat, 0, i);
-
- if (GET_CODE (tem) == USE
- || GET_CODE (tem) == CLOBBER)
- continue;
-
- if (GET_CODE (tem) != SET || ! set_noop_p (tem))
- return 0;
+ next = NEXT_INSN (insn);
+ if (INSN_P (insn) && noop_move_p (insn))
+ {
+ /* Do not call flow_delete_insn here to not confuse backward
+ pointers of LIBCALL block. */
+ PUT_CODE (insn, NOTE);
+ NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
+ NOTE_SOURCE_FILE (insn) = 0;
+ if (insn == bb->end)
+ purge_dead_edges (bb);
+ }
}
-
- return 1;
}
- return 0;
}
-/* Delete any insns that copy a register to itself. */
-
+/* Delete any jump tables never referenced. We can't delete them at the
+ time of removing tablejump insn as they are referenced by the preceeding
+ insns computing the destination, so we delay deleting and garbagecollect
+ them once life information is computed. */
static void
-delete_noop_moves (f)
- rtx f;
+delete_dead_jumptables ()
{
- rtx insn;
- for (insn = f; insn; insn = NEXT_INSN (insn))
+ rtx insn, next;
+ for (insn = get_insns (); insn; insn = next)
{
- if (GET_CODE (insn) == INSN && noop_move_p (insn))
+ next = NEXT_INSN (insn);
+ if (GET_CODE (insn) == CODE_LABEL
+ && LABEL_NUSES (insn) == 0
+ && GET_CODE (next) == JUMP_INSN
+ && (GET_CODE (PATTERN (next)) == ADDR_VEC
+ || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
{
- PUT_CODE (insn, NOTE);
- NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
- NOTE_SOURCE_FILE (insn) = 0;
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "Dead jumptable %i removed\n", INSN_UID (insn));
+ flow_delete_insn (NEXT_INSN (insn));
+ flow_delete_insn (insn);
+ next = NEXT_INSN (next);
}
}
}
{
/* Mark all call-saved registers that we actually used. */
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
- if (regs_ever_live[i] && ! call_used_regs[i] && ! LOCAL_REGNO (i))
+ if (regs_ever_live[i] && ! LOCAL_REGNO (i)
+ && ! TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
SET_REGNO_REG_SET (set, i);
}
}
if (bb->end == insn)
- bb->end = PREV_INSN (insn);
+ {
+ bb->end = PREV_INSN (insn);
+ purge_dead_edges (bb);
+ }
flow_delete_insn (insn);
}
cond = COND_EXEC_TEST (PATTERN (insn));
/* Non-constant calls clobber memory. */
- if (! CONST_CALL_P (insn))
+ if (! CONST_OR_PURE_CALL_P (insn))
{
free_EXPR_LIST_list (&pbi->mem_set_list);
pbi->mem_set_list_len = 0;
|| (GET_CODE (XEXP (canon_mem, 0)) == PLUS
&& XEXP (XEXP (canon_mem, 0), 0) == frame_pointer_rtx
&& GET_CODE (XEXP (XEXP (canon_mem, 0), 1)) == CONST_INT))
- {
-#ifdef AUTO_INC_DEC
- /* Store a copy of mem, otherwise the address may be scrogged
- by find_auto_inc. This matters because insn_dead_p uses
- an rtx_equal_p check to determine if two addresses are
- the same. This works before find_auto_inc, but fails
- after find_auto_inc, causing discrepencies between the
- set of live registers calculated during the
- calculate_global_regs_live phase and what actually exists
- after flow completes, leading to aborts. */
- if (flags & PROP_AUTOINC)
- mem = shallow_copy_rtx (mem);
-#endif
- pbi->mem_set_list = alloc_EXPR_LIST (0, mem, pbi->mem_set_list);
- if (++pbi->mem_set_list_len >= MAX_MEM_SET_LIST_LEN)
- break;
- }
+ add_to_mem_set_list (pbi, canon_mem);
}
}
and cleared in COND_LOCAL_SET.
It is valid for LOCAL_SET and COND_LOCAL_SET to be the same set. In this
case, the resulting set will be equal to the union of the two sets that
- would otherwise be computed. */
+ would otherwise be computed.
-void
+ Return non-zero if an INSN is deleted (i.e. by dead code removal). */
+
+int
propagate_block (bb, live, local_set, cond_local_set, flags)
basic_block bb;
regset live;
{
struct propagate_block_info *pbi;
rtx insn, prev;
+ int changed;
pbi = init_propagate_block_info (bb, live, local_set, cond_local_set, flags);
/* Scan the block an insn at a time from end to beginning. */
+ changed = 0;
for (insn = bb->end;; insn = prev)
{
/* If this is a call to `setjmp' et al, warn if any
non-volatile datum is live. */
if ((flags & PROP_REG_INFO)
- && GET_CODE (insn) == NOTE
- && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
+ && GET_CODE (insn) == CALL_INSN
+ && find_reg_note (insn, REG_SETJMP, NULL))
IOR_REG_SET (regs_live_at_setjmp, pbi->reg_live);
prev = propagate_one_insn (pbi, insn);
+ changed |= NEXT_INSN (prev) != insn;
if (insn == bb->head)
break;
}
free_propagate_block_info (pbi);
+
+ return changed;
}
\f
/* Return 1 if X (the body of an insn, or part of it) is just dead stores
if (GET_CODE (r) == MEM)
{
- rtx temp;
+ rtx temp, canon_r;
- if (MEM_VOLATILE_P (r))
+ if (MEM_VOLATILE_P (r) || GET_MODE (r) == BLKmode)
return 0;
+ canon_r = canon_rtx (r);
+
/* Walk the set of memory locations we are currently tracking
and see if one is an identical match to this memory location.
If so, this memory write is dead (remember, we're walking
backwards from the end of the block to the start). Since
rtx_equal_p does not check the alias set or flags, we also
- must have the potential for them to conflict (anti_dependence). */
+ must have the potential for them to conflict (anti_dependence). */
for (temp = pbi->mem_set_list; temp != 0; temp = XEXP (temp, 1))
if (anti_dependence (r, XEXP (temp, 0)))
{
rtx mem = XEXP (temp, 0);
- if (rtx_equal_p (mem, r))
+ if (rtx_equal_p (XEXP (canon_r, 0), XEXP (mem, 0))
+ && (GET_MODE_SIZE (GET_MODE (canon_r))
+ <= GET_MODE_SIZE (GET_MODE (mem))))
return 1;
+
#ifdef AUTO_INC_DEC
/* Check if memory reference matches an auto increment. Only
post increment/decrement or modify are valid. */
if (x)
{
register rtx r = SET_SRC (x);
+
if (GET_CODE (r) == REG)
{
rtx call = XEXP (note, 0);
&& REGNO_REG_SET_P (regs_live_at_setjmp, regno));
}
\f
+/* Add MEM to PBI->MEM_SET_LIST. MEM should be canonical. Respect the
+ maximal list size; look for overlaps in mode and select the largest. */
+static void
+add_to_mem_set_list (pbi, mem)
+ struct propagate_block_info *pbi;
+ rtx mem;
+{
+ rtx i;
+
+ /* We don't know how large a BLKmode store is, so we must not
+ take them into consideration. */
+ if (GET_MODE (mem) == BLKmode)
+ return;
+
+ for (i = pbi->mem_set_list; i ; i = XEXP (i, 1))
+ {
+ rtx e = XEXP (i, 0);
+ if (rtx_equal_p (XEXP (mem, 0), XEXP (e, 0)))
+ {
+ if (GET_MODE_SIZE (GET_MODE (mem)) > GET_MODE_SIZE (GET_MODE (e)))
+ {
+#ifdef AUTO_INC_DEC
+ /* If we must store a copy of the mem, we can just modify
+ the mode of the stored copy. */
+ if (pbi->flags & PROP_AUTOINC)
+ PUT_MODE (e, GET_MODE (mem));
+ else
+#endif
+ XEXP (i, 0) = mem;
+ }
+ return;
+ }
+ }
+
+ if (pbi->mem_set_list_len < MAX_MEM_SET_LIST_LEN)
+ {
+#ifdef AUTO_INC_DEC
+ /* Store a copy of mem, otherwise the address may be
+ scrogged by find_auto_inc. */
+ if (pbi->flags & PROP_AUTOINC)
+ mem = shallow_copy_rtx (mem);
+#endif
+ pbi->mem_set_list = alloc_EXPR_LIST (0, mem, pbi->mem_set_list);
+ pbi->mem_set_list_len++;
+ }
+}
+
/* INSN references memory, possibly using autoincrement addressing modes.
Find any entries on the mem_set_list that need to be invalidated due
to an address change. */
{
rtx note = REG_NOTES (insn);
for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
- {
- if (REG_NOTE_KIND (note) == REG_INC)
- {
- rtx temp = pbi->mem_set_list;
- rtx prev = NULL_RTX;
- rtx next;
-
- while (temp)
- {
- next = XEXP (temp, 1);
- if (reg_overlap_mentioned_p (XEXP (note, 0), XEXP (temp, 0)))
- {
- /* Splice temp out of list. */
- if (prev)
- XEXP (prev, 1) = next;
- else
- pbi->mem_set_list = next;
- free_EXPR_LIST_node (temp);
- pbi->mem_set_list_len--;
- }
- else
- prev = temp;
- temp = next;
- }
- }
- }
+ if (REG_NOTE_KIND (note) == REG_INC)
+ invalidate_mems_from_set (pbi, XEXP (note, 0));
}
-/* EXP is either a MEM or a REG. Remove any dependant entries
- from pbi->mem_set_list. */
+/* EXP is a REG. Remove any dependant entries from pbi->mem_set_list. */
static void
invalidate_mems_from_set (pbi, exp)
while (temp)
{
next = XEXP (temp, 1);
- if ((GET_CODE (exp) == MEM
- && output_dependence (XEXP (temp, 0), exp))
- || (GET_CODE (exp) == REG
- && reg_overlap_mentioned_p (exp, XEXP (temp, 0))))
+ if (reg_overlap_mentioned_p (exp, XEXP (temp, 0)))
{
/* Splice this entry out of the list. */
if (prev)
if (regno_first < FIRST_PSEUDO_REGISTER)
{
regno_first += subreg_regno_offset (regno_first, inner_mode,
- SUBREG_BYTE (reg),
- outer_mode);
+ SUBREG_BYTE (reg),
+ outer_mode);
regno_last = (regno_first
+ HARD_REGNO_NREGS (regno_first, outer_mode) - 1);
If this set is a REG, then it kills any MEMs which use the reg. */
if (optimize && (flags & PROP_SCAN_DEAD_CODE))
{
- if (GET_CODE (reg) == MEM || GET_CODE (reg) == REG)
+ if (GET_CODE (reg) == REG)
invalidate_mems_from_set (pbi, reg);
/* If the memory reference had embedded side effects (autoincrement
if (insn && GET_CODE (reg) == MEM)
invalidate_mems_from_autoinc (pbi, insn);
- if (pbi->mem_set_list_len < MAX_MEM_SET_LIST_LEN
- && GET_CODE (reg) == MEM && ! side_effects_p (reg)
+ if (GET_CODE (reg) == MEM && ! side_effects_p (reg)
/* ??? With more effort we could track conditional memory life. */
&& ! cond
- /* We do not know the size of a BLKmode store, so we do not track
- them for redundant store elimination. */
- && GET_MODE (reg) != BLKmode
/* There are no REG_INC notes for SP, so we can't assume we'll see
everything that invalidates it. To be safe, don't eliminate any
stores though SP; none of them should be redundant anyway. */
&& ! reg_mentioned_p (stack_pointer_rtx, reg))
- {
-#ifdef AUTO_INC_DEC
- /* Store a copy of mem, otherwise the address may be
- scrogged by find_auto_inc. */
- if (flags & PROP_AUTOINC)
- reg = shallow_copy_rtx (reg);
-#endif
- pbi->mem_set_list = alloc_EXPR_LIST (0, reg, pbi->mem_set_list);
- pbi->mem_set_list_len++;
- }
+ add_to_mem_set_list (pbi, canon_rtx (reg));
}
if (GET_CODE (reg) == REG
register twice if it is modified, but that is correct. */
REG_N_SETS (i) += 1;
REG_N_REFS (i) += 1;
- REG_FREQ (i) += (optimize_size || !pbi->bb->frequency
- ? 1 : pbi->bb->frequency);
+ REG_FREQ (i) += REG_FREQ_FROM_BB (pbi->bb);
/* The insns where a reg is live are normally counted
elsewhere, but we want the count to include the insn
/* Count an extra reference to the reg. When a reg is
incremented, spilling it is worse, so we want to make
that less likely. */
- REG_FREQ (regno) += (optimize_size || !pbi->bb->frequency
- ? 1 : pbi->bb->frequency);
+ REG_FREQ (regno) += REG_FREQ_FROM_BB (pbi->bb);
/* Count the increment as a setting of the register,
even though it isn't a SET in rtl. */
REG_BASIC_BLOCK (regno_first) = REG_BLOCK_GLOBAL;
/* Count (weighted) number of uses of each reg. */
- REG_FREQ (regno_first)
- += (optimize_size || !pbi->bb->frequency ? 1 : pbi->bb->frequency);
+ REG_FREQ (regno_first) += REG_FREQ_FROM_BB (pbi->bb);
REG_N_REFS (regno_first)++;
}
}
/* Recursively scan the operands of this expression. */
{
- register const char *fmt = GET_RTX_FORMAT (code);
+ register const char * const fmt = GET_RTX_FORMAT (code);
register int i;
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
so we want to make that less likely. */
if (regno >= FIRST_PSEUDO_REGISTER)
{
- REG_FREQ (regno) += (optimize_size || !pbi->bb->frequency
- ? 1 : pbi->bb->frequency);
+ REG_FREQ (regno) += REG_FREQ_FROM_BB (pbi->bb);
REG_N_SETS (regno)++;
}
HOST_WIDE_INT plusconst;
{
enum rtx_code code = GET_CODE (x);
- const char *fmt = GET_RTX_FORMAT (code);
+ const char * const fmt = GET_RTX_FORMAT (code);
register int i;
register rtx value = 0;
register rtx tem;
if (e->flags)
{
static const char * const bitnames[] = {
- "fallthru", "crit", "ab", "abcall", "eh", "fake"
+ "fallthru", "crit", "ab", "abcall", "eh", "fake", "dfs_back"
};
int comma = 0;
int i, flags = e->flags;
/* When a new insn has been inserted into an existing block, it will
sometimes emit more than a single insn. This routine will set the
block number for the specified insn, and look backwards in the insn
- chain to see if there are any other uninitialized insns immediately
+ chain to see if there are any other uninitialized insns immediately
previous to this one, and set the block number for them too. */
void
{
set_block_for_insn (insn, bb);
- /* Scan the previous instructions setting the block number until we find
- an instruction that has the block number set, or we find a note
+ /* Scan the previous instructions setting the block number until we find
+ an instruction that has the block number set, or we find a note
of any kind. */
for (insn = PREV_INSN (insn); insn != NULL_RTX; insn = PREV_INSN (insn))
{
if (GET_CODE (insn) == NOTE)
break;
- if (INSN_UID (insn) >= basic_block_for_insn->num_elements
+ if ((unsigned) INSN_UID (insn) >= basic_block_for_insn->num_elements
|| BLOCK_FOR_INSN (insn) == 0)
set_block_for_insn (insn, bb);
else
- test head/end pointers
- overlapping of basic blocks
- - edge list corectness
+ - edge list correctness
- headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
- tails of basic blocks (ensure that boundary is necesary)
- scans body of the basic block for JUMP_INSN, CODE_LABEL
const int max_uid = get_max_uid ();
const rtx rtx_first = get_insns ();
rtx last_head = get_last_insn ();
- basic_block *bb_info;
+ basic_block *bb_info, *last_visited;
+ size_t *edge_checksum;
rtx x;
int i, last_bb_num_seen, num_bb_notes, err = 0;
bb_info = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
+ last_visited = (basic_block *) xcalloc (n_basic_blocks + 2,
+ sizeof (basic_block));
+ edge_checksum = (size_t *) xcalloc (n_basic_blocks + 2, sizeof (size_t));
for (i = n_basic_blocks - 1; i >= 0; i--)
{
for (i = n_basic_blocks - 1; i >= 0; i--)
{
basic_block bb = BASIC_BLOCK (i);
- /* Check corectness of edge lists */
+ int has_fallthru = 0;
edge e;
e = bb->succ;
while (e)
{
- if ((e->flags & EDGE_FALLTHRU)
- && e->src != ENTRY_BLOCK_PTR
- && e->dest != EXIT_BLOCK_PTR
- && (e->src->index + 1 != e->dest->index
- || !can_fallthru (e->src, e->dest)))
+ if (last_visited [e->dest->index + 2] == bb)
{
- error ("verify_flow_info: Incorrect fallthru edge %i->%i",
+ error ("verify_flow_info: Duplicate edge %i->%i",
e->src->index, e->dest->index);
err = 1;
}
-
+ last_visited [e->dest->index + 2] = bb;
+
+ if (e->flags & EDGE_FALLTHRU)
+ has_fallthru = 1;
+
+ if ((e->flags & EDGE_FALLTHRU)
+ && e->src != ENTRY_BLOCK_PTR
+ && e->dest != EXIT_BLOCK_PTR)
+ {
+ rtx insn;
+ if (e->src->index + 1 != e->dest->index)
+ {
+ error ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
+ e->src->index, e->dest->index);
+ err = 1;
+ }
+ else
+ for (insn = NEXT_INSN (e->src->end); insn != e->dest->head;
+ insn = NEXT_INSN (insn))
+ if (GET_CODE (insn) == BARRIER || INSN_P (insn))
+ {
+ error ("verify_flow_info: Incorrect fallthru %i->%i",
+ e->src->index, e->dest->index);
+ fatal_insn ("Wrong insn in the fallthru edge", insn);
+ err = 1;
+ }
+ }
if (e->src != bb)
{
error ("verify_flow_info: Basic block %d succ edge is corrupted",
fprintf (stderr, "\n");
err = 1;
}
- if (e->dest != EXIT_BLOCK_PTR)
- {
- edge e2 = e->dest->pred;
- while (e2 && e2 != e)
- e2 = e2->pred_next;
- if (!e2)
+ edge_checksum[e->dest->index + 2] += (size_t) e;
+ e = e->succ_next;
+ }
+ if (!has_fallthru)
+ {
+ rtx insn = bb->end;
+
+ /* Ensure existence of barrier in BB with no fallthru edges. */
+ for (insn = bb->end; GET_CODE (insn) != BARRIER;
+ insn = NEXT_INSN (insn))
+ if (!insn
+ || (GET_CODE (insn) == NOTE
+ && NOTE_LINE_NUMBER (insn) == NOTE_INSN_BASIC_BLOCK))
{
- error ("Basic block %i edge lists are corrupted", bb->index);
+ error ("Missing barrier after block %i", bb->index);
err = 1;
}
- }
- e = e->succ_next;
}
e = bb->pred;
fputc ('\n', stderr);
err = 1;
}
- if (e->src != ENTRY_BLOCK_PTR)
- {
- edge e2 = e->src->succ;
- while (e2 && e2 != e)
- e2 = e2->succ_next;
- if (!e2)
- {
- error ("Basic block %i edge lists are corrupted", bb->index);
- err = 1;
- }
- }
+ edge_checksum[e->dest->index + 2] -= (size_t) e;
e = e->pred_next;
}
}
if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
{
- error ("NOTE_INSN_BASIC_BLOCK is missing for block %d\n",
+ error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
bb->index);
err = 1;
}
}
}
+ /* Complete edge checksumming for ENTRY and EXIT. */
+ {
+ edge e;
+ for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next)
+ edge_checksum[e->dest->index + 2] += (size_t) e;
+ for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next)
+ edge_checksum[e->dest->index + 2] -= (size_t) e;
+ }
+
+ for (i = -2; i < n_basic_blocks; ++i)
+ if (edge_checksum[i + 2])
+ {
+ error ("Basic block %i edge lists are corrupted", i);
+ err = 1;
+ }
+
last_bb_num_seen = -1;
num_bb_notes = 0;
x = rtx_first;
basic_block bb = NOTE_BASIC_BLOCK (x);
num_bb_notes++;
if (bb->index != last_bb_num_seen + 1)
- /* Basic blocks not numbered consecutively. */
- abort ();
-
+ internal_error ("Basic blocks not numbered consecutively.");
+
last_bb_num_seen = bb->index;
}
num_bb_notes, n_basic_blocks);
if (err)
- abort ();
+ internal_error ("verify_flow_info failed.");
/* Clean up. */
free (bb_info);
+ free (last_visited);
+ free (edge_checksum);
}
\f
/* Functions to access an edge list with a vector representation.
e->dest = new_succ;
}
+/* Like previous but avoid possible dupplicate edge. */
+
+edge
+redirect_edge_succ_nodup (e, new_succ)
+ edge e;
+ basic_block new_succ;
+{
+ edge s;
+ /* Check whether the edge is already present. */
+ for (s = e->src->succ; s; s = s->succ_next)
+ if (s->dest == new_succ && s != e)
+ break;
+ if (s)
+ {
+ s->flags |= e->flags;
+ s->probability += e->probability;
+ s->count += e->count;
+ remove_edge (e);
+ e = s;
+ }
+ else
+ redirect_edge_succ (e, new_succ);
+ return e;
+}
+
/* Redirect an edge's predecessor from one block to another. */
void
if (! loop || ! loop->header)
return;
- fprintf (file, ";;\n;; Loop %d (%d to %d):%s%s\n",
- loop->num, INSN_UID (loop->first->head),
- INSN_UID (loop->last->end),
- loop->shared ? " shared" : "",
- loop->invalid ? " invalid" : "");
+ if (loop->first->head && loop->last->end)
+ fprintf (file, ";;\n;; Loop %d (%d to %d):%s%s\n",
+ loop->num, INSN_UID (loop->first->head),
+ INSN_UID (loop->last->end),
+ loop->shared ? " shared" : "",
+ loop->invalid ? " invalid" : "");
+ else
+ fprintf (file, ";;\n;; Loop %d:%s%s\n", loop->num,
+ loop->shared ? " shared" : "",
+ loop->invalid ? " invalid" : "");
+
fprintf (file, ";; header %d, latch %d, pre-header %d, first %d, last %d\n",
loop->header->index, loop->latch->index,
loop->pre_header ? loop->pre_header->index : -1,
return num_nodes;
}
+/* Compute reverse top sort order */
+void
+flow_reverse_top_sort_order_compute (rts_order)
+ int *rts_order;
+{
+ edge *stack;
+ int sp;
+ int postnum = 0;
+ sbitmap visited;
+
+ /* Allocate stack for back-tracking up CFG. */
+ stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
+ sp = 0;
+
+ /* Allocate bitmap to track nodes that have been visited. */
+ visited = sbitmap_alloc (n_basic_blocks);
+
+ /* None of the nodes in the CFG have been visited yet. */
+ sbitmap_zero (visited);
+
+ /* Push the first edge on to the stack. */
+ stack[sp++] = ENTRY_BLOCK_PTR->succ;
+
+ while (sp)
+ {
+ edge e;
+ basic_block src;
+ basic_block dest;
+
+ /* Look at the edge on the top of the stack. */
+ e = stack[sp - 1];
+ src = e->src;
+ dest = e->dest;
+
+ /* Check if the edge destination has been visited yet. */
+ if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
+ {
+ /* Mark that we have visited the destination. */
+ SET_BIT (visited, dest->index);
+
+ if (dest->succ)
+ {
+ /* Since the DEST node has been visited for the first
+ time, check its successors. */
+ stack[sp++] = dest->succ;
+ }
+ else
+ rts_order[postnum++] = dest->index;
+ }
+ else
+ {
+ if (! e->succ_next && src != ENTRY_BLOCK_PTR)
+ rts_order[postnum++] = src->index;
+
+ if (e->succ_next)
+ stack[sp - 1] = e->succ_next;
+ else
+ sp--;
+ }
+ }
+
+ free (stack);
+ sbitmap_free (visited);
+}
+
/* Compute the depth first search order and store in the array
DFS_ORDER if non-zero, marking the nodes visited in VISITED. If
RC_ORDER is non-zero, return the reverse completion number for each
/* Count number of edges along trace from loop header to
root of pre-header extended basic block. Usually this is
- only one or two edges. */
+ only one or two edges. */
num++;
while (ebb->pred->src != ENTRY_BLOCK_PTR && ! ebb->pred->pred_next)
{
for (j = 0; j < loop->num_exits; j++)
sbitmap_a_and_b (loop->exits_doms, loop->exits_doms,
loops->cfg.dom[loop->exit_edges[j]->src->index]);
-
+
/* The header of a natural loop must dominate
all exits. */
if (! TEST_BIT (loop->exits_doms, loop->header->index))
abort ();
}
-
+
if (flags & LOOP_PRE_HEADER)
{
/* Look to see if the loop has a pre-header node. */
flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0);
}
}
+
+/* Assume that the preceeding pass has possibly eliminated jump instructions
+ or converted the unconditional jumps. Eliminate the edges from CFG.
+ Return true if any edges are eliminated. */
+
+bool
+purge_dead_edges (bb)
+ basic_block bb;
+{
+ edge e, next;
+ rtx insn = bb->end;
+ bool purged = false;
+
+ if (GET_CODE (insn) == JUMP_INSN && !simplejump_p (insn))
+ return false;
+ if (GET_CODE (insn) == JUMP_INSN)
+ {
+ rtx note;
+ edge b,f;
+ /* We do care only about conditional jumps and simplejumps. */
+ if (!any_condjump_p (insn)
+ && !returnjump_p (insn)
+ && !simplejump_p (insn))
+ return false;
+ for (e = bb->succ; e; e = next)
+ {
+ next = e->succ_next;
+
+ /* Check purposes we can have edge. */
+ if ((e->flags & EDGE_FALLTHRU)
+ && any_condjump_p (insn))
+ continue;
+ if (e->dest != EXIT_BLOCK_PTR
+ && e->dest->head == JUMP_LABEL (insn))
+ continue;
+ if (e->dest == EXIT_BLOCK_PTR
+ && returnjump_p (insn))
+ continue;
+ purged = true;
+ remove_edge (e);
+ }
+ if (!bb->succ || !purged)
+ return false;
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "Purged edges from bb %i\n", bb->index);
+ if (!optimize)
+ return purged;
+
+ /* Redistribute probabilities. */
+ if (!bb->succ->succ_next)
+ {
+ bb->succ->probability = REG_BR_PROB_BASE;
+ bb->succ->count = bb->count;
+ }
+ else
+ {
+ note = find_reg_note (insn, REG_BR_PROB, NULL);
+ if (!note)
+ return purged;
+ b = BRANCH_EDGE (bb);
+ f = FALLTHRU_EDGE (bb);
+ b->probability = INTVAL (XEXP (note, 0));
+ f->probability = REG_BR_PROB_BASE - b->probability;
+ b->count = bb->count * b->probability / REG_BR_PROB_BASE;
+ f->count = bb->count * f->probability / REG_BR_PROB_BASE;
+ }
+ return purged;
+ }
+
+ /* Cleanup abnormal edges caused by throwing insns that have been
+ eliminated. */
+ if (! can_throw_internal (bb->end))
+ for (e = bb->succ; e; e = next)
+ {
+ next = e->succ_next;
+ if (e->flags & EDGE_EH)
+ {
+ remove_edge (e);
+ purged = true;
+ }
+ }
+
+ /* If we don't see a jump insn, we don't know exactly why the block would
+ have been broken at this point. Look for a simple, non-fallthru edge,
+ as these are only created by conditional branches. If we find such an
+ edge we know that there used to be a jump here and can then safely
+ remove all non-fallthru edges. */
+ for (e = bb->succ; e && (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU));
+ e = e->succ_next);
+ if (!e)
+ return purged;
+ for (e = bb->succ; e; e = next)
+ {
+ next = e->succ_next;
+ if (!(e->flags & EDGE_FALLTHRU))
+ remove_edge (e), purged = true;
+ }
+ if (!bb->succ || bb->succ->succ_next)
+ abort ();
+ bb->succ->probability = REG_BR_PROB_BASE;
+ bb->succ->count = bb->count;
+
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "Purged non-fallthru edges from bb %i\n",
+ bb->index);
+ return purged;
+}
+
+/* Search all basic blocks for potentionally dead edges and purge them.
+
+ Return true ifif some edge has been elliminated.
+ */
+
+bool
+purge_all_dead_edges ()
+{
+ int i, purged = false;
+ for (i = 0; i < n_basic_blocks; i++)
+ purged |= purge_dead_edges (BASIC_BLOCK (i));
+ return purged;
+}
OSDN Git Service
