1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#[cfg(test)]
#[path = "trim_unused_params_test.rs"]
mod test;
use cairo_lang_diagnostics::Maybe;
use salsa::Database;
use crate::analysis::UseLocation;
use crate::analysis::use_sites::UseSites;
use crate::db::LoweringGroup;
use crate::ids::{
ConcreteFunctionWithBodyId, ConcreteFunctionWithBodyLongId, GeneratedFunction,
GeneratedFunctionKey,
};
use crate::optimizations::config::Optimizations;
use crate::{Lowered, LoweringStage, Statement};
/// Returns the sorted positions of the parameters of the function that are never used by its
/// body, based on the [LoweringStage::PostBaseline] lowering.
#[salsa::tracked(returns(ref))]
fn unused_parameters<'db>(
db: &'db dyn Database,
function: ConcreteFunctionWithBodyId<'db>,
) -> Vec<usize> {
let Ok(lowered) = db.lowered_body(function, LoweringStage::PostBaseline) else {
return vec![];
};
if lowered.blocks.is_empty() {
return vec![];
}
let use_sites = UseSites::analyze(lowered);
lowered
.parameters
.iter()
.enumerate()
.filter(|(position, param)| {
// Trimming a parameter leaves the value unconsumed at every call site, so only
// droppable parameters may be trimmed. Undroppable params are otherwise guaranteed a
// destruct use, but a param threaded into the recursion is consumed by the call, so
// droppability must be checked explicitly.
lowered.variables[**param].info.droppable.is_ok()
&& use_sites.use_locs(**param).all(|(loc, count)| {
// A parameter whose only use at a location is being passed to a recursive
// call of the function at its own position is merely threaded through the
// recursion, so it is not considered a use - if the parameter has no other
// use, the entire chain is dead.
// Note that the coupon input, if present, is beyond the parameters and is
// therefore always considered used.
if count == 1
&& let UseLocation::Statement((block_id, stmt_idx)) = loc
&& let Statement::Call(call_stmt) =
&lowered.blocks[block_id].statements[stmt_idx]
&& call_stmt.function.body(db) == Ok(Some(function))
&& call_stmt.inputs.get(*position).map(|input| input.var_id)
== Some(**param)
{
true
} else {
false
}
})
})
.map(|(position, _)| position)
.collect()
}
/// Removes parameters that are never used by the function's body, from both the function's
/// signature and from every call site.
///
/// Note that the removed positions refer to the `PostBaseline` stage layout, so this phase is
/// not idempotent and must be applied exactly once, directly on the `PostBaseline` lowering.
pub fn trim_unused_params<'db>(
db: &'db dyn Database,
function: ConcreteFunctionWithBodyId<'db>,
lowered: &mut Lowered<'db>,
) -> Maybe<()> {
// The `TrimUnusedParams` phase is only part of the enabled optimization strategy, so when
// optimizations are disabled no parameter is trimmed.
if matches!(db.optimizations(), Optimizations::Disabled) {
return Ok(());
}
// Only compiler-generated loop functions and specialized functions are trimmed, as trimming
// the parameters of a user-visible function would change its externally callable signature.
let trimmable = |function: ConcreteFunctionWithBodyId<'db>| {
matches!(
function.long(db),
ConcreteFunctionWithBodyLongId::Generated(GeneratedFunction {
key: GeneratedFunctionKey::Loop(_),
..
}) | ConcreteFunctionWithBodyLongId::Specialized(_)
)
};
if trimmable(function) {
let unused = unused_parameters(db, function);
if !unused.is_empty() {
debug_assert_eq!(lowered.parameters.len(), lowered.signature.params.len());
remove_indices(&mut lowered.parameters, unused);
remove_indices(&mut lowered.signature.params, unused);
}
}
for block in lowered.blocks.iter_mut() {
for stmt in block.statements.iter_mut() {
if let Statement::Call(call_stmt) = stmt
&& let Some(callee) = call_stmt.function.body(db)?
&& trimmable(callee)
{
remove_indices(&mut call_stmt.inputs, unused_parameters(db, callee));
}
}
}
Ok(())
}
/// Removes the elements at the given sorted `indices` from `vec`.
fn remove_indices<T>(vec: &mut Vec<T>, indices: &[usize]) {
for idx in indices.iter().rev() {
vec.remove(*idx);
}
}