Massive memory growth for -O3, -O4, -Os and -Oz, in ssa-nomerge

Hi. I am planning on applying wasm-opt to my Go project as part of Jacalz/hegelmote#30. The Go WASM files are generally quite big and our toolkit is not super optimised for WASM yet so I wanted to optimise it. As I was interested in seeing which level made the most sense, I aimed to run all of the levels to see how long they take and how they affect the binary size. What I unfortunately found out was that O1 and O2 were the only ones that were usable as -O3, -O4, -Os and -Oz all seem to use memory exponentially until all 32 GB are full. I have attached the file below if you wish to try and reproduce it.

Results:

Baseline: 37.3 MB
O1: 35.7 MB, 29.85 s
O2: 35.7 MB, 32.78 secs
O3: DNF
O4: DNF
Os: DNF
Oz: DNF

Running:

wasm-opt Hegelmote.wasm --enable-bulk-memory-opt -O3 -o O3.wasm

Potentially related to #3646.

Reference file: hegelmote-wasm.zip

I think this problem likely applies to any app built with Fyne: https://github.com/fyne-io/fyne

Looking at the output with BINARYEN_PASS_DEBUG=1 in the env, ssa-nomerge is very slow, and uses over 5 GB even when using a single core. The function that happens on is github.com_yuin_goldmark_util.map.init.0. That must be a massive function but the module is difficult to print, e.g. wabt errors:

$ ~/Dev/wabt/build/wasm2wat Hegelmote.wasm --enable-all -o a.wat
error: label stack exceeds max nesting depth
0b40c8c: error: OnBlockExpr callback failed

We could add arbitrary limits somehow (as discussed in #3646) but I'm not sure what the best ones would be.

Using just -O2 might be best for now. Note that you can add more passes manually, e.g. -O2 --precompute-propagate -O2 runs one pass after -O2 (that pass is normally run only in -O3), and optimize after it as well. Other passes you can try are optimize-added-constants-propagate, merge-locals, etc., see pass.cpp which has checks like options.optimizeLevel >= 3 (-O3+).

Thanks for the detailed analysis of the issue. Nicely found regarding that function; I started digging into the package (github.com/yuin/goldmark is the markdown parser we are using in the toolkit) and it made me notice that one of the latest releases contained this commit: yuin/goldmark@6951ff3

I updated to the latest version of the dependency and all of the build levels in wasm-opt now work as expected again. Should this be closed then or does it perhaps make sense to fix the memory leak or whatever it was? It made my computer crash last time so I kind of feel like it is something that shouldn’t be happening.

Updated binary for reference: hegelmote-wasm-fixed.zip

Thanks for the update, good to know things work now.

I agree things shouldn't crash like that, but I'm not sure what we can do. The problem isn't a memory leak, but very large memory usage - we could put some arbitrary limit, but other people might have more than enough memory and not want to be limited that way.

Ideally the OS would not crash on an OOM like this, but as a Linux user I've seen that happen now and then, unfortunately, in various apps...

Let's keep this open for more ideas here. I'll rename.

Happy to help. Maybe I should clarify that it wasn't directly a crash but more like the oom-daemon (or whatever Fedora uses) not killing it so everything grinded to a halt as more and more swap space was requested. I think I saw 8GB swap being used on top of the 32GB main memory :)

I agree that setting a limit on memory usage is a bad idea. If it isn't a memory leak, is it an algorithm that is O(n^2) in memory complexity or something like that? I feel like using 32GB+ to parse a ~37MB file is a bit excessive how ever you look at it. Perhaps there is a way to rewrite that pass to not allocate as much memory?

Yeah, I've seen similar OOM behavior on Ubuntu, sometimes forcing a reboot...

I suspect it is O(n^2) in the worst case, yes. The pass computes the "influences" of sets on gets, that is, which gets read from which set. Commonly there are few such interactions, but if there are many, it is quadratic.

In terms of raw numbers, that function has 6,125 locals, 46,041 gets, and 24,492 sets, so it is a very extreme case...

In theory the pass could be rewritten to work "online", and not compute all locals first, but it does consider interactions as well (merges) so I'm not sure offhand how. But let's keep the issue open for more investigation.

A point of interest:

$ bin/wasm-opt ~/Downloads/hegelmote-wasm/Hegelmote.wasm --extract-function=github.com_yuin_goldmark_util.map.init.0 --metrics --no-validation -O1 --metrics --ssa-nomerge --metrics
extracting github.com_yuin_goldmark_util.map.init.0
Metrics
total
 [exports]      : 1       
 [funcs]        : 1       
 [globals]      : 2       
 [imports]      : 16943   
 [memories]     : 1       
 [memory-data]  : 17782489
 [tables]       : 0       
 [tags]         : 0       
 [total]        : 323974  
 [vars]         : 6125    
 Binary         : 10719   
 Block          : 15308   
 Break          : 6122    
 Call           : 6122    
 Const          : 132271  
 GlobalGet      : 6124    
 GlobalSet      : 4595    
 If             : 3061    
 Load           : 13775   
 LocalGet       : 46041   
 LocalSet       : 24492   
 Loop           : 1       
 Return         : 1       
 Store          : 23079   
 Switch         : 1       
 Unary          : 32261   
 Unreachable    : 1       
Metrics
total
 [exports]      : 1       
 [funcs]        : 1       
 [globals]      : 1             -1
 [imports]      : 7         -16936
 [memories]     : 1       
 [memory-data]  : 17782470     -19
 [tables]       : 0       
 [tags]         : 0       
 [total]        : 293359    -30615
 [vars]         : 2          -6123
 Binary         : 10719   
 Block          : 9186       -6122
 Break          : 6122    
 Call           : 6122    
 Const          : 132271  
 GlobalGet      : 6123          -1
 GlobalSet      : 4595    
 If             : 3061    
 Load           : 13775   
 LocalGet       : 41450      -4591
 LocalSet       : 22959      -1533
 Loop           : 1       
 Return         : 1       
 Store          : 23079   
 Switch         : 1       
 Unary          : 13893     -18368
 Unreachable    : 1

That focuses on this one function ("extracting" it) by turning the rest into imports. -O1 then removes almost all vars: only 2 remain, 6,123 are removed, but we do not remove that many gets and sets. And the speed on the later ssa-nomerge is no better. So the problem is not the number of locals, but that there are very many gets and sets, with lots of overlap between them, in a huge CFG (10K blocks, 3K ifs).

This inefficiency makes my wasm optimize for more than 10 minuets... this patch fixed this issue for me and produced byte-for-byte identical wasm (same hash) as pre-patch.

diff --git a/src/ir/LocalGraph.cpp b/src/ir/LocalGraph.cpp
index b059fb6fd..f2c549006 100644
--- a/src/ir/LocalGraph.cpp
+++ b/src/ir/LocalGraph.cpp
@@ -118,10 +118,12 @@ struct LocalGraphFlower
     // scanning them linearly is efficient, avoiding hash computations (while
     // in Info, it's convenient to have a map so we can assign them easily,
     // where the last one seen overwrites the previous; and, we do that O(1)).
-    // TODO: If we also stored gets here then we could use the sets for a get
-    //       we already computed, for a get that we are computing, and stop that
-    //       part of the flow.
     std::vector<std::pair<Index, LocalSet*>> lastSets;
+
+    // Completed queries at the start of this block. If the block has no set
+    // for an index, these also describe its outgoing value. Reuse them instead
+    // of repeatedly traversing the same predecessors for later queries.
+    std::vector<std::pair<Index, LocalGet*>> computedGets;
   };
 
   // All the flow blocks.
