1 use peepmatic_runtime::{
2 cc::ConditionCode,
3 operator::Operator,
4 part::Constant,
5 r#type::{BitWidth, Type},
6 };
7 use peepmatic_test::*;
8
9 const TEST_ISA: TestIsa = TestIsa {
10 native_word_size_in_bits: 32,
11 };
12
13 macro_rules! optimizer {
14 ($opts:ident, $source:expr) => {{
15 let _ = env_logger::try_init();
16 $opts = peepmatic::compile_str($source, std::path::Path::new("peepmatic-test")).unwrap();
17 $opts.optimizer(TEST_ISA)
18 }};
19 }
20
21 #[test]
opcode()22 fn opcode() {
23 let opts;
24 let mut optimizer = optimizer!(opts, "(=> (iadd $x 0) $x)");
25
26 let mut program = Program::default();
27 let five = program.r#const(Constant::Int(5, BitWidth::ThirtyTwo), BitWidth::ThirtyTwo);
28 let zero = program.r#const(Constant::Int(0, BitWidth::ThirtyTwo), BitWidth::ThirtyTwo);
29 let add = program.new_instruction(Operator::Iadd, Type::i32(), vec![], vec![five, zero]);
30
31 let new = optimizer.apply_one(&mut program, add);
32 let new = new.expect("optimization should have applied");
33 assert!(program.structurally_eq(new, five));
34
35 let add = program.new_instruction(Operator::Iadd, Type::i32(), vec![], vec![five, five]);
36 let replacement = optimizer.apply_one(&mut program, add);
37 assert!(replacement.is_none());
38 }
39
40 #[test]
constant()41 fn constant() {
42 let opts;
43 let mut optimizer = optimizer!(opts, "(=> (iadd $C $x) (iadd_imm $C $x))");
44
45 let mut program = Program::default();
46 let five = program.r#const(Constant::Int(5, BitWidth::ThirtyTwo), BitWidth::ThirtyTwo);
47 let zero = program.r#const(Constant::Int(0, BitWidth::ThirtyTwo), BitWidth::ThirtyTwo);
48 let add = program.new_instruction(Operator::Iadd, Type::i32(), vec![], vec![five, zero]);
49
50 let expected = program.new_instruction(
51 Operator::IaddImm,
52 Type::i32(),
53 vec![Constant::Int(5, BitWidth::ThirtyTwo).into()],
54 vec![zero],
55 );
56
57 let new = optimizer.apply_one(&mut program, add);
58 let new = new.expect("optimization should have applied");
59 assert!(program.structurally_eq(new, expected));
60
61 let mul = program.new_instruction(Operator::Imul, Type::i32(), vec![], vec![five, zero]);
62 let add = program.new_instruction(Operator::Imul, Type::i32(), vec![], vec![mul, five]);
63 let replacement = optimizer.apply_one(&mut program, add);
64 assert!(replacement.is_none());
65 }
66
67 #[test]
boolean()68 fn boolean() {
69 let opts;
70 let mut optimizer = optimizer!(opts, "(=> (bint true) 1)");
71
72 let mut program = Program::default();
73 let t = program.r#const(Constant::Bool(true, BitWidth::One), BitWidth::One);
74 let bint = program.new_instruction(Operator::Bint, Type::i1(), vec![], vec![t]);
75 let one = program.r#const(Constant::Int(1, BitWidth::One), BitWidth::ThirtyTwo);
76
77 let new = optimizer.apply_one(&mut program, bint);
78 let new = new.expect("optimization should have applied");
79 assert!(program.structurally_eq(new, one));
80
81 let f = program.r#const(Constant::Bool(false, BitWidth::One), BitWidth::One);
82 let bint = program.new_instruction(Operator::Bint, Type::i1(), vec![], vec![f]);
83 let replacement = optimizer.apply_one(&mut program, bint);
84 assert!(replacement.is_none());
85 }
86
87 #[test]
condition_codes()88 fn condition_codes() {
89 let opts;
90 let mut optimizer = optimizer!(opts, "(=> (icmp eq $x $x) true)");
91
92 let mut program = Program::default();
93 let five = program.r#const(Constant::Int(5, BitWidth::ThirtyTwo), BitWidth::One);
94 let icmp_eq = program.new_instruction(
95 Operator::Icmp,
96 Type::b1(),
97 vec![ConditionCode::Eq.into()],
98 vec![five, five],
99 );
100 let t = program.r#const(Constant::Bool(true, BitWidth::One), BitWidth::One);
101
102 let new = optimizer.apply_one(&mut program, icmp_eq);
103 let new = new.expect("optimization should have applied");
104 assert!(program.structurally_eq(new, t));
105
106 let icmp_ne = program.new_instruction(
107 Operator::Icmp,
108 Type::b1(),
109 vec![ConditionCode::Ne.into()],
110 vec![five, five],
111 );
112 let replacement = optimizer.apply_one(&mut program, icmp_ne);
113 assert!(replacement.is_none());
114 }
115
116 #[test]
is_power_of_two()117 fn is_power_of_two() {
118 let opts;
119 let mut optimizer = optimizer!(
120 opts,
121 "
122 (=> (when (imul $x $C)
123 (is-power-of-two $C))
124 (ishl $x $(log2 $C)))
125 "
126 );
127
128 let mut program = Program::default();
129 let five = program.r#const(Constant::Int(5, BitWidth::ThirtyTwo), BitWidth::ThirtyTwo);
130 let two = program.r#const(Constant::Int(2, BitWidth::ThirtyTwo), BitWidth::ThirtyTwo);
131 let imul = program.new_instruction(Operator::Imul, Type::i32(), vec![], vec![five, two]);
132
133 let one = program.r#const(Constant::Int(1, BitWidth::ThirtyTwo), BitWidth::ThirtyTwo);
134 let ishl = program.new_instruction(Operator::Ishl, Type::i32(), vec![], vec![five, one]);
135
136 let new = optimizer.apply_one(&mut program, imul);
137 let new = new.expect("optimization should have applied");
138 assert!(program.structurally_eq(new, ishl));
139
140 let three = program.r#const(Constant::Int(3, BitWidth::ThirtyTwo), BitWidth::ThirtyTwo);
141 let imul = program.new_instruction(Operator::Imul, Type::i32(), vec![], vec![five, three]);
142
143 let replacement = optimizer.apply_one(&mut program, imul);
144 assert!(replacement.is_none());
145 }
146
147 #[test]
bit_width()148 fn bit_width() {
149 let opts;
150 let mut optimizer = optimizer!(
151 opts,
152 "
153 (=> (when (imul $C $x)
154 (bit-width $C 32))
155 (imul_imm $C $x))
156 "
157 );
158
159 let mut program = Program::default();
160 let five = program.r#const(Constant::Int(5, BitWidth::ThirtyTwo), BitWidth::ThirtyTwo);
161 let two = program.r#const(Constant::Int(2, BitWidth::ThirtyTwo), BitWidth::ThirtyTwo);
162 let imul = program.new_instruction(Operator::Imul, Type::i32(), vec![], vec![five, two]);
163
164 let imul_imm = program.new_instruction(
165 Operator::ImulImm,
166 Type::i32(),
167 vec![Constant::Int(5, BitWidth::ThirtyTwo).into()],
168 vec![two],
169 );
170
171 let new = optimizer.apply_one(&mut program, imul);
172 let new = new.expect("optimization should have applied");
173 assert!(program.structurally_eq(new, imul_imm));
174
175 let five = program.r#const(Constant::Int(5, BitWidth::SixtyFour), BitWidth::SixtyFour);
176 let two = program.r#const(Constant::Int(2, BitWidth::SixtyFour), BitWidth::SixtyFour);
177 let imul = program.new_instruction(Operator::Imul, Type::i32(), vec![], vec![five, two]);
178
179 let replacement = optimizer.apply_one(&mut program, imul);
180 assert!(replacement.is_none());
181 }
182
183 #[test]
fits_in_native_word()184 fn fits_in_native_word() {
185 let opts;
186 let mut optimizer = optimizer!(
187 opts,
188 "
189 (=> (when (imul $C $x)
190 (fits-in-native-word $C))
191 (imul_imm $C $x))
192 "
193 );
194
195 let mut program = Program::default();
196 let five = program.r#const(Constant::Int(5, BitWidth::ThirtyTwo), BitWidth::ThirtyTwo);
197 let two = program.r#const(Constant::Int(2, BitWidth::ThirtyTwo), BitWidth::ThirtyTwo);
198 let imul = program.new_instruction(Operator::Imul, Type::i32(), vec![], vec![five, two]);
199
200 let imul_imm = program.new_instruction(
201 Operator::ImulImm,
202 Type::i32(),
203 vec![Constant::Int(5, BitWidth::ThirtyTwo).into()],
204 vec![two],
205 );
206
207 let new = optimizer.apply_one(&mut program, imul);
208 let new = new.expect("optimization should have applied");
209 assert!(program.structurally_eq(new, imul_imm));
210
211 let five = program.r#const(Constant::Int(5, BitWidth::SixtyFour), BitWidth::SixtyFour);
212 let two = program.r#const(Constant::Int(2, BitWidth::SixtyFour), BitWidth::SixtyFour);
213 let imul = program.new_instruction(Operator::Imul, Type::i64(), vec![], vec![five, two]);
214
215 let replacement = optimizer.apply_one(&mut program, imul);
216 assert!(replacement.is_none());
217 }
218
219 #[test]
unquote_neg()220 fn unquote_neg() {
221 let opts;
222 let mut optimizer = optimizer!(
223 opts,
224 "
225 (=> (isub $x $C)
226 (iadd_imm $(neg $C) $x))
227 "
228 );
229
230 let mut program = Program::default();
231 let five = program.r#const(Constant::Int(5, BitWidth::SixtyFour), BitWidth::SixtyFour);
232 let two = program.r#const(Constant::Int(2, BitWidth::SixtyFour), BitWidth::SixtyFour);
233 let isub = program.new_instruction(Operator::Isub, Type::i64(), vec![], vec![five, two]);
234
235 let iadd_imm = program.new_instruction(
236 Operator::IaddImm,
237 Type::i64(),
238 vec![Constant::Int(-2 as _, BitWidth::SixtyFour).into()],
239 vec![five],
240 );
241
242 let new = optimizer.apply_one(&mut program, isub);
243 let new = new.expect("optimization should have applied");
244 assert!(program.structurally_eq(new, iadd_imm));
245 }
246
247 #[test]
subsumption()248 fn subsumption() {
249 let opts;
250 let mut optimizer = optimizer!(
251 opts,
252 "
253 ;; NB: the following optimizations are ordered from least to most general, so
254 ;; the first applicable optimization should be the one that is applied.
255
256 (=> (iadd (iadd (iadd $w $x) $y) $z)
257 (iadd (iadd $w $x) (iadd $y $z)))
258
259 (=> (iadd $C1 $C2)
260 $(iadd $C1 $C2))
261
262 (=> (iadd $C $x)
263 (iadd_imm $C $x))
264
265 (=> (iadd $x $x)
266 (ishl_imm 1 $x))
267 "
268 );
269
270 let mut program = Program::default();
271
272 let w = program.r#const(Constant::Int(11, BitWidth::SixtyFour), BitWidth::SixtyFour);
273 let x = program.r#const(Constant::Int(22, BitWidth::SixtyFour), BitWidth::SixtyFour);
274 let y = program.r#const(Constant::Int(33, BitWidth::SixtyFour), BitWidth::SixtyFour);
275 let z = program.r#const(Constant::Int(44, BitWidth::SixtyFour), BitWidth::SixtyFour);
276
277 log::debug!("(iadd (iadd (iadd w x) y) z) => (iadd (iadd w x) (iadd y z))");
278
279 let iadd = program.new_instruction(Operator::Iadd, Type::i64(), vec![], vec![w, x]);
280 let iadd = program.new_instruction(Operator::Iadd, Type::i64(), vec![], vec![iadd, y]);
281 let iadd = program.new_instruction(Operator::Iadd, Type::i64(), vec![], vec![iadd, z]);
282 let expected_lhs = program.new_instruction(Operator::Iadd, Type::i64(), vec![], vec![w, x]);
283 let expected_rhs = program.new_instruction(Operator::Iadd, Type::i64(), vec![], vec![y, z]);
284 let expected = program.new_instruction(
285 Operator::Iadd,
286 Type::i64(),
287 vec![],
288 vec![expected_lhs, expected_rhs],
289 );
290
291 let new = optimizer.apply_one(&mut program, iadd);
292 let new = new.expect("optimization should have applied");
293 assert!(program.structurally_eq(new, expected));
294
295 log::debug!("(iadd w x) => y");
296
297 let iadd = program.new_instruction(Operator::Iadd, Type::i64(), vec![], vec![w, x]);
298 let new = optimizer.apply_one(&mut program, iadd);
299 let new = new.expect("optimization should have applied");
300 assert!(program.structurally_eq(new, y));
301
302 log::debug!("(iadd x (iadd y z)) => (iadd_imm x (iadd y z))");
303
304 let iadd_y_z = program.new_instruction(Operator::Iadd, Type::i64(), vec![], vec![y, z]);
305 let iadd = program.new_instruction(Operator::Iadd, Type::i64(), vec![], vec![x, iadd_y_z]);
306 let iadd_imm = program.new_instruction(
307 Operator::IaddImm,
308 Type::i64(),
309 vec![Constant::Int(22, BitWidth::SixtyFour).into()],
310 vec![iadd_y_z],
311 );
312 let new = optimizer.apply_one(&mut program, iadd);
313 let new = new.expect("optimization should have applied");
314 assert!(program.structurally_eq(new, iadd_imm));
315
316 log::debug!("(iadd (imul_imm x 1) (imul_imm x 1)) => (ishl_imm 1 (imul_imm x 1))");
317
318 let imul_imm = program.new_instruction(
319 Operator::ImulImm,
320 Type::i64(),
321 vec![Constant::Int(1, BitWidth::SixtyFour).into()],
322 vec![x],
323 );
324 let iadd = program.new_instruction(
325 Operator::Iadd,
326 Type::i64(),
327 vec![],
328 vec![imul_imm, imul_imm],
329 );
330 let ishl_imm = program.new_instruction(
331 Operator::IshlImm,
332 Type::i64(),
333 vec![Constant::Int(1, BitWidth::SixtyFour).into()],
334 vec![imul_imm],
335 );
336 let new = optimizer.apply_one(&mut program, iadd);
337 let new = new.expect("optimization should have applied");
338 assert!(program.structurally_eq(new, ishl_imm));
339
340 log::debug!("(iadd (imul w x) (imul y z)) does not match any optimization.");
341
342 let imul_w_x = program.new_instruction(Operator::Imul, Type::i64(), vec![], vec![w, x]);
343 let imul_y_z = program.new_instruction(Operator::Imul, Type::i64(), vec![], vec![y, z]);
344 let iadd = program.new_instruction(
345 Operator::Iadd,
346 Type::i64(),
347 vec![],
348 vec![imul_w_x, imul_y_z],
349 );
350
351 let replacement = optimizer.apply_one(&mut program, iadd);
352 assert!(replacement.is_none());
353 }
354
355 #[test]
polymorphic_bit_widths()356 fn polymorphic_bit_widths() {
357 let opts;
358 let mut optimizer = optimizer!(opts, "(=> (iadd $C $x) (iadd_imm $C $x))");
359
360 let mut program = Program::default();
361
362 // Applies to 32 bit adds.
363
364 let x = program.r#const(Constant::Int(42, BitWidth::ThirtyTwo), BitWidth::ThirtyTwo);
365 let y = program.r#const(Constant::Int(420, BitWidth::ThirtyTwo), BitWidth::ThirtyTwo);
366 let iadd = program.new_instruction(Operator::Iadd, Type::i32(), vec![], vec![x, y]);
367 let iadd_imm = program.new_instruction(
368 Operator::IaddImm,
369 Type::i32(),
370 vec![Constant::Int(42, BitWidth::ThirtyTwo).into()],
371 vec![y],
372 );
373
374 let new = optimizer.apply_one(&mut program, iadd);
375 let new = new.expect("optimization should have applied");
376 assert!(program.structurally_eq(new, iadd_imm));
377
378 // Applies to 16 bit adds.
379
380 let x = program.r#const(Constant::Int(42, BitWidth::Sixteen), BitWidth::Sixteen);
381 let y = program.r#const(Constant::Int(420, BitWidth::Sixteen), BitWidth::Sixteen);
382 let iadd = program.new_instruction(Operator::Iadd, Type::i16(), vec![], vec![x, y]);
383 let iadd_imm = program.new_instruction(
384 Operator::IaddImm,
385 Type::i16(),
386 vec![Constant::Int(42, BitWidth::Sixteen).into()],
387 vec![y],
388 );
389
390 let new = optimizer.apply_one(&mut program, iadd);
391 let new = new.expect("optimization should have applied");
392 assert!(program.structurally_eq(new, iadd_imm));
393 }
394