diff -r 022e2cb1668d -r 5d860ff01938 progs/fun/fun_llvm.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/fun/fun_llvm.scala Sat Jul 04 22:12:18 2020 +0100 @@ -0,0 +1,290 @@ +// A Small LLVM Compiler for a Simple Functional Language +// (includes an external lexer and parser) +// +// call with +// +// scala fun_llvm.scala fact +// +// scala fun_llvm.scala defs +// +// this will generate a .ll file. You can interpret this file +// using lli. +// +// The optimiser can be invoked as +// +// opt -O1 -S in_file.ll > out_file.ll +// opt -O3 -S in_file.ll > out_file.ll +// +// The code produced for the various architectures can be obtains with +// +// llc -march=x86 -filetype=asm in_file.ll -o - +// llc -march=arm -filetype=asm in_file.ll -o - +// +// Producing an executable can be achieved by +// +// llc -filetype=obj in_file.ll +// gcc in_file.o -o a.out +// ./a.out + + + +object Compiler { + +import java.io._ +import scala.util._ +import scala.sys.process._ + +// Abstract syntax trees for the Fun language +abstract class Exp extends Serializable +abstract class BExp extends Serializable +abstract class Decl extends Serializable + +case class Def(name: String, args: List[String], body: Exp) extends Decl +case class Main(e: Exp) extends Decl + +case class Call(name: String, args: List[Exp]) extends Exp +case class If(a: BExp, e1: Exp, e2: Exp) extends Exp +case class Write(e: Exp) extends Exp +case class Var(s: String) extends Exp +case class Num(i: Int) extends Exp +case class Aop(o: String, a1: Exp, a2: Exp) extends Exp +case class Sequence(e1: Exp, e2: Exp) extends Exp +case class Bop(o: String, a1: Exp, a2: Exp) extends BExp + + +// for generating new labels +var counter = -1 + +def Fresh(x: String) = { + counter += 1 + x ++ "_" ++ counter.toString() +} + +// Internal CPS language for FUN +abstract class KExp +abstract class KVal + +case class KVar(s: String) extends KVal +case class KNum(i: Int) extends KVal +case class Kop(o: String, v1: KVal, v2: KVal) extends KVal +case class KCall(o: String, vrs: List[KVal]) extends KVal +case class KWrite(v: KVal) extends KVal + +case class KIf(x1: String, e1: KExp, e2: KExp) extends KExp { + override def toString = s"KIf $x1\nIF\n$e1\nELSE\n$e2" +} +case class KLet(x: String, e1: KVal, e2: KExp) extends KExp { + override def toString = s"let $x = $e1 in \n$e2" +} +case class KReturn(v: KVal) extends KExp + + +// CPS translation from Exps to KExps using a +// continuation k. +def CPS(e: Exp)(k: KVal => KExp) : KExp = e match { + case Var(s) => k(KVar(s)) + case Num(i) => k(KNum(i)) + case Aop(o, e1, e2) => { + val z = Fresh("tmp") + CPS(e1)(y1 => + CPS(e2)(y2 => KLet(z, Kop(o, y1, y2), k(KVar(z))))) + } + case If(Bop(o, b1, b2), e1, e2) => { + val z = Fresh("tmp") + CPS(b1)(y1 => + CPS(b2)(y2 => + KLet(z, Kop(o, y1, y2), KIf(z, CPS(e1)(k), CPS(e2)(k))))) + } + case Call(name, args) => { + def aux(args: List[Exp], vs: List[KVal]) : KExp = args match { + case Nil => { + val z = Fresh("tmp") + KLet(z, KCall(name, vs), k(KVar(z))) + } + case e::es => CPS(e)(y => aux(es, vs ::: List(y))) + } + aux(args, Nil) + } + case Sequence(e1, e2) => + CPS(e1)(_ => CPS(e2)(y2 => k(y2))) + case Write(e) => { + val z = Fresh("tmp") + CPS(e)(y => KLet(z, KWrite(y), k(KVar(z)))) + } +} + +//initial continuation +def CPSi(e: Exp) = CPS(e)(KReturn) + +// some testcases +val e1 = Aop("*", Var("a"), Num(3)) +CPSi(e1) + +val e2 = Aop("+", Aop("*", Var("a"), Num(3)), Num(4)) +CPSi(e2) + +val e3 = Aop("+", Num(2), Aop("*", Var("a"), Num(3))) +CPSi(e3) + +val e4 = Aop("+", Aop("-", Num(1), Num(2)), Aop("*", Var("a"), Num(3))) +CPSi(e4) + +val e5 = If(Bop("==", Num(1), Num(1)), Num(3), Num(4)) +CPSi(e5) + +val e6 = If(Bop("!=", Num(10), Num(10)), e5, Num(40)) +CPSi(e6) + +val e7 = Call("foo", List(Num(3))) +CPSi(e7) + +val e8 = Call("foo", List(Aop("*", Num(3), Num(1)), Num(4), Aop("+", Num(5), Num(6)))) +CPSi(e8) + +val e9 = Sequence(Aop("*", Var("a"), Num(3)), Aop("+", Var("b"), Num(6))) +CPSi(e9) + +val e = Aop("*", Aop("+", Num(1), Call("foo", List(Var("a"), Num(3)))), Num(4)) +CPSi(e) + + + + +// convenient string interpolations +// for instructions, labels and methods +import scala.language.implicitConversions +import scala.language.reflectiveCalls + +implicit def sring_inters(sc: StringContext) = new { + def i(args: Any*): String = " " ++ sc.s(args:_*) ++ "\n" + def l(args: Any*): String = sc.s(args:_*) ++ ":\n" + def m(args: Any*): String = sc.s(args:_*) ++ "\n" +} + +// mathematical and boolean operations +def compile_op(op: String) = op match { + case "+" => "add i32 " + case "*" => "mul i32 " + case "-" => "sub i32 " + case "/" => "sdiv i32 " + case "%" => "srem i32 " + case "==" => "icmp eq i32 " + case "<=" => "icmp sle i32 " // signed less or equal + case "<" => "icmp slt i32 " // signed less than +} + +def compile_val(v: KVal) : String = v match { + case KNum(i) => s"$i" + case KVar(s) => s"%$s" + case Kop(op, x1, x2) => + s"${compile_op(op)} ${compile_val(x1)}, ${compile_val(x2)}" + case KCall(x1, args) => + s"call i32 @$x1 (${args.map(compile_val).mkString("i32 ", ", i32 ", "")})" + case KWrite(x1) => + s"call i32 @printInt (i32 ${compile_val(x1)})" +} + +// compile K expressions +def compile_exp(a: KExp) : String = a match { + case KReturn(v) => + i"ret i32 ${compile_val(v)}" + case KLet(x: String, v: KVal, e: KExp) => + i"%$x = ${compile_val(v)}" ++ compile_exp(e) + case KIf(x, e1, e2) => { + val if_br = Fresh("if_branch") + val else_br = Fresh("else_branch") + i"br i1 %$x, label %$if_br, label %$else_br" ++ + l"\n$if_br" ++ + compile_exp(e1) ++ + l"\n$else_br" ++ + compile_exp(e2) + } +} + + +val prelude = """ +@.str = private constant [4 x i8] c"%d\0A\00" + +declare i32 @printf(i8*, ...) + +define i32 @printInt(i32 %x) { + %t0 = getelementptr [4 x i8], [4 x i8]* @.str, i32 0, i32 0 + call i32 (i8*, ...) @printf(i8* %t0, i32 %x) + ret i32 %x +} + +""" + + +// compile function for declarations and main +def compile_decl(d: Decl) : String = d match { + case Def(name, args, body) => { + m"define i32 @$name (${args.mkString("i32 %", ", i32 %", "")}) {" ++ + compile_exp(CPSi(body)) ++ + m"}\n" + } + case Main(body) => { + m"define i32 @main() {" ++ + compile_exp(CPSi(body)) ++ + m"}\n" + } +} + +// main compiler functions + +def time_needed[T](i: Int, code: => T) = { + val start = System.nanoTime() + for (j <- 1 to i) code + val end = System.nanoTime() + (end - start)/(i * 1.0e9) +} + +// for Scala 2.12 +/* +def deserialise[T](file: String) : Try[T] = { + val in = new ObjectInputStream(new FileInputStream(new File(file))) + val obj = Try(in.readObject().asInstanceOf[T]) + in.close() + obj +} +*/ + +def deserialise[T](fname: String) : Try[T] = { + import scala.util.Using + Using(new ObjectInputStream(new FileInputStream(fname))) { + in => in.readObject.asInstanceOf[T] + } +} + +def compile(fname: String) : String = { + val ast = deserialise[List[Decl]](fname ++ ".prs").getOrElse(Nil) + prelude ++ (ast.map(compile_decl).mkString) +} + +def compile_to_file(fname: String) = { + val output = compile(fname) + scala.tools.nsc.io.File(s"${fname}.ll").writeAll(output) +} + +def compile_and_run(fname: String) : Unit = { + compile_to_file(fname) + (s"llc -filetype=obj ${fname}.ll").!! + (s"gcc ${fname}.o -o a.out").!! + println("Time: " + time_needed(2, (s"./a.out").!)) +} + +// some examples of .fun files +//compile_to_file("fact") +//compile_and_run("fact") +//compile_and_run("defs") + + +def main(args: Array[String]) : Unit = + //println(compile(args(0))) + compile_and_run(args(0)) +} + + + + +