1 // A Small LLVM Compiler for a Simple Functional Language |
1 // Author: Zhuo Ying Jiang Li |
2 // (includes an external lexer and parser) |
2 // Starting code by Dr Christian Urban |
|
3 |
|
4 // |
|
5 // Use amm compiler.sc XXX.fun |
|
6 // ./XXX |
|
7 // This will generate XXX.ll, XXX.o as well as the binary program. |
3 // |
8 // |
4 // |
9 |
5 // call with -- prints out llvm code |
10 // lexer + parser |
6 // |
|
7 // amm fun_llvm.sc main fact.fun |
|
8 // amm fun_llvm.sc main defs.fun |
|
9 // |
|
10 // or -- writes llvm code to disk |
|
11 // |
|
12 // amm fun_llvm.sc write fact.fun |
|
13 // amm fun_llvm.sc write defs.fun |
|
14 // |
|
15 // this will generate an .ll file. |
|
16 // |
|
17 // or -- runs the generated llvm code via lli |
|
18 // |
|
19 // amm fun_llvm.sc run fact.fun |
|
20 // amm fun_llvm.sc run defs.fun |
|
21 // |
|
22 // |
|
23 // You can interpret an .ll file using lli, for example |
|
24 // |
|
25 // lli fact.ll |
|
26 // |
|
27 // The optimiser can be invoked as |
|
28 // |
|
29 // opt -O1 -S in_file.ll > out_file.ll |
|
30 // opt -O3 -S in_file.ll > out_file.ll |
|
31 // |
|
32 // The code produced for the various architectures can be obtain with |
|
33 // |
|
34 // llc -march=x86 -filetype=asm in_file.ll -o - |
|
35 // llc -march=arm -filetype=asm in_file.ll -o - |
|
36 // |
|
37 // Producing an executable can be achieved by |
|
38 // |
|
39 // llc -filetype=obj in_file.ll |
|
40 // gcc in_file.o -o a.out |
|
41 // ./a.out |
|
42 |
|
43 |
11 |
44 import $file.fun_tokens, fun_tokens._ |
12 import $file.fun_tokens, fun_tokens._ |
45 import $file.fun_parser, fun_parser._ |
13 import $file.fun_parser, fun_parser._ |
46 |
|
47 |
14 |
48 // for generating new labels |
15 // for generating new labels |
49 var counter = -1 |
16 var counter = -1 |
50 |
17 |
51 def Fresh(x: String) = { |
18 def Fresh(x: String) = { |
52 counter += 1 |
19 counter += 1 |
53 x ++ "_" ++ counter.toString() |
20 x ++ "_" ++ counter.toString() |
54 } |
21 } |
55 |
22 |
|
23 // typing |
|
24 type Ty = String |
|
25 type TyEnv = Map[String, Ty] |
|
26 |
|
27 // initial typing environment |
|
28 val initialEnv = Map[String, Ty]("skip" -> "Void", "print_int" -> "Void", "print_char" -> "Void", |
|
29 "print_space" -> "Void", "print_star" -> "Void", "new_line" -> "Void") |
|
30 |
|
31 val typeConversion = Map("Int" -> "i32", "Double" -> "double", "Void" -> "void") |
|
32 |
56 // Internal CPS language for FUN |
33 // Internal CPS language for FUN |
57 abstract class KExp |
34 abstract class KExp |
58 abstract class KVal |
35 abstract class KVal |
59 |
36 |
60 type Ty = String |
|
61 type TyEnv = Map[String, Ty] |
|
62 |
|
63 case class KVar(s: String, ty: Ty = "UNDEF") extends KVal |
37 case class KVar(s: String, ty: Ty = "UNDEF") extends KVal |
64 case class KLoad(v: KVal) extends KVal |
38 case class KConst(s: String, ty: Ty = "UNDEF") extends KVal |
65 case class KNum(i: Int) extends KVal |
39 case class KNum(i: Int) extends KVal // known type |
66 case class KFNum(i: Double) extends KVal |
40 case class KFNum(d: Float) extends KVal // known type |
67 case class KChr(c: Int) extends KVal |
41 case class KChConst(c: Int) extends KVal // known type |
68 case class Kop(o: String, v1: KVal, v2: KVal, ty: Ty = "UNDEF") extends KVal |
42 case class Kop(o: String, v1: KVal, v2: KVal, ty: Ty = "UNDEF") extends KVal |
69 case class KCall(o: String, vrs: List[KVal], ty: Ty = "UNDEF") extends KVal |
43 case class KCall(o: String, vrs: List[KVal], ty: Ty = "UNDEF") extends KVal |
70 |
44 |
|
45 case class KLet(x: String, e1: KVal, e2: KExp) extends KExp { |
|
46 override def toString = s"LET $x = $e1 in \n$e2" |
|
47 } |
71 case class KIf(x1: String, e1: KExp, e2: KExp) extends KExp { |
48 case class KIf(x1: String, e1: KExp, e2: KExp) extends KExp { |
72 override def toString = s"KIf $x1\nIF\n$e1\nELSE\n$e2" |
49 def pad(e: KExp) = e.toString.replaceAll("(?m)^", " ") |
73 } |
50 |
74 case class KLet(x: String, e1: KVal, e2: KExp) extends KExp { |
51 override def toString = |
75 override def toString = s"let $x = $e1 in \n$e2" |
52 s"IF $x1\nTHEN\n${pad(e1)}\nELSE\n${pad(e2)}" |
76 } |
53 } |
77 case class KReturn(v: KVal) extends KExp |
54 case class KReturn(v: KVal) extends KExp |
78 |
|
79 // typing K values |
|
80 def typ_val(v: KVal, ts: TyEnv) : (KVal, Ty) = v match { |
|
81 case KVar(s, _) => { |
|
82 val ty = ts.getOrElse(s, "TUNDEF") |
|
83 (KVar(s, ty), ty) |
|
84 } |
|
85 case Kop(op, v1, v2, _) => { |
|
86 val (tv1, ty1) = typ_val(v1, ts) |
|
87 val (tv2, ty2) = typ_val(v2, ts) |
|
88 if (ty1 == ty2) (Kop(op, tv1, tv2, ty1), ty1) else (Kop(op, tv1, tv2, "TMISMATCH"), "TMISMATCH") |
|
89 } |
|
90 case KCall(fname, args, _) => { |
|
91 val ty = ts.getOrElse(fname, "TCALLUNDEF" ++ fname) |
|
92 (KCall(fname, args.map(typ_val(_, ts)._1), ty), ty) |
|
93 } |
|
94 case KLoad(v) => { |
|
95 val (tv, ty) = typ_val(v, ts) |
|
96 (KLoad(tv), ty) |
|
97 } |
|
98 case KNum(i) => (KNum(i), "Int") |
|
99 case KFNum(i) => (KFNum(i), "Double") |
|
100 case KChr(c) => (KChr(c), "Int") |
|
101 } |
|
102 |
|
103 def typ_exp(a: KExp, ts: TyEnv) : KExp = a match { |
|
104 case KReturn(v) => KReturn(typ_val(v, ts)._1) |
|
105 case KLet(x: String, v: KVal, e: KExp) => { |
|
106 val (tv, ty) = typ_val(v, ts) |
|
107 KLet(x, tv, typ_exp(e, ts + (x -> ty))) |
|
108 } |
|
109 case KIf(b, e1, e2) => KIf(b, typ_exp(e1, ts), typ_exp(e2, ts)) |
|
110 } |
|
111 |
|
112 |
|
113 |
|
114 |
55 |
115 // CPS translation from Exps to KExps using a |
56 // CPS translation from Exps to KExps using a |
116 // continuation k. |
57 // continuation k. |
117 def CPS(e: Exp)(k: KVal => KExp) : KExp = e match { |
58 def CPS(e: Exp)(k: KVal => KExp) : KExp = e match { |
118 case Var(s) if (s.head.isUpper) => { |
59 case Var(s) => { |
|
60 if (s.head.isUpper) { // if this variable is a global |
119 val z = Fresh("tmp") |
61 val z = Fresh("tmp") |
120 KLet(z, KLoad(KVar(s)), k(KVar(z))) |
62 KLet(z, KConst(s), k(KVar(z))) |
121 } |
63 } else k(KVar(s)) |
122 case Var(s) => k(KVar(s)) |
64 } |
123 case Num(i) => k(KNum(i)) |
65 case Num(i) => k(KNum(i)) |
124 case ChConst(c) => k(KChr(c)) |
66 case FNum(d) => k(KFNum(d)) |
125 case FNum(i) => k(KFNum(i)) |
67 case ChConst(c) => k(KChConst(c)) |
126 case Aop(o, e1, e2) => { |
68 case Aop(o, e1, e2) => { |
127 val z = Fresh("tmp") |
69 val z = Fresh("tmp") |
128 CPS(e1)(y1 => |
70 CPS(e1)(y1 => |
129 CPS(e2)(y2 => KLet(z, Kop(o, y1, y2), k(KVar(z))))) |
71 CPS(e2)(y2 => KLet(z, Kop(o, y1, y2), k(KVar(z))))) |
130 } |
72 } |
144 } |
86 } |
145 aux(args, Nil) |
87 aux(args, Nil) |
146 } |
88 } |
147 case Sequence(e1, e2) => |
89 case Sequence(e1, e2) => |
148 CPS(e1)(_ => CPS(e2)(y2 => k(y2))) |
90 CPS(e1)(_ => CPS(e2)(y2 => k(y2))) |
149 } |
91 } |
150 |
92 |
151 //initial continuation |
93 // initial continuation |
152 def CPSi(e: Exp) = CPS(e)(KReturn) |
94 def CPSi(e: Exp) = CPS(e)(KReturn) |
153 |
95 |
154 // some testcases |
96 |
155 val e1 = Aop("*", Var("a"), Num(3)) |
97 // get type of KVal |
156 CPSi(e1) |
98 def get_typ_val(v: KVal) : Ty = v match { |
157 |
99 case KNum(i) => "Int" |
158 val e2 = Aop("+", Aop("*", Var("a"), Num(3)), Num(4)) |
100 case KFNum(d) => "Double" |
159 CPSi(e2) |
101 case KChConst(i) => "Int" |
160 |
102 case KVar(name, ty) => ty |
161 val e3 = Aop("+", Num(2), Aop("*", Var("a"), Num(3))) |
103 case KConst(name, ty) => ty |
162 CPSi(e3) |
104 case Kop(o, v1, v2, ty) => ty |
163 |
105 case KCall(o, vrs, ty) => ty |
164 val e4 = Aop("+", Aop("-", Num(1), Num(2)), Aop("*", Var("a"), Num(3))) |
106 } |
165 CPSi(e4) |
107 |
166 |
108 // update type information for KValues |
167 val e5 = If(Bop("==", Num(1), Num(1)), Num(3), Num(4)) |
109 def typ_val(v: KVal, ts: TyEnv) : KVal = v match { |
168 CPSi(e5) |
110 case KVar(name, ty) => { |
169 |
111 if (ts.contains(name)) { |
170 val e6 = If(Bop("!=", Num(10), Num(10)), e5, Num(40)) |
112 KVar(name, ts(name)) |
171 CPSi(e6) |
113 } else throw new Exception(s"Compile error: unknown type for $name") |
172 |
114 } |
173 val e7 = Call("foo", List(Num(3))) |
115 case KConst(name, ty) => { |
174 CPSi(e7) |
116 if (ts.contains(name)) { |
175 |
117 KConst(name, ts(name)) |
176 val e8 = Call("foo", List(Aop("*", Num(3), Num(1)), Num(4), Aop("+", Num(5), Num(6)))) |
118 } else throw new Exception(s"Compile error: unknown type for $name") |
177 CPSi(e8) |
119 } |
178 |
120 case Kop(o, v1, v2, ty) => { |
179 val e9 = Sequence(Aop("*", Var("a"), Num(3)), Aop("+", Var("b"), Num(6))) |
121 val tv1 = typ_val(v1, ts) |
180 CPSi(e9) |
122 val tv2 = typ_val(v2, ts) |
181 |
123 val t1 = get_typ_val(tv1) |
182 val e = Aop("*", Aop("+", Num(1), Call("foo", List(Var("a"), Num(3)))), Num(4)) |
124 val t2 = get_typ_val(tv2) |
183 CPSi(e) |
125 if (t1 != t2) throw new Exception(s"Compile error: cannot compare $t1 with $t2") |
184 |
126 Kop(o, tv1, tv2, t1) |
185 |
127 } |
186 |
128 case KCall(o, vrs, ty) => { |
|
129 val new_vrs = vrs.map(vr => typ_val(vr, ts)) |
|
130 if (ts.contains(o)) { |
|
131 KCall(o, new_vrs, ts(o)) |
|
132 } else throw new Exception(s"Compile error: unknown type for $o") |
|
133 } |
|
134 case x => x // no changes: KNum, KFNum, KChConst |
|
135 } |
|
136 |
|
137 // update type information for KExpressions |
|
138 def typ_exp(a: KExp, ts: TyEnv) : KExp = a match { |
|
139 case KLet(x, e1, e2) => { |
|
140 val te1 = typ_val(e1, ts) |
|
141 val env1 = ts + (x -> get_typ_val(te1)) |
|
142 val te2 = typ_exp(e2, env1) |
|
143 KLet(x, te1, te2) |
|
144 } |
|
145 case KIf(x1, e1, e2) => KIf(x1, typ_exp(e1, ts), typ_exp(e2, ts)) |
|
146 case KReturn(v) => KReturn(typ_val(v, ts)) |
|
147 } |
|
148 |
|
149 // prelude |
|
150 val prelude = """ |
|
151 declare i32 @printf(i8*, ...) |
|
152 |
|
153 @.str_nl = private constant [2 x i8] c"\0A\00" |
|
154 @.str_star = private constant [2 x i8] c"*\00" |
|
155 @.str_space = private constant [2 x i8] c" \00" |
|
156 @.str_int = private constant [3 x i8] c"%d\00" |
|
157 @.str_c = private constant [3 x i8] c"%c\00" |
|
158 |
|
159 define void @new_line() #0 { |
|
160 %t0 = getelementptr [2 x i8], [2 x i8]* @.str_nl, i32 0, i32 0 |
|
161 call i32 (i8*, ...) @printf(i8* %t0) |
|
162 ret void |
|
163 } |
|
164 |
|
165 define void @print_star() #0 { |
|
166 %t0 = getelementptr [2 x i8], [2 x i8]* @.str_star, i32 0, i32 0 |
|
167 call i32 (i8*, ...) @printf(i8* %t0) |
|
168 ret void |
|
169 } |
|
170 |
|
171 define void @print_space() #0 { |
|
172 %t0 = getelementptr [2 x i8], [2 x i8]* @.str_space, i32 0, i32 0 |
|
173 call i32 (i8*, ...) @printf(i8* %t0) |
|
174 ret void |
|
175 } |
|
176 |
|
177 define void @print_int(i32 %x) { |
|
178 %t0 = getelementptr [3 x i8], [3 x i8]* @.str_int, i32 0, i32 0 |
|
179 call i32 (i8*, ...) @printf(i8* %t0, i32 %x) |
|
180 ret void |
|
181 } |
|
182 |
|
183 define void @print_char(i32 %x) { |
|
184 %t0 = getelementptr [3 x i8], [3 x i8]* @.str_c, i32 0, i32 0 |
|
185 call i32 (i8*, ...) @printf(i8* %t0, i32 %x) |
|
186 ret void |
|
187 } |
|
188 |
|
189 define void @skip() #0 { |
|
190 ret void |
|
191 } |
|
192 |
|
193 ; END OF BUILT-IN FUNCTIONS (prelude) |
|
194 """ |
187 |
195 |
188 // convenient string interpolations |
196 // convenient string interpolations |
189 // for instructions, labels and methods |
197 // for instructions, labels and methods |
190 import scala.language.implicitConversions |
198 import scala.language.implicitConversions |
191 import scala.language.reflectiveCalls |
199 import scala.language.reflectiveCalls |
192 |
200 |
193 |
201 implicit def string_inters(sc: StringContext) = new { |
194 |
|
195 |
|
196 implicit def sring_inters(sc: StringContext) = new { |
|
197 def i(args: Any*): String = " " ++ sc.s(args:_*) ++ "\n" |
202 def i(args: Any*): String = " " ++ sc.s(args:_*) ++ "\n" |
198 def l(args: Any*): String = sc.s(args:_*) ++ ":\n" |
203 def l(args: Any*): String = sc.s(args:_*) ++ ":\n" |
199 def m(args: Any*): String = sc.s(args:_*) ++ "\n" |
204 def m(args: Any*): String = sc.s(args:_*) ++ "\n" |
200 } |
205 } |
201 |
|
202 def get_ty(s: String) = s match { |
|
203 case "Double" => "double" |
|
204 case "Void" => "void" |
|
205 case "Int" => "i32" |
|
206 case "Bool" => "i2" |
|
207 case _ => s |
|
208 } |
|
209 |
|
210 def compile_call_arg(a: KVal) = a match { |
|
211 case KNum(i) => s"i32 $i" |
|
212 case KFNum(i) => s"double $i" |
|
213 case KChr(c) => s"i32 $c" |
|
214 case KVar(s, ty) => s"${get_ty(ty)} %$s" |
|
215 } |
|
216 |
|
217 def compile_arg(s: (String, String)) = s"${get_ty(s._2)} %${s._1}" |
|
218 |
|
219 |
206 |
220 // mathematical and boolean operations |
207 // mathematical and boolean operations |
221 def compile_op(op: String) = op match { |
208 def compile_op(op: String) = op match { |
222 case "+" => "add i32 " |
209 case "+" => "add i32 " |
223 case "*" => "mul i32 " |
210 case "*" => "mul i32 " |
224 case "-" => "sub i32 " |
211 case "-" => "sub i32 " |
225 case "/" => "sdiv i32 " |
212 case "/" => "sdiv i32 " |
226 case "%" => "srem i32 " |
213 case "%" => "srem i32 " |
227 case "==" => "icmp eq i32 " |
214 case "==" => "icmp eq i32 " |
228 case "!=" => "icmp ne i32 " // not equal |
215 case "!=" => "icmp ne i32 " |
229 case "<=" => "icmp sle i32 " // signed less or equal |
216 case "<=" => "icmp sle i32 " |
230 case "<" => "icmp slt i32 " // signed less than |
217 case "<" => "icmp slt i32 " |
|
218 case ">=" => "icmp sge i32 " |
|
219 case ">" => "icmp sgt i32 " |
231 } |
220 } |
232 |
221 |
233 def compile_dop(op: String) = op match { |
222 def compile_dop(op: String) = op match { |
234 case "+" => "fadd double " |
223 case "+" => "fadd double " |
235 case "*" => "fmul double " |
224 case "*" => "fmul double " |
236 case "-" => "fsub double " |
225 case "-" => "fsub double " |
|
226 case "/" => "fdiv double " |
|
227 case "%" => "frem double " |
237 case "==" => "fcmp oeq double " |
228 case "==" => "fcmp oeq double " |
238 case "<=" => "fcmp ole double " |
229 case "!=" => "fcmp one double " |
239 case "<" => "fcmp olt double " |
230 case "<=" => "fcmp ole double " |
|
231 case "<" => "fcmp olt double " |
|
232 case ">=" => "icmp sge double " |
|
233 case ">" => "icmp sgt double " |
|
234 } |
|
235 |
|
236 def compile_args(vrs: List[KVal]) : List[String] = vrs match { |
|
237 case Nil => Nil |
|
238 case x::xs => s"${typeConversion(get_typ_val(x))} ${compile_val(x)}" :: compile_args(xs) |
240 } |
239 } |
241 |
240 |
242 // compile K values |
241 // compile K values |
243 def compile_val(v: KVal) : String = v match { |
242 def compile_val(v: KVal) : String = v match { |
244 case KNum(i) => s"$i" |
243 case KNum(i) => s"$i" |
245 case KFNum(i) => s"$i" |
244 case KFNum(d) => s"$d" |
246 case KChr(c) => s"$c" |
245 case KChConst(i) => s"$i" // as integer |
247 case KVar(s, ty) => s"%$s" |
246 case KVar(s, ty) => s"%$s" |
248 case KLoad(KVar(s, ty)) => s"load ${get_ty(ty)}, ${get_ty(ty)}* @$s" |
247 case KConst(s, ty) => { |
249 case Kop(op, x1, x2, ty) => ty match { |
248 val t = typeConversion(ty) |
250 case "Int" => s"${compile_op(op)} ${compile_val(x1)}, ${compile_val(x2)}" |
249 s"load $t, $t* @$s" |
251 case "Double" => s"${compile_dop(op)} ${compile_val(x1)}, ${compile_val(x2)}" |
250 } |
252 case _ => Kop(op, x1, x2, ty).toString |
251 case Kop(op, x1, x2, ty) => { |
253 } |
252 if (ty == "Double") { |
254 case KCall(fname, args, ty) => |
253 s"${compile_dop(op)} ${compile_val(x1)}, ${compile_val(x2)}" |
255 s"call ${get_ty(ty)} @$fname (${args.map(compile_call_arg).mkString(", ")})" |
254 } else if (ty == "Int") { |
|
255 s"${compile_op(op)} ${compile_val(x1)}, ${compile_val(x2)}" |
|
256 } else throw new Exception("Compile error: unknown type for comparison") |
|
257 } |
|
258 case KCall(x1, args, ty) => { |
|
259 s"call ${typeConversion(ty)} @$x1 (${compile_args(args).mkString(", ")})" |
|
260 } |
256 } |
261 } |
257 |
262 |
258 // compile K expressions |
263 // compile K expressions |
259 def compile_exp(a: KExp) : String = a match { |
264 def compile_exp(a: KExp) : String = a match { |
260 case KReturn(KVar("void", _)) => |
265 case KReturn(v) => { |
261 i"ret void" |
266 val ty = get_typ_val(v) |
262 case KReturn(KVar(x, ty)) => |
267 if (ty == "Void") { |
263 i"ret ${get_ty(ty)} %$x" |
268 i"ret void" |
264 case KReturn(KNum(i)) => |
269 } else { |
265 i"ret i32 $i" |
270 i"ret ${typeConversion(ty)} ${compile_val(v)}" |
266 case KLet(x: String, KCall(o: String, vrs: List[KVal], "Void"), e: KExp) => |
271 } |
267 i"${compile_val(KCall(o: String, vrs: List[KVal], "Void"))}" ++ compile_exp(e) |
272 } |
268 case KLet(x: String, v: KVal, e: KExp) => |
273 case KLet(x: String, v: KVal, e: KExp) => { |
269 i"%$x = ${compile_val(v)}" ++ compile_exp(e) |
274 val tv = get_typ_val(v) |
|
275 if (tv == "Void") { |
|
276 i"${compile_val(v)}" ++ compile_exp(e) |
|
277 } else i"%$x = ${compile_val(v)}" ++ compile_exp(e) |
|
278 } |
270 case KIf(x, e1, e2) => { |
279 case KIf(x, e1, e2) => { |
271 val if_br = Fresh("if_branch") |
280 val if_br = Fresh("if_branch") |
272 val else_br = Fresh("else_branch") |
281 val else_br = Fresh("else_branch") |
273 i"br i1 %$x, label %$if_br, label %$else_br" ++ |
282 i"br i1 %$x, label %$if_br, label %$else_br" ++ |
274 l"\n$if_br" ++ |
283 l"\n$if_br" ++ |
276 l"\n$else_br" ++ |
285 l"\n$else_br" ++ |
277 compile_exp(e2) |
286 compile_exp(e2) |
278 } |
287 } |
279 } |
288 } |
280 |
289 |
281 |
290 def compile_def_args(args: List[(String, String)], ts: TyEnv) : (List[String], TyEnv) = args match { |
282 val prelude = """ |
291 case Nil => (Nil, ts) |
283 declare i32 @printf(i8*, ...) |
292 case (n, t)::xs => { |
284 |
293 if (t == "Void") throw new Exception("Compile error: argument of type void is invalid") |
285 @.str_nl = private constant [2 x i8] c"\0A\00" |
294 val (rest, env) = compile_def_args(xs, ts + (n -> t)) |
286 @.str_star = private constant [2 x i8] c"*\00" |
295 (s"${typeConversion(t)} %$n" :: rest, env) |
287 @.str_space = private constant [2 x i8] c" \00" |
296 } |
288 |
297 } |
289 define void @new_line() #0 { |
298 |
290 %t0 = getelementptr [2 x i8], [2 x i8]* @.str_nl, i32 0, i32 0 |
|
291 %1 = call i32 (i8*, ...) @printf(i8* %t0) |
|
292 ret void |
|
293 } |
|
294 |
|
295 define void @print_star() #0 { |
|
296 %t0 = getelementptr [2 x i8], [2 x i8]* @.str_star, i32 0, i32 0 |
|
297 %1 = call i32 (i8*, ...) @printf(i8* %t0) |
|
298 ret void |
|
299 } |
|
300 |
|
301 define void @print_space() #0 { |
|
302 %t0 = getelementptr [2 x i8], [2 x i8]* @.str_space, i32 0, i32 0 |
|
303 %1 = call i32 (i8*, ...) @printf(i8* %t0) |
|
304 ret void |
|
305 } |
|
306 |
|
307 define void @skip() #0 { |
|
308 ret void |
|
309 } |
|
310 |
|
311 @.str_int = private constant [3 x i8] c"%d\00" |
|
312 |
|
313 define void @print_int(i32 %x) { |
|
314 %t0 = getelementptr [3 x i8], [3 x i8]* @.str_int, i32 0, i32 0 |
|
315 call i32 (i8*, ...) @printf(i8* %t0, i32 %x) |
|
316 ret void |
|
317 } |
|
318 |
|
319 @.str_char = private constant [3 x i8] c"%c\00" |
|
320 |
|
321 define void @print_char(i32 %x) { |
|
322 %t0 = getelementptr [3 x i8], [3 x i8]* @.str_char, i32 0, i32 0 |
|
323 call i32 (i8*, ...) @printf(i8* %t0, i32 %x) |
|
324 ret void |
|
325 } |
|
326 |
|
327 ; END OF BUILD-IN FUNCTIONS (prelude) |
|
328 |
|
329 """ |
|
330 |
|
331 def get_cont(ty: Ty) = ty match { |
|
332 case "Int" => KReturn |
|
333 case "Double" => KReturn |
|
334 case "Void" => { (_: KVal) => KReturn(KVar("void", "Void")) } |
|
335 } |
|
336 |
|
337 // compile function for declarations and main |
|
338 def compile_decl(d: Decl, ts: TyEnv) : (String, TyEnv) = d match { |
299 def compile_decl(d: Decl, ts: TyEnv) : (String, TyEnv) = d match { |
339 case Def(name, args, ty, body) => { |
300 case Const(name, value) => { |
340 val ts2 = ts + (name -> ty) |
301 (m"@$name = global i32 $value\n", ts + (name -> "Int")) |
341 val tkbody = typ_exp(CPS(body)(get_cont(ty)), ts2 ++ args.toMap) |
302 } |
342 (m"define ${get_ty(ty)} @$name (${args.map(compile_arg).mkString(",")}) {" ++ |
303 case FConst(name, value) => { |
343 compile_exp(tkbody) ++ |
304 (m"@$name = global double $value\n", ts + (name -> "Double")) |
344 m"}\n", ts2) |
305 } |
|
306 case Def(name, args, ty, body) => { |
|
307 val (argList, env1) = compile_def_args(args, ts + (name -> ty)) |
|
308 (m"define ${typeConversion(ty)} @$name (${argList.mkString(", ")}) {" ++ |
|
309 compile_exp(typ_exp(CPSi(body), env1)) ++ |
|
310 m"}\n", ts + (name -> ty)) // don't preserve local variables in environment |
345 } |
311 } |
346 case Main(body) => { |
312 case Main(body) => { |
347 val tbody = typ_exp(CPS(body)(_ => KReturn(KNum(0))), ts) |
|
348 (m"define i32 @main() {" ++ |
313 (m"define i32 @main() {" ++ |
349 compile_exp(tbody) ++ |
314 compile_exp(typ_exp(CPS(body)(_ => KReturn(KNum(0))), ts + ("main" -> "Int"))) ++ |
350 m"}\n", ts) |
315 m"}\n", ts + ("main" -> "Int")) |
351 } |
316 } |
352 case Const(name, n) => { |
317 } |
353 (m"@$name = global i32 $n\n", ts + (name -> "Int")) |
318 |
354 } |
319 // recursively update the typing environment while compiling |
355 case FConst(name, x) => { |
320 def compile_block(prog: List[Decl], ts: TyEnv) : (String, TyEnv) = prog match { |
356 (m"@$name = global double $x\n", ts + (name -> "Double")) |
321 case Nil => ("", ts) |
357 } |
322 case x::xs => { |
358 } |
323 val (compiled, env) = compile_decl(x, ts) |
359 |
324 val (compiled_block, env1) = compile_block(xs, env) |
360 def compile_prog(prog: List[Decl], ty: TyEnv) : String = prog match { |
325 (compiled ++ compiled_block, env1) |
361 case Nil => "" |
326 } |
362 case d::ds => { |
327 } |
363 val (s2, ty2) = compile_decl(d, ty) |
328 |
364 s2 ++ compile_prog(ds, ty2) |
329 def fun_compile(prog: List[Decl]) : String = { |
365 } |
330 val tyenv = initialEnv |
366 } |
331 val (compiled, _) = compile_block(prog, tyenv) |
367 // main compiler functions |
332 prelude ++ compiled |
368 def compile(prog: List[Decl]) : String = |
333 } |
369 prelude ++ compile_prog(prog, Map("new_line" -> "Void", "skip" -> "Void", |
|
370 "print_star" -> "Void", "print_space" -> "Void", |
|
371 "print_int" -> "Void", "print_char" -> "Void")) |
|
372 |
|
373 |
|
374 //import ammonite.ops._ |
|
375 |
334 |
376 |
335 |
377 @main |
336 @main |
378 def main(fname: String) = { |
337 def main(fname: String) = { |
379 val path = os.pwd / fname |
338 val path = os.pwd / fname |
380 val file = fname.stripSuffix("." ++ path.ext) |
339 val file = fname.stripSuffix("." ++ path.ext) |
381 val tks = tokenise(os.read(path)) |
340 val tks = tokenise(os.read(path)) |
382 val ast = parse_tks(tks) |
341 val ast = parse_tks(tks).head |
383 val code = compile(ast) |
342 val code = fun_compile(ast) |
384 println(code) |
343 println(code) |
385 } |
344 } |
386 |
345 |
387 @main |
346 @main |
388 def write(fname: String) = { |
347 def write(fname: String) = { |
389 val path = os.pwd / fname |
348 val path = os.pwd / fname |
390 val file = fname.stripSuffix("." ++ path.ext) |
349 val file = fname.stripSuffix("." ++ path.ext) |
391 val tks = tokenise(os.read(path)) |
350 val tks = tokenise(os.read(path)) |
392 val ast = parse_tks(tks) |
351 val ast = parse_tks(tks).head |
393 val code = compile(ast) |
352 val code = fun_compile(ast) |
394 //println(code) |
353 //println(code) |
395 os.write.over(os.pwd / (file ++ ".ll"), code) |
354 os.write.over(os.pwd / (file ++ ".ll"), code) |
396 } |
355 } |
397 |
356 |
398 @main |
357 @main |