SuperStack: Superoptimization of Stack-Bytecode via Greedy, Constraint-Based, and SAT Techniques

Explore a groundbreaking approach to superoptimizing stack-bytecode in this 18-minute video presentation from the PLDI 2024 conference. Delve into the novel SuperStack tool, which combines greedy algorithms, constraint-based techniques, and SAT solving to optimize modern stack-based bytecode like WebAssembly and Ethereum bytecode. Learn how this innovative method significantly improves optimization gains and reduces optimization time compared to existing superoptimizers. Discover the three key components: a greedy algorithm for refining solution length bounds, a new MaxSAT representation of the optimization problem, and domain-specific constraints to reduce the search space. Gain insights from the experimental evaluation conducted on over 500,000 sequences, demonstrating the effectiveness of this combined approach in tackling the exponential complexity of superoptimization for large instruction sequences.