a more efficient loopForestSteensgaard

[Matthew Fluet]

> > But, the flip side of that is that with your representation, computing the
> > (full) set of nodes in a loop is linear in the size of the input graph.
> > So, if you ask for the full set of nodes in a loop from each node, you're
> > still quadratic.
> 
> It is possible by a single walk over the tree (hence in time
> proportional to the size of the graph) to associate each node to a
> node vector list that contains all of the nodes in the deepest loop of
> which that node is a member.  The tree walk computes for each subtree
> the list of notInLoop vectors that appear in the subtree.

O.k., but your just shifting the space and time for computing this full
set from the computation of the loop forest to the processing of the loop
forest.  Sure, probably anything that wants a loopForest is going to
require some post processing, but computing inLoop from notInLoop requires
additional concats.

I'm not saying that we definitely need inLoop, but if almost everything
(and, currently, that's just the x86 codegen) that computes a loop forest
ends up computing the inLoop sets, then we might as well do it when
computing the loop forest.

> > Yes, you can store "deepest occurence of l in the loop forest", but you
> > need something else to determine if two nodes are nested relative to each
> > other.  You really want a representation of the path to the notInLoop
> > vector, so that you can see if one path is a prefix of the other; if so,
> > then the node with the longer path is nested inside the other node's loop.
> 
> Ah.  Makes sense.  Setting the path as a property is easy enough in a
> linear time pass over the tree.

Yup; it's just an int list using Vector.foreachi when processing the
loops.

> > I guess, in conclusion, I can switch over to the new loopForestSteensgaard
> > representation (without inLoop).
> 
> I think this is the way to go, since it looks like all the other stuff
> you need is computable via a linear pass over the loop forest.

O.k.  I just got to the point where x86LoopInfo uses the new loopForest
representation and fixed up it's sig to what's really needed.  Give me
about half an hour to do compiles and regressions, and I'll check in the
new code.