cairo_lang_lowering/optimizations/
strategy.rs

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

cairo_lang_lowering/optimizations/
strategy.rs
