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