Metering is not correct in presence of divergent control flow

[georgemitenkov]

Describe the bug

Metering instrumentation does not work for if-else statements.
Because the instrumentation is injected naively when the change on control flow is detected, for if-else statements the cost of preceding instructions is only included for the if branch.

Example of a program which has incorrect costs.

(module
(func $bomb (param $condition i32) (result i32)
    ;; dummy instructions to ensure high cost
    (local.set $condition (local.get $condition))
    (local.set $condition (local.get $condition))
    (local.set $condition (local.get $condition))
    (local.set $condition (local.get $condition))
    (if (result i32) (local.get $condition)
        (then
            (block (result i32) (local.get $condition))
         )
        (else
            (block (result i32) (local.get $condition))
        )
))

The instrumented code produced by Wasmer:

LocalGet { local_index: 0 }
LocalSet { local_index: 0 }
LocalGet { local_index: 0 }
LocalSet { local_index: 0 }
LocalGet { local_index: 0 }
LocalSet { local_index: 0 }
LocalGet { local_index: 0 }
LocalSet { local_index: 0 }
LocalGet { local_index: 0 }
If { blockty: Type(I32) }
Block { blockty: Type(I32) }
LocalGet { local_index: 0 }
METER(13)
End
METER(1)
Else
Block { blockty: Type(I32) }
LocalGet { local_index: 0 }
METER(3)
End
METER(1)
End
METER(1)
End

We can see that the else branch has lower cost than it should.

Additional context

To fix the issue, the metering has to account for diverging control flow, or a different algorithm should be used.