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