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

[Julien Fischer]

Hi,

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.

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

Julien.