Open309

C言語まとめ

PONTAPONTA

以下の書き方について

typedef struct {
    char name[20];
    int age;
} person_t;

void main() {
    person_t p;
}

これは以下の書き方を省略したもの

struct _person {
    char name[20];
    int age;
};
typedef struct _person person_t;

void main() {
    person_t p;
}

こんなイメージだと思う。typedef (struct _person) person_t;

参考:https://www.cc.kyoto-su.ac.jp/~yamada/programming/struct.html

PONTAPONTA

構造体の前方宣言

以下のように構造体のタグのみを宣言できる。

struct disk;

この宣言の後に、具体的な宣言をして構造体を使うことができる。

struct disk {
    int size;
    char* name;
};
struct disk mydisk;
PONTAPONTA

va_list, va_start, vfprintf

variable printを使う。引数が可変。

https://qiita.com/kurasho/items/1f6e04ab98d70b582ab7

PONTAPONTA

C言語で可変長の引数を取るには、#include <stdarg.h>を使う。
#include <stdarg.h>は、va_list, va_start, va_arg, va_endで構成される。

典型的には以下のように使う。

#include <stdarg.h>

int add_all(int n, ...) {
  va_list ap;
  va_start(ap, n);
  int sum = 0;
  for (int i = 0; i < n; i++) sum += va_arg(ap, int);
  va_end(ap);
  return sum;
}

int main() {
  int a = add_all(3, 1, 2, 3);
  return a; // 6
}

va_list apapが可変長の引数を扱うための変数であることを宣言する。
va_startは、apの開始位置を指定する。。具体的には関数の引数nの次から取り出すように設定する。
va_arg(ap, int)で、変数apからint型の値を取り出し、次の値を指し示すように設定する。
va_endで変数apが可変長の引数を取り出すという設定を解除する。

PONTAPONTA

va_listには引数の終わりを取得する機能が存在しない。

printfはva_listを使って実装されているが、以下のようにコードを書いた場合にコンパイラレベルでも実行時にもエラーを出すことができない。未定義動作となってしまう。

printf("%d %d", a);
PONTAPONTA

memcmp

memcmp(s1, s2, n)

ポインタs1からn bitsとポインタs2からn bitsを見て比較する。

PONTAPONTA

strtol

stdlib.hに入ってる。文字列から数字を取り出すのに使える。

char *p;
int val = strtol("10+1", &p, 10);
val;  // 10
*p; // '+'
PONTAPONTA

strtod

文字列からdoubleを取り出すのに使える。

PONTAPONTA

ポインタの整理

Cのポインタ、一生わからない。

PONTAPONTA

変数には全てアドレスが割り当てられている。

&・・・アドレス演算子
変数が格納されているアドレスを取得できる。

#include <stdio.h>

int main(int argc, char **argv) {
    int a = 10;
    printf("%p\n", &a); // 0x16b7baeac
}
PONTAPONTA

ポインタ変数を使うと、ポインタ変数に格納されたアドレスの値を取り出せる。

*・・・間接演算子
ポインタ変数に定義されている演算子で、ポインタ変数が示すアドレスの値を取り出せる。

#include <stdio.h>

int main(int argc, char **argv) {
    int a = 10;
    printf("%p \n", &a); // 0x16f506eac 
    int *p = &a;
    printf("%d, %p \n", *p, &p); // 10, 0x16f506ea0 
}

わかりずらさは、変数宣言の時のpと、変数を使うときのpは意味が違うところにある。

PONTAPONTA

アロー演算とドット演算の違い。

アロー演算は構造体のポインタから値を取り出す演算子。
ドット演算は構造体から値を取り出す演算子。

https://monozukuri-c.com/langc-pointer-struct/

PONTAPONTA
typedef struct {
    int age;
} Person;

Person a = {20};
Person *b = &a;

printf("a.age = %d\n", a.age); // 構造体から値を取り出す。
printf("b.age = %d\n", b->age); // 構造体のポインタから値を取り出す。

printf("*b.age = %d\n", (*b).age); // 構造体のポインタから構造体を取り出して、そして値を取り出す。
PONTAPONTA

生成文法の練習

1 + 2 *3の文法

expr = mul ('+' mul | '-' mul)*
mul = num ('*' num | '/' num)*
num = 1 | 2 | 3 ...

コツは演算子として優先度が高いのを下に書くこと。こうすることでこの木構造の先端から処理すると、一つのスタック用いて計算できるようになる。逆ポーランド記法を参照。

PONTAPONTA

(1+2)*3の文法

expr = mul ('+' mul | '-' mul)*
mul = primary ('*' primary | '/' primary)*
primary = num | '(' expr ')'
num = 1 | 2 | 3 ...

再帰的になってるので難しい。

PONTAPONTA

'\0'について

文字列を宣言すると、最後にこれが追加される。

PONTAPONTA
char a[] = "Hello";
for (int i = 0; i < 10; i++) {
    if (a[i] == '\0'){
        printf("a[%d] == \\0\n", i);
    }
}

上記を実行すると以下のようになった。

a[5] == \0
a[6] == \0
a[7] == \0

a[5]が'\0'なのは定義された動作。a[6], a[7]が'\0'なのは未定義動作だと思う。

PONTAPONTA

M1 Macのアセンブリを調べる

test.c
int main() {
    return 42;
}

以下でアセンブリに変換

$ cc -S test.c

変換結果

test.s
	.section	__TEXT,__text,regular,pure_instructions
	.build_version macos, 13, 0	sdk_version 13, 3
	.globl	_main                           ; -- Begin function main
	.p2align	2
_main:                                  ; @main
	.cfi_startproc
