use std::collections::{BinaryHeap, HashMap};
use super::dependency_graph::{Node, WgslDependencyGraph};
use crate::device::latency::LatencyModel;
#[derive(Debug, Eq, PartialEq)]
struct Schedulable {
release_cycle: u32,
original_order: usize,
node_idx: usize,
}
impl Ord for Schedulable {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
other
.release_cycle
.cmp(&self.release_cycle)
.then(other.original_order.cmp(&self.original_order))
.reverse()
}
}
impl PartialOrd for Schedulable {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
pub(super) struct IlpReorderer;
impl IlpReorderer {
#[must_use]
pub fn reorder(graph: &WgslDependencyGraph, model: &LatencyModel) -> Vec<String> {
let n = graph.nodes.len();
if n == 0 {
return vec![];
}
let mut dep_count: Vec<usize> = vec![0; n];
let mut successors: Vec<Vec<usize>> = vec![vec![]; n];
for (i, node) in graph.nodes.iter().enumerate() {
match node {
Node::Binding(b) => {
for &dep_idx in &b.deps {
successors[dep_idx].push(i);
dep_count[i] += 1;
}
}
Node::Passthrough(p) => {
let dep_indices = resolve_passthrough_deps(p, graph);
for dep_idx in dep_indices {
successors[dep_idx].push(i);
dep_count[i] += 1;
}
}
}
}
let mut release_cycle: Vec<u32> = vec![0; n];
for i in 0..n {
let lat = node_latency(&graph.nodes[i], model);
for &succ in &successors[i] {
let candidate = release_cycle[i] + lat;
if candidate > release_cycle[succ] {
release_cycle[succ] = candidate;
}
}
}
let mut ready: BinaryHeap<Schedulable> = BinaryHeap::new();
for (i, &cnt) in dep_count.iter().enumerate() {
if cnt == 0 {
ready.push(Schedulable {
release_cycle: release_cycle[i],
original_order: i,
node_idx: i,
});
}
}
let mut scheduled: Vec<String> = Vec::with_capacity(n);
let mut remaining_deps = dep_count.clone();
let mut scheduled_count = 0;
while let Some(item) = ready.pop() {
let idx = item.node_idx;
scheduled.push(graph.nodes[idx].source_line().to_string());
scheduled_count += 1;
for &succ in &successors[idx] {
remaining_deps[succ] -= 1;
if remaining_deps[succ] == 0 {
ready.push(Schedulable {
release_cycle: release_cycle[succ],
original_order: succ,
node_idx: succ,
});
}
}
}
if scheduled_count < n {
for (i, node) in graph.nodes.iter().enumerate() {
if remaining_deps[i] > 0 {
scheduled.push(node.source_line().to_string());
}
}
}
scheduled
}
}
fn node_latency(node: &Node, model: &LatencyModel) -> u32 {
match node {
Node::Binding(b) => model.raw_latency(b.op_class),
Node::Passthrough(_) => 0,
}
}
fn resolve_passthrough_deps(
p: &super::dependency_graph::PassthroughNode,
graph: &WgslDependencyGraph,
) -> Vec<usize> {
let name_map: HashMap<&str, usize> = graph
.nodes
.iter()
.enumerate()
.filter_map(|(i, n)| {
if let Node::Binding(b) = n {
Some((b.name.as_str(), i))
} else {
None
}
})
.collect();
p.dep_names
.iter()
.filter_map(|name| name_map.get(name.as_str()).copied())
.collect()
}
#[cfg(test)]
mod tests {
use super::*;
use crate::device::latency::LatencyModel;
use crate::shaders::optimizer::dependency_graph::WgslDependencyGraph;
#[test]
fn test_independent_bindings_reordered_for_ilp() {
let region = "\
let c = cos_val;\n\
let s = sin_val;\n\
let cc = c * c;\n\
let ss = s * s;\n\
let cs = c * s;\n\
let new_p = c * a_kp - s * a_kq;\n\
let new_q = s * a_kp + c * a_kq;\n";
let graph = WgslDependencyGraph::parse(region);
let model = LatencyModel::Sm70;
let scheduled = IlpReorderer::reorder(&graph, &model);
assert_eq!(scheduled.len(), graph.nodes.len());
let pos_c = scheduled
.iter()
.position(|l| l.contains("let c ="))
.unwrap();
let pos_new_p = scheduled
.iter()
.position(|l| l.contains("let new_p ="))
.unwrap();
assert!(pos_c < pos_new_p, "c must be scheduled before new_p");
let pos_s = scheduled
.iter()
.position(|l| l.contains("let s ="))
.unwrap();
let pos_new_q = scheduled
.iter()
.position(|l| l.contains("let new_q ="))
.unwrap();
assert!(pos_s < pos_new_q, "s must be scheduled before new_q");
}
#[test]
fn test_passthrough_after_deps() {
let region = "\
let a = x * y;\n\
let b = a + z;\n\
output[0] = b;\n";
let graph = WgslDependencyGraph::parse(region);
let model = LatencyModel::Sm70;
let scheduled = IlpReorderer::reorder(&graph, &model);
let pos_b = scheduled
.iter()
.position(|l| l.contains("let b ="))
.unwrap();
let pos_store = scheduled
.iter()
.position(|l| l.contains("output[0]"))
.unwrap();
assert!(pos_b < pos_store, "store must come after its dep b");
}
#[test]
fn test_empty_region() {
let graph = WgslDependencyGraph::parse("");
let model = LatencyModel::Sm70;
let scheduled = IlpReorderer::reorder(&graph, &model);
assert!(scheduled.is_empty());
}
#[test]
fn test_single_chain_preserves_order() {
let region = "\
let a = x;\n\
let b = a * 2.0;\n\
let c = b + 1.0;\n";
let graph = WgslDependencyGraph::parse(region);
let model = LatencyModel::Sm70;
let scheduled = IlpReorderer::reorder(&graph, &model);
let pos_a = scheduled
.iter()
.position(|l| l.contains("let a ="))
.unwrap();
let pos_b = scheduled
.iter()
.position(|l| l.contains("let b ="))
.unwrap();
let pos_c = scheduled
.iter()
.position(|l| l.contains("let c ="))
.unwrap();
assert!(pos_a < pos_b);
assert!(pos_b < pos_c);
}
#[test]
fn test_ilp_opportunity_detected() {
let region = "\
let c = cos_val;\n\
let s = sin_val;\n\
let cc = c * c;\n\
let new_p = c * a_kp - s * a_kq;\n";
let graph = WgslDependencyGraph::parse(region);
let model = LatencyModel::Sm70;
let scheduled = IlpReorderer::reorder(&graph, &model);
assert_eq!(scheduled.len(), 4);
let pc = scheduled
.iter()
.position(|l| l.contains("let c ="))
.unwrap();
let pcc = scheduled
.iter()
.position(|l| l.contains("let cc ="))
.unwrap();
assert!(pc < pcc);
}
}