# 009 — LLVM Backend

- **Status:** Draft
- **Normative language:** `MUST`, `MUST NOT`, `SHOULD`, `SHOULD NOT`, and `MAY` are to
  be interpreted as described in RFC 2119.

## 1. Purpose

The LLVM backend (`vct.backend.llvm`) translates optimized VIR into textual LLVM IR
(the `.ll` assembly format). It is the alternate backend. It runs **after** VIR
optimization and is a pure translation: it performs no optimization and no discovery.
libVCT never invokes `llvm-as`, `opt`, or `llc`, and never links against LLVM.
Converting `.ll` to bitcode, an object file, or an executable is the caller's job.

## 2. Scope

This file specifies the backend's contract: 1:1 SSA mapping, the type mapping, the full
trait-to-attribute and trait-to-metadata mapping, intrinsic selection, module
scaffolding, the LLVM version pin, and determinism. The VIR input is specified in
[006 — VIR](006-vir.md); the optimizer that runs before this backend is specified in
[007 — VIR Optimizer](007-vir-optimizer.md). The C backend is specified in
[008 — C Backend](008-c-backend.md).

## 3. Definitions

| Term | Meaning |
|---|---|
| `.ll` | Textual LLVM assembly. |
| Opaque pointer | The LLVM `ptr` type, which carries no pointee type. |
| Target triple | The architecture/vendor/OS string that selects codegen. |
| Datalayout | The LLVM string describing primitive sizes, alignments, and endianness. |
| Metadata | `!name` nodes attached to instructions or the module. |
| `!range` | Metadata constraining the possible values of a load or call result. |

## 4. Model

VIR is already in SSA form, so the mapping to LLVM is **1:1**. There is no out-of-SSA
step here; that step exists only on the C path (see [008 — C Backend](008-c-backend.md)).
Each VIR block becomes one LLVM basic block, each VIR instruction becomes one LLVM
instruction, and each `Phi` becomes an LLVM `phi`.

The output is a **self-contained module**. It carries its own target triple and
datalayout, and it declares every external symbol it references before it defines
anything. A consumer can pass the module straight to `llvm-as` with no additional
environment.

## 5. Normative requirements

### 5.1 Purity and output

**R1.** The LLVM backend MUST perform pure translation. It MUST NOT run optimization,
inference, or discovery passes, and it MUST NOT modify the VIR it reads.

**R2.** The backend MUST emit textual `.ll` only. It MUST NOT invoke `llvm-as`, `opt`,
`llc`, or any other LLVM tool, and it MUST NOT link against LLVM libraries.

**R3.** The backend MUST emit a self-contained module that includes a target triple and
a datalayout derived from that triple.

**R4.** The backend MUST emit all declarations before any definition.

**R5.** For a fixed input and `Config`, the emitted module MUST be byte-identical across
runs and independent of thread count (see [000 — Overview](000-overview.md)).

### 5.2 SSA mapping

**R6.** The backend MUST map VIR constructs to LLVM constructs 1:1:

**Table 1. VIR to LLVM structural mapping**

| VIR | LLVM |
|---|---|
| Basic block | Basic block with a label |
| Instruction | Instruction, in the same order |
| `Phi(value, pred)` | `phi` with one incoming pair per predecessor |
| Conditional branch | `br i1 <cond>, label <t>, label <f>` |
| Switch | `switch` |
| Unconditional branch | `br label <target>` |
| Return | `ret` |
| Unreachable | `unreachable` |
| `alloca` | `alloca` |
| `load` | `load` |
| `store` | `store` |

**R7.** The backend MUST preserve block order given by the VIR module, and MUST preserve
instruction order within a block, so that the 1:1 mapping is observable in the text.

**R8.** Every VIR value MUST map to exactly one LLVM SSA name. Names MUST be generated
deterministically.

### 5.3 Types

**R9.** The backend MUST map VIR types to LLVM types as specified in Table 2.

