人生は勉強ブログ

https://github.com/dooooooooinggggg

x86-64 アーキテクチャCPUで、lifegameを実装するための準備

*このブログは、インターン先の勉強会に向けて作った資料を、ブログとして公開するために一部書き直したものです。

動機

所属している研究室の発表があり、何か実装しなければならなかった。

今後の足がかりとして、アセンブリで何かを実装してみよう。

完成に至る順番

CPUやアセンブリの基礎を学ぶ

Cでlifegameを書いてみる。

そのコードを元に、自分でアセンブリを実装していく。(gccなどからのコピペはしない)

lifegameとは

https://ja.wikipedia.org/wiki/ライフゲーム

これを目指す。

パタヘネ

まずは、プログラムがどのように動くのかを、知るために、パタヘネの上巻、プロセッサの前の章までを読んだ。

今思えば、実装に直接必要のない知識も多いが、この時はよくわからなかったので、とりあえず、読んで、自分の理解をまとめてみた。

プログラムがどのように動いているか

まず、C言語コンパイルしたものを、謎の数字列が大量に表示される。

catコマンドで見てみると、もっと謎な文字列が表示される。

これは、アセンブルされたものである。

アセンブラアセンブリアセンブルというよく似た単語は、それぞれ意味が微妙に異なっている。

先ほどの、大量の文字列は、アセンブリを、アセンブラを使い、アセンブルしたものである。

登場するcpu

MIPS 32bit - risc

x86 32bit - cisc

x86-64 64 bit - cisc

32bit cpuの場合

cpuの内部には、レジスタというものが存在する。

これは超高速であるが、そのぶん低容量な、記憶装置である。

記憶装置の価格は、

HDD < SSD < main memory < register

アクセス速度

HDD < SSD < main memory < register

その代わり、容量は、

HDD > SSD > main memory > register

みたいな関係になっている。つまり、CPUが超高速に扱える、変数を一時的に保管できる場所、ただし数は限られている、みたいな認識。

これらにはそれぞれ、役割があり、32という数字は、一度に解釈できるbit数を表している。

intでいうと、例えば、16bit cpuの場合、符号なしの場合は、0 ~ 2 ** 16 - 1 ( = 65535 ) までしか一度に扱うことができず、符号ありの場合は、-32768 から 32767までしか扱うことができない。

これは、各命令も同じであり、すべての命令の長さや、アドレス、数字は、各CPUがあつかうビット数に依存する。

x86 - 32bitCPUの説明に脱線

www.ishikawa.tech

この記事は、x86(32bit)アーキテクチャレジスタ一覧だが、

ここでいうと、eipレジスタが、命令を読み込む役割を担っている。

この、eipが読み込むことのできるbit数も、当然32bit以下になる。

32bitCPUがメモリを約4GBまでしか扱えない、というのも、ここからきている。

32bit cpuが扱える範囲は、

2 32 = (2 10) * (2 10) * (2 10) * 2 * 2

2 ** 10は1024なので、1000としてみなすと、

1000 * 1000 * 1000 * 4 bit しか扱えない。

これは、4000000KBであり、4000MBであり、4GBである。

さらに脱線して、64bit cpuの例

ここで、64bit cpuのアセンブリを見てみる。

pushmovと書いてある部分が、命令。命令には、それぞれ、目的語のようなものがある。

ここでいうと、rbpだったり、rspだったり。これはレジスタの名前。

レジスタだけでなく、即値や、アドレスも目的語のようなものとして扱える。(それ以外は扱えない。)

