Proposal: UnifiedIR for Julia

Author: Keno
Status: WIP/RFC (Work In Progress / Request for Comments)
PR Reference: #62334

---

🚩 The Motivation

The current Intermediate Representation (IR) data structures within Base are roughly a decade old. While they have been resilient, they now present significant bottlenecks:

1. Usability Issues: The API design is cumbersome, particularly regarding semantic ownership and invalidation.
2. Lack of Extensibility: The system cannot easily adapt to new ecosystem requirements, forcing developers to rely on clunky hacks or build entirely separate IR structures.
3. Internal Focus: The original design was never intended to be an externally facing system.

"Our current IR data structures in Base are about 10 years old... it was never design to be an externally facing system at all."

---

🛠️ Introducing UnifiedIR

To resolve these issues, this PR proposes UnifiedIR. This is a new top-level package that serves as a self-contained, extensible substrate for IR operations. It is designed to be used by both the Julia core and the broader ecosystem.

Architecture Overview

UnifiedIR is a dialect-aware, region-based IR (drawing inspiration from MLIR), though it preserves the effective elements of the original Julia IR and JuliaLowering designs.

What is being replaced?

The goal is to consolidate several disparate structures into one:

---

⚙️ Technical Deep Dive

Core Design & Extensibility

The foundation is a core data structure providing an efficient IR representation. Users can extend this by adding additional columns (one entry per statement).

To handle different application needs, UnifiedIR utilizes layered views:

• IncrementalCompact: Optimized for fast, one-pass replacement operations.
• LLVM-like: Uses linked lists to maintain ordering, simplifying complex Control Flow Graph (CFG) transformations.
  • Note: To avoid the $\mathcal{O}(n^2)$ quadratic order maintenance penalty common in LLVM for massive functions, a specialized algorithm (developed by Keno and Claude) has been implemented.
• Graph-like: An embedding for lowering and array compilers (IR without CFG dependencies).
• Tree-like: An encoding for lowering where every statement has exactly one user (except the root).

Advanced Features

• Regions: First-class support for regions facilitates better MLIR integration and simplifies the implementation of issues like #58532.
• Dialects: First-class support for dialect extensions.

---

💻 Implementation Details (from AttrGraph)

The underlying substrate, AttrGraph, employs a sophisticated storage model:

# Conceptual layout of the UnifiedIR substrate
struct AttrGraph
    kind_column::Vector{Kind}
    operand_words::PackedTwoModeWords # Packed for efficiency
    operand_pool::TaggedPool          # Shared storage
    attribute_universes::OpenColumns  # Extensible metadata
end

Key Technical Specs:

• Layout States: The IR transitions through builder $\rightarrow$ dense $\rightarrow$ editable $\rightarrow$ floating.
• Renaming: There are exactly two renaming points.
• Registry: A namespaced kind registry with reserved dialect IDs for the bootstrap stack.
• Tree Porcelain: Includes Tree/NodeList cursors, mapchildren, copy_ast, and provenance walks via :source chains.
• Memory Management: Implements compact_graph! and collect_syntax! as a form of "compact-as-GC."

---

📈 Current Progress & Roadmap

This PR is currently a preview intended to spark discussion.

Task List

• Port Inference to UnifiedIR
• Port Optimizer to UnifiedIR
• Port JuliaLowering to UnifiedIR
• Enable for bootstrap
• Adapt codegen and interpreter (currently out of scope)
• Validate the new order maintenance algorithm

Current Testing Status: Approximately 50% of the test suite has been run successfully with the new compiler version.

---

🖼️ Visuals & Contributors

Collaborators:

• Keno (Lead)
• Claude (Algorithm assistance)