第十三號艦隊
0%

Optimizing C++ Code : Dead Code Elimination in Different Compilers

Posted on Edited on In , , ,

同樣來自VC Blog的靈感，來測試一下三大編譯器的能耐。
如果對這技術有興趣的話，可以操考Wiki跟Code Optimizations:
Partial Dead Code Elimination和Dead Code Elimination這兩份PDF。
測試程式如下

1
2
3
4
5
6
int main()
{
	long long s = 0;
	for (long long i = 1; i <= 1000000000; i++) s += i;
	return 0;
}

Visual C++的結果

未開最佳化，如同VC Blog列的那樣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
	mov	QWORD PTR i$1[rsp], 1
	jmp	SHORT $LN3@main
$LN2@main:
	mov	rax, QWORD PTR i$1[rsp]
	inc	rax
	mov	QWORD PTR i$1[rsp], rax
$LN3@main:
	cmp	QWORD PTR i$1[rsp], 1000000000		; 3b9aca00H
	jg	SHORT $LN1@main
	mov	rax, QWORD PTR i$1[rsp]
	mov	rcx, QWORD PTR s$[rsp]
	add	rcx, rax
	mov	rax, rcx
	mov	QWORD PTR s$[rsp], rax
	jmp	SHORT $LN2@main
$LN1@main:

最佳化版本，結果相同，什麼都沒有

1
// Nothing

GCC的結果

未開最佳化

1
2
3
4
5
6
7
8
9
10
11
	movq	$1, -8(%rbp)
	jmp	.L2
.L3:
	movq	-8(%rbp), %rax
	addq	%rax, -16(%rbp)
	addq	$1, -8(%rbp)
.L2:
	cmpq	$1000000000, -8(%rbp)
	setle	%al
	testb	%al, %al
	jne	.L3

如同Visual C++的結果一樣，照實執行。
最佳化版

1
// Nothing

跟Visual C++的結果相同，完全沒有程式碼，證明了這段程式碼一樣被偵測到而被捨棄。根據這篇的說明，在-O2的設定終究有暗示Dead Code Elimination的使用。

Clang的結果

未開最佳化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
	movq	$1, -24(%rbp)
.LBB0_1:                                # %for.cond
                                        # =>This Inner Loop Header: Depth=1
	cmpq	$1000000000, -24(%rbp)  # imm = 0x3B9ACA00
	jg	.LBB0_4
# BB#2:                                 # %for.body
                                        #   in Loop: Header=BB0_1 Depth=1
	movq	-24(%rbp), %rax
	movq	-16(%rbp), %rcx
	addq	%rax, %rcx
	movq	%rcx, -16(%rbp)
# BB#3:                                 # %for.inc
                                        #   in Loop: Header=BB0_1 Depth=1
	movq	-24(%rbp), %rax
	addq	$1, %rax
	movq	%rax, -24(%rbp)
	jmp	.LBB0_1
.LBB0_4:                                # %for.end

可以看出三大編譯器對做同一件事，產生的程式碼風格相差甚大。
最佳化版

1
// Nothing

大家都能偵測到Dead Code Elimination。

同場加映

在VC Blog的Option 2，在原來的程式碼後面，加上printf，使得Dead Code Elimination失效。
VC的結果如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
       xor    edx, edx
       mov    eax, 1 
       mov    ecx, edx
       mov    r8d, edx
       mov    r9d, edx
       npad   13
$LL3@main:
       inc    r9
       add    r8, 2
       add    rcx, 3
       add    r9, rax                           ;; r9  = 2  8 18 32 50 ...
       add    r8, rax                           ;; r8  = 3 10 21 36 55 ...
       add    rcx, rax                          ;; rcx = 4 12 24 40 60 ...
       add    rdx, rax                          ;; rdx = 1  6 15 28 45 ...
       add    rax, 4                            ;; rax = 1  5  9 13 17 ...
       cmp    rax, 1000000000                   ;; i <= 1000000000 ?
       jle    SHORT $LL3@main                   ;; yes, so loop back

使用Loop unwinding的技巧加速。
不過GCC跟Clang更勝一籌，直接印答案了。

1
movabsq	$500000000500000000, %rsi # imm = 0x6F05B59F17F6500

如果把原先的程式碼改成這樣

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>
int main()
{
	long long s = 0;
	long long count;
	scanf("%lld", &count);
	for (long long i = 1; i <= count; i++) s += i;
	printf("%llu\n", s);
	return 0;
}

Visual C++跟GCC的產生結果就比較像了，VC原先的Loop Unwinding被拿掉了。

1
2
3
4
5
6
7
8
9
	movl	$1, %eax
	testq	%rdx, %rdx
	jle	.L3
.L6:
	addq	%rax, %rsi
	addq	$1, %rax
	cmpq	%rdx, %rax
	jle	.L6
.L3:

而Clang會根據x64指令集作最佳化一

1
2
3
4
5
6
7
8
9
10
11
12
	movq	8(%rsp), %rax
	testq	%rax, %rax
	jle	.LBB0_2
# BB#1:                                 # %for.body.lr.ph
	movl	$1, %ecx
	cmovgq	%rax, %rcx
	leaq	-1(%rcx), %rax
	leaq	-2(%rcx), %rdx
	mulq	%rdx
	shldq	$63, %rax, %rdx
	leaq	-1(%rdx,%rcx,2), %rbx
.LBB0_2:                                # %for.end