GCCに手を加えてC言語で累乗の演算子を使えるようにしてみた

大学の講義の一環としてオープソースソフトウェアをデバッグしその動作を追うという流れを体験しました。私達の班ではC言語等のコンパイラであるGCC(GNU Compiler Collection)を対象とし、最終的にC言語で累乗の演算子を使えるように修正を加えることができました（とても限定的な状況に限りますが…）。

この記事ではGCCをソースコードからコンパイルする方法に始まり機能を追加するまでの流れを書いていきます。

環境

Ubuntu16.04.5 gcc-8.2.0 Emacs24.5.1 gdb7.11.1

動機

累乗を計算する機会は多く、Python等では演算子として言語レベルでサポートされています。C言語でもmath.h等のpow関数を使えば計算することができますが、利便性のために演算子として実装したいと考えました。

仕様

今回追加した仕様は以下2点です。 - プリプロセスの部分で+%を組み込み関数__builtin_powi()に書き換えることで、累乗の演算として扱う - オペランドが定数のときのみ、->*を組み込み関数__builtin_pow()を用いて累乗の演算として扱う

以上のように機能を限定して行っています。この事情はあとで詳しく書きますが、コンパイラ特有の問題や複雑で低級な処理の部分の多さによるものです。

ビルド

ダウンロード

以下のサイトからダウンロードしてきました。 gcc-8.2.0をミラーしたものはいくつもあり、今回はそのうちの一つを利用しています。 http://ftp.tsukuba.wide.ad.jp/software/gcc/releases/gcc-8.2.0/

コンパイル及びインストール

基本的な手順は、以下のサイトを参考にしました。
https://qiita.com/liveralmask/items/6ed4a98ebb3bf6b7f707
ただし、のちのちのためにconfigureのオプションを少し変える必要があります。

''' ../configure CFLAGS="-g -O0" CXXFLAGS="-g -O0" --enable-languages=c --prefix=/home/denjo/mygcc_constant --disable-multilib ''' CFLAGSとCXXFLAGに-O0をつけることで、最適化されずgdbでコードを上から順に追うことができるようになります。ただしこれをつけてもMakefileに何か所か-O2の部分が残っているので、ここも-O0にしておいた方がいいでしょう。

gdbによる調査

今回はデバッグツールとしてgdb及びEmacsを用いました。

gccの中を進む

コマンドラインで/gcc/bin/に移動しEmacsを起動し、M-X gud-gdb gccと入力することでgdbでgccを追うことができます。 gdbではrコマンドでプログラムを実行できます。ここで r test.c などとすれば、対象のプログラム（gcc)に引数を渡すことができます。

以下のデバッグでは、関心のある処理がどこで行われているか探るためにエラーメッセージを利用しました。例えば、あえて構文エラーを含むファイルをコンパイルさせることでエラーが出たか否かによって構文解析の部分を通りすぎたかどうか把握できるわけです。例えば、以下のような1単語だけ書いたtest.cファイルを用いることにします。 ''' hello '''

gccを実行した際に呼ばれる関数を順に追っていくとpex_unix_exec_childと言う関数にたどり着きます。

->driver::main
->driver::do_spec_on_infiles
->do_spec
->execute
->pex_run
->pex_run_in_environment
->pex_unix_exec_child

この関数内ではvfork(子プロセスを生成する関数)が呼ばれていて、この関数以降は子プロセスでコンパイルの大部分が行われるようになっています。そのため、Emacs上でgdbを用いたデバッグをする際には set follow-fork-mode child のオプションをつけると子プロセスを自動で追うことができます。vscodeでは自動で子プロセスを追う設定がNode.jsしか対応していないので、工夫して動作を追う必要があるようです(後述)。

vforkの呼び出し以降はc-parser.c、lex.cという、字句解析を担っていることが予想されるファイル内の関数が呼び出されています。lex.c内では演算子の場合分けが行われていて、それぞれの演算子の意味に対応した属性が割り振られます(例えば加算を意味するCPP_PLUSなど)。この箇所に既存の機能を持った演算子を追加することは比較的容易で、既存の演算子と被らないように条件分岐の式を追加すれば良いだけです。

