From mboxrd@z Thu Jan 1 00:00:00 1970 From: Jan Hubicka To: Richard Henderson , Jan Hubicka , Brad Lucier , gcc-patches@gcc.gnu.org, gcc@gcc.gnu.org Subject: Re: Timing information for CFG manipulations Date: Wed, 17 Oct 2001 15:38:00 -0000 Message-id: <20011018003755.B382@atrey.karlin.mff.cuni.cz> References: <200110140332.f9E3W6I16651@banach.math.purdue.edu> <20011016170137.D32633@atrey.karlin.mff.cuni.cz> <20011017133829.A6498@redhat.com> X-SW-Source: 2001-10/msg00996.html > On Tue, Oct 16, 2001 at 05:01:37PM +0200, Jan Hubicka wrote: > > * cfgrtl.c (commite_one_edge_insertion): Create an bitmap to pass > > to find_sub_basic_blocks. > > I don't especially like the feature that commite_one_edge_insertion > has to do all sorts of extra work to update one block. Perhaps you > should create a find_many_sub_basic_blocks that takes the sbitmap, > but find_sub_basic_blocks continues to update one block. > Done. Thu Oct 18 01:47:20 CEST 2001 Jan Hubicka * basic-block.h (find_sub_basic_blocks): Use sbitmap parameter. * cfgbuild.c (find_bb_boundaries, compute_outgoing_frequencies): Break out from ... (find_sub_basic_blocks): ... here; (find_many_sub_basic_blocks): New. * recog.c (split_all_insns): Update find_sub_basic_blocks call. *** cfgbuild.c.b Thu Oct 18 01:34:54 2001 --- cfgbuild.c Thu Oct 18 01:46:25 2001 *************** static void make_edges PARAMS ((rtx, i *** 55,60 **** --- 55,62 ---- static void make_label_edge PARAMS ((sbitmap *, basic_block, rtx, int)); static void make_eh_edge PARAMS ((sbitmap *, basic_block, rtx)); + static void find_bb_boundaries PARAMS ((basic_block)); + static void compute_outgoing_frequencies PARAMS ((basic_block)); /* Count the basic blocks of the function. */ *************** make_edges (label_value_list, min, max, *** 246,252 **** } /* By nature of the way these get numbered, block 0 is always the entry. */ ! cached_make_edge (edge_cache, ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU); for (i = min; i <= max; ++i) { --- 248,255 ---- } /* By nature of the way these get numbered, block 0 is always the entry. */ ! if (min == 0) ! cached_make_edge (edge_cache, ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU); for (i = min; i <= max; ++i) { *************** find_basic_blocks (f, nregs, file) *** 663,680 **** timevar_pop (TV_CFG); } ! /* Assume that someone emitted code with control flow instructions to the ! basic block. Update the data structure. */ ! void ! find_sub_basic_blocks (bb) basic_block bb; { rtx insn = bb->head; rtx end = bb->end; rtx flow_transfer_insn = NULL_RTX; edge fallthru = NULL; - basic_block first_bb = bb; - int i; if (insn == bb->end) return; --- 666,692 ---- timevar_pop (TV_CFG); } ! /* State of basic block as seen by find_sub_basic_blocks. */ ! enum state ! { ! BLOCK_NEW = 0, ! BLOCK_ORIGINAL, ! BLOCK_TO_SPLIT ! }; ! #define STATE(bb) (enum state)(size_t)(bb)->aux ! #define SET_STATE(bb, state) (bb)->aux = (void *)(state) ! ! /* Scan basic block BB for possible BB boundaries inside the block ! and create new basic blocks in the progress. */ ! ! static void ! find_bb_boundaries (bb) basic_block bb; { rtx insn = bb->head; rtx end = bb->end; rtx flow_transfer_insn = NULL_RTX; edge fallthru = NULL; if (insn == bb->end) return; *************** find_sub_basic_blocks (bb) *** 694,700 **** abort (); break; ! /* On code label, split current basic block. */ case CODE_LABEL: fallthru = split_block (bb, PREV_INSN (insn)); if (flow_transfer_insn) --- 706,712 ---- abort (); break; ! /* On code label, split current basic block. */ case CODE_LABEL: fallthru = split_block (bb, PREV_INSN (insn)); if (flow_transfer_insn) *************** find_sub_basic_blocks (bb) *** 725,731 **** { if (GET_CODE (PATTERN (insn)) == ADDR_VEC || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC) ! abort(); flow_transfer_insn = insn; } else if (code == CALL_INSN) --- 737,743 ---- { if (GET_CODE (PATTERN (insn)) == ADDR_VEC || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC) ! abort (); flow_transfer_insn = insn; } else if (code == CALL_INSN) *************** find_sub_basic_blocks (bb) *** 764,781 **** followed by cleanup at fallthru edge, so the outgoing edges may be dead. */ purge_dead_edges (bb); /* Now re-scan and wire in all edges. This expect simple (conditional) jumps at the end of each new basic blocks. */ ! make_edges (NULL, first_bb->index, bb->index, 1); /* Update branch probabilities. Expect only (un)conditional jumps to be created with only the forward edges. */ ! for (i = first_bb->index; i <= bb->index; i++) { ! edge e,f; basic_block b = BASIC_BLOCK (i); ! if (b != first_bb) { b->count = 0; b->frequency = 0; --- 776,862 ---- followed by cleanup at fallthru edge, so the outgoing edges may be dead. */ purge_dead_edges (bb); + } + + /* Assume that frequency of basic block B is known. Compute frequencies + and probabilities of outgoing edges. */ + + static void + compute_outgoing_frequencies (b) + basic_block b; + { + edge e, f; + if (b->succ && b->succ->succ_next && !b->succ->succ_next->succ_next) + { + rtx note = find_reg_note (b->end, REG_BR_PROB, NULL); + int probability; + + if (!note) + return; + probability = INTVAL (XEXP (find_reg_note (b->end, + REG_BR_PROB, NULL), 0)); + e = BRANCH_EDGE (b); + e->probability = probability; + e->count = ((b->count * probability + REG_BR_PROB_BASE / 2) + / REG_BR_PROB_BASE); + f = FALLTHRU_EDGE (b); + f->probability = REG_BR_PROB_BASE - probability; + f->count = b->count - e->count; + } + if (b->succ && !b->succ->succ_next) + { + e = b->succ; + e->probability = REG_BR_PROB_BASE; + e->count = b->count; + } + } + + /* Assume that someone emitted code with control flow instructions to the + basic block. Update the data structure. */ + + void + find_many_sub_basic_blocks (blocks) + sbitmap blocks; + { + int i; + int min, max; + + for (i = 0; i < n_basic_blocks; i++) + { + SET_STATE (BASIC_BLOCK (i), + TEST_BIT (blocks, i) + ? BLOCK_TO_SPLIT : BLOCK_ORIGINAL); + } + + for (i = 0; i < n_basic_blocks; i++) + { + basic_block bb = BASIC_BLOCK (i); + if (STATE (bb) == BLOCK_TO_SPLIT) + find_bb_boundaries (bb); + } + + for (i = 0; i < n_basic_blocks; i++) + if (STATE (BASIC_BLOCK (i)) != BLOCK_ORIGINAL) + break; + min = max = i; + for (; i < n_basic_blocks; i++) + if (STATE (BASIC_BLOCK (i)) != BLOCK_ORIGINAL) + max = i; /* Now re-scan and wire in all edges. This expect simple (conditional) jumps at the end of each new basic blocks. */ ! make_edges (NULL, min, max, 1); /* Update branch probabilities. Expect only (un)conditional jumps to be created with only the forward edges. */ ! for (i = min; i <= max; i++) { ! edge e; basic_block b = BASIC_BLOCK (i); ! ! if (STATE (b) == BLOCK_ORIGINAL) ! continue; ! if (STATE (b) == BLOCK_NEW) { b->count = 0; b->frequency = 0; *************** find_sub_basic_blocks (bb) *** 785,813 **** b->frequency += EDGE_FREQUENCY (e); } } ! if (b->succ && b->succ->succ_next && !b->succ->succ_next->succ_next) ! { ! rtx note = find_reg_note (b->end, REG_BR_PROB, NULL); ! int probability; ! if (!note) ! continue; ! probability = INTVAL (XEXP (find_reg_note (b->end, ! REG_BR_PROB, ! NULL), 0)); ! e = BRANCH_EDGE (b); ! e->probability = probability; ! e->count = ((b->count * probability + REG_BR_PROB_BASE / 2) ! / REG_BR_PROB_BASE); ! f = FALLTHRU_EDGE (b); ! f->probability = REG_BR_PROB_BASE - probability; ! f->count = b->count - e->count; ! } ! if (b->succ && !b->succ->succ_next) { ! e = b->succ; ! e->probability = REG_BR_PROB_BASE; ! e->count = b->count; } } } --- 866,913 ---- b->frequency += EDGE_FREQUENCY (e); } } ! compute_outgoing_frequencies (b); ! } ! for (i = 0; i < n_basic_blocks; i++) ! SET_STATE (BASIC_BLOCK (i), 0); ! } ! /* Like above but for single basic block only. */ ! ! void ! find_sub_basic_blocks (bb) ! basic_block bb; ! { ! int i; ! int min, max; ! basic_block next = (bb->index == n_basic_blocks - 1 ! ? NULL : BASIC_BLOCK (bb->index + 1)); ! ! min = bb->index; ! find_bb_boundaries (bb); ! max = (next ? next->index : n_basic_blocks) - 1; ! ! /* Now re-scan and wire in all edges. This expect simple (conditional) ! jumps at the end of each new basic blocks. */ ! make_edges (NULL, min, max, 1); ! ! /* Update branch probabilities. Expect only (un)conditional jumps ! to be created with only the forward edges. */ ! for (i = min; i <= max; i++) ! { ! edge e; ! basic_block b = BASIC_BLOCK (i); ! ! if (i != min) { ! b->count = 0; ! b->frequency = 0; ! for (e = b->pred; e; e=e->pred_next) ! { ! b->count += e->count; ! b->frequency += EDGE_FREQUENCY (e); ! } } + compute_outgoing_frequencies (b); } } *** basic-block.h.b Thu Oct 18 01:35:12 2001 --- basic-block.h Thu Oct 18 01:35:24 2001 *************** extern bool forwarder_block_p PARAMS (( *** 642,647 **** --- 642,648 ---- extern bool purge_all_dead_edges PARAMS ((void)); extern bool purge_dead_edges PARAMS ((basic_block)); extern void find_sub_basic_blocks PARAMS ((basic_block)); + extern void find_many_sub_basic_blocks PARAMS ((sbitmap)); extern bool can_fallthru PARAMS ((basic_block, basic_block)); extern void flow_nodes_print PARAMS ((const char *, const sbitmap, FILE *)); *** recog.c.b Thu Oct 18 01:34:59 2001 --- recog.c Thu Oct 18 01:35:04 2001 *************** split_all_insns (upd_life) *** 2778,2785 **** if (changed) { ! for (i = 0; i < n_basic_blocks; i++) ! find_sub_basic_blocks (BASIC_BLOCK (i)); } if (changed && upd_life) --- 2778,2784 ---- if (changed) { ! find_many_sub_basic_blocks (blocks); } if (changed && upd_life)