Date: Tue, 15 Jul 2014 11:03:30 GMT From: dpl@FreeBSD.org To: svn-soc-all@FreeBSD.org Subject: socsvn commit: r270881 - in soc2014/dpl: CellularAutomata ToyRuntime Message-ID: <201407151103.s6FB3U1O025653@socsvn.freebsd.org>
next in thread | raw e-mail | index | archive | help
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 ***
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201407151103.s6FB3U1O025653>