PHPで作る簡単なLLVMコンパイラ

パーサコンビネータを作ってパースして、LLVMコードに変換し、ファイルに出力して、llc,llvm-gccでコンパイルし、実行します。

パーサコンビネータを作るにはkmizuさんの記事を参考にしました。
コンパイルの処理は、MinCamlやきつねさんのLLVMの本等を参考にしてます。
caseClassはScalaを参考にしてます。
リフレクションを使ったVisitorパターンの元々のアイディアは、普通のコンパイラの作り方を参考にしています。

<?php
namespace {

class testLLVM {

    public static function main() {

        // プログラムの抽象構文木
        /*
        $ast = EBlock(Tv(), Array(
            EPrint(Ti(32), ELdc(Ti(32), 11)),
            EPrint(Ti(32), EAdd(Ti(32), ELdc(Ti(32), 11), ELdc(Ti(32), 22)))
        ));
        */
        $result = PEG\expr("{print_i(11) print_i(1+3*3*11)}");
        if ($result->value==null) {
            throw new Exception("syntax error." . $result->rest);
        }
        $ast = $result->value;
        // ASTをLLVMのアセンブラに変換
        //println("ast=", "".$ast);
        $ll = kNormal($ast);

        // LLVMのアセンブラをファイルに出力
        //println("ll=", $ll);
        emit("e.ll", $ll);

        // アセンブラに変換
        list($stdout,$stderr,$code) = exe("llc e.ll -o e.s");
        echo $stdout;
        if($code != 0) {
            throw new Exception("error code ".$code." ".$stderr);
        }
        // アセンブラをコンパイル
        list($stdout,$stderr,$code) = exe("llvm-gcc -m64 e.s -o e");
        echo $stdout;
        if($code != 0) {
            throw new Exception("error code ".$code." ".$stderr);
        }
        // 実行 11と33が出力される
        system("./e");
    }
}

/**
 * 文字列出力
 *
 * カンマ区切りで出力可能で、var_exportで出力し最後に改行を出力
 */
function println() {
    foreach(func_get_args() as $s) {
        var_export($s); 
    }
    echo "\n";
}

/**
 * 一意なIDの作成
 *
 * @param string $s 文字列
 */
function genid($s) {
    static $id = 0;
    $id += 1;
    return $s . $id;
}

/**
 * ファイルに文字列出力
 */
function asm($s) {
    fwrite(asm::$fp, $s."\n");
}

class asm {

    public static $fp = null;

    /**
     * ファイルオープン
     */
    public static function open($filename) {
        self::$fp = fopen($filename,"w");
    }

    /**
     * ネストした文字列出力
     */
    public static function _($s) {
        fwrite(asm::$fp, "  ".$s."\n");
    }

    /**
     * レジスタ有無で、出力を変更する出力関数
     * 
     * @param R $id レジスタ
     * @param string $out 出力文字列
     */
    public static function r($r, $out) {

        if ($r !== null) {
            asm::_(emit::visit($r) . " = " . $out);
        } else {
            asm::_($out);
        }

    }

    /**
     * ファイルクローズ
     */
    public static function close() {
        fclose(self::$fp);
        self::$fp = null;
    }
}

/**
 * プロセス実行
 *
 * @param string $cmd コマンド文字列 
 * @return array(標準出力, 標準Error, リターン値)
 */
function exe($cmd) {
    $desc = array(
        "0"=>array("pipe", "r"),
        "1"=>array("pipe", "w"),
        "2"=>array("pipe", "w"),
    );

    $process = proc_open($cmd, $desc, $pipes);

    if (is_resource($process)) {
        $results = array();
        $results[] = stream_get_contents($pipes[1]);
        $results[] = stream_get_contents($pipes[2]);
        fclose($pipes[0]);
        fclose($pipes[1]);
        fclose($pipes[2]);

        $results[] = proc_close($process);
        return $results;
    }
    return array("","",-1);
}

// 黒魔術

/**
 * クラスの自動生成
 */
function caseClass() {
    $args = func_get_args();
    $name = array_shift($args);
    $args2 = array_map(function($e){return '$'.$e;},$args);
    $args3 = array_map(function($e){return '$this->'.$e;},$args);
    ob_start();
    ?>

    class <?php echo $name?> {

        public function __construct(<?php echo implode(",", $args2) ?>) {
            <?php foreach($args as $v) { ?>
                $this-><?php echo $v ?> = $<?php echo $v ?>;
            <?php } ?>
        }

        public function __toString() {
            <?php if (count($args3)) { ?>
                return "<?php echo $name?>(".<?php echo implode('.",".', $args3) ?>.")";
            <?php } else { ?>
                return "<?php echo $name?>()";
            <?php } ?>
        }

    }

    function <?php echo $name?> (<?php echo implode(",", $args2) ?>) {
        return new <?php echo $name?>(<?php echo implode(",", $args2) ?>);
    }

    <?php
    $contents = ob_get_contents();
    ob_end_clean();
    echo eval($contents);
}

/**
 * パターンマッチ的なVisitor
 */
class Visitor {
    public static function __callStatic($name,$args) {

        $class = $name."_".get_class($args[0]);
        if(!method_exists(get_called_class(), $class)) {
            throw new Exception("undefined method ".$class."::".get_called_class());
        }
        return call_user_func_array(array(get_called_class(), $class), array_merge($args,array_values((Array)$args[0])));
    }
}

// AST

// 式
caseClass("ELdc","t","l"); // 値
caseClass("EBin","t","op","l","r"); // 2項演算子
caseClass("EPrint","t", "l"); // print
caseClass("EBlock","t", "ls"); // ブロック

// 足し算
function EAdd($t,$l,$r) {
    return new EBin($t,"add",$l,$r);
}

// かけ算
function EMul($t,$l,$r) {
    return new EBin($t,"mul",$l,$r);
}

// 型
caseClass("Ti","i");
caseClass("Tv");
caseClass("TFun","t","prms");

// レジスタ
caseClass("RG","t","id");
caseClass("RL","t","id");
caseClass("RR","t","id");
caseClass("RN","t","id");

// LLVMアセンブラ
caseClass("LLCall", "id", "op", "prms");
caseClass("LLBin", "id", "op", "a", "b");


// E -> LL へ変換する
function kNormal($a) {
    kNormal::$outputList = array();
    kNormal::visit($a);
    return kNormal::$outputList;
}

class kNormal extends Visitor {

