On Fri, Mar 17, 2023 at 6:16 AM Philipp Tomsich
<philipp.toms...@vrull.eu> wrote:
>
> On Fri, 17 Mar 2023 at 09:31, Richard Biener <richard.guent...@gmail.com>
> wrote:
> >
> > On Thu, Mar 16, 2023 at 4:27 PM Manolis Tsamis <manolis.tsa...@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.
Equality comparisons against 0 are also slightly cheaper than equality
comparisons against 1 on x86, though it's a code-size difference, not
an instruction-count difference. Not sure this changes the
story--just pointing out that this optimization might be slightly more
generally applicable than it initially seems.
>
> 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.guent...@gmail.com>
> wrote:
> >
> > On Thu, Mar 16, 2023 at 4:27 PM Manolis Tsamis <manolis.tsa...@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.tsa...@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
> > >
