merge-locals pass (#1334)

This optimizes the situation described in #1331. Namely, when x is copied into y, then on subsequent gets of x we could use y instead, and vice versa, as their value is equal. Specifically, this seems to get rid of the definite overlap in the live ranges of x and y, as removing it allows coalesce-locals to merge them. The pass therefore does nothing if the live range of y ends there anyhow.

The danger here is that we may extend the live range so that it causes more conflicts with other things, so this is a heuristic, but I've tested it on every codebase I can find and it always produces a net win, even on one I saw a 0.4% reduction of code size, which surprised me.

This is a fairly slow pass, because it uses LocalGraph which isn't much optimized. This PR includes a minor optimization for it, but we should rewrite it. Meanwhile this is just enabled in -O3 and -Oz.

This PR also includes some fuzzing improvements, to better test stuff like this.

1 files changed, 5 insertions, 0 deletions

diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp
index f2463691a..89467899c 100644
--- a/src/passes/pass.cpp
+++ b/src/passes/pass.cpp
@@ -83,6 +83,7 @@ void PassRegistry::registerPasses() {
   registerPass("instrument-memory", "instrument the build with code to intercept all loads and stores", createInstrumentMemoryPass);
   registerPass("memory-packing", "packs memory into separate segments, skipping zeros", createMemoryPackingPass);
   registerPass("merge-blocks", "merges blocks to their parents", createMergeBlocksPass);
+  registerPass("merge-locals", "merges locals when beneficial", createMergeLocalsPass);
   registerPass("metrics", "reports metrics", createMetricsPass);
   registerPass("nm", "name list", createNameListPass);
   registerPass("optimize-instructions", "optimizes instruction combinations", createOptimizeInstructionsPass);
@@ -140,6 +141,10 @@ void PassRunner::addDefaultFunctionOptimizationPasses() {
   add("vacuum"); // previous pass creates garbage
   add("reorder-locals");
   add("remove-unused-brs"); // simplify-locals opens opportunities for optimizations
+  // if we are willing to work hard, also optimize copies before coalescing
+  if (options.optimizeLevel >= 3 || options.shrinkLevel >= 2) {
+    add("merge-locals"); // very slow on e.g. sqlite
+  }
   add("coalesce-locals");
   add("simplify-locals");
   add("vacuum"); // previous pass creates garbage