ぱたへね

はてなダイアリーはrustの色分けができないのでこっちに来た

低レイヤを知りたい人のためのCコンパイラ作成入門の多次元配列

compiler

低レイヤを知りたい人のためのCコンパイラ作成入門を、Rustでコツコツとやっている。

www.sigbus.info

今まで苦労しながらもgithubのソースを見ながらまっすぐに来れたが、二次元配列の所で躓いたので整理してみた。

動かしたいソース

まだここまでは動かないけど、やりたいことはこのCソースの演算部分を動かす事。二次元配列の宣言と、ポインターへの変換、デリファレンス。 流石にCの動きが分からないと言うことはないが、ちゃんと動くアセンブラを自力で出力するのには難しい。

#include <stdio.h>

int main() {
    int x [2][3];
    int *y = x;
    int i;
    int z;
    
    for(i = 0;i<6;i++) {
        *(y+i) = i;
    }
    
    z = *(*(x+0)+1);
    printf(" *(*(x+0)+1 = %d\n", z); // 1

    z = *(*(x+1)+1);
    printf(" *(*(x+1)+1 = %d\n", z); // 4
    
    z = *(*(x+1)+2);
    printf(" *(*(x+1)+2 = %d\n", z); // 5

    return 0;
}

z = *(*(x+1)+2);

が動くようになると、x[1][2]をこの形に変換することで、配列にindexでアクセスできるはず。

コンパイラの実装部分

ここの実装を参考にしている。 https://github.com/rui314/chibicc/blob/3ce1b2d067164f754dcb4216c193dc98e164b3ce/chibicc.h

型情報を持つ構造体で関係のあるメンバー変数はこれ。array_lenは長いので以下lenで。

Type kind
int size
Type *base
int arrey_len

Type kindに設定できる値はここ。今回使うのは、TY_INT、TY_PTR、TY_ARRAYの3つ。

typedef enum {
  TY_INT,
  TY_PTR,
  TY_FUNC,
  TY_ARRAY,
} TypeKind;

INT型へのポインターを図でかくとこうなります。。ポインター自体の型はTY_PTRになって、baseがINTを指す。sizeは変数の大きさが入っていて、ポインターもintも8バイト。

二次元配列の型

最初にCソースで宣言している二次元配列の型を考える。

 int x [2][3];

同じように図で書くとこうなります。

二重配列なのでTY_ARRAYが二つ続く。sizeはsizeofで返ってくる値。一番右がINTで8、真ん中がINTが3つで24、x自体はsize=24の要素が2つなので48になります。

ポインターへの代入

ややこしいのはこの操作。

 int *y = x;

配列をポインターに代入するとき、デリファレンスではなく配列の先頭を示すポインターになります。関数の引数に配列を持ってきた時も同じ動きをします。

元の配列の情報がすっぽり抜けてINTへのポインターになる。コンパイラとしては、何重配列であろがbaseのポインターを最後までたぐって型を見つけないといけない。

yに整数を加算するときは、ポインターが指している型のサイズ分増やす。

 *(y+i) = i;

この例だと、i * 8 のNodeを作ってyに加算する。ASTは (+ y (* i 8)) を作ってアセンブラにする。

xへの加算

一番内側のx+1

*(*(x+1)+1)

xの型がこうなので1を足すとアドレスとしては24増える。24は配列xの要素1つの大きさ。baseをたぐっても良いし48/2でも良い。ASTは(+ x (* 1 24))。 x[i][j]のiの部分に相当する。

一回目のデリファレンス

次に、x+1のデリファレンスを行う。

*(x+1)

元々あった二重配列の一番左が取れてこうなります。

これに1を加えると、配列の1要素の大きさ8だけ増える。x[i][j]のjの部分に相当する。

*(x+1)+1

二回目のデリファレンス

最後二回目のデリファレンスを行って値を操作する。この式の一番外側です。

*(*(x+1)+1)

元々の二重配列を一回デリファレンスしたのがこの型です。

もう一度デリファレンスを行うことで、左の配列が取れてINT型になる。これはINTなので1を足す場合は素直に1を足すコードを出せばOK

整理できた。途中経過はここ。最後までいけるかな。

https://github.com/natsutan/r9cc