Add optimization from `x < 0 || x > POSITIVE_CONST` to `unsigned(x) > POSITIVE_CONST`

[i582]

Hey, I read the pinned issue carefully and probably this optimization is not really needed with LLVM, but I find this task simple enough to learn more about binaryen. If you think this PR is completely useless, I understand, anyway I learned a lot about binaryen while doing it :)

~~I also need help, how do I compare two expressions for equivalence?~~

Fixes #6685

[i582]

Thanks for the feedback! I'll check the fuzzing tests as well

[i582]

@kripken not sure, but looks like a bug in the fuzzer (as stated in the message by fuzzer :D). I rebuilt wasm-opt without my changes and got this output as well:

Fuzzer output:

./scripts/fuzz_opt.py --filter "cmp.wat" 2809011524347242031
/Users/petrmakhnev/binaryen/bin/wasm-opt --print-features /Users/petrmakhnev/binaryen/test/hello_world.wat --all-features --disable-fp16
warning: no output file specified, not emitting output
FEATURE_DISABLE_FLAGS: ['--disable-threads', '--disable-mutable-globals', '--disable-nontrapping-float-to-int', '--disable-simd', '--disable-bulk-memory', '--disable-sign-ext', '--disable-exception-handling', '--disable-tail-call', '--disable-reference-types', '--disable-multivalue', '--disable-gc', '--disable-memory64', '--disable-relaxed-simd', '--disable-extended-const', '--disable-strings', '--disable-multimemory', '--disable-typed-continuations', '--disable-shared-everything']

<<< fuzz_opt.py >>>

checking a single given seed 2809011524347242031
- Important provided initial contents:

- Recently added or modified initial contents (automatically selected: within last 30 days):
  lit/basic/f16.wast
  lit/merge/sourcemap.wat
  lit/metadce/sourcemap.wat
  lit/parse-bad-identifier.wast
  lit/passes/gsi.wast
  lit/passes/gufa-refs.wast
  lit/passes/heap2local.wast
  lit/passes/inlining-eh-legacy.wast
  lit/passes/inlining-optimizing_optimize-level=3.wast
  lit/passes/inlining-unreachable.wast
  lit/passes/inlining_all-features.wast
  lit/passes/inlining_enable-tail-call.wast
  lit/passes/inlining_optimize-level=3.wast
  lit/passes/inlining_source-maps.wast
  lit/passes/inlining_splitting.wast
  lit/passes/inlining_splitting_basics.wast
  lit/passes/local-subtyping.wast
  lit/passes/merge-blocks.wast
  lit/passes/merge-blocks_names.wast
  lit/passes/monomorphize-drop.wast
  lit/passes/no-inline-monomorphize-inlining.wast
  lit/passes/no-inline.wast
  lit/passes/optimize-instructions-cmps.wast
  lit/passes/precompute-ref-func.wast
  lit/passes/remove-unused-brs-eh.wast
  lit/passes/remove-unused-brs-gc.wast
  lit/passes/string-gathering.wast
  lit/passes/string-lowering-imports.wast
  lit/passes/string-lowering-instructions.wast
  lit/passes/unsubtyping.wast
  lit/passes/vacuum-eh.wast
  lit/source-map.wast
  lit/wasm-split/basic.wast
  lit/wasm-split/initial-table-used.wast
  lit/wasm-split/initial-table.wast
  lit/wasm-split/jspi-secondary-export.wast
  lit/wasm-split/jspi.wast
  lit/wasm-split/minimized-exports.wast
  lit/wasm-split/module-names.wast
  lit/wasm-split/multi-split.wast
  lit/wasm-split/name-collision.wast
  lit/wasm-split/no-placeholders.wast
  lit/wasm-split/passive.wast
  lit/wasm-split/profile-guided.wast
  lit/wasm-split/ref.func.wast
  lit/wasm-split/segments.wast
  spec/f16.wast


ITERATION: 1 seed: 2809011524347242031 size: 43469 (mean: 43469.0, stddev: 0.0) speed: 28728.109589041094 iters/sec,  0.0 wasm_bytes/iter

