程序优化

C代码中有许多比较通用的可以优化的地方。其中大部分优化方式在其他语言中也是有效的。

减弱强度

使用指令个数更少的代码或者需要总的时钟周期更少的代码代替原代码，比如位移动代替乘法除法等。

使用局部变量(代码移动)

表达式

如果某些表达式被重复计算了，可以提前保存。一般来说O1以上会自动开启此优化。

// 1.c
int t(int i){
    int x=3+i*i;
    int y=4+i*i;
    int z=5+i*i;
    int xx=x/y+y/z+z;
    return xx;
}

用-S生成汇编，-Ox指定优化等级：

gcc 1.c -S

使用上面的命令结果为：

t:
	pushq	%rbp
	.seh_pushreg	%rbp
	movq	%rsp, %rbp
	.seh_setframe	%rbp, 0
	subq	$16, %rsp
	.seh_stackalloc	16
	.seh_endprologue
	movl	%ecx, 16(%rbp)
	movl	16(%rbp), %eax
	imull	16(%rbp), %eax
	addl	$3, %eax
	movl	%eax, -4(%rbp)
	movl	16(%rbp), %eax
	imull	16(%rbp), %eax
	addl	$4, %eax
	movl	%eax, -8(%rbp)
	movl	16(%rbp), %eax
	imull	16(%rbp), %eax
	addl	$5, %eax
	movl	%eax, -12(%rbp)
	movl	-4(%rbp), %eax
	cltd
	idivl	-8(%rbp)
	movl	%eax, %ecx
	movl	-8(%rbp), %eax
	cltd
	idivl	-12(%rbp)
	leal	(%rcx,%rax), %edx
	movl	-12(%rbp), %eax
	addl	%edx, %eax
	movl	%eax, -16(%rbp)
	movl	-16(%rbp), %eax
	addq	$16, %rsp
	popq	%rbp
	ret
	.seh_endproc
	.ident	"GCC: (x86_64-posix-seh-rev0, Built by MinGW-W64 project) 8.1.0"

gcc 1.c -S -O1

使用上面的命令结果为：

	.file	"1.c"
	.text
	.globl	t
	.def	t;	.scl	2;	.type	32;	.endef
	.seh_proc	t
t:
	.seh_endprologue
	imull	%ecx, %ecx
	leal	4(%rcx), %r8d
	leal	5(%rcx), %r9d
	addl	$3, %ecx
	movl	%ecx, %eax
	cltd
	idivl	%r8d
	movl	%eax, %ecx
	movl	%r8d, %eax
	cltd
	idivl	%r9d
	addl	%ecx, %eax
	addl	%r9d, %eax
	ret
	.seh_endproc
	.ident	"GCC: (x86_64-posix-seh-rev0, Built by MinGW-W64 project) 8.1.0"

可见gcc是会主动优化该类型的冗余代码的。

函数调用

循环等过程中重复调用函数会花非常多的不必要的时间。因为编译器对此函数一无所知，如果存在副作用则优化后程序的结果会与优化前不一样，所以会避免对其使用优化。应主动使用局部变量来保存此重复调用的函数。

内存别名

如果赋值时使用了内存中的值，可以换成用局部变量保存（比如循环中保存累加的值），这样可以避免编译器无法判断此段代码是否使用了内存别名（比如对数组求和但是保存在数组内部）。因为优化后会得到不一样的结果而不进行优化。下面是这个例子

void sum_rows1(double *a, double *b, long n)
{
    long i, j;
    for (i = 0; i < n; i++)
    {
        b[i] = 0;
        for (j = 0; j < n; j++)
            b[i] += a[i*n + j];
    }
}

可以用局部变量代替b[i]。

void sum_rows2(double *a, double *b, long n)
{
    long i, j;
    for (i = 0; i < n; i++)
    {
        double val = 0;
        for (j = 0; j < n; j++)
            val += a[i*n + j];
        b[i] = val;
    }
}

针对机器对代码进行调整

计算重排

此部分针对于流水线CPU，对部分代码进行重排可以更高效利用ALU。 对于表达式来说，其中如果表达式右边包含多个乘法，则可以使用多个单次乘法及赋值代替一次全部乘起来。这样会避免内存的依赖，因此流水线处理器可以保证每个乘法同时处于执行的不同阶段，而不会需要等待上一条指令写回后再执行下一条。

