summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--doc/zjit.md8
-rw-r--r--zjit/src/hir.rs466
-rw-r--r--zjit/src/hir/tests.rs818
-rw-r--r--zjit/src/options.rs6
4 files changed, 1281 insertions, 17 deletions
diff --git a/doc/zjit.md b/doc/zjit.md
index 3d7ee33abf..bb20b9f692 100644
--- a/doc/zjit.md
+++ b/doc/zjit.md
@@ -162,6 +162,14 @@ A file called `zjit_exits_{pid}.dump` will be created in the same directory as `
stackprof path/to/zjit_exits_{pid}.dump
```
+### Viewing HIR in Iongraph
+
+Using `--zjit-dump-hir-iongraph` will dump all compiled functions into a directory named `/tmp/zjit-iongraph-{PROCESS_PID}`. Each file will be named `func_{ZJIT_FUNC_NAME}.json`. In order to use them in the Iongraph viewer, you'll need to use `jq` to collate them to a single file. An example invocation of `jq` is shown below for reference.
+
+`jq --slurp --null-input '.functions=inputs | .version=2' /tmp/zjit-iongraph-{PROCESS_PID}/func*.json > ~/Downloads/ion.json`
+
+From there, you can use https://mozilla-spidermonkey.github.io/iongraph/ to view your trace.
+
### Printing ZJIT Errors
`--zjit-debug` prints ZJIT compilation errors and other diagnostics:
diff --git a/zjit/src/hir.rs b/zjit/src/hir.rs
index 8e6241f0da..2640507e33 100644
--- a/zjit/src/hir.rs
+++ b/zjit/src/hir.rs
@@ -6,7 +6,7 @@
#![allow(clippy::if_same_then_else)]
#![allow(clippy::match_like_matches_macro)]
use crate::{
- cast::IntoUsize, codegen::local_idx_to_ep_offset, cruby::*, payload::{get_or_create_iseq_payload, IseqPayload}, options::{debug, get_option, DumpHIR}, state::ZJITState
+ cast::IntoUsize, codegen::local_idx_to_ep_offset, cruby::*, payload::{get_or_create_iseq_payload, IseqPayload}, options::{debug, get_option, DumpHIR}, state::ZJITState, json::Json
};
use std::{
cell::RefCell, collections::{HashMap, HashSet, VecDeque}, ffi::{c_void, c_uint, c_int, CStr}, fmt::Display, mem::{align_of, size_of}, ptr, slice::Iter
@@ -39,7 +39,7 @@ impl std::fmt::Display for InsnId {
}
/// The index of a [`Block`], which effectively acts like a pointer.
-#[derive(Copy, Clone, Eq, PartialEq, Hash, Debug)]
+#[derive(Copy, Clone, Eq, PartialEq, Hash, Debug, PartialOrd, Ord)]
pub struct BlockId(pub usize);
impl From<BlockId> for usize {
@@ -3686,23 +3686,171 @@ impl Function {
}
}
+ /// Helper function to make an Iongraph JSON "instruction".
+ /// `uses`, `memInputs` and `attributes` are left empty for now, but may be populated
+ /// in the future.
+ fn make_iongraph_instr(id: InsnId, inputs: Vec<Json>, opcode: &str, ty: &str) -> Json {
+ Json::object()
+ // Add an offset of 0x1000 to avoid the `ptr` being 0x0, which iongraph rejects.
+ .insert("ptr", id.0 + 0x1000)
+ .insert("id", id.0)
+ .insert("opcode", opcode)
+ .insert("attributes", Json::empty_array())
+ .insert("inputs", Json::Array(inputs))
+ .insert("uses", Json::empty_array())
+ .insert("memInputs", Json::empty_array())
+ .insert("type", ty)
+ .build()
+ }
+
+ /// Helper function to make an Iongraph JSON "block".
+ fn make_iongraph_block(id: BlockId, predecessors: Vec<BlockId>, successors: Vec<BlockId>, instructions: Vec<Json>, attributes: Vec<&str>, loop_depth: u32) -> Json {
+ Json::object()
+ // Add an offset of 0x1000 to avoid the `ptr` being 0x0, which iongraph rejects.
+ .insert("ptr", id.0 + 0x1000)
+ .insert("id", id.0)
+ .insert("loopDepth", loop_depth)
+ .insert("attributes", Json::array(attributes))
+ .insert("predecessors", Json::array(predecessors.iter().map(|x| x.0).collect::<Vec<usize>>()))
+ .insert("successors", Json::array(successors.iter().map(|x| x.0).collect::<Vec<usize>>()))
+ .insert("instructions", Json::array(instructions))
+ .build()
+ }
+
+ /// Helper function to make an Iongraph JSON "function".
+ /// Note that `lir` is unpopulated right now as ZJIT doesn't use its functionality.
+ fn make_iongraph_function(pass_name: &str, hir_blocks: Vec<Json>) -> Json {
+ Json::object()
+ .insert("name", pass_name)
+ .insert("mir", Json::object()
+ .insert("blocks", Json::array(hir_blocks))
+ .build()
+ )
+ .insert("lir", Json::object()
+ .insert("blocks", Json::empty_array())
+ .build()
+ )
+ .build()
+ }
+
+ /// Generate an iongraph JSON pass representation for this function.
+ pub fn to_iongraph_pass(&self, pass_name: &str) -> Json {
+ let mut ptr_map = PtrPrintMap::identity();
+ if cfg!(test) {
+ ptr_map.map_ptrs = true;
+ }
+
+ let mut hir_blocks = Vec::new();
+ let cfi = ControlFlowInfo::new(self);
+ let dominators = Dominators::new(self);
+ let loop_info = LoopInfo::new(&cfi, &dominators);
+
+ // Push each block from the iteration in reverse post order to `hir_blocks`.
+ for block_id in self.rpo() {
+ // Create the block with instructions.
+ let block = &self.blocks[block_id.0];
+ let predecessors = cfi.predecessors(block_id).collect();
+ let successors = cfi.successors(block_id).collect();
+ let mut instructions = Vec::new();
+
+ // Process all instructions (parameters and body instructions).
+ // Parameters are currently guaranteed to be Parameter instructions, but in the future
+ // they might be refined to other instruction kinds by the optimizer.
+ for insn_id in block.params.iter().chain(block.insns.iter()) {
+ let insn_id = self.union_find.borrow().find_const(*insn_id);
+ let insn = self.find(insn_id);
+
+ // Snapshots are not serialized, so skip them.
+ if matches!(insn, Insn::Snapshot {..}) {
+ continue;
+ }
+
+ // Instructions with no output or an empty type should have an empty type field.
+ let type_str = if insn.has_output() {
+ let insn_type = self.type_of(insn_id);
+ if insn_type.is_subtype(types::Empty) {
+ String::new()
+ } else {
+ insn_type.print(&ptr_map).to_string()
+ }
+ } else {
+ String::new()
+ };
+
+
+ let opcode = insn.print(&ptr_map).to_string();
+
+ // Traverse the worklist to get inputs for a given instruction.
+ let mut inputs = VecDeque::new();
+ self.worklist_traverse_single_insn(&insn, &mut inputs);
+ let inputs: Vec<Json> = inputs.into_iter().map(|x| x.0.into()).collect();
+
+ instructions.push(
+ Self::make_iongraph_instr(
+ insn_id,
+ inputs,
+ &opcode,
+ &type_str
+ )
+ );
+ }
+
+ let mut attributes = vec![];
+ if loop_info.is_back_edge_source(block_id) {
+ attributes.push("backedge");
+ }
+ if loop_info.is_loop_header(block_id) {
+ attributes.push("loopheader");
+ }
+ let loop_depth = loop_info.loop_depth(block_id);
+
+ hir_blocks.push(Self::make_iongraph_block(
+ block_id,
+ predecessors,
+ successors,
+ instructions,
+ attributes,
+ loop_depth,
+ ));
+ }
+
+ Self::make_iongraph_function(pass_name, hir_blocks)
+ }
+
/// Run all the optimization passes we have.
pub fn optimize(&mut self) {
+ let mut passes: Vec<Json> = Vec::new();
+ let should_dump = get_option!(dump_hir_iongraph);
+
+ macro_rules! run_pass {
+ ($name:ident) => {
+ self.$name();
+ #[cfg(debug_assertions)] self.assert_validates();
+ if should_dump {
+ passes.push(
+ self.to_iongraph_pass(stringify!($name))
+ );
+ }
+ }
+ }
+
+ if should_dump {
+ passes.push(self.to_iongraph_pass("unoptimized"));
+ }
+
// Function is assumed to have types inferred already
- self.type_specialize();
- #[cfg(debug_assertions)] self.assert_validates();
- self.inline();
- #[cfg(debug_assertions)] self.assert_validates();
- self.optimize_getivar();
- #[cfg(debug_assertions)] self.assert_validates();
- self.optimize_c_calls();
- #[cfg(debug_assertions)] self.assert_validates();
- self.fold_constants();
- #[cfg(debug_assertions)] self.assert_validates();
- self.clean_cfg();
- #[cfg(debug_assertions)] self.assert_validates();
- self.eliminate_dead_code();
- #[cfg(debug_assertions)] self.assert_validates();
+ run_pass!(type_specialize);
+ run_pass!(inline);
+ run_pass!(optimize_getivar);
+ run_pass!(optimize_c_calls);
+ run_pass!(fold_constants);
+ run_pass!(clean_cfg);
+ run_pass!(eliminate_dead_code);
+
+ if should_dump {
+ let iseq_name = iseq_get_location(self.iseq, 0);
+ self.dump_iongraph(&iseq_name, passes);
+ }
}
/// Dump HIR passed to codegen if specified by options.
@@ -3723,6 +3871,32 @@ impl Function {
}
}
+ pub fn dump_iongraph(&self, function_name: &str, passes: Vec<Json>) {
+ fn sanitize_for_filename(name: &str) -> String {
+ name.chars()
+ .map(|c| {
+ if c.is_ascii_alphanumeric() || c == '_' || c == '-' {
+ c
+ } else {
+ '_'
+ }
+ })
+ .collect()
+ }
+
+ use std::io::Write;
+ let dir = format!("/tmp/zjit-iongraph-{}", std::process::id());
+ std::fs::create_dir_all(&dir).expect("Unable to create directory.");
+ let sanitized = sanitize_for_filename(function_name);
+ let path = format!("{dir}/func_{sanitized}.json");
+ let mut file = std::fs::File::create(path).unwrap();
+ let json = Json::object()
+ .insert("name", function_name)
+ .insert("passes", passes)
+ .build();
+ writeln!(file, "{}", json).unwrap();
+ }
+
/// Validates the following:
/// 1. Basic block jump args match parameter arity.
/// 2. Every terminator must be in the last position.
@@ -4087,7 +4261,13 @@ impl Function {
impl<'a> std::fmt::Display for FunctionPrinter<'a> {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
let fun = &self.fun;
- let iseq_name = iseq_get_location(fun.iseq, 0);
+ // In tests, there may not be an iseq to get location from.
+ let iseq_name = if fun.iseq.is_null() {
+ String::from("<manual>")
+ } else {
+ iseq_get_location(fun.iseq, 0)
+ };
+
// In tests, strip the line number for builtin ISEQs to make tests stable across line changes
let iseq_name = if cfg!(test) && iseq_name.contains("@<internal:") {
iseq_name[..iseq_name.rfind(':').unwrap()].to_string()
@@ -5559,6 +5739,258 @@ fn compile_jit_entry_state(fun: &mut Function, jit_entry_block: BlockId, jit_ent
(self_param, entry_state)
}
+pub struct Dominators<'a> {
+ f: &'a Function,
+ dominators: Vec<Vec<BlockId>>,
+}
+
+impl<'a> Dominators<'a> {
+ pub fn new(f: &'a Function) -> Self {
+ let mut cfi = ControlFlowInfo::new(f);
+ Self::with_cfi(f, &mut cfi)
+ }
+
+ pub fn with_cfi(f: &'a Function, cfi: &mut ControlFlowInfo) -> Self {
+ let block_ids = f.rpo();
+ let mut dominators = vec![vec![]; f.blocks.len()];
+
+ // Compute dominators for each node using fixed point iteration.
+ // Approach can be found in Figure 1 of:
+ // https://www.cs.tufts.edu/~nr/cs257/archive/keith-cooper/dom14.pdf
+ //
+ // Initially we set:
+ //
+ // dom(entry) = {entry} for each entry block
+ // dom(b != entry) = {all nodes}
+ //
+ // Iteratively, apply:
+ //
+ // dom(b) = {b} union intersect(dom(p) for p in predecessors(b))
+ //
+ // When we've run the algorithm and the dominator set no longer changes
+ // between iterations, then we have found the dominator sets.
+
+ // Set up entry blocks.
+ // Entry blocks are only dominated by themselves.
+ for entry_block in &f.entry_blocks() {
+ dominators[entry_block.0] = vec![*entry_block];
+ }
+
+ // Setup the initial dominator sets.
+ for block_id in &block_ids {
+ if !f.entry_blocks().contains(block_id) {
+ // Non entry blocks are initially dominated by all other blocks.
+ dominators[block_id.0] = block_ids.clone();
+ }
+ }
+
+ let mut changed = true;
+ while changed {
+ changed = false;
+
+ for block_id in &block_ids {
+ if *block_id == f.entry_block {
+ continue;
+ }
+
+ // Get all predecessors for a given block.
+ let block_preds: Vec<BlockId> = cfi.predecessors(*block_id).collect();
+ if block_preds.is_empty() {
+ continue;
+ }
+
+ let mut new_doms = dominators[block_preds[0].0].clone();
+
+ // Compute the intersection of predecessor dominator sets into `new_doms`.
+ for pred_id in &block_preds[1..] {
+ let pred_doms = &dominators[pred_id.0];
+ // Only keep a dominator in `new_doms` if it is also found in pred_doms
+ new_doms.retain(|d| pred_doms.contains(d));
+ }
+
+ // Insert sorted into `new_doms`.
+ match new_doms.binary_search(block_id) {
+ Ok(_) => {}
+ Err(pos) => new_doms.insert(pos, *block_id)
+ }
+
+ // If we have computed a new dominator set, then we can update
+ // the dominators and mark that we need another iteration.
+ if dominators[block_id.0] != new_doms {
+ dominators[block_id.0] = new_doms;
+ changed = true;
+ }
+ }
+ }
+
+ Self { f, dominators }
+ }
+
+
+ pub fn is_dominated_by(&self, left: BlockId, right: BlockId) -> bool {
+ self.dominators(left).any(|&b| b == right)
+ }
+
+ pub fn dominators(&self, block: BlockId) -> Iter<'_, BlockId> {
+ self.dominators[block.0].iter()
+ }
+}
+
+pub struct ControlFlowInfo<'a> {
+ function: &'a Function,
+ successor_map: HashMap<BlockId, Vec<BlockId>>,
+ predecessor_map: HashMap<BlockId, Vec<BlockId>>,
+}
+
+impl<'a> ControlFlowInfo<'a> {
+ pub fn new(function: &'a Function) -> Self {
+ let mut successor_map: HashMap<BlockId, Vec<BlockId>> = HashMap::new();
+ let mut predecessor_map: HashMap<BlockId, Vec<BlockId>> = HashMap::new();
+ let uf = function.union_find.borrow();
+
+ for block_id in function.rpo() {
+ let block = &function.blocks[block_id.0];
+
+ // Since ZJIT uses extended basic blocks, one must check all instructions
+ // for their ability to jump to another basic block, rather than just
+ // the instructions at the end of a given basic block.
+ let successors: Vec<BlockId> = block
+ .insns
+ .iter()
+ .map(|&insn_id| uf.find_const(insn_id))
+ .filter_map(|insn_id| {
+ Self::extract_jump_target(&function.insns[insn_id.0])
+ })
+ .collect();
+
+ // Update predecessors for successor blocks.
+ for &succ_id in &successors {
+ predecessor_map
+ .entry(succ_id)
+ .or_default()
+ .push(block_id);
+ }
+
+ // Store successors for this block.
+ successor_map.insert(block_id, successors);
+ }
+
+ Self {
+ function,
+ successor_map,
+ predecessor_map,
+ }
+ }
+
+ pub fn is_succeeded_by(&self, left: BlockId, right: BlockId) -> bool {
+ self.successor_map.get(&right).is_some_and(|set| set.contains(&left))
+ }
+
+ pub fn is_preceded_by(&self, left: BlockId, right: BlockId) -> bool {
+ self.predecessor_map.get(&right).is_some_and(|set| set.contains(&left))
+ }
+
+ pub fn predecessors(&self, block: BlockId) -> impl Iterator<Item = BlockId> {
+ self.predecessor_map.get(&block).into_iter().flatten().copied()
+ }
+
+ pub fn successors(&self, block: BlockId) -> impl Iterator<Item = BlockId> {
+ self.successor_map.get(&block).into_iter().flatten().copied()
+ }
+
+ /// Helper function to extract the target of a jump instruction.
+ fn extract_jump_target(insn: &Insn) -> Option<BlockId> {
+ match insn {
+ Insn::Jump(target)
+ | Insn::IfTrue { target, .. }
+ | Insn::IfFalse { target, .. } => Some(target.target),
+ _ => None,
+ }
+ }
+}
+
+pub struct LoopInfo<'a> {
+ cfi: &'a ControlFlowInfo<'a>,
+ dominators: &'a Dominators<'a>,
+ loop_depths: HashMap<BlockId, u32>,
+ loop_headers: BlockSet,
+ back_edge_sources: BlockSet,
+}
+
+impl<'a> LoopInfo<'a> {
+ pub fn new(cfi: &'a ControlFlowInfo<'a>, dominators: &'a Dominators<'a>) -> Self {
+ let mut loop_headers: BlockSet = BlockSet::with_capacity(cfi.function.num_blocks());
+ let mut loop_depths: HashMap<BlockId, u32> = HashMap::new();
+ let mut back_edge_sources: BlockSet = BlockSet::with_capacity(cfi.function.num_blocks());
+ let rpo = cfi.function.rpo();
+
+ for &block in &rpo {
+ loop_depths.insert(block, 0);
+ }
+
+ // Collect loop headers.
+ for &block in &rpo {
+ // Initialize the loop depths.
+ for predecessor in cfi.predecessors(block) {
+ if dominators.is_dominated_by(predecessor, block) {
+ // Found a loop header, so then identify the natural loop.
+ loop_headers.insert(block);
+ back_edge_sources.insert(predecessor);
+ let loop_blocks = Self::find_natural_loop(cfi, block, predecessor);
+ // Increment the loop depth.
+ for loop_block in &loop_blocks {
+ *loop_depths.get_mut(loop_block).expect("Loop block should be populated.") += 1;
+ }
+ }
+ }
+ }
+
+ Self {
+ cfi,
+ dominators,
+ loop_depths,
+ loop_headers,
+ back_edge_sources,
+ }
+ }
+
+ fn find_natural_loop(
+ cfi: &ControlFlowInfo,
+ header: BlockId,
+ back_edge_source: BlockId,
+ ) -> HashSet<BlockId> {
+ // todo(aidenfoxivey): Reimplement using BlockSet
+ let mut loop_blocks = HashSet::new();
+ let mut stack = vec![back_edge_source];
+
+ loop_blocks.insert(header);
+ loop_blocks.insert(back_edge_source);
+
+ while let Some(block) = stack.pop() {
+ for pred in cfi.predecessors(block) {
+ // Pushes to stack only if `pred` wasn't already in `loop_blocks`.
+ if loop_blocks.insert(pred) {
+ stack.push(pred)
+ }
+ }
+ }
+
+ loop_blocks
+ }
+
+ pub fn loop_depth(&self, block: BlockId) -> u32 {
+ self.loop_depths.get(&block).copied().unwrap_or(0)
+ }
+
+ pub fn is_back_edge_source(&self, block: BlockId) -> bool {
+ self.back_edge_sources.get(block)
+ }
+
+ pub fn is_loop_header(&self, block: BlockId) -> bool {
+ self.loop_headers.get(block)
+ }
+}
+
#[cfg(test)]
mod union_find_tests {
use super::UnionFind;
diff --git a/zjit/src/hir/tests.rs b/zjit/src/hir/tests.rs
index abf2f9497c..a00ca97e85 100644
--- a/zjit/src/hir/tests.rs
+++ b/zjit/src/hir/tests.rs
@@ -3425,3 +3425,821 @@ pub mod hir_build_tests {
");
}
}
+
+ /// Test successor and predecessor set computations.
+ #[cfg(test)]
+ mod control_flow_info_tests {
+ use super::*;
+
+ fn edge(target: BlockId) -> BranchEdge {
+ BranchEdge { target, args: vec![] }
+ }
+
+ #[test]
+ fn test_linked_list() {
+ let mut function = Function::new(std::ptr::null());
+
+ let bb0 = function.entry_block;
+ let bb1 = function.new_block(0);
+ let bb2 = function.new_block(0);
+ let bb3 = function.new_block(0);
+
+ function.push_insn(bb0, Insn::Jump(edge(bb1)));
+ function.push_insn(bb1, Insn::Jump(edge(bb2)));
+ function.push_insn(bb2, Insn::Jump(edge(bb3)));
+
+ let retval = function.push_insn(bb3, Insn::Const { val: Const::CBool(true) });
+ function.push_insn(bb3, Insn::Return { val: retval });
+
+ let cfi = ControlFlowInfo::new(&function);
+
+ assert!(cfi.is_preceded_by(bb1, bb2));
+ assert!(cfi.is_succeeded_by(bb2, bb1));
+ assert!(cfi.predecessors(bb3).eq([bb2]));
+ }
+
+ #[test]
+ fn test_diamond() {
+ let mut function = Function::new(std::ptr::null());
+
+ let bb0 = function.entry_block;
+ let bb1 = function.new_block(0);
+ let bb2 = function.new_block(0);
+ let bb3 = function.new_block(0);
+
+ let v1 = function.push_insn(bb0, Insn::Const { val: Const::Value(Qfalse) });
+ let _ = function.push_insn(bb0, Insn::IfTrue { val: v1, target: edge(bb2)});
+ function.push_insn(bb0, Insn::Jump(edge(bb1)));
+ function.push_insn(bb1, Insn::Jump(edge(bb3)));
+ function.push_insn(bb2, Insn::Jump(edge(bb3)));
+
+ let retval = function.push_insn(bb3, Insn::Const { val: Const::CBool(true) });
+ function.push_insn(bb3, Insn::Return { val: retval });
+
+ let cfi = ControlFlowInfo::new(&function);
+
+ assert!(cfi.is_preceded_by(bb2, bb3));
+ assert!(cfi.is_preceded_by(bb1, bb3));
+ assert!(!cfi.is_preceded_by(bb0, bb3));
+ assert!(cfi.is_succeeded_by(bb1, bb0));
+ assert!(cfi.is_succeeded_by(bb3, bb1));
+ }
+ }
+
+ /// Test dominator set computations.
+ #[cfg(test)]
+ mod dom_tests {
+ use super::*;
+ use insta::assert_snapshot;
+
+ fn edge(target: BlockId) -> BranchEdge {
+ BranchEdge { target, args: vec![] }
+ }
+
+ fn assert_dominators_contains_self(function: &Function, dominators: &Dominators) {
+ for (i, _) in function.blocks.iter().enumerate() {
+ // Ensure that each dominating set contains the block itself.
+ assert!(dominators.is_dominated_by(BlockId(i), BlockId(i)));
+ }
+ }
+
+ #[test]
+ fn test_linked_list() {
+ let mut function = Function::new(std::ptr::null());
+
+ let bb0 = function.entry_block;
+ let bb1 = function.new_block(0);
+ let bb2 = function.new_block(0);
+ let bb3 = function.new_block(0);
+
+ function.push_insn(bb0, Insn::Jump(edge(bb1)));
+ function.push_insn(bb1, Insn::Jump(edge(bb2)));
+ function.push_insn(bb2, Insn::Jump(edge(bb3)));
+
+ let retval = function.push_insn(bb3, Insn::Const { val: Const::CBool(true) });
+ function.push_insn(bb3, Insn::Return { val: retval });
+
+ assert_snapshot!(format!("{}", FunctionPrinter::without_snapshot(&function)), @r"
+ fn <manual>:
+ bb0():
+ Jump bb1()
+ bb1():
+ Jump bb2()
+ bb2():
+ Jump bb3()
+ bb3():
+ v3:Any = Const CBool(true)
+ Return v3
+ ");
+
+ let dominators = Dominators::new(&function);
+ assert_dominators_contains_self(&function, &dominators);
+ assert!(dominators.dominators(bb0).eq([bb0].iter()));
+ assert!(dominators.dominators(bb1).eq([bb0, bb1].iter()));
+ assert!(dominators.dominators(bb2).eq([bb0, bb1, bb2].iter()));
+ assert!(dominators.dominators(bb3).eq([bb0, bb1, bb2, bb3].iter()));
+ }
+
+ #[test]
+ fn test_diamond() {
+ let mut function = Function::new(std::ptr::null());
+
+ let bb0 = function.entry_block;
+ let bb1 = function.new_block(0);
+ let bb2 = function.new_block(0);
+ let bb3 = function.new_block(0);
+
+ let val = function.push_insn(bb0, Insn::Const { val: Const::Value(Qfalse) });
+ let _ = function.push_insn(bb0, Insn::IfTrue { val, target: edge(bb1)});
+ function.push_insn(bb0, Insn::Jump(edge(bb2)));
+
+ function.push_insn(bb2, Insn::Jump(edge(bb3)));
+ function.push_insn(bb1, Insn::Jump(edge(bb3)));
+
+ let retval = function.push_insn(bb3, Insn::Const { val: Const::CBool(true) });
+ function.push_insn(bb3, Insn::Return { val: retval });
+
+ assert_snapshot!(format!("{}", FunctionPrinter::without_snapshot(&function)), @r"
+ fn <manual>:
+ bb0():
+ v0:Any = Const Value(false)
+ IfTrue v0, bb1()
+ Jump bb2()
+ bb1():
+ Jump bb3()
+ bb2():
+ Jump bb3()
+ bb3():
+ v5:Any = Const CBool(true)
+ Return v5
+ ");
+
+ let dominators = Dominators::new(&function);
+ assert_dominators_contains_self(&function, &dominators);
+ assert!(dominators.dominators(bb0).eq([bb0].iter()));
+ assert!(dominators.dominators(bb1).eq([bb0, bb1].iter()));
+ assert!(dominators.dominators(bb2).eq([bb0, bb2].iter()));
+ assert!(dominators.dominators(bb3).eq([bb0, bb3].iter()));
+ }
+
+ #[test]
+ fn test_complex_cfg() {
+ let mut function = Function::new(std::ptr::null());
+
+ let bb0 = function.entry_block;
+ let bb1 = function.new_block(0);
+ let bb2 = function.new_block(0);
+ let bb3 = function.new_block(0);
+ let bb4 = function.new_block(0);
+ let bb5 = function.new_block(0);
+ let bb6 = function.new_block(0);
+ let bb7 = function.new_block(0);
+
+ function.push_insn(bb0, Insn::Jump(edge(bb1)));
+
+ let v0 = function.push_insn(bb1, Insn::Const { val: Const::Value(Qfalse) });
+ let _ = function.push_insn(bb1, Insn::IfTrue { val: v0, target: edge(bb2)});
+ function.push_insn(bb1, Insn::Jump(edge(bb4)));
+
+ function.push_insn(bb2, Insn::Jump(edge(bb3)));
+
+ let v1 = function.push_insn(bb3, Insn::Const { val: Const::Value(Qfalse) });
+ let _ = function.push_insn(bb3, Insn::IfTrue { val: v1, target: edge(bb5)});
+ function.push_insn(bb3, Insn::Jump(edge(bb7)));
+
+ function.push_insn(bb4, Insn::Jump(edge(bb5)));
+
+ function.push_insn(bb5, Insn::Jump(edge(bb6)));
+
+ function.push_insn(bb6, Insn::Jump(edge(bb7)));
+
+ let retval = function.push_insn(bb7, Insn::Const { val: Const::CBool(true) });
+ function.push_insn(bb7, Insn::Return { val: retval });
+
+ assert_snapshot!(format!("{}", FunctionPrinter::without_snapshot(&function)), @r"
+ fn <manual>:
+ bb0():
+ Jump bb1()
+ bb1():
+ v1:Any = Const Value(false)
+ IfTrue v1, bb2()
+ Jump bb4()
+ bb2():
+ Jump bb3()
+ bb3():
+ v5:Any = Const Value(false)
+ IfTrue v5, bb5()
+ Jump bb7()
+ bb4():
+ Jump bb5()
+ bb5():
+ Jump bb6()
+ bb6():
+ Jump bb7()
+ bb7():
+ v11:Any = Const CBool(true)
+ Return v11
+ ");
+
+ let dominators = Dominators::new(&function);
+ assert_dominators_contains_self(&function, &dominators);
+ assert!(dominators.dominators(bb0).eq([bb0].iter()));
+ assert!(dominators.dominators(bb1).eq([bb0, bb1].iter()));
+ assert!(dominators.dominators(bb2).eq([bb0, bb1, bb2].iter()));
+ assert!(dominators.dominators(bb3).eq([bb0, bb1, bb2, bb3].iter()));
+ assert!(dominators.dominators(bb4).eq([bb0, bb1, bb4].iter()));
+ assert!(dominators.dominators(bb5).eq([bb0, bb1, bb5].iter()));
+ assert!(dominators.dominators(bb6).eq([bb0, bb1, bb5, bb6].iter()));
+ assert!(dominators.dominators(bb7).eq([bb0, bb1, bb7].iter()));
+ }
+
+ #[test]
+ fn test_back_edges() {
+ let mut function = Function::new(std::ptr::null());
+
+ let bb0 = function.entry_block;
+ let bb1 = function.new_block(0);
+ let bb2 = function.new_block(0);
+ let bb3 = function.new_block(0);
+ let bb4 = function.new_block(0);
+ let bb5 = function.new_block(0);
+
+ let v0 = function.push_insn(bb0, Insn::Const { val: Const::Value(Qfalse) });
+ let _ = function.push_insn(bb0, Insn::IfTrue { val: v0, target: edge(bb1)});
+ function.push_insn(bb0, Insn::Jump(edge(bb4)));
+
+ let v1 = function.push_insn(bb1, Insn::Const { val: Const::Value(Qfalse) });
+ let _ = function.push_insn(bb1, Insn::IfTrue { val: v1, target: edge(bb2)});
+ function.push_insn(bb1, Insn::Jump(edge(bb3)));
+
+ function.push_insn(bb2, Insn::Jump(edge(bb3)));
+
+ function.push_insn(bb4, Insn::Jump(edge(bb5)));
+
+ let v2 = function.push_insn(bb5, Insn::Const { val: Const::Value(Qfalse) });
+ let _ = function.push_insn(bb5, Insn::IfTrue { val: v2, target: edge(bb3)});
+ function.push_insn(bb5, Insn::Jump(edge(bb4)));
+
+ let retval = function.push_insn(bb3, Insn::Const { val: Const::CBool(true) });
+ function.push_insn(bb3, Insn::Return { val: retval });
+
+ assert_snapshot!(format!("{}", FunctionPrinter::without_snapshot(&function)), @r"
+ fn <manual>:
+ bb0():
+ v0:Any = Const Value(false)
+ IfTrue v0, bb1()
+ Jump bb4()
+ bb1():
+ v3:Any = Const Value(false)
+ IfTrue v3, bb2()
+ Jump bb3()
+ bb2():
+ Jump bb3()
+ bb4():
+ Jump bb5()
+ bb5():
+ v8:Any = Const Value(false)
+ IfTrue v8, bb3()
+ Jump bb4()
+ bb3():
+ v11:Any = Const CBool(true)
+ Return v11
+ ");
+
+ let dominators = Dominators::new(&function);
+ assert_dominators_contains_self(&function, &dominators);
+ assert!(dominators.dominators(bb0).eq([bb0].iter()));
+ assert!(dominators.dominators(bb1).eq([bb0, bb1].iter()));
+ assert!(dominators.dominators(bb2).eq([bb0, bb1, bb2].iter()));
+ assert!(dominators.dominators(bb3).eq([bb0, bb3].iter()));
+ assert!(dominators.dominators(bb4).eq([bb0, bb4].iter()));
+ assert!(dominators.dominators(bb5).eq([bb0, bb4, bb5].iter()));
+ }
+
+ #[test]
+ fn test_multiple_entry_blocks() {
+ let mut function = Function::new(std::ptr::null());
+
+ let bb0 = function.entry_block;
+ let bb1 = function.new_block(0);
+ function.jit_entry_blocks.push(bb1);
+ let bb2 = function.new_block(0);
+
+ function.push_insn(bb0, Insn::Jump(edge(bb2)));
+
+ function.push_insn(bb1, Insn::Jump(edge(bb2)));
+
+ let retval = function.push_insn(bb2, Insn::Const { val: Const::CBool(true) });
+ function.push_insn(bb2, Insn::Return { val: retval });
+
+ assert_snapshot!(format!("{}", FunctionPrinter::without_snapshot(&function)), @r"
+ fn <manual>:
+ bb0():
+ Jump bb2()
+ bb1():
+ Jump bb2()
+ bb2():
+ v2:Any = Const CBool(true)
+ Return v2
+ ");
+
+ let dominators = Dominators::new(&function);
+ assert_dominators_contains_self(&function, &dominators);
+
+ assert!(dominators.dominators(bb1).eq([bb1].iter()));
+ assert!(dominators.dominators(bb2).eq([bb2].iter()));
+
+ assert!(!dominators.is_dominated_by(bb1, bb2));
+ }
+ }
+
+ /// Test loop information computation.
+#[cfg(test)]
+mod loop_info_tests {
+ use super::*;
+ use insta::assert_snapshot;
+
+ fn edge(target: BlockId) -> BranchEdge {
+ BranchEdge { target, args: vec![] }
+ }
+
+ #[test]
+ fn test_loop_depth() {
+ // ┌─────┐
+ // │ bb0 │
+ // └──┬──┘
+ // │
+ // ┌──▼──┐ ┌─────┐
+ // │ bb2 ◄──────┼ bb1 ◄─┐
+ // └──┬──┘ └─────┘ │
+ // └─────────────────┘
+ let mut function = Function::new(std::ptr::null());
+
+ let bb0 = function.entry_block;
+ let bb1 = function.new_block(0);
+ let bb2 = function.new_block(0);
+
+ function.push_insn(bb0, Insn::Jump(edge(bb2)));
+
+ let val = function.push_insn(bb0, Insn::Const { val: Const::Value(Qfalse) });
+ let _ = function.push_insn(bb2, Insn::IfTrue { val, target: edge(bb1)});
+ let retval = function.push_insn(bb2, Insn::Const { val: Const::CBool(true) });
+ let _ = function.push_insn(bb2, Insn::Return { val: retval });
+
+ function.push_insn(bb1, Insn::Jump(edge(bb2)));
+
+ let cfi = ControlFlowInfo::new(&function);
+ let dominators = Dominators::new(&function);
+ let loop_info = LoopInfo::new(&cfi, &dominators);
+
+ assert_snapshot!(format!("{}", FunctionPrinter::without_snapshot(&function)), @r"
+ fn <manual>:
+ bb0():
+ Jump bb2()
+ v1:Any = Const Value(false)
+ bb2():
+ IfTrue v1, bb1()
+ v3:Any = Const CBool(true)
+ Return v3
+ bb1():
+ Jump bb2()
+ ");
+
+ assert!(loop_info.is_loop_header(bb2));
+ assert!(loop_info.is_back_edge_source(bb1));
+ assert_eq!(loop_info.loop_depth(bb1), 1);
+ }
+
+ #[test]
+ fn test_nested_loops() {
+ // ┌─────┐
+ // │ bb0 ◄─────┐
+ // └──┬──┘ │
+ // │ │
+ // ┌──▼──┐ │
+ // │ bb1 ◄───┐ │
+ // └──┬──┘ │ │
+ // │ │ │
+ // ┌──▼──┐ │ │
+ // │ bb2 ┼───┘ │
+ // └──┬──┘ │
+ // │ │
+ // ┌──▼──┐ │
+ // │ bb3 ┼─────┘
+ // └──┬──┘
+ // │
+ // ┌──▼──┐
+ // │ bb4 │
+ // └─────┘
+ let mut function = Function::new(std::ptr::null());
+
+ let bb0 = function.entry_block;
+ let bb1 = function.new_block(0);
+ let bb2 = function.new_block(0);
+ let bb3 = function.new_block(0);
+ let bb4 = function.new_block(0);
+
+ function.push_insn(bb0, Insn::Jump(edge(bb1)));
+
+ function.push_insn(bb1, Insn::Jump(edge(bb2)));
+
+ let cond = function.push_insn(bb2, Insn::Const { val: Const::Value(Qfalse) });
+ let _ = function.push_insn(bb2, Insn::IfTrue { val: cond, target: edge(bb1) });
+ function.push_insn(bb2, Insn::Jump(edge(bb3)));
+
+ let cond = function.push_insn(bb3, Insn::Const { val: Const::Value(Qtrue) });
+ let _ = function.push_insn(bb3, Insn::IfTrue { val: cond, target: edge(bb0) });
+ function.push_insn(bb3, Insn::Jump(edge(bb4)));
+
+ let retval = function.push_insn(bb4, Insn::Const { val: Const::CBool(true) });
+ let _ = function.push_insn(bb4, Insn::Return { val: retval });
+
+ let cfi = ControlFlowInfo::new(&function);
+ let dominators = Dominators::new(&function);
+ let loop_info = LoopInfo::new(&cfi, &dominators);
+
+ assert_snapshot!(format!("{}", FunctionPrinter::without_snapshot(&function)), @r"
+ fn <manual>:
+ bb0():
+ Jump bb1()
+ bb1():
+ Jump bb2()
+ bb2():
+ v2:Any = Const Value(false)
+ IfTrue v2, bb1()
+ Jump bb3()
+ bb3():
+ v5:Any = Const Value(true)
+ IfTrue v5, bb0()
+ Jump bb4()
+ bb4():
+ v8:Any = Const CBool(true)
+ Return v8
+ ");
+
+ assert!(loop_info.is_loop_header(bb0));
+ assert!(loop_info.is_loop_header(bb1));
+
+ assert_eq!(loop_info.loop_depth(bb0), 1);
+ assert_eq!(loop_info.loop_depth(bb1), 2);
+ assert_eq!(loop_info.loop_depth(bb2), 2);
+ assert_eq!(loop_info.loop_depth(bb3), 1);
+ assert_eq!(loop_info.loop_depth(bb4), 0);
+
+ assert!(loop_info.is_back_edge_source(bb2));
+ assert!(loop_info.is_back_edge_source(bb3));
+ }
+
+ #[test]
+ fn test_complex_loops() {
+ // ┌─────┐
+ // ┌──────► bb0 │
+ // │ └──┬──┘
+ // │ ┌────┴────┐
+ // │ ┌──▼──┐ ┌──▼──┐
+ // │ │ bb1 ◄─┐ │ bb3 ◄─┐
+ // │ └──┬──┘ │ └──┬──┘ │
+ // │ │ │ │ │
+ // │ ┌──▼──┐ │ ┌──▼──┐ │
+ // │ │ bb2 ┼─┘ │ bb4 ┼─┘
+ // │ └──┬──┘ └──┬──┘
+ // │ └────┬────┘
+ // │ ┌──▼──┐
+ // └──────┼ bb5 │
+ // └──┬──┘
+ // │
+ // ┌──▼──┐
+ // │ bb6 │
+ // └─────┘
+ let mut function = Function::new(std::ptr::null());
+
+ let bb0 = function.entry_block;
+ let bb1 = function.new_block(0);
+ let bb2 = function.new_block(0);
+ let bb3 = function.new_block(0);
+ let bb4 = function.new_block(0);
+ let bb5 = function.new_block(0);
+ let bb6 = function.new_block(0);
+
+ let cond = function.push_insn(bb0, Insn::Const { val: Const::Value(Qfalse) });
+ let _ = function.push_insn(bb0, Insn::IfTrue { val: cond, target: edge(bb1) });
+ function.push_insn(bb0, Insn::Jump(edge(bb3)));
+
+ function.push_insn(bb1, Insn::Jump(edge(bb2)));
+
+ let _ = function.push_insn(bb2, Insn::IfTrue { val: cond, target: edge(bb1) });
+ function.push_insn(bb2, Insn::Jump(edge(bb5)));
+
+ function.push_insn(bb3, Insn::Jump(edge(bb4)));
+
+ let _ = function.push_insn(bb4, Insn::IfTrue { val: cond, target: edge(bb3) });
+ function.push_insn(bb4, Insn::Jump(edge(bb5)));
+
+ let _ = function.push_insn(bb5, Insn::IfTrue { val: cond, target: edge(bb0) });
+ function.push_insn(bb5, Insn::Jump(edge(bb6)));
+
+ let retval = function.push_insn(bb6, Insn::Const { val: Const::CBool(true) });
+ let _ = function.push_insn(bb6, Insn::Return { val: retval });
+
+ let cfi = ControlFlowInfo::new(&function);
+ let dominators = Dominators::new(&function);
+ let loop_info = LoopInfo::new(&cfi, &dominators);
+
+ assert_snapshot!(format!("{}", FunctionPrinter::without_snapshot(&function)), @r"
+ fn <manual>:
+ bb0():
+ v0:Any = Const Value(false)
+ IfTrue v0, bb1()
+ Jump bb3()
+ bb1():
+ Jump bb2()
+ bb2():
+ IfTrue v0, bb1()
+ Jump bb5()
+ bb3():
+ Jump bb4()
+ bb4():
+ IfTrue v0, bb3()
+ Jump bb5()
+ bb5():
+ IfTrue v0, bb0()
+ Jump bb6()
+ bb6():
+ v11:Any = Const CBool(true)
+ Return v11
+ ");
+
+ assert!(loop_info.is_loop_header(bb0));
+ assert!(loop_info.is_loop_header(bb1));
+ assert!(!loop_info.is_loop_header(bb2));
+ assert!(loop_info.is_loop_header(bb3));
+ assert!(!loop_info.is_loop_header(bb5));
+ assert!(!loop_info.is_loop_header(bb4));
+ assert!(!loop_info.is_loop_header(bb6));
+
+ assert_eq!(loop_info.loop_depth(bb0), 1);
+ assert_eq!(loop_info.loop_depth(bb1), 2);
+ assert_eq!(loop_info.loop_depth(bb2), 2);
+ assert_eq!(loop_info.loop_depth(bb3), 2);
+ assert_eq!(loop_info.loop_depth(bb4), 2);
+ assert_eq!(loop_info.loop_depth(bb5), 1);
+ assert_eq!(loop_info.loop_depth(bb6), 0);
+
+ assert!(loop_info.is_back_edge_source(bb2));
+ assert!(loop_info.is_back_edge_source(bb4));
+ assert!(loop_info.is_back_edge_source(bb5));
+ }
+
+ #[test]
+ fn linked_list_non_loop() {
+ // ┌─────┐
+ // │ bb0 │
+ // └──┬──┘
+ // │
+ // ┌──▼──┐
+ // │ bb1 │
+ // └──┬──┘
+ // │
+ // ┌──▼──┐
+ // │ bb2 │
+ // └─────┘
+ let mut function = Function::new(std::ptr::null());
+
+ let bb0 = function.entry_block;
+ let bb1 = function.new_block(0);
+ let bb2 = function.new_block(0);
+
+ let _ = function.push_insn(bb0, Insn::Jump(edge(bb1)));
+ let _ = function.push_insn(bb1, Insn::Jump(edge(bb2)));
+
+ let retval = function.push_insn(bb2, Insn::Const { val: Const::CBool(true) });
+ let _ = function.push_insn(bb2, Insn::Return { val: retval });
+
+ let cfi = ControlFlowInfo::new(&function);
+ let dominators = Dominators::new(&function);
+ let loop_info = LoopInfo::new(&cfi, &dominators);
+
+ assert_snapshot!(format!("{}", FunctionPrinter::without_snapshot(&function)), @r"
+ fn <manual>:
+ bb0():
+ Jump bb1()
+ bb1():
+ Jump bb2()
+ bb2():
+ v2:Any = Const CBool(true)
+ Return v2
+ ");
+
+ assert!(!loop_info.is_loop_header(bb0));
+ assert!(!loop_info.is_loop_header(bb1));
+ assert!(!loop_info.is_loop_header(bb2));
+
+ assert!(!loop_info.is_back_edge_source(bb0));
+ assert!(!loop_info.is_back_edge_source(bb1));
+ assert!(!loop_info.is_back_edge_source(bb2));
+
+ assert_eq!(loop_info.loop_depth(bb0), 0);
+ assert_eq!(loop_info.loop_depth(bb1), 0);
+ assert_eq!(loop_info.loop_depth(bb2), 0);
+ }
+
+ #[test]
+ fn triple_nested_loop() {
+ // ┌─────┐
+ // │ bb0 ◄──┐
+ // └──┬──┘ │
+ // │ │
+ // ┌──▼──┐ │
+ // │ bb1 ◄─┐│
+ // └──┬──┘ ││
+ // │ ││
+ // ┌──▼──┐ ││
+ // │ bb2 ◄┐││
+ // └──┬──┘│││
+ // │ │││
+ // ┌──▼──┐│││
+ // │ bb3 ┼┘││
+ // └──┬──┘ ││
+ // │ ││
+ // ┌──▼──┐ ││
+ // │ bb4 ┼─┘│
+ // └──┬──┘ │
+ // │ │
+ // ┌──▼──┐ │
+ // │ bb5 ┼──┘
+ // └─────┘
+ let mut function = Function::new(std::ptr::null());
+
+ let bb0 = function.entry_block;
+ let bb1 = function.new_block(0);
+ let bb2 = function.new_block(0);
+ let bb3 = function.new_block(0);
+ let bb4 = function.new_block(0);
+ let bb5 = function.new_block(0);
+
+ let cond = function.push_insn(bb0, Insn::Const { val: Const::Value(Qfalse) });
+ let _ = function.push_insn(bb0, Insn::Jump(edge(bb1)));
+ let _ = function.push_insn(bb1, Insn::Jump(edge(bb2)));
+ let _ = function.push_insn(bb2, Insn::Jump(edge(bb3)));
+ let _ = function.push_insn(bb3, Insn::Jump(edge(bb4)));
+ let _ = function.push_insn(bb3, Insn::IfTrue {val: cond, target: edge(bb2)});
+ let _ = function.push_insn(bb4, Insn::Jump(edge(bb5)));
+ let _ = function.push_insn(bb4, Insn::IfTrue {val: cond, target: edge(bb1)});
+ let _ = function.push_insn(bb5, Insn::IfTrue {val: cond, target: edge(bb0)});
+
+ assert_snapshot!(format!("{}", FunctionPrinter::without_snapshot(&function)), @r"
+ fn <manual>:
+ bb0():
+ v0:Any = Const Value(false)
+ Jump bb1()
+ bb1():
+ Jump bb2()
+ bb2():
+ Jump bb3()
+ bb3():
+ Jump bb4()
+ IfTrue v0, bb2()
+ bb4():
+ Jump bb5()
+ IfTrue v0, bb1()
+ bb5():
+ IfTrue v0, bb0()
+ ");
+
+ let cfi = ControlFlowInfo::new(&function);
+ let dominators = Dominators::new(&function);
+ let loop_info = LoopInfo::new(&cfi, &dominators);
+
+ assert!(!loop_info.is_back_edge_source(bb0));
+ assert!(!loop_info.is_back_edge_source(bb1));
+ assert!(!loop_info.is_back_edge_source(bb2));
+ assert!(loop_info.is_back_edge_source(bb3));
+ assert!(loop_info.is_back_edge_source(bb4));
+ assert!(loop_info.is_back_edge_source(bb5));
+
+ assert_eq!(loop_info.loop_depth(bb0), 1);
+ assert_eq!(loop_info.loop_depth(bb1), 2);
+ assert_eq!(loop_info.loop_depth(bb2), 3);
+ assert_eq!(loop_info.loop_depth(bb3), 3);
+ assert_eq!(loop_info.loop_depth(bb4), 2);
+ assert_eq!(loop_info.loop_depth(bb5), 1);
+
+ assert!(loop_info.is_loop_header(bb0));
+ assert!(loop_info.is_loop_header(bb1));
+ assert!(loop_info.is_loop_header(bb2));
+ assert!(!loop_info.is_loop_header(bb3));
+ assert!(!loop_info.is_loop_header(bb4));
+ assert!(!loop_info.is_loop_header(bb5));
+ }
+ }
+
+/// Test dumping to iongraph format.
+#[cfg(test)]
+mod iongraph_tests {
+ use super::*;
+ use insta::assert_snapshot;
+
+ fn edge(target: BlockId) -> BranchEdge {
+ BranchEdge { target, args: vec![] }
+ }
+
+ #[test]
+ fn test_simple_function() {
+ let mut function = Function::new(std::ptr::null());
+ let bb0 = function.entry_block;
+
+ let retval = function.push_insn(bb0, Insn::Const { val: Const::CBool(true) });
+ function.push_insn(bb0, Insn::Return { val: retval });
+
+ let json = function.to_iongraph_pass("simple");
+ assert_snapshot!(json.to_string(), @r#"{"name":"simple", "mir":{"blocks":[{"ptr":4096, "id":0, "loopDepth":0, "attributes":[], "predecessors":[], "successors":[], "instructions":[{"ptr":4096, "id":0, "opcode":"Const CBool(true)", "attributes":[], "inputs":[], "uses":[], "memInputs":[], "type":"Any"}, {"ptr":4097, "id":1, "opcode":"Return v0", "attributes":[], "inputs":[0], "uses":[], "memInputs":[], "type":""}]}]}, "lir":{"blocks":[]}}"#);
+ }
+
+ #[test]
+ fn test_two_blocks() {
+ let mut function = Function::new(std::ptr::null());
+ let bb0 = function.entry_block;
+ let bb1 = function.new_block(0);
+
+ function.push_insn(bb0, Insn::Jump(edge(bb1)));
+
+ let retval = function.push_insn(bb1, Insn::Const { val: Const::CBool(false) });
+ function.push_insn(bb1, Insn::Return { val: retval });
+
+ let json = function.to_iongraph_pass("two_blocks");
+ assert_snapshot!(json.to_string(), @r#"{"name":"two_blocks", "mir":{"blocks":[{"ptr":4096, "id":0, "loopDepth":0, "attributes":[], "predecessors":[], "successors":[1], "instructions":[{"ptr":4096, "id":0, "opcode":"Jump bb1()", "attributes":[], "inputs":[], "uses":[], "memInputs":[], "type":""}]}, {"ptr":4097, "id":1, "loopDepth":0, "attributes":[], "predecessors":[0], "successors":[], "instructions":[{"ptr":4097, "id":1, "opcode":"Const CBool(false)", "attributes":[], "inputs":[], "uses":[], "memInputs":[], "type":"Any"}, {"ptr":4098, "id":2, "opcode":"Return v1", "attributes":[], "inputs":[1], "uses":[], "memInputs":[], "type":""}]}]}, "lir":{"blocks":[]}}"#);
+ }
+
+ #[test]
+ fn test_multiple_instructions() {
+ let mut function = Function::new(std::ptr::null());
+ let bb0 = function.entry_block;
+
+ let val1 = function.push_insn(bb0, Insn::Const { val: Const::CBool(true) });
+ function.push_insn(bb0, Insn::Return { val: val1 });
+
+ let json = function.to_iongraph_pass("multiple_instructions");
+ assert_snapshot!(json.to_string(), @r#"{"name":"multiple_instructions", "mir":{"blocks":[{"ptr":4096, "id":0, "loopDepth":0, "attributes":[], "predecessors":[], "successors":[], "instructions":[{"ptr":4096, "id":0, "opcode":"Const CBool(true)", "attributes":[], "inputs":[], "uses":[], "memInputs":[], "type":"Any"}, {"ptr":4097, "id":1, "opcode":"Return v0", "attributes":[], "inputs":[0], "uses":[], "memInputs":[], "type":""}]}]}, "lir":{"blocks":[]}}"#);
+ }
+
+ #[test]
+ fn test_conditional_branch() {
+ let mut function = Function::new(std::ptr::null());
+ let bb0 = function.entry_block;
+ let bb1 = function.new_block(0);
+
+ let cond = function.push_insn(bb0, Insn::Const { val: Const::CBool(true) });
+ function.push_insn(bb0, Insn::IfTrue { val: cond, target: edge(bb1) });
+
+ let retval1 = function.push_insn(bb0, Insn::Const { val: Const::CBool(false) });
+ function.push_insn(bb0, Insn::Return { val: retval1 });
+
+ let retval2 = function.push_insn(bb1, Insn::Const { val: Const::CBool(true) });
+ function.push_insn(bb1, Insn::Return { val: retval2 });
+
+ let json = function.to_iongraph_pass("conditional_branch");
+ assert_snapshot!(json.to_string(), @r#"{"name":"conditional_branch", "mir":{"blocks":[{"ptr":4096, "id":0, "loopDepth":0, "attributes":[], "predecessors":[], "successors":[1], "instructions":[{"ptr":4096, "id":0, "opcode":"Const CBool(true)", "attributes":[], "inputs":[], "uses":[], "memInputs":[], "type":"Any"}, {"ptr":4097, "id":1, "opcode":"IfTrue v0, bb1()", "attributes":[], "inputs":[0], "uses":[], "memInputs":[], "type":""}, {"ptr":4098, "id":2, "opcode":"Const CBool(false)", "attributes":[], "inputs":[], "uses":[], "memInputs":[], "type":"Any"}, {"ptr":4099, "id":3, "opcode":"Return v2", "attributes":[], "inputs":[2], "uses":[], "memInputs":[], "type":""}]}, {"ptr":4097, "id":1, "loopDepth":0, "attributes":[], "predecessors":[0], "successors":[], "instructions":[{"ptr":4100, "id":4, "opcode":"Const CBool(true)", "attributes":[], "inputs":[], "uses":[], "memInputs":[], "type":"Any"}, {"ptr":4101, "id":5, "opcode":"Return v4", "attributes":[], "inputs":[4], "uses":[], "memInputs":[], "type":""}]}]}, "lir":{"blocks":[]}}"#);
+ }
+
+ #[test]
+ fn test_loop_structure() {
+ let mut function = Function::new(std::ptr::null());
+
+ let bb0 = function.entry_block;
+ let bb1 = function.new_block(0);
+ let bb2 = function.new_block(0);
+
+ function.push_insn(bb0, Insn::Jump(edge(bb2)));
+
+ let val = function.push_insn(bb0, Insn::Const { val: Const::Value(Qfalse) });
+ let _ = function.push_insn(bb2, Insn::IfTrue { val, target: edge(bb1)});
+ let retval = function.push_insn(bb2, Insn::Const { val: Const::CBool(true) });
+ let _ = function.push_insn(bb2, Insn::Return { val: retval });
+
+ function.push_insn(bb1, Insn::Jump(edge(bb2)));
+
+ let json = function.to_iongraph_pass("loop_structure");
+ assert_snapshot!(json.to_string(), @r#"{"name":"loop_structure", "mir":{"blocks":[{"ptr":4096, "id":0, "loopDepth":0, "attributes":[], "predecessors":[], "successors":[2], "instructions":[{"ptr":4096, "id":0, "opcode":"Jump bb2()", "attributes":[], "inputs":[], "uses":[], "memInputs":[], "type":""}, {"ptr":4097, "id":1, "opcode":"Const Value(false)", "attributes":[], "inputs":[], "uses":[], "memInputs":[], "type":"Any"}]}, {"ptr":4098, "id":2, "loopDepth":1, "attributes":["loopheader"], "predecessors":[0, 1], "successors":[1], "instructions":[{"ptr":4098, "id":2, "opcode":"IfTrue v1, bb1()", "attributes":[], "inputs":[1], "uses":[], "memInputs":[], "type":""}, {"ptr":4099, "id":3, "opcode":"Const CBool(true)", "attributes":[], "inputs":[], "uses":[], "memInputs":[], "type":"Any"}, {"ptr":4100, "id":4, "opcode":"Return v3", "attributes":[], "inputs":[3], "uses":[], "memInputs":[], "type":""}]}, {"ptr":4097, "id":1, "loopDepth":1, "attributes":["backedge"], "predecessors":[2], "successors":[2], "instructions":[{"ptr":4101, "id":5, "opcode":"Jump bb2()", "attributes":[], "inputs":[], "uses":[], "memInputs":[], "type":""}]}]}, "lir":{"blocks":[]}}"#);
+ }
+
+ #[test]
+ fn test_multiple_successors() {
+ let mut function = Function::new(std::ptr::null());
+ let bb0 = function.entry_block;
+ let bb1 = function.new_block(0);
+ let bb2 = function.new_block(0);
+
+ let cond = function.push_insn(bb0, Insn::Const { val: Const::CBool(true) });
+ function.push_insn(bb0, Insn::IfTrue { val: cond, target: edge(bb1) });
+ function.push_insn(bb0, Insn::Jump(edge(bb2)));
+
+ let retval1 = function.push_insn(bb1, Insn::Const { val: Const::CBool(true) });
+ function.push_insn(bb1, Insn::Return { val: retval1 });
+
+ let retval2 = function.push_insn(bb2, Insn::Const { val: Const::CBool(false) });
+ function.push_insn(bb2, Insn::Return { val: retval2 });
+
+ let json = function.to_iongraph_pass("multiple_successors");
+ assert_snapshot!(json.to_string(), @r#"{"name":"multiple_successors", "mir":{"blocks":[{"ptr":4096, "id":0, "loopDepth":0, "attributes":[], "predecessors":[], "successors":[1, 2], "instructions":[{"ptr":4096, "id":0, "opcode":"Const CBool(true)", "attributes":[], "inputs":[], "uses":[], "memInputs":[], "type":"Any"}, {"ptr":4097, "id":1, "opcode":"IfTrue v0, bb1()", "attributes":[], "inputs":[0], "uses":[], "memInputs":[], "type":""}, {"ptr":4098, "id":2, "opcode":"Jump bb2()", "attributes":[], "inputs":[], "uses":[], "memInputs":[], "type":""}]}, {"ptr":4097, "id":1, "loopDepth":0, "attributes":[], "predecessors":[0], "successors":[], "instructions":[{"ptr":4099, "id":3, "opcode":"Const CBool(true)", "attributes":[], "inputs":[], "uses":[], "memInputs":[], "type":"Any"}, {"ptr":4100, "id":4, "opcode":"Return v3", "attributes":[], "inputs":[3], "uses":[], "memInputs":[], "type":""}]}, {"ptr":4098, "id":2, "loopDepth":0, "attributes":[], "predecessors":[0], "successors":[], "instructions":[{"ptr":4101, "id":5, "opcode":"Const CBool(false)", "attributes":[], "inputs":[], "uses":[], "memInputs":[], "type":"Any"}, {"ptr":4102, "id":6, "opcode":"Return v5", "attributes":[], "inputs":[5], "uses":[], "memInputs":[], "type":""}]}]}, "lir":{"blocks":[]}}"#);
+ }
+ }
diff --git a/zjit/src/options.rs b/zjit/src/options.rs
index c165035eaa..b7e2c71cef 100644
--- a/zjit/src/options.rs
+++ b/zjit/src/options.rs
@@ -70,6 +70,9 @@ pub struct Options {
/// Dump High-level IR to the given file in Graphviz format after optimization
pub dump_hir_graphviz: Option<std::path::PathBuf>,
+ /// Dump High-level IR in Iongraph JSON format after optimization to /tmp/zjit-iongraph-{$PID}
+ pub dump_hir_iongraph: bool,
+
/// Dump low-level IR
pub dump_lir: Option<HashSet<DumpLIR>>,
@@ -106,6 +109,7 @@ impl Default for Options {
dump_hir_init: None,
dump_hir_opt: None,
dump_hir_graphviz: None,
+ dump_hir_iongraph: false,
dump_lir: None,
dump_disasm: false,
trace_side_exits: None,
@@ -353,6 +357,8 @@ fn parse_option(str_ptr: *const std::os::raw::c_char) -> Option<()> {
options.dump_hir_graphviz = Some(opt_val);
}
+ ("dump-hir-iongraph", "") => options.dump_hir_iongraph = true,
+
("dump-lir", "") => options.dump_lir = Some(HashSet::from([DumpLIR::init])),
("dump-lir", filters) => {
let mut dump_lirs = HashSet::new();
generated by cgit v1.2.3 (git 2.25.1) at 2026-01-20 07:22:01 +0000