Re: [RFC PATCH] Add inlining growth bias flag

[Richard Biener <richard dot guenther at gmail dot com>]

On Fri, Sep 6, 2019 at 12:59 PM Graham Markall
<graham.markall@embecosm.com> wrote:
>
> This patch is an RFC to invite comments as to whether the approach
> to solving the problem is a suitable one for upstream GCC, or whether
> there are alternative approaches that would be recommended.
>
> Motivation
> ----------
>
> We have observed that in some cases the estimation of callee growth for
> inlining particular functions can be tuned for better overall code size
> with particular programs on particular targets. Although modification of
> the heuristics to make a general improvement is a difficult problem to
> tackle, simply biasing the growth by a fixed amount can lead to
> improvements in code size within the context of a particular program.
>
> This has first been tested on a proprietary program, where setting the
> growth bias to -2 resulted in a saving of 1.35% in the text section size
> (62396 bytes as opposed to 63252 bytes). Using the Embench suite (
> https://www.embench.org/ ) for a riscv32 bare-metal target with -Os also
> shows that adjusting the inline growth estimate carefully can also
> reduce code size. Results presented here are percentages relative to the
> Embench reference platform (which is the standard way of presenting
> Embench results) for values of the bias from -2 to 2:
>
> Benchmark       -2      -1      0       1       2
> aha-mont64       99.05   99.05   99.05   99.05   99.05
> crc32           100.00  100.00  100.00  100.00  100.00
> cubic            94.66   94.66   94.66   94.66   94.66
> edn             100.00  100.00  100.00  100.00  100.00
> huffbench        99.88   99.88   99.88   99.88   99.88
> matmult-int     100.00  100.00  100.00  102.86  102.86
> minver           97.96   97.96   97.96  106.88  106.88
> nbody            98.87   98.87   98.87   98.87   98.87
> nettle-aes       99.31   99.10   99.10   99.10   99.10
> nettle-sha256    99.89   99.89   99.89   99.89   99.89
> nsichneu        100.00  100.00  100.00  100.00  100.00
> picojpeg        102.56  102.54   99.73   99.38   99.28
> qrduino          99.70   99.70   99.90   99.90   99.90
> sglib-combined   95.52  100.00  100.00  100.43  101.12
> slre            100.66  100.66   99.09   98.85   98.85
> st               96.36   96.36   96.36   96.82   96.82
> statemate       100.00  100.00  100.00  100.00  100.00
> ud              100.00  100.00  100.00  100.00  100.00
> wikisort         99.48   99.48   99.48   99.48   99.48
> Mean             99.14   99.36   99.15   99.77   99.80
>
> In most cases, leaving the bias at 0 (unmodified) produces the smallest
> code. However, there are some cases where an alternative value prevails,
> The "Best Diff" column shows the reduction in size compared to leaving
> the bias at 0, for cases where changing it yielded an improvement:
>
> Benchmark       Best    Worst   Best diff
> aha-mont64      0       0
> crc32           0       0
> cubic           0       0
> edn             0       0
> huffbench       0       0
> matmult-int     0       1 / 2
> minver          0       1 / 2
> nbody           0       0
> nettle-aes      0       -2
> nettle-sha256   0       0
> nsichneu        0       0
> picojpeg        2       -2      -0.45%
> qrduino         -1 /-2  0       -0.20%
> sglib-combined  -2      1       -4.48%
> slre            1 / 2   -1 / -2 -0.24%
> st              0       1 / 2
> statemate       0       0
> ud              0       0
> wikisort        0       0
>
>
> In summary, for this test setup:
>
> - In most cases, leaving the growth bias at 0 is optimal.
> - Biasing the growth estimate positively may either increase or decrease
>   code size.
> - Biasing the estimate negatively may also either increase or decrease
>   code size.
> - In a small number of cases, biasing the growth estimate improves code
>   size (up to 4.48% smaller for sglib-combined).
>
>
> Patch
> -----
>
> The growth bias can be set with a flag:
>
>   -finline-growth-bias=<number>
>
> which controls the bias (an increase or decrease) of the inline growth
> in ipa-inline.c. In cases where the bias would result in a negative
> function size, we clip the growth estimate so that adding the growth to
> the size of the function results in a size of 0, by setting the growth
> to the negative of the function size.
>
> There is not a great deal of validation of the argument - if a
> non-integer is passed as the parameter (e.g. -finline-growth-bias=xyz),
> it will be as if the parameter were 0. More validation could be added if
> necessary. It seemed to me that GCC's infrastructure doesn't seem to
> anticipate option values / parameters that could contain negative
> values. For parameters, -1 seemed to represent an error and could result
> in an ICE (-2 etc. pass through OK though). For options, I looked at the
> UInteger and Host_Wide_Int numeric types, but they both expect a
> positive integer. I did consider extending this with an Integer type
> that could accept positive and negative integers, (e.g. starting with
> augmenting switch_bit_fields in opt-functions.awk) but rooting out
> assumptions of non-negative integer values in places further down seemed
> like an onerous task.
>
>
> Further discussion
> ------------------
>
> Given that a default setting of 0 (equivalent to current behaviour)
> should provide for some potential improvement in code size in individual
> situations where it is critical (albeit using a rather coarse instrument
> to do so), without affecting the general case - is the addition of such
> a flag to GCC likely to be considered an acceptable inclusion for this
> purpose?

I agree with Jeff that this should be a --param like all other inliner
tunings.

What the bias achieves is adjusting functions size estimate by
an absolute value so I'd implement it there like

Index: gcc/ipa-fnsummary.c
===================================================================
--- gcc/ipa-fnsummary.c (revision 275680)
+++ gcc/ipa-fnsummary.c (working copy)
@@ -2467,6 +2467,8 @@ compute_fn_summary (struct cgraph_node *
       break;
   node->calls_comdat_local = (e != NULL);

+  info->self_size = MAX (0, info->self_size + PARAM_VALUE
(PARAM_INLINE_FNSIZE_BIAS));
+
   /* Inlining characteristics are maintained by the cgraph_mark_inline.  */
   info->size = info->self_size;
   info->stack_frame_offset = 0;

which has the advantage to reduce the number of times the adjustment is
done.  I also think that you can use --param unlinlined-function-insns to
get the same effect of your parameter, but it doesn't allow negative values
though an effective negative value of -2 is possible since the default is 2.
The parameter is used during summary computation and so if we want
an additional parameter it could be accounted for at the same place this one is.

Richard.

>
> gcc/ChangeLog:
>
>         * common.opt: Add -finline-growth-bias= flag.
>         * ipa-inline.h (estimate_edge_growth): Adjust inline
>         growth by bias factor, if supplied.
> ---
>  gcc/common.opt   |  4 ++++
>  gcc/ipa-inline.h | 39 ++++++++++++++++++++++++++++++++++++++-
>  2 files changed, 42 insertions(+), 1 deletion(-)
>
> diff --git a/gcc/common.opt b/gcc/common.opt
> index c1605385712..4725df2c477 100644
> --- a/gcc/common.opt
> +++ b/gcc/common.opt
> @@ -1670,6 +1670,10 @@ finline-limit=
>  Common RejectNegative Joined UInteger
>  -finline-limit=<number>        Limit the size of inlined functions to <number>.
>
> +finline-growth-bias=
> +Common RejectNegative Joined Var(flag_inline_growth_bias) Init(0)
> +-finline-growth-bias=<number>  Adjust the growth estimate for inlined functions by <number>.
> +
>  finline-atomics
>  Common Report Var(flag_inline_atomics) Init(1) Optimization
>  Inline __atomic operations when a lock free instruction sequence is available.
> diff --git a/gcc/ipa-inline.h b/gcc/ipa-inline.h
> index 18c8e1eebd0..65e105b00a2 100644
> --- a/gcc/ipa-inline.h
> +++ b/gcc/ipa-inline.h
> @@ -84,7 +84,44 @@ estimate_edge_growth (struct cgraph_edge *edge)
>  {
>    ipa_call_summary *s = ipa_call_summaries->get (edge);
>    gcc_checking_assert (s->call_stmt_size || !edge->callee->analyzed);
> -  return (estimate_edge_size (edge) - s->call_stmt_size);
> +
> +  if (dump_file)
> +    {
> +      const char *caller_name
> +       = edge->caller->ultimate_alias_target ()->name ();
> +      const char *callee_name
> +       = edge->callee->ultimate_alias_target ()->name ();
> +
> +      fprintf (dump_file, "Estimate edge growth for %s -> %s\n",
> +              caller_name, callee_name);
> +      fprintf (dump_file, "\t estimate_edge_size = %d\n",
> +              estimate_edge_size (edge));
> +      fprintf (dump_file, "\t s (%p) ->call_stmt_size = %d\n",
> +              ((void *) s), s->call_stmt_size);
> +    }
> +
> +  int growth = (estimate_edge_size (edge) - s->call_stmt_size);
> +
> +  int sz = 0;
> +  if (flag_inline_growth_bias)
> +    sz = strtol(flag_inline_growth_bias, NULL, 0);
> +  if (sz != 0)
> +    {
> +      struct cgraph_node *caller = edge->caller;
> +      ipa_fn_summary *fs = ipa_fn_summaries->get (caller);
> +      if (dump_file)
> +       fprintf (dump_file, "\t Adjusting growth by %d\n", sz);
> +      growth += sz;
> +      if (growth < 0 && fs->size + growth < 0) {
> +       if (dump_file)
> +          fprintf (dump_file, "\t Growth %d would shrink size beneath zero.\n", growth);
> +       growth = -fs->size;
> +        if (dump_file)
> +         fprintf (dump_file, "\t Setting growth to %d to make size zero.\n", growth);
> +      }
> +    }
> +
> +  return growth;
>  }
>
>  /* Return estimated callee runtime increase after inlining
> --
> 2.21.0
>