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