use crate::Variable;
use alloc::vec::Vec;
use core::convert::TryInto;
use core::mem;
use cranelift_codegen::cursor::{Cursor, FuncCursor};
use cranelift_codegen::entity::SecondaryMap;
use cranelift_codegen::ir::immediates::{Ieee32, Ieee64};
use cranelift_codegen::ir::instructions::BranchInfo;
use cranelift_codegen::ir::types::{F32, F64};
use cranelift_codegen::ir::{Block, Function, Inst, InstBuilder, InstructionData, Type, Value};
use cranelift_codegen::packed_option::PackedOption;
use smallvec::SmallVec;
pub struct SSABuilder {
variables: SecondaryMap<Variable, SecondaryMap<Block, PackedOption<Value>>>,
ssa_blocks: SecondaryMap<Block, SSABlockData>,
calls: Vec<Call>,
results: Vec<Value>,
side_effects: SideEffects,
}
pub struct SideEffects {
pub split_blocks_created: Vec<Block>,
pub instructions_added_to_blocks: Vec<Block>,
}
impl SideEffects {
fn new() -> Self {
Self {
split_blocks_created: Vec::new(),
instructions_added_to_blocks: Vec::new(),
}
}
fn is_empty(&self) -> bool {
self.split_blocks_created.is_empty() && self.instructions_added_to_blocks.is_empty()
}
}
#[derive(Clone)]
struct PredBlock {
block: Block,
branch: Inst,
}
impl PredBlock {
fn new(block: Block, branch: Inst) -> Self {
Self { block, branch }
}
}
type PredBlockSmallVec = SmallVec<[PredBlock; 4]>;
#[derive(Clone, Default)]
struct SSABlockData {
predecessors: PredBlockSmallVec,
sealed: bool,
undef_variables: Vec<(Variable, Value)>,
}
impl SSABlockData {
fn add_predecessor(&mut self, pred: Block, inst: Inst) {
debug_assert!(!self.sealed, "sealed blocks cannot accept new predecessors");
self.predecessors.push(PredBlock::new(pred, inst));
}
fn remove_predecessor(&mut self, inst: Inst) -> Block {
let pred = self
.predecessors
.iter()
.position(|&PredBlock { branch, .. }| branch == inst)
.expect("the predecessor you are trying to remove is not declared");
self.predecessors.swap_remove(pred).block
}
}
impl SSABuilder {
pub fn new() -> Self {
Self {
variables: SecondaryMap::with_default(SecondaryMap::new()),
ssa_blocks: SecondaryMap::new(),
calls: Vec::new(),
results: Vec::new(),
side_effects: SideEffects::new(),
}
}
pub fn clear(&mut self) {
self.variables.clear();
self.ssa_blocks.clear();
debug_assert!(self.calls.is_empty());
debug_assert!(self.results.is_empty());
debug_assert!(self.side_effects.is_empty());
}
pub fn is_empty(&self) -> bool {
self.variables.is_empty()
&& self.ssa_blocks.is_empty()
&& self.calls.is_empty()
&& self.results.is_empty()
&& self.side_effects.is_empty()
}
}
#[derive(Debug)]
enum ZeroOneOrMore<T> {
Zero,
One(T),
More,
}
#[derive(Debug)]
enum UseVarCases {
Unsealed(Value),
SealedOnePredecessor(Block),
SealedMultiplePredecessors(Value, Block),
}
enum Call {
UseVar(Block),
FinishSealedOnePredecessor(Block),
FinishPredecessorsLookup(Value, Block),
}
fn emit_zero(ty: Type, mut cur: FuncCursor) -> Value {
if ty.is_int() {
cur.ins().iconst(ty, 0)
} else if ty.is_bool() {
cur.ins().bconst(ty, false)
} else if ty == F32 {
cur.ins().f32const(Ieee32::with_bits(0))
} else if ty == F64 {
cur.ins().f64const(Ieee64::with_bits(0))
} else if ty.is_ref() {
cur.ins().null(ty)
} else if ty.is_vector() {
let scalar_ty = ty.lane_type();
if scalar_ty.is_int() || scalar_ty.is_bool() {
let zero = cur.func.dfg.constants.insert(
core::iter::repeat(0)
.take(ty.bytes().try_into().unwrap())
.collect(),
);
cur.ins().vconst(ty, zero)
} else if scalar_ty == F32 {
let scalar = cur.ins().f32const(Ieee32::with_bits(0));
cur.ins().splat(ty, scalar)
} else if scalar_ty == F64 {
let scalar = cur.ins().f64const(Ieee64::with_bits(0));
cur.ins().splat(ty, scalar)
} else {
panic!("unimplemented scalar type: {:?}", ty)
}
} else {
panic!("unimplemented type: {:?}", ty)
}
}
impl SSABuilder {
pub fn def_var(&mut self, var: Variable, val: Value, block: Block) {
self.variables[var][block] = PackedOption::from(val);
}
pub fn use_var(
&mut self,
func: &mut Function,
var: Variable,
ty: Type,
block: Block,
) -> (Value, SideEffects) {
if let Some(var_defs) = self.variables.get(var) {
if let Some(val) = var_defs[block].expand() {
return (val, SideEffects::new());
}
}
debug_assert!(self.calls.is_empty());
debug_assert!(self.results.is_empty());
debug_assert!(self.side_effects.is_empty());
self.use_var_nonlocal(func, var, ty, block);
let value = self.run_state_machine(func, var, ty);
let side_effects = mem::replace(&mut self.side_effects, SideEffects::new());
(value, side_effects)
}
fn use_var_nonlocal(&mut self, func: &mut Function, var: Variable, ty: Type, block: Block) {
let data = &mut self.ssa_blocks[block];
let case = if data.sealed {
if data.predecessors.len() == 1 {
UseVarCases::SealedOnePredecessor(data.predecessors[0].block)
} else {
let val = func.dfg.append_block_param(block, ty);
UseVarCases::SealedMultiplePredecessors(val, block)
}
} else {
let val = func.dfg.append_block_param(block, ty);
data.undef_variables.push((var, val));
UseVarCases::Unsealed(val)
};
match case {
UseVarCases::SealedOnePredecessor(pred) => {
self.calls.push(Call::FinishSealedOnePredecessor(block));
self.calls.push(Call::UseVar(pred));
}
UseVarCases::Unsealed(val) => {
self.def_var(var, val, block);
self.results.push(val);
}
UseVarCases::SealedMultiplePredecessors(val, block) => {
self.def_var(var, val, block);
self.begin_predecessors_lookup(val, block);
}
}
}
fn finish_sealed_one_predecessor(&mut self, var: Variable, block: Block) {
let val = *self.results.last().unwrap();
self.def_var(var, val, block);
}
pub fn declare_block(&mut self, block: Block) {
self.ssa_blocks[block] = SSABlockData {
predecessors: PredBlockSmallVec::new(),
sealed: false,
undef_variables: Vec::new(),
};
}
pub fn declare_block_predecessor(&mut self, block: Block, pred: Block, inst: Inst) {
debug_assert!(!self.is_sealed(block));
self.ssa_blocks[block].add_predecessor(pred, inst)
}
pub fn remove_block_predecessor(&mut self, block: Block, inst: Inst) -> Block {
debug_assert!(!self.is_sealed(block));
self.ssa_blocks[block].remove_predecessor(inst)
}
pub fn seal_block(&mut self, block: Block, func: &mut Function) -> SideEffects {
self.seal_one_block(block, func);
mem::replace(&mut self.side_effects, SideEffects::new())
}
pub fn seal_all_blocks(&mut self, func: &mut Function) -> SideEffects {
for block in self.ssa_blocks.keys() {
if !self.is_sealed(block) {
self.seal_one_block(block, func);
}
}
mem::replace(&mut self.side_effects, SideEffects::new())
}
fn seal_one_block(&mut self, block: Block, func: &mut Function) {
let block_data = &mut self.ssa_blocks[block];
debug_assert!(
!block_data.sealed,
"Attempting to seal {} which is already sealed.",
block
);
let undef_vars = mem::replace(&mut block_data.undef_variables, Vec::new());
for (var, val) in undef_vars {
let ty = func.dfg.value_type(val);
self.predecessors_lookup(func, val, var, ty, block);
}
self.mark_block_sealed(block);
}
fn mark_block_sealed(&mut self, block: Block) {
let block_data = &mut self.ssa_blocks[block];
debug_assert!(!block_data.sealed);
debug_assert!(block_data.undef_variables.is_empty());
block_data.sealed = true;
}
fn predecessors_lookup(
&mut self,
func: &mut Function,
sentinel: Value,
var: Variable,
ty: Type,
block: Block,
) -> Value {
debug_assert!(self.calls.is_empty());
debug_assert!(self.results.is_empty());
self.begin_predecessors_lookup(sentinel, block);
self.run_state_machine(func, var, ty)
}
fn begin_predecessors_lookup(&mut self, sentinel: Value, dest_block: Block) {
self.calls
.push(Call::FinishPredecessorsLookup(sentinel, dest_block));
let mut calls = mem::replace(&mut self.calls, Vec::new());
calls.extend(
self.predecessors(dest_block)
.iter()
.rev()
.map(|&PredBlock { block: pred, .. }| Call::UseVar(pred)),
);
self.calls = calls;
}
fn finish_predecessors_lookup(
&mut self,
func: &mut Function,
sentinel: Value,
var: Variable,
dest_block: Block,
) {
let mut pred_values: ZeroOneOrMore<Value> = ZeroOneOrMore::Zero;
let num_predecessors = self.predecessors(dest_block).len();
for &pred_val in self.results.iter().rev().take(num_predecessors) {
match pred_values {
ZeroOneOrMore::Zero => {
if pred_val != sentinel {
pred_values = ZeroOneOrMore::One(pred_val);
}
}
ZeroOneOrMore::One(old_val) => {
if pred_val != sentinel && pred_val != old_val {
pred_values = ZeroOneOrMore::More;
break;
}
}
ZeroOneOrMore::More => {
break;
}
}
}
self.results.truncate(self.results.len() - num_predecessors);
let result_val = match pred_values {
ZeroOneOrMore::Zero => {
if !func.layout.is_block_inserted(dest_block) {
func.layout.append_block(dest_block);
}
self.side_effects
.instructions_added_to_blocks
.push(dest_block);
let zero = emit_zero(
func.dfg.value_type(sentinel),
FuncCursor::new(func).at_first_insertion_point(dest_block),
);
func.dfg.remove_block_param(sentinel);
func.dfg.change_to_alias(sentinel, zero);
zero
}
ZeroOneOrMore::One(pred_val) => {
let mut resolved = func.dfg.resolve_aliases(pred_val);
if sentinel == resolved {
resolved = emit_zero(
func.dfg.value_type(sentinel),
FuncCursor::new(func).at_first_insertion_point(dest_block),
);
}
func.dfg.remove_block_param(sentinel);
func.dfg.change_to_alias(sentinel, resolved);
resolved
}
ZeroOneOrMore::More => {
let mut preds =
mem::replace(self.predecessors_mut(dest_block), PredBlockSmallVec::new());
for &mut PredBlock {
block: ref mut pred_block,
branch: ref mut last_inst,
} in &mut preds
{
let ssa_block_map = self.variables.get(var).unwrap();
let pred_val = ssa_block_map.get(*pred_block).unwrap().unwrap();
let jump_arg = self.append_jump_argument(
func,
*last_inst,
*pred_block,
dest_block,
pred_val,
var,
);
if let Some((middle_block, middle_jump_inst)) = jump_arg {
*pred_block = middle_block;
*last_inst = middle_jump_inst;
self.side_effects.split_blocks_created.push(middle_block);
}
}
debug_assert!(self.predecessors(dest_block).is_empty());
*self.predecessors_mut(dest_block) = preds;
sentinel
}
};
self.results.push(result_val);
}
fn append_jump_argument(
&mut self,
func: &mut Function,
jump_inst: Inst,
jump_inst_block: Block,
dest_block: Block,
val: Value,
var: Variable,
) -> Option<(Block, Inst)> {
match func.dfg.analyze_branch(jump_inst) {
BranchInfo::NotABranch => {
panic!("you have declared a non-branch instruction as a predecessor to a block");
}
BranchInfo::SingleDest(_, _) => {
func.dfg.append_inst_arg(jump_inst, val);
None
}
BranchInfo::Table(jt, default_block) => {
let middle_block = func.dfg.make_block();
func.layout.append_block(middle_block);
self.declare_block(middle_block);
self.ssa_blocks[middle_block].add_predecessor(jump_inst_block, jump_inst);
self.mark_block_sealed(middle_block);
if let Some(default_block) = default_block {
if dest_block == default_block {
match func.dfg[jump_inst] {
InstructionData::BranchTable {
destination: ref mut dest,
..
} => {
*dest = middle_block;
}
_ => panic!("should not happen"),
}
}
}
for old_dest in func.jump_tables[jt].as_mut_slice() {
if *old_dest == dest_block {
*old_dest = middle_block;
}
}
let mut cur = FuncCursor::new(func).at_bottom(middle_block);
let middle_jump_inst = cur.ins().jump(dest_block, &[val]);
self.def_var(var, val, middle_block);
Some((middle_block, middle_jump_inst))
}
}
}
fn predecessors(&self, block: Block) -> &[PredBlock] {
&self.ssa_blocks[block].predecessors
}
pub fn has_any_predecessors(&self, block: Block) -> bool {
!self.predecessors(block).is_empty()
}
fn predecessors_mut(&mut self, block: Block) -> &mut PredBlockSmallVec {
&mut self.ssa_blocks[block].predecessors
}
pub fn is_sealed(&self, block: Block) -> bool {
self.ssa_blocks[block].sealed
}
fn run_state_machine(&mut self, func: &mut Function, var: Variable, ty: Type) -> Value {
while let Some(call) = self.calls.pop() {
match call {
Call::UseVar(ssa_block) => {
if let Some(var_defs) = self.variables.get(var) {
if let Some(val) = var_defs[ssa_block].expand() {
self.results.push(val);
continue;
}
}
self.use_var_nonlocal(func, var, ty, ssa_block);
}
Call::FinishSealedOnePredecessor(ssa_block) => {
self.finish_sealed_one_predecessor(var, ssa_block);
}
Call::FinishPredecessorsLookup(sentinel, dest_block) => {
self.finish_predecessors_lookup(func, sentinel, var, dest_block);
}
}
}
debug_assert_eq!(self.results.len(), 1);
self.results.pop().unwrap()
}
}
#[cfg(test)]
mod tests {
use crate::ssa::SSABuilder;
use crate::Variable;
use cranelift_codegen::cursor::{Cursor, FuncCursor};
use cranelift_codegen::entity::EntityRef;
use cranelift_codegen::ir::instructions::BranchInfo;
use cranelift_codegen::ir::types::*;
use cranelift_codegen::ir::{Function, Inst, InstBuilder, JumpTableData, Opcode};
use cranelift_codegen::settings;
use cranelift_codegen::verify_function;
#[test]
fn simple_block() {
let mut func = Function::new();
let mut ssa = SSABuilder::new();
let block0 = func.dfg.make_block();
ssa.declare_block(block0);
let x_var = Variable::new(0);
let x_ssa = {
let mut cur = FuncCursor::new(&mut func);
cur.insert_block(block0);
cur.ins().iconst(I32, 1)
};
ssa.def_var(x_var, x_ssa, block0);
let y_var = Variable::new(1);
let y_ssa = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
cur.ins().iconst(I32, 2)
};
ssa.def_var(y_var, y_ssa, block0);
assert_eq!(ssa.use_var(&mut func, x_var, I32, block0).0, x_ssa);
assert_eq!(ssa.use_var(&mut func, y_var, I32, block0).0, y_ssa);
let z_var = Variable::new(2);
let x_use1 = ssa.use_var(&mut func, x_var, I32, block0).0;
let y_use1 = ssa.use_var(&mut func, y_var, I32, block0).0;
let z1_ssa = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
cur.ins().iadd(x_use1, y_use1)
};
ssa.def_var(z_var, z1_ssa, block0);
assert_eq!(ssa.use_var(&mut func, z_var, I32, block0).0, z1_ssa);
let x_use2 = ssa.use_var(&mut func, x_var, I32, block0).0;
let z_use1 = ssa.use_var(&mut func, z_var, I32, block0).0;
let z2_ssa = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
cur.ins().iadd(x_use2, z_use1)
};
ssa.def_var(z_var, z2_ssa, block0);
assert_eq!(ssa.use_var(&mut func, z_var, I32, block0).0, z2_ssa);
}
#[test]
fn sequence_of_blocks() {
let mut func = Function::new();
let mut ssa = SSABuilder::new();
let block0 = func.dfg.make_block();
let block1 = func.dfg.make_block();
let block2 = func.dfg.make_block();
{
let mut cur = FuncCursor::new(&mut func);
cur.insert_block(block0);
cur.insert_block(block1);
cur.insert_block(block2);
}
ssa.declare_block(block0);
ssa.seal_block(block0, &mut func);
let x_var = Variable::new(0);
let x_ssa = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
cur.ins().iconst(I32, 1)
};
ssa.def_var(x_var, x_ssa, block0);
let y_var = Variable::new(1);
let y_ssa = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
cur.ins().iconst(I32, 2)
};
ssa.def_var(y_var, y_ssa, block0);
let z_var = Variable::new(2);
let x_use1 = ssa.use_var(&mut func, x_var, I32, block0).0;
let y_use1 = ssa.use_var(&mut func, y_var, I32, block0).0;
let z1_ssa = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
cur.ins().iadd(x_use1, y_use1)
};
ssa.def_var(z_var, z1_ssa, block0);
let y_use2 = ssa.use_var(&mut func, y_var, I32, block0).0;
let brnz_block0_block2: Inst = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
cur.ins().brnz(y_use2, block2, &[])
};
let jump_block0_block1: Inst = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
cur.ins().jump(block1, &[])
};
assert_eq!(ssa.use_var(&mut func, x_var, I32, block0).0, x_ssa);
assert_eq!(ssa.use_var(&mut func, y_var, I32, block0).0, y_ssa);
assert_eq!(ssa.use_var(&mut func, z_var, I32, block0).0, z1_ssa);
ssa.declare_block(block1);
ssa.declare_block_predecessor(block1, block0, jump_block0_block1);
ssa.seal_block(block1, &mut func);
let x_use2 = ssa.use_var(&mut func, x_var, I32, block1).0;
let z_use1 = ssa.use_var(&mut func, z_var, I32, block1).0;
let z2_ssa = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block1);
cur.ins().iadd(x_use2, z_use1)
};
ssa.def_var(z_var, z2_ssa, block1);
let jump_block1_block2: Inst = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block1);
cur.ins().jump(block2, &[])
};
assert_eq!(x_use2, x_ssa);
assert_eq!(z_use1, z1_ssa);
assert_eq!(ssa.use_var(&mut func, z_var, I32, block1).0, z2_ssa);
ssa.declare_block(block2);
ssa.declare_block_predecessor(block2, block0, brnz_block0_block2);
ssa.declare_block_predecessor(block2, block1, jump_block1_block2);
ssa.seal_block(block2, &mut func);
let x_use3 = ssa.use_var(&mut func, x_var, I32, block2).0;
let y_use3 = ssa.use_var(&mut func, y_var, I32, block2).0;
let y2_ssa = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block2);
cur.ins().iadd(x_use3, y_use3)
};
ssa.def_var(y_var, y2_ssa, block2);
assert_eq!(x_ssa, x_use3);
assert_eq!(y_ssa, y_use3);
match func.dfg.analyze_branch(brnz_block0_block2) {
BranchInfo::SingleDest(dest, jump_args) => {
assert_eq!(dest, block2);
assert_eq!(jump_args.len(), 0);
}
_ => assert!(false),
};
match func.dfg.analyze_branch(jump_block0_block1) {
BranchInfo::SingleDest(dest, jump_args) => {
assert_eq!(dest, block1);
assert_eq!(jump_args.len(), 0);
}
_ => assert!(false),
};
match func.dfg.analyze_branch(jump_block1_block2) {
BranchInfo::SingleDest(dest, jump_args) => {
assert_eq!(dest, block2);
assert_eq!(jump_args.len(), 0);
}
_ => assert!(false),
};
}
#[test]
fn program_with_loop() {
let mut func = Function::new();
let mut ssa = SSABuilder::new();
let block0 = func.dfg.make_block();
let block1 = func.dfg.make_block();
let block2 = func.dfg.make_block();
let block3 = func.dfg.make_block();
{
let mut cur = FuncCursor::new(&mut func);
cur.insert_block(block0);
cur.insert_block(block1);
cur.insert_block(block2);
cur.insert_block(block3);
}
ssa.declare_block(block0);
ssa.seal_block(block0, &mut func);
let x_var = Variable::new(0);
let x1 = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
cur.ins().iconst(I32, 1)
};
ssa.def_var(x_var, x1, block0);
let y_var = Variable::new(1);
let y1 = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
cur.ins().iconst(I32, 2)
};
ssa.def_var(y_var, y1, block0);
let z_var = Variable::new(2);
let x2 = ssa.use_var(&mut func, x_var, I32, block0).0;
let y2 = ssa.use_var(&mut func, y_var, I32, block0).0;
let z1 = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
cur.ins().iadd(x2, y2)
};
ssa.def_var(z_var, z1, block0);
let jump_block0_block1 = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
cur.ins().jump(block1, &[])
};
assert_eq!(ssa.use_var(&mut func, x_var, I32, block0).0, x1);
assert_eq!(ssa.use_var(&mut func, y_var, I32, block0).0, y1);
assert_eq!(x2, x1);
assert_eq!(y2, y1);
ssa.declare_block(block1);
ssa.declare_block_predecessor(block1, block0, jump_block0_block1);
let z2 = ssa.use_var(&mut func, z_var, I32, block1).0;
let y3 = ssa.use_var(&mut func, y_var, I32, block1).0;
let z3 = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block1);
cur.ins().iadd(z2, y3)
};
ssa.def_var(z_var, z3, block1);
let y4 = ssa.use_var(&mut func, y_var, I32, block1).0;
assert_eq!(y4, y3);
let brnz_block1_block3 = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block1);
cur.ins().brnz(y4, block3, &[])
};
let jump_block1_block2 = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block1);
cur.ins().jump(block2, &[])
};
ssa.declare_block(block2);
ssa.declare_block_predecessor(block2, block1, jump_block1_block2);
ssa.seal_block(block2, &mut func);
let z4 = ssa.use_var(&mut func, z_var, I32, block2).0;
assert_eq!(z4, z3);
let x3 = ssa.use_var(&mut func, x_var, I32, block2).0;
let z5 = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block2);
cur.ins().isub(z4, x3)
};
ssa.def_var(z_var, z5, block2);
let y5 = ssa.use_var(&mut func, y_var, I32, block2).0;
assert_eq!(y5, y3);
{
let mut cur = FuncCursor::new(&mut func).at_bottom(block2);
cur.ins().return_(&[y5])
};
ssa.declare_block(block3);
ssa.declare_block_predecessor(block3, block1, brnz_block1_block3);
ssa.seal_block(block3, &mut func);
let y6 = ssa.use_var(&mut func, y_var, I32, block3).0;
assert_eq!(y6, y3);
let x4 = ssa.use_var(&mut func, x_var, I32, block3).0;
assert_eq!(x4, x3);
let y7 = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block3);
cur.ins().isub(y6, x4)
};
ssa.def_var(y_var, y7, block3);
let jump_block3_block1 = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block3);
cur.ins().jump(block1, &[])
};
ssa.declare_block_predecessor(block1, block3, jump_block3_block1);
ssa.seal_block(block1, &mut func);
assert_eq!(func.dfg.block_params(block1)[0], z2);
assert_eq!(func.dfg.block_params(block1)[1], y3);
assert_eq!(func.dfg.resolve_aliases(x3), x1);
}
#[test]
fn br_table_with_args() {
let mut func = Function::new();
let mut ssa = SSABuilder::new();
let block0 = func.dfg.make_block();
let block1 = func.dfg.make_block();
let block2 = func.dfg.make_block();
let mut jump_table = JumpTableData::new();
jump_table.push_entry(block2);
jump_table.push_entry(block1);
{
let mut cur = FuncCursor::new(&mut func);
cur.insert_block(block0);
cur.insert_block(block1);
cur.insert_block(block2);
}
let x1 = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
cur.ins().iconst(I32, 1)
};
ssa.declare_block(block0);
ssa.seal_block(block0, &mut func);
let x_var = Variable::new(0);
ssa.def_var(x_var, x1, block0);
ssa.use_var(&mut func, x_var, I32, block0).0;
let br_table = {
let jt = func.create_jump_table(jump_table);
let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
cur.ins().br_table(x1, block2, jt)
};
ssa.declare_block(block1);
ssa.declare_block_predecessor(block1, block0, br_table);
ssa.seal_block(block1, &mut func);
let x2 = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block1);
cur.ins().iconst(I32, 2)
};
ssa.def_var(x_var, x2, block1);
let jump_block1_block2 = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block1);
cur.ins().jump(block2, &[])
};
ssa.declare_block(block2);
ssa.declare_block_predecessor(block2, block1, jump_block1_block2);
ssa.declare_block_predecessor(block2, block0, br_table);
ssa.seal_block(block2, &mut func);
let x3 = ssa.use_var(&mut func, x_var, I32, block2).0;
let x4 = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block2);
cur.ins().iadd_imm(x3, 1)
};
ssa.def_var(x_var, x4, block2);
{
let mut cur = FuncCursor::new(&mut func).at_bottom(block2);
cur.ins().return_(&[])
};
let flags = settings::Flags::new(settings::builder());
match verify_function(&func, &flags) {
Ok(()) => {}
Err(_errors) => {
#[cfg(feature = "std")]
panic!(_errors);
#[cfg(not(feature = "std"))]
panic!("function failed to verify");
}
}
}
#[test]
fn undef_values_reordering() {
let mut func = Function::new();
let mut ssa = SSABuilder::new();
let block0 = func.dfg.make_block();
let block1 = func.dfg.make_block();
{
let mut cur = FuncCursor::new(&mut func);
cur.insert_block(block0);
cur.insert_block(block1);
}
ssa.declare_block(block0);
let x_var = Variable::new(0);
ssa.seal_block(block0, &mut func);
let x1 = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
cur.ins().iconst(I32, 0)
};
ssa.def_var(x_var, x1, block0);
let y_var = Variable::new(1);
let y1 = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
cur.ins().iconst(I32, 1)
};
ssa.def_var(y_var, y1, block0);
let z_var = Variable::new(2);
let z1 = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
cur.ins().iconst(I32, 2)
};
ssa.def_var(z_var, z1, block0);
let jump_block0_block1 = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
cur.ins().jump(block1, &[])
};
ssa.declare_block(block1);
ssa.declare_block_predecessor(block1, block0, jump_block0_block1);
let z2 = ssa.use_var(&mut func, z_var, I32, block1).0;
assert_eq!(func.dfg.block_params(block1)[0], z2);
let x2 = ssa.use_var(&mut func, x_var, I32, block1).0;
assert_eq!(func.dfg.block_params(block1)[1], x2);
let x3 = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block1);
cur.ins().iadd(x2, z2)
};
ssa.def_var(x_var, x3, block1);
let x4 = ssa.use_var(&mut func, x_var, I32, block1).0;
let y3 = ssa.use_var(&mut func, y_var, I32, block1).0;
assert_eq!(func.dfg.block_params(block1)[2], y3);
let y4 = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block1);
cur.ins().isub(y3, x4)
};
ssa.def_var(y_var, y4, block1);
let jump_block1_block1 = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block1);
cur.ins().jump(block1, &[])
};
ssa.declare_block_predecessor(block1, block1, jump_block1_block1);
ssa.seal_block(block1, &mut func);
assert_eq!(func.dfg.block_params(block1)[1], y3);
assert_eq!(func.dfg.block_params(block1)[0], x2);
}
#[test]
fn undef() {
let mut func = Function::new();
let mut ssa = SSABuilder::new();
let block0 = func.dfg.make_block();
ssa.declare_block(block0);
ssa.seal_block(block0, &mut func);
let i32_var = Variable::new(0);
let f32_var = Variable::new(1);
let f64_var = Variable::new(2);
let b1_var = Variable::new(3);
let f32x4_var = Variable::new(4);
ssa.use_var(&mut func, i32_var, I32, block0);
ssa.use_var(&mut func, f32_var, F32, block0);
ssa.use_var(&mut func, f64_var, F64, block0);
ssa.use_var(&mut func, b1_var, B1, block0);
ssa.use_var(&mut func, f32x4_var, F32X4, block0);
assert_eq!(func.dfg.num_block_params(block0), 0);
}
#[test]
fn undef_in_entry() {
let mut func = Function::new();
let mut ssa = SSABuilder::new();
let block0 = func.dfg.make_block();
ssa.declare_block(block0);
ssa.seal_block(block0, &mut func);
let x_var = Variable::new(0);
assert_eq!(func.dfg.num_block_params(block0), 0);
ssa.use_var(&mut func, x_var, I32, block0);
assert_eq!(func.dfg.num_block_params(block0), 0);
assert_eq!(
func.dfg[func.layout.first_inst(block0).unwrap()].opcode(),
Opcode::Iconst
);
}
#[test]
fn undef_in_entry_sealed_after() {
let mut func = Function::new();
let mut ssa = SSABuilder::new();
let block0 = func.dfg.make_block();
ssa.declare_block(block0);
let x_var = Variable::new(0);
assert_eq!(func.dfg.num_block_params(block0), 0);
ssa.use_var(&mut func, x_var, I32, block0);
assert_eq!(func.dfg.num_block_params(block0), 1);
ssa.seal_block(block0, &mut func);
assert_eq!(func.dfg.num_block_params(block0), 0);
assert_eq!(
func.dfg[func.layout.first_inst(block0).unwrap()].opcode(),
Opcode::Iconst
);
}
#[test]
fn unreachable_use() {
let mut func = Function::new();
let mut ssa = SSABuilder::new();
let block0 = func.dfg.make_block();
let block1 = func.dfg.make_block();
{
let mut cur = FuncCursor::new(&mut func);
cur.insert_block(block0);
cur.insert_block(block1);
}
ssa.declare_block(block0);
ssa.seal_block(block0, &mut func);
{
let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
cur.ins().return_(&[]);
}
ssa.declare_block(block1);
{
let mut cur = FuncCursor::new(&mut func).at_bottom(block1);
let x_var = Variable::new(0);
let x_val = ssa.use_var(&mut cur.func, x_var, I32, block1).0;
let brz = cur.ins().brz(x_val, block1, &[]);
let jump_block1_block1 = cur.ins().jump(block1, &[]);
ssa.declare_block_predecessor(block1, block1, brz);
ssa.declare_block_predecessor(block1, block1, jump_block1_block1);
}
ssa.seal_block(block1, &mut func);
let flags = settings::Flags::new(settings::builder());
match verify_function(&func, &flags) {
Ok(()) => {}
Err(_errors) => {
#[cfg(feature = "std")]
panic!(_errors);
#[cfg(not(feature = "std"))]
panic!("function failed to verify");
}
}
}
#[test]
fn unreachable_use_with_multiple_preds() {
let mut func = Function::new();
let mut ssa = SSABuilder::new();
let block0 = func.dfg.make_block();
let block1 = func.dfg.make_block();
let block2 = func.dfg.make_block();
{
let mut cur = FuncCursor::new(&mut func);
cur.insert_block(block0);
cur.insert_block(block1);
cur.insert_block(block2);
}
ssa.declare_block(block0);
ssa.seal_block(block0, &mut func);
{
let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
cur.ins().return_(&[]);
}
ssa.declare_block(block1);
let brz = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block1);
let x_var = Variable::new(0);
let x_val = ssa.use_var(&mut cur.func, x_var, I32, block1).0;
let brz = cur.ins().brz(x_val, block2, &[]);
let jump_block1_block1 = cur.ins().jump(block1, &[]);
ssa.declare_block_predecessor(block1, block1, jump_block1_block1);
brz
};
ssa.declare_block(block2);
ssa.declare_block_predecessor(block2, block1, brz);
ssa.seal_block(block2, &mut func);
let jump_block2_block1 = {
let mut cur = FuncCursor::new(&mut func).at_bottom(block2);
cur.ins().jump(block1, &[])
};
ssa.declare_block_predecessor(block1, block2, jump_block2_block1);
ssa.seal_block(block1, &mut func);
let flags = settings::Flags::new(settings::builder());
match verify_function(&func, &flags) {
Ok(()) => {}
Err(_errors) => {
#[cfg(feature = "std")]
panic!(_errors);
#[cfg(not(feature = "std"))]
panic!("function failed to verify");
}
}
}
}