Sitelet https://github.com/starkware-libs/cairo/commit/1292dc5564b1d9f21eca6108f94f2c92fcf35c65
Skip to content

Commit 1292dc5

Browse files
eytan-starkwareeytan-starkware
committed
(optimization): non-copy variable forwarding with chain removal
1 parent 691dece commit 1292dc5

27 files changed

Lines changed: 11770 additions & 10045 deletions

‎.gitignore‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -12,3 +12,4 @@ ensure-no_std/Cargo.lock
1212
ensure-no_std/target/
1313

1414
.claude/settings.local.json
15+
.reviews/

‎crates/cairo-lang-lowering/src/analysis/use_sites.rs‎

Lines changed: 19 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -3,10 +3,11 @@
33
//! Tracks where each variable is used (statement inputs and block-end inputs).
44
//! Updated incrementally as forwarding runs, so later checks see current use counts.
55
//!
6-
//! A use is identified by the `(variable, UseLocation)` pair: a single statement
7-
//! that consumes the same variable in multiple input slots (e.g. `felt252_add(v, v)`)
8-
//! is recorded once. This matches forwarding's rename semantics — a single rename
9-
//! at a `UseLocation` rewrites every input slot at that location.
6+
//! Each `(variable, UseLocation)` pair stores a multiplicity: the number of input
7+
//! slots consuming the variable at that location (e.g. `felt252_add(v, v)` records `v`
8+
//! at that location with count 2). `use_count` sums these, so it is the total number
9+
//! of consuming slots. A rename rewrites every slot at a location at once, so moving a
10+
//! variable's uses to another (see `move_uses`) transfers the whole per-location count.
1011
1112
use cairo_lang_utils::ordered_hash_map::{Entry, OrderedHashMap};
1213

@@ -56,30 +57,26 @@ impl UseSites {
5657
Self { sites }
5758
}
5859

59-
/// Returns how many distinct use sites remain for `var`.
60+
/// Returns the total number of consuming slots remaining for `var` (the summed
61+
/// multiplicity across all of its use-site locations).
6062
pub fn use_count(&self, var: VariableId) -> usize {
6163
self.sites[var.index()].iter().map(|(_, count)| *count).sum()
6264
}
6365

