#include "insn-config.h"
#include "flags.h"
#include "recog.h"
+#include "diagnostic-core.h"
#include "toplev.h"
#include "cselib.h"
#include "params.h"
/* Set to true if crossjumps occured in the latest run of try_optimize_cfg. */
static bool crossjumps_occured;
+/* Set to true if we couldn't run an optimization due to stale liveness
+ information; we should run df_analyze to enable more opportunities. */
+static bool block_was_dirty;
+
static bool try_crossjump_to_edge (int, edge, edge);
static bool try_crossjump_bb (int, basic_block);
static bool outgoing_edges_match (int, basic_block, basic_block);
int counter, goto_locus;
bool threaded = false;
int nthreaded_edges = 0;
- bool may_thread = first_pass | df_get_bb_dirty (b);
+ bool may_thread = first_pass || (b->flags & BB_MODIFIED) != 0;
/* Skip complex edges because we don't know how to update them.
{
basic_block new_target = NULL;
bool new_target_threaded = false;
- may_thread |= df_get_bb_dirty (target);
+ may_thread |= (target->flags & BB_MODIFIED) != 0;
if (FORWARDER_BLOCK_P (target)
&& !(single_succ_edge (target)->flags & EDGE_CROSSING)
while (true)
{
-
/* Ignore notes. */
while (!NONDEBUG_INSN_P (i1) && i1 != BB_END (bb1))
i1 = NEXT_INSN (i1);
while (!NONDEBUG_INSN_P (i2) && i2 != BB_END (bb2))
i2 = NEXT_INSN (i2);
+ if ((i1 == BB_END (bb1) && !NONDEBUG_INSN_P (i1))
+ || (i2 == BB_END (bb2) && !NONDEBUG_INSN_P (i2)))
+ break;
+
if (NOTE_P (i1) || NOTE_P (i2)
|| JUMP_P (i1) || JUMP_P (i2))
break;
/* If nothing changed since the last attempt, there is nothing
we can do. */
if (!first_pass
- && (!(df_get_bb_dirty (e->src))
- && !(df_get_bb_dirty (fallthru->src))))
+ && !((e->src->flags & BB_MODIFIED)
+ || (fallthru->src->flags & BB_MODIFIED)))
continue;
if (try_crossjump_to_edge (mode, e, fallthru))
/* If nothing changed since the last attempt, there is nothing
we can do. */
if (!first_pass
- && (!(df_get_bb_dirty (e->src))
- && !(df_get_bb_dirty (e2->src))))
+ && !((e->src->flags & BB_MODIFIED)
+ || (e2->src->flags & BB_MODIFIED)))
continue;
if (try_crossjump_to_edge (mode, e, e2))
return changed;
}
+/* Search the successors of BB for common insn sequences. When found,
+ share code between them by moving it across the basic block
+ boundary. Return true if any changes made. */
+
+static bool
+try_head_merge_bb (basic_block bb)
+{
+ basic_block final_dest_bb = NULL;
+ int max_match = INT_MAX;
+ edge e0;
+ rtx *headptr, *currptr, *nextptr;
+ bool changed, moveall;
+ unsigned ix;
+ rtx e0_last_head, cond, move_before;
+ unsigned nedges = EDGE_COUNT (bb->succs);
+ rtx jump = BB_END (bb);
+ regset live, live_union;
+
+ /* Nothing to do if there is not at least two outgoing edges. */
+ if (nedges < 2)
+ return false;
+
+ /* Don't crossjump if this block ends in a computed jump,
+ unless we are optimizing for size. */
+ if (optimize_bb_for_size_p (bb)
+ && bb != EXIT_BLOCK_PTR
+ && computed_jump_p (BB_END (bb)))
+ return false;
+
+ cond = get_condition (jump, &move_before, true, false);
+ if (cond == NULL_RTX)
+ move_before = jump;
+
+ for (ix = 0; ix < nedges; ix++)
+ if (EDGE_SUCC (bb, ix)->dest == EXIT_BLOCK_PTR)
+ return false;
+
+ for (ix = 0; ix < nedges; ix++)
+ {
+ edge e = EDGE_SUCC (bb, ix);
+ basic_block other_bb = e->dest;
+
+ if (df_get_bb_dirty (other_bb))
+ {
+ block_was_dirty = true;
+ return false;
+ }
+
+ if (e->flags & EDGE_ABNORMAL)
+ return false;
+
+ /* Normally, all destination blocks must only be reachable from this
+ block, i.e. they must have one incoming edge.
+
+ There is one special case we can handle, that of multiple consecutive
+ jumps where the first jumps to one of the targets of the second jump.
+ This happens frequently in switch statements for default labels.
+ The structure is as follows:
+ FINAL_DEST_BB
+ ....
+ if (cond) jump A;
+ fall through
+ BB
+ jump with targets A, B, C, D...
+ A
+ has two incoming edges, from FINAL_DEST_BB and BB
+
+ In this case, we can try to move the insns through BB and into
+ FINAL_DEST_BB. */
+ if (EDGE_COUNT (other_bb->preds) != 1)
+ {
+ edge incoming_edge, incoming_bb_other_edge;
+ edge_iterator ei;
+
+ if (final_dest_bb != NULL
+ || EDGE_COUNT (other_bb->preds) != 2)
+ return false;
+
+ /* We must be able to move the insns across the whole block. */
+ move_before = BB_HEAD (bb);
+ while (!NONDEBUG_INSN_P (move_before))
+ move_before = NEXT_INSN (move_before);
+
+ if (EDGE_COUNT (bb->preds) != 1)
+ return false;
+ incoming_edge = EDGE_PRED (bb, 0);
+ final_dest_bb = incoming_edge->src;
+ if (EDGE_COUNT (final_dest_bb->succs) != 2)
+ return false;
+ FOR_EACH_EDGE (incoming_bb_other_edge, ei, final_dest_bb->succs)
+ if (incoming_bb_other_edge != incoming_edge)
+ break;
+ if (incoming_bb_other_edge->dest != other_bb)
+ return false;
+ }
+ }
+
+ e0 = EDGE_SUCC (bb, 0);
+ e0_last_head = NULL_RTX;
+ changed = false;
+
+ for (ix = 1; ix < nedges; ix++)
+ {
+ edge e = EDGE_SUCC (bb, ix);
+ rtx e0_last, e_last;
+ int nmatch;
+
+ nmatch = flow_find_head_matching_sequence (e0->dest, e->dest,
+ &e0_last, &e_last, 0);
+ if (nmatch == 0)
+ return false;
+
+ if (nmatch < max_match)
+ {
+ max_match = nmatch;
+ e0_last_head = e0_last;
+ }
+ }
+
+ /* If we matched an entire block, we probably have to avoid moving the
+ last insn. */
+ if (max_match > 0
+ && e0_last_head == BB_END (e0->dest)
+ && (find_reg_note (e0_last_head, REG_EH_REGION, 0)
+ || control_flow_insn_p (e0_last_head)))
+ {
+ max_match--;
+ if (max_match == 0)
+ return false;
+ do
+ e0_last_head = prev_real_insn (e0_last_head);
+ while (DEBUG_INSN_P (e0_last_head));
+ }
+
+ if (max_match == 0)
+ return false;
+
+ /* We must find a union of the live registers at each of the end points. */
+ live = BITMAP_ALLOC (NULL);
+ live_union = BITMAP_ALLOC (NULL);
+
+ currptr = XNEWVEC (rtx, nedges);
+ headptr = XNEWVEC (rtx, nedges);
+ nextptr = XNEWVEC (rtx, nedges);
+
+ for (ix = 0; ix < nedges; ix++)
+ {
+ int j;
+ basic_block merge_bb = EDGE_SUCC (bb, ix)->dest;
+ rtx head = BB_HEAD (merge_bb);
+
+ while (!NONDEBUG_INSN_P (head))
+ head = NEXT_INSN (head);
+ headptr[ix] = head;
+ currptr[ix] = head;
+
+ /* Compute the end point and live information */
+ for (j = 1; j < max_match; j++)
+ do
+ head = NEXT_INSN (head);
+ while (!NONDEBUG_INSN_P (head));
+ simulate_backwards_to_point (merge_bb, live, head);
+ IOR_REG_SET (live_union, live);
+ }
+
+ /* If we're moving across two blocks, verify the validity of the
+ first move, then adjust the target and let the loop below deal
+ with the final move. */
+ if (final_dest_bb != NULL)
+ {
+ rtx move_upto;
+
+ moveall = can_move_insns_across (currptr[0], e0_last_head, move_before,
+ jump, e0->dest, live_union,
+ NULL, &move_upto);
+ if (!moveall)
+ e0_last_head = move_upto;
+ if (e0_last_head == NULL_RTX)
+ goto out;
+
+ jump = BB_END (final_dest_bb);
+ cond = get_condition (jump, &move_before, true, false);
+ if (cond == NULL_RTX)
+ move_before = jump;
+ }
+
+ do
+ {
+ rtx move_upto;
+ moveall = can_move_insns_across (currptr[0], e0_last_head,
+ move_before, jump, e0->dest, live_union,
+ NULL, &move_upto);
+ if (!moveall && move_upto == NULL_RTX)
+ {
+ if (jump == move_before)
+ break;
+
+ /* Try again, using a different insertion point. */
+ move_before = jump;
+
+#ifdef HAVE_cc0
+ /* Don't try moving before a cc0 user, as that may invalidate
+ the cc0. */
+ if (reg_mentioned_p (cc0_rtx, jump))
+ break;
+#endif
+
+ continue;
+ }
+
+ if (final_dest_bb && !moveall)
+ /* We haven't checked whether a partial move would be OK for the first
+ move, so we have to fail this case. */
+ break;
+
+ changed = true;
+ for (;;)
+ {
+ if (currptr[0] == move_upto)
+ break;
+ for (ix = 0; ix < nedges; ix++)
+ {
+ rtx curr = currptr[ix];
+ do
+ curr = NEXT_INSN (curr);
+ while (!NONDEBUG_INSN_P (curr));
+ currptr[ix] = curr;
+ }
+ }
+
+ /* If we can't currently move all of the identical insns, remember
+ each insn after the range that we'll merge. */
+ if (!moveall)
+ for (ix = 0; ix < nedges; ix++)
+ {
+ rtx curr = currptr[ix];
+ do
+ curr = NEXT_INSN (curr);
+ while (!NONDEBUG_INSN_P (curr));
+ nextptr[ix] = curr;
+ }
+
+ reorder_insns (headptr[0], currptr[0], PREV_INSN (move_before));
+ df_set_bb_dirty (EDGE_SUCC (bb, 0)->dest);
+ if (final_dest_bb != NULL)
+ df_set_bb_dirty (final_dest_bb);
+ df_set_bb_dirty (bb);
+ for (ix = 1; ix < nedges; ix++)
+ {
+ df_set_bb_dirty (EDGE_SUCC (bb, ix)->dest);
+ delete_insn_chain (headptr[ix], currptr[ix], false);
+ }
+ if (!moveall)
+ {
+ if (jump == move_before)
+ break;
+
+ /* For the unmerged insns, try a different insertion point. */
+ move_before = jump;
+
+#ifdef HAVE_cc0
+ /* Don't try moving before a cc0 user, as that may invalidate
+ the cc0. */
+ if (reg_mentioned_p (cc0_rtx, jump))
+ break;
+#endif
+
+ for (ix = 0; ix < nedges; ix++)
+ currptr[ix] = headptr[ix] = nextptr[ix];
+ }
+ }
+ while (!moveall);
+
+ out:
+ free (currptr);
+ free (headptr);
+ free (nextptr);
+
+ crossjumps_occured |= changed;
+
+ return changed;
+}
+
/* Return true if BB contains just bb note, or bb note followed
by only DEBUG_INSNs. */
one predecessor, they may be combined. */
do
{
+ block_was_dirty = false;
changed = false;
iterations++;
&& single_succ_edge (ENTRY_BLOCK_PTR)->dest != b))
{
c = b->prev_bb;
+ if (EDGE_COUNT (b->preds) > 0)
+ {
+ edge e;
+ edge_iterator ei;
+
+ if (current_ir_type () == IR_RTL_CFGLAYOUT)
+ {
+ if (b->il.rtl->footer
+ && BARRIER_P (b->il.rtl->footer))
+ FOR_EACH_EDGE (e, ei, b->preds)
+ if ((e->flags & EDGE_FALLTHRU)
+ && e->src->il.rtl->footer == NULL)
+ {
+ if (b->il.rtl->footer)
+ {
+ e->src->il.rtl->footer = b->il.rtl->footer;
+ b->il.rtl->footer = NULL;
+ }
+ else
+ {
+ start_sequence ();
+ e->src->il.rtl->footer = emit_barrier ();
+ end_sequence ();
+ }
+ }
+ }
+ else
+ {
+ rtx last = get_last_bb_insn (b);
+ if (last && BARRIER_P (last))
+ FOR_EACH_EDGE (e, ei, b->preds)
+ if ((e->flags & EDGE_FALLTHRU))
+ emit_barrier_after (BB_END (e->src));
+ }
+ }
delete_basic_block (b);
if (!(mode & CLEANUP_CFGLAYOUT))
changed = true;
&& try_crossjump_bb (mode, b))
changed_here = true;
+ if ((mode & CLEANUP_CROSSJUMP)
+ /* This can lengthen register lifetimes. Do it only after
+ reload. */
+ && reload_completed
+ && try_head_merge_bb (b))
+ changed_here = true;
+
/* Don't get confused by the index shift caused by
deleting blocks. */
if (!changed_here)
&& try_crossjump_bb (mode, EXIT_BLOCK_PTR))
changed = true;
+ if (block_was_dirty)
+ {
+ /* This should only be set by head-merging. */
+ gcc_assert (mode & CLEANUP_CROSSJUMP);
+ df_analyze ();
+ }
+
#ifdef ENABLE_CHECKING
if (changed)
verify_flow_info ();
if ((mode & CLEANUP_EXPENSIVE) && !reload_completed
&& !delete_trivially_dead_insns (get_insns (), max_reg_num ()))
break;
- else if ((mode & CLEANUP_CROSSJUMP)
- && crossjumps_occured)
+ if ((mode & CLEANUP_CROSSJUMP) && crossjumps_occured)
run_fast_dce ();
}
else
OSDN Git Service