例えば以下のコードはlex.cの3049行目~3055行目ですがその条件分岐を書き換えることによってインクリメントを++だけでなく+-という新しい演算子によって行うことができるようになります。

3049 case '+':
3050      result->type = CPP_PLUS;
3051      if (*buffer->cur == '+')
3052        buffer->cur++, result->type = CPP_PLUS_PLUS;
3053      else if (*buffer->cur == '=')
3054        buffer->cur++, result->type = CPP_PLUS_EQ;
3055      break;

//これを以下のように書き換える

3049 case '+':
3050      result->type = CPP_PLUS;
3051      if (*buffer->cur == '+' || *buffer->cur == '-')
3052        buffer->cur++, result->type = CPP_PLUS_PLUS;
3053      else if (*buffer->cur == '=')
3054        buffer->cur++, result->type = CPP_PLUS_EQ;
3055      break;

注意しなければならないのがこの箇所の書き換えのみでは既存の演算子の上書きはできないということです。 cコンパイラはgccの他の部分のコンパイルも担っているため、既存の演算子によって書かれたコードがコンパイルエラーを起こすことが原因です。また、新たな機能を持った演算子の追加もここではできません。と言うのはここではパースしたトークンにすでに定義された属性を割り振っているだけであり、新しい属性の定義は行なっていないからです。

このようにgcc全体では複雑な依存関係があり、これらの依存関係を解消することは難しいです。そのため、まずは環境を制限してコンパイラを書き換えることを考えます。

前述したようにgccはコンパイラ全体の統括であり、コンパイルの主要な部分は子プロセスが行なっています。その子プロセスの一つとcc1呼ばれるものがあり、cコンパイラと言う名称通りこのプロセスがプリプロセスやコンパイルを行なっていることがわかりました。

cc1とは

コンパイルは以下のような4つの操作から成ります。そしてそれぞれの操作を行う実行ファイルがあり、gccを実行するとそれらを適切な順に呼び出すという形になっているのです。そのため普段私たちは、これらの分割された操作を意識せずコンパイルができます。今回見る必要があるのは狭義のコンパイルの部分であり、そのため今後は cc1 の中に限定して触ることとなります。

プリプロセス .cファイルを.iファイルに書き換えるもので、実行ファイルcc1が担っています。
狭義のコンパイル .iファイルを.sファイルに書き換えるもので、実行ファイルcc1が担っています。いわゆる字句解析や構文解析をするのがこの部分です。
アセンブリ .sファイルを.oファイルに書き換えるもので、実行ファイルasが担っています。
リンク .oファイルを.outファイルに書き換えるもので、実行ファイルcollect2が担っています。

cc1の中を進む

前述したようにcc1はgccで呼び出される子プロセスの一つであるため、cc1を実行しデバッガで追うと直接toplev.cにたどり着きます。そのため、vscode等でgccから子プロセスが追えない場合でもcc1から追うことでコンパイラの主要な動作がわかります。コンパイラを書き換える際の方針として、なるべく依存関係が複雑でないような箇所を書き換えると言うことであったのでコールスタックの上の層で書き換えられる箇所を検討すると、scan_translation_unitと言う関数が見つかります。

->main 
->toplev::main 
->do_compile 
->lang_dependent_init 
->lang_hooks.init -> c_objc_common_init 
->c_common_init 
->preprocess_file 
->scan_translation_unit

これはcc1にプリプロセスオプションを追加した際のみに呼び出される関数で、この関数によってファイルの中身を解析しtokenごとに.iファイルに出力しています。このtokenの出力の際にこちら側がマクロの展開のように新たな演算子を処理すれば良いのではないかと言うのが後述する方針1の内容です。

変更の方針

機能を限定せざるを得ない事情

ここからは実際にコードを書き換えてみるわけですが、気楽に書き換えさせてくれないコンパイラ特有の問題がいくつかありました。実際に書き換える部分とはあまり関連がありませんが、コンパイルの核となる部分で以降の書き換えの方針の決定に寄与するので先に軽く紹介しておきます。

gccのコンパイル方法による問題

