clang vectorization

llvm

• 三段式, 预处理, 字节码, 优化器汇编;

• 这种就方便高级用户自己创建语言, 并实现对应的编译器;

gcc

• 面向特定语言的编译器, 奇淫技巧, 编译优化上更专业;

优化器

• llvm更只能, 更加用户友好, 编译速度快; 且不断开发迭代;
• gcc 用户不太友好, 但是普遍更优;

https://llvm.org/docs/Vectorizers.html

优化简介

• innerloop vectorization 将最内层的循环使用SIMD优化, 减少循环(across multiple loop iterations), 一次尽量多的处理数据;

• SIMD:single instruction,multiple data; 是同时对多个数据执行相同的操作, 而不是多个数据组合成一个数据再执行;

• 如果是后者在处理浮点时就不适用; 注意区分同一个指令;各自执行同样的操作;

动态检查执行

• llvm vectorizer保留两份代码, 保存优化的循环和原始的循环, 通过动态检测来执行哪个;

• 这种会增加一点代码量, 但是不多, 可能会减少指令命中率;

参数

• -ffast-math -O3 -msse2 -march=native -mavx2 -mss4等;

优化数量未知数量的循环

• unrool loop: 即尽量的优化, 剩下部分使用源代码;

void test(int *a, int len) {
 for(int i = 0 ; i < len ; ++i) {
   a[i] += 5;
 }
}

int main(int argc,char**argv) {
 int* a = new int[argc<<10];
 test(a,argc<<10);
 return a[0];
}
1
2
3
4
5
6
7
8
9
10
11

• 实际优化后的样子

void test(int *a, int len) {
 int i;
 for(i = 0 ; i < len - 3 ; i += 4) {
   a[i] += 5;
   a[i + 1] += 5;
   a[i + 2] += 5;
   a[i + 3] += 5;
 }
 for(int j = i ; j < len ; j++) {
   a[j] += 5;
 }
}
1
2
3
4
5
6
7
8
9
10
11
12

• 可以看到, 最终还是会保留一部分循环;

小结

• 优化未知会保留一部分循环, 优化已知会尽量优化, 不能整除的直接完全扩张成n%w个表达式; 不会保留循环;

为什么

• SIMD是加载若干个数据进行操作, 如果是A,B数组出现重复, 那么重复部分有先后依赖关系, 使用SIMD就会出现bug; 所以需要动态检测;

• 动态检测, 合法就执行优化版本代码, 不合法就使用原始循环;

restrict

• 修饰符告诉编译器，指针自己独占, 没有其他使用, 尽管优化; 编译器则认为独占, 就会使用其他优化手段优化; 而调用正确性就需要用户自行保证;

案例分析

void updatePtrs(size_t *ptrA, size_t *ptrB, size_t *val)
{
 *ptrA += *val;
 *ptrB += *val;
}
1
2
3
4
5

• 不能进行优化, 如果ptra, ptrb指向同一个地址, 那么这个函数的意思就是给同一个加2 * *val

• 如果不是同一个, 则是各自加*val;

• 使用restrict限制表示开发者知道, 传入的指针不可能相同, 则进行其他优化; 正确性由开发者自行保障;

• https://en.wikipedia.org/wiki/Restrict
• https://zhuanlan.zhihu.com/p/349726808

; Hypothetical RISC Machine.
ldr r12, [val]     ; Load memory at val to r12.
ldr r3, [ptrA]     ; Load memory at ptrA to r3.
add r3, r3, r12    ; Perform addition: r3 = r3 + r12.
str r3, [ptrA]     ; Store r3 to memory location ptrA, updating the value.
ldr r3, [ptrB]     ; 'load' may have to wait until preceding 'store' completes.
ldr r12, [val]     ; Have to load a second time to ensure consistency.
add r3, r3, r12
str r3, [ptrB]

