WebAssembly / WebAssembly/binaryen

Missing optimization in Wasm for `x < 0 || x > constant`

Open
#6,685 3 comments 1 reaction 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
WebAssembly
Stars
8.6k
Forks
885
Avg merge
1d 19h
Merged PRs (30d)
69

Description

The attached .wasm file has this code at offset 95044:

 95044|        block $label3
 95046|          block $label2
 95048|            local.get $var6
 95050|            i64.const 0
 95052|            i64.lt_s                     ;; $var6 < 0 (signed)
 95053|            br_if $label2                ;; Jump to error branch
 95055|            local.get $var6
 95057|            i64.const 255
 95060|            i64.gt_s                     ;; $var6 > 255 (signed)
 95061|            i32.eqz                      ;; Negate the condition
 95062|            br_if $label3                ;; Jump to OK branch
 95064|          end $label2                    ;; Error branch
 95065|          call $FormatException
 95068|          call $Error._throwWithCurrentStackTrace
 95071|          unreachable
 95072|        end $label3                      ;; OK branch

This is a direct translation of Dart code:

if (value < 0 || value > 255) throw ...

When optimized with wasm-opt 765c61445 (current main branch) using flags

--all-features
--closed-world
--traps-never-happen
--type-unfinalizing
-Os
--type-ssa
--gufa
-Os
--type-merging
-Os
--type-finalizing

wasm-opt generates this:

local.tee $var0
i64.const 0
i64.ge_s                        ;; var0 >= 0 (signed)
local.get $var0
i64.const 255
i64.le_s                        ;; var0 =< 255 (signed)
i32.and
if                              ;; OK branch
  ...
else                            ;; Error branch
  ...
end

Here var0 >= 0 && var0 <= 255 part could be optimized to a single unsigned comparison

local.get $var0
i64.const 255
i64.le_u
if
  ...                           ;; OK branch
else
  ...                           ;; Error branch
end

Interestingly on a different program with the exact same Dart expression, wasm-opt generates different instructions, but with the same missing optimization:

local.get $var9
i64.const 0
i64.lt_s                ;; $var9 < 0 (signed)
br_if $label4
local.get $var9
i64.const 255
i64.gt_s                ;; $var9 > 255 (signed)
i32.eqz
br_if $label5

For this second program, an older wasm-opt (d844d2e77) generates code with a more obvious missing optimization:

local.tee $var5
i64.const 0
i64.ge_u                   ;; var5 >= 0 (unsigned)
local.get $var5
i64.const 255
i64.le_u                   ;; var5 <= 255 (unsigned)
i32.and
i32.eqz

Here ge_u against 0 will always evaluate to 1, so the code can be simplified to the same optimized code as above.

test.wasm.zip

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reproducing the attached test.wasm.zip with wasm-opt 765c61445 and the listed optimization flags, then compare the generated instructions with the expected unsigned comparison. Trace the relevant optimization passes for the signed range check and add a regression test showing that the equivalent 0–255 condition folds to one unsigned comparison.

Written by the indexing model from the issue text.

Assessment

Tech stack
wasm
Domain
compilers, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.