# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1570478005 -3600
# Node ID 36379b03843820d90109d4a43a35299e440262e5
# Parent  180600c04da245f41334236015f8895b060cbbf4
updated

diff -r 180600c04da2 -r 36379b038438 coursework/cw01.pdf
Binary file coursework/cw01.pdf has changed
diff -r 180600c04da2 -r 36379b038438 hws/hw09.pdf
Binary file hws/hw09.pdf has changed
diff -r 180600c04da2 -r 36379b038438 hws/hw09.tex
--- a/hws/hw09.tex	Fri Oct 04 11:21:30 2019 +0100
+++ b/hws/hw09.tex	Mon Oct 07 20:53:25 2019 +0100
@@ -45,6 +45,23 @@
 \end{lstlisting}
 
 
+\item What does the following LLVM function calculate. Give the
+
+\begin{lstlisting}[language=LLVM,numbers=none]  
+define i32 @foo(i32 %a, i32 %b)  {
+  %1 = mul i32 %a, %a
+  %2 = mul i32 %a, 2
+  %3 = mul i32 %2, %b
+  %4 = add i32 %1, %3
+  %5 = mul i32 %b, %b
+  %6 = add i32 %5, %4
+  ret i32 %6
+}
+\end{lstlisting}
+
+  
+
+
 
 \item \POSTSCRIPT  
 
diff -r 180600c04da2 -r 36379b038438 progs/bfc0.scala
--- a/progs/bfc0.scala	Fri Oct 04 11:21:30 2019 +0100
+++ b/progs/bfc0.scala	Mon Oct 07 20:53:25 2019 +0100
@@ -78,3 +78,7 @@
             +++++++++[-]<-]<-]<-]<-]<-]<-]<-]++++++++++."""
 
 println(s"${time_needed(1, compile_run(b1))} secs")
+
+
+
+
diff -r 180600c04da2 -r 36379b038438 progs/bfc1.scala
--- a/progs/bfc1.scala	Fri Oct 04 11:21:30 2019 +0100
+++ b/progs/bfc1.scala	Mon Oct 07 20:53:25 2019 +0100
@@ -87,3 +87,5 @@
             +++++++++[-]<-]<-]<-]<-]<-]<-]<-]++++++++++."""
 
 println(s"${time_needed(1, compile_run(b1))} secs")
+
+
diff -r 180600c04da2 -r 36379b038438 progs/fun_llvm.scala
--- a/progs/fun_llvm.scala	Fri Oct 04 11:21:30 2019 +0100
+++ b/progs/fun_llvm.scala	Mon Oct 07 20:53:25 2019 +0100
@@ -15,7 +15,7 @@
 
 
 
-object Compiler {
+//object Compiler {
 
 import java.io._  
 import scala.util._
@@ -43,26 +43,6 @@
 // copied from http://www.ceng.metu.edu.tr/courses/ceng444/link/jvm-cpm.html
 //
 
-val library = """
-.class public XXX.XXX
-.super java/lang/Object
-
-.method public <init>()V
-        aload_0
-        invokenonvirtual java/lang/Object/<init>()V
-        return
-.end method
-
-.method public static write(I)V 
-        .limit locals 1 
-        .limit stack 2 
-        getstatic java/lang/System/out Ljava/io/PrintStream; 
-        iload 0
-        invokevirtual java/io/PrintStream/println(I)V 
-        return 
-.end method
-
-"""
 
 // for generating new labels
 var counter = -1
@@ -72,6 +52,56 @@
   x ++ "_" ++ counter.toString()
 }
 
+
+
+// Abstract syntax trees for the Fun language
+abstract class KExp
+
+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
+case class KCall(o: String, vrs: List[String]) extends KExp
+case class KLet(x: String, e1: KExp, e2: KExp) extends KExp {
+  override def toString = s"let $x = $e1 in \n$e2" 
+}
+
+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("x"), 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))
+    }
+    aux(args_new)
+  }
+  
+}
+
+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 _ => e
+}
+
+val e = Aop("*", Aop("+", Num(1), Call("foo", List(Num(2), Num(3)))), Num(4))
+println(K(e))
+println(Denest(K(e)))
+
+
+
 // convenient string interpolations 
 // for instructions, labels and methods
 import scala.language.implicitConversions
@@ -86,15 +116,28 @@
 
 type Env = Map[String, Int]
 
+
+
 // compile expressions
-def compile_exp(a: Exp, env : Env) : String = a match {
-  case Num(i) => i"ldc $i"
-  case Var(s) => i"iload ${env(s)}"
-  case Aop("+", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"iadd"
-  case Aop("-", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"isub"
-  case Aop("*", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"imul"
-  case Aop("/", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"idiv"
-  case Aop("%", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"irem"
+def compile_exp(a: Exp, env : Env, k: Int) : (String, Int) = a match {
+  case Num(i) => (i"%$k = add i32 0, i32 $i", k)
+  case Var(s) => (i"%$k = add i32 0, i32 %${env(s)}", k)
+  case Aop("+", a1, a2) => {
+    val (cs1, k1) = compile_exp(a1, env, k)
+    val (cs2, k2) = compile_exp(a2, env, k1 + 1)
+    (cs1 ++ cs2 ++ i"%${k2+1} = add i32 %$k1, i32 %$k2", k2 + 1)
+  }
+  case Aop("-", a1, a2) => {
+    val (cs1, k1) = compile_exp(a1, env, k)
+    val (cs2, k2) = compile_exp(a2, env, k1 + 1)
+    (cs1 ++ cs2 ++ i"%${k2+1} = sub i32 %$k1, i32 %$k2", k2 + 1)
+  }
+  case Aop("*", a1, a2) => {
+    val (cs1, k1) = compile_exp(a1, env, k)
+    val (cs2, k2) = compile_exp(a2, env, k1 + 1)
+    (cs1 ++ cs2 ++ i"%${k2+1} = mul i32 %$k1, i32 %$k2", k2 + 1)
+  }
+  /*
   case If(b, a1, a2) => {
     val if_else = Fresh("If_else")
     val if_end = Fresh("If_end")
@@ -118,8 +161,13 @@
     i"dup" ++
     i"invokestatic XXX/XXX/write(I)V"
   }
+  */
 }
 
+val e = Aop("*", Aop("+", Num(2), Num(4)), Num(5))
+compile_exp(e, Map(), 1)._1.mkString
+
+
 // compile boolean expressions
 def compile_bexp(b: BExp, env : Env, jmp: String) : String = b match {
   case Bop("==", a1, a2) =>