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