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.

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

> > I agree with favoring staying or going to a more deeply nested loop
> > over exiting, but I am confused why you favor entering a more deeply
> > nested loop over staying in the same loop.
> 
> No real empirical reason (and, any small permutations on layout of blocks
> and how iff's fall don't make any consistent changes to runtimes).  There
> are a couple of reasons, though, that I think it makes sense:
>  1. The basic premise that loops are likely to be taken, either in
>      staying in the loop or entering a loop; so, the right thing for
>      branch prediction is to fall into the deeper loop; (think
>      matrix-matrix multiply loops)
>  2. The inner loop is probably smaller, so (hopefully) putting its blocks
>      right here will be cheaper (code-size) than further jumps to and from
>      the inner loop if its blocks appear "far" away.

Makes sense.

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