[Bug tree-optimization/94846] New: Failure to optimize jnc+inc into adc

[Bug tree-optimization/94846] New: Failure to optimize jnc+inc into adc

[gabravier at gmail dot com]

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

            Bug ID: 94846
           Summary: Failure to optimize jnc+inc into adc
           Product: gcc
           Version: 10.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: gabravier at gmail dot com
  Target Milestone: ---

unsigned f(unsigned *p, unsigned x)
{
    unsigned u = *p;
    *p += x;
    if (u > *p)
        ++*p;

    return *p;
}

This is what LLVM outputs with -O3 : 

f(unsigned int*, unsigned int): # @f(unsigned int*, unsigned int)
  mov eax, esi
  add eax, dword ptr [rdi]
  adc eax, 0
  mov dword ptr [rdi], eax
  ret

This is what GCC outputs :

f(unsigned int*, unsigned int):
  mov eax, esi
  add eax, DWORD PTR [rdi]
  jnc .L6
  add eax, 1
.L6:
  mov DWORD PTR [rdi], eax
  ret

GCC should most likely be optimizing this to the same thing as LLVM.

[Bug rtl-optimization/94846] Failure to optimize jnc+inc into adc

[gabravier at gmail dot com]

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

Gabriel Ravier <gabravier at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|x86_64-* i?86-*-*           |

--- Comment #1 from Gabriel Ravier <gabravier at gmail dot com> ---
Some extra notes : 

This also occurs on i?86.

This is the LLVM output :

f(unsigned int*, unsigned int): # @f(unsigned int*, unsigned int)
  mov ecx, dword ptr [esp + 4]
  mov eax, dword ptr [ecx]
  add eax, dword ptr [esp + 8]
  adc eax, 0
  mov dword ptr [ecx], eax
  ret

This is the GCC output :

f(unsigned int*, unsigned int):
  mov edx, DWORD PTR [esp+4]
  mov eax, DWORD PTR [edx]
  add eax, DWORD PTR [esp+8]
  jnc .L6
  add eax, 1
.L6:
  mov DWORD PTR [edx], eax
  ret

This also occurs on aarch64.

This is the LLVM output : 

f(unsigned int*, unsigned int): // @f(unsigned int*, unsigned int)
  ldr w8, [x0]
  adds w8, w8, w1
  cinc w8, w8, hs
  str w8, [x0]
  mov w0, w8
  ret

This is the GCC output (as of GCC 9.2, didn't have the time to check GCC 10 for
aarch64 ) :

f:
  ldr w2, [x0]
  mov x3, x0
  adds w0, w2, w1
  bcc .L6
  add w0, w0, 1
.L6:
  str w0, [x3]
  ret

[Bug rtl-optimization/94846] Failure to optimize jnc+inc into adc

[gabravier at gmail dot com]

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

--- Comment #2 from Gabriel Ravier <gabravier at gmail dot com> ---
More notes : 
This seems to be generic to all targets, I've also been able to verify it on
ARM.

This only occurs when p is a pointer. This code :

unsigned f(unsigned p, unsigned x)
{
    unsigned u = p;
    p += x;
    if (u > p)
        ++p;

    return p;
}

results in 

f(unsigned int, unsigned int):
  add edi, esi
  mov eax, edi
  adc eax, 0
  ret

with both GCC and LLVM

[Bug tree-optimization/94846] Failure to optimize jnc+inc into adc

[ubizjak at gmail dot com]

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

Uroš Bizjak <ubizjak at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2020-11-25
             Status|UNCONFIRMED                 |NEW
                 CC|                            |rguenth at gcc dot gnu.org
          Component|rtl-optimization            |tree-optimization