    /**
     * ローカルなレジストリ作成
     */
    public static function genReg($t) {
        return RR($t, genid(""));
    }

    public static $outputList = array();

    public static function add($l) {
        self::$outputList[] = $l;
    }

    public static function visit_EBin($e, $t, $op, $a, $b) {

        $a = self::visit($a);
        $b = self::visit($b);
        $id = self::genReg($t);

        if ($t != $a->t || $t != $b->t) {
            throw new Exception("type mismatch " . $t);
        }

        self::add(LLBin($id, $op, $a, $b));

        return $id;
    }

    public static function visit_ELdc($e, $t, $i) {
        return RN($t, "".$i);
    }

    public static function visit_EPrint($e, $t, $a) {

        $a = self::visit($a);

        if ($t != $a->t) {
            throw new Exception("type mismatch t=" . $t . " ta=" . $a->t);
        }

        self::add(LLCall(null, RG(TFun(Tv(), Array($t)), "print_" . emit::visit($t)), Array($a)));

        return $a;
    }

    public static function visit_EBlock($e, $t, $ls) {

        $result = null;

        foreach($ls as $l) {
            $result = self::visit($l);
        }

        return $result;
    }
}

/**
 * LLのarrayをファイルに出力する
 * 
 * @param string $file ファイル名
 * @param array $ls LLのリスト
 */
function emit($file, $ls) {
    return emit::apply($file, $ls);
}

class emit extends Visitor {

    /**
     * 文字列化処理
     * @param $node 文字列化したい要素
     * @param ... 各オブジェクトの要素
     */
    // function visit($node);

    public static function visit_Ti($node, $i) {
        return "i" . $i;
    }

    public static function visit_Tv($node) {
        return "void";
    }

    public static function visit_TFun($node, $t, $ls) {

        $paramList = array();

        foreach($ls as $l) {
            $paramList[] .= self::visit($l);
        }

        return self::visit($t) . "(" . implode(", ", $paramList) . ")*";
    }

    public static function visit_RG($node, $t, $id) {
        return "@" . $id;
    }

    public static function visit_RL($node, $t, $id) {
        return "%" . $id;
    }

    public static function visit_RR($node, $t, $id) {
        return "%.". $id;
    }

    public static function visit_RN($node, $t, $id) {
        return "" . $id;
    }

    public static function visit_LLCall($node, $id, $op, $prms) {

        $ps = array();

        foreach($prms as $l) {
            $ps[] = emit::visit($l->t) . " " . emit::visit($l);
        };

        asm::r($id, "call " . self::visit($op->t) . " " . self::visit($op) . "(" . implode(", ", $ps) . ") nounwind");
    }

    public static function visit_LLBin($node, $id, $op, $a, $b) {
        asm::r($id, $op . " " . self::visit($id->t) . " " . self::visit($a) . ", " . self::visit($b));
    }

    public static function apply($file, $ls) {

        asm::open($file);

        asm("@.str = private constant [4 x i8] c\"%d\\0A\\00\"");

        asm("define void @print_i32(i32 %a) nounwind ssp {");
        asm("entry:");
        asm::_("call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([4 x i8]* @.str, i64 0, i64 0), i32 %a) nounwind");
        asm::_("ret void");
        asm("}");

        asm("define void @print_i8(i8 %a) nounwind ssp {");
        asm("entry:");
        asm::_("call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([4 x i8]* @.str, i64 0, i64 0), i8 %a) nounwind");
        asm::_("ret void");
        asm("}");

        asm("declare i32 @printf(i8*, ...) nounwind");

        asm("define i32 @main() nounwind ssp {");
        asm("entry:");

        foreach($ls as $l) self::visit($l);

        asm::_("ret i32 0");
        asm("}");

        asm::close();
    }
}


}

