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 
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 
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 
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 = builder->CreateLoad(curhead, tapereg);
227 
228           //%tape.%d = sext i8 %tape.%d to i32
229           Value *tape_1 = builder->
230             CreateSExt(tape_0, IntegerType::getInt32Ty(C), tapereg);
231 
232           //call i32 @putchar(i32 %tape.%d)
233           Value *putchar_params[] = {
234             tape_1
235           };
236           CallInst *putchar_call = builder->
237             CreateCall(putchar_func,
238                        putchar_params);
239           putchar_call->setTailCall(false);
240         }
241         break;
242 
243       case SYM_MOVE:
244         {
245           //%head.%d = getelementptr i8 *%head.%d, i32 %d
246           curhead = builder->
247             CreateGEP(curhead, ConstantInt::get(C, APInt(32, curvalue)),
248                       headreg);
249 
250           //Error block for array out of bounds
251           if (comflag & flag_arraybounds)
252           {
253             //%test.%d = icmp uge i8 *%head.%d, %arrmax
254             Value *test_0 = builder->
255               CreateICmpUGE(curhead, ptr_arrmax, testreg);
256 
257             //%test.%d = icmp ult i8 *%head.%d, %arr
258             Value *test_1 = builder->
259               CreateICmpULT(curhead, ptr_arr, testreg);
260 
261             //%test.%d = or i1 %test.%d, %test.%d
262             Value *test_2 = builder->
263               CreateOr(test_0, test_1, testreg);
264 
265             //br i1 %test.%d, label %main.%d, label %main.%d
266             BasicBlock *nextbb = BasicBlock::Create(C, label, brainf_func);
267             builder->CreateCondBr(test_2, aberrorbb, nextbb);
268 
269             //main.%d:
270             builder->SetInsertPoint(nextbb);
271           }
272         }
273         break;
274 
275       case SYM_CHANGE:
276         {
277           //%tape.%d = load i8 *%head.%d
278           LoadInst *tape_0 = builder->CreateLoad(curhead, tapereg);
279 
280           //%tape.%d = add i8 %tape.%d, %d
281           Value *tape_1 = builder->
282             CreateAdd(tape_0, ConstantInt::get(C, APInt(8, curvalue)), tapereg);
283 
284           //store i8 %tape.%d, i8 *%head.%d\n"
285           builder->CreateStore(tape_1, curhead);
286         }
287         break;
288 
289       case SYM_LOOP:
290         {
291           //br label %main.%d
292           BasicBlock *testbb = BasicBlock::Create(C, label, brainf_func);
293           builder->CreateBr(testbb);
294 
295           //main.%d:
296           BasicBlock *bb_0 = builder->GetInsertBlock();
297           BasicBlock *bb_1 = BasicBlock::Create(C, label, brainf_func);
298           builder->SetInsertPoint(bb_1);
299 
300           // Make part of PHI instruction now, wait until end of loop to finish
301           PHINode *phi_0 =
302             PHINode::Create(PointerType::getUnqual(IntegerType::getInt8Ty(C)),
303                             2, headreg, testbb);
304           phi_0->addIncoming(curhead, bb_0);
305           curhead = phi_0;
306 
307           readloop(phi_0, bb_1, testbb, C);
308         }
309         break;
310 
311       default:
312         std::cerr << "Error: Unknown symbol.\n";
313         abort();
314         break;
315     }
316 
317     cursym = nextsym;
318     curvalue = nextvalue;
319     nextsym = SYM_NONE;
320 
321     // Reading stdin loop
322     loop = (cursym == SYM_NONE)
323         || (cursym == SYM_MOVE)
324         || (cursym == SYM_CHANGE);
325     while(loop) {
326       *in>>c;
327       if (in->eof()) {
328         if (cursym == SYM_NONE) {
329           cursym = SYM_EOF;
330         } else {
331           nextsym = SYM_EOF;
332         }
333         loop = 0;
334       } else {
335         direction = 1;
336         switch(c) {
337           case '-':
338             direction = -1;
339             LLVM_FALLTHROUGH;
340 
341           case '+':
342             if (cursym == SYM_CHANGE) {
343               curvalue += direction;
344               // loop = 1
345             } else {
346               if (cursym == SYM_NONE) {
347                 cursym = SYM_CHANGE;
348                 curvalue = direction;
349                 // loop = 1
350               } else {
351                 nextsym = SYM_CHANGE;
352                 nextvalue = direction;
353                 loop = 0;
354               }
355             }
356             break;
357 
358           case '<':
359             direction = -1;
360             LLVM_FALLTHROUGH;
361 
362           case '>':
363             if (cursym == SYM_MOVE) {
364               curvalue += direction;
365               // loop = 1
366             } else {
367               if (cursym == SYM_NONE) {
368                 cursym = SYM_MOVE;
369                 curvalue = direction;
370                 // loop = 1
371               } else {
372                 nextsym = SYM_MOVE;
373                 nextvalue = direction;
374                 loop = 0;
375               }
376             }
377             break;
378 
379           case ',':
380             if (cursym == SYM_NONE) {
381               cursym = SYM_READ;
382             } else {
383               nextsym = SYM_READ;
384             }
385             loop = 0;
386             break;
387 
388           case '.':
389             if (cursym == SYM_NONE) {
390               cursym = SYM_WRITE;
391             } else {
392               nextsym = SYM_WRITE;
393             }
394             loop = 0;
395             break;
396 
397           case '[':
398             if (cursym == SYM_NONE) {
399               cursym = SYM_LOOP;
400             } else {
401               nextsym = SYM_LOOP;
402             }
403             loop = 0;
404             break;
405 
406           case ']':
407             if (cursym == SYM_NONE) {
408               cursym = SYM_ENDLOOP;
409             } else {
410               nextsym = SYM_ENDLOOP;
411             }
412             loop = 0;
413             break;
414 
415           // Ignore other characters
416           default:
417             break;
418         }
419       }
420     }
421   }
422 
423   if (cursym == SYM_ENDLOOP) {
424     if (!phi) {
425       std::cerr << "Error: Extra ']'\n";
426       abort();
427     }
428 
429     // Write loop test
430     {
431       //br label %main.%d
432       builder->CreateBr(testbb);
433 
434       //main.%d:
435 
436       //%head.%d = phi i8 *[%head.%d, %main.%d], [%head.%d, %main.%d]
437       //Finish phi made at beginning of loop
438       phi->addIncoming(curhead, builder->GetInsertBlock());
439       Value *head_0 = phi;
440 
441       //%tape.%d = load i8 *%head.%d
442       LoadInst *tape_0 = new LoadInst(IntegerType::getInt8Ty(C), head_0,
443                                       tapereg, testbb);
444 
445       //%test.%d = icmp eq i8 %tape.%d, 0
446       ICmpInst *test_0 = new ICmpInst(*testbb, ICmpInst::ICMP_EQ, tape_0,
447                                     ConstantInt::get(C, APInt(8, 0)), testreg);
448 
449       //br i1 %test.%d, label %main.%d, label %main.%d
450       BasicBlock *bb_0 = BasicBlock::Create(C, label, brainf_func);
451       BranchInst::Create(bb_0, oldbb, test_0, testbb);
452 
453       //main.%d:
454       builder->SetInsertPoint(bb_0);
455 
456       //%head.%d = phi i8 *[%head.%d, %main.%d]
457       PHINode *phi_1 = builder->
458         CreatePHI(PointerType::getUnqual(IntegerType::getInt8Ty(C)), 1,
459                   headreg);
460       phi_1->addIncoming(head_0, testbb);
461       curhead = phi_1;
462     }
463 
464     return;
465   }
466 
467   //End of the program, so go to return block
468   builder->CreateBr(endbb);
469 
470   if (phi) {
471     std::cerr << "Error: Missing ']'\n";
472     abort();
473   }
474 }
475