About

Rui Ueyama「低レイヤを知りたい人のためのCコンパイラ作成入門」^[1]とchibicc^[2]を参考にCコンパイラを実装する。目標はセルフホストを達成すること。

脚注

9/13

構造体

以下の内、struct {int a; int b;}の部分が型。メンバ変数用の構造体を作成し、TY_STRUCTを追加してstruct Typeに構造体のメンバリストを持たせる。structを読んだら{}の中を順番にparseしていってメンバリストに登録する。この時にメンバ変数にoffsetを適用し、全体のサイズを型に保存しておく。

{struct {int a; int b;} x; x.a=1; x.b=2; x.a; }

struct Member{
    Member *next;
    Type *ty;
    Token *name;
    int offset;    
};

x.aのような式のためにND_MEMBERを追加する。この入力があった場合、xの型は構造体で、そのメンバリストにaがあるはずなのでそれを探す。ない場合はエラーにし、ノードには参照するメンバへのポインタを持たせる。
codegen側のgen_addrのcase文にND_MEMBERを足し、ND_MEMBERが来たら左辺の変数のアドレスを計算(上の例ではx)して、そのアドレスにアクセスするメンバのoffsetを足すようにする。(メンバへのポインタはND_MEMBERが保持している。)これでメンバ変数のアドレスが得られる。

aligment

現状とれる型はcharかint。struct Typeにalignメンバを追加してそれぞれ1byte,4byteにaligmentする。構造体全体のalignmentは最もaligmentが大きい型に合わせる。構造体にoffsetを適用する部分と構造体のsize計算する部分を変更する。
pointerや配列、構造体を作る時にalignをセットしないとalign_toを呼んだときに0除算が発生してfloating exceptionが出るので注意。

struct tag

構造体を定義するときに毎回

struct {int a; int b;} x;

のように書くのはだるいのでタグ名をサポートして以下のように書けるようにする。

struct T {int a; int b;};
struct T x;

