本章是系列文章的第五章，介绍了指针分析方法。指针分析在C/C++语言中非常重要，分析的结果可以有效提升指针的优化效率。
本文中的所有内容来自学习DCC888的学习笔记或者自己理解的整理，如需转载请注明出处。周荣华@燧原科技
1 #include <stdio.h>2 int main() {3 int i = 7;4 int *p = &i;5 *p = 13;6 printf("The value of i = %d\n", i);7 }
给定上面的例子。gcc的-O1选项能优化成什么样子？
将上述代码保存到pta5.1.cc，并使用“gcc -O1 pta5.1.cc -S”进行编译，生成的汇编代码如下：
1 .file "pta5.1.cc" 2 .section .rodata.str1.1,"aMS",@progbits,1 3 .LC0: 4 .string "The value of i = %d\n" 5 .text 6 .globl main 7 .type main, @function 8 main: 9 .LFB30:10 .cfi_startproc11 subq $8, %rsp12 .cfi_def_cfa_offset 1613 movl $13, %edx14 movl $.LC0, %esi15 movl $1, %edi16 movl $0, %eax17 call __printf_chk18 movl $0, %eax19 addq $8, %rsp20 .cfi_def_cfa_offset 821 ret22 .cfi_endproc23 .LFE30:24 .size main, .-main25 .ident "GCC: (Ubuntu 5.4.0-6ubuntu1~16.04.12) 5.4.0 20160609"26 .section .note.GNU-stack,"",@progbits
从汇编代码看，程序直接忽略掉了第3行和第4行的初始化和传地址操作，直接实现了第5行的赋值和第6行的打印。性能是不是强大了很多。
再看个例子：
1 #include <stdio.h> 2 #include <stdlib.h> 3 void sum0(int *a, int *b, int *r, int N) { 4 int i; 5 for (i = 0; i < N; i++) { 6 r[i] = a[i]; 7 if (!b[i]) { 8 r[i] = b[i]; 9 }10 }11 }12 void sum1(int *a, int *b, int *r, int N) {13 int i;14 for (i = 0; i < N; i++) {15 int tmp = a[i];16 if (!b[i]) {17 tmp = b[i];18 }19 r[i] = tmp;20 }21 }22 void print(int *a, int N) {23 int i;24 for (i = 0; i < N; i++) {25 if (i % 10 == 0) {26 printf("\n");27 }28 printf("%8d", a[i]);29 }30 }31 #define SIZE 1000032 #define LOOP 10000033 int main(int argc, char **argv) {34 int *a = (int *)malloc(SIZE * 4);35 int *b = (int *)malloc(SIZE * 4);36 int *c = (int *)malloc(SIZE * 4);37 int i;38 for (i = 0; i < SIZE; i++) {39 a[i] = i;40 b[i] = i % 2;41 }42 if (argc % 2) {43 printf("sum0\n");44 for (i = 0; i < LOOP; i++) {45 sum0(a, b, c, SIZE);46 }47 } else {48 printf("sum1\n");49 for (i = 0; i < LOOP; i++) {50 sum1(a, b, c, SIZE);51 }52 }53 }
在教材中提供的编译器编译的结果看，-O1无法有效优化sum0的指针操作，但对sum1手工优化后的代码能很好的进行指针优化。这是教材中提供的运行数据：
1 $> time ./a.out 2 sum0 3 0 1 0 3 4 0 11 0 13 5 real 0m6.299s 6 user 0m6.285s 7 sys 0m0.008s 8 $> time ./a.out a 9 sum110 0 1 0 311 0 11 0 1312 real 0m1.345s13 user 0m1.340s14 sys 0m0.004s
但我用gcc5编译实测下来的结果是-O0，确实不会优化，-O1仍然有很好的优化（时间是-O0的十分之一），并且sum0和sum1性能上差别不大，说明编译器进化的非常快。
1 ronghua.zhou@794bb5fbd58a:~/DCC888$ gcc pta5.2.c -O0 2 ronghua.zhou@794bb5fbd58a:~/DCC888$ time ./a.out 3 sum0 4 5 real 0m5.772s 6 user 0m5.767s 7 sys 0m0.004s 8 ronghua.zhou@794bb5fbd58a:~/DCC888$ time ./a.out a 9 sum110 11 real 0m4.766s12 user 0m4.761s13 sys 0m0.004s14 ronghua.zhou@794bb5fbd58a:~/DCC888$ gcc pta5.2.c -O115 ronghua.zhou@794bb5fbd58a:~/DCC888$ time ./a.out16 sum017 18 real 0m0.542s19 user 0m0.541s20 sys 0m0.000s21 ronghua.zhou@794bb5fbd58a:~/DCC888$ time ./a.out a22 sum123 24 real 0m0.473s25 user 0m0.473s26 sys 0m0.000s
由于sum0和sum1本身计算时间相差不大，所以外面主要对比一下sum0在-O0时的代码和-O1时的代码的差别。
不优化的结果：
1 sum0: 2 .LFB2: 3 .cfi_startproc 4 pushq %rbp 5 .cfi_def_cfa_offset 16 6 .cfi_offset 6, -16 7 movq %rsp, %rbp 8 .cfi_def_cfa_register 6 9 movq %rdi, -24(%rbp)10 movq %rsi, -32(%rbp)11 movq %rdx, -40(%rbp)12 movl %ecx, -44(%rbp)13 movl $0, -4(%rbp)14 jmp .L215 .L4:16 movl -4(%rbp), %eax17 cltq18 leaq 0(,%rax,4), %rdx19 movq -40(%rbp), %rax20 addq %rax, %rdx21 movl -4(%rbp), %eax22 cltq23 leaq 0(,%rax,4), %rcx24 movq -24(%rbp), %rax25 addq %rcx, %rax26 movl (%rax), %eax27 movl %eax, (%rdx)28 movl -4(%rbp), %eax29 cltq30 leaq 0(,%rax,4), %rdx31 movq -32(%rbp), %rax32 addq %rdx, %rax33 movl (%rax), %eax34 testl %eax, %eax35 jne .L336 movl -4(%rbp), %eax37 cltq38 leaq 0(,%rax,4), %rdx39 movq -40(%rbp), %rax40 addq %rax, %rdx41 movl -4(%rbp), %eax42 cltq43 leaq 0(,%rax,4), %rcx44 movq -32(%rbp), %rax45 addq %rcx, %rax46 movl (%rax), %eax47 movl %eax, (%rdx)48 .L3:49 addl $1, -4(%rbp)50 .L2:51 movl -4(%rbp), %eax52 cmpl -44(%rbp), %eax53 jl .L454 nop55 popq %rbp56 .cfi_def_cfa 7, 857 ret58 .cfi_endproc59 .LFE2:60 .size sum0, .-sum061 .globl sum162 .type sum1, @function
O1优化后的结果：
1 sum0: 2 .LFB38: 3 .cfi_startproc 4 testl %ecx, %ecx 5 jle .L1 6 movl $0, %eax 7 .L4: 8 movl (%rdi,%rax,4), %r9d 9 movl %r9d, (%rdx,%rax,4)10 movl (%rsi,%rax,4), %r8d11 testl %r8d, %r8d12 cmovne %r9d, %r8d13 movl %r8d, (%rdx,%rax,4)14 addq $1, %rax15 cmpl %eax, %ecx16 jg .L417 .L1:18 rep ret19 .cfi_endproc20 .LFE38:21 .size sum0, .-sum022 .globl sum123 .type sum1, @function
这个函数从O0到O1的优化过程中使用了很多优化方法，对于这里说的指针分析，由于指针的求地址和解引用非常耗时，O1使用cmovne将必要和拷贝优化成单个指令，起到了很好的效果。
在大多数情况下，sum0和sum1是等价的，但如果b和r这2个指针指向同一个地址的时候，2个算法就会有一些差别，所以编译器不能直接将sum0优化成sum1。
指针分析的目标是找到每个指针指向的地址。
指针分析经常使用基于约束系统的分析方法来描述和解决。
性能最好的指针分析算法的复杂度是O(n3)。
为了提升效率和精准度，指针分析是编译器设计中仅次于寄存器分配方法的第二大课题。
如下图所示，由于l2和l5会相互影响，但很难通过简单的语法分析就能找到他们之间的联系，所以基本的数据流分析对指针分析会失效。
常见的四种指针构造过程（控制流分析里面原来用?表达右边是左边的约束，但这个很容易和之前求指针分析时的约束弄混，因为约束是?，换算成控制流要转向成?，不知道别人会不会晕，反正我被弄晕了。所以最后我改成<-表示控制流图里面的边的方向，这样看着稍微好懂点）：
指令 | 约束名 | 约束 | 控制流分析结果 |
|---|---|---|---|
| a = &b | base | P(a)? {b} | lhs <- rhs |
| a = b | simple | P(a)? P(b) | lhs <- rhs |
| a = *b | load | t ∈ P(b)? P(a)? P(t) | {t} <- rhs' ? lhs <- rhs |
| *a = b | store | t ∈ P(a)? P(t)? P(b) | {t} <- rhs' ? lhs <- rhs |
Andersen指针分析法，又称为基于集合包含的的约束分析法。
Anderson的指向图算法：
1 let G = (V, E) 2 W = V 3 while W ≠ [] do 4 n = hd(W) 5 for each v ∈ P(n) do 6 for each load "a = *n" do 7 if (v, a) ? E then 8 E = E ∪ {(v, a)} 9 W = v::W10 for each store "*n = b" do11 if (b, v) ? E then12 E = E ∪ {(v, a)}13 W = b::W14 for each (n, z) ∈ E do15 P(z) = P(z) ∪ P(n)16 if P(z) has changed then17 W = z::W
上面的算法做一些解释：
W = v::W 的含义是将W这个数组的头部增加一个元素v。
n = hd(W) 表示从数组W中取出头结点，赋值给n。
例如，对下面的代码：
1 b = &a2 a = &c3 d = a4 *d = b5 a = *d
生成的指向图是这样的：
找到图的传递闭包的算法复杂度达到O(n3)，使得科学家们一直没停止过对它的优化。
循环坍塌是二十一世纪出发现的一种优化方法，循环坍塌的理论基础是强连通图的拓扑一致性，在指向分析图中，表示形成循环的所有节点，都有一致的指向分析集合。
算法能用和算法在实际中能用是两个概念。
DFS可以发现循环，但发现的复杂度也不低。DFS的目标是遍历所有节点，但如果想要通过DFS发现环的话，就不但要记录节点，还要记录节点的所有边，这样才能区别一个节点的子结点已经遍历过的情况下判断出只是菱形依赖，还是环。
常见的循环识别方法有波传递算法（Wave propagation），深度传递算法（Deep propagation）和惰性循环检测方法（Lazy cycle detection）。
参见The ant and the grasshopper: fast and accurate pointer analysis for millions of lines of code, 2007。这篇文章实际提出了两种循环检测方法，一种是惰性循环检测，一种是混合循环检测。
增加惰性循环检测之后的算法相对于没有循环检测的方法，主要增加了第2行和第16~18行。其中第2行是增加了一个集合初始化（用来避免重复进行循环检测）。16~18行主要是发现某条边的2个节点的指向集合相等的情况下触发循环检测，检测成功就直接触发循环坍塌。不论是否检测到循环，都会将疑似循环的边加入到已检测的集合中。
1 let G = (V, E) 2 R = {} 3 W = V 4 while W ≠ [] do 5 n = hd(W) 6 for each v ∈ P(n) do 7 for each load "a = *n" do 8 if (v, a) ? E then 9 E = E ∪ {(v, a)}10 W = v::W11 for each store "*n = b" do12 if (b, v) ? E then13 E = E ∪ {(v, a)}14 W = b::W15 for each (n, z) ∈ E do16 if P(z) = P(n) and (n, z) ? R then17 DETECTANDCOLLAPSECYCLES(z)18 R = R∪ {(n, z)}19 P(z) = P(z) ∪ P(n)20 if P(z) has changed then21 W = z::W
优点：仅在非常大可能性能找到环的情况下才触发环形检测；概念简单，容易实现。
缺点：触发检测前环已经存在一段时间，会降低部分性能；即使概率很大的时候，环形检测还是有可能失败（当前还没有失败的证据）。
对下面的伪代码：
1 c = &d2 e = &a3 a = b4 b = c5 c = *e
生成的指向图如下（其中a/b/c触发了循环坍塌）：
波传递算法的伪代码如下：
1 repeat 2 changed = false 3 collapse Strongly Connected Components 4 WAVEPROPAGATION 5 ADDNEWEDGES 6 if a new edge has been added to G then 7 changed = true 8 until changed = false 9 10 11 WAVEPROPAGATION(G, P, T)12 while T ≠ []13 v = hd(T)14 Pdif = Pcur(v) – Pold(v)15 Pold(v) = Pcur(v)16 if Pdif ≠ {}17 for each w such that (v, w) ∈ E do18 Pcur(w) = Pcur(w) ∪ Pdif19 20 21 ADDNEWEDGES(G = (E, V), C)22 for each operation c such as l = *r ∈ C do23 Pnew = Pcur(r) – Pcache(c)24 Pcache(c) = Pcache(c) ∪ Pnew25 for each v ∈ Pnew do26 if (v, l) ? E then27 E = E ∪ {(v, l)}28 Pcur(l) = Pcur(l) ∪ Pold(v)29 for each operation c such as *l = r do30 Pnew = Pcur(l) – Pcache(c)31 Pcache(c) = Pcache(c) ∪ Pnew32 for each v ∈ Pnew do33 if (r, v) ? E then34 E = E ∪ {(r, v)}35 Pcur(v) = Pcur(v) ∪ Pold(r)
上述算法中的参数的含义如下：
对下面的伪代码：
1 h = &c 2 e = &g 3 b = c 4 h = &g 5 h = a 6 c = b 7 a = &e 8 f = d 9 b = a10 d = *h11 *e = f12 f = &a
生成的指向图如下（其中b/c和d/f/g触发了循环坍塌）：
对应的堆内存拓扑图如下：
如果把Anderson指针分析算法中的集合包含换成等号（将包含符号左右两侧的集合先求并集，然后赋值给原来的两个集合），就形成了Steensgaard指针分析算法，也称为基于集合并集的指针分析算法。
对下面的伪代码：
1 x = &a;2 y = &b;3 p = &x;4 p = &y;
生成的指向图如下：
基于链式并集计算的复杂度可以达到α(n)，其中α是Ackermann function的简称，该算法实现也称为Union-Find。算法的具体描述参见An Improved Equivalence Algorithms (1964)。
例如上面例子生成的两个堆的拓扑图，按Steensgaard的分析结论，x可能指向b，y可能指向a。但Anderson的分析结论，x不可能指向b，y不可能指向a，显然Anderson的分析结论更接近事实。
迄今为止，所有分析算法都遵循一种模式：迭代，直到找到一个不动点（也就是说，如果某次迭代后，所有变量都不变，后面再触发迭代，也不会再改变）。
这个通用模式适用于数据流分析、控制流分析和指向分析。
尽管Anderson分析算法比Steensgaard算法精确，但由于它是流无关算法，所以仍然存在一些结论是实际运行中不可能出现，或者不可能同时出现的，这就是流无关分析算法（Flow Insensitive）的局限性。
但是如果按照流相关分析算法（Flow Sensitive）进行分析，每个程序点都需要保留一份独立的分析结论，这对大规模程序的分析是非常昂贵的（常常会带来OOM:)）。
