LoginSignup
227
222

More than 5 years have passed since last update.

@zacky1972(山崎 進)infukuoka.ex：福岡Elixirコミュ

C言語のアセンブリ言語コード化〜直観編

Last updated at Posted at 2014-10-29

1. はじめに

このテキストではC言語で書かれた簡単な階乗プログラムを元にコンパイラがアセンブリコードを生成する時の考え方を示しました。

2. C言語のソースコード

C言語で書かれた階乗のプログラム(元にするプログラムという意味で ソースコード と言います)を次に示します。まずはトレースしてみて動作を確認します。とくに どの経路をたどるかと 変数の値がどのように変化するかに注目してください。

fact.c
unsigned int fact(unsigned int x) {
    unsigned int y;
    if(x == 0) {
        y = 1;
    } else {
        y = x * fact(x - 1);
    }
    return y;
}

void main(void) {
    unsigned int p;
    p = fact(3);
    ...
}

なお，unsigned int は符号なしの整数という意味です。

3. オブジェクトコード (Z80風)

このソースコードをZ80風のアセンブリ言語コード(生成対象のプログラムという意味で オブジェクトコード と呼びます)にしてみました。ただし，実際のZ80には存在しない命令を含んでいます。これらの命令はZ80のインストラクション・セットに沿って命名されています。

ちょっと手間がかかりますが，まずは実際に main からトレースしてみてください。 各レジスタや(IX-$02)などのメモリが何を表しているか考えるのが手がかりになります。(もしトレースしてみてよくわからなかったら，次のセクションにこれらの手がかりを示しましたので参照してください。)

fact.s

fact:
    PUSH IX             ;; IXの内容をスタックに転送します
                        ;; (SP-$1)にIXの上位8ビット
                        ;; (SP-$2)にIXの下位8ビットを代入し，
                        ;; SPを2減らします
    LD IX,SP            ;; SPの内容をIXに転送します(実際には存在しない命令)
    SUB SP,$02          ;; SPを2減らします(実際には存在しない命令) 
    PUSH DE             ;; DEの内容をスタックに転送します
    LD HL,(IX+$04)      ;; (IX+$04)の内容をHLに転送します(実際には存在しない命令)
    LD DE,$0            ;; DEに0を転送します
    CP HL,DE            ;; HLとDEを比較します(実際には存在しない命令)
    JP NZ,if_1_else ;; ゼロでなかったら if_1_else に飛びます
    LD HL,$1            ;; HLに1を転送します
    LD (IX-$02),HL      ;; (IX-$02)にHLの値を転送します(実際には存在しない命令)
    JP if_1_exit        ;; if_1_exitに飛びます
if_1_else:
    LD HL,(IX+$04)      ;; (IX+$04)の内容をHLに転送します(実際には存在しない命令)
    LD DE,$1            ;; DEに1を転送します
    SUB HL,DE           ;; HLからDEを引きます(実際には存在しない命令)
    PUSH HL             ;; HLをスタックに転送します
    CALL fact           ;; サブルーチン fact を呼び出します
    ADD SP,$02          ;; SPを2増やします(実際には存在しない命令)
    LD DE,(IX+$04)      ;; (IX+$04)の内容をDEに転送します(実際には存在しない命令)
    MUL HL,DE           ;; HLとDEをかけて結果をHLに代入します(実際には存在しない命令)
    LD (IX-$02),HL      ;; HLの内容を(IX-$02)に転送します(実際には存在しない命令)
if_1_exit:
    POP DE              ;; スタックからDEに転送します
                        ;; SPを2増やします
                        ;; (SP-$1)にD(DEの上位8ビット)
                        ;; (SP-$2)にE(DEの下位8ビット)を代入します
    LD HL,(IX)          ;; (IX)の内容をHLに転送します
    LD SP,IX            ;; IXの内容をSPに転送します
    POP IX              ;; スタックからIXの内容を転送します
    RET                 ;; 復帰します

main:
    PUSH IX             ;; IXの内容をスタックに転送します
                        ;; (SP-$1)にIXの上位8ビット
                        ;; (SP-$2)にIXの下位8ビットを代入し，
                        ;; SPを2減らします
    LD IX,SP            ;; SPの内容をIXに転送します(実際には存在しない命令)
    SUB SP,$02          ;; SPを2減らします(実際には存在しない命令)
    LD HL,$03           ;; HLに3を代入します
    PUSH HL             ;; HLの内容をスタックに転送します
    CALL fact           ;; サブルーチン fact を呼び出します
    ADD SP,$02          ;; SPを2増やします(実際には存在しない命令)
                        ;; これで引数xを消します
    LD (IX-$02),HL      ;; HLの内容を(IX-$02)に転送します(実際には存在しない命令)
    ...
    LD SP,IX            ;; IXの内容をSPに転送します
    POP IX              ;; スタックからIXの内容を転送します
    RET                 ;; 復帰します(プログラムの終了)

