block-prompt.md

blockprompt.md

Block-Based EVM Optimization with BLOCK_START Instructions

Overview

This prompt outlines the implementation of a comprehensive block-based optimization system for the Guillotine EVM that introduces BLOCK_START pseudo-instructions to enable advanced optimizations including stack validation, gas pre-calculation, and intelligent prefetching.

Core Philosophy

Instead of validating stack depth and calculating gas costs instruction-by-instruction during execution, we pre-analyze bytecode into basic blocks and aggregate requirements at the block level. This enables:

1. Batch validation - Check stack requirements once per block entry
2. Gas pre-calculation - Calculate total gas cost for entire blocks upfront
3. Intelligent prefetching - Prefetch next blocks during current block execution
4. Better branch prediction - Provide hints based on block analysis

Architecture Overview

Phase 1: Block Analysis and Metadata

pub const BlockMetadata = struct {
    // Block identification
    start_inst_idx: u16,
    end_inst_idx: u16,
    start_pc: u16,
    
    // Execution requirements (to be calculated)
    min_stack_depth: u8,    // Minimum stack items needed on entry
    max_stack_growth: u8,   // Maximum additional stack items created
    total_gas_cost: u64,    // Total gas cost for entire block
    
    // Control flow
    is_terminator: bool,    // Block ends with RETURN/REVERT/STOP
    jump_targets: []u16,    // Possible jump destinations (for JUMPI)
    
    // Optimization hints
    is_loop_header: bool,   // Block is start of a loop
    is_hot_path: bool,      // Frequently executed block
};

pub const BlockAnalysis = struct {
    blocks: []BlockMetadata,
    inst_to_block: []u16,   // Maps instruction index to block index
    allocator: std.mem.Allocator,
    
    pub fn analyzeBlocks(allocator: std.mem.Allocator, code: []const u8) !BlockAnalysis;
    pub fn getBlockForInst(self: *const BlockAnalysis, inst_idx: u16) u16;
    pub fn deinit(self: *BlockAnalysis) void;
};

Phase 2: BLOCK_START Instruction Injection

During analysis, inject BLOCK_START pseudo-instructions at the beginning of each basic block:

// Enhanced analysis that creates ops array with BLOCK_START injections
pub fn prepareWithBlocks(allocator: std.mem.Allocator, code: []const u8) !struct {
    analysis: SimpleAnalysis,
    metadata: []u32,
    ops: []*const anyopaque,
    block_analysis: BlockAnalysis,
} {
    // 1. Analyze basic blocks
    const block_analysis = try BlockAnalysis.analyzeBlocks(allocator, code);
    
    // 2. Create ops array with BLOCK_START injections
    var ops_list = std.ArrayList(*const anyopaque).init(allocator);
    
    for (instructions) |inst, i| {
        // Check if this instruction starts a new block
        if (block_analysis.isBlockStart(i)) {
            // Inject BLOCK_START before the actual instruction
            try ops_list.append(@ptrCast(&tailcalls.op_block_start));
        }
        
        // Add the actual instruction
        const opcode_fn = mapOpcodeToFunction(inst.opcode);
        try ops_list.append(opcode_fn);
    }
    
    return .{
        .analysis = analysis,
        .metadata = metadata,
        .ops = try ops_list.toOwnedSlice(),
        .block_analysis = block_analysis,
    };
}

Phase 3: BLOCK_START Implementation

