Re: [PATCH v1] [RFC] Improve folding for comparisons with zero in tree-ssa-forwprop.

[Philipp Tomsich <philipp.tomsich@vrull.eu>]

On Fri, 17 Mar 2023 at 09:31, Richard Biener <richard.guenther@gmail.com> wrote:
>
> On Thu, Mar 16, 2023 at 4:27 PM Manolis Tsamis <manolis.tsamis@vrull.eu> wrote:
> >
> > For this C testcase:
> >
> > void g();
> > void f(unsigned int *a)
> > {
> >   if (++*a == 1)
> >     g();
> > }
> >
> > GCC will currently emit a comparison with 1 by using the value
> > of *a after the increment. This can be improved by comparing
> > against 0 and using the value before the increment. As a result
> > there is a potentially shorter dependancy chain (no need to wait
> > for the result of +1) and on targets with compare zero instructions
> > the generated code is one instruction shorter.
>
> The downside is we now need two registers and their lifetime overlaps.
>
> Your patch mixes changing / inverting a parameter (which seems unneeded
> for the actual change) with preferring compares against zero.
>
> What's the reason to specifically prefer compares against zero?  On x86
> we have add that sets flags, so ++*a == 0 would be preferred, but
> for your sequence we'd need a test reg, reg; branch on zero, so we do
> not save any instruction.

AArch64, RISC-V and MIPS support a branch-on-(not-)equals-zero, while
comparing against a constant requires to load any non-zero value into
a register first.
This feels a bit like we need to call onto the backend to check
whether comparisons against 0 are cheaper.

Obviously, the underlying issue become worse if the immediate can not
be built up in a single instruction.
Using RISC-V as an example (primarily, as RISC-V makes it particularly
easy to run into multi-instruction sequences for constants), we can
construct the following case:

  void f(unsigned int *a)
  {
    if ((*a += 0x900) == 0x900)
       g();
  }

which GCC 12.2.0 (trunk may already be small enough to reuse the
constant once loaded into register, but I did not check…) with -O3
turns into:

f:
  lw a4,0(a0)
  li a5,4096
  addiw a5,a5,-1792
  addw a4,a5,a4
  li a5,4096
  sw a4,0(a0)
  addi a5,a5,-1792
  beq a4,a5,.L4
  ret
.L4:
  tail g

Thanks,
Philipp.


