Go to Qiita Advent Calendar Top
LoginSignup
10
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@_53ain株式会社Works Human Intelligence

Rust+LLVMでコンパイラを作る：#3 大枠づくり

Last updated at Posted at 2022-06-30

本連載のバックナンバー

お久しぶりです。
前回の記事から2年も経ってしまいましたが、たまにはコンパイラ作成記事を投稿したいと思います。

今回はプロジェクトの土台となる枠組みを作ることを目的とし、数値が一つ書かれたファイルが渡されると、実行するとその数値を表示するだけの実行ファイルを生成するコンパイラ（？）を実装することを目標とします。

環境について

前回から時間が経ってしまい、LLVMも14が最新版となりました。そのため、前回の記事でLLVMの8を使用している箇所は14に読み替えていただければと思います。
また、各種ツールチェインについても可能な限り最新版を使用したいと思います。

本記事の執筆にあたっては、以下の環境で動作を確認しています。

  • OS: Windows 10
  • LLVM: 14.0.4 (x86_64-w64-windows-gnu)
  • Rust: 1.61.0
  • gcc: 12.1.0

リポジトリの準備

まず適当なディレクトリで cargo new --lib bonsai を実行し、今回から使用するリポジトリを作成します。名前はなんでも構いませんが、ここでは "bonsai" としました。

次に、Cargo.toml を以下のように書き換えます。

[package]
name = "bonsai"
version = "0.1.0"
authors = ["_53a"]
edition = "2021"

[dependencies]
anyhow = "1.0"
peg = "0.8"
id-arena = "2.2"
inkwell = { git = "https://github.com/TheDan64/inkwell", branch = "master", default-features = false, features = ["llvm14-0", "target-x86"] }

ここでは x86-64 向けの設定を記述してます。他のアーキテクチャを使用している場合はこちらを参考に適宜書き換えてください。

また、以前の記事で紹介したように、Windows上にMSYS2を使用して環境構築を行った場合は、 Cargo.toml と同じディレクトリに build.rs というファイルを作成し、以下の内容を書き込んでください。 inkwellには Windows環境では強制的にlibffiをリンク対象からはずす処理が入っていますが、MSYS2環境ではそれがかえって邪魔になってしまうため、それを回避します。

fn main() {
    println!("cargo:rustc-link-lib=dylib=ffi");
}

コードを書き始める

今回のモジュールでは、Rustのプロジェクトによくあるような、規模が小さいうちは一つのファイルだけに記述し、規模が大きくなったところでモジュールを別のファイルに独立させる、という方法を取ります。ただし、今後規模が大きくなった場合にファイルを分割しやすいよう、機能ごとにモジュールを作成してまとめておきます。

以下のコード群は基本的に src/lib.rs に順に追記していってください。

また、以下に出てくる用語に関しては、前回の記事を参照してください。

AST

ASTでは、 NodeKind に各ノードで異なる部分をもたせ、 Node に共通部分をもたせます。
id_arena::Arena というのは、平たく言うと配列のようなもので、Copy できないオブジェクトを Arena に詰め込み、
その Id を代わりに持ち回ることで、複数からの同時参照を可能にしたり、ライフタイムの管理を楽にしたりする、Rust特有の面倒を軽減するためのライブラリです1。

mod ast {
    #[derive(Debug, Clone, PartialEq)]
    pub enum LitKind {
        IntLit(i64),
    }

    #[derive(Debug, Clone, PartialEq)]
    pub enum NodeKind {
        Lit(LitKind),
    }

    #[derive(Debug, Clone, PartialEq)]
    pub struct Node {
        pub kind: NodeKind,
    }

    pub type Id = id_arena::Id<Node>;
    pub type Arena = id_arena::Arena<Node>;
}

パーサ

パーサはソースコードを受け取り、ASTを生成するモジュールです。今回はパーサ作成を手助けしてくれるライブラリとしてrust-peg というライブラリを使用します。
Rust用のパーサ作成ライブラリはいくつかあるのですが、この peg が一番簡潔で読みやすいかなと考えてチョイスしました。

