a more efficient loopForestSteensgaard

[Stephen Weeks]

> > > 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.

No.  The space required for my proposed representation of inLoop is
linear in the size of the program graph.  I don't do any concats, I
just keep a list of vectors (of notInLoop's).  The post-processing is
linear time.  The space usage is linear because of the sharing of
vectors amongst multiple loops.

> 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.  

Great!