Scopetag構造体を作成する。structの次に{ではなく識別子がある場合は構造体の型名なので使いまわせるようにリストに保存する。構造体のタグ名は以下のようにスコープがあるのでScope構造体にScopetagのリストを持たせるようにする。

#include <stdio.h>

struct T{
    int a,b;
};
int main(){
  struct T{
    char c;
  };
  printf("%ld\n", sizeof(struct T));// 1
  return 0;
}

定義の部分が以下のようになっているおかげでstruct T {int x; int y;}; のように構造体タグのみの定義ができる。

/* delspec declarator ("=" expr)? ("," declarator ("=" expr)?)* ";" */
static Node *declaration(void){
    Type* base = delspec();
    Node head = {};
    Node *cur = &head;
    while(!consume(";")){
        Type* ty = declarator(base);
        Obj *lvar = new_lvar(get_ident(ty -> name), ty);

        if(consume("=")){
           cur = cur -> next = lvar_initializer(lvar);
        }
        if(consume(",")){
            continue;
        }
    }
    Node *node = new_node(ND_BLOCK);
    node -> body = head.next;
    return node;
}

->operator

xの型が構造体へのポインタ型の時、x -> aのようにしてメンバにアクセスできるようにする。x->aは(*x).aのsynax sugarなので変換すればいいだけ。*が後置ならこの構文は必要なかったという小話もある。

r1ru

9/14

Union(共用体)

共用体はほとんどstructと同じ。唯一違うのは各メンバがメモリ領域を共用すること。そのため共用体のサイズは最も大きいメンバに合わせる。

void型を追加

void型は値を返さない関数の宣言や定義に使う。関数の返り値がvoid型ならコンパイラは返り値を取得するコードを生成する必要がない。
void型のpointerのデリファレンスやvoid型の変数の定義はエラーにする必要がある。

関数の宣言を追加

現状、関数呼び出しが合ったらそれが定義されているかに関係なく、関数呼び出しのコードを生成するようになっている。これを改善して最終的には宣言がない関数呼び出しはエラーにするようにしたい。そこでとりあえず以下のようにトップレベルに関数の宣言が来れるようにする。parserは()の後に;があれば宣言であるとみなしてObjを生成してglobalsにつなげる。codegenはglobalsをたどりながらコードを生成するので宣言を飛ばせるようにstruct Objにis_definitionというメンバを追加する。

int hogehoge();

r1ru

9/15

多次元配列を追加

int a[2][3];

という入力があった場合、aの型はintの配列(要素数3)の配列(要素数2)。int a[2] まで読むと、aが配列で、要素数が2ということまでは分かるが、何の配列なのかは確定しない。後ろの[3]を読んで初めて、intの配列(要素数3)の配列であることが分かる。

a[1][1] = 1;

という入力をparseすることを考える。これは単純にx[i]を*(x + i)に置き換えるだけでいい。
parserはa[1]を*(a + 1)に変換して、続いて[1]を読むので*(*(a + 1) + 1)になる。aの型はintの配列(要素数3)の配列(要素数2)で、ND_ADDの型も同じになる。ポインタ演算が実装できていれば(a + 1)は(a + 12)になり、ND_DEREFの型は参照を一つ外したものになるのでintの配列(要素数3)になる。従って(*(a + 1) + 1)は(*(a + 1) + 4)になり、全体としては*(a + 12 + 4)になるのでうまくいく。p + 1は、p + sizeof(p -> base -> ty) * 1になることに注意。多次元配列の初期化式は面倒なので飛ばす。

ネストした型宣言を導入

char (*a)[3];

を考える。aの型はchar型の配列(要素数3)へのポインタ型なので、sizeof(a)は8になる。()がない場合は素直に前から読めばいいので問題ないが()がある場合、前から順番に呼んでいくと困ったことになる。aを読んだ時点でaの型を確定させることができないからだ。aの型を確定させるにはまず()の部分を飛ばして外側を確定させる。()を以下のように識別子に置き換えてやると分かりやすい。

char x[3];

()の中を無視するとこれはchar型の配列(要素数3)になる。ここまで読んで初めて()の中を読む。するとaの型がchar型の配列(要素数3)のポインタ型だと確定する。Cの宣言はこのように前後にいったりきたりする必要があるので前から順番にトークン列を消費しながらparseする実装だと面倒くさいということを実感した。

handle complex type declaration

long long intとか書けるようにする。この実装はchibiccのコードがめちゃくちゃ参考になった。

typedefを追加

typedefは変数定義と同じように以下のように一気に複数定義できる。

int i, *p1, **p2;

また、typedefは関数の仮引数や構造体、共用体のメンバにはこれないため、これをエラーにする必要がある。
また以下のように既存の型が指定されていない場合はデフォルトでintになる。

typedef t;

chibiccのテストケースには以下のようなコードが含まれていたがこれの必要性が分からなかったのとコードを簡単にするためにこういった入力は許さないことにした。また、不完全型を実装するのも面倒なのでとりあえず飛ばした。

typedef int;

sizeofのオペランドに型を取れるようにする

sizeofに渡すときは識別子を以下のように省略できる。declaratorを修正して、識別子がなくてもエラーにならないようにした。これで関数の仮引数とかもエラーにならなくなる。
parserはsizeofを読んだら、(に続いて型名が来るなら型を生成してそのサイズでND_NUMを作成し、そうでなければunary()を読んでノードに型付けした後その型のサイズでND_NUMを作成する。

sizeof(int **)

r1ru

9/18

キャスト

考えられるサイズは8,16,32,64の4つなので、変換の種類は全部で16通り考えられる。本質的なのはfromではなくto。charにキャストするなら、元のレジスタの1byte(al)が有効な値になる。shortにキャストするなら16byte(ax)が有効な値になる。

r1ru

9/19

usual arithmetic conversionを実装

intより小さい型はintになる。オペランドの型が異なる場合はサイズが大きいほうに合わせられる。例えばintとlongならlongになる。どちらかのオペランドのサイズが8byteだった場合はlongにすればいい。

r1ru

9/20

未定義/未宣言の関数呼び出しを禁止する。

戻り値の型変換

char int_to_char(int x) { return x; }のような変換ができるようにする。
ND_RETURNに型変換のコードを追加すればよい。

引数の型変換

int hoge()のように引数に何も指定されていない場合、任意の型を渡せる。
Objにfunc_tyを追加する理由が分からなかったのでこれは追加しなかった。

r1ru

9/21

_Boolを追加

intやcharへのキャストはレジスタの幅を変更するだけなのだが_Boolはそうはいかない。0でない数は全てTrue(1)にする必要があるから。

escape文字とchar literalを追加

問題なのは

char *p = "abc\n";

のように文字列リテラルのなかにエスケープ文字が出てきてしまうとき。コード生成部分で以下のようにして文字列リテラルを確保していたため、okenizeするときにこれを\0aで置き換えてしまうとこのfprintfで改行が入ってしまう。この対策として、文字列リテラルだけは.byteで確保するように変更した。冗長だが処理がより簡単になる。

 fprintf(STREAM, "\t.ascii \"%s\"\n", gvar -> str);

以下のようにエスケープシーケンスの処理をprintfに丸投げすることも考えたが、あまり簡単にならなそうなのでやめた。

int n = sprintf(buf, "abc\xde\xad\xbe\xef");

r1ru

9/22

enumを追加

enumの中をparseして初期値が指定されていればそれで、されていなければ0から順に割り当てる。enumの中は、初期値があるラベルとして考えればいい。

file scope functionを追加

今まで関数のラベルを.globalにしていたが、staticが指定されていた場合は.localにするように変更する。
現状実装しているstorage class specifierはstaticとtypedef。これらを同時に指定することはできないので複数指定されている場合はエラーにする。

for文で変数を定義できるようにする

以下のように文法を変更する。

"for" "(" expr?  ";" expr? ";" expr? ")" stmt | "for" "(" declaration? expr? ";" expr? ")" stmt

for文の最初にdeclarationが来る可能性があり、declarationはND_BLOCKを返すようになっている。つまりコード生成側で一番眼だけはgen_exprではなくgen_stmtを呼ぶ必要がある。そのため最初がdeclaration出なかった場合(つまり式だった場合)、ND_EXPR_STMTを返すようにする。

for文のparseしている間は別のスコープに入るようにして、外に同じ名前の変数名があっても問題ないようにする。

int main(){ 
    int i = 2;
    for(int i=0; i <10;){
        i = i + 1;
    }
    return i; // 2
}

r1ru

9/23

+=,-=,*=,/=を追加

chibiccの通りにA op = Bを、tmp=&A, *tmp = *tmp op Bに読みかえた。この部分は無駄だと思ったが、単純にA op = BをA = A op Bに読みかえるのでは、後の後置インクリメントとデクリメントがうまくいかなかった。うまくいかなかったテストケースは以下。

ASSERT(0, ({ int a[3]; a[0]=0; a[1]=1; a[2]=2; int *p=a+1; (*(p--))--; a[1]; }));

 (*(p--))--

以下の部分が問題で、単純にA op = BをA = A op Bに読みかえると以下のようになる。

(*((p = p - 1) + 1) = *((p = p - 1) + 1) -1 ) + 1

左辺はpの値(a[1]のアドレス)、右辺の*((p = p - 1) + 1)は本来ならa[1]の値になってほしいが、左辺の代入式でpが書き変わっているのでa[0]の値になる。つまりこれはiにa[0] - 1を代入することになり、全体の評価結果はa[0] - 1 + 1 = a[0] = 0 になる。これは意図した動作ではない。

 (*(p--))--

を計算するときは()の中の評価結果を一時変数に保存しておいて、それを利用する必要がある。これがchibiccの実装が上記のように一見すると冗長なコードになっている理由だと思われる。(違うかも)

++と--を追加

++iのように前方にくる場合、この式の評価結果は加算された後の値になる。これは簡単で、++iを、i += 1に読みかえればいい。--iはi -= 1に読みかえる。
i++のように後方にくる場合、以下のようにこの式の評価結果は加算される前の値になる。しかしiはインクリメントされる必要がある。
これを実現するために、i++を(int)((i += 1) - 1)に読みかえる。

#include <stdio.h>
int main(){ 
    int i = 0;
    printf("%d\n", i++); // 0
    printf("%d\n", i); // 1
}

r1ru

9/24

数値リテラルを実装

tokenizerで変換する。0xなら16,0なら8,0bなら2進数として読む。10進数への変換はstrtoul関数を使う。
strncasecmpは大文字と小文字を区別しないで比較するための関数

!を実装

論理を反転するので、0と比較して等しかったらraxに1を格納するようにする。等しくなければraxには0が格納される。つまり論理的には0以外の整数は真として扱うことになる。

~を実装

~はbit notで、bitを反転する。これにはnot命令を使う。

%と%-を実装

idiv命令はrdx:raxをオペランドで割り、余りをrdxに格納するのでND_MODの時はrdxの値をraxに代入するようにする。

&,~,|と&=,~=,|=を実装

これらの演算子には| < ~ < &という優先順位がるのでこれを考慮する必要がある。
これらはbinary operatorなので、例えば&なら、and rax, rdiを出力すればいい。bit演算子の内、~(BITNOT)だけはunary operator。

&&と||を実装

|| < &&という優先順位があり、前に実装したBITORやBITANDよりも優先順が低いことに注意。
&&は左辺と右辺がどちらも真の時に真になる。左辺が偽の時は全体の評価結果も偽なので右辺を評価する必要はない。||も同様に左辺が真のときは全体の評価か結果も真なので右辺を評価する必要はない。そのため&&の場合はまず左辺を計算して0と比較し、等しければraxに0を格納するコードに飛ぶ。等しくなければ右辺を評価して0と比較し、等しければraxに0を格納するコードに飛ぶ。その後にraxに1をセットするコードを置いておくようにする。||の場合は左辺を計算して0と比較し、等しくなければraxに1を格納するコードに飛ぶ。等しければ右辺を計算して0と比較し、等しくなければraxに1を格納するコードに飛ぶ。その後にraxに0を格納するコードを置いておく。ここで1ではなく0と比較しているので0以外の整数値が真と解釈される。

r1ru

9/25

不完全型の概念を導入(配列)

既に配列の初期化式とグローバル変数の初期化式を実装していたが、不完全型の概念を実装した後に実装したほうが見通しが良くなると思ったので削除した。
今までは配列の要素数が指定されることを期待していた。しかしC言語では以下のように配列の要素数を省略することができる。これが許されるようにする。ただしまだ配列の初期化式を実装していないので、declarationでty -> sizeが負ならエラーにしている。ただ、これだとint a[][];はコンパイルエラーにならない。この型のサイズは4(sizeof(int) * -1 * -1)になるため。
→? 0じゃだめなのか？

int a[][3] = {{0,1,2}, {3,4}}

配列をポインタに読みかえる(関数の仮引数のみ)

関数の仮引数宣言でのみ配列型が先頭要素へのポインタ型に読み替えられる。

不完全型の概念を導入(構造体)

今まではstruct Tの後に{が来ていなければ、既にstruct Tが宣言されていることを期待していた。このステップでは不完全な構造体を許す。
これを実装することで以下のように構造体のメンバにその構造体自身を取れるようになる。

struct T{struct T *next, int x;}

struct Tの後に{が来ていない場合、既にstruct Tが定義済みか、不完全型かの二つが考えられる。そのためstruct_union_decl関数を変更し、struct Tの後に{が来ていなければtag名を検索し、見つかればそれを返し、見つからなければ不完全型なのでとりあえず構造体型を作ってtag名で検索できるようにリストに登録する。struct Tの後に{が続く場合は構造体の定義なのでparseして型を作成する。この後に現在のスコープに同じタグ名がないか検索して、あればそれは不完全型であることを意味するので作った型で上書きする。

gotoを追加

定義されていないラベルへのジャンプはエラーにしたいが、goto label; の後にlabelの定義がくる場合があるのでgoto文をparseしている時点ではこれをエラーにすることはできない。goto文と、labelのリストをそれぞれ作成して、関数のパースが全て終わった時点で名前を解決する。
自分は最初ノードにはラベル名のみを持たせればよいと思っていて、chibiccがノードにunique_nameメンバを追加していた理由が分からなかったのだが、これはラベル名が関数ごとに独立しているためだった。
現状compound_stmt関数内では先頭がtypenameだった場合、declaration関数を呼んでいる。しかし以下のようにラベルが来る可能性があるので、typenameかつ、次が:でない場合に変更する。

int main(){typedef int foo; goto foo; foo: ; 1;}

r1ru

9/26

break文を実装

whileやforをparseする先頭でユニークなラベルを作り、グローバル変数に保存しておく。このラベルはwhileやforの終わりの部分に張っておく。break文を読んだら、対応するラベルにジャンプするようにする。この時対応するラベルがなければエラーにする。forやwhileは入れ子になる可能性があるのでfor,whileの先頭で現在のラベルを保存して新しいラベルを作成して上書きし、for,whileを抜けたら元のラベルに戻すという処理にする。

contninue文を実装

実装はbreak文とほぼ同じ。ジャンプする場所が異なる。以下のプログラムを考える。

for(init; cond1; inc;){
    stmt1
    if(cond2) continue;
    stmt2
}

実行される順番はinit -> cond1 -> stmt1 -> if(cond2) continue -> stmt2 -> inc。
cond2が真の時、continue;が実行されるがこのときstmt2は実行されない。つまりcontinueで飛ぶべき場所はincの先頭。

switch-caseを実装

switch(cond){
    case const:
         stmt
    default:
        stmt
}

caseを読んだらND_CASEを作成する。このノードにはconstとユニークなラベルを持たせる。
switchを読んだらND_SWITCHを作成する。このノードにはND_CASEの連結リストを持たせる。
codegenではまず先頭でcondを生成し、ND_CASEの連結リストをたどりながらconstとraxを比較して等しければ対応するラベルにジャンプするコードを入れる。
switch-caseではbreak文を取れる。breakが来たら最後にジャンプするようにする。すると自然にfall throughが実装できる。
switch-caseの中に該当するものがなかったときはswitchから抜ける必要がある。
複数のデフォルト文はエラーにする。switchの中以外のcaseやdefaultはエラーにする。
chibiccではcondの型によって比較に使うレジスタのサイズを変えていた(rax or eax)が、これをする必要が分からなかったので採用しなかった。型を意識する必要があるのはメモリへの書き込みと読み込み時のみであり、計算するときは全て64bit幅で扱った方が簡単になるのではと思っているが違うのだろうか？

<<,>>,<<= , >>= を実装

シフト演算を実装する。シフト演算は+や-よりは優先順位が低く、比較演算子(<,<= etc)よりは優先順位が高い。
<<にはshl命令、>>にはsar命令を使う。これらはそれぞれshift left, shift arithmetic rightの略(たぶん)算術シフトは上位ビットを保ち、論理シフトは上位ビットを0する。つまり算術シフトを使うと符号を変えずにシフトすることができる。
これらの命令は第二オペランドとして8bitの即値かレジスタを取る。<<と>>はbinary operatorなので第二オペランドはrdiに格納されている。しかしrdiレジスタの下位8bitにアクセスることはできないのでchibccではrdiレジスタの値をrcxにコピーしてから第二オペランドとしてclを指定している。
chibiccでは左辺の型によって場合分けが入っていたが入れる意味が分からなったので採用しなかった。

?:operatorを実装

:? operatorは||や&&より優先度は低く、=や+=より優先度が高い。

logor ? expr : conditional

logorを評価して評価結果が真ならexprを実行、偽ならconditionalを実行する。logorを評価後0と比較して等しければ(偽ならば)conditionalに飛ぶようにすればいい。

constant expressionを実装

配列の要素数やenumの値をしてする部分、caseの右辺には今まで数値しか許していなかった。ここにconst expressionが取れるようにする。実際に値を埋め込む必要があるので構文木を下りながら計算して計算結果を返すeval関数を作成する。ND_VARやND_ASSIGN, ND_FUNCALLは許されない。

r1ru

9/27

初期化式の実装では再帰が多用されていたのでコードの動きを把握するのが難しい。これは後回しにしたくなるな...

ローカル変数の初期化式を実装

簡単のため、配列の初期化式は全ての式が明示的に与えられていることを期待する。配列の要素数の省略もまだ実装しない。chibiccのコードを写経した。new_initiralizer関数はメンバの数だけInitializer構造体を作成する。Initializer2関数は初期化式をparseして対応するInitiaizer構造体のexprメンバにparseした構文木のポインタをセットする。create_lvar_init関数はInitializerの木を下りながら代入式に読みかえていく。

初期化式が指定されていない要素を0初期化する。

以下のように配列の初期化式が指定されていない場合、0に初期化する必要がある。そのために先頭に配列のサイズ分0初期化するコードをいれる。これを実現するためにrep stpsb命令を使う。詳細はchibiccのコメントに書いてある通り。

int x[3] = {}

今までは配列の全ての要素に対して初期化式が指定されていることを前提していたが、ここからは省略可能になる。initializer2関数の配列の要素数でループしている部分にtokenが"}"でなければという条件を追加する。また、create_lvar_init関数も変更する。init -> exprがなければ初期化式が指定されていないので代入式を作る必要がないのでND_NULL_EXPRを返すようにする。

過剰な初期化式を読み飛ばす

以下のように配列の要素数よりも多い初期化式が指定されている場合、読み飛ばすようにする。(個人的にはこれはエラーにするべきではと思うのだが...)initializer2関数を変更して初期化式の数が配列の要素数よりも多ければ}まで読み飛ばすようにする。

int x[2] = {0,1,2};

配列を文字列で初期化できるようにする

以下のような式が書けるようにする。

int char [4] = "abc";

一番外側のみ配列の要素数を省略できるようにする

以下のように一番外側のみ配列の要素数の省略を許す。

int x [] = {1,2,3}

1番外側のみしか省略できないのはは以下のように配列の初期化式の数は省略したり過剰に与えたりできるので内側の要素数は簡単には判断できないから。最大値を取ればいけると考えられるが、そういう賢い推論はサポートされていない。

int x[][] = {{1,2,3}, {4,5}, {6,7,8,9}}// int x[3][3] or int x[3][2] or int x[3][4]

Initizlier構造体にbool is_flexibleメンバを追加して、new_initializer関数で初期化式の左辺が要素数指定なしの配列の場合はis_flexibleをtrueにセットする。array_intializerとstring_initializer関数の先頭で
init -> is_flexibleだった場合、Initializer *initを書き変える。配列の初期化式の場合は初期化式をたどって数を数え、文字列の場合はその長さをとって配列の要素数とする。なお、今まではdeclaration関数の中でdeclspecを読んだ後にty -> sizeが負であればエラーを吐くようにしていたがこのコードを初期化式を評価した後に移動しておく。

r1ru

9/28

構造体の初期化式

構造体も配列と同じく過剰な初期化式は読み飛ばす必要がある。

別の構造体で初期化できるようにする

左辺が構造体かつ、=の次が{でない場合、普通にparseして型付けする。TY_STRUCTなら初期化式に追加する。
構造体に構造体を代入する式をサポートしていなかったのでここで追加した。load関数の先頭で型が構造体か共用体だった場合は配列と同じように即座にreturnするように変更する。これで右辺の式を生成した結果として構造体のアドレスが返るはずなのでstore関数の中で構造体のサイズ分ループして1byteずつコピーする。冗長だが、型を意識しなくていい分実装が簡単になる。

共用体の初期化式を追加

chibiccのコメントにあるが共用体の初期化式は構造体とは違って式が一つしか許されないらしい。ただ手元の環境で試したら警告が出るだけでエラーにはならなかった。gccはスキップするようになっているのか?
上の過程を置くと先頭のメンバへの代入式を作るだけなので構造体と比べても簡単。

r1ru

9/29

グローバル変数の初期化式

ローカル変数の初期化式の実装で、初期化式のparserは完成している。これを使いまわす。ローカル変数との唯一の違いは変数の初期化式の値をバイナリに埋め込む必要があるということ。heapで確保したバッファに値を書き込んで文字列リテラルの時と同じように.byte命令を用いて1byteずつ確保する。冗長だが型を意識する必要がないだけコードが簡単になる。(型を意識し出すとif分のネストが多くなる。)
グローバル変数の初期化式では定数式だけでなく、アドレス+定数式という形が取れる。(xはグローバルに定義済みとする)

int y = &x + 2;

この値はリンク時に決まるのでコンパイル時に直接値を埋め込むことはできない。コンパイラは以下のコードを出力する。

global x
x:
    .quad y + 8

これを実装する。

chibiccでは新たにeval2関数を定義しているが、これは第二引数にNULLを指定してevalを呼び出しているだけ。ラベルが来る可能性があるのはND_ADDとND_SUBのみなので、その他の場所でeval関数の第二引数にNULLを指定するように変更するよりはこっちの方が変更箇所が少なくて嬉しい(?)

r1ru

9/30

この日実装した機能達は個人的には実装する必要性を感じなかった。(お行儀の悪い書き方を許してしまっているだけなのではとも思ったり...)飛ばしてもいいかも。

冗長な括弧を省略できるようにする。

以下のように冗長な括弧を省けるようにする。

union { int a; char b[8]; } g13[2] = {{0x01020304}, {0x05060708}};

スカラーを{}で囲めるようにする。

初期化式が一つの場合は{}で囲んでもよくする。以下のように。(いるかこれ？)

int x = {3};

余分な,を許す

以下のように余分な,が書けるようにする。(いるかこれ?)
今までは}が来たら終了とみなしていたが、それに加えて,の次に}が来ていたら終了とみなす。

int a [] = {1,2,3,}

r1ru

10/1

初期化されていないグローバル変数を.bssセクションに移動

.dataとは異なり、.bssにはデータのサイズのみが記録されている。(.dataだとサイズ分が0埋めされている)このため初期化されていないグローバル変数を.bssに移動するとelfファイルのサイズが小さくなる。

flexible arrayを追加

構造体の最後のメンバのみ、初期化式の指定なしで要素数が指定されていない配列を置ける。それはflexible arrayと呼ばれる。この配列は要素数が0の配列のようにふるまう。flexble arrayのみの構造体は作れない。以下のように使うらしい。

struct S{int x; int y[];};
int main(){
    struct S *s = malloc(sizeof(struct S) + 4 * sizeof(int));
    s -> y[2] = 1;
}

flixible array memberを初期化できるようにする

構造体、共用体のメンバとしてflexble array memberが取れる。array_inititlizer1,2関数によって要素数の指定がない配列型は初期化式の数によって適切に修正されるが、これはメンバの型が修正されるだけなので今までのようにinititlizer関数の中でty = init -> tyとするだけではうまくいかない。
chibiccでは構造体/共用体がflexible array memberを持っているとき、型情報をコピーして、
flexbile array memberの型(最後のメンバの型)をinit -> children[mem -> idx] -> tyに書き変えている。コピーしているのはstruct S{int x; int y[]};の情報を残しておくため。これをやっているのがcopy_struct_type関数。

struct S{int x; int y[]};

int main(){
    struct S s = {1,2,3,4};
    printf("%d\n", sizeof(struct S)) // 4
    printf("%d\n", sizeof(s)) // 16
}

voidを関数の引数にとれるようにする。

今までは関数が引数を取らないときは単にfunc()としていたが、以下のように引数を取らないときはfunc(void)と書けるようにする。実際func()とfunc(void)は違う。前者には引数を渡すことができるが後者に引数を渡すとエラーになる。("()"とすると型チェックが行われない。)func_params関数を変更してvoid)のときはすぐに返るようにする。

int func(void);

グローバル変数をアラインメント

現状グローバル変数の初期値はバッファに格納して、.byte命令で1byteずつコピーしている。構造体のアラインメントは実装されているので、開始アドレスさえアラインメントされていればOK。それを実現するために.align命令を使う。

externを追加

ようは実体を生成しなければいい。externだったらis_definitnitionがfalseになるようにして、emit_data関数で変数が生成されないようにする。

extern declarationを追加

関数のブロックの中にexternと関数の宣言を書けるようにする。compoud_stmt関数に少しの変更を加えればいい。
関数の定義をブロックの中にかいてみてgccデコンパイルしたらWarningもエラーも出なかった。関数内関数はGCC拡張にあるのか?それとも言語仕様で許されている?

_Alignasと_Alignofを追加

これらはC11から追加された。_Alignasで変数や構造体のメンバのアラインメントを指定することができる。今まではglobal変数のアラインメントも構造体メンバのアラインメントも、ty -> alignで指定していたが、ここからは直接指定することができるようになるのでMember構造体とObj構造体にalignメンバを追加してこれを用いるようにする。ty -> alignを書き変えることもできるがそれだと意味的に分かりにくくなる。_Alignofは変数や型のアラインメントを返す。この段階では_Alignofの引数として型名だけを許し、ty -> alignを返すようにすればよい。

_Alignofの引数に変数が取れるようにする。

これはGNU拡張らしい。

static local variableを実装

今まではstatic keywordを関数をファイルスコープにすることにしか使ってこなかった。ここでは関数のブロック内でstaticが指定されている変数をグローバル変数として扱うようにする。chibiccでnew_anon_gvarを読んでいる理由は以下のように名前が重複した場合に対応するため。new_gvarで変数名を直接使用するとコンパイルは通るが、globalラベルが重複して定義されるためにアセンブラがエラーを吐く。(まあ現状グローバル変数の重複定義は通るので意味がないと言えばない。)変数にアクセスする際にはfind_var関数が呼ばれているのでこの関数が見つけられるようにpush_scope関数で変数名を現在のスコープに登録する。このようにすると変数名でアクセスできるかつデータを生成時は名前が被らないので正常に実行できる。

int i = 2;

int main(){
    static int i = 3;
    return i; //3
}

複合リテラルを実装

複合リテラルは変数名が指定されていない変数と考えることができる。名前をユニークな値にして新しい変数を定義すればよい。
コードがpostfixに入ってるのが意外だった。
scope->next ==NULLでローカル変数化グローバル変数化を判断している。この条件式はenter_scope関数が呼ばれると(関数のparseに入ると)falseになるのでこれで判断できる。
ND_COMMAを実装したおかげでローカルの複合リテラルだった場合の処理が簡単になるなと思った。

returnが値を取らなくてもよくする。

static global variableを実装

関数の時と同様に.globalの代わりに.localを使うようにしてファイルスコープにするだけ。
new_gvar関数でis_staticをtrueにしているのは恐らく文字列リテラルと複合リテラル(グローバル)をファイルスコープにするため。

r1ru

10/2

do whileを追加

stmtの中にはbreakやcontinueが来れるるので名前を生成する。

"do" stmt "while" "(" expr ")" ";"

stackを16byte境界にそろえる。

関数のプロローグ部分でスタックフレームを確保する際は16byteにアラインメントしている。現状このコンパイラは計算過程をスタックに保存しながら計算するスタックマシンであるのでpushやpopによりスタックが16byte境界にならない可能性がある。pushやpopは8byteで行っているのでスタックの境界が揃う->揃わないが繰り返すことになる。chibiccではdepth変数を追加してpushを実行した際に1加算、popを実行した際に1減算している。関数呼び出しの際にスタックを16byteにアラインメントするときはdepth変数が偶数になっているかをチェックして、なっていなければ8を引いている。

Handle a function returning bool, char or short

typecastを実装した際に、戻り値の型をcastする機能も実装したのでこれをやる必要性が最初は分からなかったが、これは関数を使う側から見えるデータを調整するためにあると考えられる。chibiccのテストケースであるように、例えば以下のような関数があったとして

int false_fn() { return 512; }

別ファイルでは以下のように宣言、呼び出しがされていることを考える。

_Bool false_fn();
false_fn() // 返り値は?

return type conversionを実装したため、false_fnの中でreturnするときは型変換が入る。現状この関数を呼び出した際はこの値がそのまま帰るので返り値は512になる。しかし別ファイルではfalse_fnは_Boolを返すことが期待されている。そのため、別ファイルからfalse_fnを呼び出したとき、呼び出し側から見えるデータを下位8bitに制限する。

つまりこの機能は関数が返す型と関数を使う側が期待する型が異なる場合、もっと言えば関数が返す型のサイズよりも関数を使う側が期待する型のサイズが小さい場合に必要な機能なのか？
→そんなことを許していいのだろうかという疑問が残る。
→これはABIでしっかり定義されているらしい。

Allow to call a variadic function

可変長引数は今までも使っていたので(printf)呼べるようにするというよりは、可変引数関数の定義を読めるようにするという方が近い。実装はgccに丸投げしている。(test/commonはgccでコンパイル&リンクされるので)
"..."は、最後の引数にしかとれない。

va_startを追加

va_startを追加するというよりも、va_startの処理内容を実装するという方が近い。
可変長引数の関数は、渡された引数の数の情報を持っていない。だからn番目の引数にアクセスできるようにしておく必要がある。そのためにレジスタ(整数レジスタ6つと浮動小数点レジスタ8つ)のコピーとスタックで渡されている引数へのポインタを保持しておく。これでn番目のnが指定されればアクセスできるようになる。このnは...の中でのnということに注意。というもの以下の例でprintfの1番目の引数は"%d"だが、最初にva_argを読んだときに返されるのは1。このために、...の前にある引数の合計サイズを構造体メンバに持っている。(chibiccのコードのgp * 8)

printf("%d", 1)

va_startの第二引数には...の直前の識別子を渡すことになっている。この情報を使えば...の前の引数の合計サイズが計算できる。
is_variadicだったらその前に指定されている引数を生成した後に__va_area__というローカル変数(136byte)を作成する。136byteはレジスタ保存用の領域(8 * 14byte) + __va_elem構造体用の領域(24byte)。
現状浮動小数点演算をサポートしていないのでfp_offsetは常に0。現状引数は6つまでしか許していないのでoverflow_arg_areaはセットしない。reg_save_areaのみセットする。mov命令でrbpのアドレスを書き込んだ後に、offsetを足している。offsetの計算とメモリアドレスへの書き込みを同時にはできないため。
gp_offsetのgpはgeneral_purposeの略。fpはたぶんfloating pointeの略。

引数の数をチェック

func()のように引数が何も指定されていないときはチェックしないのでis_variadicをtrueにする。
→引数が何も指定されていない関数の中から渡された引数にアクセスすることってできるのだろうか。この実装だと__va_area__が作られるのでいけるけど...
funcall関数に変更を加え、引数の数が多いときと少ないときはエラーにする。

signed keywordを追加

declspecに変更を加える。他のkeywordとは異なりsignedはbit orが用いられている。これは以下のようにsignedを複数指定することができるためだと思ったが、signed signedはgccではエラーになってた。

signed signed int x;

LONG + LONG + INTとSIGNED + INTが同じ値になってしまったのでenumにOTHREも追加したga,
これを追加する意味が良く分からない。struct,union.enum,typedefされた型の時はcontinueではなく即座位にreturnするべきだと思うのだが。(というわけで追加しただけで使ってない。)

r1ru

10/3

unsigned を追加

符号の有無で変える必要があるのは以下

キャスト時に使う命令(singed: movsx, unsigned: movzx)
<と<=の時に使う命令(signed: setl, setle unsigned: setb, setbe)
右シフトの時に使う命令(signed; sar, unsigned: shr)
sarは算術シフト(上位bitがそのまま)、shrは論理シフト(上位bitは0埋め)
除算の時に使う命令
除算の時はオペランドのサイズに合わせてレジスタ幅を拡張する必要があるが以下のようにcqoやcdqは符号拡張。オペランドが符号なし整数の場合は上位bitは0にする。

get_common_typeの以下の部分が分からなかった。binary operatorの右辺の型がunsignedだとunsignedに揃えられる。仕様にあるのだろうか。

if(ty2 -> is_unsigned)
    return ty2;

U,LLL suffixを追加

これらは定数につけるもの。Uならunsigned,LならLONGとして扱う。これはtokenizerで処理する。
strncasecmpは大文字小文字の区別なしで比較するためのもの。10進数かどうかで処理を分けている理由が分からなかった。仕様にあるのだろうか。
現状、負の数はneg命令で補数を求めることによって実現している。なので定数値を読むときは、それがunsignedだと考えて良い。最初chibiccの以下の部分で31になっている理由が分からなかった。32を指定して33bit目が立っているかで判断すればよいと思ったからだ。しかしこれで合っている。もし読んでいる定数の値が負で、32bit目が立っていればneg命令を実行した時に33bitになる可能性がある。(全部1の場合)これは33bit目が立っているかでは判断できない。

ty = (val >> 31) ? ty_long : ty_int;

以下のコードも同様。64bit目が立っているということは(unsingedであることを思い出せば)この値はty_longでは表現できない。だからty_ulongになっている。

else if (l)
      ty = (val >> 63) ? ty_ulong : ty_long;

ulongを用いる

符号ありの値になりえないところではulongを使うようにする。(sizeofの式の値や_Alignofの値等)
pointerを引き算した結果の式の型はlongにする。

r1ru

10/4

pointerをunsignedにする

const-exprでunsignedを扱う

const,vlatile,auto,register,restrict,_Noreturnを無視

http://seclan.dll.jp/c99d/c99d07.htm

autoとregisterは記憶域指定クラス。前者は変数をスタックに(デフォルトなので省略されることがほとんど)、後者は変数へのアクセスが高速であってほしい(レジスタに割り当ててほしい)とコンパイラに伝えるために使う。必ず割り当てられるわけではない。
const,restrictとvolatileは型修飾子。constが指定された変数は初期化式以外で書き換えが不可になり、必ず初期化式を与える必要がある。書き変えようとするとコンパイルエラーになる。restrictはポインタに着けるものでコンパイラの最適化を促進するためのもの。ポインタが指す先を同一関数、同一ブロック内の別のポインタが指さないことをコンパイラに伝える。(計算途中に値が書き変わらないことを保証するイメージか?)volatileはコンパイラの最適化を抑制するためにある。並列プログラミング時等に使用する。
_Noreturnは関数が戻らないことをコンパイラに伝える。(これでどんな最適化ができるのかは分からない。)

array-dementionの中にstaticとrestrictを書けるようにする。

これは関数のプロトタイプ宣言でしか書けないみたい。static nを指定した場合は関数呼び出しじに渡される配列は最適でもnこの要素を持たなければならない。restrictは良く分からん。

関数宣言の時に変数名をスキップする。

name_posはエラー出力用。変数名を省略できるのは関数宣言時のみなのでそれ以外の場合にエラー🅆お吐くために使用する。(declaratorはいろんなところで使用されるため)
Objに追加しているtokは目的がよく分からなかった。
struct_membersはいいのだろうかという疑問がある。

r1ru

10/7

floating point literalを実装

浮動小数点型にはfoat(4byte)とdouble(8byte)がある。
read_int_literalのエラー文が消されているのは以下のような入力が考えられるため。

3e + 8

eは指数を表すためのものだが、16進数の数値と解釈されてしまう。

codegenで、TY_FLOATかTY_DOUBLEの時も、普通にmov raxではだめなのか。(普通の整数リテラルはサイズに関わらずmov raxなので。)
→現状数値を使っていないので演算を実装したら試してみよう。
unionを定義してfloatの時はu32,doubleの時はu64を使っているのが気になる。これをやる必要はあるのか？
→ mov rax, 0.3みたいには書けないからかな？浮動所数点のbit patternをとりあえずfloatなら32bit,doubleなら64bitの整数値として解釈しているみたいな感じ?
caseの中にcaseがあるけど、rerurneを使って関数の最後にジャンプしている。breakだとうまくいかない。

float doubleの変数とキャストをサポート

浮動小数点の値の格納にはxmmレジスタを用いる。
浮動小数点型はデータの形式が整数レジスタとは大きく異なるので変換には専用の命令が用意されている。

整数型 → 浮動小数点型

面倒なのはu64→f64の変換。

どうやらこれは浮動小数点に変換する際に数値を丸める方向を正しいものにするために必要なコードっぽい。調べたけど詳細までは理解できなかった。
shrが使われているのにclがセットされていないのが気になる。
test rax, raxをすると、highest bitが1の時にSF=1になるので後ろのj 1f;でラベル1に飛ぶ。
数値ラベルの場合にsuffixとして'f'や'b'を付けるのはGNU拡張。f(forward)だと参照後に定義された一番近いラベル、b(backward)だと参照前に定義された一番近いラベルにジャンプする。