mod parser {
    use crate::ast;
    use anyhow::{anyhow, Result};
    use std::cell::RefCell;

    #[derive(Debug)]
    pub struct Context {
        pub arena: RefCell<ast::Arena>,
    }

    peg::parser! {
        grammar main_parser(context: &Context) for str {
            rule node(r: rule<ast::NodeKind>) -> ast::Id = n: r() {
                let mut arena = context.arena.borrow_mut();
                arena.alloc(ast::Node{ kind: n })
            }

            rule int_lit() -> ast::NodeKind = n:$(['0' ..= '9']+) {
                ast::NodeKind::Lit(ast::LitKind::IntLit(n.parse().unwrap()))
            }

            pub rule parse() -> ast::Id = n: node(<int_lit()>) { n }
        }
    }

    pub fn parse(source: &str) -> Result<(ast::Arena, ast::Id)> {
        let arena_cell = RefCell::new(ast::Arena::new());
        let context = Context { arena: arena_cell };
        let root =
            main_parser::parse(source, &context).map_err(|e| anyhow!("failed to parse: {}", e))?;

        Ok((context.arena.take(), root))
    }
}

peg::parser! 内に書かれた独自記法のコードがパーサの定義です。今回もっとも重要なのは rule int_lit() -> で数値を受理しているところで、 n:$(['0' ..= '9']+) によって 0から9までの文字の羅列を受理し、それに n という名前をつけ、 { ast::NodeKind::Lit(ast::LitKind::IntLit(n.parse().unwrap())) } で NodeKind を生成しています。

rule node(r: rule<ast::NodeKind>) -> ast::Id の部分は NodeKind から Node を生成し、それを Arena に入れて Id に引き換えるボイラープレートを省略するためのマクロのようなものです。

pub rule parse() -> ast::Id はパーサの中で唯一外部に公開されている rule であり、パーサのエントリーポイントになっています。
外の Rust コードから関数として呼び出すことができます。

IR

IR は AST と異なり、各実装によって形式が様々なのですが、今回は分かりやすさ等を考え、ASTのような木構造を選択しました2。
内容的には AST とあまり変わりありません。

mod ir {
    #[derive(Debug, Clone, PartialEq)]
    pub enum Kind {
        IntValue(i64),
    }

    #[derive(Debug, Clone, PartialEq)]
    pub struct Node {
        pub kind: Kind,
    }

    pub type Id = id_arena::Id<Node>;
    pub type Arena = id_arena::Arena<Node>;
}

IrGen

IrGenはASTなどから中間表現を生成するモジュールです。
今回は型付けなども一切ないため、パーサが生成したASTがそのまま入力になります。

今回のIrGenはASTを順に辿ってIRを生成する物であるため、当然ですがASTとIRの2つの Arena を保持しています。
ここでは、それぞれのモジュール名を冠することで区別しています。

IrGenはASTの木構造を辿る操作がメインとなりますが、今回はASTのノードが数値ノードの一つだけであるため、
あまり木の走査という形にはなっていません。

mod irgen {
    use crate::{ast, ir};
    use anyhow::{anyhow, Result};

    pub struct IrGen {
        ast_arena: ast::Arena,
        ir_arena: ir::Arena,
    }

    impl IrGen {
        fn new(ast_arena: ast::Arena) -> Self {
            Self {
                ast_arena,
                ir_arena: ir::Arena::new(),
            }
        }

        fn new_node(&mut self, kind: ir::Kind) -> ir::Id {
            self.ir_arena.alloc(ir::Node { kind })
        }

        fn generate_impl(&mut self, root: ast::Id) -> Result<ir::Id> {
            let kind = &self
                .ast_arena
                .get(root)
                .ok_or(anyhow!("failed to get ast node from arena"))?
                .kind;
            match kind {
                ast::NodeKind::Lit(lit) => match lit {
                    &ast::LitKind::IntLit(i) => Ok(self.new_node(ir::Kind::IntValue(i))),
                },
            }
        }
    }

