pub mod dependency_graph;
pub mod ilp_reorderer;
pub mod loop_unroller;
use crate::device::latency::{LatencyModel, model_for_arch};
use dependency_graph::WgslDependencyGraph;
use ilp_reorderer::IlpReorderer;
pub use loop_unroller::WgslLoopUnroller;
const ILP_BEGIN: &str = "// @ilp_region begin";
const ILP_END: &str = "// @ilp_region end";
pub struct WgslOptimizer {
model: LatencyModel,
}
impl WgslOptimizer {
#[must_use]
pub fn new(model: LatencyModel) -> Self {
Self { model }
}
#[must_use]
pub fn for_arch(arch: crate::device::driver_profile::GpuArch) -> Self {
Self::new(model_for_arch(arch))
}
#[must_use]
pub fn optimize(&self, shader: &str) -> String {
let unrolled = WgslLoopUnroller::unroll(shader);
self.reorder_ilp_regions(&unrolled)
}
fn reorder_ilp_regions(&self, source: &str) -> String {
let mut output = String::with_capacity(source.len());
let mut rest: &str = source;
loop {
match rest.find(ILP_BEGIN) {
None => {
output.push_str(rest);
break;
}
Some(begin_pos) => {
output.push_str(&rest[..begin_pos]);
let after_begin = &rest[begin_pos..];
let marker_end = after_begin.find('\n').map_or(after_begin.len(), |p| p + 1);
output.push_str(&after_begin[..marker_end]);
let region_start = marker_end;
let region_src = &after_begin[region_start..];
match region_src.find(ILP_END) {
None => {
output.push_str(region_src);
break;
}
Some(end_pos) => {
let region_body = ®ion_src[..end_pos];
let after_end = ®ion_src[end_pos..];
let scheduled = self.schedule_region(region_body);
output.push_str(&scheduled);
let end_marker_end =
after_end.find('\n').map_or(after_end.len(), |p| p + 1);
output.push_str(&after_end[..end_marker_end]);
rest = &after_begin[region_start + end_pos + end_marker_end..];
}
}
}
}
}
output
}
fn schedule_region(&self, region_body: &str) -> String {
let graph = WgslDependencyGraph::parse(region_body);
if graph.is_empty() {
return region_body.to_string();
}
let scheduled_lines = IlpReorderer::reorder(&graph, &self.model);
let mut out = String::new();
for line in &scheduled_lines {
out.push_str(line);
if !line.ends_with('\n') {
out.push('\n');
}
}
out
}
}
impl Default for WgslOptimizer {
fn default() -> Self {
Self::new(LatencyModel::Conservative)
}
}
#[cfg(test)]
mod tests {
use super::*;
fn make_optimizer() -> WgslOptimizer {
WgslOptimizer::new(LatencyModel::Sm70)
}
#[test]
fn test_optimizer_passthrough_no_annotations() {
let shader = "fn main() {\n let x = 1.0;\n let y = x + 2.0;\n}\n";
let opt = make_optimizer();
assert_eq!(opt.optimize(shader), shader);
}
#[test]
fn test_optimizer_rewrites_ilp_region() {
let shader = "\
fn jacobi() {\n\
// @ilp_region begin\n\
let c = cos_val;\n\
let s = sin_val;\n\
let cc = c * c;\n\
let ss = s * s;\n\
let new_p = c * a_kp - s * a_kq;\n\
// @ilp_region end\n\
}\n";
let opt = make_optimizer();
let result = opt.optimize(shader);
assert!(result.contains(ILP_BEGIN));
assert!(result.contains(ILP_END));
assert!(result.contains("let c ="));
assert!(result.contains("let s ="));
assert!(result.contains("let cc ="));
assert!(result.contains("let ss ="));
assert!(result.contains("let new_p ="));
let pos_c = result.find("let c =").unwrap();
let pos_new_p = result.find("let new_p =").unwrap();
assert!(pos_c < pos_new_p);
}
#[test]
fn test_optimizer_unrolls_loop() {
let shader = "\
// @unroll_hint 3\n\
for (var k = 0u; k < 3u; k = k + 1u) {\n\
let v = k;\n\
}\n";
let opt = make_optimizer();
let result = opt.optimize(shader);
assert!(!result.contains("for (var k"));
assert!(result.contains("let k = 0u;"));
assert!(result.contains("let k = 1u;"));
assert!(result.contains("let k = 2u;"));
}
#[test]
fn test_multiple_ilp_regions() {
let shader = "\
// @ilp_region begin\n\
let a = x;\n\
// @ilp_region end\n\
// middle code\n\
// @ilp_region begin\n\
let b = y;\n\
// @ilp_region end\n";
let opt = make_optimizer();
let result = opt.optimize(shader);
assert!(result.contains("let a ="));
assert!(result.contains("let b ="));
assert!(result.contains("// middle code"));
assert_eq!(result.matches(ILP_BEGIN).count(), 2);
assert_eq!(result.matches(ILP_END).count(), 2);
}
#[test]
fn test_default_optimizer_conservative() {
let opt = WgslOptimizer::default();
assert_eq!(opt.optimize(""), "");
}
#[test]
fn test_for_arch_constructor() {
use crate::device::driver_profile::GpuArch;
let opt = WgslOptimizer::for_arch(GpuArch::Volta);
let result = opt.optimize("// @ilp_region begin\nlet x = 1.0;\n// @ilp_region end\n");
assert!(result.contains("let x ="));
}
#[test]
fn test_jacobi_kloop_variable_bound_unroll() {
let shader = concat!(
" // @unroll_hint 32\n",
" for (var k = 0u; k < n; k = k + 1u) {\n",
" if (k != p && k != q) {\n",
" let akp = A_batch[k * p];\n",
" let akq = A_batch[k * q];\n",
" let new_akp = c * akp - s * akq;\n",
" let new_akq = s * akp + c * akq;\n",
" A_batch[k * p] = new_akp;\n",
" A_batch[k * q] = new_akq;\n",
" }\n",
" }\n",
);
let opt = WgslOptimizer::default();
let result = opt.optimize(shader);
assert!(
!result.contains("for (var k"),
"for-loop should be unrolled"
);
assert_eq!(result.matches("let k = 0u;").count(), 1);
assert_eq!(result.matches("let k = 31u;").count(), 1);
assert_eq!(result.matches("let k = 32u;").count(), 0);
assert!(result.contains("if (0u < n)"), "iteration 0 needs guard");
assert!(result.contains("if (31u < n)"), "iteration 31 needs guard");
assert!(result.contains("A_batch[0u * p]"), "k=0 substitution");
assert!(result.contains("A_batch[31u * p]"), "k=31 substitution");
}
#[test]
fn test_ilp_region_then_unroll_coexist() {
let shader = concat!(
" // @ilp_region begin\n",
" let cc = c * c;\n",
" let ss = s * s;\n",
" // @ilp_region end\n",
" // @unroll_hint 2\n",
" for (var k = 0u; k < 2u; k = k + 1u) {\n",
" let x = k;\n",
" }\n",
);
let opt = WgslOptimizer::default();
let result = opt.optimize(shader);
assert!(result.contains(ILP_BEGIN));
assert!(result.contains("let cc ="));
assert!(result.contains("let ss ="));
assert!(result.contains(ILP_END));
assert!(!result.contains("for (var k"));
assert!(result.contains("let k = 0u;"));
assert!(result.contains("let k = 1u;"));
}
}