--- Comment #3 from Uroš Bizjak <ubizjak at gmail dot com> ---
This looks like a tree-optimization problem. A store to *p_5(D) could sink all
the way to bb5. RTL gets expanded from:

  ...
  if (_10 != 0)
    goto <bb 4>; [50.00%]
  else
    goto <bb 3>; [50.00%]

  <bb 3> [local count: 536870912]:
  *p_5(D) = _1;
  goto <bb 5>; [100.00%]

  <bb 4> [local count: 536870913]:
  _2 = _1 + 1;
  *p_5(D) = _2;

  <bb 5> [local count: 1073741824]:
  # prephitmp_11 = PHI <_1(3), _2(4)>
  return prephitmp_11;

ifcvt RTL pass (_.ce1) is unable to convert:

   ...
   17: r86:SI=r89:SI
      REG_DEAD r89:SI
   18: flags:CCZ=cmp(r85:SI,0)
      REG_DEAD r85:SI
   19: pc={(flags:CCZ!=0)?L24:pc}
      REG_DEAD flags:CCZ
      REG_BR_PROB 536870916
   20: NOTE_INSN_BASIC_BLOCK 5
   21: [r87:DI]=r89:SI
      REG_DEAD r87:DI
      ; pc falls through to BB 7
   24: L24:
   25: NOTE_INSN_BASIC_BLOCK 6
   26: {r86:SI=r89:SI+0x1;clobber flags:CC;}
      REG_UNUSED flags:CC
   27: [r87:DI]=r86:SI
      REG_DEAD r87:DI
   32: L32:
   35: NOTE_INSN_BASIC_BLOCK 7
   ...


IF-THEN-ELSE-JOIN block found, pass 2, test 2, then 5, else 6, join 7

===

In case p is not a pointer, RTL optimizers start with:

  ...
  if (_8 != 0)
    goto <bb 3>; [50.00%]
  else
    goto <bb 4>; [50.00%]

  <bb 3> [local count: 536870913]:
  p_5 = p_4 + 1;

  <bb 4> [local count: 1073741824]:
  # p_1 = PHI <p_4(2), p_5(3)>
  return p_1;

and RTL ifcvt pass is able to convert this form to addcc:

IF-THEN-JOIN block found, pass 2, test 2, then 5, join 6

if-conversion succeeded through noce_try_addcc

[Bug tree-optimization/94846] Failure to optimize jnc+inc into adc

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
The sinking opportunity is a secondary one, sink does

Sinking # .MEM_8 = VDEF <.MEM_4(D)>
*p_5(D) = _1;
 from bb 2 to bb 5

but then not sinking further with the store commoning I implemented for GCC 11.

  <bb 2> [local count: 1073741824]:
  u_6 = *p_5(D);
  _1 = u_6 + x_7(D);
  if (_1 < u_6)
    goto <bb 3>; [50.00%]
  else
    goto <bb 5>; [50.00%]

  <bb 5> [local count: 536870912]:
  *p_5(D) = _1;
  goto <bb 4>; [100.00%]

  <bb 3> [local count: 536870913]:
  _2 = _1 + 1;
  *p_5(D) = _2;

  <bb 4> [local count: 1073741824]:
  # prephitmp_11 = PHI <_1(5), _2(3)>
  return prephitmp_11;

regular sinking works up the postdom tree.  In reality we'd have to iterate
sinking and commoning as can be seen here given we're lazy and not computing
a combined dataflow.

[Bug tree-optimization/94846] Failure to optimize jnc+inc into adc

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
After r12-897 (which added a late sink pass), we get the following in
.optimized:
  if (_10 != 0)
    goto <bb 3>; [50.00%]
  else
    goto <bb 4>; [50.00%]

  <bb 3> [local count: 536870913]:
  _2 = _1 + 1;

  <bb 4> [local count: 1073741824]:
  # prephitmp_11 = PHI <_1(2), _2(3)>
  # _13 = PHI <_1(2), _2(3)>
  *p_5(D) = _13;
  return prephitmp_11;

Notice how prephitmp_11 and _13 are the same but no RTL optimizers handles
that.