Resending my response in plain text so it will go through to gcc-patches...
On Tue, Apr 24, 2012 at 2:36 PM, Teresa Johnson <tejohn...@google.com> wrote: > > > > On Tue, Apr 24, 2012 at 2:30 PM, Andrew Pinski <pins...@gmail.com> wrote: >> >> On Tue, Apr 24, 2012 at 2:26 PM, Teresa Johnson <tejohn...@google.com> wrote: >> > This patch adds heuristics to limit unrolling in loops with branches that >> > may increase >> > branch mispredictions. It affects loops that are not frequently iterated, >> > and that are >> > nested within a hot region of code that already contains many branch >> > instructions. >> > >> > Performance tested with both internal benchmarks and with SPEC 2000/2006 >> > on a variety >> > of Intel systems (Core2, Corei7, SandyBridge) and a couple of different >> > AMD Opteron systems. >> > This improves performance of an internal search indexing benchmark by >> > close to 2% on >> > all the tested Intel platforms. It also consistently improves 445.gobmk >> > (with FDO feedback >> > where unrolling kicks in) by close to 1% on AMD Opteron. Other performance >> > effects are >> > neutral. >> > >> > Bootstrapped and tested on x86_64-unknown-linux-gnu. Is this ok for trunk? >> > >> > Thanks, >> > Teresa >> > >> > 2012-04-24 Teresa Johnson <tejohn...@google.com> >> > >> > * loop-unroll.c (loop_has_call): New function. >> > (loop_has_FP_comp): Ditto. >> > (compute_weighted_branches): Ditto. >> > (max_unroll_with_branches): Ditto. >> > (decide_unroll_constant_iterations): Add heuristic to avoid >> > increasing branch mispredicts when unrolling. >> > (decide_unroll_runtime_iterations): Ditto. >> > * params.def (PARAM_MIN_ITER_UNROLL_WITH_BRANCHES): New param. >> > (PARAM_UNROLL_OUTER_LOOP_BRANCH_BUDGET): Ditto. >> > >> > Index: loop-unroll.c >> > =================================================================== >> > --- loop-unroll.c (revision 186783) >> > +++ loop-unroll.c (working copy) >> > @@ -152,6 +152,180 @@ static void combine_var_copies_in_loop_exit (struc >> > basic_block); >> > static rtx get_expansion (struct var_to_expand *); >> > >> > +/* Determine whether LOOP contains call. */ >> > +static bool >> > +loop_has_call(struct loop *loop) >> > +{ >> > + basic_block *body, bb; >> > + unsigned i; >> > + rtx insn; >> > + >> > + body = get_loop_body (loop); >> > + for (i = 0; i < loop->num_nodes; i++) >> > + { >> > + bb = body[i]; >> > + >> > + FOR_BB_INSNS (bb, insn) >> > + { >> > + if (CALL_P (insn)) >> > + { >> > + free (body); >> > + return true; >> > + } >> > + } >> > + } >> > + free (body); >> > + return false; >> > +} >> > + >> > +/* Determine whether LOOP contains floating-point computation. */ >> > +static bool >> > +loop_has_FP_comp(struct loop *loop) >> > +{ >> > + rtx set, dest; >> > + basic_block *body, bb; >> > + unsigned i; >> > + rtx insn; >> > + >> > + body = get_loop_body (loop); >> > + for (i = 0; i < loop->num_nodes; i++) >> > + { >> > + bb = body[i]; >> > + >> > + FOR_BB_INSNS (bb, insn) >> > + { >> > + set = single_set (insn); >> > + if (!set) >> > + continue; >> > + >> > + dest = SET_DEST (set); >> > + if (FLOAT_MODE_P (GET_MODE (dest))) >> > + { >> > + free (body); >> > + return true; >> > + } >> > + } >> > + } >> > + free (body); >> > + return false; >> > +} >> > + >> > +/* Compute the number of branches in LOOP, weighted by execution counts. >> > */ >> > +static float >> > +compute_weighted_branches(struct loop *loop) >> > +{ >> > + int header_count = loop->header->count; >> > + unsigned i; >> > + float n; >> > + basic_block * body; >> > + >> > + /* If no profile feedback data exists, don't limit unrolling */ >> > + if (header_count == 0) >> > + return 0.0; >> > + >> > + gcc_assert (loop->latch != EXIT_BLOCK_PTR); >> > + >> > + body = get_loop_body (loop); >> > + n = 0.0; >> > + for (i = 0; i < loop->num_nodes; i++) >> > + { >> > + if (EDGE_COUNT (body[i]->succs) >= 2) >> > + { >> > + /* If this block is executed less frequently than the header >> > (loop >> > + entry), then it is weighted based on the ratio of times it is >> > + executed compared to the header. */ >> > + if (body[i]->count < header_count) >> > + n += ((float)body[i]->count)/header_count; >> >> Please don't introduce more floating point usage into the compiler >> since it could change between different hosts (sse vs x87 for an >> example). >> Maybe use a fixed point multiply of 1000 (note use a macro for this >> special value though) like what is used in the rest of the predict >> code. > > > Ok, got it. I will address this in the next version of the patch. > > Thanks, > Teresa > >> >> >> >> Thanks, >> Andrew Pinski >> >> >> > + >> > + /* When it is executed more frequently than the header (i.e. it >> > is >> > + in a nested inner loop), simply weight the branch at 1.0. */ >> > + else >> > + n += 1.0; >> > + } >> > + } >> > + free (body); >> > + >> > + return n; >> > +} >> > + >> > +/* Compute the maximum number of times LOOP can be unrolled without >> > exceeding >> > + a branch budget, which can increase branch mispredictions. The number >> > of >> > + branches is computed by weighting each branch with its expected >> > execution >> > + probability through the loop based on profile data. If no profile >> > feedback >> > + data exists, simply return the current NUNROLL factor. */ >> > +static unsigned >> > +max_unroll_with_branches(struct loop *loop, unsigned nunroll) >> > +{ >> > + struct loop *outer; >> > + struct niter_desc *outer_desc; >> > + int outer_niters = 1; >> > + float weighted_outer_branches = 0.0; >> > + float weighted_num_branches = compute_weighted_branches (loop); >> > + >> > + /* If there was no profile feedback data, weighted_num_branches will be >> > 0.0 >> > + and we won't limit unrolling. If the weighted_num_branches is at >> > most 1.0, >> > + also don't limit unrolling as the back-edge branch will not be >> > duplicated. */ >> > + if (weighted_num_branches <= 1.0) >> > + return nunroll; >> > + >> > + /* Walk up the loop tree until we find a hot outer loop in which the >> > current >> > + loop is nested. At that point we will compute the number of times the >> > + current loop can be unrolled based on the number of branches in the >> > hot >> > + outer loop. */ >> > + outer = loop_outer(loop); >> > + /* The loop structure contains a fake outermost loop, so this should >> > always >> > + be non-NULL for our current loop. */ >> > + gcc_assert (outer); >> > + /* Detect if this is the fake outermost loop (at which point we are >> > done) >> > + by checking its outer loop. */ >> > + while (loop_outer(outer)) >> > + { >> > + outer_desc = get_simple_loop_desc (outer); >> > + >> > + if (outer_desc->const_iter) >> > + outer_niters *= outer_desc->niter; >> > + else if (outer->header->count) >> > + outer_niters *= expected_loop_iterations (outer); >> > + >> > + weighted_outer_branches = compute_weighted_branches (outer); >> > + >> > + /* Should have been checked by caller. */ >> > + gcc_assert(PARAM_VALUE (PARAM_MIN_ITER_UNROLL_WITH_BRANCHES) != -1); >> > + >> > + /* If the outer loop has enough iterations to be considered hot, >> > then >> > + we can stop our upwards loop tree traversal and examine the >> > current >> > + outer loop. */ >> > + if (outer_niters >= PARAM_VALUE >> > (PARAM_MIN_ITER_UNROLL_WITH_BRANCHES)) >> > + { >> > + /* Assume that any call will cause the branch budget to be >> > exceeded, >> > + and that we can't unroll the current loop without increasing >> > + mispredicts. */ >> > + if (loop_has_call(outer)) >> > + return 0; >> > + >> > + /* Otherwise, compute the maximum number of times current loop >> > can be >> > + unrolled without exceeding our branch budget. First we >> > subtract >> > + off the outer loop's weighted branch count from the budget. >> > Note >> > + that this includes the branches in the current loop. This >> > yields >> > + the number of branches left in the budget for the unrolled >> > copies. >> > + We divide this by the number of branches in the current loop >> > that >> > + must be duplicated when we unroll, which is the total >> > weighted >> > + number of branches minus the back-edge branch. This yields >> > the >> > + number of new loop body copies that can be created by >> > unrolling >> > + without exceeding the budget, to which we add 1 to get the >> > unroll >> > + factor. */ >> > + return (PARAM_VALUE (PARAM_UNROLL_OUTER_LOOP_BRANCH_BUDGET) - >> > + weighted_outer_branches)/(weighted_num_branches - 1) + >> > 1; >> > + } >> > + outer = loop_outer(outer); >> > + } >> > + >> > + /* The current loop is not enclosed by a hot enough outer loop in this >> > + procedure, since the hot outer loop is inter-procedural, assume that >> > + it already contains a significant number of branches, so don't >> > unroll. */ >> > + return 0; >> > +} >> > + >> > /* Unroll and/or peel (depending on FLAGS) LOOPS. */ >> > void >> > unroll_and_peel_loops (int flags) >> > @@ -522,6 +696,7 @@ static void >> > decide_unroll_constant_iterations (struct loop *loop, int flags) >> > { >> > unsigned nunroll, nunroll_by_av, best_copies, best_unroll = 0, n_copies, >> > i; >> > + unsigned nunroll_branches; >> > struct niter_desc *desc; >> > >> > if (!(flags & UAP_UNROLL)) >> > @@ -565,6 +740,25 @@ decide_unroll_constant_iterations (struct loop *lo >> > return; >> > } >> > >> > + /* Be careful when unrolling loops with branches inside -- it can >> > increase >> > + the number of mispredicts. Ignore loops with FP computation as these >> > + tend to benefit much more consistently from unrolling. */ >> > + if (num_loop_branches (loop) > 1 >> > + && loop_has_FP_comp(loop) >> > + && PARAM_VALUE (PARAM_MIN_ITER_UNROLL_WITH_BRANCHES) != -1 >> > + && desc->niter < (unsigned) PARAM_VALUE >> > (PARAM_MIN_ITER_UNROLL_WITH_BRANCHES)) >> > + { >> > + nunroll_branches = max_unroll_with_branches(loop, nunroll); >> > + if (nunroll > nunroll_branches) >> > + nunroll = nunroll_branches; >> > + if (nunroll <= 1) >> > + { >> > + if (dump_file) >> > + fprintf (dump_file, ";; Not unrolling, contains branches\n"); >> > + return; >> > + } >> > + } >> > + >> > /* Check whether the loop rolls enough to consider. */ >> > if (desc->niter < 2 * nunroll) >> > { >> > @@ -802,7 +996,7 @@ unroll_loop_constant_iterations (struct loop *loop >> > static void >> > decide_unroll_runtime_iterations (struct loop *loop, int flags) >> > { >> > - unsigned nunroll, nunroll_by_av, i; >> > + unsigned nunroll, nunroll_by_av, nunroll_branches, i; >> > struct niter_desc *desc; >> > >> > if (!(flags & UAP_UNROLL)) >> > @@ -856,6 +1050,25 @@ decide_unroll_runtime_iterations (struct loop *loo >> > return; >> > } >> > >> > + /* Be careful when unrolling loops with branches inside -- it can >> > increase >> > + the number of mispredicts. Ignore loops with FP computation as these >> > + tend to benefit much more consistently from unrolling. */ >> > + if (num_loop_branches (loop) > 1 >> > + && loop_has_FP_comp(loop) >> > + && PARAM_VALUE (PARAM_MIN_ITER_UNROLL_WITH_BRANCHES) != -1 >> > + && expected_loop_iterations (loop) < (unsigned) PARAM_VALUE >> > (PARAM_MIN_ITER_UNROLL_WITH_BRANCHES)) >> > + { >> > + nunroll_branches = max_unroll_with_branches(loop, nunroll); >> > + if (nunroll > nunroll_branches) >> > + nunroll = nunroll_branches; >> > + if (nunroll <= 1) >> > + { >> > + if (dump_file) >> > + fprintf (dump_file, ";; Not unrolling, contains branches\n"); >> > + return; >> > + } >> > + } >> > + >> > /* If we have profile feedback, check whether the loop rolls. */ >> > if ((loop->header->count >> > && expected_loop_iterations (loop) < 2 * nunroll) >> > Index: params.def >> > =================================================================== >> > --- params.def (revision 186783) >> > +++ params.def (working copy) >> > @@ -312,6 +312,16 @@ DEFPARAM(PARAM_MAX_UNROLL_ITERATIONS, >> > "The maximum depth of a loop nest we completely peel", >> > 8, 0, 0) >> > >> > +DEFPARAM(PARAM_MIN_ITER_UNROLL_WITH_BRANCHES, >> > + "min-iter-unroll-with-branches", >> > + "Minimum iteration count to ignore branch effects when unrolling", >> > + 50, 0, 0) >> > + >> > +DEFPARAM(PARAM_UNROLL_OUTER_LOOP_BRANCH_BUDGET, >> > + "unroll-outer-loop-branch-budget", >> > + "Maximum number of branches allowed in hot outer loop region after >> > unroll", >> > + 25, 0, 0) >> > + >> > /* The maximum number of insns of an unswitched loop. */ >> > DEFPARAM(PARAM_MAX_UNSWITCH_INSNS, >> > "max-unswitch-insns", >> > >> > -- >> > This patch is available for review at http://codereview.appspot.com/6099055 > > > > > -- > Teresa Johnson | Software Engineer | tejohn...@google.com | 408-460-2413 > -- Teresa Johnson | Software Engineer | tejohn...@google.com | 408-460-2413