add a new BF->LLVM translator, contributed by Sterling Stein.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@41881 91177308-0d34-0410-b5e6-96231b3b80d8

5 files changed, 721 insertions, 1 deletions

diff --git a/examples/BrainF/BrainF.cpp b/examples/BrainF/BrainF.cpp
new file mode 100644
index 0000000000..e7e11aca0b
--- /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 0000000000..03eedbc3a2
--- /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 0000000000..7d29fe6f72
--- /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 0000000000..54d298c49a
--- /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 d96f66cdaf..4251ab39c5 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