summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--examples/BrainF/BrainF.cpp458
-rw-r--r--examples/BrainF/BrainF.h91
-rw-r--r--examples/BrainF/BrainFDriver.cpp156
-rw-r--r--examples/BrainF/Makefile15
-rw-r--r--examples/Makefile2
5 files changed, 721 insertions, 1 deletions
diff --git a/examples/BrainF/BrainF.cpp b/examples/BrainF/BrainF.cpp
new file mode 100644
index 0000000..e7e11ac
--- /dev/null
+++ b/examples/BrainF/BrainF.cpp
@@ -0,0 +1,458 @@
+//===-- BrainF.cpp - BrainF compiler example ----------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by Sterling Stein and is distributed under the
+// University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===--------------------------------------------------------------------===//
+//
+// This class compiles the BrainF language into LLVM assembly.
+//
+// The BrainF language has 8 commands:
+// Command Equivalent C Action
+// ------- ------------ ------
+// , *h=getchar(); Read a character from stdin, 255 on EOF
+// . putchar(*h); Write a character to stdout
+// - --*h; Decrement tape
+// + ++*h; Increment tape
+// < --h; Move head left
+// > ++h; Move head right
+// [ while(*h) { Start loop
+// ] } End loop
+//
+//===--------------------------------------------------------------------===//
+
+#include "BrainF.h"
+#include "llvm/Constants.h"
+#include "llvm/ADT/STLExtras.h"
+
+using namespace llvm;
+
+//Set the constants for naming
+const char *BrainF::tapereg = "tape";
+const char *BrainF::headreg = "head";
+const char *BrainF::label = "brainf";
+const char *BrainF::testreg = "test";
+
+Module *BrainF::parse(std::istream *in1, int mem, CompileFlags cf) {
+ in = in1;
+ memtotal = mem;
+ comflag = cf;
+
+ header();
+ readloop(0, 0, 0);
+ delete builder;
+ return module;
+}
+
+void BrainF::header() {
+ module = new Module("BrainF");
+
+ //Function prototypes
+
+ //declare void @llvm.memset.i32(i8 *, i8, i32, i32)
+ Function *memset_func = cast<Function>(module->
+ getOrInsertFunction("llvm.memset.i32", Type::VoidTy,
+ PointerType::get(IntegerType::Int8Ty),
+ IntegerType::Int8Ty, IntegerType::Int32Ty,
+ IntegerType::Int32Ty, NULL));
+
+ //declare i32 @getchar()
+ getchar_func = cast<Function>(module->
+ getOrInsertFunction("getchar", IntegerType::Int32Ty, NULL));
+
+ //declare i32 @putchar(i32)
+ putchar_func = cast<Function>(module->
+ getOrInsertFunction("putchar", IntegerType::Int32Ty,
+ IntegerType::Int32Ty, NULL));
+
+
+ //Function header
+
+ //define void @brainf()
+ brainf_func = cast<Function>(module->
+ getOrInsertFunction("brainf", Type::VoidTy, NULL));
+
+ builder = new LLVMBuilder(new BasicBlock(label, brainf_func));
+
+ //%arr = malloc i8, i32 %d
+ ConstantInt *val_mem = ConstantInt::get(APInt(32, memtotal));
+ ptr_arr = builder->CreateMalloc(IntegerType::Int8Ty, val_mem, "arr");
+
+ //call void @llvm.memset.i32(i8 *%arr, i8 0, i32 %d, i32 1)
+ {
+ Value *memset_params[] = {
+ ptr_arr,
+ ConstantInt::get(APInt(8, 0)),
+ val_mem,
+ ConstantInt::get(APInt(32, 1))
+ };
+
+ CallInst *memset_call = builder->
+ CreateCall(memset_func, memset_params, array_endof(memset_params));
+ memset_call->setTailCall(false);
+ }
+
+ //%arrmax = getelementptr i8 *%arr, i32 %d
+ if (comflag & flag_arraybounds) {
+ ptr_arrmax = builder->
+ CreateGEP(ptr_arr, ConstantInt::get(APInt(32, memtotal)), "arrmax");
+ }
+
+ //%head.%d = getelementptr i8 *%arr, i32 %d
+ curhead = builder->CreateGEP(ptr_arr,
+ ConstantInt::get(APInt(32, memtotal/2)),
+ headreg);
+
+
+
+ //Function footer
+
+ //brainf.end:
+ endbb = new BasicBlock(label, brainf_func);
+
+ //free i8 *%arr
+ new FreeInst(ptr_arr, endbb);
+
+ //ret void
+ new ReturnInst(endbb);
+
+
+
+ //Error block for array out of bounds
+ if (comflag & flag_arraybounds)
+ {
+ //@aberrormsg = internal constant [%d x i8] c"\00"
+ Constant *msg_0 = ConstantArray::
+ get("Error: The head has left the tape.", true);
+
+ GlobalVariable *aberrormsg = new GlobalVariable(
+ msg_0->getType(),
+ true,
+ GlobalValue::InternalLinkage,
+ msg_0,
+ "aberrormsg",
+ module);
+
+ //declare i32 @puts(i8 *)
+ Function *puts_func = cast<Function>(module->
+ getOrInsertFunction("puts", IntegerType::Int32Ty,
+ PointerType::get(IntegerType::Int8Ty), NULL));
+
+ //brainf.aberror:
+ aberrorbb = new BasicBlock(label, brainf_func);
+
+ //call i32 @puts(i8 *getelementptr([%d x i8] *@aberrormsg, i32 0, i32 0))
+ {
+ Constant *zero_32 = Constant::getNullValue(IntegerType::Int32Ty);
+
+ Constant *gep_params[] = {
+ zero_32,
+ zero_32
+ };
+
+ Constant *msgptr = ConstantExpr::
+ getGetElementPtr(aberrormsg, gep_params,
+ array_lengthof(gep_params));
+
+ Value *puts_params[] = {
+ msgptr
+ };
+
+ CallInst *puts_call =
+ new CallInst(puts_func,
+ puts_params, array_endof(puts_params),
+ "", aberrorbb);
+ puts_call->setTailCall(false);
+ }
+
+ //br label %brainf.end
+ new BranchInst(endbb, aberrorbb);
+ }
+}
+
+void BrainF::readloop(PHINode *phi, BasicBlock *oldbb, BasicBlock *testbb) {
+ Symbol cursym = SYM_NONE;
+ int curvalue = 0;
+ Symbol nextsym = SYM_NONE;
+ int nextvalue = 0;
+ char c;
+ int loop;
+ int direction;
+
+ while(cursym != SYM_EOF && cursym != SYM_ENDLOOP) {
+ // Write out commands
+ switch(cursym) {
+ case SYM_NONE:
+ // Do nothing
+ break;
+
+ case SYM_READ:
+ {
+ //%tape.%d = call i32 @getchar()
+ CallInst *getchar_call = builder->CreateCall(getchar_func, tapereg);
+ getchar_call->setTailCall(false);
+ Value *tape_0 = getchar_call;
+
+ //%tape.%d = trunc i32 %tape.%d to i8
+ TruncInst *tape_1 = builder->
+ CreateTrunc(tape_0, IntegerType::Int8Ty, tapereg);
+
+ //store i8 %tape.%d, i8 *%head.%d
+ builder->CreateStore(tape_1, curhead);
+ }
+ break;
+
+ case SYM_WRITE:
+ {
+ //%tape.%d = load i8 *%head.%d
+ LoadInst *tape_0 = builder->CreateLoad(curhead, tapereg);
+
+ //%tape.%d = sext i8 %tape.%d to i32
+ SExtInst *tape_1 = builder->
+ CreateSExt(tape_0, IntegerType::Int32Ty, tapereg);
+
+ //call i32 @putchar(i32 %tape.%d)
+ Value *putchar_params[] = {
+ tape_1
+ };
+ CallInst *putchar_call = builder->
+ CreateCall(putchar_func,
+ putchar_params, array_endof(putchar_params));
+ putchar_call->setTailCall(false);
+ }
+ break;
+
+ case SYM_MOVE:
+ {
+ //%head.%d = getelementptr i8 *%head.%d, i32 %d
+ curhead = builder->
+ CreateGEP(curhead, ConstantInt::get(APInt(32, curvalue)),
+ headreg);
+
+ //Error block for array out of bounds
+ if (comflag & flag_arraybounds)
+ {
+ //%test.%d = icmp uge i8 *%head.%d, %arrmax
+ ICmpInst *test_0 = builder->
+ CreateICmpUGE(curhead, ptr_arrmax, testreg);
+
+ //%test.%d = icmp ult i8 *%head.%d, %arr
+ ICmpInst *test_1 = builder->
+ CreateICmpULT(curhead, ptr_arr, testreg);
+
+ //%test.%d = or i1 %test.%d, %test.%d
+ BinaryOperator *test_2 = builder->
+ CreateOr(test_0, test_1, testreg);
+
+ //br i1 %test.%d, label %main.%d, label %main.%d
+ BasicBlock *nextbb = new BasicBlock(label, brainf_func);
+ builder->CreateCondBr(test_2, aberrorbb, nextbb);
+
+ //main.%d:
+ builder->SetInsertPoint(nextbb);
+ }
+ }
+ break;
+
+ case SYM_CHANGE:
+ {
+ //%tape.%d = load i8 *%head.%d
+ LoadInst *tape_0 = builder->CreateLoad(curhead, tapereg);
+
+ //%tape.%d = add i8 %tape.%d, %d
+ BinaryOperator *tape_1 = builder->
+ CreateAdd(tape_0, ConstantInt::get(APInt(8, curvalue)), tapereg);
+
+ //store i8 %tape.%d, i8 *%head.%d\n"
+ builder->CreateStore(tape_1, curhead);
+ }
+ break;
+
+ case SYM_LOOP:
+ {
+ //br label %main.%d
+ BasicBlock *testbb = new BasicBlock(label, brainf_func);
+ builder->CreateBr(testbb);
+
+ //main.%d:
+ BasicBlock *bb_0 = builder->GetInsertBlock();
+ BasicBlock *bb_1 = new BasicBlock(label, brainf_func);
+ builder->SetInsertPoint(bb_1);
+
+ //Make part of PHI instruction now, wait until end of loop to finish
+ PHINode *phi_0 = new PHINode(PointerType::get(IntegerType::Int8Ty),
+ headreg, testbb);
+ phi_0->reserveOperandSpace(2);
+ phi_0->addIncoming(curhead, bb_0);
+ curhead = phi_0;
+
+ readloop(phi_0, bb_1, testbb);
+ }
+ break;
+
+ default:
+ cerr<<"Error: Unknown symbol.\n";
+ abort();
+ break;
+ }
+
+ cursym = nextsym;
+ curvalue = nextvalue;
+ nextsym = SYM_NONE;
+
+ // Reading stdin loop
+ loop = (cursym == SYM_NONE)
+ || (cursym == SYM_MOVE)
+ || (cursym == SYM_CHANGE);
+ while(loop) {
+ *in>>c;
+ if (in->eof()) {
+ if (cursym == SYM_NONE) {
+ cursym = SYM_EOF;
+ } else {
+ nextsym = SYM_EOF;
+ }
+ loop = 0;
+ } else {
+ direction = 1;
+ switch(c) {
+ case '-':
+ direction = -1;
+ // Fall through
+
+ case '+':
+ if (cursym == SYM_CHANGE) {
+ curvalue += direction;
+ // loop = 1
+ } else {
+ if (cursym == SYM_NONE) {
+ cursym = SYM_CHANGE;
+ curvalue = direction;
+ // loop = 1
+ } else {
+ nextsym = SYM_CHANGE;
+ nextvalue = direction;
+ loop = 0;
+ }
+ }
+ break;
+
+ case '<':
+ direction = -1;
+ // Fall through
+
+ case '>':
+ if (cursym == SYM_MOVE) {
+ curvalue += direction;
+ // loop = 1
+ } else {
+ if (cursym == SYM_NONE) {
+ cursym = SYM_MOVE;
+ curvalue = direction;
+ // loop = 1
+ } else {
+ nextsym = SYM_MOVE;
+ nextvalue = direction;
+ loop = 0;
+ }
+ }
+ break;
+
+ case ',':
+ if (cursym == SYM_NONE) {
+ cursym = SYM_READ;
+ } else {
+ nextsym = SYM_READ;
+ }
+ loop = 0;
+ break;
+
+ case '.':
+ if (cursym == SYM_NONE) {
+ cursym = SYM_WRITE;
+ } else {
+ nextsym = SYM_WRITE;
+ }
+ loop = 0;
+ break;
+
+ case '[':
+ if (cursym == SYM_NONE) {
+ cursym = SYM_LOOP;
+ } else {
+ nextsym = SYM_LOOP;
+ }
+ loop = 0;
+ break;
+
+ case ']':
+ if (cursym == SYM_NONE) {
+ cursym = SYM_ENDLOOP;
+ } else {
+ nextsym = SYM_ENDLOOP;
+ }
+ loop = 0;
+ break;
+
+ // Ignore other characters
+ default:
+ break;
+ }
+ }
+ }
+ }
+
+ if (cursym == SYM_ENDLOOP) {
+ if (!phi) {
+ cerr<<"Error: Extra ']'\n";
+ abort();
+ }
+
+ // Write loop test
+ {
+ //br label %main.%d
+ builder->CreateBr(testbb);
+
+ //main.%d:
+
+ //%head.%d = phi i8 *[%head.%d, %main.%d], [%head.%d, %main.%d]
+ //Finish phi made at beginning of loop
+ phi->addIncoming(curhead, builder->GetInsertBlock());
+ Value *head_0 = phi;
+
+ //%tape.%d = load i8 *%head.%d
+ LoadInst *tape_0 = new LoadInst(head_0, tapereg, testbb);
+
+ //%test.%d = icmp eq i8 %tape.%d, 0
+ ICmpInst *test_0 = new ICmpInst(ICmpInst::ICMP_EQ, tape_0,
+ ConstantInt::get(APInt(8, 0)), testreg,
+ testbb);
+
+ //br i1 %test.%d, label %main.%d, label %main.%d
+ BasicBlock *bb_0 = new BasicBlock(label, brainf_func);
+ new BranchInst(bb_0, oldbb, test_0, testbb);
+
+ //main.%d:
+ builder->SetInsertPoint(bb_0);
+
+ //%head.%d = phi i8 *[%head.%d, %main.%d]
+ PHINode *phi_1 = builder->
+ CreatePHI(PointerType::get(IntegerType::Int8Ty), headreg);
+ phi_1->reserveOperandSpace(1);
+ phi_1->addIncoming(head_0, testbb);
+ curhead = phi_1;
+ }
+
+ return;
+ }
+
+ //End of the program, so go to return block
+ builder->CreateBr(endbb);
+
+ if (phi) {
+ cerr<<"Error: Missing ']'\n";
+ abort();
+ }
+}
diff --git a/examples/BrainF/BrainF.h b/examples/BrainF/BrainF.h
new file mode 100644
index 0000000..03eedbc
--- /dev/null
+++ b/examples/BrainF/BrainF.h
@@ -0,0 +1,91 @@
+//===-- BrainF.h - BrainF compiler class ----------------------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by Sterling Stein and is distributed under the
+// University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===--------------------------------------------------------------------===//
+//
+// This class stores the data for the BrainF compiler so it doesn't have
+// to pass all of it around. The main method is parse.
+//
+//===--------------------------------------------------------------------===//
+
+#ifndef BRAINF_H
+#define BRAINF_H
+
+#include "llvm/Module.h"
+#include "llvm/Support/LLVMBuilder.h"
+
+using namespace llvm;
+
+/// This class provides a parser for the BrainF language.
+/// The class itself is made to store values during
+/// parsing so they don't have to be passed around
+/// as much.
+class BrainF {
+ public:
+ /// Options for how BrainF should compile
+ enum CompileFlags {
+ flag_off = 0,
+ flag_arraybounds = 1
+ };
+
+ /// This is the main method. It parses BrainF from in1
+ /// and returns the module with a function
+ /// void brainf()
+ /// containing the resulting code.
+ /// On error, it calls abort.
+ /// The caller must delete the returned module.
+ Module *parse(std::istream *in1, int mem, CompileFlags cf);
+
+ protected:
+ /// The different symbols in the BrainF language
+ enum Symbol {
+ SYM_NONE,
+ SYM_READ,
+ SYM_WRITE,
+ SYM_MOVE,
+ SYM_CHANGE,
+ SYM_LOOP,
+ SYM_ENDLOOP,
+ SYM_EOF
+ };
+
+ /// Names of the different parts of the language.
+ /// Tape is used for reading and writing the tape.
+ /// headreg is used for the position of the head.
+ /// label is used for the labels for the BasicBlocks.
+ /// testreg is used for testing the loop exit condition.
+ static const char *tapereg;
+ static const char *headreg;
+ static const char *label;
+ static const char *testreg;
+
+ /// Put the brainf function preamble and other fixed pieces of code
+ void header();
+
+ /// The main loop for parsing. It calls itself recursively
+ /// to handle the depth of nesting of "[]".
+ void readloop(PHINode *phi, BasicBlock *oldbb, BasicBlock *testbb);
+
+ /// Constants during parsing
+ int memtotal;
+ CompileFlags comflag;
+ std::istream *in;
+ Module *module;
+ Function *brainf_func;
+ Function *getchar_func;
+ Function *putchar_func;
+ Value *ptr_arr;
+ Value *ptr_arrmax;
+ BasicBlock *endbb;
+ BasicBlock *aberrorbb;
+
+ /// Variables
+ LLVMBuilder *builder;
+ Value *curhead;
+};
+
+#endif
diff --git a/examples/BrainF/BrainFDriver.cpp b/examples/BrainF/BrainFDriver.cpp
new file mode 100644
index 0000000..7d29fe6
--- /dev/null
+++ b/examples/BrainF/BrainFDriver.cpp
@@ -0,0 +1,156 @@
+//===-- BrainFDriver.cpp - BrainF compiler driver -----------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by Sterling Stein and is distributed under the
+// University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===--------------------------------------------------------------------===//
+//
+// This program converts the BrainF language into LLVM assembly,
+// which it can then run using the JIT or output as BitCode.
+//
+// This implementation has a tape of 65536 bytes,
+// with the head starting in the middle.
+// Range checking is off by default, so be careful.
+// It can be enabled with -abc.
+//
+// Use:
+// ./BrainF -jit prog.bf #Run program now
+// ./BrainF -jit -abc prog.bf #Run program now safely
+// ./BrainF prog.bf #Write as BitCode
+//
+// lli prog.bf.bc #Run generated BitCode
+// llvm-ld -native -o=prog prog.bf.bc #Compile BitCode into native executable
+//
+//===--------------------------------------------------------------------===//
+
+#include "BrainF.h"
+#include "llvm/Constants.h"
+#include "llvm/ModuleProvider.h"
+#include "llvm/Analysis/Verifier.h"
+#include "llvm/Bitcode/ReaderWriter.h"
+#include "llvm/ExecutionEngine/GenericValue.h"
+#include "llvm/ExecutionEngine/JIT.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/ManagedStatic.h"
+#include <fstream>
+#include <iostream>
+
+using namespace llvm;
+
+//Command line options
+
+static cl::opt<std::string>
+InputFilename(cl::Positional, cl::desc("<input brainf>"));
+
+static cl::opt<std::string>
+OutputFilename("o", cl::desc("Output filename"), cl::value_desc("filename"));
+
+static cl::opt<bool>
+ArrayBoundsChecking("abc", cl::desc("Enable array bounds checking"));
+
+static cl::opt<bool>
+JIT("jit", cl::desc("Run program Just-In-Time"));
+
+
+//Add main function so can be fully compiled
+void addMainFunction(Module *mod) {
+ //define i32 @main(i32 %argc, i8 **%argv)
+ Function *main_func = cast<Function>(mod->
+ getOrInsertFunction("main", IntegerType::Int32Ty, IntegerType::Int32Ty,
+ PointerType::get(PointerType::get(
+ IntegerType::Int8Ty)), NULL));
+ {
+ Function::arg_iterator args = main_func->arg_begin();
+ Value *arg_0 = args++;
+ arg_0->setName("argc");
+ Value *arg_1 = args++;
+ arg_1->setName("argv");
+ }
+
+ //main.0:
+ BasicBlock *bb = new BasicBlock("main.0", main_func);
+
+ //call void @brainf()
+ {
+ CallInst *brainf_call = new CallInst(mod->getFunction("brainf"),
+ "", bb);
+ brainf_call->setTailCall(false);
+ }
+
+ //ret i32 0
+ new ReturnInst(ConstantInt::get(APInt(32, 0)), bb);
+}
+
+int main(int argc, char **argv) {
+ cl::ParseCommandLineOptions(argc, argv, " BrainF compiler\n");
+
+ if (InputFilename == "") {
+ cerr<<"Error: You must specify the filename of the program to "
+ "be compiled. Use --help to see the options.\n";
+ abort();
+ }
+
+ //Get the output stream
+ std::ostream *out = &std::cout;
+ if (!JIT) {
+ if (OutputFilename == "") {
+ std::string base = InputFilename;
+ if (InputFilename == "-") {base = "a";}
+
+ //Use default filename
+ const char *suffix = ".bc";
+ OutputFilename = base+suffix;
+ }
+ if (OutputFilename != "-") {
+ out = new std::
+ ofstream(OutputFilename.c_str(),
+ std::ios::out | std::ios::trunc | std::ios::binary);
+ }
+ }
+
+ //Get the input stream
+ std::istream *in = &std::cin;
+ if (InputFilename != "-") {
+ in = new std::ifstream(InputFilename.c_str());
+ }
+
+ //Gather the compile flags
+ BrainF::CompileFlags cf = BrainF::flag_off;
+ if (ArrayBoundsChecking) {
+ cf = BrainF::CompileFlags(cf | BrainF::flag_arraybounds);
+ }
+
+ //Read the BrainF program
+ BrainF bf;
+ Module *mod = bf.parse(in, 65536, cf); //64 KiB
+ if (in != &std::cin) {delete in;}
+ addMainFunction(mod);
+
+ //Verify generated code
+ if (verifyModule(*mod)) {
+ cerr<<"Error: module failed verification. This shouldn't happen.\n";
+ abort();
+ }
+
+ //Write it out
+ if (JIT) {
+ cout<<"------- Running JIT -------\n";
+ ExistingModuleProvider *mp = new ExistingModuleProvider(mod);
+ ExecutionEngine *ee = ExecutionEngine::create(mp, false);
+ std::vector<GenericValue> args;
+ Function *brainf_func = mod->getFunction("brainf");
+ GenericValue gv = ee->runFunction(brainf_func, args);
+ } else {
+ WriteBitcodeToFile(mod, *out);
+ }
+
+ //Clean up
+ if (out != &std::cout) {delete out;}
+ delete mod;
+
+ llvm_shutdown();
+
+ return 0;
+}
diff --git a/examples/BrainF/Makefile b/examples/BrainF/Makefile
new file mode 100644
index 0000000..54d298c
--- /dev/null
+++ b/examples/BrainF/Makefile
@@ -0,0 +1,15 @@
+##===- examples/BrainF/Makefile ----------------------------*- Makefile -*-===##
+#
+# The LLVM Compiler Infrastructure
+#
+# This file was developed by Sterling Stein and is distributed under
+# the University of Illinois Open Source License. See LICENSE.TXT for details.
+#
+##===----------------------------------------------------------------------===##
+LEVEL = ../..
+TOOLNAME = BrainF
+EXAMPLE_TOOL = 1
+
+LINK_COMPONENTS := jit bitwriter native interpreter
+
+include $(LEVEL)/Makefile.common
diff --git a/examples/Makefile b/examples/Makefile
index d96f66c..4251ab3 100644
--- a/examples/Makefile
+++ b/examples/Makefile
@@ -10,7 +10,7 @@ LEVEL=..
include $(LEVEL)/Makefile.config
-PARALLEL_DIRS:= Fibonacci HowToUseJIT ModuleMaker
+PARALLEL_DIRS:= BrainF Fibonacci HowToUseJIT ModuleMaker
ifeq ($(HAVE_PTHREAD),1)
PARALLEL_DIRS += ParallelJIT
generated by cgit v1.1 at 2024-12-26 14:54:06 +0000