コンパイラアーキテクチャの王者LLVM――(6)マルチパス翻訳のマクロ翻訳システム

LLVMプラットフォームは、わずか数年の間に、多くのプログラミング言語の行方を変え、多くの特色のあるプログラミング言語の出現を促した.
本文は西風逍遥旅行のオリジナルの文章で、転載は出典の西風の世界を明記してくださいhttp://blog.csdn.net/xfxyy_sxfancy
マルチパス翻訳マクロ翻訳システム
前回は文法ツリーを構築する基本モデルについて議論しましたが、Lex+Bison+Nodeを利用して、いくつかのコンポーネントが私たちの目標文法をAST文法ツリーに翻訳することができます.第4章では、RedAppleという実装型コンパイラの文法構造も示しました.では、私たちの準備は基本的な完成に基づいています.
AST構文ツリーの構築を完了した後、構文ツリー全体を遍歴し、LLVMのモジュールに翻訳して.bcバイトコードに出力するメカニズムが必要です.
このメカニズムは、文法ツリー全体を複数回スキャンし、必要な部分をスキャンするたびにモジュール全体を構築するため、複数のマクロ翻訳システムと呼ばれています.Javaのような構文特性を実現することを望んでいます.定義順序を考慮する必要はありません.定義すれば、この記号を見つけることができます.これには合理的なスキャン順序が必要です.
スキャン順序の決定
まず、タイプの宣言が重要なため、タイプ宣言がなければ関数を構築できません.次に、すべての関数をスキャンし、関数の宣言を構築します.最後に,すべての関数定義をスキャンし,各関数の関数体を構築した.
このように我々は3回のスキャンであり,効率の問題を心配する必要はない.前の2回のスキャンはいずれもルートノードの下の層であり,スキャンの要素が非常に少ないため,処理が速い.
スキャン対象AST構文ツリー
これは私たちが前に生成したAST文法ツリーで、構造はまだはっきりしているでしょう.我々が利用できる遍歴手段は,前回実装したnextポインタであり,現在のノードのデータを絶えず判断し,対応するコードを生成することである.
各文の意味を区別するために、各リストの先頭に翻訳マクロの名前を追加しました.この設計はlispを模倣したもので、マクロはコンパイラの関数に相当し、メタデータを処理し、それを対応する内容に翻訳します.
たとえば、このコード:

