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