a more efficient loopForestSteensgaard

[Stephen Weeks]

As a reminder, here is my original datatype.

      datatype t = T of {loops: {headers: Node.t vector,
				 child: t} vector,
			 notInLoop: Node.t vector}

Here is your proposal.

      datatype t = T of {loops: {headers: Node.t vector,
                                 inLoop: Node.t vector,
				 child: t} vector,
			 notInLoop: Node.t vector}

> Yes, inLoop could be computed from the original datatype by concating all
> of the notInLoop vectors down the child, but (1) the codegen more often
> wants to know what's in a loop, not what's not in a loop, and (2) it's
> already calculated as the scc, so we just need to save it in the datatype.

I agree that inLoop is already computed in the scc computation.  My
only worry is that my original representation was linear in the size
of the input graph, while storing all the inLoops may be quadratic.
Of course, we may already be screwed in such a case because it would
have taken quadratic time to compute (using Steensgaard).  But I would
hate to force a quadratic representation on other loop forests that
don't take quadratic time to compute.

> Did you have something specific in mind for notInLoop?  

Yes.  It defines an equivalence relation on nodes, where two nodes are
equivalent if they occur in the same notInLoop vector.  This relation
captures the idea of being in exactly the same loop (and not in a more
deeply nested one).  I plan to use this for limit check insertion to
prevent moving limit checks across loop boundaries.  I also like
notInLoop because it gives a linear size representation of the loop
forest.

>  - nodes that are marked as a loopHeader get extra alignment, 
>     even if they are a fall through label; so I don't think that marking
>     every node in a trivial scc as a header is a good idea.

I'm confused about the meaning of "trivial scc".  Is a single node
with a self edge a trivial scc (I think not)?  Those will appear as
headers in my forest, which I think makes sense.  Single nodes without
self edges will only ever appear in a notInLoop.  So, I think that
aligning all of the nodes that appear in headers vectors makes sense.

> So, at a minimum, I would want an isHeader predicate returned by a loop
> forest calculation.  The other stuff I could probably compute from the
> proposed return type.  

You can set an isHeader property on nodes by a single walk over the
tree.

>  - x86GenerateTransfers wants to be able to compute the following to
>     decide how to layout blocks at an Iff:
>  if neither of the truee's and falsee's blocks have been generated,
>   then fall thru to the label with the least "loop-distance" from the
>   Iff's label (where loop distance from l1 to l2 is NONE if l1 and l2 are
>   in non-nested loops, and SOME (d(l2) - d(l1)) where d(l) is the depth of
>   the deepest occurence of l in the loop forest); this favors staying in
>   the same loop or entering nested loops over exiting loops

"deepest occurrence of l in the loop forest" corresponds to the depth
of the occurence of l in a notInLoop vector, right?  Assuming so, you
can compute and store this as property by a walk over the tree.

Since you're computing the distances from the same source (l1), this
heuristic says to fall through to the more deeply nested loop, right?

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.

>  - given a node, x86LiveTransfer wants to be able to compute all of the
>     nodes in same loop (actually, all of the nodes in the the deepest
>     nested loop of which the original node is a member)

This is the only place I see where you need inLoop.  I don't
understand well enough what you're using it for to know if the
notInLoop equivalence relation could suffice.

So, I'm still unsure whether we need the inLoop or not.