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