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.