Compiler Construction Lecture No.2

実行系の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

PowerPC

IBMとモトローラ社が開発したRISC。一つのクロックで複数の命令を同時に実行するスーパースカラーというアーキテクチャを持っている。条件ブランチ用の条件レジスタ(condition register)を複数持ち、分岐予測の時間猶予を確保できる。条件分岐の予測を示す命令を持つ。サブルーチンの戻り番地はlink registerに格納される。delayed slot などはない。

IBMのAIXに採用された。また、IBMのメインフレームを置き換えることも期待され、IBM360の命令をエミュレートすることも研究された。

Appple のMacinstoshに採用された。モトローラ社が作るG3,G4プロセッサ、そして、IBM社が作るG5 プロセッサなどがある。組込み用途などにも使われている。

PowerPCのアセンブラ

Mac OS X のgccに -arch ppc を付けることにより生成実行することが可能。

PS3 にも使われている。

ここでは取り上げなかったが、 CompaqのAlpha CPU, HPのPA-RISC, ARM なども良くできたCPUである。

コンパイラ出力を読む

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

IBMPC は、pw上でcompile すれば良い。Sparc は、nirai, kanai 上でcompileすれば良い。MIPS は、PlayStation 用のcross compiler を使用する。/usr/open/lectures/kono/compiler/mc-intel に太田昌宏氏によるMicro-C を i386 用に修正したものがある。

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

    int a[10];
    main() 
    {
	return a[4];
    }
は、gcc -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 を使う)

問題 2.2

Cの様々な整数演算が、どのようなアセンブラにコンパイラによって変換されるかを -S フラグを使って調べよ。(最低、4則演算については調べること)singed, unsigned (char, short, int, long, void *) について調べると良い。

また、それらの計算がどう進むかをstep実行し、レジスタの中身を表示することによって示せ。 

    extern int printf(char *,...);
    #define TYPE int
    TYPE f(TYPE a, TYPE b) {
	return a + b;
    }
    int main() 
    {
        TYPE a = 1;
        TYPE b = 2;
        printf("%x = %x + %x \n",f(a,b),a,b);
        return 0;
    }
    Compiler Construction Lecture No.2
  1. 実行系のArchitecture
  2. Little-Endian, Big-Endian
  3. Endian をgdbで表示する
  4. * LP64 )
  5. Alignment
  6. Addressing Mode
  7. いろいろなCPUのProgramming Model
  8. Intel x86 32bit mode
  9. * インテル386のアセンブラ
  10. Intel EMT64 64bit mode
  11. * インテルEMT64のアセンブラ
  12. * x86 Instruction Set Reference
  13. PowerPC
  14. * PowerPCのアセンブラ
  15. コンパイラ出力を読む
  16. * test.c によって、(RISCの場合は-Oを付けた方がより
  17. * test.s
  18. 問題 2.1
  19. *
  20. 問題 2.2
  21. *
Shinji KONO / Sat Mar 24 11:27:21 2012