到第 14 篇为止，Sprout 程序中每个值都能装进一个寄存器：i64 是 64 位整数，bool 是 1 位逻辑值。函数参数和返回值通过寄存器传递，局部变量在 SSA 里就是虚拟寄存器。这套方案处理标量足够了，但程序需要处理一组数据时——排序、统计、批量输入——单个寄存器放不下。

本篇引入数组，它是 Sprout 的第一个堆分配类型。数组有可变长度，住在堆上，索引时必须检查边界。围绕它展开的问题不止语法：分配多大的内存、用什么布局存放长度和元素、怎样在运行时拦截越界、大小计算本身会不会溢出。

数组的内存布局

数组变量本身是一个指针，指向堆上分配的连续内存块。这块内存的头部存放元素个数，紧随其后是元素本身。Sprout 目前只有 i64 元素类型，每个元素 8 字节，长度字段也用 i64 存储。

1
2
3
4
5
6
7
堆块起始地址 p
┌──────────┬──────────┬──────────┬───┬──────────┐
│ length   │ elem[0]  │ elem[1]  │ … │ elem[n-1]│
│  (i64)   │  (i64)   │  (i64)   │   │  (i64)   │
└──────────┴──────────┴──────────┴───┴──────────┘
偏移  +0       +8        +16              +8n
     ◄──────── 总大小 = 8 + 8×n 字节 ────────────►

let a: [i64] = [10, 20, 30]; 分配 8 + 8×3 = 32 字节。偏移 0 处写入长度 3，偏移 8、16、24 处依次写入 10、20、30。变量 a 持有的是这块内存的起始地址，占用一个 64 位指针宽度。

这个布局简单但不是任意选择。长度放在元素前面，访问 len(a) 只需读指针指向的第一个 i64，不需要额外的间接跳转。元素紧跟其后且类型固定，计算第 i 个元素的地址只需要 p + 8 + 8*i，一次乘法一次加法。

分配与初始化

数组字面量 [1, 2, 3] 在代码生成阶段翻译成一段序列：计算总大小、调用 malloc、写入长度、逐个写入元素。

分配大小的计算需要格外小心。假设数组长度为 n，总大小是 8 + 8 * n。在 64 位系统上，n 是 i64，乘法和加法都在 64 位范围内进行。如果 n 极大，8 * n 可能溢出 64 位无符号范围，得到一个远小于实际需要的数值。malloc 拿到这个缩水的大小，分配出过短的内存块，后续写入元素时越过边界。

Sprout 在分配前检查溢出。n 必须满足 n <= (UINT64_MAX - 8) / 8，否则产生运行时错误。对 64 位系统，这个上界是 2305843009213693950，约 2.3 × 10^18。实际上，远在达到这个上界之前，系统内存早已耗尽。但编译器不能假设 malloc 会处理所有异常——一个被溢出截断的小数值可能恰好是可分配的大小，程序在没有任何错误报告的情况下写入未分配的内存。

生成的 LLVM IR 大致如下（省略了错误处理函数的声明）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
; 分配 [10, 20, 30]
  %n = i64 3
  ; 溢出检查：n > (2^64 - 9) / 8 ?
  %max_len = i64 2305843009213693950
  %ovf = icmp ugt i64 %n, %max_len
  br i1 %ovf, label %trap_alloc, label %do_alloc

do_alloc:
  %elem_bytes = mul i64 %n, 8
  %total = add i64 %elem_bytes, 8
  %ptr = call ptr @malloc(i64 %total)
  ; 写入长度
  store i64 3, ptr %ptr
  ; 写入元素：ptr + 8, ptr + 16, ptr + 24
  %e0 = getelementptr i8, ptr %ptr, i64 8
  store i64 10, ptr %e0
  %e1 = getelementptr i8, ptr %ptr, i64 16
  store i64 20, ptr %e1
  %e2 = getelementptr i8, ptr %ptr, i64 24
  store i64 30, ptr %e2

字面量的长度在编译期已知，溢出检查在编译期即可完成。但 Sprout 后续会支持运行时确定长度的数组，那时检查必须在运行时执行。本篇先把检查逻辑固定下来，无论长度是否已知都生成完整路径。

