[Bug c++/64410] gcc 25% slower than clang 3.5 for adding complex numbers

[Bug c++/64410] gcc 25% slower than clang 3.5 for adding complex numbers

[glisse at gcc dot gnu.org]

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

--- Comment #1 from Marc Glisse <glisse at gcc dot gnu.org> ---
There are a number of things that make it complicated.
1) gcc doesn't like to vectorize when the number of iterations is not known at
compile time.
2) gcc doesn't vectorize anything already involving complex or vector
operations.
3) the ABI for complex uses 2 separate double instead of a vector of 2 double.

I believe there are dups at least for 2).

[Bug c++/64410] gcc 25% slower than clang 3.5 for adding complex numbers

[conradsand.arma at gmail dot com]

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

--- Comment #2 from Conrad <conradsand.arma at gmail dot com> ---
(In reply to Marc Glisse from comment #1)
> 3) the ABI for complex uses 2 separate double instead of a vector of 2
> double.

Technically yes, but in practice aren't the 2 separate doubles guaranteed to be
consecutive in memory?

[Bug c++/64410] gcc 25% slower than clang 3.5 for adding complex numbers

[glisse at gcc dot gnu.org]

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

--- Comment #3 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Conrad from comment #2)
> (In reply to Marc Glisse from comment #1)
> > 3) the ABI for complex uses 2 separate double instead of a vector of 2
> > double.
> 
> Technically yes, but in practice aren't the 2 separate doubles guaranteed to
> be consecutive in memory?

When the complex is in memory, yes. But passing a complex by value to a
function is done with 2 separate registers. And somehow that means the default
expansion for complex addition is 2 addsd, whereas the default expansion for
vector addition is addpd. Using addpd by default for complex would make some
code better (this example would hopefully be optimal without need for any
optimization) and some worse, I don't know if there are good benchmarks for
complex numbers.

Clang's use of add[ps]d seems based entirely on what is done with the result,
as can be seen on:

typedef _Complex double cd;
void f(cd&r,cd x,cd y){
  r=x+y;
}
cd f(cd&x,cd&y,cd&z){
  return x+y+z;
}

(I agree that gcc should be improved, I am not trying to defend the current
code generation. And now I'll shut up and let people who actually know the code
speak ;-)

[Bug c++/64410] gcc 25% slower than clang 3.5 for adding complex numbers

[dje at gcc dot gnu.org]

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

David Edelsohn <dje at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-12-28
     Ever confirmed|0                           |1

--- Comment #4 from David Edelsohn <dje at gcc dot gnu.org> ---
Confirmed.

[Bug c++/64410] gcc 25% slower than clang 3.5 for adding complex numbers

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Marc Glisse from comment #1)
> There are a number of things that make it complicated.
> 1) gcc doesn't like to vectorize when the number of iterations is not known
> at compile time.

Not an issue, we know it here (it's symbolic)

> 2) gcc doesn't vectorize anything already involving complex or vector
> operations.

Indeed - here the issue is that we have C++ 'complex' aggregate
load / store operations:

  _67 = MEM[(const struct complex &)_75];
  __r$_M_value = _67;
...
  _51 = REALPART_EXPR <__r$_M_value>;
  REALPART_EXPR <__r$_M_value> = _104;
...
  IMAGPART_EXPR <__r$_M_value> = _107;
  _108 = __r$_M_value;
  MEM[(struct cx_double *)_72] = _108;

which SRA for some reason didn't decompose as they are not aggregate
(well, they are COMPLEX_TYPE).  They are not in SSA form either because
they are partly written to.  In this case it would have been profitable
to SRA __r$_M_value.  Eventually this should have been complex lowerings
job (but it doesn't try to decompose complex assignments).

> 3) the ABI for complex uses 2 separate double instead of a vector of 2
> double.

I think that's unrelated.

> I believe there are dups at least for 2).

[Bug c++/64410] gcc 25% slower than clang 3.5 for adding complex numbers

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
             Status|NEW                         |ASSIGNED
             Blocks|                            |53947
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #5)
> (In reply to Marc Glisse from comment #1)
> > There are a number of things that make it complicated.
> > 1) gcc doesn't like to vectorize when the number of iterations is not known
> > at compile time.
> 
> Not an issue, we know it here (it's symbolic)
> 
> > 2) gcc doesn't vectorize anything already involving complex or vector
> > operations.
> 
> Indeed - here the issue is that we have C++ 'complex' aggregate
> load / store operations:
> 
>   _67 = MEM[(const struct complex &)_75];
>   __r$_M_value = _67;
> ...
>   _51 = REALPART_EXPR <__r$_M_value>;
>   REALPART_EXPR <__r$_M_value> = _104;
> ...
>   IMAGPART_EXPR <__r$_M_value> = _107;
>   _108 = __r$_M_value;
>   MEM[(struct cx_double *)_72] = _108;
> 
> which SRA for some reason didn't decompose as they are not aggregate
> (well, they are COMPLEX_TYPE).  They are not in SSA form either because
> they are partly written to.

And this forces it to be TREE_ADDRESSABLE.  Which means update-address-taken
might be a better candidate to fix this.

Note that it will still run into the issue that the vectorizer does not
like complex types (in loads), nor does it like building complex
registers via COMPLEX_EXPR.  After fixing update-address-taken we have

  __r$_M_value_70 = MEM[(const struct complex &)_78];
  _66 = MEM[(const double &)_77];
  _54 = REALPART_EXPR <__r$_M_value_70>;
  _105 = _54 + _66;
  _135 = IMAGPART_EXPR <__r$_M_value_70>;
  _106 = MEM[(const double &)_77 + 8];
  _107 = _106 + _135;
  __r$_M_value_180 = COMPLEX_EXPR <_105, _107>;
  MEM[(struct cx_double *)_76] = __r$_M_value_180;