void hello(int k, int g) {
    int y = k + g;
    printf("%d
", y);
    if (k + g < 5) printf("right
");
}   


void go(int k) {
    int a = 0;
    while (a < k) {
        printf("go-%d
", a);
        a = a + 1;
    }
}

void print(int k) {
    for (int i = 0; i < 10; i = i+1) {
        printf("hello-%d
",i);
    } 
}


void main() {
    printf("hello world
");
    hello(1,2);
    print(9);
}

AST構文ツリーは次のとおりです.

Node
    Node
        String function
        String void
        String hello
        Node
            Node
                String set
                String int
                String k

            Node
                String set
                String int
                String g

        Node
            Node
                String set
                String int
                String y
                Node
                    String opt2
                    String +
                    ID k
                    ID g


            Node
                String call
                String printf
                String %d

                ID y

            Node
                String if
                Node
                    String opt2
                    String <
                    Node
                        String opt2
                        String +
                        ID k
                        ID g

                    Int 5

                Node
                    String call
                    String printf
                    String right

    Node
        String function
        String void
        String go
        Node
            Node
                String set
                String int
                String k

        Node
            Node
                String set
                String int
                String a
                Int 0

            Node
                String while
                Node
                    String opt2
                    String <
                    ID a
                    ID k

                Node
                    Node
                        String call
                        String printf
                        String go-%d

                        ID a

                    Node
                        String opt2
                        String =
                        ID a
                        Node
                            String opt2
                            String +
                            ID a
                            Int 1

    Node
        String function
        String void
        String print
        Node
            Node
                String set
                String int
                String k

        Node
            Node
                String for
                Node
                    String set
                    String int
                    String i
                    Int 0

                Node
                    String opt2
                    String <
                    ID i
                    Int 10

                Node
                    String opt2
                    String =
                    ID i
                    Node
                        String opt2
                        String +
                        ID i
                        Int 1


                Node
                    Node
                        String call
                        String printf
                        String hello-%d

                        ID i



    Node
        String function
        String void
        String main
        Node
        Node
            Node
                String call
                String printf
                String hello world


            Node
                String call
                String hello
                Int 1
                Int 2

            Node
                String call
                String print
                Int 9

スキャン中のコンテキスト
翻訳の過程で、LLVMContext変数、シンボルテーブル、マクロ定義テーブルなどの必要な情報が必要です.また、必要な情報を格納するために、自分でコンテキストクラスを実現する必要があります.コンテキストクラスは最初のスキャンの前に初期化する必要があります.
たとえば、翻訳で変数に遭遇した場合、その変数は一時的なものなのか、グローバルなものなのか.どのようなタイプで、シンボルテーブルに表現を格納する必要があります.また、現在翻訳されている文はどのマクロに属していますか.どのように翻訳しますか.これらの情報を保存するクラスが必要です.
そこで私たちはまず実現の話をしないで、インタフェースを書きます

class CodeGenContext;
typedef Value* (*CodeGenFunction)(CodeGenContext*, Node*);
typedef struct _funcReg
{
    const char*     name;
    CodeGenFunction func;
} FuncReg;


class CodeGenContext
{
public:
    CodeGenContext(Node* node);
    ~CodeGenContext();

    //         
    void PreInit();
    void PreTypeInit();
    void Init();

    void MakeBegin() { 
        MacroMake(root); 
    }

    //             Node  
    Value* MacroMake(Node* node);
    //             
    void MacroMakeAll(Node* node); 
    CodeGenFunction getMacro(string& str);

    // C++   
    // void AddMacros(const FuncReg* macro_funcs); //          
    void AddOrReplaceMacros(const FuncReg* macro_funcs);

    //          
    BasicBlock* getNowBlock();
    BasicBlock* createBlock();
    BasicBlock* createBlock(Function* f);

    //              
    Function* getFunction(Node* node);
    Function* getFunction(std::string& name);
    void nowFunction(Function* _nowFunc);

    void setModule(Module* pM) { M = pM; }
    Module* getModule() { return M; }
    void setContext(LLVMContext* pC) { Context = pC; }
    LLVMContext* getContext() { return Context; }

    //         
    void DefType(string name, Type* t);
    Type* FindType(string& name);
    Type* FindType(Node*);

    void SaveMacros();
    void RecoverMacros();

    bool isSave() { return _save; }
    void setIsSave(bool save) { _save = save; }

    id* FindST(Node* node) const;

    id* FindST(string& str) const {
        return st->find(str);
    }
    IDTable* st;
private:
    //       
    Node* root;

    //    LLVM Module
    Module* M;
    LLVMContext* Context;
    Function* nowFunc;
    BasicBlock* nowBlock;

    //               
    map<string, CodeGenFunction> macro_map;

    //                  
    stack<map<string, CodeGenFunction> > macro_save_stack;

    void setNormalType();

    //                
    bool _save;
};

マクロの登録
マクロは内部のとても重要な関数で、自身は1つのC関数のポインタで、マクロは唯一の名前があって、map表を通じて、そのマクロの対応する関数を探して、それからそれを呼び出して現在の文法のノードに対して解析を行います.
マクロ関数の定義:

typedef Value* (*CodeGenFunction)(CodeGenContext*, Node*);

私がluaに倣って設計したことを登録し、関数ポインタを配列に組織し、構造体に初期化します.

extern const FuncReg macro_funcs[] = {
    {"function", function_macro},
    {"struct",   struct_macro},
    {"set",      set_macro},
    {"call",     call_macro},
    {"opt2",     opt2_macro},
    {"for",      for_macro},
    {"while",    while_macro},
    {"if",       if_macro},
    {"return",   return_macro},
    {"new",      new_macro},
    {NULL, NULL}
};

このように書くのは、私たちが一度に関数を導入して私たちのシステムに入るのを便利にするためです.関数ポインタは私はやはりCポインタを使うことに慣れています.一般的にC++のメンバーポインタを使うのを避けます.それは複雑すぎて、他のモジュールとリンクしにくいです.C++には標準ABIがありませんが、C言語はあります.
スキャンのブートを実現
スキャンは簡単です.現在のノードが文字列であり、マクロ定義で見つかった場合は、このマクロを呼び出して処理します.そうしないと、リストの化であれば、各マクロを再帰的に処理します.
マクロの検索はstlテンプレートライブラリのmapとstringを直接使用して、とても便利です.

Value* CodeGenContext::MacroMake(Node* node) {
    if (node == NULL) return NULL;

    if (node->isStringNode()) {
        StringNode* str_node = (StringNode*)node;
        CodeGenFunction func = getMacro(str_node->getStr());
        if (func != NULL) {
            return func(this, node->getNext());
        } 
        return NULL;
    } 
    if (node->getChild() != NULL && node->getChild()->isStringNode())
        return MacroMake(node->getChild());
    Value* ans;
    for (Node* p = node->getChild(); p != NULL; p = p->getNext()) 
        ans = MacroMake(p);
    return ans;
}

CodeGenFunction CodeGenContext::getMacro(string& str) {
    auto func = macro_map.find(str);
    if (func != macro_map.end()) return func->second;
    else return NULL;
}

このようにして、私たちはマクロ翻訳を導くことができます.では、何回も翻訳はどのように実現されていますか.実はとても簡単で、マクロ登録関数を使って現在のマクロを置き換えればいいので、翻訳ガイドを再実行して、何度も翻訳したのではないでしょうか.