How to merge Hoopl graph blocks / how to pass through the blocks

Question

I'm trying to introduce Hoopl into some compiler and faced some problem: creating a graph for Hoopl makes the nodes to appear in order of labels that were introduced.

Eg:

(define (test) (if (eq? (random) 1 ) 2 (if (eq? (random) 2 ) 3 0) ) )

"compiles" to

L25:    call-direct random  -> _tmp7_6
    branch L27
L26:    return RETVAL
L27:    iconst 1 _tmp8_7
    branch L28
L28:    call-direct eq? _tmp7_6, _tmp8_7 -> _tmp4_8
    branch L29
L29:    cond-branch _tmp4_8 L30 L31
L30:    iconst 2 RETVAL
    branch L26
L31:    call-direct random  -> _tmp12_10
    branch L32
L32:    iconst 2 _tmp13_11
    branch L33
L33:    call-direct eq? _tmp12_10, _tmp13_11 -> _tmp9_12
    branch L34
L34:    cond-branch _tmp9_12 L36 L37
L35:    assign RETVAL _tmp6_15
    branch L26
L36:    iconst 3 _tmp6_15
    branch L35
L37:    iconst 0 _tmp6_15
    branch L35

The order of instructions (in order of showGraph) is strange, because of order of recursive graph building from the AST. In order to generate code I need to reorder blocks in more natural way, say place return RETVAL to the end of function, merge blocks like this

    branch Lx:
Lx: ...

into the one block, and so on. Seems that I need something like:

block1 = get block
Ln = get_last jump
block2 = find block Ln
if (some conditions) 
    remove block2
    replace blick1 (merge block1 block2)

I'm totally confused how to perform this with Hoopl. Of course, I may dump all the nodes and then perform the transformations outside the Hoopl framework, but I believe that this is bad idea.

May someone give me any glue? I did not find any useful examples. Something similar is performed in Lambdachine project, but seems too complicated.

There is also an another question. Is there any point to make all Call instruction non-local? What the point of this considering that implementation of Call is not changing any local variables and always transfer the control to the next instruction of the block? If Call instructions are defined like

data Insn e x where
   Call :: [Expr] -> Expr -> Label :: Insn O C -- last instruction of the block

that cause the graph to looks even more strange. So I use

-- what the difference with any other primitive, like "add a b -> c" 
Call :: [Expr] -> Expr -> Label :: Insn O O 

May be I'm wrong with this?

Answer 1

I've found and tried a couple of ways to do the trick:

1. Using foldBlockNodesF3 function or other foldBlockNodes... functions
2. Using preorder_dfs* functions (like in Lambdachine project)
3. Build the graph with larger blocks from the start

The last option is not useful for me, because FactBase is linked with labels, so every instruction that change a liveness of the variables should have a label for using in the following analysis.

So, my final solution is to use foldBlockNodesF3 function and linearize the graph and delete extra labels manually with simultaneous register allocation

Answer 2

It is possible to implement the "block merging" using HOOPL. Your question is too generic, so I give you a plan:

1. Determine what analysis type this optimization requires (either forward or backward)
2. Design the analysis lattice
3. Design the transfer function
4. Design the rewriting function
5. Create a pass
6. Merge the pass with other passes of the same direction so they interleave
7. Run the pass using fuel
8. Convert optimized graph back to the form you need

With which stages do you have problems? Steps 1 and 2 should be rather straightforward once you've read the papers.

You should also understand the general concept of basic block - why instructions are merged into blocks, why control flow graph consists of blocks and not of individual instructions, why analysis is performed on blocks and not on individual instructions.

Your rewrite function should use the facts to rewrite the last node in the block. So the fact lattice should include not only "information about reachability", but also the destination blocks themselves.