654
|
1 |
// A Small LLVM Compiler for a Simple Functional Language
|
644
|
2 |
// (includes an external lexer and parser)
|
645
|
3 |
//
|
813
|
4 |
//
|
645
|
5 |
// call with
|
|
6 |
//
|
813
|
7 |
// amm fun_llvm.sc main fact.fun
|
|
8 |
// amm fun_llvm.sc main defs.fun
|
|
9 |
//
|
|
10 |
// or
|
|
11 |
//
|
789
|
12 |
// amm fun_llvm.sc write fact.fun
|
|
13 |
// amm fun_llvm.sc write defs.fun
|
645
|
14 |
//
|
813
|
15 |
// this will generate an .ll file.
|
|
16 |
//
|
|
17 |
// or
|
654
|
18 |
//
|
813
|
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
|
655
|
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 |
//
|
813
|
32 |
// The code produced for the various architectures can be obtain with
|
655
|
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 |
|
645
|
43 |
|
789
|
44 |
import $file.fun_tokens, fun_tokens._
|
|
45 |
import $file.fun_parser, fun_parser._
|
626
|
46 |
|
|
47 |
|
220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
48 |
// for generating new labels
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
49 |
var counter = -1
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
50 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
51 |
def Fresh(x: String) = {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
52 |
counter += 1
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
53 |
x ++ "_" ++ counter.toString()
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
54 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
55 |
|
678
|
56 |
// Internal CPS language for FUN
|
648
|
57 |
abstract class KExp
|
653
|
58 |
abstract class KVal
|
648
|
59 |
|
653
|
60 |
case class KVar(s: String) extends KVal
|
|
61 |
case class KNum(i: Int) extends KVal
|
656
|
62 |
case class Kop(o: String, v1: KVal, v2: KVal) extends KVal
|
653
|
63 |
case class KCall(o: String, vrs: List[KVal]) extends KVal
|
655
|
64 |
case class KWrite(v: KVal) extends KVal
|
649
|
65 |
|
653
|
66 |
case class KIf(x1: String, e1: KExp, e2: KExp) extends KExp {
|
|
67 |
override def toString = s"KIf $x1\nIF\n$e1\nELSE\n$e2"
|
649
|
68 |
}
|
653
|
69 |
case class KLet(x: String, e1: KVal, e2: KExp) extends KExp {
|
648
|
70 |
override def toString = s"let $x = $e1 in \n$e2"
|
|
71 |
}
|
653
|
72 |
case class KReturn(v: KVal) extends KExp
|
648
|
73 |
|
654
|
74 |
|
655
|
75 |
// CPS translation from Exps to KExps using a
|
654
|
76 |
// continuation k.
|
653
|
77 |
def CPS(e: Exp)(k: KVal => KExp) : KExp = e match {
|
|
78 |
case Var(s) => k(KVar(s))
|
|
79 |
case Num(i) => k(KNum(i))
|
|
80 |
case Aop(o, e1, e2) => {
|
|
81 |
val z = Fresh("tmp")
|
|
82 |
CPS(e1)(y1 =>
|
656
|
83 |
CPS(e2)(y2 => KLet(z, Kop(o, y1, y2), k(KVar(z)))))
|
653
|
84 |
}
|
|
85 |
case If(Bop(o, b1, b2), e1, e2) => {
|
|
86 |
val z = Fresh("tmp")
|
|
87 |
CPS(b1)(y1 =>
|
655
|
88 |
CPS(b2)(y2 =>
|
656
|
89 |
KLet(z, Kop(o, y1, y2), KIf(z, CPS(e1)(k), CPS(e2)(k)))))
|
653
|
90 |
}
|
|
91 |
case Call(name, args) => {
|
|
92 |
def aux(args: List[Exp], vs: List[KVal]) : KExp = args match {
|
|
93 |
case Nil => {
|
|
94 |
val z = Fresh("tmp")
|
|
95 |
KLet(z, KCall(name, vs), k(KVar(z)))
|
|
96 |
}
|
|
97 |
case e::es => CPS(e)(y => aux(es, vs ::: List(y)))
|
648
|
98 |
}
|
653
|
99 |
aux(args, Nil)
|
|
100 |
}
|
656
|
101 |
case Sequence(e1, e2) =>
|
679
|
102 |
CPS(e1)(_ => CPS(e2)(y2 => k(y2)))
|
655
|
103 |
case Write(e) => {
|
|
104 |
val z = Fresh("tmp")
|
|
105 |
CPS(e)(y => KLet(z, KWrite(y), k(KVar(z))))
|
|
106 |
}
|
653
|
107 |
}
|
|
108 |
|
679
|
109 |
//initial continuation
|
653
|
110 |
def CPSi(e: Exp) = CPS(e)(KReturn)
|
|
111 |
|
654
|
112 |
// some testcases
|
653
|
113 |
val e1 = Aop("*", Var("a"), Num(3))
|
654
|
114 |
CPSi(e1)
|
653
|
115 |
|
|
116 |
val e2 = Aop("+", Aop("*", Var("a"), Num(3)), Num(4))
|
654
|
117 |
CPSi(e2)
|
653
|
118 |
|
|
119 |
val e3 = Aop("+", Num(2), Aop("*", Var("a"), Num(3)))
|
654
|
120 |
CPSi(e3)
|
648
|
121 |
|
653
|
122 |
val e4 = Aop("+", Aop("-", Num(1), Num(2)), Aop("*", Var("a"), Num(3)))
|
654
|
123 |
CPSi(e4)
|
653
|
124 |
|
|
125 |
val e5 = If(Bop("==", Num(1), Num(1)), Num(3), Num(4))
|
654
|
126 |
CPSi(e5)
|
653
|
127 |
|
|
128 |
val e6 = If(Bop("!=", Num(10), Num(10)), e5, Num(40))
|
654
|
129 |
CPSi(e6)
|
648
|
130 |
|
653
|
131 |
val e7 = Call("foo", List(Num(3)))
|
654
|
132 |
CPSi(e7)
|
653
|
133 |
|
705
|
134 |
val e8 = Call("foo", List(Aop("*", Num(3), Num(1)), Num(4), Aop("+", Num(5), Num(6))))
|
654
|
135 |
CPSi(e8)
|
653
|
136 |
|
|
137 |
val e9 = Sequence(Aop("*", Var("a"), Num(3)), Aop("+", Var("b"), Num(6)))
|
654
|
138 |
CPSi(e9)
|
649
|
139 |
|
|
140 |
val e = Aop("*", Aop("+", Num(1), Call("foo", List(Var("a"), Num(3)))), Num(4))
|
654
|
141 |
CPSi(e)
|
653
|
142 |
|
648
|
143 |
|
|
144 |
|
|
145 |
|
625
|
146 |
// convenient string interpolations
|
|
147 |
// for instructions, labels and methods
|
|
148 |
import scala.language.implicitConversions
|
|
149 |
import scala.language.reflectiveCalls
|
|
150 |
|
|
151 |
implicit def sring_inters(sc: StringContext) = new {
|
|
152 |
def i(args: Any*): String = " " ++ sc.s(args:_*) ++ "\n"
|
|
153 |
def l(args: Any*): String = sc.s(args:_*) ++ ":\n"
|
|
154 |
def m(args: Any*): String = sc.s(args:_*) ++ "\n"
|
|
155 |
}
|
|
156 |
|
656
|
157 |
// mathematical and boolean operations
|
653
|
158 |
def compile_op(op: String) = op match {
|
|
159 |
case "+" => "add i32 "
|
|
160 |
case "*" => "mul i32 "
|
|
161 |
case "-" => "sub i32 "
|
656
|
162 |
case "/" => "sdiv i32 "
|
|
163 |
case "%" => "srem i32 "
|
653
|
164 |
case "==" => "icmp eq i32 "
|
813
|
165 |
case "<=" => "icmp sle i32 " // signed less or equal
|
|
166 |
case "<" => "icmp slt i32 " // signed less than
|
653
|
167 |
}
|
220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
168 |
|
813
|
169 |
// compile K values
|
653
|
170 |
def compile_val(v: KVal) : String = v match {
|
|
171 |
case KNum(i) => s"$i"
|
|
172 |
case KVar(s) => s"%$s"
|
656
|
173 |
case Kop(op, x1, x2) =>
|
653
|
174 |
s"${compile_op(op)} ${compile_val(x1)}, ${compile_val(x2)}"
|
|
175 |
case KCall(x1, args) =>
|
|
176 |
s"call i32 @$x1 (${args.map(compile_val).mkString("i32 ", ", i32 ", "")})"
|
655
|
177 |
case KWrite(x1) =>
|
|
178 |
s"call i32 @printInt (i32 ${compile_val(x1)})"
|
653
|
179 |
}
|
648
|
180 |
|
649
|
181 |
// compile K expressions
|
|
182 |
def compile_exp(a: KExp) : String = a match {
|
653
|
183 |
case KReturn(v) =>
|
|
184 |
i"ret i32 ${compile_val(v)}"
|
|
185 |
case KLet(x: String, v: KVal, e: KExp) =>
|
|
186 |
i"%$x = ${compile_val(v)}" ++ compile_exp(e)
|
|
187 |
case KIf(x, e1, e2) => {
|
679
|
188 |
val if_br = Fresh("if_branch")
|
|
189 |
val else_br = Fresh("else_branch")
|
649
|
190 |
i"br i1 %$x, label %$if_br, label %$else_br" ++
|
|
191 |
l"\n$if_br" ++
|
653
|
192 |
compile_exp(e1) ++
|
649
|
193 |
l"\n$else_br" ++
|
653
|
194 |
compile_exp(e2)
|
220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
195 |
}
|
653
|
196 |
}
|
|
197 |
|
655
|
198 |
|
|
199 |
val prelude = """
|
|
200 |
@.str = private constant [4 x i8] c"%d\0A\00"
|
|
201 |
|
|
202 |
declare i32 @printf(i8*, ...)
|
220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
203 |
|
655
|
204 |
define i32 @printInt(i32 %x) {
|
|
205 |
%t0 = getelementptr [4 x i8], [4 x i8]* @.str, i32 0, i32 0
|
679
|
206 |
call i32 (i8*, ...) @printf(i8* %t0, i32 %x)
|
655
|
207 |
ret i32 %x
|
|
208 |
}
|
|
209 |
|
|
210 |
"""
|
653
|
211 |
|
220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
212 |
|
625
|
213 |
// compile function for declarations and main
|
|
214 |
def compile_decl(d: Decl) : String = d match {
|
649
|
215 |
case Def(name, args, body) => {
|
|
216 |
m"define i32 @$name (${args.mkString("i32 %", ", i32 %", "")}) {" ++
|
653
|
217 |
compile_exp(CPSi(body)) ++
|
649
|
218 |
m"}\n"
|
221
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
219 |
}
|
649
|
220 |
case Main(body) => {
|
|
221 |
m"define i32 @main() {" ++
|
789
|
222 |
compile_exp(CPS(body)(_ => KReturn(KNum(0)))) ++
|
649
|
223 |
m"}\n"
|
221
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
224 |
}
|
220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
225 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
226 |
|
813
|
227 |
|
626
|
228 |
// main compiler functions
|
813
|
229 |
def compile(prog: List[Decl]) : String =
|
789
|
230 |
prelude ++ (prog.map(compile_decl).mkString)
|
|
231 |
|
220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
232 |
|
813
|
233 |
import ammonite.ops._
|
|
234 |
|
|
235 |
|
789
|
236 |
@main
|
813
|
237 |
def main(fname: String) = {
|
789
|
238 |
val path = os.pwd / fname
|
|
239 |
val file = fname.stripSuffix("." ++ path.ext)
|
|
240 |
val tks = tokenise(os.read(path))
|
|
241 |
val ast = parse_tks(tks)
|
813
|
242 |
println(compile(ast))
|
644
|
243 |
}
|
|
244 |
|
789
|
245 |
@main
|
|
246 |
def write(fname: String) = {
|
|
247 |
val path = os.pwd / fname
|
|
248 |
val file = fname.stripSuffix("." ++ path.ext)
|
|
249 |
val tks = tokenise(os.read(path))
|
|
250 |
val ast = parse_tks(tks)
|
813
|
251 |
val code = compile(ast)
|
789
|
252 |
os.write.over(os.pwd / (file ++ ".ll"), code)
|
626
|
253 |
}
|
|
254 |
|
789
|
255 |
@main
|
|
256 |
def run(fname: String) = {
|
|
257 |
val path = os.pwd / fname
|
|
258 |
val file = fname.stripSuffix("." ++ path.ext)
|
813
|
259 |
write(fname)
|
789
|
260 |
os.proc("llc", "-filetype=obj", file ++ ".ll").call()
|
813
|
261 |
os.proc("gcc", file ++ ".o", "-o", file ++ ".bin").call()
|
|
262 |
os.proc(os.pwd / (file ++ ".bin")).call(stdout = os.Inherit)
|
|
263 |
println(s"done.")
|
657
|
264 |
}
|
644
|
265 |
|
657
|
266 |
|
|
267 |
|
|
268 |
|
|
269 |
|