[m-dev.] Mutually recursive tailcalls in hlc.

[Paul Bone]

On Tue, Nov 10, 2015 at 12:13:41PM +1100, Julien Fischer wrote:
> On Tue, 10 Nov 2015, Paul Bone wrote:
> 
> >>I was asking about a conditional case, not the general case. You're
> >>right that I should ask about more than just gcc, though.
> >>
> >>Let me try again with a specific condition. Can the compilers we want
> >>perform tail call elimination if the signatures of the caller and
> >>callee are the same? Your argument transformation satisfies this
> >>condition, and the optimizations you mentioned are also relevant, but
> >>the actual trampoline would be redundant and may impede other C
> >>optimizations (such as inlining).
> >>
> >>Like I said earlier, it's not that I disagree with your proposal. But
> >>if someone asks, I'd like to be able to name a compiler we rely on
> >>that doesn't do tail call elimination under this condition.
> >
> >You're right, it may not be worth my/YesLogic's time to implement the
> >general solution.
> >
> >I'm not sure.  AFAIK the popular C compilers for use with Mercury are GCC,
> >Clang and VC++.
> 
> From time-to-time we have to (and should be able to) support new C
> compilers.  (It wasn't so long since clang was one such new compiler.)
> Furthormore, one of the points of the high-level C backend is that any
> C compiler that handles standard C (and isn't broken in one of many
> stupid ways) ought to be usable with it.

Agreed.  At least this change won't prevent your program from being compiled
if the C compiler's behaviour changes.  However it still depends on the C
compiler's behaviour, if the behaviour changes the optimisation may break
silently, causing a performance regression.

Worse still, if programmers come to depend on this optimisation and it
breaks, their programs are more-likely to segfault because they expected it
to work.  I don't know if anyone has noticed (I haven't) if this happens to
people when they port from low-level C to high-level C.

Depending on this behaviour, with Mark's proposal, also means _not_ applying
the general optimisation, so falling-back to the general optimisation will
not happen automatically.  This does happen automatically when using
inlining to avoid mutually recursive tailcalls.

I feel ambivalent about it.  My main concern is that it depends on the
behaviour of C compilers.

> >We could check Clang, it'll be documented somewhere.
> 
> You'll probably need to dig into the clang / LLVM source code for that,
> the user documentation is singularly useless on the subject.  (Ditto for
> GCC's for that matter.)
> 
> Taking the standard example of mutual recursion:
> 
>     bool is_even(int n)
>     {
>         if (n == 0) {
>            return true;
>         } else {
>            return is_odd(n - 1);
>        }
>     }
> 
>     bool is_odd(int n)
>     {
>         if (n == 0) {
>            return false;
>        } else {
>           return is_even(n - 1);
>        }
>     }
> 
> On my system if inlining is disabled, then GCC (4.3) eliminates the tail
> calls in the above, clang (Apple version 6) doesn't.  (If inlining is
> enabled, then one of the above functions is inlined in the body of the
> other and there are no indirect tail calls.)
> 
> >I'm not sure how we'd find out something like this for VC++.
> 
> I've had a look at the assembly that VC++ (2013) generates for the above
> (with inlining disabled) and the tail calls are eliminated.
> 

Okay, so that's:

    GCC: Yes
    Clang: No, XXX check the source
    VC++: Yes

Given Clang's popularity I would prefer not to rely on this.  However it'd
still be good to support it, as it ought to be faster.


-- 
Paul Bone