少しコードを書き換えてみて判明した問題なのですが、makeでコンパイラをbuildした際、コンパイルして作られたcc1を後段の部分をコンパイルするためのコンパイラとして使いまわしているようです。というのも、例えばcc1の一部分を書き換えてmakeしなおすと全く関係ないアセンブリなどの低級な部分でエラーが出るのです。
この問題はcc1のみでmakeすることにより一応解決できます。そのため、既存の動作を保証しないような書き換えを施す際にはcc1のみでコンパイルすることとなりました。なおcc1のみでコンパイルした際の問題点として、includeができないというものが挙げられます。そのためこの場合、stdio.hを必要とするprintf関数が使えないなど機能はかなり限定されてしまいます。

構文木を組むことの複雑さ

コンパイラの根本的な部分を書き換えるとなると、字句解析から構文解析に至るまでの流れに手を加えることとなるでしょう。しかしgccの構文木は、以下のような複雑さを孕んでいました。 - 言語非依存な表現への変換 gccはC++やgo言語も担っているので、それらをカバーするため早い段階で言語非依存な処理に書き換えられています。C++やgoでは言語特有の演算子がありこれに対する処理を追ってみると高級な部分で低級な演算子に変換されているのですが、C言語ではそのような演算子がないため、かなり早い段階で低級な部分に処理が落とし込まれていました。
さらに最適化のための処理が随所になされており、コンパイラとして非常にgccが優れているであろうことが垣間見えた一方、非常に後付けでは書き換えにくいものとなっていました。

構文木の複雑さ構文木ではそれぞれのtokenが末端の葉ではなく、さらにその内部に大きな木があります。構文木の中身を見る際、以下のサイトを参考にさせていただきながら手探っていきましたが、これを見ていただくと簡潔なコードでも大きな木が作られることが分かるかと思います。
https://qiita.com/eggman/items/2a98c9c901290bfde703
ここに演算子や関数を足していくとなると、さらに複雑な木構造となっていました。

累乗の組み込み関数

C言語で累乗の計算をするとき、基本的にはmathライブラリのpow()関数を使うかと思います。しかし、gccにはもともとbuiltin_powという組み込み関数が存在します。この関数であればmathライブラリよりも精度は落ちるもののgcc内で累乗の関数を呼び出すことができます。

プリプロセッサでの変更

上記の事情を踏まえて私たちが最初に考えたのは、プリプロセスの部分を変更するというものでした。既に述べた通りプリプロセスはコンパイルの前処理として行われるもので、この部分に手を加えてやれば好きなようにコードをいじれるという発想から生まれた方針でした。 gccやcc1の実行時に-Eオプションをつけることで、.cファイルに対してプリプロセスのみが実行され.iファイルが出力されます。これを利用し我々はプリプロセスの実行部分をgdbで追いかけ、行き着いた先の関数gcc/c-family/c-ppoutput.c:scan_translation_unitでコードを書き換えました。幸いにもこの部分が字句解析のための関数を呼び出しファイルをtokenに分割していたので、そのtokenを出力する前にチェックして適切に書き換えるという処理を行いました。今回は、演算子+%を見つけたら上記の組み込み関数__builtin_powiに書き換えるという方針を取ることにします。
具体的な処理は以下です。まず関数の先頭で専用の変数を定義しておきます。

int flag = 0;
unsigned char op1[100];

そして当該ファイルの278行目、tokenを取得したあとに出力する部分はこのようになっています。

cpp_output_token (token, print.outf);
line_marker_emitted = false;
print.printed = true;

ここを以下のように書き換えます。第一のオペランド、+、%、第二のオペランド、tokenを受け取るごとに変数flagの値がインクリメントされていきます。そして当該の演算子を見つけたときは__builtin_powi関数を使うような出力を出しています。

if (flag == 1) {
    if (token->type == CPP_PLUS) {
        flag = 2;
    } else {
        fprintf(print.outf, "%s ", op1);
        flag = 0;
    }
} else if (flag == 2) {
    if (token->type == CPP_MOD) {
        fprintf(print.outf, "__builtin_powi(%s,", op1);
        flag = 3;
    } else {
        fprintf(print.outf, "%s + ", op1);
        flag = 0;
    }
} else if (flag == 3) {
    flag = 4;
}

