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
//! This module contains miscellaneous conveniences for performing dataflow analysis on code
//! sequences.
use crate::Sequence;
use crate::StaticAnalysis;
/// Implement this trait on an instruction to communicate that the instruction reads from or writes
/// to a datum of some type. For example, if you have a type representing the register file, and
/// some type represents the machine's instruction, these methods can communicate what use the
/// instruction makes of each register.
pub trait DataFlow<Datum> {
/// Returns `true` iff the instruction reads from `datum`.
fn reads(&self, datum: &Datum) -> bool;
/// Returns `true` iff the instruction writes to `datum`.
fn writes(&self, datum: &Datum) -> bool;
/// Returns a `StaticAnalysis` for advancing the instruction.
fn sa(&self) -> StaticAnalysis<Self>
where
Self: Sized;
}
/// Returns a static analysis modifying any instructions that read from or writes to `datum`.
pub fn leave_alone<Datum, Insn: DataFlow<Datum>>(
sequence: &Sequence<Insn>,
datum: &Datum,
) -> Result<(), StaticAnalysis<Insn>> {
sequence
.iter()
.enumerate()
.find(|(_offs, i)| i.reads(datum) || i.writes(datum))
.map(|(offs, i)| i.sa().set_offset(offs))
.map_or(Ok(()), Err)
}
/// Returns a static analysis modifying any instructions that read from or writes to `datum`, but
/// ignores the last instruction in the sequence. Handy for cases like leaf subroutines on MIPS or ARM,
/// where only the last instruction should use the link register.
pub fn leave_alone_except_last<Datum, Insn: DataFlow<Datum>>(
sequence: &Sequence<Insn>,
datum: &Datum,
) -> Result<(), StaticAnalysis<Insn>> {
let len = sequence.len();
sequence
.iter()
.take(len - 1)
.enumerate()
.find(|(_offs, i)| i.reads(datum) || i.writes(datum))
.map(|(offs, i)| i.sa().set_offset(offs))
.map_or(Ok(()), Err)
}
/// If the sequence reads from `datum` before writing to it, then this function returns a
/// StaticAnalysis modifying the first instruction in the sequence. Successively applying these
/// ensures that the sequence will not read from the `datum` before it has been initialized.
pub fn uninitialized<Datum, Insn: DataFlow<Datum>>(
sequence: &Sequence<Insn>,
datum: &Datum,
) -> Result<(), StaticAnalysis<Insn>> {
let Some(read) = sequence
.iter()
.enumerate()
.find(|(_offs, insn)| insn.reads(datum))
else {
// There's no instruction in the sequence reading from `datum`
return Ok(());
};
let Some(write) = sequence
.iter()
.enumerate()
.find(|(_offs, insn)| insn.writes(datum))
else {
// There's no instruction in the sequence writing to `datum`, so `datum` is uninitialized
// wherever it's read.
return Err(read.1.sa());
};
if write.0 < read.0 {
// The write to `datum` happened before the read, so that's okay.
return Ok(());
}
Err(read.1.sa())
}
/// If the sequence writes to `datum` without reading from it afterward, then this function returns a
/// StaticAnalysis modifying the first instruction in the sequence that writes to `datum`. This
/// means that The sequence will not write to `datum` unless it is later used.
pub fn dont_expect_write<Datum, Insn: DataFlow<Datum>>(
sequence: &Sequence<Insn>,
datum: &Datum,
) -> Result<(), StaticAnalysis<Insn>> {
'outer: for (offset, write) in sequence
.iter()
.enumerate()
.filter(|(_offs, insn)| insn.writes(datum))
{
for insn in sequence.iter().skip(offset) {
if insn.reads(datum) {
// The write I found is followed by a read,
// so there's nothing to do here.
continue 'outer;
}
if insn.writes(datum) {
// The write I found gets been clobbered,
// so let's return a StaticAnalysis
break;
}
}
return Err(write.sa().set_offset(offset));
}
Ok(())
}
/// If the sequence does not contains any instruction that writes to `datum`, then this returns a
/// StaticAnalysis modifying the first instruction in the sequence. Successively applying these
/// will make sure that the sequence writes to `datum`.
pub fn expect_write<Datum, Insn: DataFlow<Datum>>(
sequence: &Sequence<Insn>,
datum: &Datum,
) -> Result<(), StaticAnalysis<Insn>> {
if !sequence.iter().any(|insn| insn.writes(datum)) {
// There's no instruction in the sequence writing to `datum`
return Err(sequence[0].sa());
};
Ok(())
}
/// If the sequence does not contains any instruction that reads from `datum`, then this returns a
/// StaticAnalysis modifying the first instruction in the sequence. Successively applying these
/// will make sure that the sequence reads from `datum`.
pub fn expect_read<Datum, Insn: DataFlow<Datum>>(
sequence: &Sequence<Insn>,
datum: &Datum,
) -> Result<(), StaticAnalysis<Insn>> {
if !sequence.iter().any(|insn| insn.reads(datum)) {
// There's no instruction in the sequence writing to `datum`
return Err(sequence[0].sa());
};
Ok(())
}
/// Returns true if the datum is in use by the sequence, that is, either read from or written to.
pub fn in_use<Datum, Insn: DataFlow<Datum>>(sequence: &Sequence<Insn>, datum: &Datum) -> bool {
sequence
.iter()
.any(|insn| insn.reads(datum) || insn.writes(datum))
}
/// Makes sure that the sequence uses the given registers in order. This mechanism can be used, for
/// example, to make sure that a program does not use register 2 if if could be equivalently
/// rewritten to use register 1, and so this can reduce the search space by the number of
/// registers.
pub fn allocate_registers<Datum, Insn: DataFlow<Datum>>(
sequence: &Sequence<Insn>,
registers: &[Datum],
) -> Result<(), StaticAnalysis<Insn>> {
for window in registers.windows(2) {
if !in_use(sequence, &window[0]) {
leave_alone(sequence, &window[1])?;
}
}
Ok(())
}