JBrainfuck — Пишем компилятор Brainfuck под Java VM

Меня давно интересовал вопрос написания своего компилятора под Java VM, но было недостаточно опыта, дабы сделать это. Да и как-то руки не доходили, а недавно все же решил разобраться в этой теме и заодно рассказать о своем опыте создания компилятора под эту VM.

В качестве реализуемого языка возьмем Brainfuck. Он прост в реализации, что отлично подходит для изучения данной темы, но сначала предоставлю вам свою реализацию.

JBrainfuck — оптимизирующий интерпретатор и компилятор Brainfuck под Java VM. Благодаря JIT обладает высокой производительностью.

• Лицензия: MIT
• Адрес проекта: https://github.com/SystemX-Files/jbrainfuck/
• Платформы: Linux, Windows, MacOS и везде, где есть Java.

Выбор средств разработки

Вполне очевидным решением будет писать компилятор на Java.
Для генерации байт-кода возьмем библиотеку ASM. Ее применяют такие популярные языки как Groovy, JRuby и др.
Чтобы удобно смотреть байт-код JVM, установим плагины в нашу IDE.

• Bytecode Outline — для Eclipse
• ASM Bytecode Outline — для IDEA

Начинаем творить

Думаю многим известен реализуемый нами язык Brainfuck. Он состоит всего лишь из 8 простых команд, но тем не менее полный по тьюрингу, что позволяет реализовать на этом языке что угодно, хоть ОС (боже упаси).
Суть его проста. У нас есть лента памяти, по которой можно перемещаться вправо или влево, а так же менять значение ячейки, прибавляя или убавляя ее.

Вот список этих команд:

char[] arr = new char[30000];
int i = 15000;

i--;

i++;

arr[i]++;

arr[i]--;

System.out.print(arr[i]);

arr[i] = (char)System.in.read();

while(arr[i] != 0) {

}

Пример программы на Brainfuck, печатающей «Hello, Habr!»:

++++++++[>+>++>+++>++++>+++++>++++++>+++++++>++++++++>
+++++++++>++++++++++>+++++++++++>++++++++++++>++++++++
+++++>++++++++++++++>+++++++++++++++>++++++++++++++++<
<<<<<<<<<<<<<<<-]>>>>>>>>>.<<<<<<<<<>>>>>>>>>>>>>---.+
++<<<<<<<<<<<<<>>>>>>>>>>>>>>----.++++<<<<<<<<<<<<<<>>
>>>>>>>>>>>>----.++++<<<<<<<<<<<<<<>>>>>>>>>>>>>>-.+<<
<<<<<<<<<<<<>>>>>>----.++++<<<<<<>>>>.<<<<>>>>>>>>>.<<
<<<<<<<>>>>>>>>>>>>+.-<<<<<<<<<<<<>>>>>>>>>>>>++.--<<<
<<<<<<<<<>>>>>>>>>>>>>>++.--<<<<<<<<<<<<<<>>>>+.-<<<<.

Пишем компилятор

Так как писать компилятор мы собираемся по всем правилам, то у него будет три стадии компиляции: лексический анализ, оптимизация и генерация байткода.
Для начала стоит обдумать возможные оптимизации, это позволит выяснить как удобнее проектировать компилятор.

Оптимизации

Наверное первое, что бросается в глаза, это однотипные операции. Разумеется сразу появляется идея все это дело сжать и множество операций свести к виду #~, где # — кол-во операций, а ~ — операция.
Так же код вида [-] или [+] является обнулением ячейки, так что есть смысл выделить для этого отдельную операцию.

Если дальше продвигать идею уменьшения кол-во операций, то можно понять, что операции сложения/вычитания эквивалентны и отличаются лишь знаком числа. Значит можно их привести к одной операции. Тоже самое допустимо и для операции движения влево/вправо.

После всех оптимизаций составим новую таблицу операций. Как раз под нее и будем делать наш компилятор.

i += arg;

arr[i] += arg;

arr[i] = 0;

while(arg --> 0)
	System.out.print(arr[i]);

while(arg --> 0)
	arr[i] = (char)System.in.read();

while(arr[i] != 0) {

}

Напишем класс, который будет хранить в себе операцию и кол-во повторений.

