Marvin Sielenkemper wrote:
> I compiled this program (fact.bitc)
> --- snip ---
> (bitc-version "0.10")
> (import bitc.main as main)
> (provide bitc.main main)
>
> (define (factorial x:int32)
> (letrec
> ((fac (lambda (n r)
> (if (<= n 0) 1 (fac (- n 1) (* n r))))))
> (fac x 1)))
>
> (define main.main:(fn (vector string) -> int32)
> (lambda (argv)
> (factorial 10)
> 0))
> --- snip ---
> with
> bitcc --emit c fact.bitc
> and expected to see the tail call of 'fac' compiled to a 'goto'.
> But I found the following code for the 'if'-expression:
> --- snip ---
> if (__t11241) {
> __t11245 = 1;
> }
> else {
> __t11252 = _16bitc_DTprelude_DT___HY_SHFN2_5int32_5int32_5int32
> (_1n_SH_5int32_SH7462, 1);
> __t11256 = _16bitc_DTprelude_DT___ST_SHFN2_5int32_5int32_5int32
> (_1n_SH_5int32_SH7462, _1r_SH_5int32_SH7464);
> __t11260 = (* __clArg_SH9094->_3fac_SHFN2_5int32_5int32_5int32)(__t11252,
> __t11256);
> __t11245 = __t11260;
> }
> --- snip ---
> and __t11245 really is returned without further operations apart from
> copying.
> So 'fac' is in tail position but is called. And as far as i can see 12.2 of
> the spec v0.10+ applies here.
>
> Another bug?
Thanks for reporting the bug. This is actually a known issue in the
current closure conversion algorithm.
The tail call in this case should have been tail recursive. But what
happened is that the closure conversion algorithm thought that function
(lambda (n r)
(if (<= n 0) 1 (fac (- n 1) (* n r))))))
is closed over the symbol `fac' itself. Therefore, it built a closure
record for the function and replaced a direct call to fac with an
indirect call (*_clArg_SH9094->_3fac_SHFN2_5int32_5int32_5int32)(...),
which made the call non-tail recursive.
The closure conversion algorithm needs two fixes:
1) Recognize that immutable function bindings need not be considered
non-local within the letrec definition.
2) Convert multiple definitions within the same letrec to a single
definition (using a switch-like despatch) so that we can issue
gotos to implement tail recursion.
I will let you know once these fixes are implemented.
Swaroop.
_______________________________________________
bitc-dev mailing list
[email protected]
http://www.coyotos.org/mailman/listinfo/bitc-dev