; %bb.0:
	sub	sp, sp, #16
	.cfi_def_cfa_offset 16
	str	wzr, [sp, #12]
	mov	w0, #42
	add	sp, sp, #16
	ret
	.cfi_endproc
                                        ; -- End function
.subsections_via_symbols
PONTAPONTA

不要な部分を削除する。

test.s
	.globl	_main
	.p2align	2
_main:                                  ; @main
	mov	w0, #42
	ret

w0に42を設置し、処理を終了。
結果を確認。

$ cc test.s
$ ./a.out
$ echo $?
42

終了ステータスが42になっている。
ちなみにx0に42を入れても同じことができる。

PONTAPONTA

12 + 13 = 25を計算する。

	.globl	_main
	.p2align	2
_main:                                  ; @main
	mov x1, #12
	mov x2, #13
	add x0, x1, x2
	ret

x1=12; x2=13; x0=x1+x2;

PONTAPONTA

スタックを使う。

    .globl _main
    .p2align 2
_main:
    mov x5, 1
    mov x6, 2
    str x5, [sp, -16]!
    str x6, [sp, -16]!
    ldr x1, [sp], 16
    ldr x2, [sp], 16
    add x0, x1, x2
    ret;

[sp]はスタックトップを表す。

str x1, [sp, -16]!でx1の値をスタックの一番上に追加する。ldr x1, [sp], 16でスタックから一つ値を取り出してx1に投入する。

PONTAPONTA

str/ldrとstp/ldp

str/ldrの他に、stp/ldpでもスタックを操作できる。
stp/ldpは二つの値を同時に書き込み、二つの値を同時に読み出しができる。

そのため上記の記述は、以下のように書ける。

    .globl _main
    .p2align 2
_main:
    mov x5, 1
    mov x6, 2
    stp x5, x6, [sp, -16]!
    ldp x1, x2, [sp], 16
    add x0, x1, x2
    ret;

以下、こういう命令が用意されている理由。

16が16bytesって意味で、メモリ上で128bits分だけ移動することを表している。
ただx0~x28のレジスタは64bitsなので、一個づつスタックに入れると128bits中64bitsしか使われない。
そのため、二つのレジスタの値をまとめて128bitsにまとめてメモリ上に配置する命令が用意されている。

PONTAPONTA

上記の参考文献に基づいてCコンパイラを作っていると以下のような記述に出会う。これはグローバル変数を使わずにローカル変数でポインタを渡して実装しているために複雑になっている。

// stmt = expr ";"
Node *stmt(Token **rest, Token *tok) {
    Node *node = new_node(
            ND_EXPR_STMT,
            expr(&tok, tok),
            NULL
    );

    *rest = tok->next; // skip ";"
    return node;
}

この書き方について以下のような疑問を持つと思う。

  • expr(&tok, tok);のように呼び出してるのは何故か?
  • *rest = tok->next;な何を意味するのか?
PONTAPONTA

expr(&tok, tok);について、第一引数はtokのポインタを表す。tokはポインタなのでポインタのポインタを渡していることになる。ポインタのポインタが出てくるのですごい複雑に感じる。

この処理を理解する前に以下の処理を理解したい。

#include <stdio.h>

int main() {
    int a = 1;
    int *p = &a;
    int **pp = &p;

    int b = 2;
    int *q = &b;

    *pp = q; // p = q;

    printf("%d\n", *p); // 2

    return 0;
}

この時、*pp=q;p=qと等価なので、pはqに変り*p=2となっている。

PONTAPONTA

次に、exprの実装を見てみよう。

// expr = assign
Node *expr(Token **rest, Token *tok) {
    Node *node = assign(&tok, tok);
    *rest = tok;
    return node;
}

この時、expr(&tok, tok)を実行するとexpr内では

Token *rest = &tok

と宣言されたことに等しい。そのため、expr内でrestを書き換えると、呼び出し元のtokの指し示す先が変わることになる。

ここでassignについても同様の実装が行われているので、tokの指し示す先は変わる。そのため、最後に*rest = tok;の部分は、assignの部分で変わったtokの指し示す先をexprの呼び出しもとのstmtに伝搬させる処理となっている。

PONTAPONTA

また、stmtの*rest = tok->next; は最後のセミコロンがスキップされることをstmtの呼び出し元に知らせるための処理ということになる。最後の文字を最後にスキップをしない場合においてもtokの変更を呼び出し元に伝搬させないといけないため、常に*rest = tok;を書く必要がある。

ちなみに、exprについては、以下のように実装しても処理としては同じものになっている。

// expr = assign
Node *expr(Token **rest, Token *tok) {
    Node *node = assign(rest, tok);
    return node;
}

expr内でがtokを先に進めないため、assignが行ったtokの変化をそのままstmtに流せば良いからである。ただ、このような書き方は混乱するので、毎回2行書いたほうがいいと思う。

PONTAPONTA

以上、グローバル変数を使わずにポインタで処理の場所を伝搬させてるため複雑になっている。特に再帰下降構文解析はかなり複雑な再帰関数なので、難しく感じる。

まとめると、基本的な書き方の以下になる。

Node *f(Token **rest, Token *tok) {
    Node *node = new_node(
            ND_kind,
            g(&tok, tok), // 処理gによってtokの示す先が変わる。
            NULL
    );
    *rest = tok; // tokの示す先が変わったことをfの呼び出し元に伝搬させる。
    return node; // 木を返す。
}

誰かわかりやすい作図してほしい。

PONTAPONTA

ARM64のレジスタの解説記事。

https://www.mztn.org/dragon/arm6403reg.html

PONTAPONTA

x0, x1, ..., x30 汎用レジスタ。

  • 全て64bit
  • w0, w1, ..., w30 64bitの半分だけ使う。
PONTAPONTA
  • xzr 常に64bitのゼロが入ってる
  • wzr 常に32bitのゼロが入ってる
  • sp スタックポインタのスタックトップのアドレスを保持する。
  • wsp
  • PC
PONTAPONTA

spの使い方

スタックに42を突っ込んで、それを取り出す。

	.globl _main
	.p2align 2
_main:
	mov w20, 42
	str w20, [sp]
	ldr w0, [sp]
	ret
PONTAPONTA

スタックに、11, 22, 33を突っ込んで、それを取り出す。

	.globl _main
	.p2align 2
_main:
	mov w20, 11
	mov w21, 22
	mov w22, 33

	str w20, [sp, -16]!
	str w21, [sp, -16]!
	str w22, [sp, -16]!

	ldr w3, [sp], 16
	ldr w2, [sp], 16
	ldr w1, [sp], 16

	add w0, wzr, w1
	add w0, w0, w2
	add w0, w0, w3

	ret

str w20, [sp, -16]!はw20をスタックトップに突っ込んで、spを-16だけ更新する。
ldrはデータを取り出した後に、第3引数分だけspを更新する。

PONTAPONTA

上記の処理をspを動かさないように実装すると次のようになる。

	.globl _main
	.p2align 2
_main:
	mov w20, 11
	mov w21, 22
	mov w22, 33

	str w20, [sp]
	str w21, [sp, -16]
	str w22, [sp, -32]

	ldr w3, [sp, -32]
	ldr w2, [sp, -16]
	ldr w1, [sp]

	add w0, wzr, w1
	add w0, w0, w2
	add w0, w0, w3

	ret

strは!をつけないと値を更新しない。[sp, -16]でスタックトップ以外からも値を取り出せる。

PONTAPONTA

sub sp, sp, 16のようにして、spの値を手動で変更できる。上記と同じ処理は以下のようになる。

	.globl _main
	.p2align 2
_main:
	mov w20, 11
	mov w21, 22
	mov w22, 33

	sub sp, sp, 16
	str w20, [sp]
	sub sp, sp, 16
	str w21, [sp]
	sub sp, sp, 16
	str w22, [sp]

	ldr w3, [sp]
	add sp, sp, 16
	ldr w2, [sp]
	add sp, sp, 16
	ldr w1, [sp]
	add sp, sp, 16

	add w0, wzr, w1
	add w0, w0, w2
	add w0, w0, w3

	ret
PONTAPONTA

ローカル変数dについて
d = 11 + 22; d;
は以下のようなコードになる。

  .globl _main
  .p2align 2
_main:
  ; prologue
  stp x29, x30, [sp, -16]!
  mov x29, sp

  ; allocate space for local variables
  sub sp, sp, 416

  ; get address of local variable d and store it to stack
  sub x0, x29, 64
  str x0, [sp, -16]!

  ; store 22 to stack
  mov w0, 22
  str w0, [sp, -16]!

  ; set 11 to w0
  mov w0, 11

  ; load 22 to w1
  ldr w1, [sp], 16

  ; calculate w0 + w1 and set it to w0
  add w0, w0, w1

  ; load address of local variable d to x1
  ldr x1, [sp], 16

  ; set w0 to d
  str w0, [x1]

  ; get address of local variable d and set value d to w0
  sub x0, x29, 64
  ldr w0, [x0]
  
  ; epilogue
  mov sp, x29
  ldp x29, x30, [sp], 16
  ret 
PONTAPONTA

プロローグ

; prologue
stp x29, x30, [sp, -16]!
mov x29, sp

x29に関数呼び出し時点のspの一番上のポインタを保管し、spを一つ進める。
x29はこの関数の座標原点的なもので、変数はx29からの相対位置で特定する。
例えばこの関数中のローカル変数aはx29から16bytesズレた位置に保存され、ローカル変数bはx29から16bytesズレた位置に保存する等を行う。x29は性質上、この関数の終了時点まで変化させない。

spはスタックのトップのアドレスで、strやldrなどの実行時にずらす。

エピローグ

; epilogue
mov sp, x29
ldp x29, x30, [sp], 16
ret

spをx29の値に戻し、x29をスタックのトップの値に置き換えて、spを関数の呼び出し直後に戻し、retでspを関数の呼び出し元に戻す処理。ldrとretの必要性は関数呼び出しのアセンブリを勉強しないとわからないのでまだ完全には理解してない。

x30はリンクレジスタと呼ばれているが、現時点では何に使うかよくわからない。この処理については、str x29, [sp, -16]!ldr x29, [sp], 16としても正常に動作する。

PONTAPONTA

いろんなコンパイラが吐くアセンブリを見てると、以下のようなプロローグとエピローグを使っているものがある。

; prologue
stp fp, lr, [sp, -16]!
mov fp, sp
; epilogue
mov sp, fp
ldp fp, lr, [sp], 16
ret

実はx29にはfpという別名があり、x30にはlrという別名がある。エピローグやプロローグで使うためには可読性の観点かあらfplrを用いているらしい。

参考: https://zenn.dev/hidenori3/articles/c9053a76be641c

PONTAPONTA

fp, lr, spの解説

ARM64には汎用レジスタを32個持つ。その内、最後の3つには以下のような別名がついている。

x29 = fp
x30 = lr
x31 = sp, xzr

sp

stack pointer, x31

スタックの一番上のメモリアドレスの値が入っている。関数呼び出し中は処理の結果を一時的にスタックに保管するたびにspの値が更新される。

ちなみに、x31はldp/stpなどの命令と一緒に使われるときはspとして使われ、mov/add/subなどの命令と一緒に使われるときはxzrとして使われる。

fp

frame pointer, x29

関数が呼び出されたタイミングで、spがfpにコピーされる。その後、fpの値は同じ関数呼び出し内では変わらない。fpは関数のローカル変数の基準となる。

lr

link register, x30

blでジャンプした時、bl命令の次の命令のアドレスがlrに書き込まれる。ret命令が呼び出されると、lrのアドレスに戻ってくる。

PONTAPONTA

プロローグの解説

関数呼び出し時点でfplrの状態は以下のようである。

fp = 呼び出し元の関数のローカル変数の基準となるアドレス
lr = bl命令の次の命令のアドレス

関数の一番最初に以下の命令を実行する。この処理はプロローグと呼ばれる。

; prologue
stp fp, lr, [sp, -16]!
mov fp, sp

stp命令で上記のfplrをスタックに積んでおく。その後、mov命令でfpspのアドレスを書き込み、関数のローカル変数の基準とする。関数実行中はspを低いアドレス方向へ伸ばすように使って、必ず元のlrfpの値を壊さないようにする必要がある。

エピローグの解説

関数が終了するタイミング(ret命令が呼ばれるタイミング)ではレジスタを以下の状態に戻す必要がある。

fp = 呼び出し元の関数のローカル変数の基準となるアドレス
lr = bl命令の次の命令のアドレス

そのために、関数の一番最後では以下の命令を実行する。この処理はエピローグと呼ばれる。

; epilogue
mov sp, fp
ldp fp, lr, [sp], 16
ret

fpから関数呼び出し時点のspの値を書き戻す。そこから呼び出し元のfplrの値を取り出す。ret命令で関数呼び出し元に返る。

PONTAPONTA

x86_64の場合

x86_64の場合も考え方はARM64と変わらない。
x86_64の場合の解説は以下が詳しい。(図を用いて丁寧に説明されている)

https://www.sigbus.info/compilerbook#スタック上の変数領域

ARM64のレジスタとx86_64のレジスタは以下のような対応がある。

arm64 x86_64
sp rsp
fp rbp
lr スタックトップ

sp, fpは変わらないが、lrだけ少し違っている。x86_64にはlrレジスタに対応するレジスタはなく、代わりにスタックトップのアドレスが利用される。call命令が実行されたとき、スタックにはcall命令の次の命令のアドレスが積まれる。ret命令で戻る時には、スタックの一番上に積まれたアドレスを取り出して戻る。

x86_64のプロローグとエピローグを記載しておく。

; Prologue
push rbp           ; Save old base pointer
mov rbp, rsp       ; New base pointer is the old stack pointer

; ... function body ...

; Epilogue
mov rsp, rbp       ; Discard local variable space
pop rbp            ; Restore old base pointer
ret                ; Return
PONTAPONTA

Wikipediaのレジスタの記事

https://ja.wikipedia.org/wiki/レジスタ_(コンピュータ)

AMD64とARMのレジスタの特徴についてよくまとまってる。

PONTAPONTA

以下のように現在はARMの方がレジスタが多いらしい。
やはりARM最強か?


汎用レジスタの数はRISCでは多く、CISCでは少ないという差がある。2023年時点で最も有名といえるRISCアーキテクチャのARMとSISCアーキテクチャのx86では、32ビット版は16本と8本、64ビット版では31本と16本である。

PONTAPONTA

x86_64のレジスタ名に関する説明。
理解し難いレジスタ名であることは以下のように拡張を重ねたかららしい。
やはりARM最強か?


インテル社の8086系列のCPUは、このように拡張してきた経緯を持つ代表的なプロセッサである。8086CPUが誕生する前のインテルの8ビットCPU、8080では汎用レジスタを“a”, “b”, “c”…と名付けていた。これを拡張した8086の汎用レジスタは“ax”, “bx”, “cx”…となった(xはextendの略)。ところが、80386で32ビット化したため、レジスタの名前は“eax”, “ebx”, “ecx”…となった(eもextendの略)。さらに、AMD社がAMD64で64ビットに拡張した時には、レジスタ名は“rax”, “rbx”, “rcx”…となった。

PONTAPONTA

ポインタの足し算と引き算

int x = 11, y = 22, z = 33;
int *p = &x, *q = &y, *r = &z;

ポインタに数字を足せるし引ける。

int *b = q + 1;
printf("%p + 1 = %d\n", q, *b);

int *c = q - 1;
printf("%p - 1 = %d\n", q, *c);
PONTAPONTA

ポインタとポインタの相対位置を計算できる。

int a = p - r;
printf("%p - %p = %d\n", p, r, a);

ポインタとポインタは足し算できない。

int *d = p + q;  // ERROR
printf("%p + %p = %p\n", p, q, d);
PONTAPONTA

数値にポインタを足すことはできる。

int *b = 1 + q;
printf("1 + %p = %d\n", q, *b);

数値からポインタを引くことは出来ない。

int *c = 1 - q;  // ERROR
printf("1 - %p = %d\n", q, *c);
PONTAPONTA

この演算って代数としては何に分類されるんだろう。

PONTAPONTA

ARM64のアセンブリからC言語の関数を呼び出す方法。

func.c
int ret11() {
    return 11;
}

オブジェクトファイルに変換

$ gcc -c func.c // func.oが生成

アセンブリを書く。Appleの場合は関数の前に_(アンダーバー)をつけないといけないらしい。

main.s
  .global _main
  .p2align 2
_main:
  stp x29, x30, [sp, #-16]!
  bl _ret11
  ldp x29, x30, [sp], #16
  ret

コンパイルして実行

$ gcc -o main main.s func.o; ./main; echo $?
11
PONTAPONTA

単にblを呼び出すと処理が終了しない。必ずstp/ldpを実行しないとだめ。以下は処理が終了しない。

main.s
  .global _main
  .p2align 2
_main:
  bl _ret11
  ret

(なぜかはわからない。誰か教えて。)

PONTAPONTA

引数がある場合の呼び出し方法。

func.c
int add2(int a, int b) {
    return a + b;
}

x0とx1の値が関数の引数になる。

main.s
  .global _main
  .p2align 2
_main:
  stp x29, x30, [sp, #-16]!
  mov x0, 11
  mov x1, 22
  bl _add2
  ldp x29, x30, [sp], #16
  ret

(intだがx0に入れてOK。w0はx0の下のbitを使ってるだけなので)

PONTAPONTA

stp/ldpをstr/ldrにしても関数は呼び出せる。以下は正常に動作。

  .global _main
  .p2align 2
_main:
  str x29, [sp, #-16]!
  str x30, [sp, #-16]!
  bl _ret11
  ldr x30, [sp], #16
  ldr x29, [sp], #16
  ret

x29を省いても関数は呼び出せる。以下は正常に動作。

  .global _main
  .p2align 2
_main:
//  str x29, [sp, #-16]!
  str x30, [sp, #-16]!
  bl _ret11
  ldr x30, [sp], #16
//  ldr x29, [sp], #16
  ret

x30を省くとエラーになる。以下はエラーになる。

main.s
  .global _main
  .p2align 2
_main:
  str x29, [sp, #-16]!
//  str x30, [sp, #-16]!
  bl _ret11
//  ldr x30, [sp], #16
  ldr x29, [sp], #16
  ret

どうやらx30が重要らしい。

PONTAPONTA

コンパイラを作っていったらわかった。

x30はリンクレジスタである。リンクレジスタは、関数の呼び出し元のメモリアドレスが入っている。
mainの最後のretでmainの呼び出し元に返らないとプロセスが終了しないんだと思う。
なのでx30を保持する必要がある。

PONTAPONTA

アセンブリ言語での関数呼び出し

	.globl	_add2
	.p2align	2
_add2:
	sub	sp, sp, #16
	add	w0, w0, w1
	add	sp, sp, #16
	ret

	.globl	_main
	.p2align	2
_main:
	sub	sp, sp, #32
	stp	x29, x30, [sp, #16]
	mov	w0, #11
	mov	w1, #22
	bl	_add2
	ldp	x29, x30, [sp, #16]
	add	sp, sp, #32
	ret
PONTAPONTA

ARM64の場合を解説する。

関数呼び出しではblを用いる。
関数の引数が8個までは、x0~x7のレジスタを用いて引数を渡す。それ以降の引数はスタックを用いる。これはAAPCS64で仕様が定められている。
呼び出された関数でretが実行されると戻ってこれる。

PONTAPONTA

M1 Macのclangで可変長の引数を持つC言語のコードをアセンブリにしたら、どうやら可変長の部分はスタック渡しになっている。
どうやら、AppleのARM64は可変長引数をスタック渡しにする仕様があるみたい。

https://qiita.com/hotpepsi/items/bd1f496411a2df74b704

PONTAPONTA

以下のコードをM1 Macでclang -O0 -Sした。

int add_all(int n, int m, ...);
int main() { 
  int b = add_all(11, 22, 1, 2, 3);
  return 0;
}

結果がこれ。

	mov	x9, sp
	mov	x8, #1
	str	x8, [x9]
	mov	x8, #2
	str	x8, [x9, #8]
	mov	x8, #3
	str	x8, [x9, #16]
	mov	w0, #11
	mov	w1, #22
	bl	_add_all

変数nmはレジスタ渡しが行われており、それ以降の変数はスタックに入っている。
M1 MacでC言語から可変長引数のアセンブリコードを実行したい場合は注意が必要。(これがApple特有の呼び出し規則なのか、ARM64全体の呼び出し規則なのかは謎である。)

PONTAPONTA

混乱したC言語の書き方。

int test(int x (int y)) {
    return x + 22;
}

int main() {
    return test(11);
}

この書き方はコンパイルが通る。

PONTAPONTA

test関数の使い方。

int add22(int x) {
    return x + 22;
}

int test(int x (int y)) {
    return x(11);
}

int main() {
    return test(add22);
}
PONTAPONTA

ポインタは64bit

#include <stdio.h>

int main() {
    int x = 11;
    printf("sizeof int x: %lu\n", sizeof(x)); // 4
    printf("pointer size: %lu\n", sizeof(&x)); // 8

    long y = 11;
    printf("sizeof long y: %lu\n", sizeof(y)); // 8
    printf("pointer size: %lu\n", sizeof(&y)); // 8
}
PONTAPONTA

配列の面白いアクセス方法。

int main() {
    int x[3];
    2[x] = 11;
    return x[2];
}
PONTAPONTA

以下が成り立つらしい。

2[x] = *(2+x) = *(x+2) = x[2]
PONTAPONTA

グローバル変数

int hello = 11;
int world;

static int hoge = 22;
static int fuga;

この四つのグローバル変数の宣言方法についてアセンブリレベルの違いを理解したい。

PONTAPONTA

hellohugeは初期化されているので、.dataセクションに配置される。
アセンブリレベルでは以下の違いが出る。

    .section    __DATA,__data
    .globl    _hello
    .align    2
_hello:
    .long    11
    .section    __DATA,__data
    .align    2
_hoge:
    .long    22

.globalの宣言がされていないと、同じファイルからしかアクセスできない変数となる。

PONTAPONTA

以下二つの違いは複雑。

int world;
static int fuga;

未定義な変数は.bssセクションに配置するらしい。.bssセクションに配置する方法は二つ?あって、
.commを用いるものと、.zerofillを用いるものがある。

.commで宣言するとグローバル変数になって、.zerofillで宣言するとそのファイルでしか使えない変数になるんだと思う。

なので上記のコードは次のようになる。

.comm	_world,4,2                      ; @world
.zerofill __DATA,__bss,_fuga,4,2        ; @fuga
PONTAPONTA

ただ、.zerofillで宣言したものをglobalにすることは可能らしく、以下のコードも正しく動作する。

.globl _world
.zerofill __DATA,__bss,_world,4,2
PONTAPONTA

グローバル変数の練習。以下のコードをコンパイルする。

int hello = 11;
int main() {
    return hello;
}

次のようになる。

	.data
	.globl	_hello
	.p2align	2
_hello:
	.long	11

	.text
	.globl	_main
	.p2align	2
_main:
	adrp	x1, _hello@PAGE
	ldr	w0, [x1, _hello@PAGEOFF]
	ret

_hello@PAGEは_helloが格納されるページアドレスの最初のアドレスを返す。
_hello@PAGEOFFは_helloがページのどの位置にあるのか、その相対位置を返す。

ldrの第二引数のリストは足し算されるので、_helloが取り出せる。
より冗長に書くのであれば以下のように書ける。

	adrp	x1, _hello@PAGE
	add	x1, x1, _hello@PAGEOFF
	ldr	w0, [x1]
PONTAPONTA

sprintf

文字列を生成する関数。

使い方

#include <stdio.h>

int main() {
    char output[20];

    int x = 11;
    int y = 22;
    int z = x + y;

    sprintf(output, "%d + %d = %d", x, y, z);
    printf("%s\n", output);

    return 0;
}
PONTAPONTA

文字列をグローバル変数に展開する方法。

	.section	__TEXT,__text,regular,pure_instructions
	.globl	_main
	.p2align	2
_main:
	sub	sp, sp, #16
	str	wzr, [sp, #12]
	adrp	x8, l_.str@PAGE
	add	x8, x8, l_.str@PAGEOFF
	str	x8, [sp]
	ldr	x8, [sp]
	ldrsb	w0, [x8, #3]
	add	sp, sp, #16
	ret

	.section	__TEXT,__cstring,cstring_literals
l_.str:
	.byte	100
	.byte	101
	.byte	102
	.byte	103
	.byte	104

データを並べる。

PONTAPONTA

色々な文字列の宣言方法。

#include <stdio.h>

int main() {
    char *s1 = "ABCD"; // 普通の文字列を宣言
    printf("%s\n", s1); // ABCD

    char *s2 = "\x41\x42\x43\x44"; // 文字コードを8進数で指定して文字列を宣言
    printf("%s\n", s2); // ABCD

    char *s3 = "\101\102\103\104"; // 文字コードを16進数で指定して文字列を宣言
    printf("%s\n", s3); // ABCD

    char s4[] = {65, 66, 67, 68, 0}; // 文字コードを10進数で指定して文字列を宣言
    printf("%s\n", s4); // ABCD
}
PONTAPONTA

GNU C Compilerだと以下の書き方ができる。

int main() {
    return ({
        11;
        22;
        33;
    });
}

clangでコンパイルするとwarningは出るがコンパイル自体はできる。

PONTAPONTA

構造体の配列はメモリに連続に並ぶ。

#include <stdio.h>

struct person {
  int age;
  int height;
} person[2];

int main() {
  int *p = person;

  p[0] = 10;
  p[1] = 150;
  p[2] = 20;
  p[3] = 180;

  for (int i = 0; i < 2; i++) {
    printf("Person %d: %d, %d\n", i, p[i * 2], p[i * 2 + 1]);
  }
}
Person 0: 10, 150
Person 1: 20, 180

未定義動作だと思う。MacのClang v11.1.0では連続に並んでた。

PONTAPONTA

複数の配列を持つ構造体は、その配列の要素が連続に並ぶ。

#include <stdio.h>

struct person {
  int age[2];
  int height[2];
} person;

int main() {
  int *p = &person;

  p[0] = 10;
  p[1] = 150;
  p[2] = 20;
  p[3] = 180;

  for (int i = 0; i < 2; i++) {
    printf("Person %d: %d, %d\n", i, p[i * 2], p[i * 2 + 1]);
  }
}

未定義動作だと思う。

PONTAPONTA

structとunionとenumのタグは全て変数名が同じ名前空間に割り当てられる。

struct t {
  int x;
  int y;
};

union t {
  int x;
  int y;
}; // error

enum t {
  x,
  y
}; // error

上記のような同じタグ名の宣言はできない。

PONTAPONTA

一方でローカル変数とタグ名は別の名前空間に存在するため、同じ名前が可能である。

struct t {
  int x;
  int y;
};

int main() {
  struct t a;
  a.x = 1;

  int t = 2;
  return a.x + t;
}

PONTAPONTA

typedefで定義した型はローカル変数と同じ名前空間に割り当てれる。そのため、以下のコードは正常に動作する。

struct t {
  int a, b;
};
typedef struct t t;

構造体のタグ名とtypedefの型名を同じに出来る。

typedefで定義した型名はローカル変数と同じ名前空間に割り当てられるため、以下のコードはエラーになる。

typedef int t;
t t = 22;

t x = 22;とすればコンパイルが通る。

PONTAPONTA

gccだと通るけど、clangだと通らないコード。

	.globl	main
main:
	movl	$11, %edi
	movsxd	%edi, %rax
	ret

movsxdはgccだと使えるけど、clangだとエラーになる。

PONTAPONTA

movsxdは、32bitのレジスタから64bitに符号拡張する命令である。

movsxdはIntel記法の命令である。上記のアセンブリはAT&T記法なので本来はmovsxdは使えないはずである。なので、clangのようにエラーになるのが正しく?、gccは親切で通してくれている?[要出典]

PONTAPONTA

AT&T記法の32bitから64bitの符号拡張は、movslqを使う。そのため以下のように書けばgccでもclangでもエラーにならない。

	.globl	main
main:
	movl	$11, %edi
	movslq	%edi, %rax
	ret
PONTAPONTA

intlongがあるのに、int64_tがあるのはなぜか。

PONTAPONTA

64bitのCPUの場合、一般的にintは32bitでlongは64bitである。

32bitのCPUの場合、一般的にintは32bitでlongは32bitであるが、longを64bitとすることもある。

PONTAPONTA

C言語は、CPUが16bitの時代から存在してるので、intlongのbitサイズを特に定めているわけではない。longintより大きいとして定めているだけである。

そのため、明示的にbitサイズを定める型が必要になってint64_tがある。

PONTAPONTA

C言語の仕様は以下のように定めている。

short: 最小16bit
int: 最小16bit
long: 最小32bit
long long: 最小64bit

PONTAPONTA

64bit CPUの場合

short: 16bit
int: 32bit
long: 64bit
long long: 64bit

サーバーやデスクトップパソコンだと32bitはなくなったためlong longを使う機会はない。全てlongで良い。マイコンを扱う場合はまだ16bitや32bitの場合があるのでlong longを使う機会がある。

PONTAPONTA

次の二つの違い。

char *x[3];
char (*x)[3];

覚えるしかない気がする。

PONTAPONTA
char *x[3];

「charへのポインタ変数」の配列(長さは3)
64bitシステムだったら64bit * 3のスタックを消費する。

PONTAPONTA
char (*x)[3];

「charが3つの配列」へのポインタ。
64bitシステムだったら64bitのスタックが消費される。

PONTAPONTA

複合技も可能

char (*x[2])[3];

「charが3つの配列」へのポインタの配列(長さは2)
64bitシステムだったら、スタック領域を128bit消費する。

C言語で最難関の文法かも。

PONTAPONTA

一つ覚え方がある。main関数の引数はこうなってる。

char *argv[]

これが「charへのポインタ変数」の配列で、オプションの数だけポインタが作れられることは直感的にわかるはず。

PONTAPONTA

何に使うかわからない書き方。

void *x;
PONTAPONTA

この書き方はvoid型のポインタと言ってCでよく使われるっぽい。

void *x;

ポインタが指し示す値の型を情報を消すのに使われるみたい。
入ってる先がintだったら、キャストしてから取り出すみたい。以下みたいな感じ。

*(int *) x;

一回キャストしてから取り出してるのでintとして取り出せる。

PONTAPONTA

以下のy=xはdeep copyされる。

int main() {
  union {
    struct {
      int a, b;
    } c;
  } x, y;
  x.c.b = 3;
  y.c.b = 5;
  y = x;
  return y.c.b; // 3
}

構造体とunionのコピーはビット単位で行われるので、deepcopyされる。

PONTAPONTA

shallow copyにしたい場合は、ポインタにすれば良い。

int main() {
  union {
    struct {
      int a, b;
    } *c;
  } x, y;
  x.c->b = 3;
  y = x;
  x.c->b = 5;
  return y.c->b; // 5
}

deep copyとshallow copyを明示的に使い分けできる。

PONTAPONTA

ARMにおける大きな数の取り扱い。
mov命令でx0に65536より大きい数を代入することはできない。

mov x0, 65537

これを実行するとexpected compatible register or logical immediateというエラーが出る。

ちなみにw0には65536より大きい数を代入することができる。

mov w0, 65537
PONTAPONTA

x0に大きい数を代入するには、movk命令を用いる。

65537を代入するには以下のようにする。

mov x0, 1
movk x0, 1, lsl 16

上記をC言語ぽくかくと次のようになる。

x = 1 + (1 << 16);
PONTAPONTA

レジスタの下位数bitを符号拡張する方法。

x86_64では以下のようにする。

movsbl %al, %eax // from 8bit to 32bit
movswl %ax, %eax // from 16bit to 32bit
movsxd %eax, %rax // from 32bit to 64bit

arm64では次のようにする。

sxtb w0, w0 // from 8bit to 32bit
sxth w0, w0 // from 16bit to 32bit
sxtw x0, w0 // from 32bit to 64bit
PONTAPONTA

以下のコードのように使う。

  .global _main
  .p2align 2
_main:
  mov w0, 0xFF0a
  sxtb w0, w0
  ret

sxtbで下位8bit (0xa)が取り出される。

PONTAPONTA

アセンブリの割り算。
以下は、x86_64で10%3をするコード

mov $10, %rax
mov $3, %rdi
cqo
idiv %rdi
mov %rdx, %rax
PONTAPONTA

rax = 10, rdi = 3の時に、idiv rdiを実行すると、rax = 3, rdx = 1になる。
rdxをraxに持ってきて余りが計算できる。

一回の命令で二つ計算できてお得だね。

PONTAPONTA

ARM64の場合は、sdivudivを使う。

sdivは符号付き整数の割り算
udivは符号なし整数の割り算

PONTAPONTA

ARM64の比較

以下の命令でx0とx1の比較ができる。

cmp  x0, x1 # compare

比較すると、フラグが立つ。フラグの0との比較結果に応じてx0に0 or 1の値をいれる。

cset x0, eq # ==
cset x0, ne # !=
cset x0, lt # <
cset x0, le # <=

eqを指定すると、x0に0 or 1の値をいれる。

PONTAPONTA

論理積と論理和

#include <stdio.h>

int main() {

  printf(" 0 && 0 = %d\n", 0 && 0);
  printf(" 0 && 1 = %d\n", 0 && 1);
  printf(" 1 && 0 = %d\n", 1 && 0);
  printf(" 1 && 1 = %d\n", 1 && 1);

  printf(" 0 || 0 = %d\n", 0 || 0);
  printf(" 0 || 1 = %d\n", 0 || 1);
  printf(" 1 || 0 = %d\n", 1 || 0);
  printf(" 1 || 1 = %d\n", 1 || 1);

  return 0;
}
PONTAPONTA

0 -> Flase
0以外 -> True

&&||は論理積と論理和である。
これらはint型を返す。

PONTAPONTA

lhs && rhsと書いた時は、以下のような感じアセンブリにする。

x0 = expr(lhs)
if x0 == 0: jmp .L.false
x0 = expr(rhs)
if x0 == 0: jmp .L.false
x0 = 1
jmp .L.end
.L.false: x0 = 0
.L.end: 

(なんだこの謎言語。。)

PONTAPONTA

lhs || rhsと書いた時は、以下のようにアセンブリにする。

x0 = expr(lhs)
if x0 != 0: jmp .L.true
x0 = expr(rhs)
if x0 != 0: jmp .L.true
x0 = 0
jmp .L.end
.L.true: x0 = 1
.L.end: 
PONTAPONTA

GOTO文

int main() {
  int i = 0;
  goto step2;

  step1: i ++;
  step2: i += 2;
  return i; // 2
}
PONTAPONTA

GOTOのラベルは変数やタグ名と名前空間が異なる。

int main() {
  struct i {int i;} i;
  i.i = 0;
  goto i;
  i: i.i +=2;
  return i.i; // 2
}

(このコードおもろくない?)

PONTAPONTA

シフト演算

x = 1;
x << 2; //4
x <<= 2;
x; // 4

y = 16;
y >> 2; // 4
y >>= 2;
y; // 4
PONTAPONTA

右シフト(x0=x0>>x1)は、

asr x0, x0, x1

右シフトにはasrとは別にlsrがある。これは符号の取り扱いが違う。

-1>>1について、
asrだと-1になる。
lsrだと2147483647になる。

PONTAPONTA

integer constant expression 整数定数式

以下のコードはコンパイルできない。

#include <stdio.h>

int main() {
  int i = 1;
  switch (i) {
  case i:
    printf("Hello");
    break;
  }
  return 0;
}

理由はcase iのiの部分が整数定数式でないから。iを整数定数式にすればコンパイルが通る。
C言語の式でコンパイル時点で値が決まるものを整数定数式と呼ばれている。

PONTAPONTA

sizeofも整数定数式なので以下のようなコードはコンパイル通る。

#include <stdio.h>
int main() {
  int i = 1;
  switch (4) {
  case sizeof(i):
    printf("Hello");
    break;
  }
  return 0;
}

他にも四則演算や3項演算は整数定数式である。

PONTAPONTA

配列宣言時のサイズ指定にも整数定数式が使える。

int x[sizeof(int)];

ちなみに、(私のコンパイラは)C言語の配列のサイズは実行開始時には完全に定まってないといけない。

ただ、最近のCは定まってなくていいらしく、Clangとかは以下のコードを正常に処理できる。

int a;
scanf("%d", &a);
int x[a];
PONTAPONTA

enumの初期値も整数定数式が使える。

enum { sz=sizeof(int) };
PONTAPONTA

プリプロセスにおいても、整数定数式の評価が行われる。

以下のような書き方が可能。

#if 1+1=2
  #include<stdio.h>
#endif
PONTAPONTA

グローバル変数についても整数定数式の評価が行われる。

以下のような書き方をした場合、実行バイナリのデータ領域には2が入ってる。

int a = 1 + 1;
int main() { return a;}
PONTAPONTA

グローバル変数の宣言とか整数定数式とかプリプロセスとか実装して思ったけど、C言語って式がどのタイミングで評価されるかを隠蔽されてるんだなぁ。この評価タイミングの隠蔽って偶然そうなっちゃったのかな。それとも言語設計者が意図的に隠蔽してるかなぁ。

PONTAPONTA

memsetをアセンブリで実装する方法。

PONTAPONTA

x86_64には、以下の命令がある。

rep stosb

以下の命令と等価である。

memset(%rdi, %al, %rcx)

alは8bitのレジスタである。(raxの下位8bit)
alに指定した値をrdiからrcx個だけ書き込む。

メモリを一気に初期化する際に使える。

PONTAPONTA

ARM64にはこの命令がないため、自前で実装する必要がある。

.L.memset.loop.1:
    cmp x1, 0
    beq .L.memset.end.1
    strb w2, [x0]
    add x0, x0, 1
    sub x1, x1, 1
    b .L.memset.loop.1
.L.memset.end.1:

x0からx1個だけx2の下8bitを書き込む。

PONTAPONTA

以下の二つが同じ

      println("    mov x0, %d", node->var->offset);
      println("    add x0, fp, x0");
      println("    mov x1, 0");
      println("    mov x2, %d", node->var->ty->size);
      println("    bl _memset");

      println("    mov x0, %d", node->var->offset);
      println("    add x0, fp, x0");
      println("    mov x1, %d", node->var->ty->size);
      println(".L.loop.%d:", c);
      println("    cmp x1, 0");
      println("    beq .L.end.%d", c);
      println("    strb wzr, [x0]");
      println("    add x0, x0, 1");
      println("    sub x1, x1, 1");
      println("    b .L.loop.%d", c);
      println(".L.end.%d:", c);
PONTAPONTA

グローバル変数の宣言時に使える計算

PONTAPONTA

C言語のグローバル変数では、以下のような計算が可能である。

int a[] = {22 - 11, 11 + 11};
int *b = a + 1;

int main() {
  return *b;
}

グローバル変数の宣言は以下のように、データとしてバイナリに静的に書き込まれる。

	.section	__DATA,__data
	.globl	_a
	.p2align	2
_a:
	.long	11
	.long	22

	.globl	_b
	.p2align	3
_b:
	.quad	_a+4
PONTAPONTA

グローバル変数の宣言では、整数定数式と他のグローバル変数へのポインタが計算として使える。コンパイラは、コンパイル時にこれらの計算を行ってバイナリに直接データを書き込む。

PONTAPONTA

グローバル変数とローカル変数は全くの別物であることがよくわかる。

グローバル変数はプログラムに静的に書き込まれているので、コードがメモリに展開されるのと同時にメモリに展開され、コードが終了するまでメモリに生存し続ける。ローカル変数は関数呼び出し時にスタックに積まれるだけ。全く別物。

PONTAPONTA

ローカル変数がスタックに積まれていることがわかるコード

PONTAPONTA

以下のコードの結果は11になる。(当然、未定義動作であるが。)

int test(int x) {
  return 0;
}

int test2() {
  int arr[] = {};
  return arr[0];
}

int main() {
  test(11);
  return test2(); // 11
}

mainからtestが呼ばれた時に、test用のスタックポインタが用意される。
このtestのスタックポインタは、mainのスタックポインタから相対的に決定される。
同様にtest2のスタックポインタも、mainのスタックポインタから相対的に決定される。

この時、testとtest2のスタックポインタの値は等しい。testのローカル変数xはスタックの一番上に積まれる。そのため、test2でスタックの一番上に積まれた値を返すと、testのスタックで積まれた値が取り出せる。

この例は、ローカル変数のスタックの仕組みがよくわかる良い例だと思う。

もちろん、上記の説明は全て実装依存である。たまたま私のパソコンにインストールされているgccがこういう動作をしていただけ。

PONTAPONTA

発展型。以下のコードは11を返す。(当然未定義動作だが)

int test(int x) {
  int y = 22;
  return 0;
}

int test2() {
  int arr[] = {};
  return arr[-1] - arr[0];
}

int main() {
  int a = 11;
  test(a);
  int b = test2();
  return b; // 11
}

test関数の変数x, yはこの順番でスタックに積まれる。test2ではtest関数で積まれた変数x, yを取り出して引き算して返している。

(私のパソコンでは)スタックはメモリが大きい方から始まって小さい方に伸びる。詳しい説明は以下の記事の「コラム: スタックの伸びる方向」を参照

https://www.sigbus.info/compilerbook#スタック上の変数領域

なので、配列arrを用いてスタックの値を取り出すときは、添え字は負の方向に伸びることになる。

そのため、arr[0]はスタックの一番上に積まれた変数xの値を取り出し、arr[-1]はスタックの二番目に積まれた変数yの値を取り出す。なのでarr[-1] - arr[0]は11を返す。

PONTAPONTA

Cって、こういうのもエラーにできないのか。

int *func(){
  int a[] = {0, 1, 2, 3, 4};
  return a;
}

int main()
{
  int *a = func();
  return a[0] + a[1] + a[2] + a[3] + a[4];
}

初見殺しすぎない?

PONTAPONTA

Variable Length Array (VLA)やalloca()を除き、C言語は関数内のローカル変数が利用するメモリのサイズはコンパイル時に確定する。抽象構文木を作るタイミングで、関数内のローカル変数のリストを作成しする。コード生成のタイミングでそのリストを参照しながら、関数内のローカル変数の位置を確定させる。

関数内のローカル変数はスタックを用いるだけなので、コンパイル時にサイズが確定してる必要は必ずしもない。それを確定させるようにしている。これは、Cの言語仕様の工夫点なのかもしれない。。

PONTAPONTA

C言語のGOTO文

PONTAPONTA

確かにC言語のGOTO文は悪だけど、使わないといけない場合があるらしい。

エラーハンドリングとか、メモリの解放とかでは使わないといけない場合があるらしい。(C言語にTry/CatchがないこともGOTO文を使う場合がある一つの原因らしい。)

PONTAPONTA

Rustでカーネル書いてる人はResult型でなんとかしてるのかなぁ
Result型って確かに安全だけど、すごく大変な気がするけどなぁ

PONTAPONTA

C言語における宣言

PONTAPONTA

以下のように宣言が可能。

int main() {
  struct {
    int a;
    char b;
  } x[2] = {1 , 2, 3, 4};
  return x[0].a + x[0].b + x[1].a + x[1].b; 
}

未定義動作かも

PONTAPONTA

宣言の際に最後にカンマを付与できる。

int main() {
  int x[] = {1, 2, 3, 4,};
  return x[0] + x[1] + x[2] + x[3];
}
PONTAPONTA

以下のような宣言も可能。

#include <stdio.h>

typedef struct {
  char a, b[];
} t;
t gvar = {11, 'H', 'e', 'l', 'l', 'o', 0};

int main() { 
  printf("%s\n", gvar.b); // Hello
  return gvar.a; // 11
}

これは未定義ではないらしい。

これってほんとに未定義じゃないのか?
構造体ってきりがいいとこまで切り上げるとかあった気がするし、その上でエンディアンの違いとか考えると、なんか未定義になっちゃう気がするけど。

これがエンディアンが違うCPUにCを移植する際はこの辺面倒くさそう。

PONTAPONTA

.data.bssの違い。

グローバル変数宣言したとき、初期値があるものは.dataに展開される。
未定義のものは.bssに置かれる。

PONTAPONTA

未定義なグローバル変数を定義する。

int y[10];

上記のこのコードをARM64のアセンブリに直すと以下のようになる。

	.globl _y
	.zerofill __DATA,__bss,_y,40,2

40と2の意味を理解したい。(これを理解するには.p2alignを理解しないといけない気がする。)

PONTAPONTA

externについて

externは外部のファイルで定義されたグローバル変数と関数が使えるようにする構文

PONTAPONTA

最も簡単な例。

file1.c
int x;
file2.c
extern int x;

file1.cで定義された変数xがfile2.cで使えるようになる。

PONTAPONTA

C言語のコンパイルプロセスにおいて、オブジェクトファイルが生成されたタイミングではexternは結合されてない。複数のオブジェクトファイルをリンクするタイミングで、externが解決される。

externはC言語からアセンブリを呼び出す際にも使われる。

PONTAPONTA

alignofalignasについて

alignasは宣言時に使う。
alignofはアライメントの確認に使う。

PONTAPONTA
alignas(256) int j;

このとき、変数jのために256Bytesが用意されて、初めの4bytesに値が格納される。

PONTAPONTA

staticについて

C言語のstaticは以下の3パターンがある。

  1. 関数内部でローカル変数の宣言時にstaticをつけることで、データセグメントに変数を配置できる。
  2. 関数宣言時にstaticをつけることで、その関数をファイル内でしか呼び出せなくなる。
  3. グローバル変数の宣言時にstaticをつけることで、その変数をファイル内でしか呼び出せなくなる。
PONTAPONTA
  1. 関数内部でローカル変数の宣言時にstaticをつけることで、データセグメントに変数を配置できる。

以下のように使う。

int main() {
  static int a = 11;
  return a;
}

このように書くと、変数aはデータセグメントに配置される。コンパイラ的には、ほとんどグローバル変数を宣言しているのと変わらない[要出典]。そのため、右辺に来れるのは整数定数式のみだったりする。つまり、以下のようなコードは許されない。

int main() {
  int b = 11;
  int c = 22;

  static int a = b + c; // error: initializer element is not a compile-time constant
  return a;
}

staticによるローカル変数の宣言で最もメジャーな使い方はカウンターだと思う。以下のように書く。

int counter() {
  static int count = 0;
  return ++count;
}

int main() {
  int c;
  for (int i = 0; i < 10; i++) {
    c = counter();
  }
  return c;
}

初見だと毎回count = 0が実行されるのかと思ってしまうが、staticがついているローカル変数の宣言は、コンパイル時に.dataセグメントに値が準備されるだけで、プログラム実行時には何ら影響を与えない。

ちなみに、staticなローカル変数のスコープはその関数内で閉じるので、以下のような書き方は許されない。

int counter() {
  static int count = 0;
  return ++count;
}

int main() {
  for (int i = 0; i < 10; i++) {
    counter();
  }
  return count; // `count' undeclared
}
PONTAPONTA
  1. 関数宣言時にstaticをつけることで、その関数をファイル内でしか呼び出せなくなる。
  2. グローバル変数の宣言時にstaticをつけることで、その変数をファイル内でしか呼び出せなくなる。

2と3は簡単で、staticをつけると、アセンブリレベルで.globalという記述がなくなって、.localが増えるという違いしかない。基本的にはリンカーがオブジェクトファイルを組み合わせるときに、指示を出してるだけ。

以下が例。

static int a = 11;
static int func1() {
  return 22;
}

int b = 33;
int func2() {
  return 44;
}

上記のC言語をARM64向けにコンパイルすると大体以下のようなアセンブリが出てくる。

	.data
	.p2align 2
a:
	.long 11

	.text
	.p2align 2
func1:
	mov w0, #22
	ret

	.data
	.globl _b
	.p2align 2
_b:
	.long 33

	.text
	.globl _func2
	.p2align 2
_func2:
	mov w0, #44
	ret

主な違いは、staticがついてないグローバル変数と関数は.globl _b.globl _func2のようにグローバルであることが明記されている。

基本的には名前空間の汚染を防ぐのに使われる。

PONTAPONTA

複合リテラル compound literals

PONTAPONTA

配列のポインタの宣言

int *arr = (int []) {1, 2, 3};
PONTAPONTA

構造体の宣言

typedef struct Tree {
  int val;
  struct Tree *lhs;
  struct Tree *rhs;
} Tree;

Tree root = (Tree) { 11, 0, 0 };
Tree proot = &(Tree) {22, 0, 0};
PONTAPONTA

以下のコードがなぜかコンパイルに通る。

(int){3} = 5;

複合リテラルは左辺値らしい。謎。

PONTAPONTA

M1 Macの可変長引数の関数呼び出し

x86_64と全然違くて苦戦した。

PONTAPONTA

以下のような関数を、M1 Macのアセンブリから呼び出す方法を解説する。

#include <stdarg.h>

int add_all(int n, ...) {
  va_list ap;
  va_start(ap, n);
  int sum = 0;
  for (int i = 0; i < n; i++) sum += va_arg(ap, int);
  va_end(ap);
  return sum;
}

つまり、以下のコードのアセンブリをかく。

int add_all(int n, ...);
int main() { return add_all(3, 11, 22, 33); }

これがわかると、アセンブリからC言語のprintfが呼び出せるため非常に便利。

PONTAPONTA

固定長の引数が8個以下の場合は、全てレジスタで渡す。8個を超える場合は超えた分をスタック渡しする。
また、可変長の引数は全てスタック渡しする。

上記の例だと、x0に変数nを入れて、数値11, 22, 33はスタックに入れる必要がある。
図で示すと以下のようになる。

レジスタ:

x0 = 3

スタック:

--- sp + 32

--- sp + 24
33
--- sp + 16
22
--- sp + 8
11
--- sp

PONTAPONTA

このようにスタックに値を詰めていく際には、ARM64のアライメントは16bytesである[要出典]ことに注意しないといけない。(16bytesが強制されていると勝手に思っている。ソースはない。)
特にstr x0, [sp, -8]!みたいな感じで、値を8bytesごとに詰めていくことはできない。

対策として、以下のような方法が考えられる。

sub sp, sp, 32 // 変数が3つなので24bytesとなるはずだが、切り上げて32bytesを用意する。

mov x0, 1
str x0, [sp, 0]

mov x0, 2
str x0, [sp, 8]

mov x0, 3
str x0, [sp, 16]

mov x0, 3
bl _add_all

add sp, sp, 32

アライメントが16bytesであるということは、spが16の倍数であれば良いというだけなので、上記のように初めに32bytes確保してから書き込むという手がある。

PONTAPONTA

もう一つの方法として、stpを用いて二つの値を書き込むという手段もある。

mov x0, 3
stp x0, x1, [sp, -16]!

mov x0, 1
mov x1, 2
stp x0, x1, [sp, -16]!

mov x0, 3
bl _add_all

add sp, sp, #32

やってることは同じ。

PONTAPONTA

コード生成器の実装方法

以下のコードをアセンブリにする際のコード生成機の実装方法を紹介する。

int add_all(int n, ...);
int main() { return add_all(3, 11, 22, 33); }

関数の引数部分は、以下のような木構造になる。

args
└── arg1
    ├── value: 3
    └── next
        └── arg2
            ├── value: 11
            └── next
                └── arg3
                    ├── value: 22
                    └── next
                        └── arg4
                            ├── value: 33
                            └── next: None

この木構造から以下のような状態を作る。

レジスタ:

x0 = 3

スタック:

--- sp + 32

--- sp + 24
33
--- sp + 16
22
--- sp + 8
11
--- sp

これは再帰関数を用いて関数の引数を右から左で評価していく戦略を取ると、綺麗に実装できる。
なぜなら左から右に評価していくと、最初に評価した3という値をどこか(スタックか使ってないレジスタ)に保管しておく必要があるためである。
右から左に評価していく場合は、可変長引数を評価したのちに、レジスタに配置すべき値をスタックを使いながら評価できるためである。

ちなみに、C言語における関数の引数の評価順序は未定義らしい。つまりどちらから評価してもいいらしい。ただ、GCCとVisualStudioは右から左に評価しているようである。

https://akkkix.hatenablog.com/entry/2016/05/13/223147

ちなみに私のM1 Macに入っているclangで、clang -S -O0出てくるアセンブリは左から右に評価している。

PONTAPONTA

以下のように二つの再帰関数を用いて実装すると綺麗に実装できる。

// 可変長引数の部分をスタックに配置。(33->22->11の順に評価する。)
static int push_vargs(Node *args, int varg) {
  if (!args) {
    int align = align_to(varg * 8, 16); // 最初にspを動かして可変長引数の領域を確保する。
    println("    sub sp, sp, %d", align); // 関数呼び出し後にspは戻すためにalignを返す。
    return align;
  }

  int align = push_vargs(args->next, varg + 1);
  gen_expr(args);
  println("    str x0, [sp, #%d]", varg * 8);
  return align;
}

// 固定長の部分を評価して、スタックに配置する。(3だけ評価する。)
static int arrange_args(Node *args, int carg, int const_nargs) {
  if (carg >= const_nargs) {
    int varg = 0;
    int align = push_vargs(args, varg);
    return align;
  }

  int align = arrange_args(args->next, carg + 1, const_nargs);
  gen_expr(args); // 可変長引数の評価の後に固定長の引数を評価する。
  push(); // 関数呼び出し前でレジスタに配置するため、評価結果を保持する。
  return align;
}

上記の関数は以下のように呼び出す。

    case ND_FUNCALL: {
      println("; gen_expr: ND_FUNCALL");

      int const_nargs = 0;
      for (Type *param = node->func_ty->params; param; param = param->next) {
        const_nargs++;
      }
      int carg = 0;
      int align = arrange_args(node->args, carg, const_nargs);
      for (; carg < const_nargs; carg++) {
        pop(argreg64[carg]); // 引数の結果をレジスタに配置する。
      }
      println("    bl _%s", node->funcname);
      println("    add sp, sp, %d", align);

引数が浮動小数点数の場合もこれをベースに実装可能だと思う。

PONTAPONTA

この実装に限らない話だけど、連結リストを処理する時に、根から処理する場合はFor文で実装すると綺麗に実装できて、葉から処理する場合は再帰で実装すると綺麗に実装できる(気がする)。

この考えを一般の木構造へ展開する場合は、それぞれBFSとDFSが対応する。
木構造をBFSで処理する場合にFor文を選ぶか再帰を選ぶか、DFSで処理する場合にFor文を選ぶか再帰を選ぶかは、実装する際に選択が迫られると思う。その際に以下の表を覚えておくと良いかもしれない。

BFS DFS
For文 Queueを用意する Stackを用意する
再帰 通常不適切 追加のデータ構造が通常必要ない

再帰下降構文解析で構文解析した木構造は、木の葉側の演算の優先度が高い。そのためDFSで処理すると追加のデータ構造を必要としない。そのため、chibiccではcodegen.cで再帰関数を書いてるのだと思う。逆に再帰関数が嫌いな人が、codegen.cをfor文で書き直そうと思ったら、Stack構造を追加で用意する必要が出てくる。

これは、競プロでも使えそうな知見。

PONTAPONTA

数値の型変換

PONTAPONTA

C言語における、二項演算は二つの型が一致している必要がある。一致していない場合は、より広い方の型にキャストしてから演算が行われる。

int main() { 
  return -1 < (unsigned)1; // 0 = false
}

上記のコードは、-1のintと1のunsigned intが比較されている。より広い型はunsinged intなので、-1の方が、unsinged intにキャストされて、比較が行われる。

int main() {
  return -1 < 1; // 1 = true
}

上記のコードは、型が共通なのでキャストは行われない。

PONTAPONTA

アセンブリに直す場合

-1 < (unsigned) 1

x86_64で以下のようになる。

mov rdi, -1
mov rax, 1
cmp rdi, rax
setb al ; 符号付き比較の場合はsetlを用いる

ARM64では以下のようになる。

mov x0, -1
mov x1, 1
cmp x0, x1
cset x0, LO ; 符号付き比較の場合はLTを用いる
PONTAPONTA

C言語にアセンブリを書く方法。ARM64の場合。

int neg(int a) {
  int src = a;
  int dst;
  __asm__ ("  neg %w0, %w1\n"
            : "=r" (dst)
            : "r" (src));
  return dst;
}

int main() { 
  int a = -11;
  int b = neg(a); // 11
  return 0;
}
PONTAPONTA

C言語であまり使われない予約語

const, volatile, auto, register, restrict, _Noreturn

PONTAPONTA

const

値が変更不可能な定数を宣言するための限定子。
これはよく使う。

PONTAPONTA

volatile

変数への読み書きが毎回物理的に行われることを強制する。
メモリマップされたデバイスレジスタや割り込みサービスルーチンで使用される変数に使われる。

PONTAPONTA

auto

変数が自動的に(自動ストレージ期間)初期化され、そのスコープ(通常はブロック文の終わり)を出たときに自動的に破棄されることを示す。C99から、「auto」キーワードは廃止され、現在では、変数宣言時に自動的に推測される。

PONTAPONTA

register

数が頻繁にアクセスされる可能性があることをコンパイラに示すために使用される。

PONTAPONTA

restrict

ポインタが指すオブジェクトが他の任意のオブジェクトとエイリアス(別名)を持たないことを表す。

PONTAPONTA

_Noreturn

この関数修飾子は、関数が戻ることはない(つまり、return文を持たないで終了する)であろうと、コンパイラにヒントを与えるためのもの。

PONTAPONTA

ARM64の浮動小数点数

PONTAPONTA

ARM64には、汎用レジスタ(x0~x30)の他に、浮動小数点数を扱うレジスタ(v0~v31)がある。

v0~v31は128bitのレジスタである。
v0~v31の下位64bitに対して、d0~d31という名前でアクセスでき、C言語だとdouble型を自然に扱える。
v0~v31の下位32bitに対して、s0~s31という名前でアクセスでき、C言語だとfloat型を自然に扱える。

以下のように利用する。

// 32 bit float add
fadd s0, s0, s1

// 64 bit double add
fadd d0, d0, d1

ちなみにfadd v0, v0, v1のように128bitの浮動小数点数を単一の値として足し算を行う命令は存在しない

PONTAPONTA

v0~v31の128bit全体を使うためには、NEON(Advanced SIMD)を使う。

以下のように使う。

// 4 float values add
fadd v0.4s, v1.4s, v2.4s

// 2 double values add
fadd v0.2d, v1.2d, v2.2d

128bit全体を用いることで、4つのfloatを同時に足し合わせたり、2つのdoubleを同時に足し合わせることが可能である。

PONTAPONTA

ARM64のアセンブリで浮動小数を扱う。

PONTAPONTA

レジスタd0に3.14を用意したい場合、例えば以下のようなことがしたい時

double d0 = 3.14;

以下のようにコードを書く。

mov	x8, #34079
movk	x8, #20971, lsl #16
movk	x8, #7864, lsl #32
movk	x8, #16393, lsl #48
fmov	d0, x8

レジスタx8にはIEEE 754の形式でビット列を宣言したのちに、fmov命令でd0に移動している。

IEEE 754の説明は、以下のウィキペディアがわかりやすい。

https://ja.wikipedia.org/wiki/IEEE_754#例

PONTAPONTA

上記のアセンブリを出力するためにはC言語で以下のように実装すれば良い。

double d = 3.14;
int64_t val = *(int64_t *)&d;
println("    mov x0, %#x", val & 0xFFFF);
println("    movk x0, %#x, lsl #16", (val >> 16) & 0xFFFF);
println("    movk x0, %#x, lsl #32", (val >> 32) & 0xFFFF);
println("    movk x0, %#x, lsl #48", (val >> 48) & 0xFFFF);
println("    fmov d0, x0");

floatの宣言も同様にできる。

PONTAPONTA

コンパイラによっては、以下のようにDataセグメントに値を書き込んでしまうものもある。

	.p2align	3
lCPI0_0:
	.quad	0x40091eb851eb851f              ; double 3.1400000000000001

	.globl	_main
	.p2align	2
_main:
	adrp	x8, lCPI0_0@PAGE
	ldr	d0, [x8, lCPI0_0@PAGEOFF]
	ret
PONTAPONTA

ARM64の整数と浮動小数点の変換

u32, i32, u64, i64, f32, f64の間の変換方法をまとめる。

PONTAPONTA

整数から浮動小数への変換

ucvtf

From To Example
u32 f32 ucvtf s0, w0
u32 f64 ucvtf d0, w0
u64 f32 ucvtf s0, x0
u64 f64 ucvtf d0, x0

scvtf

From To Example
i32 f32 scvtf s0, w0
i32 f64 scvtf d0, w0
i64 f32 scvtf s0, x0
i64 f64 scvtf d0, x0
PONTAPONTA

浮動小数から整数への変換

fcvtzs

From To Example
f32 i32 fcvtzs w0, s0
f32 i64 fcvtzs x0, s0
f64 i32 fcvtzs w0, d0
f64 i64 fcvtzs x0, d0

fcvtzu

From To Example
f32 u32 fcvtzu w0, s0
f32 u64 fcvtzu x0, s0
f64 u32 fcvtzu w0, d0
f64 u64 fcvtzu x0, d0
PONTAPONTA

浮動小数から浮動小数への変換

fcvt

From To Example
f32 f64 fcvt d0, s0
f64 f32 fcvt s0, d0
PONTAPONTA

整数から整数への変換

sxtw

From To Example
i32 i64 sxtw x0, w0

uxtw

From To Example
i32 u64 uxtw x0, w0
u32 i64 uxtw x0, w0
u32 u64 uxtw x0, w0

mov

From To Example
i64 i32 mov w0, w0
i64 u32 mov w0, w0
u64 i32 mov w0, w0
u64 u32 mov w0, w0
PONTAPONTA
  • sxtb: 32bit 整数から 8bit 符号付き整数への変換
From To Example
i32 i8 sxtb w0, w0
  • uxtb: 32bit 整数から 8bit 符号なし整数への変換
From To Example
i32 u8 uxtb w0, w0
  • sxth: 32bit 整数から 16bit 符号付き整数への変換
From To Example
i32 i16 sxth w0, w0
8bitや16bitの変数
  • uxth: 32bit 整数から 16bit 符号なし整数への変換
From To Example
i32 u16 uxth w0, w0
PONTAPONTA

浮動小数点数のNaN周りの挙動について

PONTAPONTA

ARM64ではNaNとのLT比較は常にtrueが返る。

    .text
    .globl _main
    .p2align 2
_main:
	mov x0, 0
	movk x0, 0x7ff8, lsl 48
	fmov d0, x0

	mov x1, 0
	fmov d1, x1

	fcmp d0, d1
	cset w0, LT

	ret

NaNは0x7ff8000000000000と定義されている。
上記のコードは1が返る。

ちなみに、C言語はNaNとのLT比較で0を返す。

なので、普通に実装するとC言語と仕様が異なってしまう。注意が必要。

ただ、細かすぎる仕様なのでコンパイラ自作の際は無視してもいいかも。

PONTAPONTA

#include <stdio.h>について

PONTAPONTA

以下のコードで#include <stdio.h>せずにHello, World!することができる。

typedef struct FILE FILE;
extern FILE *__stdoutp;
int fprintf(FILE *fp, char *fmt, ...);

int main() {
    fprintf(__stdoutp, "Hello, world!\n");
    return 0;
}

このコードはプラットフォームに依存してしまうため推奨されない。
基本的にはstdio.hを使ってコードは書くべきである。

PONTAPONTA

上記のコードをアセンブリにすると以下のようになる。

	.section	__TEXT,__text,regular,pure_instructions
	.build_version macos, 14, 0	sdk_version 14, 2
	.globl	_main                           ; -- Begin function main
	.p2align	2
_main:                                  ; @main
	sub	sp, sp, #32                     ; =32
	stp	x29, x30, [sp, #16]             ; 16-byte Folded Spill
	add	x29, sp, #16                    ; =16
	mov	w8, #0
	stur	wzr, [x29, #-4]
	adrp	x9, ___stdoutp@GOTPAGE
	ldr	x9, [x9, ___stdoutp@GOTPAGEOFF]
	ldr	x0, [x9]
	adrp	x1, l_.str@PAGE
	add	x1, x1, l_.str@PAGEOFF
	str	w8, [sp, #8]                    ; 4-byte Folded Spill
	bl	_fprintf
	ldr	w8, [sp, #8]                    ; 4-byte Folded Reload
	mov	x0, x8
	ldp	x29, x30, [sp, #16]             ; 16-byte Folded Reload
	add	sp, sp, #32                     ; =32
	ret

	.section	__TEXT,__cstring,cstring_literals
l_.str:                                 ; @.str
	.asciz	"Hello, world!\n"

__stdoutpはカーネルとシェルの機能を組み合わせて実装されている。詳細は以下を参考。

https://ja.wikipedia.org/wiki/標準ストリーム

frpintfはlibcとして提供されている。MacOSでは以下で実装されている。

https://github.com/apple-oss-distributions/Libc/blob/c5a3293354e22262702a3add5b2dfc9bb0b93b85/stdio/FreeBSD/fprintf.c#L45

PONTAPONTA

#include <stdarg.h>について

chibiccのこのコミットがよくわからない。

https://github.com/rui314/chibicc/commit/754a24fafcea637cab8bc01bb2702069109a0358

以下のメモを見ると、全てのレジスタのレジスタの内容と__va_elem構造体の内容を__va_area__というローカル変数に保管しているみたい。

https://zenn.dev/link/comments/c2243a44b9c94e

いまいちよくわからない。

PONTAPONTA

以下のコードをclang -E -P -C した。

#include <stdarg.h>

char buf[1024];
int vsprintf(char *buf, char *fmt, va_list ap);
char *format(char *fmt, ...){
    va_list ap;
    va_start(ap, fmt);
    vsprintf(buf, fmt, ap);
    va_end(ap);
    return buf;
}
int main() {
    format("%d + %d = %d\n", 1, 2, 1+2);
    return 0;
}

結果は次のようになった。

typedef __builtin_va_list va_list;

char buf[1024];
int vsprintf(char *buf, char *fmt, va_list ap);
char *format(char *fmt, ...){
    va_list ap;
    __builtin_va_start(ap, fmt);
    vsprintf(buf, fmt, ap);
    __builtin_va_end(ap);
    return buf;
}

int main(void) {
    format("%d + %d = %d\n", 1, 2, 1+2);
    return 0;
}

__builtin_va_list, __builtin_va_start, __builtin_va_endがある。ビルトインされた関数を呼び出して処理するみたい。

PONTAPONTA

以下のコードをアセンブリに変換clang -S -O0 -fno-stack-protectorして、va_lsitを渡した仕様を調べる。

#include <stdarg.h>

char buf[1024];
int vsprintf(char *buf, char *fmt, va_list ap);
int printf(const char *fmt, ...);

char *format(char *buf, char *fmt, ...){
    va_list ap;
    va_start(ap, fmt);
    vsprintf(buf, fmt, ap);
    //va_end(ap);
    return buf;
}

int main(void) {
    format(buf, "%d + %d = %d\n", 1, 2, 1+2);
    printf("Ans: %s\n", buf);
    return 0;
}
PONTAPONTA

bl _formatが呼ばれる直前の状態

レジスタ:

x0 = _bufのアドレス
x1 = l_.strのアドレス

スタック:

--- sp + 32
0
--- sp + 24
3
--- sp + 16
2
--- sp + 8
1
--- sp

普通の可変長呼び出しと変わらない。

PONTAPONTA

bl _vsprintfが呼ばれる前の状態

レジスタ:

x0 = _bufのアドレス
x1 = l_.strのアドレス
x2 = apのアドレス

スタック:

何でもいい。

アセンブリを見た感じだと、apを配列として扱った時の関数呼び出しと変わらない。
本質的には、以下と同じ。

int func(int a[], int n) {
    return a[n];
}

int main() {
    int a[3];
    a[0] = 11;
    a[1] = 22;
    a[2] = 33;
    return func(a, 1);
}
PONTAPONTA

ついに、自分自身をコンパイルできるようになった。

https://github.com/derbuihan/chibicc_arm64/commit/6e2b569e09febdd5d55aee66ed082573bd355059

stage2とstage3のバイナリが一致することを確認した。
また、全てのステージのバイナリがテストをパスすることも確認した。

なんか感動。

まだプリプロセスを実装してないので、python self.pyがないと完全に自立コンパイルはできない。

PONTAPONTA

ちなみに、バイナリの比較は以下で行なっている。

#!/bin/bash

chibicc2=$1
chibicc3=$2

diff_lines=$(cmp -l $chibicc2 $chibicc3 | wc -l)

if [ $diff_lines -le 1 ]; then
  echo OK
else
  echo NG
  exit 1
fi

バイナリにファイル名が書き込まれているので、1行だけ差分が出てしまう。

PONTAPONTA

関数ポインタ

PONTAPONTA

関数ポインタを使った簡単なコード

int add2(x, y) {
    return x + y;
}

int main() {
    int (*fp) (int, int) = add2;
    int ret = fp(11, 22);
    return ret;
}

blrで関数のメモリアドレスを指定して実行できるのでこんな感じで実装すれば良さそう。

	mov w0, #11
	mov w1, #22
	adrp x2, _add2@PAGE
	add x2, x2, _add2@PAGEOFF
	blr x2

ちなみにblrbrと間違えると、retで戻って来れなくなるので要注意。

(ちなみに、bはbranchのbで分岐命令、lはlink付きのlでリンクレジスタを使う、rはregisterのrでレジスタのポインタを使う。)

PONTAPONTA

ARM64の場合は、以下のように_exitを呼び出すことはできない。

mov x0, #11
adrp x1, _exit@PAGE
add x1, _exit@PAGEOFF
blr x1

普通に以下を呼び出さないといけない。

bl _exit
PONTAPONTA

こういう書き方も、関数のアドレスを渡して、実行させていると思えばわかりやすい。

int ret11() {
    return 11;
}

int call_param(int x()) {
    return x();
}

int main(void) {
    int ret = call_param(ret11);
    return ret;
}

ちなみに、C言語はローカル関数をサポートしてない。ローカル関数を実装するには、抽象構文木をクロージャー変換(ローカル関数をグローバル関数に変換してスコープを絞る処理)をする必要がある。

PONTAPONTA

私のコンパイラ、これが動くんだけどなぜ動くのかはわからない。魔法?

typedef int (*func) (int, int);

int add(int a, int b) {
    return a + b;
}

int sub(int a, int b) {
    return a - b;
}

int main() {
    func funcs[2] = {add, sub};
    return funcs[0](4, 3) + funcs[1](4, 3);
}
PONTAPONTA

これが魔法に感じるの深遠な問題な気がしてる。コンパイラって機能を追加するたびに、できることが指数関数的に増えるわけだけど、その増加スピードが実装者の認知を超える瞬間があるんだろうなぁとか思ったり。自然言語でもこういう瞬間があるから言語学って面白いんだろうなぁとか思ったり。

PONTAPONTA

これをずーっと考えててだんだん問題がわからなくなってきた。一度、言語化してみる。


最初intのみでコンパイラの作成を始めて、intのポインタ、intの配列、intの関数、intの構造体を順番に実装していった。
コンパイラが育ったどっかのタイミングで、コードを数行書き換えてcharやshortやlongを追加した。そうするとすぐに追加した型のポインタや配列や関数や構造体が正しく動くようになった。さらに、型の組み合わせも動くようになった。
その後、型変換を実装していって、ある程度コンパイラが育ったタイミングで数行追加してfloatとdoubleを実装した。そうするとすぐに追加した型のポインタや配列や関数や構造体が動くようになった。
もっとコンパイラが育ったタイミングで関数ポインタを実装すると、すぐに関数ポインタの配列や構造体が動くようになった。

このように、あとから型を追加するとき、1個の型を追加するとそのたびに、コードの量はとてつもなく膨大に増えてく気がする。そうはならなくて数行書き換えるだけで型を追加できるのはなぜなのか?

PONTAPONTA

うーん。BNFのように文法を書いた時点で言語機能が指数関数的に増やせるというのはあたり前な気がしてきがするが、それでも関数ポインタを実装したらその瞬間に関数ポインタの配列や、関数ポインタを要素に持つ構造体が正しく動作するのは魔法に感じるんだよなぁ。なんでだろう。

PONTAPONTA

実行ファイルができるまで

PONTAPONTA

C言語は以下の順番で実行ファイルに変換される。

  1. プリプロセス
  2. アセンブラへの変換
  3. オブジェクトファイルの生成
  4. リンク
PONTAPONTA
  1. プリプロセス:
gcc -E main.c -o main.i
  1. アセンブラへの変換:
gcc -S main.i -o main.s
  1. オブジェクトファイルの生成:
gcc -c main.s -o main.o

または

as main.s -o main.o
  1. リンク:
gcc main.o -o main

または

ld main.o -o main
PONTAPONTA
  1. プリプロセス:
clang -E main.c -o main.i
  1. アセンブラへの変換:
clang -S main.i -o main.s
  1. オブジェクトファイルの生成:
clang -c main.s -o main.o
  1. リンク:
clang main.o -o main
PONTAPONTA

M1 Macの場合

$ file main.o
main.o: Mach-O 64-bit object arm64

$ file main  
main: Mach-O 64-bit executable arm64

LinuxはELFが使われている。

PONTAPONTA

ELFの場合は、readelfコマンドで実行ファイルの内容を見れる。

readelf -S a.out 

Mach-Oの場合は、gobjdumpコマンドが使われる。

gobjdump -D a.out

バイナリの内容は、hexdumpで見れる。

hexdump -Cv a.out
PONTAPONTA

プッシュダウンオートマトンでは、
与えられた文字列が同じ文字列を2階繰り返す文字列か判定出来ない。

入力SがS=abcabcみたいに繰り返してるか判定出来ないらしい。

PONTAPONTA

たしかに、S=abccbaはスタックで簡単に判定できるけど、S=abcabcは簡単には判定出来ない気がする。

PONTAPONTA

この問題の本質って、どこにあるんだろう。
consタイプのリスト構造はスタックでは反転むずいってことなのか…

PONTAPONTA

連結リストを処理するときに、DFSの場合は追加のデータ構造なしに再帰関数のみで実装できる。BFSの場合は追加のデータ構造なしにFor文のみで実装できる。

この辺が本質な気がしてきた。

PONTAPONTA

前処理(preprocess)

preprocessは、字句解析や構文解析の前に実施する。なので、文字列に対して実施することになる。

ただchibiccでは、字句解析の後で構文解析の前にpreprocessを行なっている。なので標準的なCコンパイラとは異なる。

PONTAPONTA

プリプロセスはC言語の解釈は行わないので、以下のようなコードも実行できる。

main.c
#include "test1.txt"
#include "test2.txt"
test1.txt
int main(void) {
    int sum = 0;
    for (int i = 0; i < 10; i++) {
test2.txt
        sum += i;
    }
    return sum;
}

これを普通にコンパイルして実行できる。
結構、#includeって魔法なんだなぁ。

PONTAPONTA

プリプロセスにIf文を書ける。整数定数式の評価もできる。

test.h
#if 1 + 1 == 2
  int a = 11;
#endif

このif文は入れ子にすることが可能

PONTAPONTA

C言語のif系のマクロには、#if, #ifdef, #ifndefがある。

#ifdef MACROは、#if defined(MACRO)と等しい動作。

#ifndef MACROは、#if !defined(MACRO)と等しい動作。

#ifdef#ifndefは、#else#elif#endifと一緒に使うことができる。

PONTAPONTA

定義されてないマクロは0と評価される。これは仕様らしい。

#ifdef Status
#else 
int c = 33; // 生き残る。
#endif
PONTAPONTA

抽象構文木のデータ構造について

PONTAPONTA

例えば、chibiccのcodegen.cでは以下のようになっている。

static void gen_expr(Node *node);
static void gen_stmt(Node *node);

これを、Nodeを適切にExprとStmtに分離して、以下のようにできないのだろうか。

static void gen_expr(Expr *expr);
static void gen_stmt(Stmt *stmt);

もう少し分離して、整数定数式も分離して、整数定数式、式、文の三種類のノードにできないだろうか。多分、分離すればするほど複雑になるから、chibiccは意図的に単一のデータ構造にしてるんだと思うけど。

PONTAPONTA

改めてこの記事読んでみたら面白かった

https://qiita.com/ruiu/items/4d471216b71ab48d8b74

PONTAPONTA

3月24日から引用

それにしてもこの部分は自分で書いたコードが自分でも理解できるかどうかギリギリくらいで、Dennis Ritchie本人も自分の書いているコードの意味を完全に理解していたのかどうかちょっと疑問。僕のコードがまずいというわけではなくこの部分はLCCでもやっぱりわけのわからないコードになっていた。

私もchibiccの写経してて宣言の部分は理解が難しかった。(というよりほぼ理解せずに丸写しした。)写すまではCの宣言周りが複雑って印象なかったけど、実際はそうではなかった。直感で複雑かどうかを判断するのって(歴戦のエンジニアであっても)むずいんだなぁとか思った。

PONTAPONTA

4月27日から引用

TCCのソースコードはなんども読もうとしてみたんだけど、いまいち全体像がつかめないまま。コンパイラというのは複雑なプログラムだから、普通は複雑さを分割統治して制御できるようにいろいろ工夫するものだけど、TCCは複雑なものをそのままの複雑さで実装して、きちんと動いてしまっている感じがする。こんなすごいコードは少なくとも今の僕には書けない。真似したいコードかというとちょっと違うかもしれないけど、こういうコードを書くことができる人がいるんだという意味でちょっと感動させられる。

複雑さを分割統治して制御するように色々工夫するのかぁ。chibiccにはその工夫がいくつもあったと思うんだけど、自然すぎて私は全てを感じ取れなかったなぁ。その工夫を習得して複雑なプログラムを作れるようになりたいなぁ。

PONTAPONTA

#define _POSIX_C_SOURCE 200809Lの謎

chibiccでは一番最初に#define _POSIX_C_SOURCE 200809Lが呼ばれるようになっている。この謎に迫る。

https://github.com/rui314/chibicc/blob/90d1f7f199cc55b13c7fdb5839d1409806633fdb/chibicc.h#L1

PONTAPONTA

#include <stdio.h>にはPOSIXで定義された関数と、独自に定義された関数がある。

以下のコードを、Linux上でgcc -E -P test.cを実行する。

test.c
#define _POSIX_C_SOURCE 200809L // この行を切り替える。
#include <stdio.h>

そうすると、宣言されてる関数が違うことがわかるはず。

PONTAPONTA

手元のM1 Macにたまたま入ってるclangで試すと、以下の関数が増える。

typedef u_int64_t user_addr_t;
typedef u_int64_t user_size_t;
typedef int64_t user_ssize_t;
typedef int64_t user_long_t;
typedef u_int64_t user_ulong_t;
typedef int64_t user_time_t;
typedef int64_t user_off_t;

int renamex_np(const char *, const char *, unsigned int) __attribute__((availability(macosx,introduced=10.12))) __attribute__((availability(ios,introduced=10.0))) __attribute__((availability(tvos,introduced=10.0))) __attribute__((availability(watchos,introduced=3.0)));
int renameatx_np(int, const char *, int, const char *, unsigned int) __attribute__((availability(macosx,introduced=10.12))) __attribute__((availability(ios,introduced=10.0))) __attribute__((availability(tvos,introduced=10.0))) __attribute__((availability(watchos,introduced=3.0)));

int getw(FILE *);
int putw(int, FILE *);

extern const int sys_nerr;
extern const char *const sys_errlist[];
int asprintf(char ** restrict, const char * restrict, ...) __attribute__((__format__ (__printf__, 2, 3)));
char *ctermid_r(char *);
char *fgetln(FILE *, size_t *);
const char *fmtcheck(const char *, const char *) __attribute__((format_arg(2)));
int fpurge(FILE *);
void setbuffer(FILE *, char *, int);
int setlinebuf(FILE *);
int vasprintf(char ** restrict, const char * restrict, va_list) __attribute__((__format__ (__printf__, 2, 0)));
FILE *funopen(const void *,
                 int (* _Nullable)(void *, char *, int),
                 int (* _Nullable)(void *, const char *, int),
                 fpos_t (* _Nullable)(void *, fpos_t, int),
                 int (* _Nullable)(void *));

少なくとも私は上記の関数のどれも使ったことがない。。便利なのかなぁ。

PONTAPONTA

ld64.lldの使い方を覚える。

clangにオブジェクトファイルを渡してリンクさせているが、これだとセルフホストと言えない気もするので、ld64.lldの使い方を調べる。

(現状だとアセンブリからオブジェクトファイルへの変換にもclangに依存しているが。)

PONTAPONTA

リンカとしては、MacOSの/usr/bin/ldを用いる。多分、/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/ldと同じものだと思う。Xcodeのデフォルトのリンカとして用いられているものだと思う。

今は、MacOSのリンカーってややこしいっぽい。

https://lld.llvm.org/MachO/ld64-vs-lld.html
https://chromium.googlesource.com/chromium/src/+/refs/heads/main/docs/mac_lld.md

/usr/bin/ldはどのリンカーなんだろう。

PONTAPONTA

以下のコードをリンカー使って実行形式に変えたい。

tmp.c
int main() {
  return 12;
}

以下で実行できた。

$ clang -c -o tmp.o tmp.c; ld tmp.o; ./a.out; echo $?
12

ちなみに、オブジェクトファイルは以下の形式。

$ file tmp.o
tmp.o: Mach-O 64-bit object arm64
PONTAPONTA

以下のコードを実行形式に変換したい。

tmp.c
#include <stdio.h>

int main() {
  printf("Hello, World!\n");
  return 12;
}

以下では実行形式に変換できない。

$ clang -c -o tmp.o tmp.c; ld tmp.o; ./a.out; echo $?
ld: Undefined symbols:
  _printf, referenced from:
      _main in tmp.o
Hello, World!
12

ldコマンドになんらかのオプションをつける必要がある。

PONTAPONTA

stdlib.hを読み込むために対応しないといけないこと。

PONTAPONTA

__has_include

__has_include(<...>)だけ対応した。他にも__has_include("...")とか対応しないといけない。

PONTAPONTA

実用的な使い方

現在は自分自身をコンパイルすることしか確認できてない。実社会の実用的なコードをコンパイルしてみたい。

PONTAPONTA

FreeBSDのコード。bin/ls配下にlsコマンドがある。

https://github.com/freebsd/freebsd-src

少しビルド挑戦してみたけど、FreeBSD上でビルドしないといけないみたい。私のコンパイラはM1 Mac上でしか動かないので難しいかも。

PONTAPONTA

C言語でOSに依存しないライブラリ

組込開発において、OSが存在しない状況でも使えるC言語のライブラリがある。
型の定義やマクロを提供している。

PONTAPONTA

Cの規格では、以下がフリースタンディング環境で利用可能

float.h
iso646.h
limits.h
stdalign.h
stdarg.h
stdbool.h
stddef.h
stdint.h
stdnoreturn.h

逆にこれら以外のライブラリをincludeする時は、libc依存だったりして自作OS環境では動かなくなる。string.hとか注意が必要。

PONTAPONTA

ファイル操作関数

stdio.hに含まれるファイルを操作する関数たち。

PONTAPONTA

FILE構造体

  • C言語でファイルを取り扱うデータ型
  • fopenがFILE構造体のポインタを返す。
  • FILE構造体の内部にはディスクリプタを含んできる。
PONTAPONTA

fopen関数

FILE *fopen(const char *path, const char *mode);

例:

FILE *fp = fopen("/hello.txt", "r");
  • fpはFILE構造体へのポインタである。
  • 初めfpはファイルの先頭を示している。
  • fpをfreadやfwriteで操作することで、ファイルに読み書きを行う。
PONTAPONTA

fread関数

size_t fread(void *ptr, size_t size, size_t count, FILE *stream);

例:

char buf[128];
size_t read_count = fread(buf, sizeof(char), sizeof(buf), fp);
  • freadを通じて、ファイルから128個の1Bytesをbuf[128]に移す。
  • fpが指し示すファイルの位置が128個分だけインクリメントされる。
  • 例外処理が必要。
PONTAPONTA

fseek関数

int fseek(FILE *stream, long int offset, int whence);

例:

fseek(fp, 10, SEEK_SET)
  • fpが指し示すファイルの位置を10バイト動かす。
  • 第三数が基準で、SEEK_SETはファイルの先頭を、SEEK_CURは現在の位置を、SEEK_ENDはファイルの終端を表す。
  • エラーハンドリングが必要。
PONTAPONTA

fclose関数

int fclose(FILE *stream);

例:

fclose(fp);
  • FILE構造体を解放する。
PONTAPONTA

指示付き初期化子(Designated Initializer)

C99で導入された宣言の方法。chibiccでは実装されているが、私のchibicc_armでは未実装。

PONTAPONTA

以下のような構造体がある。

struct vec { int x; int y; int z; };

以下のように初期化できる。

struct vec v = {10, 15, 20};

指示付き初期化子を使うと、これを以下のように書ける。

struct vec v = {.x = 10, .y = 15, .z = 20};

構造体に要素wが加わった時に、順番に依存せずに宣言してるので、安全に代入ができる。

PONTAPONTA

2種類の配列

C言語の配列には2種類ある。一つがスタック領域の配列で、もう一つがヒープ領域の配列である。C言語はこれを意識させないように言語がデザインされてるようだが、ちゃんと意識しながら使わないとメモリリークしてしまう。

PONTAPONTA

スタック領域の配列

int main()
{
  int a[] = {1, 2, 3, 4, 5};
  return 0;
}
  • この配列はコンパイル終了時にサイズが決まっている。
  • ローカル変数と同様なので、メモリリークとかは意識する必要がない。
  • 生存が関数の終了まで
PONTAPONTA

ヒープ領域の配列

#include <stdlib.h>

int main()
{
  int *a[] = malloc(5 * sizeof(int));
  a[0] = 0;
  a[1] = 1;
  a[2] = 2;
  a[3] = 3;
  a[4] = 4;
  free(a);
  return 0;
}
  • この配列は実行中にサイズが決まる。
  • freeをしないとメモリリークしてしまう。
  • 生存はfreeするまで
PONTAPONTA

C++との違い

CとC++は微妙に文法が異なる。

PONTAPONTA

C++には以下の書き方がある。

int main()
{
  int a = 11;
  int &r = a;

  return 0;
}
  • ここで変数rは必ず参照変数を必ず初期化時に設定しなきゃいけない。また参照変数を変更することができない。

Cにはこの文法は存在しない。そのため、Cで同じようなことするには以下のように書く。

int main()
{
 int a = 11;
 int *p = &a;

 return 0;
}
  • 変数pは宣言時に初期化する必要もなければ、変更することも可能である。

Cで書いたpはintのポインタ変数だが、C++で書いたrはint型変数への参照である。なので微妙に違う。

PONTAPONTA

C++の場合は変数宣言の時のstructを省略できる。以下のコードはC++では普通に動く。Cだとエラーになる。

struct Person {
    char *name;
    int age;
};

int main() {
    Person p = {"Alice", 20};
    return 0;
}

C言語の場合は、以下を宣言してstructを省略できる。

typedef struct Person Person;

また、宣言時にtypedefを用いる書き方が一般的に行われる。

typedef struct Person {
    char *name;
    int age;
} Person;

(初見だとこのtypedefが難しいよね。。。)

PONTAPONTA

アドレス渡しと参照渡し

以下のコードはアドレス渡しを使っている。

void swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

これはCでもC++でも書くことができる。

以下のコードは参照渡しを使っている。

void swap2(int &x, int &y) {
    int temp = x;
    x = y;
    y = temp;
}

これはC++のみで書くことができる。

参照渡しを用いた関数は副作用の範囲の特定が難しいため、複雑なロジックを描かないようにすると良い。

PONTAPONTA

sizeofはコンパイル時に評価する。

PONTAPONTA

以下のコードは、コンパイル時に、配列Aの長さが5に決まるので、評価できる。

int main() {
    int A[] = {1, 2, 3, 4, 5};
    int x = sizeof(A);
    return x; // 20
}

逆に以下のようなコードは未定義動作もしくはコンパイラ依存もしくは最新のCの仕様なら動くコードになる。

int func(int n) {
    int A[n];
    return sizeof(A);
}

また、以下のコードは、配列を渡しているように見えるがこれは実態としてポインタ渡しなので、func関数内ではAはポインタ扱いなので8Bytesを返す。(64bit CPUなので)

int func(int A[]) {
    return sizeof(A);
}

int main() {
    int x = func(A);
    return x; // 8
}

sizeofがコンパイル時に評価される特殊な関数であることを意識すると、この辺がよく理解できる。

PONTAPONTA

構造体の値渡し

PONTAPONTA

構造体は値渡しである。そのため以下のようなコードを書いてもpを変更できない。

typedef struct Person {
    char *name;
    int age;
} Person;

void func(Person p, int age) {
    p.age = age;
}

int main() {
    Person p = {"John", 25};
    func(p, p.age + 1);
    return p.age; // 25
}
PONTAPONTA

pの値を変更したいのであれば、以下のように明示的なアドレス渡しをする必要がある。

void func2(Person *p, int age) {
    p->age = age;
}


int main() {
    Person p = {"John", 25};
    func2(&p, p.age + 1);
    return p.age; // 26
}
PONTAPONTA

配列を渡すと、配列の先頭のポインタが渡される。
構造体の場合は、構造体のポインタに変わって渡されることはない。
この辺が少し混乱する。

PONTAPONTA

ちなみに以下のような、配列を持つ構造体は値渡しになる。

typedef struct Person {
    char name[20];
    int age;
} Person;

以下がサンプル

void func(Person p, char *name) {
    strcpy(p.name, name);
}

void func2(Person *p, char *name) {
    strcpy(p->name, name);
}

int main() {
    Person p = {"Alice", 25};
    func(p, "Bob");
    printf("%s\n", p.name); // "Alice"

    func2(&p, "Charlie");
    printf("%s\n", p.name);// "Charlie"

    return p.age;
}

配列を値渡しとして扱いたいなら構造体に閉じ込めちゃえばいい。

PONTAPONTA

再帰関数で状態を保持するためにグローバル変数を使うべきではない。

PONTAPONTA

ネイピア数を計算するコードとして以下のようなコードを書いたとする。

float e(float x, float n) {
    static float p = 1, f = 1;
    float r;

    if (n == 0) {
        return 1;
    }

    r = e(x, n - 1);
    p *= x;
    f *= n;
    return r + p / f;
}

このコードはstaticを用いて変数を宣言しているため、一見良さそうに見える。が、このような関数を書くべきではない。以下のように実行してみる。

int main() {
    float x = e(1, 100);
    printf("x = %f\n", x); // x = 2.718282
    float y = e(1, 100);
    printf("x = %f\n", y); // y = 1.000000

    return 0;
}

一回目の実行は正しいが、二回目の実行は間違っている。入力は同じなのに答えが異なる使いにくい関数が出来上がってしまう。。

PONTAPONTA

配列の範囲外アクセス

PONTAPONTA

C言語は以下のように二次元配列にアクセス可能である。

int main() {
    int A[11][22];
    A[3][4]; // *(A + (3*11+4))
}

これをよく観察すると3*11+4の部分で、配列の長さを使ってこの演算を行なっている。また、配列の引数は動的に変更可能なので、この演算は実行時に行われている。このことからC言語は動的な配列の引数と配列の長さを使ったロジックを配列の値参照時に行えることがわかる。

さて、以下のコードはC言語でエラーにならない。

int main() {
    int A[5];
    A[6];
}

配列の値参照時に配列の引数と配列の長さを比較して、配列の引数が配列の長さを超えていたらエラーとするってロジックを組み込めば、この範囲外アクセスもエラーにできる。ただ、そうはしてない。C言語は組み込みとかOS作成用に、そもそもカーネルに例外処理の機能がなくても動くように設計されてるので、配列の範囲外アクセスで例外処理をしないように設計されてるんだと思う。言語仕様がバカなんじゃなくて、そういう思想で初めから設計されてるというだけ。

PONTAPONTA

不等号の両辺の評価順序

PONTAPONTA

不等号の両辺の評価順序が未定義だとしたら、以下の処理は未定義動作になる。

#include <stdio.h>

int g = 0;

int ret1() {
    g += 1;
    printf("%d\n", g);
    return g;
}

int ret2() {
    g += 2;
    printf("%d\n", g);
    return g;
}

int main() {
    //    if (ret1() < ret2()) {
    //        return 1;
    /p/    }
    if (ret2() > ret1()) {
        return 1;
    }
    return 2;
}

不等号を糖衣構文にする(B>AはA<Bの糖衣構文とするなど)と上記のようなコードを書かれた時に、評価順序を混乱させてしまう可能性がある。なので不等号は糖衣構文ではなくて、しっかりとcmp命令のフラグを使った方がいいと思う。