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

[Julien Fischer]

Hi Paul,

On Tue, 10 Nov 2015, Paul Bone wrote:

>> 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.

It depends what you are trying to achieve.  If you want to make
guarantees about about tailcalls being eliminated in a specified class
of mutually recursive predicates then I think you will have to handle it
in the Mercury compiler.  Leaving it up to the C compiler is at the very
least sensitive to which optimization flags the C compiler is invoked
with and the Mercury implementation itself often varies flags those in
order to workaround bugs.  Furthermore, users have the option of setting
C compiler optimization flags hemselves (and indeed, may have to because
of the contents of foreign_proc pragmas.)

Incidentally, the trampolining technique ought to also work (with
appropriate modifications) with both the C# and Java backends.

>>> 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

It would be worth trying with a newer version of clang.  The version on
my machine appears to be a little old.  (3.5 as opposed to the latest
which is 3.8.)

I'd like to see what happens with a more realistic case than the above
though (i.e. with C code generated by the Mercury compiler for a non toy
program).

Julien.