if (flag != 4 && (token->type == CPP_NAME || token->type == CPP_NUMBER)) {
    unsigned char* maybe_powi_op1;
    if (token->type == CPP_NAME) {
        maybe_powi_op1 = (unsigned char*)(token->val.node.node->ident.str);
    } else {
        maybe_powi_op1 = (unsigned char*)(token->val.str.text);
    }
    int i = 0;
    while (maybe_powi_op1[i] != '\0') {
        op1[i] = maybe_powi_op1[i];
        i++;
    }
    op1[i] = '\0';
    flag = 1;
} else if (flag == 0 || flag == 4) {
    cpp_output_token (token, print.outf);
    line_marker_emitted = false;
    print.printed = true;
}
        
if (flag == 4) {
    fprintf(print.outf, ")");
    flag = 0;
}

しかしこの方針では、いくつかの重大な欠陥があります。 - プリプロセスでファイルを書き換えるのは邪道そもそもの問題ではありますが、プリプロセスは本来マクロなどの処理をするのが目的であり、コードのその他の部分は中身を見るだけ見て受け流しているに過ぎません。それにも関わらずこの部分に+%演算子を追加するためだけのコードを無理やり挟むのは、演算子を追加できたと言うには程遠いでしょう。 - 変数や数字しかオペランドに取れないこれはプリプロセスでファイルを書き換えているがゆえに起こる問題です。プリプロセスはtokenを取得していますが構文解析しているわけではなく、したがってここではオペランドは高々1単語にしかなり得ません。より具体的には、括弧に囲まれた式や関数などをオペランドに指定するとこのコードは成り立たなくなるのです。 - -Eオプションをつけないとこの変更が反映されない先ほど-Eオプションをつけるとプリプロセスのみが実行されると述べましたが、このオプションをつけないとプリプロセスに含まれる作業が狭義のコンパイルと同時並行で行われるようです。今回変更した部分はプリプロセスのみを明示的に実行する場合に反映される場所であり、-Eをつけて一旦.iファイルを出力しなければこの部分の処理はされないということが書き換えたあとに判明しました。 - cc1でしかビルドができないプリプロセスの部分を触っただけで、gcc全体でビルドするとアセンブラの部分でエラーが出るようになります。そのためcc1のみでビルドする必要がありました。

定数に限定しての変更

2つ目は演算子のオペランドが定数である場合に動作を限定するという方針です。

cc1でのコンパイル時に以下のオプションを付与するとソースファイルがどのようなフェーズを経てコンパイルされているのかを確認することができます。このオプションにより出力されたファイルは番号が大きいほどコンパイルが進んだ段階であることを意味します。

-fdump-tree-all

さて、 int a = 2*3; のように定数同士の演算を含むソースファイルを上記のオプションをつけてコンパイルし、生成されたファイルのうち最も初期のもの（003t.originalのような名前です)を見てみると、int a = 6;のように定数が計算結果に置き換わっていることが確認できます。このことから定数同士の演算は構文解析の非常に早い段階で既に実行されていることがわかります。方針2ではこの仕様を参考にして、定数だけを相手にすることで早い段階で累乗の演算を実行してしまうことにします。

定数を操作するために、構文木の定数に関するノードがどのように生成されているのかを確認します。再掲しますが、int a = 2*3;のように定数を含むソースファイルをコンパイルし、Emacsおよびgdbで根気よくデバッグすることで定数に関する処理を見つけます。上述の_cpp_lex_direct以下でステップインを繰り返すとlibcpp/c-parser.c:lex_numberという関数を見つけることができます。この関数の戻り値numberは number->len, number->textを要素に持つ構造体です。この構造体をgdbでprintしてみると、定数が文字列として格納されていることが確認できます。

lex_numberの呼び出し元を眺めると戻り値に含まれる文字列を数値型に変換し、それから数値型のtokenを生成していることが分かります。このtokenには字句解析された結果の定数値が含まれるはずですが、実際にこれをprintしてみると、非常に複雑な構造であり期待されるような数値にアクセスすることは難しそうです。以上より累乗を適用して数値を編集する箇所としてlex_numberを選びます。これはtokenの編集に比べて文字列の編集はずっと難易度が低いためです。

