C言語まとめ
mallocとcalloc
メモリ解放する系の関数。
以下の書き方について
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
構造体の前方宣言
以下のように構造体のタグのみを宣言できる。
struct disk;
この宣言の後に、具体的な宣言をして構造体を使うことができる。
struct disk {
int size;
char* name;
};
struct disk mydisk;
va_list
, va_start
, vfprintf
variable printを使う。引数が可変。
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 ap
はap
が可変長の引数を扱うための変数であることを宣言する。
va_start
は、ap
の開始位置を指定する。。具体的には関数の引数n
の次から取り出すように設定する。
va_arg(ap, int)
で、変数ap
からint
型の値を取り出し、次の値を指し示すように設定する。
va_end
で変数ap
が可変長の引数を取り出すという設定を解除する。
va_list
には引数の終わりを取得する機能が存在しない。
printf
はva_listを使って実装されているが、以下のようにコードを書いた場合にコンパイラレベルでも実行時にもエラーを出すことができない。未定義動作となってしまう。
printf("%d %d", a);
ctype.hに入ってる便利関数たち
例
ispunct
: 区切り文字か判定
isalpha
: アルファベットか判定
memcmp
memcmp(s1, s2, n)
ポインタs1からn bitsとポインタs2からn bitsを見て比較する。
strtol
stdlib.hに入ってる。文字列から数字を取り出すのに使える。
char *p;
int val = strtol("10+1", &p, 10);
val; // 10
*p; // '+'
strtod
文字列からdoubleを取り出すのに使える。
ポインタの整理
Cのポインタ、一生わからない。
変数には全てアドレスが割り当てられている。
&・・・アドレス演算子
変数が格納されているアドレスを取得できる。
#include <stdio.h>
int main(int argc, char **argv) {
int a = 10;
printf("%p\n", &a); // 0x16b7baeac
}
ポインタ変数を使うと、ポインタ変数に格納されたアドレスの値を取り出せる。
*・・・間接演算子
ポインタ変数に定義されている演算子で、ポインタ変数が示すアドレスの値を取り出せる。
#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は意味が違うところにある。
アロー演算とドット演算の違い。
アロー演算は構造体のポインタから値を取り出す演算子。
ドット演算は構造体から値を取り出す演算子。
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); // 構造体のポインタから構造体を取り出して、そして値を取り出す。
生成文法の練習
1 + 2 *3の文法
expr = mul ('+' mul | '-' mul)*
mul = num ('*' num | '/' num)*
num = 1 | 2 | 3 ...
コツは演算子として優先度が高いのを下に書くこと。こうすることでこの木構造の先端から処理すると、一つのスタック用いて計算できるようになる。逆ポーランド記法を参照。
'\0'について
文字列を宣言すると、最後にこれが追加される。
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'なのは未定義動作だと思う。
M1 Macのアセンブリを調べる
int main() {
return 42;
}
以下でアセンブリに変換
$ cc -S test.c
変換結果
.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
不要な部分を削除する。
.globl _main
.p2align 2
_main: ; @main
mov w0, #42
ret
w0に42を設置し、処理を終了。
結果を確認。
$ cc test.s
$ ./a.out
$ echo $?
42
終了ステータスが42になっている。
ちなみにx0に42を入れても同じことができる。
以下が参考になる。
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;
スタックを使う。
.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に投入する。
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にまとめてメモリ上に配置する命令が用意されている。
比較
cmp x0, x1 # compare
cset x0, eq # ==
cset x0, ne # !=
cset x0, lt # <
cset x0, le # <=
参考: https://qiita.com/poteto0/items/0ac09f2acf0bc127426f#比較演算
上記の参考文献に基づいて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;
な何を意味するのか?
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
となっている。
次に、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に伝搬させる処理となっている。
また、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行書いたほうがいいと思う。
以上、グローバル変数を使わずにポインタで処理の場所を伝搬させてるため複雑になっている。特に再帰下降構文解析はかなり複雑な再帰関数なので、難しく感じる。
まとめると、基本的な書き方の以下になる。
Node *f(Token **rest, Token *tok) {
Node *node = new_node(
ND_kind,
g(&tok, tok), // 処理gによってtokの示す先が変わる。
NULL
);
*rest = tok; // tokの示す先が変わったことをfの呼び出し元に伝搬させる。
return node; // 木を返す。
}
誰かわかりやすい作図してほしい。
ARM64のレジスタの解説記事。
x0, x1, ..., x30 汎用レジスタ。
- 全て64bit
- w0, w1, ..., w30 64bitの半分だけ使う。
- xzr 常に64bitのゼロが入ってる
- wzr 常に32bitのゼロが入ってる
- sp スタックポインタのスタックトップのアドレスを保持する。
- wsp
- PC
spの使い方
スタックに42を突っ込んで、それを取り出す。
.globl _main
.p2align 2
_main:
mov w20, 42
str w20, [sp]
ldr w0, [sp]
ret
スタックに、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を更新する。
上記の処理を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]
でスタックトップ以外からも値を取り出せる。
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
ローカル変数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
プロローグ
; 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
としても正常に動作する。
いろんなコンパイラが吐くアセンブリを見てると、以下のようなプロローグとエピローグを使っているものがある。
; prologue
stp fp, lr, [sp, -16]!
mov fp, sp
; epilogue
mov sp, fp
ldp fp, lr, [sp], 16
ret
実はx29
にはfp
という別名があり、x30
にはlr
という別名がある。エピローグやプロローグで使うためには可読性の観点かあらfp
とlr
を用いているらしい。
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のアドレスに戻ってくる。
プロローグの解説
関数呼び出し時点でfp
とlr
の状態は以下のようである。
fp = 呼び出し元の関数のローカル変数の基準となるアドレス
lr = bl命令の次の命令のアドレス
関数の一番最初に以下の命令を実行する。この処理はプロローグと呼ばれる。
; prologue
stp fp, lr, [sp, -16]!
mov fp, sp
stp命令で上記のfp
とlr
をスタックに積んでおく。その後、mov命令でfp
にsp
のアドレスを書き込み、関数のローカル変数の基準とする。関数実行中はsp
を低いアドレス方向へ伸ばすように使って、必ず元のlr
とfp
の値を壊さないようにする必要がある。
エピローグの解説
関数が終了するタイミング(ret命令が呼ばれるタイミング)ではレジスタを以下の状態に戻す必要がある。
fp = 呼び出し元の関数のローカル変数の基準となるアドレス
lr = bl命令の次の命令のアドレス
そのために、関数の一番最後では以下の命令を実行する。この処理はエピローグと呼ばれる。
; epilogue
mov sp, fp
ldp fp, lr, [sp], 16
ret
fpから関数呼び出し時点のsp
の値を書き戻す。そこから呼び出し元のfp
とlr
の値を取り出す。ret命令で関数呼び出し元に返る。
x86_64の場合
x86_64の場合も考え方はARM64と変わらない。
x86_64の場合の解説は以下が詳しい。(図を用いて丁寧に説明されている)
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
strndup
string.hに入ってる。文字列を複製する関数。
#define _POSIX_C_SOURCE 200809L
をヘッダーに書かないと動かない。
Wikipediaのレジスタの記事
AMD64とARMのレジスタの特徴についてよくまとまってる。
以下のように現在はARMの方がレジスタが多いらしい。
やはりARM最強か?
汎用レジスタの数はRISCでは多く、CISCでは少ないという差がある。2023年時点で最も有名といえるRISCアーキテクチャのARMとSISCアーキテクチャのx86では、32ビット版は16本と8本、64ビット版では31本と16本である。
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”…となった。
スタック関連の命令はmovとaddに変換可能。
pop rax
は
mov rax, [rsp]
add rsp, 8
push rax
は
sub rsp, 8
mov [rsp], rax
変数宣言は以下が可能。
int x, y;
int x, y = 11;
int x=11, y=22;
ポインタの足し算と引き算
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);
ポインタとポインタの相対位置を計算できる。
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);
数値にポインタを足すことはできる。
int *b = 1 + q;
printf("1 + %p = %d\n", q, *b);
数値からポインタを引くことは出来ない。
int *c = 1 - q; // ERROR
printf("1 - %p = %d\n", q, *c);
この演算って代数としては何に分類されるんだろう。
ARM64のアセンブリからC言語の関数を呼び出す方法。
int ret11() {
return 11;
}
オブジェクトファイルに変換
$ gcc -c func.c // func.oが生成
アセンブリを書く。Appleの場合は関数の前に_(アンダーバー)をつけないといけないらしい。
.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
単にblを呼び出すと処理が終了しない。必ずstp/ldpを実行しないとだめ。以下は処理が終了しない。
.global _main
.p2align 2
_main:
bl _ret11
ret
(なぜかはわからない。誰か教えて。)
引数がある場合の呼び出し方法。
int add2(int a, int b) {
return a + b;
}
x0とx1の値が関数の引数になる。
.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を使ってるだけなので)
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を省くとエラーになる。以下はエラーになる。
.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が重要らしい。
コンパイラを作っていったらわかった。
x30はリンクレジスタである。リンクレジスタは、関数の呼び出し元のメモリアドレスが入っている。
mainの最後のretでmainの呼び出し元に返らないとプロセスが終了しないんだと思う。
なのでx30を保持する必要がある。
アセンブリ言語での関数呼び出し
.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
ARM64の場合を解説する。
関数呼び出しではbl
を用いる。
関数の引数が8個までは、x0~x7のレジスタを用いて引数を渡す。それ以降の引数はスタックを用いる。これはAAPCS64で仕様が定められている。
呼び出された関数でret
が実行されると戻ってこれる。
M1 Macのclangで可変長の引数を持つC言語のコードをアセンブリにしたら、どうやら可変長の部分はスタック渡しになっている。
どうやら、AppleのARM64は可変長引数をスタック渡しにする仕様があるみたい。
以下のコードを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
変数n
とm
はレジスタ渡しが行われており、それ以降の変数はスタックに入っている。
M1 MacでC言語から可変長引数のアセンブリコードを実行したい場合は注意が必要。(これがApple特有の呼び出し規則なのか、ARM64全体の呼び出し規則なのかは謎である。)
混乱したC言語の書き方。
int test(int x (int y)) {
return x + 22;
}
int main() {
return test(11);
}
この書き方はコンパイルが通る。
test関数の使い方。
int add22(int x) {
return x + 22;
}
int test(int x (int y)) {
return x(11);
}
int main() {
return test(add22);
}
ポインタは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
}
配列の面白いアクセス方法。
int main() {
int x[3];
2[x] = 11;
return x[2];
}
以下が成り立つらしい。
2[x] = *(2+x) = *(x+2) = x[2]
グローバル変数
int hello = 11;
int world;
static int hoge = 22;
static int fuga;
この四つのグローバル変数の宣言方法についてアセンブリレベルの違いを理解したい。
hello
とhuge
は初期化されているので、.dataセクションに配置される。
アセンブリレベルでは以下の違いが出る。
.section __DATA,__data
.globl _hello
.align 2
_hello:
.long 11
.section __DATA,__data
.align 2
_hoge:
.long 22
.globalの宣言がされていないと、同じファイルからしかアクセスできない変数となる。
以下二つの違いは複雑。
int world;
static int fuga;
未定義な変数は.bssセクションに配置するらしい。.bssセクションに配置する方法は二つ?あって、
.comm
を用いるものと、.zerofill
を用いるものがある。
.commで宣言するとグローバル変数になって、.zerofillで宣言するとそのファイルでしか使えない変数になるんだと思う。
なので上記のコードは次のようになる。
.comm _world,4,2 ; @world
.zerofill __DATA,__bss,_fuga,4,2 ; @fuga
ただ、.zerofillで宣言したものをglobalにすることは可能らしく、以下のコードも正しく動作する。
.globl _world
.zerofill __DATA,__bss,_world,4,2
グローバル変数の練習。以下のコードをコンパイルする。
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]
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;
}
文字列をグローバル変数に展開する方法。
.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
データを並べる。
色々な文字列の宣言方法。
#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
}
GNU C Compilerだと以下の書き方ができる。
int main() {
return ({
11;
22;
33;
});
}
clangでコンパイルするとwarningは出るがコンパイル自体はできる。
左辺に来れる式と右辺に来れる式について細かい話
暇な時に理解しよう。
こういうやばい書き方は許容されるのか?
int main() {
int i = 2, j = 3;
(i = 5, j) = 6;
return j;
}
構造体の配列はメモリに連続に並ぶ。
#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では連続に並んでた。
複数の配列を持つ構造体は、その配列の要素が連続に並ぶ。
#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]);
}
}
未定義動作だと思う。
structとunionとenumのタグは全て変数名が同じ名前空間に割り当てられる。
struct t {
int x;
int y;
};
union t {
int x;
int y;
}; // error
enum t {
x,
y
}; // error
上記のような同じタグ名の宣言はできない。
一方でローカル変数とタグ名は別の名前空間に存在するため、同じ名前が可能である。
struct t {
int x;
int y;
};
int main() {
struct t a;
a.x = 1;
int t = 2;
return a.x + t;
}
typedefで定義した型はローカル変数と同じ名前空間に割り当てれる。そのため、以下のコードは正常に動作する。
struct t {
int a, b;
};
typedef struct t t;
構造体のタグ名とtypedefの型名を同じに出来る。
typedefで定義した型名はローカル変数と同じ名前空間に割り当てられるため、以下のコードはエラーになる。
typedef int t;
t t = 22;
t x = 22;
とすればコンパイルが通る。
gcc
だと通るけど、clang
だと通らないコード。
.globl main
main:
movl $11, %edi
movsxd %edi, %rax
ret
movsxd
はgccだと使えるけど、clang
だとエラーになる。
int
やlong
があるのに、int64_t
があるのはなぜか。
64bitのCPUの場合、一般的にint
は32bitでlong
は64bitである。
32bitのCPUの場合、一般的にint
は32bitでlong
は32bitであるが、long
を64bitとすることもある。
C言語は、CPUが16bitの時代から存在してるので、int
やlong
のbitサイズを特に定めているわけではない。long
はint
より大きいとして定めているだけである。
そのため、明示的にbitサイズを定める型が必要になってint64_t
がある。
C言語の仕様は以下のように定めている。
short: 最小16bit
int: 最小16bit
long: 最小32bit
long long: 最小64bit
32bit CPUの場合
short: 16bit
int: 32bit
long: 32bit
long long: 64bit
64bit CPUの場合
short: 16bit
int: 32bit
long: 64bit
long long: 64bit
サーバーやデスクトップパソコンだと32bitはなくなったためlong longを使う機会はない。全てlongで良い。マイコンを扱う場合はまだ16bitや32bitの場合があるのでlong longを使う機会がある。
次の二つの違い。
char *x[3];
char (*x)[3];
覚えるしかない気がする。
char *x[3];
「charへのポインタ変数」の配列(長さは3)
64bitシステムだったら64bit * 3のスタックを消費する。
char (*x)[3];
「charが3つの配列」へのポインタ。
64bitシステムだったら64bitのスタックが消費される。
複合技も可能
char (*x[2])[3];
「charが3つの配列」へのポインタの配列(長さは2)
64bitシステムだったら、スタック領域を128bit消費する。
C言語で最難関の文法かも。
一つ覚え方がある。main関数の引数はこうなってる。
char *argv[]
これが「charへのポインタ変数」の配列で、オプションの数だけポインタが作れられることは直感的にわかるはず。
何に使うかわからない書き方。
void *x;
以下の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される。
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を明示的に使い分けできる。
ARMにおける大きな数の取り扱い。
mov命令でx0に65536より大きい数を代入することはできない。
mov x0, 65537
これを実行するとexpected compatible register or logical immediate
というエラーが出る。
ちなみにw0には65536より大きい数を代入することができる。
mov w0, 65537
x0に大きい数を代入するには、movk命令を用いる。
65537を代入するには以下のようにする。
mov x0, 1
movk x0, 1, lsl 16
上記をC言語ぽくかくと次のようになる。
x = 1 + (1 << 16);
レジスタの下位数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
以下のコードのように使う。
.global _main
.p2align 2
_main:
mov w0, 0xFF0a
sxtb w0, w0
ret
sxtbで下位8bit (0xa)が取り出される。
アセンブリの割り算。
以下は、x86_64で10%3をするコード
mov $10, %rax
mov $3, %rdi
cqo
idiv %rdi
mov %rdx, %rax
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の値をいれる。
論理積と論理和
#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;
}
0 && 0 = 0
0 && 1 = 0
1 && 0 = 0
1 && 1 = 1
0 || 0 = 0
0 || 1 = 1
1 || 0 = 1
1 || 1 = 1
0 -> Flase
0以外 -> True
&&
と||
は論理積と論理和である。
これらはint型を返す。
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:
(なんだこの謎言語。。)
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:
GOTO文
int main() {
int i = 0;
goto step2;
step1: i ++;
step2: i += 2;
return i; // 2
}
GOTOのラベルは変数やタグ名と名前空間が異なる。
int main() {
struct i {int i;} i;
i.i = 0;
goto i;
i: i.i +=2;
return i.i; // 2
}
(このコードおもろくない?)
シフト演算
x = 1;
x << 2; //4
x <<= 2;
x; // 4
y = 16;
y >> 2; // 4
y >>= 2;
y; // 4
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言語の式でコンパイル時点で値が決まるものを整数定数式と呼ばれている。
sizeofも整数定数式なので以下のようなコードはコンパイル通る。
#include <stdio.h>
int main() {
int i = 1;
switch (4) {
case sizeof(i):
printf("Hello");
break;
}
return 0;
}
他にも四則演算や3項演算は整数定数式である。
整数定数式の仕様?
配列宣言時のサイズ指定にも整数定数式が使える。
int x[sizeof(int)];
ちなみに、(私のコンパイラは)C言語の配列のサイズは実行開始時には完全に定まってないといけない。
ただ、最近のCは定まってなくていいらしく、Clangとかは以下のコードを正常に処理できる。
int a;
scanf("%d", &a);
int x[a];
enumの初期値も整数定数式が使える。
enum { sz=sizeof(int) };
プリプロセスにおいても、整数定数式の評価が行われる。
以下のような書き方が可能。
#if 1+1=2
#include<stdio.h>
#endif
グローバル変数についても整数定数式の評価が行われる。
以下のような書き方をした場合、実行バイナリのデータ領域には2が入ってる。
int a = 1 + 1;
int main() { return a;}
グローバル変数の宣言とか整数定数式とかプリプロセスとか実装して思ったけど、C言語って式がどのタイミングで評価されるかを隠蔽されてるんだなぁ。この評価タイミングの隠蔽って偶然そうなっちゃったのかな。それとも言語設計者が意図的に隠蔽してるかなぁ。
memsetをアセンブリで実装する方法。
x86_64には、以下の命令がある。
rep stosb
以下の命令と等価である。
memset(%rdi, %al, %rcx)
alは8bitのレジスタである。(raxの下位8bit)
alに指定した値をrdiからrcx個だけ書き込む。
メモリを一気に初期化する際に使える。
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を書き込む。
以下の二つが同じ
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);
グローバル変数の宣言時に使える計算
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
グローバル変数の宣言では、整数定数式と他のグローバル変数へのポインタが計算として使える。コンパイラは、コンパイル時にこれらの計算を行ってバイナリに直接データを書き込む。
グローバル変数とローカル変数は全くの別物であることがよくわかる。
グローバル変数はプログラムに静的に書き込まれているので、コードがメモリに展開されるのと同時にメモリに展開され、コードが終了するまでメモリに生存し続ける。ローカル変数は関数呼び出し時にスタックに積まれるだけ。全く別物。
ローカル変数がスタックに積まれていることがわかるコード
以下のコードの結果は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がこういう動作をしていただけ。
発展型。以下のコードは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を取り出して引き算して返している。
(私のパソコンでは)スタックはメモリが大きい方から始まって小さい方に伸びる。詳しい説明は以下の記事の「コラム: スタックの伸びる方向」を参照
なので、配列arrを用いてスタックの値を取り出すときは、添え字は負の方向に伸びることになる。
そのため、arr[0]はスタックの一番上に積まれた変数xの値を取り出し、arr[-1]はスタックの二番目に積まれた変数yの値を取り出す。なのでarr[-1] - arr[0]
は11を返す。
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];
}
初見殺しすぎない?
Variable Length Array (VLA)やalloca()
を除き、C言語は関数内のローカル変数が利用するメモリのサイズはコンパイル時に確定する。抽象構文木を作るタイミングで、関数内のローカル変数のリストを作成しする。コード生成のタイミングでそのリストを参照しながら、関数内のローカル変数の位置を確定させる。
関数内のローカル変数はスタックを用いるだけなので、コンパイル時にサイズが確定してる必要は必ずしもない。それを確定させるようにしている。これは、Cの言語仕様の工夫点なのかもしれない。。
C言語のGOTO文
確かにC言語のGOTO文は悪だけど、使わないといけない場合があるらしい。
エラーハンドリングとか、メモリの解放とかでは使わないといけない場合があるらしい。(C言語にTry/CatchがないこともGOTO文を使う場合がある一つの原因らしい。)
以下はLinuxカーネルのUDPの実装である。gotoで検索するとゴリゴリ使っている。
GOTO使わなくても書けそうなコードありそう。(try_againとか...)
うーん。低レイヤだと綺麗にならないのかもなぁ。
Rustでカーネル書いてる人はResult型でなんとかしてるのかなぁ
Result型って確かに安全だけど、すごく大変な気がするけどなぁ
C言語における宣言
以下のように宣言が可能。
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;
}
未定義動作かも
宣言の際に最後にカンマを付与できる。
int main() {
int x[] = {1, 2, 3, 4,};
return x[0] + x[1] + x[2] + x[3];
}
以下のような宣言も可能。
#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を移植する際はこの辺面倒くさそう。
.data
と.bss
の違い。
グローバル変数宣言したとき、初期値があるものは.dataに展開される。
未定義のものは.bssに置かれる。
未定義なグローバル変数を定義する。
int y[10];
上記のこのコードをARM64のアセンブリに直すと以下のようになる。
.globl _y
.zerofill __DATA,__bss,_y,40,2
40と2の意味を理解したい。(これを理解するには.p2align
を理解しないといけない気がする。)
extern
について
extern
は外部のファイルで定義されたグローバル変数と関数が使えるようにする構文
alignof
とalignas
について
alignasは宣言時に使う。
alignofはアライメントの確認に使う。
static
について
C言語のstaticは以下の3パターンがある。
- 関数内部でローカル変数の宣言時にstaticをつけることで、データセグメントに変数を配置できる。
- 関数宣言時にstaticをつけることで、その関数をファイル内でしか呼び出せなくなる。
- グローバル変数の宣言時にstaticをつけることで、その変数をファイル内でしか呼び出せなくなる。
- 関数内部でローカル変数の宣言時に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
}
- 関数宣言時にstaticをつけることで、その関数をファイル内でしか呼び出せなくなる。
- グローバル変数の宣言時に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
のようにグローバルであることが明記されている。
基本的には名前空間の汚染を防ぐのに使われる。
複合リテラル compound literals
ARM64のb
とbl
の違い。
詳しい説明は以下にある。
M1 Macの可変長引数の関数呼び出し
x86_64と全然違くて苦戦した。
以下のような関数を、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が呼び出せるため非常に便利。
固定長の引数が8個以下の場合は、全てレジスタで渡す。8個を超える場合は超えた分をスタック渡しする。
また、可変長の引数は全てスタック渡しする。
上記の例だと、x0
に変数n
を入れて、数値11
, 22
, 33
はスタックに入れる必要がある。
図で示すと以下のようになる。
レジスタ:
x0 = 3
スタック:
--- sp + 32
--- sp + 24
33
--- sp + 16
22
--- sp + 8
11
--- sp
このようにスタックに値を詰めていく際には、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確保してから書き込むという手がある。
もう一つの方法として、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
やってることは同じ。
コード生成器の実装方法
以下のコードをアセンブリにする際のコード生成機の実装方法を紹介する。
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は右から左に評価しているようである。
ちなみに私のM1 Macに入っているclangで、clang -S -O0
出てくるアセンブリは左から右に評価している。
以下のように二つの再帰関数を用いて実装すると綺麗に実装できる。
// 可変長引数の部分をスタックに配置。(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);
引数が浮動小数点数の場合もこれをベースに実装可能だと思う。
この実装に限らない話だけど、連結リストを処理する時に、根から処理する場合はFor文で実装すると綺麗に実装できて、葉から処理する場合は再帰で実装すると綺麗に実装できる(気がする)。
この考えを一般の木構造へ展開する場合は、それぞれBFSとDFSが対応する。
木構造をBFSで処理する場合にFor文を選ぶか再帰を選ぶか、DFSで処理する場合にFor文を選ぶか再帰を選ぶかは、実装する際に選択が迫られると思う。その際に以下の表を覚えておくと良いかもしれない。
BFS | DFS | |
---|---|---|
For文 | Queueを用意する | Stackを用意する |
再帰 | 通常不適切 | 追加のデータ構造が通常必要ない |
再帰下降構文解析で構文解析した木構造は、木の葉側の演算の優先度が高い。そのためDFSで処理すると追加のデータ構造を必要としない。そのため、chibiccではcodegen.cで再帰関数を書いてるのだと思う。逆に再帰関数が嫌いな人が、codegen.cをfor文で書き直そうと思ったら、Stack構造を追加で用意する必要が出てくる。
これは、競プロでも使えそうな知見。
数値の型変換
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
}
上記のコードは、型が共通なのでキャストは行われない。
アセンブリに直す場合
-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を用いる
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;
}
C言語であまり使われない予約語
const, volatile, auto, register, restrict, _Noreturn
const
値が変更不可能な定数を宣言するための限定子。
これはよく使う。
volatile
変数への読み書きが毎回物理的に行われることを強制する。
メモリマップされたデバイスレジスタや割り込みサービスルーチンで使用される変数に使われる。
auto
変数が自動的に(自動ストレージ期間)初期化され、そのスコープ(通常はブロック文の終わり)を出たときに自動的に破棄されることを示す。C99から、「auto」キーワードは廃止され、現在では、変数宣言時に自動的に推測される。
register
数が頻繁にアクセスされる可能性があることをコンパイラに示すために使用される。
restrict
ポインタが指すオブジェクトが他の任意のオブジェクトとエイリアス(別名)を持たないことを表す。
_Noreturn
この関数修飾子は、関数が戻ることはない(つまり、return文を持たないで終了する)であろうと、コンパイラにヒントを与えるためのもの。
ARM64の浮動小数点数
浮動小数点数ってすごい複雑っぽい
規定に従うのは難しそう。
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の浮動小数点数を単一の値として足し算を行う命令は存在しない
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を同時に足し合わせることが可能である。
ARM64のアセンブリで浮動小数を扱う。
レジスタ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の説明は、以下のウィキペディアがわかりやすい。
上記のアセンブリを出力するためには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の宣言も同様にできる。
コンパイラによっては、以下のように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
ARM64の整数と浮動小数点の変換
u32, i32, u64, i64, f32, f64の間の変換方法をまとめる。
整数から浮動小数への変換
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 |
浮動小数から整数への変換
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 |
浮動小数から浮動小数への変換
fcvt
From | To | Example |
---|---|---|
f32 | f64 | fcvt d0, s0 |
f64 | f32 | fcvt s0, d0 |
整数から整数への変換
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 |
- 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 |
浮動小数点数のNaN周りの挙動について
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言語と仕様が異なってしまう。注意が必要。
ただ、細かすぎる仕様なのでコンパイラ自作の際は無視してもいいかも。
#include <stdio.h>
について
MacOSの場合は、stdio.hは以下で見れる。
fprintfは以下。
int fprintf(FILE * __restrict, const char * __restrict, ...) __DARWIN_LDBL_COMPAT(fprintf);
stdin
, stdout
, stderr
は以下。
#define stdin __stdinp
#define stdout __stdoutp
#define stderr __stderrp
以下のコードで#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を使ってコードは書くべきである。
上記のコードをアセンブリにすると以下のようになる。
.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
はカーネルとシェルの機能を組み合わせて実装されている。詳細は以下を参考。
frpintf
はlibcとして提供されている。MacOSでは以下で実装されている。
#include <stdarg.h>
について
chibiccのこのコミットがよくわからない。
以下のメモを見ると、全てのレジスタのレジスタの内容と__va_elem構造体の内容を__va_area__というローカル変数に保管しているみたい。
いまいちよくわからない。
以下のコードを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
がある。ビルトインされた関数を呼び出して処理するみたい。
以下で図解されていて、わかりやすい。(複雑で理解できてないが)
x86_64 LinuxとM1 Macでは仕様が異なるだろうから、自分でアセンブリ解析するかドキュメント漁らないといけなさそう。
以下のコードをアセンブリに変換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;
}
bl _format
が呼ばれる直前の状態
レジスタ:
x0 = _bufのアドレス
x1 = l_.strのアドレス
スタック:
--- sp + 32
0
--- sp + 24
3
--- sp + 16
2
--- sp + 8
1
--- sp
普通の可変長呼び出しと変わらない。
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);
}
ついに、自分自身をコンパイルできるようになった。
stage2とstage3のバイナリが一致することを確認した。
また、全てのステージのバイナリがテストをパスすることも確認した。
なんか感動。
まだプリプロセスを実装してないので、python self.pyがないと完全に自立コンパイルはできない。
ちなみに、バイナリの比較は以下で行なっている。
#!/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行だけ差分が出てしまう。
関数ポインタ
関数ポインタを使った簡単なコード
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
ちなみにblr
をbr
と間違えると、ret
で戻って来れなくなるので要注意。
(ちなみに、b
はbranchのbで分岐命令、l
はlink付きのlでリンクレジスタを使う、r
はregisterのrでレジスタのポインタを使う。)
ARM64の場合は、以下のように_exitを呼び出すことはできない。
mov x0, #11
adrp x1, _exit@PAGE
add x1, _exit@PAGEOFF
blr x1
普通に以下を呼び出さないといけない。
bl _exit
こういう書き方も、関数のアドレスを渡して、実行させていると思えばわかりやすい。
int ret11() {
return 11;
}
int call_param(int x()) {
return x();
}
int main(void) {
int ret = call_param(ret11);
return ret;
}
ちなみに、C言語はローカル関数をサポートしてない。ローカル関数を実装するには、抽象構文木をクロージャー変換(ローカル関数をグローバル関数に変換してスコープを絞る処理)をする必要がある。
私のコンパイラ、これが動くんだけどなぜ動くのかはわからない。魔法?
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);
}
これが魔法に感じるの深遠な問題な気がしてる。コンパイラって機能を追加するたびに、できることが指数関数的に増えるわけだけど、その増加スピードが実装者の認知を超える瞬間があるんだろうなぁとか思ったり。自然言語でもこういう瞬間があるから言語学って面白いんだろうなぁとか思ったり。
これをずーっと考えててだんだん問題がわからなくなってきた。一度、言語化してみる。
最初intのみでコンパイラの作成を始めて、intのポインタ、intの配列、intの関数、intの構造体を順番に実装していった。
コンパイラが育ったどっかのタイミングで、コードを数行書き換えてcharやshortやlongを追加した。そうするとすぐに追加した型のポインタや配列や関数や構造体が正しく動くようになった。さらに、型の組み合わせも動くようになった。
その後、型変換を実装していって、ある程度コンパイラが育ったタイミングで数行追加してfloatとdoubleを実装した。そうするとすぐに追加した型のポインタや配列や関数や構造体が動くようになった。
もっとコンパイラが育ったタイミングで関数ポインタを実装すると、すぐに関数ポインタの配列や構造体が動くようになった。
このように、あとから型を追加するとき、1個の型を追加するとそのたびに、コードの量はとてつもなく膨大に増えてく気がする。そうはならなくて数行書き換えるだけで型を追加できるのはなぜなのか?
うーん。BNFのように文法を書いた時点で言語機能が指数関数的に増やせるというのはあたり前な気がしてきがするが、それでも関数ポインタを実装したらその瞬間に関数ポインタの配列や、関数ポインタを要素に持つ構造体が正しく動作するのは魔法に感じるんだよなぁ。なんでだろう。