use std::collections::BTreeSet;
use std::fmt::Write as _;
use crate::debug::{DebugColorMode, DebugDetail, DebugFilters, colorize_debug_text, format_display_set};
use crate::transformer::{LowInstr, LoweredChunk, LoweredProto};
use super::common::{
BlockRef, CfgGraph, DataflowFacts, DefId, EffectTag, GraphFacts, OpenDefId, RegValueMap,
SsaValue, ValueMapRef, ValueSetRef,
};
#[derive(Debug, Clone, Copy)]
struct ProtoEntry<'a, T> {
id: usize,
depth: usize,
facts: &'a T,
}
#[derive(Debug, Clone, Copy)]
struct DataflowProtoEntry<'a> {
id: usize,
depth: usize,
proto: &'a LoweredProto,
cfg: &'a CfgGraph,
facts: &'a DataflowFacts,
}
pub fn dump_cfg(
graph: &CfgGraph,
detail: DebugDetail,
filters: &DebugFilters,
color: DebugColorMode,
) -> String {
let mut output = String::new();
let entries = collect_proto_entries(graph);
let visible = visible_ids(entries.iter().map(|e| e.id), filters);
let _ = writeln!(output, "===== Dump CFG =====");
let _ = writeln!(output, "cfg detail={} protos={}", detail, entries.len());
if let Some(proto_id) = filters.proto {
let _ = writeln!(output, "filters proto=proto#{proto_id}");
}
let _ = writeln!(output);
for entry in &entries {
if !visible.contains(&entry.id) {
continue;
}
let cfg = &entry.facts.cfg;
let indent = " ".repeat(entry.depth);
let _ = writeln!(
output,
"{indent}proto#{} blocks={} edges={} entry=#{} exit=#{} reachable={}",
entry.id,
cfg.block_order.len(),
cfg.edges.len(),
cfg.entry_block.index(),
cfg.exit_block.index(),
format_display_set(&cfg.reachable_blocks),
);
if matches!(detail, DebugDetail::Summary) {
continue;
}
let _ = writeln!(output, "{indent} block listing");
for block_ref in &cfg.block_order {
let block = cfg.blocks[block_ref.index()];
let _ = writeln!(
output,
"{indent} block #{} instrs=[@{}..@{}) preds={} succs={}",
block_ref.index(),
block.instrs.start.index(),
block.instrs.end(),
format_edge_refs(&cfg.preds[block_ref.index()]),
format_edge_refs(&cfg.succs[block_ref.index()]),
);
}
let _ = writeln!(
output,
"{indent} block #{} <synthetic-exit> preds={} succs={}",
cfg.exit_block.index(),
format_edge_refs(&cfg.preds[cfg.exit_block.index()]),
format_edge_refs(&cfg.succs[cfg.exit_block.index()]),
);
let _ = writeln!(output, "{indent} edge listing");
for (edge_index, edge) in cfg.edges.iter().enumerate() {
let _ = writeln!(
output,
"{indent} edge #{} #{} -> #{} kind={}",
edge_index,
edge.from.index(),
edge.to.index(),
format_edge_kind(edge.kind),
);
}
}
colorize_debug_text(&output, color)
}
pub fn dump_graph_facts(
graph_facts: &GraphFacts,
detail: DebugDetail,
filters: &DebugFilters,
color: DebugColorMode,
) -> String {
let mut output = String::new();
let entries = collect_proto_entries(graph_facts);
let visible = visible_ids(entries.iter().map(|e| e.id), filters);
let _ = writeln!(output, "===== Dump GraphFacts =====");
let _ = writeln!(
output,
"graph-facts detail={} protos={}",
detail,
entries.len()
);
if let Some(proto_id) = filters.proto {
let _ = writeln!(output, "filters proto=proto#{proto_id}");
}
let _ = writeln!(output);
for entry in &entries {
if !visible.contains(&entry.id) {
continue;
}
let facts = entry.facts;
let indent = " ".repeat(entry.depth);
let _ = writeln!(
output,
"{indent}proto#{} rpo={} backedges={} loop_headers={}",
entry.id,
format_display_set(&facts.rpo),
format_edge_refs(&facts.backedges),
format_display_set(&facts.loop_headers),
);
if matches!(detail, DebugDetail::Summary) {
continue;
}
let _ = writeln!(output, "{indent} dominator tree");
for (block_index, parent) in facts.dominator_tree.parent.iter().enumerate() {
let _ = writeln!(
output,
"{indent} block #{} parent={}",
block_index,
parent
.map(|block| format!("#{}", block.index()))
.unwrap_or_else(|| "-".to_owned()),
);
}
let _ = writeln!(output, "{indent} post-dominator tree");
for (block_index, parent) in facts.post_dominator_tree.parent.iter().enumerate() {
let _ = writeln!(
output,
"{indent} block #{} parent={}",
block_index,
parent
.map(|block| format!("#{}", block.index()))
.unwrap_or_else(|| "-".to_owned()),
);
}
let _ = writeln!(output, "{indent} dominance frontier");
for block_index in 0..facts.dominance_frontier.len() {
let block = BlockRef(block_index);
if facts.dominance_frontier_is_empty(block) && matches!(detail, DebugDetail::Normal) {
continue;
}
let _ = writeln!(
output,
"{indent} block #{} frontier={}",
block_index,
format_display_set(facts.dominance_frontier_blocks(block)),
);
}
let _ = writeln!(output, "{indent} natural loops");
if facts.natural_loops.is_empty() {
let _ = writeln!(output, "{indent} <none>");
} else {
for natural_loop in &facts.natural_loops {
let _ = writeln!(
output,
"{indent} header=#{} backedge=#{} blocks={}",
natural_loop.header.index(),
natural_loop.backedge.index(),
format_display_set(&natural_loop.blocks),
);
}
}
}
colorize_debug_text(&output, color)
}
pub fn dump_dataflow(
chunk: &LoweredChunk,
cfg: &CfgGraph,
dataflow: &DataflowFacts,
detail: DebugDetail,
filters: &DebugFilters,
color: DebugColorMode,
) -> String {
let mut output = String::new();
let entries = collect_dataflow_entries(&chunk.main, cfg, dataflow);
let visible = visible_ids(entries.iter().map(|e| e.id), filters);
let _ = writeln!(output, "===== Dump Dataflow =====");
let _ = writeln!(
output,
"dataflow detail={} protos={}",
detail,
entries.len()
);
if let Some(proto_id) = filters.proto {
let _ = writeln!(output, "filters proto=proto#{proto_id}");
}
let _ = writeln!(output);
for entry in &entries {
if !visible.contains(&entry.id) {
continue;
}
let indent = " ".repeat(entry.depth);
let _ = writeln!(
output,
"{indent}proto#{} defs={} open_defs={} phis={}",
entry.id,
entry.facts.defs.len(),
entry.facts.open_defs.len(),
entry.facts.phi_candidates.len(),
);
if matches!(detail, DebugDetail::Summary) {
continue;
}
let _ = writeln!(output, "{indent} instr effects");
for (instr_index, instr) in entry.proto.instrs.iter().enumerate() {
let effect = &entry.facts.instr_effects[instr_index];
let summary = &entry.facts.effect_summaries[instr_index];
let block = entry.cfg.cfg.instr_to_block[instr_index];
let _ = writeln!(
output,
"{indent} @{instr_index:03} block=#{} {:<18} reads={} writes={} open-use={} open-def={} effects={}",
block.index(),
format_low_instr_head(instr),
format_display_set(&effect.fixed_uses),
format_display_set(&effect.fixed_must_defs),
effect
.open_use
.map(|r| r.to_string())
.unwrap_or_else(|| "-".to_owned()),
effect
.open_must_def
.map(|r| r.to_string())
.unwrap_or_else(|| "-".to_owned()),
format_effect_tags(&summary.tags),
);
}
let _ = writeln!(output, "{indent} liveness");
for block in &entry.cfg.cfg.block_order {
let _ = writeln!(
output,
"{indent} block #{} live_in={} live_out={} open_in={} open_out={}",
block.index(),
format_display_set(entry.facts.live_in_regs(*block)),
format_display_set(entry.facts.live_out_regs(*block)),
entry.facts.block_open_live_in(*block),
entry.facts.block_open_live_out(*block),
);
}
let _ = writeln!(output, "{indent} phi candidates");
if entry.facts.phi_candidates.is_empty() {
let _ = writeln!(output, "{indent} <none>");
} else {
for candidate in &entry.facts.phi_candidates {
let _ = writeln!(
output,
"{indent} block #{} reg={} incoming={}",
candidate.block.index(),
candidate.reg,
format_phi_incoming(&candidate.incoming),
);
}
}
if matches!(detail, DebugDetail::Verbose) {
let _ = writeln!(output, "{indent} reaching defs");
for (instr_index, defs) in entry.facts.reaching_defs.iter().enumerate() {
let _ = writeln!(
output,
"{indent} @{instr_index:03} fixed={} open={}",
format_reaching_defs(&defs.fixed),
format_open_def_set(
entry
.facts
.open_reaching_defs_at(crate::transformer::InstrRef(instr_index)),
),
);
}
let _ = writeln!(output, "{indent} reaching values");
for instr_index in 0..entry.proto.instrs.len() {
let _ = writeln!(
output,
"{indent} @{instr_index:03} fixed={}",
format_reaching_values(
entry
.facts
.reaching_values_at(crate::transformer::InstrRef(instr_index)),
),
);
}
}
}
colorize_debug_text(&output, color)
}
fn collect_proto_entries<'a, T>(root: &'a T) -> Vec<ProtoEntry<'a, T>>
where
T: ProtoChildren<T>,
{
let mut entries = Vec::new();
collect_proto_entries_inner(root, 0, &mut entries);
entries
}
fn collect_proto_entries_inner<'a, T>(
node: &'a T,
depth: usize,
entries: &mut Vec<ProtoEntry<'a, T>>,
) where
T: ProtoChildren<T>,
{
let id = entries.len();
entries.push(ProtoEntry {
id,
depth,
facts: node,
});
for child in node.children() {
collect_proto_entries_inner(child, depth + 1, entries);
}
}
fn collect_dataflow_entries<'a>(
proto: &'a LoweredProto,
cfg: &'a CfgGraph,
dataflow: &'a DataflowFacts,
) -> Vec<DataflowProtoEntry<'a>> {
let mut entries = Vec::new();
collect_dataflow_entries_inner(proto, cfg, dataflow, 0, &mut entries);
entries
}
fn collect_dataflow_entries_inner<'a>(
proto: &'a LoweredProto,
cfg: &'a CfgGraph,
dataflow: &'a DataflowFacts,
depth: usize,
entries: &mut Vec<DataflowProtoEntry<'a>>,
) {
let id = entries.len();
entries.push(DataflowProtoEntry {
id,
depth,
proto,
cfg,
facts: dataflow,
});
for ((child_proto, child_cfg), child_dataflow) in proto
.children
.iter()
.zip(cfg.children.iter())
.zip(dataflow.children.iter())
{
collect_dataflow_entries_inner(child_proto, child_cfg, child_dataflow, depth + 1, entries);
}
}
fn visible_ids(entries: impl Iterator<Item = usize>, filters: &DebugFilters) -> Vec<usize> {
let all: Vec<usize> = entries.collect();
match filters.proto {
Some(id) if all.contains(&id) => vec![id],
Some(_) => Vec::new(),
None => all,
}
}
trait ProtoChildren<T> {
fn children(&self) -> &[T];
}
impl ProtoChildren<CfgGraph> for CfgGraph {
fn children(&self) -> &[CfgGraph] {
&self.children
}
}
impl ProtoChildren<GraphFacts> for GraphFacts {
fn children(&self) -> &[GraphFacts] {
&self.children
}
}
fn format_edge_refs(edge_refs: &[super::common::EdgeRef]) -> String {
if edge_refs.is_empty() {
"-".to_string()
} else {
edge_refs
.iter()
.map(|edge| edge.to_string())
.collect::<Vec<_>>()
.join(", ")
}
}
fn format_reaching_defs(defs: &RegValueMap<DefId>) -> String {
if defs.iter().next().is_none() {
"[-]".to_string()
} else {
defs.iter()
.map(|(reg, defs)| format!("{reg}<-{}", format_display_set(defs)))
.collect::<Vec<_>>()
.join(" ")
}
}
fn format_reaching_values(values: ValueMapRef<'_>) -> String {
if values.iter().next().is_none() {
"[-]".to_string()
} else {
values
.iter()
.map(|(reg, values)| format!("{reg}<-{}", format_value_set(values)))
.collect::<Vec<_>>()
.join(" ")
}
}
fn format_value_set(values: ValueSetRef<'_>) -> String {
if values.is_empty() {
"[-]".to_string()
} else {
format!(
"[{}]",
values
.iter()
.map(|value| match value {
SsaValue::Def(def) => def.to_string(),
SsaValue::Phi(phi) => phi.to_string(),
})
.collect::<Vec<_>>()
.join(", ")
)
}
}
fn format_open_def_set(defs: &BTreeSet<OpenDefId>) -> String {
if defs.is_empty() {
"[-]".to_string()
} else {
format!(
"[{}]",
defs.iter()
.map(|def| format!("open{}", def.index()))
.collect::<Vec<_>>()
.join(", ")
)
}
}
fn format_effect_tags(tags: &BTreeSet<EffectTag>) -> String {
if tags.is_empty() {
"[-]".to_string()
} else {
format!(
"[{}]",
tags.iter()
.map(|tag| format_effect_tag(*tag))
.collect::<Vec<_>>()
.join(", ")
)
}
}
fn format_phi_incoming(incoming: &[super::common::PhiIncoming]) -> String {
incoming
.iter()
.map(|incoming| {
format!(
"{}:{}",
incoming.pred,
format_display_set(&incoming.defs)
)
})
.collect::<Vec<_>>()
.join(", ")
}
fn format_low_instr_head(instr: &LowInstr) -> &'static str {
match instr {
LowInstr::Move(_instr) => "move",
LowInstr::LoadNil(_instr) => "load-nil",
LowInstr::LoadBool(_instr) => "load-bool",
LowInstr::LoadConst(_instr) => "load-const",
LowInstr::LoadInteger(_instr) => "load-int",
LowInstr::LoadNumber(_instr) => "load-num",
LowInstr::UnaryOp(_instr) => "unary-op",
LowInstr::BinaryOp(_instr) => "binary-op",
LowInstr::Concat(_instr) => "concat",
LowInstr::GetUpvalue(_instr) => "get-upvalue",
LowInstr::SetUpvalue(_instr) => "set-upvalue",
LowInstr::GetTable(_instr) => "get-table",
LowInstr::SetTable(_instr) => "set-table",
LowInstr::ErrNil(_instr) => "err-nnil",
LowInstr::NewTable(_instr) => "new-table",
LowInstr::SetList(_instr) => "set-list",
LowInstr::Call(_instr) => "call",
LowInstr::TailCall(_instr) => "tail-call",
LowInstr::VarArg(_instr) => "vararg",
LowInstr::Return(_instr) => "return",
LowInstr::Closure(_instr) => "closure",
LowInstr::Close(_instr) => "close",
LowInstr::Tbc(_instr) => "tbc",
LowInstr::NumericForInit(_instr) => "numeric-for-init",
LowInstr::NumericForLoop(_instr) => "numeric-for-loop",
LowInstr::GenericForCall(_instr) => "generic-for-call",
LowInstr::GenericForLoop(_instr) => "generic-for-loop",
LowInstr::Jump(_instr) => "jump",
LowInstr::Branch(_instr) => "branch",
}
}
fn format_effect_tag(tag: EffectTag) -> &'static str {
match tag {
EffectTag::Alloc => "alloc",
EffectTag::ReadTable => "read-table",
EffectTag::WriteTable => "write-table",
EffectTag::ReadEnv => "read-env",
EffectTag::WriteEnv => "write-env",
EffectTag::ReadUpvalue => "read-upvalue",
EffectTag::WriteUpvalue => "write-upvalue",
EffectTag::Call => "call",
EffectTag::Close => "close",
}
}
fn format_edge_kind(kind: super::common::EdgeKind) -> &'static str {
match kind {
super::common::EdgeKind::Fallthrough => "fallthrough",
super::common::EdgeKind::Jump => "jump",
super::common::EdgeKind::BranchTrue => "branch-true",
super::common::EdgeKind::BranchFalse => "branch-false",
super::common::EdgeKind::LoopBody => "loop-body",
super::common::EdgeKind::LoopExit => "loop-exit",
super::common::EdgeKind::Return => "return",
super::common::EdgeKind::TailCall => "tail-call",
}
}