CoalesceLocals N^2 memory usages of "copies" (affects AddressSanitizer -O3 builds on large wasm file)

Hi,

I've found that wasm2js is getting terminated during execution,
After re-compiling wasm2js with address sanitizer suport I've got follwing report.
The original wasm was compiled with -O3 -g2 -fsanitize=address (so, wasm with ASAN).

The iteration speed over this issue is pretty slow, getting asan report took 90min of execution, now I'm tryign to get to run with debugger. Wat file is 1GiB size, which makes challenging to process it

While digging through code I've found that this might be already a suspected flaw:
https://github.com/WebAssembly/binaryen/blob/760a51bd15a51f02bc1c75087a9cd9e11b9f27bb/src/cfg/liveness-traversal.h#L174-L176

=================================================================
==431669==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x7f3d3f4fddd9 at pc 0x000000e33332 bp 0x7f40353253b0 sp 0x7f40353253a0
READ of size 1 at 0x7f3d3f4fddd9 thread T5
    #0 0xe33331 in wasm::LivenessWalker<wasm::CoalesceLocals, wasm::Visitor<wasm::CoalesceLocals, void> >::getCopies(unsigned int, unsigned int) (/home/piotr/Projects/binaryen/bin/wasm2js+0xe33331)
    #1 0xe1e0ac in wasm::CoalesceLocals::pickIndicesFromOrder(std::vector<unsigned int, std::allocator<unsigned int> >&, std::vector<unsigned int, std::allocator<unsigned int> >&, unsigned int&) /home/piotr/Projects/binaryen/src/passes/CoalesceLocals.cpp:292
    #2 0xe1ecaf in wasm::CoalesceLocals::pickIndices(std::vector<unsigned int, std::allocator<unsigned int> >&) /home/piotr/Projects/binaryen/src/passes/CoalesceLocals.cpp:331
    #3 0xe1bf28 in wasm::CoalesceLocals::doWalkFunction(wasm::Function*) /home/piotr/Projects/binaryen/src/passes/CoalesceLocals.cpp:102
    #4 0xe5d9e5 in wasm::Walker<wasm::CoalesceLocals, wasm::Visitor<wasm::CoalesceLocals, void> >::walkFunction(wasm::Function*) /home/piotr/Projects/binaryen/src/wasm-traversal.h:558
    #5 0xe5d8ae in wasm::WalkerPass<wasm::LivenessWalker<wasm::CoalesceLocals, wasm::Visitor<wasm::CoalesceLocals, void> > >::runOnFunction(wasm::PassRunner*, wasm::Module*, wasm::Function*) /home/piotr/Projects/binaryen/src/pass.h:338
    #6 0xd76237 in wasm::PassRunner::runPassOnFunction(wasm::Pass*, wasm::Function*) /home/piotr/Projects/binaryen/src/passes/pass.cpp:720
    #7 0xd73dbe in operator() /home/piotr/Projects/binaryen/src/passes/pass.cpp:564
    #8 0xd76e75 in __invoke_impl<wasm::ThreadWorkState, wasm::PassRunner::run()::<lambda()>::<lambda()>&> /usr/include/c++/10/bits/invoke.h:60
    #9 0xd76d16 in __invoke_r<wasm::ThreadWorkState, wasm::PassRunner::run()::<lambda()>::<lambda()>&> /usr/include/c++/10/bits/invoke.h:141
    #10 0xd76a95 in _M_invoke /usr/include/c++/10/bits/std_function.h:291
    #11 0x1664223 in std::function<wasm::ThreadWorkState ()>::operator()() const /usr/include/c++/10/bits/std_function.h:622
    #12 0x166249b in wasm::Thread::mainLoop(void*) /home/piotr/Projects/binaryen/src/support/threads.cpp:86
    #13 0x166872a in void std::__invoke_impl<void, void (*)(void*), wasm::Thread*>(std::__invoke_other, void (*&&)(void*), wasm::Thread*&&) /usr/include/c++/10/bits/invoke.h:60
    #14 0x1668648 in std::__invoke_result<void (*)(void*), wasm::Thread*>::type std::__invoke<void (*)(void*), wasm::Thread*>(void (*&&)(void*), wasm::Thread*&&) /usr/include/c++/10/bits/invoke.h:95
    #15 0x16685b8 in void std::thread::_Invoker<std::tuple<void (*)(void*), wasm::Thread*> >::_M_invoke<0ul, 1ul>(std::_Index_tuple<0ul, 1ul>) /usr/include/c++/10/thread:264
    #16 0x1668571 in std::thread::_Invoker<std::tuple<void (*)(void*), wasm::Thread*> >::operator()() /usr/include/c++/10/thread:271
    #17 0x1668555 in std::thread::_State_impl<std::thread::_Invoker<std::tuple<void (*)(void*), wasm::Thread*> > >::_M_run() /usr/include/c++/10/thread:215
    #18 0x7f4042cfaad3  (/lib64/libstdc++.so.6+0xd8ad3)
    #19 0x7f4042aa9431 in start_thread (/lib64/libpthread.so.0+0x9431)
    #20 0x7f40429d76d2 in __clone (/lib64/libc.so.6+0x1016d2)

