[Bug tree-optimization/104547] New: std::vector::resize(v.size() - n) produces poor code

[Bug tree-optimization/104547] New: std::vector::resize(v.size() - n) produces poor code

[redi at gcc dot gnu.org]

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

            Bug ID: 104547
           Summary: std::vector::resize(v.size() - n) produces poor code
           Product: gcc
           Version: 11.2.1
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: redi at gcc dot gnu.org
  Target Milestone: ---

The codegen for this is pretty bad:

#include <vector>

void shrink(std::vector<int>& v, unsigned n) {
    v.resize(v.size() - n);
}

_Z6shrinkRSt6vectorIiSaIiEEj:
.LFB865:
        .cfi_startproc
        movq    8(%rdi), %rdx
        movq    (%rdi), %rcx
        movl    %esi, %esi
        movq    %rdx, %rax
        subq    %rcx, %rax
        sarq    $2, %rax
        movq    %rax, %r8
        subq    %rsi, %r8
        jb      .L3
        cmpq    %rax, %r8
        jnb     .L1
        leaq    (%rcx,%r8,4), %rax
        cmpq    %rax, %rdx
        je      .L1
        movq    %rax, 8(%rdi)
.L1:
        ret
.L3:
        pushq   %rax
        .cfi_def_cfa_offset 16
        movl    $.LC0, %edi
        call    _ZSt20__throw_length_errorPKc
        .cfi_endproc



Telling the compiler that v.size() - n doesn't wrap doesn't help at all:

#include <vector>

void shrink(std::vector<int>& v, unsigned n) {
    if (v.size() < n)
      __builtin_unreachable();
    v.resize(v.size() - n);
}

Why do we still have the call to __throw_length_error() there? It's
unreachable, because we're only shrinking, not growing.


This is better:

void shrink_pop(std::vector<int>& v, unsigned n) {
    while (n--)
      v.pop_back();
}

_Z10shrink_popRSt6vectorIiSaIiEEj:
.LFB866:
        .cfi_startproc
        testl   %esi, %esi
        je      .L10
        movq    8(%rdi), %rax
        movl    %esi, %esi
        negq    %rsi
        leaq    (%rax,%rsi,4), %rdx
        .p2align 4,,10
        .p2align 3
.L12:
        subq    $4, %rax
        movq    %rax, 8(%rdi)
        cmpq    %rax, %rdx
        jne     .L12
.L10:
        ret
        .cfi_endproc


And this:

void shrink_min(std::vector<int>& v, unsigned n) {
    v.resize(std::min<std::size_t>(v.size(), n));
}

_Z10shrink_minRSt6vectorIiSaIiEEj:
.LFB867:
        .cfi_startproc
        movq    8(%rdi), %rdx
        movq    (%rdi), %rcx
        movl    %esi, %esi
        movq    %rdx, %rax
        subq    %rcx, %rax
        sarq    $2, %rax
        cmpq    %rax, %rsi
        jb      .L54
.L52:
        ret
        .p2align 4,,10
        .p2align 3
.L54:
        leaq    (%rcx,%rsi,4), %rax
        cmpq    %rax, %rdx
        je      .L52
        movq    %rax, 8(%rdi)
        ret
        .cfi_endproc

[Bug tree-optimization/104547] std::vector::resize(v.size() - n) produces poor code

[redi at gcc dot gnu.org]

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

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
If we have two versions of the function in the same TU:

#include <vector>

void shrink(std::vector<int>& v, unsigned n) {
    v.resize(v.size() - n);
}

void shrink_min(std::vector<int>& v, unsigned n) {
    v.resize(std::min<std::size_t>(v.size(), n));
}

Then the .s file contains an instantiation of vector::_M_default_append even
though neither of the functions calls it. Why isn't that eliminated as dead
code? We shouldn't need to keep an implicit instantiation of a non-inline
function template if it's not called.

[Bug tree-optimization/104547] std::vector::resize(v.size() - n) produces poor code

[redi at gcc dot gnu.org]

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

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
If I change the type of n to match the type of v.size() the code size explodes:

#include <vector>

void shrink_assume(std::vector<int>& v, std::size_t n) {
    if (v.size() < n)
      __builtin_unreachable();
    v.resize(v.size() - n);
}


This adds 141 lines to the .s compared to the same function with unsigned n.

