[Bug tree-optimization/37810] Bad store sinking job

[Bug tree-optimization/37810] Bad store sinking job

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2009-04-03 12:34:44         |2021-7-25

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
For the reduced testcase in comment #2 I get now:
4.8.0+:
.L4:
        addl    $1, %eax
        movl    %eax, (%rbx)
        cmpl    4(%rbx), %eax
        je      .L8
.L3:
        testl   %eax, %eax
        jne     .L4

4.7.4 and before:
.L3:
        testl   %eax, %eax
        je      .L8
        addl    $1, %eax
        cmpl    4(%rbx), %eax
        movl    %eax, (%rbx)
        jne     .L3

Or on the trunk at the gimple level:
  <bb 3> [local count: 1014686025]:
  _1 = prephitmp_10 + 1;
  iter_6(D)->n = _1;
  _2 = iter_6(D)->m;
  if (_1 == _2)
    goto <bb 4>; [5.50%]
  else
    goto <bb 6>; [94.50%]

  <bb 4> [local count: 55807731]:
  g ();

  <bb 5> [local count: 114863530]:
  pretmp_11 = iter_6(D)->n;

  <bb 6> [local count: 1073741824]:
  # prephitmp_10 = PHI <pretmp_11(5), _1(3)>
  if (prephitmp_10 != 0)
    goto <bb 3>; [94.50%]
  else
    goto <bb 7>; [5.50%]

Aka the store still happens inside the loop unconditionally.

[Bug tree-optimization/37810] Bad store sinking job

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #2)
> The original testcase (from an IRC discussion) reduced to a C testcase is:
> 
> struct A {
>   int n;
>   int m;
> };
> 
> void g();
> 
> void test (struct A* iter)
> {
>   struct A end = { 0, 0 };
>   while (iter->n != end.n)
>     {
>       iter->n = iter->n + 1;
>       if (iter->n == iter->m)
>         g();
>     }
> }
> 
> where there is an optimization possibility to sink the store to iter->n to
> before the call and apply load-store motion to iter->n for the remaining
> loop.

So to clarify the desired code would look like

void test (struct A* iter)
{
  struct A end = { 0, 0 };
  int tem = iter->n;
  while (tem != end.n)
    {
      tem = tem + 1;
      if (tem == iter->m)
        {
          iter->n = tem;
          g();
          tem = iter->n;
        }
    }
  iter->n = tem;
}

PRE does half of the job, but then sinking would need to duplicate the store
on the loop exit, something it currently cannot do (the logic is to duplicate
to two places less frequently executed).

[Bug tree-optimization/37810] New: Bad store sinking job

[carlo at gcc dot gnu dot org]

The following code snippet:

void g();

struct A {
  int n;
  int m;

  A& operator++(void)
  {
    if (__builtin_expect(n == m, false))
      g();
    else
      ++n;
    return *this;
  }

  A() : n(0), m(0) { }

  friend bool operator!=(A const& a1, A const& a2) { return a1.n != a2.n; }
};

void testfunction(A& iter)
{
  A const end;
  while (iter != end)
    ++iter;
}

Results in the following assembly code, using maximum optimization:

        movl    (%rdi), %eax
        jmp     .L6

.L4:
        cmpl    %eax, 4(%rdi)     // n == m ?
        je      .L8               // unlikely jump
        addl    $1, %eax          // ++n
        movl    %eax, (%rdi)      // *** store result to memory ***
.L6:
        testl   %eax, %eax        // iter != end ?
        jne     .L4               // continue while loop


The storing (back) of %eax to (%rdi) remains inside the inner
loop no matter what I try. It could/should be moved outside
the loop, since nothing inside the L4 loop is accessing (%rdi)
or could possibly be accessing that memory.

This loop has two exits: below the last jne .L4, and the
jump to .L8. The store could be sinked to both exits.
This grows the code, but it seems reasonable to do for
a loop with a very small body, especially if one of the
exits is marked as unlikely :p.


-- 
           Summary: Bad store sinking job
           Product: gcc
           Version: 4.4.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: carlo at gcc dot gnu dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37810

[Bug tree-optimization/37810] Bad store sinking job

[rguenth at gcc dot gnu dot org]

------- Comment #1 from rguenth at gcc dot gnu dot org  2008-10-12 15:20 -------
store-sinking doesn't do its job because it thinks that

Memory reference 0: iter_1(D)->n
Memory reference 1: iter_1(D)->m
...
Querying dependencies of ref 0 in loop 1: dependent


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu dot
                   |                            |org
           Severity|normal                      |enhancement
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
           Keywords|                            |missed-optimization
   Last reconfirmed|0000-00-00 00:00:00         |2008-10-12 15:20:19
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37810

[Bug tree-optimization/37810] Bad store sinking job

[rguenth at gcc dot gnu dot org]

------- Comment #2 from rguenth at gcc dot gnu dot org  2008-10-12 15:25 -------
The original testcase (from an IRC discussion) reduced to a C testcase is:

struct A {
  int n;
  int m;
};

void g();

void test (struct A* iter)
{
  struct A end = { 0, 0 };
  while (iter->n != end.n)
    {
      iter->n = iter->n + 1;
      if (iter->n == iter->m)
        g();
    }
}

where there is an optimization possibility to sink the store to iter->n to
before the call and apply load-store motion to iter->n for the remaining loop.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |alias


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37810

[Bug tree-optimization/37810] Bad store sinking job

[rguenth at gcc dot gnu dot org]

------- Comment #3 from rguenth at gcc dot gnu dot org  2008-10-12 15:29 -------
It looks like the testcase in comment #2 should be fixed by SSUPRE?  We have

  *p = ...;
  if ()
    foo();

where foo() is an "implicit" store to *p.  Still store sinking should be
applied
to the subloop.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dberlin at gcc dot gnu dot
                   |                            |org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37810

[Bug tree-optimization/37810] Bad store sinking job

[carlo at gcc dot gnu dot org]

------- Comment #4 from carlo at gcc dot gnu dot org  2008-10-12 15:32 -------
Note that the original code was:

  A& operator++(void)
  {
    ++n;
    if (__builtin_expect(n == m, false))
      g();
    return *this;
  }

but g++ fails to optimize that by decrementing m outside
the loop (so I'm decrementing m myself now and use the
former code). The former code has as advantage, namely,
that the result of the addl $1,%eax can be used for the
conditional jump. However, gcc ALSO doesn't do that: in
the above assembly it follows the add with a redundant
testl %eax,%eax.

Anyway, using the operator++ given in this comment,
the assembly code is:

        movl    (%rdi), %eax
        jmp     .L3

.L4:
        addl    $1, %eax
        cmpl    4(%rdi), %eax
        movl    %eax, (%rdi)
        je      .L8
.L3:
        testl   %eax, %eax
        jne     .L4

which is essentially the same, except now the
testl %eax,%eax is indeed "needed" ...


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37810

[Bug tree-optimization/37810] Bad store sinking job

[rguenth at gcc dot gnu dot org]

------- Comment #5 from rguenth at gcc dot gnu dot org  2009-04-03 12:34 -------
Re-confirmed.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2008-10-12 15:20:19         |2009-04-03 12:34:44
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37810