    pub fn generate(ast_arena: ast::Arena, root: ast::Id) -> Result<(ir::Arena, ir::Id)> {
        let mut irgen = IrGen::new(ast_arena);
        let ir = irgen.generate_impl(root)?;
        Ok((irgen.ir_arena, ir))
    }
}

いよいよもっとも規模の大きなモジュールである CodeGen です。CodeGenは前回記事でのコード生成を担当するモジュールです。
こちらも IrGen と同様、IRの木構造を辿るのがメインになります。
このモジュールでは、 LLVMが適切な機械語を生成できるような設定を行う処理や、生成した機械語をファイルに書き出す処理なども含まれています3。

CodeGen

mod codegen {
    use crate::ir;
    use anyhow::{anyhow, Result};
    use inkwell::{builder::Builder, context::Context, module::Module, targets, values};
    use std::{collections::HashMap, path::Path};

    #[derive(Debug, Clone)]
    struct Value<'a>(Option<values::AnyValueEnum<'a>>);

    impl<'a> Value<'a> {
        fn from_int_value(v: values::IntValue<'a>) -> Self {
            Self(Some(values::AnyValueEnum::IntValue(v)))
        }

        fn into_int_value(self) -> Result<values::IntValue<'a>> {
            let v = self
                .0
                .ok_or(anyhow!("expected integer value but actually None"))?;
            if !v.is_int_value() {
                anyhow::bail!("expected integer value but actually {:?}", v)
            }
            Ok(v.into_int_value())
        }
    }

    pub struct CodeGen<'a> {
        ir_arena: ir::Arena,
        context: &'a Context,
        module: Module<'a>,
        builder: Builder<'a>,
        target_machine: targets::TargetMachine,
    }

    impl<'a> CodeGen<'a> {
        pub fn new(
            ir_arena: ir::Arena,
            context: &'a Context,
            target_machine: targets::TargetMachine,
            module_name: &str,
        ) -> Self {
            let module = context.create_module(module_name);
            let builder = context.create_builder();
            Self {
                ir_arena,
                context,
                module,
                builder,
                target_machine,
            }
        }

        fn generate_builtins(&self) -> Result<HashMap<&str, values::FunctionValue>> {
            let i64_ty = self.context.i64_type();
            let i8_ptr_ty = self
                .context
                .i8_type()
                .ptr_type(inkwell::AddressSpace::Generic);
            let void_ty = self.context.void_type();

            let printf = self.module.add_function(
                "printf",
                void_ty.fn_type(&[i8_ptr_ty.into()], true),
                None,
            );

            let print_int = self.module.add_function(
                "print_int",
                void_ty.fn_type(&[i64_ty.into()], false),
                None,
            );
            let print_int_body = self.context.append_basic_block(print_int, "entry");
            self.builder.position_at_end(print_int_body);

            // cf. https://github.com/TheDan64/inkwell/issues/32
            let format_str = unsafe {
                self.builder
                    .build_global_string("result: %d\n", "format string")
            };
            let format_str = self.builder.build_cast(
                values::InstructionOpcode::BitCast,
                format_str.as_pointer_value(),
                i8_ptr_ty,
                "",
            );
            let val_to_print = print_int
                .get_nth_param(0)
                .ok_or(anyhow!("failed to get first param of print_int"))?
                .into_int_value();

            self.builder
                .build_call(printf, &[format_str.into(), val_to_print.into()], "");
            self.builder.build_return(None);

            let mut builtins = HashMap::new();
            builtins.insert("print_int", print_int);

            Ok(builtins)
        }

        fn generate_impl(&self, id: ir::Id) -> Result<Value> {
            let kind = &self
                .ir_arena
                .get(id)
                .ok_or(anyhow!("failed to get ir from arena"))?
                .kind;

            match kind {
                &ir::Kind::IntValue(i) => Ok(Value::from_int_value(
                    self.context.i64_type().const_int(i as u64, true),
                )),
            }
        }

        pub fn generate(&self, root: ir::Id) -> Result<()> {
            let builtins = self.generate_builtins()?;
            let print_int = builtins
                .get("print_int")
                .ok_or(anyhow!("builtin function not found"))?;

            let ptr_sized_int_ty = self
                .context
                .ptr_sized_int_type(&self.target_machine.get_target_data(), None);

            let main = self
                .module
                .add_function("main", ptr_sized_int_ty.fn_type(&[], false), None);
            let main_body = self.context.append_basic_block(main, "entry");
            self.builder.position_at_end(main_body);

            let val = { self.generate_impl(root)?.into_int_value()? };
            let arg = &[val.into()];

            self.builder.build_call(*print_int, arg, "");

            self.builder.build_return(Some(&val));

            Ok(())
        }

        pub fn write_to_file(&self, file: &Path) -> Result<()> {
            self.module
                .verify()
                .map_err(|e| anyhow!("module verification failed: {}", e))?;
            self.target_machine
                .write_to_file(&self.module, targets::FileType::Object, file)
                .map_err(|e| anyhow!("failed to write object file: {}", e))
        }
    }

    pub fn get_host_target_machine() -> Result<targets::TargetMachine> {
        use targets::*;

        Target::initialize_native(&InitializationConfig::default())
            .map_err(|e| anyhow!("failed to initialize native target: {}", e))?;

        let triple = TargetMachine::get_default_triple();
        let target =
            Target::from_triple(&triple).map_err(|e| anyhow!("failed to get target: {}", e))?;

        let cpu = TargetMachine::get_host_cpu_name();
        let features = TargetMachine::get_host_cpu_features();

        let opt_level = inkwell::OptimizationLevel::Default;
        let reloc_mode = RelocMode::Default;
        let code_model = CodeModel::Default;

        target
            .create_target_machine(
                &triple,
                cpu.to_str()?,
                features.to_str()?,
                opt_level,
                reloc_mode,
                code_model,
            )
            .ok_or(anyhow!("failed to get target machine"))
    }
}

