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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
//! Optimization passes that reduce the amount of CPS code, therefore reducing
//! the amount of LLVM code that needs to be optimized.
use super::*;
impl Cps {
pub(super) fn reduce(self) -> Self {
// Perform beta reduction twice. This seems like the sweet spot for now
let mut uses_cache = HashMap::default();
self.beta_reduction(&mut uses_cache)
.beta_reduction(&mut uses_cache)
.dead_code_elimination(&mut uses_cache)
}
/// Beta-reduction optimization step. This function replaces applications to
/// functions with the body of the function with arguments substituted.
///
/// Our initial heuristic is rather simple: if a function is non-recursive and
/// is applied to exactly once in its continuation expression, its body is
/// substituted for the application.
///
/// The uses analysis cache is absolutely demolished and dangerous to use by
/// the end of this function.
fn beta_reduction(self, uses_cache: &mut HashMap<Local, HashMap<Local, usize>>) -> Self {
match self {
Cps::PrimOp(prim_op, values, result, cexp) => Cps::PrimOp(
prim_op,
values,
result,
Box::new(cexp.beta_reduction(uses_cache)),
),
Cps::If(cond, success, failure) => Cps::If(
cond,
Box::new(success.beta_reduction(uses_cache)),
Box::new(failure.beta_reduction(uses_cache)),
),
Cps::Lambda {
args,
body,
val,
cexp,
span,
} => {
let body = body.beta_reduction(uses_cache);
let mut cexp = cexp.beta_reduction(uses_cache);
let is_recursive = body.uses(uses_cache).contains_key(&val);
let uses = cexp.uses(uses_cache).get(&val).copied().unwrap_or(0);
if !is_recursive && uses == 1 {
let reduced = cexp.reduce_function(val, &args, &body, uses_cache);
if reduced {
return cexp;
}
}
Cps::Lambda {
args,
body: Box::new(body),
val,
cexp: Box::new(cexp),
span,
}
}
cexp => cexp,
}
}
fn reduce_function(
&mut self,
func: Local,
args: &LambdaArgs,
func_body: &Cps,
uses_cache: &mut HashMap<Local, HashMap<Local, usize>>,
) -> bool {
let new = match self {
Cps::PrimOp(_, _, _, cexp) => {
return cexp.reduce_function(func, args, func_body, uses_cache);
}
Cps::If(_, succ, fail) => {
return succ.reduce_function(func, args, func_body, uses_cache)
|| fail.reduce_function(func, args, func_body, uses_cache);
}
Cps::Lambda {
val, body, cexp, ..
} => {
let reduced = body.reduce_function(func, args, func_body, uses_cache)
|| cexp.reduce_function(func, args, func_body, uses_cache);
if reduced {
uses_cache.remove(val);
}
return reduced;
}
Cps::App(Value::Var(Var::Local(operator)), applied) if *operator == func => {
if args.variadic {
let (req, var) = applied.split_at(args.num_required());
let var_args = Local::gensym();
Cps::PrimOp(
PrimOp::List,
var.to_vec(),
var_args,
Box::new(substitute(
func_body.clone(),
args,
req.iter().cloned().chain(Some(Value::from(var_args))),
uses_cache,
)),
)
} else if args.num_required() == applied.len() {
substitute(func_body.clone(), args, applied.iter().cloned(), uses_cache)
} else {
// It's an error if the number of arguments don't match but
// defer until evaluation to raise it.
return false;
}
}
Cps::App(_, _) | Cps::Halt(_) => return false,
};
*self = new;
true
}
/// Removes any closures and allocated cells that are left unused.
#[allow(dead_code)]
fn dead_code_elimination(self, uses_cache: &mut HashMap<Local, HashMap<Local, usize>>) -> Self {
match self {
Cps::Lambda { val, cexp, .. } if !cexp.uses(uses_cache).contains_key(&val) => {
// Unused closure can be eliminated
cexp.dead_code_elimination(uses_cache)
}
Cps::PrimOp(PrimOp::AllocCell, _, result, cexp)
if !cexp.uses(uses_cache).contains_key(&result) =>
{
cexp.dead_code_elimination(uses_cache)
}
Cps::PrimOp(prim_op, values, result, cexp) => Cps::PrimOp(
prim_op,
values,
result,
Box::new(cexp.dead_code_elimination(uses_cache)),
),
Cps::If(cond, success, failure) => Cps::If(
cond,
Box::new(success.dead_code_elimination(uses_cache)),
Box::new(failure.dead_code_elimination(uses_cache)),
),
Cps::Lambda {
args,
body,
val,
cexp,
span,
} => Cps::Lambda {
args,
body: Box::new(body.dead_code_elimination(uses_cache)),
val,
cexp: Box::new(cexp.dead_code_elimination(uses_cache)),
span,
},
cexp => cexp,
}
}
}
fn substitute(
mut body: Cps,
args: &LambdaArgs,
applied: impl Iterator<Item = Value>,
uses_cache: &mut HashMap<Local, HashMap<Local, usize>>,
) -> Cps {
let substitutions = args.iter().copied().zip(applied).collect::<HashMap<_, _>>();
body.substitute(&substitutions, uses_cache);
body
}