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