Compiler Construction Lecture No.2

Menu

実行系のArchitecture

Compilerのtargetにはいろいろあるが、あるComputer上でもっとも高速なのは、そのComputerのmachine language(機械語)である。したがって、machine language がもっとも重要なCompiler targetだということができる。ここでは、いくつかのCPUのProgramming Modelを学び、その実行を調べる方法を学ぶ。

CPUのprogramming modelは、以下の要素からなる。

個々のCPUには、それぞれ特徴があり、compilerを作る際にはその特徴を考慮する必要がある。しかし、極端に異なるachitecutreを持っているものは少なく、どれをとっても同じようなものだともいうことができる。

すべてのCPUに詳しくなる必要はないが、どれか一つの専門家にはなっていたい所である。

Little-Endian, Big-Endian

Computer には memory がつきものだが、memory は、1 byte (= 8bit)単位でlinear address (byte addressing) がふられている。しかし、最近のCPUは、16bit, 32bit, 64bit 単位(word)で処理をおこなう。従って、wordをどのように byte addressing に割り振る(map)かという問題がある。これには主に2種類の mapping があり、それぞれLittle-Endian, Big-Endian と呼ばれている。

どちらが優れているかという議論はあったが、現在では卵のとがっている方から割るか、丸い方から割るかぐらいの違いしかないと認識されているようだ。

Endian をgdbで表示する

    long check = 0x123456789abcdef;
    main()
    {
	char i, *ptr;
	
	ptr = (char *)✓ 
	i = ptr[1];
	return i;
    }
32bit machine の場合は、 
    long check = 0x12345678;
ぐらいが良い。long は 64bit であることが多い。( LP64 )

これをコンパイルして、 

    % gdb a.out
    GNU gdb 6.3.50-20050815 (Apple version gdb-563) (Wed Jul 19 05:17:43 GMT 2006)
    (gdb) b main
    Breakpoint 1 at 0x1da8
    (gdb) run
    Starting program: /private/tmp/a.out 
    Reading symbols for shared libraries . done
    Breakpoint 1, 0x00001da8 in main ()
    (gdb) x/20b &check
    0x2014 <check>: 0x12    0x34    0x56    0x78    0xa0    0x00    0x1f    0xdc
    0x201c <check+8>:       0xa0    0x01    0x1b    0x1c    0xa0    0x00    0x1f    0x98
    0x2024 <check+16>:      0xa0    0x00    0x5c    0x00
    (gdb)
と表示してみよう。0x12, 0x34, 0x56, 0x78 の順にメモリに格納されていることがわかる。

x は examine の略らしい。/20b は、表示するフォーマットを表す。 

    (gdb) help x
    Examine memory: x/FMT ADDRESS.
    ADDRESS is an expression for the memory address to examine.
    FMT is a repeat count followed by a format letter and a size letter.
    Format letters are o(octal), x(hex), d(decimal), u(unsigned decimal),
      t(binary), f(float), a(address), i(instruction), c(char) and s(string),
      T(OSType).
    Size letters are b(byte), h(halfword), w(word), g(giant, 8 bytes).
    The specified number of objects of the specified size are printed
    according to the format.
Intel と PowerPC で調べてみること。

つまり、Mac OS X では、Intel/PowerPC でEndianが異なる。したがって、Endian に依存したプログラムをしてはいけない。(特にネットワークでバイナリを送る場合)

cf. htons, ntohs

Alignment

もう、このmappingは、CPU - memory 間の転送も考慮する必要がある。同じ 1 word を転送するのでも、Busが64bit幅だったりすれば、そのアドレス下位3bitの値によって、一回で転送できる場合とそうでない場合がある。これを word alignment の問題という。当然、一回で転送できる方が高速に動作する。

つまり、32bit integer を格納する場合、配列などは、4byte 単位の alignment を持つ。 

   0x1231
などのアドレスにintを格納するとalignmentがずれる。 
   0x1230 や 0x1234
ならば良い。

アセンブラでは、 

    .align 4
という疑似命令で制御されていることが多い。

実際には、CPU - memory 間の転送は、直接行われるわけではなく、キャッシュ間の転送として現れるので、パフォーマンスとして影響が出ることは少ない。

しかし、IntelのSSE2 (Pentinum 4 以降)では、XMM レジスタが16byte alignment を要求する。alignment がずれると、CPU が例外を発生する。

これらの問題は、普通のプログラミングでは考える必要はないが、効率の良いMachine Languageを生成する場合には考慮する必要がある。

malloc 時に alignment を指定できる malloc を使用する。 

   posix_memalign

Addressing Mode

実際にCPUとmemoryのdataのやり取りをするのが、load/store 系の命令である。CPUの命令の中で大きな割合を占める。Addressing modeとは、register や命令で、どのように memory address を指定するかを決める方法である。昔は、MC6809のように豊富なIndex modeを持つものが歓迎された。今では、RISC Architecture という、simple な Address mode を持つ命令が好まれている。

現在のプログラミングでは、配列(array)やリスト(list)、構造体(structure)のアクセスが重要なので、Addressing mode は、それを1命令で実現しやすいように設計されているのが普通だ。だいたい図のようなAddressing mode を採用しているものが多い。

