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/Constants.h"
28 #include "llvm/Intrinsics.h"
29 #include "llvm/ADT/STLExtras.h"
33 //Set the constants for naming
34 const char *BrainF::tapereg = "tape";
35 const char *BrainF::headreg = "head";
36 const char *BrainF::label = "brainf";
37 const char *BrainF::testreg = "test";
39 Module *BrainF::parse(std::istream *in1, int mem, CompileFlags cf,
40 LLVMContext& Context) {
46 readloop(0, 0, 0, Context);
51 void BrainF::header(LLVMContext& C) {
52 module = new Module("BrainF", C);
56 //declare void @llvm.memset.i32(i8 *, i8, i32, i32)
57 const Type *Tys[] = { Type::Int32Ty };
58 Function *memset_func = Intrinsic::getDeclaration(module, Intrinsic::memset,
61 //declare i32 @getchar()
62 getchar_func = cast<Function>(module->
63 getOrInsertFunction("getchar", IntegerType::Int32Ty, NULL));
65 //declare i32 @putchar(i32)
66 putchar_func = cast<Function>(module->
67 getOrInsertFunction("putchar", IntegerType::Int32Ty,
68 IntegerType::Int32Ty, NULL));
73 //define void @brainf()
74 brainf_func = cast<Function>(module->
75 getOrInsertFunction("brainf", Type::VoidTy, NULL));
77 builder = new IRBuilder<>(BasicBlock::Create(label, brainf_func));
79 //%arr = malloc i8, i32 %d
80 ConstantInt *val_mem = ConstantInt::get(C, APInt(32, memtotal));
81 ptr_arr = builder->CreateMalloc(IntegerType::Int8Ty, val_mem, "arr");
83 //call void @llvm.memset.i32(i8 *%arr, i8 0, i32 %d, i32 1)
85 Value *memset_params[] = {
87 ConstantInt::get(C, APInt(8, 0)),
89 ConstantInt::get(C, APInt(32, 1))
92 CallInst *memset_call = builder->
93 CreateCall(memset_func, memset_params, array_endof(memset_params));
94 memset_call->setTailCall(false);
97 //%arrmax = getelementptr i8 *%arr, i32 %d
98 if (comflag & flag_arraybounds) {
99 ptr_arrmax = builder->
100 CreateGEP(ptr_arr, ConstantInt::get(C, APInt(32, memtotal)), "arrmax");
103 //%head.%d = getelementptr i8 *%arr, i32 %d
104 curhead = builder->CreateGEP(ptr_arr,
105 ConstantInt::get(C, APInt(32, memtotal/2)),
113 endbb = BasicBlock::Create(label, brainf_func);
116 new FreeInst(ptr_arr, endbb);
119 ReturnInst::Create(endbb);
123 //Error block for array out of bounds
124 if (comflag & flag_arraybounds)
126 //@aberrormsg = internal constant [%d x i8] c"\00"
128 ConstantArray::get("Error: The head has left the tape.", true);
130 GlobalVariable *aberrormsg = new GlobalVariable(
134 GlobalValue::InternalLinkage,
138 //declare i32 @puts(i8 *)
139 Function *puts_func = cast<Function>(module->
140 getOrInsertFunction("puts", IntegerType::Int32Ty,
141 PointerType::getUnqual(IntegerType::Int8Ty), NULL));
144 aberrorbb = BasicBlock::Create(label, brainf_func);
146 //call i32 @puts(i8 *getelementptr([%d x i8] *@aberrormsg, i32 0, i32 0))
148 Constant *zero_32 = Constant::getNullValue(IntegerType::Int32Ty);
150 Constant *gep_params[] = {
155 Constant *msgptr = ConstantExpr::
156 getGetElementPtr(aberrormsg, gep_params,
157 array_lengthof(gep_params));
159 Value *puts_params[] = {
163 CallInst *puts_call =
164 CallInst::Create(puts_func,
165 puts_params, array_endof(puts_params),
167 puts_call->setTailCall(false);
170 //br label %brainf.end
171 BranchInst::Create(endbb, aberrorbb);
175 void BrainF::readloop(PHINode *phi, BasicBlock *oldbb, BasicBlock *testbb,
177 Symbol cursym = SYM_NONE;
179 Symbol nextsym = SYM_NONE;
185 while(cursym != SYM_EOF && cursym != SYM_ENDLOOP) {
186 // Write out commands
194 //%tape.%d = call i32 @getchar()
195 CallInst *getchar_call = builder->CreateCall(getchar_func, tapereg);
196 getchar_call->setTailCall(false);
197 Value *tape_0 = getchar_call;
199 //%tape.%d = trunc i32 %tape.%d to i8
200 Value *tape_1 = builder->
201 CreateTrunc(tape_0, IntegerType::Int8Ty, tapereg);
203 //store i8 %tape.%d, i8 *%head.%d
204 builder->CreateStore(tape_1, curhead);
210 //%tape.%d = load i8 *%head.%d
211 LoadInst *tape_0 = builder->CreateLoad(curhead, tapereg);
213 //%tape.%d = sext i8 %tape.%d to i32
214 Value *tape_1 = builder->
215 CreateSExt(tape_0, IntegerType::Int32Ty, tapereg);
217 //call i32 @putchar(i32 %tape.%d)
218 Value *putchar_params[] = {
221 CallInst *putchar_call = builder->
222 CreateCall(putchar_func,
223 putchar_params, array_endof(putchar_params));
224 putchar_call->setTailCall(false);
230 //%head.%d = getelementptr i8 *%head.%d, i32 %d
232 CreateGEP(curhead, ConstantInt::get(C, APInt(32, curvalue)),
235 //Error block for array out of bounds
236 if (comflag & flag_arraybounds)
238 //%test.%d = icmp uge i8 *%head.%d, %arrmax
239 Value *test_0 = builder->
240 CreateICmpUGE(curhead, ptr_arrmax, testreg);
242 //%test.%d = icmp ult i8 *%head.%d, %arr
243 Value *test_1 = builder->
244 CreateICmpULT(curhead, ptr_arr, testreg);
246 //%test.%d = or i1 %test.%d, %test.%d
247 Value *test_2 = builder->
248 CreateOr(test_0, test_1, testreg);
250 //br i1 %test.%d, label %main.%d, label %main.%d
251 BasicBlock *nextbb = BasicBlock::Create(label, brainf_func);
252 builder->CreateCondBr(test_2, aberrorbb, nextbb);
255 builder->SetInsertPoint(nextbb);
262 //%tape.%d = load i8 *%head.%d
263 LoadInst *tape_0 = builder->CreateLoad(curhead, tapereg);
265 //%tape.%d = add i8 %tape.%d, %d
266 Value *tape_1 = builder->
267 CreateAdd(tape_0, ConstantInt::get(C, APInt(8, curvalue)), tapereg);
269 //store i8 %tape.%d, i8 *%head.%d\n"
270 builder->CreateStore(tape_1, curhead);
277 BasicBlock *testbb = BasicBlock::Create(label, brainf_func);
278 builder->CreateBr(testbb);
281 BasicBlock *bb_0 = builder->GetInsertBlock();
282 BasicBlock *bb_1 = BasicBlock::Create(label, brainf_func);
283 builder->SetInsertPoint(bb_1);
285 // Make part of PHI instruction now, wait until end of loop to finish
287 PHINode::Create(PointerType::getUnqual(IntegerType::Int8Ty),
289 phi_0->reserveOperandSpace(2);
290 phi_0->addIncoming(curhead, bb_0);
293 readloop(phi_0, bb_1, testbb, C);
298 std::cerr << "Error: Unknown symbol.\n";
304 curvalue = nextvalue;
307 // Reading stdin loop
308 loop = (cursym == SYM_NONE)
309 || (cursym == SYM_MOVE)
310 || (cursym == SYM_CHANGE);
314 if (cursym == SYM_NONE) {
328 if (cursym == SYM_CHANGE) {
329 curvalue += direction;
332 if (cursym == SYM_NONE) {
334 curvalue = direction;
337 nextsym = SYM_CHANGE;
338 nextvalue = direction;
349 if (cursym == SYM_MOVE) {
350 curvalue += direction;
353 if (cursym == SYM_NONE) {
355 curvalue = direction;
359 nextvalue = direction;
366 if (cursym == SYM_NONE) {
375 if (cursym == SYM_NONE) {
384 if (cursym == SYM_NONE) {
393 if (cursym == SYM_NONE) {
394 cursym = SYM_ENDLOOP;
396 nextsym = SYM_ENDLOOP;
401 // Ignore other characters
409 if (cursym == SYM_ENDLOOP) {
411 std::cerr << "Error: Extra ']'\n";
418 builder->CreateBr(testbb);
422 //%head.%d = phi i8 *[%head.%d, %main.%d], [%head.%d, %main.%d]
423 //Finish phi made at beginning of loop
424 phi->addIncoming(curhead, builder->GetInsertBlock());
427 //%tape.%d = load i8 *%head.%d
428 LoadInst *tape_0 = new LoadInst(head_0, tapereg, testbb);
430 //%test.%d = icmp eq i8 %tape.%d, 0
431 ICmpInst *test_0 = new ICmpInst(*testbb, ICmpInst::ICMP_EQ, tape_0,
432 ConstantInt::get(C, APInt(8, 0)), testreg);
434 //br i1 %test.%d, label %main.%d, label %main.%d
435 BasicBlock *bb_0 = BasicBlock::Create(label, brainf_func);
436 BranchInst::Create(bb_0, oldbb, test_0, testbb);
439 builder->SetInsertPoint(bb_0);
441 //%head.%d = phi i8 *[%head.%d, %main.%d]
442 PHINode *phi_1 = builder->
443 CreatePHI(PointerType::getUnqual(IntegerType::Int8Ty), headreg);
444 phi_1->reserveOperandSpace(1);
445 phi_1->addIncoming(head_0, testbb);
452 //End of the program, so go to return block
453 builder->CreateBr(endbb);
456 std::cerr << "Error: Missing ']'\n";