use std::collections::BTreeSet;
use cranelift_entity::{entity_impl, packed_option::PackedOption, PrimaryMap, SecondaryMap};
use fxhash::{FxHashMap, FxHashSet};
use crate::{
cfg::ControlFlowGraph,
domtree::{DomTree, DominatorTreeTraversable},
};
use sonatina_ir::{
func_cursor::{CursorLocation, FuncCursor, InsnInserter},
insn::{BinaryOp, CastOp, InsnData, UnaryOp},
Block, DataFlowGraph, Function, Immediate, Insn, Type, Value,
};
use super::{constant_folding, simplify_impl};
const INITIAL_CLASS: Class = Class(0);
const IMMEDIATE_RANK: u32 = 0;
#[derive(Debug)]
pub struct GvnSolver {
classes: PrimaryMap<Class, ClassData>,
values: SecondaryMap<Value, GvnValueData>,
insn_table: FxHashMap<GvnInsn, Class>,
edges: PrimaryMap<Edge, EdgeData>,
blocks: SecondaryMap<Block, GvnBlockData>,
value_phi_table: FxHashMap<ValuePhi, Class>,
always_avail: Vec<Value>,
}
impl GvnSolver {
pub fn new() -> Self {
Self {
classes: PrimaryMap::default(),
values: SecondaryMap::default(),
insn_table: FxHashMap::default(),
edges: PrimaryMap::default(),
blocks: SecondaryMap::default(),
value_phi_table: FxHashMap::default(),
always_avail: Vec::default(),
}
}
pub fn run(&mut self, func: &mut Function, cfg: &mut ControlFlowGraph, domtree: &mut DomTree) {
self.clear();
if func.layout.entry_block().is_none() {
return;
}
self.classes.push(ClassData {
values: BTreeSet::new(),
gvn_insn: GvnInsn::Value(Value(u32::MAX)),
value_phi: None,
});
debug_assert!(self.classes.len() == 1);
for &value in func.dfg.immediates.values() {
self.assign_class_to_imm_value(value);
}
let mut rank = IMMEDIATE_RANK + 1;
for &arg in &func.arg_values {
self.values[arg].rank = rank;
rank += 1;
let gvn_insn = GvnInsn::Value(arg);
self.always_avail.push(arg);
let class = self.make_class(gvn_insn, None);
self.assign_class(arg, class);
}
for &block in domtree.rpo() {
self.blocks[block].rank = rank;
rank += 1;
for insn in func.layout.iter_insn(block) {
if let Some(insn_result) = func.dfg.insn_result(insn) {
self.values[insn_result].rank = rank;
rank += 1;
}
match func.dfg.insn_data(insn) {
InsnData::Jump { dests, .. } => {
let dest = dests[0];
self.add_edge_info(block, dest, None, None, None);
}
InsnData::Branch { args, dests } => {
let cond = args[0];
debug_assert_eq!(func.dfg.value_ty(cond), Type::I1);
let then_block = dests[0];
let else_block = dests[1];
let then_predicate = func.dfg.value_insn(cond).map(|insn| {
let insn_data = func.dfg.insn_data(insn).clone();
self.perform_predicate_simplification(&mut func.dfg, insn_data)
});
let else_predicate = self.perform_predicate_simplification(
&mut func.dfg,
InsnData::unary(UnaryOp::Not, cond),
);
let then_imm = self.make_imm(&mut func.dfg, true);
let else_imm = self.make_imm(&mut func.dfg, false);
self.add_edge_info(
block,
then_block,
Some(cond),
then_predicate,
Some(then_imm),
);
self.add_edge_info(
block,
else_block,
Some(cond),
Some(else_predicate),
Some(else_imm),
);
}
InsnData::BrTable {
args,
default,
table,
} => {
if let Some(default) = default {
self.add_edge_info(block, *default, None, None, None);
}
let cond = args[0];
for (value, dest) in args[1..].iter().zip(table.iter()) {
self.add_edge_info(block, *dest, Some(cond), None, Some(*value));
}
}
_ => {}
}
}
}
let entry = func.layout.entry_block().unwrap();
self.blocks[entry].reachable = true;
let mut changed = true;
while changed {
changed = false;
for &block in domtree.rpo() {
if !self.blocks[block].reachable {
continue;
}
let mut next_insn = func.layout.first_insn_of(block);
while let Some(insn) = next_insn {
if let Some(insn_result) = func.dfg.insn_result(insn) {
changed |= self.reassign_congruence(func, domtree, insn, insn_result);
}
next_insn = func.layout.next_insn_of(insn);
}
if let Some(last_insn) = func.layout.last_insn_of(block) {
changed |= self.analyze_last_insn(func, domtree, block, last_insn);
}
}
}
let mut remover = RedundantCodeRemover::new(self);
remover.remove_redundant_code(func, cfg, domtree);
}
pub fn clear(&mut self) {
self.classes.clear();
self.values.clear();
self.insn_table.clear();
self.edges.clear();
self.blocks.clear();
self.value_phi_table.clear();
self.always_avail.clear();
}
fn analyze_last_insn(
&mut self,
func: &Function,
domtree: &DomTree,
block: Block,
insn: Insn,
) -> bool {
match func.dfg.insn_data(insn) {
InsnData::Jump { .. } => {
let out_edges = &self.blocks[block].out_edges;
debug_assert_eq!(out_edges.len(), 1);
let out_edge = out_edges[0];
self.mark_edge_reachable(out_edge)
}
InsnData::Branch {
args,
dests: [then_dest, else_dest],
} => {
let cond = args[0];
let out_edges = &self.blocks[block].out_edges;
debug_assert_eq!(out_edges.len(), 2);
let then_edge = *out_edges
.iter()
.find(|edge| self.edge_data(**edge).to == *then_dest)
.unwrap();
let else_edge = *out_edges
.iter()
.find(|edge| self.edge_data(**edge).to == *else_dest)
.unwrap();
if self.infer_edge_reachability(func, cond, then_edge, domtree) {
self.mark_edge_reachable(then_edge)
} else if self.infer_edge_reachability(func, cond, else_edge, domtree) {
self.mark_edge_reachable(else_edge)
} else {
let changed = self.mark_edge_reachable(then_edge);
changed || self.mark_edge_reachable(else_edge)
}
}
InsnData::BrTable {
args,
default,
table,
} => {
let cond = args[0];
for dest in table {
let edge = self.find_edge(&self.blocks[block].out_edges, block, *dest);
if self.infer_edge_reachability(func, cond, edge, domtree) {
return self.mark_edge_reachable(edge);
}
}
let mut changed = false;
if let Some(default) = default {
let edge_to_default =
self.find_edge(&self.blocks[block].out_edges, block, *default);
changed |= self.mark_edge_reachable(edge_to_default);
}
for dest in table {
let edge = self.find_edge(&self.blocks[block].out_edges, block, *dest);
changed |= self.mark_edge_reachable(edge);
}
changed
}
_ => false,
}
}
fn reassign_congruence(
&mut self,
func: &mut Function,
domtree: &DomTree,
insn: Insn,
insn_result: Value,
) -> bool {
let block = func.layout.insn_block(insn);
let gvn_insn = self.perform_symbolic_evaluation(
func,
domtree,
func.dfg.insn_data(insn).clone(),
block,
);
if func.dfg.has_side_effect(insn) {
if self.value_class(insn_result) == INITIAL_CLASS {
let class = self.make_class(gvn_insn, None);
self.assign_class(insn_result, class);
return true;
} else {
return false;
}
}
let mut changed = false;
let new_class = if let GvnInsn::Value(value) = &gvn_insn {
self.value_class(*value)
} else if let Some(class) = self.insn_table.get(&gvn_insn).copied() {
changed |= self.recompute_value_phi(func, &gvn_insn, insn_result);
class
} else if let Some(value_phi) =
ValuePhiFinder::new(self, insn_result).compute_value_phi(func, &gvn_insn)
{
if let Some(class) = self.value_phi_table.get(&value_phi) {
*class
} else {
self.make_class(gvn_insn.clone(), Some(value_phi))
}
} else {
self.make_class(gvn_insn.clone(), None)
};
let old_class = self.value_class(insn_result);
if old_class == new_class {
changed
} else {
self.assign_class(insn_result, new_class);
true
}
}
fn recompute_value_phi(
&mut self,
func: &mut Function,
insn_data: &GvnInsn,
insn_result: Value,
) -> bool {
let value_phi = ValuePhiFinder::new(self, insn_result).compute_value_phi(func, insn_data);
let class = self.value_class(insn_result);
let old_value_phi = &mut self.classes[class].value_phi;
if &value_phi == old_value_phi {
false
} else {
*old_value_phi = value_phi;
true
}
}
fn mark_edge_reachable(&mut self, edge: Edge) -> bool {
let edge_data = &mut self.edges[edge];
let dest = edge_data.to;
if !edge_data.reachable {
edge_data.reachable = true;
self.blocks[dest].reachable = true;
true
} else {
false
}
}
fn infer_edge_reachability(
&self,
func: &Function,
cond: Value,
edge: Edge,
domtree: &DomTree,
) -> bool {
let edge_data = &self.edges[edge];
let resolved_cond = match edge_data.resolved_cond.expand() {
Some(cond) => cond,
None => return true,
};
let inferred_value = self.infer_value_at_block(func, domtree, cond, edge_data.from);
self.is_congruent_value(inferred_value, resolved_cond)
}
fn infer_value_at_block(
&self,
func: &Function,
domtree: &DomTree,
value: Value,
target_block: Block,
) -> Value {
let mut rep_value = self.leader(value);
let mut current_block = Some(target_block);
while current_block.is_some() && (!func.dfg.is_imm(rep_value)) {
let block = current_block.unwrap();
if let Some(dominant_edge) = self.dominant_reachable_in_edges(block) {
if self.is_back_edge(dominant_edge) {
break;
}
if let Some(value) = self.infer_value_impl(dominant_edge, rep_value) {
rep_value = value;
current_block = Some(target_block);
} else {
current_block = Some(self.edge_data(dominant_edge).from);
}
} else {
current_block = domtree.idom_of(block);
}
}
rep_value
}
fn infer_value_at_edge(
&self,
func: &Function,
domtree: &DomTree,
value: Value,
edge: Edge,
) -> Value {
let mut rep_value = self.leader(value);
if let Some(inferred_value) = self.infer_value_impl(edge, rep_value) {
rep_value = inferred_value;
}
self.infer_value_at_block(func, domtree, rep_value, self.edge_data(edge).from)
}
fn infer_value_impl(&self, edge: Edge, value: Value) -> Option<Value> {
let edge_data = self.edge_data(edge);
let edge_cond = edge_data.cond.expand()?;
if self.is_congruent_value(edge_cond, value) {
return Some(edge_data.resolved_cond.unwrap());
}
let predicate = edge_data.predicate.as_ref()?;
match predicate {
InsnData::Binary {
code: BinaryOp::Eq,
args: [lhs, rhs],
} => {
if self.is_congruent_value(*lhs, value)
&& self.value_rank(*rhs) < self.value_rank(value)
{
Some(*rhs)
} else if self.is_congruent_value(*rhs, value)
&& self.value_rank(*lhs) < self.value_rank(value)
{
Some(*lhs)
} else {
None
}
}
_ => None,
}
}
fn reachable_in_edges(&self, block: Block) -> impl Iterator<Item = &Edge> {
self.blocks[block]
.in_edges
.iter()
.filter(|edge| self.edge_data(**edge).reachable)
}
fn unreachable_out_edges(&self, block: Block) -> impl Iterator<Item = &Edge> {
self.blocks[block]
.out_edges
.iter()
.filter(|edge| !self.edge_data(**edge).reachable)
}
fn dominant_reachable_in_edges(&self, block: Block) -> Option<Edge> {
let mut edges = self.reachable_in_edges(block);
let dominant = edges.next()?;
if edges.next().is_none() {
Some(*dominant)
} else {
None
}
}
fn is_congruent_value(&self, lhs: Value, rhs: Value) -> bool {
let lhs_class = self.values[lhs].class;
let rhs_class = self.values[rhs].class;
(lhs_class == rhs_class) && (lhs_class != INITIAL_CLASS)
}
fn perform_symbolic_evaluation(
&mut self,
func: &mut Function,
domtree: &DomTree,
insn_data: InsnData,
block: Block,
) -> GvnInsn {
let insn_data = match insn_data {
InsnData::Unary { code, args: [arg] } => {
let arg = self.infer_value_at_block(func, domtree, arg, block);
InsnData::unary(code, arg)
}
InsnData::Binary {
code,
args: [lhs, rhs],
} => {
let mut lhs = self.infer_value_at_block(func, domtree, lhs, block);
let mut rhs = self.infer_value_at_block(func, domtree, rhs, block);
if code.is_commutative() && self.value_rank(rhs) < self.value_rank(lhs) {
std::mem::swap(&mut lhs, &mut rhs);
}
InsnData::binary(code, lhs, rhs)
}
InsnData::Cast {
code,
args: [arg],
ty,
} => {
let arg = self.infer_value_at_block(func, domtree, arg, block);
InsnData::cast(code, arg, ty)
}
InsnData::Store { .. }
| InsnData::Load { .. }
| InsnData::Call { .. }
| InsnData::Jump { .. }
| InsnData::Branch { .. }
| InsnData::BrTable { .. }
| InsnData::Alloca { .. }
| InsnData::Gep { .. }
| InsnData::Return { .. } => insn_data.clone(),
InsnData::Phi { values, blocks, ty } => {
let edges = &self.blocks[block].in_edges;
let mut phi_args = Vec::with_capacity(values.len());
for (&value, &from) in (values).iter().zip(blocks.iter()) {
let edge = self.find_edge(edges, from, block);
if !self.edge_data(edge).reachable {
continue;
}
let inferred_value = self.infer_value_at_edge(func, domtree, value, edge);
phi_args.push((inferred_value, from));
}
phi_args.sort_unstable_by(|(_, block1), (_, block2)| {
self.block_rank(*block1).cmp(&self.block_rank(*block2))
});
InsnData::Phi {
values: phi_args.iter().map(|(value, _)| *value).collect(),
blocks: phi_args.iter().map(|(_, block)| *block).collect(),
ty,
}
}
};
if let Some(imm) = self.perform_constant_folding(func, &insn_data) {
GvnInsn::Value(imm)
} else if let Some(result) = self.perform_simplification(&mut func.dfg, &insn_data) {
result
} else {
GvnInsn::Insn(insn_data)
}
}
fn perform_constant_folding(
&mut self,
func: &mut Function,
insn_data: &InsnData,
) -> Option<Value> {
constant_folding::fold_constant(&func.dfg, insn_data)
.map(|imm| self.make_imm(&mut func.dfg, imm))
}
fn perform_simplification(
&mut self,
dfg: &mut DataFlowGraph,
insn_data: &InsnData,
) -> Option<GvnInsn> {
simplify_impl::simplify_insn_data(dfg, insn_data.clone()).map(|res| match res {
simplify_impl::SimplifyResult::Value(value) => {
if let Some(imm) = dfg.value_imm(value) {
GvnInsn::Value(self.make_imm(dfg, imm))
} else {
GvnInsn::Value(value)
}
}
simplify_impl::SimplifyResult::Insn(insn) => GvnInsn::Insn(insn),
})
}
fn perform_predicate_simplification(
&mut self,
dfg: &mut DataFlowGraph,
insn_data: InsnData,
) -> InsnData {
if let Some(GvnInsn::Insn(insn)) = self.perform_simplification(dfg, &insn_data) {
insn
} else {
insn_data.clone()
}
}
fn add_edge_info(
&mut self,
from: Block,
to: Block,
cond: Option<Value>,
predicate: Option<InsnData>,
resolved_cond: Option<Value>,
) {
let edge_data = EdgeData {
from,
to,
cond: cond.into(),
predicate,
resolved_cond: resolved_cond.into(),
reachable: false,
};
let edge = self.edges.push(edge_data);
self.blocks[to].in_edges.push(edge);
self.blocks[from].out_edges.push(edge);
}
fn assign_class(&mut self, value: Value, class: Class) {
let old_class = self.value_class(value);
if old_class == class {
return;
}
let value_rank = self.value_rank(value);
let class_data = &mut self.classes[class];
class_data.values.insert((value_rank, value));
self.values[value].class = class;
let old_class_data = &mut self.classes[old_class];
old_class_data.values.remove(&(value_rank, value));
if let Some(insn_class) = self.insn_table.get_mut(&old_class_data.gvn_insn) {
if *insn_class == old_class && old_class_data.values.is_empty() {
self.insn_table.remove(&old_class_data.gvn_insn);
if let Some(value_phi) = &old_class_data.value_phi {
self.value_phi_table.remove(value_phi);
}
}
}
}
fn make_imm(&mut self, dfg: &mut DataFlowGraph, imm: impl Into<Immediate>) -> Value {
let value = dfg.make_imm_value(imm);
self.assign_class_to_imm_value(value);
value
}
fn assign_class_to_imm_value(&mut self, value: Value) {
let class = self.values[value].class;
let gvn_insn = GvnInsn::Value(value);
if class != INITIAL_CLASS {
debug_assert_eq!(self.values[value].rank, IMMEDIATE_RANK);
return;
}
self.values[value].rank = IMMEDIATE_RANK;
self.always_avail.push(value);
let class = self.make_class(gvn_insn, None);
self.assign_class(value, class);
}
fn is_back_edge(&self, edge: Edge) -> bool {
let from = self.edge_data(edge).from;
let to = self.edge_data(edge).to;
self.blocks[to].rank <= self.blocks[from].rank
}
fn leader(&self, value: Value) -> Value {
let class = self.values[value].class;
self.class_data(class).values.iter().next().unwrap().1
}
fn class_leader(&self, class: Class) -> Value {
self.class_data(class).values.iter().next().unwrap().1
}
fn edge_data(&self, edge: Edge) -> &EdgeData {
&self.edges[edge]
}
fn class_data(&self, class: Class) -> &ClassData {
&self.classes[class]
}
fn value_class(&self, value: Value) -> Class {
self.values[value].class
}
fn value_rank(&self, value: Value) -> u32 {
self.values[value].rank
}
fn block_rank(&self, block: Block) -> u32 {
self.blocks[block].rank
}
fn make_class(&mut self, gvn_insn: GvnInsn, value_phi: Option<ValuePhi>) -> Class {
let class_data = ClassData {
values: BTreeSet::new(),
gvn_insn: gvn_insn.clone(),
value_phi: value_phi.clone(),
};
let class = self.classes.push(class_data);
self.insn_table.insert(gvn_insn, class);
if let Some(value_phi) = value_phi {
self.value_phi_table.insert(value_phi, class);
}
class
}
fn find_edge(&self, edges: &[Edge], from: Block, to: Block) -> Edge {
edges
.iter()
.find(|edge| {
let data = self.edge_data(**edge);
data.from == from && data.to == to
})
.copied()
.unwrap()
}
}
impl Default for GvnSolver {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone, PartialEq, Eq, Copy, Hash, PartialOrd, Ord)]
struct Class(u32);
entity_impl!(Class);
#[derive(Debug, Clone, PartialEq)]
struct ClassData {
values: BTreeSet<(u32, Value)>,
gvn_insn: GvnInsn,
value_phi: Option<ValuePhi>,
}
#[derive(Debug, Clone, PartialEq)]
struct GvnValueData {
class: Class,
rank: u32,
}
impl Default for GvnValueData {
fn default() -> Self {
Self {
class: INITIAL_CLASS,
rank: 0,
}
}
}
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
enum GvnInsn {
Value(Value),
Insn(InsnData),
}
impl From<Value> for GvnInsn {
fn from(value: Value) -> Self {
Self::Value(value)
}
}
impl From<InsnData> for GvnInsn {
fn from(insn: InsnData) -> Self {
Self::Insn(insn)
}
}
#[derive(Debug, Clone, PartialEq, Eq, Copy, Hash, PartialOrd, Ord)]
struct Edge(u32);
entity_impl!(Edge);
#[derive(Debug, Clone)]
struct EdgeData {
from: Block,
to: Block,
cond: PackedOption<Value>,
predicate: Option<InsnData>,
resolved_cond: PackedOption<Value>,
reachable: bool,
}
#[derive(Debug, Default, Clone)]
struct GvnBlockData {
in_edges: Vec<Edge>,
out_edges: Vec<Edge>,
reachable: bool,
rank: u32,
}
struct ValuePhiFinder<'a> {
solver: &'a mut GvnSolver,
visited: FxHashSet<Value>,
}
impl<'a> ValuePhiFinder<'a> {
fn new(solver: &'a mut GvnSolver, insn_result: Value) -> Self {
let mut visited = FxHashSet::default();
visited.insert(insn_result);
Self { solver, visited }
}
fn compute_value_phi(&mut self, func: &mut Function, gvn_insn: &GvnInsn) -> Option<ValuePhi> {
let insn_data = if let GvnInsn::Insn(insn_data) = gvn_insn {
insn_data
} else {
return None;
};
match insn_data {
InsnData::Unary { code, args: [arg] } => {
let arg = self.get_phi_of(func, *arg)?;
self.compute_value_phi_for_unary(func, *code, arg)
}
InsnData::Binary {
code,
args: [lhs, rhs],
} => {
let (lhs, rhs) = if lhs == rhs {
let lhs_phi = self.get_phi_of(func, *lhs)?;
let rhs_phi = lhs_phi.clone();
(lhs_phi, rhs_phi)
} else {
match (self.get_phi_of(func, *lhs), self.get_phi_of(func, *rhs)) {
(Some(lhs_phi), Some(rhs_phi)) => (lhs_phi, rhs_phi),
(Some(lhs_phi), None) => (lhs_phi, ValuePhi::Value(*rhs)),
(None, Some(rhs_phi)) => (ValuePhi::Value(*lhs), rhs_phi),
(None, None) => return None,
}
};
self.compute_value_phi_for_binary(func, *code, lhs, rhs)
}
InsnData::Cast {
code,
args: [arg],
ty,
} => {
let arg = self.get_phi_of(func, *arg)?;
self.compute_value_phi_for_cast(func, *code, arg, *ty)
}
_ => None,
}
}
fn compute_value_phi_for_unary(
&mut self,
func: &mut Function,
code: UnaryOp,
value_phi: ValuePhi,
) -> Option<ValuePhi> {
let value_phi_insn = if let ValuePhi::PhiInsn(insn) = value_phi {
insn
} else {
return None;
};
let mut result =
ValuePhiInsn::with_capacity(value_phi_insn.block, value_phi_insn.args.len());
for (arg, block) in value_phi_insn.args.into_iter() {
match arg {
ValuePhi::Value(value) => {
let query_insn = InsnData::unary(code, value);
let phi_arg = self.lookup_value_phi_arg(func, query_insn)?;
result.args.push((phi_arg, block));
}
ValuePhi::PhiInsn(_) => {
let phi_arg = self.compute_value_phi_for_unary(func, code, arg)?;
result.args.push((phi_arg, block));
}
}
}
Some(result.canonicalize())
}
fn compute_value_phi_for_binary(
&mut self,
func: &mut Function,
code: BinaryOp,
lhs: ValuePhi,
rhs: ValuePhi,
) -> Option<ValuePhi> {
let (args, phi_block): (Vec<_>, _) = match (lhs, rhs) {
(ValuePhi::PhiInsn(lhs_phi), ValuePhi::PhiInsn(rhs_phi)) => {
if lhs_phi.block != rhs_phi.block || lhs_phi.args.len() != rhs_phi.args.len() {
return None;
}
let mut args = Vec::with_capacity(lhs_phi.args.len());
for ((lhs_arg, lhs_block), (rhs_arg, rhs_block)) in
lhs_phi.args.into_iter().zip(rhs_phi.args.into_iter())
{
if lhs_block != rhs_block {
return None;
}
args.push(((lhs_arg, rhs_arg), lhs_block));
}
(args, lhs_phi.block)
}
(ValuePhi::PhiInsn(lhs_phi), ValuePhi::Value(rhs_value)) => (
lhs_phi
.args
.into_iter()
.map(|(phi_arg, block)| ((phi_arg, ValuePhi::Value(rhs_value)), block))
.collect(),
lhs_phi.block,
),
(ValuePhi::Value(lhs_value), ValuePhi::PhiInsn(rhs_phi)) => (
rhs_phi
.args
.into_iter()
.map(|(phi_arg, block)| ((ValuePhi::Value(lhs_value), phi_arg), block))
.collect(),
rhs_phi.block,
),
(ValuePhi::Value(_), ValuePhi::Value(_)) => return None,
};
let mut result = ValuePhiInsn::with_capacity(phi_block, args.len());
for ((lhs_arg, rhs_arg), block) in args {
match (lhs_arg, rhs_arg) {
(ValuePhi::Value(mut lhs_value), ValuePhi::Value(mut rhs_value)) => {
if code.is_commutative()
&& self.solver.value_rank(rhs_value) < self.solver.value_rank(lhs_value)
{
std::mem::swap(&mut lhs_value, &mut rhs_value);
}
let query_insn = InsnData::binary(code, lhs_value, rhs_value);
let phi_arg = self.lookup_value_phi_arg(func, query_insn)?;
result.args.push((phi_arg, block));
}
(lhs_arg, rhs_arg) => {
let phi_arg =
self.compute_value_phi_for_binary(func, code, lhs_arg, rhs_arg)?;
result.args.push((phi_arg, block));
}
}
}
Some(result.canonicalize())
}
fn compute_value_phi_for_cast(
&mut self,
func: &mut Function,
code: CastOp,
value_phi: ValuePhi,
ty: Type,
) -> Option<ValuePhi> {
let value_phi_insn = if let ValuePhi::PhiInsn(insn) = value_phi {
insn
} else {
return None;
};
let mut result =
ValuePhiInsn::with_capacity(value_phi_insn.block, value_phi_insn.args.len());
for (arg, block) in value_phi_insn.args.into_iter() {
match arg {
ValuePhi::Value(value) => {
let query_insn = InsnData::cast(code, value, ty);
let phi_arg = self.lookup_value_phi_arg(func, query_insn)?;
result.args.push((phi_arg, block));
}
ValuePhi::PhiInsn(_) => {
let phi_arg = self.compute_value_phi_for_cast(func, code, arg, ty)?;
result.args.push((phi_arg, block));
}
}
}
Some(result.canonicalize())
}
fn lookup_value_phi_arg(&mut self, func: &mut Function, query: InsnData) -> Option<ValuePhi> {
let query = if let Some(imm) = self.solver.perform_constant_folding(func, &query) {
return Some(ValuePhi::Value(imm));
} else if let Some(simplified) = self.solver.perform_simplification(&mut func.dfg, &query) {
if let GvnInsn::Value(value) = simplified {
return Some(ValuePhi::Value(value));
} else {
simplified
}
} else {
GvnInsn::Insn(query)
};
if let Some(class) = self.solver.insn_table.get(&query) {
let leader = self.solver.class_leader(*class);
return Some(ValuePhi::Value(leader));
}
self.compute_value_phi(func, &query)
}
fn get_phi_of(&mut self, func: &Function, value: Value) -> Option<ValuePhi> {
if !self.visited.insert(value) {
return None;
}
let class = self.solver.value_class(value);
let phi_block = func.layout.insn_block(func.dfg.value_insn(value)?);
if let GvnInsn::Insn(InsnData::Phi { values, blocks, .. }) =
&self.solver.classes[class].gvn_insn
{
let mut result = ValuePhiInsn::with_capacity(phi_block, values.len());
let in_edges = &self.solver.blocks[phi_block].in_edges;
for (value, from) in values.iter().copied().zip(blocks.iter().copied()) {
let edge = self.solver.find_edge(in_edges, from, phi_block);
if self.solver.edges[edge].reachable {
result.args.push((ValuePhi::Value(value), from))
}
}
return Some(result.canonicalize());
};
let class = self.solver.value_class(value);
match &self.solver.classes[class].value_phi {
value_phi @ Some(ValuePhi::PhiInsn(..)) => value_phi.clone(),
_ => None,
}
}
}
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
enum ValuePhi {
Value(Value),
PhiInsn(ValuePhiInsn),
}
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct ValuePhiInsn {
block: Block,
args: Vec<(ValuePhi, Block)>,
}
impl ValuePhiInsn {
fn with_capacity(block: Block, cap: usize) -> Self {
Self {
block,
args: Vec::with_capacity(cap),
}
}
fn canonicalize(mut self) -> ValuePhi {
let first_arg = &self.args[0].0;
if self
.args
.iter()
.all(|(value_phi, _)| value_phi == first_arg)
{
first_arg.clone()
} else {
self.args.sort_by_key(|(_, block)| *block);
ValuePhi::PhiInsn(self)
}
}
}
struct RedundantCodeRemover<'a> {
solver: &'a GvnSolver,
avail_set: SecondaryMap<Block, FxHashMap<Class, Value>>,
resolved_value_phis: FxHashMap<ValuePhi, Value>,
}
impl<'a> RedundantCodeRemover<'a> {
fn new(solver: &'a GvnSolver) -> Self {
Self {
solver,
avail_set: SecondaryMap::default(),
resolved_value_phis: FxHashMap::default(),
}
}
fn remove_redundant_code(
&mut self,
func: &mut Function,
cfg: &mut ControlFlowGraph,
domtree: &mut DomTree,
) {
self.remove_unreachable_edges(func);
cfg.compute(func);
domtree.compute(cfg);
let mut domtree_traversable = DominatorTreeTraversable::default();
domtree_traversable.compute(domtree);
let entry = func.layout.entry_block().unwrap();
let mut blocks = vec![entry];
while let Some(block) = blocks.pop() {
blocks.extend_from_slice(domtree_traversable.children_of(block));
self.remove_code_in_block(func, domtree, block);
}
let mut next_block = Some(entry);
while let Some(block) = next_block {
self.resolve_value_phi_in_block(func, block);
next_block = func.layout.next_block_of(block);
}
}
fn remove_code_in_block(&mut self, func: &mut Function, domtree: &DomTree, block: Block) {
let mut avails = if block == func.layout.entry_block().unwrap() {
let mut avails = FxHashMap::default();
for &avail in &self.solver.always_avail {
let class = self.solver.value_class(avail);
avails.insert(class, avail);
}
avails
} else {
let idom = domtree.idom_of(block).unwrap();
self.avail_set[idom].clone()
};
let mut inserter = InsnInserter::new(func, CursorLocation::BlockTop(block));
loop {
match inserter.loc() {
CursorLocation::BlockTop(_) => {
inserter.proceed();
}
CursorLocation::BlockBottom(..) | CursorLocation::NoWhere => {
break;
}
CursorLocation::At(insn) => {
let block = inserter.block().unwrap();
if let Some(insn_result) = inserter.func().dfg.insn_result(insn) {
let class = self.solver.value_class(insn_result);
if let Some(value) = avails.get(&class) {
inserter.func_mut().dfg.change_to_alias(insn_result, *value);
inserter.remove_insn();
continue;
}
self.rewrite_phi(inserter.func_mut(), insn, block);
avails.insert(class, insn_result);
}
inserter.proceed();
}
}
}
self.avail_set[block] = avails;
}
fn resolve_value_phi_in_block(&mut self, func: &mut Function, block: Block) {
let mut inserter = InsnInserter::new(func, CursorLocation::BlockTop(block));
loop {
match inserter.loc() {
CursorLocation::BlockTop(_) => {
inserter.proceed();
}
CursorLocation::BlockBottom(..) | CursorLocation::NoWhere => {
break;
}
CursorLocation::At(insn) => {
let block = inserter.block().unwrap();
if let Some(insn_result) = inserter.func().dfg.insn_result(insn) {
let class = self.solver.value_class(insn_result);
if let Some(value_phi) = &self.solver.classes[class].value_phi {
let ty = inserter.func().dfg.value_ty(insn_result);
if self.is_value_phi_resolvable(value_phi, block) {
let value =
self.resolve_value_phi(&mut inserter, value_phi, ty, block);
inserter.func_mut().dfg.change_to_alias(insn_result, value);
inserter.remove_insn();
continue;
}
}
}
inserter.proceed();
}
}
}
}
fn is_value_phi_resolvable(&self, value_phi: &ValuePhi, block: Block) -> bool {
if self.resolved_value_phis.contains_key(value_phi) {
return true;
}
match value_phi {
ValuePhi::Value(value) => {
let class = self.solver.value_class(*value);
self.avail_set[block].contains_key(&class)
}
ValuePhi::PhiInsn(phi_insn) => {
for (value_phi, phi_block) in &phi_insn.args {
if !self.is_value_phi_resolvable(value_phi, *phi_block) {
return false;
}
}
true
}
}
}
fn resolve_value_phi(
&mut self,
inserter: &mut InsnInserter,
value_phi: &ValuePhi,
ty: Type,
block: Block,
) -> Value {
debug_assert!(self.is_value_phi_resolvable(value_phi, block));
if let Some(value) = self.resolved_value_phis.get(value_phi) {
return *value;
}
match value_phi {
ValuePhi::Value(value) => {
let class = self.solver.value_class(*value);
self.avail_set[block].get(&class).copied().unwrap()
}
ValuePhi::PhiInsn(phi_insn) => {
let current_inserter_loc = inserter.loc();
let mut phi = InsnData::phi(ty);
for (value_phi, phi_block) in &phi_insn.args {
let resolved = self.resolve_value_phi(inserter, value_phi, ty, *phi_block);
phi.append_phi_arg(resolved, *phi_block);
}
inserter.set_loc(CursorLocation::BlockTop(phi_insn.block));
let insn = inserter.insert_insn_data(phi);
let result = inserter.make_result(insn).unwrap();
inserter.attach_result(insn, result);
inserter.set_loc(current_inserter_loc);
self.resolved_value_phis.insert(value_phi.clone(), result);
result
}
}
}
fn remove_unreachable_edges(&self, func: &mut Function) {
let entry_block = func.layout.entry_block().unwrap();
let mut inserter = InsnInserter::new(func, CursorLocation::BlockTop(entry_block));
loop {
match inserter.loc() {
CursorLocation::BlockTop(block) => {
if !self.solver.blocks[block].reachable {
inserter.remove_block();
} else {
inserter.proceed();
}
}
CursorLocation::BlockBottom(..) => inserter.proceed(),
CursorLocation::At(insn) => {
if inserter.func().dfg.is_branch(insn) {
let block = inserter.block().unwrap();
for &out_edge in self.solver.unreachable_out_edges(block) {
let edge_data = self.solver.edge_data(out_edge);
inserter
.func_mut()
.dfg
.remove_branch_dest(insn, edge_data.to);
}
}
inserter.proceed();
}
CursorLocation::NoWhere => break,
}
}
}
fn rewrite_phi(&self, func: &mut Function, insn: Insn, block: Block) {
if !func.dfg.is_phi(insn) {
return;
}
let edges = &self.solver.blocks[block].in_edges;
for &edge in edges {
let edge_data = self.solver.edge_data(edge);
if !edge_data.reachable {
func.dfg.remove_phi_arg(insn, edge_data.from);
}
}
}
}