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->CreateGEP(
118         Int8Ty, ptr_arr, ConstantInt::get(C, APInt(32, memtotal)), "arrmax");
119   }
120 
121   //%head.%d = getelementptr i8 *%arr, i32 %d
122   curhead = builder->CreateGEP(
123       Int8Ty, ptr_arr, ConstantInt::get(C, APInt(32, memtotal / 2)), headreg);
124 
125   //Function footer
126 
127   //brainf.end:
128   endbb = BasicBlock::Create(C, label, brainf_func);
129 
130   //call free(i8 *%arr)
131   endbb->getInstList().push_back(CallInst::CreateFree(ptr_arr, endbb));
132 
133   //ret void
134   ReturnInst::Create(C, endbb);
135 
136   //Error block for array out of bounds
137   if (comflag & flag_arraybounds)
138   {
139     //@aberrormsg = internal constant [%d x i8] c"\00"
140     Constant *msg_0 =
141       ConstantDataArray::getString(C, "Error: The head has left the tape.",
142                                    true);
143 
144     GlobalVariable *aberrormsg = new GlobalVariable(
145       *module,
146       msg_0->getType(),
147       true,
148       GlobalValue::InternalLinkage,
149       msg_0,
150       "aberrormsg");
151 
152     //declare i32 @puts(i8 *)
153     FunctionCallee puts_func = module->getOrInsertFunction(
154         "puts", IntegerType::getInt32Ty(C),
155         PointerType::getUnqual(IntegerType::getInt8Ty(C)));
156 
157     //brainf.aberror:
158     aberrorbb = BasicBlock::Create(C, label, brainf_func);
159 
160     //call i32 @puts(i8 *getelementptr([%d x i8] *@aberrormsg, i32 0, i32 0))
161     {
162       Constant *zero_32 = Constant::getNullValue(IntegerType::getInt32Ty(C));
163 
164       Constant *gep_params[] = {
165         zero_32,
166         zero_32
167       };
168 
169       Constant *msgptr = ConstantExpr::
170         getGetElementPtr(aberrormsg->getValueType(), aberrormsg, gep_params);
171 
172       Value *puts_params[] = {
173         msgptr
174       };
175 
176       CallInst *puts_call =
177         CallInst::Create(puts_func,
178                          puts_params,
179                          "", aberrorbb);
180       puts_call->setTailCall(false);
181     }
182 
183     //br label %brainf.end
184     BranchInst::Create(endbb, aberrorbb);
185   }
186 }
187 
188 void BrainF::readloop(PHINode *phi, BasicBlock *oldbb, BasicBlock *testbb,
189                       LLVMContext &C) {
190   Symbol cursym = SYM_NONE;
191   int curvalue = 0;
192   Symbol nextsym = SYM_NONE;
193   int nextvalue = 0;
194   char c;
195   int loop;
196   int direction;
197   Type *Int8Ty = IntegerType::getInt8Ty(C);
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(Int8Ty, 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->CreateGEP(Int8Ty, curhead,
247                                        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(Int8Ty, 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 = PHINode::Create(PointerType::getUnqual(Int8Ty), 2,
302                                            headreg, testbb);
303           phi_0->addIncoming(curhead, bb_0);
304           curhead = phi_0;
305 
306           readloop(phi_0, bb_1, testbb, C);
307         }
308         break;
309 
310       default:
311         std::cerr << "Error: Unknown symbol.\n";
312         abort();
313         break;
314     }
315 
316     cursym = nextsym;
317     curvalue = nextvalue;
318     nextsym = SYM_NONE;
319 
320     // Reading stdin loop
321     loop = (cursym == SYM_NONE)
322         || (cursym == SYM_MOVE)
323         || (cursym == SYM_CHANGE);
324     while(loop) {
325       *in>>c;
326       if (in->eof()) {
327         if (cursym == SYM_NONE) {
328           cursym = SYM_EOF;
329         } else {
330           nextsym = SYM_EOF;
331         }
332         loop = 0;
333       } else {
334         direction = 1;
335         switch(c) {
336           case '-':
337             direction = -1;
338             LLVM_FALLTHROUGH;
339 
340           case '+':
341             if (cursym == SYM_CHANGE) {
342               curvalue += direction;
343               // loop = 1
344             } else {
345               if (cursym == SYM_NONE) {
346                 cursym = SYM_CHANGE;
347                 curvalue = direction;
348                 // loop = 1
349               } else {
350                 nextsym = SYM_CHANGE;
351                 nextvalue = direction;
352                 loop = 0;
353               }
354             }
355             break;
356 
357           case '<':
358             direction = -1;
359             LLVM_FALLTHROUGH;
360 
361           case '>':
362             if (cursym == SYM_MOVE) {
363               curvalue += direction;
364               // loop = 1
365             } else {
366               if (cursym == SYM_NONE) {
367                 cursym = SYM_MOVE;
368                 curvalue = direction;
369                 // loop = 1
370               } else {
371                 nextsym = SYM_MOVE;
372                 nextvalue = direction;
373                 loop = 0;
374               }
375             }
376             break;
377 
378           case ',':
379             if (cursym == SYM_NONE) {
380               cursym = SYM_READ;
381             } else {
382               nextsym = SYM_READ;
383             }
384             loop = 0;
385             break;
386 
387           case '.':
388             if (cursym == SYM_NONE) {
389               cursym = SYM_WRITE;
390             } else {
391               nextsym = SYM_WRITE;
392             }
393             loop = 0;
394             break;
395 
396           case '[':
397             if (cursym == SYM_NONE) {
398               cursym = SYM_LOOP;
399             } else {
400               nextsym = SYM_LOOP;
401             }
402             loop = 0;
403             break;
404 
405           case ']':
406             if (cursym == SYM_NONE) {
407               cursym = SYM_ENDLOOP;
408             } else {
409               nextsym = SYM_ENDLOOP;
410             }
411             loop = 0;
412             break;
413 
414           // Ignore other characters
415           default:
416             break;
417         }
418       }
419     }
420   }
421 
422   if (cursym == SYM_ENDLOOP) {
423     if (!phi) {
424       std::cerr << "Error: Extra ']'\n";
425       abort();
426     }
427 
428     // Write loop test
429     {
430       //br label %main.%d
431       builder->CreateBr(testbb);
432 
433       //main.%d:
434 
435       //%head.%d = phi i8 *[%head.%d, %main.%d], [%head.%d, %main.%d]
436       //Finish phi made at beginning of loop
437       phi->addIncoming(curhead, builder->GetInsertBlock());
438       Value *head_0 = phi;
439 
440       //%tape.%d = load i8 *%head.%d
441       LoadInst *tape_0 = new LoadInst(Int8Ty, head_0, tapereg, testbb);
442 
443       //%test.%d = icmp eq i8 %tape.%d, 0
444       ICmpInst *test_0 = new ICmpInst(*testbb, ICmpInst::ICMP_EQ, tape_0,
445                                     ConstantInt::get(C, APInt(8, 0)), testreg);
446 
447       //br i1 %test.%d, label %main.%d, label %main.%d
448       BasicBlock *bb_0 = BasicBlock::Create(C, label, brainf_func);
449       BranchInst::Create(bb_0, oldbb, test_0, testbb);
450 
451       //main.%d:
452       builder->SetInsertPoint(bb_0);
453 
454       //%head.%d = phi i8 *[%head.%d, %main.%d]
455       PHINode *phi_1 =
456           builder->CreatePHI(PointerType::getUnqual(Int8Ty), 1, headreg);
457       phi_1->addIncoming(head_0, testbb);
458       curhead = phi_1;
459     }
460 
461     return;
462   }
463 
464   //End of the program, so go to return block
465   builder->CreateBr(endbb);
466 
467   if (phi) {
468     std::cerr << "Error: Missing ']'\n";
469     abort();
470   }
471 }
472