64-
/// Removes the use of `var` at `loc`. Idempotent.
65-
pub fn remove_use(&mut self, var: VariableId, loc: UseLocation) {
66-
match self.sites[var.index()].entry(loc) {
67-
Entry::Occupied(mut entry) => {
68-
*entry.get_mut() -= 1;
69-
if *entry.get() == 0 {
70-
entry.swap_remove();
71-
}
72-
}
73-
Entry::Vacant(_) => {}
74-
}
75-
}
76-
77-
/// Adds a use of `var` at `loc`. Idempotent.
78-
pub fn add_use(&mut self, var: VariableId, loc: UseLocation) {
79-
*self.sites[var.index()].entry(loc).or_default() += 1;
66+
/// Moves all uses of `from` at `loc` to `to`, mirroring a rename that rewrites
67+
/// every consuming slot at that location in one go: the whole per-location count is
68+
/// transferred and added to any uses `to` already has there. No-op if `from` has no
69+
/// use at `loc`.
70+
pub fn move_uses(&mut self, from: VariableId, to: VariableId, loc: UseLocation) {
71+
let Entry::Occupied(entry) = self.sites[from.index()].entry(loc) else {
72+
return;
73+
};
74+
let count = entry.swap_remove();
75+
*self.sites[to.index()].entry(loc).or_default() += count;
8076
}
8177

82-
/// Returns the use-site locations for `var`.
78+
/// Returns each use-site location for `var` together with its multiplicity (the
79+
/// number of consuming slots at that location).
8380
pub fn use_locs(
8481
&self,
8582
var: VariableId,

‎crates/cairo-lang-lowering/src/lower/test_data/loop‎

Lines changed: 12 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -3439,18 +3439,17 @@ End:
34393439
blk3:
34403440
Statements:
34413441
(v13: core::gas::GasBuiltin) <- core::gas::redeposit_gas(v3)
3442-
(v14: core::result::Result::<(), core::integer::u32>) <- Result::Err(v8)
3443-
(v15: (core::result::Result::<(), core::integer::u32>,)) <- struct_construct(v14)
3444-
(v16: core::panics::PanicResult::<(core::result::Result::<(), core::integer::u32>,)>) <- PanicResult::Ok(v15)
3442+
(v14: (core::result::Result::<(), core::integer::u32>,)) <- struct_construct(v6)
3443+
(v15: core::panics::PanicResult::<(core::result::Result::<(), core::integer::u32>,)>) <- PanicResult::Ok(v14)
34453444
End:
3446-
Return(v2, v13, v16)
3445+
Return(v2, v13, v15)
34473446

34483447
blk4:
34493448
Statements:
3450-
(v17: (core::panics::Panic, core::array::Array::<core::felt252>)) <- core::panic_with_const_felt252::<375233589013918064796019>()
3451-
(v18: core::panics::PanicResult::<(core::result::Result::<(), core::integer::u32>,)>) <- PanicResult::Err(v17)
3449+
(v16: (core::panics::Panic, core::array::Array::<core::felt252>)) <- core::panic_with_const_felt252::<375233589013918064796019>()
3450+
(v17: core::panics::PanicResult::<(core::result::Result::<(), core::integer::u32>,)>) <- PanicResult::Err(v16)
34523451
End:
3453-
Return(v4, v5, v18)
3452+
Return(v4, v5, v17)
34543453

34553454

34563455
Final lowering of specialized call "test::foo[30-63]":
@@ -3482,18 +3481,17 @@ End:
34823481
blk3:
34833482
Statements:
34843483
(v13: core::gas::GasBuiltin) <- core::gas::redeposit_gas(v3)
3485-
(v14: core::result::Result::<(), core::integer::u32>) <- Result::Err(v8)
3486-
(v15: (core::result::Result::<(), core::integer::u32>,)) <- struct_construct(v14)
3487-
(v16: core::panics::PanicResult::<(core::result::Result::<(), core::integer::u32>,)>) <- PanicResult::Ok(v15)
3484+
(v14: (core::result::Result::<(), core::integer::u32>,)) <- struct_construct(v6)
3485+
(v15: core::panics::PanicResult::<(core::result::Result::<(), core::integer::u32>,)>) <- PanicResult::Ok(v14)
34883486
End:
3489-
Return(v2, v13, v16)
3487+
Return(v2, v13, v15)
34903488

34913489
blk4:
34923490
Statements:
3493-
(v17: (core::panics::Panic, core::array::Array::<core::felt252>)) <- core::panic_with_const_felt252::<375233589013918064796019>()
3494-
(v18: core::panics::PanicResult::<(core::result::Result::<(), core::integer::u32>,)>) <- PanicResult::Err(v17)
3491+
(v16: (core::panics::Panic, core::array::Array::<core::felt252>)) <- core::panic_with_const_felt252::<375233589013918064796019>()
3492+
(v17: core::panics::PanicResult::<(core::result::Result::<(), core::integer::u32>,)>) <- PanicResult::Err(v16)
34953493
End:
3496-
Return(v4, v5, v18)
3494+
Return(v4, v5, v17)
34973495

34983496
//! > lowering_diagnostics
34993497

‎crates/cairo-lang-lowering/src/optimizations/mod.rs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -33,3 +33,4 @@ pub mod strategy;
3333
pub mod trim_unreachable;
3434
pub mod validate;
3535
pub mod var_renamer;
36+
pub mod variable_forwarding;

‎crates/cairo-lang-lowering/src/optimizations/strategy.rs‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -25,6 +25,7 @@ use crate::optimizations::remappings::optimize_remappings;
2525
use crate::optimizations::reorder_statements::reorder_statements;
2626
use crate::optimizations::return_optimization::return_optimization;
2727
use crate::optimizations::split_structs::split_structs;
28+
use crate::optimizations::variable_forwarding::variable_forwarding;
2829
use crate::reorganize_blocks::reorganize_blocks;
2930

3031
/// Enum of the optimization phases that can be used in a strategy.
@@ -47,6 +48,7 @@ pub enum OptimizationPhase<'db> {
4748
ReturnOptimization,
4849
SplitStructs,
4950
TrimUnreachable,
51+
VariableForwarding,
5052
GasRedeposit,
5153
/// The following is not really an optimization but we want to apply optimizations before and
5254
/// after it, so it is convenient to treat it as an optimization.
@@ -103,6 +105,7 @@ impl<'db> ApplyOptimization<'db> for OptimizationPhase<'db> {
103105
OptimizationPhase::ReturnOptimization => return_optimization(db, lowered),
104106
OptimizationPhase::SplitStructs => split_structs(lowered),
105107
OptimizationPhase::TrimUnreachable => trim_unreachable(db, lowered),
108+
OptimizationPhase::VariableForwarding => variable_forwarding(db, lowered),
106109
OptimizationPhase::LowerImplicits => lower_implicits(db, function, lowered),
107110
OptimizationPhase::GasRedeposit => gas_redeposit(db, function, lowered),
108111
OptimizationPhase::Validate => validate(lowered).unwrap_or_else(|err| {
@@ -190,6 +193,12 @@ pub fn baseline_optimization_strategy<'db>(db: &'db dyn Database) -> Optimizatio
190193
OptimizationPhase::ReorderStatements,
191194
OptimizationPhase::BranchInversion,
192195
OptimizationPhase::CancelOps,
196+
OptimizationPhase::ReorderStatements,
197+
OptimizationPhase::VariableForwarding,
198+
OptimizationPhase::ReorderStatements,
199+
OptimizationPhase::ReorganizeBlocks,
200+
OptimizationPhase::OptimizeMatches,
201+
OptimizationPhase::ReorderStatements,
193202
// Must be right before const folding.
194203
OptimizationPhase::ReorganizeBlocks,
195204
OptimizationPhase::ConstFolding,
@@ -201,6 +210,9 @@ pub fn baseline_optimization_strategy<'db>(db: &'db dyn Database) -> Optimizatio
201210
OptimizationPhase::ReorganizeBlocks,
202211
OptimizationPhase::Reboxing,
203212
OptimizationPhase::CancelOps,
213+
OptimizationPhase::ReorderStatements,
214+
OptimizationPhase::VariableForwarding,
215+
OptimizationPhase::ReorderStatements,
204216
OptimizationPhase::ReorganizeBlocks,
205217
// Performing CSE here after blocks are the most contiguous, to reach maximum
206218
// effect.

0 commit comments

Comments
 (0)