[Bug tree-optimization/58483] New: missing optimization opportunity for const std::vector compared to std::array

[Bug tree-optimization/58483] New: missing optimization opportunity for const std::vector compared to std::array

[dl.soluz at gmx dot net]

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

            Bug ID: 58483
           Summary: missing optimization opportunity for const std::vector
                    compared to std::array
           Product: gcc
           Version: 4.8.1
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: dl.soluz at gmx dot net

this small testprogram shows a missing optimization opportunity for const
std::vector when using initialization_list - in compared to std::array

#include <vector>
#include <numeric>
#include <array>

static int calc(const std::array<int,3> p_ints, const int& p_init)
//static int calc(const std::vector<int> p_ints, const int& p_init)
{
  return std::accumulate(p_ints.begin(), p_ints.end(), p_init);
}

int main()
{
  const int result = calc({10,20,30},100);
  return result;
}

optimizer-result using std::array

int main() ()
{
  <bb 2>:
  return 160;
}

the result using std::vector

int main() ()
{
  int __init;
  int _2;
  int _11;
  int _32;
  int * _33;

  <bb 2>:
  _33 = operator new (12);
  __builtin_memcpy (_33, &._79, 12);
  _32 = MEM[(const int &)_33];
  __init_28 = _32 + 100;
  _2 = MEM[(const int &)_33 + 4];
  __init_18 = _2 + __init_28;
  _11 = MEM[(const int &)_33 + 8];
  __init_13 = _11 + __init_18;
  if (_33 != 0B)
    goto <bb 3>;
  else
    goto <bb 4>;

  <bb 3>:
  operator delete (_33);

  <bb 4>:
  return __init_13;
}

according to Marc Gliss's answer in
(http://gcc.gnu.org/ml/gcc/2013-09/msg00179.html)

"...
We don't perform such high-level optimizations. But if you expand, inline and
simplify this program, the optimizers sees something like:

p=operator new(12);
memcpy(p,M,12); // M contains {10, 20, 30}
res=100+p[0]+p[1]+p[2];
if(p!=0) operator delete(p);

A few things that go wrong:
* because p is filled with memcpy and not with regular assignments,
the compiler doesn't realize that p[0] is known. 

* the test p != 0 is unnecessary (a patch that should help is pending review) *
we would then be left with: 

p=new(12); delete p; return 160; 

gcc knows how to remove free(malloc(12)) but not the C++ variant (I don't even
know if it is legal, or what conditions and flags are required to make it so).
..."

the pending patch is http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19476

but the question is still can new(delete(12)) also removed like
free(malloc(12)) in this scenario?

[Bug tree-optimization/58483] missing optimization opportunity for const std::vector compared to std::array

[glisse at gcc dot gnu.org]

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

Marc Glisse <glisse at gcc dot gnu.org> changed:

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

--- Comment #1 from Marc Glisse <glisse at gcc dot gnu.org> ---
Note that FRE already knows how to look through a memcpy, on trivial examples,
but here I assume the FRE pass is too early.

Also related: PR 58480 (an alternate way to remove the !=0 test).

[Bug tree-optimization/58483] missing optimization opportunity for const std::vector compared to std::array

[dl.soluz at gmx dot net]

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

--- Comment #2 from dennis luehring <dl.soluz at gmx dot net> ---
i missed the commandline

g++-4.8 -O3 -march=native -std=c++11 -fdump-tree-optimized test.cpp

[Bug tree-optimization/58483] missing optimization opportunity for const std::vector compared to std::array

[dl.soluz at gmx dot net]

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

--- Comment #3 from dennis luehring <dl.soluz at gmx dot net> ---
according to the feedback from the clang mailing list by Benjamin Kramer

http://lists.cs.uiuc.edu/pipermail/cfe-dev/2013-September/032111.html

llvm seems to not have any problem in removing new/delete in this situation but
got still a bug in not understanding that there is no need for the values to be
on the heap - if i get it correct :)

[Bug tree-optimization/58483] missing optimization opportunity for const std::vector compared to std::array

[dl.soluz at gmx dot net]

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

--- Comment #4 from dennis luehring <dl.soluz at gmx dot net> ---
rechecked with latest clang 3.3(3.4) on http://gcc.godbolt.org/

reduces both cases std::array and std::vector down to

return 160

[Bug tree-optimization/58483] missing optimization opportunity for const std::vector compared to std::array

[dl.soluz at gmx dot net]

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

--- Comment #5 from dennis luehring <dl.soluz at gmx dot net> ---
but clang 3.3 produces only the optimized output when using -O2 (-O3 still
invokes the loop optimizer too early - but this is a known bug)

so it seems that the llvm/clang developers think that new/delete can be removed
the same way as malloc/free

[Bug tree-optimization/58483] missing optimization opportunity for const std::vector compared to std::array

[glisse at gcc dot gnu.org]

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

Bug 58483 depends on bug 19476, which changed state.

Bug 19476 Summary: Missed null checking elimination with new
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19476

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED

[Bug tree-optimization/58483] missing optimization opportunity for const std::vector compared to std::array

[glisse at gcc dot gnu.org]

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

Bug 58483 depends on bug 58480, which changed state.

Bug 58480 Summary: Use attribute((nonnull)) to optimize callers
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58480

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|---                         |FIXED

[Bug tree-optimization/58483] missing optimization opportunity for const std::vector compared to std::array

