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