JIT_IR_GENERATION_PLAN.md

# JIT IR Generation Implementation Plan

## Overview

This document lists all parse tree nodes that require IR generation support for the JIT compiler, organized by category and implementation priority.

---

## Expression Types (tree_expression subclasses)

### Priority 1: Basic Expressions (Foundation)

#### 1.1 Constants (`tree_constant`)
**File:** `libinterp/parse-tree/pt-const.h`
- **Description:** Literal values (numbers, strings, etc.)
- **IR Generation:**
  - Convert `octave_value` to LLVM constant
  - Handle different types (scalar, matrix, string, etc.)
  - Create LLVM constant values
- **Complexity:** Low
- **Dependencies:** None

#### 1.2 Identifiers (`tree_identifier`)
**File:** `libinterp/parse-tree/pt-id.h`
- **Description:** Variable names and symbol references
- **IR Generation:**
  - Lookup variable in symbol table
  - Load variable value
  - Handle scoping (local, global, persistent)
  - Support for lvalue/rvalue contexts
- **Complexity:** Medium
- **Dependencies:** Symbol table integration

#### 1.3 Binary Expressions (`tree_binary_expression`)
**File:** `libinterp/parse-tree/pt-binop.h`
- **Description:** Binary operations (+, -, *, /, etc.)
- **Operations to support:**
  - Arithmetic: `+`, `-`, `*`, `/`, `\` (left divide), `^` (power)
  - Element-wise: `.*`, `./`, `.\`, `.^`
  - Comparison: `<`, `<=`, `==`, `!=`, `>=`, `>`
  - Logical: `&&`, `||`, `&`, `|`
  - Matrix operations: `*`, `/`, `\`, `^`
- **IR Generation:**
  - Generate IR for left and right operands
  - Map Octave operators to LLVM instructions
  - Handle type promotion
  - Support scalar and matrix operations
- **Complexity:** High
- **Dependencies:** Constants, Identifiers, Type system

#### 1.4 Unary Expressions (`tree_unary_expression`)
**File:** `libinterp/parse-tree/pt-unop.h`
- **Subtypes:**
  - `tree_prefix_expression` (++x, --x, +x, -x, !x, ~x)
  - `tree_postfix_expression` (x++, x--)
- **Operations to support:**
  - Unary plus: `+`
  - Unary minus: `-`
  - Logical NOT: `!`, `~`
  - Increment/decrement: `++`, `--`
  - Transpose: `'`, `.'`
- **IR Generation:**
  - Generate IR for operand
  - Map unary operators to LLVM instructions
  - Handle side effects (prefix vs postfix)
- **Complexity:** Medium
- **Dependencies:** Constants, Identifiers

#### 1.5 Simple Assignment (`tree_simple_assignment`)
**File:** `libinterp/parse-tree/pt-assign.h`
- **Description:** Variable assignment (x = y)
- **Assignment operators:**
  - `=`, `+=`, `-=`, `*=`, `/=`, `\=`, `^=`
  - `.*=`, `./=`, `.\=`, `.^=`
  - `&=`, `|=`, `&&=`, `||=`
- **IR Generation:**
  - Generate IR for right-hand side
  - Store to left-hand side (lvalue)
  - Handle compound assignments
  - Return assigned value
- **Complexity:** Medium
- **Dependencies:** Identifiers, Binary expressions

### Priority 2: Indexing and Arrays

#### 2.1 Index Expressions (`tree_index_expression`)
**File:** `libinterp/parse-tree/pt-idx.h`
- **Description:** Array/struct indexing (a(i,j), s.field, etc.)
- **Index types:**
  - Parentheses: `()` - function calls or array indexing
  - Brackets: `[]` - cell arrays or array indexing
  - Dot: `.` - structure field access
  - Dynamic field: `.(expr)` - dynamic field access
- **IR Generation:**
  - Generate IR for base expression
  - Generate IR for each index argument
  - Handle different index types
  - Support multi-dimensional indexing
  - Handle lvalue/rvalue contexts
- **Complexity:** Very High
- **Dependencies:** Identifiers, Expressions, Arrays

#### 2.2 Matrix Expressions (`tree_matrix`)
**File:** `libinterp/parse-tree/pt-mat.h`
- **Description:** Matrix/array literals ([1,2,3; 4,5,6])
- **IR Generation:**
  - Create matrix/array constants
  - Handle row/column construction
  - Support different element types
- **Complexity:** Medium
- **Dependencies:** Constants, Arrays

#### 2.3 Cell Arrays (`tree_cell`)
**File:** `libinterp/parse-tree/pt-cell.h`
- **Description:** Cell array literals ({1, 'a', [2,3]})
- **IR Generation:**
  - Create cell array structure
  - Store heterogeneous elements
- **Complexity:** Medium
- **Dependencies:** Constants, Arrays

### Priority 3: Advanced Expressions

#### 3.1 Colon Expression (`tree_colon_expression`)
**File:** `libinterp/parse-tree/pt-colon.h`
- **Description:** Colon operator (1:10, 1:2:10)
- **IR Generation:**
  - Generate range/sequence
  - Handle start:step:end syntax
- **Complexity:** Low
- **Dependencies:** Constants, Binary expressions

#### 3.2 Boolean Expressions (`tree_boolean_expression`)
**File:** `libinterp/parse-tree/pt-cbinop.h`
- **Description:** Short-circuit logical operations (&&, ||)
- **IR Generation:**
  - Implement short-circuit evaluation
  - Generate conditional branches
- **Complexity:** Medium
- **Dependencies:** Binary expressions, Control flow

#### 3.3 Compound Binary Expressions (`tree_compound_binary_expression`)
**File:** `libinterp/parse-tree/pt-cbinop.h`
- **Description:** Chained operations (a + b + c)
- **IR Generation:**
  - Handle associativity
  - Generate sequential operations
- **Complexity:** Medium
- **Dependencies:** Binary expressions

#### 3.4 Function Handles (`tree_fcn_handle`, `tree_anon_fcn_handle`)
**File:** `libinterp/parse-tree/pt-fcn-handle.h`
- **Description:** Function handles (@sin, @(x) x^2)
- **IR Generation:**
  - Store function pointer
  - Handle anonymous functions
- **Complexity:** High
- **Dependencies:** Functions

---

## Command Types (tree_command subclasses)

### Priority 1: Control Flow

#### 4.1 If Command (`tree_if_command`)
**File:** `libinterp/parse-tree/pt-select.h`
- **Description:** Conditional statements (if/elseif/else)
- **IR Generation:**
  - Generate condition evaluation
  - Create basic blocks for each branch
  - Implement if/elseif/else chain
  - Handle empty else clauses
- **Complexity:** Medium
- **Dependencies:** Boolean expressions, Statement lists

#### 4.2 While Command (`tree_while_command`)
**File:** `libinterp/parse-tree/pt-loop.h`
- **Description:** While loops (while condition ... end)
- **IR Generation:**
  - Create loop header block
  - Generate condition check
  - Create loop body block
  - Generate back edge
  - Handle break/continue
- **Complexity:** Medium
- **Dependencies:** Boolean expressions, Statement lists

#### 4.3 For Command (`tree_simple_for_command`, `tree_complex_for_command`)
**File:** `libinterp/parse-tree/pt-loop.h`
- **Description:** For loops (for i = 1:10 ... end)
- **IR Generation:**
  - Generate loop variable initialization
  - Create loop header with condition
  - Generate loop body
  - Generate loop variable increment
  - Create back edge
  - Handle break/continue
- **Complexity:** High
- **Dependencies:** Colon expressions, Identifiers, Statement lists

#### 4.4 Do-Until Command (`tree_do_until_command`)
**File:** `libinterp/parse-tree/pt-loop.h`
- **Description:** Do-until loops (do ... until condition)
- **IR Generation:**
  - Create loop body block
  - Generate condition check at end
  - Create back edge
- **Complexity:** Medium
- **Dependencies:** Boolean expressions, Statement lists

### Priority 2: Jump Commands

#### 5.1 Break Command (`tree_break_command`)
**File:** `libinterp/parse-tree/pt-jump.h`
- **Description:** Break from loop
- **IR Generation:**
  - Branch to loop exit block
- **Complexity:** Low
- **Dependencies:** Loop structure

#### 5.2 Continue Command (`tree_continue_command`)
**File:** `libinterp/parse-tree/pt-jump.h`
- **Description:** Continue to next loop iteration
- **IR Generation:**
  - Branch to loop header
- **Complexity:** Low
- **Dependencies:** Loop structure

#### 5.3 Return Command (`tree_return_command`)
**File:** `libinterp/parse-tree/pt-jump.h`
- **Description:** Return from function
- **IR Generation:**
  - Generate return value
  - Create return instruction
- **Complexity:** Low
- **Dependencies:** Function structure

### Priority 3: Exception Handling

#### 6.1 Try-Catch Command (`tree_try_catch_command`)
**File:** `libinterp/parse-tree/pt-except.h`
- **Description:** Try-catch blocks
- **IR Generation:**
  - Create try block
  - Create catch block
  - Handle exception propagation
  - Implement exception handling
- **Complexity:** Very High
- **Dependencies:** Exception system

#### 6.2 Unwind Protect Command (`tree_unwind_protect_command`)
**File:** `libinterp/parse-tree/pt-except.h`
- **Description:** Unwind-protect (cleanup code)
- **IR Generation:**
  - Create protected block
  - Create cleanup block
  - Ensure cleanup executes
- **Complexity:** Very High
- **Dependencies:** Exception system

### Priority 4: Switch Command

#### 7.1 Switch Command (`tree_switch_command`)
**File:** `libinterp/parse-tree/pt-select.h`
- **Description:** Switch-case statements
- **IR Generation:**
  - Generate switch value
  - Create case blocks
  - Implement case matching
  - Handle otherwise/default case
  - Generate switch instruction or if-else chain
- **Complexity:** Medium
- **Dependencies:** Expressions, Statement lists

### Priority 5: Declarations

#### 8.1 Declaration Command (`tree_decl_command`)
**File:** `libinterp/parse-tree/pt-decl.h`
- **Description:** Variable declarations (global, persistent)
- **IR Generation:**
  - Mark variables as global/persistent
  - Initialize variables
- **Complexity:** Low
- **Dependencies:** Symbol table

### Priority 6: Parallel Computing

#### 9.1 SPMD Command (`tree_spmd_command`)
**File:** `libinterp/parse-tree/pt-spmd.h`
- **Description:** Single Program Multiple Data blocks
- **IR Generation:**
  - Handle parallel execution
  - Distribute work
- **Complexity:** Very High
- **Dependencies:** Parallel runtime

---

## Function Calls

### Priority 1: Basic Function Calls

#### 10.1 Function Calls (via `tree_index_expression`)
- **Description:** Function invocation (f(x, y), sin(pi))
- **IR Generation:**
  - Generate arguments
  - Lookup function
  - Call function (built-in or user)
  - Handle return values
  - Support multiple return values
- **Complexity:** Very High
- **Dependencies:** Index expressions, Function lookup, Runtime

---

## Special Features

### Priority 1: Type System

#### 11.1 Dynamic Typing
- **Description:** Octave's dynamic type system
- **IR Generation:**
  - Type inference
  - Runtime type checks
  - Type specialization
  - Boxing/unboxing
- **Complexity:** Very High
- **Dependencies:** All expressions

#### 11.2 Array Operations
- **Description:** Matrix/array operations
- **IR Generation:**
  - Vectorization
  - Broadcasting
  - Element-wise operations
  - Matrix operations
- **Complexity:** Very High
- **Dependencies:** Arrays, Binary expressions

### Priority 2: Advanced Features

#### 12.1 Variable Arguments (varargin/varargout)
- **Description:** Variable number of arguments
- **IR Generation:**
  - Handle variable argument lists
  - Pack/unpack arguments
- **Complexity:** High
- **Dependencies:** Function calls

#### 12.2 Nested Functions
- **Description:** Functions defined inside other functions
- **IR Generation:**
  - Handle closure capture
  - Access outer scope variables
- **Complexity:** Very High
- **Dependencies:** Scoping, Functions

#### 12.3 Anonymous Functions
- **Description:** Lambda functions
- **IR Generation:**
  - Create function object
  - Capture variables
- **Complexity:** High
- **Dependencies:** Functions, Closures

---

## Implementation Phases

### Phase 1: Foundation (Priority 1 Expressions)
**Goal:** Support simple arithmetic and assignments

1. Constants (`tree_constant`)
2. Identifiers (`tree_identifier`)
3. Binary expressions (`tree_binary_expression`) - basic arithmetic
4. Unary expressions (`tree_unary_expression`)
5. Simple assignment (`tree_simple_assignment`)

**Expected Result:** Can compile functions like:
```octave
function y = add(a, b)
  y = a + b;