lex_numberを修正して累乗が適用されるようにします。~もちろんこの段階で計算することは本来のGCCの仕様から見ると邪道ですが…~(←打ち消し線出来てない？)方針2では後述の理由により累乗の演算子として

->*

を割り当てます。つまりint a = 2->*3;といった構文を受理するようにしていきます。lex_number中のpfile->buffer->curに現在字句解析している位置が格納されています。そこでこのポインタを進めることで次に累乗の演算子が来ているかどうか確認します。次が累乗ならばさらにポインタを進め、そのままlex_numberを呼び出します。これにより演算子の右のオペランドを文字列として取得することが出来ます。文字列を既存の関数で数値に変換し累乗の組込関数である__builtin_powを適用し、最後に計算結果を文字列としてnumberに格納すれば演算が適用されたことになります。

const uchar* cur_saved = cur;

while (*(cur)==' ') cur++;//avoid white space

if(*(cur)=='-'&&*(cur+1)=='>'&&＊(cur+2)=='＊'){
    cur += 3;
    while (*(cur)==' ') cur++;//avoid white space
    pfile->buffer->cur = cur+1;

    struct normalize_state nst = INITIAL_NORMALIZE_STATE;
    cpp_string rhs_str;
    lex_number(pfile, &rhs_str, &nst);

    double lhs = atof((char*)dest);
    double rhs = atof((char*)rhs_str.text);

    double powered = __builtin_pow(lhs,rhs);
    dest = _cpp_unaligned_alloc(pfile,100);//大きめに確保しておく
    sprintf((char*)dest,"%lf",powered);
    char* dest_temp = (char*)dest;
    int powered_len = strlen(dest_temp);
    number->text = dest;
    number->len = powered_len;

    pfile->buffer->cur = cur_saved;
}

以上の処理により累乗の演算子については左のオペランドが字句解析された時点で演算が実行されます。したがって演算子自体と右のオペランドについての構文解析はスキップする必要があります。そこで、lex_numberよりかなり上位の層にtokenを読み飛ばす処理を加えます。

ここで一旦プリプロセッサを顧みます。GCCはC言語以外にもC++やgoなどいくつかの言語をコンパイルすることができますが、プリプロセスはコンパイラ依存であるため、プリプロセッサとしては言語非依存な構造になっているのではないかと考えられます。実際にプリプロセッサが字句解析を行う関数libcpp/lex.c:_cpp_lex_directの3056行目付近を見てみるとC++にあってC言語にない演算子の1つであるCPP_DEREF_STAR->*が扱われているように、C言語にない演算子にも名前が割り当てられていることが分かります。そこで今回は上記のCPP_DEREF_STARをC言語のプリプロセス中にも受理できるようにすることで、擬似的に累乗の演算子を追加します。具体的にはlex.cの3062行目付近が以下のようになっているのを書き換えます。

case '-':
    result->type = CPP_MINUS;
    if (*buffer->cur == '>')
    {
        buffer->cur++;
        result->type = CPP_DEREF;
        if (＊buffer->cur == '＊' && CPP_OPTION (pfile, cplusplus))
        buffer->cur++, result->type = CPP_DEREF_STAR;
    }
    else if (*buffer->cur == '-')
        buffer->cur++, result->type = CPP_MINUS_MINUS;
    else if (*buffer->cur == '=')
        buffer->cur++, result->type = CPP_MINUS_EQ;
    break;

ここを以下のようにすることでC言語でも受理できるようになります。

case '-':
    result->type = CPP_MINUS;
    if (*buffer->cur == '>')
    {
        buffer->cur++;
        result->type = CPP_DEREF;
        if (＊buffer->cur == '＊')
        buffer->cur++, result->type = CPP_DEREF_STAR;
    }
    else if (*buffer->cur == '-')
        buffer->cur++, result->type = CPP_MINUS_MINUS;
    else if (*buffer->cur == '=')
        buffer->cur++, result->type = CPP_MINUS_EQ;
    break;

