1 | //===-- BrainF.cpp - BrainF compiler example ------------------------------===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // This class compiles the BrainF language into LLVM assembly. |
10 | // |
11 | // The BrainF language has 8 commands: |
12 | // Command Equivalent C Action |
13 | // ------- ------------ ------ |
14 | // , *h=getchar(); Read a character from stdin, 255 on EOF |
15 | // . putchar(*h); Write a character to stdout |
16 | // - --*h; Decrement tape |
17 | // + ++*h; Increment tape |
18 | // < --h; Move head left |
19 | // > ++h; Move head right |
20 | // [ while(*h) { Start loop |
21 | // ] } End loop |
22 | // |
23 | //===----------------------------------------------------------------------===// |
24 | |
25 | #include "BrainF.h" |
26 | #include "llvm/ADT/APInt.h" |
27 | #include "llvm/IR/BasicBlock.h" |
28 | #include "llvm/IR/Constant.h" |
29 | #include "llvm/IR/Constants.h" |
30 | #include "llvm/IR/DerivedTypes.h" |
31 | #include "llvm/IR/Function.h" |
32 | #include "llvm/IR/GlobalValue.h" |
33 | #include "llvm/IR/GlobalVariable.h" |
34 | #include "llvm/IR/InstrTypes.h" |
35 | #include "llvm/IR/Instruction.h" |
36 | #include "llvm/IR/Instructions.h" |
37 | #include "llvm/IR/Intrinsics.h" |
38 | #include "llvm/IR/Module.h" |
39 | #include "llvm/IR/Type.h" |
40 | #include "llvm/Support/Casting.h" |
41 | #include <cstdlib> |
42 | #include <iostream> |
43 | |
44 | using namespace llvm; |
45 | |
46 | //Set the constants for naming |
47 | const char *BrainF::tapereg = "tape" ; |
48 | const char *BrainF::headreg = "head" ; |
49 | const char *BrainF::label = "brainf" ; |
50 | const char *BrainF::testreg = "test" ; |
51 | |
52 | Module *BrainF::parse(std::istream *in1, int mem, CompileFlags cf, |
53 | LLVMContext& Context) { |
54 | in = in1; |
55 | memtotal = mem; |
56 | comflag = cf; |
57 | |
58 | header(C&: Context); |
59 | readloop(phi: nullptr, oldbb: nullptr, testbb: nullptr, Context); |
60 | delete builder; |
61 | return module; |
62 | } |
63 | |
64 | void BrainF::(LLVMContext& C) { |
65 | module = new Module("BrainF" , C); |
66 | |
67 | //Function prototypes |
68 | |
69 | //declare void @llvm.memset.p0i8.i32(i8 *, i8, i32, i1) |
70 | Type *Tys[] = {PointerType::getUnqual(C), Type::getInt32Ty(C)}; |
71 | Function *memset_func = Intrinsic::getDeclaration(M: module, Intrinsic::id: memset, |
72 | Tys); |
73 | |
74 | //declare i32 @getchar() |
75 | getchar_func = |
76 | module->getOrInsertFunction(Name: "getchar" , RetTy: IntegerType::getInt32Ty(C)); |
77 | |
78 | //declare i32 @putchar(i32) |
79 | putchar_func = module->getOrInsertFunction( |
80 | Name: "putchar" , RetTy: IntegerType::getInt32Ty(C), Args: IntegerType::getInt32Ty(C)); |
81 | |
82 | //Function header |
83 | |
84 | //define void @brainf() |
85 | brainf_func = Function::Create(Ty: FunctionType::get(Result: Type::getVoidTy(C), isVarArg: false), |
86 | Linkage: Function::ExternalLinkage, N: "brainf" , M: module); |
87 | |
88 | builder = new IRBuilder<>(BasicBlock::Create(Context&: C, Name: label, Parent: brainf_func)); |
89 | |
90 | //%arr = malloc i8, i32 %d |
91 | ConstantInt *val_mem = ConstantInt::get(Context&: C, V: APInt(32, memtotal)); |
92 | Type* IntPtrTy = IntegerType::getInt32Ty(C); |
93 | Type* Int8Ty = IntegerType::getInt8Ty(C); |
94 | Constant* allocsize = ConstantExpr::getSizeOf(Ty: Int8Ty); |
95 | allocsize = ConstantExpr::getTruncOrBitCast(C: allocsize, Ty: IntPtrTy); |
96 | ptr_arr = builder->CreateMalloc(IntPtrTy, AllocTy: Int8Ty, AllocSize: allocsize, ArraySize: val_mem, MallocF: nullptr, |
97 | Name: "arr" ); |
98 | |
99 | //call void @llvm.memset.p0i8.i32(i8 *%arr, i8 0, i32 %d, i1 0) |
100 | { |
101 | Value *memset_params[] = { |
102 | ptr_arr, |
103 | ConstantInt::get(Context&: C, V: APInt(8, 0)), |
104 | val_mem, |
105 | ConstantInt::get(Context&: C, V: APInt(1, 0)) |
106 | }; |
107 | |
108 | CallInst *memset_call = builder-> |
109 | CreateCall(Callee: memset_func, Args: memset_params); |
110 | memset_call->setTailCall(false); |
111 | } |
112 | |
113 | //%arrmax = getelementptr i8 *%arr, i32 %d |
114 | if (comflag & flag_arraybounds) { |
115 | ptr_arrmax = builder->CreateGEP( |
116 | Ty: Int8Ty, Ptr: ptr_arr, IdxList: ConstantInt::get(Context&: C, V: APInt(32, memtotal)), Name: "arrmax" ); |
117 | } |
118 | |
119 | //%head.%d = getelementptr i8 *%arr, i32 %d |
120 | curhead = builder->CreateGEP( |
121 | Ty: Int8Ty, Ptr: ptr_arr, IdxList: ConstantInt::get(Context&: C, V: APInt(32, memtotal / 2)), Name: headreg); |
122 | |
123 | //Function footer |
124 | |
125 | //brainf.end: |
126 | endbb = BasicBlock::Create(Context&: C, Name: label, Parent: brainf_func); |
127 | |
128 | // call free(i8 *%arr) |
129 | builder->SetInsertPoint(endbb); |
130 | builder->CreateFree(Source: ptr_arr); |
131 | |
132 | //ret void |
133 | ReturnInst::Create(C, InsertAtEnd: endbb); |
134 | |
135 | //Error block for array out of bounds |
136 | if (comflag & flag_arraybounds) |
137 | { |
138 | //@aberrormsg = internal constant [%d x i8] c"\00" |
139 | Constant *msg_0 = |
140 | ConstantDataArray::getString(Context&: C, Initializer: "Error: The head has left the tape." , |
141 | AddNull: true); |
142 | |
143 | GlobalVariable *aberrormsg = new GlobalVariable( |
144 | *module, |
145 | msg_0->getType(), |
146 | true, |
147 | GlobalValue::InternalLinkage, |
148 | msg_0, |
149 | "aberrormsg" ); |
150 | |
151 | //declare i32 @puts(i8 *) |
152 | FunctionCallee puts_func = module->getOrInsertFunction( |
153 | Name: "puts" , RetTy: IntegerType::getInt32Ty(C), |
154 | Args: PointerType::getUnqual(ElementType: IntegerType::getInt8Ty(C))); |
155 | |
156 | //brainf.aberror: |
157 | aberrorbb = BasicBlock::Create(Context&: C, Name: label, Parent: brainf_func); |
158 | |
159 | //call i32 @puts(i8 *getelementptr([%d x i8] *@aberrormsg, i32 0, i32 0)) |
160 | { |
161 | Constant *zero_32 = Constant::getNullValue(Ty: IntegerType::getInt32Ty(C)); |
162 | |
163 | Constant *gep_params[] = { |
164 | zero_32, |
165 | zero_32 |
166 | }; |
167 | |
168 | Constant *msgptr = ConstantExpr:: |
169 | getGetElementPtr(Ty: aberrormsg->getValueType(), C: aberrormsg, IdxList: gep_params); |
170 | |
171 | Value *puts_params[] = { |
172 | msgptr |
173 | }; |
174 | |
175 | CallInst *puts_call = |
176 | CallInst::Create(Func: puts_func, |
177 | Args: puts_params, |
178 | NameStr: "" , InsertAtEnd: aberrorbb); |
179 | puts_call->setTailCall(false); |
180 | } |
181 | |
182 | //br label %brainf.end |
183 | BranchInst::Create(IfTrue: endbb, InsertAtEnd: aberrorbb); |
184 | } |
185 | } |
186 | |
187 | void BrainF::readloop(PHINode *phi, BasicBlock *oldbb, BasicBlock *testbb, |
188 | LLVMContext &C) { |
189 | Symbol cursym = SYM_NONE; |
190 | int curvalue = 0; |
191 | Symbol nextsym = SYM_NONE; |
192 | int nextvalue = 0; |
193 | char c; |
194 | int loop; |
195 | int direction; |
196 | Type *Int8Ty = IntegerType::getInt8Ty(C); |
197 | |
198 | while(cursym != SYM_EOF && cursym != SYM_ENDLOOP) { |
199 | // Write out commands |
200 | switch(cursym) { |
201 | case SYM_NONE: |
202 | // Do nothing |
203 | break; |
204 | |
205 | case SYM_READ: |
206 | { |
207 | //%tape.%d = call i32 @getchar() |
208 | CallInst *getchar_call = |
209 | builder->CreateCall(Callee: getchar_func, Args: {}, Name: tapereg); |
210 | getchar_call->setTailCall(false); |
211 | Value *tape_0 = getchar_call; |
212 | |
213 | //%tape.%d = trunc i32 %tape.%d to i8 |
214 | Value *tape_1 = builder-> |
215 | CreateTrunc(V: tape_0, DestTy: IntegerType::getInt8Ty(C), Name: tapereg); |
216 | |
217 | //store i8 %tape.%d, i8 *%head.%d |
218 | builder->CreateStore(Val: tape_1, Ptr: curhead); |
219 | } |
220 | break; |
221 | |
222 | case SYM_WRITE: |
223 | { |
224 | //%tape.%d = load i8 *%head.%d |
225 | LoadInst *tape_0 = builder->CreateLoad(Ty: Int8Ty, Ptr: curhead, Name: tapereg); |
226 | |
227 | //%tape.%d = sext i8 %tape.%d to i32 |
228 | Value *tape_1 = builder-> |
229 | CreateSExt(V: tape_0, DestTy: IntegerType::getInt32Ty(C), Name: tapereg); |
230 | |
231 | //call i32 @putchar(i32 %tape.%d) |
232 | Value *putchar_params[] = { |
233 | tape_1 |
234 | }; |
235 | CallInst *putchar_call = builder-> |
236 | CreateCall(Callee: putchar_func, |
237 | Args: putchar_params); |
238 | putchar_call->setTailCall(false); |
239 | } |
240 | break; |
241 | |
242 | case SYM_MOVE: |
243 | { |
244 | //%head.%d = getelementptr i8 *%head.%d, i32 %d |
245 | curhead = builder->CreateGEP(Ty: Int8Ty, Ptr: curhead, |
246 | IdxList: ConstantInt::get(Context&: C, V: APInt(32, curvalue)), |
247 | Name: headreg); |
248 | |
249 | //Error block for array out of bounds |
250 | if (comflag & flag_arraybounds) |
251 | { |
252 | //%test.%d = icmp uge i8 *%head.%d, %arrmax |
253 | Value *test_0 = builder-> |
254 | CreateICmpUGE(LHS: curhead, RHS: ptr_arrmax, Name: testreg); |
255 | |
256 | //%test.%d = icmp ult i8 *%head.%d, %arr |
257 | Value *test_1 = builder-> |
258 | CreateICmpULT(LHS: curhead, RHS: ptr_arr, Name: testreg); |
259 | |
260 | //%test.%d = or i1 %test.%d, %test.%d |
261 | Value *test_2 = builder-> |
262 | CreateOr(LHS: test_0, RHS: test_1, Name: testreg); |
263 | |
264 | //br i1 %test.%d, label %main.%d, label %main.%d |
265 | BasicBlock *nextbb = BasicBlock::Create(Context&: C, Name: label, Parent: brainf_func); |
266 | builder->CreateCondBr(Cond: test_2, True: aberrorbb, False: nextbb); |
267 | |
268 | //main.%d: |
269 | builder->SetInsertPoint(nextbb); |
270 | } |
271 | } |
272 | break; |
273 | |
274 | case SYM_CHANGE: |
275 | { |
276 | //%tape.%d = load i8 *%head.%d |
277 | LoadInst *tape_0 = builder->CreateLoad(Ty: Int8Ty, Ptr: curhead, Name: tapereg); |
278 | |
279 | //%tape.%d = add i8 %tape.%d, %d |
280 | Value *tape_1 = builder-> |
281 | CreateAdd(LHS: tape_0, RHS: ConstantInt::get(Context&: C, V: APInt(8, curvalue)), Name: tapereg); |
282 | |
283 | //store i8 %tape.%d, i8 *%head.%d\n" |
284 | builder->CreateStore(Val: tape_1, Ptr: curhead); |
285 | } |
286 | break; |
287 | |
288 | case SYM_LOOP: |
289 | { |
290 | //br label %main.%d |
291 | BasicBlock *testbb = BasicBlock::Create(Context&: C, Name: label, Parent: brainf_func); |
292 | builder->CreateBr(Dest: testbb); |
293 | |
294 | //main.%d: |
295 | BasicBlock *bb_0 = builder->GetInsertBlock(); |
296 | BasicBlock *bb_1 = BasicBlock::Create(Context&: C, Name: label, Parent: brainf_func); |
297 | builder->SetInsertPoint(bb_1); |
298 | |
299 | // Make part of PHI instruction now, wait until end of loop to finish |
300 | PHINode *phi_0 = PHINode::Create(Ty: PointerType::getUnqual(ElementType: Int8Ty), NumReservedValues: 2, |
301 | NameStr: headreg, InsertAtEnd: testbb); |
302 | phi_0->addIncoming(V: curhead, BB: bb_0); |
303 | curhead = phi_0; |
304 | |
305 | readloop(phi: phi_0, oldbb: bb_1, testbb, C); |
306 | } |
307 | break; |
308 | |
309 | default: |
310 | std::cerr << "Error: Unknown symbol.\n" ; |
311 | abort(); |
312 | break; |
313 | } |
314 | |
315 | cursym = nextsym; |
316 | curvalue = nextvalue; |
317 | nextsym = SYM_NONE; |
318 | |
319 | // Reading stdin loop |
320 | loop = (cursym == SYM_NONE) |
321 | || (cursym == SYM_MOVE) |
322 | || (cursym == SYM_CHANGE); |
323 | while(loop) { |
324 | *in>>c; |
325 | if (in->eof()) { |
326 | if (cursym == SYM_NONE) { |
327 | cursym = SYM_EOF; |
328 | } else { |
329 | nextsym = SYM_EOF; |
330 | } |
331 | loop = 0; |
332 | } else { |
333 | direction = 1; |
334 | switch(c) { |
335 | case '-': |
336 | direction = -1; |
337 | [[fallthrough]]; |
338 | |
339 | case '+': |
340 | if (cursym == SYM_CHANGE) { |
341 | curvalue += direction; |
342 | // loop = 1 |
343 | } else { |
344 | if (cursym == SYM_NONE) { |
345 | cursym = SYM_CHANGE; |
346 | curvalue = direction; |
347 | // loop = 1 |
348 | } else { |
349 | nextsym = SYM_CHANGE; |
350 | nextvalue = direction; |
351 | loop = 0; |
352 | } |
353 | } |
354 | break; |
355 | |
356 | case '<': |
357 | direction = -1; |
358 | [[fallthrough]]; |
359 | |
360 | case '>': |
361 | if (cursym == SYM_MOVE) { |
362 | curvalue += direction; |
363 | // loop = 1 |
364 | } else { |
365 | if (cursym == SYM_NONE) { |
366 | cursym = SYM_MOVE; |
367 | curvalue = direction; |
368 | // loop = 1 |
369 | } else { |
370 | nextsym = SYM_MOVE; |
371 | nextvalue = direction; |
372 | loop = 0; |
373 | } |
374 | } |
375 | break; |
376 | |
377 | case ',': |
378 | if (cursym == SYM_NONE) { |
379 | cursym = SYM_READ; |
380 | } else { |
381 | nextsym = SYM_READ; |
382 | } |
383 | loop = 0; |
384 | break; |
385 | |
386 | case '.': |
387 | if (cursym == SYM_NONE) { |
388 | cursym = SYM_WRITE; |
389 | } else { |
390 | nextsym = SYM_WRITE; |
391 | } |
392 | loop = 0; |
393 | break; |
394 | |
395 | case '[': |
396 | if (cursym == SYM_NONE) { |
397 | cursym = SYM_LOOP; |
398 | } else { |
399 | nextsym = SYM_LOOP; |
400 | } |
401 | loop = 0; |
402 | break; |
403 | |
404 | case ']': |
405 | if (cursym == SYM_NONE) { |
406 | cursym = SYM_ENDLOOP; |
407 | } else { |
408 | nextsym = SYM_ENDLOOP; |
409 | } |
410 | loop = 0; |
411 | break; |
412 | |
413 | // Ignore other characters |
414 | default: |
415 | break; |
416 | } |
417 | } |
418 | } |
419 | } |
420 | |
421 | if (cursym == SYM_ENDLOOP) { |
422 | if (!phi) { |
423 | std::cerr << "Error: Extra ']'\n" ; |
424 | abort(); |
425 | } |
426 | |
427 | // Write loop test |
428 | { |
429 | //br label %main.%d |
430 | builder->CreateBr(Dest: testbb); |
431 | |
432 | //main.%d: |
433 | |
434 | //%head.%d = phi i8 *[%head.%d, %main.%d], [%head.%d, %main.%d] |
435 | //Finish phi made at beginning of loop |
436 | phi->addIncoming(V: curhead, BB: builder->GetInsertBlock()); |
437 | Value *head_0 = phi; |
438 | |
439 | //%tape.%d = load i8 *%head.%d |
440 | LoadInst *tape_0 = new LoadInst(Int8Ty, head_0, tapereg, testbb); |
441 | |
442 | //%test.%d = icmp eq i8 %tape.%d, 0 |
443 | ICmpInst *test_0 = new ICmpInst(*testbb, ICmpInst::ICMP_EQ, tape_0, |
444 | ConstantInt::get(Context&: C, V: APInt(8, 0)), testreg); |
445 | |
446 | //br i1 %test.%d, label %main.%d, label %main.%d |
447 | BasicBlock *bb_0 = BasicBlock::Create(Context&: C, Name: label, Parent: brainf_func); |
448 | BranchInst::Create(IfTrue: bb_0, IfFalse: oldbb, Cond: test_0, InsertAtEnd: testbb); |
449 | |
450 | //main.%d: |
451 | builder->SetInsertPoint(bb_0); |
452 | |
453 | //%head.%d = phi i8 *[%head.%d, %main.%d] |
454 | PHINode *phi_1 = |
455 | builder->CreatePHI(Ty: PointerType::getUnqual(ElementType: Int8Ty), NumReservedValues: 1, Name: headreg); |
456 | phi_1->addIncoming(V: head_0, BB: testbb); |
457 | curhead = phi_1; |
458 | } |
459 | |
460 | return; |
461 | } |
462 | |
463 | //End of the program, so go to return block |
464 | builder->CreateBr(Dest: endbb); |
465 | |
466 | if (phi) { |
467 | std::cerr << "Error: Missing ']'\n" ; |
468 | abort(); |
469 | } |
470 | } |
471 | |