cucu: a compiler u can understand (part 3)

6136 ワード
コンパイラのバックエンドアーキテクチャについてお話しします.C言語は移植可能な言語であるべきであるが,移植の過程で,新しいCPUアーキテクチャのためにC全体のコンパイラを再記述する必要はない.コンパイラバックエンドは低レベルのバイトコードを生成するために使用され、コンパイラフロントエンドはコンパイラバックエンドの関数を呼び出します.優れたバックエンド設計により、コンパイラは移植性に優れます.
CUCUが移植可能なコンパイラ(いわゆるクロスコンパイル)になることを望んでいます.そのため、バックエンドコードを独立したモジュールに書くつもりです.
しかし、バックエンドコードを具体的に考慮する前に、まだ多くの仕事があります.
シンプルなCPUアーキテクチャ
我々がスライドしたCPUアーキテクチャには、2つのレジスタ(AとBと記す)と1つのスタックが含まれています.レジスタAはアキュムレータである.多くのRISCのCPUのように,定長命令セットを用い,より面白くするために命令を16進コードに変えるのではなく,比較的自然な方法で提示する.
私は簡単な方法で命令を設計します.各命令は8バイト長です(確かに、これは少し長いですが、関係ありません.結局、これは仮想的なアーキテクチャです).先頭の7バイトはASCIIのシンボルで、最後は0 x 10(')です.
これにより、A:=A+B、A:=1ef8、またはpush A。 （“ B A ”，“ 0x1ef8 A ” “ A ”）。などのより読みやすい命令を設計することができます.
  • A:=NNNN-0 xNNNNをレジスタAに入れる.
  • A:=m[A]-アドレスがレジスタAの値であるコンテンツ(バイトとして)をレジスタAの
    • に格納.
  • A:=M[A]-アドレスがレジスタAの値である内容(int型変数として)をレジスタAの
    • に格納.
  • m[B]:=A−レジスタAの値は、レジスタBが指すアドレス(バイトとして)に格納される.
  • M[B]:=A−レジスタAの値を、レジスタBが指すアドレス(int型変数として)に格納する.
  • push A-レジスタAの値をキャプテンに押し込む.
  • pop B-スタックトップ要素をスタックし、レジスタBに入れる.
  • A:=B+A-AとBの値を加算し、結果をAに入れる.
  • A:=B-A−BはAを減算し、結果をAに格納する.
  • A:=B&A-ビットアンド.
  • A:=B|A-ビット単位または.
  • A:=B!=A-若B!=Aは、Aが1である、そうでない場合Aは0である.
  • A:=B==A-B=Aの場合Aは1、そうでない場合Aは0
  • A:=B<<A-Bの値をAビット左にシフトし、結果をAに格納します.
  • A:=B>>A-Bの値をAビット右にシフトし、結果をAに格納します.
  • A:=B<A-B
  • popNNNN−スタック内のNNNN個の要素をスタックから取り出す.
  • sp@NNNN−スタック内のアドレスがNNNNである要素の値をレジスタAに入れる.
  • jmpNNNN−プログラムはNNNNアドレスにジャンプして実行を継続する.
  • jpzNNNN−Aの値が0であればNNNNにジャンプして実行する.
  • call A-呼び出しアドレスはAの関数に存在する.
  • ret-関数から
    • を返します.
    CUCUバックエンドアーキテクチャ設計
    「gen.c」というファイルが含まれている場合、実際にはバックエンドアーキテクチャの具体的な実装が含まれています.2つの最も基本的な関数から始めましょう:gen_start()とgen_finish().この2つの関数は、PEヘッダおよびELFヘッダなどのプログラムヘッダおよびいくつかの前処理されたバイトコードを生成するために使用される.
    コンパイラは、code[]配列にバイトコードを送信するために関数emit()を使用する.この配列の各要素は、使用可能なコンパイルされたプログラムを表しています.
    したがって、コンパイラはバックエンドアーキテクチャが提供する言い訳のみを呼び出し、エンドエンドアーキテクチャはemit()を呼び出して特定のバイトコードを生成します.これは、コンパイラがマシン言語をコンパイルするプロセスです.
    したがって、最も一般的なコマンドを定義し、バックエンドアーキテクチャを実装する必要があります.最も簡単なプログラムから始めましょう.
    int main() {
    return 0;
}

    関数呼び出しのプロセスを分析しましょう.このプロシージャは,関数パラメータが関数体にどのように伝達されるか,戻り値がどのように処理されるかのプロシージャである.前述したように、パラメータはスタックの上部に配置されて伝達される(最初のパラメータの最初のスタック).レジスタAには関数の戻り値が付いているという約束をしましょう.
    実際,レジスタAを用いてすべての値を格納し,レジスタBは一時変数のみを格納する.
    上記のプログラムについて、期待されるバイトコードは以下の形式であるべきである.
    A:=0000
ret

    したがって,即時数をレジスタAに格納するための関数と,戻りを処理するための関数が必要である.この2つの関数をgenとして定義します.const(int)とgen_ret().
    コンパイラがプライマリ式が即時数であることを発見したときgen_constが呼び出され、return文が見つかった場合gent_retが呼び出されます.ただし、一部の関数のタイプはvoidなので、明示的なReturnはありません.しかし、安全で簡単なために、各関数の最後にgenを呼び出します.ret()は、その前に明示的なreturnがあっても.
    私たちのコンパイラは最適化、効率、安全を追求していないので、このような二重returnの方法は私たちにとって実行できます.
    数学演算
    数学式をコンパイルしましょう.これらの数学式は似ているので、コンパイラがどのように処理されているかを説明するために例を使用します.文法分析器がどのように機能しているか覚えていますか.式の左値を分析し(より厳密にはコンパイル)、式の右値を演算子にします.
    これは典型的な数学式のコンパイルの過程です(象を冷蔵庫に入れた冗談を覚えていますか):
    ..    
push A
..    
pop B
A:=A+B

    左の値を計算した後、結果を一時的に保存する必要があります.スタックを使用するのは良い選択です.したがって、式1+2+3は次のようにコンパイルされます.
    A:=0001  -+     -+
push A    |      |
A:=0002   | 1+2  |
pop B     |      |
A:=A+B   -+      | +3
push A           |
A:=0003          |
pop B            |
A:=A+B       ----+

    他のもの
    シンボルの処理も同様に簡単です.
    関数を呼び出すには、まずそのアドレスをレジスタAに入れ、gen_を使用します.call()は、コードcall Aを生成する.
    ローカル変数にアクセスするにはgen_を使用します.stack_addrは、スタック内のこの変数のアドレスを返します.
    グローバル変数にアクセスするにはgen_を使用します.sym_addr().それ以外に、新しいシンボルコンパイラを確立するたびに、アセンブリコードなどのコードを生成する必要があります.gen_Symはこれらの状況を処理するために使用される.
    gen_popはスタックトップからN個の要素をポップアップし、スタックトップポインタを追加します.
    gen_unrefは、いくつかのポインタ関連動作を生成するために使用される.タイプによって(byteまたはint)、A:=m[A]or A:=M[A]コードが生成されます.
    gen_arrayは配列アドレスをスタックトップに押し込む.
    最後にif/while文に遭遇したときgen_patchはアドレスジャンプを生成するコードを追加するために使用される.なぜ追加と言うのですか?ジャンプが必要な文に遭遇したときにジャンプが必要なアドレスは未知であり、このアドレスはコンパイルされた文ブロックのサイズに依存するからです.したがって,文ブロックコンパイル終了後にアドレスジャンプを追加するコードが必要である.
    ほとんど成功するところではありません.以下のプログラムを試してみましょう.
    int main() {
    int k;
    k = 3;
    if (k == 0) {
        return 1;
    }
    return 0;
}

jmp0008 #  gen_start()  ，   main，   0x08
push A  #      K    
sp@0000 #             
push A  #        
A:=0003 #  3  A 
pop B   #        K   
M[B]:=A #  A     int  K 
sp@0000 #   K   
A:=M[A] #         int  A
push A  #     
A:=0000 #  A   0
pop B   #        K  
A:=B==A #   A B   (   "k"   0)
jmz0090 #     (A!=B, k!=0) -     to 0x90
A:=0001 #  1  A      
pop0001 #        k     
ret     # return
jmp0090 # else      ，        0x90
A:=0000 #  0  A      
    pop0001 #        k     
    ret     # return
ret     #             return

    私たちのコードは散らかっていて膨らんでいますが、確かに動作します.さらに重要なのは、コンパイラの動作原理を理解し、自分で自分のコンパイラを作ることができます.
    しかし、私はあなたに警告しなければなりません..
    警告
    以上の手順に従ってはいけません.独自のコンパイラを書く場合は、次の成熟したツールを使用することをお勧めします.
  • flex/lex/jlex/...
  • yacc/bison/cup...
  • ANTLR
  • Ragel
  • and many others

    • それ以外に、龍書のような専門的な文献がほしいです(『コンパイル原理』、訳者注).そしてcoursera.orgの授業はあなたに役立つかもしれません.
    システムを既存の言語に適応させる必要がある場合は、LLVMのバックエンドとGCCのバックエンドを理解することができます.
    おもちゃのコンパイラについてもっと情報が必要なら、SmallCを理解してください.
    簡単な言語コンパイラを書きたいなら、PL/0かBasicかCを知ることができます.
    しかし、コンパイラを最初から書いて実際の仕事に使わないでください.
    後記
    プロジェクト全体のコードはここで見つけることができます.MITに権限を与え、誰でも無料で使用したり修正したりすることができます.
    いずれにしても、コンパイラはおもしろいものです.あなたがそれを好きになってほしい.
    ふるい素数アルゴリズム(一)——線形ふるい素数アルゴリズム
    一、アルゴリズム第四版(二分検索、リュック、キュー、スタック)