socsvn commit: r270881 - in soc2014/dpl: CellularAutomata ToyRuntime
dpl at FreeBSD.org
dpl at FreeBSD.org
Tue Jul 15 11:03:33 UTC 2014
Author: dpl
Date: Tue Jul 15 11:03:29 2014
New Revision: 270881
URL: http://svnweb.FreeBSD.org/socsvn/?view=rev&rev=270881
Log:
Added some code that uses the llvm library, to use as an example.
Added:
soc2014/dpl/CellularAutomata/
soc2014/dpl/CellularAutomata/AST.h (contents, props changed)
soc2014/dpl/CellularAutomata/Makefile (contents, props changed)
soc2014/dpl/CellularAutomata/compiler.cc (contents, props changed)
soc2014/dpl/CellularAutomata/connway.ca (contents, props changed)
soc2014/dpl/CellularAutomata/count.ac (contents, props changed)
soc2014/dpl/CellularAutomata/countNeighbours.ca (contents, props changed)
soc2014/dpl/CellularAutomata/fib.ac (contents, props changed)
soc2014/dpl/CellularAutomata/flash.ca (contents, props changed)
soc2014/dpl/CellularAutomata/grammar.c (contents, props changed)
soc2014/dpl/CellularAutomata/grammar.y (contents, props changed)
soc2014/dpl/CellularAutomata/interpreter.c (contents, props changed)
soc2014/dpl/CellularAutomata/lemon.c (contents, props changed)
soc2014/dpl/CellularAutomata/lempar.c (contents, props changed)
soc2014/dpl/CellularAutomata/main.c (contents, props changed)
soc2014/dpl/CellularAutomata/on.ca (contents, props changed)
soc2014/dpl/CellularAutomata/runtime.c (contents, props changed)
soc2014/dpl/ToyRuntime/
soc2014/dpl/ToyRuntime/test.c
soc2014/dpl/ToyRuntime/toyruntime.c
soc2014/dpl/ToyRuntime/toyruntime.h
Added: soc2014/dpl/CellularAutomata/AST.h
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ soc2014/dpl/CellularAutomata/AST.h Tue Jul 15 11:03:29 2014 (r270881)
@@ -0,0 +1,55 @@
+#include <stdint.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+// The AST node structure. This contains a node type and two values that can
+// be used to represent children. There are three kinds of AST elements,
+// identified by the low two bits in a pointer. If the low bit is 0, then it
+// is a pointer to one of these structures. If it is 1, then the value is
+// either an integer literal or a register.
+struct ASTNode {
+ enum {
+ NTNeighbours,
+ NTRangeMap,
+ NTOperatorAdd,
+ NTOperatorSub,
+ NTOperatorMul,
+ NTOperatorDiv,
+ NTOperatorAssign,
+ NTOperatorMin,
+ NTOperatorMax
+ } type;
+ uintptr_t val[2];
+};
+// A complete program. This is an array of AST nodes representing single
+// statements.
+struct statements
+{
+ uintptr_t count;
+ struct ASTNode *list[1];
+};
+
+
+// An entry in a range map. This
+struct RangeMapEntry {
+ intptr_t min;
+ intptr_t max;
+ intptr_t val;
+};
+// Range expressions use this structure in one of the val pointers. It
+// contains an array of RangeMapEntries
+struct RangeMap {
+ intptr_t value;
+ intptr_t count;
+ struct RangeMapEntry entries[1];
+};
+
+void printAST(struct ASTNode *ast);
+void runOneStep(int16_t *oldgrid, int16_t *newgrid, int16_t width, int16_t height, struct ASTNode **ast, uintptr_t count);
+typedef void(*automaton)(int16_t *oldgrid, int16_t *newgrid, int16_t width, int16_t height);
+automaton compile(struct ASTNode **ast, uintptr_t count, int optimiseLevel);
+#ifdef __cplusplus
+}
+#endif
Added: soc2014/dpl/CellularAutomata/Makefile
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ soc2014/dpl/CellularAutomata/Makefile Tue Jul 15 11:03:29 2014 (r270881)
@@ -0,0 +1,28 @@
+CC=c99
+#LLVM_LIBS=analysis archive bitreader bitwriter codegen core engine executionengine instrumentation interpreter ipa ipo jit linker native nativecodegen scalaropts selectiondag support target transformutils
+LLVM_LIBS=all
+
+all: cellatom
+
+cellatom: interpreter.o main.o grammar.o compiler.o runtime.bc
+ c++ compiler.o interpreter.o grammar.o main.o `llvm-config --ldflags --libs ${LLVM_LIBS}` -o cellatom -ldl
+
+interpreter.o: interpreter.c AST.h
+main.o: main.c AST.h grammar.h
+
+runtime.bc: runtime.c
+ clang -c -emit-llvm runtime.c -o runtime.bc -O0
+
+compiler.o: compiler.cc AST.h
+ c++ -std=c++0x `llvm-config --cxxflags` -c compiler.cc -O3 #-g -O0 -fno-inline
+grammar.h: grammar.c
+
+grammar.c: grammar.y AST.h lemon
+ ./lemon grammar.y
+
+
+lemon: lemon.c
+ cc lemon.c -o lemon
+
+clean:
+ rm -f interpreter.o main.o grammar.o compiler.o runtime.bc grammar.h grammar.out cellatom lemon
Added: soc2014/dpl/CellularAutomata/compiler.cc
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ soc2014/dpl/CellularAutomata/compiler.cc Tue Jul 15 11:03:29 2014 (r270881)
@@ -0,0 +1,409 @@
+#include "llvm/LinkAllPasses.h"
+#include <llvm/Bitcode/ReaderWriter.h>
+#include <llvm/IR/Constants.h>
+#include <llvm/IR/DerivedTypes.h>
+#include <llvm/Linker.h>
+#include <llvm/ExecutionEngine/ExecutionEngine.h>
+#include <llvm/ExecutionEngine/JIT.h>
+#include <llvm/ExecutionEngine/GenericValue.h>
+#include <llvm/IR/GlobalVariable.h>
+#include <llvm/IR/Module.h>
+#include <llvm/IR/LLVMContext.h>
+#include <llvm/PassManager.h>
+#include "llvm/Analysis/Verifier.h"
+#include <llvm/IR/IRBuilder.h>
+#include <llvm/Support/MemoryBuffer.h>
+#include "llvm/Transforms/IPO/PassManagerBuilder.h"
+#include <llvm/IR/DataLayout.h>
+#include <llvm/Support/system_error.h>
+#include <llvm/Support/TargetSelect.h>
+
+#include "AST.h"
+
+using namespace llvm;
+
+namespace {
+union automaton_or_ptr {
+ automaton a;
+ void *v;
+};
+ class CellularAutomatonCompiler {
+ // LLVM uses a context object to allow multiple threads
+ LLVMContext &C;
+ // The compilation unit that we are generating
+ Module *Mod;
+ // The function representing the program
+ Function *F;
+ // A helper class for generating instructions
+ IRBuilder<> B;
+ // The 10 local registers in the source language
+ Value *a[10];
+ // The 10 global registers in the source language
+ Value *g[10];
+ // The input grid (passed as an argument)
+ Value *oldGrid;
+ // The output grid (passed as an argument)
+ Value *newGrid;
+ // The width of the grid (passed as an argument)
+ Value *width;
+ // The height of the grid (passed as an argument)
+ Value *height;
+ // The x coordinate of the current cell (passed as an argument)
+ Value *x;
+ // The y coordinate of the current cell (passed as an argument)
+ Value *y;
+ // The value of the current cell (passed as an argument, returned at the end)
+ Value *v;
+ // The type of our registers (currently i16)
+ Type *regTy;
+ // Stores a value in the specified register.
+ void storeInLValue(uintptr_t reg, Value *val) {
+ reg >>= 2;
+ assert(reg < 22);
+ if (reg < 10) {
+ B.CreateStore(val, a[reg]);
+ } else if (reg < 20) {
+ B.CreateStore(val, g[reg-10]);
+ } else if (reg == 21) {
+ B.CreateStore(val, v);
+ }
+ }
+ // Loads a value from an AST-encoded form. This may be either a register,
+ // a literal (constant), or a pointer to an expression.
+ Value *getRValue(uintptr_t val) {
+ // If the low bit is 1, then this is either an immediate or a register
+ if (val & 1) {
+ val >>= 1;
+ // Second lowest bit indicates that this is a register
+ if (val & 1) {
+ val >>= 1;
+ assert(val < 22);
+ if (val < 10) {
+ return B.CreateLoad(a[val]);
+ }
+ if (val < 20) {
+ return B.CreateLoad(g[val - 10]);
+ }
+ return B.CreateLoad(v);
+ }
+ // Literal
+ return ConstantInt::get(regTy, val >> 1);
+ }
+ // If the low bit is 0, this is a pointer to an AST node
+ return emitStatement((struct ASTNode*)val);
+ }
+
+ // A helper function when debugging to allow you to print a register-sized
+ // value. This will print the string in the first argument, followed by
+ // the value, and then a newline.
+ void dumpRegister(const char *str, Value *val) {
+#if 0
+ std::string format(str);
+
+ format += "%hd\n";
+ // Create an array constant with the string data
+ Constant *ConstStr = ConstantArray::get(C, format.c_str());
+ // Create a global variable storing it
+ ConstStr = new GlobalVariable(*Mod, ConstStr->getType(), true,
+ GlobalValue::InternalLinkage, ConstStr, str);
+ // Create the GEP indexes
+ Constant *Idxs[] = {ConstantInt::get(Type::getInt32Ty(C), 0), 0 };
+ Idxs[1] = Idxs[0];
+
+ std::vector<Type*> Params;
+ Params.push_back(PointerType::getUnqual(Type::getInt8Ty(C)));
+ // Get the printf() function (takes an i8* followed by variadic parameters)
+ Value *PrintF = Mod->getOrInsertFunction("printf",
+ FunctionType::get(Type::getVoidTy(C), Params, true));
+ // Call printf
+ B.CreateCall2(PrintF, ConstantExpr::getGetElementPtr(ConstStr, Idxs, 2), val);
+#endif
+ }
+
+ public:
+ CellularAutomatonCompiler() : C(getGlobalContext()), B(C){
+ // Load the bitcode for the runtime helper code
+ OwningPtr<MemoryBuffer> buffer;
+ MemoryBuffer::getFile("runtime.bc", buffer);
+ Mod = ParseBitcodeFile(buffer.get(), C);
+ // Get the stub (prototype) for the cell function
+ F = Mod->getFunction("cell");
+ // Set it to have private linkage, so that it can be removed after being
+ // inlined.
+ F->setLinkage(GlobalValue::PrivateLinkage);
+ // Add an entry basic block to this function and set it
+ BasicBlock *entry = BasicBlock::Create(C, "entry", F);
+ B.SetInsertPoint(entry);
+ // Cache the type of registers
+ regTy = Type::getInt16Ty(C);
+
+ // Collect the function parameters
+ auto args = F->arg_begin();
+ oldGrid = args++;
+ newGrid = args++;
+ width = args++;
+ height = args++;
+ x = args++;
+ y = args++;
+
+ // Create space on the stack for the local registers
+ for (int i=0 ; i<10 ; i++) {
+ a[i] = B.CreateAlloca(regTy);
+ }
+ // Create a space on the stack for the current value. This can be
+ // assigned to, and will be returned at the end. Store the value passed
+ // as a parameter in this.
+ v = B.CreateAlloca(regTy);
+ B.CreateStore(args++, v);
+
+ // Create a load of pointers to the global registers.
+ Value *gArg = args;
+ for (int i=0 ; i<10 ; i++) {
+ B.CreateStore(ConstantInt::get(regTy, 0), a[i]);
+ g[i] = B.CreateConstGEP1_32(gArg, i);
+ }
+ }
+
+ // Emits a statement or expression in the source language. For
+ // expressions, returns the result, for statements returns NULL.
+ Value *emitStatement(struct ASTNode *ast) {
+ switch (ast->type) {
+ // All of the arithmetic statements have roughly the same format: load
+ // the value from a register, use it in a computation, store the result
+ // back in the register.
+ case ASTNode::NTOperatorAdd:
+ case ASTNode::NTOperatorSub:
+ case ASTNode::NTOperatorMul:
+ case ASTNode::NTOperatorDiv:
+ case ASTNode::NTOperatorAssign:
+ case ASTNode::NTOperatorMin:
+ case ASTNode::NTOperatorMax: {
+ // Load the value from the register
+ Value *reg = getRValue(ast->val[0]);
+ // Evaluate the expression
+ Value *expr = getRValue(ast->val[1]);
+ // Now perform the operation
+ switch (ast->type) {
+ // Simple arithmetic operations are single LLVM instructions
+ case ASTNode::NTOperatorAdd:
+ expr = B.CreateAdd(reg, expr);
+ break;
+ case ASTNode::NTOperatorSub:
+ expr = B.CreateSub(reg, expr);
+ break;
+ case ASTNode::NTOperatorMul:
+ expr = B.CreateMul(reg, expr);
+ break;
+ case ASTNode::NTOperatorDiv:
+ expr = B.CreateSDiv(reg, expr);
+ break;
+ // Min and Max are implemented by an integer compare (icmp)
+ // instruction followed by a select. The select chooses between
+ // two values based on a predicate.
+ case ASTNode::NTOperatorMin: {
+ Value *gt = B.CreateICmpSGT(expr, reg);
+ expr = B.CreateSelect(gt, reg, expr);
+ break;
+ }
+ case ASTNode::NTOperatorMax: {
+ Value *gt = B.CreateICmpSGT(expr, reg);
+ expr = B.CreateSelect(gt, expr, reg);
+ break;
+ }
+ default: break;
+ }
+ // Now store the result back in the register.
+ storeInLValue(ast->val[0], expr);
+ break;
+ }
+ // Range expressions are more complicated. They involve some flow
+ // control, because we select a different value.
+ case ASTNode::NTRangeMap: {
+ // Get the structure describing this node.
+ struct RangeMap *rm = (struct RangeMap*)ast->val[0];
+ // Load the register that we're mapping
+ Value *reg = getRValue(rm->value);
+ // Now create a basic block for continuation. This is the block that
+ // will be reached after the range expression.
+ BasicBlock *cont = BasicBlock::Create(C, "range_continue", F);
+ // In this block, create a PHI node that contains the result.
+ PHINode *phi = PHINode::Create(regTy, rm->count, "range_result", cont);
+ // Now loop over all of the possible ranges and create a test for each one
+ BasicBlock *current= B.GetInsertBlock();
+ for (int i=0 ; i<rm->count ; i++) {
+ struct RangeMapEntry *re = &rm->entries[i];
+ Value *match;
+ // If the min and max values are the same, then we just need an
+ // equals-comparison
+ if (re->min == re->max) {
+ Value *val = ConstantInt::get(regTy, (re->min >> 2));
+ match = B.CreateICmpEQ(reg, val);
+ } else {
+ // Otherwise we need to emit both values and then compare if
+ // we're greater-than-or-equal-to the smaller, and
+ // less-than-or-equal-to the larger.
+ Value *min = ConstantInt::get(regTy, (re->min >> 2));
+ Value *max = ConstantInt::get(regTy, (re->max >> 2));
+ match = B.CreateAnd(B.CreateICmpSGE(reg, min), B.CreateICmpSLE(reg, max));
+ }
+ // The match value is now a boolean (i1) indicating whether the
+ // value matches this range. Create a pair of basic blocks, one
+ // for the case where we did match the specified range, and one for
+ // the case where we didn't.
+ BasicBlock *expr = BasicBlock::Create(C, "range_result", F);
+ BasicBlock *next = BasicBlock::Create(C, "range_next", F);
+ // Branch to the correct block
+ B.CreateCondBr(match, expr, next);
+ // Now construct the block for the case where we matched a value
+ B.SetInsertPoint(expr);
+ // getRValue() may emit some complex code, so we need to leave
+ // everything set up for it to (potentially) write lots of
+ // instructions and create more basic blocks (imagine nested range
+ // expressions). If this is just a constant, then the next basic
+ // block will be empty, but the SimplifyCFG pass will remove it.
+ Value *exprV = getRValue(re->val);
+ phi->addIncoming(exprV, B.GetInsertBlock());
+ //phi->addIncoming(getRValue(re->val), B.GetInsertBlock());
+ // Now that we've generated the correct value, branch to the
+ // continuation block.
+ B.CreateBr(cont);
+ // ...and repeat
+ current = next;
+ B.SetInsertPoint(current);
+ }
+ // Branch to the continuation block if we've fallen off the end, and
+ // set the value to 0 for this case.
+ B.CreateBr(cont);
+ phi->addIncoming(ConstantInt::get(regTy, 0), current);
+ B.SetInsertPoint(cont);
+ return phi;
+ }
+ case ASTNode::NTNeighbours: {
+ // For each of the (valid) neighbours
+ // Start by identifying the bounds
+ Value *XMin = B.CreateSub(x, ConstantInt::get(regTy, 1));
+ Value *XMax = B.CreateAdd(x, ConstantInt::get(regTy, 1));
+ Value *YMin = B.CreateSub(y, ConstantInt::get(regTy, 1));
+ Value *YMax = B.CreateAdd(y, ConstantInt::get(regTy, 1));
+ // Now clamp them to the grid
+ XMin = B.CreateSelect(B.CreateICmpSLT(XMin, ConstantInt::get(regTy, 0)), x, XMin);
+ YMin = B.CreateSelect(B.CreateICmpSLT(YMin, ConstantInt::get(regTy, 0)), y, YMin);
+ XMax = B.CreateSelect(B.CreateICmpSGE(XMax, width), x, XMax);
+ YMax = B.CreateSelect(B.CreateICmpSGE(YMax, height), y, YMax);
+
+ // Now create the loops
+ BasicBlock *start = B.GetInsertBlock();
+ BasicBlock *xLoopStart = BasicBlock::Create(C, "x_loop_start", F);
+ BasicBlock *yLoopStart = BasicBlock::Create(C, "y_loop_start", F);
+ B.CreateBr(xLoopStart);
+ B.SetInsertPoint(xLoopStart);
+ PHINode *XPhi = B.CreatePHI(regTy, 2);
+ XPhi->addIncoming(XMin, start);
+ B.CreateBr(yLoopStart);
+ B.SetInsertPoint(yLoopStart);
+ PHINode *YPhi = B.CreatePHI(regTy, 2);
+ YPhi->addIncoming(YMin, xLoopStart);
+
+ BasicBlock *endY = BasicBlock::Create(C, "y_loop_end", F);
+ BasicBlock *body = BasicBlock::Create(C, "body", F);
+
+ B.CreateCondBr(B.CreateAnd(B.CreateICmpEQ(x, XPhi), B. CreateICmpEQ(y, YPhi)), endY, body);
+ B.SetInsertPoint(body);
+
+
+ for (unsigned i=0 ; i<ast->val[0]; i++) {
+ Value *idx = B.CreateAdd(YPhi, B.CreateMul(XPhi, width));
+ B.CreateStore(B.CreateLoad(B.CreateGEP(oldGrid, idx)), a[0]);
+ emitStatement(((struct ASTNode**)ast->val[1])[i]);
+ }
+ B.CreateBr(endY);
+ B.SetInsertPoint(endY);
+ BasicBlock *endX = BasicBlock::Create(C, "x_loop_end", F);
+ BasicBlock *cont = BasicBlock::Create(C, "continue", F);
+ // Increment the loop country for the next iteration
+ YPhi->addIncoming(B.CreateAdd(YPhi, ConstantInt::get(regTy, 1)), endY);
+ B.CreateCondBr(B.CreateICmpEQ(YPhi, YMax), endX, yLoopStart);
+
+ B.SetInsertPoint(endX);
+ XPhi->addIncoming(B.CreateAdd(XPhi, ConstantInt::get(regTy, 1)), endX);
+ B.CreateCondBr(B.CreateICmpEQ(XPhi, XMax), cont, xLoopStart);
+ B.SetInsertPoint(cont);
+
+ break;
+ }
+ }
+ return 0;
+ }
+
+ // Returns a function pointer for the automaton at the specified
+ // optimisation level.
+ automaton getAutomaton(int optimiseLevel) {
+ // We've finished generating code, so add a return statement - we're
+ // returning the value of the v register.
+ B.CreateRet(B.CreateLoad(v));
+#ifdef DEBUG_CODEGEN
+ // If we're debugging, then print the module in human-readable form to
+ // the standard error and verify it.
+ Mod->dump();
+ verifyModule(*Mod);
+#endif
+ // Now we need to construct the set of optimisations that we're going to
+ // run.
+ PassManagerBuilder PMBuilder;
+ // Set the optimisation level. This defines what optimisation passes
+ // will be added.
+ PMBuilder.OptLevel = optimiseLevel;
+ // Create a basic inliner. This will inline the cell function that we've
+ // just created into the automaton function that we're going to create.
+ PMBuilder.Inliner = createFunctionInliningPass(275);
+ // Now create a function pass manager that is responsible for running
+ // passes that optimise functions, and populate it.
+ FunctionPassManager *PerFunctionPasses= new FunctionPassManager(Mod);
+ PMBuilder.populateFunctionPassManager(*PerFunctionPasses);
+
+ // Run all of the function passes on the functions in our module
+ for (Module::iterator I = Mod->begin(), E = Mod->end() ;
+ I != E ; ++I) {
+ if (!I->isDeclaration())
+ PerFunctionPasses->run(*I);
+ }
+ // Clean up
+ PerFunctionPasses->doFinalization();
+ delete PerFunctionPasses;
+ // Run the per-module passes
+ PassManager *PerModulePasses = new PassManager();
+ PMBuilder.populateModulePassManager(*PerModulePasses);
+ PerModulePasses->run(*Mod);
+ delete PerModulePasses;
+
+ // Now we are ready to generate some code. First create the execution
+ // engine (JIT)
+ std::string error;
+ ExecutionEngine *EE = ExecutionEngine::create(Mod, false, &error);
+ if (!EE) {
+ fprintf(stderr, "Error: %s\n", error.c_str());
+ exit(-1);
+ }
+ // Now tell it to compile
+ automaton_or_ptr a;
+ a.v = EE->getPointerToFunction(Mod->getFunction("automaton"));
+ return a.a;
+ }
+
+ };
+}
+
+extern "C"
+automaton compile(struct ASTNode **ast, uintptr_t count, int optimiseLevel) {
+ // These functions do nothing, they just ensure that the correct modules are
+ // not removed by the linker.
+ InitializeNativeTarget();
+ LLVMLinkInJIT();
+ CellularAutomatonCompiler compiler;
+ // For each statement, generate some IR
+ for (unsigned i=0 ; i<count ; i++) {
+ compiler.emitStatement(ast[i]);
+ }
+ // And then return the compiled version.
+ return compiler.getAutomaton(optimiseLevel);
+}
Added: soc2014/dpl/CellularAutomata/connway.ca
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ soc2014/dpl/CellularAutomata/connway.ca Tue Jul 15 11:03:29 2014 (r270881)
@@ -0,0 +1,5 @@
+neighbours ( + a1 a0 )
+= v [ v |
+ 0 => [ a1 | 3 => 1] ,
+ 1 => [ a1 | (2,3) => 1]
+]
Added: soc2014/dpl/CellularAutomata/count.ac
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ soc2014/dpl/CellularAutomata/count.ac Tue Jul 15 11:03:29 2014 (r270881)
@@ -0,0 +1,2 @@
++ g0 1
+= v g0
Added: soc2014/dpl/CellularAutomata/countNeighbours.ca
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ soc2014/dpl/CellularAutomata/countNeighbours.ca Tue Jul 15 11:03:29 2014 (r270881)
@@ -0,0 +1,2 @@
+neighbours ( + a1 1)
+= v a1
Added: soc2014/dpl/CellularAutomata/fib.ac
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ soc2014/dpl/CellularAutomata/fib.ac Tue Jul 15 11:03:29 2014 (r270881)
@@ -0,0 +1,5 @@
+neighbours ( + a1 a0 )
+= v [ v |
+ 0 => [ a1 | 3 => 1, => 0]
+ 1 => [ a1 | (2,3) => 1, => 0]
+]
Added: soc2014/dpl/CellularAutomata/flash.ca
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ soc2014/dpl/CellularAutomata/flash.ca Tue Jul 15 11:03:29 2014 (r270881)
@@ -0,0 +1 @@
+= v [ v | 0 => 1 ]
Added: soc2014/dpl/CellularAutomata/grammar.c
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ soc2014/dpl/CellularAutomata/grammar.c Tue Jul 15 11:03:29 2014 (r270881)
@@ -0,0 +1,1132 @@
+/* Driver template for the LEMON parser generator.
+** The author disclaims copyright to this source code.
+*/
+/* First off, code is included that follows the "include" declaration
+** in the input grammar file. */
+#include <stdio.h>
+#line 1 "grammar.y"
+
+ #include "AST.h"
+ #include <assert.h>
+ #include <stdlib.h>
+ #include <string.h>
+
+ static inline void* allocNode(int op, void *reg, void *rval)
+ {
+ struct ASTNode *node = calloc(1, sizeof(struct ASTNode));
+ node->type = op;
+ node->val[0] = (uintptr_t)reg;
+ node->val[1] = (uintptr_t)rval;
+ return node;
+ }
+ static inline void *combineRanges(struct RangeMap *rl, struct RangeMap *r)
+ {
+ if (rl == NULL) { return r; }
+ rl = realloc(rl, sizeof(struct RangeMap) + (sizeof(struct RangeMapEntry) *(rl->count + r->count)));
+ memcpy(&rl->entries[rl->count], r->entries, r->count * sizeof(struct RangeMapEntry));
+ rl->count += r->count;
+ free(r);
+ return rl;
+ }
+#line 32 "grammar.c"
+/* Next is all token values, in a form suitable for use by makeheaders.
+** This section will be null unless lemon is run with the -m switch.
+*/
+/*
+** These constants (all generated automatically by the parser generator)
+** specify the various kinds of tokens (terminals) that the parser
+** understands.
+**
+** Each symbol here is a terminal symbol in the grammar.
+*/
+/* Make sure the INTERFACE macro is defined.
+*/
+#ifndef INTERFACE
+# define INTERFACE 1
+#endif
+/* The next thing included is series of defines which control
+** various aspects of the generated parser.
+** YYCODETYPE is the data type used for storing terminal
+** and nonterminal numbers. "unsigned char" is
+** used if there are fewer than 250 terminals
+** and nonterminals. "int" is used otherwise.
+** YYNOCODE is a number of type YYCODETYPE which corresponds
+** to no legal terminal or nonterminal number. This
+** number is used to fill in empty slots of the hash
+** table.
+** YYFALLBACK If defined, this indicates that one or more tokens
+** have fall-back values which should be used if the
+** original value of the token will not parse.
+** YYACTIONTYPE is the data type used for storing terminal
+** and nonterminal numbers. "unsigned char" is
+** used if there are fewer than 250 rules and
+** states combined. "int" is used otherwise.
+** CellAtomParseTOKENTYPE is the data type used for minor tokens given
+** directly to the parser from the tokenizer.
+** YYMINORTYPE is the data type used for all minor tokens.
+** This is typically a union of many types, one of
+** which is CellAtomParseTOKENTYPE. The entry in the union
+** for base tokens is called "yy0".
+** YYSTACKDEPTH is the maximum depth of the parser's stack. If
+** zero the stack is dynamically sized using realloc()
+** CellAtomParseARG_SDECL A static variable declaration for the %extra_argument
+** CellAtomParseARG_PDECL A parameter declaration for the %extra_argument
+** CellAtomParseARG_STORE Code to store %extra_argument into yypParser
+** CellAtomParseARG_FETCH Code to extract %extra_argument from yypParser
+** YYNSTATE the combined number of states.
+** YYNRULE the number of rules in the grammar
+** YYERRORSYMBOL is the code number of the error symbol. If not
+** defined, then do no error processing.
+*/
+#define YYCODETYPE unsigned char
+#define YYNOCODE 27
+#define YYACTIONTYPE unsigned char
+#define CellAtomParseTOKENTYPE void*
+typedef union {
+ int yyinit;
+ CellAtomParseTOKENTYPE yy0;
+} YYMINORTYPE;
+#ifndef YYSTACKDEPTH
+#define YYSTACKDEPTH 100
+#endif
+#define CellAtomParseARG_SDECL void **p;
+#define CellAtomParseARG_PDECL ,void **p
+#define CellAtomParseARG_FETCH void **p = yypParser->p
+#define CellAtomParseARG_STORE yypParser->p = p
+#define YYNSTATE 53
+#define YYNRULE 21
+#define YY_NO_ACTION (YYNSTATE+YYNRULE+2)
+#define YY_ACCEPT_ACTION (YYNSTATE+YYNRULE+1)
+#define YY_ERROR_ACTION (YYNSTATE+YYNRULE)
+
+/* The yyzerominor constant is used to initialize instances of
+** YYMINORTYPE objects to zero. */
+static const YYMINORTYPE yyzerominor = { 0 };
+
+/* Define the yytestcase() macro to be a no-op if is not already defined
+** otherwise.
+**
+** Applications can choose to define yytestcase() in the %include section
+** to a macro that can assist in verifying code coverage. For production
+** code the yytestcase() macro should be turned off. But it is useful
+** for testing.
+*/
+#ifndef yytestcase
+# define yytestcase(X)
+#endif
+
+
+/* Next are the tables used to determine what action to take based on the
+** current state and lookahead token. These tables are used to implement
+** functions that take a state number and lookahead value and return an
+** action integer.
+**
+** Suppose the action integer is N. Then the action is determined as
+** follows
+**
+** 0 <= N < YYNSTATE Shift N. That is, push the lookahead
+** token onto the stack and goto state N.
+**
+** YYNSTATE <= N < YYNSTATE+YYNRULE Reduce by rule N-YYNSTATE.
+**
+** N == YYNSTATE+YYNRULE A syntax error has occurred.
+**
+** N == YYNSTATE+YYNRULE+1 The parser accepts its input.
+**
+** N == YYNSTATE+YYNRULE+2 No such action. Denotes unused
+** slots in the yy_action[] table.
+**
+** The action table is constructed as a single large table named yy_action[].
+** Given state S and lookahead X, the action is computed as
+**
+** yy_action[ yy_shift_ofst[S] + X ]
+**
+** If the index value yy_shift_ofst[S]+X is out of range or if the value
+** yy_lookahead[yy_shift_ofst[S]+X] is not equal to X or if yy_shift_ofst[S]
+** is equal to YY_SHIFT_USE_DFLT, it means that the action is not in the table
+** and that yy_default[S] should be used instead.
+**
+** The formula above is for computing the action when the lookahead is
+** a terminal symbol. If the lookahead is a non-terminal (as occurs after
+** a reduce action) then the yy_reduce_ofst[] array is used in place of
+** the yy_shift_ofst[] array and YY_REDUCE_USE_DFLT is used in place of
+** YY_SHIFT_USE_DFLT.
+**
+** The following are the tables generated in this section:
+**
+** yy_action[] A single table containing all actions.
+** yy_lookahead[] A table containing the lookahead for each entry in
+** yy_action. Used to detect hash collisions.
+** yy_shift_ofst[] For each state, the offset into yy_action for
+** shifting terminals.
+** yy_reduce_ofst[] For each state, the offset into yy_action for
+** shifting non-terminals after a reduce.
+** yy_default[] Default action for each state.
+*/
+#define YY_ACTTAB_COUNT (85)
+static const YYACTIONTYPE yy_action[] = {
+ /* 0 */ 50, 49, 33, 75, 34, 2, 51, 32, 17, 30,
+ /* 10 */ 23, 22, 21, 20, 19, 18, 16, 25, 50, 49,
+ /* 20 */ 33, 47, 53, 31, 52, 2, 51, 15, 2, 51,
+ /* 30 */ 46, 45, 48, 13, 3, 29, 28, 26, 14, 27,
+ /* 40 */ 10, 35, 12, 24, 1, 9, 11, 76, 8, 7,
+ /* 50 */ 76, 6, 5, 76, 4, 76, 76, 76, 76, 76,
+ /* 60 */ 76, 44, 43, 42, 41, 76, 40, 39, 76, 76,
+ /* 70 */ 76, 76, 76, 76, 76, 38, 76, 37, 76, 76,
+ /* 80 */ 76, 76, 76, 76, 36,
+};
+static const YYCODETYPE yy_lookahead[] = {
+ /* 0 */ 1, 2, 3, 19, 20, 21, 22, 2, 9, 1,
+ /* 10 */ 11, 12, 13, 14, 15, 16, 17, 1, 1, 2,
+ /* 20 */ 3, 5, 0, 7, 20, 21, 22, 20, 21, 22,
+ /* 30 */ 5, 6, 23, 24, 4, 6, 1, 9, 25, 8,
+ /* 40 */ 2, 8, 10, 9, 7, 2, 10, 26, 2, 2,
+ /* 50 */ 26, 2, 2, 26, 2, 26, 26, 26, 26, 26,
+ /* 60 */ 26, 22, 22, 22, 22, 26, 22, 22, 26, 26,
+ /* 70 */ 26, 26, 26, 26, 26, 22, 26, 22, 26, 26,
+ /* 80 */ 26, 26, 26, 26, 22,
+};
+#define YY_SHIFT_USE_DFLT (-2)
+#define YY_SHIFT_COUNT (34)
+#define YY_SHIFT_MIN (-1)
+#define YY_SHIFT_MAX (52)
+static const signed char yy_shift_ofst[] = {
+ /* 0 */ -1, -1, -1, -2, 17, 17, 17, 17, 17, 17,
+ /* 10 */ 17, 17, 17, 16, 25, 33, 37, 52, 50, 49,
+ /* 20 */ 47, 46, 43, 38, 36, 34, 32, 28, 31, 35,
+ /* 30 */ 29, 8, 30, 5, 22,
+};
+#define YY_REDUCE_USE_DFLT (-17)
+#define YY_REDUCE_COUNT (13)
+#define YY_REDUCE_MIN (-16)
+#define YY_REDUCE_MAX (62)
+static const signed char yy_reduce_ofst[] = {
+ /* 0 */ -16, 7, 4, 9, 62, 55, 53, 45, 44, 42,
+ /* 10 */ 41, 40, 39, 13,
+};
+static const YYACTIONTYPE yy_default[] = {
+ /* 0 */ 55, 55, 55, 63, 74, 74, 74, 74, 74, 74,
+ /* 10 */ 74, 74, 74, 74, 74, 74, 74, 74, 74, 74,
+ /* 20 */ 74, 74, 74, 74, 74, 74, 74, 74, 74, 74,
+ /* 30 */ 74, 74, 74, 74, 74, 73, 72, 71, 70, 69,
+ /* 40 */ 68, 67, 66, 65, 64, 62, 61, 60, 59, 58,
+ /* 50 */ 57, 56, 54,
+};
+#define YY_SZ_ACTTAB (int)(sizeof(yy_action)/sizeof(yy_action[0]))
+
+/* The next table maps tokens into fallback tokens. If a construct
+** like the following:
+**
+** %fallback ID X Y Z.
+**
+** appears in the grammar, then ID becomes a fallback token for X, Y,
+** and Z. Whenever one of the tokens X, Y, or Z is input to the parser
+** but it does not parse, the type of the token is changed to ID and
+** the parse is retried before an error is thrown.
+*/
+#ifdef YYFALLBACK
+static const YYCODETYPE yyFallback[] = {
+};
+#endif /* YYFALLBACK */
+
+/* The following structure represents a single element of the
+** parser's stack. Information stored includes:
+**
+** + The state number for the parser at this level of the stack.
+**
+** + The value of the token stored at this level of the stack.
+** (In other words, the "major" token.)
+**
+** + The semantic value stored at this level of the stack. This is
+** the information used by the action routines in the grammar.
+** It is sometimes called the "minor" token.
+*/
+struct yyStackEntry {
+ YYACTIONTYPE stateno; /* The state-number */
+ YYCODETYPE major; /* The major token value. This is the code
+ ** number for the token at this stack level */
+ YYMINORTYPE minor; /* The user-supplied minor token value. This
+ ** is the value of the token */
+};
+typedef struct yyStackEntry yyStackEntry;
+
+/* The state of the parser is completely contained in an instance of
+** the following structure */
+struct yyParser {
+ int yyidx; /* Index of top element in stack */
+#ifdef YYTRACKMAXSTACKDEPTH
+ int yyidxMax; /* Maximum value of yyidx */
+#endif
+ int yyerrcnt; /* Shifts left before out of the error */
+ CellAtomParseARG_SDECL /* A place to hold %extra_argument */
+#if YYSTACKDEPTH<=0
+ int yystksz; /* Current side of the stack */
+ yyStackEntry *yystack; /* The parser's stack */
+#else
+ yyStackEntry yystack[YYSTACKDEPTH]; /* The parser's stack */
+#endif
+};
+typedef struct yyParser yyParser;
+
+#ifndef NDEBUG
+#include <stdio.h>
+static FILE *yyTraceFILE = 0;
+static char *yyTracePrompt = 0;
+#endif /* NDEBUG */
+
+#ifndef NDEBUG
+/*
+** Turn parser tracing on by giving a stream to which to write the trace
+** and a prompt to preface each trace message. Tracing is turned off
+** by making either argument NULL
+**
+** Inputs:
+** <ul>
+** <li> A FILE* to which trace output should be written.
+** If NULL, then tracing is turned off.
+** <li> A prefix string written at the beginning of every
+** line of trace output. If NULL, then tracing is
+** turned off.
+** </ul>
+**
+** Outputs:
+** None.
+*/
+void CellAtomParseTrace(FILE *TraceFILE, char *zTracePrompt){
+ yyTraceFILE = TraceFILE;
+ yyTracePrompt = zTracePrompt;
+ if( yyTraceFILE==0 ) yyTracePrompt = 0;
+ else if( yyTracePrompt==0 ) yyTraceFILE = 0;
+}
+#endif /* NDEBUG */
+
+#ifndef NDEBUG
+/* For tracing shifts, the names of all terminals and nonterminals
+** are required. The following table supplies these names */
+static const char *const yyTokenName[] = {
+ "$", "NUMBER", "REGISTER", "LSQ",
+ "BAR", "RSQ", "COMMA", "LBR",
+ "RBR", "EQ", "GT", "PLUS",
+ "SUB", "MUL", "DIV", "MIN",
+ "MAX", "NEIGHBOURS", "error", "program",
+ "statement_list", "statement", "expression", "range_list",
+ "ranges", "range",
+};
+#endif /* NDEBUG */
+
+#ifndef NDEBUG
+/* For tracing reduce actions, the names of all rules are required.
+*/
+static const char *const yyRuleName[] = {
+ /* 0 */ "program ::= statement_list",
+ /* 1 */ "statement_list ::= statement statement_list",
+ /* 2 */ "statement_list ::=",
+ /* 3 */ "statement ::= expression",
+ /* 4 */ "expression ::= NUMBER",
+ /* 5 */ "expression ::= REGISTER",
+ /* 6 */ "expression ::= LSQ REGISTER BAR range_list",
+ /* 7 */ "range_list ::= ranges RSQ",
+ /* 8 */ "range_list ::= ranges range RSQ",
+ /* 9 */ "ranges ::= ranges range COMMA",
+ /* 10 */ "ranges ::=",
+ /* 11 */ "range ::= LBR NUMBER COMMA NUMBER RBR EQ GT expression",
+ /* 12 */ "range ::= NUMBER EQ GT expression",
+ /* 13 */ "statement ::= PLUS REGISTER expression",
+ /* 14 */ "statement ::= SUB REGISTER expression",
+ /* 15 */ "statement ::= MUL REGISTER expression",
+ /* 16 */ "statement ::= DIV REGISTER expression",
+ /* 17 */ "statement ::= MIN REGISTER expression",
+ /* 18 */ "statement ::= MAX REGISTER expression",
+ /* 19 */ "statement ::= EQ REGISTER expression",
+ /* 20 */ "statement ::= NEIGHBOURS LBR statement_list RBR",
+};
+#endif /* NDEBUG */
+
+
+#if YYSTACKDEPTH<=0
+/*
+** Try to increase the size of the parser stack.
+*/
+static void yyGrowStack(yyParser *p){
+ int newSize;
+ yyStackEntry *pNew;
+
+ newSize = p->yystksz*2 + 100;
+ pNew = realloc(p->yystack, newSize*sizeof(pNew[0]));
+ if( pNew ){
+ p->yystack = pNew;
+ p->yystksz = newSize;
+#ifndef NDEBUG
+ if( yyTraceFILE ){
+ fprintf(yyTraceFILE,"%sStack grows to %d entries!\n",
+ yyTracePrompt, p->yystksz);
+ }
+#endif
+ }
+}
+#endif
+
+/*
+** This function allocates a new parser.
+** The only argument is a pointer to a function which works like
+** malloc.
+**
+** Inputs:
+** A pointer to the function used to allocate memory.
+**
+** Outputs:
+** A pointer to a parser. This pointer is used in subsequent calls
+** to CellAtomParse and CellAtomParseFree.
+*/
+void *CellAtomParseAlloc(void *(*mallocProc)(size_t)){
+ yyParser *pParser;
+ pParser = (yyParser*)(*mallocProc)( (size_t)sizeof(yyParser) );
+ if( pParser ){
+ pParser->yyidx = -1;
+#ifdef YYTRACKMAXSTACKDEPTH
+ pParser->yyidxMax = 0;
+#endif
+#if YYSTACKDEPTH<=0
+ pParser->yystack = NULL;
+ pParser->yystksz = 0;
+ yyGrowStack(pParser);
+#endif
+ }
+ return pParser;
+}
+
+/* The following function deletes the value associated with a
+** symbol. The symbol can be either a terminal or nonterminal.
+** "yymajor" is the symbol code, and "yypminor" is a pointer to
+** the value.
+*/
+static void yy_destructor(
+ yyParser *yypParser, /* The parser */
+ YYCODETYPE yymajor, /* Type code for object to destroy */
+ YYMINORTYPE *yypminor /* The object to be destroyed */
+){
+ CellAtomParseARG_FETCH;
+ switch( yymajor ){
+ /* Here is inserted the actions which take place when a
+ ** terminal or non-terminal is destroyed. This can happen
+ ** when the symbol is popped from the stack during a
+ ** reduce or during error processing or when a parser is
+ ** being destroyed before it is finished parsing.
+ **
+ ** Note: during a reduce, the only symbols destroyed are those
+ ** which appear on the RHS of the rule, but which are not used
+ ** inside the C code.
+ */
+ default: break; /* If no destructor action specified: do nothing */
+ }
+}
+
+/*
+** Pop the parser's stack once.
+**
+** If there is a destructor routine associated with the token which
+** is popped from the stack, then call it.
+**
+** Return the major token number for the symbol popped.
+*/
+static int yy_pop_parser_stack(yyParser *pParser){
+ YYCODETYPE yymajor;
+ yyStackEntry *yytos = &pParser->yystack[pParser->yyidx];
+
+ if( pParser->yyidx<0 ) return 0;
+#ifndef NDEBUG
+ if( yyTraceFILE && pParser->yyidx>=0 ){
+ fprintf(yyTraceFILE,"%sPopping %s\n",
+ yyTracePrompt,
+ yyTokenName[yytos->major]);
+ }
+#endif
+ yymajor = yytos->major;
+ yy_destructor(pParser, yymajor, &yytos->minor);
+ pParser->yyidx--;
+ return yymajor;
+}
+
+/*
+** Deallocate and destroy a parser. Destructors are all called for
+** all stack elements before shutting the parser down.
+**
+** Inputs:
+** <ul>
+** <li> A pointer to the parser. This should be a pointer
+** obtained from CellAtomParseAlloc.
+** <li> A pointer to a function used to reclaim memory obtained
+** from malloc.
+** </ul>
+*/
+void CellAtomParseFree(
+ void *p, /* The parser to be deleted */
+ void (*freeProc)(void*) /* Function used to reclaim memory */
+){
+ yyParser *pParser = (yyParser*)p;
*** DIFF OUTPUT TRUNCATED AT 1000 LINES ***
More information about the svn-soc-all
mailing list