examples/BrainF/BrainF.cpp

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