Lesson 9.2 — The type system, data layout strings and target triples¶

Techniques: integer, byte, floating-point and pointer types (with address spaces); aggregate types (arrays; literal, identified and packed structs); fixed and scalable vectors; special types (target extension, label, token, metadata); data layout strings and target triples · Pebble uses: i64, i1, double, ptr, arrays and identified structs · Lab: E3, E9 · Prerequisites: Lesson 9.1 · Time: 3 hours

Ask clang for the IR of long double f(long double x) twice, once for Linux on x86-64 and once for macOS on Apple silicon. The first says x86_fp80, the second double. The IR type of a C type is a target decision, and so are the size and alignment of every IR type: { i8, double } is 16 bytes on x86-64 and 12 on 32-bit x86. LLVM IR separates the two questions. The type system says what a value is (an integer of 24 bits, a pointer into address space 1, a struct of an i8 and a double); the data layout string says how the target lays it out in memory; the target triple says which target that is. This lesson defines all three. Lesson 9.4 uses them to compute addresses.

1. Problem and motivation¶

An IR type system must be low-level enough that every source language maps onto it without losing information the back end needs (widths, alignment, calling-convention distinctions), yet language-neutral: no classes, no signedness, no unions. LLVM's answer, fixed in 2004 and refined since, is a small set of structural types over which the whole optimizer is written [LA04, §2.2; LLVM-LangRef, §Type System]. The two big changes since then are both simplifications: pointers lost their pointee type (opaque pointers, LLVM 15–17 [LLVM-OpaquePtr]), and the type of raw memory got its own type (bN, the byte type, new in LLVM 23).

Integer, byte, floating-point and pointer types¶

Integers carry a width and no sign: add i32 is the same operation for int and unsigned, and signedness lives in the instructions (sdiv/udiv, icmp slt/ult, sext/zext) and in flags (Lesson 9.7). Arbitrary widths (i1 to i8388608, that is, up to \(2^{23}\) bits) exist because hardware and languages need them: i1 for conditions, i24 for C23 _BitInt(24), i128 for __int128. Floating-point types name IEEE formats (half, bfloat, float, double, fp128) plus two legacy target formats (x86_fp80, ppc_fp128). Pointers were typed (i32*) until LLVM 15; the pointee type turned out to carry no semantics (every load and GEP names its own type) and to cost a bitcast on every type pun, so LLVM 17 made every pointer plain ptr [LLVM-OpaquePtr]. What remains is the address space, which does carry semantics (GPU memories, garbage-collected references, segment registers).

Aggregate types: arrays and structs¶