下面的代码里，将一个数组中各个元素乘起来，用x保存。这里用一次乘两个元素的方式减少了一半赋值语句。

void unroll2a_combine(vec__ptr v, data_t *dest)
{
    long length = vec_length(v);
    long limit = length - 1;
    data_t *d = get_vec_start(v);
    data_t x = IDENT;
    long i; 
    /* Combine 2 elements at a time */
    for (i = 0; i < limit; i += 2)
    {
        x = (x OP d[i])OP d[i + l];
    }
    /* Finish any remaining elements */ 
    for (; i < length; i++)
    {
        x = x OP d[i];
    }
    *dest = x;
}

但是仍然有优化空间，因为这里每次都乘到x上，需要等x更新完才能继续下一次计算，流水线上其他元件不能不闲着。将乘数全部换成d中的元素，则每次执行时都没有互相的内存依赖（d[0],d[1]一组，d[2],d[3]一组，互不依赖）。

void unroll2a_combine(vec__ptr v, data_t *dest)
{
    long length = vec_length(v);
    long limit = length - 1;
    data_t *d = get_vec_start(v);
    data_t x = IDENT;
    long i; 
    /* Combine 2 elements at a time */
    for (i = 0; i < limit; i += 2)
    {
        x = x OP (d[i] OP d[i + l]);
    }
    /* Finish any remaining elements */ 
    for (; i < length; i++)
    {
        x = x OP d[i];
    }
    *dest = x;
}

这样可能存在的问题是，浮点数乘法不一定满足结合律，但是对于目前我们常使用的位数（32，64）即使存在误差，大部分时间是可以接受的。这个优化方法叫做循环展开（loop unrolling）。

避免无法预测的分支

条件移动可以在流水线中进行，条件跳转则如果遇到不可预测的分支可能出现预测（此时会执行预测结果开始的指令，但是不修改寄存器和内存）失败而直接回到分支前重新执行。

条件移动的例子是：

long f(long x,long y){
    long res;
    if(x>y)res=x-y;
    else res=y-x;
    return res;
}

汇编为：

	.file	"1.c"
	.text
	.globl	f
	.def	f;	.scl	2;	.type	32;	.endef
	.seh_proc	f
f:
	.seh_endprologue
	movl	%ecx, %r8d
	subl	%edx, %r8d
	movl	%edx, %eax
	subl	%ecx, %eax
	cmpl	%edx, %ecx
	cmovg	%r8d, %eax
	ret
	.seh_endproc
	.ident	"GCC: (x86_64-posix-seh-rev0, Built by MinGW-W64 project) 8.1.0"

可以看到使用了cmovg来设置返回值%eax，否的情况则跳过。

如果使用下面的命令进行编译，汇编里就会使用条件分支。

gcc 1.c -S -O1 -fno-if-conversion

	.file	"1.c"
	.text
	.globl	f
	.def	f;	.scl	2;	.type	32;	.endef
	.seh_proc	f
f:
	.seh_endprologue
	cmpl	%edx, %ecx
	jle	.L2
	movl	%ecx, %eax
	subl	%edx, %eax
.L1:
	ret
.L2:
	movl	%edx, %eax
	subl	%ecx, %eax
	jmp	.L1
	.seh_endproc
	.ident	"GCC: (x86_64-posix-seh-rev0, Built by MinGW-W64 project) 8.1.0"

}

这里是题外话，一般来说需要避免条件移动，有两个原因： 1. 他会将两个分支都进行计算，但是实际上两个分支的内容有多复杂是不知道的，有可能会额外执行非常多无意义的指令，而且有可能某分支的内容对于当前条件是非法的（比如对空指针进行解引用）。对GCC一般来说只有两个分支都是非常简单的语句才会使用。 2. 不必要执行的分支可能存在副作用。

这部分我的理解是，不要写太多奇怪的条件语句，尤其是循环内部，这样会使得预测结果错误比较频繁。比如如果只是最后退出循环的时候条件预测错了一次，开销相对整体的多次循环并不算很大。