4. メモリマップ／レジスタマップ

オブジェクトコードをトレースできましたか？ 手がかりがなくて，なかなか難しかったんじゃないでしょうか。今回，オブジェクトコードに変換した際に，次のようなメモリの使い方(メモリマップと呼びます)とレジスタの使い方(レジスタマップと呼びます)をしました。これを手がかりにして再びオブジェクトコードを読んでみてください。このプログラムは階乗として機能していますか？

レジスタマップ

レジスタ 使い方
SP スタックポインタ: スタック領域の先頭を表します。
IX フレームポインタ あるいは ベースポインタ: スタック領域の中に記憶されている 自動変数 や 引数 を参照するときに使います。
HL 汎用16ビットレジスタとして使います。サブルーチンから復帰した際の 戻り値 としても使います。
DE 汎用16ビットレジスタとして使います。

メモリマップ(fact)

アドレス 使い方
(IX-$02) 自動変数 y
(IX) 以前のレジスタ IX の内容のバックアップ
(IX+$02) サブルーチンfactからの復帰先のプログラムコードのアドレス
(IX+$04) 引数 x

メモリマップ(main)

アドレス 使い方
(IX-$02) 自動変数 p
(IX) 以前のレジスタ IX の内容のバックアップ
(IX+$02) サブルーチンmainからの復帰先のプログラムコードのアドレス

5. コード生成の考え方

このようなオブジェクトコードはどのようにして生成されたのでしょうか。ソースコードと対比しながら見ていきましょう。

5.1 関数の定義

次のようなコードの断片は関数の定義の一例です。

unsigned int fact(unsigned int x) {
    ...
}

関数の定義をオブジェクトコードに変換するときには次の原理に従います。

  1. 関数名を表すラベルを定義します。
  2. フレームポインタをスタックにバックアップします。
  3. スタックポインタの内容をフレームポインタにコピーします。
  4. ...をコード生成します。
  5. フレームポインタの内容をスタックポインタにコピーします。
  6. スタックにバックアップしたフレームポインタの内容を元に戻します。
  7. サブルーチンから復帰します。

オブジェクトコードとしては次のようになります。

fact:                   ;; 1. 関数名を表すラベルを定義します。
    PUSH IX             ;; 2. フレームポインタをスタックにバックアップします。
    LD IX,SP                ;; 3. スタックポインタの内容をフレームポインタにコピーします。
    ...                 ;; 4.
    LD SP,IX            ;; 5. フレームポインタの内容をスタックポインタにコピーします。
    POP IX              ;; 6. スタックにバックアップしたフレームポインタの内容を元に戻します。
    RET                 ;; 7. サブルーチンから復帰します。

5.2 自動変数の定義

次のようなコードの断片は自動変数の定義の一例です。

fact.c
{
    unsigned int y;
    ...
}

自動変数の定義をオブジェクトコードに変換するときには次の原理に従います。

  1. スタックポインタを必要とするメモリ量分減らして変数領域を確保します。
  2. ...をコード生成します。
  3. スタックポインタを必要とするメモリ量分増やして変数領域を解放します。

オブジェクトコードとしては次のようになります。

    SUB SP,$02          ;; 1. スタックポインタを必要とするメモリ量分減らして変数領域を確保します。
    ...                 ;; 2. 
    ADD SP,$02          ;; 3. スタックポインタを必要とするメモリ量分増やして変数領域を解放します。

関数の定義と合わせて次のようなコードになります。

fact:                   ;; 関数名を表すラベルを定義します。
    PUSH IX             ;; フレームポインタをスタックにバックアップします。
    LD IX,SP            ;; スタックポインタの内容をフレームポインタにコピーします。
    SUB SP,$02          ;; スタックポインタを必要とするメモリ量分減らして変数領域を確保します。
    ...
    ADD SP,$02          ;; スタックポインタを必要とするメモリ量分増やして変数領域を解放します。
    LD SP,IX            ;; フレームポインタの内容をスタックポインタにコピーします。
    POP IX              ;; スタックにバックアップしたフレームポインタの内容を元に戻します。
    RET                 ;; サブルーチンから復帰します。

しかし， ADD SP,$02 の直後で LD SP,IX と SP の内容を上書きしているので， ADD SP,$02 は無駄なコードです。そこで， ADD SP,$02 を削除します。このような変換を 最適化 と言います。

