cairo_lang_lowering/optimizations/
const_folding.rs

1#[cfg(test)]
2#[path = "const_folding_test.rs"]
3mod test;
4
5use std::sync::Arc;
6
7use cairo_lang_defs::ids::{ExternFunctionId, ModuleId};
8use cairo_lang_semantic::helper::ModuleHelper;
9use cairo_lang_semantic::items::constant::ConstValue;
10use cairo_lang_semantic::items::imp::ImplLookupContext;
11use cairo_lang_semantic::{GenericArgumentId, MatchArmSelector, TypeId, corelib};
12use cairo_lang_utils::ordered_hash_map::OrderedHashMap;
13use cairo_lang_utils::ordered_hash_set::OrderedHashSet;
14use cairo_lang_utils::unordered_hash_map::UnorderedHashMap;
15use cairo_lang_utils::{Intern, LookupIntern, extract_matches, try_extract_matches};
16use id_arena::Arena;
17use itertools::{chain, zip_eq};
18use num_bigint::BigInt;
19use num_integer::Integer;
20use num_traits::Zero;
21
22use crate::db::LoweringGroup;
23use crate::ids::{FunctionId, SemanticFunctionIdEx};
24use crate::{
25    BlockId, FlatBlockEnd, FlatLowered, MatchArm, MatchEnumInfo, MatchExternInfo, MatchInfo,
26    Statement, StatementCall, StatementConst, StatementDesnap, StatementEnumConstruct,
27    StatementStructConstruct, StatementStructDestructure, VarUsage, Variable, VariableId,
28};
29
30/// Keeps track of equivalent values that a variables might be replaced with.
31/// Note: We don't keep track of types as we assume the usage is always correct.
32#[derive(Debug, Clone)]
33enum VarInfo {
34    /// The variable is a const value.
35    Const(ConstValue),
36    /// The variable can be replaced by another variable.
37    Var(VarUsage),
38    /// The variable is a snapshot of another variable.
39    Snapshot(Box<VarInfo>),
40    /// The variable is a struct of other variables.
41    /// `None` values represent variables that are not tracked.
42    Struct(Vec<Option<VarInfo>>),
43}
44
45/// Performs constant folding on the lowered program.
46/// The optimization works better when the blocks are topologically sorted.
47pub fn const_folding(db: &dyn LoweringGroup, lowered: &mut FlatLowered) {
48    if db.optimization_config().skip_const_folding || lowered.blocks.is_empty() {
49        return;
50    }
51    let libfunc_info = priv_const_folding_info(db);
52    // Note that we can keep the var_info across blocks because the lowering
53    // is in static single assignment form.
54    let mut ctx = ConstFoldingContext {
55        db,
56        var_info: UnorderedHashMap::default(),
57        variables: &mut lowered.variables,
58        libfunc_info: &libfunc_info,
59    };
60    let mut stack = vec![BlockId::root()];
61    let mut visited = vec![false; lowered.blocks.len()];
62    while let Some(block_id) = stack.pop() {
63        if visited[block_id.0] {
64            continue;
65        }
66        visited[block_id.0] = true;
67
68        let block = &mut lowered.blocks[block_id];
69        let mut additional_consts = vec![];
70        for stmt in block.statements.iter_mut() {
71            ctx.maybe_replace_inputs(stmt.inputs_mut());
72            match stmt {
73                Statement::Const(StatementConst { value, output }) => {
74                    // Preventing the insertion of non-member consts values (such as a `Box` of a
75                    // const).
76                    if matches!(
77                        value,
78                        ConstValue::Int(..)
79                            | ConstValue::Struct(..)
80                            | ConstValue::Enum(..)
81                            | ConstValue::NonZero(..)
82                    ) {
83                        ctx.var_info.insert(*output, VarInfo::Const(value.clone()));
84                    }
85                }
86                Statement::Snapshot(stmt) => {
87                    if let Some(info) = ctx.var_info.get(&stmt.input.var_id).cloned() {
88                        ctx.var_info.insert(stmt.original(), info.clone());
89                        ctx.var_info.insert(stmt.snapshot(), VarInfo::Snapshot(info.into()));
90                    }
91                }
92                Statement::Desnap(StatementDesnap { input, output }) => {
93                    if let Some(VarInfo::Snapshot(info)) = ctx.var_info.get(&input.var_id) {
94                        ctx.var_info.insert(*output, info.as_ref().clone());
95                    }
96                }
97                Statement::Call(call_stmt) => {
98                    if let Some(updated_stmt) =
99                        ctx.handle_statement_call(call_stmt, &mut additional_consts)
100                    {
101                        *stmt = Statement::Const(updated_stmt);
102                    }
103                }
104                Statement::StructConstruct(StatementStructConstruct { inputs, output }) => {
105                    let mut const_args = vec![];
106                    let mut all_args = vec![];
107                    let mut contains_info = false;
108                    for input in inputs.iter() {
109                        let Some(info) = ctx.var_info.get(&input.var_id) else {
110                            all_args.push(
111                                ctx.variables[input.var_id]
112                                    .copyable
113                                    .is_ok()
114                                    .then_some(VarInfo::Var(*input)),
115                            );
116                            continue;
117                        };
118                        contains_info = true;
119                        if let VarInfo::Const(value) = info {
120                            const_args.push(value.clone());
121                        }
122                        all_args.push(Some(info.clone()));
123                    }
124                    if const_args.len() == inputs.len() {
125                        let value = ConstValue::Struct(const_args, ctx.variables[*output].ty);
126                        ctx.var_info.insert(*output, VarInfo::Const(value));
127                    } else if contains_info {
128                        ctx.var_info.insert(*output, VarInfo::Struct(all_args));
129                    }
130                }
131                Statement::StructDestructure(StatementStructDestructure { input, outputs }) => {
132                    if let Some(mut info) = ctx.var_info.get(&input.var_id) {
133                        let mut n_snapshot = 0;
134                        while let VarInfo::Snapshot(inner) = info {
135                            info = inner.as_ref();
136                            n_snapshot += 1;
137                        }
138                        let wrap_with_snapshots = |mut info| {
139                            for _ in 0..n_snapshot {
140                                info = VarInfo::Snapshot(Box::new(info));
141                            }
142                            info
143                        };
144                        match info {
145                            VarInfo::Const(ConstValue::Struct(member_values, _)) => {
146                                for (output, value) in zip_eq(outputs, member_values.clone()) {
147                                    ctx.var_info.insert(
148                                        *output,
149                                        wrap_with_snapshots(VarInfo::Const(value)),
150                                    );
151                                }
152                            }
153                            VarInfo::Struct(members) => {
154                                for (output, member) in zip_eq(outputs, members.clone()) {
155                                    if let Some(member) = member {
156                                        ctx.var_info.insert(*output, wrap_with_snapshots(member));
157                                    }
158                                }
159                            }
160                            _ => {}
161                        }
162                    }
163                }
164                Statement::EnumConstruct(StatementEnumConstruct { variant, input, output }) => {
165                    if let Some(VarInfo::Const(val)) = ctx.var_info.get(&input.var_id) {
166                        let value = ConstValue::Enum(variant.clone(), val.clone().into());
167                        ctx.var_info.insert(*output, VarInfo::Const(value.clone()));
168                    }
169                }
170            }
171        }
172        block.statements.splice(0..0, additional_consts.into_iter().map(Statement::Const));
173
174        match &mut block.end {
175            FlatBlockEnd::Goto(block_id, remappings) => {
176                stack.push(*block_id);
177                for (_, v) in remappings.iter_mut() {
178                    ctx.maybe_replace_input(v);
179                }
180            }
181            FlatBlockEnd::Match { info } => {
182                stack.extend(info.arms().iter().map(|arm| arm.block_id));
183                ctx.maybe_replace_inputs(info.inputs_mut());
184                match info {
185                    MatchInfo::Enum(MatchEnumInfo { input, arms, .. }) => {
186                        if let Some(VarInfo::Const(ConstValue::Enum(variant, value))) =
187                            ctx.var_info.get(&input.var_id)
188                        {
189                            let arm = &arms[variant.idx];
190                            ctx.var_info
191                                .insert(arm.var_ids[0], VarInfo::Const(value.as_ref().clone()));
192                        }
193                    }
194                    MatchInfo::Extern(info) => {
195                        if let Some((extra_stmt, updated_end)) = ctx.handle_extern_block_end(info) {
196                            if let Some(stmt) = extra_stmt {
197                                block.statements.push(Statement::Const(stmt));
198                            }
199                            block.end = updated_end;
200                        }
201                    }
202                    MatchInfo::Value(..) => {}
203                }
204            }
205            FlatBlockEnd::Return(ref mut inputs, _) => ctx.maybe_replace_inputs(inputs),
206            FlatBlockEnd::Panic(_) | FlatBlockEnd::NotSet => unreachable!(),
207        }
208    }
209}
210
211struct ConstFoldingContext<'a> {
212    /// The used database.
213    db: &'a dyn LoweringGroup,
214    /// The variables arena, mostly used to get the type of variables.
215    variables: &'a mut Arena<Variable>,
216    /// The accumulated information about the const values of variables.
217    var_info: UnorderedHashMap<VariableId, VarInfo>,
218    /// The libfunc information.
219    libfunc_info: &'a ConstFoldingLibfuncInfo,
220}
221
222impl ConstFoldingContext<'_> {
223    /// Handles a statement call.
224    ///
225    /// Returns None if no additional changes are required.
226    /// If changes are required, returns an updated const-statement (to override the current
227    /// statement).
228    /// May add an additional const to `additional_consts` if just replacing the current statement
229    /// is not enough.
230    fn handle_statement_call(
231        &mut self,
232        stmt: &mut StatementCall,
233        additional_consts: &mut Vec<StatementConst>,
234    ) -> Option<StatementConst> {
235        if stmt.function == self.panic_with_felt252 {
236            let val = self.as_const(stmt.inputs[0].var_id)?;
237            stmt.inputs.clear();
238            stmt.function = ModuleHelper::core(self.db.upcast())
239                .function_id(
240                    "panic_with_const_felt252",
241                    vec![GenericArgumentId::Constant(val.clone().intern(self.db))],
242                )
243                .lowered(self.db);
244            return None;
245        }
246        let (id, _generic_args) = stmt.function.get_extern(self.db)?;
247        if id == self.felt_sub {
248            // (a - 0) can be replaced by a.
249            let val = self.as_int(stmt.inputs[1].var_id)?;
250            if val.is_zero() {
251                self.var_info.insert(stmt.outputs[0], VarInfo::Var(stmt.inputs[0]));
252            }
253            None
254        } else if self.wide_mul_fns.contains(&id) {
255            let lhs = self.as_int_ex(stmt.inputs[0].var_id);
256            let rhs = self.as_int(stmt.inputs[1].var_id);
257            let output = stmt.outputs[0];
258            if lhs.map(|(v, _)| v.is_zero()).unwrap_or_default()
259                || rhs.map(Zero::is_zero).unwrap_or_default()
260            {
261                return Some(self.propagate_zero_and_get_statement(output));
262            }
263            let (lhs, nz_ty) = lhs?;
264            Some(self.propagate_const_and_get_statement(lhs * rhs?, stmt.outputs[0], nz_ty))
265        } else if id == self.bounded_int_add || id == self.bounded_int_sub {
266            let lhs = self.as_int(stmt.inputs[0].var_id)?;
267            let rhs = self.as_int(stmt.inputs[1].var_id)?;
268            let value = if id == self.bounded_int_add { lhs + rhs } else { lhs - rhs };
269            Some(self.propagate_const_and_get_statement(value, stmt.outputs[0], false))
270        } else if self.div_rem_fns.contains(&id) {
271            let lhs = self.as_int(stmt.inputs[0].var_id);
272            if lhs.map(Zero::is_zero).unwrap_or_default() {
273                additional_consts.push(self.propagate_zero_and_get_statement(stmt.outputs[1]));
274                return Some(self.propagate_zero_and_get_statement(stmt.outputs[0]));
275            }
276            let rhs = self.as_int(stmt.inputs[1].var_id)?;
277            let (q, r) = lhs?.div_rem(rhs);
278            let q_output = stmt.outputs[0];
279            let q_value = ConstValue::Int(q, self.variables[q_output].ty);
280            self.var_info.insert(q_output, VarInfo::Const(q_value.clone()));
281            let r_output = stmt.outputs[1];
282            let r_value = ConstValue::Int(r, self.variables[r_output].ty);
283            self.var_info.insert(r_output, VarInfo::Const(r_value.clone()));
284            additional_consts.push(StatementConst { value: r_value, output: r_output });
285            Some(StatementConst { value: q_value, output: q_output })
286        } else if id == self.storage_base_address_from_felt252 {
287            let input_var = stmt.inputs[0].var_id;
288            if let Some(ConstValue::Int(val, ty)) = self.as_const(input_var) {
289                stmt.inputs.clear();
290                stmt.function =
291                    ModuleHelper { db: self.db.upcast(), id: self.storage_access_module }
292                        .function_id(
293                            "storage_base_address_const",
294                            vec![GenericArgumentId::Constant(
295                                ConstValue::Int(val.clone(), *ty).intern(self.db),
296                            )],
297                        )
298                        .lowered(self.db);
299            }
300            None
301        } else if id == self.into_box {
302            let const_value = match self.var_info.get(&stmt.inputs[0].var_id)? {
303                VarInfo::Const(val) => val,
304                VarInfo::Snapshot(info) => try_extract_matches!(info.as_ref(), VarInfo::Const)?,
305                _ => return None,
306            };
307            let value = ConstValue::Boxed(const_value.clone().into());
308            // Not inserting the value into the `var_info` map because the
309            // resulting box isn't an actual const at the Sierra level.
310            Some(StatementConst { value, output: stmt.outputs[0] })
311        } else if id == self.upcast {
312            let int_value = self.as_int(stmt.inputs[0].var_id)?;
313            let output = stmt.outputs[0];
314            let value = ConstValue::Int(int_value.clone(), self.variables[output].ty);
315            self.var_info.insert(output, VarInfo::Const(value.clone()));
316            Some(StatementConst { value, output })
317        } else {
318            None
319        }
320    }
321
322    /// Adds `value` as a const to `var_info` and return a const statement for it.
323    fn propagate_const_and_get_statement(
324        &mut self,
325        value: BigInt,
326        output: VariableId,
327        nz_ty: bool,
328    ) -> StatementConst {
329        let mut value = ConstValue::Int(value, self.variables[output].ty);
330        if nz_ty {
331            value = ConstValue::NonZero(Box::new(value));
332        }
333        self.var_info.insert(output, VarInfo::Const(value.clone()));
334        StatementConst { value, output }
335    }
336
337    /// Adds 0 const to `var_info` and return a const statement for it.
338    fn propagate_zero_and_get_statement(&mut self, output: VariableId) -> StatementConst {
339        self.propagate_const_and_get_statement(BigInt::zero(), output, false)
340    }
341
342    /// Handles the end of an extern block.
343    /// Returns None if no additional changes are required.
344    /// If changes are required, returns a possible additional const-statement to the block, as well
345    /// as an updated block end.
346    fn handle_extern_block_end(
347        &mut self,
348        info: &mut MatchExternInfo,
349    ) -> Option<(Option<StatementConst>, FlatBlockEnd)> {
350        let (id, generic_args) = info.function.get_extern(self.db)?;
351        if self.nz_fns.contains(&id) {
352            let val = self.as_const(info.inputs[0].var_id)?;
353            let is_zero = match val {
354                ConstValue::Int(v, _) => v.is_zero(),
355                ConstValue::Struct(s, _) => s.iter().all(|v| {
356                    v.clone().into_int().expect("Expected ConstValue::Int for size").is_zero()
357                }),
358                _ => unreachable!(),
359            };
360            Some(if is_zero {
361                (None, FlatBlockEnd::Goto(info.arms[0].block_id, Default::default()))
362            } else {
363                let arm = &info.arms[1];
364                let nz_var = arm.var_ids[0];
365                let nz_val = ConstValue::NonZero(Box::new(val.clone()));
366                self.var_info.insert(nz_var, VarInfo::Const(nz_val.clone()));
367                (
368                    Some(StatementConst { value: nz_val, output: nz_var }),
369                    FlatBlockEnd::Goto(arm.block_id, Default::default()),
370                )
371            })
372        } else if self.eq_fns.contains(&id) {
373            let lhs = self.as_int(info.inputs[0].var_id);
374            let rhs = self.as_int(info.inputs[1].var_id);
375            if (lhs.map(Zero::is_zero).unwrap_or_default() && rhs.is_none())
376                || (rhs.map(Zero::is_zero).unwrap_or_default() && lhs.is_none())
377            {
378                let db = self.db.upcast();
379                let nz_input = info.inputs[if lhs.is_some() { 1 } else { 0 }];
380                let var = &self.variables[nz_input.var_id].clone();
381                let function = self.type_value_ranges.get(&var.ty)?.is_zero;
382                let unused_nz_var = Variable::new(
383                    self.db,
384                    ImplLookupContext::default(),
385                    corelib::core_nonzero_ty(db, var.ty),
386                    var.location,
387                );
388                let unused_nz_var = self.variables.alloc(unused_nz_var);
389                return Some((
390                    None,
391                    FlatBlockEnd::Match {
392                        info: MatchInfo::Extern(MatchExternInfo {
393                            function,
394                            inputs: vec![nz_input],
395                            arms: vec![
396                                MatchArm {
397                                    arm_selector: MatchArmSelector::VariantId(
398                                        corelib::jump_nz_zero_variant(db, var.ty),
399                                    ),
400                                    block_id: info.arms[1].block_id,
401                                    var_ids: vec![],
402                                },
403                                MatchArm {
404                                    arm_selector: MatchArmSelector::VariantId(
405                                        corelib::jump_nz_nonzero_variant(db, var.ty),
406                                    ),
407                                    block_id: info.arms[0].block_id,
408                                    var_ids: vec![unused_nz_var],
409                                },
410                            ],
411                            location: info.location,
412                        }),
413                    },
414                ));
415            }
416            Some((
417                None,
418                FlatBlockEnd::Goto(
419                    info.arms[if lhs? == rhs? { 1 } else { 0 }].block_id,
420                    Default::default(),
421                ),
422            ))
423        } else if self.uadd_fns.contains(&id)
424            || self.usub_fns.contains(&id)
425            || self.diff_fns.contains(&id)
426            || self.iadd_fns.contains(&id)
427            || self.isub_fns.contains(&id)
428        {
429            let rhs = self.as_int(info.inputs[1].var_id);
430            if rhs.map(Zero::is_zero).unwrap_or_default() && !self.diff_fns.contains(&id) {
431                let arm = &info.arms[0];
432                self.var_info.insert(arm.var_ids[0], VarInfo::Var(info.inputs[0]));
433                return Some((None, FlatBlockEnd::Goto(arm.block_id, Default::default())));
434            }
435            let lhs = self.as_int(info.inputs[0].var_id);
436            let value = if self.uadd_fns.contains(&id) || self.iadd_fns.contains(&id) {
437                if lhs.map(Zero::is_zero).unwrap_or_default() {
438                    let arm = &info.arms[0];
439                    self.var_info.insert(arm.var_ids[0], VarInfo::Var(info.inputs[1]));
440                    return Some((None, FlatBlockEnd::Goto(arm.block_id, Default::default())));
441                }
442                lhs? + rhs?
443            } else {
444                lhs? - rhs?
445            };
446            let ty = self.variables[info.arms[0].var_ids[0]].ty;
447            let range = self.type_value_ranges.get(&ty)?;
448            let (arm_index, value) = match range.normalized(value) {
449                NormalizedResult::InRange(value) => (0, value),
450                NormalizedResult::Under(value) => (1, value),
451                NormalizedResult::Over(value) => (
452                    if self.iadd_fns.contains(&id) || self.isub_fns.contains(&id) { 2 } else { 1 },
453                    value,
454                ),
455            };
456            let arm = &info.arms[arm_index];
457            let actual_output = arm.var_ids[0];
458            let value = ConstValue::Int(value, ty);
459            self.var_info.insert(actual_output, VarInfo::Const(value.clone()));
460            Some((
461                Some(StatementConst { value, output: actual_output }),
462                FlatBlockEnd::Goto(arm.block_id, Default::default()),
463            ))
464        } else if id == self.downcast {
465            let input_var = info.inputs[0].var_id;
466            let value = self.as_int(input_var)?;
467            let success_output = info.arms[0].var_ids[0];
468            let ty = self.variables[success_output].ty;
469            let range = self.type_value_ranges.get(&ty)?;
470            Some(if let NormalizedResult::InRange(value) = range.normalized(value.clone()) {
471                let value = ConstValue::Int(value, ty);
472                self.var_info.insert(success_output, VarInfo::Const(value.clone()));
473                (
474                    Some(StatementConst { value, output: success_output }),
475                    FlatBlockEnd::Goto(info.arms[0].block_id, Default::default()),
476                )
477            } else {
478                (None, FlatBlockEnd::Goto(info.arms[1].block_id, Default::default()))
479            })
480        } else if id == self.bounded_int_constrain {
481            let input_var = info.inputs[0].var_id;
482            let (value, nz_ty) = self.as_int_ex(input_var)?;
483            let generic_arg = generic_args[1];
484            let constrain_value = extract_matches!(generic_arg, GenericArgumentId::Constant)
485                .lookup_intern(self.db)
486                .into_int()
487                .unwrap();
488            let arm_idx = if value < &constrain_value { 0 } else { 1 };
489            let output = info.arms[arm_idx].var_ids[0];
490            Some((
491                Some(self.propagate_const_and_get_statement(value.clone(), output, nz_ty)),
492                FlatBlockEnd::Goto(info.arms[arm_idx].block_id, Default::default()),
493            ))
494        } else if id == self.array_get {
495            if self.as_int(info.inputs[1].var_id)?.is_zero() {
496                if let [success, failure] = info.arms.as_mut_slice() {
497                    let arr = info.inputs[0].var_id;
498                    let unused_arr_output0 = self.variables.alloc(self.variables[arr].clone());
499                    let unused_arr_output1 = self.variables.alloc(self.variables[arr].clone());
500                    info.inputs.truncate(1);
501                    info.function = ModuleHelper { db: self.db.upcast(), id: self.array_module }
502                        .function_id("array_snapshot_pop_front", generic_args)
503                        .lowered(self.db);
504                    success.var_ids.insert(0, unused_arr_output0);
505                    failure.var_ids.insert(0, unused_arr_output1);
506                }
507            }
508            None
509        } else {
510            None
511        }
512    }
513
514    /// Returns the const value of a variable if it exists.
515    fn as_const(&self, var_id: VariableId) -> Option<&ConstValue> {
516        try_extract_matches!(self.var_info.get(&var_id)?, VarInfo::Const)
517    }
518
519    /// Return the const value as an int if it exists and is an integer, additionally, if it is of a
520    /// non-zero type.
521    fn as_int_ex(&self, var_id: VariableId) -> Option<(&BigInt, bool)> {
522        match self.as_const(var_id)? {
523            ConstValue::Int(value, _) => Some((value, false)),
524            ConstValue::NonZero(const_value) => {
525                if let ConstValue::Int(value, _) = const_value.as_ref() {
526                    Some((value, true))
527                } else {
528                    None
529                }
530            }
531            _ => None,
532        }
533    }
534
535    /// Return the const value as a int if it exists and is an integer.
536    fn as_int(&self, var_id: VariableId) -> Option<&BigInt> {
537        Some(self.as_int_ex(var_id)?.0)
538    }
539
540    /// Replaces the inputs in place if they are in the var_info map.
541    fn maybe_replace_inputs(&mut self, inputs: &mut [VarUsage]) {
542        for input in inputs {
543            self.maybe_replace_input(input);
544        }
545    }
546
547    /// Replaces the input in place if it is in the var_info map.
548    fn maybe_replace_input(&mut self, input: &mut VarUsage) {
549        if let Some(VarInfo::Var(new_var)) = self.var_info.get(&input.var_id) {
550            *input = *new_var;
551        }
552    }
553}
554
555/// Query implementation of [LoweringGroup::priv_const_folding_info].
556pub fn priv_const_folding_info(
557    db: &dyn LoweringGroup,
558) -> Arc<crate::optimizations::const_folding::ConstFoldingLibfuncInfo> {
559    Arc::new(ConstFoldingLibfuncInfo::new(db))
560}
561
562/// Holds static information about libfuncs required for the optimization.
563#[derive(Debug, PartialEq, Eq)]
564pub struct ConstFoldingLibfuncInfo {
565    /// The `felt252_sub` libfunc.
566    felt_sub: ExternFunctionId,
567    /// The `into_box` libfunc.
568    into_box: ExternFunctionId,
569    /// The `upcast` libfunc.
570    upcast: ExternFunctionId,
571    /// The `downcast` libfunc.
572    downcast: ExternFunctionId,
573    /// The set of functions that check if a number is zero.
574    nz_fns: OrderedHashSet<ExternFunctionId>,
575    /// The set of functions that check if numbers are equal.
576    eq_fns: OrderedHashSet<ExternFunctionId>,
577    /// The set of functions to add unsigned ints.
578    uadd_fns: OrderedHashSet<ExternFunctionId>,
579    /// The set of functions to subtract unsigned ints.
580    usub_fns: OrderedHashSet<ExternFunctionId>,
581    /// The set of functions to get the difference of signed ints.
582    diff_fns: OrderedHashSet<ExternFunctionId>,
583    /// The set of functions to add signed ints.
584    iadd_fns: OrderedHashSet<ExternFunctionId>,
585    /// The set of functions to subtract signed ints.
586    isub_fns: OrderedHashSet<ExternFunctionId>,
587    /// The set of functions to multiply integers.
588    wide_mul_fns: OrderedHashSet<ExternFunctionId>,
589    /// The set of functions to divide and get the remainder of integers.
590    div_rem_fns: OrderedHashSet<ExternFunctionId>,
591    /// The `bounded_int_add` libfunc.
592    bounded_int_add: ExternFunctionId,
593    /// The `bounded_int_sub` libfunc.
594    bounded_int_sub: ExternFunctionId,
595    /// The `bounded_int_constrain` libfunc.
596    bounded_int_constrain: ExternFunctionId,
597    /// The array module.
598    array_module: ModuleId,
599    /// The `array_get` libfunc.
600    array_get: ExternFunctionId,
601    /// The storage access module.
602    storage_access_module: ModuleId,
603    /// The `storage_base_address_from_felt252` libfunc.
604    storage_base_address_from_felt252: ExternFunctionId,
605    /// The `core::panic_with_felt252` function.
606    panic_with_felt252: FunctionId,
607    /// Type ranges.
608    type_value_ranges: OrderedHashMap<TypeId, TypeInfo>,
609}
610impl ConstFoldingLibfuncInfo {
611    fn new(db: &dyn LoweringGroup) -> Self {
612        let core = ModuleHelper::core(db.upcast());
613        let felt_sub = core.extern_function_id("felt252_sub");
614        let box_module = core.submodule("box");
615        let into_box = box_module.extern_function_id("into_box");
616        let integer_module = core.submodule("integer");
617        let bounded_int_module = core.submodule("internal").submodule("bounded_int");
618        let upcast = integer_module.extern_function_id("upcast");
619        let downcast = integer_module.extern_function_id("downcast");
620        let array_module = core.submodule("array");
621        let array_get = array_module.extern_function_id("array_get");
622        let starknet_module = core.submodule("starknet");
623        let storage_access_module = starknet_module.submodule("storage_access");
624        let storage_base_address_from_felt252 =
625            storage_access_module.extern_function_id("storage_base_address_from_felt252");
626        let nz_fns = OrderedHashSet::<_>::from_iter(chain!(
627            [
628                core.extern_function_id("felt252_is_zero"),
629                bounded_int_module.extern_function_id("bounded_int_is_zero")
630            ],
631            ["u8", "u16", "u32", "u64", "u128", "u256", "i8", "i16", "i32", "i64", "i128"]
632                .map(|ty| integer_module.extern_function_id(format!("{ty}_is_zero")))
633        ));
634        let utypes = ["u8", "u16", "u32", "u64", "u128"];
635        let itypes = ["i8", "i16", "i32", "i64", "i128"];
636        let eq_fns = OrderedHashSet::<_>::from_iter(
637            chain!(utypes, itypes).map(|ty| integer_module.extern_function_id(format!("{ty}_eq"))),
638        );
639        let uadd_fns = OrderedHashSet::<_>::from_iter(
640            utypes.map(|ty| integer_module.extern_function_id(format!("{ty}_overflowing_add"))),
641        );
642        let usub_fns = OrderedHashSet::<_>::from_iter(
643            utypes.map(|ty| integer_module.extern_function_id(format!("{ty}_overflowing_sub"))),
644        );
645        let diff_fns = OrderedHashSet::<_>::from_iter(
646            itypes.map(|ty| integer_module.extern_function_id(format!("{ty}_diff"))),
647        );
648        let iadd_fns = OrderedHashSet::<_>::from_iter(
649            itypes
650                .map(|ty| integer_module.extern_function_id(format!("{ty}_overflowing_add_impl"))),
651        );
652        let isub_fns = OrderedHashSet::<_>::from_iter(
653            itypes
654                .map(|ty| integer_module.extern_function_id(format!("{ty}_overflowing_sub_impl"))),
655        );
656        let wide_mul_fns = OrderedHashSet::<_>::from_iter(chain!(
657            [bounded_int_module.extern_function_id("bounded_int_mul")],
658            ["u8", "u16", "u32", "u64", "i8", "i16", "i32", "i64"]
659                .map(|ty| integer_module.extern_function_id(format!("{ty}_wide_mul"))),
660        ));
661        let div_rem_fns = OrderedHashSet::<_>::from_iter(chain!(
662            [bounded_int_module.extern_function_id("bounded_int_div_rem")],
663            utypes.map(|ty| integer_module.extern_function_id(format!("{ty}_safe_divmod"))),
664        ));
665        let bounded_int_add = bounded_int_module.extern_function_id("bounded_int_add");
666        let bounded_int_sub = bounded_int_module.extern_function_id("bounded_int_sub");
667        let bounded_int_constrain = bounded_int_module.extern_function_id("bounded_int_constrain");
668        let type_value_ranges = OrderedHashMap::from_iter(
669            [
670                ("u8", BigInt::ZERO, u8::MAX.into()),
671                ("u16", BigInt::ZERO, u16::MAX.into()),
672                ("u32", BigInt::ZERO, u32::MAX.into()),
673                ("u64", BigInt::ZERO, u64::MAX.into()),
674                ("u128", BigInt::ZERO, u128::MAX.into()),
675                ("u256", BigInt::ZERO, BigInt::from(1) << 256),
676                ("i8", i8::MIN.into(), i8::MAX.into()),
677                ("i16", i16::MIN.into(), i16::MAX.into()),
678                ("i32", i32::MIN.into(), i32::MAX.into()),
679                ("i64", i64::MIN.into(), i64::MAX.into()),
680                ("i128", i128::MIN.into(), i128::MAX.into()),
681            ]
682            .map(|(ty, min, max): (&str, BigInt, BigInt)| {
683                let info = TypeInfo {
684                    min,
685                    max,
686                    is_zero: integer_module
687                        .function_id(format!("{ty}_is_zero"), vec![])
688                        .lowered(db),
689                };
690                (corelib::get_core_ty_by_name(db.upcast(), ty.into(), vec![]), info)
691            }),
692        );
693        Self {
694            felt_sub,
695            into_box,
696            upcast,
697            downcast,
698            nz_fns,
699            eq_fns,
700            uadd_fns,
701            usub_fns,
702            diff_fns,
703            iadd_fns,
704            isub_fns,
705            wide_mul_fns,
706            div_rem_fns,
707            bounded_int_add,
708            bounded_int_sub,
709            bounded_int_constrain,
710            array_module: array_module.id,
711            array_get,
712            storage_access_module: storage_access_module.id,
713            storage_base_address_from_felt252,
714            panic_with_felt252: core.function_id("panic_with_felt252", vec![]).lowered(db),
715            type_value_ranges,
716        }
717    }
718}
719
720impl std::ops::Deref for ConstFoldingContext<'_> {
721    type Target = ConstFoldingLibfuncInfo;
722    fn deref(&self) -> &ConstFoldingLibfuncInfo {
723        self.libfunc_info
724    }
725}
726
727/// The information of a type required for const foldings.
728#[derive(Debug, PartialEq, Eq)]
729struct TypeInfo {
730    /// The minimum value of the type.
731    min: BigInt,
732    /// The maximum value of the type.
733    max: BigInt,
734    /// The function to check if the value is zero for the type.
735    is_zero: FunctionId,
736}
737impl TypeInfo {
738    /// Normalizes the value to the range.
739    /// Assumes the value is within size of range of the range.
740    fn normalized(&self, value: BigInt) -> NormalizedResult {
741        if value < self.min {
742            NormalizedResult::Under(value - &self.min + &self.max + 1)
743        } else if value > self.max {
744            NormalizedResult::Over(value + &self.min - &self.max - 1)
745        } else {
746            NormalizedResult::InRange(value)
747        }
748    }
749}
750
751/// The result of normalizing a value to a range.
752enum NormalizedResult {
753    /// The original value is in the range, carries the value, or an equivalent value.
754    InRange(BigInt),
755    /// The original value is larger than range max, carries the normalized value.
756    Over(BigInt),
757    /// The original value is smaller than range min, carries the normalized value.
758    Under(BigInt),
759}
cairo_lang_lowering/optimizations/const_folding.rs

cairo_lang_lowering/optimizations/
const_folding.rs
