[WebAssembly] Loop that shouldn't be given a return type

[Photosounder]

I could be wrong about this one because Wasm control flow is confusing, but I'm 85% sure this C function compiles to something it shouldn't:

intmax_t make_power_of_10_int(int p)
{
	intmax_t v = 1;

	while (p >= 5) { v *= 100000; p -= 5; }
	while (p >= 1) { v *= 10;     p -= 1; }

	return v;
}

Using -Oz this compiles to:

make_power_of_10_int:
    i64.const         1
    local.set         1

        loop              i64
            block

            local.get       0
            i32.const       4
            i32.gt_s
            br_if           0

                block
                    loop

                    local.get       0
                    i32.const       1
                    i32.lt_s
                    br_if           1

                    local.get       0
                    i32.const       -1
                    i32.add
                    local.set       0

                    local.get       1
                    i64.const       10
                    i64.mul
                    local.set       1

                    br              0
                    end_loop
                end_block

            local.get       1
            return

            end_block

        local.get         0
        i32.const         -5
        i32.add
        local.set         0

        local.get         1
        i64.const         100000
        i64.mul
        local.set         1

        br                0
        end_loop

    end_function

The problem is that:

• The first (outermost) loop has a i64 return type, but at the 4th line from the bottom local.set 1 empties the stack.
• This loop branches unconditionally with br 0, so even if there was something in the stack it could never be used.
• This loop and the whole function can only end through return.
• The result is stored in local1 anyway, I can't see why the loop would need a return type.

Therefore the most immediately obvious conclusion is that giving that loop a return type is a mistake because it doesn't actually return anything (due to empty stack) and it can never exit normally anyway. I guess it would make sense if at the end of the loop the last local.set was treated as a local.tee, but I see no reason to believe things are supposed to work like this.

This problem seems specific to -Oz as the other optimisation settings produce totally different Wasm.

[llvmbot]

@llvm/issue-subscribers-backend-webassembly

Author: Michel Rouzic (Photosounder)

I could be wrong about this one because Wasm control flow is confusing, but I'm 85% sure this C function compiles to something it shouldn't:

intmax_t make_power_of_10_int(int p)
{
	intmax_t v = 1;

	while (p >= 5) { v *= 100000; p -= 5; }
	while (p >= 1) { v *= 10;     p -= 1; }

	return v;
}

Using -Oz this compiles to:

make_power_of_10_int:
    i64.const         1
    local.set         1

        loop              i64
            block

            local.get       0
            i32.const       4
            i32.gt_s
            br_if           0

                block
                    loop

                    local.get       0
                    i32.const       1
                    i32.lt_s
                    br_if           1

                    local.get       0
                    i32.const       -1
                    i32.add
                    local.set       0

                    local.get       1
                    i64.const       10
                    i64.mul
                    local.set       1

                    br              0
                    end_loop
                end_block

            local.get       1
            return

            end_block

        local.get         0
        i32.const         -5
        i32.add
        local.set         0

        local.get         1
        i64.const         100000
        i64.mul
        local.set         1

        br                0
        end_loop

    end_function

The problem is that:

• The first (outermost) loop has a i64 return type, but at the 4th line from the bottom local.set 1 empties the stack.
• This loop branches unconditionally with br 0, so even if there was something in the stack it could never be used.
• This loop and the whole function can only end through return.
• The result is stored in local1 anyway, I can't see why the loop would need a return type.

Therefore the most immediately obvious conclusion is that giving that loop a return type is a mistake because it doesn't actually return anything (due to empty stack) and it can never exit normally anyway. I guess it would make sense if at the end of the loop the last local.set was treated as a local.tee, but I see no reason to believe things are supposed to work like this.

This problem seems specific to -Oz as the other optimisation settings produce totally different Wasm.

[tlively]

br is stack-polymorphic (see https://webassembly.github.io/spec/core/valid/instructions.html#instructions), so it can leave any types on the stack required by subsequent instructions, such as the end of the loop.

So while the loop certainly doesn't need a return type, it's also valid for it to have one. This code should validate and run on any WebAssembly engine (unless there's another problem here; I haven't tried running it myself).

[tlively]

To elaborate, here is the end of the function:

        br                0 ;; Branches to beginning of loop, leaves a polymorphic stack.
        end_loop            ;; End of loop i64. Pops an i64 off the polymorphic stack
                            ;; and pushes it back.
    end_function            ;; Pops the i64 off the stack and returns it
                            ;; (but this is never reached).

[Photosounder]

Thank you for the elaboration but even with a polymorphic stack I don't see what there is left to pop off of it at the end. Here's my annotation with the stack heights according to my understanding:

make_power_of_10_int:                     ; Stack height change
    i64.const         1                   ; 0 -> 1
    local.set         1                   ; 1 -> 0
                                          
        loop              i64             
            block                         
                                          
            local.get       0             ; 0 -> 1
            i32.const       4             ; 1 -> 2
            i32.gt_s                      ; 2 -> 1
            br_if           0             ; 1 -> 0
                                          
                block                     
                    loop                  
                                          
                    local.get       0     ; 0 -> 1
                    i32.const       1     ; 1 -> 2
                    i32.lt_s              ; 2 -> 1
                    br_if           1     ; 1 -> 0
                                          
                    local.get       0     ; 0 -> 1
                    i32.const       -1    ; 1 -> 2
                    i32.add               ; 2 -> 1
                    local.set       0     ; 1 -> 0
                                          
                    local.get       1     ; 0 -> 1
                    i64.const       10    ; 1 -> 2
                    i64.mul               ; 2 -> 1
                    local.set       1     ; 1 -> 0
                                          
                    br              0     
                    end_loop              
                end_block                 
                                          
            local.get       1             ; 0 -> 1
            return                        ; 1 -> 0
                                          
            end_block                     
                                          
        local.get         0               ; 0 -> 1
        i32.const         -5              ; 1 -> 2
        i32.add                           ; 2 -> 1
        local.set         0               ; 1 -> 0
                                          
        local.get         1               ; 0 -> 1
        i64.const         100000          ; 1 -> 2
        i64.mul                           ; 2 -> 1
        local.set         1               ; 1 -> 0
                                          
        br                0               ; 0
        end_loop                          ; 0
                                          
    end_function                          ; 0 -> -1

I think there's something I'm getting wrong, but no matter how I think of it I can't imagine what could be left in the stack because it seems to me that local.set empties the stack no matter what. Does the unconditional branching making the rest unreachable mean that it's imaginarily popping an imaginary element off the stack?

[tlively]

Does the unconditional branching making the rest unreachable mean that it's imaginarily popping an imaginary element off the stack?

Yes, pretty much. This is the magical polymorphic behavior I was talking about.