limit check insertion via loop forests

[Matthew Fluet]

> > But if there is a non-allocating loop followed
> > by some allocations, we want to avoid moving the limit check into the
> > loop, where we would expect it to be executed more often.
> 
> Although, if there is an allocating loop followed by some allocations,
> I would argue that we should move the limit check backward and
> coalesce it into the loop limit check.  My proposal doesn't do this,
> so there is still room for improvement.

I spelled this out a little more verbosely in my previous email.  I don't
think it's that hard.  We just need to limit what labels are thrown into L
along with Headers.  Given your definition of "same loop" we can also
define a notion of the allocation of a loop -- it's simply the sum of A(l)
for all l in the same loop.  So, we define L : Label -> Loops and extend
A to Loops in the obvious manner.

L = Headers U
    { l | exists l' s.t. L(l) <> L(l'), A(L(l')) = 0, and l in S(l') }

i.e., add all labels that are following non-allocating loops.


B.t.w., there is one complication with Steve's represenation of loop
forests, which is that all of the nodes that aren't in any loops are
in the same notInLoop vector (at the top level) are effectively in the
same loop.  Not a big deal, when setting up the equivalence classes, we
just need to specially treat those in the top notInLoop vector.