小さいプログラムで試してみる。
いきなり大きなプログラムをつくるのではなくて、逐次的に作っていく。
.align 2 sum: .word 0
レジスタに答えが求められた後、sw (store word) 命令で sum 番地に保存す る。後は、サンプル・プログラムに含まれている syscall の働きにより結果 が表示される。(この課題では、syscall の部分は単にそのまま利用するだけ でよい。)
lw 命令や sw 命令は、プリントにあるように、本来は次の形式でしか書けな い。
lw $8, 100($2) sw $8, 100($2)しかし、実際には xspim のアセンブリ言語処理系の働きで、直接メモリ番地 (ラベル)を指定して、lw 命令や sw 命令が使えるように見える。実際には、 2命令に展開される。
ソース・プログラム: lw $t0, sum sw $t0, sum load されたプログラム: [0x00400020] 0x3c011001 lui $1, 4097 [sum] ; 5: lw $t0, sum [0x00400024] 0x8c280004 lw $8, 4($1) [sum] [0x00400028] 0x3c011001 lui $1, 4097 [sum] ; 6: sw $t0, sum [0x0040002c] 0xac280004 sw $8, 4($1) [sum]
見えない所でレジスタ $1
が壊されている。アセンブリ言語で
プログラムを書く時には、 $1
を使わないようにする。
syscall (システム・コール)が何なのかについては、詳しくは3年生以上の科 目、システムプログラミング、オペレーティングシステムなどで出てくる。機 械語序論の範囲では、「システムコールという便利な仕掛けのものがある」と いう程度の理解でもよい。3年生以上では、「ではどうすればシステムコール という便利な仕掛けを実現することができるか」ということも考える必要があ る。
システムコールと同じことが機械語1命令1命令にも言える。3年生以上では、 ハードウェアで機械語命令を実現するにはどうすればよいかを考える。
プリント2ページ。swap: の最後の所、1行足りない。
lw $31,0($29) # この行が抜けている lw $5,4($29) addi $29,$29,8 jr $31関数の入口の sw と出口の lw は対応している。lw の順番は、どちらが先で もよい。sw と同じ順番でやってもよいし、ちょうど逆順にやってもよい。 (ランダムに入れ替えも動くが、プログラムが読みにくくなるのでやらないように。)
プリント2ページ。C言語のプログラムの一番最後の return が違う。
誤: return; 正: return( v );ラベルがついているもの全てが関数(手続き)ではない。ループや if 文を作 るためのラベルもある。
関数(手続き)の特徴は、次の通りである。
プログラムを作る時には、レジスタの使い方を決める。関数の中では、あるレ ジスタは、自由に使ってもよい(内容を書き換えてよい)とし、別のレジスタ は関数呼出しの前後で値を保持しなければならないと定める。
関数呼出しの前後で保持すべきレジスタを関数の中で使う時には、関数の先頭 で元の値をスタックに保存し、関数の出口でスタックから元の値を回復する。
逆に、関数の中で自由に使って良いとされているレジスタに入っている値は、 関数呼出し(jal)をすると、返ってきた時にはその値は失われているものと覚 悟する。大事なデータは、保持されるレジスタに入れておくか、自分自身でス タックに保存する。
MIPS 標準では、次のようになっている(「XSPIMシミュレータ」という プリントの11ページ)
この授業では、課題の本質が重視されるので、標準的な約束に従うことの優先 度は低い。
決まり文句($31 と3つのレジスタを保存する)
関数の入口 .text .align 2 .globl func func: addi $29,$29,-16 lw $31,0($29) lw $s0,4($29) lw $s1,8($29) lw $s2,12($29) ... 関数の出口 sw $31,0($29) sw $s0,4($29) sw $s1,8($29) sw $s2,12($29) addi $29,$29,16 jr $31
t0 を保存・回復しても、規約には違反しない。
(関数の中で)レジスタの内容を保存・回復しないことを、「レジスタの内容 を壊す」という。逆に、「レジスタの内容を(関数呼出しで)壊されないように、 入口でレジスタの内容をスタックに保存して、出口で回復する」という。
XSPIM で最初に0が入っているからといって、常に0が入っているとは限らない。
詳しくは、教科書下巻の付録「A.6手続き呼出し規約」を参照のこと。
ある関数の中で、自分自身を呼び出す時に再帰呼出しという。機械語でプログラムを書く時には、再帰呼出しであっても、他の関数の呼出し であっても、方法はまったく同じである。
直接再帰呼出しをしていないように見えても、間接的に再帰呼出しになってい ることもある。f()→g()→h()→f() のように戻ってくることもある。
f() { g() } g() { h() } h() { f() }kikaigo4 の課題では、出題者の意図としては再帰呼出しで fact を実行する。 プリントのC言語で書かれた例では、fact の中にはif 文が1つ、関数呼出し が1つ、掛け算が1つがあるだけである。つまり、ループは使わないで書いて 欲しいというのが、本来の意図である。
ただし、この課題でも、特に「再帰」を意識しなくても、普通に関数呼出しと してプログラムを書けば完成するはずである。
---------------------------------------------------------------------- fact( n ) { if( n != 1 ) goto label1; v0 = 1 ; return( v0 ); label1: tmp = n ; n-- ; v0 = fact( n ); v0 = v0 * tmp; return( v0 ); } ---------------------------------------------------------------------- fact: a0 が 1 かどうか調べる branch-if-1でない, label1 1をv0にセットする returnの処理 label1: a0 を壊れない場所に保存 a0 を減らす jar fact # (再帰)呼出し 答え(v0) と保存していた a0 を掛けて、答えを v0 に入れる returnの処理C言語で if( n == 0 ) のような条件判定は、機械語では、if( n!=0 ) goto .... のように、条件をひっくり返して、goto と組み合わせるとわかりやすい。
---------------------------------------------------------------------- if( n == 0 ) { 成立時の処理; } ---------------------------------------------------------------------- if( n != 1 ) goto label1; 成立時の処理; label1: ---------------------------------------------------------------------- n != 1 か調べる 条件成立なら label1へbranch 成立時の処理; label1: ----------------------------------------------------------------------else があれば、goto を付ける。
---------------------------------------------------------------------- if( n == 0 ) { 成立時の処理; } else { 非成立時の処理; } ---------------------------------------------------------------------- if( n != 1 ) goto label1; 成立時の処理; goto label2 label1: 非成立時の処理; label2: ----------------------------------------------------------------------for 文も、if 文と goto 文で書くとよい。
for( i=0 ; i<10; i++ ) { ループの中身; } i = 0 ; begin: if( i >= 10 ) goto out; ループの中身; i++ ; goto begin; out:機械語言語だと、for 文より do-while の方が考えやすいことが多い。
i = 0 ; do { ループの中身; i++ ; } while( i<10 ) i = 0 ; begin: ループの中身; i++ ; if( i < 10 ) goto begin;
プリント2ページ。print_newline で 最初の addi と最後の addi の値が食 い違っている。
print_newline: addi $29,$29,-12 # この行は正しい .... addi $29,$29,8 # この行は間違い。8 ではなくて 12 にすべき。 jr $31その他に、例題で括弧が余計についている部分がいくつかある。
プリント2ページ。C言語のプログラムの一番最後の return が違う。
誤: sw $2,8,($29)) 正: sw $2,8,($29)
1文字を表示するには、次のファイルにある putchar 関数を使ってもよい。
~yas/kikaigo/putchar.s
sb (store byte) は、その番地へ 1 バイトだけ書込む。 sw (store word) は、その番地へ 1 ワード ( 4 バイト) 書込む。
4 番の syscall は、「文字列」を表示するためのシステムコールである。文 字列の最後には、終わりの印の 0 が必要である。
プリントの3ページの例は、sll を巧みに使って、終わりの印の 0 も作って いる。
sb は、(CPU によっては) sw より遅い。
(1) 2ページの Subject: は、kikaigo (最初のgはk)
(2) 3ページの1文字をプリントする方法。
中間レジスタとして $1 を使うと、アセンブラ(xspim)がエラーを出す。$1 以 外の使われていないレジスタを使うとよい。
大きな問題は、いくつかの小さな問題に分解して考えるとよい。 小さな問題は、解きやすいし、他への応用も広い。
kadai6 では、次のような問題に分解できる。
キーボードからデータを読込む。
x = read_int(); /* syscall */32ビットの数のうち、左から順次4ビットずつ取り出す。
for( n=28 ; n>=0 ; n-=4 ) { bits =( x >> n )&15 ; .... }4倍してもよい。
for( i=8 ; i>=0 ; i-- ) { n = i * 4 ; bits =( x >> n )&15 ; .... }ループの変数は、0 から増やす方向でまわしてもよい。
for( i=0 ; i<8 ; ++ ) { n = 28 - i * 4 ; bits =( x >> n )&15 ; .... }
if( bits < 10 ) c = ... ; else c = ... ;
画面に出力する。
putchar( c ); /* syscall */全てのコンピュータのプログラムは、(入出力を除くと)レジスタやメモリに 入っているビットパタン(01のビットの並び)を元にして別のビットパタンを 作り出すものである。
ビットパタンを変換するためには、and, or, not, xor のようなビット演算を 使うとは限らない。add/sub/mul/div を使うこともある。
全てのビットパタンの変換は、and, or, not の3つだけで実現できる。
コンピュータで処理させるためには、データをビットパタンに変換する必要が ある。どんなデータであっても、ビットパタンで変換できれば、コンピュータ で扱える。ビットパタンに変換できないものは、コンピュータであつかえない。
数をコンピュータで扱うには、数を2進数で「表記」した時のパタンをそのま ま使う。ただし、正の整数で小さいもの(0から232-1の範囲内に 入る)の場合である。小数、負の数、この範囲に入らないような大きな正の整 数は、別のビットパタンでの表現方法を使う。
文字をコンピュータで扱うには、文字とビットパタン(数)との対応表を作る。 対応のさせかたを、文字の符号化(コード化)、対応表を 文字コード表という。
対応表には、いくつも種類がある。
xspim では、キーボードや画面で入出力できるのは、本来は、文字だけである。 コンピュータとキーボード、コンピュータと画面の間は、文字コードが流れる。
+−−−−−−+ キーボード →→→→ |コンピュータ| 画面 ←←←← +−−−−−−+しかし、システムコールの read_int() [1] や文字(0,1,2,3,4,5,6,7,8,9) を読込み、それが10進数表記だと思って数(32ビット)に変換する機能を 含んでいる。逆に、print_int() [5] は、数(32ビット)を、10進数表記 の文字の並びに変換した上で、画面に出離よくする機能を持っている。
この課題では、print_int() [5] の内部でやっているように、数(32ビット) を文字の並び(次から次へと文字)に変換する。ただし、10進数の表記では なくて、16進数の表記に変換する。
実際のキーボードと画面の関係は、もう少し複雑である。キーボードは、文字 ではなくて、「どのキーか」という番号(keycode, 0..255)と、「シフトや caps が押されていたか」を返す。 画面は、ビットマップディスプレイの場合は、メモリ(フレームバッファと呼 ばれる特殊なメモリ)中に1点を数ビット(1ビットから24ビット)で表す ようにしてデータを作る。
1時間目の講義の時に唾かつたプログラム。
Java 言語の文字型(char)は、整数型(int)ではないので、整数型に使える演算 は、文字型には使えない。Java の内部的には、char は16 ビットで、文字コー ドは、Unicode を使うとされている。
1ページ目、la $12,1 は、ループの中へ。addui $12,412,1 は、このプログ ラムでは不要(ポインタを使う場合には必要)。
addu $10,$0,$0 # $10: s addu $11,$0,$0 # $10: i li $8,10 loop: la $12,a # lbまでの3行で a[i] のレジスタへの読み込み addu $12,$12,$11 lb $9,0($12) addu $10,$10,$9 addi $11,$11,1 slt $2,$11,$8 bne $2,$0,loop #$10: resultmain を含む、動く例が、~yas/kikaigo/sum-char-array.s にある。 元のC言語のプログラムは、~yas/kikaigo/sum-char-array-c.c にある。
2ページ、setp3 の所で、数(10でわった余りなので、0から9)をdecimal[?] に保存しているが、保存するまえに、48 (0x30, '0') を足して、数を文字コードに変換した方がよい。
配列の後ろから使うと、逆順に出ない。
char decimal[12] = { 0,0,0,0,0,0,0,0,0,0,0,0 }; main() { int i ; int a,b,c ; char ch ; a = 123 ; for( i=9 ; i>=0 ; i-- ) { b = a / 10 ; c = a % 10 ; ch = c + '0' ; decimal[i] = ch ; a = b ; } print_string( decimal ); } print_string( char *s ) { printf("%s",s); }
C言語の int は、4 バイト(32ビット)なので、 1バイトの整数型 char の方が機械語のプログラ ムに近い。
char a[10]; char *pi; char s; s=0;機械語のプログラムの例で、動作確認後のものが、次のファイルに入っている。
~yas/kikaigo/sum-char-array-p.s
(ポインタを使うもの)
lb $9,0($12) # $9 = *pi
先週の例のプログラムと比較してみるとよい。
~yas/kikaigo/sum-char-array.s
(配列を使うもの)
la $12,a # lbまでの3行で $9 = a[$11] addu $12,$12,$11 lb $9,0($12)
プログラムを、プリントにあるように3つの部分に分割して作る。計算する部 分を作る時には、入力部分を飛ばして、メモリ中にあらかじめセットしたデー タを使うと楽である。
(1)の入力部分の動作確認は、xspim の画面のData Segment の所で、 0x10010000 番地あたりを見るとわかる。 入力が終わった辺りで、 HM_Ref(`xspim.html#xspim',ブレークポイントを設定すると便利である。)
課題としては、1バイト(8ビット)の整数で扱えるものでもよい。つまり、 -128から+127までの範囲の数だけを取れるもので考えてもよい。4バイト(32 ビット)の整数(-2147483648 から 2147483647)が扱えるようにするには、次の 点に気を付ける。
a: .word 0,0,0,0,0,0,0,0,0,0あるいは、.space で 40 バイト確保する。
a: .space 40
(1) の lw で、装置の状態を調べているのは、前の出力が完了しているかどう かを調べている。1文字しか出力しないならば、プログラムの実行を開始した 時点で必ず出力可能になっいるはずなので、状態を調べなくても動作する。し かし、複数文字を出力することを考えると、前の出力が終わるまで待つ必要が ある。
次のファイルに、画面に出力するだけのプログラムがある。これは、基本的にはプリントで配布したものと同じものである。今日の課題で、 print_char は、このプログラムのloop の部分と、sw $13,0($11) の部分を変 形して使うとよい。loop2 は、出力の遅れを補うものなので、main の最後に 入れるとよい。
print_char から先に完成させるとよい。その時には、次のような main を使うとよい。
# jal read_char li $4,'A' jal print_charread_char の代りに、プログラムの中でデータを与えて print_char を呼ぶ。
read_char は、print_char と似たような構造を持つ。違いは、レジスタの番 地と、lw/sw の方向である。read は、lw, print は、sw になる部分がある。
この課題の方法で1文字入力しても、画面にはエコーバックされない。画面に 同じ文字が出力されたとすると、それは、自分自身のプログラムの中で出力し ているからである。
プログラムが動作していることを確認するには、次のようにしてみるとよい。
jal read_char addi $4,$4,1 jal print_charこれで、打ち込んだキーとは別の文字が出力されるはずである。
このように、キーが打ち込まれた時、同じ文字を画面にプリントすることを、 エコーバックという。kterm などの端末でエコーバックされるのは、 エコーバックを行うプログラムが動作しているからである。 パスワードの入力の時や、エディタを実行したときなど、エコーバックしない 動作もさせられることと比較するとわかる。
情報学類のシステムでは、標準で -mapped_io オプションが付けられている。 マニュアルの記述と異なり、このオプションを自分で付けなくても今日の課題 は動作する。% cat /usr/local/bin/xspim #!/bin/sh exec /usr/local2/bin/xspim -mapped_io "$@" adonis1[~/kikaigo] 115% %-mapped_io を付けたくない時には、次のようにする。
% /usr/local2/bin/xspim args関数呼出しの方法は、1月8日、1月15日のプリントや、 WWW資料も 参考にする。
保存すべきレジスタ、破壊してもよいレジスタをきちんと決める。 この課題では、MIPS 標準に従う必要はない。
値を返すレジスタは、保存しない。
関数呼出し jal 命令では、$31 も破壊される点に注意する。 main関数では、$31 を保存・回復した方がよい。
関数の中で関数呼出しをしないなら、$31 は破壊されない(保存/回復しなく てもよい)。こういう最適化を、leaf node optimization という。 この課題(print_char, read_char)では、この最適化が可能である。 意識して行うならば、この最適化を行ってもよい。
la $12,a sll $13,$11,2 # $11 は添字 addu $12,$12,$13 sw $??,0($12) または lw $??,0($12)int は、4 バイトなので、C言語で 1 を増やす (++) 操作をするには4増や す。
C言語: int *p ; p++ ;
アセンブリ言語: addi $11,$11,4 # $11: p配列の最後の番地の計算
C言語: int array[10]; int *p ; p = &array[10];
アセンブリ言語: ... la $11,array+40 # $11:p ... .data .align 2 array: .word 0,0,0,0,0,0,0,0,0,00に初期化された配列ならば、.byte, .word で 0 と書く方法の他に、.space も使える。
array: .space 40次とだいたい同じ。
array: .word 0,0,0,0,0,0,0,0,0,0.word の場合、オブジェクト・コードにその大きさのデータが出力されるが、. space では出力されず、プログラムがメモリに読込まれる時にオペレーティン グ・システムによって初期化される。 C言語
int array[10] ; /* .space 40 */ int array[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } ; /* .word 0,0,0,0,0,0,0,0,0,0 */