Geekly Articles each Day

JBrainfuck-Java VM用のBrainfuckコンパイラの作成

Java VM用のコンパイラーを作成する問題に長い間興味がありましたが、これを行うには十分な経験がありませんでした。 はい、どういうわけか私の手は届きませんでしたが、最近、このトピックを理解すると同時に、このVMのコンパイラを作成した経験について話すことにしました。

実装言語としてBrainfuckを使用してください。 実装は簡単です。これはこのトピックを調査するのに最適ですが、最初に実装を紹介します。

JBrainfuckは、Java VM用の最適化Brainfuckインタープリターおよびコンパイラーです。 JITのおかげで、高いパフォーマンスが得られます。



開発ツールの選択


明らかな解決策は、Javaでコンパイラーを作成することです。
バイトコードを生成するには、 ASMライブラリを使用します。 Groovy、JRubyなどの一般的な言語で使用されます。
JVMバイトコードを簡単に監視するには、IDEにプラグインをインストールします。



作成を開始


私たちが実装しているBrainfuck言語を知っている人は多いと思います。 それはたった8つの単純なコマンドで構成されていますが、それでもチューリングは完全であり、OS（ 神は禁じられています ）でさえ、この言語で何でも実装できます。
その本質はシンプルです。 左右に移動したり、セルの値を増減することでセルの値を変更できるメモリテープがあります。

これらのコマンドのリストは次のとおりです。
Brainfuckチーム同等のJava説明
開始する
プログラム
char[] arr = new char[30000]; int i = 15000;
テープにメモリを割り当てます
真ん中に位置を置きます
<
 i--;
左にスキップ
>
 i++;
右にスキップ
+
 arr[i]++;
現在のセルに1を追加
-
 arr[i]--;
現在のセルから1を引く
。
 System.out.print(arr[i]);
現在のセル値を印刷
、
 arr[i] = (char)System.in.read();
現在のセルの値を入力してください
[
 while(arr[i] != 0) {
値がゼロ以外になるまでサイクルで作業します
]
 }
サイクルの先頭に移動します
「Hello、Habr！」を出力するBrainfuckプログラムの例：
コード
 ++++++++[>+>++>+++>++++>+++++>++++++>+++++++>++++++++> +++++++++>++++++++++>+++++++++++>++++++++++++>++++++++ +++++>++++++++++++++>+++++++++++++++>++++++++++++++++< <<<<<<<<<<<<<<<-]>>>>>>>>>.<<<<<<<<<>>>>>>>>>>>>>---.+ ++<<<<<<<<<<<<<>>>>>>>>>>>>>>----.++++<<<<<<<<<<<<<<>> >>>>>>>>>>>>----.++++<<<<<<<<<<<<<<>>>>>>>>>>>>>>-.+<< <<<<<<<<<<<<>>>>>>----.++++<<<<<<>>>>.<<<<>>>>>>>>>.<< <<<<<<<>>>>>>>>>>>>+.-<<<<<<<<<<<<>>>>>>>>>>>>++.--<<< <<<<<<<<<>>>>>>>>>>>>>>++.--<<<<<<<<<<<<<<>>>>+.-<<<<.

コンパイラを書く

すべての規則に従ってコンパイラーを作成するため、コンパイラーには、字句解析、最適化、バイトコード生成の3つのコンパイル段階があります。
まず、可能な最適化を検討する価値があります。これにより、コンパイラの設計がより便利であることがわかります。

最適化

おそらく最初に目を引くのは、同じ種類の操作です。 もちろん、すべてを圧縮し、一連の操作を#~の形式に減らすという考えがすぐに生まれます。ここで、 ＃は操作の数で、 〜は操作です。
また、 [-]または[+]という形式のコードはセルのゼロ化であるため、このために別の操作を選択することは理にかなっています。

演算の数を減らすという考えをさらに進めると、加算/減算演算は同等であり、数の符号のみが異なることが理解できます。 したがって、それらを1つの操作に導くことができます。 同じことが左/右に移動する操作にも有効です。

すべての最適化の後、新しい操作テーブルを作成します。 そのすぐ下でコンパイラーを実行します。
運営Javaアナログ説明
SHIFT（引数）
 i += arg;
テープシフト
ADD（引数）
 arr[i] += arg;
加算（負の数による減算）
ゼロ
 arr[i] = 0;
ゼロ調整
OUT（引数）
 while(arg --> 0) System.out.print(arr[i]);
セル引数時間を印刷
IN（引数）
 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コードで発生する可能性のあるトークンを強調表示します。
トークン運営
<-でシフト
>SHIFT +
++追加
--で追加
.アウト
,で
[ながら
]終了
[-]または[+]ゼロ

そして、これらのトークンのシーケンスを選択するアナライザーを作成します。
コード
 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

これで、コードがバイトコードレベルでどのように機能するかがわかりました。 ラベル、行番号、および返却後のすべてを削除します。 この情報は、正しい操作には必要ありません。 その結果、次のようになります。

 //  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の存在はその意味を失うと想定できます。 また、コンパイラーは繰り返しを整数（ Opcodeクラスのargフィールドの型）に格納するため、 SIPUSH命令をLDC置き換えます（整数型の定数をスタックに追加します）。

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(); //

ここでのタスクは、Brainfuck操作を使用して、配列からrunメソッドに命令を追加することです。 通常の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 [[CI] //  //   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

その結果、ループの場合、ラベルとトランジションを正しく配置するだけで済みます。
labelsにはLabelNodeクラスがあり、実際にはオブジェクト自体がラベルです。 指示の中に挿入した場所に行きます。
ジャンプするには、 JumpInsnNodeクラスを使用します。 最初の引数は遷移のタイプ（無条件または条件付きのいずれか）を示し、2番目の引数は遷移が行われるラベル自体です。
ネストを考慮してラベルを配布するには、スタックを使用します。 つまり ループの始まりに会い、ラベルをスタックに保存し、終わりに会い、ラベルを引き出し、トランジションを登録しました。
結果は次のとおりです。

  // 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を使用して）テストされます。

テスト結果（少ないほど良い）：


ご覧のとおり、私たちの努力は無駄ではありませんでした。 Java VMでのJITコンパイルはその役割を果たし、パフォーマンスをネイティブ実行のレベルに引き上げました。

おわりに


Java VMは、言語を実装するための非常に便利なプラットフォームです。 よく考えられた一連の命令と便利なAPIを備えたVMを使用すると、ごく短時間で独自の言語を作成できます。
シンプルで理解しやすいASMチュートリアルがないため、最初はライブラリの仕組みを理解するのが難しくなり、さまざまな古代の奇跡につながる可能性がありますが、ライブラリ自体はエレガントなソリューションを提供します。
この記事の目的は、このギャップを埋め、できるだけ早く作成を開始する機会を与えることでした。
私は成功したと思います。

ご清聴ありがとうございました！

Source: https://habr.com/ru/post/J229267/

More articles:


All Articles