Advanced middle-end passes: GVN, loop unrolling, and function inlining improvements

[yudongusa]

Background

The current optimization pipeline covers basic cases (DCE, Mem2Reg, ConstProp, basic Inliner). A production middle-end requires a broader pass suite that dramatically reduces code size and improves runtime performance.

Passes to implement

Global Value Numbering (GVN)

Eliminate redundant computations by identifying instructions that compute the same value:

• Hash-based value numbering within a basic block (local GVN)
• Dominator-tree-based propagation across blocks (global GVN)
• Handles load elimination when memory is known not to have changed

Loop Unrolling

For loops with known trip counts, replicate the body N times to:

• Eliminate branch overhead
• Enable constant folding across iterations
• Expose more ILP to the backend

Implementation:

• Detect loops with constant trip counts using LoopInfo
• Clone loop body N times (configurable factor, default 4×)
• Patch exit conditions appropriately

Inliner improvements

The current inliner (inline_pass.rs) has a fixed size limit. Production inlining requires:

• Hotness-based decisions (inline functions called in loops)
• Recursive inlining with a depth limit
• Devirtualization after inlining

Acceptance criteria

• llvm-transforms/src/gvn.rs: local + global GVN, tested with at least 10 unit tests
• llvm-transforms/src/loop_unroll.rs: constant-trip-count unrolling, tested on loops 1×–16× trip count
• Inliner depth limit + recursive inlining in inline_pass.rs
• All three integrated into the O2 pipeline (see issue Optimization presets: implement -O0, -O1, -O2, -O3 pass pipelines #84)
• Benchmark showing ≥10% IR instruction count reduction on `sample.ll` at O2 vs O1

References

• LLVM GVN pass documentation
• Cooper & Torczon, "Engineering a Compiler", chapter on GVN