layout: true class: typo, typo-selection --- count: false class: nord-dark, middle, center # Understanding Compilers: LLVM IR & MLIR π @luk036 π¨βπ» Β· 2026 π --- ## Welcome! ππ * **Title:** Understanding Compilers: LLVM IR & MLIR * **Goal:** Demystify Intermediate Representations (IRs) and how they power modern compilers. π§ * **Key takeaway:** Reading IR reveals how the compiler *thinks* about your code. π --- ### Why Care About Compiler IRs? π€ * **For Performance Critical Code:** Understanding your optimizer's IR is a useful tool. β‘ * **Beyond Assembly:** ποΈ * Reading assembly helps understand what your *processor* is doing. π» * Learning LLVM IR helps understand what your *compiler* is doing to create highly optimized code. π οΈ * **Developer Productivity:** Compilers are fundamental tools that boost developer productivity by automating the conversion between different levels of abstraction. οΏ½ --- ### What is LLVM? π οΈποΈ * **Umbrella Name:** "LLVM" is an umbrella name for a number of software components used to build compilers. π * **Flagship Product:** Clang, a high-end C/C++/Objective-C compiler. π * **Compiler Architecture:** Clang follows the orthodox compiler architecture: π 1. **Frontend (Parser):** Parses source code into an Abstract Syntax Tree (AST). π³ 2. **Lowering:** Converts AST into an **Intermediate Representation (IR)**. β¬οΈ 3. **Optimizer (Middle-end):** Transforms IR into "better" IR. β¨ 4. **Backend (llc):** Converts IR into machine code for a particular platform. πΎ --- .mermaid[ <pre> graph TD A["Source Code (.c file)"] --> B[AST]; B --> C[LLVM IR]; C --> D[Assembly]; subgraph Clang-Frontend A -- parser --> B; B -- lowering --> C; end subgraph LLVM C -- "optimizer (opt)" --> C; C -- "backend (llc)" --> D; end A:::source B:::ast C:::ir D:::asm classDef source fill:#FFD700, stroke:#FFA500, stroke-width:2px, color:#000; classDef ast fill:#87CEFA,stroke:#1E90FF,stroke-width:2px; classDef ir fill:#98FB98,stroke:#3CB371,stroke-width:2px; classDef asm fill:#FFA07A,stroke:#FF6347,stroke-width:2px; </pre> ] --- ### LLVM IR: The Core Language ππ§ * **Popular & Well-Documented:** LLVM IR is very popular, well-documented, and reasonably well-specified, allowing it to be treated as a programming language. π * **Compilation Target:** It's a very good compilation target due to its documentation and stability, allowing language implementers to reuse thousands of engineering hours. β³ * **Forms:** LLVM IR exists as a binary format (bitcode) and a human-readable text format (using `.ll` extension). π½π * Compilers like Clang (`clang++ -S -emit-llvm foo.cc`) and Rust (`rustc --emit=llvm-ir foo.rs`) can emit LLVM IR. π― * **Strongly Typed:** Unlike most assembly languages, LLVM IR is strongly typed and requires explicit type annotations almost everywhere. π·οΈ --- ### LLVM IR: Basic Structure π𧩠* **Function Definitions:** Introduced with `define`. ποΈ * Example: `define void @do_nothing () { ret void }`. π * **External Symbols:** `declare` brings external symbols (functions without a body) into scope, similar to C. π * **Sigils:** User-defined symbols start with a sigil indicating type: π£ * `@`: Global and functions (addressable, `ptr`-typed when used as a value). π * `%`: Local variables, often called "registers" (LLVM IR is like assembly for an abstract machine with infinite registers). πΎ --- ### LLVM IR: Basic Structure π𧩠* **Primitive Types:** 𧱠* `iN`: Arbitrary-bit integers (e.g., `i32`, `i64`). No inherent signed/unsigned, defined by instructions. `i1` is used for booleans. π’ * `void`: Only used as a return value. π³οΈ * `ptr`: Untyped pointer. π * **Arithmetic Operations:** `add`, `sub`, `mul`, `and`, `or`, `xor`, `shl`, `sdiv`, `udiv`, `srem`, `urem`, `ashr`, `lshr`. βββοΈ * **Type Conversion:** `trunc`, `zext` (zero-extend), `sext` (sign-extend). π --- ### LLVM IR: Control Flow ππ * **Function Body:** Resembles assembly β a list of labels and instructions. π * **Basic Blocks:** A sequence of non-control flow operations, ending with a control flow instruction. They form the Control Flow Graph (CFG). 𧱠* **Branch Instruction (`br`):** General branch operation. πΏ * Conditional: `br i1 %cond, label %a, label %b` (if/else). π€ * Unconditional: `br label %a` (simple goto). π * **Switch Instruction (`switch`):** Similar to C switch, easier for LLVM to generate jump tables. π * **`unreachable` Instruction:** Represents a codepath the compiler assumes is never executed. Triggers undefined behavior (UB) upon being called. β οΈ * Used in dead code elimination (DCE): `unreachable`s "bubble upwards" in the CFG, dissolving parts of it. π --- ### LLVM IR: SSA ππ * **Static Single Assignment (SSA):** Every register is assigned by at most one instruction per function. β * **Advantages:** Simplifies optimizations like global value numbering and constant-folding. π― * Mutation is reinterpreted as "versions" of a variable (e.g., `%x.1 = add i32 %x.0, %y.0`). π * **Phi Nodes (`phi`):** Handle values where control flow merges (e.g., in loops). π * Selects a value based on which basic block was jumped from. ποΈ * Can refer to values not defined in all dominating blocks, allowing dynamic versions. π --- ### LLVM IR: SSA Phi Merge .mermaid[ <pre> graph TD BBA["Basic Block A"] --> PHI["%x.1 = phi\n[ %x.0, BB-A ], [ %x.2, BB-B ]"] BBB["Basic Block B"] --> PHI PHI --> USE["%result = add i32 %x.1, %y.1"] style BBA fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style BBB fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style PHI fill:#fff9c4,stroke:#f57f17,stroke-width:3px style USE fill:#ffccbc,stroke:#bf360c,stroke-width:3px </pre> ] --- ### LLVM IR: Aggregates & Other Operations ποΈπ§© * **Aggregate Types:** 𧱠* `[n x T]`: Arrays (e.g., `[1024 x i8]`). π¦ * `{T1, T2, ...}`: Structs (fields indexed, no names). `<{...}>` for packed structs. ποΈ * `<n x T>`: Vectors (for SIMD operations). β * **Aggregate Operations:** π οΈ * `insertvalue`, `extractvalue`: Statically access/change struct/array fields (does *not* mutate in-place due to SSA). π * **`getelementptr` (GEP):** Pointer arithmetic instruction. π * Calculates an offset pointer into a struct or array. π * Takes an untyped pointer, has an extra index parameter (even for single elements), and explicit types for indices. π’ --- ### LLVM IR: Aggregates & Other Operations ποΈπ§© * **Function Calls:** `call`, `invoke` (for C++ `try {}` blocks). π * **Synchronization:** `load atomic`, `store atomic`, `fence`, `cmpxchg` (CAS), `atomicrmw` (read-modify-write). βοΈ * Can be marked `volatile` (compiler-invisible side-effects). π₯ * **Reinterpret Operations:** π * `bitcast`: Converts non-aggregate types of same bit width (e.g., `double` to `i64`). Used to cast pointer types before opaque pointers were standard. π * `inttoptr`, `ptrtoint`: Convert between pointer and integer data (sketchy semantics). π€Ή * **Intrinsics:** Functions starting with `llvm.` (e.g., `llvm.memcpy`). π© --- ### LLVM IR: Undefined Behavior & Poison β οΈπ * **Purpose of UB:** LLVM declares certain machine states "impossible" to enable optimizations and simplify code. π * **Examples:** `unreachable` execution, division by zero, out-of-bounds memory access. π« * **Poisoned Values:** Many LLVM UBs factor through "poisoned values". β£οΈ * A poison value can "take on every value at once," convenient for optimization. π * Using a poison value (e.g., as a pointer in `load`/`store`/`call`, or as a denominator in `udiv`, or in `br`/`switch`) *must* be UB. β οΈ * LLVM can propagate UB forward through dataflow analysis (e.g., "time traveling UB"). β³ * **Poison Generation:** Many operations generate poison instead of defined behavior (e.g., `add nsw` for signed overflow). β * `udiv exact`, `getelementptr inbounds`, `nnan`/`ninf` fp operations. π * **Key Distinction:** Creating poison is *not* UB; *only using it is*. This is weaker than C's UB, allowing more reordering and simplification of operational semantics. βοΈ --- ### LLVM IR: The Other Side of the Coin πͺβοΈ * **Centralization:** LLVM IR's role as the central IR for frontends and backends creates a high bar for changing the IR itself. π― * **Forks:** Leads to many different flavors of LLVM forks, which are costly to maintain and update. π * **Evolution vs. Compatibility:** LLVM IR co-evolves with analyses and transformations, resulting in weak compatibility guarantees. β³ * **Hardware Drivers:** Not ideal for device drivers (e.g., in cell phones) where updates are infrequent, leading to compatibility issues. π± * **SPIR Example:** Standard Portable Intermediate Representation (SPIR) tried to use LLVM IR but found it unsuitable for bridging software and hardware, leading to SPIR-V. π * **Domain Specificity:** The fundamental problem is strong coupling across application domains and compiler transformation paths. 𧩠* LLVM's design, while good for general languages, struggles to provide top performance for *all* applications and specialized hardware. π― --- ### Enter MLIR: Multi-Level IR ππ * **What is MLIR?** An open-source compiler infrastructure project developed as a sub-project of LLVM. ποΈ * **Purpose:** Provides a modular and extensible IR framework to facilitate building domain-specific compilers and improve compilation for heterogeneous computing platforms. 𧩠* **Origin:** Developed by Chris Lattner at Google in 2018 to address challenges in building compilers for modern workloads like machine learning, hardware acceleration, and high-level synthesis. π * It was open-sourced as part of the LLVM monorepository in 2019. π * **Multi-Level:** MLIR models computations at various abstraction levels and progressively lowers them toward machine code. β¬οΈ * **Beyond ML:** While it serves machine learning, MLIR is a general-purpose compiler infrastructure for any domain ("ML" stood for "everything but Machine Learning" initially). π --- ### MLIR Core Concepts: Operations * **Operations (Ops):** The fundamental unit in MLIR. βοΈ * Fully extensible; no fixed list of operations. β * Represent concepts from high-level (function definitions, ML graphs) to low-level (target-specific instructions). π * **SSA-based:** Values are results of exactly one operation or block argument. MLIR avoids traditional PHI nodes by using block arguments in conjunction with control-flow operation operands. π * Can return zero or more results, take zero or more operands, have attributes and properties, and contain regions. ποΈ --- ### MLIR Core Concepts: Regions * **Regions:** Ordered lists of MLIR Blocks. ποΈ * Contained within operations, enabling hierarchical structures. ποΈ * **Encapsulation:** Values defined in a region do not escape to the enclosing region. π‘οΈ * **Types of Regions:** π * **SSACFG Regions:** Describe control flow between blocks (like traditional basic blocks in LLVM IR). Control flow enters via the "entry" block. πͺ * **Graph Regions:** For concurrent semantics without control flow, or modeling generic directed graphs. Only contain a single basic block. πΈοΈ --- ### MLIR Hierarchy .mermaid[ <pre> graph TD MOD[ModuleOp] --> FUNC{Operation\ne.g., FuncOp} FUNC --> REG[Region\nordered list of blocks] REG --> BLK[Block\nentry block + args] BLK --> OP[Operation\n...] OP -.->|"can contain"| REG style MOD fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style FUNC fill:#fff9c4,stroke:#f57f17,stroke-width:3px style REG fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style BLK fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style OP fill:#ffccbc,stroke:#bf360c,stroke-width:3px </pre> ] --- ### MLIR Core Concepts: Dialects β¨π£οΈ * **The Key to Extensibility:** Dialects are MLIR's primary mechanism for extensibility. π * **Logical Grouping:** A dialect is a self-contained namespace of: ποΈ * **Operations** βοΈ * **Types** π·οΈ * **Attributes** π¨ * **Other constructs** 𧩠* **Defining Rules and Semantics:** Dialects provide: π * **Verifiers** for operation invariants (e.g., `toy.print` must have a single operand). βοΈ * **Semantics** (e.g., `has-no-side-effects`, `constant-folding`, `CSE-allowed`). π * **Passes** (analysis, transformations, dialect conversions). π * Possibly custom parser and assembly printer for readability. π * **Co-existence:** Multiple dialects can co-exist within one module. π€ * **Examples of Built-in Dialects:** `arith`, `memref`, `affine` (for polyhedral optimization), `scf` (structured control flow), `func`, `gpu`, `tosa`, and even `llvm` (mapping to LLVM IR). π --- ### MLIR: Traits & Interfaces π€π * **Traits:** Mixins that define additional functionality, properties, and verification on an Attribute/Operation/Type. π¨ * Indicate that an operation satisfies certain properties (e.g., `Commutative`, `Terminator`, `ZeroOperands`). βοΈ * Presence checked opaquely by analyses/transformations. π * **Interfaces:** Abstract classes that allow opaque manipulation of MLIR entities. ποΈ * Group of methods implemented by an attribute/dialect/operation/type. 𧩠* **Cornerstone of Extensibility & Reusability:** Allow generic transformation passes to operate on operations without knowing their actual implementation, relying only on interface properties. β»οΈ * Example: `CallOpInterface` for callgraph modeling, `ShapeInferenceOpInterface`. π * Dialects implement interfaces to enable and reuse generic transformations. π --- ### MLIR: Progressive Lowering β¬οΈποΈ * **Multi-level Abstraction:** MLIR enables dialects and operations to model concepts at different abstraction levels (vertically). π * **Seamless Flow:** Different levels can be represented using the same infrastructure, making the flow between them seamless. π * **Lowering Process:** π * **Dialect Conversion:** The primary mechanism for lowering, converting operations from source dialects into "legal" target dialects. π§ * **Operation Conversion:** Dag-to-Dag rewrite patterns transform illegal ops to legal ones. π οΈ * **Type Conversion:** Transforms illegal types to legal ones. π * **Modes:** Can be `Partial` (subset of operations converted) or `Full` (all operations converted). βοΈ * **Benefits:** β¨ * Separates concerns, allowing each layer to focus on a dedicated task. * Avoids lowering too early and losing high-level information. β³ * Allows mixing levels of abstraction (e.g., Toy dialect ops cohabiting with affine and other ops in the same function). π€ --- ### MLIR: Progressive Lowering Flow .mermaid[ <pre> graph LR HL["High-Level\nDialect Ops"] -->|"Dialect Conversion\n(Dag-to-Dag rewrites)"| ML["Mid-Level\nDialect Ops"] ML -->|"Partial / Full Conversion"| LL["Low-Level\nDialect Ops"] LL -->|"Type Conversion"| TGT["Target\n(e.g., LLVM IR)"] style HL fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style ML fill:#fff9c4,stroke:#f57f17,stroke-width:3px style LL fill:#fff9c4,stroke:#f57f17,stroke-width:3px style TGT fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px </pre> ] --- ### MLIR in Action: Ecosystem & Applications π * **Growing Ecosystem:** MLIR has fostered a vibrant open-source ecosystem, production compilers, and experimental toolchains. π± * **Key Applications:** π― * **Machine Learning:** TensorFlow/XLA, IREE, torch-mlir, ONNX-MLIR, TPU-MLIR, Triton-MLIR. π€ * **Systems Programming Languages:** Mojo (integrates Python syntax with low-level performance, built on MLIR). π * **Hardware Design:** CIRCT project for high-level synthesis. π₯οΈ * **Runtimes:** TFRT. β‘ * **Research:** Quantum computing, homomorphic encryption. π¬ * **"Dialects, dialects, dialects":** The infrastructure helps define operations and form logical groups (dialects) based on functionality. π£οΈ --- ### The Future: Democratizing AI Compute? π * **Unbundling Compilers & IRs:** MLIR aims to further decouple compilers, breaking down monolithic IRs into mixable dialects. 𧩠* Enables defining new "partial" IRs easily. β * Developing domain-specific compilers could become as simple as choosing, customizing, and mixing existing dialects. π οΈ * **Challenges:** β οΈ * Early explosion of AI-specific dialects created fragmentation and made some designs not ideal for evolving requirements (e.g., GenAI, PyTorch support). π₯ * Identity crisis: Is MLIR a general compiler framework or an AI solution? π€ * Governance and corporate rivalries have complicated its evolution towards a unified end-to-end AI solution. π’ * **The Vision:** MLIR seeks to harmonize compute across many different hardware makers and accelerate development of domain-specific solutions. π --- ### Key Takeaways & Discussion π―π‘ * **LLVM IR:** Powerful, well-documented, SSA-based, but its monolithic nature and weak compatibility can be limiting for specialized domains. βοΈ * **MLIR:** A framework for *building* compilers, offering multi-level abstraction, extensible dialects, and reusable infrastructure (operations, regions, traits, interfaces). ποΈ * **The Evolution:** From single, monolithic IRs to modular, decentralized approaches, allowing greater flexibility and domain-specific optimizations. π --- ### Thank You! Questions? πβ * **MLIR Project Website:** [https://mlir.llvm.org/](https://mlir.llvm.org/) π * **LLVM Project Website:** [https://llvm.org/](https://llvm.org/) π * **Sources Consulted:** π * "A Gentle Introduction to LLVM IR - mcyoung" π * "Compilers and IRs: LLVM IR, SPIR-V, and MLIR - Lei.Chat()" π¬ * "MLIR (software) - Wikipedia" π§ * "MLIR For Beginners: A series of articles on the MLIR framework - Hacker News" π * "MLIR Language Reference" π * "MLIR dialect design best practise? : r/Compilers - Reddit" π¬ * "MLIR: Multi-Level Intermediate Representation - LLVM" ποΈ * "Open Projects - MLIR - LLVM" πͺ * "What about the MLIR compiler infrastructure? (Democratizing AI Compute, Part 8) - Modular" π€ * "Writing an LLVM Pass β LLVM 21.0.0git documentation" π