SwadicalRag / wasm2lua

wasm2lua: converting WASM into Lua
MIT License
194 stars 11 forks source link

Optimise allocation of local variables #21

Open SwadicalRag opened 5 years ago

SwadicalRag commented 5 years ago

This way virtual registers are confined within a block and the LuaJIT's tracer heuristics can work better with inferring local variable lifespans

MDFL64 commented 5 years ago

when do I get to tear the code apart and add big boy ssa ir?

presumably it will be sometime I actually have time to do literally anything

SwadicalRag commented 5 years ago

anytime, fam. I think we've half implemented SSA IR through phantom registers (they can only be created once, and right now are only assigned to once) and temporary virtual registers (created once, assigned once)

SwadicalRag commented 5 years ago

Copy+pasted from discord

locals/registers be translated with these rules: assume (blocks B1 -> B2 -> B3 -> B4 -> B5)

  1. if a local is declared in a sub block (e.g. B5) but it is later used in a parent block (e.g. B2) , its declaration should be hoisted to either (whichever exists firsts, in order): 1.a) before the first sub-block to the local declaration (B3) starts in the parent block 1.b) before the first sub-block containing the local declaration starts in the parent block
  2. if a local is declared in a sub block but does not leave the sub block, it can be declared where it was first referenced
SwadicalRag commented 5 years ago

say example:

do -- block1
    do (result i32) -- block2
        i32.load 1
        setvar var1
        loadvar var1
        call print
        i32.load 2
        setvar var2
    end

    loadvar var2
    call print
end

so using those rules, the above code will be translated to

do
    local var2;
    do
        local var1 = 1
        print(var1)
        var2 = 2
    end
    print(var2)
end
SwadicalRag commented 5 years ago

and with the same rules:

do -- block1
    do -- block2
        -- other code here
        do -- block3
            do -- block4
                i32.load 1
                setvar v1
                loadvar v1
                call print
                i32.load 2
                setvar v2
            end
        end
        -- other code here
    end
    -- other code here
    loadvar v2
    print
end

becomes

do -- block1
    local v2
    do -- block2
        -- other code here
        do -- block3
            do -- block4
                local v1 = 1
                print(v1)
                v2 = 2
            end
        end
        -- other code here
    end
    -- other code here
    print(v2)
end
SwadicalRag commented 5 years ago

increment currentBlockState.currentDeclarations or funcState.currentDeclarations (whichever exists first) every time something is declared

if (sum(currentDeclarations in funcState.blocks) + funcState.currentDeclarations) >= 199 {
    if(!funcState.useTableVariables) {
        funcState.useTableVariables = true;
        funcState.tableVariableIdx = 1;
    }
    -- allocate `tableVarName[${funcState.tableVariableIdx++}]`
}