Optimization for speed by code duplication

[cardillan]

Suggested by @limonovthesecond2 here.

In loops with expressions such as if-else and case after the expression is completed, the jump forwards to the next command after the comparing. However, we can inject all the code there instead. Example:

i = 0
do
    block = getlink(i)
    case block
        when @unloader then print("unloader")
        when @sorter then print("sorter")
        else print("else")
    end
    i += 1
loop while i < @links

Compiles:

set i 0
getlink block i
jump 5 notEqual block @unloader
print "unloader"
jump 9 always 0 0
jump 8 notEqual block @sorter
print "sorter"
jump 9 always 0 0
print "else"
op add i i 1
jump 1 lessThan i @links
end

This code compiles with 2 jump 9 always, which redirects to the loop condition and adding a counter. Instead of this redirection, we can add code itself at the end of each condition, which will result in larger size but also greater efficiency. To avoid reaching the size limit, something like auto-function-inline can be used with a maximum operation size limit.

i = 0
while true
    block = getlink(i)
    case block
        when @unloader then
            print("unloader")
            i += 1
            if i >= @links
                end()
            end
        when @sorter then
            print("sorter")
            i += 1
            if i >= @links
                end()
            end
        else
            print("else")
            i += 1
            if i >= @links
                end()
            end
    end
end

Compiles:

set i 0
getlink block i
jump 7 notEqual block @unloader
print "unloader"
op add i i 1
jump 1 lessThan i @links
end
jump 12 notEqual block @sorter
print "sorter"
op add i i 1
jump 1 lessThan i @links
end
print "else"
op add i i 1
jump 1 lessThan i @links
end
end

[cardillan]

It looks like this optimization could improve nested conditional expressions as well as loops:

if A
    if B print("B") else print("not B") end
    print("A")
else
    print("not A")
end

compiles to

jump 7 equal A false
jump 4 equal B false
print "B"
jump 5 always 0 0
print "not B"
print "A"
jump 0 always 0 0
print "not A"
end

which could be improved to

jump 8 equal A false
jump 5 equal B false
print "B"
print "A"
jump 0 always 0 0
print "not B"
print "A"
jump 0 always 0 0
print "not A"
end

An optimizer might therefore inspect every unconditional jump, and if it leads to a section of linear code ended by an unconditional jump, replace the jump with the target section of code. If the jump at the end of the section is conditional, and is part of a loop condition, the loop condition would be duplicated there.

In the initial implementation, complex structures (e.g. function calls or conditional expressions) wouldn't be copied.

Code optimizers (particularly the Data Flow Optimizer, but some others too) rely on the compiled code having certain expected structure. The DFO will need to be updated to understand the new structure.