[PATCH] Take branch misprediction effects into account when RTL loop unrolling (issue 6099055)

[Teresa Johnson]

Fixed the stylist suggestions. Other responses below.

On Tue, Apr 24, 2012 at 10:22 PM,  <davidxl@google.com> wrote:
>
> http://codereview.appspot.com/6099055/diff/1/loop-unroll.c
> File loop-unroll.c (right):
>
> http://codereview.appspot.com/6099055/diff/1/loop-unroll.c#newcode156
> loop-unroll.c:156: static bool
> An empty line here.
>
> http://codereview.appspot.com/6099055/diff/1/loop-unroll.c#newcode182
> loop-unroll.c:182: static bool
> add empty line after comment.
>
> http://codereview.appspot.com/6099055/diff/1/loop-unroll.c#newcode213
> loop-unroll.c:213: /* Compute the number of branches in LOOP, weighted
> by execution counts.  */
> same here.
>
> http://codereview.appspot.com/6099055/diff/1/loop-unroll.c#newcode215
> loop-unroll.c:215: compute_weighted_branches(struct loop *loop)
> Missing space. Similarly for other functions.
>
> http://codereview.appspot.com/6099055/diff/1/loop-unroll.c#newcode255
> loop-unroll.c:255: data exists, simply return the current NUNROLL
> factor.  */
> same here.
>
> http://codereview.appspot.com/6099055/diff/1/loop-unroll.c#newcode281
> loop-unroll.c:281: while (loop_outer(outer))
> Should the check start from the current loop? Or the handling of the
> current loop should be peeled out -- max_unroll_factor =
> branch_budget/weighted_num_branches

Here we are trying to find a hot enclosing path, so we start from the
next most enclosing outer loop and walk outwards.

>
> http://codereview.appspot.com/6099055/diff/1/loop-unroll.c#newcode317
> loop-unroll.c:317: return (PARAM_VALUE
> (PARAM_UNROLL_OUTER_LOOP_BRANCH_BUDGET) -
> The number of branches may be larger than budget --> leading to overflow
> -- need to guard against it.

Yes, this is a bug. I verified that it didn't have any real affect on
spec or internal benchmarks, thankfully, because in most cases where
there are more branches than the budget we have hit the outermost
(fake) loop and weren't executing this code. In the few cases we were,
we decided for other reasons not to unroll.

>
> http://codereview.appspot.com/6099055/diff/1/loop-unroll.c#newcode318
> loop-unroll.c:318: weighted_outer_branches)/(weighted_num_branches - 1)
> + 1;
> Should it continue walking up the loop tree and find the minmal unroll
> factor?

Once we find a hot enough enclosing loop we stop, because the number
of iterations is large enough to assume that the nested branches will
train the predictor and also are relatively hot enough to make the
benefits of unrolling the innermost loop outweigh any negative impact
on the outer region's branch prediction.

New patch coming shortly.

Thanks,
Teresa

>
> http://codereview.appspot.com/6099055/diff/1/loop-unroll.c#newcode747
> loop-unroll.c:747: && loop_has_FP_comp(loop)
> missing space
>
> http://codereview.appspot.com/6099055/diff/1/loop-unroll.c#newcode749
> loop-unroll.c:749: && desc->niter < (unsigned) PARAM_VALUE
> (PARAM_MIN_ITER_UNROLL_WITH_BRANCHES))
> line too long.
>
> http://codereview.appspot.com/6099055/diff/1/loop-unroll.c#newcode1057
> loop-unroll.c:1057: && loop_has_FP_comp(loop)
> Refactor the check into a helper function?
>
> http://codereview.appspot.com/6099055/diff/1/params.def
> File params.def (right):
>
> http://codereview.appspot.com/6099055/diff/1/params.def#newcode314
> params.def:314:
> Missing comment.
>
> http://codereview.appspot.com/6099055/diff/1/params.def#newcode319
> params.def:319:
> missing comment.
>
> http://codereview.appspot.com/6099055/



-- 
Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413