Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(1355)

Issue 6099055: [PATCH] Take branch misprediction effects into account when RTL loop unrolling

Can't Edit
Can't Publish+Mail
Start Review
Created:
11 years, 11 months ago by tejohnson
Modified:
9 years, 6 months ago
Reviewers:
pinskia, richard.guenther, andi, stevenb.gcc, davidxl, izamyatin
CC:
gcc-patches_gcc.gnu.org
Base URL:
svn+ssh://gcc.gnu.org/svn/gcc/trunk/gcc/
Visibility:
Public.

Patch Set 1 #

Total comments: 13

Patch Set 2 : [PATCH] Take branch misprediction effects into account when RTL loop unrolling #

Patch Set 3 : [PATCH] Take branch misprediction effects into account when RTL loop unrolling #

Unified diffs Side-by-side diffs Delta from patch set Stats (+247 lines, -17 lines) Patch
M cfgloop.h View 1 2 4 chunks +15 lines, -2 lines 0 comments Download
M cfgloop.c View 1 2 1 chunk +84 lines, -10 lines 0 comments Download
M doc/invoke.texi View 1 1 chunk +6 lines, -0 lines 0 comments Download
M loop-iv.c View 1 2 1 chunk +6 lines, -2 lines 0 comments Download
M loop-unroll.c View 1 2 7 chunks +127 lines, -3 lines 0 comments Download
M params.def View 1 1 chunk +9 lines, -0 lines 0 comments Download

Messages