public class Opcode{
    public enum Type{
        SHIFT,
        ADD,
        ZERO,
        OUT,
        IN,
        WHILE,
        END
    }

    public Type type = null; //тип операции
    public int arg = 1; //кол-во повторений

    public Opcode(Type type, int arg) {
        this.type = type;
        this.arg = arg;
    }

    public Opcode(Type type) {
        this.type = type;
    }

    public Opcode clone(){
        return new Opcode(type, arg);
    }
}

Лексический анализатор

Выделим лексемы, которые могут встречаться в коде Brainfuck:

А теперь напишем анализатор, который выделит последовательность этих лексем:

public abstract class Tokenizer{
    public static List<Opcode> tokenize(String code) {
        //Создаем массив лексем (которые уже являются опкодами и готовы к исполнению)
        List<Opcode> retValue = new ArrayList<Opcode>();
        int pos = 0;

        //Приходимся по всем символам
        while (pos < code.length()) {
            switch (code.charAt(pos++)) {
                //Как и говорилось ранее, некоторые команды эквивалентны
                case '>': retValue.add(new Opcode(Opcode.Type.SHIFT, +1)); break;
                case '<': retValue.add(new Opcode(Opcode.Type.SHIFT, -1)); break;

                case '+': retValue.add(new Opcode(Opcode.Type.ADD, +1)); break;
                case '-': retValue.add(new Opcode(Opcode.Type.ADD, -1)); break;

                case '.': retValue.add(new Opcode(Opcode.Type.OUT)); break;
                case ',': retValue.add(new Opcode(Opcode.Type.IN)); break;
                case '[':
                    char next = code.charAt(pos);

                    //проверяем, является ли это обнулением ячейки ([+] или [-])
                    if((next == '+' || next == '-') && code.charAt(pos + 1) == ']') {
                        retValue.add(new Opcode(Opcode.Type.ZERO));
                        pos += 2;
                    } else
                        retValue.add(new Opcode(Opcode.Type.WHILE));
                    break;
                case ']': retValue.add(new Opcode(Opcode.Type.END)); break;
            }
        }

        return retValue;
    }
}

Оптимизатор

Теперь наша задача сжать повторяющийся операции и убрать лишние (например несколько подряд команд ZERO).
Все делается относительно просто:

public abstract class Optimizer {
    public static List<Opcode> optimize(String code) {
        return optimize(Tokenizer.tokenize(code));
    }

    public static List<Opcode> optimize(List<Opcode> tokens) {
        Stack<Opcode> retValue = new Stack<Opcode>();

        //Приходимся по всем командам
        for (Opcode token : tokens) {
            switch (token.type){
                case SHIFT:
                case ADD:
                case OUT:
                case IN:
                case ZERO:
                    //Если это первая итерация, добавляем элемент и переходим к следующему
                    if(retValue.size() == 0) {
                        retValue.push(token.clone());
                        continue;
                    }

                    //Если последняя команда не совпадает с текущей, значит мы закончили сжатие
                    if(retValue.peek().type != token.type) {
                        if(retValue.peek().arg == 0) //если в результате сжатия команда "исчезла"
                            retValue.pop(); //то просто убираем ее

                        if(retValue.peek().type == Opcode.Type.ZERO) //если это команда ZERO
                            retValue.peek().arg = 1; //то убираем возможные повторы, ибо они не имеют смысла

                        retValue.push(token.clone()); //добавляем текущую команду
                        continue;
                    }

                    //сюда мы попадет при условии, если команда дальше повторяется
                    //мы просто дополняем текущую команду вместо добавления новой
                    retValue.peek().arg += token.arg; 
                    break;

                case WHILE:
                case END:
                    //циклы объединять не надо
                    retValue.add(token.clone());
                    break;
            }
        }

        return retValue;
    }
}

Генератор байткода

Переходим к самой сложной и интересной части, к генерации байткода под Java VM. Разобраться в том, как надо генерировать байткод, нам помогут ранее установленные плагины для IDE. Приступим.

Для начала нам нужно выделить память под ленту и установить позицию. Просто создаем класс с методом без параметров и объявляем в нем массив и переменную для позиции.

//наш метод
public void test() {
    char[] arr = new char[30000];
    int i = 15000; //позиция
}