fact:                   ;; 関数名を表すラベルを定義します。
    PUSH IX             ;; フレームポインタをスタックにバックアップします。
    LD IX,SP            ;; スタックポインタの内容をフレームポインタにコピーします。
    SUB SP,$02          ;; スタックポインタを必要とするメモリ量分減らして変数領域を確保します。
    ...
    LD SP,IX            ;; フレームポインタの内容をスタックポインタにコピーします。
    POP IX              ;; スタックにバックアップしたフレームポインタの内容を元に戻します。
    RET                 ;; サブルーチンから復帰します。

以上のように下準備すると ... のコードの範囲では メモリマップ(fact) にしたがって自動変数や引数を参照できます。

5.3 if文

if文は次のようなコードの断片です。

    if( ... /* 条件式 */) {
        ... /* then 節 */
    } else {
        ... /* else 節 */
    }

if文をオブジェクトコードに変換するときには次の原理に従います。

  1. 条件式をコード生成します。
  2. ゼロでなかったときelse節にジャンプします。
  3. then節をコード生成します。
  4. 無条件でif文の末尾にジャンプします。
  5. else節のラベルを定義します。
  6. else節をコード生成します。
  7. if文の末尾のラベルを定義します。

オブジェクトコードとしては次のようになります。

    ...                 ;; 1. 条件式をコード生成します。
    JP NZ,if_1_else ;; 2. ゼロでなかったときelse節にジャンプします。
    ...                 ;; 3. then節をコード生成します。
    JP if_1_exit        ;; 4. 無条件でif文の末尾にジャンプします。
if_1_else:              ;; 5. else節のラベルを定義します。
    ...                 ;; 6. else節をコード生成します。
if_1_exit:              ;; 7. if文の末尾のラベルを定義します。

5.4 等号

等号は次のようなコードの断片です。

    /*左辺式*/ == /*右辺式*/

等号をオブジェクトコードに変換するときには次の原理に従います。

1. 左辺式を汎用レジスタr1に転送するコードを生成します。
2. 右辺式を汎用レジスタr2に転送するコードを生成します。
3. r1とr2を比較するコードを生成します。

オブジェクトコードとしては次のようになります。

    LD r1, (左辺式)      ;; 1. 左辺式を汎用レジスタr1に転送するコードを生成します。
    LD r2, (右辺式)      ;; 2. 右辺式を汎用レジスタr2に転送するコードを生成します。
    CP r1,r2            ;; 3. r1とr2を比較するコードを生成します。

5.5 引数・自動変数の参照

汎用レジスタ r に引数や自動変数を参照するときには，フレームポインタ fp を使って次のようにコード生成します。

    LD r,(fp +/- ?)

5.6 定数の代入

汎用レジスタ r に定数 n を代入するときには次のようにコード生成します。

    LD r,n

5.7 条件式のコード生成

5.4〜5.6 を基にして条件式をコード生成。

ソースコード

    x == 0 /* x は引数 */

レジスタマップ・メモリマップ

仮のレジスタ 実際のレジスタ ソースコード上の変数・定数
fp IX -
(fp+$04) (IX+$04) 引数x
r1 HL 引数x
r2 DE 定数0
左辺のr HL 引数x
右辺のr DE 定数0

実際のオブジェクトコード

    LD HL,(IX+$04)
    LD DE,$0
    CP HL,DE

汎用レジスタDEを使用するので PUSH と POP を使って退避／復帰します。

5.8 自動変数への代入

汎用レジスタ r の内容を自動変数へ代入するときには，フレームポインタ fp を使って次のようにコード生成します。

    LD (fp +/- ?),r

5.9 then節のコード生成

5.8 を基にして then 節をコード生成します。

ソースコード

    y = 1;

レジスタマップ・メモリマップ

仮のレジスタ 実際のレジスタ ソースコード上の変数・定数
fp IX -
(fp-$02) (IX-$02) 変数y
r HL 定数1

実際のオブジェクトコード

    LD HL,$1
    LD (IX-$02),HL

5.10 数式〜else節のコード生成

else節にあるような複雑な数式はいったん次のような木構造の形で書いておくと見通しが良くなります。このような木構造を 解析木 といいます。

        y = x * fact(x - 1);

fact-parse-tree.jpg

次の原則に従ってコード生成を行います。

  • 代入式の場合
    1. 右辺
    2. 左辺
    3. 自身のコード(代入)
  • それ以外の式の場合
    1. 左辺
    2. 右辺
    3. 自身のコード(数式)

この場合は次のような順番でコード生成を行います。

  1. 引数x(左側)
  2. 引数x(右側)
  3. 定数1
  4. 関数呼び出し
  5. 乗算
  6. 自動変数y(代入式の左辺)
  7. 代入式

