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