## Coverage Report

#### Created: 2026-01-23 22:55

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

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

    Line
    Count
    Source
    1
    //! Execution Graph and Brick Profiling Types
    2
    //!
    3
    //! This module contains types for execution path tracking and profiling:
    4
    //!
    5
    //! - **PAR-073**: BrickSample, BrickBottleneck - foundational profiling primitives
    6
    //! - **PAR-200**: BrickId, BrickCategory, SyncMode - O(1) hot path brick identification
    7
    //! - **PAR-201**: ExecutionGraph, ExecutionNode, etc. - full execution hierarchy tracking
    8
    9
    use std::collections::HashMap;
    10
    use std::fmt;
    11
    12
    // ============================================================================
    13
    // BrickProfiler: FOUNDATIONAL Real-Time Per-Brick Timing (PAR-073)
    14
    // ============================================================================
    15
    16
    /// Individual brick timing sample.
    17
    /// Pure Rust timing using `std::time::Instant`.
    18
    #[derive(Debug, Clone, Copy)]
    19
    pub struct BrickSample {
    20
        /// Brick name hash (for fast lookup)
    21
        pub brick_id: u64,
    22
        /// Elapsed time in nanoseconds
    23
        pub elapsed_ns: u64,
    24
        /// Number of elements processed
    25
        pub elements: u64,
    26
    }
    27
    28
    /// Bottleneck classification for roofline analysis (PMAT-451)
    29
    #[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
    30
    pub enum BrickBottleneck {
    31
        /// Not classified
    32
        #[default]
    33
        Unknown,
    34
        /// Limited by memory bandwidth
    35
        Memory,
    36
        /// Limited by compute throughput
    37
        Compute,
    38
    }
    39
    40
    impl fmt::Display for BrickBottleneck {
    41
    0
        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    42
    0
            match self {
    43
    0
                BrickBottleneck::Unknown => write!(f, "unknown"),
    44
    0
                BrickBottleneck::Memory => write!(f, "memory"),
    45
    0
                BrickBottleneck::Compute => write!(f, "compute"),
    46
            }
    47
    0
        }
    48
    }
    49
    50
    // ============================================================================
    51
    // PAR-200: BrickProfiler v2 - O(1) Hot Path with BrickId Enum
    52
    // ============================================================================
    53
    54
    /// Well-known brick types for O(1) lookup on hot path.
    55
    ///
    56
    /// PAR-200: Eliminates string allocation and HashMap hashing during profiling.
    57
    /// Use `BrickId::Custom` with string fallback for unknown brick types.
    58
    ///
    59
    /// # Example
    60
    /// ```rust
    61
    /// use trueno::brick::BrickId;
    62
    ///
    63
    /// let brick = BrickId::RmsNorm;
    64
    /// assert_eq!(brick.category(), trueno::brick::BrickCategory::Norm);
    65
    /// assert_eq!(brick.name(), "RmsNorm");
    66
    /// ```
    67
    #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
    68
    #[repr(u8)]
    69
    pub enum BrickId {
    70
        // Normalization (0-1)
    71
        /// RMS normalization layer
    72
        RmsNorm = 0,
    73
        /// Layer normalization
    74
        LayerNorm = 1,
    75
    76
        // Attention (2-7)
    77
        /// Q/K/V projection (combined or separate)
    78
        QkvProjection = 2,
    79
        /// Rotary position embedding
    80
        RopeEmbedding = 3,
    81
        /// Attention score computation (Q @ K^T)
    82
        AttentionScore = 4,
    83
        /// Attention softmax
    84
        AttentionSoftmax = 5,
    85
        /// Attention output (scores @ V)
    86
        AttentionOutput = 6,
    87
        /// Output projection after attention
    88
        OutputProjection = 7,
    89
    90
        // FFN (8-11)
    91
        /// Gate projection (for gated FFN)
    92
        GateProjection = 8,
    93
        /// Up projection
    94
        UpProjection = 9,
    95
        /// SiLU/GELU/ReLU activation
    96
        Activation = 10,
    97
        /// Down projection
    98
        DownProjection = 11,
    99
    100
        // Other (12-14)
    101
        /// Token embedding lookup
    102
        Embedding = 12,
    103
        /// Language model head (logits)
    104
        LmHead = 13,
    105
        /// Token sampling
    106
        Sampling = 14,
    107
    }
    108
    109
    impl BrickId {
    110
        /// Number of well-known brick types.
    111
        pub const COUNT: usize = 15;
    112
    113
        /// Get the category for hierarchical aggregation.
    114
        #[inline]
    115
    0
        pub fn category(self) -> BrickCategory {
    116
    0
            match self {
    117
    0
                Self::RmsNorm | Self::LayerNorm => BrickCategory::Norm,
    118
                Self::QkvProjection
    119
                | Self::RopeEmbedding
    120
                | Self::AttentionScore
    121
                | Self::AttentionSoftmax
    122
                | Self::AttentionOutput
    123
    0
                | Self::OutputProjection => BrickCategory::Attention,
    124
                Self::GateProjection | Self::UpProjection | Self::Activation | Self::DownProjection => {
    125
    0
                    BrickCategory::Ffn
    126
                }
    127
    0
                Self::Embedding | Self::LmHead | Self::Sampling => BrickCategory::Other,
    128
            }
    129
    0
        }
    130
    131
        /// Get the string name of this brick.
    132
        #[inline]
    133
    0
        pub const fn name(self) -> &'static str {
    134
    0
            match self {
    135
    0
                Self::RmsNorm => "RmsNorm",
    136
    0
                Self::LayerNorm => "LayerNorm",
    137
    0
                Self::QkvProjection => "QkvProjection",
    138
    0
                Self::RopeEmbedding => "RopeEmbedding",
    139
    0
                Self::AttentionScore => "AttentionScore",
    140
    0
                Self::AttentionSoftmax => "AttentionSoftmax",
    141
    0
                Self::AttentionOutput => "AttentionOutput",
    142
    0
                Self::OutputProjection => "OutputProjection",
    143
    0
                Self::GateProjection => "GateProjection",
    144
    0
                Self::UpProjection => "UpProjection",
    145
    0
                Self::Activation => "Activation",
    146
    0
                Self::DownProjection => "DownProjection",
    147
    0
                Self::Embedding => "Embedding",
    148
    0
                Self::LmHead => "LmHead",
    149
    0
                Self::Sampling => "Sampling",
    150
            }
    151
    0
        }
    152
    153
        /// Try to parse a string into a BrickId.
    154
        #[allow(clippy::should_implement_trait)]
    155
    0
        pub fn from_str(s: &str) -> Option<Self> {
    156
    0
            match s {
    157
    0
                "RmsNorm" => Some(Self::RmsNorm),
    158
    0
                "LayerNorm" => Some(Self::LayerNorm),
    159
    0
                "QkvProjection" | "Qkv" => Some(Self::QkvProjection),
    160
    0
                "RopeEmbedding" | "Rope" | "RoPE" => Some(Self::RopeEmbedding),
    161
    0
                "AttentionScore" => Some(Self::AttentionScore),
    162
    0
                "AttentionSoftmax" | "Softmax" => Some(Self::AttentionSoftmax),
    163
    0
                "AttentionOutput" => Some(Self::AttentionOutput),
    164
    0
                "OutputProjection" | "OutProj" => Some(Self::OutputProjection),
    165
    0
                "GateProjection" | "Gate" => Some(Self::GateProjection),
    166
    0
                "UpProjection" | "Up" => Some(Self::UpProjection),
    167
    0
                "Activation" | "SiLU" | "GELU" | "ReLU" => Some(Self::Activation),
    168
    0
                "DownProjection" | "Down" => Some(Self::DownProjection),
    169
    0
                "Embedding" | "Embed" => Some(Self::Embedding),
    170
    0
                "LmHead" | "Head" => Some(Self::LmHead),
    171
    0
                "Sampling" | "Sample" => Some(Self::Sampling),
    172
    0
                _ => None,
    173
            }
    174
    0
        }
    175
    }
    176
    177
    impl fmt::Display for BrickId {
    178
    0
        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    179
    0
            write!(f, "{}", self.name())
    180
    0
        }
    181
    }
    182
    183
    /// Category for hierarchical aggregation of brick statistics.
    184
    ///
    185
    /// PAR-200: Groups related bricks for high-level performance analysis.
    186
    #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default)]
    187
    #[repr(u8)]
    188
    pub enum BrickCategory {
    189
        /// Normalization layers (RmsNorm, LayerNorm)
    190
        Norm = 0,
    191
        /// Attention mechanism (QKV, RoPE, scores, softmax, output)
    192
        Attention = 1,
    193
        /// Feed-forward network (gate, up, activation, down)
    194
        Ffn = 2,
    195
        /// Other operations (embedding, lm_head, sampling)
    196
        #[default]
    197
        Other = 3,
    198
    }
    199
    200
    impl BrickCategory {
    201
        /// Number of categories.
    202
        pub const COUNT: usize = 4;
    203
    204
        /// Get the string name of this category.
    205
        #[inline]
    206
    0
        pub const fn name(self) -> &'static str {
    207
    0
            match self {
    208
    0
                Self::Norm => "Norm",
    209
    0
                Self::Attention => "Attention",
    210
    0
                Self::Ffn => "FFN",
    211
    0
                Self::Other => "Other",
    212
            }
    213
    0
        }
    214
    }
    215
    216
    impl fmt::Display for BrickCategory {
    217
    0
        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    218
    0
            write!(f, "{}", self.name())
    219
    0
        }
    220
    }
    221
    222
    /// Synchronization mode for GPU profiling.
    223
    ///
    224
    /// PAR-200: Controls the trade-off between accuracy and overhead.
    225
    ///
    226
    /// # Performance Characteristics
    227
    ///
    228
    /// | Mode | Overhead | Accuracy | Use Case |
    229
    /// |------|----------|----------|----------|
    230
    /// | `Immediate` | ~200% | Exact per-kernel | Debugging |
    231
    /// | `PerLayer` | ~20% | Per-layer exact | Development |
    232
    /// | `Deferred` | ~5% | Approximate | Production |
    233
    /// | `None` | 0% | N/A | Disabled |
    234
    #[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
    235
    pub enum SyncMode {
    236
        /// Sync after each kernel (accurate but slow).
    237
        /// Best for debugging and detailed optimization.
    238
        Immediate,
    239
        /// Sync once per transformer layer.
    240
        /// Good balance for development.
    241
        PerLayer,
    242
        /// Sync once per forward pass (fast, approximate).
    243
        /// Best for production profiling.
    244
        #[default]
    245
        Deferred,
    246
        /// No synchronization (profiling disabled or CPU-only).
    247
        None,
    248
    }
    249
    250
    // ============================================================================
    251
    // PAR-201: Execution Path Graph Types
    252
    // ============================================================================
    253
    254
    /// Node ID in the execution graph.
    255
    #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
    256
    pub struct ExecutionNodeId(pub u32);
    257
    258
    /// Execution graph node types.
    259
    ///
    260
    /// PAR-201: Represents different levels of the execution hierarchy.
    261
    #[derive(Debug, Clone)]
    262
    pub enum ExecutionNode {
    263
        /// High-level brick (BrickId from v2)
    264
        Brick {
    265
            id: BrickId,
    266
            timing_ns: u64,
    267
            elements: u64,
    268
        },
    269
        /// GPU kernel launch
    270
        Kernel {
    271
            name: String,
    272
            /// FNV-1a hash of PTX source for identity
    273
            ptx_hash: u64,
    274
            /// Grid dimensions (blocks)
    275
            grid: (u32, u32, u32),
    276
            /// Block dimensions (threads)
    277
            block: (u32, u32, u32),
    278
            /// Shared memory bytes
    279
            shared_mem: u32,
    280
            /// Kernel execution time in nanoseconds (Phase 9: for CPA)
    281
            timing_ns: Option<u64>,
    282
            /// Arithmetic intensity (FLOPs/byte) for roofline analysis (Phase 9)
    283
            arithmetic_intensity: Option<f32>,
    284
            /// Achieved throughput in TFLOP/s (Phase 9)
    285
            achieved_tflops: Option<f32>,
    286
        },
    287
        /// Memory transfer operation (Phase 9: data movement topology)
    288
        Transfer {
    289
            /// Source location description
    290
            src: String,
    291
            /// Destination location description
    292
            dst: String,
    293
            /// Bytes transferred
    294
            bytes: u64,
    295
            /// Transfer direction
    296
            direction: TransferDirection,
    297
            /// Transfer time in nanoseconds
    298
            timing_ns: Option<u64>,
    299
        },
    300
        /// Rust function (from DWARF or manual annotation)
    301
        Function {
    302
            name: String,
    303
            file: Option<String>,
    304
            line: Option<u32>,
    305
        },
    306
        /// Transformer layer grouping
    307
        Layer { index: u32 },
    308
        /// Phase 11 (E.9.4): Async task metrics for poll efficiency tracking
    309
        AsyncTask {
    310
            /// Task name for identification
    311
            name: String,
    312
            /// Number of times poll() was called
    313
            poll_count: u64,
    314
            /// Number of times poll() returned Pending
    315
            yield_count: u64,
    316
            /// Total time spent in poll() (nanoseconds)
    317
            total_poll_ns: u64,
    318
        },
    319
    }
    320
    321
    impl ExecutionNode {
    322
        /// Get the display name of this node.
    323
    0
        pub fn name(&self) -> String {
    324
    0
            match self {
    325
    0
                Self::Brick { id, .. } => id.name().to_string(),
    326
    0
                Self::Kernel { name, .. } => name.clone(),
    327
    0
                Self::Function { name, .. } => name.clone(),
    328
    0
                Self::Layer { index } => format!("Layer{}", index),
    329
                Self::Transfer {
    330
    0
                    src,
    331
    0
                    dst,
    332
    0
                    direction,
    333
                    ..
    334
                } => {
    335
    0
                    let dir = match direction {
    336
    0
                        TransferDirection::H2D => "H2D",
    337
    0
                        TransferDirection::D2H => "D2H",
    338
    0
                        TransferDirection::D2D => "D2D",
    339
                    };
    340
    0
                    format!("{}:{}->{}", dir, src, dst)
    341
                }
    342
    0
                Self::AsyncTask { name, .. } => name.clone(),
    343
            }
    344
    0
        }
    345
    346
        /// Check if this is a kernel node.
    347
    0
        pub fn is_kernel(&self) -> bool {
    348
    0
            matches!(self, Self::Kernel { .. })
    349
    0
        }
    350
    351
        /// Check if this is a brick node.
    352
    0
        pub fn is_brick(&self) -> bool {
    353
    0
            matches!(self, Self::Brick { .. })
    354
    0
        }
    355
    356
        /// Check if this is a transfer node.
    357
    0
        pub fn is_transfer(&self) -> bool {
    358
    0
            matches!(self, Self::Transfer { .. })
    359
    0
        }
    360
    361
        /// Get timing if available (bricks, kernels, and transfers).
    362
    0
        pub fn timing_ns(&self) -> Option<u64> {
    363
    0
            match self {
    364
    0
                Self::Brick { timing_ns, .. } => Some(*timing_ns),
    365
    0
                Self::Kernel { timing_ns, .. } => *timing_ns,
    366
    0
                Self::Transfer { timing_ns, .. } => *timing_ns,
    367
    0
                _ => None,
    368
            }
    369
    0
        }
    370
    371
        /// Get PTX hash if available (kernels only).
    372
    0
        pub fn ptx_hash(&self) -> Option<u64> {
    373
    0
            match self {
    374
    0
                Self::Kernel { ptx_hash, .. } => Some(*ptx_hash),
    375
    0
                _ => None,
    376
            }
    377
    0
        }
    378
    379
        /// Get arithmetic intensity if available (kernels only, Phase 9).
    380
    0
        pub fn arithmetic_intensity(&self) -> Option<f32> {
    381
    0
            match self {
    382
                Self::Kernel {
    383
    0
                    arithmetic_intensity,
    384
                    ..
    385
    0
                } => *arithmetic_intensity,
    386
    0
                _ => None,
    387
            }
    388
    0
        }
    389
    390
        /// Get achieved TFLOP/s if available (kernels only, Phase 9).
    391
    0
        pub fn achieved_tflops(&self) -> Option<f32> {
    392
    0
            match self {
    393
                Self::Kernel {
    394
    0
                    achieved_tflops, ..
    395
    0
                } => *achieved_tflops,
    396
    0
                _ => None,
    397
            }
    398
    0
        }
    399
    400
        /// Get transfer bytes if available (transfers only, Phase 9).
    401
    0
        pub fn transfer_bytes(&self) -> Option<u64> {
    402
    0
            match self {
    403
    0
                Self::Transfer { bytes, .. } => Some(*bytes),
    404
    0
                _ => None,
    405
            }
    406
    0
        }
    407
    }
    408
    409
    /// Edge types in execution graph.
    410
    ///
    411
    /// PAR-201: Describes relationships between execution nodes.
    412
    /// Phase 9 (E.7.12): Added DependsOn and Transfer for advanced profiling.
    413
    #[derive(Debug, Clone, PartialEq)]
    414
    pub enum EdgeType {
    415
        /// Function calls function
    416
        Calls,
    417
        /// Brick contains sub-operations
    418
        Contains,
    419
        /// Function launches GPU kernel
    420
        Launches,
    421
        /// Temporal sequence (A happens before B)
    422
        Sequence,
    423
        /// Dependency edge for critical path analysis (CUDA events, stream sync)
    424
        /// PAR-201 Phase 9: CPA requires tracking true dependencies vs containment
    425
        DependsOn,
    426
        /// Data transfer edge with byte count (H2D/D2H/D2D)
    427
        /// PAR-201 Phase 9: For data movement topology and ping-pong detection
    428
        Transfer {
    429
            /// Bytes transferred
    430
            bytes: u64,
    431
            /// Transfer direction
    432
            direction: TransferDirection,
    433
        },
    434
    }
    435
    436
    /// Direction of memory transfer.
    437
    ///
    438
    /// PAR-201 Phase 9: Used with EdgeType::Transfer for data movement analysis.
    439
    #[derive(Debug, Clone, Copy, PartialEq, Eq)]
    440
    pub enum TransferDirection {
    441
        /// Host to Device
    442
        H2D,
    443
        /// Device to Host
    444
        D2H,
    445
        /// Device to Device
    446
        D2D,
    447
    }
    448
    449
    /// An edge in the execution graph.
    450
    #[derive(Debug, Clone)]
    451
    pub struct ExecutionEdge {
    452
        /// Source node ID
    453
        pub src: ExecutionNodeId,
    454
        /// Destination node ID
    455
        pub dst: ExecutionNodeId,
    456
        /// Edge type
    457
        pub edge_type: EdgeType,
    458
        /// Optional weight (e.g., call count, timing)
    459
        pub weight: f32,
    460
    }
    461
    462
    /// Execution path graph for tracking brick → kernel → PTX relationships.
    463
    ///
    464
    /// PAR-201: Captures the full execution hierarchy for profiling analysis.
    465
    ///
    466
    /// # Example
    467
    ///
    468
    /// ```rust,ignore
    469
    /// use trueno::brick::{ExecutionGraph, ExecutionNode, EdgeType};
    470
    ///
    471
    /// let mut graph = ExecutionGraph::new();
    472
    ///
    473
    /// // Add layer scope
    474
    /// let layer_id = graph.add_node(ExecutionNode::Layer { index: 0 });
    475
    ///
    476
    /// // Add brick within layer
    477
    /// let brick_id = graph.add_node(ExecutionNode::Brick {
    478
    ///     id: BrickId::QkvProjection,
    479
    ///     timing_ns: 1000,
    480
    ///     elements: 4096,
    481
    /// });
    482
    /// graph.add_edge(layer_id, brick_id, EdgeType::Contains);
    483
    ///
    484
    /// // Add kernel launched by brick
    485
    /// let kernel_id = graph.add_node(ExecutionNode::Kernel {
    486
    ///     name: "batched_q4k_gemv".into(),
    487
    ///     ptx_hash: 0x7a3b1c2d,
    488
    ///     grid: (32, 1, 1),
    489
    ///     block: (256, 1, 1),
    490
    ///     shared_mem: 4096,
    491
    /// });
    492
    /// graph.add_edge(brick_id, kernel_id, EdgeType::Launches);
    493
    ///
    494
    /// // Export to trueno-graph for analysis
    495
    /// #[cfg(feature = "execution-graph")]
    496
    /// let csr = graph.to_csr();
    497
    /// ```
    498
    #[derive(Debug, Default)]
    499
    pub struct ExecutionGraph {
    500
        /// All nodes in the graph
    501
        nodes: Vec<ExecutionNode>,
    502
        /// All edges in the graph
    503
        edges: Vec<ExecutionEdge>,
    504
        /// Scope stack for hierarchical recording
    505
        scope_stack: Vec<ExecutionNodeId>,
    506
        /// Node name → ID mapping for fast lookup
    507
        name_to_id: HashMap<String, ExecutionNodeId>,
    508
    }
    509
    510
    impl ExecutionGraph {
    511
        /// Create a new empty execution graph.
    512
    0
        pub fn new() -> Self {
    513
    0
            Self::default()
    514
    0
        }
    515
    516
        /// Add a node to the graph, returning its ID.
    517
    0
        pub fn add_node(&mut self, node: ExecutionNode) -> ExecutionNodeId {
    518
    0
            let id = ExecutionNodeId(self.nodes.len() as u32);
    519
    0
            let name = node.name();
    520
    0
            self.name_to_id.insert(name, id);
    521
    0
            self.nodes.push(node);
    522
    0
            id
    523
    0
        }
    524
    525
        /// Add an edge between two nodes.
    526
    0
        pub fn add_edge(&mut self, src: ExecutionNodeId, dst: ExecutionNodeId, edge_type: EdgeType) {
    527
    0
            self.edges.push(ExecutionEdge {
    528
    0
                src,
    529
    0
                dst,
    530
    0
                edge_type,
    531
    0
                weight: 1.0,
    532
    0
            });
    533
    0
        }
    534
    535
        /// Add an edge with a weight.
    536
    0
        pub fn add_weighted_edge(
    537
    0
            &mut self,
    538
    0
            src: ExecutionNodeId,
    539
    0
            dst: ExecutionNodeId,
    540
    0
            edge_type: EdgeType,
    541
    0
            weight: f32,
    542
    0
        ) {
    543
    0
            self.edges.push(ExecutionEdge {
    544
    0
                src,
    545
    0
                dst,
    546
    0
                edge_type,
    547
    0
                weight,
    548
    0
            });
    549
    0
        }
    550
    551
        /// Push a scope for hierarchical recording.
    552
        /// All subsequent nodes will be children of this scope.
    553
    0
        pub fn push_scope(&mut self, node: ExecutionNode) -> ExecutionNodeId {
    554
    0
            let id = self.add_node(node);
    555
    0
            if let Some(&parent) = self.scope_stack.last() {
    556
    0
                self.add_edge(parent, id, EdgeType::Contains);
    557
    0
            }
    558
    0
            self.scope_stack.push(id);
    559
    0
            id
    560
    0
        }
    561
    562
        /// Pop the current scope.
    563
    0
        pub fn pop_scope(&mut self) -> Option<ExecutionNodeId> {
    564
    0
            self.scope_stack.pop()
    565
    0
        }
    566
    567
        /// Get the current scope (if any).
    568
    0
        pub fn current_scope(&self) -> Option<ExecutionNodeId> {
    569
    0
            self.scope_stack.last().copied()
    570
    0
        }
    571
    572
        /// Add a node under the current scope.
    573
    0
        pub fn add_node_in_scope(&mut self, node: ExecutionNode) -> ExecutionNodeId {
    574
    0
            let id = self.add_node(node);
    575
    0
            if let Some(&parent) = self.scope_stack.last() {
    576
    0
                self.add_edge(parent, id, EdgeType::Contains);
    577
    0
            }
    578
    0
            id
    579
    0
        }
    580
    581
        /// Record a kernel launch under the current scope.
    582
    0
        pub fn record_kernel_launch(
    583
    0
            &mut self,
    584
    0
            name: &str,
    585
    0
            ptx_hash: u64,
    586
    0
            grid: (u32, u32, u32),
    587
    0
            block: (u32, u32, u32),
    588
    0
            shared_mem: u32,
    589
    0
        ) -> ExecutionNodeId {
    590
    0
            let kernel = ExecutionNode::Kernel {
    591
    0
                name: name.to_string(),
    592
    0
                ptx_hash,
    593
    0
                grid,
    594
    0
                block,
    595
    0
                shared_mem,
    596
    0
                timing_ns: None,
    597
    0
                arithmetic_intensity: None,
    598
    0
                achieved_tflops: None,
    599
    0
            };
    600
    0
            let kernel_id = self.add_node(kernel);
    601
    602
            // Link from current scope with Launches edge
    603
    0
            if let Some(&parent) = self.scope_stack.last() {
    604
    0
                self.add_edge(parent, kernel_id, EdgeType::Launches);
    605
    0
            }
    606
    607
    0
            kernel_id
    608
    0
        }
    609
    610
        /// Record a kernel launch with roofline metrics (Phase 9).
    611
        #[allow(clippy::too_many_arguments)]
    612
    0
        pub fn record_kernel_launch_with_metrics(
    613
    0
            &mut self,
    614
    0
            name: &str,
    615
    0
            ptx_hash: u64,
    616
    0
            grid: (u32, u32, u32),
    617
    0
            block: (u32, u32, u32),
    618
    0
            shared_mem: u32,
    619
    0
            timing_ns: u64,
    620
    0
            arithmetic_intensity: f32,
    621
    0
            achieved_tflops: f32,
    622
    0
        ) -> ExecutionNodeId {
    623
    0
            let kernel = ExecutionNode::Kernel {
    624
    0
                name: name.to_string(),
    625
    0
                ptx_hash,
    626
    0
                grid,
    627
    0
                block,
    628
    0
                shared_mem,
    629
    0
                timing_ns: Some(timing_ns),
    630
    0
                arithmetic_intensity: Some(arithmetic_intensity),
    631
    0
                achieved_tflops: Some(achieved_tflops),
    632
    0
            };
    633
    0
            let kernel_id = self.add_node(kernel);
    634
    635
    0
            if let Some(&parent) = self.scope_stack.last() {
    636
    0
                self.add_edge(parent, kernel_id, EdgeType::Launches);
    637
    0
            }
    638
    639
    0
            kernel_id
    640
    0
        }
    641
    642
        /// Record a memory transfer (Phase 9: data movement topology).
    643
    0
        pub fn record_transfer(
    644
    0
            &mut self,
    645
    0
            src: &str,
    646
    0
            dst: &str,
    647
    0
            bytes: u64,
    648
    0
            direction: TransferDirection,
    649
    0
            timing_ns: Option<u64>,
    650
    0
        ) -> ExecutionNodeId {
    651
    0
            let transfer = ExecutionNode::Transfer {
    652
    0
                src: src.to_string(),
    653
    0
                dst: dst.to_string(),
    654
    0
                bytes,
    655
    0
                direction,
    656
    0
                timing_ns,
    657
    0
            };
    658
    0
            let transfer_id = self.add_node(transfer);
    659
    660
    0
            if let Some(&parent) = self.scope_stack.last() {
    661
    0
                self.add_edge(parent, transfer_id, EdgeType::Contains);
    662
    0
            }
    663
    664
    0
            transfer_id
    665
    0
        }
    666
    667
        /// Add a dependency edge for critical path analysis (Phase 9).
    668
    0
        pub fn add_dependency(&mut self, from: ExecutionNodeId, to: ExecutionNodeId) {
    669
    0
            self.add_edge(from, to, EdgeType::DependsOn);
    670
    0
        }
    671
    672
        /// Get a node by ID.
    673
    0
        pub fn node(&self, id: ExecutionNodeId) -> Option<&ExecutionNode> {
    674
    0
            self.nodes.get(id.0 as usize)
    675
    0
        }
    676
    677
        /// Get a node by name.
    678
    0
        pub fn node_by_name(&self, name: &str) -> Option<(ExecutionNodeId, &ExecutionNode)> {
    679
    0
            self.name_to_id
    680
    0
                .get(name)
    681
    0
                .and_then(|&id| self.nodes.get(id.0 as usize).map(|n| (id, n)))
    682
    0
        }
    683
    684
        /// Get all nodes.
    685
    0
        pub fn nodes(&self) -> &[ExecutionNode] {
    686
    0
            &self.nodes
    687
    0
        }
    688
    689
        /// Get all edges.
    690
    0
        pub fn edges(&self) -> &[ExecutionEdge] {
    691
    0
            &self.edges
    692
    0
        }
    693
    694
        /// Number of nodes.
    695
    0
        pub fn num_nodes(&self) -> usize {
    696
    0
            self.nodes.len()
    697
    0
        }
    698
    699
        /// Number of edges.
    700
    0
        pub fn num_edges(&self) -> usize {
    701
    0
            self.edges.len()
    702
    0
        }
    703
    704
        /// Get outgoing edges for a node.
    705
    0
        pub fn outgoing_edges(&self, node: ExecutionNodeId) -> impl Iterator<Item = &ExecutionEdge> {
    706
    0
            self.edges.iter().filter(move |e| e.src == node)
    707
    0
        }
    708
    709
        /// Get incoming edges for a node.
    710
    0
        pub fn incoming_edges(&self, node: ExecutionNodeId) -> impl Iterator<Item = &ExecutionEdge> {
    711
    0
            self.edges.iter().filter(move |e| e.dst == node)
    712
    0
        }
    713
    714
        /// Find all kernel nodes.
    715
    0
        pub fn kernel_nodes(&self) -> impl Iterator<Item = (ExecutionNodeId, &ExecutionNode)> {
    716
    0
            self.nodes
    717
    0
                .iter()
    718
    0
                .enumerate()
    719
    0
                .filter(|(_, n)| n.is_kernel())
    720
    0
                .map(|(i, n)| (ExecutionNodeId(i as u32), n))
    721
    0
        }
    722
    723
        /// Find the slowest kernel (by parent brick timing).
    724
    0
        pub fn slowest_kernel(&self) -> Option<(ExecutionNodeId, &ExecutionNode, u64)> {
    725
    0
            let mut slowest: Option<(ExecutionNodeId, &ExecutionNode, u64)> = None;
    726
    727
    0
            for (id, node) in self.nodes.iter().enumerate() {
    728
    0
                if let ExecutionNode::Brick { timing_ns, .. } = node {
    729
                    // Check if this brick has kernel children
    730
    0
                    let node_id = ExecutionNodeId(id as u32);
    731
    0
                    let has_kernel = self
    732
    0
                        .outgoing_edges(node_id)
    733
    0
                        .any(|e| e.edge_type == EdgeType::Launches);
    734
    735
    0
                    if has_kernel {
    736
    0
                        match &slowest {
    737
    0
                            None => slowest = Some((node_id, node, *timing_ns)),
    738
    0
                            Some((_, _, t)) if *timing_ns > *t => {
    739
    0
                                slowest = Some((node_id, node, *timing_ns))
    740
                            }
    741
    0
                            _ => {}
    742
                        }
    743
    0
                    }
    744
    0
                }
    745
            }
    746
    747
    0
            slowest
    748
    0
        }
    749
    750
        /// Export to DOT format for Graphviz visualization.
    751
    0
        pub fn to_dot(&self) -> String {
    752
    0
            let mut dot = String::from("digraph ExecutionGraph {\n");
    753
    0
            dot.push_str("  rankdir=TB;\n");
    754
    0
            dot.push_str("  node [shape=box];\n\n");
    755
    756
            // Add nodes with styling based on type
    757
    0
            for (i, node) in self.nodes.iter().enumerate() {
    758
    0
                let (label, style) = match node {
    759
    0
                    ExecutionNode::Layer { index } => {
    760
    0
                        (format!("Layer {}", index), "style=filled,fillcolor=lightblue")
    761
                    }
    762
    0
                    ExecutionNode::Brick { id, timing_ns, .. } => (
    763
    0
                        format!("{}\\n{:.1}µs", id.name(), *timing_ns as f64 / 1000.0),
    764
    0
                        "style=filled,fillcolor=lightgreen",
    765
    0
                    ),
    766
                    ExecutionNode::Kernel {
    767
    0
                        name, grid, block, ..
    768
    0
                    } => (
    769
    0
                        format!("{}\\n<<<{},{},{}>>>", name, grid.0, block.0, block.1),
    770
    0
                        "style=filled,fillcolor=lightyellow",
    771
    0
                    ),
    772
    0
                    ExecutionNode::Function { name, file, line } => {
    773
    0
                        let loc = match (file, line) {
    774
    0
                            (Some(f), Some(l)) => format!("\\n{}:{}", f, l),
    775
    0
                            _ => String::new(),
    776
                        };
    777
    0
                        (
    778
    0
                            format!("{}{}", name, loc),
    779
    0
                            "style=filled,fillcolor=lightgray",
    780
    0
                        )
    781
                    }
    782
                    ExecutionNode::Transfer {
    783
    0
                        src,
    784
    0
                        dst,
    785
    0
                        bytes,
    786
    0
                        direction,
    787
                        ..
    788
                    } => {
    789
    0
                        let dir = match direction {
    790
    0
                            TransferDirection::H2D => "H2D",
    791
    0
                            TransferDirection::D2H => "D2H",
    792
    0
                            TransferDirection::D2D => "D2D",
    793
                        };
    794
    0
                        (
    795
    0
                            format!("{}\\n{}->{}\\n{:.1}MB", dir, src, dst, *bytes as f64 / 1e6),
    796
    0
                            "style=filled,fillcolor=lightsalmon",
    797
    0
                        )
    798
                    }
    799
                    ExecutionNode::AsyncTask {
    800
    0
                        name,
    801
    0
                        poll_count,
    802
    0
                        yield_count,
    803
    0
                        total_poll_ns,
    804
                    } => {
    805
    0
                        let efficiency = if *poll_count > 0 {
    806
    0
                            100.0 / *poll_count as f64
    807
                        } else {
    808
    0
                            0.0
    809
                        };
    810
    0
                        (
    811
    0
                            format!(
    812
    0
                                "{}\\npolls:{} yields:{}\\n{:.1}µs ({:.0}%)",
    813
    0
                                name,
    814
    0
                                poll_count,
    815
    0
                                yield_count,
    816
    0
                                *total_poll_ns as f64 / 1000.0,
    817
    0
                                efficiency
    818
    0
                            ),
    819
    0
                            "style=filled,fillcolor=lightcyan",
    820
    0
                        )
    821
                    }
    822
                };
    823
    0
                dot.push_str(&format!("  n{} [label=\"{}\",{}];\n", i, label, style));
    824
            }
    825
    826
    0
            dot.push('\n');
    827
    828
            // Add edges with styling based on type
    829
    0
            for edge in &self.edges {
    830
    0
                let style = match edge.edge_type {
    831
    0
                    EdgeType::Calls => "style=solid",
    832
    0
                    EdgeType::Contains => "style=dashed",
    833
    0
                    EdgeType::Launches => "style=bold,color=red",
    834
    0
                    EdgeType::Sequence => "style=dotted",
    835
    0
                    EdgeType::DependsOn => "style=solid,color=blue",
    836
    0
                    EdgeType::Transfer { .. } => "style=bold,color=orange",
    837
                };
    838
    0
                dot.push_str(&format!(
    839
    0
                    "  n{} -> n{} [{}];\n",
    840
    0
                    edge.src.0, edge.dst.0, style
    841
    0
                ));
    842
            }
    843
    844
    0
            dot.push_str("}\n");
    845
    0
            dot
    846
    0
        }
    847
    848
        /// Export to trueno-graph CsrGraph format.
    849
        #[cfg(feature = "execution-graph")]
    850
        pub fn to_csr(&self) -> trueno_graph::CsrGraph {
    851
            use trueno_graph::{CsrGraph, NodeId};
    852
    853
            let edges: Vec<(NodeId, NodeId, f32)> = self
    854
                .edges
    855
                .iter()
    856
                .map(|e| (NodeId(e.src.0), NodeId(e.dst.0), e.weight))
    857
                .collect();
    858
    859
            let mut graph = CsrGraph::from_edge_list(&edges).unwrap_or_default();
    860
    861
            // Set node names for querying
    862
            for (i, node) in self.nodes.iter().enumerate() {
    863
                graph.set_node_name(NodeId(i as u32), node.name());
    864
            }
    865
    866
            graph
    867
        }
    868
    869
        /// Convert to presentar-terminal TreeNode for TUI visualization.
    870
        ///
    871
        /// PAR-201: Renders the execution graph as a collapsible tree in the terminal.
    872
        #[cfg(feature = "presentar-tui")]
    873
        pub fn to_tree_node(&self) -> presentar_terminal::TreeNode {
    874
            use presentar_terminal::{Color, TreeNode};
    875
    876
            // Color scheme for node types
    877
            let layer_color = Color::new(0.4, 0.6, 1.0, 1.0); // Light blue
    878
            let brick_color = Color::new(0.4, 0.8, 0.4, 1.0); // Light green
    879
            let kernel_color = Color::new(1.0, 0.8, 0.3, 1.0); // Yellow/orange
    880
            let func_color = Color::new(0.7, 0.7, 0.7, 1.0); // Light gray
    881
    882
            // Build child map: parent -> [children]
    883
            let mut children_map: HashMap<u32, Vec<u32>> = HashMap::new();
    884
            let mut has_parent: std::collections::HashSet<u32> = std::collections::HashSet::new();
    885
    886
            for edge in &self.edges {
    887
                if edge.edge_type == EdgeType::Contains || edge.edge_type == EdgeType::Launches {
    888
                    children_map
    889
                        .entry(edge.src.0)
    890
                        .or_default()
    891
                        .push(edge.dst.0);
    892
                    has_parent.insert(edge.dst.0);
    893
                }
    894
            }
    895
    896
            // Find root nodes (nodes with no parent)
    897
            let root_ids: Vec<u32> = (0..self.nodes.len() as u32)
    898
                .filter(|id| !has_parent.contains(id))
    899
                .collect();
    900
    901
            // Recursive function to build TreeNode
    902
            fn build_node(
    903
                graph: &ExecutionGraph,
    904
                id: u32,
    905
                children_map: &HashMap<u32, Vec<u32>>,
    906
                layer_color: Color,
    907
                brick_color: Color,
    908
                kernel_color: Color,
    909
                func_color: Color,
    910
            ) -> TreeNode {
    911
                let node = &graph.nodes[id as usize];
    912
                let (label, info, color) = match node {
    913
                    ExecutionNode::Layer { index } => {
    914
                        (format!("Layer {}", index), None, layer_color)
    915
                    }
    916
                    ExecutionNode::Brick {
    917
                        id: brick_id,
    918
                        timing_ns,
    919
                        elements,
    920
                    } => (
    921
                        brick_id.name().to_string(),
    922
                        Some(format!(
    923
                            "{:.1}µs ({} elem)",
    924
                            *timing_ns as f64 / 1000.0,
    925
                            elements
    926
                        )),
    927
                        brick_color,
    928
                    ),
    929
                    ExecutionNode::Kernel {
    930
                        name,
    931
                        grid,
    932
                        block,
    933
                        shared_mem,
    934
                        ..
    935
                    } => (
    936
                        name.clone(),
    937
                        Some(format!(
    938
                            "<<<{},{},{}>>> smem={}B",
    939
                            grid.0, block.0, block.1, shared_mem
    940
                        )),
    941
                        kernel_color,
    942
                    ),
    943
                    ExecutionNode::Function { name, file, line } => {
    944
                        let loc = match (file, line) {
    945
                            (Some(f), Some(l)) => format!(" ({}:{})", f, l),
    946
                            _ => String::new(),
    947
                        };
    948
                        (format!("{}{}", name, loc), None, func_color)
    949
                    }
    950
                    ExecutionNode::Transfer {
    951
                        src,
    952
                        dst,
    953
                        bytes,
    954
                        direction,
    955
                        timing_ns,
    956
                    } => {
    957
                        let timing_str = timing_ns
    958
                            .map(|ns| format!(" {:.1}µs", ns as f64 / 1000.0))
    959
                            .unwrap_or_default();
    960
                        (
    961
                            format!("{:?}: {} → {}", direction, src, dst),
    962
                            Some(format!("{}B{}", bytes, timing_str)),
    963
                            Color::Magenta, // Transfer color
    964
                        )
    965
                    }
    966
                    ExecutionNode::AsyncTask {
    967
                        name,
    968
                        poll_count,
    969
                        yield_count,
    970
                        total_poll_ns,
    971
                    } => {
    972
                        let efficiency = if *poll_count > 0 {
    973
                            100.0 / *poll_count as f64
    974
                        } else {
    975
                            0.0
    976
                        };
    977
                        (
    978
                            name.clone(),
    979
                            Some(format!(
    980
                                "polls:{} yields:{} {:.1}µs ({:.0}% eff)",
    981
                                poll_count,
    982
                                yield_count,
    983
                                *total_poll_ns as f64 / 1000.0,
    984
                                efficiency
    985
                            )),
    986
                            Color::Cyan, // Async task color
    987
                        )
    988
                    }
    989
                };
    990
    991
                let mut tree_node = TreeNode::new(id as u64, label).with_color(color);
    992
                if let Some(info_str) = info {
    993
                    tree_node = tree_node.with_info(info_str);
    994
                }
    995
    996
                // Add children
    997
                if let Some(child_ids) = children_map.get(&id) {
    998
                    for &child_id in child_ids {
    999
                        let child = build_node(
    1000
                            graph,
    1001
                            child_id,
    1002
                            children_map,
    1003
                            layer_color,
    1004
                            brick_color,
    1005
                            kernel_color,
    1006
                            func_color,
    1007
                        );
    1008
                        tree_node = tree_node.with_child(child);
    1009
                    }
    1010
                }
    1011
    1012
                tree_node
    1013
            }
    1014
    1015
            // Build root node
    1016
            if root_ids.is_empty() {
    1017
                TreeNode::new(0, "Empty Graph")
    1018
            } else if root_ids.len() == 1 {
    1019
                build_node(
    1020
                    self,
    1021
                    root_ids[0],
    1022
                    &children_map,
    1023
                    layer_color,
    1024
                    brick_color,
    1025
                    kernel_color,
    1026
                    func_color,
    1027
                )
    1028
            } else {
    1029
                // Multiple roots: wrap in a synthetic root
    1030
                let mut root =
    1031
                    TreeNode::new(u64::MAX, "Execution Graph").with_color(Color::new(0.9, 0.9, 0.9, 1.0));
    1032
                for &root_id in &root_ids {
    1033
                    let child = build_node(
    1034
                        self,
    1035
                        root_id,
    1036
                        &children_map,
    1037
                        layer_color,
    1038
                        brick_color,
    1039
                        kernel_color,
    1040
                        func_color,
    1041
                    );
    1042
                    root = root.with_child(child);
    1043
                }
    1044
                root
    1045
            }
    1046
        }
    1047
    1048
        /// Render graph to ASCII tree string (headless mode for testing/automation).
    1049
        ///
    1050
        /// PAR-201: Zero-dependency tree visualization for CI/CD, logging, and snapshot tests.
    1051
        #[must_use]
    1052
    0
        pub fn to_ascii_tree(&self) -> String {
    1053
            // Build child map: parent -> [children]
    1054
    0
            let mut children_map: HashMap<u32, Vec<u32>> = HashMap::new();
    1055
    0
            let mut has_parent: std::collections::HashSet<u32> = std::collections::HashSet::new();
    1056
    1057
    0
            for edge in &self.edges {
    1058
    0
                if edge.edge_type == EdgeType::Contains || edge.edge_type == EdgeType::Launches {
    1059
    0
                    children_map
    1060
    0
                        .entry(edge.src.0)
    1061
    0
                        .or_default()
    1062
    0
                        .push(edge.dst.0);
    1063
    0
                    has_parent.insert(edge.dst.0);
    1064
    0
                }
    1065
            }
    1066
    1067
            // Find root nodes (nodes with no parent)
    1068
    0
            let root_ids: Vec<u32> = (0..self.nodes.len() as u32)
    1069
    0
                .filter(|id| !has_parent.contains(id))
    1070
    0
                .collect();
    1071
    1072
            // Recursive function to build tree string
    1073
    0
            fn build_tree(
    1074
    0
                graph: &ExecutionGraph,
    1075
    0
                id: u32,
    1076
    0
                children_map: &HashMap<u32, Vec<u32>>,
    1077
    0
                prefix: &str,
    1078
    0
                connector: &str,
    1079
    0
                output: &mut String,
    1080
    0
            ) {
    1081
    0
                let node = &graph.nodes[id as usize];
    1082
    0
                let (label, info) = match node {
    1083
    0
                    ExecutionNode::Layer { index } => (format!("Layer {}", index), String::new()),
    1084
                    ExecutionNode::Brick {
    1085
    0
                        id: brick_id,
    1086
    0
                        timing_ns,
    1087
    0
                        elements,
    1088
    0
                    } => (
    1089
    0
                        brick_id.name().to_string(),
    1090
    0
                        format!("  {:.1}µs ({} elem)", *timing_ns as f64 / 1000.0, elements),
    1091
    0
                    ),
    1092
                    ExecutionNode::Kernel {
    1093
    0
                        name,
    1094
    0
                        grid,
    1095
    0
                        block,
    1096
    0
                        shared_mem,
    1097
                        ..
    1098
    0
                    } => (
    1099
    0
                        name.clone(),
    1100
    0
                        format!(
    1101
    0
                            "  <<<{},{},{}>>> smem={}B",
    1102
    0
                            grid.0, block.0, block.1, shared_mem
    1103
    0
                        ),
    1104
    0
                    ),
    1105
    0
                    ExecutionNode::Function { name, file, line } => {
    1106
    0
                        let loc = match (file, line) {
    1107
    0
                            (Some(f), Some(l)) => format!(" ({}:{})", f, l),
    1108
    0
                            _ => String::new(),
    1109
                        };
    1110
    0
                        (format!("{}{}", name, loc), String::new())
    1111
                    }
    1112
                    ExecutionNode::Transfer {
    1113
    0
                        src,
    1114
    0
                        dst,
    1115
    0
                        bytes,
    1116
    0
                        direction,
    1117
    0
                        timing_ns,
    1118
                    } => {
    1119
    0
                        let timing_str = timing_ns
    1120
    0
                            .map(|ns| format!(" {:.1}µs", ns as f64 / 1000.0))
    1121
    0
                            .unwrap_or_default();
    1122
    0
                        (
    1123
    0
                            format!("{:?}: {} → {}", direction, src, dst),
    1124
    0
                            format!("  {}B{}", bytes, timing_str),
    1125
    0
                        )
    1126
                    }
    1127
                    ExecutionNode::AsyncTask {
    1128
    0
                        name,
    1129
    0
                        poll_count,
    1130
    0
                        yield_count,
    1131
    0
                        total_poll_ns,
    1132
                    } => {
    1133
    0
                        let efficiency = if *poll_count > 0 {
    1134
    0
                            100.0 / *poll_count as f64
    1135
                        } else {
    1136
    0
                            0.0
    1137
                        };
    1138
    0
                        (
    1139
    0
                            name.clone(),
    1140
    0
                            format!(
    1141
    0
                                "  polls:{} yields:{} {:.1}µs ({:.0}% eff)",
    1142
    0
                                poll_count,
    1143
    0
                                yield_count,
    1144
    0
                                *total_poll_ns as f64 / 1000.0,
    1145
    0
                                efficiency
    1146
    0
                            ),
    1147
    0
                        )
    1148
                    }
    1149
                };
    1150
    1151
    0
                output.push_str(&format!("{}{}{}{}\n", prefix, connector, label, info));
    1152
    1153
    0
                if let Some(child_ids) = children_map.get(&id) {
    1154
    0
                    let child_count = child_ids.len();
    1155
    0
                    for (i, &child_id) in child_ids.iter().enumerate() {
    1156
    0
                        let is_last = i == child_count - 1;
    1157
    0
                        let new_connector = if is_last { "└── " } else { "├── " };
    1158
    0
                        let new_prefix = if connector.is_empty() {
    1159
    0
                            prefix.to_string()
    1160
    0
                        } else if connector == "└── " {
    1161
    0
                            format!("{}    ", prefix)
    1162
                        } else {
    1163
    0
                            format!("{}│   ", prefix)
    1164
                        };
    1165
    0
                        build_tree(graph, child_id, children_map, &new_prefix, new_connector, output);
    1166
                    }
    1167
    0
                }
    1168
    0
            }
    1169
    1170
    0
            let mut output = String::new();
    1171
    1172
    0
            if root_ids.is_empty() {
    1173
    0
                output.push_str("(empty graph)\n");
    1174
    0
            } else if root_ids.len() == 1 {
    1175
    0
                build_tree(self, root_ids[0], &children_map, "", "", &mut output);
    1176
    0
            } else {
    1177
                // Multiple roots: add synthetic root
    1178
    0
                output.push_str("Execution Graph\n");
    1179
    0
                let root_count = root_ids.len();
    1180
    0
                for (i, &root_id) in root_ids.iter().enumerate() {
    1181
    0
                    let is_last = i == root_count - 1;
    1182
    0
                    let connector = if is_last { "└── " } else { "├── " };
    1183
    0
                    build_tree(self, root_id, &children_map, "", connector, &mut output);
    1184
                }
    1185
            }
    1186
    1187
            // Remove trailing newline for cleaner output
    1188
    0
            if output.ends_with('\n') {
    1189
    0
                output.pop();
    1190
    0
            }
    1191
    0
            output
    1192
    0
        }
    1193
    1194
        // ========================
    1195
        // Phase 9: Critical Path Analysis (CPA)
    1196
        // ========================
    1197
    1198
        /// Get timing for a node (ns). Returns 0 for non-timed nodes.
    1199
    0
        fn node_timing_ns(&self, id: ExecutionNodeId) -> u64 {
    1200
    0
            match &self.nodes[id.0 as usize] {
    1201
    0
                ExecutionNode::Brick { timing_ns, .. } => *timing_ns,
    1202
    0
                ExecutionNode::Kernel { timing_ns, .. } => timing_ns.unwrap_or(0),
    1203
    0
                ExecutionNode::Transfer { timing_ns, .. } => timing_ns.unwrap_or(0),
    1204
    0
                _ => 0,
    1205
            }
    1206
    0
        }
    1207
    1208
        /// Compute critical path through execution graph using longest-path algorithm.
    1209
        ///
    1210
        /// Returns (critical_path_nodes, total_time_ns). The critical path represents
    1211
        /// the longest chain of dependencies that determines total execution time.
    1212
        ///
    1213
        /// Reference: Graham et al. (1979) "Scheduling Algorithms for Multi-Processor Systems"
    1214
    0
        pub fn critical_path(&self) -> (Vec<ExecutionNodeId>, u64) {
    1215
    0
            if self.nodes.is_empty() {
    1216
    0
                return (vec![], 0);
    1217
    0
            }
    1218
    1219
            // Build adjacency list for DependsOn and Sequence edges
    1220
    0
            let mut adj: Vec<Vec<(u32, u64)>> = vec![vec![]; self.nodes.len()];
    1221
    0
            for edge in &self.edges {
    1222
    0
                match &edge.edge_type {
    1223
    0
                    EdgeType::DependsOn | EdgeType::Sequence => {
    1224
    0
                        let weight = self.node_timing_ns(edge.dst);
    1225
    0
                        adj[edge.src.0 as usize].push((edge.dst.0, weight));
    1226
    0
                    }
    1227
    0
                    EdgeType::Contains | EdgeType::Calls | EdgeType::Launches => {
    1228
    0
                        // Hierarchical edges: children contribute to parent time
    1229
    0
                        let weight = self.node_timing_ns(edge.dst);
    1230
    0
                        adj[edge.src.0 as usize].push((edge.dst.0, weight));
    1231
    0
                    }
    1232
    0
                    EdgeType::Transfer { .. } => {
    1233
    0
                        // Transfer edges carry their own timing
    1234
    0
                        let weight = self.node_timing_ns(edge.dst);
    1235
    0
                        adj[edge.src.0 as usize].push((edge.dst.0, weight));
    1236
    0
                    }
    1237
                }
    1238
            }
    1239
    1240
            // Topological sort using Kahn's algorithm
    1241
    0
            let mut in_degree = vec![0u32; self.nodes.len()];
    1242
    0
            for edges in &adj {
    1243
    0
                for (dst, _) in edges {
    1244
    0
                    in_degree[*dst as usize] += 1;
    1245
    0
                }
    1246
            }
    1247
    1248
    0
            let mut queue: Vec<u32> = (0..self.nodes.len() as u32)
    1249
    0
                .filter(|&i| in_degree[i as usize] == 0)
    1250
    0
                .collect();
    1251
    0
            let mut topo_order = Vec::with_capacity(self.nodes.len());
    1252
    1253
    0
            while let Some(u) = queue.pop() {
    1254
    0
                topo_order.push(u);
    1255
    0
                for (v, _) in &adj[u as usize] {
    1256
    0
                    in_degree[*v as usize] -= 1;
    1257
    0
                    if in_degree[*v as usize] == 0 {
    1258
    0
                        queue.push(*v);
    1259
    0
                    }
    1260
                }
    1261
            }
    1262
    1263
            // Longest path DP
    1264
    0
            let mut dist = vec![0u64; self.nodes.len()];
    1265
    0
            let mut pred = vec![None::<u32>; self.nodes.len()];
    1266
    1267
            // Initialize with node's own timing for roots
    1268
    0
            for &node in &topo_order {
    1269
    0
                if self.edges.iter().all(|e| e.dst.0 != node) {
    1270
    0
                    dist[node as usize] = self.node_timing_ns(ExecutionNodeId(node));
    1271
    0
                }
    1272
            }
    1273
    1274
    0
            for &u in &topo_order {
    1275
    0
                for (v, weight) in &adj[u as usize] {
    1276
    0
                    let new_dist = dist[u as usize] + weight;
    1277
    0
                    if new_dist > dist[*v as usize] {
    1278
    0
                        dist[*v as usize] = new_dist;
    1279
    0
                        pred[*v as usize] = Some(u);
    1280
    0
                    }
    1281
                }
    1282
            }
    1283
    1284
            // Find endpoint with maximum distance
    1285
    0
            let (end_node, &total_time) = dist
    1286
    0
                .iter()
    1287
    0
                .enumerate()
    1288
    0
                .max_by_key(|(_, &d)| d)
    1289
    0
                .unwrap_or((0, &0));
    1290
    1291
            // Reconstruct path
    1292
    0
            let mut path = vec![];
    1293
    0
            let mut current = Some(end_node as u32);
    1294
    0
            while let Some(node) = current {
    1295
    0
                path.push(ExecutionNodeId(node));
    1296
    0
                current = pred[node as usize];
    1297
    0
            }
    1298
    0
            path.reverse();
    1299
    1300
    0
            (path, total_time)
    1301
    0
        }
    1302
    1303
        /// Compute slack for each node (how much it can be delayed without affecting total time).
    1304
        ///
    1305
        /// Returns map from node ID to slack in nanoseconds. Nodes on critical path have slack = 0.
    1306
    0
        pub fn compute_slack(&self) -> HashMap<ExecutionNodeId, u64> {
    1307
    0
            let (critical_path, total_time) = self.critical_path();
    1308
    0
            let critical_set: std::collections::HashSet<_> = critical_path.iter().copied().collect();
    1309
    1310
    0
            let mut slack = HashMap::new();
    1311
    1312
            // Build reverse adjacency
    1313
    0
            let mut reverse_adj: Vec<Vec<u32>> = vec![vec![]; self.nodes.len()];
    1314
    0
            for edge in &self.edges {
    1315
    0
                reverse_adj[edge.dst.0 as usize].push(edge.src.0);
    1316
    0
            }
    1317
    1318
            // Forward pass: earliest start time
    1319
    0
            let mut earliest = vec![0u64; self.nodes.len()];
    1320
    0
            for i in 0..self.nodes.len() {
    1321
    0
                let mut max_pred = 0u64;
    1322
    0
                for &pred in &reverse_adj[i] {
    1323
    0
                    max_pred =
    1324
    0
                        max_pred.max(earliest[pred as usize] + self.node_timing_ns(ExecutionNodeId(pred)));
    1325
    0
                }
    1326
    0
                earliest[i] = max_pred;
    1327
            }
    1328
    1329
            // Backward pass: latest start time
    1330
    0
            let mut latest = vec![total_time; self.nodes.len()];
    1331
    0
            for i in (0..self.nodes.len()).rev() {
    1332
    0
                let timing = self.node_timing_ns(ExecutionNodeId(i as u32));
    1333
    0
                let mut min_succ = total_time;
    1334
    0
                for edge in &self.edges {
    1335
    0
                    if edge.src.0 == i as u32 {
    1336
    0
                        min_succ = min_succ.min(latest[edge.dst.0 as usize]);
    1337
    0
                    }
    1338
                }
    1339
    0
                latest[i] = min_succ.saturating_sub(timing);
    1340
            }
    1341
    1342
            // Slack = latest - earliest
    1343
    0
            for i in 0..self.nodes.len() {
    1344
    0
                let node_id = ExecutionNodeId(i as u32);
    1345
    0
                let node_slack = if critical_set.contains(&node_id) {
    1346
    0
                    0
    1347
                } else {
    1348
    0
                    latest[i].saturating_sub(earliest[i])
    1349
                };
    1350
    0
                slack.insert(node_id, node_slack);
    1351
            }
    1352
    1353
    0
            slack
    1354
    0
        }
    1355
    1356
        /// Compute roofline distance for kernel nodes.
    1357
        ///
    1358
        /// Returns map from kernel node ID to distance from roofline (0.0 = optimal).
    1359
        /// Distance = 1.0 - min(achieved/peak_compute, achieved/peak_bandwidth).
    1360
        ///
    1361
        /// Reference: Williams et al. (2009) "Roofline: An Insightful Visual Performance Model"
    1362
    0
        pub fn roofline_distance(
    1363
    0
            &self,
    1364
    0
            peak_tflops: f32,
    1365
    0
            peak_bandwidth_gb_s: f32,
    1366
    0
        ) -> HashMap<ExecutionNodeId, f32> {
    1367
    0
            let mut distances = HashMap::new();
    1368
    1369
    0
            for (i, node) in self.nodes.iter().enumerate() {
    1370
                if let ExecutionNode::Kernel {
    1371
    0
                    arithmetic_intensity,
    1372
    0
                    achieved_tflops,
    1373
                    ..
    1374
    0
                } = node
    1375
                {
    1376
    0
                    if let (Some(ai), Some(achieved)) = (arithmetic_intensity, achieved_tflops) {
    1377
    0
                        // Roofline model: achievable = min(peak_compute, ai * bandwidth)
    1378
    0
                        let bandwidth_bound = *ai * peak_bandwidth_gb_s / 1000.0; // Convert GB/s to TFLOP/s
    1379
    0
                        let roofline_bound = peak_tflops.min(bandwidth_bound);
    1380
    0
                        let efficiency = achieved / roofline_bound;
    1381
    0
                        let distance = 1.0 - efficiency.min(1.0);
    1382
    0
                        distances.insert(ExecutionNodeId(i as u32), distance);
    1383
    0
                    }
    1384
    0
                }
    1385
            }
    1386
    1387
    0
            distances
    1388
    0
        }
    1389
    1390
        /// Detect ping-pong memory transfer patterns (wasteful H2D followed by D2H).
    1391
        ///
    1392
        /// Returns pairs of transfer node IDs that exhibit ping-pong behavior.
    1393
    0
        pub fn detect_ping_pong(&self) -> Vec<(ExecutionNodeId, ExecutionNodeId)> {
    1394
    0
            let mut patterns = Vec::new();
    1395
    1396
            // Find transfer nodes
    1397
    0
            let transfers: Vec<(usize, &ExecutionNode)> = self
    1398
    0
                .nodes
    1399
    0
                .iter()
    1400
    0
                .enumerate()
    1401
    0
                .filter(|(_, n)| matches!(n, ExecutionNode::Transfer { .. }))
    1402
    0
                .collect();
    1403
    1404
            // Check for H2D followed by D2H on same data
    1405
    0
            for i in 0..transfers.len() {
    1406
    0
                for j in (i + 1)..transfers.len() {
    1407
                    if let (
    1408
                        ExecutionNode::Transfer {
    1409
    0
                            src: src1,
    1410
    0
                            dst: dst1,
    1411
    0
                            direction: dir1,
    1412
    0
                            bytes: bytes1,
    1413
                            ..
    1414
                        },
    1415
                        ExecutionNode::Transfer {
    1416
    0
                            src: src2,
    1417
    0
                            dst: dst2,
    1418
    0
                            direction: dir2,
    1419
    0
                            bytes: bytes2,
    1420
                            ..
    1421
                        },
    1422
    0
                    ) = (&transfers[i].1, &transfers[j].1)
    1423
                    {
    1424
                        // Ping-pong: H2D then D2H with matching src/dst and same size
    1425
    0
                        let is_ping_pong = (*dir1 == TransferDirection::H2D
    1426
    0
                            && *dir2 == TransferDirection::D2H
    1427
    0
                            && dst1 == src2
    1428
    0
                            && bytes1 == bytes2)
    1429
    0
                            || (*dir1 == TransferDirection::D2H
    1430
    0
                                && *dir2 == TransferDirection::H2D
    1431
    0
                                && src1 == dst2
    1432
    0
                                && bytes1 == bytes2);
    1433
    1434
    0
                        if is_ping_pong {
    1435
    0
                            patterns.push((
    1436
    0
                                ExecutionNodeId(transfers[i].0 as u32),
    1437
    0
                                ExecutionNodeId(transfers[j].0 as u32),
    1438
    0
                            ));
    1439
    0
                        }
    1440
    0
                    }
    1441
                }
    1442
            }
    1443
    1444
    0
            patterns
    1445
    0
        }
    1446
    1447
        /// Get critical path analysis summary as formatted string.
    1448
    0
        pub fn critical_path_summary(&self) -> String {
    1449
    0
            let (path, total_ns) = self.critical_path();
    1450
    0
            let slack = self.compute_slack();
    1451
    1452
    0
            let mut output = String::new();
    1453
    0
            output.push_str(&format!(
    1454
    0
                "Critical Path: {:.2}ms ({} nodes)\n",
    1455
    0
                total_ns as f64 / 1_000_000.0,
    1456
    0
                path.len()
    1457
    0
            ));
    1458
    0
            output.push_str("─".repeat(50).as_str());
    1459
    0
            output.push('\n');
    1460
    1461
    0
            for (i, node_id) in path.iter().enumerate() {
    1462
    0
                let node = &self.nodes[node_id.0 as usize];
    1463
    0
                let timing = self.node_timing_ns(*node_id);
    1464
    0
                let node_name = match node {
    1465
    0
                    ExecutionNode::Layer { index } => format!("Layer {}", index),
    1466
    0
                    ExecutionNode::Brick { id, .. } => id.name().to_string(),
    1467
    0
                    ExecutionNode::Kernel { name, .. } => name.clone(),
    1468
    0
                    ExecutionNode::Function { name, .. } => name.clone(),
    1469
                    ExecutionNode::Transfer {
    1470
    0
                        direction, src, dst, ..
    1471
                    } => {
    1472
    0
                        format!("{:?} {} → {}", direction, src, dst)
    1473
                    }
    1474
                    ExecutionNode::AsyncTask {
    1475
    0
                        name, poll_count, ..
    1476
                    } => {
    1477
    0
                        format!("{} ({}polls)", name, poll_count)
    1478
                    }
    1479
                };
    1480
    1481
    0
                let prefix = if i == 0 {
    1482
    0
                    "┌"
    1483
    0
                } else if i == path.len() - 1 {
    1484
    0
                    "└"
    1485
                } else {
    1486
    0
                    "│"
    1487
                };
    1488
    0
                output.push_str(&format!(
    1489
    0
                    "{} {} ({:.1}µs)\n",
    1490
    0
                    prefix,
    1491
    0
                    node_name,
    1492
    0
                    timing as f64 / 1000.0
    1493
    0
                ));
    1494
            }
    1495
    1496
            // Show nodes with most slack (parallelization opportunities)
    1497
    0
            let mut slack_vec: Vec<_> = slack.iter().collect();
    1498
    0
            slack_vec.sort_by(|a, b| b.1.cmp(a.1));
    1499
    1500
    0
            if slack_vec.iter().any(|(_, &s)| s > 0) {
    1501
    0
                output.push_str("\nParallelization Opportunities (high slack):\n");
    1502
    0
                for (node_id, &node_slack) in slack_vec.iter().take(5) {
    1503
    0
                    if node_slack > 0 {
    1504
    0
                        let node = &self.nodes[node_id.0 as usize];
    1505
    0
                        let node_name = match node {
    1506
    0
                            ExecutionNode::Layer { index } => format!("Layer {}", index),
    1507
    0
                            ExecutionNode::Brick { id, .. } => id.name().to_string(),
    1508
    0
                            ExecutionNode::Kernel { name, .. } => name.clone(),
    1509
    0
                            ExecutionNode::Function { name, .. } => name.clone(),
    1510
                            ExecutionNode::Transfer {
    1511
    0
                                direction, src, dst, ..
    1512
                            } => {
    1513
    0
                                format!("{:?} {} → {}", direction, src, dst)
    1514
                            }
    1515
                            ExecutionNode::AsyncTask {
    1516
    0
                                name, poll_count, ..
    1517
                            } => {
    1518
    0
                                format!("{} ({}polls)", name, poll_count)
    1519
                            }
    1520
                        };
    1521
    0
                        output.push_str(&format!(
    1522
    0
                            "  {} slack={:.1}µs\n",
    1523
    0
                            node_name,
    1524
    0
                            node_slack as f64 / 1000.0
    1525
    0
                        ));
    1526
    0
                    }
    1527
                }
    1528
    0
            }
    1529
    1530
    0
            output
    1531
    0
        }
    1532
    1533
        /// Clear the graph.
    1534
    0
        pub fn clear(&mut self) {
    1535
    0
            self.nodes.clear();
    1536
    0
            self.edges.clear();
    1537
    0
            self.scope_stack.clear();
    1538
    0
            self.name_to_id.clear();
    1539
    0
        }
    1540
    1541
        /// Check if scope stack is balanced (empty).
    1542
    0
        pub fn is_scope_balanced(&self) -> bool {
    1543
    0
            self.scope_stack.is_empty()
    1544
    0
        }
    1545
    }
    1546
    1547
    /// PTX kernel registry for execution graph correlation.
    1548
    ///
    1549
    /// PAR-201: Maps PTX hashes to source code for debugging and analysis.
    1550
    #[derive(Debug, Default)]
    1551
    pub struct PtxRegistry {
    1552
        /// Hash → (kernel_name, ptx_source, file_path)
    1553
        kernels: HashMap<u64, (String, String, Option<std::path::PathBuf>)>,
    1554
    }
    1555
    1556
    impl PtxRegistry {
    1557
        /// Create a new empty registry.
    1558
    0
        pub fn new() -> Self {
    1559
    0
            Self::default()
    1560
    0
        }
    1561
    1562
        /// Register PTX source code.
    1563
        ///
    1564
        /// # Arguments
    1565
        /// - `name`: Kernel name (e.g., "batched_q4k_gemv")
    1566
        /// - `ptx`: PTX source code
    1567
        /// - `path`: Optional file path for source correlation
    1568
    0
        pub fn register(&mut self, name: &str, ptx: &str, path: Option<&std::path::Path>) {
    1569
    0
            let hash = Self::hash_ptx(ptx);
    1570
    0
            self.kernels.insert(
    1571
    0
                hash,
    1572
                (
    1573
    0
                    name.to_string(),
    1574
    0
                    ptx.to_string(),
    1575
    0
                    path.map(|p| p.to_path_buf()),
    1576
                ),
    1577
            );
    1578
    0
        }
    1579
    1580
        /// Compute FNV-1a hash of PTX source.
    1581
        #[inline]
    1582
    0
        pub fn hash_ptx(ptx: &str) -> u64 {
    1583
            // FNV-1a hash
    1584
    0
            let mut hash: u64 = 0xcbf29ce484222325;
    1585
    0
            for byte in ptx.bytes() {
    1586
    0
                hash ^= byte as u64;
    1587
    0
                hash = hash.wrapping_mul(0x100000001b3);
    1588
    0
            }
    1589
    0
            hash
    1590
    0
        }
    1591
    1592
        /// Lookup PTX source by hash.
    1593
    0
        pub fn lookup(&self, hash: u64) -> Option<&str> {
    1594
    0
            self.kernels.get(&hash).map(|(_, ptx, _)| ptx.as_str())
    1595
    0
        }
    1596
    1597
        /// Lookup kernel name by hash.
    1598
    0
        pub fn lookup_name(&self, hash: u64) -> Option<&str> {
    1599
    0
            self.kernels.get(&hash).map(|(name, _, _)| name.as_str())
    1600
    0
        }
    1601
    1602
        /// Lookup file path by hash.
    1603
    0
        pub fn lookup_path(&self, hash: u64) -> Option<&std::path::Path> {
    1604
    0
            self.kernels
    1605
    0
                .get(&hash)
    1606
    0
                .and_then(|(_, _, path)| path.as_deref())
    1607
    0
        }
    1608
    1609
        /// Get all registered hashes.
    1610
    0
        pub fn hashes(&self) -> impl Iterator<Item = u64> + '_ {
    1611
    0
            self.kernels.keys().copied()
    1612
    0
        }
    1613
    1614
        /// Number of registered kernels.
    1615
    0
        pub fn len(&self) -> usize {
    1616
    0
            self.kernels.len()
    1617
    0
        }
    1618
    1619
        /// Check if registry is empty.
    1620
    0
        pub fn is_empty(&self) -> bool {
    1621
    0
            self.kernels.is_empty()
    1622
    0
        }
    1623
    }
    1624
    1625
    /// Aggregated statistics for a brick category.
    1626
    #[derive(Debug, Clone, Copy, Default)]
    1627
    pub struct CategoryStats {
    1628
        /// Total elapsed time (nanoseconds)
    1629
        pub total_ns: u64,
    1630
        /// Total elements processed
    1631
        pub total_elements: u64,
    1632
        /// Total samples
    1633
        pub count: u64,
    1634
    }
    1635
    1636
    impl CategoryStats {
    1637
        /// Average time per sample in microseconds.
    1638
        #[inline]
    1639
    0
        pub fn avg_us(&self) -> f64 {
    1640
    0
            if self.count == 0 {
    1641
    0
                0.0
    1642
            } else {
    1643
    0
                self.total_ns as f64 / self.count as f64 / 1000.0
    1644
            }
    1645
    0
        }
    1646
    1647
        /// Throughput in elements per second.
    1648
        #[inline]
    1649
    0
        pub fn throughput(&self) -> f64 {
    1650
    0
            if self.total_ns == 0 {
    1651
    0
                0.0
    1652
            } else {
    1653
    0
                self.total_elements as f64 / (self.total_ns as f64 / 1_000_000_000.0)
    1654
            }
    1655
    0
        }
    1656
    1657
        /// Percentage of total time (given total_ns across all categories).
    1658
        #[inline]
    1659
    0
        pub fn percentage(&self, total: u64) -> f64 {
    1660
    0
            if total == 0 {
    1661
    0
                0.0
    1662
            } else {
    1663
    0
                100.0 * self.total_ns as f64 / total as f64
    1664
            }
    1665
    0
        }
    1666
    }
    1667
    1668
    /// Accumulated per-brick statistics.
    1669
    #[derive(Debug, Clone, Default)]
    1670
    pub struct BrickStats {
    1671
        /// Brick name
    1672
        pub name: String,
    1673
        /// Total samples collected
    1674
        pub count: u64,
    1675
        /// Total elapsed time (nanoseconds)
    1676
        pub total_ns: u64,
    1677
        /// Min elapsed time (nanoseconds)
    1678
        pub min_ns: u64,
    1679
        /// Max elapsed time (nanoseconds)
    1680
        pub max_ns: u64,
    1681
        /// Total elements processed
    1682
        pub total_elements: u64,
    1683
        /// PMAT-451: Total bytes processed (for throughput calculation)
    1684
        pub total_bytes: u64,
    1685
        /// PMAT-451: Total compressed bytes (for compression ratio)
    1686
        pub total_compressed_bytes: u64,
    1687
        /// PMAT-451: Bottleneck classification
    1688
        pub bottleneck: BrickBottleneck,
    1689
        /// Phase 11 (E.9.2): Total CPU cycles (from RDTSCP/CNTVCT)
    1690
        pub total_cycles: u64,
    1691
        /// Phase 11: Minimum CPU cycles observed
    1692
        pub min_cycles: u64,
    1693
        /// Phase 11: Maximum CPU cycles observed
    1694
        pub max_cycles: u64,
    1695
    }
    1696
    1697
    impl BrickStats {
    1698
        /// Create new stats for a brick.
    1699
    0
        pub fn new(name: &str) -> Self {
    1700
    0
            Self {
    1701
    0
                name: name.to_string(),
    1702
    0
                count: 0,
    1703
    0
                total_ns: 0,
    1704
    0
                min_ns: u64::MAX,
    1705
    0
                max_ns: 0,
    1706
    0
                total_elements: 0,
    1707
    0
                total_bytes: 0,
    1708
    0
                total_compressed_bytes: 0,
    1709
    0
                bottleneck: BrickBottleneck::Unknown,
    1710
    0
                total_cycles: 0,
    1711
    0
                min_cycles: u64::MAX,
    1712
    0
                max_cycles: 0,
    1713
    0
            }
    1714
    0
        }
    1715
    1716
        /// Add a sample to statistics.
    1717
    0
        pub fn add_sample(&mut self, elapsed_ns: u64, elements: u64) {
    1718
    0
            self.count += 1;
    1719
    0
            self.total_ns += elapsed_ns;
    1720
    0
            self.min_ns = self.min_ns.min(elapsed_ns);
    1721
    0
            self.max_ns = self.max_ns.max(elapsed_ns);
    1722
    0
            self.total_elements += elements;
    1723
    0
        }
    1724
    1725
        /// Phase 11 (E.9.2): Add a sample with CPU cycle count.
    1726
        ///
    1727
        /// Use this for frequency-invariant performance analysis.
    1728
        /// Cycles are immune to CPU frequency scaling (turbo boost).
    1729
    0
        pub fn add_sample_with_cycles(&mut self, elapsed_ns: u64, elements: u64, cycles: u64) {
    1730
    0
            self.add_sample(elapsed_ns, elements);
    1731
    0
            self.total_cycles += cycles;
    1732
    0
            self.min_cycles = self.min_cycles.min(cycles);
    1733
    0
            self.max_cycles = self.max_cycles.max(cycles);
    1734
    0
        }
    1735
    1736
        /// Phase 11: Cycles per element (frequency-invariant throughput metric).
    1737
        ///
    1738
        /// Lower is better. This metric is immune to CPU frequency scaling.
    1739
        #[must_use]
    1740
    0
        pub fn cycles_per_element(&self) -> f64 {
    1741
    0
            if self.total_elements == 0 {
    1742
    0
                0.0
    1743
            } else {
    1744
    0
                self.total_cycles as f64 / self.total_elements as f64
    1745
            }
    1746
    0
        }
    1747
    1748
        /// Phase 11: Average cycles per sample.
    1749
        #[must_use]
    1750
    0
        pub fn avg_cycles(&self) -> f64 {
    1751
    0
            if self.count == 0 {
    1752
    0
                0.0
    1753
            } else {
    1754
    0
                self.total_cycles as f64 / self.count as f64
    1755
            }
    1756
    0
        }
    1757
    1758
        /// Phase 11: Estimated IPC (Instructions Per Cycle).
    1759
        ///
    1760
        /// Approximation assuming ~1 instruction per element for simple ops.
    1761
        /// - Low IPC (<1.0): Memory stalls (cache misses, memory latency)
    1762
        /// - High IPC (>2.0): Compute bound (efficient execution)
    1763
        #[must_use]
    1764
    0
        pub fn estimated_ipc(&self) -> f64 {
    1765
    0
            if self.total_cycles == 0 {
    1766
    0
                0.0
    1767
            } else {
    1768
                // Rough approximation: assume 1 instruction per element
    1769
    0
                self.total_elements as f64 / self.total_cycles as f64
    1770
            }
    1771
    0
        }
    1772
    1773
        /// Phase 11: Diagnose bottleneck based on cycles vs time ratio.
    1774
        ///
    1775
        /// High cycles + low time = likely cache misses
    1776
        /// Low cycles + high time = likely CPU throttling or context switches
    1777
        #[must_use]
    1778
    0
        pub fn diagnose_from_cycles(&self) -> &'static str {
    1779
    0
            if self.total_cycles == 0 || self.total_ns == 0 {
    1780
    0
                return "insufficient data";
    1781
    0
            }
    1782
    1783
    0
            let ipc = self.estimated_ipc();
    1784
    0
            let ns_per_cycle = self.total_ns as f64 / self.total_cycles as f64;
    1785
    1786
            // Typical CPU runs at ~3GHz, so 1 cycle ≈ 0.33ns
    1787
            // If ns_per_cycle >> 0.33, we're seeing stalls or throttling
    1788
    0
            if ipc < 0.5 {
    1789
    0
                "memory-bound (low IPC, likely cache misses)"
    1790
    0
            } else if ipc > 2.0 {
    1791
    0
                "compute-bound (efficient)"
    1792
    0
            } else if ns_per_cycle > 1.0 {
    1793
    0
                "throttled or context-switched"
    1794
            } else {
    1795
    0
                "balanced"
    1796
            }
    1797
    0
        }
    1798
    1799
        /// PMAT-451: Add a sample with byte metrics for compression workloads.
    1800
        ///
    1801
        /// # Arguments
    1802
        /// - `elapsed_ns`: Time taken in nanoseconds
    1803
        /// - `elements`: Number of elements processed (e.g., pages)
    1804
        /// - `input_bytes`: Original uncompressed size
    1805
        /// - `output_bytes`: Compressed output size
    1806
    0
        pub fn add_sample_with_bytes(
    1807
    0
            &mut self,
    1808
    0
            elapsed_ns: u64,
    1809
    0
            elements: u64,
    1810
    0
            input_bytes: u64,
    1811
    0
            output_bytes: u64,
    1812
    0
        ) {
    1813
    0
            self.add_sample(elapsed_ns, elements);
    1814
    0
            self.total_bytes += input_bytes;
    1815
    0
            self.total_compressed_bytes += output_bytes;
    1816
    0
        }
    1817
    1818
        /// PMAT-451: Calculate compression ratio (input_size / output_size).
    1819
        /// Returns 1.0 if no compression data available.
    1820
        #[must_use]
    1821
    0
        pub fn compression_ratio(&self) -> f64 {
    1822
    0
            if self.total_compressed_bytes == 0 {
    1823
    0
                1.0
    1824
            } else {
    1825
    0
                self.total_bytes as f64 / self.total_compressed_bytes as f64
    1826
            }
    1827
    0
        }
    1828
    1829
        /// PMAT-451: Calculate throughput in GB/s.
    1830
        /// Based on total input bytes processed.
    1831
        #[must_use]
    1832
    0
        pub fn throughput_gbps(&self) -> f64 {
    1833
    0
            if self.total_ns == 0 {
    1834
    0
                0.0
    1835
            } else {
    1836
    0
                let bytes_per_ns = self.total_bytes as f64 / self.total_ns as f64;
    1837
    0
                bytes_per_ns * 1e9 / 1e9 // Convert to GB/s (ns to sec, bytes to GB)
    1838
            }
    1839
    0
        }
    1840
    1841
        /// PMAT-451: Set bottleneck classification.
    1842
    0
        pub fn set_bottleneck(&mut self, bottleneck: BrickBottleneck) {
    1843
    0
            self.bottleneck = bottleneck;
    1844
    0
        }
    1845
    1846
        /// PMAT-451: Get bottleneck classification.
    1847
        #[must_use]
    1848
    0
        pub fn get_bottleneck(&self) -> BrickBottleneck {
    1849
    0
            self.bottleneck
    1850
    0
        }
    1851
    1852
        /// Average time in microseconds.
    1853
        #[must_use]
    1854
    0
        pub fn avg_us(&self) -> f64 {
    1855
    0
            if self.count == 0 {
    1856
    0
                0.0
    1857
            } else {
    1858
    0
                self.total_ns as f64 / self.count as f64 / 1000.0
    1859
            }
    1860
    0
        }
    1861
    1862
        /// Throughput in elements/second.
    1863
        #[must_use]
    1864
    0
        pub fn throughput(&self) -> f64 {
    1865
    0
            if self.total_ns == 0 {
    1866
    0
                0.0
    1867
            } else {
    1868
    0
                self.total_elements as f64 / (self.total_ns as f64 / 1_000_000_000.0)
    1869
            }
    1870
    0
        }
    1871
    1872
        /// Throughput in tokens/second (alias for throughput).
    1873
        #[must_use]
    1874
    0
        pub fn tokens_per_sec(&self) -> f64 {
    1875
    0
            self.throughput()
    1876
    0
        }
    1877
    1878
        /// Minimum time in microseconds.
    1879
        #[must_use]
    1880
    0
        pub fn min_us(&self) -> f64 {
    1881
    0
            if self.min_ns == u64::MAX {
    1882
    0
                0.0
    1883
            } else {
    1884
    0
                self.min_ns as f64 / 1000.0
    1885
            }
    1886
    0
        }
    1887
    1888
        /// Maximum time in microseconds.
    1889
        #[must_use]
    1890
    0
        pub fn max_us(&self) -> f64 {
    1891
    0
            self.max_ns as f64 / 1000.0
    1892
    0
        }
    1893
    }
    1894
    1895
    #[cfg(test)]
    1896
    mod tests {
    1897
        use super::*;
    1898
    1899
        #[test]
    1900
        fn test_brick_id_category() {
    1901
            assert_eq!(BrickId::RmsNorm.category(), BrickCategory::Norm);
    1902
            assert_eq!(BrickId::LayerNorm.category(), BrickCategory::Norm);
    1903
            assert_eq!(BrickId::QkvProjection.category(), BrickCategory::Attention);
    1904
            assert_eq!(BrickId::GateProjection.category(), BrickCategory::Ffn);
    1905
            assert_eq!(BrickId::Embedding.category(), BrickCategory::Other);
    1906
        }
    1907
    1908
        #[test]
    1909
        fn test_brick_id_name() {
    1910
            assert_eq!(BrickId::RmsNorm.name(), "RmsNorm");
    1911
            assert_eq!(BrickId::QkvProjection.name(), "QkvProjection");
    1912
        }
    1913
    1914
        #[test]
    1915
        fn test_brick_id_from_str() {
    1916
            assert_eq!(BrickId::from_str("RmsNorm"), Some(BrickId::RmsNorm));
    1917
            assert_eq!(BrickId::from_str("Qkv"), Some(BrickId::QkvProjection));
    1918
            assert_eq!(BrickId::from_str("RoPE"), Some(BrickId::RopeEmbedding));
    1919
            assert_eq!(BrickId::from_str("Unknown"), None);
    1920
        }
    1921
    1922
        #[test]
    1923
        fn test_brick_id_display() {
    1924
            assert_eq!(format!("{}", BrickId::RmsNorm), "RmsNorm");
    1925
        }
    1926
    1927
        #[test]
    1928
        fn test_brick_category_name() {
    1929
            assert_eq!(BrickCategory::Norm.name(), "Norm");
    1930
            assert_eq!(BrickCategory::Ffn.name(), "FFN");
    1931
        }
    1932
    1933
        #[test]
    1934
        fn test_brick_bottleneck_display() {
    1935
            assert_eq!(format!("{}", BrickBottleneck::Memory), "memory");
    1936
            assert_eq!(format!("{}", BrickBottleneck::Compute), "compute");
    1937
        }
    1938
    1939
        #[test]
    1940
        fn test_execution_graph_basic() {
    1941
            let mut graph = ExecutionGraph::new();
    1942
            let layer = graph.add_node(ExecutionNode::Layer { index: 0 });
    1943
            let brick = graph.add_node(ExecutionNode::Brick {
    1944
                id: BrickId::RmsNorm,
    1945
                timing_ns: 1000,
    1946
                elements: 4096,
    1947
            });
    1948
            graph.add_edge(layer, brick, EdgeType::Contains);
    1949
    1950
            assert_eq!(graph.num_nodes(), 2);
    1951
            assert_eq!(graph.num_edges(), 1);
    1952
        }
    1953
    1954
        #[test]
    1955
        fn test_execution_node_name() {
    1956
            let brick = ExecutionNode::Brick {
    1957
                id: BrickId::RmsNorm,
    1958
                timing_ns: 1000,
    1959
                elements: 4096,
    1960
            };
    1961
            assert_eq!(brick.name(), "RmsNorm");
    1962
    1963
            let layer = ExecutionNode::Layer { index: 5 };
    1964
            assert_eq!(layer.name(), "Layer5");
    1965
        }
    1966
    1967
        #[test]
    1968
        fn test_execution_graph_scopes() {
    1969
            let mut graph = ExecutionGraph::new();
    1970
            let layer = graph.push_scope(ExecutionNode::Layer { index: 0 });
    1971
            let brick = graph.add_node_in_scope(ExecutionNode::Brick {
    1972
                id: BrickId::RmsNorm,
    1973
                timing_ns: 1000,
    1974
                elements: 4096,
    1975
            });
    1976
            graph.pop_scope();
    1977
    1978
            assert_eq!(graph.num_nodes(), 2);
    1979
            // Should have a Contains edge from layer to brick
    1980
            let edges: Vec<_> = graph.outgoing_edges(layer).collect();
    1981
            assert_eq!(edges.len(), 1);
    1982
            assert_eq!(edges[0].dst, brick);
    1983
        }
    1984
    1985
        #[test]
    1986
        fn test_brick_stats_basic() {
    1987
            let mut stats = BrickStats::new("test_brick");
    1988
            stats.add_sample(1000, 100);
    1989
            stats.add_sample(2000, 200);
    1990
    1991
            assert_eq!(stats.count, 2);
    1992
            assert_eq!(stats.total_ns, 3000);
    1993
            assert_eq!(stats.total_elements, 300);
    1994
            assert_eq!(stats.min_ns, 1000);
    1995
            assert_eq!(stats.max_ns, 2000);
    1996
        }
    1997
    1998
        #[test]
    1999
        fn test_category_stats_percentage() {
    2000
            let stats = CategoryStats {
    2001
                total_ns: 250,
    2002
                total_elements: 1000,
    2003
                count: 10,
    2004
            };
    2005
            assert!((stats.percentage(1000) - 25.0).abs() < 0.001);
    2006
        }
    2007
    2008
        #[test]
    2009
        fn test_ptx_registry() {
    2010
            let mut registry = PtxRegistry::new();
    2011
            registry.register("test_kernel", ".version 8.0\n.entry test {}", None);
    2012
    2013
            assert_eq!(registry.len(), 1);
    2014
            assert!(!registry.is_empty());
    2015
    2016
            let hash = PtxRegistry::hash_ptx(".version 8.0\n.entry test {}");
    2017
            assert_eq!(registry.lookup_name(hash), Some("test_kernel"));
    2018
        }
    2019
    2020
        #[test]
    2021
        fn test_transfer_direction() {
    2022
            let node = ExecutionNode::Transfer {
    2023
                src: "host".to_string(),
    2024
                dst: "device".to_string(),
    2025
                bytes: 1024,
    2026
                direction: TransferDirection::H2D,
    2027
                timing_ns: Some(100),
    2028
            };
    2029
            assert!(node.is_transfer());
    2030
            assert_eq!(node.transfer_bytes(), Some(1024));
    2031
        }
    2032
    2033
        #[test]
    2034
        fn test_execution_graph_to_dot() {
    2035
            let mut graph = ExecutionGraph::new();
    2036
            graph.add_node(ExecutionNode::Layer { index: 0 });
    2037
            let dot = graph.to_dot();
    2038
            assert!(dot.contains("digraph ExecutionGraph"));
    2039
            assert!(dot.contains("Layer 0"));
    2040
        }
    2041
    2042
        #[test]
    2043
        fn test_execution_graph_to_ascii_tree() {
    2044
            let mut graph = ExecutionGraph::new();
    2045
            graph.push_scope(ExecutionNode::Layer { index: 0 });
    2046
            graph.add_node_in_scope(ExecutionNode::Brick {
    2047
                id: BrickId::RmsNorm,
    2048
                timing_ns: 1000,
    2049
                elements: 4096,
    2050
            });
    2051
            graph.pop_scope();
    2052
    2053
            let tree = graph.to_ascii_tree();
    2054
            assert!(tree.contains("Layer 0"));
    2055
            assert!(tree.contains("RmsNorm"));
    2056
        }
    2057
    2058
        #[test]
    2059
        fn test_brick_stats_cycles() {
    2060
            let mut stats = BrickStats::new("test");
    2061
            stats.add_sample_with_cycles(1000, 100, 3000);
    2062
    2063
            assert_eq!(stats.total_cycles, 3000);
    2064
            assert!((stats.cycles_per_element() - 30.0).abs() < 0.001);
    2065
        }
    2066
    2067
        // FALSIFICATION TESTS
    2068
    2069
        /// FALSIFICATION TEST: BrickId round-trip via name
    2070
        #[test]
    2071
        fn test_falsify_brick_id_round_trip() {
    2072
            for brick_id in [
    2073
                BrickId::RmsNorm,
    2074
                BrickId::LayerNorm,
    2075
                BrickId::QkvProjection,
    2076
                BrickId::RopeEmbedding,
    2077
                BrickId::AttentionScore,
    2078
                BrickId::AttentionSoftmax,
    2079
                BrickId::AttentionOutput,
    2080
                BrickId::OutputProjection,
    2081
                BrickId::GateProjection,
    2082
                BrickId::UpProjection,
    2083
                BrickId::Activation,
    2084
                BrickId::DownProjection,
    2085
                BrickId::Embedding,
    2086
                BrickId::LmHead,
    2087
                BrickId::Sampling,
    2088
            ] {
    2089
                let name = brick_id.name();
    2090
                let parsed = BrickId::from_str(name);
    2091
                assert_eq!(
    2092
                    parsed,
    2093
                    Some(brick_id),
    2094
                    "FALSIFICATION FAILED: BrickId::{:?}.name() = {:?} does not round-trip",
    2095
                    brick_id,
    2096
                    name
    2097
                );
    2098
            }
    2099
        }
    2100
    2101
        /// FALSIFICATION TEST: ExecutionGraph maintains node/edge count consistency
    2102
        #[test]
    2103
        fn test_falsify_graph_consistency() {
    2104
            let mut graph = ExecutionGraph::new();
    2105
    2106
            // Add nodes and edges
    2107
            let n1 = graph.add_node(ExecutionNode::Layer { index: 0 });
    2108
            let n2 = graph.add_node(ExecutionNode::Layer { index: 1 });
    2109
            graph.add_edge(n1, n2, EdgeType::Sequence);
    2110
    2111
            assert_eq!(
    2112
                graph.num_nodes(),
    2113
                2,
    2114
                "FALSIFICATION FAILED: node count mismatch"
    2115
            );
    2116
            assert_eq!(
    2117
                graph.num_edges(),
    2118
                1,
    2119
                "FALSIFICATION FAILED: edge count mismatch"
    2120
            );
    2121
    2122
            // Clear and verify
    2123
            graph.clear();
    2124
            assert_eq!(
    2125
                graph.num_nodes(),
    2126
                0,
    2127
                "FALSIFICATION FAILED: clear did not reset nodes"
    2128
            );
    2129
            assert_eq!(
    2130
                graph.num_edges(),
    2131
                0,
    2132
                "FALSIFICATION FAILED: clear did not reset edges"
    2133
            );
    2134
        }
    2135
    2136
        /// FALSIFICATION TEST: BrickStats min/max tracking
    2137
        #[test]
    2138
        fn test_falsify_brick_stats_minmax() {
    2139
            let mut stats = BrickStats::new("test");
    2140
    2141
            for ns in [1000u64, 500, 2000, 750, 1500] {
    2142
                stats.add_sample(ns, 100);
    2143
            }
    2144
    2145
            assert_eq!(
    2146
                stats.min_ns, 500,
    2147
                "FALSIFICATION FAILED: min_ns should be 500, got {}",
    2148
                stats.min_ns
    2149
            );
    2150
            assert_eq!(
    2151
                stats.max_ns, 2000,
    2152
                "FALSIFICATION FAILED: max_ns should be 2000, got {}",
    2153
                stats.max_ns
    2154
            );
    2155
        }
    2156
    }