469 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This class compiles the BrainF language into LLVM assembly.10//11// The BrainF language has 8 commands:12// Command Equivalent C Action13// ------- ------------ ------14// , *h=getchar(); Read a character from stdin, 255 on EOF15// . putchar(*h); Write a character to stdout16// - --*h; Decrement tape17// + ++*h; Increment tape18// < --h; Move head left19// > ++h; Move head right20// [ while(*h) { Start loop21// ] } End loop22//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 43using namespace llvm;44 45//Set the constants for naming46const char *BrainF::tapereg = "tape";47const char *BrainF::headreg = "head";48const char *BrainF::label = "brainf";49const char *BrainF::testreg = "test";50 51Module *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 63void BrainF::header(LLVMContext& C) {64 module = new Module("BrainF", C);65 66 //Function prototypes67 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 header82 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 %d90 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 %d113 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 %d119 curhead = builder->CreateGEP(120 Int8Ty, ptr_arr, ConstantInt::get(C, APInt(32, memtotal / 2)), headreg);121 122 //Function footer123 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 void132 ReturnInst::Create(C, endbb);133 134 //Error block for array out of bounds135 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_32164 };165 166 Constant *msgptr = ConstantExpr::167 getGetElementPtr(aberrormsg->getValueType(), aberrormsg, gep_params);168 169 Value *puts_params[] = {170 msgptr171 };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.end181 BranchInst::Create(endbb, aberrorbb);182 }183}184 185void 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 commands198 switch(cursym) {199 case SYM_NONE:200 // Do nothing201 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 i8212 Value *tape_1 = builder->213 CreateTrunc(tape_0, IntegerType::getInt8Ty(C), tapereg);214 215 //store i8 %tape.%d, i8 *%head.%d216 builder->CreateStore(tape_1, curhead);217 }218 break;219 220 case SYM_WRITE:221 {222 //%tape.%d = load i8 *%head.%d223 LoadInst *tape_0 = builder->CreateLoad(Int8Ty, curhead, tapereg);224 225 //%tape.%d = sext i8 %tape.%d to i32226 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_1232 };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 %d243 curhead = builder->CreateGEP(Int8Ty, curhead,244 ConstantInt::get(C, APInt(32, curvalue)),245 headreg);246 247 //Error block for array out of bounds248 if (comflag & flag_arraybounds)249 {250 //%test.%d = icmp uge i8 *%head.%d, %arrmax251 Value *test_0 = builder->252 CreateICmpUGE(curhead, ptr_arrmax, testreg);253 254 //%test.%d = icmp ult i8 *%head.%d, %arr255 Value *test_1 = builder->256 CreateICmpULT(curhead, ptr_arr, testreg);257 258 //%test.%d = or i1 %test.%d, %test.%d259 Value *test_2 = builder->260 CreateOr(test_0, test_1, testreg);261 262 //br i1 %test.%d, label %main.%d, label %main.%d263 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.%d275 LoadInst *tape_0 = builder->CreateLoad(Int8Ty, curhead, tapereg);276 277 //%tape.%d = add i8 %tape.%d, %d278 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.%d289 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 finish298 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 loop318 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 = 1341 } else {342 if (cursym == SYM_NONE) {343 cursym = SYM_CHANGE;344 curvalue = direction;345 // loop = 1346 } 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 = 1362 } else {363 if (cursym == SYM_NONE) {364 cursym = SYM_MOVE;365 curvalue = direction;366 // loop = 1367 } 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 characters412 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 test426 {427 //br label %main.%d428 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 loop434 phi->addIncoming(curhead, builder->GetInsertBlock());435 Value *head_0 = phi;436 437 //%tape.%d = load i8 *%head.%d438 LoadInst *tape_0 = new LoadInst(Int8Ty, head_0, tapereg, testbb);439 440 //%test.%d = icmp eq i8 %tape.%d, 0441 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.%d445 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 block462 builder->CreateBr(endbb);463 464 if (phi) {465 std::cerr << "Error: Missing ']'\n";466 abort();467 }468}469