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 45using namespace llvm; 46 47//Set the constants for naming 48const char *BrainF::tapereg = "tape"; 49const char *BrainF::headreg = "head"; 50const char *BrainF::label = "brainf"; 51const char *BrainF::testreg = "test"; 52 53Module *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 65void 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), NULL)); 78 79 //declare i32 @putchar(i32) 80 putchar_func = cast<Function>(module-> 81 getOrInsertFunction("putchar", IntegerType::getInt32Ty(C), 82 IntegerType::getInt32Ty(C), NULL)); 83 84 //Function header 85 86 //define void @brainf() 87 brainf_func = cast<Function>(module-> 88 getOrInsertFunction("brainf", Type::getVoidTy(C), NULL)); 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)), NULL)); 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 192void 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 // Fall through 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 // Fall through 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} 477