Island-model parallel optimization: run competing pass orderings concurrently

[avrabe]

Context

ESA PaGMO (Parallel Global Multiobjective Optimizer) runs different optimization strategies on independent "islands" that periodically exchange best solutions. Jolt Physics uses the same "island" concept for parallel rigid body solving. Both achieve better results within the same time budget.

Problem

Loom's 12-phase optimization pipeline runs a fixed sequence of passes. But multiple valid optimization sequences exist for any WASM module — different orderings can produce significantly different code sizes and verification outcomes.

Proposal

Implement island-model parallel optimization:

1. Multiple islands: Each island runs the 12-phase pipeline with a different configuration:

   • Different pass orderings (e.g., inline-first vs. CSE-first)
   • Different aggressiveness levels (e.g., inline threshold)
   • Different loop unrolling strategies

2. Migration: After each island completes, compare results by:

   • Output binary size
   • Z3 verification success (provably correct optimizations preferred)
   • Instruction count / estimated cycle cost

3. Selection: Pick the best verified result across all islands

4. Implementation sketch:

   // Run N islands in parallel (rayon or tokio::spawn)
   let results: Vec<OptResult> = islands.par_iter().map(|config| {
       let mut pipeline = Pipeline::new(config);
       pipeline.run(module.clone())
   }).collect();
   
   // Select best verified result
   results.into_iter()
       .filter(|r| r.z3_verified)
       .min_by_key(|r| r.output_size)

5. Cost: Bounded by number of cores. Each island is independent — no synchronization during optimization. Memory cost is N copies of the IR.

Benefits

• Better optimization results with the same wall-clock time
• Naturally exploits multi-core developer machines
• Each island's result is independently Z3-verified — no compromise on correctness
• Can discover that certain pass orderings are generally better (learning)

References

• ESA PaGMO: https://github.com/esa/pagmo2
• Jolt Physics island solving: https://github.com/jrouwe/JoltPhysics

Priority

High — better optimization without compromising verification.