Arrays [n x T] and structs { T1, …, Tk } describe memory layout and multi-value returns. Structs come in two flavors because two needs conflict: literal structs are identified by their structure (so { i64, i64 } written twice is one type), identified structs by their name (so %struct.Point and %struct.Size stay distinct even with equal bodies, which keeps the IR readable and matches the front end's view) [LLVM-LangRef, §Structure Types].

Vector types: fixed and scalable¶

SIMD hardware operates on vectors of lanes; <4 x float> names a 128-bit SSE/NEON register value. Arm SVE and RISC-V V have vectors whose length is a run-time constant chosen by the hardware; <vscale x 4 x i32> names "vscale times 4 lanes of i32", where vscale is unknown at compile time but fixed for the program run. Scalable vectors were added to the IR in 2019, first for Arm SVE, so that vectorizers could target such hardware without committing to a width.

Special types: target extension, label, token, metadata¶

Some values must flow through the IR without the optimizer being allowed to inspect, copy or merge them: an image handle on a GPU (target("spirv.Image", …)), a coroutine or convergence token, a basic block used as a branch target (label), a piece of metadata passed to an intrinsic (metadata). These types exist precisely to forbid operations: a token cannot be put in a phi, a label cannot be a function parameter.

Data layout strings and target triples¶

The optimizer needs sizes and alignments (to fold sizeof, to compute GEP offsets, to decide whether a load is aligned) but must not depend on target code. Since the start, LLVM has put that knowledge into a string in the module, the data layout, which the target also checks against its own [LLVM-LangRef, §Data Layout]; the target triple arch-vendor-os[-env] names the target itself.

2. Definitions and algorithms¶

Definition 9.2.1 (Types)

The types of LLVM 23 are generated by the grammar

\[ \begin{aligned} \tau \;::=\;& \texttt{void} \mid \texttt{i}N \mid \texttt{b}N \mid \texttt{half} \mid \texttt{bfloat} \mid \texttt{float} \mid \texttt{double} \mid \texttt{fp128} \mid \texttt{x86\_fp80} \mid \texttt{ppc\_fp128} \\ \mid\;& \texttt{ptr addrspace(}a\texttt{)} \mid [\,n \times \tau\,] \mid \{\tau_1, \dots, \tau_k\} \mid \langle\{\tau_1, \dots, \tau_k\}\rangle \mid \%\mathit{name} \\ \mid\;& \langle n \times \tau \rangle \mid \langle \texttt{vscale} \times n \times \tau \rangle \mid \tau\,(\tau_1, \dots, \tau_k [, \dots]) \\ \mid\;& \texttt{label} \mid \texttt{token} \mid \texttt{metadata} \mid \texttt{target(}"\mathit{name}", \tau^{*}, n^{*}\texttt{)} \end{aligned} \]

with \(1 \le N \le 2^{23}\), \(a \ge 0\) (written ptr when \(a = 0\)), \(n \ge 0\) for arrays and \(n \ge 1\) for vectors, whose element \(\tau\) is an integer, floating-point or pointer type. \(\langle\{\dots\}\rangle\) is a packed struct; \(\%\mathit{name}\) refers to an identified struct declared %name = type {…} or %name = type opaque.

Definition 9.2.2 (Classes of types)

Single-value types: integer, byte, floating-point, pointer, vector and target extension types (values that fit a "register").
Aggregate types: arrays and structs.
First-class types: single-value types, aggregates, label, token and metadata — the types an instruction can produce or take.
A type is sized if its size is a compile-time constant: every single-value type except scalable vectors and most target extension types; an array of a sized type; a struct whose fields are all sized and which is not opaque. (This is stricter than LLVM's Type::isSized(), which also returns true for scalable vectors, whose size is a TypeSize known only up to the factor vscale.)

Definition 9.2.3 (Type identity)

Two literal types are equal iff they have the same constructor and pairwise equal components (structural identity). Two identified structs are equal iff they are the same declaration (nominal identity), whatever their bodies.

Algorithm 9.2.4 (Type uniquing by hash-consing)

Input: a request for a literal type \(c(\tau_1, \dots, \tau_k)\) (constructor \(c\) with components that are already unique type objects), or for a new identified struct named \(x\).
Output: the unique type object representing it.
Precondition: the component objects were obtained from the same context.
Postcondition: for literal types, equal requests return the same object.
Invariant: the table \(U\) maps each key \((c, \tau_1, \dots, \tau_k)\) to at most one object, and every live literal type object is the value of its own key.

function GetLiteral(c, τ1, …, τk):          # e.g. c = struct, packed = false
    key ← (c, τ1, …, τk)                    # compares components by object identity
    if key ∈ U: return U[key]
    t ← new type object c(τ1, …, τk)
    U[key] ← t
    return t

function CreateIdentified(x, body):
    while x ∈ NamedStructs: x ← x + "." + counter   # rename, never merge
    t ← new struct object named x with body
    NamedStructs[x] ← t
    return t

Definition 9.2.5 (Data layout)

A data layout is a finite partial map \(\mathit{DL}\) from specification keys to values, parsed from the string target datalayout = "s1-s2-…": e/E (endianness); p[a]:size:abi[:pref[:idx]] (pointer width, alignments and index width in address space \(a\)); iN:abi[:pref], fN:abi[:pref], vN:abi[:pref] (alignments of integers, floats, vectors of \(N\) bits); a:abi[:pref] (aggregates); nN:M:… (native integer widths); S (stack alignment); m: (symbol mangling); plus less common keys. Alignments are given in bits and must be \(8 \cdot 2^j\). A key that is absent takes its default: p:64:64:64, i1:8, i8:8, i16:16, i32:32, i64:32:64, f16:16, f32:32, f64:64, f128:128, v64:64, v128:128, a:0:64 [LLVM-LangRef, §Data Layout].

Algorithm 9.2.6 (ABI alignment of a type)

Input: a sized type \(\tau\) and a data layout \(\mathit{DL}\) with defaults filled in.
Output: \(\mathrm{align}(\tau)\) in bytes, a power of two.
Precondition: \(\tau\) is sized and not a target extension type.
Postcondition: agrees with LLVM's DataLayout::getABITypeAlign.
Invariant: each case returns a value of some specification or a power of two computed from a size.

function Align(τ):
    case τ of
      iN, bN:  if "iN" ∈ DL: return DL[iN].abi
               M ← the smallest listed integer width > N, else the largest listed width
               return DL[iM].abi
      fN:      if "fN" ∈ DL: return DL[fN].abi
               return PowerOf2Ceil(N / 8)                  # e.g. x86_fp80 without f80 → 16
      ptr addrspace(a): return DL[p a].abi                 # p0 if p a is absent
      <n x e>: S ← n · bits(e)                              # size in bits, not rounded
               if "vS" ∈ DL: return DL[vS].abi
               if "ve" ∈ DL: return Align(e)                # element-aligned vectors
               return PowerOf2Ceil(StoreSize(τ))           # natural alignment
      [n x e]: return Align(e)
      struct:  if packed: return 1
               return max(DL[a].abi, max over fields f of Align(f))

function StoreSize(τ):                                    # bytes a store may write
    case τ of
      iN, bN, fN, ptr: return ceil(bits(τ) / 8)
      <n x e>: return ceil(n · bits(e) / 8)
      [n x e]: return n · AllocSize(e)
      struct:  return the size computed by Algorithm 9.4.2
function AllocSize(τ): return AlignTo(StoreSize(τ), Align(τ))

Definition 9.2.7 (Sizes)

For a sized type \(\tau\): its size in bits \(\lvert\tau\rvert\) (for iN, \(N\)); its store size \(\mathrm{store}(\tau) = \lceil \lvert\tau\rvert / 8 \rceil\) bytes for single-value types; and its alloc size \(\mathrm{alloc}(\tau) = \mathrm{align}(\tau) \cdot \lceil \mathrm{store}(\tau) / \mathrm{align}(\tau) \rceil\), the distance between consecutive elements of an array of \(\tau\). For example, on x86-64 i24 has \(\lvert\tau\rvert = 24\), \(\mathrm{store} = 3\), \(\mathrm{align} = 4\) (from i32), \(\mathrm{alloc} = 4\).

Definition 9.2.8 (Target triple)

A target triple is a string arch[sub]-vendor-os[-environment] such as x86_64-unknown-linux-gnu or arm64-apple-macosx14.0.0. It selects the back end, the object format and the ABI; it does not determine the data layout by itself, but each back end requires the module's data layout to match the one it computes for the triple.

Scalable vectors. For \(\langle \texttt{vscale} \times n \times e \rangle\) the size is \(\texttt{vscale} \cdot n \cdot \lvert e \rvert\) bits, where \(\texttt{vscale} \ge 1\) is a hardware constant unknown at compile time (read with llvm.vscale). Such types are not sized in the sense of Definition 9.2.2, although Type::isSized() is true for them: they may be allocaed, loaded, stored and used as a GEP source type (the offset then scales with vscale), but they cannot be (or be contained in) global variables. A struct containing scalable vectors is unsized for loads, stores, allocas and GEPs, except a struct of identical scalable vectors, which may be loaded, stored and allocated but not indexed by a GEP [LLVM-LangRef, §Global Variables].

3. Worked example¶

Types of the running example. In @sum_pos (Lesson 9.1), %a is ptr (the C const long long * lost both its pointee type and const), %n, %s.0, %i.0, %add, %inc, %0, %1 are i64, %cmp and %cmp1 are i1, %arrayidx is ptr, and the blocks are values of type label. Nothing in the IR says that %a points to i64s: the load i64 and the getelementptr inbounds i64 each say it themselves.

A layout under three data layouts. Take %S = type { i8, double, i64 } and apply Algorithm 9.2.6 and the struct layout of Algorithm 9.4.2 (each field at the next multiple of its alignment) under three data layouts:

field	x86-64 `…-i64:64-…` (f64 default)	i686 `…-f64:32:64-…` (i64 default)	empty string (all defaults)
`i8` at	0	0	0
`double`: align, offset	8, 8	4, 4	8, 8
`i64`: align, offset	8, 16	4 (from `i64:32:64`), 12	4 (from `i64:32:64`), 16
end of last field	24	20	24
struct alignment	8	4	8
alloc size	24	20	24

The i686 layout says f64:32:64: a double needs only 4-byte alignment there (the System V i386 ABI), and it says nothing about i64, so the default i64:32:64 applies. The empty layout gives the same size as x86-64 although its i64 is only 4-aligned: double is 8-aligned by default, so the i64 follows at offset 16, which is already a multiple of 4, and the struct's alignment is still 8 (from the double). The difference shows on { i32, i64 }: 12 bytes under the empty layout, 16 on x86-64. The real-world box in the "Data layout strings and target triples" section below checks all three with clang and opt.

Uniquing. Parsing %A = type { i32, ptr } and %A.0 = type { i32, ptr } and using the literal { i32, ptr } gives three distinct types for Algorithm 9.2.4: two identified structs (one of them renamed because the name was taken) and one literal struct; a second occurrence of the literal { i32, ptr } anywhere in the module returns the same object as the first.

step	request	table before	action	result
1	literal `i32`	—	create	\(t_1\)
2	literal `ptr`	\(\{t_1\}\)	create	\(t_2\)
3	identified `A`	—	new, named `A`	\(t_3\)
4	identified `A`	`A` taken	rename to `A.0`, new	\(t_4 \ne t_3\)
5	literal `{ i32, ptr }`	key \((\mathrm{struct}, t_1, t_2)\) absent	create	\(t_5\)
6	literal `{ i32, ptr }` again	key present	return \(U[\mathrm{key}]\)	\(t_5\)

Try it

./course drill gep-offset --seed 5 --difficulty medium --solution lays out random structs under the three target layouts above, field by field.

4. Invariants and correctness¶

Integer, byte, floating-point and pointer types¶

Proposition 9.2.9 (Signedness is not in the type)

For every width \(N\), the add, sub, mul, shl, and, or, xor instructions on iN without flags compute the same bit pattern whether their operands are read as unsigned or as two's-complement signed numbers.

Proof

Let \(x, y \in [0, 2^N)\) be the bit patterns and \(x_s = x - 2^N b_x\), \(y_s = y - 2^N b_y\) their signed readings, with \(b_x, b_y \in \{0, 1\}\) the sign bits. Then \(x_s + y_s \equiv x + y\), \(x_s - y_s \equiv x - y\) and \(x_s \cdot y_s \equiv x \cdot y \pmod{2^N}\), because the differences are multiples of \(2^N\). Each instruction returns its exact result reduced modulo \(2^N\), so the two readings give the same pattern. The bitwise operations and shl act on bits directly, without reading a number. Division, remainder, right shifts, comparisons and extensions do depend on the reading, which is why they come in pairs (sdiv/udiv, ashr/lshr, slt/ult, sext/zext).

Aggregate types: arrays and structs¶

Proposition 9.2.10 (The type graph is well founded)

In a module accepted by LLVM 23, no type contains itself: the relation "\(\tau'\) is a component of \(\tau\)" (array element, vector element, struct field, including through identified-struct names) has no cycle. Hence every sized type has a finite size.

Proof

Components are introduced only by the constructors of Definition 9.2.1. A literal type is built from already existing components (Algorithm 9.2.4 takes component objects), so a cycle would have to pass through an identified struct whose body refers, directly or through other identified structs, back to itself. StructType::setBodyOrError checks exactly this when a body is set and rejects it ("identified structure type 'T' is recursive"). The only other way a type could refer to itself would be through a pointer's pointee type, and opaque ptr has none. So the component relation is acyclic, and sizes are defined by structural recursion on it (Algorithm 9.2.6), which terminates.

Corollary 9.2.11 (Structural equality is pointer equality)

Two literal types in the same context are structurally equal (Definition 9.2.3) iff they are the same object.

Proof

By induction on the height of the (well-founded, Proposition 9.2.10) component relation. Base: primitive types (i32, ptr, …) are unique per context by construction of their tables (IntegerTypes, …). Step: two structurally equal literal types have the same constructor and components that are structurally equal, hence, by the induction hypothesis, the same component objects; so their keys in Algorithm 9.2.4 are equal, and the invariant (one object per key) makes them the same object. The converse is immediate.

Vector types: fixed and scalable¶

Proposition 9.2.12 (What is known about a scalable size)

For a scalable vector \(v = \langle \texttt{vscale} \times n \times e \rangle\), every size is a known positive multiple of the run-time constant: \(\lvert v \rvert = \texttt{vscale} \cdot (n \lvert e \rvert)\), and for any two scalable types \(v, w\) the ratio \(\lvert v \rvert / \lvert w \rvert\) is a compile-time constant.

Proof

By the definition of scalable vectors, \(\lvert v \rvert = \texttt{vscale} \cdot n \cdot \lvert e \rvert\) with the same \(\texttt{vscale}\) for all scalable types in one run [LLVM-LangRef, §Vector Type]. Dividing, \(\lvert v \rvert / \lvert w \rvert = (n_v \lvert e_v \rvert) / (n_w \lvert e_w \rvert)\), which does not mention \(\texttt{vscale}\). This is why LLVM represents such sizes as TypeSize (a known minimum plus a "scalable" flag): comparisons between scalable sizes are decidable, comparisons with fixed sizes are not.

Special types: target extension, label, token, metadata¶

Proposition 9.2.13 (Tokens have no data flow)

In a verified module, a value of type token is produced only by an intrinsic call or the constant none, and is never the operand of a phi or select; hence every use of a token refers to one statically known producing instruction.

Proof

The verifier rejects a token-typed phi ("PHI nodes cannot have token type!") and a non-intrinsic function that returns or takes a token ("Function returns a token but isn't an intrinsic", "Function takes token but isn't an intrinsic"); the parser rejects a token-typed select ("select values cannot have token type") and token-typed globals ("invalid type for global variable"). The remaining ways to produce a token are intrinsic calls and none. Since no instruction merges tokens, the operand of each use is a single SSA value (Definition 9.1.6), i.e. one statically known producer. Optimizations that would merge two token producers (tail merging, sinking into a phi) are therefore illegal, which is the point of the type.

Data layout strings and target triples¶

Theorem 9.2.14 (Alloc size and alignment)

For every sized type \(\tau\): (a) \(\mathrm{align}(\tau)\) divides \(\mathrm{alloc}(\tau)\); (b) \(\mathrm{alloc}([n \times \tau]) = n \cdot \mathrm{alloc}(\tau)\) and \(\mathrm{align}([n \times \tau]) = \mathrm{align}(\tau)\); (c) if an array of \(\tau\) starts at an address \(p\) with \(\mathrm{align}(\tau) \mid p\), then every element address \(p + k \cdot \mathrm{alloc}(\tau)\) is a multiple of \(\mathrm{align}(\tau)\).

Proof

(a) By Definition 9.2.7, \(\mathrm{alloc}(\tau) = \mathrm{align}(\tau) \cdot \lceil \mathrm{store}(\tau)/\mathrm{align}(\tau) \rceil\). (b) Algorithm 9.2.6 gives \(\mathrm{align}([n \times \tau]) = \mathrm{align}(\tau)\) and \(\mathrm{store}([n \times \tau]) = n \cdot \mathrm{alloc}(\tau)\), which is a multiple of \(\mathrm{align}(\tau)\) by (a); rounding a multiple of the alignment up to the alignment leaves it unchanged, so \(\mathrm{alloc}([n \times \tau]) = n \cdot \mathrm{alloc}(\tau)\). (c) \(p\) and \(k \cdot \mathrm{alloc}(\tau)\) are both multiples of \(\mathrm{align}(\tau)\) by hypothesis and (a), so is their sum.

When it breaks. Theorem 9.2.14 is about the layout the data layout string describes. If a front end emits a data layout that differs from the one the back end computes for the triple, the optimizer folds sizeof and field offsets for one layout while the generated code follows another; LLVM therefore makes every back end check the module's string (TargetMachine::isCompatibleDataLayout) and refuse a mismatch rather than miscompile.

5. Complexity¶

Technique	Time (worst)	Time (typical)	Space	Variables
Type uniquing (Algorithm 9.2.4)	\(O(k)\) hashing per request	\(O(1)\)	\(O(T)\)	\(k\) = components, \(T\) = distinct types
Type equality (Corollary 9.2.11)	\(O(1)\)	\(O(1)\)	—	—
ABI alignment (Algorithm 9.2.6)	\(O(\log s + d)\)	\(O(1)\) (cached)	\(O(s)\)	\(s\) = specs in the layout, \(d\) = type depth
Struct layout (Algorithm 9.4.2)	\(O(f)\) once per struct, then cached	—	\(O(f)\)	\(f\) = fields
Data layout parsing	\(O(\lvert\mathit{DL}\rvert)\)	—	\(O(s)\)	string length

Proposition 9.2.15 (Cost of the alignment lookup)

With the specifications of each kind kept sorted by width, Algorithm 9.2.6 answers an integer, float, pointer or vector query in \(O(\log s)\) time, and an aggregate query in \(O(\log s)\) per distinct type after its first computation.

Proof

The integer rule "exact width, else the next larger listed width, else the largest" is one lower_bound on the sorted list of integer specs, \(O(\log s)\); the float and vector rules are also one lower_bound plus \(O(1)\) arithmetic. An array's alignment is its element's; a struct's is the maximum over its fields, computed once when its StructLayout is built and then cached per type, so each later query is a map lookup.

Pathological input. Without caching, a struct nested \(d\) levels deep with \(f\) fields per level costs \(\Theta(f^d)\) to lay out, because each level would recompute the layout of every inner struct for every occurrence; with the per-type cache (DataLayout::getStructLayout) it is \(\Theta(f \cdot d)\) distinct layouts. A module with \(10^5\) distinct literal struct types (generated code does this) spends measurable time in AnonStructTypes hashing; interning is why identified structs from different linked modules are renamed (%A.0) rather than compared structurally.

Integer, byte, floating-point and pointer types¶

Opaque pointers [LLVM-OpaquePtr]: typed pointers i32* were removed in LLVM 17 after a three-release migration; trade-off: no type-directed alias information from pointer types (it moved to TBAA metadata, Lesson 9.6), in exchange for no bitcast noise and simpler canonical forms.
The byte type bN (LLVM 23, [LLVM-LangRef, §Byte Type]): a register value of raw memory bits, each bit an integer bit, part of a pointer, or poison. It lets a memcpy be lowered to load/store without claiming the bytes are integers (which would lose pointer provenance and turn poison bits into full-width poison). Trade-off: one more type every pass must handle; back ends lower it to iN.
Non-integral address spaces (ni: in the layout): pointers whose integer value is not stable (garbage-collected heaps); ptrtoint/inttoptr on them are not meaningful, which some passes must respect.

Aggregate types: arrays and structs¶

Packed structs <{ … }>: every field at alignment 1, the struct at alignment 1; models __attribute__((packed)), at the cost of unaligned accesses.
Opaque structs %T = type opaque: a named type with no body yet; since opaque pointers it is needed only when a front end must name an incomplete type that is never laid out.
Structs as multiple return values: { i64, i1 } from llvm.sadd.with.overflow and { i64, i64 } from clang's small-struct returns are literal structs used as values, taken apart with extractvalue.

Vector types: fixed and scalable¶

Scalable vectors (for Arm SVE and RISC-V V): sizes as TypeSize with a scalable flag; trade-off: every size computation in the optimizer must handle "unknown multiple".
Vectors of pointers <4 x ptr>: operands of vector GEPs, gathers and scatters; used by the loop vectorizer.

Special types: target extension, label, token, metadata¶

Target extension types target("name", types…, ints…) (LLVM 16+): replace ad-hoc opaque struct pointers for GPU handles (SPIR-V, DirectX) and RISC-V vector tuples, with properties (can be zero-initialized, can be a global, has a layout type) registered per name.
Tokens for control-dependent values: exception-handling pads (catchpad, Lesson 9.3), coroutines (llvm.coro.id), convergence control (llvm.experimental.convergence.*).

Data layout strings and target triples¶

Index width distinct from pointer width (p:64:64:64:32): GEP arithmetic in 32 bits on a 64-bit pointer (CHERI capabilities, some GPUs); Lesson 9.4's formula works modulo \(2^{\mathrm{idx}}\).
Triple normalization: aarch64-apple-macosx14 is stored as arm64-apple-macosx14.0.0; Triple::normalize fills in missing components so that two spellings of one target compare equal.

7. In real compilers¶

Integer, byte, floating-point and pointer types¶

LLVM

llvm/include/llvm/IR/DerivedTypes.h — IntegerType, ByteType, PointerType; llvm/lib/IR/Type.cpp — IntegerType::get uniques integer types in LLVMContextImpl::IntegerTypes (llvm/lib/IR/LLVMContextImpl.h) (LLVM 23.1.2).

GCC 15: INTEGER_TYPE, BITINT_TYPE, REAL_TYPE, POINTER_TYPE tree codes (gcc/tree.def); unlike LLVM, GCC integer types do carry signedness (TYPE_UNSIGNED).
Cranelift 37: i8–i128, f16–f128, no pointer type at all: addresses are plain integers of the target's pointer width (cranelift/codegen/src/ir/types.rs, Type).

Find where LLVM does it. In llvm/lib/IR/LLVMContextImpl.h, find the map that uniques integer types. Question: what is its key type?

C scalar types as IR types, on two targets

Reproduce (clang 23.1.2):

cat > scalars.c <<'EOF'
_BitInt(24) b24(_BitInt(24) x) { return x + 1; }
__int128 wide(__int128 x) { return x * 3; }
_Float16 h(_Float16 x) { return x * 2; }
long double ld(long double x) { return x / 3; }
int __attribute__((address_space(1))) *as1(int __attribute__((address_space(1))) *p) { return p + 1; }
_Bool flip(_Bool b) { return !b; }
EOF
for t in x86_64-unknown-linux-gnu aarch64-apple-macosx14; do
  echo "--- $t"; clang-23 --target=$t -O1 -S -emit-llvm scalars.c -o - | grep "^define"
done

Output (complete):

--- x86_64-unknown-linux-gnu
define dso_local signext i24 @b24(i24 noundef signext %0) local_unnamed_addr #0 {
define dso_local i128 @wide(i128 noundef %0) local_unnamed_addr #0 {
define dso_local noundef half @h(half noundef %0) local_unnamed_addr #0 {
define dso_local noundef x86_fp80 @ld(x86_fp80 noundef %0) local_unnamed_addr #0 {
define dso_local nonnull ptr addrspace(1) @as1(ptr addrspace(1) nofree noundef readnone captures(ret: address, provenance) %0) local_unnamed_addr #0 {
define dso_local noundef zeroext i1 @flip(i1 noundef zeroext %0) local_unnamed_addr #0 {
--- aarch64-apple-macosx14
define signext i24 @b24(i24 noundef signext %0) local_unnamed_addr #0 {
define i128 @wide(i128 noundef %0) local_unnamed_addr #0 {
define noundef half @h(half noundef %0) local_unnamed_addr #0 {
define noundef double @ld(double noundef %0) local_unnamed_addr #0 {
define nonnull ptr addrspace(1) @as1(ptr addrspace(1) nofree noundef readnone captures(ret: address, provenance) %0) local_unnamed_addr #0 {
define noundef zeroext i1 @flip(i1 noundef zeroext %0) local_unnamed_addr #0 {

What to notice: widths are exact (i24, i128, i1) and carry no sign; the ABI sign or zero extension of small integers is an attribute (signext, zeroext, Lesson 9.5), not a type. long double is a target choice (x86_fp80 vs double). The address space survives as part of the pointer type (ptr addrspace(1)); the pointee int does not.

The byte type bN in LLVM 23

Reproduce (opt 23.1.2):

cat > byte.ll <<'EOF'
define void @copy8(ptr %dst, ptr %src) {
  %v = load b64, ptr %src, align 1
  store b64 %v, ptr %dst, align 1
  ret void
}
define i64 @as_int(b64 %b) {
  %i = bitcast b64 %b to i64
  ret i64 %i
}
EOF
opt -passes=verify -S byte.ll | grep -v "^;\|^$\|source_file"

Output (complete):

define void @copy8(ptr %dst, ptr %src) {
  %v = load b64, ptr %src, align 1
  store b64 %v, ptr %dst, align 1
  ret void
}
define i64 @as_int(b64 %b) {
  %i = bitcast b64 %b to i64
  ret i64 %i
}

What to notice: b64 is a first-class type of LLVM 23: it can be loaded, stored and passed around, and turned into an integer only by an explicit bitcast, which is where poison bits and pointer provenance are resolved (Lesson 9.7). clang 23 still lowers an 8-byte memcpy to load i64/store i64; the byte type is the IR's new, more precise option, not yet the default everywhere.

Aggregate types: arrays and structs¶

LLVM

llvm/lib/IR/Type.cpp — StructType::get (literal, uniqued in AnonStructTypes), StructType::create (identified, named in NamedStructTypes, renamed with a numeric suffix on a clash), StructType::setBodyOrError (rejects recursive bodies) (LLVM 23.1.2).

GCC 15: RECORD_TYPE/ARRAY_TYPE trees with field decls that already carry byte offsets (DECL_FIELD_OFFSET), i.e. the front end lays out, not the optimizer.
rustc 1.94: layouts are computed in compiler/rustc_abi/src/layout.rs (LayoutCalculator, method univariant), which may reorder fields to reduce padding; the LLVM struct rustc emits reflects the reordered layout.

Find where LLVM does it. In llvm/lib/IR/Type.cpp, find the error message for a recursive identified struct. Question: which function reports it?

Identified, packed and literal structs from C

Reproduce (clang 23.1.2):

cat > aggr.c <<'EOF'
struct Node { int key; struct Node *next; };            /* recursive: identified */
struct __attribute__((packed)) Hdr { char tag; int len; };
struct Opaque;                                           /* never completed        */
struct Pair { long a, b; };
int keys[4][3];
struct Pair mk(long a, long b) { struct Pair p = {a, b}; return p; }
int use(struct Node *n, struct Hdr *h, struct Opaque *o) { return n->next->key + h->len + (o != 0); }
EOF
clang-23 --target=x86_64-unknown-linux-gnu -O0 -S -emit-llvm aggr.c -o - | grep -E "^%|^@|^define|getelementptr"

Output (complete):

%struct.Pair = type { i64, i64 }
%struct.Node = type { i32, ptr }
%struct.Hdr = type <{ i8, i32 }>
@keys = dso_local global [4 x [3 x i32]] zeroinitializer, align 16
define dso_local { i64, i64 } @mk(i64 noundef %0, i64 noundef %1) #0 {
  %6 = getelementptr inbounds nuw %struct.Pair, ptr %3, i32 0, i32 0
  %8 = getelementptr inbounds nuw %struct.Pair, ptr %3, i32 0, i32 1
define dso_local i32 @use(ptr noundef %0, ptr noundef %1, ptr noundef %2) #0 {
  %8 = getelementptr inbounds nuw %struct.Node, ptr %7, i32 0, i32 1
  %10 = getelementptr inbounds nuw %struct.Node, ptr %9, i32 0, i32 0
  %13 = getelementptr inbounds nuw %struct.Hdr, ptr %12, i32 0, i32 1

What to notice: struct Node refers to itself only through ptr, so its IR type is not recursive (Proposition 9.2.10). struct Opaque never appears: a pointer to it is just ptr. The packed struct is <{ i8, i32 }>, so its len sits at offset 1. The function returns a literal struct { i64, i64 }: that is the x86-64 ABI's two-register return, a different type from %struct.Pair although the bodies are equal (Definition 9.2.3). @keys is aligned to 16 although [4 x [3 x i32]] needs 4: the x86-64 System V ABI aligns global arrays of 16 bytes or more to 16, and alignment is a property of the global, not of its type.

Vector types: fixed and scalable¶

LLVM

llvm/include/llvm/IR/DerivedTypes.h — VectorType, FixedVectorType, ScalableVectorType; llvm/include/llvm/Support/TypeSize.h — TypeSize (known minimum + scalable flag); vector types are uniqued in LLVMContextImpl::VectorTypes keyed by (element type, ElementCount) (LLVM 23.1.2).

GCC 15: VECTOR_TYPE with TYPE_VECTOR_SUBPARTS as a poly_uint64, GCC's counterpart of a scalable element count (gcc/tree.def, gcc/poly-int.h).
Cranelift 37: fixed vectors (i32x4) plus dynamic vector types for scalable hardware (Type::is_dynamic_vector, cranelift/codegen/src/ir/types.rs).

Find where LLVM does it. In llvm/lib/IR/LLVMContextImpl.h, find VectorTypes. Question: which type represents the element count in its key, so that <4 x i32> and <vscale x 4 x i32> get different entries?

Fixed and scalable vectors from clang

Reproduce (clang 23.1.2):

cat > sve.c <<'EOF'
#include <arm_sve.h>
svint32_t addv(svint32_t a, svint32_t b) { return svadd_s32_x(svptrue_b32(), a, b); }
typedef float f4 __attribute__((ext_vector_type(4)));
f4 scale(f4 v, float k) { return v * k; }
EOF
clang-23 --target=aarch64-unknown-linux-gnu -march=armv8-a+sve -ffreestanding -O1 -S -emit-llvm sve.c -o - \
  | grep -E "^define|^  %|^  ret"

Output (complete):

define dso_local <vscale x 4 x i32> @addv(<vscale x 4 x i32> %0, <vscale x 4 x i32> %1) local_unnamed_addr #0 {
  %3 = tail call <vscale x 4 x i32> @llvm.aarch64.sve.add.u.nxv4i32(<vscale x 4 x i1> splat (i1 true), <vscale x 4 x i32> %0, <vscale x 4 x i32> %1)
  ret <vscale x 4 x i32> %3
define dso_local noundef <4 x float> @scale(<4 x float> noundef %0, float noundef %1) local_unnamed_addr #0 {
  %3 = insertelement <4 x float> poison, float %1, i64 0
  %4 = shufflevector <4 x float> %3, <4 x float> poison, <4 x i32> zeroinitializer
  %5 = fmul <4 x float> %0, %4
  ret <4 x float> %5

What to notice: the SVE type svint32_t is <vscale x 4 x i32> (4 lanes per 128 bits of hardware vector); the all-true predicate is a scalable i1 vector written as the splat constant. The fixed vector <4 x float> is built from a scalar by the insertelement + shufflevector broadcast idiom, whose unused lanes start as poison (Lesson 9.7).

Special types: target extension, label, token, metadata¶

LLVM

llvm/include/llvm/IR/DerivedTypes.h — TargetExtType (name, type parameters, integer parameters, properties); the token and label rules are checks in llvm/lib/IR/Verifier.cpp ("PHI nodes cannot have token type!", "Function returns a token but isn't an intrinsic") and in llvm/lib/AsmParser/LLParser.cpp ("invalid type for function argument") (LLVM 23.1.2) [LLVM-Verifier].

GCC: no token type; GIMPLE marks such values with flags on calls (ECF_*) instead, e.g. __builtin_setjmp receivers, which is why some GCC passes special-case calls by name.
SPIR-V / DirectX back ends in LLVM consume target("spirv.Image", …) and target("dx.TypedBuffer", …) from HLSL and OpenCL front ends.

Find where LLVM does it. In llvm/lib/IR/Verifier.cpp, find the check that rejects token-typed phis. Question: in which visit… function is it?

What the special types forbid

Reproduce (opt and llvm-as 23.1.2):

cat > special.ll <<'EOF'
declare token @llvm.experimental.convergence.entry()
declare void @use.img(target("spirv.Image", float, 1, 0, 0, 0, 0, 0, 0))

define void @ok(target("spirv.Image", float, 1, 0, 0, 0, 0, 0, 0) %img) convergent {
entry:
  %t = call token @llvm.experimental.convergence.entry()
  call void @use.img(target("spirv.Image", float, 1, 0, 0, 0, 0, 0, 0) %img)
  ret void
}

define void @bad(i1 %c) convergent {
entry:
  %t1 = call token @llvm.experimental.convergence.entry()
  br i1 %c, label %a, label %b
a:
  br label %b
b:
  %t = phi token [ %t1, %entry ], [ %t1, %a ]
  ret void
}
EOF
opt -passes=verify -disable-output special.ll
printf 'define void @f(label %%l) {\n  ret void\n}\n' > lab.ll
llvm-as lab.ll -o /dev/null
printf 'define token @g() {\n  ret token none\n}\n' > tok.ll
llvm-as tok.ll -o /dev/null

Output (complete):

PHI nodes cannot have token type!
opt: special.ll: error: input module is broken!
llvm-as: lab.ll:1:16: error: invalid type for function argument
define void @f(label %l) {
               ^
llvm-as: assembly parsed, but does not verify as correct!
Function returns a token but isn't an intrinsic
ptr @g

What to notice: @ok verifies: a target extension type can be a parameter and an argument, and a token can be produced by an intrinsic. The three failures are the three prohibitions behind Proposition 9.2.13: no merging tokens, no labels as data, no tokens from ordinary functions. Only the first is caught by the verifier's CFG-aware checks; the label rule is enforced by the parser.

Data layout strings and target triples¶

LLVM

llvm/lib/IR/DataLayout.cpp — DataLayout::parseLayoutString and parseSpecification read the string; DataLayout::getAlignment implements Algorithm 9.2.6 (the integer "next larger width" rule, PowerOf2Ceil for unknown floats and vectors); StructLayout::StructLayout lays out structs. llvm/lib/TargetParser/Triple.cpp — Triple::normalize (LLVM 23.1.2) [LLVM-DataLayout].

GCC 15: sizes and alignments come from target macros at compile time (BITS_PER_UNIT, BIGGEST_ALIGNMENT, ADJUST_FIELD_ALIGN in gcc/config/i386/i386.h), not from a string carried by the IR.
rustc 1.94: each target spec (compiler/rustc_target/src/spec/targets/*.rs) contains the LLVM data layout string verbatim, and compiler/rustc_codegen_llvm/src/context.rs compares it with the layout LLVM's target machine reports, emitting MismatchedDataLayout if they differ.

Find where LLVM does it. In llvm/lib/IR/DataLayout.cpp, find the fallback for a floating-point type whose width has no specification. Question: what alignment does x86_fp80 get in a layout without f80?

One struct, three data layouts

Reproduce (clang 23.1.2, opt 23.1.2, llvm-as 23.1.2):

cat > layout.c <<'EOF'
struct S { char c; double d; long long q; };
unsigned off_d(void) { return __builtin_offsetof(struct S, d); }
unsigned size_s(void) { return sizeof(struct S); }
unsigned align_s(void) { return _Alignof(struct S); }
EOF
for t in x86_64-unknown-linux-gnu i686-unknown-linux-gnu aarch64-apple-macosx14; do
  clang-23 --target=$t -O1 -S -emit-llvm layout.c -o - | grep -E "^target|ret i32"
done
printf '%%S = type { i8, double, i64 }\ndefine i64 @size() {\n  %%p = getelementptr %%S, ptr null, i64 1\n  %%n = ptrtoint ptr %%p to i64\n  ret i64 %%n\n}\n' > empty.ll
opt -passes=instsimplify -S empty.ll | grep ret
echo 'target datalayout = "e-i64:65"' | llvm-as -o /dev/null

Output (complete):

target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
  ret i32 8
  ret i32 24
  ret i32 8
target datalayout = "e-m:e-p:32:32-p270:32:32-p271:32:32-p272:64:64-i128:128-f64:32:64-f80:32-n8:16:32-S128"
target triple = "i686-unknown-linux-gnu"
  ret i32 4
  ret i32 20
  ret i32 4
target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-n32:64-S128-Fn32"
target triple = "arm64-apple-macosx14.0.0"
  ret i32 8
  ret i32 24
  ret i32 8
  ret i64 24
llvm-as: <stdin>:1:21: error: ABI alignment must be a power of two times the byte width
target datalayout = "e-i64:65"
                    ^

What to notice: the three columns of the Section 3 table: offset 8 / size 24 on x86-64 and AArch64, offset 4 / size 20 on i686 (f64:32:64), and 24 under the empty layout (the constant folder uses the defaults of Definition 9.2.5). The triple was normalized (aarch64-apple-macosx14 → arm64-apple-macosx14.0.0, Definition 9.2.8). An alignment that is not \(8 \cdot 2^j\) is rejected.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Integer, byte, floating-point and pointer types	any width `iN`; IEEE + 2 legacy FP formats; `ptr` + address space; `bN` for raw memory	uniqued, \(O(1)\) equality	signedness must be read from instructions and ABI attributes	small	every value
Aggregate types: arrays and structs	literal (structural) and identified (nominal) structs, packed, opaque	uniqued; layout \(O(f)\) cached	readable names via identified structs	moderate (layout, renaming on link)	memory layout, multi-value returns
Vector types: fixed and scalable	SIMD of fixed or `vscale`-multiple width	sizes as `TypeSize`; scalable comparisons need care	clear lane types	high for scalable (every size query)	vectorizers, SIMD intrinsics
Special types: target extension, label, token, metadata	values the optimizer may pass but not inspect or merge	no cost	verifier states the forbidden operation	small per type	GPUs, EH, coroutines, convergence, debug info
Data layout strings and target triples	exact sizes/alignments without target code in the optimizer	\(O(\log s)\) lookup, cached layouts	mismatch refused by the back end	small, but every front end must emit the right string	constant folding of `sizeof`, GEP offsets, alignment

Choose integers without sign when the IR serves many languages: signedness is an operation's property. Choose identified structs whenever a human will read the IR or a debugger will map it back to source; literal structs for anonymous tuples. Choose scalable vectors only when the hardware has run-time vector length; fixed vectors otherwise. Choose a special type when an optimization would be wrong for a value (merging two tokens, copying an image handle into integer registers). Always emit the data layout the back end expects: copy it from the target, never write it by hand.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch09.yaml`)	Drill	Flashcard tag	Exercises
Integer, byte, floating-point and pointer types	`signless-integers`, `opaque-pointer-consequence`	`./course drill flags` (signedness lives in flags)	`types-scalar`	E6
Aggregate types: arrays and structs	`struct-layout-x86`, `literal-vs-identified`	`./course drill gep-offset`	`types-aggregate`	E3, E9
Vector types: fixed and scalable	`scalable-size`, `vector-alloc`	`./course drill gep-offset --difficulty hard` (vector fields)	`types-vector`	—
Special types: target extension, label, token, metadata	`token-phi`, `find-token-check`	`./course drill ir-validity` (type rules)	`types-special`	—
Data layout strings and target triples	`datalayout-i686`, `datalayout-default-i64`	`./course drill gep-offset --difficulty medium`	`datalayout`	E9

The empty data layout is not 'no layout'

A module without target datalayout still has one: LLVM's defaults, in which i64 is only 4-byte aligned (i64:32:64). Hand-written IR tested with opt but no layout line can fold offsets differently from the same IR compiled for x86-64. Put the target's layout in any test whose output depends on sizes.

References¶

See the chapter references.

Lesson 9.2 — The type system, data layout strings and target triples¶

1. Problem and motivation¶

Integer, byte, floating-point and pointer types¶

Aggregate types: arrays and structs¶

Vector types: fixed and scalable¶

Special types: target extension, label, token, metadata¶

Data layout strings and target triples¶

2. Definitions and algorithms¶

3. Worked example¶

4. Invariants and correctness¶

Integer, byte, floating-point and pointer types¶

Aggregate types: arrays and structs¶

Vector types: fixed and scalable¶

Special types: target extension, label, token, metadata¶

Data layout strings and target triples¶

5. Complexity¶

6. Variants and refinements¶

Integer, byte, floating-point and pointer types¶

Aggregate types: arrays and structs¶

Vector types: fixed and scalable¶

Special types: target extension, label, token, metadata¶

Data layout strings and target triples¶

7. In real compilers¶

Integer, byte, floating-point and pointer types¶

Aggregate types: arrays and structs¶

Vector types: fixed and scalable¶

Special types: target extension, label, token, metadata¶

Data layout strings and target triples¶

8. Comparison¶

9. Assessment¶

References¶