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
// Copyright (c) 2017-2021 Fabian Schuiki
//! Global Common Subexpression Elimination
use crate::{
ir::{prelude::*, InstData},
opt::prelude::*,
};
use std::collections::{HashMap, HashSet};
/// Global Common Subexpression Elimination
///
/// This pass implements global common subexpression elimination. It tries to
/// eliminate redundant instructions.
pub struct GlobalCommonSubexprElim;
impl Pass for GlobalCommonSubexprElim {
fn run_on_cfg(_ctx: &PassContext, unit: &mut UnitBuilder) -> bool {
info!("GCSE [{}]", unit.name());
// Build the predecessor table and dominator tree.
let pred = unit.predtbl();
let dt = unit.domtree_with_predtbl(&pred);
// Build the temporal predecessor table and dominator tree.
let temp_pt = unit.temporal_predtbl();
let temp_dt = unit.domtree_with_predtbl(&temp_pt);
// Compute the TRG to allow for `prb` instructions to be eliminated.
let trg = unit.trg();
// Collect instructions.
let mut insts = vec![];
for bb in unit.blocks() {
for inst in unit.insts(bb) {
insts.push(inst);
}
}
// Perform GCSE.
let mut modified = false;
let mut values = HashMap::<InstData, HashSet<Value>>::new();
'outer: for inst in insts {
// Don't mess with instructions that produce no result or have side
// effects.
let opcode = unit[inst].opcode();
if !unit.has_result(inst)
|| opcode == Opcode::Ld
|| opcode == Opcode::Var
|| opcode == Opcode::Sig
{
continue;
}
let value = unit.inst_result(inst);
trace!("Examining {}", inst.dump(&unit));
// Try the candidates.
if let Some(aliases) = values.get_mut(&unit[inst]) {
'inner: for &cv in aliases.iter() {
trace!(" Trying {}", cv.dump(&unit));
let cv_inst = unit.value_inst(cv);
let inst_bb = unit.inst_block(inst).unwrap();
let cv_bb = unit.inst_block(cv_inst).unwrap();
// Make sure that we don't merge `prb` instructions in
// different temporal regions.
if trg[inst_bb] != trg[cv_bb] {
trace!(" Skipping because in other temporal region");
continue;
}
// Decide which dominator tree to use.
let which_dt = if opcode == Opcode::Prb { &temp_dt } else { &dt };
// Replace the current inst with the recorded value if the
// latter dominates the former.
if which_dt.dominates(cv_bb, inst_bb) {
debug!("Replace {} with {}", inst.dump(&unit), cv.dump(&unit),);
unit.replace_use(value, cv);
unit.prune_if_unused(inst);
modified = true;
continue 'outer;
}
// Replace the recorded value with the current inst if the
// latter dominates the former.
if which_dt.dominates(inst_bb, cv_bb) {
debug!("Replace {} with {}", cv.dump(&unit), value.dump(&unit),);
unit.replace_use(cv, value);
unit.prune_if_unused(cv_inst);
aliases.remove(&cv); // crazy that this works; NLL <3
modified = true;
break 'inner;
}
// Try to merge the current inst with the recorded value by
// hoisting the instruction up to an earlier BB. We know
// know that such a BB exists because being in this loop
// body means that both instructions have the same args,
// which is only possible if they are both dominated by the
// args.
trace!(
" Intersect(Dom({}), Dom({})):",
inst_bb.dump(&unit),
cv_bb.dump(&unit)
);
for bb in which_dt
.dominators(inst_bb)
.intersection(&which_dt.dominators(cv_bb))
{
trace!(" {}", bb.dump(&unit));
}
let target_bb = which_dt
.dominators(inst_bb)
.intersection(which_dt.dominators(cv_bb))
.max_by(|&&bb_a, &&bb_b| {
if which_dt.dominates(bb_a, bb_b) {
std::cmp::Ordering::Less
} else {
std::cmp::Ordering::Greater
}
});
let target_bb = match target_bb {
Some(&bb) => bb,
None => continue,
};
trace!(" Latest common dominator: {}", target_bb.dump(&unit));
// Hoist the instruction up into the target block.
debug!(
"Hoist {} up into {}",
inst.dump(&unit),
target_bb.dump(&unit)
);
let term = unit.terminator(target_bb);
unit.remove_inst(inst);
unit.insert_inst_before(inst, term);
// Replace all uses of the recorded value with the inst.
debug!("Replace {} with {}", cv.dump(&unit), value.dump(&unit),);
unit.replace_use(cv, value);
unit.prune_if_unused(cv_inst);
aliases.remove(&cv); // crazy that this works; NLL <3
modified = true;
break 'inner;
}
}
// Insert the instruction into the table.
// trace!("Recording {}", inst.dump(&unit));
values
.entry(unit[inst].clone())
.or_insert_with(Default::default)
.insert(value);
}
modified
}
}