cairo_lang_lowering/optimizations/
strategy.rs

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

cairo_lang_lowering/optimizations/
strategy.rs
