[Bug tree-optimization/99142] New: [11 Regression] __builtin_clz match.pd transformation too greedy

[Bug tree-optimization/99142] New: [11 Regression] __builtin_clz match.pd transformation too greedy

[hp at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99142

            Bug ID: 99142
           Summary: [11 Regression] __builtin_clz match.pd transformation
                    too greedy
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: hp at gcc dot gnu.org
  Target Milestone: ---

Created attachment 50215
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=50215&action=edit
test-case  gcc.dg/tree-ssa/prXXXXX.c

See the attachment test-case, which is de-macroized from
gcc.target/cris/pr93372-31.c, which started regressing with d2eb616a0f7b
"match.pd: Add clz(X) == 0 -> (int)X < 0 etc. simpifications [PR94802]"

In the test-case, the result *is* used more than once (twice more besides the
transformed compare) and the match.pd matching expression *does* have the s
modifier: (op (clz:s @0) INTEGER_CST@1), but since the transformation doesn't
result in "an expression with more than one operator" (cf.
doc/match-and-simplify.texi), it's still performed.

The result is that the *input* is kept alive *after* the clz instruction.  This
generally causes additional register pressure and throws away any re-use of
incidentally computed condition codes.  Though the original observation was for
cris-elf, where the effect is more dramatic, the effect is visible even for
x86_64 and of the same kind: losing the re-use of non-zero condition codes from
the bsrl instruction, i.e. the transformation causes an additional instruction:

--- prXXXXX.s.64good    2021-02-17 02:26:57.646183108 +0100
+++ prXXXXX.s.64bad     2021-02-17 02:27:33.124979464 +0100
@@ -9,7 +9,8 @@ f:
        bsrl    %edi, %eax
        xorl    $31, %eax
        movl    %eax, (%rsi)
-       je      .L1
+       testl   %edi, %edi
+       js      .L1
        movl    %eax, (%rdx)
 .L1:
        ret

To wit, my conclusion is that the matching condition should better be gated by
single_use(clz result) *everywhere*.

Alternatively, the "s" modifier adjusted somehow, but I'm not sure besides
obviously just making it *exactly* single_use, and that suggestion has been
shot down before.

Maybe there should be an additional *reverse* version of the "simplification",
replacing "y = clz(x); if (x < 0) ...stuff using y but not x" -> "y = clz(x);
if (y != 0) ...stuff using y but not x"!

[Bug tree-optimization/99142] [11 Regression] __builtin_clz match.pd transformation too greedy

[hp at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99142

Hans-Peter Nilsson <hp at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
           Assignee|unassigned at gcc dot gnu.org      |hp at gcc dot gnu.org
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2021-02-17

[Bug tree-optimization/99142] [11 Regression] __builtin_clz match.pd transformation too greedy

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99142

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |11.0
           Keywords|                            |missed-optimization

[Bug tree-optimization/99142] [11 Regression] __builtin_clz match.pd transformation too greedy

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99142

--- Comment #1 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Hans-Peter Nilsson <hp@gcc.gnu.org>:

https://gcc.gnu.org/g:a2ef38b1f94dd108046e702ad46dcd8e9b34625e

commit r11-7277-ga2ef38b1f94dd108046e702ad46dcd8e9b34625e
Author: Hans-Peter Nilsson <hp@axis.com>
Date:   Tue Feb 16 22:27:53 2021 +0100

    match.pd: Restrict clz cmp 0 replacement by single_use, PR99142

    If we're not going to eliminate the clz, it's better for the
    comparison to use that result than its input, so we don't
    extend the lifetime of the input.  Also, an additional use
    of the result is more likely cheaper than a compare of the
    input, in particular considering that the clz may have made
    available a non-zero condition matching the original use.
    The "s" modifier doesn't stop this situation, as the
    transformation wouldn't result in "an expression with more
    than one operator"; a gating single_use condition on the
    result is necessary.

    gcc:
            PR tree-optimization/99142
            * match.pd (clz cmp 0): Gate replacement on single_use of clz
result.

    gcc/testsuite:
            PR tree-optimization/99142
            * gcc.dg/tree-ssa/pr99142.c: New test.

[Bug tree-optimization/99142] [11 Regression] __builtin_clz match.pd transformation too greedy

[hp at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99142

Hans-Peter Nilsson <hp at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #2 from Hans-Peter Nilsson <hp at gcc dot gnu.org> ---
.