**Table 2. VIR type to LLVM type**

| VIR type | LLVM type |
|---|---|
| Integer of N bits, signed or unsigned | `iN` |
| `f32` | `float` |
| `f64` | `double` |
| Pointer `T*` | `ptr` |
| Struct | `%struct.Name = type { ... }` |
| Union | `%union.Name = type { ... }` |
| Array `[N x T]` | `[N x T]` |
| `void` | `void` |
| Function type | `<ret> (<params>)` |

**R10.** The backend MUST pin LLVM 18 or later and MUST use **opaque pointers**. It MUST
NOT emit typed pointers such as `i32*`.

**R11.** Aggregate GEPs MUST use VIR field indices directly as LLVM struct indices. The
backend MUST NOT translate them to byte offsets.

**R12.** The backend MUST emit no `!llvm.dbg` metadata in v1. Debug mapping exists only
on the C path (see [008 — C Backend](008-c-backend.md)).

### 5.4 Traits to attributes and metadata

**R13.** The backend MUST map traits to LLVM attributes and metadata as specified in
Table 3. When a trait is absent, the matching attribute or metadata MUST NOT be emitted.

**Table 3. Trait to LLVM attribute and metadata mapping**

| Trait | LLVM attribute or metadata |
|---|---|
| `Restrict`, `NoAlias` | `noalias` parameter attribute plus `!alias.scope` and `!noalias` |
| `ReadOnly`, `NoWrite` | `readonly` |
| `WriteOnly`, `NoRead` | `writeonly` |
| `NoRead` + `NoWrite` | `readnone` (spelled `memory(none)` on LLVM 18) |
| `NonNull` | `nonnull` |
| `Align(n)` | `align n` |
| `Range(lo, hi)` | `!range` on loads and calls |
| `Assume(pred)` | `llvm.assume` |
| `NoInline`, `AlwaysInline` | `noinline` / `alwaysinline` |
| `TailCall`, `MustTail`, `NoTail` | `tail` / `musttail` / `none` |
| `NoReturn` | `noreturn` |
| `HotPath`, `ColdPath` | `!prof` |
| `Vectorize` | `!llvm.loop.vectorize.enable` |
| `Unroll(n)` | `!llvm.loop.unroll.count` |
| `Unreachable` | `unreachable` terminator |
| `NoUndef` | Reserved; see R14 |

The pairing mirrors the C mapping in [008 — C Backend](008-c-backend.md): a no-write fact takes a
read-only annotation, a no-read fact takes a write-only annotation, and their combination takes
`readnone`. `ReadOnly`/`WriteOnly` are region-level facts and `NoRead`/`NoWrite` are access-edge
primitives (see [002 — Traits](002-traits.md)); the emitted attribute follows the entity the trait
attaches to, whether a function or a pointer parameter.

**R14.** `NoUndef` is reserved and is only meaningful on the LLVM path. The backend MUST
NOT interpret it on the C path. When present here, it MUST translate to the
corresponding `noundef` attribute.

**R15.** The backend MUST emit real `llvm.assume` calls and real `!range` metadata; it
MUST NOT emit placeholders that a consumer would have to fill in.

### 5.5 Intrinsics

**R16.** The backend MUST lower the VIR intrinsics of [006 — VIR](006-vir.md) to the LLVM
intrinsics listed in Table 4.

**Table 4. VIR intrinsic to LLVM intrinsic**

