alphaとは、Digitalが開発したスーパースカラ構造をもつRISCチップです。
linux
は、UnixクローンなFreeOSでLinus Torvalds氏が中心となって
つくられました。他のalphaチップ上で動作するFreeOSとしては
NetBSD,OpenBSDがあります。
gccとはGNU の Cコンパイラです。
ソースが公開されているという特徴があり、
コンパイラを直接いじって遊ぶことができます。(このページのようなことができる
のも GNU があればこそです:-)
この Web page の内容は１９９８年当時のものです。
現在更新はしていませんのでご注意ください。
ページ内目次
gcc/linux/alphaとは
RISC なので x86 と比較して命令列が読みやすいという優れた
特徴があります。
このページを読んでおけば今度RSMが来日した時に「gcc のコードを読んだこと
ある人は？」と言われても堂々と手が挙げられますね。
後藤版 linux/alpha パッケージの御紹介
後藤版 linux/alpha パッケージは、1998 9/8 を
もちまして終了しました。後藤さんご苦労さまでした。
目次に戻る
alpha は AT互換機と違ってそれぞれのマザーボードの BIOS 周りに は互換性がありません。よってそれぞれのマザーボードごとにlinux 側の の対応が必要であり、すべてのマザーボードで linux が動作する訳では ありません。alpha を購入されて linux のインストールをお考えの方は 購入前によくお調べになることをお勧めします。
egcs-1.0.1
は、かなり強力なオプティマイザを持った gcc,g77 コンパイラです。
フロー解析を基にした投機的実行など最新のコンパイラ技術を楽しむことが
できます。
egcs-1.0.1.tar.gzをダウンロードして展開し
cd egcs-1.0.1/gcc
./configure --prefix=/usr alphaev5-linux --enable-haifa
make CFLAGS="-O2";make install
でインストールできます。g77 -O2 -fsched-spec-load で、投機的実行を含む
オブジェクトを生成します。
egcs-1.0.3a が出ています、またかなり改良されているようで
SUBROUTINE DAXPY(N,DA,DX,INCX,DY,INCY)
DOUBLE PRECISION DX(1),DY(1),DA
INTEGER I,INCX,INCY,IX,IY,M,MP1,N
DO 30 I = 1,N
DY(I) = DY(I) + DA*DX(I)
30 CONTINUE
RETURN
END
という daxpy のコアの部分に対して
21164:#g77 -O4 -S -funroll-loops daxpy.f
とコンパイルすると
$L5:
ldt $f13,0($18)
ldt $f14,8($18)
ldt $f15,16($18)
ldt $f22,24($18)
ldt $f12,0($20)
ldt $f11,8($20)
ldt $f10,16($20)
ldt $f1,24($20)
addq $18,32,$18
subl $2,4,$2
mult $f23,$f13,$f13
mult $f23,$f14,$f14
mult $f23,$f15,$f15
mult $f23,$f22,$f22
addt $f12,$f13,$f12
addt $f11,$f14,$f11
addt $f10,$f15,$f10
addt $f1,$f22,$f1
stt $f12,0($20)
stt $f11,8($20)
stt $f10,16($20)
stt $f1,24($20)
addq $20,32,$20
bge $2,$L5
と文句のつけようのない命令列が生成されます(残念ながら
増分値が定数以外の場合はこうはいきませんが)
この最適化が何処でされているかを少し調べてみます。
daxpy.f.rtl: unroll 前
daxpy.f.jump: unroll 前
daxpy.f.cse: unroll 前
daxpy.f.loop: unroll 後
(insn 210 209 211 (set (reg:DI 165)
(plus:DI (reg:DI 108)
(const_int 8))) -1 (nil)
(nil))
...
(insn 221 220 222 (set (reg:DF 173)
(mem/s:DF (reg:DI 165))) -1 (nil)
(nil))
...
という具合にここではいったん 仮想レジスタ 108 に 8 を加えた
アドレスを仮想レジスタ 165 に入れたあとそれを参照してロー
ドしてます
daxpy.f.cse2: unroll 後
(insn 210 209 211 (set (reg:DI 165)
(plus:DI (reg:DI 108)
(const_int 8))) 7 {adddi3} (nil)
(nil))
...
(insn 221 216 222 (set (reg:DF 173)
(mem/s:DF (plus:DI (reg:DI 108)
(const_int 8)))) 243 {movsf-1} (nil)
(nil))
上で使われていた 165 はもう参照されず、ロード命令の
オフセット領域に 8 を入れて実現されています。
daxpy.f.bp:
daxpy.f.flow:
daxpy.f.combine:
daxpy.f.regmove:
daxpy.f.sched:
daxpy.f.lreg:
daxpy.f.greg:
daxpy.f.sched2:
daxpy.f.jump2:
それでは、ソースを見て書き換え処理の場所を探してみましょう。
toplev.c:
3341 TIMEVAR (cse2_time, tem = cse_main (insns, max_reg_num (),
3342 1, cse2_dump_file));
ここいらへんで、上の書き換え処理をしているようです。
cse.c:
8175 int
8176 cse_main (f, nregs, after_loop, file)
6340 /* Simplify and foldable subexpressions in SRC. Then get the full
6341 simplified result, which may not necessarily be valid. */
6342 src_folded = fold_rtx (src, insn);
ここでやっています。
4966 case MEM:
4967 /* If we are not actually processing an insn, don't try to find th
4968 best address. Not only don't we care, but we could modify the
4969 MEM in an invalid way since we have no insn to validate against
4971 if (insn != 0)
4972 find_best_addr (insn, &XEXP (x, 0));
ここでやっています。
2659 if (validate_change (insn, loc,
2660 canon_reg (copy_rtx (best_elt->exp),
2661 NULL_RTX), 0))
2662 return;
ここでやっています。
2557 if ((GET_CODE (addr) == PLUS
2558 && GET_CODE (XEXP (addr, 0)) == REG
2559 && GET_CODE (XEXP (addr, 1)) == CONST_INT
2560 && (regno = REGNO (XEXP (addr, 0)),
2561 regno == FRAME_POINTER_REGNUM || regno == HARD_FRAME_POINTER_
2562 || regno == ARG_POINTER_REGNUM))
2563 || (GET_CODE (addr) == REG
2564 && (regno = REGNO (addr), regno == FRAME_POINTER_REGNUM
2565 || regno == HARD_FRAME_POINTER_REGNUM
2566 || regno == ARG_POINTER_REGNUM))
2567 || CONSTANT_ADDRESS_P (addr))
2568 return;
で条件のチェックをして書き換えを行っています。
こういうふうに最適化は結構狭い守備範囲なのですこし RTL が変化
しただけでうまくいかなくなる可能性があります。
もうひとつの daxpy のループも見ておきましょう。
SUBROUTINE DAXPY(N,DA,DX,INCX,DY,INCY)
DOUBLE PRECISION DX(1),DY(1),DA
INTEGER I,INCX,INCY,IX,IY,M,MP1,N
IX=1
IY=1
DO 30 I = 1,N
DY(IY) = DY(IY) + DA*DX(IX)
IX=IX+INCX
IY=IY+INCY
30 CONTINUE
RETURN
END
21164:~/1#g77 -O4 -S -funroll-loops daxpy.f
$L5:
ldt $f1,0($18)
mult $f12,$f1,$f1
ldt $f10,0($20)
addq $18,$4,$18
addt $f10,$f1,$f10
ldt $f11,0($18)
mult $f12,$f11,$f11
stt $f10,0($20)
addq $20,$2,$20
ldt $f1,0($20)
addt $f1,$f11,$f1
addq $18,$4,$18
subl $3,2,$3
stt $f1,0($20)
addq $20,$2,$20
bge $3,$L5
DO 30 I = 1,N
DY(IY) = DY(IY) + DA*DX(IX)
IX=IX+INCX
IY=IY+INCY
30 CONTINUE
の IY が 0 かもしれないので DY(IY) の定義と
次の繰り返しの引用が入れ換えられないので窮屈
な命令列になっています。
また前のプログラムに戻りますが
stt $f12,0($20)
stt $f11,8($20)
stt $f10,16($20)
stt $f1,24($20)
addq $20,32,$20
bge $2,$L5
の所が
addq $20,32,$20
stt $f12,-32($20)
stt $f11,-24($20)
stt $f10,-16($20)
stt $f1,-8($20)
bge $2,$L5
とでた方が気持いいですね。
「gcc は DEC FORTRAN に比べて倍位遅いらしい」という 噂が世間を騒がせているようなので現状をまとめます、確かにプログラム によって倍位遅い場合も あります。alpha はコンパイラにできることはコンパイラにやってもらう 設計になっているのでコンパイラの負担が高くまだ gcc (含む egcs)は 完全に DEC FORTRAN レベルにはなっていません。(インライン展開、 ソフトウエアパイプライニングがまだ、ループの構造も cache 最適化 したいところです)ただある程度アーキテクチャ を理解している人間がコードを書く場合には満足の行く性能が得られる筈です。 また、 Linux/Alpha-JP Mailing Listで後藤さんが公開している Stataboware の 最新版は、数値関数に関して後藤さんが精力的にチューニングを押し進めて DEC 版に遜色ない性能を得ています。コンパイラ本体に関しては egcs その ものです。(安定した組合せを探す努力をされています)
「egcs-1.0.3a について」で見たように egcs には、参照されない代入を消去する機能があり ます何処にあるか探してみましょう。
SUBROUTINE DAXPY(N,DA,DX,INCX,DY,INCY)
DOUBLE PRECISION DX(1),DY(1),DA
INTEGER I,INCX,INCY,IX,IY,M,MP1,N
DO 30 I = 1,N
DY(I) = DY(I) + DA*DX(I)
30 CONTINUE
RETURN
END
という daxpy のコアの部分で
21164:#g77 -da -O4 -S -funroll-loops daxpy.f
とコンパイルして調べます
daxpy.f.loop: unroll 後
(insn 210 209 211 (set (reg:DI 165)
(plus:DI (reg:DI 108)
(const_int 8))) -1 (nil)
(nil))
...
(insn 221 220 222 (set (reg:DF 173)
(mem/s:DF (reg:DI 165))) -1 (nil)
(nil))
...
という具合にここではいったん 仮想レジスタ 108 に 8 を加えた
アドレスを仮想レジスタ 165 に入れたあとそれを参照してロー
ドしてます
daxpy.f.cse2: unroll 後
(insn 210 209 211 (set (reg:DI 165)
(plus:DI (reg:DI 108)
(const_int 8))) 7 {adddi3} (nil)
(nil))
...
(insn 221 216 222 (set (reg:DF 173)
(mem/s:DF (plus:DI (reg:DI 108)
(const_int 8)))) 243 {movsf-1} (nil)
(nil))
上で使われていた 165 はもう参照されず、ロード命令の
オフセット領域に 8 を入れて実現されています。
daxpy.f.bp:
daxpy.f.flow:
ここでは、もう 165 に対する RTL 式はない。
それでは、ソースを見て書き換え処理の場所を探してみましょう。
toplev.c:
3420 /* Do control and data flow analysis,
3421 and write some of the results to dump file. */
3422
3423 TIMEVAR (flow_time, flow_analysis (insns, max_reg_num (),
3424 flow_dump_file));
ここいらへんで、書き換え処理をしているようです。
flow.c:
276 void
277 flow_analysis (f, nregs, file)
278 rtx f;
279 int nregs;
280 FILE *file;
281 {
958 static void
959 life_analysis (f, nregs)
960 rtx f;
961 int nregs;
962 {
1306 for (i = 0; i < n_basic_blocks; i++)
1307 {
1308 propagate_block (basic_block_live_at_end[i],
1309 basic_block_head[i], basic_block_end[i], 1,
1310 (regset) 0, i);
1447 static void
1448 propagate_block (old, first, last, final, significant, bnum)
1561 /* If an instruction consists of just dead store(s) on final p
1562 "delete" it by turning it into a NOTE of type NOTE_INSN_DEL
1563 We could really delete it with delete_insn, but that
1564 can cause trouble for first or last insn in a basic block.
1565 if (final && insn_is_dead)
1566 {
1568 PUT_CODE (insn, NOTE);
1569 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1570 NOTE_SOURCE_FILE (insn) = 0;
ここで delete されている。
1434 static void
1435 propagate_block (old, first, last, final, significant, bnum)
1436 register regset old;
1437 rtx first;
1438 rtx last;
1439 int final;
1440 regset significant;
1441 int bnum;
1442 {
1443 register rtx insn;
1444 rtx prev;
1445 regset live;
1446 regset dead;
1452 register int *regs_sometimes_live;
1453 int sometimes_max = 0;
1456 regset maxlive;
1461 loop_depth = basic_block_loop_depth[bnum];
1463 dead = ALLOCA_REG_SET ();
1464 live = ALLOCA_REG_SET ();
bitmap.h:
/* Allocate a bitmap with alloca. */
#define BITMAP_ALLOCA() \
bitmap_initialize ((bitmap) alloca (sizeof (bitmap_head)))
bitmap.c:
/* Initialize a bitmap header. */
bitmap
bitmap_initialize (head)
bitmap head;
{
head->first = head->current = 0;
return head;
}
1466 cc0_live = 0;
1467 last_mem_set = 0;
1472 while (NEXT_INSN (last) != 0 && GET_CODE (NEXT_INSN (last)) == NOTE)
1473 {
1474 /* Look for loop boundaries, we are going forward here. */
1475 last = NEXT_INSN (last);
1476 if (NOTE_LINE_NUMBER (last) == NOTE_INSN_LOOP_BEG)
1477 loop_depth++;
rtl.h:#define NOTE_INSN_LOOP_BEG -4
1478 else if (NOTE_LINE_NUMBER (last) == NOTE_INSN_LOOP_END)
1479 loop_depth--;
1480 }
1482 if (final)
1483 {
1484 register int i;
1486 num_scratch = 0;
1487 maxlive = ALLOCA_REG_SET ();
1488 COPY_REG_SET (maxlive, old);
1489 regs_sometimes_live = (int *) alloca (max_regno * sizeof (int));
1494 EXECUTE_IF_SET_IN_REG_SET (old, 0, i,
1495 {
1496 REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBA
1497 regs_sometimes_live[sometimes_max] =
1498 sometimes_max++;
1499 });
#define EXECUTE_IF_SET_IN_REG_SET(REGSET, MIN, REGNUM, CODE) \
EXECUTE_IF_SET_IN_BITMAP (REGSET, MIN, REGNUM, CODE)
bitmap.h:
#define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, CODE) \
do { \
bitmap_element *ptr_ = (BITMAP)->first; \
unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \
unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT); \
unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT)) \
% BITMAP_ELEMENT_WORDS); \
/* Find the block the minimum bit is in. */ \
while (ptr_ != 0 && ptr_->indx < indx_) \
ptr_ = ptr_->next; \
if (ptr_ != 0 && ptr_->indx != indx_) \
{ \
bit_num_ = 0; \
word_num_ = 0; \
} \
for (; ptr_ != 0; ptr_ = ptr_->next) \
{
for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \
{ \
unsigned HOST_WIDE_INT word_ = ptr_->bits[word_num_]; \
if (word_ != 0) \
{ \
for (; bit_num_ HOST_BITS_PER_WIDE_INT; bit_num_++) \
{ \
unsigned HOST_WIDE_INT mask_ \
= ((unsigned HOST_WIDE_INT) 1) << bit_num_; \
if ((word_ & mask_) != 0) \
{ \
word_ &= ~ mask_; \
(BITNUM) = (ptr_->indx * BITMAP_ELEMENT_ALL_BITS \
+ word_num_ * HOST_BITS_PER_WIDE_INT \
+ bit_num_); \
CODE; \
if (word_ == 0) \
break; \
}
} \
} \
bit_num_ = 0; \
} \
word_num_ = 0; \
} \
} while (0)
1500 }
1502 /* Scan the block an insn at a time from end to beginning. */
1504 for (insn = last; ; insn = prev)
1505 {
1506 prev = PREV_INSN (insn);
1508 if (GET_CODE (insn) == NOTE)
1509 {
1510 /* Look for loop boundaries, remembering that we are going
1511 backwards. */
1512 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
1513 loop_depth++;
1514 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1515 loop_depth--;
1517 /* If we have LOOP_DEPTH == 0, there has been a bookkeeping er
1518 Abort now rather than setting register status incorrectly.
1519 if (loop_depth == 0)
1520 abort ();
1522 /* If this is a call to `setjmp' et al,
1523 warn if any non-volatile datum is live. */
1525 if (final && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
1526 IOR_REG_SET (regs_live_at_setjmp, old);
1527 }
1536 else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1537 {
1538 register int i;
1539 rtx note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
1540 int insn_is_dead
1541 = (insn_dead_p (PATTERN (insn), old, 0)
1542 /* Don't delete something that refers to volatile storage
1543 && ! INSN_VOLATILE (insn)); /* 揮発性 */
### 割り込み開始 ###
daxpy.f.flow には
Register 108 used 7 times across 13 insns; dies in 0 places; pointer.
のような所があるこれは仮想レジスタの参照回数を示しているようで
flow.c:
2926 fprintf (file, "\nRegister %d used %d times across %d insns",
2927 i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
で出力されている。この値は
flow.c:
REG_N_REFS (regno) += loop_depth;
と更新されているようだ。
### 割り込み終了 ###
flow.c:
static int
insn_dead_p (x, needed, call_ok)
rtx x;
regset needed;
int call_ok;
{
register RTX_CODE code = GET_CODE (x);
/* If setting something that's a reg or part of one,
see if that register's altered value will be live. */
if (code == SET)
{
register rtx r = SET_DEST (x);
###割り込み###
ここで
if (filefile)
fprintf (filefile, "x=(%lx) SET_DEST (x)=(%lx) SET_SRC (x)=(%lx) \n",x,S
とダンプさせると
daxpy.f.flow:
x=(1204b0f60) SET_DEST (x)=(1204b0f38) SET_SRC (x)=(1204b0f48)
set の RTL reg の RTL plus の RTL
daxpy.f.loop:
(1204b0f78 1b) (insn 210 209 211 (1204b0f60 29) (set (1204b0f38 34) (reg:DI 1
(1204b0f48 41) (plus:DI (1204ac380 34) (reg:DI 108)
(120477950 2f) (const_int 8))) -1 (nil)
(nil))
となる
###割り込み終り###
/* A SET that is a subroutine call cannot be dead. */
if (! call_ok && GET_CODE (SET_SRC (x)) == CALL)
return 0;
if (GET_CODE (r) == MEM && last_mem_set && ! MEM_VOLATILE_P (r)
&& rtx_equal_p (r, last_mem_set))
return 1;
while (GET_CODE (r) == SUBREG
|| GET_CODE (r) == STRICT_LOW_PART
|| GET_CODE (r) == ZERO_EXTRACT
|| GET_CODE (r) == SIGN_EXTRACT)
r = SUBREG_REG (r);
if (GET_CODE (r) == REG)
{
register int regno = REGNO (r);
/* Don't delete insns to set global regs. */
if ((regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
/* Make sure insns to set frame pointer aren't deleted. */
|| regno == FRAME_POINTER_REGNUM
|| REGNO_REG_SET_P (needed, regno))
どうもこの条件がなりたつかどうかで delete を免れている RTL が
多いようだ。
### 割り込み ###
basic-block.h:#define REGNO_REG_SET_P(TO, REG) bitmap_bit_p (TO, REG)
bitmap.c:
int
bitmap_bit_p (head, bit)
bitmap head;
int bit;
{
bitmap_element *ptr;
unsigned bit_num;
unsigned word_num;
ptr = bitmap_find_bit (head, bit);
if (ptr == 0) return 0;
bit_num = bit % (unsigned) HOST_BITS_PER_WIDE_INT;
word_num = ((bit / (unsigned) HOST_BITS_PER_WIDE_INT) % BITMAP_ELEMENT_WORDS);
return (ptr->bits[word_num] & (((unsigned HOST_WIDE_INT) 1) << bit_num)) != 0;
}
### 割り込み終了 ###
needed というのがこの時点でのレジスタの生死情報を持ったテーブルのようで
その情報で決定する。このテーブルは flow.c の中で定義している。
return 0;
/* If this is a hard register, verify that subsequent words are
not needed. */
if (regno < FIRST_PSEUDO_REGISTER)
config/alpha/alpha.h:#define FIRST_PSEUDO_REGISTER 64
{
int n = HARD_REGNO_NREGS (regno, GET_MODE (r));
while (--n > 0)
if (REGNO_REG_SET_P (needed, regno+n))
return 0;
}
return 1;
ここへ制御が渡って delete となっているようだ。(返却値 1 が delete の印)
}
}
/* If performing several activities,
insn is dead if each activity is individually dead.
Also, CLOBBERs and USEs can be ignored; a CLOBBER or USE
that's inside a PARALLEL doesn't make the insn worth keeping. */
else if (code == PARALLEL)
{
register int i = XVECLEN (x, 0);
for (i--; i >= 0; i--)
{
rtx elt = XVECEXP (x, 0, i);
if (!insn_dead_p (elt, needed, call_ok)
&& GET_CODE (elt) != CLOBBER
&& GET_CODE (elt) != USE)
return 0;
}
return 1;
}
/* We do not check CLOBBER or USE here.
An insn consisting of just a CLOBBER or just a USE
should not be deleted. */
return 0;
}
1544 int libcall_is_dead
1545 = (insn_is_dead && note != 0
1546 && libcall_dead_p (PATTERN (insn), old, note, insn));
1547
1548 /* If an instruction consists of just dead store(s) on final p
1549 "delete" it by turning it into a NOTE of type NOTE_INSN_DEL
1550 We could really delete it with delete_insn, but that
1551 can cause trouble for first or last insn in a basic block.
1552 if (final && insn_is_dead)
1553 {
1554 PUT_CODE (insn, NOTE);
1555 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1556 NOTE_SOURCE_FILE (insn) = 0;
1557
ここで、delete されている。
いまのところ g77 では、f2c の -r8 オプションに相当する 機能(精度自動拡張)がないようなので考えてみます。
egcs-1.0.3a/gcc/f/stc.c: 520 case FFESTP_typeREAL: 521 bt = FFEINFO_basictypeREAL; 522 ktd = FFEINFO_kindtypeREALDEFAULT; 523 break; を 520 case FFESTP_typeREAL: 521 bt = FFEINFO_basictypeREAL; 522 ktd = FFEINFO_kindtypeREALDOUBLE; 523 per_var_kind_ok = FALSE; 524 break; と変更して make したら real → real*8 になって 簡単なプログラムは動きました。複素数も必要な 場合は複素数の所も同様に変更してください。
さる御方から以下のようなお問い合わせをいただきました。
--- cut cut cut ---
egcs でコンパイルすると 0 との比較をした後にジャンプするよ
うな命令列がある場合、例えば、
if (a>0){
....
}
という場合に、本来なら
ble a, $next
....
$next:
という処理にすればいいはずですが、egcs では
cmplt a, $31, $1
bne $1, $next
...
$next:
という処理をしてしまいます。整数系ならばこの処理でも遅くなる
ことはないのですが、浮動小数系の場合には効果てきめんです。
というわけで、ゼロとの比較の場合、cmp 系列の比較をスキップさ
せたいのです。これはピープホールの処理でどうにかなると思うの
ですが、いかがでしょう?
--- cut cut cut ---
この page でも alpha.md の所で peep hole については説明をして
いますが、実際には alpha にはなにも peep hole 最適化は入って
いません、可能か調べてみましょう。
test.c:
double c(double a)
{
if(a>0)
return 1.0;
}
というソースを使って調べます。
#cc -S -O4 -da test.c
でコンパイルすると
test.s:
cpys $f31,$f31,$f1
cmptlt $f1,$f16,$f1
fbeq $f1,$L2
という命令列が生成されます。
この部分の test.c.rtl は
(12038eb08 1b) (insn 10 8 11 (12038eaf0 29) (set (12038eae0 34) (reg:DF 69)
(120390d50 30) (const_double:DF (12038ba48 3c) (cc0) 0 0)) -1 (nil)
(12038eb48 2) (expr_list:REG_EQUAL (120390d50 30) (const_double:DF (12038
(nil)))
(12038ebe8 1b) (insn 11 10 12 (12038ebd0 29) (set (12038eb90 34) (reg:DF 70)
(12038eba0 5f) (lt:DF (12038eae0 34) (reg:DF 69)
(12038e9b0 34) (reg/v:DF 68))) -1 (nil)
(nil))
(12038ec80 1c) (jump_insn 12 11 15 (12038ec68 29) (set (12038ba40 33) (pc)
(12038ec48 3e) (if_then_else (12038ecf0 5b) (eq (12038eb90 34) (reg:D
(120390d50 30) (const_double:DF (12038ba48 3c) (cc0) 0 0))
(12038ec28 3a) (label_ref 21)
(12038ba40 33) (pc))) 181 {minsf3+1} (nil)
(nil))
となっています。
config/alpha/alpha.md を見ると
cpys $f31,$f31,$f1
の部分は、
(define_insn ""
[(set (match_operand:SF 0 "nonimmediate_operand" "=r,r,m,f,f,f,m")
(match_operand:SF 1 "input_operand" "rG,m,rG,f,G,m,fG"))]
"register_operand (operands[0], SFmode)
|| reg_or_fp0_operand (operands[1], SFmode)"
"@
bis %r1,%r1,%0
ldl %0,%1
stl %r1,%0
cpys %1,%1,%0
cpys $f31,$f31,%0
ld%, %0,%1
st%, %R1,%0"
[(set_attr "type" "ilog,ld,st,fcpys,fcpys,ld,st")])
cmptlt $f1,$f16,$f1
の部分は、
(define_insn ""
[(set (match_operand:DF 0 "register_operand" "=f")
(match_operator:DF 1 "alpha_comparison_operator"
[(match_operand:DF 2 "reg_or_fp0_operand" "fG")
(match_operand:DF 3 "reg_or_fp0_operand" "fG")]))]
"TARGET_FP && alpha_tp != ALPHA_TP_INSN"
"cmp%-%C1%' %R2,%R3,%0"
[(set_attr "type" "fadd")
(set_attr "trap" "yes")])
fbeq $f1,$L2
の部分は、
(define_insn ""
[(set (pc)
(if_then_else
(match_operator 1 "signed_comparison_operator"
[(match_operand:DF 2 "reg_or_fp0_operand" "fG")
(match_operand:DF 3 "fp0_operand" "G")])
(label_ref (match_operand 0 "" ""))
(pc)))]
"TARGET_FP"
"fb%C1 %R2,%0"
[(set_attr "type" "fbr")])
から生成されているようです。この部分の見つけ方は命令を少し書き換え
て見てテストプログラムで生成される命令が変化するかを観察します。
peephole 宣言の所の書き方はまた少し違っていてむずかしいのですが
cpys $f31,$f31,$f1
cmptlt $f1,$f16,$f1
fbeq $f1,$L2
に合う peep hole 宣言は、
(define_peephole
[(set (match_operand:DF 0 "register_operand" "")
(match_operand:DF 1 "fp0_operand" ""))
(set (match_dup 0)
(match_operator:DF 2 "alpha_comparison_operator"
[(match_dup 0)
(match_operand:DF 3 "register_operand" "")]))
(set (pc)
(if_then_else
(match_operator 4 "signed_comparison_operator"
[(match_dup 0)
(match_operand:DF 5 "fp0_operand" "")])
(label_ref (match_operand 6 "" ""))
(pc)))
]
"GET_CODE (operands[2]) == LT"
"cpys $f31,$f31,%0\;cmp%-%C2%' %0,%3,%0\;fb%C4 %0,%6")
となります。各部分について説明すると
(define_peephole
[(set (match_operand:DF 0 "register_operand" "")
(match_operand:DF 1 "fp0_operand" ""))
は
cpys $f31,$f31,$f1
の部分を表しています。
fp0_operand が $f31 register_operand が $f1 で 倍精度のゼロの
代入がマッチします。
(set (match_dup 0)
(match_operator:DF 2 "alpha_comparison_operator"
[(match_dup 0)
(match_operand:DF 3 "register_operand" "")]))
は
cmptlt $f1,$f16,$f1
の部分を表しています。
(set (match_dup 0) は cpys 命令で定義されたレジスタへの定義を
ここでも行うことを表しています。
(match_operator:DF 2 "alpha_comparison_operator" は、比較の
結果を代入することを表しています。
[(match_dup 0) (match_operand:DF 3 "register_operand" "")]))
は、上で使われたレジスタと新たに現れたレジスタの比較を表して
います。
(set (pc)
(if_then_else
(match_operator 4 "signed_comparison_operator"
[(match_dup 0)
(match_operand:DF 5 "fp0_operand" "")])
(label_ref (match_operand 6 "" ""))
(pc)))
は
fbeq $f1,$L2
の部分を表しています。
(set (pc) が、プログラムカウンタの定義、すなわち分岐である
ことを示しています。
[(match_dup 0) (match_operand:DF 5 "fp0_operand" "")]) は
ゼロとの比較(RISC なのでゼロとの比較しかないので常にこの
形になりますね)を表しています。
"GET_CODE (operands[2]) == LT"
ここは、条件をしぼる場合に書く場所で
cmptlt $f1,$f16,$f1
の条件が LT の時だけこの最適化を行うことを表しています。
"cpys $f31,$f31,%0\;cmp%-%C2%' %0,%3,%0\;fb%C4 %0,%6")
ここが生成する命令を書く場所です。今は元の命令列をそのまま
生成するように書いてあります。分岐条件の書き方とかを良く
見てください。
命令を最適化した宣言は、
(define_peephole
[(set (match_operand:DF 0 "register_operand" "")
(match_operand:DF 1 "fp0_operand" ""))
(set (match_dup 0)
(match_operator:DF 2 "alpha_comparison_operator"
[(match_dup 0)
(match_operand:DF 3 "register_operand" "")]))
(set (pc)
(if_then_else
(match_operator 4 "signed_comparison_operator"
[(match_dup 0)
(match_operand:DF 5 "fp0_operand" "")])
(label_ref (match_operand 6 "" ""))
(pc)))
]
"GET_CODE (operands[2]) == LT"
"fble %0,%6")
となります。これを config/alpha/alpha.md の最後に追加して再 make すれば
この peephole 最適化が行われます。
また依頼の御手紙が ---cut cut cut--- jsr のコールの際の 3 点セットである jsr $26, hoghoge ldgp $29, 0($26) を ldq $27, hogehoge .... jsr $26, ($27), hogehoge ..... ldgp $29, ??($26) と 3 つにわけてスケジューリングできませんか? ---cut cut cut--- これはなかなか難しい依頼です。 もともとくっついてしか生成出来ないものを無理に分けろとは
ELF だ static だとか分からないのですが分かっている範囲で書くと
gp は スタックポインタとかの仲間でサブルーチン内の定数とかの
アクセスをするためのポインタのようです。
test.f:
subroutine sub3(a)
a=a+1.0
end
を g77 -O4 test.f して objdump --disassemble-all a.out > p すると
p:
00000001200014c8 :
1200014c8: 11 00 bb 27 ldah gp,17(t12)
1200014cc: e8 35 bd 23 lda gp,13800(gp)
00000001200014d0 :
1200014d0: f0 84 3d a4 ldq t0,-31504(gp)
1200014d4: 00 00 30 88 lds $f1,0(a0)
1200014d8: 00 00 41 89 lds $f10,0(t0)
1200014dc: 01 10 2a 58 adds $f1,$f10,$f1
1200014e0: 00 00 30 98 sts $f1,0(a0)
1200014e4: 01 80 fa 6b ret zero,(ra),0x1
となります、ldgp にあたる所が ldah と lda です、まあ gp を
この手続き内での値に変えているのでしょう、で この gp を使
って 定数 1.0 のロードをしているようです。
test.f:
subroutine sub3(a)
a=a+a
end
とすると定数がないので
00000001200014c8 :
1200014c8: 00 00 30 88 lds $f1,0(a0)
1200014cc: 01 10 21 58 adds $f1,$f1,$f1
1200014d0: 00 00 30 98 sts $f1,0(a0)
1200014d4: 01 80 fa 6b ret zero,(ra),0x1
というふうに出ます。このサブルーチン内でまたサブルーチンを
呼んでいると定数を使っていなくても ldgp が出ます。(呼んだ
先で壊れるかもしれないから)
ldgp がなくて gp を壊さないのでこのサブルーチンから戻った
時は ldgp がいらない筈です。
do 10 i=1,n
10 a(i)=a(i)+b
のように continue や enddo 文を使わないで do ループを書くと
-funroll-loops オプションをつけても unroll されないという件が
あります。（linux-alpha-jp ML より）
これは、以下の部分の return; をコメント化することで unroll
可能になります。
gcc/unroll.c:
if (LABEL_NAME (start_label))
{
/* The jump optimization pass must have combined the original start label
with a named label for a goto. We can't unroll this case because
jumps which go to the named label must be handled differently than
jumps to the loop start, and it is impossible to differentiate them
in this case. */
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Unrolling failure: loop start label is gone\n");
return;
}
ここでは、
do
10 continue
a(i)=
enddo
のように unroll するループの本体部分の先頭がユーザ定義のラベルの
場合をチェックして unroll しないようにしているのですが、特に問題
なさそうです。
その１： 1byte アクセスの高速化 について
その２： f77/alpha load store の並べ換え について
alpha のような細粒度パイプラインを持つプロセッサには、 命令並べ換えによる最適化が欠かせません。 ここでは、f2c -> gcc を使う場合の最適化をします。
その３： cache miss プロファイラについて
参考にできるコードがいまのところみつからずPALコ ードの記述が難しく中断しています。
その４： ベクトル sqrt 関数について
ここのプログラムは、実験用です。オリジナルは libc の ソースです。再配布等の際はご注意下さい。
alpha アーキテクチャの高速性を生かすために、配列 を渡してその配列の sqrt を一度に求めて返却する ベクトル sqrt 関数です。 関数中でアンロールを行い数倍の高速化を行ってます。
計算機はどうやってSQRT()関数の値を高速に計算するのでしょうか。 ニュートン法を使えば、r'=(x/r+r)/2 の反復でもとめられますが、 うまく初期値を選ばないと反復の回数が多くなってしまいますそこで 初期値を多項式で与えてやります、多項式も全ての範囲をカバーする ことはできないので入力の範囲を０〜１などに変換する正規化をしま す、指数部をとるだけで済む正規化ならば簡単で高速です。 正規化した値で多項式を計算し予め誤差を許容範囲に小さくできる と見積もった回数だけニュートン法を繰り返して、次に正規化の逆を 行って答えを求めます。このように最後の1bitまで計算すると遅くな ります、誤差の見積もりができる人は自分で多項式近似だけのSQRT() 関数を作ると高速化できるでしょう。 詳しくは、一松信氏の教科書などを参照してください。
その５： ベクトル演算ルーチンについて
配列の四則演算をアセンブラチューニングされた サブルーチン呼出にすることにより高速化します。 ４byte浮動小数点版のみです。
subroutine faddv(a,b,c,i)
real a(*),b(*),c(*),i
do j=1,i
c(j)=a(j)+b(j)
enddo
end
とのような演算ルーチンがアセンブラコーディ
ングされています。
このベクトル演算ルーチンはSQRT()関数と比較して十分に性能が でません、理由は１つの演算のたびにメモリからのロードストアを 繰り返す為です、alphaのメモリバンド幅では、２項 演算だけをするルーチンをアセンブラコーディングしても高速化でき ないようです。
その６： 32bit int 高速化
まず、
do i=1,10
a(i)=〜
enddo
のようなループがあって最適化(-O)が指定されていないと
i=0
ラベル：
i=i+1
tmp=i*4+a()のベースアドレス
tmpのアドレスに値をストア
ラベルへジャンプ
のようなオブジェクトが生成されます。
これが最適化ありだと
tmp=a()のベースアドレス
ラベル：
tmp=tmp+4
tmpのアドレスに値をストア
ラベルへジャンプ
のようなオブジェクトが生成されます。
ループの繰り返しごとに 4byte アドレスを
ずらしてやるだけなので命令も少なくなりますし、命令の
実行時間(最大パス長)も短くなります。
バグが見つかっています、ご注意ください。
gcc-2.7.1/config/alpha/alpha.md リスト読み
始めに
ここに書く内容は、gcc/config/alpha/alpha.md をリスト読みした時の
メモの内容です。例えば 型の種類等については書いていません。
そういった内容は、gcc/gcc-info〜 に詳しく書かれていますのでそちらを
参照してください。
alpha.md の md とはマシン依存の略で、config/alpha 配下には、gcc で
alpha アーキテクチャに依存する部分が集められています。
configure を実行すると config/alpha 配下のファイルにパスが張られて
make 実行時に プリプロセッサが alpha.md を参考にして gcc/ 配下にマシン
依存の .c を生成して、gcc を作ります。make を実際にしてみると良く解り
ます。
alpha.md はその生成の為の種をある規則に従って記述してあります。
規則については、gcc-info〜に解説してあるもののよく解らないので、
実際の alpha.md と 生成される RTL 式 及び アセンブラ出力を
参考に alpha.md の規則を調べてみます。
gcc-2.7.1 を使っていますので 行番号は、gcc-2.7.1 のものになります。
参考文献としては、gcc 1.26 の gcc.info-〜 の和訳である。
「インサイド GNU C コンパイラ」 啓学出版(ISBN4-7665-0960-9)
が手元にあると役立ちます。ただし 出版社が倒産しているので
図書館で探してみてください。当然 Copy Left なので堂々と
コピーして手もとに置いてください。
＃訳者の岩谷様 電子原稿の公開はできないものでしょうか。
まず例として Linus さん御推薦の char への代入
sub.c:
1 #include
2 #include
3
4 struct meibo{
5 struct meib *next;
6 char name;
7 };
8 struct meibo *first=NULL;
9
10 int sub()
11 {
12 struct meibo *p;
13
14 for(p=first;p;p=p->next)
15 {
16 p->name=1;
17 }
18 }
を cc -S -da sub.c で コンパイルします。
そうすると sub.c.rtl というファイルができます。これが最初に
作られる RTL 式* のダンプです。本当はこの前にも 構造式がある
はずですが ダンプはありません。(yacc とかカッコつけたやり方
で処理されているのが最近判明しました)
RTL式:コンパイラでは入力したソースから機械語の命令列を作るまで
の間、中間言語という形式でソースの内容を表します。gcc で
は RTL式という形の中間言語が使われています。実際の RTL式
はメモリ中のデータ列ですがダンプルーチンによってプリント
アウトすることができます。
16 p->name=1;
にあたる部分の sub.s は、
36 $42:
37 ldq $1,16($15)
38 bis $31,1,$2
39 ldq_u $3,9($1)
40 addq $1,9,$4
41 mskbl $3,$4,$3
42 insbl $2,$4,$2
43 bis $2,$3,$2
44 stq_u $2,9($1)
です、この部分の sub.c.rtl は、
247 (code_label 22 21 24 10 "")
248
249 (note 24 22 26 "" NOTE_INSN_DELETED)
250
251 (insn 26 24 28 (set (reg:DI 72)
252 (mem:DI (reg:DI 65))) -1 (nil)
253 (nil))
254
255 (insn 28 26 29 (set (reg:QI 73)
256 (const_int 1)) -1 (nil)
257 (expr_list:REG_EQUAL (const_int 1)
258 (nil)))
259
260 (insn 29 28 30 (set (reg:DI 75)
261 (mem/s:DI (and:DI (plus:DI (reg:DI 72)
262 (const_int 9))
263 (const_int -8)))) -1 (nil)
264 (nil))
265
266 (insn 30 29 31 (set (reg:DI 74)
267 (plus:DI (reg:DI 72)
268 (const_int 9))) -1 (nil)
269 (nil))
270
271 (insn 31 30 32 (set (reg:DI 75)
272 (and:DI (not:DI (ashift:DI (const_int 255)
273 (ashift:DI (reg:DI 74)
274 (const_int 3))))
275 (reg:DI 75))) -1 (nil)
276 (nil))
277
278 (insn 32 31 33 (set (reg:DI 76)
279 (ashift:DI (zero_extend:DI (reg:QI 73))
280 (ashift:DI (reg:DI 74)
281 (const_int 3)))) -1 (nil)
282 (nil))
283
284 (insn 33 32 34 (set (reg:DI 76)
285 (ior:DI (reg:DI 76)
286 (reg:DI 75))) -1 (nil)
287 (nil))
288
289 (insn 34 33 37 (set (mem/s:DI (and:DI (plus:DI (reg:DI 72)
290 (const_int 9))
291 (const_int -8)))
292 (reg:DI 76)) -1 (nil)
293 (nil))
294
295 (note 37 34 38 "" NOTE_INSN_LOOP_CONT)
です。で、
39 ldq_u $3,9($1)
にあたるのが
260 (insn 29 28 30 (set (reg:DI 75)
261 (mem/s:DI (and:DI (plus:DI (reg:DI 72)
262 (const_int 9))
263 (const_int -8)))) -1 (nil)
264 (nil))
この RTL 式です。改行されていることには意味はありません。
(insn 29 28 30 は、この式の番号が 29 で１つ前が 28 次が 30 である
ことを示します。
(set (reg:DI 75) は、set が この次 定義式であることを示して
(reg:DI 75) レジスタ番号 75 番に DI という型で定義することを示して
います。ここはまだレジスタ割り当ての前なので 75 番は仮想レジスタ番号*
です、この番号はこのサブルーチン中で一意なので、
仮想レジスタ:中間テキストレベルでは、HW の構成を抽象化するために
レジスタ数を無限と考えて処理しますこの時のレジスタ
を仮想レジスタと言います。
275 (reg:DI 75))) -1 (nil)
で参照されていることがわかります。DI は 8byte 整数を示しています。
(mem/s:DI は DI の型のメモリオペランドを示しています。
(and:DI は、and を示しています、わかりにくいですが、
(and:DI () ()) で最初の () の内容と次の () の内容の and をとることを
示しています、このように 2 オペランドをとるものと (not:DI ()) 否定の
ように 1 オペランドをとるものがあります。
(plus:DI (reg:DI 72) (const_int 9)) で、仮想レジスタ 72 の内容と 定数
9 を加算した結果 を示しています。 (const_int -8)) まででその結果と -8
の and を示しています。 これで (mem/s:DI ()) が終りました解りにくいで
すがこれが alpha の ldq_u のアドレスを示しています、
この (mem/s:DI (and:DI (plus:DI の並びは ldq_u のお約束で これがくると
ldq_u 命令になり
251 (insn 26 24 28 (set (reg:DI 72)
252 (mem:DI (reg:DI 65))) -1 (nil)
253 (nil))
のように単純だと
37 ldq $1,16($15)
_u がつきません。(オフセットの 16 がどこから来てるか気になりますが)
このように RTL 式中のオペランドの構成が 生成される命令を決めています。
どう関連づけされているのかは、alpha.c alpha.h alpha.md のどこかに
あるはずですが解っていません、アセンブラと RTL の比較 で約束を調べて
います。
この調子でみていくと、
271 (insn 31 30 32 (set (reg:DI 75)
272 (and:DI (not:DI (ashift:DI (const_int 255)
273 (ashift:DI (reg:DI 74)
274 (const_int 3))))
275 (reg:DI 75))) -1 (nil)
276 (nil))
が、
41 mskbl $3,$4,$3
などが解ります、 255 は 8bit のマスクを示しているようだし、3 は
8 倍を示して 回りくどいながら mskbl 命令の動きを表しています。
さてこれで RTL式と 命令列の関係は 解りました？が、
この RTL 式の列が どう生成されているかというと
alpha.md の
3703 (define_expand "unaligned_storeqi"
3704 [(set (match_operand:DI 3 "register_operand" "")
3705 (mem:DI (and:DI (match_operand:DI 0 "address_operand" "")
3706 (const_int -8))))
3707 (set (match_operand:DI 2 "register_operand" "")
3708 (match_dup 0))
3709 (set (match_dup 3)
3710 (and:DI (not:DI (ashift:DI (const_int 255)
3711 (ashift:DI (match_dup 2) (const_int 3))))
3712 (match_dup 3)))
3713 (set (match_operand:DI 4 "register_operand" "")
3714 (ashift:DI (zero_extend:DI (match_operand:QI 1 "register_operand" ""))
3715 (ashift:DI (match_dup 2) (const_int 3))))
3716 (set (match_dup 4) (ior:DI (match_dup 4) (match_dup 3)))
3717 (set (mem:DI (and:DI (match_dup 0) (const_int -8)))
3718 (match_dup 4))]
3719 ""
3720 "")
に 上に 示した RTL式と全く同じ 並び を見ることができます、
命令列でいうと
39 ldq_u $3,9($1)
40 addq $1,9,$4
41 mskbl $3,$4,$3
42 insbl $2,$4,$2
43 bis $2,$3,$2
44 stq_u $2,9($1)
の部分(つまりアラインされていない char(QI) のストアです。これが 元に
なってこのとうりの RTL 式列が生成されています。これは RTL 式の構造の
定義なので さっきとは少し形が違っていて、
[(set (match_operand:DI 3 "register_operand" "") は [ から ] までが
生成する RTL 式を示して 3 番目の オペランドに 適合して それがレジスタ
オペランドであることを示しています。
3709 (set (match_dup 3) は、(match_dup 3) で それより前にでてきた
3 番目のオペランド (match_operand:DI 3 "register_operand" "") と 全く
同じものを示します、つまり
3704 [(set (match_operand:DI 3 "register_operand" "")
で定義したレジスタに
3709 (set (match_dup 3)
でまた定義することを示しています。
39 ldq_u $3,9($1)
40 addq $1,9,$4
41 mskbl $3,$4,$3
でみると $3 がこのとうりに再定義されています。
でこの RTL 式定義がどこで参照されているかというと
3703 (define_expand "unaligned_storeqi"
に gen_ を付けた(これはお約束)
3765 (define_expand "movqi"
3766 [(set (match_operand:QI 0 "general_operand" "")
3767 (match_operand:QI 1 "general_operand" ""))]
3768 ""
〜〜〜
3840 else
3841 {
3842 rtx temp1 = gen_reg_rtx (DImode);
3843 rtx temp2 = gen_reg_rtx (DImode);
3844 rtx temp3 = gen_reg_rtx (DImode);
3845 rtx seq = gen_unaligned_storeqi (get_unaligned_address (operands[0]),
3846 operands[1], temp1, temp2, temp3);
3847
3848 alpha_set_memflags (seq, operands[0]);
3849 emit_insn (seq);
3850 }
で参照されています。 movqi というのは、1byte の転送で
3766 [(set (match_operand:QI 0 "general_operand" "")
3767 (match_operand:QI 1 "general_operand" ""))]
で全ての 型 QI から QI への転送をひっかけて、オペランドがメモリにある
とか unaligned だとかを調べて適切な命令を生成します。
3703 (define_expand "unaligned_storeqi"
は当然整列されていない 1byte ストアの時だけに呼ばれます。
3843 rtx temp2 = gen_reg_rtx (DImode);
は、ワークのレジスタの生成で うえの $3 にあたります。
オペランドの数 ５つが 上の RTL 式の定義中の 0 〜 4 の match_operand
に対応しているのがわかるとおもいます。
ここに 条件式をいれれば自分の好きな RTL 式を生成させることが
できます、例えば、
16 p->name=1;
の様に 1 が定義されているか調べるには、
3770 { extern rtx get_unaligned_address ();
3771
3772 /* If the output is not a register, the input must be. */
3773 if (GET_CODE (operands[0]) == MEM)
3774 operands[1] = force_reg (QImode, operands[1]);
の 3771 行に IF(INTVAL(operans[1]==1) {} と書けば調べられます。
3774 行で オペランドが 代入した結果のレジスタへと変えられて
いるのでここで調べる必要があるのです。
この様に 参照のツリーをたどったりして自由に どのような 入力だとか
を調べられるのですがまだ研究中です。
たとえば今は、p->name が8 byte 境界にあるかどうかを調べたい(これが
できれば Linus さんの要求する命令列が生成できる) のですがうまく
いっていません。あと peep_hole については少し解ってますが、また今度、
他のマシンモデルの peep_hole がたいへん参考になります。
peep hole 最適化
peep hole(覗き穴)最適化とは、コンパイラが前後数個の テキストの
関係だけを調べてする最適化で コンパイラの最終段階に良くされます。
(床屋さんが最後に必ずやる チョキチョキと同じです)
例えば、前の命令で定義したレジスタが次の命令で参照もされないのに
上書きされてたりする場合に 前の命令を削除したりする最適化のことです。
このような命令列になるわけないと考えがちですが、最適化を繰り返し
たりするとこのような盲腸命令ができることがあります。
gcc は、-O 以上が指定された場合にこの最適化を行い、この最適化をさせる
ルールは alpha.md の最後に宣言します。(alpha アーキテクチャ用は 今は、
１個もありませんが)
例えば、
(define_peephole
[(set (match_operand:DI 0 "register_operand" "")
(ior:DI (const_int 0) (match_dup 0))) ]
""
"")
と書くと、 bis ?,0,? の様な自分自身に対するレジスタ転送を
削除します。
(define_peephole
[(set (match_operand:DI 0 "register_operand" "")
(ior:DI (const_int 0) (match_dup 0))) ]
""
"and %0,0,%0")
と書くと and 命令に置き換えます。
置き換えの条件も書けて、
(define_peephole
[(set (match_operand:DI 0 "register_operand" "")
(ior:DI (const_int 0) (match_dup 0))) ]
"REGNO(operands[0]) > 3 && REGNO(operands[0]) < 6"
"and %0,0,%0")
とかくと、レジスタ番号が 4 と 5 の時だけに置き換えが行われ
ます。
%0 の 0 は、(match_operand:DI 0 の 0 に対応してて %1 なら
(match_operand:DI 1 に対応します。
1 (define_peephole
2 [(set (match_operand:DI 0 "register_operand" "")
3 (ior:DI (const_int 0) (match_dup 0))) ]
4 "REGNO(operands[0]) > 3 && REGNO(operands[0]) < 6"
5 "and %0,0,%0")
2〜3 行目にマッチする命令列に対して 4 行目の条件を検査して
成り立てば 5 行目の命令列に置き換えます。
メモリ関連の命令の場合には、
(define_peephole
[(set (match_operand:DI 0 "register_operand" "")
(match_operand:DI 1 "memory_operand" ""))]
""
"ldq_u %0,%1")
memory_operand と書けば、 %1 は base+disp を表し、
(define_peephole
[(set (match_operand:DI 0 "register_operand" "")
(mem:DI (match_operand:DI 1 "register_operand" ""))) ]
""
"ldq_u %0,0(%1)")
と書けば、%1 は base を表します。
複数命令については、 \； で区切って書きます。
本来、CISC にありがちな 複合命令への置き換えなどに使います。
同じ動きを幾種類にも表せる CISC なら腕の見せどころも多い
はずです。 (RISCなら積和命令ぐらいですか)
急ぎ足でしたが、とりあえず。
RTL 式 とアセンブラ命令の関係
命令の雛型は、
alpha.md:
3517 (define_insn ""
3518 [(set (match_operand:DI 0 "general_operand" "=r,r,r,r,r,r,r,m,f,f,f,Q"
3519 (match_operand:DI 1 "input_operand" "r,J,I,K,L,s,m,rJ,f,J,Q,fG")
3520 "register_operand (operands[0], DImode)
3521 || reg_or_0_operand (operands[1], DImode)"
3523 bis %1,%1,%0
3524 bis $31,$31,%0
3525 bis $31,%1,%0
3526 lda %0,%1
3527 ldah %0,%h1
3528 lda %0,%1
3529 ldq%A1 %0,%1
3530 stq%A0 %r1,%0
3531 cpys %1,%1,%0
3532 cpys $f31,$f31,%0
3533 ldt %0,%1
3534 stt %R1,%0"
3535 [(set_attr "type" "iaddlog,iaddlog,iaddlog,iaddlog,iaddlog,ldsym,ld,st
3536
というように記述されています。
3518 [(set (match_operand:DI 0 "general_operand" "=r,r,r,r,r,r,r,m,f,f,f,Q"
は、オペランドの種類を表しています。r ならレジスタ m ならメモリという具
合です、何番目かが命令イメージの何番目かに対応しています。
3529 ldq%A1 %0,%1
なら、
3518 [(set (match_operand:DI 0 "general_operand" "r"
3519 (match_operand:DI 1 "input_operand" "m")
に対応しているというわけです。
3529 ldq%A1 %0,%1
の %A は、_u を付けるかどうかの処理をしろということで、
alpha.c:
1224 case 'A':
1225 /* Write "_u" for unaligned access. */
1226 if (GET_CODE (x) == MEM && GET_CODE (XEXP (x, 0)) == AND)
1227 fprintf (file, "_u");
1228 break;
で、オペランドに unaligned の処理が入っているかどうかを調べて
_u を付ける処理をしています。
alpha.md:
294 (define_split
295 [(set (match_operand:DI 0 "register_operand" "")
296 (plus:DI (plus:DI (match_operand:DI 1 "register_operand" "")
297 (match_operand:DI 2 "register_operand" ""))
298 (match_operand:DI 3 "add_operand" "")))]
299 "reload_completed"
300 [(set (match_dup 0) (plus:DI (match_dup 1) (match_dup 2)))
301 (set (match_dup 0) (plus:DI (match_dup 0) (match_dup 3)))]
302 "")
これは、RTL 式に 必要な変更をするもののようです、
A=(B+C)+？ では１つの命令 で表せないので A=B+C;A=A+？ に
分解しているように見えます。
print-rtl.c:
このルーチンは、RTL 式をここで見ているようなダンプで出力するルーチン
です、ここからも RTL 式の構造のヒントが得られます。
final.c:
このルーチンは命令ごとにループして実際のアセンブラ命令を出力します。
例えば、
2553 void
2554 output_address (x)
2555 rtx x;
2556 {
2557 walk_alter_subreg (x);
2558 PRINT_OPERAND_ADDRESS (asm_out_file, x);
2559 }
では、メモリアクセス命令の base と disp の出力をしています。
alpha.h:
1941 #define PRINT_OPERAND_ADDRESS(FILE, ADDR) \
1942 { rtx addr = (ADDR); \
1943 int basereg = 31; \
1944 HOST_WIDE_INT offset = 0; \
1945 \
1946 if (GET_CODE (addr) == AND) \
1947 addr = XEXP (addr, 0); \
〜〜〜
にマクロがあります。ここで作られた RTL 式をたどって実際の命令の
オペランドを生成しているので、理解のヒントになります。
expr.c:
memcpy などのインライン展開されるテキストが入っています。
move_by_pieces などでcopyを生成するもようです。
unroll.c:
unroll.c は、unroll といってループを何回かに展開する最適化を行ないます。
1151 /* Set the jump label so that it can be used by later loop unr
1152 passes. */
1153 JUMP_LABEL (insn) = tem;
1154 LABEL_NUSES (tem)++;
1155 }
ここでループ本体をコピーしている
1157 copy_loop_body (copy_start, copy_end, map, exit_label,
1158 i == unroll_number - 1, unroll_type, start_label,
1159 loop_end, insert_before, insert_before);
1160 }
1161
ここで各配列のインデックスの分離を行なっている
2818 emit_insn_before (gen_rtx (SET, VOIDmode, tem,
2819 copy_rtx (v->new_reg)),
2820 loop_start);
2821 if (recog_memoized (PREV_INSN (loop_start)) < 0)
2822 {
2823 rtx sequence, ret;
最後に、マシンモデルというのは C という言語を構成するのに
必要な中間言語の種類をどうやって実際の各ハードの命令列に
マッピングするかを定義するファイルのようです。新しいハード
を追加するには必要とされる中間言語の種類全てについて対応
する宣言をしてやります。
目次に戻る
g77の最適化について調査した所 RTL 生成以前に ついての調査になりました。
if(a.gt.0) a=a+b
call sub(a)
end
とかくと a は a=a+b の所でメモリにストアされてしまうが、
if(a.gt.0) a=a+b
c=a
call sub(c)
end
とかくと a は レジスタに割り当てられて メモリにストアされずに済む
が何故かいつでもレジスタを使うようにできないかという問題がありました。
g77 の問題なのでなので f/ 配下を調べる
top.c:bool ffe_is_ffedebug_ = FALSE;
で妙なダンプがでるようになる
target.h にいろいろな規定値がある
com.c:void ffecom_end_transition ();
->std.c:ffestd_exec_end ();
->stc.c:ffestc_shriek_subroutine_ (bool ok)
ここでサブルーチンとかファンクションとかがでてくる
stc.c:
/* ffestc_R1225 -- END SUBROUTINE statement
ffestc_R1225(name_token);
ここはサブルーチンの最後のEND の処理ということ
->bfd.c:static ffelexHandler
ffestb_varlist6_ (ffelexToken t)
ここでループして stc.c 内のいろいろな statement に対応する部分を
call している
->bfd.c:static ffelexHandler ffestb_varlist5_ (ffelexToken t)
->bfd.c:ffestb_varlist (ffelexToken t)
->sta.c:ffesta_second_ (ffelexToken t)
->sta.c:ffesta_first (ffelexToken t)
->st.c:ffest_first (ffelexToken t)a
->top.c:ffe_file (ffewhereFile wf, FILE *f)a
->parse.c:yyparse ()
yacc ???
f2c->gcc でも同じ現象が起きるので gcc の部分だけで解決できるかも
gcc/x86 でも同じ振舞をした(マシン依存でない)
一番最初の RTL ダンプの .c.rtl で 既に２つのソースの RTL が違うので
RTL を作るところをチェックしなければならない
(最初から RTL が片方はメモリ、片方はレジスタで出ている)
c=a
if(a.gt.0) a=a+b
call sub(a)
end
a に関する属性はこのサブルーチン内で一定のようだ。
stmt.c:RTL を作る
c-decl.c:
lookup_name (name)
tree name;
{
register tree val;
if (current_binding_level != global_binding_level
&& IDENTIFIER_LOCAL_VALUE (name))
val = IDENTIFIER_LOCAL_VALUE (name);
else
val = IDENTIFIER_GLOBAL_VALUE (name);
return val;
}
-> c-lex.c:yylex()
ここで文法を解析している
c-lex.c:yyprint() なにかの print
cc -O を付けて始めて store が消える このオプションを
参照している場所から推定できないか
main.c:t
toplev.c:main()
->compile_file (filename);
3825 /*yamada*/
3826 obey_regdecls = (optimize == 0);
このフラグが関係しているようだ。
stmt.c:
3584 else if (DECL_MODE (decl) != BLKmode
3585 /* If -ffloat-store, don't put explicit float vars
3586 into regs. */
3587 && !(flag_float_store
3588 && TREE_CODE (type) == REAL_TYPE)
3589 && ! TREE_THIS_VOLATILE (decl)
3590 && ! TREE_ADDRESSABLE (decl)
3591 && (DECL_REGISTER (decl) || ! obey_regdecls))
ここで obey_regdecls を反転してやると全て メモリになって
しまうのでここの処理が関係している
3590 {
3591 /* Automatic variable that can go in a register. */
3592 int unsignedp = TREE_UNSIGNED (type);
3593 enum machine_mode reg_mode
3594 = promote_mode (type, DECL_MODE (decl), &unsignedp, 0);
3595 /* explow.c の中にある */
3596 /* ここを通ったあとが問題 */
3597 DECL_RTL (decl) = gen_reg_rtx (reg_mode); emit-rtl.c
3598 fprintf(stderr," yamada 1 %i %i (%x) ",DECL_MODE (decl),unsignedp
3599 ,DECL_RTL (decl));
この fprintf で出した アドレスと -da のダンプのアドレスを比較
するとここで メモリかレジスタの RTL を生成しているようだ
ここで作られる時に メモリかレジスタか決定しているのかそれ以前にすでに
決定しているのかはまだ不明
automatic data には２種類あってレジスタの上に置いといて保存しなくて
も良いものとメモリにつねに保存しないといけないものがある、フロー解析が
十分でないので基本ブロックの最後でつねにメモリにセーブされてしまう
print-rtl.c
73 if (in_rtx == 0)
74 {
75 fprintf (outfile, "(nil)");
76 sawclose = 1;
77 return;
78 }
79 else fprintf (outfile, " (%lx %x) ",in_rtx,GET_CODE (in_rtx));
RTL のアドレスを出す為のパッチ
出力の例
yamada 1 12 0 (2038f2d8) yamada 1 12 0 (2038f3b8) yamada 1 12 0 (2038f498) ; block 0, state NIL
対応する RTL ダンプ
(2038f2d8) (mem:SF (2038c668) (reg:DI 65))
(2038f3b8) (reg/v:SF 69)
(2038f498) (reg/v:SF 70)
-O を指定しない場合は
stmt.c:
3634 DECL_RTL (decl)
3635 = assign_stack_temp (DECL_MODE (decl),
3636 ((TREE_INT_CST_LOW (DECL_SIZE (decl))
3637 + BITS_PER_UNIT - 1)
3638 / BITS_PER_UNIT),
3639 1);
3640 fprintf(stderr," yamada 31 (%x) ",DECL_RTL (decl));
3641 MEM_IN_STRUCT_P (DECL_RTL (decl)) = AGGREGATE_TYPE_P (TREE_TYPE (d
ecl));
で全て メモリ への RTL を作っている
DECL_REGISTER (decl) をキーにして調べてみる
toplev.c:
2633 for (i = 0; i < len; i++)
2634 {
2635 decl = vec[i];
という記述がある decl は何かに１つづつ割り当てられていて
何かを記述しているらしい
halfpic.c: debug_tree (decl);
print-tree.c:debug_tree (node)
stmt.c:
3597 DECL_RTL (decl) = gen_reg_rtx (reg_mode); emit-rtl.c
3598 fprintf(stderr," yamada 1 %i %i (%x) ",DECL_MODE (decl),unsignedp
3599 ,DECL_RTL (decl));
debug_tree(decl);
で decl のダンプがとれるが特にレジスタ割り当て可能とそうでない
場合に違いはなさそうだ
gen_reg_rtx (reg_mode); emit-rtl.c を素直に調べた方がよさそうだ
emit-rtl.c:
488 gen_reg_rtx (mode)
550 val = gen_rtx (REG, mode, reg_rtx_no);
290 gen_rtx VPROTO((enum rtx_code code, enum machine_mode mode, ...))
364 fprintf(stderr," ya 221 ");
365 rt_val = rtx_alloc (code);
366 rt_val->mode = mode;
367 REGNO (rt_val) = regno;
368 fprintf(stderr," ya 221(%x) ",rt_val);
369 /* おかしいメモリの場合もここを通る */
370 return rt_val;
371 }
370 print_rtl(stderr,rt_val);
で RTL ダンプがとれる
s ya 22 ya 221 ya 221(2038f4b8)
((( (2038f4b8) (reg:SF 68) )))
yamada 14 [2038f4b8] yamada 1 (2038f4b8)
となっていても
(2038fb20) (insn 23 8 10 (2038fb08) (set (2038faf8) (reg:SF 75)
(2038f4b8) (mem:SF (2038c848) (reg:DI 65))) -1 (nil)
(nil))
test.f.rtl では、メモリに書き変わっている？
toplev.c:
2175 static void
2176 compile_file (name)
2177 char *name;
2178 {
がはじまり。
2540 if (rtl_dump)
2541 {
2542 register rtx insns;
2543 insns = get_insns ();
2544 print_rtl (stderr, insns);
2545 }
のようにして RTL ダンプをとって書き変わっている所をさがしているが
だめ。最初の作る所の近くで書き換えてしまっているかも。
しょうがないのでもう一度ふりだしに戻る
stmt.c:
3584 else if (DECL_MODE (decl) != BLKmode
3585 /* If -ffloat-store, don't put explicit float vars
に戻る
3539 void
3540 expand_decl (decl)
やっと expand_decl を呼んでいる所がわかった
g77 なので f/ 配下なのであった
f/com.c
14476 if (TYPE_SIZE (TREE_TYPE (tem)) != 0)
14477 {
14478 expand_decl (tem);
14438 static tree
14439 start_decl (tree decl, bool is_top_level)
7938 ffecom_sym_transform_ (ffesymbol s)
8137 t = start_decl (t, FALSE);
で呼ばれている。ここではレジスタのままである。
6641 s = ffecom_sym_transform_ (s);
ここらをそれぞれの変数につき call している間はレジスタの
ままのようだ。
rtl dump の expr_list とかの種は rtl.def にある。
そろそろ、gcc 内のテーブルのチェーンとかも押える頃
tree.c:
2041 tree
2042 build_decl_list (parm, value)
2043 tree parm, value;
2044 {
2045 register tree node;
2046 register struct obstack *ambient_obstack = current_obstack;
2047 current_obstack = &temp_decl_obstack;
2048 node = build_tree_list (parm, value);
2049 current_obstack = ambient_obstack;
2050 return node;
2051 }
2030 build_tree_list (parm, value)
2031 tree parm, value;
2032 {
2033 register tree t = make_node (TREE_LIST);
2034 TREE_PURPOSE (t) = parm;
2035 TREE_VALUE (t) = value;
2036 return t;
2037 }
decl を作っている。
toplev.c:
globals = getdecls ();
for (i = 0, decl = globals; i < len; i++, decl = TREE_CHAIN (decl))
c-decl.c:
2688 tree
2689 getdecls ()
2690 {
2691 return current_binding_level->names;
2692 }
というチェーンで decl はたどれる。
f/perse.c:
73 #if FFECOM_targetCURRENT == FFECOM_targetFFE
74 wf = ffewhere_file_new (NAME_OF_STDIN, strlen (NAME_OF_STDIN));
75 ffecom_file (NAME_OF_STDIN);
76 ffe_file (wf, stdin);
77 #elif FFECOM_targetCURRENT == FFECOM_targetGCC
78 wf = ffewhere_file_new (main_input_filename, strlen (main_input_filename));
79 ffecom_file (main_input_filename);
80 ffe_file (wf, finput);
81 #else
82 #error
83 #endif
ここの間に RTL の生成が呼ばれている。
ここに戻って来る前に メモリに書き変わっている。
f/top.c:
546 void
547 ffe_file (ffewhereFile wf, FILE *f)
548 {
ここ以降
549 ffe_init_1 ();
550 ffelex_set_handler ((ffelexHandler) ffest_first);
551 ffewhere_file_set (wf, TRUE, 0);
552 if (ffe_is_free_form_)
553 ffelex_file_free (wf, f);
554 else
555 ffelex_file_fixed (wf, f);
ここ以前
556 ffest_eof ();
557 ffe_terminate_1 ();
558 }
から
f/lex.c:
1811 ffelexHandler
1812 ffelex_file_fixed (ffewhereFile wf, FILE *f)
1813 {
が呼ばれる、この先で処理されているらしい
1886 ffelex_finish_statement_ ();
1887 ffewhere_line_kill (ffelex_current_wl_);
1888 ffewhere_column_kill (ffelex_current_wc_);
1885 行で既にメモリになっている。
ここは、EOF が検出された時にくる処理なのですでにその前に
メモリへの書き換えの処理がされていることになる。
C の場合は実引数に現れた変数は行った先のサブルー
チンでグローバル領域にアドレスがコピーされて他のサ
ブルーチンで参照される可能性があるので全てのサブル
ーチンコールの前で変数の内容をメモリにストアする必
要が生じてしまうこの処理が g77 にも影響しているの
ではないか。
gcc.info-13:
813 If you use `longjmp', beware of automatic variables. ANSI C says
814 that automatic variables that are not declared `volatile' have undefined
815 values after a `longjmp'. And this is all GNU CC promises to do,
816 because it is very difficult to restore register variables correctly,
817 and one of GNU CC's features is that it can put variables in registers
818 without your asking it to.
819
820 If you want a variable to be unaltered by `longjmp', and you don't
821 want to write `volatile' because old C compilers don't accept it, just
822 take the address of the variable. If a variable's address is ever
823 taken, even if just to compute it and ignore it, then the variable
824 cannot go in a register:
825
826 {
827 int careful;
828 &careful;
829 ...
830 }
g77 では、２つの借り引数が同じ変数をさしていた場合に
問題が起こるので C の仕様をそのまま受け継いだ可能性も
ある。
f/lex.c:
1859 ffelex_current_wc_ = ffewhere_column_unknown ();
この 先で処理されるようだ。
3005 if ((ffelex_number_of_tokens_ == ffelex_label_tokens_)
3006 && (ffelex_token_->type == FFELEX_typeNAMES)
3007 && (ffelex_token_->length == 3)
3008 && (ffesrc_strncmp_2c (ffe_case_match (),
3009 ffelex_token_->text,
3010 "END", "end", "End",
3011 3)
3012 == 0))
3013 {
3014 ffelex_finish_statement_ ();
3015 disallow_continuation_line = TRUE;
3016 ignore_disallowed_continuation = FALSE;
3017 fprintf(stderr,"\n36natosaki\n");
3018 goto beginning_of_line_again; /* :::::::::::::::::::: */
ここ通ってる。
3014 /*ここはまだダンプでない */
3015 ffelex_finish_statement_ ();
963 static void
964 ffelex_finish_statement_ ()
965 {
1662 assert (ffelex_handler_ != NULL);
1663 ffelex_handler_ = (ffelexHandler) (*ffelex_handler_) (ffelex_token_);
1664 assert (ffelex_handler_ != NULL);
1665 /* ここの数行が呼んでいるらしい */
1666 /* すでにめもり */
f/sta.c:
578 static ffelexHandler
579 ffesta_second_ (ffelexToken t)
580 {
1369 return (ffelexHandler) (*next) (t);
1370 }
この return の前ではまだダンプがでないので、
(ffelexHandler) (*next) (t); を２つ書いて落してみる。
(gdb) where
#0 0x15555698968 in __kill () at __kill:2
#1 0x15555698778 in raise ()
#2 0x15555699dbc in abort ()
#3 0x12002cfcc in __eprintf (
string=0x120306168 "%s:%u: failed assertion `%s'\n",
expression=0x120306188 "f/sta.c", line=325,
filename=0x120306228 "ffesta_confirmed_current_") at f/com.c:14648
#4 0x1200828bc in ffesta_save_ (t=0x1204a1750) at f/sta.c:325
#5 0x12007889c in ffelex_send_token_ () at f/lex.c:1656
#6 0x120076c78 in ffelex_finish_statement_ () at f/lex.c:975
#7 0x1200799f4 in ffelex_file_fixed (wf=0x12049ea80, f=0x1204766e0)
at f/lex.c:2283
#8 0x1200fa7b0 in ffe_file (wf=0x12049ea80, f=0x1204766e0) at f/top.c:557
#9 0x120080468 in yyparse () at f/parse.c:74
#10 0x12010047c in compile_file (name=0x11ffff8f6 "test.f") at toplev.c:2529
#11 0x120105894 in main (argc=10, argv=0x11ffff6a8, envp=0x11ffff700)
at toplev.c:4446
(gdb)
f/com.c:
6935
6936 return ffecom_1 (ADDR_EXPR,
6937 build_pointer_type (TREE_TYPE (ffecom_gfrt_[ix])),
6938 ffecom_gfrt_[ix]);
ここではすでにメモリ。
11045 ffecom_call_gfrt (ffecomGfrt ix, tree args)
11046 {
11047 fprintf(stderr,"yamada 3332");
11048 /* すでにめもり*/
6649 s = ffecom_sym_transform_ (s);
6650 fprintf(stderr,"yamada 3006");
まだダンプがでない。
f/std.c:
1403 ffecom_end_transition ();
/* まだだんぷでない */
f/com.c:
8996 lineno = old_lineno;
8997 input_filename = old_input_filename;
8999 /* まだでない*/
9008 return s;
9009 }
9010
f/std.c:
1409 #if FFECOM_TWOPASS
1410 ffestd_stmt_pass_ ();
1411 #endif
1412 /* だんぷでるすでにめもり */
もし改造ができたとしてうまく動くかを考えてみます。
改造は、最初のレジスタの時の設定の内容を覚えておいて
適当な所で書き戻してやるとします。
if(a.gt.0) a=a+b
call sub(a)
end
lds $f1,0($17)
adds $f10,$f1,$f1
sts $f1,16($30)
$L2:
jsr $26,sub_
となっていて、 sub を call するブロックでは
a の定義は行われていません、ただ単にメモリをレジスタ
に書き直してもうまくいかないことがわかります。
(メモ．)入口で 全てレジスタにコピーするように RTL を
書き換えられないか、まだ 元の RTL がレジスタ
であるうちに行う必要がある。
この方法だと、関数 call をしている場合にメモリに
ストアがでないのでまずい。仮引数で 関数 call の
実引数にあらわれない場合はこの最適化を行っても
よい。
いきなり調査に復帰
真面目に gdb を使ってメモリを書き換えている場所を探す
(12047b658 34) (reg/v:SF 70) から
(12047b658 39) (mem:SF (120478718 34) (reg:DI 65)) に変化する場所を探す
gdb /usr/lib/gcc-lib/alphaev5-linux/egcs-2.90.21/f771
(gdb) r test.f -fset-g77-defaults -quiet -dumpbase test.f -da -O4 -version -fversion -o test.s
Breakpoint 8, put_reg_into_stack (function=0x0, reg=0x12047b658,
type=0x1204870b0, promoted_mode=SFmode, decl_mode=SFmode, volatile_p=0)
at function.c:1417
1417 rtx new = 0;
(gdb) stepi 1700
yamada 000001 x/4x 0x12047b658
0x120130844 1440 MEM_VOLATILE_P (reg) = volatile_p;
(gdb) x/4x 0x12047b658
0x12047b658 : 0x080c0034 0x00000000 0x20478718 0x00000001
^^ 0x34 がレジスタを示す
(gdb) stepi 10
0x12013086c 1441 PUT_CODE (reg, MEM);
(gdb) x/4x 0x12047b658
0x12047b658 : 0x000c0034 0x00000000 0x20478718 0x00000001
(gdb) stepi 10
0x120130894 1445 MEM_IN_STRUCT_P (reg) = AGGREGATE_TYPE_P (type);
(gdb) x/4x 0x12047b658
0x12047b658 : 0x000c0039 0x00000000 0x20478718 0x00000001
^^ 0x39 がメモリを示す
ここでレジスタからメモリに 書き変わっている。
(gdb) where
#0 0x120130894 in put_reg_into_stack (function=0x0, reg=0x12047b658,
type=0x1204870b0, promoted_mode=SFmode, decl_mode=SFmode, volatile_p=0)
at function.c:1445
#1 0x120130408 in put_var_into_stack (decl=0x12047b5b8) at function.c:1358
#2 0x12002daa0 in mark_addressable (exp=0x12047b5b8) at f/com.c:14876
#3 0x120021dc0 in ffecom_1 (code=ADDR_EXPR, type=0x1204a2890,
node=0x12047b5b8) at f/com.c:10280
#4 0x12002967c in ffecom_ptr_to_expr (expr=0x1204a19b0) at f/com.c:13080
#5 0x120023748 in ffecom_arg_ptr_to_expr (expr=0x1204a19b0,
length=0x11ffff0c8) at f/com.c:10905
egcs-1.0.1/gcc/function.c:
1351 if (GET_CODE (reg) == REG)
1352 {/* yamada
1353 put_reg_into_stack (function, reg, TREE_TYPE (decl),
1354 promoted_mode, decl_mode, TREE_SIDE_EFFECTS (decl));
1355 */}
1356 else if (GET_CODE (reg) == CONCAT)
でレジスタに割り当てられるようになる。
上にも書いてあるように C ではポインタの問題があるのでこのコメントアウトは
できない。f771 だけに使って cc1 はコメントアウトしないで make したものを
使ってください。
C の場合は、関数にアドレスを渡す変数については問題があるのでできないが
親から渡された変数については自関数で使う分にはレジスタ割り当てをしてかま
わないと思う。
上のコメントアウトだけでは g77 でもうまくいかない。値を復帰する
ロードが出ない場合がある。ちょうど アドレスを渡さないで値を渡す C
の call のような動きになる。
上の部分の少し上
egcs-1.0.1/gcc/function.c:
1331 /* If this variable comes from an outer function,
1332 find that function's saved context. */
1333 if (context != current_function_decl && context != inline_function_decl)
1334 for (function = outer_function_chain; function; function = function->next)
1335 if (function->decl == context)
1336 break;
この値が関数呼び出しの実引数かを調べている、実引数なら function に
アドレスが入る。
そして呼び出された先
egcs-1.0.1/gcc/function.c:
1404 static void
1405 put_reg_into_stack (function, reg, type, promoted_mode, decl_mode, volatile_p)
1406 struct function *function;
1407 rtx reg;
1408 tree type;
1409 enum machine_mode promoted_mode, decl_mode;
1410 int volatile_p;
1411 {
1412 rtx new = 0;
1414 if (function)
1415 {
1416 if (REGNO (reg) < function->max_parm_reg)
1417 new = function->parm_reg_stack_loc[REGNO (reg)];
1418 if (new == 0)
1419 new = assign_outer_stack_local (decl_mode, GET_MODE_SIZE (decl_mode),
1420 0, function);
こちら側が実引数
1421 }
1422 else
1423 {
1424 if (REGNO (reg) < max_parm_reg)
1425 new = parm_reg_stack_loc[REGNO (reg)];
1426 if (new == 0)
1427 new = assign_stack_local (decl_mode, GET_MODE_SIZE (decl_mode), 0);
1428 }
1429
こちら側が仮引数の処理をしている。
目次に戻る
g77,f2c+gcc,f2c+egcs と FORTAN 処理系の種類も充実してきたので
性能に影響する DO ループ の添字計算の出力をまた調べてみました。
FORTRAN のデータ宣言には データ割り当ての観点からいって COMMON 文
に現れるもの仮引数に現れるものローカルに現れるものがあります。
さらに f2c を通す場合は -a オプションの違いによってローカルでも
static になる場合(-a なし)とならない場合(-a)があります、static と
auto(-a) と区別します。
この４つに配列と添字がそれぞれ割り当てられた状態でループが構成さ
れる可能性があります。
テストプログラム
c subroutine sub(a,b,i)
c subroutine sub(a,b)
subroutine sub()
real a(100),b(100)
common/d/a,b
c common/c/i
do i=1,100 <- この i を添字といいます
a(i)=b(i)
enddo
call sss(a,b)
end
このプログラムの配列と添字の宣言をいろいろ変えて調べました。
数字は DO ループ中の命令数です。(もちろん少ない方が望ましい)
配列 添字 g77 f2c+gcc f2c+egcs
(-O4) (-O4) (-O4)
static static 15 13 10
static 仮引数 17 14 11
static COMMON 17 14 10
auto auto -- 14 8
auto 仮引数 -- 18 12
auto COMMON -- 18 12
仮引数 static 11 11 12
仮引数 auto -- 7 7
仮引数 仮引数 13 12 12
仮引数 COMMON 13 12 12
COMMON static 11 13 10
COMMON auto -- 10 6
COMMON 仮引数 13 14 11
COMMON COMMON 13 14 10
-- は、その組合せがないことを示します。
コーディング、チューニング作業の参考にしてください。
目次に戻る
f2c のソースを少し読んでみました
vax.c
Parameter adjustments などのコメントを出している
do_format()->procode()->prolog()
format.c
ここでループしていろんな文を出している。
do_format()
再帰呼び出しをしながら do の内部構造とかを
出している。token という構造になっているようだ。
start_formatting()
ここで最初に do_format()を呼び出す
do_p1_head()
サブルーチンの先頭の部分を出す
do_p1_head()->list_decls()
list_decls()
配列とかのを出してるみたい
output.c
out_for()
for(... を出す
proc.c: ?_dim? とかの出力もしている
newproc()->endproc()
endproc()
start_formatting() を呼び出す
文法checkもまだやってる
endproc()->dobss()
dobss()
local data の chack とかしてる
endproc()->epicode()
epicode()
たいしたことしてない
ここから先は普通のプログラムになってないので追跡できない。
ちょっとやり方を変える ctlstack が DO loop BLOCK IF の nest を
示しているのでそれを追跡する
init.c と exec.c で参照更新している。
init.c
fileinit(Void) でインクリメント
procinit(Void) でデクリメント
main.c
main()->fileinit(Void)
main()->procinit(Void)
main()->set_tmp_names()
最初にソースをたどってツリーを作って最後にツリーをたどって C
ソースを出しているようだ。
sysdep.c
set_tmp_names() コンパイル中にワークで使うファイルの確保？
ｆ２ｃ のオブジェクト調査f2c.eucもあります。
ここでは、FORTRANのソースやf2c の出力の C ソースに少し手を加えて 性能を出してみます。BLAS の DGEMM を単純化したソースを例に使います。
もとソース
SUBROUTINE DGEMM ( M, N, K, A, LDA, B, C )
INTEGER M, N, K, LDA
DOUBLE PRECISION A( LDA, * ), B( LDA, * ), C( LDA, * )
INTEGER I, J, L
DOUBLE PRECISION TEMP
DO J = 1, N
DO L = 1, K
TEMP = -B( L, J )
DO I = 1, M
C( I, J ) = C( I, J ) + TEMP*A(I,L)
ENDDO
ENDDO
ENDDO
RETURN
END
まず unroll をします unroll は最内側などを複数段するよりも
すべての DO ループを少しずつ unroll した方がいいようです。
SUBROUTINE DGEMM ( M, N, K, A, LDA, B, C )
INTEGER M, N, K, LDA
DOUBLE PRECISION A( LDA, * ), B( LDA, * ), C( LDA, * )
INTEGER I, J, L
DOUBLE PRECISION bl0j0,bl0j1,bl0j2,bl0j3
DOUBLE PRECISION bl1j0,bl1j1,bl1j2,bl1j3
DOUBLE PRECISION bl2j0,bl2j1,bl2j2,bl2j3
DOUBLE PRECISION bl3j0,bl3j1,bl3j2,bl3j3
DOUBLE PRECISION ai0l0,ai0l1,ai0l2,ai0l3
DOUBLE PRECISION ai1l0,ai1l1,ai1l2,ai1l3
DOUBLE PRECISION ai2l0,ai2l1,ai2l2,ai2l3
DOUBLE PRECISION ai3l0,ai3l1,ai3l2,ai3l3
DO J = 1, N,4
DO L = 1, K,4
bl0j0 = B(L+0,J+0)
bl1j0 = B(L+1,J+0)
bl2j0 = B(L+2,J+0)
bl3j0 = B(L+3,J+0)
bl0j1 = B(L+0,J+1)
bl1j1 = B(L+1,J+1)
bl2j1 = B(L+2,J+1)
bl3j1 = B(L+3,J+1)
bl0j2 = B(L+0,J+2)
bl1j2 = B(L+1,J+2)
bl2j2 = B(L+2,J+2)
bl3j2 = B(L+3,J+2)
bl0j3 = B(L+0,J+3)
bl1j3 = B(L+1,J+3)
bl2j3 = B(L+2,J+3)
bl3j3 = B(L+3,J+3)
DO I = 1, M,4
ai0l0 = a(i+0,l+0)
ai1l0 = a(i+1,l+0)
ai2l0 = a(i+2,l+0)
ai3l0 = a(i+3,l+0)
ai0l1 = a(i+0,l+1)
ai1l1 = a(i+1,l+1)
ai2l1 = a(i+2,l+1)
ai3l1 = a(i+3,l+1)
ai0l2 = a(i+0,l+2)
ai1l2 = a(i+1,l+2)
ai2l2 = a(i+2,l+2)
ai3l2 = a(i+3,l+2)
ai0l3 = a(i+0,l+3)
ai1l3 = a(i+1,l+3)
ai2l3 = a(i+2,l+3)
ai3l3 = a(i+3,l+3)
C(I+0,J+0) = C(I+0,J+0)
1 - ( bl0j0 * ai0l0
1 + bl1j0 * ai0l1
1 + bl2j0 * ai0l2
1 + bl3j0 * ai0l3 )
C(I+1,J+0) = C(I+1,J+0)
1 - ( bl0j0 * ai1l0
1 + bl1j0 * ai1l1
1 + bl2j0 * ai1l2
1 + bl3j0 * ai1l3 )
C(I+2,J+0) = C(I+2,J+0)
1 - ( bl0j0 * ai2l0
1 + bl1j0 * ai2l1
1 + bl2j0 * ai2l2
1 + bl3j0 * ai2l3 )
C(I+3,J+0) = C(I+3,J+0)
1 - ( bl0j0 * ai3l0
1 + bl1j0 * ai3l1
1 + bl2j0 * ai3l2
1 + bl3j0 * ai3l3 )
C(I+0,J+1) = C(I+0,J+1)
1 - ( bl0j1 * ai0l0
1 + bl1j1 * ai0l1
1 + bl2j1 * ai0l2
1 + bl3j1 * ai0l3 )
C(I+1,J+1) = C(I+1,J+1)
1 - ( bl0j1 * ai1l0
1 + bl1j1 * ai1l1
1 + bl2j1 * ai1l2
1 + bl3j1 * ai1l3 )
C(I+2,J+1) = C(I+2,J+1)
1 - ( bl0j1 * ai2l0
1 + bl1j1 * ai2l1
1 + bl2j1 * ai2l2
1 + bl3j1 * ai2l3 )
C(I+3,J+1) = C(I+3,J+1)
1 - ( bl0j1 * ai3l0
1 + bl1j1 * ai3l1
1 + bl2j1 * ai3l2
1 + bl3j1 * ai3l3 )
C(I+0,J+2) = C(I+0,J+2)
1 - ( bl0j2 * ai0l0
1 + bl1j2 * ai0l1
1 + bl2j2 * ai0l2
1 + bl3j2 * ai0l3 )
C(I+1,J+2) = C(I+1,J+2)
1 - ( bl0j2 * ai1l0
1 + bl1j2 * ai1l1
1 + bl2j2 * ai1l2
1 + bl3j2 * ai1l3 )
C(I+2,J+2) = C(I+2,J+2)
1 - ( bl0j2 * ai2l0
1 + bl1j2 * ai2l1
1 + bl2j2 * ai2l2
1 + bl3j2 * ai2l3 )
C(I+3,J+2) = C(I+3,J+2)
1 - ( bl0j2 * ai3l0
1 + bl1j2 * ai3l1
1 + bl2j2 * ai3l2
1 + bl3j2 * ai3l3 )
C(I+0,J+3) = C(I+0,J+3)
1 - ( bl0j3 * ai0l0
1 + bl1j3 * ai0l1
1 + bl2j3 * ai0l2
1 + bl3j3 * ai0l3 )
C(I+1,J+3) = C(I+1,J+3)
1 - ( bl0j3 * ai1l0
1 + bl1j3 * ai2l1
1 + bl2j3 * ai2l2
1 + bl3j3 * ai2l3 )
C(I+3,J+3) = C(I+3,J+3)
1 - ( bl0j3 * ai3l0
1 + bl1j3 * ai3l1
1 + bl2j3 * ai3l2
1 + bl3j3 * ai3l3 )
ENDDO
ENDDO
ENDDO
RETURN
END
gcc は、配列の引用では同じ要素でも共通化されない為、一旦変数に
代入するように書いてやります。
次に f2c に通します -a オプションを付けて変数が stack にわりあて
られるようにします。
f2c の出力は、
i__3 = *m;
for (i = 1; i <= i__3; i += 4) {
ai0l0 = a[i + l * a_dim1];
ai1l0 = a[i + 1 + l * a_dim1];
ai2l0 = a[i + 2 + l * a_dim1];
ai3l0 = a[i + 3 + l * a_dim1];
ai0l1 = a[i + (l + 1) * a_dim1];
ai1l1 = a[i + 1 + (l + 1) * a_dim1];
ai2l1 = a[i + 2 + (l + 1) * a_dim1];
..........
c[i + j * c_dim1] -= bl0j0 * ai0l0 + bl1j0 * ai0l1 + bl2j0 *
ai0l2 + bl3j0 * ai0l3;
c[i + 1 + j * c_dim1] -= bl0j0 * ai1l0 + bl1j0 * ai1l1 +
bl2j0 * ai1l2 + bl3j0 * ai1l3;
c[i + 2 + j * c_dim1] -= bl0j0 * ai2l0 + bl1j0 * ai2l1 +
bl2j0 * ai2l2 + bl3j0 * ai2l3;
c[i + 3 + j * c_dim1] -= bl0j0 * ai3l0 + bl1j0 * ai3l1 +
bl2j0 * ai3l2 + bl3j0 * ai3l3;
c[i + (j + 1) * c_dim1] -= bl0j1 * ai0l0 + bl1j1 * ai0l1 +
bl2j1 * ai0l2 + bl3j1 * ai0l3;
c[i + 1 + (j + 1) * c_dim1] -= bl0j1 * ai1l0 + bl1j1 * ai1l1
+ bl2j1 * ai1l2 + bl3j1 * ai1l3;
のような感じです。
この c[ ] という配列の参照の仕方は添え字の計算が沢山でてしまって
性能がでないので ptr を使うように書き換えてやります。
doublereal *pai0l0,*pai0l1,*pai0l2,*pai0l3;
doublereal *pci0j0,*pci0j1,*pci0j2,*pci0j3;
doublereal *pci0j0s,*pci0j1s,*pci0j2s,*pci0j3s;
doublereal *pbl0j0,*pbl0j1,*pbl0j2,*pbl0j3;
doublereal *pbl0j0s,*pbl0j1s,*pbl0j2s,*pbl0j3s;
doublereal *ppai0l0;
..........
pci0j0s = &c[ii+ j * c_dim1];
pci0j1s = &c[ii+ (j + 1) * c_dim1];
pci0j2s = &c[ii+ (j + 2) * c_dim1];
pci0j3s = &c[ii+ (j + 3) * c_dim1];
pbl0j0 = &b[1 + j * b_dim1];
..........
i__2 = *k;
for (l = 1; l <= i__2; l += 4) {
bl0j0 = *pbl0j0++;
bl1j0 = *pbl0j0++;
bl2j0 = *pbl0j0++;
bl3j0 = *pbl0j0++;
bl0j1 = *pbl0j1++;
..........
pai0l0 =ppai0l0;ppai0l0+=a_dim1;
pai0l1 =ppai0l0;ppai0l0+=a_dim1;
pai0l2 =ppai0l0;ppai0l0+=a_dim1;
pai0l3 =ppai0l0;ppai0l0+=a_dim1;
..........
pci0j0 = pci0j0s;
pci0j1 = pci0j1s;
pci0j2 = pci0j2s;
pci0j3 = pci0j3s;
for (i = ii; i <= ii+15; i += 4) {
ai0l0 = *pai0l0++;
ai0l1 = *pai0l1++;
ai0l2 = *pai0l2++;
ai0l3 = *pai0l3++;
*pci0j0++ -=
bl0j0 * ai0l0
+ bl1j0 * ai0l1
+ bl2j0 * ai0l2
+ bl3j0 * ai0l3;
*pci0j1++ -=
bl0j1 * ai0l0
+ bl1j1 * ai0l1
+ bl2j1 * ai0l2
+ bl3j1 * ai0l3;
これでかなり奇麗なアセンブラコードを出力することができ、
性能も良くなります。是非おためしください。
目次に戻る
linux/alpha で使える、フーリーなオプティマイズプリプロセッサの
SUIF というものがあります。オプティマイズプリプロセッサというのは
ソースを変更して最適化を行ってくれるものです。
SUIF のソースのありか
をダウンロードして、
後藤さんの記事
に従って make;install します。
性能は f2c+gcc 以上 g77 以下のようです。
alpha は非常に高いピーク性能を持っていますが、それを発揮させるのは 容易ではありません。ここでは g77 の出力のアセンブラに手をいれて alpha が確かにピーク性能近くで動作することを確認してみましょう。
まず c で時間測定ルーチンを用意します。
sec.c:
float second_()
{
#include
return ((float)((float)clock()/(float)1000000));
}
このルーチンで実行時間が秒で得られます。(1000000 の部分はお
使いのシステムにあわせて変更してください。)
次に改造の元となるプログラムを FORTRAN で作ります。
do j=1,10
t1=second()
do k=1,1000000
i=0
a=0.0
call sub(i,a)
enddo
t2=second()
write(*,*) t2-t1
enddo
end
subroutine sub(i,a)
i=i+1
a=a+1.0
end
サブルーチン SUB を 100 万回 call してその時間をプリントするプ
ログラムになっています。
このプログラムを g77 -O4 -S でコンパイルして
i=i+1
a=a+1.0
に相当する部分の命令を 1000 個の命令で置き換えてやります。
そうして実行して時間が１秒となったとすると 1 Gmips(ギガミップス
ギガは 1000000000)ということになります。
上の２行に相当する部分のアセンブラは
105 lda $1,$C38
106 lds $f1,0($17)
107 lds $f10,0($1)
108 ldl $1,0($16)
109 adds $f1,$f10,$f1
110 addq $1,1,$1
111 stl $1,0($16)
112 sts $f1,0($17)
です、この部分を
nop |
nop |
fnop | x 250回
fnop |
で置き換えてやります。nop と fnop を使うのは nop は整数演算器
fnop は浮動小数点演算器を使うからです。
このプログラムを私のEB164(21164 300Mhz 1200 mips)で実行すると
0.88 秒で 1136 mips という結果がでました。
目次に戻る
linux/alpha に LAPACK を利用して、linpack TPP を
作ってみました。
dgemm.f という行列積ルーチンの性能が鍵です。
linux/alpha で X86_S3 をコンパイルするには、
ftp://ftp.iij.ad.jp/pub/X/XFree86/XFree86/3.3.1/source
から、src のつく３つのファイルをロードしてきて展開し、
cd xc;make World を実行。
終了後 cd programs/Xserver;make CDEBUGFLAGS="-O "
でサーバを構築しなおします。(情報提供：後藤さん)
floor 関数が 遅いので少し調べてみました。
double floor(x)
double x;
{
double t;
t=(x+4503599627370496.0)-4503599627370496.0;
return t;
}
としてオブジェクトを出力し、加算に
addt/c $f16,$f0,$f16
として切り捨てをさせると上手く答えがあうようです。
目次に戻る
GNU の多倍長計算ライブラリ gmp を使ったプログラムです。 御試しください。
円周率計算プログラム pai.euc
ルーカステストプログラム prime.euc
最近、新しい Alpha のＭＬが始まりました。
http://www.alpha-usr.gr.jp
です。(2009年現在 HP は消滅しているようです。主催者の方おつかれさまでした。)