From 6b24c25948265c30431460146bc6f43ee9a34c23 Mon Sep 17 00:00:00 2001 From: Jan Hubicka Date: Sun, 22 Jul 2001 23:42:35 +0200 Subject: [PATCH] basic-block.h (redirect_edge_and_branch_force, [...]): Declare. * basic-block.h (redirect_edge_and_branch_force, redirect_edge_and_branch, block_label, forwarder_block_p): Declare. * flow.c (redirect_edge_and_branch_force, redirect_edge_and_branch, block_label, forwarder_block_p): Make global. (redirect_edge_and_branch_force): Fix copying of lifeness information. (block_label): Handle EXIT_BLOCK_PTR by returning NULL. * ifcvt.c (dead_or_predictable): Take BB as an new destionation instead of label; update CFG after transformation. (find_if_case_1): Update call, use redirect_edge_and_branch_force for finishing the transformation; handle even case where ELSE does not follow THEN. (find_if_case_2): Update call of dead_or_predictable; simplify CFG update. * emit-rtl.c (split_branch_probability): New global variable. (try_split): Take care to set split_branch_probability and create REG_BR_PROB note for new jump insns. * md.texi (define_split): Document new feature. * i386.c (ix86_split_fp_branch): Redistribute branch probability notes. From-SVN: r44249 --- gcc/ChangeLog | 23 +++++++++++ gcc/basic-block.h | 5 +++ gcc/config/i386/i386.c | 72 ++++++++++++++++++++++++----------- gcc/doc/md.texi | 16 ++++++++ gcc/emit-rtl.c | 46 ++++++++++++++++++---- gcc/flow.c | 16 ++++---- gcc/ifcvt.c | 86 +++++++++++++++++++----------------------- gcc/rtl.h | 1 + 8 files changed, 178 insertions(+), 87 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 29f9d564e6d..98980849931 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,26 @@ +Sun Jul 22 23:28:56 CEST 2001 Jan Hubicka + + * basic-block.h (redirect_edge_and_branch_force, + redirect_edge_and_branch, block_label, forwarder_block_p): Declare. + * flow.c (redirect_edge_and_branch_force, + redirect_edge_and_branch, block_label, forwarder_block_p): Make global. + (redirect_edge_and_branch_force): Fix copying of lifeness information. + (block_label): Handle EXIT_BLOCK_PTR by returning NULL. + * ifcvt.c (dead_or_predictable): Take BB as an new destionation + instead of label; update CFG after transformation. + (find_if_case_1): Update call, use redirect_edge_and_branch_force + for finishing the transformation; handle even case where ELSE + does not follow THEN. + (find_if_case_2): Update call of dead_or_predictable; simplify + CFG update. + + * emit-rtl.c (split_branch_probability): New global variable. + (try_split): Take care to set split_branch_probability and + create REG_BR_PROB note for new jump insns. + * md.texi (define_split): Document new feature. + + * i386.c (ix86_split_fp_branch): Redistribute branch probability notes. + 2001-07-22 Neil Booth * varasm.c: Don't inlcude dbxout.h, sdbout.h or xcoffout.h. diff --git a/gcc/basic-block.h b/gcc/basic-block.h index 5b210fb981b..6a6039eff04 100644 --- a/gcc/basic-block.h +++ b/gcc/basic-block.h @@ -597,6 +597,11 @@ extern void debug_regset PARAMS ((regset)); extern void allocate_reg_life_data PARAMS ((void)); extern void allocate_bb_life_data PARAMS ((void)); extern void find_unreachable_blocks PARAMS ((void)); +extern basic_block redirect_edge_and_branch_force PARAMS ((edge, basic_block)); +extern bool redirect_edge_and_branch PARAMS ((edge, basic_block)); +extern rtx block_label PARAMS ((basic_block)); +extern bool forwarder_block_p PARAMS ((basic_block)); + /* This function is always defined so it can be called from the debugger, and it is declared extern so we don't get warnings about diff --git a/gcc/config/i386/i386.c b/gcc/config/i386/i386.c index 948fde26d84..821daa696f2 100644 --- a/gcc/config/i386/i386.c +++ b/gcc/config/i386/i386.c @@ -6267,6 +6267,8 @@ ix86_split_fp_branch (code, op1, op2, target1, target2, tmp) rtx second, bypass; rtx label = NULL_RTX; rtx condition; + int bypass_probability = -1, second_probability = -1, probability = -1; + rtx i; if (target2 != pc_rtx) { @@ -6278,35 +6280,59 @@ ix86_split_fp_branch (code, op1, op2, target1, target2, tmp) condition = ix86_expand_fp_compare (code, op1, op2, tmp, &second, &bypass); + + if (split_branch_probability >= 0) + { + /* Distribute the probabilities across the jumps. + Assume the BYPASS and SECOND to be always test + for UNORDERED. */ + probability = split_branch_probability; + + /* Value of 1 is low enought to make no need for probability + to be updated. Later we may run some experiments and see + if unordered values are more frequent in practice. */ + if (bypass) + bypass_probability = 1; + if (second) + second_probability = 1; + } if (bypass != NULL_RTX) { label = gen_label_rtx (); - emit_jump_insn (gen_rtx_SET + i = emit_jump_insn (gen_rtx_SET + (VOIDmode, pc_rtx, + gen_rtx_IF_THEN_ELSE (VOIDmode, + bypass, + gen_rtx_LABEL_REF (VOIDmode, + label), + pc_rtx))); + if (bypass_probability >= 0) + REG_NOTES (i) + = gen_rtx_EXPR_LIST (REG_BR_PROB, + GEN_INT (bypass_probability), + REG_NOTES (i)); + } + i = emit_jump_insn (gen_rtx_SET (VOIDmode, pc_rtx, gen_rtx_IF_THEN_ELSE (VOIDmode, - bypass, - gen_rtx_LABEL_REF (VOIDmode, - label), - pc_rtx))); - } - /* AMD Athlon and probably other CPUs too have fast bypass path between the - comparison and first branch. The second branch takes longer to execute - so place first branch the worse predicable one if possible. */ - if (second != NULL_RTX - && (GET_CODE (second) == UNORDERED || GET_CODE (second) == ORDERED)) - { - rtx tmp = condition; - condition = second; - second = tmp; - } - emit_jump_insn (gen_rtx_SET - (VOIDmode, pc_rtx, - gen_rtx_IF_THEN_ELSE (VOIDmode, - condition, target1, target2))); + condition, target1, target2))); + if (probability >= 0) + REG_NOTES (i) + = gen_rtx_EXPR_LIST (REG_BR_PROB, + GEN_INT (probability), + REG_NOTES (i)); if (second != NULL_RTX) - emit_jump_insn (gen_rtx_SET - (VOIDmode, pc_rtx, - gen_rtx_IF_THEN_ELSE (VOIDmode, second, target1, target2))); + { + i = emit_jump_insn (gen_rtx_SET + (VOIDmode, pc_rtx, + gen_rtx_IF_THEN_ELSE (VOIDmode, second, target1, + target2))); + if (second_probability >= 0) + REG_NOTES (i) + = gen_rtx_EXPR_LIST (REG_BR_PROB, + GEN_INT (second_probability), + REG_NOTES (i)); + } if (label != NULL_RTX) emit_label (label); } diff --git a/gcc/doc/md.texi b/gcc/doc/md.texi index 98752a6afe8..0a79f3471ff 100644 --- a/gcc/doc/md.texi +++ b/gcc/doc/md.texi @@ -3805,6 +3805,22 @@ insns that don't. Instead, write two separate @code{define_split} definitions, one for the insns that are valid and one for the insns that are not valid. +The splitter is allowed to split jump instructions into sequence of +jumps or create new jumps in while splitting non-jump instructions. As +the central flowgraph and branch prediction information needs to be updated, +several restriction apply. + +Splitting of jump instruction into sequence that over by another jump +instruction is always valid, as compiler expect identical behaviour of new +jump. When new sequence contains multiple jump instructions or new labels, +more assistance is needed. Splitter is required to create only unconditional +jumps, or simple conditional jump instructions. Additionally it must attach a +@code{REG_BR_PROB} note to each conditional jump. An global variable +@code{split_branch_probability} hold the probability of original branch in case +it was an simple conditional jump, @minus{}1 otherwise. To simplify +recomputing of edge frequencies, new sequence is required to have only +forward jumps to the newly created labels. + For the common case where the pattern of a define_split exactly matches the pattern of a define_insn, use @code{define_insn_and_split}. It looks like this: diff --git a/gcc/emit-rtl.c b/gcc/emit-rtl.c index 58e264f0ba3..5c021772a34 100644 --- a/gcc/emit-rtl.c +++ b/gcc/emit-rtl.c @@ -185,6 +185,10 @@ static int const_int_htab_eq PARAMS ((const void *, static int rtx_htab_mark_1 PARAMS ((void **, void *)); static void rtx_htab_mark PARAMS ((void *)); +/* Probability of the conditional branch currently proceeded by try_split. + Set to -1 otherwise. */ +int split_branch_probability = -1; + /* Returns a hash code for X (which is a really a CONST_INT). */ @@ -2486,9 +2490,19 @@ try_split (pat, trial, last) { rtx before = PREV_INSN (trial); rtx after = NEXT_INSN (trial); - rtx seq = split_insns (pat, trial); int has_barrier = 0; rtx tem; + rtx note, seq; + int probability; + + if (any_condjump_p (trial) + && (note = find_reg_note (trial, REG_BR_PROB, 0))) + split_branch_probability = INTVAL (XEXP (note, 0)); + probability = split_branch_probability; + + seq = split_insns (pat, trial); + + split_branch_probability = -1; /* If we are splitting a JUMP_INSN, it might be followed by a BARRIER. We may need to handle this specially. */ @@ -2505,7 +2519,7 @@ try_split (pat, trial, last) it, in turn, will be split (SFmode on the 29k is an example). */ if (GET_CODE (seq) == SEQUENCE) { - int i; + int i, njumps = 0; rtx eh_note; /* Avoid infinite loop if any insn of the result matches @@ -2518,9 +2532,27 @@ try_split (pat, trial, last) /* Mark labels. */ for (i = XVECLEN (seq, 0) - 1; i >= 0; i--) if (GET_CODE (XVECEXP (seq, 0, i)) == JUMP_INSN) - mark_jump_label (PATTERN (XVECEXP (seq, 0, i)), - XVECEXP (seq, 0, i), 0); - + { + rtx insn = XVECEXP (seq, 0, i); + mark_jump_label (PATTERN (insn), + XVECEXP (seq, 0, i), 0); + njumps++; + if (probability != -1 + && any_condjump_p (insn) + && !find_reg_note (insn, REG_BR_PROB, 0)) + { + /* We can preserve the REG_BR_PROB notes only if exactly + one jump is created, otherwise the machinde description + is responsible for this step using + split_branch_probability variable. */ + if (njumps != 1) + abort (); + REG_NOTES (insn) + = gen_rtx_EXPR_LIST (REG_BR_PROB, + GEN_INT (probability), + REG_NOTES (insn)); + } + } /* If we are splitting a CALL_INSN, look for the CALL_INSN in SEQ and copy our CALL_INSN_FUNCTION_USAGE to it. */ if (GET_CODE (trial) == CALL_INSN) @@ -2577,8 +2609,8 @@ try_split (pat, trial, last) /* Return either the first or the last insn, depending on which was requested. */ return last - ? (after ? prev_active_insn (after) : last_insn) - : next_active_insn (before); + ? (after ? PREV_INSN (after) : last_insn) + : NEXT_INSN (before); } return trial; diff --git a/gcc/flow.c b/gcc/flow.c index fb054e4b411..a6a63e5a3ae 100644 --- a/gcc/flow.c +++ b/gcc/flow.c @@ -393,7 +393,6 @@ static int merge_blocks_move_successor_nojumps PARAMS ((basic_block, static int merge_blocks PARAMS ((edge,basic_block,basic_block, int)); static bool try_optimize_cfg PARAMS ((int)); -static bool forwarder_block_p PARAMS ((basic_block)); static bool can_fallthru PARAMS ((basic_block, basic_block)); static bool try_redirect_by_replacing_jump PARAMS ((edge, basic_block)); static bool try_simplify_condjump PARAMS ((basic_block)); @@ -485,9 +484,6 @@ static void flow_loops_tree_build PARAMS ((struct loops *)); static int flow_loop_level_compute PARAMS ((struct loop *, int)); static int flow_loops_level_compute PARAMS ((struct loops *)); static void find_sub_basic_blocks PARAMS ((basic_block)); -static bool redirect_edge_and_branch PARAMS ((edge, basic_block)); -static basic_block redirect_edge_and_branch_force PARAMS ((edge, basic_block)); -static rtx block_label PARAMS ((basic_block)); /* Find basic blocks of the current function. F is the first insn of the function and NREGS the number of register @@ -1598,10 +1594,12 @@ split_block (bb, insn) } /* Return label in the head of basic block. Create one if it doesn't exist. */ -static rtx +rtx block_label (block) basic_block 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); return block->head; @@ -1609,7 +1607,7 @@ block_label (block) /* Return true if the block has no effect and only forwards control flow to its single destination. */ -static bool +bool forwarder_block_p (bb) basic_block bb; { @@ -1759,7 +1757,7 @@ try_redirect_by_replacing_jump (e, target) Return true if transformation suceeded. We still return flase in case E already destinated TARGET and we didn't managed to simplify instruction stream. */ -static bool +bool redirect_edge_and_branch (e, target) edge e; basic_block target; @@ -1867,7 +1865,7 @@ redirect_edge_and_branch (e, target) /* 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. */ -static basic_block +basic_block redirect_edge_and_branch_force (e, target) edge e; basic_block target; @@ -1937,7 +1935,7 @@ redirect_edge_and_branch_force (e, target) new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack); new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack); COPY_REG_SET (new_bb->global_live_at_start, - e->dest->global_live_at_start); + target->global_live_at_start); COPY_REG_SET (new_bb->global_live_at_end, new_bb->global_live_at_start); } diff --git a/gcc/ifcvt.c b/gcc/ifcvt.c index bdb44c41274..08ec087e4ca 100644 --- a/gcc/ifcvt.c +++ b/gcc/ifcvt.c @@ -106,7 +106,7 @@ static int find_if_case_2 PARAMS ((basic_block, edge, edge)); static int find_cond_trap PARAMS ((basic_block, edge, edge)); static int find_memory PARAMS ((rtx *, void *)); static int dead_or_predicable PARAMS ((basic_block, basic_block, - basic_block, rtx, int)); + basic_block, basic_block, int)); static void noce_emit_move_insn PARAMS ((rtx, rtx)); /* Abuse the basic_block AUX field to store the original block index, @@ -2183,9 +2183,8 @@ find_if_case_1 (test_bb, then_edge, else_edge) edge then_edge, else_edge; { basic_block then_bb = then_edge->dest; - basic_block else_bb = else_edge->dest; + basic_block else_bb = else_edge->dest, new_bb; edge then_succ = then_bb->succ; - rtx new_lab; /* THEN has one successor. */ if (!then_succ || then_succ->succ_next != NULL) @@ -2199,8 +2198,8 @@ find_if_case_1 (test_bb, then_edge, else_edge) if (then_bb->pred->pred_next != NULL) return FALSE; - /* ELSE follows THEN. (??? could be moved) */ - if (else_bb->index != then_bb->index + 1) + /* THEN must do something. */ + if (forwarder_block_p (then_bb)) return FALSE; num_possible_if_blocks++; @@ -2213,18 +2212,9 @@ find_if_case_1 (test_bb, then_edge, else_edge) if (count_bb_insns (then_bb) > BRANCH_COST) return FALSE; - /* Find the label for THEN's destination. */ - if (then_succ->dest == EXIT_BLOCK_PTR) - new_lab = NULL_RTX; - else - { - new_lab = JUMP_LABEL (then_bb->end); - if (! new_lab) - abort (); - } - /* Registers set are dead, or are predicable. */ - if (! dead_or_predicable (test_bb, then_bb, else_bb, new_lab, 1)) + if (! dead_or_predicable (test_bb, then_bb, else_bb, + then_bb->succ->dest, 1)) return FALSE; /* Conversion went ok, including moving the insns and fixing up the @@ -2235,9 +2225,17 @@ find_if_case_1 (test_bb, then_edge, else_edge) else_bb->global_live_at_start, then_bb->global_live_at_end, BITMAP_IOR); - make_edge (NULL, test_bb, then_succ->dest, 0); + new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb), else_bb); + /* Make rest of code believe that the newly created block is the THEN_BB + block we are going to remove. */ + if (new_bb) + { + new_bb->aux = then_bb->aux; + SET_UPDATE_LIFE (then_bb); + } flow_delete_block (then_bb); - tidy_fallthru_edge (else_edge, test_bb, else_bb); + /* We've possibly created jump to next insn, cleanup_cfg will solve that + later. */ num_removed_blocks++; num_updated_if_blocks++; @@ -2255,7 +2253,7 @@ find_if_case_2 (test_bb, then_edge, else_edge) basic_block then_bb = then_edge->dest; basic_block else_bb = else_edge->dest; edge else_succ = else_bb->succ; - rtx new_lab, note; + rtx note; /* ELSE has one successor. */ if (!else_succ || else_succ->succ_next != NULL) @@ -2294,27 +2292,8 @@ find_if_case_2 (test_bb, then_edge, else_edge) if (count_bb_insns (then_bb) > BRANCH_COST) return FALSE; - /* Find the label for ELSE's destination. */ - if (else_succ->dest == EXIT_BLOCK_PTR) - new_lab = NULL_RTX; - else - { - if (else_succ->flags & EDGE_FALLTHRU) - { - new_lab = else_succ->dest->head; - if (GET_CODE (new_lab) != CODE_LABEL) - abort (); - } - else - { - new_lab = JUMP_LABEL (else_bb->end); - if (! new_lab) - abort (); - } - } - /* Registers set are dead, or are predicable. */ - if (! dead_or_predicable (test_bb, else_bb, then_bb, new_lab, 0)) + if (! dead_or_predicable (test_bb, else_bb, then_bb, else_succ->dest, 0)) return FALSE; /* Conversion went ok, including moving the insns and fixing up the @@ -2325,8 +2304,6 @@ find_if_case_2 (test_bb, then_edge, else_edge) then_bb->global_live_at_start, else_bb->global_live_at_end, BITMAP_IOR); - remove_edge (else_edge); - make_edge (NULL, test_bb, else_succ->dest, 0); flow_delete_block (else_bb); num_removed_blocks++; @@ -2360,10 +2337,10 @@ find_memory (px, data) static int dead_or_predicable (test_bb, merge_bb, other_bb, new_dest, reversep) basic_block test_bb, merge_bb, other_bb; - rtx new_dest; + basic_block new_dest; int reversep; { - rtx head, end, jump, earliest, old_dest; + rtx head, end, jump, earliest, old_dest, new_label; jump = test_bb->end; @@ -2548,9 +2525,10 @@ dead_or_predicable (test_bb, merge_bb, other_bb, new_dest, reversep) change group management. */ old_dest = JUMP_LABEL (jump); + new_label = block_label (new_dest); if (reversep - ? ! invert_jump_1 (jump, new_dest) - : ! redirect_jump_1 (jump, new_dest)) + ? ! invert_jump_1 (jump, new_label) + : ! redirect_jump_1 (jump, new_label)) goto cancel; if (! apply_change_group ()) @@ -2558,13 +2536,25 @@ dead_or_predicable (test_bb, merge_bb, other_bb, new_dest, reversep) if (old_dest) LABEL_NUSES (old_dest) -= 1; - if (new_dest) - LABEL_NUSES (new_dest) += 1; - JUMP_LABEL (jump) = new_dest; + if (new_label) + LABEL_NUSES (new_label) += 1; + JUMP_LABEL (jump) = new_label; if (reversep) invert_br_probabilities (jump); + redirect_edge_succ (BRANCH_EDGE (test_bb), new_dest); + if (reversep) + { + gcov_type count, probability; + count = BRANCH_EDGE (test_bb)->count; + BRANCH_EDGE (test_bb)->count = FALLTHRU_EDGE (test_bb)->count; + FALLTHRU_EDGE (test_bb)->count = count; + probability = BRANCH_EDGE (test_bb)->probability; + BRANCH_EDGE (test_bb)->probability = FALLTHRU_EDGE (test_bb)->probability; + FALLTHRU_EDGE (test_bb)->probability = probability; + } + /* Move the insns out of MERGE_BB to before the branch. */ if (head != NULL) { diff --git a/gcc/rtl.h b/gcc/rtl.h index 8c8a2db7854..e9227b14079 100644 --- a/gcc/rtl.h +++ b/gcc/rtl.h @@ -1301,6 +1301,7 @@ extern rtx *find_constant_term_loc PARAMS ((rtx *)); /* In emit-rtl.c */ extern rtx try_split PARAMS ((rtx, rtx, int)); +extern int split_branch_probability; /* In unknown file */ extern rtx split_insns PARAMS ((rtx, rtx)); -- 2.30.2