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, 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
65impl<'db> OptimizationPhase<'db> {
66    /// Applies the optimization phase to the lowering.
67    ///
68    /// Assumes `lowered` is a lowering of `function`.
69    pub fn apply(
70        self,
71        db: &'db dyn Database,
72        function: ConcreteFunctionWithBodyId<'db>,
73        lowered: &mut Lowered<'db>,
74    ) -> Maybe<()> {
75        debug!("Applying optimization: {self:?}");
76
77        match self {
78            OptimizationPhase::ApplyInlining { enable_const_folding } => {
79                apply_inlining(db, function, lowered, enable_const_folding)?
80            }
81            OptimizationPhase::BranchInversion => branch_inversion(db, lowered),
82            OptimizationPhase::CancelOps => cancel_ops(lowered),
83            OptimizationPhase::ConstFolding => const_folding(db, function, lowered),
84            OptimizationPhase::Cse => cse(lowered),
85            OptimizationPhase::EarlyUnsafePanic => early_unsafe_panic(db, lowered),
86            OptimizationPhase::DedupBlocks => dedup_blocks(lowered),
87            OptimizationPhase::OptimizeMatches => optimize_matches(lowered),
88            OptimizationPhase::OptimizeRemappings => optimize_remappings(lowered),
89            OptimizationPhase::Reboxing => apply_reboxing(db, lowered),
90            OptimizationPhase::ReorderStatements => reorder_statements(db, lowered),
91            OptimizationPhase::ReorganizeBlocks => reorganize_blocks(lowered),
92            OptimizationPhase::ReturnOptimization => return_optimization(db, lowered),
93            OptimizationPhase::SplitStructs => split_structs(lowered),
94            OptimizationPhase::TrimUnreachable => trim_unreachable(db, lowered),
95            OptimizationPhase::LowerImplicits => lower_implicits(db, function, lowered),
96            OptimizationPhase::GasRedeposit => gas_redeposit(db, function, lowered),
97            OptimizationPhase::Validate => validate(lowered).unwrap_or_else(|err| {
98                panic!(
99                    "Failed validation for function {}: {:?}",
100                    function.full_path(db),
101                    err.to_message()
102                )
103            }),
104            OptimizationPhase::SubStrategy { strategy, iterations } => {
105                for _ in 1..iterations {
106                    let before = lowered.clone();
107                    strategy.apply_strategy(db, function, lowered)?;
108                    if *lowered == before {
109                        return Ok(());
110                    }
111                }
112                strategy.apply_strategy(db, function, lowered)?
113            }
114        }
115        Ok(())
116    }
117}
118
119define_short_id!(OptimizationStrategyId, OptimizationStrategy<'db>);
120
121/// A strategy is a sequence of optimization phases.
122#[derive(Clone, Debug, Eq, Hash, PartialEq, HeapSize)]
123pub struct OptimizationStrategy<'db>(pub Vec<OptimizationPhase<'db>>);
124
125impl<'db> OptimizationStrategyId<'db> {
126    /// Applies the optimization strategy phase to the lowering.
127    ///
128    /// Assumes `lowered` is a lowering of `function`.
129    pub fn apply_strategy(
130        self,
131        db: &'db dyn Database,
132        function: ConcreteFunctionWithBodyId<'db>,
133        lowered: &mut Lowered<'db>,
134    ) -> Maybe<()> {
135        for phase in self.long(db).0.clone() {
136            phase.apply(db, function, lowered)?;
137        }
138
139        Ok(())
140    }
141}
142
143/// Query implementation of [crate::db::LoweringGroup::baseline_optimization_strategy].
144#[salsa::tracked]
145pub fn baseline_optimization_strategy<'db>(db: &'db dyn Database) -> OptimizationStrategyId<'db> {
146    match db.optimizations() {
147        Optimizations::Enabled(_) => {
148            OptimizationStrategy(vec![
149                // Must be right before inlining.
150                OptimizationPhase::ReorganizeBlocks,
151                OptimizationPhase::ApplyInlining { enable_const_folding: true },
152                OptimizationPhase::ReturnOptimization,
153                OptimizationPhase::ReorganizeBlocks,
154                OptimizationPhase::ReorderStatements,
155                OptimizationPhase::BranchInversion,
156                OptimizationPhase::CancelOps,
157                // Must be right before const folding.
158                OptimizationPhase::ReorganizeBlocks,
159                OptimizationPhase::ConstFolding,
160                OptimizationPhase::OptimizeMatches,
161                OptimizationPhase::SplitStructs,
162                OptimizationPhase::ReorganizeBlocks,
163                OptimizationPhase::ReorderStatements,
164                OptimizationPhase::OptimizeMatches,
165                OptimizationPhase::ReorganizeBlocks,
166                OptimizationPhase::Reboxing,
167                OptimizationPhase::CancelOps,
168                OptimizationPhase::ReorganizeBlocks,
169                // Performing CSE here after blocks are the most contiguous, to reach maximum
170                // effect.
171                OptimizationPhase::Cse,
172                OptimizationPhase::DedupBlocks,
173                // Re-run ReturnOptimization to eliminate harmful merges introduced by DedupBlocks.
174                OptimizationPhase::ReturnOptimization,
175                OptimizationPhase::ReorderStatements,
176                OptimizationPhase::ReorganizeBlocks,
177            ])
178        }
179        Optimizations::Disabled => OptimizationStrategy(vec![OptimizationPhase::ApplyInlining {
180            enable_const_folding: false,
181        }]),
182    }
183    .intern(db)
184}
185
186/// Query implementation of [crate::db::LoweringGroup::final_optimization_strategy].
187#[salsa::tracked]
188pub fn final_optimization_strategy<'db>(db: &'db dyn Database) -> OptimizationStrategyId<'db> {
189    match db.optimizations() {
190        Optimizations::Enabled(_) => {
191            OptimizationStrategy(vec![
192                OptimizationPhase::GasRedeposit,
193                OptimizationPhase::EarlyUnsafePanic,
194                // Apply `TrimUnreachable` here to remove unreachable `redeposit_gas` and
195                // `unsafe_panic` calls.
196                OptimizationPhase::TrimUnreachable,
197                OptimizationPhase::LowerImplicits,
198                OptimizationPhase::ReorganizeBlocks,
199            ])
200        }
201        Optimizations::Disabled => OptimizationStrategy(vec![
202            OptimizationPhase::LowerImplicits,
203            OptimizationPhase::ReorganizeBlocks,
204        ]),
205    }
206    .intern(db)
207}
cairo_lang_lowering/optimizations/strategy.rs

cairo_lang_lowering/optimizations/
strategy.rs