0x7f3d3f4fddd9 is located 0 bytes to the right of 903644633-byte region [0x7f3d09735800,0x7f3d3f4fddd9)
allocated by thread T5 here:
    #0 0x7f4042ec4067 in operator new(unsigned long) (/lib64/libasan.so.6+0xb2067)
    #1 0xe46b80 in __gnu_cxx::new_allocator<unsigned char>::allocate(unsigned long, void const*) /usr/include/c++/10/ext/new_allocator.h:115
    #2 0xe42cf4 in std::allocator_traits<std::allocator<unsigned char> >::allocate(std::allocator<unsigned char>&, unsigned long) /usr/include/c++/10/bits/alloc_traits.h:460
    #3 0xe3eaa5 in std::_Vector_base<unsigned char, std::allocator<unsigned char> >::_M_allocate(unsigned long) /usr/include/c++/10/bits/stl_vector.h:346
    #4 0xe3950d in std::vector<unsigned char, std::allocator<unsigned char> >::_M_default_append(unsigned long) (/home/piotr/Projects/binaryen/bin/wasm2js+0xe3950d)
    #5 0xe32d4c in std::vector<unsigned char, std::allocator<unsigned char> >::resize(unsigned long) /usr/include/c++/10/bits/stl_vector.h:940
    #6 0xe311ff in wasm::LivenessWalker<wasm::CoalesceLocals, wasm::Visitor<wasm::CoalesceLocals, void> >::doWalkFunction(wasm::Function*) (/home/piotr/Projects/binaryen/bin/wasm2js+0xe311ff)
    #7 0xe1be96 in wasm::CoalesceLocals::doWalkFunction(wasm::Function*) /home/piotr/Projects/binaryen/src/passes/CoalesceLocals.cpp:95
    #8 0xe5d9e5 in wasm::Walker<wasm::CoalesceLocals, wasm::Visitor<wasm::CoalesceLocals, void> >::walkFunction(wasm::Function*) /home/piotr/Projects/binaryen/src/wasm-traversal.h:558
    #9 0xe5d8ae in wasm::WalkerPass<wasm::LivenessWalker<wasm::CoalesceLocals, wasm::Visitor<wasm::CoalesceLocals, void> > >::runOnFunction(wasm::PassRunner*, wasm::Module*, wasm::Function*) /home/piotr/Projects/binaryen/src/pass.h:338
    #10 0xd76237 in wasm::PassRunner::runPassOnFunction(wasm::Pass*, wasm::Function*) /home/piotr/Projects/binaryen/src/passes/pass.cpp:720
    #11 0xd73dbe in operator() /home/piotr/Projects/binaryen/src/passes/pass.cpp:564
    #12 0xd76e75 in __invoke_impl<wasm::ThreadWorkState, wasm::PassRunner::run()::<lambda()>::<lambda()>&> /usr/include/c++/10/bits/invoke.h:60
    #13 0xd76d16 in __invoke_r<wasm::ThreadWorkState, wasm::PassRunner::run()::<lambda()>::<lambda()>&> /usr/include/c++/10/bits/invoke.h:141
    #14 0xd76a95 in _M_invoke /usr/include/c++/10/bits/std_function.h:291
    #15 0x1664223 in std::function<wasm::ThreadWorkState ()>::operator()() const /usr/include/c++/10/bits/std_function.h:622
    #16 0x166249b in wasm::Thread::mainLoop(void*) /home/piotr/Projects/binaryen/src/support/threads.cpp:86
    #17 0x166872a in void std::__invoke_impl<void, void (*)(void*), wasm::Thread*>(std::__invoke_other, void (*&&)(void*), wasm::Thread*&&) /usr/include/c++/10/bits/invoke.h:60
    #18 0x1668648 in std::__invoke_result<void (*)(void*), wasm::Thread*>::type std::__invoke<void (*)(void*), wasm::Thread*>(void (*&&)(void*), wasm::Thread*&&) /usr/include/c++/10/bits/invoke.h:95
    #19 0x16685b8 in void std::thread::_Invoker<std::tuple<void (*)(void*), wasm::Thread*> >::_M_invoke<0ul, 1ul>(std::_Index_tuple<0ul, 1ul>) /usr/include/c++/10/thread:264
    #20 0x1668571 in std::thread::_Invoker<std::tuple<void (*)(void*), wasm::Thread*> >::operator()() /usr/include/c++/10/thread:271
    #21 0x1668555 in std::thread::_State_impl<std::thread::_Invoker<std::tuple<void (*)(void*), wasm::Thread*> > >::_M_run() /usr/include/c++/10/thread:215
    #22 0x7f4042cfaad3  (/lib64/libstdc++.so.6+0xd8ad3)

