2004年作成
変数を増やした場合、使用するレジスタが少なくなる
以下のようなサンプルプログラムを作って使用するレジスタ数を比較してみました。
プログラムはperlスクリプトで自動生成されます。
% perl t22.pl <変数の数>
struct s {
int a;
int b;
};
struct s a000;
struct s a001;
struct s a002;
:
int f()
{
int a = 0;
int b = 0;
a += (a000.a ^ a001.b);
a += (a001.a ^ a002.b);
:
a += (a145.a ^ a146.b);
a += (a146.a ^ a000.b);
b += (a000.b ^ a146.a);
b += (a146.b ^ a145.a);
:
b += (a002.b ^ a001.a);
b += (a001.b ^ a000.a);
return a + b;
}
このプログラムを-O3でコンパイルして使用するレジスタ数を調査しました。
結果は次のようになります。
変数の数
レジスタの数
80
87
90
97
100
107
110
117
120
127
130
127
140
127
147
127
148
123
149
116
150
113
160
86
170
66
180
55
190
43
200
44
変数の数が 147 までは使用できるレジスタを最大限に使うのですが、それからはレ
ジスタを使用しなくなって最終的に 43,44個に落ち着きます。
命令の順番を代えることによってサイクル数を少なくする
1 sub(char *a, char *b, char *c, int n)
2 {
3 int i;
4 5 for (i = 0; i < n; i++) {
6 c[i] = a[i] + b[i];
7 }
8 }
このソースを-O3でコンパイルすると以下のようになります。
6 sub:
7 ori $11,$3,0
8 cgti $3,$6,0
9 ori $12,$6,0
10 ori $10,$4,0
11 ori $9,$5,0
12 hbra .L9,.L6
13 lnop
14 nop $127
15 il $8,0
16 brz $3,.L8
17 .L6:
18 a $4,$11,$8 ; FX even 2
19 lqx $5,$10,$8 ; LS odd 5
20 a $14,$10,$8 ; FX even 2
21 lqx $2,$11,$8 ; LS odd 5
22 ai $6,$4,13 ; FX even 2
23 lqx $13,$9,$8 ; LS odd 5
24 ai $3,$14,13 ; FX even 2
25 cbx $14,$9,$8 ; SH odd 4
26 rotqby $7,$2,$6 ; SH odd 4
27 rotqby $6,$5,$3 ; SH odd 4
28 ah $5,$7,$6
29 shufb $4,$5,$13,$14
30 stqx $4,$9,$8
31 ai $8,$8,1
32 cgt $3,$12,$8
33 .L9:
34 brnz $3,.L6
35 .L8:
(18,19),(20,21),(22,23),(24,25)がそれぞれ同じサイクルで実行されます。
26 で参照している $2 の準備のために 3 サイクル (22,24 で 2 サイクルですが LS では 5 サイクル必要なため) 無駄になります。
19 行目と 21 行目を交換するか、26,27 行目を交換 (この場合、レジスタ $6 の置き換えが必要) をすれば、無駄なサイクルは 2 サイクルに減ります。
上記のような命令順序の調整でサイクル数を削減することが可能です。
整数演算の順序
1 int foo2(int a, int b, int c, int d)
2 {
3 return a + b + c + d;
4 5 }
上記の関数を-O3でコンパイルすると
1 foo2:
2 a $7,$3,$4
3 a $2,$7,$5
4 a $3,$2,$6
5 bi $lr
のようになります。
これは 2 行目の結果を 3 行目で、3 行目の結果を 4 行目で使用するため、二つの無駄なサイクルが発生します。
ここでは (((a+b)+c)+d) の順序で計算していますが、整数の加算・乗算の場合、順序は関係無いので、((a+b)+(c+d)) のように計算しても問題ありません。
この変更によって無駄なサイクルを減らすことが出来ます。(以下のパターンだと無駄なサイクル数が 1 になります)
1 foo2:
2 a $7,$3,$4
3 a $2,$5,$6
4 a $3,$2,$7
5 bi $lr
乗算の場合は加算よりも効果があります。
1 long foo1(long a, long b, long c, long d)
2 {
3 return a * b * c * d;
4 }
上記の関数をコンパイルした場合：
1 foo1:
2 mpyh $14,$3,$4
3 mpyh $7,$4,$3
4 mpyu $13,$3,$4
5 a $12,$14,$7
6 a $11,$12,$13
7 hbr .L2,$lr
8 mpyh $10,$11,$5
9 nop $127
10 mpyh $2,$5,$11
11 mpyu $9,$11,$5
12 a $5,$10,$2
13 a $4,$5,$9
14 mpyh $3,$6,$4
15 mpyh $8,$4,$6
16 mpyu $7,$4,$6
17 a $5,$8,$3
18 a $3,$5,$7
変更後
1 foo1:
2 mpyh $14,$3,$4
3 mpyh $7,$4,$3
4 mpyu $13,$3,$4
5 mpyh $8,$5,$6
6 mpyh $9,$6,$5
7 mpyu $10,$5,$6
8 hbr .L2,$lr
9 a $12,$14,$7
10 a $15,$8,$9
11 a $11,$12,$13
12 a $16,$15,$10
13 mpyh $13,$11,$16
14 mpyh $14,$16,$11
15 mpyu $15,$11,$16
16 a $5,$13,$14
17 a $3,$5,$15
計算回数は代わりませんが、乗算だけを詰めることで無駄なサイクルがなくなります。
この場合、9サイクル早くなりました。括弧で順序付けすることでも最適化されます。
減算、除算等にも使用できます。
無駄な型変換
1 char foo4(char a, char b, char c, char d)
2 {
3 return a + b + c + d;
4 }
上記のソースを-O3でコンパイルすると以下のアセンブラが生成されます。
1 foo4:
2 nop $127
3 hbr .L6,$lr
4 ah $7,$3,$4
5 ah $4,$5,$7
6 ah $2,$6,$4
7 xsbh $3,$2
8 xshw $2,$3
9 ori $3,$2,0
10 nop $127
11 nop $127
12 nop $127
13 .L6:
14 bi $lr
7行目でhalf wordからbyteへの型変換をやっていますので、8行目の処理が無駄です。
除算
定数がある場合。
1 foo(int a)
2 {
3 return a / 3;
4 }
これを-O3でコンパイルすると以下のようになります。
定数部分の最適化がされていません。
1 .file "c.c"
2 .text
3 .align 3
4 .global foo
5 .type foo, @function
6 foo:
7 il $2,3
8 lnop
9 heqi $2,0 不必要
10 hbrr 3f,1f
11 sfi $10,$3,0
12 sfi $11,$2,0
13 cgti $12,$3,-1
14 cgti $13,$2,-1 事前計算可能
15 selb $10,$10,$3,$12
16 selb $11,$11,$2,$13 事前計算可能
17 xor $13,$12,$13
18 clz $9,$11 事前計算可能
19 clz $6,$10
20 il $7,1
21 sf $9,$6,$9
22 ori $4,$10,0
23 shl $6,$11,$9
24 shl $7,$7,$9
25 il $5,0
26 1: clgt $8,$6,$4
27 sf $9,$6,$4
28 or $14,$5,$7
29 rotmi $7,$7,-1
30 rotmi $6,$6,-1
31 selb $4,$9,$4,$8
32 selb $5,$14,$5,$8
33 3: brnz $7,1b
34 2: sfi $10,$4,0
35 sfi $11,$5,0
36 selb $4,$10,$4,$12
37 selb $5,$5,$11,$13
38 ori $3,$5,0
39 nop $127
40 bi $lr
switch文
switch 文は case 毎にコードブロックを作成しテーブルを使ってそこに間接ジャンプするようになっています。
以下の特殊な場合、処理自体をまとめることで、無駄なジャンプを削ることが可能です。
1. 同じ変数への定数代入が多い。
2. 定数のリターン処理が多い。
1 foo(unsigned short a)
2 {
3 switch(a) {
4 case 0: return 1;
5 case 1: return 2;
6 case 2: return 3;
7 case 3: return 4;
8 case 4: return 5;
9 default: return 0;
10 }
11 }
これをコンパイルすると以下のようになります。
6 foo:
7 ila $2,65535
8 il $5,0
9 and $4,$3,$2
10 clgti $3,$4,4
11 nop $127
12 brnz $3,.L1
13 shli $7,$4,2
14 ila $3,.L9
15 a $6,$7,$3
16 lqd $5,0($6)
17 rotqby $4,$5,$6
18 bi $4
19 .align 2
20 .align 2
21 .L9:
22 .word .L3
23 .word .L4
24 .word .L5
25 .word .L6
26 .word .L7
27 .L3:
28 il $5,1
29 br .L1
30 .L4:
31 il $5,2
32 br .L1
33 .L5:
34 il $5,3
35 br .L1
36 .L6:
37 il $5,4
38 br .L1
39 .L7:
40 il $5,5
41 lnop
42 .L1:
43 ori $3,$5,0
44 bi $lr
この場合、case ブロックへのジャンプと case ブロックから脱出するためのジャンプの 2 回ジャンプが存在しますが、以下のようにすると 1 回ですみます。
6 foo:
7 ila $2,65535
8 il $5,0
9 and $4,$3,$2
10 clgti $3,$4,4
11 nop $127
12 brnz $3,.L1
13 shli $7,$4,2
14 ila $3,.L9
15 a $6,$7,$3
16 lqd $5,0($6)
17 .L1:
18 ori $3,$5,0
19 bi $lr
20 .align 2
21 .align 2
22 .L9:
23 .word 1
24 .word 2
25 .word 3
26 .word 4
27 .word 5
無効命令が削除されない
1 foo(int a)
2 {
3 if (a > 0) {
4 return 0;
5 }
6 if (a > 100) {
7 return 100;
8 }
9 return -1;
10 }
上記の命令では 7 行目の処理が行なわれることはありませんが、アセンブラファイルにはその処理が入っています。
6 foo:
7 cgti $9,$3,100
8 hbr .L4,$lr
9 cgti $5,$3,0
10 nop $127
11 ceqi $8,$9,0
12 ceqi $2,$5,0
13 ori $7,$8,100
14 il $6,0
15 selb $5,$6,$7,$2
16 ori $3,$5,0
17 nop $127
18 .L4:
19 bi $lr
マージ処理
条件分岐でまとめられる処理を SELB で一括処理しようとしていますが、しきれていません。
1 foo(int a, int b, int c)
2 {
3 if (a > b) {
4 a++;
5 b++;
6 c++;
7 } else {
8 a++;
9 b--;
10 c++;
11 }
12 return a + b + c;
13 }
上記のソースでは 4 行目と 8 行目、6 行目と 11 行目がそれぞれ同じものになっています。
これをコンパイルすると、以下のようになります。
6 foo:
7 cgt $13,$3,$4
8 hbr .L4,$lr
9 ori $2,$5,0
10 nop $127
11 ai $7,$3,1
12 ceqi $5,$13,0
13 ai $10,$4,-1
14 ai $14,$4,1
15 selb $12,$7,$7,$5
16 selb $4,$14,$10,$5
17 ai $11,$2,1
18 ceqi $8,$13,0
19 a $5,$12,$4
20 selb $7,$11,$11,$8
21 a $3,$5,$7
22 .L4:
23 bi $lr
selb を使ってまとめて処理しようとしていますが、15 行目と 20 行目の処理でもselb を使用しています。この部分はコピー処理と等価です。