以上の修正だけでは累乗を含むソースファイルをコンパイルした時に構文エラーが生じます。それは演算子->*が読み飛ばされていないためです。そこで最後の修正として、tokenを適切に読み飛ばす部分を追記します。これはlex_numberより上位の関数である必要があり、今回はgcc/c/c-parser.c:c_parser_binary_expressionとします。この関数は読み込まれた演算子が二項演算子であるか判定するものです。switch文にCPP_DEREF_STARのcaseを加え、読み込み済みのtokenを消費する関数c_parser_consume_tokenを呼ぶことで累乗の演算子を読み飛ばせます。さらに演算子の右のオペランドを読み飛ばす処理を追加することで、lex_numberでの修正とつじつまが合います。

case CPP_DEREF_STAR:
  if(c_parser_peek_2nd_token(parser)->type==CPP_NUMBER){
    c_parser_consume_token(parser);
    c_parser_consume_token(parser);
  }
  goto out;

この方法によって定数に関する累乗の演算子を

int a = 2->*3;

のように使用することができるようになります。

1つ目の方針に比べると幾分か自然な変更にはなっているかと思います。ただし欠点としては、 - 定数以外には適用できないこと - 関数やネスト（丸括弧）に対応できないこと

が挙げられます。

実験結果

方針1

cc1のみで実行するため、ビルドで作られたディレクトリから以下に移動します。

libexec/gcc/x86_64-pc-linux-gnu/8.2.0

ここでまずは以下のようなファイルtest.cを作ります。

int square(int a) {
 return a+%2;
}

int main() {
 int a = 1+1;
 int b = 2;
 a = a+%b;
 a = square(a);
 return a;
}

そしてこれを以下のようにプリプロセスしリダイレクトします。

$ ./cc1 -E test.c > test.i

すると以下のようなtest.iが作られます。なお、ファイルの冒頭にあるのはデフォルトで出力されるものです。空白文字に関しては元々の処理に埋め込まれている部分があるためj制御しようとすると少し手間となりますが、その代わりに演算子の前後に空白があろうとなかろうと元々の処理が勝手に読み飛ばしてくれます。

# 1 "test.c"
# 1 "<組み込み>"
# 1 "<コマンドライン>"
# 31 "<コマンドライン>"
# 1 "/usr/include/stdc-predef.h" 1 3 4
# 32 "<コマンドライン>" 2
# 1 "test.c"
int square ( int a ) {
  return __builtin_powi(a,2);
}

int main () {
  int  a = 1 + 1 ;
  int  b = 2 ;
  a = __builtin_powi(a,b);
  a = square (a );
  return a ;
}

ここでデフォルトのgccでtest.iをコンパイルし、main関数の返り値を表示します。

$ gcc test.i
$ ./a.out
$ echo $?
16

これによりa=16となっていることが確かめられました。

方針2

こちらはgcc全体でコンパイルできるので、ディレクトリbinに移動します。ここで以下のファイルをコンパイルして実行します。

#include <stdio.h>

int main() {
    int a  2->*3;
    double b = 2 ->* 0.5;
    printf("a=%d, b=%lf\n", a, b);
    return 0;
}

実行結果は以下のようになります。整数でも少数でも、また演算子の前後の空白に関係なく実行できていることが分かるかと思います。

$ ./gcc test.c
$ ./a.out
a=8, b=1.414214

ソース

プロジェクトのページは以下です。
https://doss-gitlab.eidos.ic.i.u-tokyo.ac.jp/segfault/cnull

また今回、2つの方針で一方はcc1でしかコンパイルできずもう一方はgcc全体でコンパイルできるため、それぞれ別のブランチのまま変更を保存しています。
方針1の変更を保存したブランチは以下です。
https://doss-gitlab.eidos.ic.i.u-tokyo.ac.jp/segfault/cnull/tree/hati

方針2の変更を保存したブランチは以下です。
https://doss-gitlab.eidos.ic.i.u-tokyo.ac.jp/segfault/cnull/tree/constant

参考文献

https://qiita.com/liveralmask/items/6ed4a98ebb3bf6b7f707
http://www.delorie.com/gnu/docs/gcc/gccint_31.html
http://www.cr.ie.u-ryukyu.ac.jp/slides/OSC2018/slide.html
https://www.cse.iitb.ac.in/grc/slides/pldi14tut-gcc/4-gcc-pldi14-control-flow.pdf
https://qiita.com/eggman/items/2a98c9c901290bfde703

doss-segfaultのブログ

GCCに手を加えてみた