From b62c888152fb7d3245bbea7464c50aef8fe1c8fa Mon Sep 17 00:00:00 2001 From: Jeffrey A Law Date: Fri, 6 Jul 2001 18:19:47 +0000 Subject: [PATCH] basic-block.h (first_insn_after_basic_block_note): Declare. * 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. From-SVN: r43816 --- gcc/ChangeLog | 13 +++++ gcc/basic-block.h | 2 +- gcc/flow.c | 22 +++++++ gcc/ssa-dce.c | 144 +++++++++++++++++++++++++++++++++++----------- gcc/ssa.c | 24 -------- 5 files changed, 145 insertions(+), 60 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 3e8e968e6d0..c60c6035eba 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,16 @@ +Fri Jul 6 11:47:59 2001 Jeffrey A Law (law@cygnus.com) + + * 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. + 2001-07-06 Zack Weinberg * varray.c (varray_check_failed): Use internal_error. diff --git a/gcc/basic-block.h b/gcc/basic-block.h index 23e1e16511b..256492ebfb2 100644 --- a/gcc/basic-block.h +++ b/gcc/basic-block.h @@ -294,7 +294,7 @@ extern int flow_depth_first_order_compute PARAMS ((int *, int *)); 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 diff --git a/gcc/flow.c b/gcc/flow.c index ab1bb7f12fa..e578b504c42 100644 --- a/gcc/flow.c +++ b/gcc/flow.c @@ -1088,6 +1088,28 @@ create_basic_block (index, head, end, bb_note) 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. */ diff --git a/gcc/ssa-dce.c b/gcc/ssa-dce.c index 76a5162e159..142126baa2d 100644 --- a/gcc/ssa-dce.c +++ b/gcc/ssa-dce.c @@ -370,17 +370,15 @@ find_inherently_necessary (x) return !0; else switch (GET_CODE (x)) - { + { case CALL_INSN: + case BARRIER: 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; @@ -626,50 +624,126 @@ ssa_eliminate_dead_code () { 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) + { + /* 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) { - rtx lbl = find_block_label (BASIC_BLOCK (pdom_block_number)); - rtx new_jump = emit_jump_insn_before (gen_jump (lbl), insn); + edge temp = e; - /* Let jump know that label is in use. */ - JUMP_LABEL (new_jump) = lbl; - ++LABEL_NUSES (lbl); + e = e->succ_next; - delete_insn_bb (insn); + if (temp->flags & EDGE_ABNORMAL) + continue; - /* 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. */ + /* 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); - /* 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); + 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); diff --git a/gcc/ssa.c b/gcc/ssa.c index 97e259b3d9f..cad10ca71a6 100644 --- a/gcc/ssa.c +++ b/gcc/ssa.c @@ -162,8 +162,6 @@ struct rename_context; 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 @@ -633,28 +631,6 @@ compute_iterated_dominance_frontiers (idfs, frontiers, evals, 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. */ static void -- 2.30.2