いろいろなCPUのProgramming Model

Intel x86 32bit mode

現在もっとも良く使われているCPU。しかし、16bit modeを使っている所も多いだろう。ここでは、比較的きれいなarchitectureを持っている32bit mode のみを紹介する。IA32 と呼ばれている。

8bit CPU(8080)の拡張によってできたCPUなので、32bit modeでもそれをかなり引きずっている。命令は8bitの可変長命令である。80386によって、16bit/32bit切替と仮想記憶がサポートされ爆発的な成功を納めた。最近のPentinum II では、内部でRISC 命令に変換してから実行するというようなことをしている。16bit ではregisterの役割が偏っていたが、32bitでは若干対称性が良くなっている。4本のAccumulator、4本のIndex register を持つ。

Addressing modeには以下のようなものがある。 

 Immediate                        movb al,$F0     constantをloadする
 extended                         movb al,[$F000] 指定されたaddressからloadする
 indexed                          movb al,[EAX+5] indexとoffsetで示されたaddress からload する
 accumulator offset indexed       mov [EBX+EAX]
 accumulator offset indexed       mov [EBX+EAX+5]
さらに、x86には segement register というのがあり、それによってvirtual memory (メモリ空間) を切り替えることができる。しかし、普通はすべて同じメモリ空間が設定されている。他のCPUでもデータ(data)とコード(code)は別空間にできるものが多い。

演算はレジスタとレジスタの間で行うことが多い。 もう少し詳しくは、インテル386のアセンブラ を参照すること。

Intel EMT64 64bit mode

IA32を、AMDが拡張したものをIntelが採用した64bit mode。

register が16本に増えて、rip (program counter)を含めて対称的に扱えるようになっている。128bit XMMレジスタも16本に増えた。

インテルEMT64のアセンブラ

x86 の命令に関しては、このサイトが便利x86 Instruction Set Reference

ARM

iPhone などで使われている CPU。16本のレジスタ、16本の浮動小数点レジスタ。

ARM32 の命令 (簡単な方) ARM64 (Aarch) の命令

Java byte code

Java の byte code は、構文木を直接表しているので、CPU 命令よりも構文よりの命令が多い。

Java byte code

LLVM byte code

LLVM も変数の宣言などの構文よりの命令がたくさん入っている。

LLVM byte code

コンパイラ出力を読む

LLVM compiler には、-S option があり、Assembelr sourceを生成することができる。簡単なCのプログラムを書いてcompileして見るとどんな命令が生成されるかがわかる。

gdb というdebuggerを使って、そのAssemberの実行を一命令づつ調べることができる。 

    int a[10];
    main() 
    {
	return a[4];
    }
は、clang -O -S test.c によって、(RISCの場合は-Oを付けた方がより 分かりやすいコードがでることが多い) 

	    .file   "test.c"
	    .version        "01.01"
    gcc2_compiled.:
    .text
	    .align 4
    .globl main
	    .type    main,@function
    main:
	    pushl %ebp
	    movl %esp,%ebp
	    movl a+16,%eax
	    leave
	    ret
    .Lfe1:
	    .size    main,.Lfe1-main
	    .comm   a,40,4
	    .ident  "GCC: (GNU) 2.8.1"
という形test.s にcompileされる。これをgdbで実行するには、これをさらにcompileして、 
    gcc -g test.c
    gdb a.out
とする。 

    (gdb) b main
    Breakpoint 1 at 0x80483cf: file test.c, line 4.
    (gdb) r
    Starting program: /local/kono/public_html/lecture/1999/compiler/99-10-25/a.out 
    Breakpoint 1, main () at test.c:4
    4           return a[4];
    (gdb) disass
    Dump of assembler code for function main:
    0x80483cc <main>:       pushl  %ebp
    0x80483cd <main+1>:     movl   %esp,%ebp
    0x80483cf <main+3>:     movl   0x80494e4,%eax
    0x80483d4 <main+8>:     leave  
    0x80483d5 <main+9>:     ret    
    End of assembler dump.
    (gdb) stepi
    5       }
    (gdb) stepi
    0x80483d5 in main () at test.c:5
    5       }
    (gdb) p $eax
    $1 = 0
    (gdb)
とすれば良い。

問題 2.1

以下のprogram check_endian.c がある。 

    int check = 0x12345678;
    main()
    {
	char i, *ptr;
	
	ptr = (char *)&check; 
	i = ptr[1];
	return i;
    }
このprogramをcompileしたassemblerを、i386, emt64 のCPUで表示させて見よ。また、gdb で i にどのような値が入るかを確認せよ。そのCPUは、Little-Endian か Big-Endian かを答えよ。また、 trace の結果を、確認せよ。

Endian の変換はどのような時に必要になるか。どのようにすれば実現できるか?

Unix には、Builtin のEndianの変換関数がある。それを探し出せ。また、その実装がどうなっているかを調べよ。(ヒント: man -k を使う)

Shinji KONO / Wed Oct 19 17:16:05 2022