end
```

### Phase 2: Control Flow (Priority 1 Commands)
**Goal:** Support conditionals and loops

1. If command (`tree_if_command`)
2. While command (`tree_while_command`)
3. For command (`tree_simple_for_command`)
4. Break/Continue commands
5. Return command

**Expected Result:** Can compile functions with conditionals and loops:
```octave
function s = sum_to_n(n)
  s = 0;
  for i = 1:n
    s = s + i;
  end
end
```

### Phase 3: Arrays and Indexing
**Goal:** Support array operations

1. Index expressions (`tree_index_expression`) - basic indexing
2. Matrix expressions (`tree_matrix`)
3. Colon expression (`tree_colon_expression`)
4. Array operations in binary expressions

**Expected Result:** Can compile functions with arrays:
```octave
function y = array_sum(x)
  y = 0;
  for i = 1:length(x)
    y = y + x(i);
  end
end
```

### Phase 4: Function Calls
**Goal:** Support calling other functions

1. Function call via index expression
2. Built-in function calls
3. User function calls
4. Multiple return values

**Expected Result:** Can compile functions that call other functions:
```octave
function y = compute(x)
  y = sin(x) + cos(x);
end
```

### Phase 5: Advanced Features
**Goal:** Support advanced Octave features

1. Cell arrays
2. Structures
3. Switch statements
4. Try-catch
5. Variable arguments
6. Nested functions
7. Anonymous functions

---

## Implementation Strategy

### For Each Node Type:

1. **Create IR Generation Method**
   - Add method to `jit_llvm_codegen` class
   - Signature: `llvm::Value* generate_ir_for_X(tree_X* node, llvm::IRBuilder<>& builder)`

2. **Handle Type Conversion**
   - Convert Octave types to LLVM types
   - Handle type promotion
   - Support dynamic typing

3. **Generate LLVM IR**
   - Use LLVM IRBuilder API
   - Create appropriate instructions
   - Handle control flow

4. **Integration**
   - Call from main `generate_ir()` method
   - Handle errors gracefully
   - Fall back to interpreter if needed

5. **Testing**
   - Create test cases
   - Verify correctness
   - Performance benchmarks

---

## File Organization

### New Files to Create:

1. `libinterp/jit/jit-ir-generator.h/cc`
   - Main IR generation class
   - Visitor pattern for parse tree traversal
   - Type conversion utilities

2. `libinterp/jit/jit-ir-expr.h/cc`
   - Expression IR generation methods
   - One method per expression type

3. `libinterp/jit/jit-ir-cmd.h/cc`
   - Command IR generation methods
   - One method per command type

4. `libinterp/jit/jit-ir-types.h/cc`
   - Type system for IR generation
   - Octave to LLVM type mapping
   - Type promotion rules

5. `libinterp/jit/jit-ir-runtime.h/cc`
   - Runtime helper functions
   - Function call interface
   - Array operations

---

## Estimated Complexity

| Category | Nodes | Complexity | Estimated Effort |
|----------|-------|------------|-----------------|
| Basic Expressions | 5 | Low-Medium | 2-3 weeks |
| Control Flow | 5 | Medium | 2-3 weeks |
| Arrays/Indexing | 4 | High | 3-4 weeks |
| Function Calls | 1 | Very High | 2-3 weeks |
| Advanced Features | 7 | Very High | 4-6 weeks |
| **Total** | **22** | - | **13-19 weeks** |

---

## Notes

- Start with simple cases and expand incrementally
- Each phase should produce working code
- Test thoroughly before moving to next phase
- Performance optimization can come later
- Some features may require interpreter fallback initially

---

## References

- Parse tree headers: `libinterp/parse-tree/pt-*.h`
- LLVM IR Documentation: https://llvm.org/docs/LangRef.html
- Octave evaluation: `libinterp/parse-tree/pt-eval.cc`