cairo_lang_lowering/optimizations/
strategy.rs

1use cairo_lang_diagnostics::Maybe;
2use cairo_lang_utils::{Intern, define_short_id};
3use salsa::Database;
4
5use super::cse::cse;
6use super::dedup_blocks::dedup_blocks;
7use super::early_unsafe_panic::early_unsafe_panic;
8use super::gas_redeposit::gas_redeposit;
9use super::trim_unreachable::trim_unreachable;
10use super::validate::validate;
11use crate::Lowered;
12use crate::ids::ConcreteFunctionWithBodyId;
13use crate::implicits::lower_implicits;
14use crate::inline::apply_inlining;
15use crate::optimizations::branch_inversion::branch_inversion;
16use crate::optimizations::cancel_ops::cancel_ops;
17use crate::optimizations::const_folding::const_folding;
18use crate::optimizations::match_optimizer::optimize_matches;
19use crate::optimizations::remappings::optimize_remappings;
20use crate::optimizations::reorder_statements::reorder_statements;
21use crate::optimizations::return_optimization::return_optimization;
22use crate::optimizations::split_structs::split_structs;
23use crate::reorganize_blocks::reorganize_blocks;
24
25/// Enum of the optimization phases that can be used in a strategy.
26#[derive(Clone, Debug, Eq, Hash, PartialEq)]
27pub enum OptimizationPhase<'db> {
28    ApplyInlining {
29        enable_const_folding: bool,
30    },
31    BranchInversion,
32    CancelOps,
33    ConstFolding,
34    Cse,
35    DedupBlocks,
36    EarlyUnsafePanic,
37    OptimizeMatches,
38    OptimizeRemappings,
39    ReorderStatements,
40    ReorganizeBlocks,
41    ReturnOptimization,
42    SplitStructs,
43    TrimUnreachable,
44    GasRedeposit,
45    /// The following is not really an optimization but we want to apply optimizations before and
46    /// after it, so it is convenient to treat it as an optimization.
47    LowerImplicits,
48    /// A validation phase that checks the lowering is valid. Used for debugging purposes.
49    Validate,
50    /// A phase that iteratively a set of optimizations to the lowering.
51    /// Stops after a certain number of iterations, or when no more changes are made.
52    SubStrategy {
53        /// The id of the optimization strategy to apply.
54        strategy: OptimizationStrategyId<'db>,
55        /// The number of times to apply the strategy.
56        iterations: usize,
57    },
58}
59
60impl<'db> OptimizationPhase<'db> {
61    /// Applies the optimization phase to the lowering.
62    ///
63    /// Assumes `lowered` is a lowering of `function`.
64    pub fn apply(
65        self,
66        db: &'db dyn Database,
67        function: ConcreteFunctionWithBodyId<'db>,
68        lowered: &mut Lowered<'db>,
69    ) -> Maybe<()> {
70        match self {
71            OptimizationPhase::ApplyInlining { enable_const_folding } => {
72                apply_inlining(db, function, lowered, enable_const_folding)?
73            }
74            OptimizationPhase::BranchInversion => branch_inversion(db, lowered),
75            OptimizationPhase::CancelOps => cancel_ops(lowered),
76            OptimizationPhase::ConstFolding => const_folding(db, function, lowered),
77            OptimizationPhase::Cse => cse(lowered),
78            OptimizationPhase::EarlyUnsafePanic => early_unsafe_panic(db, lowered),
79            OptimizationPhase::DedupBlocks => dedup_blocks(lowered),
80            OptimizationPhase::OptimizeMatches => optimize_matches(lowered),
81            OptimizationPhase::OptimizeRemappings => optimize_remappings(lowered),
82            OptimizationPhase::ReorderStatements => reorder_statements(db, lowered),
83            OptimizationPhase::ReorganizeBlocks => reorganize_blocks(lowered),
84            OptimizationPhase::ReturnOptimization => return_optimization(db, lowered),
85            OptimizationPhase::SplitStructs => split_structs(lowered),
86            OptimizationPhase::TrimUnreachable => trim_unreachable(db, lowered),
87            OptimizationPhase::LowerImplicits => lower_implicits(db, function, lowered),
88            OptimizationPhase::GasRedeposit => gas_redeposit(db, function, lowered),
89            OptimizationPhase::Validate => validate(lowered).unwrap_or_else(|err| {
90                panic!(
91                    "Failed validation for function {}: {:?}",
92                    function.full_path(db),
93                    err.to_message()
94                )
95            }),
96            OptimizationPhase::SubStrategy { strategy, iterations } => {
97                for _ in 1..iterations {
98                    let before = lowered.clone();
99                    strategy.apply_strategy(db, function, lowered)?;
100                    if *lowered == before {
101                        return Ok(());
102                    }
103                }
104                strategy.apply_strategy(db, function, lowered)?
105            }
106        }
107        Ok(())
108    }
109}
110
111define_short_id!(OptimizationStrategyId, OptimizationStrategy<'db>);
112
113/// A strategy is a sequence of optimization phases.
114#[derive(Clone, Debug, Eq, Hash, PartialEq)]
115pub struct OptimizationStrategy<'db>(pub Vec<OptimizationPhase<'db>>);
116
117impl<'db> OptimizationStrategyId<'db> {
118    /// Applies the optimization strategy phase to the lowering.
119    ///
120    /// Assumes `lowered` is a lowering of `function`.
121    pub fn apply_strategy(
122        self,
123        db: &'db dyn Database,
124        function: ConcreteFunctionWithBodyId<'db>,
125        lowered: &mut Lowered<'db>,
126    ) -> Maybe<()> {
127        for phase in self.long(db).0.clone() {
128            phase.apply(db, function, lowered)?;
129        }
130
131        Ok(())
132    }
133}
134
135/// Query implementation of [crate::db::LoweringGroup::baseline_optimization_strategy].
136#[salsa::tracked]
137pub fn baseline_optimization_strategy<'db>(db: &'db dyn Database) -> OptimizationStrategyId<'db> {
138    OptimizationStrategy(vec![
139        // Must be right before inlining.
140        OptimizationPhase::ReorganizeBlocks,
141        OptimizationPhase::ApplyInlining { enable_const_folding: true },
142        OptimizationPhase::ReturnOptimization,
143        OptimizationPhase::ReorganizeBlocks,
144        OptimizationPhase::ReorderStatements,
145        OptimizationPhase::BranchInversion,
146        OptimizationPhase::CancelOps,
147        // Must be right before const folding.
148        OptimizationPhase::ReorganizeBlocks,
149        OptimizationPhase::ConstFolding,
150        OptimizationPhase::OptimizeMatches,
151        OptimizationPhase::SplitStructs,
152        OptimizationPhase::ReorganizeBlocks,
153        OptimizationPhase::ReorderStatements,
154        OptimizationPhase::OptimizeMatches,
155        OptimizationPhase::ReorganizeBlocks,
156        OptimizationPhase::CancelOps,
157        OptimizationPhase::ReorganizeBlocks,
158        // Performing CSE here after blocks are the most contiguous, to reach maximum effect.
159        OptimizationPhase::Cse,
160        OptimizationPhase::DedupBlocks,
161        // Re-run ReturnOptimization to eliminate harmful merges introduced by DedupBlocks.
162        OptimizationPhase::ReturnOptimization,
163        OptimizationPhase::ReorderStatements,
164        OptimizationPhase::ReorganizeBlocks,
165    ])
166    .intern(db)
167}
168
169/// Query implementation of [crate::db::LoweringGroup::final_optimization_strategy].
170#[salsa::tracked]
171pub fn final_optimization_strategy<'db>(db: &'db dyn Database) -> OptimizationStrategyId<'db> {
172    OptimizationStrategy(vec![
173        OptimizationPhase::GasRedeposit,
174        OptimizationPhase::EarlyUnsafePanic,
175        // Apply `TrimUnreachable` here to remove unreachable `redeposit_gas` and `unsafe_panic`
176        // calls.
177        OptimizationPhase::TrimUnreachable,
178        OptimizationPhase::LowerImplicits,
179        OptimizationPhase::ReorganizeBlocks,
180    ])
181    .intern(db)
182}
cairo_lang_lowering/optimizations/strategy.rs

cairo_lang_lowering/optimizations/
strategy.rs
