Membuat Bahasa Pemrograman Sederhana dengan Rust dan LLVM

Setelah kita membuat Lexer dan Parser kita memerlukan 1 hal lagi yaitu fungsi untuk mengevaluasi expression yang sudah ada.

Untuk kode yang sudah lengkap bisa dilihat di github: https://github.com/aldidana/hitung

Kita bisa saja mengevaluasi expression yang sudah ada langsung menggunakan Rust tanpa llvm atau kita juga bisa mentranslate expression yang ada tadi menjadi sebuah Bytecode yang akan dijalankan di VM

Namun untuk tutorial kali ini kita akan menjalankannya dengan menggunakan JIT (Just In Time) compiler dari llvm.

LLVM adalah sebuah compiler infrastructure dimana kita dapat membuat sebuah instruksi berupa intermediate representation atau IR, kemudian llvm juga dapat meng-compile IR menjadi binary yang berdiri sendiri (standalone binary) atau melakukan Just In Time compilation pada saat runtime.

Dibawah ini adalah contoh IR dari kode if 1 < 2 then 1 else 0.

define double @@berhitung() {
entry:
  br i64 1, label %entry1, label %entry2

entry1:                                           ; preds = %entry
  br label %entry3

entry2:                                           ; preds = %entry
  br label %entry3

entry3:                                           ; preds = %entry2, %entry1
  %entry4 = phi double [ 1.000000e+00, %entry1 ], [ 0.000000e+00, %entry2 ]
  ret double %entry4
}

if.ll

Kita akan menggunakan library Inkwell. Inkwell merupakan sebuah high-level wrapper dari library llvm-sys.

LLVM

Untuk mengikutin ini pastikan kia sudah meng-install llvm versi 10.

Untuk mengecek versi llvm yang sudah terinstall bisa menggunakan perintah ini:

llvm-config --version

Struktur

hitung
│   Cargo.toml   
│
└───src
	| main.rs
	| lexer.rs
   	| token.rs
	| expression.rs
	| parser.rs
	| jit.rs //file baru

Cargo.toml

Buka file cargo.toml dan tambahkan library inkwell.

[package]
name = "hitung"
version = "0.1.0"
authors = ["Nama Author"]
edition = "2018"

[dependencies]
inkwell = { git = "https://github.com/TheDan64/inkwell", branch = "master", features = ["llvm10-0"] }

JIT (Just In Time)

Kita akan membutuhkan 3 objek yang ada di llvm.

Context: Bagian inti/core dari llvm
Module: Tempat dimana fungsi dan IR di simpan
Builder: Yang akan melakukan instruksi kemudian memasukannya ke dalam BasicBlock

Buka file jit.rs dan tambahkan barisan kode berikut ini:

use std::collections::HashMap;
use std::path::Path;

use inkwell;
use inkwell::builder::Builder;
use inkwell::context::Context;
use inkwell::module::Module;
use inkwell::values::PointerValue;
use inkwell::FloatPredicate;
use inkwell::OptimizationLevel;

use crate::expression::Expression;
use crate::lexer::Lexer;
use crate::parser::Parser;
use crate::token::Token;

pub type FuncSign = unsafe extern "C" fn() -> f64;

Kita menambahkan beberapa module yang berkaitan dengan inkwell dan membuat tipe data yang dibutuhkan untuk hasil dari fungsi yang dipanggil oleh llvm.

Untuk bagian pub type FuncSign = unsafe extern "C" fn() -> f64; disini adalah kita akan memanggil eksternal kode agar dapat menggunakan suatu fungsi dari bahasa pemrograman lain dalam hal ini bahasa pemrograman C, bagian "C" diatas disebut ABI (Application Binary Interface) sedangkan keyword extern yang memfasilitasi FFI (Foreign Function Interface). Penggunaan keyword extern sendiri tidak membutuhkan keyword unsafe tetapi untuk memanggilnya dibutuhkan keyword unsafe, dikarenakan Rust tidak mengetahui aturan dan jaminan dari bahasa lain tersebut.