randomized pass debug: 
randomized feature opts: 
  --all-features
  --disable-fp16
  --disable-nontrapping-float-to-int
  --disable-sign-ext
  --disable-memory64
  --disable-strings
  --disable-typed-continuations
  --disable-shared-everything
randomized settings (NaNs, OOB, legalize): False False False
!
-----------------------------------------
Exception:
  File "/Users/petrmakhnev/binaryen/./scripts/fuzz_opt.py", line 1780, in <module>
    total_wasm_size += test_one(raw_input_data, given_wasm)
  File "/Users/petrmakhnev/binaryen/./scripts/fuzz_opt.py", line 1437, in test_one
    pick_initial_contents()
  File "/Users/petrmakhnev/binaryen/./scripts/fuzz_opt.py", line 373, in pick_initial_contents
    test_name = random.choice(all_tests)
  File "/Applications/Xcode.app/Contents/Developer/Library/Frameworks/Python3.framework/Versions/3.9/lib/python3.9/random.py", line 346, in choice
    return seq[self._randbelow(len(seq))]
-----------------------------------------
!
list index out of range
================================================================================
You found a bug in the fuzzer itself! It failed to generate a valid wasm file
from the random input. Please report it with

  seed: 2809011524347242031

and the exact version of Binaryen you found it on, plus the exact Python
version (hopefully deterministic random numbers will be identical).

You can run that testcase again with "fuzz_opt.py 2809011524347242031"

(We can't automatically reduce this testcase since we can only run the reducer
on valid wasm files.)
================================================================================
                
(finished running seed 2809011524347242031, see error above)

Test file:

(module
 (global $g (mut i32) (i32.const 0))

 (func $cmp (param $0 i32) (result i32)
  (i32.or
   (i32.lt_s
    (local.get $0)
    (i32.const 0)
   )
   (i32.gt_s
    (local.get $0)
    (i32.const 255)
   )
  )
 )

 (func $cmp2 (param $0 i32) (result i32)
  (i32.or
   (i32.lt_s
    (local.get $0)
    (i32.const 0)
   )
   (i32.gt_s
    (local.get $0)
    (i32.const -255)
   )
  )
 )

 (func $cmp3 (param $0 i32) (result i32)
  (i32.or
   (i32.lt_s
    (local.get $0)
    (i32.const 10)
   )
   (i32.gt_s
    (local.get $0)
    (i32.const 255)
   )
  )
 )

 (func $set_global_and_return (param $x i32) (result i32)
   (global.set $g (local.get $x))
   (local.get $x)
 )

 (func $cmp4 (result i32)
  (i32.or
   (i32.lt_s
    (call $set_global_and_return (i32.const 10))
    (i32.const 0)
   )
   (i32.gt_s
    (call $set_global_and_return (i32.const 10))
    (i32.const 255)
   )
  )
 )

 (func $cmp5 (param $0 i32) (param $1 i32) (result i32)
  (i32.or
   (i32.lt_s
    (local.get $0)
    (i32.const 0)
   )
   (i32.gt_s
    (local.get $1)
    (i32.const 255)
   )
  )
 )

 (func $cmp6 (param $0 i32) (param $1 i32) (result i32)
  (i32.or
   (i32.lt_s
    (local.get $0)
    (i32.const 0)
   )
   (i32.gt_s
    (local.get $0)
    (local.get $1)
   )
  )
 )
)

Python 3.12.6 (main, Sep 6 2024, 19:03:47) [Clang 15.0.0 (clang-1500.1.0.2.5)] on darwin Binaryen at defe0ac9d981c1cf34a48af3823348297ca85ac6

[i582]

But most likely the problem is on my side, since even (module) causes the fuzzer to crash with a similar output

[kripken]

Strange about that fuzzer error. You might need to debug that line test_name = random.choice(all_tests) to see why all_tests is empty (I assume the error means it is empty and it can't make a choice from it). That list should contain the files mentioned in that logging (like lit/passes/merge-blocks.wast) but maybe there is a lowercase/uppercase issue, or something else? The script has not been tested much outside of Linux, I'm afraid, and it looks like you're on MacOS, so that might be a factor somehow.