## Coverage Report

#### Created: 2026-01-25 15:05

next uncovered line (L), next uncovered region (R), next uncovered branch (B)

    /home/noah/src/trueno/src/brick/exec_graph/traversal.rs

    Line
    Count
    Source
    1
    //! ExecutionGraph - Execution Path Graph for Profiling
    2
    //!
    3
    //! PAR-201: Captures the full execution hierarchy for profiling analysis.
    4
    5
    use std::collections::HashMap;
    6
    7
    use super::node::{
    8
        EdgeType, ExecutionEdge, ExecutionNode, ExecutionNodeId, TransferDirection,
    9
    };
    10
    11
    /// Execution path graph for tracking brick → kernel → PTX relationships.
    12
    ///
    13
    /// PAR-201: Captures the full execution hierarchy for profiling analysis.
    14
    ///
    15
    /// # Example
    16
    ///
    17
    /// ```rust,ignore
    18
    /// use trueno::brick::{ExecutionGraph, ExecutionNode, EdgeType};
    19
    ///
    20
    /// let mut graph = ExecutionGraph::new();
    21
    ///
    22
    /// // Add layer scope
    23
    /// let layer_id = graph.add_node(ExecutionNode::Layer { index: 0 });
    24
    ///
    25
    /// // Add brick within layer
    26
    /// let brick_id = graph.add_node(ExecutionNode::Brick {
    27
    ///     id: BrickId::QkvProjection,
    28
    ///     timing_ns: 1000,
    29
    ///     elements: 4096,
    30
    /// });
    31
    /// graph.add_edge(layer_id, brick_id, EdgeType::Contains);
    32
    ///
    33
    /// // Add kernel launched by brick
    34
    /// let kernel_id = graph.add_node(ExecutionNode::Kernel {
    35
    ///     name: "batched_q4k_gemv".into(),
    36
    ///     ptx_hash: 0x7a3b1c2d,
    37
    ///     grid: (32, 1, 1),
    38
    ///     block: (256, 1, 1),
    39
    ///     shared_mem: 4096,
    40
    /// });
    41
    /// graph.add_edge(brick_id, kernel_id, EdgeType::Launches);
    42
    ///
    43
    /// // Export to trueno-graph for analysis
    44
    /// #[cfg(feature = "execution-graph")]
    45
    /// let csr = graph.to_csr();
    46
    /// ```
    47
    #[derive(Debug, Default)]
    48
    pub struct ExecutionGraph {
    49
        /// All nodes in the graph
    50
        nodes: Vec<ExecutionNode>,
    51
        /// All edges in the graph
    52
        edges: Vec<ExecutionEdge>,
    53
        /// Scope stack for hierarchical recording
    54
        scope_stack: Vec<ExecutionNodeId>,
    55
        /// Node name → ID mapping for fast lookup
    56
        name_to_id: HashMap<String, ExecutionNodeId>,
    57
    }
    58
    59
    impl ExecutionGraph {
    60
        /// Create a new empty execution graph.
    61
    0
        pub fn new() -> Self {
    62
    0
            Self::default()
    63
    0
        }
    64
    65
        /// Add a node to the graph, returning its ID.
    66
    0
        pub fn add_node(&mut self, node: ExecutionNode) -> ExecutionNodeId {
    67
    0
            let id = ExecutionNodeId(self.nodes.len() as u32);
    68
    0
            let name = node.name();
    69
    0
            self.name_to_id.insert(name, id);
    70
    0
            self.nodes.push(node);
    71
    0
            id
    72
    0
        }
    73
    74
        /// Add an edge between two nodes.
    75
    0
        pub fn add_edge(&mut self, src: ExecutionNodeId, dst: ExecutionNodeId, edge_type: EdgeType) {
    76
    0
            self.edges.push(ExecutionEdge {
    77
    0
                src,
    78
    0
                dst,
    79
    0
                edge_type,
    80
    0
                weight: 1.0,
    81
    0
            });
    82
    0
        }
    83
    84
        /// Add an edge with a weight.
    85
    0
        pub fn add_weighted_edge(
    86
    0
            &mut self,
    87
    0
            src: ExecutionNodeId,
    88
    0
            dst: ExecutionNodeId,
    89
    0
            edge_type: EdgeType,
    90
    0
            weight: f32,
    91
    0
        ) {
    92
    0
            self.edges.push(ExecutionEdge {
    93
    0
                src,
    94
    0
                dst,
    95
    0
                edge_type,
    96
    0
                weight,
    97
    0
            });
    98
    0
        }
    99
    100
        /// Push a scope for hierarchical recording.
    101
        /// All subsequent nodes will be children of this scope.
    102
    0
        pub fn push_scope(&mut self, node: ExecutionNode) -> ExecutionNodeId {
    103
    0
            let id = self.add_node(node);
    104
    0
            if let Some(&parent) = self.scope_stack.last() {
    105
    0
                self.add_edge(parent, id, EdgeType::Contains);
    106
    0
            }
    107
    0
            self.scope_stack.push(id);
    108
    0
            id
    109
    0
        }
    110
    111
        /// Pop the current scope.
    112
    0
        pub fn pop_scope(&mut self) -> Option<ExecutionNodeId> {
    113
    0
            self.scope_stack.pop()
    114
    0
        }
    115
    116
        /// Get the current scope (if any).
    117
    0
        pub fn current_scope(&self) -> Option<ExecutionNodeId> {
    118
    0
            self.scope_stack.last().copied()
    119
    0
        }
    120
    121
        /// Add a node under the current scope.
    122
    0
        pub fn add_node_in_scope(&mut self, node: ExecutionNode) -> ExecutionNodeId {
    123
    0
            let id = self.add_node(node);
    124
    0
            if let Some(&parent) = self.scope_stack.last() {
    125
    0
                self.add_edge(parent, id, EdgeType::Contains);
    126
    0
            }
    127
    0
            id
    128
    0
        }
    129
    130
        /// Record a kernel launch under the current scope.
    131
    0
        pub fn record_kernel_launch(
    132
    0
            &mut self,
    133
    0
            name: &str,
    134
    0
            ptx_hash: u64,
    135
    0
            grid: (u32, u32, u32),
    136
    0
            block: (u32, u32, u32),
    137
    0
            shared_mem: u32,
    138
    0
        ) -> ExecutionNodeId {
    139
    0
            let kernel = ExecutionNode::Kernel {
    140
    0
                name: name.to_string(),
    141
    0
                ptx_hash,
    142
    0
                grid,
    143
    0
                block,
    144
    0
                shared_mem,
    145
    0
                timing_ns: None,
    146
    0
                arithmetic_intensity: None,
    147
    0
                achieved_tflops: None,
    148
    0
            };
    149
    0
            let kernel_id = self.add_node(kernel);
    150
    151
            // Link from current scope with Launches edge
    152
    0
            if let Some(&parent) = self.scope_stack.last() {
    153
    0
                self.add_edge(parent, kernel_id, EdgeType::Launches);
    154
    0
            }
    155
    156
    0
            kernel_id
    157
    0
        }
    158
    159
        /// Record a kernel launch with roofline metrics (Phase 9).
    160
        #[allow(clippy::too_many_arguments)]
    161
    0
        pub fn record_kernel_launch_with_metrics(
    162
    0
            &mut self,
    163
    0
            name: &str,
    164
    0
            ptx_hash: u64,
    165
    0
            grid: (u32, u32, u32),
    166
    0
            block: (u32, u32, u32),
    167
    0
            shared_mem: u32,
    168
    0
            timing_ns: u64,
    169
    0
            arithmetic_intensity: f32,
    170
    0
            achieved_tflops: f32,
    171
    0
        ) -> ExecutionNodeId {
    172
    0
            let kernel = ExecutionNode::Kernel {
    173
    0
                name: name.to_string(),
    174
    0
                ptx_hash,
    175
    0
                grid,
    176
    0
                block,
    177
    0
                shared_mem,
    178
    0
                timing_ns: Some(timing_ns),
    179
    0
                arithmetic_intensity: Some(arithmetic_intensity),
    180
    0
                achieved_tflops: Some(achieved_tflops),
    181
    0
            };
    182
    0
            let kernel_id = self.add_node(kernel);
    183
    184
    0
            if let Some(&parent) = self.scope_stack.last() {
    185
    0
                self.add_edge(parent, kernel_id, EdgeType::Launches);
    186
    0
            }
    187
    188
    0
            kernel_id
    189
    0
        }
    190
    191
        /// Record a memory transfer (Phase 9: data movement topology).
    192
    0
        pub fn record_transfer(
    193
    0
            &mut self,
    194
    0
            src: &str,
    195
    0
            dst: &str,
    196
    0
            bytes: u64,
    197
    0
            direction: TransferDirection,
    198
    0
            timing_ns: Option<u64>,
    199
    0
        ) -> ExecutionNodeId {
    200
    0
            let transfer = ExecutionNode::Transfer {
    201
    0
                src: src.to_string(),
    202
    0
                dst: dst.to_string(),
    203
    0
                bytes,
    204
    0
                direction,
    205
    0
                timing_ns,
    206
    0
            };
    207
    0
            let transfer_id = self.add_node(transfer);
    208
    209
    0
            if let Some(&parent) = self.scope_stack.last() {
    210
    0
                self.add_edge(parent, transfer_id, EdgeType::Contains);
    211
    0
            }
    212
    213
    0
            transfer_id
    214
    0
        }
    215
    216
        /// Add a dependency edge for critical path analysis (Phase 9).
    217
    0
        pub fn add_dependency(&mut self, from: ExecutionNodeId, to: ExecutionNodeId) {
    218
    0
            self.add_edge(from, to, EdgeType::DependsOn);
    219
    0
        }
    220
    221
        /// Get a node by ID.
    222
    0
        pub fn node(&self, id: ExecutionNodeId) -> Option<&ExecutionNode> {
    223
    0
            self.nodes.get(id.0 as usize)
    224
    0
        }
    225
    226
        /// Get a node by name.
    227
    0
        pub fn node_by_name(&self, name: &str) -> Option<(ExecutionNodeId, &ExecutionNode)> {
    228
    0
            self.name_to_id
    229
    0
                .get(name)
    230
    0
                .and_then(|&id| self.nodes.get(id.0 as usize).map(|n| (id, n)))
    231
    0
        }
    232
    233
        /// Get all nodes.
    234
    0
        pub fn nodes(&self) -> &[ExecutionNode] {
    235
    0
            &self.nodes
    236
    0
        }
    237
    238
        /// Get all edges.
    239
    0
        pub fn edges(&self) -> &[ExecutionEdge] {
    240
    0
            &self.edges
    241
    0
        }
    242
    243
        /// Number of nodes.
    244
    0
        pub fn num_nodes(&self) -> usize {
    245
    0
            self.nodes.len()
    246
    0
        }
    247
    248
        /// Number of edges.
    249
    0
        pub fn num_edges(&self) -> usize {
    250
    0
            self.edges.len()
    251
    0
        }
    252
    253
        /// Get outgoing edges for a node.
    254
    0
        pub fn outgoing_edges(&self, node: ExecutionNodeId) -> impl Iterator<Item = &ExecutionEdge> {
    255
    0
            self.edges.iter().filter(move |e| e.src == node)
    256
    0
        }
    257
    258
        /// Get incoming edges for a node.
    259
    0
        pub fn incoming_edges(&self, node: ExecutionNodeId) -> impl Iterator<Item = &ExecutionEdge> {
    260
    0
            self.edges.iter().filter(move |e| e.dst == node)
    261
    0
        }
    262
    263
        /// Find all kernel nodes.
    264
    0
        pub fn kernel_nodes(&self) -> impl Iterator<Item = (ExecutionNodeId, &ExecutionNode)> {
    265
    0
            self.nodes
    266
    0
                .iter()
    267
    0
                .enumerate()
    268
    0
                .filter(|(_, n)| n.is_kernel())
    269
    0
                .map(|(i, n)| (ExecutionNodeId(i as u32), n))
    270
    0
        }
    271
    272
        /// Find the slowest kernel (by parent brick timing).
    273
    0
        pub fn slowest_kernel(&self) -> Option<(ExecutionNodeId, &ExecutionNode, u64)> {
    274
    0
            let mut slowest: Option<(ExecutionNodeId, &ExecutionNode, u64)> = None;
    275
    276
    0
            for (id, node) in self.nodes.iter().enumerate() {
    277
    0
                if let ExecutionNode::Brick { timing_ns, .. } = node {
    278
                    // Check if this brick has kernel children
    279
    0
                    let node_id = ExecutionNodeId(id as u32);
    280
    0
                    let has_kernel = self
    281
    0
                        .outgoing_edges(node_id)
    282
    0
                        .any(|e| e.edge_type == EdgeType::Launches);
    283
    284
    0
                    if has_kernel {
    285
    0
                        match &slowest {
    286
    0
                            None => slowest = Some((node_id, node, *timing_ns)),
    287
    0
                            Some((_, _, t)) if *timing_ns > *t => {
    288
    0
                                slowest = Some((node_id, node, *timing_ns))
    289
                            }
    290
    0
                            _ => {}
    291
                        }
    292
    0
                    }
    293
    0
                }
    294
            }
    295
    296
    0
            slowest
    297
    0
        }
    298
    299
        /// Export to DOT format for Graphviz visualization.
    300
    0
        pub fn to_dot(&self) -> String {
    301
    0
            let mut dot = String::from("digraph ExecutionGraph {\n");
    302
    0
            dot.push_str("  rankdir=TB;\n");
    303
    0
            dot.push_str("  node [shape=box];\n\n");
    304
    305
            // Add nodes with styling based on type
    306
    0
            for (i, node) in self.nodes.iter().enumerate() {
    307
    0
                let (label, style) = match node {
    308
    0
                    ExecutionNode::Layer { index } => {
    309
    0
                        (format!("Layer {}", index), "style=filled,fillcolor=lightblue")
    310
                    }
    311
    0
                    ExecutionNode::Brick { id, timing_ns, .. } => (
    312
    0
                        format!("{}\\n{:.1}µs", id.name(), *timing_ns as f64 / 1000.0),
    313
    0
                        "style=filled,fillcolor=lightgreen",
    314
    0
                    ),
    315
                    ExecutionNode::Kernel {
    316
    0
                        name, grid, block, ..
    317
    0
                    } => (
    318
    0
                        format!("{}\\n<<<{},{},{}>>>", name, grid.0, block.0, block.1),
    319
    0
                        "style=filled,fillcolor=lightyellow",
    320
    0
                    ),
    321
    0
                    ExecutionNode::Function { name, file, line } => {
    322
    0
                        let loc = match (file, line) {
    323
    0
                            (Some(f), Some(l)) => format!("\\n{}:{}", f, l),
    324
    0
                            _ => String::new(),
    325
                        };
    326
    0
                        (
    327
    0
                            format!("{}{}", name, loc),
    328
    0
                            "style=filled,fillcolor=lightgray",
    329
    0
                        )
    330
                    }
    331
                    ExecutionNode::Transfer {
    332
    0
                        src,
    333
    0
                        dst,
    334
    0
                        bytes,
    335
    0
                        direction,
    336
                        ..
    337
                    } => {
    338
    0
                        let dir = match direction {
    339
    0
                            TransferDirection::H2D => "H2D",
    340
    0
                            TransferDirection::D2H => "D2H",
    341
    0
                            TransferDirection::D2D => "D2D",
    342
                        };
    343
    0
                        (
    344
    0
                            format!("{}\\n{}->{}\\n{:.1}MB", dir, src, dst, *bytes as f64 / 1e6),
    345
    0
                            "style=filled,fillcolor=lightsalmon",
    346
    0
                        )
    347
                    }
    348
                    ExecutionNode::AsyncTask {
    349
    0
                        name,
    350
    0
                        poll_count,
    351
    0
                        yield_count,
    352
    0
                        total_poll_ns,
    353
                    } => {
    354
    0
                        let efficiency = if *poll_count > 0 {
    355
    0
                            100.0 / *poll_count as f64
    356
                        } else {
    357
    0
                            0.0
    358
                        };
    359
    0
                        (
    360
    0
                            format!(
    361
    0
                                "{}\\npolls:{} yields:{}\\n{:.1}µs ({:.0}%)",
    362
    0
                                name,
    363
    0
                                poll_count,
    364
    0
                                yield_count,
    365
    0
                                *total_poll_ns as f64 / 1000.0,
    366
    0
                                efficiency
    367
    0
                            ),
    368
    0
                            "style=filled,fillcolor=lightcyan",
    369
    0
                        )
    370
                    }
    371
                };
    372
    0
                dot.push_str(&format!("  n{} [label=\"{}\",{}];\n", i, label, style));
    373
            }
    374
    375
    0
            dot.push('\n');
    376
    377
            // Add edges with styling based on type
    378
    0
            for edge in &self.edges {
    379
    0
                let style = match edge.edge_type {
    380
    0
                    EdgeType::Calls => "style=solid",
    381
    0
                    EdgeType::Contains => "style=dashed",
    382
    0
                    EdgeType::Launches => "style=bold,color=red",
    383
    0
                    EdgeType::Sequence => "style=dotted",
    384
    0
                    EdgeType::DependsOn => "style=solid,color=blue",
    385
    0
                    EdgeType::Transfer { .. } => "style=bold,color=orange",
    386
                };
    387
    0
                dot.push_str(&format!(
    388
    0
                    "  n{} -> n{} [{}];\n",
    389
    0
                    edge.src.0, edge.dst.0, style
    390
    0
                ));
    391
            }
    392
    393
    0
            dot.push_str("}\n");
    394
    0
            dot
    395
    0
        }
    396
    397
        /// Export to trueno-graph CsrGraph format.
    398
        #[cfg(feature = "execution-graph")]
    399
        pub fn to_csr(&self) -> trueno_graph::CsrGraph {
    400
            use trueno_graph::{CsrGraph, NodeId};
    401
    402
            let edges: Vec<(NodeId, NodeId, f32)> = self
    403
                .edges
    404
                .iter()
    405
                .map(|e| (NodeId(e.src.0), NodeId(e.dst.0), e.weight))
    406
                .collect();
    407
    408
            let mut graph = CsrGraph::from_edge_list(&edges).unwrap_or_default();
    409
    410
            // Set node names for querying
    411
            for (i, node) in self.nodes.iter().enumerate() {
    412
                graph.set_node_name(NodeId(i as u32), node.name());
    413
            }
    414
    415
            graph
    416
        }
    417
    418
        /// Convert to presentar-terminal TreeNode for TUI visualization.
    419
        ///
    420
        /// PAR-201: Renders the execution graph as a collapsible tree in the terminal.
    421
        #[cfg(feature = "presentar-tui")]
    422
        pub fn to_tree_node(&self) -> presentar_terminal::TreeNode {
    423
            use presentar_terminal::{Color, TreeNode};
    424
    425
            // Color scheme for node types
    426
            let layer_color = Color::new(0.4, 0.6, 1.0, 1.0); // Light blue
    427
            let brick_color = Color::new(0.4, 0.8, 0.4, 1.0); // Light green
    428
            let kernel_color = Color::new(1.0, 0.8, 0.3, 1.0); // Yellow/orange
    429
            let func_color = Color::new(0.7, 0.7, 0.7, 1.0); // Light gray
    430
    431
            // Build child map: parent -> [children]
    432
            let mut children_map: HashMap<u32, Vec<u32>> = HashMap::new();
    433
            let mut has_parent: std::collections::HashSet<u32> = std::collections::HashSet::new();
    434
    435
            for edge in &self.edges {
    436
                if edge.edge_type == EdgeType::Contains || edge.edge_type == EdgeType::Launches {
    437
                    children_map
    438
                        .entry(edge.src.0)
    439
                        .or_default()
    440
                        .push(edge.dst.0);
    441
                    has_parent.insert(edge.dst.0);
    442
                }
    443
            }
    444
    445
            // Find root nodes (nodes with no parent)
    446
            let root_ids: Vec<u32> = (0..self.nodes.len() as u32)
    447
                .filter(|id| !has_parent.contains(id))
    448
                .collect();
    449
    450
            // Recursive function to build TreeNode
    451
            fn build_node(
    452
                graph: &ExecutionGraph,
    453
                id: u32,
    454
                children_map: &HashMap<u32, Vec<u32>>,
    455
                layer_color: Color,
    456
                brick_color: Color,
    457
                kernel_color: Color,
    458
                func_color: Color,
    459
            ) -> TreeNode {
    460
                let node = &graph.nodes[id as usize];
    461
                let (label, info, color) = match node {
    462
                    ExecutionNode::Layer { index } => {
    463
                        (format!("Layer {}", index), None, layer_color)
    464
                    }
    465
                    ExecutionNode::Brick {
    466
                        id: brick_id,
    467
                        timing_ns,
    468
                        elements,
    469
                    } => (
    470
                        brick_id.name().to_string(),
    471
                        Some(format!(
    472
                            "{:.1}µs ({} elem)",
    473
                            *timing_ns as f64 / 1000.0,
    474
                            elements
    475
                        )),
    476
                        brick_color,
    477
                    ),
    478
                    ExecutionNode::Kernel {
    479
                        name,
    480
                        grid,
    481
                        block,
    482
                        shared_mem,
    483
                        ..
    484
                    } => (
    485
                        name.clone(),
    486
                        Some(format!(
    487
                            "<<<{},{},{}>>> smem={}B",
    488
                            grid.0, block.0, block.1, shared_mem
    489
                        )),
    490
                        kernel_color,
    491
                    ),
    492
                    ExecutionNode::Function { name, file, line } => {
    493
                        let loc = match (file, line) {
    494
                            (Some(f), Some(l)) => format!(" ({}:{})", f, l),
    495
                            _ => String::new(),
    496
                        };
    497
                        (format!("{}{}", name, loc), None, func_color)
    498
                    }
    499
                    ExecutionNode::Transfer {
    500
                        src,
    501
                        dst,
    502
                        bytes,
    503
                        direction,
    504
                        timing_ns,
    505
                    } => {
    506
                        let timing_str = timing_ns
    507
                            .map(|ns| format!(" {:.1}µs", ns as f64 / 1000.0))
    508
                            .unwrap_or_default();
    509
                        (
    510
                            format!("{:?}: {} → {}", direction, src, dst),
    511
                            Some(format!("{}B{}", bytes, timing_str)),
    512
                            Color::new(0.8, 0.4, 0.8, 1.0), // Transfer color (magenta)
    513
                        )
    514
                    }
    515
                    ExecutionNode::AsyncTask {
    516
                        name,
    517
                        poll_count,
    518
                        yield_count,
    519
                        total_poll_ns,
    520
                    } => {
    521
                        let efficiency = if *poll_count > 0 {
    522
                            100.0 / *poll_count as f64
    523
                        } else {
    524
                            0.0
    525
                        };
    526
                        (
    527
                            name.clone(),
    528
                            Some(format!(
    529
                                "polls:{} yields:{} {:.1}µs ({:.0}% eff)",
    530
                                poll_count,
    531
                                yield_count,
    532
                                *total_poll_ns as f64 / 1000.0,
    533
                                efficiency
    534
                            )),
    535
                            Color::new(0.4, 0.8, 0.8, 1.0), // Async task color (cyan)
    536
                        )
    537
                    }
    538
                };
    539
    540
                let mut tree_node = TreeNode::new(id as u64, label).with_color(color);
    541
                if let Some(info_str) = info {
    542
                    tree_node = tree_node.with_info(info_str);
    543
                }
    544
    545
                // Add children
    546
                if let Some(child_ids) = children_map.get(&id) {
    547
                    for &child_id in child_ids {
    548
                        let child = build_node(
    549
                            graph,
    550
                            child_id,
    551
                            children_map,
    552
                            layer_color,
    553
                            brick_color,
    554
                            kernel_color,
    555
                            func_color,
    556
                        );
    557
                        tree_node = tree_node.with_child(child);
    558
                    }
    559
                }
    560
    561
                tree_node
    562
            }
    563
    564
            // Build root node
    565
            if root_ids.is_empty() {
    566
                TreeNode::new(0, "Empty Graph")
    567
            } else if root_ids.len() == 1 {
    568
                build_node(
    569
                    self,
    570
                    root_ids[0],
    571
                    &children_map,
    572
                    layer_color,
    573
                    brick_color,
    574
                    kernel_color,
    575
                    func_color,
    576
                )
    577
            } else {
    578
                // Multiple roots: wrap in a synthetic root
    579
                let mut root =
    580
                    TreeNode::new(u64::MAX, "Execution Graph").with_color(Color::new(0.9, 0.9, 0.9, 1.0));
    581
                for &root_id in &root_ids {
    582
                    let child = build_node(
    583
                        self,
    584
                        root_id,
    585
                        &children_map,
    586
                        layer_color,
    587
                        brick_color,
    588
                        kernel_color,
    589
                        func_color,
    590
                    );
    591
                    root = root.with_child(child);
    592
                }
    593
                root
    594
            }
    595
        }
    596
    597
        /// Render graph to ASCII tree string (headless mode for testing/automation).
    598
        ///
    599
        /// PAR-201: Zero-dependency tree visualization for CI/CD, logging, and snapshot tests.
    600
        #[must_use]
    601
    0
        pub fn to_ascii_tree(&self) -> String {
    602
            // Build child map: parent -> [children]
    603
    0
            let mut children_map: HashMap<u32, Vec<u32>> = HashMap::new();
    604
    0
            let mut has_parent: std::collections::HashSet<u32> = std::collections::HashSet::new();
    605
    606
    0
            for edge in &self.edges {
    607
    0
                if edge.edge_type == EdgeType::Contains || edge.edge_type == EdgeType::Launches {
    608
    0
                    children_map
    609
    0
                        .entry(edge.src.0)
    610
    0
                        .or_default()
    611
    0
                        .push(edge.dst.0);
    612
    0
                    has_parent.insert(edge.dst.0);
    613
    0
                }
    614
            }
    615
    616
            // Find root nodes (nodes with no parent)
    617
    0
            let root_ids: Vec<u32> = (0..self.nodes.len() as u32)
    618
    0
                .filter(|id| !has_parent.contains(id))
    619
    0
                .collect();
    620
    621
            // Recursive function to build tree string
    622
    0
            fn build_tree(
    623
    0
                graph: &ExecutionGraph,
    624
    0
                id: u32,
    625
    0
                children_map: &HashMap<u32, Vec<u32>>,
    626
    0
                prefix: &str,
    627
    0
                connector: &str,
    628
    0
                output: &mut String,
    629
    0
            ) {
    630
    0
                let node = &graph.nodes[id as usize];
    631
    0
                let (label, info) = match node {
    632
    0
                    ExecutionNode::Layer { index } => (format!("Layer {}", index), String::new()),
    633
                    ExecutionNode::Brick {
    634
    0
                        id: brick_id,
    635
    0
                        timing_ns,
    636
    0
                        elements,
    637
    0
                    } => (
    638
    0
                        brick_id.name().to_string(),
    639
    0
                        format!("  {:.1}µs ({} elem)", *timing_ns as f64 / 1000.0, elements),
    640
    0
                    ),
    641
                    ExecutionNode::Kernel {
    642
    0
                        name,
    643
    0
                        grid,
    644
    0
                        block,
    645
    0
                        shared_mem,
    646
                        ..
    647
    0
                    } => (
    648
    0
                        name.clone(),
    649
    0
                        format!(
    650
    0
                            "  <<<{},{},{}>>> smem={}B",
    651
    0
                            grid.0, block.0, block.1, shared_mem
    652
    0
                        ),
    653
    0
                    ),
    654
    0
                    ExecutionNode::Function { name, file, line } => {
    655
    0
                        let loc = match (file, line) {
    656
    0
                            (Some(f), Some(l)) => format!(" ({}:{})", f, l),
    657
    0
                            _ => String::new(),
    658
                        };
    659
    0
                        (format!("{}{}", name, loc), String::new())
    660
                    }
    661
                    ExecutionNode::Transfer {
    662
    0
                        src,
    663
    0
                        dst,
    664
    0
                        bytes,
    665
    0
                        direction,
    666
    0
                        timing_ns,
    667
                    } => {
    668
    0
                        let timing_str = timing_ns
    669
    0
                            .map(|ns| format!(" {:.1}µs", ns as f64 / 1000.0))
    670
    0
                            .unwrap_or_default();
    671
    0
                        (
    672
    0
                            format!("{:?}: {} → {}", direction, src, dst),
    673
    0
                            format!("  {}B{}", bytes, timing_str),
    674
    0
                        )
    675
                    }
    676
                    ExecutionNode::AsyncTask {
    677
    0
                        name,
    678
    0
                        poll_count,
    679
    0
                        yield_count,
    680
    0
                        total_poll_ns,
    681
                    } => {
    682
    0
                        let efficiency = if *poll_count > 0 {
    683
    0
                            100.0 / *poll_count as f64
    684
                        } else {
    685
    0
                            0.0
    686
                        };
    687
    0
                        (
    688
    0
                            name.clone(),
    689
    0
                            format!(
    690
    0
                                "  polls:{} yields:{} {:.1}µs ({:.0}% eff)",
    691
    0
                                poll_count,
    692
    0
                                yield_count,
    693
    0
                                *total_poll_ns as f64 / 1000.0,
    694
    0
                                efficiency
    695
    0
                            ),
    696
    0
                        )
    697
                    }
    698
                };
    699
    700
    0
                output.push_str(&format!("{}{}{}{}\n", prefix, connector, label, info));
    701
    702
    0
                if let Some(child_ids) = children_map.get(&id) {
    703
    0
                    let child_count = child_ids.len();
    704
    0
                    for (i, &child_id) in child_ids.iter().enumerate() {
    705
    0
                        let is_last = i == child_count - 1;
    706
    0
                        let new_connector = if is_last { "└── " } else { "├── " };
    707
    0
                        let new_prefix = if connector.is_empty() {
    708
    0
                            prefix.to_string()
    709
    0
                        } else if connector == "└── " {
    710
    0
                            format!("{}    ", prefix)
    711
                        } else {
    712
    0
                            format!("{}│   ", prefix)
    713
                        };
    714
    0
                        build_tree(graph, child_id, children_map, &new_prefix, new_connector, output);
    715
                    }
    716
    0
                }
    717
    0
            }
    718
    719
    0
            let mut output = String::new();
    720
    721
    0
            if root_ids.is_empty() {
    722
    0
                output.push_str("(empty graph)\n");
    723
    0
            } else if root_ids.len() == 1 {
    724
    0
                build_tree(self, root_ids[0], &children_map, "", "", &mut output);
    725
    0
            } else {
    726
                // Multiple roots: add synthetic root
    727
    0
                output.push_str("Execution Graph\n");
    728
    0
                let root_count = root_ids.len();
    729
    0
                for (i, &root_id) in root_ids.iter().enumerate() {
    730
    0
                    let is_last = i == root_count - 1;
    731
    0
                    let connector = if is_last { "└── " } else { "├── " };
    732
    0
                    build_tree(self, root_id, &children_map, "", connector, &mut output);
    733
                }
    734
            }
    735
    736
            // Remove trailing newline for cleaner output
    737
    0
            if output.ends_with('\n') {
    738
    0
                output.pop();
    739
    0
            }
    740
    0
            output
    741
    0
        }
    742
    743
        // ========================
    744
        // Phase 9: Critical Path Analysis (CPA)
    745
        // ========================
    746
    747
        /// Get timing for a node (ns). Returns 0 for non-timed nodes.
    748
    0
        fn node_timing_ns(&self, id: ExecutionNodeId) -> u64 {
    749
    0
            match &self.nodes[id.0 as usize] {
    750
    0
                ExecutionNode::Brick { timing_ns, .. } => *timing_ns,
    751
    0
                ExecutionNode::Kernel { timing_ns, .. } => timing_ns.unwrap_or(0),
    752
    0
                ExecutionNode::Transfer { timing_ns, .. } => timing_ns.unwrap_or(0),
    753
    0
                _ => 0,
    754
            }
    755
    0
        }
    756
    757
        /// Compute critical path through execution graph using longest-path algorithm.
    758
        ///
    759
        /// Returns (critical_path_nodes, total_time_ns). The critical path represents
    760
        /// the longest chain of dependencies that determines total execution time.
    761
        ///
    762
        /// Reference: Graham et al. (1979) "Scheduling Algorithms for Multi-Processor Systems"
    763
    0
        pub fn critical_path(&self) -> (Vec<ExecutionNodeId>, u64) {
    764
    0
            if self.nodes.is_empty() {
    765
    0
                return (vec![], 0);
    766
    0
            }
    767
    768
            // Build adjacency list for DependsOn and Sequence edges
    769
    0
            let mut adj: Vec<Vec<(u32, u64)>> = vec![vec![]; self.nodes.len()];
    770
    0
            for edge in &self.edges {
    771
    0
                match &edge.edge_type {
    772
    0
                    EdgeType::DependsOn | EdgeType::Sequence => {
    773
    0
                        let weight = self.node_timing_ns(edge.dst);
    774
    0
                        adj[edge.src.0 as usize].push((edge.dst.0, weight));
    775
    0
                    }
    776
    0
                    EdgeType::Contains | EdgeType::Calls | EdgeType::Launches => {
    777
    0
                        // Hierarchical edges: children contribute to parent time
    778
    0
                        let weight = self.node_timing_ns(edge.dst);
    779
    0
                        adj[edge.src.0 as usize].push((edge.dst.0, weight));
    780
    0
                    }
    781
    0
                    EdgeType::Transfer { .. } => {
    782
    0
                        // Transfer edges carry their own timing
    783
    0
                        let weight = self.node_timing_ns(edge.dst);
    784
    0
                        adj[edge.src.0 as usize].push((edge.dst.0, weight));
    785
    0
                    }
    786
                }
    787
            }
    788
    789
            // Topological sort using Kahn's algorithm
    790
    0
            let mut in_degree = vec![0u32; self.nodes.len()];
    791
    0
            for edges in &adj {
    792
    0
                for (dst, _) in edges {
    793
    0
                    in_degree[*dst as usize] += 1;
    794
    0
                }
    795
            }
    796
    797
    0
            let mut queue: Vec<u32> = (0..self.nodes.len() as u32)
    798
    0
                .filter(|&i| in_degree[i as usize] == 0)
    799
    0
                .collect();
    800
    0
            let mut topo_order = Vec::with_capacity(self.nodes.len());
    801
    802
    0
            while let Some(u) = queue.pop() {
    803
    0
                topo_order.push(u);
    804
    0
                for (v, _) in &adj[u as usize] {
    805
    0
                    in_degree[*v as usize] -= 1;
    806
    0
                    if in_degree[*v as usize] == 0 {
    807
    0
                        queue.push(*v);
    808
    0
                    }
    809
                }
    810
            }
    811
    812
            // Longest path DP
    813
    0
            let mut dist = vec![0u64; self.nodes.len()];
    814
    0
            let mut pred = vec![None::<u32>; self.nodes.len()];
    815
    816
            // Initialize with node's own timing for roots
    817
    0
            for &node in &topo_order {
    818
    0
                if self.edges.iter().all(|e| e.dst.0 != node) {
    819
    0
                    dist[node as usize] = self.node_timing_ns(ExecutionNodeId(node));
    820
    0
                }
    821
            }
    822
    823
    0
            for &u in &topo_order {
    824
    0
                for (v, weight) in &adj[u as usize] {
    825
    0
                    let new_dist = dist[u as usize] + weight;
    826
    0
                    if new_dist > dist[*v as usize] {
    827
    0
                        dist[*v as usize] = new_dist;
    828
    0
                        pred[*v as usize] = Some(u);
    829
    0
                    }
    830
                }
    831
            }
    832
    833
            // Find endpoint with maximum distance
    834
    0
            let (end_node, &total_time) = dist
    835
    0
                .iter()
    836
    0
                .enumerate()
    837
    0
                .max_by_key(|(_, &d)| d)
    838
    0
                .unwrap_or((0, &0));
    839
    840
            // Reconstruct path
    841
    0
            let mut path = vec![];
    842
    0
            let mut current = Some(end_node as u32);
    843
    0
            while let Some(node) = current {
    844
    0
                path.push(ExecutionNodeId(node));
    845
    0
                current = pred[node as usize];
    846
    0
            }
    847
    0
            path.reverse();
    848
    849
    0
            (path, total_time)
    850
    0
        }
    851
    852
        /// Compute slack for each node (how much it can be delayed without affecting total time).
    853
        ///
    854
        /// Returns map from node ID to slack in nanoseconds. Nodes on critical path have slack = 0.
    855
    0
        pub fn compute_slack(&self) -> HashMap<ExecutionNodeId, u64> {
    856
    0
            let (critical_path, total_time) = self.critical_path();
    857
    0
            let critical_set: std::collections::HashSet<_> = critical_path.iter().copied().collect();
    858
    859
    0
            let mut slack = HashMap::new();
    860
    861
            // Build reverse adjacency
    862
    0
            let mut reverse_adj: Vec<Vec<u32>> = vec![vec![]; self.nodes.len()];
    863
    0
            for edge in &self.edges {
    864
    0
                reverse_adj[edge.dst.0 as usize].push(edge.src.0);
    865
    0
            }
    866
    867
            // Forward pass: earliest start time
    868
    0
            let mut earliest = vec![0u64; self.nodes.len()];
    869
    0
            for i in 0..self.nodes.len() {
    870
    0
                let mut max_pred = 0u64;
    871
    0
                for &pred in &reverse_adj[i] {
    872
    0
                    max_pred =
    873
    0
                        max_pred.max(earliest[pred as usize] + self.node_timing_ns(ExecutionNodeId(pred)));
    874
    0
                }
    875
    0
                earliest[i] = max_pred;
    876
            }
    877
    878
            // Backward pass: latest start time
    879
    0
            let mut latest = vec![total_time; self.nodes.len()];
    880
    0
            for i in (0..self.nodes.len()).rev() {
    881
    0
                let timing = self.node_timing_ns(ExecutionNodeId(i as u32));
    882
    0
                let mut min_succ = total_time;
    883
    0
                for edge in &self.edges {
    884
    0
                    if edge.src.0 == i as u32 {
    885
    0
                        min_succ = min_succ.min(latest[edge.dst.0 as usize]);
    886
    0
                    }
    887
                }
    888
    0
                latest[i] = min_succ.saturating_sub(timing);
    889
            }
    890
    891
            // Slack = latest - earliest
    892
    0
            for i in 0..self.nodes.len() {
    893
    0
                let node_id = ExecutionNodeId(i as u32);
    894
    0
                let node_slack = if critical_set.contains(&node_id) {
    895
    0
                    0
    896
                } else {
    897
    0
                    latest[i].saturating_sub(earliest[i])
    898
                };
    899
    0
                slack.insert(node_id, node_slack);
    900
            }
    901
    902
    0
            slack
    903
    0
        }
    904
    905
        /// Compute roofline distance for kernel nodes.
    906
        ///
    907
        /// Returns map from kernel node ID to distance from roofline (0.0 = optimal).
    908
        /// Distance = 1.0 - min(achieved/peak_compute, achieved/peak_bandwidth).
    909
        ///
    910
        /// Reference: Williams et al. (2009) "Roofline: An Insightful Visual Performance Model"
    911
    0
        pub fn roofline_distance(
    912
    0
            &self,
    913
    0
            peak_tflops: f32,
    914
    0
            peak_bandwidth_gb_s: f32,
    915
    0
        ) -> HashMap<ExecutionNodeId, f32> {
    916
    0
            let mut distances = HashMap::new();
    917
    918
    0
            for (i, node) in self.nodes.iter().enumerate() {
    919
                if let ExecutionNode::Kernel {
    920
    0
                    arithmetic_intensity,
    921
    0
                    achieved_tflops,
    922
                    ..
    923
    0
                } = node
    924
                {
    925
    0
                    if let (Some(ai), Some(achieved)) = (arithmetic_intensity, achieved_tflops) {
    926
    0
                        // Roofline model: achievable = min(peak_compute, ai * bandwidth)
    927
    0
                        let bandwidth_bound = *ai * peak_bandwidth_gb_s / 1000.0; // Convert GB/s to TFLOP/s
    928
    0
                        let roofline_bound = peak_tflops.min(bandwidth_bound);
    929
    0
                        let efficiency = achieved / roofline_bound;
    930
    0
                        let distance = 1.0 - efficiency.min(1.0);
    931
    0
                        distances.insert(ExecutionNodeId(i as u32), distance);
    932
    0
                    }
    933
    0
                }
    934
            }
    935
    936
    0
            distances
    937
    0
        }
    938
    939
        /// Detect ping-pong memory transfer patterns (wasteful H2D followed by D2H).
    940
        ///
    941
        /// Returns pairs of transfer node IDs that exhibit ping-pong behavior.
    942
    0
        pub fn detect_ping_pong(&self) -> Vec<(ExecutionNodeId, ExecutionNodeId)> {
    943
    0
            let mut patterns = Vec::new();
    944
    945
            // Find transfer nodes
    946
    0
            let transfers: Vec<(usize, &ExecutionNode)> = self
    947
    0
                .nodes
    948
    0
                .iter()
    949
    0
                .enumerate()
    950
    0
                .filter(|(_, n)| matches!(n, ExecutionNode::Transfer { .. }))
    951
    0
                .collect();
    952
    953
            // Check for H2D followed by D2H on same data
    954
    0
            for i in 0..transfers.len() {
    955
    0
                for j in (i + 1)..transfers.len() {
    956
                    if let (
    957
                        ExecutionNode::Transfer {
    958
    0
                            src: src1,
    959
    0
                            dst: dst1,
    960
    0
                            direction: dir1,
    961
    0
                            bytes: bytes1,
    962
                            ..
    963
                        },
    964
                        ExecutionNode::Transfer {
    965
    0
                            src: src2,
    966
    0
                            dst: dst2,
    967
    0
                            direction: dir2,
    968
    0
                            bytes: bytes2,
    969
                            ..
    970
                        },
    971
    0
                    ) = (&transfers[i].1, &transfers[j].1)
    972
                    {
    973
                        // Ping-pong: H2D then D2H with matching src/dst and same size
    974
    0
                        let is_ping_pong = (*dir1 == TransferDirection::H2D
    975
    0
                            && *dir2 == TransferDirection::D2H
    976
    0
                            && dst1 == src2
    977
    0
                            && bytes1 == bytes2)
    978
    0
                            || (*dir1 == TransferDirection::D2H
    979
    0
                                && *dir2 == TransferDirection::H2D
    980
    0
                                && src1 == dst2
    981
    0
                                && bytes1 == bytes2);
    982
    983
    0
                        if is_ping_pong {
    984
    0
                            patterns.push((
    985
    0
                                ExecutionNodeId(transfers[i].0 as u32),
    986
    0
                                ExecutionNodeId(transfers[j].0 as u32),
    987
    0
                            ));
    988
    0
                        }
    989
    0
                    }
    990
                }
    991
            }
    992
    993
    0
            patterns
    994
    0
        }
    995
    996
        /// Get critical path analysis summary as formatted string.
    997
    0
        pub fn critical_path_summary(&self) -> String {
    998
    0
            let (path, total_ns) = self.critical_path();
    999
    0
            let slack = self.compute_slack();
    1000
    1001
    0
            let mut output = String::new();
    1002
    0
            output.push_str(&format!(
    1003
    0
                "Critical Path: {:.2}ms ({} nodes)\n",
    1004
    0
                total_ns as f64 / 1_000_000.0,
    1005
    0
                path.len()
    1006
    0
            ));
    1007
    0
            output.push_str("─".repeat(50).as_str());
    1008
    0
            output.push('\n');
    1009
    1010
    0
            for (i, node_id) in path.iter().enumerate() {
    1011
    0
                let node = &self.nodes[node_id.0 as usize];
    1012
    0
                let timing = self.node_timing_ns(*node_id);
    1013
    0
                let node_name = match node {
    1014
    0
                    ExecutionNode::Layer { index } => format!("Layer {}", index),
    1015
    0
                    ExecutionNode::Brick { id, .. } => id.name().to_string(),
    1016
    0
                    ExecutionNode::Kernel { name, .. } => name.clone(),
    1017
    0
                    ExecutionNode::Function { name, .. } => name.clone(),
    1018
                    ExecutionNode::Transfer {
    1019
    0
                        direction, src, dst, ..
    1020
                    } => {
    1021
    0
                        format!("{:?} {} → {}", direction, src, dst)
    1022
                    }
    1023
                    ExecutionNode::AsyncTask {
    1024
    0
                        name, poll_count, ..
    1025
                    } => {
    1026
    0
                        format!("{} ({}polls)", name, poll_count)
    1027
                    }
    1028
                };
    1029
    1030
    0
                let prefix = if i == 0 {
    1031
    0
                    "┌"
    1032
    0
                } else if i == path.len() - 1 {
    1033
    0
                    "└"
    1034
                } else {
    1035
    0
                    "│"
    1036
                };
    1037
    0
                output.push_str(&format!(
    1038
    0
                    "{} {} ({:.1}µs)\n",
    1039
    0
                    prefix,
    1040
    0
                    node_name,
    1041
    0
                    timing as f64 / 1000.0
    1042
    0
                ));
    1043
            }
    1044
    1045
            // Show nodes with most slack (parallelization opportunities)
    1046
    0
            let mut slack_vec: Vec<_> = slack.iter().collect();
    1047
    0
            slack_vec.sort_by(|a, b| b.1.cmp(a.1));
    1048
    1049
    0
            if slack_vec.iter().any(|(_, &s)| s > 0) {
    1050
    0
                output.push_str("\nParallelization Opportunities (high slack):\n");
    1051
    0
                for (node_id, &node_slack) in slack_vec.iter().take(5) {
    1052
    0
                    if node_slack > 0 {
    1053
    0
                        let node = &self.nodes[node_id.0 as usize];
    1054
    0
                        let node_name = match node {
    1055
    0
                            ExecutionNode::Layer { index } => format!("Layer {}", index),
    1056
    0
                            ExecutionNode::Brick { id, .. } => id.name().to_string(),
    1057
    0
                            ExecutionNode::Kernel { name, .. } => name.clone(),
    1058
    0
                            ExecutionNode::Function { name, .. } => name.clone(),
    1059
                            ExecutionNode::Transfer {
    1060
    0
                                direction, src, dst, ..
    1061
                            } => {
    1062
    0
                                format!("{:?} {} → {}", direction, src, dst)
    1063
                            }
    1064
                            ExecutionNode::AsyncTask {
    1065
    0
                                name, poll_count, ..
    1066
                            } => {
    1067
    0
                                format!("{} ({}polls)", name, poll_count)
    1068
                            }
    1069
                        };
    1070
    0
                        output.push_str(&format!(
    1071
    0
                            "  {} slack={:.1}µs\n",
    1072
    0
                            node_name,
    1073
    0
                            node_slack as f64 / 1000.0
    1074
    0
                        ));
    1075
    0
                    }
    1076
                }
    1077
    0
            }
    1078
    1079
    0
            output
    1080
    0
        }
    1081
    1082
        /// Clear the graph.
    1083
    0
        pub fn clear(&mut self) {
    1084
    0
            self.nodes.clear();
    1085
    0
            self.edges.clear();
    1086
    0
            self.scope_stack.clear();
    1087
    0
            self.name_to_id.clear();
    1088
    0
        }
    1089
    1090
        /// Check if scope stack is balanced (empty).
    1091
    0
        pub fn is_scope_balanced(&self) -> bool {
    1092
    0
            self.scope_stack.is_empty()
    1093
    0
        }
    1094
    }