Re: [PATCH] fwprop: Prevent infinite looping (PR79405)

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

On Thu, Mar 23, 2017 at 3:58 PM, Segher Boessenkool
<segher@kernel.crashing.org> wrote:
> The algorithm fwprop uses never reconsiders a possible propagation,
> although it could succeed if the def (in the def-use to propagate)
> has changed.  This causes fwprop to do infinite propagations, like
> in the scenario in the PR, where we end up with effectively
>   B = A
>   A = B
>   D = A
> where only propagations into the last statement are still tried, and
> that loops (it becomes D = B, then back to D = A, etc.)
>
> Fixing this properly isn't easy; this patch instead limits the number
> of propagations performed to the number of uses we originally had,
> which is the maximum number of propagations that can be done if there
> are no such infinite loops.
>
> Bootstrapped and regression checked on powerpc64-linux {-m64,-m32};
> is this okay for trunk?

https://gcc.gnu.org/ml/gcc-patches/2017-02/msg01485.html

?

>
> Segher
>
>
> 2017-03-23  Segher Boessenkool  <segher@kernel.crashing.org>
>
>         PR rtl-optimization/79405
>         * fwprop.c (propagations_left): New variable.
>         (forward_propagate_into): Decrement it.
>         (fwprop_init): Initialize it.
>         (fw_prop): If the variable has reached zero, stop propagating.
>         (fwprop_addr): Ditto.
>
> gcc/testsuite/
>         PR rtl-optimization/79405
>         gcc.dg/pr79405.c: New testcase.
>
> ---
>  gcc/fwprop.c                   | 17 ++++++++++++++++
>  gcc/testsuite/gcc.dg/pr79405.c | 45 ++++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 62 insertions(+)
>  create mode 100644 gcc/testsuite/gcc.dg/pr79405.c
>
> diff --git a/gcc/fwprop.c b/gcc/fwprop.c
> index 285fb1a..0ab25ef 100644
> --- a/gcc/fwprop.c
> +++ b/gcc/fwprop.c
> @@ -120,6 +120,13 @@ static vec<df_ref> use_def_ref;
>  static vec<df_ref> reg_defs;
>  static vec<df_ref> reg_defs_stack;
>
> +/* The maximum number of propagations that are still allowed.  If we do
> +   more propagations than originally we had uses, we must have ended up
> +   in a propagation loop, as in PR79405.  Until the algorithm fwprop
> +   uses can obviously not get into such loops we need a workaround like
> +   this.  */
> +static int propagations_left;
> +
>  /* The MD bitmaps are trimmed to include only live registers to cut
>     memory usage on testcases like insn-recog.c.  Track live registers
>     in the basic block and do not perform forward propagation if the
> @@ -1407,6 +1414,8 @@ forward_propagate_into (df_ref use)
>    if (forward_propagate_and_simplify (use, def_insn, def_set)
>        || forward_propagate_subreg (use, def_insn, def_set))
>      {
> +      propagations_left--;
> +
>        if (cfun->can_throw_non_call_exceptions
>           && find_reg_note (use_insn, REG_EH_REGION, NULL_RTX)
>           && purge_dead_edges (DF_REF_BB (use)))
> @@ -1434,6 +1443,8 @@ fwprop_init (void)
>    active_defs = XNEWVEC (df_ref, max_reg_num ());
>    if (flag_checking)
>      active_defs_check = sparseset_alloc (max_reg_num ());
> +
> +  propagations_left = DF_USES_TABLE_SIZE ();
>  }
>
>  static void
> @@ -1480,6 +1491,9 @@ fwprop (void)
>
>    for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
>      {
> +      if (!propagations_left)
> +       break;
> +
>        df_ref use = DF_USES_GET (i);
>        if (use)
>         if (DF_REF_TYPE (use) == DF_REF_REG_USE
> @@ -1540,6 +1554,9 @@ fwprop_addr (void)
>       end, and we'll go through them as well.  */
>    for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
>      {
> +      if (!propagations_left)
> +       break;
> +
>        df_ref use = DF_USES_GET (i);
>        if (use)
>         if (DF_REF_TYPE (use) != DF_REF_REG_USE
> diff --git a/gcc/testsuite/gcc.dg/pr79405.c b/gcc/testsuite/gcc.dg/pr79405.c
> new file mode 100644
> index 0000000..c17baff
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/pr79405.c
> @@ -0,0 +1,45 @@
> +/* PR rtl-optimization/79405 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2" } */
> +
> +char cz;
> +long long int xx, u2;
> +
> +void
> +qv (int js, int wl)
> +{
> +  if (js != 0)
> +    {
> +      short int sc;
> +      int *at = (int *)&sc;
> +      long long int gx = 0;
> +
> +      for (;;)
> +       {
> +         *at = 0;
> +         js /= sc;
> +
> +         for (wl = 0; wl < 2; ++wl)
> +           {
> +             xx = gx;
> +             u2 %= xx > 0;
> +             cz /= u2;
> +
> + fa:
> +             if (cz != u2)
> +               {
> +                 gx |= js;
> +                 cz = gx / js;
> +               }
> +           }
> +       }
> +
> + yq:
> +      wl /= 0x80000000;
> +      u2 = wl;
> +      u2 |= (wl != 0) | (wl != 0 && gx != 0);
> +      js = u2;
> +      goto fa;
> +    }
> +  goto yq;
> +}
> --
> 1.9.3
>