limit check insertion
Matthew Fluet
Matthew Fluet <fluet@CS.Cornell.EDU>
Mon, 22 Oct 2001 20:22:32 -0400 (EDT)
> Isn't hoisting of limit checks into loops (which do allocation) required by
> Stephen's set up? If a loop does an allocation then the fact that there are
> an inifinite number of paths from the start which allocate any amount desired
> in the loop will mean that without a limit check in the loop there are NO
> correct annotations.
Yes, but under the existing limit check insertion, we can hoist a limit
check for an allocation down the loop exit into a non-allocating loop.
That's that extra limit check in tailfib.sml.
> I don't think that any amount of moving limit checks can violate our notion
> of safe-for-space. The reason is that it only costs you an `arbitrary'
> amount for non-tail calls, and then you are still safe for space since you
> can charge the fixed overhead to the non-tail call stack frame.
>
> Don't get me wrong: we would be wasting space in the case Matthew mentions,
> but it would still be safe-for-space in our sense. I.e., we already waste
> that space in other ways (like by turning tail calls into non-tail calls).
Agreed. I wasn't claiming that limit checks would violate safe-for-space
in the stack sense. Just that we could get into a situation where we
asked for more than a "reasonable" ammount of space for the execution of
the program.
> As to the final paragraph in Matthew's note, I think that if you don't handle
> that case you will do extra limit checks. Not a failure, but not optimal.
No, I meant to point out that if you use the standard intra-procedural
control flow (i.e., paths from non-tail caller block to continuation
block), then you might _not_ put a limit check in the continuation,
thinking that the limit check done before the non-tail call got you enough
space.