索引与边界检查

a[i] 读取数组第 i 个元素。合法的索引范围是 0 <= i < length。超出这个范围——无论是负数还是大于等于长度——都是运行时错误，编译器生成的代码必须在访问内存之前拦截它。

Sprout 的索引类型是 i64，有符号整数。负数索引天然小于 0，这一侧的检查直接判断 i < 0。但另一侧需要注意：length 也存为 i64，合法长度总是非负的，因此 i >= length 的比较在有符号语义下是正确的。两个条件用 or 合并，任一为真则跳到错误路径。

生成的 LLVM IR：

1
2
3
4
5
6
7
8
9
10
11
12
; a[i] 的边界检查
  %len = load i64, ptr %arr_ptr          ; 读取长度
  %lo  = icmp slt i64 %i, 0              ; i < 0 ?
  %hi  = icmp sge i64 %i, %len           ; i >= length ?
  %oob = or i1 %lo, %hi
  br i1 %oob, label %trap_bounds, label %do_access

do_access:
  %offset = mul i64 %i, 8
  %base   = add i64 %offset, 8
  %elem   = getelementptr i8, ptr %arr_ptr, i64 %base
  %val    = load i64, ptr %elem

trap_bounds 调用运行时错误函数，报告越界的索引值、数组长度和源码位置。错误信息包含源码范围（span），与第 03 篇建立的位置追踪体系对接。

值得单独说一下 getelementptr（GEP）。GEP 是 LLVM 的地址计算指令，它只计算地址，不读写内存。上面的代码用 i8 基类型按字节偏移计算目标地址，这比用 LLVM 的数组类型更直接——Sprout 的堆块不是 LLVM 意义上的数组类型，而是一段原始内存，头部是长度，后面是元素。用 i8 基类型加字节偏移可以精确表达这个布局，不需要让 LLVM 的类型系统去理解 Sprout 的对象头。

空数组

let a: [i64] = []; 是合法表达式。长度为 0，分配大小 8 + 8×0 = 8 字节——只有长度字段，没有元素。变量 a 持有一个有效指针，len(a) 返回 0。

对空数组执行任何索引操作都会触发边界检查失败。a[0] 尝试访问索引 0，但 0 >= length（0 >= 0 为真），进入错误路径。这意味着空数组只能用来传递"没有数据"这个信息，不能被解引用。它在内存中确实存在，不是空指针。

负索引

a[-1] 是运行时错误，不是从末尾倒数访问。i < 0 检查在索引为负时直接成立，跳到错误路径。不同于 Python 这类把负索引映射到末尾位置的语言，Sprout 把负数视为越界。

如果省略 i < 0 的检查会怎样？i64 的 -1 在二进制中是全 1，解释为无符号时是 2^64 - 1，远大于任何合法长度。因此 i >= length 在无符号比较下仍能拦住它。但这个推理依赖于长度非负的不变量和特定的比较指令选择。显式拆成两个有符号比较更清楚：一个检查下界，一个检查上界，不需要在有符号和无符号之间来回切换。

有一种常见的优化把两个比较合并成一次无符号比较：把 i 转为无符号后判断 i >= length。负数转为无符号后变成极大的正数，自然大于任何合法长度。这在生成代码时是有效的优化，但 Sprout 目前在 IR 层面保留两个显式比较，把合并留给 LLVM 的后端优化。

len(a) 内建函数

len(a) 返回数组长度。它不是用户定义的函数，而是编译器内建操作。代码生成时，len(a) 直接翻译为从数组指针偏移 0 处加载一个 i64：

1
%len = load i64, ptr %arr_ptr

没有函数调用开销，没有间接跳转。这也解释了为什么长度放在堆块开头——它是最频繁被访问的元数据，每次边界检查都要读它。

边界检查的代价与必要性

每次数组访问都插入两次比较和一次分支，这不是免费的。在一个紧密循环中遍历数组，边界检查的分支预测通常总是落到"安全"一侧，现代 CPU 的分支预测器可以很好地处理这种情况。但检查本身仍然占用指令槽位，增加代码体积。