Tambahkan kode berikut setelah kode diatas:

pub struct Compiler<'ctx> {
    context: &'ctx Context,
    module: Module<'ctx>,
    builder: Builder<'ctx>,

    variables: HashMap<String, PointerValue<'ctx>>,
    debug: bool,
}

Struct Compiler terdiri dari Context untuk menyimpan konteks llvm selama program berjalan, Module, Builder, Variables untuk menyimpan Global Variable berupa HashMap yang isinya adalah sebuah pointer, Debug untuk menampilkan IR yang telah dibuat.

Kemudian lanjutkan dengan membuat associate function dan method untuk Compiler diatas.

impl<'ctx> Compiler<'ctx> {
    pub fn new(context: &'ctx Context, debug: bool) -> Self {
        let module = context.create_module("hitung");
        let builder = context.create_builder();

        Compiler {
            context,
            module,
            builder,
            variables: HashMap::new(),
            debug,
        }
    }
    pub fn compile_source(&mut self, source: &str) -> Result<f64, String> {
        let lexer = Lexer::new(source);
        let tokens = lexer.lex();
        let mut parser = Parser::new(tokens);
        match parser.expr(0) {
            Ok(expression) => self.jit_compile(expression),
            Err(e) => Err(e),
        }
    }
    .... // fungsi berikutnya
}

jit.rs

Fungsi new diatas menerima sebuah reference Context dari fungsi yang memanggilnya karena kita membutuhkannya selama program berjalan, fungsi ini juga akan membuat sebuah module yang dinamai "hitung".

Fungsi compile_source akan memanggil Lexer dan Parser untuk menghasilkan expression dari kode sumber yang sudah dimasukan, fungsi ini akan memanggil fungsi jit_compile jika dapat menghasilkan expression yang benar.

Tambahkan fungsi jit_compile berikut setelah fungsi compile_source:

... // fungsi sebelumnya
pub fn jit_compile(&mut self, expr: Expression) -> Result<f64, String> {
    let float = self.context.f64_type();
    let fn_type = float.fn_type(&[], false);
    let function = self.module.add_function("berhitung", fn_type, None);
    let basic_block = self.context.append_basic_block(function, "entry");
    self.builder.position_at_end(basic_block);

    let return_val = self.eval(expr)?;
    self.builder.build_return(Some(&return_val));

    let execution_engine = self
        .module
        .create_jit_execution_engine(OptimizationLevel::None)
        .map_err(|e| e.to_string())
        .unwrap();

    let last_func = self.module.get_last_function().unwrap();
    let last_func_name = last_func.get_name().to_str().unwrap();

    let function_calc = unsafe { execution_engine.get_function::<FuncSign>(last_func_name) };

    if self.debug {
        println!("LLVM IR:");
        function.print_to_stderr();
        self.module
            .print_to_file(Path::new("hitung.ll"))
            .expect("Error print to file");
    }

    match execution_engine.remove_module(&self.module) {
        Ok(_ok) => match function_calc {
            Ok(f) => Ok(unsafe { f.call() }),
            Err(err) => {
                println!("!> Error during execution: {:?}", err);
                Err(err.to_string())
            }
        },
        Err(err) => Err(err.to_string()),
    }
}

jit.rs

Fungsi jit_compile akan membuat sebuah fungsi "berhitung" di dalam module "hitung" dengan tipe data f64 dan fungsi ini tidak mempunyai parameter. Selanjutnya kita membuat sebuah basic block yang dinamai "entry", basic block adalah urutan untuk instruksi, basic block disini mengacu pada fungsi yang sudah dibuat yaitu fungsi "berhitung". Lalu kita menginformasikan builder untuk mulai dari/berpindah ke basic block ini. Basic block dari fungsi ini juga membutuhkan tipe data yang akan dikembalikan, oleh karena itu tipe data yang akan dikembalikan diambil setelah mengevaluasi expression yang ada dari fungsi eval.

