LLVM AliasAnalysis别名分析 TBAA TypeBasedAliasAnalysis

一、什么是别名分析

Alias Analysis (又名 Pointer Analysis)是用于确定两个指针是否指向内存中的同一对象，这里有很多不同的别名分析算法，分为几种类型：流敏感vs流非敏感、上下文敏感vs上下文非敏感、域敏感vs域非敏感、基于一致性的vs基于子集的。传统的别名分析用于回答must、may、no的问题，也即两个指针总是指向同一对象，可能指向同一对象以及绝不会指向同一对象。(SSA—静态单一赋值，将同一变量名用多个名表示，被赋值的变量名不会重复，便于寻找变量的产生与使用点)。

二、别名分析有什么用

有这样一个例子：

int foo (int __attribute__((address_space(0)))* a,
         int __attribute__((address_space(1)))* b) {
    *a = 42;
    *b = 20;
    return *a;
}

__attribute__ 指示符指定 a 是一个i32*的地址，b 是一个i32 addrspace(1)*的地址，生成ir如下：

define i32 @foo(i32* nocapture %0, i32 addrspace(1)* nocapture %1) local_unnamed_addr #0 {
  store i32 42, i32* %0, align 4, !tbaa !10
  store i32 20, i32 addrspace(1)* %1, align 4, !tbaa !10
  %3 = load i32, i32* %0, align 4, !tbaa !10
  ret i32 %3
}

我们先忽略指令后边的!tbaa这个metadata信息，这个之后会讲到。这个是clang在O2的场景下生成的IR。现在需要对于函数foo进行进一步的优化，去掉不必要的load：

define i32 @foo(i32* nocapture %0, i32 addrspace(1)* nocapture %1) local_unnamed_addr #0 {
  store i32 42, i32* %0, align 4, !tbaa !10
  store i32 20, i32 addrspace(1)* %1, align 4, !tbaa !10
  ret i32 42
}

但是这个优化有一个前提，就是a和b不能别名，不然可能会有错误：

int i = 0;
int result = foo(&i, &i);

以上可以看到，以上调用会使a和b别名，本应该返回20，结果因为优化的缘故返回了42，导致错误。所以编译器只有确定两个指针不会产生别名时，才能进行以上优化。这个就是别名分析的作用的一个小例子。

三、当前LLVM内置的别名分析

当前LLVM内置使用了多种别名分析，我们这里简单介绍下。

3.1 -basic-aa

不同全局变量、栈分配和堆分配之间永远不会发生别名冲突。 这意味着，如果两个指针分别指向全局变量、栈分配和堆分配，那么它们一定指向不同的内存位置。
全局变量、栈分配和堆分配永远不会与空指针发生别名冲突。 这意味着，指向全局变量、栈分配和堆分配的指针一定指向有效的内存地址，而不是空指针。
结构体的不同成员之间不会发生别名冲突。 也就是说，指向结构体不同成员的指针一定指向不同的内存位置。
具有静态不同的下标的数组索引不会发生别名冲突。 例如，a[0] 和 a[1] 指向不同的内存位置，因此它们不会发生别名冲突。
许多常见的标准 C 库函数不会访问内存或者只读内存。 这意味着，如果一个指针指向由这些函数返回的内存位置，那么它不会与其他指针发生别名冲突。
显然指向常量全局变量的指针具有 "pointToConstantMemory" 属性。 这意味着，指向常量全局变量的指针永远不会被修改，因此不会发生别名冲突。
如果函数调用从未将栈分配的变量传递到函数外部，那么该函数调用不会修改或引用这些变量。 这意味着，在函数内部创建的自动数组不会与其他指针发生别名冲突。

3.2 -typebased-aa（tbaa）

这个就是我们在上边的那个IR中看到的metadata信息，这里是基于类型的别名分析。我们先看一个简单的C++的例子。

#include <cstdio>
using namespace std;

struct tests {
  int size;
  int *arr;
  tests(int _size, int *_arr) : size(_size), arr(_arr) {}

  __attribute__((noinline)) void dump() {
    for (int i = 0; i < size; ++i) {
      printf("%d ", arr[i]);
    }
    printf("\n");
  }
};

int main() {
  int arr1[5] = { 1, 2, 3, 4, 5 };
  int arr2[3] = { 6, 7, 8 };
  tests t(5, arr1);
  t.dump();
  printf("\n");
  return 0;
}

生成的IR如下所示，这里我截取了关键部分的IR：

; i32:size i32*:arr
%struct.tests = type { i32, i32* }

define i32 @main() local_unnamed_addr #0 {
  %1 = alloca [5 x i32], align 4
  %2 = alloca %struct.tests, align 8
  %3 = bitcast [5 x i32]* %1 to i8*
  call void @llvm.lifetime.start.p0i8(i64 20, i8* nonnull %3) #6
  call void @llvm.memcpy.p0i8.p0i8.i64(i8* noundef nonnull align 4 dereferenceable(20) %3, i8* noundef nonnull align 4 dereferenceable(20) bitcast ([5 x i32]* @__const.main.arr1 to i8*), i64 20, i1 false)
  %4 = bitcast %struct.tests* %2 to i8*
  call void @llvm.lifetime.start.p0i8(i64 16, i8* nonnull %4) #6
  %5 = getelementptr inbounds [5 x i32], [5 x i32]* %1, i64 0, i64 0
  %6 = getelementptr inbounds %struct.tests, %struct.tests* %2, i64 0, i32 0
  ; 存size到struct中
  store i32 5, i32* %6, align 8, !tbaa !10
  %7 = getelementptr inbounds %struct.tests, %struct.tests* %2, i64 0, i32 1
  ; 存arr到struct中
  store i32* %5, i32** %7, align 8, !tbaa !16
  call void @_ZN5tests4dumpEv(%struct.tests* nonnull %2)
  %8 = call i32 @putchar(i32 10)
  call void @llvm.lifetime.end.p0i8(i64 16, i8* nonnull %4) #6
  call void @llvm.lifetime.end.p0i8(i64 20, i8* nonnull %3) #6
  ret i32 0
}

!10 = !{!11, !12, i64 0}
!11 = !{!"_ZTS5tests", !12, i64 0, !15, i64 8}
!12 = !{!"int", !13, i64 0}
!13 = !{!"omnipotent char", !14, i64 0}
!14 = !{!"Simple C++ TBAA"}
!15 = !{!"any pointer", !13, i64 0}
!16 = !{!11, !15, i64 8}
!17 = !{!12, !12, i64 0}

我们先看一下tbaa的结构，tbaa存的主要是类型信息，概括一下就是三个数据，我们当前处理的base的类型是什么，我们当前获取到的实际类型是什么，这个实际类型在base中的偏移是多少。我们可以看存arr的这条store指令是16这条metadata，其中11就是base类型也就是test，11中存了test类型的layout，然后16中的15就是获取到的类型，对于store指令也就是%5的类型是个指针，也就与15的类型相匹配，最终的这些类型都会指向13和14这两条公共父节点，这样其实构成了一个树状结构。然后16中的第三个操作数是8表示arr在test偏移为8的位置，同时我们在树上找test这个节点能看到偏移8对应的是15这条，也与16的实际类型相一致。这个就是tbaa的一个例子，其实就是构成了一个类型树。

基于类型我们能够判断出来一些别名关系，例如：