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 BB->getInstList().push_back(cast<Instruction>(ptr_arr));
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->
118 CreateGEP(ptr_arr, ConstantInt::get(C, APInt(32, memtotal)), "arrmax");
119 }
120
121 //%head.%d = getelementptr i8 *%arr, i32 %d
122 curhead = builder->CreateGEP(ptr_arr,
123 ConstantInt::get(C, APInt(32, memtotal/2)),
124 headreg);
125
126 //Function footer
127
128 //brainf.end:
129 endbb = BasicBlock::Create(C, label, brainf_func);
130
131 //call free(i8 *%arr)
132 endbb->getInstList().push_back(CallInst::CreateFree(ptr_arr, endbb));
133
134 //ret void
135 ReturnInst::Create(C, endbb);
136
137 //Error block for array out of bounds
138 if (comflag & flag_arraybounds)
139 {
140 //@aberrormsg = internal constant [%d x i8] c"\00"
141 Constant *msg_0 =
142 ConstantDataArray::getString(C, "Error: The head has left the tape.",
143 true);
144
145 GlobalVariable *aberrormsg = new GlobalVariable(
146 *module,
147 msg_0->getType(),
148 true,
149 GlobalValue::InternalLinkage,
150 msg_0,
151 "aberrormsg");
152
153 //declare i32 @puts(i8 *)
154 FunctionCallee puts_func = module->getOrInsertFunction(
155 "puts", IntegerType::getInt32Ty(C),
156 PointerType::getUnqual(IntegerType::getInt8Ty(C)));
157
158 //brainf.aberror:
159 aberrorbb = BasicBlock::Create(C, label, brainf_func);
160
161 //call i32 @puts(i8 *getelementptr([%d x i8] *@aberrormsg, i32 0, i32 0))
162 {
163 Constant *zero_32 = Constant::getNullValue(IntegerType::getInt32Ty(C));
164
165 Constant *gep_params[] = {
166 zero_32,
167 zero_32
168 };
169
170 Constant *msgptr = ConstantExpr::
171 getGetElementPtr(aberrormsg->getValueType(), aberrormsg, gep_params);
172
173 Value *puts_params[] = {
174 msgptr
175 };
176
177 CallInst *puts_call =
178 CallInst::Create(puts_func,
179 puts_params,
180 "", aberrorbb);
181 puts_call->setTailCall(false);
182 }
183
184 //br label %brainf.end
185 BranchInst::Create(endbb, aberrorbb);
186 }
187 }
188
readloop(PHINode * phi,BasicBlock * oldbb,BasicBlock * testbb,LLVMContext & C)189 void BrainF::readloop(PHINode *phi, BasicBlock *oldbb, BasicBlock *testbb,
190 LLVMContext &C) {
191 Symbol cursym = SYM_NONE;
192 int curvalue = 0;
193 Symbol nextsym = SYM_NONE;
194 int nextvalue = 0;
195 char c;
196 int loop;
197 int direction;
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 =
227 builder->CreateLoad(IntegerType::getInt8Ty(C), 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 =
280 builder->CreateLoad(IntegerType::getInt8Ty(C), curhead, tapereg);
281
282 //%tape.%d = add i8 %tape.%d, %d
283 Value *tape_1 = builder->
284 CreateAdd(tape_0, ConstantInt::get(C, APInt(8, curvalue)), tapereg);
285
286 //store i8 %tape.%d, i8 *%head.%d\n"
287 builder->CreateStore(tape_1, curhead);
288 }
289 break;
290
291 case SYM_LOOP:
292 {
293 //br label %main.%d
294 BasicBlock *testbb = BasicBlock::Create(C, label, brainf_func);
295 builder->CreateBr(testbb);
296
297 //main.%d:
298 BasicBlock *bb_0 = builder->GetInsertBlock();
299 BasicBlock *bb_1 = BasicBlock::Create(C, label, brainf_func);
300 builder->SetInsertPoint(bb_1);
301
302 // Make part of PHI instruction now, wait until end of loop to finish
303 PHINode *phi_0 =
304 PHINode::Create(PointerType::getUnqual(IntegerType::getInt8Ty(C)),
305 2, headreg, testbb);
306 phi_0->addIncoming(curhead, bb_0);
307 curhead = phi_0;
308
309 readloop(phi_0, bb_1, testbb, C);
310 }
311 break;
312
313 default:
314 std::cerr << "Error: Unknown symbol.\n";
315 abort();
316 break;
317 }
318
319 cursym = nextsym;
320 curvalue = nextvalue;
321 nextsym = SYM_NONE;
322
323 // Reading stdin loop
324 loop = (cursym == SYM_NONE)
325 || (cursym == SYM_MOVE)
326 || (cursym == SYM_CHANGE);
327 while(loop) {
328 *in>>c;
329 if (in->eof()) {
330 if (cursym == SYM_NONE) {
331 cursym = SYM_EOF;
332 } else {
333 nextsym = SYM_EOF;
334 }
335 loop = 0;
336 } else {
337 direction = 1;
338 switch(c) {
339 case '-':
340 direction = -1;
341 LLVM_FALLTHROUGH;
342
343 case '+':
344 if (cursym == SYM_CHANGE) {
345 curvalue += direction;
346 // loop = 1
347 } else {
348 if (cursym == SYM_NONE) {
349 cursym = SYM_CHANGE;
350 curvalue = direction;
351 // loop = 1
352 } else {
353 nextsym = SYM_CHANGE;
354 nextvalue = direction;
355 loop = 0;
356 }
357 }
358 break;
359
360 case '<':
361 direction = -1;
362 LLVM_FALLTHROUGH;
363
364 case '>':
365 if (cursym == SYM_MOVE) {
366 curvalue += direction;
367 // loop = 1
368 } else {
369 if (cursym == SYM_NONE) {
370 cursym = SYM_MOVE;
371 curvalue = direction;
372 // loop = 1
373 } else {
374 nextsym = SYM_MOVE;
375 nextvalue = direction;
376 loop = 0;
377 }
378 }
379 break;
380
381 case ',':
382 if (cursym == SYM_NONE) {
383 cursym = SYM_READ;
384 } else {
385 nextsym = SYM_READ;
386 }
387 loop = 0;
388 break;
389
390 case '.':
391 if (cursym == SYM_NONE) {
392 cursym = SYM_WRITE;
393 } else {
394 nextsym = SYM_WRITE;
395 }
396 loop = 0;
397 break;
398
399 case '[':
400 if (cursym == SYM_NONE) {
401 cursym = SYM_LOOP;
402 } else {
403 nextsym = SYM_LOOP;
404 }
405 loop = 0;
406 break;
407
408 case ']':
409 if (cursym == SYM_NONE) {
410 cursym = SYM_ENDLOOP;
411 } else {
412 nextsym = SYM_ENDLOOP;
413 }
414 loop = 0;
415 break;
416
417 // Ignore other characters
418 default:
419 break;
420 }
421 }
422 }
423 }
424
425 if (cursym == SYM_ENDLOOP) {
426 if (!phi) {
427 std::cerr << "Error: Extra ']'\n";
428 abort();
429 }
430
431 // Write loop test
432 {
433 //br label %main.%d
434 builder->CreateBr(testbb);
435
436 //main.%d:
437
438 //%head.%d = phi i8 *[%head.%d, %main.%d], [%head.%d, %main.%d]
439 //Finish phi made at beginning of loop
440 phi->addIncoming(curhead, builder->GetInsertBlock());
441 Value *head_0 = phi;
442
443 //%tape.%d = load i8 *%head.%d
444 LoadInst *tape_0 = new LoadInst(IntegerType::getInt8Ty(C), head_0,
445 tapereg, testbb);
446
447 //%test.%d = icmp eq i8 %tape.%d, 0
448 ICmpInst *test_0 = new ICmpInst(*testbb, ICmpInst::ICMP_EQ, tape_0,
449 ConstantInt::get(C, APInt(8, 0)), testreg);
450
451 //br i1 %test.%d, label %main.%d, label %main.%d
452 BasicBlock *bb_0 = BasicBlock::Create(C, label, brainf_func);
453 BranchInst::Create(bb_0, oldbb, test_0, testbb);
454
455 //main.%d:
456 builder->SetInsertPoint(bb_0);
457
458 //%head.%d = phi i8 *[%head.%d, %main.%d]
459 PHINode *phi_1 = builder->
460 CreatePHI(PointerType::getUnqual(IntegerType::getInt8Ty(C)), 1,
461 headreg);
462 phi_1->addIncoming(head_0, testbb);
463 curhead = phi_1;
464 }
465
466 return;
467 }
468
469 //End of the program, so go to return block
470 builder->CreateBr(endbb);
471
472 if (phi) {
473 std::cerr << "Error: Missing ']'\n";
474 abort();
475 }
476 }
477