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