examples/BrainF/BrainF.cpp

   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>
  31 using namespace llvm;
  32
  33 //Set the constants for naming
  34 const char *BrainF::tapereg = "tape";
  35 const char *BrainF::headreg = "head";
  36 const char *BrainF::label   = "brainf";
  37 const char *BrainF::testreg = "test";
  38
  39 Module *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, Context);
  47   delete builder;
  48   return module;
  49 }
  50
  51 void 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::getInt32Ty(C) };
  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::getInt32Ty(C), NULL));
  64
  65   //declare i32 @putchar(i32)
  66   putchar_func = cast<Function>(module->
  67     getOrInsertFunction("putchar", IntegerType::getInt32Ty(C),
  68                         IntegerType::getInt32Ty(C), NULL));
  69
  70
  71   //Function header
  72
  73   //define void @brainf()
  74   brainf_func = cast<Function>(module->
  75     getOrInsertFunction("brainf", Type::getVoidTy(C), NULL));
  76
  77   builder = new IRBuilder<>(BasicBlock::Create(C, label, brainf_func));
  78
  79   //%arr = malloc i8, i32 %d
  80   ConstantInt *val_mem = ConstantInt::get(C, APInt(32, memtotal));
  81   ptr_arr = builder->CreateMalloc(IntegerType::getInt8Ty(C), 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(C, APInt(8, 0)),
  88       val_mem,
  89       ConstantInt::get(C, 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(C, APInt(32, memtotal)), "arrmax");
 101   }
 102
 103   //%head.%d = getelementptr i8 *%arr, i32 %d
 104   curhead = builder->CreateGEP(ptr_arr,
 105                                ConstantInt::get(C, APInt(32, memtotal/2)),
 106                                headreg);
 107
 108
 109
 110   //Function footer
 111
 112   //brainf.end:
 113   endbb = BasicBlock::Create(C, label, brainf_func);
 114
 115   //free i8 *%arr
 116   new FreeInst(ptr_arr, endbb);
 117
 118   //ret void
 119   ReturnInst::Create(C, 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 =
 128       ConstantArray::get(C, "Error: The head has left the tape.", true);
 129
 130     GlobalVariable *aberrormsg = new GlobalVariable(
 131       *module,
 132       msg_0->getType(),
 133       true,
 134       GlobalValue::InternalLinkage,
 135       msg_0,
 136       "aberrormsg");
 137
 138     //declare i32 @puts(i8 *)
 139     Function *puts_func = cast<Function>(module->
 140       getOrInsertFunction("puts", IntegerType::getInt32Ty(C),
 141                       PointerType::getUnqual(IntegerType::getInt8Ty(C)), NULL));
 142
 143     //brainf.aberror:
 144     aberrorbb = BasicBlock::Create(C, 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::getInt32Ty(C));
 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
 175 void BrainF::readloop(PHINode *phi, BasicBlock *oldbb, BasicBlock *testbb,
 176                       LLVMContext &C) {
 177   Symbol cursym = SYM_NONE;
 178   int curvalue = 0;
 179   Symbol nextsym = SYM_NONE;
 180   int nextvalue = 0;
 181   char c;
 182   int loop;
 183   int direction;
 184
 185   while(cursym != SYM_EOF && cursym != SYM_ENDLOOP) {
 186     // Write out commands
 187     switch(cursym) {
 188       case SYM_NONE:
 189         // Do nothing
 190         break;
 191
 192       case SYM_READ:
 193         {
 194           //%tape.%d = call i32 @getchar()
 195           CallInst *getchar_call = builder->CreateCall(getchar_func, tapereg);
 196           getchar_call->setTailCall(false);
 197           Value *tape_0 = getchar_call;
 198
 199           //%tape.%d = trunc i32 %tape.%d to i8
 200           Value *tape_1 = builder->
 201             CreateTrunc(tape_0, IntegerType::getInt8Ty(C), tapereg);
 202
 203           //store i8 %tape.%d, i8 *%head.%d
 204           builder->CreateStore(tape_1, curhead);
 205         }
 206         break;
 207
 208       case SYM_WRITE:
 209         {
 210           //%tape.%d = load i8 *%head.%d
 211           LoadInst *tape_0 = builder->CreateLoad(curhead, tapereg);
 212
 213           //%tape.%d = sext i8 %tape.%d to i32
 214           Value *tape_1 = builder->
 215             CreateSExt(tape_0, IntegerType::getInt32Ty(C), tapereg);
 216
 217           //call i32 @putchar(i32 %tape.%d)
 218           Value *putchar_params[] = {
 219             tape_1
 220           };
 221           CallInst *putchar_call = builder->
 222             CreateCall(putchar_func,
 223                        putchar_params, array_endof(putchar_params));
 224           putchar_call->setTailCall(false);
 225         }
 226         break;
 227
 228       case SYM_MOVE:
 229         {
 230           //%head.%d = getelementptr i8 *%head.%d, i32 %d
 231           curhead = builder->
 232             CreateGEP(curhead, ConstantInt::get(C, APInt(32, curvalue)),
 233                       headreg);
 234
 235           //Error block for array out of bounds
 236           if (comflag & flag_arraybounds)
 237           {
 238             //%test.%d = icmp uge i8 *%head.%d, %arrmax
 239             Value *test_0 = builder->
 240               CreateICmpUGE(curhead, ptr_arrmax, testreg);
 241
 242             //%test.%d = icmp ult i8 *%head.%d, %arr
 243             Value *test_1 = builder->
 244               CreateICmpULT(curhead, ptr_arr, testreg);
 245
 246             //%test.%d = or i1 %test.%d, %test.%d
 247             Value *test_2 = builder->
 248               CreateOr(test_0, test_1, testreg);
 249
 250             //br i1 %test.%d, label %main.%d, label %main.%d
 251             BasicBlock *nextbb = BasicBlock::Create(C, label, brainf_func);
 252             builder->CreateCondBr(test_2, aberrorbb, nextbb);
 253
 254             //main.%d:
 255             builder->SetInsertPoint(nextbb);
 256           }
 257         }
 258         break;
 259
 260       case SYM_CHANGE:
 261         {
 262           //%tape.%d = load i8 *%head.%d
 263           LoadInst *tape_0 = builder->CreateLoad(curhead, tapereg);
 264
 265           //%tape.%d = add i8 %tape.%d, %d
 266           Value *tape_1 = builder->
 267             CreateAdd(tape_0, ConstantInt::get(C, APInt(8, curvalue)), tapereg);
 268
 269           //store i8 %tape.%d, i8 *%head.%d\n"
 270           builder->CreateStore(tape_1, curhead);
 271         }
 272         break;
 273
 274       case SYM_LOOP:
 275         {
 276           //br label %main.%d
 277           BasicBlock *testbb = BasicBlock::Create(C, label, brainf_func);
 278           builder->CreateBr(testbb);
 279
 280           //main.%d:
 281           BasicBlock *bb_0 = builder->GetInsertBlock();
 282           BasicBlock *bb_1 = BasicBlock::Create(C, label, brainf_func);
 283           builder->SetInsertPoint(bb_1);
 284
 285           // Make part of PHI instruction now, wait until end of loop to finish
 286           PHINode *phi_0 =
 287             PHINode::Create(PointerType::getUnqual(IntegerType::getInt8Ty(C)),
 288                             headreg, testbb);
 289           phi_0->reserveOperandSpace(2);
 290           phi_0->addIncoming(curhead, bb_0);
 291           curhead = phi_0;
 292
 293           readloop(phi_0, bb_1, testbb, C);
 294         }
 295         break;
 296
 297       default:
 298         std::cerr << "Error: Unknown symbol.\n";
 299         abort();
 300         break;
 301     }
 302
 303     cursym = nextsym;
 304     curvalue = nextvalue;
 305     nextsym = SYM_NONE;
 306
 307     // Reading stdin loop
 308     loop = (cursym == SYM_NONE)
 309         || (cursym == SYM_MOVE)
 310         || (cursym == SYM_CHANGE);
 311     while(loop) {
 312       *in>>c;
 313       if (in->eof()) {
 314         if (cursym == SYM_NONE) {
 315           cursym = SYM_EOF;
 316         } else {
 317           nextsym = SYM_EOF;
 318         }
 319         loop = 0;
 320       } else {
 321         direction = 1;
 322         switch(c) {
 323           case '-':
 324             direction = -1;
 325             // Fall through
 326
 327           case '+':
 328             if (cursym == SYM_CHANGE) {
 329               curvalue += direction;
 330               // loop = 1
 331             } else {
 332               if (cursym == SYM_NONE) {
 333                 cursym = SYM_CHANGE;
 334                 curvalue = direction;
 335                 // loop = 1
 336               } else {
 337                 nextsym = SYM_CHANGE;
 338                 nextvalue = direction;
 339                 loop = 0;
 340               }
 341             }
 342             break;
 343
 344           case '<':
 345             direction = -1;
 346             // Fall through
 347
 348           case '>':
 349             if (cursym == SYM_MOVE) {
 350               curvalue += direction;
 351               // loop = 1
 352             } else {
 353               if (cursym == SYM_NONE) {
 354                 cursym = SYM_MOVE;
 355                 curvalue = direction;
 356                 // loop = 1
 357               } else {
 358                 nextsym = SYM_MOVE;
 359                 nextvalue = direction;
 360                 loop = 0;
 361               }
 362             }
 363             break;
 364
 365           case ',':
 366             if (cursym == SYM_NONE) {
 367               cursym = SYM_READ;
 368             } else {
 369               nextsym = SYM_READ;
 370             }
 371             loop = 0;
 372             break;
 373
 374           case '.':
 375             if (cursym == SYM_NONE) {
 376               cursym = SYM_WRITE;
 377             } else {
 378               nextsym = SYM_WRITE;
 379             }
 380             loop = 0;
 381             break;
 382
 383           case '[':
 384             if (cursym == SYM_NONE) {
 385               cursym = SYM_LOOP;
 386             } else {
 387               nextsym = SYM_LOOP;
 388             }
 389             loop = 0;
 390             break;
 391
 392           case ']':
 393             if (cursym == SYM_NONE) {
 394               cursym = SYM_ENDLOOP;
 395             } else {
 396               nextsym = SYM_ENDLOOP;
 397             }
 398             loop = 0;
 399             break;
 400
 401           // Ignore other characters
 402           default:
 403             break;
 404         }
 405       }
 406     }
 407   }
 408
 409   if (cursym == SYM_ENDLOOP) {
 410     if (!phi) {
 411       std::cerr << "Error: Extra ']'\n";
 412       abort();
 413     }
 414
 415     // Write loop test
 416     {
 417       //br label %main.%d
 418       builder->CreateBr(testbb);
 419
 420       //main.%d:
 421
 422       //%head.%d = phi i8 *[%head.%d, %main.%d], [%head.%d, %main.%d]
 423       //Finish phi made at beginning of loop
 424       phi->addIncoming(curhead, builder->GetInsertBlock());
 425       Value *head_0 = phi;
 426
 427       //%tape.%d = load i8 *%head.%d
 428       LoadInst *tape_0 = new LoadInst(head_0, tapereg, testbb);
 429
 430       //%test.%d = icmp eq i8 %tape.%d, 0
 431       ICmpInst *test_0 = new ICmpInst(*testbb, ICmpInst::ICMP_EQ, tape_0,
 432                                     ConstantInt::get(C, APInt(8, 0)), testreg);
 433
 434       //br i1 %test.%d, label %main.%d, label %main.%d
 435       BasicBlock *bb_0 = BasicBlock::Create(C, 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::getInt8Ty(C)), 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 }