WebAssembly / WebAssembly/binaryen

Incomplete analysis for the states of global integer variables that does not eliminate excessive equality checks

Open
#9,086 2 comments 0 reactions 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

In kotlin-wasm-benchmarks ParameterNotNullAssertionBenchmark we pass global property
val OBJ = Any()
as several arguments into methods, like
methodWithEightNotnullParameters(OBJ, OBJ, OBJ, OBJ, OBJ, OBJ, OBJ, OBJ).

With the current schema of the initialization in K/Wasm, OBJ getter first calls the function responsible for the initialization of static properties for the whole file - here $"microBenchmarks.<init properties ParameterNotNullAssertionBenchmark.kt>"

  (func $microBenchmarks.<get-OBJ> (;5386;) (type $"#type1038 ") (result (ref null $kotlin.Any))
    call $"microBenchmarks.<init properties ParameterNotNullAssertionBenchmark.kt>"
    global.get $microBenchmarks.OBJ
    return
  )

Initialization function first checks, by the global state
(global $"microBenchmarks.properties initialized ParameterNotNullAssertionBenchmark.kt" (;5674;) (mut i32) i32.const 1)

  • if the properties were already successfully initialized (value 0) - fast path, just return
  • if previous initialization attempt failed (value 2) - call staticInitializationFailureWithClassName that will throw corresponding error
  • if not initialized (value 1) - call initializers inside try {} catch {} block, so that when the error occur we will be able to catch it and throw corresponding staticInitialization error.
  (func $"microBenchmarks.<init properties ParameterNotNullAssertionBenchmark.kt>" (;5400;) (type $"#type3092 ")
    (local $~state i32) (local $reason (ref null $kotlin.Throwable))
    global.get $"microBenchmarks.properties initialized ParameterNotNullAssertionBenchmark.kt"
    local.tee $~state
    i32.eqz
    if ;; label = @1  // already successfully initialized, state == 0
      return
    end
    local.get $~state
    i32.const 2
    i32.eq
    if ;; label = @1 // previous initialization attempt failed, state == 2 - throw corresponding error
      ref.null none
      call $kotlin.wasm.internal.staticInitializationFailureWithClassName
      unreachable
    end
    i32.const 0
    global.set $"microBenchmarks.properties initialized ParameterNotNullAssertionBenchmark.kt" // state = 0
    try ;; label = @1 // try to initialize, catch an error if thrown during initialization
      global.get $"#global6460 <classVTable>"
      ref.null none
      global.get $kotlin.Any_rtti
      i32.const 0
      struct.new $kotlin.Any
      global.set $microBenchmarks.OBJ
    catch 0
      call $kotlin.wasm.internal.getKotlinException
      local.set $reason
      i32.const 2 // state = 2
      global.set $"microBenchmarks.properties initialized ParameterNotNullAssertionBenchmark.kt"
      local.get $reason
      ref.null none
      call $kotlin.internal.staticInitializationFailure
      unreachable
    end
    nop
  )

Here, initializer for OBJ property is primitive and Binaryen seems to be able to prove that it does not throw an error. So, it removes try/catch block and inlines $"microBenchmarks.<init properties ParameterNotNullAssertionBenchmark.kt>" function into <get-OBJ>.

  (func $microBenchmarks.<get-OBJ> (;2109;) (type 128) (result (ref null $kotlin.Any_125))
    (local i32)
    global.get $"microBenchmarks.properties initialized ParameterNotNullAssertionBenchmark.kt"
    local.tee 0
    if ;; label = @1 // state != 0
      local.get 0
      i32.const 2
      i32.eq
      if ;; label = @2 // state == 2 - excessive check
        ref.null none
        call $kotlin.wasm.internal.staticInitializationFailureWithClassName
        unreachable
      end
      i32.const 0
      global.set $"microBenchmarks.properties initialized ParameterNotNullAssertionBenchmark.kt"
      global.get $<classVTable>_1501
      ref.null none
      global.get $kotlin.Any_rtti
      i32.const 0
      struct.new $kotlin.Any_125
      global.set $microBenchmarks.OBJf
    end
    global.get $microBenchmarks.OBJ
  )

Since, try/catch block is gone, there is no more assignment state = 2, but there is a check for it. Without this check Binaryen (as we observed) could inline $microBenchmarks.<get-OBJ> into its callsites and speed up the benchmark. Is it feasible to eliminate such kind of checks?

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 with kotlin-wasm-benchmarks/src/commonMain/kotlin/microBenchmarks/ParameterNotNullAssertionBenchmark.kt and reproduce the generated getter and initialization function shown in the issue. Trace the optimization that removes the try/catch block, then verify that the redundant state == 2 check can be eliminated without changing initialization-failure behavior and that the getter can still be inlined into its callsites.

Written by the indexing model from the issue text.

Assessment

Tech stack
kotlin, wasm
Domain
compilers, performance
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.