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