能不能去掉循环中的边界检查？可以，但不在本篇。如果循环变量 i 从 0 递增到 len(a) - 1，编译器可以在循环外一次性验证范围，循环体内的逐次检查就是冗余的。这种优化叫做循环边界消除（loop bounds check elimination），依赖于归纳变量分析和不变量提升——这些是 LLVM 已经做得很好的 pass。Sprout 在 IR 层面始终生成完整的边界检查，把消除的决策交给 LLVM 后端。

不检查边界的后果是真实的。C 语言不检查数组越界，缓冲区溢出是四十年来最持久的安全漏洞类型。Sprout 选择每次检查的理由很简单：一个确定会崩溃的程序比一个默默写坏内存的程序更容易修复。

关于目标指针宽度

本篇的所有大小计算假设 64 位目标：指针 8 字节，i64 也是 8 字节。这不是巧合——第 01 篇锁定的目标三元组是 x86_64-unknown-linux-gnu，data layout 指定指针宽度为 64 位。

如果要支持 32 位目标，堆块的长度字段仍然用 i64（语言语义），但指针变成 4 字节，malloc 的参数类型可能是 32 位的 size_t。总大小的计算需要检查是否超过 32 位 size_t 的范围（约 4 GB），而不是 64 位的上限。这些调整集中在代码生成阶段，与前端和 SSA 无关。本系列主线只处理 64 位目标，32 位留作练习。

数组与之前的编译管线

数组在各个编译阶段引入了新问题。词法和语法需要识别方括号字面量 [1, 2, 3] 和索引表达式 a[i]。类型检查需要区分 i64 和 [i64]，拒绝 a + 1 这样对数组施加算术的表达式。名称解析需要把 len 识别为内建函数而不是用户定义的标识符。

SSA 构造阶段，数组指针像普通 i64 值一样参与 phi 节点和数据流。SSA 不需要知道值指向堆内存还是纯粹是个整数——它只关心定义和使用的关系。但代码生成必须知道：对数组类型的变量，赋值传递的是指针而不是整块数据的拷贝，离开作用域时需要释放堆内存（第 16 篇会处理引用计数），函数参数传递的也是指针。

参考解释器同步增加数组值的表示。解释器用宿主语言的 Vec<i64> 存放元素，在索引时执行相同的边界检查。差分测试对比解释器和编译后程序的输出，要求两者在正常输入和越界输入上的行为完全一致——都输出相同值，或都报告相同类别的错误。

完整示例

1
2
3
4
5
6
7
fn main() -> i64 {
    let a: [i64] = [10, 20, 30];
    print_i64(len(a));       // 输出 3
    print_i64(a[0]);         // 输出 10
    print_i64(a[2]);         // 输出 30
    return 0;
}

编译运行，stdout 依次输出 3、10、30，退出码 0。把 a[2] 改成 a[3]，运行时报告越界错误，包含索引 3、长度 3 和源码位置。把 a[2] 改成 a[-1]，运行时报告负索引越界，同样带源码位置。

空数组测试：

1
2
3
4
5
6
fn main() -> i64 {
    let b: [i64] = [];
    print_i64(len(b));       // 输出 0
    print_i64(b[0]);         // 运行时错误：索引 0 越界，长度 0
    return 0;
}

len(b) 正常返回 0。下一行触发越界，程序在错误报告后终止，不会执行到 return。

练习与资料

  1. 64 位系统上，数组的最大合法长度是多少？写出计算过程：(2^64 - 1 - 8) / 8，结果是 2305843009213693950。在这个长度下，堆块总大小是多少字节？它能否放进实际物理内存？
  2. 把边界检查的两个有符号比较合并为一次无符号比较 icmp uge i64 %i, %len。解释为什么当 length >= 0 时这个变换是正确的，画出 i64 值域在有符号和无符号解释下的映射关系。
  3. 如果元素类型改为 bool（1 字节），堆块布局会怎样变化？需要考虑对齐吗？

LLVM LangRef 的 getelementptr 文档说明了 GEP 的地址计算规则与 inbounds 标志的含义。LLVM 的 Data Layout 格式定义了指针宽度、对齐和大小端。本篇所有命令基于第 01 篇锁定的工具链版本执行。

上一篇：14 - 接入 LLVM 优化与后端。下一篇：16 - 字符串和引用计数。