今回は実装が未熟なため、

  • 外部関数（printf）の宣言
  • 関数の定義
  • 関数の呼び出し

といった、bonsai言語上でまだ記述できない機能等を generate_builtins や generate 内で補っています。

Driver

上記のモジュール群をまとめ、コンパイラとして使えるようにするためのモジュールです。
とはいえこのモジュールも単体では実行できないため、

pub mod driver {
    use std::{path::{Path, PathBuf}, io::Read};

    use crate::{codegen, irgen, parser};
    use anyhow::{anyhow, Result};

    pub fn read_file(source: &Path) -> Result<String> {
        let mut buf = String::new();
        let mut f = std::fs::File::open(source)?;
        f.read_to_string(&mut buf)?;
        Ok(buf)
    }

    pub fn generate_object_from_string(name: &str, source: &str, out_dir: Option<PathBuf>) -> Result<PathBuf> {
        let (ast_arena, ast_root) = parser::parse(source)?;
        let (ir_arena, ir_root) = irgen::generate(ast_arena, ast_root)?;
        let context = inkwell::context::Context::create();
        let target_machine = codegen::get_host_target_machine()?;
        let codegen = codegen::CodeGen::new(ir_arena, &context, target_machine, name);
        codegen.generate(ir_root)?;
        let mut output = out_dir.unwrap_or(std::env::current_dir()?);
        output.push(name);
        output.set_extension("o");
        codegen.write_to_file(&output.as_path())?;
        Ok(output)
    }

    pub fn execute_linker(source: &Path) -> Result<PathBuf> {
        let cc = std::env::var("CC").unwrap_or("gcc".into());
        let ext = if cfg!(windows) { "exe" } else { "" };

        let mut output_path = PathBuf::from(source.clone());
        output_path.set_extension(ext);
        
        let compiling = std::process::Command::new(cc)
            .args(vec![source.as_os_str() , std::ffi::OsStr::new("-o"), output_path.as_os_str()])
            .output()?;

        let stderr = String::from_utf8(compiling.stderr)?;
        let status = compiling
            .status
            .code()
            .ok_or(anyhow!("failed to execute the compiler"))?;
        if status != 0 {
            return Err(anyhow!(
                "compile failed with code {}\nstderr: {}",
                status,
                stderr
            ));
        }

        Ok(output_path)
    }