[Bug tree-optimization/104547] std::vector::resize(v.size() - n) produces poor code

[redi at gcc dot gnu.org]

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

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
For this TU with three functions, clang generates good code:


#include <vector>

void shrink_pop(std::vector<int>& v, std::size_t n) {
    while (n--)
      v.pop_back();
}

void shrink_assume(std::vector<int>& v, std::size_t n) {
    if (v.size() < n)
      __builtin_unreachable();
    v.resize(v.size() - n);
}

void shrink_min(std::vector<int>& v, std::size_t n) {
    v.resize(std::min<std::size_t>(v.size(), n));
}


Clang removes the unreachable __throw_length_error, doesn't explode if the type
is size_t, and doesn't keep the unused _M_default_append instantiation.

[Bug tree-optimization/104547] std::vector::resize(v.size() - n) produces poor code

[redi at gcc dot gnu.org]

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

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #0)
> This is better:
> 
> void shrink_pop(std::vector<int>& v, unsigned n) {
>     while (n--)
>       v.pop_back();
> }
> 
> _Z10shrink_popRSt6vectorIiSaIiEEj:
> .LFB866:
>         .cfi_startproc
>         testl   %esi, %esi
>         je      .L10
>         movq    8(%rdi), %rax
>         movl    %esi, %esi
>         negq    %rsi
>         leaq    (%rax,%rsi,4), %rdx
>         .p2align 4,,10
>         .p2align 3
> .L12:
>         subq    $4, %rax
>         movq    %rax, 8(%rdi)
>         cmpq    %rax, %rdx
>         jne     .L12
> .L10:
>         ret
>         .cfi_endproc

This should be A LOT better, but see PR 96717 comment 6 and 7. It's still
better than the resize(v.size() - n) code even with that regression.

Clang's code for shrink_pop is:

_Z10shrink_popRSt6vectorIiSaIiEEm:      # @_Z10shrink_popRSt6vectorIiSaIiEEm
        .cfi_startproc
# %bb.0:
        testq   %rsi, %rsi
        je      .LBB0_2
# %bb.1:
        shlq    $2, %rsi
        subq    %rsi, 8(%rdi)
.LBB0_2:
        retq

I was expecting something like that for v.resize(v.size() - n) too.

[Bug tree-optimization/104547] std::vector::resize(v.size() - n) produces poor code

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2022-02-15
                 CC|                            |aldyh at gcc dot gnu.org,
                   |                            |amacleod at redhat dot com,
                   |                            |jakub at gcc dot gnu.org
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
If you mean with -O3 on the
#include <vector>

