4.4 常用优化方法
4.4.1 简单的优化方法
Intel编译器在优化时采用了很多优化方法，包括拷贝传递、常数传播、公共子表达式、循环优化等。首先我们看看下面的代码：
// test1.c
#define DEBUG 0
int test1 ( )
{
int i = rand();
int j = rand();
int a,b,c;
a= i;
b = a+j;
c = a+b;
i = 5+ 14*j + 10;
if (DEBUG)
printf("i=%d",i);
return (c + i);
}
icl /O2 /S test1.c
|
使用/O2选项进行编译，下面给出生成的汇编代码片断，可以看到在这个过程中编译器进行了4个优化：
- 首先是拷贝传递，即把常量或者变量的值直接传播到表达式中，而在这个例子中a=i; b=a+j 被代替以b=i+j。
- 其次是常数折叠（constant folding），i = 5+ 14*j + 10被代替以 i = 14*j +15
- 然后是强度减少（strength reduction），计算时间比较长的乘法运算以移位和减法运算来代替，例子中 14*j = j<<4 – j –j
- 最后是无用代码消除，由于debug为0，也就是条件语句下面的printf永远不会执行，最后生成的代码里面可以看到没有该条件语句。
call _rand
mov esi, eax ; esi = i
call _rand ;eax = j
lea edx, DWORD PTR [eax+esi] ; b = a+j;
add esi, edx ; c=a+b;
mov ecx, eax
shl ecx, 4
sub ecx, eax
sub ecx, eax ; 14*j
lea eax, DWORD PTR [esi+ecx+15] ; i=5+14*j+10, c+i
pop esi
ret
|
接下来我们看看下面的代码：
// test2.c
#define MAX 100
int test2(int *val, int i, int j,int n) {
int up,down,left,right,sum;
int k;
for (i=0; i<MAX; i++) {
k = 4*i+10;
up = val[(k-1)*n + j];
down = val[(k+1)*n + j];
left = val[k*n + j-1];
right = val[k*n + j+1];
sum += up + down + left + right
;
}
return (sum);
}
|
仍然采用/O2选项编译，下面给出了生成的汇编代码的片断，在这里主要的优化有两个：
mov edx, DWORD PTR [esp+24] ;val
xor eax, eax ;
mov ecx, DWORD PTR [esp+32] ;j
mov ebx, DWORD PTR [esp+36]
mov ebp, DWORD PTR [esp+36] ;n
lea ecx, DWORD PTR [edx+ecx*4] ;val+4*j
neg ebx ;
mov DWORD PTR [esp], ebx ;-n
mov edx, 10 ; k = 10
$B4$2: ; Preds $B4$2 $B4$1
mov esi, DWORD PTR [esp] ;-n
mov ebx, ebp
imul ebx, edx ;k*n
add eax, DWORD PTR [ecx+ebx*4+4] ;sum + right: val[j+k*n+1]
add edx, 4 ;k = k+ 4
lea edi, DWORD PTR [esi+ebx] ;k*n-n
mov edi, DWORD PTR [ecx+edi*4] ;up=val[k*n-n+j]
lea esi, DWORD PTR [ebp+ebx] ;k*n+n
add edi, DWORD PTR [ecx+esi*4] ;sum + down:val[k*n+n+j]
add edi, DWORD PTR [ecx+ebx*4-4] ;sum + left: val[k*n+j-1]
add eax, edi ;sum + up;
cmp edx, 410 ;5.14
jl $B4$2 ; Prob 99% ;5.14
$B4$3: ; Preds $B4$2
pop ecx ;13.9
pop ebx ;13.9
pop ebp ;13.9
pop esi ;13.9
pop edi ;13.9
ret ;13.9
|
其实上面的公共子表达式可以更进一步手工优化，如下面代码所示：
int knj = k*n + j;
up = val[knj - n];
down = val[knj + n];
left = val[knj - 1];
right = val[knj + 1];
sum += up + down + left + right;
|
接下来看一个循环不变量优化的例子，它实际上类似于公共子表达式提取，把内循环体中不变的乘法运算n*i提到内循环外面：
int test3(int *a, int *b, int n) {
int i,j;
for (i = 0; i<n; i++)
for (j = 0; j<n; j++)
a[n*i + j] = b[j]+2;
return (0);
}
|
采用/O2选项编译后的汇编代码的片断如下：
imul edi, edx ;n*i
lea esi, DWORD PTR [esi+edi*4] ;a+n*i*4
$B5$4: ;
mov edi, DWORD PTR [ecx+ebp*4] ;
add edi, 2 ;b[j]+2
mov DWORD PTR [esi+ebp*4], edi ;a[n*i+j] = b[j]+2
add ebp, 1 ;4.24
cmp ebp, edx ;4.21
jl $B5$4 ; Prob 82% ;4.21
|
4.4.2 循环交换
循环交换优化用在多重循环中，交换内外两个循环的执行顺序。循环交换一般用于提高缓存的利用率，增加在循环过程中数据访问的局部性（连续性）。考虑下面代码：
// test4.c
#define MAX 1024
int test4(int a[MAX][MAX], int b[MAX][MAX]) {
int i,j;
for (j = 0; j<MAX; j++)
for (i = 0; i<MAX; i++)
a[i][j] = 3*a[i][j]; // a[i][j] = 3* b[i][j] ;
return (0);
}
|
从上面的代码可以看出，循环体是按照a[i][j]、a[i+1][j]的顺序来访问两维数组a的，而C语言中数组在内存中是按照行来存储的，即a[i][j]、a[i][j+1]在内存中是连续的，但是上面的代码中内循环中数组元素的访问顺序是以MAX为步长的。通过把循环交换就可以按顺序访问了：
for (i = 0; i<MAX; j++)
for (j= 0; j<MAX;j++)
a[i][j] = 3*a[i][j]; // a[i][j] = 3* b[i][j] ;
|
循环交换优化在Intel编译器中需要采用/O3选项才会启用，而且同时也要求开启处理器相关的选项。比如采用下列命令编译：
icl /O3 /QxT /S /Qopt-report3 /Qopt-report-phasehlo test.c
从优化报告中可以看到进行了循环交换优化，同时还进行了自动矢量化等优化。注意编译器并不是万能的，在有些情况下可能无法自动进行循环交换，比如上面的循环体中赋值语句改为：a[i][j] = 3* b[i][j] ; 仍然采用上述命令进行编译会发现没有进行循环交换优化，而只是进行了循环展开。另外如果用前面循环不变量的例子来进行编译，优化报告会报告由于可能的数据依赖而没有进行循环交换，因此这时你可以手工修改源代码来进行优化：
<test.c;3:3;hlo_linear_trans;_test3;0>
Loop Interchange not done due to: Data Dependencies
Dependencies found between following statements:
[From_Line# -> (Dependency Type) To_Line#]
[5 ->(Flow) 5] [5 ->(Anti) 5]
Advice: Loop Interchange, if possible, might help Loopnest at lines: 3 4
: Suggested Permutation: (1 2 ) --> ( 2 1 )
|
4.4.3 循环展开
所谓循环展开技术指把那些本来要通过循环迭带连续执行K次的循环体合并在一起作为一个大的循环体，相应的循环索引变量也作相应的改变，k被称为展开因子。比如代码：
for (i =0; i<100; i++)
a[i]=b[i]+c[i];
|
可以循环展开为：
for (i =0; i<100; i+=2) {
a[i]=b[i]+c[i];
a[i+1]=b[i+1]+c[i];
}
|
通过循环展开，循环次数会减少，这样减少了每次循环的跳转指令的开销，另外通过把小的循环体扩展成多条指令，使得处理器的指令级并行技术可以发挥作用，另外通过循环展开还可能消除循环的数据依赖，从而可以进一步进行自动矢量化。当然循环展开带来的一个后果是代码大小的增加。可以通过编译器的选项和在源代码中加进相应的pragma对于什么时候进行循环展开进行控制。具体的编译选项和pragma在前面我们已经介绍过，另外也可以参考Intel编译器的用户手册。
循环展开的一个特殊情形就是在循环次数比较小时把循环体完全展开，这样原来的循环变为顺序执行，不再有分支，考虑下列的代码：
// test5.c
void test6(int r[4], int m[4][4], int v[4]) {
// 3D-transform: Multiply vector V by 4x4 transform matrix M.
int i,j;
for (i = 0; i<4; i++) {
r[i] = 0;
for (j = 0; j<4; j++) {
r[i] += m[j][i] * v[j];
}
}
}
icl /O2 /S /Qopt-report3 /Qopt-report-phasehlo test5.c
|
采用上面的命令编译后查看汇编代码可以看到该循环被完全展开，相当于：
r[0] = m[0][0] * v[0] + m[1][0] * v[1] + m[2][0] * v[2] + m[3][0] * v[3];
r[1] = m[0][1] * v[0] + m[1][1] * v[1] + m[2][1] * v[2] + m[3][1] * v[3];
r[2] = m[0][2] * v[0] + m[1][2] * v[1] + m[2][2] * v[2] + m[3][2] * v[3];
r[3] = m[0][3] * v[0] + m[1][3] * v[1] + m[2][3] * v[2] + m[3][3] * v[3];
|
如果你要自己手动来展开循环，需要考虑到循环次数可能不是展开因子的倍数的情形，考虑下面的代码：
// N 1025, M = 5
for(i=0;i<N; i++) {
for (j=0;j<M; j++) {
a[i][j] = b[i][j] + c[i][j]
}
}
|
假设循环展开因子为4，但是当前N=1025无法整除4，这时你可以采用一种称为后条件循环技术来把原来的循环分成两个循环，前面的循环正好可以展开：
K = N % 4; // K= N MOD 4
//main part of loop
for(i=0;i<N-K; i+=4) {
for (j=0;j<M; j++) {
a[i][j] = b[i][j] + c[i][j];
a[i+1][j] = b[i+1][j] + c[i+1][j];
a[i+2][j] = b[i+2][j] + c[i+2][j];
a[i+3][j] = b[i+3][j] + c[ i+3][j];
}
}
//post conditioning part of loop
for(i= N-K+1;i<N; i++4) {
for (j=0;j<M; j++) {
a[i][j] = b[i][j] + c[i][j];
}
}
|
4.4.4 循环分隔和融合
循环分割优化在前面介绍#pragma distribution point已经提到过，其基本思想是把循环体分割成两个或者多个部分，这样一个循环被分割为两个或者多个循环。通过把循环体分割，然后把那些相似或者完成相同功能的指令组成一个新的循环，这样有可能提高缓存的利用率、消除数据依赖而进行自动矢量化、利用指令级的并行或者进行其他循环优化等来提高性能。
考虑下列代码，由于编译器不知道在调用foo是否会改变a和b的值，即能确保有没有额外效应，因此编译器可能不会进行循环分割。但是如果你知道foo不会有任何问题，那么你可以手工进行分割，前一个部分可以进行自动矢量化：
void test6(int a[100][100], int b[100][100], int len)
{
int i,j;
for (i=0; i<len; i++) {
for (j=0; j < len; j++) {
a[i][j] = a[i][j]*3;
foo(a,b);
}
}
}
|
循环分割后的代码为：
for (i=0; i<len; i++) {
for (j=0; j < len; j++) {
a[i][j] = 3*a[i][j];
}
}
for (i=0; i<len; i++) {
for (j=0; j < len; j++) {
foo(a,b);
}
}
|
循环融合正好和循环分割相反，它是把两个或者多个具有相同循环条件的循环体合并在一起构成一个新的循环。原来的多个循环变成一个循环，循环开销减少了，同时也可能利用指令级并行、缓存的有效访问等技术来提高性能。考虑下列代码：
int test7(int *a, int *b, int len)
{
int i;
for (i = 1; i < len; i++)
a[i] = b[i+1]+b[i-1];
for (i = 1; i< len; i++)
b[i] = a[i+1] + a[i-1];
return (0);
}
|
注意初看起来这两个循环合并之后会出现问题，但是仔细观察之后可以这样来合并：
a[1] = b[2] + b[0] ;
for (i =2; i < len; i++) {
a[i] = b[i+1]+b[i-1];
b[i-1] = a[i] + a[i-2];
}
b[len-1] = a[len] + a[len-2];
|
除了上面介绍的循环优化技术之外，还有一种称为缓存块（cache blocking）的技术，主要用在访问那些比较大的没有办法一次容纳到缓存中的数组时用到，其基本思想是把每次只取大数组的一块数据放入缓存中，处理完之后再用新的数据块代替继续处理。
循环分支（Loop unswitching）技术把在循环体中的分支提取到循环外面，这样循环体没有分支，有助于进行更进一步的优化，比如自动矢量化等。
for (i=1;i<=10000;i++) {
if (a<2) {
b=b*c;
}
else {
b=b*bˆ2-c;
}
}
|
优化后的代码为：
if (a<2) {
for (i=1;i<=10000;i++)
b=b*c;
}
else {
for (i=1;i<=10000;i++)
b=b*bˆ2-c;
}
|