which we ideally would have converted to piecewise loading / storing,
but the vectorizer may also be able to recover here with some twists.

> In this case it would have been profitable
> to SRA __r$_M_value.  Eventually this should have been complex lowerings
> job (but it doesn't try to decompose complex assignments).
> 
> > 3) the ABI for complex uses 2 separate double instead of a vector of 2
> > double.
> 
> I think that's unrelated.
> 
> > I believe there are dups at least for 2).

[Bug c++/64410] gcc 25% slower than clang 3.5 for adding complex numbers

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 34400
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=34400&action=edit
update-address-taken fix

[Bug c++/64410] gcc 25% slower than clang 3.5 for adding complex numbers

[glisse at gcc dot gnu.org]

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

--- Comment #8 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #5)
> (In reply to Marc Glisse from comment #1)
> > There are a number of things that make it complicated.
> > 1) gcc doesn't like to vectorize when the number of iterations is not known
> > at compile time.
> 
> Not an issue, we know it here (it's symbolic)

IIRC I tried modifying the original code by replacing all complex operations by
explicit scalar operations and it failed to vectorize, but worked when
replacing the number of iterations by a constant.

> > 3) the ABI for complex uses 2 separate double instead of a vector of 2
> > double.
> 
> I think that's unrelated.

Indeed, it's just that with a different ABI we could have been lucky and
stumbled upon the optimal code, almost by accident.

[Bug c++/64410] gcc 25% slower than clang 3.5 for adding complex numbers

[rguenth at gcc dot gnu.org]

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

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 34402
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=34402&action=edit
patch to pattern-detect the load/store

This pattern matches real/imagpart uses and single-use complex stores and
transforms them to component-wise accesses in forwprop.  Together we vectorize
the loop now and produce:

.L28:
        movupd  (%rbx,%rax), %xmm1
        movupd  (%r15,%rax), %xmm0
        addpd   %xmm1, %xmm0
        movups  %xmm0, 0(%r13,%rax)
        addq    $16, %rax
        cmpq    %rax, %rdx
        jne     .L28

note that we need a runtime alias check to disambiguate things (because
std::vector memory cannot be disambiguated statically) and similarly we
cannot prove sufficent alignment to use aligned loads/stores.

[Bug c++/64410] gcc 25% slower than clang 3.5 for adding complex numbers

[rguenth at gcc dot gnu.org]

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

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
Improves runtime from 8.3s to 6.5s (~25%).

[Bug tree-optimization/64410] gcc 25% slower than clang 3.5 for adding complex numbers

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
      Known to work|                            |5.0
         Resolution|---                         |FIXED

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed in GCC 5.

[Bug tree-optimization/64410] gcc 25% slower than clang 3.5 for adding complex numbers

[rguenth at gcc dot gnu.org]

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

--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Fri Jan  9 11:14:55 2015
New Revision: 219380

URL: https://gcc.gnu.org/viewcvs?rev=219380&root=gcc&view=rev
Log:
2015-01-09  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/64410
    * tree-ssa.c (non_rewritable_lvalue_p): Allow REALPART/IMAGPART_EXPR
    on the LHS.
    (execute_update_addresses_taken): Deal with that.
    * tree-ssa-forwprop.c (pass_forwprop::execute): Use component-wise
    loads/stores for complex variables.

    * g++.dg/vect/pr64410.cc: New testcase.

Added:
    trunk/gcc/testsuite/g++.dg/vect/pr64410.cc
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-forwprop.c
    trunk/gcc/tree-ssa.c

[Bug tree-optimization/64410] gcc 25% slower than clang 3.5 for adding complex numbers

[ro at gcc dot gnu.org]

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

Rainer Orth <ro at gcc dot gnu.org> changed:

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

--- Comment #13 from Rainer Orth <ro at gcc dot gnu.org> ---
The new testcase FAILs on Solaris/SPARC (both 32 and 64-bit):

FAIL: g++.dg/vect/pr64410.cc  -std=c++11  scan-tree-dump vect "vectorized 1
loops in function"
FAIL: g++.dg/vect/pr64410.cc  -std=c++14  scan-tree-dump vect "vectorized 1
loops in function"
FAIL: g++.dg/vect/pr64410.cc  -std=c++98  scan-tree-dump vect "vectorized 1
loops in function"

I'm attaching the .vect dump.

  Rainer

[Bug tree-optimization/64410] gcc 25% slower than clang 3.5 for adding complex numbers

[ro at gcc dot gnu.org]

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

--- Comment #14 from Rainer Orth <ro at gcc dot gnu.org> ---
Created attachment 34496
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=34496&action=edit
sparc-sun-solaris2.11 .vect dump

[Bug tree-optimization/64410] gcc 25% slower than clang 3.5 for adding complex numbers

[rguenth at gcc dot gnu.org]

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

--- Comment #15 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Tue Jan 20 11:06:13 2015
New Revision: 219885

URL: https://gcc.gnu.org/viewcvs?rev=219885&root=gcc&view=rev
Log:
2015-01-20  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/64410
    * g++.dg/vect/pr64410.cc: Require vect_double.

Modified:
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/g++.dg/vect/pr64410.cc

[Bug tree-optimization/64410] gcc 25% slower than clang 3.5 for adding complex numbers

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |5.0