void shrink(std::vector<int>& v, unsigned n) {
    if (v.size() < n)
      __builtin_unreachable();
    v.resize(v.size() - n);
}
testcase (with -O2 _M_default_append isn't nlined), then I think it is
something that ideally ranger's symbolic handling should figure out but
doesn't.
We have:
  long unsigned int _1;
...
  long unsigned int _11;
...
  if (_1 > _11)
    goto <bb 3>; [0.00%]
  else
    goto <bb 4>; [100.00%]

  <bb 3> [count: 0]:
  __builtin_unreachable ();

  <bb 4> [local count: 1073741824]:
  # RANGE ~[2305843009213693952, 16140901060200890368]
  _2 = _11 - _1;
  if (_2 > _11)
and we don't figure out that _2 > _11 is always false, because we earlier
assert that _1 <= _11 and so _11 - _1 will not wrap around and so the result _2
<= _11.

[Bug tree-optimization/104547] std::vector::resize(v.size() - n) produces poor code

[redi at gcc dot gnu.org]

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

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #5)
> If you mean with -O3 

Yes, sorry for not saying so: all examples were compiled with -O3.

[Bug tree-optimization/104547] std::vector::resize(v.size() - n) produces poor code

[amacleod at redhat dot com]

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

--- Comment #7 from Andrew Macleod <amacleod at redhat dot com> ---
Created attachment 52447
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52447&action=edit
proposed patch

(In reply to Jakub Jelinek from comment #5)
> If you mean with -O3 on the
> #include <vector>
> 
> void shrink(std::vector<int>& v, unsigned n) {
>     if (v.size() < n)
>       __builtin_unreachable();
>     v.resize(v.size() - n);
> }
> testcase (with -O2 _M_default_append isn't nlined), then I think it is
> something that ideally ranger's symbolic handling should figure out but
> doesn't.
> We have:
>   long unsigned int _1;
> ...
>   long unsigned int _11;
> ...
>   if (_1 > _11)
>     goto <bb 3>; [0.00%]
>   else
>     goto <bb 4>; [100.00%]
>   
>   <bb 3> [count: 0]:
>   __builtin_unreachable ();
>   
>   <bb 4> [local count: 1073741824]:
>   # RANGE ~[2305843009213693952, 16140901060200890368]
>   _2 = _11 - _1;
>   if (_2 > _11)
> and we don't figure out that _2 > _11 is always false, because we earlier
> assert that _1 <= _11 and so _11 - _1 will not wrap around and so the result
> _2 <= _11.

Relational : (_1 <= _11)
    <bb 4> [local count: 1073741824]:
    _2 = _11 - _1;
    if (_2 > _11)
      goto <bb 5>; [33.00%]
    else
      goto <bb 6>; [67.00%]

Looks like we know _1 is <= _11, but what seems to be missing is the extra
relation that _2 > _11 as a result.

normally we'd handle this by providing operator_minus::lhs_op1_relation()
routine, but unfortunately, it does not currently take a relation between op1
and op2 like the corresponding fold does.. it should be trivial to add it
however. 

The attached patch does the basics...  adds the parameter and provides a very
simple operator_minus::lhs_op1_relation () which then achieves the goal of the
PR. It hasn't been bootstrapped or anything.

I didn't try to flush out anything else, or make any enhancements because I
don't trust myself at this late stage to get it right :-) Feel free to work
with it if you want.

ie, I don't even look at the ranges.. if op1 >= op2, we return LHS <= op1.  We
could also check if the range of op2 does not contain 0, then we could return
LSH < OP1.  There is probably some sign checking that could be done too. 

There is also  the routine fold uses (minus_op1_op2_relation_effect) which
could possibly be leveraged as well, but I don't want to delve into that

Note that this will affect all minus operations everywhere...  for instance,
this patch ends up enabling a much earlier threading pass to eliminate the
branch.. so it never makes it to VRP2.

I also didn't implement lhs_op2 relation.. again, I don't trust myself to get
it right.
So I can either package this up and submit it, or someone more trustworthy can
take it an run with it and add whatever tweaks you feel are safe.

[Bug tree-optimization/104547] std::vector::resize(v.size() - n) produces poor code

[redi at gcc dot gnu.org]

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

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Thanks for looking at it! There's no urgency here from my point of view, I just
wanted to get it into bugzilla so I could concentrate on other things. Parking
this until stage1 makes sense.

[Bug tree-optimization/104547] std::vector::resize(v.size() - n) produces poor code

[cvs-commit at gcc dot gnu.org]

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

--- Comment #9 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Andrew Macleod <amacleod@gcc.gnu.org>:

https://gcc.gnu.org/g:cf2141a0c640fc9b1c497db3f4d5b270f4b8252a

commit r13-438-gcf2141a0c640fc9b1c497db3f4d5b270f4b8252a
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Tue Feb 15 10:17:26 2022 -0500

    Add relation between op1 & op2 to lhs_opN_relation API.

    We use the relation between op1 and op2 to help fold a statement, but
    it was not provided to the lhs_op1_relation and lhs_op2_relation routines
    to determine if is also creates a relation between the LHS and either
operand.

            gcc/
            PR tree-optimization/104547
            * gimple-range-fold.cc (fold_using_range::range_of_range_op): Add
            the op1/op2 relation to the relation call.
            * range-op.cc (*::lhs_op1_relation): Add param.
            (*::lhs_op2_relation): Ditto.
            (operator_minus::lhs_op1_relation): New.
            (range_relational_tests): Add relation param.
            * range-op.h (lhs_op1_relation, lhs_op2_relation): Adjust
prototype.

            gcc/testsuite/
            * g++.dg/pr104547.C: New.

[Bug tree-optimization/104547] std::vector::resize(v.size() - n) produces poor code

[amacleod at redhat dot com]

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

Andrew Macleod <amacleod at redhat dot com> changed:

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

--- Comment #10 from Andrew Macleod <amacleod at redhat dot com> ---
fixed.

[Bug tree-optimization/104547] std::vector::resize(v.size() - n) produces poor code

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |13.0