We can splice a single-entry, single-exit LGraph onto a head or a tail. For a head, we have a head h followed by a LGraph g. The entry node of g gets joined to h, forming the entry into the new LGraph. The exit of g becomes the new head. For both arguments and results, the order of values is the order of control flow: before splicing, the head flows into the LGraph; after splicing, the LGraph flows into the head. Splicing a tail is the dual operation. (In order to maintain the order-means-control-flow convention, the orders are reversed.)

For example, assume head = [L: x:=0] grph = (M, [M: stuff, blocks, N: y:=x; LastExit]) tail = [return (y,x)]

Then splice_head head grph = ((L, [L: x:=0; goto M, M: stuff, blocks]) , N: y:=x)

Then splice_tail grph tail = ( stuff , (???, [blocks, N: y:=x; return (y,x)])

A safe operation

Conversion to and from the environment form is convenient. For layout or dataflow, however, one will want to use postorder_dfs in order to get the blocks in an order that relates to the control flow in the procedure.

Traversal: postorder_dfs returns a list of blocks reachable from the entry node. This list has the following property:

Say a back reference exists if one of a block's control-flow successors precedes it in the output list

Then there are as few back references as possible

The output is suitable for use in a forward dataflow problem. For a backward problem, simply reverse the list. (postorder_dfs is sufficiently tricky to implement that one doesn't want to try and maintain both forward and backward versions.)

This is the most important traversal over this data structure. It drops unreachable code and puts blocks in an order that is good for solving forward dataflow problems quickly. The reverse order is good for solving backward dataflow problems quickly. The forward order is also reasonably good for emitting instructions, except that it will not usually exploit Forrest Baskett's trick of eliminating the unconditional branch from a loop. For that you would need a more serious analysis, probably based on dominators, to identify loop headers.

The ubiquity of postorder_dfs is one reason for the ubiquity of the LGraph representation, when for most purposes the plain Graph representation is more mathematically elegant (but results in more complicated code).

Here's an easy way to go wrong! Consider A -> [B,C] B -> D C -> D Then ordinary dfs would give [A,B,D,C] which has a back ref from C to D. Better to get [A,B,C,D]

For layout, we fold over pairs of 'Block m l' and 'Maybe BlockId' in layout order. The 'Maybe BlockId', if present, identifies the block that will be the layout successor of the current block. This may be useful to help an emitter omit the final goto of a block that flows directly to its layout successor.

For example: fold_layout f z [ L1:B1, L2:B2, L3:B3 ] = z $ f (L1:B1) (Just L2) $ f (L2:B2) (Just L3) $ f (L3:B3) Nothing where a $ f = f a