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

Commit ea673ed

Browse files
oriziorizi
committed
performance(lowering): Avoid cloning blocks and analysis info in inlining and dataflow.
 Reduce heap allocations in the lowering pipeline by removing redundant copies: - inline: seed the BlocksBuilder by moving the existing blocks in via the new `Blocks::into_builder` (mem::take) instead of deep-cloning every block, since `lowered.blocks` is overwritten at the end of the pass anyway. - analysis/backward: back the per-block info cache with a `Vec<Option<Info>>` indexed by `BlockId` instead of an `UnorderedHashMap`, dropping the hashing and per-entry allocation. - analysis/forward: move the incoming info out with `take()` rather than `clone()`, since each block's slot is dead once the block is processed. Measured on corelib -> Sierra (dhat): -33.7 MB allocated (-3.7%) and -140,744 allocations (-2.2%); peak heap unchanged.
1 parent 0077583 commit ea673ed

4 files changed

Lines changed: 26 additions & 45 deletions

File tree

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

Lines changed: 8 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -1,25 +1,19 @@
11
//! This module introduces the BackAnalysis utility that allows writing analyzers that go backwards
22
//! in the flow of the program, on a Lowered representation.
33
4-
use cairo_lang_utils::unordered_hash_map::UnorderedHashMap;
5-
64
use crate::analysis::{Analyzer, DataflowAnalyzer, Direction, Edge, StatementLocation};
75
use crate::{Block, BlockEnd, BlockId, Lowered, MatchInfo, Statement, VarRemapping, VarUsage};
86

97
/// Main analysis type that allows traversing the flow backwards.
108
pub struct BackAnalysis<'db, 'a, TAnalyzer: Analyzer<'db, 'a>> {
119
lowered: &'a Lowered<'db>,
1210
pub analyzer: TAnalyzer,
13-
block_info: UnorderedHashMap<BlockId, TAnalyzer::Info>,
11+
block_info: Vec<Option<TAnalyzer::Info>>,
1412
}
1513
impl<'db, 'a, TAnalyzer: Analyzer<'db, 'a>> BackAnalysis<'db, 'a, TAnalyzer> {
1614
/// Creates a new BackAnalysis instance.
1715
pub fn new(lowered: &'a Lowered<'db>, analyzer: TAnalyzer) -> Self {
18-
Self {
19-
lowered,
20-
analyzer,
21-
block_info: UnorderedHashMap::with_capacity(lowered.blocks.len()),
22-
}
16+
Self { lowered, analyzer, block_info: vec![None; lowered.blocks.len()] }
2317
}
2418
/// Gets the analysis info for the entire function.
2519
pub fn get_root_info(&mut self) -> TAnalyzer::Info {
@@ -31,7 +25,7 @@ impl<'db, 'a, TAnalyzer: Analyzer<'db, 'a>> BackAnalysis<'db, 'a, TAnalyzer> {
3125
self.calc_block_info(dfs_stack.pop().unwrap());
3226
}
3327
}
34-
self.block_info.remove(&BlockId::root()).unwrap()
28+
self.block_info[BlockId::root().0].take().unwrap()
3529
}
3630

3731
/// Gets the analysis info from the start of a block.
@@ -47,7 +41,7 @@ impl<'db, 'a, TAnalyzer: Analyzer<'db, 'a>> BackAnalysis<'db, 'a, TAnalyzer> {
4741
self.analyzer.visit_block_start(&mut info, block_id, &self.lowered.blocks[block_id]);
4842

4943
// Store result.
50-
self.block_info.insert(block_id, info);
44+
self.block_info[block_id.0] = Some(info);
5145
}
5246

