Code Representation

Code representation bridges human-readable source code and executable target instructions. Compilers parse and lower source code through multiple levels of Intermediate Representation (IR) to analyze semantics and apply performance optimizations.

Abstract Syntax Tree (AST)

An Abstract Syntax Tree (AST) is a hierarchical, tree-structured representation of source code produced during syntactic analysis. It strips away purely syntactic tokens (such as semicolons, explicit parentheses, and whitespace) while retaining structural semantics, operator precedence, and parent-child execution scopes.

Nodes: Represent structural constructs such as operators (+, *), statements (if, while), or expressions (BinaryOp).
Leaves: Represent terminal operands, such as variable names (Name) or literals (Constant).
Usage: Used by parsers, linters, semantic analyzers, static security checkers, and source-to-source compilers.

List of Instructions

Lowering an AST into a linear List of Instructions flattens the tree structure into sequential abstract machine instructions. This flat Intermediate Representation (IR) often uses Three-Address Code (3AC) or register-based bytecode instructions where each operation has at most three operands.

Characteristics: Simple instruction semantics (e.g., LOAD, ADD, STORE, JUMP_IF_FALSE).
Usage: Simplifies register allocation, instruction selection, and target machine code emission. In Numba, Python AST is lowered into Numba IR instructions (such as jump, branch, call, and assignment operations) before being passed to LLVM.

Control Flow Graph (CFG)

A Control Flow Graph (CFG) is a directed graph $(V, E)$ that explicitly models all possible execution paths through a program unit (such as a function or subroutine).

Nodes ($V$): Basic Blocks containing sequential instructions.
Edges ($E$): Control transfers via conditional branches, unconditional jumps, or function calls.

Basic Blocks

Basic blocks are sequences of instructions with no branches except at the end. They are the building blocks of control flow graphs.

CFG is applied to basic blocks.

Direction vector (Dependence Vector)

A Direction vector is a mathematical representation of the direction of data dependencies between statements in a program. It captures the relationships between statements that read and write shared variables, indicating how data flows through the program. Each vector component corresponds to a loop level, and its value indicates the distance (in iterations) between the source and target statements.

Function compute_dependence_vector(producer_slice, consumer_slice, active_loops):
    If active_loops is empty: return None, None

    Collect all variable names present in producer and consumer slices
    Initialize distance_vector and direction_vector lists
    Is_self_dep = (producer_slice == consumer_slice)

    For each loop_var in active_loops:
        If loop_var is in subscript_vars:
            dist = 0 (if self-dep) or calculate offset difference (if inter-statement)
        Else:
            dist = 1 (indicates loop-carried recurrence)

        Append dist to distance_vector
        Determine direction symbol ('<', '>', or '=') based on dist and append to direction_vector

    Return tuple(distance_vector), tuple(direction_vector)

Example

Consider the following code snippet:

for (int i = 1; i < N; i++) {
    for (int j = 1; j < N; j++) {
        A[i][j] = A[i - 1][j + 1] + 1; // Read from (i-1, j+1), Write to (i, j)
    }
}

The direction vector for the dependency from the read at (i-1, j+1) to the write at (i, j) is (<, >), indicating that the dependency is carried across iterations of both loops.

Data Dependence Graph (DDG)

A Data Dependence Graph (DDG) is a directed graph $(V, E)$ where nodes represent program statements or instructions, and edges represent data dependencies between them. An edge from node $u$ to node $v$ indicates that $v$ depends on the output of $u

The algorithm for constructing DDG is as follows:

Function generate_ddg_with_vectors(node, active_loops=[], state=None):
    If state is None:
        Initialize state with empty DiGraph, last_def dict, last_uses dict, slice_registry, and stmt_counter = 0

    Unwrap node body (Module, list of statements, or single statement)

    For each statement in body:
        If statement is FunctionDef or AsyncFunctionDef:
            Recursively call generate_ddg_with_vectors(stmt.body, active_loops, state)
            Continue

        If statement is For Loop:
            Extract loop_var from loop target
            New_loops = active_loops + [loop_var]
            Recursively call generate_ddg_with_vectors(stmt.body, new_loops, state)
            Continue

        If statement is If or While:
            Recursively call generate_ddg_with_vectors(stmt.body / orelse, active_loops, state)
            Continue

        # Process regular statement
        idx = state.stmt_counter
        Add statement node to DDG graph with its AST and active loop nest

        Run DefUseVisitor on statement to extract defs, uses, and subscripts
        Register subscript slices for this statement index

        # 1. Check True Dependencies (RAW: Read-After-Write)
        For each variable v in statement.uses:
            If v is in state.last_def:
                prev_idx = state.last_def[v]
                Add dependence edge (prev_idx -> idx) of type 'RAW' for variable v
            Else if active_loops and v in statement.defs:
                # Self-dependence recurrence (e.g., C[i][j] += ...)
                Add dependence edge (idx -> idx) of type 'RAW' for variable v

        # 2. Check Output Dependencies (WAW: Write-After-Write)
        For each variable v in statement.defs:
            If v is in state.last_def and prev_idx != idx:
                prev_idx = state.last_def[v]
                Add dependence edge (prev_idx -> idx) of type 'WAW' for variable v
            Else if active_loops and v in statement.uses:
                Add dependence edge (idx -> idx) of type 'WAW' for variable v

        # Update tracking state
        For each variable v in statement.defs:
            state.last_def[v] = idx
        For each variable v in statement.uses:
            Add idx to state.last_uses[v]

        Increment state.stmt_counter

    Return DDG graph