[Bug c++/92559] Returning std∷map breaks tail-recursion optimization

[Bug c++/92559] Returning std∷map breaks tail-recursion optimization

[pinskia at gcc dot gnu.org]

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I don't think this can ever be optimized.  Mainly because there are copies
happening due to passing via value and returning by value.

If I change it to foo to MyMap &foo(MyMap &m), I get the behavior you want.

[Bug c++/92559] Returning std∷map breaks tail-recursion optimization

[Hi-Angel at yandex dot ru]

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

--- Comment #3 from Konstantin Kharlamov <Hi-Angel at yandex dot ru> ---
(In reply to Andrew Pinski from comment #2)
> I don't think this can ever be optimized.  Mainly because there are copies
> happening due to passing via value and returning by value.

Please correct me if I'm wrong, but it seems like, given the code in question:

    MyMap foo(MyMap m) {
        if (m[0] == 0)
            return m;
        else {
            m[0] -= 1;
            return foo(m);
        }
    }

When tail-recursion optimization applied, it should be analogous to this code:

    MyMap foo(MyMap m) {
        while(m[0] > 0) {
            m[0] -= 1;
            m = MyMap(m);
        }
        return m;
    }

Doesn't look impossible to me, unless of course I am missing something.

[Bug c++/92559] Returning std∷map breaks tail-recursion optimization

[Hi-Angel at yandex dot ru]

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

--- Comment #4 from Konstantin Kharlamov <Hi-Angel at yandex dot ru> ---
By the way, FTR: I don't have the code anymore, but initially the problem came
from a real-life algorithm involving lots of state, which looked barely
readable when implemented in iterative way (i.e. as opposed to "recursive",
that is when you use for/while-cycles instead of recursion). The iterative
version was 1.5 times bigger than the recursive one, and has a lot of
additional state-tracking variables; and I think it also has two cycles (as
compared to recursive version that has none at all).

Back then we decided that we want the readable code, because at the end of the
day, readable code is the reason people don't write assembly and rely on
compilers to optimize instead. Of course, we would have to add to CI some
checks to make sure the optimization was done as expected (tho I don't think it
was ever added, simply because since the optimization currently doesn't work,
there's nothing to check).

IIRC, this bug-report was a reduced problem of tail-recursion not working for
us. The state in the algorithm has std::map in particular I think.

[Bug c++/92559] Returning std∷map breaks tail-recursion optimization

[Hi-Angel at yandex dot ru]

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

--- Comment #5 from Konstantin Kharlamov <Hi-Angel at yandex dot ru> ---
(In reply to Konstantin Kharlamov from comment #4)
> By the way, FTR: I don't have the code anymore, but initially the problem
> came from a real-life algorithm involving lots of state, which looked barely
> readable when implemented in iterative way (i.e. as opposed to "recursive",
> that is when you use for/while-cycles instead of recursion). The iterative
> version was 1.5 times bigger than the recursive one, and has a lot of
> additional state-tracking variables; and I think it also has two cycles (as
> compared to recursive version that has none at all).

Oh, I just remember: the recursive version was also immutable, which also made
the code much easier to understand (and I was kinda hoping, easier for the
compiler to optimize as well). The iterative version involved lots of
mutations. They always do.