limit checks

[Matthew Fluet]

> That is quite possible, since limit checks are moved backward across
> control flow edges (forward in time :-).  For example, if there is an
> if-test that requires a limit check only on one branch, then the limit
> check will be moved up before the test with coalescing.

Yes, I realized this afterwards.

> We were very much focused on decreasing the static number of limit
> checks.  We are not at the min, as your pathalogical example showed,
> but we're probably pretty close.  There are clearly improvements that
> could be had to our current approach that will decrease the dynamic
> counts without increasing the static counts.  For example, pushing a
> limit check down an if branch if it is only needed on one branch.

Agreed.  Something bouncing around in my mind, but not fully developed
yet, is to do some sort of dynamic programming assignment on the CFG as
decycled by the loop headers; I think something like that would move
towards the min.

> What's not clear is if working on decreasing the dynamic counts is
> worth the effort.  It's tough to measure the run-time cost of limit
> checks, which I would guess is almost zero.  

Yes; one of the comments I want to make is that although the cost of
a limit check itself is small (2 or 3 instructions), there are auxilary
costs to consider -- at every limit check, you have the potential to fail
and be forced to GC; that entails at least some code to transfer and
return from a GC and additional "work" to ensure that the roots are set up
correctly (one can imagine multiple schemes of transfering root info to
the GC, but they will all either require some setup if the limit check
fails or "constraints" (on register allocation, etc.) around the limit
check point).

> But maybe we need to make
> an attempt.  Also, the interplay with other optimizations, like
> register allocation, argues that keeping the static count small is
> good because fewer variables will be live across limit checks, and
> will hence be free to live in pseudo-regs.

On the other hand, moving limit checks backwards along control flow edges
might move a limit check into the live range of a variable, which would
otherwise live in a pseudo-reg.  Go back to your if-test; if there are
allocations down both branches, then moving the limit check to before the
test forces the test variable (or variables used in the test expression)
to be live across a limit-check and hence stack allocated.

On the other hand, I did look at benchmarks with
-native-live-stack {false,true} -limit-check-per-block {false,true}
and, again, there was almost no runtime difference between the different
limit-check insertions.