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