Branch Simplification (RemoveUnusedBrs)

[avrabe]

Goal

Remove unreachable branches, fold constant conditions, simplify control flow.

Why High-Impact

• 30-40% of code has simplifiable branches
• Guard patterns and error handling create many constant-folded branches
• Enables block merging and further DCE
• LOOM currently has NO control flow support - major gap

Tasks

• Implement constant condition folding for br_if
• Remove branches that are never taken
• Remove branches that are always taken (replace with unconditional br)
• Simplify branch tables with constant indices
• Remove unreachable code after unconditional branches
• Add tests for branch optimization scenarios

Dependencies

• Requires Control Flow Representation in ISLE #12 (Control Flow Representation)

Implementation Complexity

Medium-High

Priority

CRITICAL

Estimated Time

2-3 weeks (after control flow support)

References

• wasm-opt: remove-unused-brs pass

[avrabe]

✅ Branch Simplification Implemented!

What Was Built

Implemented Phase 1 of branch simplification: constant branch folding and control flow simplification.

Key Optimizations

1. Constant br_if Folding

   • br_if with constant 1 → unconditional br
   • br_if with constant 0 → removed entirely

2. Constant If Folding

   • if with constant condition → select appropriate branch
   • Eliminates dead branches at compile time

3. Nested Simplification

   • Recursively simplifies nested constant conditions
   • Example: nested ifs with constants → single constant result

4. Nop Removal

   • Removes all nop instructions during simplification

Implementation Details

• Algorithm: Pattern-based lookahead with O(n) complexity
• Integration: Runs between constant folding and DCE in pipeline
• Recursive: Handles deeply nested control structures
• Test Coverage: 6 comprehensive tests, all passing (27/27 total)

Files Changed

• loom-core/src/lib.rs: Added simplify_branches() optimization pass
• loom-cli/src/main.rs: Integrated into optimization pipeline
• docs/BRANCH_SIMPLIFICATION_DESIGN.md: Full design documentation
• tests/fixtures/branch_simplification_test.wat: Test fixtures

Future Enhancements (Phase 2 & 3)

Documented in design doc:

• Redundant branch removal (branches to natural flow)
• Branch merging (combine multiple br_if to same target)
• EqZ optimization (flip if/else to remove eqz)
• Branch table simplification

Commit

Commit f3f6533