/* Control flow graph manipulation code for GNU compiler.
Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
- 1999, 2000, 2001 Free Software Foundation, Inc.
+ 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
This file is part of GCC.
Software Foundation, 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA. */
-/* This file contains low level functions to manipulate with CFG and analyze it
- that are aware of RTL intermediate language.
+/* This file contains low level functions to manipulate the CFG and analyze it
+ that are aware of the RTL intermediate language.
Available functionality:
- - CFG aware instruction chain manipulation
+ - CFG-aware instruction chain manipulation
delete_insn, delete_insn_chain
- Basic block manipulation
- create_basic_block, flow_delete_block, split_block, merge_blocks_nomove
- - Infrastructure to determine quickly basic block for instruction.
+ create_basic_block, flow_delete_block, split_block,
+ merge_blocks_nomove
+ - Infrastructure to determine quickly basic block for insn
compute_bb_for_insn, update_bb_for_insn, set_block_for_insn,
- - Edge redirection with updating and optimizing instruction chain
- block_label, redirect_edge_and_branch,
- redirect_edge_and_branch_force, tidy_fallthru_edge, force_nonfallthru
+ - Edge redirection with updating and optimizing of insn chain
+ block_label, redirect_edge_and_branch,
+ redirect_edge_and_branch_force, tidy_fallthru_edge, force_nonfallthru
- Edge splitting and commiting to edges
- split_edge, insert_insn_on_edge, commit_edge_insertions
- - Dumpipng and debugging
- print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n
+ split_edge, insert_insn_on_edge, commit_edge_insertions
+ - Dumping and debugging
+ print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n
- Consistency checking
- verify_flow_info
+ verify_flow_info
- CFG updating after constant propagation
- purge_dead_edges, purge_all_dead_edges
- */
+ purge_dead_edges, purge_all_dead_edges */
\f
#include "config.h"
#include "system.h"
#include "toplev.h"
#include "tm_p.h"
#include "obstack.h"
+#include "insn-config.h"
-/* Stubs in case we haven't got a return insn. */
+/* Stubs in case we don't have a return insn. */
#ifndef HAVE_return
#define HAVE_return 0
#define gen_return() NULL_RTX
#endif
/* The basic block structure for every insn, indexed by uid. */
-
varray_type basic_block_for_insn;
/* The labels mentioned in non-jump rtl. Valid during find_basic_blocks. */
/* ??? Should probably be using LABEL_NUSES instead. It would take a
bit of surgery to be able to use or co-opt the routines in jump. */
-
rtx label_value_list;
rtx tail_recursion_label_list;
static int can_delete_note_p PARAMS ((rtx));
static int can_delete_label_p PARAMS ((rtx));
-static void commit_one_edge_insertion PARAMS ((edge));
+static void commit_one_edge_insertion PARAMS ((edge, int));
static bool try_redirect_by_replacing_jump PARAMS ((edge, basic_block));
static rtx last_loop_beg_note PARAMS ((rtx));
static bool back_edge_of_syntactic_loop_p PARAMS ((basic_block, basic_block));
static basic_block force_nonfallthru_and_redirect PARAMS ((edge, basic_block));
\f
/* Return true if NOTE is not one of the ones that must be kept paired,
- so that we may simply delete them. */
+ so that we may simply delete it. */
static int
can_delete_note_p (note)
rtx note;
{
return (NOTE_LINE_NUMBER (note) == NOTE_INSN_DELETED
- || NOTE_LINE_NUMBER (note) == NOTE_INSN_BASIC_BLOCK);
+ || NOTE_LINE_NUMBER (note) == NOTE_INSN_BASIC_BLOCK
+ || NOTE_LINE_NUMBER (note) == NOTE_INSN_PREDICTION);
}
/* True if a given label can be deleted. */
can_delete_label_p (label)
rtx label;
{
- rtx x;
-
- if (LABEL_PRESERVE_P (label))
- return 0;
-
- for (x = forced_labels; x; x = XEXP (x, 1))
- if (label == XEXP (x, 0))
- return 0;
- for (x = label_value_list; x; x = XEXP (x, 1))
- if (label == XEXP (x, 0))
- return 0;
- for (x = exception_handler_labels; x; x = XEXP (x, 1))
- if (label == XEXP (x, 0))
- return 0;
-
- /* User declared labels must be preserved. */
- if (LABEL_NAME (label) != 0)
- return 0;
-
- return 1;
+ return (!LABEL_PRESERVE_P (label)
+ /* User declared labels must be preserved. */
+ && LABEL_NAME (label) == 0
+ && !in_expr_list_p (forced_labels, label)
+ && !in_expr_list_p (label_value_list, label));
}
/* Delete INSN by patching it out. Return the next insn. */
if (GET_CODE (insn) == CODE_LABEL)
{
/* Some labels can't be directly removed from the INSN chain, as they
- might be references via variables, constant pool etc.
+ might be references via variables, constant pool etc.
Convert them to the special NOTE_INSN_DELETED_LABEL note. */
if (! can_delete_label_p (insn))
{
NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED_LABEL;
NOTE_SOURCE_FILE (insn) = name;
}
+
remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels);
}
if (really_delete)
{
+ /* If this insn has already been deleted, something is very wrong. */
+ if (INSN_DELETED_P (insn))
+ abort ();
remove_insn (insn);
INSN_DELETED_P (insn) = 1;
}
int i;
for (i = 0; i < len; i++)
- LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0))--;
+ {
+ rtx label = XEXP (XVECEXP (pat, diff_vec_p, i), 0);
+
+ /* When deleting code in bulk (e.g. removing many unreachable
+ blocks) we can delete a label that's a target of the vector
+ before deleting the vector itself. */
+ if (GET_CODE (label) != NOTE)
+ LABEL_NUSES (label)--;
+ }
}
return next;
}
+/* Like delete_insn but also purge dead edges from BB. */
+rtx
+delete_insn_and_edges (insn)
+ rtx insn;
+{
+ rtx x;
+ bool purge = false;
+
+ if (basic_block_for_insn
+ && INSN_P (insn)
+ && (unsigned int)INSN_UID (insn) < basic_block_for_insn->num_elements
+ && BLOCK_FOR_INSN (insn)
+ && BLOCK_FOR_INSN (insn)->end == insn)
+ purge = true;
+ x = delete_insn (insn);
+ if (purge)
+ purge_dead_edges (BLOCK_FOR_INSN (insn));
+ return x;
+}
+
/* Unlink a chain of insns between START and FINISH, leaving notes
that must be paired. */
delete_insn_chain (start, finish)
rtx start, finish;
{
- /* Unchain the insns one by one. It would be quicker to delete all
- of these with a single unchaining, rather than one at a time, but
- we need to keep the NOTE's. */
-
rtx next;
+ /* Unchain the insns one by one. It would be quicker to delete all of these
+ with a single unchaining, rather than one at a time, but we need to keep
+ the NOTE's. */
while (1)
{
next = NEXT_INSN (start);
start = next;
}
}
+
+/* Like delete_insn but also purge dead edges from BB. */
+void
+delete_insn_chain_and_edges (first, last)
+ rtx first, last;
+{
+ bool purge = false;
+
+ if (basic_block_for_insn
+ && INSN_P (last)
+ && (unsigned int)INSN_UID (last) < basic_block_for_insn->num_elements
+ && BLOCK_FOR_INSN (last)
+ && BLOCK_FOR_INSN (last)->end == last)
+ purge = true;
+ delete_insn_chain (first, last);
+ if (purge)
+ purge_dead_edges (BLOCK_FOR_INSN (last));
+}
\f
-/* Create a new basic block consisting of the instructions between
- HEAD and END inclusive. This function is designed to allow fast
- BB construction - reuses the note and basic block struct
- in BB_NOTE, if any and do not grow BASIC_BLOCK chain and should
- be used directly only by CFG construction code.
- END can be NULL in to create new empty basic block before HEAD.
- Both END and HEAD can be NULL to create basic block at the end of
- INSN chain. */
+/* Create a new basic block consisting of the instructions between HEAD and END
+ inclusive. This function is designed to allow fast BB construction - reuses
+ the note and basic block struct in BB_NOTE, if any and do not grow
+ BASIC_BLOCK chain and should be used directly only by CFG construction code.
+ END can be NULL in to create new empty basic block before HEAD. Both END
+ and HEAD can be NULL to create basic block at the end of INSN chain.
+ AFTER is the basic block we should be put after. */
basic_block
-create_basic_block_structure (index, head, end, bb_note)
+create_basic_block_structure (index, head, end, bb_note, after)
int index;
rtx head, end, bb_note;
+ basic_block after;
{
basic_block bb;
bb = alloc_block ();
if (!head && !end)
- {
- head = end = bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK,
- get_last_insn ());
- }
+ head = end = bb_note
+ = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
else if (GET_CODE (head) == CODE_LABEL && end)
{
bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
if (!end)
end = head;
}
+
NOTE_BASIC_BLOCK (bb_note) = bb;
}
bb->head = head;
bb->end = end;
bb->index = index;
+ bb->flags = BB_NEW;
+ link_block (bb, after);
BASIC_BLOCK (index) = bb;
if (basic_block_for_insn)
update_bb_for_insn (bb);
return bb;
}
-/* Create new basic block consisting of instructions in between HEAD and
- END and place it to the BB chain at possition INDEX.
- END can be NULL in to create new empty basic block before HEAD.
- Both END and HEAD can be NULL to create basic block at the end of
- INSN chain. */
+/* Create new basic block consisting of instructions in between HEAD and END
+ and place it to the BB chain after block AFTER. END can be NULL in to
+ create new empty basic block before HEAD. Both END and HEAD can be NULL to
+ create basic block at the end of INSN chain. */
basic_block
-create_basic_block (index, head, end)
- int index;
+create_basic_block (head, end, after)
rtx head, end;
+ basic_block after;
{
basic_block bb;
- int i;
+ int index = last_basic_block++;
- /* Place the new block just after the block being split. */
- VARRAY_GROW (basic_block_info, ++n_basic_blocks);
+ /* Place the new block just after the end. */
+ VARRAY_GROW (basic_block_info, last_basic_block);
- /* Some parts of the compiler expect blocks to be number in
- sequential order so insert the new block immediately after the
- block being split.. */
- for (i = n_basic_blocks - 1; i > index; --i)
- {
- basic_block tmp = BASIC_BLOCK (i - 1);
- BASIC_BLOCK (i) = tmp;
- tmp->index = i;
- }
+ n_basic_blocks++;
- bb = create_basic_block_structure (index, head, end, NULL);
+ bb = create_basic_block_structure (index, head, end, NULL, after);
bb->aux = NULL;
return bb;
}
to post-process the stream to remove empty blocks, loops, ranges, etc. */
int
-flow_delete_block (b)
+flow_delete_block_noexpunge (b)
basic_block b;
{
int deleted_handler = 0;
and remove the associated NOTE_INSN_EH_REGION_BEG and
NOTE_INSN_EH_REGION_END notes. */
+ /* Get rid of all NOTE_INSN_PREDICTIONs hanging before the block. */
+
+ for (insn = PREV_INSN (b->head); insn; insn = PREV_INSN (insn))
+ {
+ if (GET_CODE (insn) != NOTE)
+ break;
+ if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_PREDICTION)
+ NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
+ }
+
insn = b->head;
- never_reached_warning (insn);
+ never_reached_warning (insn, b->end);
if (GET_CODE (insn) == CODE_LABEL)
maybe_remove_eh_handler (insn);
b->pred = NULL;
b->succ = NULL;
- /* Remove the basic block from the array, and compact behind it. */
+ return deleted_handler;
+}
+
+int
+flow_delete_block (b)
+ basic_block b;
+{
+ int deleted_handler = flow_delete_block_noexpunge (b);
+
+ /* Remove the basic block from the array. */
expunge_block (b);
return deleted_handler;
compute_bb_for_insn (max)
int max;
{
- int i;
+ basic_block bb;
if (basic_block_for_insn)
VARRAY_FREE (basic_block_for_insn);
+
VARRAY_BB_INIT (basic_block_for_insn, max, "basic_block_for_insn");
- for (i = 0; i < n_basic_blocks; ++i)
+ FOR_EACH_BB (bb)
{
- basic_block bb = BASIC_BLOCK (i);
- rtx insn, end;
+ rtx end = bb->end;
+ rtx insn;
- end = bb->end;
- insn = bb->head;
- while (1)
+ for (insn = bb->head; ; insn = NEXT_INSN (insn))
{
- int uid = INSN_UID (insn);
- if (uid < max)
- VARRAY_BB (basic_block_for_insn, uid) = bb;
+ if (INSN_UID (insn) < max)
+ VARRAY_BB (basic_block_for_insn, INSN_UID (insn)) = bb;
+
if (insn == end)
break;
- insn = NEXT_INSN (insn);
}
}
}
{
if (basic_block_for_insn)
VARRAY_FREE (basic_block_for_insn);
+
basic_block_for_insn = 0;
}
for (insn = bb->head; ; insn = NEXT_INSN (insn))
{
set_block_for_insn (insn, bb);
-
if (insn == bb->end)
break;
}
basic_block bb;
{
size_t uid = INSN_UID (insn);
+
if (uid >= basic_block_for_insn->num_elements)
{
- int new_size;
-
/* Add one-eighth the size so we don't keep calling xrealloc. */
- new_size = uid + (uid + 7) / 8;
+ size_t new_size = uid + (uid + 7) / 8;
VARRAY_GROW (basic_block_for_insn, new_size);
}
+
VARRAY_BB (basic_block_for_insn, uid) = bb;
}
\f
return 0;
/* Create the new basic block. */
- new_bb = create_basic_block (bb->index + 1, NEXT_INSN (insn), bb->end);
+ new_bb = create_basic_block (NEXT_INSN (insn), bb->end, bb);
new_bb->count = bb->count;
new_bb->frequency = bb->frequency;
new_bb->loop_depth = bb->loop_depth;
propagate_block (new_bb, new_bb->global_live_at_start, NULL, NULL, 0);
COPY_REG_SET (bb->global_live_at_end,
new_bb->global_live_at_start);
+#ifdef HAVE_conditional_execution
+ /* In the presence of conditional execution we are not able to update
+ liveness precisely. */
+ if (reload_completed)
+ {
+ bb->flags |= BB_DIRTY;
+ new_bb->flags |= BB_DIRTY;
+ }
+#endif
}
return new_edge;
merge_blocks_nomove (a, b)
basic_block a, b;
{
- edge e;
- rtx b_head, b_end, a_end;
+ rtx b_head = b->head, b_end = b->end, a_end = a->end;
rtx del_first = NULL_RTX, del_last = NULL_RTX;
int b_empty = 0;
+ edge e;
/* If there was a CODE_LABEL beginning B, delete it. */
- b_head = b->head;
- b_end = b->end;
if (GET_CODE (b_head) == CODE_LABEL)
{
/* Detect basic blocks with nothing but a label. This can happen
in particular at the end of a function. */
if (b_head == b_end)
b_empty = 1;
+
del_first = del_last = b_head;
b_head = NEXT_INSN (b_head);
}
- /* Delete the basic block note. */
+ /* Delete the basic block note and handle blocks containing just that
+ note. */
if (NOTE_INSN_BASIC_BLOCK_P (b_head))
{
if (b_head == b_end)
b_empty = 1;
if (! del_last)
del_first = b_head;
+
del_last = b_head;
b_head = NEXT_INSN (b_head);
}
/* If there was a jump out of A, delete it. */
- a_end = a->end;
if (GET_CODE (a_end) == JUMP_INSN)
{
rtx prev;
if (only_sets_cc0_p (prev))
{
rtx tmp = prev;
+
prev = prev_nonnote_insn (prev);
if (!prev)
prev = a->head;
for (e = b->succ; e; e = e->succ_next)
e->src = a;
a->succ = b->succ;
+ a->flags |= b->flags;
/* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
b->pred = b->succ = NULL;
+ a->global_live_at_end = b->global_live_at_end;
expunge_block (b);
/* Reassociate the insns of B with A. */
if (!b_empty)
{
- rtx x = a_end;
if (basic_block_for_insn)
{
- BLOCK_FOR_INSN (x) = a;
- while (x != b_end)
- {
- x = NEXT_INSN (x);
- BLOCK_FOR_INSN (x) = a;
- }
+ rtx x;
+
+ for (x = a_end; x != b_end; x = NEXT_INSN (x))
+ set_block_for_insn (x, a);
+
+ set_block_for_insn (b_end, a);
}
+
a_end = b_end;
}
+
a->end = a_end;
}
\f
-/* Return label in the head of basic block. Create one if it doesn't exist. */
+/* Return the label in the head of basic block BLOCK. Create one if it doesn't
+ exist. */
rtx
block_label (block)
{
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);
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.
-
- The parameters and return values are equivalent to redirect_edge_and_branch.
- */
+ instruction by unconditional jump or removing jump completely. 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. */
static bool
try_redirect_by_replacing_jump (e, target)
basic_block src = e->src;
rtx insn = src->end, kill_from;
edge tmp;
- rtx set;
+ rtx set, table;
int fallthru = 0;
/* Verify that all targets will be TARGET. */
for (tmp = src->succ; tmp; tmp = tmp->succ_next)
if (tmp->dest != target && tmp != e)
break;
+
if (tmp || !onlyjump_p (insn))
return false;
+ if (reload_completed && JUMP_LABEL (insn)
+ && (table = NEXT_INSN (JUMP_LABEL (insn))) != NULL_RTX
+ && GET_CODE (table) == JUMP_INSN
+ && (GET_CODE (PATTERN (table)) == ADDR_VEC
+ || GET_CODE (PATTERN (table)) == ADDR_DIFF_VEC))
+ return false;
/* Avoid removing branch with side effects. */
set = single_set (insn);
fprintf (rtl_dump_file, "Removing jump %i.\n", INSN_UID (insn));
fallthru = 1;
- /* Selectivly unlink whole insn chain. */
+ /* Selectively unlink whole insn chain. */
delete_insn_chain (kill_from, PREV_INSN (target->head));
}
+
/* If this already is simplejump, redirect it. */
else if (simplejump_p (insn))
{
if (rtl_dump_file)
fprintf (rtl_dump_file, "Redirecting jump %i from %i to %i.\n",
INSN_UID (insn), e->dest->index, target->index);
- redirect_jump (insn, block_label (target), 0);
+ if (!redirect_jump (insn, block_label (target), 0))
+ {
+ if (target == EXIT_BLOCK_PTR)
+ return false;
+ abort ();
+ }
}
+
+ /* Cannot do anything for target exit block. */
+ else if (target == EXIT_BLOCK_PTR)
+ return false;
+
/* Or replace possibly complicated jump insn by simple jump insn. */
else
{
rtx target_label = block_label (target);
- rtx barrier;
+ rtx barrier, tmp;
- emit_jump_insn_after (gen_jump (target_label), kill_from);
+ emit_jump_insn_after (gen_jump (target_label), insn);
JUMP_LABEL (src->end) = target_label;
LABEL_NUSES (target_label)++;
if (rtl_dump_file)
fprintf (rtl_dump_file, "Replacing insn %i by jump %i\n",
INSN_UID (insn), INSN_UID (src->end));
+
delete_insn_chain (kill_from, insn);
+ /* Recognize a tablejump that we are converting to a
+ simple jump and remove its associated CODE_LABEL
+ and ADDR_VEC or ADDR_DIFF_VEC. */
+ 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))
+ {
+ delete_insn_chain (JUMP_LABEL (insn), tmp);
+ }
+
barrier = next_nonnote_insn (src->end);
if (!barrier || GET_CODE (barrier) != BARRIER)
emit_barrier_after (src->end);
e->flags = EDGE_FALLTHRU;
else
e->flags = 0;
+
e->probability = REG_BR_PROB_BASE;
e->count = src->count;
if (e->dest != target)
redirect_edge_succ (e, target);
+
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. */
+ When emitting jump to redirect an fallthru edge, it should always appear
+ after the LOOP_BEG notes, as loop optimizer expect loop to either start by
+ fallthru edge or jump following the LOOP_BEG note jumping to the loop exit
+ test. */
static rtx
last_loop_beg_note (insn)
rtx insn;
{
rtx last = insn;
- insn = NEXT_INSN (insn);
- while (insn && 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);
- }
+
+ for (insn = NEXT_INSN (insn); insn && GET_CODE (insn) == NOTE
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK;
+ insn = NEXT_INSN (insn))
+ if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
+ last = 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.
+/* Attempt to change code to redirect edge E to TARGET. Don't do that on
+ expense of adding new instructions or reordering basic blocks.
- Function can be also called with edge destionation equivalent to the
- TARGET. Then it should try the simplifications and do nothing if
- none is possible.
+ Function can be also called with edge destination equivalent to the TARGET.
+ Then it should try the simplifications and do nothing if none is possible.
- Return true if transformation suceeded. We still return flase in case
- E already destinated TARGET and we didn't managed to simplify instruction
+ Return true if transformation succeeded. We still return false in case E
+ already destinated TARGET and we didn't managed to simplify instruction
stream. */
bool
basic_block src = e->src;
rtx insn = src->end;
- if (e->flags & EDGE_COMPLEX)
+ if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
return false;
if (try_redirect_by_replacing_jump (e, target))
return true;
+
/* Do this fast path late, as we want above code to simplify for cases
where called on single edge leaving basic block containing nontrivial
jump insn. */
/* We can only redirect non-fallthru edges of jump insn. */
if (e->flags & EDGE_FALLTHRU)
return false;
- if (GET_CODE (insn) != JUMP_INSN)
+ else if (GET_CODE (insn) != JUMP_INSN)
return false;
/* Recognize a tablejump and adjust all matching cases. */
int j;
rtx new_label = block_label (target);
+ if (target == EXIT_BLOCK_PTR)
+ return false;
if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
vec = XVEC (PATTERN (tmp), 0);
else
/* ?? We may play the games with moving the named labels from
one basic block to the other in case only one computed_jump is
available. */
- if (computed_jump_p (insn))
- return false;
-
- /* A return instruction can't be redirected. */
- if (returnjump_p (insn))
+ if (computed_jump_p (insn)
+ /* A return instruction can't be redirected. */
+ || returnjump_p (insn))
return false;
/* If the insn doesn't go where we think, we're confused. */
if (JUMP_LABEL (insn) != old_label)
abort ();
- redirect_jump (insn, block_label (target), 0);
+
+ /* If the substitution doesn't succeed, die. This can happen
+ if the back end emitted unrecognizable instructions or if
+ target is exit block on some arches. */
+ if (!redirect_jump (insn, block_label (target), 0))
+ {
+ if (target == EXIT_BLOCK_PTR)
+ return false;
+ abort ();
+ }
}
if (rtl_dump_file)
fprintf (rtl_dump_file, "Edge %i->%i redirected to %i\n",
e->src->index, e->dest->index, target->index);
+
if (e->dest != target)
redirect_edge_succ_nodup (e, target);
+
return true;
}
-/* Like force_nonfallthru bellow, but additionally performs redirection
+/* Like force_nonfallthru below, but additionally performs redirection
Used by redirect_edge_and_branch_force. */
static basic_block
if (e->flags & EDGE_ABNORMAL)
abort ();
- if (!(e->flags & EDGE_FALLTHRU))
+ else if (!(e->flags & EDGE_FALLTHRU))
abort ();
+ else if (e->src == ENTRY_BLOCK_PTR)
+ {
+ /* We can't redirect the entry block. Create an empty block at the
+ start of the function which we use to add the new jump. */
+ edge *pe1;
+ basic_block bb = create_basic_block (e->dest->head, NULL, ENTRY_BLOCK_PTR);
+
+ /* Change the existing edge's source to be the new block, and add
+ a new edge from the entry block to the new block. */
+ e->src = bb;
+ for (pe1 = &ENTRY_BLOCK_PTR->succ; *pe1; pe1 = &(*pe1)->succ_next)
+ if (*pe1 == e)
+ {
+ *pe1 = e->succ_next;
+ break;
+ }
+ e->succ_next = 0;
+ bb->succ = e;
+ make_single_succ_edge (ENTRY_BLOCK_PTR, bb, EDGE_FALLTHRU);
+ }
+
if (e->src->succ->succ_next)
{
/* Create the new structures. */
note = last_loop_beg_note (e->src->end);
- jump_block = create_basic_block (e->src->index + 1, NEXT_INSN (note), NULL);
+ jump_block
+ = create_basic_block (NEXT_INSN (note), NULL, e->src);
jump_block->count = e->count;
jump_block->frequency = EDGE_FREQUENCY (e);
jump_block->loop_depth = target->loop_depth;
if (target->global_live_at_start)
{
- jump_block->global_live_at_start =
- OBSTACK_ALLOC_REG_SET (&flow_obstack);
- jump_block->global_live_at_end =
- OBSTACK_ALLOC_REG_SET (&flow_obstack);
+ jump_block->global_live_at_start
+ = OBSTACK_ALLOC_REG_SET (&flow_obstack);
+ jump_block->global_live_at_end
+ = OBSTACK_ALLOC_REG_SET (&flow_obstack);
COPY_REG_SET (jump_block->global_live_at_start,
target->global_live_at_start);
COPY_REG_SET (jump_block->global_live_at_end,
}
else
jump_block = e->src;
+
e->flags &= ~EDGE_FALLTHRU;
if (target == EXIT_BLOCK_PTR)
{
JUMP_LABEL (jump_block->end) = label;
LABEL_NUSES (label)++;
}
+
emit_barrier_after (jump_block->end);
redirect_edge_succ_nodup (e, target);
/* Edge E is assumed to be fallthru edge. Emit needed jump instruction
(and possibly create new basic block) to make edge non-fallthru.
Return newly created BB or NULL if none. */
+
basic_block
force_nonfallthru (e)
edge e;
/* Redirect edge even at the expense of creating new jump insn or
basic block. Return new basic block if created, NULL otherwise.
- Abort if converison is impossible. */
+ Abort if conversion is impossible. */
basic_block
redirect_edge_and_branch_force (e, target)
edge e;
basic_block target;
{
- basic_block new_bb;
-
- if (redirect_edge_and_branch (e, target))
- return NULL;
- if (e->dest == target)
+ if (redirect_edge_and_branch (e, target)
+ || e->dest == target)
return NULL;
/* In case the edge redirection failed, try to force it to be non-fallthru
and redirect newly created simplejump. */
- new_bb = force_nonfallthru_and_redirect (e, target);
- return new_bb;
+ return force_nonfallthru_and_redirect (e, target);
}
/* The given edge should potentially be a fallthru edge. If that is in
So search through a sequence of barriers, labels, and notes for
the head of block C and assert that we really do fall through. */
- if (next_real_insn (b->end) != next_real_insn (PREV_INSN (c->head)))
- return;
+ for (q = NEXT_INSN (b->end); q != c->head; q = NEXT_INSN (q))
+ if (INSN_P (q))
+ return;
/* Remove what will soon cease being the jump insn from the source block.
If block B consisted only of this single jump, turn it into a deleted
void
tidy_fallthru_edges ()
{
- int i;
+ basic_block b, c;
+
+ if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
+ return;
- for (i = 1; i < n_basic_blocks; ++i)
+ FOR_BB_BETWEEN (b, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, next_bb)
{
- basic_block b = BASIC_BLOCK (i - 1);
- basic_block c = BASIC_BLOCK (i);
edge s;
+ c = b->next_bb;
+
/* We care about simple conditional or unconditional jumps with
a single successor.
Furthermore, the edge will be marked as a fallthru because we
merge the flags for the duplicate edges. So we do not want to
check that the edge is not a FALLTHRU edge. */
+
if ((s = b->succ) != NULL
&& ! (s->flags & EDGE_COMPLEX)
&& s->succ_next == NULL
{
rtx insn;
int count = 0;
+ basic_block bb;
- if (bb1->index > bb2->index)
- return false;
-
- if (bb1->index == bb2->index)
+ if (bb1 == bb2)
return true;
+ /* ??? Could we guarantee that bb indices are monotone, so that we could
+ just compare them? */
+ for (bb = bb1; bb && bb != bb2; bb = bb->next_bb)
+ continue;
+
+ if (!bb)
+ return false;
+
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)
+ else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
count--;
}
abort ();
/* We are going to place the new block in front of edge destination.
- Avoid existence of fallthru predecesors. */
+ Avoid existence of fallthru predecessors. */
if ((edge_in->flags & EDGE_FALLTHRU) == 0)
{
edge e;
+
for (e = edge_in->dest->pred; e; e = e->pred_next)
if (e->flags & EDGE_FALLTHRU)
break;
/* Create the basic block note.
- Where we place the note can have a noticable impact on the generated
+ Where we place the note can have a noticeable impact on the generated
code. Consider this cfg:
E
if (edge_in->dest != EXIT_BLOCK_PTR
&& PREV_INSN (edge_in->dest->head)
&& GET_CODE (PREV_INSN (edge_in->dest->head)) == NOTE
- && NOTE_LINE_NUMBER (PREV_INSN (edge_in->dest->head)) == NOTE_INSN_LOOP_BEG
+ && (NOTE_LINE_NUMBER (PREV_INSN (edge_in->dest->head))
+ == NOTE_INSN_LOOP_BEG)
&& !back_edge_of_syntactic_loop_p (edge_in->dest, edge_in->src))
before = PREV_INSN (edge_in->dest->head);
else if (edge_in->dest != EXIT_BLOCK_PTR)
else
before = NULL_RTX;
- bb = create_basic_block (edge_in->dest == EXIT_BLOCK_PTR ? n_basic_blocks
- : edge_in->dest->index, before, NULL);
+ bb = create_basic_block (before, NULL, edge_in->dest->prev_bb);
bb->count = edge_in->count;
bb->frequency = EDGE_FREQUENCY (edge_in);
{
bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
- COPY_REG_SET (bb->global_live_at_start, edge_in->dest->global_live_at_start);
- COPY_REG_SET (bb->global_live_at_end, edge_in->dest->global_live_at_start);
+ COPY_REG_SET (bb->global_live_at_start,
+ edge_in->dest->global_live_at_start);
+ COPY_REG_SET (bb->global_live_at_end,
+ edge_in->dest->global_live_at_start);
}
edge_out = make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
/* Update the CFG for the instructions queued on edge E. */
static void
-commit_one_edge_insertion (e)
+commit_one_edge_insertion (e, watch_calls)
edge e;
+ int watch_calls;
{
rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last;
basic_block bb;
insns = e->insns;
e->insns = NULL_RTX;
- /* Figure out where to put these things. If the destination has
- one predecessor, insert there. Except for the exit block. */
- if (e->dest->pred->pred_next == NULL
- && e->dest != EXIT_BLOCK_PTR)
+ /* Special case -- avoid inserting code between call and storing
+ its return value. */
+ if (watch_calls && (e->flags & EDGE_FALLTHRU) && !e->dest->pred->pred_next
+ && e->src != ENTRY_BLOCK_PTR
+ && GET_CODE (e->src->end) == CALL_INSN)
{
- bb = e->dest;
+ rtx next = next_nonnote_insn (e->src->end);
- /* Get the location correct wrt a code label, and "nice" wrt
- a basic block note, and before everything else. */
- tmp = bb->head;
- if (GET_CODE (tmp) == CODE_LABEL)
- tmp = NEXT_INSN (tmp);
- if (NOTE_INSN_BASIC_BLOCK_P (tmp))
- tmp = NEXT_INSN (tmp);
- if (tmp == bb->head)
- before = tmp;
- else
- after = PREV_INSN (tmp);
+ after = e->dest->head;
+ /* The first insn after the call may be a stack pop, skip it. */
+ while (next
+ && keep_with_call_p (next))
+ {
+ after = next;
+ next = next_nonnote_insn (next);
+ }
+ bb = e->dest;
}
-
- /* If the source has one successor and the edge is not abnormal,
- insert there. Except for the entry block. */
- else if ((e->flags & EDGE_ABNORMAL) == 0
- && e->src->succ->succ_next == NULL
- && e->src != ENTRY_BLOCK_PTR)
+ if (!before && !after)
{
- bb = e->src;
- /* It is possible to have a non-simple jump here. Consider a target
- where some forms of unconditional jumps clobber a register. This
- happens on the fr30 for example.
-
- We know this block has a single successor, so we can just emit
- the queued insns before the jump. */
- if (GET_CODE (bb->end) == JUMP_INSN)
+ /* Figure out where to put these things. If the destination has
+ one predecessor, insert there. Except for the exit block. */
+ if (e->dest->pred->pred_next == NULL && e->dest != EXIT_BLOCK_PTR)
{
- before = bb->end;
- while (GET_CODE (PREV_INSN (before)) == NOTE
- && NOTE_LINE_NUMBER (PREV_INSN (before)) == NOTE_INSN_LOOP_BEG)
- before = PREV_INSN (before);
+ bb = e->dest;
+
+ /* Get the location correct wrt a code label, and "nice" wrt
+ a basic block note, and before everything else. */
+ tmp = bb->head;
+ if (GET_CODE (tmp) == CODE_LABEL)
+ tmp = NEXT_INSN (tmp);
+ if (NOTE_INSN_BASIC_BLOCK_P (tmp))
+ tmp = NEXT_INSN (tmp);
+ if (tmp == bb->head)
+ before = tmp;
+ else if (tmp)
+ after = PREV_INSN (tmp);
+ else
+ after = get_last_insn ();
}
- else
+
+ /* If the source has one successor and the edge is not abnormal,
+ insert there. Except for the entry block. */
+ else if ((e->flags & EDGE_ABNORMAL) == 0
+ && e->src->succ->succ_next == NULL
+ && e->src != ENTRY_BLOCK_PTR)
{
- /* We'd better be fallthru, or we've lost track of what's what. */
- if ((e->flags & EDGE_FALLTHRU) == 0)
- abort ();
+ bb = e->src;
+
+ /* It is possible to have a non-simple jump here. Consider a target
+ where some forms of unconditional jumps clobber a register. This
+ happens on the fr30 for example.
+
+ We know this block has a single successor, so we can just emit
+ the queued insns before the jump. */
+ if (GET_CODE (bb->end) == JUMP_INSN)
+ for (before = bb->end;
+ GET_CODE (PREV_INSN (before)) == NOTE
+ && NOTE_LINE_NUMBER (PREV_INSN (before)) ==
+ NOTE_INSN_LOOP_BEG; before = PREV_INSN (before))
+ ;
+ else
+ {
+ /* We'd better be fallthru, or we've lost track of what's what. */
+ if ((e->flags & EDGE_FALLTHRU) == 0)
+ abort ();
+ after = bb->end;
+ }
+ }
+ /* Otherwise we must split the edge. */
+ else
+ {
+ bb = split_edge (e);
after = bb->end;
}
}
- /* Otherwise we must split the edge. */
- else
- {
- bb = split_edge (e);
- after = bb->end;
- }
-
/* Now that we've found the spot, do the insertion. */
if (before)
{
/* ??? Remove all outgoing edges from BB and add one for EXIT.
This is not currently a problem because this only happens
- for the (single) epilogue, which already has a fallthru edge
- to EXIT. */
+ for the (single) epilogue, which already has a fallthru edge
+ to EXIT. */
e = bb->succ;
if (e->dest != EXIT_BLOCK_PTR
- || e->succ_next != NULL
- || (e->flags & EDGE_FALLTHRU) == 0)
+ || e->succ_next != NULL || (e->flags & EDGE_FALLTHRU) == 0)
abort ();
- e->flags &= ~EDGE_FALLTHRU;
+ e->flags &= ~EDGE_FALLTHRU;
emit_barrier_after (last);
if (before)
}
else if (GET_CODE (last) == JUMP_INSN)
abort ();
+
find_sub_basic_blocks (bb);
}
void
commit_edge_insertions ()
{
- int i;
basic_block bb;
#ifdef ENABLE_CHECKING
verify_flow_info ();
#endif
- i = -1;
- bb = ENTRY_BLOCK_PTR;
- while (1)
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
{
edge e, next;
{
next = e->succ_next;
if (e->insns)
- commit_one_edge_insertion (e);
+ commit_one_edge_insertion (e, false);
}
+ }
+}
+\f
+/* Update the CFG for all queued instructions, taking special care of inserting
+ code on edges between call and storing its return value. */
- if (++i >= n_basic_blocks)
- break;
- bb = BASIC_BLOCK (i);
+void
+commit_edge_insertions_watch_calls ()
+{
+ basic_block bb;
+
+#ifdef ENABLE_CHECKING
+ verify_flow_info ();
+#endif
+
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
+ {
+ edge e, next;
+
+ for (e = bb->succ; e; e = next)
+ {
+ next = e->succ_next;
+ if (e->insns)
+ commit_one_edge_insertion (e, true);
+ }
}
}
\f
dump_regset (bb->global_live_at_start, outf);
putc ('\n', outf);
- for (insn = bb->head, last = NEXT_INSN (bb->end);
- insn != last;
+ for (insn = bb->head, last = NEXT_INSN (bb->end); insn != last;
insn = NEXT_INSN (insn))
print_rtl_single (outf, insn);
FILE *outf;
rtx rtx_first;
{
- register rtx tmp_rtx;
+ rtx tmp_rtx;
if (rtx_first == 0)
fprintf (outf, "(nil)\n");
else
{
- int i;
enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
int max_uid = get_max_uid ();
- basic_block *start = (basic_block *)
- xcalloc (max_uid, sizeof (basic_block));
- basic_block *end = (basic_block *)
- xcalloc (max_uid, sizeof (basic_block));
- enum bb_state *in_bb_p = (enum bb_state *)
- xcalloc (max_uid, sizeof (enum bb_state));
-
- for (i = n_basic_blocks - 1; i >= 0; i--)
+ basic_block *start
+ = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
+ basic_block *end
+ = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
+ enum bb_state *in_bb_p
+ = (enum bb_state *) xcalloc (max_uid, sizeof (enum bb_state));
+
+ basic_block bb;
+
+ FOR_EACH_BB_REVERSE (bb)
{
- basic_block bb = BASIC_BLOCK (i);
rtx x;
start[INSN_UID (bb->head)] = bb;
for (x = bb->head; x != NULL_RTX; x = NEXT_INSN (x))
{
enum bb_state state = IN_MULTIPLE_BB;
+
if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
state = IN_ONE_BB;
in_bb_p[INSN_UID (x)] = state;
for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
{
int did_output;
- basic_block bb;
if ((bb = start[INSN_UID (tmp_rtx)]) != NULL)
{
}
}
\f
+void
+update_br_prob_note (bb)
+ basic_block bb;
+{
+ rtx note;
+ if (GET_CODE (bb->end) != JUMP_INSN)
+ return;
+ note = find_reg_note (bb->end, REG_BR_PROB, NULL_RTX);
+ if (!note || INTVAL (XEXP (note, 0)) == BRANCH_EDGE (bb)->probability)
+ return;
+ XEXP (note, 0) = GEN_INT (BRANCH_EDGE (bb)->probability);
+}
+\f
/* Verify the CFG consistency. This function check some CFG invariants and
aborts when something is wrong. Hope that this function will help to
convert many optimization passes to preserve CFG consistent.
- overlapping of basic blocks
- edge list correctness
- headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
- - tails of basic blocks (ensure that boundary is necesary)
+ - tails of basic blocks (ensure that boundary is necessary)
- scans body of the basic block for JUMP_INSN, CODE_LABEL
and NOTE_INSN_BASIC_BLOCK
- check that all insns are in the basic blocks
- (except the switch handling code, barriers and notes)
+ (except the switch handling code, barriers and notes)
- check that all returns are followed by barriers
In future it can be extended check a lot of other stuff as well
basic_block *bb_info, *last_visited;
size_t *edge_checksum;
rtx x;
- int i, last_bb_num_seen, num_bb_notes, err = 0;
+ int num_bb_notes, err = 0;
+ basic_block bb, last_bb_seen;
bb_info = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
- last_visited = (basic_block *) xcalloc (n_basic_blocks + 2,
+ last_visited = (basic_block *) xcalloc (last_basic_block + 2,
sizeof (basic_block));
- edge_checksum = (size_t *) xcalloc (n_basic_blocks + 2, sizeof (size_t));
+ edge_checksum = (size_t *) xcalloc (last_basic_block + 2, sizeof (size_t));
+
+ /* Check bb chain & numbers. */
+ last_bb_seen = ENTRY_BLOCK_PTR;
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
+ {
+ if (bb != EXIT_BLOCK_PTR
+ && bb != BASIC_BLOCK (bb->index))
+ {
+ error ("bb %d on wrong place", bb->index);
+ err = 1;
+ }
- for (i = n_basic_blocks - 1; i >= 0; i--)
+ if (bb->prev_bb != last_bb_seen)
+ {
+ error ("prev_bb of %d should be %d, not %d",
+ bb->index, last_bb_seen->index, bb->prev_bb->index);
+ err = 1;
+ }
+
+ last_bb_seen = bb;
+ }
+
+ FOR_EACH_BB_REVERSE (bb)
{
- basic_block bb = BASIC_BLOCK (i);
rtx head = bb->head;
rtx end = bb->end;
for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
if (x == end)
break;
+
if (!x)
{
- error ("End insn %d for block %d not found in the insn stream.",
+ error ("end insn %d for block %d not found in the insn stream",
INSN_UID (end), bb->index);
err = 1;
}
used by other passes. */
if (bb_info[INSN_UID (x)] != NULL)
{
- error ("Insn %d is in multiple basic blocks (%d and %d)",
+ error ("insn %d is in multiple basic blocks (%d and %d)",
INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
err = 1;
}
+
bb_info[INSN_UID (x)] = bb;
if (x == head)
}
if (!x)
{
- error ("Head insn %d for block %d not found in the insn stream.",
+ error ("head insn %d for block %d not found in the insn stream",
INSN_UID (head), bb->index);
err = 1;
}
}
/* Now check the basic blocks (boundaries etc.) */
- for (i = n_basic_blocks - 1; i >= 0; i--)
+ FOR_EACH_BB_REVERSE (bb)
{
- basic_block bb = BASIC_BLOCK (i);
- int has_fallthru = 0;
+ int n_fallthru = 0, n_eh = 0, n_call = 0, n_abnormal = 0, n_branch = 0;
edge e;
+ rtx note;
- e = bb->succ;
- while (e)
+ if (INSN_P (bb->end)
+ && (note = find_reg_note (bb->end, REG_BR_PROB, NULL_RTX))
+ && bb->succ && bb->succ->succ_next
+ && any_condjump_p (bb->end))
+ {
+ if (INTVAL (XEXP (note, 0)) != BRANCH_EDGE (bb)->probability)
+ {
+ error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
+ INTVAL (XEXP (note, 0)), BRANCH_EDGE (bb)->probability);
+ err = 1;
+ }
+ }
+ if (bb->count < 0)
+ {
+ error ("verify_flow_info: Wrong count of block %i %i",
+ bb->index, (int)bb->count);
+ err = 1;
+ }
+ if (bb->frequency < 0)
+ {
+ error ("verify_flow_info: Wrong frequency of block %i %i",
+ bb->index, bb->frequency);
+ err = 1;
+ }
+ for (e = bb->succ; e; e = e->succ_next)
{
if (last_visited [e->dest->index + 2] == bb)
{
e->src->index, e->dest->index);
err = 1;
}
+ if (e->probability < 0 || e->probability > REG_BR_PROB_BASE)
+ {
+ error ("verify_flow_info: Wrong probability of edge %i->%i %i",
+ e->src->index, e->dest->index, e->probability);
+ err = 1;
+ }
+ if (e->count < 0)
+ {
+ error ("verify_flow_info: Wrong count of edge %i->%i %i",
+ e->src->index, e->dest->index, (int)e->count);
+ err = 1;
+ }
+
last_visited [e->dest->index + 2] = bb;
if (e->flags & EDGE_FALLTHRU)
- has_fallthru = 1;
+ n_fallthru++;
+
+ if ((e->flags & ~EDGE_DFS_BACK) == 0)
+ n_branch++;
+
+ if (e->flags & EDGE_ABNORMAL_CALL)
+ n_call++;
+
+ if (e->flags & EDGE_EH)
+ n_eh++;
+ else if (e->flags & EDGE_ABNORMAL)
+ n_abnormal++;
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)
+
+ if (e->src->next_bb != e->dest)
{
- error ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
- e->src->index, e->dest->index);
- err = 1;
+ 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))
+ if (GET_CODE (insn) == BARRIER
+#ifndef CASE_DROPS_THROUGH
+ || INSN_P (insn)
+#else
+ || (INSN_P (insn) && ! JUMP_TABLE_DATA_P (insn))
+#endif
+ )
{
error ("verify_flow_info: Incorrect fallthru %i->%i",
e->src->index, e->dest->index);
- fatal_insn ("Wrong insn in the fallthru edge", insn);
+ 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;
}
+
edge_checksum[e->dest->index + 2] += (size_t) e;
- e = e->succ_next;
}
- if (!has_fallthru)
+
+ if (n_eh && GET_CODE (PATTERN (bb->end)) != RESX
+ && !find_reg_note (bb->end, REG_EH_REGION, NULL_RTX))
+ {
+ error ("Missing REG_EH_REGION note in the end of bb %i", bb->index);
+ err = 1;
+ }
+ if (n_branch
+ && (GET_CODE (bb->end) != JUMP_INSN
+ || (n_branch > 1 && (any_uncondjump_p (bb->end)
+ || any_condjump_p (bb->end)))))
+ {
+ error ("Too many outgoing branch edges from bb %i", bb->index);
+ err = 1;
+ }
+ if (n_fallthru && any_uncondjump_p (bb->end))
+ {
+ error ("Fallthru edge after unconditional jump %i", bb->index);
+ err = 1;
+ }
+ if (n_branch != 1 && any_uncondjump_p (bb->end))
+ {
+ error ("Wrong amount of branch edges after unconditional jump %i", bb->index);
+ err = 1;
+ }
+ if (n_branch != 1 && any_condjump_p (bb->end)
+ && JUMP_LABEL (bb->end) != bb->next_bb->head)
{
- rtx insn = bb->end;
+ error ("Wrong amount of branch edges after conditional jump %i", bb->index);
+ err = 1;
+ }
+ if (n_call && GET_CODE (bb->end) != CALL_INSN)
+ {
+ error ("Call edges for non-call insn in bb %i", bb->index);
+ err = 1;
+ }
+ if (n_abnormal
+ && (GET_CODE (bb->end) != CALL_INSN && n_call != n_abnormal)
+ && (GET_CODE (bb->end) != JUMP_INSN
+ || any_condjump_p (bb->end)
+ || any_uncondjump_p (bb->end)))
+ {
+ error ("Abnormal edges for no purpose in bb %i", bb->index);
+ err = 1;
+ }
+
+ if (!n_fallthru)
+ {
+ rtx insn;
/* Ensure existence of barrier in BB with no fallthru edges. */
- for (insn = bb->end; GET_CODE (insn) != BARRIER;
+ for (insn = bb->end; !insn || GET_CODE (insn) != BARRIER;
insn = NEXT_INSN (insn))
if (!insn
|| (GET_CODE (insn) == NOTE
&& NOTE_LINE_NUMBER (insn) == NOTE_INSN_BASIC_BLOCK))
{
- error ("Missing barrier after block %i", bb->index);
+ error ("missing barrier after block %i", bb->index);
err = 1;
+ break;
}
}
- e = bb->pred;
- while (e)
+ for (e = bb->pred; e; e = e->pred_next)
{
if (e->dest != bb)
{
- error ("Basic block %d pred edge is corrupted", bb->index);
+ error ("basic block %d pred edge is corrupted", bb->index);
fputs ("Predecessor: ", stderr);
dump_edge_info (stderr, e, 0);
fputs ("\nSuccessor: ", stderr);
err = 1;
}
edge_checksum[e->dest->index + 2] -= (size_t) e;
- e = e->pred_next;
}
- for (x = bb->head; x != NEXT_INSN (bb->end); x = NEXT_INSN (x))
- if (basic_block_for_insn && BLOCK_FOR_INSN (x) != bb)
- {
- debug_rtx (x);
- if (! BLOCK_FOR_INSN (x))
- error ("Insn %d is inside basic block %d but block_for_insn is NULL",
- INSN_UID (x), bb->index);
- else
- error ("Insn %d is inside basic block %d but block_for_insn is %i",
- INSN_UID (x), bb->index, BLOCK_FOR_INSN (x)->index);
- err = 1;
- }
+
+ for (x = bb->head; x != NEXT_INSN (bb->end); x = NEXT_INSN (x))
+ if (basic_block_for_insn && BLOCK_FOR_INSN (x) != bb)
+ {
+ debug_rtx (x);
+ if (! BLOCK_FOR_INSN (x))
+ error
+ ("insn %d inside basic block %d but block_for_insn is NULL",
+ INSN_UID (x), bb->index);
+ else
+ error
+ ("insn %d inside basic block %d but block_for_insn is %i",
+ INSN_UID (x), bb->index, BLOCK_FOR_INSN (x)->index);
+
+ err = 1;
+ }
/* OK pointers are correct. Now check the header of basic
block. It ought to contain optional CODE_LABEL followed
bb->index);
err = 1;
}
+
x = NEXT_INSN (x);
}
+
if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
{
error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
}
if (bb->end == x)
- {
- /* Do checks for empty blocks here */
- }
+ /* Do checks for empty blocks her. e */
+ ;
else
- {
- x = NEXT_INSN (x);
- while (x)
- {
- if (NOTE_INSN_BASIC_BLOCK_P (x))
- {
- error ("NOTE_INSN_BASIC_BLOCK %d in the middle of basic block %d",
- INSN_UID (x), bb->index);
- err = 1;
- }
-
- if (x == bb->end)
- break;
-
- if (GET_CODE (x) == JUMP_INSN
- || GET_CODE (x) == CODE_LABEL
- || GET_CODE (x) == BARRIER)
- {
- error ("In basic block %d:", bb->index);
- fatal_insn ("Flow control insn inside a basic block", x);
- }
+ for (x = NEXT_INSN (x); x; x = NEXT_INSN (x))
+ {
+ if (NOTE_INSN_BASIC_BLOCK_P (x))
+ {
+ error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
+ INSN_UID (x), bb->index);
+ err = 1;
+ }
+
+ if (x == bb->end)
+ break;
- x = NEXT_INSN (x);
- }
- }
+ if (GET_CODE (x) == JUMP_INSN
+ || GET_CODE (x) == CODE_LABEL
+ || GET_CODE (x) == BARRIER)
+ {
+ error ("in basic block %d:", bb->index);
+ fatal_insn ("flow control insn inside a basic block", x);
+ }
+ }
}
/* 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])
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+ if (edge_checksum[bb->index + 2])
{
- error ("Basic block %i edge lists are corrupted", i);
+ error ("basic block %i edge lists are corrupted", bb->index);
err = 1;
}
- last_bb_num_seen = -1;
num_bb_notes = 0;
- x = rtx_first;
- while (x)
+ last_bb_seen = ENTRY_BLOCK_PTR;
+
+ for (x = rtx_first; x; x = NEXT_INSN (x))
{
if (NOTE_INSN_BASIC_BLOCK_P (x))
{
- basic_block bb = NOTE_BASIC_BLOCK (x);
+ bb = NOTE_BASIC_BLOCK (x);
+
num_bb_notes++;
- if (bb->index != last_bb_num_seen + 1)
- internal_error ("Basic blocks not numbered consecutively.");
+ if (bb != last_bb_seen->next_bb)
+ internal_error ("basic blocks not numbered consecutively");
- last_bb_num_seen = bb->index;
+ last_bb_seen = bb;
}
if (!bb_info[INSN_UID (x)])
&& GET_CODE (NEXT_INSN (x)) == JUMP_INSN
&& (GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_DIFF_VEC
|| GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_VEC))
- {
- x = NEXT_INSN (x);
- }
+ x = NEXT_INSN (x);
/* But in any case, non-deletable labels can appear anywhere. */
break;
default:
- fatal_insn ("Insn outside basic block", x);
+ fatal_insn ("insn outside basic block", x);
}
}
&& GET_CODE (x) == JUMP_INSN
&& returnjump_p (x) && ! condjump_p (x)
&& ! (NEXT_INSN (x) && GET_CODE (NEXT_INSN (x)) == BARRIER))
- fatal_insn ("Return not followed by barrier", x);
-
- x = NEXT_INSN (x);
+ fatal_insn ("return not followed by barrier", x);
}
if (num_bb_notes != n_basic_blocks)
num_bb_notes, n_basic_blocks);
if (err)
- internal_error ("verify_flow_info failed.");
+ internal_error ("verify_flow_info failed");
/* Clean up. */
free (bb_info);
free (edge_checksum);
}
\f
-/* Assume that the preceeding pass has possibly eliminated jump instructions
+/* Assume that the preceding pass has possibly eliminated jump instructions
or converted the unconditional jumps. Eliminate the edges from CFG.
Return true if any edges are eliminated. */
basic_block bb;
{
edge e, next;
- rtx insn = bb->end;
+ rtx insn = bb->end, note;
bool purged = false;
- if (GET_CODE (insn) == JUMP_INSN && !simplejump_p (insn))
- return false;
+ /* If this instruction cannot trap, remove REG_EH_REGION notes. */
+ if (GET_CODE (insn) == INSN
+ && (note = find_reg_note (insn, REG_EH_REGION, NULL)))
+ {
+ rtx eqnote;
+
+ if (! may_trap_p (PATTERN (insn))
+ || ((eqnote = find_reg_equal_equiv_note (insn))
+ && ! may_trap_p (XEXP (eqnote, 0))))
+ remove_note (insn, note);
+ }
+
+ /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
+ for (e = bb->succ; e; e = next)
+ {
+ next = e->succ_next;
+ if (e->flags & EDGE_EH)
+ {
+ if (can_throw_internal (bb->end))
+ continue;
+ }
+ else if (e->flags & EDGE_ABNORMAL_CALL)
+ {
+ if (GET_CODE (bb->end) == CALL_INSN
+ && (! (note = find_reg_note (insn, REG_EH_REGION, NULL))
+ || INTVAL (XEXP (note, 0)) >= 0))
+ continue;
+ }
+ else
+ continue;
+
+ remove_edge (e);
+ bb->flags |= BB_DIRTY;
+ purged = true;
+ }
+
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;
+ return purged;
+
+ /* Branch probability/prediction notes are defined only for
+ condjumps. We've possibly turned condjump into simplejump. */
+ if (simplejump_p (insn))
+ {
+ note = find_reg_note (insn, REG_BR_PROB, NULL);
+ if (note)
+ remove_note (insn, note);
+ while ((note = find_reg_note (insn, REG_BR_PRED, NULL)))
+ remove_note (insn, note);
+ }
+
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))
+ /* Avoid abnormal flags to leak from computed jumps turned
+ into simplejumps. */
+
+ e->flags &= ~EDGE_ABNORMAL;
+
+ /* See if this edge is one we should keep. */
+ if ((e->flags & EDGE_FALLTHRU) && any_condjump_p (insn))
+ /* A conditional jump can fall through into the next
+ block, so we should keep the edge. */
+ continue;
+ else if (e->dest != EXIT_BLOCK_PTR
+ && e->dest->head == JUMP_LABEL (insn))
+ /* If the destination block is the target of the jump,
+ keep the edge. */
continue;
- if (e->dest != EXIT_BLOCK_PTR
- && e->dest->head == JUMP_LABEL (insn))
+ else if (e->dest == EXIT_BLOCK_PTR && returnjump_p (insn))
+ /* If the destination block is the exit block, and this
+ instruction is a return, then keep the edge. */
continue;
- if (e->dest == EXIT_BLOCK_PTR
- && returnjump_p (insn))
+ else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
+ /* Keep the edges that correspond to exceptions thrown by
+ this instruction. */
continue;
+
+ /* We do not need this edge. */
+ bb->flags |= BB_DIRTY;
purged = true;
remove_edge (e);
}
+
if (!bb->succ || !purged)
- return false;
+ return purged;
+
if (rtl_dump_file)
fprintf (rtl_dump_file, "Purged edges from bb %i\n", bb->index);
+
if (!optimize)
return purged;
{
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));
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);
+ 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;
+ {
+ bb->flags |= BB_DIRTY;
+ 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;
return purged;
}
-/* Search all basic blocks for potentionally dead edges and purge them.
-
- Return true ifif some edge has been elliminated.
- */
+/* Search all basic blocks for potentially dead edges and purge them. Return
+ true if some edge has been eliminated. */
bool
-purge_all_dead_edges ()
+purge_all_dead_edges (update_life_p)
+ int update_life_p;
{
- int i, purged = false;
- for (i = 0; i < n_basic_blocks; i++)
- purged |= purge_dead_edges (BASIC_BLOCK (i));
+ int purged = false;
+ sbitmap blocks = 0;
+ basic_block bb;
+
+ if (update_life_p)
+ {
+ blocks = sbitmap_alloc (last_basic_block);
+ sbitmap_zero (blocks);
+ }
+
+ FOR_EACH_BB (bb)
+ {
+ bool purged_here = purge_dead_edges (bb);
+
+ purged |= purged_here;
+ if (purged_here && update_life_p)
+ SET_BIT (blocks, bb->index);
+ }
+
+ if (update_life_p && purged)
+ update_life_info (blocks, UPDATE_LIFE_GLOBAL,
+ PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE
+ | PROP_KILL_DEAD_CODE);
+
+ if (update_life_p)
+ sbitmap_free (blocks);
return purged;
}
OSDN Git Service
