1 //===-- BrainF.cpp - BrainF compiler example ----------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===--------------------------------------------------------------------===//
10 // This class compiles the BrainF language into LLVM assembly.
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
24 //===--------------------------------------------------------------------===//
27 #include "llvm/ADT/STLExtras.h"
28 #include "llvm/IR/Constants.h"
29 #include "llvm/IR/Instructions.h"
30 #include "llvm/IR/Intrinsics.h"
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";
40 Module *BrainF::parse(std::istream *in1, int mem, CompileFlags cf,
41 LLVMContext& Context) {
47 readloop(0, 0, 0, Context);
52 void BrainF::header(LLVMContext& C) {
53 module = new Module("BrainF", C);
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,
62 //declare i32 @getchar()
63 getchar_func = cast<Function>(module->
64 getOrInsertFunction("getchar", IntegerType::getInt32Ty(C), NULL));
66 //declare i32 @putchar(i32)
67 putchar_func = cast<Function>(module->
68 getOrInsertFunction("putchar", IntegerType::getInt32Ty(C),
69 IntegerType::getInt32Ty(C), NULL));
74 //define void @brainf()
75 brainf_func = cast<Function>(module->
76 getOrInsertFunction("brainf", Type::getVoidTy(C), NULL));
78 builder = new IRBuilder<>(BasicBlock::Create(C, label, brainf_func));
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,
89 BB->getInstList().push_back(cast<Instruction>(ptr_arr));
91 //call void @llvm.memset.p0i8.i32(i8 *%arr, i8 0, i32 %d, i32 1, i1 0)
93 Value *memset_params[] = {
95 ConstantInt::get(C, APInt(8, 0)),
97 ConstantInt::get(C, APInt(32, 1)),
98 ConstantInt::get(C, APInt(1, 0))
101 CallInst *memset_call = builder->
102 CreateCall(memset_func, memset_params);
103 memset_call->setTailCall(false);
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");
112 //%head.%d = getelementptr i8 *%arr, i32 %d
113 curhead = builder->CreateGEP(ptr_arr,
114 ConstantInt::get(C, APInt(32, memtotal/2)),
122 endbb = BasicBlock::Create(C, label, brainf_func);
124 //call free(i8 *%arr)
125 endbb->getInstList().push_back(CallInst::CreateFree(ptr_arr, endbb));
128 ReturnInst::Create(C, endbb);
132 //Error block for array out of bounds
133 if (comflag & flag_arraybounds)
135 //@aberrormsg = internal constant [%d x i8] c"\00"
137 ConstantDataArray::getString(C, "Error: The head has left the tape.",
140 GlobalVariable *aberrormsg = new GlobalVariable(
144 GlobalValue::InternalLinkage,
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));
154 aberrorbb = BasicBlock::Create(C, label, brainf_func);
156 //call i32 @puts(i8 *getelementptr([%d x i8] *@aberrormsg, i32 0, i32 0))
158 Constant *zero_32 = Constant::getNullValue(IntegerType::getInt32Ty(C));
160 Constant *gep_params[] = {
165 Constant *msgptr = ConstantExpr::
166 getGetElementPtr(aberrormsg->getValueType(), aberrormsg, gep_params);
168 Value *puts_params[] = {
172 CallInst *puts_call =
173 CallInst::Create(puts_func,
176 puts_call->setTailCall(false);
179 //br label %brainf.end
180 BranchInst::Create(endbb, aberrorbb);
184 void BrainF::readloop(PHINode *phi, BasicBlock *oldbb, BasicBlock *testbb,
186 Symbol cursym = SYM_NONE;
188 Symbol nextsym = SYM_NONE;
194 while(cursym != SYM_EOF && cursym != SYM_ENDLOOP) {
195 // Write out commands
203 //%tape.%d = call i32 @getchar()
204 CallInst *getchar_call =
205 builder->CreateCall(getchar_func, {}, tapereg);
206 getchar_call->setTailCall(false);
207 Value *tape_0 = getchar_call;
209 //%tape.%d = trunc i32 %tape.%d to i8
210 Value *tape_1 = builder->
211 CreateTrunc(tape_0, IntegerType::getInt8Ty(C), tapereg);
213 //store i8 %tape.%d, i8 *%head.%d
214 builder->CreateStore(tape_1, curhead);
220 //%tape.%d = load i8 *%head.%d
221 LoadInst *tape_0 = builder->CreateLoad(curhead, tapereg);
223 //%tape.%d = sext i8 %tape.%d to i32
224 Value *tape_1 = builder->
225 CreateSExt(tape_0, IntegerType::getInt32Ty(C), tapereg);
227 //call i32 @putchar(i32 %tape.%d)
228 Value *putchar_params[] = {
231 CallInst *putchar_call = builder->
232 CreateCall(putchar_func,
234 putchar_call->setTailCall(false);
240 //%head.%d = getelementptr i8 *%head.%d, i32 %d
242 CreateGEP(curhead, ConstantInt::get(C, APInt(32, curvalue)),
245 //Error block for array out of bounds
246 if (comflag & flag_arraybounds)
248 //%test.%d = icmp uge i8 *%head.%d, %arrmax
249 Value *test_0 = builder->
250 CreateICmpUGE(curhead, ptr_arrmax, testreg);
252 //%test.%d = icmp ult i8 *%head.%d, %arr
253 Value *test_1 = builder->
254 CreateICmpULT(curhead, ptr_arr, testreg);
256 //%test.%d = or i1 %test.%d, %test.%d
257 Value *test_2 = builder->
258 CreateOr(test_0, test_1, testreg);
260 //br i1 %test.%d, label %main.%d, label %main.%d
261 BasicBlock *nextbb = BasicBlock::Create(C, label, brainf_func);
262 builder->CreateCondBr(test_2, aberrorbb, nextbb);
265 builder->SetInsertPoint(nextbb);
272 //%tape.%d = load i8 *%head.%d
273 LoadInst *tape_0 = builder->CreateLoad(curhead, tapereg);
275 //%tape.%d = add i8 %tape.%d, %d
276 Value *tape_1 = builder->
277 CreateAdd(tape_0, ConstantInt::get(C, APInt(8, curvalue)), tapereg);
279 //store i8 %tape.%d, i8 *%head.%d\n"
280 builder->CreateStore(tape_1, curhead);
287 BasicBlock *testbb = BasicBlock::Create(C, label, brainf_func);
288 builder->CreateBr(testbb);
291 BasicBlock *bb_0 = builder->GetInsertBlock();
292 BasicBlock *bb_1 = BasicBlock::Create(C, label, brainf_func);
293 builder->SetInsertPoint(bb_1);
295 // Make part of PHI instruction now, wait until end of loop to finish
297 PHINode::Create(PointerType::getUnqual(IntegerType::getInt8Ty(C)),
299 phi_0->addIncoming(curhead, bb_0);
302 readloop(phi_0, bb_1, testbb, C);
307 std::cerr << "Error: Unknown symbol.\n";
313 curvalue = nextvalue;
316 // Reading stdin loop
317 loop = (cursym == SYM_NONE)
318 || (cursym == SYM_MOVE)
319 || (cursym == SYM_CHANGE);
323 if (cursym == SYM_NONE) {
337 if (cursym == SYM_CHANGE) {
338 curvalue += direction;
341 if (cursym == SYM_NONE) {
343 curvalue = direction;
346 nextsym = SYM_CHANGE;
347 nextvalue = direction;
358 if (cursym == SYM_MOVE) {
359 curvalue += direction;
362 if (cursym == SYM_NONE) {
364 curvalue = direction;
368 nextvalue = direction;
375 if (cursym == SYM_NONE) {
384 if (cursym == SYM_NONE) {
393 if (cursym == SYM_NONE) {
402 if (cursym == SYM_NONE) {
403 cursym = SYM_ENDLOOP;
405 nextsym = SYM_ENDLOOP;
410 // Ignore other characters
418 if (cursym == SYM_ENDLOOP) {
420 std::cerr << "Error: Extra ']'\n";
427 builder->CreateBr(testbb);
431 //%head.%d = phi i8 *[%head.%d, %main.%d], [%head.%d, %main.%d]
432 //Finish phi made at beginning of loop
433 phi->addIncoming(curhead, builder->GetInsertBlock());
436 //%tape.%d = load i8 *%head.%d
437 LoadInst *tape_0 = new LoadInst(head_0, tapereg, testbb);
439 //%test.%d = icmp eq i8 %tape.%d, 0
440 ICmpInst *test_0 = new ICmpInst(*testbb, ICmpInst::ICMP_EQ, tape_0,
441 ConstantInt::get(C, APInt(8, 0)), testreg);
443 //br i1 %test.%d, label %main.%d, label %main.%d
444 BasicBlock *bb_0 = BasicBlock::Create(C, label, brainf_func);
445 BranchInst::Create(bb_0, oldbb, test_0, testbb);
448 builder->SetInsertPoint(bb_0);
450 //%head.%d = phi i8 *[%head.%d, %main.%d]
451 PHINode *phi_1 = builder->
452 CreatePHI(PointerType::getUnqual(IntegerType::getInt8Ty(C)), 1,
454 phi_1->addIncoming(head_0, testbb);
461 //End of the program, so go to return block
462 builder->CreateBr(endbb);
465 std::cerr << "Error: Missing ']'\n";