Relooper Algorithm

[MikeInnes]

Like #23, but splits all the CFG logic from the actual generation of expressions (todo), which should make it a bit easier to reuse in other contexts.

julia> using IRTools: @code_ir, CFG, reloop

julia> cfg = CFG(@code_ir gcd(10, 5))
CFG(Array{Int64,1}[[4, 2], [], [5], [5], [8, 6], [], [9], [9], [10], [14, 11], [13, 12], [13], [10], [16, 15], [17], [17], []])

julia> reloop(cfg)
Structured CFG:
1
Multiple:
  Simple:
    4
    5
    Multiple:
      Simple:
        8
        9
        Loop:
          10
          11
          Multiple:
            12
          13
        Multiple:
          14
        Multiple:
          Simple:
            16
          Simple:
            15
        17
      Simple:
        6
  Simple:
    2

Needs some docs and a PoC for generating Julia expressions.

[MikeInnes]

Had a quick go at AST recovery:

julia> ir = explicitbranch!(IR(@meta(pow(1,1)), slots = true));

julia> ex = reloop(ir)
quote
    slot_5 = arg3
    slot_4 = 1
    __label__ = 2
    begin
        while true
            begin
                if slot_5 > 0
                    __label__ = 3
                else
                    __label__ = 4
                    break
                end
                begin
                    slot_5 = slot_5 - 1
                    slot_4 = slot_4 * arg2
                    begin
                        __label__ = 2
                        continue
                    end
                    nothing
                end
            end
        end
        begin
            return slot_4
            nothing
        end
    end
end

Clearly, this is not the prettiest code. Luckily it's quite straightforward to elide all these labels where they are obviously redundant (which should be all Julia code that doesn't use @goto).