namespace PEG {
    $lastInput = "";
    class PEGResult {
      function __construct($value, $rest) {
        $this->value = $value;
        $this->rest = $rest;
      }

      function __toString() {
        return "PEGResult(".$this->value.", ".$this->rest.")";
      }
    }

    function proxy() {
        $p = null;
        return function($input,$f=null)use(&$p){
            if($f!==null) {
                $p = $f;
                return;
            }
            return $p($input);
        };
    }

    function string($param) {
        return function($input)use($param) {
            $input = preg_replace("/^[ \\r\\n\\t]*/", "", $input);
            if($param=="" || strpos($input, $param)===0) {
                global $lastInput;
                return new PEGResult($param, $lastInput = substr($input, strlen($param)));
            }
            return new PEGResult(null, $input);
        };
    }

    function reg($param) {
        $param = "/^".$param."/";
        return function($input)use($param) {
            $input = preg_replace("/^[ \\r\\n\\t]*/", "", $input);
            if(preg_match($param, $input, $m) > 0) {
                global $lastInput;
                return new PEGResult("".$m[0], $lastInput = substr($input, strlen("".$m[0])));
            }
            return new PEGResult(null, $input);
        };
    }

    function any() {
        return function($input) {
            $input = preg_replace("/^[ \\r\\n\\t]*/", "", $input);
            if(strlen($input) > 0) {
                global $lastInput;
                return new PEGResult(substr($input, 0, 1), $lastInput = substr($input, 1));
            }
            return new PEGResult(null, $input);
        };
    }

    function alt() {
        $ps = func_get_args();
        return function($input)use($ps) {
            $r = new PEGResult(null, $input);
            foreach ($ps as $p) {
                $r = $p($input);
                if($r->value !== null) return $r;
            }
            return $r;
        };
    }

    function seq() {
        return seqN(func_get_args());
    }

    function seqN($ps) {
        return function($input)use($ps) {
            $rs = array();
            foreach ($ps as $p) {
                $r = $p($input);
                if($r->value === null) return $r;
                $rs[] = $r->value;
                $input = $r->rest;
            }
            return new PEGResult($rs, $input);
        };
    }

    function not($p) {
        return function($input)use($p) {
            $r = $p($input);
            if($r->value === null) return new PEGResult("not", $input);
            return new PEGResult(null, $input);
        };
    }

    function opt($p) {
        return alt(
            $p, apply(string(""), function ($param) { return new PEGResult(null, $param); })
        );
    }

    function rep($p) {
        return function($input)use($p) {
            $rs = array();
            while(true) {
                $r = $p($input);
                if($r->value === null) break;
                $rs[] = $r->value;
                $input = $r->rest;
            }
            return new PEGResult($rs, $input);
        };
    }

    function rep1($p) {
        return apply(seq($p, rep($p)), function($param) {
            return array_unsift($param[0], $param[1]);
        });
    }

    function apply($p, $t) {
        return function($input) use($p, $t) {
            $r = $p($input);
            if($r->value === null) return $r;
            return new PEGResult($t($r->value), $r->rest);
        };
    }

    function expr($input) {
        global $lastInput;
        $lastInput = $input;
        static $expr = null;

        if ($expr == null) {
            $expr = proxy();
            $num = apply(reg("[1-9][0-9]*"),function($e){return ELdc(Ti(32), $e);});
            $id = reg("[a-zA-Z_][a-zA-Z_0-9]*");
            $print_i = apply(seq(string("print_i"),string("("),$expr,string(")")),function($ls){return EPrint(Ti(32),$ls[2]);});
            $block = apply(seq(string("{"), rep($expr), string("}")), function($ls) {return EBlock(Tv(),$ls[1]);});
            $fact = alt($print_i, $block, $num,$id,seq(string("("),$expr,string(")")));
            $term = apply(seq($fact,rep(seq(alt(string("*"),string("/")),$fact))),function($ls){
                $ops = array("*"=>"mul","/"=>"div");
                return array_reduce($ls[1], function($r,$l)use($ops) { return EBin(Ti(32),$ops[$l[0]],$r, $l[1]); }, $ls[0]);
            });
            $expr(null, apply(seq($term,rep(seq(alt(string("+"),string("-")),$term))),function($ls){
                $ops = array("+"=>"add","-"=>"sub");
                return array_reduce($ls[1], function($r,$l)use($ops) { return EBin(Ti(32),$ops[$l[0]],$r, $l[1]); }, $ls[0]);
            }));
        }
        $result = $expr($input);
        if($result->value==null) {
            $result->rest = "error pos=".(strlen($input) - strlen($lastInput));
        }
        return $result;
    }
}

namespace
{
    testLLVM::main();
}