[glisse at gcc dot gnu.org]

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

Marc Glisse <glisse at gcc dot gnu.org> changed:

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

--- Comment #6 from Marc Glisse <glisse at gcc dot gnu.org> ---
With current trunk, for the vector version, the most obvious optimization
failure is the following:

  _57 = (unsigned long) &MEM[(void *)&._79 + 12B];
  _36 = (unsigned long) &MEM[(void *)&._79 + 4B];
  _51 = _57 - _36;
  _3 = _51 /[ex] 4;
  _26 = _3;
  _27 = _26 + 1;
  _31 = _27 * 4;
etc.

_51 should be folded to 8 (then we have the usual useless /4*4, but with a
constant it would be ok). This part is a 4.9/4.10 regression, gcc-4.8 managed
to get the constant 12:
  __builtin_memcpy (_33, &._80, 12);

[Bug tree-optimization/58483] missing optimization opportunity for const std::vector compared to std::array

[dl.soluz at gmx dot net]

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

--- Comment #7 from dennis luehring <dl.soluz at gmx dot net> ---
clang got now support for 

(see:
http://clang-developers.42468.n3.nabble.com/missing-optimization-opportunity-for-const-std-vector-compared-to-std-array-td4034587.html#none)

void *__builtin_operator_new(size_t)
void __builtin_operator_delete(void*)

and using this in libc++ can reduce all testcases down to the const result

gcc seems to have removed these long time ago and i currently do understand
whats gcc solution could be

[Bug tree-optimization/58483] missing optimization opportunity for const std::vector compared to std::array

[glisse at gcc dot gnu.org]

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

--- Comment #8 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to dennis luehring from comment #7)
[clang]
> void *__builtin_operator_new(size_t)
> void __builtin_operator_delete(void*)

I don't understand why N3664 is talking of new expressions instead of operator
new calls, it doesn't give any rationale for that choice, and we get duplicate
wording between the description of new expressions and
std::allocator::allocate. But at least it explains why they have these builtins
(which at first sight is strange since they don't have __builtin_malloc).

> gcc seems to have removed these long time ago and i currently do understand
> whats gcc solution could be

We may add a compilation flag that promises the user won't try to replace the
main operator new / operator delete. The compiler could then inline them
(either LTO or make an inlined version available), see malloc + free, and
hopefully simplify that.

We may also introduce those 2 builtins.

Anyway, the first priority is simplifying the rest until there are just the
calls to new+delete left. That's not currently the case.

[Bug tree-optimization/58483] missing optimization opportunity for const std::vector compared to std::array

[dl.soluz at gmx dot net]

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

--- Comment #16 from dennis luehring <dl.soluz at gmx dot net> ---
the sample still gets reduced by clang to 160 with -O2 or -O3

clang:

main:                                   # @main
        mov     eax, 160
        ret

and gcc 11.2/trunk producing

-O2
main:
        push    rbp
        mov     edi, 12
        sub     rsp, 48
        movq    xmm15, QWORD PTR .LC0[rip]
        mov     DWORD PTR [rsp+8], 30
        movq    QWORD PTR [rsp], xmm15
        pxor    xmm15, xmm15
        mov     QWORD PTR [rsp+32], 0
        movaps  XMMWORD PTR [rsp+16], xmm15
        call    operator new(unsigned long)
        mov     rcx, QWORD PTR [rsp]
        lea     rdx, [rax+12]
        lea     rdi, [rsp+16]
        mov     QWORD PTR [rsp+16], rax
        mov     QWORD PTR [rsp+32], rdx
        mov     QWORD PTR [rax], rcx
        mov     ecx, DWORD PTR [rsp+8]
        mov     QWORD PTR [rsp+24], rdx
        mov     DWORD PTR [rax+8], ecx
        call    std::_Vector_base<int, std::allocator<int> >::~_Vector_base()
[base object destructor]
        add     rsp, 48
        mov     eax, 160
        pop     rbp
        ret
        mov     rbp, rax
        jmp     .L5
main.cold:
.LC0:
        .long   10
        .long   20

-O3
main:
        sub     rsp, 24
        mov     edi, 12
        movq    xmm15, QWORD PTR .LC0[rip]
        mov     DWORD PTR [rsp+8], 30
        movq    QWORD PTR [rsp], xmm15
        call    operator new(unsigned long)
        mov     esi, 12
        mov     rdi, rax
        mov     rax, QWORD PTR [rsp]
        mov     QWORD PTR [rdi], rax
        mov     eax, DWORD PTR [rsp+8]
        mov     DWORD PTR [rdi+8], eax
        call    operator delete(void*, unsigned long)
        mov     eax, 160
        add     rsp, 24
        ret
.LC0:
        .long   10
        .long   20


does that mean its still not clear if the unused new/delete can be removed
here?

[Bug tree-optimization/58483] missing optimization opportunity for const std::vector compared to std::array

[pinskia at gcc dot gnu.org]

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

--- Comment #17 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Here is related reduced testcase:
```

int f(void)
{
        int tt = 100;
        int t[3] = {10,20,30};
        int *t1 = new int[3];
        __builtin_memcpy(t1, t, sizeof(t));
        for(int *i = t1; i != &t1[3]; i++)
          tt += *i;
        delete[] t1;
        return tt;
}
```
Note in the above testcase we can remove the memcpy but not the operator
new/delete.  This is unlike the original testcase where memcpy is not removed
either.