diff options
Diffstat (limited to 'examples')
| -rw-r--r-- | examples/Makefile | 3 | ||||
| -rw-r--r-- | examples/TracingBrainF/BrainF.h | 77 | ||||
| -rw-r--r-- | examples/TracingBrainF/BrainFCodeGen.cpp | 351 | ||||
| -rw-r--r-- | examples/TracingBrainF/BrainFInterpreter.cpp | 116 | ||||
| -rw-r--r-- | examples/TracingBrainF/BrainFOpcodes.cpp | 68 | ||||
| -rw-r--r-- | examples/TracingBrainF/BrainFTraceRecorder.cpp | 155 | ||||
| -rw-r--r-- | examples/TracingBrainF/BrainFVM.h | 63 | ||||
| -rw-r--r-- | examples/TracingBrainF/Makefile | 17 | ||||
| -rw-r--r-- | examples/TracingBrainF/README | 1 |
9 files changed, 850 insertions, 1 deletions
diff --git a/examples/Makefile b/examples/Makefile index 50a6db76aa..bc09b8e047 100644 --- a/examples/Makefile +++ b/examples/Makefile @@ -10,7 +10,8 @@ LEVEL=.. include $(LEVEL)/Makefile.config -PARALLEL_DIRS:= BrainF Fibonacci HowToUseJIT Kaleidoscope ModuleMaker +PARALLEL_DIRS:= BrainF Fibonacci HowToUseJIT Kaleidoscope ModuleMaker \ + TracingBrainF ifeq ($(HAVE_PTHREAD),1) PARALLEL_DIRS += ParallelJIT diff --git a/examples/TracingBrainF/BrainF.h b/examples/TracingBrainF/BrainF.h new file mode 100644 index 0000000000..c5a91b94f6 --- /dev/null +++ b/examples/TracingBrainF/BrainF.h @@ -0,0 +1,77 @@ +//===-- BrainF.h - BrainF compiler class ----------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===--------------------------------------------------------------------===// + +#ifndef BRAINF_H +#define BRAINF_H + +#include "llvm/LLVMContext.h" +#include "llvm/Module.h" +#include "llvm/ExecutionEngine/GenericValue.h" +#include "llvm/ExecutionEngine/JIT.h" +#include "llvm/PassManager.h" +#include "llvm/Support/IRBuilder.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" + + +using namespace llvm; + +class BrainFTraceRecorder { + struct BrainFTraceNode { + uint8_t opcode; + size_t pc; + BrainFTraceNode(uint8_t o, size_t p) + : opcode(o), pc(p), left(0), right(0) { } + void dump(unsigned level); + + // On an if, left is the x != 0 edge. + // A value of 0 indicates an un-traced edge. + // A value of ~0ULL indicates an edge to the trace head. + BrainFTraceNode *left, *right; + }; + + uint8_t prev_opcode; + uint8_t *iteration_count; + std::pair<uint8_t, size_t> *trace_begin, *trace_end, *trace_tail; + DenseMap<size_t, BrainFTraceNode*> trace_map; + Module *module; + BasicBlock *Header; + Value *DataPtr; + PHINode *HeaderPHI; + ExecutionEngine *EE; + + const IntegerType *int_type; + const FunctionType *op_type; + GlobalValue *bytecode_array, *executed_flag; + Value *getchar_func, *putchar_func; + FunctionPassManager *FPM; + + + void commit(); + void initialize_module(); + void compile(BrainFTraceNode* trace); + void compile_opcode(BrainFTraceNode *node, IRBuilder<>& builder); + void compile_plus(BrainFTraceNode *node, IRBuilder<>& builder); + void compile_minus(BrainFTraceNode *node, IRBuilder<>& builder); + void compile_left(BrainFTraceNode *node, IRBuilder<>& builder); + void compile_right(BrainFTraceNode *node, IRBuilder<>& builder); + void compile_put(BrainFTraceNode *node, IRBuilder<>& builder); + void compile_get(BrainFTraceNode *node, IRBuilder<>& builder); + void compile_if(BrainFTraceNode *node, IRBuilder<>& builder); + void compile_back(BrainFTraceNode *node, IRBuilder<>& builder); + +public: + BrainFTraceRecorder(); + ~BrainFTraceRecorder(); + + void record(size_t pc, uint8_t opcode); + void record_simple(size_t pc, uint8_t opcode); +}; + +#endif diff --git a/examples/TracingBrainF/BrainFCodeGen.cpp b/examples/TracingBrainF/BrainFCodeGen.cpp new file mode 100644 index 0000000000..87965460ce --- /dev/null +++ b/examples/TracingBrainF/BrainFCodeGen.cpp @@ -0,0 +1,351 @@ +//===-- BrainFCodeGen.cpp - BrainF trace compiler -----------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===--------------------------------------------------------------------===// + +#include "BrainF.h" +#include "BrainFVM.h" +#include "llvm/Attributes.h" +#include "llvm/Support/StandardPasses.h" +#include "llvm/Target/TargetData.h" +#include "llvm/Target/TargetSelect.h" +#include "llvm/Transforms/Scalar.h" +#include "llvm/ADT/StringExtras.h" + +/// initialize_module - perform setup of the LLVM code generation system. +void BrainFTraceRecorder::initialize_module() { + LLVMContext &Context = module->getContext(); + + // Initialize the code generator, and enable aggressive code generation. + InitializeNativeTarget(); + EngineBuilder builder(module); + builder.setOptLevel(CodeGenOpt::Aggressive); + EE = builder.create(); + + // Create a FunctionPassManager to handle running optimization passes + // on our generated code. Setup a basic suite of optimizations for it. + FPM = new llvm::FunctionPassManager(module); + FPM->add(createInstructionCombiningPass()); + FPM->add(createCFGSimplificationPass()); + FPM->add(createScalarReplAggregatesPass()); + FPM->add(createSimplifyLibCallsPass()); + FPM->add(createInstructionCombiningPass()); + FPM->add(createJumpThreadingPass()); + FPM->add(createCFGSimplificationPass()); + FPM->add(createInstructionCombiningPass()); + FPM->add(createCFGSimplificationPass()); + FPM->add(createReassociatePass()); + FPM->add(createLoopRotatePass()); + FPM->add(createLICMPass()); + FPM->add(createLoopUnswitchPass(false)); + FPM->add(createInstructionCombiningPass()); + FPM->add(createIndVarSimplifyPass()); + FPM->add(createLoopDeletionPass()); + FPM->add(createLoopUnrollPass()); + FPM->add(createInstructionCombiningPass()); + FPM->add(createGVNPass()); + FPM->add(createSCCPPass()); + FPM->add(createInstructionCombiningPass()); + FPM->add(createJumpThreadingPass()); + FPM->add(createDeadStoreEliminationPass()); + FPM->add(createAggressiveDCEPass()); + FPM->add(createCFGSimplificationPass()); + + // Cache the LLVM type signature of an opcode function + int_type = sizeof(size_t) == 4 ? + IntegerType::getInt32Ty(Context) : + IntegerType::getInt64Ty(Context); + const Type *data_type = + PointerType::getUnqual(IntegerType::getInt8Ty(Context)); + std::vector<const Type*> args; + args.push_back(int_type); + args.push_back(data_type); + op_type = + FunctionType::get(Type::getVoidTy(Context), args, false); + + // Setup a global variable in the LLVM module to represent the bytecode + // array. Bind it to the actual bytecode array at JIT time. + const Type *bytecode_type = PointerType::getUnqual(op_type); + bytecode_array = cast<GlobalValue>(module-> + getOrInsertGlobal("BytecodeArray", bytecode_type)); + EE->addGlobalMapping(bytecode_array, BytecodeArray); + + // Setup a similar mapping for the global executed flag. + const IntegerType *flag_type = IntegerType::get(Context, 8); + executed_flag = + cast<GlobalValue>(module->getOrInsertGlobal("executed", flag_type)); + EE->addGlobalMapping(executed_flag, &executed); + + // Cache LLVM declarations for putchar() and getchar(). + const Type *int_type = sizeof(int) == 4 ? IntegerType::getInt32Ty(Context) + : IntegerType::getInt64Ty(Context); + putchar_func = + module->getOrInsertFunction("putchar", int_type, int_type, NULL); + getchar_func = module->getOrInsertFunction("getchar", int_type, NULL); +} + +void BrainFTraceRecorder::compile(BrainFTraceNode* trace) { + LLVMContext &Context = module->getContext(); + + // Create a new function for the trace we're compiling. + Function *curr_func = cast<Function>(module-> + getOrInsertFunction("trace_"+utostr(trace->pc), op_type)); + + // Create an entry block, which branches directly to a header block. + // This is necessary because the entry block cannot be the target of + // a loop. + BasicBlock *Entry = BasicBlock::Create(Context, "entry", curr_func); + Header = BasicBlock::Create(Context, utostr(trace->pc), curr_func); + + // Mark the array pointer as noalias, and setup compiler state. + IRBuilder<> builder(Entry); + Argument *Arg1 = ++curr_func->arg_begin(); + Arg1->addAttr(Attribute::NoAlias); + DataPtr = Arg1; + + // Emit code to set the executed flag. This signals to the recorder + // that the preceding opcode was executed as a part of a compiled trace. + const IntegerType *flag_type = IntegerType::get(Context, 8); + ConstantInt *True = ConstantInt::get(flag_type, 1); + builder.CreateStore(True, executed_flag); + builder.CreateBr(Header); + + // Header will be the root of our trace tree. As such, all loop back-edges + // will be targetting it. Setup a PHI node to merge together incoming values + // for the current array pointer as we loop. + builder.SetInsertPoint(Header); + HeaderPHI = builder.CreatePHI(DataPtr->getType()); + HeaderPHI->addIncoming(DataPtr, Entry); + DataPtr = HeaderPHI; + + // Recursively descend the trace tree, emitting code for the opcodes as we go. + compile_opcode(trace, builder); + + // Run out optimization suite on our newly generated trace. + FPM->run(*curr_func); + + // Compile our trace to machine code, and install function pointer to it + // into the bytecode array so that it will be executed every time the + // trace-head PC is reached. + void *code = EE->getPointerToFunction(curr_func); + BytecodeArray[trace->pc] = + (opcode_func_t)(intptr_t)code; +} + +/// compile_plus - Emit code for '+' +void BrainFTraceRecorder::compile_plus(BrainFTraceNode *node, + IRBuilder<>& builder) { + Value *CellValue = builder.CreateLoad(DataPtr); + Constant *One = + ConstantInt::get(IntegerType::getInt8Ty(Header->getContext()), 1); + Value *UpdatedValue = builder.CreateAdd(CellValue, One); + builder.CreateStore(UpdatedValue, DataPtr); + + if (node->left != (BrainFTraceNode*)~0ULL) + compile_opcode(node->left, builder); + else { + HeaderPHI->addIncoming(DataPtr, builder.GetInsertBlock()); + builder.CreateBr(Header); + } +} + +/// compile_minus - Emit code for '-' +void BrainFTraceRecorder::compile_minus(BrainFTraceNode *node, + IRBuilder<>& builder) { + Value *CellValue = builder.CreateLoad(DataPtr); + Constant *One = + ConstantInt::get(IntegerType::getInt8Ty(Header->getContext()), 1); + Value *UpdatedValue = builder.CreateSub(CellValue, One); + builder.CreateStore(UpdatedValue, DataPtr); + + if (node->left != (BrainFTraceNode*)~0ULL) + compile_opcode(node->left, builder); + else { + HeaderPHI->addIncoming(DataPtr, builder.GetInsertBlock()); + builder.CreateBr(Header); + } +} + +/// compile_left - Emit code for '<' +void BrainFTraceRecorder::compile_left(BrainFTraceNode *node, + IRBuilder<>& builder) { + Value *OldPtr = DataPtr; + DataPtr = builder.CreateConstInBoundsGEP1_32(DataPtr, -1); + if (node->left != (BrainFTraceNode*)~0ULL) + compile_opcode(node->left, builder); + else { + HeaderPHI->addIncoming(DataPtr, builder.GetInsertBlock()); + builder.CreateBr(Header); + } + DataPtr = OldPtr; +} + +/// compile_right - Emit code for '>' +void BrainFTraceRecorder::compile_right(BrainFTraceNode *node, + IRBuilder<>& builder) { + Value *OldPtr = DataPtr; + DataPtr = builder.CreateConstInBoundsGEP1_32(DataPtr, 1); + if (node->left != (BrainFTraceNode*)~0ULL) + compile_opcode(node->left, builder); + else { + HeaderPHI->addIncoming(DataPtr, builder.GetInsertBlock()); + builder.CreateBr(Header); + } + DataPtr = OldPtr; +} + + +/// compile_put - Emit code for '.' +void BrainFTraceRecorder::compile_put(BrainFTraceNode *node, + IRBuilder<>& builder) { + Value *Loaded = builder.CreateLoad(DataPtr); + Value *Print = + builder.CreateSExt(Loaded, IntegerType::get(Loaded->getContext(), 32)); + builder.CreateCall(putchar_func, Print); + if (node->left != (BrainFTraceNode*)~0ULL) + compile_opcode(node->left, builder); + else { + HeaderPHI->addIncoming(DataPtr, builder.GetInsertBlock()); + builder.CreateBr(Header); + } +} + +/// compile_get - Emit code for ',' +void BrainFTraceRecorder::compile_get(BrainFTraceNode *node, + IRBuilder<>& builder) { + Value *Ret = builder.CreateCall(getchar_func); + Value *Trunc = + builder.CreateTrunc(Ret, IntegerType::get(Ret->getContext(), 8)); + builder.CreateStore(Ret, Trunc); + if (node->left != (BrainFTraceNode*)~0ULL) + compile_opcode(node->left, builder); + else { + HeaderPHI->addIncoming(DataPtr, builder.GetInsertBlock()); + builder.CreateBr(Header); + } +} + +/// compile_if - Emit code for '[' +void BrainFTraceRecorder::compile_if(BrainFTraceNode *node, + IRBuilder<>& builder) { + BasicBlock *ZeroChild = 0; + BasicBlock *NonZeroChild = 0; + + IRBuilder<> oldBuilder = builder; + + LLVMContext &Context = Header->getContext(); + + // If both directions of the branch go back to the trace-head, just + // jump there directly. + if (node->left == (BrainFTraceNode*)~0ULL && + node->right == (BrainFTraceNode*)~0ULL) { + HeaderPHI->addIncoming(DataPtr, builder.GetInsertBlock()); + builder.CreateBr(Header); + return; + } + + // Otherwise, there are two cases to handle for each direction: + // ~0ULL - A branch back to the trace head + // 0 - A branch out of the trace + // * - A branch to a node we haven't compiled yet. + // Go ahead and generate code for both targets. + + if (node->left == (BrainFTraceNode*)~0ULL) { + NonZeroChild = Header; + HeaderPHI->addIncoming(DataPtr, builder.GetInsertBlock()); + } else if (node->left == 0) { + NonZeroChild = BasicBlock::Create(Context, + "exit_left_"+utostr(node->pc), + Header->getParent()); + builder.SetInsertPoint(NonZeroChild); + ConstantInt *NewPc = ConstantInt::get(int_type, node->pc+1); + Value *BytecodeIndex = + builder.CreateConstInBoundsGEP1_32(bytecode_array, node->pc+1); + Value *Target = builder.CreateLoad(BytecodeIndex); + CallInst *Call =cast<CallInst>(builder.CreateCall2(Target, NewPc, DataPtr)); + Call->setTailCall(); + builder.CreateRetVoid(); + } else { + NonZeroChild = BasicBlock::Create(Context, + utostr(node->left->pc), + Header->getParent()); + builder.SetInsertPoint(NonZeroChild); + compile_opcode(node->left, builder); + } + + if (node->right == (BrainFTraceNode*)~0ULL) { + ZeroChild = Header; + HeaderPHI->addIncoming(DataPtr, builder.GetInsertBlock()); + } else if (node->right == 0) { + ZeroChild = BasicBlock::Create(Context, + "exit_right_"+utostr(node->pc), + Header->getParent()); + builder.SetInsertPoint(ZeroChild); + ConstantInt *NewPc = ConstantInt::get(int_type, JumpMap[node->pc]+1); + Value *BytecodeIndex = + builder.CreateConstInBoundsGEP1_32(bytecode_array, JumpMap[node->pc]+1); + Value *Target = builder.CreateLoad(BytecodeIndex); + CallInst *Call =cast<CallInst>(builder.CreateCall2(Target, NewPc, DataPtr)); + Call->setTailCall(); + builder.CreateRetVoid(); + } else { + ZeroChild = BasicBlock::Create(Context, + utostr(node->right->pc), + Header->getParent()); + builder.SetInsertPoint(ZeroChild); + compile_opcode(node->right, builder); + } + + // Generate the test and branch to select between the targets. + Value *Loaded = oldBuilder.CreateLoad(DataPtr); + Value *Cmp = oldBuilder.CreateICmpEQ(Loaded, + ConstantInt::get(Loaded->getType(), 0)); + oldBuilder.CreateCondBr(Cmp, ZeroChild, NonZeroChild); +} + +/// compile_back - Emit code for ']' +void BrainFTraceRecorder::compile_back(BrainFTraceNode *node, + IRBuilder<>& builder) { + if (node->right != (BrainFTraceNode*)~0ULL) + compile_opcode(node->right, builder); + else { + HeaderPHI->addIncoming(DataPtr, builder.GetInsertBlock()); + builder.CreateBr(Header); + } +} + +/// compile_opcode - Dispatch to a more specific compiler function based +/// on the opcode of the current node. +void BrainFTraceRecorder::compile_opcode(BrainFTraceNode *node, + IRBuilder<>& builder) { + switch (node->opcode) { + case '+': + compile_plus(node, builder); + break; + case '-': + compile_minus(node, builder); + break; + case '<': + compile_left(node, builder); + break; + case '>': + compile_right(node, builder); + break; + case '.': + compile_put(node, builder); + break; + case ',': + compile_get(node, builder); + break; + case '[': + compile_if(node, builder); + break; + case ']': + compile_back(node, builder); + break; + } +} diff --git a/examples/TracingBrainF/BrainFInterpreter.cpp b/examples/TracingBrainF/BrainFInterpreter.cpp new file mode 100644 index 0000000000..c059afd354 --- /dev/null +++ b/examples/TracingBrainF/BrainFInterpreter.cpp @@ -0,0 +1,116 @@ +//===-- BrainFInterpreter.cpp - BrainF trace compiler interpreter -------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===--------------------------------------------------------------------===// + +#include "BrainF.h" +#include "BrainFVM.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/MemoryBuffer.h" +#include "llvm/Support/raw_ostream.h" +#include <cstdio> +using namespace llvm; + +//Command line options + +static cl::opt<std::string> +InputFilename(cl::Positional, cl::desc("<input brainf>")); + +int main(int argc, char **argv) { + cl::ParseCommandLineOptions(argc, argv, " BrainF compiler\n"); + + if (InputFilename == "") { + errs() << "Error: You must specify the filename of the program to " + "be compiled. Use --help to see the options.\n"; + abort(); + } + + // Read the input file. + MemoryBuffer *Code = MemoryBuffer::getFileOrSTDIN(InputFilename); + const uint8_t *CodeBegin = (const uint8_t*)(Code->getBufferStart()); + + // Create a new buffer to hold the preprocessed code. + MemoryBuffer *ParsedCode = + MemoryBuffer::getNewMemBuffer(sizeof(opcode_func_t) * + (Code->getBufferSize()+1)); + BytecodeArray = (opcode_func_t*)(ParsedCode->getBufferStart()); + size_t BytecodeOffset = 0; + + // Create JumpMap, a special on-the-side data array used to implement + // efficient jumps in the interpreter. + JumpMap = new size_t[Code->getBufferSize()]; + memset(JumpMap, 0, sizeof(size_t) * Code->getBufferSize()); + std::vector<size_t> Stack; + + // Preprocess the input source code, performing three tasks: + // 1 - Remove non-instruction characters + // 2 - Replace character literals with opcode function pointers + // 3 - Precompute the jump targets for [ and ] instructions in JumpMap + for (size_t i = 0; i < Code->getBufferSize(); ++i) { + uint8_t opcode = CodeBegin[i]; + switch (opcode) { + case '>': + BytecodeArray[BytecodeOffset++] = &op_right; + break; + case '<': + BytecodeArray[BytecodeOffset++] = &op_left; + break; + case '+': + BytecodeArray[BytecodeOffset++] = &op_plus; + break; + case '-': + BytecodeArray[BytecodeOffset++] = &op_minus; + break; + case '.': + BytecodeArray[BytecodeOffset++] = &op_put; + break; + case ',': + BytecodeArray[BytecodeOffset++] = &op_get; + break; + case '[': + Stack.push_back(BytecodeOffset); + BytecodeArray[BytecodeOffset++] = &op_if; + break; + case ']': + JumpMap[Stack.back()] = BytecodeOffset; + JumpMap[BytecodeOffset] = Stack.back(); + Stack.pop_back(); + BytecodeArray[BytecodeOffset++] = &op_back; + break; + default: + continue; + } + } + + // Fill in the suffix of the preprocessed source for op_exit. + // Thus, if we reach the end of the source, the program will terminate. + while (BytecodeOffset < Code->getBufferSize()+1) { + BytecodeArray[BytecodeOffset++] = &op_end; + } + + // Setup the array. + uint8_t *BrainFArray = new uint8_t[32768]; + memset(BrainFArray, 0, 32768); + + // Setup the trace recorder. + Recorder = new BrainFTraceRecorder(); + + // Main interpreter loop. + // Note the lack of a explicit loop: every opcode is a tail-recursive + // function that calls its own successor by indexing into BytecodeArray. + uint8_t* data = BrainFArray; + BytecodeArray[0](0, data); + + //Clean up + delete Recorder; + delete Code; + delete ParsedCode; + delete[] BrainFArray; + delete[] JumpMap; + + return 0; +} diff --git a/examples/TracingBrainF/BrainFOpcodes.cpp b/examples/TracingBrainF/BrainFOpcodes.cpp new file mode 100644 index 0000000000..f6c22a3458 --- /dev/null +++ b/examples/TracingBrainF/BrainFOpcodes.cpp @@ -0,0 +1,68 @@ +//===-- BrainFOpcodes.cpp - BrainF interpreter opcodes ------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===--------------------------------------------------------------------===// + +#include "BrainFVM.h" +#include <cstdio> + +opcode_func_t *BytecodeArray = 0; +size_t *JumpMap = 0; +uint8_t executed = 0; + +BrainFTraceRecorder *Recorder = 0; + +void op_plus(size_t pc, uint8_t *data) { + Recorder->record_simple(pc, '+'); + *data += 1; + BytecodeArray[pc+1](pc+1, data); +} + +void op_minus(size_t pc, uint8_t *data) { + Recorder->record_simple(pc, '-'); + *data -= 1; + BytecodeArray[pc+1](pc+1, data); +} + +void op_left(size_t pc, uint8_t *data) { + Recorder->record_simple(pc, '<'); + BytecodeArray[pc+1](pc+1, data-1); +} + +void op_right(size_t pc, uint8_t *data) { + Recorder->record_simple(pc, '>'); + BytecodeArray[pc+1](pc+1, data+1); +} + +void op_put(size_t pc, uint8_t *data) { + Recorder->record_simple(pc, '.'); + putchar(*data); + BytecodeArray[pc+1](pc+1, data); +} + +void op_get(size_t pc, uint8_t *data) { + Recorder->record_simple(pc, ','); + *data = getchar(); + BytecodeArray[pc+1](pc+1, data); +} + +void op_if(size_t pc, uint8_t *data) { + Recorder->record(pc, '['); + size_t new_pc = pc+1; + if (!*data) new_pc = JumpMap[pc]+1; + BytecodeArray[new_pc](new_pc, data); +} + +void op_back(size_t pc, uint8_t *data) { + Recorder->record_simple(pc, ']'); + size_t new_pc = JumpMap[pc]; + BytecodeArray[new_pc](new_pc, data); +} + +void op_end(size_t, uint8_t *) { + return; +} diff --git a/examples/TracingBrainF/BrainFTraceRecorder.cpp b/examples/TracingBrainF/BrainFTraceRecorder.cpp new file mode 100644 index 0000000000..cd8babd199 --- /dev/null +++ b/examples/TracingBrainF/BrainFTraceRecorder.cpp @@ -0,0 +1,155 @@ +//===-- BrainFTraceRecorder.cpp - BrainF trace recorder ------------------==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===--------------------------------------------------------------------===// +// +// This class observes the execution trace of the interpreter, identifying +// hot traces and eventually compiling them to native code. +// +// The operation of the recorder can be divided into four parts: +// 1) Interation Counting - To identify hot traces, we track the execution +// counts of all loop headers ('[' instructions). We use a fixed-size +// array of counters for this, since lack of precision does not affect +// correctness. +// +// 2) Trace Buffering - Once a header has passed a hotness threshold, we +// begin buffering the execution trace beginning from that header the +// next time it is executed. This buffer is of a fixed length, though +// that choice can be tuned for performance. If the end of the buffer +// is reached without execution returning to the header, we throw out +// the trace. +// +// 3) Trace Commit - If the buffered trace returns to the header before +// the buffer limit is reached, that trace is commited to form a trace +// tree. This tree aggregates all execution traces that have been +// observed originating from the header since it passed the hotness +// threshold. The buffer is then cleared to allow a new trace to be +// recorded. +// +// 4) Trace Compilation - Once a secondary hotness threshold is reached, +// trace recording is terminated and the set of observed traces encoded +// in the trace tree are compiled to native code, and a function pointer +// to that trace is installed into the bytecode array in place of one of +// the normal opcode functions. Details of this compilation are in +// BrainFCodeGen.cpp +//===--------------------------------------------------------------------===// + +#include "BrainF.h" +#include "BrainFVM.h" +#include "llvm/Support/raw_ostream.h" + +#define ITERATION_BUF_SIZE 1024 +#define TRACE_BUF_SIZE 256 +#define TRACE_THRESHOLD 50 +#define COMPILE_THRESHOLD 200 + +void BrainFTraceRecorder::BrainFTraceNode::dump(unsigned lvl) { + for (unsigned i = 0; i < lvl; ++i) + outs() << '.'; + outs() << opcode << " : " << pc << "\n"; + if (left && left != (BrainFTraceNode*)~0ULL) left->dump(lvl+1); + if (right && right != (BrainFTraceNode*)~0ULL) right->dump(lvl+1); +} + +BrainFTraceRecorder::BrainFTraceRecorder() + : prev_opcode('+'), iteration_count(new uint8_t[ITERATION_BUF_SIZE]), + trace_begin(new std::pair<uint8_t, size_t>[TRACE_BUF_SIZE]), + trace_end(trace_begin + TRACE_BUF_SIZE), + trace_tail(trace_begin), + module(new Module("BrainF", getGlobalContext())) { + memset(iteration_count, 0, ITERATION_BUF_SIZE); + memset(trace_begin, 0, sizeof(std::pair<uint8_t, size_t>) * TRACE_BUF_SIZE); + + initialize_module(); +} + +BrainFTraceRecorder::~BrainFTraceRecorder() { + delete[] iteration_count; + delete[] trace_begin; + delete FPM; + delete EE; +} + +void BrainFTraceRecorder::commit() { + BrainFTraceNode *&Head = trace_map[trace_begin->second]; + if (!Head) + Head = new BrainFTraceNode(trace_begin->first, trace_begin->second); + + BrainFTraceNode *Parent = Head; + std::pair<uint8_t, size_t> *trace_iter = trace_begin+1; + while (trace_iter != trace_tail) { + BrainFTraceNode *Child = 0; + + if (trace_iter->second == Parent->pc+1) { + if (Parent->left) Child = Parent->left; + else Child = Parent->left = + new BrainFTraceNode(trace_iter->first, trace_iter->second); + } else { + if (Parent->right) Child = Parent->right; + else Child = Parent->right = + new BrainFTraceNode(trace_iter->first, trace_iter->second); + } + + Parent = Child; + ++trace_iter; + } + + if (Parent->pc+1 == Head->pc) + Parent->left = (BrainFTraceNode*)~0ULL; + else + Parent->right = (BrainFTraceNode*)~0ULL; +} + +void BrainFTraceRecorder::record_simple(size_t pc, uint8_t opcode) { + if (executed) { + executed = false; + trace_tail = trace_begin; + } + + if (trace_tail != trace_begin) { + if (trace_tail == trace_end) { + trace_tail = trace_begin; + } else { + trace_tail->first = opcode; + trace_tail->second = pc; + ++trace_tail; + } + } + prev_opcode = opcode; +} + +void BrainFTraceRecorder::record(size_t pc, uint8_t opcode) { + if (executed) { + executed = false; + trace_tail = trace_begin; + } + + if (trace_tail != trace_begin) { + if (pc == trace_begin->second) { + commit(); + trace_tail = trace_begin; + } else if (trace_tail == trace_end) { + trace_tail = trace_begin; + } else { + trace_tail->first = opcode; + trace_tail->second = pc; + ++trace_tail; + } + } else if (opcode == '[' && prev_opcode == ']'){ + size_t hash = pc % ITERATION_BUF_SIZE; + if (iteration_count[hash] == 255) iteration_count[hash] = 254; + if (++iteration_count[hash] > COMPILE_THRESHOLD && trace_map.count(pc)) { + compile(trace_map[pc]); + } else if (++iteration_count[hash] > TRACE_THRESHOLD) { + trace_tail->first = opcode; + trace_tail->second = pc; + ++trace_tail; + } + } + + prev_opcode = opcode; +}
\ No newline at end of file diff --git a/examples/TracingBrainF/BrainFVM.h b/examples/TracingBrainF/BrainFVM.h new file mode 100644 index 0000000000..454df51837 --- /dev/null +++ b/examples/TracingBrainF/BrainFVM.h @@ -0,0 +1,63 @@ +//===-- BrainFVM.h - BrainF interpreter header ----------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===--------------------------------------------------------------------===// + +#ifndef BRAINF_VM_H +#define BRAINF_VM_H + +#include "BrainF.h" +#include "stdint.h" +#include <cstring> + +/// opcode_func_t - A function pointer signature for all opcode functions. +typedef void(*opcode_func_t)(size_t pc, uint8_t* data); + +/// BytecodeArray - An array of function pointers representing the +/// source program. Indexed by PC address. +extern opcode_func_t *BytecodeArray; + +/// JumpMap - An array of on-the-side data used by the interpreter. +/// Indexed by PC address. +extern size_t *JumpMap; + +/// executed - A flag indicating whether the preceding opcode was evaluated +/// within a compiled trace execution. Used by the trace recorder. +extern uint8_t executed; + +/// Recorder - The trace recording engine. +extern BrainFTraceRecorder *Recorder; + +/// op_plus - Implements the '+' instruction. +void op_plus(size_t, uint8_t*); + +/// op_minus - Implements the '-' instruction. +void op_minus(size_t, uint8_t*); + +// op_left - Implements the '<' instruction. +void op_left(size_t, uint8_t*); + +// op_right - Implements the '>' instruction. +void op_right(size_t, uint8_t*); + +// op_put - Implements the '.' instruction. +void op_put(size_t, uint8_t*); + +// op_get - Implements the ',' instruction. +void op_get(size_t, uint8_t*); + +// op_if - Implements the '[' instruction. +void op_if(size_t, uint8_t*); + +// op_back - Implements the ']' instruction. +void op_back(size_t, uint8_t*); + +// op_end - Terminates an execution. +void op_end(size_t, uint8_t*); + + +#endif
\ No newline at end of file diff --git a/examples/TracingBrainF/Makefile b/examples/TracingBrainF/Makefile new file mode 100644 index 0000000000..54676f7f64 --- /dev/null +++ b/examples/TracingBrainF/Makefile @@ -0,0 +1,17 @@ +##===- examples/TracingBrainF/Makefile ------------------- -*- Makefile -*-===## +# +# The LLVM Compiler Infrastructure +# +# This file is distributed under the University of Illinois Open Source +# License. See LICENSE.TXT for details. +# +##===----------------------------------------------------------------------===## +LEVEL = ../.. +TOOLNAME = TracingBrainF +EXAMPLE_TOOL = 1 + +CXXFLAGS += -foptimize-sibling-calls + +LINK_COMPONENTS := scalaropts jit nativecodegen + +include $(LEVEL)/Makefile.common diff --git a/examples/TracingBrainF/README b/examples/TracingBrainF/README new file mode 100644 index 0000000000..11a6392127 --- /dev/null +++ b/examples/TracingBrainF/README @@ -0,0 +1 @@ +This is an example trace-based JIT for Brainfuck, using LLVM as its code generation engine. To compile it, simply drop this directory within llvm/examples in an LLVM source tree, and do `make` in that directory. |