# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1570885870 -3600
# Node ID 9d7843934d30dc01b972cdbcffba3dcf7dd077d0
# Parent  4642e2073808b793dff05d446807f0f98fe56556
updated llvm

diff -r 4642e2073808 -r 9d7843934d30 handouts/ho04.pdf
Binary file handouts/ho04.pdf has changed
diff -r 4642e2073808 -r 9d7843934d30 progs/fun_llvm.scala
--- a/progs/fun_llvm.scala	Thu Oct 10 21:04:38 2019 +0100
+++ b/progs/fun_llvm.scala	Sat Oct 12 14:11:10 2019 +0100
@@ -56,60 +56,84 @@
 
 // Abstract syntax trees for the Fun language
 abstract class KExp
+abstract class KVal
 
-case class KVar(s: String) extends KExp
-case class KNum(i: Int) extends KExp
-case class KAop(o: String, x1: String, x2: String) extends KExp
-case class KIfeq(x1: String, x2: String, e1: KExp, e2: KExp) extends KExp {
-  override def toString = s"KIf $x1 == $x2 \nIF\n$e1\nELSE\n$e2"
+case class KVar(s: String) extends KVal
+case class KNum(i: Int) extends KVal
+case class KAop(o: String, v1: KVal, v2: KVal) extends KVal
+case class KBop(o: String, v1: KVal, v2: KVal) extends KVal
+case class KCall(o: String, vrs: List[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 KCall(o: String, vrs: List[String]) extends KExp
-case class KLet(x: String, e1: KExp, e2: KExp) extends KExp {
+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
 
-def K(e: Exp) : KExp = e match {
-  case Var(s) => KVar(s) 
-  case Num(i) => KNum(i)
-  case Aop(o, a1, a2) => {
-    val x1 = Fresh("tmp")
-    val x2 = Fresh("tmp") 
-    KLet(x1, K(a1), KLet(x2, K(a2), KAop(o, x1, x2)))
-  } 
-  case Call(name: String, args: List[Exp]) => {
-    val args_new = args.map{a => (Fresh("tmp"), K(a))}
-    def aux(as: List[(String, KExp)]) : KExp = as match {
-      case Nil => KCall(name, args_new.map(_._1))
-      case (x, a)::rest => KLet(x, a, aux(rest))
+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, KAop(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, KBop(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_new)
+    aux(args, Nil)
+  }
+  case Sequence(e1, e2) => {
+    val z = Fresh("tmp")
+    CPS(e1)(y1 => 
+      CPS(e2)(y2 => KLet("_", y1, KLet(z, y2, k(KVar(z))))))
   }
-  case If(Bop("==", b1, b2), e1, e2) => {
-    val x1 = Fresh("tmp")
-    val x2 = Fresh("tmp") 
-    KLet(x1, K(b1), KLet(x2, K(b2), KIfeq(x1, x2, K(e1), K(e2))))
-  }
-}
+}   
+
+def CPSi(e: Exp) = CPS(e)(KReturn)
+
+val e1 = Aop("*", Var("a"), Num(3))
+CPS(e1)(KReturn)
+
+val e2 = Aop("+", Aop("*", Var("a"), Num(3)), Num(4))
+CPS(e2)(KReturn)
+
+val e3 = Aop("+", Num(2), Aop("*", Var("a"), Num(3)))
+CPS(e3)(KReturn)
 
-def Denest(e: KExp) : KExp = e match {
-  case KLet(xt, e1, e2) => {
-    def insert(e: KExp) : KExp = e match {
-      case KLet(yt, e3, e4) => KLet(yt, e3, insert(e4))
-      case e => KLet(xt, e, Denest(e2))
-    }
-    insert(Denest(e1))  
-  }
-  case KIfeq(x1, x2, e1, e2) =>  KIfeq(x1, x2, Denest(e1), Denest(e2))
-  case _ => e
-}
+val e4 = Aop("+", Aop("-", Num(1), Num(2)), Aop("*", Var("a"), Num(3)))
+CPS(e4)(KReturn)
+
+val e5 = If(Bop("==", Num(1), Num(1)), Num(3), Num(4))
+CPS(e5)(KReturn)
+
+val e6 = If(Bop("!=", Num(10), Num(10)), e5, Num(40))
+CPS(e6)(KReturn)
 
+val e7 = Call("foo", List(Num(3)))
+CPS(e7)(KReturn)
+
+val e8 = Call("foo", List(Num(3), Num(4), Aop("+", Num(5), Num(6))))
+CPS(e8)(KReturn)
+
+val e9 = Sequence(Aop("*", Var("a"), Num(3)), Aop("+", Var("b"), Num(6)))
+CPS(e9)(KReturn)
 
 val e = Aop("*", Aop("+", Num(1), Call("foo", List(Var("a"), Num(3)))), Num(4))
-println(K(e))
-println()
-println(Denest(K(e)))
-println()
+CPS(e)(KReturn)
+
 
 
 
@@ -124,88 +148,64 @@
     def m(args: Any*): String = sc.s(args:_*) ++ "\n"
 }
 
+def compile_op(op: String) = op match {
+  case "+" => "add i32 "
+  case "*" => "mul i32 "
+  case "-" => "sub i32 "
+  case "==" => "icmp eq i32 "
+}
 
-type Env = Map[String, Int]
-
-
+def compile_val(v: KVal) : String = v match {
+  case KNum(i) => s"$i"
+  case KVar(s) => s"%$s"
+  case KAop(op, x1, x2) => 
+    s"${compile_op(op)} ${compile_val(x1)}, ${compile_val(x2)}"
+  case KBop(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 ", "")})"
+}
 
 // compile K expressions
 def compile_exp(a: KExp) : String = a match {
-  case KNum(i) => s"?$i?"
-  case KVar(s) => s"?$s?"
-  case KAop("+", x1, x2) => s"add i32 %$x1, i32 %$x2"
-  case KAop("-", x1, x2) => s"sub i32 %$x1, i32 %$x2"
-  case KAop("*", x1, x2) => s"mul i32 %$x1, i32 %$x2"
-  case KLet(x: String, e1: KExp, e2: KExp) => {
-    val is1 = compile_exp(e1)
-    val is2 = compile_exp(e2)
-    i"%$x = $is1" ++ is2
-  }
-  case KLet(x: String, e1: KExp, e2: KExp) => {
-    val is1 = compile_exp(e1)
-    val is2 = compile_exp(e2)
-    i"%$x = $is1" ++ is2
-  }
-  case KIfeq(x1, x2, a1, a2) => {
+  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_br")
     val else_br = Fresh("else_br")
-    val x = Fresh("tmp")
-    i"%$x = icmp eq i32 %$x1, i32 %$x2" ++
     i"br i1 %$x, label %$if_br, label %$else_br" ++
     l"\n$if_br" ++
-    compile_exp(a1) ++
+    compile_exp(e1) ++
     l"\n$else_br" ++ 
-    compile_exp(a2)
-  }
-  case KCall(x1, args) => {
-    s"Call $x1 ($args)"
+    compile_exp(e2)
   }
-/*
-  case Call(name, args) => {
-    val is = "I" * args.length
-    args.map(a => compile_exp(a, env)).mkString ++
-    i"invokestatic XXX/XXX/$name($is)I"
-  }
-  case Sequence(a1, a2) => {
-    compile_exp(a1, env) ++ i"pop" ++ compile_exp(a2, env)
-  }
-  case Write(a1) => {
+}
+
+/*  case Write(a1) => {
     compile_exp(a1, env) ++
     i"dup" ++
     i"invokestatic XXX/XXX/write(I)V"
   }
-  */
-}
+*/
 
-/*
-// compile boolean expressions
-def compile_bexp(b: BExp, env : Env, jmp: String) : String = b match {
-  case Bop("==", a1, a2) => 
-    compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpne $jmp"
-  case Bop("!=", a1, a2) => 
-    compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpeq $jmp"
-  case Bop("<", a1, a2) => 
-    compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpge $jmp"
-  case Bop("<=", a1, a2) => 
-    compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpgt $jmp"
-}
-*/
+
 
 // compile function for declarations and main
 def compile_decl(d: Decl) : String = d match {
   case Def(name, args, body) => { 
-    println(s"DEF\n $name ($args) = \nBODY:")
-    println(Denest(K(body)))
-    println()
-    counter = -1
+    //println(s"DEF\n $name ($args) = \nBODY:")
+    //println(CPSi(body))
+    //println()
+    //counter = -1
     m"define i32 @$name (${args.mkString("i32 %", ", i32 %", "")}) {" ++
-    compile_exp(Denest(K(body))) ++
+    compile_exp(CPSi(body)) ++
     m"}\n"
   }
   case Main(body) => {
     m"define i32 @main() {" ++
-    compile_exp(Denest(K(body))) ++
-    i"ret i32 0" ++
+    compile_exp(CPSi(body)) ++
     m"}\n"
   }
 }
@@ -228,9 +228,8 @@
 
 def compile(class_name: String) : String = {
   val ast = deserialise[List[Decl]](class_name ++ ".prs").getOrElse(Nil) 
-  println(ast(0).toString ++ "\n")
-  val instructions = List(ast(0), ast(2)).map(compile_decl).mkString
-  instructions
+  //println(ast(0).toString ++ "\n")
+  ast.map(compile_decl).mkString
 }
 
 /*