cairo_lang_lowering/graph_algorithms/
feedback_set.rs

1use cairo_lang_diagnostics::Maybe;
2use cairo_lang_filesystem::flag::FlagsGroup;
3use cairo_lang_utils::graph_algos::feedback_set::calc_feedback_set;
4use cairo_lang_utils::ordered_hash_set::OrderedHashSet;
5use salsa::Database;
6
7use super::concrete_function_node::ConcreteFunctionWithBodyNode;
8use crate::db::LoweringGroup;
9use crate::ids::ConcreteFunctionWithBodyId;
10use crate::{DependencyType, LoweringStage};
11
12/// Query implementation of [crate::db::LoweringGroup::function_with_body_feedback_set].
13#[salsa::tracked(returns(ref))]
14pub fn function_with_body_feedback_set<'db>(
15    db: &'db dyn Database,
16    function: ConcreteFunctionWithBodyId<'db>,
17    stage: LoweringStage,
18) -> Maybe<OrderedHashSet<ConcreteFunctionWithBodyId<'db>>> {
19    let r = db.lowered_scc_representative(function, DependencyType::Cost, stage);
20    function_with_body_feedback_set_of_representative(db, r.0, stage)
21}
22
23/// Query implementation of [crate::db::LoweringGroup::needs_withdraw_gas].
24#[salsa::tracked]
25pub fn needs_withdraw_gas<'db>(
26    db: &'db dyn Database,
27    function: ConcreteFunctionWithBodyId<'db>,
28) -> Maybe<bool> {
29    Ok(db.flag_add_withdraw_gas()
30        && db
31            .function_with_body_feedback_set(function, LoweringStage::Monomorphized)?
32            .contains(&function))
33}
34
35/// Returns the feedback-vertex-set of the given concrete-function SCC-representative. A
36/// feedback-vertex-set is the set of vertices whose removal leaves a graph without cycles.
37#[salsa::tracked]
38fn function_with_body_feedback_set_of_representative<'db>(
39    db: &'db dyn Database,
40    function_id: ConcreteFunctionWithBodyId<'db>,
41    stage: LoweringStage,
42) -> Maybe<OrderedHashSet<ConcreteFunctionWithBodyId<'db>>> {
43    Ok(calc_feedback_set(
44        ConcreteFunctionWithBodyNode {
45            function_id,
46            db,
47            dependency_type: DependencyType::Cost,
48            stage,
49        }
50        .into(),
51    ))
52}
cairo_lang_lowering/graph_algorithms/feedback_set.rs

cairo_lang_lowering/graph_algorithms/
feedback_set.rs
