58 abstract class KExp |
58 abstract class KExp |
59 |
59 |
60 case class KVar(s: String) extends KExp |
60 case class KVar(s: String) extends KExp |
61 case class KNum(i: Int) extends KExp |
61 case class KNum(i: Int) extends KExp |
62 case class KAop(o: String, x1: String, x2: String) extends KExp |
62 case class KAop(o: String, x1: String, x2: String) extends KExp |
63 case class KIfeq(x1: String, x2: String, e1: KExp, e2: KExp) extends KExp |
63 case class KIfeq(x1: String, x2: String, e1: KExp, e2: KExp) extends KExp { |
|
64 override def toString = s"KIf $x1 == $x2 \nIF\n$e1\nELSE\n$e2" |
|
65 |
|
66 } |
64 case class KCall(o: String, vrs: List[String]) extends KExp |
67 case class KCall(o: String, vrs: List[String]) extends KExp |
65 case class KLet(x: String, e1: KExp, e2: KExp) extends KExp { |
68 case class KLet(x: String, e1: KExp, e2: KExp) extends KExp { |
66 override def toString = s"let $x = $e1 in \n$e2" |
69 override def toString = s"let $x = $e1 in \n$e2" |
67 } |
70 } |
68 |
71 |
73 val x1 = Fresh("tmp") |
76 val x1 = Fresh("tmp") |
74 val x2 = Fresh("tmp") |
77 val x2 = Fresh("tmp") |
75 KLet(x1, K(a1), KLet(x2, K(a2), KAop(o, x1, x2))) |
78 KLet(x1, K(a1), KLet(x2, K(a2), KAop(o, x1, x2))) |
76 } |
79 } |
77 case Call(name: String, args: List[Exp]) => { |
80 case Call(name: String, args: List[Exp]) => { |
78 val args_new = args.map{a => (Fresh("x"), K(a))} |
81 val args_new = args.map{a => (Fresh("tmp"), K(a))} |
79 def aux(as: List[(String, KExp)]) : KExp = as match { |
82 def aux(as: List[(String, KExp)]) : KExp = as match { |
80 case Nil => KCall(name, args_new.map(_._1)) |
83 case Nil => KCall(name, args_new.map(_._1)) |
81 case (x, a)::rest => KLet(x, a, aux(rest)) |
84 case (x, a)::rest => KLet(x, a, aux(rest)) |
82 } |
85 } |
83 aux(args_new) |
86 aux(args_new) |
84 } |
87 } |
85 |
88 case If(Bop("==", b1, b2), e1, e2) => { |
|
89 val x1 = Fresh("tmp") |
|
90 val x2 = Fresh("tmp") |
|
91 KLet(x1, K(b1), KLet(x2, K(b2), KIfeq(x1, x2, K(e1), K(e2)))) |
|
92 } |
86 } |
93 } |
87 |
94 |
88 def Denest(e: KExp) : KExp = e match { |
95 def Denest(e: KExp) : KExp = e match { |
89 case KLet(xt, e1, e2) => { |
96 case KLet(xt, e1, e2) => { |
90 def insert(e: KExp) : KExp = e match { |
97 def insert(e: KExp) : KExp = e match { |
91 case KLet(yt, e3, e4) => KLet(yt, e3, insert(e4)) |
98 case KLet(yt, e3, e4) => KLet(yt, e3, insert(e4)) |
92 case e => KLet(xt, e, Denest(e2)) |
99 case e => KLet(xt, e, Denest(e2)) |
93 } |
100 } |
94 insert(Denest(e1)) |
101 insert(Denest(e1)) |
95 } |
102 } |
|
103 case KIfeq(x1, x2, e1, e2) => KIfeq(x1, x2, Denest(e1), Denest(e2)) |
96 case _ => e |
104 case _ => e |
97 } |
105 } |
98 |
106 |
99 val e = Aop("*", Aop("+", Num(1), Call("foo", List(Num(2), Num(3)))), Num(4)) |
107 |
|
108 val e = Aop("*", Aop("+", Num(1), Call("foo", List(Var("a"), Num(3)))), Num(4)) |
100 println(K(e)) |
109 println(K(e)) |
|
110 println() |
101 println(Denest(K(e))) |
111 println(Denest(K(e))) |
|
112 println() |
102 |
113 |
103 |
114 |
104 |
115 |
105 // convenient string interpolations |
116 // convenient string interpolations |
106 // for instructions, labels and methods |
117 // for instructions, labels and methods |
116 |
127 |
117 type Env = Map[String, Int] |
128 type Env = Map[String, Int] |
118 |
129 |
119 |
130 |
120 |
131 |
121 // compile expressions |
132 // compile K expressions |
122 def compile_exp(a: Exp, env : Env, k: Int) : (String, Int) = a match { |
133 def compile_exp(a: KExp) : String = a match { |
123 case Num(i) => (i"%$k = add i32 0, i32 $i", k) |
134 case KNum(i) => s"?$i?" |
124 case Var(s) => (i"%$k = add i32 0, i32 %${env(s)}", k) |
135 case KVar(s) => s"?$s?" |
125 case Aop("+", a1, a2) => { |
136 case KAop("+", x1, x2) => s"add i32 %$x1, i32 %$x2" |
126 val (cs1, k1) = compile_exp(a1, env, k) |
137 case KAop("-", x1, x2) => s"sub i32 %$x1, i32 %$x2" |
127 val (cs2, k2) = compile_exp(a2, env, k1 + 1) |
138 case KAop("*", x1, x2) => s"mul i32 %$x1, i32 %$x2" |
128 (cs1 ++ cs2 ++ i"%${k2+1} = add i32 %$k1, i32 %$k2", k2 + 1) |
139 case KLet(x: String, e1: KExp, e2: KExp) => { |
129 } |
140 val is1 = compile_exp(e1) |
130 case Aop("-", a1, a2) => { |
141 val is2 = compile_exp(e2) |
131 val (cs1, k1) = compile_exp(a1, env, k) |
142 i"%$x = $is1" ++ is2 |
132 val (cs2, k2) = compile_exp(a2, env, k1 + 1) |
143 } |
133 (cs1 ++ cs2 ++ i"%${k2+1} = sub i32 %$k1, i32 %$k2", k2 + 1) |
144 case KIfeq(x1, x2, a1, a2) => { |
134 } |
145 val if_br = Fresh("if_br") |
135 case Aop("*", a1, a2) => { |
146 val else_br = Fresh("else_br") |
136 val (cs1, k1) = compile_exp(a1, env, k) |
147 val x = Fresh("tmp") |
137 val (cs2, k2) = compile_exp(a2, env, k1 + 1) |
148 i"%$x = icmp eq i32 %$x1, i32 %$x2" ++ |
138 (cs1 ++ cs2 ++ i"%${k2+1} = mul i32 %$k1, i32 %$k2", k2 + 1) |
149 i"br i1 %$x, label %$if_br, label %$else_br" ++ |
139 } |
150 l"\n$if_br" ++ |
140 /* |
151 compile_exp(a1) ++ |
141 case If(b, a1, a2) => { |
152 l"\n$else_br" ++ |
142 val if_else = Fresh("If_else") |
153 compile_exp(a2) |
143 val if_end = Fresh("If_end") |
154 } |
144 compile_bexp(b, env, if_else) ++ |
155 case KCall(x1, args) => { |
145 compile_exp(a1, env) ++ |
156 s"Call $x1 ($args)" |
146 i"goto $if_end" ++ |
157 } |
147 l"$if_else" ++ |
158 /* |
148 compile_exp(a2, env) ++ |
|
149 l"$if_end" |
|
150 } |
|
151 case Call(name, args) => { |
159 case Call(name, args) => { |
152 val is = "I" * args.length |
160 val is = "I" * args.length |
153 args.map(a => compile_exp(a, env)).mkString ++ |
161 args.map(a => compile_exp(a, env)).mkString ++ |
154 i"invokestatic XXX/XXX/$name($is)I" |
162 i"invokestatic XXX/XXX/$name($is)I" |
155 } |
163 } |
162 i"invokestatic XXX/XXX/write(I)V" |
170 i"invokestatic XXX/XXX/write(I)V" |
163 } |
171 } |
164 */ |
172 */ |
165 } |
173 } |
166 |
174 |
167 val e = Aop("*", Aop("+", Num(2), Num(4)), Num(5)) |
175 /* |
168 compile_exp(e, Map(), 1)._1.mkString |
|
169 |
|
170 |
|
171 // compile boolean expressions |
176 // compile boolean expressions |
172 def compile_bexp(b: BExp, env : Env, jmp: String) : String = b match { |
177 def compile_bexp(b: BExp, env : Env, jmp: String) : String = b match { |
173 case Bop("==", a1, a2) => |
178 case Bop("==", a1, a2) => |
174 compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpne $jmp" |
179 compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpne $jmp" |
175 case Bop("!=", a1, a2) => |
180 case Bop("!=", a1, a2) => |
177 case Bop("<", a1, a2) => |
182 case Bop("<", a1, a2) => |
178 compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpge $jmp" |
183 compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpge $jmp" |
179 case Bop("<=", a1, a2) => |
184 case Bop("<=", a1, a2) => |
180 compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpgt $jmp" |
185 compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpgt $jmp" |
181 } |
186 } |
|
187 */ |
182 |
188 |
183 // compile function for declarations and main |
189 // compile function for declarations and main |
184 def compile_decl(d: Decl) : String = d match { |
190 def compile_decl(d: Decl) : String = d match { |
185 case Def(name, args, a) => { |
191 case Def(name, args, body) => { |
186 val env = args.zipWithIndex.toMap |
192 println(s"DEF\n $name ($args) = \nBODY:") |
187 val is = "I" * args.length |
193 println(Denest(K(body))) |
188 m".method public static $name($is)I" ++ |
194 println() |
189 m".limit locals ${args.length.toString}" ++ |
195 counter = -1 |
190 m".limit stack ${1 + max_stack_exp(a)}" ++ |
196 m"define i32 @$name (${args.mkString("i32 %", ", i32 %", "")}) {" ++ |
191 l"${name}_Start" ++ |
197 compile_exp(Denest(K(body))) ++ |
192 compile_exp(a, env) ++ |
198 m"}\n" |
193 i"ireturn" ++ |
199 } |
194 m".end method\n" |
200 case Main(body) => { |
195 } |
201 m"define i32 @main() {" ++ |
196 case Main(a) => { |
202 compile_exp(Denest(K(body))) ++ |
197 m".method public static main([Ljava/lang/String;)V" ++ |
203 i"ret i32 0" ++ |
198 m".limit locals 200" ++ |
204 m"}\n" |
199 m".limit stack 200" ++ |
|
200 compile_exp(a, Map()) ++ |
|
201 i"invokestatic XXX/XXX/write(I)V" ++ |
|
202 i"return" ++ |
|
203 m".end method\n" |
|
204 } |
205 } |
205 } |
206 } |
206 |
207 |
207 // main compiler functions |
208 // main compiler functions |
208 |
209 |
220 } |
221 } |
221 } |
222 } |
222 |
223 |
223 def compile(class_name: String) : String = { |
224 def compile(class_name: String) : String = { |
224 val ast = deserialise[List[Decl]](class_name ++ ".prs").getOrElse(Nil) |
225 val ast = deserialise[List[Decl]](class_name ++ ".prs").getOrElse(Nil) |
225 val instructions = ast.map(compile_decl).mkString |
226 println(ast(0).toString ++ "\n") |
226 (library + instructions).replaceAllLiterally("XXX", class_name) |
227 val instructions = List(ast(0), ast(2)).map(compile_decl).mkString |
227 } |
228 instructions |
228 |
229 } |
|
230 |
|
231 /* |
229 def compile_to_file(class_name: String) = { |
232 def compile_to_file(class_name: String) = { |
230 val output = compile(class_name) |
233 val output = compile(class_name) |
231 scala.tools.nsc.io.File(s"${class_name}.j").writeAll(output) |
234 scala.tools.nsc.io.File(s"${class_name}.j").writeAll(output) |
232 } |
235 } |
233 |
236 |
234 def compile_and_run(class_name: String) : Unit = { |
237 def compile_and_run(class_name: String) : Unit = { |
235 compile_to_file(class_name) |
238 compile_to_file(class_name) |
236 (s"java -jar jvm/jasmin-2.4/jasmin.jar ${class_name}.j").!! |
239 (s"java -jar jvm/jasmin-2.4/jasmin.jar ${class_name}.j").!! |
237 println("Time: " + time_needed(2, (s"java ${class_name}/${class_name}").!)) |
240 println("Time: " + time_needed(2, (s"java ${class_name}/${class_name}").!)) |
238 } |
241 } |
239 |
242 */ |
240 |
243 |
241 // some examples of .fun files |
244 // some examples of .fun files |
242 //compile_to_file("fact") |
245 //compile_to_file("fact") |
243 //compile_and_run("fact") |
246 //compile_and_run("fact") |
244 //compile_and_run("defs") |
247 //compile_and_run("defs") |
245 |
248 |
246 |
249 |
247 def main(args: Array[String]) = |
250 def main(args: Array[String]) : Unit = |
248 compile_and_run(args(0)) |
251 println(compile(args(0))) |
249 |
252 |
250 |
253 |
251 } |
254 } |