pub fn op_block_start(frame: *StackFrame) Error!noreturn {
    const block_idx = frame.block_analysis.getBlockForInst(frame.ip);
    const block = &frame.block_analysis.blocks[block_idx];
    
    // 1. STACK VALIDATION
    // Check if we have sufficient stack depth for this block
    if (frame.stack.depth() < block.min_stack_depth) {
        @branchHint(.cold);
        return Error.StackUnderflow;
    }
    
    // Check if block would cause stack overflow
    if (frame.stack.depth() + block.max_stack_growth > MAX_STACK_SIZE) {
        @branchHint(.cold);
        return Error.StackOverflow;
    }
    
    // 2. GAS PRE-CALCULATION AND CHARGING
    // Charge gas for the entire block upfront
    try frame.useGas(block.total_gas_cost);
    
    // 3. INTELLIGENT PREFETCHING
    // Prefetch likely next blocks based on control flow analysis
    if (block.jump_targets.len > 0) {
        // This block ends with a conditional jump - prefetch both targets
        const fallthrough_block = block_idx + 1;
        const jump_target_block = findBlockForPC(block.jump_targets[0]);
        
        // Prefetch fallthrough (more likely)
        if (fallthrough_block < frame.block_analysis.blocks.len) {
            prefetchBlock(frame, fallthrough_block, .medium_locality);
        }
        
        // Prefetch jump target (less likely unless it's a loop)
        if (block.is_loop_header) {
            prefetchBlock(frame, jump_target_block, .high_locality);
        } else {
            prefetchBlock(frame, jump_target_block, .low_locality);
        }
    } else if (!block.is_terminator) {
        // Linear execution - prefetch next block
        const next_block = block_idx + 1;
        if (next_block < frame.block_analysis.blocks.len) {
            prefetchBlock(frame, next_block, .high_locality);
        }
    }
    
    // 4. EXECUTION OPTIMIZATION HINTS
    // Provide branch prediction hints based on block analysis
    if (block.is_hot_path) {
        @branchHint(.likely);
    }
    
    // 5. Continue to actual block execution
    return next(frame);
}

Phase 4: Block-Aware Prefetching

fn prefetchBlock(frame: *StackFrame, block_idx: u16, locality: enum { low_locality, medium_locality, high_locality }) void {
    if (block_idx >= frame.block_analysis.blocks.len) return;
    
    const block = &frame.block_analysis.blocks[block_idx];
    const start_idx = block.start_inst_idx;
    const end_idx = @min(block.end_inst_idx, start_idx + 8); // Limit prefetch window
    
    const locality_val: u2 = switch (locality) {
        .low_locality => 1,
        .medium_locality => 2, 
        .high_locality => 3,
    };
    
    // Prefetch the block's instructions
    for (start_idx..end_idx) |i| {
        if (i < frame.ops.len) {
            @prefetch(frame.ops.ptr + i, .{ .rw = .read, .locality = locality_val, .cache = .data });
            @prefetch(frame.metadata.ptr + i, .{ .rw = .read, .locality = locality_val, .cache = .data });
            @prefetch(frame.ops[i], .{ .rw = .read, .locality = locality_val, .cache = .instruction });
        }
    }
}

Implementation Phases

Phase 1: Basic Block Detection

1. Implement BlockAnalysis.analyzeBlocks() to identify basic block boundaries
2. Create BlockMetadata structures for each block
3. Build instruction-to-block mapping

Phase 2: BLOCK_START Injection

1. Modify prepareWithBlocks() to inject BLOCK_START instructions
2. Update metadata arrays to account for injected instructions
3. Ensure instruction indexing remains consistent

Phase 3: Stack and Gas Analysis

1. Implement stack depth analysis for each block
2. Calculate total gas costs per block
3. Identify stack growth/shrinkage patterns

Phase 4: Control Flow Analysis

1. Identify jump targets and fallthrough paths
2. Detect loop headers and hot paths
3. Build jump target mappings

Phase 5: Prefetching Integration

1. Implement block-aware prefetching in op_block_start
2. Remove old instruction-level prefetching
3. Add locality-based prefetching strategies

Phase 6: Optimization and Validation

1. Add comprehensive tests for block analysis
2. Benchmark performance improvements
3. Validate correctness of stack/gas calculations

Key Benefits

1. Reduced Overhead: Validate stack once per block instead of per instruction
2. Better Gas Accounting: Batch gas charging reduces per-instruction overhead
3. Smarter Prefetching: Block-level analysis enables better cache utilization
4. Branch Prediction: Provide CPU with better hints about execution patterns
5. Future Optimizations: Foundation for JIT compilation, superblock formation

Performance Expectations

• Stack Validation: 5-10x reduction in validation overhead for large blocks
• Gas Calculation: 3-5x reduction in gas accounting overhead
• Cache Performance: 15-25% improvement in instruction cache hit rates
• Branch Prediction: 10-20% improvement in branch prediction accuracy

Implementation Requirements

1. Correctness: Block analysis must be 100% accurate - any errors break execution
2. Memory Safety: All block metadata must be properly allocated/deallocated
3. Compatibility: Must work with existing fusion optimizations
4. Performance: Block analysis overhead must be amortized by execution gains
5. Testing: Comprehensive test suite covering edge cases and error conditions

This architecture provides a solid foundation for advanced EVM optimizations while maintaining correctness and enabling significant performance improvements through intelligent batching and prefetching.