(gdb) disass main
# Dump of assembler code for function main:
#    0x0000000100001e00 <+0>: push   rbp
#    0x0000000100001e01 <+1>: mov    rbp,rsp
#    0x0000000100001e04 <+4>: sub    rsp,0x2a320
#    0x0000000100001e0b <+11>:    lea    rdi,[rbp-0xe110]
#    0x0000000100001e12 <+18>:    mov    rax,QWORD PTR [rip+0x1e7]        # 0x100002000
#    0x0000000100001e19 <+25>:    mov    rax,QWORD PTR [rax]
#    0x0000000100001e1c <+28>:    mov    QWORD PTR [rbp-0x8],rax
#    0x0000000100001e20 <+32>:    mov    DWORD PTR [rbp-0x2a314],0x0
#    0x0000000100001e2a <+42>:    call   0x100001500 <define_init_val>
#    0x0000000100001e2f <+47>:    lea    rsi,[rbp-0x1c210]
#    0x0000000100001e36 <+54>:    lea    rdi,[rbp-0xe110]
#    0x0000000100001e3d <+61>:    call   0x1000015a0 <cp_first>
#    0x0000000100001e42 <+66>:    lea    rdi,[rbp-0x1c210]
#    0x0000000100001e49 <+73>:    call   0x100001400 <print_func>
#    0x0000000100001e4e <+78>:    mov    DWORD PTR [rbp-0x2a318],0x0
#    0x0000000100001e58 <+88>:    cmp    DWORD PTR [rbp-0x2a318],0x3e8
#    0x0000000100001e62 <+98>:    jge    0x100001edd <main+221>
#    0x0000000100001e68 <+104>:   mov    edi,0x1
#    0x0000000100001e6d <+109>:   call   0x100001f1a
#    0x0000000100001e72 <+114>:   lea    rdi,[rip+0x12b]        # 0x100001fa4
#    0x0000000100001e79 <+121>:   mov    ecx,DWORD PTR [rbp-0x2a318]
#    0x0000000100001e7f <+127>:   add    ecx,0x1
#    0x0000000100001e82 <+130>:   mov    esi,ecx
#    0x0000000100001e84 <+132>:   mov    DWORD PTR [rbp-0x2a31c],eax
#    0x0000000100001e8a <+138>:   mov    al,0x0
#    0x0000000100001e8c <+140>:   call   0x100001f0e
#    0x0000000100001e91 <+145>:   lea    rsi,[rbp-0x2a310]
#    0x0000000100001e98 <+152>:   lea    rdi,[rbp-0x1c210]
#    0x0000000100001e9f <+159>:   mov    DWORD PTR [rbp-0x2a320],eax
#    0x0000000100001ea5 <+165>:   call   0x1000016c0 <generational_change>
#    0x0000000100001eaa <+170>:   lea    rdi,[rbp-0x2a310]
#    0x0000000100001eb1 <+177>:   call   0x100001400 <print_func>
#    0x0000000100001eb6 <+182>:   lea    rsi,[rbp-0x2a310]
#    0x0000000100001ebd <+189>:   lea    rdi,[rbp-0x1c210]
#    0x0000000100001ec4 <+196>:   call   0x100001630 <cp_prev_to_next>
#    0x0000000100001ec9 <+201>:   mov    eax,DWORD PTR [rbp-0x2a318]
#    0x0000000100001ecf <+207>:   add    eax,0x1
#    0x0000000100001ed2 <+210>:   mov    DWORD PTR [rbp-0x2a318],eax
#    0x0000000100001ed8 <+216>:   jmp    0x100001e58 <main+88>
#    0x0000000100001edd <+221>:   mov    rax,QWORD PTR [rip+0x11c]        # 0x100002000
#    0x0000000100001ee4 <+228>:   mov    rax,QWORD PTR [rax]
#    0x0000000100001ee7 <+231>:   mov    rcx,QWORD PTR [rbp-0x8]
#    0x0000000100001eeb <+235>:   cmp    rax,rcx
#    0x0000000100001eee <+238>:   jne    0x100001f02 <main+258>
#    0x0000000100001ef4 <+244>:   mov    eax,0x1
#    0x0000000100001ef9 <+249>:   add    rsp,0x2a320
#    0x0000000100001f00 <+256>:   pop    rbp
#    0x0000000100001f01 <+257>:   ret
#    0x0000000100001f02 <+258>:   call   0x100001f08
# End of assembler dump.

risc cisc

この二つは、cpu アーキテクチャの、設計思想の違い。

ciscは命令の数がとにかく多い。命令の長さも可変。

反対に、riscは、命令の種類を減らし、回路を単純化することで、演算速度の向上を測るもの。

命令に長さは、固定されていて、すべての演算が1クロックで終了する。

