This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
SSA-DCE
- To: gcc-patches at gcc dot gnu dot org
- Subject: SSA-DCE
- From: law at redhat dot com
- Date: Thu, 05 Jul 2001 20:11:02 -0700
- Reply-to: law at redhat dot com
The SSA-DCE pass fails to update the CFG when it finds conditional
branches which are dead. This was until recently OK from a correctness
standpoint, but the recent improvements to cleanup_cfg have tightened
the need to keep the insn stream and the CFG in sync with each other.
I was going to tackle this problem eventually, but the cleanup_cfg
changes just made me tackle it earlier. And (of course) when we remove
dead edges from the CFG, we remove dead alternatives from PHI nodes.
Additionally, I noticed that we were leaving in unreachable epilogues
rather often. It turns out that delete_insn will delete any BARRIER
which immediately followed the insn that is being deleted. This patch
includes a change to add any missing barriers after blocks which have
no successors.
I bootstrapped this patch on ia64-linux with a modified tree which
enables SSA and SSA-DCE by default.
* basic-block.h (first_insn_after_basic_block_note): Declare.
* flow.c (first_insn_after_basic_block_note): Define. Moved
from...
* ssa.c (first_insn_after_basic_block_note): Remove.
* ssa-dce.c (find_inherently_necessary): Consider BARRIERs
necessary.
(ssa_eliminate_dead_code): Properly update the CFG and PHI
nodes when we find a dead conditional branch. Insert BARRIERs
after any blocks with no successors, but which do not have
any BARRIERs.
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/basic-block.h,v
retrieving revision 1.97
diff -c -3 -p -r1.97 basic-block.h
*** basic-block.h 2001/06/28 22:11:18 1.97
--- basic-block.h 2001/07/06 02:50:54
*************** extern int flow_depth_first_order_comput
*** 294,300 ****
extern void dump_edge_info PARAMS ((FILE *, edge, int));
extern void clear_edges PARAMS ((void));
extern void mark_critical_edges PARAMS ((void));
!
/* Structure to hold information for each natural loop. */
struct loop
--- 294,300 ----
extern void dump_edge_info PARAMS ((FILE *, edge, int));
extern void clear_edges PARAMS ((void));
extern void mark_critical_edges PARAMS ((void));
! extern rtx first_insn_after_basic_block_note PARAMS ((basic_block));
/* Structure to hold information for each natural loop. */
struct loop
Index: flow.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/flow.c,v
retrieving revision 1.413
diff -c -3 -p -r1.413 flow.c
*** flow.c 2001/07/05 20:54:29 1.413
--- flow.c 2001/07/06 02:51:22
*************** create_basic_block (index, head, end, bb
*** 1088,1093 ****
--- 1088,1115 ----
bb->aux = bb;
}
+ /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
+ note associated with the BLOCK. */
+
+ rtx
+ first_insn_after_basic_block_note (block)
+ basic_block block;
+ {
+ rtx insn;
+
+ /* Get the first instruction in the block. */
+ insn = block->head;
+
+ if (insn == NULL_RTX)
+ return NULL_RTX;
+ if (GET_CODE (insn) == CODE_LABEL)
+ insn = NEXT_INSN (insn);
+ if (!NOTE_INSN_BASIC_BLOCK_P (insn))
+ abort ();
+
+ return NEXT_INSN (insn);
+ }
+
/* Records the basic block struct in BB_FOR_INSN, for every instruction
indexed by INSN_UID. MAX is the size of the array. */
Index: ssa-dce.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/ssa-dce.c,v
retrieving revision 1.6
diff -c -3 -p -r1.6 ssa-dce.c
*** ssa-dce.c 2001/07/02 14:46:11 1.6
--- ssa-dce.c 2001/07/06 02:51:25
*************** find_inherently_necessary (x)
*** 370,386 ****
return !0;
else
switch (GET_CODE (x))
! {
case CALL_INSN:
return !0;
case CODE_LABEL:
case NOTE:
- case BARRIER:
return 0;
- break;
case JUMP_INSN:
return JUMP_TABLE_DATA_P (x) || computed_jump_p (x) != 0;
- break;
case INSN:
{
int inherently_necessary_set = 0;
--- 370,384 ----
return !0;
else
switch (GET_CODE (x))
! {
case CALL_INSN:
+ case BARRIER:
return !0;
case CODE_LABEL:
case NOTE:
return 0;
case JUMP_INSN:
return JUMP_TABLE_DATA_P (x) || computed_jump_p (x) != 0;
case INSN:
{
int inherently_necessary_set = 0;
*************** ssa_eliminate_dead_code ()
*** 626,675 ****
{
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)
{
! 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);
}
! else
! /* The block drops off the end of the function and the
! ending conditional jump is not needed. */
! delete_insn_bb (insn);
}
else if (!JUMP_P (insn))
delete_insn_bb (insn);
});
!
/* Remove fake edges from the CFG. */
remove_fake_edges ();
/* Release allocated memory. */
for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
RESURRECT_INSN (insn);
--- 625,750 ----
{
if (any_condjump_p (insn))
{
! 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)
! {
! /* 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);
}
!
! /* 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);
Index: ssa.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/ssa.c,v
retrieving revision 1.30
diff -c -3 -p -r1.30 ssa.c
*** ssa.c 2001/06/22 22:20:42 1.30
--- ssa.c 2001/07/06 02:51:31
*************** struct rename_context;
*** 162,169 ****
static inline rtx * phi_alternative
PARAMS ((rtx, int));
- static rtx first_insn_after_basic_block_note
- PARAMS ((basic_block));
static void compute_dominance_frontiers_1
PARAMS ((sbitmap *frontiers, int *idom, int bb, sbitmap done));
static void find_evaluations_1
--- 162,167 ----
*************** compute_iterated_dominance_frontiers (id
*** 631,658 ****
"Iterated dominance frontier: %d passes on %d regs.\n",
passes, nregs);
}
- }
-
- /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
- note associated with the BLOCK. */
-
- static rtx
- first_insn_after_basic_block_note (block)
- basic_block block;
- {
- rtx insn;
-
- /* Get the first instruction in the block. */
- insn = block->head;
-
- if (insn == NULL_RTX)
- return NULL_RTX;
- if (GET_CODE (insn) == CODE_LABEL)
- insn = NEXT_INSN (insn);
- if (!NOTE_INSN_BASIC_BLOCK_P (insn))
- abort ();
-
- return NEXT_INSN (insn);
}
/* Insert the phi nodes. */
--- 629,634 ----