[Bug tree-optimization/64319] New: add alias runtime check to remove load after load redundancy

[Bug tree-optimization/64319] New: add alias runtime check to remove load after load redundancy

[spop at gcc dot gnu.org]

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

            Bug ID: 64319
           Summary: add alias runtime check to remove load after load
                    redundancy
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: spop at gcc dot gnu.org

Looking at the code generated at -O3 for the following function, we have to
load "*a" twice because "a" may alias "b":

$ cat foo.c
int foo(int *a, int *b)
{
  *a = 1;
  (*b)++;
  return *a;
}

Here is the code generated for aarch64 (for illustration only, ie., this is not
an aarch64 bug):

$ gcc foo.c -O3 -S -o -
[...]
foo:
 mov w2, 1
 str w2, [x0]
 ldr w2, [x1]
 add w2, w2, 1
 str w2, [x1]
 ldr w0, [x0]
 ret

GCC could insert a runtime check to disambiguate the two pointers: in
principle, we should obtain better code on both branches, because the compiler
knows something more about the program in each case.

$ cat bar.c
int bar(int *a, int *b)
{
  if (a == b)
    {
      *a = 1;
      (*b)++;
      return *a;
    }

  *a = 1;
  (*b)++;
  return *a;
}

GCC does optimize correctly the case "a==b" and still has an optimization
problem in the case "a!=b". Here is the code generated for aarch64:

bar:
 cmp    x0, x1
 beq    .L6
 mov    w2, 1
 str    w2, [x0]
 ldr    w2, [x1]
 add    w2, w2, 1
 str    w2, [x1]
 ldr    w0, [x0]  <-- this load should be replaced by a "mov w0, 1" 
                      because we know "x1 != x0" on this branch.
 ret
.L6:
 mov    w1, 2
 str    w1, [x0]
 mov    w0, w1
 ret

[Bug tree-optimization/64319] add alias runtime check to remove load after load redundancy

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |alias, missed-optimization
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-12-16
     Ever confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
The interesting problem to solve is of course which disabiguation checks to
insert
(and where).  And whether there is really a net positive effect in runtime
(surley not code-size).  Probably making this a value-profiling would make
sense?

As for the missed optimization with the conditonal code here the issue is that
points-to information is not flow-sensitive (or rather only in sofar as SSA
defs are flow-sensitive).

  <bb 2>:
  if (a_3(D) == b_4(D))
    goto <bb 3>;
  else
    goto <bb 4>;
...
  <bb 4>:
  *a_3(D) = 1;
  _12 = *b_4(D);
  _13 = _12 + 1;
  *b_4(D) = _13;
  _15 = *a_3(D);

And of course our points-to code doesn't look at conditionals at all to
derive alias information (it couldn't associate it with SSA names later
anyway).  It would need to add explicit IL similar to VRP (but that does
it only temporarily), and it also would require to teach the solver of
a constraint that makes two pointers non-equal (not sure if doable at all).

For the a == b case we manage to copy-propagate
both to equal values in DOM and thus optimize the loads and later DSE the
redundant store.

We could use the recently added facility to record explicit non-dependences
which is also flow-sensitive (recorded on actual memory references) when
adding the alias check or from code (DOM?) that figures out non-equivalence.
[see MR_DEPENDENCE_CLIQE / MR_DEPENDENCE_BASE]

I see this as two bugs - one to generate runtime disambiguation code, possibly
directed by profiling, and one to actually make use of present runtime alias
checks.

Confirmed.

[Bug tree-optimization/64319] add alias runtime check to remove load after load redundancy

[b.grayson at samsung dot com]

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

--- Comment #2 from Brian Grayson <b.grayson at samsung dot com> ---
alignd() in m88ksim from SPECint95 is a poster child for this kind of
optimization -- it receives several pointers to portions of FP representations,
and then operates on them via code like this:

...
*amantlo >>= 1;
*amantlo |= *amanthi << 31;
*amanthi >>= 1;
...

In this case, there may actually be a code-space reduction(!) with dynamic
disambiguation, because gcc has to insert so many redundant loads and stores in
the general case that are not needed in either of the two forks.

That may make a handy stand-alone real-world testcase.

[Bug tree-optimization/64319] add alias runtime check to remove load after load redundancy

[pinskia at gcc dot gnu.org]

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

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

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