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