On Fri, 17 Mar 2023 at 09:31, Richard Biener <richard.guenther@gmail.com> wrote:
>
> On Thu, Mar 16, 2023 at 4:27 PM Manolis Tsamis <manolis.tsamis@vrull.eu> wrote:
> >
> > For this C testcase:
> >
> > void g();
> > void f(unsigned int *a)
> > {
> >   if (++*a == 1)
> >     g();
> > }
> >
> > GCC will currently emit a comparison with 1 by using the value
> > of *a after the increment. This can be improved by comparing
> > against 0 and using the value before the increment. As a result
> > there is a potentially shorter dependancy chain (no need to wait
> > for the result of +1) and on targets with compare zero instructions
> > the generated code is one instruction shorter.
>
> The downside is we now need two registers and their lifetime overlaps.
>
> Your patch mixes changing / inverting a parameter (which seems unneeded
> for the actual change) with preferring compares against zero.
>
> What's the reason to specifically prefer compares against zero?  On x86
> we have add that sets flags, so ++*a == 0 would be preferred, but
> for your sequence we'd need a test reg, reg; branch on zero, so we do
> not save any instruction.
>
> We do have quite some number of bugreports with regards to making VRPs
> life harder when splitting things this way.  It's easier for VRP to handle
>
>   _1 = _2 + 1;
>   if (_1 == 1)
>
> than it is
>
>   _1 = _2 + 1;
>   if (_2 == 0)
>
> where VRP fails to derive a range for _1 on the _2 == 0 branch.  So besides
> the life-range issue there's other side-effects as well.  Maybe ranger meanwhile
> can handle the above case?
>
> What's the overall effect of the change on a larger code base?
>
> Thanks,
> Richard.
>
> >
> > Example from Aarch64:
> >
> > Before
> >         ldr     w1, [x0]
> >         add     w1, w1, 1
> >         str     w1, [x0]
> >         cmp     w1, 1
> >         beq     .L4
> >         ret
> >
> > After
> >         ldr     w1, [x0]
> >         add     w2, w1, 1
> >         str     w2, [x0]
> >         cbz     w1, .L4
> >         ret
> >
> > gcc/ChangeLog:
> >
> >         * tree-ssa-forwprop.cc (combine_cond_expr_cond):
> >         (forward_propagate_into_comparison_1): Optimize
> >         for zero comparisons.
> >
> > Signed-off-by: Manolis Tsamis <manolis.tsamis@vrull.eu>
> > ---
> >
> >  gcc/tree-ssa-forwprop.cc | 41 +++++++++++++++++++++++++++-------------
> >  1 file changed, 28 insertions(+), 13 deletions(-)
> >
> > diff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc
> > index e34f0888954..93d5043821b 100644
> > --- a/gcc/tree-ssa-forwprop.cc
> > +++ b/gcc/tree-ssa-forwprop.cc
> > @@ -373,12 +373,13 @@ rhs_to_tree (tree type, gimple *stmt)
> >  /* Combine OP0 CODE OP1 in the context of a COND_EXPR.  Returns
> >     the folded result in a form suitable for COND_EXPR_COND or
> >     NULL_TREE, if there is no suitable simplified form.  If
> > -   INVARIANT_ONLY is true only gimple_min_invariant results are
> > -   considered simplified.  */
> > +   ALWAYS_COMBINE is false then only combine it the resulting
> > +   expression is gimple_min_invariant or considered simplified
> > +   compared to the original.  */
> >
> >  static tree
> >  combine_cond_expr_cond (gimple *stmt, enum tree_code code, tree type,
> > -                       tree op0, tree op1, bool invariant_only)
> > +                       tree op0, tree op1, bool always_combine)
> >  {
> >    tree t;
> >
> > @@ -398,17 +399,31 @@ combine_cond_expr_cond (gimple *stmt, enum tree_code code, tree type,
> >    /* Canonicalize the combined condition for use in a COND_EXPR.  */
> >    t = canonicalize_cond_expr_cond (t);
> >
> > -  /* Bail out if we required an invariant but didn't get one.  */
> > -  if (!t || (invariant_only && !is_gimple_min_invariant (t)))
> > +  if (!t)
> >      {
> >        fold_undefer_overflow_warnings (false, NULL, 0);
> >        return NULL_TREE;
> >      }
> >
> > -  bool nowarn = warning_suppressed_p (stmt, OPT_Wstrict_overflow);
> > -  fold_undefer_overflow_warnings (!nowarn, stmt, 0);
> > +  if (always_combine || is_gimple_min_invariant (t))
> > +    {
> > +      bool nowarn = warning_suppressed_p (stmt, OPT_Wstrict_overflow);
> > +      fold_undefer_overflow_warnings (!nowarn, stmt, 0);
> > +      return t;
> > +    }
> >
> > -  return t;
> > +  /* If the result of folding is a zero comparison treat it preferentially.  */
> > +  if (TREE_CODE_CLASS (TREE_CODE (t)) == tcc_comparison
> > +      && integer_zerop (TREE_OPERAND (t, 1))
> > +      && !integer_zerop (op1))
> > +    {
> > +      bool nowarn = warning_suppressed_p (stmt, OPT_Wstrict_overflow);
> > +      fold_undefer_overflow_warnings (!nowarn, stmt, 0);
> > +      return t;
> > +    }
> > +
> > +  fold_undefer_overflow_warnings (false, NULL, 0);
> > +  return NULL_TREE;
> >  }
> >
> >  /* Combine the comparison OP0 CODE OP1 at LOC with the defining statements
> > @@ -432,7 +447,7 @@ forward_propagate_into_comparison_1 (gimple *stmt,
> >        if (def_stmt && can_propagate_from (def_stmt))
> >         {
> >           enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
> > -         bool invariant_only_p = !single_use0_p;
> > +         bool always_combine = single_use0_p;
> >
> >           rhs0 = rhs_to_tree (TREE_TYPE (op1), def_stmt);
> >
> > @@ -442,10 +457,10 @@ forward_propagate_into_comparison_1 (gimple *stmt,
> >                    && TREE_CODE (TREE_TYPE (TREE_OPERAND (rhs0, 0)))
> >                       == BOOLEAN_TYPE)
> >                   || TREE_CODE_CLASS (def_code) == tcc_comparison))
> > -           invariant_only_p = false;
> > +           always_combine = true;
> >
> >           tmp = combine_cond_expr_cond (stmt, code, type,
> > -                                       rhs0, op1, invariant_only_p);
> > +                                       rhs0, op1, always_combine);
> >           if (tmp)
> >             return tmp;
> >         }
> > @@ -459,7 +474,7 @@ forward_propagate_into_comparison_1 (gimple *stmt,
> >         {
> >           rhs1 = rhs_to_tree (TREE_TYPE (op0), def_stmt);
> >           tmp = combine_cond_expr_cond (stmt, code, type,
> > -                                       op0, rhs1, !single_use1_p);
> > +                                       op0, rhs1, single_use1_p);
> >           if (tmp)
> >             return tmp;
> >         }
> > @@ -470,7 +485,7 @@ forward_propagate_into_comparison_1 (gimple *stmt,
> >        && rhs1 != NULL_TREE)
> >      tmp = combine_cond_expr_cond (stmt, code, type,
> >                                   rhs0, rhs1,
> > -                                 !(single_use0_p && single_use1_p));
> > +                                 single_use0_p && single_use1_p);
> >
> >    return tmp;
> >  }
> > --
> > 2.34.1
> >