/* Dead-code elimination pass for the GNU compiler.
- Copyright (C) 2000 Free Software Foundation, Inc.
+ Copyright (C) 2000, 2001 Free Software Foundation, Inc.
Written by Jeffrey D. Oldham <oldham@codesourcery.com>.
-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
+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
+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. */
The last step can require adding labels, deleting insns, and
modifying basic block structures. Some conditional jumps may be
converted to unconditional jumps so the control-flow graph may be
- out-of-date.
+ out-of-date.
Edges from some infinite loops to the exit block can be added to
the control-flow graph, but will be removed after this pass is
PARAMS ((rtx current_rtx));
static int propagate_necessity_through_operand
PARAMS ((rtx *current_rtx, void *data));
+static void note_inherently_necessary_set
+ PARAMS ((rtx, rtx, void *));
\f
/* Unnecessary insns are indicated using insns' in_struct bit. */
if (INDEX_EDGE_PRED_BB (el, edge_index) == EXIT_BLOCK_PTR)
abort ();
- ending_block =
- (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
- ? BASIC_BLOCK (0)
+ ending_block =
+ (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
+ ? BASIC_BLOCK (0)
: find_pdom (pdom, INDEX_EDGE_PRED_BB (el, edge_index));
for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index);
{
case CLOBBER:
/* Do not traverse the rest of the clobber. */
- return -1;
+ return -1;
break;
case PC:
return 0;
&inherently_necessary_register_1, NULL);
}
+
+/* Called via note_stores for each store in an insn. Note whether
+ or not a particular store is inherently necessary. Store a
+ nonzero value in inherently_necessary_p if such a store is found. */
+
+static void
+note_inherently_necessary_set (dest, set, data)
+ rtx set ATTRIBUTE_UNUSED;
+ rtx dest;
+ void *data;
+{
+ int *inherently_necessary_set_p = (int *)data;
+
+ while (GET_CODE (dest) == SUBREG
+ || GET_CODE (dest) == STRICT_LOW_PART
+ || GET_CODE (dest) == ZERO_EXTRACT
+ || GET_CODE (dest) == SIGN_EXTRACT)
+ dest = XEXP (dest, 0);
+
+ if (GET_CODE (dest) == MEM
+ || GET_CODE (dest) == UNSPEC
+ || GET_CODE (dest) == UNSPEC_VOLATILE)
+ *inherently_necessary_set_p = 1;
+}
+
/* Mark X as inherently necessary if appropriate. For example,
function calls and storing values into memory are inherently
necessary. This function is to be used with for_each_rtx ().
find_inherently_necessary (x)
rtx x;
{
- rtx pattern;
if (x == NULL_RTX)
return 0;
else if (inherently_necessary_register (x))
switch (GET_CODE (x))
{
case CALL_INSN:
- case CODE_LABEL:
- case NOTE:
case BARRIER:
return !0;
- break;
+ case CODE_LABEL:
+ case NOTE:
+ return 0;
case JUMP_INSN:
return JUMP_TABLE_DATA_P (x) || computed_jump_p (x) != 0;
- break;
case INSN:
- pattern = PATTERN (x);
- switch (GET_CODE (pattern))
- {
- case SET:
- case PRE_DEC:
- case PRE_INC:
- case POST_DEC:
- case POST_INC:
- return GET_CODE (SET_DEST (pattern)) == MEM;
- case CALL:
- case RETURN:
- case USE:
- case CLOBBER:
- return !0;
- break;
- case ASM_INPUT:
- /* We treat assembler instructions as inherently
- necessary, and we hope that its operands do not need to
- be propagated. */
- return !0;
- break;
- default:
- return 0;
- }
+ {
+ int inherently_necessary_set = 0;
+ note_stores (PATTERN (x),
+ note_inherently_necessary_set,
+ &inherently_necessary_set);
+
+ /* If we found an inherently necessary set or an asm
+ instruction, then we consider this insn inherently
+ necessary. */
+ return (inherently_necessary_set
+ || GET_CODE (PATTERN (x)) == ASM_INPUT
+ || asm_noperands (PATTERN (x)) >= 0);
+ }
default:
/* Found an impossible insn type. */
abort();
basic_block bb;
if (!insn)
abort ();
+
+ /* Do not actually delete anything that is not an INSN.
+
+ We can get here because we only consider INSNs as
+ potentially necessary. We leave it to later passes
+ to remove unnecessary notes, unused labels, etc. */
+ if (! INSN_P (insn))
+ return;
+
bb = BLOCK_FOR_INSN (insn);
if (!bb)
abort ();
/* Perform the dead-code elimination. */
void
-eliminate_dead_code ()
+ssa_eliminate_dead_code ()
{
int i;
rtx insn;
&propagate_necessity_through_operand,
(PTR) &unprocessed_instructions);
+ /* PHI nodes are somewhat special in that each PHI alternative
+ has data and control dependencies. The data dependencies
+ are handled via propagate_necessity_through_operand. We
+ handle the control dependency here.
+
+ We consider the control dependent edges leading to the
+ predecessor block associated with each PHI alternative
+ as necessary. */
+ if (PHI_NODE_P (current_instruction))
+ {
+ rtvec phi_vec = XVEC (SET_SRC (PATTERN (current_instruction)), 0);
+ int num_elem = GET_NUM_ELEM (phi_vec);
+ int v;
+
+ for (v = num_elem - 2; v >= 0; v -= 2)
+ {
+ basic_block bb;
+
+ bb = BASIC_BLOCK (INTVAL (RTVEC_ELT (phi_vec, v + 1)));
+ EXECUTE_IF_CONTROL_DEPENDENT
+ (cdbte, bb->end, edge_number,
+ {
+ rtx jump_insn;
+
+ jump_insn = (INDEX_EDGE_PRED_BB (el, edge_number))->end;
+ if (((GET_CODE (jump_insn) == JUMP_INSN))
+ && UNNECESSARY_P (jump_insn))
+ {
+ RESURRECT_INSN (jump_insn);
+ VARRAY_PUSH_RTX (unprocessed_instructions, jump_insn);
+ }
+ });
+
+ }
+ }
}
}
{
if (any_condjump_p (insn))
{
- /* Convert unnecessary conditional insn to an unconditional
- jump to immediate postdominator block. */
- rtx old_label = JUMP_LABEL (insn);
- int pdom_block_number =
- find_pdom (pdom, BLOCK_FOR_INSN (insn))->index;
-
- /* Prevent the conditional jump's label from being deleted so
- we do not have to modify the basic block structure. */
- ++LABEL_NUSES (old_label);
-
- if (pdom_block_number != EXIT_BLOCK
- && pdom_block_number != INVALID_BLOCK)
+ basic_block bb = BLOCK_FOR_INSN (insn);
+ basic_block pdom_bb = find_pdom (pdom, bb);
+ rtx lbl;
+ edge e;
+
+ /* Egad. The immediate post dominator is the exit block. We
+ would like to optimize this conditional jump to jump directly
+ to the exit block. That can be difficult as we may not have
+ a suitable CODE_LABEL that allows us to fall unmolested into
+ the exit block.
+
+ So, we just delete the conditional branch by turning it into
+ a deleted note. That is safe, but just not as optimal as
+ it could be. */
+ if (pdom_bb == EXIT_BLOCK_PTR)
{
- rtx lbl = find_block_label (BASIC_BLOCK (pdom_block_number));
- rtx new_jump = emit_jump_insn_before (gen_jump (lbl), insn);
-
- /* Let jump know that label is in use. */
- JUMP_LABEL (new_jump) = lbl;
- ++LABEL_NUSES (lbl);
-
- delete_insn_bb (insn);
-
- /* A conditional branch is unnecessary if and only if any
- block control-dependent on it is unnecessary. Thus,
- any phi nodes in these unnecessary blocks are also
- removed and these nodes need not be updated. */
-
- /* A barrier must follow any unconditional jump. Barriers
- are not in basic blocks so this must occur after
- deleting the conditional jump. */
- emit_barrier_after (new_jump);
+ /* Since we're going to just delete the branch, we need
+ look at all the edges and remove all those which are not
+ a fallthru edge. */
+ e = bb->succ;
+ while (e)
+ {
+ edge temp = e;
+
+ e = e->succ_next;
+ if ((temp->flags & EDGE_FALLTHRU) == 0)
+ {
+ /* We've found a non-fallthru edge, find any PHI nodes
+ at the target and clean them up. */
+ if (temp->dest != EXIT_BLOCK_PTR)
+ {
+ rtx insn
+ = first_insn_after_basic_block_note (temp->dest);
+
+ while (PHI_NODE_P (insn))
+ {
+ remove_phi_alternative (PATTERN (insn), temp->src);
+ insn = NEXT_INSN (insn);
+ }
+ }
+
+ remove_edge (temp);
+ }
+ }
+
+ /* Now "delete" the conditional jump. */
+ PUT_CODE (insn, NOTE);
+ NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
+ continue;
+ }
+
+ /* We've found a conditional branch that is unnecessary.
+
+ First, remove all outgoing edges from this block, updating
+ PHI nodes as appropriate. */
+ e = bb->succ;
+ while (e)
+ {
+ edge temp = e;
+
+ e = e->succ_next;
+
+ if (temp->flags & EDGE_ABNORMAL)
+ continue;
+
+ /* We found an edge that is not executable. First simplify
+ the PHI nodes in the target block. */
+ if (temp->dest != EXIT_BLOCK_PTR)
+ {
+ rtx insn = first_insn_after_basic_block_note (temp->dest);
+
+ while (PHI_NODE_P (insn))
+ {
+ remove_phi_alternative (PATTERN (insn), temp->src);
+ insn = NEXT_INSN (insn);
+ }
+ }
+
+ remove_edge (temp);
}
- else
- /* The block drops off the end of the function and the
- ending conditional jump is not needed. */
- delete_insn_bb (insn);
+
+ /* Create an edge from this block to the post dominator.
+ What about the PHI nodes at the target? */
+ make_edge (NULL, bb, pdom_bb, 0);
+
+ /* Third, transform this insn into an unconditional
+ jump to the label for the immediate postdominator. */
+ lbl = find_block_label (pdom_bb);
+ SET_SRC (PATTERN (insn)) = gen_rtx_LABEL_REF (VOIDmode, lbl);
+ INSN_CODE (insn) = -1;
+ JUMP_LABEL (insn) = lbl;
+ LABEL_NUSES (lbl)++;
+
+ /* A barrier must follow any unconditional jump. Barriers
+ are not in basic blocks so this must occur after
+ deleting the conditional jump. */
+ emit_barrier_after (insn);
}
else if (!JUMP_P (insn))
delete_insn_bb (insn);
/* Remove fake edges from the CFG. */
remove_fake_edges ();
+ /* Find any blocks with no successors and ensure they are followed
+ by a BARRIER. delete_insn has the nasty habit of deleting barriers
+ when deleting insns. */
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ basic_block bb = BASIC_BLOCK (i);
+
+ if (bb->succ == NULL)
+ {
+ rtx next = NEXT_INSN (bb->end);
+
+ if (!next || GET_CODE (next) != BARRIER)
+ emit_barrier_after (bb->end);
+ }
+ }
/* Release allocated memory. */
for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
RESURRECT_INSN (insn);
OSDN Git Service