5.11 関数呼び出し

次のようなコードの断片は関数呼び出しの一例です。

    func(/*引数1*/, /*引数2*/, ...);

関数呼び出しをオブジェクトコードに変換するときには次の原理に従います。

  1. 引数1のコードを生成し，レジスタrに代入します。
  2. スタックにレジスタrを転送します。
  3. 引数2のコードを生成し，レジスタrに代入します。
  4. スタックにレジスタrを転送します。
  5. ...
  6. 関数に対応するサブルーチンを呼び出します。
  7. 引数を確保した分スタックポインタを増やし，引数を解放します。

オブジェクトコードとしては次のようになります。

    ...             ;; 1. 引数1のコードを生成し，レジスタrに代入します。
    PUSH r          ;; 2. スタックにレジスタrを転送します。
    ...             ;; 3. 引数2のコードを生成し，レジスタrに代入します。
    PUSH r          ;; 4. スタックにレジスタrを転送します。
    ...             ;; 5.
    CALL func       ;; 6. 関数に対応するサブルーチンを呼び出します。
    ADD SP,...      ;; 7. 引数を確保した分スタックポインタを増やし，引数を解放します。

5.12 四則演算

四則演算をオブジェクトコードに変換するときには次の原理に従います。

  1. 左の式をレジスタr1に転送します。
  2. 右の式をレジスタr2に転送します。
  3. 四則演算をコード生成します。
    • 加算の場合: ADD r1, r2
    • 減算の場合: SUB r1, r2
    • 乗算の場合: MUL r1, r2
    • 除算の場合: DIV r1, r2

なお演算結果はr1に格納されます。

加算の場合，オブジェクトコードとしては次のようになります。

    LD r1, ...      ;; 1. 左の式をレジスタr1に転送します。
    LD r2, ...  ;; 2. 右の式をレジスタr2に転送します。
    ADD r1, r2      ;; 3. 四則演算をコード生成します。

5.13 else節

以上を踏まえて，else節は次のようにコード生成されます。

ソースコード

        y = x * fact(x - 1);

解析木

fact-parse-tree.jpg

レジスタマップ・メモリマップ

実際のレジスタ ソースコード上の変数・定数
IX フレームポインタ
(IX-$02) 自動変数y
(IX+$04) 引数x
HL 演算の途中経過
BC 引数x
DE 定数1

実際のオブジェクトコード

    LD BC,(IX+$04)
    LD HL,(IX+$04)
    LD DE,$1
    SUB HL,DE
    PUSH HL  
    CALL fact 
    ADD SP,$02 
    MUL HL,BC 
    LD (IX-$02),HL

5.14 else節の最適化

生成されたオブジェクトコードの命令順番を入れ替えるとレジスタBCを削減できる最適化が可能です。

最適化されたレジスタマップ・メモリマップ

実際のレジスタ ソースコード上の変数・定数
IX フレームポインタ
(IX-$02) 自動変数y
(IX+$04) 引数x
HL 演算の途中経過
DE 引数x, 定数1

最適化されたオブジェクトコード

    LD HL,(IX+$04)
    LD DE,$1
    SUB HL,DE
    PUSH HL
    CALL fact 
    ADD SP,$02 
    LD DE,(IX+$04) 
    MUL HL,DE 
    LD (IX-$02),HL

汎用レジスタDEを使用するので PUSH と POP を使って退避／復帰します。

5.15 戻り値

関数の最後に戻り値をHLに代入します。

6. おわりに

コード生成の考え方はわかりましたか？ 自分の手でコード生成をなぞってみてください。

このようなコード生成の原則がわかると，高級言語で書かれたプログラムがどのようにアセンブリ言語に変換されるのか，CPUがどのように解釈して実行するのかがよくわかると思います。

コメントいただきました

fujita nozomu ‏@fujitanozomu 10月21日
@zacky1972 メモリマップ(main)は(IX+\$02) サブルーチンmainからの復帰先のプログラムコードのアドレス(IX) レジスタ IXの内容のバックアップでは?自動変数pを配置すべきは(IX-\$02)ではないですか? fact()も同様におかしいと思います。
https://twitter.com/fujitanozomu/status/656831687259656192

コメントありがとうございます！ ようやく修正しました。もしまだ問題点があるようならご指摘ください。

学生から寄せられた質問に対するフィードバック講義動画を公開しました。

リンク先を参照ください。

  1. C言語のアセンブリコード化〜フィードバック講義 2015年 https://www.youtube.com/watch?v=MPg4ul0Nn7s
  2. C言語のアセンブリコード化〜直観編フィードバック講義 2015年 その2 https://youtu.be/cATWCs62CDc
227
222
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
227
222