use crate::{
dispatch::{
CompilationOptions, OptFlags,
backend::{DType, Op, ValueId, ValueState, kernel::RawKernel},
},
errors::Error,
};
use std::vec::Vec;
#[allow(clippy::unnecessary_wraps)]
pub fn optimize(kernel: &mut RawKernel, options: &CompilationOptions) -> Result<(), Error> {
for _ in 0..options.opt.passes {
dead_code_elimination(kernel, options);
if options.opt.flags.contains(OptFlags::UNUSED_MUT) {
for value_id in 0..kernel.values.len() {
if kernel.values[value_id].state == ValueState::Mut
&& kernel.values[value_id].init.is_some()
&& !(0..kernel.ops.len())
.any(|statement| kernel.ops[statement].does_mutate(value_id))
{
kernel.values[value_id].state = ValueState::Immut;
}
}
}
if options.opt.flags.contains(OptFlags::OP_ASSIGN) {
op_assign(kernel);
}
if options.opt.flags.contains(OptFlags::MUL_ADD) {
for value_id in 0..kernel.values.len() {
if kernel.values[value_id].state == ValueState::Masked
|| !matches!(
kernel.values[value_id].dtype,
DType::F32 | DType::F16 | DType::BF16
)
{
continue;
}
if let Some(Op::Add { a, b }) = kernel.values[value_id].init {
if let Some(Op::Mul { a: a_mul, b: b_mul }) = kernel.values[a].init {
kernel.values[value_id].init.replace(Op::Fma {
a: a_mul,
b: b_mul,
c: b,
});
} else if let Some(Op::Mul { a: a_mul, b: b_mul }) = kernel.values[b].init {
kernel.values[value_id].init.replace(Op::Fma {
a: a_mul,
b: b_mul,
c: a,
});
}
}
}
let additions = iter_values(kernel, |op, value_id| {
if kernel.values[value_id].state == ValueState::Masked
|| !matches!(
kernel.values[value_id].dtype,
DType::F32 | DType::F16 | DType::BF16
)
{
return None;
}
if let Op::Add { a, b } = &op {
Some((*a, *b, value_id))
} else {
None
}
});
for (a, b, value_id) in additions {
if let Some(Op::Mul { a: a_mul, b: b_mul }) = kernel.values[a].init {
kernel.values[value_id].init.replace(Op::Fma {
a: a_mul,
b: b_mul,
c: b,
});
}
if let Some(Op::Mul { a: a_mul, b: b_mul }) = kernel.values[b].init {
kernel.values[value_id].init.replace(Op::Fma {
a: a_mul,
b: b_mul,
c: a,
});
}
}
}
if options.opt.flags.contains(OptFlags::DIV_CONST) {
let divisions = iter_values(kernel, |op, value_id| {
if kernel.values[value_id].state == ValueState::Masked
|| !matches!(
kernel.values[value_id].dtype,
DType::F32 | DType::F16 | DType::BF16
)
{
return None;
}
if let Op::Div { a, b } = &op {
Some((*a, *b, value_id))
} else {
None
}
});
for (a, b, value_id) in divisions {
if kernel.values[b].state == ValueState::Mut {
continue;
}
if let Some(Op::ConstF32 { value }) = kernel.values[b].init {
kernel.values[b]
.init
.replace(Op::ConstF32 { value: 1.0 / value });
kernel.values[value_id].init.replace(Op::Mul { a, b });
}
}
}
if options.opt.flags.contains(OptFlags::CONST_FOLD) {
for value_id in 0..kernel.values.len() {
if kernel.values[value_id].state == ValueState::Masked {
continue;
}
const_fold(kernel, value_id);
}
}
if options.opt.flags.contains(OptFlags::IDENTITY) {
for value_id in 0..kernel.values.len() {
if kernel.values[value_id].state == ValueState::Masked {
continue;
}
identity(kernel, value_id);
}
}
if options.opt.flags.contains(OptFlags::COPY_IMMUT) {
for value_id in 0..kernel.values.len() {
if !matches!(
kernel.values[value_id].state,
ValueState::Inline | ValueState::Immut
) {
continue;
}
let copy_op = Op::CopyVar { id: value_id };
let copies = iter_values(kernel, |op, value_id| {
if op == ©_op && kernel.values[value_id].state != ValueState::Mut {
Some(value_id)
} else {
None
}
});
for copy_id in copies {
for value in &mut kernel.values {
if let Some(op) = &mut value.init {
op.replace_usage(copy_id, value_id);
}
}
for op in &mut kernel.ops {
op.replace_usage(copy_id, value_id);
}
}
}
}
kernel.ops = erase_nops(&kernel.ops);
}
dead_code_elimination(kernel, options);
Ok(())
}
#[inline]
fn dead_code_elimination(kernel: &mut RawKernel, options: &CompilationOptions) {
if options.opt.flags.contains(OptFlags::DEAD_CODE) {
for value_id in 0..kernel.values.len() {
if kernel.values[value_id].state == ValueState::Masked {
continue;
}
if !any_ops(kernel, |op| {
op.does_read(value_id) && !op.does_mutate(value_id)
}) {
kernel.values[value_id].state = ValueState::Masked;
erase_writes(kernel, value_id);
}
}
}
}
#[inline]
fn iter_values<R>(kernel: &RawKernel, mut f: impl FnMut(&Op, ValueId) -> Option<R>) -> Vec<R> {
let mut value_ids = Vec::new();
for value_id in 0..kernel.values.len() {
if kernel.values[value_id].state == ValueState::Masked {
continue;
}
if let Some(op) = &kernel.values[value_id].init
&& let Some(value) = f(op, value_id)
{
value_ids.push(value);
}
}
value_ids
}
#[inline]
fn any_ops(kernel: &RawKernel, mut f: impl FnMut(&Op) -> bool) -> bool {
for op in &kernel.ops {
if f(op) {
return true;
}
}
for value in &kernel.values {
if let Some(init) = &value.init
&& f(init)
{
return true;
}
}
false
}
#[inline]
fn erase_writes(kernel: &mut RawKernel, value_id: ValueId) {
for op in &mut kernel.ops {
if op.does_write(value_id) {
*op = Op::Nop;
}
}
}
#[inline]
fn erase_nops(ops: &[Op]) -> Vec<Op> {
let mut new_ops = Vec::new();
for op in ops {
if *op != Op::Nop {
new_ops.push(*op);
}
}
new_ops
}
macro_rules! const_fold_op {
($kernel:ident, $value_id:ident, $a:ident, $b:expr, $opu:path, $opi:path, $($opf:path)?) => {{
let a = $kernel.values[*$a];
let b = $kernel.values[*$b];
if a.state == ValueState::Mut
|| b.state == ValueState::Mut {
return;
}
if let Some(a_op) = a.init
&& let Some(b_op) = b.init {
match (a_op, b_op) {
$((Op::ConstF32 { value: a }, Op::ConstF32 { value: b }) => {
$kernel.values[$value_id].init.replace(Op::ConstF32 { value: $opf(a, b) });
})?
(Op::ConstU32 { value: a }, Op::ConstU32 { value: b }) => {
$kernel.values[$value_id].init.replace(Op::ConstU32 { value: $opu(a, b) });
}
(Op::ConstI32 { value: a }, Op::ConstI32 { value: b }) => {
$kernel.values[$value_id].init.replace(Op::ConstI32 { value: $opi(a, b) });
}
_ => {}
}
}
}};
}
#[inline]
fn const_fold(kernel: &mut RawKernel, value_id: ValueId) {
use core::ops::{Add, Div, Mul, Shl, Shr, Sub};
if let Some(init) = &kernel.values[value_id].init {
match init {
Op::Add { a, b } => {
const_fold_op!(kernel, value_id, a, b, u32::add, i32::add, f32::add);
}
Op::Mul { a, b } => {
const_fold_op!(kernel, value_id, a, b, u32::mul, i32::mul, f32::mul);
}
Op::Sub { a, b } => {
const_fold_op!(kernel, value_id, a, b, u32::sub, i32::sub, f32::sub);
}
Op::Div { a, b } => {
const_fold_op!(kernel, value_id, a, b, u32::div, i32::div, f32::div);
}
Op::Shr { a, b } => const_fold_op!(kernel, value_id, a, b, u32::shr, i32::shr,),
Op::Shl { a, b } => const_fold_op!(kernel, value_id, a, b, u32::shl, i32::shl,),
Op::Fma { a, b, c } => {
let a = kernel.values[*a];
let b = kernel.values[*b];
let c = kernel.values[*c];
if a.state == ValueState::Mut
|| b.state == ValueState::Mut
|| c.state == ValueState::Mut
{
return;
}
if let Some(Op::ConstF32 { value: a }) = a.init
&& let Some(Op::ConstF32 { value: b }) = b.init
&& let Some(Op::ConstF32 { value: c }) = c.init
{
kernel.values[value_id].init.replace(Op::ConstF32 {
value: a.mul_add(b, c),
});
}
}
_ => {}
}
}
}
#[inline]
fn identity(kernel: &mut RawKernel, value_id: ValueId) {
if let Some(init) = kernel.values[value_id].init {
match init {
Op::Add { a, b } => {
if kernel.values[a].init.is_some_and(|op| op.is_zero())
&& kernel.values[a].state != ValueState::Mut
{
kernel.values[value_id].init.replace(Op::CopyVar { id: b });
} else if kernel.values[b].init.is_some_and(|op| op.is_zero())
&& kernel.values[b].state != ValueState::Mut
{
kernel.values[value_id].init.replace(Op::CopyVar { id: a });
}
}
Op::Sub { a, b } => {
if kernel.values[b].init.is_some_and(|op| op.is_zero())
&& kernel.values[b].state != ValueState::Mut
{
kernel.values[value_id].init.replace(Op::CopyVar { id: a });
}
}
Op::Mul { a, b } => {
if kernel.values[a].init.is_some_and(|op| op.is_one())
&& kernel.values[a].state != ValueState::Mut
{
kernel.values[value_id].init.replace(Op::CopyVar { id: b });
}
if kernel.values[b].init.is_some_and(|op| op.is_one())
&& kernel.values[b].state != ValueState::Mut
{
kernel.values[value_id].init.replace(Op::CopyVar { id: a });
}
}
Op::Div { a, b }
if kernel.values[b].init.is_some_and(|op| op.is_one())
&& kernel.values[b].state != ValueState::Mut =>
{
kernel.values[value_id].init.replace(Op::CopyVar { id: a });
}
_ => {}
}
}
}
macro_rules! impl_op_assign {
(@var $kernel:ident, $op_id:ident, $id:ident, $value:ident, $($inline:ident => $assign:ident),*) => {
match $value.init {
$(
Some(Op::$inline { a, b }) => if a == $id {
$kernel.ops[$op_id] = Op::$assign { $id, val: b }
} else if b == $id {
$kernel.ops[$op_id] = Op::$assign { $id, val: a }
}
)*
_ => {}
}
};
(@param $load:ident, $kernel:ident, $op_id:ident, $param:ident, $index:ident, $value:ident, $($inline:ident => $assign:ident),*) => {
match $value.init {
$(
Some(Op::$inline { a, b }) => if $kernel.values[a].init == Some(Op::$load { $param, $index }) {
$kernel.ops[$op_id] = Op::$assign { $param, $index, value: b }
} else if $kernel.values[b].init == Some(Op::$load { $param, $index }) {
$kernel.ops[$op_id] = Op::$assign { $param, $index, value: a }
}
)*
_ => {}
}
};
}
#[inline]
fn op_assign(kernel: &mut RawKernel) {
for op_id in 0..kernel.ops.len() {
if let Op::OverwriteVar { id, val } = kernel.ops[op_id] {
let value = &mut kernel.values[val];
if value.state == ValueState::Inline {
impl_op_assign!(
@var
kernel,
op_id,
id,
value,
Add => AddAssign,
Sub => SubAssign,
Mul => MulAssign,
Div => DivAssign,
Shr => ShrAssign,
Shl => ShlAssign
);
}
}
if let Op::ParamStore {
param,
index,
value,
} = kernel.ops[op_id]
{
let value = &mut kernel.values[value];
if value.state == ValueState::Inline {
impl_op_assign!(
@param
ParamLoad,
kernel,
op_id,
param,
index,
value,
Add => ParamAccum,
Sub => ParamSub,
Mul => ParamMul,
Div => ParamDiv,
Shr => ParamShr,
Shl => ParamShl
);
}
}
if let Op::SharedStore { mem, index, value } = kernel.ops[op_id] {
let value = &mut kernel.values[value];
if value.state == ValueState::Inline {
impl_op_assign!(
@param
SharedLoad,
kernel,
op_id,
mem,
index,
value,
Add => SharedAccum,
Sub => SharedSub,
Mul => SharedMul,
Div => SharedDiv,
Shr => SharedShr,
Shl => SharedShl
);
}
}
}
}