Berikut ini contoh fungsi dan basic block llvm:

define double @berhitung() {
entry:
	ret double 1.000000e+00
}

Selanjutnya membuat execution_engine dari module yang sudah kita buat sebelumnya, execution_engine akan menjalankan fungsi yang sudah diisi basic block. Disini juga kita akan mencetak setiap hasil dari module tersebut ke file hitung.ll jika Debug diset menjadi true. Kemudian execution_engine melepas module yang kita buat sebelumnya agar kita bisa membuat kembali execution_engine baru dengan module yang sama dari setiap kode sumber yang dimasukan.

Aritmatika

Sebelum ke tahap selanjutnya, disini akan membahas fungsi aritmatika yang ada di llvm.

Misalnya kita mempunyai sebuah fungsi penjumlahan seperti ini:

fn add(lhs: f64, rhs: f64) -> f64 {
	lhs + rhs
}

Dalam library Inkwell kita bisa memanggilnya dengan fungsi yang mirip seperti fungsi diatas:

builder.build_float_add(lhs, rhs, "add") // nama bisa diisi apa saja

Maka fungsi diatas akan langsung mengembalikan jawaban yang sesuai.

Eval

Kembali ke file jit.rs, setelah fungsi jit_compile tambahkan kode berikut:

fn eval(
    &mut self,
    expression: Expression,
) -> Result<inkwell::values::FloatValue<'ctx>, String> {
    match expression {
        Expression::Variable(name) => match self.variables.get(&name) {
            Some(value) => {
                let val = self.builder.build_load(*value, name.as_str());
                Ok(val.into_float_value())
            }
            None => Err("Variable not declared".to_string()),
        },
        Expression::Num(n) => {
            let float = self.context.f64_type();
            Ok(float.const_float(n as f64))
        }
        Expression::Unary(operator, expr) => match operator {
            Token::Add => {
                let num = self.eval(*expr)?;

                Ok(num)
            }
            Token::Sub => {
                let float = self.context.f64_type();
                let num = self.eval(*expr)?;
                let rhs = float.const_float_from_string("-1");
                let sum = self.builder.build_float_mul(num, rhs, "mul");
                Ok(sum)
            }
            _ => Err("Expression for Unary must be + or -".to_string()),
        },
        ... // berikutnya
	}
}

jit.rs

catatan: fungsi eval dipanggil dengan cara recursive untuk mengevaluasi expression lainnya.

Jika expression itu adalah expression untuk variable maka kita akan mencari apakah variable tersebut ada atau tidak, variable saat ini disimpan di global variable, jika variable tersebut ada maka kita mengambil pointer dari isi variable tersebut.

Jika expression berupa angka atau num maka kita hanya perlu mengembalikan angka tersebut dengan tipe data yang sudah ditentukan (dalam hal ini f64)

Jika expression tersebut berupa Unary operator maka kita perlu menentukan bagian kiri dan bagian kanan yang ada dari expression tersebut, misalnya jika +3 maka akan menjadi 3 tetapi jika -3 tetap menjadi -3, disini kita hanya mengecek unary untuk +angka dan -angka.

Masih didalam fungsi eval, tambahkan kode berikutnya:

... // sebelumnya
Expression::Binary(left, operator, right) => match operator {
    Token::LT | Token::GT => {
        let lhs = self.eval(*left)?;
        let rhs = self.eval(*right)?;

        let predicate = match operator {
            Token::LT => FloatPredicate::OLT,
            Token::GT => FloatPredicate::OGT,
            _ => return Err("Operator not supported".to_string()),
        };

        let conditional = self.builder.build_float_compare(predicate, lhs, rhs, "if");

        Ok(self.builder.build_unsigned_int_to_float(
            conditional,
            self.context.f64_type(),
            "bool",
        ))
    },
    Token::ASSIGN => match *left {
        Expression::Variable(var) => {
            let f64_type = self.context.f64_type();
            let global = self.module.add_global(f64_type, None, var.as_str());
            global.set_initializer(&f64_type.const_float(0 as f64));
            let rhs = self.eval(*right)?;
            global.set_initializer(&rhs);
            self.builder.build_store(global.as_pointer_value(), rhs);

            let value = self
                .builder
                .build_load(global.as_pointer_value(), var.as_str());
            self.variables.insert(var, global.as_pointer_value());

            Ok(value.into_float_value())
        }
        _ => Err("Assignment must be a variable".to_string()),
    },
    _ => {
        let lhs = self.eval(*left)?;
        let rhs = self.eval(*right)?;

        match operator {
            Token::Add => Ok(self.builder.build_float_add(lhs, rhs, "add")),
            Token::Sub => Ok(self.builder.build_float_sub(lhs, rhs, "sub")),
            Token::Mul => Ok(self.builder.build_float_mul(lhs, rhs, "mul")),
            Token::Div => Ok(self.builder.build_float_div(lhs, rhs, "div")),
            _ => Err("Operator not supported".to_string()),
        }
    }
},
Expression::Paren(expr) => {
    let result = &self.eval(*expr)?;
    Ok(*result)
}
... // berikutnya

jit.rs

Untuk binary operator:

Jika expression berupa sebuah komparasi lebih besar (GT) dari atau lebih kecil dari (LT) llvm memiliki sebuah predicate sesuai dengan dua hal tersebut, komparasi akan mengembalikan angka 1 jika true dan 0 jika false.
Jika expression berupa Variable Assignment maka kita akan mengambil angka dari variable tersebut lalu menyimpannya di global variable, disini juga kita langsung mengembalikan angka dari variable tersebut.
Jika Binary operator bukan dari kedua diatas, maka binary operator tersebut adalah sebuah aritmatika.

Kemudian jika expression yang ditemukan berupa tanda kurung maka kita akan mengevaluasi expression yang ada didalamnya.

Terakhir masih dengan fungsi yang sama yaitu fungsi eval, tambahkan kode dibawah ini:

... // sebelumnya
Expression::Conditional(cond, then, els) => {
    let if_cond = self.eval(*cond)?;

    let function = self.module.get_last_function().unwrap();

    let then_block = self.context.append_basic_block(function, "entry");
    let else_block = self.context.append_basic_block(function, "entry");
    let cont_block = self.context.append_basic_block(function, "entry");

    let i64_type = self.context.i64_type();

    self.builder.build_conditional_branch(
        if_cond.const_to_unsigned_int(i64_type),
        then_block,
        else_block,
    );
    self.builder.position_at_end(then_block);

    let then_value = self.eval(*then)?;
    self.builder.build_unconditional_branch(cont_block);
    let then_block = self.builder.get_insert_block().unwrap();

    // build else block
    self.builder.position_at_end(else_block);
    let else_value = self.eval(*els)?;
    self.builder.build_unconditional_branch(cont_block);

    let else_block = self.builder.get_insert_block().unwrap();
    self.builder.position_at_end(cont_block);

    let phi = self.builder.build_phi(self.context.f64_type(), "entry");
    phi.add_incoming(&[(&then_value, then_block), (&else_value, else_block)]);

    Ok(phi.as_basic_value().into_float_value())
}

jit.rs

Untuk expression terakhir adalah branching/conditional atau pencabangan. Kita menambahkan 3 basic block dari fungsi yang sudah dibuat, yaitu basic block untuk then, else dan cont yang dinamai "entry", jika memiliki nama basic block yang sama makan nama tersebut akan ditambahkan angka, misalnya "entry" -> "entry1" -> "entry2". Untuk menentukan cabang mana yang akan dijalankan adalah dengan phi node dengan memberikan daftar instruksi dari sebuah basic block dan nilai dari basic block itu sendiri.

Test JIT

