[Bug tree-optimization/99199] New: [9/10/11 Regression] Very large boolean expression leads to quite a few return statements

[Bug tree-optimization/99199] New: [9/10/11 Regression] Very large boolean expression leads to quite a few return statements

[tkoenig at gcc dot gnu.org]

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

            Bug ID: 99199
           Summary: [9/10/11 Regression] Very large boolean expression
                    leads to quite a few return statements
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: tkoenig at gcc dot gnu.org
  Target Milestone: ---

Created attachment 50233
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=50233&action=edit
C test case

The attached test case translated rather strangely with -O3.

The instruction sequence is very long, and it generates 42 return
instructions, quite a few of them at the end:

$ gcc -O3 -S tr.c
$ wc -l tr.s
504 tr.s
$ grep ret tr.s | wc -l
42

...

L24:
        movl    %r9d, %eax
        orl     %r8d, %eax
        xorl    $1, %eax
        jmp     .L112
.L131:
        ret
.L132:
        ret
.L140:
        ret
.L141:
        ret
.L145:
        ret
.L146:
        ret
.L148:
        ret
.L142:
        ret
.L143:
        ret
.L150:
        ret
.L152:
        ret
.L151:
        ret
.L138:
        ret
.L129:
        ret
.L147:
        ret
        .cfi_endproc

Seems to have been introduced with gcc 9, gcc 8 is fine.

[Bug tree-optimization/99199] [9/10/11 Regression] Very large boolean expression leads to quite a few return statements

[tkoenig at gcc dot gnu.org]

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

Thomas Koenig <tkoenig at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Version|unknown                     |11.0
   Target Milestone|---                         |11.0

[Bug tree-optimization/99199] [9/10/11 Regression] Very large boolean expression leads to quite a few return statements

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |glisse at gcc dot gnu.org,
                   |                            |jakub at gcc dot gnu.org,
                   |                            |law at gcc dot gnu.org

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
So many ret insns started with
r8-4600-g611a7c7e3799549b0de94c75ca810ba0d450b804
When looking just about number of lines in assembly, there was a rise in number
of lines (452 -> 476) already with
r8-4395-ge268a77b59cb788637d6db4829f0fd1ddf63f6f2 and then (479 -> 550) in
r8-4579-g0cea1d34f781ba9e08ffa82458f0410b398e9c93.
Though I don't see how r8-4579 could have changed something when there is no
inlining.

[Bug tree-optimization/99199] [9/10/11 Regression] Very large boolean expression leads to quite a few return statements

[jakub at gcc dot gnu.org]

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

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Until before pro_and_epilogue we have a bb with just code_label, note and
return reg use which has 65 predecessors.
The pro_and_epilogue pass turns that into 65 simple_return jumps.
The ret insns at the end are there since the bbro pass, before that they are at
various spots in the IL and depending on the branch probabilities could even
make sense.
I guess we'd need some simplified crossjumping either during the bbro pass when
going from cfglayout mode into cfgrtl mode, or afterwards (but not too many
passes are left there) that would be able to cross-jump bbs containing those:
(code_label 1552 999 925 128 147 (nil) [1 uses])
(note 925 1552 1389 128 [bb 128] NOTE_INSN_BASIC_BLOCK)
(insn 1389 925 926 128 (use (reg/i:QI 0 ax)) -1
     (nil))
(jump_insn 926 1389 927 128 (simple_return) 837 {simple_return_internal}
     (nil)
 -> simple_return)

[Bug rtl-optimization/99199] [9/10/11 Regression] Very large boolean expression leads to quite a few return statements

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2021-02-23
     Ever confirmed|0                           |1

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
x86 needs a conditional return ;)  But yeah, special-casing of BBs with
only a simple_return in BB-reorder or some cross-jumping might do the trick.

[Bug rtl-optimization/99199] [9/10/11 Regression] Very large boolean expression leads to quite a few return statements

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2

[Bug rtl-optimization/99199] [9/10/11/12 Regression] Very large boolean expression leads to quite a few return statements

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|11.0                        |11.2

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 11.1 has been released, retargeting bugs to GCC 11.2.

[Bug rtl-optimization/99199] [9/10/11/12 Regression] Very large boolean expression leads to quite a few return statements

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|11.2                        |11.3

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 11.2 is being released, retargeting bugs to GCC 11.3

[Bug rtl-optimization/99199] [9/10/11/12 Regression] Very large boolean expression leads to quite a few return statements

[pinskia at gcc dot gnu.org]

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

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I don't see it on the trunk really; I wonder what changed, I know there has
been many jump threading changes and even some phiopt changes which might have
changed this for the better.

Though I do see "label:ret" at least twice so it is not fully fixed.


One thing I did notice is that is LLVM saves a lot of registers:
        push    rbp
        push    r15
        push    r14
        push    r13
        push    r12
        push    rbx

:)
Which solves the problem there :).

[Bug rtl-optimization/99199] [9/10/11/12 Regression] Very large boolean expression leads to quite a few return statements

[pinskia at gcc dot gnu.org]

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

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Also for this testcase seem it should just return true even :).

[Bug rtl-optimization/99199] [9/10/11/12 Regression] Very large boolean expression leads to quite a few return statements

[jakub at gcc dot gnu.org]

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

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
It doesn't trigger anymore since
r12-3903-g0288527f47cec6698b31ccb3210816415506009e

[Bug rtl-optimization/99199] [9/10/11/12 Regression] Very large boolean expression leads to quite a few return statements

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|11.3                        |11.4

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 11.3 is being released, retargeting bugs to GCC 11.4.

[Bug rtl-optimization/99199] [10/11/12/13/14 Regression] Very large boolean expression leads to quite a few return statements

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|11.4                        |11.5

--- Comment #10 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 11.4 is being released, retargeting bugs to GCC 11.5.

[Bug rtl-optimization/99199] [11/12/13/14 Regression] Very large boolean expression leads to quite a few return statements

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pinskia at gcc dot gnu.org

--- Comment #11 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
  <bb 5> [local count: 234881022]:
  _1 = ~u_163(D);
  _2 = _1 & v_164(D);
  if (_2 != 0)
    goto <bb 40>; [50.00%]
  else
    goto <bb 6>; [50.00%]

  <bb 6> [local count: 55050240]:
  _357 = ~v_164(D);
  _363 = u_163(D) & _357;
  if (_363 != 0)
    goto <bb 40>; [53.57%]
  else
    goto <bb 7>; [46.43%]

This is literally just if (u != v) goto <bb 40>; else goto <bb 7>;

```
int f0(_Bool u, _Bool v)
{
  _Bool t1, t;
  t = !u & v;
  t1 = !v & u;
  if (t) goto L40;
  if (t1) goto L40;
  return 0;
L40:
  return 1;
}
int f1(_Bool u, _Bool v)
{
  _Bool t1, t;
  t = !u & v;
  if (t) goto L40;
  t1 = !v & u;
  if (t1) goto L40;
  return 0;
L40:
  return 1;
}
```

These should give the same result but don't.
Let me file that as a seperate bug ...

[Bug rtl-optimization/99199] [11 Regression] Very large boolean expression leads to quite a few return statements

[law at gcc dot gnu.org]

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

Jeffrey A. Law <law at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[11/12/13/14 Regression]    |[11 Regression] Very large
                   |Very large boolean          |boolean expression leads to
                   |expression leads to quite a |quite a few return
                   |few return statements       |statements

--- Comment #12 from Jeffrey A. Law <law at gcc dot gnu.org> ---
Fixed for gcc-12, so adjusting the regression markers.