solar_codegen/
pass.rs

1//! Pass infrastructure for MIR transformations and analyses.
2//!
3//! Inspired by LLVM/MLIR pass infrastructure:
4//! - **Analysis passes** ([`AnalysisPass`]) are read-only and produce a cached result. They take
5//!   `&Function` and store their result in [`AnalysisManager`].
6//! - **Module passes** ([`ModulePass`]) modify the IR at module scope. Function-local passes can
7//!   implement [`FunctionPass`] and are automatically applied to each function.
8//!
9//! # Usage
10//!
11//! ```ignore
12//! // Read-only analysis pipeline (codegen):
13//! let mut am = AnalysisManager::new();
14//! let liveness = am.get_or_compute(&LivenessAnalysis, &func);
15//!
16//! // Transform pipeline:
17//! let mut pm = PassManager::new();
18//! pm.add_pass(Box::new(DcePass));
19//! let changed = pm.run(&mut module).1;
20//! ```
21
22use crate::{
23    analysis::Validator,
24    mir::{Function, Module},
25    transform::{
26        AdcePass, CfgSimplifyPass, CheckElimPass, CsePass, DcePass, FrameSlotPromotionPass,
27        FunctionDcePass, GvnPass, IndVarSimplifyPass, InlinePass, InstSimplifyPass,
28        JumpThreadingPass, LicmPass, LoadPrePass, LoopCanonicalizePass, MemoryDsePass, PrePass,
29        PureEvalPass, SccpTransformPass, StorageDsePass, StorageLoadCsePass,
30        StorageScalarPromotionPass,
31    },
32};
33use solar_data_structures::map::FxHashMap;
34use std::any::{Any, TypeId};
35
36type PassFactory = fn() -> Box<dyn ModulePass>;
37
38/// Registry entry for a MIR transform pass.
39#[derive(Clone, Copy, Debug)]
40pub struct PassInfo {
41    /// Command-line and pipeline name.
42    pub name: &'static str,
43    /// Human-readable help text.
44    pub description: &'static str,
45    make_pass: PassFactory,
46}
47
48impl PassInfo {
49    const fn new(name: &'static str, description: &'static str, make_pass: PassFactory) -> Self {
50        Self { name, description, make_pass }
51    }
52
53    fn make_pass(&self) -> Box<dyn ModulePass> {
54        (self.make_pass)()
55    }
56}
57
58macro_rules! declare_passes {
59    ($(
60        $(#[doc = $description:literal])+
61        $vis:vis const $const_name:ident -> $name:literal = $pass:expr;
62    )+) => {
63        $(
64            $(#[doc = $description])+
65            $vis const $const_name: PassInfo = PassInfo::new(
66                $name,
67                concat!($($description, "\n"),+).trim_ascii(),
68                || Box::new($pass),
69            );
70        )+
71    };
72}
73
74declare_passes! {
75    /// Internal MIR function inlining.
76    pub const INLINE_PASS -> "inline" = InlinePass;
77
78    /// Dead internal function elimination.
79    pub const FUNCTION_DCE_PASS -> "function-dce" = FunctionDcePass;
80
81    /// Sparse Conditional Constant Propagation.
82    pub const SCCP_PASS -> "sccp" = SccpTransformPass;
83
84    /// Bounded evaluator for closed pure MIR loops/functions.
85    pub const PURE_EVAL_PASS -> "pure-eval" = PureEvalPass;
86
87    /// Local MIR instruction simplification.
88    pub const INST_SIMPLIFY_PASS -> "inst-simplify" = InstSimplifyPass;
89
90    /// Common Subexpression Elimination (fixed-point).
91    pub const CSE_PASS -> "cse" = CsePass;
92
93    /// Partial redundancy elimination for pure expressions.
94    pub const PRE_PASS -> "pre" = PrePass;
95
96    /// Congruence-class global value numbering.
97    pub const GVN_PASS -> "gvn" = GvnPass;
98
99    /// Reuse storage loads across definitely-disjoint stores.
100    pub const STORAGE_LOAD_CSE_PASS -> "storage-load-cse" = StorageLoadCsePass;
101
102    /// Eliminate overwritten or repeated storage stores.
103    pub const STORAGE_DSE_PASS -> "storage-dse" = StorageDsePass;
104
105    /// Availability-dataflow redundancy elimination and PRE for memory-dependent reads.
106    pub const LOAD_PRE_PASS -> "load-pre" = LoadPrePass;
107
108    /// Canonicalize natural loops with explicit preheaders.
109    pub const LOOP_CANONICALIZE_PASS -> "loop-canonicalize" = LoopCanonicalizePass;
110
111    /// Strength-reduce affine induction-variable address expressions.
112    pub const INDVAR_SIMPLIFY_PASS -> "indvar-simplify" = IndVarSimplifyPass;
113
114    /// Promote simple loop-carried storage updates to memory.
115    pub const STORAGE_PROMOTION_PASS -> "storage-promotion" = StorageScalarPromotionPass;
116
117    /// Loop-Invariant Code Motion.
118    pub const LICM_PASS -> "licm" = LicmPass;
119
120    /// Range-based elimination of provably dead overflow-check branches.
121    pub const CHECK_ELIM_PASS -> "check-elim" = CheckElimPass;
122
123    /// Jump Threading (fixed-point).
124    pub const JUMP_THREADING_PASS -> "jump-threading" = JumpThreadingPass;
125
126    /// CFG Simplification (fixed-point).
127    pub const CFG_SIMPLIFY_PASS -> "cfg-simplify" = CfgSimplifyPass;
128
129    /// Promote non-escaping compiler-local slots to SSA values.
130    pub const FRAME_SLOT_PROMOTION_PASS -> "frame-slot-promotion" = FrameSlotPromotionPass;
131
132    /// Local dead memory-store elimination.
133    pub const MEMORY_DSE_PASS -> "memory-dse" = MemoryDsePass;
134
135    /// Dead Code Elimination (fixed-point).
136    pub const DCE_PASS -> "dce" = DcePass;
137
138    /// Aggressive dead-code elimination for dead control regions.
139    pub const ADCE_PASS -> "adce" = AdcePass;
140}
141
142/// All known MIR passes exposed to `solar mir-opt`.
143pub const PASS_REGISTRY: &[PassInfo] = &[
144    INLINE_PASS,
145    FUNCTION_DCE_PASS,
146    ADCE_PASS,
147    DCE_PASS,
148    INST_SIMPLIFY_PASS,
149    CSE_PASS,
150    GVN_PASS,
151    PRE_PASS,
152    STORAGE_LOAD_CSE_PASS,
153    STORAGE_DSE_PASS,
154    LOAD_PRE_PASS,
155    LOOP_CANONICALIZE_PASS,
156    INDVAR_SIMPLIFY_PASS,
157    SCCP_PASS,
158    PURE_EVAL_PASS,
159    LICM_PASS,
160    CHECK_ELIM_PASS,
161    CFG_SIMPLIFY_PASS,
162    JUMP_THREADING_PASS,
163    FRAME_SLOT_PROMOTION_PASS,
164    MEMORY_DSE_PASS,
165    STORAGE_PROMOTION_PASS,
166];
167
168/// Finds a pass in the global MIR pass registry by command-line name.
169pub fn lookup_pass(name: &str) -> Option<&'static PassInfo> {
170    PASS_REGISTRY.iter().find(|pass| pass.name == name)
171}
172
173/// The canonical MIR optimization pipeline used by EVM codegen.
174pub const DEFAULT_PIPELINE: &[PassInfo] = &[
175    INLINE_PASS,
176    FUNCTION_DCE_PASS,
177    SCCP_PASS,
178    PURE_EVAL_PASS,
179    INST_SIMPLIFY_PASS,
180    CSE_PASS,
181    GVN_PASS,
182    PRE_PASS,
183    STORAGE_LOAD_CSE_PASS,
184    STORAGE_DSE_PASS,
185    LOAD_PRE_PASS,
186    FRAME_SLOT_PROMOTION_PASS,
187    LOOP_CANONICALIZE_PASS,
188    INDVAR_SIMPLIFY_PASS,
189    STORAGE_PROMOTION_PASS,
190    LICM_PASS,
191    CHECK_ELIM_PASS,
192    JUMP_THREADING_PASS,
193    CFG_SIMPLIFY_PASS,
194    MEMORY_DSE_PASS,
195    ADCE_PASS,
196    DCE_PASS,
197];
198
199/// Cleanup passes rerun after the primary pipeline until no pass changes MIR.
200///
201/// Keep this group focused on simplification and canonicalization. Structural
202/// profitability passes such as inlining and storage promotion run once in
203/// [`DEFAULT_PIPELINE`], while this loop cleans up opportunities exposed by
204/// those transforms.
205pub const DEFAULT_CLEANUP_PIPELINE: &[PassInfo] = &[
206    SCCP_PASS,
207    PURE_EVAL_PASS,
208    INST_SIMPLIFY_PASS,
209    CSE_PASS,
210    GVN_PASS,
211    PRE_PASS,
212    STORAGE_LOAD_CSE_PASS,
213    STORAGE_DSE_PASS,
214    LOAD_PRE_PASS,
215    CHECK_ELIM_PASS,
216    JUMP_THREADING_PASS,
217    CFG_SIMPLIFY_PASS,
218    FRAME_SLOT_PROMOTION_PASS,
219    MEMORY_DSE_PASS,
220    ADCE_PASS,
221    DCE_PASS,
222];
223
224const DEFAULT_CLEANUP_MAX_ROUNDS: usize = 3;
225
226/// Options for running a MIR pass pipeline.
227#[derive(Clone, Copy, Debug)]
228pub struct PipelineOptions {
229    /// Print the full module after every pass in the pipeline.
230    pub print_after_each: bool,
231    /// Validate MIR after every pass.
232    pub validate_after_each: bool,
233}
234
235impl Default for PipelineOptions {
236    fn default() -> Self {
237        Self { print_after_each: false, validate_after_each: cfg!(debug_assertions) }
238    }
239}
240
241/// Runs a named MIR pass over a module.
242pub fn run_pass(module: &mut Module, pass: &PassInfo) -> bool {
243    run_pass_with_options(module, pass, PipelineOptions::default())
244}
245
246fn run_pass_with_options(module: &mut Module, pass: &PassInfo, options: PipelineOptions) -> bool {
247    let mut pm = PassManager::new();
248    pm.set_validate_after_each(options.validate_after_each);
249    pm.add_pass(pass.make_pass());
250    pm.run(module).1
251}
252
253/// Runs a named MIR pass pipeline over a module.
254pub fn run_pipeline(module: &mut Module, passes: &[PassInfo]) -> bool {
255    let mut changed = false;
256    for pass in passes {
257        changed |= run_pass(module, pass);
258    }
259    changed
260}
261
262/// Runs a named MIR pass pipeline over a module with observer options.
263pub fn run_pipeline_with_options(
264    module: &mut Module,
265    passes: &[PassInfo],
266    options: PipelineOptions,
267) -> bool {
268    let mut changed = false;
269    for pass in passes {
270        changed |= run_pass_with_options(module, pass, options);
271        if options.print_after_each {
272            println!("// === {} (after {}) ===", module.name, pass.name);
273            print!("{}", module.to_text());
274        }
275    }
276    changed
277}
278
279/// Runs the canonical MIR optimization pipeline used by EVM codegen.
280pub fn run_default_pipeline(module: &mut Module) -> bool {
281    run_default_pipeline_with_options(module, PipelineOptions::default())
282}
283
284/// Runs the canonical MIR optimization pipeline used by EVM codegen with options.
285pub fn run_default_pipeline_with_options(module: &mut Module, options: PipelineOptions) -> bool {
286    let mut changed = run_pipeline_with_options(module, DEFAULT_PIPELINE, options);
287    changed |=
288        run_cleanup_pipeline_to_fixpoint(module, DEFAULT_CLEANUP_PIPELINE, options, "cleanup");
289    changed
290}
291
292fn run_cleanup_pipeline_to_fixpoint(
293    module: &mut Module,
294    passes: &[PassInfo],
295    options: PipelineOptions,
296    label: &str,
297) -> bool {
298    let mut changed = false;
299    for round in 1..=DEFAULT_CLEANUP_MAX_ROUNDS {
300        let mut round_changed = false;
301        for pass in passes {
302            let pass_changed = run_pass_with_options(module, pass, options);
303            round_changed |= pass_changed;
304            if options.print_after_each {
305                println!("// === {} (after {label}-{round}:{}) ===", module.name, pass.name);
306                print!("{}", module.to_text());
307            }
308        }
309        if !round_changed {
310            break;
311        }
312        changed = true;
313    }
314    changed
315}
316
317/// A key identifying a particular analysis, derived from its result type.
318#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
319pub struct AnalysisKey(TypeId);
320
321impl AnalysisKey {
322    /// Creates a key from a type.
323    pub fn of<T: 'static>() -> Self {
324        Self(TypeId::of::<T>())
325    }
326}
327
328/// A read-only analysis pass.
329///
330/// Analysis passes inspect a function without modifying it and produce a
331/// cacheable result that downstream passes can query via [`AnalysisManager`].
332pub trait AnalysisPass {
333    /// The result type produced by this analysis.
334    type Result: 'static;
335
336    /// The name of this analysis, for debugging and logging.
337    fn name(&self) -> &str;
338
339    /// Computes the analysis result for the given function.
340    fn run(&self, func: &Function) -> Self::Result;
341}
342
343/// A transformation pass that mutates a MIR module.
344///
345/// Module-level passes can inspect or transform more than one function. Function-local passes
346/// should implement [`FunctionPass`] instead and use the blanket [`ModulePass`] implementation.
347pub trait ModulePass {
348    /// The name of this pass, for debugging and logging.
349    fn name(&self) -> &str;
350
351    /// Runs the transformation on the given module.
352    ///
353    /// Returns true if the transform changed MIR.
354    fn run(&mut self, module: &mut Module) -> bool;
355}
356
357/// A transformation pass that mutates one function at a time.
358pub trait FunctionPass {
359    /// The name of this pass, for debugging and logging.
360    fn name(&self) -> &str;
361
362    /// Runs the transformation on the given function.
363    fn run_on_function(&mut self, func: &mut Function) -> bool;
364}
365
366impl<T: FunctionPass> ModulePass for T {
367    fn name(&self) -> &str {
368        FunctionPass::name(self)
369    }
370
371    fn run(&mut self, module: &mut Module) -> bool {
372        let mut changed = false;
373        for func in module.functions.iter_mut().filter(|func| !func.blocks.is_empty()) {
374            changed |= self.run_on_function(func);
375        }
376        changed
377    }
378}
379
380/// Manages cached analysis results for a function.
381///
382/// Analyses are keyed by their result type via [`AnalysisKey`].
383#[derive(Default)]
384pub struct AnalysisManager {
385    results: FxHashMap<AnalysisKey, Box<dyn Any>>,
386}
387
388impl AnalysisManager {
389    /// Creates a new, empty analysis manager.
390    pub fn new() -> Self {
391        Self::default()
392    }
393
394    /// Returns the cached result for the given analysis type, if available.
395    pub fn get<T: 'static>(&self) -> Option<&T> {
396        let key = AnalysisKey::of::<T>();
397        self.results.get(&key)?.downcast_ref::<T>()
398    }
399
400    /// Caches an analysis result.
401    pub fn insert<T: 'static>(&mut self, result: T) {
402        let key = AnalysisKey::of::<T>();
403        self.results.insert(key, Box::new(result));
404    }
405
406    /// Returns the result of the analysis, computing and caching it if not already present.
407    ///
408    /// This is the recommended way to obtain analysis results, matching
409    /// LLVM's `AnalysisManager::getResult<AnalysisT>(F)` pattern.
410    pub fn get_or_compute<A: AnalysisPass>(&mut self, analysis: &A, func: &Function) -> &A::Result {
411        let key = AnalysisKey::of::<A::Result>();
412        self.results.entry(key).or_insert_with(|| {
413            let result = analysis.run(func);
414            Box::new(result)
415        });
416        self.results[&key].downcast_ref::<A::Result>().unwrap()
417    }
418
419    /// Invalidates all cached analysis results.
420    pub fn invalidate_all(&mut self) {
421        self.results.clear();
422    }
423
424    /// Invalidates a specific analysis result.
425    pub fn invalidate<T: 'static>(&mut self) {
426        let key = AnalysisKey::of::<T>();
427        self.results.remove(&key);
428    }
429}
430
431/// Orchestrates execution of [`ModulePass`]es on a module.
432///
433/// Each transform automatically invalidates all cached analyses after changing MIR.
434pub struct PassManager {
435    passes: Vec<Box<dyn ModulePass>>,
436    validate_after_each: bool,
437}
438
439impl Default for PassManager {
440    fn default() -> Self {
441        Self { passes: Vec::new(), validate_after_each: cfg!(debug_assertions) }
442    }
443}
444
445impl PassManager {
446    /// Creates a new, empty pass manager.
447    pub fn new() -> Self {
448        Self::default()
449    }
450
451    /// Adds a transformation pass to the pipeline.
452    pub fn add_pass(&mut self, pass: Box<dyn ModulePass>) {
453        self.passes.push(pass);
454    }
455
456    /// Enables or disables MIR validation after every pass.
457    pub const fn set_validate_after_each(&mut self, enabled: bool) {
458        self.validate_after_each = enabled;
459    }
460
461    /// Runs all transforms in order on the given module.
462    /// Returns an [`AnalysisManager`] and whether any transform changed MIR.
463    pub fn run(&mut self, module: &mut Module) -> (AnalysisManager, bool) {
464        let mut am = AnalysisManager::new();
465        let mut changed = false;
466        for pass in &mut self.passes {
467            let pass_name = pass.name().to_string();
468            if pass.run(module) {
469                changed = true;
470                am.invalidate_all();
471            }
472            if self.validate_after_each {
473                validate_module_after_pass(module, &pass_name);
474            }
475        }
476        (am, changed)
477    }
478}
479
480fn validate_module_after_pass(module: &Module, pass_name: &str) {
481    let errors = Validator::validate_module(module);
482    if errors.is_empty() {
483        return;
484    }
485
486    let mut message = format!("MIR validation failed after `{pass_name}`");
487    for error in errors {
488        message.push_str("\n  ");
489        message.push_str(&error.to_string());
490    }
491    panic!("{message}");
492}
493
494/// Liveness analysis pass.
495pub struct LivenessAnalysis;
496
497impl AnalysisPass for LivenessAnalysis {
498    type Result = crate::analysis::Liveness;
499
500    fn name(&self) -> &str {
501        "liveness"
502    }
503
504    fn run(&self, func: &Function) -> Self::Result {
505        crate::analysis::Liveness::compute(func)
506    }
507}
solar_codegen/pass.rs

solar_codegen/
pass.rs
