Make compilation faster :rocket:

[kripken]

I did some investigation on the speed of compilation. This is getting important because of things like j2cl output which is a 50MB real-world file.

Slowest passes: (in -O3; note that some passes run more than once)

[PassRunner]   running pass: precompute-propagate...           14.23460 seconds.
[PassRunner]   running pass: dae...                            10.91160 seconds.
[PassRunner]   running pass: heap2local...                     10.44350 seconds.
[PassRunner]   running pass: precompute-propagate...            9.07261 seconds.
[PassRunner]   running pass: inlining...                        8.02837 seconds.
[PassRunner]   running pass: once-reduction...                  8.02484 seconds.
[PassRunner]   running pass: vacuum...                          5.16162 seconds.
[PassRunner]   running pass: vacuum...                          3.64088 seconds.
[PassRunner]   running pass: vacuum...                          3.58191 seconds.
[PassRunner]   running pass: vacuum...                          3.61897 seconds.

perf reports almost 15% of time is spent in malloc/free methods - quite a lot. I counted how many mallocs (note: not the size of them) are done in each pass, here are the heaviest (note: timings here include the overhead of counting mallocs atomically among threads, so those matter less):

    once-reduction...                 9.51466 seconds.  141558196 mallocs. 
    precompute-propagate...           14.7426 seconds.   61611533 mallocs. 
    dae...                            11.3789 seconds.   53792948 mallocs. 
    precompute-propagate...           9.69919 seconds.   39531493 mallocs. 
    heap2local...                     10.5116 seconds.   38582302 mallocs. 
    local-cse...                      4.70765 seconds.   33454468 mallocs. 
    cfp...                            2.43619 seconds.   32292682 mallocs. 
    ssa-nomerge...                    4.92099 seconds.   26378117 mallocs. 
    simplify-locals-nostructure...    6.03281 seconds.   22663794 mallocs. 
    vacuum...                         5.10813 seconds.   23880789 mallocs. 
    inlining...                       107.781 seconds.   20940365 mallocs. 
    dce...                            3.84722 seconds.   20025273 mallocs. 
    local-subtyping...                3.44374 seconds.   19067529 mallocs. 

and vacuum runs 3 more times:

    vacuum...                         3.71648 seconds.   16648663 mallocs. 
    vacuum...                         3.86917 seconds.   16302767 mallocs. 
    vacuum...                         3.89855 seconds.   16162915 mallocs. 

Help in speeding things up would be very welcome!

[MaxGraey]

I think precompute-propagate could be speedup also if interpreter will avoid exceptions: #2917 (comment) and uses monadic Expect / Result instead

[MaxGraey]

Another variant is rewrite simple constant propagation algorithm to Sparse Conditional Constant Propagation (SCCP pass in LLVM) which should be mush faster

[kripken]

@MaxGraey Good idea about precompute-propagate. I checked that now. Running precompute instead (which still uses exceptions, but avoids the propagation using LocalGraph) is just 2-3 seconds. So looks like exceptions are not a significant factor there.

[andrewevstyukhin]

Hi there.

I have some statistics for 500MB wasm under Windows 10 (sadly 2 times slower than Linux).
-Os -flto -fomit-frame-pointer

[PassRunner] running pass: duplicate-function-elimination... 32.0065 seconds.
[PassRunner] running pass: simplify-locals-nostructure... 31.395 seconds.
[PassRunner] running pass: simplify-locals... 34.4849 seconds.
[PassRunner] running pass: dae-optimizing... 33.4361 seconds.
[PassRunner] running pass: inlining-optimizing... 48.7857 seconds.
[PassRunner] running pass: optimize-stack-ir... 27.0179 seconds.
[PassRunner] running pass: asyncify... 1022.96 seconds.
[PassRunner] passes took 1428.02 seconds.

Most passes run as single threaded...

-flto=thin occasionally breaks execution

wasm-ld: warning: function signature mismatch: ...
defined as () -> void in ...
defined as (i32, i32, i32, i32, i32) -> void in lto.tmp

-Os -flto=thin -fomit-frame-pointer

[PassRunner] running pass: duplicate-function-elimination... 32.5 seconds.
[PassRunner] running pass: simplify-locals-nostructure... 37.1433 seconds.
[PassRunner] running pass: simplify-locals... 42.461 seconds.
[PassRunner] running pass: dae-optimizing... 116.364 seconds.
[PassRunner] running pass: inlining-optimizing... 67.1076 seconds.
[PassRunner] running pass: optimize-stack-ir... 32.2354 seconds.
[PassRunner] running pass: asyncify... 1547.16 seconds.
[PassRunner] passes took 2106.44 seconds.

[kripken]

Thanks for the data @andrewevstyukhin , looks like by far the largest factor is asyncify:

[PassRunner] running pass: asyncify... 1022.96 seconds.

I think that is because it flattens the IR, which is very costly by itself, does the transform, and then optimizes after to unflatten it. Asyncify will be replaced by stack switching eventually, so this will get resolved that way. But it could be improved a lot meanwhile, I think - currently Flatten generates many more locals than it needs to.

[andrewevstyukhin]

Yes, asyncify is heavy. Also it doubles wasm size but not so large in entropy:

1.39.7: wasm-ld 45 357 52 (8 541 334 in 7z) -> wasm-opt 67 428 723 (8 579 733 in 7z)
2.0.14: wasm-ld 44 989 373 (8 374 314 in 7z) -> wasm-opt 69 631 668 (8 717 509 in 7z)

Best time is 481.723 seconds (asyncify 185.695 seconds, 39%).

C++ assertions are really hard for recent versions in "release" builds:
1.39.7: passes took 627.178 seconds (running pass: asyncify... 238.017 seconds)
2.0.14: passes took 1428.02 seconds (running pass: asyncify... 1022.96 seconds)

[andrewevstyukhin]

asyncify: I wonder can we make an attribute to mark functions in C++ code additionally to ASYNCIFY_ADD?
To not write extern "C" and be more handy than manual ASYNCIFY_ADVISE.

[asyncify] invoke_iiii is an import that can change the state
[asyncify] std::__2::__function::__value_func<void\20\28bool\29>::~__value_func\28\29 can change the state due to initial scan
[asyncify] bool\20boost::spirit::karma::string_inserterboost::spirit::unused_type\2c\20boost::spirit::unused_type::call<boost::spirit::karma::detail::output_iterator<std::__2::back_insert_iterator<std::__2::basic_string<char\2c\20std::__2::char_traits\2c\20std::2::allocator\20>\20>\2c\20mpl::int<0>\2c\20boost::spirit::unused_type>\2c\20char\20const*>\28boost::spirit::karma::detail::output_iterator<std::__2::back_insert_iterator<std::__2::basic_string<char\2c\20std::__2::char_traits\2c\20std::2::allocator\20>\20>\2c\20mpl::int<0>\2c\20boost::spirit::unused_type>&\2c\20char\20const*\29 can change the state due to

I can try to make an empty function with EMSCRIPTEN_KEEPALIVE and include function in ASYNCIFY_ADD then add calls...

Found that -s ASYNCIFY_ONLY=['*'] breaks execution at legalstub$dynCall_iij

[kripken]

@andrewevstyukhin I know there has been some discussion on the LLVM side about adding a way to annotate things in the source so that they show up in a wasm custom section. We could use that for asyncify, and also things like noinline. But I don't think anyone is working on it atm. I don't follow the LLVM side super-closely, though.