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, 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 = builder->CreateCall(getchar_func, tapereg); 205 getchar_call->setTailCall(false); 206 Value *tape_0 = getchar_call; 207 208 //%tape.%d = trunc i32 %tape.%d to i8 209 Value *tape_1 = builder-> 210 CreateTrunc(tape_0, IntegerType::getInt8Ty(C), tapereg); 211 212 //store i8 %tape.%d, i8 *%head.%d 213 builder->CreateStore(tape_1, curhead); 214 } 215 break; 216 217 case SYM_WRITE: 218 { 219 //%tape.%d = load i8 *%head.%d 220 LoadInst *tape_0 = builder->CreateLoad(curhead, tapereg); 221 222 //%tape.%d = sext i8 %tape.%d to i32 223 Value *tape_1 = builder-> 224 CreateSExt(tape_0, IntegerType::getInt32Ty(C), tapereg); 225 226 //call i32 @putchar(i32 %tape.%d) 227 Value *putchar_params[] = { 228 tape_1 229 }; 230 CallInst *putchar_call = builder-> 231 CreateCall(putchar_func, 232 putchar_params); 233 putchar_call->setTailCall(false); 234 } 235 break; 236 237 case SYM_MOVE: 238 { 239 //%head.%d = getelementptr i8 *%head.%d, i32 %d 240 curhead = builder-> 241 CreateGEP(curhead, ConstantInt::get(C, APInt(32, curvalue)), 242 headreg); 243 244 //Error block for array out of bounds 245 if (comflag & flag_arraybounds) 246 { 247 //%test.%d = icmp uge i8 *%head.%d, %arrmax 248 Value *test_0 = builder-> 249 CreateICmpUGE(curhead, ptr_arrmax, testreg); 250 251 //%test.%d = icmp ult i8 *%head.%d, %arr 252 Value *test_1 = builder-> 253 CreateICmpULT(curhead, ptr_arr, testreg); 254 255 //%test.%d = or i1 %test.%d, %test.%d 256 Value *test_2 = builder-> 257 CreateOr(test_0, test_1, testreg); 258 259 //br i1 %test.%d, label %main.%d, label %main.%d 260 BasicBlock *nextbb = BasicBlock::Create(C, label, brainf_func); 261 builder->CreateCondBr(test_2, aberrorbb, nextbb); 262 263 //main.%d: 264 builder->SetInsertPoint(nextbb); 265 } 266 } 267 break; 268 269 case SYM_CHANGE: 270 { 271 //%tape.%d = load i8 *%head.%d 272 LoadInst *tape_0 = builder->CreateLoad(curhead, tapereg); 273 274 //%tape.%d = add i8 %tape.%d, %d 275 Value *tape_1 = builder-> 276 CreateAdd(tape_0, ConstantInt::get(C, APInt(8, curvalue)), tapereg); 277 278 //store i8 %tape.%d, i8 *%head.%d\n" 279 builder->CreateStore(tape_1, curhead); 280 } 281 break; 282 283 case SYM_LOOP: 284 { 285 //br label %main.%d 286 BasicBlock *testbb = BasicBlock::Create(C, label, brainf_func); 287 builder->CreateBr(testbb); 288 289 //main.%d: 290 BasicBlock *bb_0 = builder->GetInsertBlock(); 291 BasicBlock *bb_1 = BasicBlock::Create(C, label, brainf_func); 292 builder->SetInsertPoint(bb_1); 293 294 // Make part of PHI instruction now, wait until end of loop to finish 295 PHINode *phi_0 = 296 PHINode::Create(PointerType::getUnqual(IntegerType::getInt8Ty(C)), 297 2, headreg, testbb); 298 phi_0->addIncoming(curhead, bb_0); 299 curhead = phi_0; 300 301 readloop(phi_0, bb_1, testbb, C); 302 } 303 break; 304 305 default: 306 std::cerr << "Error: Unknown symbol.\n"; 307 abort(); 308 break; 309 } 310 311 cursym = nextsym; 312 curvalue = nextvalue; 313 nextsym = SYM_NONE; 314 315 // Reading stdin loop 316 loop = (cursym == SYM_NONE) 317 || (cursym == SYM_MOVE) 318 || (cursym == SYM_CHANGE); 319 while(loop) { 320 *in>>c; 321 if (in->eof()) { 322 if (cursym == SYM_NONE) { 323 cursym = SYM_EOF; 324 } else { 325 nextsym = SYM_EOF; 326 } 327 loop = 0; 328 } else { 329 direction = 1; 330 switch(c) { 331 case '-': 332 direction = -1; 333 // Fall through 334 335 case '+': 336 if (cursym == SYM_CHANGE) { 337 curvalue += direction; 338 // loop = 1 339 } else { 340 if (cursym == SYM_NONE) { 341 cursym = SYM_CHANGE; 342 curvalue = direction; 343 // loop = 1 344 } else { 345 nextsym = SYM_CHANGE; 346 nextvalue = direction; 347 loop = 0; 348 } 349 } 350 break; 351 352 case '<': 353 direction = -1; 354 // Fall through 355 356 case '>': 357 if (cursym == SYM_MOVE) { 358 curvalue += direction; 359 // loop = 1 360 } else { 361 if (cursym == SYM_NONE) { 362 cursym = SYM_MOVE; 363 curvalue = direction; 364 // loop = 1 365 } else { 366 nextsym = SYM_MOVE; 367 nextvalue = direction; 368 loop = 0; 369 } 370 } 371 break; 372 373 case ',': 374 if (cursym == SYM_NONE) { 375 cursym = SYM_READ; 376 } else { 377 nextsym = SYM_READ; 378 } 379 loop = 0; 380 break; 381 382 case '.': 383 if (cursym == SYM_NONE) { 384 cursym = SYM_WRITE; 385 } else { 386 nextsym = SYM_WRITE; 387 } 388 loop = 0; 389 break; 390 391 case '[': 392 if (cursym == SYM_NONE) { 393 cursym = SYM_LOOP; 394 } else { 395 nextsym = SYM_LOOP; 396 } 397 loop = 0; 398 break; 399 400 case ']': 401 if (cursym == SYM_NONE) { 402 cursym = SYM_ENDLOOP; 403 } else { 404 nextsym = SYM_ENDLOOP; 405 } 406 loop = 0; 407 break; 408 409 // Ignore other characters 410 default: 411 break; 412 } 413 } 414 } 415 } 416 417 if (cursym == SYM_ENDLOOP) { 418 if (!phi) { 419 std::cerr << "Error: Extra ']'\n"; 420 abort(); 421 } 422 423 // Write loop test 424 { 425 //br label %main.%d 426 builder->CreateBr(testbb); 427 428 //main.%d: 429 430 //%head.%d = phi i8 *[%head.%d, %main.%d], [%head.%d, %main.%d] 431 //Finish phi made at beginning of loop 432 phi->addIncoming(curhead, builder->GetInsertBlock()); 433 Value *head_0 = phi; 434 435 //%tape.%d = load i8 *%head.%d 436 LoadInst *tape_0 = new LoadInst(head_0, tapereg, testbb); 437 438 //%test.%d = icmp eq i8 %tape.%d, 0 439 ICmpInst *test_0 = new ICmpInst(*testbb, ICmpInst::ICMP_EQ, tape_0, 440 ConstantInt::get(C, APInt(8, 0)), testreg); 441 442 //br i1 %test.%d, label %main.%d, label %main.%d 443 BasicBlock *bb_0 = BasicBlock::Create(C, label, brainf_func); 444 BranchInst::Create(bb_0, oldbb, test_0, testbb); 445 446 //main.%d: 447 builder->SetInsertPoint(bb_0); 448 449 //%head.%d = phi i8 *[%head.%d, %main.%d] 450 PHINode *phi_1 = builder-> 451 CreatePHI(PointerType::getUnqual(IntegerType::getInt8Ty(C)), 1, 452 headreg); 453 phi_1->addIncoming(head_0, testbb); 454 curhead = phi_1; 455 } 456 457 return; 458 } 459 460 //End of the program, so go to return block 461 builder->CreateBr(endbb); 462 463 if (phi) { 464 std::cerr << "Error: Missing ']'\n"; 465 abort(); 466 } 467 } 468