他にも特徴があるが、だいたいこんな感じ。ciscでは、一つの命令で済むようなものも、小さくて高速な命令を組み合わせることで、全体の速度も上がるよねみたいな思想。

例として、分岐の際は、flagを使用したり。。。みたないのがあった気がする。

上にも書いてあるが、x86系は、cisc、armやMIPSは、risc

MIPSアセンブリに関して。

MIPSは、riscであり、命令の長さが一定である。

今回扱ったのは、32bit cpuなので、一つの命令の中に、01が、32個しかない。

これのうち、最初の6bitが命令を表している。

基本的な命令は、この後、5bit, 5bit, 5bit, 5bit, 6bitとなっている。

000000 00000 00000 00000 00000 000000

左から、op rs rt rd shamt functとなっている。

それぞれの命令で、どれを使うかはすでに決まっている。

この32個の数字を繋げて、32bitになったものを、文字列にしたものが、最初に言ったやつ

MIPSには他にも、命令の形はある。つまり、6,5,5,5,5,6みたいな分け方になっていないものも当然ある。

これらは、最初の6bitの命令を見て、どこからどこまでが何かを判別する。

6,5,5,5,5,6となっているものは、R方式という。これは算術命令の形式。(add など)

6,5,5,16となっているものは、データ転送、分岐、即値命令の形式。

6,26となっているものは、ジャンプ命令の形式。

では、ここで、この5bitに入るものは、どんなものか、ということを考えてみる。

まずはいるのは、レジスタの名前。名前は、すでに決まっていて、$0とか$1みたいな名前。2種類ある。

当然、これより前の命令で、そのレジスタに値が入っていることが必須。

他には、即値。例えば、1など。

MIPSレジスタ一覧

$zero 0

$v0 - $v1 結果及び式の評価のための値 ( 2 ~ 3 )

$a0 - $a3 引数 ( 4 ~ 7 )

$t0 - $t7 一時 ( 8 ~ 15 )

$s0 - $s7 退避 ( 16 ~ 23 )

$t8 - $t9 予備の予備の一時 ( 24 ~ 25 )

$gp グローバルポインタ 28

$sp スタックポインタ 29

$fp フレームポインタ 30

$ra 戻りアドレス 31

アドレシングモード

アドレスの扱い方。ちょっとよくわかってないので、いつか追記。

即値

レジスタアドレシング

ベース相対アドレシング

PC相対アドレシング

擬似直接アドレシング

ちょっとした例

00af8020

これが表している、アセンブリ言語の命令は何か。

こういう問いに対しては、

まず、2進数に戻す

16進数は、4bitなので、

0->0->0000

0->0->0000

a->10->1010

f->15->1111

8->8->1000

0->0->0000

2->2->0010

0->0->0000

並べると、

00000000101011111000000000100000

最初の6bit(31 ~ 26)が、

000000 00101011111000000000100000

となっているものはR形式だということがわかる(P116)ので、

000000 00101 01111 10000 00000 100000

このように分けられる

その中からさらに、最後の6bitを見てみると、100000となっているものは、addである。

op rs rt rd shamt functなので、それぞれに値を振り分けることができる。

rsが、00101 -> 5

rtが、01111 -> 15

rdが、10000 -> 16

であり、add命令の仕様を見ると、

この3つ全ては、レジスタであり、shamtは使用しないとなっている(00000)

したがって、この命令は、アセンブリにすると、

16 -> $s0

5 -> $a1

15 -> $t7

であることから、

add $s0, $a1, $t7

$s0 = $a1 + $t7

となる。

実装

以上の知識を前提に、x86-64アーキテクチャの資料を探しつつ、実装をしていった。

この記事を書いた時点で、実装は完了していなかったが、この後、実装が完了した。

https://github.com/dooooooooinggggg/lifegame

↑これ↑

もちろん、使った知識、使わなかった知識、どちらもあったが、ここで調べたことが割と役に立った。

が、やはり一番大事なのは、とりあえず手を動かすことだなと感じた。

この実装のそれぞれの要点に関してはいつか気が向いたら書いてみようかなと考えている。