ldr r12, [val]  ; Note that val is now only loaded once.
ldr r3, [ptrA]  ; Also, all 'load's in the beginning ...
ldr r4, [ptrB]
add r3, r3, r12
add r4, r4, r12
str r3, [ptrA]  ; ... all 'store's in the end.
str r4, [ptrB]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 前后指令优化对比;

小结

• 动态检测指针, 决定执行优化版本还是普通版本;

解释概念

• https://stackoverflow.com/questions/14955912/what-is-reduction-variable-could-anyone-give-me-some-examples

案例分析

int foo(int *A, int *B, int n) {
 unsigned sum = 0;
 for (int i = 0; i < n; ++i)
   sum += A[i] + 5;
 return sum;
}
1
2
3
4
5
6

• SIMD怎么操作sum? 同时操作? 同时操作会不会出问题?

• 这种变量会进行优化: 拆分成若干独立的变量result = var1 op var2;, 最后按照op将拆分的result进行合并即可;

• 一般结合-ffast-math使用;

int foo(int *A, int *B, int n) {
 unsigned sum0 = 0;
 unsigned sum1 = 0;
 unsigned sum2 = 0;
 unsigned sum3 = 0;
 for (int i = 0; i < n - 3; i += 4) {
   sum0 += A[i] + 5;
   sum1 += A[i + 1] + 5;
   sum2 += A[i + 2] + 5;
   sum3 += A[i + 3] + 5;
 }
 return sum0 + sum1 + sum2 + sum3;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

指针类型的induction

• 这类也可以优化, 原理差不多, 动态判断是否采用优化版本循环;

int baz(int *A, int n) {
 return std::accumulate(A, A + n, 0);
}
1
2
3

小结

• 将看似强相关的共享变量,拆分分支,归并结果;进行优化;

• Inductions variable: i, Reduction variable: sum;

简介

• 尝试用算法去掉if else甚至goto; 将分支依赖变成数据依赖，即所有都执行。这样会导致任务变多，可能会变慢；

• 参考MIT 6.172 3. bit hacks

其他

• 在一个循环中，进行计算 sum, 计数+1，偶数+2 的计算并编译优化即可反汇编看到优化；

• 其他参考相应的 paper

说明

• ++变成--, 这种也可以优化;

其他

int foo(int *A, int *B, int n) {
 for (int i = n; i > 0; --i)
   A[i] +=1;
}
1
2
3
4

说明

• https://en.wikipedia.org/wiki/Vectored_I/O

• llvm的loop vectorizer可以将代码中零散内存中获取数据行为的也进行优化;

案例

int foo(int * A, int * B, int n) {
 for (intptr_t i = 0; i < n; ++i)
   A[i] += B[i * 4];
}
1
2
3
4

• 这种就是内存零散, 也是比较常见的;

说明

• 会评估是否有优化, 没有则不懂, 或者动态判断保留两份代码;

案例

int foo(int *A, char *B, int n, int k) {
 for (int i = 0; i < n; ++i)
   A[i] += 4 * B[i];
}
1
2
3
4

• 这种类型不一样;

说明

• 这些也可以直接进行vectorize

常见

pow exp exp2
sin cos sqrt 
log log2 log10
fabs floor ceil
fma trunc nearbyint fmuladd
1
2
3
4
5

说明

• 取决于生成文件大小和寄存器压力. 是否保留两份?

SLP vectorization

• SLP: Superword-Level Parallelism

• 在内部循环中, 自底向上找op相同, 但数据不同的零散代码进行vec操作;

• 支持内存访问, 算数运算, 比较等都可以vectorization;

outer loop vectorization

• 这种一般应用于特定语言和程序, 如OpenCL,CUDA, 这种非常依赖于外部vectorization的数据操作;

SLP案例

void foo(int a1, int a2, int b1, int b2, int *A) {
 A[0] = a1*(a1 + b1);
 A[1] = a2*(a2 + b2);
 A[2] = a1*(a1 + b1);
 A[3] = a2*(a2 + b2);
}
1
2
3
4
5
6