Теперь надо посмотреть байткод, который создаст компилятор Java из этого кода. Для этого нужно вызвать из контекстного меню редактора команду «Show Bytecode outline» (для IDEA так). Среда скомпилирует класс с нашим методом и покажет байткод. Находим наш метод и смотрим его.
Для более уверенного понимания результата, желательно посмотреть таблицу инструкций JVM.

  public test()V 
   //метка в байткоде, может применяться для прыжков или просто указания начала строки для отладчика (наш случай)
   L0 
    //информируем VM, что находимся на 5 строке и начинается она с метки L0
    LINENUMBER 5 L0 
    //добавляем в стек константу типа short с значением 30000
    SIPUSH 30000 
    //создаем массив типа T_CHAR и кладем указатель на него в стэк, кол-во берется из стэка (заодно удаляется)
    NEWARRAY T_CHAR 
    //записываем указатель из стэка в локальную переменную 1 (грубо говоря аналог регистров в JVM)
    ASTORE 1 
   L1 //еще метка
    LINENUMBER 6 L1 //строка 5 с метки L1
    SIPUSH 15000 //добавляем константу в стэк
    ISTORE 2 //записываем число типа integer в локальную переменную 2
   L2
    LINENUMBER 7 L2
    RETURN //вернуть пустой результат
   L3 //это смотреть нам не надо
    LOCALVARIABLE this LByteCodeTest; L0 L3 0
    LOCALVARIABLE arr [C L1 L3 1
    LOCALVARIABLE i I L2 L3 2
    MAXSTACK = 1
    MAXLOCALS = 3

Теперь мы имеем представление, как работает наш код на уровне байткода. Уберем метки, указание номера строки и все после return. Для корректной работы эта информация не нужна. В итоге получаем это:

//объявляем массив
SIPUSH 30000
NEWARRAY T_CHAR 
ASTORE 1 
//объявляем указатель
SIPUSH 15000
ISTORE 2
//выход
RETURN

Пока все более менее просто. В JVM большая часть операций после выполнения удаляет из стэка свои аргументы. Это очень удобно и не надо после подчищать. Теперь добавим в наш метод все операции, пока без циклов, в том числе и в вводе/выводе, которые мы описали в таблице.
Получится примерно такое:

public void test() throws IOException { //исключение от read()
    char[] arr = new char[30000];
    int i = 15000;

    i += 1111;

    arr[i] += 2222;

    arr[i] = 0;

    System.out.print(arr[i]);

    arr[i] = (char) System.in.read();
}

В данном случае смысл кода нам не важен, нам важно увидеть байткод операций.
Уберем лишние инструкции и посмотрим его:

public test()V throws java/io/IOException 
  //объявляем массив
  SIPUSH 30000
  NEWARRAY T_CHAR
  ASTORE 1

  //объявляем позицию
  SIPUSH 15000
  ISTORE 2

  //прибавим к позиции 1111
  IINC 2 1111

  //прибавим к ячейке число 2222
  ALOAD 1 //загружаем в стэк указатель на массив
  ILOAD 2 //загружаем в стэк позицию
  DUP2 //дублируем два последних значения в стэке
  CALOAD //загружаем элемент массива типа char в стэк, взяв в аргументы два последних значения стэка (такие же у CASTORE)
  SIPUSH 2222 //кладем в стэк константу 2222
  IADD //складываем два последних значения в стэке
  I2C //приводим значение стэка к типу char (все значения в стэке типа integer)
  CASTORE //сохраняем значение в массив

  //обнуляем ячейку
  ALOAD 1
  ILOAD 2
  ICONST_0 //специальная константа JVM для числа 0 (есть и другие)
  CASTORE //сохраняем значение в массив

  //вывод значения ячейки
  GETSTATIC java/lang/System.out : Ljava/io/PrintStream; //получаем значение (указатель на объект) статичного поля класса
  ALOAD 1
  ILOAD 2
  CALOAD //загружаем ячейку
  INVOKEVIRTUAL java/io/PrintStream.print (C)V //вызываем метод

  //ввод значения ячейки
  ALOAD 1
  ILOAD 2
  GETSTATIC java/lang/System.in : Ljava/io/InputStream; //получаем указатель 
  INVOKEVIRTUAL java/io/InputStream.read ()I //вызываем метод
  I2C
  CASTORE 

  //выход
  RETURN

Теперь у нас есть байткод всех нужных нам операций, для реализации генератора без циклов.
Хочу отметить, что инструкция I2C не требуется (выяснено опытным путем). Могу предположить, что размерность типа так же контролирует инструкция CALOAD и в итоге наличие I2C теряет смысл. Еще мы заменим инструкцию SIPUSH на LDC (добавить в стэк константу типа integer), ибо наш компилятор хранит повторения в integer (тип поля arg в классе Opcode).

Начнем генератор кода с того, что в Java все хранится в классах, поэтому во время генерации будет создавать именно класс. В библиотеке ASM есть замечательные средства для их генерации. Все сводится к простому построению дерева класса, с элементами вида полей, методов и вложенных классов. Методы же в себе хранят массивы инструкций JVM. Чтобы проще было понять, как работать с результатом компиляции, пусть наш класс будет унаследоваться от интерфейса Runnable.

Создадим пустой класс унаследованный от этого интерфейса:

public class ClassTest implements Runnable {
    @Override
    public void run() {

    }
}

И посмотрим байткод:

// class version 52.0 (52)
// access flags 0x21
public class ClassTest implements java/lang/Runnable  {
  // access flags 0x1
  public <init>()V
   L0
    LINENUMBER 3 L0
    ALOAD 0
    INVOKESPECIAL java/lang/Object.<init> ()V
    RETURN
   L1
    LOCALVARIABLE this LClassTest; L0 L1 0
    MAXSTACK = 1
    MAXLOCALS = 1

  // access flags 0x1
  public run()V
   L0
    LINENUMBER 7 L0
    RETURN
   L1
    LOCALVARIABLE this LClassTest; L0 L1 0
    MAXSTACK = 0
    MAXLOCALS = 1
}

Как видно, при генерации байткода, добавляется метод <init>, задача которого вызвать родительский конструктор. Этот момент надо учесть и не забыть добавить этот метод.

Для генерации класса существует класс ClassNode, а для методов MethodNode.
Генерировать наш пустой класс можно так (без учета меток и номеров строк):

ClassNode cn = new ClassNode();

cn.version = V1_8; //версия библеотеки ASM
cn.access = ACC_PUBLIC + ACC_SUPER; //класс публичный, что значит ACC_SUPER, могу лишь гадать
cn.name = "ClassTest"; //имя класса
cn.superName = "java/lang/Object"; //имя родительского класса
cn.interfaces.add("java/lang/Runnable"); //добавляем интерфейс

{
    //создаем метод public void <init>()
    MethodNode mn = new MethodNode(ACC_PUBLIC, "<init>", "()V", null, null);
    //список инструкий метода
    InsnList il = mn.instructions;

    //вызывем родительский конструктор
    //вполне видна взаимосвязь с байткодом JVM
    il.add(new VarInsnNode(ALOAD, 0)); 
    il.add(new MethodInsnNode(INVOKESPECIAL, cn.superName, "<init>", "()V", false));

    //выход
    il.add(new InsnNode(RETURN));

    //добавляем метод к классу
    cn.methods.add(mn);
}
{
    //создаем метод public void run()
    MethodNode mn = new MethodNode(ACC_PUBLIC, "run", "()V", null, null);
    //список инструкий метода
    InsnList il = mn.instructions;

    //выход
    il.add(new InsnNode(RETURN));

    //добавляем метод к классу
    cn.methods.add(mn);
}

//класс, который позволяет получить байткод
// параметр COMPUTE_FRAMES включает автоматический рассчет
// кол-во используемых локальных переменных и максимальный размер стэка (эта информация нужна для JVM)
// а так же рассчитывает прыжки по меткам
ClassWriter cw = new ClassWriter(ClassWriter.COMPUTE_FRAMES);

//связываем ClassNode с ClassWriter
cn.accept(cw);

cw.toByteArray(); //получаем байткод

Теперь задача состоит в том, чтобы реализовать добавление инструкций в метод run из массива c операциями Brainfuck. Сделаем это через обычный switch.

//можем произвольно указывать имя класса и размер памяти
//в классе метода есть поле opcodes, где лежит массив операций Brainfuck
public byte[] toByteCode(String className, int memorySize){
        // ......................  

        MethodNode mn = new MethodNode(ACC_PUBLIC, "run", "()V", null, null);
        InsnList il = mn.instructions;

        //объявляем массив размером memorySize
        il.add(new LdcInsnNode(memorySize)); //заносим в стэк константу типа integer
        il.add(new IntInsnNode(NEWARRAY, T_CHAR)); //создаем массив
        il.add(new VarInsnNode(ASTORE, 1)); //кладем его в локальную переменную 1

        //объявляем позицию
        il.add(new LdcInsnNode(memorySize / 2)); 
        il.add(new VarInsnNode(ISTORE, 2)); //кладем его в локальную переменную 2

        //идем по массиву операций
        for (Opcode opcode : opcodes) {
            switch (opcode.type) {
                case SHIFT: //операция сдвига по позиции на opcode.arg                   
                    il.add(new IincInsnNode(2, opcode.arg));
                    break;
                case ADD: //операция прибавления opcode.arg к ячейке
                    il.add(new VarInsnNode(ALOAD, 1));
                    il.add(new VarInsnNode(ILOAD, 2));
                    il.add(new InsnNode(DUP2));
                    il.add(new InsnNode(CALOAD));
                    il.add(new LdcInsnNode(opcode.arg));
                    il.add(new InsnNode(IADD));
                    il.add(new InsnNode(CASTORE));

                    break;
                case ZERO: //обнуление ячейки
                    il.add(new VarInsnNode(ALOAD, 1));
                    il.add(new VarInsnNode(ILOAD, 2));
                    il.add(new InsnNode(ICONST_0));
                    il.add(new InsnNode(CASTORE));

                    break;
                case OUT: //выводим ячейку opcode.arg раз
                    for (int i = 0; i < opcode.arg;+i) {
                        il.add(new VarInsnNode(ALOAD, 0));
                        il.add(new FieldInsnNode(GETFIELD, cn.name, "out", "Ljava/io/PrintStream;"));
                        il.add(new VarInsnNode(ALOAD, 1));
                        il.add(new VarInsnNode(ILOAD, 2));
                        il.add(new InsnNode(CALOAD));
                        il.add(new MethodInsnNode(INVOKEVIRTUAL, "java/io/PrintStream", "print", "(C)V", false));
                    }

                    break;
                case IN: //вводим ячейку opcode.arg раз
                    for (int i = 0; i < opcode.arg;+i) {
                        il.add(new VarInsnNode(ALOAD, 1));
                        il.add(new VarInsnNode(ILOAD, 2));
                        il.add(new VarInsnNode(ALOAD, 0));
                        il.add(new FieldInsnNode(GETSTATIC, cn.name, "in", "Ljava/io/InputStream;"));
                        il.add(new MethodInsnNode(INVOKEVIRTUAL, "java/io/InputStream", "read", "()I", false));
                        il.add(new InsnNode(CASTORE));
                    }

                    break;
                case WHILE:
                    break;
                case END:
                    break;
            }
        }

        // ......................
}

Осталось решить проблему с циклами. Снова прибегнем к просмотру байткода тестового метода:

public void test() {
    char[] arr = new char[30000];
    int i = 15000; //позиция

    while(arr[i] != 0) {
        i += 10000000;
    }
}

Вот его байт код:

public test()V
   L0
    LINENUMBER 6 L0
    SIPUSH 30000
    NEWARRAY T_CHAR
    ASTORE 1
   L1
    LINENUMBER 7 L1
    SIPUSH 15000
    ISTORE 2
   L2
    LINENUMBER 9 L2
   FRAME APPEND [[C I] //ненужный байткод
    //читаем значение ячейки
    ALOAD 1
    ILOAD 2
    CALOAD
    IFEQ L3 //если оно равно нулю, то прыгаем к метке L3 (конец цикла)
   L4
    LINENUMBER 10 L4

    //тело цикла
    ILOAD 2
    LDC 10000000
    IADD
    ISTORE 2

    //перед самым концом цикла прыгаем к L2 (начало цикла - проверка условия)
    GOTO L2 
   L3
    LINENUMBER 12 L3
   //FRAME SAME //снова ненужный байткод 
    RETURN

В итоге для циклов нам надо всего лишь правильно расставить метки и прыжки для них.
Для меток есть класс LabelNode, по сути сам объект есть метка. Куда его вставили среди инструкций, туда мы и прыгнем.
Для прыжка используем класс JumpInsnNode. Первый аргумент указывает тип прыжка (безусловный или какой-либо из условных) и второй аргумент сама метка, куда будет совершен прыжок.
Для распределения меток с учетом вложенности, воспользуемся стэком. Т.е. встретили начало цикла, сохранили метку в стэк, встретили конец, вытащили метку и прописали прыжки.
Вот он результат:

		//стэк
		Stack<LabelNode> lbls = new Stack<LabelNode>();
		MethodNode mn = new MethodNode(ACC_PUBLIC, "run", "()V", null, null);

		// ......................		

		for (Opcode opcode : opcodes) {
			switch (opcode.type) {
				// ........................

				case WHILE:
					//создаем сразу метки начала и конца
					LabelNode
							begin = new LabelNode(),
							end = new LabelNode();
					
					//кладем их в стэк
					lbls.push(end);
					lbls.push(begin);

					//указываем начало
					il.add(begin);
					//проверяем условие
					il.add(new VarInsnNode(ALOAD, 1));
					il.add(new VarInsnNode(ILOAD, 2));
					il.add(new InsnNode(CALOAD));
					il.add(new JumpInsnNode(IFEQ, end)); //прыгаем в конец при условии, что значение равно нулю
					break;
				case END:
					//прыгаем в начало
					il.add(new JumpInsnNode(GOTO, lbls.pop()));
					//прописываем конец
					il.add(lbls.pop());
					break;
			}
		}

Выполнение байткода

Теперь все это дело нужно как то запустить, но сначала загрузим этот класс. К сожалению Java не предоставляет штатного API для этих целей, поэтому прибегнем к вот таким вот костылям (куда же без них):

public class ByteCodeLoader extends ClassLoader {
    public static final ByteCodeLoader clazz = new ByteCodeLoader();

    public Class<?> loadClass(byte[] bytecode) {
        return defineClass(null, bytecode, 0, bytecode.length);
    }
}

А сама загрузка и запуск будет выглядеть вот так:

Class<?> aClass = ByteCodeLoader.clazz.loadClass( //загружаем байткод и получем класс
        toByteCode( //получаем байткод
                "BrainFuckJit", //имя
                30000 //объем памяти
        )
);
        
((Runnable)aClass.newInstance()).run(); //создаем класс и запускаем

Тесты производительности

Интересно будет узнать, насколько же шустрый вариант у нас получился. Для этого есть специальная программа на Brainfuck, которая имеет много вложенных циклов и хороша для тестирования производительности.

>+>+>+>+>++<[>[<+++>-
 >>>>>
 >+>+>+>+>++<[>[<+++>-
   >>>>>
   >+>+>+>+>++<[>[<+++>-
     >>>>>
     >+>+>+>+>++<[>[<+++>-
       >>>>>
       +++[->+++++<]>[-]<
       <<<<<
     ]<<]>[-]
     <<<<<
   ]<<]>[-]
   <<<<<
 ]<<]>[-]
 <<<<<
]<<]>.

Данный код так же подходит для теста работоспособности компилятора, в конце программы выводится символ с кодом 202, если это так, значит все в порядке.
Проведем 6 тестов. Проверим обычный интерпретатор Brainfuck, компилятор под JVM и компиляцию в VC++. Каждый тест будет проверяться с оптимизацией и без (у Brainfuck).

Результаты теста (меньше — лучше):

Как видно, наши старания прошли не зря. JIT компиляция в Java VM сделала свое дело и довела производительность до уровня нативного исполнения.

Заключение

Java VM является весьма удобной платформой для реализации своих языков. VM с продуманным набором инструкций и удобное API позволяют в довольно краткие сроки написать свой язык.
Хотя отсутствие простых и понятных туториалов по ASM поначалу усложняет понимание того, как работает библиотека и способно навести вас на различные древние грабли, в то время как сама библиотека предлагает элегантные решения.
И целью данной статьи было восполнить данный пробел и дать возможность как можно быстрее начать творить.
Надеюсь мне это удалось.

Спасибо за внимание!

Автор: SystemXFiles

Источник