1use crate::const_prop::subst_kind;
9use crate::pass::FunctionPass;
10use llvm_analysis::{Cfg, DomTree};
11use llvm_ir::{
12 BlockId, Context, FastMathFlags, FloatPredicate, Function, InstrId, InstrKind, IntArithFlags,
13 IntPredicate, TypeId, ValueRef,
14};
15use std::collections::{HashMap, HashSet};
16
17#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
18enum ExprKey {
19 Add(u8, ValueRef, ValueRef),
20 Sub(u8, ValueRef, ValueRef),
21 Mul(u8, ValueRef, ValueRef),
22 UDiv(bool, ValueRef, ValueRef),
23 SDiv(bool, ValueRef, ValueRef),
24 URem(ValueRef, ValueRef),
25 SRem(ValueRef, ValueRef),
26 And(ValueRef, ValueRef),
27 Or(ValueRef, ValueRef),
28 Xor(ValueRef, ValueRef),
29 Shl(u8, ValueRef, ValueRef),
30 LShr(bool, ValueRef, ValueRef),
31 AShr(bool, ValueRef, ValueRef),
32 ICmp(u8, ValueRef, ValueRef),
33 Select(ValueRef, ValueRef, ValueRef),
34 Trunc(ValueRef, TypeId),
35 ZExt(ValueRef, TypeId),
36 SExt(ValueRef, TypeId),
37 BitCast(ValueRef, TypeId),
38 PtrToInt(ValueRef, TypeId),
39 IntToPtr(ValueRef, TypeId),
40 FPTrunc(ValueRef, TypeId),
41 FPExt(ValueRef, TypeId),
42 FPToUI(ValueRef, TypeId),
43 FPToSI(ValueRef, TypeId),
44 UIToFP(ValueRef, TypeId),
45 SIToFP(ValueRef, TypeId),
46 AddrSpaceCast(ValueRef, TypeId),
47 FAdd(u16, ValueRef, ValueRef),
48 FSub(u16, ValueRef, ValueRef),
49 FMul(u16, ValueRef, ValueRef),
50 FDiv(u16, ValueRef, ValueRef),
51 FRem(u16, ValueRef, ValueRef),
52 FNeg(u16, ValueRef),
53 FCmp(u16, u8, ValueRef, ValueRef),
54}
55
56fn int_flags_bits(flags: IntArithFlags) -> u8 {
57 (if flags.nuw { 1 } else { 0 }) | ((if flags.nsw { 1 } else { 0 }) << 1)
58}
59
60fn fast_math_bits(flags: FastMathFlags) -> u16 {
61 (if flags.nnan { 1 } else { 0 })
62 | ((if flags.ninf { 1 } else { 0 }) << 1)
63 | ((if flags.nsz { 1 } else { 0 }) << 2)
64 | ((if flags.arcp { 1 } else { 0 }) << 3)
65 | ((if flags.contract { 1 } else { 0 }) << 4)
66 | ((if flags.afn { 1 } else { 0 }) << 5)
67 | ((if flags.reassoc { 1 } else { 0 }) << 6)
68 | ((if flags.fast { 1 } else { 0 }) << 7)
69}
70
71fn int_pred_bits(pred: IntPredicate) -> u8 {
72 match pred {
73 IntPredicate::Eq => 0,
74 IntPredicate::Ne => 1,
75 IntPredicate::Ugt => 2,
76 IntPredicate::Uge => 3,
77 IntPredicate::Ult => 4,
78 IntPredicate::Ule => 5,
79 IntPredicate::Sgt => 6,
80 IntPredicate::Sge => 7,
81 IntPredicate::Slt => 8,
82 IntPredicate::Sle => 9,
83 }
84}
85
86fn float_pred_bits(pred: FloatPredicate) -> u8 {
87 match pred {
88 FloatPredicate::False => 0,
89 FloatPredicate::Oeq => 1,
90 FloatPredicate::Ogt => 2,
91 FloatPredicate::Oge => 3,
92 FloatPredicate::Olt => 4,
93 FloatPredicate::Ole => 5,
94 FloatPredicate::One => 6,
95 FloatPredicate::Ord => 7,
96 FloatPredicate::Uno => 8,
97 FloatPredicate::Ueq => 9,
98 FloatPredicate::Ugt => 10,
99 FloatPredicate::Uge => 11,
100 FloatPredicate::Ult => 12,
101 FloatPredicate::Ule => 13,
102 FloatPredicate::Une => 14,
103 FloatPredicate::True => 15,
104 }
105}
106
107fn value_rank(v: ValueRef) -> (u8, u32) {
108 match v {
109 ValueRef::Instruction(id) => (0, id.0),
110 ValueRef::Argument(id) => (1, id.0),
111 ValueRef::Constant(id) => (2, id.0),
112 ValueRef::Global(id) => (3, id.0),
113 }
114}
115
116fn order_pair(a: ValueRef, b: ValueRef) -> (ValueRef, ValueRef) {
117 if value_rank(a) <= value_rank(b) {
118 (a, b)
119 } else {
120 (b, a)
121 }
122}
123
124fn expr_key(kind: &InstrKind) -> Option<ExprKey> {
125 use InstrKind::*;
126 Some(match kind {
127 Add { flags, lhs, rhs } => {
128 let (l, r) = order_pair(*lhs, *rhs);
129 ExprKey::Add(int_flags_bits(*flags), l, r)
130 }
131 Sub { flags, lhs, rhs } => ExprKey::Sub(int_flags_bits(*flags), *lhs, *rhs),
132 Mul { flags, lhs, rhs } => {
133 let (l, r) = order_pair(*lhs, *rhs);
134 ExprKey::Mul(int_flags_bits(*flags), l, r)
135 }
136 UDiv { exact, lhs, rhs } => ExprKey::UDiv(*exact, *lhs, *rhs),
137 SDiv { exact, lhs, rhs } => ExprKey::SDiv(*exact, *lhs, *rhs),
138 URem { lhs, rhs } => ExprKey::URem(*lhs, *rhs),
139 SRem { lhs, rhs } => ExprKey::SRem(*lhs, *rhs),
140 And { lhs, rhs } => {
141 let (l, r) = order_pair(*lhs, *rhs);
142 ExprKey::And(l, r)
143 }
144 Or { lhs, rhs } => {
145 let (l, r) = order_pair(*lhs, *rhs);
146 ExprKey::Or(l, r)
147 }
148 Xor { lhs, rhs } => {
149 let (l, r) = order_pair(*lhs, *rhs);
150 ExprKey::Xor(l, r)
151 }
152 Shl { flags, lhs, rhs } => ExprKey::Shl(int_flags_bits(*flags), *lhs, *rhs),
153 LShr { exact, lhs, rhs } => ExprKey::LShr(*exact, *lhs, *rhs),
154 AShr { exact, lhs, rhs } => ExprKey::AShr(*exact, *lhs, *rhs),
155 ICmp { pred, lhs, rhs } => {
156 if matches!(pred, IntPredicate::Eq | IntPredicate::Ne) {
157 let (l, r) = order_pair(*lhs, *rhs);
158 ExprKey::ICmp(int_pred_bits(*pred), l, r)
159 } else {
160 ExprKey::ICmp(int_pred_bits(*pred), *lhs, *rhs)
161 }
162 }
163 Select {
164 cond,
165 then_val,
166 else_val,
167 } => ExprKey::Select(*cond, *then_val, *else_val),
168 Trunc { val, to } => ExprKey::Trunc(*val, *to),
169 ZExt { val, to } => ExprKey::ZExt(*val, *to),
170 SExt { val, to } => ExprKey::SExt(*val, *to),
171 BitCast { val, to } => ExprKey::BitCast(*val, *to),
172 PtrToInt { val, to } => ExprKey::PtrToInt(*val, *to),
173 IntToPtr { val, to } => ExprKey::IntToPtr(*val, *to),
174 FPTrunc { val, to } => ExprKey::FPTrunc(*val, *to),
175 FPExt { val, to } => ExprKey::FPExt(*val, *to),
176 FPToUI { val, to } => ExprKey::FPToUI(*val, *to),
177 FPToSI { val, to } => ExprKey::FPToSI(*val, *to),
178 UIToFP { val, to } => ExprKey::UIToFP(*val, *to),
179 SIToFP { val, to } => ExprKey::SIToFP(*val, *to),
180 AddrSpaceCast { val, to } => ExprKey::AddrSpaceCast(*val, *to),
181 FAdd { flags, lhs, rhs } => ExprKey::FAdd(fast_math_bits(*flags), *lhs, *rhs),
182 FSub { flags, lhs, rhs } => ExprKey::FSub(fast_math_bits(*flags), *lhs, *rhs),
183 FMul { flags, lhs, rhs } => ExprKey::FMul(fast_math_bits(*flags), *lhs, *rhs),
184 FDiv { flags, lhs, rhs } => ExprKey::FDiv(fast_math_bits(*flags), *lhs, *rhs),
185 FRem { flags, lhs, rhs } => ExprKey::FRem(fast_math_bits(*flags), *lhs, *rhs),
186 FNeg { flags, operand } => ExprKey::FNeg(fast_math_bits(*flags), *operand),
187 FCmp {
188 flags,
189 pred,
190 lhs,
191 rhs,
192 } => ExprKey::FCmp(fast_math_bits(*flags), float_pred_bits(*pred), *lhs, *rhs),
193 _ => return None,
194 })
195}
196
197pub struct Gvn;
199
200impl FunctionPass for Gvn {
201 fn name(&self) -> &'static str {
202 "gvn"
203 }
204
205 fn run_on_function(&mut self, _ctx: &mut Context, func: &mut Function) -> bool {
206 if func.blocks.is_empty() {
207 return false;
208 }
209
210 let cfg = Cfg::compute(func);
211 let dom = DomTree::compute(func, &cfg);
212
213 let mut dom_children: Vec<Vec<BlockId>> = vec![Vec::new(); func.num_blocks()];
214 for bi in 0..func.num_blocks() {
215 let bid = BlockId(bi as u32);
216 if let Some(idom) = dom.idom(bid) {
217 dom_children[idom.0 as usize].push(bid);
218 }
219 }
220
221 let mut subst: HashMap<InstrId, ValueRef> = HashMap::new();
222 let mut remove: HashSet<InstrId> = HashSet::new();
223
224 rewrite_block(
225 func,
226 BlockId(0),
227 &dom_children,
228 &mut HashMap::new(),
229 &mut HashMap::new(),
230 &mut subst,
231 &mut remove,
232 );
233
234 if subst.is_empty() {
235 return false;
236 }
237
238 for instr in &mut func.instructions {
239 instr.kind = subst_kind(instr.kind.clone(), &subst);
240 }
241
242 for bb in &mut func.blocks {
243 bb.body.retain(|iid| !remove.contains(iid));
244 if let Some(tid) = bb.terminator {
245 bb.terminator = Some(tid);
246 }
247 }
248
249 true
250 }
251}
252
253#[allow(clippy::too_many_arguments)]
254fn rewrite_block(
255 func: &mut Function,
256 bid: BlockId,
257 dom_children: &[Vec<BlockId>],
258 exprs_in: &mut HashMap<ExprKey, ValueRef>,
259 loads_in: &mut HashMap<ValueRef, ValueRef>,
260 subst: &mut HashMap<InstrId, ValueRef>,
261 remove: &mut HashSet<InstrId>,
262) {
263 let mut exprs = exprs_in.clone();
264 let mut loads = loads_in.clone();
265
266 let body = func.blocks[bid.0 as usize].body.clone();
267 for iid in body {
268 let rewritten = subst_kind(func.instr(iid).kind.clone(), subst);
269 func.instr_mut(iid).kind = rewritten.clone();
270
271 match &rewritten {
272 InstrKind::Load {
273 ptr,
274 volatile: false,
275 ..
276 } => {
277 if let Some(existing) = loads.get(ptr).copied() {
278 subst.insert(iid, existing);
279 remove.insert(iid);
280 } else {
281 loads.insert(*ptr, ValueRef::Instruction(iid));
282 }
283 }
284 InstrKind::Store { .. }
285 | InstrKind::Call { .. }
286 | InstrKind::Alloca { .. }
287 | InstrKind::GetElementPtr { .. }
288 | InstrKind::IntToPtr { .. }
289 | InstrKind::PtrToInt { .. } => {
290 loads.clear();
291 if let Some(key) = expr_key(&rewritten) {
292 if let Some(existing) = exprs.get(&key).copied() {
293 subst.insert(iid, existing);
294 remove.insert(iid);
295 } else {
296 exprs.insert(key, ValueRef::Instruction(iid));
297 }
298 }
299 }
300 _ => {
301 if let Some(key) = expr_key(&rewritten) {
302 if let Some(existing) = exprs.get(&key).copied() {
303 subst.insert(iid, existing);
304 remove.insert(iid);
305 } else {
306 exprs.insert(key, ValueRef::Instruction(iid));
307 }
308 }
309 }
310 }
311 }
312
313 if let Some(tid) = func.blocks[bid.0 as usize].terminator {
314 let tk = subst_kind(func.instr(tid).kind.clone(), subst);
315 func.instr_mut(tid).kind = tk;
316 }
317
318 for &child in &dom_children[bid.0 as usize] {
319 rewrite_block(func, child, dom_children, &mut exprs, &mut loads, subst, remove);
320 }
321}
322
323#[cfg(test)]
324mod tests {
325 use super::*;
326 use llvm_ir::{Builder, Linkage, Module};
327
328 fn run_gvn(mut ctx: Context, mut module: Module) -> Function {
329 let mut pass = Gvn;
330 let changed = pass.run_on_function(&mut ctx, &mut module.functions[0]);
331 assert!(changed, "GVN should change this test case");
332 module.functions.remove(0)
333 }
334
335 fn make_binop_fn(kind: &str, commuted_second: bool) -> (Context, Module) {
336 let mut ctx = Context::new();
337 let mut module = Module::new("m");
338 let mut b = Builder::new(&mut ctx, &mut module);
339 b.add_function(
340 "f",
341 b.ctx.i64_ty,
342 vec![b.ctx.i64_ty, b.ctx.i64_ty],
343 vec!["a".into(), "b".into()],
344 false,
345 Linkage::External,
346 );
347 let entry = b.add_block("entry");
348 b.position_at_end(entry);
349 let a = b.get_arg(0);
350 let bv = b.get_arg(1);
351 let x = match kind {
352 "add" => b.build_add("x", a, bv),
353 "sub" => b.build_sub("x", a, bv),
354 "mul" => b.build_mul("x", a, bv),
355 _ => unreachable!(),
356 };
357 let y = match kind {
358 "add" => {
359 if commuted_second {
360 b.build_add("y", bv, a)
361 } else {
362 b.build_add("y", a, bv)
363 }
364 }
365 "sub" => {
366 if commuted_second {
367 b.build_sub("y", bv, a)
368 } else {
369 b.build_sub("y", a, bv)
370 }
371 }
372 "mul" => {
373 if commuted_second {
374 b.build_mul("y", bv, a)
375 } else {
376 b.build_mul("y", a, bv)
377 }
378 }
379 _ => unreachable!(),
380 };
381 let s = b.build_add("s", x, y);
382 b.build_ret(s);
383 (ctx, module)
384 }
385
386 #[test]
387 fn gvn_eliminates_same_add_in_block() {
388 let (ctx, module) = make_binop_fn("add", false);
389 let f = run_gvn(ctx, module);
390 assert_eq!(f.blocks[0].body.len(), 2);
391 }
392
393 #[test]
394 fn gvn_eliminates_commutative_add() {
395 let (ctx, module) = make_binop_fn("add", true);
396 let f = run_gvn(ctx, module);
397 assert_eq!(f.blocks[0].body.len(), 2);
398 }
399
400 #[test]
401 fn gvn_does_not_eliminate_non_commutative_sub() {
402 let (mut ctx, mut module) = make_binop_fn("sub", true);
403 let mut pass = Gvn;
404 let changed = pass.run_on_function(&mut ctx, &mut module.functions[0]);
405 assert!(!changed, "sub(a,b) and sub(b,a) are not equivalent");
406 }
407
408 #[test]
409 fn gvn_eliminates_commutative_mul() {
410 let (ctx, module) = make_binop_fn("mul", true);
411 let f = run_gvn(ctx, module);
412 assert_eq!(f.blocks[0].body.len(), 2);
413 }
414
415 #[test]
416 fn gvn_eliminates_load_without_store() {
417 let mut ctx = Context::new();
418 let mut module = Module::new("m");
419 let mut b = Builder::new(&mut ctx, &mut module);
420 b.add_function("f", b.ctx.i32_ty, vec![], vec![], false, Linkage::External);
421 let entry = b.add_block("entry");
422 b.position_at_end(entry);
423 let p = b.build_alloca("p", b.ctx.i32_ty);
424 let c = b.const_int(b.ctx.i32_ty, 9);
425 b.build_store(c, p);
426 let l1 = b.build_load("l1", b.ctx.i32_ty, p);
427 let l2 = b.build_load("l2", b.ctx.i32_ty, p);
428 let s = b.build_add("s", l1, l2);
429 b.build_ret(s);
430
431 let f = run_gvn(ctx, module);
432 assert!(f.blocks[0].body.len() < 5);
433 }
434
435 #[test]
436 fn gvn_store_invalidates_load_value_numbering() {
437 let mut ctx = Context::new();
438 let mut module = Module::new("m");
439 let mut b = Builder::new(&mut ctx, &mut module);
440 b.add_function("f", b.ctx.i32_ty, vec![], vec![], false, Linkage::External);
441 let entry = b.add_block("entry");
442 b.position_at_end(entry);
443 let p = b.build_alloca("p", b.ctx.i32_ty);
444 let c1 = b.const_int(b.ctx.i32_ty, 1);
445 b.build_store(c1, p);
446 let _l1 = b.build_load("l1", b.ctx.i32_ty, p);
447 let c2 = b.const_int(b.ctx.i32_ty, 2);
448 b.build_store(c2, p);
449 let l2 = b.build_load("l2", b.ctx.i32_ty, p);
450 b.build_ret(l2);
451
452 let mut pass = Gvn;
453 let mut changed = false;
454 changed |= pass.run_on_function(&mut ctx, &mut module.functions[0]);
455 assert!(!changed, "second load must not be replaced across store");
456 }
457
458 #[test]
459 fn gvn_eliminates_redundant_icmp_eq_commuted() {
460 let mut ctx = Context::new();
461 let mut module = Module::new("m");
462 let mut b = Builder::new(&mut ctx, &mut module);
463 b.add_function(
464 "f",
465 b.ctx.i1_ty,
466 vec![b.ctx.i64_ty, b.ctx.i64_ty],
467 vec!["a".into(), "b".into()],
468 false,
469 Linkage::External,
470 );
471 let entry = b.add_block("entry");
472 b.position_at_end(entry);
473 let a = b.get_arg(0);
474 let bv = b.get_arg(1);
475 let c1 = b.build_icmp("c1", IntPredicate::Eq, a, bv);
476 let c2 = b.build_icmp("c2", IntPredicate::Eq, bv, a);
477 let r = b.build_and("r", c1, c2);
478 b.build_ret(r);
479
480 let f = run_gvn(ctx, module);
481 assert_eq!(f.blocks[0].body.len(), 2);
482 }
483
484 #[test]
485 fn gvn_eliminates_cross_block_when_dominated() {
486 let mut ctx = Context::new();
487 let mut module = Module::new("m");
488 let mut b = Builder::new(&mut ctx, &mut module);
489 b.add_function(
490 "f",
491 b.ctx.i64_ty,
492 vec![b.ctx.i64_ty, b.ctx.i64_ty, b.ctx.i1_ty],
493 vec!["a".into(), "b".into(), "cond".into()],
494 false,
495 Linkage::External,
496 );
497 let entry = b.add_block("entry");
498 let then_bb = b.add_block("then");
499 let else_bb = b.add_block("else");
500 let merge = b.add_block("merge");
501
502 b.position_at_end(entry);
503 let a = b.get_arg(0);
504 let bv = b.get_arg(1);
505 let cond = b.get_arg(2);
506 let x = b.build_add("x", a, bv);
507 b.build_cond_br(cond, then_bb, else_bb);
508
509 b.position_at_end(then_bb);
510 let y = b.build_add("y", a, bv);
511 b.build_br(merge);
512
513 b.position_at_end(else_bb);
514 b.build_br(merge);
515
516 b.position_at_end(merge);
517 let p = b.build_phi("p", b.ctx.i64_ty, vec![(y, then_bb), (x, else_bb)]);
518 b.build_ret(p);
519
520 let f = run_gvn(ctx, module);
521 assert!(f.blocks[1].body.is_empty());
522 }
523
524 #[test]
525 fn gvn_does_not_cross_non_dominating_siblings() {
526 let mut ctx = Context::new();
527 let mut module = Module::new("m");
528 let mut b = Builder::new(&mut ctx, &mut module);
529 b.add_function(
530 "f",
531 b.ctx.i64_ty,
532 vec![b.ctx.i64_ty, b.ctx.i64_ty, b.ctx.i1_ty],
533 vec!["a".into(), "b".into(), "cond".into()],
534 false,
535 Linkage::External,
536 );
537 let entry = b.add_block("entry");
538 let then_bb = b.add_block("then");
539 let else_bb = b.add_block("else");
540 let merge = b.add_block("merge");
541
542 b.position_at_end(entry);
543 let a = b.get_arg(0);
544 let bv = b.get_arg(1);
545 let cond = b.get_arg(2);
546 b.build_cond_br(cond, then_bb, else_bb);
547
548 b.position_at_end(then_bb);
549 let t = b.build_add("t", a, bv);
550 b.build_br(merge);
551
552 b.position_at_end(else_bb);
553 let e = b.build_add("e", a, bv);
554 b.build_br(merge);
555
556 b.position_at_end(merge);
557 let p = b.build_phi("p", b.ctx.i64_ty, vec![(t, then_bb), (e, else_bb)]);
558 b.build_ret(p);
559
560 let mut pass = Gvn;
561 let changed = pass.run_on_function(&mut ctx, &mut module.functions[0]);
562 assert!(!changed, "sibling-block expressions are not dominance-equivalent");
563 }
564
565 #[test]
566 fn gvn_eliminates_redundant_select() {
567 let mut ctx = Context::new();
568 let mut module = Module::new("m");
569 let mut b = Builder::new(&mut ctx, &mut module);
570 b.add_function(
571 "f",
572 b.ctx.i64_ty,
573 vec![b.ctx.i1_ty, b.ctx.i64_ty, b.ctx.i64_ty],
574 vec!["c".into(), "a".into(), "b".into()],
575 false,
576 Linkage::External,
577 );
578 let entry = b.add_block("entry");
579 b.position_at_end(entry);
580 let c = b.get_arg(0);
581 let a = b.get_arg(1);
582 let bv = b.get_arg(2);
583 let s1 = b.build_select("s1", c, a, bv);
584 let s2 = b.build_select("s2", c, a, bv);
585 let r = b.build_add("r", s1, s2);
586 b.build_ret(r);
587
588 let f = run_gvn(ctx, module);
589 assert_eq!(f.blocks[0].body.len(), 2);
590 }
591}