Total messages: 24
tejohnson
This patch adds heuristics to limit unrolling in loops with branches that may increase branch ...
11 years, 11 months ago (2012-04-24 21:26:49 UTC) #1
pinskia_gmail.com
On Tue, Apr 24, 2012 at 2:26 PM, Teresa Johnson <tejohnson@google.com> wrote: > This patch ...
11 years, 11 months ago (2012-04-24 21:31:13 UTC) #2
tejohnson
On Tue, Apr 24, 2012 at 2:30 PM, Andrew Pinski <pinskia@gmail.com> wrote: > On Tue, ...
11 years, 11 months ago (2012-04-24 21:36:12 UTC) #3
tejohnson
Resending my response in plain text so it will go through to gcc-patches... On Tue, ...
11 years, 11 months ago (2012-04-24 21:41:04 UTC) #4
stevenb.gcc
On Tue, Apr 24, 2012 at 11:26 PM, Teresa Johnson <tejohnson@google.com> wrote: > * params.def ...
11 years, 11 months ago (2012-04-24 23:38:17 UTC) #5
andi_firstfloor.org
tejohnson@google.com (Teresa Johnson) writes: > This patch adds heuristics to limit unrolling in loops with ...
11 years, 11 months ago (2012-04-25 01:13:58 UTC) #6
davidxl
On Tue, Apr 24, 2012 at 6:13 PM, Andi Kleen <andi@firstfloor.org> wrote: > tejohnson@google.com (Teresa ...
11 years, 11 months ago (2012-04-25 04:57:10 UTC) #7
davidxl
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 ...
11 years, 11 months ago (2012-04-25 05:22:14 UTC) #8
andi_firstfloor.org
> Tree level unrollers (cunrolli and cunroll) do complete unroll. At O2, > both of ...
11 years, 11 months ago (2012-04-25 08:27:10 UTC) #9
richard.guenther_gmail.com
On Tue, Apr 24, 2012 at 11:26 PM, Teresa Johnson <tejohnson@google.com> wrote: > This patch ...
11 years, 11 months ago (2012-04-25 09:03:43 UTC) #10
tejohnson
On Tue, Apr 24, 2012 at 4:38 PM, Steven Bosscher <stevenb.gcc@gmail.com> wrote: > On Tue, ...
11 years, 11 months ago (2012-04-25 15:27:59 UTC) #11
tejohnson
On Tue, Apr 24, 2012 at 6:13 PM, Andi Kleen <andi@firstfloor.org> wrote: > tejohnson@google.com (Teresa ...
11 years, 11 months ago (2012-04-25 15:36:05 UTC) #12
tejohnson
On Wed, Apr 25, 2012 at 2:03 AM, Richard Guenther <richard.guenther@gmail.com> wrote: > On Tue, ...
11 years, 11 months ago (2012-04-25 15:48:23 UTC) #13
davidxl
I think the general mechanism applies to most of the targets. What is needed is ...
11 years, 11 months ago (2012-04-25 16:11:59 UTC) #14
izamyatin_gmail.com
Are you sure that tree-level unrollers are turned on at O2? My impression was that ...
11 years, 11 months ago (2012-04-27 07:07:42 UTC) #15
davidxl
On Fri, Apr 27, 2012 at 12:07 AM, Igor Zamyatin <izamyatin@gmail.com> wrote: > Are you ...
11 years, 11 months ago (2012-04-27 07:18:37 UTC) #16
tejohnson
Fixed the stylist suggestions. Other responses below. On Tue, Apr 24, 2012 at 10:22 PM, ...
11 years, 11 months ago (2012-05-01 21:17:23 UTC) #17
tejohnson
Improved patch based on feedback. Main changes are: 1) Improve efficiency by caching loop analysis ...
11 years, 11 months ago (2012-05-01 22:54:30 UTC) #18
davidxl
It might be better to separate the data structure name change (niter_desc to loop_desc) into ...
11 years, 11 months ago (2012-05-04 16:39:17 UTC) #19
tejohnson
On David's suggestion, I have removed the changes that rename niter_desc to loop_desc from this ...
11 years, 11 months ago (2012-05-04 22:41:41 UTC) #20
tejohnson
Ping? Teresa On Fri, May 4, 2012 at 3:41 PM, Teresa Johnson <tejohnson@google.com> wrote: > ...
11 years, 10 months ago (2012-05-11 13:09:44 UTC) #21
tejohnson
Ping? Teresa On Fri, May 4, 2012 at 3:41 PM, Teresa Johnson <tejohnson@google.com> wrote: > ...
11 years, 10 months ago (2012-05-11 13:12:00 UTC) #22
tejohnson
Ping? Teresa On Fri, May 11, 2012 at 6:11 AM, Teresa Johnson <tejohnson@google.com> wrote: > ...
11 years, 10 months ago (2012-05-18 14:21:03 UTC) #23
tejohnson
11 years, 9 months ago (2012-06-20 01:49:04 UTC) #24
Ping.
Teresa

On Fri, May 18, 2012 at 7:21 AM, Teresa Johnson <tejohnson@google.com> wrote:
> Ping?
> Teresa
>
> On Fri, May 11, 2012 at 6:11 AM, Teresa Johnson <tejohnson@google.com> wrote:
>> Ping?
>> Teresa
>>
>> On Fri, May 4, 2012 at 3:41 PM, Teresa Johnson <tejohnson@google.com> wrote:
>>>
>>> On David's suggestion, I have removed the changes that rename niter_desc
>>> to
>>> loop_desc from this patch to focus the patch on the unrolling changes. I
>>> can
>>> submit a cleanup patch to do the renaming as soon as this one goes in.
>>>
>>> Bootstrapped and tested on x86_64-unknown-linux-gnu.  Ok for trunk?
>>>
>>> Thanks,
>>> Teresa
>>>
>>> Here is the new description of improvements from the original patch:
>>>
>>> Improved patch based on feedback. Main changes are:
>>>
>>> 1) Improve efficiency by caching loop analysis results in the loop
>>> auxiliary
>>> info structure hanging off the loop structure. Added a new routine,
>>> analyze_loop_insns, to fill in information about the average and total
>>> number
>>> of branches, as well as whether there are any floating point set and call
>>> instructions in the loop. The new routine is invoked when we first create
>>> a
>>> loop's niter_desc struct, and the caller (get_simple_loop_desc) has been
>>> modified to handle creating a niter_desc for the fake outermost loop.
>>>
>>> 2) Improvements to max_unroll_with_branches:
>>> - Treat the fake outermost loop (the procedure body) as we would a hot
>>> outer
>>> loop, i.e. compute the max unroll looking at its nested branches, instead
>>> of
>>> shutting off unrolling when we reach the fake outermost loop.
>>> - Pull the checks previously done in the caller into the routine (e.g.
>>> whether the loop iterates frequently or contains fp instructions).
>>> - Fix a bug in the previous version that sometimes caused overflow in the
>>> new unroll factor.
>>>
>>> 3) Remove float variables, and use integer computation to compute the
>>> average number of branches in the loop.
>>>
>>> 4) Detect more types of floating point computations in the loop by walking
>>> all set instructions, not just single sets.
>>>
>>> 2012-05-04   Teresa Johnson  <tejohnson@google.com>
>>>
>>>        * doc/invoke.texi: Update the documentation with new params.
>>>        * loop-unroll.c (max_unroll_with_branches): New function.
>>>        (decide_unroll_constant_iterations,
>>> decide_unroll_runtime_iterations):
>>>        Add heuristic to avoid increasing branch mispredicts when
>>> unrolling.
>>>        (decide_peel_simple, decide_unroll_stupid): Retrieve number of
>>>        branches from niter_desc instead of via function that walks loop.
>>>        * loop-iv.c (get_simple_loop_desc): Invoke new analyze_loop_insns
>>>        function, and add guards to enable this function to work for the
>>>        outermost loop.
>>>        * cfgloop.c (insn_has_fp_set, analyze_loop_insns): New functions.
>>>        (num_loop_branches): Remove.
>>>        * cfgloop.h (struct loop_desc): Added new fields to cache
>>> additional
>>>        loop analysis information.
>>>        (num_loop_branches): Remove.
>>>        (analyze_loop_insns): Declare.
>>>        * params.def (PARAM_MIN_ITER_UNROLL_WITH_BRANCHES): New param.
>>>        (PARAM_UNROLL_OUTER_LOOP_BRANCH_BUDGET): Ditto.
>>>
>>> Index: doc/invoke.texi
>>> ===================================================================
>>> --- doc/invoke.texi     (revision 187013)
>>> +++ doc/invoke.texi     (working copy)
>>> @@ -8842,6 +8842,12 @@ The maximum number of insns of an unswitched loop.
>>>  @item max-unswitch-level
>>>  The maximum number of branches unswitched in a single loop.
>>>
>>> +@item min-iter-unroll-with-branches
>>> +Minimum iteration count to ignore branch effects when unrolling.
>>> +
>>> +@item unroll-outer-loop-branch-budget
>>> +Maximum number of branches allowed in hot outer loop region after unroll.
>>> +
>>>  @item lim-expensive
>>>  The minimum cost of an expensive expression in the loop invariant motion.
>>>
>>> Index: loop-unroll.c
>>> ===================================================================
>>> --- loop-unroll.c       (revision 187013)
>>> +++ loop-unroll.c       (working copy)
>>> @@ -152,6 +152,99 @@ static void combine_var_copies_in_loop_exit (struc
>>>                                             basic_block);
>>>  static rtx get_expansion (struct var_to_expand *);
>>>
>>> +/* 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 = 0;
>>> +  int outer_niters = 1;
>>> +  int frequent_iteration_threshold;
>>> +  unsigned branch_budget;
>>> +  struct niter_desc *desc = get_simple_loop_desc (loop);
>>> +
>>> +  /* Ignore loops with FP computation as these tend to benefit much more
>>> +     consistently from unrolling.  */
>>> +  if (desc->has_fp)
>>> +    return nunroll;
>>> +
>>> +  frequent_iteration_threshold = PARAM_VALUE
>>> (PARAM_MIN_ITER_UNROLL_WITH_BRANCHES);
>>> +  if (expected_loop_iterations (loop) >= (unsigned)
>>> frequent_iteration_threshold)
>>> +    return nunroll;
>>> +
>>> +  /* If there was no profile feedback data, av_num_branches will be 0
>>> +     and we won't limit unrolling. If the av_num_branches is at most 1,
>>> +     also don't limit unrolling as the back-edge branch will not be
>>> duplicated.  */
>>> +  if (desc->av_num_branches <= 1)
>>> +    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);
>>> +
>>> +  /* Walk up the loop tree until we either find a hot outer loop or hit
>>> the
>>> +     fake outermost loop at the root.  */
>>> +  while (true)
>>> +    {
>>> +      outer_desc = get_simple_loop_desc (outer);
>>> +
>>> +      /* Stop if we hit the fake outermost loop at the root of the tree,
>>> +         which includes the whole procedure.  */
>>> +      if (!loop_outer (outer))
>>> +        break;
>>> +
>>> +      if (outer_desc->const_iter)
>>> +        outer_niters *= outer_desc->niter;
>>> +      else if (outer->header->count)
>>> +        outer_niters *= expected_loop_iterations (outer);
>>> +
>>> +      /* 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 >= frequent_iteration_threshold)
>>> +        break;
>>> +
>>> +      outer = loop_outer (outer);
>>> +    }
>>> +
>>> +  gcc_assert(outer);
>>> +
>>> +  /* 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 (outer_desc->has_call)
>>> +    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 average 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 average
>>> +     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. Note that the "outermost loop" may be the whole procedure
>>> +     if we did not find a hot enough enclosing loop.  */
>>> +  branch_budget = PARAM_VALUE (PARAM_UNROLL_OUTER_LOOP_BRANCH_BUDGET);
>>> +  if (outer_desc->av_num_branches > branch_budget)
>>> +    return 0;
>>> +  /* We already returned early if desc->av_num_branches <= 1.  */
>>> +  return (branch_budget - outer_desc->av_num_branches)
>>> +      / (desc->av_num_branches - 1) + 1;
>>> +}
>>> +
>>>  /* Unroll and/or peel (depending on FLAGS) LOOPS.  */
>>>  void
>>>  unroll_and_peel_loops (int flags)
>>> @@ -522,6 +615,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 +659,21 @@ decide_unroll_constant_iterations (struct loop *lo
>>>       return;
>>>     }
>>>
>>> +  /* Be careful when unrolling loops with branches inside -- it can
>>> increase
>>> +     the number of mispredicts.  */
>>> +  if (desc->num_branches > 1)
>>> +    {
>>> +      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 +911,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 +965,21 @@ decide_unroll_runtime_iterations (struct loop *loo
>>>       return;
>>>     }
>>>
>>> +  /* Be careful when unrolling loops with branches inside -- it can
>>> increase
>>> +     the number of mispredicts.  */
>>> +  if (desc->num_branches > 1)
>>> +    {
>>> +      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)
>>> @@ -1233,7 +1357,7 @@ decide_peel_simple (struct loop *loop, int flags)
>>>
>>>   /* Do not simply peel loops with branches inside -- it increases number
>>>      of mispredicts.  */
>>> -  if (num_loop_branches (loop) > 1)
>>> +  if (desc->num_branches > 1)
>>>     {
>>>       if (dump_file)
>>>        fprintf (dump_file, ";; Not peeling, contains branches\n");
>>> @@ -1394,7 +1518,7 @@ decide_unroll_stupid (struct loop *loop, int flags
>>>
>>>   /* Do not unroll loops with branches inside -- it increases number
>>>      of mispredicts.  */
>>> -  if (num_loop_branches (loop) > 1)
>>> +  if (desc->num_branches > 1)
>>>     {
>>>       if (dump_file)
>>>        fprintf (dump_file, ";; Not unrolling, contains branches\n");
>>> Index: loop-iv.c
>>> ===================================================================
>>> --- loop-iv.c   (revision 187013)
>>> +++ loop-iv.c   (working copy)
>>> @@ -2948,8 +2948,12 @@ get_simple_loop_desc (struct loop *loop)
>>>   /* At least desc->infinite is not always initialized by
>>>      find_simple_loop_exit.  */
>>>   desc = XCNEW (struct niter_desc);
>>> -  iv_analysis_loop_init (loop);
>>> -  find_simple_exit (loop, desc);
>>> +  if (loop->latch != EXIT_BLOCK_PTR)
>>> +    {
>>> +      iv_analysis_loop_init (loop);
>>> +      find_simple_exit (loop, desc);
>>> +    }
>>> +  analyze_loop_insns (loop, desc);
>>>   loop->aux = desc;
>>>
>>>   if (desc->simple_p && (desc->assumptions || desc->infinite))
>>> Index: cfgloop.c
>>> ===================================================================
>>> --- cfgloop.c   (revision 187013)
>>> +++ cfgloop.c   (working copy)
>>> @@ -1156,24 +1156,98 @@ get_loop_exit_edges (const struct loop *loop)
>>>   return edges;
>>>  }
>>>
>>> -/* Counts the number of conditional branches inside LOOP.  */
>>> +/* Determine if INSN is a floating point set.  */
>>>
>>> -unsigned
>>> -num_loop_branches (const struct loop *loop)
>>> +static bool
>>> +insn_has_fp_set(rtx insn)
>>>  {
>>> -  unsigned i, n;
>>> -  basic_block * body;
>>> +  int i;
>>> +  rtx pat = PATTERN(insn);
>>> +  if (GET_CODE (pat) == SET)
>>> +    return (FLOAT_MODE_P (GET_MODE (SET_DEST (pat))));
>>> +  else if (GET_CODE (pat) == PARALLEL)
>>> +    {
>>> +      for (i = 0; i < XVECLEN (pat, 0); i++)
>>> +        {
>>> +          rtx sub = XVECEXP (pat, 0, i);
>>> +          if (GET_CODE (sub) == SET)
>>> +            return (FLOAT_MODE_P (GET_MODE (SET_DEST (sub))));
>>> +        }
>>> +    }
>>> +  return false;
>>> +}
>>>
>>> -  gcc_assert (loop->latch != EXIT_BLOCK_PTR);
>>> +/* Analyzes the instructions inside LOOP, updating the DESC. Currently
>>> counts
>>> +   the number of conditional branch instructions, calls and fp
>>> instructions,
>>> +   as well as the average number of branches executed per iteration.  */
>>>
>>> +void
>>> +analyze_loop_insns (const struct loop *loop, struct niter_desc *desc)
>>> +{
>>> +  unsigned i, nbranch;
>>> +  gcov_type weighted_nbranch;
>>> +  bool has_call, has_fp;
>>> +  basic_block * body, bb;
>>> +  rtx insn;
>>> +  gcov_type header_count = loop->header->count;
>>> +
>>> +  nbranch = weighted_nbranch = 0;
>>> +  has_call = has_fp = false;
>>> +
>>>   body = get_loop_body (loop);
>>> -  n = 0;
>>>   for (i = 0; i < loop->num_nodes; i++)
>>> -    if (EDGE_COUNT (body[i]->succs) >= 2)
>>> -      n++;
>>> +    {
>>> +      bb = body[i];
>>> +
>>> +      if (EDGE_COUNT (bb->succs) >= 2)
>>> +        {
>>> +          nbranch++;
>>> +
>>> +          /* If this block is executed less frequently than the header
>>> (loop
>>> +             entry), then it is weighted based on its execution count,
>>> which
>>> +             will be turned into a ratio compared to the loop header
>>> below. */
>>> +          if (bb->count < header_count)
>>> +            weighted_nbranch += bb->count;
>>> +
>>> +          /* When it is executed more frequently than the header (i.e. it
>>> is
>>> +             in a nested inner loop), simply weight the branch the same
>>> as the
>>> +             header execution count, so that it will contribute 1 branch
>>> to
>>> +             the ratio computed below. */
>>> +          else
>>> +            weighted_nbranch += header_count;
>>> +        }
>>> +
>>> +      /* No need to iterate through the instructions below if
>>> +         both flags have already been set.  */
>>> +      if (has_call && has_fp)
>>> +        continue;
>>> +
>>> +      FOR_BB_INSNS (bb, insn)
>>> +        {
>>> +          if (!INSN_P (insn))
>>> +            continue;
>>> +
>>> +          if (!has_call)
>>> +            has_call = CALL_P (insn);
>>> +
>>> +          if (!has_fp)
>>> +            has_fp = insn_has_fp_set (insn);
>>> +        }
>>> +    }
>>>   free (body);
>>>
>>> -  return n;
>>> +  desc->num_branches = nbranch;
>>> +  /* Now divide the weights computed above by the loop header execution
>>> count,
>>> +     to compute the average number of branches through the loop. By
>>> adding
>>> +     header_count/2 to the numerator we round to nearest with integer
>>> +     division.  */
>>> +  if (header_count  != 0)
>>> +    desc->av_num_branches
>>> +        = (weighted_nbranch + header_count/2) / header_count;
>>> +  else
>>> +    desc->av_num_branches = 0;
>>> +  desc->has_call = has_call;
>>> +  desc->has_fp = has_fp;
>>>  }
>>>
>>>  /* Adds basic block BB to LOOP.  */
>>> Index: cfgloop.h
>>> ===================================================================
>>> --- cfgloop.h   (revision 187013)
>>> +++ cfgloop.h   (working copy)
>>> @@ -249,7 +249,6 @@ extern basic_block *get_loop_body_in_custom_order
>>>
>>>  extern VEC (edge, heap) *get_loop_exit_edges (const struct loop *);
>>>  edge single_exit (const struct loop *);
>>> -extern unsigned num_loop_branches (const struct loop *);
>>>
>>>  extern edge loop_preheader_edge (const struct loop *);
>>>  extern edge loop_latch_edge (const struct loop *);
>>> @@ -359,7 +358,8 @@ struct rtx_iv
>>>  };
>>>
>>>  /* The description of an exit from the loop and of the number of
>>> iterations
>>> -   till we take the exit.  */
>>> +   till we take the exit. Also includes other information used primarily
>>> +   by the loop unroller.  */
>>>
>>>  struct niter_desc
>>>  {
>>> @@ -400,6 +400,18 @@ struct niter_desc
>>>
>>>   /* The number of iterations of the loop.  */
>>>   rtx niter_expr;
>>> +
>>> +  /* The number of branches in the loop.  */
>>> +  unsigned num_branches;
>>> +
>>> +  /* The number of executed branches per iteration.  */
>>> +  unsigned av_num_branches;
>>> +
>>> +  /* Whether the loop contains a call instruction.  */
>>> +  bool has_call;
>>> +
>>> +  /* Whether the loop contains fp instructions.  */
>>> +  bool has_fp;
>>>  };
>>>
>>>  extern void iv_analysis_loop_init (struct loop *);
>>> @@ -413,6 +425,7 @@ extern void iv_analysis_done (void);
>>>
>>>  extern struct niter_desc *get_simple_loop_desc (struct loop *loop);
>>>  extern void free_simple_loop_desc (struct loop *loop);
>>> +void analyze_loop_insns (const struct loop *, struct niter_desc *desc);
>>>
>>>  static inline struct niter_desc *
>>>  simple_loop_desc (struct loop *loop)
>>> Index: params.def
>>> ===================================================================
>>> --- params.def  (revision 187013)
>>> +++ params.def  (working copy)
>>> @@ -312,6 +312,15 @@ 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 | tejohnson@google.com | 408-460-2413
>
>
>
> --
> Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413



-- 
Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413
Sign in to reply to this message.

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b