| VIR intrinsic | LLVM intrinsic |
|---|---|
| `memcpy` | `llvm.memcpy.p0.p0.i64` |
| `memset` | `llvm.memset.p0.i64` |
| `memmove` | `llvm.memmove.p0.p0.i64` |
| `sqrt(f32/f64)` | `llvm.sqrt.f32` / `llvm.sqrt.f64` |
| `fabs(f32/f64)` | `llvm.fabs.f32` / `llvm.fabs.f64` |
| `ctpop(iN)` | `llvm.ctpop.iN` |
| `fshl(iN)` | `llvm.fshl.iN` |
| `sadd_sat`, `uadd_sat`, `ssub_sat`, `usub_sat` | `llvm.sadd.sat.iN`, `llvm.uadd.sat.iN`, `llvm.ssub.sat.iN`, `llvm.usub.sat.iN` |
| `sadd_overflow`, `uadd_overflow`, `ssub_overflow`, `usub_overflow`, `smul_overflow`, `umul_overflow` | `llvm.sadd.with.overflow.iN`, `llvm.uadd.with.overflow.iN`, `llvm.ssub.with.overflow.iN`, `llvm.usub.with.overflow.iN`, `llvm.smul.with.overflow.iN`, `llvm.umul.with.overflow.iN` |

**R17.** The backend MUST emit the declaration of every intrinsic it references before
the definition that calls it.

### 5.6 Module scaffolding

**R18.** The backend MUST emit a `target triple` line taken from the configured target
(see [010 — Driver & CLI](010-driver-cli.md)).

**R19.** The backend MUST emit a `target datalayout` line derived from that triple, so
the module is self-contained.

**R20.** The backend MUST emit declarations for all external functions and globals before
any definition.

**R21.** The backend SHOULD emit deterministic type and global names so that two runs
over the same module produce identical text.

## 6. Invariants

- **I1.** The emitted module is parseable by `llvm-as` for LLVM 18 or later.
- **I2.** There is a 1:1 correspondence between VIR blocks and instructions and the
  emitted LLVM blocks and instructions.
- **I3.** The module is self-contained: triple, datalayout, and all referenced
  declarations are present.
- **I4.** No typed pointers appear anywhere in the output.
- **I5.** Declarations precede definitions.
- **I6.** Output is deterministic for a fixed input and `Config`, at any thread count.
- **I7.** No `!llvm.dbg` metadata appears in v1 output.

## 7. Examples

Module scaffolding with a declaration before a definition, opaque pointers, and a `phi`:

```llvm
; ModuleID = 'demo'
target triple = "x86_64-unknown-linux-gnu"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"

%struct.Pair = type { i32, i64 }

declare i32 @extern_fn(ptr)

define i32 @add(i32 %a, i32 %b) {
entry:
  %r = add i32 %a, %b
  ret i32 %r
}

define i32 @loop_sum(ptr %p, i32 %n) {
entry:
  br label %loop

loop:
  %i = phi i32 [ 0, %entry ], [ %next, %body ]
  %acc = phi i32 [ 0, %entry ], [ %acc.next, %body ]
  %cond = icmp slt i32 %i, %n
  br i1 %cond, label %body, label %exit

body:
  %v = load i32, ptr %p, align 4, !range !0
  %acc.next = add i32 %acc, %v
  %next = add i32 %i, 1
  br label %loop

exit:
  ret i32 %acc
}

!0 = !{i32 0, i32 100}
```

A `Restrict` parameter and an `Assume` lower like this:

```llvm
define void @copy(ptr noalias %dst, ptr noalias %src) {
entry:
  %ok = icmp ne ptr %dst, null
  call void @llvm.assume(i1 %ok)
  ret void
}
```

## 8. Cross-references

- [000 — Overview](000-overview.md) for determinism and conformance.
- [001 — Architecture](001-architecture.md) for module boundaries.
- [002 — Traits](002-traits.md) for the trait vocabulary consumed here.
- [006 — VIR](006-vir.md) for the input IR and its invariants.
- [007 — VIR Optimizer](007-vir-optimizer.md) for the pass pipeline.
- [008 — C Backend](008-c-backend.md) for the default C path.
- [010 — Driver & CLI](010-driver-cli.md) for the `-target` flag and mode selection.
- [011 — Diagnostics](011-diagnostics.md) for error reporting.