Thread T5 created by T0 here:
    #0 0x7f4042e69be5 in __interceptor_pthread_create (/lib64/libasan.so.6+0x57be5)
    #1 0x7f4042cfad98 in std::thread::_M_start_thread(std::unique_ptr<std::thread::_State, std::default_delete<std::thread::_State> >, void (*)()) (/lib64/libstdc++.so.6+0xd8d98)
    #2 0x1663fdc in std::unique_ptr<std::thread, std::default_delete<std::thread> > wasm::make_unique<std::thread, void (&)(void*), wasm::Thread*>(void (&)(void*), wasm::Thread*&&) /home/piotr/Projects/binaryen/src/support/utilities.h:57
    #3 0x1662014 in wasm::Thread::Thread(wasm::ThreadPool*) /home/piotr/Projects/binaryen/src/support/threads.cpp:52
    #4 0x166440b in std::unique_ptr<wasm::Thread, std::default_delete<wasm::Thread> > wasm::make_unique<wasm::Thread, wasm::ThreadPool*>(wasm::ThreadPool*&&) /home/piotr/Projects/binaryen/src/support/utilities.h:57
    #5 0x1662920 in wasm::ThreadPool::initialize(unsigned long) /home/piotr/Projects/binaryen/src/support/threads.cpp:127
    #6 0x1662ec7 in wasm::ThreadPool::get() /home/piotr/Projects/binaryen/src/support/threads.cpp:160
    #7 0xd73fc8 in operator() /home/piotr/Projects/binaryen/src/passes/pass.cpp:548
    #8 0xd7575c in wasm::PassRunner::run() /home/piotr/Projects/binaryen/src/passes/pass.cpp:585
    #9 0x158f05a in wasm::WalkerPass<wasm::PostWalker<wasm::FunctionValidator, wasm::Visitor<wasm::FunctionValidator, void> > >::run(wasm::PassRunner*, wasm::Module*) /home/piotr/Projects/binaryen/src/pass.h:325
    #10 0x157d59f in wasm::WasmValidator::validate(wasm::Module&, unsigned int) /home/piotr/Projects/binaryen/src/wasm/wasm-validator.cpp:2145
    #11 0xc817ea in main /home/piotr/Projects/binaryen/src/tools/wasm2js.cpp:912
    #12 0x7f40428fd081 in __libc_start_main (/lib64/libc.so.6+0x27081)

SUMMARY: AddressSanitizer: heap-buffer-overflow (/home/piotr/Projects/binaryen/bin/wasm2js+0xe33331) in wasm::LivenessWalker<wasm::CoalesceLocals, wasm::Visitor<wasm::CoalesceLocals, void> >::getCopies(unsigned int, unsigned int)
Shadow bytes around the buggy address:
  0x0fe827e97b60: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fe827e97b70: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fe827e97b80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fe827e97b90: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fe827e97ba0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0fe827e97bb0: 00 00 00 00 00 00 00 00 00 00 00[01]fa fa fa fa
  0x0fe827e97bc0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0fe827e97bd0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0fe827e97be0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0fe827e97bf0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0fe827e97c00: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==431669==ABORTING

Start with the suspected copies logic in cfg/liveness-traversal.h at lines 174-176, then trace the callers in src/passes/CoalesceLocals.cpp around lines 95, 292, and 331. Use the reported wasm2js AddressSanitizer failure on the large wasm input to investigate the out-of-bounds access and excessive copies; done means the input no longer triggers the reported failure or N^2 memory usage.