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