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