@@ -285,12 +287,23 @@ struct LocalGraphFlower
                                       });
           if (lastSet != pred->lastSets.end()) {
             // There is a set here, apply it, and stop the flow.
-            // TODO: If we find a computed get, apply its sets and stop? That
-            //       could help but it requires more info on FlowBlock.
             for (auto* get : gets) {
               getSetsMap[get].insert(lastSet->second);
             }
           } else {
+            auto computed = std::find_if(
+              pred->computedGets.begin(),
+              pred->computedGets.end(),
+              [&](const auto& value) { return value.first == index; });
+            if (computed != pred->computedGets.end()) {
+              const auto& sets = getSetsMap.at(computed->second);
+              for (auto* get : gets) {
+                for (auto* set : sets) {
+                  getSetsMap[get].insert(set);
+                }
+              }
+              continue;
+            }
             // Keep on flowing.
             work.push_back(pred);
           }
@@ -300,6 +313,11 @@ struct LocalGraphFlower
 
     // Bump the current iteration for the next time we are called.
     currentIteration++;
+
+    // Publish only after the entire search has finished: a loop may revisit
+    // this block while its query is still incomplete.
+    getSetsMap.try_emplace(gets[0]);
+    block->computedGets.emplace_back(index, gets[0]);
   }
 
   // When the LocalGraph is in lazy mode we do not compute all of getSetsMap

@jkbz64

@jkbz64 Looks interesting, feel free to open a PR with that for CI to test it, and more detailed discussion.

Navigation Menu

Repository navigation

Massive memory growth for -O3, -O4, -Os and -Oz, in ssa-nomerge #7644

Results:

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Massive memory growth for -O3, -O4, -Os and -Oz, in ssa-nomerge #7644

Description

Results:

Activity

Jacalz commented on Jun 8, 2025

kripken commented on Jun 9, 2025

Jacalz commented on Jun 9, 2025

kripken commented on Jun 9, 2025

Jacalz commented on Jun 9, 2025

kripken commented on Jun 10, 2025

kripken commented on Jun 10, 2025

jkbz64 commented on Sep 29, 2026

kripken commented on Sep 29, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions