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