5347
/// Adds to the DFS stack the dependent blocks that are not yet in cache - returns whether
@@ -59,17 +53,15 @@ impl<'db, 'a, TAnalyzer: Analyzer<'db, 'a>> BackAnalysis<'db, 'a, TAnalyzer> {
5953
) -> bool {
6054
match block_end {
6155
BlockEnd::NotSet => unreachable!(),
62-
BlockEnd::Goto(target_block_id, _)
63-
if !self.block_info.contains_key(target_block_id) =>
64-
{
56+
BlockEnd::Goto(target_block_id, _) if self.block_info[target_block_id.0].is_none() => {
6557
dfs_stack.push(*target_block_id);
6658
true
6759
}
6860
BlockEnd::Goto(_, _) | BlockEnd::Return(..) | BlockEnd::Panic(_) => false,
6961
BlockEnd::Match { info } => {
7062
let mut missing_cache = false;
7163
for arm in info.arms() {
72-
if !self.block_info.contains_key(&arm.block_id) {
64+
if self.block_info[arm.block_id.0].is_none() {
7365
dfs_stack.push(arm.block_id);
7466
missing_cache = true;
7567
}
@@ -86,7 +78,7 @@ impl<'db, 'a, TAnalyzer: Analyzer<'db, 'a>> BackAnalysis<'db, 'a, TAnalyzer> {
8678
match block_end {
8779
BlockEnd::NotSet => unreachable!(),
8880
BlockEnd::Goto(target_block_id, remapping) => {
89-
let mut info = self.block_info[target_block_id].clone();
81+
let mut info = self.block_info[target_block_id.0].clone().unwrap();
9082
self.analyzer.visit_goto(
9183
&mut info,
9284
statement_location,
@@ -102,7 +94,7 @@ impl<'db, 'a, TAnalyzer: Analyzer<'db, 'a>> BackAnalysis<'db, 'a, TAnalyzer> {
10294
BlockEnd::Match { info } => {
10395
// Can remove the block since match blocks do not merge.
10496
let arm_infos =
105-
info.arms().iter().map(|arm| self.block_info.remove(&arm.block_id).unwrap());
97+
info.arms().iter().map(|arm| self.block_info[arm.block_id.0].take().unwrap());
10698
self.analyzer.merge_match(statement_location, info, arm_infos)
10799
}
108100
}

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

Lines changed: 3 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -53,19 +53,18 @@ impl<'db, 'a, TAnalyzer: DataflowAnalyzer<'db, 'a>> ForwardDataflowAnalysis<'db,
5353
while let Some(block_id) = ready.pop() {
5454
let block = &self.lowered.blocks[block_id];
5555

56-
// Get entry info from incoming edges.
57-
let mut info = self.incoming[block_id.0].clone().unwrap();
56+
// Get entry info from incoming edges. Can move out, since we are working in
57+
// topological order.
58+
let mut info = self.incoming[block_id.0].take().unwrap();
5859

5960
// Process block.
6061
self.analyzer.visit_block_start(&mut info, block_id, block);
6162
self.analyzer.transfer_block(&mut info, block_id, block);
6263

6364
// Transfer to successors and check readiness.
6465
self.propagate_to_successors(block_id, &info, &mut ready);
65-
6666
block_info[block_id.0] = Some(info);
6767
}
68-
6968
block_info
7069
}
7170

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

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -179,7 +179,7 @@ fn test_block_level_analysis() {
179179

180180
let analyzer = BlockCounter::default();
181181
let mut analysis = ForwardDataflowAnalysis::new(lowered, analyzer);
182-
let _ = analysis.run();
182+
analysis.run();
183183

184184
// Block-level analyzer should have counted multiple blocks
185185
assert!(
@@ -206,7 +206,7 @@ fn test_forward_single_block() {
206206

207207
let analyzer = ReachabilityAnalyzer::default();
208208
let mut analysis = ForwardDataflowAnalysis::new(lowered, analyzer);
209-
let _ = analysis.run();
209+
analysis.run();
210210

211211
// Should have visited at least the root block
212212
assert!(!analysis.analyzer.reachable_blocks.is_empty());
@@ -234,7 +234,7 @@ fn test_forward_with_branching() {
234234

235235
let analyzer = ReachabilityAnalyzer::default();
236236
let mut analysis = ForwardDataflowAnalysis::new(lowered, analyzer);
237-
let exit_info = analysis.run().clone();
237+
let exit_info = analysis.run();
238238

239239
// With branching, should visit multiple blocks
240240
assert!(

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

Lines changed: 12 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,7 @@ use cairo_lang_utils::unordered_hash_map::UnorderedHashMap;
1414
use itertools::{Itertools, zip_eq};
1515
use salsa::Database;
1616

17-
use crate::blocks::{Blocks, BlocksBuilder};
17+
use crate::blocks::Blocks;
1818
use crate::db::LoweringGroup;
1919
use crate::diagnostic::{
2020
LoweringDiagnostic, LoweringDiagnosticKind, LoweringDiagnostics, LoweringDiagnosticsBuilder,
@@ -221,40 +221,31 @@ impl<'db, 'mt> Rebuilder<'db> for Mapper<'db, 'mt, '_> {
221221
/// error case.
222222
fn inner_apply_inlining<'db>(
223223
db: &'db dyn Database,
224-
lowered: &mut Lowered<'db>,
224+
Lowered { blocks, variables, .. }: &mut Lowered<'db>,
225225
calling_function_id: ConcreteFunctionWithBodyId<'db>,
226226
mut enable_const_folding: bool,
227227
) -> Maybe<()> {
228-
lowered.blocks.has_root()?;
229-
230-
let mut blocks: BlocksBuilder<'db> = BlocksBuilder::new();
228+
blocks.has_root()?;
231229

232-
let mut stack: Vec<std::vec::IntoIter<BlockId>> = vec![
233-
lowered
234-
.blocks
235-
.iter()
236-
.map(|(_, block)| blocks.alloc(block.clone()))
237-
.collect_vec()
238-
.into_iter(),
239-
];
230+
let mut stack: Vec<std::vec::IntoIter<BlockId>> =
231+
vec![(0..blocks.len()).map(BlockId).collect_vec().into_iter()];
240232

241-
let mut const_folding_ctx =
242-
ConstFoldingContext::new(db, calling_function_id, &mut lowered.variables);
233+
let mut const_folding_ctx = ConstFoldingContext::new(db, calling_function_id, variables);
243234

244235
enable_const_folding = enable_const_folding && !const_folding_ctx.should_skip_const_folding(db);
245236

246237
while let Some(mut func_blocks) = stack.pop() {
247238
for block_id in func_blocks.by_ref() {
248-
let blocks = &mut blocks;
239+
let blocks = &mut *blocks;
249240
if enable_const_folding
250-
&& !const_folding_ctx.visit_block_start(block_id, |block_id| &blocks.0[block_id.0])
241+
&& !const_folding_ctx.visit_block_start(block_id, |block_id| &blocks[block_id])
251242
{
252243
continue;
253244
}
254245

255246
// Read the next block id before `blocks` is borrowed.
256247
let next_block_id = blocks.len();
257-
let block = blocks.get_mut_block(block_id);
248+
let block = &mut blocks[block_id];
258249

259250
let mut opt_inline_info = None;
260251
for (idx, statement) in block.statements.iter_mut().enumerate() {
@@ -303,16 +294,16 @@ fn inner_apply_inlining<'db>(
303294
);
304295

305296
// Apply the mapper to the inlined blocks and add them as a contiguous chunk to the
306-
// blocks builder.
297+
// blocks.
307298
let mut inlined_blocks_ids = inlined_lowered
308299
.blocks
309300
.iter()
310-
.map(|(_block_id, block)| blocks.alloc(inline_mapper.rebuild_block(block)))
301+
.map(|(_block_id, block)| blocks.push(inline_mapper.rebuild_block(block)))
311302
.collect_vec();
312303

313304
// Move the remaining statements and the original block end to a new return block.
314305
let return_block_id =
315-
blocks.alloc(Block { statements: remaining_statements, end: orig_block_end });
306+
blocks.push(Block { statements: remaining_statements, end: orig_block_end });
316307
assert_eq!(return_block_id, inline_mapper.return_block_id);
317308

318309
// Append the id of the return block to the list of blocks in the inlined function.
@@ -328,7 +319,6 @@ fn inner_apply_inlining<'db>(
328319
}
329320
}
330321

331-
lowered.blocks = blocks.build().unwrap();
332322
Ok(())
333323
}
334324

0 commit comments

Comments
 (0)