[Bug tree-optimization/63185] New: Improve DSE with branches

[Bug tree-optimization/63185] New: Improve DSE with branches

[glisse at gcc dot gnu.org]

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

            Bug ID: 63185
           Summary: Improve DSE with branches
           Product: gcc
           Version: 5.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: glisse at gcc dot gnu.org

#include <stdlib.h>
#include <string.h>
void g();
void f(int n){
  char*p=malloc(1024);
  memset(p,8,1024);
  if(n)g();
}

We do not manage to remove the dead store (memset) because there is a PHI that
doesn't post-dominate the statement.

[Bug tree-optimization/63185] Improve DSE with branches

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-09-05
     Ever confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Hm?  The PHI does post-dominate the memset.  I think you run into another
check,
namely we visited the call already (temp != NULL).

We don't special-case a non-diamond if (where there are never two possible
uses on different CFG paths).  That is, the walking over all uses is
somewhat stupid.

[Bug tree-optimization/63185] Improve DSE with branches

[glisse at gcc dot gnu.org]

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

--- Comment #2 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #1)
> Hm?  The PHI does post-dominate the memset.  I think you run into another
> check, namely we visited the call already (temp != NULL).

Oups... The original testcase was failing because a PHI didn't post-dominate,
and I wasn't very careful when reducing. Bah, the issue seems close enough...

[Bug tree-optimization/63185] Improve DSE with branches

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
Btw, what was the original testcase?

It's all a little bit complicated and not really fit for the current simple
handling of PHIs.  Because with a conditional store we have to continue
looking for uses on the other path (for regular stores we'd have expected
code sinking to sink the store).

That is, without making the walk very much more expensive there isn't anything
we can do about this.

[Bug tree-optimization/63185] Improve DSE with branches

[glisse at gcc dot gnu.org]

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

--- Comment #4 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #3)
> Btw, what was the original testcase?

Sorry, I don't remember. Probably something involving std::vector or
std::string. Since llvm optimizes it just fine, I hadn't realized it would be
so hard.

> That is, without making the walk very much more expensive there isn't
> anything we can do about this.

Ok, thanks for looking at it. Down to P5?

[Bug tree-optimization/63185] Improve DSE with branches

[glisse at gcc dot gnu.org]

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

--- Comment #5 from Marc Glisse <glisse at gcc dot gnu.org> ---
Another example:

#include <time.h>
void f(){
  const int n=1<<14;
  double a[n];
  double b[n];
  double c[n];
  __builtin_memset(a,0,n);
  __builtin_memset(b,0,n);
  __builtin_memset(c,0,n);
  for(int i=0;i<n;++i)
    c[i]=a[i]+b[i];
  time(0);
}

If I make n a constant (using #define), DCE knows that c is not
ref_may_be_aliased (that test could probably be weakened) and removes almost
everything. We don't replace alloca_with_align with an array because the size
is larger than 256 (with a more limited scope the limit would even be 25...).
DSE is likely confused by the loop. And PRE and others don't know that a[i] is
always 0. (llvm removes everything but the final call)

[Bug tree-optimization/63185] Improve DSE with branches

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |10.5.0, 13.2.1, 14.1.0
         Resolution|---                         |FIXED
             Status|NEW                         |RESOLVED
      Known to fail|                            |7.5.0

--- Comment #13 from Richard Biener <rguenth at gcc dot gnu.org> ---
The original testcase has the memset removed with GCC 10 already.