Consider optimizing x < 0 || x > positiveInt to single unsigned comparison
#56083
Assignees
Labels
area-dart2wasm
Issues for the dart2wasm compiler.
Comments
copybara-service bot
pushed a commit
that referenced
this issue
Jul 2, 2024
…possible" This reverts commit 8b1aa18. Reason for revert: This caused at least two issues: (1) wasm-opt doesn't inline the simple helpers introduced in this CL, for example: ``` (func $IntToWasmInt|geU (;217;) (param $var0 i64) (param $var1 i64) (result i32) local.get $var0 local.get $var1 i64.ge_u ) ``` Even though when inlined this becomes just one instruction. This causes diffs like: ``` i64.const 1 i64.add local.set $var1 + local.get $var2 local.get $var10 struct.get $JSArrayBufferImpl_80 $field2 call $wasm:js-string.length (import) i64.extend_i32_u local.tee $var3 - local.get $var2 - i64.le_u + call $IntToWasmInt|geU if ``` (2) Changing `length.leU(index)` to `index.geU(length)` causes missing some optimizations like the following: ``` local.get $var0 ref.cast $JSArrayBufferImpl_80 local.tee $var3 struct.get $JSArrayBufferImpl_80 $field2 call $wasm:js-string.length (import) - drop + i64.extend_i32_u + local.tee $var4 + i64.const 0 + i64.lt_u + if + i64.const 0 + i64.const 0 + local.get $var4 + ref.null none + ref.null none + call $RangeError.range + call $Error._throwWithCurrentStackTrace + unreachable + end ``` Here the `i64.const 0; i64.lt_u` always produces `0`, but wasm-opt doesn't do this optimization. The Dart changes that caused this diff: ``` - if (WasmI64.fromInt(length).leU(WasmI64.fromInt(index))) { + if (index.geU(length)) { ``` Original change's description: > [dart2wasm] Use single unsigned cmp instead of two cmps when possible > > wasm-opt doesn't optimize `0 < x || x > y` when y is known to be > positive (e.g. a positive integer constant), so we do it manually. > > We also do it in a few places where `y` is not known to be positive in > the Wasm code, but we know it's always positive, for example when it's a > length. > > Example improvement in the wasm-opt output: > > ``` > (func $_newArrayLengthCheck (;426;) (param $var0 i64) (result i64) > local.get $var0 > i64.const 2147483647 > - i64.le_s > - local.get $var0 > - i64.const 0 > - i64.ge_s > - i32.and > - i32.eqz > + i64.gt_u > if > i32.const 46 > i32.const 0 > @@ -19190,13 +19172,8 @@ > i64.const 97 > i64.sub > local.tee $var3 > - i64.const 0 > - i64.ge_s > - local.get $var3 > i64.const 5 > - i64.le_s > - i32.and > - i32.eqz > + i64.gt_u > if > local.get $var0 > local.get $var6 > @@ -19810,10 +19787,10 @@ > global.get $global4 > array.new_fixed $Array<_Type> 2 > ) > ``` > > Closes #56083. > > Change-Id: Idb1dd0d0809b26be8aec3d082aa341c59e1a353d > Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/373663 > Reviewed-by: Martin Kustermann <[email protected]> > Commit-Queue: Ömer Ağacan <[email protected]> Change-Id: Iac5428037b0c19d76e4c841a1b6623b7305ff702 Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/373800 Reviewed-by: Martin Kustermann <[email protected]> Reviewed-by: Ömer Ağacan <[email protected]> Bot-Commit: Rubber Stamper <[email protected]> Commit-Queue: Ömer Ağacan <[email protected]>
osa1
added a commit
to osa1/sdk
that referenced
this issue
Jul 2, 2024
…possible" This is a reland of commit 8b1aa18 Original change's description: > [dart2wasm] Use single unsigned cmp instead of two cmps when possible > > wasm-opt doesn't optimize `0 < x || x > y` when y is known to be > positive (e.g. a positive integer constant), so we do it manually. > > We also do it in a few places where `y` is not known to be positive in > the Wasm code, but we know it's always positive, for example when it's a > length. > > Example improvement in the wasm-opt output: > > ``` > (func $_newArrayLengthCheck (;426;) (param $var0 i64) (result i64) > local.get $var0 > i64.const 2147483647 > - i64.le_s > - local.get $var0 > - i64.const 0 > - i64.ge_s > - i32.and > - i32.eqz > + i64.gt_u > if > i32.const 46 > i32.const 0 > @@ -19190,13 +19172,8 @@ > i64.const 97 > i64.sub > local.tee $var3 > - i64.const 0 > - i64.ge_s > - local.get $var3 > i64.const 5 > - i64.le_s > - i32.and > - i32.eqz > + i64.gt_u > if > local.get $var0 > local.get $var6 > @@ -19810,10 +19787,10 @@ > global.get $global4 > array.new_fixed $Array<_Type> 2 > ) > ``` > > Closes dart-lang#56083. > > Change-Id: Idb1dd0d0809b26be8aec3d082aa341c59e1a353d > Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/373663 > Reviewed-by: Martin Kustermann <[email protected]> > Commit-Queue: Ömer Ağacan <[email protected]> Change-Id: I822ca612e5c8d5d33ba443107b72e9f1021c5c4a
copybara-service bot
pushed a commit
that referenced
this issue
Jul 2, 2024
…possible" This is a reland of commit 8b1aa18 This relands the commit with the following changes to avoid regressions and some random changes: - Add inline annotations to `IntToWasmInt` extensions. These methods are 3 instructions long and often become just one instruction when inlined, but wasm-opt still doesn't inline them, turning a single `i64.lt_u` and similar into a function call. - Revert changes from `length.leU(index)` to `index.geU(length)`. I had done this change because I find `if (index >= length) throw` easier to read than `if (length <= index) throw`, but the change introduced some larger changes in the wasm-opt output. These changes are probably harmless, but to minimize unintentional changes I reverted these changes for now. Original change's description: > [dart2wasm] Use single unsigned cmp instead of two cmps when possible > > wasm-opt doesn't optimize `0 < x || x > y` when y is known to be > positive (e.g. a positive integer constant), so we do it manually. > > We also do it in a few places where `y` is not known to be positive in > the Wasm code, but we know it's always positive, for example when it's a > length. > > Example improvement in the wasm-opt output: > > ``` > (func $_newArrayLengthCheck (;426;) (param $var0 i64) (result i64) > local.get $var0 > i64.const 2147483647 > - i64.le_s > - local.get $var0 > - i64.const 0 > - i64.ge_s > - i32.and > - i32.eqz > + i64.gt_u > if > i32.const 46 > i32.const 0 > @@ -19190,13 +19172,8 @@ > i64.const 97 > i64.sub > local.tee $var3 > - i64.const 0 > - i64.ge_s > - local.get $var3 > i64.const 5 > - i64.le_s > - i32.and > - i32.eqz > + i64.gt_u > if > local.get $var0 > local.get $var6 > @@ -19810,10 +19787,10 @@ > global.get $global4 > array.new_fixed $Array<_Type> 2 > ) > ``` > > Closes #56083. > > Change-Id: Idb1dd0d0809b26be8aec3d082aa341c59e1a353d > Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/373663 > Reviewed-by: Martin Kustermann <[email protected]> > Commit-Queue: Ömer Ağacan <[email protected]> Change-Id: I822ca612e5c8d5d33ba443107b72e9f1021c5c4a Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/374000 Reviewed-by: Martin Kustermann <[email protected]> Commit-Queue: Ömer Ağacan <[email protected]>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The expression
x < 0 || x > positiveIntcan be compiled as a single unsigned comparisonx.gtU(positiveInt).Currently wasm-opt doesn't do this for us and it seems like it won't do it any time soon: WebAssembly/binaryen#6685
In a few places in the standard library we do it manually by using the
WasmI64type:sdk/sdk/lib/_internal/wasm/lib/string.dart
Line 1614 in 8f962bd
However there are many more places where we can do this optimization:
It may worth doing this in the code generator instead of relying on wasm-opt.
Note that some of the cases cannot be optimized by wasm-opt. For example it may not possible for wasm-opt to infer that
string.lengthcannot be negative. In those cases we have no option but to call the intrinsics manually.The text was updated successfully, but these errors were encountered: