1. No category

「情報科学基礎実験」
計算機システム演習 (アセンブリ入門)
第3回 (全5回)
2014年1月22日(金)
石川研 助教 ゲローフィ　バリ
[email protected]
(Based on Kazuki Yoshizoe’s slides)
質問受付
[email protected]
不正行為について
•  もちろん、他の講義と同様禁止
–  不正行為はハイリスク・ノーリターン
•  参考にした資料などあれば、明示すること
•  さらに、本演習特有の問題として
–  コンパイラの出力をそのまま提出するのは禁止
•  ほぼ分かります
•  分からなくなるくらいまで改変できればアセンブリ
でプログラムが書けるのと同じこと
2
注意書き
•  アセンブリのマニュアルを持参すること
–  以下にある
•  Power ISA Documentation (2.05を使います)
–  http://www.power.org/resources/reading/
–  そのために csp にログインして課題を実行する
–  ログインできないときは早急に連絡するように
–  その他、問題が起きたと思ったら早急に連絡
•  プロセスが止まらない等
•  他の演習と同様、以下に資料などを掲載する
–  http://hagi.is.s.u-tokyo.ac.jp/kisojikken/
•  課題を提出、質問、連絡なども、同様に以下で受
け付ける
–  [email protected]
3
前回までのフォロー
•  %r1 などは、汎用レジスタ(GPR)に対応する
–  %r1 はマニュアルの GPR1, %r31は GPR31
–  本当は、 add 1 2 3 で GPR1 = GPR2+GPR3
•  人間にとって分かりやすくするために、レジスタの頭に %r を
つけている ( -mregnames )
•  マニュアルは紙媒体とPDFの使い分けを推奨
–  検索等のために原典をダウンロードしましょう
–  PowerPC Architecture Book, Version 2.05
•  http://www.power.org/resources/reading/
•  csp (Power7) は 64bitアーキテクチャであることに
注意
–  sizeof(long) とか sizeof(void *) とかを確認すること
•  命令の書き方について詳しい説明を追加
–  次ページ以降 (ページ数などは ver. 2.05 の物)
4
add命令 詳細
XO-form: 命令の形式。32bit の使い方の種類
p.17 (1.6.12 XO-Form)
RT: target register. 代入される汎用レジスタ
RA: 被演算子となる又は代入されるレジスタ
RB: 被演算子となる汎用レジスタ
OE: XERレジスタに OV, SV bit を立てるか
Rc: Record bit. Condition Register に演算結
果に応じたフラグを立てるか
p.20 (1.6.24 Instruction Fields)
例えば、オーバーフローを検知して、フラグを立てる加算命令を書くとする。
レジスタ3にレジスタ3とレジスタ4を足した物を代入するとすると、
・ (OE=1, Rc=1) の命令なので、使う命令は addo. (末尾のピリオドに注意)
・ RT は 3, RA は例えば 3, RB は例えば 4
なので、 addo. RT,RA,RB の通りに、
addo. 3, 3, 4
と書けばよい。
5
無条件分岐 詳細 (1/2)
数値は基本的には10進数。ただし、0bnnnn
は2進数、0xnnnn は16進数。
​𝑋↓𝑝 : X の p番目の bit
​𝑋↓𝑝:𝑞 : X の pからq番目までの bit列
​𝑋↓𝑝,𝑞, … : X の p番目, q番目, … の bit列
p.4∼ (1.3.2 Notation)
EXTS(x):xの符号を保って左側のbitを埋める
CIA: Current Instruction Address
NIA: Next Instruction Address
p.7 (1.3.4 Description of Instruction Operation)
AA: Absolute Address bit (絶対アドレス bit)
LK: Link bit (Link Register を書き換えるか)
p.18 (1.6.24 Instruction Fields)
6
無条件分岐 詳細 (2/2)
分岐先のアドレス指定には、2つ方法がある。
一つは相対アドレス指定。CIA＋LI のアドレ
スへジャンプする。
もう一つは絶対アドレス指定。LIが示すアド
レスへジャンプする。
AA bit (Absolute Address bit) で区別する。
CIA+4 を Link register に保存するかどうか
は LK bit で区別する。
例えば、一番よく使われる、相対アドレス
ジャンプ ＋ Link register にCIA+4を保存する
命令は、
bl 命令である。書き方は、
bl target_addr
となる。target_addr の部分は、アセンブリ
の中なら、例えばラベルで指定できる。
補足： qsortの実装の場合、この命令では駄目
7
分岐命令 (branch 命令)
if (x == y) {
(分岐する場合の処理)
}
(分岐しない場合の処理)
cmp %cr7, %r3, %r4
beq %cr7, mylabel
(分岐しない場合
はここを実行)
mylabel:
(分岐する場合は
ここを実行)
プログラムの実行が枝分か
れするので分岐命令
(branch instruction) と言う
分岐するとき、branch が taken
であると言い、分岐しないとき
not taken であると言う
拡張ニーモニックが多数用意
されているので、まだ気づい
ていない人はマニュアルを
bgt などで検索してみること
8
条件付分岐命令 詳細 (1/2)
BO: 分岐命令(B)の Option (Figure 38 参照)
BI: CRのどのbitによって分岐するか指定す
る。具体的には 32+BI 番目の bit
p.18 (1.6.24 Instruction Fields)
9
条件付分岐命令 詳細(2/2)
マニュアルの Figure 38 を見れば、分岐条件の
記述方法が分かる。しかしこれはかなり複雑な
ので良く読まないと分からない。
分岐予測に関する説明もあるが、ここはまだ知
らなくて良い。(Figure 39)
しかし p.384 付近によく使われる分岐命令の短
縮形 (拡張ニーモニック extended mnemonic)が
載っているのでここを参考にすると良い
10
メモリアクセス命令 詳細
MEM(x, y): メモリ上の x番地から y byte分
p.7 (1.3.4 Description of Instruction Operation)
EA: Effective Address
この場の変数定義 (一行下ですぐに使われている)
^↑𝑛↓𝑋 : Xをn回繰り返したもの
p.5 (1.3.2 Notation)
レジスタ RA に D を符号拡張した物を足した値をアドレスと見なして、メモリから
4 byte分読み込んで RT に代入し、上位 32bitをゼロで埋める、と書いてある。(長い)
命令を確認するには、例えば
addtwo2.o:
file format elf64-powerpc
user@~> gcc -c addtwo.s
Disassembly of section .text:
user@~> objdump -d addtwo.o
とすると右のような出力が得られる。0000000000000000 <addtwo>:
add r3, r4, r3 の bit 列が16進数で
0: 7c 64 1a 14 add r3,r4,r3
4: 4e 80 00 20 blr
表示される。
11
関数呼出：レジスタの待避
•  関数を呼び出すと、呼び出された側では当然
レジスタを使う
–  前回の課題では、GPR3 (%r3) からGPR12 (%r12)
だけを使用するように指示した。なぜか？
–  add_main.s と addtwo.s で使うレジスタが重複し
ていないのは偶然か？
•  もちろん、偶然ではない
•  関数呼出の際にはレジスタをメモリに待避す
る操作が必要
–  当たり前だが、32個のレジスタをうまく使い回さ
なければならない
–  そのために、ルールが決められている
12
volatile, non-volatile
関数呼出の前後で値が変わってしまう可能性があるレジスタを
volatile (揮発性) なレジスタという。呼び出し側が待避する。
そうでないレジスタを non-volatile なレジスタという。呼び出さ
れた側が使う場合はメモリに待避し、リターンする前に書き戻す。
レジスタ名
内容の待避
役割
r0
volatile
命令によっては、ゼロレジスタ (値が0のレジスタ) と見なされる
r1
スタックポインタ
r2
Table of contents pointer (本演習では説明しない)
r3 - r10
volatile
引数に使う (r3は返値を置く)
r11, r12
volatile
関数のリンクなどに使われる。(本演習では説明しない)
r13
non-volatile
small data area pointer (本演習では説明しない)
r14 - r31
non-volatile
ローカル変数として使う。使う場合は待避する。
LR
volatile
link register. 分岐命令から戻るアドレスを記録する。
CTR
volatile
counter register. ループのカウンタ用。
CR0-1, 5-7
volatile
condition register. 実体は 32bit のレジスタを 4bitずつ 8分割した物
CR2 - CR4
non-volatile
condition register. この部分は保存する
13
main.c
#include <stdio.h>
int main() {
return func_a(1);
}
a.c
関数呼出とスタック
このように、何段も関数が呼ばれた場合、
それぞれの関数の情報はどのように保持
されているか。
例えば、func_a からリターンするアドレ
スはどこに保存されているのだろうか？
int func_a(int x) {
return func_b(x);
}
func_c
b.c
int func_b(int x) {
return func_c(x);
}
c.c
int func_c(int x) {
return (x + 1);
}
main
func_b
func_b
func_a
func_a
func_a
main
main
main
func_b
func_a
func_a
main
main
main
14
上位アドレス
main
スタックポインタの操作
mainのスタックフレーム
main を実行中の
スタックポインタ
スタックは、上から下へ伸びる
addtwo
下位アドレス
addtwoのスタックフレーム
addtwo を実行中の
スタックポインタ
関数呼出のためのスタックをコー
ルスタックなどとも呼ぶ。
(単にスタックと呼ぶことが多い)
スタックは、上から下へ伸びる。
そのため、addtwo のスタックポ
インタは main のスタックポイン
タよりも値が小さい。
スタックポインタはr1です。
注意：いつも16の倍数である!
add_main.c
#include <stdio.h>
extern int addtwo(int x, int y);
int main() {
int a = 3;
int b = 4;
int c;
c = addtwo(a, b);
printf ("%d + %d = %d\n", a, b, c);
return 0;
}
addtwo.c
int addtwo(int x, int y) {
return x + y;
}
15
スタックフレームの中身
上位
アドレス
こちらに
成長する
(SP +
(SP +
(SP +
(SP +
(SP +
(SP +
(SP +
下位
アドレス
48)
40)
32)
24)
16)
8)
0)
LR (link register)保存領域
CR (condition register)保存領域
Back chain
FPR保存領域
GPR保存領域
VRSAVE save word
アラインメントパディング
ベクトルレジスタ保存領域
局所変数保存領域
関数呼出用パラメータ保存領域
TOC保存領域 (予約)
リンクエディタ領域 (予約)
コンパイラ領域 (予約)
LR (link register)保存領域
CR (condition register)保存領域
Back chain
これは、64bit PowerPC の
Unix のABI (Linux も共通)
non-volatile なレジスタを待避す
る領域 (必要に応じて確保する)
局所変数や局所配列に使
う領域 (少し先でも説明)
呼び出す関数の引数の数
によりサイズが変わる
ここまでは、スタックを
伸ばす場合は必ず作る
%r1 (=SP, Stack Pointer) は常
にスタックの先頭のアドレス
を持つ
“64-bit PowerPC ELF Application Binary Interface Supplement 1.9”
Fig 3-17. Stack Frame Organization 又は、
「Power アーキテクチャーのためのアセンブリー言語 第 4 回:
関数コールと PowerPC の 64-ビット ABI」を参考
16
リンクレジスタ
•  主に、一部の分岐命令で更新される
–  戻りアドレスをリンクレジスタに記録してから分岐する
•  bl 命令が代表例 (bl printf などとしているはず)
•  リンクレジスタの示す場所へジャンプする命令で使う
–  例えば blr 命令 (今の関数からリターンする命令)
•  blr 命令を実行する前に、リンクレジスタを元の値に
戻しておく必要がある
–  関数を呼び出す前にリンクレジスタを保存し、呼び出した
関数から戻ってきたらリンクレジスタを元に戻す
–  自分から関数を呼び出さないならリンクレジスタに触る必
要はない
•  リンクレジスタを保存する場所に注意
–  前の関数のスタックの中 (次ページ参照)
17
リンクレジスタ等の待避
sample.s
r3を使いつつ、
他の関数を呼ぶ
ld %r3, 112(%r1)
ld %r0,144(%r1)
mtlr %r0
addi %r1,%r1, 128
blr
LR save word
128 byte
sample:
stdu %r1, -128(%r1)
mflr %r0
std %r0, 144(%r1)
std %r3, 112(%r1)
上位
アドレス
%r1+144
Back chain
%r1+128
(元の%r1)
r3 を 保存
%r1+112
LR save word
下位
アドレス
Back chain
新しい%r1
mflr 命令は、mfspr の拡張命令。
Link Register をコピーする。
18
スタックポインタの増やし方
必要な分だけ増やす。
たとえば、以下の c1000.c では、1000
文字分のcharの配列をスタック上に置
くことになるので、スタックポインタ
は1000 byteと少しだけ動いている
c1000.c
#include <stdio.h>
int main() {
char str[1000];
return 0;
}
$ gcc -S -mregnames c1000.c
16の倍数である
ことに注意！
(quad word アライン)
c1000.s
.file "c1000.c"
.section
".toc","aw"
.section
".text"
.align 2
.globl main
.section
".opd","aw"
.align 3
main:
.quad .L.main,.TOC.@tocbase,0
.previous
.type main, @function
.L.main:
std %r31,-8(%r1)
stdu %r1,-1072(%r1)
mr %r31,%r1
li %r0,0
mr %r3,%r0
addi %r1,%r31,1072
ld %r31,-8(%r1)
blr
19
呼出規約 (Calling Convention)
•  関数呼出の際のスタックの作り方、レジスタの使
い方等を合わせて呼出規約 (Calling Convention)
と呼ぶ
–  実行可能ファイルが互換性を持つには、機械語が互換
性があるだけではなく、呼出規約が同じである必要
がある
•  実行可能ファイルに互換性があるためには、ABI
(Application Binary Interface) に互換性がある必
要がある
–  例えば、Intel互換CPU上の Linux の ABI, PowerPC 上
の Linux の ABI 等というように決まっている
–  呼出規約は ABI の一部
–  もちろん機械語が互換でないとダメ
–  システムコール (そのうち説明) も互換でないとダメ
20
関数呼出時のレジスタ待避 (補足)
•  レジスタは、使っている物 (これから使う物) だけ待避すれば良い
–  volatile, non-volatile なものそれぞれについてルール通り待避、復帰す
れば、何重に関数呼出が起きても大丈夫
–  呼ばれる側の関数 (callee) は、呼び出し元がどんなプログラムであって
も動くように書く
–  呼び出す側の関数 (caller) は呼び出す関数がどんな関数であっても動く
ように書く
•  もちろん、お互いが呼出規約のルールに従っている限り
–  コンパイラのコードを参考にすると、無駄に待避していることがある
•  それをそのまま写す人もいますが…
•  詳細については：
–  http://refspecs.linuxfoundation.org/ELF/ppc64/PPC-elf64abi-1.9.html
–  http://www.ibm.com/developerworks/linux/library/l-powasm4/
index.html
–  日本語で：
http://www.ibm.com/developerworks/jp/linux/library/lpowasm4.html
21
課題58, maxof3 関数を作成せよ
•  3つの整数引数を受け取り、大小比較を行って、最大
の値を返す関数 maxof3 を作成せよ
–  ただし、自作の maxof2.s を2回呼び出して使うこと
–  適当な Cプログラムを作成し、(例えば) maxof3.s と組み
合わせてコンパイルし実行すること。
–  ヒント： maxof3 ではリンクレジスタも保存すること。
(mflr, mtlr 命令は何をする命令か？)
•  提出物
–  maxof3, maxof2 のアセンブリソースコード
–  Cソースコード
–  コンパイル時のコマンド
•  コンパイルオプションが分かるように
–  実行結果
•  締切 2014年1月29日(水)
22
課題59, strlenを使ったstrcmp
•  自作の mystrlen 関数を部品として呼び出す
mystrcmp2 関数を作成すること。
–  適当な Cプログラムと組み合わせてコンパイルし、実行す
ること。
–  ヒント： レジュメで説明した addtwo.s ではリンクレジス
タを保存していない。mystrcmp2 ではリンクレジスタも
保存すること。 (add_main.s を参照, mflr, mtlr 命令は何
をする命令か？)
•  提出物
–  mystrcmp2, mystrlen のアセンブリソースコード
–  Cソースコード
–  コンパイル時のコマンド
•  コンパイルオプションが分かるように
–  実行結果
•  締切 2014年1月29日(水)
23
課題60, strlenを使った strcat
•  自作の mystrlen 関数を部品として呼び出す mystrcat2
関数を作成すること。
–  適当な Cプログラムと組み合わせてコンパイルし、実行す
ること。
–  ヒント： レジュメで説明した addtwo.s ではリンクレジス
タを保存していない。mystrcat2 ではリンクレジスタも保
存すること。 (add_main.s を参照, mflr, mtlr 命令は何を
する命令か？)
•  提出物
–  アセンブリソースコード
–  Cソースコード
–  コンパイル時のコマンド
•  コンパイルオプションが分かるように
–  実行結果
•  締切 2014年1月29日(水)
24
課題61, 浮動小数を作る関数
•  3つの整数を受け取り、それぞれを浮動小数の符号部、指数部、
仮数部とみなして、浮動小数点数を作って返す関数をアセン
ブリで作成せよ。
–  適当な Cプログラムと組み合わせてコンパイルし、実行すること。
–  ヒント：ビット演算、シフト演算などを使うこと。
•  マニュアル 3.3.12, 3.3.13 等を参照
–  ヒント： GPR と FPR の間のデータの受け渡しはメモリアクセス
を介して良い
–  (optional) 複数の動作を一括で行う命令もある。できるだけ少な
い命令数で実装せよ。
•  提出物
– 
– 
– 
– 
アセンブリソースコード
Cソースコード
コンパイル時に実行したコマンド
実行結果
•  締切 2014年1月29日(水)
25
課題58∼61 について
•  レジスタの待避は呼出規約通りに行うこと
–  maxof3 は、自作の maxof2 ではなく、誰か他人の作った maxof2 でも
(それが呼出規約に従っている限り) 動作するようにする
•  つまり、maxof2 が %r3から%r10あたりを好き勝手に使っているかもしれない
•  例えば %r3 や %r4 を maxof2 が使っていない volatile なレジスタに待避すれば、
この場合は正しく動作するが、課題の意図としては誤り
–  また、レジスタをスタックに待避するのではなく %r14 などにコピーし
ているのもやめよう
•  main関数で %r14 を使っていたら誤動作します。あらかじめ%r14を待避している
ならば正しいです
•  去年の経験：
–  レジスタを待避する場所が間違っているコードが多数提出されてた
–  運良く動作していることに気づいていない人が多かった
•  mystrcmp2 などについて
–  mystrlen を呼び出す際に、引数がポインタとしては不正な値になって
いる可能性が高い
–  呼び出す前に、%r3 が正しい値かどうか確認 (例えばgdbを使ってみる)
2011/11/30
情報科学基礎実験
26
課題62, 再帰で階乗
•  アセンブリでも、Cと同様に再帰呼び出しを行う
関数を作ることも可能である
•  アセンブリで、再帰呼び出しにより階乗を求める
関数を作成せよ
–  例えば、fact.c と同様の動作をすれば良い
–  Cプログラムと組み合わせてコンパイルし、実行せよ
–  オーバーフローに注意
•  提出物
–  アセンブリソースコード
–  C ソースコード
–  コンパイル時のコマンド
–  実行結果
fact.c
int fact(int i) {
if (i == 0) return 1;
else return i * fact(i-1);
}
•  締切 2014年2月5日(水)
27
課題63, 再帰でフィボナッチ
•  アセンブリでも、Cと同様に再帰呼び出しを行う
関数を作ることも可能である
•  アセンブリで、再帰呼び出しによりフィボナッチ
数を求める関数を作成せよ
–  例えば fib.c と同様の動作をすれば良い
–  Cプログラムと組み合わせてコンパイルし、実行せよ。
•  提出物
–  アセンブリソースコード
–  C ソースコード
–  コンパイル方法 (オプション)
–  実行結果
fib.c
int fib(int a) {
if (a == 0) return 0;
if (a == 1) return 1;
return fib(a-1) + fib(a-2);
}
•  締切 2014年2月5日(水)
28
課題64, (optional) アッカーマン関数
•  アッカーマン関数の定義を調べよ
•  再帰呼び出しでアッカーマン関数を計算する関数を実
装せよ
–  Cプログラムと組み合わせてコンパイルし、実行せよ。
–  オーバーフローに注意
–  注意: ctrl-c や kill コマンドの準備をしておきましょう
•  提出物
– 
– 
– 
– 
アセンブリソースコード
C ソースコード
コンパイル時のコマンド
実行結果
•  締切 2014年2月5日(水)
29
補足: ハマりがちな罠 (再掲)
•  cmp %cr7, %r4, 5 としてもアセンブルが通る
–  objdumpで逆アセンブルしてみると
cmp %cr7, %r4, %r5 の意味になっています
•  cmpi %cr7, %r4, %r5 も同様
–  実際には cmpi %cr7, %r4, 5 の意味になります
•  おかしいなと思ったら
–  hoge.o ファイルを作ってから objdump してみる
•  $ objdump -d hoge.o
•  比較命令や分岐命令でコンディションレジスタの番号を指定
しないと cr0 が使われます
–  書き忘れに注意
–  意図して書かないなら問題なし
•  addi や lbzx 命令で r0 を使うと数値の 0 として扱われます
–  自信がなければ使わないほうがいいです
30
アセンブリ上級者向け課題
•  以下の2つの課題を両方とも解いた場合、アセンブリ入門の課
題は免除されます。
–  課題98, qsort と互換のクイックソートを csp 上のアセンブリで
実装せよ。また、自作のCプログラムからリンクして使用せよ。
性能を qsort と比較せよ。
–  課題99, printf のサブセットを csp 上のアセンブリで実装せよ。
最低限、%d と %s にのみ対応すれば良い。出力の際は、標準ラ
イブラリ等を使うのではなく、アセンブリから直接システム
コールを呼ぶこと。また、自作のアセンブリプログラムから10
個以上の引数を用いて、動作を確認すること。
•  さらに興味があれば、x86アセンブリでも課題のプログラムを
作成してみることも良いと思います。
–  本演習が PowerPC を用いるのは教育的配慮によるものです
•  提出物 (zip)
–  本課題は、必要なファイルを zip形式でまとめて提出すること。
–  プログラム以外に、仕様やコードの簡単な説明を添付すること。
31
予定
•  第1回 (1月8日(水))
–  プログラミング環境の設
定
–  アセンブリの生成
–  整数表現、浮動小数表現
•  第2回 (1月10日(金))
–  アセンブリとは
–  マニュアルの読み方
–  簡単なアセンブリプログ
ラム
•  (一週間空白)
•  第3回 (1月22日(水))
– 
– 
– 
– 
関数呼び出し
スタックの扱い方
レジスタの待避
再帰呼び出し
•  第4回 (1月24日(金))
–  多倍長計算
–  積和命令
–  内積、行列
•  第5回 (1月27日(月))
–  システムコール
–  質疑応答
32
補足: gdbの使い方 (再掲)
•  コンパイル時に -g オプションをつけると、C と同様に
gdb を使ったデバッグが可能
–  例えば、 addtwo.s と add_main.c がある状態で
•  $ gcc -g add_main.c addtwo.s -o add
–  とコンパイルすると、
•  $ gdb add
–  でデバッガが起動する
•  デバッガ (gdb) の主なコマンド
–  機能は各自調べること (help コマンドやgoogleで)
• 
• 
• 
• 
実行開始： run, start, …
途中で止める: break, condition, …
ステップ実行： step, stepi, next, nexti, …
スタック操作： backtrace (bt), up, down, …
•  デバッガは非常に便利なので使い方を身につけるべき
–  特に上級者向け課題はデバッガなしではかなり厳しい
33