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