一、前言
不知您是否了解单指令流多数据流，也就是我们常听说的SIMD（Single Instruction Multiple Data）？它是采用单个控制器来控制多个处理器，同时对一组数据中的每一个分别执行相同的操作，从而实现空间上的并行性的一种技术。就SIMD的工作原理而言，我们可以将其理解为三个层次：
- 编译器具有一定智能，可以自动矢量化（auto-vectorize）所有的代码。
- 编译器自动向量化的能力欠佳，容易受不相关代码变更的影响，因此开发人员需要手动编写明确的SIMD指令。
- 需要重复为每个不同的CPU架构手工编写SIMD。此时，作为工具的编译器，可以通过更好的指令和约束，以适合向量化的形式，编写出可靠的向量化代码。
在日常工作中，我们的开发场景通常处于第二级和第三级，需要用编译器来优化模型。下面，我将和您讨论静态语言（如Rust或C++）编译器优化的一般框架，以及如何将该框架应用于自动矢量化。
二、从编译器的视角看问题
首先，让我们来了解编译器是如何查看代码的。鉴于有着许多结构上相似之处，我们可以参照WebAssembly规范（https://webassembly.github.io/spec/core/）来了解编译器在优化方面的核心规范。如下方简单代码段所示，一个优化单元往往就是一个函数：
fn sum(xs: &[i32]) -> i32 { let mut total = 0; for i in 0..xs.len() { total = total.wrapping_add(xs[i]); } total } 在一些伪IR（指令寄存器）中，上述代码表现为： fn sum return i32 { param xs_ptr: ptr param xs_len: size local total: i32 local i: size = 0 local x: i32 local total: i32 = 0 loop: branch_if i >= xs_len :ret load x base=xs_ptr offset=i add total x add i 1 goto :loop ret: return total }
此处出现了两个重要的特征实体：
- 作为粗略字节数组的程序内存，编译器往往无法很好地推断出内存中的内容。而且由于它们是由所有函数共享的，因此不同的函数可能会以不同的方式去解释内存中的内容。
- 作为整数形式的局部变量，它们遵循编译器可推理的数学属性。
例如，如果编译器看到了如下循环：
param n: u32 local i: u32 = 0 local total: u32 local tmp loop: branch_if i >= n :ret set tmp i mul tmp 4 add t tmp goto :loop ret: return total
它可以推断在每一次循环中，tmp能够保持i * 4，进而会将其优化为：
param n: u32 local i: u32 = 0 local total: u32 local tmp = 0 loop: branch_if i >= n :ret add t tmp add tmp 4 # replace multiplication with addition goto :loop ret: return total
不过，如果我们进行相同的计算，但所有数字都位于内存中，那么编译器将很难推断出转换的正确性。如果针对n的存储和total实际是重叠的，而tmp与某些不在当前函数中的数据重叠了，该怎么办呢？
其实，load和store指令可以作为数学局部变量和内存字节的桥梁。也就是说，load指令在内存中获取一系列字节，将字节解释为整数，并将该整数存储到局部变量中。而store指令的执行操作正好相反。通过将某些内容从内存加载到本地，编译器可以获得对其进行精确推理的能力。因此，编译器无需跟踪内存的基本内容，只需检查在特定时间点，从内存进行的加载是否正确即可。可见，编译器一次只能真正推理一个函数，而且只能推理该函数中的局部变量。
三、将代码向编译器推近些
通过为编译器提供更多的上下文，我们可以实现两项核心的优化任务：
第一项核心优化是内联（inlining）。它使用被调用者去代替特定的调用。据此，调用者和被调用者的局部变量都在同一个框架中，编译器可以一起优化它们。
让我们看一段Rust代码：
fn sum(xs: &[i32]) -> i32 { let mut total = 0; for i in 0..xs.len() { total = total.wrapping_add(xs[i]); } total }
其中的表达式xs[i]实际上是一个函数调用。索引函数在访问数组元素之前，会进行边界检查。将其内联到sum中后，编译器可以看到其代码并消除之。毕竟，在内联之后，函数倾向于处理一般情况，并在特定的调用站点（call-site），使用足够的约束，来消除各种边缘情况。
第二项核心优化是聚合的标量替换（scalar replacement of aggregates，SROA）。我们使用load避免对内存进行推理，而是对本地进行推理。
例如，有如下这样一个函数：
fn permute(xs: &mut Vec<i32>) { ... }
编译器会收到一个指向某段内存的指针。由于该内存包含了一个复杂的结构（即：ptr、len、capacity triple），因此它很难推理出该结构的演变。对此，编译器可以从内存中加载该结构，并使用一堆标量局部变量，来进行替换聚合：
fn permute(xs: &mut Vec<i32>) { local ptr: ptr local len: usize local cap: usize load ptr xs.ptr load len xs.len load cap xs.cap ... store xs.ptr ptr store xs.len len store xs.cap cap }
如此，编译器再次获得了推理能力。虽然与内联类似，但是SROA主要用于内存，而不是代码。
四、不可能与可能
使用编译器模型的主要优势在于：
- 在每个函数的基础上进行优化
- 可以进行内联函数的调用
- 擅长发现局部变量之间的关系，并据此重新排列代码
- 能够对内存进行有限的推理（即，决定何时适合load或store）。
当然，我们需要描述哪些代码可以被可靠地优化，哪些代码无法被优化，从而解释零成本抽象（zero cost abstractions）。针对启用内联的情况，编译器需要知道有哪个函数被实际调用了。如果属于直接调用，编译器则会尝试着与之内联；如果是间接调用（即：通过函数指针或通过虚函数表进行调用），那么在一般情况下，编译器将无法与之内联。对于间接调用而言，编译器有时也可以推断指针的值，并对调用进行去虚拟化（de-virtualize）。不过，这往往依赖于在其他地方已实现了成功的优化。
这也就是为什么在Rust中，每个函数都有一个唯一的、大小为零（zero-sized）的类型，而且并没有运行时（runtime）的表示。它静态的方式保证了编译器始终可以内联到代码上，以使得抽象的成本为零，毕竟任何优化编译器都会将其“融化”为零。
当然，更高级别的语言则可能会选择始终使用函数指针去表示函数。实际上，在许多情况下，它们生成的代码就等效为可优化的。不过，在源代码中是不会有任何迹象来表明这是一个可优化的情况（实际指针在编译时是可知的），还是真正的动态调用状况。因此，使用Rust就保证了可优化和潜在可优化之间的区别，能够反映在源语言之中，请参见如下代码段：
// Compiler is guaranteed to be able to inline call to `f`. fn call1<F: Fn()>(f: F) { f() } // Compiler _might_ be able to inline call to `f`. fn call2(f: fn()) { f() }
由上述代码可知，其第一条规则便是使大多数调用可以被静态解析，以允许内联。而函数指针和动态调度则会防止内联。此外，内存中的间接寻址也会给编译器带来如下麻烦：
struct Foo { bar: Bar, baz: Baz, }
显然，上述Foo结构对编译器是完全透明的。不过，让我们稍作如下修改：
struct Foo { bar: Box<Bar>, baz: Baz, }
上述结果就不那么明确了。也就是说，被Foo占用的内存一般不会转移到被Bar占用的内存处。同样，在许多情况下，鉴于唯一性，编译器可以通过box进行“不保证”的推理。
如下代码段展示了map是如何被签名和定义的。
#[inline] fn map<B, F>(self, f: F) -> Map<Self, F> where Self: Sized, F: FnMut(Self::Item) -> B, { Map::new(self, f) }
关于内存的另一个重点是，一般而言，编译器不能改变整体布局。SROA可以将一些数据结构加载到一堆局部变量中，然后可以用“一对指针”代替“一个指针和一个索引”的表示。不过，SROA最终将不得不具体化“一个指针和一个索引”，并将该表示存储回内存之中。这是因为内存布局是在所有函数之间共享的，因此函数不能单方面地指定更优化的表示。
总之，只要能够“看到”代码，编译器就能够更擅长推理代码。因此，请确保大多数调用在编译时可以实现内联。
五、SIMD
让我们将前面讨论的、为编译器提供可优化代码的通用框架，应用到自动矢量化上。下面是我们优化计算两个字节片之间最长公共前缀的函数。
use std::iter::zip; // 650 milliseconds fn common_prefix(xs: &[u8], ys: &[u8]) -> usize { let mut result = 0; for (x, y) in zip(xs, ys) { if x != y { break; } result += 1 } result }
如果您已经有了自动矢量化的模型，或者已查看了汇编的输出，那么就会发现一次仅处理一个字节的函数，效率非常慢。我们该如何解决这个问题呢？
SIMD既然可以同时处理多个值，那么我们就希望编译器能够同时比较一堆字节。例如，我们通过如下代码段，先一次性处理16个字节，然后分别处理剩余部分，以便使得结构更加显式化：
// 450 milliseconds fn common_prefix(xs: &[u8], ys: &[u8]) -> usize { let chunk_size = 16; let mut result = 0; 'outer: for (xs_chunk, ys_chunk) in zip(xs.chunks_exact(chunk_size), ys.chunks_exact(chunk_size)) { for (x, y) in zip(xs_chunk, ys_chunk) { if x != y { break 'outer; } result += 1 } } for (x, y) in zip(&xs[result..], &ys[result..]) { if x != y { break; } result += 1 } result }
其实，上述代码在速度上的提升是远远不够的。具体来说，SIMD需要以相同的方式，并行处理块中的所有值。在上述代码中，我们用到了一个break。这意味着第n对字节的处理，取决于第n-1对。我们可以通过禁用短路（short-circuiting），来检查整个字节块是否匹配。当然，我们并不关心具体哪个特定字节出现了不匹配：
// 80 milliseconds fn common_prefix3(xs: &[u8], ys: &[u8]) -> usize { let chunk_size = 16; let mut result = 0; for (xs_chunk, ys_chunk) in zip(xs.chunks_exact(chunk_size), ys.chunks_exact(chunk_size)) { let mut chunk_equal: bool = true; for (x, y) in zip(xs_chunk, ys_chunk) { // NB: &, unlike &&, doesn't short-circuit. chunk_equal = chunk_equal & (x == y); } if !chunk_equal { break; } result += chunk_size; } for (x, y) in zip(&xs[result..], &ys[result..]) { if x != y { break; } result += 1 } result }
至此，矢量化已成功开始，而且几乎减少了一个数量级的运行时间。我们现在可以使用迭代器来进行压缩了。
// 80 milliseconds fn common_prefix5(xs: &[u8], ys: &[u8]) -> usize { let chunk_size = 16; let off = zip(xs.chunks_exact(chunk_size), ys.chunks_exact(chunk_size)) .take_while(|(xs_chunk, ys_chunk)| xs_chunk == ys_chunk) .count() * chunk_size; off + zip(&xs[off..], &ys[off..]) .take_while(|(x, y)| x == y) .count() }
显然，此时的代码已与我们开始时有了显著不同。可见，我们不应盲目依赖编译器的优化，而需要知道在何种情况下进行特定优化，以触发它们编写代码的方式。例如，对于SIMD而言，我们需要根据处理元素块来表达算法。而且在每个块中，我们应确保没有分支，让所有元素都能以相同的方式处理。