    pub fn compile(source: &Path) -> Result<PathBuf> {
        let src = read_file(source)?;
        let out_dir = PathBuf::from(source.parent().unwrap_or(&source).clone());
        let mod_name = source.file_stem().and_then(|n| n.to_str()).unwrap_or("a");
        let obj = generate_object_from_string(mod_name, src.as_str(), Some(out_dir))?;
        let exe = execute_linker(obj.as_path())?;
        Ok(exe)
    }
}

コンパイルと実行

bonsaic

実行ファイルを作成して実際にコードをコンパイルしてみるために、 driver の機能を呼び出すためだけの小さなバイナリを書きましょう。

まずは src ディレクトリ（先程まで書いてきた lib.rs がある場所）の中に bin というディレクトリを作成してください。
その中に bonsaic.rs というファイルを新たに作成し、以下のコードを入力して保存してください。

use std::path::Path;
use bonsai::driver;
fn main() {

    let args = std::env::args().collect::<Vec<_>>();
    if args.len() < 2 {
        eprintln!("please specify input file");
        std::process::exit(1);
    }
    let source = Path::new(&args[1]);
    match driver::compile(source) {
        Ok(v) => println!("successfully compiled to {}", v.to_str().unwrap_or("<unknown>")),
        Err(v) => eprintln!("failed to compile:\n{}", v)
    }
}

cargo build --bin bonsaic というコマンドを叩いてビルドが通れば成功です。

もしエラーになる場合、

  • 手元の環境にインストールされているLLVMのバージョンを、 Cargo.toml 内の inkwell の features 指定と一致させる
  • LLVM がインストールされているディレクトリ（ lib/ や bin/ がある場所）のパスを 環境変数 LLVM_SYS_140_PREFIX に指定する
    • インストールされている LLVM のバージョンが 14.0 以外の場合は、 上記変数名の 140 を変更してください
  • 環境変数 LLVM_SYS_14_FFI_WORKAROUND をセットする
    • インストールされている LLVM のバージョンが 14.0 以外の場合は、 上記変数名の 14 を変更してください

といったことを試みてみてください。

テスト用の入力ファイル

実際に動作を確認するために入力するソースコード（？）として、数値のみが書かれたファイルを用意します。

例としては、以下の内容を test.bonsai という名前で保存します。

42

注意する点としては、末尾も含めて改行や空白等を含めないこと、UTF-16等でエンコードしないことに留意してください。
Windowsを使用していてターミナル上から echo 42 > test.bonsai などとやると、 UTF-16 LE で保存されたファイルができあがってしまい実行できずにハマります。

実行

上記ファイルが保存されているディレクトリ上で cargo run --bin bonsaic -- test.bonsai を実行します。 successfully compiled to test （Windows ならば test.exe ） という表示が出ればコンパイル成功です。

生成された実行ファイルを実行し、result: 42 という表示が出ることを確認してください。

終わりに

今回はファイルに書いてある数字をオウム返しするだけの、とてもつまらないコンパイラでしたが、コンパイラの大枠は整えることができました。
次回以降は四則演算を実装したり、エラー表示を多少まともにしたり、モジュールを複数のファイルに分割したりといったことができたらなと考えています。

それでは次回をお楽しみに4

2022-12-31 追記: 次回はこちらです

  1. とはいえ通常の Box を使うのと一長一短であるため、将来的に使用しなくなる可能性もあります ↩

  2. タイガーブックの中間表現も木構造だったのでいいかなと…… ↩

  3. 将来的に分離するかもしれません ↩

  4. また2年後かもしれませんが ↩

10
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
10
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?