Tambahkan kode ini di bagian paling bawah untuk mengetest fungsi yang ada pada file jit.rs ini:

impl<'ctx> Compiler<'ctx> {
 ....
}

// tambahkan test disini
#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test_eval_from_expression() {
        let expression = Expression::Binary(
            Box::new(Expression::Binary(
                Box::new(Expression::from(3)),
                Token::Add,
                Box::new(Expression::from(2)),
            )),
            Token::Sub,
            Box::new(Expression::from(2)),
        );

        let context = Context::create();
        let module = context.create_module("test_hitung");
        let builder = context.create_builder();

        let mut compiler = Compiler {
            context: &context,
            module,
            builder,
            variables: Default::default(),
            debug: false,
        };

        let actual = compiler.jit_compile(expression).unwrap();
        assert_eq!(3.0, actual);
    }

    #[test]
    fn test_eval_from_source() {
        let context = Context::create();
        let mut compiler = Compiler::new(&context, false);

        let actual = compiler.compile_source(r"2 + 2 * 3 / 2").unwrap();

        assert_eq!(5.0, actual);
    }

    #[test]
    fn test_eval_from_source_if_then_else() {
        let context = Context::create();
        let mut compiler = Compiler::new(&context, false);

        let actual = compiler.compile_source(r"if 1 < 2 then 123 else 456").unwrap();

        assert_eq!(123.0, actual);
    }
}

jalankan test dan pastikan semuanya sukses

cargo test

Main

Saatnya kembali ke file main.rs untuk menggunakan jit compiler yang telah dibuat, pastikan file main.rs menjadi seperti dibawah ini:

use std::io;
use std::io::Write;

use inkwell::context::Context;

mod expression;
mod jit;
mod lexer;
mod parser;
mod token;

use jit::Compiler;

fn main() {
    let mut debug = false;

    for arg in std::env::args() {
        match arg.as_str() {
            "debug" => debug = true,
            _ => (),
        }
    }

    let context = Context::create();
    let mut compiler = Compiler::new(&context, debug);

    loop {
        // repl
        println!();
        print!("> ");

        io::stdout().flush().expect("Error when flush stdout.");

        let mut input = String::new();

        io::stdin()
            .read_line(&mut input)
            .expect("Could not read from standard input.");

        match compiler.compile_source(input.as_str()) {
            Ok(result) => println!("{}", result),
            Err(err) => {
                eprintln!("Error {:?}", err);
                break
            },
        }
    }
}

Jalankan program dan aktifkan debug mode

cargo run debug

Silahkan ketikan input yang diinginkan, contoh:

a = 2 // tekan enter
a + 2 * 3 tekan enter

Maka hasilnya adalah 8

contoh menghitung:

2 + ( 4 + 5) * 7 / 2 * 4

Hasilnya 128

contoh if then else:

if 20 > 15 then 100 else 99

Hasilnya 100

Jika debug aktif pastikan anda dapat melihat file hitung.ll

Masih banyak sekali hal yang dapat ditingkatkan di bahasa "hitung" ini, misalnya menambahkan fungsi dan memanggil fungsi tersebut, for loop, if then else yang tidak hanya 1 level.

Sekian.

Bagian 1 - https://aldidana.com/membuat-bahasa-pemrograman-rust-llvm-lexer/
Bagian 2 - https://aldidana.com/membuat-bahasa-pemrograman-rust-llvm-parser/
(Disini) Bagian 3 - https://aldidana.com/membuat-bahasa-pemrograman-rust-llvm-jit-compiler/

Membuat Bahasa Pemrograman Sederhana dengan Rust dan LLVM - Bagian 3 JIT Compiler

LLVM

Struktur

Cargo.toml

JIT (Just In Time)

Aritmatika

Eval

Test JIT

Main

Aldi Perdana

LLVM

Struktur

Cargo.toml

JIT (Just In Time)

Aritmatika

Eval

Test JIT

Main

You might also like...